中北大學(xué) 機械CADCAM技術(shù) 第二章 機械CAD、CAM常用的數(shù)據(jù)結(jié)構(gòu)

1、1. 理解和掌握有關(guān)數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念；理解和掌握有關(guān)數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念；2. 熟練掌握線形表存儲結(jié)構(gòu)和相關(guān)操作方法；熟練掌握線形表存儲結(jié)構(gòu)和相關(guān)操作方法；3. 掌握棧、隊列、樹數(shù)據(jù)結(jié)構(gòu)的運算方法。掌握棧、隊列、樹數(shù)據(jù)結(jié)構(gòu)的運算方法。第一節(jié)第一節(jié) 基本概念基本概念第二節(jié)第二節(jié) 線形表線形表第三節(jié)第三節(jié) 棧、隊列和數(shù)組棧、隊列和數(shù)組第四節(jié)第四節(jié) 樹結(jié)構(gòu)樹結(jié)構(gòu)本本章章內(nèi)內(nèi)容容機械CAD/CAM課程教案教教學(xué)學(xué)目目的的1. 數(shù)據(jù)數(shù)據(jù)(data) 是對客觀事物的符號表示，是指所有能輸入到計算是對客觀事物的符號表示，是指所有能輸入到計算 機內(nèi)并被計算機處理的符號的總稱。機內(nèi)并被計算機處理的符號的總稱。2

2、. 數(shù)據(jù)元素數(shù)據(jù)元素(data element) 是數(shù)據(jù)的基本單位，是數(shù)據(jù)這個集合中相對獨立的個體。是數(shù)據(jù)的基本單位，是數(shù)據(jù)這個集合中相對獨立的個體。3. 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)(The logical structure of the data) 是指數(shù)據(jù)之間的邏輯關(guān)系。是指數(shù)據(jù)之間的邏輯關(guān)系。表 學(xué)生成績表學(xué)號姓名計算機導(dǎo)論高等數(shù)學(xué)大學(xué)物理平均成績1102044401丁一809085851102044402馬二756878741102044403張三908593891102044404李四708486801102044405王五827866754.數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)(The

3、 physical structure of the data ) 是數(shù)據(jù)元素和它們之間的關(guān)系在計算機中的存儲表示。是數(shù)據(jù)元素和它們之間的關(guān)系在計算機中的存儲表示。 計算機處理信息的最小單位叫做計算機處理信息的最小單位叫做位位(bit)，一個位表示一個二，一個位表示一個二進制的數(shù)。進制的數(shù)。 若干位的組合形成一個位若干位的組合形成一個位串串(string) 。用一個位串表示一個數(shù)。用一個位串表示一個數(shù)據(jù)元素，稱這樣的位串為一個據(jù)元素，稱這樣的位串為一個結(jié)點結(jié)點(node) 。6. 數(shù)據(jù)運算數(shù)據(jù)運算(data operation) 是指對數(shù)據(jù)進行的各種操作。是指對數(shù)據(jù)進行的各種操作。5. 數(shù)據(jù)類

4、型數(shù)據(jù)類型(data type) 是程序設(shè)計語言提供的變量類別。是程序設(shè)計語言提供的變量類別。7.數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(data structure)數(shù)據(jù)結(jié)構(gòu)非線性結(jié)構(gòu)數(shù)據(jù)存儲結(jié)構(gòu)數(shù)據(jù)運算數(shù)據(jù)邏輯結(jié)構(gòu)線性結(jié)構(gòu)線性表隊列棧網(wǎng)狀結(jié)構(gòu)樹結(jié)構(gòu)鏈式存儲順序存儲 插入， 刪除， 更新， 檢索， 排序， 數(shù)學(xué)運算， 是按某種邏輯結(jié)構(gòu)組織起來，按一定的存儲表示方是按某種邏輯結(jié)構(gòu)組織起來，按一定的存儲表示方式把組織好的數(shù)據(jù)存儲到計算機中，并對之定義一系列式把組織好的數(shù)據(jù)存儲到計算機中，并對之定義一系列操作運算的數(shù)據(jù)的集合。操作運算的數(shù)據(jù)的集合。 p線性表線性表n(n0)個數(shù)據(jù)元素按前驅(qū)后繼關(guān)系個數(shù)據(jù)元素按前驅(qū)后繼關(guān)

5、系排成的有限序列。排成的有限序列。同一表中的數(shù)據(jù)元素的類型必須相同；同一表中的數(shù)據(jù)元素的類型必須相同；除了第一個和最后一個數(shù)據(jù)元素外，每個數(shù)據(jù)元除了第一個和最后一個數(shù)據(jù)元素外，每個數(shù)據(jù)元素有且只有一個直接前趨，有且只有一個直接后繼；素有且只有一個直接前趨，有且只有一個直接后繼；如工資表、學(xué)生名冊。如工資表、學(xué)生名冊。線性表中數(shù)據(jù)元素的個數(shù)定義為線性表的長度。線性表中數(shù)據(jù)元素的個數(shù)定義為線性表的長度。p線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu) 順序存儲就是用一組連續(xù)的存儲單元，按照數(shù)據(jù)元素順序存儲就是用一組連續(xù)的存儲單元，按照數(shù)據(jù)元素的邏輯順序的邏輯順序依次存放依次存放。 假定每個數(shù)據(jù)元素占用假

6、定每個數(shù)據(jù)元素占用L個存儲單元，每個數(shù)據(jù)元素個存儲單元，每個數(shù)據(jù)元素第第1個單元的存儲位置為該數(shù)據(jù)元素的存儲位置，若第個單元的存儲位置為該數(shù)據(jù)元素的存儲位置，若第1個個數(shù)據(jù)元素的存儲化置為數(shù)據(jù)元素的存儲化置為b，則第，則第i個數(shù)據(jù)元素的存儲位置為個數(shù)據(jù)元素的存儲位置為 Loc(ai)b十十(i1)Lp線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)特點：特點：1）有序性；）有序性；2）均勻性。）均勻性。操作：操作：1）建表；）建表； 2）訪問；）訪問； 3）修改；）修改； 4）刪除；）刪除； 5）插入。）插入。刪除或插入刪除或插入運算時，數(shù)運算時，數(shù)據(jù)移動量大，據(jù)移動量大，運算時間長。運算時間長。順序

7、表類型定義順序表類型定義#defineListSize100/表空間的大小可根據(jù)實際需要而定，這里假設(shè)為100typedefintDataType;/DataType的類型可根據(jù)實際情況而定，這里假設(shè)為inttypedefstructDataTypedataListSize；/向量data用于存放表結(jié)點intlength；/當前的表長度SeqList； 順序表上實現(xiàn)的基本運算順序表上實現(xiàn)的基本運算（1）表的初始化voidInitList（SeqList*L）順序表的初始化即將表的長度置為0L-length=0；（2）求表長intListLength（SeqList*L）求表長只需返回L-len

8、gthreturnL-length;（3）取表中第i個結(jié)點DataTypeGetNode（L，i）取表中第i個結(jié)點只需返回和L-datai-1即可if(iL-length-1)Error(positionerror)；returnL-datai-1；線性表插入運算線性表插入運算：p線性表的鏈式存儲結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)特點：特點：1）存儲單元可以不連續(xù)、動態(tài)分配存儲空間；）存儲單元可以不連續(xù)、動態(tài)分配存儲空間； 2）存儲結(jié)點有兩種域：數(shù)據(jù)域、指針域。）存儲結(jié)點有兩種域：數(shù)據(jù)域、指針域。單向鏈表單向鏈表 雙向鏈表雙向鏈表循環(huán)鏈表循環(huán)鏈表單鏈表類型描述單鏈表類型描述typedefcharData

9、Type;/假設(shè)結(jié)點的數(shù)據(jù)域類型為字符typedefstructnode/結(jié)點類型定義DataTypedata;/結(jié)點的數(shù)據(jù)域structnode*next;/結(jié)點的指針域ListNode;typedefListNode*LinkList;ListNode*p;LinkListhead; 生成結(jié)點變量的標準函數(shù)生成結(jié)點變量的標準函數(shù) p=(ListNode*)malloc(sizeof(ListNode)；/函數(shù)malloc分配一個類型為ListNode的結(jié)點變量的空間,并將其首地址放入指針變量p中釋放結(jié)點變量空間的標準函數(shù)釋放結(jié)點變量空間的標準函數(shù) free(p)；/釋放p所指的結(jié)點變量空間

10、結(jié)點分量的訪問結(jié)點分量的訪問 利用結(jié)點變量的名字*p訪問結(jié)點分量方法一：(*p).data和(*p).next方法二：p-data和p-next 指針變量指針變量p和結(jié)點變量和結(jié)點變量*p的關(guān)系的關(guān)系 指針變量p的值結(jié)點地址結(jié)點變量*p的值結(jié)點內(nèi)容(*p).data的值p指針所指結(jié)點的data域的值(*p).next的值*p后繼結(jié)點的地址*(*p).next)*p后繼結(jié)點p單向鏈表的操作單向鏈表的操作操作：操作：1）建表；）建表； 2）訪問；）訪問； 3）修改；）修改； 4）刪除；）刪除； 5）插入。）插入。p建表建表鏈表插入操作運算步驟：申請新結(jié)點存儲空間；將待插入元素M存放在新增結(jié)點數(shù)據(jù)域

11、；新增結(jié)點指針鏈接。 p訪問訪問p查找查找p修改修改p刪除刪除p插入插入p雙向鏈表雙向鏈表p雙向鏈表的操作雙向鏈表的操作1）建表）建表p建表建表p查找查找p修改修改p刪除刪除p插入插入p鏈式存儲相對于順序存儲的特點：鏈式存儲相對于順序存儲的特點：(1)刪除或插入運算速度快，因為刪除或插入運算過程中數(shù)刪除或插入運算速度快，因為刪除或插入運算過程中數(shù)據(jù)并不移動；據(jù)并不移動；(2)無需事先分配存儲空間，以免有些空間不能充分利用；無需事先分配存儲空間，以免有些空間不能充分利用；(3)表的容量易于擴充；表的容量易于擴充；(4)按邏輯順序進行查找的速度慢；按邏輯順序進行查找的速度慢；(5)比相等長度的順序

12、存儲多占用作為指針域的存儲空間。比相等長度的順序存儲多占用作為指針域的存儲空間。線性表線性表順序存儲與順序存儲與鏈式鏈式存儲結(jié)構(gòu)比較存儲結(jié)構(gòu)比較順序存儲順序存儲：優(yōu)點：結(jié)構(gòu)均勻，便于數(shù)據(jù)元素訪問和修改操作；不足：刪除插入大量數(shù)據(jù)元素需移動，運算效率低。應(yīng)用：多用于查找頻繁、很少增刪的場合。鏈式存儲鏈式存儲：優(yōu)點：刪除插入效率高，不需數(shù)據(jù)元素移動，不需 事先分配存儲空間，存儲空間利用充分。不足：搜索效率低，需從頭結(jié)點順次搜尋。 應(yīng)用多用于事先難以確定容量，頻繁增、刪場合。p棧棧p棧的結(jié)構(gòu)棧的結(jié)構(gòu)(1)棧的邏輯結(jié)構(gòu)棧的邏輯結(jié)構(gòu) 線形表：后進先出線形表：后進先出(2)棧的存儲結(jié)構(gòu)棧的存儲結(jié)構(gòu) 一般采

13、用順序存儲結(jié)構(gòu)一般采用順序存儲結(jié)構(gòu) 棧的定義棧的定義 棧棧(Stack)(Stack)是限制在表的一端進行插入和刪除運算是限制在表的一端進行插入和刪除運算的線性表，通常稱插入、刪除的這一端為棧頂?shù)木€性表，通常稱插入、刪除的這一端為棧頂(Top)(Top)，另一端為棧底另一端為棧底(Bottom).(Bottom).當表中沒有元素時稱為當表中沒有元素時稱為空?？諚！?假設(shè)棧假設(shè)棧S=(aS=(a1 1，a a2 2，a a3 3，aan n) )，則，則a a1 1稱為棧底元素，稱為棧底元素，a an n為棧為棧頂元素頂元素。棧中元素按。棧中元素按a a1 1，a a2 2，a a3 3，a a

14、n n的次序進的次序進棧，退棧的第一個元素應(yīng)為棧頂元素。換句話說，棧的棧，退棧的第一個元素應(yīng)為棧頂元素。換句話說，棧的修改是按后進先出的原則進行的。因此，棧稱為修改是按后進先出的原則進行的。因此，棧稱為后進先后進先出表（出表（LIFOLIFO）。棧：棧：限定只能在表的一端進行插入和刪除的特殊的線性表限定只能在表的一端進行插入和刪除的特殊的線性表. . 設(shè)棧設(shè)棧s=s=（a a1 1，a a2 2，. . . ,a. . . ,ai i，. . . . . . ，a an n），其中其中a a1 1是是棧底棧底元素，元素， a an n是是棧頂棧頂元素。元素。棧頂（棧頂（top)top)：允許插

15、入和刪除的一端；允許插入和刪除的一端； 棧頂?shù)漠斍拔恢糜蓷ｍ斨羔樀奈恢弥甘酒髦甘尽ｍ數(shù)漠斍拔恢糜蓷ｍ斨羔樀奈恢弥甘酒髦甘?。棧底（棧底（bottom):bottom):不允許插入和刪除的一端。不允許插入和刪除的一端。進?；蛉霔＃哼M?；蛉霔＃簵５牟迦氩僮鳌５牟迦氩僮?。出棧或退棧：出?；蛲藯＃簵５膭h除操作。棧的刪除操作。 a1 a2 . an進棧進棧出棧出棧棧頂棧頂棧底棧底棧的定義棧的定義空棧：空棧：沒有元素的棧沒有元素的棧棧的特性：棧的特性：l先進后出（先進后出（LIFOLIFO），即只能在末端（棧頂）進），即只能在末端（棧頂）進行插、刪的操作行插、刪的操作棧的定義棧的定義棧中的幾種基本操作：

16、棧中的幾種基本操作： 1.1.設(shè)置空棧設(shè)置空棧 初始化：初始化：initStack(S);initStack(S); 清空：清空：emptyStack (S);emptyStack (S); 2. 2.插入一個新的棧頂元素插入一個新的棧頂元素（進棧）（進棧）:push(S,x);:push(S,x); 3. 3.刪除棧頂元素刪除棧頂元素（出棧）（出棧）: pop(S);: pop(S); 4. 4.讀取棧頂元素讀取棧頂元素:getTop(S);:getTop(S); 5. 5.判空棧判空棧:stackEmpty(S);:stackEmpty(S); 6. 6.判滿棧判滿棧:stackFull(

17、S);:stackFull(S); 7. 7.顯示棧中元素顯示棧中元素：stackTraverse(S);stackTraverse(S); 棧的存儲結(jié)構(gòu)棧的存儲結(jié)構(gòu)順序棧順序棧l利用一組地址連續(xù)的存儲單元依次存放自棧底到利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，一般用棧頂?shù)臄?shù)據(jù)元素，一般用一維數(shù)組一維數(shù)組表示表示l必須附設(shè)一個位置指針必須附設(shè)一個位置指針toptop（棧頂指針）來動態(tài)（棧頂指針）來動態(tài)地指示地指示棧棧頂元素頂元素在順序棧中的位置在順序棧中的位置鏈棧鏈棧l采用鏈表作為存儲結(jié)構(gòu)實現(xiàn)的采用鏈表作為存儲結(jié)構(gòu)實現(xiàn)的l必須設(shè)置一個棧頂指針永遠指向棧頂必須設(shè)置一個棧頂指針永

18、遠指向棧頂棧的表示和實現(xiàn)棧的表示和實現(xiàn)一、順序棧一、順序棧 棧的順序存儲結(jié)構(gòu)簡稱為棧的順序存儲結(jié)構(gòu)簡稱為順序棧順序棧，它，它是運算受限的線性表。因此，可用數(shù)組來是運算受限的線性表。因此，可用數(shù)組來實現(xiàn)順序棧。因為棧底位置是固定不變的實現(xiàn)順序棧。因為棧底位置是固定不變的, ,所以可以將棧底位置設(shè)置在數(shù)組的兩端的所以可以將棧底位置設(shè)置在數(shù)組的兩端的任何一個端點；棧頂位置是隨著進棧和退任何一個端點；棧頂位置是隨著進棧和退棧操作而變化的。棧操作而變化的。棧的表示和實現(xiàn)棧的表示和實現(xiàn) 需用一個整型變量需用一個整型變量top來指示當前棧頂?shù)奈粊碇甘井斍皸ｍ數(shù)奈恢茫ǔ７Q置，通常稱top為為棧頂指針棧頂指針

19、。因此，。因此，順序棧的順序棧的類型定義只需將順序表的類型定義中的長度類型定義只需將順序表的類型定義中的長度屬性改為屬性改為top即可。即可。一、順序棧一、順序棧 a1 a2 top順序棧的結(jié)構(gòu)順序棧的結(jié)構(gòu)#define Stack_Size 50#define Stack_Size 50typedef structtypedef structStackElemType elemStack_Size;StackElemType elemStack_Size; / /* *用一維數(shù)組存放自棧底到棧頂?shù)臄?shù)據(jù)元素用一維數(shù)組存放自棧底到棧頂?shù)臄?shù)據(jù)元素* */ / int top; int top; /

20、*附設(shè)一個位置指針附設(shè)一個位置指針top*/SeqStack;SeqStack;一、順序棧一、順序棧 設(shè)設(shè)S S是是SeqStackSeqStack類型的指針變量。若棧底位置在向量類型的指針變量。若棧底位置在向量的低端，即的低端，即s selem0elem0是棧底元素是棧底元素. . 那么：那么： 進棧：進棧：s stoptop加加1 1；退棧：退棧：s stop top 減減1 1； 空棧：空棧：s stoptoptop =stacksize-1top =stacksize-1。 上溢：上溢：當棧滿時再做進棧運算必定產(chǎn)生的空間溢出當棧滿時再做進棧運算必定產(chǎn)生的空間溢出; ;下溢：下溢：當?？?/p>

21、當?？諘r再做退棧運算產(chǎn)生的溢出。時再做退棧運算產(chǎn)生的溢出。 上溢是一種出錯狀態(tài)，應(yīng)該設(shè)法避免之；下溢則可能上溢是一種出錯狀態(tài)，應(yīng)該設(shè)法避免之；下溢則可能是正?，F(xiàn)象，因為棧在程序中使用時，其初態(tài)或終態(tài)都是是正?，F(xiàn)象，因為棧在程序中使用時，其初態(tài)或終態(tài)都是空棧，所以下溢常常用來作為程序控制轉(zhuǎn)移的條件?？諚＃韵乱绯３Ｓ脕碜鳛槌绦蚩刂妻D(zhuǎn)移的條件。一、順序棧一、順序棧設(shè)數(shù)組設(shè)數(shù)組S S是一個順序棧是一個順序棧棧棧S S的最大容量的最大容量stacksize=4 stacksize=4 ，初始狀態(tài)，初始狀態(tài)top=top=1 1 10S42310basetop=top+1stop=xtop 10 25

22、 30S42310topbasex=stoptop=top-1?？諚？?010進棧進棧3030出出棧棧S42310Top=-1top棧滿棧滿 top=stacksize-1 10 25 30 40S42310top=3baseS42310Top=-1top進棧算法進棧算法#define Statck_Size 100#define Statck_Size 100int Push(SeqStack int Push(SeqStack * *S, int x)S, int x) if(S-top=Stack_Size if(S-top=Stack_Size1)1) return 0; return

23、 0; S-top+; S-top+; S-elemS-top=x; S-elemS-top=x; return(1); return(1); a2 a3 a4987654321 a10top一、順序棧一、順序棧進棧算法進棧算法#define Statck_Size 100#define Statck_Size 100int Push(SeqStack int Push(SeqStack * *S, int x)S, int x) if(S-top=Stack_Size if(S-top=Stack_Size1)1) return(0); return(0); S-top+;S-top+; S

24、-elemS-top=x; S-elemS-top=x; return(1); return(1); a2 a3 a4987654321 a10top一、順序棧一、順序棧進棧算法進棧算法#define Statck_Size 100#define Statck_Size 100int Push(SeqStack int Push(SeqStack * *S, int x)S, int x) if(S-top=Stack_Size if(S-top=Stack_Size1)1) return(0); return(0); S-top+; S-top+; S-elemS-top=x;S-elemS

25、-top=x; return(1); return(1); a2 a3 a4987654321 a10topx一、順序棧一、順序棧出棧算法出棧算法： i n t p o p ( S e q S t a c k * S , StackElementType *x) if(S-top= =1) p r i n t f ( “ s t a c k e m p t y ” ) ; return(0); else *x=S-elemS-top; /*返回出返回出棧元素棧元素*/ S-top- -; return(1); 通過指針變量通過指針變量x x，帶回出棧元素，帶回出棧元素 a2 a3 a49876

26、54321 a10top一、順序棧一、順序棧 a2 a3 a4987654321 a10topx出棧算法：出棧算法： i n t p o p ( S e q S t a c k * S , StackElementType *x) if(S-top= =1) p r i n t f ( “ s t a c k e m p t y ” ) ; return(0); else *x=S-elemS-top; /*返回出返回出棧元素棧元素*/ S-top- -; return(1); 一、順序棧一、順序棧為兩個棧申請一個共享的一維數(shù)組空間為兩個棧申請一個共享的一維數(shù)組空間SMSM將兩個棧的棧底分別放

27、在一維數(shù)組的兩端，分別是將兩個棧的棧底分別放在一維數(shù)組的兩端，分別是0 0，M M1 1a a1 1 a a2 2 a a3 3 b b5 5 b b4 4 b b3 3 b b2 2 b b1 10 0M M1 1top0top0top1top1一、順序棧一、順序棧順序棧的共享順序棧的共享共享棧的結(jié)構(gòu)定義共享棧的結(jié)構(gòu)定義a a1 1 a a2 2 a a3 3 b b5 5 b b4 4 b b3 3 b b2 2 b b1 10 0M M1 1top0top0top1top1#define M 100#define M 100typedef structtypedef structStac

28、kElementType elemM;StackElementType elemM; int top2; int top2;DqStack;DqStack;一、順序棧一、順序棧a a1 1 a a2 2 a a3 3 b b5 5 b b4 4 b b3 3 b b2 2 b b1 10 0M M1 1top0top0top1top1判空：判空：top0=-1;top0=-1;top1=M;top1=M;判滿：判滿：top0+1= =top1;top0+1= =top1;共享棧的操作共享棧的操作共享棧的進棧操作共享棧的進棧操作int Push(DqStack int Push(DqStack

29、* *S,StackElementType x,int i)S,StackElementType x,int i)if(S-top0+1= =S-top1) return(0);if(S-top0+1= =S-top1) return(0); switch(i) switch(i) case 0: case 0: S-top0+; S-top0+; S-elemS-top0=x; break; S-elemS-top0=x; break; case 1: case 1: S-top1+; S-top1+; S-elemS-top1=x; break; S-elemS-top1=x; break

30、; default: default: return(0); return(0); return(1); return(1);共享棧的出棧操作共享棧的出棧操作int Pop(DqStack int Pop(DqStack * *S,StackElementType S,StackElementType * *x,int i)x,int i)switch(i)switch(i) case 0: case 0: if(S-top0= =-1) return(0); if(S-top0= =-1) return(0); * *x=S-elemS-top0;x=S-elemS-top0; S-top0

31、- -; break; S-top0- -; break; case 1: case 1: if(S-top1= =M) return(0); if(S-top1= =M) return(0); * *x=S-elemS-top1;x=S-elemS-top1; S-top1- -; break; S-top1- -; break; default: default: return(0); return(0); return(1); return(1);二、鏈棧二、鏈棧棧的鏈式存儲結(jié)構(gòu)稱為棧的鏈式存儲結(jié)構(gòu)稱為鏈棧鏈棧，它是運算，它是運算受限的單鏈表，插入和刪除操作僅限制在表頭受限的單鏈表，插入

32、和刪除操作僅限制在表頭位置上進行位置上進行.由于只能在鏈表頭部進行操作，由于只能在鏈表頭部進行操作，故鏈表沒有必要像單鏈表那樣附加頭結(jié)點。棧故鏈表沒有必要像單鏈表那樣附加頭結(jié)點。棧頂指針就是鏈表的頭指針。頂指針就是鏈表的頭指針。 a1 antop棧底棧底 用指針來實現(xiàn)的棧叫鏈棧。棧的容量事先不用指針來實現(xiàn)的棧叫鏈棧。棧的容量事先不能估計時采用這種存儲結(jié)構(gòu)。能估計時采用這種存儲結(jié)構(gòu)。鏈棧的類型說明如下：鏈棧的類型說明如下：typedef struct Lnodetypedef struct Lnode int data int data； struct Lnode struct Lnode ne

33、xtnext； LnodeLnode， LinkStackLinkStack；toptop頭指針永頭指針永遠指向頭結(jié)點遠指向頭結(jié)點二、鏈棧二、鏈棧進棧算法進棧算法i n t P u s h ( L i n k S t a c k t o p , StackElementType e)Lnode *p; p=(LinkStack)malloc(sizeof(Lnode); p-data=e; p-next=top-next; top-next=p; return (1);a1a2anbasetop棧棧 s s進棧元素進棧元素e e二、鏈棧二、鏈棧進棧算法進棧算法i n t P u s h ( L

34、 i n k S t a c k t o p , StackElementType e)Lnode *p; p=(LinkStack)malloc(sizeof(Lnode); p-data=e; p-next=top-next; top-next=p; return (1); Pa1a2anbasetop二、鏈棧二、鏈棧進棧算法進棧算法i n t P u s h ( L i n k S t a c k t o p , StackElementType e)Lnode *p; p=(LinkStack)malloc(sizeof(Lnode); p-data=e; p-next=top-nex

35、t; top-next=p; return (1); ePa1a2anbasetop二、鏈棧二、鏈棧進棧算法進棧算法i n t P u s h ( L i n k S t a c k t o p , StackElementType e)Lnode *p; p=(LinkStack)malloc(sizeof(Lnode); p-data=e; p-next=top-next; top-next=p; return (1); ePa1a2anbasetop進棧算法進棧算法i n t P u s h ( L i n k S t a c k t o p , StackElementType e)L

36、node *p; p=(LinkStack)malloc(sizeof(Lnode); p-data=e; p-next=top-next; top-next=p; return (1); ePa1a2anbasetop二、鏈棧二、鏈棧出棧算法出棧算法i n t P o p ( L i n k S t a c k t o p , StackElementType *x)Lnode *temp; temp=top-next; if(temp= =NULL) return(0); top-next=temp-next; *x=temp-data; free(temp);棧棧 s s指針變量帶回指針

37、變量帶回出棧元素的值出棧元素的值a1a2anbasetop二、鏈棧二、鏈棧temptempa1a2anbasetop出棧算法出棧算法i n t P o p ( L i n k S t a c k t o p , StackElementType *x)Lnode *temp; temp=top-next; if(temp= =NULL) return(0); top-next=temp-next; *x=temp-data; free(temp);二、鏈棧二、鏈棧temptempa1a2anbasetop出棧算法出棧算法i n t P o p ( L i n k S t a c k t o p

38、 , StackElementType *x)Lnode *temp; temp=top-next; if(temp= =NULL) return(0); top-next=temp-next; *x=temp-data; free(temp);二、鏈棧二、鏈棧temptempa1a2anbasetop出棧算法出棧算法i n t P o p ( L i n k S t a c k t o p , StackElementType *x)Lnode *temp; temp=top-next; if(temp= =NULL) return(0); top-next=temp-next; *x=te

39、mp-data; free(temp);x xa1二、鏈棧二、鏈棧temptempa1a2anbasetop出棧算法出棧算法i n t P o p ( L i n k S t a c k t o p , StackElementType *x)Lnode *temp; temp=top-next; if(temp= =NULL) return(0); top-next=temp-next; *x=temp-data; free(temp);x xa1二、鏈棧二、鏈棧 隊列隊列(Queue)(Queue)也是一種運算受限的線性表。它也是一種運算受限的線性表。它只允許在只允許在表的一端進行插入，而

40、在另一端進行刪除。表的一端進行插入，而在另一端進行刪除。允許刪除的一端允許刪除的一端稱為稱為隊頭隊頭(front)(front)，允許插入的一端稱為，允許插入的一端稱為隊尾隊尾(rear)(rear)。例如：排隊購物。操作系統(tǒng)中的作業(yè)排隊。例如：排隊購物。操作系統(tǒng)中的作業(yè)排隊。 先進入隊列的成員總是先離開隊列。因此隊列亦稱作先進入隊列的成員總是先離開隊列。因此隊列亦稱作先先進先出進先出(First In First Out)(First In First Out)的線性表的線性表，簡稱，簡稱FIFOFIFO表。表。當隊列中沒有元素時稱為當隊列中沒有元素時稱為空隊列空隊列。在空隊列中依次加入。在

41、空隊列中依次加入元素元素a a1 1,a,a2 2,a,an n之后，之后，a a1 1是隊頭元素，是隊頭元素，a an n是隊尾元素。顯然退是隊尾元素。顯然退出隊列的次序也只能是出隊列的次序也只能是a a1 1,a,a2 2,a,an n ，也就是說隊列的修改是，也就是說隊列的修改是依依先進先出先進先出的原則進行的。的原則進行的。2.3 2.3 隊列的定義隊列的定義隊列（隊列（Queue）：限定在表一端插入，在另一端刪除的“先進先出”線性表。a1a2akan-1an入隊出隊隊列數(shù)據(jù)結(jié)構(gòu)隊列數(shù)據(jù)結(jié)構(gòu)循環(huán)循環(huán)隊列隊列 隊列隊列 隊列隊列尾追頭為滿尾追頭為滿頭追尾為空頭追尾為空尾指尾指+1判判斷斷

42、下圖是隊列的示意圖：下圖是隊列的示意圖：出隊出隊入隊入隊隊頭隊頭隊尾隊尾 a a1 1a a2 2a an nn隊尾：在隊列中，允許隊尾：在隊列中，允許插入插入的一端的一端n隊頭：在隊列中，允許隊頭：在隊列中，允許刪除刪除的一端的一端隊列的主要運算隊列的主要運算設(shè)置一個空隊列；設(shè)置一個空隊列；插入一個新的隊尾元素，稱為進隊；插入一個新的隊尾元素，稱為進隊；刪除隊頭元素，稱為出隊；刪除隊頭元素，稱為出隊；讀取隊頭元素；等讀取隊頭元素；等2.3 2.3 隊列的定義隊列的定義隊列的存儲結(jié)構(gòu)隊列的存儲結(jié)構(gòu)（1 1）順序存儲結(jié)構(gòu)）順序存儲結(jié)構(gòu)(a) (a) 線性隊列線性隊列 (b) (b) 循環(huán)隊列循環(huán)

43、隊列（2 2）鏈式存儲結(jié)構(gòu)）鏈式存儲結(jié)構(gòu)隊列的表示和實現(xiàn)隊列的表示和實現(xiàn)隊列的類型定義：隊列的類型定義：#define MAXSIZE 50#define MAXSIZE 50typedef structtypedef structQueueElementType elem MAXSIZE;QueueElementType elem MAXSIZE; int front;int rear; int front;int rear;SeqQueue;SeqQueue;e1,e2e1,e2出隊，出隊，e4e4入隊隊滿入隊隊滿 e1 e2 e3 (b)rearfronte1,e2,e3e1,e2,e3

44、入隊入隊 隊空時，隊空時， 令令rear=front=0rear=front=0，當有新元素入隊時，尾指針加當有新元素入隊時，尾指針加1 1，當有元素出隊時，頭指針加當有元素出隊時，頭指針加1 1。故。故在非空隊列中，在非空隊列中，頭指針頭指針始終指向始終指向隊隊頭元素的位置頭元素的位置，而，而尾指針尾指針始終指向始終指向隊尾元素后一個位置隊尾元素后一個位置rear=front=0(rear=front=0(隊空隊空) )front 3 2 1 0 (a)rearrear=4 (c) e3 e4front隊列的順序存儲隊列的順序存儲 和棧類似，隊列中亦有上溢和下溢現(xiàn)象。和棧類似，隊列中亦有上溢

45、和下溢現(xiàn)象。此外，順序隊列中還存在此外，順序隊列中還存在“假上溢假上溢”（假溢出假溢出）現(xiàn)象。因為在入隊和出隊的操作中，頭尾指針現(xiàn)象。因為在入隊和出隊的操作中，頭尾指針只增加不減小，致使被刪除元素的空間永遠無只增加不減小，致使被刪除元素的空間永遠無法重新利用。因此，盡管隊列中實際的元素個法重新利用。因此，盡管隊列中實際的元素個數(shù)遠遠小于向量空間的規(guī)模，但也可能由于尾數(shù)遠遠小于向量空間的規(guī)模，但也可能由于尾指針巳超出向量空間的上界而不能做入隊操作指針巳超出向量空間的上界而不能做入隊操作。該現(xiàn)象稱為假上溢。該現(xiàn)象稱為假上溢。隊列的順序存儲隊列的順序存儲 為充分利用向量空間?？朔鲜黾偕弦绗F(xiàn)象的方法

46、是為充分利用向量空間?？朔鲜黾偕弦绗F(xiàn)象的方法是將向量空間想象為一個首尾相接的圓環(huán)，并稱這種向量將向量空間想象為一個首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量，存儲在其中的隊列稱為循環(huán)隊列為循環(huán)向量，存儲在其中的隊列稱為循環(huán)隊列Circular Circular Queue)Queue)。在循環(huán)隊列中進行出隊、入隊操作時，頭尾指。在循環(huán)隊列中進行出隊、入隊操作時，頭尾指針仍要加針仍要加1 1，朝前移動。，朝前移動。 只不過當頭尾指針指向向量上界（只不過當頭尾指針指向向量上界（QueueSize-1QueueSize-1）時，）時，其加其加1 1操作的結(jié)果是指向向量的下界操作的結(jié)果是指向向量的下界0

47、 0。這種循環(huán)意義下的加這種循環(huán)意義下的加1 1操作可以描述為：操作可以描述為： if(i+1=QueueSize) i=0;if(i+1=QueueSize) i=0; else i+; else i+;利用模運算可簡化為：利用模運算可簡化為： i=(i+1)%QueueSizei=(i+1)%QueueSize隊列的順序存儲隊列的順序存儲 顯然，因為循環(huán)隊列元素的空間可以被利用，除非向量顯然，因為循環(huán)隊列元素的空間可以被利用，除非向量空間真的被隊列元素全部占用，否則不會上溢。因此，除一空間真的被隊列元素全部占用，否則不會上溢。因此，除一些簡單的應(yīng)用外，真正實用的順序隊列是些簡單的應(yīng)用外，真

48、正實用的順序隊列是循環(huán)隊列循環(huán)隊列。 如圖所示：由于入隊時尾指針向前追趕頭指針，出隊時如圖所示：由于入隊時尾指針向前追趕頭指針，出隊時頭指針向前追趕尾指針，故隊空和隊滿時頭尾指針均相等。頭指針向前追趕尾指針，故隊空和隊滿時頭尾指針均相等。因此，我們無法通過因此，我們無法通過front=rearfront=rear來判斷隊列來判斷隊列“空空”還是還是“滿滿”。 解決此問題的方法至少有三種解決此問題的方法至少有三種： 其一是另設(shè)一個布爾變量以區(qū)別隊列的空和滿；其二是其一是另設(shè)一個布爾變量以區(qū)別隊列的空和滿；其二是少用一個元素的空間，約定入隊前，測試尾指針在循環(huán)意義少用一個元素的空間，約定入隊前，測

49、試尾指針在循環(huán)意義下加下加1 1后是否等于頭指針，若相等則認為隊滿（注意：后是否等于頭指針，若相等則認為隊滿（注意：rearrear所指的單元始終為空）；所指的單元始終為空）；隊列的順序存儲隊列的順序存儲 其三是其三是使用一個計數(shù)器記錄隊列中元素的總數(shù)使用一個計數(shù)器記錄隊列中元素的總數(shù)（實際（實際上是隊列長度）。上是隊列長度）。下面我們用第三種方法實現(xiàn)循環(huán)隊列上的六種基本操作，下面我們用第三種方法實現(xiàn)循環(huán)隊列上的六種基本操作，為此先給出循環(huán)隊列的類型定義。為此先給出循環(huán)隊列的類型定義。 #define QueueSize 100 typedef struct Queuedatatype dat

50、aqueuesize int front， rear; int len; sqqueue;隊列的順序存儲隊列的順序存儲（1）置空隊置空隊 void initqueue(sqqueue *q) qfront=qrear=-1; qlen=0; （2）判斷隊空判斷隊空 int queueempty(sqqueue *q) return qlen=0; （3）判斷隊滿判斷隊滿 int queuefull(sqqueue *q) return qlen=queuesize; 隊列的順序存儲隊列的順序存儲（4 4）入隊入隊 void inqueue(sqqueue void inqueue(sqqueu

51、e * *q,datatype x)q,datatype x) if(queuefull(q) if(queuefull(q) printf(“queue overflow”); printf(“queue overflow”); return; return; q qlen+;len+; q qdataqdataqrear=x;rear=x; q qrear=(qrear=(qrear+1)%queuesize;rear+1)%queuesize; 隊列的順序存儲隊列的順序存儲（5 5）出隊出隊 queuedatatype dequeue(sqqueue queuedatatype dequ

52、eue(sqqueue * *q)q) datatype temp; datatype temp; if(queueempty(q) if(queueempty(q) printf(“queue underflow”); printf(“queue underflow”); return; return; temp=q temp=qdataqdataqfront;front; q qlen-; len-; q qfront=(qfront=(qfront+1)%queuesize;front+1)%queuesize; return temp; return temp; 隊列的順序存儲隊列的順

53、序存儲（6 6）取頭元素取頭元素 queuedatatype queuefront(sqqueue queuedatatype queuefront(sqqueue * *q)q) if(queueempty(q) if(queueempty(q) printf(“queue is empty.”); printf(“queue is empty.”); return(0); return(0); return q return qdataqdataqfront;front; 隊列的順序存儲隊列的順序存儲區(qū)分隊列空與滿另一種方法區(qū)分隊列空與滿另一種方法 少用一個元素的空間，約定入隊前，測試尾指

54、針在少用一個元素的空間，約定入隊前，測試尾指針在循環(huán)意義下加循環(huán)意義下加1 1后是否等于頭指針后是否等于頭指針, ,若相等則認為隊滿若相等則認為隊滿（注意：（注意：rearrear所指的單元始終為空）；所指的單元始終為空）；隊列的順序存儲隊列的順序存儲循環(huán)隊列循環(huán)隊列 rear front 0 1 2 3(3) 隊空隊空隊滿條件隊滿條件：(Q.rear+1)%MAX=Q.front注：實際上為了避免與隊空標注：實際上為了避免與隊空標志沖突，還留有一個空間。志沖突，還留有一個空間。將頭尾連接成將頭尾連接成一個環(huán)，形成一個環(huán)，形成循環(huán)隊列。循環(huán)隊列。(1)1)一般情況一般情況 rear front

55、 0 1 2 3e4e3 (2) 隊滿隊滿 front e3 e4 0 1 2 3 reare5隊列的順序存儲隊列的順序存儲#define MAXSIZE 50#define MAXSIZE 50typedef structtypedef structQueueElementType elementMAXSIZE;QueueElementType elementMAXSIZE; int front;int rear; int front;int rear;SeqQueue;SeqQueue;注意事項：注意事項：1 1、出隊時，頭指針的變化為、出隊時，頭指針的變化為front=(front+1)

56、 mod MAXSIZEfront=(front+1) mod MAXSIZE2 2、入隊時，尾指針的變化為、入隊時，尾指針的變化為rear=(rear+1) mod MAXSIZErear=(rear+1) mod MAXSIZE3 3、凡是遇到指針要發(fā)生變化，頭和尾指針的有效范圍為、凡是遇到指針要發(fā)生變化，頭和尾指針的有效范圍為0,MAXSIZE-10,MAXSIZE-1，所以用取模運算來保證頭尾指針的取值，所以用取模運算來保證頭尾指針的取值循環(huán)隊列的類型定義循環(huán)隊列的類型定義循環(huán)隊列中加入一個元素的算法：循環(huán)隊列中加入一個元素的算法： int EnQueue(SeqQueue int E

57、nQueue(SeqQueue * *Q,int x) Q,int x) Q Q為已有的為已有的循環(huán)隊列循環(huán)隊列將插入將插入的值的值循環(huán)隊列循環(huán)隊列循環(huán)隊列中加入一個元素的算法：循環(huán)隊列中加入一個元素的算法： int EnQueue(SeqQueue *Q,int x) if(Q-rear+1)%MAXSIZE= =Q-front) return(0); else Q-rear=x; Q-rear=(Q-rear+1)%MAXSIZE; return(1); rear front 0 1 2 3e4e3rearrearX X循環(huán)隊列循環(huán)隊列循環(huán)隊列中刪除一個元素的算法：循環(huán)隊列中刪除一個元素的

58、算法：int DeQueue(SeqQueue int DeQueue(SeqQueue * *Q Q，int int * *py) py) 已有的循環(huán)已有的循環(huán)隊列隊列返回刪返回刪除的值除的值的地址的地址循環(huán)隊列循環(huán)隊列循環(huán)隊列中刪除一個元素的算法：循環(huán)隊列中刪除一個元素的算法：int DeQueue(SeqQueue *Q，int *py) if(Q-rear= =Q-front) return(0); else*py=QQ-front; Q-front=(Q-front+1)%MAXSIZE; return(1); rear front 0 1 2 3e4e3frontfront循環(huán)隊列

59、循環(huán)隊列鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu) an a2 a1 Q.frontQ.rear隊頭隊頭隊尾隊尾typedef struct Nodetypedef struct NodeQueueElementType data;QueueElementType data; struct Node struct Node * *next;next;LinkQueueNode;/LinkQueueNode;/* *結(jié)點的定義結(jié)點的定義* */ /typedef structtypedef structLinkQueueNode LinkQueueNode * *front;front; LinkQueueNod

60、e LinkQueueNode * *rear;rear;LinkQueue;/LinkQueue;/* *隊列的定義隊列的定義* */ /注意：注意：隊頭永遠指向頭結(jié)點，隊尾永遠指向最后一個元素。隊頭永遠指向頭結(jié)點，隊尾永遠指向最后一個元素。3.3.2 3.3.2 隊列的表示和實現(xiàn)隊列的表示和實現(xiàn)e a1 a2 anQ.frontQ.rear 鏈隊列添加操作鏈隊列添加操作Q.rearnewNode=(LinkQueueNode newNode=(LinkQueueNode * *) )malloc(sizeof(LinkQueueNode);malloc(sizeof(LinkQueueNo