《C语言程序》-第10章 结构体与链表

1．问题描述——构建手机通讯录众所周知，手机中有一个简单的通讯录工具，用于管理联系人的基本信息，其基本功能包括对联系人信息的新建、修改、删除和查询等。2．引例分析要想构建手机通讯录，应创建联系人的基本信息，而联系人的基本信息应该包括姓名、年龄和联系电话等，假设通讯录最多容纳50名联系人的信息，建立一个数组friends，数组的大小为50，每一个数组元素都应存放姓名、年龄和联系电话等信息。10.1引例

3．程序代码#include<stdio.h>#include<string.h>structfriend_list/*手机通讯录结构体定义*/{charname[10];/*姓名*/intage;/*年龄*/chartelephone[13];/*联系电话*/};main(){intchoice;charname[10];structfriend_listfriends[50];/*包含50个人的通讯录*/do{printf("手机通讯录功能选项：1:新建2:修改3:删除4:查询0:退出\n");printf("请选择功能:");scanf("%d",&choice);switch(choice){case1:printf("新建联系人姓名:");;/*new_friend(friends);*/break;case2:printf("请输入要修改的联系人姓名:");scanf("%s",name);;/*modify_friend(friends,name);*/break;case3:printf("请输入要删除的联系人姓名:");scanf("%s",name);;/*delete_friend(friends,name);*/break;case4:printf("请输入要查询的联系人姓名:");scanf("%s",name);;/*search_friend(friends,name);*/break;case0:break;}}while(choice!=0);printf("谢谢使用通信录功能！\n");}10.2.1结构体类型与结构体变量的定义1.结构体类型定义struct结构体类型名 /*struct是结构体类型关键字*/{数据类型数据项1;

数据类型数据项2;……

数据类型数据项ｎ;}; /*此行分号不能少！*/其中，struct是定义结构体类型的关键字。结构体类型名的命名规则，与变量名相同。成员的数据类型可以是基本数据类型。10.2结构体类型及其变量

【例10.1】定义一个反映学生基本情况的结构体类型，用以存储学生的信息。structdate /*日期结构体类型：由年、月、日共三项组成*/{intyear;intmonth;intday;};structstd_info/*学生结构体类型：由学号、姓名、性别和生日共四项组成*/{charno[7];charname[9];charsex[3];structdatebirthday;};structscore /*成绩结构体类型：由学号和三门成绩共四项组成*/{charno[7];intscore1;intscore2;intscore3;};

2.结构体类型变量定义（1）间接定义法──先定义结构体类型、再定义结构体变量。定义一般格式为：struct结构体类型名{…};/*定义结构体类型*/struct结构体类型名结构体变量表;/*定义结构体类型变量*/（2）直接定义法──在定义结构体类型的同时定义结构体变量。一般格式为：struct结构体类型名{…}结构体变量表;（3）一次性定义──先定义无名结构体类型，紧接着定义结构体类型变量。一般格式为：struct{…}结构体变量表;1.结构体变量的引用规则对于结构体变量，要通过成员运算符“.”，逐个引用其成员。结构体变量的引用格式为：结构体变量.成员/*其中的“.”是成员运算符*/如果某成员本身又是一个结构体类型，则只能通过多级的分量运算，对最低一级的成员进行引用。此时的引用格式可扩展为：结构体变量.成员.子成员.….最低1级子成员10.2.2结构体变量的引用与初始化【例10.2】利用例10.1中定义的结构体类型structstd_info，定义一个结构体变量student，用于存储和显示一个学生的基本情况。#include"stdio.h"/*定义并初始化一个外部结构体变量student*/structstd_infostudent={"000102","张三","男",{1980,9,20}};

main(){printf("No:%s\n",student.no);/*引用结构体变量student中的no成员项*/printf("Name:%s\n",);/*引用结构体变量student中的name成员项*/printf("Sex:%s\n",student.sex);/*引用结构体变量student中的sex成员项*/printf("Birthday:");printf("%d-",student.birthday.year);/*引用student中birthday的year成员项*/printf("%d-",student.birthday.month);/*引用birthday的month成员项*/printf("%d\n",student.birthday.day);/*引用student中birthday的day成员项*/}2.结构体变量的初始化与一维数组的初始化类似，结构体变量初始化的一般格式为：结构体变量={初值表};例如:structstudent{intnum;charname[20];floatscore;}st={1001,"gxl",98};结构体数组初始化的格式为：结构体数组[n]＝{{初值表1},{初值表2},...,{初值表n}};【例10.3】首先定义结构体类型structstudent，然后定义一个结构体数组st[3]，用于存储和显示三个学生的基本情况。#include"stdio.h"main(){structstudent{intnum;charname[20];floatscore;}st[3]={{1102,"张三",89},{1105,"李四",89},{1112,"王五",98}};inti;for(i=0;i<3;i++){printf("%6d",st[i].num);printf("%s",st[i].name);printf("%.0f\n",st[i].score);}}

10.3结构体数组【例10.4】计算学生的某科平均成绩和不及格学生的人数。#include"stdio.h"structstu{intnum;char*name; charsex;floatscore;}boy[5]={{101,"Liping",'M',45},{102,"Zhangping",'M',62.5},{103,"Hefang",'F',92.5},{104,"Chengling",'F',87},{105,"Wangming",'M',58}};main(){inti,c=0;floatave,s=0;for(i=0;i<5;i++){s+=boy[i].score;if(boy[i].score<60)c+=1;

}printf("s=%f\n",s);

ave=s/5;printf("average=%f\ncount=%d\n",ave,c);}10.4.1指向结构体变量的指针一般来说，如果指针变量pointer已指向结构体变量var，则用指针变量pointer引用结构体变量var成员项可用以下形式：pointer->成员或(*pointer).成员一般地说，以下三种形式等价。var.成员pointer->成员(*pointer).成员

10.4指向结构体类型数据的指针【例10.5】使用指向结构体变量的指针来访问结构体变量的各个成员。#include"stdio.h"main(){structstudent{intnum;charname[20];floatscore;}st={1102,"张三",89},*p=&st;printf("%6d",p->num);printf("%s",p->name);printf("%.0f\n",p->score);}10.4.2指向结构体数组的指针如果指针变量p已指向某结构体数组，则p+1指向结构体数组的下一个元素，而不是当前元素的下一个成员。【例10.6】使用指向结构体数组的指针来访问结构体数组。#include"stdio.h"main(){structstudent{intnum;charname[20];floatscore;}st[3]={{1102,"张三",89},{1105,"李四",89},{1112,"王五",98}},*p=st;inti;for(i=0;i<3;i++,p++){printf("%6d",p->num);printf("%s",p->name);printf("%.0f\n",p->score);}}10.5.1链表结构1．链表的概念链表是用指针把各个结点链接在一起，其一般形式如图所示。10.5链表处理

【例10.7】建立一个简单的链表，它由3个存放学生数据（包括学号和成绩）的结点组成，然后输出各结点的数据。#include"stdio.h"structnode/*定义结构体类型*/{intnum;/*学号*/floatscore;/*成绩*/structnode*next;/*指向structnode类型的指针变量*/}main(){structnodea,b,c,*head,*p;a.num=101;a.score=85.4;b.num=103;b.score=96.1;c.num=105;c.score=77.5;head=&a;a.next=&b;b.next=&c;c.next=NULL;p=head;do{printf("学号：%d成绩：%5.2f\n",p->num,p->score);p=p->next;}while(p!=NULL);}2．动态存储分配函数（1）分配内存空间函数malloc()调用形式：(类型说明符*)malloc(size)；功能：在内存的动态存储区中分配一块长度为“size”字节的连续区域。函数的返回值为该区域的首地址。例如：pc=(char*)malloc(sizeof(char));表示分配1个字节的内存空间，并强制转换为字符类型，函数的返回值为指向该字节的指针，把该指针赋予指针变量pc。（2）分配内存空间函数calloc()调用形式：(类型说明符*)calloc(n,size)；功能：在内存动态存储区中分配n块长度为“size”字节的连续区域。函数的返回值为该区域的首地址。说明：“（类型说明符*）”用于强制类型转换。calloc()函数与malloc()函数的区别仅在于一次可以分配n块区域。例如：ps=(struetstu*)calloc(2,sizeof(structstu));其中的sizeof(structstu)是求stu的结构体长度。因此该语句的意思是：按stu的长度分配2块连续区域，强制转换为stu类型，并把其首地址赋予指针变量ps。（3）释放内存空间函数free()调用形式：free(void*ptr)；功能：释放ptr所指向的一块内存空间，ptr是一个任意类型的指针变量，它指向被释放区域的首地址。被释放区应是由malloc()或calloc()函数所分配的区域。【例10.8】分配一块区域，输入一个学生数据。#include"stdlib.h"#include"stdio.h"main(){structstu{intnum;char*name;charsex;floatscore;}*ps;ps=(structstu*)malloc(sizeof(structstu));ps->num=102;ps->name="Zhangping";ps->sex='M';ps->score=62.5;printf("Number=%d\nName=%s\n",ps->num,ps->name);printf("Sex=%c\nScore=%f\n",ps->sex,ps->score);free(ps);}对链表的常用的操作主要包括创建、插入、删除和输出等基本操作。创建链表【例10.9】编写一个create()函数，按照规定的结点结构，创建一个单链表。基本思路：首先向系统申请一个结点的空间，然后输入结点数据域中的数据项，并将指针域置为空（链尾标志），最后将新结点插入到链表尾。对于链表的第一个结点，还要设置头指针变量。本题中设3个指针变量head、new1和tail，分别说明如下：head：头指针变量，指向链表的第一个结点，用作函数返回值。new1：指向新申请的结点。tail：指向链表的尾结点，用tail->next=new1，实现将新申请的结点，插入到链表尾，使之成为新的尾结点。10.5.2对链表的基本操作#include"stdio.h"#include"malloc.h"#defineNULL0#defineLENsizeof(structstudent) /*定义结点长度*/structstudent/*定义结点结构*/{intnum; /*学号*/floatscore; /*成绩*/structstudent*next; /*指针域*/};structstudent*create()/*create()函数:创建单链表*/{structstudent*head=NULL,*new1,*tail;intcount=0;/*链表中的结点个数(初值为0)*/new1=tail=(structstudent*)malloc(LEN);/*向系统申请一新结点空间*/scanf("%d%f",&new1->num,&new1->score);while((new1->num)!=0)/*如果学号0，则退出*/{count++;/*结点个数加1*/if(count==1)head=new1;/*将新结点插入到链表尾，并设置新的尾指针*/elsetail->next=new1;/*非首结点,将新结点插入到链表尾*/tail=new1; /*设置新的尾结点*/new1=(structstudent*)malloc(LEN);scanf("%d%f",&new1->num,&new1->score);}tail->next=NULL;return(head);/*返回单链表的头指针*/}3.插入操作在结点a与b之间插入一个新的结点x。插入前，结点a是结点b的前驱结点，结点b是结点a的后继结点；插入后，新插入的结点x成为结点a的后继结点、结点b的前驱结点。结点插入前的链表结点插入后的链表算法如下：s=p->next;p->next=s;【例10.10】编写insert()函数，完成在单链表的第i个结点后插入1个新结点的操作。structstudent*insert(structstudent*head,structstudent*stu,inti){structstudent*pointer;if(head==NULL)/*若为空链表*/head=stu,stu->next=NULL;/*将新结点插入到空链表中*/else /*非空链表*/if(i==0)stu->next=head,head=stu;/*使新结点成为链表新的首结点*/else /*其他位置*/{pointer=head;/*查找单链表的第i个结点(pointer指向它)*/for(;pointer!=NULL&&i>1;pointer=pointer->next,i--)if(pointer==NULL) /*越界错*/printf("Outoftherange,can'tinsertnewnode!\n");else /*一般情况：pointer指向第i个结点*/stu->next=pointer->next,pointer->next=stu;}return(head);}

4.删除操作删除结点x。删除前，结点x是结点b的前驱结点、结点a的后继结点；删除后，结点a成为结点b的前驱结点，结点b成为结点a的后继结点。

结点删除前的链表结点删除后的链表pa->next=px->next;free(px);【例10.11】编写一个dele()函数，删除链表中学号为num的指定结点。structstudent*dele(structstudent*head,intnum){structstudent*pf,*pb;if(head==NULL)/*若为空表，输出提示信息*/{printf("\nemptylist!\n");returnhead;}pb=head;while(pb->num!=num&&pb->next!=NULL)/*当前结果不是要删除的结点，而且也不是最后一个结点时，继续循环*/{pf=pb;pb=pb->next;}/*pf指向当前结点，pb指向下一结点*/if(pb->num==num){if(pb==head)head=pb->next;/*找到被删结点，且为第一结点，则使head指向第二个结点，否则使pf所指结点的指针指向下一结点的后续*/elsepf->next=pb->next;free(pb);printf("Thenodeisdeleted\n");}elseprintf("Thenodenotbeenfoud!\n");returnhead;}

5.输出链表首先知道head头指针的值，设一个指针变量p，先指向第一个结点，输出p所指的结点，然后使p后移一个结点，再输出，直到链表的尾结点。【例10.12】输出链表。voidoutput(structstudent*head){structstudent*p;p=head;if(head!=NULL)do{printf("%d%5.1f\n",p->num,p->score);p=p->next;}while(p!=NULL);}

10.6.1共用体共用体类型的定义与结构体类型的定义类似，格式为：

union共用体类型名

{成员列表;};1.间接定义──先定义类型、再定义变量。例如：定义data共用体类型变量un1,un2,un3的语句如下：uniondata{inti;charch;floatf;};uniondataun1,un2,un3;2.直接定义──定义类型的同时定义变量。union[data]{inti;charch;floatf;}un1,un2,un3;

10.6共用体和枚举类型枚举类型的定义为：enum枚举类型名{取值表};如：enumweekdays{Sun,Mon,Tue,Wed,Thu,Fri,Sat}；枚举类型变量的定义与结构体变量类似。例如：enumweekdays

{Sun,Mon,Tue,Wed,Thu,Fri,Sat}workday;10.6.2枚举类型在C语言中，可以用typedef关键字来为系统已经有的数据类型定义别名，该别名与标准类型名一样，可以用来定义相应的变量。例如：

typedefintINTEGER;/*指定别名INTEGER代表int*/typedeffloatREAL;/*指定别名REAL代表float*/INTEGERx,y;等价于intx,y;REALa,b;等价于floata,b;10.7定义已有类型的别名也可以声明一个新的别名DATE代表一个结构体类型。例如：typedefstructdate{intmonth;intday;intyear;}DATE;下面可以用DATE定义变量DATEbirthday;/*定义结构体变量*/

上机实验1．掌握结构体变量的引用与初始化；2．掌握结构体数组的应用；3．掌握指向结构体类型的指针变量的应用。一、实验目的1．验证性实验1）分析并运行下面的程序，给出运行结果。#include"stdio.h"structstudent{charname[10];intold;}main(){structstudentstudents[3]={{"wangming",18},{"liyang",19},{"liuping",20}};structstudentstu;inti;for(i=0;i<2;i++){if(students[i].old>students[i+1].old){stu=students[i];students[i]=students[i+1];students[i+1]=stu;}}printf("Theyoungestis%s\n",students[0].name);}二、实验内容

2．设计性实验1）请编写函数fun，找出成绩最低的学生记录。#include<stdio.h>#include<string.h>#defineN10typedefstructss{charnum[10];ints;}STU;fun(STUa[],STU*s){}main(){STUa[N]={{"A01",81},{"A02",89},{"A03",66},{"A04",87},{"A05",77},