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

1、數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí)資料 (完整版 )2018數(shù)據(jù)結(jié)構(gòu)回顧第 1 章簡介1.1 數(shù)據(jù)結(jié)構(gòu)的定義和分類1。數(shù)據(jù)結(jié)構(gòu)的定義 數(shù)據(jù)結(jié)構(gòu)是一門研究計(jì)算機(jī)操作對象、它們之間的關(guān)系以及在非數(shù) 值計(jì)算編程問題中的操作的學(xué)科2。數(shù)據(jù)結(jié)構(gòu)中包含的內(nèi)容(1) 邏輯結(jié)構(gòu) :數(shù)據(jù)元素之間的邏輯關(guān)系(2) 存儲結(jié)構(gòu) :計(jì)算機(jī)內(nèi)存中數(shù)據(jù)元素及其關(guān)系的表示 (3)操作 :數(shù)據(jù)操作 (檢索、排序、插入、刪除和修改 )為什么1.2 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)1。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的功能(1) 計(jì)算機(jī)中的數(shù)值運(yùn)算依賴于方程，而不是數(shù)值運(yùn)算 (如表、樹、圖 等)。)依賴于數(shù)據(jù)結(jié)構(gòu) (2)同一數(shù)據(jù)對象，用不同的數(shù)據(jù)結(jié)構(gòu)表示，在 運(yùn)行效率上可能有明顯的差異(3

2、) 編程的本質(zhì)是為實(shí)際問題選擇一個好的數(shù)據(jù)結(jié)構(gòu)和設(shè)計(jì)一個好 的算法。然而，一個好的算法在很大程度上取決于描述實(shí)際問題的數(shù) 據(jù)結(jié)構(gòu)。2。電話號碼查詢問題(1) 一個好的搜索算法取決于該表的結(jié)構(gòu)和存儲。 (2)電話號碼表的結(jié) 構(gòu)和存儲方式?jīng)Q定了搜索 (算法 )的效率1.3 算法1 的概念和特點(diǎn)。算法 算法的概念和特征是由幾條指令組成的有限序列，并且具有以下特 征:(1)輸入:具有 0 個或更多輸入的外部量 (2)輸出:至少生成一個輸出(3)很差:必須限制每條指令的執(zhí)行次數(shù) (4)確定性 :每條指令的含義必 須清晰明確 (5)可行性 :每條指令的執(zhí)行時間是有限的。2。算法和程序的區(qū)別(1) 一個程序

3、可能不滿足有限性，但算法必須(2) 程序中的指令必須是機(jī)器可執(zhí)行的，并且算法沒有這樣的限制。(3) 如果用機(jī)器可執(zhí)行語言描述，算法就是程序1/621.4 算法分析1。時間復(fù)雜度算法中基本運(yùn)算的重復(fù)次數(shù)是問題規(guī)模 n的函數(shù)，用 T(n)表示。如果 存在輔助函數(shù) f(n) ，使得當(dāng) n 接近無窮大時， T(n)/f(n) 的極限值是不 等于零的常數(shù)，那么 f(n)是與 T(n) 數(shù)量級相同的函數(shù) T(n)=O(f(n) ， O(f(n)是算法的漸近時間復(fù)雜度，縮寫為時間復(fù)雜度。算法的效率由 時間復(fù)雜度來衡量。常用函數(shù)的時間復(fù)雜度按數(shù)量和增長率的升序排列 :常數(shù)階 O(1) 對數(shù)階 O(log2n)

4、 線性階 O(n)線性對數(shù)階 O(n log2n)2 平方階 O(n)3 立方階 O(n).kk 次冪 O(n)n次冪 O(2)2。空間復(fù)雜度空間復(fù)雜度是算法在計(jì)算機(jī)中執(zhí)行時所需存儲空間的度量，記錄 為:S(n) = O(f(n)3。算法分析 的目的是選擇合適的算法并改進(jìn)算法1.5例例 1:為(I = 1；不精確= p； 否則如果 (t-> next = = NULL) t-> next = p ；p->下一個 =空；否則p-> next = t-> next；t-> next = p； (3)刪除void(link list * head) link li

5、st p ，q； p = headwhile (p->next ！=NULL)if (p-> 數(shù)據(jù)！ =p->下一個 ->數(shù)據(jù))p=p->下一個；否則 q = p-> next ；p-> next = q-> next；自由(q)；(4) 反向無效反向 (linklist * head) linklist * s ，* t，* p；p = heads = p->下一 個；while(s->next！=空) t = s->下一個； s-> next = p；p = s。s = t。 s-> next = p；頭->

6、;下一個 ->下一個 =空； head-> next = s；5/622.3 示例示例 1:一維數(shù)組 m，下標(biāo)范圍為 0到 9，每個數(shù)組元素存儲有相鄰的5 個字節(jié)內(nèi)存由字節(jié)尋址。如果存儲陣列元件的第一個字節(jié)的地址是 98，那么 3 的第一個字節(jié)的地址是 113示例 2:在長度為 n的序列表中， 當(dāng)在第 I 個元素(1 i n+之1)前插入新元素時，需要向后移動第 n-i+1 個元素(或者需要向前移動第 n-i個元素以刪除第 I 個元素)示例 3:如果 *p 節(jié)點(diǎn)不是單個鏈表中的結(jié)束節(jié)點(diǎn)，在它之前或之后插入 *s 節(jié)點(diǎn)或刪除節(jié)點(diǎn)的操作是什么？解決方案 :在其前面插入 *s 節(jié)點(diǎn) :s

7、-> next = p-> next；p-> next = s； t=p->數(shù)據(jù)； p->數(shù)據(jù)=s->數(shù)據(jù)； s->數(shù)據(jù)= t；在之后，插入 *s 節(jié)點(diǎn):s-> next = p-> next；p-> next = s；刪除前一個節(jié) 點(diǎn):需要通過遍歷: q = p->next 刪除后一個節(jié)點(diǎn)； p-> next = q-> next；自由 (q) ； 刪除自己的節(jié)點(diǎn) :q = p-> next；p->數(shù)據(jù)= q->數(shù)據(jù)；p-> next = q-> next； 自由(q)；例 4: 在以

8、下線性表的存儲結(jié)構(gòu)中，讀取指定序列號所需時間最少的 元素是序列結(jié)構(gòu)第 3 章堆棧和隊(duì)列3.1 堆棧和隊(duì)列的基本概念1。堆棧概念 堆棧是一個線性表，只允許在同一側(cè)進(jìn)行插入和刪除操作允許插入 和刪除的一端稱為棧頂， 另一端稱為棧底。 當(dāng)堆棧中沒有數(shù)據(jù)元素時， 它被稱為空堆棧。它具有先進(jìn)先出或后進(jìn)先出的特點(diǎn)2。堆棧(1) 順序堆棧typedef int 數(shù)據(jù)類型的定義； #定義 MAXSIZE 100 typedef 結(jié)構(gòu) 數(shù)據(jù)類型數(shù)據(jù) MAXSIZE ；int top； seqstack。seqstack * s；(2) 鏈接堆棧typedef int 數(shù)據(jù)類型； typedef 結(jié)構(gòu)節(jié)點(diǎn) 數(shù)據(jù)類

9、型數(shù)據(jù)；結(jié)構(gòu)節(jié)點(diǎn) * next linkstacklinkstack * toptop 是唯一確定鏈棧的棧頂指針當(dāng) top =空時，鏈接棧為空鏈棧中的 節(jié)點(diǎn)是動態(tài)生成的，沒有考慮溢出問題。3。順序堆棧操作(1) 確定堆棧為空。 s 頂部 = 0)；6/62(2) 空堆棧void set null(seqtack * s)s top =-1；(3) 判斷堆棧已滿int full(seqtach * s)return(s top = = maxsize-1)； (4) 推入堆棧seqtack * push (seqtack * s，data typex) if(full(s) printf( 堆棧

10、“溢出 ”；)返回空值； s top +;s 數(shù)據(jù) s 頂部 = x； 返回 s； (5)按下datatype pop(seq tach * s)if( 空的)printf( “ stack underflo；w返回”空)值；頂部-；年收益(s 數(shù)據(jù)s 排名+1) ；(6)獲取堆棧的頂部data typetop(seqtach * s)if(empty(s)printf( 堆“棧為空 ”；)返回空值；返回(s 數(shù)據(jù)s 頂部)；4。鏈接棧操作(1) 推棧鏈接棧*推棧(鏈接棧*頂部，數(shù)據(jù)類型 X) 鏈接棧* P；p =(link stack *)malloc(size of(link stack)

11、 ；p-數(shù)據(jù)= x ；p-下一個= 頂部；返回 p；/* 返回新的堆棧頂部指針 */ (2) 堆棧外LinkStack * PopStack(LinkStack * Top，數(shù)據(jù)類型 * data)7/62LinkStack * p ；if (top=NULL) printf( 欠“流”；)返回空值； 數(shù)據(jù)=頂部->數(shù)據(jù)； /* 堆棧的頂部節(jié) 點(diǎn)數(shù)據(jù)存儲在 * data */p = top 中；top = top-> next；免費(fèi) (p)；9 年返回頂部； /* 返回新的堆棧頂部指針 */5。隊(duì)列隊(duì)列的概念也是一個具有有限操作的線性表只允許在表的一端插 入，允許在另一端刪除。允許

12、刪除的一端稱為前端，允許插入的一端 稱為后端。它具有先進(jìn)先出的特點(diǎn)6。隊(duì)列(1)順序隊(duì)列#定義 MaxSize 100TypeDef 結(jié)構(gòu) DataType數(shù)據(jù) MaxSize ；內(nèi)部陣線；內(nèi)部后部； sequeue sequeue * sq；(2) 鏈隊(duì)列typedef structqueuenode data type dat；astruct queue node * nex；t 隊(duì)列節(jié)點(diǎn)； typedef 結(jié)構(gòu)QueueNode * front；隊(duì)列節(jié)點(diǎn) *后部； 鏈接隊(duì)列；7。循環(huán)隊(duì)列(1)假溢出在入隊(duì)和出隊(duì)操作期間，頭指針和尾指針只增加而不減少，導(dǎo)致已 刪除元素的空間永遠(yuǎn)不會被重用雖

13、然隊(duì)列中元素的實(shí)際數(shù)量比向量 空間的規(guī)模小得多， 但尾部指針也有可能超出向量空間的上限， 無法 排隊(duì)。這種現(xiàn)象被稱為假溢出 (2)循環(huán)隊(duì)列引入循環(huán)隊(duì)列的概念來解決假溢出問題在循環(huán)隊(duì)列中的隊(duì)列輸出和 隊(duì)列輸入操作期間，頭指針和尾指針仍然需要增加 1 才能向前移動。 然而，當(dāng)頭指針和尾指針指向向量的上限 (MaxSize-1)時，其加 1 運(yùn)算 的結(jié)果是指向向量的下限 0(3) 當(dāng)團(tuán)隊(duì)為空且已滿時， 進(jìn)入團(tuán)隊(duì)，尾部指針趕上頭部指針。當(dāng)離開隊(duì)伍時，頭指針追上尾 指針。因此，當(dāng)團(tuán)隊(duì)是空的和滿的時候，頭指針等于尾指針。無法通 過 sq-> front = = sq->原因來判斷隊(duì)列是空的還是

14、滿的至少有兩種方法來解決這個問題 :1，和另一個布爾變量來區(qū)分空隊(duì)列和滿隊(duì)列；2，以少一個元素空間為代價(jià)， 在進(jìn)入團(tuán)隊(duì)之前， 測試尾部指針 sq-> reason+1 = = sq-> front，如果相等，則認(rèn)為該團(tuán)隊(duì)已滿 (4)常見操作 團(tuán)隊(duì)空判斷 :sq->front = sq-> rear團(tuán)隊(duì)滿判斷 :sq-> front = =(sq-> rear+1)% maxSize 入隊(duì) :sq-> rear=(sq-> rear+1)% maxSize8/62出列 :sq-> front =(sq-> front+1)% maxSi

15、ze 詢問隊(duì)長 :(sq->原因-sq-> front+1)循環(huán)隊(duì)列操作(1)入隊(duì)(1)檢查隊(duì)列是否已滿，如果隊(duì)列已滿，將執(zhí)行溢出錯誤處理 (2)將尾 部指針向后移動一個位置 (即加 1)以指向下一個單元 (3)將新的元素分 配給團(tuán)隊(duì)尾部指針?biāo)赶虻膯卧獱顟B(tài)入隊(duì) (SqQueue *Q，ElemType e) if ( (Q-后+1)%MAXQSIZE = Q- 前) 返回(錯誤)；/團(tuán)隊(duì)溢出 q-原因= (q-原因+1)% maxqsize；Q-數(shù)據(jù)Q-后= e；返回(真)；(2) 出列 (1)檢查隊(duì)列是否為空，如果隊(duì)列為空，則繼續(xù)下溢錯誤處理 將組長指針向后移動一個位置 (即加

16、 1)(3)重視團(tuán)隊(duì)第一要素的價(jià) 值狀態(tài)出列 (SqQueue *Q) if (Q-后= Q-前)返回(NULL) ；/團(tuán)隊(duì)空溢出 Q-前臺=(Q-前臺+1)% MAXQSIZE ；返 回(Q-數(shù)據(jù) Q-前部 )；(3) 空隊(duì)列q- front = q- reason = maxqsize-1； (4)取團(tuán)隊(duì)負(fù)責(zé)人 datatypegethead(sqqueue * q) if(q- front = = q- reason) return(null) ； /團(tuán)隊(duì)空返回 (q-數(shù)據(jù) (q-前臺 +1)% maxqsize)；(5) 判斷隊(duì)空int 隊(duì)列空 (sqqueue * q)if(q- f

17、ront = = q- reason)返回 (true)；否則 返回(假)；9。鏈隊(duì)列操作(1)空 無效初始化隊(duì)列 (鏈接隊(duì)列 * Q) 隊(duì)列前 =隊(duì)列。原因 =（ 隊(duì)列節(jié)點(diǎn) *） Malloc（ 隊(duì)列節(jié)點(diǎn)大小 ）；9/62前置-下一個=后置-下一個=空； (2) 判斷團(tuán)隊(duì)為空int 隊(duì)列為空 (link queue * Q)return(Q . front- next = = null (3) 團(tuán)隊(duì)在void Enqueue(Linkqueue * Q，數(shù)據(jù)類型 x)QueueNode * p；p =(QueueNode *)malloc(sizeof(QueueNode)；p 數(shù)據(jù)= x；

18、p 下一個=空；Q-后部下一個= p；Q-后部= p； (4) 出列出列 (link queue * q) link queue * p ；數(shù)據(jù)類型 x。 if(EMPTY(Q)返回空值；p = Q-前-下； Q-前-下一個= p 下一個；如果 (p-下一個= = 空)Q- 后= Q- 前；x = p- 數(shù)據(jù)；免費(fèi) (p)；返回 x；3.2 堆棧和隊(duì)列應(yīng)用程序1。遞歸函數(shù)遞歸函數(shù)也稱為自調(diào)用函數(shù)，它具有以下特點(diǎn) :函數(shù)本身可以在函數(shù)內(nèi)部直接或間接調(diào)用例如，階乘函數(shù) :n！=1， n = 1elsereturn(n * FACT(n-1) ；10/622。算法表達(dá)式求值在處理表達(dá)式之前，計(jì)算機(jī)系

19、統(tǒng)建立兩個堆棧 :操作數(shù)堆棧 (OPRD)， 它在處理表達(dá)式的過程中存儲操作數(shù)。運(yùn)算符堆棧 (OPTR):在表達(dá)式 處理期間存儲運(yùn)算符在開始時， 首先按下操作符堆棧， 在堆棧底部有 一個表達(dá)式的結(jié)束符號 “#?！?1)中綴符號 計(jì)算機(jī)系統(tǒng)在處理表達(dá)式時從左到右依次讀出表達(dá)式中的每個符號(操作數(shù)或運(yùn)算符 )。在讀出每個符號 ch 之后，它根據(jù)運(yùn)算規(guī)則執(zhí)行以 下處理:(1)如果 ch 是操作數(shù)，它被推入操作數(shù)堆棧 OPRD，并依次讀出下一 個符號(2)如果 ch是運(yùn)算符，則為A ；如果讀取操作符的優(yōu)先級高于 OPTR 堆棧頂部的操作符的優(yōu)先 級，則將其按入 OPTR，并按順序讀取下一個符號B。如果

20、讀出 “#并”且 OPTR 堆棧頂部的運(yùn)算符也是 “#，”則表達(dá)式處 理結(jié)束，最終計(jì)算結(jié)果位于 OPRD 堆棧的頂部C，如果顯示 “（，”將其按入 OPTR如果它讀為 “ ），”則:如果 OPTR 堆棧的頂部不是 “（，”則兩個操作數(shù)相繼從 OPRD 退出， 一個操作數(shù)從 OPTR 退出，然后執(zhí)行相應(yīng)的操作，操作結(jié)果被壓入 OPRD，然后返回 a），允許 ch 繼續(xù)與 OPTR 堆棧的頂部元素進(jìn)行比 較如果OPTR堆棧頂部為“（ ”，）則從 OPTR退出“ （ ”，）并依次讀取下一 個符號E。如果讀操作符的優(yōu)先級低于 OPTR 棧頂操作符的優(yōu)先級，兩個 操作數(shù)將連續(xù)從 OPRD 中取出，一個操

21、作符將從 OPTR 中取出，然 后執(zhí)行相應(yīng)的操作，將操作結(jié)果壓入 OPRD 返回 （2）繼續(xù) OPTR 堆棧 頂部元素比較（2）波蘭符號和反向波蘭符號以 5+（64/2）* 3 為例，波蘭符號 :+5 *-6/4 2 3 反向波蘭符號 :5 6 4 2/-3 *+操作從左到右執(zhí)行，不帶括號。計(jì)算表達(dá)式時，可以建立一個堆棧， 從左到右掃描后綴表達(dá)式， 并將每個操作數(shù)推入堆棧。 每次讀取一個 運(yùn)算符時，都會從堆棧頂部提取兩個操作數(shù)操作， 并將結(jié)果推入堆棧， 直到讀取后綴表達(dá)式最后，堆棧頂部是計(jì)算結(jié)果。3。括號匹配# include # define max size 100 typedef int

22、 datatyp；etypedef結(jié)構(gòu)數(shù)據(jù)類型數(shù)據(jù) maxsize；數(shù)據(jù)類型頂部； seqstack。seqstack * s； void build() ；無效推送 ()；void pop()；國際支票 (char ss)；void main()char ssmaxsize； build() ；請輸入要測試的算術(shù)表達(dá)式 : scanf( if(check(ss)=-1) 算術(shù)表達(dá)式不匹配！ 否則算術(shù)表達(dá)式匹配！ void build()s =(seqstack *)malloc(sizeof(seqstack)；) s-> top =-1；11/62int check(char ss)

23、 int I = 0； while(ssi)！= 0 ) i+；+ if(ssI=( ；)push()；)' )pop()else if(ssI= = 返回 s-> top；void push() s->top+;void pop() s-> top- ；+4?；匚淖址袛? include # include # include # define maxsize 100 typedef 結(jié)構(gòu) chardatamaxsize；int top 堆棧； typedef 結(jié)構(gòu)char 數(shù)據(jù)maxsize；內(nèi)部陣線；內(nèi)部后部； 隊(duì)列；int is empty _ queue

24、(queue * stq) return stq-> front = = stq-> rea；r int 是 full _ queue(queue * stq)return stq-> rear > = maxsize-1； queue * init _ queue() queue * tmp =(queue *)malloc(sizeof(queue)； tmp->前= tmp->后 = 0；返回 tmpchardequeue(queue * stq) if(isempty _ queue(stq) printf( queue 為空，無法出列 n exit

25、(0) ； 返回 stq->數(shù)據(jù)stq->前臺+ ；void 隊(duì)列 (queue * stq，char value) if(is full _ queue(stq) 隊(duì)列已滿，無法排隊(duì) n exit(0)；stq->數(shù)據(jù)stq->后置+ =值；stack * init _ stack() stack * tmp =(stack *)malloc(size of(stack)； tmp-> top = 0；返回 tmpint is empty _ stack(stack * STK) return STK-> top = = 0 ？1:0； int 是 ful

26、l_stack(stack *stk) 返回 stk->top >= maxsize -1？1:0； char pop(stack * STK)if(isempty _ stack(STK)printf( stack 為空，無法彈出 n exit(0) ；12/62返回 stk->數(shù)據(jù) - stk->頂部； void push(堆棧* stk ，char value) if(is full _ stack(STK) 堆棧已滿，無法堆疊 n exit(0) ； stk->數(shù)據(jù)stk->top+ = 值；void compare(堆棧* stk，隊(duì)列*stq，字

27、符串)，int len) int I ； int 標(biāo)志= 0；char 臨時堆棧； char 臨時隊(duì)列；(I = 0；i (I = 0 ；i if(temp_stack！= temp_queue) 不是回文字符串 n flag = 1；休息； if( ！標(biāo)志)是回文字符串 n int main()queue * stq = init _ queue()；堆棧* STK = init _ stack() ；char cmaxsize，s；int I = 0；請輸入以 n scanf（ while！= ） cI；= sscanf（ i+;cI= 0 ；比較（stk、stq、c、strlen（c）-

28、1）；返回 0；3.3示例示例 1:堆棧和隊(duì)列是特殊的線性表，其特殊性如？為什么引入循環(huán)隊(duì)列？解決方案 :與普通的線性表相比，插入和刪除操作是有限的一般一維 數(shù)組隊(duì)列的尾部指針已到達(dá)數(shù)組的上限， 不允許隊(duì)列條目，但數(shù)組中 仍有一個空位置。為了解決這個問題，必須引入循環(huán)隊(duì)列。示例 2:如果堆棧的堆棧入口序列是 A、B、C、D，那么可能的堆棧 出口序列是什么？解決方案 :共 14 種，即:ABCD 、ACBD 、ACDB 、ABDC 、ADCB 、 BACD 、BADC 、 BCAD 、 BCDA 、BDCA 、CBAD 、 CBDA 、 CDBA 、 DCBA案例 3:有 5個元素，它們的堆疊順

29、序是 a、b、c、d、e。在各種可能 的堆疊順序中，哪一個是元素 c、d 先堆疊的順序 （c 先堆疊，d 后堆 疊）？解決方案:共3種，即:CDEBA 、CDBEA 和 CDBAE示例 4:確定順序堆棧 st（最大元素?cái)?shù)為 StackSize）是否為空 /滿的條件是解決方案 :空:ST-頂部=0，滿:ST-頂部 =MAXSIZE-113/62情況 5:判斷循環(huán)隊(duì)列 q（存儲元素位置 :0到 QueueSize-1）已滿的條件是 解決方案 :sq- front = = （sq-原因 +1）% maxsize示例 6:如果使用大小為 6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列， 并且當(dāng)前的 reason 和 front 值分別為 0 和