《數(shù)據(jù)結(jié)構(gòu)課程總結(jié)》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、課程總結(jié)(提要)一、數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型ADT定義：一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。構(gòu)成一個(gè)抽象數(shù)據(jù)類型的三個(gè)要素是：數(shù)據(jù)對象、數(shù)據(jù)關(guān)系、基本操作數(shù)據(jù)結(jié)構(gòu)(非數(shù)值計(jì)算程序設(shè)計(jì)問題中的數(shù)學(xué)模型)·邏輯結(jié)構(gòu)（描述數(shù)據(jù)元素之間的關(guān)系）線性結(jié)構(gòu)——線性表、棧、隊(duì)列、串、數(shù)組、廣義表非線性結(jié)構(gòu)——樹和森林、二叉樹、圖集合結(jié)構(gòu)——查找表、文件·存儲結(jié)構(gòu)（邏輯結(jié)構(gòu)在存儲器中的映象）按“關(guān)系”的表示方法不同而分：順序結(jié)構(gòu)—以數(shù)據(jù)元素在存儲器中的一個(gè)固定的相對位置來表示“關(guān)系”鏈?zhǔn)浇Y(jié)構(gòu)—以指針表示數(shù)據(jù)元素的“后繼”或“前驅(qū)”·基本操作(三類

2、)結(jié)構(gòu)的建立和銷毀查找——引用型操作（不改變元素間的關(guān)系）按“關(guān)系”進(jìn)行檢索按給定值進(jìn)行檢索遍歷——訪問結(jié)構(gòu)中的每一個(gè)數(shù)據(jù)元素，且對每個(gè)元素只訪問一次修改——加工型操作（改變元素間的關(guān)系）插入刪除更新（刪除+插入）8二、線性結(jié)構(gòu)·線性表和有序表——不同存儲結(jié)構(gòu)的比較順序表：可以實(shí)現(xiàn)隨機(jī)存取；O(1)插入和刪除時(shí)需要移動元素；O(n)需要預(yù)分配存儲空間;適用于“不常進(jìn)行修改操作、表中元素相對穩(wěn)定”的場合。鏈表：只能進(jìn)行順序存取；O(n)插入和刪除時(shí)只需修改指針;O(1)不需要預(yù)分配存儲空間;適用于“修改操作頻繁、事先無法估計(jì)最大表長”的

3、場合?！獞?yīng)用問題的算法時(shí)間復(fù)雜度的比較例如，以線性表表示集合進(jìn)行運(yùn)算的時(shí)間復(fù)雜度為O(n2),而以有序表表示集合進(jìn)行運(yùn)算的時(shí)間復(fù)雜度為O(n)·棧和隊(duì)列——數(shù)據(jù)類型的特點(diǎn)及其應(yīng)用范疇·串——和線性表的差異：數(shù)據(jù)對象不同（數(shù)據(jù)元素限定為單個(gè)字符）、基本操作集不同（串整體作為操作對象）、存儲結(jié)構(gòu)不同??串的模式匹配算法·數(shù)組——只有引用型的操作，∴只需要順序存儲結(jié)構(gòu)多維到一維的不同映象方法：以行序?yàn)橹餍颍ǖ拖聵?biāo)優(yōu)先）以列序?yàn)橹餍颍ǜ呦聵?biāo)優(yōu)先）·廣義表——多層次的線性結(jié)構(gòu)特性：次序性、長度、層次性、深度、遞歸等獨(dú)有的特性：共享存儲結(jié)構(gòu)的特

4、點(diǎn)8三、非線性結(jié)構(gòu)??樹和森林、二叉樹、圖·數(shù)據(jù)類型的定義(結(jié)構(gòu)特點(diǎn)和基本操作)·存儲結(jié)構(gòu)·二叉樹的特性及其證明方法·遍歷·何謂“遍歷”？對結(jié)構(gòu)中的每個(gè)元素都訪問到，且只被訪問一次·對非線性結(jié)構(gòu)的遍歷需要確定一條搜索路徑·兩條搜索路徑:深度優(yōu)先搜索和廣度優(yōu)先搜索·邏輯定義深度優(yōu)先搜索——以結(jié)構(gòu)中的某個(gè)數(shù)據(jù)元素為起始點(diǎn)，首先訪問該數(shù)據(jù)元素，然后依次以它的各個(gè)“后繼”為起始點(diǎn)進(jìn)行“深度優(yōu)先搜索遍歷”。其特點(diǎn)為：在訪問了起始數(shù)據(jù)元素之后，沿著某一條“路徑”(后繼)向前，直至“到底”，然后退回一步找另一個(gè)后繼，再向前繼續(xù)，……，直至所有通路都

5、走遍。廣度優(yōu)先搜索——以結(jié)構(gòu)中的某個(gè)數(shù)據(jù)元素為起始點(diǎn)，首先訪問該數(shù)據(jù)元素，然后先訪問其所有后繼；之后其它結(jié)點(diǎn)的訪問次序由已被訪問的結(jié)點(diǎn)的訪問次序決定：先被訪問的結(jié)點(diǎn)的后繼“優(yōu)先于”后被訪問的結(jié)點(diǎn)的后繼。其特點(diǎn)為：在訪問了起始數(shù)據(jù)元素之后，先訪問它的所有后繼，然后再依這些后繼被訪問的先后次序訪問它們的后繼，……，直至沒有后繼未被訪問為止?！に惴ǖ男问矫枋錾疃葍?yōu)先搜索——通常采用遞歸的形式二叉樹（先序、中序、后序）、樹/圖（先根、后根）一般形式算法的描述:8voidDFSearch(ADTDS,ElemTypev){//從v開始，對DS進(jìn)

6、行深度優(yōu)先搜索遍歷if(DS){visit(v);(visited[v]=true;)w=FirstSucc(v);while(w){if(!visited[v])DFSearch(DS,w);w=NextSucc(DS,v,w);}//while}//if}//DFSearch不同數(shù)據(jù)結(jié)構(gòu)(邏輯和存儲)有不同寫法。例如對森林，起始點(diǎn)只有一個(gè)(第一棵樹的根)，只有兩個(gè)后繼，且各棵樹互不相交，按搜索路徑上的訪問次序有先序遍歷和中序遍歷之分。voidPreOrder_F(CSTreeT){//對以T為根指針的森林進(jìn)行先序遍歷if(T){v

7、isit(T->data);PreOrder_F(T->firstchild);//先序遍歷第一棵樹的子樹森林PreOrder_F(T->nextsibling);//先序遍歷其余樹構(gòu)成的森林}//if}//PreOrder_F或者從森林是樹的集合角度來看遍歷(依次從左至右依次先根遍歷各棵子樹)while(樹)doPreOrder_T(樹);voidPreOrder_T(CSTreeT){8//對以T為根指針的樹進(jìn)行先根遍歷if(T){visit(T->data);p=T->firstchild;while(p){PreOrder_T

8、(p);//對以p為根指針的子樹進(jìn)行先根遍歷p=p->next;}//while}//PreOrder_T·由“訪問”操作的不同可以實(shí)現(xiàn)不同的操作具體問題具體分析，按分割求解的思想:“遞歸基”考慮最簡單的結(jié)構(gòu)（“空集”/