鄰接多重表怎么理解 鄰接多重表是無向圖和有向圖的鏈式存儲結(jié)構(gòu)嗎

快數(shù)據(jù)結(jié)構(gòu)的重點是什么，各位大哥大姐，有學過數(shù)據(jù)結(jié)構(gòu)的幫個忙吧，感謝萬分？鄰接多重表的優(yōu)缺點，數(shù)據(jù)結(jié)構(gòu)題、大哥大姐幫我做下題吧。萬分感謝??？鄰接多重表是無向圖和有向圖的鏈式存儲結(jié)構(gòu)嗎？

本文導航

• 數(shù)據(jù)結(jié)構(gòu)知識點詳細
• 鄰接多重表的優(yōu)缺點
• 數(shù)據(jù)結(jié)構(gòu)題、大哥大姐幫我做下題吧。萬分感謝啊
• 鄰接多重表是無向圖和有向圖的鏈式存儲結(jié)構(gòu)嗎

數(shù)據(jù)結(jié)構(gòu)知識點詳細

第一章 數(shù)據(jù)結(jié)構(gòu)基本概念

1、基本概念：理解什么是數(shù)據(jù)、數(shù)據(jù)對象、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)、邏輯結(jié)構(gòu)與物理結(jié)構(gòu)間的關(guān)系。

2、面向?qū)ο蟾拍睿豪斫馐裁词菙?shù)據(jù)類型、抽象數(shù)據(jù)類型、數(shù)據(jù)抽象和信息隱蔽原則。了解什么是面向?qū)ο?。由于目前關(guān)于這個問題有許多說法，我們采用了一種最流行的說法，即Coad與Yourdon 給出的定義：面向?qū)ο?= 對象 + 類 + 繼承 + 通信。

要點：

·抽象數(shù)據(jù)類型的封裝性

·面向?qū)ο笙到y(tǒng)結(jié)構(gòu)的穩(wěn)定性

·面向?qū)ο蠓椒ㄖ埸c在于應(yīng)用問題所涉及的對象

3、數(shù)據(jù)結(jié)構(gòu)的抽象層次：理解用對象類表示的各種數(shù)據(jù)結(jié)構(gòu)

4、算法與算法分析：理解算法的定義、算法的特性、算法的時間代價、算法的空間代價。

要點：·算法與程序的不同之處需要從算法的特性來解釋

·算法的正確性是最主要的要求

·算法的可讀性是必須考慮的

·程序的程序步數(shù)的計算與算法的事前估計

·程序的時間代價是指算法的漸進時間復雜性度量

第二章 數(shù)組

1、作為抽象數(shù)據(jù)類型的數(shù)組：數(shù)組的定義、數(shù)組的按行順序存儲與按列順序存儲

要點：

·數(shù)組元素的存放地址計算

2、順序表：順序表的定義、搜索、插入與刪除

要點：

·順序表搜索算法、平均比較次數(shù)的計算

·插入與刪除算法、平均移動次數(shù)的計算

3、多項式：多項式的定義

4、字符串：字符串的定義及其操作的實現(xiàn)

要點：

·串重載操作的定義與實現(xiàn)

第三章 鏈接表

1、單鏈表：單鏈表定義、相應(yīng)操作的實現(xiàn)、單鏈表的游標類。

要點：

·單鏈表的兩種定義方式（復合方式與嵌套方式）

·單鏈表的搜索算法與插入、刪除算法

·單鏈表的遞歸與迭代算法

2、循環(huán)鏈表：單鏈表與循環(huán)鏈表的異同

3、雙向鏈表：雙向鏈表的搜索、插入與刪除算法、鏈表帶表頭結(jié)點的優(yōu)點

4、多項式的鏈接表示

第四章 棧與隊列

1、棧：棧的特性、棧的基本運算

要點：

·棧的數(shù)組實現(xiàn)、棧的鏈表實現(xiàn)

·棧滿及?？諚l件、抽象數(shù)據(jù)類型中的先決條件與后置條件

2、棧的應(yīng)用：用后綴表示計算表達式，中綴表示改后綴表示

3、隊列：隊列的特性、隊列的基本運算

要點：

·隊列的數(shù)組實現(xiàn)：循環(huán)隊列中隊頭與隊尾指針的表示，隊滿及隊空條件

·隊列的鏈表實現(xiàn)：鏈式隊列中的隊頭與隊尾指針的表示、

4、雙向隊列：雙向隊列的插入與刪除算法

5、優(yōu)先級隊列：優(yōu)先級隊列的插入與刪除算法

第五章 遞歸與廣義表

1、遞歸：遞歸的定義、遞歸的數(shù)據(jù)結(jié)構(gòu)、遞歸問題用遞歸過程求解

要點：·鏈表是遞歸的數(shù)據(jù)結(jié)構(gòu)，可用遞歸過程求解有關(guān)鏈表的問題

2、遞歸實現(xiàn)時棧的應(yīng)用

要點：·遞歸的分層（樹形）表示：遞歸樹

·遞歸深度（遞歸樹的深度）與遞歸工作棧的關(guān)系

·單向遞歸與尾遞歸的迭代實現(xiàn)

3、廣義表：廣義表定義、廣義表長度、廣義表深度、廣義表表頭、廣義表表尾

要點：

·用圖形表示廣義表的存儲結(jié)構(gòu)

·廣義表的遞歸算法

第六章 樹與森林

1、樹：樹的定義、樹的基本運算

要點：

·樹的分層定義是遞歸的

·樹中結(jié)點個數(shù)與高度的關(guān)系

2、二叉樹：二叉樹定義、二叉樹的基本運算

要點：

·二叉樹性質(zhì)、二叉樹中結(jié)點個數(shù)與高度的關(guān)系、不同種類的二叉樹棵數(shù)

·完全二叉樹的順序存儲、完全二叉樹的雙親、子女和兄弟的位置

·二叉樹的前序·中序·后序·層次遍歷

·前序

·中序

·后序的線索化二叉樹、前驅(qū)與后繼的查找方法

3、霍夫曼樹：霍夫曼樹的構(gòu)造方法、霍夫曼編碼、帶權(quán)路徑長度的計算

4、樹的存儲：樹的廣義表表示、樹的雙親表示、樹與二叉樹的對應(yīng)關(guān)系、樹的先根·中根·后根·層次遍歷。

5、堆：堆的定義、堆的插入與刪除算法

要點：

·形成堆時用到的向下調(diào)整算法及形成堆時比較次數(shù)的上界估計

·堆插入時用到的向上調(diào)整算法

第七章 集合與搜索

1、集合的概念：集合的基本運算、集合的存儲表示

要點：

·用位數(shù)組表示集合時集合基本運算的實現(xiàn)

·用有序鏈表表示集合時集合基本運算的實現(xiàn)

2、并查集：并查集定義、并查集的三種基本運算的實現(xiàn)

3、基本搜索方法

要點：

·對一般表的順序搜索算法（包括有監(jiān)視哨和沒有監(jiān)視哨）

·對有序順序表的順序搜索算法、用判定樹（即擴充二叉搜索樹）描述搜索，以及平均搜索長度（成功與不成功）的計算。

·對有序順序表的折半搜索算法、用判定樹（即擴充二叉搜索樹）描述搜索，以及平均搜索長度（成功與不成功）的計算。

4、二叉搜索樹：

要點：

·動態(tài)搜索樹與靜態(tài)搜索樹的特性

·二叉搜索樹的定義、二叉搜索樹上的搜索算法、二叉搜索樹搜索時的平均搜索長度（成功與不成功）的計算。

·AVL樹結(jié)點上的平衡因子、AVL樹的平衡旋轉(zhuǎn)方法

·高度為h的AVL樹上的最少結(jié)點個數(shù)與最多結(jié)點個數(shù)

· AVL樹的搜索方法、插入與刪除方法

第八章 圖

1、圖：圖的定義與圖的存儲表示

要點：

·鄰接矩陣表示（通常是稀疏矩陣）

·鄰接表與逆鄰接表表示

·鄰接多重表(十字鏈表)表示

2、深度優(yōu)先遍歷與廣度優(yōu)先遍歷

要點：

·生成樹與生成樹林的定義

·深度優(yōu)先搜索是個遞歸的過程，而廣度優(yōu)先搜索是個非遞歸的過程

·為防止重復訪問已經(jīng)訪問過的頂點，需要設(shè)置一個訪問標志數(shù)組visited

3、圖的連通性

要點：

·深度優(yōu)先搜索可以遍歷一個連通分量上的所有頂點

·對非連通圖進行遍歷，可以建立一個生成森林

·對強連通圖進行遍歷，可能建立一個生成森林

·關(guān)節(jié)點的計算和以最少的邊構(gòu)成重連通圖

4、最小生成樹

要點：

·對于連通網(wǎng)絡(luò)、可用不會構(gòu)成環(huán)路的權(quán)值最小的n-1條邊構(gòu)成最小生成樹

·會畫出用Kruskal算法及Prim算法構(gòu)造最小生成樹的過程

5、單源最短路徑

要點：

·采用逐步求解的方式求某一頂點到其他頂點的最短路徑

·要求每條邊的權(quán)值必須大于零

6、活動網(wǎng)絡(luò)

要點：

·拓撲排序、關(guān)鍵路徑、關(guān)鍵活動、AOE網(wǎng)

·拓撲排序?qū)⒁粋€偏序圖轉(zhuǎn)化為一個全序圖。

·為實現(xiàn)拓撲排序，要建立一個棧，將所有入度為零的頂點進棧

·關(guān)鍵路徑的計算

第九章 排序

1、基本概念：關(guān)鍵碼、初始關(guān)鍵碼排列、關(guān)鍵碼比較次數(shù)、數(shù)據(jù)移動次數(shù)、穩(wěn)定性、附加存儲、內(nèi)部排序、外部排序

2、插入排序：

要點：

·當待排序的關(guān)鍵碼序列已經(jīng)基本有序時，用直接插入排序最快

3、選擇排序：

要點：

·用直接選擇排序在一個待排序區(qū)間中選出最小的數(shù)據(jù)時，與區(qū)間第一個數(shù)據(jù)對調(diào)，而不是順次后移。這導致方法不穩(wěn)定。

·當在n個數(shù)據(jù)（n很大）中選出最小的5 ~ 8個數(shù)據(jù)時，錦標賽排序最快

·錦標賽排序的算法中將待排序的數(shù)據(jù)個數(shù)n補足到2的k次冪2k-1<n≤2k

·在堆排序中將待排序的數(shù)據(jù)組織成完全二叉樹的順序存儲。

4、交換排序：

要點：

·快速排序是一個遞歸的排序方法

·當待排序關(guān)鍵碼序列已經(jīng)基本有序時，快速排序顯著變慢。

5、二路歸并排序：

要點：

·歸并排序可以遞歸執(zhí)行

·歸并排序需要較多的附加存儲?？梢圆捎靡环N"推拉法"（參見教科書上習題）實現(xiàn)歸并排序，算法的時間復雜度為O (n)、空間復雜度為O(1)

·歸并排序?qū)Υ判蜿P(guān)鍵碼的初始排列不敏感，排序速度較穩(wěn)定

6、外排序

要點：

·多路平衡歸并排序的過程、I/O緩沖區(qū)個數(shù)的配置

·外排序的時間分析、利用敗者樹進行多路平衡歸并

·利用置換選擇方法生成不等長的初始歸并段

·最佳歸并樹的構(gòu)造及WPL的計算

第十章 索引與散列

1、線性索引：

要點：

·密集索引、稀疏索引、索引表計算

·基于屬性查找建立倒排索引、單元式倒排表

2、動態(tài)搜索樹

要點：

·平衡的m路搜索樹的定義、搜索算法

·B樹的定義、B樹與平衡的m路搜索樹的關(guān)系

·B樹的插入（包括結(jié)點分裂）、刪除（包括結(jié)點調(diào)整與合并）方法

·B樹中結(jié)點個數(shù)與高度的關(guān)系

·B+樹的定義、搜索、插入與刪除的方法

3、散列表

要點：

·散列函數(shù)的比較

·裝填因子 a 與平均搜索長度的關(guān)系，平均搜索長度與表長m及表中已有數(shù)據(jù)對象個數(shù)n的關(guān)系

·解決地址沖突的（閉散列）線性探查法的運用，平均探查次數(shù)的計算

·線性探查法的刪除問題、散列表類的設(shè)計中必須為各地址設(shè)置三個狀態(tài)

·線性探查法中的聚集問題

·解決地址沖突的（閉散列）雙散列法的運用，平均探查次數(shù)的計算

·雙散列法中再散列函數(shù)的設(shè)計要求與表長m互質(zhì)，為此m設(shè)計為質(zhì)數(shù)較宜

·解決地址沖突的（閉散列）二次散列法的運用，平均探查次數(shù)的計算

·注意：二次散列法中裝填因子 a 與表長m的設(shè)置

·解決地址沖突的（開散列）鏈地址法的運用，平均探查次數(shù)的計算

鄰接多重表的優(yōu)缺點

#include <stdio.h>

#include <stdlib.h>

typedef int MYTYPE;

void Merge(MYTYPE x[], MYTYPE tmp[], int lpos, int rpos, int rightend){

int leftend= rpos - 1,

numelements = rightend - lpos + 1,

tmppos= lpos,i;

while ((lpos <= leftend) && (rpos <= rightend))

tmp[tmppos++] = x[lpos] <= x[rpos] ? x[lpos++] : x[rpos++];

while (lpos <= leftend) tmp[tmppos++] = x[lpos++];

while (rpos <= rightend)tmp[tmppos++] = x[rpos++];

for (i = 0; i < numelements; ++i, --rightend) x[rightend] = tmp[rightend];

}

void MSort(MYTYPE x[], MYTYPE tmp[], int left, int right){

if (left >= right) return;

int center = (left + right) / 2;

MSort(x, tmp, left, center);

MSort(x, tmp, center + 1, right);

Merge(x, tmp, left, center + 1, right);

}

void MergeSort(MYTYPE x[], int n){

MYTYPE *tmp = (MYTYPE*)malloc(n*sizeof(MYTYPE));

MSort(x, tmp, 0, n - 1);

free(tmp);

}

void main() {

int ar[10],i;

for(i=0;i<10;++i){

printf("輸入第%d個數(shù):",i+1);

scanf("%d",&ar[i]);

}

for(i=0;i<10;++i) printf("%d,",ar[i]);

MergeSort(ar,10);

printf("\n排序后:\n");

for(i=0;i<10;++i) printf("%d,",ar[i]);

printf("\n");

}算法轉(zhuǎn)自<數(shù)據(jù)結(jié)構(gòu)與算法分析學習筆記>,代碼也可以編譯,我測試了下

你看下有沒幫助吧

為什么 孤傲※王子 這種貼海報刷分的人有存在這個世界的必要呢?我真是不理解上帝的用意,是來告知人世的悲哀,還是想為一個常人作點襯托呢?

數(shù)據(jù)結(jié)構(gòu)題、大哥大姐幫我做下題吧。萬分感謝啊

什么是數(shù)據(jù)、數(shù)據(jù)對象、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)、邏輯結(jié)構(gòu)與物理結(jié)構(gòu)間的關(guān)系。

2、面向?qū)ο蟾拍睿豪斫馐裁词菙?shù)據(jù)類型、抽象數(shù)據(jù)類型、數(shù)據(jù)抽象和信息隱蔽原則。了解什么是面向?qū)ο?。由于目前關(guān)于這個問題有許多說法，我們采用了一種最流行的說法，即Coad與Yourdon 給出的定義：面向?qū)ο?= 對象 + 類 + 繼承 + 通信。

要點：

·抽象數(shù)據(jù)類型的封裝性

·面向?qū)ο笙到y(tǒng)結(jié)構(gòu)的穩(wěn)定性

·面向?qū)ο蠓椒ㄖ埸c在于應(yīng)用問題所涉及的對象

3、數(shù)據(jù)結(jié)構(gòu)的抽象層次：理解用對象類表示的各種數(shù)據(jù)結(jié)構(gòu)

4、算法與算法分析：理解算法的定義、算法的特性、算法的時間代價、算法的空間代價。

要點：·算法與程序的不同之處需要從算法的特性來解釋

·算法的正確性是最主要的要求

·算法的可讀性是必須考慮的

·程序的程序步數(shù)的計算與算法的事前估計

·程序的時間代價是指算法的漸進時間復雜性度量

第二章 數(shù)組

1、作為抽象數(shù)據(jù)類型的數(shù)組：數(shù)組的定義、數(shù)組的按行順序存儲與按列順序存儲

要點：

·數(shù)組元素的存放地址計算

2、順序表：順序表的定義、搜索、插入與刪除

要點：

·順序表搜索算法、平均比較次數(shù)的計算

·插入與刪除算法、平均移動次數(shù)的計算

3、多項式：多項式的定義

4、字符串：字符串的定義及其操作的實現(xiàn)

要點：

·串重載操作的定義與實現(xiàn)

第三章 鏈接表

1、單鏈表：單鏈表定義、相應(yīng)操作的實現(xiàn)、單鏈表的游標類。

要點：

·單鏈表的兩種定義方式（復合方式與嵌套方式）

·單鏈表的搜索算法與插入、刪除算法

·單鏈表的遞歸與迭代算法

2、循環(huán)鏈表：單鏈表與循環(huán)鏈表的異同

3、雙向鏈表：雙向鏈表的搜索、插入與刪除算法、鏈表帶表頭結(jié)點的優(yōu)點

4、多項式的鏈接表示

第四章 棧與隊列

1、棧：棧的特性、棧的基本運算

要點：

·棧的數(shù)組實現(xiàn)、棧的鏈表實現(xiàn)

·棧滿及?？諚l件、抽象數(shù)據(jù)類型中的先決條件與后置條件

2、棧的應(yīng)用：用后綴表示計算表達式，中綴表示改后綴表示

3、隊列：隊列的特性、隊列的基本運算

要點：

·隊列的數(shù)組實現(xiàn)：循環(huán)隊列中隊頭與隊尾指針的表示，隊滿及隊空條件

·隊列的鏈表實現(xiàn)：鏈式隊列中的隊頭與隊尾指針的表示、

4、雙向隊列：雙向隊列的插入與刪除算法

5、優(yōu)先級隊列：優(yōu)先級隊列的插入與刪除算法

第五章 遞歸與廣義表

1、遞歸：遞歸的定義、遞歸的數(shù)據(jù)結(jié)構(gòu)、遞歸問題用遞歸過程求解

要點：·鏈表是遞歸的數(shù)據(jù)結(jié)構(gòu)，可用遞歸過程求解有關(guān)鏈表的問題

2、遞歸實現(xiàn)時棧的應(yīng)用

要點：·遞歸的分層（樹形）表示：遞歸樹

·遞歸深度（遞歸樹的深度）與遞歸工作棧的關(guān)系

·單向遞歸與尾遞歸的迭代實現(xiàn)

3、廣義表：廣義表定義、廣義表長度、廣義表深度、廣義表表頭、廣義表表尾

要點：

·用圖形表示廣義表的存儲結(jié)構(gòu)

·廣義表的遞歸算法

第六章 樹與森林

1、樹：樹的定義、樹的基本運算

要點：

·樹的分層定義是遞歸的

·樹中結(jié)點個數(shù)與高度的關(guān)系

2、二叉樹：二叉樹定義、二叉樹的基本運算

要點：

·二叉樹性質(zhì)、二叉樹中結(jié)點個數(shù)與高度的關(guān)系、不同種類的二叉樹棵數(shù)

·完全二叉樹的順序存儲、完全二叉樹的雙親、子女和兄弟的位置

·二叉樹的前序·中序·后序·層次遍歷

·前序

·中序

·后序的線索化二叉樹、前驅(qū)與后繼的查找方法

3、霍夫曼樹：霍夫曼樹的構(gòu)造方法、霍夫曼編碼、帶權(quán)路徑長度的計算

4、樹的存儲：樹的廣義表表示、樹的雙親表示、樹與二叉樹的對應(yīng)關(guān)系、樹的先根·中根·后根·層次遍歷。

5、堆：堆的定義、堆的插入與刪除算法

要點：

·形成堆時用到的向下調(diào)整算法及形成堆時比較次數(shù)的上界估計

·堆插入時用到的向上調(diào)整算法

第七章 集合與搜索

1、集合的概念：集合的基本運算、集合的存儲表示

要點：

·用位數(shù)組表示集合時集合基本運算的實現(xiàn)

·用有序鏈表表示集合時集合基本運算的實現(xiàn)

2、并查集：并查集定義、并查集的三種基本運算的實現(xiàn)

3、基本搜索方法

要點：

·對一般表的順序搜索算法（包括有監(jiān)視哨和沒有監(jiān)視哨）

·對有序順序表的順序搜索算法、用判定樹（即擴充二叉搜索樹）描述搜索，以及平均搜索長度（成功與不成功）的計算。

·對有序順序表的折半搜索算法、用判定樹（即擴充二叉搜索樹）描述搜索，以及平均搜索長度（成功與不成功）的計算。

4、二叉搜索樹：

要點：

·動態(tài)搜索樹與靜態(tài)搜索樹的特性

·二叉搜索樹的定義、二叉搜索樹上的搜索算法、二叉搜索樹搜索時的平均搜索長度（成功與不成功）的計算。

·AVL樹結(jié)點上的平衡因子、AVL樹的平衡旋轉(zhuǎn)方法

·高度為h的AVL樹上的最少結(jié)點個數(shù)與最多結(jié)點個數(shù)

· AVL樹的搜索方法、插入與刪除方法

第八章 圖

1、圖：圖的定義與圖的存儲表示

要點：

·鄰接矩陣表示（通常是稀疏矩陣）

·鄰接表與逆鄰接表表示

·鄰接多重表(十字鏈表)表示

2、深度優(yōu)先遍歷與廣度優(yōu)先遍歷

要點：

·生成樹與生成樹林的定義

·深度優(yōu)先搜索是個遞歸的過程，而廣度優(yōu)先搜索是個非遞歸的過程

·為防止重復訪問已經(jīng)訪問過的頂點，需要設(shè)置一個訪問標志數(shù)組visited

3、圖的連通性

要點：

·深度優(yōu)先搜索可以遍歷一個連通分量上的所有頂點

·對非連通圖進行遍歷，可以建立一個生成森林

·對強連通圖進行遍歷，可能建立一個生成森林

·關(guān)節(jié)點的計算和以最少的邊構(gòu)成重連通圖

4、最小生成樹

要點：

·對于連通網(wǎng)絡(luò)、可用不會構(gòu)成環(huán)路的權(quán)值最小的n-1條邊構(gòu)成最小生成樹

·會畫出用Kruskal算法及Prim算法構(gòu)造最小生成樹的過程

5、單源最短路徑

要點：

·采用逐步求解的方式求某一頂點到其他頂點的最短路徑

·要求每條邊的權(quán)值必須大于零

6、活動網(wǎng)絡(luò)

要點：

·拓撲排序、關(guān)鍵路徑、關(guān)鍵活動、AOE網(wǎng)

·拓撲排序?qū)⒁粋€偏序圖轉(zhuǎn)化為一個全序圖。

·為實現(xiàn)拓撲排序，要建立一個棧，將所有入度為零的頂點進棧

·關(guān)鍵路徑的計算

第九章 排序

1、基本概念：關(guān)鍵碼、初始關(guān)鍵碼排列、關(guān)鍵碼比較次數(shù)、數(shù)據(jù)移動次數(shù)、穩(wěn)定性、附加存儲、內(nèi)部排序、外部排序

2、插入排序：

要點：

·當待排序的關(guān)鍵碼序列已經(jīng)基本有序時，用直接插入排序最快

3、選擇排序：

要點：

·用直接選擇排序在一個待排序區(qū)間中選出最小的數(shù)據(jù)時，與區(qū)間第一個數(shù)據(jù)對調(diào)，而不是順次后移。這導致方法不穩(wěn)定。

·當在n個數(shù)據(jù)（n很大）中選出最小的5 ~ 8個數(shù)據(jù)時，錦標賽排序最快

·錦標賽排序的算法中將待排序的數(shù)據(jù)個數(shù)n補足到2的k次冪2k-1<n≤2k

·在堆排序中將待排序的數(shù)據(jù)組織成完全二叉樹的順序存儲。

4、交換排序：

要點：

·快速排序是一個遞歸的排序方法

·當待排序關(guān)鍵碼序列已經(jīng)基本有序時，快速排序顯著變慢。

5、二路歸并排序：

要點：

·歸并排序可以遞歸執(zhí)行

·歸并排序需要較多的附加存儲?？梢圆捎靡环N"推拉法"（參見教科書上習題）實現(xiàn)歸并排序，算法的時間復雜度為O (n)、空間復雜度為O(1)

·歸并排序?qū)Υ判蜿P(guān)鍵碼的初始排列不敏感，排序速度較穩(wěn)定

6、外排序

要點：

·多路平衡歸并排序的過程、I/O緩沖區(qū)個數(shù)的配置

·外排序的時間分析、利用敗者樹進行多路平衡歸并

·利用置換選擇方法生成不等長的初始歸并段

·最佳歸并樹的構(gòu)造及WPL的計算

第十章 索引與散列

1、線性索引：

要點：

·密集索引、稀疏索引、索引表計算

·基于屬性查找建立倒排索引、單元式倒排表

2、動態(tài)搜索樹

要點：

·平衡的m路搜索樹的定義、搜索算法

·B樹的定義、B樹與平衡的m路搜索樹的關(guān)系

·B樹的插入（包括結(jié)點分裂）、刪除（包括結(jié)點調(diào)整與合并）方法

·B樹中結(jié)點個數(shù)與高度的關(guān)系

·B+樹的定義、搜索、插入與刪除的方法

3、散列表

要點：

·散列函數(shù)的比較

·裝填因子 a 與平均搜索長度的關(guān)系，平均搜索長度與表長m及表中已有數(shù)據(jù)對象個數(shù)n的關(guān)系

·解決地址沖突的（閉散列）線性探查法的運用，平均探查次數(shù)的計算

·線性探查法的刪除問題、散列表類的設(shè)計中必須為各地址設(shè)置三個狀態(tài)

·線性探查法中的聚集問題

·解決地址沖突的（閉散列）雙散列法的運用，平均探查次數(shù)的計算

·雙散列法中再散列函數(shù)的設(shè)計要求與表長m互質(zhì)，為此m設(shè)計為質(zhì)數(shù)較宜

·解決地址沖突的（閉散列）二次散列法的運用，平均探查次數(shù)的計算

·注意：二次散列法中裝填因子 a 與表長m的設(shè)置

·解決地址沖突的（開散列）鏈地址法的運用，平均探查次數(shù)的計算

鄰接多重表是無向圖和有向圖的鏈式存儲結(jié)構(gòu)嗎

無向圖的任何2個不同的節(jié)點都可以有一條鄰接邊。

結(jié)點個數(shù)為m，圖中的邊數(shù)為從m中取2的組合數(shù)，

為 m(m-1)/2.