數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料

1、數(shù)據(jù)結(jié)構(gòu)(C+版)第一章緒論(1) 數(shù)據(jù)結(jié)構(gòu)+算法=程序(2) 數(shù)據(jù)的邏輯結(jié)構(gòu)：線性表，樹，圖 等數(shù)搖結(jié)構(gòu)。其核心是如何紐織待處理數(shù)據(jù)以 及數(shù)據(jù)之間關(guān)系。(3) 數(shù)據(jù)的存儲結(jié)構(gòu)：如何將線性表，樹，圖等數(shù)據(jù)結(jié)構(gòu)存儲到計算機的存儲器中，其核 心是如何有效的存儲數(shù)據(jù)以及數(shù)據(jù)之間的邏輯關(guān)系。(4) 常用數(shù)據(jù)處理技術(shù)：包括查找技術(shù)，排序技術(shù)，索引技術(shù)等(5) 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，構(gòu)成數(shù)據(jù)元素的不可分割的就小單位稱為數(shù)據(jù)項。(6) 數(shù)據(jù)結(jié)構(gòu)分為以下四類：集合(屬于同一集合)，線性結(jié)構(gòu)(一對一)，樹結(jié)構(gòu)(一對 多)，圖結(jié)構(gòu)(多對多)(7) 數(shù)據(jù)的存儲結(jié)構(gòu)又稱為物理結(jié)構(gòu)。(8) 抽象數(shù)據(jù)類型ADT:包括

2、數(shù)據(jù)元素間的邏輯關(guān)系和操作聲明(9) 算法必須滿足五個重要特性：輸入，輸出，有窮性，確定性，可行性(10) 算法的描述方法：自然語言，流程圖，程序設(shè)計語言，偽代碼(11) 算法的時間復(fù)雜度：算法中基本語句的執(zhí)行次數(shù)在漸進(jìn)意艾下的階，通常用0記號 表彷O(12) 算法的空間復(fù)雜度：算法的執(zhí)行過程中，需要的輔助空間數(shù)量。S (n)=0(f (n) n為問題規(guī)模第二章線性表(1) 線性表簡稱表，是n(n> = 0)個具有相同數(shù)據(jù)元素的有限序列，線性表中數(shù)據(jù)元素 的個數(shù)稱為線性表的長度。(2) 元素a1無前驅(qū)，元素a n無后繼，其他元素有且僅有一個前驅(qū)和一個后繼。(3) 線性表的存儲結(jié)構(gòu)稱為順序

3、表。(4) 順序表按位查找算法GetTemp I ate <cla s s DataT ype>Data T y p e Se q Li st <DataT y p e> :Get (i n t i)I f ( i < 1 && i>length) t how “查找位置非法“； Else retur n dat a iT;(5) 順序表按值查找算法LocateT e mp I ate<c I a s s Da t aTyp e >I n t SeqLi s tDataType> : :Loc a te (Dat a Typ

4、e x)For (i=0; i < le n gth ; i+)I f (d a tai=x) ret urn i+1;R eturn 0;(6) 順序表的存儲結(jié)構(gòu)單鏈表1 單鏈表的遍歷算法Pri ntLi s tTem p la t e<cI a ss Da t aT y p e>Vo i d L inkList<Da taType>: : Pr int L i st ()p= f i r s t->ne x t;whi I e (p! =NULL)Co u t«p>d ata;P=p> n e x t ;2 單儺表的按值僉找算法Lo

5、cateTemp I at e< c la s s D a taT ype>I nt LinkL i st<Da t aTy p e >: :L o cate (Da t aT y p e x)P=fr ist ->next ；count=1;Whi I e (p!二NULL)I f (p >data =x) ret u r n count;P= p ->nex t：Coun t+;r etu r n 0:3 單鏈表插入算法Inser tTemp I ate V c lass Da t a Type>Void Lin k L is t VData

6、T ype>: I n s ert (i nt i: D a ta T ype x) P = f i r st;c o un t =0;Whi I e (p!=NULL && count<i-1)P=p > next;Count+ i ;I f (p 二二 NULL) t hr ow “位置''；Else S=n e w Node;s->data = x;s ->ne x t=p>ne x t; p ->next= s ;4 尾赭法建立單鏈表Li n kListT e mp I at e < c I ass Da

7、t aT y p e >Lin k Lis t <D a ta T ype>:L i n k Lis t (Da taTyp e a , i n t n)Fi r st =new Node;R=f i r s t ;F o r (i =0; i <n; i +)s=new Node : s >data= a i;r-> n ex t =s;r=s：r-> n ext 二NULL;第三章棧和隊列(1) 棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表，允許插入和刪除的一端稱為棧頂, 另一端稱為棧底。后進(jìn)先出事棧的特性。(2) 棧的順序存儲結(jié)構(gòu)順序棧1 順序棧入

8、棧算法PushT emp I at e<c I ass Dat aTy p e >Void Se q Stac k <DataType>: Pu s h (Da t a Typex)If (to p =St a ckSi z e - 1 ) thow "上溢"；data + to p=x；2 順序棧出棧算法PopT em p I at e <clas s Da t a T yp e >If (top=-1) thow “上溢“；x = d a tatop:retun x;(3) 棧的鏈接存儲結(jié)構(gòu)一鏈棧棧的鏈接存儲結(jié)構(gòu)稱為縫棧。1 鏈棧入棧

9、算法PushTemp late <c I a ss Da t a Type>Vo i d LinkSt a c k <D a t aType>: P ush (DataT y pe x)S=new No d e ;s->da t a=x：S->next二top; t op=s;(4) 隊列的定狡:P人列是只允許在一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作的線性表。 允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。(5) 臥列的順序存儲結(jié)構(gòu)：循環(huán)隊列頭尾相接的順序存儲結(jié)構(gòu)稱為循環(huán)隊列。重要問題！隊空和隊滿的判定：隊空條件fro n t二rear隊滿條件(rea r

10、 + 1 )%Q u enu e S i z e =from1 循環(huán)隊列的入隊算法EnQueueT emp I a t e<c lass D a ta T ype>Vo i d C i r Queu e <DataType>: E nQue u e (DataT y pe x)I f ( ( r e a r + 1) %QueueSize=front) t hrow” 上溢"；Rear= (rea r+1) %Queu e S i z e ;D a tar e a r =x;2 循環(huán)隊列出隊算法DeQ ueueTemp I a t e<cI ass D

11、ata T ype>Da t aType Ci rQu e u e <Data T y p e>: DeQu e ue ()I f (r e ar=front) t h ro w"下溢”;F ront= (f r ont+ 1 )%Que u e Size;Return data f r o n t;(6) 隊列的鏈接存儲結(jié)構(gòu)稱為鏈隊列。第四章 字符串和多維數(shù)組(1) 字符串，簡稱串，是零個或者多個字符組成的有限序列。給定兩個字符串S = " s1,s2, sn”和T二“2,tn",在主串S中尋找子串T的過程稱為模式匹配.T稱為模式。1 樸素的模

12、式匹配算法BFI n t BF (char S , c h ar T )l=0;j=0;Whi I e (Si ! =' 0)&&(Tj" (r )lf(s i =T j)i+;j+Else (i = i-j+1;j=O;JI f (Tj = 0f ) re t u r n (i j+1);E I se retur n 0 ;第5章樹和二叉樹(1) 在樹中常將數(shù)扌居元素稱為結(jié)點。樹有且僅有一個稱為根的結(jié)點。(2) 菜結(jié)點所擁有的子樹的個數(shù)稱為該結(jié)點的度。(3) 樹的遍歷操作：1前序遍歷：訪問根結(jié)點，按照從左到右的順序祈序遍歷根結(jié)點的毎 一棵子樹。2后序遍歷：按

13、照從左到右的順序后序遍歷根結(jié)點的每一棵子樹，訪問根 結(jié)點。3層序遍歷：從樹的第一層開始，自上而下逐層遍歷，在同一層，按從左到右的 順序?qū)Y(jié)點逐個訪問。(4) 樹的存儲結(jié)構(gòu)：雙親表示法，孩子表示法，雙親孩子表示法，孩子兄弟表示法。(5) 二叉樹:是n個結(jié)點的有限集合，該集合或者為空集(稱為空二叉樹)，或者有一個根結(jié)點 和兩棵互不相交的，分別稱為根結(jié)點的左子樹和右子樹的二義樹組成。斜樹(每層只有 一個結(jié)點)滿二叉樹(葉子只能出現(xiàn)在最下一層，只有度為0和度為2的結(jié)點)完全二叉 樹(葉子結(jié)點只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點都集中在二叉樹的左側(cè)連續(xù)的 位置，如果有度為1的結(jié)點，只可能有一個，且該結(jié)

14、點只有左孩子。)(6) 二叉樹的基本性質(zhì)：1二叉樹的第i層上最多有2的(i-1)次方個結(jié)點。(i > = 1)2在一棵深度為k的二叉樹中，最多有2的k次方T個結(jié)點，最少有k個結(jié)點。3在一棵二叉樹中，如果葉子結(jié)點的個數(shù)為nO,度為2的結(jié)點個數(shù)為門2,則nO=n2+14具有n個結(jié)點的完全二叉樹的深度為I og2 n +1.(7) 二叉樹的遍歷操作：前序遍歷，中序適歷(中序遍歷根結(jié)點的左子樹，訪問根結(jié)點，中序 遍歷根結(jié)點的右子樹)后序遍歷，層序遍歷由二叉樹的后序序列和中序序列課唯一缺定一棵二叉樹，但是如果只知道二叉樹的前序序 列和后序序列，則不能唯一確定一顆二叉樹。(8) 二叉樹的存儲結(jié)構(gòu)及實

15、現(xiàn)二叉樹一般用二叉鏈表存儲：另二叉樹的每個結(jié)點對應(yīng)一個鏈表結(jié)點，鏈表除了存放與二叉 樹結(jié)點有關(guān)的數(shù)據(jù)信息外，還要設(shè)置指示左右孩子的指針。1二叉樹的前序遍歷遞歸算法PreOrderTem p I ate<class Da t aType>Vo i d B i T ree<DataType>: P r eOrder (B iNode< DataType>* b t)I f (bt=NULL) return;Else C o ut<< b t > d at a ;PreO r der (bt->lchiId);P reO r de r (b

16、t->rchi Id);2二叉樹中序遍歷遞歸算法I nOrde rTemp I ate c las sData T ype>Void B i T re e <D a taT ype>: I n e Orde r (BiNode<Da t aTyp e >*bt)If ( b t=NULL) r etu r n;Else InOrder (bt>lchi Id);Cout<<bt->d ata;InOrder ( b t->r child);3 二叉樹的后序遍歷算法PostOrd e rTempi at e<cla s sD

17、at a T yp e >Void BiTr e e <D a t aType>: PostOr d e r (B i T ree<DataTy p e >* b t )If (b t =NULL) return ;Else!Pos t 0rder(b t->lchiId);PostOrder (bt->r c h i I d );C o ut«b t ->Data;(9) 層序遍歷非遞歸隊列：設(shè)豈一個隊列存放已訪問結(jié)點，遍歷從二叉樹的根結(jié)點開始，首 先將根指針入隊，然后從隊頭取出一個元素并執(zhí)行下述操作：訪問該指針?biāo)附Y(jié)點，若該指針 所

18、指結(jié)點的左。右孩子結(jié)點非空，則將其左孩子指針和右孩子指針入隊。電復(fù)執(zhí)行直到隊列 為空。(10) 二叉樹遍歷的非遞歸算法：1前序遍歷非遞歸算法 PreOrderTern p I a t e<clas s Data T ype>Vo i d B iTre e <DataTyp e >:P r e Ord e r (B i T r ee<Da t aType> * b t)T op=- 1 ;While ( bt!二NULL| | t op!=-1)Whil e (bt!二NULL)Cou t «b t ->data;S4-+top=bt;Bt=b

19、t->I chi Id;I f (top! =- 1) Bt二stop;B t = b t ->rch i Id;(11) 樹，森林與二叉樹的轉(zhuǎn)換：樹轉(zhuǎn)換為二叉樹：1 加線樹中所有相鄰兄弟結(jié)點之間加一條連線；2 去線對樹中的每個結(jié)點，只保留它與第一個孩子結(jié)點之間的連線，刪去它與其他孩 子結(jié)點之間的連線。3 層次調(diào)螯以根結(jié)點為軸心，將樹順時針轉(zhuǎn)動一定得角度，使之層次分明樹的前序遍歷=二叉樹的詢序遍歷樹的后序遍歷=二叉樹的中序遍歷(12) 森林的遍歷：前序(根)遍歷和后序(根)遍歷前序遍歷森林即為前序遍歷森林里的每一棵樹； 后序遍歷森林即為后序遍歷森林里的每一棵樹。(13) 哈夫曼樹：

20、也稱最優(yōu)二叉樹，給定一組具有確定權(quán)值的葉子結(jié)點，可以構(gòu)造出不同的二 叉樹，將其中帶權(quán)路徑長度最小得二叉樹稱為哈夫曼樹。(1 4)前綴編碼：如果一組編碼中任一編碼都不是其他任何一個編碼的前綴，我們稱這紐編 碼為前綴編碼。前綴編碼保證了編碼被解碼時不會有多種可能。第六章 圖(1) 簡單圖：若不存在頂點到其自身的邊，且同一條邊不重復(fù)出現(xiàn)，則稱這樣的圖為簡單圖。(2) 頂點的度，入度，出度：在無向圖中，頂點V的度是指依附于該頂點的邊的個數(shù)，記 為TD (V)o入度是指以該頂點為弧頭的弧的個數(shù)記為ID(V)°出度是指以該頂點為弧尾 的弧的個數(shù)，記為OD (V)o(3) 圖的遍歷操作：深度優(yōu)先遍

21、歷，廣度優(yōu)先遍歷。深度優(yōu)先遍歷：訪問頂點V;從V的未被訪問的鄰接點中選取一個頂點W,從W出發(fā)進(jìn)行深度 優(yōu)先遍歷；重復(fù)上述兩步，直到圖中所有和V有路徑想通的頂點都被訪問到。廣度優(yōu)先遍歷：訪問頂點V;依次訪問V的各個未被訪問的鄰接點V 1 ,V2,Vk；分別從 V1,V2,Vk出發(fā)依次訪問它們未被訪問的鄰接點，并使“先被訪問頂點的鄰接點”先于 “后被訪問頂點的鄰接點”被訪問。直到圖中所有和V有路徑想通的頂點都被訪問到。(4) 鄰接矩陣：圖的鄰接矩陣存儲也稱數(shù)組表示法，其方法是用一個一唯數(shù)組存儲圖中頂點 的信息，用一個二維數(shù)組存儲圖中邊的信息(即各頂點之間的鄰接關(guān)系)，存儲頂點之間的鄰 接關(guān)系的二維

22、數(shù)組稱為鄰接矩陣。(5) 算法在鄰接矩陣存儲結(jié)構(gòu)下的實現(xiàn)：1深度優(yōu)先遍歷算法 D F STraverseT e mplate <class D ataType>Voi d MG r a p h<Data T y pe>: : DFSTraverse (i nt v )Cout« ver t e xv; v i s i t ed v=1;Fo r (j = 0; j <ver t e x N u m; j +)If (arcv j =1 && visite d j = O)DFSTra v e r se(j);2廣度優(yōu)先遍歷算法BFSTra

23、ver seT e mp late <c lassDataType>Void MG ra p h<DataTy p e> : BFSTra v e rse(int v)Fr o n t =rear = 1:Co u t«ver t ex v ; vi s i tedv =1; Q+rear= v ;While (front! =r e a r )V=Q+f r ont:For (j=0; j< v e r texNurn; j+)If (arc v j = = 1 && visitedj=0) Cout<<v e r t e

24、x j ;vi s it e dj =1 ;Q+rea r = j ;最小生成樹"殳G = (V, E)是一個無向聯(lián)通網(wǎng)，生成樹上冬邊的權(quán)值之和稱為該生成樹的 代價，在G的所有生成樹中代價最小的生成樹稱為靈小生成樹。第七章查找技術(shù)(1)靜態(tài)查找，動態(tài)查找：不涉入插入和刪除操作的查找稱為靜態(tài)查找。涉及插入和刪除操作 的查找稱為動態(tài)查找。(2) 查找時構(gòu)：面向査找操作的數(shù)據(jù)結(jié)構(gòu)稱為查找結(jié)構(gòu)。線性表:適用于靜態(tài)査找，主要采用順序查找技術(shù)，折半查找技術(shù)。樹表：適用于動態(tài)查找，主要釆用二叉排序樹的查找技術(shù)。散列表：赫態(tài)查找和動態(tài)查找均適用，主要采用散列技術(shù)。(3) 順序表的順序查找算法 Seq

25、SearchlS eqSearc h 1 ( i n t r , in t n, i nt k)R0 =k：l=n;Whi I e (ri !=k)i ；r etut n i ;(4) 折半查找：要求線性表中的記錄必須按關(guān)鍵碼有序，并且必須釆用順序存儲。一般只能 應(yīng)用于赫態(tài)查找。1折半查找非遞歸算法 B i n Search 1B i n Searc h 1 (i nt r , int n, int k)low=1 ;high = n;w h i I e ( I o w<=h i gh)mid=(low +high)/2;if (k<r mid) I ow= m id- 1 ;el

26、se if (k>r mid) low=mid+ 1 ; e I se return mi d ;2折半查找遞歸算法Bi n Sear ch2I nt Bin Sea r c h2(in t r , i n t low , int high , int k)rif (Iow>hi g h ) r et u r n 0;mid= (low+h i gh) return 0 ;i f (k< r mid) ret u rn BinS e a rc h 2 ( r , Iow, m i d- 1 , k ); else i f(k>r m i d) return Bin Search2 (r, mi d +1,h i gh,k) ; e I se return mid;(5) 二叉排序樹：又稱二叉查找樹它或者是一棵空的二叉樹，或者是具有以下性質(zhì)的二叉 樹：若它的左子樹不空，則左子