第3章-數(shù)據(jù)結(jié)構(gòu)-預(yù)覽頁
【正文】 1) a(1, 2) … a(1,m) … … a(i, j) … a(n, 1) a(n, 2) … a(n,m) a(1, 1) … a(1, m) a(2, 1) … a(2,m) … a(n,1) … a(n,m) a(1, 1) … a(n, 1) a(1, 2) … a(n, 2) … a(1,m) … a(n,m) 按行存儲 按列存儲 按行存儲 addr(a(i, j)) = addr(a(1, 1))+ (i –1)?m + j 1 按列存儲 addr(a(i, j)) = addr(a(1, 1))+ (j –1)?n + i 1 21 167。 表 三、存儲方式 ? 順序存放 ? 把表中元素依次存放在一組連續(xù)的單元內(nèi) ? 訪問方便快捷，更新操作復(fù)雜 ? 設(shè)表的基地址為 addr(a1)，假定每個數(shù)據(jù)元素占用k 個存儲單元，則的存儲單元的首地址為 addr[ai] = addr(a1) + (i 1) ? k 25 167。 棧 三、存儲 ?用向量（由相同數(shù)據(jù)類型組成的線性序列）表示棧，并用指針指示棧頂?shù)奈恢? ai ai1 … … a2 a1 棧底 棧頂 棧頂指示器 ?i 29 167。 隊(duì)列 二、存儲 ? 用順序表實(shí)現(xiàn)，分配一塊連續(xù)存儲區(qū)域存放隊(duì)列中的元素，用兩個指針分別指向隊(duì)列的頭尾 ? 當(dāng)隊(duì)列首尾指針相連時，發(fā)生隊(duì)列溢出 … ai ai+1 … aj 頭指針 尾指針 … an1 an 頭指針 尾指針 假溢出 33 167。 樹 ? 樹是包含 n個節(jié)點(diǎn)的有限集合，滿足 ① 有且僅有一個節(jié)點(diǎn)沒有前驅(qū)，稱為樹的根 ② 除根之外的其他節(jié)點(diǎn)被分成 m個不相交的集合，而且這些集合的每一個又都是樹 ? 樹的一枝所含子節(jié)點(diǎn)的數(shù)目稱為度，各節(jié)點(diǎn)度的最大值稱為樹的度 數(shù)據(jù)結(jié)構(gòu) 線性結(jié)構(gòu) 非線性結(jié)構(gòu) 數(shù)組 串 表 棧 隊(duì)列 樹 圖 根節(jié)點(diǎn) 內(nèi)部節(jié)點(diǎn) 葉節(jié)點(diǎn) 37 167。 樹 ? 按寬度的方向遍歷 ? 首先訪問層數(shù)為 0的節(jié)點(diǎn)，然后依次訪問層數(shù)為 1的節(jié)點(diǎn)，直到訪問完最下一層的所有節(jié)點(diǎn) A B C G H F D E J I ABCDEFGHIJ 41 167。 圖 V2 V1 V3 V4 V={V1,V2,V3,V4} E={(V1,V2), (V2,V3), (V1,V4), (V2,V4) (V3,V4)} V2 V1 V3 V4 V={V1,V2,V3,V4} E={(V1,V2), (V1,V4), (V2,V3) , (V3,V2) (V4,V3)} 度為 3 度為 2 出度為 1 入度為 2 度為 3 45 167。 圖 三、圖的遍歷 ? 遍歷： 從圖中某一點(diǎn)出發(fā)訪問圖中其余頂點(diǎn)，或當(dāng)給定的圖是連通圖，則從圖中任意一點(diǎn)出發(fā)順著某些邊可以訪問到該圖中的所有的頂點(diǎn)，且使每一個頂點(diǎn)僅被訪問一次。重復(fù)這種訪問，直到一個頂點(diǎn)的所有鄰接點(diǎn)都被訪問過為止，接著退回到尚有鄰接點(diǎn)未被訪問過的頂點(diǎn)，再從該頂點(diǎn)出發(fā)，重復(fù)上述搜索過程，直到所有的被訪問過的頂點(diǎn)的鄰接點(diǎn)都已被訪問到為止。 Ｖ １ → Ｖ ２ → Ｖ ３ → Ｖ ４ → Ｖ ５ → Ｖ ６ → Ｖ ７ → Ｖ ８ 1 2 3 4 5 6 7
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1