C语言课程之一高级编程部分结构体和链表

讲师：任继梅系列课程—C语言高级编程结构体和链表第一章课程目标掌握C语言自定义类型结构体的定义和使用、共用体、链表的建立和基本操作掌握C语言的存储方式存储类、链接、内存管理掌握线性表和常用的数据结构线性表、存储方式、顺序表、链表、队列、栈掌握常用的查询和排序算法顺序查询、折半查询、插入排序、选择拍寻掌握动态链接库和静态链接库课程安排第一天上午：自定义数据类型下午：链表的建立和基本操作第二天上午：数据的存储方式下午：线性表第三天上午：队列下午：栈第四天上午：查找下午：排序第五天上午：其他常用算法下午：静态链接库和动态链接库课前提问

结构体是如何定义的？如何引用结构体成员？指针怎样引用结构体成员？什么是共用体？怎么样建立链表？如何删除链表的一个节点？本章目标结构体类型与结构体变量结构体的类型和变量的使用结构体成员的引用结构体数组结构体与函数动态数据结构——链表链表存储结构链表的基本操作其他自定义数据类型共用体 枚举类型自定义类型标识符（typedef）自定义类型知识点1-结构体结构体

内部资料请勿COPY6结构体是一种构造数据类型。结构体类型的变量可以拥有不同数据类型的成员，是不同数据类型成员的集合。

用途：把不同类型的数据组合成一个整体——自定义数据类型。结构体的声明

声明结构体类型的一般形式：

struct结构体名{类型标识符成员名；类型标识符成员名；…………….}；成员类型可以是基本型或构造型struct关键字,不能省略合法标识符可省:无名结构体结构体类型和结构体变量

内部资料请勿COPY7示例:定义一个可描述学生基本情况的结构体类型如下：structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];};namenumsexagescoreaddr2字节2字节20字节1字节4字节30字节……..结构体类型定义描述结构的组织形式,不分配内存结构体变量

内部资料请勿COPY8例structstudent{intnum;charname[20];charsex;intage;floatscore;};structstudentstu1,stu2;结构体变量的定义定义好一个结构体类型后，我们可以将其看作是和int、char、float等数据类型一样的一个新的数据类型。struct结构体名{类型标识符成员名；类型标识符成员名；…………….}；struct结构体名变量名表列；1.先定义结构体类型，再定义结构体变量结构体变量

内部资料请勿COPY92.定义结构体类型的同时定义结构体变量struct结构体名{类型标识符成员名；类型标识符成员名；…………….}变量名表列；例structstudent{intnum;charname[20];charsex;intage;floatscore;}stu1,stu2;结构体变量

内部资料请勿COPY103.直接定义结构体变量struct{

类型标识符成员名；类型标识符成员名；…………….}变量名表列；例struct{intnum;charname[20];charsex;intage;floatscore;}stu1,stu2;用无名结构体直接定义变量只能一次结构体类型与结构体变量比较

类型:不分配内存,变量:分配内存类型:不能赋值、存取、运算；变量:可以结构体成员名与程序中变量名可相同，不会混淆结构体可嵌套结构体变量的引用

内部资料请勿COPY11结构体变量的引用格式引用规则：结构体变量不能整体引用,只能引用变量成员成员(分量)运算符优先级:1结合性:从左向右引用方式：结构体变量名.成员名例structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}stu1,stu2;stu1.num=10;stu1.score=85.5;stu1.score+=stu2.score;stu1.age++;结构体变量引用

内部资料请勿COPY12例structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}stu1,stu2;printf(“%d,%s,%c,%d,%f,%s\n”,stu1);()stu1={101,“WanLin”,‘M’,19,87.5,“DaLian”};()结构体嵌套

内部资料请勿COPY13结构体嵌套时逐级引用structdate{intmonth;intday;intyear;};structperson{charname[20];charsex;structdatebirthday;};若有定义：structpersonperson1;

可以这样访问person1中的成员month：person1.birthday.monthnameSexbirthdaymonthdayyear结构体变量赋值

内部资料请勿COPY14同类型结构体变量间的整体赋值结构体变量可以通过整体赋值，将一个结构体变量中的所有数据，赋给另一个结构体类型相同的结构体变量中对应的数据成员。例structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}stu1,stu2;stu2=stu1;

结构体示例建立一个学生的基本情况表，然后将其打印输出(structSample1.c)。

内部资料请勿COPY15structstudent{intnum;charname[20];charsex;intage;floatscore;};intmain(){structstudentstu1,stu2;stu1.num=10001;

strcpy(,"zhang");stu1.sex='M';stu1.age=19;stu1.score=88;

stu2=stu1;printf("stu1:%d,%s,%c,%d,%6.2f\n",stu1.num,,stu1.sex,stu1.age,stu1.score);printf("stu2:%d,%s,%c,%d,%6.2f\n",stu2.num,,stu2.sex,stu2.age,stu2.score);}结构体变量初始化

内部资料请勿COPY16struct结构体名{类型标识符成员名；类型标识符成员名；…………….}；struct结构体名结构体变量={初始数据}；例

structstudent{intnum;charname[20];charsex;intage;};structstudentstu1={112,“WangLin”,‘M’,19};在定义的时候初始化结构体变量自定义类型知识点2-结构体指针

内部资料请勿COPY17指向结构体变量的指针的值是该结构体变量所分配的存储区域的首地址。结构指针变量的定义指向结构体的指针numnamesexagestupstructstudent{intnum;charname[20];charsex;intage;}stu;structstudent*p=&stu;结构体指针

内部资料请勿COPY182.通过指针访问结构体变量的成员结构变量中简单成员的引用形式有下面三种：①结构变量名.成员名（名字引用）；②结构指针->成员名（指针引用）；③（*结构指针）.成员名（将指针转化为名字引用）；(*结构体指针名).成员名结构体指针名-->成员名结构体变量名.成员名例intn;int*p=&n;*p=10;n=10structstudentstu1;structstudent*p=&stu1;stu1.num=101;(*p).num=101结构体指针示例编写一个时钟调试程序，并以hh:mm:ss的方式显示日期。

内部资料请勿COPY19//结构体定义structDateTime{inthours;intminutes;intseconds;};voiddelay()//延时函数{ longi; for(i=0;i<92345678;voidgetTime(structDateTime*tt){tt->seconds++;if(tt->seconds==60){delay();//调整时间精度tt->minutes++;tt->seconds=0;}if(tt->minutes==60){tt->hours++;tt->minutes=0;}if(tt->hours==24){tt->hours=0;}}结构体指针练习设计一个C程序，文件名struceExercise1.c,给定一个日期，求出该日为星期几（已知2014-5-1为星期四）

内部资料请勿COPY20自定义数据类型知识点3-结构体数组

内部资料请勿COPY21结构体数组的定义结构体数组的定义的三种形式：numnamesexagenumnamesexagestu[0]stu[1]25B形式一:structstudent{intnum;charname[20];charsex;intage;};structstudentstu[2];形式二:

structstuden{intnum;

charname[20];

charsex;

intage;}stu[2];形式三:struct

{intnum;

charname[20];

charsex;

intage;

}stu[2];结构体数组

内部资料请勿COPY22结构体数组的初始化，与通常数组的初始化类似例如：

structstudent{intnum;charname[20];charsex;intage;};structstudentstu[]={{100,“WangLin”,‘M’,20},{101,“LiGang”,‘M’,19},{110,“LiuYan”,‘F’,19}};结构体数组的初始化和引用引用方式：结构体数组名[下标].成员名stu[1].age++;strcpy(stu[0].name,”ZhaoDa”);structstudent{intnum;charname[20];charsex;intage;}stu[3];结构体数组示例

内部资料请勿COPY23structstudent{intnum;charname[20];charsex;intage;}stu[3]={{10101,"LiLin",'M',18},{10102,"ZhangFun",'M',19}, {10104,"WangMin",'F',20}};voidmain(){structstudent*p;for(p=stu;p<stu+3;p++)printf("%d%s%c%d\n",p->num,p->name,p->sex,p->age);}numnamesexagestu[0]pstu[1]stu[2]p+1自定义数据类型知识点4-结构体和函数

内部资料请勿COPY24结构体变量作函数参数arga:27b:3c:30(main)值传递main(){voidfunc(structdata);structdataarg;arg.a=27;arg.b=3;arg.c=arg.a+arg.b;printf("%d%d%d\n",arg.a,arg.b,arg.c);func(arg);printf("%d%d%d\n",arg.a,arg.b,arg.c);}voidfunc(structdataparm){printf("%d%d%d\n",parm.a,parm.b,parm.c);parm.a=18;parm.b=5;parm.c=parm.a*parm.b;printf("%d%d%d\n",parm.a,parm.b,parm.c);}structdata{inta,b,c;};结构体和函数

内部资料请勿COPY25用结构体指针变量作函数参数voidfunc(structdata*parm){printf("%d%d%d\n",parm->a,parm->b,parm->c);parm->a=18;parm->b=5;parm->c=parm->a*parm->b;printf("%d%d%d\n",parm->a,parm->b,parm->c);}结构体数组作函数参数voidprint(structstudentstu[],intn){for(i=0;i<n;i++){printf("%d",stu[i].num);printf("%s",stu[i].name);printf("%6.1f,%6.1f,%6.1f\n",stu[i].score[0],stu[i].score[1],stu[i].score[2]);}}结构体与函数返回结构体的函数

内部资料请勿COPY26例：建立10名学生的信息表，每个学生的数据包括学号、姓名、及三门课的成绩。输出总分最高的学生记录，要求将查找该记录的过程编写为函数。//查找最高分学生的记录函数，返回值为指向该记录的指针

student*search_max(student*x,intn){inti,k=0;for(i=1;i<n;i++)if(x[i].sum>x[k].sum)k=i;returnx+k;}结构体综合实例设计程序structSample.c，要求模拟银行存款的过程

内部资料请勿COPY27//结构体类型设计structfunds{

charbank[FUNDLEN];//银行名

doublebankfund;//账号中的钱

charsave[FUNDLEN];账号

doublesavefund;存入金额};intmain(void){

structfundsstan={

“Garlic-MelonBank“,

3024.72,

”Lucky‘sSavingsandLoan“,

9237.11

};

printf("Stanhasatotalof$%.2f.\n“,

sum(&stan);

return0;}/*addstwodoublenumbers*/doublesum(conststructfunds*money){

return(money->bankfund+money->savefund);}?更改add函数的参数，1、修改成传递结构体成员2、修改成传递结构体变量结构体综合练习设计C语言程序，程序名：structExercise2.c完善银行终端存取款机的功能，完成如下功能：1、查询功能：输入银行账号和密码，可以查询余额2、存款功能输入存款金额，可以存款3、取款功能，可以根据输入金额进行取款

内部资料请勿COPY28

自定义数据类型知识点5-链表

内部资料请勿COPY29链表的提出数组在内存中占用连续存储的空间。链表是动态的进行存储分配，链表的各个结点在逻辑上是连续的，但是在内存中存储时不占用连续的空间。链表的使用能有效的避免存储空间的浪费和数据移动的问题。链表结点的定义structstudent{intnum;floatscore;structstudent*next;};动态数据结构-链表

内部资料请勿COPY30链表的基本结构链表是一种常用的、能够实现动态存储分配的数据结构。（1）头指针变量head──指向链表的首结点。（2）每个结点一般由2个域组成： 1）数据域──存储结点本身的信息。 2）指针域──指向后继结点的指针。（3）尾结点的指针域置为“NULL(空)”，作为链表结束标

志。1356A1475BNULLC1249head124913561475链表

内部资料请勿COPY31单向链表的访问1.输出链表各个结点的数据voidprint_link(structstudent*head){structstudent*p;p=head;while(p!=NULL) {printf(“%d,%6.1f\n”,p->num,p->score);p=p->next;}}2.统计链表的长度voidlen_link(structstudent*head){intn=0;structstudent*p;p=head;while(p!=NULL) { n++; p=p->next; }return(n);}链表

内部资料请勿COPY32动态存储空间的建立和释放1．动态存储空间的建立（1）malloc函数,其函数原型为:void*malloc(unsignedintsize);其作用是在内存的动态存储区中分配一个长度为size的连续空间。（2）sizeof(type)运算符计算所给数据类型type的字节数，主要用来计算链表中结点所占动态存储空间的字节数。（3）calloc函数,其函数原型为:void*calloc(unsignedn，unsignedsize);其作用是在内存的动态区存储中分配n个长度为size的连续空间。链表

内部资料请勿COPY332.动态存储空间的释放

free函数,其函数原型为：voidfree(void*p);其作用是释放由p指向的内存区，使这部分内存区能被其他变量使用。p是调用calloc或malloc函数时返回的值。链表的基本操作包括建立链表、输出链表、查找链表中某个结点、在链表中插入一个新的结点、删除链表中的某个结点。链表示例链表的建立（structSample3_link.c）（1）先设三个指针变量：head、p1、p2，它们都是用来指向structstudent类型数据的。structstudent*head=NULL,*p1,*p2;head：头指针变量，指向链表第一个结点，作函数返回值。p1：指向新申请的结点。p2：指向链表的尾结点，用p2->next=p1，实现将新申请的结点插入到链表尾，使之成为新的尾结点。（2）malloc函数开辟第一个结点，并使head和p2都指向它。head=p2=(structstudent*)malloc(sizeof(structstudent));scanf("%d%f",&p2->num,&p2->score);/*读入数据*/(3)再用malloc函数开辟另一个结点并使p1指向它，接着输入该结点的数据，并与上一结点相连，且使p2指向新建立的结点。

内部资料请勿COPY34链表示例-链表建立

内部资料请勿COPY35建立新结点：

p1=(structstudent*)malloc(sizeof(structstudent))；scanf("%d%f",&p1->num,&p1->score);如图8-6(a)所示：与上一结点连接：p2->next=p1;如图8-6(b)所示：使p2指向新链结点：p2=p1;如图8-6(c)所示：重复执行第（3）步，可以建立第三个结点，并使第三个结点和第二个结点链接（p2->next=p1;），依次创建后面的结点，直到所有的结点建立完毕。8-6(a)8-6(b)8-6(c)链表示例-链表建立

内部资料请勿COPY36建立有n个student类型结点的链表，n的值从键盘输入，再输出链表。/*create(intn)函数:创建一个具有头结点的单链表*//*形参n值：创建链表的结点数*//*返回值：返回单链表的头指针*/structstudent*create(intn){inti;structstudent*head=NULL,*p1,*p2;head=p2=(structstudent*)malloc(LEN);/*申请新结点的空间*/

scanf("%d%f",&p2->num,&p2->score);/*读入数据*/for(i=2;i<=n;i++){p1=(structstudent*)malloc(LEN);scanf("%d%f",&p1->num,&p1->score);p2->next=p1;/*与上一结点相链*/

p2=p1;/*使p2指向新链结点*/}

p2->next=NULL;return(head);}

链表删除

内部资料请勿COPY37在结点类型为student的链表中删除num域为某个值的结点的主要操作步骤：设三个指针变量：head、p1、p2，它们都是用来指向structstudent类型数据的，head指向链表头，若head==NULL，则链表为空，没有可删除结点。查找要删除的结点，使p1指向它，p2指向p1的前一结点。有两种情况：删除首结点和其它结点。（2）删除其它结点删除链表的中间结点通过将下一结点地址赋给前一结点地址来实现，即将要删除的p1结点的后继地址，放入前一结点p2的地址域（p2->next=p1->next;），同时释放p1结点。（1）删除首结点使p1指向第一个结点，用以下语句实现删除首结点操作。p1=head;head=p1->next;free(p1);链表的插入操作

内部资料请勿COPY38在结点类型为student的链表中插入一个新结点的主要操作步骤：先设四个指针变量head、p0、p1、p2：head：要插入链表的头指针。p0：指向要插入的结点。p1：指向当前结点，首先使p1指向头结点（p1=head）。p2：指向前一结点（即P1原来指向的结点）。首先查找插入的位置，应插入的位置：p1之前，p2之后。在链表中，各结点按成员score（成绩）由小到大顺序存放，从第一个结点开始，把待插入结点p0->score与每一个结点p1->score比较，若(p0->score)>(p1->score)，则p1移到下一个结点（p1=p1->next），同时，p2也移到下一个位置（p2=p1）。链表的插入操作

内部资料请勿COPY39（1）原链表为空表,即head=NULL时，

用以下语句实现插入操作：head=p0;p0->next=NULL;p0是该链表惟一一个结点。（2）在头结点之前插入当p0->score<=p1->score时，若p1=head，表示插入结点在头结点之前。用以下语句实现插入操作：head=p0;p0->next=p1;插入前插入后链表的插入操作

内部资料请勿COPY40（3）在非头结点之前，非尾节点之后插入当p0->score<=p1->score，且p1<>head时，表示在在非头结点之前，非尾节点之后插入结点，用以下语句实现插入操作：p2->next=p0;p0->next=p1;插入前插入后链表的插入操作

内部资料请勿COPY41（4）尾节点之后插入当p0->score>p1->score时，表示在尾节点之后插入结点，用以下语句实现插入操作：p1->next=p0;p0->next=NULL;插入前插入后链表综合练习题设计一C语言程序，文件名为：structExercise3.c,实现链表的基本的删除、插入、查询等操作。结构体类型如下：structstudent/*定义结构体*/{longnumber;/*学号*/ charname[20];/*姓名*/ structstudent*next;/*连接指针*/};

内部资料请勿COPY42定义类型知识点6-共用体

内部资料请勿COPY43构造数据类型，也叫联合体使几个不同类型的变量共占一段内存(相互覆盖)共用体类型定义定义形式：union共用体名{类型标识符成员名；类型标识符成员名；…………….}；fchi类型定义不分配内存例uniondata{inti;charch;floatf;};共用体

内部资料请勿COPY44fchib共用体变量定义分配内存,长度=最长成员所占字节数fchia共用体变量任何时刻只有一个成员存在uniondata{inti;char ch;floatf;}a,b;uniondata{inti;charch;floatf;};uniondataa,b,c,*p,d[3];

union{inti;charch;floatf;}a,b,c;共用体

内部资料请勿COPY45共用体变量引用共用体指针名->成员名共用体变量名.成员名(*共用体指针名).成员名a.ia.cha.fp->ip->chp->f(*p).i(*p).ch(*p).fd[0].id[0].chd[0].funiondata{inti;charch;floatf;};uniondataa,b,c,*p,d[3];共用体

内部资料请勿COPY46对共用体变量的使用需要注意如下几个问题：（1）系统采用覆盖技术，实现共用变量各成员的内存共享，所以在某一时刻，存放的和起作用的是最后一次存入的成员值。（2）由于所有成员共享同一内存空间，故共用变量与其各成员的地址相同。（3）不能对共用变量进行初始化（注意：结构变量可以）；也不能将共用变量作为函数参数，以及使函数返回一个共用数据，但可以使用指向共用变量的指针。（4）共用类型可以出现在结构类型定义中，反之亦然。

共用体和结构体区别

内部资料请勿COPY47区别:存储方式不同联系:两者可相互嵌套achkbchk变量的各成员同时存在任一时刻只有一个成员存在结构体与共用体structnode{charch[2];intk;}a;unionnode{charch[2];intk;}b;共用体示例

内部资料请勿COPY48structstu_score{intnum;charname[20];inttype;

/*type值为0时五分制，type值为1时百分制*/

unionmixed{intiscore;/*五分制*/

floatfscore;/*百分制*/}score;};main(){structstu_scorestud1;scanf("%d%s%d",&stud1.num,,&stud1.type);if(stud1.type==0)scanf("%d",&stud1.score.iscore);elseif(stud1.type==1)scanf("%f",&stud1.score.fscore);if(stud1.type==0)printf("%d,%s,%d,%d",stud1.num,,stud1.type,stud1.score.iscore);elseif(stud1.type==1)printf("%d,%s,%d,%f",stud1.num,,stud1.type,stud1.score.fscore);}自定义数据类型7-枚举类型

内部资料请勿COPY491．枚举类型的定义:enum枚举类型名{取值表}；例如，enumweekdays{Sun,Mon,Tue,Wed,Thu,Fri,Sat}；２．枚举变量的定义──与结构变量类似（1）间接定义：例如，enumweekdaysworkday;（2）直接定义：例如，enum{Sun,Mon,Tue,Wed,Thu,Fri,Sat}workday;３．说明（1）枚举型仅适应于取值有限的数据。（2）取值表中的值称为枚举元素，枚举元素是常量。在Ｃ编译器中，按定义的顺序取值0、1、2、...。所以枚举元素可以进行比较，比较规则是：序号大者为大。例如，上例中的Sun=0、Mon=1、……、Sat=6，所以Mon>Sun、Sat最大。（3）