《链表与链表的基本操作.ppt》由会员分享，可在线阅读，更多相关《链表与链表的基本操作.ppt（26页珍藏版）》请在三一办公上搜索。
1、7.2 链表与链表的基本操作,线性表是最简单，最常用的一种数据结构。线性表的逻辑结构是n个数据元素的有限序列（a1,a2,an）。而线性表的物理结构包括：顺序表(数组)，链表。,7.2.1 单链表基本算法,7.2.3 双向链表(选读),7.2.1 单链表基本算法,单链表（Singly Linked list）：有若干结点（Node）组成。一个结点包含info和link两个域，info域存放数据，类型由应用决定；link存放指向该链表中下一个结点的地址。,结点定义如下：typedef int DataType;/数据为整型struct Node DataType info;Node*link;,
2、在C/C+中允许一个类型（结构体或类）的数据成员是自身的指针类型，但决不能是自身类型，这会导致一个无穷递归的定义。,7.2.1 单链表基本算法,通常使用表头指针head指向单链表的第一个结点，head在使用中千万不可丢失，否则链表整个丢失，内存也发生泄漏。,infon-1,info2,info1,info0,head,图7.3 单链表结构,单链表的插入与删除：只要改变链中结点指针的值，无需移动表中的结点，就能实现插入和删除操作。若考虑在链表中包含数据info的结点之前插入一个新元素，则有三种情况：info位于第一个结点；位于中间某个结点；没找到info。,7.2.1 单链表基本算法,infox
3、,info0,info1,head,插在链首：首先新结点的link指针指向info0所在结点，然后，head指向新结点。即：newnode-link=head；head=newnode；/注意：链表操作次序非常重要,newnode,注意：访问符“.”与“-”的区别。p-link:p为结点指针；n.link:n为结点;p-link等价于(*p).link。,7.2.1 单链表基本算法,infox,infoi-1,infoi,newnode,插在中间：结点型指针q为指向infoi-1的工作指针，则：newnode-link=q-link；q-link=newnode；,7.2.1 单链表基本算法,
4、infox,newnode,p,infon-1,插在队尾：只要工作指针p找到队尾，即可链在其后：p-link=newnode；newnode-link=NULL;,7.2.1 单链表基本算法,带表头结构的链表：通过给每一个链表加上一个表头结点，可以提高结点插入操作的通用性。,空表如下：,head,下面将介绍带表头结构的链表的各种基本算法。,tail,head,7.2.1 单链表基本算法,tail,p,info1,tail,p,tail,1.建立链表头节点Node*CreatHead()Node*head,*tail;head=new Node;/建立链表头 tail=head;head-lin
5、k=NULL;return head;2.链表向后生长一个结点Node*GrowDN(Node*tail,DataType data)Node*p=new Node;/建立结点 p-info=data;tail-link=p;tail=p;tail-link=NULL;return tail;,head,tail,info0,head,7.2.1 单链表基本算法,head,info0,P,P,info1,3.链表向前生长一结点void GrowUP(Node*head,DataType data)Node*p=new node;p-info=data;p-link=head-link;/新结点
6、放在原链表前方 head-link=p;/头结点放新结点之前,7.2.1 单链表基本算法,4.链表遍历查找(按关键字)Node*TravFind(Node*head,DataType key)Node*p=head-link;while(p!=NULL,7.2.1 单链表基本算法,6.删除结点p后的结点void RemoveAfter(Node*p)Node*q;q=p-link;if(q!=NULL)p-link=q-link;delete q;q=NULL;/如果该结点还要用，则不要释放，将q返回7.删除指定结点pvoid RemoveCur(Node*head,Node*p)Node*q
7、=head;while(q-link!=NULL/删除q后面的结点p,7.2.1 单链表基本算法,8.清空单链表,保留表头结点void MakeEmpty(Node*head)Node*p;while(head-link!=NULL)/未到尾节点p=head-link;head-link=p-link;/头结点后第一个结点从链中脱落delete p;p=NULL;/删除脱离下来的结点,7.2.2 单链表类设计,不同于【例7.5_h】的单链表类定义结点类：typedef int DataType;class Node DataType info;/数据域 Node*link;/指针域public
8、:Node();/生成空结点的构造函数 Node(const Datatype,例7.5_h 结点类,Node:Node()link=NULL;Node:Node(const DataType,定义链表类:class SLList Node*head,*tail;/链表头指针和尾指针public:SLList();/构造函数，生成头结点(空链表)SLList();/析构函数 void MakeEmpty();/清空链表，只余表头结点 Node*TravFind(DataType);/搜索数据域与data相同的结点，返回该结点的地址 void PrintSLL();/打印链表的数据域 void
9、GrowUP(const DataType,7.2.2 单链表类,例7.5_h 单链表类,链表类成员函数：SLList:SLList()head=tail=new Node();SLList:SLList()MakeEmpty();delete head;head=NULL;void SLList:MakeEmpty()/清空链表 Node*p;while(head-link!=NULL)/把头结点后的第一个结点从链中脱离 p=head-link;head-link=p-link;delete p;p=NULL;/删除(释放)脱离下来的结点 tail=head;/表头指针与表尾指针均指向表头结
10、点，表示空链,例7.5_h 单链表类,链表类成员函数：Node*SLList:TravFind(DataType key)Node*p=head-link;while(p!=NULL,例7.5_h 单链表类,链表类成员函数：void SLList:GrowUP(const DataType,链表类成员函数：void SLList:RemoveAfter(Node*p)Node*q;q=p-link;if(q!=NULL)p-link=q-link;delete q;q=NULL;,例7.5_h 单链表类,void SLList:RemoveCur(Node*p)Node*q=head;whil
11、e(q-link!=NULL/删除q后面的结点p,例7.5_h 主函数,void int main()SLList L1;Node n,*tmp;for(int j=0;j10;j+)L1.GrowDN(j);/向后生成链表cout初始链表:;L1.PrintSLL();/打印表L1.GrowUP(20);/向前插入到头结点后cout插入结点后的链表:;L1.PrintSLL();/打印tmp=L1.TravFind(20);/查找插入的结点n=*tmp;cout找到结点的信息域:;n.PrintNode();L1.RemoveCur(tmp);/删除插入的结点cout删除结点后的链表:;L1
12、.PrintSLL();/打印return 0;,结果：,7.2.2 单链表类,讨论复制构造函数：P239说法有待改进！如下：本例中没有给出Node类的复制构造函数的根本原因在于：对Node类复制的结果只是一个孤立结点：Node:Node(Node（1）不涉及动态内存分配，不存在深复制和浅复制的问题（参见Node的构造函数），无需自定义复制构造函数和复制赋值运算符。（2）Node和SLList类的所有函数的参数和返回值仅使用指向Node的指针，因此无需自定义的复制构造函数；（3）若程序中确实需要通过复制建立Node对象，完全可由系统默认的复制构造函数和复制赋值运算符实现复制（按成员）。,7.2
13、.2 单链表类,讨论复制构造函数：单链表是通过动态内存分配建立的，因此链表的复制就涉及了深复制与浅复制问题，必须自定义复制构造函数和复制赋值运算符。对象深复制过程：（1）复制对象主体，即数据成员（除了指向动态内存的指针）；数据成员只有指向动态内存的指针head，tail,此步不需要！（2）为当前对象分配独立的自由存储区空间；分配一个完整的链表所占据的自由存储区空间！（3）将被复制对象的自由存储区目标内容按位复制给当前对象；将被复制链表中所有的信息域逐位复制给当前链表！,7.2.2 单链表类,讨论复制构造函数：/拷贝构造函数SLList:SLList(SLList,7.2.2 单链表类,讨论复制构造函数：/拷贝赋值运算符SLList,7.3 栈与队列的基本操作及其应用,栈和队都是特殊的线性表，限制存取位置的线性结构，可以由顺序表实现，也可以由链表实现。,7.3.1 栈,7.3.3队列,7.3.2 栈的应用（选读）,
