資料結構:C語言描述(簡體書)
- 系列名:清華大學電腦系列教材
- ISBN13:9787302291190
- 出版社:清華大學出版社(大陸)
- 作者:殷人昆
- 裝訂/頁數:平裝/426頁
- 出版日:2012/10/08
商品簡介
作者簡介
名人/編輯推薦
目次
1.1 數據結構的概念及分類
1.1.1 為什么要學習數據結構
1.1.2 與數據結構相關的基本術語
1.1.3 數據結構的分類
1.1.4 數據結構的存儲結構
1.1.5 定義在數據結構上的操作
1.1.6 “好”的數據結構
1.2 使用C語言描述數據結構
1.2.1 C語言的數據類型
1.2.2 算法的控制結構
1.2.3 算法的函數結構
1.2.4 動態存儲分配
1.2.5 邏輯和關系運算的約定
1.2.6 輸入與輸出
1.3 算法和算法設計
1.3.1 算法的定義和特性
1.3.2 算法的設計步驟
1.3.3 算法設計的基本方法
1.4 算法分析與度量
1.4.1 算法的評價標準
1.4.2 算法的時間和空間復雜性度量
1.4.3 算法的漸進分析
小結
習題
第2章 線性表
2.1 線性表
2.1.1 線性表的定義和特點
2.1.2 線性表的主要操作
2.2 順序表
2.2.1 順序表的定義和特點
2.2.2 順序表的結構定義
2.2.3 順序表主要操作的實現
2.2.4 順序表主要操作的性能分析
2.2.5 順序表的應用舉例
2.3 單鏈表
2.3.1 單鏈表的定義和特點
2.3.2 單鏈表的結構定義
2.3.3 單鏈表中指針的操作
2.3.4 單鏈表中的插入與刪除
2.3.5 帶頭結點的單鏈表
2.3.6 單鏈表主要操作的性能分析
2.3.7 單鏈表的順序訪問與尾遞歸
2.3.8 單鏈表的應用舉例
2.4 順序表與線性鏈表的比較
2.5 線性鏈表的其他變形
2.5.1 循環鏈表
2.5.2 雙向鏈表
2.5.3 靜態鏈表
2.6 線性表的應用:一元多項式及其運算
2.6.1 一元多項式的表示
2.6.2 多項式的結構定義
2.6.3 多項式的加法
2.6.4 多項式的乘法
小結
習題
第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.3 棧的應用
3.3.1 數制轉換
3.3.2 括號匹配
3.3.3 表達式的計算與優先級處理
3.3.4 棧與遞歸的實現
3.4 隊列的應用
3.4.1 打印楊輝三角形與逐行處理
3.4.2 電路布線與兩點間的最短路徑
3.5 在算法設計中使用遞歸
3.5.1 漢諾塔問題與分治法
3.5.2 迷宮問題與回溯法
3.5.3 計算組合數與動態規劃
3.6 雙端隊列
3.6.1 雙端隊列的概念
3.6.2 輸入受限的雙端隊列
3.6.3 輸出受限的雙端隊列
3.6.4 雙端隊列的順序存儲表示
3.6.5 雙端隊列的鏈接存儲表示
小結
習題
第4章 數組、串和廣義表
4.1 數組
4.1.1 一維數組
4.1.2 多維數組
4.1.3 數組的應用舉例
4.2 特殊矩陣的壓縮存儲
4.2.1 對稱矩陣的壓縮存儲
4.2.2 三對角矩陣的壓縮存儲
4.3 稀疏矩陣
4.3.1 稀疏矩陣的概念
4.3.2 稀疏矩陣的三元組表表示
4.3.3 稀疏矩陣的十字鏈表表示
4.4 字符串
4.4.1 字符串的概念
4.4.2 字符串的初始化和賦值
4.4.3 C語言中有關字符串的庫函數
4.4.4 自定義字符串的存儲表示
4.4.5 串的模式匹配
4.5 廣義表
4.5.1 廣義表的概念
4.5.2 廣義表的性質
4.5.3 廣義表的鏈接表示
4.5.4 三元多項式的表示
小結
習題
第5章 樹與二叉樹
5.1 樹的基本概念
5.1.] 樹的定義和術語
5.1.2 樹的基本操作
5.2 二叉樹
5.2.1 二叉樹的概念
5.2.2 二叉樹的性質
5.2.3 二叉樹的主要操作
5.3 二叉樹的存儲表示
5.3.1 二叉樹的順序存儲表示
5.3.2 二叉樹的鏈表存儲表示
5.4 二叉樹的遍歷
5.4.1 二叉樹遍歷的遞歸算法
5.4.2 遞歸遍歷算法的應用舉例
5.4.3 二叉樹遍歷的非遞歸算法
5.4.4 非遞歸遍歷算法的應用舉例
5.4.5 二叉樹的計數
5.5 線索二叉樹
5.5.1 線索二叉樹的概念
5.5.2 線索二叉樹的種類
5.5.3 中序線索二叉樹的建立和遍歷
5.5.4 前序與后序線索二叉樹
5.6 樹與森林
5.6.1 樹的存儲表示
5.6.2 森林與二叉樹的轉換
5.6.3 樹與森林的深度優先遍歷
5.6.4 樹與森林的廣度優先遍歷
5.6.5 樹遍歷算法的應用舉例
小結
習題
第6章 樹與二叉樹的應用
6.1 二叉查找樹
6.1.1 二叉查找樹的概念
6.1.2 二叉查找樹的查找
6.1.3 二叉查找樹的插入
6.1.4 二叉查找樹的刪除
6.1.5 二叉查找樹的性能分析
6.2 AVL樹
第7章 圖
第8章 查找
第9章 內排序
第10章 外排序
附錄A 程序索引
附錄B 實訓作業要求與樣例
參考文獻
書摘/試閱
此外,函數每遞歸調用一層,必須重新分配一批工作單元,包括本層使用的局部變量和形式參數(實際是上一層傳來的實際參數的副本)等,這樣可以防止使用數據的沖突,還可以在退出本層返回到上一層后恢復上一層的數據。
2.遞歸工作棧
為了保證遞歸過程每次調用和返回的正確執行,必須解決調用時的參數數據傳遞和返回地址問題。因此,在每次遞歸過程調用時,必須做參數保存和參數傳遞等工作。在高級語言的處理程序中,是利用一個“遞歸工作棧”來進行處理的。
每一層遞歸調用所需保存的信息構成一個工作記錄,它通常包括如下內容:
(1)返回地址:即上一層中調用自己的語句的后繼語句處。
(2)在本次過程調用時,為與形式參數對應的實際參數創建副本。包括傳值參數的副本空間、引用型參數和返回值的地址空間。
(3)為本層的局部變量值分配的存儲空間。遞歸工作記錄的結構如圖3—16(b)所示。
在每進入一層遞歸時,系統就要建立一個新的王作記錄,把上述項目登入,加到遞歸工作棧的棧頂。它構成函數可用的活動框架。每退出一層遞歸,就從遞歸工作棧退出 一個工作記錄。因此,棧頂的工作記錄必定是當前正在執行的這一層的工作記錄,所以又稱為活動記錄。
以圖3—15所示的計算Factorial(4)的過程為例,看遞歸計算的過程中遞歸工作棧和活動記錄是如何使用的,如圖3—17所示。
最初對Factorial(4)的調用由主程序執行。當函數運行結柬后控制返回到主程序RetLocl處,主程序將使用函數的返回值24(即4!)繼續做計算或賦值。而在Factorial(4)函數過程內部遞歸調用Factorial(3)時,調用返回到Factorial程序內部RetLoc2處,計算n*(n—1)!,RetLoc2在乘法運算符*處。
就Factorial函數而言,每一層遞歸調用所創建的活動記錄山3部分組成:實際參數值n的副本、返回上一層的指令地址和局部變量存儲單元trmp。如圖3—17(a)所示。
Factorial(4)的執行啟動了一連串5個函數調用。圖3—17(b)描述廠每一次函數調用吋的活動記錄。主程序外部調用的活動記錄在棧的底部,隨內部調用一層層地進棧。遞歸結束條件出現于函數Factorial(0)的內部,從此開始一連串的返回語句。退出棧頂的活動記錄,控制按返回地址轉移到上一層調用遞歸過程處。
遞歸工作棧是編譯程序實現遞歸機制時在內部建立的,使用者看不到。但是,分析算法的時間復雜度和空間復雜度時應考慮它的時間和空間開銷,因此必須了解它的工作。
3.4 隊列的應用
隊列在計算機中也有廣泛的應用,除了用作輸入/輸出緩沖區、為實現調度算法而創建的任務隊列和進程隊列之外,在數據結構方面還有很多用途。
主題書展
更多主題書展
更多書展本週66折
您曾經瀏覽過的商品
購物須知
大陸出版品因裝訂品質及貨運條件與台灣出版品落差甚大,除封面破損、內頁脫落等較嚴重的狀態,其餘商品將正常出貨。
特別提醒:部分書籍附贈之內容(如音頻mp3或影片dvd等)已無實體光碟提供,需以QR CODE 連結至當地網站註冊“並通過驗證程序”,方可下載使用。
無現貨庫存之簡體書,將向海外調貨:
海外有庫存之書籍,等候約45個工作天;
海外無庫存之書籍,平均作業時間約60個工作天,然不保證確定可調到貨,尚請見諒。
為了保護您的權益,「三民網路書店」提供會員七日商品鑑賞期(收到商品為起始日)。
若要辦理退貨,請在商品鑑賞期內寄回,且商品必須是全新狀態與完整包裝(商品、附件、發票、隨貨贈品等)否則恕不接受退貨。