《结构和链表》PPT课件.ppt

1,第7章 结构和链表,7.1 结构类型和结构变量 7.2 结构数组 7.3 结构与函数 7.4 链表 *7.5 联合,*7.6 位域 *7.7 枚举 *7.8 类型定义 *7.9 变量定义,2,基本类型：如整型、实型、字符型等。 构造类型：数组，每个元素都是属于同一个类型。 结构类型：不同的数据类型组成一个整体方便引用。 例如：一个学生数据实体可能有以下多项信息 学号、 姓名、 性别、 年龄、 成绩、 家庭地址 int char char int float char 说明：这类实体的数据因所包含的成员类型不同，不能用单个数组来表示，也不便将它们的成员分拆成多个独立的简单变量，因为这样会失去实体的整体性。,7.1 结构类型和结构变量,3,结构类型形式： struct 结构类型名 成员说明表 ; 其中 关键字“struct”：引出结构类型的定义。 结构类型名：结构类型的标记，用来定义引用该结构的结构变量。 成员说明表：指明该结构类型的各成员的数据类型和名称。 每个成员的说明形式为： 类型 成员名;,1. 结构类型,4,【例】学生基本信息的结构类型： struct student int number; /* 学号 */ char name20; /* 姓名，设姓名少于20个字符 */ char sex; /* 性别 */ char address40; /* 家庭地址 */ ; 说明：在C+中，如果不会引起混淆(例如，结构类型与结构变量同名)，引用结构类型可以不用struct引导。,结构类型例,5,当结构类型中的某个成员又是另一个结构类型时，这种结构类型是一种嵌套的结构类型。 例如，给上述学生信息增加出生日期，并将出生日期定义为一种包含日、月、年3项信息的结构类型，则更完整的学生信息类型就被定义成嵌套的结构类型。,嵌套的结构类型,6,struct Date int day; /* 日 */ int month; /* 月 */ int year; /* 年 */ ; struct student int number; /* 学号 */ char name20; /* 姓名 */ char sex; /* 性别 */ struct Date birthday; /*嵌套 Date结构 */ char address40; /* 家庭地址 */ ;,嵌套的结构类型例,7,在结构类型定义中，详细列出了结构类型所包含的每个成员的名称及其类型。实际上，结构类型定义只是表明一类实体其数据属性的“模式”，并不定义一个特定的数据实体，因此不要求分配存储单元。 程序如果要实际使用结构类型所描述的数据信息，就必须定义结构变量。 结构变量要占用存储单元，能存放如结构类型所描述的具体数据。 对结构类型和结构变量，我们可以简单地理解为，结构类型是表示数据框架的描述文本，结构变量才能存放实际数据。,2. 结构变量,8,一、先定义结构类型，再声明结构变量 形式：struct 结构类型名 结构变量名表; 例如：利用前面已定义的结构类型 student声明结构变量 代码： struct student st1, st2; 其中： student为结构类型名，st1和st2为结构变量。 说明：结构变量声明后，每个结构变量的成员名称、成员个数和各成员的数据类型与结构类型定义中的成员名称、成员个数和各成员的数据类型相一致。,结构变量的定义,9,结构变量内存分配单元,10,二、在定义结构类型的同时声明结构变量,一般形式： struct 结构类型名 成员说明表 结构变量表;,结构变量的定义,例如： struct stuSType int number;/* 学号 */ char name20;/* 姓名 */ int score;/* 成绩 */ stuS;,结构变量,11,在定义结构变量的同时给它赋初值，称为结构变量的初始化。结构变量初始化时，要按结构类型定义中成员的顺序逐一给出各成员的初值。 例如：struct point /* 说明绘图程序的坐标类型 */ int x; int y; p1 = 20, 50, p2; /* p1的x值为20，p1的y值为50 */ 说明：也可以在定义结构类型与声明结构变量分开的情况下，在声明结构变量时进行初始化。 例如： struct point p3 = 10, 40, p4 = 20, 50;,结构变量初始化,12,要注意结构类型名和结构变量名的区别。不能对结构类型名进行赋值、存取或运算，因为类型不占用存储空间；而结构变量会占用存储空间，定义时可以赋初值，定义后可引用。 结构变量初始化的时间。静态的和全局的结构变量初始化在程序执行之前完成，静态的结构变量未指定初值时，值自动置0。局部结构变量初始化是程序控制每次进入它所属辖域时创建并初始化，未指定初值的局部结构变量其初值是不确定的。,结构变量初始化说明,13,可以定义指向结构的指针变量（结构指针变量简称结构指针）。 例如: struct Date *pd, date3; /* 定义变量 */ pd = /* pd指向date3 */ 表示：定义结构指针pd和结构变量date3，并使结构指针pd指向结构变量date3，即结构指针pd的内容为结构变量date3所占据的存储块的首地址。,结构变量初始化说明,14,一、引用结构变量 1. 用结构变量名直接引用结构变量 例如： struct student int number;/* 学号 */ char name20;/* 姓名 */ float score;/* 成绩 */ st1 = 10001, Zhang ping, 85.0, st2; st2 = st1; /* 将结构变量st1作为整体赋值给结构变量st2 */ 说明：两个结构变量必须是同类型的。,3. 结构变量的引用,15,2. 指向结构变量的指针间接引用结构变量 例如： struct student int number;/* 学号 */ char name20;/* 姓名 */ float score;/* 成绩 */ st1 = 10001, Zhang ping, 85.0, st2; struct student *p1 = /* 定义结构指针变量p1，并指向结构变量st1的首地址 */,3. 结构变量的引用,16,二、引用结构成员 1. 使用结构变量和成员运算符 引用方法：结构变量名.成员名 其中：点符号“.”是结构的成员运算符，是优先级最高运算符之一。 假设有前面定义的类型为stuSType的结构变量stuS 例如： stuS.name /* 直接引用stuS结构变量的name成员*/,3. 结构变量的引用,17,引用结构变量的成员无非是对该成员进行输入输出、赋值、运算等操作。 例如: printf(学号：%d 姓名：%s 成绩：%dn, stuS.number, stuS.name, stuS.score);/* 输出学生stuS的信息 */ 代码： stuS.score += 5; /* 更新学生stuS的成绩 */ strcpy(stuS.name, Li ming); /*更正学生stuS的姓名 */,3. 结构变量的引用,18,2. 使用结构指针和指针运算符 引用方法：指针变量名-成员名 其中：“-”是指针运算符，它是由减号“-”和大于号“”两个字符组成（请注意中间不能有空格符），其优先级与成员运算符“.”一样，也是优先级最高的运算符之一。 继续使用前面定义的结构变量stuS，可以使用结构指针间接引用stuS结构变量的成员。 struct stuSType *sp = /* 修改成绩 */,二、引用结构成员,19,3. 使用结构指针和成员运算符 引用方法：(* 指针变量名).成员名 其中：圆括号是必要的。若省略，由于成员运算符“.”优先级高于“*”，将会导致编译错误。 例如： struct stuSType *sp = */,二、引用结构成员,20,(1) 不能直接对结构变量进行输入或输出，只允许对结构变量的成员变量进行输入和输出。 例如，对于前面定义的类型为student的结构变量st1，以下分别是错误和正确的代码： printf(%s, st1); /*错误，st1是结构变量不能直接输出*/ printf(%s, st1.name); /*正确，仅输出st1的name成员 */,引用结构变量或成员注意,21,(2) 如果结构中的成员本身也是一个结构类型，在引用该成员的成员时需使用多个成员运算符“.”，将嵌套的结构成员一级一级地连续指定。 例如，想引用前面定义的类型为student的结构变量st1中成员birthday成员year， 正确的写法是： st1.birthday.year,引用结构变量或成员注意,22,#include struct stuScore /* 定义结构 */ char name20; int chinese; int math; ; void main() float aver1,aver2,aver3; struct stuScore st1,st2,st3; /* 定义3个结构变量 */ printf(请输入3位学生的姓名、语文成绩、数学成绩n); scanf(%s%d%d, st1.name, ,【例7.1】利用结构变量，输入3个学生的姓名、语文成绩和数学成绩，然后计算每个学生的平均成绩并输出。,23,aver1=(st1.chinese+st1.math)/2.0; /* 计算平均成绩 */ aver2=(st2.chinese+st2.math)/2.0; aver3=(st3.chinese+st3.math)/2.0; printf(姓名t语文t数学t平均成绩n); printf(%st%4dt%4dt%6.2fn, st1.name, st1.chinese, st1.math, aver1); printf(%st%4dt%4dt%6.2fn, st2.name, st2.chinese,st2.math, aver2); printf(%st%4dt%4dt%6.1fn, st3.name, st3.chinese,st3.math, aver3); ,【例7.1】程序续,24,从例7.1中可以看出，一个结构变量只能存放一个学生的基本信息。如果要描述两个学生的信息需要有两个结构变量，依此类推， 当要描述一个班级的学生时，独立定义同样类型的许许多多结构变量的方法显然是不可取的。在C程序设计中，一般用结构类型描述个体的信息结构，用数组表示个体的集合。 当数组的元素是结构时，这种数组就称为结构数组。 例如，用结构数组表示一个班级学生，数组的元素存储一个学生的有关信息。这样，能充分反映班级的整体性，程序处理也变得更为方便。,7.2 结构数组,25,定义结构数组与定义结构变量的方法类似也有两种方法。 (1) 先定义结构类型，再声明结构数组 struct stuScore char name20; int chinese; int math; ; struct stuScore st3;,1. 结构数组的定义,结构数组,26,与结构变量初始化相仿，在定义结构数组时，也可给结构数组赋初值。例如： struct stuScore char name20; int chinese; int math; st3=Zhang,80,85,Li,85,90,Wang,90,70;,结构数组的初始化,27,结构数组的引用实际上是对每个元素中的成员进行引用。与引用结构成员类似，也有以下3种方法： (1) 使用结构数组元素和成员运算符 方法：结构数组名元素下标.结构成员名 例如：printf(%s, st0.name); 说明：输出第1个学生的姓名，即Zhang,2. 结构数组的引用,28,2. 结构数组的引用,(2) 使用结构指针和指针运算符 方法：指针变量名-成员名 例如： struct stuScore *sp = st; /*定义结构指针sp，指向结构数组st首元素*/ printf(%sn, sp-name); /*输出第1个学生的姓名，即Zhang */ sp+;/* 结构指针指向下一个元素 */ printf(%sn, sp-name); /* 输出第2个学生的姓名，即Li */,29,2. 结构数组的引用,(3) 使用结构指针和成员运算符 方法：(* 指针变量名).成员名 例如： struct stuScore *sp = st; /*定义结构指针sp，指向结构数组st首元素*/ printf(%sn, (*sp).name); /* 输出学生st0的姓名，即Zhang */ sp+;/* 结构指针指向下一个元素，即指向st1 */ printf(%sn, sp-name);/* 输出学生st1的姓名，即Li */,30,#include struct stuScore char name20; int chinese; int math; ; void main() int i; float aver3;/* 定义普通数组 */ struct stuScore st3;/* 定义结构数组 */ printf(请输入3位学生的姓名、语文成绩、数学成绩n);,【例7.2】利用结构数组，输入3个学生的姓名、语文成绩和数学成绩，然后计算每个学生的平均成绩并输出。,31,for( i=0; i3; i+) scanf(%s%d%d, sti.name, ,【例7.2】程序续,32,在C语言中，函数的形参可以是变量、指针、数组，也允许是一个结构。 将一个结构传递给函数有三种方式：传递单个成员、传递整个结构、传递指向结构的指针。 传递单个成员或整个结构给函数在C中认为是值调用，即在被调用的函数中尽管修改了形参的值，但不会改变调用函数时提供的实参变量的值。,7.3 结构与函数,33,将结构成员作为实参传递给一个函数，实际上和其他基本数据类型的传递方法相同。 【例7.3】输入年月日，输出该年中的第几天 #include int dayTable12=31,28,31,30,31,30,31,31,30,31,30,31, 31,29,31,30,31,30,31,31,30,31,30,31; /* 平年或闰年 */ struct Date /* 定义一个Date结构类型 */ int day; int month; int year; int yearDay; date; /* 定义一个Date结构类型的结构变量 */,1. 结构成员作为函数参数,34,int dayofYear(int d, int m, int y) /* 计算年中第几天函数 */ int i, leap, day = d; leap = (y%4 = 0 /* 返回计算的结果 */ ,【例7.3】程序续 dayofYear() 函数,35,void main() int leap, days; printf( Date Conversion Programn); printf(Year = ); scanf(%d, ,【例7.3】程序续主函数,36,leap = (date.year%4 = 0 ,【例7.3】程序续主函数,37,程序运行时，输入的数据与输出的结果如下：,【例7.3】程序运行结果,38,使用结构作为实参传递给一个函数，实际上将这个结构的所有成员都传递给了被调用函数的形参。 以例7.3程序为例，对主函数中对函数dayofYear的调用，原来使用表示日、月、年的3个结构成员作为实参改为用一个结构变量date作为实参。即将代码 date.yearDay = dayofYear(date.day, date.month, date.year); 改写成 date.yearDay = dayofYear(date);,2. 结构作为函数参数,39,对应的dayofYear函数也要作如下的修改： int dayofYear(struct Date d) /* 计算年中第几天函数 */ int i, leap, day = d.day; leap=(d.year%4=0 /* 返回计算的结果 */ ,2. 结构作为函数参数,40,指向结构的指针作为函数的形参。实参可以是结构的地址，也可以是指向结构的指针变量。 仍以例7.3程序为例，主函数中对函数dayofYear的调用，原来使用结构变量date作为实参现改为用结构变量date的地址作为实参。即将代码 date.yearDay = dayofYear(date); 改写成 dayofYear(,2. 结构指针作为函数参数,41,对应的dayofYear函数也要作如下的修改： /* 计算年中第几天函数，无返回值 */ void dayofYear(struct Date *dp) int i, leap, day = dp-day; leap = ( dp-year%4 = 0 /* 计算结果回填到yearDay成员，没有return语句 */ ,2. 结构作为函数参数,42,(1) 结构或结构成员作为函数参数是值传递方式，在被调用函数dayofYear中必须用return语句返回结果。 如果不用return语句，写成“d.yearDay = day;”，主函数不能获得函数结果。因为函数的形参是函数的局部变量，函数调用时，将结构date的各成员值依次送给形参d的各成员中，以后函数对d作任何的改变与date无关。,对结构、结构成员与结构指针作为函数参数作一个总结,main函数调用语句 dayofYear函数 date结构（实参） d结构（形参）,43,(2) 使用结构地址或结构指针作为函数的参数，函数调用时，虽只传递结构的地址给结构指针形参，但通过该结构指针形参间接引用所指向的结构变量。因此，函数既可以引用结构指针形参所指向结构的成员，也可把计算结果存储于结构指针形参所指向结构的成员中。,对结构、结构成员与结构指针作为函数参数作一个总结,date结构,形参dp,44,将结构date作为实参传递给dayofYear函数的结构类型形参d，但计算结果是通过return day;语句返回到主函数的调用语句。 如果希望将计算的结果先保存到结构类型形参d的成员yearDay中，然后返回结构类型形参d的值，可以对函数dayofYear重新改写如下： struct Date dayofYear(struct Date d) int i, leap; d.yearDay = d.day; leap = (d.year%4 = 0 /* 返回结构类型 */ ,4. 函数返回结构类型值,45,在主函数中，调用dayofYear函数后把返回的结构赋值给结构变量date，调用语句也作相应的修改。即将 date.yearDay = dayofYear(date); 改写成 date = dayofYear(date); 调用带有结构类型形参的函数时，实参结构的各成员的值需要全部拷贝给形参结构的相应成员，费时间又费空间。一般情况下，以传递结构地址或指针为好。,4. 函数返回结构类型值,46,变量：通过变量定义引入。程序执行时，不能显式地用语句随意生成变量和消去变量。 数组：必须事先定义固定的长度（即元素个数），有时存放的数据不确定时，往往把数组定得足够大。,7.4 链表,按数据对象可能最多情况来设定变量或数组，称为静态方法。 而按需要用随时生成和消去数据对象，数据之间的关系也能由程序随时设定和改变，这种实现方法称为动态方法，如链表。,47,head：链表的“头指针”变量，存放的是地址，指向链表的第一个元素（或称表元、结点）。 链表元素：分成两部分，存放实际的数据和后继表元指针。,单向链表结构示意图,空链表示意图,1. 什么是链表,48,链表与数组相比较，主要有以下几个方面的区别： 数组的元素个数在数组定义时指定，元素个数是固定的；链表表元的存储空间是在程序执行时由程序动态向系统申请的，链表的表元个数可按需要增减。 数组的元素顺序关系由元素在数组中的下标确定，链表表元顺序关系由表元的指针实现。 在数组中插入或删除表元，要移动部分表元的存储位置。在链表中插入或删除表元，不要移动表元，仅改变表元的指针指向即可。,链表与数组的区别,49,动态数据结构中的数据对象是一种结构变量，它除有一些成员存储数据信息外，还有存储指针的成员。最简单情况是结构包含有指向与自己同样结构的指针。 例如： struct intNode /* 整数链表表元类型 */ int value ; /* 存放整数 */ intNode *next ; /* 存放后继表元的指针 */ ; 利用指针成员next，可把一个intNode类型的结构与另一个同类型的结构链接起来，用于描述动态数据结构中两数据对象之间的关系。,2. 动态变量,50,动态数据结构中的变量称为动态变量，动态变量能由程序调用库函数，显式地随意生成和释放(消去)。 在C语言中，有malloc和calloc两个库函数用于生成动态变量，另有一个库函数free用于释放动态变量。,2. 动态变量,51,格式：void *malloc(size) 功能：向系统申请size个字节的连续空间。如果申请成功，函数的返回值是指向已分配的连续空间开始地址的指针；如果因动态存储区域的内存已分配完，而不能满足这次申请要求，函数将返回0(NULL)值。 说明：由于malloc()函数的返回值是void类型（无类型）的指针值，程序需将该返回值强制转换成某种特定的指针类型。 例如： intNode *p; p = (intNode *) malloc(sizeof(intNode);,(1) malloc() 函数,52,(2) calloc() 函数,格式：void *calloc(n, size) 功能：向系统申请n块size个字节的连续空间（即n*size个字节）。如果申请成功，函数的返回值是指向已分配的连续空间的开始地址的指针；如果申请不成功，则返回NULL值。 说明：calloc()与malloc()函数一样，返回值是一个无类型的指针值，程序需将该返回值强制转换成某种特定的指针类型。函数calloc()与函数malloc()比较，除多一个参数外，在功能上，函数calloc()还给分配的空间完成清0的工作，而函数malloc()通常不另还做清0的工作,53,(2) calloc() 函数,例如：申请能存储100个整数的存储块。 int *p; p = (int *) calloc(100, sizeof(int); 也可以使用 malloc 函数实现，如： p = (int *) malloc(100 * sizeof(int); 利用上述函数返回的存储块的首地址，就能如同普通数组一样访问这存储块中100个元素，习惯称这样的数组为动态数组。 例如: 以下代码置这个动态数组的值为1至100的整数： for(int k = 0; k 100; k+) pk = k+1;,54,(3) free() 函数,格式：void free(*ptr) 功能： 释放由ptr所指向的存储块。 说明： ptr的值必须是调用函数malloc()或calloc()时的返回值，即为动态申请内存得到的一块连续存储空间的地址。,以上三个函数中，形参n和size为unsigned类型，ptr为指针类型。函数malloc()和calloc()返回的是系统分配的连续存储空间的首地址，其类型为void *，程序将这个返回值强制转换成某种指针类型后，赋值给某个指针变量，然后用这个指针变量间接引用存储空间的相应成员。,55,主要包括建立空的单链表、创建一个表元、遍历单链表、查找指定值的表元、插入一个表元、删除一个表元等。 假定存储一个学生信息的链表表元类型定义如下： struct stuS/* 学生链表表元结构类型 */ int number;/* 学号 */ char name20;/* 姓名 */ int score;/* 成绩 */ stuS *next; /* 指向后继表元的指针 */ ; stuS *head,*p,*p1,*p2; /* head是链表的头指针，其余是工作指针 */,3. 单链表上的基本操作,56,单链表的建立过程是从空链表(没有链表表元)开始，逐步插入新表元的过程。 要建立空链表首先应让“头指针”为空，即设置变量head为NULL。 例如：head = NULL; 说明：建立以head为链表头指针的空链表。,(1) 建立空链表,空链表示意图,57,假设要创建一个新的学生，该生的学号、姓名和成绩从键盘输入。程序应首先向系统申请对应该生的表元的存储空间，然后输入该生的信息存入这个表元。 例如： p=(stuS *)malloc(sizeof(stuS); /* p指向申请到的存储块 */ scanf(%d%s%d, /* 后继表元地址为空 */,(2) 创建一个表元,58,stuS *createStudent (int num, char *name, int s) /* 学生的学号、姓名和成绩 */ stuS *p = (stuS *) malloc(sizeof(stuS); p-number = num;/* 学号 */ strcpy(p-name, name); /* 姓名*/ p-score = s; /* 成绩 */ p-next = NULL; /* 后继表元地址为空 */ return p; ,【例7.4】编写创建一个学生表元的函数,59,所谓遍历链表是顺序访问链表中的表元，对各表元作某种处理。 例如，顺序输出链表各表元的数据。遍历单链表需从链表的首表元开始，沿着表元的链接顺序逐一考察链表的每个表元，直至链表结束。 假设用工作指针p遍历整个链表，p的初值应该是链表的头指针，循环条件是指针p还指向某个表元，即p不等于NULL。循环要做的工作包括输出p所指向的表元的值，和准备考察下一个表元（p = p-next实现）。,(3) 遍历链表,60,void travelStuLink(stuS *head) stuS *p = head; if(head = NULL) printf (n目前在链表中没有学生n); return; printf (n目前在链表中的学生如下n); while (p != NULL) printf(%dt%st%dn, p-number, p-name, p-score); p = p-next; /* 准备访问下一个表元 */ ,【例7.5】编写遍历学生单链表的函数,61,在链表中查找指定值的表元可能有以下几个目的： 获取该表元的详细信息； 对找到的表元进行修改； 将查到的表元删除； 在查到的表元之前插入一个新表元等。 查找分为两种： 无序链表上的查找， 有序链表上的查找。,(4) 在链表中查找表元,62,【例7.6】编写无序学生链表上的查找函数, 在无序链表上查找 从链表头指针所指的第一个表元出发，顺序查找。若发现有指定值的表元，以指向该表元的指针值为查找结果；若查找至链表末尾，未发现有指定值的表元，查找结果为NULL，表示链表中没有指定值的表元。 stuS *searchSLink(stuS *h, int num) /* h为头指针，num为要查找的学号 */ stuS *v = h;/* 工作指针v的初值是链表的头指针 */ while(v != NULL ,63, 在有序链表上查找,有序链表的表元是按值从小到大顺序链接的，在顺序查找循环中，当发现还有表元，并且该表元的值比寻找值小时，应继续查找。 反之，若不再有表元，或当前表元值不比寻找值小，则查找应结束。 查找循环结束后，仅当还有表元，并且当前表元的值与寻找值相等情况下，才算找到，函数返回当前表元的指针。否则，链表中没有要寻找的表元，函数应该返回NULL 。,64,【例7.7】编写有序学生链表上的查找函数,从链表的首表元开始，循环条件是还有表元，且表元的值小于寻找值。循环体要做的工作是准备考察下一个学生。寻找循环结束后，在有当前表元，且当前表元的值是要寻找值情况下，函数才返回当前表元的指针。否则，函数返回NULL。 stuS *searchSOLink(stuS *h, int key) /* h为头指针，key为要查找的学号 */ stuS *v = h; /* 工作指针v的初值是链表的头指针 */ while (v != NULL ,65,在链表中插入一个表元，可以插在链表的最前面（作为首表元）、最后面（作为尾表元）、也可以插在指定的表元之后。 在首表元之前插入新表元 在原来的首表元之前插入一个新表元，插入的表元将成为链表新的首表元。这个工作包括将链表原来的首表元接在新插入的表元后面，并修改链表的头指针，使链表的头指针指向新插入的表元。设指针p指向新申请到的表元地址，实现这个功能的代码如下： p-next = head; /* 新表元指向原首表元地址，使原首表元成为后继表元 */ head = p; /* 头指针指向新表元，使新表元成为首表元 */,(5) 在链表中插入新表元,66,插入新表元之前的状态,插入新表元之后的状态,执行 p-next = head;,执行 head = p;,在首表元之前插入新表元图示,67,假设： 指针w指向指定的表元（新表元插在其后） 指针p指向新表元 插入工作包含两个基本动作： a. 将原先w所指向表元的后继表元成为p所指向表元的后继表元，用代码p-next = w-next实现。 b. 将p所指的表元成为w所指表元的后继表元，用代码w-next = p实现。, 在指定的表元之后插入新表元,68,插入新表元之前的状态,插入新表元之后的状态,执行 p-next = w-next;,执行 w-next = p;,在指定的表元之后插入新表元图示,69,【例7.8】编写在学生链表中，在指定学生 之后插入一个新学生的函数,void insert(stuS *head, int num) /* num为要查找的学号 */ stuS *w=head, *p; while (w != NULL /* *p作为*w的后继表元 */ ,70,设指针p指向新表元，由以下3个操作步骤完成： a. 从头指针开始依次找到最后的表元，由指针w指向最后的表元。 b. 将指针p所指表元成为指针w所指的后继表元，用代码 w-next = p 实现。 c. 将新表元的后继表元设置为空，用代码 p-next = NULL 实现。, 在链表末尾添加新表元,71,添加新表元之前的状态,添加新表元之后的状态,NULL,执行 w-next = p;,执行 p-next = NULL;,在链表末尾添加新表元图示,NULL,72,【例7.9】编写在学生链表的末尾接上一个新学生的函数,stuS *append(stuS *head) stuS *w = head,*p; p = (stuS *)malloc(sizeof(stuS); /* p指向新申请的表元 */ printf (请输入学号、姓名、成绩：); scanf (%d%s%d, /* 返回头指针 */ ,73,要将一表元从链表中删除，首先要在链表中查找该表元。若未找到，则不用做删除工作； 在删除时还要考虑两种不同的情况： 如果删除的是首表元要修改链表头指针。 如果删除的表元不是链表的首表元，则要更改删除表元的前驱表元的后继指针。 假设指针变量p的初值指向首表元，通过循环，p依次指向下一个表元（使用p = p-next实现）；指针变量w总是指向p的前导表元（使用w = p实现）。,(6) 从链表中删除表元,74,p = head;/* 将首表元的指针保存到指针变量p */ if(p) /* 判是否为空链表 */ head = head-next; /* 让链表的头指针指向首表元的后继表元*/ p-next = NULL; /* 删除的表元脱离链表 */ , 删除单链表的首表元,删除首表元 之后状态,75,p = w-next;/* w是要删除表元的前驱表元的指针*/ w-next = p-next; /* p是要删除表元的指针 */ p-next = NULL; /* 删除的表元脱离链表 */, 删除单链表中的某表元,删除表元 之前状态,删除非首表 元之后状态,p = w-next;,w-next = p-next;,p-next = NULL;,NULL,76,【例7.10】编写在学生链表中删除 指定学号的表元的函数,stuS *delStu (stuS *head, int num)/* num为要查找的学号 */ stuS *w, *p; if (head = NULL) return NULL; p = head; /* 让p指向链表的首表元 */ while (p != NULL /* 返回头指针 */ ,77,#include #include #include struct stuS int number;/* 学号 */ char name20; /* 姓名 */ int score;/* 成绩 */ stuS *next; ;/* 其他函数应插在主函数之前 */,主函数1,78,void main() stuS *head=NULL; char *menu = 1 在链表末尾添加新表元, 2 在指定表元之后插入新表元”, 3 显示链表中所有表元,4 删除链表中指定表元,; int i, ans, number; while (1) printf(n请选择下列菜单命令：n); for( i=0; menui0!=0; i+) printf(t%sn, menui); /*显示在链表上操作的菜单 */ printf(t其他选择（非14），结束本程序运行！n); scanf(%d,主函数2,79,switch(ans) case 1: head= append (head); break; case 2: printf(请输入插入学生的学号：); scanf(%d, ,主函数3,80,【例7.11】写一个函数，输入n个整数，并按整数的输入顺序建立一个整数单链表。 算法思想： 1. 为加快新表元添加到链表的末尾，引入指向链表的末尾表元的指针变量tail； 2. 链表的初始状态为空链表，即头指针head和末尾表元指针tail都为 NULL； 3. 每输入一个大于0的整数时，向系统申请一个表元的存储空间并赋给指针变量p； 4. 将输入的整数n存入新表元并将新表元接在链表的末尾； 5. 当输入一个小于或等于0的整数时，函数运行结束并返回链表的头指针head。,4. 单链表程序设计实例,81,连接前的状态,连接后的状态,【例7.11】图示,tail = tail-next = p,82,#include #include struct intNode int value; struct intNode *next; ; /* 建立正整数链表的函数 */ struct intNode *createList( ) struct intNode *head, *tail, *p; /* 链表头尾指针 */ int n; /* 存放读入的整数 */ head = tail = NULL; /* 初始时为空链表 */ printf (请输入一个整型数据（0时运行结束）：); scanf (%d, ,【例7.11】程序,83,while ( n 0) /* 有整数读入 */ p = ( struct intNode *) malloc ( sizeof ( struct intNode); /* 申请一个表元的存储空间 */ p-value = n; /* 输入的整数存入新表元 */ p-next = NULL;/* 新表元为最后一个表元 */ if (head = NULL) head = tail = p; /* 当空链表时，新表元作为首表元 */ else tail = tail-next = p; /* 非空链表时，新表元接在链表的末尾 */ printf (请输入一个整型数据（0时运行结束）：); scanf (%d, /* 返回链表的头指针head */ ,【例7.11】程序续,84,/* 主函数 */ void main() struct intNode *p, *q; q = createList( );/* 当函数返回时，q为头指针 */ while (q) printf(%dn,q-value); /* 依次显示链表中的表元值 */ p = q-next; free(q); q = p; ,【例7.11】程序续,85,算法思想： 为程序处理方便，引入指向当前要考察的表元的指针变量v和指向当前要考察的表元前一个表元的指针变量u； 链表的初始状态为空链表，即头指针head为 NULL； 每输入一个大于0的整数时，向系统申请一个表元的存储空间并赋给指针变量p； 将输入的整数n存入新表元； 寻找新表元插入的位置：从链表的首表元开始考察，与输入的整数n比较。若n当前表元的值，则考察下一个表元；否则新表元插在当前表元之前。 当输入一个小于或等于0的整数时，函数运行结束并返回链表的头指针head。,【例7.12】编写一个函数，输入n个整数，建立一个按值从小到大顺序链接的链表,86,#include #include struct intNode int value; struct intNode *next; ; /* 建立有序的正整数链表的函数 */ struct intNode *createSortList( ) struct intNode *u, *v, *p, *head = NULL; /* u 指向上一个表元，v指向下一个表元 */ int n; printf (请输入一个整型数据（0时运行结束）：); scanf (%d, ,【例7.12】程序,87,while ( n 0) /* 有整数读入 */ p = (struct intNode *)malloc (sizeof(struct intNode); p-value = n; /* 输入的整数存入新表元 */ v = head; /* 从首表元开始考察 */ while(v != NULL /* 返回链表的头指针head */ ,【例7.12】程序续,88,/* 主函数 */ void main() struct intNode *p, *q; q = createSortList ( );/* 当函数返回时，q为头指针 */ while (q) printf(%dn,q-value); /* 依次显示链表中的表元值 */ p = q-next; free(q); q = p; ,【例7.12】程序续,89,【例7.13】实现将一个已知链表颠倒排列， 即将链头当链尾，链尾当链头。,颠倒前的状态,颠倒后的状态,90,【例7.13】链表颠倒图示,颠倒前,第1次循环,第2次循环,第3次循环,head = v2-next,v1 = v2,v2 = head,v2-next = v1,91,void reverse(intNode *h) intNode *p, *v1, *v2; v1 = NULL; /* v1指向v2前一个表元，初值指向NULL */ v2 = h-next; /* v2 指向要颠倒的表元，初值指向首表元 */ while (v2 != NULL) /* 还未颠倒完，循环 */ p = v2-next;/* p 指向v2的后继表元 */ v2-next = v1; /* v2所指表元的后继表元是v1所指表元 */ v1 = v2; /* 调整v1的指向，即指向下一个表元 */ v2 = p; /* 调整v2的指向，即指向下一个表元 */ h= v1; /* 原链表的最后一个表元变为首表元 */ return; ,【例7.13】链表颠倒函数,92,联合类型和结构类型类似，都可以定义和使用不同类型的成员数据。 但在联合类型中，所有成员是共享同一个存储空间，任一时刻只存储其中一个成员。因此，联合也被称之为共用体。 联合的目的是表达某种数据在不同时刻取不同类型的值。,7.5 联合,93,格式：union 联合类型名 成员说明表 ; 例如：union Data int ival; char chval; float fval; ; 表示：定义一个名为Data的联合类型，能存储整型、字符型或浮点型的数据。,1. 联合类型与联合变量的定义,94,在程序中如果要使用联合类型的数据，就必须定义联合变量。定义联合变量也与定义结构变量一样，可以先定义联合类型再定义联合变量，也可在定义联合类型同时定义联合变量。 例如，以上已定义了联合类型Data，再定义联合变量： union Data x, y; /*C语言句法*/ Data a, b; /C+句法,1. 联合类型与联合变量的定义,也可以联合类型与联合变量一起定义。例如： union Data int ival; char chval; float fval; u, v;,95,格式：联合变量名.成员名 例如：前面定义了联合类型Data及联合变量x、y，下面就可以正确地引用了。 x.ival/* 引用联合变量x的成员ival */ y.chval/* 引用联合变量y的成员chval */ 注意：只引用联合变量是错误的。 例如：printf(%d, x);/* 错误的引用 */ 说明：这是因为联合变量中的存储的是某个成员的值，不存储联合的所有成员。,2. 联合变量中成员的引用,96,(1) 一个联合可以存放多种不同类型的数据，但实际上只存储着其中的一种数据，而不是同时存放着多种数据。存于联合中的值是最近一次存入的值。存入新值后，原有的值就全部或部分被新值所覆盖。 例如：x.ival = 1; x.fval = 2.0; x.chval= ?; 完成以上三个赋值后，只有x.chval是有效的，而x.ival或x.fval中的值已经变成无意义的了。,使用联合变量注意1,97,(2) 联合类型变量定义时可以初始化，但只能对该变量的第一个成员置初值。 例如：Data x = 1; /* 将数值1赋给x的ival成员，注意花括号是必须的 */ 下面的写法是错误的。 Data x = 1, 2.0, ?;/* 不能同时给3个成员赋值 */,使用联合变量注意2,98,(3) 联合变量的开始地址和它的成员变量的开始地址是相同。例如， /* 给联合变量u赋一个long型值 */ 则u.s0、u.s1、u.s2、u.s3是对long类型值按照字节的分拆。,使用联合变量注意3,99,(4) 函数的形参类型不能是联合类型，函数的结果类型也不能是联合类型。但指向联合的指针可以作为函数形参，函数也可以返回指向联合的指针。 (5) 联合可出现在结构类型中，联合也可包含有结构和数组。引用结构中的联合，或联合中的结构与引用嵌套结构成员的书写形式完全一样 。,使用联合变量注意4、5,100,在某些应用中，需要标志某些对象的状态或特征。这可分别用一个机器字中的一位二进制位或连续若干二进制位代表不同属性的状态。例如，某台计算机配置的磁盘机中的控制状态寄存器的字长为16位(自右至左，第0位至第15位)。设某些位的意义如下： 第15位: 置 1 表示数据传送发生错误； 第7位 : 置 1 表示设备已准备好，可传送数据； 第6位 : 置 1 允许响应中断； 第2位 : 置 1 表示读； 第1位 : 置 1 表示写。,7.6 位域,101,实现上述要求可以给对应字中的某些二进位定义一系列表示特征的代码。如 #define ERROR 0100000 /* 对应第 15 位错误标志 */ #define READY 0200 /* 对应第 7 位准备好 */ #define IENABLE 0100 /* 对应第 6 位允许中断 */ #define READ 04 /* 对应第 2 位读 */ #define WRITE 02 /* 对应第 1 位写 */,7.6 位域,102,在编译程序处理符号表时，为了区分每个标识符的类别属性，如变量名，函数名，类型名，及全局的，静态的等。描述类别属性的最简单方法是把表示类别属性的字符或整数中的某些二进位作为标志位使用。例如： #define VARIABLE O1 /* 第 0 位表示变量名 */ #define FUNCTION 02 /* 第 1 位表示函数名 */ #define TYPE 04 /* 第 2 位表示类型名 */ #define EXTERNAL 010 /* 第 3 位表示外部的 */ #define STATICAL 020 /* 第 4 位表示静态的 */ 通常称这种表示法为字位标志法，所有的数字必定是2的若干次幂。对这些位可以进行移位、屏蔽、求补等运算，就能实现对属性值的测试，存储等。,7.6 位域,103,例1： flg = VARIABLE | EXTERNAL | STATICAL; 表示：将flg置成变量，全局，静态的。 例2： flg 表示：将flg置成非变量，非全局，非静态的。 说明：利用提供的位域机制，能直接定义和存取字中的字段。字段是机器字存储单元中的一串连续的二进位。字段的定义和存取的方法建立在结构基础上。,7.6 位域,104,struct id_atr unsigned variable :1; unsigned function :1; unsigned type :1; unsigned external :1; unsigned statical :1; ; struct id_atr flg; 说明：flg 包含五个字段，其中每个字段的长度均为1。为特别强调它们是无正负号的量，定义它们是 unsigned 型的。,7.6 位域,字段名,字段长度,105,struct ins_type unsigned op :6; /* 操作码占前 6 位 */ unsigned flg :2; /* 特征码占 2 位 */ unsigned operand1 :4; /* 第一操作数占 4 位 */ unsigned operand2 :4; /* 第二操作数占 4 位 */ instruction ; 引用字段的方法（类似于引用结构的成员）： 如：instruction.op表示引用instruction的op字段。另外，字段可以认为是一个无符号整数，像别的整数一样可出现在算术表达式中。 如：flg.variable = flg.external = flg.statical = 1;,7.6 位域,106,条件：if (flg.extermal=0 表示：测试flg的相应位是否都为0。 说明： 1. 一个字段只能在同一个整数字中，即限制字段不能跨越整数字的边界。如果剩余的位太少不够下一个字段时，下一个字段将占用下一个整