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