第1章緒論

1．1數據結構的基本概念

1．1．1數據結構的定義與研究對像

1．1．2數據結構在程序設計中的作用

1．1．3邏輯結構與存儲結構

1．2抽像數據類型與C 類

1．2．1抽像數據類型的基本概念

1．2．2設計與實現: 無人駕駛汽車

1．3算法與算法分析

1．3．1算法的基本概念

1．3．2算法描述的工具

1．3．3算法評價與漸進復雜度思想

1．3．4算法的復雜度分析

1．4本章小結

本章習題

擴展閱讀: 唐納德·歐文·克努特和他的天書

第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．3．5循環鏈表

2．3．6靜態鏈表

2．4順序表與鏈表的比較

2．5可怕的死亡遊戲

2．5．1一維數組

2．5．2順序表

2．5．3循環鏈表

2．5．4數學建模

2．6本章小結

本章習題

擴展閱讀: 復雜繫統的計算機仿真方法

目錄

數據結構與算法——C 實現（微課視頻版）
第3章棧和隊列

3．1引言

3．2棧

3．2．1棧的定義

3．2．2棧的順序存儲結構及其實現

3．2．3兩棧共享空間

3．2．4棧的鏈接存儲結構及其實現

3．3隊列

3．3．1隊列的定義

3．3．2隊列的順序存儲結構及其實現

3．3．3雙端隊列

3．3．4隊列的鏈接存儲結構及其實現

3．4棧和隊列的應用

3．4．1數制轉換

3．4．2函數的調用與遞歸

3．4．3表達式求值

3．4．4魔王語言翻譯官

3．5本章小結

本章習題

擴展閱讀: 排隊論

第4章串和數組

4．1引言

4．2字符串與模式匹配

4．2．1字符串的邏輯結構

4．2．2字符串的存儲結構

4．2．3模式匹配

4．3數組和矩陣的壓縮存儲

4．3．1數組與矩陣

4．3．2特殊矩陣的壓縮存儲

4．3．3稀疏矩陣的壓縮存儲

4．4本章小結

本章習題

擴展閱讀: 暴力破解

第5章樹和二叉樹

5．1引言

5．2樹與樹的存儲結構

5．2．1樹的基本概念

5．2．2樹的邏輯結構

5．2．3樹的存儲結構

5．3二叉樹的邏輯結構

5．3．1二叉樹的基本概念

5．3．2二叉樹的基本性質

5．3．3二叉樹的抽像數據類型

5．3．4二叉樹的遍歷

5．3．5二叉樹的構造

5．4二叉樹的存儲結構

5．4．1順序存儲結構

5．4．2鏈式存儲結構

5．4．3線索鏈表

5．5樹、森林和二叉樹的轉換

5．5．1樹和二叉樹的對應關繫

5．5．2樹、森林和二叉樹的相互轉換

5．5．3樹、森林和二叉樹遍歷操作的關繫

5．6哈夫曼樹和哈夫曼編碼

5．6．1哈夫曼樹的定義

5．6．2哈夫曼樹的構造

5．6．3前綴編碼和哈夫曼編碼

5．7本章小結

本章習題

擴展閱讀: 樹結構的設計模式——組合模式

第6章圖

6．1引言

6．2圖的定義和基本概念

6．2．1圖的定義

6．2．2圖的基本概念

6．2．3圖的抽像數據類型

6．3圖的存儲

6．3．1鄰接矩陣

6．3．2鄰接表

6．4圖的遍歷

6．4．1深度優先遍歷

6．4．2廣度優先遍歷

6．5圖的典型應用

6．5．1小生成樹

6．5．2短路徑

6．5．3有向無環圖及其應用

6．6本章小結

本章習題

擴展閱讀: 艾茲格·W.迪傑斯特拉

第7章查找

7．1查找的基本概念

7．2線性表的查找

7．2．1順序查找

7．2．2折半查找

7．3樹表的查找技術

7．3．1二叉排序樹

7．3．2平衡二叉樹

7．4散列表

7．4．1散列表的概念

7．4．2常用的散列函數

7．4．3處理衝突的方法

7．4．4散列表的查找分析

7．5B樹

7．5．1B樹的概念與查找

7．5．2B樹的插入、構造和刪除

7．6本章小結

本章習題

擴展閱讀: 啟發式搜索算法

第8章排序

8．1排序的基本概念

8．2插入排序

8．2．1直接插入排序

8．2．2希爾排序

8．3交換排序

8．3．1冒泡排序

8．3．2快速排序

8．4選擇排序

8．4．1簡單選擇排序

8．4．2堆排序

8．5歸並排序

8．6分配排序

8．6．1桶式排序

8．6．2基數排序

8．7本章小結

本章習題

擴展閱讀: 影響世界進步的十大經典算法

“數據結構”課程是計算機及相關專業的核心課程，主要學習如何將實際工程問題轉化為計算機可以描述、存儲和解決的問題，並編程實現。該課程理論和實踐緊密結合，對學生的綜合素質要求較高。教學過程中發現，多數學生對數據結構的理論知識掌握較好，但實際動手編程實現能力不足，運用能力較差; 代碼編寫較為隨意，導致代碼晦澀、調試困難，進而影響了學習積極性。針對上述問題，本書以學生為本，以工程應用為導向，具有以下幾個特色。
(1) 理論聯繫實際，引入典型的工程應用問題，分析其中涉及的數據結構，並給出案例的分析過程及代碼實現。各個環節緊密銜接，實現了理論和實踐的有機結合。
(2) 采用面向對像設計方法，用規範的UML語言對數據結構和算法進行描述，並注重代碼風格，便於代碼閱讀和調試，也為學生畢業後適應公司代碼規範化要求打好基礎。
(3) 為拉近與學生的距離，激發其學習興趣，部分內容引入網絡流行用語和深入淺出的例子，以輕松詼諧的方式介紹復雜的理論知識。利用二維碼方式提供課件和教學視頻等資源，將紙質教材和電子資源融為一體，更利於讀者對所學知識融會貫通。
(4) 每章後增加了擴展閱讀的內容，對章節知識進行一定的拓展，或者介紹科學家的事跡，激發學生的學習興趣，引導學生對更深、更新層次的知識進行探索。 
本書共分為8章，重點介紹線性表、樹和圖三類基本數據結構，並講解常用的查找和排序算法，培養學生的算法分析能力。第1章主要介紹數據結構和算法的基本概念，包括數據結構和算法在程序設計中的作用、抽像數據類型、面向對像建模的基本思路、算法描述的常用方法、算法分析的思想和時間復雜度的計算等內容。其中，算法的時間復雜度是本章的重點和難點。第2章重點介紹種基本數據結構——線性表，包括線性表的基本知識以及線性表的順序存儲結構和鏈接存儲結構的實現，並擴展到雙向鏈表、循環鏈表和靜態鏈表等相關知識，向讀者展示了不同數據結構對程序的影響。其中，單鏈表是本章的重點。第3章介紹兩類特殊的線性表——棧和隊列，包括棧和隊列的特性以及順序存儲結構和鏈接存儲結構的實現。棧是限定在一端進行插入和刪除操作的線性表; 隊列是限定在一端插入，另一端刪除的線性表。本章還介紹了棧在函數遞歸調用中的作用和表達式求值等知識。其中，表達式求值是本章的難點。第4章介紹另外兩類特殊的線性表——串和數組，包括字符串的存儲、數組的尋址、稀疏矩陣和特殊矩陣的壓縮存儲，以及串的兩種模式匹配算法BF算法和KMP算法等內容。其中，模式匹配是本章的難點。第5章介紹第二種基本數據結構——樹和二叉樹，包括樹和二叉樹的邏輯結構和存儲結構，樹、森林和二叉樹的轉換，以及樹的典型應用——哈夫曼樹和哈夫曼編碼。其中，二叉鏈表是本章的重點。第6章介紹第三種基本數據結構——圖，包括圖的定義和基本概念、圖的存儲、圖的遍歷、圖的典型應用（小生成樹、短路徑、有向無環圖的應用、AOV網和AOE網）。其中，圖的存儲、小生成樹和短路徑算法是本章的重點和難點。第7章介紹線性表和樹表的查找方法，包括順序查找、折半查找、二叉排序樹、平衡二叉樹、散列表和B樹等重要的查找算法。其中，平衡二叉樹是本章的難點。第8章介紹幾類重要的排序算法，包括插入、交換、選擇、歸並和分配等排序算法，其中，快速排序和堆排序是本章的重點。
本書重點培養學生使用數學和計算機方法解決實際生活中的各種復雜工程問題的能力，包括： ①培養學生應用數學和計算機方法對計算機領域的復雜工程問題進行識別、表達和分析的能力; ②設計和開發滿足特定需求的解決方案; ③學習使用數據存儲和數據處理的重要技術和方法，並理解不同存儲方法在解決實際問題時的優勢和局限性; ④初步培養學生評價一個問題的解決方案對社會、安全、法律及環境的影響的能力; ⑤通過課程設計和專題研究等教學環節，還可以培養學生的團隊合作和溝通表達能力。
本書銜接C 程序設計或者面向對像程序設計課程，並建議讀者具備離散數學的基本知識。在學習本書之前，讀者需要掌握基本的C 程序設計能力，了解類、函數、數組、遞歸、指針和模板等知識。本書將頻繁使用，並幫助讀者熟練掌握這些知識。
本書由長期從事“數據結構”課程本科教學工作的團隊負責編寫，每位老師都有10年以上的“數據結構”課程教學經驗。本書由慕晨老師統稿，安毅生老師組織。其中，第1章和第6章由慕晨老師編寫，第2章和第3章由張淼艷老師編寫，第4章和第5章由公維賓老師編寫，第7章和第8章由周琳老師編寫。研究生王春利、陳茹夢、孫靖、朱明明等同學參與了繪圖、校稿和代碼調試工作，在此表示感謝。
由於作者水平有限，本書雖經仔細斟酌，不當之處仍在所難免，敬請各位讀者批評指正。
作者
2022年3月