數(shù)據(jù)結(jié)構(gòu)ppt課件(編輯修改稿)
2025-05-27 18:23 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 棧u 例 3. 開(kāi)關(guān)盒布線– 給定一個(gè)矩形布線區(qū)域，其外圍有若干針腳。兩個(gè)針腳之間通過(guò)布設(shè)一條金屬線路而實(shí)現(xiàn)互連。這條線路被稱(chēng)為電線，被限制在矩形區(qū)域內(nèi)。如果有電線交叉，則發(fā)生短路。每對(duì)互連的針腳被稱(chēng)為網(wǎng)組。– 問(wèn)題：給定一個(gè)開(kāi)關(guān)盒布線實(shí)例，確定它是不是一個(gè)可布線的。u 例 4. 迷宮老鼠– 迷宮是一個(gè)矩形區(qū)域，它有一個(gè)入口和一個(gè)出口。在迷宮的內(nèi)部包含不能穿越的墻或障礙。– 假定用 nxm的矩陣來(lái)描述迷宮，位置 (1,1)表示入口， (n,m)表示出口，n和 m分別代表迷宮的行數(shù)和列數(shù)。– 問(wèn)題：尋找一條從入口和出口的路徑。u 問(wèn)題 1. 表達(dá)式求值問(wèn)題– 用兩個(gè)棧分別記錄運(yùn)算符和運(yùn)算對(duì)象，支持加減乘除和圓括號(hào)u 問(wèn)題 2. 漢諾塔隊(duì)列u 定義– 一種先進(jìn)先出的線性表；只允許在一端進(jìn)行插入，另一端刪除。– 允許插入的一端稱(chēng)為隊(duì)尾，允許刪除的一端稱(chēng)為隊(duì)頭。u 順序存儲(chǔ)結(jié)構(gòu)– 解決 “假溢出– 解決下標(biāo)越界– 解決頭尾指針相同時(shí)的滿空二義性u(píng) 問(wèn)題 1. 迷宮老鼠之最短路徑u 問(wèn)題 2. 識(shí)別圖元– 數(shù)字化圖像是一個(gè) mxm的像素矩陣。在單色圖像中，每個(gè)像素的值要么為 0，要么為 1，值為 0的像素表示圖像的背景，值為 1的像素則表示圖元上的一個(gè)點(diǎn)，稱(chēng)為圖元像素。彼此相鄰的圖元像素構(gòu)成一個(gè)圖元。串u 定義– 由零個(gè)或多個(gè)字符組成的有限序列，也稱(chēng)字符串。u 串的模式匹配（查找子串）– S(n字符 )， T(m字符 )為給定的兩個(gè)串，從 S中查找等于 T的子串； S稱(chēng)為主串，T稱(chēng)為模式串。– BruteForce算法 (BF算法 ) (O(mn))187。 從主串 S的第 pos個(gè)字符起和模式串的第一個(gè)字符比較，若相等，則繼續(xù)逐個(gè)比較后續(xù)字符；否則從主串的下一個(gè)字符起再重新和模式串的字符比較。187。 最壞情況 m(nm)– KMP算法 (Knuth,Morris,Pratt) (O(m+n))187。 1. 首先在模式串中找出與其首字母起子串相重疊的各個(gè)子串。187。 2. 從主串 S的第一個(gè)字母與模式串的第一個(gè)字母開(kāi)始依次比較，如發(fā)現(xiàn)不同，則根據(jù)情況滑動(dòng)模式串，再?gòu)陌l(fā)現(xiàn)不同的那個(gè)字母開(kāi)始比較。u 例：凱撒密碼加密問(wèn)題– 將明文中的所有字母都在字母表上向后按照一個(gè)固定數(shù)目進(jìn)行偏移后被替換成密文。數(shù)組u 定義– 數(shù)組可以看成是一般線性表的擴(kuò)充。二維數(shù)組可以看成是線性表的線性表。u 二維數(shù)組的存儲(chǔ)– 以行為主序的存儲(chǔ)方式，稱(chēng)為行優(yōu)先存儲(chǔ)。– 以列為主序的存儲(chǔ)方式，稱(chēng)為列優(yōu)先存儲(chǔ)。u 特殊矩陣的壓縮存儲(chǔ)– 對(duì)稱(chēng)矩陣、三角矩陣、對(duì)角矩陣等u 稀疏矩陣的壓縮存儲(chǔ)– 三元組順序表187。 (行下標(biāo) ,列下標(biāo) ,元素 )– 十字鏈表187。 (行下標(biāo) ,列下標(biāo) ,元素 ,指向同行下個(gè)元素指針 ,指向同列下個(gè)元素指針 )187。 每行首個(gè)非零元素指針列表187。 每列首個(gè)非零元素指針列表– 基本運(yùn)算187。 轉(zhuǎn)置、加法、乘法廣義表u 定義– 廣義表是 n個(gè)數(shù)據(jù)元素的有限序列，每個(gè)數(shù)據(jù)元素可以是單個(gè)元素，也可以是廣義表。187。 廣義表的定義是一個(gè)遞歸的定義。– 廣義表記為： LS=(a1,a2,…,an),ai 可為單個(gè)元素，稱(chēng)為 LS的原子，用小寫(xiě)字母表示；也可為廣義表，稱(chēng)為 LS的子表，用大寫(xiě)字母表示。– 表頭： LS的第一個(gè)元素 a1為 LS的表頭。– 表尾：除第一個(gè)元素外，其余元素組成的表 (a2,…,an) 為 LS的表尾。– 長(zhǎng)度：廣義表中包含元素的個(gè)數(shù) (包含原子和子表 )，即最高層表結(jié)點(diǎn)的個(gè)數(shù)。– 深度：廣義表中括號(hào)嵌套的最大層數(shù)。u 例– A=()：一個(gè)空表，長(zhǎng)度為零。– B=(e)：有一個(gè)原子，長(zhǎng)度為 1。– C=(a,(b,c,d))：長(zhǎng)度為 2，元素分別為原子和子表。– D=(A,B,C)：長(zhǎng)度為 3，元素都是列表。– E=(a,E)：一個(gè)遞歸的表，長(zhǎng)度為 2。廣義表u 存儲(chǔ)– 頭尾鏈表存儲(chǔ)187。 表結(jié)點(diǎn)：標(biāo)志域、表頭指針、表尾指針187。 原子結(jié)點(diǎn)：標(biāo)志域、值域187。 typedef enum{ATOM,LIST} ElemFlag。187。 Typedef struct GLNode {187。 ElemFlag flag。187。 union {187。 AtomType atom。187。 struct { struct GLNode *hp, *tp} ptr。187。 }。187。 }*GList。廣義表u 存儲(chǔ)– 擴(kuò)展線性鏈表存儲(chǔ)187。 表結(jié)點(diǎn)：標(biāo)志域、表頭指針、表尾指針187。 原子結(jié)點(diǎn)：標(biāo)志域、值域、表尾指針187。 typedef
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1