【正文】 但當原隊中只有一個結(jié)點時，該結(jié)點既是隊頭也是隊尾，故刪去此結(jié)點時亦需修改尾指針，且刪去此結(jié)點后隊列變空。 return x。 x=p–data。 q–rear=p。 p–data=x。 }linkqueue。 ? struct queuenode *next。 } ? 鏈隊列 ? 隊列的鏈式存儲結(jié)構(gòu)簡稱為鏈隊列，它是限制僅在表頭刪除和表尾插入的單鏈表。 q–front=(q–front+1)%queuesize。 } （ 5）出隊 datatype dequeue(cirqueue *q) { datatype temp。 } （ 4）入隊 void enqueue(cirqueue *q,datatype x) { if(queuefull(q)) error(“ queue overflow” )。 （ 1）置空隊 void initqueue(cirqueue *q){ q–front=q–rear=0。 ? typedef Struct{ ? int front。因此，我們無法通過 front=rear來判斷隊列“空”還是“滿”。 else i++。克服上述假上溢現(xiàn)象的方法是將向量空間想象為一個首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量，存儲在其中的隊列稱為循環(huán)隊列（ Circular Queue)。因為在入隊和出隊的操作中，頭尾指針只增加不減小，致使被刪除元素的空間永遠無法重新利用。由此可見，當頭尾指針相等時隊列為空。 下圖是隊列的示意圖： a1 a2 ? an 出隊 入隊 隊頭 隊尾 隊列的抽象數(shù)據(jù)定義見書Ｐ 59 循環(huán)隊列－隊列的順序表示和實現(xiàn) 隊列的順序存儲結(jié)構(gòu)稱為順序隊列，順序隊列實際上是運算受限的順序表，和順序表一樣，順序隊列也是必須用一個向量空間來存放當前隊 列中的元素。因此隊列亦稱作先進先出 (First In First Out)的線性表，簡稱 FIFO表。允許刪除的一端稱為隊頭 (front)，允許插入的一端稱為隊尾 (rear)。 if(ch!=eof) ch=gethar( )。 case ‘ ’ : clearstack(s)。允許用戶輸入錯誤，并在發(fā)現(xiàn)有誤時可以及時更正。 } while(! Stackempty(s)){ pop(s,e)。 數(shù)制轉(zhuǎn)換 十進制 N和其它進制數(shù)的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題 ,其解決方法很多 ,其中一個簡單算法基于下列原理 : 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 void conversion( ) { initstack(s)。 } datatype stack top(linkstack *p) { if(stackempty(p)) error(“ stack is empty.” )。 x=q–data。 p–top=p。 } int stackempty(linkstack *p) { return p–top==null。 } 鏈棧 棧的鏈式存儲結(jié)構(gòu)稱為鏈棧，它是運算是受限的單鏈表，克插入和刪除操作僅限制在表頭位置上進行 .由于只能在鏈表頭部進行操作，故鏈表沒有必要像單鏈表那樣附加頭結(jié)點。 s– top。 } 置空棧 void initstack(seqstack *s) { s– top=1。上溢是一種出錯狀態(tài)，應(yīng)該設(shè)法避免之；下溢則可能是正?，F(xiàn)象，因為棧在程序中使用時，其初態(tài)或終態(tài)都是空棧，所以下溢常常用來作為程序控制轉(zhuǎn)移的條件。若棧底位置在向量的低端，即 s– data[0]是棧底元素，那么棧頂指針 s– top是正向增加的，即進棧時需將 s– top加 1，退棧時需將s–top 減 1。 typedef struct { datatype data[stacksize]。因為棧底位置是固定不變的，所以可以將棧底位置設(shè)置在數(shù)組的兩端的任何一個端點；棧頂位置是隨著進棧和退棧操作而變化的，故需用一個整型變量 top 例、一疊書或一疊盤子。因此，棧稱為后進先出表（ LIFO）。當表中沒有元素時稱為空棧。 free(p)。 p—prior—next=q。 雙向鏈表的前插操作算法如下： void dinsertbefor(dlistnode *p， datatype x) { dlistnode *q=malloc(sizeof(dlistnode))。 typedef dlistnode * dlinklist。這樣就形成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。 heada—next=(headb—next)—next free(headb—next)。因此，實際中多采用尾指針表示單循環(huán)鏈表。 單循環(huán)鏈表： 在單鏈表中，將終端結(jié)點的指針域 NULL改為指向表頭結(jié)點的或開始結(jié)點，就得到了單鏈形式的循環(huán)鏈表，并簡單稱為單循環(huán)鏈表。 顯然此算法的時間復雜度也是 O(n)。 free( r ) 。 p=getnode(head， i1)。因為在單鏈表中結(jié)點 ai的存儲地址是在其直接前趨結(jié)點 a a i1的指針域 next中，所以我們必須首先找到 a i1的存儲位置 p。注意當 i=1時， getnode找到的是頭結(jié)點，當 i=n+1時， getnode找到的是結(jié)點 an。 q–data=x。從而實現(xiàn)三個結(jié)點 ai1， x和 ai之間的邏輯關(guān)系的變化，插入過程如： 具體算法如下： void insertnode(linklist head， datetype x， int i) { listnode * p， *q。 return p。 } 按值查找 按值查找是在鏈表中，查找是否有結(jié)點值等于給定值 key的結(jié)點，若有的話，則返回首次找到的其值為 key的結(jié)點的存儲位置；否則返回 NULL。 while(p–next jI){ p=p–next。但有時需要找頭結(jié)點的位置，故我們將頭結(jié)點看做是第 0 個結(jié)點，其算法如下： Listnode * getnode(linklist head ， int i) { int j。 以上算法的時間復雜度均為 O(n)。 } r–next=NULL。 while((ch=getchar( ))!=‵ \n′{ p=(listnode*)malloc(sizeof(listnode))。 如果我們在鏈表的開始結(jié)點之前附加一個結(jié)點，并稱它為 頭結(jié)點 ，那么會帶來以下兩個優(yōu)點： a、由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中，所以在鏈表的第一個位置上的操作就 和在表的其它位置上的操作一致，無需進行特殊處理； b、無論鏈表是否為空，其頭指針是指向頭結(jié)點 在的非空指針（空表中頭結(jié)點的指針域為空），因此空表和非空表的處理也就統(tǒng)一了。 return(head)。 if(head=NULL) head=p。) head=NULL。例： linklist creater( ) { char ch。 } return(head)。i){ p=(listnode*)malloc(sizeof(listnode))。 linklist head。 head=p。 ch=getchar( )。 linklist createlistf(void) { char ch。一旦 p所指的結(jié)點變量不再需要了，又可通過標準函數(shù) free(p) 釋放所指的結(jié)點變量空間。 linklist head。 struct node *next。 例 線性表 :(bat， cat， eat， fat， hat， jat，lat， mat) data link 的單鏈表示意圖如下： …… 110 …… 130 135 …… 160 頭指針 head 165 170 …… 200 205 …… ……… …… hat 200 ……. …… cat 135 eat 170 …. …… mat Null bat 130 fat 110 …… …… jat 205 lat 160 …… …… 165 ? head bat cat eat mat ^ … 單鏈表是由表頭唯一確定，因此單鏈表可以用頭 指針的名字來命名。鏈表正是通過每個結(jié)點的鏈域?qū)⒕€性表的 n個結(jié)點按其邏輯次序鏈接在一起的。因此，鏈表中結(jié)點的邏輯次序和物理次序不一定相同。在長度為 n的線性表中刪除一個結(jié)點，令 Ede(n)表示所需移動結(jié)點的平均次數(shù)，刪除表中第 i個結(jié)點的移動次數(shù)為 ni，故 Ede(n)= pi(nI) ? 式中， pi表示刪除表中第 i個結(jié)點的概率。 } ? 該算法的時間分析與插入算法相似，結(jié)點的移動次數(shù)也是由表長 n和位置 i決定。 return ERROR for(j=i。雖然 Eis(n)中 n的的系數(shù)較小，但就數(shù)量級而言，它仍然是線性階的。 ?當時，由于循環(huán)變量的終值大于初值，結(jié)點后移語句將不進行；這是最好情況，其時間復雜度 O（ 1）； ?當 =1時，結(jié)點后移語句將循環(huán)執(zhí)行 n次，需移動表中所有結(jié)點，這是最壞情況， ? 其時間復雜度為 O（ n）。 ? } ? 現(xiàn)在分析算法的復雜度。j=I1。 ? if(I1 || I+1) ? printf(“ Position error” )。 ? 順序表上實現(xiàn)的基本操作