數(shù)據(jù)結(jié)構(gòu)考研講義

1、目錄緒論 0.1 基本概念 第一章 線性表 1.1 線性表的定義 1.2 線性表的實(shí)現(xiàn) 1.2.2 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 第二章 棧、隊(duì)列和數(shù)組 棧 隊(duì)列 特殊矩陣的壓縮存儲(chǔ) 2.3.1 數(shù)組 2.3.2 特殊矩陣 第三章 樹與二叉樹 樹的概念 1.樹的定義 2相關(guān)術(shù)語(yǔ) 二叉樹 3.2.13.2.23.2.33.2.42.12.22.33.13.2定義與性質(zhì) . 二叉樹的存儲(chǔ) 二叉樹的遍歷 線索二叉樹 .71212161818182121213.3樹和森林 3.3.1 樹的存儲(chǔ)結(jié)構(gòu) 3.3.2 森林和二叉樹的轉(zhuǎn)換 3.3.3 樹和森林的遍歷 哈夫曼( Huffman )樹和哈夫曼編碼21222

2、2232426303031313.4第四章 圖圖的概念 圖的存儲(chǔ)及基本操作 4.2.1 鄰接矩陣 4.2.2 鄰接表 圖的遍歷 4.3.1 深度優(yōu)先搜索 4.3.2 廣度優(yōu)先搜索 圖的基本應(yīng)用 4.4.1 4.4.2 4.4.3 4.4.4 第五章 查找 .4.14.24.34.4最小生成樹 最短路徑 . 拓?fù)渑判?. 關(guān)鍵路徑 .3233333434343636363838394041435.15.25.35.4查找的基本概念順序查找法 折半查找法 動(dòng)態(tài)查找樹表 .434445465.4.1 二叉排序樹 5.4.2 平衡二叉樹 543 B樹及其基本操作、B+樹的基本概念5.5 散列表5.5.

3、25.5.3464850常用的散列函數(shù)處理沖突的方法散列表的查找 散列表的查找分析5252535.5.45.5.5 第六章 排序 .插入排序 6.1.1 直接插入排序 6.1.2 折半插入排序 冒泡排序 簡(jiǎn)單選擇排序 希爾排序 快速排序 堆排序 二路歸并排序 基數(shù)排序 各種內(nèi)部排序算法的比較6.16.26.36.46.56.66.76.86.95454555555555657585961636465緒論1 、數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組Data_Structure =( D, R),其中，D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。2

4、、邏輯結(jié)構(gòu)：是指數(shù)據(jù)之間的相互關(guān)系。通常分為四類結(jié)構(gòu)：(3、0.1 基本概念1)2)3)4)集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。 樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。 圖狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。存儲(chǔ)結(jié)構(gòu)：是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，又稱為數(shù)據(jù)的物理結(jié)構(gòu)。通常由四種基本的存儲(chǔ)方法實(shí)現(xiàn)：( 1 )順序存儲(chǔ)方式。數(shù)據(jù)元素順序存放，每個(gè)存儲(chǔ)結(jié)點(diǎn)只含一個(gè)元素。存儲(chǔ)位置反映數(shù)據(jù)元素間的 邏輯關(guān)系。存儲(chǔ)密度大。但有些操作(如插入、刪除)效率較差。( 2)鏈?zhǔn)酱鎯?chǔ)方式。每個(gè)存儲(chǔ)結(jié)點(diǎn)除包含數(shù)據(jù)元素信息外還包

5、含一組(至少一個(gè))指針。指針反映 數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲(chǔ)空間連續(xù)，便于動(dòng)態(tài)操作(如插入、刪除等)，但存儲(chǔ)空間開銷大(用于指針) ，另外不能折半查找等。( 3)索引存儲(chǔ)方式。除數(shù)據(jù)元素存儲(chǔ)在一組地址連續(xù)的內(nèi)存空間外，還需建立一個(gè)索引表，索引表 中索引指示存儲(chǔ)結(jié)點(diǎn)的存儲(chǔ)位置(下標(biāo))或存儲(chǔ)區(qū)間端點(diǎn)(下標(biāo))。( 4)散列存儲(chǔ)方式。通過散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)， 并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲(chǔ)地址。其特點(diǎn)是存取速度快， 只能按關(guān)鍵字隨機(jī)存取，不能順序存取，也不能折半存取。2 算法和算法的衡量1、算法是對(duì)特定問題求解步驟的一種描述， 是指

6、令的有限序列。 其中每一條指令表示一個(gè)或多個(gè)操作。 算法具有下列特性：有窮性確定性可行性輸入輸出。算法和程序十分相似，但又有區(qū)別。程序不一定具有有窮性，程序中的指令必須是機(jī)器可執(zhí)行的，而 算法中的指令則無此限制。算法代表了對(duì)問題的解，而程序則是算法在計(jì)算機(jī)上的特定的實(shí)現(xiàn)。一個(gè) 算法若用程序設(shè)計(jì)語(yǔ)言來描述，則它就是一個(gè)程序。2、算法的時(shí)間復(fù)雜度：以基本運(yùn)算的原操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。一般情況下，算法中基本運(yùn)算次數(shù) T(n)是問題規(guī)模n (輸入量的多少，稱之為問題規(guī)模)的某個(gè)函數(shù)f(n),記作：T(n) = O (f(n);也可表示 T(n) = m(f(n)，其中m為常量。記號(hào)&q

7、uot;O”讀作"大 O”，它表示隨問題 規(guī)模n的增大，算法執(zhí)行時(shí)間 T(n)的增長(zhǎng)率和f(n)的增長(zhǎng)率相同。 注意：有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。 常見的漸進(jìn)時(shí)間復(fù)雜度有：O (1) <O (Iog2 n) <O (n) <O (nl og2 n) vO (n2) <O (n3) <O (2n) < O(n!) < O( nn)。3、算法的空間復(fù)雜度：是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間大小的量度。只需要 分析除輸入和程序之外的輔助變量所占額外空間。原地工作：若所需額外空間相對(duì)于輸入數(shù)據(jù)量來說

8、是常數(shù)，則稱此算法為原地工作，空 間復(fù)雜度為 O(1)。第一章 線性表1.1 線性表的定義線性表是一種線性結(jié)構(gòu)，在一個(gè)線性表中數(shù)據(jù)元素的類型是相同的，或者說線性表是由同一類型的數(shù) 據(jù)元素構(gòu)成的線性結(jié)構(gòu)，定義如下：線性表是具有相同數(shù)據(jù)類型的n(n > 0)個(gè)數(shù)據(jù)元素的有限序列，通常記為：(a1, a2,ai-1, ai, ai+1,an)其中n為表長(zhǎng)，n = 0時(shí)稱為空表。需要說明的是： ai為序號(hào)為i的數(shù)據(jù)元素(i=1,2,n),通常將它的數(shù)據(jù)類型抽象為ElemTy pe,ElemT ype根據(jù)具體問題而定。1.2 線性表的實(shí)現(xiàn)1.2.1 線性表的順序存儲(chǔ)結(jié)構(gòu)1.順序表線性表的順序存儲(chǔ)是

9、指在內(nèi)存中用地址連續(xù)的一塊存儲(chǔ)空間順序存放線性表的各元素，用這種存儲(chǔ)形 式存儲(chǔ)的線性表稱其為順序表。因?yàn)閮?nèi)存中的地址空間是線性的，因此，用物理上的相鄰實(shí)現(xiàn)數(shù)據(jù)元 素之間的邏輯相鄰關(guān)系是既簡(jiǎn)單又自然的。設(shè)a 1的存儲(chǔ)地址為L(zhǎng)oc(al )，每個(gè)數(shù)據(jù)元素占d個(gè)存儲(chǔ)地址，則第i個(gè)數(shù)據(jù)元素的地址為：Loc(ai)=Loc(a 1 )+(i-1)*d 1 < i< n 這就是說只要知道順序表首地址和每個(gè)數(shù)據(jù)元素所占地址單元的個(gè)數(shù)就可求出第 來，這也是順序表具有按數(shù)據(jù)元素的序號(hào)隨機(jī)存取的特點(diǎn)。線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)：#define LIST_INIT_SIZE 100 /存儲(chǔ)空間的初始分

10、配量#define LISTINCREMENT 10 /存儲(chǔ)空間的分配增量typedef structElemType *elem;int length;int listsize;SqList;/ 線性表的存儲(chǔ)空間基址/ 當(dāng)前長(zhǎng)度/ 當(dāng)前已分配的存儲(chǔ)空間2.順序表上基本運(yùn)算的實(shí)現(xiàn) ( 1 )順序表的初始化 順序表的初始化即構(gòu)造一個(gè)空表， 首先動(dòng)態(tài)分配存儲(chǔ)空間，然后，將 int Init_SqList (SqList &L)i 個(gè)數(shù)據(jù)元素的地址這對(duì)表是一個(gè)加工型的運(yùn)算，因此， 將L設(shè)為引用參數(shù),length 置為 0,表示表中沒有數(shù)據(jù)元素。L.elem = (ElemType * )ma

11、lloc(LIST_INIT_SIZE * sizeof(ElemType); if (!L.elem) exit (OVERFLOW);L.length=0;L. listsize = LIST_INIT_SIZE; return OK;/ 存儲(chǔ)分配失敗/ 初始存儲(chǔ)容量 ( 2 )插入運(yùn)算線性表的插入是指在表的第i(i的取值范圍：1 w iw n+1)個(gè)位置上插入一個(gè)值為x的新元素,n 的表:ai-1 ， ai， ai+1 ，. ， an)n+1 表:插入后使原表長(zhǎng)為(a1 ， a2，成為表長(zhǎng)為ai-1 ， x， ai， ai+1 ，.， an ) 。(a1 ， a2， 順序表上完成這一運(yùn)算

12、則通過以下步驟進(jìn)行： 將aian順序向下移動(dòng)，為新元素讓出位置；(注意數(shù)據(jù)的移動(dòng)方向：從后往前依次后移一個(gè)元素) 將 x 置入空出的第 i 個(gè)位置； 修改表長(zhǎng)。int Insert_SqList (SqList &L， int i ， ElemType x) if (i < 1 | i > L.length+1) return ERROR; / 插入位置不合法 if (L.length >= L.listsize) return OVERFLOW; / 當(dāng)前存儲(chǔ)空間已滿 ,不能插入 / 需注意的是，若是采用動(dòng)態(tài)分配的順序表，當(dāng)存儲(chǔ)空間已滿時(shí)也可增加分配 q = &am

13、p;(L.elemi-1);/ q指示插入位置插入位置及之后的元素右移 插入 e 表長(zhǎng)增 1for (p = &(L.elemL.length-1); p >= q; -p) *(p+1) = *p;/*q = e;/+L.length;/return OK;在第 i 個(gè)位置上插入 x ， 從 ai 到 an 都 順序表上的插入運(yùn)算， 時(shí)間主要消耗在了數(shù)據(jù)的移動(dòng)上， 要向下移動(dòng)一個(gè)位置，共需要移動(dòng)ni1 個(gè)元素。( 3 )刪除運(yùn)算 線性表的刪除運(yùn)算是指將表中第 i ( 刪除后使原表長(zhǎng)為i 的取值范圍為K iw n)個(gè)元素從線性表中去掉,n 的線性表：(a1 ， a2， 成為表長(zhǎng)為

14、n1ai-1 ， ai， ai+1 ，的線性表：an)ai-1 ， ai+1 ，(a1 ， a2，順序表上完成這一運(yùn)算的步驟如下： 將 ai+1an 順序向上移動(dòng)； (注意數(shù)據(jù)的移動(dòng)方向：從前往后依次前移一個(gè)元素) 修改表長(zhǎng)。int Delete_SqList (SqList &L;int i) if (i < 1) | (i > L.length) return ERROR; p = &(L.elemi-1); e = *p;q = L.elem+L.length-1; for (+p; p <= q; +p) *(p-1) = *p;-L.length;

15、return OK; 順序表的刪除運(yùn)算與插入運(yùn)算相同，其時(shí)間主要消耗在了移動(dòng)表中元素上，刪除第/ 刪除位置不合法/ p 為被刪除元素的位置 被刪除元素的值賦給 e 表尾元素的位置/被刪除元素之后的元素左移表長(zhǎng)減 1i 個(gè)元素時(shí)，其后面的元素ai+1an都要向上移動(dòng)一個(gè)位置，共移動(dòng)了n-i個(gè)元素，順序表的插入、刪除需移動(dòng)大量O(1)。元素0(n);但在尾端插入、刪除效率高1.2.2 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1.2.2.1 單鏈表1.鏈表表示 鏈表是通過一組任意的存儲(chǔ)單元來存儲(chǔ)線性表中的數(shù)據(jù)元素的。為建立起數(shù)據(jù)元素之間的線性關(guān)系，對(duì)每個(gè)數(shù)據(jù)元素 ai,除了存放數(shù)據(jù)元素的自身的信息ai之外，還需要和 a

16、i 一起存放其后繼 ai+1所在的存儲(chǔ)單元的地址，這兩部分信息組成一個(gè)“結(jié)點(diǎn)” ，結(jié)點(diǎn)的結(jié)構(gòu)如圖所示。 其中，存放數(shù)據(jù)元素信息的稱為數(shù)據(jù)域，存放其后繼地址的稱為指針域。因此n 個(gè)元素的線性表通過每個(gè)結(jié)點(diǎn)的指針域拉成了一個(gè)“鏈” ，稱之為鏈表。因?yàn)槊總€(gè)結(jié)點(diǎn)中只有一個(gè)指向后繼的指針，所以稱 其為單鏈表。線性表的單鏈表存儲(chǔ)結(jié)構(gòu) C語(yǔ)言描述下： typedef struct LNode ElemType data; / 數(shù)據(jù)域 struct LNode *next; / 指針域LNode， *LinkList;LinkList L；/ L 為單鏈表的頭指針通常用“頭指針”來標(biāo)識(shí)一個(gè)單鏈表，如單鏈表L、

17、單鏈表H等，是指某鏈表的第一個(gè)結(jié)點(diǎn)的地址放在了指針變量 L、 H中，頭指針為“ NULL”則表示一個(gè)空表。2.單鏈表上基本運(yùn)算的實(shí)現(xiàn)(1) 建立單鏈表 單鏈表結(jié)點(diǎn)結(jié)構(gòu)data next頭插法在鏈表的頭部插入結(jié)點(diǎn)建立單鏈表鏈表與順序表不同， 它是一種動(dòng)態(tài)管理的存儲(chǔ)結(jié)構(gòu)， 鏈表中的每個(gè)結(jié)點(diǎn)占用的存儲(chǔ)空間不是預(yù)先分配， 而是運(yùn)行時(shí)系統(tǒng)根據(jù)需求而生成的，因此建立單鏈表從空表開始，每讀入一個(gè)數(shù)據(jù)元素則申請(qǐng)一個(gè)結(jié) 點(diǎn)，然后插在鏈表的頭部。LinkList CreateListF ( )LinkList L=NULL;/ 空表LNode *s;int x;/ 設(shè)數(shù)據(jù)元素的類型為 intscanf(%d,&a

18、mp;x);while (x!=flag) s=(LNode *)malloc(sizeof(LNode);s->data=x;s->next=L; L=s;scanf (%d,&x);return L;若希望次序 r 用來始終不是結(jié)束標(biāo)尾插法在單鏈表的尾部插入結(jié)點(diǎn)建立單鏈表 頭插入建立單鏈表簡(jiǎn)單， 但讀入的數(shù)據(jù)元素的順序與生成的鏈表中元素的順序是相反的， 一致，則用尾插入的方法。因?yàn)槊看问菍⑿陆Y(jié)點(diǎn)插入到鏈表的尾部，所以需加入一個(gè)指針 指向鏈表中的尾結(jié)點(diǎn)，以便能夠?qū)⑿陆Y(jié)點(diǎn)插入到鏈表的尾部。初始狀態(tài)， 頭指針 L=NULL， 尾指針 r=NULL; 按線性表中元素的順序依次讀

19、入數(shù)據(jù)元素， 志時(shí)，申請(qǐng)結(jié)點(diǎn)，將新結(jié)點(diǎn)插入到 r 所指結(jié)點(diǎn)的后面，然后 r 指向新結(jié)點(diǎn)(注意第一個(gè)結(jié)點(diǎn)有所不 同)。LinkList CreateListR1 ( )LinkList L=NULL;LNode *s,*r=NULL;/ 設(shè)數(shù)據(jù)元素的類型為 intint x;scanf(%d,&x);while (x!=flag) s=(LNode *)malloc(sizeof(LNode); s->data=x;/ 第一個(gè)結(jié)點(diǎn)的處理/ 其它結(jié)點(diǎn)的處理/r 指向新的尾結(jié)點(diǎn)if (L=NULL) L=s;else r->next=s;r=s;scanf(%d,&x);

20、if ( r!=NULL) r->next=NULL; /對(duì)于非空表，最后結(jié)點(diǎn)的指針域放空指針return L;在算法 CreateListR1 中，第一個(gè)結(jié)點(diǎn)的處理和其它結(jié)點(diǎn)是不同的，原因是第一個(gè)結(jié)點(diǎn)加入時(shí)鏈表為空， 它沒有直接前驅(qū)結(jié)點(diǎn)，它的地址就是整個(gè)鏈表的指針，需要放在鏈表的頭指針變量中；而其它結(jié)點(diǎn)有 直接前驅(qū)結(jié)點(diǎn)，其地址放入直接前驅(qū)結(jié)點(diǎn)的指針域。 “第一個(gè)結(jié)點(diǎn)”的問題在很多操作中都會(huì)遇到， 如在鏈表中插入結(jié)點(diǎn)時(shí)，將結(jié)點(diǎn)插在第一個(gè)位置和其它位置是不同的，在鏈表中刪除結(jié)點(diǎn)時(shí)，刪除第 一個(gè)結(jié)點(diǎn)和其它結(jié)點(diǎn)的處理也是不同的，等等。為了方便操作，有時(shí)在鏈表的頭部加入一個(gè)“頭結(jié)點(diǎn)” ，頭結(jié)點(diǎn)的

21、類型與數(shù)據(jù)結(jié)點(diǎn)一致，標(biāo)識(shí)鏈表的頭 指針變量L中存放該結(jié)點(diǎn)的地址，這樣即使是空表，頭指針變量L也不為空了。頭結(jié)點(diǎn)的加入使得“第一個(gè)結(jié)點(diǎn)”的問題不再存在，也使得“空表”和“非空表”的處理成為一致。 頭結(jié)點(diǎn)的加入完全是為了運(yùn)算的方便， 它的數(shù)據(jù)域無定義， 指針域中存放的是第一個(gè)數(shù)據(jù)結(jié)點(diǎn)的地址， 空表時(shí)為空。尾插法建立帶頭結(jié)點(diǎn)的單鏈表，將算法CreateListRI改寫成算法 CreateListR2形式。LinkList CreateListR2( )LinkList L=(LNode *)malloc(sizeof(LNode);L->next=NULL； / 空表LNode *s,*r=L

22、;int x; / 設(shè)數(shù)據(jù)元素的類型為 intscanf(%d,&x);while (x!=flag) s=(LNode *)malloc(sizeof(LNode);s->data=x;r->next=s;r=s; /r指向新的尾結(jié)點(diǎn)scanf(" %d" ,&x);r->n ext=NULL;return L;因此，頭結(jié)點(diǎn)的加入會(huì)帶來以下兩個(gè)優(yōu)點(diǎn)：第一個(gè)優(yōu)點(diǎn)：由于開始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，所以在鏈表的第一個(gè)位置上的操作就 和在表的其它位置上的操作一致，無需進(jìn)行特殊處理；第二個(gè)優(yōu)點(diǎn)：無論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn)在的

23、非空指針(空表中頭結(jié)點(diǎn)的指針域?yàn)榭?因此空表和非空表的處理也就統(tǒng)一了。在以后的算法中不加說明則認(rèn)為單鏈表是帶頭結(jié)點(diǎn)的。(2) 查找操作按序號(hào)查找 Get_L in kList(L,i)i個(gè)，若是，則返回該結(jié)點(diǎn)的指針，否則繼續(xù)后從鏈表的第一個(gè)元素結(jié)點(diǎn)起，判斷當(dāng)前結(jié)點(diǎn)是否是第一個(gè)，表結(jié)束為止，沒有第i個(gè)結(jié)點(diǎn)時(shí)返回空。LNode * Get_L in kList(L in kList L, i nt i); LNode * p=L;int j=0;while (p->n ext !=NULL && j<i )p=p->n ext; j+;if (j=i) retur

24、 n p;else return NULL;(3) 插入運(yùn)算后插結(jié)點(diǎn)：設(shè)P指向單鏈表中某結(jié)點(diǎn)，s指向待插入的值為x的新結(jié)點(diǎn)，將*s插入到*p的后面，插入示意圖如圖所示。在*P之后捕入羯操作如下： s->n ext =p->n ext; p->n ext=s;注意：兩個(gè)指針的操作順序不能交換。(4)刪除運(yùn)算刪除結(jié)點(diǎn)設(shè)P指向單鏈表中某結(jié)點(diǎn)，刪除*p。操作過程如圖。要實(shí)現(xiàn)對(duì)結(jié)點(diǎn)*p的刪除，首先要找到*p的前驅(qū)結(jié)點(diǎn)*q，然后完成指針的操作即可。操作如下：q=L;while (q->n ext!=p)q=q->next; /找*p的直接前驅(qū) q->n ext=p-&g

25、t;n ext;free( p);因?yàn)檎?p前驅(qū)的時(shí)間復(fù)雜度為O(n)，所以該操作的時(shí)間復(fù)雜度為O(n)通過上面的基本操作我們得知：(1) 單鏈表上插入、刪除一個(gè)結(jié)點(diǎn)，必須知道其前驅(qū)結(jié)點(diǎn)。(2) 單鏈表不具有按序號(hào)隨機(jī)訪問的特點(diǎn)，只能從頭指針開始一個(gè)個(gè)順序進(jìn)行。1.2.2.2循環(huán)鏈表對(duì)于單鏈表而言，最后一個(gè)結(jié)點(diǎn)的指針域是空指針，如果將該鏈表頭指針置入該指針域，則使得鏈表 頭尾結(jié)點(diǎn)相連，就構(gòu)成了單循環(huán)鏈表。NULL變?yōu)槭欠袷穷^指在單循環(huán)鏈表上的操作基本上與非循環(huán)鏈表相同，只是將原來判斷指針是否為針而已，沒有其它較大的變化。對(duì)于單鏈表只能從頭結(jié)點(diǎn)開始遍歷整個(gè)鏈表，而對(duì)于單循環(huán)鏈表則可以從表中任意結(jié)

26、點(diǎn)開始遍歷整個(gè) 鏈表，不僅如此，有時(shí)對(duì)鏈表常做的操作是在表尾、表頭進(jìn)行，此時(shí)可以改變一下鏈表的標(biāo)識(shí)方法， 不用頭指針而用一個(gè)指向尾結(jié)點(diǎn)的指針R來標(biāo)識(shí)，可以使得操作效率得以提高。1.223雙向鏈表單鏈表的結(jié)點(diǎn)中只有一個(gè)指向其后繼結(jié)點(diǎn)的指針域next，因此若已知某結(jié)點(diǎn)的指針為P,其后繼結(jié)點(diǎn)的指針則為p->next ,而找其前驅(qū)則只能從該鏈表的頭指針開始，順著各結(jié)點(diǎn)的next域進(jìn)行，也就是說找后繼的時(shí)間性能是 0(1),找前驅(qū)的時(shí)間性能是0(n),如果也希望找前驅(qū)的時(shí)間性能達(dá)到0(1),則只能付出空間的代價(jià)：每個(gè)結(jié)點(diǎn)再加一個(gè)指向前驅(qū)的指針域，結(jié)點(diǎn)的結(jié)構(gòu)為如圖所示，用這種結(jié)點(diǎn) 組成的鏈表稱為雙向

27、鏈表。prior data next線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)C語(yǔ)言描述下：typ edef struct DuLNodeElemT ype data;struct DuLNode *p rior,* next;DuLNode,*DuLi nkList;和單鏈表類似，雙向鏈表通常也是用頭指針標(biāo)識(shí)，也可以帶頭結(jié)點(diǎn)。(1)雙向鏈表中結(jié)點(diǎn)的插入：設(shè)P指向雙向鏈表中某結(jié)點(diǎn)，s指向待插入的值為x的新結(jié)點(diǎn)，將*s插入到*p的前面，插入示意圖如所示。田翠向«叢申附»點(diǎn)»入操作如下：s->pnor=p->p rior;p->pnor->n ext=s;s-&

28、gt;n ext=p;p->p rior=s;指針操作的順序不是唯一的，但也不是任意的，操作必須要放到操作的前面完成，否則*p的前驅(qū)結(jié)點(diǎn)的指針就丟掉了。(2)雙向鏈表中結(jié)點(diǎn)的刪除：設(shè)P指向雙向鏈表中某結(jié)點(diǎn)，刪除*p。操作示意圖如圖所示。P、廠下_S朋向儀規(guī)中除埔點(diǎn)1.2.2.4順序表和鏈表的比較操作如下： p->pnor->n ext=p->n ext;順序表以地址ffl鄰表示關(guān)系用捲針表不關(guān)系隨機(jī)»間，収元秦0(1)順訪問.収兀索插入，刪餘鬧®移動(dòng)元索05)插入、刪除不用移動(dòng)元案ox用j杳找 位買)總之, p->n ext- >pnor

29、=p->p rior; free( p);兩種存儲(chǔ)結(jié)構(gòu)各有長(zhǎng)短，選擇那一種由實(shí)際問題中的主要因素決定。通常“較穩(wěn)定” 的線性表選擇順序存儲(chǔ)，而頻繁做插入刪除的即動(dòng)態(tài)性較強(qiáng)的線性表宜選擇鏈?zhǔn)酱鎯?chǔ)。第二章 棧、隊(duì)列和數(shù)組2.1 棧2.1.1 棧的定義 棧是限制在表的一端進(jìn)行插入和刪除的線性表。允許插入、刪除的這一端稱為棧頂，另一個(gè)固定端稱 為棧底。當(dāng)表中沒有元素時(shí)稱為空棧。/ 在棧構(gòu)造之前和銷毀之后， base 的值為 NULL / 棧頂指針/ 當(dāng)前已分配的存儲(chǔ)空間2.1.2 棧的存儲(chǔ)實(shí)現(xiàn)和運(yùn)算實(shí)現(xiàn) 棧是運(yùn)算受限的線性表，線性表的存儲(chǔ)結(jié)構(gòu)對(duì)棧也是適用的，只是操作不同而已。 利用順序存儲(chǔ)方式實(shí)

30、現(xiàn)的棧稱為順序棧。與線性表類似，棧的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)如下： #define STACK_INIT_SIZE 100 /存/ 儲(chǔ)空間的初始分配量 #define STACKINCREMENT 10 /存/ 儲(chǔ)空間的分配增量 typedef struct SElemType *base; SElemType *top; int stacksize;SqStack;base 始終指向棧底元素，非空棧中的 top 始終在棧頂需要注意，在棧的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)中， 元素的下一個(gè)位置。下面是順序棧上常用的基本操作的實(shí)現(xiàn)。 ( 1)入棧：若棧不滿，則將e 插入棧頂。int Push (SqStack

31、&S, SElemType e) if (S.top-S.base>=S.stacksize)/ 棧滿，追加存儲(chǔ)空間/top 始終在棧頂元素的下一個(gè)位置 *S.top+ = e; return OK;若棧不空，則刪除S的棧頂元素，用 e返回其值，并返回 0K,否則返回ERROR( 2)出棧： int Pop (SqStack &S, SElemType &e) if (S.top=S.base) return ERROR; e = *-S.top;return OK; 出棧和讀棧頂元素操作，先判棧是否為空，為空時(shí)不能操作，否則產(chǎn)生錯(cuò)誤。通常棧空常作為一種控 制轉(zhuǎn)移

32、的條件。2.1.3 棧的應(yīng)用舉例 由于棧的“先進(jìn)先出”特點(diǎn)，在很多實(shí)際問題中都利用棧做一個(gè)輔助的數(shù)據(jù)結(jié)構(gòu)來進(jìn)行求解，下面通 過幾個(gè)例子進(jìn)行說明。1數(shù)制轉(zhuǎn)換十進(jìn)制數(shù) N 和其他 d 進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問題，其解決方法很多，其中一個(gè)簡(jiǎn)單 算法基于下列原理：N = (N div + N mod ddiv 為整除運(yùn)算，mtxl 為求余運(yùn)算)其運(yùn)算過程如心例如：(25(*4), «NN div 8N mod 8134S16S421212502對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的般來說恰好和計(jì)算過程相反。 因此，若將計(jì)算過程中得到的八進(jìn)制數(shù)的各位順序進(jìn)棧,假設(shè)現(xiàn)要

33、編制一個(gè)滿足下列要求的程序：八進(jìn)制數(shù)。由于上述計(jì)算過程是從低位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個(gè)數(shù)位，而打印輸出, 應(yīng)從高位到低位進(jìn)行，當(dāng) N>0時(shí)重復(fù)(1)，( 2)NM 0,則將N % r壓入棧s中，執(zhí)行(2);若N=0，將棧s的內(nèi)容依次出棧，算法結(jié)則按出棧序列打印輸出的即為與輸入對(duì)應(yīng)的八進(jìn)制數(shù)。 算法思想：(1 )若N / r代替N。(2 )用void conversion () InitStack(S); / 構(gòu)造空棧sca nf (”d",N);while (N) Push(S, N % 8);N = N/8;while (!StackE mp ty(S) Pop (S,e

34、); printf ( "%d", e ); 2.表達(dá)式求值表達(dá)式求值是程序設(shè)計(jì)語(yǔ)言編譯中一個(gè)最基本的問題，它的實(shí)現(xiàn)也是需要棧的加入。下面的算法是由 運(yùn)算符優(yōu)先法對(duì)表達(dá)式求值。在此僅限于討論只含二目運(yùn)算符的算術(shù)表達(dá)式。(1)中綴表達(dá)式求值：中綴表達(dá)式：每個(gè)二目運(yùn)算符在兩個(gè)運(yùn)算量的中間，假設(shè)所討論的算術(shù)運(yùn)算符包括：+、-、*、/、八(乘方)和括號(hào)()o設(shè)運(yùn)算規(guī)則為：.運(yùn)算符的優(yōu)先級(jí)為：()> 八>*、 /、 %> +、-;.有括號(hào)出現(xiàn)時(shí)先算括號(hào)內(nèi)的，后算括號(hào)外的，多層括號(hào)，由內(nèi)向外進(jìn)行； .乘方連續(xù)出現(xiàn)時(shí)先算最右面的。表達(dá)式作為一個(gè)滿足表達(dá)式語(yǔ)法規(guī)則的串存儲(chǔ)

35、，如表達(dá)式“3*2人(4+2*2- 1 *3 ) -5”，它的的求值過程為：自左向右掃描表達(dá)式，當(dāng)掃描到3*2時(shí)不能馬上計(jì)算，因?yàn)楹竺婵赡苓€有更高的運(yùn)算，正確的處理過程是：需要兩個(gè)棧：對(duì)象棧 s1和運(yùn)算符棧s2。當(dāng)自左至右掃描表達(dá)式的每一個(gè)字符時(shí)， 若當(dāng)前字符是運(yùn)算對(duì)象，入對(duì)象棧，是運(yùn)算符時(shí)，若這個(gè)運(yùn)算符比棧頂運(yùn)算符高則入棧，繼續(xù)向后處 理，若這個(gè)運(yùn)算符比棧頂運(yùn)算符低則從對(duì)象棧出棧兩個(gè)運(yùn)算量，從運(yùn)算符棧出棧一個(gè)運(yùn)算符進(jìn)行運(yùn)算，并將其運(yùn)算結(jié)果入對(duì)象棧，繼續(xù)處理當(dāng)前字符，直到遇到結(jié)束符。中綴表達(dá)式表達(dá)式“ 3*2人(4+2*2- 1 *3 ) -5”求值過程中兩個(gè)棧的狀態(tài)情況見圖所示。a3i入棧訂

36、43*ARs2232#2入棧siA32A入技s2J2人桟s243 2, 4滬列4入檯si+3 2，4s2亠3.4. 22入際1+3. 2.乩 223 2. 4. 2. 2#n+*2入犠叮3. 2，4. 4242=4.第果入?！?H3. 2. H#叫-入棧s213.Ht 1卜1入棧S43. 2* 亂 1*At£ s233 2. W. 1. 3# r丄$入棧d)32,乩3結(jié)果3入找H3 2, 5做舊*箔址5入棧3. :. 5(出棧3225、結(jié)聖取入檯5196#做護(hù)范.粘果州人棧引沁人核強(qiáng)5臉55入校叮結(jié)駛符 Is圖中綴表達(dá)式 3*2人(4+2*2-1*3)-5的求值過程為了處理方便，編譯

37、程序常把中綴表達(dá)式首先轉(zhuǎn)換成等價(jià)的后綴表達(dá)式，后綴表達(dá)式的運(yùn)算符在 運(yùn)算對(duì)象之后。在后綴表達(dá)式中，不在引入括號(hào)，所有的計(jì)算按運(yùn)算符出現(xiàn)的順序，嚴(yán)格從左向右進(jìn)行，而不用再考慮運(yùn)算規(guī)則和級(jí)別。“32422*+13*-A*5- ”。中綴表達(dá)式“ 3*2人(4+2*2-1*3)-5 ”的后綴表達(dá)式為：這是因?yàn)楸磉_(dá)式中即無括號(hào)又無(2 )后綴表達(dá)式求值 計(jì)算一個(gè)后綴表達(dá)式，算法上比計(jì)算一個(gè)中綴表達(dá)式簡(jiǎn)單的多。優(yōu)先級(jí)的約束。具體做法：只使用一個(gè)對(duì)象棧，當(dāng)從左向右掃描表達(dá)式時(shí)，每遇到一個(gè)操作數(shù)就送入 棧中保存，每遇到一個(gè)運(yùn)算符就從棧中取出兩個(gè)操作數(shù)進(jìn)行當(dāng)前的計(jì)算，然后把結(jié)果再入棧，直到整 個(gè)表達(dá)式結(jié)束，這時(shí)

38、送入棧頂?shù)闹稻褪墙Y(jié)果。(3) 中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式：將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)示和前述對(duì)中綴表達(dá)式求值的方法完全類似，但只需要運(yùn)算符棧，遇到運(yùn)算對(duì)象時(shí)直接放后綴表達(dá)式的存儲(chǔ)區(qū)，假設(shè)中綴表達(dá)式本身合法且在字符數(shù)組A中，轉(zhuǎn)換后的后綴表達(dá)式存儲(chǔ)在字符數(shù)組 B 中。具體做法：遇到運(yùn)算對(duì)象順序向存儲(chǔ)后綴表達(dá)式的 B 數(shù)組中存 放，遇到運(yùn)算符時(shí)類似于中綴表達(dá)式求值時(shí)對(duì)運(yùn)算符的處理過程，但運(yùn)算符出棧后不是進(jìn)行相應(yīng)的運(yùn) 算，而是將其送入 B 中存放。具體算法在此不再贅述。當(dāng)在3棧與遞歸 在高級(jí)語(yǔ)言編制的程序中， 調(diào)用函數(shù)與被調(diào)用函數(shù)之間的鏈接和信息交換必須通過棧進(jìn)行。一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，

39、在運(yùn)行該被調(diào)用函數(shù)之前，需先完成三件事 :（ 1 ）將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存;（ 2 ）為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū) ;（ 3 ）將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。1）保存被調(diào)函數(shù)的計(jì)算結(jié)果 ;2）釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū) ;3）依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。 多個(gè)函數(shù)嵌套調(diào)用的規(guī)則是：后調(diào)用先返回，此時(shí)的內(nèi)存管理實(shí)行“棧式管理” 。從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成 :（ 遞歸函數(shù)的調(diào)用類似于多層函數(shù)的嵌套調(diào)用，只是調(diào)用單位和被調(diào)用單位是同一個(gè)函數(shù)而已。在每次 調(diào)用時(shí)系統(tǒng)將屬于各個(gè)遞歸層次的信息組成一個(gè)活動(dòng)記錄 （ ActivaTion Reco

40、rd ），這個(gè)記錄中包含著本 層調(diào)用的實(shí)參、返回地址、局部變量等信息，并將這個(gè)活動(dòng)記錄保存在系統(tǒng)的“遞歸工作?！敝?，每 當(dāng)遞歸調(diào)用一次，就要在棧頂為過程建立一個(gè)新的活動(dòng)記錄，一旦本次調(diào)用結(jié)束，則將棧頂活動(dòng)記錄 出棧，根據(jù)獲得的返回地址信息返回到本次的調(diào)用處。將遞歸程序轉(zhuǎn)化為非遞歸程序時(shí)常使用棧來實(shí)現(xiàn)。22隊(duì)列2.2.1隊(duì)列的定義及基本運(yùn)算棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，在實(shí)際問題中還經(jīng)常使用一種“先進(jìn)先出”的數(shù)據(jù)結(jié)構(gòu)：即插入 在表一端進(jìn)行，而刪除在表的另一端進(jìn)行，將這種數(shù)據(jù)結(jié)構(gòu)稱為隊(duì)或隊(duì)列，把允許插入的一端叫隊(duì)尾(rear);把允許刪除的一端叫隊(duì)頭(front)。2.2.2隊(duì)列的存儲(chǔ)實(shí)現(xiàn)及運(yùn)算實(shí)現(xiàn)

41、與線性表、棧類似，隊(duì)列也有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)方法。1. 順序隊(duì)列循環(huán)隊(duì)列的類型定義如下：#define MAXQSIZE 100 / 最大隊(duì)列長(zhǎng)度typ edef struct /動(dòng)態(tài)分配存儲(chǔ)空間/頭指針，若隊(duì)列不空，指向隊(duì)列頭元素/尾指針，若隊(duì)列不空，指向隊(duì)列尾元素的下一個(gè)位置QElemT ype *base;int front;int rear; SqQueue;(2)出ini DcQucuc (SqQucuc &Q, QEIcmTypc J if (Q,frpnt = Q rear) rehim ERROR;c - 0 hahc0.ronl;Q.from = (Q.fro

42、rLr+l> % MAXQSIZE; mum OK;下面是循環(huán)隊(duì)列上基本操作的實(shí)現(xiàn)。J入甌irt EriQueuc(SqOucuc &Q,QFJetuTypcc ifiQ.rcan-DMAXQSIZE Q.front) return ERROR;Q.baselQ.rvar = e;Q.rear = | Q r訛l1 J % MAXQSIZE;rtMLirn OK;(3)求循環(huán)隊(duì)列元素個(gè)數(shù)：int QueueLength ( SqQueue Q)return (Q.rear-Q.fro nt+MAXQSIZE) %MAXQSIZE2 .鏈隊(duì)列鏈?zhǔn)酱鎯?chǔ)的隊(duì)稱為鏈隊(duì)列。和鏈棧類似，用單

43、鏈表來實(shí)現(xiàn)鏈隊(duì)列，根據(jù)隊(duì)的先進(jìn)先出原 則，為了操作上的方便，分別需要一個(gè)頭指針和尾指針。鋌隊(duì)列的形式描述如typedef strict QNode / 結(jié)點(diǎn)類型QEkiiiTypc tkiUi：struct QNode *rext"鏈隊(duì)列類型 from； 臥頭指針 rear； "I認(rèn)M指針卜 QNodc, *QucueFtr;typedef struct QuciicPirQueuePtr卜 LinkQueue:定義一個(gè)指向鏈隊(duì)列的指針： LinkQueue Q; 下面是鏈隊(duì)列的基本運(yùn)算的實(shí)現(xiàn)。( 1 )入隊(duì)int EnQueue (LinkQueue &Q, QE

44、lemType e) QNode *p;p = ( QNode * ) malloc ( sizeof( QNode) ; p->data = e; p->next = NULL; Q.rear->next = p;Q.rear = p;return OK;( 2 )出隊(duì)int DeQueue (LinkQueue &Q, QElemType &e) if (Q.front = Q.rear) return ERROR; / 隊(duì)空，出隊(duì)失敗p = Q.front->next;/ 隊(duì)頭元素放 e 中e = p->data;Q.front->ne

45、xt = p->next;/ 只有一個(gè)元素時(shí)，此時(shí)還要修改隊(duì)尾指針if(Q.rear=p) Q.rear= Q.front;free (p);return OK; 3除了棧和隊(duì)列之外，還有一種限定性數(shù)據(jù)結(jié)構(gòu)是雙端隊(duì)列。( 1 )雙端隊(duì)列：可以在雙端進(jìn)行插入和刪除操作的線性表。( 2 )輸入受限的雙端隊(duì)列：線性表的兩端都可以輸出數(shù)據(jù)元素，但是只能在一端輸入數(shù)據(jù)元素。( 3 )輸出受限的雙端隊(duì)列：線性表的兩端都可以輸入數(shù)據(jù)元素，但是只能在一端輸出數(shù)據(jù)元素。2.3 特殊矩陣的壓縮存儲(chǔ)2.3.1 數(shù)組數(shù)組可以看作線性表的推廣。數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)其特點(diǎn)是結(jié)構(gòu)中的元素本身可以是具有某種 結(jié)構(gòu)的數(shù)據(jù)

46、,但屬于同一數(shù)據(jù)類型,數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)有序集,每一個(gè)數(shù)據(jù)元素 有唯一的一組下標(biāo)來標(biāo)識(shí),因此,在數(shù)組上不能做插入、刪除數(shù)據(jù)元素的操作。通常在各種高級(jí)語(yǔ)言 中數(shù)組一旦被定義,每一維的大小及上下界都不能改變?，F(xiàn)在來討論數(shù)組在計(jì)算機(jī)中的存儲(chǔ)表示。通常,數(shù)組在內(nèi)存被映象為向量,即用向量作為數(shù)組的 一種存儲(chǔ)結(jié)構(gòu),這是因?yàn)閮?nèi)存的地址空間是一維的,數(shù)組的行列固定后,通過一個(gè)映象函數(shù),則可根 據(jù)數(shù)組元素的下標(biāo)得到它的存儲(chǔ)地址。對(duì)于一維數(shù)組按下標(biāo)順序分配即可。 對(duì)多維數(shù)組分配時(shí), 要把它的元素映象存儲(chǔ)在一維存儲(chǔ)器中, 一般有兩種存儲(chǔ)方式：一是以行為主序(或先行后列)的順序存放,即一行分配完了接著

47、分配下一行。 另一種是以列為主序(先列后行)的順序存放,即一列一列地分配。以行為主序的分配規(guī)律 是：最右邊的下標(biāo)先變化,即最右下標(biāo)從小到大,循環(huán)一遍后,右邊第二 個(gè)下標(biāo)再變，從右向左，最后是左下標(biāo)。以列為主序分配的規(guī)律恰好相反：最左邊的下標(biāo)先變化，即最左下標(biāo)從小到大，循環(huán)一遍后，左邊第二個(gè)下標(biāo)再變，從左向右，最后是右下標(biāo)。設(shè)有m X n二維數(shù)組 Amn，下面我們看按元素的下標(biāo)求其地址的計(jì)算：以“以行為主序”的分配為例：設(shè)數(shù)組的基址為L(zhǎng)0C(a11),每個(gè)數(shù)組元素占據(jù)d個(gè)地址單元，那么 aij 的物理地址可用一線性尋址函數(shù)計(jì)算：L0C(aij) = L0C(a11) + ( (i-1)*n +

48、j-1 ) * d這是因?yàn)閿?shù)組元素 aij的前面有i-1行，每一行的元素個(gè)數(shù)為n,在第i行中它的前面還有j-1個(gè)數(shù)組元素。在 C 語(yǔ)言中,數(shù)組中每一維的下界定義為 0,則：L0C(aij) = L0C(a00) + ( i*n + j ) * d推廣到一般的二維數(shù)組：Ac1.d1 c2.d2 ,則 aij 的物理地址計(jì)算函數(shù)為：L0C(aij)=L0C(a c1 c2)+( (i- c1) *( d2 - c2 + 1)+ (j- c2) )d2.3.2 特殊矩陣矩陣在這種存儲(chǔ)表示之下, 可以對(duì)1。但是在矩陣中非零元素呈某對(duì)于一個(gè)矩陣結(jié)構(gòu)顯然用一個(gè)二維數(shù)組來表示是非常恰當(dāng)?shù)模?其元素進(jìn)行隨機(jī)存

49、取，各種矩陣運(yùn)算也非常簡(jiǎn)單，并且存儲(chǔ)的密度為 種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，比如常見的一些特殊矩陣，如三角矩陣、對(duì)稱矩 陣、對(duì)角矩陣、稀疏矩陣等，從節(jié)約存儲(chǔ)空間的角度考慮，這種存儲(chǔ)是不太合適的，看起來存儲(chǔ)密度 仍為 1，但實(shí)際上占用了許多單元去存儲(chǔ)重復(fù)的非零元素或零元素， 這對(duì)高階矩陣會(huì)造成極大的浪費(fèi)， 為了節(jié)省存儲(chǔ)空間，我們可以對(duì)這類矩陣進(jìn)行壓縮存儲(chǔ)：即為多個(gè)相同的非零元素只分配一個(gè)存儲(chǔ)空 間；對(duì)零元素不分配空間。1. 對(duì)稱矩陣對(duì)稱矩陣的特點(diǎn)是：在一個(gè) n階方陣中，有 aij=aji ,其中 K i , j < n,對(duì)稱矩陣關(guān)于主對(duì)角線對(duì)稱,因此只需存儲(chǔ)上三角或下三角部

50、分即可，比如，< i< n,對(duì)于上三角中的元素aij，它和對(duì)應(yīng)的問和它對(duì)應(yīng)的下三角元素即可，這樣，原來需要 了，節(jié)約了 n(n-1)/2個(gè)存儲(chǔ)單元。對(duì)下三角部分以行為主序順序存儲(chǔ)到一個(gè)向量中去，在下三角中共有n*(n+1)/2個(gè)元素，因此，不失一般性，設(shè)存儲(chǔ)到向量SA n(n+1)/2 中，存儲(chǔ)順序可用圖示意，這樣，原矩陣下三角中的某一個(gè)元素aij則具體對(duì)應(yīng)一個(gè) sak,下面的問題是要找到k與i、j之間的關(guān)系。我們只存儲(chǔ)下三角中的元素aij，其特點(diǎn)是中j< i且1aji相等，因此當(dāng)訪問的元素在上三角時(shí)，直接去訪 n*n個(gè)存儲(chǔ)單元，現(xiàn)在只需要n(n +1)/2個(gè)存儲(chǔ)單元fl對(duì)于

51、下三角中的元素aij，其特點(diǎn)是：ij且面有i-1行，共有1+2+i-1=i*(i-1)/ 2個(gè)元素，而列順序中，aij是第i*(i-1)/2+j個(gè)元素，因此它在1 < i< n,存儲(chǔ)到SA中后，根據(jù)存儲(chǔ)原則，它前 aij又是它所在的行中的第j個(gè)，所以在上面的排SA中的下標(biāo)k與i、 j的關(guān)系為：ii(n+IV2-aij時(shí)則去訪問和它對(duì)SA中的對(duì)應(yīng)關(guān)系：k=i*(i-1)/2+j-1 ( 0W k<n*(n +1)/2 )若i<j,則aij是上三角中的元素，因?yàn)閍ij=aji ,這樣，訪問上三角中的元素應(yīng)的下三角中的 aji即可，因此將上式中的行列下標(biāo)交換就是上三角中的元素

52、在k=j*(j-1)/ 2+i-1 (0< k<n*(n+1)/2 )綜上所述，對(duì)于對(duì)稱矩陣中的任意元素aij，若令l=max(i,j),J=min(i,j)，則將上面兩個(gè)式子綜合起來得到：k=l*(l-1)/2+J-1。2. 三角矩陣(1) 下三角矩陣與對(duì)稱矩陣類似，不同之處在于存完下三角中的元素之后，緊接著存儲(chǔ)對(duì)角線上方的常量，因?yàn)?是同一個(gè)常數(shù)，所以存一個(gè)即可，這樣一共存儲(chǔ)了n*( n+1)+1個(gè)元素，設(shè)存入向量：aji 迦 L(2)上三角矩陣 對(duì)于上三角矩陣, 方的常量。11*( n+l)/245a站1 a英I和3/ k/第-行第、廳下三肅矩脾的壓堀存儲(chǔ)當(dāng)iMjn(n+l/

53、2笫時(shí)亍存儲(chǔ)思想與下三角類似， 以行為主序順序存儲(chǔ)上三角部分,最后存儲(chǔ)對(duì)角線下3.對(duì)角矩陣對(duì)角矩陣也稱為帶狀矩陣。，在這種三對(duì)角矩陣中，所有非零元素都集中在以主對(duì)角線為中心的對(duì) 角區(qū)域中，即除了主對(duì)角線和它的上下方若干條對(duì)角線的元素外，所有其他元素都為零(或同一個(gè)常數(shù)C)。三對(duì)角矩陣 A也可以采用壓縮存儲(chǔ)，將三對(duì)角矩陣壓縮到向量SA中去，按以行為主序，順序的存儲(chǔ)其非零元素，如圖所示，按其壓縮規(guī)律，找到相應(yīng)的映象函數(shù)?，F(xiàn)與叫|的時(shí)應(yīng)關(guān)條為：67891011W*i+j-3廠眄1ai2000助a推an000gUu000陽(yáng)a«載1?u00awj0少(flj二對(duì)打佝陣0234耳| nlj I a：俱2 J玄忙 ait I a詔 aji 344a產(chǎn)圖時(shí)箱矩存儲(chǔ)Tm， 樹。2相關(guān)術(shù)語(yǔ)第三章 樹與二叉樹3.1 樹的概念1.樹的定義樹（Tree）是n （ n0）個(gè)有限數(shù)據(jù)元素的集合。當(dāng)n= 0時(shí)，稱這棵樹為空樹。在一棵非樹T 中:1）有一個(gè)特殊的數(shù)據(jù)元素稱為樹的根結(jié)點(diǎn)，根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)；2） 若n>1,除根結(jié)點(diǎn)之外的