第0章緒論 2
一、 基礎知識 2
第1章線性表 3
一、 基礎知識和演算法 3
1. 線性表及其特點 3
2. 順序表——線性表的順序儲存結構 3
3. 單鏈表——線性表的鏈式儲存結構之一 6
4. 迴圈鍊錶 10
5. 雙向迴圈鍊錶 11
6. 順序表與單鏈表的比較 12
第2章棧和佇列 13
一、 基礎知識和演算法 13
1. 棧 13
2. 鏈棧 13
3. 順序棧 14
4. 佇列 15
5. 鏈佇列 16
6. 迴圈佇列 16
7. 棧和佇列比較 18
8. 簡化的棧和佇列結構 19
9. 棧和佇列的應用 19
第3章串 19
一、 基礎知識和演算法 19
1. 概念 19
2. 串的基本操作 19
3. 串的儲存結構 20
二、 習題 20
第5章樹和二叉樹 20
一、 基礎知識和演算法 20
1. 樹及有關概念 20
2. 二叉樹 20
3. 二叉樹的性質 21
4. 二叉樹的儲存結構 21
5. 二叉樹的五種基本形態 22
6. 遍歷二叉樹 22
7. 遍歷二叉樹的應用 24
8. 線索二叉樹 24
9. 樹和森林 25
10. 赫夫曼樹及其應用 26
第6章圖 28
一、 基礎知識和演算法 28
1. 圖的有關概念 28
2. 圖的儲存結構 28
3. 圖的遍歷 30
4. 最小生成樹 32
5. 關鍵路徑 33
6. 最短路徑 34
二、 習題 35
概念和術語(黑體字部分)。
另外，注意：
1、資料元素是資料的基本單位。p4
2、資料項是資料不可分割的最小單位。p5
3、資料結構及其形式定義。p5
四種基本結構：①集合②線性結構③樹形結構④圖（網）狀結構
4、資料結構的
邏輯結構（抽象的，與實現無關）
物理結構（儲存結構） 順序映像（順序儲存結構）位置「相鄰」
非順序映像（鏈式儲存結構）指標表示關係p6
5、資料型別 p7
抽象資料型別（adt）p7
adt=（資料物件，資料關係，基本操作）
adt細分為原子型別，固定聚合，可變聚合型別。p8
6、演算法的概念 p13
7、演算法的五個特徵
①有窮性 ②確定性 ③可行性 ④輸入（0個或多個） ⑤輸出（1個或多個）
8、演算法設計的要求：①正確性②可讀性③健壯性④效率與低儲存量
其中正確性的四個層次（通常要求達到c層）。
9、演算法的時間複雜度 p15
常見有： o(1)，o(n)，o(n2)，o(log2n)，o(n log2n)，o(2n)
語句頻度，用歸納法計算。
10、演算法的空間複雜度 p17
線性表及其特點
線性表是n個資料元素的有限序列。
線性結構的特點： ①「第乙個」 ②「最後乙個」 ③前驅 ④後繼。
特點a) 邏輯上相鄰的元素在物理位置上相鄰。
b) 隨機訪問。
型別定義
簡而言之，「陣列+長度」。
const int maxsize = 線性表最大長度;
typedef struct sqlist;
注：a) sqlist為型別名，可換用其他寫法。
b) datatype是資料元素的型別，根據需要確定。
c) maxsize根據需要確定。如
const int maxsize=64;
d) 課本上的sqlist型別可在需要時增加儲存空間，在上面這種定義下不可以。(這樣做避免了動態記憶體分配，明顯減少了演算法的複雜程度，容易理解。而且，原來pascal版本的《資料結構》（嚴蔚敏）就是這樣做的。
)e) 課本上的sqlist型別定義中listsize表示已經分配的空間大小（容納資料元素的個數）。當插入元素而遇到l.length==l.
listsize時，用realloc (l.elem, l.listsize+增量) 重新分配記憶體，而realloc()函式在必要的時候自動複製原來的元素到新分配的空間中。
基本形態
順序表空
條件 l.length==0
不允許刪除操作
順序表滿
條件 l.length==maxsize
不允許插入操作
不空也不滿
可以插入，刪除
基本演算法——遍歷
順序訪問所有元素
for ( i=0; i visit ( l.elem[i] );
查詢元素x
for ( i=0; i if ( l.elem[i]==x ) break;
if ( i 找到;
else
未找到;
插入演算法 listinsert(&l,i,x)
前提：表不滿
合理的插入範圍：1≤i≤l.length+1
注：位序i在c/c++中對應於下標i-1。
步驟 第i至最後所有元素後移乙個元素
在第i個位置插入元素x
表長增1
演算法bool listinsert ( sqlist& l, int i, datatype x )
刪除演算法 listdelete(&l,i,&x)
前提：表非空
合理的刪除範圍：1≤i≤l.length
步驟取出第i個元素
第i個元素之後的元素向前移動乙個位置
表長減1
演算法bool listdelete ( sqlist& l, int i, datatype& x )
其他演算法
initlist (&l), clearlist (&l)
l.length = 0;
listempty (l)
return l.length == 0;
listlength (l)
return l.length;
getelem (l, i, &e)
e = l.elem[i-1];
概念線性鍊錶，單鏈表，結點；資料域，指標域；頭指標，頭結點。
特點用指標表示資料之間的邏輯關係（邏輯相鄰的元素物理位置不一定相鄰）。
型別定義
簡而言之，「資料 + 指標」。
typedef struct lnode {
資料結構實驗內容 20131009
資料結構實驗 內容 2012級電腦科學與技術 一 實驗名稱 線性表的鏈式儲存 二 實驗學時 2學時 第7周 三 實驗目的 1.掌握單鏈表的結構特性和基本操作演算法 2.利用指標來實現單鏈表的建立 輸出 插入和刪除。四 實驗內容 步驟 1.建立單鏈表 2.遍歷單鏈表 3.在第i個元素前插入乙個元素e ...
資料結構與拓撲資料結構
資料結構在gis中對於資料的採集 儲存 查詢 檢索和應用分析等操作方式有著重要的影響，一種高效率的資料結構應該具備以下幾個要求 1 組織的資料能夠表示要素之間的層次關係，便於不同資料聯絡於覆蓋 2 正確反映地理實體之間的空間排列方式和各實體之間的相互關係 3 便於訪問與檢索 4 節省儲存空間，減少資...
資料結構個人總結
第一章複習題 一 選擇 1 計算機演算法指的是 1 它必須具備 c 2 這三個特性 b 1 a 計算方法 b.排序方法 c.解決問題的步驟序列 d.排程方法 2 a 可執行性 可移植性 可擴充性 b.可執行性 確定性 有窮性 c.確定性 有窮性 穩定性d.易讀性 穩定性 安全性 2 下面關於演算法說...