第十一章--结构体与共用体链表课件

第十一章第十一章结构体与共用体结构体与共用体简单链表简单链表例例题题1：某某学学生生，姓姓名名是是Li，学学号号是是9800，化化学学成成绩绩是是85。请编写程序输出这些数据。见程序：请编写程序输出这些数据。见程序：main()charname4=Li;intnum=9800;intscore=85;printf(%s,%d,%c,%f,name,num,sex,score);如如果果有有100个个学学生生，则则更更麻麻烦烦.TC允允许许我我们们定定义义自自己己的的数数据据类类型型，以以解解决决特特定定的的实实际际问问题题。为为了了很很好好地地解解决决例例题题1，我们可以定义一种叫我们可以定义一种叫structstudent的数据类型。的数据类型。结构体类型也是属于一种构造类型数据，它将不同类结构体类型也是属于一种构造类型数据，它将不同类型的数据项组织成一个组合项，这些组合项中的数型的数据项组织成一个组合项，这些组合项中的数据项是互相联系的。据项是互相联系的。定义一个定义一个结构体类型结构体类型的一般形式：的一般形式：struct结构体名结构体名成员表列成员表列；例如：例如：对于一名学生，有如下不同类型的属性：对于一名学生，有如下不同类型的属性：学号、姓名、年龄、性别、成绩、地址等。学号、姓名、年龄、性别、成绩、地址等。要表示一个学生的六个方面不同类型的有关数据要表示一个学生的六个方面不同类型的有关数据,就可就可以定义一个结构体类型。以定义一个结构体类型。11.1结构体类型概述结构体类型概述structstudentintnum;charname10;charsex;intage;floatscore;charaddr30;其中：其中：struct是关键字，表示结构体类型。是关键字，表示结构体类型。student是结是结构体类型名，构体类型名，structstudent和标准类型名和标准类型名(int、float)一样可以用作定义变量的类型。花括号内是结一样可以用作定义变量的类型。花括号内是结构体中的各个成员，每个成员都应进行类型说明。构体中的各个成员，每个成员都应进行类型说明。11.1结构体类型概述结构体类型概述结构体名相当结构体名相当float,int分号不能少分号不能少成员表列成员表列一、先定义结构体类型，再定义变量名一、先定义结构体类型，再定义变量名例如：例如：structstudentintnum;charname10;charsex;intage;floatscore;charaddr30;structstudentstudent1，student2；上面的上面的student1和和student2是是structstudent类型的变量，类型的变量，它们具有它们具有structstudent类型的结构。类型的结构。定义结构体变量后，系统为变量分配内存单元。可用定义结构体变量后，系统为变量分配内存单元。可用sizeof(student1)来计来计student1和和student2各占各占49个字节。个字节。11.2定义结构体类型变量的方法定义结构体类型变量的方法二、在定义结构体类型的同时定义变量二、在定义结构体类型的同时定义变量例如：例如：structstudentintnum;charname10;charsex;intage;floatscore;charaddr30;student1，student2；11.2定义结构体类型变量的方法定义结构体类型变量的方法三、直接定义结构体类型变量三、直接定义结构体类型变量(不写类型名不写类型名)例如：例如：structintnum;charname10;charsex;intage;floatscore;charaddr30;student1，student2；11.2定义结构体类型变量的方法定义结构体类型变量的方法说明：说明：1.定义类型与定义变量是不同的，在编译时对类型不定义类型与定义变量是不同的，在编译时对类型不分配空间，只对变量分配存储空间。分配空间，只对变量分配存储空间。2.只能对变量赋值、存取或运算，而对结构体类型不只能对变量赋值、存取或运算，而对结构体类型不可以。可以。3.对结构体中的成员可以单独使用，它的作用和地位对结构体中的成员可以单独使用，它的作用和地位相当于普通变量。相当于普通变量。4.可以用可以用sizeof运算符测一个类型数据的长度。运算符测一个类型数据的长度。n=sizeof(structstudent)或或n=sizeof(student1)n=sizeof(int)n=sizeof(float)11.2定义结构体类型变量的方法定义结构体类型变量的方法5.成员也可以是结构体变量。成员也可以是结构体变量。structstudentintnum;charname20；charsex；intage;structdatebirthday；charaddr30；student1，student2；structdateintmonth；intday；intyear；numnamesexagebirthdayaddrmonthday year一个结构体类型的变量一个结构体类型的变量不能不能作为一个整体进行输入和输作为一个整体进行输入和输出，只能对结构体变量中的各个成员进行输入、输出和出，只能对结构体变量中的各个成员进行输入、输出和运算。运算。scanf(“%d,%s,%c,%d,%f,%s”,&student1);printf(“%d,%s,%c,%d,%f,%s”,student1);11.3结构体类型变量的引用结构体类型变量的引用引用方式：结构体变量名引用方式：结构体变量名.成员名成员名例如：例如：scanf(“%d”,&student1.num);student2.num=student1.num;printf(“%d,%d”,student1.num,student2.num);“.”是成员运算符是成员运算符,表示在表示在student1结构体变量中找结构体变量中找出成员出成员num的值。其优先级最高，结合性为自左向右。的值。其优先级最高，结合性为自左向右。如如student1.num+100;v若结构体类型嵌套一个结构体类型，则采用逐级若结构体类型嵌套一个结构体类型，则采用逐级访问的方法，只能对最低级的成员进行访问。访问的方法，只能对最低级的成员进行访问。student1.birthday.year访问结构体变量访问结构体变量student1的成员出生年份。而不的成员出生年份。而不能用能用student1.birthday访问访问birthday。v结构体变量的成员可以和普通变量一样进行各种结构体变量的成员可以和普通变量一样进行各种运算运算student2.score=student1.score;student1.age+;+student1.age;例如：例如：structstudentlongintnum;charname20；charsex;charaddr20;a=89031,LiLin,M,123BeijingRoad;Printf(“%ld,%s,%c,%sn”,a.num,a.name,a.sex,a.addr);11.4结构体类型变量的初始化结构体类型变量的初始化结构体数组中的每个元素都是一个结构体类型的数据，结构体数组中的每个元素都是一个结构体类型的数据，它们都分别包括各个成员项。它们都分别包括各个成员项。例如：要表示例如：要表示3名学生的学号、姓名和成绩。名学生的学号、姓名和成绩。structstudentintnum;charname20;floatscore;structstudentstu3=1000,“liming”,70,1001,“wangfan”,80,1002,“zhangyan”,65.5;11.5结构体数组结构体数组程序举例：有四个学生，每个学生包括学号、姓名、程序举例：有四个学生，每个学生包括学号、姓名、成绩，要求找出成绩最高者的姓名和成绩。成绩，要求找出成绩最高者的姓名和成绩。S11_ex1.cmain()structstudentintnum;charname20;intscore;structstudentstu4;inti,k=0,max;printf(请按行输入学生的记录请按行输入学生的记录:n);11.5结构体数组结构体数组for(i=0;i4;i+)scanf(%d%s%d”,&stui.num,stui.name,&stui.score);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指向结构体变量的指针指向结构体变量的指针一个结构体变量的指针就是该变量所占据的内一个结构体变量的指针就是该变量所占据的内存空间的起始地址，可以设一个指针变量指向存空间的起始地址，可以设一个指针变量指向一个结构体变量。一个结构体变量。例如：例如：structstudentintnum;charname20;intscore;stu;structstudent*p=&stu;11.6指向结构体类型数据的指针指向结构体类型数据的指针 如果要表示如果要表示stu变量中的变量中的num成员项成员项可写成下面三种形式：可写成下面三种形式：1.stu.num2.(*p).num3.p-num11.6指向结构体类型数据的指针指向结构体类型数据的指针 10.6.2指向结构体数组的指针指向结构体数组的指针对结构体数组也可以用指针变量来指向。对结构体数组也可以用指针变量来指向。例如：已知三名学生的有关数据，现全部输出。例如：已知三名学生的有关数据，现全部输出。s11_4.cstructstudentintnum;charname10;charsex;intage;stu3=10101,LiLin,M,18,10102,ZhangFun,M,19,10104,WangMin,F,20;main()structstudent*p;for(p=stu;pnum,p-name,p-sex,p-age);10.3共用体共用体unionstudentintnum;floatscore;unionstudentb;b.num=1;b.score=2;sizeof(b)为为4structstudentintnum;floatscore;structstudenta;a.num=1;a.score=2;sizeof(a)为为6abnumscorenumscore11.8.1共用体类型的定义和变量的定义方式共用体类型的定义和变量的定义方式使几个不同的变量共占同一段内存单元的结构，称为使几个不同的变量共占同一段内存单元的结构，称为“共用体共用体”类型的结构。它也是一种构造类型的数据。类型的结构。它也是一种构造类型的数据。共用体类型的定义形式：共用体类型的定义形式：union共用体名共用体名成员表列成员表列;例如：例如：uniondatainti;charch;floatf;uniondataa,b,c;11.8共共用用体体定义形式也可以定义形式也可以:uniondatainti;charch;floatf;a,b,c；11.8.2共用体变量的引用方式共用体变量的引用方式不能直接引用共用体变量本身不能直接引用共用体变量本身scanf(“%d”,&a);printf(“%d”,a);而应引用共用体变量的成员。而应引用共用体变量的成员。例如：例如：a.ia.cha.f11.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共共用用体体#includeunionuninti;charc2;main()unionunx;x.c0=10;x.c1=1;printf(n%d,x.i);266思考题思考题1：求下面程序的输出结果：求下面程序的输出结果。main()uniontimelongi;intk5;charc;structdateintcat;uniontimecow;doubledog;dt;uniontimemax;printf(%dn,sizeof(dt)+sizeof(max);说明：说明：sizeof()是是求类型长度的运算求类型长度的运算符，即在内存中所符，即在内存中所占的字节数。占的字节数。20+10=30思考题思考题2：求下面程序的输出结果：求下面程序的输出结果。structksinta;int*b;s4,*p;main()intn=1,i;printf(n);for(i=0;ia,(p+)-a);s0.a=1s1.a=3s2.a=5s3.a=77,3右结合右结合先观察链表示意图，后理解链表概念。先观察链表示意图，后理解链表概念。某某3 3位同学的物理成绩分别为位同学的物理成绩分别为9696，8989，9393。分别用数。分别用数组和链表存储这些数据的示意图如下：组和链表存储这些数据的示意图如下：613609605601938996p指针指针89空空93指针指针963 3个节点的链表：个节点的链表：3 3个元素的数组：个元素的数组：float a3;float a3;a a11.9简单链表11.9.1 链表的概念v 链表是一种动态数据结构，可以用来表示顺序访问的线性群体。v 链表是由系列结点组成的，结点可以在运行时动态生成。v 每一个结点包括数据域和指向链表中下一个结点的指针（即下一个结点的地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称为单链表。v 链表不要求逻辑上相邻的元素在物理位置上也相邻，在内存允许的范围内，占用空间大小不受限制，摒弃了数组的弱点。11.9.2 数组与链表的比较数组：仅能实现静态存储。数组：仅能实现静态存储。链表：可以实现动态存储。链表：可以实现动态存储。链表的使用步骤：链表的使用步骤：建立链表建立链表(使用使用malloc函数函数)访问链表访问链表(使用使用*p表达式表达式)释放链表释放链表(使用使用free函数函数)p指针指针89空空93指针指针961链表结构（1）头指针变量）头指针变量head指向链表的首结点。指向链表的首结点。（2）每个结点由）每个结点由2个域组成：个域组成：1）数据域）数据域存储结点本身的信息。存储结点本身的信息。2）指针域）指针域指向后继结点的指针。指向后继结点的指针。（3）尾尾结结点点的的指指针针域域置置为为“NULL（空空）”，作作为链表结束的标志为链表结束的标志QianSunLiZhouWuWangHead链表结构的定义struct studentchar name10;struct student*next;next为为struct student类型指针变量，指类型指针变量，指向下一个结点。向下一个结点。结点的变量或指针变量的定义：结点的变量或指针变量的定义：struct student node,*head;node可以存放一个学生结点可以存放一个学生结点指针指针head可以存放学生结点的地址。可以存放学生结点的地址。相关库函数1.void*malloc(unsignedintsize);用途：在内存的动态存储区中分配一个用途：在内存的动态存储区中分配一个size长度长度的连续存储空间。的连续存储空间。返回值：返回一个指向分配域地址的指针（类返回值：返回一个指向分配域地址的指针（类型为型为void）;若未成功，则返回空指针（若未成功，则返回空指针（NULL）例如：例如：int*p;p=(int*)malloc(8);p指示系统分配的指示系统分配的4个整型存储单元的起始地址个整型存储单元的起始地址也可看成包含也可看成包含4个数组元素的个数组元素的p数组：数组：p0,p1,p2,p32.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），继续建立新结点。），继续建立新结点。#includestdio.hstructsinta;structs*q;#defineLENsizeof(structs)main()structs*head,*p1,*p2;intm,i,n;for(i=1;ia=m;if(i=1)head=p1=p2;elsep1-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()inta3,i;for(i=0;i3;i+)scanf(%d,&ai);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个结点之后个结点之后Headp101Zhang90103Wang80NULL105Li70(a)head指示已有链表，指示已有链表，q指示待插入结点指示待插入结点q104Zhao70Headr101Zhang90q104Zhao60103Wang80pNULL105Li7011.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。p经常不断地学习,你就什么都知道。你知道得越多,你就越有力量pStudyConstantly,AndYouWillKnowEverything.TheMoreYouKnow,TheMorePowerfulYouWillBe写在最后谢谢你的到来学习并没有结束，希望大家继续努力Learning Is Not Over.I Hope You Will Continue To Work Hard演讲人：XXXXXX 时 间：XX年XX月XX日