《數(shù)據(jù)結(jié)構(gòu)》課件(完整版)

1、數(shù)據(jù)結(jié)構(gòu)第1章 緒論第2章 線性表第3章 棧第4章 隊列第5章 數(shù)組和稀疏矩陣第6章 樹和二叉樹第7章 圖第8章 查找第9章 排序第一章 緒論1.1 數(shù)據(jù)結(jié)構(gòu)的概念1.2 算法1.1 數(shù)據(jù)結(jié)構(gòu)的概念計算機科學(xué)的重要研究內(nèi)容之一就是用計算機進行數(shù)據(jù)表示和處理。這里面涉及到兩個問題： 數(shù)據(jù)的表示和數(shù)據(jù)的處理。 數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容是計算機所處理數(shù)據(jù)元素間的關(guān)系及其操作實現(xiàn)的算法，包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)以及數(shù)據(jù)的運算。1.1.1基本概念和術(shù)語數(shù)據(jù)(Data)是能被計算機識別、存儲和加工處理的具有一定結(jié)構(gòu)的符號的總稱。 數(shù)據(jù)項(Data Item)是具有獨立意義的不可分割的最小數(shù)據(jù)單位。

2、 數(shù)據(jù)元素(Data Element)是數(shù)據(jù)被使用時的基本單位，在計算機程序中通常作為一個整體進行處理。 數(shù)據(jù)對象(Data object)是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。 數(shù)據(jù)結(jié)構(gòu)(Data Structure)由一個數(shù)據(jù)元素的集合和一系列基本運算組成。1.1.2邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。根據(jù)數(shù)據(jù)元素之間邏輯關(guān)系的不同特性，主要有下列三類基本結(jié)構(gòu)。 線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。 樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。 圖狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。 如下圖所示：1.1.3 存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計算機中的表示稱

3、為數(shù)據(jù)的存儲結(jié)構(gòu)，也稱為物理結(jié)構(gòu)?；镜拇鎯Y(jié)構(gòu)有兩種：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序存儲結(jié)構(gòu)是把邏輯上相鄰的元素存儲在一組連續(xù)的存儲單元中，其元素之間的邏輯關(guān)系由物理位置的相鄰關(guān)系表示。鏈?zhǔn)酱鎯Y(jié)構(gòu)將每個數(shù)據(jù)元素單獨存放，稱為一個結(jié)點，無需占用一整塊存儲空間。但為了表示結(jié)點之間的關(guān)系，需要給每個結(jié)點附加指針字段，用于存放下一個結(jié)點的存儲地址。 1.1.4 抽象數(shù)據(jù)類型 抽象數(shù)據(jù)類型（Abstract Data Type，簡稱ADT）是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。 抽象數(shù)據(jù)類型可用以下三元組表示： Abstract_Data_Type=(D，R，P) 其中：D是數(shù)據(jù)元素的有限

4、集，R是D上的關(guān)系的有限集，P是對D的基本運算集。 返回本章目錄1.2 算法1.2.1 算法的描述三種方式： 非形式化方式。 半形式化方式。 形式化方式。 1.2.2 算法設(shè)計的要求 正確性。 高效率。 低存儲量需求。 算法（Algorithm）是對特定問題求解步驟的一種描述。 1.2.3 算法分析算法的分析主要包括兩個方面：算法的時間復(fù)雜度分析和空間復(fù)雜度分析。 一個算法是由控制結(jié)構(gòu)和問題的基本操作構(gòu)成的，因此，一個算法的“運行工作量”就可以用該基本操作的重復(fù)次數(shù)來表示。 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，算法的時間量度記作： T(n)=O(f(n) T(n)稱

5、做算法的漸近時間復(fù)雜度，簡稱時間復(fù)雜度（Time Complexity）。 算法的時間復(fù)雜度常見的有：常量階O(1)、線性階O(n)、平方階O(n2) 、立方階O(n3)、對數(shù)階O(log2n)、指數(shù)階O(2n)等。不同數(shù)量級時間復(fù)雜度的性狀如下圖所示?！纠?】 起泡排序的算法描述如下，分析其時間復(fù)雜度。 void bubble-sort(int a，int n) int i,j,change,temp; for(i=n-1;change=1;i1 & change;-i) change=0; for(j=0;jaj+1) temp= aj; aj =aj+1; aj+1=temp; chan

6、ge=1; /bubble-sort解：在上述起泡排序算法中，問題的基本操作是“交換序列中相鄰兩個元素”，初始序列的狀態(tài)不同，該基本操作的重復(fù)次數(shù)也有很大不同： 最好情況：當(dāng)初始序列為自小至大有序時，基本操作的重復(fù)次數(shù)為0，時間復(fù)雜度為O(1)； 最壞情況：當(dāng)初始序列為自大至小有序時，基本操作的重復(fù)次數(shù)為： 1+2+3+n-1 =n(n-1)/2 時間復(fù)雜度為:O(n2) 平均情況：假設(shè)初始序列可能出現(xiàn)的排列情況（共n!種）的概率相等，則時間復(fù)雜度為O(n2)。通常，時間復(fù)雜度的評價指標(biāo)可以分為以下三種：最好時間復(fù)雜度：在最好情況下執(zhí)行一個算法所需要的時間。最壞時間復(fù)雜度：在最壞情況下執(zhí)行一個

7、算法所需要的時間。平均時間復(fù)雜度：在平均情況下執(zhí)行一個算法所需要的時間。算法的空間復(fù)雜度（Space Complexity）是指執(zhí)行算法過程中所使用的額外存儲空間的開銷。不包括算法程序代碼和所處理的數(shù)據(jù)本身所占用的空間部分。通常，額外空間與問題的規(guī)模有關(guān)，類似于算法的時間復(fù)雜度，算法的空間復(fù)雜度記作： S(n)=O(f(n) 其中n為問題的規(guī)模(或大小)。數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)以及數(shù)據(jù)的運算。數(shù)據(jù)元素之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。主要有線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)在計算機中的表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)?；?/p>

8、的存儲結(jié)構(gòu)有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)兩種。算法是對特定問題求解步驟的一種描述。算法的設(shè)計既要保證正確性，同時也必須考慮算法的效率和對存儲量的需求。1. 簡述下列術(shù)語：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)。2. 什么叫數(shù)據(jù)的邏輯結(jié)構(gòu)？主要有哪幾種？3. 什么叫數(shù)據(jù)的存儲結(jié)構(gòu)？基本的存儲結(jié)構(gòu)有哪幾種？4. 試述順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的區(qū)別。5. 算法的時間復(fù)雜度和空間復(fù)雜度分別是什么？6. 試寫一算法，將3個整數(shù)a、b和c按從小到大的次序輸出。結(jié)束第二章 線性表2.1 線性表的抽象數(shù)據(jù)類型 2.2 線性表的順序存儲結(jié)構(gòu) 2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 2.1 線性表的抽象數(shù)據(jù)類型一個線性表(Li

9、near List) 是由n(n0)個數(shù)據(jù)元素(結(jié)點) 組成的有限序列。數(shù)據(jù)元素可以是一個字符、一個數(shù)或一個記錄，也可以是更復(fù)雜的信息。 線性表一：26個英文字母組成的字母表（A，B，C，Z）。表中的數(shù)據(jù)元素是單個字母字符。線性表二：某學(xué)生五門課的成績列表（76，87，88，80，92）。表中的數(shù)據(jù)元素是整數(shù)。線性表三：某班級學(xué)生信息表（如下表所示）。表中的數(shù)據(jù)元素是一個記錄，包括姓名、學(xué)號、性別和年齡4個數(shù)據(jù)項。線性表中的元素可以是各種各樣的，但同一線性表中的元素必定具有相同特性，即屬同一數(shù)據(jù)對象。 一個線性表可記為： （a1,a2, ,ai-1,ai,ai+1, ,an），n 0 其中，n

10、為表的長度，當(dāng)n=0時，稱為空表。 稱i為ai在線性表中的位序。 表中ai-1領(lǐng)先于ai，稱ai-1是ai的直接前驅(qū)，ai+1是ai的直接后繼。線性表的抽象數(shù)據(jù)類型定義 （參見教材）返回本章目錄2.2 線性表的順序存儲結(jié)構(gòu) 線性表的順序存儲是指在內(nèi)存中用地址連續(xù)的一塊存儲空間依次存放線性表的數(shù)據(jù)元素，用這種存儲形式存儲的線性表稱其為順序表。假設(shè)每個數(shù)據(jù)元素占d個存儲單元，且將ai的存儲地址表示為Loc(ai)，則有如下關(guān)系： Loc(ai)=Loc(a1)+(i-1)*d Loc(a1)是線性表的第一個數(shù)據(jù)元素a1的存儲地址，通常稱作線性表的基地址。順序表的存儲結(jié)構(gòu)如下圖所示，其中b為線性表的

11、基地址。 2.2.1 順序表的類型定義 #define MAXSIZE 100 / 順序表的容量 typedef struct ElemType dataMAXSIZE; / 存放順序表的元素 int len; / 順序表的實際長度 SqList;MAXSIZE為順序表的容量，表示線性表實際可能達到的最大長度。 len表示順序表當(dāng)前的長度。2.2.2 線性表基本運算在順序表上的實現(xiàn)C語言中數(shù)組的下標(biāo)從“0”開始，因此，若L是Sqlist類型的順序表，則表中第i個元素是L.datai-1。 1. 初始化線性表運算void InitList(SqList &sq) sq.len=0; 2.求線性表

12、長度運算int ListLength (SqList sq) return(sq.len); 3.求線性表中第i個元素運算ElemType GetElem(SqList sq,int i) if (isq.len) / i 值不合法 return 0; else return(sq.datai-1); 4.按值查找運算int LocateElem(SqList sq, ElemType e) int i=0; while (i=sq.len) return 0; else return i+1; 5. 插入元素運算int ListInsert(SqList &sq ,int i, ElemTy

13、pe e) int j; if (isq.len+1) return 0; / i 值不合法 for (j=sq.len;j=i;j-) / 插入位置及之后的元素右移 sq.dataj= sq.dataj-1; sq.datai-1=e; / 插入e sq.len+; / 表長增1 return 1;6. 刪除元素運算 int ListDelete (SqList &sq ,int i) int j; if (isq.len) return 0; / i 值不合法 for (j=i;jsq.len;j+) / 被刪除元素之后的元素左移 sq.dataj-1= sq.dataj; sq.len-

14、; / 表長減1 return 1;2.2.3 順序?qū)崿F(xiàn)的算法分析1. 插入假設(shè)pi是在第i個位置插入一個元素的概率，則在長度為n的線性表中插入一個元素時所需移動元素的平均次數(shù)為：pi=1/(n+1)插入算法的平均時間復(fù)雜度為O(n)。2. 刪除假設(shè)qi是在第i個位置刪除一個元素的概率，則在長度為n的線性表中刪除一個元素時所需移動元素的平均次數(shù)為：qi=1/n刪除算法的平均時間復(fù)雜度為O(n)。2.2.4 順序表的應(yīng)用舉例【例1】 編寫一算法，從順序表中刪除自第i個元素開始的k個元素。算法思路： 為保持順序表的邏輯特性，需將i+k n位置的所有元素依次前移k個位置。算法如下： int dele

15、teK(Sqlist &sq,int i,int k) if (i1|ksq.len) return 0; for (j=i+k-1;j=sq.len-1;j+) sq.dataj-k=sq.dataj; sq.len-=k; return 1; / deleteK 【例2】巳知有兩個按元素值遞增有序的順序表La和Lb，設(shè)計一個算法將表La和表Lb的全部元素歸并為一個按元素值遞增有序的順序表Lc。算法思路：用i掃描順序表La，用j掃描順序表Lb。當(dāng)表La和表Lb都未掃描完時，比較兩者的當(dāng)前元素，將較小者插入表Lc的表尾，若兩者的當(dāng)前元素相等，則將這兩個元素依次插入表Lc的表尾。最后，將尚為掃描

16、完的順序表的余下部分元素依次插入表Lc的表尾。算法如下： void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) int i=0,j=0,k=0;while (i La.len & jLb.len) / 表La和表Lb都未掃描完時 if (La. datai Lb.data j) Lc. data k= Lb. data j;j+;k+; else Lc. data k= La. data i;i+;k+; Lc. data k= Lb. data j;j+;k+; while (iLa.len) Lc. data k= La.data i;i+

17、;k+; while (jnext=NULL; （2）求線性表長度 int ListLength(LinkList h) int i=1; LNode *p=h-next; while (p-next!=NULL) /當(dāng)p指向最后一個數(shù)據(jù)結(jié)點時，循環(huán)停止 p=p-next; i+; /指針p沿著next域移動一次，i值增1 return i; （3）求線性表中第i個元素 LNode *GetElem(LinkList h,int i) int j=1; LNode *p=h-next; if (i ListLength(h) return NULL; /i值不合法 while (jnext;

18、j+; return p; / 返回第i個結(jié)點的指針 本算法的時間復(fù)雜度為O(n)。（4）按值查找 LNode *LocateElem(LinkList h,ElemType e) LNode *p=h-next; while (p!=NULL & p-data!=e) /從第1個結(jié)點開始，查找data域為e的結(jié)點 p=p-next; return p; （5）插入結(jié)點 int ListInsert(LinkList &h,ElemType e,int i) int j=0; LNode *p=h,*s; if (i ListLength(h)+1) return 0; /i值不合法 whil

19、e (jnext; j+; /從頭結(jié)點開始，查找第i-1個結(jié)點 s=( LNode *)malloc(sizeof(LNode); /創(chuàng)建新結(jié)點 s-data=e; s-next=p-next; p-next=s; /插入鏈表中 return 1; （6）刪除結(jié)點 int ListDelete(LinkList &h,int i) int j=0; LNode *p=h,*q; if (i ListLength(h) return 0; /i值不合法 while (jnext; j+; /從頭結(jié)點開始，查找第i-1個結(jié)點 q=p-next; /刪除并釋放結(jié)點 p-next=q-next; fr

20、ee(q); return 1; （7）輸出元素值 void ListOutput(LinkList h) LNode *p=h-next; while (p!=NULL) printf(“%5d ”, p-data); /輸出結(jié)點的data域 p=p-next; 2. 建立單鏈表 （1） 頭插法建表 算法思路：從一個空表開始，讀取數(shù)據(jù)，生成新結(jié)點，將讀取的數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到當(dāng)前鏈表的表頭上，如此重復(fù)，直到讀入結(jié)束標(biāo)志為止。算法如下：void CreateListF(LinkList &h,ElemType a,int n) LNode *s; int i; h=(

21、 LNode *)malloc(sizeof(LNode); / 創(chuàng)建頭結(jié)點 h-next=NULL; for (i=0;idata=ai; s-next=h-next; / 將新結(jié)點插入到頭結(jié)點之后 h-next=s; / CreateListF（2) 尾插法建表 算法思路：將新結(jié)點插入到當(dāng)前鏈表的表尾上，為此必須增加一個尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點。 算法如下： void CreateListR(LinkList &h,ElemType a,int n) LNode *s,*r; int i; h=( LNode *)malloc(sizeof(LNode); / 創(chuàng)建頭結(jié)點 r

22、=h; / r始終指向尾結(jié)點，開始時指向頭結(jié)點 for (i=0;idata=ai; r-next=s; r=s; / 將新結(jié)點插入到尾結(jié)點之后 r-next=NULL; / 將尾結(jié)點的next域置為空 / CreateListR頭插法建表和尾插法建表算法的時間復(fù)雜度都是O(n)。 3. 單鏈表的應(yīng)用舉例【例1】設(shè)ha和hb分別是兩個帶頭結(jié)點的非遞減有序單鏈表的表頭指針，試設(shè)計一個算法，將這兩個有序鏈表合并成一個非遞減有序的單鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的空間。表中允許有重復(fù)的數(shù)據(jù)。算法思路： 設(shè)立3個指針pa、pb和pc，其中pa和pb分別指向ha和hb表中當(dāng)前待比較插入的結(jié)點，而p

23、c指向hc表中當(dāng)前最后一個結(jié)點。 比較pa-data和pb-data,將較小者插入hc的表尾，即鏈到pc所指結(jié)點之后。若pa-data和pb-data相等，則將兩個結(jié)點均鏈到pc所指結(jié)點之后。 如此反復(fù)，直到有一個表的元素已歸并完（pa或pb為空）為止，再將另一個表的剩余段鏈接到pc所指結(jié)點之后。 具體算法：void MergeList_L(LinkList &ha, LinkList &hb, LinkList &hc) LNode *pa,*pb,*pc; pa=ha-next; pb=hb-next; hc=pc=ha; / 用ha的頭結(jié)點作為hc的頭結(jié)點，pc始終指向hc的表尾結(jié)點 w

24、hile(pa&pb) if(pa-datadata) pc-next=pa; pc=pa;pa=pa-next; else if(pa-datapb-data) pc-next=pb; pc=pb;pb=pb-next; else pc-next=pa;pc=pa;pa=pa-next; pc-next=pb;pc=pb;pb=pb-next; pc-next=pa?pa:pb; / 插入剩余段free(hb); / 釋放hb的頭結(jié)點/ MergeList_L本算法的基本操作是結(jié)點數(shù)據(jù)的比較和結(jié)點的鏈入，在最壞情況下，對每個結(jié)點均需進行上述操作，因此，若表ha和表hb的長度分別是m和n，則本

25、算法的時間復(fù)雜度為O(m+n)。【例2】設(shè)計算法，根據(jù)輸入的學(xué)生人數(shù)和成績建立一個單鏈表，并累計其中成績不及格的人數(shù)。要求給出完整的程序。解題思路：先定義單鏈表結(jié)點的類型，并根據(jù)題意將ElemType設(shè)為int型；然后設(shè)計一個算法create，用于輸入學(xué)生人數(shù)和成績，并建立相應(yīng)的單鏈表；設(shè)計一個算法count，用于計算不及格人數(shù)；最后在主函數(shù)中調(diào)用實現(xiàn)上述兩個算法的函數(shù)。完整的程序參見教材 2.3.2 單循環(huán)鏈表循環(huán)鏈表的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。 單循環(huán)鏈表的操作和單鏈表基本一致，差別僅在于算法中的循環(huán)條件不是p或p-next是否為空，而是它們是否等于頭指

26、針。 例如，求線性表的長度運算在單循環(huán)鏈表上的實現(xiàn)算法如下： int ListLength(LinkList h) int i=1; LNode *p=h-next; while (p-next!=h) /當(dāng)p指向最后一個數(shù)據(jù)結(jié)點時，循環(huán)停止 p=p-next; i+; /指針p沿著next域移動一次，i值增1 return i; / ListLength(a)雙向鏈表的結(jié)點結(jié)構(gòu) (b) 空的雙向循環(huán)鏈表 (c) 非空的雙向循環(huán)鏈表2.3.3 雙向鏈表 在雙向鏈表的結(jié)點中有兩個指針域，其一指向直接后繼，另一指向直接前驅(qū)。 1. 刪除 int ListDelete_DuL(DuLinkList

27、&Dh,int i) int j=0; DuLNode *p=Dh,*q; if (i ListLength_DuL(Dh) return 0; /i值不合法 while (jnext; j+; /從頭結(jié)點開始，查找第i個結(jié)點 p-prior-next=p-next; /刪除并釋放結(jié)點 p-next-prior=p-prior; free(p); return 1; / ListDelete_DuL2. 插入 int ListInsert_DuL(DuLinkList &Dh,ElemType e,int i) int j=0; LNode *p=Dh,*s; if (i ListLength

28、_DuL(Dh)+1) return 0; /i值不合法 while (jnext; j+; /從頭結(jié)點開始，查找第i個結(jié)點 s=( DuLNode *)malloc(sizeof(DuLNode); /創(chuàng)建新結(jié)點 s-data=e; s-prior=p-prior; p-prior-next=s; /插入鏈表中 s-next=p; p-prior=s; return 1; / ListInsert_DuL線性表是一種典型的線性結(jié)構(gòu)。線性表中的元素可以是各種各樣的，但同一線性表中的元素必具有相同的特性。順序表是以“物理位置相鄰”來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系的，通常用數(shù)組來描述。鏈表是通

29、過每個結(jié)點的鏈域?qū)⒕€性表的各個結(jié)點按其邏輯次序鏈接在一起的。 單循環(huán)鏈表的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。雙向鏈表的結(jié)點中有兩個分別指向直接后繼和指向直接前驅(qū)的指針域，在雙向鏈表中尋查結(jié)點的前驅(qū)和后繼都很方便。1. 對于表長為n的順序表，在任何位置上插入或刪除一個元素的概率相等時，插入一個元素所需要移動的元素的平均個數(shù)為多少？刪除一個元素所需要移動的元素的平均個數(shù)為多少？2. 設(shè)線性表A采用順序存儲且元素按值遞增有序排列。試編一算法，將x插入到線性表的適當(dāng)位置上，并保持線性表的有序性。分析算法的時間復(fù)雜度。3. 設(shè)線性表A采用鏈?zhǔn)酱鎯η以匕粗颠f增有序排列。試編一

30、算法，將x插入到線性表的適當(dāng)位置上，并保持線性表的有序性。分析算法的時間復(fù)雜度。4. 已知La是帶頭結(jié)點的單鏈表，編寫一算法，從表La中刪除自第i個元素起，共len個元素。5. 分別畫出順序表、單鏈表、雙鏈表和單循環(huán)鏈表的結(jié)構(gòu)圖。結(jié)束第三章 棧3.1 棧的抽象數(shù)據(jù)類型 3.2 棧的順序存儲結(jié)構(gòu) 3.3 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)3.4 棧與遞歸的實現(xiàn) 3.1 棧的抽象數(shù)據(jù)類型棧(Stack)是限制在表的一端進行插入和刪除運算的線性表，通常稱允許進行插入、刪除的一端為棧頂(Top)，另一端為棧底(Bottom)。棧的修改原則 ：后進先出（LIFO）棧的抽象數(shù)據(jù)類型定義 （參見教材）返回本章目錄3.2 棧的

31、順序存儲結(jié)構(gòu) 棧的順序存儲結(jié)構(gòu)簡稱為順序棧。順序棧是利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時用一個變量top記錄棧頂?shù)奈恢?，通常稱此變量為棧頂指針。 3.2.1 順序棧的類型定義 #define StackSize 100 /順序棧的初始分配空間 typedef struct ElemType dataStackSize; / 保存棧中元素 int top; / 棧頂指針 SqStack; 其中，StackSize是指順序棧的初始分配空間，是棧的最大容量。數(shù)組data用于存儲棧中元素，top為棧頂指針。 由于C語言中數(shù)組的下標(biāo)約定從0開始，因此，用top=-1表示?？铡Ｃ?/p>

32、當(dāng)插入新的棧頂元素時，指針top增1；刪除棧頂元素時，指針top減1。 3.2.2 棧基本運算在順序棧上的實現(xiàn)1. 初始化棧運算 void InitStack(SqStack st) st.top=-1; 2. 進棧運算 int Push(SqStack &st,ElemType e) if (st.top=StackSize-1) return 0; else st.top+; st.datast.top=e; return 1; 3. 出棧運算 int Pop(SqStack &st,ElemType &e) if (st.top=-1) return 0; else e=st.datas

33、t.top; st.top-; return 1; 4. 取棧頂元素運算 int GetTop(SqStack st,ElemType &e) if (st.top=-1) return 0; else e=st.datast.top; return 1; 5. 判斷棧空運算 int StackEmpty(SqStack st) if (st.top=-1) return 1; else return 0; 3.2.3 順序棧的應(yīng)用舉例【例1】 設(shè)計一個算法，判斷一個表達式中括號是否匹配。若匹配，則返回1；否則返回0。 算法思路：掃描表達式，當(dāng)遇到左括號時，將其進棧，遇到右括號時，判斷棧頂是否

34、為相匹配的左括號。若不是，則退出掃描過程，返回0；否則棧頂元素出棧，直到掃描完整個表達式時，若棧為空，則返回1。 具體算法參見教材【例2】編寫一個算法，將非負的十進制整數(shù)轉(zhuǎn)換為其他進制的數(shù)輸出，10及其以上的數(shù)字從A開始的字母表示。并給出完整的程序。解題思路：先定義順序棧的類型，并根據(jù)題意將ElemType設(shè)為char型；然后設(shè)計一個算法trans來完成數(shù)制的轉(zhuǎn)換；最后在主函數(shù)中調(diào)用實現(xiàn)轉(zhuǎn)換算法的函數(shù)。算法trans的思路：先用“除基取余”法求得從低位到高位的值，同時采用順序棧暫時存放每次得到的數(shù)，當(dāng)商為0時，再從棧頂?shù)綏５纵敵鰪母呶坏降臀坏臄?shù)字。完整的程序參見教材返回本章目錄3.3 棧的鏈?zhǔn)?/p>

35、存儲結(jié)構(gòu)棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧，它是運算是受限的單鏈表，即插入和刪除操作僅限制在表頭位置上進行。3.3.1鏈棧的類型定義 typedef struct stnode ElemType data; struct stnode *next; StNode,*LinkStack;3.3.2 ?；具\算在鏈棧上的實現(xiàn)1. 初始化棧運算 void InitStack(LinkStack &ls) ls=NULL; 2. 進棧運算 void Push(LinkStack &ls,ElemType x) StNode *p; p=( StNode* ) malloc(sizeof(StNode); p-d

36、ata=x; p-next=ls; ls=p; 3. 出棧運算 int Pop(LinkStack &ls,ElemType &x) StNode *p; if (ls=NULL) return 0; else p=ls; x=p-data; ls=p-next; free(p); return 1; 4. 取棧頂元素運算 int GetTop(LinkStack ls,ElemType &x) if (ls=NULL) return 0; else x=ls-data; return 1; 5. 判斷?？者\算 int StackEmpty(LinkStack ls) if (ls=NULL)

37、 return 1; else return 0; 3.3.3 鏈棧的應(yīng)用舉例【例3】回文指的是一個字符串從前面讀和從后面讀都一樣，編寫一個算法判斷一個字符串是否為回文。并給出完整的程序。解題思路：先定義鏈棧的類型，并根據(jù)題意將ElemType設(shè)為char型；然后設(shè)計一個算法huiwei來完成判斷；最后在主函數(shù)中調(diào)用實現(xiàn)判斷算法的函數(shù)。算法huiwei的思路：先將字符串從頭到尾的各個字符依次放入一個鏈棧中；然后依次取棧頂?shù)綏５椎母鱾€字符與字符串從頭到尾的各個字符比較，如果兩者不同，則表明該字符串不是回文，若相同，則繼續(xù)比較；如果直到比較完畢相互之間都相匹配，則表明該字符串是回文。完整的程序參見

38、教材 返回本章目錄3.4 棧與遞歸的實現(xiàn)棧的一個重要應(yīng)用是在程序設(shè)計語言中實現(xiàn)遞歸。一個直接調(diào)用自己或通過一系列的調(diào)用語句間接地調(diào)用自己的函數(shù)，稱做遞歸函數(shù)。 【例4】階乘函數(shù)。 1 若n=0 Fact(n)= n*Fact(n-1) 若n0以求3！為例，完整的程序如下：#include stdio.hvoid main() int result,n; n=3; result =fact(n); printf(“3!=%dn”,result);int fact(int n) 1 int f;2 if(n=0) /遞歸終止條件3 f=1;4 else5 f=n*fact(n-1);6 retur

39、n f; 遞歸是把一個不能或不好直接求解的“大問題”轉(zhuǎn)化成一個或幾個“小問題”來解決，再把這些“小問題”進一步分解成更小的“小問題”來解決，如此分解，直至每個“小問題”都可以直接解決，此時遞歸終止，逐層返回。計算fac(3)的過程如 下：遞歸調(diào)用的特點是：主調(diào)函數(shù)和被調(diào)函數(shù)是同一個函數(shù)，因此，在一個遞歸函數(shù)的運行過程中，一個和每次調(diào)用相關(guān)的重要概念是遞歸函數(shù)運行的“層次”。為了保證遞歸函數(shù)正確執(zhí)行，系統(tǒng)需設(shè)立一個“遞歸工作?！弊鳛檎麄€遞歸函數(shù)運行期間使用的數(shù)據(jù)存儲區(qū)。每一層遞歸所需信息構(gòu)成一個“工作記錄”，其中包括所有的實際參數(shù)、所有的局部變量以及上一層的返回地址。每進入一層遞歸，就產(chǎn)生一個新

40、的工作記錄壓入棧頂。每退出一層遞歸，就從棧頂彈出一個工作記錄。棧是一種操作受限的線性表，即只允許在表尾進行插入和刪除操作。棧的結(jié)構(gòu)特點是后進先出，在許多軟件系統(tǒng)中都會用到這種結(jié)構(gòu)。棧也有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。棧的順序存儲結(jié)構(gòu)稱為順序棧，主要通過改變棧頂指針來實現(xiàn)各種操作；棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧，其各種操作的實現(xiàn)類似于單鏈表。1.棧有什么特點？什么情況下用到棧？2.設(shè)一個棧的輸入序列為A,B,C,D,則借助一個棧所得到的輸出序列不可能是哪個？ （1）ABCD （2）BDCBA （3）ACDB （4）DABC3.若元素進棧順序為1234，為了得到1342的出棧順序，試給出相應(yīng)的操作序列。4

41、.鏈棧中為何不設(shè)頭結(jié)點？5.寫一個算法，借助于棧將一個單鏈表逆置。結(jié)束第四章 隊列4.1 隊列的抽象數(shù)據(jù)類型 4.2 隊列的順序存儲結(jié)構(gòu) 4.3 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)4.1 隊列的抽象數(shù)據(jù)類型隊列(Queue)是限制在表的一端進行插入，而在表的另一端進行刪除的線性表，通常稱允許進行插入的一端為隊尾(Rear)，允許進行刪除的一端為對頭(Front)。隊列的修改原則 ：先進先出（FIFO）隊列的抽象數(shù)據(jù)類型定義 （參見教材）返回本章目錄4.2 隊列的順序存儲結(jié)構(gòu) 在隊列的順序存儲結(jié)構(gòu)中，除了用一組地址連續(xù)的存儲單元依次存放自隊頭到隊尾的數(shù)據(jù)元素之外，還需附設(shè)兩個變量front和rear分別指示隊頭

42、元素和隊尾元素的位置，這兩個變量分別稱為“隊頭指針”和“隊尾指針”。 通常約定：初始化隊列時，令front=rear=0，每當(dāng)有新元素入隊列時，隊尾指針增1；每當(dāng)刪除隊頭元素時，隊頭指針增1。因此，在非空隊列中，隊頭指針始終指向隊頭元素的當(dāng)前位置，而隊尾指針始終指向隊尾元素當(dāng)前位置的下一個位置。 “假溢出”現(xiàn)象 ：隊列的實際可用空間未占滿，但不能再進行入隊 列操作了。 解決假溢出的方法之一：將隊列的數(shù)據(jù)區(qū)看成首尾相接的循環(huán)結(jié)構(gòu)，形成一個環(huán)形的空間，稱之為循環(huán)隊列。4.2.1 循環(huán)隊列的類型定義 #define QueueSize 100 / 循環(huán)隊列的初始分配空間 typedef struct

43、 ElemType dataQueueSize; / 保存隊列中元素 int front; / 隊頭指針 int rear; / 隊尾指針 SqQueue;其中，QueueSize是指循環(huán)隊列的初始分配空間，是循環(huán)隊列的最大容量。數(shù)組data用于存儲隊列中的元素，front和rear分別為“隊頭指針”和“隊尾指針”。在循環(huán)隊列Q中： 隊頭指針增1：Q.front=(Q.front+1)% QueueSize 隊尾指針增1： Q.rear=(Q.rear+1)% QueueSize4.2.2 隊列基本運算在循環(huán)隊列上的實現(xiàn)1. 初始化隊列運算 void InitQueue(SqQueue &qu

44、) qu.rear=qu.front=0; 2. 入隊列運算 int EnQueue(SqQueue &qu,ElemType e) if (qu.rear+1)%QueueSize=qu.front) return 0; qu.dataqu.rear=e; qu.rear=(qu.rear+1)%QueueSize; return 1; 3. 出隊列運算 int DeQueue(SqQueue &qu,ElemType &e) if (qu.rear=qu.front) return 0; e=qu.dataqu.front; qu.front=(qu.front+1)%QueueSize;

45、 return 1; 4. 取隊頭元素運算 int GetHead(SqQueue qu,ElemType &e) if (qu.rear=qu.front) return 0; e=qu.dataqu.front; return 1; 5. 判斷隊列空運算 int QueueEmpty(SqQueue qu) if (qu.rear=qu.front) return 0; else return 1;4.2.3 循環(huán)隊列的應(yīng)用舉例【例1】設(shè)從鍵盤輸入一整數(shù)序列a1,a2,an，試編程實現(xiàn)：當(dāng)ai0時，ai進隊；當(dāng)ainext=NULL; 2. 入隊列運算 void EnQueue(LinkQ

46、ueue &lq,ElemType e) p= (QueuePtr)malloc(sizeof(QNode); p-data=e; p-next=NULL; lq.rear-next=p; lq.rear=p; 3. 出隊列運算 int DeQueue(LinkQueue &lq,ElemType &e) if (lq.rear=lq.front) return 0; p=lq.front-next; e=p-data; lq.front-next=p-next; if(lq.rear=p) lq.rear=lq.front; free(p); return 1; 4. 取隊頭元素運算 int

47、 GetHead(LinkQueue &lq,ElemType &e) if (lq.rear=lq.front) return 0; p=lq.front-next; e=p-data; return 1; 5. 判斷隊列空運算 int QueueEmpty(LinkQueue lq) if (lq.rear=lq.front) return 0; else return 1; 4.3.3 鏈隊列的應(yīng)用舉例【例2】編寫一個程序，反映病人到醫(yī)院看病、排隊看醫(yī)生的情況。在病人排隊過程中，主要發(fā)生兩件事：（1）病人到達診室，將病歷交給護士，排隊候診；（2）護士從排好隊的病歷中取出下一位病人的病歷，

48、該病人進入診室就診。 要求程序采用菜單方式，其選項及功能說明如下：（1）排隊：輸入排隊病人的病歷號，加入到病人排隊隊列中；（2）就診：病人排隊隊列中最前面的病人就診，并將其從隊列中刪除；（3）查看排隊：從隊首到隊尾列出所有的排隊病人的病歷號；（4）下班：退出運行。解題思路：先定義鏈隊列的類型，并根據(jù)題意將ElemType設(shè)為char型；在程序中根據(jù)功能要求進行插入、刪除和輸出操作，并使用switch語句實現(xiàn)菜單的選擇。完整的程序參見教材。隊列也是一種操作受限的線性表。它只允許在表尾進行插入而在表頭進行刪除操作。隊列的結(jié)構(gòu)特點是先進先出，在許多實際問題的解決中和系統(tǒng)軟件的設(shè)計中，都會用到隊列。隊

49、列也有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。為了解決假溢出的問題，通常將隊列的順序存儲結(jié)構(gòu)數(shù)據(jù)區(qū)看成首尾相接的循環(huán)結(jié)構(gòu)，形成一個環(huán)形的空間，稱之為循環(huán)隊列。隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈隊列，是一個同時帶有首指針和尾指針的單鏈表，其各種操作的實現(xiàn)也類似于單鏈表。 1.循環(huán)隊列有什么優(yōu)點？如何判斷它的空和滿？2.對于一個具有Qsize個單元的循環(huán)隊列，寫出求隊列中元素個數(shù)的公式。3.假設(shè)以一維數(shù)組sqm存儲循環(huán)隊列的元素，同時以rear和length分別指示循環(huán)隊列中的隊尾位置和隊列中所含元素的個數(shù)。試給出該循環(huán)隊列的隊空條件和隊滿條件，并寫出相應(yīng)的入隊列和出隊列的算法。4.假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示一個隊列

50、，并且只設(shè)一個隊尾指針指向隊尾元素結(jié)點（注意不設(shè)頭指針），試寫出相應(yīng)的初始化、入隊列和出隊列的算法。結(jié)束第五章 數(shù)組和稀疏矩陣5.1數(shù)組的概念與表示 5.2 稀疏矩陣 5.1數(shù)組的概念與表示 數(shù)組可以看作線性表的推廣，或者說是線性表的嵌套。5.1.1 數(shù)組的概念數(shù)組是有序排列的相同類型的數(shù)據(jù)元素的集合。數(shù)組具有如下兩個特征：（1）數(shù)組中的元素是有序的。數(shù)組中的元素可以用數(shù)組名和下標(biāo)指定，下標(biāo)指出了該元素在數(shù)組中的順序。（2）數(shù)組的元素是相同類型的。數(shù)組中存儲的所有元素必須是同一種數(shù)據(jù)類型，而不能是多種數(shù)據(jù)類型的混合。對數(shù)組的操作一般只有兩類：（1）獲得特定位置的元素值；（2）修改特定位置的元素

51、值。數(shù)組的抽象數(shù)據(jù)類型（參見教材） 5.1.2 數(shù)組的順序表示對于多維數(shù)組，數(shù)組元素在一維結(jié)構(gòu)的存儲單元中連續(xù)存儲時，有個存儲的次序問題。 對于二維數(shù)組，按行序為主序的存儲方式和按列序為主序的存儲方式 5.1.3 特殊矩陣的壓縮存儲為了節(jié)省存儲空間，可以對這些特殊矩陣進行壓縮存儲。 1.下三角矩陣對于一個n階矩陣來說，若當(dāng)ij時，有，則稱此矩陣為下三角矩陣。對于下三角矩陣的壓縮存儲，我們只存儲下三角中的元素，對于其余的零元素則不存。 若已知首元素的存儲地址為Loc(1,1)，并且知道每個元素所占的存儲空間L，下三角中任意元素aij地址的計算公式如下：Loc(i,j)=Loc(1,1)+(i*(

52、i-1)/2+(j-1)*L,i j2.上三角矩陣對于一個n階矩陣，若當(dāng)ij時，有，則稱此矩陣為上三角矩陣。對于上三角矩陣的壓縮存儲，同下三角矩陣類似，我們只存儲上三角中的元素，對于其余的零元素則不存。若已知首元素的存儲地址為Loc(1,1)，并且知道每個元素所占的存儲空間L，上三角中任意元素aij地址的計算公式如下：Loc(i,j)=Loc(1,1)+(2n-i+2）*(i-1)/2+(j-i)*L, i j3.對稱矩陣若矩陣中的所有元素均滿足aij=aji，則稱此矩陣為對稱矩陣。對于對稱矩陣，因其元素滿足aij=aji ，我們可以為每一對相等的元素分配一個存儲空間，即只存下三角（或上三角）

53、矩陣，從而將n2個元素壓縮到n（n+1）/2個存儲空間中。返回本章目錄5.2 稀疏矩陣 矩陣中大多數(shù)元素的值為零，只有少部分元素的值非零，并且，這些非零元素在矩陣中的分布沒有一定的規(guī)律性，這種矩陣稱為稀疏矩陣。 稀疏矩陣的抽象數(shù)據(jù)類型 （參見教材） 5.2.1 稀疏矩陣的三元組表示一個三元組（i，j，aij）便能唯一地確定矩陣中的一個非零元素，其中,aij表示矩陣第i行第j列非零元素的值。 若以某種方式（如上，按行序為主序的順序）將各個三元組排列起來，則所形成的表就能唯一地確定稀疏矩陣，從而得到稀疏矩陣的一種壓縮存儲方式，即三元組順序表。 稀疏矩陣的三元組順序表存儲結(jié)構(gòu)define MAXSI

54、ZE 1000 /非零元素的個數(shù)最多為1000typedef struct int row，col;/該非零元素的行下標(biāo)和列下標(biāo) ElemType data;/該非零元素的值 Triple;typedef struct Triple dataMAXSIZE+1;/非零元素的三元組順序表，data0未用 int m，n，len;/矩陣的行數(shù)、 列數(shù)和非零元素的個數(shù)SMatrix;1.轉(zhuǎn)置運算矩陣的轉(zhuǎn)置：通過變換元素的位置，把位于（row，col）位置上的元素換到（col，row）位置上，得到一個新的矩陣。 在稀疏矩陣的三元組順序表存儲結(jié)構(gòu)下，為了保證轉(zhuǎn)置后矩陣的三元組順序表仍按行序為主序的進行存

55、儲，需要按照col從小到大的順序完成元素位置的變換。為了找到所有的非零元素，需要對其data域從第1行起整個掃描一遍。具體算法描述如下。 inti , j, k ; dst-m= src.n ; dst -n= src.m ; dst -len= src.len ; if(dst-len0) j=1; for(k=1; k= src.n; k+) for(i=1; idataj.row = src.datai.col;dst-dataj.col = src.datai.row; dst-dataj.data = src.datai.data; j+; / Transpose void Tran

56、spose (SMatrix src, Smatrix* dst)2.乘法運算采用三元組順序表來實現(xiàn)時，由于乘積矩陣的三元組順序表仍要按行序為主序的進行存儲，可以采用固定矩陣M的三元組順序表中的元素（i，k，aik）（1iq，1kr），在矩陣N的三元組順序表中找所有行號為k的對應(yīng)元素（k，j，akj）（1ks，1jt）進行相乘、累加，從而得到，并且僅當(dāng)時矩陣P的三元組順序表中才有元素（i，j，pij）。注意：稀疏矩陣的乘積不一定是稀疏矩陣。具體算法 （參見教材）5.2.2 稀疏矩陣的十字鏈表表示十字鏈表又稱正交鏈表，是三元組的鏈接表示。稀疏矩陣的每個非零元素仍由三元組表示，這些三元組通過鏈接方

57、式相互關(guān)聯(lián)。十字鏈表的每個結(jié)點中除了矩陣元素的三元組信息外，還包含指向同一行下一個非零元素的指針域(right)和指向同一列下一個非零元素的指針域(down)。這樣，整個矩陣就構(gòu)成了一個十字交叉的鏈表，故稱之為十字鏈表。十字鏈表結(jié)點的結(jié)構(gòu)類型說明如下：typedef struct OLNode introw，col; /非零元素的行和列下標(biāo) ElemTypedata; struct OLNode* right，*down; /非零元素所在行表、列表的后繼鏈域 OLNode; *OLink; 在稀疏矩陣的十字鏈表表示中，行鏈表是由稀疏矩陣中同行的非零元素組成的鏈表，列鏈表是同列的非零元素組成的鏈

58、表。一個mn的矩陣包含m個行鏈表和n個列鏈表?？梢杂脙蓚€一維數(shù)組分別存儲每個行鏈表的頭指針和每個列鏈表的頭指針，從而得到十字鏈表的結(jié)構(gòu)類型說明如下：typedef struct OLink * row_head，*col_head;/行、列鏈表的頭指針 intm，n，len;/稀疏矩陣的行數(shù)、列數(shù)、非零元素數(shù) CrossList;數(shù)組是一種特殊的數(shù)據(jù)結(jié)構(gòu)，它用來表示有序的、相同類型的數(shù)據(jù)的集合。作為一種靜態(tài)的數(shù)據(jù)結(jié)構(gòu)，數(shù)組必須在聲明時用常量指定大小。數(shù)組元素的訪問是通過指定數(shù)組名和下標(biāo)進行的。數(shù)組中的元素是按照下標(biāo)順序連續(xù)存儲的，特定元素的存儲位置可以根據(jù)數(shù)組首元素的地址及該元素相對于首元素的

59、偏移量進行計算。對于多維數(shù)組，不同語言采取的存儲主序是不同的。特殊矩陣由于元素值呈現(xiàn)出一定的規(guī)律性，可以進行壓縮存儲以節(jié)省存儲空間，這就需要對特定元素存儲位置的計算公式進行調(diào)整。稀疏矩陣采用三元組順序表只存儲非零元素雖然可以大幅度的節(jié)省存儲空間，但實現(xiàn)矩陣轉(zhuǎn)置和乘法運算時，即使借助于一些輔助數(shù)組，仍需要耗費較多的時間。十字鏈表是三元組的鏈接表示，它的創(chuàng)建過程更加復(fù)雜。1. C語言中數(shù)組下標(biāo)從0開始，且C語言采用的是按行序為主序的存儲方式，請推導(dǎo)C語言中 1）一維數(shù)組元素地址的計算公式。 2）二維數(shù)組元素地址的計算公式。2. 對于矩陣，其每個元素占六個存儲單元，且的存儲地址為1500 1）如果是

60、下三角矩陣，求元素的存儲地址。 2）如果是上三角矩陣，求元素的存儲地址。 3）如果是對稱矩陣，保存為下三角矩陣，求元素的存儲地址。3. 已知稀疏矩陣和如下圖所示，試寫出這兩個矩陣及其轉(zhuǎn)置矩陣的三元組表示。結(jié)束第六章 樹和二叉樹6.1 樹 6.2 二叉樹 6.3 二叉樹的遍歷 6.4 森林與二叉樹的轉(zhuǎn)換 6.5 哈夫曼樹及其應(yīng)用 6.1 樹 樹是一種非線性的層次結(jié)構(gòu)。在客觀世界中，我們所熟悉的人類家族譜系和各種社會管理機構(gòu)的組織架構(gòu)都反映了這種層次結(jié)構(gòu)。在計算機科學(xué)中，樹為具有層次關(guān)系或分支關(guān)系的數(shù)據(jù)提供了一種自然的表示，可以用來描述操作系統(tǒng)中文件系統(tǒng)的結(jié)構(gòu)，也可以用來組織數(shù)據(jù)庫系統(tǒng)的信息，還可