數(shù)據(jù)結構 單鏈表講授

數(shù)據(jù)結構——第2章線性表掌握線性表的順序存儲的實現(xiàn)及順序表的存儲類型定義。掌握順序表的創(chuàng)建、查找、插入和刪除算法及算法的分析（時間復雜度）。復習本章內(nèi)容2.1線性表的邏輯結構2.2線性表的順序存儲及運算實現(xiàn)2.3線性表的鏈式存儲及運算實現(xiàn)2.3線性表的鏈式存儲和運算實現(xiàn)

2.3.1單鏈表

2.3.2單鏈表上基本運算的實現(xiàn)

2.3.3循環(huán)鏈表和雙向鏈表

2.3.4靜態(tài)鏈表

2.3.5單鏈表應用舉例2.3.1單鏈表線性表以鏈式存儲方式存儲時稱為鏈表。存儲實現(xiàn)：◆用一組任意的存儲單元存儲線性表的元素；◆利用指針存放邏輯上相鄰的元素間的關系。結論：每個數(shù)據(jù)元素，除存儲本身信息外，還需存儲其直接后繼的地址。結點

數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲位置數(shù)據(jù)域指針域2.3.1單鏈表相關術語單鏈表頭指針值域指針域NULL頭結點結點類型定義：

typedef

structnode{ DataType

data;

structnode*next;}LNode，*LinkList；舉例：LNode*L;LinkListL;2.3.2單鏈表上基本運算的實現(xiàn)1、單鏈表的創(chuàng)建（頭插入法和尾插入法）2、單鏈表的查找3、單鏈表的插入4、單鏈表的刪除2.3.2單鏈表上基本運算的實現(xiàn)1、單鏈表的創(chuàng)建用頭插入法建立單鏈表

◆創(chuàng)建一個新結點的語句◆創(chuàng)建一個帶頭結點的單鏈表

◆創(chuàng)建單鏈表的過程

◆結點間的連接語句2.3.2單鏈表上基本運算的實現(xiàn)1、單鏈表的創(chuàng)建用頭插入法建立單鏈表

◆創(chuàng)建一個新結點的語句

LNode*s;s=newLNode;s->data=x;◆創(chuàng)建一個帶頭結點的單鏈表

◆創(chuàng)建單鏈表的過程

◆結點間的連接語句2.3.2單鏈表上基本運算的實現(xiàn)1、單鏈表的創(chuàng)建用頭插入法建立單鏈表

◆創(chuàng)建一個新結點的語句◆創(chuàng)建一個帶頭結點的單鏈表

LinkListL;L=newLNode;L->next=NULL;

◆創(chuàng)建單鏈表的過程

◆結點間的連接語句2.3.2單鏈表上基本運算的實現(xiàn)1、單鏈表的創(chuàng)建用頭插入法建立單鏈表

◆創(chuàng)建一個新結點的語句◆創(chuàng)建一個帶頭結點的單鏈表

◆創(chuàng)建單鏈表的過程

◆結點間的連接語句

LinkListL;s->next=L->next;L->next=s;2.3.2單鏈表上基本運算的實現(xiàn)1、單鏈表的創(chuàng)建LinkListCreat_LinkList1(){LinkListL；L=newLNode;L->next=NULL;

Lnode*s;DataTypex;

cin>>x;while(x!=flag)//flag是結束標志！

{s=newLNode;s->data=x;s->next=L->next;L->next=s;

cin>>x;}returnL;}2.3.2單鏈表上基本運算的實現(xiàn)1、單鏈表的創(chuàng)建LinkListCreat_LinkList1(){LinkListL；L=newLNode;L->next=NULL;

Lnode*s;DataTypex;

cin>>x;while(x!=flag)//flag是結束標志！

{s=newLNode;s->data=x;s->next=L->next;L->next=s;

cin>>x;}returnL;}LinkListCreat_LinkList1(){LinkListL；

L=newLNode;L->next=NULL;

Lnode*s;DataTypex;

cin>>x;2.3.2單鏈表上基本運算的實現(xiàn)1、單鏈表的創(chuàng)建LinkListCreat_LinkList1(){LinkListL；L=newLNode;L->next=NULL;

Lnode*s;DataTypex;

cin>>x;while(x!=flag)//flag是結束標志！

{s=newLNode;s->data=x;s->next=L->next;L->next=s;

cin>>x;}returnL;}while(x!=flag)//flag是結束標志！

{s=newLNode;s->data=x;s->next=L->next;L->next=s;

cin>>x;}returnL;2.3.2單鏈表上基本運算的實現(xiàn)1、單鏈表的創(chuàng)建用尾插入法建立單鏈表

◆創(chuàng)建一個新結點的語句◆創(chuàng)建一個帶頭結點的單鏈表

◆創(chuàng)建過程

◆結點間的連接語句

Lnode*r;

//指向已建成單鏈表的最后一個結點

s->next=NULL;r->next=s;r=s;LinkListCreat_LinkList2(){LinkListL;L=newLNode;L->next=NULL;

Lnode*s,*r=L;DataTypex;cin>>x;while(x!=flag){s=newLNode;s->data=x;r->next=s;r=s;

cin>>x;}r->next=NULL;returnL;}2.3.2單鏈表上基本運算的實現(xiàn)

LinkListCreat_LinkList2(){LinkListL;L=newLNode;L->next=NULL;

Lnode*s,*r=L;

DataTypex;cin>>x;LinkListCreat_LinkList2(){LinkListL;L=newLNode;L->next=NULL;

Lnode*s,*r=L;DataTypex;cin>>x;while(x!=flag){s=newLNode;s->data=x;r->next=s;r=s;

cin>>x;}r->next=NULL;returnL;}2.3.2單鏈表上基本運算的實現(xiàn)

while(x!=flag){s=newLNode;s->data=x;r->next=s;r=s;

cin>>x;}r->next=NULL;returnL;2.3.2單鏈表上基本運算的實現(xiàn)1、單鏈表的創(chuàng)建用尾插入法或頭插入法建立的單鏈表都是帶頭結點的。如何用頭插入法和尾插入法建立不帶頭結點的單鏈表，兩種算法有什么區(qū)別？結論：？創(chuàng)建帶頭結點的單鏈表可簡化鏈表操作。2.3.2單鏈表上基本運算的實現(xiàn)2、查找操作按序號查找

◆查找成功返回指向該結點的指針，不成功返回空值。

◆查找過程◆特殊情況判斷2.3.2單鏈表上基本運算的實現(xiàn)2、查找操作按序號查找

◆查找成功返回指向該結點的指針，不成功返回空值。

◆查找過程

Lnode*p=L->next;intj=1;

while(p!=NULL&&j<i){p=p->next;j++;}◆特殊情況判斷2.3.2單鏈表上基本運算的實現(xiàn)2、查找操作按序號查找

◆查找成功返回指向該結點的指針，不成功返回空值。

◆查找過程◆特殊情況判斷

（1）單鏈表是空表（2）i不合法（1<=i<=單鏈表長度）LNode*Get_LinkList(LinkListL,inti){LNode*p=L->next;

intj=1;

if(i<1)returnNULL;while(p!=NULL&&j<i){p=p->next;j++;}if(p!=NULL)returnp;elsereturnNULL;}2、查找操作2.3.2單鏈表上基本運算的實現(xiàn)2.3.2單鏈表上基本運算的實現(xiàn)2、查找操作按值查找Locate_LinkList(L,x)

◆查找成功返回指向該結點的指針，不成功返回空值。

◆查找過程

◆特殊情況判斷：單鏈表是否是空表

◆實現(xiàn)算法LNode*Locate_LinkList(LinkListL,DataTypex){LNode*p=L->next;while(p!=NULL&&p->data!=x)p=p->next;returnp;}2、查找操作2.3.2單鏈表上基本運算的實現(xiàn)3、插入操作插入運算：Insert_LinkList(L,i,x)插入結點：將新結點s插入到p結點（第i個）位置2.3.2單鏈表上基本運算的實現(xiàn)3、插入操作插入結點過程首先要找到p的前驅q，然后將s插入在q之后。操作：q=L;//單鏈表頭指針為Lwhile(q->next!=p)q=q->next;s->next=q->next;q->next=s；2.3.2單鏈表上基本運算的實現(xiàn)3、插入操作插入運算：Insert_LinkList(L,i,x)插入過程：1、創(chuàng)建新結點，找到第i-1個結點，進行插入。2、插入位置不合法（1<=i<=單鏈表的長度+1）算法實現(xiàn)2.3.2單鏈表上基本運算的實現(xiàn)2.3.2單鏈表上基本運算的實現(xiàn)3、插入操作int

Insert_LinkList(LinkListL,inti,DataTypex){LNode*p,*s;

p=Get_LinkList(L,i-1);

if(p==NULL){cout<<“參數(shù)i錯”<<endl;return0;}else{s=newLNode;s->data=x;s->next=p->next;p->next=s;return1;}}有沒有問題？2.3.2單鏈表上基本運算的實現(xiàn)3、插入操作int

Insert_LinkList(LinkListL,inti,DataTypex){LNode*p,*s;

if(i==1)p=L;elsep=Get_LinkList(L,i-1);

if(p==NULL){cout<<“參數(shù)i錯”<<endl;return0;}else{s=newLNode;s->data=x;s->next=p->next;p->next=s;return1;}}3、插入操作插入運算：Insert_LinkList(L,i,x)插入過程：算法實現(xiàn)：性能分析：時間復雜度為o(n)2.3.2單鏈表上基本運算的實現(xiàn)4、刪除操作刪除運算：Del_LinkList(L,i)算法過程：1、找到第i-1個結點；進行刪除；釋放空間。2、刪除位置不合法（1<=i<=單鏈表長度）算法實現(xiàn)：2.3.2單鏈表上基本運算的實現(xiàn)2.3.2單鏈表上基本運算的實現(xiàn)4、刪除操作int

Del_LinkList(LinkList

L,inti){LNode*p=L,*q;intj=0;

if(i<1){cout<<“結點不存在!”;return-1;}

while((p->next!=NULL)&&(j<i-1)){p=p->next;j++;}if(p->next==NULL){cout<<“結點不存在!”;return0;}else{q=p->next;p->next=q->next;deleteq;return1;}}4、刪除操作刪除運算：Del_LinkList(L,i)算法過程：1、找到第i-1個結點；進行刪除；釋放空間。2、刪除位置不合法（1<=i<=單鏈表長度）

3、需要保留被刪除元素。算法實現(xiàn)：2.3.2單鏈表上基本運算的實現(xiàn)2.3.2單鏈表上基本運算的實現(xiàn)3、插入操作int

Del_LinkList(LinkList

L,int

i,DataType

&x){LNode*p=L,*q;intj=0;

if(i<1){cout<<“結點不存在!＂;return-1;}

while((p->next!=NULL)&&(j<i-1)){p=p->next;j++;}if(p->next==NULL){cout<<“結點不存在!＂;return0;}else{q=p->next;x=q->data;

p->next=q->next;deleteq;return1;}}4、刪除操作刪除運算：Del_LinkList(L,i)算法過程：算法實現(xiàn)：性能分析：時間復雜度O(n)2.3.2單鏈表上基本運算的實現(xiàn)總結：創(chuàng)建新結點時動態(tài)分配空間。查找結點只能順序查找，不能隨機查找。進行插入和刪除操作時都需要先找到進行插入和刪除的結點的前驅結點，通過移動指針實現(xiàn)。鏈表進行操作時，不要隨意移動頭指針。與位置相關的操作一定要判斷位置的合法性。2.3.2單鏈表上基本運算的實現(xiàn)2.3線性表的鏈式存儲和運算實現(xiàn)

2.3.1單鏈表

2.3.2單鏈表上基本運算的實現(xiàn)

2.3.3循環(huán)鏈表和雙向鏈表

2.3.4靜態(tài)鏈表

2.3.5單鏈表應用舉例2.3.3循環(huán)鏈表和雙向鏈表循環(huán)單鏈表是指將鏈表中最后一個結點的指針指向表頭結點或第一個結點，使鏈表構成環(huán)狀。特點：從表中任一結點出發(fā)均可找到表中其他結點，提高查找效率。HH2.3.3循環(huán)鏈表和雙向鏈表循環(huán)單鏈表的操作與單鏈表基本一致，不同之處在于算法中對鏈表為空的判斷條件發(fā)生變化：單鏈表：p->next=NULL循環(huán)鏈表：p->next=LHH^2.3.3循環(huán)鏈表和雙向鏈表雙向鏈表：構成鏈表的結點中包含兩個指針域，分別指向該結點的前驅結點和后繼結點。H

^^H^^2.3.3循環(huán)鏈表和雙向鏈表

雙向鏈表結點類型定義：typedef

struct

dnode{

DataTypedata;

struct

dnode

*prior,*next;}DLNode,*DLinkList;2.3.3循環(huán)鏈表和雙向鏈表

雙向鏈表主要操作

雙向鏈表中通過某結點的指針p即可以直接得到它的后繼結點的指針p->next，也可以直接得到它的前驅結點的指針p->prior。p->prior->next==p==p->next->prior2.3.3循環(huán)鏈表和雙向鏈表

雙向鏈表主要操作

雙向鏈表插入：將新結點s插入在p的前面。①s->prior=p->prior;②p->prior->next=s;③s->next=p;④p->prior=s;

2.3.3循環(huán)鏈表和雙向鏈表

雙向鏈表主要操作

雙向鏈表刪除：刪除p結點。①p->prior->next=p->next;②p->next->prior=p->prior;③deletep;2.3線性表的鏈式存儲和運算實現(xiàn)

2.3.1單鏈表

2.3.2單鏈表上基本運算的實現(xiàn)

2.3.3循環(huán)鏈表和雙向鏈表

2.3.4靜態(tài)鏈表

2.3.5單鏈表應用舉例2.3.4靜態(tài)鏈表

靜態(tài)鏈表

將單鏈表中結點的指針用相對地址來描述，即數(shù)組的下標。2.3.4靜態(tài)鏈表

靜態(tài)鏈表

數(shù)組sd定義：

#defineMAXSIZE…typedef

struct

{DataTypedata;

intnext;}SNode;SNode

sd[MAXSIZE];

intSL,AV;