西安交通大學(xué)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料-在線瀏覽
2025-06-04 12:21本頁面
【正文】 的指針就是頭指針。若線性表的操作主要是查找和讀取時(shí)，采用順序存儲(chǔ)結(jié)構(gòu)為宜；若線性表的操作主要是插入和刪除時(shí)，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)為宜。在順序表中進(jìn)行插入和刪除數(shù)據(jù)元素時(shí)，平均要移動(dòng)近一半的元素，尤其是當(dāng)每個(gè)數(shù)據(jù)元素包含的信息量較大時(shí)，移動(dòng)元素所花費(fèi)的時(shí)間就相當(dāng)可觀。但在動(dòng)態(tài)鏈表中進(jìn)行插入和刪除結(jié)點(diǎn)時(shí)，不需要移動(dòng)結(jié)點(diǎ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)行刪除。向隊(duì)列中插入新元素稱為進(jìn)隊(duì)或入隊(duì)，新元素進(jìn)隊(duì)后就成為新的隊(duì)尾元素；從隊(duì)列中刪除元素稱為離隊(duì)或出隊(duì)，元素離隊(duì)后，其后繼元素就成為隊(duì)首元素。了解隊(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)的度的最大值就是這棵樹的度。v 分支結(jié)點(diǎn)：度非零的結(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)(cousins)：其雙親在同一層但不同的結(jié)點(diǎn)互為堂兄弟。有序樹：結(jié)點(diǎn)的子樹從左到右有序安排。在有序樹中，改變了子樹的相對(duì)次序就變成了另一棵樹。熟悉樹的性質(zhì)，并能根據(jù)這些性質(zhì)進(jìn)行相關(guān)推理和計(jì)算v 性質(zhì)1: 樹中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1。樹的總分支數(shù)為：v 性質(zhì)2： 度為k的樹中第i層上至多有ki1個(gè)結(jié)點(diǎn)（i≥1）。 假設(shè)第i1層(i1)命題成立，該層上有ki2 個(gè)結(jié)點(diǎn)。 v 性質(zhì)3 深度為h的k叉樹至多有 個(gè)結(jié)點(diǎn)。v 性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的k叉樹的最小深度為： 233。 分析：在結(jié)點(diǎn)數(shù)相同的 k叉樹中，每一層結(jié)點(diǎn)都滿，或除最后一層外其余層都滿的樹，其深度為最小。logk( n(k1)+1)249。logk( n(k1)+1)249。x 249。v 二叉樹(binary tree)是指樹的度為2的有序樹。v 二叉樹的遞歸定義為：二叉樹或者是一棵空樹，或者是一棵由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的分別稱做根的左子樹和右子樹所組成的非空樹，左子樹和右子樹又同樣都是一棵二叉樹。性質(zhì)2： 深度為k的二叉樹，最多有2k1個(gè)結(jié)點(diǎn) ( k ≥1)。 n1 :單分支結(jié)點(diǎn)數(shù), n2 :雙分支結(jié)點(diǎn)數(shù)) (2) 設(shè)B為二叉樹中總的分支數(shù)目，由于二叉樹中除了根結(jié)點(diǎn)之外，其余結(jié)點(diǎn)都有一個(gè)分支進(jìn)入,而這些分支只能是由度數(shù)為1或2的結(jié)點(diǎn)所發(fā)出，所以： B = n1 + 2n2 于是得： n = n1 + 2n2 + 1(3) 由(1)和(2)得： n0 + n1 + n2 = n1 + 2n2 + 1 所以 n0 = n2 + 1 證畢性質(zhì)4：對(duì)完全二叉樹中編號(hào)為i的結(jié)點(diǎn)(1≤i≤n,n≥1，n為結(jié)點(diǎn)數(shù))有： (1) 若i≤235。即2i≤n，則編號(hào)為i的結(jié)點(diǎn)為分支結(jié)點(diǎn)，否則為葉子結(jié)點(diǎn)。x (2) 若n為奇數(shù)，則樹中每個(gè)分支結(jié)點(diǎn)都既有左孩子，又有右孩子；若n為偶數(shù)，則編號(hào)最大的分支結(jié)點(diǎn)（編號(hào)為n/2）只有左孩子，沒有右孩子，其余分支結(jié)點(diǎn)左、右孩子都有。 (4) 除樹根結(jié)點(diǎn)外，若一個(gè)結(jié)點(diǎn)的編號(hào)為i，則它的雙親結(jié)點(diǎn)的編號(hào)為235。,也就是說，當(dāng)i為偶數(shù)時(shí)，其雙親結(jié)點(diǎn)的編號(hào)為i/2，它是雙親結(jié)點(diǎn)的左孩子，當(dāng)i為奇數(shù)時(shí)，其雙親結(jié)點(diǎn)的編號(hào)為(i1)/2，它是雙親結(jié)點(diǎn)的右孩子。性質(zhì)5：具有n個(gè)(n0)結(jié)點(diǎn)的完全二叉樹的深度為233。或235。+1。 證明：設(shè)所求完全二叉樹的深度為h，由完全二叉樹的定義可知，它的前h1層都是滿的，最后一層可以滿，也可以不滿，由此得到的如下不等式 2h11n≤2h1 ． 可變換為： 2h1n+1≤2h 取對(duì)數(shù)后得： h1log2(n+1)≤h 即： log2(n+1)≤hlog2(n+1)+1 因h只能取整數(shù)，所以： h= 233。 完全二叉樹的深度h和結(jié)點(diǎn)數(shù)n的關(guān)系，還可表示為： 2h1≤n2h 取對(duì)數(shù)后得： h1≤l
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1