第3次-第2章-線性表及其順序存儲

1、第2章 線性表及其順序存儲盧芳芳free-計算機科學與技術學院線性表順序表棧隊列 線性表是一種常用的數(shù)據(jù)結(jié)構(gòu)，本章介紹線性表及其順序存儲，并對棧和隊列及它們的順序?qū)崿F(xiàn)給出了詳細的設計描述。 2.1線性表 在非空的線性表，有且僅有一個開始結(jié)點a1，它沒有直接前趨，而僅有一個直接后繼a2；有且僅有一個終端結(jié)點an，它沒有直接后繼，而僅有一個直接前趨an-1；其余的內(nèi)部結(jié)點ai(2in-1)都有且僅有一個直接前趨ai-1和一個直接后繼ai+1。 線性表是一種典型的線性結(jié)構(gòu)。2.2.1順序表 線性表采用順序存儲的方式存儲就稱之為順序表。順序表是將表中的結(jié)點依次存放在計算機內(nèi)存

2、中一組地址連續(xù)的存儲單元中。 2.2順序表順序表的存儲結(jié)構(gòu)如下圖所示： 結(jié)點序號 1 2 i n len len len lenk1k2k ik n內(nèi)存狀況 存儲地址 location(k1) location(k1)+(i-1)l en 順序表的存儲結(jié)構(gòu)的C語言描述如下：/*順序表的頭文件，文件名sequlist.h */ #define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int size; sequence_list;表長順序表的幾個基本操作的具體實現(xiàn) ：/ 函數(shù)功能:順序表的初始化置空表

3、 / 函數(shù)參數(shù):指向sequence_list型變量的指針變量slt / 函數(shù)返回值:空 / 文件名:sequlist.c, 函數(shù)名:init() / void init(sequence_list slt) slt-size=0; 算法2.1順序表的初始化-置空表/ 函數(shù)功能:在順序表后部進行插入操作 / 函數(shù)參數(shù):指向sequence_list型變量的指針變量slt / datatype類型的變量x / 函數(shù)返回值:空 / 文件名:sequlist.c, 函數(shù)名:append() / void append(sequence_list slt,datatype x) if(slt-size

4、=MAXSIZE) printf(順序表是滿的!);exit(1); slt-aslt-size=x; slt-size=slt-size+1; 算法2.2 在順序表后部進行插入操作打印順序表的各結(jié)點值 / 函數(shù)功能:打印順序表的各結(jié)點值 / 函數(shù)參數(shù):sequence_list型變量slt / 函數(shù)返回值:空 / 文件名:sequlist.c, 函數(shù)名:display() / void display(sequence_list slt) int i; if(!slt.size) printf(n順序表是空的!); else for(i=0;islt.size;i+) printf(%5d,

5、slt.ai); 算法2.3 打印順序表的各結(jié)點值判斷順序表是否為空 / 函數(shù)功能:判斷順序表是否為空 / 函數(shù)參數(shù):sequence_list型變量slt / 函數(shù)返回值:int類型。1表示空,0表示非空 / 文件名:sequlist.c,函數(shù)名:empty() / int empty(sequence_list slt) return(slt.size=0 ? 1:0); 算法2.4 判斷順序表是否為空查找順序表中值為x的結(jié)點位置 / 函數(shù)功能:查找順序表中值為x的結(jié)點位置 / 函數(shù)參數(shù):sequence_list型變量slt,datatype型變量x / 函數(shù)返回值:int類型。返回x的

6、位置值,-1表示沒找到 / 文件名:sequlist.c,函數(shù)名:find() / int find(sequence_list slt,datatype x) int i=0; while( islt.size&slt.ai!=x ) i+; return(islt.size? i:1); 算法2.5 查找順序表中值為x的結(jié)點位置 取得順序表中第i個結(jié)點的值 / 函數(shù)功能:取得順序表中第i個結(jié)點的值 / 函數(shù)參數(shù):sequence_list型變量slt,int型變量i / 函數(shù)返回值:datatype類型。返回第i個結(jié)點的值 / 文件名:sequlist.c,函數(shù)名:get() / data

7、type get(sequence_list slt,int i) if(i=slt.size) printf(n指定位置的結(jié)點不存在!);exit(1); else return slt.ai; 算法2.6 取得順序表中第i個結(jié)點的值 順序表的插入運算是將一個值為x的結(jié)點插入到順序表的第i個位置0in，即將x插入到ki-1和ki之間，如果i=n，則表示插入到表的最后，一般地可表示為：插入前：k0, k1, , ki-1, ki, , kn-1插入后：k0, k1, , ki-1,x, ki, , kn-1 插入過程的圖示見下圖： k ik0k1k i-1k n-1k0k1k i-1k n-1

8、xk i后移開始位置后移結(jié)束位置插入前插入后/ 函數(shù)功能:在順序表的position位置插入值為x的結(jié)點 / 函數(shù)參數(shù):指向sequence_list型變量的指針變量slt / datatype型變量x,int型變量 position / 函數(shù)返回值:空 文件名:sequlist.c,函數(shù)名:insert() / void insert(sequence_list slt,datatype x,int position) int i; if(slt-size=MAXSIZE) printf(n順序表是滿的!沒法插入!);exit(1); if(positionslt-size) printf(

9、n指定的插入位置不存在!);exit(1); for(i=slt-size;iposition;i-) slt-ai=slt-ai1; slt-aposition=x; slt-size+; 算法2.7 在順序表的position位置插入值為x的結(jié)點 算法2.7中，所花費的時間主要是元素后移操作，對于在第i個位置上插入一個新的元素，需要移動（n-i）個元素，設在第i個位置上插入一個元素的概率為pi，且在任意一個位置上插入元素的概率相等，即p0=p1=p2=pn=1/(n+1)，則在一個長度為n的順序表中插入一個元素所需的平均移動次數(shù)為： 即在長度為n的順序表中插入一個元素平均需要移動表中的一半

10、元素。該算法的時間復雜度為O（n）。 順序表的刪除操作是指刪除順序表中的第i個結(jié)點，0in-1，一般地可表示為： 刪除前：k0, k1, , ki-1, ki, ki+1, , kn-1 刪除后：k0, k1, , ki-1, ki+1, , kn-1 刪除過程的圖示見下圖 ：k ik0k1k i-1k n-1k0k1k i-1k n-1k i+1前移結(jié)束位置前移開始位置刪除前刪除后k i+1刪除操作的具體實現(xiàn)見算法2.8 / 函數(shù)功能:刪除順序表中第position位置的結(jié)點 / 函數(shù)參數(shù):指向sequence_list型變量的指針變量slt / int型變量 position / 函數(shù)返回

11、值:空 文件名:sequlist.c,函數(shù)名:dele() / void dele(sequence_list slt,int position) int i; if(slt-size=0) printf(n順序表是空的!);exit(1); if(position=slt-size) printf(n指定的刪除位置不存在!);exit(1); for(i=position;isize-1;i+) slt-ai=slt-ai+1; slt-size-; 算法2.8 刪除順序表中第position位置的結(jié)點 要刪除順序表中的第i個結(jié)點，則需要移動（n-i-1）個元素，設刪除表中第i個結(jié)點的概率為

12、qi，且在表中每一個位置刪除的概率相等，即：q0=q1=qn-1=1/n 則在一個長度為n的順序表中刪除一個結(jié)點的平均移動次數(shù)為： 這表明，在一個長為n的順序表中刪除一個元素平均需要移動表中大約一半的元素。該算法的時間復雜度為O（n）。 棧2.3 棧 2.3.1棧 棧是一種特殊的線性表，對于這種線性表規(guī)定它的插入運算和刪除運算均在線性表的同一端進行，進行插入和刪除的那一端稱為棧頂，另一端稱為棧底。棧的插入操作和刪除操作也分別簡稱進棧和出棧。 如果棧中有n個結(jié)點k0, k1, k2, , kn-1，k0為棧底，kn-1是棧頂，則棧中結(jié)點的進棧順序為k0, k1, k2, , kn-1，而出棧的順

13、序為kn-1, kn-2, , k1, k0。如圖所示。 棧具有后進先出或先進后出（FILO,First In Last Out）的性質(zhì) k0k1k n-1棧頂棧底 出棧 進棧2.3.2順序棧及其實現(xiàn) 棧的順序存儲方式就是在順序表的基礎上對插入和刪除操作限制它們在順序表的同一端進行，所以同順序表一樣也可用一維數(shù)組表示。 一般地，可以設定一個足夠大的一維數(shù)組存儲棧，數(shù)組中下標為0的元素就是棧底，對于棧頂，可以設一個指針top指示它。 為了方便，設定top所指的位置是下一個將要插入的結(jié)點的存儲位置，這樣，當top=0時就表示是一個空的棧。一個棧的幾種狀態(tài)以及在這些狀態(tài)下棧頂指針top和棧中結(jié)點的關

14、系如下圖所示。 k0k1k0k2k1k 數(shù)組下標 數(shù)組下標 數(shù)組下標MAXSIZE-1 MAXSIZE-1 MAXSIZE-12 top 2 21 1 1 top 0 0 0top (a)空棧 (b)有兩個結(jié)點的棧 (c)棧已滿棧的順序存儲結(jié)構(gòu)的C語言描述如下：/ 棧（順序存儲）的頭文件 / 文件名seqstack.h / #define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int top; sequence_stack;下面是順序存儲棧的幾個基本操作的具體實現(xiàn) / 函數(shù)功能:棧（順序存儲）初始

15、化 / 函數(shù)參數(shù):指向sequence_stack型變量的指針變量st / 函數(shù)返回值:空 / 文件名:seqstack.c,函數(shù)名:init() / void init(sequence_stack st) st-top=0; 算法2.9棧（順序存儲）初始化 說明:top=0表示?？眨@種情況下棧頂指示位內(nèi)容始終為空。/ 函數(shù)功能:判斷棧（順序存儲）是否為空 / 函數(shù)參數(shù):sequence_stack型變量st / 函數(shù)返回值:int類型。1表示空,0表示非空 / 文件名:seqstack.c,函數(shù)名:empty() / int empty(sequence_stack st) return

16、(st.top? 0:1); 算法2.10判斷棧（順序存儲）是否為空 / 函數(shù)功能:讀棧頂（順序存儲）結(jié)點值 / 函數(shù)參數(shù):sequence_stack型變量st / 函數(shù)返回值:datatype類型。返回棧頂結(jié)點值 / 文件名:seqstack.c,函數(shù)名:read() / datatype read(sequence_stack st) if (empty(st) printf(n棧是空的!);exit(1); else return st.ast.top-1; 算法2.11 取得棧頂（順序存儲）結(jié)點值順序棧的進棧與出棧操作下圖表明進出棧情況。543210top（a）空棧543210top

17、A（b）A進棧543210-1topA（c）B、C、D進棧BCDtoptoptop543210A（d）D,C出棧BCDtop543210（e）E進棧ABCDtopEtop543210ABEDtop（f）E、B、A出棧toptop/ 函數(shù)功能:棧（順序存儲）的插入（進棧）操作 / 函數(shù)參數(shù):指向sequence_stack型變量的指針變量st / datatype型變量x / 函數(shù)返回值:空 / 文件名:seqstack.c,函數(shù)名:push() / void push(sequence_stack st,datatype x) if(st-top=MAXSIZE) printf(nThe se

18、quence stack is full!);exit(1); st-ast-top=x; st-top+; 算法2.12 棧（順序存儲）的插入操作 / 函數(shù)功能:棧（順序存儲）的刪除（出棧）操作 / 函數(shù)參數(shù):指向sequence_stack型變量的指針變量st / 函數(shù)返回值:空 / 文件名:seqstack.c,函數(shù)名pop() / void pop(sequence_stack st) if(st-top=0) printf(nThe sequence stack is empty!);exit(1); st-top-; 算法2.13棧（順序存儲）的刪除操作 思考:如果將?？毡硎緸閠o

19、p=-1,則所有棧的所有操作為何變化呢?2.3.3棧的應用之一-括號匹配 設一個表達式中可以包含三種括號：小括號、中括號和大括號，各種括號之間允許任意嵌套，如小括號內(nèi)可以嵌套中括號、大括號，但是不能交叉。舉例如下：()正確的() 正確的()正確的()不正確的() 不正確的 如何去檢驗一個表達式的括號是否匹配呢？大家知道當自左向右掃描一個表達式時，凡是遇到的開括號（或稱左括號）都期待有一個和它對應的閉括號（或稱右括號）與之匹配。 按照括號正確匹配的規(guī)則，在自左向右掃描一個表達式時，后遇到的開括號比先遇到的開括號更加期待有一個閉括號與之匹配。（后進先出） / 函數(shù)功能:判斷表達式括號是否匹配 /

20、函數(shù)參數(shù):char類型數(shù)組c / 函數(shù)返回值:int類型。返回1為匹配,返回0為不匹配 / 文件名:seqmatch.c,函數(shù)名:match_kouhao() /int match_kuohao(char c) int i=0; sequence_stack s; init(&s); while(ci!=#) switch(ci) case : case : case (:push(&s,ci);break; case :if(!empty(s)&read(s)= ) pop(&s);break; else return 0; case :if(!empty(s)&read(s)= ) pop

21、(&s);break; else return 0; case ):if(!empty(s)&read(s)=( ) pop(&s);break; else return 0; i+; return (empty(s); /棧為空則匹配,否則不匹配/ 算法2.14 判斷表達式括號是否匹配 算術表達式通常是由操作數(shù)、算術運算符和一對圓括號“（”和“）”組合而成。其中操作數(shù)允許是程序語言中任意合法的變量名或常數(shù)。 以下我們討論+、-、*、/四種算術運算。表達式求值中的首要問題：如何確定表達式中所含運算的計算次序。算術運算的規(guī)則：1）先括號內(nèi)、后括號外2）先乘除、后加減3）從左算到右2.3.4棧的應

22、用之二-算術表達式求值 方法1：加括號，即對每個一運算都用一對括號將與其配對的左、右操作對象括在一起，由此上面算術表達式將寫成（A+（B*（C+D）利用棧求表達式的值：1）自左至右的掃描加括號的算術表達式2）將非右括號“）”的符號進棧3）每當遇見右括號“）”，從棧頂向下掃描至第一個左括號“（”，這就是和遇見的右括號“）”配對的左括號“（”，該左括號“（”上面的表達式就是現(xiàn)在應該計算的表達式，從棧中彈出對應的左括號“（”以上的所有符號（含左括號”（“），計算相應表達式，并將結(jié)果壓入棧中。重復1）2）3）即可計算出表達式的值。特點：方法簡單明了，但要求人們事先為要計算的表達式加好括號，這既繁瑣，又

23、易出錯。方法2：重新改寫表達式為后綴表達式。在計算機中，表達式可以有三種不同的標識方法設 Exp = S1 + OP + S2則稱 OP + S1 + S2 為表達式的前綴表示法 稱 S1 + OP + S2 為表達式的中綴表示法 稱 S1 + S2 + OP 為表達式的后綴表示法 可見，它以運算符所在不同位置命名的。例： 中綴表達式 后綴表達式 （1） A A （2） A+B AB+ （3） A+B*C ABC*+ （4） A*（B-C）+D ABC-*D+ （5） D+A/（B-C） DABC-/+算法：將中綴表達式轉(zhuǎn)換為后綴表達式根據(jù)中綴表達式與后綴表達式的特點，可得將中綴表達式變換為后

24、綴表達式的方法：1）操作數(shù)的排列次序不變2）把每一運算符從第二操作數(shù)之前排到第二操作數(shù)之后3）刪去所有括號關鍵問題：如何找到一個運算符的第二個操作數(shù)的結(jié)束位置？算法：利用后綴表達式求值基本思想：1）從左到右掃描后綴表達式，遇到操作對象進棧。2）遇到運算符，彈出棧頂?shù)脑兀渲袟ｍ敒榈诙僮鲗ο?，次棧頂為第一操作對象，對其按遇到的運算符進行運算，并將結(jié)果進棧。重復上述動作最后即可求出表達式的值。例如有中綴表達式：A/B-（C+D）*E其對應的后綴表達式為：AB/CD+E*-利用后綴表達式求值過程如下所示：步驟 操作數(shù)棧 后綴表達式 說明1 AB/CD+E*-# 初始?？?，A進棧2 A AB/CD

25、+E*-#B進棧3 AB AB/CD+E*-#遇/，彈出棧頂兩元素做A/B= ，并將其進棧4 AB/CD+E*-# C進棧5 C AB/CD+E*-# D進棧9 AB/CD+E*-# 8 E AB/CD+E*-# 7 AB/CD+E*-# 6 CD AB/CD+E*-# 步驟 操作數(shù)棧 后綴表達式 說明遇+，彈出CD做 C+D= ，并將其進棧E進棧遇*，彈出棧頂兩元做 *E= ，并將結(jié)果進棧遇-，彈出棧頂二元做 - = ，并將結(jié)果進棧10 AB/CD+E*-# 遇#，結(jié)束，棧頂就是表達式的計算結(jié)果習題:數(shù)制轉(zhuǎn)換問題 十進制n和其它進制數(shù)的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題，其解決方法很多，其中一個

26、簡單算法基于下列原理: n=(n div d)*d+n mod d ( 其中:div為整除運算,mod為求余運算) 例如 (1348)10=(2504)8，其運算過程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2倒取余數(shù)(1348)10=(2504)8例用棧的知識實現(xiàn)任意正的10進制整數(shù)到其它進位制的轉(zhuǎn)換程序。算法設計題:2、回文是指正讀和反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文，試寫一個算法判定給定的字符向量是否為回文。 void conversion( ) init(s); scanf

27、 (“%d”,&n); while(n) /余數(shù)進棧 push(&s,n%8); n=n/8; while(! Stackempty(s) e=pop(&s); /余數(shù)出棧 printf(“%d”,e); 習題一解答:隊列2.4 隊列 2.4.1 隊列 隊列是一種特殊的線性表，它的特殊性在于隊列的插入和刪除操作分別在表的兩端進行。插入的那一端稱為隊尾，刪除的那一端稱為隊首。隊列的插入操作和刪除操作也分別簡稱進隊和出隊。 對于一個隊列：k0, k1, k2, , kn-1則k0是這些結(jié)點中最先插入的結(jié)點，若要做刪除操作，k0將首先被刪除，所以說，隊列是具有“先進先出”（FIFO,First In

28、 First Out）特點的線性結(jié)構(gòu)。 隊列類型的描述如下：ADT sequence_queue 數(shù)據(jù)集合K:K=k1,k2,kn,n0,K中的元素是datatype類型; 數(shù)據(jù)關系R:R=r r= | i=1,2,n1。 操作集合: （1）void init (sequence_queue sq) 隊列（順序存儲）初始化; （2）int empty (sequence_queue sq) 判斷隊列（順序存儲）是否為空; （3）void display (sequence_queue sq) 打印隊列（順序存儲）的結(jié)點值; （4）datatype get(sequence_queue sq)

29、取得隊列（順序存儲）的隊首結(jié)點值; （5）void insert(sequence_queue sq,datatype x) 隊列（順序存儲）的插入操作; （6）void dele(sequence_queue sq) 隊列（順序存儲）的刪除操作。 ADT sequence_queue;2.4.2順序隊列及其實現(xiàn) 隊列的順序存儲在C語言中可以用一維數(shù)組表示，為了標識隊首和隊尾，需要附設兩個指針front和rear，front指示的是隊列中最前面，即隊首結(jié)點在數(shù)組中元素的下標，rear指示的是隊尾結(jié)點在數(shù)組中元素的下標的下一個位置，也就是說rear指示的是即將插入的結(jié)點在數(shù)組中的下標。 隊列的幾

30、種狀態(tài) ：隊首、隊尾指針 front rear 數(shù)組下標 0 1 MAXSIZE-1 (a)初始狀態(tài)-空隊列AB隊首、隊尾指針 front rear 數(shù)組下標 0 1 MAXSIZE-1 (b)連續(xù)插入幾個結(jié)點后的狀態(tài)DC隊首、隊尾指針 front rear 數(shù)組下標 0 1 2 3 MAXSIZE-1 (c)連續(xù)刪除幾個結(jié)點后的狀態(tài)-此時隊列中只有一個結(jié)點D隊首、隊尾指針 front rear 數(shù)組下標 0 1 MAXSIZE-1 (d) 在(c)狀態(tài)下再刪除一個結(jié)點后的狀態(tài)-空隊列X隊首、隊尾指針 front rear 數(shù)組下標 0 1 2 3 MAXSIZE-1 (e)連續(xù)插入若干結(jié)點后

31、的狀態(tài)-此時隊列呈現(xiàn)滿的狀態(tài)，但數(shù)組前部有空位子DE隊列的順序存儲結(jié)構(gòu)的C語言描述如下：/ 隊列（順序存儲）的頭文件 / 文件名seqqueue.h / #define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int front; /隊首 int rear; /隊尾 sequence_queue;順序存儲隊列的幾個基本操作的具體實現(xiàn) :/ 函數(shù)功能:隊列（順序存儲）初始化 / 函數(shù)參數(shù):指向sequence_queue類型變量的指針變量sq / 函數(shù)返回值:空 / 文件名:seqqueue.c,函數(shù)

32、名:init() / void init(sequence_queue sq) sq-front=sq-rear=0; 算法2.20 隊列（順序存儲）初始化 / 函數(shù)功能:判斷隊列（順序存儲）是否為空 / 函數(shù)參數(shù):sequence_queue類型變量sq / 函數(shù)返回值:int類型。返回1表示空,0表示非空 / 文件名:seqqueue.c,函數(shù)名:empty() / int empty(sequence_queue sq) return (sq.front=sq.rear? 1:0); 算法2.21判斷隊列（順序存儲）是否為空 / 函數(shù)功能:打印隊列（順序存儲）的結(jié)點值 / 函數(shù)參數(shù):se

33、quence_queue類型變量sq / 函數(shù)返回值:空 / 文件名:seqqueue.c,函數(shù)名:display() /void display(sequence_queue sq) int i; if(empty(sq) printf(n順序隊列是空的!); else for(i=sq.front;irear=MAXSIZE) printf(n順序隊列是滿的!);exit(1); sq-asq-rear=x; sq-rear=sq-rear+1; 算法2.24 隊列（順序存儲）的插入操作/ 函數(shù)功能:隊列（順序存儲）的刪除（出隊）操作 / 函數(shù)參數(shù):指向sequence_queue類型變量

34、的指針變量sq / 函數(shù)返回值:空 / 文件名:seqqueue.c,函數(shù)名:dele() / void dele(sequence_queue sq) if(sq-front=sq-rear) printf(n順序隊列是空的！不能做刪除操作！); exit(1); sq-front+; 算法2.25 隊列（順序存儲）的刪除操作 在隊列的幾種狀態(tài)圖的（e）狀態(tài)中，隊列是一種隊滿狀態(tài)，將不能再插入新的結(jié)點，而實際上數(shù)組的前部還有許多空的位置。為了充分地利用空間，可以將隊列看作一個循環(huán)隊列，在數(shù)組的前部繼續(xù)作插入運算，這就是循環(huán)隊列。 X隊首、隊尾指針 front rear 數(shù)組下標 0 1 2

35、3 MAXSIZE-1 (e)連續(xù)插入若干結(jié)點后的狀態(tài)-此時隊列呈現(xiàn)滿的狀態(tài)，但數(shù)組前部有空位子DE2.4.3順序循環(huán)隊列及其實現(xiàn) 給定一個大小為MAXSIZE的數(shù)組存儲一個隊列時，經(jīng)過若干次插入和刪除操作后，當隊尾指示rear=MAXSIZE時，呈現(xiàn)隊列滿的狀態(tài)，而事實上數(shù)組的前部可能還有空閑的位置。為了有效利用空間，將順序存儲的隊列想象為一個環(huán)狀，把數(shù)組中的最前和最后兩個元素看作是相鄰的，這就是循環(huán)隊列。 front450123 (e) E、F進隊EFrearfront450123rear (f) G H I J進隊EFgHIJ隊滿2015.3.20 在循環(huán)隊列中進行出隊、入隊操作時，頭尾

36、指針仍要加1，朝前移動。只不過當頭尾指針指向向量上界（MaxSize-1）時，其加1操作的結(jié)果是指向向量的下界0。 這種循環(huán)意義下的加1操作可以描述為： if(rear+1=MaxSize) rear=0; else rear+; 利用模運算可簡化為： rear=(rear+1)%MaxSizerear front450123(a)隊列初始情況450123rear front (b)A進隊A front450123rear (c) B、C、D進隊ABCD450123rear (d) ABCD出隊front隊空 front450123rear (f) G H I J進隊EFgHIJfront45

37、0123 (e) E、F進隊EFrear隊滿如圖所示：由于入隊時尾指針向前追趕頭指針，出隊時頭指針向前追趕尾指針，故隊空和隊滿時頭尾指針均相等。因此，我們無法通過front=rear來判斷隊列“空”還是“滿”。本書采用犧牲一個數(shù)組元素的空間，即若數(shù)組的大小是MAXSIZE，則該數(shù)組所表示的循環(huán)隊列最多允許存儲MAXSIZE-1個結(jié)點。這樣，循環(huán)隊列滿的條件是(rear+1)%MAXSIZE=front循環(huán)隊列空的條件是 rear=front 解決此問題的方法至少有三種：其一是另設一個布爾變量以匹別隊列的空和滿；其二是少用一個元素的空間，約定入隊前，測試尾指針在循環(huán)意義下加1后是否等于頭指針，若

38、相等則認為隊滿（注意：rear所指的單元始終為空）；其三是使用一個計數(shù)器記錄隊列中元素的總數(shù)（實際上是隊列長度）。循環(huán)隊列的插入與刪除操作的實現(xiàn) ：/ 函數(shù)功能:循環(huán)隊列（順序存儲）的插入操作/ 函數(shù)參數(shù):指向sequence_queue類型變量的指針變量sq/ datatype類型的變量x / 文件名:secqinse.c,函數(shù)名:insert_sequence_cqueue()/void insert_sequence_cqueue(sequence_queue sq,datatype x) if(sq-rear+1)%MAXSIZE=sq-front) printf(n順序循環(huán)隊列是滿的

39、！無法進行插入操作！);exit(1); sq-asq-rear=x; sq-rear=(sq-rear+1)%MAXSIZE; 算法2.26 循環(huán)隊列（順序存儲）的插入操作 循環(huán)隊列（順序存儲）的刪除操作 / 函數(shù)功能:循環(huán)隊列（順序存儲）的刪除操作 / 函數(shù)參數(shù):指向sequence_queue類型變量的指針變量sq / 函數(shù)返回值:空 / 文件名secqdele.c, 函數(shù)名dele_sequence_cqueue() / void dele_sequence_cqueue(sequence_queue sq) if(sq-front=sq-rear) printf(n循環(huán)隊列是空的！無

40、法進行刪除操作！); exit(1); sq-front=(sq-front+1)%MAXSIZE; 算法2.27 循環(huán)隊列（順序存儲）的刪除操作習題:1、以計數(shù)器的方法實現(xiàn)循環(huán)隊列的基本運算。2、對于循環(huán)隊列，寫出求隊列長度的公式。*2.1 選擇題（1）表長為n的順序存儲的線性表，當在任何位置上插入或刪除一個元素的概率相等時，插入一個元素所需移動元素的平均個數(shù)為（），刪除一個元素所需移動元素的平均個數(shù)為（）。A（n1）/2BnCn+1Dn1En/2F(n+1)/2G(n2)/2（2）設棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次通過棧S，一個元素出棧后即進入隊列Q，

41、若6個元素出隊的序列為e2、e4、e3、e6、e5和e1，則棧S的容量至少應該為（）。A6B4C3D2（3）設棧的輸入序列為1、2、3n，若輸出序列的第一個元素為n，則第i個輸出的元素為（）。A不確定Bni+1CiDni（4）在一個長度為n的順序表中刪除第i個元素（1=i=n）時，需向前移動（）個元素。AniBni+1Cni1Di（5）若長度為n的線性表采用順序存儲結(jié)構(gòu)存儲，在第i個位置上插入一個新元素的時間復雜度為（）。AO(n)BO(1)CO(n2)DO(n3)（6）表達式a*(b+c)d的后綴表達式是（）。Aabcd*+Babc+*dCabc*+dD+*abcd（7）隊列是一種特殊的線性

42、表，其特殊性在于（）。A插入和刪除在表的不同位置執(zhí)行B插入和刪除在表的兩端位置執(zhí)行 C插入和刪除分別在表的兩端執(zhí)行D插入和刪除都在表的某一端執(zhí)行（8）棧是一種特殊的線性表，具有（）性質(zhì)。A先進先出B先進后出C后進后出D順序進出（9）順序循環(huán)隊列中（數(shù)組的大小為n），隊頭指示front指向隊列的第1個元素，隊尾指示rear指向隊列最后元素的后1個位置，則循環(huán)隊列中存放了n1個元素，即循環(huán)隊列滿的條件為（）。A(rear+1)%n=front1B(rear+1)%n=frontC(rear)%n=frontDrear+1=front（10）順序循環(huán)隊列中（數(shù)組的大小為6），隊頭指示front和隊尾

43、指示rear的值分別為3和0，當從隊列中刪除1個元素，再插入2個元素后，front和rear的值分別為（）。A5和1B2和4C1和5D4和2*2.2 什么是順序表？什么是棧？什么是隊列？2.3 設計一個算法，求順序表中值為x的結(jié)點的個數(shù)。2.4 設計一個算法，將一個順序表倒置，即如果順序表各個結(jié)點值存儲在一維數(shù)組a中，倒置的結(jié)果是使得數(shù)組a中的a0等于原來的最后一個元素，a1等于原來的倒數(shù)第2個元素，a的最后一個元素等于原來的第一個元素。2.5 已知一個順序表中的各結(jié)點值是從小到大有序的，設計一個算法，插入一個值為x的結(jié)點，使順序表中的結(jié)點仍然是從小到大有序。*2.6 將下列中綴表達式轉(zhuǎn)換為等

44、價的后綴表達式。（1）5+675 6 7*+（2）（56）/75 6- 7/（3）56785 6 7 *8*-（4）5785 7*8-（5）5（76）+8/95 7 6-* 8 9/+（6）7（568）97 5 6 8*-* 9-*2.7 已知循環(huán)隊列存儲在一個數(shù)組中，數(shù)組大小為n，隊首指針和隊尾指針分別為front和rear，寫出求循環(huán)隊列中當前結(jié)點個數(shù)的表達式。*2.8 編號為1，2，3，4的4列火車通過一個棧式的列車調(diào)度站，可能得到的調(diào)度結(jié)果有哪些？如果有n列火車通過調(diào)度站，設計一個算法，輸出所有可能的調(diào)度結(jié)果。#include #define MAXSIZE 100 /*表的最大空間大小*/typedef int datatype;typedef struct datatype aMAXSIZE ; /*向量data用于*/ int size; /*當前的表長度*/ sequence_list;實驗：自定義一個線性表 sequlist.h（1）void reverse(seqlist *L) 將順序表L就地轉(zhuǎn)置，即借助于O（1）的