數(shù)據(jù)結(jié)構(gòu)與算法全套教學(xué)課件

數(shù)據(jù)結(jié)構(gòu)與算法全套可編輯PPT課件課程內(nèi)容第1章數(shù)據(jù)結(jié)構(gòu)概述第2章線性表第3章棧和隊(duì)列第4章串第5章數(shù)組第6章樹和二叉樹第7章圖第8章查找第9章排序第1章數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)課程主要討論數(shù)據(jù)的表示（數(shù)據(jù)的結(jié)構(gòu)）和數(shù)據(jù)處理的基本方法（算法）。要想成為一個(gè)優(yōu)秀的程序設(shè)計(jì)人員，至少需要以下三個(gè)條件：①

能夠熟練地選擇和設(shè)計(jì)各種數(shù)據(jù)結(jié)構(gòu)和算法。

②至少要能夠熟練地掌握一門程序設(shè)計(jì)語言。

③熟知所涉及的相關(guān)應(yīng)用領(lǐng)域的知識(shí)。3【本章重點(diǎn)】①數(shù)據(jù)結(jié)構(gòu)及相關(guān)概念；②數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，二者的關(guān)系；③算法及特性；④算法的時(shí)間復(fù)雜度和空間復(fù)雜度的概念。4【本章難點(diǎn)】①抽象數(shù)據(jù)類型的理解和使用；②描述算法的工具；③算法的時(shí)間復(fù)雜度分析與計(jì)算。5【本章內(nèi)容】數(shù)據(jù)結(jié)構(gòu)的基本概念算法習(xí)題161.1數(shù)據(jù)結(jié)構(gòu)的基本概念軟件開發(fā)的三個(gè)階段（1）分析階段：對問題進(jìn)行分析，抽象出數(shù)據(jù)模型，形成求解問題的基本思路，確定解決問題的方案；（2）設(shè)計(jì)階段：將數(shù)據(jù)以及數(shù)據(jù)之間的關(guān)系存儲(chǔ)到計(jì)算機(jī)的內(nèi)存中，設(shè)計(jì)數(shù)據(jù)處理的算法；（3）實(shí)現(xiàn)階段：將算法轉(zhuǎn)換為用某種程序設(shè)計(jì)語言編寫的程序，并進(jìn)行測試、修改，直到得到問題的解答。7關(guān)于數(shù)據(jù)結(jié)構(gòu)的基本術(shù)語數(shù)據(jù)是信息的載體，它是描述客觀事物的數(shù)字、字符以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的集合。例如，一個(gè)代數(shù)方程的求解程序中所用的數(shù)據(jù)是整數(shù)和實(shí)數(shù)；一個(gè)編譯程序或文本編輯程序中所使用的數(shù)據(jù)是字符串。隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大，數(shù)據(jù)的含義更為廣泛，如圖像、聲音等都可以通過編碼而屬于數(shù)據(jù)的范疇。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。有些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的，不可再分割的最小標(biāo)識(shí)單位。一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成，8數(shù)據(jù)結(jié)構(gòu)（DataStructure）是數(shù)據(jù)元素之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般來說，數(shù)據(jù)結(jié)構(gòu)所研究的主要內(nèi)容包括以下三個(gè)方面：（1）數(shù)據(jù)的邏輯結(jié)構(gòu)——數(shù)據(jù)元素之間的邏輯關(guān)系。（2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)——數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)中的存儲(chǔ)方式，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又稱為數(shù)據(jù)的物理結(jié)構(gòu)。（3）數(shù)據(jù)的運(yùn)算——對數(shù)據(jù)施加的操作，即數(shù)據(jù)的運(yùn)算。9數(shù)據(jù)的邏輯結(jié)構(gòu)（1）集合：數(shù)據(jù)元素之間只是“屬于同一集合”的關(guān)系。（2）線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在“一對一”的前后順序關(guān)系，除第一個(gè)元素和最后一個(gè)元素之外，其余元素都有唯一的一個(gè)直接前驅(qū)元素和唯一的一個(gè)直接后繼元素。（3）樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在“一對多”的層次關(guān)系，除最頂層的元素之外，其余元素都有若干個(gè)直接給后繼元素。（4）圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在“多對多”的任意關(guān)系，每個(gè)元素都有若干個(gè)直接前驅(qū)元素和若干個(gè)直接后繼元素。10數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（1）順序存儲(chǔ)結(jié)構(gòu)

元素之間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。通常順序存儲(chǔ)結(jié)構(gòu)是借助于程序語言的數(shù)組（又稱為向量）來描述的。

該方法主要應(yīng)用于線性數(shù)據(jù)結(jié)構(gòu)，非線性的數(shù)據(jù)結(jié)構(gòu)也可以通過某種線性化的方法來實(shí)現(xiàn)順序存儲(chǔ)。（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

通過元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系，即邏輯上相鄰的元素在物理位置上不一定相鄰。通常要借助于程序語言的指針類型來描述它。（3）索引存儲(chǔ)結(jié)構(gòu)

在存儲(chǔ)數(shù)據(jù)元素的同時(shí)，還需要有索引表，索引表中的每一項(xiàng)稱為索引項(xiàng)，其一般形式是（關(guān)鍵字，地址），關(guān)鍵字是能夠唯一標(biāo)識(shí)一個(gè)元素的那些數(shù)據(jù)項(xiàng)。（4）散列存儲(chǔ)結(jié)構(gòu)

根據(jù)數(shù)據(jù)元素的關(guān)鍵字計(jì)算出該元素的存儲(chǔ)地址。又稱為計(jì)算尋址的方式。111.2算法算法的定義

算法是對特定問題求解步驟的描述，是指令的有限序列。算法的性質(zhì)（1）輸入性：0至多個(gè)輸入。（2）輸出性：1至多個(gè)輸出。（3）有窮性:對于合法的輸入值，算法在執(zhí)行有窮步之后結(jié)束。（4）確定性:對于相同的輸入執(zhí)行相同的路徑，即對于相同的輸入只能得出相同的輸出。（5）可行性:用于描述算法的操作都是足夠基本的，即算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。12（1）自然語言

優(yōu)點(diǎn)：容易理解；缺點(diǎn)：不夠嚴(yán)謹(jǐn)，容易出現(xiàn)二義性。（2）流程圖

優(yōu)點(diǎn)：直觀易懂；缺點(diǎn)：嚴(yán)密性不如程序設(shè)計(jì)語言，靈活性不如自然語言。（3）程序設(shè)計(jì)語言

優(yōu)點(diǎn)：描述算法能夠由計(jì)算機(jī)執(zhí)行；缺點(diǎn)：抽象性差，設(shè)計(jì)者在設(shè)計(jì)算法時(shí)過于受到程序設(shè)計(jì)語言的語法規(guī)則限制，往往忽視了算法的正確性和邏輯性。（4）偽代碼

偽代碼是介于自然語言和高級(jí)語言之間的方法，例如用類C語言來描述算法。優(yōu)點(diǎn)：重點(diǎn)給出算法的邏輯，并且不受語言的語法規(guī)則限制?！纠浚≒8）用偽代碼描述求兩個(gè)正整數(shù)的最大公約數(shù)。13描述算法的工具對算法的評價(jià)標(biāo)準(zhǔn)

通常從正確性、易讀性、健壯性和高效性等四個(gè)方面評價(jià)算法的質(zhì)量。算法的高效性

算法的高效性包括時(shí)間特性和空間特性。時(shí)間特性是指執(zhí)行算法所需要的計(jì)算時(shí)間長短?？臻g特性則是執(zhí)行算法所需要的輔助存儲(chǔ)空間大小。（1）算法時(shí)間特性的分析

一個(gè)算法所需的計(jì)算時(shí)間，應(yīng)當(dāng)是該算法中每條語句的執(zhí)行時(shí)間之和，而每條語句的執(zhí)行時(shí)間是該語句的執(zhí)行次數(shù)（稱為頻度）與該語句執(zhí)行一次所需時(shí)間的乘積。

我們通過算法的時(shí)間復(fù)雜度來衡量算法的時(shí)間特性。14算法時(shí)間復(fù)雜度的計(jì)算【例1.2】求兩個(gè)n階方陣的乘積C＝A×B，其算法如下：＃definen自然數(shù)voidMatrixmlt(intA[n][n],intB[n][n],intC[n][n]){ inti,j,k;

語句頻度

for(i=0;i<n;i++) //語句①

n+1

for(j=0；j<n;j++){ //語句②

n(n+1)

C[i][j]=0; //語句③

n2

for(k=0;k<n;k++)//語句④

n2(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j];//語句⑤

n3 }}

算法中所有語句的頻度之和為T(n)=2n3+3n2+2n+1。算法的語句頻度之和T(n)是矩陣階數(shù)n的函數(shù)，n是算法求解方陣乘積問題的規(guī)模。15

一般情況下，算法中基本操作重復(fù)執(zhí)行的時(shí)間是問題規(guī)模n的某個(gè)函數(shù)f(n)，算法的時(shí)間復(fù)雜度記為T(n)=O(f(n))它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同，f(n)一般是算法中頻度最大的語句頻度。例如，算法Matrixmlt的時(shí)間復(fù)雜度是T(n)=O(n3)，這里的f(n)=n3是該算法中語句⑤的頻度。由此可見，當(dāng)有循環(huán)嵌套時(shí)，算法的時(shí)間復(fù)雜度是由最內(nèi)層語句的頻度f(n)決定的。

計(jì)算算法的時(shí)間復(fù)雜度要考慮問題的規(guī)模。16【例1.3】交換a和b的值。temp=a;a=b;b=temp;

以上三條單個(gè)語句的頻度都為1，該算法的執(zhí)行時(shí)間是一個(gè)與問題規(guī)模n無關(guān)的常數(shù)，時(shí)間復(fù)雜度記作T(n)=O(1)。事實(shí)上，只要算法的執(zhí)行時(shí)間不隨著問題的規(guī)模增加而增長，即使算法中有成百上千條語句，其時(shí)間復(fù)雜度也只是O(1)。17【例】在一維數(shù)組A[n]中順序查找值為k的元素，順序查找算法如下：intFind(intA[],intn,intk){ for(i=0;i<n;i++) if(A[i]==k)break; returni;}

算法從A[0]開始查找，如果A[0]的值就等于k，那么比較一次就查找到了，這是最好情況；如果A[n-1]的值等于k，則需要比較n次才能查找到，這是最壞情況；平均情況下需要比較(n+1)/2次。

計(jì)算算法的時(shí)間復(fù)雜度要考慮最壞情況。1819【例1.4】判斷n是否為素?cái)?shù)。voidprime(intn){ inti=2;

while((n%i)!=0&&i<sqrt(n))

i++;

if(i>=sqrt(n))printf("%d是素?cái)?shù)",n);

elseprintf("%d不是素?cái)?shù)",n);}設(shè)語句i++；的頻度為f(n)，由i<sqrt(n)可知f(n)<sqrt(n)。時(shí)間復(fù)雜度應(yīng)考慮最壞的情況，所以20【例1.5】變量計(jì)數(shù)。 i=1；1 while(i<=n)i=i*2;f(n)

由于2f(n)≤n，即f(n)≤log2n，取最大值f(n)=log2n，T(n)=O(f(n))=O(log2n)常見的時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列：常量階O(1)<對數(shù)階O(log2n)<線性階O(n)<線性對數(shù)階O(nlog2n)<平方階O(n2)<立方階O(n3)<…<k次方階O(nk)<指數(shù)階O(2n)算法的空間復(fù)雜度算法的空間復(fù)雜度是指在算法執(zhí)行過程中所需要的輔助存儲(chǔ)空間數(shù)量。輔助存儲(chǔ)空間是除算法本身和輸入輸出數(shù)據(jù)所占存儲(chǔ)空間之外，算法運(yùn)行時(shí)臨時(shí)開辟的存儲(chǔ)空間，記為：S(n)=O(f(n))

其中n為問題的規(guī)模，分析方法與算法的時(shí)間復(fù)雜度類似。21算法的易讀性

一個(gè)高質(zhì)量的算法除了正確和運(yùn)行效率高之外，還對算法的易讀性有一定的要求。算法的易讀性主要體現(xiàn)在算法的結(jié)構(gòu)、代碼的書寫格式以及注釋等方面。（1）算法的結(jié)構(gòu)

解決某個(gè)較為復(fù)雜問題的算法通常也是由一個(gè)個(gè)模塊組成的，而每個(gè)模塊的功能相對獨(dú)立。盡可能做到高內(nèi)聚、低耦合。（2）代碼書寫格式

采用縮進(jìn)的方式突出分支、循環(huán)、嵌套等結(jié)構(gòu)，這樣可以清晰地體現(xiàn)算法的視覺組織。（3）注釋

注釋就是對算法進(jìn)行必要的說明，幫助我們理解算法。注釋分為序言性注釋和功能性注釋。2223

習(xí)題1作業(yè)

習(xí)題1中的第一、二、三題寫在教材上，盡可能都做，會(huì)在上課時(shí)抽查。習(xí)題1中的第四題寫在作業(yè)本上，作業(yè)本要交。四、簡答題（1）、（2）、（3）、（4）、（5）第2章線性表

線性表是一種典型的線性結(jié)構(gòu)，是簡單而且常用的數(shù)據(jù)結(jié)構(gòu)。線性表的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以及基本運(yùn)算的實(shí)現(xiàn)又是后面各章的基礎(chǔ)。24【本章重點(diǎn)】①線性表的定義和線性表的基本運(yùn)算；②順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的基本思想；③基于順序表和單鏈表基本運(yùn)算的實(shí)現(xiàn)；④基于順序表和單鏈表基本運(yùn)算的時(shí)間特性和空間特性。⑤順序表和鏈表之間的比較。25【本章難點(diǎn)】①關(guān)于順序表、單鏈表、循環(huán)鏈表和雙向鏈表的算法設(shè)計(jì)及應(yīng)用；②模塊之間參數(shù)傳遞的問題。26【本章內(nèi)容】線性表的邏輯結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序表與鏈表的比較習(xí)題2272.1線性表的邏輯結(jié)構(gòu)線性表的定義

線性表是由n（n≥0）個(gè)元素組成的有限序列，n為線性表的長度。當(dāng)n=0時(shí)稱為空表，當(dāng)n>0時(shí)稱為非空表，記為L=(a1,…,ai-1,ai,ai+1,…,an)需要注意的幾點(diǎn)（1）線性表中各元素具有相同的特性（2）i是元素ai在線性表中的位序，即位置序號(hào)，位序從1開始（3）對于一個(gè)非空線性表，有且僅有一個(gè)開始結(jié)點(diǎn)a1；有且僅有一個(gè)終端結(jié)點(diǎn)an；除第一個(gè)結(jié)點(diǎn)外，其余結(jié)點(diǎn)ai（2≤i≤n)均有且僅有一個(gè)直接前驅(qū)ai-1；除最后一個(gè)結(jié)點(diǎn)外，其余結(jié)點(diǎn)ai（1≤i≤n-1)均有且僅有一個(gè)直接后繼ai+128線性表的基本運(yùn)算（1）InitList(&L)線性表初始化

初始條件：線性表L不存在。

運(yùn)算結(jié)果：構(gòu)造一個(gè)空的線性表。（2）SetNull(L)置空表，

初始條件：線性表L已存在。

運(yùn)算結(jié)果：將表L置為空表。（3）Length(L)求表長度

初始條件：線性表L已存在。

運(yùn)算結(jié)果：返回表L中的數(shù)據(jù)元素個(gè)數(shù)。29每一種數(shù)據(jù)的邏輯結(jié)構(gòu)，對應(yīng)一組基本運(yùn)算。這里只是給出抽象的運(yùn)算，而運(yùn)算的具體實(shí)現(xiàn)，只有在確定了數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)之后才能夠考慮。（4）Get(L,i)取元素值

初始條件：線性表L已存在。

運(yùn)算結(jié)果：返回表L中第i個(gè)數(shù)據(jù)元素ai的值或元素的位置信息。（5）Locate(L,x)定位，按值查找

初始條件：線性表L已存在。

運(yùn)算結(jié)果：若表L中存在一個(gè)或多個(gè)值為x的元素，返回第一個(gè)查找到的數(shù)據(jù)元素的位序，否則返回一個(gè)特殊值。（6）Insert(L,x,i)插入

初始條件：線性表L已存在。

運(yùn)算結(jié)果：在表L中第i個(gè)位置上插入值為x的元素，若插入成功，表長加1。（7）Delete(L,i)刪除

初始條件：線性表L已存在。

運(yùn)算結(jié)果：刪除表L中第i個(gè)數(shù)據(jù)元素，若刪除成功，表長減1。30函數(shù)的參數(shù)L是指向線性表結(jié)構(gòu)體的指針。對線性表的基本運(yùn)算可以分為三類，所對應(yīng)的函數(shù)參數(shù)是不同的。（1）線性表初始化運(yùn)算使得線性表從不存在到存在，顯然指針L的指向發(fā)生了變化；（2）置空表、插入和刪除運(yùn)算使得線性表的內(nèi)容發(fā)生了變化，但指針的指向并不會(huì)發(fā)生變化；（3）求表長度、取元素值和定位運(yùn)算對于指針L和表的內(nèi)容都沒有發(fā)生變化?；具\(yùn)算應(yīng)用的舉例【例2.1】將線性表A按元素值奇、偶數(shù)拆分成兩個(gè)表，A表存放奇數(shù)，B表存放偶數(shù)。voidseparate(Linear_list*La,Linear_list*Lb)//已有線性表La和空線性表Lb{

inti=1,j=1,x; while(i<=Length(La)) { x=Get(La,i);//取ai

if(x%2==0) { Insert(Lb,x,j); j++; Delete(La,i);

}//ai是偶數(shù)，插入到B表末尾，并從A表中刪除

elsei++;//ai是奇數(shù)，仍放在A表中

}}說明: （1）將偶數(shù)插入到B表，A表只保留奇數(shù)

（2）時(shí)間復(fù)雜度是O(Length(La))312.2線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)又稱為順序表，是把線性表的元素按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。順序表中元素地址的計(jì)算

假設(shè)順序表中每個(gè)元素占用c個(gè)存儲(chǔ)單元，其中的第一個(gè)單元的存儲(chǔ)地址則是該元素的存儲(chǔ)地址，順序表中開始元素a1的存儲(chǔ)地址是Loc(a1)，那么元素ai的存儲(chǔ)地址Loc(ai)可通過下式計(jì)算：Loc(ai)=Loc(a1)+(i-1)*c（1≤i≤n）

其中Loc(a1)是順序表的第一個(gè)元素a1的存儲(chǔ)地址，稱為順序表的起始地址或基地址。可以對順序表順序存取或隨機(jī)存取。32順序表的結(jié)構(gòu)類型定義#definemaxsize1024typedefintdatatype;typedefstruct{ datatypedata[maxsize];//采用一維數(shù)組存儲(chǔ)線性表 intlast;//順序表當(dāng)前的長度}sequenlist;33線性表順序存儲(chǔ)的兩種方式

由于線性表結(jié)點(diǎn)的位序從1開始，而C語言中數(shù)組的下標(biāo)從0開始，關(guān)于線性表中數(shù)據(jù)元素的位序（邏輯位置）和存放它的數(shù)組下標(biāo)（物理位置）之間的關(guān)系通常有兩種處理方式。（1）從下標(biāo)為0的數(shù)組元素開始存放，則結(jié)點(diǎn)的位序等于數(shù)組元素的下標(biāo)加一。（2）從下標(biāo)為1的數(shù)組元素開始使用，這樣結(jié)點(diǎn)的位序和數(shù)組的下標(biāo)是相等的，使用起來會(huì)更簡單自然一些，下標(biāo)為0的元素不用或用作其它用途。這里我們約定采用第一種方式。34位序=下標(biāo)+1，下標(biāo)=位序-1位序=下標(biāo)若L是指向順序表的指針，則a1~an分別存儲(chǔ)在L->data[0]~L->data[L->last-1]中。L->data[i-1]是元素ai；L->last表示線性表當(dāng)前的長度?；具\(yùn)算在順序表上的實(shí)現(xiàn)1、順序表的初始化

在函數(shù)中建立一個(gè)空順序表L，指針L從沒有指向順序表變?yōu)橹赶蛞粋€(gè)空表，顯然指針L的指向發(fā)生了變化。如何將這一變化的結(jié)果帶回到主調(diào)函數(shù)，我們給出以下三種方式，并進(jìn)行比較?！舅惴?.1】通過函數(shù)返回值將結(jié)果帶回到主調(diào)函數(shù)。sequenlist*InitList(){ sequenlist*L=(sequenlist*)malloc(sizeof(sequenlist));//分配順序表的動(dòng)態(tài)存儲(chǔ)空間 L->last=0;//將表的長度置為0 returnL;}//時(shí)間復(fù)雜度為O(1)35在函數(shù)中定義的指針指向順序表，指針作為函數(shù)的返回值?！舅惴?.2】采用指向指針的指針作為函數(shù)參數(shù)，通過函數(shù)的參數(shù)將結(jié)果帶回到主調(diào)函數(shù)。voidInitList(sequenlist**L){ *L=(sequenlist*)malloc(sizeof(sequenlist));//第二級(jí)指針*L指向順序表 *L->last=0;//將*L所指向的順序表長度置0}//時(shí)間復(fù)雜度為O(1)36第一級(jí)指針L指向第二級(jí)指針*L，L的指向沒有改變，而*L的指向發(fā)生了變化，函數(shù)運(yùn)行結(jié)束，將*L的指向帶回到主調(diào)函數(shù)。【算法2.3】采用指針的引用作為函數(shù)參數(shù)，通過函數(shù)的參數(shù)將結(jié)果帶回到主調(diào)函數(shù)。voidInitList(sequenlist*&L)//指針的引用作為參數(shù){ L=(sequenlist*)malloc(sizeof(sequenlist)); L->last=0;}//時(shí)間復(fù)雜度為O(1)37參數(shù)的類型使用了C++語言中的指針類型的引用，從而可以將指針?biāo)赶虻慕Y(jié)構(gòu)體動(dòng)態(tài)存儲(chǔ)帶回到主調(diào)函數(shù)。2、在順序表中插入一個(gè)元素

在線性表的第i（1≤i≤n+1）個(gè)位置上插入一個(gè)新結(jié)點(diǎn)x，并且使表的長度加一，即使 (a1,…,ai-1,ai,…an)變?yōu)殚L度是n+1的線性表 (a1,…,ai-1,x,ai,…an)38【算法2.4】在順序表的第i個(gè)位置上插入一個(gè)新結(jié)點(diǎn)x。intInsert(sequenlist*L,datatypex,inti)//將新結(jié)點(diǎn)插入順序表的第i個(gè)位置。插入成功，返回1；不成功，返回0{ if(L->last==maxsize){print("表已滿");return0;} elseif(i<1||i>L->last+1){print("非法插入位置");return0;} else{ for(j=L->last;j>=i;j--)L->data[j]=L->data[j-1];//結(jié)點(diǎn)后移 L->data[i-1]=x;//插入到L->data[i-1]中 L->last++;//表長度加1 return1;}}39

3、在順序表中刪除一個(gè)元素

將表的第i（1≤i≤n）個(gè)結(jié)點(diǎn)刪去，并且使表的長度減一。即使 (a1,…,ai-1,ai,ai+1,…an)變成長度為n-1的線性表 (a1,…,ai-1,ai+1,…an)40【算法2.5】刪除順序表的第i個(gè)結(jié)點(diǎn)。intDelete(sequenlist*L,inti)//刪除順序表的第i個(gè)結(jié)點(diǎn)。刪除成功，返回1；不成功，返回0{ intj; if((i<1)||(i>L->last)){print("非法刪除位置");return0;} else{

for(j=i;j<=L->last-1;j++)L->data[j-1]=L->data[j];//結(jié)點(diǎn)前移

L->last--;//表長度減1

return1； }}41

【例2.2】有順序表A和B，其表中元素按由小到大的順序排列。編寫一個(gè)算法將它們合并為順序表C，并且表C中的元素也按由小到大的順序排列。voidmerge(sequenlist*A,sequenlist*B,sequenlist*&C){//在函數(shù)中產(chǎn)生順序表C，為了將C的指向帶回到主調(diào)函數(shù)，參數(shù)采用指針的引用 if(A->last+B->last>maxsize)rintf("Error!\n"); else{ C=(sequenlist*)malloc(sizeof(sequenlist)); i=0; j=0; k=0; while(i<A->last&&j<B->last) if(A->data[i]<B->data[j]) C->data[k++]=A->data[i++]; else C->data[k++]=B->data[j++]; while(i<A->last) C->data[k++]=A->data[i++]; //將表A的剩余元素復(fù)制完 while(j<B->last) C->data[k++]=B->data[j++]; //將表B的剩余元素復(fù)制完 C->last=k; }}42順序表的應(yīng)用實(shí)例——一個(gè)完整的程序

問題的描述：首先建立一個(gè)順序存儲(chǔ)結(jié)構(gòu)的線性表，然后刪除順序表中所有值為x的結(jié)點(diǎn)。432.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)的線性表具有順序存取和隨機(jī)存取表中元素的優(yōu)點(diǎn)，同時(shí)，它也存在下列缺點(diǎn)：（1）插入、刪除操作時(shí)需要移動(dòng)大量元素，效率較低；（2）最大表長難以估計(jì)，太大了浪費(fèi)空間，太小了容易溢出。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表可以克服上述缺點(diǎn)，但是只能順序存取不能隨機(jī)存取。鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表。44

線性表采用單鏈表來表示，在內(nèi)存中用一組連續(xù)的或不連續(xù)的存儲(chǔ)單元來存儲(chǔ)線性表的數(shù)據(jù)元素，每個(gè)元素含有數(shù)據(jù)域（data）和一個(gè)指針域（next），這兩部分信息組成了單鏈表中的一個(gè)結(jié)點(diǎn)。45單鏈表單鏈表的結(jié)點(diǎn)類型定義typedef結(jié)點(diǎn)數(shù)據(jù)域類型datatype;typedefstructnode{ datatypedata; structnode*next;}linklist;linklist*head,*p; //head為頭指針，p為工作指針指針?biāo)赶虻慕Y(jié)點(diǎn)存儲(chǔ)空間是在程序執(zhí)行過程中生成和釋放的，故稱為動(dòng)態(tài)存儲(chǔ)空間。在C語言中，通過下面兩個(gè)標(biāo)準(zhǔn)函數(shù)生成或釋放結(jié)點(diǎn)。

生成結(jié)點(diǎn)：p=(linklist*)malloc(sizeof(linklist));

釋放結(jié)點(diǎn)：free(p);必須通過指針來訪問結(jié)點(diǎn)，即用*p表示結(jié)點(diǎn)。用p->data和p->next，或者(*p).data和(*p).next表示結(jié)點(diǎn)的數(shù)據(jù)域和指針域。46關(guān)于鏈表的頭結(jié)點(diǎn)

單鏈表以及后面所討論的循環(huán)鏈表和雙向鏈表均可以帶頭結(jié)點(diǎn)或者不帶頭結(jié)點(diǎn)。47單鏈表的基本運(yùn)算1、建立單鏈表

假設(shè)單鏈表結(jié)點(diǎn)的數(shù)據(jù)域類型是字符型，我們逐個(gè)輸入字符，并以換行符“\n”作為輸入結(jié)束標(biāo)志。動(dòng)態(tài)建立單鏈表通常有以下兩種方法。（1）頭插法建表

從空表開始，每次將輸入的字符作為新結(jié)點(diǎn)插入到表頭，鏈表中結(jié)點(diǎn)的次序與輸入字符的順序相反。用偽代碼描述單鏈表的建立過程：

481 建立只有頭結(jié)點(diǎn)的空表2 循環(huán)讀取字符，若不是換行符，則執(zhí)行循環(huán)體；若是換行符，則結(jié)束循環(huán)

2_1 產(chǎn)生新結(jié)點(diǎn)

2_2 將新結(jié)點(diǎn)插入到表頭，即作為單鏈表當(dāng)前的第一個(gè)結(jié)點(diǎn)3 返回單鏈表的頭指針【算法2.6】頭插法建立單鏈表linklist*CreateListF()//帶頭結(jié)點(diǎn)的頭插法，返回單鏈表的頭指針{ linklist*head,*p;charch;head=(linklist*)malloc(sizeof(linklist));//產(chǎn)生頭結(jié)點(diǎn)①head->next=NULL; while((ch=getchar())!='\n')//輸入abc{p=(linklist*)malloc(sizeof(linklist));//生成新結(jié)點(diǎn)②p->data=ch;//對結(jié)點(diǎn)的數(shù)據(jù)域賦值③p->next=head->next;//新結(jié)點(diǎn)的指針域指向原第一個(gè)結(jié)點(diǎn)④head->next=p;//修改頭結(jié)點(diǎn)的指針域⑤}returnhead;}49（2）尾插法建表【算法2.7】尾插法建立單鏈表linklist*CreateListR()//帶頭結(jié)點(diǎn)的尾插法，返回單鏈表的頭指針{ linklist*head,*p,*r;charch; head=(linklist*)malloc(sizeof(linklist)); //生成頭結(jié)點(diǎn)① head->next=NULL;//建立空表 r=head;//r指針指向頭結(jié)點(diǎn)

while((ch=getchar())!='\n')//輸入abc { p=(linklist*)malloc(sizeof(linklist));//生成新結(jié)點(diǎn)② p->data=ch;//將輸入的字符賦給新結(jié)點(diǎn)的數(shù)據(jù)域 r->next=p; //新結(jié)點(diǎn)插入表尾③ r=p; //r指針指向到表尾④ } r->next=NULL;//表尾結(jié)點(diǎn)的指針域置空⑤ returnhead;}//時(shí)間復(fù)雜度為O(n)502、單鏈表查找對單鏈表的查找只能從表頭開始順序查找。

（1）按序號(hào)查找

單鏈表的第一個(gè)結(jié)點(diǎn)的序號(hào)為1，第二個(gè)結(jié)點(diǎn)的序號(hào)為2，以此類推。

設(shè)單鏈表的長度為n，并且規(guī)定頭結(jié)點(diǎn)的位序?yàn)?，要查找第i個(gè)結(jié)點(diǎn)，僅當(dāng)1≤i≤n時(shí)，才能查找到；否則查找不到，返回NULL。

（2）按值查找

在單鏈表中查找是否存在給定查找值key的結(jié)點(diǎn)，若存在，則返回該結(jié)點(diǎn)的地址；否則返回NULL。513、單鏈表的插入

在單鏈表中插入結(jié)點(diǎn)，只需要修改指針的指向，不需要移動(dòng)結(jié)點(diǎn)。

單鏈表只能做“后插”，不能做“前插”。算法2.11是在單鏈表的第i個(gè)結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)，必須先找到第i-1個(gè)結(jié)點(diǎn)并插入，即將“前插”變?yōu)椤昂蟛濉薄！纠?.3】將值為x的新結(jié)點(diǎn)插入到遞增有序單鏈表中，使插入后該鏈表仍然有序。

先查找插入位置，然后插入新結(jié)點(diǎn)。在查找過程中，若遇到某個(gè)結(jié)點(diǎn)的元素值大于等于x，則在該結(jié)點(diǎn)之前插入新結(jié)點(diǎn)。在單鏈表中必須利用前驅(qū)指針將“前插操作”變?yōu)椤昂蟛宀僮鳌薄?24、單鏈表的刪除

在單鏈表中刪除一個(gè)結(jié)點(diǎn)，必須先查找到該結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，然后刪除該結(jié)點(diǎn)?！舅惴?.12】單鏈表的刪除voidDelete(linklist*L,inti)//在帶頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn){ p=Get(L,i-1);//調(diào)用算法2.9，找第i-1個(gè)結(jié)點(diǎn)① if(p!=NULL&&p->next!=NULL)//第i-1個(gè)結(jié)點(diǎn)和第i個(gè)結(jié)點(diǎn)均存在 { r=p->next;//r指向*p的后繼結(jié)點(diǎn)② p->next=r->next;//刪除結(jié)點(diǎn)*r③ free(r);//釋放結(jié)點(diǎn)*r所占的存儲(chǔ)空間 } elseprintf("第i個(gè)結(jié)點(diǎn)不存在");}53循環(huán)鏈表

循環(huán)鏈表的一種形式是單循環(huán)鏈表。其特點(diǎn)是單鏈表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)或開始結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)，從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)。54【例2.4】在單循環(huán)鏈表上實(shí)現(xiàn)將兩個(gè)線性表（a1,a2,…,am）和（b1,b2,…,bn）合并為一個(gè)循環(huán)鏈表（a1,…,am,b1,…,bn）的運(yùn)算。（1）采用尾指針，為指針指向終端結(jié)點(diǎn)，在算法中沒有循環(huán)，算法的時(shí)間復(fù)雜度為O(1)。（2）采用頭指針，分別需要找到La表和Lb表的終端結(jié)點(diǎn)，需要兩個(gè)循環(huán)的并列，算法的時(shí)間復(fù)雜度為O(Length(La)+Length(Lb))。55雙向鏈表（雙向循環(huán)鏈表）

雙向鏈表結(jié)點(diǎn)的結(jié)構(gòu)體類型定義：typedefstructdnode{datatypedata; //data為結(jié)點(diǎn)的數(shù)據(jù)域structdnode*prior,*next;//prior和next分別是結(jié)點(diǎn)的前驅(qū)和后繼指針域}dlinklist;dlinklist*head;56雙向鏈表將頭結(jié)點(diǎn)和終端結(jié)點(diǎn)鏈接起來，構(gòu)成順時(shí)針和逆時(shí)針的兩個(gè)環(huán)。

雙向鏈表可以“后插”，也可以“前插”?！舅惴?.13】雙向鏈表的后插voidDInsertAfter(dlinklist*p,datatypex){//在帶頭結(jié)點(diǎn)的非空雙向鏈表中,將值為x的新結(jié)點(diǎn)插入*p之后

dlinklist*s=(dlinklist*)malloc(sizeof(dlinklist));//生成新結(jié)點(diǎn)① s->data=x;

s->prior=p; //*s的前驅(qū)指針域指向*p②

s->next=p->next; //*s的后繼指針域指向*p的后繼結(jié)點(diǎn)③

p->next->prior=s; //*p的后繼結(jié)點(diǎn)的前驅(qū)指針域指向*s④

p->next=s; //*p的后繼指針域指向*s⑤}//時(shí)間復(fù)雜度為O(1)57【算法2.14】雙向鏈表的前插voidDInsertBefore(dlinklist*p,datatypex){//在帶頭結(jié)點(diǎn)的非空雙向鏈表中,將值為x的新結(jié)點(diǎn)插入*p之前

dlinklist*s=(dlinklist*)malloc(sizeof(dlinklist));//生成新結(jié)點(diǎn)① s->data=x;

s->prior=p->prior; //*s的前驅(qū)指針域指向*p的前驅(qū)結(jié)點(diǎn)②

s->next=p; //*s的后繼指針域指向*p③

p->prior->next=s; //*p的前驅(qū)結(jié)點(diǎn)的后繼指針域指向*s④ p->prior=s; //*p的前驅(qū)指針域指向*s⑤}//時(shí)間復(fù)雜度為O(1)58

在雙向鏈表中刪除一個(gè)結(jié)點(diǎn)也是比較靈活的?！舅惴?.15】雙向鏈表的刪除voidDDelete(dlinklist*p){//在帶頭結(jié)點(diǎn)的非空雙向鏈表中,刪除結(jié)點(diǎn)*p,設(shè)*p為非終端結(jié)點(diǎn) p->prior->next=p->next;//*p的前驅(qū)結(jié)點(diǎn)的后繼指針域指向*p的后繼結(jié)點(diǎn)①

p->next->prior=p->prior;//*p的后繼結(jié)點(diǎn)的前驅(qū)指針域指向*p的前驅(qū)結(jié)點(diǎn)②

free(p);//釋放結(jié)點(diǎn)*p}//時(shí)間復(fù)雜度為O(1)592.4順序表與鏈表的比較

6061

習(xí)題2（第2章作業(yè)）

習(xí)題2中的第一、二、三題寫在教材上，盡可能都做，在上課時(shí)會(huì)抽查。習(xí)題2中的第四題寫在作業(yè)本上，作業(yè)本要交。四、簡答及算法設(shè)計(jì)1、2、6、9第3章棧和隊(duì)列棧和隊(duì)列也屬于線性結(jié)構(gòu)，它們的邏輯結(jié)構(gòu)和線性表相同。存儲(chǔ)方式有順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)，只是其運(yùn)算規(guī)則較線性表有更多的限制，因此，可以稱為操作受限的線性表。62【本章重點(diǎn)】①棧和隊(duì)列的操作特性；②基于順序棧和鏈棧的基本運(yùn)算的實(shí)現(xiàn)；③基于循環(huán)隊(duì)列和鏈隊(duì)列的基本運(yùn)算的實(shí)現(xiàn)。63【本章難點(diǎn)】①多個(gè)棧共享空間的算法設(shè)計(jì)；②循環(huán)隊(duì)列的組織及隊(duì)空和隊(duì)滿的判定條件；③基于棧、隊(duì)列的算法設(shè)計(jì)及應(yīng)用。64【本章內(nèi)容】棧隊(duì)列棧和隊(duì)列的應(yīng)用舉例習(xí)題3653.1棧棧的定義：棧是限定僅在表的一端進(jìn)行插入或刪除操作的線性表。插入、刪除的一端稱為棧頂（Top），另一端稱為棧底（Bottom）。棧是一種后進(jìn)先出的（LastInFirstOut）的線性表。棧可以是空?；蚍强諚！τ诜强諚=(a1,a2,…,an),a1是棧底元素,an是棧頂元素。如果進(jìn)棧的順序是a1,a2,…,an，n個(gè)元素全部進(jìn)棧后再出棧，其順序正好相反。66棧的常用基本運(yùn)算（1）InitStack(&S)棧初始化，操作結(jié)果是構(gòu)造一個(gè)空棧S。（2）SetNull(S)置空棧，棧S已存在，將棧S清為空棧。（3）Empty(S)判斷棧空，若棧S為空則返回“真”值；否則返回“假”值。（4）Push(S，x)進(jìn)棧，若棧S不滿，將數(shù)據(jù)元素x插入棧頂，并返回入棧是否成功的狀態(tài)信息。入棧操作會(huì)改變棧的內(nèi)容。（5）Pop(S,&x)出棧，若棧S非空，刪除棧頂數(shù)據(jù)元素，通過參數(shù)x帶回棧頂元素，并返回出棧是否成功的狀態(tài)信息。出棧操作會(huì)使棧的內(nèi)容發(fā)生變化。（6）GetTop(S,&x)取棧頂元素，若棧S非空，通過參數(shù)x帶回棧頂元素，并返回取棧頂元素是否成功的狀態(tài)信息。該操作完成后，棧的內(nèi)容不變。67棧的基本運(yùn)算應(yīng)用舉例【例3.1】將一個(gè)非負(fù)的十進(jìn)制整數(shù)轉(zhuǎn)換為其它進(jìn)制數(shù)（二、八、十六進(jìn)制），利用棧來實(shí)現(xiàn)。voidConversion(intn,intbase)//以十進(jìn)制數(shù)和基數(shù)作為參數(shù){ Stack*S;intbit; InitStack(S);//建立空棧

while(n!=0)

{ Push(S,n%base);//余數(shù)入棧

n=n/base; //整除基數(shù)

}

while(!EmptyStack(S))

{ bit=Pop(S);//余數(shù)出棧

if(bit>9)printf("%c",bit+55);//將余數(shù)轉(zhuǎn)為字符輸出

elseprintf("%c",bit+48); }

printf("\n");}68采用除基數(shù)取余的算法，例如將十進(jìn)制數(shù)123轉(zhuǎn)換為八進(jìn)制數(shù)173，采用棧存放余數(shù)，入棧順序是3、7、1，出棧順序是1、7、3。棧的順序存儲(chǔ)結(jié)構(gòu)和基本運(yùn)算的實(shí)現(xiàn)1、棧的順序存儲(chǔ)結(jié)構(gòu)——順序棧

棧的順序存儲(chǔ)結(jié)構(gòu)簡稱順序棧。順序棧采用一維數(shù)組來存儲(chǔ)，并且用一個(gè)稱為棧頂指針的整型量Top指示當(dāng)前棧頂?shù)奈恢谩?/p>

順序棧的類型定義如下： typedefstruct {

datatypedata[maxsize]; //棧中元素存儲(chǔ)空間

intTop; //棧頂指針 }SeqStack;69如果把數(shù)組中下標(biāo)為0的一端作為棧底，那么S->data[0]是棧底元素，S->data[S->Top]是棧頂元素。當(dāng)S->Top=-1時(shí)為空棧，滿棧時(shí)S->Top=maxsize-1。對于順序棧，入棧時(shí)要先判斷棧是否已滿，棧滿簡稱為“上溢”；出棧時(shí)需判斷棧是否為空，?？蘸喎Q為“下溢”。入棧操作S->Top加一，出棧操作S->Top減一。2、順序?；具\(yùn)算的實(shí)現(xiàn)（1）棧初始化 voidInitStack(SeqStack*&S) //構(gòu)造一個(gè)空棧S {S=(SeqStack*)malloc(sizeof(SeqStack));//生成順序?？臻g

S->Top=-1; //棧頂指針置為-1 }（2）置空棧 voidSetNull(SeqStack*S) //將棧S置為空棧 {S->Top=-1; //棧頂指針置為-1 }70（3）判斷棧空 intEmpty(SeqStack*S) //若棧S為空棧，返回1；否則返回0 { if(S->Top==-1)return1; elsereturn0; }（4）入棧 intPush(SeqStack*S,datatypex) //若棧S未滿，則將元素x插入棧頂，并返回1，表示入棧成功；否則返回0，表示入棧不成功 { if(S->Top==maxsize-1) {printf("棧上溢"); return0; }//上溢 else {S->data[++S->Top]=x; return1; } }71（5）出棧

intPop(SeqStack*S,datatype&x)//若棧不空，則刪除棧頂元素，由參數(shù)x帶回棧頂元素，并返回1，表示出棧成功；否則返回0，表示出棧失敗 {if(Empty(S))//判斷棧是否為空

{printf("棧下溢");

return0;

}//下溢

else

{x=S->data[S->Top--];

return1;

} }72（6）取棧頂元素 intGetTop(SeqStack*S,datatype&x) //若棧不空，則刪除棧頂元素，由x帶回棧頂元素，并返回1，表示取棧頂元素成功；否則返回0，表示取棧頂元素失敗 {if(EmptyS(S))//調(diào)用算法4.3，判斷棧是否為空

{printf("棧下溢");

return0;

}//下溢

else

{x=S->data[S->Top];

return1;

} }73兩個(gè)順序棧共享連續(xù)空間，降低溢出的概率進(jìn)棧操作的算法：voidpush(SeqStack*S,datatypex,inti)//將元素x插入i號(hào)棧{if(S->Top1+1==S->Top2)printf("數(shù)組空間已占滿，發(fā)生上溢");elseif(i==1){S->Top1++;S->v[S->Top1]=x;} //入1號(hào)棧else{S->Top2--;S->v[S->Top2]=x;} //入2號(hào)棧}74出棧操作的算法：datatypepop(SeqStack*S,inti)//i號(hào)棧的棧頂元素出棧{datatypex;if(i==1)

if(S->Top1==-1)printf(“1號(hào)棧下溢”);

else{x=S->v[S->Top1];S->Top1--;}//1號(hào)棧出棧else

if(S->top2==maxsize)printf(“2號(hào)棧下溢”);

else{x=S->v[S->Top2];S->Top2++;}//2號(hào)棧出棧returnx;//返回出棧元素的值}75【例3.2】檢查表達(dá)式中的括號(hào)是否匹配。

以表達(dá)式((1+2)*3-4)/5為例。表達(dá)式作為字符串存儲(chǔ)在字符數(shù)組ex中，charex[]="((1+2)*3-4)/5";

在檢查過程中，對字符數(shù)組進(jìn)行掃描，當(dāng)遇到“(”時(shí)入棧，遇到“)”時(shí)出棧。當(dāng)整個(gè)表達(dá)式掃描完畢時(shí)，若棧為空，則表達(dá)式中的括號(hào)是匹配的；否則不匹配。voidcorrent(charex[]){ SeqStack*S; InitStack(S); i=0; while(i<length) { ch=ex[i]; switch(ch) { case'(':Push(S,ch);

break; case')':if(Empty(S)||Pop(S)!='(')

return"期望("; } i++; } if(!Empty(S)) return"期望)"; elsereturn"OK";}76棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和基本運(yùn)算的實(shí)現(xiàn)1、棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)棧的鏈接存儲(chǔ)結(jié)構(gòu)（鏈棧）用單鏈表來表示。鏈棧的結(jié)點(diǎn)結(jié)構(gòu)類型定義如下：typedefstructnone{datatypedata; //data為結(jié)點(diǎn)的數(shù)據(jù)信息structnode*next; //next為后繼結(jié)點(diǎn)的指針}StackNode; //鏈棧結(jié)點(diǎn)類型typedefstruct{StackNode*Top; //指向棧頂結(jié)點(diǎn)的指針}LinkStack;//含有棧頂指針Top的鏈棧結(jié)構(gòu)體類型77將單鏈表的表頭作為棧頂，由于只能在棧頂進(jìn)行入棧和出棧操作，所以只能在單鏈表的表頭進(jìn)行插入和刪除。78S是LinkStack類型的指針，指向鏈棧，可以看作是棧的接口。Top是棧頂指針，指向棧頂結(jié)點(diǎn)，當(dāng)Top等于NULL時(shí)，為空棧。2、鏈?；具\(yùn)算的實(shí)現(xiàn)鏈棧的入棧和出棧都是在棧頂（單鏈表的表頭）進(jìn)行，所以算法的時(shí)間復(fù)雜度均為O(1)。79【算法3.7】建立空鏈棧。voidInitStack(LinkStack*&S)//構(gòu)造一個(gè)空棧S{S=(LinkStack*)malloc(sizeof(LinkStack));S->Top=NULL;}【算法3.8】鏈棧置空。voidSetNull(LinkStack*S)//將棧S置為空棧{S->Top=NULL;}【算法3.9】鏈棧入棧。voidPush(LinkStack*S,datatypex)//將元素x入棧{StackNode*p=(StackNode*)malloc(sizeof(StackNode));

p->data=x;p->next=S->Top;//將新結(jié)點(diǎn)*p插入棧頂 S->Top=p;}80由于鏈棧不存在上溢的問題，所以在入棧時(shí)不需要判斷棧滿的情況81【算法3.10】鏈棧棧頂元素出棧。intPop(LinkStack*S,datatype&x)//若棧非空，則刪除棧頂元素，由x帶回棧頂元素，并返回1；否則返回0{StackNode*p=S->Top;//指針p指向棧頂結(jié)點(diǎn)if(Empty(S))//判斷棧是否為空{(diào)printf("棧下溢");return0;}//下溢else{ x=p->data;

S->Top=p->next;//將棧頂結(jié)點(diǎn)*p從鏈上摘下

free(p);//釋放原棧頂結(jié)點(diǎn)空間

return1;}}82【算法3.11】取鏈棧的棧頂元素。intGetTop(LinkStack*S,datatype&x)//若棧非空，則取棧頂元素，由x帶回棧頂元素，并返回1；否則返回0{StackNode*p=S->Top;//指針p指向棧頂結(jié)點(diǎn)if(Empty(S))//判斷棧是否為空{(diào)printf("棧下溢");return0;}//下溢else{ x=p->data;

return1;}}在鏈棧中取棧頂元素與出棧是類似的，只是沒有下面兩條語句：S->Top=p->next;//將棧頂結(jié)點(diǎn)*p從鏈上摘下free(p);//釋放原棧頂結(jié)點(diǎn)空間3.2隊(duì)列1、隊(duì)列的定義及基本運(yùn)算隊(duì)列也是一種運(yùn)算受限的線性表。它只允許在表的一端進(jìn)行插入，該端稱為隊(duì)尾（Rear）；在表的另一端進(jìn)行刪除，該端稱為隊(duì)頭（Front)。隊(duì)列亦稱作先進(jìn)先出（FirstInFirstOut）的線性表，簡稱為FIFO表。當(dāng)隊(duì)列中沒有元素時(shí)稱為空隊(duì)列。83隊(duì)列的主要基本運(yùn)算（1）InitQueue(&Q)隊(duì)列初始化。構(gòu)造一個(gè)空隊(duì)列Q。（2）SetNull(Q)置空隊(duì)。將隊(duì)列Q清空。（3）Length(Q)求隊(duì)列長度。返回隊(duì)列中元素的個(gè)數(shù)。（4）Empty(Q)判空隊(duì)。若隊(duì)列Q為空隊(duì)列，返回“真”值；否則返回“假”值。（5）EnQueue(Q,x)入隊(duì)。若隊(duì)列Q非滿，將元素X插入Q的隊(duì)尾。（6）DeQueue(Q)出隊(duì)。若隊(duì)列Q非空，刪除隊(duì)頭元素，返回Q的隊(duì)頭元素。（7）GetFront(Q)取隊(duì)頭元素。若隊(duì)列Q非空，返回Q的隊(duì)頭元素。Q中元素保持不變。84隊(duì)列的基本運(yùn)算應(yīng)用【例】利用隊(duì)列Q將棧S中的元素逆置。voidreverseS(Stack*S){InitQueue(&Q);while(!EmptyStack(S))EnQueue(Q,Pop(S));while(!Empty(Q))Push(S,DeQueue(Q));}851、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)——順序隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列，采用數(shù)組存儲(chǔ)隊(duì)列中的元素。我們約定，在非空隊(duì)列中隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針rear指向隊(duì)尾元素的位置。（也可以約定，隊(duì)頭指針front指向隊(duì)頭元素的位置，隊(duì)尾指針rear指向隊(duì)尾元素的后一個(gè)位置）如果是空隊(duì)，隊(duì)頭、隊(duì)尾指針相等。隊(duì)尾指針減去對頭指針就是隊(duì)列的長度。順序隊(duì)列的結(jié)構(gòu)類型定義如下：typedefstruct{datatypedata[maxsize];intfront;intrear;}SeQueue;SeQueue*sq=(SeQueue*)malloc(sizeof(SeQueue));86隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和基本運(yùn)算的實(shí)現(xiàn)循環(huán)隊(duì)列

順序隊(duì)列中可能出現(xiàn)“上溢”和“下溢”情況，并且還存在“假上溢”現(xiàn)象，例如在教材中圖3.6中的（c）或（d）的情況下，再進(jìn)行入隊(duì)操作，則出現(xiàn)“假上溢”。

循環(huán)隊(duì)列可以解決“假上溢”問題。87sq->rear=(sq->rear+1)%maxsize;sq->front=(sq->front+1)%maxsize;在循環(huán)隊(duì)列中區(qū)分空隊(duì)和滿隊(duì)的方法在循環(huán)隊(duì)列中，由于入隊(duì)時(shí)尾指針向前追趕頭指針，出隊(duì)時(shí)頭指針向前追趕尾指針，在隊(duì)空和隊(duì)滿時(shí)都有sq->front等于sq->rear，無法區(qū)分空隊(duì)和滿隊(duì)。如果在循環(huán)隊(duì)列中少用一個(gè)元素空間，則可以區(qū)分空隊(duì)和滿隊(duì)。判斷空隊(duì)的條件：sq->rear==sq->front判斷滿隊(duì)的條件：sq->front==(sq->rear+1)%maxsize882、循環(huán)隊(duì)列基本運(yùn)算的實(shí)現(xiàn)89【算法3.12】生成空循環(huán)隊(duì)列。voidInitQueue(SeQueue*&sq)//建立空循環(huán)隊(duì)列sq{ sq=(SeQueue*)malloc(sizeof(SeQueue));

sq->front=sq->rear=0;/*對于循環(huán)隊(duì)列來說，只要隊(duì)頭和隊(duì)尾指針相等即為空隊(duì)，所以這里置為0~maxsize-1之間的任何一個(gè)值都可以，但一般置為0*/}【算法3.13】循環(huán)隊(duì)列置空。voidSetNull(SeQueue*sq)//置隊(duì)列sq為空隊(duì){sq->front=sq->rear=0;}90【算法3.14】求循環(huán)隊(duì)列長度intLength(SeQueue*sq){return(sq->rear-sq->front+maxsize)%maxsize;}【算法3.15】循環(huán)隊(duì)列入隊(duì)。intEnqueue(sequeue*sq,datatypex)//將新元素x插入隊(duì)列*sq的隊(duì)尾，入隊(duì)成功返回1，不成功返回0{ if(sq->front==(sq->rear+1)％maxsize) {printf("隊(duì)列上溢");return(0);} else{sq->rear=(sq->rear+1)％maxsize;sq->data[sq->rear]=x;return(1); }}91【算法3.16】循環(huán)隊(duì)列出隊(duì)intDequeue(SeQueue*sq,datatype&x)//通過參數(shù)x帶回該元素值，出隊(duì)成功返回1，不成功返回0{ if(sq->rear==sq->front) {printf("隊(duì)列下溢");return(0);} else{sq->front=(sq->front+1)％maxsize;x=sq->data[sq->front];return(1); }}92【算法3.17】取循環(huán)隊(duì)列的隊(duì)頭元素intGetFront(SeQueue*sq,datatype&x)//通過參數(shù)x帶回該元素值，取隊(duì)頭元素成功返回1，不成功返回0{if(sq->rear==sq->front){

printf("隊(duì)列下溢");return(0);}

else{

x=sq->data[(sq->front+1)%maxsize];

return(1);

}}93【例】如果循環(huán)隊(duì)列只有頭指針front和隊(duì)列長度len，實(shí)現(xiàn)隊(duì)列的基本運(yùn)算。結(jié)構(gòu)類型定義如下：typedefstruct{datatypedata[maxsize];intfront,len;}sequeue;sequeue*sq;說明：由于可以區(qū)分空隊(duì)和滿隊(duì)，所以不需要少用一個(gè)存儲(chǔ)單元?？贞?duì)：sq->len==0成立滿隊(duì)：sq->len==maxsize成立94（1）隊(duì)列初始化voidinit(sequeue*&sq){sq=(sequeue*)malloc(sizeof(sequeue));sq->front=maxsize-1;sq->len=0;}（2）置空隊(duì)voidsetnull(sequeue*sq){sq->len=0;}95（3）判隊(duì)空intempty(sequeue*sq){if(sq->len==0)return(1);elsereturn(0);}（4）入隊(duì)intenter(sequeue*sq,datatypex){if(sq->len==maxsize){printf(“queueisfull”);return(0);}//隊(duì)列中最多可容納maxsize個(gè)元素

else{sq->len++;sq->data[(sq->front+sq->len)%maxsize]=x;return(1);}}入隊(duì)時(shí)隊(duì)尾指針的操作，相當(dāng)于：sq->len++;(sq->front+sq->len)%maxsize96（5）出隊(duì)intdel(sequeue*sq,datatype&x){if(empty(sq)){printf(“queueisempty”);return(0);}else{sq->front=(sq->front+1)%maxsize;sq->len--;x=sq->data[sq->front];return(1);}}（6）取隊(duì)頭元素intget(sequeue*sq,datatype&x){if(empty(sq){printf(“queueisempty”);return(0);}else{x=sq->data[(sq->front+1)%maxsize];return(1);}}隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和基本運(yùn)算的實(shí)現(xiàn)鏈隊(duì)列的結(jié)構(gòu)類型定義：typedefstructnode{datatypedata;structnode*next;}QueueNode;//鏈隊(duì)列的結(jié)點(diǎn)類型typedefstruct{QueueNode*front,*rear;}LinkQueue;//隊(duì)頭、隊(duì)尾指針的結(jié)構(gòu)體類型LinkQueue*q;將鏈隊(duì)列的頭指針和尾指針封裝在一起，作為一個(gè)結(jié)構(gòu)體類型q為LinkQueue類型的指針97鏈隊(duì)列基本運(yùn)算的實(shí)現(xiàn)98算法3.18生成空鏈隊(duì)列。voidInitQueue(LinkQueue*&q){q=(LinkQueue*)malloc(sizeof(LinkQueue));//產(chǎn)生隊(duì)頭、隊(duì)尾指針結(jié)構(gòu)體q->front=q->rear=(QueueNode*)malloc(sizeof(QueueNode));//產(chǎn)生頭結(jié)點(diǎn)q->front->next=NULL;//頭結(jié)點(diǎn)指針域置空}算法3.19鏈隊(duì)列置空。voidSetNull(LinkQueue*q){q->rear=q->front; //尾指針也指向頭結(jié)點(diǎn)q->front->next=NULL; //頭結(jié)點(diǎn)指針域置空}算法3.20鏈隊(duì)列判空隊(duì)。intEmpty(LinkQueue*q){if(q->front==q->rear)return(1);elsereturn(0);}99算法3.21鏈隊(duì)列入隊(duì)。voidEnQueue(LinkQueue*q,datatypex)//將新元素x加入鏈隊(duì)列*q{q->rear->next=(QueueNode*)malloc(sizeof(QueueNode));//新結(jié)點(diǎn)插入隊(duì)尾q->rear=q->rear->next;//尾指針指向新結(jié)點(diǎn)q->rear->data=x;//給新結(jié)點(diǎn)賦值q->rear->next=NULL;//隊(duì)尾結(jié)點(diǎn)的指針域置空}//鏈隊(duì)列不會(huì)出現(xiàn)“上溢”的情況，入隊(duì)時(shí)不需要判斷隊(duì)滿100算法3.22鏈隊(duì)列出隊(duì)。intDeQueue(LinkQueue*q,datatype&x)//通過參數(shù)x帶回該元素值，出隊(duì)成功返回1，不成功返回0{QueueNode*s;if(Empty(q)){printf("隊(duì)列下溢");return(0);}else{s=q->front->next;//s指向被刪除的隊(duì)頭結(jié)點(diǎn)

if(s->next==NULL){//當(dāng)前鏈隊(duì)列的長度等于1，出隊(duì)后為空隊(duì)

q->front->next=NULL;q->rear=q->front;//置為空隊(duì)

}

elseq->front->next=s->next;//隊(duì)列的長度大于1，修改頭結(jié)點(diǎn)的指針域

x=s->data;

free(s);//釋放被刪除的結(jié)點(diǎn)空間

return(1);

}}101算法3.23取鏈隊(duì)列的隊(duì)頭元素。intGetFront(LinkQueue*q,datatype&x)//通過參數(shù)x帶回隊(duì)頭元素值，取隊(duì)頭元素成功返回1，不成功返回0{if(Empty(q)){printf("隊(duì)列下溢");return(0);}else{x=q->front->next->data;return(1);}}例4.3用帶有頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)隊(duì)尾指針rear，編寫入隊(duì)和出隊(duì)算法?？梢詫ear->next->next看作隊(duì)頭指針。根據(jù)隊(duì)列長度的不同，出隊(duì)操作需考慮出隊(duì)之前隊(duì)列為空隊(duì)、長度等于1和大于1三種不同的情況。如果出隊(duì)之前隊(duì)列長度為1，那么出隊(duì)之后就是空隊(duì)了。（1）入隊(duì)算法102voidEnQueue(QueueNode*&rear,datatypex){QueueNode*p;p=(QueueNode*)malloc(sizeof(QueueNode));p->data=x; p->next=rear->next; rear->next=p; rear=p;}（2）出隊(duì)算法103intDelQueue(QueueNode*&rear,datatype&x){QueueNode*p;if(rear==rear->next){printf("隊(duì)列下溢");return(0);}else{ p=rear->next->next;x=p->data;