的數(shù)據(jù)結(jié)構(gòu)第二章線性表

第二章線性表

2.1線性表的類型定義?

2.2線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3線性表類型鏈?zhǔn)酱鎯?chǔ)

?2.3.1鏈表的基本概念

2.3.2單鏈表

2.3.3單循環(huán)鏈表

2.3.4雙向循環(huán)鏈表

2.3.5改進(jìn)的鏈表及基本操作

2.3.6鏈表的應(yīng)用

2.3.1鏈表的基本概念?什么是鏈表

鏈表的存儲(chǔ)結(jié)構(gòu)

什么是鏈表？鏈表——

鏈?zhǔn)酱鎯?chǔ)的線性表用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素（這組存儲(chǔ)地址可以連續(xù)或者非連續(xù)）以線性表中第一個(gè)數(shù)據(jù)元素a1的存儲(chǔ)地址作為線性表的地址，為線性表的頭指針2.3.1鏈表的基本概念2.3.1鏈表的基本概念

什么是鏈表?

鏈表的存儲(chǔ)結(jié)構(gòu)

2.3.1鏈表的基本概念鏈表的存儲(chǔ)結(jié)構(gòu)鏈表中的每個(gè)數(shù)據(jù)元素稱為結(jié)點(diǎn)

每個(gè)結(jié)點(diǎn)包括：

數(shù)據(jù)域——存放數(shù)據(jù)元素ai的值；

指針域——存放ai的直接后繼ai＋1的地址鏈表正是通過(guò)每個(gè)結(jié)點(diǎn)的指針域?qū)⒈碇衝個(gè)數(shù)據(jù)元素按其邏輯順序鏈接在一起的鏈表中數(shù)據(jù)元素的邏輯順序與其物理存儲(chǔ)順序不一定相同；【例】設(shè)有一組線性排列的數(shù)據(jù)元素（zhao,qian,sun,li,zhou,wu,zheng,wang），其鏈接存儲(chǔ)形式下頁(yè)圖所示：討論：在該存儲(chǔ)方式下，如何找到表中任一元素？答：在鏈接存儲(chǔ)方式下（鏈表中），每一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址是存放在其直接前驅(qū)結(jié)點(diǎn)的next域中，只要知道第一個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）zhao的存儲(chǔ)地址，就可以“順藤摸瓜”找到其后續(xù)的所有結(jié)點(diǎn)。存儲(chǔ)地址數(shù)據(jù)域指針域………………………………………zhaolizhouzhengqianwang100sunwu160170200210220310320320210160310200220100∧頭指針H170zhaozhouzhengqianlisunwuwang∧H通常情況下，我們用箭頭來(lái)表示指針域中的指針，忽略每一個(gè)結(jié)點(diǎn)的實(shí)際存儲(chǔ)位置，而重點(diǎn)突出鏈表中結(jié)點(diǎn)間的邏輯順序，將鏈表直觀地畫(huà)成用箭頭鏈接起來(lái)的結(jié)點(diǎn)序列。

2.3.1鏈表的基本概念

?2.3.2單鏈表

2.3.3單循環(huán)鏈表

2.3.4雙向循環(huán)鏈表

2.3.5改進(jìn)的鏈表及基本操作

2.3.6鏈表的應(yīng)用

2.3線性表類型鏈?zhǔn)酱鎯?chǔ)2.3.2單鏈表一、定義鏈表的每個(gè)結(jié)點(diǎn)只有一個(gè)指針域——單鏈表data2nextdata1datanext可以有多個(gè)數(shù)據(jù)域二、單鏈表結(jié)點(diǎn)的C語(yǔ)言描述typedefstructLNod

{ElemTypedata;//數(shù)據(jù)域

//LNode*next;//指針域

structLNod*next;}LNode,*LinkList;

datanextLNodes;LinkListL;LNode*L;注意2者區(qū)別？？zhaozhouqianlisunzhengwuwang∧H稱H為該單鏈表的頭指針。若已知單鏈表的頭指針，則可以搜索到表中任一結(jié)點(diǎn)；也就是說(shuō)，單鏈表由頭指針唯一確定。因此，單鏈表可以用頭指針的名字來(lái)命名。上圖所示的單鏈表可稱為單鏈表H。

若有：在單鏈表的第一個(gè)結(jié)點(diǎn)之前設(shè)一個(gè)頭結(jié)點(diǎn)頭結(jié)點(diǎn)的數(shù)據(jù)域不存儲(chǔ)數(shù)據(jù)頭結(jié)點(diǎn)的指針域存儲(chǔ)第一個(gè)結(jié)點(diǎn)的地址空鏈表L->next=NULL三、帶頭結(jié)點(diǎn)的單鏈表L28597L為什么要設(shè)頭結(jié)點(diǎn)？答：頭結(jié)點(diǎn)即在鏈表的首元素結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元素結(jié)點(diǎn)進(jìn)行統(tǒng)一處理，編程更方便。討論.在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？Status

GetElem_L

(LinkListL,intpos,ElemType&e)StatusListInsert_L

(LinkListL,intpos,ElemTypee)

StatusListDelete_L(LinkListL,intpos,ElemType&e)voidCreateList_L(LinkList&L,intn)

voidCreateList_L(LinkList&L)

四、帶頭結(jié)點(diǎn)的單鏈表基本操作的實(shí)現(xiàn)

（1Union_LinkList.cpp）取第i個(gè)元素GetElem_L（L,i,&e）i=3思路：要取第i個(gè)數(shù)據(jù)元素，關(guān)鍵是要先找到該結(jié)點(diǎn)的指針p,然后輸出p地址存儲(chǔ)的數(shù)據(jù)元素的值p->data。難點(diǎn)：?jiǎn)捂湵碇邢肴〉玫趇個(gè)元素，必須從頭指針出發(fā)尋找（順藤摸瓜），不能隨機(jī)存取。a1a2a3anL∧PStatus

GetElem_L(LinkListL,intpos,ElemType&e){/*將第pos個(gè)數(shù)據(jù)元素的值賦給e并返回OK，否則返回ERROR*/

LinkListp=L->next;//

p指向第一個(gè)結(jié)點(diǎn)

j=1;//j為計(jì)數(shù)器

while(p&&j<pos){//順指針向后查找，直到p為空或p指向第pos個(gè)元素

p=p->next;j++;}if(!p||j>pos)returnERROR;//第pos個(gè)元素不存在

e=p->data;//取第pos個(gè)元素

returnOK;}//GetElem_Lpos=3pL28597

StatusListInsert_L(LinkList&L,intpos,ElemTypee){//在帶頭結(jié)點(diǎn)的單鏈表L中第pos個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素e

LinkListp=L->next; intj=1;while(p&&j<pos-1)//尋找第pos-1個(gè)結(jié)點(diǎn)

{p=p->next;j++;}if(!p)returnERROR;//pos小于1或者大于表長(zhǎng)

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

s->data=e;s->next=p->next;p->next=s;

//插入L中

returnOK;}

//LinstInsert_Lpos=3e=4

4spL28575StatusListDelete_L(LinkListL,intpos,ElemType&e){//在帶頭結(jié)點(diǎn)的單鏈表L中，刪除第pos個(gè)元素，并由e返回其值

LinkListp=L->next,q; intj=1; while(p!=NULL&&j<pos) {//尋找第pos個(gè)結(jié)點(diǎn)，并令p指向其前趨

q=p; p=p->next; j++; } if(p==NULL||j>pos)returnERROR;//刪除位置不合理

q->next=p->next;//刪除并釋放結(jié)點(diǎn)

e=p->data; free(p); returnOK;}//ListDelete_Lqpos=3pL25785voidCreateList_L(LinkList&L,intn){//逆位序輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L。

L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表

for(i=n;i>0;i--){p=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點(diǎn)

scanf(“%d”,&p->data);//輸入元素值

p->next=L->next;L->next=p;

//插入到表頭

}}//CreateList_L8Lp8voidCreateList_L(LinkList&L,intn){//逆位序輸入n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L。

L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表

q=L;//保持q指向當(dāng)前表尾

for(i=1;i<=n;i++)//n=2{p=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點(diǎn)

scanf(“%d”,&p->data);//輸入元素值

q->next=p; q=p;

//插入到表尾

}q->next=NULL;}//CreateList_Lcreat之尾插：

2.3.1鏈表的基本概念

2.3.2單鏈表?2.3.3單循環(huán)鏈表

2.3.4雙向循環(huán)鏈表

2.3.5改進(jìn)的鏈表及基本操作

2.3.6鏈表的應(yīng)用

2.3線性表類型鏈?zhǔn)酱鎯?chǔ)單循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)的鏈表怎么樣判斷鏈表為空？if(head->next==head)循環(huán)鏈表的操作和單鏈表基本一致，差別僅在于算法中的循環(huán)條件不是p或者p->next是否為空，而是p或者p->next是否等于頭指針p->next=heada1headpa2帶尾指針的單循環(huán)鏈表：a1anaiRR空表：這時(shí)：R->next==R這時(shí)：頭指針為：R－>next

2.3.1鏈表的基本概念

2.3.2單鏈表

2.3.3單循環(huán)鏈表

?2.3.4雙向循環(huán)鏈表

2.3.5改進(jìn)的鏈表及基本操作

2.3.6鏈表的應(yīng)用

2.3線性表類型鏈?zhǔn)酱鎯?chǔ)問(wèn)：鏈表只能查找結(jié)點(diǎn)的直接后繼，能不能找到直接前驅(qū)？答：能，只要給每個(gè)結(jié)點(diǎn)多開(kāi)一個(gè)指針域typedefstructDuLNode

{ElemTypedata;//數(shù)據(jù)域

DuLNode*prior;//指向前驅(qū)的指針域

DuLNode*next;//指向后繼的指針域}DuLNode,*DuLinkList;priordatanexta1La2a3和單循環(huán)鏈表類似，雙向鏈表也可以有循環(huán)鏈表雙向循環(huán)鏈表a1La2a3pp->next->prior==p->prior->next==p一個(gè)空的雙向循環(huán)鏈表：LL->next==LL->prior==L雙向循環(huán)鏈表的操作a1La2a3pstatusListInsert_Dul(DuLinkList&L,inti,ElemTypee)statusListDelete_Dul(DuLinkList&L,inti,ElemTypee)statusListInsert_Dul(DuLinkList&L,inti,ElemTypee)xspai-1aiai+1p->prior

(4)p->prior=s(3)p->prior->next=s(1)s->prior=p->prior(2)s->next=pstatusListInsert_Dul(DuLinkList&L,inti,ElemTypee){if(!(p=GetElemP_Dul(L,i)))returnERROR;if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))returnERROR;

s->data=e;s->prior=p->prior;s->next=p;p->prior->next=s;p->prior=s;returnOK;}//ListInsert_Dulpaiai+1ai-1

p->prior->next=p->next;

p->next->prior=p->prior;

free(p);p->priorp->nextstatusListDelete_Dul(DuLinkList&L,inti,ElemTypee)status

ListDelete_Dul(DuLinkList

&L,inti,ElemTypee){if(!(p=GetElemP_Dul(L,i)))returnERROR;e=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);returnOK;}//ListDelete_Dulpai+1ai-1aip－>priorp－>next

2.3.1鏈表的基本概念

2.3.2單鏈表

2.3.3單循環(huán)鏈表

2.3.4雙向循環(huán)鏈表

?2.3.4改進(jìn)的鏈表及基本操作

2.3.5鏈表的應(yīng)用2.3線性表類型鏈?zhǔn)酱鎯?chǔ)單鏈表的表長(zhǎng)是一個(gè)隱含的值；在單鏈表的最后一個(gè)元素最后插入元素時(shí)，需遍歷整個(gè)鏈表；在鏈表中，元素的“位序”概念淡化，結(jié)點(diǎn)的“位置”概念強(qiáng)化。用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時(shí)，存在的問(wèn)題：增加“表長(zhǎng)”和“表尾指針”兩個(gè)數(shù)據(jù)域；改進(jìn)鏈表的設(shè)置：改進(jìn)的單鏈表類型typedefstruct

LNode{//結(jié)點(diǎn)類型

ElemTypedata;structLNode*next;}*Link,*Position;typedefstruct

{//鏈表類型

Linkhead,tail;

//指向頭結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)

intlen;

//指示鏈表長(zhǎng)度}LinkList;headtaillendatanextheadtailLen4L

2.3.1鏈表的基本概念

2.3.2單鏈表

2.3.3單循環(huán)鏈表

2.3.4雙向循環(huán)鏈表

2.3.4改進(jìn)的鏈表及基本操作

?2.3.5鏈表的應(yīng)用2.3線性表類型鏈?zhǔn)酱鎯?chǔ)一元多項(xiàng)式的表示

一元多項(xiàng)式pn(x)=p0+p1x+p2x2+……pnxn在計(jì)算機(jī)中，可以用一個(gè)線性表來(lái)表示:P=(p0，p1，…，pn)但是對(duì)于形如:S(x)=1+3x10000–2x20000的多項(xiàng)式，上述表示也就不恰當(dāng)了。一般情況下的一元多項(xiàng)式可寫(xiě)成

Pn(x)=p1xe1+p2xe2+……+pmxem其中：pi是指數(shù)為ei

的項(xiàng)的非零系數(shù)，

0≤e1<e2<……<em=n它可以用其數(shù)據(jù)元素為(系數(shù)項(xiàng)，指數(shù)項(xiàng))的線性表來(lái)表示（（p1，e1），(p2，e2)，……，(pm，em)）例如：線性表(

(7,3),(-2,12),(-8,999))表示多項(xiàng)式

P(x)=7x3-2x12-8x999抽象數(shù)據(jù)