【文章內(nèi)容簡(jiǎn)介】 tatype*)malloc(sizeof(datatype))。 *x=Tdata。 p=T 。 Top=Tnext。 free(p)。 return (x)。 x=(datatype*)malloc(sizeof( datatype))。 *x=Topnextdata。 p=Top next。 Topnext=pnext。 free(p)。 return (x)。 } 2021/11/10 25 ( 按 教材上定義棧 )鏈棧出棧操作 (不帶頭結(jié)點(diǎn) ) datatype * PopS(linkstack *S) { datatype * x。 StackNode *p。 if(STop= =NULL) { printf(―棧下溢” )。 return NULL。 } else { } } x=(datatype*)malloc(sizeof(datatype))。 p=STop。 * x=pdata。 STop=pnext free(p)。 return (x)。 2021/11/10 26 棧的應(yīng)用 由于棧的操作具有 后進(jìn)先出的固有特性 ，致使棧成為程序設(shè)計(jì)中的有用工具。凡應(yīng)用問(wèn)題求解的過(guò)程具有“ 后進(jìn)先出 ”的天然特性的話，則求解的算法中也必然需要利用“?！薄? 例如：假設(shè)要編制一個(gè)滿足下列要求的程序：對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)。 2021/11/10 27 十進(jìn)制 N和其它進(jìn)制數(shù)（二、八、十六進(jìn)制）的轉(zhuǎn)換， 基于下列原理 :采用除基數(shù)取余，直至商為 0為止的方法。 例如 (1348)10=(2504)8， 其運(yùn)算過(guò)程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 采用棧存放余數(shù)，入棧順序： 0、 2，出棧順序： 0、 4。 低位 高位 2021/11/10 28 ： void Conversion( int N， int base) { linkstack *Top。 int M； //M存放當(dāng)前商 Top= InitStack( )。 scanf(―%d,%d‖, amp。N, amp。base)。 /*輸入十進(jìn)制數(shù)和基數(shù) */ M=N。 while (M!=0) { PushS (Top, M%base)。 /*余數(shù)入棧 */ M = M/base。 /*商繼續(xù)除以基數(shù) */ } while (Topnext!=NULL) { e=PopS(Top)。 /*余數(shù)出棧 */ if (e9) printf(―%c‖,e+55)。 else printf(―%c‖,e+48)。 /*將余數(shù)轉(zhuǎn)為字符 */ } printf(\n)。 } 帶頭結(jié)點(diǎn)的鏈棧 2021/11/10 29 例：編寫(xiě)算法判斷字符串是否中心對(duì)稱(chēng)。 “ abcba‖ 、“ abccba‖是中心對(duì)稱(chēng)，“ abcab‖不是中心對(duì) 稱(chēng)。 分析：先將前半部字符入棧，然后出棧與后半部字符 逐個(gè)比較。 2021/11/10 30 int symmetry( Seqstring * str) { linkstack *Top。 char x。 int i=1。 int flag。 Top=InitStack( )。 /*建立空棧 */ while (i=strlen(str)/2) /*將前半部字符入棧 */ { PushS(Top,substr(str,i,1))。 /*調(diào)用取子串的算法，取 str中的第 i個(gè)字符入棧 */ i++}。 if(strlen(str)%2==1) i++。 /*如果字符串長(zhǎng)度是奇數(shù)，跳過(guò)中間一個(gè)字符 */ flag=1。 /*標(biāo)志變量置 1*/ while(Topnext!=NULL amp。amp。 i=strlen (str)) { x=PopS(Top)。 /*棧頂字符出棧 */ if(Substr(str,i,1)!=x) { flag=0。 break。 } /*不是中心對(duì)稱(chēng)，標(biāo)志變量置 0，終止循環(huán) */ else i++。 } return flag。 } 帶頭結(jié)點(diǎn)的鏈棧 2021/11/10 31 隊(duì)列 1. 隊(duì)列概念 1) 只允許在表的一端進(jìn)行刪除操作，在表的另一端進(jìn)行 插入的特殊線性表。 2) 隊(duì)尾 (rear)：可以進(jìn)行插入操作的一端。 3) 隊(duì)頭 (front)：可以進(jìn)行刪除操作的一端。 4) 特點(diǎn)：先進(jìn)先出（ FIFO）。 當(dāng)隊(duì)列中沒(méi)有元素時(shí)稱(chēng)為 空隊(duì)列 。 隊(duì)列的示意圖 a 1 a 2 a 3 a 4 …… a n 出隊(duì) 入隊(duì) 隊(duì)頭 f ro n t 隊(duì)尾 r ear 2021/11/10 32 ? 隊(duì)列的基本運(yùn)算有以下 7種： ? InitQueue( ):初始化隊(duì)列 。 ? SetnullQS (Q): 置 Q為一個(gè)空隊(duì)列 ， 即 清空隊(duì)列 。 ? EmptyQS(Q): 判隊(duì)列 Q是否為空隊(duì)列 。 當(dāng) Q是空隊(duì)列時(shí) ，返回 “ 真 ” 值 ， 否則返回 “ 假 ” 值 。 ? LengthQS(Q） ：求隊(duì)列長(zhǎng)度 ， 返回隊(duì)列中元素個(gè)數(shù) 。 ? GetfrontQS (Q): 取隊(duì)列 Q的隊(duì)頭元素 ， 隊(duì)列中元素保持不變 。 ? EnQueueQS (Q,X): 將元素 X插入隊(duì)列 Q的隊(duì)尾 。 簡(jiǎn)稱(chēng)為入隊(duì) (列 )。 ? DeQueueQS (Q): 刪除隊(duì)列 Q的隊(duì)頭元素 ， 簡(jiǎn)稱(chēng)為出隊(duì)(列 )。 函數(shù)返回原隊(duì)頭元素 。 2021/11/10 33 隊(duì)列的存儲(chǔ)結(jié)構(gòu) 1. 順序隊(duì)列 順序隊(duì)列的結(jié)構(gòu)類(lèi)型定義： define maxsize 1024。 typedef char datatype。 typedef struct { datatype data[maxsize]。 int front, rear。 } sequeue。 sequeue *sq。 入隊(duì)： sqrear++。 sqdata[sqrear]=x。 出隊(duì)： x=sqdata[sqfront+1]。 sqfront++。 初始時(shí)，隊(duì)列的頭、尾指針指向向量空間下界的前一個(gè) 置，在此設(shè)置為 1。 說(shuō)明： 規(guī)定隊(duì)頭指針 front總是指向當(dāng)前隊(duì)頭元素的 前一個(gè)位置 ，隊(duì)尾指針 rear指向當(dāng)前隊(duì)尾元素的位置。 2021/11/10 34 下圖說(shuō)明了在順序隊(duì)列中進(jìn)行出隊(duì)和入隊(duì)運(yùn)算時(shí)隊(duì)列中的數(shù) 據(jù)元素及其頭、尾指針的變化情況。 若 sqfront==sqrear成立，則當(dāng)前隊(duì)列是 空隊(duì) ； 若 (sqre