堆刪除演算法
㈠ dijkstra演算法是什麼
迪傑斯特拉演算法用來解決從頂點v0出發到其餘頂點的最短路徑，該演算法按照最短路徑長度遞增的順序產生所以最短路徑。
對於圖G=（V，E），將圖中的頂點分成兩組：第一組S：已求出的最短路徑的終點集合（開始為｛v0}）。第二組V-S：尚未求出最短路徑的終點集合（開始為V-{v0}的全部結點）。
堆優化
思考
該演算法復雜度為n^2,我們可以發現，如果邊數遠小於n^2,對此可以考慮用堆這種數據結構進行優化，取出最短路徑的復雜度降為O(1)；每次調整的復雜度降為O（elogn）；e為該點的邊數，所以復雜度降為O((m+n)logn)。
實現
1、將源點加入堆，並調整堆。
2、選出堆頂元素u（即代價最小的元素），從堆中刪除，並對堆進行調整。
3、處理與u相鄰的，未被訪問過的，滿足三角不等式的頂點
1):若該點在堆里，更新距離，並調整該元素在堆中的位置。
2):若該點不在堆里，加入堆，更新堆。
4、若取到的u為終點，結束演算法；否則重復步驟2、3。
㈡ 數據結構考試重點
第一章 數據結構基本概念
1、基本概念：理解什麼是數據、數據對象、數據元素、數據結構、數據的邏輯結構與物理結構、邏輯結構與物理結構間的關系。
2、面向對象概念：理解什麼是數據類型、抽象數據類型、數據抽象和信息隱蔽原則。了解什麼是面向對象。由於目前關於這個問題有許多說法，我們採用了一種最流行的說法，即Coad與Yourdon 給出的定義：面向對象 = 對象 + 類 + 繼承 + 通信。
要點：
·抽象數據類型的封裝性
·面向對象系統結構的穩定性
·面向對象方法著眼點在於應用問題所涉及的對象
3、數據結構的抽象層次：理解用對象類表示的各種數據結構
4、演算法與演算法分析：理解演算法的定義、演算法的特性、演算法的時間代價、演算法的空間代價。
要點：·演算法與程序的不同之處需要從演算法的特性來解釋
·演算法的正確性是最主要的要求
·演算法的可讀性是必須考慮的
·程序的程序步數的計算與演算法的事前估計
·程序的時間代價是指演算法的漸進時間復雜性度量
第二章 數組
1、作為抽象數據類型的數組：數組的定義、數組的按行順序存儲與按列順序存儲
要點：
·數組元素的存放地址計算
2、順序表：順序表的定義、搜索、插入與刪除
要點：
·順序表搜索演算法、平均比較次數的計算
·插入與刪除演算法、平均移動次數的計算
3、多項式：多項式的定義
4、字元串：字元串的定義及其操作的實現
要點：
·串重載操作的定義與實現
第三章 鏈接表
1、單鏈表：單鏈表定義、相應操作的實現、單鏈表的游標類。
要點：
·單鏈表的兩種定義方式（復合方式與嵌套方式）
·單鏈表的搜索演算法與插入、刪除演算法
·單鏈表的遞歸與迭代演算法
2、循環鏈表：單鏈表與循環鏈表的異同
3、雙向鏈表：雙向鏈表的搜索、插入與刪除演算法、鏈表帶表頭結點的優點
4、多項式的鏈接表示
第四章 棧與隊列
1、棧：棧的特性、棧的基本運算
要點：
·棧的數組實現、棧的鏈表實現
·棧滿及棧空條件、抽象數據類型中的先決條件與後置條件
2、棧的應用：用後綴表示計算表達式，中綴表示改後綴表示
3、隊列：隊列的特性、隊列的基本運算
要點：
·隊列的數組實現：循環隊列中隊頭與隊尾指針的表示，隊滿及隊空條件
·隊列的鏈表實現：鏈式隊列中的隊頭與隊尾指針的表示、
4、雙向隊列：雙向隊列的插入與刪除演算法
5、優先順序隊列：優先順序隊列的插入與刪除演算法
第五章 遞歸與廣義表
1、遞歸：遞歸的定義、遞歸的數據結構、遞歸問題用遞歸過程求解
要點：·鏈表是遞歸的數據結構，可用遞歸過程求解有關鏈表的問題
2、遞歸實現時棧的應用
要點：·遞歸的分層（樹形）表示：遞歸樹
·遞歸深度（遞歸樹的深度）與遞歸工作棧的關系
·單向遞歸與尾遞歸的迭代實現
3、廣義表：廣義表定義、廣義表長度、廣義表深度、廣義表表頭、廣義表表尾
要點：
·用圖形表示廣義表的存儲結構
·廣義表的遞歸演算法
第六章 樹與森林
1、樹：樹的定義、樹的基本運算
要點：
·樹的分層定義是遞歸的
·樹中結點個數與高度的關系
2、二叉樹：二叉樹定義、二叉樹的基本運算
要點：
·二叉樹性質、二叉樹中結點個數與高度的關系、不同種類的二叉樹棵數
·完全二叉樹的順序存儲、完全二叉樹的雙親、子女和兄弟的位置
·二叉樹的前序·中序·後序·層次遍歷
·前序
·中序
·後序的線索化二叉樹、前驅與後繼的查找方法
3、霍夫曼樹：霍夫曼樹的構造方法、霍夫曼編碼、帶權路徑長度的計算
4、樹的存儲：樹的廣義表表示、樹的雙親表示、樹與二叉樹的對應關系、樹的先根·中根·後根·層次遍歷。
5、堆：堆的定義、堆的插入與刪除演算法
要點：
·形成堆時用到的向下調整演算法及形成堆時比較次數的上界估計
·堆插入時用到的向上調整演算法
第七章 集合與搜索
1、集合的概念：集合的基本運算、集合的存儲表示
要點：
·用位數組表示集合時集合基本運算的實現
·用有序鏈表表示集合時集合基本運算的實現
2、並查集：並查集定義、並查集的三種基本運算的實現
3、基本搜索方法
要點：
·對一般表的順序搜索演算法（包括有監視哨和沒有監視哨）
·對有序順序表的順序搜索演算法、用判定樹（即擴充二叉搜索樹）描述搜索，以及平均搜索長度（成功與不成功）的計算。
·對有序順序表的折半搜索演算法、用判定樹（即擴充二叉搜索樹）描述搜索，以及平均搜索長度（成功與不成功）的計算。
4、二叉搜索樹：
要點：
·動態搜索樹與靜態搜索樹的特性
·二叉搜索樹的定義、二叉搜索樹上的搜索演算法、二叉搜索樹搜索時的平均搜索長度（成功與不成功）的計算。
·AVL樹結點上的平衡因子、AVL樹的平衡旋轉方法
·高度為h的AVL樹上的最少結點個數與最多結點個數
· AVL樹的搜索方法、插入與刪除方法
第八章 圖
1、圖：圖的定義與圖的存儲表示
要點：
·鄰接矩陣表示（通常是稀疏矩陣）
·鄰接表與逆鄰接表表示
·鄰接多重表(十字鏈表)表示
2、深度優先遍歷與廣度優先遍歷
要點：
·生成樹與生成樹林的定義
·深度優先搜索是個遞歸的過程，而廣度優先搜索是個非遞歸的過程
·為防止重復訪問已經訪問過的頂點，需要設置一個訪問標志數組visited
3、圖的連通性
要點：
·深度優先搜索可以遍歷一個連通分量上的所有頂點
·對非連通圖進行遍歷，可以建立一個生成森林
·對強連通圖進行遍歷，可能建立一個生成森林
·關節點的計算和以最少的邊構成重連通圖
4、最小生成樹
要點：
·對於連通網路、可用不會構成環路的權值最小的n-1條邊構成最小生成樹
·會畫出用Kruskal演算法及Prim演算法構造最小生成樹的過程
5、單源最短路徑
要點：
·採用逐步求解的方式求某一頂點到其他頂點的最短路徑
·要求每條邊的權值必須大於零
6、活動網路
要點：
·拓撲排序、關鍵路徑、關鍵活動、AOE網
·拓撲排序將一個偏序圖轉化為一個全序圖。
·為實現拓撲排序，要建立一個棧，將所有入度為零的頂點進棧
·關鍵路徑的計算
第九章 排序
1、基本概念：關鍵碼、初始關鍵碼排列、關鍵碼比較次數、數據移動次數、穩定性、附加存儲、內部排序、外部排序
2、插入排序：
要點：
·當待排序的關鍵碼序列已經基本有序時，用直接插入排序最快
3、選擇排序：
要點：
·用直接選擇排序在一個待排序區間中選出最小的數據時，與區間第一個數據對調，而不是順次後移。這導致方法不穩定。
·當在n個數據（n很大）中選出最小的5 ~ 8個數據時，錦標賽排序最快
·錦標賽排序的演算法中將待排序的數據個數n補足到2的k次冪2k-1<n≤2k
·在堆排序中將待排序的數據組織成完全二叉樹的順序存儲。
4、交換排序：
要點：
·快速排序是一個遞歸的排序方法
·當待排序關鍵碼序列已經基本有序時，快速排序顯著變慢。
5、二路歸並排序：
要點：
·歸並排序可以遞歸執行
·歸並排序需要較多的附加存儲。可以採用一種"推拉法"（參見教科書上習題）實現歸並排序，演算法的時間復雜度為O (n)、空間復雜度為O(1)
·歸並排序對待排序關鍵碼的初始排列不敏感，排序速度較穩定
6、外排序
要點：
·多路平衡歸並排序的過程、I/O緩沖區個數的配置
·外排序的時間分析、利用敗者樹進行多路平衡歸並
·利用置換選擇方法生成不等長的初始歸並段
·最佳歸並樹的構造及WPL的計算
第十章 索引與散列
1、線性索引：
要點：
·密集索引、稀疏索引、索引表計算
·基於屬性查找建立倒排索引、單元式倒排表
2、動態搜索樹
要點：
·平衡的m路搜索樹的定義、搜索演算法
·B樹的定義、B樹與平衡的m路搜索樹的關系
·B樹的插入（包括結點分裂）、刪除（包括結點調整與合並）方法
·B樹中結點個數與高度的關系
·B+樹的定義、搜索、插入與刪除的方法
3、散列表
要點：
·散列函數的比較
·裝填因子 a 與平均搜索長度的關系，平均搜索長度與表長m及表中已有數據對象個數n的關系
·解決地址沖突的（閉散列）線性探查法的運用，平均探查次數的計算
·線性探查法的刪除問題、散列表類的設計中必須為各地址設置三個狀態
·線性探查法中的聚集問題
·解決地址沖突的（閉散列）雙散列法的運用，平均探查次數的計算
·雙散列法中再散列函數的設計要求與表長m互質，為此m設計為質數較宜
·解決地址沖突的（閉散列）二次散列法的運用，平均探查次數的計算
·注意：二次散列法中裝填因子 a 與表長m的設置
·解決地址沖突的（開散列）鏈地址法的運用，平均探查次數的計算
㈢ 數據結構題、大哥大姐幫我做下題吧。萬分感謝啊
什麼是數據、數據對象、數據元素、數據結構、數據的邏輯結構與物理結構、邏輯結構與物理結構間的關系。
2、面向對象概念：理解什麼是數據類型、抽象數據類型、數據抽象和信息隱蔽原則。了解什麼是面向對象。由於目前關於這個問題有許多說法，我們採用了一種最流行的說法，即Coad與Yourdon 給出的定義：面向對象 = 對象 + 類 + 繼承 + 通信。
要點：
·抽象數據類型的封裝性
·面向對象系統結構的穩定性
·面向對象方法著眼點在於應用問題所涉及的對象
3、數據結構的抽象層次：理解用對象類表示的各種數據結構
4、演算法與演算法分析：理解演算法的定義、演算法的特性、演算法的時間代價、演算法的空間代價。
要點：·演算法與程序的不同之處需要從演算法的特性來解釋
·演算法的正確性是最主要的要求
·演算法的可讀性是必須考慮的
·程序的程序步數的計算與演算法的事前估計
·程序的時間代價是指演算法的漸進時間復雜性度量
第二章 數組
1、作為抽象數據類型的數組：數組的定義、數組的按行順序存儲與按列順序存儲
要點：
·數組元素的存放地址計算
2、順序表：順序表的定義、搜索、插入與刪除
要點：
·順序表搜索演算法、平均比較次數的計算
·插入與刪除演算法、平均移動次數的計算
3、多項式：多項式的定義
4、字元串：字元串的定義及其操作的實現
要點：
·串重載操作的定義與實現
第三章 鏈接表
1、單鏈表：單鏈表定義、相應操作的實現、單鏈表的游標類。
要點：
·單鏈表的兩種定義方式（復合方式與嵌套方式）
·單鏈表的搜索演算法與插入、刪除演算法
·單鏈表的遞歸與迭代演算法
2、循環鏈表：單鏈表與循環鏈表的異同
3、雙向鏈表：雙向鏈表的搜索、插入與刪除演算法、鏈表帶表頭結點的優點
4、多項式的鏈接表示
第四章 棧與隊列
1、棧：棧的特性、棧的基本運算
要點：
·棧的數組實現、棧的鏈表實現
·棧滿及棧空條件、抽象數據類型中的先決條件與後置條件
2、棧的應用：用後綴表示計算表達式，中綴表示改後綴表示
3、隊列：隊列的特性、隊列的基本運算
要點：
·隊列的數組實現：循環隊列中隊頭與隊尾指針的表示，隊滿及隊空條件
·隊列的鏈表實現：鏈式隊列中的隊頭與隊尾指針的表示、
4、雙向隊列：雙向隊列的插入與刪除演算法
5、優先順序隊列：優先順序隊列的插入與刪除演算法
第五章 遞歸與廣義表
1、遞歸：遞歸的定義、遞歸的數據結構、遞歸問題用遞歸過程求解
要點：·鏈表是遞歸的數據結構，可用遞歸過程求解有關鏈表的問題
2、遞歸實現時棧的應用
要點：·遞歸的分層（樹形）表示：遞歸樹
·遞歸深度（遞歸樹的深度）與遞歸工作棧的關系
·單向遞歸與尾遞歸的迭代實現
3、廣義表：廣義表定義、廣義表長度、廣義表深度、廣義表表頭、廣義表表尾
要點：
·用圖形表示廣義表的存儲結構
·廣義表的遞歸演算法
第六章 樹與森林
1、樹：樹的定義、樹的基本運算
要點：
·樹的分層定義是遞歸的
·樹中結點個數與高度的關系
2、二叉樹：二叉樹定義、二叉樹的基本運算
要點：
·二叉樹性質、二叉樹中結點個數與高度的關系、不同種類的二叉樹棵數
·完全二叉樹的順序存儲、完全二叉樹的雙親、子女和兄弟的位置
·二叉樹的前序·中序·後序·層次遍歷
·前序
·中序
·後序的線索化二叉樹、前驅與後繼的查找方法
3、霍夫曼樹：霍夫曼樹的構造方法、霍夫曼編碼、帶權路徑長度的計算
4、樹的存儲：樹的廣義表表示、樹的雙親表示、樹與二叉樹的對應關系、樹的先根·中根·後根·層次遍歷。
5、堆：堆的定義、堆的插入與刪除演算法
要點：
·形成堆時用到的向下調整演算法及形成堆時比較次數的上界估計
·堆插入時用到的向上調整演算法
第七章 集合與搜索
1、集合的概念：集合的基本運算、集合的存儲表示
要點：
·用位數組表示集合時集合基本運算的實現
·用有序鏈表表示集合時集合基本運算的實現
2、並查集：並查集定義、並查集的三種基本運算的實現
3、基本搜索方法
要點：
·對一般表的順序搜索演算法（包括有監視哨和沒有監視哨）
·對有序順序表的順序搜索演算法、用判定樹（即擴充二叉搜索樹）描述搜索，以及平均搜索長度（成功與不成功）的計算。
·對有序順序表的折半搜索演算法、用判定樹（即擴充二叉搜索樹）描述搜索，以及平均搜索長度（成功與不成功）的計算。
4、二叉搜索樹：
要點：
·動態搜索樹與靜態搜索樹的特性
·二叉搜索樹的定義、二叉搜索樹上的搜索演算法、二叉搜索樹搜索時的平均搜索長度（成功與不成功）的計算。
·AVL樹結點上的平衡因子、AVL樹的平衡旋轉方法
·高度為h的AVL樹上的最少結點個數與最多結點個數
· AVL樹的搜索方法、插入與刪除方法
第八章 圖
1、圖：圖的定義與圖的存儲表示
要點：
·鄰接矩陣表示（通常是稀疏矩陣）
·鄰接表與逆鄰接表表示
·鄰接多重表(十字鏈表)表示
2、深度優先遍歷與廣度優先遍歷
要點：
·生成樹與生成樹林的定義
·深度優先搜索是個遞歸的過程，而廣度優先搜索是個非遞歸的過程
·為防止重復訪問已經訪問過的頂點，需要設置一個訪問標志數組visited
3、圖的連通性
要點：
·深度優先搜索可以遍歷一個連通分量上的所有頂點
·對非連通圖進行遍歷，可以建立一個生成森林
·對強連通圖進行遍歷，可能建立一個生成森林
·關節點的計算和以最少的邊構成重連通圖
4、最小生成樹
要點：
·對於連通網路、可用不會構成環路的權值最小的n-1條邊構成最小生成樹
·會畫出用Kruskal演算法及Prim演算法構造最小生成樹的過程
5、單源最短路徑
要點：
·採用逐步求解的方式求某一頂點到其他頂點的最短路徑
·要求每條邊的權值必須大於零
6、活動網路
要點：
·拓撲排序、關鍵路徑、關鍵活動、AOE網
·拓撲排序將一個偏序圖轉化為一個全序圖。
·為實現拓撲排序，要建立一個棧，將所有入度為零的頂點進棧
·關鍵路徑的計算
第九章 排序
1、基本概念：關鍵碼、初始關鍵碼排列、關鍵碼比較次數、數據移動次數、穩定性、附加存儲、內部排序、外部排序
2、插入排序：
要點：
·當待排序的關鍵碼序列已經基本有序時，用直接插入排序最快
3、選擇排序：
要點：
·用直接選擇排序在一個待排序區間中選出最小的數據時，與區間第一個數據對調，而不是順次後移。這導致方法不穩定。
·當在n個數據（n很大）中選出最小的5 ~ 8個數據時，錦標賽排序最快
·錦標賽排序的演算法中將待排序的數據個數n補足到2的k次冪2k-1<n≤2k
·在堆排序中將待排序的數據組織成完全二叉樹的順序存儲。
4、交換排序：
要點：
·快速排序是一個遞歸的排序方法
·當待排序關鍵碼序列已經基本有序時，快速排序顯著變慢。
5、二路歸並排序：
要點：
·歸並排序可以遞歸執行
·歸並排序需要較多的附加存儲。可以採用一種"推拉法"（參見教科書上習題）實現歸並排序，演算法的時間復雜度為O (n)、空間復雜度為O(1)
·歸並排序對待排序關鍵碼的初始排列不敏感，排序速度較穩定
6、外排序
要點：
·多路平衡歸並排序的過程、I/O緩沖區個數的配置
·外排序的時間分析、利用敗者樹進行多路平衡歸並
·利用置換選擇方法生成不等長的初始歸並段
·最佳歸並樹的構造及WPL的計算
第十章 索引與散列
1、線性索引：
要點：
·密集索引、稀疏索引、索引表計算
·基於屬性查找建立倒排索引、單元式倒排表
2、動態搜索樹
要點：
·平衡的m路搜索樹的定義、搜索演算法
·B樹的定義、B樹與平衡的m路搜索樹的關系
·B樹的插入（包括結點分裂）、刪除（包括結點調整與合並）方法
·B樹中結點個數與高度的關系
·B+樹的定義、搜索、插入與刪除的方法
3、散列表
要點：
·散列函數的比較
·裝填因子 a 與平均搜索長度的關系，平均搜索長度與表長m及表中已有數據對象個數n的關系
·解決地址沖突的（閉散列）線性探查法的運用，平均探查次數的計算
·線性探查法的刪除問題、散列表類的設計中必須為各地址設置三個狀態
·線性探查法中的聚集問題
·解決地址沖突的（閉散列）雙散列法的運用，平均探查次數的計算
·雙散列法中再散列函數的設計要求與表長m互質，為此m設計為質數較宜
·解決地址沖突的（閉散列）二次散列法的運用，平均探查次數的計算
·注意：二次散列法中裝填因子 a 與表長m的設置
·解決地址沖突的（開散列）鏈地址法的運用，平均探查次數的計算
㈣ 求數據結構試題…重點
這是我們老師要求的重點，即考點。列印出來，背一下就行了，准過！
第一章：緒論
1.1：數據結構課程的任務是：討論數據的各種邏輯結構、在計算機中的存儲結構以及各種操作的演算法設計。
1.2：數據：是客觀描述事物的數字、字元以及所有的能輸入到計算機中並能被計算機接收的各種集合的統稱。
數據元素：表示一個事物的一組數據稱作是一個數據元素，是數據的基本單位。
數據項：是數據元素中有獨立含義的、不可分割的最小標識單位。
數據結構概念包含三個方面：數據的邏輯結構、數據的存儲結構的數據的操作。
1.3數據的邏輯結構指數據元素之間的邏輯關系，用一個數據元素的集合定義在此集合上的若干關系來表示，數據結構可以分為三種：線性結構、樹結構和圖。
1.4：數據元素及其關系在計算機中的存儲表示稱為數據的存儲結構，也稱為物理結構。
數據的存儲結構基本形式有兩種：順序存儲結構和鏈式存儲結構。
2.1：演算法：一個演算法是一個有窮規則的集合，其規則確定一個解決某一特定類型問題的操作序列。演算法規則需滿足以下五個特性：
輸入——演算法有零個或多個輸入數據。
輸出——演算法有一個或多個輸出數據，與輸入數據有某種特定關系。
有窮性——演算法必須在執行又窮步之後結束。
確定性——演算法的每個步驟必須含義明確，無二義性。
可行性——演算法的每步操作必須是基本的，它們的原則上都能夠精確地進行，用筆和紙做有窮次就可以完成。
有窮性和可行性是演算法最重要的兩個特徵。
2.2：演算法與數據結構：演算法建立數據結構之上，對數據結構的操作需用演算法來描述。
演算法設計依賴數據的邏輯結構，演算法實現依賴數據結構的存儲結構。
2.3：演算法的設計應滿足五個目標：
正確性：演算法應確切的滿足應用問題的需求，這是演算法設計的基本目標。
健壯性：即使輸入數據不合適，演算法也能做出適當的處理，不會導致不可控結
高時間效率：演算法的執行時間越短，時間效率越高。 果。
高空間效率：演算法執行時佔用的存儲空間越少，空間效率越高。
可讀性：演算法的可讀性有利於人們對演算法的理解。
2.4：度量演算法的時間效率，時間復雜度，（課本39頁）。
2.5：遞歸定義：即用一個概念本身直接或間接地定義它自己。遞歸定義有兩個條件：
至少有一條初始定義是非遞歸的，如1！=1.
由已知函數值逐步遞推計算出未知函數值，如用（n-1）！定義n！。
第二章：線性表
1.1線性表：線性表是由n(n>=0)個類型相同的數據元素a0,a1,a2,…an-1,組成的有限序列,記作： LinearList = (a0,a1,a2,…an-1)
其中，元素ai可以是整數、浮點數、字元、也可以是對象。n是線性表的元素個數，成為線性表長度。若n=0，則LinearList為空表。若n>0，則a0沒有前驅元素，an-1沒有後繼元素，ai（0<i<n-1）有且僅有一個直接前驅元素ai-1和一個直接後繼元素ai+1。
1.2線性表的順序存儲是用一組連續的內存單元依次存放線性表的數據元素，元素在內存的物理存儲次序與它們在線性表中的邏輯次序相同。
線性表的數據元素數據同一種數據類型，設每個元素佔用c位元組，a0的存儲地址為
Loc（a0），則ai的存儲地址Loc（ai）為：Loc（ai） = Loc（a0）+ i*c
數組是順序存儲的隨機存儲結構，它佔用一組連續的存儲單元，通過下標識別元素，元素地址是下標的線性函數。
1.3：順序表的插入和刪除操作要移動數據元素。平均移動次數是 屬數據表長度的一半。（課本第50頁）
1.4：線性表的鏈式存儲是用若乾地址分散的存儲單元存儲數據元素，邏輯上相鄰的數據元素在物理位置上不一定相鄰，必須採用附加信息表示數據元素之間的順序關系。
它有兩個域組成：數據域和地址域。通常成為節點。（課本第55頁及56頁）
1.5單鏈表（課本56頁）
單鏈表的遍歷：Node<E> p = head; while(p!=null){ 訪問p節點；p = p.next;}
單鏈表的插入和刪除操作非常簡便，只要改變節點間的鏈接關系，不需移動數據元素。
單鏈表的插入操作：1）：空表插入/頭插入 2)中間插入/尾插入
if(head == null) Node<E> q = new Node<E>(x);
{ head = new Node<E>(x); q.next = p.next;
}else{ p.next = q;
Node<E> q=new Node<E>(x); 中間插入或尾插入都不會改變單表
q.next = head; 的頭指針head。
head = q;
}
單鏈表的刪除操作：
頭刪除：head = head.next;
中間/尾刪除：if(p.next!=null){ p.next = p.next.next;}
循環單鏈表：如果單鏈表最後一個節點的next鏈保存單鏈表的頭指針head值，則該單鏈表成為環形結構，稱為循環單鏈表。（課本67）
若rear是單鏈表的尾指針，則執行（rear.next=head;）語句，使單鏈表成為一條循環單鏈表。當head.next==head時，循環單鏈表為空。
1.6：雙鏈表結構：雙鏈表的每個結點有兩個鏈域，分別指向它的前驅和後繼結點，
當head.next==null時，雙鏈表為空。
設p指向雙鏈表中非兩端的某個結點，則成立下列關系：p=p.next.prev=p.prev.next。
雙鏈表的插入和刪除：1）插入 2)刪除
q=new DLinkNode（x）； p.prev.next = p.next;
q.prev=p.prev;q.next =p; if(p.next=null){
p.prev.next = q;p.prev=q; (p.next).prev = p.prev;}
循環雙鏈表：當head.next==head且head.prev==head時，循環雙鏈表為空。
第三章：棧和隊列
1.1棧：棧是一種特殊的線性表，其中插入和刪除操作只允許在線性表的一端進行。允許操作的一端稱為棧頂，不允許操作的一端稱為棧底。棧有順序棧和鏈式棧。
棧中插入元素的操作稱為入棧，刪除元素的操作稱為出棧。沒有元素的中稱為空棧。
棧的進出棧順序：後進先出，先進後出。（及75頁的思考題）。
1.2：隊列：隊列是一種特殊的線性表，其中插入和刪除操作分別在線性表的兩端進行。
向隊列中插入元素的過程稱為入隊，刪除元素的過程稱為出對，允許入隊的一端稱為隊尾，允許出隊的一端稱為對頭。沒有元素的隊列稱為空隊列。隊列是先進先出。
第四章：串
1.1：串是一種特殊的線性表，其特殊性在於線性表中的每個元素是一個字元。一個串記為： s=「s0s1s2…sn-1」 其中n>=0,s是串名，一對雙引號括起來的字元序列s0s1s2…sn-1是串值，si（i=0，1，2，…n-1）為特定字元集合中的一個字元。一個串中包含的字元個數稱為串的長度。
長度為0的串稱為空串，記作「」，而由一個或多個空格字元構成的字元串稱為空格串。
子串：由串s中任意連續字元組成的一個子序列sub稱為s的子串，s稱為sub的主串。子串的序號是指該子串的第一個字元在主串中的序號。
串比較：兩個串可比較是否相等，也可比較大小。兩個串（子串）相等的充要條件是兩個串（子串）的長度相同，並且各對應位置上的字元也相同。
兩個串的大小由對應位置的第一個不同字元的大小決定，字元比較次序是從頭開始依次向後。當兩個串長度不等而對應位置的字元都相同時，較長的串定義為較「大」。
第五章：數組和廣義表
1.1：數組是一種數據結構，數據元素具有相同的數據類型。一維數組的邏輯結構是線性表，多維數組是線性表的擴展。
1.2：一維數組：一維數組採用順序存儲結構。一個一維數組佔用一組連續的存儲單元。
設數組第一個元素a0的存儲地址為Loc（a0），每個元素佔用c位元組，則數組其他元素ai的存儲地址Loc（ai）為： Loc（ai）= Loc（a0）+i*c
數組通過下標識別元素，元素地址是下標的線性函數。一個下標能夠唯一確定一個元素，所劃給的時間是O（1）。因此數組是隨機存取結構，這是數組最大的優點。
1.3：多維數組的遍歷：有兩種次序：行主序和列主序。
行主序：以行為主序，按行遞增訪問數組元素，訪問完第i行的所有元素之後再訪問第i+1行的元素，同一行上按列遞增訪問數組元素。
a00,a01,…a0(n-1), a10,a11,…a1(n-1),…a(m-1)0,a(m-1)1,…,a(m-1)(n-1)
2)列主序：以列為主序，按列遞增訪問數組元素，訪問完第j列的所有元素之後再訪問第j+1列的元素，同一列上按列遞增訪問數組元素。
多維數組的存儲結構：多維數組也是由多個一維數組組合而成，組合方式有一下兩種。
靜態多維數組的順序存儲結構：可按行主序和列主序進行順序存儲。
按行主序存儲時，元素aij的地址為：Loc（aij）= Loc（a00）+（i*n+j）*c
按列主序存儲時，Loc（aij）= Loc（a00）+（j*m+i）*c
動態多維數組的存儲結構。
二維數組元素地址就是兩個下標的線性函數。無論採用哪種存儲結構，多維數組都是基於一維數組的，因此也只能進行賦值、取值兩種存取操作，不能進行插入，刪除操作。
第六章：
樹是數據元素（結點）之間具有層次關系的非線性結構。在樹結構中，除根以外的結點只有一個直接前驅結點，可以有零至多個直接後繼結點。根沒有前驅結點。
樹是由n（n>=0）個結點組成的有限集合（樹中元素通常稱為結點）。N=0的樹稱為空樹；n>0大的樹T；
@有一個特殊的結點稱為根結點，它只有後繼結點，沒有前驅結點。
@除根結點之外的其他結點分為m（m>=0）個互不相交的集合T0,T1,T3……..,Tm-1，其中每個集合Ti（0<=i<m）本身又是一棵樹，稱為根的子樹。
樹是遞歸定義的。結點是樹大的基本單位，若干個結點組成一棵子樹，若干棵互不相交的子樹組成一棵樹。樹的每個結點都是該樹中某一棵子樹的根。因此，樹是由結點組成的、結點之間具有層次關系大的非線性結構。
結點的前驅結點稱為其父母結點，反之，結點大的後繼結點稱為其孩子結點。一棵樹中，只有根結點沒有父母結點，其他結點有且僅有一個父母結點。
擁有同一個父母結點的多個結點之間稱為兄弟結點。結點的祖先是指從根結點到其父母結點所經過大的所有結點。結點的後代是指該結點的所有孩子結點，以及孩子的孩子等。
結點的度是結點所擁有子樹的棵數。度為0的結點稱為葉子結點，又叫終端結點；樹中除葉子結點之外的其他結點稱為分支結點，又叫非葉子結點或非終端結點。樹的度是指樹中各結點度的最大值。
結點的層次屬性反應結點處於樹中的層次位置。約定根結點的層次為1，其他結點的層次是其父母結點的層次加1。顯然，兄弟結點的層次相同。
樹的高度或深度是樹中結點的最大層次樹。
設樹中x結點是y結點的父母結點，有序對（x，y）稱為連接這兩個結點的分支，也稱為邊。
設（X0,X1,….,Xk-1）是由樹中結點組成的一個序列，且（Xi，Xi+1）（0<=i<k-1）都是樹中的邊，則該序列稱為從X0到Xk-1的一條路徑。路徑長度為路徑上的邊數。
在樹的定義中，結點的子樹T0，T1…..,Tm-1之間沒有次序，可以交換位置，稱為無序樹，簡稱樹。如果結點的子樹T0,T1……,Tm-1從左到右是有次序的，不能交換位置，則 稱該樹為有序樹。
森林是m（m>=0）棵互不相乾的樹的集合。給森林加上一個根結點就變成一棵樹，將樹的根節點刪除就變成森林。
二叉樹的性質1：若根結點的層次為1，則二叉樹第i層最多有2 的i-1次方（i>=1）個結點。
二叉樹的性質2：在高度為k的二叉樹中，最多有2的k次方減一個結點。
二叉樹的性質3：設一棵二叉樹的葉子結點數為n0,2度結點數為n2，則n0=n2+1。
一棵高度為k的滿二叉樹是具有2的k次方減一個結點的二叉樹。滿二叉樹中每一層的結點數目都達到最大值。對滿二叉樹的結點進行連續編號，約定根節點的序號為0，從根節點開始，自上而下，每層自左至右編號。
一棵具有n個結點高度為k的二叉樹，如果他的每個節點都與高度為k的滿二叉樹中序號為0~n-1
的結點一一對應，則這棵二叉樹為為完全二叉樹。
滿二叉樹是完全二叉樹，而完全二叉樹不一定是滿二叉樹。完全二叉樹的第1~k-1層是滿二叉樹第k層不滿，並且該層所有結點必須集中在該層左邊的若干位置上。
二叉樹的性質4：一棵具有n個結點的完全二叉樹，其高度k=log2n的絕對值+1
二叉樹的性質5：一棵具有n個結點的完全二叉樹，對序號為i的結點，有
@若i=0，則i為根節點，無父母結點；若i>0，則i的父母結點的序號為[（i-1）/2]。
@若2i+1<n，則i的左孩子結點序號為2i+1；否則i無左孩子。
@若2i+2<n，則i的右孩子結點的序號為2i+2，否則i無右孩子。
二叉樹的遍歷
二叉樹的遍歷是按照一定規則和次序訪問二叉樹中的所有結點，並且每個結點僅被訪問一次。
二叉樹的三種次序遍歷
1：先根次序；訪問根節點，遍歷左子樹，遍歷右子樹。
2：中根次序；遍歷左子樹，訪問右子樹，遍歷右子樹。
3：後根次序；遍歷左子樹，遍歷右子樹，訪問根節點。
先根次序遍歷時，最先訪問根節點；後根次序遍歷時，最後訪問根節點；中根次序遍歷時，左子樹上的結點在根節點之前訪問，右子樹上的結點在根節點之後訪問。
二叉樹的插入和刪除操作P147
二叉樹的層次遍歷P149
習題P167 6—10，6—19
第七章
圖是由定點集合及頂點間的關系集合組成的一種數據關邊系。頂點之間的關系成為邊。一個圖G記為G=（V,E），V是頂點A的有限集合，E是邊的有限集合。即 V={A|A屬於某個數據元素集合}
E={(A,B)|A,B屬於V}或E={<A,B>|A,B屬於V且Path（A,B）}其中Path（A,B）表示從頂點A到B的一條單向通路，即Path（A,B）是有方向的。
無向圖中的邊事沒有方向，每條邊用兩個頂點的無序對表示。
有向圖中的邊是有方向，每條邊用兩個頂點的有序對表示。
完全圖指圖的邊數達到最大值。n個頂點的完全圖記為Kn。無向完全圖Kn的邊數為n*（n-1）/2,有向完全圖Kn的邊數為n*（n-1）。
子圖：設圖G==(V,E),G』=(V』,E』)，若V』包含於V且E』包含於E,則稱圖G』是G的子圖。若G』是G的真子圖。
連通圖：在無向圖G中，若從頂點VI到Vj有路徑，則稱Vi和Vj是聯通的。若圖G中任意一對頂點Vi和Vj（Vi不等於Vj）都是聯通的，則稱G為連通圖。非連通圖的極大聯通子圖稱為該圖的聯通分量。
強連通圖：在有向圖中，若在每一對頂點Vi和Vj（Vi不等於Vj）之間都存在一條從Vi到Vj的路徑，也存在一條從Vi到Vj的路徑，也存在一條從Vi到Vj的路徑，則稱該圖的強連通圖。非強連通圖的極大強連通子圖稱為該圖的強連通圖分量。
圖的遍歷
遍歷圖是指從圖G中任意一個頂點V出發，沿著圖中的邊前行，到達並訪問圖中的所有頂點，且每個頂點僅被訪問一次。遍歷圖要考慮一下三個問題：
@指定遍歷的第一個訪問頂點
@由於一個頂點可能與多個頂點相鄰，因此要在多個鄰接頂點之間約定一種訪問次序。
@由於圖中可能存在迴路，在訪問某個頂點之後，可能沿著某條路徑又回到該頂點。
深度優先搜索
圖的深度優先搜索策略是，訪問某個頂點v，接著尋找v的另一個未被訪問的鄰接頂點w訪問，如此反復執行，走過一條較長路徑到達最遠頂點；若頂點v沒有未被訪問的其他鄰接頂點，則回到前一個被訪問頂點，再尋找其他訪問路徑。
圖的深度優先搜索遍歷演算法P188
聯通的無迴路的無向圖，簡稱樹。樹中的懸掛點又成為樹葉，其他頂點稱為分支點。各連通分量均為樹的圖稱為森林，樹是森林。
由於樹中無迴路，因此樹中必定無自身環也無重邊（否則他有迴路）若去掉樹中的任意一條邊，則變成森林，成為非聯通圖；若給樹加上一條邊，形成圖中的一條迴路，則不是樹。P191
生成樹和生成森林：
一個連通無向圖的生成樹是該圖的一個極小聯通生成子圖，它包含原圖中所有頂點（n個）以及足以構成一棵樹的n-1條邊。
一個非聯通的無向圖，其各連通圖分量的生成圖組成該圖的生成森林。
圖的生成圖或生成森林不是唯一的，從不同頂點開始、採用不同遍歷可以得到不同的生成樹或森林。
在生成樹中，任何樹中，任何兩個頂點之間只有唯一的一條路徑。
第八章
折半查找演算法描述 P206,P207
二叉排序樹及其查找：
二叉排序樹或者是一棵空樹；或者是具有下列性質的二叉樹：
@每個結點都有一個作為查找依據的關鍵字，所有結點的關鍵字互不相同。
@若一個結點的左子樹不空，則左子樹上所有結點的關鍵字均小於這個節點的關鍵字；
@每個結點的左右子樹也分別為二叉排序樹。
在一棵二叉排序樹中，查找值為value的結點，演算法描述如下：
@從根結點開始，設p指向根結點
@將value與p結點的關鍵字進行比較，若兩者相等，則查找成功；若value值較小，則在p的左子樹中繼續查找；若value值較大，則在p的右子樹中繼續查找。
@重復執行上一步，直到查找成功或p為空，若p為空，則查找不成功。
習題 8-6
第九章
直接插入排序演算法描述：p228
冒泡排序演算法的描述：p232
快速排序演算法描述p233
直接選擇排序演算法描述p236
直接選擇排序演算法實現如下：
Public static void selectSort(int[]table){
for(int i=0;i<table.length-1;i++){
int min=I;
for(int j=i+1;j<table.length;j++){
if(table[j]<table[min])
min=j;
if(min!=i){
int temp=table[i];
table[i]==table[min];
table[min]=temp;
}
}
}
}
堆排序是完全二叉樹的應用，是充分利用完全二叉樹特性的一種選擇排序。
堆定義：設n個元素的數據序列{k0，k1，。。。。kn-1}，當且僅當滿足下列關系
k1<=k2i+1且ki<=k2i+2 i=0,1,2,3,….,[n/2-1]
或ki>==k2i+1且ki>=2i+2i=0,1,2,3,…..[n/2-1]時，序列{k0，k1…….kn-1}稱為最小堆或最大堆。將最小（大）堆看成是一顆完全二叉樹的層次遍歷序列，則任意一個結點的關鍵字都小於等於（大於等於）它的孩子節點的關鍵字值，由此可知，根結點值最小（大）。根據二叉樹的性質5，完全二叉樹中的第i（0<=i<n）個結點，如果有孩子，則左孩子為第2i+1個結點，右孩子為第2i+2個結點。
希望對你會有所幫助。
㈤ 用演算法實現:單鏈表和順序表刪除。刪除順序表中值相同的多餘結點
第8章排序(演算法設計)習題練習答案
作者： 來源： http://www.csai.cn 2006年9月4日
13. 將哨兵放在R[n]中，被排序的記錄放在R[0..n-1]中，重寫直接插入排序演算法。
解：
重寫的演算法如下：
void InsertSort(SeqList R)
{//對順序表中記錄R[0..n-1]按遞增序進行插入排序
int i,j;
for(i=n-2;i>=0;i--) //在有序區中依次插入R[n-2]..R[0]
if(R[i].key>R[i+1].key) //若不是這樣則R[i]原位不動
{
R[n]=R[i];j=i+1; //R[n]是哨兵
do{ //從左向右在有序區中查找插入位置
R[j-1]=R[j]; //將關鍵字小於R[i].key的記錄向右移
j++;
}while(R[j].key<R[n].key]);
R[j-1]=R[n]; //將R[i]插入到正確位置上
}//endif
}//InsertSort.
14.以單鏈表作為存儲結構實現直接插入排序演算法。
解：
#define int KeyType //定義KeyType 為int型
typedef struct node{
KeyType key; //關鍵字域
OtherInfoType info; //其它信息域，
struct node * next; //鏈表中指針域
}RecNode; //記錄結點類型
typedef RecNode * LinkList ; //單鏈表用LinkList表示
void InsertSort(LinkList head)
{//鏈式存儲結構的直接插入排序演算法,head是帶頭結點的單鏈表
RecNode *p,*q,*s;
if ((head->next)&&(head->next->next))//當表中含有結點數大於1
{
p=head->next->next;//p指向第二個節點
head->next=NULL;
q=head;//指向插入位置的前驅節點
while(p)&&(q->next)&&(p->key<q->next->key)
q=q->next;
if (p)
{s=p;p=p->next;// 將要插入結點摘下
s->next=q->next;//插入合適位置：q結點後
q->next=s;
}
}
}
15.設計一演算法，使得在盡可能少的時間內重排數組，將所有取負值的關鍵字放在所有取非負值的關鍵字之前。請分析演算法的時間復雜度。
解：
因為只需將負數關鍵字排在前面而無需進行精確排列順序，因此本演算法採用兩端掃描的方法，就象快速排序採用的方法一樣，左邊掃描到正數時停止，開始掃描右邊，遇到負數時與左邊的當前記錄交換，如此交替進行，一趟下來就可以完成排序。
void ReSort(SeqList R)
{//重排數組，使負值關鍵字在前
int i=1,j=n; //數組存放在R[1..n]中
while (i<j) //i<j表示尚未掃描完畢
{ while(i<j&&R[i].key<0) //遇到負數則繼續掃描
i++;
R[0]=R[i]; //R[0]為輔助空間
while(i<j&&R[j].key>=0)// 遇到正數則繼續向左掃描
j--;
R[i++]=R[j];R[j--]=R[0];//交換當前兩個元素並移動指針
}//endwhile
}//ReSort
本演算法在任何情況下的比較次數均為n(每個元素和0)相比，交換次數少於n/2，總的來說，時間復雜度為O(n).
*16.寫一個雙向冒泡排序的演算法，即在排序過程中交替改變掃描方向。
解：
演算法如下：
void BubbleSort(SeqList R)
{//R[1..n]是待排序文件，雙向掃描冒泡排序
int i,j,k;
Boolean exchange; //交換標記
i=n;j=1;
exchange=TRUE;
while (i>j)&&(exchange)
{k=i-1;exchange=FALSE;
while (k>=j)//由下往上掃描
{if (r[k]>r[k+1])
{r[0]=r[k];r[k]=r[k+1];r[k+1]=r[k];exchange=TRUE;//交換
}//endif
k--;
}//endwhile
if (exchange)
{exchange=FALSE;
j++;k=j+1;
while(k<=i)//由上往下掃描
{if (r[k]<r[k-1])
{r[0]=r[k];r[k]=r[k-1];r[k-1]=r[k];exchange=TRUE;//交換
}//endif
k++;
}endwhile
i--;
}//endif
}endwhile
}//endsort
17.下面是一個自上往下掃描的冒泡排序的偽代碼演算法，它採用lastExchange 來記錄每趟掃描中進行交換的最後一個元素的位置，並以它作為下一趟排序循環終止的控制值。請仿照它寫一個自下往上掃描的冒泡排序演算法。
void BubbleSort(int A[],int n)
//不妨設A[0..n-1]是整型向量
int lastExchange,j,i=n-1;
while (i>0)
lastExchange=0;
for(j=0;j<i;j++)//從上往下掃描A[0..i]
if(A[j+1]<A[j]){
交換A[j]和A[j+1];
lastExchange=j;
}
i=lastExchange;//將i置為最後交換的位置
}//endwhile
}//BubbleSort
解：演算法如下：
void BubbleSort(int A[],int n)
//不妨設A[0..n-1]是整型向量
int lastExchange,j,i=0;
while (i<n) //這一條很重要，如不改為這樣，演算法將無限循環下去
lastExchange=n;
for(j=n-1;j>i;j--)//從下往上掃描A[0..i]
if(A[j-1]<A[j]){
交換A[j]和A[j-1];
lastExchange=j;
}
i=lastExchange;//將i置為最後交換的位置
}//endwhile
}//BubbleSort
18.改寫快速排序演算法，要求採用三者取中的方式選擇劃分的基準記錄；若當前被排序的區間長度小於等於3時，無須劃分而是直接採用直接插入方式對其排序。
解：
改寫後的演算法如下：
void QuickSort(SeqList R,int low ,int high)
{//對R[low..high]快速排序
int pivotpos;
if(high-low<=2)//若當前區內元素少於3個
{//則進行直接插入排序
InsertSort(R,low,high);
}
else
{
pivotpos=midPartion(R,low,high);
QuickSort(R,low,pivotpos-1);
QuickSort(R,pivotpos+1，high);
}
}//QuickSort
int midPartion(SeqList R,int i, int j)
{//三者取中規則定基準
if(R[(i+j)/2].key>R[i].key)
{ 交換R[(i+j)/2]和R[i];}
if(R[i].key>R[j].key)
{ 交換R[i]和R[j];}
if(R[i].key)<R[(i+j)/2].key)
{ 交換R[i]和R[(i+j)/2];}
//以上三個if語句就使區間的第一個記錄的key值為三個key的中間值
return Partion(R,i,j);//這樣我們就可以仍使用原來的劃分演算法了
}
19.對給定的j(1≤j≤n ),要求在無序的記錄區R[1..n]中找到按關鍵字自小到大排在第j個位置上的記錄(即在無序集合中找到第j個最小元)，試利用快速排序的劃分思想編寫演算法實現上述的查找操作。
答：
int QuickSort(SeqList R,int j,int low,int high)
{ //對R[low..high]快速排序
int pivotpos； //劃分後的基準記錄的位置
if(low<high){//僅當區間長度大於1時才須排序
pivotpos=Partition(R，low，high)； //對R[low..high]做劃分
if (pivotpos==j) return r[j];
else if (pivotpos>j) return(R,j,low,pivotpos-1);
else return quicksort(R,j,pivotpos+1,high);
}
} //QuickSort
20.以單鏈表為存儲結構，寫一個直接選擇排序演算法。
答：
#define int KeyType //定義KeyType 為int型
typedef struct node{
KeyType key; //關鍵字域
OtherInfoType info; //其它信息域，
struct node * next; //鏈表中指針域
}RecNode; //記錄結點類型
typedef RecNode * LinkList ; //單鏈表用LinkList表示
void selectsort(linklist head)
{RecNode *p,*q,*s;
if(head->next)&&(head->next->next)
{p=head->next;//p指向當前已排好序最大元素的前趨
while (p->next)
{q=p->next;s=p;
while(q)
{if (q->key<s->key) s=q;
q=q->next;
}//endwhile
交換s結點和p結點的數據；
p=p->next;
}//endwhile
}//endif
}//endsort
21.寫一個heapInsert(R,key)演算法，將關鍵字插入到堆R中去，並保證插入R後仍是堆。提示：應為堆R增加一個長度屬性描述(即改寫本章定義的SeqList類型描述，使其含有長度域)；將key先插入R中已有元素的尾部(即原堆的長度加1的位置，插入後堆的長度加1)，然後從下往上調整，使插入的關鍵字滿足性質。請分析演算法的時間。
答：
#define n 100//假設文件的最長可能長度
typedef int KeyType; //定義KeyType 為int型
typedef struct node{
KeyType key; //關鍵字域
OtherInfoType info; //其它信息域，
}Rectype; //記錄結點類型
typedef struct{
Rectype data[n] ; //存放記錄的空間
int length;//文件長度
}seqlist;
void heapInsert(seqlist *R,KeyType key)
{//原有堆元素在R->data[1]~R->data[R->length],
//將新的關鍵字key插入到R->data[R->length+1]位置後，
//以R->data[0]為輔助空間，調整為堆(此處設為大根堆)
int large;//large指向調整結點的左右孩子中關鍵字較大者
int low,high;//low和high分別指向待調整堆的第一個和最後一個記錄
int i;
R->length++；R->data[R->length].key=key;//插入新的記錄
for(i=R->length/2;i>0;i--)//建堆
{
low=i;high=R->length;
R->data[0].key=R->data[low].key;//R->data[low]是當前調整的結點
for(large=2*low;large<=high;large*=2){
//若large>high，則表示R->data[low]是葉子，調整結束；
//否則令large指向R->data[low]的左孩子
if(large<high&&R->data[large].key<R->data[large+1].key)
large++;//若R->data[low]的右孩子存在
//且關鍵字大於左兄弟，則令large指向它
if (R->data[0].key<R->data[large].key)
{ R->data[low].key= R->data[large].key;
low=large;//令low指向新的調整結點
}
else break;//當前調整結點不小於其孩子結點的關鍵字，結束調整
}//endfor
R->data[low].key=R->data[0].key;//將被調整結點放入最終的位置上
}//end of for
}end of heapinsert
演算法分析：
設文件長度為n,則該演算法需進行n/2趟調整，總的時間復雜度與初建堆類似，最壞時間復雜度為O(nlgn)，輔助空間為O(1).
22.寫一個建堆演算法：從空堆開始，依次讀入元素調用上題中堆插入演算法將其插入堆中。
答：
void BuildHeap(seqlist *R)
{
KeyType key;
R->length=0;//建一個空堆
scanf("%d",&key);//設MAXINT為不可能的關鍵字
while(key!=MAXINT)
{
heapInsert(R,key);
scanf("%d",&key);
}
}
23.寫一個堆刪除演算法：HeapDelete(R,i),將R[i]從堆中刪去，並分析演算法時間，提示：先將R[i]和堆中最後一個元素交換，並將堆長度減1，然後從位置i開始向下調整，使其滿足堆性質。
答：
void HeapDelete(seqlist *R,int i)
{//原有堆元素在R->data[1]~R->data[R->length],
//將R->data[i]刪除，即將R->data[R->length]放入R->data[i]中後，
//將R->length減1，再進行堆的調整，
//以R->data[0]為輔助空間，調整為堆(此處設為大根堆)
int large;//large指向調整結點的左右孩子中關鍵字較大者
int low,high;//low和high分別指向待調整堆的第一個和最後一個記錄
int j;
if (i>R->length)
Error("have no such node");
R->data[i].key=R->data[R->length].key;
R->length--；R->data[R->length].key=key;//插入新的記錄
for(j=i/2;j>0;j--)//建堆
{
low=j;high=R->length;
R->data[0].key=R->data[low].key;//R->data[low]是當前調整的結點
for(large=2*low;large<=high;large*=2){
//若large>high，則表示R->data[low]是葉子，調整結束；
//否則令large指向R->data[low]的左孩子
if(large<high&&R->data[large].key<R->data[large+1].key)
large++;//若R->data[low]的右孩子存在
//且關鍵字大於左兄弟，則令large指向它
if (R->data[0].key<R->data[large].key)
{ R->data[low].key= R->data[large].key;
low=large;//令low指向新的調整結點
}
else break;//當前調整結點不小於其孩子結點的關鍵字，結束調整
}//endfor
R->data[low].key=R->data[0].key;//將被調整結點放入最終的位置上
}//end of for
}end of HeapDelete
24.已知兩個單鏈表中的元素遞增有序，試寫一演算法將這兩個有序表歸並成一個遞增有序的單鏈表。演算法應利用原有的鏈表結點空間。
答：
typedef struct node{
KeyType key; //關鍵字域
OtherInfoType info; //其它信息域，
struct node * next; //鏈表中指針域
}RecNode; //記錄結點類型
typedef RecNode * LinkList ; //單鏈表用LinkList表示
void mergesort(LinkList la,LinkList lb,LinkList lc)
{RecNode *p,*q,*s,*r;
lc=la;
p=la;//p是la表掃描指針，指向待比較結點的前一位置
q=lb->next;//q是lb表掃描指針，指向比較的結點
while(p->next)&&(q)
if (p->next->key<=q->key)
p=p->next;
else {s=q;q=q->next;
s->next=p->next;p->next=s;//將s結點插入到p結點後
p=s;}
if (!p->next) p->next=q;
free(lb);
}
25.設向量A[0..n-1]中存有n個互不相同的整數，且每個元素的值均在0到n-1之間。試寫一時間為O(n)的演算法將向量A排序，結果可輸出到另一個向量B[0..n-1]中。
答：
sort(int *A,int *B)
{//將向量A排序後送入B向量中
int i;
for(i=0;i<=n-1;i++)
B[A[i]]=A[i];
}
*26.寫一組英文單詞按字典序排列的基數排序演算法。設單詞均由大寫字母構成，最長的單詞有d個字母。提示：所有長度不足d個字母的單詞都在尾處補足空格，排序時設置27個箱子，分別與空格，A，B...Z對應。
答：
#define KeySize 10 //設關鍵字位數d=10
#define Radix 27 //基數rd為27
typedef RecType DataType;//將隊列中結點數據類型改為RecType類型
typedef struct node{
char key[KeySize]; //關鍵字域
OtherInfoType info; //其它信息域，
}RecType; //記錄結點類型
typedef RecType seqlist[n+1];
void RadixSort(seqlist R)
{
LinkQueue B[Radix];
int i;
for(i=0;i<Radix;i++)//箱子置空
InitQueue(&B[i]);
for(i=KeySize-1;i>=0;i--){//從低位到高位做d趟箱排序
Distribute(R,B,i);//第KeySize-i趟分配
Collect(R,B);//第KeySize-i趟收集
}
}
void Distribute(seqlist R,LinkQueue B[], int j)
{//按關鍵字的第j個分量進行分配，初始時箱子為空
int i;
j=KeySize-j; // 確定關鍵字從低位起的位置
for(i=0;i<n;i++) //依次掃描R[i]，將其裝箱
if (R[i].key[j]-'A'>26)
EnQueue(&B[0],R[i]);//將第j位關鍵字位空格的記錄入第0個隊列
else EnQueue(&B[0],R[R[i].key[j]-'A'+1]);
}
void Collect(seqlist R,LinkQueue B[])
{
//依次將各非空箱子中的記錄收集起來，本過程結束，各箱子都變空
int i,j;
for (j=0;j<Radix;j++)
while(!QueueEmpty(&B[j]))
R[i++]=DeQueue(&B[j]);//將出隊記錄依次輸出到R[i]中
}