1、第六章第六章 结构体与简单链表结构体与简单链表 6.1 6.1 结构体结构体6.2 6.2 链表概念链表概念 6.3 6.3 链表的基本操作链表的基本操作6.4 6.4 链表的复杂操作链表的复杂操作6.1 6.1 结构体结构体 结构体是一种导出数据类型，它由若干个数据结构体是一种导出数据类型，它由若干个数据项组成，每个数据项可以是基本数据类型，也可以项组成，每个数据项可以是基本数据类型，也可以是导出数据类型。在现实生活中，有时需解决某种是导出数据类型。在现实生活中，有时需解决某种问题：如对学生的基本信息进行处理（查找、排序问题：如对学生的基本信息进行处理（查找、排序等）。等）。 40301 Y
2、angKe 85.5 学号 姓名 C+成绩图6-1学生基本信息 6.1.1 结构体类型的定义结构体类型的定义定义一个结构体类型的一般形式为：定义一个结构体类型的一般形式为：struct 结构体名结构体名 成员表列成员表列 ；图图6-1学生基本信息可以定义成如下结构体类型。学生基本信息可以定义成如下结构体类型。struct student int num；char name20；float CPPscore；注注：structstruct是关键字是关键字 ；numnum、namename、CPPscoreCPPscore等不同类型的数据项；等不同类型的数据项；student student 是一
3、个类型名；最后的是一个类型名；最后的分号不能省略。分号不能省略。6.1.26.1.2结构体类型变量的定义结构体类型变量的定义 定义结构体类型的变量，有以下三种方法：定义结构体类型的变量，有以下三种方法：1.先声明结构体类型再定义变量名先声明结构体类型再定义变量名例如：例如： student student1,student2;student是在是在6.1.1中定义好的结构体类型，中定义好的结构体类型，student1和和student2就是两个用户自己定就是两个用户自己定义的义的student结构体类型的变量。结构体类型的变量。 2.在声明类型的同时定义变量在声明类型的同时定义变量例如：例如：
4、struct day int hour;int minute;int second;d1,d2;定义了两个定义了两个day 类型的变量类型的变量d1、d2。3.直接定义结构体类型变量直接定义结构体类型变量例如：例如：struct int num;char sex;s1,s2;在定义了结构体类型的变量后，系统会为它分配在定义了结构体类型的变量后，系统会为它分配内存单元。其所占存储空间的大小为各个成员所内存单元。其所占存储空间的大小为各个成员所占内存单元之和。例如占内存单元之和。例如student1和和student2在内在内存中各占存中各占28byte（4+20+4=28）结构体变量是一个整体，
5、要访问其数据成员，要用结构体变量是一个整体，要访问其数据成员，要用成员运算符成员运算符“”指定该成员属于哪个变量。指定该成员属于哪个变量。 对结构体变量进行初始化有以下几种常用的方法：对结构体变量进行初始化有以下几种常用的方法： 1. 在定义时进行初始化在定义时进行初始化struct student int num；char name20；char sex；float CPPscore；sd1=40301,”YangKe”,M,89.5；6.1.3结构体类型变量的初始化与引用结构体类型变量的初始化与引用 2.用对象流用对象流cin进行初始化进行初始化cinsd1.numsd1.namesd1.
6、sexsd1.CPPscore;3.使用赋值语句进行初始化使用赋值语句进行初始化sd1.num=40301;sd1.name=” YangKe”; /错误错误 sd1.sex=M；sd1.CPPscore=89.5; 结构体变量的引用应遵循以下规则：结构体变量的引用应遵循以下规则：1.不能将一个结构体变量作为一个整体进行输不能将一个结构体变量作为一个整体进行输入输出。入输出。例如：例如：cinsd1; /错误错误2.允许将一个结构体变量直接赋值给另一个具允许将一个结构体变量直接赋值给另一个具有相同类型的结构体变量。有相同类型的结构体变量。例如：例如：student sd2; sd2=sd1;
7、则变量则变量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, sd
8、1.name); sd1.CPPscore+;注意：注意：结构体成员可以是另一个结构体类结构体成员可以是另一个结构体类型的变量（见下例）。型的变量（见下例）。 struct date int month; int day; int year; struct student int num; char name20; date birthday; student1；student类型中的类型中的birthday成员就是一个成员就是一个date结构体类结构体类型的变量。型的变量。如果某成员本身又是一个结构体类型，则只能通过如果某成员本身又是一个结构体类型，则只能通过多多级的分量运算级的分量运算，对
9、最低一级的成员进行引用。，对最低一级的成员进行引用。格式为：格式为：结构体变量结构体变量.成员成员.子成员子成员. .最低级子成员最低级子成员如：引用结构体变量如：引用结构体变量student1中的中的birthday成员：成员：student1.birthday.year，student1.birthday.month6.1.4指向结构体变量的指针指向结构体变量的指针 一个结构体变量的指针就是给该变量一个结构体变量的指针就是给该变量所分配内存段的起始地址。可以定义一个所分配内存段的起始地址。可以定义一个指针变量，用来指向一个结构体变量。此指针变量，用来指向一个结构体变量。此时该指针变量的值就
10、是结构体变量的起始时该指针变量的值就是结构体变量的起始地址。地址。 下面通过一个例子来说明指向结构体下面通过一个例子来说明指向结构体变量的指针变量的使用。变量的指针变量的使用。 例例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; /定义了定义了st
11、udent类型的变量类型的变量 stu_1 student *p; /p是指向结构体是指向结构体student类型的类型的指针变量指针变量p=&stu_1;/将将stu_1的起始地址赋给的起始地址赋给 pstu_1.num=40301;strcpy(stu_1.name,” YangKe”);stu_1.sex=M; stu_1.CPPscore=89.5; cout“NO:”stu_1.numt”name:”stu_1.namet”sex:”stu_1.sext”CPPscore:” stu_1.CPPscoreendl; cout“NO:”(*p).numt”name:”(*p).name
12、t”sex:”(*p).sext”CPPscore:” (*p).CPPscoreendl ; cout“NO:”numt”name:”namet”sex:”sext”CPPscore:”CPPscore成员名成员名 注意：注意：结构体的成员不能是自身的结构体变量，结构体的成员不能是自身的结构体变量，但可以是指向自身的结构体类型的指针变量。但可以是指向自身的结构体类型的指针变量。例如：例如：struct node long int num;float CPPscore;node *next; / next是指向是指向node的指针变量的指针变量node m; /错误错误;运行结果：运行结果：N
13、O:40301 name: YangKesex:M CPPscore:89.5NO:40301 name: YangKesex:M CPPscore:89.5NO:40301 name: YangKesex:M CPPscore:89.56.1.5 结构体数组结构体数组 结构体数组的定义方法和结构体变量相似，只需说明结构体数组的定义方法和结构体变量相似，只需说明它为数组类型即可。它为数组类型即可。 struct stu int num; char *name; char sex; float score;boy5; 以上示例定义了一个结构体数组以上示例定义了一个结构体数组boy，共有，共有5个
14、数组个数组元素，元素，boy0boy4。每个数组元素都具有。每个数组元素都具有stu的的结构形式，都是一个结构体类型的变量。结构形式，都是一个结构体类型的变量。 对结构体数组可以作初始化赋值对结构体数组可以作初始化赋值，例如：，例如：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.可将一个结构体数组元素赋值给
15、同一个结构可将一个结构体数组元素赋值给同一个结构体类型数组中的另一个元素或赋给同一类型体类型数组中的另一个元素或赋给同一类型的变量。的变量。例如：例如：boy2=boy0;stu aa; aa=stu0;2.不能把结构体数组元素作为一个整体直接进不能把结构体数组元素作为一个整体直接进行输入输出，只能对单个成员进行输入输出。行输入输出，只能对单个成员进行输入输出。 例如：例如：cin boy2;/wrong cinboy0.sex;/right6.1.6用结构体变量作函数参数用结构体变量作函数参数 结构体类型变量可作为函数的参数，函数结构体类型变量可作为函数的参数，函数返回值的类型也可为结构体类
16、型。返回值的类型也可为结构体类型。 当函数的形参与实参为结构体类型的当函数的形参与实参为结构体类型的变量时，这种结合方式属于值调用方式，变量时，这种结合方式属于值调用方式，即属于值传递。要求实参与相应的形参必即属于值传递。要求实参与相应的形参必须是同一类型的结构体变量。须是同一类型的结构体变量。例例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.
17、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;运行结果：运行结果：300300 y.m=400 y.x y.m=400 y.x=600=600 程序解读：程序解读：（1）swap函数中形参函数中形参s1和和s2是结构体是结构体s类类型的变量。型的变量。（2）因为形参与实参之间参数的传递方式）因为形参与实参之间参数的传递方式属于值传递，因此属于值传递，因此swap函数中形参函数中形
18、参s1和和s2的值进行了交换，但并没有影响到实参的值进行了交换，但并没有影响到实参r1和和r2的值。所以的值。所以r1.m依然等于依然等于100。（3）fun函数的返回值类型为结构体类型，函数的返回值类型为结构体类型，即即s类型。函数的功能是分别求出两个结构类型。函数的功能是分别求出两个结构体类型变量中对应的成员变量的和，即体类型变量中对应的成员变量的和，即s1.m+s2.m;和和s1.x+s2.x;求出的和存放在局求出的和存放在局部结构体变量部结构体变量t中。函数返回中。函数返回t的值。的值。 例例6-3 建立一个学生档案的结构体数组，描建立一个学生档案的结构体数组，描述一个学生的信息：姓名
19、，年龄，述一个学生的信息：姓名，年龄，C+成绩，成绩，并输出已建的学生档案。并输出已建的学生档案。算法：算法：（1）定义一个描述学生信息的结构体类型。）定义一个描述学生信息的结构体类型。（2）通过输入语句）通过输入语句cin输入某个学生的信息。输入某个学生的信息。（3）处理多个学生信息时，因为已经限定学）处理多个学生信息时，因为已经限定学生信息都一致，所以定义一个结构体类型的生信息都一致，所以定义一个结构体类型的数组，对每个数组元素进行输入、输出的处数组，对每个数组元素进行输入、输出的处理。理。 #includestruct stuchar name8;int age; float cscor
20、e;stu input(stu x)cinx.namex.agex.cscore ;return x;void output(stu x) cout x.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;In; float an; 这时我们可以用这时我们可以用C+的的new运算符来动态地分配运算符来动态地分配一个有一个有n个元素的
21、数组。个元素的数组。 new运算符运算的结果是动态申请内存空间的起始地址。例如：运算符运算的结果是动态申请内存空间的起始地址。例如：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开辟一个元素的
22、动态字符型内存开辟一个元素的动态字符型内存空间，为空间，为p2 开辟开辟10个元素的字符型动态连续内存空个元素的字符型动态连续内存空间，为间，为p3开辟了一个开辟了一个5行行10列的字符型二维数组动态列的字符型二维数组动态内存空间，为内存空间，为p4开辟一个开辟一个50个元素的字符型一维数个元素的字符型一维数组动态内存空间。组动态内存空间。 可以在分配单个的动态内存的同时给该内存赋一个可以在分配单个的动态内存的同时给该内存赋一个初始值，如对上面初始值，如对上面p1，可以这样赋初值：，可以这样赋初值：p1=new char(A) ; 但在给数组或结构体数据分配动态内存的同时不可但在给数组或结构体
23、数据分配动态内存的同时不可以对其赋初值，如：以对其赋初值，如：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 ;/错误错误系统不会自动释放动态分配的内存空间，因此动系统不会自动释放动态分配的内存空间，因此动态分配的内存在使用完后应释放掉。如对上面分态分配的内存在使用完后应释放掉。如对上面分配的动态内存，可以作如下释放：配的动态内存，可以作如下释放：delete p
24、1 ; 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; /头指针没有指向任一个结点，链表头指针没有指向任一个结点，链表为空为空链表结点所占内存单元是动态分配的，创建一个结点需要用链表结点所占内存单元是动态分配的，创建一个结点需要用到
25、到new运算符。语句如下：运算符。语句如下：new node;new运算的结果是个地址值，因此要定义一个指针变量来保运算的结果是个地址值，因此要定义一个指针变量来保存该运算结果，以便给申请的内存单元存储对应的数据。存该运算结果，以便给申请的内存单元存储对应的数据。node *p;p=new node;第一个结点的内存单元有了，下面把实际数据存储进去。第一个结点的内存单元有了，下面把实际数据存储进去。p-num=40301;p-CPPscore=85.5;6.3.2 链表的建立链表的建立例例6-4 写一个函数建立一条有写一个函数建立一条有4名学生数据的单向链表名学生数据的单向链表 算法：算法：（
26、1）目前在内存中没有任何的学生数据。因此要用）目前在内存中没有任何的学生数据。因此要用new运运算符动态申请内存空间。算符动态申请内存空间。让让p指针指向该空间。指针指向该空间。（2）把学生学号、）把学生学号、C+分数这些实际数据赋值给第一个结分数这些实际数据赋值给第一个结点的成员项。这时用头指针指向刚建好的第一个结点即点的成员项。这时用头指针指向刚建好的第一个结点即head=p ;p指针值可以更新，保存动态申请的第二个内存指针值可以更新，保存动态申请的第二个内存空间的地址。即空间的地址。即p=new node ;（3）依次类推，当建立到第）依次类推，当建立到第4个学生数据时，第个学生数据时，
27、第4个结点就个结点就是尾结点，它的是尾结点，它的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 ;
28、 else /A点点 pend-next=p ; / pend指向指向p所指向结点的前驱结点所指向结点的前驱结点 pend=p ; /pend指向链尾，用于在其后插入新创建的指向链尾，用于在其后插入新创建的结点结点 couta; coutscore ; If(head) pend-next=0 ; / 置链尾标志置链尾标志 return head ; 6.3.3 链表的输出链表的输出链表的输出是从链表头指针开始，逐个结点输出。链表的输出是从链表头指针开始，逐个结点输出。每输出一个结点，则由该结点的每输出一个结点，则由该结点的next指针取得下指针取得下一个结点，直到链表的尾结点。输出链表的一个
29、结点，直到链表的尾结点。输出链表的print( )函数的形参不能是引用类型的变量，因为函数的形参不能是引用类型的变量，因为要保持要保持“头指针头指针”head的值不变。即不能定义为的值不变。即不能定义为void print(node & *head );例例6-5 写一个函数输出链表上各个结点的值。写一个函数输出链表上各个结点的值。 编程实现：编程实现：void print(node *head ) if(head=0) cout 链表为空链表为空!n ; return ; node *p=head ; cout链表上各个结点的值为：链表上各个结点的值为：n;cout学号学号t C+成绩成绩n
30、 ; while(p!=0) cout numtCPPscorenext ; /p指向下一个结点指向下一个结点 6.3.4释放链表的结点空间释放链表的结点空间 我们建立的链表是动态链表，组成链表的每个我们建立的链表是动态链表，组成链表的每个结点的内存单元都是通过结点的内存单元都是通过new运算符动态申请空间运算符动态申请空间的。因此在对链表操作完毕后，动态申请的空间要的。因此在对链表操作完毕后，动态申请的空间要释放掉，以便于对内存进行有效的管理。定义一个释放掉，以便于对内存进行有效的管理。定义一个函数函数release来完成此操作。该函数的形参是指向结来完成此操作。该函数的形参是指向结构体类型
31、的指针变量。构体类型的指针变量。 例例6-6 释放链表的结点空间释放链表的结点空间 编程实现：编程实现：void release(node *head ) if(head=0) coutnext ; /头指针不断后移，指向头指针不断后移，指向链表的各个结点链表的各个结点delete p; /释放释放p指针指向的结点的内存单元指针指向的结点的内存单元 cout结点空间释放完毕结点空间释放完毕!;6.3.5 主函数的编写主函数的编写例例6-7链表主函数的编写链表主函数的编写#includestruct node long int num;float CPPscore; node *next; ;v
32、oid main( ) node *create( ); /该函数建立一条有该函数建立一条有4名学生数据的单向链表名学生数据的单向链表void print(node *head ); /该函数输出链表上各个结点的值该函数输出链表上各个结点的值void release(node *head ); /该函数释放链表的结点空间该函数释放链表的结点空间node *head;head=create( );print(head);release(head); 调试与运行结果：调试与运行结果：请输入学号请输入学号:40301请输入分数请输入分数(分数为负表示结束输入分数为负表示结束输入)：85.5请输入学号
33、请输入学号:40302请输入分数请输入分数(分数为负表示结束输入分数为负表示结束输入)：78.5请输入学号请输入学号:40303请输入分数请输入分数(分数为负表示结束输入分数为负表示结束输入)：80.5请输入学号请输入学号:40304请输入分数请输入分数(分数为负表示结束输入分数为负表示结束输入)：83请输入学号请输入学号:40305请输入分数请输入分数(分数为负表示结束输入分数为负表示结束输入)：-7链表上各个结点的值为：链表上各个结点的值为：学号学号 C+成绩成绩4030185.54030278.54030380.54030483结点空间释放完毕结点空间释放完毕!6.4 链表的复杂操作链表
34、的复杂操作链表的复杂操作有链表的复杂操作有三种三种：删除链表中具有指定值的一个结点；删除链表中具有指定值的一个结点；把创建好的一个结点插入链表；把创建好的一个结点插入链表；建立一条有序链表。这三种操作都要基建立一条有序链表。这三种操作都要基于查找第于查找第n个结点的操作。个结点的操作。4030185.5&node24030278.5&node340304830node1node2node34030380.5&node4node4head&node1 对链表进行操作时，注意的语句对链表进行操作时，注意的语句 1.1.设指针变量设指针变量p1p1指向指向node1node1，若让，若让p1p1指向
35、指向node2node2，指针变量指针变量p2p2指向指向node1node1，可使用语句，可使用语句: p2=p1; : p2=p1; p1=p1p1=p1-next;-next;注意这两条语句的顺序不能颠倒，注意这两条语句的顺序不能颠倒，否则否则p2p2也指向也指向node2node2。图图 6.46.4学生信息链表示意图学生信息链表示意图2.设设p1指向指向node1，p2指向指向node2，指针变，指针变量量p3指向指向node3，若让，若让node1与与node3链链接起来，即接起来，即node2不在链表中，可使用语不在链表中，可使用语句句: p1-next=p3;或或p1-next
36、=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指向指向node1，p2指向新结点指向新结点node5，若，若让
37、让node5做链表的首结点，可使用语句：做链表的首结点，可使用语句：p2-next=p1；head=p2;或或p2-next=head；head=p2;4030185.5&node24030278.5&node34030483NULLnode1node2node34030380.5&node4node4head&node16.4.16.4.1结点的删除结点的删除4030185.5&node24030278.5&node34030380.5&node44030483NULL&node1node1node2node3node4p1p1p2p2p1p1p2p2删除第删除第n个结点的关键步骤为：个结点
38、的关键步骤为： 查找第查找第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; 删除链表中具有指定值的一个
39、结点时有以删除链表中具有指定值的一个结点时有以下几种情况：下几种情况：链表是空表（无结点）；链表是空表（无结点）； 要删的是第一个结点；要删的是第一个结点； 要删的是中间的一个结点；要删的是中间的一个结点； 要删的是最后一个结点要删的是最后一个结点 链表中找不到要删除的结点。链表中找不到要删除的结点。 例例6-8 删除链表上一个结点删除链表上一个结点编程实现：编程实现：node *Delete_one_node(node *head,int num) node *p1,*p2;if(head=NULL)/第第种情况种情况coutdata=num)/ 第第种情况种情况p2=head;head=h
40、ead-next;delete p2;elsep2=p1=head; while(p2-data!=num&p2-next!=NULL) /查找要删除的结点查找要删除的结点 p1=p2;p2=p2-next; if(p2-data=num) p1-next=p2-next;delete p2; /第第种情况种情况 else cout没有找到要删除的结点没有找到要删除的结点;/第第种情况种情况return head;4030185.5&node24030278.5&node34030483NULLnode1node2node34030380.5&node4node4head&node16.4.1
41、6.4.1结点的插入结点的插入4030185.5&node24030278.5&node44030483NULL&node1node1node2node4p1p1p pp2p2 在第在第n个结点之后插入一个新结点的关键步骤为：个结点之后插入一个新结点的关键步骤为： 查找第查找第n个结点，让个结点，让p1指针指向它；指针指向它； 生成新结点，让生成新结点，让p指针指向它；指针指向它； p指针指向的结点插到指针指向的结点插到p1指针指向的结点之后。指针指向的结点之后。关键语句如下：关键语句如下：node *p1;p1=head;for(int i=1;inext;node *p=new node;
42、p-num=40303; p-CPPscore=80.5;if(n) p-next=p1-next; p1-next=p;else p-next=head; head=p; /插入的结点做第插入的结点做第一个结点一个结点将一个具有值的结点插入到一个有序链表中可将一个具有值的结点插入到一个有序链表中可遇到以下几种情况：遇到以下几种情况： 该链表是空表，则插入的结点做为第一个结点； 要插入的结点做链表的第一个结点； 在两结点之间，正常插入结点； 要插入的结点是尾结点。 例例6-9将一个结点插入有序链表，插入后链表仍保持有序将一个结点插入有序链表，插入后链表仍保持有序编程实现：编程实现：node *
43、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; p2=p1=head; /也可使用两个指针，编写结点插入也可使用两个指针，编写结点插入语句语句while(p2-next&p2-datadata)p1=p2;p2=p2-next; /p1指向指向p2的前驱的前驱if(p2-datadata) /第第种情况种情况p2-next=p; p-next
44、=0;else /第第种情况种情况p-next=p2; p1-next=p;return head; 例例6-10建立一条有序链表。链表的每一个结点包括：建立一条有序链表。链表的每一个结点包括：学号、姓名、年龄和学号、姓名、年龄和C+成绩。定义一个函数完成成绩。定义一个函数完成建立链表的工作，一个函数完成输出链表的各结点建立链表的工作，一个函数完成输出链表的各结点的值，一个函数完成释放链表的结点占用的动态存的值，一个函数完成释放链表的结点占用的动态存储空间。按储空间。按C+成绩升序排序。成绩升序排序。 算法：算法：建立一条有序链表可以在建立链表的过程中完建立一条有序链表可以在建立链表的过程中完
45、成。当建立第一个结点后，头指针成。当建立第一个结点后，头指针h指向它，第二指向它，第二个结点建立好后，把第二个结点的个结点建立好后，把第二个结点的C+成绩与第一成绩与第一个结点的相比较，如果第二个结点的个结点的相比较，如果第二个结点的C+成绩比第成绩比第一个结点的小，则使第二个结点的指针项一个结点的小，则使第二个结点的指针项next保存保存第一个结点的地址，头指针第一个结点的地址，头指针h移动指向第二个结点；移动指向第二个结点；反之使第一个结点的指针项反之使第一个结点的指针项next保存第二个结点的保存第二个结点的地址，头指针地址，头指针h依然指向第一个结点。以此类推，依然指向第一个结点。以此
46、类推，若第三个结点的若第三个结点的C+成绩在另两个结点之间，则把成绩在另两个结点之间，则把第三个结点插入到链表中。总之，第三个结点插入到链表中。总之，h始终指向始终指向C+成成绩最小的结点。绩最小的结点。编程实现：编程实现：#include#define NULL 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=
47、NULL)h=p;elsep1=p2=h;while(p2&p-c=p2-c)p1=p2;p2=p1-next;if(p2=h)p-next=p2;h=p;elsep-next=p2;p1-next=p; i+;return h; void print(NODE *h)NODE *p;p=h;while(p!=0)coutidtnametagetcnext;coutnext;delete p;void main()int n;cout请输入班级人数！请输入班级人数！endln;coutendl;cout请输入班级学生信息！请输入班级学生信息！endl;cout学号学号 姓名姓名 年龄年龄 C+
48、成绩成绩endl;NODE *h;h=Create(n);coutendl学号学号 姓名姓名 年龄年龄 C+成绩成绩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所指向链表上各结点的数所指向链表上各结点的数据按据按dat
49、a值升序排序。结点的数据结构如下：值升序排序。结点的数据结构如下：struct node int data;node *next; ; 算法：算法：初始时，使指针变量初始时，使指针变量p p指向该指向该链表的首结点，从链表的首结点，从p p之后的所有结点之后的所有结点中找出中找出datadata值最小的结点，让值最小的结点，让p1p1指向指向该结点。将该结点。将p p指向结点的指向结点的datadata值与值与p1p1指向结点的指向结点的datadata值进行交换。让值进行交换。让p p指指向下一个结点，依此类推，直至向下一个结点，依此类推，直至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本章结束！本章结束！
