计概课件Lecture 20

1、计算概论 (Introduction to Computing),主讲人：马思伟 北京大学数字媒体研究所 ,第二十讲 复习,关于考试,内容：C程序设计 题型 选择、填空、判断、程序阅读、程序补充、编程 时间：1.13（星期二） 一教01101 下午 2:00-4:00 计算概论成绩： 期中30% 平时成绩20% 期末50%,复习,第五讲 程序设计简介及编程环境 第六讲 C程序设计导引-变量与数据类型 第七讲 程序结构设计选择结构 第八讲 程序结构设计循环结构 第九讲 数组 第十讲 数组 第十二讲 数组与字符串 第十三讲 函数与结构化设计 第十四讲 函数与结构化设计 第十五讲 指针 第十六讲 指

2、针 第十七讲 数组、指针与函数 第十八讲 结构体 第十九讲 排序查找算法、文件操作 第二十讲 复习,机器语言,机器指令采用二进制代码形式，它们符合具体计算机的指令系统，可以由计算机直接执行。因此机器指令实际上也是一种可以在程序设计中使用的语言，被称为“机器语言”。每一条机器指令包括两个主要方面：操作（指出计算机应做什么）和被操作的对象（指出处理的数据或它的地址）。 机器指令 格式：操作码 操作数操作数 分类：数据传送、算术运算、逻辑运算、控制转移,汇编语言,从人的思维方式而言更适合于用概念描述事物，对于烦琐冗长的数字编码，由于它们不能与概念和概念之间的语义联系产生任何提示作用，则显然对设计思维

3、没有任何帮助作用，纯粹是一种累赘。人们显然更希望用有帮助记忆作用的符号来书写程序，例如用 ADD 表示加法操作，用 JMP 表示控制性转移等。操作的对象（数据或数据的地址）最好也能用符号形式表示，例如用 X、Y代表两个存储数据的容器。显然这样做比直接采用二进码方便得多。这就是“汇编程序设计语言”的基本想法。 格式 助记符 操作数操作数,高级程序设计语言,高级语言在对计算过程的描述方面，完全脱离了简单的指令方式，采用类似于数学公式的书写方式描述由一些数据计算出结果的过程，用一些更高级程序流程描述结构取代简单的跳转指令方式，以更好地满足书写程序的需要。 程序存储数据的空间处理数据的语句 4个核心概

4、念 变量 表达式、语句、赋值,C程序设计导引,程序的基本框架 编译预处理: #include, #define 自定义函数的声明 主函数：main() 自定义函数的定义 程序的基本元素 标识符和关键字 标识符是以字母，下划线( _ ) 开始的一个字符序列，后面可以跟字母，下划线，数字 关键字：具有专门的意义和用途，不能当作一般的标识符使用 数据类型、常量和变量 基本数据类型：整型、短整型、长整型、单精度浮点型、双精度浮点型、字符型、空类型 常量：直接使用；#define定义 变量：内存空间 运算符和表达式 算术、关系、逻辑、位运算、赋值、条件运算 语句和控制流,字符数据类型,字符类型数据与整数

5、(0-255), 区别 char c1 = 0;赋初值为字符0 char c1= 0; 字符类型数据的运算 char c2 = A; printf(“%c”, c2+1); 特殊类型字符 反斜线（Backslash） 退格（Backspace）b 回车（Carriage return）r 进纸符（Form feed）f 制表符（Form feed）t 换行（New line）n 单引号（Single quote）,数据类型转换,两种方式 强制转换，使用 (DataType) 强制转换，例 int a, b=1; float c=4.3; a = b + (int) c; 赋值表达式也会进行强制

6、转换 a = b + c; 自动转换，表达式运算中低精度变量自动向高精度转换 区别上面的a = b + (int) c;与a = b + c; 区别 c = 5/2; 与 c = 5.0/2; a = 5.0/2;与a = 5/2;,自加自减运算,区别+在变量前后 j = +i; 表示先将i的值加1，再赋给j，如果i的值是5，则j的值是6。（先给变量加1，再使用变量） j = i+; 表示先将i的值赋给j，再把i的值加1，如果i的值是5，则j的值是5。（先使用变量，再给变量加1）,位运算与逻辑运算,位运算：逐位进行逻辑运算 逻辑运算：非零为真，运算结果为0/1分别表示真假 int a=1, b

7、=2; if (a,运算符优先级,最高优先级: .,-, , () /左右结合 单目运算：-, , !, +, -, !(), sizeof /右结合 算术乘除运算: *, /, % /左结合 算术加减运算：+, - /左结合 移位运算: , , = /左结合 相等关系运算：=, != /左结合 按位与： 赋值语句，如：x = y + z; 函数调用语句，如：scanf(“%d”, 程序控制语句 空语句 ,三种结构语句,程序控制语句及其控制说明： 分支控制语句：if-else, switch-case/default 循环控制语句：while, do-while, for 此外，还有一些与程序

8、转移控制有关的语句：break, continue, return 用大括号（）把修饰性描述和语句组合在一起的，称为复合语句。复合语句在语法上和简单语句是一样的（代码段：也包括不含有修饰性描述的情况）,分支控制if-else,条件表达式加括号，多条语句用 括起来 嵌套if-else, 最近邻原则-else与最近的if语句共同构成一句 if (i0) if (ji) x=j; else x=i; 区别 if (i0) if (ji) x=j; else x=i;,多分支语句switch-case/default,表达式带括号 Case 值后加冒号 表达式的值必须是整数或者字符 计算表达式选择入口

9、 遇到break或switch语句结束停止,循环语句,循环控制语句包括： 当型循环语句：for 当型循环语句：while 直到型型循环语句：do-while,循环语句for,循环语句for（另一种当型循环） for (初始条件表达式;循环控制表达式;循环操作表达式) 语句/语句组 一次for循环执行过程 首先执行初始条件表达式（第一次）：可以为空 循环控制表达式：一定是一个数值表达式，也可以为空 如果表达式值为真，条件成立，执行循环体一次 如果表达式值为假，条件不成立，退出循环 如果省略，默认值为真，直到遇到break, return语句退出循环 循环操作表达式：也可为空,循环语句for,例，

10、计算从0到100的整数中有多少个数是偶数（包括），有多少数是的倍数 #include int main() int i, n2=0, n3=0; for(i=0; i=100; i+) if (i%2=0) n2+; else if (i%3=0) n3+; printf(“n2=%d, n3=%dn”, n2, n3); return 0; ,循环语句while,循环语句while（当型循环） while (表达式) 语句/语句组 表达式必须是数值表达式 一次循环 计算表达式的值 如果表达式值为真，执行循环体，为假退出 循环,循环语句do-while,循环语句do-while（直到型循环）

11、do 语句/语句组 while (表达式); 一次循环 执行一次循环体 计算表达式，条件成立再执行一次循环体， 否则退出循环,循环语句do-while,程序转移语句,程序转移相关语句包括： break continue,程序转移语句break,break退出的是包含它的最内层循环体 例: #include int main() int i, j; for (i=1; i10; i+) for (j=1; j=10; j+) if (i+j)%5=0) printf(“%d %d”, i, j ); break; return 0; ,程序转移语句continue,continue语句用来结束本

12、次循环(while, do-while, for) ，跳过循环体中continue之后尚未执行的语句，接着进行终止条件的判断，以决定是否继续循环。注意：在进行终止条件的判断前，都应先执行迭代语句。它的格式为： continue；,输入输出,在标准输入输出函数库（stdio.h）中，提供了通过标准输入输出设备（键盘和显示器）进行数据的输入输出函数： 单个字符输入：int getchar()，返回的是字符的ASCII码 单个字符输出：int putchar(int) 格式化输入：int scanf(constrol_string, arg1, arg2, ) 格式化输出：int printf(co

13、nstrol_string, arg1, arg2, ),输入输出,getchar(), putchar(),输入输出,在scanf()中的格式控制中，还可以控制多个输入数据之间的分隔标记，如：scanf(“%c,%d,%f”, 如果n的值为10，则输出效果为,复习,第五讲 程序设计简介及编程环境 第六讲 C程序设计导引-变量与数据类型 第七讲 程序结构设计选择结构 第八讲 程序结构设计循环结构 第九讲 数组 第十讲 数组 第十二讲 数组与字符串 第十三讲 函数与结构化设计 第十四讲 函数与结构化设计 第十五讲 指针 第十六讲 指针 第十七讲 数组、指针与函数 第十八讲 结构体 第十九讲 排序

14、查找算法、文件操作 第二十讲 复习,数组,数组 数组定义时数组的长度是个常量，不能包含变量 数组的下标从0开始，注意数组下标越界使用 数组的初始化 例 int score5; char cards4 = a, 0, r, W;,数组,数组 数组元素的访问：每个元素是一个变量 数组元素在内存中的存放：连续存放，多维数组按行存放 int n2323=1,2,3,2,4,6;,多维数组的使用,计算全年级180名学生每个学生8门课的平均成绩和每门课全年级平均成绩 求解过程 定义一个1808的二维数组记录各门课成绩 录入每个人各门课成绩 计算每名学生的平均成绩并打印出来 计算每门课程的平均成绩并打印出来

15、,多维数组的使用,多维数组的使用,复习,第五讲 程序设计简介及编程环境 第六讲 C程序设计导引-变量与数据类型 第七讲 程序结构设计选择结构 第八讲 程序结构设计循环结构 第九讲 数组 第十讲 数组 第十二讲 数组与字符串 第十三讲 函数与结构化设计 第十四讲 函数与结构化设计 第十五讲 指针 第十六讲 指针 第十七讲 数组、指针与函数 第十八讲 结构体 第十九讲 排序查找算法、文件操作 第二十讲 复习,字符数组与字符串,字符串 字符数组以0结尾，字符串长度与字符数组长度不等同 char str12 = “Beijing”; 另一种写法 char str=“Beijing”; 字符串输出 pr

16、intf(“%s”, str);,a9,字符串变量输入,字符串变量初始化 定义时初始化 char s12 = “I am happy”; char *str=“I am happy”; 使用scanf(), gets()输入 char name12; char *str; scanf(“%s”, name); scanf(“%s”, str); str = name; scanf(“%s”, str); gets(name);,字符串变量输出,使用printf(), puts()输出 printf(“%s”, s); printf(“%s”, str); puts(name);,字符串操作,字

17、符串复制 使用循环操作 #inlcude int main() char s12 = “I am happy”; char t20; int i; for (i=0; si!=0; i+) ti = si ti = 0; printf(“%sn%s”, s, t); return 0; ,字符串复制 使用指针操作 #inlcude #inlcude int main() char s12 = “I am happy”; char t20; char *ps=s, *pt=t; for (; *ps!=0; ps+, pt+) *pt = *ps; *pt = 0; printf(“%sn%s”

18、, s, t); return 0; ,字符串处理函数,头文件： strcat(字符数组1，字符串2)：连接字符串 字符串2的第一个字符覆盖第一个字符串的0 strcpy(字符数组1，字符串2)：复制字符串 strcmp(字符串1，字符串2)：比较字符串 strlen(字符串)：求字符串长度 不包括0 strlwr(字符数组)：把字符串中字符都变小写 strupr (字符数组)：把字符串中字符都变大写,复习,第五讲 程序设计简介及编程环境 第六讲 C程序设计导引-变量与数据类型 第七讲 程序结构设计选择结构 第八讲 程序结构设计循环结构 第九讲 数组 第十讲 数组 第十二讲 数组与字符串 第十

19、三讲 函数与结构化设计 第十四讲 函数与结构化设计 第十五讲 指针 第十六讲 指针 第十七讲 数组、指针与函数 第十八讲 结构体 第十九讲 排序查找算法、文件操作 第二十讲 复习,函数说明和定义,int multiple(int x,int y); / 函数说明 void main() int a=0,b=0; scanf(“%d %d”, ,函数的调用,调用分类 函数语句 printf(“ Hello world!”); 函数表达式 c=2*max(a, b); 函数参数 m = max(a, max(b, c);,形参和实参,在函数调用前不占内存，只在发生函数调用时才给形参分配内存单元 传

20、值调用时，形参与实参是不同的内存单元,void swap(int a, int b) int tmp=0; tmp = a; a = b; b = tmp; ,void main( ) int a=0, b=0; a = 20; b = 45; if (a1时， age(n) = age(n-1)+2; 当n=1时， age(n) = 10; int age (int n) if (n=1) return 10; else return (age(n-1)+2); ,age(5),age(4)+2,age(3)+2,age(2)+2,age(1)+2,age(1),输出age(5),n=5,n

21、=4,n=3,n=2,n=1,复习,第五讲 程序设计简介及编程环境 第六讲 C程序设计导引-变量与数据类型 第七讲 程序结构设计选择结构 第八讲 程序结构设计循环结构 第九讲 数组 第十讲 数组 第十二讲 数组与字符串 第十三讲 函数与结构化设计 第十四讲 函数与结构化设计 第十五讲 指针 第十六讲 指针 第十七讲 数组、指针与函数 第十八讲 结构体 第十九讲 排序查找算法、文件操作 第二十讲 复习,内存中的资源地址,0 x0012FF70 0 x0012FF74 0 x0012FF78 0 x0012FF7C 0 x0012FF80 0 x0012FF84,void main( ) int

22、a = 15； int b = 2； int c = 76； int i = 30； int j = 126； int k = 5； ,内存中的资源地址,/images/content/166502.jpg,N49 Nebula,把某个变量的地址称为“指向该变量的指针”,76,0 x0012FF78,c,我们能不能拿到、看到地址？,可以利用 取地址运算符“ /定义int型变量c，并赋值76； int *pointer; /定义名字为pointer的指针变量; /“*”表示变量pointer的类型为指针类型； pointer = /将变量c的地址赋值给指针变量

23、pointer； /赋值后，称指针变量pointer指向了变量c,指针变量的定义、赋值,定义一个指向int型变量c的指针变量 int *pointer ; pointer = ,能不能写成： int *pointer ; pointer = c ;,绝对不行！ 因为pointer是存放地址的变量，所以只能存放地址！,指针变量的使用,则*pointer： 为“pointer所指向的存储单元的内容”； “pointer所指向的存储单元的内容” 是 变量c,若有：,0 x0012FF74 0 x0012FF75 0 x0012FF76 0 x0012FF77 0 x0012FF78 0 x0012F

24、F79 0 x0012FF7A 0 x0012FF7B,int c = 76;, ,0 x0012FF78,pointer,int c = 76; int *pointer = ,可以利用 指针运算符* 实现,动态数组 申请空间,使用前要在文件的开始包含文件。例如： #include void main( ) double *pd; pd = (double *)malloc(sizeof(double) * 50); ,动态数组 赋值,与静态数组相同，动态数组的元素下标也是从0开始的。所以对上面pi所指的数组可以用如下的循环将全部元素赋初值为0： int j; for(j=0; j100;

25、j+) *(pi+j) = 0;,动态数组 申请空间,申请结构体动态数组 struct point int x, y; struct point *pp; pp = (struct point *)malloc(sizeof(struct point)*100); float *pf; pf = (float *)malloc(sizeof(float)*20);,动态数组 空间回收,静态数组是数组变量定义时分配空间的，它的空间在该变量失效时由系统自动回收。动态数组是用malloc()函数动态申请的，需要在程序中调用free()函数主动释放。如： char *pc; /定义字符指针pc pc

26、= (int *)malloc(sizeof(char) * 2); / 两个数组元素，每个元素类型为char free(pc);,复习,第五讲 程序设计简介及编程环境 第六讲 C程序设计导引-变量与数据类型 第七讲 程序结构设计选择结构 第八讲 程序结构设计循环结构 第九讲 数组 第十讲 数组 第十二讲 数组与字符串 第十三讲 函数与结构化设计 第十四讲 函数与结构化设计 第十五讲 指针 第十六讲 指针 第十七讲 数组、指针与函数 第十八讲 结构体 第十九讲 排序查找算法、文件操作 第二十讲 复习,数组与指针,指向数组元素的指针 例： int a10; /定义一个包含10个整型数据的数组 i

27、nt *p; /定义一个指向整型变量的指针变量 p=,数组与指针,通过指针引用数组元素 地址偏移，取得相应元素的地址 p+i 和a+i就是ai的地址 p+1=1004不是1001！ p+1所代表的地址实际上是 p+1*d, d表示一个数组元素所占的字节数 累加地址，p+ 取地址（指针）内容，获得相应的数组元素 *p, *(p+i),*(a+i)表示p+i, a+i所指向的数组元素即ai, 可视为变址运算符，即按a+i计算地址，然后找出此地址单元的值 指向数组的指针变量也可以带下标，pi与*(p+i)等价 pi *(p+i),a0,a9,ai,数组与指针,通过指针引用数组元素 方法1：下标法，即

28、ai 方法2：地址法，即*(a+i)，相应于计算a+i*d地址 方法3：指针法，*p, pi, *(p+i) 方法比较：输出一个有10个整数元素的数组的值 指针法(*p)效率最高 数组名不允许进行a+运算（形参除外）,void main() for(i=0; i10; i+) printf(“%d “，ai); . ,void main() for(i=0; iage. (*p).name, (*p).age -指向运算符 struct student *p; for (p=stu; pnum, p-name, p-sex, p-age);,复习,第五讲 程序设计简介及编程环境 第六讲 C程序

29、设计导引-变量与数据类型 第七讲 程序结构设计选择结构 第八讲 程序结构设计循环结构 第九讲 数组 第十讲 数组 第十二讲 数组与字符串 第十三讲 函数与结构化设计 第十四讲 函数与结构化设计 第十五讲 指针 第十六讲 指针 第十七讲 数组、指针与函数 第十八讲 结构体 第十九讲 排序查找算法、文件操作 第二十讲 复习,查找,查找是利用给出的关键值，在一个数据集合或数据序列中找出与关键值匹配的一个或一组数据的过程。 顺序查找：最简单的查找算法。 程序从数据序列的第一个数据开始，逐个与关键值比较，直到找到一个或所有的匹配数据为止（也可能找不到）。顺序查找不要求待查找的数据序列已经排好序。但当待查

30、找数据序列中数据比较多时，顺序查找的效率将十分低。 二分查找：二分查找可以提高查找效率，但要求待查找的数据序列已经排好序。 以序列中间数据为界将待查找的数据序列分成两个子序列，比较匹配关键值与中间数据的大小，再确定去哪个子序列中继续查找。这样逐步缩小范围，直到找到所需数据。,顺序查找,void main int numbers10 = 4, 6, 9, 11, 79, 52, 34, 1, 25, 17; int key; / 待查找整数 int j; / 循环变量 int count = 0; / 记录找到的出现数 scanf(%d, ,二分查找,#define MAX_NUM 10 voi

31、d main int numbersMAX_NUM=1, 4, 6, 9, 11, 17, 25, 34, 52, 79; int key; / 待查找的整数 int curMin= 0, curMax= MAX_NUM-1; int answer = 0; / 记录待查找数是否出现在数组中 scanf(%d, ,例 9 第一次 9 numbers4=11 0, 9 第二次 9 numbers1= 4 0, 3 第三次 9 numbers2 = 6 2, 3 第四次 9 numbers3= 9 3, 3,插入排序,#define NUMBER 100 Int arrayNUMBER; Int

32、main() int j, r; for(j=0; jNUMBER; j+) scanf(“%d”, arrayj); return 0; ,for(j=1; j=0; r- -) if(tmparrayr) arrayr+1 = arrayr; arrayr = tmp; else arrayr+1 = tmp; break; ,选择排序,#include #include void main() int n; int* numbers; int i,j; int tempNum; int tempIndex; numbers = (int*)malloc( n*sizeof(int) );

33、 if( !numbers ) return;,for( i=0; in; i+ ) j=i; tempNum = numbersj; tempIndex = j; for( j=i+1; jn; j+ ) if( numbersj tempNum ) tempNum = numbersj; tempIndex = j; numberstempIndex = numbersi; numbersi = tempNum; free( numbers ); ,冒泡排序法（程序）,#include void main( ) int number, *array; int j, r; printf(“please input the number”); scanf(“%d”, ,文件的打开与关闭,文件打开 FILE *fp; fp = fopen(“文件名”，使用文件方式) 打开方式 “r”只读打开一个文本文件 “w”只写打开一个文本文件 “rb”只读打开一个二进制文件 “wb”只写打开一个二进制文件 “a”向文本文件追加数据 “ab”向二进制文件追加数据,文件的读写,fputc(ch, fp) fputc(ch, fp) 把一个字符写到磁盘文件上去 fgetc() ch=fge