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

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

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

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

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

5、做算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度（Time Complexity）。 算法的時(shí)間復(fù)雜度常見(jiàn)的有：常量階O(1)、線性階O(n)、平方階O(n2) 、立方階O(n3)、對(duì)數(shù)階O(log2n)、指數(shù)階O(2n)等。不同數(shù)量級(jí)時(shí)間復(fù)雜度的性狀如下圖所示?！纠?】 起泡排序的算法描述如下，分析其時(shí)間復(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解：在上述起泡排序算法中，問(wèn)題的基本操作是“交換序列中相鄰兩個(gè)元素”，初始序列的狀態(tài)不同，該基本操作的重復(fù)次數(shù)也有很大不同： 最好情況：當(dāng)初始序列為自小至大有序時(shí)，基本操作的重復(fù)次數(shù)為0，時(shí)間復(fù)雜度為O(1)； 最壞情況：當(dāng)初始序列為自大至小有序時(shí)，基本操作的重復(fù)次數(shù)為： 1+2+3+n-1 =n(n-1)/2 時(shí)間復(fù)雜度為:O(n2) 平均情況：假設(shè)初始序列可能出現(xiàn)的排列情況（共n!種）的概率相等，則時(shí)間復(fù)雜度為O(n2)。通常，時(shí)間復(fù)雜度的評(píng)價(jià)指標(biāo)可以分為以下三種：最好時(shí)間復(fù)雜度：在最好情況下執(zhí)行一個(gè)算法所需要的時(shí)間。最壞時(shí)間復(fù)雜度：在最壞情況下執(zhí)行一個(gè)

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

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

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

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

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

12、長(zhǎng)度運(yùn)算int ListLength (SqList sq) return(sq.len); 3.求線性表中第i個(gè)元素運(yùn)算ElemType GetElem(SqList sq,int i) if (isq.len) / i 值不合法 return 0; else return(sq.datai-1); 4.按值查找運(yùn)算int LocateElem(SqList sq, ElemType e) int i=0; while (i=sq.len) return 0; else return i+1; 5. 插入元素運(yùn)算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+; / 表長(zhǎng)增1 return 1;6. 刪除元素運(yùn)算 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、; / 表長(zhǎng)減1 return 1;2.2.3 順序?qū)崿F(xiàn)的算法分析1. 插入假設(shè)pi是在第i個(gè)位置插入一個(gè)元素的概率，則在長(zhǎng)度為n的線性表中插入一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為：pi=1/(n+1)插入算法的平均時(shí)間復(fù)雜度為O(n)。2. 刪除假設(shè)qi是在第i個(gè)位置刪除一個(gè)元素的概率，則在長(zhǎng)度為n的線性表中刪除一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為：qi=1/n刪除算法的平均時(shí)間復(fù)雜度為O(n)。2.2.4 順序表的應(yīng)用舉例【例1】 編寫(xiě)一算法，從順序表中刪除自第i個(gè)元素開(kāi)始的k個(gè)元素。算法思路： 為保持順序表的邏輯特性，需將i+k n位置的所有元素依次前移k個(gè)位置。算法如下： 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】巳知有兩個(gè)按元素值遞增有序的順序表La和Lb，設(shè)計(jì)一個(gè)算法將表La和表Lb的全部元素歸并為一個(gè)按元素值遞增有序的順序表Lc。算法思路：用i掃描順序表La，用j掃描順序表Lb。當(dāng)表La和表Lb都未掃描完時(shí)，比較兩者的當(dāng)前元素，將較小者插入表Lc的表尾，若兩者的當(dāng)前元素相等，則將這兩個(gè)元素依次插入表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都未掃描完時(shí) 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）求線性表長(zhǎng)度 int ListLength(LinkList h) int i=1; LNode *p=h-next; while (p-next!=NULL) /當(dāng)p指向最后一個(gè)數(shù)據(jù)結(jié)點(diǎn)時(shí)，循環(huán)停止 p=p-next; i+; /指針p沿著next域移動(dòng)一次，i值增1 return i; （3）求線性表中第i個(gè)元素 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個(gè)結(jié)點(diǎn)的指針 本算法的時(shí)間復(fù)雜度為O(n)。（4）按值查找 LNode *LocateElem(LinkList h,ElemType e) LNode *p=h-next; while (p!=NULL & p-data!=e) /從第1個(gè)結(jié)點(diǎn)開(kāi)始，查找data域?yàn)閑的結(jié)點(diǎn) p=p-next; return p; （5）插入結(jié)點(diǎn) 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é)點(diǎn)開(kāi)始，查找第i-1個(gè)結(jié)點(diǎn) s=( LNode *)malloc(sizeof(LNode); /創(chuàng)建新結(jié)點(diǎn) s-data=e; s-next=p-next; p-next=s; /插入鏈表中 return 1; （6）刪除結(jié)點(diǎn) int ListDelete(LinkList &h,int i) int j=0; LNode *p=h,*q; if (i ListLength(h) return 0; /i值不合法 while (jnext; j+; /從頭結(jié)點(diǎn)開(kāi)始，查找第i-1個(gè)結(jié)點(diǎn) q=p-next; /刪除并釋放結(jié)點(diǎn) 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é)點(diǎn)的data域 p=p-next; 2. 建立單鏈表 （1） 頭插法建表 算法思路：從一個(gè)空表開(kāi)始，讀取數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀取的數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(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é)點(diǎn) h-next=NULL; for (i=0;idata=ai; s-next=h-next; / 將新結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之后 h-next=s; / CreateListF（2) 尾插法建表 算法思路：將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，為此必須增加一個(gè)尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。 算法如下： void CreateListR(LinkList &h,ElemType a,int n) LNode *s,*r; int i; h=( LNode *)malloc(sizeof(LNode); / 創(chuàng)建頭結(jié)點(diǎn) r

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

23、c指向hc表中當(dāng)前最后一個(gè)結(jié)點(diǎn)。 比較pa-data和pb-data,將較小者插入hc的表尾，即鏈到pc所指結(jié)點(diǎn)之后。若pa-data和pb-data相等，則將兩個(gè)結(jié)點(diǎn)均鏈到pc所指結(jié)點(diǎn)之后。 如此反復(fù)，直到有一個(gè)表的元素已歸并完（pa或pb為空）為止，再將另一個(gè)表的剩余段鏈接到pc所指結(jié)點(diǎn)之后。 具體算法：void MergeList_L(LinkList &ha, LinkList &hb, LinkList &hc) LNode *pa,*pb,*pc; pa=ha-next; pb=hb-next; hc=pc=ha; / 用ha的頭結(jié)點(diǎn)作為hc的頭結(jié)點(diǎn)，pc始終指向hc的表尾結(jié)點(diǎn) 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é)點(diǎn)/ MergeList_L本算法的基本操作是結(jié)點(diǎn)數(shù)據(jù)的比較和結(jié)點(diǎn)的鏈入，在最壞情況下，對(duì)每個(gè)結(jié)點(diǎn)均需進(jìn)行上述操作，因此，若表ha和表hb的長(zhǎng)度分別是m和n，則本

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

26、針。 例如，求線性表的長(zhǎng)度運(yùn)算在單循環(huán)鏈表上的實(shí)現(xiàn)算法如下： int ListLength(LinkList h) int i=1; LNode *p=h-next; while (p-next!=h) /當(dāng)p指向最后一個(gè)數(shù)據(jù)結(jié)點(diǎn)時(shí)，循環(huán)停止 p=p-next; i+; /指針p沿著next域移動(dòng)一次，i值增1 return i; / ListLength(a)雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu) (b) 空的雙向循環(huán)鏈表 (c) 非空的雙向循環(huán)鏈表2.3.3 雙向鏈表 在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域，其一指向直接后繼，另一指向直接前驅(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é)點(diǎn)開(kāi)始，查找第i個(gè)結(jié)點(diǎn) p-prior-next=p-next; /刪除并釋放結(jié)點(diǎn) 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é)點(diǎn)開(kāi)始，查找第i個(gè)結(jié)點(diǎn) s=( DuLNode *)malloc(sizeof(DuLNode); /創(chuàng)建新結(jié)點(diǎn) s-data=e; s-prior=p-prior; p-prior-next=s; /插入鏈表中 s-next=p; p-prior=s; return 1; / ListInsert_DuL線性表是一種典型的線性結(jié)構(gòu)。線性表中的元素可以是各種各樣的，但同一線性表中的元素必具有相同的特性。順序表是以“物理位置相鄰”來(lái)表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系的，通常用數(shù)組來(lái)描述。鏈表是通

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

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

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

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

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

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

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

36、ata=x; p-next=ls; ls=p; 3. 出棧運(yùn)算 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. 取棧頂元素運(yùn)算 int GetTop(LinkStack ls,ElemType &x) if (ls=NULL) return 0; else x=ls-data; return 1; 5. 判斷?？者\(yùn)算 int StackEmpty(LinkStack ls) if (ls=NULL)

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

38、教材 返回本章目錄3.4 棧與遞歸的實(shí)現(xiàn)棧的一個(gè)重要應(yīng)用是在程序設(shè)計(jì)語(yǔ)言中實(shí)現(xiàn)遞歸。一個(gè)直接調(diào)用自己或通過(guò)一系列的調(diào)用語(yǔ)句間接地調(diào)用自己的函數(shù)，稱(chēng)做遞歸函數(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; 遞歸是把一個(gè)不能或不好直接求解的“大問(wèn)題”轉(zhuǎn)化成一個(gè)或幾個(gè)“小問(wèn)題”來(lái)解決，再把這些“小問(wèn)題”進(jìn)一步分解成更小的“小問(wèn)題”來(lái)解決，如此分解，直至每個(gè)“小問(wèn)題”都可以直接解決，此時(shí)遞歸終止，逐層返回。計(jì)算fac(3)的過(guò)程如 下：遞歸調(diào)用的特點(diǎn)是：主調(diào)函數(shù)和被調(diào)函數(shù)是同一個(gè)函數(shù)，因此，在一個(gè)遞歸函數(shù)的運(yùn)行過(guò)程中，一個(gè)和每次調(diào)用相關(guān)的重要概念是遞歸函數(shù)運(yùn)行的“層次”。為了保證遞歸函數(shù)正確執(zhí)行，系統(tǒng)需設(shè)立一個(gè)“遞歸工作?！弊鳛檎麄€(gè)遞歸函數(shù)運(yùn)行期間使用的數(shù)據(jù)存儲(chǔ)區(qū)。每一層遞歸所需信息構(gòu)成一個(gè)“工作記錄”，其中包括所有的實(shí)際參數(shù)、所有的局部變量以及上一層的返回地址。每進(jìn)入一層遞歸，就產(chǎn)生一個(gè)新

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

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

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

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

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

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

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

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

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

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

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

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

54、ZE 1000 /非零元素的個(gè)數(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ù)和非零元素的個(gè)數(shù)SMatrix;1.轉(zhuǎn)置運(yùn)算矩陣的轉(zhuǎn)置：通過(guò)變換元素的位置，把位于（row，col）位置上的元素?fù)Q到（col，row）位置上，得到一個(gè)新的矩陣。 在稀疏矩陣的三元組順序表存儲(chǔ)結(jié)構(gòu)下，為了保證轉(zhuǎn)置后矩陣的三元組順序表仍按行序?yàn)橹餍虻倪M(jìn)行存

55、儲(chǔ)，需要按照col從小到大的順序完成元素位置的變換。為了找到所有的非零元素，需要對(duì)其data域從第1行起整個(gè)掃描一遍。具體算法描述如下。 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.乘法運(yùn)算采用三元組順序表來(lái)實(shí)現(xiàn)時(shí)，由于乘積矩陣的三元組順序表仍要按行序?yàn)橹餍虻倪M(jìn)行存儲(chǔ)，可以采用固定矩陣M的三元組順序表中的元素（i，k，aik）（1iq，1kr），在矩陣N的三元組順序表中找所有行號(hào)為k的對(duì)應(yīng)元素（k，j，akj）（1ks，1jt）進(jìn)行相乘、累加，從而得到，并且僅當(dāng)時(shí)矩陣P的三元組順序表中才有元素（i，j，pij）。注意：稀疏矩陣的乘積不一定是稀疏矩陣。具體算法 （參見(jiàn)教材）5.2.2 稀疏矩陣的十字鏈表表示十字鏈表又稱(chēng)正交鏈表，是三元組的鏈接表示。稀疏矩陣的每個(gè)非零元素仍由三元組表示，這些三元組通過(guò)鏈接方

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

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

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

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