數據結構基礎教程(C語言)（簡體書）

《重點大學計算機專業系列教材：數據結構基礎教程（C語言）》是數據結構課程的基本教材。全書分為3個部分：課程概述、基於內存的數據結構（線性結構、樹結構、圖結構和集合）和基於文件的數據結構（文件的組織與查找）。本書的編寫思路和材料組織具有體現整體結構、注重本質關聯、突出關鍵細節和強化實例講解等特點，同時書中的基本算法和實例實現程序都經過vc平臺調試運行，實現教材學習到實驗操作的無縫對接。本書還配有相應學習指導書供相關人員選用。
《重點大學計算機專業系列教材：數據結構基礎教程（C語言）》可供高等院校計算機信息科學與技術及其相關專業本科教學使用，同時也適合於非計算機專業人員自學使用。·

章毓晉，1989年獲比利時列日大學應用科學博士學位。1989年至1993年為荷蘭德爾夫特大學博士後及研究人員。從1993年到中國北京清華大學工作，1997年被聘為教授，1998年被評為博士生導師。2003年學術休假期間同時被聘為新加坡南洋理工大學訪問教授。
在清華大學，先後開出並講授10多門本科生和研究生課程。在南洋理工大學，開出並講授過研究生課程：“現代圖像分析（英語）”。已編寫出版了圖像工程系列教材第1版和第2版，以及《圖像處理和分析基礎》，《圖像處理和分析技術》（第2版），《圖像處理和分析教程》、《計算機視覺教程》和《Image Engineering：Processing，Analysis，and Understanding》，翻譯出版了《彩色數字圖像處理》。已在國內外發表了30多篇教學研究論文。
主要科學研究領域為其積極倡導的圖像工程（圖像處理、圖像分析、圖像理解及其技術應用）和相關學科。從1996年起已連續十六年對中國圖像工程的研究及主要文獻進行了系統的年度分類總結綜述。已在國內外發表400多篇圖像工程研究論文，出版了專著《圖像分割》，《基於內容的視覺信息檢索》，《基於子空間的人臉識別》，編著了《英漢圖像工程辭典》，主持編著了《Advances in Image and Video Segmentation》，《Semantic-Based Visual lnformation Retrieval》，《Advances in Face Image Analysis：Techniques and Technologies》。
現為中國圖像圖形學學會學術委員會主任；國際電氣電子工程師協會（IEEE）高級會員；國際光學工程協會（SPIE）會士（因在圖像工程方面的成就）；《中國圖像圖形學報》副主編，《電子與信息學報》，《計算機輔助設計與圖形學學報》，《信號處理》和《自動化學報》編委；以及國際刊物“Pattern Recognition Letters”的associate editor。曾任第一屆、第二屆、第四屆、第五屆和第六屆國際圖像圖形學術會議（ICIG'2000.ICIG'2002，ICIG'2007.ICIG'2009.ICIG'2011）程序委員會主席，第十二屆、第十三屆、第十四屆、第十五屆和第十六屆全國圖像圖形學術會議（NCIG'2005，NCIG'2006，NCIG'2008，NCIG'2010，NCIG'2012）程序委員會主席。·

《重點大學計算機專業系列教材:數據結構基礎教程(C語言)》可供高等院校計算機信息科學與技術及其相關專業本科教學使用，同時也適合于非計算機專業人員自學使用。

第1章 緒論
1.1 數據
1.2 數據項與數據元素
1.3 數據類型與抽象數據類型
1.4 數據模型與數據結構
1.5 數據操作與算法
1.6 數據結構課程的地位與本書內容體系
本章小結

第2章 線性表
2.1 線性表的概念
2.2 線性表的順序存儲
2.3 線性表的鏈式存儲
2.4 線性表存儲結構的比較
本章小結

第3章 棧與隊列
3.1 棧
3.2 隊列
本章小結

第4章 數組、串與廣義表
4.1 數組
4.2 串
4.3 廣義表
本章小結

第5章 二叉樹
5.1 二叉樹及其基本性質
5.2 二叉樹的存儲
5.3 二叉樹的遍歷
5.4 線索二叉樹
5.5 二叉樹的應用
本章小結

第6章 樹與森林
6.1 樹及其相關概念
6.2 樹的存儲結構
6.3 樹的遍歷
6.4 森林
6.5 樹與二叉樹的轉換
本章小結

第7章 圖
7.1 基本概念與相關描述
7.2 圖的存儲
7.3 圖的遍歷
7.4 生成樹與最小生成樹
7.5 最短路徑
7.6 有向無環網及應用
本章小結

第8章 查找
8.1 數據查找
8.2 基於線性表的查找
8.3 基於二叉樹的查找
8.4 基於散列表的查找
本章小結

第9章 排序
9.1 數據排序
9.2 插入排序
9.3 交換排序
9.4 選擇排序
9.5 歸併排序
9.6 外排序
本章小結

第10章 文件
10.1 文件的基本概念
10.2 順序文件
10.3 索引文件
10.4 動態索引b-樹
10.5 散列文件
10.6 多關鍵字文件
本章小結
參考文獻·

函數遞歸調用是C語言的一個主要特點，分為直接調用和間接調用兩種情形。如果在函數f中，又需要調用f函數，這就是直接遞歸調用本函數f；如果在函數f1中需要調用另一函數f2，而在函數f2中又要調用函數f1，這就是函數的間接遞歸調用。
遞歸過程需要解決遞歸計算公式和遞歸結束條件兩個問題。
（1）遞歸計算公式：大問題在變成次大問題中表現出來的規律，要表達清楚這個大問題與下一級的次大問題有什么聯系。
（2）遞歸結束條件：解決遞歸問題中的分解不能無終止地分解下去，需有一個結束的條件。這樣才可以由結束遞歸再返回層層解套，最終解決整個問題。遞歸的結束條件也稱為遞歸出口。
上述遞歸問題的解決大致做下述的算法描述：
n階階乘f（n）=n！=n（n—1）！的計算過程就體現了上述遞歸思想的應用。
n階階乘（factorial）n！是基斯頓·卡曼（Christian Kramp，1760—1826）于1808年提出的運算符號。n階階乘n！是指從1乘以2乘以3乘以4一直乘到所要求的自然數n，即前n個自然數的連乘。如所要求的數是3，則階乘式是1×2×3，得到的積是6，6就是3的階乘。如所要求的數是n，則階乘式是1×2×3×…×n，設得到的積是x，x就是n的階乘。求n！時，如n比較大，n！就會很大，一般比較難計算，用計算機計算是常用的快捷方法。
可以使用遞歸的思想來考慮n！的計算，即要求解n！，先要求解（n—1）！；要求解（n—1）！，又要先求解（n—2）！；……；要求解2！，先求解1！；要求解1！，先求解0！。而0！=1是遞歸結束的返回值，即n=0就是遞歸出口。然后再返回層層解套：1！=0！×1=1，進而求2！，3！，…，n！。相應如算法3—8所示。
算法3—8 遞歸方法求解n的階乘。
算法分析上述算法程序中給出的階乘函數fact是一個遞歸函數。假設輸人的n是合法的，即n≥0。如果n==0時將結束函數的執行，否則就遞歸調用fact函數自身。由于遞歸調用的實參為n—1，即把n—1的值賦予形參n。當n—1的值為1時，此時n—1不等于0，繼續作遞歸調用，當形參n的值為0時，這時遞歸終止，然后逐層退回。假設執行上述程序時輸人為3，即求3！。在主函數中的調用語句即為fac=fact（3），進人fact函數后，先進行程序中第03行的判斷，由于n=3不等于0，故執行程序中第06行fac=fact（72—1）×n，即fac=fact（3—1）×3，該語句對fact作遞歸調用，即fact（2）。進行2次遞歸調用后，fact函數形參取得的值變為0，故不再繼續遞歸調用而開始逐層返回主調函數。fact（0）的函數返回值為1；fact（1）的函數返回值為1×1=1；fact（2）的返回值為1×2=2；最后fact（3）的返回值為2×3=6。
fact（3）=3！遞歸實現如圖3—8所示。圖中，實線箭頭表示正向分解，虛線箭頭表示反向回溯。
如前所述，對于遞歸過程中的函數調用，需要考慮下述幾個基本問題。
（1）實際參數：即每次調用中與形式參數相關聯的實在參數，其中包括函數名稱、引用參數和實在參數等，如在圖3—8首次調用過程中需要將實參3傳遞給fact（n）的形參n。
（2）計算結果：即回溯過程中每次得到的計算結果，如fact（1）=1，fact（2）=2，fact（3）=6。
（3）返回地址：即回溯過程中需要返回的地址，也就是上一層中本次調用自身語句的后繼語句位置，如圖3—8中的loc0和loc1等。