數(shù)據(jù)結(jié)構(gòu)第2章b-12級

第2章線性表2.1線性表的概念及運(yùn)算2.2線性表的順序存儲

2.3線性表的鏈?zhǔn)酱鎯?.4順序表和鏈表的比較知識點(diǎn)回顧：順序表的存儲特點(diǎn)邏輯關(guān)系上相鄰的兩個元素在物理位置上也相鄰優(yōu)點(diǎn)：（1）不需要另設(shè)空間存儲邏輯關(guān)系；（2）方便隨機(jī)存取表中任一結(jié)點(diǎn)不足:(1)按最大長度預(yù)先分配表空間，難以擴(kuò)充（2）插入與刪除效率較低1能不能做到刪除時不移動大量元素呢？？思考2.3線性表的鏈?zhǔn)酱鎯?、鏈接存儲方法

鏈接方式存儲的線性表簡稱為鏈表（LinkedList）。

鏈表的具體存儲表示為：

①用一組任意的存儲單元來存放線性表的結(jié)點(diǎn)（這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的）

②鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲每個結(jié)點(diǎn)值的同時，還必須存儲指示其后繼結(jié)點(diǎn)的地址（或位置）信息（稱為指針（pointer）或鏈(link)）

注意：

鏈?zhǔn)酱鎯κ亲畛Ｓ玫拇鎯Ψ绞街?，它不僅可用來表示線性表，而且可用來表示各種非線性的數(shù)據(jù)結(jié)構(gòu)。

2.3線性表的鏈?zhǔn)酱鎯?、鏈表的結(jié)點(diǎn)結(jié)構(gòu)

┌───┬───┐

│data│next│

└───┴───┘

data域--存放結(jié)點(diǎn)值的數(shù)據(jù)域

next域--存放結(jié)點(diǎn)的直接后繼的地址（位置）的指針域（鏈域）3、頭指針head和終端結(jié)點(diǎn)指針域的表示

單鏈表中每個結(jié)點(diǎn)的存儲地址是存放在其前趨結(jié)點(diǎn)next域中，而開始結(jié)點(diǎn)無前趨，故應(yīng)設(shè)頭指針head指向開始結(jié)點(diǎn)。

注意：

鏈表由頭指針唯一確定，單鏈表可以用頭指針的名字來命名。

【例】頭指針名是head的鏈表可稱為表head。

終端結(jié)點(diǎn)無后繼，故終端結(jié)點(diǎn)的指針域為空，即NULL。

4、單鏈表的一般圖示法

5、線性表的單鏈存儲結(jié)構(gòu)

typedefintdatatype；

typedefstructNode{

datatypedata;

structNode*next;}linklist;linklist*head,*p,*L;帶頭結(jié)點(diǎn)的單鏈表(a)非空表(b)空表6.指針變量和結(jié)點(diǎn)變量

①生成結(jié)點(diǎn)變量的標(biāo)準(zhǔn)函數(shù)

p=(LinkList*)malloc(sizeof(LinkList))；

②釋放結(jié)點(diǎn)變量空間的標(biāo)準(zhǔn)函數(shù)

free(p)；

③結(jié)點(diǎn)分量的訪問

利用結(jié)點(diǎn)變量的名字*p訪問結(jié)點(diǎn)分量

方法一：(*p).data和(*p).next

方法二：p-﹥data和p-﹥next2.3.2單鏈表上的基本運(yùn)算建立頭插法：尾插法：帶頭結(jié)點(diǎn)的尾插法：查找刪除運(yùn)算頭插法建表從空表開始重復(fù)讀入數(shù)據(jù)創(chuàng)建新結(jié)點(diǎn)將新結(jié)點(diǎn)插入到鏈表的表頭上直到讀入結(jié)束標(biāo)志12一、建立單鏈表尾插法建表從空表開始重復(fù)讀入數(shù)據(jù)創(chuàng)建新結(jié)點(diǎn)將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上直到讀入結(jié)束標(biāo)志思考（1）觀察頭指針head的變化（2）單鏈表中每一個新結(jié)點(diǎn)的產(chǎn)生過程是否完全相同（3）生成鏈表中結(jié)點(diǎn)的順序與輸入順序有什么關(guān)系（1）頭插法建表

從一個空表開始,重復(fù)讀入數(shù)據(jù),生成新結(jié)點(diǎn),將讀入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域中,然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上,直到讀入結(jié)束標(biāo)志為止。該方法生成的鏈表的結(jié)點(diǎn)次序與輸入順序相反。

LinkList*CreatListF()//返回單鏈表的頭指針

{

charch;

LinkList*head;//頭指針

LinkList*s;

//工作指針

head=NULL;

//鏈表開始為空

ch=getchar();//讀入第1個字符

while(ch!='\n'){

s=(LinkList*)malloc(sizeof(LinkList));//生成新結(jié)點(diǎn)

s->data=ch;

//將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中

s->next=head;

head=s;

ch=getchar();

//讀入下一字符

}

returnhead;

}思考（1）觀察頭指針head的變化（2）與頭插法相比，尾插法創(chuàng)建鏈表每一個新結(jié)點(diǎn)的產(chǎn)生過程有什么不同？（3）生成鏈表中結(jié)點(diǎn)的順序與輸入順序是否相同尾插法建表步驟分解1.尾插法建表生成的鏈表中結(jié)點(diǎn)次序和輸入順序一致2.增加尾指針r,使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)3.創(chuàng)建第一個結(jié)點(diǎn)時，頭指針的變化

LinkList*CreatListR(void){

charch;LinkList*head,*s,*r;

//工作指針

head=NULL;

r=NULL;//鏈表開始為空,尾指針初值為空

ch=getchar();//讀入第1個字符

while(ch!=‘\n’){

s=(LinkList*)malloc(sizeof(LinkList));

s->data=ch;

if(head==NULL)

head=s;//新結(jié)點(diǎn)插入空表

else

r->next=s;//將新結(jié)點(diǎn)插到*r之后

r=s;//尾指針指向新表尾

ch=getchar();

//讀入下一字符}

if(r!=NULL)r->next=NULL;//對于非空表尾結(jié)點(diǎn)指針域置空

returnhead;

}（3）尾插法建帶頭結(jié)點(diǎn)的單鏈表

頭結(jié)點(diǎn)是在鏈表的開始結(jié)點(diǎn)之前附加一個結(jié)點(diǎn)。它具有兩個優(yōu)點(diǎn):

⒈由于開始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中,所以在鏈表的第一個位置上的操作就和在表的其它位置上操作一致,無須進(jìn)行特殊處理;

⒉無論鏈表是否為空，其頭指針都是指向頭結(jié)點(diǎn)的非空指針（空表中頭結(jié)點(diǎn)的指針域空），因此空表和非空表的處理也就統(tǒng)一了。linklist*CreatListR1(){

charch;

linklist*head=(linklist*)malloc(sizeof(linklist));

linklist*s,*r;

r=head;

while((ch=getchar())!='\n'){

s=(linklist*)malloc(sizeof(linklist));

s->data=ch;

r->next=s;

r=s;

}

r->next=NULL;

returnhead;

}按號查找給定待查找的結(jié)點(diǎn)序號i，從鏈表的頭指針出發(fā)，順鏈域next逐個結(jié)點(diǎn)往下搜索，直至搜索到第i個結(jié)點(diǎn)或是終端結(jié)點(diǎn)為止。12二、查找運(yùn)算按值查找從開始結(jié)點(diǎn)出發(fā)，順鏈域逐個將結(jié)點(diǎn)的值和給定值key作比較，若有結(jié)點(diǎn)的值與key相等，則返回首次找到的key結(jié)點(diǎn)的存儲位置；否則返回NULL。j=0head57123i=31719∧4j=1j=2j=3Linklist*GET(linklist*head,inti)

{

intj;

linklist*p;

p=head;j=0;

while(p->next!=NULL&&j<i)

{

p=p->next;

j++;

}

if(i==j)returnp;

elsereturnNULL;

}head57123i=31719∧42、按值查找linklist*LOCATE(linklist*head1,datatypekey){linklist*p;p=head1->next;while(p!=NULL)

if(p->data!=key)p=p->next;elsebreak;returnp;}查找算法的執(zhí)行時間與輸入key相關(guān)，其平均時間復(fù)雜度為O(n)。三、插入操作xsheada1aiai+1p原鏈表序列：a1,a2,……ai,ai+1插入后鏈表序列：a1,a2,……ai,x,ai+1后插操作圖示：voidINSERTAFTER(linklist*p,datatypex){linklist*s;s=(linklist*)malloc(sizeof(linklist));s->data=x;s->next=p->next;p->next=s;}后插操作具體算法如下：xheada1ai-1aips原鏈表序列：a1,a2,……ai-1,ai插入后鏈表序列：a1,a2,……ai-1,x,ai前插操作圖示：qvoidINSERTBEFORE(linklist*head,linklist*p,datatypex){linklist*s,*q;s=(linklist*)malloc(sizeof(linklist));s->data=x;q=head;while(q->next!=p)q=q->next;s->next=p;q->next=s;}前插操作具體算法如下：改進(jìn)的前插操作圖示：sheada1ai+1p原鏈表序列：a1,a2,……ai-1,ai插入后鏈表序列：a1,a2,……ai-1,x,aiaixaivoidINSERTBEFORE1(linklist*p,datatypex){linklist*s;s=(linklist*)malloc(sizeof(linklist));s->next=p->next;p->next=s;s->data=p->data;p->data=x;}改進(jìn)的前插操作具體算法：4.刪除運(yùn)算

刪除運(yùn)算是將表的第i個結(jié)點(diǎn)刪去。

具體步驟：

（1）找到ai-1的存儲位置p（因為在單鏈表中結(jié)點(diǎn)ai的存儲地址是在其直接前趨結(jié)點(diǎn)ai-1的指針域next中）

（2）令p-＞next指向ai的直接后繼結(jié)點(diǎn)（即把a(bǔ)i從鏈上摘下）

（3）釋放結(jié)點(diǎn)ai的空間，將其歸還給"存儲池"。

voidDeleteList(LinkList*head,inti)

{//刪除帶頭結(jié)點(diǎn)的單鏈表head上的第i個結(jié)點(diǎn)

ListNode*p,*r;

p=GetNode(head,i-1);//找到第i-1個結(jié)點(diǎn)

if(p==NULL||p->next==NULL)Error("positionerror");//i<1或i>n時，刪除位置錯,退出程序運(yùn)行

r=p->next;//使r指向被刪除的結(jié)點(diǎn)ai

p->next=r->next;//將ai從鏈上摘下

free(r);//釋放結(jié)點(diǎn)ai的空間給存儲池

}注意：

設(shè)單鏈表的長度為n，則刪去第i個結(jié)點(diǎn)僅當(dāng)1≤i≤n時是合法的。

當(dāng)i=n+1時，雖然被刪結(jié)點(diǎn)不存在，但其前趨結(jié)點(diǎn)卻存在，它是終端結(jié)點(diǎn)。因此被刪結(jié)點(diǎn)的直接前趨*p存在并不意味著被刪結(jié)點(diǎn)就一定存在，僅當(dāng)*p存在（即p！=NULL）且*p不是終端結(jié)點(diǎn)（即p-＞next！=NULL）時，才能確定被刪結(jié)點(diǎn)存在。

（3）算法分析

算法的時間復(fù)雜度也是O（n）。

鏈表上實(shí)現(xiàn)的插入和刪除運(yùn)算，無須移動結(jié)點(diǎn)，僅需修改指針。循環(huán)鏈表（CircularLinkedList）

1、循環(huán)鏈表

循環(huán)鏈表是一種首尾相接的鏈表。

（1）單循環(huán)鏈表——在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)或開始結(jié)點(diǎn)即可。

（2）多重鏈的循環(huán)鏈表——將表中結(jié)點(diǎn)鏈在多個環(huán)上。

判斷空鏈表的條件是head==head->next;

2、僅設(shè)尾指針的單循環(huán)鏈表

用尾指針rear表示的單循環(huán)鏈表對開始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an查找時間都是O(1)。而表的操作常常是在表的首尾位置上進(jìn)行，因此，實(shí)用中多采用尾指針表示單循環(huán)鏈表。帶尾指針的單循環(huán)鏈表可見下圖。判斷空鏈表的條件為rear==rear->next;3、循環(huán)鏈表的特點(diǎn)

循環(huán)鏈表的特點(diǎn)是無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。

【例】在鏈表上實(shí)現(xiàn)將兩個線性表（a1，a2，…，an）和（b1，b2，…，bm）連接成一個線性表（a1，…，an，b1，…bm）的運(yùn)算。分析：若在單鏈表或頭指針表示的單循環(huán)表上做這種鏈接操作，都需要遍歷第一個鏈表，找到結(jié)點(diǎn)an，然后將結(jié)點(diǎn)b1鏈到an的后面，其執(zhí)行時間是O(n)。若在尾指針表示的單循環(huán)鏈表上實(shí)現(xiàn)，則只需修改指針，無須遍歷，其執(zhí)行時間是O(1)。

LinkList*Connect(LinkList*A,LinkList*B)

{//假設(shè)A，B為非空循環(huán)鏈表的尾指針

LinkList*p=A->next;//①保存A表的頭結(jié)點(diǎn)位置

A->next=B->next->next;//②B表的開始結(jié)點(diǎn)鏈接到A表尾

free(B->next);//③釋放B表的頭結(jié)點(diǎn)

B->next=p;//④

returnB;//返回新循環(huán)鏈表的尾指針

}注意：

①循環(huán)鏈表中沒有NULL指針。涉及遍歷操作時，其終止條件就不再是像非循環(huán)鏈表那樣判別p或p-＞next是否為空，而是判別它們是否等于某一指定指針，如頭指針或尾指針等。

②在單鏈表中，從一已知結(jié)點(diǎn)出發(fā)，只能訪問到該結(jié)點(diǎn)及其后續(xù)結(jié)點(diǎn)，無法找到該結(jié)點(diǎn)之前的其它結(jié)點(diǎn)。而在單循環(huán)鏈表中，從任一結(jié)點(diǎn)出發(fā)都可訪問到表中所有結(jié)點(diǎn)，這一優(yōu)點(diǎn)使某些運(yùn)算在單循環(huán)鏈表上易于實(shí)現(xiàn)。雙鏈表

1、雙向鏈表（DoubleLinkedList）

雙（向）鏈表中有兩條方向不同的鏈，即每個結(jié)點(diǎn)中除next域存放后繼結(jié)點(diǎn)地址外，還增加一個指向其直接前趨的指針域prior。注意：

①雙鏈表由頭指針head惟一確定的。

②帶頭結(jié)點(diǎn)的雙鏈表的某些運(yùn)算變得方便。

③將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來，為雙（向）循環(huán)鏈表。2、雙向鏈表的結(jié)點(diǎn)形式描述

ty