數據結構課程的內容.ppt

1,數據結構課程的內容,2,討論：,已知L是無表頭結點的單鏈表，且P結點既不是首元結點，也不是尾元結點，請寫出在P結點后插入S結點的核心語句序列。 答：此題答案不唯一。,法二：已知P結點，則不必“順藤摸瓜”，直接鏈接即可。 (4) S-next=P-next; (1) P-next=S;,法一：從頭“摸”起： (7) Q=P; (11) P=L; (8) while(P-next!=Q)P=P-next; (10) P=Q; (4) S-next=P-next; (1) P-next=S;,3,3.1 棧（Stack）,第三章 棧和隊列,3.2 隊列（Queue）,1. 定義 2. 邏輯結構 3. 存儲結構 4. 運算規(guī)則 5. 實現(xiàn)方式,1. 定義 2. 邏輯結構 3. 存儲結構 4. 運算規(guī)則 5. 實現(xiàn)方式,4,1. 定義,3.1 棧,與同線性表相同，仍為一對一關系。,用順序棧或鏈棧存儲均可，但以順序棧更常見,只能在棧頂運算，且訪問結點時依照后進先出（LIFO）或先進后出（FILO）的原則。,關鍵是編寫入棧和出棧函數，具體實現(xiàn)依順序?；蜴湕５牟煌煌?基本操作有入棧、出棧、讀棧頂元素值、建棧、或判斷棧滿、?？盏?。,限定只能在表的一端進行插入和刪除運算的線性表（只能在棧頂操作）,5,問：堆棧是什么？它與一般線性表有什么不同？,3.1 棧,答：堆棧是一種特殊的線性表，它只能在表的一端（即棧頂）進行插入和刪除運算。 與一般線性表的區(qū)別：僅在于運算規(guī)則不同。,一般線性表 堆棧 邏輯結構：一對一 邏輯結構：一對一 存儲結構：順序表、鏈表 存儲結構：順序棧、鏈棧 運算規(guī)則：隨機存取 運算規(guī)則：后進先出(LIFO),“進” 壓入=PUSH（x) “出” 彈出=POP ( y ),6,棧 是僅在表尾進行插入、刪除操作的線性表。 表尾(即 an 端)稱為棧頂 top ; 表頭(即 a1 端)稱為棧底base,例如： 棧 s= (a1 , a2 , a3 , .,an-1 , an ),a1 稱為 棧底元素 an 稱為 棧頂元素,插入元素到棧頂（即表尾）的操作，稱為入棧。 從棧頂（即表尾）刪除最后一個元素的操作，稱為出棧。,教材P44對棧有更詳細定義：,強調：插入和刪除都只能在表的一端（棧頂）進行！,7,順序棧示意圖,8,表和棧的操作區(qū)別對線性表 s= (a1 , a2 , . , an-1 , an ),寫入：vi= ai 讀出： x= vi,壓入：PUSH (an+1) 彈出： POP (x),前提：一定要預設棧頂指針top！,an+1,9,入棧操作例如用堆棧存放（A，B，C，D） （注意要遵循“后進先出” 原則）,A,A,C B A,B A,核心語句： top=L;,順序棧中的PUSH函數 status Push(ElemType x) if(topM)上溢 else vtop+=x; ,Push (B);,Push (C);,Push (D);,低地址L,Push (A);,高地址M,B,C,D,10,出棧操作例如從棧中取出B （注意要遵循“后進先出” 原則）,核心語句： Pop ( ); Pop ( ); Printf( Pop () );,順序棧中的POP函數 status Pop( ) if(top=L) 下溢 else y=v-top; return(y); ,11,例1：一個棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實現(xiàn)嗎？12345的輸出呢？,43512不可能實現(xiàn)，主要是其中的12順序不能實現(xiàn)； 12345的輸出可以實現(xiàn)，只需壓入一個立即彈出一個即可。,435612中到了12順序不能實現(xiàn)； 135426可以實現(xiàn)。,例2：如果一個棧的輸入序列為123456，能否得到435612和135426的出棧序列？,答：,答：,12,例3（嚴題集3.1）一個棧的輸入序列為123，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？,答：,可以通過窮舉所有可能性來求解： 1入1出， 2入2出，3入3出， 即123； 1入1出， 2、3入3、2出， 即132； 1、2入，2出， 3入3出， 即231； 1、2入，2、1出，3入3出， 即213； 1、2、3入，3、2、1出， 即321； 合計有5種可能性。,13,例4：計算機系2001年考研題（程序設計基礎）,設依次進入一個棧的元素序列為c，a，b，d，則可得到出棧的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，b,A、D可以（ B、C不行）。,討論：有無通用的判別原則？ 有。在可能的輸出序列中，不存在這樣的輸入序列i，j，k，能同時滿足 ijk 和 PjPkPi,答：,14,補充1： 若入棧動作使地址向高端增長，稱為“向上生成”的棧； 若入棧動作使地址向低端增長，稱為“向下生成”的棧； 對于向上生成的棧 入?？谠E：堆棧指針top先壓后加（vtop+=x）； 出?？谠E：堆棧指針top先減后彈（y=v-top) 。,3.1 棧,補充2： 棧不存在的條件： base=NULL; 棧為空 的條件 ： base=top; 棧滿的條件 ： top-base=stacksize;,15,補充3：鏈棧 鏈棧示意圖,16,鏈棧的入棧函數、出棧函數 （以頭指針為棧頂，在頭指針處插入或刪除?。?公共說明部分： typedef struct snode SElemType data; struct snode *link; NODE; NODE *st, *p; int m=sizeof(NODE);,17,Push (SElemType x) p=(NODE*)malloc(m); if(!p)上溢 else p-data=x; p-link=st; st=p; ,Status pop( ) if(st=NULL)下溢 elsey=st-data;p=st;st=st-link; free(p); return(y); ,鏈棧 入棧函數,鏈棧 出棧函數,插入表頭,從表頭刪除,18, 鏈棧不必設頭結點，因為棧頂（表頭）操作頻繁； 采用鏈棧存儲方式，可使多個棧共享空間；當棧中元素個數變化較大，且存在多個棧的情況下，鏈棧是棧的首選存儲方式。,說 明,19,問：為什么要設計堆棧？它有什么獨特用途？,調用函數或子程序非它莫屬； 遞歸運算的有力工具； 用于保護現(xiàn)場和恢復現(xiàn)場； 簡化了程序設計的問題。,答：,20,數制轉換（十轉N） P48 設計思路：用棧暫存低位值 例2：括號匹配的檢驗P49 設計思路：用棧暫存左括號 例3 ：表達式求值 -P52 設計思路：用棧暫存運算符 例4：漢諾儀（Hanoi）塔-P55 設計思路：用棧實現(xiàn)遞歸調用,例1：,21,例3 表達式求值 ( 這是棧應用的典型例子 ) 這里，表達式求值的算法是 “算符優(yōu)先法”。,例如：3*（7 2 ） （1）要正確求值，首先了解算術四則運算的規(guī)則： a. 從左算到右 b. 先乘除，后加減 c. 先括號內，后括號外 由此，此表達式的計算順序為： 3*（7 2 ）= 3 * 5 = 15,22,（2）根據上述三條運算規(guī)則，在運算的每一步中，對任意相繼出現(xiàn)的算符1和2 ，都要比較優(yōu)先權關系。 算符優(yōu)先法所依據的算符間的優(yōu)先關系見教材P53表3.1 （是提供給計算機用的表！） 由表可看出，右括號 ) 和井號 # 作為2時級別最低； 由c 規(guī)則得出： * ，/， + ，-為1時的優(yōu)先權低于（，高于） 由a規(guī)則得出：（=） 表明括號內運算，已算完。 # = # 表明表達式求值完畢。,棧的應用（表達式求值）,23,（3）算法思想： 設定兩棧：操作符棧 OPTR ，操作數棧 OPND 棧初始化：設操作數棧 OPND 為空；操作符棧 OPTR 的棧底元素為表達式起始符 #； 依次讀入字符：是操作數則入OPND棧，是操作符則要判斷： if 操作符 棧頂元素，壓入OPTR棧。,棧的應用（表達式求值）,24,棧的應用（表達式求值）,25,Status EvaluateExpression( OperandType /EvaluateExpression,此函數在哪里？,26,例4 漢諾儀（ Hanoi）塔 傳說在創(chuàng)世紀時，在一個叫Brahma的寺廟里，有三個柱子，其中一柱上有64個盤子從小到大依次疊放，僧侶的工作是將這64個盤子從一根柱子移到另一個柱子上。 移動時的規(guī)則： 每次只能移動一個盤子； 只能小盤子在大盤子上面； 可以使用任一柱子。 當工作做完之后，就標志著世界末日到來。,分析： 設三根柱子分別為 x，y, z , 盤子在 x 柱上，要移到 z 柱上。 1、當 n=1 時，盤子直接從 x 柱移到 z 柱上； 2、當 n1 時, 則設法將 前 n 1 個盤子 借助 z ，從 x 移到 y 柱上，把 盤子 n 從 x 移到 z 柱上； 把n 1 個盤子 從 y 移到 z 柱上。,n,n 1,27,Void Hanoi ( int n, char x, char y, char z ) /將 n 個 編號從上到下為 1n 的盤子從 x 柱，借助 y 柱移到 z 柱 if ( n = = 1 ) move ( x , 1 , z ) ; /將編號為 1 的盤子從 x 柱移到 z 柱 else /將 n -1個 編號從上到下為1n-1的盤子從 x 柱，借助 y 柱移到 z 柱 Hanoi ( n-1 , x , z , y ) ; move ( x , n, z) ; /將編號為 n 的盤子從 x 柱移到 z 柱 /將 n -1個 編號從上到下為 1n-1的盤子從 y 柱，借助 x 柱移到 z 柱 Hanoi ( n-1 , y , x , z ); /Hanoi,28,定 義,3.2 隊列,與同線性表相同，仍為一對一關系。,順序隊或鏈隊，以循環(huán)順序隊更常見。,只能在隊首和隊尾運算，且訪問結點時依照先進先出（FIFO）的原則。,關鍵是掌握入隊和出隊操作，具體實現(xiàn)依順序隊或鏈隊的不同而不同。 基本操作有入隊或出隊，建空隊列，判隊空或隊滿等操作。,只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表 （頭刪尾插）,29,隊列 （Queue）是僅在表尾進行插入操作，在表頭進行刪除操作的線性表。 表尾即 an 端，稱為 隊尾 ； 表頭即 a1 端，稱為隊頭。 它是一種先進先出（）的線性表。,例如：隊列 Q= (a1 , a2 , a3 , .,an-1 , an ),插入元素稱為入隊；刪除元素稱為出隊。,隊頭,隊尾,教材P59對隊列有更詳細定義：,隊列的抽象數據類型定義見教材5960 隊列的存儲結構為鏈隊或順序隊 （常用循環(huán)順序隊）,30,鏈隊列示意圖,討論： 空隊列的特征？, 怎樣實現(xiàn)入隊和出隊操作？ 入隊（尾部插入）：rear-next=S; rear=S; 出隊（頭部刪除）：front-next=p-next;,完整動作設計參見教材P61-62, 隊列會滿嗎？,front=rear,一般不會，因為刪除時有free動作。除非內存不足！,31,順序隊示意圖,(隊尾),(隊首), 隊列會滿嗎？ 很可能會，因為數組前端空間無法釋放。因此數組應當有長度限制。, 空隊列的特征？ 約定：front=rear,隊尾后地址,入隊(尾部插入)：vrear=e; rear+; 出隊(頭部刪除)：x=vfront; front+;,討論：,假溢出,有缺陷, 怎樣實現(xiàn)入隊和出隊操作？,3.2 隊列,32,問：什么叫“假溢出” ？如何解決？,答：在順序隊中，當尾指針已經到了數組的上界，不能再有入隊操作，但其實數組中還有空位置，這就叫“假溢出”。,3.2 隊列,解決假溢出的途徑采用循環(huán)隊列,33,循環(huán)隊列（臆造）,順序隊列,新問題：在循環(huán)隊列中，空隊特征是front=rear；隊滿時也會有front=rear；判決條件將出現(xiàn)二義性！ 解決方案有三： 加設標志位，讓刪除動作使其為1,插入動作使其為0,則可識別當前 front=rear 使用一個計數器記錄隊列中元素個數（即隊列長度）； 人為浪費一個單元，令隊滿特征為front=(rear+1)%N；,34,隊空條件 : front = rear (初始化時：front = rear ) 隊滿條件： front = (rear+1) % N (N=maxsize) 隊列長度：L=（Nrearfront）% N,選用空閑單元法：即front和rear之一指向實元素，另一指向空閑元素。,問2： 在具有n個單元的循環(huán)隊列中，隊滿時共有多少個元素？,n-1個,6,問1：左圖中隊列長度L=？,35,例1： 一循環(huán)隊列如下圖所示，若先刪除4個元素，接著再插入4個元素，請問隊頭和隊尾指針分別指向哪個位置?,解：由圖可知，隊頭和隊尾指針的初態(tài)分別為front=1和rear=6。,刪除4個元素后front=5；再插入4個元素后，r=(6+4)%6=4,36,例2 ：數組n用來表示一個循環(huán)隊列，f 為當前隊列頭元素的前一位置，r 為隊尾元素的位置。假定隊列中元素的個數小于n，計算隊列中元素的公式為:,（） rf （）（nfr）% n （）nrf （） （nrf）% n,4種公式哪種合理？ 當 r f 時（A）合理； 當 r f 時（C）合理；,分析 ：,綜合2種情況，以（D）的表達最為合理,例3：在一個循環(huán)隊列中，若約定隊首指針指向隊首元素的前一個位置。那么，從循環(huán)隊列中刪除一個元素時，其操作是 先 ，后 。,移動隊首指針,取出元素,37,問：為什么要設計隊列？它有什么獨特用途？,離散事件的模擬（模擬事件發(fā)生的先后順序）； 操作系統(tǒng)中多道作業(yè)的處理（一個CPU執(zhí)行多個作業(yè)）； 3. 簡化程序設計。,答：,循環(huán)隊列的操作實現(xiàn)見教材P64,38,循環(huán)隊列的操作實現(xiàn),1）初始化一空隊列,算法要求：生成一空隊列 算法操作：為隊列分配基本容量空間 設置隊列為空隊列， 即 front=rear=0（也可為任意單元，如 2，或 4）;,39,算法：,Status InitQueue ( SqQueue ,新開單元的地址為0則表示內存不足,40,算法說明：向循環(huán)隊列的隊尾插入一個元素 分 析： (1) 插入前應當先判斷隊列是否