【正文】 圖 三、圖的遍歷 ? 遍歷： 從圖中某一點(diǎn)出發(fā)訪問圖中其余頂點(diǎn)，或當(dāng)給定的圖是連通圖，則從圖中任意一點(diǎn)出發(fā)順著某些邊可以訪問到該圖中的所有的頂點(diǎn)，且使每一個(gè)頂點(diǎn)僅被訪問一次。 隊(duì)列 二、存儲 ? 用順序表實(shí)現(xiàn)，分配一塊連續(xù)存儲區(qū)域存放隊(duì)列中的元素，用兩個(gè)指針分別指向隊(duì)列的頭尾 ? 當(dāng)隊(duì)列首尾指針相連時(shí)，發(fā)生隊(duì)列溢出 … ai ai+1 … aj 頭指針 尾指針 … an1 an 頭指針 尾指針 假溢出 33 167。 數(shù)組 一、定義 ? 一組具有相同屬性的數(shù)據(jù)元素（數(shù)據(jù)類型、數(shù)據(jù)長度相同）按一定方式進(jìn)行排列，使得其中每一數(shù)據(jù)元素都能由一個(gè)整數(shù)序列唯一確定它的位置，這樣的數(shù)據(jù)結(jié)構(gòu)稱為數(shù)組。 ? 數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及對數(shù)據(jù)的各種操作。 ? 它刻畫了應(yīng)用中涉及到的數(shù)據(jù)的邏輯組織。 表 一、定義 二、運(yùn)算 三、存儲方式 22 數(shù)據(jù)項(xiàng) 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。 1 2 3 4 5 6 7 8 Ｖ １ → Ｖ ２ → Ｖ ４ → Ｖ ８ → Ｖ ５ → Ｖ ６ → Ｖ ３ → Ｖ ７ 50 167。 圖 一、定義 ? 有限的節(jié)點(diǎn)集合 K，對 K中節(jié)點(diǎn)的前驅(qū)和后繼節(jié)點(diǎn)的個(gè)數(shù)不加限制，則就是圖結(jié)構(gòu) ? 用 G=(V, E)表示一個(gè)圖，圖的節(jié)點(diǎn)稱為頂點(diǎn)， V是有窮頂點(diǎn)的集合，節(jié)點(diǎn)的偶對稱為邊， E是邊的集合 ? 如果節(jié)點(diǎn)的偶對是無序的，則稱為 無向圖 ；如果節(jié)點(diǎn)的偶對是有序的，則稱為 有向圖 ? 在無向圖中，若頂點(diǎn) Vi與 Vj之間有一條邊 (Vi, Vj)，則稱 Vi與 Vj鄰接，稱邊 (Vi, Vj)依附于頂點(diǎn) Vi, Vj；依附于頂點(diǎn)邊的個(gè)數(shù)稱為 度 ? 在有向圖中，進(jìn)入該頂點(diǎn)的有向邊的個(gè)數(shù)為入度，由該頂點(diǎn)引出的有向邊的個(gè)數(shù)為出度， 度 =入度 +出度 44 167。 棧 一、定義 ? 棧是一種操作受限的線性表 ? 對于棧的插入和刪除操作都限制在表的末端進(jìn)行 ? 將表的末端稱為棧頂，起始位置稱為棧底 二、特性 ? 每次刪除的總是最后插入的表目，而最先插入的表目則放在棧的底部，要到最后才能刪除，因此棧是“后進(jìn)先出表”或下推表 ? 食堂里的一疊盤子 ? 算術(shù)表達(dá)式、遞歸 28 167。 串 三、存儲結(jié)構(gòu) ?順序存放 ?特點(diǎn) ?查詢快 ?更新慢 H o w a r e y o u ? ? H o w a r e y o u ? ? 按字節(jié)編址 H o w a r e y o u ? ? 按字編址 無壓縮 按字編址 壓縮存放 節(jié)省存儲空間，單字節(jié)操作不方便 H o w d o y o u ? ? 更新需移動多個(gè)存儲單元 13 167。2 第三章 數(shù) 據(jù) 結(jié) 構(gòu) 3 什么是數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。 串 二、定義 ?由零個(gè)或多個(gè)字符組成的有限序列 ,記作 ： S = ‘a(chǎn)1 a2 … a n’ ?子串 有兩