考研-數據結構-棧-隊列-多維數組

1、數據結構棧 隊列 多維數組張憲超 教授本節(jié)重點復習要點考點精講例題精解同步練習2復習要點（1）1.棧的定義及特點棧的定義、棧頂與棧底概念棧的基本運算，包括進棧、出棧、判空棧、置空棧等2.棧的存儲表示順序棧的實現及基本操作鏈式棧的實現及基本操作3.隊列的定義及特點隊列的定義、先進先出特點隊列的基本運算，包括進隊、出隊、判隊空、置空隊3復習要點（2）4.隊列的存儲表示隊列的順序存儲及基本操作隊列的鏈式存儲及基本操作5.棧的應用棧在遞歸過程中作為工作棧的使用，棧在表達式計算中從中綴表示轉后綴表示，棧在括號配對中的應用，棧在數制轉換中的應用雙棧共用一個數組的進棧、退棧、置空棧算法及棧滿、?？諚l件，使用

2、兩個棧模擬一個隊列時的進隊列和出隊列算法。4復習要點（3）6.隊列的應用隊列在分層處理中的使用，包括二叉樹、樹、圖等 層次遍歷過程中的使用隊列在對數據循環(huán)處理過程中的使用，例如約瑟夫問題、歸并排序隊列在調度算法中的使用7.多維數組和特殊矩陣二維數組的基本概念和操作，特殊矩陣的壓縮存儲等5考點精講（1）1.棧和隊列的基本概念棧的定義及基本運算隊列的定義及基本運算2.棧的存儲結構棧的順序存儲結構棧的鏈式存儲結構棧操作的要點3.隊列的存儲結構隊列的順序存儲結構隊列的鏈式存儲結構隊列操作的要點6考點精講（2）4.棧和隊列的應用棧在表達式計算中的應用棧在遞歸中的應用隊列的應用5.數組與特殊矩陣的壓縮存儲

3、二維數組特殊矩陣的壓縮存儲7棧和隊列的基本概念棧的定義及基本運算隊列的定義及基本運算8棧和隊列的基本概念（1）棧的定義及基本運算通常，棧（Stack）可定義為只允許在表的末端進行插入和刪除的線性表。允許插入和刪除的一端叫做棧頂，而不允許插入和刪除的另一端叫做棧底。由于棧只能通過在它的棧頂進行訪問，因此，棧又叫做后進先出（LIFO，Last In First Out）的線性表。棧的基本運算棧初始化：創(chuàng)建一個空棧并使之初始化判?？辗瘢簵？辗祷豻rue，否則返回false進棧：棧未滿時，將新元素加入使之成為新的棧頂，若操作成功返回true，否則返回false出棧：棧非空時，將棧頂元素退出，若操作成功

4、返回true，否則返回false讀棧頂元素：當棧非空時，通過引用參數返回棧頂元素值（但不退出）。若操作成功返回true，否則返回false9棧和隊列的基本概念（2）隊列的定義及基本運算隊列（Queue）只允許在表的一端插入，在另一端刪除。允許插入的一端叫做隊尾，允許刪除的一端叫做隊頭。新的元素每次在隊尾加入，最早進入隊列的元素最先退出隊列。隊列的這種特性叫做先進先出（FIFO First In First Out）。隊列的基本運算隊列初始化：創(chuàng)建一個空隊列并初始化判隊列空否：隊列空時返回true，否則返回false進隊：隊列未滿時，將新元素加入使之成為新的隊尾，若操作成功返回true，否則返回

5、false出隊：隊列非空時，將隊頭元素退出，若操作成功返回true，否則返回false讀隊頭元素：當隊列非空時，通過引用參數返回隊頭元素值（但不退出）。若操作成功返回true，否則返回false10棧和隊列的基本概念（3）棧和隊列的進出規(guī)則利用鐵路調車軌道的棧式結構分析，當列車車廂按照1,2,3,n的編號進棧時，可能的不同出棧序列數目的計算利用Catalan函數可以計算得出：而列車車廂按照編號1,2,3,n進入隊列時，可能的出隊序列只有一種，該序列中各元素的編號仍然是1,2,3,n 。11棧的存儲實現棧的順序存儲結構棧的鏈式存儲結構棧操作的要點12棧的順序存儲棧的順序存儲指用一組地址連續(xù)的存儲

6、單元依次存儲棧中的元素順序存儲時，需要預先定義或申請棧的存儲空間，即棧空間的容量是有限的。因此當一個元素進棧前，需判斷是否棧滿，若棧滿，則元素進棧會發(fā)生上溢現象13棧的鏈式存儲利用單鏈表作為存儲結構的棧稱為鏈式棧鏈式棧的棧頂在鏈表的表頭（如圖2.2），因此結點的插入和刪除都在鏈表的表頭，即棧頂進行采用鏈式棧，便于結點的插入和刪除14棧操作的要點出棧操作和讀取棧頂元素操作是有區(qū)別的。前者退出棧頂元素，后者僅復制出一份棧頂元素，棧中元素個數不發(fā)生變化順序棧的缺點在于當棧滿時要發(fā)生溢出鏈式棧便于結點的插入和刪除，不存在棧滿的問題15隊列的存儲實現隊列的順序存儲結構隊列的鏈式存儲結構隊列操作的要點16

7、隊列的順序存儲（1）隊列的順序存儲又稱為順序隊列，它也是利用一組地址連續(xù)的存儲單元存放隊列中的元素。為了指示當前隊頭元素和隊尾元素，分別設置了隊頭指針front和隊尾指針rear為了消除順序隊列在進、出隊列過程中可能產生的“假溢出”現象，通常把順序隊列的存儲數組設想成一個環(huán)形數組（稱為循環(huán)隊列），關于如何進隊和出隊，不同教材有不同處理，下面介紹兩種方法17隊列的順序存儲（2）方法一，先將新元素加入到隊尾指針指示的位置，再讓隊尾指針加一，如圖2.3（a）所示。按此方式，隊尾指針指示實際隊尾的下一位置，隊頭指針指示實際隊頭位置。這使得退出或讀取元素都比較方便。方法二，先讓隊尾指針進一，再將新元素加

8、入到隊尾指針指示的位置。如圖2.3（b）所示。若按此方式，要想退出隊頭元素，必須先讓隊頭指針進一，才能取到隊頭元素。18隊列的鏈式存儲鏈式隊列是基于單鏈表的一種存儲表示。鏈式隊列中，隊頭指針指向單鏈表的第一個結點，隊尾指針指向單鏈表的最后一個結點。這意味著若要從隊列中退出一個元素，必須從單鏈表中刪除第一個結點，而存放新元素則應插在單鏈表最后一個結點的后面。鏈式隊列適合于數據元素變動比較大的情形，而且不存在隊列滿而產生溢出的情況。19隊列的操作要點隊列的出隊操作和讀取隊頭元素操作是有區(qū)別的，這一點跟棧類似。循環(huán)隊列中進行插入和刪除操作時，不需要比較和移動任何元素，只需要修改隊尾和隊頭指針，并向隊

9、尾插入元素或從隊頭取出元素。在循環(huán)隊列的進隊運算中需要先判斷隊列是否已滿，退隊或讀取隊頭元素時需要先判斷隊列是否為空。隊列經常用在調度算法中。對于分層結構或圖結構，可用隊列實現逐層處理。最常用的循環(huán)隊列組織采用犧牲一個元素來區(qū)分隊空和隊滿的情況，因此，隊列滿的條件為（rear+1）% maxSize = front20棧和隊列的應用棧在表達式計算中的應用棧在遞歸中的應用隊列的應用21棧在表達式計算中的應用在求解表達式的值時常用到棧，例如后綴表達式的求值運算就可以用棧來解決后綴表達式用棧求解過程：順序掃描每一項，如果該項是操作數，則將其壓入棧中；如果該項是操作符，則連續(xù)從棧中退出兩個操作數y和x

10、，形成運算指令xy，并將計算結果重新壓入棧中，當表達式的所有項都掃描完畢后，棧頂存放的就是最后的計算結果。例如，下圖為后綴表達式ABCD-*+EF/-求值的過程22ABCD-*+EF/- 的計算過程23棧在遞歸中的應用遞歸工作棧的原理遞歸程序每一次遞歸調用自己時，都要創(chuàng)建一個工作記錄，以保存遞歸調用的返回地址、使用的局部變量、傳入的實際參數的副本等。這些工作記錄被組織成棧的形式：每次遞歸調用時，為該層創(chuàng)建的工作記錄放在棧頂，使得存放的信息當前可用；每當退出本層遞歸調用時，相應工作記錄從棧頂刪除，上一層遞歸調用的工作記錄就成為棧頂，從而使得與上一層有關的工作記錄恢復可用。24隊列的應用信息處理中

11、有一大類問題需要逐層或逐行處理。這類問題的處理方法往往是在處理當前層或當前行時，就對下一層或下一行做預處理，待當前層或當前行處理完，就可以解決下一層或下一行了。使用隊列的關鍵是為了保存下一步的處理順序，下面給出一個逐行打印二項展開式 的系數的例子2526數組與特殊矩陣的壓縮存儲二維數組特殊矩陣的壓縮存儲27二維數組二維數組的特點二維數組是最簡單的非線性結構每個數組元素都具有相同的類型數組元素的下標關系具有上下界的約束且下標有序一旦確定了數組每一維的上下界約束，元素的個數就固定下來數組的兩個基本運算按照給定的下標，讀取相應的數組元素的值按照給定的下標，更新相應的數組元素的值28二維數組二維數組的

12、順序存儲有兩種方式將二維數組的所有元素存放到一個連續(xù)的存儲空間當中，一種是行優(yōu)先順序存放，一種是列優(yōu)先順序存放。設一個二維數組Anm如下所示29二維數組行優(yōu)先的順序存儲列優(yōu)先順序存儲30特殊矩陣的壓縮存儲矩陣的壓縮存儲矩陣的存儲表示就是二維數組，數據結構中關心的是如何高效地存儲矩陣元素，從而使矩陣的各種運算能有效地進行在一些矩陣中，存在很多值相同的元素或者是零元素。為了節(jié)省空間，可以對這類矩陣進行壓縮存儲壓縮存儲的含義是為多個值相同的元素只分配一個存儲單元，對零元素不分配單元。假設值相同的元素或零元素在矩陣中的分布有一定的規(guī)律，則稱此類矩陣為特殊矩陣下面講解兩種特殊矩陣的壓縮存儲：對稱矩陣和三

13、對角線矩陣31特殊矩陣的壓縮存儲（對稱矩陣）32特殊矩陣的壓縮存儲（對稱矩陣）33特殊矩陣的壓縮存儲（三對角線矩陣）34例題精講選擇填空題綜合應用題35單選填空題例1 為解決計算機主機與打印機之間速度不匹配的問題，通常設置一個打印數據緩沖區(qū)。主機將要打印輸出的數據依次寫入緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數據，該緩沖區(qū)的邏輯結構應該是（ ）。 A、棧 B、隊列 C、樹 D、圖【解答】 B。通常用于輸入輸出的緩沖區(qū)都是采用先入先出的隊列。36單選填空題例2 設棧S和隊列Q的初始狀態(tài)都為空，元素a,b,c,d,e,f,g依次進入棧S.如果每個元素出棧后立即進入隊列Q，且7個元素出隊的順序為b,

14、d,c,f,e,a,g,則棧S的容量至少是_; A.1 B.2 C.3 D.4 【解答】C。隊列的特點是先進先出，出隊順序和入隊順序一致，即與出棧順序一致。如果用S表示進棧，用X表示出棧，則進棧/出棧序列為下圖由圖知，棧中最多時有3個元素，所以棧的容量最少為337單選填空題例3 將遞歸算法轉換成對應的非遞歸算法時，除了單向遞歸和尾遞歸的情況外，通常用來保存中間結果的是_。 A.鏈表 B.棧 C.隊列 D.順序表【解答】B 。棧的一個典型應用就是在實際遞歸程序時作遞歸工作棧，用于開辟每一層遞歸程序調用時需要的局部變量，實際參數的副本空間和記錄返回上一層調用的返回地址等38單選填空題例4 假設一個

15、循環(huán)隊列QmaxSize的隊頭指針為front，隊尾指針為rear，隊列的最大容量為maxSize，除此之外，該隊列再沒有其他數據成員，則該隊列的隊滿條件是_。A. Q.front = Q.rear B. Q.front+Q.rear = maxSizeC. Q.front = (Q.rear+1) % maxSize D. Q.rear = (Q.front+1) % maxSize【解答】C。既然不能附加任何其他數據成員，只能采用犧牲一個隊列元素的整除取余的方式區(qū)分隊空和隊滿的條件，因此選項C是合理的，選項A是判斷隊列是否為空的條件，其他都是干擾項。39單選填空題例5 在一個二維數組A中，

16、假設每個數組元素的長度為3個存儲單元，行下標i從0到8，列下標j從0到9，從首地址SA開始按行連續(xù)存放。在這種情況下，元素A85的起始地址為_. A.SA+141 B.SA+144 C.SA+222 D.SA+255【解答】D。按照二維數組計算地址（按行優(yōu)先順序）的公式LOC(i,j)=LOC(0,0)+(i*m+j)*L其中，LOC(0,0)=SA，是數組存放首地址，L=3是每個數組元素的長度，m=9-0+1=10是數組的列數。因此有LOC(8,5)=SA+(8*10+5)*3=SA+25540單選填空題例6 設有一個10階的對稱矩陣A1010,采用壓縮存儲方式按行將矩陣中下三角部分的元素存入一堆數組B中，A00存入B0中，則A85在B中的位置是_. A.32 B.33 C.41 D.65【解答】B。如果將對稱矩陣的下三角部分（要求0=i=9,0=j=j)前面總共有1+2+i-1+j=i(i-1)/2+