實用數據結構(2013年清華大學出版出版的圖書)

《實用數據結構》是由林小茶編著，2013年清華大學出版社出版的普通高等教育"十一五"國家級規劃教材、北京高等教育精品教材。該教材既可以作為計算機相關專業本科學生學習數據結構的教材，也可作為自學者的教材或參考書。

該教材共8章，主要內容包括概述、棧與佇列、線性表、線性表的鏈式存儲、哈希表與索引表、內排序等。

基本介紹

• 書名：實用數據結構
• 作者：林小茶
• ISBN：9787302338284
• 類別：普通高等教育"十一五"國家級規劃教材、北京高等教育精品教材
• 頁數：273頁
• 出版社：清華大學出版社
• 出版時間：2013年12月1日
• 裝幀：平裝
• 開本：16開
• 字數：447千字
• CIP核字號：2013215278

成書過程

該教材由林小茶編著。2013年12月1日，該教材由清華大學出版社出版。

出版社工作人員

責任編輯	封面設計	責任校對	責任印製
張民	常雪影	梁毅	何芊

內容簡介

該教材共8章，主要內容包括概述、棧與佇列、線性表、線性表的鏈式存儲、哈希表與索引表、內排序、樹與二叉樹和圖。在各章內容的安排上不求大而全，力求少而精，講解透徹，重點突出。

教材目錄

第1章概述/11.1什麼是數據結構/1; 1.2數據結構的相關概念和術語/5; 1.3算法/8; 1.3.1算法的概念/8; 1.3.2算法的特性/11; 1.3.3算法的描述方法——類C語言/12; 1.4算法分析/13; 1.4.1計算比較次數和移動次數/13; 1.4.2大O表示法及算法的時間複雜度/16; 1.4.3最好、最差和平均情況/18; 1.4.4算法的空間複雜度/19; 本章小結/20; 習題/20; 第2章棧與佇列/23; 2.1棧/23; 2.1.1棧的實例/23; 2.1.2棧的基本概念/24; 2.1.3棧的順序存儲/25; 2.1.4順序棧的基本算法/26; 2.1.5順序棧的算法效率/30; 2.1.6棧的鏈式存儲/30; 2.1.7單鏈棧的基本算法/32; 2.1.8鏈棧的算法效率/35; 2.1.9棧套用舉例/35; 2.2佇列/39; 2.2.1佇列的實例/39; 2.2.2佇列的基本概念/39; 2.2.3順序佇列的基本思想/40; 2.2.4環形佇列的基本算法/43; 2.2.5環形佇列的算法效率/47; 2.2.6用單鍊表存儲佇列的基本算法/47; 2.2.7鏈佇列的算法效率/51; 2.2.8佇列套用舉例/51; 本章小結/58; 習題/59; 第3章線性表/64; 3.1線性表的定義/64; 3.1.1線性表實例/64; 3.1.2線性表的定義和基本操作/64; 3.1.3線性表的數學定義和邏輯圖/65; 3.2線性表的順序存儲結構/66; 3.3順序表基本算法實現/68; 3.3.1線性表內容與線性表長度分別存儲的算法實現/68; 3.3.2線性表內容與線性表長度存儲在一個結構體中的算法實現/75; 3.4順序表的查找/78; 3.4.1順序查找/79; 3.4.2二分查找/80; 3.4.3順序查找與二分查找的效率分析/81; 3.5插入與刪除操作的效率分析/82; 3.5.1在順序表的第i個位置（邏輯位置）; 插入一個元素/82; 3.5.2插入算法的移動次數/84; 3.5.3刪除算法的移動次數/84; 3.6順序表套用舉例/85; 本章小結/92; 習題/93; 第4章線性表的鏈式存儲/97; 4.1線性表的鏈式存儲結構/97; 4.1.1為什麼要使用鏈式存儲結構/97; 4.1.2單鍊表的數據定義/98; 4.2基於單鍊表的算法實現/99; 4.2.1單鍊表的基本算法實現/99; 4.2.2單鍊表中插入運算的進一步討論/105; 4.3單鍊表套用舉例/109; 4.4鏈式存儲的其他方法/115; 4.5基於帶表頭結點的單循環鍊表算法實現/117; 4.5.1帶表頭結點的單循環鍊表的基本算法實現/117; 4.5.2帶表頭結點的單循環鍊表的套用舉例/122; 4.5.3帶表頭結點與不帶表頭結點的單循環鍊表的比較/124; 4.6雙向鍊表基本算法實現/126; 4.7順序存儲與鏈式存儲方式的比較/132; 本章小結/132; 習題/133

第5章哈希表與索引表/139; 5.1查找的基本概念/139; 5.2哈希表/140; 5.2.1哈希表的基本概念/140; 5.2.2衝突的產生/141; 5.2.3可以選擇的哈希函式/142; 5.2.4解決衝突的方法/145; 5.2.5基本算法的實現/147; 5.2.6哈希表存儲方法的性能分析/154; 5.2.7哈希表套用舉例/155; 5.3索引表/157; 5.3.1索引表的構成/157; 5.3.2索引表的查找/159; 5.3.3分塊查找/161; 5.4各種查找算法的效率分析/162; 本章小結/163; 習題/164; 第6章內排序/167; 6.1排序的基本概念/167; 6.1.1簡單選擇排序的算法思想和實現/167; 6.1.2排序的相關概念/169; 6.2插入排序/170; 6.2.1直接插入排序的算法思想和實現/170; 6.2.2折半插入排序思想和算法實現/173; 6.2.3希爾排序思想和算法實現/174; 6.2.4插入排序算法效率分析/177; 6.3交換排序/179; 6.3.1冒泡排序思想和算法實現/179; 6.3.2快速排序思想和算法實現/181; 6.3.3交換排序算法效率分析/185; 6.4歸併排序/185; 6.5基數排序/188; 6.6各種排序算法的比較和分析/192; 本章小結/193; 習題/193; 第7章樹與二叉樹/197; 7.1樹與二叉樹的基本概念/197; 7.1.1樹與二叉樹實例/197; 7.1.2樹與二叉樹的定義/198; 7.1.3樹與二叉樹的相互轉換/199; 7.2二叉樹的基本操作和實現/200; 7.2.1二叉樹的存儲結構/200; 7.2.2二叉樹的建立/203; 7.2.3二叉樹的遍歷/205; 7.3套用舉例:堆排序/211; 7.4線索二叉樹/215; 7.5哈夫曼樹/218; 7.5.1哈夫曼樹與哈夫曼編碼/218; 7.5.2算法實現/220; 7.6二叉搜尋樹/223; 7.6.1二叉搜尋樹的定義/223; 7.6.2二叉搜尋樹基本操作實現/224; 7.6.3套用舉例/230; 本章小結/232; 習題/233; 第8章圖/239; 8.1圖的基本概念/239; 8.1.1圖的實例/239; 8.1.2圖的定義和術語/240; 8.2圖的存儲結構/241; 8.2.1圖的鄰接矩陣表示/242; 8.2.2圖的鄰接表表示/245; 8.2.3圖的十字鍊表表示/247; 8.3圖的操作和實現/249; 8.3.1圖的建立/249; 8.3.2圖的遍歷/254; 8.4圖的套用——拓撲排序/260; 8.4.1拓撲排序的思想/260; 8.4.2拓撲排序的實現/263; 8.5圖的套用——最小生成樹/265; 8.5.1最小生成樹的構造方法/265; 8.5.2構造最小生成樹的算法實現/267; 本章小結/270; 習題/271; 參考文獻/274

（註：目錄排版順序為從左列至右列）

教學資源

該教材配有輔助教材《實用數據結構習題解答與上機指導》。

書名	書號	出版社	作者
《實用數據結構習題解答與上機指導》	9787302399599	清華大學出版社	林小茶

教材特色

該教材為與計算機套用相關的專業量身定做，保留了經典數據結構的主要內容，但是做了一些必要的刪減，以適應相對較少的課時安排；同時，還選擇了一些實用性比較強的實例作為案例。在講解數據的存儲結構時，使用了大量的圖表。

該教材在編寫的過程中，遵循譚浩強老師提出的“提出問題——解決問題——歸納分析”的新三部曲，強調從實踐中獲取知識。該教材給出了能夠解決實際問題的算法，希望學生們在閱讀和總結這些算法的基礎上提高自己程式設計的水平。因此，該教材的大部分算法只要經過簡單的修改，就能上機運行。

該教材將經典的數據結構內容做了一些重新整合，去掉了一些筆者認為只是為了應付考試而沒有實用價值的內容。例如，該教材並沒有將數組和（字元）串的內容作為單獨的章節來討論，而是將這部分內容融入其他章節，作為解決具體問題的一種方法，從而避免了只討論抽象而簡單的理論，而不注重實用的講解方法。

作者簡介

林小茶，女，1962年生，北京信息科技大學信息管理學院副教授，主要研究方向為信息安全。