第3章-數據結構(文件)
【正文】 樹 ? 后根次序 ? 在后根次序下遍歷頭一棵樹樹根的子樹 ? 訪問頭一棵樹的根 ? 在后根次序下遍歷其他的樹 A B C G H F D E J I D I J E F B G H CA 40 167。 圖 一、定義 ? 有限的節(jié)點集合 K，對 K中節(jié)點的前驅和后繼節(jié)點的個數不加限制，則就是圖結構 ? 用 G=(V, E)表示一個圖，圖的節(jié)點稱為頂點， V是有窮頂點的集合，節(jié)點的偶對稱為邊， E是邊的集合 ? 如果節(jié)點的偶對是無序的，則稱為 無向圖 ；如果節(jié)點的偶對是有序的，則稱為 有向圖 ? 在無向圖中，若頂點 Vi與 Vj之間有一條邊 (Vi, Vj)，則稱 Vi與 Vj鄰接，稱邊 (Vi, Vj)依附于頂點 Vi, Vj；依附于頂點邊的個數稱為 度 ? 在有向圖中，進入該頂點的有向邊的個數為入度，由該頂點引出的有向邊的個數為出度， 度 =入度 +出度 44 167。 圖 V2 V1 V3 V4 V1 V2 V3 V4 2 4 ? 3 ? 2 ? 3 ? V1 ? V2 V3 V4 1 3 ? 2 4 ? 1 ? 出邊表 入邊表 48 167。然后，從Ｗ ２ 出發(fā)進行如上的訪問。然后，再順序訪問Ｗ １ ，Ｗ ２ ， … ，Ｗ ｔ 的所有的鄰接點（已被訪問過的頂點除外），再從這些被訪問的點出發(fā)，逐次進行訪問，依次類推，直到所有頂點都被訪問到為止。 1 2 3 4 5 6 7 8 Ｖ １ → Ｖ ２ → Ｖ ４ → Ｖ ８ → Ｖ ５ → Ｖ ６ → Ｖ ３ → Ｖ ７ 50 167。 ? 深度優(yōu)先搜索： ? 廣度優(yōu)先搜索： 49 167。 圖 二、存儲 ? 相鄰矩陣表示法 ? 若 G是一個具有 n個節(jié)點的有向圖，則 G的相鄰矩陣為： A[i, j] = 1 若 (Vi,Vj)或 (Vj,Vi)是圖 G的邊 0 若 (Vi,Vj)或 (Vj,Vi)不是圖 G的邊 { V2 V1 V3 V4 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0 V2 V1 V3 V4 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 0 46 167。 樹 三、存儲方式 ? 一般采用鏈表存儲 數據 指針 1 指針 2 …… 指針 m 指向直接 后繼節(jié)點 A B C G H F D E 數據 指針 1 指針 2 指針 3 指針 4 A B C ? B D E F ? C G H ? D ? E ? F ? G ? H ? 42 167。 樹 A B C G H F D E J I A B C G H F D E J I (A(B(D)(E(I)(J))(F))(C(G)(H))) 樹形表示 文氏圖表示 嵌套括號表示 38 167。 隊列 三、操作 ? enq(QU, X)：往隊列 QU中插入一個值為 X的表目 ? deq(QU)：從隊列 QU中刪除一個表目 ? front(QU, X)：把隊列 QU頭部表目的值讀到變量X中 ? qempty(QU)：判斷隊列是否為空 … ai ai+1 … aj aj+1 … 頭指針 尾指針 … ai ai+1 … aj 頭指針 尾指針 插入aj+1 刪除 ai
教學課件相關推薦
鄂ICP備17016276號-1