算法與數據結構（第2版）

《算法與數據結構（第2版）》是由寧正元、賴賢偉編著，2012年清華大學出版社出版的高等院校信息技術規劃教材。該教材可以適應於不同院校計算機科學與技術學科各專業的教學需求，也可作為從事計算機科學與技術工作的科技人員的參考用書。

全書內容共8章。主要內容包括：算法與程式，常用數據結構，簡單數據結構，樹與二叉樹，圖與網，數據結構的程式實現，檢索及基本算法，排序及基本算法。

基本介紹

• 書名：算法與數據結構（第2版）
• 作者：寧正元、賴賢偉
• ISBN：9787302274926
• 類別：高等院校信息技術規劃教材
• 頁數：261頁
• 出版社：清華大學出版社
• 出版時間：2012年3月1日
• 裝幀：平裝
• 開本：16開
• 字數：431千字
• CIP核字號：2011253601

成書過程

修訂過程

作者在總結教學經驗和體會的基礎上，結合大學生的素質特點與學習現狀（截止2012年3月1日），按照《中國計算機科學與技術學科教程2002》中設定的“算法與數據結構”課程教學大綱要求編寫而成。

該教材由寧正元教授和賴賢偉博士共同編著，其中第1～8章由寧正元教授執筆，賴賢偉博士針對該教材製作了電子教案。王秀麗教授、陳國龍教授、康寶生教授、林大輝副教授、易金聰副教授、黃思先副教授、劉雄恩副教授、黃建實驗師、林敏講師等在該教材的成稿前期工作或精品課程建設中做了部分工作或提供了幫助，高等教育出版社計算機分社社長張龍和清華大學出版社計算機分社高級策劃編輯袁勤勇對該教材的出版都給予了支持。

出版工作

2012年3月1日，該教材由清華大學出版社出版。

出版社工作人員

責任編輯	封面設計	責任校對	責任印製
袁勤勇、顧冰	傅瑞學	李建莊	李紅英

內容簡介

全書內容共8章。第1章介紹算法與程式的基本概念、表示、設計和分析方法，是在前導課程“高級語言程式設計”基礎上的進一步引申和總結；第2章由前導課程中的數據類型概念引出數據結構的有關基本概念，並介紹讀者已在前導課程中熟知的數組結構和串結構的進一步內容；第3章介紹一些簡單的線性結構（如順序表、鍊表、棧、佇列、廣義表等結構）的定義、基本算法和典型套用；第4章和第5章介紹非線性結構中的樹、二叉樹、圖與網的有關內容；第6章介紹各類數據結構在程式設計語言中的實現策略和大批量數據的組織策略，並結合實際問題討論了數據結構在問題建模中的套用方法；第7章和第8章介紹了在實際套用中使用的檢索和排序的基本算法，並進行了算法分析。

教材目錄

第1章算法與程式11.1算法的基本概念1; 1.1.1什麼是算法1; 1.1.2算法的基本特性2; 1.2算法的表示3; 1.2.1自然語言表示3; 1.2.2流程圖表示3; 1.2.3N-S圖表示4; 1.2.4偽代碼表示4; 1.2.5程式語言表示5; 1.3算法的設計與評價6; 1.3.1評價算法的標準6; 1.3.2算法的環路複雜度7; 1.3.3算法的時空效率8; 1.3.4常見的算法設計方法11; 1.4算法與程式14; 1.4.1程式的基本概念14; 1.4.2問題求解與實現策略14; 1.4.3程式調試與查錯策略16; 1.4.4程式設計方法概述17; 習題121; 第2章常用數據結構23; 2.1數據類型與數據結構23; 2.1.1數據、數據元素與數據類型23; 2.1.2數據結構的基本概念25; 2.1.3抽象數據類型27; 2.2數組29; 2.2.1數組及其運算29; 2.2.2數組的順序存儲結構30; 2.2.3特殊矩陣的壓縮存儲31; 2.3串34; 2.3.1串的基本概念34; 2.3.2串的定長順序存儲及運算實現35; 2.3.3模式匹配38; 2.3.4串的堆式動態存儲及運算實現43; 2.3.5漢字串46; 習題249; 上機實驗題51; 第3章簡單數據結構52; 3.1順序表52; 3.1.1線性表的基本概念52; 3.1.2線性表的順序存儲結構--順序表53; 3.1.3順序表上的基本運算54; 3.2鍊表58; 3.2.1線性表的鏈式存儲結構--鍊表58; 3.2.2單鍊表上的基本運算60; 3.2.3循環鍊表和雙向鍊表65; 3.2.4線性表套用舉例--一元多項式相加問題67; 3.3棧69; 3.3.1棧的概念及運算69; 3.3.2順序棧及運算實現69; 3.3.3鏈棧及運算實現72; 3.3.4棧的套用舉例--遞歸的實現74; 3.4佇列76; 3.4.1佇列的概念及其運算76; 3.4.2順序佇列及運算實現77; 3.4.3鏈佇列及運算實現80; 3.4.4佇列的套用舉例--I/O緩衝區管理及其他82; 3.5廣義表84; 3.5.1廣義表的概念84; 3.5.2廣義表的存儲結構及運算實現85; 3.5.3廣義表的套用--m元多項式的表示87; 習題389; 上機實驗題92; 第4章樹與二叉樹93; 4.1樹的基本概念93; 4.1.1樹的定義及表示93; 4.1.2樹的常用術語及運算94; 4.2二叉樹96; 4.2.1二叉樹的概念96; 4.2.2二叉樹的性質97; 4.2.3二叉樹的存儲結構98; 4.2.4二叉樹的簡單運算實現101; 4.3二叉樹的遍歷102; 4.3.1遍歷二叉樹的遞歸算法102; 4.3.2遍歷二叉樹的非遞歸算法104; 4.3.3遍歷序列與二叉樹的復原108; 4.3.4基於遍歷的幾種二叉樹運算的實現和套用舉例110; 4.4線索二叉樹111; 4.4.1線索二叉樹的概念111; 4.4.2線索二叉樹的構造算法113; 4.4.3線索二叉樹上的運算實現114; 4.5樹和森林115; 4.5.1樹和森林的存儲結構116; 4.5.2樹和森林與二叉樹之間的轉換117; 4.5.3樹和森林的遍歷119; 4.5.4樹的套用舉例--判定樹120; 4.6哈夫曼樹121; 4.6.1哈夫曼樹的概念及其構造算法121; 4.6.2哈夫曼樹的套用--哈夫曼編碼124; 習題4125

上機實驗題128; 第5章圖與網129; 5.1圖與網的基本概念129; 5.1.1圖與網的定義129; 5.1.2圖的相關術語130; 5.2圖與網的存儲結構132; 5.2.1鄰接矩陣132; 5.2.2鄰接表與逆鄰接表133; 5.2.3鄰接多重表135; 5.3圖的遍歷136; 5.3.1深度優先搜尋遍歷136; 5.3.2廣度優先搜尋遍歷138; 5.3.3圖的遍歷套用舉例--圖的連通性與生成樹139; 5.4無向連通網的最小生成樹140; 5.4.1最小生成樹的概念140; 5.4.2Prim算法141; 5.4.3Kruskal算法143; 5.5有向網的最短路徑144; 5.5.1單源最短路徑144; 5.5.2所有頂點對之間的最短路徑146; 5.6有向無環圖及其套用148; 5.6.1有向無環圖的概念148; 5.6.2AOV網與拓撲排序150; 5.6.3AOE網與關鍵路徑154; 習題5159; 上機實驗題161; 第6章數據結構的程式實現162; 6.1基本的實現策略162; 6.1.1簡單數據結構的程式實現162; 6.1.2構造型數據結構的程式實現163; 6.1.3數據結構的鏈式實現163; 6.1.4數據結構的數組實現163; 6.2動態結構的靜態實現163; 6.2.1靜態鍊表164; 6.2.2二叉樹的靜態二叉鍊表表示法164; 6.2.3樹和森林的雙親表示法165; 6.2.4哈夫曼算法的靜態實現166; 6.3大批量數據的組織策略170; 6.3.1檔案的組織170; 6.3.2資料庫技術177; 6.4數據結構在問題建模中的套用179; 6.4.1Josephus問題180; 6.4.2教務管理與二分圖182; 6.4.3學籍管理系統中的數據組織185; 習題6190; 上機實驗題191; 第7章檢索及基本算法192; 7.1檢索的概念192; 7.2線性表的檢索194; 7.2.1順序檢索194; 7.2.2二分法檢索195; 7.2.3黃金分割點檢索198; 7.2.4精算點檢索200; 7.2.5分塊檢索202; 7.3樹表的檢索204; 7.3.1二叉檢索樹204; 7.3.2二叉檢索樹的平衡性調整211; 7.3.3B樹和B+樹214; 7.4哈希檢索217; 7.4.1哈希檢索與哈希表217; 7.4.2哈希函式的構造方法218; 7.4.3地址衝突的消解策略220; 7.4.4哈希表的檢索算法及性能分析222; 習題7224; 上機實驗題226; 第8章排序及基本算法228; 8.1排序的基本概念228; 8.2插入排序229; 8.2.1直接插入排序230; 8.2.2希爾排序231; 8.2.3其他插入排序簡介234; 8.3交換排序237; 8.3.1冒泡排序237; 8.3.2快速排序238; 8.4選擇排序241; 8.4.1直接選擇排序241; 8.4.2樹型選擇排序242; 8.4.3堆排序243; 8.5歸併排序247; 8.5.1歸併相鄰兩個有序序列248; 8.5.2二路歸併排序的遞歸算法249; 8.5.3二路歸併排序的非遞歸算法249; 8.6基數排序250; 8.6.1多關鍵字排序250; 8.6.2鏈式基數排序251; 8.7各種內部排序方法的比較和選擇254; 8.8外部排序簡介256; 習題8258; 上機實驗題260; 參考文獻261

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

教學資源

• 配套教材
  

該教材有配套教材——《算法與數據結構習題精解與實驗指導（第2版）》。

書名	書號	出版社	出版時間	作者
《算法與數據結構習題精解與實驗指導（第2版）》	9787302276524	清華大學出版社	2012.03.01	寧正元、賴賢偉、寧靜

• 課程資源
  

該教材提供電子教案。

教材特色

該教材是針對套用型本科教學特點和需求編寫的課程教材之一，它覆蓋了《中國計算機科學與技術學科教程2002》中關於核心課程“算法與數據結構”的所有知識單元和課程提綱，介紹了各種常用數據結構的有關知識和各種基本的檢索排序算法。每章配有例題、習題和上機實驗題。

該教材強調算法與數據結構之間的聯繫，體現程式設計方法中抽象、枚舉、歸納三個原則的運用，反覆再現算法的複雜性、效率、折中、重用等重要概念，並增加了“數據結構的程式實現”一章內容。圍繞基本內容，除了增加“數據結構的程式實現”一章內容外，還介紹了一些同類其他書籍中沒有或很少討論的內容，如由層次序列和中序序列恢復二叉樹、黃金點檢索、精算點檢索、共享棧插入排序等。

作者簡介

寧正元，1957年生，男，陝西武功人，福建農林大學計算機與信息學院教授，主要研究方向為智慧型計算算法分析。

賴賢偉，1981年生，男，福建漳州人，碩士，福建農林大學計算機與信息學院助教，主要研究方向為多Agent系統、數理邏輯。