高级语言程序设计：chap08-结构体相关

《高级语言程序设计：chap08-结构体相关》由会员分享，可在线阅读，更多相关《高级语言程序设计：chap08-结构体相关（127页珍藏版）》请在金锄头文库上搜索。

1、Chap 9 结构结构 08120001081200990812000708120007 张帅帅 李美美 赵小飞 罗小花110108350108360108410108MFMF0.10500.0020.0088.20?内容内容9.1 构建手机通讯录构建手机通讯录9.2 结构变量结构变量9.3 结构数组结构数组9.4 结构指针结构指针9.5 单向链表单向链表本章要点本章要点n什么是结构？结构与数组有什么差别？什么是结构？结构与数组有什么差别？n有几种结构的定义形式，它们之间有什么不同？有几种结构的定义形式，它们之间有什么不同？n什么是结构的嵌套？什么是结构的嵌套？n什么是结构变量和结构成员变量，

2、如何引用结构成什么是结构变量和结构成员变量，如何引用结构成员变量？员变量？n结构变量如何作为函数参数使用？结构变量如何作为函数参数使用？n什么是结构数组，如何定义和使用结构数组？什么是结构数组，如何定义和使用结构数组？n什么是结构指针，它如何实现对结构分量的操作？什么是结构指针，它如何实现对结构分量的操作？n结构指针是如何作为函数的参数的？结构指针是如何作为函数的参数的？ 9.1 构建手机通讯录构建手机通讯录 9.1.1 程序解析程序解析9.1.2 结构的概念与定义结构的概念与定义9.1.3 结构的嵌套定义结构的嵌套定义9.1.1 程序解析程序解析例例9-1 构建简单的手机通讯录构建简单的手机

3、通讯录联系人的基本信息：姓名、年龄和联系电话联系人的基本信息：姓名、年龄和联系电话最多容纳最多容纳50名联系人的信息名联系人的信息 具有新建和查询功能具有新建和查询功能9.1.1 程序解析程序结构程序解析程序结构n程序结构程序结构主函数主函数main：程序的总体控制：程序的总体控制函数函数new_friend：新建联系人功能：新建联系人功能函数函数search_friend：查询联系人功能：查询联系人功能 main()new_friend()search_friend()程序解析数据类型程序解析数据类型/变量变量n数据类型数据类型/变量变量结构类型结构类型struct friends_list

4、：在程序首部定义，：在程序首部定义，其中的成员分别代表联系人的基本信息其中的成员分别代表联系人的基本信息struct friends_list char name10; /* 姓名姓名 */ int age; /* 年龄年龄 */ char telephone13; /* 联系电话联系电话 */; 结构数组结构数组friends：每个元素就是一个结构变量，：每个元素就是一个结构变量，对应一个联系人对应一个联系人struct friends_list friends50; 程序解析全局变量程序解析全局变量/函数参数函数参数全局变量全局变量Count：记录当前的联系人总数：记录当前的联系人总数 函

5、数函数new_friend和和search_friend的参数之一是的参数之一是结构数组：结构数组：void new_friend(struct friends_list friends );void search_friend(struct friends_list friends , char *name); 结构数组名作为函数实参与普通数组名作函数参数一样，结构数组名作为函数实参与普通数组名作函数参数一样，将数组首地址传递给函数形参将数组首地址传递给函数形参程序解析源程序程序解析源程序#include#include/*手机通讯录结构定义手机通讯录结构定义*/struct friends

6、_list char name10; /* 姓名姓名 */ int age; /* 年龄年龄 */ char telephone13; /* 联系电话联系电话 */; int Count = 0; /* 全局变量记录当前联系人总数全局变量记录当前联系人总数 */void new_friend(struct friends_list friends );void search_friend(struct friends_list friends , char *name);源程序源程序int main(void) int choice; char name10; struct friends_l

7、ist friends50; /* 包含包含50个人的通讯录个人的通讯录 */ do printf(手机通讯录功能选项：手机通讯录功能选项：1:新建新建 2:查询查询 0:退出退出n); printf(请选择功能：请选择功能：); scanf(%d, &choice); switch(choice) case 1: new_friend(friends); break; case 2: printf(请输入要查找的联系人名请输入要查找的联系人名:); scanf(%s, name); search_friend(friends, name); break; case 0: break; whi

8、le(choice != 0); printf(谢谢使用通讯录功能谢谢使用通讯录功能!n); return 0;源程序源程序/*新建联系人新建联系人*/void new_friend(struct friends_list friends ) struct friends_list f; if(Count = 50) printf(通讯录已满通讯录已满!n); return; printf(请输入新联系人的姓名请输入新联系人的姓名:); scanf(%s, f.name); printf(请输入新联系人的年龄请输入新联系人的年龄:); scanf(%d, &f.age); printf(请输入

9、新联系人的联系电话请输入新联系人的联系电话:); scanf(%s, f.telephone); friendsCount = f; Count+;源程序源程序/*查询联系人查询联系人*/void search_friend(struct friends_list friends , char *name) int i, flag = 0; if(Count = 0) printf(通讯录是空的通讯录是空的!n); return; for(i = 0; i Count; i+) if(strcmp(name, friendsi.name) = 0) /* 找到联系人找到联系人*/ flag=1

10、; break; if(flag) printf(姓名姓名: %st, friendsi.name); printf(年龄年龄: %dt, friendsi.age); printf(电话电话: %sn, friendsi.telephone); else printf(无此联系人无此联系人!);9.1.2 结构的概念与定义结构的概念与定义n使用结构来表示通讯录信息：使用结构来表示通讯录信息：struct friends_listname ; /*姓名姓名*/ age; /*年龄年龄*/telephone ; /*联系电话联系电话*/; n结构：结构：构造数据类型构造数据类型，把有内在联系的，

11、把有内在联系的不同类型不同类型的数据的数据统一成一个整体，使它们相互关联统一成一个整体，使它们相互关联char 10 intchar 13 结构的定义结构的定义n结构类型定义的一般形式为：结构类型定义的一般形式为： struct 结构名结构名 类型名类型名 结构成员名结构成员名1； 类型名类型名 结构成员名结构成员名2； 类型名类型名 结构成员名结构成员名n； ;结构的定义以分号结束，结构的定义以分号结束，被看作一条语句被看作一条语句 关键字关键字struct和它后面和它后面的结构名一起组成一个的结构名一起组成一个新的数据类型名新的数据类型名 结构定义示例结构定义示例定义平面坐标结构：定义平面

12、坐标结构：struct point double x; double y; 虽然虽然x、y的类型相同，也可以用数组的方式的类型相同，也可以用数组的方式表示，但采用结构体描述整体性更强，增加表示，但采用结构体描述整体性更强，增加了程序的可读性，使程序更清晰。了程序的可读性，使程序更清晰。9.1.3 结构的嵌套定义结构的嵌套定义n在实际生活中，一个较大的实体可能由多个成员在实际生活中，一个较大的实体可能由多个成员构成，而这些成员中有些又有可能是由一些更小构成，而这些成员中有些又有可能是由一些更小的成员构成的实体。的成员构成的实体。n在手机通讯录中，增加在手机通讯录中，增加“通信地址通信地址”姓名姓

13、名性别性别年龄年龄 通信地址通信地址联系联系电话电话电子电子邮箱邮箱城市城市街道街道门牌号门牌号邮编邮编结构的嵌套定义结构的嵌套定义struct address char city10; char street20; int code; int zip;struct nest_friendslist char name10; int age; struct address addr; char telephone13; nest_friend;在定义嵌套的结构类型时，必须先定义在定义嵌套的结构类型时，必须先定义成员的结构类型，再定义主结构类型。成员的结构类型，再定义主结构类型。 姓名姓名性别性

14、别年龄年龄 通信地址通信地址联系联系电话电话电子电子邮箱邮箱城市城市街道街道门牌号门牌号邮编邮编9.2 结构变量结构变量 9.2.1 结构变量的定义和初始化结构变量的定义和初始化9.2.2 结构变量的使用结构变量的使用9.2.1结构变量的定义和初始化结构变量的定义和初始化三种定义结构变量的方式：三种定义结构变量的方式： 1.单独定义单独定义先定义先定义结构类型结构类型，再定义具有这种，再定义具有这种结构类型的变结构类型的变量量 struct friends_list char name10; /* 姓名姓名 */ int age; /* 年龄年龄 */ char telephone13; /*

15、 联系电话联系电话 */; struct friends_list friend1, friend2;结构变量的定义结构变量的定义2. 混合定义混合定义在定义结构体类型的同时定义结构体变量在定义结构体类型的同时定义结构体变量 struct friends_listchar name10; int age; char telephone13; friend1, friend2; 3. 无类型名定义无类型名定义在定义结构体变量时省略结构体名在定义结构体变量时省略结构体名struct char name10; int age; char telephone13; friend1, friend2;

16、1. 自定义类型（自定义类型（typedef）：）：将将C语言中的已有类型（包括已定义过的自定语言中的已有类型（包括已定义过的自定义类型）重新命名义类型）重新命名新的名称可以代替已有数据类型新的名称可以代替已有数据类型常用于简化对复杂数据类型定义的描述常用于简化对复杂数据类型定义的描述typedef ;自定义类型（自定义类型（typedef）typedef ;typedef int INTEGER; int i, j; INTEGER i, j; typedef int* POINT; int* p1; POINT p1; 自定义类型（自定义类型（typedef）的使用方法）的使用方法定义变量

17、定义变量 int i变量名变量名新类型名新类型名 int INTEGER加上加上 typedef typedef int INTEGER用新类型名定义变量用新类型名定义变量 INTEGER i;int num10int NUM10typedef int NUM10NUM a int a10struct friends_list char name10; int age; char telephone13; ; struct friends_list friend1, friend2;typedef struct friends_list Fri_list; Fri_list friend1,

18、friend2;结构变量的初始化结构变量的初始化 struct friends_list friend1 = Zhang, 26, 0571-85171880 ;name age telephone Zhang260571-852718809.2.2 结构变量的使用结构变量的使用1. 结构变量成员的引用结构变量成员的引用结构变量名结构变量名 .结构成员名结构成员名friend1.age = 26;strcpy(friend1.name, Zhang San); nest_friend.addr.zip例例9-2 计算实发工资计算实发工资在一个职工工资管理系统中，在一个职工工资管理系统中，工资项

19、目包括编号、姓工资项目包括编号、姓名、基本工资、奖金、保险、实发工资名、基本工资、奖金、保险、实发工资。输入一个正整数输入一个正整数n，再输入，再输入n个职工的前个职工的前5项信息，计项信息，计算并输出每位职工的实发工资。算并输出每位职工的实发工资。实发工资实发工资 = 基本工资基本工资+奖金奖金保险。保险。上课练习：结构体类型的定义以及上课练习：结构体类型的定义以及结构体变量的定义结构体变量的定义例例9-2 源程序源程序#includestruct employee int num; char name20; float jbgz, jj, bx, sfgz;int main(void) i

20、nt i, n; struct employee e; printf(请输入职工人数请输入职工人数n: ); scanf(%d, &n); for(i = 1; i = n; i+) printf(请输入第请输入第%d个职工的信息个职工的信息: , i); scanf(%d%s, &e.num, e.name); scanf(%f%f%f, &e.jbgz, &e.jj, &e.bx); e.sfgz = e.jbgz + e.jj - e.bx; printf(编号编号:%d 姓名姓名:%s实发工资实发工资:%.2fn, e.num, e.name, e.sfgz); return 0;请输

21、入职工人数请输入职工人数n: 1请输入第请输入第1个职工的信息：个职工的信息：102 Zhong 2200.5 800 85.2编号编号:102 姓名姓名:Zhong 实发工资实发工资:2915.30 结构变量的使用整体赋值结构变量的使用整体赋值2. 结构变量的整体赋值结构变量的整体赋值具有相同类型的结构变量可以直接赋值。具有相同类型的结构变量可以直接赋值。将赋值符号右边结构变量的每一个成员的值都赋给了左边将赋值符号右边结构变量的每一个成员的值都赋给了左边结构变量中相应的成员。结构变量中相应的成员。 struct friends_list char name10; int age; char

22、telephone13; friend1 = Zhang,26, “0571-85271880”, friend2;friend2 = friend1;练习练习:结构变量的使用函数参数结构变量的使用函数参数3. 结构变量作为函数参数结构变量作为函数参数如果在函数间传递结构数据，则需用结构变量作如果在函数间传递结构数据，则需用结构变量作为函数的参数或返回值。为函数的参数或返回值。例例9-3 结构变量做为函数参数结构变量做为函数参数改写例改写例9-2，要求使用，要求使用结构变量结构变量作为函数参数。作为函数参数。n定义一个用于计算实发工资的函数：定义一个用于计算实发工资的函数： float cou

23、nt_sfgz(struct employee m) return m.jbgz + m.jj - m.bx; n再将主函数再将主函数main中的语句：中的语句： e.sfgz = e.jbgz + e.jj - e.bx; 改为：改为： e.sfgz = count_sfgz(e);void count_sfgz(struct employee m) m.sfgz = m.jbgz + m.jj - m.bx; int main(void) struct employee e; count_sfgz(e)emm.sfgzstruct employee count_sfgz(struct em

24、ployee m) struct employee tmp;tmp=m;tmp.sfgz = tmp.jbgz + tmp.jj - tmp.bx;return tmp; int main(void) struct employee e; count_sfgz(e)emtmp.sfgzn一个结构变量只能表示一个实体的信息，一个结构变量只能表示一个实体的信息，如果有许多相同类型的实体，就需要使用如果有许多相同类型的实体，就需要使用结构数组。结构数组。n结构数组是结构与数组的结合，与普通数结构数组是结构与数组的结合，与普通数组的不同之处在于每个数组元素都是一个组的不同之处在于每个数组元素都是一个结

25、构类型的数据，包括各个成员项。结构类型的数据，包括各个成员项。 9.3 结构数组结构数组 n结构数组的定义方法与结构变量相同结构数组的定义方法与结构变量相同 struct friends_list char name10; int age; char telephone13; friends10; 结构数组结构数组friends，它有，它有10个数组元素，从个数组元素，从friends0到到friends9，每个数组元素都是结，每个数组元素都是结构类型构类型struct friends_list9.3 结构数组结构数组 结构数组的初始化结构数组的初始化 struct friends_list

26、friends10 = zhang san, 26, 0571-85271880, Li Si, 30, 13605732436 ; friends91360573243630Li Sifriends10571-8527188026Zhang Sanfriends0结构数组元素结构数组元素 n结构数组元素的成员引用结构数组元素的成员引用结构体数组名结构体数组名下标下标 . 结构体成员名结构体成员名 n使用方法与同类型的变量完全相同使用方法与同类型的变量完全相同friends5.age = 26;strcpy(friends5.name,Zhang San);friends4 = friends

27、1;friends91360573243630Li Sifriends10571-8527188026Zhang Sanfriends0例例9-4 结构数组排序结构数组排序 输入并保存输入并保存10个学生的信息，计算并输出平均个学生的信息，计算并输出平均分，再按照从高分到低分的顺序输出他们分，再按照从高分到低分的顺序输出他们的信息。的信息。 #include struct student int num; char name20; int score; struct student stud10; /* 定义结构数组定义结构数组 */选择排序法选择排序法int SelectiveSort(st

28、ruct student narr, int nLen)int nStartPos, nCurPos, nMinPos;struct student nTemp;/nStartPos:无序元素起点，无序元素起点，nCurPos:选择过程中的当前元素，选择过程中的当前元素，/nMinPos:当前轮次最小元素所在位置，当前轮次最小元素所在位置，nTemp:临时变量临时变量if (NULL = narr) | (nLen 0) return -1;/合法性检查合法性检查for (nStartPos = 0; nStartPos nLen - 1; nStartPos+)/开始排序开始排序nMinPo

29、s = nStartPos;for (nCurPos = nStartPos + 1; nCurPos nLen; nCurPos+)if (narrnCurPos.score narrnMinPos.score)nMinPos = nCurPos;if (nMinPos != nStartPos) /交换位置交换位置nTemp = narrnStartPos;narrnStartPos = narrnMinPos;narrnMinPos = nTemp;return 0;例例9-4 源程序源程序int main(void) int i, sum = 0; struct student stu

30、dN; /* 定义结构数组定义结构数组 */ printf( 输入输入10个学生的记录，并累加成绩个学生的记录，并累加成绩 n); for(i = 0; i N; i+)scanf(%d%s%d, &studi.num, studi.name, &studi.score); sum = sum + studi.score; printf( 输出排序前信息输出排序前信息n);for(i = 0; i N; i+) printf(No %dt%st%dn, studi.num, studi.name, studi.score); printf( 按照分数从低到高排序，使用选择排序法按照分数从低到高

31、排序，使用选择排序法n); SelectiveSort(stud, N); printf( 输出排序后信息输出排序后信息n);for(i = 0; i ”访问指针指向的结构成员。访问指针指向的结构成员。p-age = 36;当当p = &friend1时，以下三条语句相同：时，以下三条语句相同： friend1.age = 36; (*p).age = 36; p-age = 36;9.4.2 结构指针作为函数参数结构指针作为函数参数例例9-5 输输入入10个个学学生生的的学学号号、姓姓名名和和成成绩绩，输输出学生的成绩等级和不及格人数。出学生的成绩等级和不及格人数。每个学生的记录包括学号、姓

32、名、成绩和等级每个学生的记录包括学号、姓名、成绩和等级要要求求定定义义和和调调用用函函数数set_grade根根据据学学生生成成绩绩设设置置等等级级，并统计不及格人数并统计不及格人数等级设置：等级设置：A ：85100；B：7084；C：6069；D：059例例9-5 源程序源程序#define N 10struct student int num; char name20; int score; char grade;int main(void) struct student stuN, *ptr; ptr = stu; /* 输入输入 略略 */ count = set_grade( pt

33、r ); int set_grade(struct student * p) int i, n = 0; for(i = 0; i score = 85) p-grade = A; else if(p-score = 70) p-grade = B; else if(p-score = 60) p-grade = C; else p-grade = D; n+; return n;调用调用set_grade返回主函数后，主函数中结返回主函数后，主函数中结构数组构数组stu的元素的的元素的grade成员已经被赋值成员已经被赋值 例例9-1 说明说明n例例9-1中中，结结构构数数组组名名frien

34、ds作作为为函函数数参参数数时时，其其实实质质就就是是结结构构指指针针作作为为函函数数参参数数，因因为为数数组组名名代代表表数数组组的的首首地地址址。因因此此，结结构构数数组组名名与与结结构构指指针针变变量量都都可以做为函数的参数。可以做为函数的参数。 n函数返回值的类型函数返回值的类型整型、字符型、浮点型、结构类型整型、字符型、浮点型、结构类型指针（返回一个地址）指针（返回一个地址）n函数的定义、调用方法与其他函数一样函数的定义、调用方法与其他函数一样9.5 指针作为函数的返回值指针作为函数的返回值指针作为函数的返回值例指针作为函数的返回值例9-8输入一个字符串和一个字符，如果该字符在字符串

35、中，输入一个字符串和一个字符，如果该字符在字符串中，就从该字符首次出现的位置开始输出字符串中的字就从该字符首次出现的位置开始输出字符串中的字符。符。要求定义函数要求定义函数match(s, ch)，在字符串，在字符串s中查找字符中查找字符ch，如果找到，返回第一次找到的该字符在字符串，如果找到，返回第一次找到的该字符在字符串中的位置（地址）；否则，返回空指针中的位置（地址）；否则，返回空指针NULL。 例如，输入字符例如，输入字符r和字符串和字符串program后，输出后，输出rogram。例例9-8 源程序源程序#include char *match(char *s, char ch) w

36、hile(*s != 0) if(*s = ch) return(s); /* 若找到字符若找到字符ch，返回相应的地址，返回相应的地址 */ else s+; return(NULL); /* 没有找到没有找到ch，返回空指针，返回空指针 */int main(void ) char ch, str80, *p = NULL; printf(“Please Input the string:n”); scanf(%s, str); getchar( ); ch = getchar( ); if( ( p = match(str, ch) ) != NULL ) printf(%sn, p);

37、 else printf(Not Foundn); return 0;Please Input the string:University vversity字符指针字符指针p接收接收match返回的返回的地址，从地址，从p指向的存储单元开指向的存储单元开始，连续输出其中的内容，直始，连续输出其中的内容，直至至0为止。为止。 Please Input the string:school aNot Foundmain()char ch, str80, *p = NULL; p = match(str, ch)printf(%sn, p);char *match(char *s, char ch)r

38、eturn s;ABCDE0strSch DchDp9.5-2 解密藏头诗解密藏头诗 例例9-9 输输入入一一首首藏藏头头诗诗（假假设设只只有有4句句），输输出出其真实含义。其真实含义。藏藏头头诗诗：将将这这首首诗诗每每一一句句的的第第一一个个字字连连起起来来，所所组组成的内容就是该诗的真正含义。成的内容就是该诗的真正含义。藏头诗藏头诗一叶轻舟向东流，一叶轻舟向东流，帆梢轻握杨柳手，帆梢轻握杨柳手，风纤碧波微起舞，风纤碧波微起舞，顺水任从雅客悠。顺水任从雅客悠。一一 帆帆 风风 顺顺char * change(char s 20, char t )一叶轻舟向东流，一叶轻舟向东流，帆梢轻握杨柳手

39、，帆梢轻握杨柳手，风纤碧波微起舞，风纤碧波微起舞，顺水任从雅客悠。顺水任从雅客悠。一一 帆帆 风风 顺顺0st获取头字的函数获取头字的函数二维数组的初始化二维数组的初始化n若初始化给出了全部元素值，第一下标的若初始化给出了全部元素值，第一下标的元素个数可以不写（可根据初始化表示算元素个数可以不写（可根据初始化表示算出）。出）。int a2 = 1,2,3,4,5,6;int b2 = 1, 2, 3, 4, 5, 6;57二维数组的在内存中排列方式二维数组的在内存中排列方式nC在内存中排放数组的原则在内存中排放数组的原则一维数组元素连续存放一维数组元素连续存放多维数组同样依次存放成员数组。多维

40、数组同样依次存放成员数组。成员数组按同样方式表示。成员数组按同样方式表示。nC的数组存放方式，一行（成员数组）元素连续的数组存放方式，一行（成员数组）元素连续存，这种形式又称按行方式或存，这种形式又称按行方式或行优先行优先方式。方式。58行列优先顺序与内存中的排列行列优先顺序与内存中的排列a00a01a02a03a10a11a12a13a20a21a22a23int a34;a00a01a02a03a10a11a12a13a20a21a22a23 0 1 2 3 4 5 6 7 11按照行优先顺序在内存中存储a的开始位置也是其首成员a0的开始位置，也是a0首成员a00的位置。9.5-2 程序解

41、析程序解析#include char *change(char s 20, char t );int main(void) int i; char s420, t10, *p; printf(“请输入藏头诗：请输入藏头诗：n”); for(i = 0; i 4; i+) scanf(%s, si); p = change(s, t); printf(%sn, p); return 0;请输入藏头诗：请输入藏头诗：一叶轻舟向东流，一叶轻舟向东流，帆梢轻握杨柳手，帆梢轻握杨柳手，风纤碧波微起舞，风纤碧波微起舞，顺水任从雅客悠。顺水任从雅客悠。一帆风顺一帆风顺char * change(char s

42、 20, char t ) int i; for(i= 0; i 4; i+) t2*i = si0; t2*i+1 = si1; t2*i = 0; return t;函数的返回值函数的返回值是字符指针是字符指针printf(%sn, change(s, t) );或或change(s, t);printf(%sn, t);main()char s420, t10, *p;p = change(s, t);printf(%sn, p);char * change(char s 20,char t )return t;一叶轻舟向东流，一叶轻舟向东流，帆梢轻握杨柳手，帆梢轻握杨柳手，风纤碧波微起

43、舞，风纤碧波微起舞，顺水任从雅客悠。顺水任从雅客悠。SSt一一帆帆风风顺顺0tp一一帆帆风风顺顺0指针作为函数的返回值的进一步讨论指针作为函数的返回值的进一步讨论n函数返回值的类型函数返回值的类型整型、字符型、浮点型、结构类型整型、字符型、浮点型、结构类型指针（返回一个地址）指针（返回一个地址）n函数的定义、调用方法与其他函数一样函数的定义、调用方法与其他函数一样n进一步讨论进一步讨论定义函数时，可以：定义函数时，可以：n动态分配内存动态分配内存n操作这些新分配的单元操作这些新分配的单元n返回新分配单元的地址返回新分配单元的地址 修改例修改例9-99-9，采用动态，采用动态分配内存的方法分配内

44、存的方法例例9-9 修改动态分配内存修改动态分配内存#include #include char *change_d(char s 20);int main(void) int i; char s420, *p = NULL; printf(请输入藏头诗：请输入藏头诗：n); for(i = 0; i 4; i+) scanf(%s, si); p = change_d(s); printf(%sn, p); free(p); return 0;char * change_d(char s 20) int i; char *head, *p; p = (char *) calloc(9, si

45、zeof(char); head = p; for(i= 0; i MAXLEN) return -1; if (nPos nLen - 1) return -2; for (i = nLen; i nPos; i-) arri = arri - 1; /逐个后移逐个后移 arrnPos = nValue;数组元素删除程序示例数组元素删除程序示例int DeleteAt(int arr, int nPos) int i; if (nPos = nLen) return -1; for (i = nPos; i nLen 1; i+) arri = arri + 1; /逐个前移逐个前移 ret

46、urn nPos;void main()struct dblBuffer a;a.nLen=10;int loc = 3;int i;for(i=0; ia.nLen; i+)scanf(%d, &(a.darri);printf(Before Delete:n);for(i=0; ia.nLen; i+)printf(%dt, a.darri);printf(n);a=DeleteAt(a, loc);printf(After Delete:n);for(i=0; ia.nLen; i+)printf(%dt, a.darri);struct dblBuffer int darr10; in

47、t nLen;struct dblBuffer DeleteAt(struct dblBuffer arr, int nPos) int i; for (i= nPos;iarr.nLen-1;i+) arr.darri = arr.darri + 1; /逐个前移逐个前移 arr.nLen=arr.nLen-1; return arr;链接结构链接结构n采用链式数据结构采用链式数据结构一环扣一环，通过一个元素保存的其它元素的地址找一环扣一环，通过一个元素保存的其它元素的地址找到其它元素。到其它元素。n通过链接结构实现动态数据通过链接结构实现动态数据增加元素：在铁链的某个位置加一铁环增加元素：

48、在铁链的某个位置加一铁环删除元素：去掉铁链的某一铁环删除元素：去掉铁链的某一铁环n问题问题铁链中的每一铁环是一样的吗？铁链中的每一铁环是一样的吗？普通的铁链是单向的还是双向的？普通的铁链是单向的还是双向的？有没有一些特殊的铁链，比如有多个分叉的？有没有一些特殊的铁链，比如有多个分叉的？铁链的头部可以拴在柱子上吗？铁链的头部可以拴在柱子上吗？链接结构实现原理链接结构实现原理n链接结构中的元素需要保存的信息链接结构中的元素需要保存的信息与结点本身有关的信息与结点本身有关的信息找到其它元素所需要的信息找到其它元素所需要的信息n这些信息可以组织成结构这些信息可以组织成结构n问题：如何找到其它元素？问题

49、：如何找到其它元素？保存其它元素在内存中的地址保存其它元素在内存中的地址在结构中设置指针分量，用来保存其它元素的地址的在结构中设置指针分量，用来保存其它元素的地址的分量指针分量分量指针分量n问题：指针的类型？问题：指针的类型？需要指向元素的结构类型的指针类型需要指向元素的结构类型的指针类型如果需要指向的元素与本元素的类型相同的话，则需如果需要指向的元素与本元素的类型相同的话，则需要定义自引用的结构类型。要定义自引用的结构类型。链接结构链接结构n一个结构元素可以通过指针引用同类或不一个结构元素可以通过指针引用同类或不同类的结构元素，多个结构元素通过指针同类的结构元素，多个结构元素通过指针建立联系

50、。建立联系。n指向结构的指针称为链接，形成的复杂数指向结构的指针称为链接，形成的复杂数据结构称为链接结构据结构称为链接结构n最简单的链接结构最简单的链接结构线性链接形成的表，线性链接形成的表，链接表链接表。每个自引用结构有一个链接指针分量。每个自引用结构有一个链接指针分量。最简单的链接结构：单向链表最简单的链接结构：单向链表n单向链接表就像链条，自引用结构是链表中单向链接表就像链条，自引用结构是链表中的一个链节，称为链表结点，结点间由指针的一个链节，称为链表结点，结点间由指针连接形成整个结构。连接形成整个结构。n所有结点（结构）由动态分配创建。所有结点（结构）由动态分配创建。n从指向表首结点的

51、指针出发，沿链接可顺序从指向表首结点的指针出发，沿链接可顺序访问表中各结点。该指针代表整个表。通常访问表中各结点。该指针代表整个表。通常把最后结点的指针置空表示结束。把最后结点的指针置空表示结束。更复杂的引用链接结构更复杂的引用链接结构单向链表结构示例单向链表结构示例struct UserAccount char UserNO15; char Name20; char ID19; char Gender; double Balance;struct UserAccount *pNextUser;用来保存下一个结点的地址此处改成如下形式是否可行，为什么？struct UserAccount Ne

52、xtUser;#include struct UserAccount char UserNO15; char Name20; char ID19; char Gender; double Balance;struct UserAccount *pNextUser;void main() int i, j, k;i=sizeof(int *);j=sizeof(double *);k=sizeof(struct UserAccount *);printf(i=%d,t j=%d,t k=%dn, i, j, k); 普通单向链表示意图普通单向链表示意图08120001 张帅帅110108M0.1

53、008120002 赵小飞360108M20.0008120007 罗小花410108F88.2008120099 李美美350108F500.00NULLHeadTail例，需求例，需求n设有某系统的用户信息结构体，其中设有某系统的用户信息结构体，其中用户用户ID长度为长度为10用户姓名长度不超过用户姓名长度不超过10n需要处理的用户数据需要处理的用户数据不定不定，n假设某程序需要以链表方式处理用户的数假设某程序需要以链表方式处理用户的数据据普通单向链表示意普通单向链表示意DataDataDataDataNULLHeadTail链表结点结构声明链表结点结构声明方法方法1:struct Use

54、rInfoNodechar szID11;/IDchar szName11;/姓名姓名 struct UserInfoNode *pNextUser; /下个用户指针下个用户指针;方法方法2：typedef struct UserInfoNode USERNODE, *USERPOINTER;/typedef struct UserInfoNode USERNODE;/typedef struct UserInfoNode* USERPOINTER;struct UserInfoNodechar szID11;/IDchar szName11;/姓名姓名 USERPOINTER pNextUs

55、er;/下个用下个用户指指针;更好的方法更好的方法,更常见合理的声明方法更常见合理的声明方法/用户基本信息结构声明用户基本信息结构声明struct UserInfochar szID11;/ID，11个字符个字符char szName11;/姓名，姓名，11个字符个字符;或或typedef structchar szID11;/ID，11个字符个字符char szName11;/姓名，姓名，11个字符个字符 USERINFO;基本信息单独说明基本信息单独说明方法方法3：struct UserLinkNode struct UserInfo Data; /数据数据 struct UserLink

56、Node *pNextUser; /;或或typedef struct USERINFO Data;/数据结点数据结点 struct UserLinkNode *pNextUser; / USERLINKNODE ;增加一个链表描述信息结点增加一个链表描述信息结点NumberHeadTailDataDataDataDataNULLLinkInfoNoden关于链表整体描述信息结点关于链表整体描述信息结点struct UserInfo UserInfoArr100;描述整体信息结点说明示例描述整体信息结点说明示例struct UserLinkstruct UserLinkNode *pHead;

57、 /头指针头指针 struct UserLinkNode *pTail; /尾指针尾指针int nNumber;/链表中的结点计数链表中的结点计数;或或typedef struct USERLINKNODE *pHead; /头指针头指针 USERLINKNODE *pTail; /尾指针尾指针int nNumber;/链表中的结点计数链表中的结点计数 USERLINK;可以增加一个不用的头结点可以增加一个不用的头结点NumberHeadTailDataDataDataNULLLinkInfoNoden目的在于写程序方便，简化一些链表操作，目的在于写程序方便，简化一些链表操作，数据结构数据结构

58、课程中会有进一步的阐述课程中会有进一步的阐述不用的头结点关于后面的操作的假定关于后面的操作的假定n链表为单向链表链表为单向链表n没有设置空的头结点没有设置空的头结点n设置有信息描述结点，记录如下信息设置有信息描述结点，记录如下信息头结点头结点尾结点尾结点链表中结点个数链表中结点个数在链表中增加一个节点在链表中增加一个节点n有几种增加方式有几种增加方式将新结点作为最后一个元素增加到链表的尾部，将新结点作为最后一个元素增加到链表的尾部，将新结点作为第一个元素增加到链表的头部将新结点作为第一个元素增加到链表的头部将新结点按照某种次序要求插入到指定位置将新结点按照某种次序要求插入到指定位置加到尾部加到

59、尾部n如果链表为空，则需要做一些初始化工作，如果链表为空，则需要做一些初始化工作，将新的结点当成头结点和尾结点将新的结点当成头结点和尾结点n如果链表不为空，则将该结点作为尾结点如果链表不为空，则将该结点作为尾结点的下一个结点，修改尾结点指针。的下一个结点，修改尾结点指针。如果没有记录尾结点指针，则需要从头结点开如果没有记录尾结点指针，则需要从头结点开始找到最后一个结点。始找到最后一个结点。pHeadpTailDataDataNULLpNewNode NULL 示例代码，加到尾部示例代码，加到尾部int AddUserToTail( struct UserLink *pUsers, /链表描述信

60、息指针链表描述信息指针 struct UserLinkNode *pNewUser/新结点指针新结点指针) if (pUsers = NULL | pNewUser = NULL) return -1;if (pUsers-nNumber pHead = pNewUser; pUsers-pTail = pUsers-pHead; /头尾指针指向同一个结点头尾指针指向同一个结点 else/把结点信息附到链表尾部把结点信息附到链表尾部 pUsers-pTail-pNext = pNewUser; /加到尾到加到尾到 pUsers-pTail = pNewUser;/修改尾结点指针修改尾结点指针

61、pUsers-pTail-pNext = NULL;/最后一个结点的后继置空最后一个结点的后继置空pUsers-nNumber+;/计数加计数加1return 0;加到头部加到头部n如果链表为空，则需要做一些初始化工作，如果链表为空，则需要做一些初始化工作，将新的结点当成头结点和尾结点将新的结点当成头结点和尾结点n如果链表不为空，需要将新结点的下一个如果链表不为空，需要将新结点的下一个结点置为原来的头结点，并把新结点作为结点置为原来的头结点，并把新结点作为头结点头结点pHeadpTailDataDataNULLNULLpNewNode 示例代码，加到头部示例代码，加到头部int AddUser

62、ToHead( struct UserLink *pUsers, /链表描述信息指针链表描述信息指针 struct UserLinkNode *pNewUser/新结点指针新结点指针) if (pUsers = NULL | pNewUser = NULL) return -1;if (pUsers-nNumber pHead = pNewUser; pUsers-pTail = pUsers-pHead; /头尾指针指向同一个结点头尾指针指向同一个结点 pNewUser-pNext = NULL; else/把结点信息附到链表头部把结点信息附到链表头部 pNewUser-pNext = pU

63、sers-pHead ; /加到头部加到头部 pUsers-pHead = pNewUser;/修改头结点指针修改头结点指针 pUsers-nNumber+;/计数加计数加1return 0;在链表中插入一个新结点在链表中插入一个新结点head numnamenext1201aaanumnamenext1203cccnumnamenext1202bbbnumnamenext1208kkks ptr s-next = ptr-nextptr-next = s先连后断先连后断在在ptr后插入节点后插入节点s去除链表中的某个结点去除链表中的某个结点head numnext120112031202pr

64、e p=pre-nextpre-next=p-nextfree(p)先接后删先接后删1204p 删除节点删除节点p遍历链表遍历链表n常见功能常见功能遍历链表逐个访问所有结点，进行相应的处理，遍历链表逐个访问所有结点，进行相应的处理，如将所有用户的某项指标求和，输出所有用户如将所有用户的某项指标求和，输出所有用户的信息的信息查找某个或某些符合给定条件的结点，进行相查找某个或某些符合给定条件的结点，进行相应处理应处理示例代码示例代码: 输出所有元素输出所有元素int ShowData(struct UserLink *pUsers)struct UserLinkNode *pNode;if (pU

65、sers-nNumber pHead; /从第一个元素开始从第一个元素开始 pNode != NULL; /判断当前结点是否为空判断当前结点是否为空pNode = pNode-pNext /准备处理下一个结点准备处理下一个结点 ) /对每个结点出输出信息对每个结点出输出信息printf( %11st%11stn,pNode-Data.szID,pNode-Data.szName,return 0;9.5 学生信息管理的链表实现学生信息管理的链表实现 9.5.1 程序解析程序解析9.5.2 链表的概念链表的概念9.5.3 单向链表的常用操作单向链表的常用操作9.5.1 程序解析程序解析例例9-1

66、1 建建立立一一个个学学生生成成绩绩信信息息（包包括括学学号号、姓姓名名、成成绩绩）的的单单向向链链表表，学学生生记记录录按按学学号号由由小小到到大大顺顺序序排排列列，要要求求实实现现对对成成绩绩信信息息的的插插入入、修修改改、删删除和遍历操作。除和遍历操作。mainInsertDocDeleteDocPrint_Stu_Doc head9905 Qian 80 NULL9901 Wang 809902 Li 90例例9-11 数据定义与函数声明数据定义与函数声明 struct stud_node /*链表结点类型链表结点类型*/ int num; char name20; int score

67、; struct stud_node *next; struct StudLinkstruct stud_node *pHead; /头指针头指针 struct stud_node *pTail; /尾指针尾指针int nNumber; /链表中的结点计数链表中的结点计数;struct StudLink InsertDoc(struct StudLink Link, struct stud_node *stud); /* 插入插入 */struct StudLink DeleteDoc(struct StudLink Link, int num); /* 删除删除 */void Print_S

68、tu_Doc(struct StudLink Link); /* 遍历遍历 */9.5.2 链表的概念链表的概念n一种一种动态存储动态存储分布的数据结构分布的数据结构n若干个同一结构类型的若干个同一结构类型的“结点结点”依次串接而依次串接而成成n单向链表单向链表、双向链表、双向链表 头指针头指针结点结点尾结点尾结点head9903 Qian 80 NULL9901 Wang 809902 Li 90链表的概念结点定义链表的概念结点定义head9905 Qian 80 NULL9901 Wang 809902 Li 90void Print_Stu_Doc(struct StudLink Lin

69、k) struct stud_node *ptr; if(Link.pHead = NULL) printf(nNo Recordsn); return; printf(nThe Students Records Are: n); printf(NumtNametScoren); for(ptr = Link.pHead; ptr!=NULL; ptr = ptr-next) printf(%dt%st%dn, ptr-num, ptr-name, ptr-score);void main()struct StudLink Link;struct stud_node *p1, *p2, *p3

70、;int size;size = sizeof(struct stud_node);p1 = (struct stud_node *) malloc(size);p2 = (struct stud_node *) malloc(size);p3 = (struct stud_node *) malloc(size);scanf(%d%s%d, &(p1-num), p1-name, &(p1-score);scanf(%d%s%d, &(p2-num), p2-name, &(p2-score);scanf(%d%s%d, &(p3-num), p3-name, &(p3-score);p1-

71、next = p2; p2-next = p3;p3-next = NULL;Link.pHead = p1; Link.pTail = p3;Print_Stu_Doc(Link); Link0-2.cppvoid main()struct StudLink Link;struct stud_node s1, s2, s3;scanf(%d%s%d, &(s1.num), s1.name, &(s1.score);scanf(%d%s%d, &(s2.num), s2.name, &(s2.score);scanf(%d%s%d, &(s3.num), s3.name, &(s3.score

72、);s1.next = &s2; s2.next = &s3;s3.next = NULL;Link.pHead = &s1; Link.pTail = &s3;Print_Stu_Doc(Link); Link0-1.cpp链表的概念与数组比较链表的概念与数组比较n数组数组事先定义固定长度的数组事先定义固定长度的数组在数组元素个数不确定时，可能会发生浪费内存在数组元素个数不确定时，可能会发生浪费内存空间的情况空间的情况 n链表链表动态存储分配的数据结构动态存储分配的数据结构根据需要动态开辟内存空间，比较方便地插入新根据需要动态开辟内存空间，比较方便地插入新元素（结点）元素（结点）使用链表可以

73、使用链表可以节省内存节省内存，提高操作效率，提高操作效率 动态存储分配函数动态存储分配函数malloc()void *malloc(unsigned size) 在内存的动态存储区中分配一连续空间，其长度为在内存的动态存储区中分配一连续空间，其长度为size若申请成功，则返回一个指向所分配内存空间的起若申请成功，则返回一个指向所分配内存空间的起始地址的指针始地址的指针若申请不成功，则返回若申请不成功，则返回NULL（值为值为0）返回值类型：返回值类型：(void *)n通用指针的一个重要用途通用指针的一个重要用途n将将malloc的返回值转换到特定指针类型，赋给一个指针的返回值转换到特定指针类

74、型，赋给一个指针 malloc()示例示例int *ip = (int *) malloc( sizeof(int) )struct student * p;p = (struct student *) malloc(sizeof(struct student);n调用调用malloc时，用时，用 sizeof 计算存储块大小计算存储块大小n虽然存储块是动态分配的，但它的大小在分配后也是虽然存储块是动态分配的，但它的大小在分配后也是确定的，不要越界使用。确定的，不要越界使用。 p动态存储释放函数动态存储释放函数free 当某个动态分配的存储块不再用时，要及时当某个动态分配的存储块不再用时，要及

75、时将它释放将它释放void free(void *ptr) 释放由动态存储分配函数申请到的整块内存空间，释放由动态存储分配函数申请到的整块内存空间，ptr为指向要释放空间的首地址。为指向要释放空间的首地址。free(ip);free(p); p9.5.3 单向链表的常用操作单向链表的常用操作1. 链表的建立链表的建立2. 链表的遍历链表的遍历3. 插入结点插入结点4. 删除结点删除结点1.链表的建立链表的建立struct StudLink Create_Stu_Doc()struct StudLink Link;Link.pHead = Link.pTail = NULL;return Lin

76、k;Link1.cpp 或Link.cpp1.链表的建立链表的建立size = sizeof(struct stud_node);p = (struct stud_node *) malloc(size);链表的建立过程链表的建立过程-1headtailheadtailpnumnamescorenext1201aaa80head = tail = NULL; if(head = NULL) head = p; tail = p;链表的建立过程链表的建立过程-2headtail numnamescorenext1201aaa80headtail numnamescorenext1201aaa80

77、numnamescorenext1202bbb85ptail-next = p; tail = p;链表的建立过程链表的建立过程-3head numnamescorenext1201aaa80numnamescorenext1203ccc75pnumnamescorenext1202bbb85tail tail-next = p; tail = p;scanf(%d%s%d, &num, name, &score);while(num != 0) p = (struct stud_node *) malloc(size); p-num = num; strcpy(p-name, name);

78、p-score = score; p-next = NULL; Link = InsertDoc(Link, p); scanf(%d%s%d, &num, name, &score);程序段程序段struct StudLink InsertDoc(struct StudLink Link, struct stud_node *stud) if(Link.pHead = NULL) Link.pHead = stud; else Link.pTail-next = stud; Link.pTail = stud; return Link;2. 链表的遍历链表的遍历ptr-numptr-scor

79、eptrptrfor(ptr = head; ptr != NULL; ptr = ptr - next) printf(%ld, %d, ptr - num, ptr - score);ptr=ptr-nexthead9905 Qian 80 NULL9901 Wang 809902 Li 90链表的遍历函数链表的遍历函数void Print_Stu_Doc(struct StudLink Link) struct stud_node *ptr; if(Link.pHead = NULL) printf(nNo Recordsn); return; printf(nThe Students

80、Records Are: n); printf(NumtNametScoren); for(ptr = Link.pHead; ptr!=NULL; ptr = ptr-next) printf(%dt%st%dn, ptr-num, ptr-name, ptr-score);3. 插入结点插入结点head numnamenext1201aaanumnamenext1203cccnumnamenext1202bbbnumnamenext1208kkks ptr s-next = ptr-nextptr-next = s先连后断先连后断4. 删除结点删除结点head numnext1201120

81、31202pre p=pre-nextpre-next=p-nextfree(p)先接后删先接后删1204p struct StudLink DeleteDoc(struct StudLink Link, int num)struct stud_node *p, *pre;p=Link.pHead; pre=Link.pHead;while(p != NULL) & (p-num !=num)pre=p;p=p-next;if(p=NULL)printf(not found !n);return Link;if(pre=p)Link.pHead=p-next;free(p);elsepre-next=p-next;free(p);return Link;