數(shù)據(jù)結(jié)構(gòu)與算法課件第4章

數(shù)據(jù)結(jié)構(gòu)與算法分析

APracticalIntroductionto

DataStructuresandAlgorithmAnalysis

陳星

第4章線性表、棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)：相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。反映

數(shù)據(jù)的值和數(shù)據(jù)的位置邏輯結(jié)構(gòu)：反映數(shù)據(jù)元素之間邏輯關(guān)系。存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間的存放形式。4.1線性表由稱為元素(element)的數(shù)據(jù)項(xiàng)組成的一種有限且有序的序列。記為：<a0,a1,…,an-1>

術(shù)語(yǔ)：空表、長(zhǎng)度、表頭、表尾、有序線性表、無(wú)序線性表線性和非線性:線性linear，指量與量之間按比例、成直線的關(guān)系，在數(shù)學(xué)上可以理解為一階導(dǎo)數(shù)為常數(shù)的函數(shù)；非線性non-linear則指不按比例、不成直線的關(guān)系，一階導(dǎo)數(shù)不為常數(shù)。線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的有序集合,它有四個(gè)基本特征：集合中必存在唯一的一個(gè)"第一個(gè)元素"；集合中必存在唯一的一個(gè)"最后的元素"；除最后元素之外，其它數(shù)據(jù)元素均有唯一的"后繼"；除第一元素之外，其它數(shù)據(jù)元素均有唯一的"前驅(qū)"。

線性表ADT抽象數(shù)據(jù)類型是指數(shù)據(jù)結(jié)構(gòu)作為一個(gè)軟件組件的實(shí)現(xiàn)。通過(guò)ADT掌握數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)和操作。

線性表ADT設(shè)計(jì)的思想：當(dāng)前位置。一個(gè)柵欄和兩個(gè)分離部分。如：<20,23|12,15>注：當(dāng)前位置的元素（當(dāng)前元素）為柵欄右邊的第1個(gè)元素，或右邊部分的第1個(gè)元素。線性表的C++抽象類聲明template<classElem>classList{public:virtualvoidclear()=0;//回收元素的存儲(chǔ)空間virtualboolinsert(constElem&)=0;//當(dāng)前位置插入新元素virtualboolappend(constElem&)=0;//表尾插入新元素virtualboolremove(Elem&)=0;//刪除當(dāng)前元素virtualvoidsetStart()=0;//將柵欄置于表頭前virtualvoidsetEnd()=0;//將柵欄置于表尾后virtualvoidprev()=0;//將柵欄向前（左）移動(dòng)一個(gè)元素virtualvoidnext()=0;//將柵欄向后（右）移動(dòng)一個(gè)元素virtualintleftLength()const=0;//返回左邊部分的元素個(gè)數(shù)virtualintrightLength()const=0;//返回左邊部分的元素個(gè)數(shù)virtualboolsetPos(intpos)=0;//返回柵欄在表中的位置virtualboolgetValue(Elem&)const=0;//返回當(dāng)前元素的值virtualvoidprint()const=0;//輸出線性表中元素序列｝；線性表的ADT舉例1.線性表:<12|32,15>MyList.insert(99);

結(jié)果:<12|99,32,15>2.線性表循環(huán)獲得每個(gè)元素的值:for(MyList.setStart();MyList.getValue(it);MyList.next())DoSomething(it);3.在線性表中查找元素值k，找到返回True，未找到返回False。boolfind(List<int>&L,intK){ intit; for(L.setStart();L.getValue(it);L.next()) if(K==it)returntrue;//Foundit returnfalse;//Notfound}4.1.1順序表的實(shí)現(xiàn)

線性表的兩種實(shí)現(xiàn)方法–順序表(又稱順序存儲(chǔ)結(jié)構(gòu)的線性，array-basedlist,sequentiallist)和鏈表(又稱鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表，Linkedlist)順序存儲(chǔ)結(jié)構(gòu)（向量式的存儲(chǔ)結(jié)構(gòu)，順序分配）的基本特點(diǎn)：(1)線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的。(2)線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放。邏輯上相鄰的兩個(gè)元素在存儲(chǔ)空間中是相鄰的。利用元素存儲(chǔ)的位置關(guān)系反映元素之間的邏輯關(guān)系。

通常用一個(gè)一維數(shù)組來(lái)表示線性表的順序存儲(chǔ)空間?？梢酝ㄟ^(guò)簡(jiǎn)單計(jì)算得到任意元素的存儲(chǔ)地址：

ADR(ai)=ADR(a1)+(i-1)*k其中，k為每一個(gè)元素占的字節(jié)數(shù)，i為元素在線性表中的序號(hào)。思考:順序表中插入和刪除一個(gè)元素的過(guò)程和時(shí)間代價(jià)?順序表的插入操作時(shí)間代價(jià)Θ(n)//在當(dāng)前位置（柵欄右邊第1個(gè)元素處）插入一個(gè)新元素template<classElem>boolAList<Elem>::insert(constElem&item){if(listSize==maxSize)returnfalse;//存儲(chǔ)空間已滿//從線性表尾到插入處，每個(gè)元素向右移動(dòng)一個(gè)存儲(chǔ)單元for(inti=listSize;i>fence;i--)listArray[i]=listArray[i-1];listArray[fence]=item;//插入新元素listSize++;//Incrementlistsizereturntrue;}討論：在實(shí)際應(yīng)用中，順序表有何優(yōu)點(diǎn)和缺點(diǎn)，適宜用于何種情況，不適宜用于何種情況？?jī)?yōu)點(diǎn)缺點(diǎn)結(jié)構(gòu)簡(jiǎn)單2.運(yùn)算方便3.存儲(chǔ)空間利用效率高插入和刪除需移動(dòng)大量數(shù)據(jù)元素，時(shí)間代價(jià)大。容量不易擴(kuò)充。存儲(chǔ)空間分配困難：（1）靜態(tài)分配：存儲(chǔ)空間利用效率低。（2）動(dòng)態(tài)分配：每次重新分配需移動(dòng)大量數(shù)據(jù)元素。結(jié)論：只適合小線性表、長(zhǎng)度和數(shù)據(jù)元素不變化的線性表。算法編程課堂練習(xí)

對(duì)一個(gè)長(zhǎng)度為n順序表（用一維數(shù)組V表示順序表的存儲(chǔ)空間），要求將元素x和它后一個(gè)單元的元素交換，可用的中間變量為T(mén)。

寫(xiě)出相應(yīng)的算法程序。ProcedureEXCHANE(V,n,x)IF(n<2)thenreturnfalse;//無(wú)法完成交換操作，返回i=1Dowhile(V(i)≠xandi<n)//搜索線性表元素x i=i+1enddoIf(i>=n)thenreturnfalse;//無(wú)法完成交換操作，返回T=V(i)//交換x和其后單元的元素V(i)=V(i+1)V(i+1)=TReturn第3章3.11題答案3.11(a)

(b)

因此

得

4.1.2鏈表

每一個(gè)數(shù)據(jù)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)存儲(chǔ)單元，占據(jù)一小塊存儲(chǔ)空間，稱為存儲(chǔ)結(jié)點(diǎn)，簡(jiǎn)稱結(jié)點(diǎn)。每個(gè)存儲(chǔ)結(jié)點(diǎn)由兩部分組成：1)數(shù)據(jù)域（element域）：存放數(shù)據(jù)元素值。2）指針域（next域）：存放指針（數(shù)據(jù)元素在線性表中的邏輯位置）。通常指向該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。

特點(diǎn)：（1）物理上無(wú)序：存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素間的邏輯關(guān)系可以不一致。（2）邏輯上有序：指針域確定數(shù)據(jù)元素之間的邏輯關(guān)系。（3）用頭指針HEAD指向第一個(gè)數(shù)據(jù)元素，用最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭眨?或NULL）表示線性鏈表的結(jié)束。

鏈表的實(shí)現(xiàn)示例單元地址Element域Next域12382201317441195121063097142810592271015011120Head鏈表的插入三個(gè)重要指針：head、tail、fence變量leftcnt和rightcnt分別保存左右兩部分的長(zhǎng)度。//在柵欄位置處插入一個(gè)新元素template<classElem>boolLList<Elem>::insert(constElem&item){fence->next=newLink<Elem>(item,fence->next);if(tail==fence)tail=fence->next;rightcnt++;returntrue;}問(wèn)題：當(dāng)鏈表為空，沒(méi)有元素可供head，tail和fence來(lái)指向，當(dāng)鏈表左邊部分為空時(shí)，fence不能指向任何元素。解決方法：增加表頭結(jié)點(diǎn)。算法編程練習(xí)

一個(gè)鏈表長(zhǎng)度為n，頭指針為head，用兩個(gè)同樣大小的一維數(shù)組V(1:m)和Next(1:m)分別保存該鏈表各結(jié)點(diǎn)的數(shù)據(jù)域值和指針域值。請(qǐng)編程實(shí)現(xiàn):在鏈表中元素值為x的結(jié)點(diǎn)之前插入一個(gè)新元素。新元素值為b，數(shù)組下標(biāo)為p。

提示：不但要考慮一般情況下操作，還要考慮特殊情況下的操作。ProcedureInsert(V,next,x,b,p) V(p)=b//如果鏈表為空if(head==NULL)return;//在第一個(gè)結(jié)點(diǎn)前插入

if(V(head)==x){next(p)=head;head=p;return}//尋找值為x結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn),該結(jié)點(diǎn)地址保存在q中

q=head

while((next(q)!=NULL)&&(((V(next(q))!=x))q=next(q)if(next(q)==NULL)returnfalse;//沒(méi)有找到x//將結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后next(p)=next(q);next(q)=pReturn算法編程練習(xí)

一個(gè)鏈表長(zhǎng)度為n，頭指針為head，用兩個(gè)同樣大小的一維數(shù)組V(1:m)和Next(1:m)分別保存該鏈表各結(jié)點(diǎn)的數(shù)據(jù)域值和指針域值。請(qǐng)編程實(shí)現(xiàn):在鏈表中元素值為x的結(jié)點(diǎn)之后插入一個(gè)新元素。新元素值為b，數(shù)組下標(biāo)為p。ProcedureInsert(V,next,x,b,p) V(p)=b//如果鏈表為空if(head==NULL)return;//尋找值為x結(jié)點(diǎn),該結(jié)點(diǎn)地址保存在q中

q=head;

while((next(q)!=NULL)&&(((V(q)!=x))q=next(q);if((next(q)==NULL)&&(V(q)!=x))returnfalse;//沒(méi)有找到xif((next(q)==NULL)&&(V(q)==x))//x在鏈表尾next(q)=p,next(p)=NULL;//將結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后next(p)=next(q);next(q)=pReturn鏈表的刪除操作可利用空間表鏈表插入和刪除操作取得空結(jié)點(diǎn)和回收刪除的結(jié)點(diǎn)對(duì)存儲(chǔ)空間合理的存儲(chǔ)分配和回收機(jī)制語(yǔ)言編譯器的效率不高可利用空間表(freelist)插入一個(gè)新結(jié)點(diǎn)到鏈表前,首先從可利用空間表中取走一個(gè)結(jié)點(diǎn)。刪除一個(gè)鏈表上的結(jié)點(diǎn)后，要將刪除的結(jié)點(diǎn)放到可利用空間表的首端。4.1.4元素的表示

1.順序表和鏈表中的元素是存儲(chǔ)數(shù)據(jù)元素的一份拷貝(副本)還是存儲(chǔ)指向數(shù)據(jù)元素的指針?

建議:數(shù)據(jù)元素大而且重復(fù)多,存儲(chǔ)數(shù)據(jù)元素指針.2.是否要求線性表中元素類型相同?

根據(jù)應(yīng)用選擇元素類型是固定還是不同.3.當(dāng)線性表被刪除或調(diào)用Clear函數(shù)(回收)時(shí),如何處理表中對(duì)象占用的內(nèi)存?

注意:如果表中元素是對(duì)象的指針,就可能刪除指向?qū)ο蟮闹羔?從而使對(duì)象占用的內(nèi)存變成不可訪問(wèn)的(懸掛引用).?4.1.5雙鏈表單鏈表只允許從一個(gè)結(jié)點(diǎn)訪問(wèn)它的后繼結(jié)點(diǎn)特點(diǎn)（與單鏈表比）：優(yōu)點(diǎn)：可從任何一個(gè)結(jié)點(diǎn)出發(fā)，訪問(wèn)其它所有結(jié)點(diǎn)。缺點(diǎn)：占用更多空間。雙鏈表:每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，左指針指向其前件結(jié)點(diǎn)；右指針指向其后件結(jié)點(diǎn)。雙鏈表的插入操作

雙鏈表的刪除操作

編程練習(xí)

一個(gè)雙鏈表長(zhǎng)度為n，頭指針為head，用三個(gè)同樣大小的一維數(shù)組V(1:m)、LNext(1:m)和RNext(1:m)分別保存該鏈表各結(jié)點(diǎn)的數(shù)據(jù)域值和左、右指針域值。請(qǐng)用C語(yǔ)言編程實(shí)現(xiàn):

1.在鏈表中元素值為x的結(jié)點(diǎn)之后插入一個(gè)新元素。新元素值為b，數(shù)組下標(biāo)為p。

2.刪除鏈中元素值為x的結(jié)點(diǎn)。注：假設(shè)此雙鏈表中值為x的結(jié)點(diǎn)最多只有一個(gè)。4.2字典ADT

描述用于一個(gè)簡(jiǎn)單數(shù)據(jù)庫(kù)的接口，稱為字典。字典將定義為一個(gè)ADT，它提供在數(shù)據(jù)庫(kù)存儲(chǔ)、查找和刪除記錄的功能。常用操作：記錄檢索(find)：通過(guò)比較關(guān)鍵碼，返回匹配的記錄。插入記錄(insert)：插入新記錄。刪除記錄(remove)：刪除指定關(guān)鍵碼的記錄。刪除任意記錄(removeAny)：刪除任意一條（如最后一條）記錄?？蓪?shí)現(xiàn)字典的數(shù)據(jù)結(jié)構(gòu)：

4.3棧

棧：一種特殊的線性表。其插入與刪除只在一端進(jìn)行。符合“先進(jìn)后出，后進(jìn)先出”的原則，允許插入和刪除的一端稱為棧頂，不允許插入和刪除的一端稱為棧底。通常用棧項(xiàng)指針top來(lái)指向棧項(xiàng)，用棧底指針bottom來(lái)指向棧底。元素的插入稱為壓入或入棧，元素的刪除稱為彈出或退棧。

4.3.1順序棧程序設(shè)計(jì)中，用一維數(shù)組作為棧的順序存儲(chǔ)空間。為使用方便，通常棧頂指針指向?？臻g的高地址一端。棧頂指針指向棧中第一個(gè)空閑位置。棧的基本運(yùn)算：1、入棧運(yùn)算2、退棧運(yùn)算3、讀棧項(xiàng)元素。4.3.2鏈?zhǔn)綏２捎面準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧。通常用來(lái)收集計(jì)算機(jī)存儲(chǔ)空間中所有空閑的存儲(chǔ)結(jié)點(diǎn)，即可利用空間表。4.3.3順序棧與鏈?zhǔn)綏５谋容^1.基本操作時(shí)間代價(jià)的比較基本操作時(shí)間代價(jià)入棧運(yùn)算退棧運(yùn)算讀棧項(xiàng)元素順序棧鏈?zhǔn)綏?.存儲(chǔ)空間利用的比較討論！4.3.4遞歸的實(shí)現(xiàn)棧的最廣泛應(yīng)用：子程序調(diào)用時(shí)將有關(guān)子程序的必要信息壓入到一個(gè)棧中子程序調(diào)用結(jié)束后，再將信息從棧中彈出。采用棧，遞歸調(diào)用（不是全部）可以用迭代來(lái)代替。4.4隊(duì)列隊(duì)列：符合“先進(jìn)先出，后進(jìn)后出”的原則，在一端進(jìn)行插入，在另一端進(jìn)行刪除的線性表。如消息映射隊(duì)列。例：排隊(duì)，自動(dòng)流水線上裝配部件。計(jì)算機(jī)操作系統(tǒng)利用隊(duì)列管理多個(gè)用戶程序：消息隊(duì)列。允許插入的一端稱為隊(duì)尾，用尾指針（rear）指向；允許刪除的一端稱為隊(duì)首，用頭指針(front)指向。隊(duì)尾插入元素稱為入隊(duì)操作，隊(duì)首刪除元素稱為出隊(duì)操作。4.4.1順序隊(duì)列順序隊(duì)列實(shí)現(xiàn)上的困難：1.要求隊(duì)列中n個(gè)元素都存儲(chǔ)在數(shù)組的前n個(gè)單元中。（1）0號(hào)單元存儲(chǔ)隊(duì)尾元素。刪除元素的時(shí)間代價(jià)：Θ（1）插入新元素的時(shí)間代價(jià)：Θ（n）（1）0號(hào)單元存儲(chǔ)隊(duì)首元素。插入新元素的時(shí)間代價(jià)：Θ（1）刪除元素的時(shí)間代價(jià)：Θ（n）2.不要求隊(duì)列中n個(gè)元素都必須存儲(chǔ)在數(shù)組的前n個(gè)單元中。刪除元素的時(shí)間代價(jià)：Θ（1）插入新元素的時(shí)間代價(jià)：Θ（1）但如果隊(duì)列不斷地插入和刪除元素后，整個(gè)隊(duì)列向數(shù)組中編號(hào)較高的位置移動(dòng)。解決方法：循環(huán)隊(duì)列思考：一維數(shù)組中如何實(shí)現(xiàn)循環(huán)隊(duì)列。？循環(huán)隊(duì)列中如何區(qū)分隊(duì)列空和隊(duì)列滿例1：隊(duì)列中只有一個(gè)元素，位于單元m。front=m，rear＝m。刪除該元素，front=front+1=m+1=rear+1隊(duì)列空時(shí)，rear比f(wàn)ront小1。例2：循環(huán)隊(duì)列如右示，只有一個(gè)空閑單元m。此時(shí)：front=m+1,rear=m-1若插入一個(gè)新元素，則rear=rear+1=m即隊(duì)列滿時(shí)，rear比f(wàn)ront小1。解決辦法：1、設(shè)置標(biāo)志區(qū)別隊(duì)列空或滿。2、以尾指針追上頭指針作為隊(duì)列滿的條件。3、記錄元素的數(shù)量。4.4.2鏈?zhǔn)疥?duì)列4.4.3順序隊(duì)列和鏈?zhǔn)疥?duì)列的比較表達(dá)式計(jì)算21+3*52/(4+18)-3^2/4=?要求：從左到右只需一次掃描表達(dá)式。自動(dòng)區(qū)分運(yùn)算符和運(yùn)算數(shù)。自動(dòng)根據(jù)運(yùn)算符的優(yōu)先級(jí)確定計(jì)算順序。

表達(dá)式計(jì)算21+3*52/(4+18)-3^2/4;運(yùn)算符和優(yōu)先級(jí)：低＋－

×/高^(guò)特殊：()

？如何判斷山峰利用棧實(shí)現(xiàn)表達(dá)式計(jì)算21+3*52/(4+18)-3^2/4;規(guī)則：在表達(dá)式最后加一個(gè)結(jié)束符；將結(jié)束符;看作最低優(yōu)先級(jí)。設(shè)置兩個(gè)棧：運(yùn)算符棧，暫存表達(dá)式處理過(guò)程中的運(yùn)算符。運(yùn)算數(shù)棧，暫存表達(dá)式處理過(guò)程中的運(yùn)算數(shù)。首先將結(jié)束符;直接壓入運(yùn)算符棧