C语言高级程序设计(上)ppt.ppt

1,C语言高级程序设计(上),2,第1章 语言提高,3,概述,1.1 基本数据类型、操作符、表达式 1.2 语句 1.3 数组 1.4 指针 1.5 结构和联合体 1.6 函数 1.7 存储类型 1.8 预编译 1.9 有缓冲方式的文件操作及控制台操作 1.10 其它库函数操作,4,1.1 基本数据类型、操作符、表达式,在C语言中，变量的声明格式是： 类型 变量； 例: int x = 5;,5,1.1 基本数据类型、操作符、表达式,6,1.1 基本数据类型、操作符、表达式,7,1.1 基本数据类型、操作符、表达式,unsigned、signed修饰 十六进制、十进制、八进制表示 字符常量表示及编码 转义符 逻辑类型的规定,8,1.1 基本数据类型、操作符、表达式,1.1.2 操作符、表达式 1算术操作符,9,1.1 基本数据类型、操作符、表达式,1.1.2 操作符、表达式 2.关系操作符,10,1.1 基本数据类型、操作符、表达式,1.1.2 操作符、表达式 2.关系操作符 “x y 2” 的含义 “x” 和 “!x” 作为逻辑表达式的含义,11,1.1 基本数据类型、操作符、表达式,1.1.2 操作符、表达式 3.逻辑操作符,12,1.1 基本数据类型、操作符、表达式,1.1.2 操作符、表达式 4. 位操作符,13,1.1 基本数据类型、操作符、表达式,1.1.2 操作符、表达式 5移位操作符,14,1.1 基本数据类型、操作符、表达式,1.1.2 操作符、表达式 5移位操作符 例1.1：我们可以将x的第3至第7位置为y。 int x=0x44444444; int y=7; x=(x,15,1.1 基本数据类型、操作符、表达式,1.1.2 操作符、表达式 5移位操作符 例1.2：我们可以将x的第3至第7取到y中，代码如下 int x=0x44444444; int y; y=(x,16,1.1 基本数据类型、操作符、表达式,1.1.2 操作符、表达式 6条件表达式操作符 “? :” 表达式 例：计算y年的天数：若y是闰年，则366天，否则365天。用C表达如下： isLeap(y)?366:365,17,1.1 基本数据类型、操作符、表达式,1.1.2 操作符、表达式 7. 赋值操作符,18,1.1 基本数据类型、操作符、表达式,1.1.2 操作符、表达式 7. 赋值操作符 应用形式为： 左值 赋值操作符 表达式 例： x%=7 意义是计算 “x%7” 的结果，送给 x 空间，其值是最后 x 的值。 注意：无分号。有分号时是语句。 “x=y=6” 表达正确吗？,19,1.1 基本数据类型、操作符、表达式,1.1.2 操作符、表达式 8逗号表达式 逗号表达式的形式如下： 表达式, 表达式,表达式 例： char c=100; printf(“%i“,(c+1,c+2,c+3);,20,1.2 语句,赋值语句 文法 赋值表达式; x+; +x; x-; -x;,21,1.2 语句,赋值语句 自加（减）赋值 x+; +x; x-; -x;,例： int x=5; int y; y=x+; printf(“nx=%d,y=%d“,x,y); x=5; y=+x; printf(“nx=%d,y=%d“,x,y);,22,1.2 语句,条件语句 文法 if ( E ) S 或 if ( E ) S1 else S2,23,1.2 语句,复合语句 文法 说明部分 语句部分 复合语句书写规范,24,1.2 语句,循环语句 while语句 for语句 do-while语句,25,1.2 语句,循环语句 while语句 while( E ) S,图1.4 while循环的流程图,26,1.2 语句,循环语句 while语句 int getSum(int m) int sum=0; int i=1; while(i=m) sum+=i+; return sum; ,27,1.2 语句,循环语句 for语句 for(S0; E; S1) S,图1.5 for循环语句的流程图,28,1.2 语句,循环语句 do-while语句 do S while( E );,图1.6 do-while循环语句的流程图,29,1.2 语句,break 语句 文法 break; 用于循环和switch语句中，表示中止语句执行。,30,1.2 语句,continue 语句 文法 continue; 用在循环语句中，表示跳至循环控制部分，继续循环。,31,1.2 语句,空语句 文法 ;,例： if(xy); x+; y-; 例： for(i=0;i10;i+); . ,32,1.2 语句,goto 语句 文法 goto 标号;,33,1.2 语句,switch 语句 文法 switch(表达式) case I1: S11 S12 S13 case l2: S21 S22 S23 default: S01 S02 S03 ,34,1.2 语句,switch 语句 int k=1; char c=A; do switch(c+) case A: k*=2; break; case B: k+=2;continue; case C: k%=3; default: k+; case D: k/=3; k+; while(cF); printf(“k=%d“,k);,35,1.2 语句,return 语句 文法 return ； return 表达式； 前者所在的函数返回类型应是void ;后者所在的函数的返回类型应是非void.,36,1.2 语句,return 语句 void f() . f1(); . void f1() . if(.) return; . ,37,1.2 语句,函数调用 文法 函数名( 实参表 );,38,综合训练,例1.13：“万年历”程序：给定年y，计算y年的日历，即按星期对齐的方式，将y年的日历打印出来。 问题分析： 本问题的求解步骤是 S1 计算y年第一天的星期； S2 计算y年m月第一天的星期； S3 打印y年的日历：对y年的每一月，执行打印操作。,39,综合训练,S1 计算y年第一天的星期； int getYearWeekDay(int y) int sum = 0; int i; if (y = 2000) for (i = 2000; i y; i+) sum += getYearDays(i); return (sum + 6) % 7; else for (i = y; i 2000; i+) sum += getYearDays(i); return ( -sum + 6) % 7; ,40,综合训练,S2 计算y年m月第一天的星期； int getMonthWeekDay(int y, int m) int sum = 0; int i; for (i = 1; i m; i+) sum += getMonthDays(y, i); return (getYearWeekDay(y) + sum ) % 7; ,41,综合训练,S3 打印y年的日历：对y年的每一月，执行打印操作。 void printYear(int y) int i; count=1; for(i=1;i=12;i+) printMonth(y,i); ,42,void printMonth(int y, int m) int i=0; int w; printf(“n* %d月 *n“,m); w = getMonthWeekDay(y, m); if(w=0) printf(“n%-7d“,count); count+; else printf(“ “); for (i = 0; i w; i+) printf(“ “); for (i = 1; i = getMonthDays(y, m); i+) printf( “%7i“, i); w+; w %= 7; if (w = 0 ,43,1.3 数组,一维数组 一维数组的声明形式是： 类型 数组变量数组长度; 如：int a 10 ;,a是缓冲区的开始地址，是常地址。,44,1.3 数组,一维数组 &a+1：表示下一个a10空间的地址； a+1：表示下一个整数空间的地址。,45,1.3 数组,一维数组 运算符 地址表达式 例：若有声明int x,a10，从文法上，下式都是正确的。 a-1 a100 (&a3)-2 (&x)0,46,1.3 数组,二维数组 二维数组的说明形式如下： 类型 数组变量名长度1长度2;,47,1.3 数组,二维数组 如： int aa23;,48,1.3 数组,二维数组,49,1.3 数组,多维数组 int aaa234;,50,1.4 指针,指针 指针的声明形式是： 类型 * 指针变量; 例如： int * p;,51,1.4 指针,指针 *p表示p所指空间的内容,52,1.4 指针,指针 例1.14： int x=0; int *p; p=,53,1.4 指针,指针 例： int a10; int *p; p=a;,54,1.4 指针,指针 “*” 和 “&”是运算符,55,1.4 指针,指针-注意类型 例1.16： int i; long l=0xf1f2f3f4; char c4; for(i=0;i4;i+) ci=*(char *) ,56,1.4 指针,指向指针的指针 例1.17： int * *pp; /pp是指向int *空间的指针 int * p; int x; pp=,57,1.4 指针,指向指针的指针,58,1.4 指针,例1.19：命令行参数的获取 int main(int argc,char *argv) int y,m; if(argc=1) printf(“nUsage:MyDate year month“); return 0; else if (argc=2) y=atoi(*(argv+1); if(argc=3) m=atoi(*(argv+2); printMonth(y,m); else printYear(y); return 1; ,59,1.4 指针,例1.19：命令行参数的获取,60,1.4 指针,字符串 C中的字符串实质上是这个缓冲区的首地址。 一个字符串，它是自标志的，字符串的结束是以0标志的。 常字符串，如 “hello”,61,1.4 指针,字符串操作-拷贝 char * strcpy(char * s1,char * s2) int i; for(i=0;*(s2+i)!=0;i+) *(s1+i)=*(s2+i); *(s1+i)=0; return s1; ,62,1.4 指针,字符串操作-连接 char * strcat(char * s1,char * s2) int i, j; for(j=0;*(s1+j)!= 0;j+); for(i=0;*(s2+i)!=0;i+) *(s1+j+i)=*(s2+i); *(s1+j+i)=0; return s1; ,63,1.4 指针,字符串操作-比较 int strcmp(char * s1,char * s2) int i; for(i=0;*(s1+i)!= 0 ,64,1.4 指针,字符串操作-计算长度 int strlen(char * s1) int i; for(i=0;*(s1+i)!= 0 ;i+); return i; ,65,1.4 指针,考虑下面代码的执行结果： char str25; strcpy(str0,“hello“); strcpy(str1,“hi“);,66,1.4 指针,指针数组 int * pInt8; char * str= “请输入整数”， “x=%d”, “除法错误” ;,67,1.4 指针,数组指针 int * pList4; int (* pItem)4;,68,1.4 指针,数组指针 int getTotal(int (* item)4) int i; int sum=0; for(i=0;i4;i+) sum+=*(*item+i); return sum; ,69,1.4 指针,数组指针 int main() int i; int items44=1,3,4,5,2,4,5,3,5,6,3,2,6,4,3,1; for(i=0;i4;i+) printf(“n%d:%d“,i+1,getTotal(items+i); ,70,1.5 结构和联合体,结构 结构类型定义的一般形式是： struct 结构体名 类型 域变量; 类型 域变量; ;,71,1.5 结构和联合体,结构 例1.21： struct stu char id8; char name10; int sex; float scores7; ;,72,1.5 结构和联合体,结构,73,1.5 结构和联合体,结构 struct stu * pStu; struct stu li; pStu=,74,1.5 结构和联合体,结构,75,1.5 结构和联合体,联合体 union 联合体名 类型 域变量; 类型 域变量; ;,76,1.5 结构和联合体,联合体 union tag struct int w,h; rect; int r; int d; ; union tag shape;,77,1.5 结构和联合体,联合体 union iaddr unsigned long ip; unsigned char byte4; ; sizeof(union iaddr)=4。,78,1.5 结构和联合体,位域 struct unsigned int f1:3; unsigned int f2:3; unsigned int f3:3; q;,79,1.5 结构和联合体,链表结点的定义 typedef struct stag int key; struct stag *next; SNODE; /单向链表结点的定义 typedef struct dtag int key; struct dtag *previous,*next; DNODE; /双向链表结点的定义,80,1.5 结构和联合体,链表结点的操作 void insertAtHead(SNODE * head,SNODE *); SNODE * createSNode(int key); void deleteAtTail(SNODE * head); void traversal(SNODE * head); ,81,1.5 结构和联合体,二叉树结点的定义 typedef struct t2Tag int key; struct t2Tag * left,*right; T2NODE;,82,1.5 结构和联合体,树结点的定义 typedef struct tTag int key; struct tTag * parent; struct tTag *elderBrother,*brother; struct tTag * children; TNODE;,83,1.6 函数,函数的定义格式是： 返回类型 函数名(参数表) 函数体 函数的调用格式是： 函数名（实际参数）; 函数原型声明的格式为： 返回类型 函数名(参数表);,84,1.6 函数,参数传递 函数定义时的参数称为形式参数，函数调用时的参数称为实际参数。 当函数调用时，首先在栈区内分配形式参数的内存空间，然后计算实际参数的值，并将实际参数的值传给形式参数的空间。,85,1.6 函数,参数传递 void f(int); void f1(int *); int main() int x=100; f(x); printf(“x=%d“,x); f1( ,void f(int x) int y=100; x+=100; ,void f1(int * x) int y=100; *x+=y; ,86,1.6 函数,参数传递 void f2(int); int main() int a=1,2,3; f2(a); printf(“%d-%d-%d“,a0,a1,a2); ,void f2(int a3) a0=4; a1=3; a2=2; ,在参数传递时，它将数组的地址传给形参，在函数执行时，改变的是同一数组的元素值。,87,1.6 函数,函数指针定义形式 返回类型 (* 函数指针变量)(参数表); 函数指针是一个指针变量，与一般指针不同的是，它是指向代码区的，而不是指向数据区的指针。 例：void (*pf)();,88,1.6 函数,函数指针 void open(); /* open的原型声明 */ void print(); /* print的原型声明 */ void exitIt(); /* exitIt的原型声明 */ void (*pfs)()=open,print,exitIt; /* 函数指针数组 */ int main() int i; void (*pf)(); pf=open; (*pf)(); /* 调用open */ for(i=0;i3;i+) (*pfsi)(); /* 依次调用函数open、print、exitIt */ ,89,1.6 函数,其中 void open() printf(“open“); void print() printf(“print“); void exitIt() printf(“exit“); ,90,1.6 函数,例：以下定义的意义 void (*getInterrupt(int no)(); void setInterrupt(int no, void (*pf)(); LRESULT (* lpfnWndProc) (HWND,UINT,WPARM,LPARAM);,91,1.7 存储类型,C中变量的完整说明形式是： 存储类型 数据类型 变量; C中存储类型 register auto(默认存储类型) static extern,92,1.7 存储类型,static存储类型 在函数内定义时，static作用范围在函数内，但在运行期间一直存在。 在函数外定义时，从定义点开始有效，但只限于本文件使用。在程序运行期间一直存在。,93,1.7 存储类型,static存储类型-下面代码打印出什么，为什么？ int main() void print(); print(); print(); print(); void print() static int i=0; printf(“%d-“,i+); ,94,1.7 存储类型,extern存储类型 在函数内时，引用函数外定义的量。 在函数外时，引用其它文件定义的量。 总之，extern 变量，不分配内存。,95,1.8 预编译,宏定义可用于定义值或定义一些功能，其形式是： #define 预编译 量 #define预编译量 值 #define预编译量(参数, 参数) 功能定义,96,1.8 预编译,宏定义例子 #define PRINT #define PI 3.14159265 #define子 LEN 200 #define HIWORD(l) *(short*)&l+1) #define LOWORD(l) *(short*)&l),97,1.8 预编译,宏定义 例如求一个量平方的宏定义的各种写法： #define SQUARE(x) x*x #define SQUARE(x) (x*x) #define SQUARE(x) (x)*(x) #define SQUARE(x) (x)*(x) 正确的是哪一种？对不正确的，请举反例说明。,98,1.8 预编译,宏引用形如： #include “文件名“ 例： #include “stdio.h“ #include “malloc.h“ 在引用位置引入指定文件（任意文件）的内容。,99,1.8 预编译,条件编译 #define PRINT int main() #ifdef PRINT /*若定义了PRINT，则下面代码参与编译*/ printf(“nPRINT is defined.“); #endif #ifndef PRINT /*若未定义PRINT，则下面代码参与编译*/ printf(“nPRINT is not defined.“); #endif #ifdef PRINT /*若定义了PRINT，则下面代码参与编译*/ printf(“nPRINT is defined.“); #else /*否则，即若未定义PRINT，则下面代码参与编译*/ printf(“nPRINT is not defined.“); #endif printf(“nend“); ,100,1.9 有缓冲方式的文件操作及控制台操作,控制台操作 int printf(const char *, .); int scanf(const char *, .);,101,1.9 有缓冲方式的文件操作及控制台操作,控制台操作 printf(“n%d,%ld,%10d,%10ld“,6,6L,6,6L); printf(“n%x,%5lx“,64,64); printf(“n%o,%5o“,64,64); printf(“n%u,%5u“,65,-1); printf(“n%c,%5c“,65,A); printf(“n%s,%10s“,“hello“,“hello“); printf(“n%f,%10.3f“,6.0,6.00); printf(“n%e,%10.3e“,6.0,6.00); printf(“n%g,%10.3g“,6.0,6.00);,102,1.9 有缓冲方式的文件操作及控制台操作,控制台操作 int x; long l; scanf(“%d,%ld“,103,1.9 有缓冲方式的文件操作及控制台操作,文件操作读取操作时有三个步骤： 打开文件， 读写操作， 关闭文件，以释放文件所占的各种缓冲区。,104,1.9 有缓冲方式的文件操作及控制台操作,打开文件 FILE * fopen(const char *, const char *); 打开文件“c:tttt.txt”。 char * path=“c:tttt.txt“; FILE * stream; if(NULL=(stream=fopen(path,“rb“) printf(“File %s doesnt exist.“,path); exit(0); ,105,1.9 有缓冲方式的文件操作及控制台操作,打开文件方式 r：打开文件用于输入文件必须存在，否则无法打开 w：打开文件用于输出文件若存在，则删除重新建立 a：打开文件用于在文件尾追加数据。文件必须存在，否则无法打开 r+：打开文件用于读、写文件必须存在，否则无法打开,106,1.9 有缓冲方式的文件操作及控制台操作,读写操作-文件状态 函数feof可判定指定的输入流是否结束。其原型定义： int feof(FILE *); 若处于文件尾（end of file），则返回真（1），否则返回假（0）。 函数ferror可判定指定的流是否出错，若有错误，则返回1，否则返回0。其原型定义如下： int ferror(FILE *);,107,1.9 有缓冲方式的文件操作及控制台操作,读写操作-读写字符 函数getc和fgetc都是按字符读入内容，其原型定义如下： int getc(FILE *); int fgetc(FILE *); 例： while(!feof(stream) int ch=getc(stream); /这里应是处理代码 ,108,1.9 有缓冲方式的文件操作及控制台操作,读写操作-格式读写 按指定的格式读、写文件流的操作函数是以下两个函数： int fprintf(FILE *, const char *, .); int fscanf(FILE *, const char *, .);,109,1.9 有缓冲方式的文件操作及控制台操作,读写操作-块读写 函数fwrite将指定缓冲区中的内容写入文件中，函数fread将文件中的内容读到指定的缓冲区中。它们的原型声明如下： size_t fwrite(const void *, size_t, size_t, FILE *); size_t fread(void *, size_t, size_t, FILE *);,110,1.9 有缓冲方式的文件操作及控制台操作,读写操作-文件指针操作 函数fseek改变文件指针的位置。其原型声明为： int fseek(FILE *, long, int); 其中第三个参数可选三个值：0、1、2。0表示以文件头为参照，表示以当前位置为参照，2表示以文件尾为参照。第二个参数表示距参照点的距离，类型为长整数。 函数ftell可得到文件指针的位置。 long ftell(FILE *); 函数rewind将文件指针返回文件开始位置。 void rewind(FILE *);,111,1.9 有缓冲方式的文件操作及控制台操作,读写操作-文件指针操作 例：利用文件指针计算文件长度的函数： long getFileLen(FILE * stream) long old,len; old=ftell(stream); /保留原文件操作地址 fseek(stream,0,2); /将文件指针移至文件尾 len=ftell(stream); /保留文件位置 fseek(stream,old,0); /恢复原文件位置 return len; ,112,1.9 有缓冲方式的文件操作及控制台操作,关闭文件的函数是： void fclose(FILE * f); 关闭文件后，所以该文件操作的缓冲区全部释放。,113,1.10 其它库函数操作,string.h char * strcpy(char *, const char *);字符串拷贝 char * strcat(char *, const char *);字符串连接 int strcmp(const char *, const char *);字符串比较 size_t strlen(const char *);计算字符串长度,114,1.10 其它库函数操作,ctype.h int isalpha(int); 给定的符号是字母吗？ Int isupper(int); 给定的符号是大写吗？ int islower(int); 给定的符号是小写吗？ int isdigit(int); 给定的符号是数字符号吗？ int isspace(int); 给定的符号是空格吗？ int isalnum(int); 给定的符号是数字符号或字母吗？ int toupper(int); 给定的符号字转变为大写符号 int tolower(int); 给定的符号转变为小写符号 int iscntrl(int); 给定的符号是控制符吗？,115,1.10 其它库函数操作,stdlib.h double atof(const char *); 字符串转变为双精度的数 int atoi(const char *); 字符串转变为整数 long atol(const char *); 字符串转变为长整数 char * itoa(int, char *, int);将整数以指定的进制转变为字符串 void exit(int); 退出应用程序 void * malloc(size_t); 分配指定大小的内存空间 void free(void *); 释放内存空间 int rand(void); 求随机数 int system(const char *); 运行系统命令 void * malloc(size_t); 动态申请内存空间 void free(void *); 释放已申请的内存,116,1.10 其它库函数操作,math.h float floorf( float ); 取地板值 float ceilf( float ); 取天棚值 math.hfloat fabsf( float );取绝对值,117,第2章 递归,118,概述,递归方法是程序设计的一种主要手段。 事实上，计算机可以识别的语言是递归可枚举语言，可计算的函数是部分递归函数。 可见，可计算的问题，如果不是有限情形，都可以写成递归处理程序。,119,例2.1：用递归方法求 。 提示： 设getSum(m)= ，则不难看出有如下递归定义： 这里递归变量是m，起始值是1（当m=1时）。 递归函数： int getSum(int m) if(m=1) return 1; return m+getSum(m-1);,getSum(m)=,m+getSum(m-1) 否则,1 当m=1时,120,例2.2：编程，输入一个自然数，试将其表示成质因数乘积的形式。例如： 输入：140时，则输出：140=2*2*5*7 要求编写递归程序。 提示： 对要分解的数字m或当前正在尝试的因子n进行递归调用，当m为1时，结束递归调用。 递归函数：void priNum(int m,int n); 参数 m 为待分解的数字， 参数 n 为待尝试的因子。 m%n不为0时，n不是m的一个因子，因此需要递归调用函数，继续尝试用n+1去分解m m%n为0时，n是m的一个因子，则需要递归调用函数，继续用n去分解m/n,121,例2.3：试编写一个递归函数，完成回文的判定。回文是如下形式的对称字符串： ”a”，”abccba”，”abcdcba”。 提示： 对字符串的长度进行递归处理，当长度为0或1时，结束递归调用。 例如，判定字符串”abcdcba”是否是回文。 当发现串的首字符和尾字符同是a时，问题就变成求字符串”bcdcb”是否是回文， 继续求字符串”cdc”是否是回文， ，以此类推。 当字符串的长度l=1时，递归调用结束。,122,例2.4：读下面汉诺塔问题的解决程序，写出输出结果。 汉诺塔问题是在三个座间移动大小不同的盘子，要求： （1）每次只能移动一个盘子； （2）只可以利用这三个座放盘子； （3）座上放盘子时只能是大盘在下，小盘在上。 提示： 这是一个经典的递归程序。可以用栈示意图模拟函数调用的过程。 递归函数： void hanoi(int n,char fr,char to,char by)； n 层数；fr 原点；by 中间点；to 目标点,123,例如：hanoi(4,A,C,B)-把4个盘子从A借助C移到B,n,fr,to,by,列表示某一时刻栈的内容，上面表示栈顶。,粗线用于分隔调用函数（粗线下面）和被调用函数（粗线上面）的参数值或局部变量值。,空格中的值是最邻近的、非空的左面格中的值。,124,例2.5：读程序，该程序输入N个学生的学号和成绩，输出高于平均成绩的学生的学号和成绩，其中学号和成绩均为整数。 提示： 用递归栈来求平均值。输入的学号不为0时，将计算当前已输入学生的总分和人数，继续递归调用。 这里并没有使用数组等线性数据结构。只有学号输入0时，才能得到总分和人数，也才能计算出平均成绩ave。之后将ave的值返回上一函数，该函数再根据其stu.score和ave的比较结果看是否高于平均成绩，并决定是否输出其学号和成绩。 递归函数： int student(int total, int n) ； total：总分，n：学生个数，返回值：平均分,125,例如：s.num 1 2 3 4 5 s.score 45 67 89 78 76,126,例2.6： 试编写程序，输入一个整数，将其各位上的数按逆序存放在一个数组中。 提示： 设转换函数是reverse(int *a,int n)，其中第一个参数是存放位的数组，第二个参数是待处理的数。要将n的各位放在a中，就要将n/10（当n10时）放在a+1中。如：将n=12345（10），存放在数组a中，就要将1234放在a+1中，为此，就要将123放在a+2中，以此类推。当n10时，将n放于a中，递归调用结束。 提示： 迭代公式为：x1=(x0+a/x0)/2,例2.7：用递归算法实现牛顿迭代法，求平方根。,127,例2.9：已知递归函数（其中DIV为整除）： F(n)= 1 n=0 n*F(n DIV 2) n0 试写出求F(n)的非递归算法。 提示： 用栈实现。在栈的元素中记录三个值： 当前要求的值； n； 递归调用函数F(n DIV 2)的返回值，,因此有: statop0=statop1*statop2; statop2=statop+10;,128,例2.10：Ackerman函数定义如下 ： n+1 m=0 akm(m,n) = akm(m-1,1) m0,n=0 akm(m-1,akm(m,n-1) m0,n0 试写出求该函数的非递归算法。 提示： Ackerman函数是一个递归定义的而不是原始递归的函数。这里我们用栈结构实现其非递归的程序。我们定义栈元素有4项内容：m、m1、n和r ； 当r为0时，表示调用akm(m,n)，处理时直接弹栈；当r为1时，表示调用akm(m-1,akm(m,n-1)，此时不弹栈而计算akm(m1,n)，即计算akm(m,n-1)。,129,例2.12：输入M个不同的字符，从中选出N个字符，输出所有可能的选择方案。说明： （1）M、N均由键盘输入； （2）假定输入的M和N均合法，输入的M个字符均不同。 提示：如有M字母“abcde”，从中选3个不同的字母，我们可以把这样的问题递归描述为：,130,例2.13：从文件t.in中读出整数，将其中不同整数及其出现次数，按整数由大到小的次序输出到文件t.out中。要求：用一个有序二叉树存储数据。 提示： 首先我们要定义树形的描述，对于树的描述只需定义出树的结点定义及其相关的操作，在这里就是树的插入操作和遍历操作。然后是文件操作。 递归函数：按从小到大的顺序（中序）输出 void T_tree(FILE *fp, struct node *t) if (t=NULL) return; T_tree(fp,t-left); fprintf(fp,“n%d %d,“,t-val,t-count); T_tree(fp,t-right); ,131,例2.14：试编写一个递归函数，函数的输入为一个带括号的包含加、减、乘、除四则运算表达式的字符串，例如“（a+b）*(c+d)”，该函数根据运算符优先级来构造一棵二叉树，树的根节点为优先级最低的运算符。该函数最终返回二叉树的根节点，并用后序遍历方式遍历生成的二叉树。假设表达式中的操作数都是长度是1的串。 提示： 首先要描述二叉树，包括定义树的结点，其支持的操作有创建结点、后序遍历。然后分析四则表达式，生成二叉树 。 递归函数：递归函数的核心算法可以描述如下： NODE *creatTree(char *bstr) /*创建表达式对应的二叉树*/ 把bstr分解成bstr1 bstr2; /*是bstr中最后运算的操作符*/ if (head=head=createNode()!=NULL) head-left=creatTree(bstr1); head-right=creatTree(bstr2); 其中，分解bstr就是找出其中最后运算的操作符。,132,例2.15：试利用递归方法判别用链表表示的两个非递归列表是否相等。程序中的非递归列表定义如下： （1）无元素的空列表是非递归列表； （2）由元素序列组成的一个列表，其中的元素可以是一个字符，或者是满足本定义的一个列表。例如： 提示： 首先要定义结构描述列表的元素，然后根据定义编写判定相等的函数。 表结点定义 ：typedef struct node int tag; union u char data; struct node *link; un ; struct node *next; NODE;,133,第3章 排序部分,134,例3.1 冒泡排序,冒泡排序是交换排序; 方法：对于i=0，1，2，n-1，在第i个与第n个元素之间，包括二者，选极大（小）值放于第i个位置； 选取方式是从第n个元素开始，每次都与前一个关键字比较，将大（小）者“浮”上去，直至第i+1元素。,135,例3.1 冒泡排序,136,例3.1 冒泡排序,void bSort(int a,int order,int len) int i,j; for(i=0;ii;j-) if(ajaj-1) int t=aj;aj=aj-1;aj-1=t; t=orderj; orderj=orderj-1;orderj-1=t; ,137,例3.1 冒泡排序,void bSort(int a,int order,int len) int i,j; for(i=0;ii;j-) if(aorderjaorderj-1) int t=orderj; orderj=orderj-1; orderj-1=t; ,138,例3.2 希尔排序,希尔排序是一种插入排序,即将一个数记录按规定的关键字序插入到一已排序的数列中。 希尔排序用步长控制参与排序的元素;,139,例3.2 希尔排序,如步长k，则考虑的数列为： aj aj+k aj+2k aj+3k aj+i*k 当aj aj+k aj+2k aj+3k aj+i*k已排序，则将aj+(i+1)*k插入到前面的数列中。 当k=1时，对a2，a3，依次执行插入后，就完成了排序过程。,140,例3.2 希尔排序,k=4 （47） 56 36 78 23 58 49 60 38 k=4 47 （56）36 78 23 58 49 60 38 k=4 47 58 （36）78 23 56 49 60 38 k=4 47 58 49 （78）23 56 36 60 38 k=4 （47）58 49 78 （23）56 36 60 38,141,例3.2 希尔排序,k=1时 （49） 78 47 60 38 58 36 56 23 （78）（49） 47 60 38 58 36 56 23 （78）（49）（47） 60 38 58 36 56 23 （78）（60）（49）（47） 38 58 36 56 23 （78）（60）（49）（47）（38）58 36 56 23 （78）（60）（58）（49）（47）（38） 36 56 23 （78）（60）（58）（49）（47）（38）（36） 56 23 （78）（60）（58）（56）（49）（47）（38）（36） 23 （78）（60）（58）（56）（49）（47）（38）（36）（23）,142,例3.2 希尔排序,void shell(int a,int n) int k,j, i, t; for(k=n/2;k0;k=k/3+1) /*k是步长*/ for(j=k;j=0 ,143,例3.3 快速排序,快速排序是一种交换排序; 基本思想是：以某一个关键字将整个数列分成二部分：大于该关键字的部分和小于该关键字的部分。然后对每一部分再执行该排序算法。,144,例3.3 快速排序,（47） 56 36 78 23 58 49 60 （47） 56 36 78 23 58 49 （60） 60 （56） 36 78 23 58 49 （60） 56 （36） 78 23 58 49 （60） 60 56 （36） 78 23 58 （49） 36 56 49 （78） 23 58 （49） 36 60 56 49 78 （23） 58 （49） 36 56 49 78 （23）（58） 23 36 60 56 49 78 58 （58） 23 36 60 56 49 78 58 47 23 36,145,例3.3 快速排序,void qsort(int a,int begin,int end) /* 分为二个部分*/ int i=begin, j=end,key=ai, left=1; if(begin=end) return; for(;ij;) if(left=1) if(keyaj) ai=aj; i+; left=!left; else j-; else if(aikey) aj=ai; j-; left=!left; else i+; ,146,例3.3 快速排序,/* 对每个部分,递归再排 */ ai=key; qsort(a,begin,i-1); qsort(a,i+1,end); ,147,例3.4 归并排