【導(dǎo)讀】計(jì)算機(jī)是一門研究用計(jì)算機(jī)進(jìn)行信息表示和處。這里面涉及到兩個(gè)問題：。隨著計(jì)算機(jī)的普及，信息量的增。程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。眾所周知，計(jì)算機(jī)的程序是對(duì)信息進(jìn)行加工處理。例1、電話號(hào)碼查詢系統(tǒng)。設(shè)有一個(gè)電話號(hào)碼薄，它記錄了N個(gè)人的名字和其。其中ai，bi(i=1，2…n)分別表示某人的名字和對(duì)應(yīng)的電。算法的設(shè)計(jì)，依賴于計(jì)算機(jī)如何存儲(chǔ)人的。元向量的形式，它的每個(gè)元素是一個(gè)數(shù)對(duì)(ai，是原來的結(jié)構(gòu)類型。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。種或多種特定關(guān)系的數(shù)據(jù)元素的集合。別表示復(fù)數(shù)的實(shí)部和虛部。型上的一組操作。順序表示和非順序表示。抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)。出是同輸入有著某些特定關(guān)系的量。不是產(chǎn)年莫名其妙的輸出結(jié)果。效率與存儲(chǔ)量需求效率指的是算法執(zhí)行的

　　

【正文】 位置上進(jìn)行 .由于只能在鏈表頭部進(jìn)行操作，故鏈表沒有必要像單鏈表那樣附加頭結(jié)點(diǎn)。棧頂指針就是鏈表的頭指針。 鏈棧的類型說明如下： typedef struct stacknode{ datatype data struct stacknode *next }stacknode。 來自 的資料庫下載 Void initstack(seqstack *p) { p–top=null。 } int stackempty(linkstack *p) { return p–top==null。 } 來自 的資料庫下載 ? Void push(linkstack *p,datatype x) { stacknode *q q=(stacknode*)malloc(sizeof(stacknode))。 q–data=x。 q–next=p–top。 p–top=p。 } 來自 的資料庫下載 Datatype pop(linkstack *p) { datatype x。 stacknode *q=p–top。 if(stackempty(p) error(―stack underflow.‖)。 x=q–data。 p–top=q–next。 free(q)。 return x。 } 來自 的資料庫下載 datatype stack top(linkstack *p) { if(stackempty(p)) error(―stack is empty.‖)。 return p–top–data。 } 來自 的資料庫下載 棧的應(yīng)用舉例 由于棧結(jié)構(gòu)具有的后進(jìn)先出的固有特性，致使棧成為程序設(shè)計(jì)中常用的工具。以下是幾個(gè)棧應(yīng)用的例子。 數(shù)制轉(zhuǎn)換 十進(jìn)制 N和其它進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問題 ,其解決方法很多 ,其中一個(gè)簡單算法基于下列原理 : 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 來自 的資料庫下載 void conversion( ) { initstack(s)。 scanf (―%‖,n)。 while(n){ push(s,n%8)。 n=n/8。 } while(! Stackempty(s)){ pop(s,e)。 printf(―%d‖,e)。 } } 來自 的資料庫下載 括號(hào)匹配的檢驗(yàn) 假設(shè)表達(dá)式中充許括號(hào)嵌套 ,則檢驗(yàn)括號(hào)是否匹配的方法可用 “ 期待的急迫程度 ” 這個(gè)概念來描述。例： （（）（） （（））） 行編輯程序 在編輯程序中，設(shè)立一個(gè)輸入緩沖區(qū)，用于接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入錯(cuò)誤，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。 來自 的資料庫下載 行編輯程序算法如下 : void lineedit( ){ initstack(s)。 ch=gether( )。 while(ch!=eof){ while(ch!=eof amp。amp。 ch!=?\n‘){ switch(ch){ case ?‘ : pop(s,c)。 case ?@‘ : clearstack(s)。 default : push(s,ch)。 } 來自 的資料庫下載 ch=getchar( )。 } clearstack(s)。 if(ch!=eof) ch=gethar( )。 } destroystack(s)。 } 來自 的資料庫下載 迷宮求解 入口 出口 來自 的資料庫下載 隊(duì)列 抽象數(shù)據(jù)類型隊(duì)列的定義 隊(duì)列 (Queue)也是一種運(yùn)算受限的線性表。它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許刪除的一端稱為隊(duì)頭 (front)，允許插入的一端稱為隊(duì)尾 (rear)。 例如：排隊(duì)購物。操作系統(tǒng)中的作業(yè)排隊(duì)。先進(jìn)入隊(duì)列的成員總是先離開隊(duì)列。因此隊(duì)列亦稱作先進(jìn)先出 (First In First Out)的線性表，簡稱 FIFO表。 當(dāng)隊(duì)列中沒有元素時(shí)稱為空隊(duì)列。在空隊(duì)列中依次加入元素 a1,a2,… an之后， a1是隊(duì)頭元素， an是隊(duì)尾元素。顯然退出隊(duì)列的次序也只能是 a1,a2,… an ，也就是說隊(duì)列的修改是依先進(jìn)先出的原則進(jìn)行的。 來自 的資料庫下載 下圖是隊(duì)列的示意圖： a1 a2 … an 出隊(duì) 入隊(duì) 隊(duì)頭 隊(duì)尾 隊(duì)列的抽象數(shù)據(jù)定義見書Ｐ 59 循環(huán)隊(duì)列－隊(duì)列的順序表示和實(shí)現(xiàn) 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列，順序隊(duì)列實(shí)際上是運(yùn)算受限的順序表，和順序表一樣，順序隊(duì)列也是必須用一個(gè)向量空間來存放當(dāng)前隊(duì) 來自 的資料庫下載 列中的元素。由于隊(duì)列的隊(duì)頭和隊(duì)尾的位置是變化的，因而要設(shè)兩個(gè)指針和分別指示隊(duì)頭和隊(duì)尾元素在隊(duì)列中的位置，它們的初始值地隊(duì)列初始化時(shí)均應(yīng)置為０。入隊(duì)時(shí)將新元素插入所指的位置，然后將加１。出隊(duì)時(shí)，刪去所指的元素，然后將加１并返回被刪元素。由此可見，當(dāng)頭尾指針相等時(shí)隊(duì)列為空。在非空隊(duì)列里，頭指針始終指向隊(duì)頭元素，而尾指針始終指向隊(duì)尾元素的下一位置。 ０ １ ２ ３ 0 1 2 3 Front rear a b c Front rear (a)隊(duì)列初始為空 （ b） A,B,C入隊(duì) 來自 的資料庫下載 ０ １ ２ ３ ０ １ ２ ３ b c front rear front rear （ c) a出隊(duì) (d) b,c出隊(duì)，隊(duì)為空 和棧類似，隊(duì)列中亦有上溢和下溢現(xiàn)象。此外，順序隊(duì)列中還存在 “ 假上溢 ” 現(xiàn)象。因?yàn)樵谌腙?duì)和出隊(duì)的操作中，頭尾指針只增加不減小，致使被刪除元素的空間永遠(yuǎn)無法重新利用。因此，盡管隊(duì)列中實(shí)際的元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模，但也可能由于尾指針?biāo)瘸鱿蛄靠臻g的上界而不能做入隊(duì)操作。該現(xiàn)象稱為假上溢。 來自 的資料庫下載 為充分利用向量空間?？朔鲜黾偕弦绗F(xiàn)象的方法是將向量空間想象為一個(gè)首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量，存儲(chǔ)在其中的隊(duì)列稱為循環(huán)隊(duì)列（ Circular Queue)。在循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，頭尾指針仍要加 1，朝前移動(dòng)。只不過當(dāng)頭尾指針指向向量上界（ QueueSize1）時(shí)，其加 1操作的結(jié)果是指向向量的下界 0。 這種循環(huán)意義下的加 1操作可以描述為： if(I+1==QueueSize) i=0。 else i++。 利用模運(yùn)算可簡化為 ： i=(i+1)%QueueSize 來自 的資料庫下載 顯然，因?yàn)檠h(huán)隊(duì)列元素的空間可以被利用，除非向量空間真的被隊(duì)列元素全部占用，否則不會(huì)上溢。因此，除一些簡單的應(yīng)用外，真正實(shí)用的順序隊(duì)列是循環(huán)隊(duì)列。 如圖所示：由于入隊(duì)時(shí)尾指針向前追趕頭指針，出隊(duì)時(shí)頭指針向前追趕尾指針，故隊(duì)空和隊(duì)滿時(shí)頭尾指針均相等。因此，我們無法通過 front=rear來判斷隊(duì)列“空”還是“滿”。 解決此問題的方法至少有三種： 其一是另設(shè)一個(gè)布爾變量以匹別隊(duì)列的空和滿；其二是少用一個(gè)元素的空間，約定入隊(duì)前，測(cè)試尾指針在循環(huán)意義下加 1后是否等于頭指針，若相等則認(rèn)為隊(duì)滿（注意： rear所指的單元始終為空）； 來自 的資料庫下載 其三是使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)（實(shí)際上是隊(duì)列長度）。下面我們用第三種方法實(shí)現(xiàn)循環(huán)隊(duì)列上的六種基本操作，為此先給出循環(huán)隊(duì)列的類型定義。 ? define QueueSize 100 ? typedef char DataType。 ? typedef Struct{ ? int front。 ? int rear。 ? int count。 ? datatype data[queuesize] ? }cirqueue。 來自 的資料庫下載 （ 1）置空隊(duì) void initqueue(cirqueue *q){ q–front=q–rear=0。 q–count=0。 } （ 2）判斷隊(duì)空 int queueempty(cirqueue *q) { return q–count==0。 } （ 3）判斷隊(duì)滿 int queuefull(cirqueue *q){ return q–count==queuesize。 } 來自 的資料庫下載 （ 4）入隊(duì) void enqueue(cirqueue *q,datatype x) { if(queuefull(q)) error(―queue overflow‖)。 q–count++。 q–data[q–rear]=x。 q–rear=(q–rear+1)%queuesize。 } 來自 的資料庫下載 （ 5）出隊(duì) datatype dequeue(cirqueue *q) { datatype temp。 if(queueempty(q)) error(―queue underflow‖)。 temp=q–data[q–front]。 q–count。 q–front=(q–front+1)%queuesize。 return temp。 } 來自 的資料庫下載 （ 6）取頭指針 datatype queuefront(cirqueue *q) { if(queueempty(q))