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

第二章線性表

2.1線性表的類型定義?

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

?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鏈表的基本概念?什么是鏈表

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

什么是鏈表？鏈表——

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

什么是鏈表?

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

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

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

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

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

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

//LNode*next;//指針域

structLNod*next;}LNode,*LinkList;

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

若有：在單鏈表的第一個結(jié)點(diǎn)之前設(shè)一個頭結(jié)點(diǎn)頭結(jié)點(diǎn)的數(shù)據(jù)域不存儲數(shù)據(jù)頭結(jié)點(diǎn)的指針域存儲第一個結(jié)點(diǎn)的地址空鏈表L->next=NULL三、帶頭結(jié)點(diǎn)的單鏈表L28597L為什么要設(shè)頭結(jié)點(diǎn)？答：頭結(jié)點(diǎn)即在鏈表的首元素結(jié)點(diǎn)之前附設(shè)的一個結(jié)點(diǎn)，其作用是為了對鏈表進(jìn)行操作時，可以對空表、非空表的情況以及對首元素結(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個元素GetElem_L（L,i,&e）i=3思路：要取第i個數(shù)據(jù)元素，關(guān)鍵是要先找到該結(jié)點(diǎn)的指針p,然后輸出p地址存儲的數(shù)據(jù)元素的值p->data。難點(diǎn)：單鏈表中想取得第i個元素，必須從頭指針出發(fā)尋找（順藤摸瓜），不能隨機(jī)存取。a1a2a3anL∧PStatus

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

LinkListp=L->next;//

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

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

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

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

e=p->data;//取第pos個元素

returnOK;}//GetElem_Lpos=3pL28597

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

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

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

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個元素，并由e返回其值

LinkListp=L->next,q; intj=1; while(p!=NULL&&j<pos) {//尋找第pos個結(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個元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L。

L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一個帶頭結(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個元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L。

L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一個帶頭結(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)酱鎯窝h(huán)鏈表最后一個結(jié)點(diǎn)的指針域的指針又指回第一個結(jié)點(diǎn)的鏈表怎么樣判斷鏈表為空？if(head->next==head)循環(huán)鏈表的操作和單鏈表基本一致，差別僅在于算法中的循環(huán)條件不是p或者p->next是否為空，而是p或者p->next是否等于頭指針p->next=heada1headpa2帶尾指針的單循環(huán)鏈表：a1anaiRR空表：這時：R->next==R這時：頭指針為：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)酱鎯枺烘湵碇荒懿檎医Y(jié)點(diǎn)的直接后繼，能不能找到直接前驅(qū)？答：能，只要給每個結(jié)點(diǎn)多開一個指針域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一個空的雙向循環(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)酱鎯捂湵淼谋黹L是一個隱含的值；在單鏈表的最后一個元素最后插入元素時，需遍歷整個鏈表；在鏈表中，元素的“位序”概念淡化，結(jié)點(diǎn)的“位置”概念強(qiáng)化。用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時，存在的問題：增加“表長”和“表尾指針”兩個數(shù)據(jù)域；改進(jìn)鏈表的設(shè)置：改進(jìn)的單鏈表類型typedefstruct

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

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

{//鏈表類型

Linkhead,tail;

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

intlen;

//指示鏈表長度}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)酱鎯σ辉囗?xiàng)式的表示

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

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

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

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

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

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