資源描述：
《數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、特殊線性表?xiàng)ｊ?duì)列串邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)物理結(jié)構(gòu)物理結(jié)構(gòu)順序棧鏈?zhǔn)綏ｍ樞蜿?duì)列順序存儲(chǔ)鏈?zhǔn)疥?duì)列鏈?zhǔn)酱鎯?chǔ)⑴棧的定義⑵操作特性⑶ADT定義⑴隊(duì)列定義⑵操作特性⑶ADT定義⑴串的定義⑵操作特性⑶ADT定義⑴基本操作的實(shí)現(xiàn)⑵時(shí)間性能⑴基本操作的實(shí)現(xiàn)⑵時(shí)間性能模式匹配第三章棧和隊(duì)列棧和隊(duì)列是兩種特殊的線性表，是操作受限的線性表，稱限定性DS“取”操作必須在這端進(jìn)行“放”操作必須在同一端進(jìn)行3.1棧（stack）定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表。表尾—棧頂表頭—棧底不含元素的空表稱空棧特點(diǎn)：先進(jìn)后出（FIL
2、O）3.1.1抽象數(shù)據(jù)類型棧的定義ADTStack{數(shù)據(jù)對(duì)象：D＝{ai
3、ai∈ElemSet,i=0,1,...,n-1,n≥0}數(shù)據(jù)關(guān)系：R1＝{
4、ai-1,ai∈D,i=1,...,n-1}約定an-1端為棧頂，a0端為棧底?；静僮鳎篒nitStack(&S);DestroyStack(&S);StackLength(S);StackEmpty(s);GetTop(S,&e);……}ADTStack3.1.2棧的表示與實(shí)現(xiàn)順序棧：是利用一塊地址連續(xù)的存儲(chǔ)單元來存放棧中的元素，同時(shí)要利用一個(gè)
5、指針top來指示棧頂元素的位置。//-----棧的順序存儲(chǔ)表示-----#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;順序棧示意圖*base*topstacksize......a1...aian*base*topstacksize初始空棧*top=*base;stacksize=STACK_INIT_SIZE順序棧棧的幾種狀態(tài)示意圖
6、top=0123450?？諚ｍ斨羔榯op,指向?qū)嶋H棧頂后的空位置，初值為0top123450進(jìn)棧Atop出棧棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=0,棧空，此時(shí)出棧，則下溢（underflow)top=M,棧滿，此時(shí)入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？誗tatusInitStack(SqStack&S){//構(gòu)造一個(gè)空棧SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemTy
7、pe));if(!S.base)exit(OVERFLOW);//存儲(chǔ)分配失敗S.top=S.base;//棧頂指針指向待插入的位置S.stacksize=STACK_INIT_SIZE;returnOK;}在此存儲(chǔ)結(jié)構(gòu)下的基本操作實(shí)現(xiàn):StatusPush(SqStack&S,SElemTypee){//插入元素e為新的棧頂元素if(S.top-S.base>=S.stacksize){//棧滿，追加存儲(chǔ)空間S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKIN
8、CREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存儲(chǔ)分配失敗S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;//先傳數(shù)據(jù)再移指針returnOK;}StatusPop(SqStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，//用e返回其值，并返回OK；//否則返回ERRORif(S.top==S.base)returnERROR;e=*--S.to
9、p；//先移指針再傳數(shù)據(jù)returnOK;}2.鏈棧（1）鏈棧的存儲(chǔ)結(jié)構(gòu)鏈棧是指采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的棧。鏈棧是一種特殊的單鏈表，即限定僅在表頭進(jìn)行插入和刪除操作的單鏈表，因此鏈棧的結(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)點(diǎn)結(jié)構(gòu)相同。a1a2an∧topdatanext棧頂棧底…3.2棧的應(yīng)用舉例3.2.1數(shù)制轉(zhuǎn)換十進(jìn)制N和其它進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問題,其中一個(gè)簡單算法基于下列原理:N=(Ndivd)10?d+Nmodd例如:(1348)10=2?83+5?82+0?8+4=(2504)8NNdiv8Nmod8 1348
10、1684168210 2125 202結(jié)果：2504計(jì)算時(shí)從低位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個(gè)數(shù)位顯示時(shí)按從高位到低位的順序輸出voidconversion() {InitStack(s);//建空棧scanf(“%d”,&n);//輸入一個(gè)非負(fù)十進(jìn)制整數(shù)while(n){//x不等于零循環(huán)push(s,n%8);//x/8第一個(gè)余數(shù)進(jìn)棧n=n/8;//整除運(yùn)
