[理學(xué)]第4章棧和隊(duì)列-wenkub.com
2024-10-13 21:23 本頁(yè)面
【正文】 free(s)。 qrear=qfront 。 if (EmptyQL(q)) { printf(“queue is empty”)。 //尾指針指向新結(jié)點(diǎn) qrearnext=NULL。 p=(linklist*)malloc(sizeof(linklist))。 else return(0)。 //頭結(jié)點(diǎn)指針域置空 return q。 ? 鏈隊(duì)列 *q 為空條件： q?front==q?rear 2021/11/10 52 ? 鏈隊(duì)列的基本運(yùn)算實(shí)現(xiàn) ① 鏈隊(duì)列初始化（建立空隊(duì)列） linkqueue * InitQL( ) { linkqueue* q 。鏈隊(duì)列的結(jié)點(diǎn)類型 typedef struct { linklist *front, *rear。 也是解決假溢出問(wèn)題的第三種方法。 return (0)。 sqlen=0。 空隊(duì)： sqlen==0成立 滿隊(duì)： sqlen==maxsize成立 隊(duì)尾指針為 （ sqfront+ sq len） %maxsize 2021/11/10 47 ① 隊(duì)列初始化 sequeue* InitSQ( ) { sequeue*sq； sq=(sequeue*)malloc (sizeof (sequeue))。 int front, len。 return (x)。 return NULL。 sqdata [sqrear]=x。 return (x)。 if (EmptyQS(sq)) { printf(queue is empty)?；?0 sqrear=maxsize1。 sqfront=maxsize1或 0。 具有空 /滿標(biāo)志的循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu) /*tag=1表示空； tag=0表示滿 */ /* 循環(huán)隊(duì)列的類型 */ maxsize1 maxsize1 0 1 2 0 1 2 2021/11/10 39 解決辦法（ 2）： 犧牲一個(gè)存儲(chǔ)單元，隊(duì)列的最大長(zhǎng) 度為 maxsize1，這是通常采用的更為簡(jiǎn)單的方法。 else sqrear++。 （ 2）將順序隊(duì)列構(gòu)造為環(huán)狀，形成循環(huán)隊(duì)列。 2021/11/10 34 下圖說(shuō)明了在順序隊(duì)列中進(jìn)行出隊(duì)和入隊(duì)運(yùn)算時(shí)隊(duì)列中的數(shù) 據(jù)元素及其頭、尾指針的變化情況。 出隊(duì)： x=sqdata[sqfront+1]。 } sequeue。 2021/11/10 33 隊(duì)列的存儲(chǔ)結(jié)構(gòu) 1. 順序隊(duì)列 順序隊(duì)列的結(jié)構(gòu)類型定義： define maxsize 1024。 ? EnQueueQS (Q,X): 將元素 X插入隊(duì)列 Q的隊(duì)尾 。 ? EmptyQS(Q): 判隊(duì)列 Q是否為空隊(duì)列 。 4) 特點(diǎn)：先進(jìn)先出（ FIFO）。 } return flag。 i=strlen (str)) { x=PopS(Top)。 if(strlen(str)%2==1) i++。 int flag。 分析：先將前半部字符入棧，然后出棧與后半部字符 逐個(gè)比較。 else printf(―%c‖,e+48)。 while (M!=0) { PushS (Top, M%base)。 scanf(―%d,%d‖, amp。 2021/11/10 27 十進(jìn)制 N和其它進(jìn)制數(shù)（二、八、十六進(jìn)制）的轉(zhuǎn)換， 基于下列原理 :采用除基數(shù)取余，直至商為 0為止的方法。 return (x)。 } else { } } x=(datatype*)malloc(sizeof(datatype))。 } 2021/11/10 25 ( 按 教材上定義棧 )鏈棧出棧操作 (不帶頭結(jié)點(diǎn) ) datatype * PopS(linkstack *S) { datatype * x。 p=Top next。 free(p)。 } else { } } 帶有頭結(jié)點(diǎn)的鏈棧出棧 ： if(Topnext==NULL) { ... } else { } x指向新開(kāi)辟的空間 出棧： (不帶頭結(jié)點(diǎn) , Top全局變量 ) x=(datatype*)malloc(sizeof(datatype))。 } 2021/11/10 24 datatype * PopS(linkstack *T) {datatype * x。 } 棧初始化 (不帶頭結(jié)點(diǎn) ): LinkStack * InitStack( ) { LinkStack *S 。 p=(StackNode *)malloc(sizeof(StackNode ))。 } StackNode。 pnext=Topnext。 Top=p。 }| 棧初始化 (不帶頭結(jié)點(diǎn) ): void InitStack( ) { Top=NULL。 void main( ) { …. InitStack ( )。 } linkstack。 } include include typedef char datatype。 pnext=Top。 （ 3）使用帶有頭結(jié)點(diǎn)的鏈棧。 } 置空棧 void InitStack( linkstack * Top) { Top=NULL。 return(Top)。 當(dāng) Top等于 NULL時(shí)，該鏈棧為空棧。 struct node *next。 return (temp)； 2021/11/10 18 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) —— 鏈棧 ? 定義： 采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧稱為鏈棧 。 STop 。 } 2021/11/10 14 判斷棧是否為空 int EmptyS(seqstack *s) { if (STop=0) return 0； //棧非空，返回 0 else return 1； //?？?，返回 1 } 求棧中元素個(gè)數(shù) int LengthS(seqstack*S) { return(STop+1) ； } 0下標(biāo)單元不用時(shí)： =1 0下標(biāo)單元不用時(shí)： return(STop)。 順序棧 : 2021/11/10 11 0 1 2 3 4 5 Top=1 Top=0 Top=4 Top=2 Top=1 A (a)空棧 (b)’A’進(jìn)棧 (c)’B’ ’C’ ’D’ ’E’進(jìn)棧 (d)’E’ ’D’出棧 (e)’C’ ’B’ ’A’ 出棧 0 1 2 3 4 5 * 數(shù)組下標(biāo)為 0的元素空間使用的情況 STop A B C D E A B C 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 STop STop STop S
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1