第十一章结构体与共用体链表.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第十一章 结构体与共用体,简单链表,例题1：某学生，姓名是,Li，,学号是9800，化学成绩是85。请编写程序输出这些数据。见程序：,main(),char name4=Li;,int,num=9800;,int,score=85;,printf,(%s,%d,%c,%f,name,num,sex,score);,如果有100个学生，则更麻烦.,TC,允许我们定义自己的数据类型，以解决特定的实际问题。为了很好地解决例题1，我们可以定义一种叫,struct,student,的数据类型。,结构体类型也是属于一种构造类型数据，它将不同类型的数据项组织成一个组合项，这些组合项中的数据项是互相联系的。,定义一个,结构体类型,的一般形式：,struct,结构体名,成员表列；,例如：,对于一名学生，有如下不同类型的属性：,学号、姓名、年龄、性别、成绩、地址等。,要表示一个学生的六个方面不同类型的有关数据,就可以定义一个结构体类型。,11.1 结构体类型概述,struct student,int num;,char name10;,char sex;,int age;,float score;,char addr30;,其中：,struct,是关键字，表示结构体类型。,student,是结构体类型名，,struct,student,和标准类型名(,int、float),一样可以用作定义变量的类型。花括号内是结构体中的各个成员，每个成员都应进行类型说明。,11.1 结构体类型概述,结构体名相当,float,int,分号不能少,成员表列,一、先定义结构体类型，再定义变量名,例如：,struct student,int num;,char name10;,char sex;,int age;,float score;,char addr30;,struct student student1，student2；,上面的,student1,和,student2,是,struct student,类型的变量，它们具有,struct student,类型的结构。,定义结构体变量后，系统为变量分配内存单元。可用,sizeof,(student1),来计,student1,和,student2,各占49个字节。,11.2 定义结构体类型变量的方法,二、在定义结构体类型的同时定义变量,例如：,struct student,int num;,char name10;,char sex;,int age;,float score;,char addr30;,student1，student2；,11.2 定义结构体类型变量的方法,三、直接定义结构体类型变量(不写类型名),例如：,struct,int num;,char name10;,char sex;,int age;,float score;,char addr30;,student1，student2；,11.2 定义结构体类型变量的方法,说明：,1.定义类型与定义变量是不同的，在编译时对类型不分配空间，只对变量分配存储空间。,2.只能对变量赋值、存取或运算，而对结构体类型不可以。,3.对结构体中的成员可以单独使用，它的作用和地位相当于普通变量。,4.,可以用,sizeof,运算符测一个类型数据的长度。,n=,sizeof,(,struct,student),或,n=,sizeof,(student1),n=,sizeof,(,int,),n=,sizeof,(float),11.2 定义结构体类型变量的方法,5.成员也可以是结构体变量。,struct,student,int,num;,char name20；,char sex；,int,age;,struct,date birthday；,char,addr,30；,student1，student2；,struct,date,int,month；,int,day；,int,year；,；,num,name,sex,age,birthday,addr,month,day,year,一个结构体类型的变量,不能,作为一个整体进行输入和输出，只能对结构体变量中的各个成员进行输入、输出和运算。,scanf,(“%d,%s,%c,%d,%f,%s”,printf,(“%d,%s,%c,%d,%f,%s”,student1);,11.3 结构体类型变量的引用,引用方式：结构体变量名.成员名,例如：,scanf,(“%d”,student2.num=student1.num;,printf,(“%d,%d”,student1.num,student2.num);,“,.,”,是成员运算符,表示在,student1,结构体变量中找出成员,num,的值。其优先级最高，结合性为自左向右。,如,student1.num+100;,若结构体类型嵌套一个结构体类型，则采用逐级访问的方法，只能对最低级的成员进行访问。,student1.birthday.year,访问结构体变量,student1,的成员出生年份。而不能用,student1.birthday,访问,birthday。,结构体变量的成员可以和普通变量一样进行各种运算,student2.score=student1.score;,student1.age+;,+student1.age;,例如：,struct student,long int num;,char name20；,char sex;,char addr20;,a=89031,Li Lin,M,123 Beijing Road;,Printf,(“%ld,%s,%c,%sn”,a.num,a.name,a.sex,a.,addr,);,11.4 结构体类型变量的初始化,结构体数组中的每个元素都是一个结构体类型的数据，它们都分别包括各个成员项。,例如：要表示3名学生的学号、姓名和成绩。,struct student,int num;,char name 20;,float score;,struct student stu3=1000,“li ming”,70,1001,“wang fan”,80,1002,“zhang yan”,65.5,;,11.5 结构体数组,程序举例：有四个学生，每个学生包括学号、姓名、成绩，要求找出成绩最高者的姓名和成绩。,S11_ex1.c,main(),struct student,int num;,char name20;,int score;,struct student stu4;,int i,k=0,max;,printf(,请按行输入学生的记录:,n);,11.5 结构体数组,for(i=0;i4;i+),scanf(%d%s%d”,for(max=stu0.score,i=1;imax),max=stui.score;k=i;,printf(n,最高成绩为:,n);,printf(”No.:%dnname:%snscore:%dn”,stuk.num,stuk.name,stuk.score);,11.5 结构体数组,11.6.1 指向结构体变量的指针,一个结构体变量的指针就是该变量所占据的内存空间的起始地址，可以设一个指针变量指向一个结构体变量。,例如：,struct student,int num;,char name20;,int score;,stu,;,struct,student *p=,11.6 指向结构体类型数据的指针,如果要表示,stu,变量中的,num,成员项,可写成下面三种形式：,1.,stu.num,2.(*p).num,3.p-num,11.6 指向结构体类型数据的指针,10.6.2 指向结构体数组的指针,对结构体数组也可以用指针变量来指向。,例如：已知三名学生的有关数据，现全部输出。,s11_4.c,struct student,int num;,char name10;,char sex;,int age;,stu,3=10101,Li Lin,M,18,10102,Zhang Fun,M,19,10104,Wang Min,F,20;,main(),struct,student*p;,for(p=,stu,;pnum,p-name,p-sex,p-age);,10.3 共用体,union student,int,num;,float score;,union student b;,b.num=1;b.score=2;,sizeof,(b),为4,struct,student,int,num;,float score;,;,struct,student a;,a.num=1;a.score=2;,sizeof,(a),为6,a,b,num,score,num,score,11.8.1 共用体类型的定义和变量的定义方式,使几个不同的变量共占同一段内存单元的结构，称为,“共用体”类型的结构。它也是一种构造类型的数据。,共用体类型的定义形式：,union,共用体名,成员表列;,例如：,union data,int i;,char ch;,float f;,union data a,b,c;,11.8 共 用 体,定义形式也可以:,union data,int,i;,char,ch,;,float f;,a,b,c；,11.8.2 共用体变量的引用方式,不能直接引用共用体变量本身,scanf,(“%d”,printf,(“%d”,a);,而,应引用共用体变量的成员。,例如：,a.i,a.ch,a.f,11.8.3,共用体类型数据的特点,1.,共用体与结构体的不同：,结构体变量所占内存长度为各成员所占内存长度之和；,而共用体变量所占内存长度为最长的成员的长度，所有的成员共用同一段内存，同一时刻只有一个成员起作用。,11.8 共 用 体,2.共用体变量的地址和它的各成员项的地址是同一地址。如：&,a、&a.i、&a.ch、&a.f,都是同一地址值。,3.共用体变量不能赋初值。,4.共用体和结构体可以互相成为其中的成员；,5.共用体变量起作用的成员是最后一次存放值的成员。,例如：,a.i=10;,a.ch=a;,printf(“%d”,a.i);,a.f=1.5;,printf(“%f”,a.f);,则当前共用体变量中,，,只有,a.f,是有效的。,11.8 共 用 体,#,include,union un,int,i;,char c2;,main(),union un x;,x.c0=10;,x.c1=1;,printf,(n%d,x.i);,266,思考题1：求下面程序的输出结果。,main(),union time,long i;,int k5;,char c;,struct date,int,cat;,union time cow;,double dog;,dt,;,union time max;,printf(%dn,sizeof(,dt,)+sizeof(max);,说明：,sizeof(),是求类型长度的运算符，即在内存中所占的字节数。,20+10=30,思考题2：求下面程序的输出结果。,struct ks,int,a;,int,*b;,s4,*p;,main(),int,n=1,i;,printf,(n);,for(i=0;ia,(p+)-a);,s0.a=1,s1.a=3,s2.a=5,s3.a=7,7,3,右结合,先观察链表示意图，后理解链表概念。,某3位同学的物理成绩分别为96，89，93。分别用数组和链表存储这些数据的示意图如下：,613 609 605 601,93,89,96,p,指针,89,空,93,指针,96,3个节点的链表：,3个元素的数组：,float a3;,a,11.9简单链表,11.9.1 链表的概念,链表是一种动态数据结构，可以用来表示顺序访问的线性群体。,链表是由系列结点组成的，结点可以在运行时动态生成。,每一个结点包括数据域和指向链表中下一个结点的指针（即下一个结点的地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称为单链表。,链表不要求逻辑上相邻的元素在物理位置上也相邻，在内存允许的范围内，占用空间大小不受限制，摒弃了数组的弱点。,11.9.2 数组与链表的比较,数组：仅能实现静态存储。,链表：可以实现动态存储。,链表的使用步骤：,建立链表 (使用,malloc,函数),访问链表 (使用*,p,表达式),释放链表 (使用,free,函数),p,指针,89,空,93,指针,96,1链表结构,（1）头指针变量,head,指向链表的首结点。,（2）每个结点由2个域组成：,1）数据域存储结点本身的信息。,2）指针域指向后继结点的指针。,（3）尾结点的指针域置为“,NULL（,空）”，作为链表结束的标志,Qian,Sun,Li,Zhou,Wu,Wang,Head,链表结构的定义,struct,student,char name10;,struct,student*next;,;,next,为,struct,student,类型指针变量，指向下一个结点。,结点的变量或指针变量的定义：,struct,student node,*head;,node,可以存放一个学生结点,指针,head,可以存放学生结点的地址。,相关库函数,1.,void *,malloc,(unsigned,int,size);,用途：在内存的动态存储区中分配一个,size,长度的连续存储空间。,返回值：返回一个指向分配域地址的指针（类型为,void）;,若未成功，则返回空指针（,NULL）,例如：,int,*p;,p=(,int,*),malloc,(8);,p,指示系统分配的4个整型存储单元的起始地址,也可看成包含4个数组元素的,p,数组：,p0,p1,p2,p3,2.,void free(void*p);,用途：释放由指针变量,p,所指示的内存区域。,例如：,free(p);,通过函数,free,将已分配的内存区域交还系统，使系统可以重新对其进行分配。,11.9.3 建立链表,尾插法建立单链表,特点：头指针固定不变，新产生的结点总是链接到链表的尾部。,操作步骤：,（1）设,head,为链表头，,last,为链表尾结点，,head=last=NULL;,（2）,生成新结点，由,p,指针指示，并将新结点的地址域,清空：,p-next=NULL;,（3）,如果,head,为,NULL，,则,head=p;,否则,last-next=p;,（4）last=p;,（5）,重复（2）（4），继续建立新结点。,#,include,stdio,.h,struct,s,int,a;,struct,s*q;,;,#define LEN,sizeof,(,struct,s),main(),struct,s*head,*p1,*p2;,int,m,i,n;,for(i=1;ia=m;,if(i=1)head=p1=p2;,else,p1-q=p2;p1=p2;,if(i=3)p2-q=NULL;,for(p1=head;p1!=NULL;),printf,(n%d,p1-a);p1=p1-q;,while(head),p1=head-q;head-q=NULL;,free(head);head=p1;,例 三位同学的化学成绩分别是90，89，96。请分别用数组和链表存储这些数据。,main(),int,a3,i;,for(i=0;i3;i+),scanf,(%d,for(i=0;inext，p,结点往前移动一个结点；,（4）若,inext=head，head=q;,（6）,若,inext=q，q-next=NULL;,（7）,否则，将,q,结点插入到第,n,个结点之后，即插入到,r,结点与,p,结点之间：,r-next=q，q-next=p;,（8）,返回链表头,head。,图13-1 将指针,q,所指结点插入第,n,个结点之后,(,b),插入到第2个结点之后,Head,p,101,Zhang,90,103,Wang,80,N,UL,L,105,Li,70,(,a)head,指示已有链表，,q,指示待插入结点,q,104,Zhao,70,Head,r,101,Zhang,90,q,104,Zhao,60,103,Wang,80,p,N,UL,L,105,Li,70,11.9.5,链表的删除操作,删除第,n,个结点,（1）,p=head，q,指针指向,p,所指结点的前1个结点；,（2）,i,为访问过的结点数目；,（3）,i+，q=p，p=p-next，p、q,移动1个结点；,（4）若,p!=NULL,且,inext;,（6）,若,head=NULL，,链表为空，不能删除；,（7）若,p=NULL，,第,n,个结点不存在，不能删除；,（8）找到第,n,个结点，删除,p,结点：,q-next=p-next;,（9）,返回,head。,图13-2 删除第,n,个结点,(,a)head,指示已有链表,Head,p,101,Zhang,90,103,Wang,80,N,UL,L,105,Li,60,101,Zhao,70,(,b),删除第3个结点,q,p,Head,101,Zhang,90,103,Wang,80,N,UL,L,105,Li,60,101,Zhao,70,