结构与链表 c++ 描述

(共137张PPT)
C++程序设计
第7单元 结构与链表
【学习目标】
掌握结构数据类型的定义和使用方法，理解链表的概念，掌握链表的插入、删除等基本操作。
【重点和难点】
重点： 结构类型的概念、作用和特点；
结构变量的定义、初始化和使用；
链表概念及基本操作。
难点： 链表创建、插入、删除等基本操作。
7.1 结构体
以前所使用的数据（整型、字符、浮点型）都是C++预先定义的基本数据类型，这些数据类型的存储方法和运算规则是由语言本身规定，它们与机器硬件有更直接的关系。但仅用这些基本数据类型还难以描述现实世界的各种各样的客观对象之间的关系。
　 在实际问题中，一组数据往往具有不同的数据类型。例如，在学生登记表中，姓名应为字符型；学号可为整型或字符型；年龄应为整型；性别应为字符型；成绩可为整型或实型。由于数组还必须要求元素为相同类型，显然不能用一个数组来存放这一组数据。因为数组中各元素的类型和长度都必须一致，以便于编译系统处理。
　 我们可用结构数据类型来解决这个问题。为了满足程序设计的需要，C++允许我们自己定义数据类型，称之为自定义数据类型，结构是自定义数据类型中的一种，它可将多种数据类型组合在一起使用。
一、为什么要用结构
7.1 结构体
数组是用来保存许多数据的，但它有许多缺点：
数组的大小往往是固定的，在程序运行期间通常是不能改变的。我们在定义数组时必须足够大，保证程序运行时不会溢出。但是，这也常常导致大量数组存储单元的浪费。
数组需要一块连续的内存空间。但当应用程序较大，数组需要的内存块也较大时，这可能会降低程序的效率。
如果在数组元素中，有较多的插入操作，则被插元素后的元素需要向后移位，这也浪费机器的运行时间。
7.1 结构体
如：
记录一批小孩的身高、重量、年龄和性别等。可用数组处理：
const int nMaxChildren = 1000;
　　 double heights[nMaxChildren];
　　 double weights[nMaxChildren];
　　 int years[nMaxChildren];
　　 int months[nMaxChildren];
　　 char gender[nMaxChildren];
如要查找某一个小孩的身高、体重等，可以通过读取有相同下标的数组元素得到，如heights[5], weights[5]等。
但是：
一个小孩到底有哪些相关的数据项，不是很明显；
如按身高等排序，要获取某一个小孩的相关数据项将十分困难。
7.1 结构体
在C++中，允许同时指定一组数据变量，称为结构。
结构与数组不同，是不同数据类型的数据集合。结构中的不同类型的数据都是有关联的，它们被作为一个整体来看待。
结构类型在使用之前必须先定义。
结构类型定义的一般形式是：
　　struct 结构名
　　{
　　　 数据类型标识符1 变量名1；
　　　 数据类型标识符2 变量名2；
　　　 …………
　　　 数据类型标识符n 变量名n；
　　}；
二、结构类型
7.1 结构体
例如：
struct Child
{
　　　double height;
　　　double weight;
　　　int years;
　　　int months;
　　　char gender;
};
struct是关键字。Child类型包含两个double、两个int和一个char域（或成员），它可以与C++的基本数据类型一样地使用。
注意：结构类型定义也是一个语句，所以结尾必须有分号（;），否则，会产生编译错误。
7.1 结构体
1. 定义结构变量，可以采用以下三种方法：
（1）先定义结构类型，再定义结构类型变量。
这种方式定义结构变量的一般形式是：
结构类型名 变量名1，变量名2，…，变量名n；
三、结构变量
7.1 结构体
（2）在定义结构类型的同时定义结构变量。
一般形式：
　　 struct 结构名
　　 {
　　　 成员列表
　　 }变量名列表;
例如：
　　 struct example
　　 {
　　　 int a;
　　　 float b;
　　　 double c;
　　　 example * ptr;
　　 }x,y;
7.1 结构体
（3）直接说明结构变量
一般形式为：
　　 struct
　　 {
　　　 成员列表
　　 }变量名列表;
与方法（2）区别在于：
省去了结构名，而直接给出结构变量。由于它不便于使用，我们很少用这种方法定义结构变量。
7.1 结构体
例：
struct date
{
　 int month;
　 int day;
　 int year;
};
struct
{
　 int num;
　 char name[20];
　 char sex;
　 date birthday;
　 float score;
}boy1,boy2;
练习一
用三种方式定义职工、学生等结构体变量。
struct employee //定义职工结构体数据类型
{
int no ; //职工编号
char name[8]; //职工姓名
char addr[40]; //家庭地址
};
struct student //定义学生结构体数据类型
{
int no; //学号
float eng,phy,math,ave; //英语、数学、物理成绩、平均成绩
} stu1,stu2; //同时定义结构体变量stu1、stu2
7.1 结构体
2. 访问结构成员
（1）点记法
　　 结构变量名.成员名
这样的表达式也称之为成员选择表达式，其中圆点“.”称为成员运算符，它的运算优先级很高。
对于给成员赋值语句cute.weight=35.4，系统的操作顺序是先找到结构变量cute，然后从cute所在的存储空间找到成员weight，把35.4存入到weight分配的存储空间。
由于成员运算符“.”的结合性是从左到右的，因此可以引用成员类型较为复杂的结构。
对于嵌套结构类型，即一个结构的成员本身是一个结构类型，可以通过嵌套引用的方法对最低级的成员进行引用。
7.1 结构体
（2）指针法
可以通过结构指针来访问结构变量的成员
此时用“箭头运算符”，形式为：
指向结构的指针变量名->成员名
7.1 结构体
3. 结构变量初始化
结构变量可以在定义时初始化，例如：
struct stu
　　 {
　　　 int num;
　　　 char *name;
　　　 char sex;
　　　 float score;
　　 }boy2,boy1={102,"Zhang ping",'M',77.5};
定义了结构类型stu的同时，也定义了结构变量boy1和boy2，并对boy1作了初始化。
7.1 结构体
在数组中，数组是不能彼此赋值的。
因为数组名是一个常量指针，不允许被赋值。数组本质上不是数据类型，定义的每个数组都认为是不同类型的，即使数组元素个数相同。
结构就不同了，它大小固定，可以被赋值。
例如： struct Person
{
　　　　　char name[20];
　　　　　unsigned long id;
　　　　　float salary;
};
Person pr1={"Frank Voltaire",12345678,3.35};
Person pr2;
pr2=pr1;
注意：两个不同结构名的变量是不允许相互赋值的，即使两者包含有同样的成员。
4．结构赋值
7.1 结构体
5. 结构的嵌套
结构可以嵌套，即结构中可以包含结构成员。例如：
struct Education
　　　　{
　　　　　 char major[20]；
　　　　　 char degree[20]；
　　　　　 double gpa；
}；
　　　　struct Student
{
　　　　　 Education school； //结构中嵌套一个Education结构
　　　　　 char id[20]；
　　　　　 int graduate；
　　　　}；
Student ss；
7.1 结构体
在引用嵌套结构的成员时，要使用多个点操作符，例如，
ss.school.major
注意：
结构成员不能是自身的结构变量，但可以用自身结构指针作为成员。
例如，下面的结构含有一个自身结构的指针，但不应有自身结构的变量：
struct List
{
char name[20]；
List* pN； //可以：List结构指针作为其成员
List m; //错误：不应含有自身结构变量
}；
练习二
假设职工信息包括姓名、性别、出生年月、政治面貌、工资等。从键盘输入相关信息，并输出。
7.2 结构与函数
1. 结构的成员作函数参数
double addsalary(double x)
{
x=x+x*0.05;
return x;
}
main()
{
……
first_employee.salary=addsalary(first_employee.salary);
……
}
一、结构作函数参数
7.2 结构与函数
2. 整个结构作函数参数
struct Person
{
　　　　　char name[20];
　　　　　unsigned long id;
　　　　　float salary;
};
void Print(Person pr)
{
　　　　　cout <　　　　　　　　<　　　　　　　　<}
7.2 结构与函数
Person allone[4]=
{
{"jone", 12345, 339.0},
{"david", 13916, 449.0},
{"marit", 27519, 311.0},
{"yoke", 12335, 511.0}
};
void main()
{
　　　　　for(int i=0; i<4; i++)
　　　　　Print(allone[i]);
}
7.2 结构与函数
3. 传递结构的引用
结构也可以引用传递，这种情况下仅仅把结构地址传递给形参。
struct Person
　　　　{
　　　　　char name[20];
　　　　　unsigned long id;
　　　　　float salary;
　　　　};
　　　　void Print(Person& pr)
　　　　{
　　　　　cout <　　　　　　　<　　　　　　　<　　　　}
7.2 结构与函数
Person allone[4]=
{
{"jone", 12345, 339.0},
{"david", 13916, 449.0},
{"marit", 27519, 311.0},
{"yoke", 12335, 511.0}
};
void main()
{
　　　　　for(int i=0; i<4; i++)
　　　　　Print(allone[i]);
}
7.2 结构与函数
1．返回结构
一个函数可以返回一个结构值。
#include
struct Person
{
　　　　　char name[20];
　　　　　unsigned long id;
　　　　　float salary;
};
二、返回结构
7.2 结构与函数
Person GetPerson()
{
　　　　　Person temp;
　　　　　cout <<"Please enter a name for one person:\n";
　　　　　cin>>temp.name;
　　　　　cout <<"Enter one's id number and his salary:\n";
　　　　　cin >>temp.id >>temp.salary;
　　　　　return temp;
}
7.2 结构与函数
void Print(Person& p)
{
cout <　　　　　 <　　　　　 <}
void main()
{
Person employee[3];
for(int i=0; i<3; i++)
{
　　　　　　employee[i]=GetPerson();
　　　　　　Print(employee[i]);
}
}
7.2 结构与函数
2. 返回结构的引用
一个函数可以返回一个结构的引用和结构的指针。
Person& GetPerson()
{
　　　　　Person p；
　　　　　cout<<"Please enter a name for one person：\n"；
　　　　　cin.get(p.name)；
　　　　　cout<<"Enter one's idnumber andhis salary：\n"；
cin>>p.id>>p.salary；
　　　　　return p；
}
7.2 结构与函数
void main()
{
...
　　　　　Person& sp=GetPerson()；
...
}
7.2 结构与函数
结构变量作为函数参数传递和作为函数结果返回时，坚持下面的基本规则：
对于小的结构数据，可以采用传值的方法。
对于大的结构数据，采用传地址或引用。因为占用内存大的结构变量，在复制时，对时间和空间的开销都较大。
如果需要修改结构变量数据，要传地址或引用，而传值是不能修改变量数据的。
如果要返回函数的一个局部变量的值，用return返回，不必考虑变量数据的大小。虽然有复制的开销，但不能返回局部变量的指针或引用，不过，可以返回用new申请内存的指针。
如果不需要改变所传递的参数或函数的返回结果，可以用const修饰形参（当形参为引用或指针时）或用const修饰返回类型。
练习三
定义结构类型Date{int day,int month,int year}；编写函数Date One(Date Next)，根据今天的日期Next，确定明天的日期。
注意：考虑月末、年末、闰年等特殊情况。
7.3 结构数组
结构是一个数据类型，所以也可以拥有结构数组。要定义结构数组，必须先声明一个结构，然后定义这个结构类型的数组。
例如：
定义一个100个元素组成的Person结构类型数组：
　　　　struct Person
　　　　{
　　　　　char name[20]；
　　　　　unsigned long id；
　　　　　float salary；
　　　　}；
Person allone[100]；
结构数组中，每个元素都是结构变量，访问结构数组元素中的成员，方法与前类似。
7.3 结构数组
举例：
下面的程序中，对一个Person结构数组进行“冒泡法”排序，工资高的排在后面：
struct Person
{
char name[20];
　　　　　 unsigned long id;
　　　　　 float salary;
　　　　};
　　　　Person allone[6]=
{
{"jone", 12345, 339.0},
{"david", 13916, 449.0},
　　　　　　 　 {"marit", 27519, 311.0},
　　　　　 {"jasen", 42876, 623.0},
　　 {"peter", 23987, 400.0},
　　　　 {"yoke", 12335, 511.0}
};
7.3 结构数组
void main()
{
　　　　　Person temp;
　　　　　for(int i=1; i<6; i++)
{
　　　　　　for(int j=0; j<=5-i; j++)
　　　　　　 if(allone[j].salary > allone[j+1].salary)
　　　　　 　 {
　　　　　　　　temp=allone[j];
　　　　　　　　allone[j]=allone[j+1];
　　　　　　　　allone[j+1]=temp;
　　　　　　 }
　　　　　}
　　　　　for(int k=0; k<6; k++)
　　　　　　cout <　　　　　　　　 <　　　　　　　 　<}
排序中交换数组元素，就是交换结构变量，程序中以结构变量赋值的方法来进行交换。
练习
定义一个学生成绩结构体类型，包含“学号”、“姓名”、“性别”、“年龄”、“班级”、“英语”、“数学”、“物理”、“总分”、“名次”等信息。编写6个函数分别用于：
使用结构体数组，输入全班10名学生的上述信息
计算每一个学生的总分、平均分；
计算每一门课程的平均分；
查找成绩有不及格的学生信息；
按学生成绩总分降序排序；
输出全班学生的学号、总分及名次。
7.4 结构指针
根据结构类型可以定义一个变量，是变量就有地址。
结构不像数组，结构变量不是指针。
通过取地址“&”操作，可以得到结构变量的地址，这个地址就是结构的第一个成员地址。
可以将结构变量的地址赋给结构指针，结构指针通过箭头操作符“—>” 来访问结构成员。
struct Person
{
　　　　　char name[20];
　　　　　unsigned long id;
　　　　　float salary;
};
7.4 结构指针
如：
void main( )
{
　　　　　Person pr1;
　　　　　Person* prPtr;
　　　　　prPtr=&pr1;
　　　　　strcpy(prPtr->name,"David Marat");
　　　　　prPtr->id=987654321;
　　　　　prPtr->salary=335.0;
　　　　　cout <name <<" "
　　　　　 　　<id <<" "
　　　　　　 　<salary <}
7.4 结构指针
注意：
当用点操作符时，它的左边应是一个结构变量
当用箭头操作符时，它的左边应是一个结构指针。
箭头操作符与点操作符是可以互换的：
prPtr—>name
等价于：
prl.name
等价于：
(*prPtr).name
练习一
使用结构指针：
1 假设有10名学生信息，包括姓名、性别、出生年月、总分等。从键盘输入相关信息，并输出。
2 显示第一题中总分前三名的学生信息。（利用选择法排序）
7.5 指向自身的结构指针
我们已经知道，定义结构体类型时可以嵌套，即结构体的某个成员也可以是结构体类型。
例如下面首先定义结构体Date：
struct Date
{
int year；
int month；
int day；
};
再定义结构体Stu：
struct Stu
{
int ST_Num；
char ST_Name[8]；
bool ST_Sex；
Date ST_Birth；
float ST_Culture ；
float ST_Specialty；
};
7.5 指向自身的结构指针
声明一个结构变量：
Stu per；
在引用嵌套结构的成员时，可以使用多个点操作符，例如，
per.ST_Birth.year=2008;
7.5 指向自身的结构指针
但定义结构体不能进行自身嵌套，即成员不能是结构自身的简单变量。
例如，当使用VC++集成环境调试下面的代码时：
struct Stu
{
int ST_Num;
char ST_Name[8];
bool ST_Sex;
Date ST_Birth;
float ST_Culture;
float ST_Specialty;
Stu Next; //结构的简单变量
};
7.5 指向自身的结构指针
将提示如下错误：
警告：
使用了“正在定义的对象‘Stu’”，即违反了“先定义，后使用”的基本原则。
uses 'Stu', which is being defined
7.5 指向自身的结构指针
但是，我们可以用结构的指针变量作为结构的自身成员。
例如：
struct Stu
{
int ST_Num；
char ST_Name[8]；
bool ST_Sex；
Date ST_Birth；
float ST_Culture ；
float ST_Specialty；
Stu *Next； //指针类型变量
};
Next 就是指向自身的
结构指针
7.5 指向自身的结构指针
假如，我们再声明四个Stu类型的结构指针变量：
Stu *P1,*P2,*P3,*P4;
2000
ST_Num
···
ST_Sports
Next
P2
2000
1000
ST_Num
···
ST_Sports
Next
P1
1000
3000
ST_Num
···
ST_Sports
Next
P3
3000
4000
ST_Num
···
ST_Sports
Next
P4
4000
7.5 指向自身的结构指针
由图中可以看出，指针变量P1、P2、P3、P4的值即为它们所指向的结构变量存储单元的首地址，假设分别为：1000、2000、3000及4000。
这四个结构变量的存储单元之间是非连续的，在分配存储空间的时候是随机的，如果我们利用其中的Next成员指向另一个结构体变量，就可以在它们之间建立联系，如下图所示。
7.5 指向自身的结构指针
2000
ST_Num
···
ST_Sports
3000
P2
2000
1000
ST_Num
···
ST_Sports
2000
P1
1000
3000
ST_Num
···
ST_Sports
4000
P3
3000
4000
ST_Num
···
ST_Sports
Next
P4
4000
7.5 指向自身的结构指针
这种联系是通过将一个变量的首地址赋予另一个变量的Next成员，如P2指向单元的首地址2000赋予P1的Next成员。
为便于表述，我们将这种结构体变量称为结点。
这些结点通过每个Next成员依次链接，能构造任意长的结构点链条，这样的结构链就称为链表。
我们可以通过链表的head指针找到链表的头结点，然后通过该结点的指针域找到一个结点的首地址，从而可以找到该链表的所有结点。
7.5 指向自身的结构指针
链表用一组任意的存储单元来存放表的结点，这组存储单元既可以是连续的，也可以是不连续的。结点的逻辑次序和物理次序不一定相同。
数组是一组相同类型的数据的集合，在内存中连续存放，是线性表的一种。
结构是一组不同类型的数据的集合，一个结构变量的各个成员在内存中也是连续存放的。
结构数组是一组结构数据的集合，也具有数组的各种性质，如连续存储。
7.5 指向自身的结构指针
一个简单的链表：
Head
为表头指针.
7.5 指向自身的结构指针
头指针head和终端结点指针域的表示
（1）由于每个结点的存储地址是存放在其前趋结点的next域中，而开始结点并无前趋，故应设头指针head指向开始结点。
注意： 链表由头指针唯一确定，单链表可以用头指针的名字来命名。
【例】
头指针名是head的链表可称为表head。
（2）终端结点无后继，故终端结点的指针域为空，即NULL。
7.5 指向自身的结构指针
图示法
由于常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用箭头来表示链域中的指针。
线性表：
bat，cat，eat，fat，hat，jat，lat，mat
的单链表就可以表示为下图形式：
7.5 指向自身的结构指针
7.2 结构与指针
根据结构类型可以定义一个变量，是变量就有地址。
结构不像数组，结构变量不是指针。
通过取地址“&”操作，可以得到结构变量的地址，这个地址就是结构的第一个成员地址。
可以将结构变量的地址赋给结构指针，结构指针通过箭头操作符“—>” 来访问结构成员。
struct Person
{
　　　　　char name[20];
　　　　　unsigned long id;
　　　　　float salary;
};
7.2 结构与指针
如：
void main( )
{
　　　　　Person pr1;
　　　　　Person* prPtr;
　　　　　prPtr=&pr1;
　　　　　strcpy(prPtr->name,"David Marat");
　　　　　prPtr->id=987654321;
　　　　　prPtr->salary=335.0;
　　　　　cout <name <<" "
　　　　　 　　<id <<" "
　　　　　　 　<salary <}
7.2 结构与指针
注意：
当用点操作符时，它的左边应是一个结构变量
当用箭头操作符时，它的左边应是一个结构指针。
箭头操作符与点操作符是可以互换的：
prPtr—>name
等价于：
prl.name
等价于：
(*prPtr).name
7.5 链表
一、基础知识
1. 线性与非线性数据结构
在数据集合中，依据数据成员之间的关系的不同，可把数据结构分为两大类：
线性结构：各个数据成员依次排列在一个线性序列中，如数组、链表等；
非线性结构：每个数据成员可能与零个或多个其它数据成员之间发生关系，如树、图等。
7.5 链表
2. 线性表
线性表是一种线性结构，元素“一个接一个的排列”，元素类型是相同的。线性表定义如下：
(a1，a2，… ai-1，ai，ai+1，…an)
其中n为表长， n＝0 时称为空表。
将 ai-1 称为 ai 的直接前趋，ai+1 称为 ai 的直接后继。
即：
对于ai，当 i=2，...，n 时，有且仅有一个直接前趋 ai-1.；
对于ai，当i=1，2，...，n-1 时，有且仅有一个直接后继 ai+1；
a1 是表中第一个元素，它没有前趋；
an 是最后一个元素无后继。
7.5 链表
3. 数组与链表
数组是一组相同类型的数据的集合，在内存中连续存放，是线性表的一种。
结构是一组不同类型的数据的集合，一个结构变量的各个成员在内存中也是连续存放的。
结构数组是一组结构数据的集合，也具有数组的各种性质，如连续存储。
如将多个结构变量不组成数组结构，不用一个连续的内存块。则可使用一种称作“链表”的数据结构，此时每一个结构变量动态分配内存单元，通过指针把他们联系在一起。链表元素称之为链表结点。
7.5 链表
二、单链表
1. 存储
① 用一组任意的存储单元来存放表的结点，这组存储单元既可以是连续的，也可以是不连续的。
② 结点的逻辑次序和物理次序不一定相同。
为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址。
7.5 链表
一个简单的链表：
Head
为表头指针.
7.5 链表
头指针head和终端结点指针域的表示
（1）由于每个结点的存储地址是存放在其前趋结点的next域中，而开始结点并无前趋，故应设头指针head指向开始结点。
注意： 链表由头指针唯一确定，单链表可以用头指针的名字来命名。
【例】
头指针名是head的链表可称为表head。
（2）终端结点无后继，故终端结点的指针域为空，即NULL。
7.5 链表
图示法
由于常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用箭头来表示链域中的指针。
线性表：
bat，cat，eat，fat，hat，jat，lat，mat
的单链表就可以表示为下图形式：
7.5 链表
7.5 链表
2. 结点类型
struct Node
{ DataType data; struct node *next; };
data为数据域，存放结点数值；next是指针域，指向下一个结点。
任意数据类型
例如：
struct Student
{
　　　　　 long number;
　　　　　 Student* next;
};
7.5 链表
指针变量和结点变量
7.5 链表
（1）结点分量的访问
利用结点变量的名字*p访问结点分量
方法1： (*p).data
(*p).next
方法2：
p－＞data
p－＞next
7.5 链表
（2）指针变量p和结点变量*p的关系
　 指针变量p的值 —— 结点地址
　结点变量*p的值 —— 结点内容
　(*p).data的值 —— p指针所指结点的data域的值
　(*p).next的值 —— *p后继结点的地址
　　*((*p).next) —— *p后继结点
7.6 链表基本操作
首先新建一个结点，将表头指针head指向第一个结点。
然后，根据循环条件，依次生成新结点，将新结点插入到当前链表的表尾。
具体创建过程如下：
一、创建链表
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
1
head
NULL
pS
pEnd
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
1
head
pS
pEnd
第1次循环
NULL
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
1
head
pS
pEnd
第1次循环
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第1次循环
pS
pEnd
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第2次循环
pS
pEnd
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第2次循环
pS
pEnd
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第2次循环
pS
pEnd
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第2次循环
pS
pEnd
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第2次循环
pS
pEnd
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第2次循环
pS
pEnd
3
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第3次循环
pS
pEnd
3
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第3次循环
pS
pEnd
3
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第3次循环
pS
pEnd
3
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第3次循环
pS
pEnd
3
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第3次循环
pS
pEnd
3
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第3次循环
pS
pEnd
3
4
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第4次循环
pS
pEnd
3
4
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第4次循环
pS
pEnd
3
4
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第4次循环
pS
pEnd
3
4
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第4次循环
pS
pEnd
3
4
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第4次循环
pS
pEnd
3
4
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第4次循环
pS
pEnd
3
4
0
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
第5次循环
pS
pEnd
3
4
0
pS->number==0
循环结束
NULL
7.6 链表基本操作
Student* head; //链首指针
Student* Create()
{
head=NULL;
Student* pS; //创建的结点指针
Student* pEnd; //链尾指针
pS=new Student; //新建一个结点
cin >>pS->number;
pEnd=pS;
while(pS->number!=0)
{
if(head==NULL)
　　　　　　　head=pS;
else
　　　　　　　pEnd->next=pS;
pEnd=pS;
pS=new Student;
cin >>pS->number;
}
pEnd->next=NULL;
delete pS;
return(head);
}
结点类型 struct Student
{
　　　 long number;
　　　 Student* next;
};
2
1
head
pEnd
3
4
NULL
头
尾
7.6 链表基本操作
二、遍历链表
7.6 链表基本操作
void ShowList(Student* head)
{
Student *P;
P=head;
while(P)
{
　　　cout <number<　　　P=P->next;
}
}
结点类型
struct Student
{
long number;
Student* next;
};
2
1
head
P
3
4
NULL
遍历链表
P未指空,即
P！=NULL
7.6 链表基本操作
void ShowList(Student* head)
{
Student *P;
P=head;
while(P)
{
　　　cout <number<　　　P=P->next;
}
}
结点类型
struct Student
{
long number;
Student* next;
};
2
1
head
P
3
4
NULL
遍历链表
next
7.6 链表基本操作
void ShowList(Student* head)
{
Student *P;
P=head;
while(P)
{
　　　cout <number<　　　P=P->next;
}
}
结点类型
struct Student
{
long number;
Student* next;
};
2
1
head
P
3
4
NULL
遍历链表
依此类推
7.6 链表基本操作
1）查找第K个结点
从第一个结点起，判断当前结点是否是第K个，若是，则返回该结点的指针。直到表结束为止。若没有第K个结点，则返回空。
Student* GetNode(Student* head，int K)
{
Student *P;int n=0;
P=head;
while(P)
{
n++;
　　　 if(n==K) return P;
　　　 P=P->next;
}
return NULL;
}
三、查找结点
7.6 链表基本操作
2）查找值为X的结点
Student* GetNode(Student* head，int X)
{
Student *P;
P=head;
while(P)
{
　　　 if(P->number==X)
return P;
　　　 P=P->next;
}
return NULL;
}
思考：
如果有多个值为X的元素，如何处理？
7.6 链表基本操作
将值为x的新结点插入到表的第i个结点的位置上。见下图：
找到位置p，即ai-1
生成一个新结点S
设置新结点值为x
新结点指向下一个结点，即ai
p所指向的结点ai-1指向新结点S
四、插入结点
7.6 链表基本操作
void Ins(Student* head,
Student* stud)
{
if(head==NULL)
{
　　　 head=stud；
　　 stud->next=NULL；
　　　 return；
}
}
X
head
NULL
插入结点——原链表为空
stud
NULL
开始为空链表
7.6 链表基本操作
void Ins(Student* head,
Student* stud)
{
将stud的next成员指向链首，再将head指向stud即可：
…………
stud->next=head；
　 head=stud；
…………
}
1
X
head
2
3
NULL
插入结点——插在链表之首
stud
7.6 链表基本操作
void Ins(Student* head,
Student* stud)
{
将stud的next成员指向链首，再将head指向stud即可：
…………
stud->next=head；
　 head=stud；
…………
}
1
X
head
2
3
NULL
插入结点——插在链表之首
stud
7.6 链表基本操作
void Ins(Student* head,
Student* stud)
{
首先将P定位到最后结点
将P的next成员指向stud，再将stud的next设为NULL：
…………
P->next=stud；
　 stud->next=NULL；
…………
}
2
1
head
3
X
NULL
插入结点——插在链表之尾
stud
P
NULL
7.6 链表基本操作
void Ins(Student* head,
Student* stud)
{
……
首先定位到插入点
stud->next=P->next
p->next=stud
……
}
5
4
head
P
6
9
NULL
插入结点——插在链表中间
1
stud
7.6 链表基本操作
void Ins(Student* head,
Student* stud)
{
……
首先定位到插入点
stud->next=P->next
p->next=stud
……
}
插入结点——插在链表中间
5
4
head
P
6
9
NULL
1
stud
7.6 链表基本操作
void Ins(Student* head,
Student* stud)
{
……
首先定位到插入点
stud->next=P->next
p->next=stud
……
}
插入结点——插在链表中间
5
4
head
P
6
9
NULL
1
stud
7.6 链表基本操作
将表的指定结点删去。具体步骤：
找到指定位置p；
令p的前驱结点的next指向其后继结点；
释放p结点。
注意：
三种情况：
删除首结点
删除尾结点
删除中间结点
五、删除结点
7.6 链表基本操作
第一种：删除首结点
2
1
head
3
4
NULL
p
删除该结点
①
②
① head=P->next;
② delete P;
7.6 链表基本操作
第二种：删除尾结点P
2
1
head
3
4
NULL
p
删除该结点
①
②
① Q->next =NULL; 或
Q->next=P->next
② delete P;
NULL
Q
7.6 链表基本操作
第三种：删除中间结点P
2
1
head
3
4
NULL
Q
删除该结点
①
②
① Q->next=P->next;
② delete P;
p
综合练习
1. 编写函数实现单链表的倒置。
分析：
可以用二种方法：辅助指针或递归方法实现链表倒置。
如下图：
原表
倒置表
void Reverse (Student *head)
{
Student *P;
Student *Q;
Q= NULL;
while (head->next != NULL)
{
P = head->next;
head->next = Q;
Q = head;
head = P;
}
P->next=Q;
P=NULL; Q=NULL;
}
综合练习—链表倒置
2
1
head
Q
3
4
NULL
P
不为空
NULL
(1)辅助指针法
void Reverse (Student *head)
{
Student *P;
Student *Q;
Q= NULL;
while (head->next != NULL)
{
P = head->next;
head->next = Q;
Q = head;
head = P;
}
P->next=Q;
P=NULL; Q=NULL;
}
综合练习—链表倒置
(1)辅助指针法
2
1
head
Q
3
4
NULL
P
NULL
综合练习—链表倒置
void Reverse (Student *head)
{
Student *P;
Student *Q;
Q= NULL;
while (head->next != NULL)
{
P = head->next;
head->next = Q;
Q = head;
head = P;
}
P->next=Q;
P=NULL; Q=NULL;
}
(1)辅助指针法
2
1
head
Q
3
4
NULL
P
NULL
综合练习—链表倒置
void Reverse (Student *head)
{
Student *P;
Student *Q;
Q= NULL;
while (head->next != NULL)
{
P = head->next;
head->next = Q;
Q = head;
head = P;
}
P->next=Q;
P=NULL; Q=NULL;
}
(1)辅助指针法
2
1
head
Q
3
4
NULL
P
NULL
综合练习—链表倒置
void Reverse (Student *head)
{
Student *P;
Student *Q;
Q= NULL;
while (head->next != NULL)
{
P = head->next;
head->next = Q;
Q = head;
head = P;
}
P->next=Q;
P=NULL; Q=NULL;
}
(1)辅助指针法
2
1
head
Q
3
4
NULL
P
NULL
综合练习—链表倒置
void Reverse (Student *head)
{
Student *P;
Student *Q;
Q= NULL;
while (head->next != NULL)
{
P = head->next;
head->next = Q;
Q = head;
head = P;
}
P->next=Q;
P=NULL; Q=NULL;
}
(1)辅助指针法
2
1
head
Q
3
4
NULL
P
NULL
综合练习—链表倒置
void Reverse (Student *head)
{
Student *P;
Student *Q;
Q= NULL;
while (head->next != NULL)
{
P = head->next;
head->next = Q;
Q = head;
head = P;
}
P->next=Q;
P=NULL; Q=NULL;
}
(1)辅助指针法
2
1
head
Q
3
4
NULL
P
NULL
综合练习—链表倒置
void Reverse (Student *head)
{
Student *P;
Student *Q;
Q= NULL;
while (head->next != NULL)
{
P = head->next;
head->next = Q;
Q = head;
head = P;
}
P->next=Q;
P=NULL; Q=NULL;
}
(1)辅助指针法
2
1
head
Q
3
4
NULL
P
NULL
综合练习—链表倒置
void Reverse (Student *head)
{
Student *P;
Student *Q;
Q= NULL;
while (head->next != NULL)
{
P = head->next;
head->next = Q;
Q = head;
head = P;
}
P->next=Q;
P=NULL; Q=NULL;
}
(1)辅助指针法
2
1
head
Q
3
4
NULL
P
NULL
综合练习—链表倒置
void Reverse (Student *head)
{
Student *P;
Student *Q;
Q= NULL;
while (head->next != NULL)
{
P = head->next;
head->next = Q;
Q = head;
head = P;
}
P->next=Q;
P=NULL; Q=NULL;
}
(1)辅助指针法
2
1
head
Q
3
4
NULL
P
NULL
head->next为NULL，循环结束。
综合练习—链表倒置
void Reverse (Student *head)
{
Student *P;
Student *Q;
Q= NULL;
while (head->next != NULL)
{
P = head->next;
head->next = Q;
Q = head;
head = P;
}
P->next=Q;
P=NULL; Q=NULL;
}
(1)辅助指针法
2
1
head
Q
3
4
P
NULL
综合练习—链表倒置
void Reverse (Student *head)
{
Student *P;
Student *Q;
Q= NULL;
while (head->next != NULL)
{
P = head->next;
head->next = Q;
Q = head;
head = P;
}
P->next=Q;
P=NULL; Q=NULL;
}
(1)辅助指针法
2
1
head
Q
3
4
P
NULL
NULL
NULL
(2)递归法
Student* rev( Student * head )
{
Student *rHead;
if( !head )
return head;
else if( !head->next )
//只有一个结点
return head;
综合练习—链表倒置
else { rHead = rev( head->next ); head->next->next = head; head->next = NULL; return rHead; }
}
综合练习—链表排序
2. 建立10结点的单向链表，包括：学号、姓名、性别、年龄。按学号从小到大排序。
解：
struct Student
{
int code;
char name[20];
char sex;
unsigned age;
};
struct Node
{
Student* s;
Node* next;
};
学生信息结构体。
结点类型。
综合练习—链表排序
采用插入法进行排序：
void Insert(Node*& head, Node*& t)
{
if(!head || t->s->code < head->s->code)
{
t->next = head;
head = t;
return;
}
for(Node* p=head; p->next; p=p->next)
if(t->s->code < p->next->s->code)
break;
t->next = p->next;
p->next = t;
}
将 t 结点作为新的表头结点。
确定插入位置。
将 t 结点插在p结点之后。
综合练习—链表排序
void Display(const Node*& head)
{
cout <for(const Node* p=head; p; p=p->next)
cout <s->code
<s->name
<s->sex=='M' "male":"female")
<s->age <}
综合练习—链表排序
void main()
{
Student a[10] =
{
{8311001, "Smith", 'M', 18},
{8512901, "Kerry", 'F', 19},
{9022101, "Levy", 'M', 16},
{8508020, "Doris", 'F', 20},
{8881232, "Ella", 'F', 18},
{9123001, "Carrie", 'M', 22},
{8100825, "Barbara", 'F', 23},
{9012120, "Carmen", 'M', 20},
{8712001, "Brice", 'M', 19},
{8100923, "Auden", 'M', 20}
};
Node* first=NULL;
for(int i=0; i<10; i++)
{
Node* pN = new Node;
pN->s = &a[i];
Insert(first, pN);
}
Display(first);
}
综合练习—链表合并
3. 合并两个单向链表。
struct Lnode
{
double data;
Lnode* next;
};
void ShowList(const Lnode* const head)
{
for(Lnode* p=(Lnode*)head; p; p=p->next)
cout <data <<" ";
cout <}
综合练习—链表合并
void Insert(Lnode*& head, Lnode* p)
{
if(!head)
{
head = p;
p->next = NULL;
return;
}
if(head->data > p->data)
{
p->next = head;
head =p;
return;
}
Lnode* sp;
for(sp=head; sp->next&& sp->next->data < p->data; sp=sp->next);
p->next = sp->next;
sp->next = p;
}
综合练习—链表合并
Lnode* Merge(Lnode* h1, Lnode* h2)
{
Lnode* newHead = h1;
for(Lnode* p=h2; p; )
{
Lnode* t=p;
p=p->next;
Insert(newHead,t);
}
return newHead;
}
综合练习—链表合并
void AddToEnd(Lnode* pnew, Lnode*& head)
{
if(!head)
head=pnew;
else
{
Lnode* p;
for(p=head; p->next; p=p->next);
p->next = pnew;
}
pnew->next=NULL;
}
综合练习—链表合并
Lnode* GetNode()
{
Lnode* item = new Lnode;
if(item)
{
item->next=NULL;
item->data=0.0;
}
else
cout <<"Nothing allocated\n";
return item;
}
综合练习—链表合并
void main()
{
Lnode* head1=NULL;
Lnode* temp;
double d;
cout <<"data ";
cin >>d;
while(d>0&&(temp=GetNode()))
{
temp->data=d;
AddToEnd(temp, head1);
cout <<"data ";
cin >>d;
}
ShowList(head1);
Lnode* head2=NULL;
cout <<"data ";
cin >>d;
while(d>0&&(temp=GetNode()))
{
temp->data=d;
AddToEnd(temp, head2);
cout <<"data ";
cin >>d;
}
ShowList(head2);
Lnode*head=Merge(head1,head2);
ShowList(head);
}
本章小结
结构是自定义数据类型中的一种，它可将多种数据类型组合在一起使用，方便了程序对一些复杂数据的处理。在程序中，定义结构变量以前，必须先进行结构类型的定义。定义一个结构类型的变量，介绍了三种不同的方法。
访问结构数据的成员，可以用成员运算符有两个：“．”和“->”。如果是结构变量，用“．”运算符，如果是结构指针，用“->”运算符。
同样，结构型数据也能作为函数参数，且有值传递和引用传递两种。结构型数据，通常采取引用传递方式，这可以避免结构数据复制所带来的开销。结构也可定义为数组，结构数组的初始化与其它类型数组的初始化方法也类似。
在介绍了结构数据类型后，介绍了链表，链表综合了结构和指针的有关内容。初学者对链表的学习可能感到困难。但是，如果搞清楚了链表，有助于加深对指针、结构等内容的理解和掌握。