數據結構與算法分析

APracticalIntroductionto

DataStructuresandAlgorithmAnalysis

陳星

第4章線性表、棧和隊列數據結構：相互有關聯的數據元素的集合。反映

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

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

線性表ADT抽象數據類型是指數據結構作為一個軟件組件的實現。通過ADT掌握數據結構的實現和操作。

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

結果:<12|99,32,15>2.線性表循環獲得每個元素的值: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順序表的實現

線性表的兩種實現方法–順序表(又稱順序存儲結構的線性，array-basedlist,sequentiallist)和鏈表(又稱鏈式存儲結構的線性表，Linkedlist)順序存儲結構（向量式的存儲結構，順序分配）的基本特點：(1)線性表中所有元素所占的存儲空間是連續的。(2)線性表中各數據元素在存儲空間中是按邏輯順序依次存放。邏輯上相鄰的兩個元素在存儲空間中是相鄰的。利用元素存儲的位置關系反映元素之間的邏輯關系。

通常用一個一維數組來表示線性表的順序存儲空間。可以通過簡單計算得到任意元素的存儲地址：

ADR(ai)=ADR(a1)+(i-1)*k其中，k為每一個元素占的字節數，i為元素在線性表中的序號。思考:順序表中插入和刪除一個元素的過程和時間代價?順序表的插入操作時間代價Θ(n)//在當前位置（柵欄右邊第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;}討論：在實際應用中，順序表有何優點和缺點，適宜用于何種情況，不適宜用于何種情況？優點缺點結構簡單2.運算方便3.存儲空間利用效率高插入和刪除需移動大量數據元素，時間代價大。容量不易擴充。存儲空間分配困難：（1）靜態分配：存儲空間利用效率低。（2）動態分配：每次重新分配需移動大量數據元素。結論：只適合小線性表、長度和數據元素不變化的線性表。算法編程課堂練習

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

寫出相應的算法程序。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鏈表

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

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

鏈表的實現示例單元地址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;}問題：當鏈表為空，沒有元素可供head，tail和fence來指向，當鏈表左邊部分為空時，fence不能指向任何元素。解決方法：增加表頭結點。算法編程練習

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

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

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

q=head

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

一個鏈表長度為n，頭指針為head，用兩個同樣大小的一維數組V(1:m)和Next(1:m)分別保存該鏈表各結點的數據域值和指針域值。請編程實現:在鏈表中元素值為x的結點之后插入一個新元素。新元素值為b，數組下標為p。ProcedureInsert(V,next,x,b,p) V(p)=b//如果鏈表為空if(head==NULL)return;//尋找值為x結點,該結點地址保存在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;//將結點p插入到結點q之后next(p)=next(q);next(q)=pReturn鏈表的刪除操作可利用空間表鏈表插入和刪除操作取得空結點和回收刪除的結點對存儲空間合理的存儲分配和回收機制語言編譯器的效率不高可利用空間表(freelist)插入一個新結點到鏈表前,首先從可利用空間表中取走一個結點。刪除一個鏈表上的結點后，要將刪除的結點放到可利用空間表的首端。4.1.4元素的表示

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

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

根據應用選擇元素類型是固定還是不同.3.當線性表被刪除或調用Clear函數(回收)時,如何處理表中對象占用的內存?

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

雙鏈表的刪除操作

編程練習

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

1.在鏈表中元素值為x的結點之后插入一個新元素。新元素值為b，數組下標為p。

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

描述用于一個簡單數據庫的接口，稱為字典。字典將定義為一個ADT，它提供在數據庫存儲、查找和刪除記錄的功能。常用操作：記錄檢索(find)：通過比較關鍵碼，返回匹配的記錄。插入記錄(insert)：插入新記錄。刪除記錄(remove)：刪除指定關鍵碼的記錄。刪除任意記錄(removeAny)：刪除任意一條（如最后一條）記錄。可實現字典的數據結構：

4.3棧

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

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

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

×/高^特殊：()

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