C__课件第六章.ppt

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

2、； ；,注：struct是关键字 ；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; 定义了两个

3、day 类型的变量d1、d2。,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；

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

5、 则变量sd2的各个成员变量与 sd1的成员变量具有相同的值。sd2.num的值也为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.CPPscore+; 注意：结构体成员可以是另一个结构体类型的变量（见下例）。,struct date int month; int d

6、ay; int year; struct student int num; char name20; 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是

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

9、node的指针变量 node m; /错误 ;,运行结果： NO:40301name: YangKesex:M CPPscore:89.5 NO:40301name: YangKesex:M CPPscore:89.5 NO:40301name: YangKesex:M CPPscore:89.5,6.1.5 结构体数组,结构体数组的定义方法和结构体变量相似，只需说明它为数组类型即可。 structstu int num; char *name; char sex; float score;boy5; 以上示例定义了一个结构体数组boy，共有5个数组元素，boy0boy4。每个数组元素都具有s

10、tu的结构形式，都是一个结构体类型的变量。,对结构体数组可以作初始化赋值，例如： struct stu int num; char *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.不能把结构体数组元素作为一个整

11、体直接进行输入输出，只能对单个成员进行输入输出。 例如：cin boy2;/wrong cinboy0.sex;/right,6.1.6用结构体变量作函数参数,结构体类型变量可作为函数的参数，函数返回值的类型也可为结构体类型。 当函数的形参与实参为结构体类型的变量时，这种结合方式属于值调用方式，即属于值传递。要求实参与相应的形参必须是同一类型的结构体变量。,例6-2 结构体类型变量作为函数的参数 #include struct sint m; float x; void swap(s s1,s s2) s t; t=s1,s1=s2, s2=t; /变量值的交换 s fun(s s1,s s2

12、) s t; t.m=s1.m+s2.m; t.x=s1.x+s2.x; return t; ,void main() s r1=100,200,r2=300,400; 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依然等于10

13、0。 （3）fun函数的返回值类型为结构体类型，即s类型。函数的功能是分别求出两个结构体类型变量中对应的成员变量的和，即s1.m+s2.m;和s1.x+s2.x;求出的和存放在局部结构体变量t中。函数返回t的值。,例6-3 建立一个学生档案的结构体数组，描述一个学生的信息：姓名，年龄，C+成绩，并输出已建的学生档案。 算法： （1）定义一个描述学生信息的结构体类型。 （2）通过输入语句cin输入某个学生的信息。 （3）处理多个学生信息时，因为已经限定学生信息都一致，所以定义一个结构体类型的数组，对每个数组元素进行输入、输出的处理。,#include struct stu char name8;

14、 int age; float cscore; ; stu input(stu x) x.agex.cscore ; return x; void output(stu x) cout tx.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语言分数 李易 1

15、8 89 王华 19 78 苏三 20 67 李朋 17 90 张辉 18 88 姓名 年龄C语言分数 李易 18 89 王华 19 78 苏三 20 67 李朋 17 90 张辉 18 88,程序解读： （1）该程序中学生信息的输入、输出是用函数完成的。input函数对形参x的成员变量赋值。通过函数返回x的值。在主函数中，用赋值语句接收返回值。即sI=input(sI);完成对结构体数组元素的赋初值。 （2）程序中要处理多个学生的信息，注意输入、输出格式。,6.2 链表概念,6.2.1 遍历结构体变量 定义一个结构体类型，该结构体的成员中包含一个指向自身的结构体类型的指针变量。这样就可以实现

16、随机分布的结构体变量的遍历。 定义一个简单的结构体，如下： struct node long int num; float CPPscore; node *next; ;,node1,node2,node3,node4,num,score,next,如图6.2所示num成员含有结构体中的实际数据信息，next成员是指向另一个node的指针变量。这种结构体变量，我们称为结点。通过每个结点的next成员把不断加入的结点链接起来。可解决很多情况下开始不知道有多少个结点的问题。这样一个结点链接一个结点就构成了一个结构体链，我们称之为链表。,图 6.2遍历结构体变量,6.2.2 链表 所谓链表是指若干个

17、数据组（每一个数据组称为一个结点），按一定的原则连接起来。这个原则是：前一个结点“指向”下一个结点，只有通过前一个结点才能找到下一个结点。组成链表的一个个结点是同类型的结构体变量。链表根据需要开辟内存单元。,链表结点间的链接是通过前一个结点中存放了下一个结点的指针的方法来实现的。要存取学生的信息，必须通过链表的首地址逐个结点往后找。所以，对于一个链表来说，首地址是一个链表操作的关键。链表的第一个结点的地址，即首地址一般存放在一个指针变量中，我们称之为“头指针”变量。显然该指针变量不是结构体成员，而是指向结构体类型的指针变量。 链表分为单向链表、双向链表和循环链表。这里只介绍单向链表。如图6.3

18、就是一个有4个结点的表示学生信息的单向链表。每个结点用一个矩形框表示。矩形框的三部分分别表示node类型的三个成员： num、CPPscore、next。,node1,node2,node3,node4,head, cinn; float an; 这时我们可以用C+的new运算符来动态地分配一个有n个元素的数组。,new运算符运算的结果是动态申请内存空间的起始地址。例如： char *p1 , *p2 , (*p3)10 , *p4 ; p1=new char ; p2=new char 10 ; p3=new char 510 ; / 或p3=( char (*)10) new char 5

19、 ; p4=new char 5*10 ; / 或p4=( char *) new char 510 ; 其中，p3指向一个一维字符数组，该数组由十个元素组成。系统为p1开辟一个元素的动态字符型内存空间，为p2 开辟10个元素的字符型动态连续内存空间，为p3开辟了一个5行10列的字符型二维数组动态内存空间，为p4开辟一个50个元素的字符型一维数组动态内存空间。,可以在分配单个的动态内存的同时给该内存赋一个初始值，如对上面p1，可以这样赋初值： p1=new char(A) ; 但在给数组或结构体数据分配动态内存的同时不可以对其赋初值，如： int *s1; s1=new int 10(1,2,

20、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 ;/错误,系统不会自动释放动态分配的内存空间，因此动态分配的内存在使用完后应释放掉。如对上面分配的动态内存，可以作如下释放： delete p1 ; delete p2 ; delete 5p3 ; delete5*10p4 ; delete s2;,6.3 链表的基本操作,6.3.1 链表结点的创建 struct node long int num; float

21、CPPscore; node *next; ; 链表都有一个“头指针”，该指针变量定义如下： node *head; head=NULL; /头指针没有指向任一个结点，链表为空,链表结点所占内存单元是动态分配的，创建一个结点需要用到new运算符。语句如下： new node; new运算的结果是个地址值，因此要定义一个指针变量来保存该运算结果，以便给申请的内存单元存储对应的数据。 node *p; p=new node; 第一个结点的内存单元有了，下面把实际数据存储进去。 p-num=40301; p-CPPscore=85.5;,6.3.2 链表的建立 例6-4 写一个函数建立一条有4名学生

22、数据的单向链表 算法： （1）目前在内存中没有任何的学生数据。因此要用new运算符动态申请内存空间。 让p指针指向该空间。 （2）把学生学号、C+分数这些实际数据赋值给第一个结点的成员项。这时用头指针指向刚建好的第一个结点即head=p ;p指针值可以更新，保存动态申请的第二个内存空间的地址。即p=new node ; （3）依次类推，当建立到第4个学生数据时，第4个结点就是尾结点，它的next成员项赋值为空，即pend-next=0 ;,编程实现： node *create( ) node *head ; /头指针 node *p , *pend ; long int a; float sc

23、ore ; 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=p ; /pend指向链尾，用于在其后插入新创建的结点 couta; coutscore ; If(head) pend-next=0 ; / 置链尾标志 return head ; ,6.3.3 链表的输出 链表

24、的输出是从链表头指针开始，逐个结点输出。每输出一个结点，则由该结点的next指针取得下一个结点，直到链表的尾结点。输出链表的print( )函数的形参不能是引用类型的变量，因为要保持“头指针”head的值不变。即不能定义为void print(node 例6-5 写一个函数输出链表上各个结点的值。,编程实现： void print(node *head ) if(head=0) coutnumCPPscorenext ; /p指向下一个结点 ,6.3.4释放链表的结点空间 我们建立的链表是动态链表，组成链表的每个结点的内存单元都是通过new运算符动态申请空间的。因此在对链表操作完毕后，动态申请

25、的空间要释放掉，以便于对内存进行有效的管理。定义一个函数release来完成此操作。该函数的形参是指向结构体类型的指针变量。,例6-6 释放链表的结点空间 编程实现： void release(node *head ) if(head=0) coutnext ; /头指针不断后移，指向链表的各个结点 delete p; /释放p指针指向的结点的内存单元 cout结点空间释放完毕!; ,6.3.5 主函数的编写 例6-7链表主函数的编写 #include struct node long int num; float CPPscore; node *next; ; void main( ) no

26、de *create( ); /该函数建立一条有4名学生数据的单向链表 void print(node *head ); /该函数输出链表上各个结点的值 void release(node *head ); /该函数释放链表的结点空间 node *head; head=create( ); print(head); release(head); ,调试与运行结果： 请输入学号:40301 请输入分数(分数为负表示结束输入)：85.5 请输入学号:40302 请输入分数(分数为负表示结束输入)：78.5 请输入学号:40303 请输入分数(分数为负表示结束输入)：80.5 请输入学号:40304

27、 请输入分数(分数为负表示结束输入)：83 请输入学号:40305 请输入分数(分数为负表示结束输入)：-7 链表上各个结点的值为： 学号 C+成绩 4030185.5 4030278.5 4030380.5 4030483 结点空间释放完毕!,6.4 链表的复杂操作,链表的复杂操作有三种： 删除链表中具有指定值的一个结点； 把创建好的一个结点插入链表； 建立一条有序链表。这三种操作都要基于查找第n个结点的操作。,node1,node2,node3,node4,head, p1=p1-next;注意这两条语句的顺序不能颠倒，否则p2也指向node2。,图 6.4学生信息链表示意图,2.设p1指

28、向node1，p2指向node2，指针变量p3指向node3，若让node1与node3链接起来，即node2不在链表中，可使用语句: p1-next=p3;或p1-next=p2-next; 3.设p1指向尾结点node4，p2指向一个新结点node5，若让node5作为链表的尾结点，可使用语句: p1-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

29、指向node1，p2指向新结点node5，若让node5做链表的首结点，可使用语句： p2-next=p1；head=p2;或p2-next=head；head=p2;,node1,node2,node3,node4,head, p2=head; for(int i=1;inext; /查找第n 个结点 if(n=1) head=head-next; /头指针指向第2个结点 else p1-next=p2-next; /建立如图6.5中标号所示箭头的链接 delete p2;,删除链表中具有指定值的一个结点时有以下几种情况： 链表是空表（无结点）； 要删的是第一个结点； 要删的是中间的一个结点

30、； 要删的是最后一个结点 链表中找不到要删除的结点。,例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; ,else p2=p1=head; while(p2-data!=num ,node1,node2,node3,node4,head, p1=head; for(int i=1;inext; node *p=new node; p-num=4

31、0303; p-CPPscore=80.5; if(n) p-next=p1-next; p1-next=p; else p-next=head; head=p; /插入的结点做第一个结点,将一个具有值的结点插入到一个有序链表中可遇到以下几种情况： 该链表是空表，则插入的结点做为第一个结点； 要插入的结点做链表的第一个结点； 在两结点之间，正常插入结点； 要插入的结点是尾结点。,例6-9将一个结点插入有序链表，插入后链表仍保持有序 编程实现： node *Insert(node *head,node *p) node *p1,*p2; if(head=0) /第种情况 head=p; p-ne

32、xt=0; return head; if(head-data=p-data) /第种情况 p-next=head; head=p; return head; ,p2=p1=head; /也可使用两个指针，编写结点插入语句 while(p2-next ,例6-10建立一条有序链表。链表的每一个结点包括：学号、姓名、年龄和C+成绩。定义一个函数完成建立链表的工作，一个函数完成输出链表的各结点的值，一个函数完成释放链表的结点占用的动态存储空间。按C+成绩升序排序。 算法： 建立一条有序链表可以在建立链表的过程中完成。当建立第一个结点后，头指针h指向它，第二个结点建立好后，把第二个结点的C+成绩与第

33、一个结点的相比较，如果第二个结点的C+成绩比第一个结点的小，则使第二个结点的指针项next保存第一个结点的地址，头指针h移动指向第二个结点；反之使第一个结点的指针项next保存第二个结点的地址，头指针h依然指向第一个结点。以此类推，若第三个结点的C+成绩在另两个结点之间，则把第三个结点插入到链表中。总之，h始终指向C+成绩最小的结点。,编程实现： #include #define NULL 0 struct NODE int id,age; char name10; float c; NODE *next; ; NODE *Create(int n) NODE *p,*p1,*p2,*h=NU

34、LL; int i=0; if(n1)return NULL;,while(ip-idp-namep-agep-c; p-next=NULL; if(h=NULL)h=p; else p1=p2=h; while(p2 ,void print(NODE *h) NODE *p; p=h; while(p!=0) coutidnameagecnext; coutnext;delete p; ,void main() int n; coutn; coutendl; cout请输入班级学生信息！endl; cout学号 姓名 年龄 C+成绩endl; NODE *h;h=Create(n); coutendl学号 姓名 年龄 C+成绩endl; print(h); deletechain(h); ,调试与运行结果： 请输入班级人数！ 班级人数为：4 请输入班级学生信息！ 学号 姓名 年龄 C+成绩 40301 liming 18 90 40