第三章棧與隊列-資料下載頁
2025-08-22 21:46本頁面
【導(dǎo)讀】棧的數(shù)組表示可能棧滿。棧的單鏈表表示無棧滿問題。出棧在表頭進行刪除操作。不能，3出棧時，說明2和1都在棧里，而且2必須。則棧大小至少為多少？一個表達式由操作數(shù)、操作符。優(yōu)先級高的先計算；優(yōu)先級相同的自左向右計算；當(dāng)使用括號時從最內(nèi)層括號開始計算。前綴和中綴表達式求值需要兩個棧；后綴表達。式求值只需一個棧，相對簡單些。順序掃描后綴表達式每一項。若該項是操作數(shù)，則進棧。若是雙目運算符，則連續(xù)出棧兩個操作數(shù)X和Y，并將。當(dāng)表達式的所有項都掃描并處理完后，棧頂存放的。就是最后的計算結(jié)果。
【正文】 6 p5 p4 p3 p10 p9 尋找凸包 ? Grahamscan的基本思想 p0 p2 p1 p7 p8 p6 p5 p4 p3 p10 p9 尋找凸包 ? Grahamscan的基本思想 p0 p2 p1 p7 p6 p8 p5 p4 p3 p10 p9 尋找凸包 ? Grahamscan的基本思想 p0 p2 p1 p7 p6 p8 p5 p4 p3 p10 p9 尋找凸包 ? Grahamscan的基本思想 p0 p2 p1 p7 p6 p8 p5 p4 p3 p10 p9 尋找凸包 ? Grahamscan的基本思想 p0 p2 p1 p7 p6 p8 p5 p4 p3 p10 p9 尋找凸包 ? Grahamscan的基本思想 47 Grahamscan(Q) 1. 求 Q中 y坐標(biāo)值最小的點 p0； 2. 按照與 p0極角 (逆時針方向 )大小排序 Q中其余點， 結(jié)果為 p1, p2, …, p m； 3. Push(p0, S)。 Push(p1, S)。 Push(p2, S)。 4. FOR i=3 TO m DO 5. While Nexttotop(S)、 Top(S)和 pi形成非左移動 Do 6. Pop(S)。 7. Push(pi, S)。 8. Rerurn S； O(nlogn) O(n) O(1) O(n) 總時間復(fù)雜度 O(nlogn) 循環(huán)為什么是 O(n) 最多 n次入棧， 那么出棧也是最多 n次 隊列 ? 定義 ? 隊列是只允許在一端刪除，在另一端插入的線性表 ? 允許刪除的一端叫做隊頭 (front)，允許插入的一端叫做隊尾 (rear)。 ? 特點：先進先出 ? 隊列的操作 ? 入隊 EnQueue() ? 出隊 DeQueue() ? 判斷是否為空 isEmpty() ? 隊列滿 isFull() 48 隊列 ? 隊列的數(shù)組表示 ? 入隊：在 rear 位置加入數(shù)據(jù)， rear = rear + 1 ? 出隊：在 front位置取出數(shù)據(jù)， front = front + 1 49 A B C D E F front rear 空隊列 A入隊 B、 C入隊 A出隊 B出隊 D、 E、 F入隊 ear rear rear front front 隊列 ? 隊列的數(shù)組表示 (循環(huán)隊列 ) ? 入隊：在 rear 處加入數(shù)據(jù)， rear=(rear+1)%SIZE ? 出隊：在 front處取出數(shù)據(jù)， front=(front+1)%SIZE ? 隊滿： (rear+1)%SIZE == front ? 隊空： rear == front 50 1 2 3 4 5 6 7 0 D E F G H A B C 空隊列 A入隊 B、 C、 D入隊 A、 B出隊 E、 F、 G、 H、 I入隊 rear front rear rear front I 隊列 ? 隊列的單鏈表表示 ? 隊列的數(shù)組表示可能隊列滿 ? 隊列的單鏈表表示無隊列滿問題 ? 入隊在表尾進行插入操作 ? 出隊在表頭進行刪除操作 51 A B C null front rear 打印二項展開式 (a+b)i 的系數(shù) ? 楊輝三角形 52 1 1 i = 1 1 2 1 2 1 3 3 1 3 1 4 6 4 1 4 1 5 10 10 5 1 5 1 6 15 20 15 6 1 6 (a+b)1=a+b (a+b)2=a2+2ab+b2 (a+b)3=a3+3a2b+3ab2+b3 打印二項展開式 (a+b)i 的系數(shù) ? 第 i行與第 i+1行關(guān)系 53 i = 2 i = 3 i = 4 0 1 3 3 1 0 1 4 6 4 1 0 1 2 1 0 0 1 1 0 打印二項展開式 (a+b)i 的系數(shù) 54 0 0 1 2 1 0 1 1 1 3 3 1 0 出隊列時與前一個出隊列的數(shù)相加，結(jié)果入隊列 0作為被加數(shù)時， 0入隊列，作為分隔符 隊列的應(yīng)用：電路布線 ? 找最短路徑 ? 網(wǎng)格方式布線，布線不能有重疊，轉(zhuǎn)彎用直角 55 (0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) (3,0) (3,1) (3,2) (3,3) 起點 終點 已布線 隊列的應(yīng)用：電路布線 ? 找最短路徑 56 (0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) (3,0) (3,1) (3,2) (3,3) 起點 終點 已布線 (1,1) (0,1) (1,0) (2,1) (2,0) (3,1) (3,0) (3,2) (3,3) front rear 已訪問 rear rear rear rear rear rear rear front front front front front front front front front null (1,1) (1,1) (1,1) (1,0) (2,1) (2,0) (3,1) (3,2)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1