1.緒論：專門研究數(shù)據(jù)的特性和數(shù)據(jù)之間存在的關系琳骡，以及如何在計算機中有效地存取數(shù)據(jù)和處理數(shù)據(jù)〉驯“數(shù)據(jù)結構”是設計和實現(xiàn)編譯程序屎勘、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)和大型應用程序的重要基礎，它也是介于數(shù)學、計算機硬件和計算機軟件之間的一門核心課程。
1.1什么是數(shù)據(jù)結構 1.2算法和算法分析
2.線性表：線性表是實際應用中最基本捎琐、最簡單、最常用的一種數(shù)據(jù)結構裹匙，例如瑞凑，26個英文字母表(A, B, …, Z)就是一個線性表，表中的元素是單個字母概页。線性表的基本特點是籽御，數(shù)據(jù)元素之間具有一種線性關系，即除第一個元素外惰匙，集合中的每個元素均有且只有一個直接前驅元素技掏；除最后一個元素外，集合中的每個元素均有且只有一個直接后繼元素项鬼。
2.1線性表的類型定義 2.2線性表的順序存儲結構 2.3線性表的鏈式存儲結構 2.4線性表的應用–多項式相加與josephus問題
3.棧與隊列：棧與隊列是兩種特殊的線性表哑梳，它們的邏輯結構與線性表的邏輯結構相同，但在運算操作方面較線性表有更多的限制绘盟，它們是重要的線性數(shù)據(jù)結構鸠真，通常被稱為運算受限的線性表悯仙。在面向對象的程序設計中，它們是多型數(shù)據(jù)類型弧哎。
3.1棧 3.2棧的應用舉例 3.3棧與遞歸 3.4隊列
4.串：現(xiàn)實世界中的實體有多種形式雁比，如數(shù)值稚虎、文字符號序列撤嫩、圖形、圖像蠢终、聲音等序攘，其中文字（符號）序列稱為字符串，簡稱串寻拂。串是一種常用的數(shù)據(jù)結構程奠，用于描述非數(shù)值的簡單信息，它在現(xiàn)實世界中屢見不鮮祭钉，如人名瞄沙、產(chǎn)品名、事物名稱慌核、車牌號距境、文獻、源程序等垮卓。從數(shù)據(jù)元素間的邏輯關系看垫桂，串是線性表，但從操作方式與種類看粟按，它與線性表有許多不同诬滩。在計算機中，串被認為是一種特殊的線性表——元素為文字符號的線性表灭将。由于現(xiàn)實問題中經(jīng)常使用串疼鸟，所以對串應選擇合適的存儲結構，并提供靈活多樣的基本操作庙曙。
4.1串的邏輯結構 4.2串的存儲結構 4.3串函數(shù)與串的類定義 4.4串模式匹配 4.5串的應用–文本編輯
5.多維數(shù)組與廣義表：多維數(shù)組與廣義表均可看成是線性表的一種擴展愚臀，即表中的數(shù)據(jù)元素本身也是一個數(shù)據(jù)結構，元素的值是可再分解的矾利。它們的邏輯特征是姑裂，一個數(shù)據(jù)元素可能有多個直接前驅和多個直接后繼。盡管C++支持多維數(shù)組男旗，但它無法保證數(shù)組下標的合法性舶斧。同時，C++也未能提供數(shù)組的輸入察皇、輸出以及簡單的算術運算（如數(shù)組賦值和數(shù)組相加）茴厉。為了克服這些不足泽台，本章針對一維數(shù)組設計了類Array1D。
5.1數(shù)組 5.2類Array1D 5.3矩陣的存儲 5.4十字鏈表 5.5廣義表
6.樹結構和二叉樹：樹結構中每個元素最多只有一個前驅矾缓，但可能有多個后繼怀酷，體現(xiàn)出明顯的層次關系。
6.1樹的相關概念 6.2樹的存儲結構與遍歷 6.3二叉樹
7.圖：圖（Graph）是一種比樹更復雜的非線性結構嗜闻。在這種結構中蜕依，任意兩個結點之間都可能有關系，即結點之間的連接關系是任意的琉雳，因此圖可用來描述更復雜的數(shù)據(jù)對象样眠。圖在人工智能、數(shù)學翠肘、物理檐束、化學、電信束倍、生物和計算機科學等領域都有著廣泛的應用被丧。本章利用圖論的知識來討論如何在計算機上實現(xiàn)圖的操作，主要學習圖的存儲結構以及圖的操作實現(xiàn)等绪妹。 7.1圖的定義和術語 7.2圖的對象抽象模型 7.3圖的存儲結構 7.4圖的遍歷 7.5圖的連通性問題 7.6有向無環(huán)圖及其應用
8.查找：查找運算在各種數(shù)據(jù)結構中的使用頻率非常高甥桂，同時也是很多系統(tǒng)軟件及應用程序的核心功能。當要處理的數(shù)據(jù)量非常龐大時喂急，查找算法的效率就顯得更加重要格嘁，尤其對于一些實時查詢的應用。本章將系統(tǒng)地討論一種廣泛應用于實際問題的數(shù)據(jù)結構——查找表廊移，主要介紹查找表的基本概念和一些基本的查找算法糕簿。
8.1查找表的相關概念 8.2靜態(tài)查找表 8.3動態(tài)查找表 8.4哈希表
9.排序：查找運算在各種數(shù)據(jù)結構中的使用頻率非常高，同時也是很多系統(tǒng)軟件及應用程序的核心功能狡孔。當要處理的數(shù)據(jù)量非常龐大時懂诗，查找算法的效率就顯得更加重要，尤其對于一些實時查詢的應用苗膝。本章將系統(tǒng)地討論一種廣泛應用于實際問題的數(shù)據(jù)結構——查找表殃恒，主要介紹查找表的基本概念和一些基本的查找算法。
9.1排序的基本概念 9.2 插入排序 9.3交換排序 9.4選擇排序 9.5歸并排序 9.6基數(shù)排序 9.7內排序方法的比較和討論
10.文件組織和外排序：盡管數(shù)據(jù)管理技術早已從文件系統(tǒng)發(fā)展到數(shù)據(jù)庫系統(tǒng)辱揭，但因為文件系統(tǒng)是數(shù)據(jù)庫系統(tǒng)的基礎离唐，從專用、高效和系統(tǒng)軟件開發(fā)的角度來看问窃，文件系統(tǒng)仍有其不可取代的地位亥鬓。在數(shù)據(jù)處理方面，特別是事務型的軟件編制工作域庇，都涉及有關文件的知識嵌戈。通常覆积，將存儲在主存儲器（內存）中的記錄集合稱為表，存儲在輔助存儲器（外存）中的記錄集合稱為文件熟呛。如何有效地組織文件中的數(shù)據(jù)宽档，提供方便而高效的文件數(shù)據(jù)讀取方法，是本章所要討論的內容庵朝。
10.1外存儲器概述 10.2文件的基本概念 10.3順序文件 10.4索引文件 10.5 isam文件和vsam文件 10.6散列文件
10.7多關鍵字文件 10.8外部排序
11.貪婪算法：先從最優(yōu)化概念開始吗冤，然后介紹該算法在貨箱裝船問題、背包問題偿短、拓撲排序問題欣孤、二分覆蓋問題馋没、最短路徑問題昔逗、最小代價生成樹問題中應用時的求解方案 11.1最優(yōu)化問題 11.2算法思想 11.3應用
12.分而治之算法：它是一種對復雜問題進行分解并逐一解決的方法，在算法設計中也常用到篷朵。本章將重點介紹分而治之方法在解決最小最大問題勾怒、排序問題、選擇問題及計算幾何問題等方面的應用
13.動態(tài)規(guī)劃：
14.回溯：一種可靠的問題求解方法是對其所有的候選解進行逐一檢查声旺，以此來獲得所需要的解笔链。但當一個問題的候選解數(shù)量非常大（如指數(shù)級）時，上述方法不太適用腮猖，因為即便使用最快的計算機也只能解決規(guī)模很小的問題鉴扫。對候選解進行系統(tǒng)檢查的方法有多種，其中回溯法和分枝定界法是較常用的兩種方法澈缺，它們能夠避免對很大的候選解集合進行檢查坪创，同時也能夠保證在算法運行結束時找到所需要的解，因此它被稱為“通用解題法”姐赡。本章主要討論回溯方法莱预，這種方法被用來設計貨箱裝船、背包项滑、最大完備子圖等問題的求解算法
15.分支定界法：分枝定界法和前面介紹的回溯法相似依沮，也是在解空間中求出問題的解，但不同的是枪狂，分枝定界法一般采用廣度優(yōu)先或最小耗費方法來搜索解空間的樹結構危喉。本章通過采用與第14章相同的應用例子來進行討論，以便更容易地比較分枝定界法與回溯法的異同州疾。相對而言辜限，分枝定界法的解空間比回溯法的大得多，因此當內存容量有限時孝治，回溯法成功的可能性更大列粪。
