【正文】 要運算都在棧頂進行 ， 為訪問單鏈表的表頭方便 ， 指定單鏈表的表頭作為棧頂 。 ? 鏈棧的插入和刪除運算實現(xiàn)起來和鏈表的操作相似 ， 下面僅給出鏈棧的進棧和出棧操作的具體算法 。 其中結(jié)點結(jié)構(gòu)定義為： typedef struct node { elemtype data。 struct node *next。 }node,*pointer。 棧的存儲結(jié)構(gòu)及其基本運算的實現(xiàn) ? 2. 鏈?zhǔn)酱鎯Y(jié)構(gòu) ? 進棧算法 (算法 ) void push(pointer s,datatype x) /*將數(shù)據(jù) x插入到棧頂 ， s為表頭指針*/ { p=(pointer*)malloc(sizeof(node))。 /*申請一個新結(jié)點 */ pdata=x。 /*將 x放入新結(jié)點的數(shù)據(jù)域 */ pnext=snext。 /*將新結(jié)點插入鏈表 ， 作為首元素 */ snext=p。 } 棧的存儲結(jié)構(gòu)及其基本運算的實現(xiàn) ? 2. 鏈?zhǔn)酱鎯Y(jié)構(gòu) ? 出棧算法 (算法 ) datatype pop(pointer s) /*將鏈棧 s的棧頂出棧 */ { if(snext==null) return(null)。 /*空棧 ， 返回空 */ else { p=snext。 /*使 P指針指向棧頂結(jié)點 */ x=pdata。 /*將棧頂結(jié)點的數(shù)據(jù)域的值賦給 x*/ snext=pnext。 /*刪除棧頂結(jié)點 */ free(p)。 /*釋放被刪除的結(jié)點 */ return(x)。 /*返回原棧頂結(jié)點的數(shù)據(jù)域的值 */ } } 隊 列 ? 隊列的定義 ? 隊列的基本運算 ? 隊列的存儲結(jié)構(gòu)及其基本運算的實現(xiàn) 隊列的定義 ? 隊列 (Queue)是只能在一端進行插入 ， 而在另一端刪除的線性表 。 能進行插入的一端稱為隊列的尾 ， 能進行刪除的一端稱為隊列的頭 。 ? 隊列 是限定只能在隊尾插入 、 只能在隊列的頭刪除的線性表 。 ? 先進入隊列中的元素稱為隊列的 頭元素 (隊列的頭 )，最后進入隊列中的元素稱為隊列的 尾元素 (隊列的尾 )。隊列稱為 先進先出表 (First In First Out)， 簡稱 FIFO。 隊列的基本運算 ? 隊列的基本運算有以下幾種： ? 初始化 InitQueue(Q)： 其作用是建立一個空隊列 Q，準(zhǔn)備存放數(shù)據(jù)。 ? 入隊列 EnQueue(Q， x)： 其作用是將數(shù)據(jù) x插入到隊列 Q的隊尾，隊列的長度加 1。 ? 讀隊頭 GetHead(Q)： 其作用是當(dāng)隊列非空時，返回隊列頭元素的值，但不刪除隊列頭元素。 ? 判隊列空否 EmptyQueue(Q)： 若隊列 Q為空，則返回的值為 1，否則返回的值為 0。 隊列的存儲結(jié)構(gòu)及其基本運算的實現(xiàn) ?隊列和棧一樣 ， 也可采用 順序存儲 和 鏈?zhǔn)酱鎯?兩種存儲結(jié)構(gòu) 。 ?1. 鏈?zhǔn)酱鎯Y(jié)構(gòu) 采用鏈表存儲的隊列叫鏈隊列 。 一般用單鏈表表示一個鏈隊列 。 隊列經(jīng)常從隊列的頭出隊 ， 從隊列的尾進隊 ， 所以用兩個指針分別指向兩端 。 一個指向頭結(jié)點 ， 稱為 front，另一個指向尾結(jié)點 ， 稱為 rear。 用這種鏈表表示隊列的示意如圖 。 提示： 使用上述鏈表存儲隊列時 ， 必須注意正確使用 front和 rear兩個指針 ， 才能方便地實現(xiàn)隊列的各種運算 。 圖 鏈表存儲的隊列 隊列的存儲結(jié)構(gòu)及其基本運算的實現(xiàn) ? 1. 鏈?zhǔn)酱鎯Y(jié)構(gòu) ? 進隊列算法 (算法 ) void EnQueue(struct linkqueue Q,elemtype x)/*x進鏈?zhǔn)疥犃?Q*/ { p=(pointer*)malloc(sizeof(node))。 /*為新元素準(zhǔn)備結(jié)點的空間 */ pdata=x。 /*將數(shù)據(jù) x存入該新結(jié)點 */ pnext=NULL。 /*將尾結(jié)點的指針域置空指針 */ next=p。 /*將新結(jié)點插入隊列 Q的尾部 */ =p。 /*將尾指針指向新的尾元素 */ } 隊列的存儲結(jié)構(gòu)及其基本運算的實現(xiàn) ? 1. 鏈?zhǔn)酱鎯Y(jié)構(gòu) ? 出隊算法 (算法 ) datatype OutQueue(stuct linkqueue Q) { if(front==rear) error(Empty Queue)。 else { p=next。 /*使 P指 向隊列的頭元素 */ x=pdata。 /*將頭元素的值賦給 x*/ next=pnext。 /*刪去隊列的頭元素 */ free(p)。 /*釋放被輸出元素所占的空間 */ return(x)。 /*返回 x中 存放的原隊列頭元素的值 */ } } 隊列的存儲結(jié)構(gòu)及其基本運算的實現(xiàn) ?2. 順序存儲結(jié)構(gòu) 用順序存儲結(jié)構(gòu)存儲的隊列稱為順序隊列 。 順序隊列用一個向量來存儲隊列元素 ， 再用整型變量 front存儲隊列的頭元素位置的前一個位置 ， 用整型變量 rear存儲隊列的尾元素的位置 。 ? 初始化運算 ? 進隊列運算 ? 出隊列運算 ,將隊列頭元素刪除 ， 并返回其值 。 ? 讀隊列頭元素運算 ? 判斷隊列是否是空隊列的運算 棧和隊列上機實習(xí) ? 實習(xí) 1 ? 實習(xí) 2 ? 實習(xí) 3 ? 實習(xí) 4 實習(xí) 1 ? 借助棧將輸入的任意一個非負的十進制整數(shù) ， 轉(zhuǎn)換成與其等值的八進制數(shù)并輸出 ， 用 C語言編寫函數(shù) 。 (算法 ) conversion( ) { InitStack(s)。 scanf(%d,n)。 while(n) { push(s,n%8)。 n=n/8。 } while(!EmptyStack (s)) { pop(s,x)。 printf(%d,x)。 } } 實習(xí) 2 ? 編寫判斷 “ [‖與 “ ]‖是否配對的函數(shù) 。 (算法 ) pracket( ) { InitStack(s)。 ch=getchar( )。 while(ch!=39。39。) { if(ch== 39。[39。) Push(s,ch)。 if(ch== 39。]39。) { if(EmptyStack(s))error(不配對)。 else Pop(s,x)。 ch=getchar( )。 } } if(!Emput(s))error(不配對 )。 } 實習(xí) 3 ? 求鏈棧 Ls中包括棧元素個數(shù)的算法 。 (算法 ) StackLength(Ls) { p=Lsnext。 i=0。 while(p) { p=pnext。 i++。 } return(i)。 } 實習(xí) 4 ? 求鏈隊 Lq中包括棧元素個數(shù)的算法 。 (算法 ) QueueLength(Lq) { p=Lqfrontnext。 i=0。 while(p) { p=pnext。 i++。 } return(i)。 } 習(xí) 題 ? 1 填空題 ? 2 選擇題 ? 3 簡答題 ? 4 算法題 習(xí) 題 __填空題 ? 1. 填空題 (1) 已知順序棧 s，在對 s進行進棧操作之前要先判斷 _______。 (2) 已知棧 s是順序存儲結(jié)構(gòu)，在進行出棧操作之前要先判斷 ___。 (3) 順序棧 s存儲在數(shù)組 Ssdata[0..max]中， s棧滿的條件是 ____________。 (4) 同一棧內(nèi)的各元素的類型 __________。 (5) 順序棧 s存儲在數(shù)組 Ssdata[0..max]中，ｓ進行出棧操作后，要執(zhí)行的語句是Sstop____。 (6) 順序棧 s存儲在數(shù)組 Ssdata[0..max]中， s進行進棧操作前，要執(zhí)行的語句是Sstop______運算。 (7) 順序棧 s存儲在數(shù)組 Ssdata[0..max]中， s棧滿時， Sstop==______。 習(xí) 題 __ 填空題 (8) 順序棧 s存儲在數(shù)組 Ssdata[0..max]中， s?？諘r， Sstop==______。 (9) 對鏈棧 ls，指向棧頂元素的指針是 ______。 (10) 鏈棧 ls是空棧的條件是 ______。 (11) 鏈棧 ls的棧頂元素是鏈表的 ______元素。 (12) 鏈棧 ls的棧頂元素安排在鏈表的首元素，原因是 ____。 (13) 棧 s經(jīng)過運算 InitStack(s)。Push(s,a)。Push(s,b)后， GetTop(S)的值是 ____。 (15) 元素進入隊列的一端是 ____________。 (16) 隊列出隊的一端是 ____________。 (17) 已知循環(huán)隊列 sq，在進行進隊操作之前要先判斷 ______。 習(xí) 題 __ 填空題 (18) 已知循環(huán)隊列 sq，在進行出隊操作之前要先判斷 __________。 (19) 循環(huán)隊列 sq存儲在數(shù)組 [0..max]中， sq滿的條件是 ____________。 (20) 循環(huán)隊列 sq空的條件是 ____________。 (21) 循環(huán)隊列 sq存儲在數(shù)組 [0..max]中， max，則存放隊列頭元素的數(shù)組元素是 ____________。 (22) 循環(huán)隊列 sq存儲在數(shù)組 [0..max]中， max，則存放隊列尾元素的數(shù)組元素是 ____________。 (23) 循環(huán)隊列 sq存儲在數(shù)組 [0..max]中，則 sq中最多能存放 ________個隊列元素。 (24) 鏈隊 lq中，指向隊頭元素的指針是 ______。 (25) 鏈隊 lq中，指向隊尾元素的指針是 ____________。 (26) 鏈隊 lq是空隊的條件是 _____________。 (27) 鏈隊 lq經(jīng)過運算 InitQueue(lq)， lqfront與 lqear_____________。 (28) 在鏈隊列 lq中，鏈隊的尾元素是鏈表的 _____________元素。 (29) 在鏈隊列 lq中，鏈隊的頭元素是鏈表的 _____________元素。 (30) 鏈隊 lq是空隊時， lqfrontnext為 _______________。 習(xí) 題 __ 選擇題 (1) 棧是限定在 __________處進行插入或刪除操作的線性表。 A. 端點 B. 棧底 C. 棧頂 D. 中間 (2) 在棧頂一端可進行的全部操作是 ___________。 A. 插入 C. 插入和刪除 D. 進棧 (3) 4個元素按 A、 B、 C、 D順序連續(xù)進 S棧， 進行 Pop(S,x)運算后， x的值是___________。 A. A B. B C. C D. D (4) 棧的特點是 __________。 A. 先進先出 B. 后進先出 C. 后進后出 D. 不進不出 (5) 棧結(jié)構(gòu)的元素個數(shù)是 ___________。 A. 不變的 C. 任意的 D. 0 (6) 4個元素進 S棧的順序是 A、 B、 C、 D，進行兩次 Pop(S,x)操作后，棧頂元素的值是 __________。 A. A B. B C. C D. D 習(xí) 題 __ 選擇題 (7) 同一個棧內(nèi)各元素的類型 _________。 A. 必須一致 B. 可以不一致 C. 不能一致 D. 不必不一致 (8) 順序棧存儲空間的實現(xiàn)使用 ___________。 A.