數據結構教程(第4版)（簡體書）

《高等學校數據結構課程系列教材：數據結構教程（第4版）》在前3版的基礎上，根據教育部新的考研大綱和大量讀者來信提出的要求進行了修訂。《高等學校數據結構課程系列教材：數據結構教程（第4版）》內容包括緒論、線性表、棧和隊列、串、遞歸、數組和廣義表、樹和二叉樹、圖、查找、內排序、外排序和文件，還給出了6個綜合實驗題、實驗報告格式、引用型參數的說明、順序表和順序棧以及順序隊列使用指針引用型參數的說明、書中部分算法清單、全國計算機專業數據結構2011年聯考大綱。
《高等學校數據結構課程系列教材：數據結構教程（第4版）》適合高等院校計算機及相關專業本科生和研究生使用。

李春葆，武漢大學計算機學院教授，主要研究方向為數據挖掘和算法設計，先後主持和參加多個大型研究項目。主要為本科生講授數據結構（15年以上）和軟件工程等課程，為研究生講授軟件開發新技術、數據倉庫與數據挖掘等課程，並出版十多部精品著作。

《"十二五"普通高等教育本科國家級規劃教材?高等學校數據結構課程系列教材:數據結構教程(第4版)》針對數據結構課程概念多、算法靈活和抽象性強等特點，在總結長期教學經驗的基礎上編寫的。《"十二五"普通高等教育本科國家級規劃教材?高等學校數據結構課程系列教材:數據結構教程(第4版)》適合高等院校計算機及相關專業本科生和研究生使用。

第1章緒論
1．1什麼是數據結構
1．1．1數據結構的定義
1．1．2邏輯結構類型
1．1．3存儲結構類型
1．1．4數據類型和數據結構
1．2算法及其描述
1．2．1什麼是算法
1．2．2算法描述
1．3算法分析
1．3．1算法設計的目標
1．3．2算法效率分析
1．3．3算法存儲空間分析
1．4數據結構十算法-程序
1．4．1程序和數據結構
1．4．2算法和程序
1．4．3算法和數據結構
1．4．4數據結構的發展
本章小結
練習題1
上機實驗題1

第2章線性表
2．1線性表及其邏輯結構
2．1．1線性表的定義
2．1．2線性表的抽象數據類型描述
2．2線性表的順序存儲結構
2．2．1線性表的順序存儲結構：順序表
2．2．2順序表基本運算的實現
2．3線性表的鏈式存儲結構
2．3．1線性表的鏈式存儲結構：鏈表
2．3．2單鏈表
2．3．3雙鏈表
2．3．4循環鏈表
2．4線性表的應用
2．5有序表
2．5．1有序表的抽象數據類型描述
2．5．2有序表的存儲結構及其基本運算算法
2．5．3有序表的歸併算法
2．5．4有序表的應用
本章小結
練習題2
上機實驗題2

第3章棧和隊列
3．1棧
3．1．1棧的定義
3．1．2棧的順序存儲結構及其基本運算的實現
3．1．3棧的鏈式存儲結構及其基本運算的實現
3．1．4棧的應用
3．2隊列
3．2．1隊列的定義
3．2．2隊列的順序存儲結構及其基本運算的實現
3．2．3隊列的鏈式存儲結構及其基本運算的實現
3．2．4隊列的應用
3．2．5雙端隊列
本章小結
練習題3
上機實驗題3

第4章串
4．1串的基本概念
4．2串的存儲結構
4．2．1串的順序存儲結構：順序串
4．2．2串的鏈式存儲結構：鏈串
……

第5章遞歸
第6章數組和廣義表
第7章樹和二叉樹
第8章圖
第9章查找
第10章內排序
第11章外排序
第12章文件
第13章採用面向對象的方法描述算法
附錄A綜合實驗題
附錄B實驗報告格式
附錄C引用型參數的說明
附錄D順序表、順序棧和順序隊列使用指針引用型參數的說明
附錄E書中部分算法清單
附錄F全國計算機專業數據結構2012年聯考大綱
參考文獻

7.2.3二叉樹與樹、森林之間的轉換
樹、森林與二叉樹之間有一個自然的對應關系，它們之間可以進行相互轉換，即任何一個森林或一棵樹都可以唯一地對應一棵二叉樹，而任一棵二叉樹也能唯一地對應一個森林或一棵樹。正是由于有這樣的一一對應關系，可以把在樹中處理的問題對應到二叉樹中進行處理，從而可以把問題簡單化。下面介紹森林、樹與二叉樹相互轉換的方法。
對于一般的樹來說，樹中節點的左右次序無關緊要，只要其雙親節點與孩子節點的關系不發生錯誤就可以了。但在二叉樹中，左、右孩子節點的次序不能隨意顛倒。因此，下面討論的二叉樹與一般樹之間的轉換都約定按照樹在圖形上的節點次序進行，即把一般樹作為有序樹來處理，這樣不致于引起混亂。
上述方法是一種遞歸構造方法，如果假定T是有序樹的序列，那么，由T所構造的二叉樹β（T）是唯一的。
用上述遞歸方法構造的二叉樹p（T）的節點與原來樹T的節點的關系為：二叉樹β（T）中的任意節點k，若有左孩子節點，則該左孩子節點為k原來的最左邊（即第一棵）子樹的根節點；若有右孩子節點，則該右孩子節點為k原來的右邊相鄰的第一個兄弟節點或右邊第一棵相鄰的樹的根節點（當k為原森林中樹的根節點時）。由此可以把遞歸構造二叉樹β（T）的過程歸納如下：
（1）在所有相鄰兄弟節點（森林中每棵樹的根節點可看成是兄弟節點）之間加一條水平連線。
（2）對每個非葉子節點k，除了其最左邊的孩子節點外，刪去k與其他孩子節點的連線。
（3）所有水平線段以左邊節點為軸心順時針旋轉45°。
通過以上步驟，原來的森林就轉換為一棵二叉樹。一棵樹是森林中的特殊情況，由一棵樹轉換的二叉樹的根節點的右孩子節點始終為空，原因是一棵樹的根節點不存在兄弟節點和相鄰的樹。
【例7.5】將如圖7.6（a）所示的森林（由三棵樹組成）轉換成二叉樹。
解：轉換為二叉樹的過程如圖7.6（b）和（c）所示，最終結果如圖7.6（d）所示。