链表与链表的基本操作ppt课件.ppt

7.2 链表与链表的根本操作链表与链表的根本操作 线性表是最性表是最简单，最常用的一种数据构，最常用的一种数据构造线性表的性表的逻辑构造是构造是n n个数据元素的有个数据元素的有限序列〔限序列〔a1,a2,…,ana1,a2,…,an〕而线性表的物理性表的物理构造包括：构造包括：顺序表序表( (数数组) )，，链表表 7.2.1 单链表根本算法单链表根本算法 7.2.3 双向链表双向链表(选读选读)7.2.1 单链表根本算法单链表根本算法单链表〔单链表〔Singly Linked list〕：〕： 有有假假设设干干结结点点〔〔Node〕〕组组成成一一个个结结点点包包含含info和和link两两个个域域，，info域域存存放放数数据据，，类类型型由由运运用用决决议议；；link存存放放指指向向该该链链表表中中下下一一个个结结点的地址点的地址结点定点定义如下：如下： typedef int DataType; //typedef int DataType; //数据数据为整型整型struct Nodestruct Node{ { DataType info; DataType info; Node *link; Node *link;};};在在C/C++中允中允许一个一个类型〔构造体或型〔构造体或类〕的数据成〕的数据成员是本身是本身的指的指针类型，但决不能是本身型，但决不能是本身类型，型，这会会导致一个无致一个无穷递归的定的定义。

 7.2.1 单链表根本算法单链表根本算法　通常运用表　通常运用表头指指针head指向指向单链表的第一个表的第一个结点，点，head在运在运用中千万不可用中千万不可丧失，否那么失，否那么链表整个表整个丧失，内存也失，内存也发生走漏infon-1 ^info2 info1 info0 ……head图图7.3 单链表构造单链表构造 单链表的插入与表的插入与删除：除： 只需改只需改动链中中结点指点指针的的值，无需挪，无需挪动表中的表中的结点，就能点，就能实现插入和插入和删除操作　　假　　假设思索在思索在链表中包含数据表中包含数据info的的结点之前插点之前插入一个新元素，那么有三种情况：入一个新元素，那么有三种情况：info位于第一个位于第一个结点；位于中点；位于中间某个某个结点；没找到点；没找到info 7.2.1 单链表根本算法单链表根本算法infoxinfo0info1headhead插在链首：插在链首： 首首先先新新结结点点的的link指指针针指指向向info0所所在在结结点点，，然然后后，，head指向新结点即：指向新结点即：newnode->link=head；；head=newnode；； //留意：链表操作次序非常重要留意：链表操作次序非常重要newnodenewnodehead留意：访问符留意：访问符“.〞与〞与“->〞的〞的区别。

区别p->link: p为结点指针；为结点指针；n: n为结点为结点;p->link等价于等价于(*p)7.2.1 单链表根本算法单链表根本算法infoxinfoi-1infoiｑｑnewnodenewnode插在中间：插在中间： 结点型指针结点型指针q为指向为指向infoi-1的任务指针，那么：的任务指针，那么：newnode->link=q->link；；q->link=newnode；；7.2.1 单链表根本算法单链表根本算法infox infox newnodenewnodep^infon-1 infon-1 ^ ^插在队尾：插在队尾：只需任务指针只需任务指针p找到队尾，即可链在其后：找到队尾，即可链在其后：p->link=newnode；；newnode->link=NULL;7.2.1 单链表根本算法单链表根本算法带表头构造的链表：带表头构造的链表：经经过过给给每每一一个个链链表表加加上上一一个个表表头头结结点点，，可可以以提提高高结点插入操作的通用性结点插入操作的通用性空表如下：空表如下：headinfo0Infon-1^info1…head^ 下面将引见带表头构造的链表的各种根本算法。

tailhead7.2.1 单链表根本算法单链表根本算法tailpinfo1tailptail^1.1.建立链表头节点建立链表头节点Node* CreatHead(){Node* CreatHead(){ Node *head,*tail; Node *head,*tail; head=new head=new Node; Node; ////建建立立链链表表头头 tail=head; tail=head; head->link=NULL; head->link=NULL; return head; return head;} }2.2.链表向后生长一个结点链表向后生长一个结点Node*GrowDN(Node*tail,DataType Node*GrowDN(Node*tail,DataType data){data){ Node* Node* p=new p=new Node; Node; ////建建立立结结点点 p->info=data; p->info=data; tail->link=p; tail->link=p; tail=p; tail=p; tail->link=NULL; tail->link=NULL; return tail;} return tail;}headtail^^^info0head7.2.1 单链表根本算法单链表根本算法head^info0 P^Pinfo13.3.链表向前生长一结点链表向前生长一结点void void GrowUP(Node*head,DataType GrowUP(Node*head,DataType data){ data){ Node* p=new node; Node* p=new node; p->info=data; p->info=data; p->link= head->link ; p->link= head->link ; // //新结点放在原链表前方新结点放在原链表前方 head->link=p; head->link=p; // //头结点放新结点之前头结点放新结点之前 } }7.2.1 单链表根本算法单链表根本算法4. 4. 链表遍表遍历查找找( (按关按关键字字) )Node*TravFind(Node*head, DataType key){Node*TravFind(Node*head, DataType key){Node *p=head->link;Node *p=head->link;while(p!=NULL&&p->info!=key)p=p->link; while(p!=NULL&&p->info!=key)p=p->link; ////挪挪动p preturn p;return p;} } ////前前往往指指针p p，，指指向向找找到到的的结点点，，或或者者未未找找到到，，前前往往NULLNULL5. 5. 链表表节点点p p后插入新后插入新节点：点：留意与向前向后生留意与向前向后生长算法的区算法的区别！！void InsertAfter(Node*p, DataType x){void InsertAfter(Node*p, DataType x){Node *q=new Node;Node *q=new Node;q->info=x;q->info=x;q->link=p->link;q->link=p->link;p->link=q;p->link=q;} }7.2.1 单链表根本算法单链表根本算法6. 6. 删除结点删除结点p p后的结点后的结点void RemoveAfter(Node*p){void RemoveAfter(Node*p){ Node*q; Node*q; q=p->link; q=p->link; if(q!=NULL){ if(q!=NULL){ p->link=q->link; p->link=q->link; delete q; q=NULL;} delete q; q=NULL;}}//}//假设该结点还要用，那么不要释放，将假设该结点还要用，那么不要释放，将q q前往前往7. 7. 删除指定结点删除指定结点p pvoid RemoveCur(Node*head, Node*p){void RemoveCur(Node*head, Node*p){ Node*q=head; Node*q=head; while(q->link!=NULL while(q->link!=NULL && && q->link!=p) q->link!=p) q=q->link;q=q->link; // //遍历查找遍历查找 RemoveAfter(q);// RemoveAfter(q);//删除删除q q后面的结点后面的结点p p} }7.2.1 单链表根本算法单链表根本算法8.8.清空单链表清空单链表, ,保管表头结点保管表头结点void MakeEmpty(Node* head){void MakeEmpty(Node* head){Node*p;Node*p;while(head->link!=NULL){//while(head->link!=NULL){//未到尾节点未到尾节点p=head->link;p=head->link;head->link=p->link;head->link=p->link; // //头结点后第一个结点从头结点后第一个结点从链中零落链中零落delete p; p=NULL;delete p; p=NULL;}//}//删除脱离下来的结点删除脱离下来的结点} }7.2.2 单链表类设计单链表类设计不同于【例不同于【例7.5_h】的单链表类】的单链表类定义结点类：定义结点类：typedef int DataType;class Node{ DataType info; //数据域数据域 Node *link; //指针域指针域public: Node(); //生成空结点的构造函数生成空结点的构造函数 Node(const Datatype &); //生成普通结点的构造函数生成普通结点的构造函数 void PrintNode(); //打印当前结点的信息域打印当前结点的信息域 friend class SLList; //以以SLList为为Node友元类，友元类，SLList可直接访问可直接访问Node私有数据，私有数据，比构造平安比构造平安};例例7.5_h 结点类结点类Node::Node(){link=NULL;}Node::Node(const DataType & data){info=data;link=NULL; } void Node::PrintNode(){cout<link!=NULL) { //把头结点后的第一个结点从链中脱离把头结点后的第一个结点从链中脱离 p=head->link; head->link=p->link; delete p; p=NULL; //删除删除(释放释放)脱离下来的结点脱离下来的结点 } tail=head; //表头指针与表尾指针均指向表头结点，表示空链表头指针与表尾指针均指向表头结点，表示空链}例例7.5_h 单链表类单链表类链表类成员函数：链表类成员函数：Node* SLList::TravFind(DataType key){ Node*p=head->link; while(p!=NULL&&p->info!=key)p=p->link; return p;//搜索胜利前往该结点地址，不胜利前往搜索胜利前往该结点地址，不胜利前往NULL }void SLList::PrintSLL() { //显示链表显示链表 Node* p=head->link; while(p!=NULL) { cout<info<<'\t'; p=p->link; } cout<link=head->link;head->link=p; //新结点一直在头结点之后新结点一直在头结点之后}void SLList::GrowDN(const DataType& data){Node* p=new Node(data);tail->link=p;tail=p;tail->link=NULL;}链表类成员函数：链表类成员函数：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;while(q->link!=NULL && q->link!=p) q=q->link;//遍历查找if(q->link==tail) tail=q;//曾经找到末尾RemoveAfter(q);//删除q后面的结点p}例例7.5_h 主函数主函数void int main(){SLList L1; Node n, *tmp;for(int j=0;j<10;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.PrintSLL();//打印打印return 0;}结果：结果：7.2.2 单链表类单链表类讨论复制构造函数：复制构造函数：P239说法有待改良！如下：法有待改良！如下： 本例中没有本例中没有给出出Node类的复制构造函数的根本的复制构造函数的根本缘由在于：由在于：对Node类复制的复制的结果只是一个孤立果只是一个孤立结点：点：Node::Node(Node & node){info=node;link=NULL;}〔〔1〕不涉及〕不涉及动态内存分配，不存在深复制和浅复制的内存分配，不存在深复制和浅复制的问题〔参〔参见Node的构造函数〕，无需自定的构造函数〕，无需自定义复制构造函数和复制复制构造函数和复制赋值运运算符。

算符〔〔2〕〕Node和和SLList类的一切函数的参数和前往的一切函数的参数和前往值仅运用指向运用指向Node的指的指针，因此无需自定，因此无需自定义的复制构造函数；的复制构造函数；〔〔3〕假〕假设程序中确程序中确实需求需求经过复制建立复制建立Node对象，完全可由象，完全可由系系统默默许的复制构造函数和复制的复制构造函数和复制赋值运算符运算符实现复制〔按成复制〔按成员〕7.2.2 单链表类单链表类讨论复制构造函数：复制构造函数：单链表是表是经过动态内存分配建立的，因此内存分配建立的，因此链表的复制表的复制就涉及了深复制与浅复制就涉及了深复制与浅复制问题，必需自定，必需自定义复制构造复制构造函数和复制函数和复制赋值运算符对象深复制象深复制过程：程：〔〔1〕复制〕复制对象主体，即数据成象主体，即数据成员〔除了指向〔除了指向动态内存内存的指的指针〕；〕；数据成数据成员只需指向只需指向动态内存的指内存的指针head，，tail, 此步不此步不需求！需求！〔〔2〕〕为当前当前对象分配独立的自在存象分配独立的自在存储区空区空间；；分配一个完好的分配一个完好的链表所占据的自在存表所占据的自在存储区空区空间！！〔〔3〕将被复制〕将被复制对象的自在存象的自在存储区目的内容按位复制区目的内容按位复制给当前当前对象；象；将被复制将被复制链表中一切的信息域逐位复制表中一切的信息域逐位复制给当前当前链表！表！7.2.2 单链表类单链表类讨论复制构造函数：讨论复制构造函数：//拷贝构造函数拷贝构造函数SLList::SLList(SLList & ls){ Node* p=ls.head->link;head=tail=new Node();while(p!=NULL){GrowDN(p->info);//向后生长一个结点向后生长一个结点p=p->link;}}7.2.2 单链表类单链表类讨论复制构造函数：讨论复制构造函数：//拷贝赋值运算符拷贝赋值运算符SLList& SLList::operator=(SLList & ls){Node* p=ls.head->link;if(tail!=NULL) MakeEmpty();//提高平安性提高平安性while(p!=NULL){GrowDN(p->info);//向后生长一个结点向后生长一个结点p=p->link;}return *this;}7.3 栈与队列的根本操作及其运用栈与队列的根本操作及其运用 　栈和队都是特殊的线性表，限　栈和队都是特殊的线性表，限制存取位置的线性构造，可以由顺制存取位置的线性构造，可以由顺序表实现，也可以由链表实现。

序表实现，也可以由链表实现 7.　　3.　　1 栈栈 7.　　3.　　3　　队　列　　队　列 7.　　3.　　2 栈的运用〔选读〕栈的运用〔选读〕 。