第三章棧與隊(duì)列-資料下載頁(yè)
2025-08-22 21:46本頁(yè)面
【導(dǎo)讀】棧的數(shù)組表示可能棧滿。棧的單鏈表表示無(wú)棧滿問(wèn)題。出棧在表頭進(jìn)行刪除操作。不能，3出棧時(shí)，說(shuō)明2和1都在棧里，而且2必須。則棧大小至少為多少？一個(gè)表達(dá)式由操作數(shù)、操作符。優(yōu)先級(jí)高的先計(jì)算；優(yōu)先級(jí)相同的自左向右計(jì)算；當(dāng)使用括號(hào)時(shí)從最內(nèi)層括號(hào)開(kāi)始計(jì)算。前綴和中綴表達(dá)式求值需要兩個(gè)棧；后綴表達(dá)。式求值只需一個(gè)棧，相對(duì)簡(jiǎn)單些。順序掃描后綴表達(dá)式每一項(xiàng)。若該項(xiàng)是操作數(shù)，則進(jìn)棧。若是雙目運(yùn)算符，則連續(xù)出棧兩個(gè)操作數(shù)X和Y，并將。當(dāng)表達(dá)式的所有項(xiàng)都掃描并處理完后，棧頂存放的。就是最后的計(jì)算結(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)值最小的點(diǎn) p0； 2. 按照與 p0極角 (逆時(shí)針?lè)较?)大小排序 Q中其余點(diǎn)， 結(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形成非左移動(dòng) Do 6. Pop(S)。 7. Push(pi, S)。 8. Rerurn S； O(nlogn) O(n) O(1) O(n) 總時(shí)間復(fù)雜度 O(nlogn) 循環(huán)為什么是 O(n) 最多 n次入棧， 那么出棧也是最多 n次 隊(duì)列 ? 定義 ? 隊(duì)列是只允許在一端刪除，在另一端插入的線性表 ? 允許刪除的一端叫做隊(duì)頭 (front)，允許插入的一端叫做隊(duì)尾 (rear)。 ? 特點(diǎn)：先進(jìn)先出 ? 隊(duì)列的操作 ? 入隊(duì) EnQueue() ? 出隊(duì) DeQueue() ? 判斷是否為空 isEmpty() ? 隊(duì)列滿 isFull() 48 隊(duì)列 ? 隊(duì)列的數(shù)組表示 ? 入隊(duì)：在 rear 位置加入數(shù)據(jù)， rear = rear + 1 ? 出隊(duì)：在 front位置取出數(shù)據(jù)， front = front + 1 49 A B C D E F front rear 空隊(duì)列 A入隊(duì) B、 C入隊(duì) A出隊(duì) B出隊(duì) D、 E、 F入隊(duì) ear rear rear front front 隊(duì)列 ? 隊(duì)列的數(shù)組表示 (循環(huán)隊(duì)列 ) ? 入隊(duì)：在 rear 處加入數(shù)據(jù)， rear=(rear+1)%SIZE ? 出隊(duì)：在 front處取出數(shù)據(jù)， front=(front+1)%SIZE ? 隊(duì)滿： (rear+1)%SIZE == front ? 隊(duì)空： rear == front 50 1 2 3 4 5 6 7 0 D E F G H A B C 空隊(duì)列 A入隊(duì) B、 C、 D入隊(duì) A、 B出隊(duì) E、 F、 G、 H、 I入隊(duì) rear front rear rear front I 隊(duì)列 ? 隊(duì)列的單鏈表表示 ? 隊(duì)列的數(shù)組表示可能隊(duì)列滿 ? 隊(duì)列的單鏈表表示無(wú)隊(duì)列滿問(wèn)題 ? 入隊(duì)在表尾進(jìn)行插入操作 ? 出隊(duì)在表頭進(jìn)行刪除操作 51 A B C null front rear 打印二項(xiàng)展開(kāi)式 (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 打印二項(xiàng)展開(kāi)式 (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 打印二項(xiàng)展開(kāi)式 (a+b)i 的系數(shù) 54 0 0 1 2 1 0 1 1 1 3 3 1 0 出隊(duì)列時(shí)與前一個(gè)出隊(duì)列的數(shù)相加，結(jié)果入隊(duì)列 0作為被加數(shù)時(shí)， 0入隊(duì)列，作為分隔符 隊(duì)列的應(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) 起點(diǎn) 終點(diǎn) 已布線 隊(duì)列的應(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) 起點(diǎn) 終點(diǎn) 已布線 (1,1) (0,1) (1,0) (2,1) (2,0) (3,1) (3,0) (3,2) (3,3) front rear 已訪問(wèn) 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號(hào)-1