1、緒論：1. 數(shù)據(jù)結(jié)構(gòu)研究內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)，儲存結(jié)構(gòu)，基本操作運算的定義和實現(xiàn)。2. 基本概念和術(shù)語： (1).數(shù)據(jù)：對客觀事物的符號表示，在計算機科學(xué)中是所有能輸入到計算機中并能被計算機程序處理的符號的總稱。 （2）數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。也稱節(jié)點或記錄。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。 （3） 數(shù)據(jù)對象：是性質(zhì)相同（數(shù)據(jù)項個數(shù)和類型均相同）的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。（4） 數(shù)據(jù)結(jié)構(gòu)：簡稱DS，是數(shù)據(jù)元素和數(shù)據(jù)元素關(guān)系的集合。（5） 數(shù)據(jù)結(jié)構(gòu)中的“關(guān)系”描述的是數(shù)據(jù)元素之間的邏輯關(guān)系，因此又稱為邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)通常分為四種

2、基本類型：i. 集合結(jié)構(gòu)ii. 線性結(jié)構(gòu)iii. 樹結(jié)構(gòu)iv. 圖結(jié)構(gòu)（樹和圖也稱為非線性結(jié)構(gòu)）3. 儲存結(jié)構(gòu)a) 數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機內(nèi)存中的存儲方式，又稱物理結(jié)構(gòu)i. 順序存儲結(jié)構(gòu)-借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素間的邏輯關(guān)系。ii. 鏈式存儲結(jié)構(gòu)-借助指示元素存儲地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系。4. 邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的關(guān)系a) 存儲結(jié)構(gòu)是邏輯關(guān)系的映像與元素本身的映像，是數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)b) 邏輯結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的抽象算法設(shè)計-邏輯結(jié)構(gòu)算法實現(xiàn)-存儲結(jié)構(gòu) 5.數(shù)據(jù)類型 6. 算法a) 算法的定義：i. 是解決問題的步驟和方法。即為解決某一特定類型問題的有限

3、運算序列。7. 算法的特征a) 輸入b) 輸出c) 又窮性d) 可行性e) 確定性8. 評價一個算法一般從四個方面進行a) 正確性，必須利用數(shù)據(jù)進行算法測試。b) 可讀性，必須為算法增加豐富的注釋信息。c) 健壯性，必須利用非法數(shù)據(jù)對算法進行測試。d) 高效性，時間復(fù)雜度和空間復(fù)雜度都盡量低。時間復(fù)雜度是對算法速度的衡量；空間復(fù)雜度是對算法占用內(nèi)存量的衡量。時間復(fù)雜度和空間復(fù)雜度是一對矛盾，可以互相轉(zhuǎn)化。9. 算法效率的度量：a) 事后統(tǒng)計的方法b) 事前分析估算的方法10.算法的存儲量包括A 輸入數(shù)據(jù)所占空間 B 程序本身所占空間 C 輔助變量所占空間 若輸入數(shù)據(jù)所占空間只取決于問題本身，和

4、算法無關(guān)，則只需要分析除輸入和程序之外的輔助變量所占額外空間。 若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。 線性表1. 線性表結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是一對一的。2.注意：同一線性表中的元素必定具有相同特性！3. 特點：實現(xiàn)邏輯上相鄰-物理地址相鄰 實現(xiàn)隨機存取4. 線性表的順序存儲結(jié)構(gòu)定義-靜態(tài) #define MAXSIZE 100 Typedef struct ElemType elemMAXSIZE Int lengthSqList5. 動態(tài) #define LIST_INIT_SIZE 100/線性表存儲空間的初始分配量 #define LISTINCREMENT 10/線性表存儲空間的分配增量 Typedef struct ElemType