《C语言程序设计》课件第8章

本章目录8.1结构体8.2结构体数组8.3指向结构体类型数据的指针8.4链表8.5共用体前面已经介绍了C语言中的大部分数据类型，包括基本类型、数组类型、指针类型等。但在实际生活中有许多需要由不同类型的数据共同描述的实体，比如通讯录可由姓名、地址、电话、邮政编码等组成；一个学生的情况可由姓名、性别、年龄、成绩、家庭住址等数据项组成。C语言提供了这样一种数据结构，它们是结构体类型和共用体类型。

8.1结构体在C语言中，基本类型数据在系统已经有系统定义好了，编程人员只要直接应用它们就可以了。但是结构体是一种构造类型，在使用该类型的数据之前必须先给出类型定义即先定义后使用。8.1.1结构体类型的定义1.结构体类型的定义的一般形式为：struct结构体类型名{数据类型1成员名1；数据类型2成员名2；┋数据类型n成员名n；｝；结构体名的命名应该遵守标识符的命名规则。打括号内可以包含若干个成员，每个成员应有具体的数据类型。8.1结构体例如，描述日期定义的结构体类型：structdate｛intyear；intmonth；intday；｝；其中date是结构体名，该结构体类型是由三个成员组成。成员都是整型，编者可根据自己需求编写成员，成员的数据类型可以是任何数据类型，当然也可以包含结构体类型。注意最后大括号后要加上分号“；”作为结束。8.1结构体例如structstudent{charname[8]；

charsex[2]；

structdatebirthday；

};结构体类型structstudent的定义中，成员birthday是结构体类型，这就形成了结构体的嵌套。结构体类型的定义完成后，我们就可以应用该结构体类型的变量，它的使用和int,float等相同，如上例中定义了structdate结构体类型，在structstudent结构体定义中用到了structdate结构体类型的变量birthday。8.1结构体8.1.2结构体变量的定义

定义了结构体类型之后，就可以在此基础上定义结构体类型的变量，结构体变量的定义可以采用以下三种方法：1．先定义结构体类型再定义变量，例如上面已定义了一个结构体类型structdate，可以用它来定义变量：structdatebirthday；2．在定义类型的同时定义变量上面可改写为：例如structdate｛intyear；intmonth；intday；｝student1,student2；即在结构体类型定义后直接写出变量名。8.1结构体3．直接定义结构体类型变量，即不定义结构体类型名，在写出结构体类型后直接写出变量名struct｛intyear；intmonth；intday；｝student1,student2；定义变量后，编译系统会为它分配存储空间，存储空间的大小是结构体各成员变量所占内存单元的总和。结构体类型变量说明：１)类型与变量的概念不同。对结构体类型变量来说，在定义时一般先定义结构体类型，然后再定义该结构体类型的变量。只能对结构体类型的变量赋值、存取或运算，而不能对结构体类型赋值、存取或运算。在编译时对类型是不分配存储空间的，只对变量分配存储空间。8.1结构体

２)对结构体变量中的成员,可以单独使用，其作用与地位相当于普通变量。３)结构体类型的成员可以是一个已定义的结构体类型变量。如结构体类型structstudent中的structdatebirthday；这样先定义了一个structdate类型，它包括三个成员,然后在定义结构体类型structstudent时，成员birthday被定义为structdate类型。４)结构体类型中的成员可以与程序中的变量同名，二者不代表同一对象。8.1结构体8.1.3结构体变量的引用在定义结构体变量以后，可以引用这个变量中的成员。但是怎样引用？在C语言中一般不整体引用。对结构体变量的使用主要是对其成员的操作，引用成员的一般形式为：结构体变量名.成员名其中“.”是成员运算符，它优先级别最高，引用结构体变量应遵守以下规则：1．不能将一个结构体变量作为一个整体加以引用，只能引用结构体变量中的成员。经常把结构体变量名.成员名看作一个整体进行操作。例如：student1.year=2008;student1.month=8；8.1结构体2．如果成员本身又属于一个结构体类型，则需要再次使用取成员运算符“．”，这样逐级的应用成员运算符找到最低级的成员。例如：student1.birthday.year3．对结构体类型变量的成员所能执行的操作，与具有相同类型的普通变量所能执行的操作相同，包括赋值、输入输出、运算等。例如：student1.year++；4.C语言允许两个同类型的结构体变量之间相互赋值。在执行“student2=student1；”不允许用赋值语句将一组常量直接赋给一个结构体变量。输入下面语句不合法：Student1={″WangLi″,18,M′,12,15,1974,89101,89.5}；下面通过程序来应用结构体变量的成员。8.1结构体例8.1

学生信息输出。structdate{intmonth;intday;intyear;};structstud_type{charname[20];intage;charsex;structdatebirthday;longnum;floatscore;};main(){8.1结构体structstud_typestudent1={"WangLi",20,'M',12,15,1978,89101,89.5};structstud_typestudent2;student2=student1;printf("student1:%s,%d,%c,%d,%d,%d,%ld,%5.2f\n",,student1.age,student1.sex,student1.birthday.month,student1.birthday.day,student1.birthday.year,student1.num,student1.score);printf("student2:%s,%d,%c,%d,%d,%d,%ld,%5.2f\n",,student2.age,student2.sex,student2.birthday.month,student2.birthday.day,student2.birthday.year,student2.num,student2.score);}运行情况如下：8.2结构体数组一个结构体变量中可以存放一组数据（如一个学生的考号、姓名、成绩等数据）。如果有10个学生的数据需要参加运算，显然应该用数组，这就是结构体数组。结构体数组与以前介绍过的数值型数组不同之处在于每个数组元素都是一个结构体类型的数据，它们都分别包括各个成员（分量）项。8.2.1定义结构体数组和定义结构体变量的方法相仿，只需说明其为数组即可。例如：structstudent{intnum; charname[20];charsex;intage;floatscore;charaddr[30];}structstudentstu[3];8.2结构体数组以上定义了一个数组stu,数组有3个元素，均为structstudent类型数据。也可以直接定义一个结构体数组，例如：structstudent{intnum;...}stu[3]；或者struct{intnum;...}stu[3];8.2结构体数组8.2.2结构体数组的初始化1.与其他类型的数组一样，对结构体数组可以初始化。结构体数组初始化的一般形式是在定义数组的后面加上“＝｛初值表列｝；”例如：structstudent{intnum;charname[20];charsex;intage;floatscore;charadd[30];}stu[3]={{10101,”lilin”,‘M’,18,87.5,”103BeijingRoad”},{10102,”Zhangfun”,’M’,19,99,”130ShanghaiRoad”},{10104,”WangMin”,’F’,20,78.5,”1010ZhongshanRoad”}};8.2结构体数组定义数组stu时，元素个数可以不指定，即写成以下形式：stu[]={{…}，｛…｝，｛…｝}；数组成员见图8-1

numnamesexagescoreaddr101011010210104LiLinZhangFunWangMingMMF18192087.59978.5103BingjiRoad103ShanghiRoad1010ZhongshanRoad数组各元素在内存中连续存放。编译时，系统会根据给出初值的结构体常量的个数来确定数组元素的个数。一个结构体常量结构体中全部成员的值。8.2结构体数组当然，数组的初始化也可以用以下形式：structstudent{intnum;charname[20];charsex;intage;floatscore;charadd[30];};structstudentstu[]={{…}，｛…｝，｛…｝}；即先声明本类型，然后定义数组为该结构体类型，在定义数组时初始化。8.2结构体数组2．举一个简单的例子来说明结构体数组的定义和引用。例8.2对候选人得票的统计程序。设有3个候选人，每次输入一个得票的候选人的名字，要求最后输出各人得票结果。程序如下：#include<stdio.h>#include<string.h>structperson{charname[20];intcount;}leader[3]={"Li",0,"Zhang",0,"Fun",0};main(){inti,j;charleader_name[20];for(i=1;i<=10;i++)8.2结构体数组{scanf("%s",leader_name);for(j=0;j<3;jif(strcmp(leader_name,leader[j].name)==0)leader[j].count++;}printf("\n");for(i=0;i<3;i++)printf("%5s:%d\n",leader[i].name,leader[i].count);}运行结果：8.2结构体数组程序定义一个全局的结构体数组leader，它有3个元素，每一个元素包含两个成员name（姓名）和count（票数）。在定义数组时使之初始化，使3位候选人的票数都先置零。在主函数中定义字符数组leader_name,它代表被选人的具体人名，然后把它与3个候选人姓名相比，看它和哪一个候选人的名字相同。注意leader_name是和结构体数组中的leader[j].name相比，leader[j]是结构体数组中的字符数组leader的第j个元素，它包含两个成员项，leader_name应该和leader数组第j个元素的name成员相比。若j为某一值时，输入的姓名与leader[j].name相等，就执行”leader[j].count++”，由于成员运算符”.”优先于自增运算符”++”，因此它相当于（leader[j].count）++，使leader[j]的成员count的值加1。在输入和统计结束之后，将3人的名字和得票数输出。8.3指向结构体类型数据的指针

结构体变量的指针就是该结构体变量在内存中的起始地址。可以设一个指针变量，用来指向一个结构体变量，指针变量的值是结构体变量的起始地址。指针变量也可以用来指同结构全数组中的元素。8.3.1指向结构体变量的指针下面通过一个简单例子来说明指向结构体变量的指针变量的应用。例8.3指向结构体变量的指针的应用#include<stdio.h>#include<string.h>structstudent{longnum;charname[20];charsex;floatscore;};main(){structstudentstu_1,*p;8.3指向结构体类型数据的指针

p=&stu_1;stu_1.num=89101;strcpy(stu_1.name,"wangwei");stu_1.sex='M';stu_1.score=89.5;printf("No.:%ld\nname:%s\nsex:%c\nscore;%f\n",stu_1.num,stu_1.name,stu_1.sex,stu_1.score);printf("No.:%ld\nname:%s\nsex:%c\nscore:%f\n",(*p).num,(*p).name,(*p).sex,(*p).score);}运行结果：8.3指向结构体类型数据的指针声明了structstudent类型，在主函数中定义一个structstudent类型的变量stu_1。同时又定义一个指针变量p，它指向一个structstudent类型的数据。在函数的执行部分将结构体变量stu_1的起始地址赋给指针变量p，也就是使p指向stu_1中的成员num，依此类推。第二个printf函数也是用来输出stu_1各成员的值，只是使用了(*p).num这样的形式。（*p）表示p指向的结构体变量，(*p).num是p指向的结构体变量中的成员num。注意*p两侧的括号不可省，因为成员运算符“.”优先于“*”运算符，*p.num就等价于*(p.num)了。两个printf函数输出的结果是相同的。为了使用方便和使之直观，可以把(*p).num改用p—>name。也就是说，以下3种形式等价：结构体变量.成员名(*P).成员名p—>成员名上面程序中最后一个printf函数中的输出项表列可以改写为p—>num,p—>name,p—>sex,p—>score其中—>称为指向运算符。8.3指向结构体类型数据的指针8.3.2指向结构体数组的指针对构体数组及其元素可以用指针变量来指向。例8.4指向结构体数组的指针的应用。#include<stdio.h>main(){structstudent{intnum;charname[20];charsex;intage;}stu[3]={{10101,"LiLin",'M',18},{10102,"ZhangFun",'M',19},{10104,"Wangmin",'F',20}};structstudent*p;printf("No.Namesexage\n\n");for(p=stu;p<stu+3;p++)printf("%5d%-10s%4c%6d\n",p->num,p->name,p->sex,p->age);}运行结果

8.3指向结构体类型数据的指针p是指向structstudent结构体类型数据的指针变量。在for语句中先使p的初值为stu，也就是数组stu第一个元素的起始地址。在第一次循环中输出stu[0]的各个成员值。然后执行p++，使p自加1。p指向了结构体数组中的stu[1]即“走“过了本例中2+20+1+2＝25字节的存储单元，p指向了stu[1]，输出stu[1]中的各成员值之后，在进行下一此循环。注意：程序已定义了p是一个指向structstudent类型数据的指针变量，它用来指向一个structstudent类型的数据，不应用来指向stu数组元素中的某一成员。下面的用法是不对的：p=stu[0].name;编译时将给“警告”信息，表示地址的类型不匹配。8.4链表链表是一种常见的重要的数据结构。它是动态地进行了存储分配的一种结构。我们知道，用数组存放数据时，必须事先定义固定的长度（即元素个数）。有时候会因为这样浪费存储空间，这时候使用链表是最好的选择，链表没有这种缺点，它根据需要开辟内存单元。链表不需要连续的存储空间，随时实现数据的插入和删除等操作。8.4.1简单链表的定义和使用链表主要是动态的存储数据。链表中可以包含若干个结点即元素，每个结点最少包含两部分内容：数据和下一个结点的地址。通过结点的地址信息将各结点连接起来。在链表结构中，只要知道了第一个结点的地址就可以访问链表中的其他结点。链表有一个“头指针”变量，图中以head表示，它存放一个地址，该地址指向一个元素。head指向第一个结点；第一个结点又指向第二个结点……直到最后一个结点，该结点不再指向其他结点，它称为“表尾”，它的地址部分放一个“NULL”(表示“空地址”)，链表到此结束。8.4链表可以看到链表中各结点在内存中可以不是连续存放的。要找某一结点，必须先找到上一个结点，根据它提供的下一结点地址才能找到下一个结点。如果不提供“头指针”（head），则整个链表都无法访问。链表如同一条铁链一样，一环扣一环，中间是不能断开的。打个通俗的比方：幼儿园的老师带领孩子出来散步，老师牵着第一个小孩的手，第一个小孩的另一只手牵着第二个孩子……这就是一个“链”，最后一个孩子有一只手空着，他是“链尾”。要找这个队伍，必须先找到老师，然后顺序找到每一个孩子。可以看到，这种链表的数据结构，必须利用指针变量才能实现，即一个结点中应包含一个指针变量，用它存放下一结点的地址。headnumfloatnext081001980810298808103066NULL……图8-28.4链表用结构体变量作链表中的结点是最合适的。一个结构体变量含若干成员，这些成员可以是数值类型、字符类型、数组类型，也可以是指针类型。我们用这个指针类型成员来存放下一个结点的地址。通常链表结点可以定义如下的结构体类型：structstudent{intnum;floatscore;structstudent*next;};其中成员num和score用来存放结点中的有用数据（用户需要用到的数据），next是指针类型的成员，它指向structstudent类型数据（这就是next所在的结构体类型）。一个指针类型的成员既可以指向其他类型的结构体类型的数据。现在，next是structstudent类型中的一个成员，它又指向structstudent类型的据。用这种方法就可以建立链表，见图8-2。图8.2中每一个结点都属于structstudent类型，它的成员next存放下一结点的地址，程序设计人员可以不必具体知道各结点的地址，只要保证下一个结点的地址放到前一结点的成员next中即可。请注意：上面只是定义了一个structstudent类型，并未实际分配存储空间。只有定义了变量才分配内存单元。下面通过一个例子来说明如何建立和输出一个简单链表8.4链表例8.5建立一个如图8-2所示的简单链表，它由3个学生数据的结点组成。输出各结点中的数据。#include<stdio.h>#defineNULL0structstudent{longnum;floatscore;structstudent*next;};voidmain(){structstudenta,b,c,*head,*p;a.num=08101;a.score=89.5;b.num=08102;b.score=90;c.num=08103;c.score=85;/*对结点的num和score成员赋值*/head=&a;/*将结点a的起始地址赋给头指针head*/a.next=&b;/*将结点b的起始地址赋给a结点的next成员*/8.4链表b.next=&c;/*将结点c的起始地址赋给b结点的next成员*/c.next=NULL;/*c结点的next成员不存放其他结点地址*/p=head;/*使p指针指向a结点*/do{printf("%8ld%5.1f\n",p->num,p->score);/*输出p指向的结点的数据*/p=p->next;/*使p指向下一结点*/}while(p!=NULL);/*输出完c结点后p的值为NULL*/}运行结果：8.4链表开始时使head指向a结点，a.next指向b结点，b.next指向c结点，这就构成链表关系。“c.next=NULL”的作用是使c.next不指向任何有用的存储单元。在输出链表时要借助p，先使p指向a结点，然后输出a结点中的数据，“p=p->next”是为输出下一个结点作准备。p->next的值是b结点的地址，因此执行“p=p->nxet”后p就指向b结点，所以在下一次循环时输出的的是b结点中的数据。上例是比较简单的，所有结点都是在程序中定义的，不是临时开辟的，也不能用完后释放，这种链表称为“静态链表”。8.4链表8.4.2动态链表处理动态链表所需的函数链表结构是动态地分配存储的，即在需要时才开辟一个结点的存储单元。Ｃ语言的库函数提供了以下有关函数。1）Malloc函数其函数的原型为void*malloc(unsignedintsize);其作用是在内存的动态存储区中分配一个长度为size的连续空间。此函数的值（即“返回值”）是一个指向分配该起始地址的指针（类型为void）。如果此函数未能成功地执行（例如内存空间不足），则返回空指针（NULL）。2）Calloc函数其函数原型为void*calloc(unsignedn,unsignedsize);其作用是在内存的动态存储区中分配n个长度为size的连续空间。函数返回一个指向分配哉起始地址的指针；如果分配不成功，返回NULL。用calloc函数可以为一维数组开辟动态存储空间，n为数组地素个数，每个结点长度为size.8.4链表3）free函数其函数原型为voidfree(void*p)其作用是释放由p指向的内存区，使这部分内存区能被其他变量使用。P是最近一次调用calloc或malloc函数时返回的值。free函数无返回值。ANSIC提供的malloc和calloc函数规定为void*类型。2．动态链表有了上面的函数，下面就可以对链表进行操作了，包括建立链表、插入、删除链表中的一个结点和输出。1）建立动态链表是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点数据，并建立起前后相链的关系。2）对链表的插入是指将一个结点插入到一个已有的链表中。若已有一个学生链表，各结点是按其成员项num（学号）的值由小到大顺序排列的，今要插入一个新生的结点，要求按学号的顺序插入。为了能做到正确插入，必须解决两个问题：（１）怎样找到插入的位置。（２）怎样实现插入。8.4链表3）删除动态链表中指定的结点。以指定的学号作为删除结点的标志，还需要考虑链表是空表（无结点）和链表中找不到要删除的结点的情况。4）将链表中各结点的数据依次输出。下面举例说名如何建立链表、如何插入一个结点及删除一个结点和输出。例8.6建立一个存放学生序号和成绩的链表，学生信息有键盘输入，数目不定，当输入学号为0时，建表结束，在进行删除一个学生信息，输出结果，最后插入该学生信息，输出结果。#include<stdio.h>#include<malloc.h>#defineNULL0#defineLENsizeof(structstudent)structstudent{longnum;floatscore;structstudent*next;};intn;/*n为全局变量，本文件模块中各函数均可使用它*/8.4链表structstudent*creat()/*定义函数，此函数带回一个指向链表头的指针*/{structstudent*head;structstudent*p1,*p2;n=0;p1=p2=(structstudent*)malloc(LEN);/*开辟一个新单元*/scanf("%ld,%f",&p1->num,&p1->score);head=NULL;while(p1->num!=0){n=n+1;if(n==1)head=p1;elsep2->next=p1;p2=p1;p1=(structstudent*)malloc(LEN);scanf("%ld,%f",&p1->num,&p1->score);}p2->next=NULL;return(head);}8.4链表structstudent*del(structstudent*head,longnum){structstudent*p1,*p2;if(head==NULL){printf("\nlistnull!\n");gotoend;}p1=head;while(num!=p1->num&&p1->next!=NULL){p2=p1;p1=p1->next;}if(num==p1->num){if(p1==head)head=p1->next;elsep2->next=p1->next;printf("delete:%ld\n",num);n=n-1;}elseprintf("%ldnotbeenfound!\n",num);end:return(head);}8.4链表structstudent*insert(structstudent*head,structstudent*stud){structstudent*p0,*p1,*p2;p1=head;/*使p1指向第一个结点*/p0=stud;/*p0指向要插入到点*/if(head==NULL)/*原来的链表是空表*/{head=p0;p0->next=NULL;/*使p0指向的结点作为头结点*/}else{while((p0->num>p1->num)&&(p1->next!=NULL)){p2=p1;/*使p2指向刚才p1指向的结点*/p1=p1->next;}/*p1后移一个结点*/if(p0->num<=p1->num){if(head==p1)8.4链表head=p0;/*插到原来第一个结点之前*/elsep2->next=p0;/*插到p2指向的结点之后*/p0->next=p1;}else{p1->next=p0;p0->next=NULL;/*插到最后的结点之后*/}}n=n+1;/*结点数加１*/return(head);}voidprint(structstudent*head){structstudent*p;printf("\nNow.these%drecordsare:\n",n);p=head;if(head!=NULL)do{printf("%ld%5.1f\n",p->num,p->score);8.4链表p=p->next;}while(p!=NULL);}main(){structstudent*head,stu;longdel_num;printf("inputrecords;\n");head=creat();/*建立链表，返回头指针*/print(head);/*输出全部结点*/printf("\ninputthedeletednumber:");scanf("%ld",&del_num);/*输入要删除的学号*/head=del(head,del_num);/*删除后链表的头地址*/print(head);printf("\ninputtheinsertedrecord:");scanf("%ld,%f",&stu.num,&stu.score);/*输入要插入的结点*/head=insert(head,&stu);/*插入一个结点，返回头结点地址*/print(head);}8.4链表

运行结果：

8.4链表请注意：#define命令行，令NULL代表0，用它表示“空地址”。LEN代表structstudent类型数据的长度，sizeof是“求字节数运算符”。creat函数，它是指针类型，即此函数带回一个指针值，它指向一个structstudent类型数据。实际上此creat函数带回一个链表起始地址。malloc(LEN)的作用是开辟一个长度为LEN的内存区，LEN已定义为sizeof（structstudent）,即结构体structstudent的长度。Malloc带回的是不指向任何类型数据的指针(void*)。而p1、p2是指向structstudent类型数据的指针变量，因此必须用强制类型转换的方法使指针的基类型改变为structstudent类型，在malloc(LEN)之前加了“(structstudent)”，它的作用是使malloc返回的指针转换为指向structstudent类型数据的指针。注意“*”号不可省略，否则变成换成structstudent类型了，而不是指针类型了。8.4链表最后一行return后面的参数是head(head已定义为指直变量，指向structstudent类型数据)。因此函数返回的是head的值，也就是链表的头地址。n是结点个数。这个算法的思路是让p1指向新开辟的结点，p2指向链表中最后一个结点，把p1所指的结点连接在p2所指的结点后面，用“p2—>next=p1”来实现。将链表中各结点的数据依次输出。首先要知道链表第一个结点的地址，也就是要知道head的值。Head的值由实参传过来，也就是将已有的链表的头指针传给被调用的函数，在print函数中从head所指的第一个结点出发顺序输出各个结点。然后设一个指针变量p，先指向第一个结点，输出p所指的结点，然后使p后移一个结点，再输出，直到链表的尾结点。从一动态链表中去一个结点，并不是真正从内存中把它抹掉，而是把它从链表中分离开来，只要撤销原来的