數據結構（簡體書）

《數據結構(本科)》共9章，依次介紹數據結構和算法的基本概念、線性表、棧和隊列、串、數組和廣義表、樹和二叉樹、圖、查找和排序算法等。附錄部分是相關章節的實驗內容。《數據結構(本科)》在教學內容上遵循少而精和重應用的原則。在敘述方法上力求深入淺出、通俗易懂。全書用C語言作為數據結構和算法的描述語言，使初學者和自學者易于掌握。《數據結構(本科)》可作為大中專院校計算機類專業及相關專業“數據結構”課程的教材，也可作為從事計算機工程和應用人員的參考書。

《數據結構(本科)》由中央廣播電視大學出版社出版。

“數據結構”是計算機專業的專業基礎課和主干課程之一。隨著計算機技術的發展和廣泛應用，本課程已經成為其他專業熱門的限選課和選修課。本書是根據中央廣播電視大學計算機科學與技術專業“數據結構”課程教學大綱的要求編寫的。
全書共分9章，第l章介紹有關數據結構和算法的基本概念，為以下章節的學習作準備。第2～7章由淺入深地討論了線性表、棧和隊列、串、數組和廣義表、樹及圖等基本的數據結構，并著重介紹了它們在計算機中的存儲方法和相關算法，使讀者對以上常用數據結構有一個基本的了解，并為具體應用打下良好基礎。第8-9章結合相關的數據結構，針對非數值算法中最常用的“查找”、“排序”算法的部分典型算例，介紹了算法的原理和具體實現方法。這兩章也是數據結構的一個初步應用。書中以c語言作為數據結構和算法的描述語言，給出了部分程序。讀者按照程序中的提示和注釋，在相應的運行環境中很容易改寫并運行相關程序。
針對廣播電視大學學生的特點和實際情況，“數據結構”課程更應該注重于應用，教學中要突出重點。所以本書在教學內容上遵循少而精和重應用的原則，略去了數據結構的形式定義、抽象數據類型等概念和內容。而對算法分析，則僅僅介紹了一些基本原理，并說明如何直觀地對算法進行評估。對現有部分教材中列出但不作教學要求的章節、帶*號的內容，本書均作了刪除。另外還刪改了部分較煩瑣但不影響本課程知識結構的內容。

1 緒論
1.1 數據結構的基本術語和概念
1.2 算法和算法分析簡介
1.2.1 算法
1.2.2 時間復雜度
1.2.3 空間復雜度
本章小結
習題

2 線性表
2.1 線性表的定義
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.4 線性表的鏈式存儲結構(鏈表)及相關操作
2.4.1 線性表的鏈式存儲的基本概念
2.4.2 單向鏈表
2.4.3 單向循環鏈表
2.4.4 雙向循環鏈表
2.5 一元多項式的存儲和加法運算
2.5.1 一元多項式和線性表
2.5.2 使用數組方式
2.5.3 使用鏈表方式
本章小結
習題

3 棧和隊列
3.1 棧
3.1.1 棧的定義
3.1.2 棧的基本運算
3.1.3 棧的順序存儲結構及基本操作
3.1.4 棧的鏈式存儲結構及基本操作
3.1.5 棧的應用
3.1.6 棧與遞歸
3.2 隊列
3.2.l隊列的定義
3.2.2 隊列的基本運算
3.2.3 隊列的順序存儲結構及基本操作
3.2.4 隊列的鏈式存儲結構及基本操作
3.2.5 隊列的簡單應用舉例
本章小結
習題

4 串
4.1 串的概念
4.1.1 串的定義
4.1.2 串的存儲結構
4.1.3 利用串初始化字符數組
4.1.4 利用二維字符數組保存存儲串
4.1.5 字符串的輸入和輸出
4.2 串的運算
4.3 串應用舉例
本章小結
習題

5 數組和廣義表
5.1 數組的定義
5.2 數組的順序存儲結構
5.3 矩陣的壓縮存儲
5.3.1 特殊矩陣
5.3.2 稀疏矩陣
5.4 廣義表
5.4.1 廣義表的定義和性質
5.4.2 廣義表的存儲結構
5.5 數組應用舉例
本章小結
習題

6 樹和二叉樹
6.1 樹的概念
6.1.1 樹的定義
6.1.2 樹的日常應用舉例
6.1.3 樹的表示
6.1.4 樹的基本術語
6.1.5 樹的性質
6.2 二叉樹的概念
6.2.1 二叉樹的定義
6.2.2 二叉樹的性質
6.3 二叉樹的存儲結構
6.3.1 順序存儲結構
6.3.2 鏈接存儲結構
6.4 二叉樹遍歷
6.4.1 二叉樹遍歷的概念
6.4.2 叉樹的遞歸遍歷算法
6.4.3 二叉樹的非遞歸遍歷算法
6.4.4 二叉樹的按層遍歷算法
6.5 二叉樹的其他運算
6.6 二叉樹運算的程序調試
6.7 哈夫曼樹
6.7.1 基本術語
6.7.2 構造哈夫曼樹
6.7.3 哈夫曼編碼
6.7.4 哈夫曼樹運算的程序調試
本章小結
習題

7 圖
8 查找
9 排序
附錄實驗
參考文獻

數據結構（data stmcture）是相互之間存在一種或多種特定關系的數據元素的集合。數據元素間的關系稱為結構。客觀事物之間存在著各種不同的聯系，但抽象為數據以後再來研究它們具有的共性關系就單純得多。數據結構研究這種關系的目的是要把數據合理、有效地存儲到計算機中進行處理，所以我們的著眼點放在諸如數據間的位置關系、數據間是否存在直接或間接的聯系等方面。例如一個班的學生名單表中，學生是一個接著一個排列的，就可以抽象為“一對一的線性結構”，而把它們隨機地記錄在筆記本上時，從位置上看就不存在任何關系，只是他們同屬于一個班級。又如某單位的上級單位與各個下級單位的關系、祖輩與後輩的關系就可以抽象為“一對多的樹形結構”。而諸如某城市中各個公交站點之間的關系、通訊線路上用戶之間的關系就可以用“多對多的圖狀結構”來描述。根據數據間的不同特性，通常有4類基本結構。