1、结构体与简单链表结构体与简单链表 C+C+程程序设计基础序设计基础教程教程第 5 章 要拼自己，不要拼爹；要追梦，不要追星；要做要拼自己，不要拼爹；要追梦，不要追星；要做“学霸学霸”，不要做，不要做“学渣学渣”。动态空间动态空间本章内容结构体结构体12第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-8简单链表简单链表3共用体共用体45.1 5.1 结构结构体体 结构体结构体是一种导出数据类型，它由若干个数据项组成，是一种导出数据类型，它由若干个数据项组成，每个数据项可以是基本数据类型，也可以是导出数据类每个数据项可以是基本数据类型，也可以是导出数据类型。型。2022-8-8第第
2、1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 3340301 YangKe 85.5 学号学号 姓名姓名 C+C+成绩成绩图图5-1学生基本信息学生基本信息 2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言5.1 5.1 结构结构体体5.1.1 结构体类型的定义结构体类型的定义定义一个结构体类型的一般形式为：定义一个结构体类型的一般形式为：struct 结构体名结构体名 成员表列成员表列；图图5-1学生基本信息可以定义成如下结构体类型。学生基本信息可以定义成如下结构体类型。struct Student int nu
3、m；char name20；float CPPscore；第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言5.1.2结构体类型的变量结构体类型的变量一一.结构体类型变量的说明结构体类型变量的说明 定义结构体类型的变量，有以下定义结构体类型的变量，有以下3 3种方法：种方法：1.1.先声明结构体类型再定义变量名先声明结构体类型再定义变量名例如：例如：Student student1,student2;Student student1,student2;第第5 5章章 结构体与简单链表结构体与简单链表 5.1 5.1 结构结
4、构体体2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-85.1.2结构体类型的变量结构体类型的变量2.在声明类型的同时定义变量在声明类型的同时定义变量例如：例如：struct Day int hour;int minute;int second;d1,d2;5.1 5.1 结构结构体体 2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-8 2022-8-85.1.2结构体类型的变量结构体类型的变量3.直接定义结构体类型变量
5、直接定义结构体类型变量 例如：例如：struct int num;float sex;s1,s2;5.1 5.1 结构结构体体 在定义了结构体类型的变量后，系统会为它分配内在定义了结构体类型的变量后，系统会为它分配内存单元。其所占存储空间的大小为各个成员所占内存单元。其所占存储空间的大小为各个成员所占内存单元之和。存单元之和。2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-82022-8-8 2022-8-85.1.2结构体类型的变量结构体类型的变量二、结构体类型变量的初始化二、结构体类型变量的初始化 结构
6、体变量是一个整体，要访问其数据成员，要用结构体变量是一个整体，要访问其数据成员，要用成员运算符成员运算符“”指定该成员属于哪个变量。指定该成员属于哪个变量。对结构体变量进行初始化，有以下三种方法：对结构体变量进行初始化，有以下三种方法：5.1 5.1 结构结构体体2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-8 2022-8-82022-8-8 2022-8-85.1.2结构体类型的变量结构体类型的变量1.1.在定义时进行初始化在定义时进行初始化struct Student int num；char na
7、me20；char sex；float CPPscore；sd1=40301,”YangKe”,M,89.5；5.1 5.1 结构结构体体第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-8 2022-8-82022-8-8 2022-8-85.1.2结构体类型的变量结构体类型的变量2.2.用对象流用对象流cincin进行初始化进行初始化cinsd1.numsd1.namesd1.sex;cinsd1.CPPscore;3.3.使用赋值语句进行初始化使用赋值语句进行初始化sd1.num=40301;sd1.name=”Yan
8、gKe”;/错误错误 sd1.sex=M；sd1.CPPscore=89.5;5.1 5.1 结构结构体体2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-8 2022-8-82022-8-8 2022-8-85.1.2结构体类型的变量结构体类型的变量3结构体变量的引用应遵循的规则结构体变量的引用应遵循的规则 1.不能将一个结构体变量作为一个整体进行输入输不能将一个结构体变量作为一个整体进行输入输出。出。例如：例如：cinsd1;/错误错误 2.允许将一个结构体变量直接赋值给另一个具有相允许将一个结构体变量直
9、接赋值给另一个具有相同类型的结构体变量。同类型的结构体变量。例如：例如：student sd2;sd2=sd1;5.1 5.1 结构结构体体第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-82022-8-8 2022-8-82022-8-8 2022-8-85.1.2结构体类型的变量结构体类型的变量若有定义：若有定义：struct int num;char sex;s1=40301,M;struct int num;char sex;s2；则则 s2=s1;/wrong，因为，因为s1,s2属于两个不同的结属于两个不同的结
10、构体类型的变量构体类型的变量5.1 5.1 结构结构体体第第2 2章章 C+C+语言编语言编程程基础基础第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-82022-8-8 2022-8-82022-8-8 2022-8-85.1.2结构体类型的变量结构体类型的变量5.1 5.1 结构结构体体3.3.对成员变量可以像普通变量一样进行各种运对成员变量可以像普通变量一样进行各种运算（依成员变量的类型而定）。算（依成员变量的类型而定）。例如：例如：char a20;strcpy(a,sd1.name);sd1.CPPscore+;
11、第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-82022-8-8 2022-8-82022-8-8 2022-8-85.1.2结构体类型的变量结构体类型的变量5.1 5.1 结构结构体体注意：注意：结构体成员可以是另一个结构体类型的变量。结构体成员可以是另一个结构体类型的变量。struct date int month;int day;int year;struct student int num;char name20;date birthday;student1；第第1 1章章 初识初识C+C+程程序设计语言序设计语
12、言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-82022-8-8 2022-8-82022-8-8 2022-8-85.1.2结构体类型的变量结构体类型的变量5.1 5.1 结构结构体体 如果某成员本身又是一个结构体类型，通过多级的分如果某成员本身又是一个结构体类型，通过多级的分量运算，对最低一级的成员进行引用。量运算，对最低一级的成员进行引用。格式为：结构体变量格式为：结构体变量.成员成员.子成员子成员.最低级子成员最低级子成员 student1.birthday.day=12;第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体
13、与简单链表 2022-8-82022-8-8 2022-8-82022-8-8 2022-8-85.1.2结构体类型的变量结构体类型的变量5.1 5.1 结构结构体体4指向结构体变量的指针指向结构体变量的指针 一个结构体变量的指针就是给该结构体变量所分配内一个结构体变量的指针就是给该结构体变量所分配内存段的起始地址。可以定义一个指针变量，用来指向一存段的起始地址。可以定义一个指针变量，用来指向一个结构体变量。此时该指针变量的值就是结构体变量的个结构体变量。此时该指针变量的值就是结构体变量的起始地址。起始地址。第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链
14、表结构体与简单链表 2022-8-82022-8-8 2022-8-82022-8-8 2022-8-85.1.2结构体类型的变量结构体类型的变量5.1 5.1 结构结构体体【例例5-1】指向结构体变量的指向结构体变量的指针变量的使用指针变量的使用#include“iostream”#include“string”using namespace std;int main()struct Stu int num;char name20;float score;Stu stu_1;Stu*p;p=&stu_1;stu_1.num=11401;strcpy(stu_1.name,”LiNing”);
15、stu_1.score=79.5;2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言 cout“NO:”stu_1.numtstu_1.name;couttstu_1.scoreendl;cout“NO:”(*p).numt(*p).namet;cout(*p).scoreendl;cout“NO:”numtnamet;coutscore成员名成员名第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-82022-8-8 2022-8-82022-8-8 2022-8-85.1.2结构体类型的变量结构体类型
16、的变量注意：注意：结构体的成员不能是自身的结构体变量，但可以是结构体的成员不能是自身的结构体变量，但可以是指向自身的结构体类型的指针变量。指向自身的结构体类型的指针变量。例如：例如：struct Node long int num;float score;Node*next;/next是指向是指向node的指针变量的指针变量Node m;/错误错误;5.1 5.1 结构结构体体第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-82022-8-8 2022-8-82022-8-8 2022-8-85.2.1 new运算符运算符
17、 如下数组的定义就是错误的。如下数组的定义就是错误的。int n;cinn;float an;通过通过new运算符动态申请空间。运算符运算符动态申请空间。运算符new的运算的运算结果是动态申请空间的首地址。可以定义一个指针变量结果是动态申请空间的首地址。可以定义一个指针变量来保存该地址。动态创建的变量本身没有名字，通过指来保存该地址。动态创建的变量本身没有名字，通过指针来间接操作。针来间接操作。5.2 5.2 动态空间动态空间第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-82022-8-8 2022-8-82022-8-
18、8 2022-8-85.2.1 new运算符运算符用用new运算符动态申请空间的格式有运算符动态申请空间的格式有3种：种：pointer=new type;/pointer是指针变量是指针变量 /type可以是整型、字符型和结构体类型等可以是整型、字符型和结构体类型等 pointer=new type(value);/type只能是基本数据类型只能是基本数据类型 /value为所分配内存空间的初始化值为所分配内存空间的初始化值 pointer=new type 表达式表达式 /动态申请数组空间动态申请数组空间 5.2 5.2 动态空间动态空间第第1 1章章 初识初识C+C+程程序设计语言序设计
19、语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-82022-8-8 2022-8-82022-8-8 2022-8-85.2.1 new运算符运算符例如：例如：char*p1,*p2,*p3;int*q1,*q2;p1=new char;p2=new char(a);p3=new char 10;q1=new int;q2=new int(123);5.2 5.2 动态空间动态空间第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-82022-8-8 2022-8-82022-8-8 2022-8-85.2
20、.1 new运算符运算符 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;/错误错误5.2 5.2 动态空间动态空间第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-82022-8-8 2022-8-82022-8-8 2022-8-85.2.2 delete运算符运算符 系统不会自动释放动态分配的内存空间，
21、因此在使用系统不会自动释放动态分配的内存空间，因此在使用完后应释放掉。完后应释放掉。如：如：char*p1,*p2,*p3;delete p1;/p1=new char;delete p2;/p2=new char 10;delete5*10p3;/p3=new char 5*10;delete s2;/s2=new node1;5.2 5.2 动态空间动态空间第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-82022-8-8 2022-8-82022-8-8 2022-8-8练习练习：（09秋）秋）基本概念题基本概念题:
22、程序中使用程序中使用new运算符动态分配的内存空间，必须运算符动态分配的内存空间，必须用用 来释放。来释放。5.2 5.2 动态空间动态空间5.2.2 delete运算符运算符第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-82022-8-8 2022-8-82022-8-8 2022-8-81.数组数组-顺序存储结构（在内存中按顺序存储结构（在内存中按先后顺序连续存放）先后顺序连续存放）例如：例如：int a6=2,4,6,8,10;5.3 5.3 简简单链单链表表5.3.1 链表的概念链表的概念272468100ppp
23、pppa0 a1 a2 a3 a4 a5用指针输出数组元素：用指针输出数组元素：for(int i=0,*p=a;i5;i+)coutnum=40301;p1-score=85.5;p1-next=&node2;p1-next=p2;2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.1 链表的概念链表的概念315.链表的表示链表的表示-（如下图所示）（如下图所示）4030185.5&4030278.5&403048304030380.5&headnumscorenext图图5-4 链
24、表的表示链表的表示2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.1 链表的概念链表的概念32建立链表所考虑的问题建立链表所考虑的问题?第一个结点怎样找第一个结点怎样找?如何从前一个结点找到下一个结点如何从前一个结点找到下一个结点 最后一个结点的指针项应放怎样的地址？最后一个结点的指针项应放怎样的地址？2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.1 链表的概念链表的
25、概念1.链表的头指针链表的头指针 链表的操作总是从链表的操作总是从第一个结点第一个结点（首结点首结点）逐个结点）逐个结点往后进往后进 行的。通常用行的。通常用指针变量指针变量（head）存放首结点地）存放首结点地址（址（首地址首地址）。）。node*p=new node;node*head=0;p-num=40301;p-score=85.5;2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.1 链表的概念链表的概念34 2.链表的前驱结点和后继结点链表的前驱结点和后继结点 当前结点
26、的前一个结点称为当前结点的前一个结点称为前驱结点前驱结点，后一个结点称，后一个结点称为为后继结点后继结点。如图。如图5-5所示。所示。正在操作的结点称为正在操作的结点称为当前结点。当前结点。head=p;第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.1 链表的概念链表的概念4030185.5&4030278.5&403048304030380.5&numscorenextp1pp2p1pp2head图图5-5 链表的前驱结点和后继结点链表的前驱结点和后继结点2022-8-8第第1 1章章 初识初
27、识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.1 链表的概念链表的概念 p指向的结点为当前结点，指向的结点为当前结点，p1指向指向p的前驱结点，的前驱结点，p2指向指向p的后继结点。的后继结点。p1-next=p；p-next=p2；p1-next-next=p2；第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.1 链表的概念链表的概念3.3.链表的尾结点链表的尾结点 链表的链表的最后一个结点最后一个结点（尾结点尾结点）
28、的指针项）的指针项（nextnext）中保存的值为）中保存的值为0 0（NULLNULL），表示链表到此结），表示链表到此结束。束。p2-next=0;2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.2链表的基本操作链表的基本操作1.1.结点的基本操作结点的基本操作 （1 1）定义结构体，表示结点的数据类型）定义结构体，表示结点的数据类型 struct Node long int num;float score;Node*next;2022-8-8第第1 1章章 初识初识C+C+程
29、程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.2链表的基本操作链表的基本操作（2 2）用）用newnew申请动态空间，并定义指针变量指向该空申请动态空间，并定义指针变量指向该空间间 Node*p=new Node;（3）通过指针变量给结点赋值）通过指针变量给结点赋值 int id;cinid;p-num=id;cinp-score;coutnumtscore;第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-8 5.3 5.3 简简单链单链表表5.3.2链表的
30、基本操作链表的基本操作（4 4）释放结点空间）释放结点空间 delete p;2.操作链表的基本语句操作链表的基本语句（1）遍历链表）遍历链表 for(node*p=head;p-next!=0;p=p-next);/p指向尾结点指向尾结点2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.2链表的基本操作链表的基本操作41 （2 2）查找具有指定值的结点（例如学号为）查找具有指定值的结点（例如学号为 num num）遍历时，保持遍历时，保持p1p1指向指向p2p2的前驱结点的前驱结点
31、:p1=p2;p2=p2-nextp1=p2;p2=p2-next；循环条件循环条件 可合并：可合并：while(while(p2-num!=nump2-num!=num&p2-next!=NULLp2-next!=NULL)以指针以指针p2p2遍历链表，至遍历链表，至链尾链尾（循环条件（循环条件p2-next!=0p2-next!=0）；）；遍历过程中，若找到结点（遍历过程中，若找到结点（p2-num=nump2-num=num），），查找结束（循环终止）；查找结束（循环终止）；2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简
32、单链表 5.3 5.3 简简单链单链表表5.3.2链表的基本操作链表的基本操作（3 3）删除具有指定值的结点（例如学号）删除具有指定值的结点（例如学号为为 num）链表是链表是空表空表（无结点可删）（无结点可删）head=NULL 要删除的是要删除的是第一个结点第一个结点（p2p2指向要删的结点）指向要删的结点）p2=head;head=head-next;delete p2;要删除的是要删除的是中间结点中间结点p1-next=p2-next;delete p2;p1-next=p第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3
33、5.3 简简单链单链表表5.3.2链表的基本操作链表的基本操作43numscorenext4030185.5&4030278.5&403048304030380.5&headp1p2p2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.2链表的基本操作链表的基本操作 要删除的是链表的尾结点要删除的是链表的尾结点p1-next=0;delete p2;链表中找不到要删除的结点链表中找不到要删除的结点2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结
34、构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.2链表的基本操作链表的基本操作45（4 4）在有序链表中插入一个结点（）在有序链表中插入一个结点（p p指向插入的结点）指向插入的结点）链表是空表，则插入的结点做首结点链表是空表，则插入的结点做首结点(head=0）p-next=0；head=p；链表不是空表，要插入的结点做首结点链表不是空表，要插入的结点做首结点 p-next=head；head=p；2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.2链表的基
35、本操作链表的基本操作4030185.5p14030278.5p2403048304030380.5&p1numscorenextheadp2 在两结点之间，正常插入结点（在在两结点之间，正常插入结点（在p1p1、p2p2之间插入之间插入p p）4030595.5pp1-next=p;p-next=p2;或或 p-next=p1-next;p1-next=p;2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.2链表的基本操作链表的基本操作47 要插入的结点做链表的尾结点要插入的结点做链
36、表的尾结点p2-next=p;p-next=0；2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.3 链表的应用链表的应用 48 链表的应用包括链表的建立与输出、链表结点空间链表的应用包括链表的建立与输出、链表结点空间 的释放、在链表中删除具有指定值的结点以及插入一个的释放、在链表中删除具有指定值的结点以及插入一个 结点等。结点等。1.1.建立一条无序链表建立一条无序链表 链表创建的基本思路是：链表创建的基本思路是：第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章
37、章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.3 链表的应用链表的应用 （1 1）定义并输入学号；）定义并输入学号；numscorenext4030185.5head4030278.5ppendppp4030380.540304830&（2 2）分配动态结点空间）分配动态结点空间p p，并对学号赋值、输入成绩；，并对学号赋值、输入成绩；（3 3）若）若p p是首结点，指针是首结点，指针headhead和和pendpend都指向该结点；否则，都指向该结点；否则，把把p p链接到链接到pendpend的的 后面，并把后面，并把p p作为当前尾结点；作为当前尾结点；p
38、endpppendppendp-next=0;/pend-next=0;2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.3 链表的应用链表的应用 50int id;cinid;p=new Node;p-num=id;cinp-score;if(head=0)head=p;pend=p;else （4）重新输入学号；）重新输入学号；cinid;（5）只要学号不为）只要学号不为0，就重复（，就重复（2）（4）步骤（循环）步骤（循环)；while(id!=0)pend-next=p;pe
39、nd=p;（6）循环结束（结点全部产生）后，给尾结点加上结束标记。）循环结束（结点全部产生）后，给尾结点加上结束标记。2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.3 链表的应用链表的应用 Node*create()Node*head=0,*p,*pend;int id;cinid;while(id!=0)p=new Node;/p指向新建立的结点指向新建立的结点 p-num=id;cinp-score;if(head=0)head=p;pend=p;else pend-next
40、=p;pend=p;/pend指向指向p的前驱结点的前驱结点 cinid;p-next=0;链表建立的函数如下：链表建立的函数如下：return head;第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.3 链表的应用链表的应用 2.输出链表输出链表（1）用头指针）用头指针head遍历链表遍历链表（2）遍历过程中输出）遍历过程中输出head所指向的数据项所指向的数据项（3）定义输出函数）定义输出函数head=NULLcoutnum;coutscore;head=head-next;第第1 1章章
41、初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表53numscore next4030185.5&4030278.5&403048304030380.5&void print(Node*head)；headheadheadhead5.3.3 链表的应用链表的应用 第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.3 链表的应用链表的应用 void print(Node*head)while(head!=NULL)coutnum
42、t;coutscore;head=head-next;coutn;第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.3 链表的应用链表的应用 3.释放链表释放链表 建立的链表是动态链表，组成链表的每个结点的建立的链表是动态链表，组成链表的每个结点的内存单元都是通过内存单元都是通过new运算符动态申请空间的。因此运算符动态申请空间的。因此在对链表操作完毕后，动态申请的空间要释放掉，以在对链表操作完毕后，动态申请的空间要释放掉，以便于对内存进行有效的管理。便于对内存进行有效的管理。2022-8-8第第1
43、 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.3 链表的应用链表的应用 void release(Node*head)if(head=0)coutnext;delete p;cout结点空间释放完毕结点空间释放完毕!;2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.3 链表的应用链表的应用 主函数的编写主函数的编写:#include using namespace std;struct N
44、ode long int num;float score;Node*next;void main()Node*create();/建立单向链表建立单向链表 void print(Node*head);/输出链表上各个结点的值输出链表上各个结点的值 void release(Node*head);/释放链表的结点空释放链表的结点空间间 Node*head;head=create();print(head);release(head);return 0;2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链
45、单链表表5.3.3 链表的应用链表的应用 4.4.对链表的删除操作对链表的删除操作 删除链表中具有指定值的一个结点时有以下几种情况：删除链表中具有指定值的一个结点时有以下几种情况：链表是空表（无结点）；链表是空表（无结点）；要删的是第一个结点；要删的是第一个结点；要删的是中间的一个结点；要删的是中间的一个结点；要删的是最后一个结点要删的是最后一个结点 链表中找不到要删除的结点。链表中找不到要删除的结点。第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.3 链表的应用链表的应用 编写函数，删除链表上具
46、有指定值的一个结点。编写函数，删除链表上具有指定值的一个结点。Node*Delete_one_Node(Node*head,int data)Node*p1,*p2;if(head=NULL)/第种情况第种情况coutnum=data)/第种情况第种情况 p2=head;head=head-next;delete p2;2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.3 5.3 简简单链单链表表5.3.3 链表的应用链表的应用 else p2=p1=head;while(p2-num!=data&p2-next!=N
47、ULL)/查找要删除的结点查找要删除的结点 p1=p2;p2=p2-next;if(p2-num=data)p1-next=p2-next;delete p2;/第种情况第种情况else coutnext=0;return head;if(head-num=p-num)/第种情况第种情况 p-next=head;head=p;return head;2022-8-8 5.3 5.3 简简单链单链表表5.3.3 链表的应用链表的应用 p2=p1=head;while(p2-next&p2-numnum)p1=p2;p2=p2-next;/p1指向指向p2的前驱的前驱if(p2-numnum)/第
48、种情况第种情况p2-next=p;p-next=0;else /第种情况第种情况p-next=p2;p1-next=p;return head;第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 2022-8-8 5.4 5.4 共共用体用体 第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 共用体共用体是一种构造数据类型，是一种构造数据类型，它是使几种它是使几种不同类型的变量存放到同一个地址开始的内存不同类型的变量存放到同一个地址开始的内存单元中。单元中。具有这种存储特性的变量称为具
49、有这种存储特性的变量称为共用体类型共用体类型的变量的变量。2022-8-8 2022-8-8 5.4.1共用体类型共用体类型第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.4 5.4 共共用体用体 定义一个共用体类型的一般形式为：定义一个共用体类型的一般形式为：union 共用体类型名共用体类型名 成员表列成员表列；如：如：union SS int num；char name20；float CPPscore；2022-8-8 2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结
50、构体与简单链表 5.4.2共用体类型变量的定义共用体类型变量的定义 5.4 5.4 共共用体用体 一一.变量定义变量定义 定义共用体类型的变量，有以下定义共用体类型的变量，有以下3 3种方法：种方法：1.1.先声明共用体类型再定义变量名先声明共用体类型再定义变量名 例如：例如：SS s1,s2;2022-8-8 2022-8-8第第1 1章章 初识初识C+C+程程序设计语言序设计语言第第5 5章章 结构体与简单链表结构体与简单链表 5.4.2共用体类型变量的定义共用体类型变量的定义 5.4 5.4 共共用体用体 2.在声明类型的同时定义变量在声明类型的同时定义变量例如：例如：union Day
