《数据结构教程(简答易懂)第三章》由会员分享，可在线阅读，更多相关《数据结构教程(简答易懂)第三章（36页珍藏版）》请在金锄头文库上搜索。
1、2018/9/20,1,第三章 线性链表,2018/9/20,2,3.1 线性链表的基本概念,2018/9/20,3,3.1.1 线性表顺序存储的问题,顺序表的问题？,线性表的链式存储： 不要求逻辑上相邻的数据元素在物理位置上也相邻。,2018/9/20,4,线性表的顺序存储结构存在以上这些缺点，因此，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而是采用下面将要介绍的链式存储结构。,2018/9/20,5,3.1.2 线性链表的存储结构,为了存储变形表中的每一个元素，一方面要存储数据元素的值，另一方面要存储个数据元素之间的前后件关系；故将存储空间中的每一个存储结点分为两部
2、分：一部分用语存储数据元素的值，称为数据域，另一部分用于存放下一个数据元素的存储序号，即指向后件结点，称为指针域。,2018/9/20,6,数据域,指针域,2018/9/20,7,逻辑结构,物理结构,见图示,2018/9/20,8,在C+中，可以使用结构体类型定义结点类型：,struct 结构体类型名 数据成员表；结构体类型名 *指针变量名； ；,2018/9/20,9,#include using namespace std; struct node int d;node *next; ; int main() node *p;p=new node;delete p;return 0; ,2
3、018/9/20,10,对某线性链表，要求从头指针开始，沿各结点的指针扫描并输出链表中的所有结点：,#include using namespace std; struct node int d;node *next; ;,2018/9/20,11,void prtll(node *head) node *p;p=head;while(p!=NULL) coutdnext; ,2018/9/20,12,编程：建立一个线性链表，其元素值依次为从键盘输入的正整数(以输入一个非正整数为结束)，然后依次输出线性链表中各结点的元素值，并删除各结点。,2018/9/20,13,#include using
4、 namespace std;struct node /定义结点类型 int d;node *next;int main() int x;node *head, *p, *q;head=NULL; /置链表空q=NULL;cin x; /输入一个正整数while(x0) /若输入值大于0 p=new node; /申请一个结点p-d=x; /置当前结点的数据域为输入的正整数xp-next=NULL; /置当前结点的指针域为空if (head=NULL) head=p; /若链表为空，则将头指针指向当前结点pelse q-next=p; /将当前结点链接在最后q=p; /置当前结点为链表最后一个
5、结点cin x;p=head;while(p!=NULL) /从链表的第一个结点开始，输出各结点的元素值，并删除 cout d next; /删除当前结点delete q; /释放删除的结点空间return 0;,2018/9/20,14,3.1.3 线性链表类,2018/9/20,15,结点类型声明,template struct node T d; / 数据域 node *next; / 指针域 ;,2018/9/20,16,链表类的基本操作 创建空链表 检测链表状态 插入链头元素 在链表包含元素x的结点之前插入新元素b 删除链头元素 删除包含元素x的结点元素 从头指针开始扫描输出链表中的
6、元素 逆转链表 计算链表长度 ,2018/9/20,17,#include using namespace std; template struct node T d;node *next; ;,2018/9/20,18,template class linked_LList private:node *head;public:linked_LList();int flag_linked_LList();void prt_linked_LList();void ins_linked_LList(T);void ins_linked_LList(T,T);T del_linked_LList()
7、;int del_linked_LList(T);int lencst();,2018/9/20,19,插入链头元素算法（ ins_linked_LList(T); ）,2018/9/20,20,删除链头元素算法（ del_linked_LList()；）,2018/9/20,21,算法：在含x的结点前插入含b的新结点,有下列几种情况： 1、当此时链表为空时： 2、当含x的结点是第一个结点时： 3、当含x的结点非第一个结点时： 4、当此链表中没有含x的结点时：,2018/9/20,22,算法：在含x的结点前插入含b的新结点,1、 if (head=NULL) 2、 if (head-d=x)3
8、、else,head,NULL,=,p,b,N,head,p,head,head,q = head,q = q-next,p,2018/9/20,23,在含x的结点前插入含b的新结点,void linked_LList:ins_linked_LList(T x, T b) node *p, *q;p=new node; p-d=b; if (head=NULL) head=p; p-next=NULL; return; / 1if (head-d=x) p-next=head; head=p; return; / 2q=head; / 3while (q-next!=NULL) ,2018/9
9、/20,24,算法：删除包含x的结点,有下列几种情况： 1、当链表为空时： 2、当含x的结点是第一个结点时： 3、当含x的结点非第一个结点时： 4、当此链表中没有含x的结点时：,2018/9/20,25,1、 2、if (head-d) = x)3、else,算法：删除包含x的结点,head,if ( head = = NULL),返回 0 标志,head,x,p,q = head,q = q-next,x,p,N,先查找含x的结点，再删除它。,2018/9/20,26,算法：删除包含x的结点,int linked_LList:del_linked_LList(T x) node *p, *q
10、;if (head=NULL) return 0; if (head-d) = x) p=head-next; delete head; head=p; return 1; q=head;while (q-next!=NULL) ,2018/9/20,27,线性链表类的实现,请综合教材 62页的文件linked_List.h 72页的文件linked_Llist.h 合并一个完整的线性链表类,2018/9/20,28,template class linked_LList private:node *head;public:linked_LList();int flag_linked_LLis
11、t();void prt_linked_LList();void ins_linked_LList(T);void ins_linked_LList(T,T);T del_linked_LList();int del_linked_LList(T);int lencst();,2018/9/20,29,template int linked_LList:lencst() ,2018/9/20,30,例 建立一个空线性链表。依次做下列操作： 第1次扫描输出链表s中的元素 在包含元素10的结点前插入新元素10 在包含元素10的结点前插入新元素20 在包含元素10的结点前插入新元素30 在包含元素4
12、0的结点前插入新元素40 在线性链表的链头插入元素9 在线性链表的链头插入元素8 第2次扫描并输出该链表 在线性链表中删除元素30 删除链头元素 在线性链表中删除元素50 第3次扫描并输出该链表,2018/9/20,31,#include “linked_Listzx.h“int main() linked_LList s;cout “第1次扫描输出链表s中的元素:“ endl;s.prt_linked_LList(); s.ins_linked_LList(10,10); /在包含元素10的结点前插入新元素10s.ins_linked_LList(10,20); /在包含元素10的结点前插入
13、新元素20s.ins_linked_LList(10,30); /在包含元素10的结点前插入新元素30s.ins_linked_LList(40,40); /在包含元素40的结点前插入新元素40s.ins_linked_LList(9);s.ins_linked_LList(8);cout “第2次扫描输出链表s中的元素:“ endl;s.prt_linked_LList();cout“单链表长度=“s.lencst()endl;if (s.del_linked_LList(30) cout “删除元素:30“ endl;elsecout “链表中无元素:30“ endl;cout“单链表长度
14、=“s.lencst()endl;if (s.flag_linked_LList()cout“删除的链头元素:“ s.del_linked_LList()endl;cout“单链表长度=“s.lencst()endl;if (s.del_linked_LList(50)cout “删除元素:50“ endl;elsecout “链表中无元素:50“ endl;cout “第3次扫描输出链表s中的元素:“ endl;s.prt_linked_LList(); cout“单链表长度=“s.lencst()endl;return 0;,2018/9/20,32,单链表特点,可通过指针顺序访问链上所有结点（遍历） 各结点所占用的存储空间不一定连续 链表中结点的逻辑顺序与其存储空间的位置无关 结点的指针值只反映结点之间的前后件关系,2018/9/20,33,如何在单链表中寻找它的前件呢？,必须从头指针开始重新寻找！,如何改进？,2018/9/20,34,双向链表,上述链表是单向链表，存在以下问题无法进行反向查找 双向链表逻辑结构,2018/9/20,35,小 结,线性链表类的实现： 重点：插入与删除,2018/9/20,36,作业： P88 第4题,
