第09章C语言高级程序设计.ppt

C语言程序设计,湖南工学院,第9章 C语言高级程序设计,9.1 编译预处理命令 9.2 位运算 9.3 结构体高级应用链表 本章小结,9.1 编译预处理命令,ANSI C 标准规定可以在C源程序中加入一些“预处理命令”，以改进程序环境，提高编程效率。C程序中编译预处理语句的作用不是实现程序的功能，它们是发送给编译系统的信息。也就是说，对于预处理命令，必须在程序编译之前，先对这些特殊命令进行“预处理”。经过预处理后程序不再包含预处理命令了。 C语言提供的预处理功能主要有宏定义、文件包含及条件编译三种。 分别用宏定义命令，文件包含命令，条件编译命令来实现。为了与一般C语句相区别，这些命令以符号“#”开头。,9.1.1 宏,宏定义功能是定义符号常量和常参数的宏，宏定义编译预处理语句的格式如下 ： #define 字符串1 字符串2 它把字符串1定义为字符串2，字符串1称为字符串2的宏定义，例如，下面是符号常量的宏定义： #define ON 1 #define OFF 0 它把符号常量ON定义为1，OFF定义为0。符号常量经过宏定义后，就可以在程序中作为常量使用。例如： if(a=ON) printf(“Switch is ONn”); else if(a=OFF) printf(“Switch is OFFn”);,在系统执行编译预处理过程时，将把程序中出现的字符串1一律用字符串2置换，就是说程序中的符号常量用定义它们的常量置换，然后再对置换处理后的源文件进行编译。如上面程序段经编译预处理后成为下列形式： if(a=1) printf(“Switch is ONn”); else if(a=2) printf(“Switch is OFFn”); 在宏定义语句中，可以使用已经定义过的符号常量定义新的符号常理。例如： #define WID 40 #define LEN （WID+20） 其中第二个宏定义中使用了第一个宏定义的符号常量WID。在执行编译预处理时，程序中出现的所有符号常量WID都将被40置换，所有的符号常量LEN,不带参数的宏定义: 用一个指定的标识符(即名字)来代表一个字符串。 一般形式：#define 标识符 字符串 例：#define PI 3.14159 说明： （1）宏名一般习惯用大写字母表示。 （2）使用宏名代替一个字符串，可以减少程序中重复书写某些字符串的工作量。 （3）宏定义是用宏名代替一个字符串，也就是作简单的置换，不作正确性检查。 （4）宏定义不是C语句，不必在行末加分号. #define PI 3.14159; area=PI*r*r; 展开: area=3.14159;*r*r; 出现语法错误 （5）#define命令出现在程序中函数的外面，宏名的有效范围为定义命令之后到本源文件结束。 （6）可以用#undef命令终止宏定义的作用域。 格式：#undef 宏名,（7）在进行宏定义时，可以引用已定义的宏名，可以层层置换。 #define R 3.0 #define PI 3.14159 #define L 2*PI*R #define S PI*R*R main( ) printf(“L=%fnS=%fn”,L,S); （8）对程序中用双括号括起来的字符串内的字符，即使与宏名相同，也不进行置换。 （9）宏定义是专门用于预处理命令，只作字符替换。,带参数的宏定义： 不是进行简单的字符串替换，还要进行对数替换。 一般形式： #define 宏名(参数表) 字符串 例：#define S(a,b) a*b area=S(3,2) #define PI 3.14159 #define S(r) PI*r*r main() float a ,area; a=3.6; area=S(a); printf(“r=%fnarea=%fn”,a,area); ,说明： （1）对带参数的宏的展开只是将语句中的宏名后面括号内的实参字符串代替#define命令行中的形参。 area=S(a+b) 把实参a+b代替PI*r*r中的形参r,成为： area=PI*a+b*a+b 则 #define S(r) PI*( r)*( r),都将被（40+20）置换。例如，程序中的下列语句： area=LEN*WID; 在执行编译预处理时，该语句将被置换成： area=(40+20)*40; 经运算后变量area的值是2400。从上面的置换过程可以看到，LEN定义时包围WID+20的圆括号是不可缺少的，若上面的宏定义时不使用圆括号： #define LEN WID+20 则上面的area赋值表达式在编译预处理后成为： area=40+20*40; 这时变量area的计算结果值是840，它并不是预定的计算结果。因此，在进行宏定义时，为了保证宏定义被置换后仍保持正确的运算顺序，经常在定义式中使用必要的圆括号包围定义的式子。,在C语言程序中，宏定义语句除了定义符号常量外，还经常用于定义带参数的宏，带参数的宏是在定义的宏定义中可以带有若干参数。例如： #define MULT2（X） X*X 其中，MULT2（X）称为带参数的宏，X是它的形式参数。该宏定义把MULT2（X）定义为X*X。在此定义后，MULT2（X）就可以用在程序中代替定义它的运算表达式X*X。它的形式参数的使用特性类似于函数的形式参数。在程序中需要计算某个数的平方值时，可以使用这个已定义 的宏，例如： a=10; c=MULT2(a); 在进行编译预处理时，带参数的宏用它的定义置换，其中的形式参数用实际使用的实际参数置换。因此，上面的赋值表达式置换后的形式是： c=a*a;,其中定义式中的形式参数X被实际参数a置换，该运算表达式的结果是100。当程序中需要计算某两个变量和的平方时，如果使用上面定义的带参数的宏的话，如下所示： w=6;v=4; c=MULT2(w+v); 进行编译预处理后，上面的赋值表达式置换后的形式是： c=w+v*w+v; 它的运算顺序与预定的顺序完全不同，计算结果是34。如果上面的宏定义改为下列形式： #define MULT2（X） （X）*（X） 上面的赋值表达式置换后就成为： c=（w+v）*（w+v）; 它的运算结果就正确了。这里又一次看到在定义式中使用必要圆括号的重要性。,【例9.1】程序中的宏定义（计算球的体积） 程序如L9-1.c 该程序在编译预处理中，计算球体积的表达式语句： v=4*PI*MULT3(r)/3;其中的两个宏定义PI和MULT3将分别由定义它们的常量和表达式进行置换，实际上参加编译的语句如下所示： v=4*3.1415926*(r)*(r)*(r)/3; 在程序设计时，经常把那些反复使用的运算表达式定义不带参数的宏，这样一方面使程序更加简洁，另一方面可以使运算的意义更加明显。下面再给出几个带参数宏的例子，它们都是使用三项条件表达式定义的。 #define min(x,y) (xy)?x:y) 求x和y中较大的一个。,#define abs(x) (x=0)?x:-x) 求x的绝对值。 #define sign(x) (x0)?1:(x1)? 1:0) 判断x的符号。 上面给出的宏定义中，在定义式的运算表达式里都是单纯的形式。在实际应用时，应该根据需要加上保证运算顺序的圆括号。,9.1.2 文件包含,“文件包含”处理 所谓“文件包含”处理是指一个源文件可以将另外一个源文件的全部内容包含进来，即将另外的文件包含到本文件之中。C语言提供了#inctude命令用来实现“文件包含”的操作。其一般形式为 # include “文件名” 或 #include 注意： （1）一个include命令只能指定一个被包含文件，如果要包含几个文件，要用几个include命令。,（2）如果文件1包含文件2，而文件2中要用到文件3的内容，则可在文件1中用两个inctude命令分别包含文件2和文件3，而且文件3应出现在文件2之前，即在filel.C中定义： #include “file3.h” #include “file2.h” 这样，fite1和file2都可以用file3的内容。在file2中不必再用#include 了。 （3）在一个被包含文件中又可以包含另一个被包含文件，即文件包含是可以嵌套的。,【例9.2】文件put.h使用TYPE命令显示的内容如put.h代码，它包含有各种输出格式的带参数宏的定义： 程序如L9-2.c 【例9.3】 有如下两个源文件： filel.h L9-3.c,9.1.3 条件编译,为了解决程序的可移植性问题，C语言提供了条件编译命令，它能使用一个源程序在不同的编译环境下生成不同的目标文件，条件编译命令有以下几种： （1）# ifdef 标识符 程序段1 # else 程序段2 # endif 其功能是用来测试测试一个标识符（宏名）是否被定义，如果标识符已被定义，则在程序编译阶段只编译程序段1，否则编译程序段2。该命令形式的简化形式是没有#else部分，这时，若标识符未定义，则此命令中没有程序段被编译。,（2）# ifndef 标识符 程序段1 # else 程序段2 # endif 其功能是用来测试测试一个标识符（宏名）是否未曾被定义，如果标识符未被定义，则编译程序段1，否则编译程序段2。该命令形式的简化形式是没有#else部分，这时，若标识符已定义，则此命令中没有程序段被编译。 （3）#if 表达式 程序段1 #else 程序段2 #endif,它的作用是当指定的表达式为真时就编译程序段1，否则编译程序段2。其中的表达式必须是整型常量表达式（不包含sizeof运算符、强制类型转换和枚举常量）。该命令形式的简化形式是没有#else部分，这时，若表达式为“假”，则此命令中没有程序段被编译。 （4）#if 表达式1 程序段1 #elif 表达式2 程序段2 #elif 表达式3 程序段3 #else 程序段n #endif,这里的#elif其含义是“else if”，该命令的功能是，如果常量表达式1的值为“真”，则编译程序段1，否则如果常量表达式2的值为“真”，则编译程序段2，如果常量表达式的值都为“假”，则编译程序段n。也可以没有#else部分，这时，若所有表达式的值都为“假”，则此命令中没有程序段被编译。 （5） #if defined(宏名) 程序段1 #else 程序段2 #endif 该命令等价于#ifdef 标识符，但该命令可以判别多个宏名的定义情况，而#ifdef命令只能判断一个宏名的定义情况。！ Defined(宏名)的作用是当宏名未定义时其值为真，因此#if ！defined(宏名)等价于#ifndef 标识符。,例如，在alloc.h文件中，可以看到以下关于NULL的定义，其目的是适合不同编译模式的兼容性。 #ifndef NULL #if defined(_TINY_)|defined(_SMALL_)|defined(_MEDIUM_) #define NULL 0 #else #define NULL 0L #endif #endif 【例9.4】输入一个口令，根据需要设置条件编译，使之在调试程序时，按原码输出；在使用时输出“*”号。,#define DEBUG void main(viod) char pass80;int=-1; printf(“n Pleasa Input Password:”); do i+; passi=getch(); #ifdef DEBUG putchar(passi); #else putchar(*); #endif while(passi!=n); ,9.2 位运算,所谓位运算，是指对一个数据的某些二进制位进行的运算。每个二进制位只能存放1位二进制数“0”或者“1”。通常把组成一个数据的最右边的二进制位称作第0位，从右以此称为第1位，第二位，最左边一位称作最高位，如图91所示。,9.2.1 位运算和位运算符,C语言提供6种运算符，如表9-1所示。 说明: 反运算符“”是单目运算符，其余是双目运算符，即要求两侧各有一个运算量。 位运算的运算对象只能是整型或字符型数据，而不能是实型数据。,9.2.2 位运算符的使用,1 按位取反运算符“” 按位取反运算为单目运算，它将运算对象的各位取反，即将1变0，0变1。例如O24是对八进制数24（即二进制数00010100）按位求反： 00010100 11101011 运算结果为八进制数353。 2 按位与运算符“&” “按位与”是指两个运算对象按对应二进制位进行“逻辑与”运算，即当且仅当参加运算的两个对象的对应二进制都为1时，结果的对应二进制位为1，否则为0。即,0 因为x，y是整型，占两个字节，对应的二进制形式分别为0000000000000011和0000000000000101，所以 x = 0000000000000011 y = 0000000000000101 x&y = 0000000000000001 因此，3&5的值值等于1。如果参加&运算的是负数（如-3& -5），则以补码形式表示为二进制数，然后按位进行“与”运算。 “按位与”运算的应用主要为：位清零、测试指定位的值和获取指定位的值。,(1)位清零 如果想将一个数据中的某些位清零，根据“按位与”运算的含义，只需要鼗这些位与0进行“按位与”运算即可。 例95 设有一个字符型变量（8位二进制位），把它的低4位清0。 分析：欲使x的低4位为0，只需将x的低4位与0进行“按位与”即可。即x=x&0xf0。运算过程如下： x= * * * * * * * * & 1 1 1 1 0 0 0 0 * * * * 0 0 0 0 其中“*”是1或0。,(2)测试指定位的值 要想判断某一指定位的值是1还是0，只需将这一位与1进行“按位与”运算，然后判断结果是否为0即可。 例96 设x是一个字符型变量（8位二进制位），判断x的最低位是否为0。 分析：想要判断x的最低位是0还是1，可以进行如下运算： if(x&0x01)!=0)则x的最低位是1； 或者 if(x&0x0x)=0)则x的最低位是0； 因为： x = * * * * * * * * & 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 *,所以若x最低位为1，则表达式结果为1；若最低位为0，则表达式结果为0。 注意：“按位与”运算&的优先级低于关系运算符!=和=，所以表达式（x&0x01）的圆括号不能省略。 (3) 获取指定的值 要想获得某些位的值只需将这些位与1“按位与”运算，而将其他位清0即可。 例97 设X是unsigned类型的整数（16位二进制数），要想获取X的低8位，可做运算X&0X00ff。运算过程为： x=* * * * * * * * * * * * * * * * & 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 * * * * * * * * 可以看出，结果只保存了X的低8位。,例98 从键盘输入一个正整数，判断此数是奇数还是偶数。 分析：一个正数是奇数还是偶数，只需要判断最低位是1还是0。若最低位为0，该数是偶数；最低位为1，则是奇数。 程序如L9-8.c 3 按位或运算符“|” “按位或”运算是指两个运算对象按对应二进制位进行“逻辑或”运算，即当参加运算的两个对象的对应二进制位有一个“1”时，结果的对应二进制位为“1”，如下所示： 0|0=0；0|1=1；1|0=1；1|1=1； 例如：设int x=3,y=-5,则x|y的结果如下：,x= 0000000000000011 | 1111111111111011 1111111111111011 “按位或“运算常用于对一个数据中的某些位置1。 例99 编一程序，从键盘输入一个字符，如果是大写字母，则转换成小写字母输出。 分析：字符在计算机内是以ASC码表示的，小写字母的ASC码值范围为16进制数61H7AH，大写字母的ASC码值范围为16进制数41H5AH，即小写字母和大写字母的ASC码值相差20H。因此要想把大写字母转换成小写字母只需把大写字母的第6位置1即可。如：A的ASC码为41H，a的ASC码值为61H。 A=01000001 （41H） | 00100000 （20H） a=01100001 (61H),程序如L9-9.c 4 按位异或运算符“” “按位异或”运算是指两个运算对象按对应二进制位进行“逻辑异或”运算，即当参加运算的两个对象的相应二进制位一个为“0”，另一个为“1”时，结果的对应二进制位为“1”，如下所示： 00=0;01=1;10=1;11=0; “按位异或”运算的应用； （1）使数据中的某些位求反。因为0和1的异或结果为1，1和1的“异或”结果为0，所以只需将要求反的位与1进行“异或”运算，就可以将该位求反。 （2）将变量清0。任何一个属于变量本身的“异或”结果都为0。利用“异或”运算的这个性质可以完成对变量的清0操作。,5 左移运算符“” 右移运算符“”的使用方式为： 运算对象右移位数 右移运算符将运算对象的每个二进制位同时向右移动指定的位数，从右边移出的低位部分被丢弃。对无符号数，左边空出的高位补0；对有符号数，正数的高位部分补0，负数的高位部分补0还是1和计算机系统有关。移入0的称为“逻辑右移”，移入1的称为“算术右移”。,“逻辑右移”相当于无符号数除以2，“算术右移”相当于有符号数除以2。 例如： a: 1001011111101101 a1: 0100101111110110 -逻辑右移 a1: 1100101111110110 -算术右移 7 位复合赋值运算符 类似于算术运算的复合运算符，位运算符和赋值运算符也可以构成“复合赋值运算符”。如9-2所示。,8 位运算的应用 （1）键盘扫描码 键盘上除了ASC|码外，还有非ASC|码（如左移键“”对应的编码），叫扩充键盘码。我们把扩充键盘码放在高八位，ASC|码放在低八位所组成的代码称为扫描码。 对于某一特定的扫描码，若其低八位不为零，则此八位就是相应字符的ASC|码值；若低八位是零，则高八位是扩充键盘码，需要再读取入第二个字节，根据它的值来判断它是那一个功能键。表9-3给出了单功能键和组合功能键的键值，表中代码,系指第二个字节键值的十进制数。例如，“”的扫描码低八位应为零，而高八位是0X4B，所以，“”键的扫描码为0X4B00；回车键也有对应的ASC|码，故其扫描码的低八位是回车键的ASC|码值0X0D。,(2) 测试键盘扫描码 调用标准库函数bioskey()读取键盘扫描码，再通过位运算分离低八位字符的ASC|码和高八位的扩充键盘码。注意使用bioskey()函数，应在头部加上#include “bios.h”。 例910 利用bioskey()函数，测试键盘扫描码，按ESC键退出。 算法设计： （1）利用位的“与”运算，提取低8位 low=key ,程序如L9-10.c 说明： （1）关于函数bioskey() 函数bioskey()的功能是用于识别用户按键和获得按键值。函数原型是： int bioskey(int cmd); 在中定义，在使用它时，应用include命令将bios.h文件包含进来。其中参数cmd可取0或1。 当cmd=1时，检测键盘是否击键，如果没有击键，函数将返回0，否则返回非零； 当cmd=0时，返回从键盘输入的扫描码。 语句key=bioskey(0);读取键盘输入的扫描码，并存储在变量key中。,9.2.3 位段,在计算机中一般以字节为单位存放数据，但实际上有时存储一个信息不必用一个字节或多个字节，例如，“真”或“假”用0或1表示，即只需要1位表示即可。因此，在计算机里常常在一个字节中放几个信息。 C语言提供两种方法，操作一个字节中的一个或几个二进制位。 1 位运算法 如图9-2所示，假设a、b、c和d分别占2位、6位、4位和4位，设data由a、b、c和d组成。,如果想将c的值置为12，用位运算方法，操作如下： 将数x=12左移4位，使1100成为右面的第47位，即： x=4 (0000000011000000) （2） 将data与0xff0f进行“与”运算，使data的第47位全为0，即： data 显然用位运算方法太麻烦，下面介绍使用位段结构体的方法,2 位段 C语言允许在一个结构体中以位为单位来指定其成员所占内在长度，这种以位为单位的成员称为“位段”或称“位域”（bit field）。利用位段能够用较少的位数存储数据。 （1）位段结构类型定义 位段是一种构造类型，类型定义的方法为： struct 类型名 基类型 位段名1：位段1占用位数； 基类型 位段名2：位段2占用位数； 基类型 位段名n：位段n占用位数； ;,例如，图9-2所示的问题，可以用位段结构类型定义为： struct my_data unsigned a:2; unsigned b:6; unsigned c:4; unsigned d:4; ; 其中my_data称位段名，它包含4个位段（bit field），每个位段的数据类型都是unsigned，各位段所占的二进制位数由冒号后面的数字指定：2，6，4，4。,（2） 位段变量的定义与引用 定义了位段结构类型后，就可以定义相应的位段结构类型变量了。其定义方法和其他变量的定义方法一样。 如，struct my_data data；位段数据的引用方法和结构成员的引用方式相同。例如： data.c = 12; 就实现了上题的目的。 （3） 关于位段的说明 位段的基类型必须为unsigned int 类型。 可以将类型说明和变量说明一起完成。例如， struct my_data unsigned a:2; unsigned b:6;,unsigned c:4; unsigned d:4; data; 可以定义无名位段，它起着位段之间的分隔作用。例如： struct my_data1 unsigned a:4; unsigned b:4; unsigned :2; unsigned c:2; data1; 该位段的第3个位段是无名位段，占2个二进制位，其作用是交b和c两个位段分隔开，如图9-3所示。, 若某一位段要从另一个字开始存放。可以定义无名位段的长度为0，用以下形式定义： struct my_data2 unsigned a:4; unsigned b:4; unsigned :0; /*无名位段长度为0*/ unsigned c:2; data2; 位段变量data2在内存的存储格式如图9-4所示。由于用了长度为0的位段，使其下一个位段从下一个字（每字2个字节）开始存放。因此，a、b存储在一个字中，c存储在下一个字中。, 一个位段必须存储在同一存储单元（字）中，不能跨单元（字）存储。如果一个单元（字）空间不能容纳下一个位段，则该空间不用，而从下一个单元（字）起存放该位段。 位段的长度不能大于存储单元（字）的长度，也不能定义位段数组。,9.3 结构体高级应用链表,数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要3 0个大小的数组，有时需要5 0个数组的大小，难于统一。我们只能够根据可能的最大需求来定义数组，常常会造成一定存储空间的浪费。 我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的浪费。,9.3.1 链表和动态存储分配概述,在数组一章中，曾介绍过数组的长度是预先定义好的， 在整个程序中固定不变。C语言中不允许动态数组类型。例如： int n;scanf(“%d“, 用变量表示长度，想对数组的大小作动态说明， 这是错误的。但是在实际的编程中，往往会发生这种情况， 即所需的内存空间取决于实际输入的数据，而无法预先确定。对于这种问题， 用数组的办法很难解决。为了解决上述问题，C语言提供了一些内存管理函数，这些内存管理函数可以按需要动态地分配内存空间， 也可把不再使用的空间回收待用，为有效地利用内存资源提供了手段。 常用的内存管理函数有以下三个：,1.分配内存空间函数malloc 调用形式： (类型说明符*) malloc (size) 功能：在内存的动态存储区中分配一块长度为“size” 字节的连续区域。函数的返回值为该区域的首地址。 “类型说明符”表示把该区域用于何种数据类型。(类型说明符*)表示把返回值强制转换为该类型指针。“size”是一个无符号数。例如： pc=(char *) malloc (100); 表示分配100个字节的内存空间，并强制转换为字符数组类型， 函数的返回值为指向该字符数组的指针， 把该指针赋予指针变量pc。 2.分配内存空间函数 calloc calloc 也用于分配内存空间。 调用形式： (类型说明符*)calloc(n,size),功能：在内存动态存储区中分配n块长度为“size”字节的连续区域。函数的返回值为该区域的首地址。(类型说明符*)用于强制类型转换。calloc函数与malloc 函数的区别仅在于一次可以分配n块区域。例如： ps=(struet stu*) calloc(2,sizeof (struct stu); 其中的sizeof(struct stu)是求stu的结构长度。因此该语句的意思是：按stu的长度分配2块连续区域，强制转换为stu类型，并把其首地址赋予指针变量ps。 3.释放内存空间函数free 调用形式： free(void*ptr); 功能：释放ptr所指向的一块内存空间，ptr 是一个任意类型的指针变量，它指向被释放区域的首地址。被释放区应是由malloc或calloc函数所分配的区域：,例9.11 分配一块区域，输入一个学生数据。 程序如L9-11.c 本例中，定义了结构stu，定义了stu类型指针变量ps。 然后分配一块stu大内存区，并把首地址赋予ps，使ps指向该区域。再以ps为指向结构的指针变量对各成员赋值，并用printf 输出各成员值。最后用free函数释放ps指向的内存空间。 整个程序包含了申请内存空间、使用内存空间、释放内存空间三个步骤， 实现存储空间的动态分配。链表的概念在例7.9中采用了动态分配的办法为一个结构分配内存空间。每一次分配一块空间可用来存放一个学生的数据， 我们可称之为一个结点。有多少个学生就应该申请分配多少块内存空间， 也就是说要建立多少个结点。当然用结构数组也可以完成上述工作， 但如果预先不能准确把握学生人数，也就无法确定数组大小。 而且当学生留级、退学,之后也不能把该元素占用的空间从数组中释放出来。 用动态存储的方法可以很好地解决这些问题。 有一个学生就分配一个结点，无须预先确定学生的准确人数，某学生退学， 可删去该结点，并释放该结点占用的存储空间。从而节约了宝贵的内存资源。 另一方面，用数组的方法必须占用一块连续的内存区域。 而使用动态分配时，每个结点之间可以是不连续的(结点内是连续的)。 结点之间的联系可以用指针实现。 即在结点结构中定义一个成员项用来存放下一结点的首地址，这个用于存放地址的成员，常把它称为指针域。可在第一个结点的指针域内存入第二个结点的首地址， 在第二个结点的指针域内又存放第三个结点的首地址， 如此串连下去直到最后一个结点。最后一个结点因无后续结点连接，其指针域可赋为0。这样一种连接方式，在数据结构中称为“链表”。,在链表中，第0个结点称为头结点， 它存放有第一个结点的首地址，它没有数据，只是一个指针变量。 以下的每个结点都分为两个域，一个是数据域，存放各种实际的数据，如学号num，姓名name，性别sex和成绩score等。另一个域为指针域， 存放下一结点的首地址。链表是一种常见的重要的数据结构。链表中的每一个结点都是同一种结构类型。 它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量，以head表示，它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。因此，head指向第一个元素：第一个元素又指向第二个元素；，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。,链表是一种复杂的数据结构，其数据之间的相互关系使链表分成三种：单链表、循环链表、双向链表，下面将逐一介绍。,9.3.2 单链表,单链表有一个头节点h e a d，指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此,9.3.2.1 单链表的结构,结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问那一个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为N U L L。图9-5还给出这样一层含义，链表中的各节点在内存的存储地址不是连续的，其各节点的地址是在需要时向系统申请分配的，系统根据内存的当前情况，既可以连续分配地址，也可以跳跃式分配地址。看一下链表节点的数据结构定义： struct node int num; struct node *p; ;,在链表节点的定义中，除一个整型的成员外，成员p是指向与节点类型完全相同的指针。在链表节点的数据结构中，非常特殊的一点就是结构体内的指针域的数据类型使用了未定义成功的数据类型。这是在C中唯一规定可以先使用后定义的数据结构。 单链表的创建过程有以下几步： 1 ) 定义链表的数据结构。 2 ) 创建一个空表。 3 ) 利用m a l l o c ( )函数向系统申请分配一个节点。 4 ) 将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新节点接到表尾。 5 ) 判断一下是否有后续节点要接入链表，若有转到3 )，否则结束。, 单链表的输出过程有以下几步 1) 找到表头。 2) 若是非空表，输出节点的值成员，是空表则退出。 3) 跟踪链表的增长，即找到下一个节点的地址。 4) 转到2 )。 例9.12 创建一个存放正整数（输入- 9 9 9做结束标志）的单链表，并打印输出。 程序如L9-12.c 在链表的创建过程中，链表的头指针是非常重要的参数。因为对链表的输出和查找都要从链表的头开始，所以链表创建成功后，要返回一个链表头节点的地址，即头指针。,9.3.2.2 单链表的插入与删除,在链表这种特殊的数据结构中，链表的长短需要根据具体情况来设定，当需要保存数据时向系统申请存储空间，并将数据接入链表中。对链表而言，表中的数据可以依此接到表尾或连结到表头，也可以视情况插入表中；对不再需要的数据，将其从表中删除并释放其所占空间，但不能破坏链表的结构。这就是下面将介绍的链表的插入与删除。 1. 链表的删除 在链表中删除一个节点，用图9-6描述如下：,例9.13 创建一个学生学号及姓名的单链表，即节点包括学生学号、姓名及指向下一个节点的指针，链表按学生的学号排列。再从键盘输入某一学生姓名，将其从链表中删除。,首先定义链表的结构： struct int num;/ * 学生学号* / char str20; / * 姓名* / struct node *next; ; 从图9-6中看到，从链表中删除一个节点有三种情况，即删除链表头节点、删除链表的中间节点、删除链表的尾节点。题目给出的是学生姓名，则应在链表中从头到尾依此查找各节点，并与各节点的学生姓名比较，若相同，则查找成功，否则，找不到节点。由于删除的节点可能在链表的头，会对链表的头指针造成丢失，所以定义删除节点的函数的返回值定义为返回结构体类型的指针。,struct node *delet(head,pstr)以/*he a d 为头指针，删除ps t r 所在节点*/ struct node *head; char *pstr; struct node *temp,*p; temp=head; / * 链表的头指针* / if (head=NULL) / *链表为空* / printf(“nList is null!n“); else /*非空表* / temp=head; while (strcmp(temp-str,pstr)!=0,temp=temp-next; / * 跟踪链表的增长，即指针后移* / if(strcmp(temp-str,pstr)=0 ) / *找到字符串* / if(temp=head) / * 表头节点* / printf(“delete string :%sn“,temp-str); head=head-next; free(temp); / *释放被删节点* / else p-next=temp-next; /表*中节点*/ printf(“delete string :%sn“,temp-str); free(temp); ,else printf(“nno find string!n“);没/找* 到要删除的字符串*/ return(head); / *返回表头指针* / 2. 链表的插入 首先定义链表的结构： struct int num; /*学生学号* / char str20; /*姓名* / struct node *next; ; 在建立的单链表中，插入节点有三种情况，如图9 - 7所示。,插入的节点可以在表头、表中或表尾。假定我们按照以学号为顺序建立链表，则插入的节点依次与表中节点相比较，找到插入位置。由于插入的节点可能在链表的头，会对链表的头指针造成修改，所以定义插入节点的函数的返回值定义为返回结构体类型的指针。节点的插入函数如下： struct node *insert(head,pstr,n) / *插入学号为n、姓名为p s t r 的节点* / struct node *head; / *链表的头指针* / char *pstr; int n; struct node *p1,*p2,*p3; p1=(struct node*)malloc(sizeof(struct node)分;配/*一个新节点*/ strcpy(p1-str,pstr) ; / * 写入节点的姓名字串* / p1-num=n ; / * 学号* /,p2=head; if (head=NULL) / * 空表* / head=p1; p1-next=NULL;/ *新节点插入表头* / else /*非空表* / while(np2-num / * 跟踪链表增长* / if (nnum) / *找到插入位置* / if (head=p2) / * 插入位置在表头* / ,head=p1; p1-next=p2; else /*插入位置在表中* / p3-next=p1; p1-next=p2; else /*插入