數(shù)據(jù)結(jié)構(gòu)課程教案

1、數(shù)據(jù)結(jié)構(gòu)課程教案第一章 緒論教學(xué)目標(biāo)：1 了解數(shù)據(jù)結(jié)構(gòu)中的基本概念2 理解抽象數(shù)據(jù)類型3 了解時間復(fù)雜度和空間復(fù)雜度的分析教學(xué)重點:1. 數(shù)據(jù)結(jié)構(gòu)中的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的分類2. 四種邏輯結(jié)構(gòu)的特點教學(xué)過程:一、常用術(shù)語：1數(shù)據(jù)（Data）數(shù)據(jù)是信息的載體。它能夠被計算機識別、存儲和加工處理，是計算機程序加工的原料。隨著計算機應(yīng)用領(lǐng)域的擴大，數(shù)據(jù)的范疇包括：整數(shù)、實數(shù)、字符串、圖像和聲音等。2數(shù)據(jù)元素（Data Element）數(shù)據(jù)元素是數(shù)據(jù)的基本單位。數(shù)據(jù)元素也稱元素、結(jié)點、頂點、記錄。一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項（也可稱為字段、域、屬性）組成。數(shù)據(jù)項是具有獨立含義的最小標(biāo)識單位。3數(shù)據(jù)結(jié)

2、構(gòu)（Data Structure）數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。數(shù)據(jù)結(jié)構(gòu)一般包括以下三方面內(nèi)容： 數(shù)據(jù)元素之間的邏輯關(guān)系，也稱數(shù)據(jù)的邏輯結(jié)構(gòu)（Logical Structure）； 數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。 數(shù)據(jù)的邏輯結(jié)構(gòu)分類： （1）線性結(jié)構(gòu) 線性結(jié)構(gòu)的邏輯特征是：若結(jié)構(gòu)是非空集，則有且僅有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個直接后繼。即特點為：一對一 線性表是一個典型的線性結(jié)構(gòu)。棧、隊列、串等都是線性結(jié)構(gòu)。 （2）非線性結(jié)構(gòu)非線性結(jié)構(gòu)

3、的邏輯特征是：一個結(jié)點可能有多個直接前趨和直接后繼。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。 包括：樹結(jié)構(gòu)、圖結(jié)構(gòu)。另外還有集合結(jié)構(gòu)（特點為：各元素間無任何關(guān)系）樹結(jié)構(gòu)特點：一對多圖結(jié)構(gòu)特點：多對多 數(shù)據(jù)元素及其關(guān)系在計算機存儲器內(nèi)的表示，稱為數(shù)據(jù)的存儲結(jié)構(gòu)（Storage Structure）； 數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)（亦稱為映象），它依賴于計算機語言。對機器語言而言，存儲結(jié)構(gòu)是具體的。一般，只在高級語言的層次上討論存儲結(jié)構(gòu)。 數(shù)據(jù)的四種基本存儲方法：順序存儲方法、鏈接存儲方法、索引存儲方法、散列存儲方法4數(shù)據(jù)類型（Data Type） 所謂數(shù)據(jù)類型是一個值的集合以

4、及在這些值上定義的一組操作的總稱。通常數(shù)據(jù)類型可以看作是程序設(shè)計語言中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。5抽象數(shù)據(jù)類型（Abstract Type簡稱ADT） ADT是指抽象數(shù)據(jù)的組織和與之相關(guān)的操作?？梢钥醋魇菙?shù)據(jù)的邏輯結(jié)構(gòu)及其在邏輯結(jié)構(gòu)上定義的操作。一個ADT可描述為：ADT ADT-Name Data:/數(shù)據(jù)說明 數(shù)據(jù)元素之間邏輯關(guān)系的描述 Operations:/操作說明 Operation1:/操作1，它通?？捎肅或C的函數(shù)原型來描述 Input:對輸入數(shù)據(jù)的說明 Preconditions:執(zhí)行本操作前系統(tǒng)應(yīng)滿足的狀態(tài)/可看作初始條件 Process:對數(shù)據(jù)執(zhí)行的操作 Output:對返回數(shù)據(jù)的說

5、明 Postconditions:執(zhí)行本操作后系統(tǒng)的狀態(tài)/系統(tǒng)可看作某個數(shù)據(jù)結(jié)構(gòu) Operation2:/操作2 /ADT 二、算法描述：1 包含文件語句：# include # include # include # include 4 函數(shù)：函數(shù)可以不帶任何參數(shù)，若有參數(shù)則分為：值參、形參5 運算符重載： 絕大多運算符可以進行重載三、算法評價：1 正確性2 健壯性3 可讀性4 時間復(fù)雜度：算法有效性的量度之一只分析循環(huán)體內(nèi)操作的執(zhí)行次數(shù)7 時間復(fù)雜度：算法在運行過程中臨時占用存儲空間大小第二章 線性表教學(xué)目標(biāo)：1 掌握線性表的順序存儲結(jié)構(gòu)和抽象數(shù)據(jù)類型2 掌握連接存儲的概念3 單鏈表的查找

6、和插入教學(xué)重點：1 線性表順序存儲的14種算法（重點掌握插入、刪除）2 線性表鏈接存儲的14種算法（重點掌握插入、查找）教學(xué)過程：1 線性表的定義和抽象數(shù)據(jù)結(jié)構(gòu)：1線性表的定義： 線性表（Linear List）是由n（n0）個數(shù)據(jù)元素（結(jié)點）a1，a2，an組成的有限序列。 數(shù)據(jù)元素的個數(shù)n定義為表的長度（n=0時稱為空表）。 將非空的線性表（n0）記作：（a1，a2，an） 數(shù)據(jù)元素ai（1in）只是個抽象符號，其具體含義在不同情況下可以不同。 對于非空的線性表:（a1為表頭元素，an為表尾元素） 有且僅有一個開始結(jié)點a1，沒有直接前趨，有且僅有一個直接后繼a2； 有且僅有一個終結(jié)結(jié)點an

7、，沒有直接后繼，有且僅有一個直接前趨an-1； 其余的內(nèi)部結(jié)點ai（2in-1）都有且僅有一個直接前趨ai-1和一個ai+1。2線性表的抽象數(shù)據(jù)類型：3 操作舉例：4 線性表的順序存儲和操作實現(xiàn)：5 線性表的順序存儲：(1) 順序存儲方法 即把線性表的結(jié)點按邏輯次序依次存放在一組地址連續(xù)的存儲單元里的方法。(2) 順序表（Sequential List） 用順序存儲方法存儲的線性表簡稱為順序表（Sequential List）。 注意：在順序表中，每個結(jié)點ai的存儲地址是該結(jié)點在表中的位置i的線性函數(shù)。只要知道基地址和每個結(jié)點的大小，就可在相同時間內(nèi)求出任一結(jié)點的存儲地址。是一種隨機存取結(jié)構(gòu)。

8、順序表上實現(xiàn)的基本運算2順序存儲下的線性表操作的實現(xiàn)： 表的初始化 void InitList（SeqList *L） 順序表的初始化即將表的長度置為0 L-length=0； 求表長 int ListLength（SeqList *L） 求表長只需返回L-length return L-length; 取表中第i個結(jié)點 DataType GetNode（L，i） 取表中第i個結(jié)點只需返回和L-datai-1即可 if (i L-length-1) Error(position error)； return L-datai-1； 查找值為x的結(jié)點 插入（1） 插入運算的邏輯描述線性表的插入運算

9、是指在表的第i（1in+1）個位置上，插入一個新結(jié)點x，使長度為n的線性表： （a1，ai-1，ai，an）變成長度為n+1的線性表： （a1，ai-1，x，ai，an）注意： 由于向量空間大小在聲明時確定，當(dāng)L-lengthListSize時，表空間已滿，不可再做插入操作 當(dāng)插入位置i的值為in或i1時為非法位置，不可做正常插入操作（2） 順序表插入操作過程在順序表中，結(jié)點的物理順序必須和結(jié)點的邏輯順序保持一致，因此必須將表中位置為n ，n-1，i上的結(jié)點，依次后移到位置n+1，n，i+1上，空出第i個位置，然后在該位置上插入新結(jié)點x。僅當(dāng)插入位置i=n+1時，才無須移動結(jié)點，直接將x插入表

10、的末尾。（3）具體算法描述 void InsertList(SeqList *L，DataType x，int i) /將新結(jié)點 x插入L所指的順序表的第i個結(jié)點ai的位置上 int j; if (iL-length+1) Error(position error);/非法位置，退出運行 if (L-length=ListSize) Error(overflow); /表空間溢出，退出運行 for(j=L-length-1;j=i-1;j-) L-dataj+1=L-dataj;/結(jié)點后移 L-datai-1=x; /插入x L-Length+; /表長加1 （4）算法分析 問題的規(guī)模 表的長

11、度L-length（設(shè)值為n）是問題的規(guī)模。 移動結(jié)點的次數(shù)由表長n和插入位置i決定 算法的時間主要花費在for循環(huán)中的結(jié)點后移語句上。該語句的執(zhí)行次數(shù)是n-i+1。 當(dāng)i=n+1：移動結(jié)點次數(shù)為0，即算法在最好時間復(fù)雜度是0(1) 當(dāng)i=1：移動結(jié)點次數(shù)為n，即算法在最壞情況下時間復(fù)雜度是0(n) 移動結(jié)點的平均次數(shù)Eis(n) 其中： 在表中第i個位置插入一個結(jié)點的移動次數(shù)為n-i+1 pi表示在表中第i個位置上插入一個結(jié)點的概率。不失一般性，假設(shè)在表中任何合法位置（1in+1）上的插入結(jié)點的機會是均等的，則 p1=p2=pn+1=1/(n+1) 刪除（1）刪除運算的邏輯描述 線性表的刪除

12、運算是指將表的第i（1in）個結(jié)點刪去，使長度為n的線性表 （a1，ai-1，ai，ai+1，an） 變成長度為n-1的線性表 （a1，ai-1，ai+1，an）注意： 當(dāng)要刪除元素的位置i不在表長范圍（即i1或iL-length）時，為非法位置，不能做正常的刪除操作（2）順序表刪除操作過程 在順序表上實現(xiàn)刪除運算必須移動結(jié)點，才能反映出結(jié)點間的邏輯關(guān)系的變化。若i=n，則只要簡單地刪除終端結(jié)點，無須移動結(jié)點；若1in-1，則必須將表中位置i+1，i+2，n的結(jié)點，依次前移到位置i，i+1，n-1上，以填補刪除操作造成的空缺。（3）具體算法描述 void DeleteList(SeqList

13、*L,int i) /從L所指的順序表中刪除第i個結(jié)點ai int j; if(iL-length) Error(position error); /非法位置 for(j=i;jlength-1;j+) L-dataj-1=L-dataj; /結(jié)點前移 L-length-; /表長減小 （4）算法分析結(jié)點的移動次數(shù)由表長n和位置i決定： i=n時，結(jié)點的移動次數(shù)為0，即為0(1) i=1時，結(jié)點的移動次數(shù)為n-1，算法時間復(fù)雜度分別是0(n)移動結(jié)點的平均次數(shù)EDE(n)其中： 刪除表中第i個位置結(jié)點的移動次數(shù)為n-i pi表示刪除表中第i個位置上結(jié)點的概率。不失一般性，假設(shè)在表中任何合法位置

14、（1in）上的刪除結(jié)點的機會是均等的，則 p1=p2=pn=1/n3線性表順序存儲空間的動態(tài)分配：3 線性表應(yīng)用舉例：4 線性表的鏈接存儲：5 鏈接存儲的概念：鏈接存儲方法鏈接方式存儲的線性表簡稱為鏈表（Linked List）。鏈表的具體存儲表示為： 用一組任意的存儲單元來存放線性表的結(jié)點（這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的） 鏈表中結(jié)點的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還必須存儲指示其后繼結(jié)點的地址（或位置）信息（稱為指針（pointer）或鏈(link)） 指針變量p的值結(jié)點地址 結(jié)點變量*p的值結(jié)點內(nèi)容 (*p).data

15、的值p指針?biāo)附Y(jié)點的data域的值 (*p).next的值*p后繼結(jié)點的地址*(*p).next)-*p后繼結(jié)點單鏈表的運算 ：1、建立單鏈表 假設(shè)線性表中結(jié)點的數(shù)據(jù)類型是字符，我們逐個輸入這些字符型的結(jié)點，并以換行符n為輸入條件結(jié)束標(biāo)志符。動態(tài)地建立單鏈表的常用方法有如下兩種：（1） 頭插法建表 算法思路 從一個空表開始,重復(fù)讀入數(shù)據(jù),生成新結(jié)點,將讀入數(shù)據(jù)存放在新結(jié)點的數(shù)據(jù)域中,然后將新結(jié)點插入到當(dāng)前鏈表的表頭上,直到讀入結(jié)束標(biāo)志為止。注意：該方法生成的鏈表的結(jié)點次序與輸入順序相反。 具體算法實現(xiàn) LinkList CreatListF(void) /返回單鏈表的頭指針 char ch;

16、LinkList head;/頭指針 ListNode *s; /工作指針 head=NULL; /鏈表開始為空 ch=getchar(); /讀入第1個字符 while(ch!=n) s=(ListNode *)malloc(sizeof(ListNode);/生成新結(jié)點 s-data=ch; /將讀入的數(shù)據(jù)放入新結(jié)點的數(shù)據(jù)域中 s-next=head; head=s; ch=getchar(); /讀入下一字符 return head; （2） 尾插法建表 算法思路 從一個空表開始,重復(fù)讀入數(shù)據(jù),生成新結(jié)點,將讀入數(shù)據(jù)存放在新結(jié)點的數(shù)據(jù)域中,然后將新結(jié)點插入到當(dāng)前鏈表的表尾上,直到讀入結(jié)束

17、標(biāo)志為止。注意：采用尾插法建表，生成的鏈表中結(jié)點的次序和輸入順序一致 必須增加一個尾指針r,使其始終指向當(dāng)前鏈表的尾結(jié)點 具體算法實現(xiàn) LinkList CreatListR(void) /返回單鏈表的頭指針 char ch; LinkList head;/頭指針 ListNode *s,*r; /工作指針 head=NULL; /鏈表開始為空 r=NULL;/尾指針初值為空 ch=getchar(); /讀入第1個字符 while(ch!=n) s=(ListNode *)malloc(sizeof(ListNode);/生成新結(jié)點 s-data=ch; /將讀入的數(shù)據(jù)放入新結(jié)點的數(shù)據(jù)域中

18、if (head!=NULL) head=s;/新結(jié)點插入空表 else r-next=s;/將新結(jié)點插到*r之后 r=s;/尾指針指向新表尾 ch=getchar(); /讀入下一字符 /endwhile if (r!=NULL) r-next=NULL;/對于非空表，將尾結(jié)點指針域置空head=s; return head; 注意：開始結(jié)點插入的特殊處理 由于開始結(jié)點的位置是存放在頭指針(指針變量)中,而其余結(jié)點的位置是在其前趨結(jié)點的指針域中，插入開始結(jié)點時要將頭指針指向開始結(jié)點。 空表和非空表的不同處理若讀入的第一個字符就是結(jié)束標(biāo)志符,則鏈表head是空表,尾指針r亦為空,結(jié)點*r不存在

19、;否則鏈表head非空,最后一個尾結(jié)點*r是終端結(jié)點,應(yīng)將其指針域置空。（3） 尾插法建帶頭結(jié)點的單鏈表 頭結(jié)點及作用頭結(jié)點是在鏈表的開始結(jié)點之前附加一個結(jié)點。它具有兩個優(yōu)點: 由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中,所以在鏈表的第一個位置上的操作就和在表的其它位置上操作一致,無須進行特殊處理; 無論鏈表是否為空，其頭指針都是指向頭結(jié)點的非空指針（空表中頭結(jié)點的指針域空），因此空表和非空表的處理也就統(tǒng)一了。帶頭結(jié)點的單鏈表注意：頭結(jié)點數(shù)據(jù)域的陰影表示該部分不存儲信息。在有的應(yīng)用中可用于存放表長等附加信息。尾插法建帶頭結(jié)點鏈表算法 LinkList CreatListR1(void) /用尾

20、插法建立帶頭結(jié)點的單鏈表 char ch; LinkList head=(ListNode *)malloc(sizeof(ListNode);/生成頭結(jié)點 ListNode *s,*r; /工作指針 r=head; / 尾指針初值也指向頭結(jié)點 while(ch=getchar()!=n) s=(ListNode *)malloc(sizeof(ListNode);/生成新結(jié)點 s-data=ch; /將讀入的數(shù)據(jù)放入新結(jié)點的數(shù)據(jù)域中 r-next=s; r=s; r-next=NULL;/終端結(jié)點的指針域置空，或空表的頭結(jié)點指針域置空 return head; 注意：上述算法里，動態(tài)申請新結(jié)

21、點空間時未加錯誤處理，這對申請空間極少的程序而言不會出問題。但在實用程序里，尤其是對空間需求較大的程序，凡是涉及動態(tài)申請空間，一定要加入錯誤處理以防系統(tǒng)無空間可供分配。（4） 算法時間復(fù)雜度 以上三個算法的時間復(fù)雜度均為0(n)。循環(huán)鏈表（Circular Linked List）：循環(huán)鏈表是一種首尾相接的鏈表。1、循環(huán)鏈表（1）單循環(huán)鏈表在單鏈表中，將終端結(jié)點的指針域NULL改為指向表頭結(jié)點或開始結(jié)點即可。（2）多重鏈的循環(huán)鏈表將表中結(jié)點鏈在多個環(huán)上。2、帶頭結(jié)點的單循環(huán)鏈表注意：判斷空鏈表的條件是head=head-next;3、僅設(shè)尾指針的單循環(huán)鏈表 用尾指針rear表示的單循環(huán)鏈表對開

22、始結(jié)點a1和終端結(jié)點an查找時間都是O(1)。而表的操作常常是在表的首尾位置上進行，因此，實用中多采用尾指針表示單循環(huán)鏈表。帶尾指針的單循環(huán)鏈表可見下圖。注意：判斷空鏈表的條件為rear=rear-next;4、循環(huán)鏈表的特點循環(huán)鏈表的特點是無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活?！纠吭阪湵砩蠈崿F(xiàn)將兩個線性表（a1，a2，an）和（b1，b2，bm）連接成一個線性表（a1，an，b1，bm）的運算。分析：若在單鏈表或頭指針表示的單循環(huán)表上做這種鏈接操作，都需要遍歷第一個鏈表，找到結(jié)點an，然后將結(jié)點b1鏈到an的后面，其執(zhí)行時間是O(n)。若在尾指針表示的單循環(huán)

23、鏈表上實現(xiàn)，則只需修改指針，無須遍歷，其執(zhí)行時間是O(1)。相應(yīng)的算法如下： LinkList Connect(LinkList A,LinkList B) /假設(shè)A，B為非空循環(huán)鏈表的尾指針 LinkList p=A-next;/保存A表的頭結(jié)點位置 A-next=B-next-next;/B表的開始結(jié)點鏈接到A表尾 free(B-next);/釋放B表的頭結(jié)點 B-next=p;/ return B;/返回新循環(huán)鏈表的尾指針 注意：循環(huán)鏈表中沒有NULL指針。涉及遍歷操作時，其終止條件就不再是像非循環(huán)鏈表那樣判別p或p-next是否為空，而是判別它們是否等于某一指定指針，如頭指針或尾指針等

24、。 在單鏈表中，從一已知結(jié)點出發(fā)，只能訪問到該結(jié)點及其后續(xù)結(jié)點，無法找到該結(jié)點之前的其它結(jié)點。而在單循環(huán)鏈表中，從任一結(jié)點出發(fā)都可訪問到表中所有結(jié)點，這一優(yōu)點使某些運算在單循環(huán)鏈表上易于實現(xiàn)。雙鏈表：1、雙向鏈表（Double Linked List） 雙（向）鏈表中有兩條方向不同的鏈，即每個結(jié)點中除next域存放后繼結(jié)點地址外，還增加一個指向其直接前趨的指針域prior。注意：雙鏈表由頭指針head惟一確定的。 帶頭結(jié)點的雙鏈表的某些運算變得方便。 將頭結(jié)點和尾結(jié)點鏈接起來，為雙（向）循環(huán)鏈表。2、雙向鏈表的結(jié)點結(jié)構(gòu)和形式描述結(jié)點結(jié)構(gòu) 形式描述 typedef struct dlistnod

25、e DataType data; struct dlistnode *prior,*next; DListNode; typedef DListNode *DLinkList; DLinkList head;3、雙向鏈表的前插和刪除本結(jié)點操作 由于雙鏈表的對稱性，在雙鏈表能能方便地完成各種插入、刪除操作。雙鏈表的前插操作 void DInsertBefore(DListNode *p,DataType x) /在帶頭結(jié)點的雙鏈表中，將值為x的新結(jié)點插入*p之前，設(shè)pNULL DListNode *s=malloc(sizeof(DListNode);/ s-data=x;/ s-prior=p

26、-prior;/ s-next=p;/ p-prior-next=s;/ p-prior=s;/ 雙鏈表上刪除結(jié)點*p自身的操作 void DDeleteNode(DListNode *p) /在帶頭結(jié)點的雙鏈表中，刪除結(jié)點*p，設(shè)*p為非終端結(jié)點 p-prior-next=p-next;/ p-next-prior=p-prior;/ free(p);/ 注意： 與單鏈表上的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時修改兩個方向上的指針。 上述兩個算法的時間復(fù)雜度均為O(1)。第三章 棧和隊列教學(xué)目標(biāo)：1 掌握棧的順序存儲和鏈接存儲2 掌握隊列的定義以及存儲教學(xué)重點：1 棧的特點及

27、操作（插入、刪除）2 中綴變?yōu)楹缶Y3 隊列的特點及操作（隊滿隊空公式）教學(xué)過程： 棧和隊列是兩種特殊的線性表，它們的邏輯結(jié)構(gòu)和線性表相同，只是其運算規(guī)則較線性表有更多的限制，故又稱它們?yōu)檫\算受限的線性表。棧和隊列被廣泛應(yīng)用于各種程序設(shè)計中。棧的定義及基本運算1、棧的定義 棧（Stack）是限制僅在表的一端進行插入和刪除運算的線性表。(1)通常稱插入、刪除的這一端為棧頂（Top），另一端稱為棧底（Bottom）。(2)當(dāng)表中沒有元素時稱為空棧。(3)棧為后進先出（Last In First Out）的線性表，簡稱為LIFO表。 棧的修改是按后進先出的原則進行。每次刪除（退棧）的總是當(dāng)前棧中最新的

28、元素，即最后插入（進棧）的元素，而最先插入的是被放在棧的底部，要到最后才能刪除。 【示例】元素是以a1，a2，an的順序進棧，退棧的次序卻是an，an-1，a1。2、棧的基本運算（1）InitStack（S） 構(gòu)造一個空棧S。（2）StackEmpty（S） 判?？?。若S為空棧，則返回TRUE，否則返回FALSE。（3）StackFull（S） 判棧滿。若S為滿棧，則返回TRUE，否則返回FALSE。 注意： 該運算只適用于棧的順序存儲結(jié)構(gòu)。（4）Push（S，x） 進棧。若棧S不滿，則將元素x插入S的棧頂。（5）Pop（S） 退棧。若棧S非空，則將S的棧頂元素刪去，并返回該元素。（6）Sta

29、ckTop（S） 取棧頂元素。若棧S非空，則返回棧頂元素，但不改變棧的狀態(tài)。順序棧 棧的順序存儲結(jié)構(gòu)簡稱為順序棧,它是運算受限的順序表。1、 順序棧的類型定義 #define StackSize 100 /假定預(yù)分配的?？臻g最多為100個元素 typedef char DataType;/假定棧元素的數(shù)據(jù)類型為字符 typedef struct DataType dataStackSize; int top; SeqStack; 注意： 順序棧中元素用向量存放 棧底位置是固定不變的，可設(shè)置在向量兩端的任意一個端點 棧頂位置是隨著進棧和退棧操作而變化的，用一個整型量top（通常稱top為棧頂指針

30、）來指示當(dāng)前棧頂位置2、 順序棧的基本操作 前提條件： 設(shè)S是SeqStack類型的指針變量。若棧底位置在向量的低端，即S-data0是棧底元素。（1） 進棧操作 進棧時，需要將S-top加1 注意： S-top=StackSize-1表示棧滿上溢現(xiàn)象-當(dāng)棧滿時，再做進棧運算產(chǎn)生空間溢出的現(xiàn)象。 上溢是一種出錯狀態(tài)，應(yīng)設(shè)法避免。（2） 退棧操作 退棧時，需將S-top減1 注意： S-toptop=-1; （2） 判?？?int StackEmpty（SeqStack *S） return S-top=-1; （3） 判棧滿 int StackFull（SeqStack *SS） return

31、 S-top=StackSize-1; （4） 進棧 void Push（S，x） if (StackFull(S) Error(Stack overflow); /上溢，退出運行 S-data+S-top=x;/棧頂指針加1后將x入棧 （5） 退棧 DataType Pop（S） if(StackEmpty(S) Error(Stack underflow); /下溢，退出運行 return S-dataS-top-;/棧頂元素返回后將棧頂指針減1 （6） 取棧頂元素 DataType StackTop（S） if(StackEmpty(S) Error(Stack is empty); r

32、eturn S-dataS-top; 鏈棧 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧。1、鏈棧的類型定義鏈棧是沒有附加頭結(jié)點的運算受限的單鏈表。棧頂指針就是鏈表的頭指針。鏈棧的類型說明如下： typedef struct stacknode DataType data struct stacknode *next StackNode; typedef struct StackNode *top; /棧頂指針 LinkStack; 注意：LinkStack結(jié)構(gòu)類型的定義是為了方便在函數(shù)體中修改top指針本身 若要記錄棧中元素個數(shù)，可將元素個數(shù)屬性放在LinkStack類型中定義。2、鏈棧的基本運算（1） 置棧空

33、 Void InitStack(LinkStack *S) S-top=NULL; （2） 判?？?int StackEmpty(LinkStack *S) return S-top=NULL; （3） 進棧 void Push(LinkStack *S,DataType x) /將元素x插入鏈棧頭部 StackNode *p=(StackNode *)malloc(sizeof(StackNode); p-data=x; p-next=S-top;/將新結(jié)點*p插入鏈棧頭部 S-top=p; （4） 退棧 DataType Pop(LinkStack *S) DataType x; Stac

34、kNode *p=S-top;/保存棧頂指針 if(StackEmpty(S) Error(Stack underflow.); /下溢 x=p-data; /保存棧頂結(jié)點數(shù)據(jù) S-top=p-next; /將棧頂結(jié)點從鏈上摘下 free(p); return x; （5） 取棧頂元素 DataType StackTop(LinkStack *S) if(StackEmpty(S) Error(Stack is empty.) return S-top-data; 隊列的定義及基本運算1、定義 隊列（Queue）是只允許在一端進行插入，而在另一端進行刪除的運算受限的線性表 （1）允許刪除的一端

35、稱為隊頭（Front）。（2）允許插入的一端稱為隊尾（Rear）。（3）當(dāng)隊列中沒有元素時稱為空隊列。（4）隊列亦稱作先進先出（First In First Out）的線性表，簡稱為FIFO表。 隊列的修改是依先進先出的原則進行的。新來的成員總是加入隊尾（即不允許加塞），每次離開的成員總是隊列頭上的（不允許中途離隊），即當(dāng)前最老的成員離隊。2、隊列的基本邏輯運算（1）InitQueue（Q） 置空隊。構(gòu)造一個空隊列Q。（2）QueueEmpty（Q） 判隊空。若隊列Q為空，則返回真值，否則返回假值。（3） QueueFull（Q） 判隊滿。若隊列Q為滿，則返回真值，否則返回假值。 注意： 此操

36、作只適用于隊列的順序存儲結(jié)構(gòu)。（4） EnQueue（Q，x） 若隊列Q非滿，則將元素x插入Q的隊尾。此操作簡稱入隊。（5） DeQueue（Q） 若隊列Q非空，則刪去Q的隊頭元素，并返回該元素。此操作簡稱出隊。（6） QueueFront（Q） 若隊列Q非空，則返回隊頭元素，但不改變隊列Q的狀態(tài)。順序隊列1、順序隊列 （1）順序隊列的定義 隊列的順序存儲結(jié)構(gòu)稱為順序隊列，順序隊列實際上是運算受限的順序表。（2） 順序隊列的表示和順序表一樣，順序隊列用一個向量空間來存放當(dāng)前隊列中的元素。由于隊列的隊頭和隊尾的位置是變化的，設(shè)置兩個指針front和rear分別指示隊頭元素和隊尾元素在向量空間中的

37、位置，它們的初值在隊列初始化時均應(yīng)置為0。 （3） 順序隊列的基本操作入隊時：將新元素插入rear所指的位置，然后將rear加1。出隊時：刪去front所指的元素，然后將front加1并返回被刪元素。 注意：當(dāng)頭尾指針相等時，隊列為空。 在非空隊列里，隊頭指針始終指向隊頭元素，尾指針始終指向隊尾元素的下一位置。（4）順序隊列中的溢出現(xiàn)象 下溢現(xiàn)象 當(dāng)隊列為空時，做出隊運算產(chǎn)生的溢出現(xiàn)象?！跋乱纭笔钦，F(xiàn)象，常用作程序控制轉(zhuǎn)移的條件。 真上溢現(xiàn)象 當(dāng)隊列滿時，做進棧運算產(chǎn)生空間溢出的現(xiàn)象。“真上溢”是一種出錯狀態(tài)，應(yīng)設(shè)法避免。 假上溢現(xiàn)象由于入隊和出隊操作中，頭尾指針只增加不減小，致使被刪元素的

38、空間永遠無法重新利用。當(dāng)隊列中實際的元素個數(shù)遠遠小于向量空間的規(guī)模時，也可能由于尾指針已超越向量空間的上界而不能做入隊操作。該現(xiàn)象稱為假上溢現(xiàn)象。2、循環(huán)隊列 為充分利用向量空間，克服假上溢現(xiàn)象的方法是：將向量空間想象為一個首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量。存儲在其中的隊列稱為循環(huán)隊列（Circular Queue）。 （1） 循環(huán)隊列的基本操作 循環(huán)隊列中進行出隊、入隊操作時，頭尾指針仍要加1，朝前移動。只不過當(dāng)頭尾指針指向向量上界（QueueSize-1）時，其加1操作的結(jié)果是指向向量的下界0。這種循環(huán)意義下的加1操作可以描述為： 方法一： if(i+1=QueueSize) /i表

39、示front或rear i=0; else i+; 方法二-利用模運算 i=(i+1)%QueueSize；（2） 循環(huán)隊列邊界條件處理 循環(huán)隊列中，由于入隊時尾指針向前追趕頭指針；出隊時頭指針向前追趕尾指針，造成隊空和隊滿時頭尾指針均相等。因此，無法通過條件front=rear來判別隊列是空還是滿。解決這個問題的方法至少有三種： 另設(shè)一布爾變量以區(qū)別隊列的空和滿； 少用一個元素的空間。約定入隊前，測試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認(rèn)為隊滿（注意：rear所指的單元始終為空）；使用一個計數(shù)器記錄隊列中元素的總數(shù)（即隊列長度）。（3） 循環(huán)隊列的類型定義 #define Que

40、ur Size 100 /應(yīng)根據(jù)具體情況定義該值 typedef char Queue DataType; /DataType的類型依賴于具體的應(yīng)用 typedef Sturet /頭指針，隊非空時指向隊頭元素 int front; /尾指針，隊非空時指向隊尾元素的下一位置 int rear; /計數(shù)器，記錄隊中元素總數(shù) DataType dataQueueSize CirQueue;（4） 循環(huán)隊列的基本運算用第三種方法，循環(huán)隊列的六種基本運算： 置隊空 void InitQueue(CirQueue *Q) Q-front=Q-rear=0; Q-count=0; /計數(shù)器置0 判隊空 i

41、nt QueueEmpty(CirQueue *Q) return Q-count=0; /隊列無元素為空 判隊滿int QueueFull(CirQueue *Q) return Q-count=QueueSize; /隊中元素個數(shù)等于QueueSize時隊滿 入隊void EnQueue(CirQueuq *Q,DataType x) if(QueueFull(Q) Error(Queue overflow); /隊滿上溢 Q-count +; /隊列元素個數(shù)加1 Q-dataQ-rear=x; /新元素插入隊尾 Q-rear=(Q-rear+1)%QueueSize; /循環(huán)意義下將尾指

42、針加1 出隊DataType DeQueue(CirQueue *Q) DataType temp; if(QueueEmpty(Q) Error(Queue underflow); /隊空下溢 temp=Q-dataQ-front; Q-count-; /隊列元素個數(shù)減1 Q-front=(Q-front+1)&QueueSize; /循環(huán)意義下的頭指針加1 return temp; 取隊頭元素DataType QueueFront(CirQueue *Q) if(QueueEmpty(Q) Error(Queue if empty.); return Q-dataQ-front; 鏈隊列

43、1、 鏈隊列的定義 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈隊列。它是限制僅在表頭刪除和表尾插入的單鏈表。2、 鏈隊列的結(jié)構(gòu)類型說明注意：增加指向鏈表上的最后一個結(jié)點的尾指針，便于在表尾做插入操作。 鏈隊列示意圖見上圖，圖中Q為LinkQueue型的指針。3、 鏈隊列的基本運算（1） 置空隊 void InitQueue(LinkQueue *Q) Q-front=Q-rear=NULL; （2） 判隊空 intQueueEmpty(LinkQueue *Q) return Q-front=NULL&Q-rear=Null; /實際上只須判斷隊頭指針是否為空即可 （3） 入隊 void EnQueue(LinkQueue *Q,DataType x) /將元素x插入鏈隊列尾部 QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode);/申請新結(jié)點 p-data=x; p-next=NULL;