计算机软件基础：10第三章C语言及编程规范

PAGE1《计算机软件基础》多媒体教程第十讲第三章 C语言及编程规范3.1基本问题3.1.1基本数据类型与存储空间变量定义与存储空间定义一个变量，表示确定了该变量将占有内存单元的空间大小(以字节byte为单位)。 例如： inta; longb; 表示定义int变量a和long变量b，将各自占有规定的内存单元。同一种数据类型，在不同的计算机中所占字节数可能不同。基本数据类型不同计算机所占字节数本课程约定字节数字符型char1or21整数型int1,2or42short1or22long2,4or84浮点型float2or44double4or88int称为缺省整型，依不同的计算机而定，它可能等同于short也可能等同于long，因此重要的变量要避免定义为int类型。变量引用及其数值 引用变量是指存取内存单元中的值(数据)。在内存存储的总是二进制数据，也是引用变量进行计算时用的格式。但是给定不同的输出格式输出变量时，需要将内部二进制格式按照不同的数据类型转换为输出格式。(可参阅课本第314页的附录A：ASCII字符集)【例3-1.1】定义 charc; 内存数据为(01000001)二=(101)八=(65)十 则执行打印语句为 printf(“c(dec)=%d,c(char)=%c\n”,c,c); 运行结果为 c(dec)=65,c(char)=A带符号的数据类型 整型和字符型存在有符号和无符号的差别，应注意正确选用。【例3-1.2】测试有符号和无符号的差别。 chara; 有符号字符型变量，省略signed unsignedcharb; 无符号字符型变量 a=b=0xFF; 存储单元内数值均为(11111111) printf(“a=%d,\tb=%d\n”,a,b); 得 a=-1, b=255 由于标准ASCII码只用7位二进制数，0xFF用到第8位，成为扩展的ASCII码(非标准码)，在不同的计算机中用“%c”打印的字符不一定相同。内存单元与存储空间 由于在不同的计算机中一种数据类型的存储空间所占字节数可能不同，所以通常在开始使用一台计算机时，可以使用运算符sizeof来测试内存单元所占的字节数。 例如，定义int变量a： inta=-1; 但是其存储空间可能占1个、2个或者4个字节。测试方法是使用打印语句如下： printf(“sizeof(int)=%d\n”,sizeof(int)); 或者 printf(“sizeof(int)=%d\n”,sizeof(a)); sizeof既可测试数据类型的字节数，也可测试变量的字节数。3.1.2类型转换规则隐式(自动)转换规则(从低向高自动转换) char(低)->int,short->long->float->double(高)【例3-1.3】隐式转换示例 inti1,i2; floatf; f=i1+i2; (1) i2=f*i1; (2) (1)计算“i1+i2”时，不转换，它们的和转换为float后赋给f。 (2)先将i1转换为float，计算“f*i1”，获得float型，然后再转换为int后赋给i2。显式(强制)转换 采用显式转换，可以不需要去记住隐式转换规则，以免出错。 例如，定义 inti=1; 则 i/3*3为0，而(float)i/3*3为0.99...9 又如，定义 inti1=3,i2; floata=3.5; 则 i2=a*(float)i1; 遵循显式转换：i2为10 i2=(int)a*i1; 遵循显式转换：i2为9 i2=a*i1; 遵循隐式转换：i2为10 应该尽量采用显式转换，而不要采用隐式转换规则。3.2指针3.2.1指针的定义指针定义的格式 类型*变量； 例如： int*pa,*pb; float*pc; 表示定义pa和pb为整数型指针，pc为浮点型指针。 如果将以上定义改为： int*pa,pb; 则是错误的定义方式。由于定义指针时的星号不能共享，因此结果只是将pa定义为指针，而pb定义为变量，并没有定义为指针。指针的存储单元 指针的类型实际是指它目标的数据类型，而不是指针的数据类型。无论用什么数据类型定义指针，指针的存储单元长度在同一台计算机中是相同的，指针所用存储单元的类型都是unsignedlong(4个字节)。因此所谓的指针类型实际上是指其目标的数据类型，根据其类型可以是不同的字长。 例如： char*pa; 定义字符型(char)指针pa short*pb; 定义浮点型(float)指针pb long**pc; 定义长整型指针(long*)的指针pc 其中，pa，pb和pc的存储单元长度与目标无关，所占的存储单元类型总是unsignedlong，占4个字节。3.2.2指针的含义 指针是一个变量，所以指针又称指针变量。指针的用途 指针的存储单元是用来存放地址的，该地址所指向的存储单元称为指针的目标。例如： int*pa,a; 定义整数型指针pa和整数型变量a pa=&a; 令指针pa指向变量a(a成为pa的目标)指针的等价含义 指针与目标的关系，可用以下任何一种表述，它们是互相等价的(包括同义命题)： 指针指向目标。 指针的目标是它指向的变量。 指针存放其目标的地址。(同义：指针的值为其目标的地址) 通过指针可访问其目标。(同义：通过指针可存取其目标的值) 例如： int*pa; 定义pa为整数型指针(4字节) inta; 定义a为整数型变量(2字节) 则指针与目标的等价表述为： pa指向a。 pa的目标是a。 pa存放a的地址。 通过pa可存取a的值。3.2.3指向目标指针指向目标的含义 定义指针时，只是定义了指针的存储空间，但没有给指针赋值。 定义指针不等于该指针已指向某个目标。 只有指针的值为有效地址时，才能说指针指向目标。空指针 指针的值如果等于零，称为空指针，也即该指针无目标。 使指针的值等于零，称为清零指针或指针清零。 C语言中的零地址用宏NULL表示。 例如： short*pa; 定义pa为整数型指针 pa=NULL; 令指针pa指向空，或称pa为空指针指针的赋值 给指针赋以有效的地址(例如某个已知变量的地址)，才能说指针指向目标。【例3-2.1】指针赋值示例。 shorta,b[3],*pa,*pb; 定义变量和指针(定义空间) pa=&a; 令a成为pa的目标(假定a地址为FF50) a=1111; 令a(pa的目标)为1111 pb=&b[1]; 令pb指向b[1](假定b[1]的地址为E0A1) *pb=4567; 使b[1]的值为4567(等价为b[1]=4567)内存分配内存分配与动态存储空间 程序中定义的变量，无论是动态变量还是静态变量，其存储单元都有相应的地址(位于用户数据区)。除此之外，在计算机系统中还提供了可以在程序运行过程中动态申请的存储空间。通常可以用内存分配类函数来申请动态空间。内存分配函数malloc 调用形式：malloc(size) malloc的功能是向系统申请size个字节数的存储单元。如果系统中存在着这样大小的单元，将返回一个非零值，表示该单元已为用户进程所有。malloc()的返回类型为char*，而实际申请所需的目标类型可由用户任意选定，所以应该将其类型强制转换。通常用指针指向这样的动态内存空间(使指针指向目标)。 例如，定义short*pa;int*pb; 执行动态内存分配： pa=(short*)malloc(sizeof(short)); 假设返回地址为0D40 pb=(int*)malloc(3*sizeof(int)); 假设返回地址为0D50 每次调用malloc函数后应该测试其返回值。例如： if((pa=(int*)malloc(sizeof(int)))==NULL) exit(-1); 如果返回值为NULL，表示分配失败(系统内存已耗尽)，这时若再要访问其目标，比如要求执行语句：*pa=4; 则操作系统的内存保护功能将发挥作用，令进程异常中止，并给出以下常见的出错信息： “buserror”,“coredump”,“fragmentationviolation”,等等。内存释放函数free 调用形式：free(ptr) free的功能是用于释放由ptr指向的(先前分配的)单元，归还给操作系统。 虽然用free释放动态单元后，指针ptr的目标已消失，但ptr的值不变，这时若还要访问其目标，则也将导致进程出错(访问非法地址)。 动态申请的单元必须一次释放。比如用pb申请了3个int型的动态空间，首地址为0D50，则释放时应该为“free(pb);”，指针pb指向的单元地址也必须为0D50，形如“free(pb[1]);”是错误的(因为pb[1]的值为0D52)。3.2.4访问目标指针运算符 指针运算符包括取址符&和取值符*。 取址符&的作用是获得变量的地址，如&x表示变量x的地址。 取值符*的作用是获得目标的数值，如*x表示指针x的目标的值。【例3-2.2】指针运算符示例一 inta,b,*pa; a=5; pa=&a; pa通过取址符&获得a的地址 printf(”%d,%d\n”,a,*pa); *pa等价于a b=*pa; 等价于b=a; printf(”%d,%d,%d\n”,a,b,*pa); 运行结果为： 5,5 5,5,5由指针指向连续的存储单元【例3-2.3】指针运算符示例二 int*pc,i,n=4; pc=(int*)malloc(sizeof(int)*n); for(i=0;i<n;i++) *(pc+i)=i+1; printf(“%d,%d\n”,pc[0],pc[3]); 其中，*(pc+i)等价于pc[i]，通常我们愿意使用pc[i]的形式，即数组元素的形式。由指针指向的这种地址连续的存储单元并不是C语言定义的数组，但是具有数组的特性。由于它们是通过动态分配获得的，因此可将其称为动态数组。 运行结果为： 1,43.2.5字符串(数组和指针的应用)字符串的数据类型 C语言没有为字符串提供专用的数据类型，而是利用数组或动态数组中连续的存储单元存储字符串。用字符串常量存储字符串 例如，“Doit!”是一个字符串常量。 字符串的结束符‘\0’也占一个存储单元。用字符数组存储字符串 例如： chars0[7]={‘D’,‘o’,‘□’,‘i’,‘t’,‘!’,‘\0’};用指针的目标存储字符串，可简称为用指针存储字符串。 char*s,*t,*u; s=(char*)malloc(sizeof(char)*7); u=(char*)malloc(sizeof(char)*7); strcpy(s,”Doit!”); t=s; strcpy(u,s); 其中，s将目标的地址复制给t，将目标的值复制给u，两者是不同的。字符串的赋值字符串复制 利用strcpy和strcat等函数将字符串复制给数组或者动态数组。 函数strcpy(dst,src)的功能是将src复制到dst。 函数strcat(dst,src)的功能是将src附加到dst的后面。 例如，定义chars1[7];可有 strcpy(s1,”Doi”); strcat(s1,”t!”);按数组元素逐个赋值 例如，定义chars2[7];可有 s2[0]=’D’; s2[1]=’o’; s2[6]=‘\0’;初始化赋值 例如， chars3[7]=“Doit!”;字符串使用的常见问题示例【例3-2.4】字符串使用示例一 #include<stdio.h> #include<stdlib.h> #include<string.h> main() { char*t,*u,*v; t=(char*)malloc(sizeof(char)*strlen("hello")); u=(char*)malloc(sizeof(char)*(strlen("hello")+1)); v=(char*)malloc(sizeof(char)*strlen("he")); strcpy(t,"helloyou"); strcpy(u,"helloyou"); strcpy(v,"helloyou"); printf("t=[%X]\tu=[%X]\tv=[%X]\n",t,u,v); printf("t=[%s]\tu=[%s]\tv=[%s]\n",t,u,v); } 在VC++的环境下，运行结果为： t=[431C50] u=[431C10] v=[431BE0] t=[helloyou] u=[helloyou] v=[helloyou] 请分析输出结果，并且提出应该如何编程的方案。【例3-2.5】字符串使用示例二 #include<stdio.h> #include<stdlib.h> #include<string.h> main() { chars0[6],s1[4],s2[2]; strcpy(s0,"hello"); printf("len=%d\ts0=[%s]\n",strlen("hello"),s0); strcpy(s2,"helloyou"); printf("s0=[%X],s1=[%X],s2=[%X]\n",s0,s1,s2); printf("s0=[%s],s1=[%s],s2=[%s]\n",s0,s1,s2); } 在VC++的环境下，运行结果为： len=5 s0=[hello] s0=[12FF78],s1=[12FF74],s2=[12FF70] s0=[u],s1=[oyou],s2=[helloyou] 请分析输出结果，并且提出应该如何编程的方案。3.2.6指针和数组数组和指针的比较数组指针inta[3];int*pa;a为常量pa为变量a的值为数组首址pa值为目标首址a=pa; /*非法赋值*/pa=a; /*合法赋值*/ 设数组a的首址为1000，令 pa=a; a[1]=15; 则 a+1,&a[1],pa+1,&pa[1] 均为1002 (a+1),a[1],*(pa+1),pa[1] 均为15 数值： a[1]<=>*(a+1) pa[1]<=>*(pa+1) 地址： &a[1]<=>a+1 &pa[1]<=>pa+1数组和指针的应用【例3-2.6】库函数strlen()的实现函数描述 函数名：strlen(s) 函数功能：返回字符串s中字符的个数，不包括‘\0’。 形参说明： (1) 数组形式 chars[]; 或者 (2) 指针形式 char*s;用数组形式实现形参的函数strlen()，程序为： intstrlen(s) chars[]; { inti=0; while(s[i]!=’\0’) i++; return(i); }用指针形式实现形参的函数strlen()，程序为： intstrlen(s) char*s; { inti; for(i=0;*s!=’\0’;i++) s++; return(i); }【例3-2.7】库函数strcpy()的实现函数描述 函数名：char*strcpy(dst,src) 函数功能：将字符串从src复制到dst，包括‘\0’，返回dst的地址，即返回字符串的首地址。 形参说明： (1) 数组形式 charsrc[],dst[]; 或者(2) 指针形式 char*src,*dst; 将src中的字符串复制到dst中，包括‘\0’，返回dst的地址。 将src目标中的字符串复制到dst目标中，包括‘\0’，返回dst的值。用数组形式实现形参的函数strcpy()用指针形式实现形参的函数strcpy()3.2.7多级指针多级指针和数组的定义 假设有以下定义： shorta[3], b[3][2],*c,**d,*e[3]; 表示定义了(一维)数组a，二维数组b，(一级)指针c，二级指针d，以及指针数组e。多级指针和数组的存储单元 假设通过以下语句动态申请内存(令R=3;C=2;)： c=(short*)malloc(size(short)*R); d=(short**)malloc(size(short*)*R); for(i=0;i<R;i++) { d[i]=(short*)malloc(size(short)*C); e[i]=(short*)malloc(size(short)*C); } 问题：各种数组的存储单元有什么相同之处和不同之处?数组a和动态数组c的比较数组a动态数组(指针)c表示数组当然可以性质a是常量c是变量存储单元sizeof(short)x3=6字节sizeof(short)x3+sizeof(short*)=6+4=10字节获得空间根据定义动态分配/指向目标可扩展性没有任意二维数组、二级指针和指针数组的比较 由二级指针d和指针数组e分别生成了几个数组? 动态数组中各个元素之间的地址有什么关系? 各个数组在使用上有什么异同?二维数组、二级指针和指针数组的比较二维数组b二级指针d指针数组e表示数组当然。1个二维数组可以。1个动态指针数组，3个动态数组可以。1个指针数组，3个动态数组性质b是常量d是变量e是变量存储单元sizeof(short)x3x2=12字节sizeof(short)x3x2+sizeof(short*)x3+sizeof(short**)=12+12+4=28字节sizeof(short)x3x2+sizeof(short*)x3=12+12=24字节获得空间根据定义动态分配/指向目标动态分配/指向目标可扩展性没有行和列都可以扩展列可以扩展各行长度相同，固定可变可变行元素地址的连续性连续不连续不连续【例3-2.8】指针应用示例：关键字查表程序 设计一个关键字表，存放六个关键字：begin，end，if，else，while和for。编制一段程序，每输入一个字符串(标识符)，就去调用查表函数lookup。若标识符与某个关键字匹配，就返回该关键字在表中的序号(从0到5)，若找不到匹配的关键字，返回值为-1。 由于关键字的数量是已知的，因此可以在程序中定义一个字符指针数组Keyword，数组长度为6，数组中的每一个元素都指一个关键字字符串的地址。 程序为： #include<stdio.h> #include<string.h> #defineBUFSIZE80 #defineTABLELEN6 char*Keyword[TABLELEN]={"begin","end","if","else","while","for"}; /*lookupstringinKeywordandreturnitsindex*/ lookup(string) char*string; { inti; for(i=0;i<TABLELEN;i++) if(strcmp(string,Keyword[i])==0) return(i); return(-1); } main() { shortid; /*keywordindex*/ charstring[BUFSIZE]; /*inputstring*/ printf("Enterastring:"); while(scanf("%s",string)==1) { id=(short)lookup(string); if(id!=-1) printf("IDof[%s]is%d\n",string,id); else printf("string'%s'isnotakeyword\n",string); printf("Enterastring:"); } }【例3-2.9】数组应用示例：计算运费问题(程序设计课程例题) 已知若干个城市之间存在的公路以及两个城市间的运费(以图示为例)。输入发货和收货地名，如果它们之间存在公路，则输出所需的运费，否则输出无法直接运输的信息。 考虑采用二维数组存储城市之间的运费。假如已知共有7各城市，可建立一个二维数组cost[7][7]，反映了一个运费矩阵C(7,7)，其行数和列数均为城市的数量(7个)，每个数组元素cost[s][d]等于发货地(src)到收货地(dst)间的运费，如果没有公路直接连接，cost[s][d]为0。数据定义 设置一个城市名数组city[7][10](假定由每个城市名的长度不超过字符)，并设置一个二维数组c[7][7]，表示城市的公路连接和运费。定义为： #defineN7 charcity[N][10]; shortcost[N][N];存储城市、公路连接以及运费的函数input()为： voidinput() { intr,c; /*r:row,c:column */ for(r=0;r<N;r++) { scanf("%s",city[r]); for(c=0;c<N;c++) scanf("%d",&cost[r][c]); } }输入数据为 a 0404650 b 4040200 c 0400304 d 4000050 e 6230042 f 5005405 g 0040250求取运费的函数getCost() voidgetCost() { intr,c; /*r:row,c:column */ charsrc[10],dst[10]; printf("Inputsourcecityanddestinationcity:\t"); scanf("%s%s",&src,&dst); if((r=index(src))==-1||(c=index(dst))==-1||r==c) exit(0); /*无效的发货城市或者收货城市 */ if(cost[r][c]) /*存在公路，输出运费 */ printf("costfrom%sto%sis%d\n",src,dst,cost[r][c]); else /*不存在公路，无法直接运货 */ printf("nohighwayfrom%sto%s!\n",src,dst); } 其中，函数index()的功能是根据城市名查找在数组中的索引号。查找城市名的函数index() intindex(char*cityName) { intr; /*r:row,c:column */ for(r=0;r<N;r++) if(strcmp(cityName,city[r])) return(r); return(-1); }主函数main() main() { input(); getCost(); }3.3结构 数据处理是编制计算机程序的主要工作，我们可以发现往往有些数据相互之间关系密切，它们组合在一起可以表达某种信息，而且总是需要一起处理。例如，处理人员工资的数据时，人员的姓名、单位、基本工资、附加工资、扣发工资和实发工资等数据组合起来才能完整地表达一个人员的信息，而且这些数据的处理总是同时出现。假定用多个数组表示人员信息，对同一人员的各项数据用相同的下标来表示。这样的程序对数据的表达不够清晰。特别地，在数据对象很复杂，描述对象的信息有多重层次关系时，处理更为困难。 为此，C语言提供了一种方法，将若干个数据组合起来，形成一种构造性数据类型，称为结构。例如，将一个人员的信息定义为一种结构，结构中含有人员的各个数据，从而体现了这些数据之间密切的关系，并且易于编程和易于理解。3.3.1结构的定义和存储单元结构的定义最简单的结构类型定义 struct[结构标识符] /*结构标识符可以省略 */ { 成员定义 /*定义所有成员的数据类型 */ }; 例如：定义年月日为结构类型的语句为用结构类型定义结构变量 struct { shortday; charmonth[3]; shortyear; }d1; struct { shortday; charmonth[3]; shortyear; }d2[3]; struct { shortday; charmonth[3]; shortyear; }*d3; 表示定义了一个结构变量d1，一个含有结构数组d2[3]，以及一个指向结构对象的结构指针d3。这种结构类型含有3个成员year，month和day。用结构标识符定义结构变量 structdate { shortday; charmonth[3]; shortyear; }; structdated1,d2[3],*d3; 先定义结构structdate。再用structdate定义结构变量d1，结构数组d2[3]，以及结构指针d3。用typedef定义结构和变量 structdate { shortday; charmonth[3]; shortyear; }d1; typedefstructdateDATE; DATEd2[3],*d3; 表示先定义类型structdate(可以同时定义变量)， 然后将structdate定义成类型DATE， 再用类型DATE来定义变量。用define定义结构和变量 #defineDATEstructdate DATE { shortday; charmonth[3]; shortyear; }d1; DATEd2[3],*d3; 表示先将structdate定义成宏DATE， 然后用宏DATE定义类型(可以同时定义变量)， 再用类型DATE来定义变量。结构类型的存储空间 结构的存储空间的大小等于其成员所占存储空间的总和。 例如，结构类型date所占存储空间的字节数等于整型变量day、字符数组month以及整型变量year的字节数之和。 sizeof(structdate)=sizeof(day)+sizeof(month)+sizeof(year)=2+3+2=7 虽然sizeof(structdate)的理论计算为7字节，但是由于还要考虑偶数字节的排齐，实际需要的存储空间为8字节。结构类型的嵌套定义 假定已用define语句定义了两个结构A和B，结构类型的嵌套定义可以分成以下几种情况。非法的直接嵌套定义 A { shorta; Ab; }; 在结构类型A中含有同类的结构变量b，从而无法确定结构A所需的存储空间。非法的间接嵌套定义 A { ……; Bx; }; B { ……; Ay; }; 在结构类型A中含有结构类型B的变量x，而在结构类型B中含有结构类型A的变量y，两者相互依赖，从而无法确定结构A和B所需的存储空间。合法的嵌套定义 A { shorta; A*b; }; 在结构类型A中，包含有同类结构类型的指针变量b。由于指针变量b占4个字节，从而可确定结构A所需的存储空间。3.3.2结构与指针结构与指针的定义 假设有以下定义： DATEd，*pe，*pf，*pg; 表示定义了结构变量d，结构指针pe、pf和pg。结构指针的对象指向已知单元 例如：pe=&d;指向空 例如：pf=NULL;指向一个动态申请的结构变量 例如：pg=(DATE*)malloc(sizeof(DATE));指向若干个动态申请的结构(动态结构数组) 例如：ph=(DATE*)malloc(sizeof(DATE)*N);3.3.3结构成员的引用结构引用运算符包括“.”和“->”。 假定已有以下语句： DATEd,*pd; pd=&d; 可有以下应用的示例：结构变量成员的引用符“.” d.day=17; d.month[0]=‘A’; d.month[1]=‘p’; d.month[2]=‘r’; d.year=2000;结构指针对象成员的引用符“->” pd->day=17; pd->month[0]=‘A’; pd->month[1]=‘p’; pd->month[2]=‘r’; pd->year=2000;结构引用符“.”和“->”的等价 pd->year 等价于 (*pd).year pd->month[i] 等价于 (*pd).month[i]结构赋值结构成员的地址表示 &(d.year) 等价于 &((*pd).year) 等价于 &(pd->year) &(d.month[i]) 等价于 &((*pd).month[i]) 等价于 &(pd->month[i]) C语言不允许对结构变量进行整体赋值。例如有 DATEd1,d2,*pd; 其中，假定结构指针pd已经指向某个非空的结构变量。 如果需要将d1成员的值赋给d2的成员或者赋给pd对象的成员，以下语句是非法的： d2=d1; *pd=d1; 应该改为 d2.day=d1.day; for(i=0;i<=2;i++) d2.month[i]=d1.month[i]; d2.year=d1.year;或者 pd->day=d1.day; strcpy(pd->month,d1.month); pd->.year=d1.year;3.3.4结构的应用－链表链表的组成 链表是结构的一个非常重要的应用，其中一个重要的特点是在结构的成员中含有结构指针，通常是同类结构类型的指针。 链表由若干个结点(node)组成，每个结点都是结构类型的变量。其成员由两部分组成，一部分是数据成员，另一部分是指针成员。用某个指针成员(通常定义为next)指向下一个结点，各个结点逐个相连，从而构成一个链表。 例如，定义一个结构A，它的数据成员n存放结点的数据，通过成员指针next，将多个结点逐个相连形成链表。 #defineAstructa A { shortn; A*next; };链表的构成形式 链表的起始结点称为链表头/表头/首结点。指向表头的指针称为首指针/表头指针/表首指针。 链表的结尾结点称为链表尾/表尾/尾结点。指向表尾的指针称为表尾指针/尾指针。 若表尾的指针成员指向NULL，这样的链表称为单向链表。 若表尾的指针成员指向表头，这样的链表称为循环链表。 首指针的设置不使用首指针 例如，结构变量head就是链表头，因此不需要使用首指针。用结构变量的指针成员作为首指针 例如，定义结构变量：Ahead; 用head.next作为首指针，指向表头。用结构指针作为首指针(最常用) 例如，定义结构指针：A*first; 用first作为首指针，指向表头。尾指针的设置不使用尾指针 在许多应用中是不需要尾指针的，从而不一定设置尾指针。用结构变量的指针成员作为尾指针 例如，定义结构变量：Alast; 用last.next作为尾指针，指向表尾。用结构指针作为尾指针(最常用) 例如，定义结构指针：A*tail; 用tail作为尾指针，指向表尾。链表的前插入链表的设定 定义首指针： A*first; 假定不考虑哨兵和尾指针 初始链表为空表： first=NULL; 待插入结点： 用指针node指向。 非空链表： first非空。表头前插入(包括空表前插入)表中前插入操作 ①node->next=first; ①node->next=prev->next; ②first=node; ②prev->next=node;链表的后插入链表的设定 定义首指针和尾指针： A*first,*tail; 初始链表为空表： first=tail=NULL; 待插入结点： 用指针node指向。空链表的表尾后插入 node->next=first; first=tail=node;或 node->next=NULL; first=tail=node;或 first=tail=node; node->next=NULL;非空链表的后插入 非空链表的后插入包括非空链表的表尾后插入和非空链表的表中后插入两种情况。其中，可以把表尾后插入中的表尾指针tail看成是表中后插入的当前结点指针now。 尾结点的成员next可以指向NULL(单向链表)，也可以指向首结点(循环链表)，因此在后插入时统一用#表示next的值。 ①node->next=now->next; ②now->next=node; ③now=node; /*假定需要更新指针now */3.3.5数组和指针应用的讨论 要存储和处理N个数据，可以根据数据量的情况，考虑采用数组或者链表以实现不同的编程方案。数据量N的情况N为先知：数据量N已知，在程序运行时是固定的。N为后知：数据量N将在程序运行中获得，如通过输入或者通过计算得到。N为未知：数据量N在程序运行中是动态变化的。可采用的方案定义数组：定义N个元素的数组 Aa[N]；动态数组：动态申请N个单元 A*pa； pa=(A*)malloc(N*sizeof(A));采用链表：动态申请结点方案数据量N为已知N为可知N为未知定义数组唯一方案××动态数组更灵活比较适合×采用链表更灵活更灵活唯一方案3.5函数3.5.1函数间的数据通讯什么是数据通讯 在C语言中，函数是能够完成独立功能的程序段。也就是说，在函数的内部或者外部，可以各自定义变量。但是，函数又需要对其他函数定义的变量进行存取。例如，某个函数需要获得其他函数的变量值，或者需要将函数定义的变量值传递给其他函数。因此，必须考虑各个函数之间的数据通讯(数据共享)问题。 可以通过函数返回值、函数的虚实结合以及共享外部变量(静态数据)三种方式实现函数之间的数据通讯。函数返回值 通过函数的返回值，主调函数可以从被调函数获得一个数据，其实现的是被调函数向主调函数的单向传递。 在被调函数中，使用return语句，可以将一个基本类型的数据或者一个地址值返回(传递)给主调函数，或者说主调函数可以从被调函数获得数据，即获得一个基本类型的数据或者一个地址值。函数的传值调用 通过函数参数的虚实结合，被调函数可以从主调函数获得若干个数据，其实现的是通过主调函数的实参(实在参数)向被调函数的形参(形式参数)的单向传递。因此，函数参数的虚实结合又称为函数的传值调用。 形参的存储单元是在函数执行时获得的。也就是说，在函数开始运行之前(调用函数)，或者函数结束运行之后(函数返回)，形参所占的存储单元是不存在的。只有在该函数被调用的过程中，这些形参才会获得存储空间。因此，形参又被称为动态变量。 形参的值是在函数调用时由实参值传递来的，因此只有在函数调用时，形参才能获得数据。 无论被调函数中的形参和主调函数中的实参是否同名，它们必须在数量和数据类型上完全一致。 形参和实参在数据类型上的一致，可以表现为以下两种情况：数据对应 如果形参和实参都是变量，则不论是哪一种数据类型，只要是同一种数据类型，在函数调用时，数据传递的过程将把实参的数值复制给形参。如果不是同一种数据类型，将按照数据转换的隐式规则，先将实参转换成形参的数据类型，然后复制数据。地址对应 由于无论是数组还是指针，无论是一维数组还是二维数组，无论是指针数组还是二级指针，它们的值表达的都是地址。因此，如果形参和实参的值都是地址，则它们可以是数组或者指针。在函数调用时，数据传递的过程总是将实参的数值复制给形参。所以，只要分辨出它们的地址是指向同一类对象(例如同一种整型、同一种结构等等)的话，形参和实参就能够做到地址对应。【例3-5.1】函数的传值调用示例一：swap1main(){ shorta=5,b=3;① swap1(a,b); printf(“%d,%d\n”,a,b);}voidswap1(inta,inty){ intt;② t=a;③ a=y;④ y=t;}运行结果 a=5,b=3 主调函数main中实参a和b是变量，被调函数swap1中的形参a和y也是变量。由于函数调用的语句为swap1(a,b)，表示将main的a和b的数值传递给swap1的a和y。由于main:a和swap1:a占有不同的存储单元，main:b和swap1:y也占有不同的存储单元，因此在swap1中的变量交换操作没有改变main中变量a和b的值。【例3-5.2】函数的传值调用示例二：swap2 main中a和b是变量,实参&a和&b是地址,swap2中形参a和y是指针。由于调用语句为swap2(&a,&b),表示将main的变量a和b的地址传递给swap2的指针a和y,使swap2的a和y指向main的a和b,即main的a和b成为swap2的a和y的对象。因此swap2中对*a和*y的操作,实际上是对main的a和b进行操作,从而改变了它们的数值。main(){ shorta=5,b=3;① swap2(&a,&b); printf(“%d,%d\n”,a,b);}voidswap2(int*a,int*y){ intt;② t=*a;③ *a=*y;④ *y=t;}运行结果 a=3,b=5共享外部变量(静态数据) 外部变量和外部静态变量都是静态数据，它们的存储空间位于内存中的静态数据区。根据它们的定义位置，可确定用权访问这些静态数据的函数，从而通过静态数据的共享实现不同函数之间的数据通讯。这种方式通常称为是通过外部变量实现的数据通讯。 根据以下示例的源文件中静态数据的定义及位置，列出可共享数据的函数，表示这些函数可以存取(访问)与其相关的静态数据。源文件c1.cinta,b;staticintc;externintg;A(){ externintd;}intd;staticinte;B(){}源文件c2.cexterninta;staticintb;C(){}intg;staticintc;D(){ externintd;}3.5.2递归函数函数的递归调用 函数直接或者间接地调用函数自己，称为函数递归调用(直接递归或间接递归)。main(){ …... sub1(); …... sub2(); ……}sub2(){ …... sub3(); …... sub4(); ……}sub4(){ …... sub5(); …... sub2(); ……}sub5(){ …... sub5(); ……}递归函数的特点递归函数比较适用于可用递归方法描述的算法，应该使每层的算法完全一致。 例如求阶乘： if(n>1) n!=n•(n-1)! 例如用辗转相除法求最大公约数： if(a%b!=0) gcd(a,b)=gcd(b,a%b) 例如Hanoi塔问题： if(n>1) { moveN(n-1,from,tmp,to); moveOne(n,from,to); moveN(n-1,tmp,to,from); }必须是有条件的递归，通常是伴有if语句。即在某一层上能够结束，否则将引起死循环。 例如求阶乘： if(n==1) n!=1 例如用辗转相除法求最大公约数： if(a%b==0) gcd(a,b)=b 例如Hanoi塔问题： if(n==1) moveOne(1,from,to);必须设置是否递归的测试点和返回点。如果满足递归条件，进行递归调用；否则返回。 例如：#include<stdio.h>shortgcd(a,b)shorta,b;{ intr; if(a%(r=b)) /*递归测试*/ r=gcd(b,a%b); /*递归调用*/ return(r); /*返回点*/}main(){ shorta,b,r; scanf(“%d%d”,&a,&b); r=gcd(a,b); printf(“r=%d\n”,r);}递归方法不能节省空间，也不能节省时间，但是易于编程和易于理解算法。递归函数的适用性 递归函数比较适用于用递归算法描述的问题(递归问题)，但也可以用来解决非递归问题。而非递归函数不仅可以用来解决非递归问题，也可以用来解决递归问题。 或者说：递归问题可以采用递归函数编程来解决问题，也可以采用非递归函数。另外，非递归问题也可以采用非递归函数或者递归函数。【例3-5.3】递归函数示例一：Hanoi(汉诺)塔问题 算法(问题)描述： 利用C塔，将n个金片从A塔移到B塔。#include<stdio.h>intstep=0;moveOne(intn,charfrom,charto){ printf("step%3d:",++step); printf("movechip(%d)",n); printf("from%c",from); printf("to%c\n",to);}voidmoveN(n,from,to,tmp)intn;charfrom,to,tmp;{ if(n==1) moveOne(1,from,to); else { moveN(n-1,from,tmp,to); moveOne(n,from,to);main(){ shortn; printf("Entern:"); scanf("%d",&n); moveN(n,'A','B','C');} moveN(n-1,tmp,to,from); }}

【例3-5.4】递归函数示例二：用辗转相除法求最大公约数(用递归算法描述的问题)(1)用递归函数实现的程序 #include<stdio.h> shortgcd(shorta,shortb) { intr; if(a%b) r=gcd(b,a%b); else r=b; return(r); } main() { shorta,b,r; scanf(“%d%d”,&a,&b); r=gcd(a,b); printf(“r=%d\n”,r); }(2)用非递归函数实现的程序 #include<stdio.h> shortgcd(shorta,shortb) { intr; while(r=a%b) { a=b; b=r; } return(b); } main() { shorta,b,r; scanf(“%d%d”,&a,&b); r=gcd(a,b); printf(“r=%d\n”,r); }【例3-5.5】递归函数示例三：逆序打印链表结点(求解用非递归算法描述的问题)(1)顺序打印(采用非递归函数) #include<stdio.h> #defineNstructnode N{intn;N*next;}*first; voidprt(N*head) { N*node; for(node=head;node;node=node->next) printf(“n=%d\n”,node->n); } 调用函数： prt(first);(2)逆序打印(采用递归函数) #include<stdio.h> #defineNstructnode N{intn;N*next;}*first; voidprt(N*head) { if(!head) return; else prt(head->next); printf(“n=%d\n”,node->n); }3.7C语言和shell的通信3.7.1命令行参数 命令行参数是指针数组和二级指针的一种应用。 main函数的定义形式为： main([argc,argv]) 形参argc用于表示命令行参数的个数，argv表示命令行参数的内容。其中，argv可以用二级指针或者指针数组来表示。 (1)用指针数组表示 main(argc,argv) intargc;char*argv[]; (2)用二级指针表示 main(argc,argv) intargc;char**argv; 设可执行文件为try，执行命令为 $tryIamabc 则argc=4用指针数组表示argv 程序try.c的内容为: main(argc,argv) intargc; char*argv[]; { inti; for(i=0;i<argc;i++) { printf(“argv[%d]=%s\t”,i,argv[i]); printf(“argv[%d][0]:<%c>\n”,i,argv[i][0]); } } 其中，argv[i]是字符数组的首地址，argv[i][0]是字符数组的第一个元素。 通过编译生成可执行文件try。在命令行中运行及结果为： $tryIamABC argv[0]=try argv[0][0]:<t> argv[1]=I argv[1][0]:<I> argv[2]=am argv[2][0]:<a> argv[3]=ABC argv[3][0]:<A>用二级指针表示argv 程序try.c的内容为: main(argc,argv) intargc; char**argv; { inti; for(i=0;i<argc;i++,argv++) { printf(“argv[%d]=%s\t”,i,*argv); printf(“*argv[0]:<%c>\n”,*argv[0]); } } 其中，*argv是字符数组的首地址，*argv[0]是字符数组的第一个元素。 通过编译生成可执行文件try。在命令行中运行及结果为： $tryIamABC argv[0]=try *argv[0]:<t> argv[1]=I *argv[0]:<I> argv[2]=am *argv[0]:<a> argv[3]=ABC *argv[0]:<A>3.8程序设计标准(实施要求) 在编程的实践中逐步提高认识，认同编程的标准和规范，做到能够编写结构合理、风格良好的软件。基本要求 要求在本课程的练习和考试时按照讲义“程序设计标准”进行编程。数据类型、常量和运算符命名规则变量、指针的初始化函数排版注释高级要求数据管理调试程序风格程序和软件维护3.8.1数据类型、常量和运算符基本数据类型 在开始使用某个计算机的编程环境时，最好先明确基本数据类型(short，long，char，float，double)所占的字节数。 尽量少用自然(缺省)整数类型int，而明确地使用short和long类型的整数类型。常量 在程序中尽量避免出现常数，而先定义符合常量，然后在程序中使用该符合常量。例如：不要写成shortgroup[100];不要写成for(i=1;i<50;i++)应该改为#defineLEN100shortgroup[LEN];;应该改为#defineLAST50for(i=1;i<LAST;i++)或者#defineFIRST1#defineLAST50for(i=FIRST;i<LAST;i++)数据类型转换 在对不同类型的数据进行混合运算时，尽量避免使用缺省(隐式)的数据类型转换，而使用显式的数据类型转换。例如： 不要写成 3*4.25 应该根据实际需要而改为 3*(int)4.25 或者 (float)3*4.25运算符的分隔 在一个表达式中，应该合理地加空格来分隔运算符。不应该使用空格分隔的的运算符 负数运算符：-， 自增减运算符：++，--， 取值取址运算符：*，& 结构成员引用符：->，.，以及!，~，(类型)，sizeof()等 例如：不要写成 -a 应该写成 -a i++ i++需要使用空格分隔的的运算符 以下运算符需要在其左右加空格以分隔： 双目运算符：+，-，*，/，%， 移位运算符：<<，>>， 赋值运算符：= 关系运算符：<，<=，>，>=，==，!=， 逻辑运算符：&&，|| 复合赋值运算符：⊕=，条件运算符：?：，按位运算符：&，^，| 例如：不要写成 b*b-4*a*c 应该写成 b*b-4*a*c需要在左右一侧加空格的运算符 在左一侧加空格的运算符：(，[，{ 在右一侧加空格的运算符：)，]，}，分号运算符：；，逗号运算符：， 以上运算符如果连续出现，可以在之间加空格，也可以不加空格。 例如：以下两种写法都是合理的： if((node=(NODE*)(malloc(sizeof(NODE)))==NULL) 或者 if((node=(NODE*)(malloc(sizeof(NODE)))==NULL) shortdate[3][2]={{4,3},{5,6},7,8}}; 或者 sho