西安交通大學(xué)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料-文庫吧
2025-04-02 12:21 本頁面
【正文】 向其直接后繼。循環(huán)鏈表。循環(huán)鏈表和單鏈表的差別僅在于鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不為“NULL”，而是指向頭一個(gè)結(jié)點(diǎn)，成為一個(gè)由鏈指針鏈結(jié)的環(huán)。循環(huán)鏈表的特點(diǎn)：只要知道表中任何一個(gè)結(jié)點(diǎn)的地址，就能查詢到表中的任何一個(gè)結(jié)點(diǎn)。 了解單鏈表的結(jié)點(diǎn)的類型定義在程序中，L為單鏈表的頭指針，它指向表中第一個(gè)結(jié)點(diǎn)。若 L 為“空”(L = NULL)，則所表示的線性表為“空”表，其長度為“零”。除了線性表第一個(gè)數(shù)據(jù)元素作為該鏈表的頭結(jié)點(diǎn)外，在某些線性鏈表存儲(chǔ)結(jié)構(gòu)中，還可在單鏈表第一個(gè)結(jié)點(diǎn)之前附加一個(gè)同結(jié)構(gòu)結(jié)點(diǎn)，稱為附加頭結(jié)點(diǎn)。頭結(jié)點(diǎn)數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存儲(chǔ)如線性表的長度等類的附加信息；頭結(jié)點(diǎn)指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針(即第一個(gè)元素的存儲(chǔ)位置)。那么，指向頭結(jié)點(diǎn)的指針就是頭指針。當(dāng)頭結(jié)點(diǎn)的指針域?yàn)椤翱铡睍r(shí)，單鏈表為空鏈表熟悉單鏈表中結(jié)點(diǎn)的定位、插入、刪除、查詢的算法思想和操作程序了解線性表的順序與鏈?zhǔn)酱鎯?chǔ)各自的優(yōu)點(diǎn)、不足與它們適用場合。若線性表的操作主要是查找和讀取時(shí)，采用順序存儲(chǔ)結(jié)構(gòu)為宜；若線性表的操作主要是插入和刪除時(shí)，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)為宜。 了解線性表的順序與鏈?zhǔn)酱鎯?chǔ)在不同操作場合下的時(shí)間復(fù)雜度指標(biāo)順序表是隨機(jī)存儲(chǔ)結(jié)構(gòu)，表中任一數(shù)據(jù)元素都可以通過計(jì)算直接得到地址進(jìn)行存取，時(shí)間復(fù)雜度為O(1)。在順序表中進(jìn)行插入和刪除數(shù)據(jù)元素時(shí)，平均要移動(dòng)近一半的元素，尤其是當(dāng)每個(gè)數(shù)據(jù)元素包含的信息量較大時(shí)，移動(dòng)元素所花費(fèi)的時(shí)間就相當(dāng)可觀。動(dòng)態(tài)鏈表是順序存儲(chǔ)結(jié)構(gòu)，表中的任一結(jié)點(diǎn)都需要從頭指針起順鏈掃描才能取得，時(shí)間復(fù)雜度為O(n)(n為表長)。但在動(dòng)態(tài)鏈表中進(jìn)行插入和刪除結(jié)點(diǎn)時(shí)，不需要移動(dòng)結(jié)點(diǎn)，只需要修改指針。第四章 棧和隊(duì)列了解棧的定義及性質(zhì)棧（stack）又稱堆棧，它是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。能給出在特定要求下的進(jìn)出棧序列以及判斷某些出棧序列出現(xiàn)的可能性了解棧的順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)，棧頂指針的設(shè)置了解棧的鏈接存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)、棧頂指針的更改熟悉棧在順序和鏈接存儲(chǔ)結(jié)構(gòu)下的進(jìn)棧、出棧和讀取棧頂元素的操作程序了解遞歸算法的特點(diǎn)及遞歸算法的中止條件，會(huì)結(jié)合具體程序來分析遞歸程序的合理性了解隊(duì)列的定義和它的順序存儲(chǔ)結(jié)構(gòu)v 隊(duì)列（queue）簡稱隊(duì)，它也是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除。v 我們把進(jìn)行插入的一端稱作隊(duì)尾(rear)，進(jìn)行刪除的一端稱作隊(duì)首(front)。向隊(duì)列中插入新元素稱為進(jìn)隊(duì)或入隊(duì)，新元素進(jìn)隊(duì)后就成為新的隊(duì)尾元素；從隊(duì)列中刪除元素稱為離隊(duì)或出隊(duì)，元素離隊(duì)后，其后繼元素就成為隊(duì)首元素。v 由于隊(duì)列的插入和刪除操作分別是在各自的一端進(jìn)行的，每個(gè)元素必然按照進(jìn)入的次序離隊(duì)，所以又把隊(duì)列稱為先進(jìn)先出表（first in first out, 簡稱FIFO）。了解隊(duì)列特別是循環(huán)隊(duì)列情況下，隊(duì)列頭指針和尾指針的設(shè)置了解隊(duì)列出現(xiàn)“假溢出”現(xiàn)象的原因及解決辦法：循環(huán)隊(duì)列的實(shí)現(xiàn)（循環(huán)頭指針和尾指針的計(jì)算、循環(huán)（和普通）隊(duì)列長度的計(jì)算以及循環(huán)隊(duì)列為空和滿的判斷方法）第五章 樹和二叉樹了解樹的定義和樹的基本術(shù)語：樹和結(jié)點(diǎn)的度、分支結(jié)點(diǎn)和葉子結(jié)點(diǎn)、父母結(jié)點(diǎn)和孩子結(jié)點(diǎn)、結(jié)點(diǎn)的層數(shù)和樹的深度、有序樹和無序樹等在樹形表示法中，結(jié)點(diǎn)之間的關(guān)系是通過連線表示的，雖然每條連線上都不帶有箭頭(即方向)，但它并不是無向的，而是有向的，其方向隱含為從上向下或從左向右，即連線的上方或左邊結(jié)點(diǎn)是下方或右邊結(jié)點(diǎn)的前驅(qū)，下方或右邊結(jié)點(diǎn)是上方或左邊結(jié)點(diǎn)的后繼。 v 結(jié)點(diǎn)的度：樹中每個(gè)結(jié)點(diǎn)具有的非空子樹數(shù)或者說后繼結(jié)點(diǎn)數(shù)被定義為該結(jié)點(diǎn)的度（degree）。v 樹的度：一棵樹上所有結(jié)點(diǎn)的度的最大值就是這棵樹的度。 v 葉子結(jié)點(diǎn)：度為零的結(jié)點(diǎn)稱葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)。v 分支結(jié)點(diǎn)：度非零的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)或稱為非終端結(jié)點(diǎn)。v 孩子結(jié)點(diǎn)(child) ：某結(jié)點(diǎn)子樹的根或者說某個(gè)結(jié)點(diǎn)的后繼被稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。v 雙親結(jié)點(diǎn)(parent)：一個(gè)結(jié)點(diǎn)是它的那些子樹的根的雙親結(jié)點(diǎn)。v 兄弟結(jié)點(diǎn)(sibling)：同一個(gè)雙親的孩子之間互為兄弟。v 堂兄弟結(jié)點(diǎn)(cousins)：其雙親在同一層但不同的結(jié)點(diǎn)互為堂兄弟。v 子孫結(jié)點(diǎn)：每個(gè)結(jié)點(diǎn)的所有子樹中的結(jié)點(diǎn)被稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)v 祖先結(jié)點(diǎn)：從整個(gè)（子）樹的根結(jié)點(diǎn)到達(dá)該結(jié)點(diǎn)的路徑上經(jīng)過的所有分支結(jié)點(diǎn)v 結(jié)點(diǎn)層次：從根結(jié)點(diǎn)開始，根結(jié)點(diǎn)為第1層，根結(jié)點(diǎn)的孩子為第2層，依此類推 1 A ………..第1層 2 B 3 C 4 D …. 第2層 5 E 6 F G 7 ……... 第3層樹的深度：樹中結(jié)點(diǎn)的最大層次。有序樹：結(jié)點(diǎn)的子樹從左到右有序安排。也即樹T中各子樹T1，T2，…，Tn的相對次序是有意義的。在有序樹中，改變了子樹的相對次序就變成了另一棵樹。 無序樹：結(jié)點(diǎn)的子樹順序任意。熟悉樹的性質(zhì)，并能根據(jù)這些性質(zhì)進(jìn)行相關(guān)推理和計(jì)算v 性質(zhì)1: 樹中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1。 證明：根據(jù)定義：除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有一個(gè)分支指向。樹的總分支數(shù)為：v 性質(zhì)2： 度為k的樹中第i層上至多有ki1個(gè)結(jié)點(diǎn)（i≥1）。 用數(shù)學(xué)歸納法證明： 對于 i=1, ki1 =k0 =1 命題成立。 假設(shè)第i1層(i1)命題成立，該層上有ki2 個(gè)結(jié)點(diǎn)。 對于第i層，最多結(jié)點(diǎn)數(shù)為：= ki1 命題得證。 v 性質(zhì)3 深度為h的k叉樹至多有 個(gè)結(jié)點(diǎn)。 證明：利用性質(zhì) 2來證明，k 叉樹的最大結(jié)點(diǎn)數(shù)為每一層最大結(jié)點(diǎn)數(shù)之和，則有：
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1