數(shù)據(jù)結(jié)構(gòu)

使用C語言(第7版)第1章緒論主要知識點數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型和軟件構(gòu)造方法算法和算法的時間復雜度1.1數(shù)據(jù)結(jié)構(gòu)的基本概念基本術(shù)語(1)數(shù)據(jù)：人們利用文字符號、數(shù)字符號以及其他規(guī)定的符號對現(xiàn)實世界的事物及其活動所做的抽象描述。(2)數(shù)據(jù)元素：表示一個事物的一組數(shù)據(jù)。(3)數(shù)據(jù)項：構(gòu)成數(shù)據(jù)元素的數(shù)據(jù)。例如，學生信息可包括學生的學號、姓名、性別、年齡等數(shù)據(jù)。這些數(shù)據(jù)構(gòu)成學生情況的描述的數(shù)據(jù)項；包括學號、姓名、性別、年齡等數(shù)據(jù)項的一組數(shù)據(jù)就構(gòu)成學生信息的一個數(shù)據(jù)元素?；拘g(shù)語(4)抽象數(shù)據(jù)元素：沒有實際含義的數(shù)據(jù)元素。(5)抽象數(shù)據(jù)元素的數(shù)據(jù)類型：沒有確切定義的數(shù)據(jù)類型。(6)數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的相互聯(lián)系方式。(7)數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)元素在計算機中的存儲方式。(8)數(shù)據(jù)的操作：對一種數(shù)據(jù)類型的數(shù)據(jù)進行的某種處理。(9)數(shù)據(jù)的操作集合：對一種數(shù)據(jù)類型的數(shù)據(jù)進行的所有操作。數(shù)據(jù)的邏輯結(jié)構(gòu)線性結(jié)構(gòu)：除第一個和最后一個數(shù)據(jù)元素外，每個數(shù)據(jù)元素只有一個前驅(qū)和一個后繼數(shù)據(jù)元素。樹結(jié)構(gòu)：除根結(jié)點外，每個數(shù)據(jù)元素只有一個前驅(qū)數(shù)據(jù)元素，可有０個或若干個后繼數(shù)據(jù)元素。圖結(jié)構(gòu)：每個數(shù)據(jù)元素可有０個或若干個前驅(qū)數(shù)據(jù)元素和０個或若干個后繼數(shù)據(jù)元素。線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)：把數(shù)據(jù)元素存儲在一塊連續(xù)地址空間的內(nèi)存中，其特點是邏輯上相鄰的數(shù)據(jù)元素在物理上也相鄰，數(shù)據(jù)間的邏輯關(guān)系表現(xiàn)在數(shù)據(jù)元素存儲位置關(guān)系上。指針是指向物理存儲單元地址的變量。由數(shù)據(jù)元素域和指針域組成的一個結(jié)構(gòu)體稱為結(jié)點。鏈式存儲結(jié)構(gòu)：使用指針把相互直接關(guān)聯(lián)的結(jié)點(即直接前驅(qū)結(jié)點或直接后繼結(jié)點)鏈接起來，其特點是邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰，數(shù)據(jù)間的邏輯關(guān)系表現(xiàn)在結(jié)點的鏈接關(guān)系上。順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)數(shù)據(jù)的操作

從抽象角度，數(shù)據(jù)的操作主要討論某種數(shù)據(jù)類型數(shù)據(jù)應(yīng)具備操作的邏輯功能。抽象角度下的操作一般和數(shù)據(jù)的邏輯結(jié)構(gòu)一起討論。具體說，數(shù)據(jù)的操作主要討論操作的具體實現(xiàn)算法。具體問題的操作實現(xiàn)必須在數(shù)據(jù)的存儲結(jié)構(gòu)確定后才能進行。

數(shù)據(jù)結(jié)構(gòu)課程主要討論表、堆棧、隊列、串、數(shù)組、樹、二叉樹、圖等典型的常用數(shù)據(jù)結(jié)構(gòu)。在討論這些典型數(shù)據(jù)結(jié)構(gòu)時，主要從它們的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)操作三個方面進行分析討論。另外，還討論查找和排序算法的實現(xiàn)方法。1.2抽象數(shù)據(jù)類型和軟件構(gòu)造方法類型是一組值的集合。數(shù)據(jù)類型是指一個類型和定義在這個類型上的操作集合。抽象數(shù)據(jù)類型是指一個邏輯概念上的類型和這個類型上的操作集合。數(shù)據(jù)類型和抽象數(shù)據(jù)類型的不同之處僅僅在于數(shù)據(jù)類型指的是高級程序設(shè)計語言支持的基本數(shù)據(jù)類型，而抽象數(shù)據(jù)類型指的是在基本數(shù)據(jù)類型支持下用戶新設(shè)計的數(shù)據(jù)類型。

抽象數(shù)據(jù)類型使軟件設(shè)計成為工業(yè)化流水線生產(chǎn)的一個中間環(huán)節(jié)。一方面，根據(jù)給出的抽象數(shù)據(jù)類型的功能定義，負責設(shè)計這些抽象數(shù)據(jù)類型的專門公司設(shè)計該抽象數(shù)據(jù)類型的具體存儲結(jié)構(gòu)以及在具體存儲結(jié)構(gòu)下各操作的具體實現(xiàn)算法；另一方面，利用已設(shè)計實現(xiàn)的抽象數(shù)據(jù)類型模塊，負責設(shè)計應(yīng)用軟件的專門公司可以安全、快速、方便的完成應(yīng)用軟件系統(tǒng)的設(shè)計。

軟件的設(shè)計采用模塊化方法，抽象數(shù)據(jù)類型就是構(gòu)造大型軟件的最基本模塊。1.3算法及其時間復雜度算法是描述求解問題方法的操作步驟集合。描述算法的語言形式1.文字形式:用中文或英文這樣的文字來描述算法。2.偽碼形式:用一種仿程序設(shè)計語言的語言來描述算法。3.程序設(shè)計語言形式:用某種程序設(shè)計語言描述算法。其優(yōu)點是算法不用修改，直接作為程序語句鍵入計算機，計算機能調(diào)用和運行。例1-1:設(shè)計一個把存儲在數(shù)組中的有n個抽象數(shù)據(jù)元素a0,a1,…,an-1逆置的算法，要求逆置后的新數(shù)組b中數(shù)據(jù)元素序列為an-1,…,a1,a0,并要求原數(shù)組中的數(shù)據(jù)元素值不被改變。voidReverse(intn,DataTypea[],DataTypeb[]){inti;for(i=0;i<n;i++)b[i]=a[n-1-i];//把數(shù)組a的元素逆置后賦給數(shù)組b}例1-2:設(shè)計一個把存儲在數(shù)組中的有n個抽象數(shù)據(jù)元素a0,a1,…,an-1就地逆置的算法，即要求逆置后的原數(shù)組中數(shù)據(jù)元素序列改變?yōu)閍n-1,…,a1,a0。voidReverse(intn,DataTypea[]){inti,m=n/2;DataTypetemp;for(i=0;i<m;i++){

//進行m次調(diào)換

temp=a[i];a[i]=a[n-1-i];a[n-1-i]=temp;}}

(1)輸入性(2)輸出性(3)有限性

(4)確定性(5)可執(zhí)行性算法滿足性質(zhì):

(1)正確性(2)可讀性(3)健壯性

(4)高時間效率(5)高空間效率算法設(shè)計目標:算法時間效率的度量算法的執(zhí)行時間需通過根據(jù)該算法編制的程序在計算機上運行時所消耗的時間來度量。方法有兩種:

(1)事后（實際）統(tǒng)計方法(2)事前（理論）分析方法程序運行消耗時間的有關(guān)因素:(1)書寫算法的程序設(shè)計語言(2)編譯產(chǎn)生的機器語言代碼質(zhì)量(3)機器執(zhí)行指令的速度(4)問題的規(guī)模，即算法的時間效率與算法所處理的數(shù)據(jù)個數(shù)n的函數(shù)關(guān)系。算法的時間效率是算法所處理的數(shù)據(jù)個數(shù)n的函數(shù)，算法的時間效率也稱作算法的時間復雜度。定義:T(n)=O(f(n)),當且僅當存在正常數(shù)c和n0，對所有的n(n≥n0)滿足T(n)≤c×f(n)。例1-3設(shè)數(shù)組a和b在前邊部分已賦值，求如下兩個n階矩陣相乘運算算法的時間復雜度。for(i=0;i<n;i++)for(j=0;j<n;j++){c[i][j]=0;//基本語句1for(k=0;k<n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j];//基本語句2}解:設(shè)基本語句的執(zhí)行次數(shù)為f(n),有f(n)=c1×n2+c2×n3,因 T(n)=f(n)=c1×n2+c2×n3≤c×n3,其中c1,c2,c均為常數(shù)，所以該算法的時間復雜度為

T(n)=O(n3)

例1-4設(shè)n為如下算法處理的數(shù)據(jù)個數(shù)，求如下算法的時間復雜度。

for(i=1;i<=n;i=2*i) cout<<"i="<<i;解:設(shè)基本語句的執(zhí)行次數(shù)為f(n),有2f(n)≤n,即有f(n)≤lbn。因T(n)=f(n)≤lbn≤c×

lbn,所以該算法的時間復雜度為

T(n)=O(lbn)。例1-5:下邊的算法是用冒泡排序法對數(shù)字a中的n個整數(shù)類型的數(shù)據(jù)元素(a[0]~a[n-1])，從小到大進行排序，求該算法的時間復雜度。voidBubbleSort(inta[],intn){inti,j,flag=1;inttemp;for(i=1;i<n&&flag==1;i++){flag=0;for(j=0;j<n-i;j++){if(a[j]>a[j+1]){flag=1;temp=a[j];a[j]=a[j+1];[j+1]=temp;}}}}解:設(shè)基本語句的執(zhí)行次數(shù)為f(n),最壞情況下有

f(n)≈n+4*n2/2因 T(n)=f(n)≈n+2*n2≤c*

n2,其中c為常數(shù)，所以該算法的時間復雜度為

T(n)=O(n2)。例1-6下面的算法是在一個有n個數(shù)據(jù)元素的數(shù)組a中刪除第i個位置的數(shù)組元素，要求當刪除成功時數(shù)組元素個數(shù)減1，求該算法的時間復雜度。其中數(shù)組下標從0至n-1。intDelete(inta[],int&n,inti){intj;if(i<0||i>=n)return0;//刪除位置錯誤，失敗返回for(j=i+1;j<n;j++)a[j-1]=a[j];//順次移位填補n--;//數(shù)組元素個數(shù)減1return1;//刪除成功返回}解:假設(shè)刪除任何位置上的數(shù)據(jù)元素都是等概率的,設(shè)Pi為刪除第i個位置上數(shù)據(jù)元素的概率，則有Pi=1/n，設(shè)E為刪除數(shù)組元素的平均次數(shù)，則有因T(n)=E≤(n+1)/2≤

c*n,其中c為常數(shù)，所以該算法的等概率平均時間復雜度為

T(n)=O(n)

例1-7對比在數(shù)據(jù)元素個數(shù)為30000時，冒泡排序算法和快速排序算法的實際耗時。根據(jù)問題的要求，設(shè)計測試程序，并在計算機上實際運行。程序運行結(jié)果：冒泡排序:6.00秒；快速排序:0.00秒程序運行結(jié)果說明：系統(tǒng)中的difftime(end,start)函數(shù)以秒為單位計時，快速排序的實際耗時少于0.5秒，所以輸出顯示為0.00秒。程序運行結(jié)果說明，當數(shù)據(jù)元素個數(shù)足夠大時，理論分析的快速排序算法優(yōu)于冒泡排序算法的結(jié)果，和程序的實際測試結(jié)果吻合。算法耗時的實際測試算法的時間復雜度是衡量一個算法好壞的重要指標。一般來說，具有多項式時間復雜度（如O(n)、O(n2)、O(n6)、O(n8)等）的算法，是可接受、可實際使用的算法；而具有指數(shù)時間復雜度（如O(2n)、O(nn)、O(n！)等）的算法，是理論上可以計算，但實際上不可計算的問題，通常稱作難解的問題。對于具有多項式時間復雜度的算法，無論數(shù)據(jù)元素個數(shù)多大（只要是有限的數(shù)值），算法都可以在有限的時間內(nèi)運行完成；而對于難解的問題，當n足夠小時，算法可以在有限的時間內(nèi)運行完成，當n比較大時，其運行時間將是一個天文數(shù)字！

數(shù)據(jù)元素個數(shù)和時間復雜度

習題1-1，1-2，1-5，1-7，1-8， 1-9，1-10，1-11習題1-13，1-14，1-15

作業(yè)

第2章線性表主要知識點線性表抽象數(shù)據(jù)類型順序表單鏈表循環(huán)單鏈表循環(huán)雙向鏈表靜態(tài)鏈表設(shè)計舉例2.1

線性表抽象數(shù)據(jù)類型1.線性表的定義線性表是一種可以在任意位置插入和刪除數(shù)據(jù)元素操作、由n(n≥0)個相同類型數(shù)據(jù)元素a0,a1,…,an-1組成的線性結(jié)構(gòu)。線性結(jié)構(gòu):2.線性表抽象數(shù)據(jù)類型數(shù)據(jù):｛a0,a1,…,an-1｝,ai的數(shù)據(jù)類型為DataType操作:(1)ListInitiate(L)初始化線性表(2)ListLength(L)求當前數(shù)據(jù)元素個數(shù)(3)ListInsert(L,i,x)插入數(shù)據(jù)元素(4)ListDelete(L,i,x)刪除數(shù)據(jù)元素(5)ListGet(L,i,x)取數(shù)據(jù)元素｛a0,a1,…,an-1｝表示數(shù)據(jù)元素有次序關(guān)系。2.2線性表的順序表示和實現(xiàn)1、順序表的存儲結(jié)構(gòu)

實現(xiàn)順序存儲結(jié)構(gòu)的方法是使用數(shù)組。數(shù)組把線性表的數(shù)據(jù)元素存儲在一塊連續(xù)地址空間的內(nèi)存單元中，這樣線性表中邏輯上相鄰的數(shù)據(jù)元素在物理存儲地址上也相鄰。數(shù)據(jù)元素間的邏輯上的前驅(qū)、后繼邏輯關(guān)系就表現(xiàn)在數(shù)據(jù)元素的存儲單元的物理前后位置上。順序表的存儲結(jié)構(gòu)如圖所示順序存儲結(jié)構(gòu)的線性表稱作順序表a0a1a2a3a4a5…listsize=6MaxSize-10123456其中a0,a1,

a2等表示順序表中存儲的數(shù)據(jù)元素，list表示順序表存儲數(shù)據(jù)元素的數(shù)組，MaxSize表示存儲順序表的數(shù)組的最大存儲單元個數(shù)，size表示順序表當前存儲的數(shù)據(jù)元素個數(shù)。

typedefstruct{DataTypelist[MaxSize]; intsize;}SeqList;2、順序表操作的實現(xiàn)

（1）初始化ListInitiate(L)voidListInitiate(SeqList*L) {L->size=0; //定義初始數(shù)據(jù)元素個數(shù)}

（2）求當前數(shù)據(jù)元素個數(shù)ListLength(L)intListLength(SeqListL) {returnL.size;}

（3）插入數(shù)據(jù)元素ListInsert(L,i,x)intListInsert(SeqList*L,inti,DataTypex){intj;for(j=L->size;j>i;j--)L->list[j]=L->list[j-1];

//從后向前依次后移

L->list[i]=x; //插入x L->size++; //元素個數(shù)加1

return1;}（4）刪除數(shù)據(jù)元素ListDelete(L,i,x)intListDelete(SeqList*L,inti,DataType*x) {intj;

*x=L->list[i]; //保存刪除的元素到x中

for(j=i+1;j<=L->size-1;j++)

L->list[j-1]=L->list[j];

//依次前移

L->size--; //數(shù)據(jù)元素個數(shù)減1

return1;}（5）取數(shù)據(jù)元素ListGet(L,i,x)intListGet(SeqListL,inti,DataType*x){if(i<0||i>L.size-1){printf("參數(shù)i不合法!\n"); return0;}else{ *x=L.list[i];return1;}}3、順序表操作的效率分析時間效率分析:算法時間主要耗費在移動元素的操作上，因此計算時間復雜度的基本操作(最深層語句頻度)T(n)=O(移動元素次數(shù))而移動元素的個數(shù)取決于插入或刪除元素的位置i.若i=size，則根本無需移動（特別快）；若i=0，則表中元素全部要后移（特別慢）；應(yīng)當考慮在各種位置插入（共n+1種可能）的平均移動次數(shù)才合理。設(shè)Pi是在第i個存儲位置插入一個數(shù)據(jù)元素的概率，順序表中的數(shù)據(jù)元素個數(shù)為n,當在順序表的任何位置上插入數(shù)據(jù)元素的概率相等時，有Pi=1/(n+1),則

插入時的平均移動次數(shù)為:n(n+1)/2÷（n+1）＝n/2≈O(n)同理可證:順序表刪除一元素的時間效率為:T（n)=(n-1)/2≈O(n)

順序表中的其余操作都和數(shù)據(jù)元素個數(shù)n無關(guān)，因此，在順序表中插入和刪除一個數(shù)據(jù)元素的時間復雜度為O(n),其余操作的時間復雜度都為O(1)主要優(yōu)點是算法簡單，空間單元利用率高；主要缺點是需要預先確定數(shù)據(jù)元素的最大個數(shù)，插入和刪除時需要移動較多的數(shù)據(jù)元素。主要優(yōu)缺點4、順序表應(yīng)用舉例例：編程實現(xiàn)如下任務(wù):建立一個線性表，首先依次輸入數(shù)據(jù)元素1，2，3，…，10，然后刪除數(shù)據(jù)元素5，最后依次顯示當前線性表中的數(shù)據(jù)元素。要求采用順序表實現(xiàn)，假設(shè)該順序表的數(shù)據(jù)元素個數(shù)在最壞情況下不會超過100個。

實現(xiàn)方法：

1、采用直接編寫一個主函數(shù)實現(xiàn)。

2、利用已設(shè)計實現(xiàn)的抽象數(shù)據(jù)類型模塊。（存放在頭文件名為SeqList.h中，通過#include“SeqList.h”）程序設(shè)計如下：#include<stdio.h> #defineMaxSize100 typedefintDataType;#include"SeqList.h"

voidmain(void){SeqListmyList;inti,x;ListInitiate(&myList);for(i=0;i<10;i++)ListInsert(&myList,i,i+1);ListDelete(&myList,4,&x);for(i=0;i<ListLength(myList);i++) ListGet(myList,i,&x);}程序運行結(jié)果：12346789102.3線性表的鏈式表示和實現(xiàn)1、單鏈表的結(jié)構(gòu)(1)單鏈表中構(gòu)成鏈表的結(jié)點只有一個指向直接后繼結(jié)點的指針域。其結(jié)構(gòu)特點：邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。結(jié)點結(jié)構(gòu)如圖示：指針域數(shù)據(jù)域nextdata或數(shù)據(jù)域：存儲元素數(shù)值數(shù)據(jù)指針域：存儲直接后繼的存儲位置(2)頭指針、頭結(jié)點和首元結(jié)點的區(qū)別頭指針頭結(jié)點首元結(jié)點a0heada1…an^示意圖如下：頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點、或為首元結(jié)點）的指針；頭結(jié)點是在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標志和表長等信息，它不計入表長度。首元結(jié)點是指鏈表中存儲線性表第一個數(shù)據(jù)元素a０的結(jié)點。(3)帶頭結(jié)點單鏈表和不帶頭結(jié)點單鏈表的比較pa0a1an-1∧…h(huán)eaddatanextx∧s(a)插入前pa0a1an-1∧…h(huán)eaddatanextx∧s(b)插入后1).在帶頭結(jié)點單鏈表第一個數(shù)據(jù)元素前插入結(jié)點2).刪除帶頭結(jié)點單鏈表第一個數(shù)據(jù)元素結(jié)點pa0a1an-1∧…h(huán)eaddatanext3).在不帶頭結(jié)點單鏈表第一個數(shù)據(jù)元素前插入結(jié)點a0a1an-1∧…h(huán)eadx∧s(a)插入前a0a1an-1∧…h(huán)eadxs(b)插入后4).在不帶頭結(jié)點單鏈表其他數(shù)據(jù)元素前插入結(jié)點pai-1a0aian-1∧…h(huán)eaddatanextxs…×5).刪除不帶頭結(jié)點單鏈表第一個數(shù)據(jù)元素結(jié)點a0a1an-1∧…h(huán)eaddatanext×6).刪除不帶頭結(jié)點單鏈表其他數(shù)據(jù)元素結(jié)點pai-1a0aian-1∧…h(huán)eaddatanext…×ai+1結(jié)論：（1）帶頭結(jié)點單鏈表無論在第一個數(shù)據(jù)元素結(jié)點前插入，還是在其他結(jié)點前插入，操作方法一樣；而不帶頭結(jié)點單鏈表在第一個數(shù)據(jù)元素結(jié)點前插入，和在其他結(jié)點前插入，操作方法不一樣（2）刪除操作和插入操作類似（3）設(shè)計帶頭結(jié)點單鏈表的算法時，頭指針參數(shù)可設(shè)計成輸入型參數(shù)；設(shè)計不帶頭結(jié)點單鏈表的算法時，頭指針參數(shù)必須設(shè)計成輸出型參數(shù)（4）因此，帶頭結(jié)點單鏈表的算法設(shè)計簡單結(jié)點定義：typedefstructNode{DataTypedata;structNode*next;}SLNode2、單鏈表的操作實現(xiàn)（1）初始化ListInitiate(head)voidListInitiate(SLNode**head){*head=(SLNode*)malloc(sizeof(SLNode));(*head)->next=NULL; }（2）求當前數(shù)據(jù)元素個數(shù)ListLength(head)intListLength(SLNode*head){SLNode*p=head;intsize=0; while(p->next!=NULL) {p=p->next; size++; }returnsize;}（3）插入ListInsert(head,i,x)intListInsert(SLNode*head,inti,DataTypex){SLNode*p,*q;intj;

p=head;j=-1; while(p->next!=NULL&&j<i-1){p=p->next;j++;}

if(j!=i-1){printf(“插入位置參數(shù)錯！”);return0;}

q=(SLNode*)malloc(sizeof(SLNode));q->data=x;q->next=p->next;p->next=q; return1;}說明：①要在帶頭結(jié)點的單鏈表第i（0≤i≤size）個結(jié)點前插入一個存放數(shù)據(jù)元素x的結(jié)點，首先要在單鏈表中尋找到第i-1個結(jié)點并由指針p指示，然后動態(tài)申請一個結(jié)點存儲空間并由指針q指示，并把數(shù)據(jù)元素x的值賦予新結(jié)點的數(shù)據(jù)元素域（即q->data=x），最后修改新結(jié)點的指針域指向ai結(jié)點（即q->next=p->next），并修改ai-1結(jié)點的指針域指向新結(jié)點q（即p->next=q）。②循環(huán)條件由兩個子條件邏輯與組成，其中子條件p->next!=NULL保證指針所指結(jié)點存在，子條件j<i-1保證最終讓指針p指向ai-1結(jié)點。

（4）刪除ListDelete(head,i,x)intListDelete(SLNode*head,inti,DataType*x){SLNode*p,*s;intj;

p=head;j=-1;while(p->next!=NULL&&p->next->next!=NULL&&j<i-1){p=p->next; j++;}

if(j!=i-1){printf(“插入位置參數(shù)錯！”); return0;}

s=p->next;*x=s->data;p->next=p->next->next;free(s);return1;}

說明：要在帶頭結(jié)點的單鏈表中刪除第i（0≤i≤size-1）個結(jié)點，首先要在單鏈表中尋找到第i-1個結(jié)點并由指針p指示，然后讓指針s指向ai結(jié)點（即s=p->next），并把數(shù)據(jù)元素ai的值賦予x（即*x=s->data），最后把ai結(jié)點脫鏈（即p->next=p->next->next），并動態(tài)釋放ai結(jié)點的存儲空間（即free(s)）。刪除過程如圖2-14所示。圖中的①對應(yīng)算法中的刪除語句。（5）取數(shù)據(jù)元素ListGet(head,i,x)intListGet(SLNode*head,inti,DataType*x){SLNode*p;intj;

p=head;j=-1;while(p->next!=NULL&&j<i){p=p->next; j++;}

if(j!=i){printf(“取元素位置參數(shù)錯！”); return0;}

*x=p->data;return1;}

（6）撤消單鏈表內(nèi)存空間Destroy(head)voidDestroy(SLNode**head){SLNode*p,*p1;

p=*head;while(p!=NULL){p1=p;p=p->next;free(p1); }*head=NULL;}4、單鏈表操作的效率分析單鏈表的插入和刪除操作不需移動數(shù)據(jù)元素，只需比較數(shù)據(jù)元素。因此，當在單鏈表的任何位置上插入數(shù)據(jù)元素的概率相等時，在單鏈表中插入一個數(shù)據(jù)元素時比較數(shù)據(jù)元素的平均次數(shù)為：刪除一個數(shù)據(jù)元素時比較數(shù)據(jù)元素的平均次數(shù)為：另外，單鏈表求數(shù)據(jù)元素個數(shù)操作的時間復雜度為O(n)。和順序表相比主要優(yōu)點是不需要預先確定數(shù)據(jù)元素的最大個數(shù)，插入和刪除操作不需要移動數(shù)據(jù)元素；主要缺點是查找數(shù)據(jù)元素時需要順序進行，不能像順序表那樣隨機查找任意一個數(shù)據(jù)元素。另外，每個結(jié)點中要有一個指針域，因此空間單元利用率不高。而且單鏈表操作的算法也較復雜。單鏈表和順序表相比，單鏈表的優(yōu)點和缺點正好相反。5、單鏈表應(yīng)用舉例例：編程實現(xiàn)如下任務(wù):建立一個線性表，首先依次輸入數(shù)據(jù)元素1，2，3，…，10，然后刪除數(shù)據(jù)元素5，最后依次顯示當前線性表中的數(shù)據(jù)元素。要求采用單鏈表實現(xiàn)。#include<stdio.h> #include<stdlib.h> #include<malloc.h>typedefintDataType;#include"LinList.h"

voidmain(void){SLNode*head;inti,x;ListInitiate(&head);

for(i=0;i<10;i++)ListInsert(head,i,i+1);ListDelete(head,4,&x); for(i=0;i<ListLength(head);i++){ListGet(head,i,&x)==0); printf(“%d”,x);

} Destroy(&head);}程序運行結(jié)果：12346789102.4循環(huán)單鏈表循環(huán)單鏈表是單鏈表的另一種形式，其結(jié)構(gòu)特點是鏈表中最后一個結(jié)點的指針域指向整個鏈表的第一個結(jié)點，從而使鏈表形成一個環(huán)。它的優(yōu)點是從鏈尾到鏈頭比較方便。循環(huán)單鏈表也有帶頭結(jié)點和不帶頭結(jié)點兩種結(jié)構(gòu)。一個帶頭結(jié)點的循環(huán)單鏈表如下圖示：a0a1an-1…h(huán)eadhead(a)空鏈表(b)非空鏈表程序設(shè)計：p!=NULL 改為 p!=headP->next!=NULL 改為 p->next!=head2.5雙向鏈表雙向鏈表是每個結(jié)點除后繼指針域外還有一個前驅(qū)指針域，它有帶頭結(jié)點和不帶頭結(jié)點，循環(huán)和非循環(huán)結(jié)構(gòu)，雙向鏈表是解決查找前驅(qū)結(jié)點問題的有效途徑。結(jié)點結(jié)構(gòu)如圖示：priordatanext下圖是帶頭結(jié)點的循環(huán)雙向鏈表的結(jié)構(gòu)，可見，其前驅(qū)指針和后繼指針各自構(gòu)成自己的循環(huán)單鏈表。head(a)空鏈表a0a1an-1head(b)非空鏈表…在雙向鏈表中:設(shè)指針p指向第i個數(shù)據(jù)元素結(jié)點，則p->next指向第i+1個數(shù)據(jù)元素結(jié)點，p->next->prior仍指向第i個數(shù)據(jù)元素結(jié)點，即p->next->prior=p;同樣p->prior->next=p。循環(huán)雙向鏈表的插入過程如圖示：a0aian-1head…xs…ai-1××…④①②③p刪除過程如圖示：ai+1aian-1head……ai-1××①②p2.6靜態(tài)鏈表在數(shù)組中增加一個(或兩個)指針域用來存放下一個(或上一個)數(shù)據(jù)元素在數(shù)組中的下標，從而構(gòu)成用數(shù)組構(gòu)造的單鏈表。因為數(shù)組內(nèi)存空間的申請方式是靜態(tài)的，所以稱為靜態(tài)鏈表，增加的指針稱做仿真指針。結(jié)構(gòu)如下：ABCE∧headD(a)常規(guī)鏈表A1B2C3D4E-1┇(b)靜態(tài)鏈表1datanext01234┇maxSize-1A2E-1B4D1C3┇(b)靜態(tài)鏈表2datanext01234┇maxSize-12.7設(shè)計舉例例2-4設(shè)計一個順序表的刪除函數(shù)，把順序表L中的數(shù)據(jù)元素x刪除。算法思想：首先，找到要刪除元素的位置，然后，從這個位置到最后一個元素，逐個前移，最后，把元素個數(shù)減1。intListDataDelete(SeqList*L,DataTypex){inti,j;

for(i=0;i<L->size;i++) if(x==L->list[i])break;

if(i==L->size)return0; else {for(j=i;j<L->size;j++)

L->list[j]=L->list[j+1];

L->size--; return1;}}例2-5構(gòu)造一個順序表的刪除算法，把順序表L中所有值相同的數(shù)據(jù)元素x全部刪除。算法思想：在例2-4所設(shè)計的刪除算法的基礎(chǔ)上，增加外重循環(huán)進行查找，查找到元素x則刪除，然后繼續(xù)進行這樣的過程和刪除過程，直到元素末尾結(jié)束。intListMoreDataDelete(SeqList*L,DataTypex){inti,j; inttag=0; for(i=0;i<L->size;i++){if(x==L->list[i]) {for(j=i;j<L->size-1;j++)

L->list[j]=L->list[j+1]; L->size--;

i--;

tag=1; }}

returntag;}例2-6設(shè)頭指針為head，并設(shè)帶頭結(jié)點單鏈表中的數(shù)據(jù)元素遞增有序，編寫算法將數(shù)據(jù)元素x插入到帶頭結(jié)點單鏈表的適當位置上，要求插入后保持單鏈表數(shù)據(jù)元素的遞增有序。算法思想：從鏈表的第一個數(shù)據(jù)元素結(jié)點開始，逐個比較每個結(jié)點的data域值和x的值，當data小于等于x時，進行下一個結(jié)點的比較；否則就找到了插入結(jié)點的合適位置，此時申請新結(jié)點把x存入，然后把新結(jié)點插入；當比較到最后一個結(jié)點仍有data小于等于x時，則把新結(jié)點插入單鏈表尾。voidLinListInsert(SLNode*head,DataTypex){SLNode*curr,*pre,*q;curr=head->next;pre=head;while(curr!=NULL&&curr->data<=x){pre=curr; curr=curr->next;}q=(SLNode*)malloc(sizeof(SLNode));q->data=x;q->next=pre->next;pre->next=q;}算法設(shè)計說明：（1）在循環(huán)定位插入位置時，循環(huán)條件必須首先是curr!=NULL，然后是curr->data<=x。如果次序顛倒，則當curr為空（即等于鏈表結(jié)束標記NULL）時,將因為curr->data不存在而出錯；次序不顛倒時，當curr等于NULL時將退出循環(huán)，不會進行后邊條件curr->data<=x的比較。（2）當比較到最后一個結(jié)點仍有data小于等于x時，此時有pre指向最后一個結(jié)點，curr等于NULL，則上述算法把新結(jié)點插入到了單鏈表尾作為了單鏈表新的表尾結(jié)點。

例2-7設(shè)head為單鏈表的頭指針，并設(shè)單鏈表帶有頭結(jié)點，編寫算法將單鏈表中的數(shù)據(jù)元素按照數(shù)據(jù)元素的值遞增有序的順序進行就地排序。算法思想：在例2-6算法的基礎(chǔ)上，再增加一重循環(huán)即可實現(xiàn)全部數(shù)據(jù)元素的排序。由于此時的排序過程沒有申請新的結(jié)點空間，所以這樣的排序算法滿足就地排序，即不增加新的內(nèi)存空間的設(shè)計要求。具體實現(xiàn)過程是：

把頭指針head所指單鏈表置空（即初始時head所指單鏈表僅包含一個頭結(jié)點），把去掉頭結(jié)點的原單鏈表（設(shè)由頭指針p指示）中的數(shù)據(jù)元素逐個重新插入head所指單鏈表中。每次插入從head所指單鏈表的第一個數(shù)據(jù)元素結(jié)點開始，逐個比較head所指單鏈表每個結(jié)點的data域值和p所指單鏈表的當前第一個數(shù)據(jù)元素結(jié)點的data域值，當前者小于或等于后者時，用head所指單鏈表的下一個結(jié)點進行比較；否則就找到了插入結(jié)點的合適位置，從p所指單鏈表中取下當前第一個數(shù)據(jù)元素結(jié)點插入到head所指單鏈表的合適位置。這樣的過程一直進行到p所指單鏈表為空時結(jié)束。voidLinListSort(SLNode*head){SLNode*curr,*pre,*p,*q;p=head->next;head->next=NULL;while(p!=NULL){curr=head->next;pre=head; while(curr!=NULL&&curr->data<=p->data) {pre=curr;curr=curr->next; } q=p;p=p->next;q->next=pre->next;pre->next=q;}}

習題2-1，2-2，2-3習題2-4，2-10，2-14習題2-16習題2-5，2-6，2-15習題2-20，2-21習題2-18，2-22作業(yè)

第3章棧和隊列主要知識點棧棧應(yīng)用隊列隊列應(yīng)用優(yōu)先級隊列3.1

堆棧1、棧的基本概念(1)定義:限定只能在固定一端進行插入和刪除操作的線性表。特點：后進先出。(2)允許進行插入和刪除操作的一端稱為棧頂，另一端稱為棧底。作用：可以完成從輸入數(shù)據(jù)序列到某些輸出數(shù)據(jù)序列的轉(zhuǎn)換2、棧抽象數(shù)據(jù)類型數(shù)據(jù)集合:{a0,a1,…,an-1}ai的數(shù)據(jù)類型為DataType。操作集合：

(1)StackInitiate(S)：初始化棧S(2)StackNotEmpty(S)：棧S非空否

(3)StackPush(S,x)：入棧

(4)StackPop(S,d)：出棧

(5)StackTop(S,d)：取棧頂數(shù)據(jù)元素3、順序棧

順序棧：順序存儲結(jié)構(gòu)的棧。

順序棧的存儲結(jié)構(gòu)：利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素.a0a1a2a3a4stack棧底棧頂MaxStackSize-1012345=toptypedefstruct{DataTypestack[MaxStackSize]; inttop;}SeqStack;順序棧的操作實現(xiàn)：

（1）初始化StackInitiate(S)voidStackInitiate(SeqStack*S) {S->top=0; }（2）非空否StackNotEmpty(S)intStackNotEmpty(SeqStackS){if(S.top<=0)return0;elsereturn1;}（3）入棧StackPush(S,x)intStackPush(SeqStack*S,DataTypex){if(S->top>=MaxStackSize){printf("棧已滿無法插入!\n"); return0;}else{S->stack[S->top]=x; S->top++;return1;}}（4）出棧StackPop(S,d)intStackPop(SeqStack*S,DataType*d){if(S->top<=0){printf("棧已空無數(shù)據(jù)元素出棧!\n"); return0;}else{S->top--;*d=S->stack[S->top];

return1;}}（5）取棧頂數(shù)據(jù)元素StackTop(SeqStackS,DataType*d)intStackTop(SeqStackS,DataType*d){if(S.top<=0){printf("棧已空!\n"); return0;}else{*d=S.stack[S.top-1]; return1;}}

測試主程序：任務(wù)：建立一個順序棧，首先依次輸入數(shù)據(jù)元素1,2,3,......,10，然后依次出棧數(shù)據(jù)元素并顯示。假設(shè)該順序棧的數(shù)據(jù)元素個數(shù)在最壞情況下不會超過100個。

#include<stdio.h>#include<stdlib.h> #defineMaxStackSize100 typedefintDataType; #include"SeqStack.h"

voidmain(void){SeqStackmyStack;inti,x;StackInitiate(&myStack);for(i=0;i<10;i++)StackPush(&myStack,i+1)StackTop(myStack,&x)printf("當前棧頂數(shù)據(jù)元素為：%d\n",x);printf("依次出棧的數(shù)據(jù)元素序列如下：\n");while(StackNotEmpty(myStack)){StackPop(&myStack,&x); printf("%d",x);} }程序運行輸出結(jié)果如下：當前棧頂數(shù)據(jù)元素為：10依次出棧的數(shù)據(jù)元素序列如下：109876543214、鏈式棧1)鏈式棧

鏈式存儲結(jié)構(gòu)的棧。2)鏈式棧的存儲結(jié)構(gòu)它是以頭指針為棧頂，在頭指針處插入或刪除，帶頭結(jié)點的鏈式棧結(jié)構(gòu)：頭結(jié)點an-1an-2a0∧…h(huán)棧底棧頂鏈棧中每個結(jié)點由兩個域構(gòu)成：data域和next域結(jié)點結(jié)構(gòu)體定義如下：typedefstructsnode{DataTypedata;structsnode*next;}LSNode;3)鏈式棧的操作實現(xiàn)

（1）初始化StackInitiate(head)voidStackInitiate(LSNode**head){*head=(LSNode*)malloc(sizeof(LSNode)); (*head)->next=NULL;}（2）非空否StackNotEmpty(head)intStackNotEmpty(LSNode*head){if(head->next==NULL)return0;elsereturn1;}（3）入棧StackPush(head,x)intStackPush(LSNode*head,DataTypex){LSNode*p;

p=(LSNode*)malloc(sizeof(LSNode));

p->data=x;p->next=head->next;head->next=p;

return1;}（4）出棧StackPop(head,*d)intStackPop(LSNode*head,DataType*d){LSNode*p=head->next;if(p==NULL){printf("棧已空出錯！"); return0;}

head->next=p->next;*d=p->data; free(p);return1;}（5）取棧頂數(shù)據(jù)元素StackTop(head,d)intStackTop(LSNode*head,DataType*d){LSNode*p=head->next; if(p==NULL) { printf("棧已空出錯！"); return0; }

*d=p->data; return1;}（6）撤消鏈式棧內(nèi)存空間Destroy(*head)voidDestroy(LSNode*head){LSNode*p,*p1;

p=head; while(p!=NULL) {p1=p; p=p->next; free(p1); }}

說明：1)鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，修改指針即可完成。

2)一般不會出現(xiàn)棧滿情況；除非沒有空間導致malloc分配失敗。3)采用鏈棧存儲方式的優(yōu)點是，當棧中元素個數(shù)變化較大，準確數(shù)字難以確定時，鏈棧較順序棧方便。3.2

棧應(yīng)用1、括號匹配問題例：假設(shè)一個算術(shù)表達式中包含圓括號、方括號和花括號三種類型的括號，編寫一個判別表達式中括號是否正確配對的函數(shù)，并設(shè)計一個測試主函數(shù)。解題：這是一個輸入元素序列到特定輸出元素序列轉(zhuǎn)換問題。算法思想：算術(shù)表達式中右括號和左括號匹配的次序正好符合后到的括號要最先被匹配的“后進先出”棧操作特點，因此可以借助一個棧來進行判斷。括號匹配共有四種情況：（1）左右括號配對次序不正確；（2）右括號多于左括號；（3）左括號多于右括號；（4）左右括號匹配正確。具體方法：順序掃描算術(shù)表達式（表現(xiàn)為一個字符串），當遇到三種類型的左括號時讓該括號進棧；當掃描到某一種類型的右括號時，比較當前棧頂括號是否與之匹配，若匹配則退棧繼續(xù)進行判斷；若當前棧頂括號與當前掃描的括號不相同，則左右括號配對次序不正確；若字符串當前為某種類型左括號而棧已空，則右括號多于左括號；字符串循環(huán)掃描結(jié)束時，若棧非空（即棧中尚有某種類型左括號），則說明左括號多于右括號；否則，左右括號匹配正確。括號匹配共有四種情況：（1）左右括號配對次序不正確： "(())abc{[]()]"（2）右括號多于左括號： "(()))abc{[]}"（3）左括號多于右括號： "(()()abc{[]}"（4）左右括號匹配正確： "(())abc{[]}"voidExpIsCorrect(charexp[],intn){SeqStackmyStack;inti;charc;

StackInitiate(&myStack);for(i=0;i<n;i++){if((exp[i]=='(')||(exp[i]=='[')||(exp[i]=='{'))StackPush(&myStack,exp[i]);

elseif(exp[i]==')'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c=='(')StackPop(&myStack,&c); elseif(exp[i]==')'&&StackNotEmpty(myStack)&&StackTop(myStack,&c)&&c!='(') {printf("左右括號配對次序不正確！\n"); return; }

elseif(exp[i]==']'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c=='['] StackPop(&myStack,&c);

elseif(exp[i]==']'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c!='[') {printf("左右括號配對次序不正確！\n"); return; }

elseif(exp[i]=='}'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c=='{'} StackPop(&myStack,&c);

elseif(exp[i]=='}'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c!='{') {printf("左右括號配對次序不正確！\n"); return; } elseif(((exp[i]==')')||(exp[i]==']')||(exp[i]=='}')) &&!StackNotEmpty(myStack)) { printf("右括號多于左括號！\n"); return; } }

if(StackNotEmpty(myStack)) printf("左括號多于右括號！\n"); else printf("左右括號匹配正確！\n");}2、表達式計算問題

表達式計算是編譯系統(tǒng)中的基本問題，其實現(xiàn)方法是棧的一個典型應(yīng)用。在編譯系統(tǒng)中，要把便于人理解的表達式翻譯成能正確求值的機器指令序列，通常需要先把表達式變換成機器便于理解的形式，這就要變換表達式的表示序列。假設(shè)計算機高級語言中的一個算術(shù)表達式為

A+(B-C/D)*E這種表達式稱為中綴表達式，寫成滿足四則運算規(guī)則的相應(yīng)的后綴表達式即為

ABCD/-E*+

優(yōu)點：可以直接計算中綴表達式的值。

編譯系統(tǒng)中表達式的計算分為兩個步驟：（1）把中綴表達式變換成相應(yīng)的后綴表達式；（2）根據(jù)后綴表達式計算表達式的值。其中，步驟（1）這種數(shù)據(jù)序列的特定變換可以利用棧來實現(xiàn)；步驟（2）的算法也可借助棧來實現(xiàn)。

中綴表達式變換為后綴表達式的算法步驟可以總結(jié)為：

(1)設(shè)置一個棧，初始時將棧頂元素置為“?！?。

(2)順序讀入中綴表達式，當讀到的單詞為操作數(shù)時就將其輸出，并接著讀下一個單詞。

(3)令x1為當前棧頂運算符的變量，x2為當前掃描讀到運算符的變量，當順序從中綴表達式中讀入的單詞為運算符時就賦予x2，然后比較x1的優(yōu)先級與x2的優(yōu)先級，若x1的優(yōu)先級高于x2的優(yōu)先級，將x1退棧并作為后綴表達式的一個單詞輸出，然后接著比較新的棧頂運算符x1的優(yōu)先級與x2的優(yōu)先級；若x1的優(yōu)先級低于x2的優(yōu)先級，將x2進棧然后讀下一個字符；若x1的優(yōu)先級等于x2的優(yōu)先級，特別處理。 如：中綴表達式A+(B-C/D)*E＃ 后綴表達式ABCD/-E*+運算符優(yōu)先級關(guān)系表

把中綴表達式A+(B-C/D)*E變換成后綴表達式的過程

計算后綴表達式的值的過程仍是一個棧應(yīng)用問題算法思想是：設(shè)置一個棧存放操作數(shù)，從左到右依次掃描后綴表達式，每讀到一個操作數(shù)就將其進棧；每讀到一個運算符就從棧頂取出兩個操作數(shù)施以該運算符所代表的運算操作，并把該運算結(jié)果作為一個新的操作數(shù)入棧；此過程一直進行到后綴表達式讀完，最后棧頂?shù)牟僮鲾?shù)就是該后綴表達式的運算結(jié)果。后綴表達式ABCD/-E*+求值過程:3.3

隊列1、隊列的基本概念(1)定義:只能在表的一端進行插入操作，在表的另一端進行刪除操作的線性表。一個隊列的示意圖如下：隊尾插入隊頭刪除a0a1a2…an-1隊頭隊尾數(shù)據(jù)集合:{a0,a1,…,an-1}，ai的數(shù)據(jù)類型為DataType。操作集合：（1）初始化QueueInitiate(Q)（2）非空否QueueNotEmpty(Q)（3）入隊列QueueAppend(Q,x)（4）出隊列QueueDelete(Q,d)（5）取隊頭數(shù)據(jù)元素QueueGet(Q,d)

3、順序隊列(1)順序隊列：順序存儲結(jié)構(gòu)的隊列。2、隊列抽象數(shù)據(jù)類型(2)順序隊列的存儲結(jié)構(gòu)有6個存儲空間的順序隊列動態(tài)示意圖(a)空隊列frontrear=012345CBA(b)入隊列A、B、C后front=012345C(c)出隊列A、B后front=012345rear=EDC(d)入隊列D、E后front=012345rear=(3)順序隊列的“假溢出”問題①假溢出順序隊列因多次入隊列和出隊列操作后出現(xiàn)的雖有存儲空間但不能進行入隊列操作的情況。

可采取四種方法：

1)采用順序循環(huán)隊列；（教材中的方法）

2)按最大可能的進隊操作次數(shù)設(shè)置順序隊列的最大元素個數(shù)；（最差的方法）

3)修改出隊列算法，使每次出隊列后都把隊列中剩余數(shù)據(jù)元素向隊頭方向移動一個位置；４)修改入隊列算法，增加判斷條件，當假溢出時，把隊列中的數(shù)據(jù)元素向隊頭移動，然后完成入隊列操作。②如何解決順序隊列的假溢出問題？(4)順序循環(huán)隊列的基本原理把順序隊列所使用的存儲空間構(gòu)造成一個邏輯上首尾相連的循環(huán)隊列。當rear和front達到MaxQueueSize-1后，再前進一個位置就自動到０。順序隊列a3a2a1frontrear0123..N-1a3a2a10123N-1rearfront循環(huán)隊列(5)順序循環(huán)隊列的隊空和隊滿判斷問題新問題：在順序循環(huán)隊列中，隊空特征是front=rear；隊滿時也會是front=rear；判決條件將出現(xiàn)二義性！解決方案有三：①使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）；（教材中的方法）判隊滿：count>0&&rear==front

判隊空：count==0②設(shè)標志位，出隊時置０,入隊時置１,則可識別當前front=rear屬于何種情況判隊滿：tag==1&&rear==front

判隊空：tag==0&&rear==front③少用一個存儲單元判隊滿：front=＝(rear+1)%MaxQueueSize

判隊空：rear==front4、順序循環(huán)隊列順序循環(huán)隊列的結(jié)構(gòu)體定義如下：typedefstruct{DataTypequeue[MaxQueueSize];intrear;intfront;intcount;}SeqCQueue;（1）初始化QueueInitiate(Q)voidQueueInitiate(SeqCQueue*Q){Q->rear=0; Q->front=0;Q->count=0;}（2）非空否QueueNotEmpty(Q)intQueueNotEmpty(SeqCQueueQ){if(Q.c