數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容.ppt

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