C++-ppt课件第六章.ppt

《C++-ppt课件第六章.ppt》由会员分享，可在线阅读，更多相关《C++-ppt课件第六章.ppt（77页珍藏版）》请在三一办公上搜索。

1、第六章,结构体与简单链表,6.1 结构体6.2 链表概念 6.3 链表的基本操作6.4 链表的复杂操作,6.1 结构体,结构体是一种导出数据类型，它由若干个数据项组成，每个数据项可以是基本数据类型，也可以是导出数据类型。在现实生活中，有时需解决某种问题：如对学生的基本信息进行处理（查找、排序等）。,学号 姓名 C+成绩,图6-1学生基本信息,6.1.1 结构体类型的定义定义一个结构体类型的一般形式为：struct 结构体名 成员表列 ；图6-1学生基本信息可以定义成如下结构体类型。struct student int num；char name20；float CPPscore；,注：stru

2、ct是关键字 ；num、name、CPPscore等不同类型的数据项；student 是一个类型名；最后的分号不能省略。,6.1.2结构体类型变量的定义 定义结构体类型的变量，有以下三种方法：1.先声明结构体类型再定义变量名例如： student student1,student2;student是在6.1.1中定义好的结构体类型，student1和student2就是两个用户自己定义的student结构体类型的变量。,2.在声明类型的同时定义变量例如：struct day int hour;int minute;int second;d1,d2;定义了两个day 类型的变量d1、d2。,3.

3、直接定义结构体类型变量例如：struct int num;char sex;s1,s2;在定义了结构体类型的变量后，系统会为它分配内存单元。其所占存储空间的大小为各个成员所占内存单元之和。例如student1和student2在内存中各占28byte（4+20+4=28）,结构体变量是一个整体，要访问其数据成员，要用成员运算符“”指定该成员属于哪个变量。 对结构体变量进行初始化有以下几种常用的方法： 1. 在定义时进行初始化struct student int num；char name20；char sex；float CPPscore；sd1=40301,”YangKe”,M,89.5；,

4、6.1.3结构体类型变量的初始化与引用,2.用对象流cin进行初始化cinsd1.numsd1.namesd1.sexsd1.CPPscore;3.使用赋值语句进行初始化sd1.num=40301;sd1.name=” YangKe”; /错误 sd1.sex=M；sd1.CPPscore=89.5;,结构体变量的引用应遵循以下规则：1.不能将一个结构体变量作为一个整体进行输入输出。例如：cinsd1; /错误2.允许将一个结构体变量直接赋值给另一个具有相同类型的结构体变量。例如：student sd2; sd2=sd1; 则变量sd2的各个成员变量与 sd1的成员变量具有相同的值。sd2.n

5、um的值也为40301。,若有定义：struct int num;char sex;s1=40301,M;struct int num;char sex;s2；此时s2=s1;是错误的。s1,s2属于两个不同的结构体类型的变量。,3.对成员变量可以像普通变量一样进行各种运算（依成员变量的类型而定）。例如：char a20; strcpy(a, sd1.name); sd1.CPPscore+;注意：结构体成员可以是另一个结构体类型的变量（见下例）。,struct date int month; int day; int year;struct student int num; char nam

6、e20; date birthday; student1；student类型中的birthday成员就是一个date结构体类型的变量。如果某成员本身又是一个结构体类型，则只能通过多级的分量运算，对最低一级的成员进行引用。格式为：结构体变量.成员.子成员. .最低级子成员如：引用结构体变量student1中的birthday成员：student1.birthday.year，student1.birthday.month,6.1.4指向结构体变量的指针,一个结构体变量的指针就是给该变量所分配内存段的起始地址。可以定义一个指针变量，用来指向一个结构体变量。此时该指针变量的值就是结构体变量的起始地址

7、。 下面通过一个例子来说明指向结构体变量的指针变量的使用。,例6-1 指向结构体变量的指针变量的使用 # include “iostream.h”# include “string.h”void main( ) struct student /声明了 student结构体类型 long int num; char name20; char sex; float CPPscore; ;,student stu_1; /定义了student类型的变量 stu_1 student *p; /p是指向结构体student类型的指针变量p=,coutnumnamesexCPPscoreendl ; ,程

8、序解读：（1）成员变量name是个字符数组，给它赋值时要用字符串拷贝函数。strcpy(stu_1.name,” YangKe”);而不能用赋值运算符。stu_1.name=” YangKe”;（2）以下三种形式等价: 结构体变量.成员名 (*p).成员名 p-成员名,注意：结构体的成员不能是自身的结构体变量，但可以是指向自身的结构体类型的指针变量。例如：struct node long int num;float CPPscore;node *next; / next是指向node的指针变量node m; /错误;,运行结果：NO:40301name: YangKesex:M CPPscor

9、e:89.5NO:40301name: YangKesex:M CPPscore:89.5NO:40301name: YangKesex:M CPPscore:89.5,6.1.5 结构体数组,结构体数组的定义方法和结构体变量相似，只需说明它为数组类型即可。 structstu int num; char *name; char sex; float score;boy5; 以上示例定义了一个结构体数组boy，共有5个数组元素，boy0boy4。每个数组元素都具有stu的结构形式，都是一个结构体类型的变量。,对结构体数组可以作初始化赋值，例如：struct stu int num; char

10、*name; char sex; float score;boy5=101,Li ping,M,45, 102,Zhang ping,M,62.5, 103,He fang,F,92.5, 104,Cheng ling,F,87, 105,Wang ming,M,58；,注意：1.可将一个结构体数组元素赋值给同一个结构体类型数组中的另一个元素或赋给同一类型的变量。例如：boy2=boy0;stu aa; aa=stu0;2.不能把结构体数组元素作为一个整体直接进行输入输出，只能对单个成员进行输入输出。 例如：cin boy2;/wrong cinboy0.sex;/right,6.1.6用结构

11、体变量作函数参数,结构体类型变量可作为函数的参数，函数返回值的类型也可为结构体类型。 当函数的形参与实参为结构体类型的变量时，这种结合方式属于值调用方式，即属于值传递。要求实参与相应的形参必须是同一类型的结构体变量。,例6-2 结构体类型变量作为函数的参数#includestruct sint m; float x;void swap(s s1,s s2)s t;t=s1,s1=s2, s2=t; /变量值的交换s fun(s s1,s s2)s t;t.m=s1.m+s2.m; t.x=s1.x+s2.x;return t;,void main()s r1=100,200,r2=300,40

12、0;swap(r1,r2);coutr1.mtr2.mendl;s y;y=fun(r1,r2);cout“y.m=”y.mt”y.x=”y.x;,运行结果：300 y.m=400 y.x=600,程序解读：（1）swap函数中形参s1和s2是结构体s类型的变量。（2）因为形参与实参之间参数的传递方式属于值传递，因此swap函数中形参s1和s2的值进行了交换，但并没有影响到实参r1和r2的值。所以r1.m依然等于100。（3）fun函数的返回值类型为结构体类型，即s类型。函数的功能是分别求出两个结构体类型变量中对应的成员变量的和，即s1.m+s2.m;和s1.x+s2.x;求出的和存放在局部结

13、构体变量t中。函数返回t的值。,例6-3 建立一个学生档案的结构体数组，描述一个学生的信息：姓名，年龄，C+成绩，并输出已建的学生档案。算法：（1）定义一个描述学生信息的结构体类型。（2）通过输入语句cin输入某个学生的信息。（3）处理多个学生信息时，因为已经限定学生信息都一致，所以定义一个结构体类型的数组，对每个数组元素进行输入、输出的处理。,#includestruct stuchar name8;int age; float cscore;stu input(stu x)cinx.namex.agex.cscore ;return x;void output(stu x) cout x.

14、nametx.agetx.cscoreendl ;,void main()stu s5;cout请输入5个学生的信息:n;cout姓名 年龄C语言分数n;for(int I=0;I5;I+)sI=input(sI);cout姓名 年龄C语言分数n;for( I=0;I5;I+)output(sI);,调试与运行：请输入5个学生的信息:“姓名 年龄 C语言分数李易 18 89王华 19 78苏三 20 67李朋 17 90张辉 18 88 姓名 年龄C语言分数李易 18 89王华 19 78苏三 20 67李朋 17 90张辉 18 88,程序解读： （1）该程序中学生信息的输入、输出是用函数完

15、成的。input函数对形参x的成员变量赋值。通过函数返回x的值。在主函数中，用赋值语句接收返回值。即sI=input(sI);完成对结构体数组元素的赋初值。 （2）程序中要处理多个学生的信息，注意输入、输出格式。,6.2 链表概念,6.2.1 遍历结构体变量 定义一个结构体类型，该结构体的成员中包含一个指向自身的结构体类型的指针变量。这样就可以实现随机分布的结构体变量的遍历。定义一个简单的结构体，如下：struct node long int num; float CPPscore; node *next; ;,node1,node2,node3,node4,num,score,next,如图

16、6.2所示num成员含有结构体中的实际数据信息，next成员是指向另一个node的指针变量。这种结构体变量，我们称为结点。通过每个结点的next成员把不断加入的结点链接起来。可解决很多情况下开始不知道有多少个结点的问题。这样一个结点链接一个结点就构成了一个结构体链，我们称之为链表。,图 6.2遍历结构体变量,6.2.2 链表 所谓链表是指若干个数据组（每一个数据组称为一个结点），按一定的原则连接起来。这个原则是：前一个结点“指向”下一个结点，只有通过前一个结点才能找到下一个结点。组成链表的一个个结点是同类型的结构体变量。链表根据需要开辟内存单元。,链表结点间的链接是通过前一个结点中存放了下一个

17、结点的指针的方法来实现的。要存取学生的信息，必须通过链表的首地址逐个结点往后找。所以，对于一个链表来说，首地址是一个链表操作的关键。链表的第一个结点的地址，即首地址一般存放在一个指针变量中，我们称之为“头指针”变量。显然该指针变量不是结构体成员，而是指向结构体类型的指针变量。链表分为单向链表、双向链表和循环链表。这里只介绍单向链表。如图6.3就是一个有4个结点的表示学生信息的单向链表。每个结点用一个矩形框表示。矩形框的三部分分别表示node类型的三个成员： num、CPPscore、next。,node1,node2,node3,node4,head,&node1,现在的问题是链表的第一个结点

18、怎样找，怎样表示链表的最后一个结点。即最后一个结点的指针成员应放怎样的地址？,图 6.3学生信息链表示意图,用head头指针指向链表的第一个结点node1。node1的next成员又指向结点node2，这样一直指下去，直到最后一个结点。最后一个结点的next成员值为空（NULL），表示链表的尾结点，链表到此结束。,6.2.3 new和delete 我们知道，定义一个数组时，数组的大小必须是一个确定的值，即在程序运行之前必须将数组的大小确定下来。而如下数组的定义就是错误的。int n; cinn; float an; 这时我们可以用C+的new运算符来动态地分配一个有n个元素的数组。,new运算

19、符运算的结果是动态申请内存空间的起始地址。例如：char *p1 , *p2 , (*p3)10 , *p4 ; p1=new char ; p2=new char 10 ; p3=new char 510 ; / 或p3=( char (*)10) new char 5 ; p4=new char 5*10 ; / 或p4=( char *) new char 510 ; 其中，p3指向一个一维字符数组，该数组由十个元素组成。系统为p1开辟一个元素的动态字符型内存空间，为p2 开辟10个元素的字符型动态连续内存空间，为p3开辟了一个5行10列的字符型二维数组动态内存空间，为p4开辟一个50个

20、元素的字符型一维数组动态内存空间。,可以在分配单个的动态内存的同时给该内存赋一个初始值，如对上面p1，可以这样赋初值：p1=new char(A) ; 但在给数组或结构体数据分配动态内存的同时不可以对其赋初值，如：int *s1; s1=new int 10(1,2,3,4,5,6,7,8);/错误struct node1 long int num; float CPPscore; ;node1 *s2,*s3;s2=new node1;s3=new node1 =40301,95.5 ;/错误,系统不会自动释放动态分配的内存空间，因此动态分配的内存在使用完后应释放掉。如对上面分配的动态内存，

21、可以作如下释放：delete p1 ; delete p2 ; delete 5p3 ; delete5*10p4 ; delete s2;,6.3 链表的基本操作,6.3.1 链表结点的创建 struct node long int num; float CPPscore; node *next; ;链表都有一个“头指针”，该指针变量定义如下：node *head;head=NULL; /头指针没有指向任一个结点，链表为空,链表结点所占内存单元是动态分配的，创建一个结点需要用到new运算符。语句如下：new node;new运算的结果是个地址值，因此要定义一个指针变量来保存该运算结果，以便给

22、申请的内存单元存储对应的数据。node *p;p=new node;第一个结点的内存单元有了，下面把实际数据存储进去。p-num=40301;p-CPPscore=85.5;,6.3.2 链表的建立例6-4 写一个函数建立一条有4名学生数据的单向链表 算法：（1）目前在内存中没有任何的学生数据。因此要用new运算符动态申请内存空间。让p指针指向该空间。（2）把学生学号、C+分数这些实际数据赋值给第一个结点的成员项。这时用头指针指向刚建好的第一个结点即head=p ;p指针值可以更新，保存动态申请的第二个内存空间的地址。即p=new node ;（3）依次类推，当建立到第4个学生数据时，第4个结

23、点就是尾结点，它的next成员项赋值为空，即pend-next=0 ;,编程实现：node *create( ) node *head ; /头指针node *p , *pend ; long int a;float score ; couta;coutscore ; /给结点赋值 head=0 ;,while(score=0) p=new node ; / p指向新创建的结点p-num=a ; p-CPPscore=score ; if(head=0) / 空链表head=p ; pend=p ; else /A点 pend-next=p ; / pend指向p所指向结点的前驱结点 pend

24、=p ; /pend指向链尾，用于在其后插入新创建的结点 couta; coutscore ; If(head) pend-next=0 ; / 置链尾标志 return head ; ,6.3.3 链表的输出链表的输出是从链表头指针开始，逐个结点输出。每输出一个结点，则由该结点的next指针取得下一个结点，直到链表的尾结点。输出链表的print( )函数的形参不能是引用类型的变量，因为要保持“头指针”head的值不变。即不能定义为void print(node 例6-5 写一个函数输出链表上各个结点的值。,编程实现：void print(node *head ) if(head=0) cou

25、tnumCPPscorenext ; /p指向下一个结点 ,6.3.4释放链表的结点空间 我们建立的链表是动态链表，组成链表的每个结点的内存单元都是通过new运算符动态申请空间的。因此在对链表操作完毕后，动态申请的空间要释放掉，以便于对内存进行有效的管理。定义一个函数release来完成此操作。该函数的形参是指向结构体类型的指针变量。,例6-6 释放链表的结点空间编程实现：void release(node *head ) if(head=0) coutnext ; /头指针不断后移，指向链表的各个结点delete p; /释放p指针指向的结点的内存单元 cout结点空间释放完毕!;,6.3.

26、5 主函数的编写例6-7链表主函数的编写#includestruct node long int num;float CPPscore; node *next; ;void main( ) node *create( ); /该函数建立一条有4名学生数据的单向链表void print(node *head ); /该函数输出链表上各个结点的值void release(node *head ); /该函数释放链表的结点空间node *head;head=create( );print(head);release(head);,调试与运行结果：请输入学号:40301请输入分数(分数为负表示结束输入

27、)：85.5请输入学号:40302请输入分数(分数为负表示结束输入)：78.5请输入学号:40303请输入分数(分数为负表示结束输入)：80.5请输入学号:40304请输入分数(分数为负表示结束输入)：83请输入学号:40305请输入分数(分数为负表示结束输入)：-7链表上各个结点的值为：学号 C+成绩4030185.54030278.54030380.54030483结点空间释放完毕!,6.4 链表的复杂操作,链表的复杂操作有三种：删除链表中具有指定值的一个结点；把创建好的一个结点插入链表；建立一条有序链表。这三种操作都要基于查找第n个结点的操作。,node1,node2,node3,nod

28、e4,head,&node1,对链表进行操作时，注意的语句 1.设指针变量p1指向node1，若让p1指向node2，指针变量p2指向node1，可使用语句: p2=p1; p1=p1-next;注意这两条语句的顺序不能颠倒，否则p2也指向node2。,图 6.4学生信息链表示意图,2.设p1指向node1，p2指向node2，指针变量p3指向node3，若让node1与node3链接起来，即node2不在链表中，可使用语句: p1-next=p3;或p1-next=p2-next;3.设p1指向尾结点node4，p2指向一个新结点node5，若让node5作为链表的尾结点，可使用语句: p1

29、-next=p2; p2-next=NULL;,4.设p1指向node1，p2指向node2，p3指向新结点node5，若让node5插入到node1和node2之间，可使用语句: p1-next=p3；p3-next=p2；或p3-next=p1-next；p1-next=p3;5.设p1指向node1，p2指向新结点node5，若让node5做链表的首结点，可使用语句：p2-next=p1；head=p2;或p2-next=head；head=p2;,node1,node2,node3,node4,head,&node1,6.4.1结点的删除,&node1,node1,node2,node

30、3,node4,p1,p2,p1,p2,删除第n个结点的关键步骤为： 查找第n个结点，让p2指针指向它，让p1指针指向第n个结点的前驱结点； 删除第n个结点； 释放第n个结点的空间。关键语句如下：node *p2,*p1;p2=head;for(int i=1;inext; /查找第n 个结点if(n=1) head=head-next; /头指针指向第2个结点else p1-next=p2-next; /建立如图6.5中标号所示箭头的链接delete p2;,删除链表中具有指定值的一个结点时有以下几种情况：链表是空表（无结点）； 要删的是第一个结点； 要删的是中间的一个结点； 要删的是最后一

31、个结点 链表中找不到要删除的结点。,例6-8 删除链表上一个结点编程实现：node *Delete_one_node(node *head,int num) node *p1,*p2;if(head=NULL)/第种情况coutdata=num)/ 第种情况p2=head;head=head-next;delete p2;,elsep2=p1=head; while(p2-data!=num,node1,node2,node3,node4,head,&node1,6.4.1结点的插入,&node1,node1,node2,node4,p1,p,p2,在第n个结点之后插入一个新结点的关键步骤为：

32、 查找第n个结点，让p1指针指向它； 生成新结点，让p指针指向它； p指针指向的结点插到p1指针指向的结点之后。关键语句如下：node *p1;p1=head;for(int i=1;inext;node *p=new node;p-num=40303; p-CPPscore=80.5;if(n) p-next=p1-next; p1-next=p;else p-next=head; head=p; /插入的结点做第一个结点,将一个具有值的结点插入到一个有序链表中可遇到以下几种情况： 该链表是空表，则插入的结点做为第一个结点； 要插入的结点做链表的第一个结点； 在两结点之间，正常插入结点； 要

33、插入的结点是尾结点。,例6-9将一个结点插入有序链表，插入后链表仍保持有序编程实现：node *Insert(node *head,node *p)node *p1,*p2;if(head=0) /第种情况head=p; p-next=0; return head;if(head-data=p-data) /第种情况p-next=head;head=p;return head;,2=p1=head; /也可使用两个指针，编写结点插入语句while(p2-next,例6-10建立一条有序链表。链表的每一个结点包括：学号、姓名、年龄和C+成绩。定义一个函数完成建立链表的工作，一个函数完成输出链表的

34、各结点的值，一个函数完成释放链表的结点占用的动态存储空间。按C+成绩升序排序。算法：建立一条有序链表可以在建立链表的过程中完成。当建立第一个结点后，头指针h指向它，第二个结点建立好后，把第二个结点的C+成绩与第一个结点的相比较，如果第二个结点的C+成绩比第一个结点的小，则使第二个结点的指针项next保存第一个结点的地址，头指针h移动指向第二个结点；反之使第一个结点的指针项next保存第二个结点的地址，头指针h依然指向第一个结点。以此类推，若第三个结点的C+成绩在另两个结点之间，则把第三个结点插入到链表中。总之，h始终指向C+成绩最小的结点。,编程实现：#include#define NULL

35、0struct NODEint id,age;char name10;float c;NODE *next;NODE *Create(int n)NODE *p,*p1,*p2,*h=NULL;int i=0;if(n1)return NULL;,while(ip-idp-namep-agep-c;p-next=NULL;if(h=NULL)h=p;elsep1=p2=h;while(p2,void print(NODE *h)NODE *p;p=h;while(p!=0)coutidnameagecnext;coutnext;delete p;,void main()int n;coutn;

36、coutendl;cout请输入班级学生信息！endl;cout学号 姓名 年龄 C+成绩endl;NODE *h;h=Create(n);coutendl学号 姓名 年龄 C+成绩endl;print(h);deletechain(h);,调试与运行结果：请输入班级人数！班级人数为：4请输入班级学生信息！学号 姓名 年龄 C+成绩40301 liming 18 9040302 lifeng 19 6740303 wanghua 18 7740304 keyang 19 80学号 姓名 年龄 C+成绩40302 lifeng 19 6740303 wanghua 18 7740304 keya

37、ng 19 8040301 liming 18 90,例6-11设已建立一个单向链表，定义一个函数将该链表中相邻的两个结点合并成一个结点。即将第一个结点的数据项与第二个结点的合并，第三个结点的与第四个结点的合并，依此类推。若链表上结点个数为奇数，则尾结点不合并，直接作为合并后新链表上的最后一个结点。结点的数据结构如下：struct node int data;node *next; ;,算法：初始时，使指针变量p1指向链表的首结点，p2指向它的后继结点。将p1所指向结点的data值与p2所指向结点的data值相加。保存在p1所指向结点的data成员项中。p1指向第三个结点，p2指向它的后继结点

38、，即第四个结点。两结点的data值相加。依此类推，直至p2为空。,编程实现：void merge(node *h)node *p1,*p2;if(h-next=NULL|h=NULL)return ;p1=h;p2=h-next;while(p2)p1-data+=p2-data;p1-next=p2-next;delete p2;p1=p1-next;if(p1!=NULL)p2=p1-next;else p2=NULL;,例6-12设已建立一个单向链表，指针head指向该链表的首结点。定义一个函数将head所指向链表上各结点的数据按data值升序排序。结点的数据结构如下：struct no

39、de int data;node *next; ;,算法：初始时，使指针变量p指向该链表的首结点，从p之后的所有结点中找出data值最小的结点，让p1指向该结点。将p指向结点的data值与p1指向结点的data值进行交换。让p指向下一个结点，依此类推，直至p指向链表的最后一个结点为止。最后，函数返回已排好序的链表的头指针。,编程实现：node *sort(node *h)node *p=h,*p1,*p2;if(p=NULL)return h;while(p-next!=NULL)p1=p;p2=p-next;while(p2!=NULL)if(p2-datadata)p1=p2;p2=p2-next;,if(p!=p1)int t;t=p-data;p-data=p1-data; p1-data=t;p=p-next;return h;,练习题 P144,本章结束！,