兩種存儲結(jié)構(gòu)比較線性表

第三章棧與隊列兩種重要的，限定操作的線性結(jié)構(gòu)。第三章棧與隊列兩種重要的，限定操作的線性結(jié)構(gòu)。1§3.1棧棧的例子：操作系統(tǒng)中中斷現(xiàn)場的保留等。一、定義：限定只能在表尾進行插入或刪除操作的線性表。修改原則：后進先出（LIFO）§3.1棧棧的例子：操作系統(tǒng)中中斷現(xiàn)場的保留等。2練習(xí)：設(shè)進棧順序為1、2、3、4，請說出以下的出棧順序是否可能？A、1234B、4312C、2143D、3214E、3421F、3412練習(xí)：設(shè)進棧順序為1、2、3、4，請說出以下的出棧順序是否可3二、棧的基本操作進棧、出棧、清空、求棧頂元素……

接下來學(xué)習(xí)線索：存儲方式：順序，鏈式行為特征應(yīng)用實例二、棧的基本操作進棧、出棧、清空、求棧頂元素……4三、棧的順序存儲結(jié)構(gòu)數(shù)組定義棧：stack[max]max-1

…10規(guī)定：top指向棧頂元素所在位置初始：top=-1（空棧）空棧：top=-1，出棧下溢棧滿：top=max-1，進棧上溢三、棧的順序存儲結(jié)構(gòu)數(shù)組定義棧：stack[max]max-5進棧：開始top==max-1?top=top+1stack[top]=x結(jié)束上溢處理NY棧的順序存儲結(jié)構(gòu)有棧滿的情況，有可能出現(xiàn)上溢的致命錯誤。多棧共享空間是解決問題的折中方法，但不能完全解決。進棧：開始top==max-1?top=top+1stack6出棧：開始top==-1?x=stack[top]top=top-1結(jié)束下溢處理NY出棧：開始top==-1?x=stack[top]top=t7四、棧的鏈式存儲結(jié)構(gòu)規(guī)定：top指向棧頂元素地址datalink設(shè)指針域指向次頂結(jié)點四、棧的鏈式存儲結(jié)構(gòu)規(guī)定：top指向棧頂元素地址datali8判斷空棧進棧出棧利用鏈式存儲結(jié)構(gòu)存儲棧，可解決棧的致命錯誤——上溢基本操作：判斷空?；静僮鳎?五、棧的應(yīng)用1、遞歸調(diào)用一個子程序調(diào)用自身，稱為遞歸調(diào)用。例：階乘的計算n!=1(n=0,1)n*(n-1)!(n>1)五、棧的應(yīng)用1、遞歸調(diào)用n!=1(n=0,1)n*(n-10五、棧的應(yīng)用2、計算表達式（1）由計算規(guī)則得算符優(yōu)先關(guān)系表3+5*33+5+5θ1：先來的算符θ2：后來的算符=<<<>>>>><>>><>>（\-+）*-+θ1

θ2五、棧的應(yīng)用2、計算表達式=<<<>>>>><>>><>>（11（2）原理兩工作棧：一個算符棧，一個操作數(shù)棧a.讀取到操作數(shù)，直接入操作數(shù)棧b.讀取到運算符，取運算符棧棧頂元素與該算符比較優(yōu)先級：

“<”：讀取符號入運算符棧；

“>”：運算符棧出一元素，操作數(shù)棧出兩元素，運算后，結(jié)果放回操作數(shù)棧；

“=”：運算符棧出一元素，與之相抵消。（2）原理兩工作棧：一個算符棧，一個操作數(shù)棧12（2）原理

算法結(jié)束標志：運算符棧為空，操作數(shù)棧有一元素，即為結(jié)果。（2）原理算法結(jié)束標志：運算符棧為空，操作數(shù)13上機：輸入一包含“(”和“)”的字符串，檢測括號是否匹配（其中括號中能嵌套括號），并輸出括號是否匹配的信息（匹配、缺少左括號、缺少右括號）；上機：輸入一包含“(”和“)”的字符串，檢測括號是否匹配（其14分析：gets(fun)while(fun[i]!=’\0’){if(fun[i]==’(‘)：入棧；if(fun[i]==‘)’)：if?？眨哄e，缺左邊，return；else出棧；i=i+1;}如?？諏Γ。?！否則錯，缺少右邊分析：gets(fun)15§3.2隊列隊列的例子：排隊等。一、定義：限定只能在表的一端進行插入，在表的另一端進行刪除的線性表。修改原則：先進先出（FIFO）§3.2隊列隊列的例子：排隊等。16二、隊列的基本操作進隊、出隊、清空、求隊頭元素……

接下來學(xué)習(xí)線索：存儲方式：鏈式，順序行為特征二、隊列的基本操作進隊、出隊、清空、求隊頭元素……17三、隊列的鏈式存儲結(jié)構(gòu)需設(shè)兩個指針：front：頭結(jié)點地址rear：隊尾結(jié)點地址c∧dba……frontrear三、隊列的鏈式存儲結(jié)構(gòu)需設(shè)兩個指針：c∧dba……front18基本操作：rear=front；front->link=NULL;∧frontrear1、初始化隊列2、進隊從隊尾進隊列基本操作：rear=front；∧frontrear1、初始19基本操作：2、進隊從隊尾進隊列3、出隊只要隊列不空，從隊頭出；被刪除結(jié)點如為隊尾結(jié)點，隊列置空?；静僮鳎?、進隊20四、隊列的順序存儲結(jié)構(gòu)數(shù)組定義隊列：queue[max]max-1

…10規(guī)定：front指向隊頭元素位置rear指向隊尾元素的下一個空位初始：front=rear=0隊空：front=rear隊滿：rear=max四、隊列的順序存儲結(jié)構(gòu)數(shù)組定義隊列：queue[max]ma21四、隊列的順序存儲結(jié)構(gòu)假溢出的問題：用循環(huán)隊列來解決下一個rear計算公式：rear=（rear+1）modmax循環(huán)隊列隊空隊滿標志沖突的問題：以犧牲一個存儲空間為代價，當判斷到（下一個rear==front）時，即認為隊滿。實際上，max個空間只存放了（max-1）個元素四、隊列的順序存儲結(jié)構(gòu)假溢出的問題：用循環(huán)隊列來解決循環(huán)隊列22循環(huán)隊列隊空、隊滿標志：隊滿：（rear+1）modmax==front隊空：front=rear

沖突解決??！循環(huán)隊列隊空、隊滿標志：23練習(xí)：設(shè)循環(huán)隊列容量為70（序號0~69），現(xiàn)經(jīng)過一系列的入隊和出隊后，問下列情況下循環(huán)隊列中各有幾個元素？（1）front=14，rear=21（2）front=23，rear=12練習(xí)：設(shè)循環(huán)隊列容量為70（序號0~69），現(xiàn)經(jīng)過一系列的入24§3.3兩種存儲結(jié)構(gòu)比較（線性表）：順序存儲（數(shù)組）：思想簡單，靜態(tài)管理，定位方便；但會有溢出問題，有時會有大量冗余，系統(tǒng)開銷大。鏈式存儲（鏈表）：操作方便，無冗余，解決溢出問題。§3.3兩種存儲結(jié)構(gòu)比較（線性表）：順序存儲（數(shù)組）：25兩個限定操作、用途廣泛的線性表：堆棧：LIFO隊列：FIFO兩個限定操作、用途廣泛的線性表：26設(shè)有一順序棧S，元素s1,s2,s3,s4,s5,s6依次入棧，如果出棧順序為s2,s3,s4,s6,s5,s1，棧的容量至少為（）。A.2 B.3C.5 D.6練習(xí):B設(shè)有一順序棧S，元素s1,s2,s3,s4,s5,s6依次入27設(shè)有一棧已有a1,a2,a3三個元素,棧頂為a3,a4正等待入棧,則以下序列是不可能的出棧序列是()。A.a3,a1,a4,a2 B.a3,a2,a4,a1C.a3,a4,a2,a1 D.a4,a3,a2,a1A設(shè)有一棧已有a1,a2,a3三個元素,棧頂為a3,a4正等待28()在鏈隊中,即使不設(shè)置尾指針也能進行入隊操作;()在帶頭結(jié)點的鏈隊中進行出隊操作,不會改變頭結(jié)點地址front的值;()循環(huán)隊列中元素個數(shù)為rear-frontTTF()在鏈隊中,即使不設(shè)置尾指針也能進行入隊操作;TTF29以S和X分別代表入棧和出棧，對輸入序列a、b、c、d、e進行一系