1、 C语言程序设计（第3版）张磊编著，2012年10月清华大学出版社出版。该教材面向程序设计初学者编写，适合将C语言作为第一门程序设计语言的高校学生。该教材理论教学和实验教学合二为一，在每章之后均设有实验指导。实验指导分为基础实验和综合实验两部分。基础实验紧密结合教材中的例题程序设置，以“理解验证完善扩充提高”为实验教学线索，重在巩固课堂教学知识，提高调试程序及完善程序的能力；综合实验以算法设计和程序实现为重点，训练运用所学知识解决实际问题的能力。该教材同时配有程序资源和试题库。Email： C C语言程序设计语言程序设计（第（第3 3版）版）张张 磊磊 编著编著 2121世纪高等学校规划教材世
2、纪高等学校规划教材 清华大学出版社清华大学出版社u8.1 结构体数据概述 u8.2 结构体类型和结构体变量u8.3 结构体数组 u8.4 结构体指针变量u8.5 使用动态链表存储数据u8.6 链表的基本操作u8.7 结构体应用举例结构体数据是由多个数据项组合而成的数据，如表8-1所示的学生信息表，当把每一行视为一个完整数据时，该数据就是一个结构体数据。为了有效地处理这样一类组合数据，C语言提供了“结构体”技术，它可以把多个数据项组合起来，作为一个数据整体进行处理。学号姓名性别成绩9901liujiaM879902wangkaiM899903xiaohuaF819904zhangliF82990
3、5wangfengM88u8.2.1 使用结构体变量存储学生信息 u8.2.2 定义结构体数据类型 u8.2.3 结构体变量的定义及使用8-1 利用结构体变量存储表8-1中第1行的学生信息，并输出其姓名和成绩。#includevoid main()printf(Name:%sn,stu.name);printf(Score:%dn,stu.score);l定义结构体类型的一般格式说明：“结构体名”是用户定义的结构体的名字，在以后定义结构体变量时，使用该名字进行类型标识。“成员表”是对结构体数据中每一个数据项的变量说明，其格式与说明一个变量的一般格式相同：“struct”是关键字，”是结构体类型
4、标识符，在类型定义和类型使用时“struct”都不能省略。结构体名称可以省略，此时定义的结构体称为无名结构体。l学生组合数据的结构体类型定义：学生组合数据的结构体类型定义：struct studentint num;char name20;char sex;int score;学号学号姓名姓名性别性别成绩成绩9901liujiaM879902wangkaiM899903xiaohuaF819904zhangliF829905wangfengM88 先定义结构体类型，再定义结构体变量。l一般格式如：student1,student2;在定义结构体类型的同时定义结构体变量。l一般格式例如：stru
5、ct student int num;char name20;char sex;int score;student1,student2;不定义结构体类型名，直接定义结构体类型变量。l一般格式;例如：struct int num;char name20;char sex;int score;student1,student2;l引用结构体成员的一般格式例如：student1.age 输入两个学生的信息，然后输出学习成绩高的学生的姓名和成绩信息。若成绩相同时，只输出第1个学生的信息。#includevoid main()printf(Data1:);scanf(%d%s%c%d,&stu1.num
6、,stu1.name,&stu1.sex,&stu1.score);printf(Data2:);scanf(%d%s%c%d,&stu2.num,stu2.name,&stu2.sex,&stu2.score);if(stu1.score=stu2.score)printf(%s,%dn,stu1.name,stu1.score);elseprintf(%s,%dn,stu2.name,stu2.score);stu.num9901intstu.nameliujiacharstu.sexMcharstu.score87intl8.3.1 结构体数组概述l8.3.2 结构体数组的初始化l8.3
7、.3 利用结构体数组管理学生信息数组元素是结构体类型的数组，称为结构体数组。l定义方法与其他结构体变量的定义方法相同。先定义结构体类型，然后用结构体类型定义数组变量。例如：struct student information100;定义结构体类型的同时，定义数组变量。定义无类型名的结构体数组变量。例如：l引用结构体数组成员的一般格式结构体数组名下标.成员名information20.score=91;例如：studentl 结构体数组的初始化例如：struct student info3=9901,liujia,M,87,9902,wangkai,M,89,9903,xiaohua,F,81;
8、按照表8-1的数据，输入一个班级的学生信息，并进行如下处理：把学习成绩在85以上的学生找出来，并输出这部分学生的姓名和成绩。分别统计男生和女生人数。l分析 定义一个结构体类型，并用它定义一个存储学生信息的结构体数组；向结构体数组中输入学生数据；统计，并输出结果。/*program e8-3.c*/#include#define N 5 struct studentint num;char name20;char sex;int score;void main()struct student stuN;int i,count_m=0,count_f=0;printf(Input Data:n);
9、for(i=0;iN;i+)scanf(%d%s%c%d,&stui.num,stui.name,&stui.sex,&stui.score);printf(Result:n);for(i=0;i85)printf(%s,%dn,stui.name,stui.score);if(stui.sex=M|stui.sex=m)count_m+;else count_f+;printf(Boys=%d,Girls=%dn,count_m,count_f);l指向结构体变量的指针变量，简称为结构体指针变量。与其他类型的指针一样，结构体指针变量既可以指向单一的结构体变量，也可以指向结构体数组变量，结构体
10、指针还可以作函数的参数。l8.4.1 结构体指针变量的定义及使用l8.4.2 结构体指针作函数的参数l 定义结构体指针变量的一般形式：struct 结构体名*结构体指针变量名;例如：struct student*p,*q;struct student stud1,info10;p=&stud1;q=info;p p stud1stud1q q infoinfon成员引用std1.num与p-num等价info1.num与q1-num等价void main()struct student stu,*p;p=&stu;p-num=9911;strcpy(p-name,changjiang);p-s
11、ex=F;p-score=91;printf(Num:%dnName:%sn,p-num,p-name);printf(Sex:%cnScore:%dn,p-sex,p-score);结构体指针用法示例。结构体指针用法示例。/*program e8-4.c*/#include#includestruct student int num;char name20;char sex;int score;/*program e9-4.c*/#include#includestruct student int num;char name20;char sex;int score;stu3=9913,xi
12、aoli,F,81,9914,zhanghua,M,82,9915,wangjun,F,88;void main()struct student*p;printf(%d%20s%3c%4dn,void main()void output(struct sudent*,int);output(stu,N);void output(struct student*p,int n)int i;for(i=0;inum,p-name,p-sex,p-score);return;/*program e8-6.c*/#include#include#define N 3struct student int
13、num;char name20;char sex;int score;stuN=9913,xiaoli,F,81,9914,zhanghua,M,82,9915,wangjun,F,88;l8.5.1 链表的概念l8.5.2 链表的特点l8.5.3 动态内存管理函数l8.5.4 定义链表结构是结构体最重要的应用，它是一种非固定长度的数据结构，是一种动态存储技术，它能够根据数据的结构特点和数量使用内存，尤其适用于数据个数可变的数据存储。l使用链表存储表中前3个学生数据。学号姓名性别成绩9901liujiaM879902wangkaiM899903xiaohuaF819904zhangliF829
14、905wangfengM88用calloc()申请一段内存M，并把它分成两部分：一部分存储数据；另一部分存储下一个内存段的地址。将一个学生数据存储在M的数据区中。若当前是第一个数据，则将M的首地址保存在指针变量head中；否则将M的首地保存在上一个内存段中。重复、的过程，直到所有数据存储完毕，在最后一段内存的地址区存储结束标志。链表中的结点具有完全相同的结构，每一个结点存储一个独立的结构体数据；链表的结点由系统随机分配，它们在内存中的位置可能是相邻的，也可能是不相邻的，结点之间的联系是通过指针域实现的；为了能准确的定位第一个结点，每个链表要有一个表头指针，从第一个结点开始，沿指针链能遍历链表中
15、的所有结点；链表中的结点是在需要时用calloc()申请的，当不再需要时，应有free()函数释放所占用的内存段。一个链表不需要事先说明它要包括的结点数目，在需要存储新的数据时，就可增加结点，需要删除数据时，就减少结点，链表结点是动态变化的。l要定义一个链表结点的结构，需要包括两个方面：定义数据存储所对应的各个成员；定义指向其他结点的指针成员。例如：假若要用链表逐个存储一批整数，其结点结构可定义如下：struct node int data;struct node*next;存储具体存储具体数据数据存储下一个节存储下一个节点的地址点的地址ustruct node类型的结点形成的链表类型的结点形
16、成的链表 头指针头指针空指针空指针学号学号姓名姓名性别性别成绩成绩9901liujiaM879902wangkaiM899903xiaohuaF819904zhangliF829905wangfengM88struct studentint num;char name20;char sex;int score;struct student*next;必须的成员，必须的成员，否则构不成链否则构不成链表表l8.6.1 链表结点的插入l8.6.2 链表结点的删除l8.6.3 链表结点的查找l在链表中插入结点，就是把一个新结点连接到链表中。l两种情况：在空链表中插入一个结点；在链表的p结点之后插入一个
17、新结点。1在空链表中插入一个结点在空链表中插入一个结点空链表就是头指针head为空的链表。申请一个new结点。new=(struct node*)calloc(1,sizeof(struct node);为p结点填充数据。将要存储的数据对应赋值给p结点数据域的各个成员。修改有关指针的指向。将new的next成员置空，使new结点成为链表的最后一个结点。将head指向new结点。head链表和要插入结点new如图所示。要将new结点插入在p结点之后，就是将new结点变成结点C的下一个结点，而使new的下一个结点成为结点D。使new的指针域存储结点D的首地址。new-next=p-next;把ne
18、w的首地址存储到结点p的指针域中。p-next=new;linsert()函数 功能：在head链表的p结点之后插入值为x的结点struct student*insert(struct node*head,struct node*p,int x)struct node*new;new=(struct node*)calloc(1,sizeof(struct node);new-data=x;if(head=NULL)head=new;head-next=NULL;else new-next=p-next;p-next=new;return(head);用插入结点的方法建立图示的学生成绩链表，链
19、表head有10个结点，每个结点存储一个学生的学号和学习成绩数据。程序程序:e8-8.cl函数的功能 creat_node()函数：生成一个链表结点。creat_list()函数：生成有n个struct s_node型结点的链表，函数的返回值是链表的头指针。out_list()函数：用于输出head链表的各结点值。#include#define N 10struct s_node /*定义结点类型*/char num4;int score;struct s_node*next;void main()struct s_node*create_node(void);struct s_node*cr
20、eate_list(int n);void out_list(struct s_node*head);struct s_node*head=NULL;head=create_list(N);out_list(head);/*生成一个链表结点的函数*/struct s_node*create_node(void)struct s_node*p;p=(struct s_node*)calloc(1,sizeof(struct s_node);scanf(%s%d,p-num,&(p-score);p-next=NULL;return(p);struct s_node*create_list(int
21、 n)struct s_node*new,*p;struct s_node*head;int i;if(n=1)new=create_node();head=new;p=new;for(i=2;inext=new;p=new;if(n=1)return(head);elsereturn(NULL);建立含有n个结点的链表的函数/*输出head链表中所有结点的函数*/void out_list(struct s_node*head)struct s_node*p;if(head!=NULL)p=head;while(p!=NULL)printf(%s%dn,p-num,p-score);p=p-
22、next;l从链表中删除结点，就是撤销结点在链表中的链接，把结点从链表中孤立出来。l删除结点过程：把指定的结点从链表中拿下来，通过修改有关结点的指针域实现；释放该结点使用的内存空间，使用free()函数来实现。n 删除删除p结点时指针变化情况结点时指针变化情况 n删除删除p结点后的结点后的head链表链表 l删除结点步骤删除结点步骤/*delete()函数函数*/struct node*delete(struct node*head,struct node*p)struct node*q;if(p=NULL)return(head);if(p=head)head=head-next;else
23、q=head;while(q-next!=p)q=q-next;q-next=p-next;free(p);return(head);l链表查找是从链表的第一个结点开始，沿着指针链，用查找值与链表结点逐个比较的过程。找到符合要求的结点之后，停止查找过程，返回相应结点的指针，否则返回一个空指针。l在head链表中查找data值为m的结点的过程，其中p为struct node型指针：p=head；当pNULL时，若p-data=m，则找到要求结点，查找结束，返回结点地址p；否则，执行下一步；当p=NULL时，链表中不存在要找的结点，查找结束，返回空指针NULL；p=p-next,转步骤。l查找函数
24、find()struct node*find(struct node*head,int m)struct node*p=head;while(p!=NULL&p-data!=m)p=p-next;if(p=NULL)return(NULL)else return(p);对图示的head链表，删除其值是x的结点。具体要求：输出被删除结点的值；当指定值结点不存在时，显示一个提示信息；x的值由键盘输入。程序程序e8-9.c u分析该问题的关键点有两点：查找data等于x的结点p；删除p结点。将输入的一个字符串加密后输出，加密表中未出现的源字符原样输出。u1问题分析与算法设计问题分析与算法设计 设计数
25、据结构存储字母加设计数据结构存储字母加密对照表。密对照表。struct table char input;char output;定义定义struct table型数组用于存储密码表。型数组用于存储密码表。输入一个字符串，在密码表的输入一个字符串，在密码表的input成员中查找每一个输入的字符，查找成成员中查找每一个输入的字符，查找成功后使用对应的功后使用对应的output成员加密输出，否则，原样输出源字符。成员加密输出，否则，原样输出源字符。#includestdio.h#include structstruct table table char input;/char input;/*存储
26、输入的源字符存储输入的源字符 */char output;/char output;/*存储加密后的字符存储加密后的字符 */;void main()void main()char chchar ch;int length,iint length,i;structstruct table encrypt10=table encrypt10=a,f,b,g,w,d,f,9,v,a,f,b,g,w,d,f,9,v,*,x,s,m,3,x,s,m,3,h,k,p,t,u h,k,p,t,u,?;,?;while(ch=getcharwhile(ch=getchar()!=n)()!=n)for(i=
27、0;encrypti.input!=ch&ifor(i=0;encrypti.input!=ch&i10;i+);10;i+);if(iif(i10)next），指向下一个结点。），指向下一个结点。当当p指向的结点数到指向的结点数到m时时，输出该结点的值并将其从链表中删除（出列），这时使，输出该结点的值并将其从链表中删除（出列），这时使p指向下一个结指向下一个结点，然后从点，然后从1开始重新报数。当链表中只有一个结点时，报数结束，输出开始重新报数。当链表中只有一个结点时，报数结束，输出该结点。该结点。Josephus问题。有n个人围成一圈，从1开始顺序编号到n，现在从1号开始顺时针从1数数，数
28、到m者自动出列，然后从下一个人开始重新数数，仍然每次数到m者自动出列。给出这n个人出列的顺序。结构体数据类型不是系统固有的，它需要在程序中先行定义，然后才能使用。结构体变量的定义有3种方法：先定义结构体类型，再定义结构体变量；在定义结构体类型的同时定义结构体变量；不定义结构体类型名，直接定义结构体类型变量。引用结构体成员的方法主要有两种：使用结构体变量名引用结构体成员；通过指向结构体变量的指针引用结构体成员。4数组元素是结构体类型的数组，称为结构体数组，结构体数组具有数组的一切性质。指向结构体变量的指针，称为结构体指针，结构体指针既可以指向单一的结构体变量，也可以指向结构体数组变量，结构体指针
29、也可以作函数的参数。使用结构体指针作函数的实参时，实参和形参必须是同一种结构体类型。链表是一种动态的数据存储结构，它的每一个结点都是结构体类型的数据，同一个链表中的所有结点具有相同的数据类型。一个链表结点包括数据域和指针域两部分，数据域存储需要处理的数据，指针域存储下一个结点的位置。C语言使用动态内存管理函数为链表申请结点空间。链表的基本操作有插入结点、删除结点、查找结点、结点数据读写等，向链表插入结点前必须先用动态内存分配函数获得存储空间，从链表中删除的结点要进行释放操作。从空链表开始不断地插入结点即可建立一个链表，任何一个链表必须有一个头指针，只有通过头指针才能访问链表结点。当一个链表结点的指针域为空时，表明是链表的最后一个结点，当最后一个结点的指针指向开头结点时，便形成一个循环链表。
