第3次-第2章-線性表及其順序存儲(chǔ)

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

2、中一組地址連續(xù)的存儲(chǔ)單元中。 2.2順序表順序表的存儲(chǔ)結(jié)構(gòu)如下圖所示： 結(jié)點(diǎn)序號(hào) 1 2 i n len len len lenk1k2k ik n內(nèi)存狀況 存儲(chǔ)地址 location(k1) location(k1)+(i-1)l en 順序表的存儲(chǔ)結(jié)構(gòu)的C語言描述如下：/*順序表的頭文件，文件名sequlist.h */ #define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int size; sequence_list;表長(zhǎng)順序表的幾個(gè)基本操作的具體實(shí)現(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ù)功能:在順序表后部進(jìn)行插入操作 / 函數(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 在順序表后部進(jìn)行插入操作打印順序表的各結(jié)點(diǎn)值 / 函數(shù)功能:打印順序表的各結(jié)點(diǎn)值 / 函數(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é)點(diǎn)值判斷順序表是否為空 / 函數(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é)點(diǎn)位置 / 函數(shù)功能:查找順序表中值為x的結(jié)點(diǎn)位置 / 函數(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é)點(diǎn)位置 取得順序表中第i個(gè)結(jié)點(diǎn)的值 / 函數(shù)功能:取得順序表中第i個(gè)結(jié)點(diǎn)的值 / 函數(shù)參數(shù):sequence_list型變量slt,int型變量i / 函數(shù)返回值:datatype類型。返回第i個(gè)結(jié)點(diǎn)的值 / 文件名:sequlist.c,函數(shù)名:get() / data

7、type get(sequence_list slt,int i) if(i=slt.size) printf(n指定位置的結(jié)點(diǎn)不存在!);exit(1); else return slt.ai; 算法2.6 取得順序表中第i個(gè)結(jié)點(diǎn)的值 順序表的插入運(yùn)算是將一個(gè)值為x的結(jié)點(diǎn)插入到順序表的第i個(gè)位置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é)點(diǎn) / 函數(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é)點(diǎn) 算法2.7中，所花費(fèi)的時(shí)間主要是元素后移操作，對(duì)于在第i個(gè)位置上插入一個(gè)新的元素，需要移動(dòng)（n-i）個(gè)元素，設(shè)在第i個(gè)位置上插入一個(gè)元素的概率為pi，且在任意一個(gè)位置上插入元素的概率相等，即p0=p1=p2=pn=1/(n+1)，則在一個(gè)長(zhǎng)度為n的順序表中插入一個(gè)元素所需的平均移動(dòng)次數(shù)為： 即在長(zhǎng)度為n的順序表中插入一個(gè)元素平均需要移動(dòng)表中的一半

10、元素。該算法的時(shí)間復(fù)雜度為O（n）。 順序表的刪除操作是指刪除順序表中的第i個(gè)結(jié)點(diǎn)，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刪除操作的具體實(shí)現(xiàn)見算法2.8 / 函數(shù)功能:刪除順序表中第position位置的結(jié)點(diǎn) / 函數(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é)點(diǎn) 要?jiǎng)h除順序表中的第i個(gè)結(jié)點(diǎn)，則需要移動(dòng)（n-i-1）個(gè)元素，設(shè)刪除表中第i個(gè)結(jié)點(diǎn)的概率為

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

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

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

15、化 / 函數(shù)參數(shù):指向sequence_stack型變量的指針變量st / 函數(shù)返回值:空 / 文件名:seqstack.c,函數(shù)名:init() / void init(sequence_stack st) st-top=0; 算法2.9棧（順序存儲(chǔ)）初始化 說明:top=0表示?？?，這種情況下棧頂指示位內(nèi)容始終為空。/ 函數(shù)功能:判斷棧（順序存儲(chǔ)）是否為空 / 函數(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判斷棧（順序存儲(chǔ)）是否為空 / 函數(shù)功能:讀棧頂（順序存儲(chǔ)）結(jié)點(diǎn)值 / 函數(shù)參數(shù):sequence_stack型變量st / 函數(shù)返回值:datatype類型。返回棧頂結(jié)點(diǎn)值 / 文件名:seqstack.c,函數(shù)名:read() / datatype read(sequence_stack st) if (empty(st) printf(n棧是空的!);exit(1); else return st.ast.top-1; 算法2.11 取得棧頂（順序存儲(chǔ)）結(jié)點(diǎn)值順序棧的進(jìn)棧與出棧操作下圖表明進(jìn)出棧情況。543210top（a）空棧543210top

17、A（b）A進(jìn)棧543210-1topA（c）B、C、D進(jìn)棧BCDtoptoptop543210A（d）D,C出棧BCDtop543210（e）E進(jìn)棧ABCDtopEtop543210ABEDtop（f）E、B、A出棧toptop/ 函數(shù)功能:棧（順序存儲(chǔ)）的插入（進(jìn)棧）操作 / 函數(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 棧（順序存儲(chǔ)）的插入操作 / 函數(shù)功能:棧（順序存儲(chǔ)）的刪除（出棧）操作 / 函數(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棧（順序存儲(chǔ)）的刪除操作 思考:如果將?？毡硎緸閠o

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

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 判斷表達(dá)式括號(hào)是否匹配 算術(shù)表達(dá)式通常是由操作數(shù)、算術(shù)運(yùn)算符和一對(duì)圓括號(hào)“（”和“）”組合而成。其中操作數(shù)允許是程序語言中任意合法的變量名或常數(shù)。 以下我們討論+、-、*、/四種算術(shù)運(yùn)算。表達(dá)式求值中的首要問題：如何確定表達(dá)式中所含運(yùn)算的計(jì)算次序。算術(shù)運(yùn)算的規(guī)則：1）先括號(hào)內(nèi)、后括號(hào)外2）先乘除、后加減3）從左算到右2.3.4棧的應(yīng)

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

23、易出錯(cuò)。方法2：重新改寫表達(dá)式為后綴表達(dá)式。在計(jì)算機(jī)中，表達(dá)式可以有三種不同的標(biāo)識(shí)方法設(shè) Exp = S1 + OP + S2則稱 OP + S1 + S2 為表達(dá)式的前綴表示法 稱 S1 + OP + S2 為表達(dá)式的中綴表示法 稱 S1 + S2 + OP 為表達(dá)式的后綴表示法 可見，它以運(yùn)算符所在不同位置命名的。例： 中綴表達(dá)式 后綴表達(dá)式 （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-/+算法：將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式根據(jù)中綴表達(dá)式與后綴表達(dá)式的特點(diǎn)，可得將中綴表達(dá)式變換為后

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

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

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

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

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

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

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

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

32、名:init() / void init(sequence_queue sq) sq-front=sq-rear=0; 算法2.20 隊(duì)列（順序存儲(chǔ)）初始化 / 函數(shù)功能:判斷隊(duì)列（順序存儲(chǔ)）是否為空 / 函數(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判斷隊(duì)列（順序存儲(chǔ)）是否為空 / 函數(shù)功能:打印隊(duì)列（順序存儲(chǔ)）的結(jié)點(diǎn)值 / 函數(shù)參數(shù):se

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

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

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

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

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

38、相等則認(rèn)為隊(duì)滿（注意：rear所指的單元始終為空）；其三是使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)（實(shí)際上是隊(duì)列長(zhǎng)度）。循環(huán)隊(duì)列的插入與刪除操作的實(shí)現(xiàn) ：/ 函數(shù)功能:循環(huán)隊(duì)列（順序存儲(chǔ)）的插入操作/ 函數(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)隊(duì)列是滿的

39、！無法進(jìn)行插入操作！);exit(1); sq-asq-rear=x; sq-rear=(sq-rear+1)%MAXSIZE; 算法2.26 循環(huán)隊(duì)列（順序存儲(chǔ)）的插入操作 循環(huán)隊(duì)列（順序存儲(chǔ)）的刪除操作 / 函數(shù)功能:循環(huán)隊(duì)列（順序存儲(chǔ)）的刪除操作 / 函數(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)隊(duì)列是空的！無

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

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

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

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

44、價(jià)的后綴表達(dá)式。（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)隊(duì)列存儲(chǔ)在一個(gè)數(shù)組中，數(shù)組大小為n，隊(duì)首指針和隊(duì)尾指針分別為front和rear，寫出求循環(huán)隊(duì)列中當(dāng)前結(jié)點(diǎn)個(gè)數(shù)的表達(dá)式。*2.8 編號(hào)為1，2，3，4的4列火車通過一個(gè)棧式的列車調(diào)度站，可能得到的調(diào)度結(jié)果有哪些？如果有n列火車通過調(diào)度站，設(shè)計(jì)一個(gè)算法，輸出所有可能的調(diào)度結(jié)果。#include #define MAXSIZE 100 /*表的最大空間大小*/typedef int datatype;typedef struct datatype aMAXSIZE ; /*向量data用于*/ int size; /*當(dāng)前的表長(zhǎng)度*/ sequence_list;實(shí)驗(yàn)：自定義一個(gè)線性表 sequlist.h（1）void reverse(seqlist *L) 將順序表L就地轉(zhuǎn)置，即借助于O（1）的