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

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

APracticalIntroductionto

DataStructuresandAlgorithmAnalysis

陳星

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

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

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

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

線性表ADT設(shè)計的思想：當(dāng)前位置。一個柵欄和兩個分離部分。如：<20,23|12,15>注：當(dāng)前位置的元素（當(dāng)前元素）為柵欄右邊的第1個元素，或右邊部分的第1個元素。線性表的C++抽象類聲明template<classElem>classList{public:virtualvoidclear()=0;//回收元素的存儲空間virtualboolinsert(constElem&)=0;//當(dāng)前位置插入新元素virtualboolappend(constElem&)=0;//表尾插入新元素virtualboolremove(Elem&)=0;//刪除當(dāng)前元素virtualvoidsetStart()=0;//將柵欄置于表頭前virtualvoidsetEnd()=0;//將柵欄置于表尾后virtualvoidprev()=0;//將柵欄向前（左）移動一個元素virtualvoidnext()=0;//將柵欄向后（右）移動一個元素virtualintleftLength()const=0;//返回左邊部分的元素個數(shù)virtualintrightLength()const=0;//返回左邊部分的元素個數(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)獲得每個元素的值: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順序表的實現(xiàn)

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

通常用一個一維數(shù)組來表示線性表的順序存儲空間?？梢酝ㄟ^簡單計算得到任意元素的存儲地址：

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

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

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

(b)

因此

得

4.1.2鏈表

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

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

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

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

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

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

q=head

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

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

q=head;

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

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

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

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

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

雙鏈表的刪除操作

編程練習(xí)

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

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

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

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

4.3棧

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

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

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

×/高^特殊：()

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