數(shù)據(jù)結(jié)構(gòu)答案第3章棧學(xué)習(xí)指導(dǎo)

1、3. 鏈棧用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)的棧稱為鏈棧。(1) 鏈棧的特點：(a) 數(shù)據(jù)元素的存儲與不帶頭結(jié)點的單鏈表相似:(b) 用指針top指向單鏈表的第一個結(jié)點:(c) 插入和刪除在top端進(jìn)行。(2) 鏈棧的存儲表示：/棧的存儲結(jié)構(gòu)/定義數(shù)據(jù)類型H定義一個結(jié)構(gòu)體的鏈指針/top為棧頂抬針typcdef struct stacknode datatype data;stnict stacknode 幺next;stacknode» * Linkstack；Linkstack top；(3) 基本操作的實現(xiàn)要點(a) 鏈棧進(jìn)棧之前不必判棧是否為滿。(b) 鏈棧出棧之前必須判棧是否為空，判斷的條

2、件：s->top=NULLo(c) 初始化棧(置?？?：s->top=NULLo(4) 進(jìn)棧操作：stacknodc *p=new stacknode; p->data=x;p->next=s->top;s->top=p:(5>出棧操作：int x;stacknode *p=s->top;x=p->data;s->top=p->next;delete p;return x;(6)取棧頂元素if(p!=NULL)x=s->top->data; return x:申請一個新結(jié)點/數(shù)據(jù)入棧/修改棧頂抬針定義一個變雖x.用以

3、存放出棧的元素棧頂描針抬向p棧頂元素送x/修改棧頂指針/回收結(jié)點p/返回棧頂元素H輸出棧頂元素/返回棧頂元素3.2典型習(xí)題分析【例1】若已知一個棧的入棧序列是1，2, 3,，n,其輸出序列是Pi, P2,廠，Pn, 若 P,=n,則 R二( )oA. iBn-iCn-i+1D不確定分析：棧的特點是后進(jìn)先岀，pi輸出為n, P2輸出為nl,Pi輸出為n-i,所以選C?！纠?】在對棧的操作中，能改變棧的結(jié)構(gòu)的是()。A. SEmpty(S)B SFuIl(S)C ReadTop (S) D InitStack(S)分析：SEmpty(S)是判棧滿函數(shù),SFull(S)是判?？蘸瘮?shù),ReadTop(

4、S)是讀棧頂元素的函數(shù), 它們都不改變棧中的數(shù)據(jù)和結(jié)構(gòu)。InitStack(S)為初始化棧函數(shù)，若棧S中原來有數(shù)拯存在， 則經(jīng)過初始化以后，就成為一個空棧，也就是說改變了棧的結(jié)構(gòu)。所以D為正確答案。【例3】“后進(jìn)先出”是棧的特點，那么岀棧的次序一立是入棧次序的逆序列嗎？分析：不一左。因為當(dāng)棧后而的元素未進(jìn)棧時，先入棧的元素可以先岀棧。例如將1、2、3 依次入棧，得到出棧的次序可以是：123、132、213、231、321五種。在1、2、3的六種全 排列中，只有312不可能是出棧的序列。例如213可以這樣得到：1入棧：2入棧，并出棧: 1出棧；3入棧，并出棧。312之所以不可能是岀棧的序列，原因

5、是：3第一個出棧，表示1、2必然在棧中，且2 是棧頂元素，它必須先于1岀棧。所以，312是不可能得到的出棧次序?！纠?】設(shè)一個棧的進(jìn)棧序列是a、b、c、d.進(jìn)棧的過程中可以出棧，不可能的出棧序列 是（）。A. d, c, b, aB. c, d, b, aC. d, c, a, b D. a, b, c, d分析：棧是僅能在表的一端進(jìn)行插入和刪除操作的線性表，即進(jìn)棧和出棧運算僅能在棧頂進(jìn) 行，其操作原則是后進(jìn)先岀。（1）要求出棧序列是d, c, b, a時，要將a, b, c, d都進(jìn)棧，再依次出棧。（2）要求出棧序列是c, d, b, a時，需要將a, b, c進(jìn)棧，c岀棧，d出棧，再b出棧

6、, a出棧。（3）要求岀棧序列是d, c, a, b時，需要將a、b、c、d依次進(jìn)棧，d岀棧，c出棧，當(dāng) 前棧頂元素是b,故a不能出棧。所以C是不可能的出棧序列。（4）要求出棧序列是a, b, c, d時，可將a、b、c、d逐個進(jìn)棧后立即出棧?！纠?】鐵路列車調(diào)度時，常把站臺設(shè)計成棧式結(jié)構(gòu)，如圖3-1所示。岀站進(jìn)站1,2,345,6圖3-1棧式站臺結(jié)構(gòu)（1）設(shè)有編號為1, 2, 3, 4, 5, 6的6倆列車順序開入棧式結(jié)構(gòu)的站臺，則可能的出棧的 序列有幾種？（2）進(jìn)棧順序如上所述，能否得到435612和325641兩個岀棧序列。答：（1）可能的出棧的序列有（1 /（6+ 1）*Ci，=132

7、（2）不能得到435612的岀棧序列。因為若在4, 3, 5, 6之后再將1, 2出棧，則1, 2必33232325325325632564325641圖3-2進(jìn)棧、出棧過程分析【例6】在鏈棧中為什么不必設(shè)頭結(jié)點? 分析：在鏈棧中，首結(jié)點為棧頂元素。在棧中的插入、刪除操作都在棧頂進(jìn)行，因此每次插入、 刪除操作都要修改棧頂指針。如果設(shè)置頭結(jié)點，則頭結(jié)點后跟的是棧頂元素，每次插入、刪 除操作就要修改頭結(jié)點中的指針。反正要修改一個指針，可見設(shè)置頭結(jié)點是沒有必要的?！纠?】指出下述程序段的功能是什么？void ProgKSeqStack *S) int i. n=0, a64;/設(shè)棧中的元素個數(shù)小于6

8、4while (! StackEmpty(S) an+=Pop(S);for (i=0; i<=n; i+)Push(S, ai);答：Progl的功能是將順序棧S中的元素逆置。例如，執(zhí)行Dcmol前S=(aba2,，a)則 執(zhí)行 Progl 后 S=(an,az, aj。【例8】指出下述程序段的功能是什么？void Prog2(ScqStack *S1, S2) SeqStack SI, S2.Tcmp;設(shè) SI 已存在，S2.Temp 已初始化DataType x;while (! StackEmpty(&Sl) x=Pop(&Sl);Push(&Temp,

9、x);while (! StackEmpty(&Tcmp) x=Pop (&Tcpm);Push(&Sl. x);Push(&S2, x);答：Prog2的功能是用Temp作為輔助棧，將SI復(fù)制到S2中，并保持S1中的內(nèi)容不變。 設(shè)執(zhí)行此程序段之前Sl=(ai,a2,，aj,執(zhí)行此程序段之后，Sl=(a,a2,，an), S2=(ai,a2, a。程序的第一個while語句把S1的內(nèi)容倒到Temp中，第二個while語句把Temp中的內(nèi)容分別倒到S1和S2中?！纠?】指出下述程序段的功能是什么？void Prog3 (SeqStack *S, char x) S

10、eqStack T;char i;InitStack (&T);while (! StackEmpty(S)if (i二Pop(S) !='k')Push(&T, i);while (! StackEmpty(&T) i=Pop (&T);Push(S, i);答：Prog3的功能是把棧S中值為“k”的結(jié)點刪除。 【例10寫出運行下列程序段的輸出結(jié)果void main() Stack S;char x,y;InitStack(S);/ 初始化棧x= Hc M;y=Hk “；Push(S.x);Push(S, Ha M);Push(S,y);Pop

11、(S.x);Push(StM);Push(S.x);Pop(S.x);Push(Ss ”)；While (!SEmpty(S) Pop(S,y);cout«y; ;cout«x;分析：本題主要是分淸變量的內(nèi)容進(jìn)棧，還是字符直接進(jìn)棧。按照程序，其進(jìn)棧、出棧的主 要步驟，以及變量x和y值的變化過程如圖3-3所示。在While循環(huán)語句中，棧頂數(shù)據(jù)依次 彈出到y(tǒng),并輸出。循環(huán)結(jié)朿輸岀"stac",最后輸出x的值"k",所以運行程序段的輸岀結(jié)果 為:"stack y=圖33進(jìn)棧、出棧過程分析3.3單元練習(xí)3解答一.判斷題答案題目123

12、45678910答案XdXXXXV（2）棧空二.填空題答案（1） 棧頂(3)0(1)(4) 0(1)(5)棧（6）?？?7)p->next=top；(8) +(或=S->top+l )(9)LS>ncxl（10）棧頂元素(11)頭（12）棧是否滿(13)棧是否空(14)鏈(15)LS->next=NULL（16）首(17)相同(18) B(19)ABC/+DE*.(20) C三.選擇題答案題目12345678910答案CDBDBAABDB題目11121314151617181920答案BAABBCBBCA四.答案（1 ） IIIOOOIOIO（2）求后綴表達(dá)式答案 IO

13、IIOOIIOOABACAD/0ABc*+ABc+*D*AB+C*EF852+/6 -D E / +E -G H / + / - D -（3）stack （分析見典型習(xí)題分析【例10）五.算法設(shè)計題答案（1）分析：用一整型變量top表示棧頂指針，top為0時表示棧為空。棧中元素從Sl開始存放元素?！救霔３绦虼a】void push (char x) if (top+M)>MAXLEN-1) printf ("堆棧溢岀！ ”);else if (top= =0) top+;S top=x:else top=top+M;S top=x;【岀棧程序代碼】void pop (char

14、x) if (top= =0)pnntf(“堆棧為空棧！ ”);else if (top=l) x= S topi; top:else x= S top; top=top-M;(2) 分析：設(shè)表達(dá)式在字符數(shù)組a中， 【程序代碼】int correct (char a)stack s;InitStack (s);for (i=0; i <strlen(a);i+)if(ai=X5)Push (sj(');else if (ai= =')')if SEmpty (s)return 0;elsePop ；if (SEmpty )pnntf(“配對正確！ “); else

15、pnntf(“配對錯誤！ “);(3) 【程序代碼】# includc<stdio.h>#include<stdlib.h>typedef struct stacknodeint data;使用一堆棧S來幫助判斷。/調(diào)用初始化棧函數(shù)/ SEmpty (s)為判?？蘸瘮?shù)/若棧為空返回0：否則出棧若?？?，說明配對正確，并返回1/配對錯誤返回0/棧的存儲結(jié)構(gòu)struct stacknode 切ext; stacknode;typedef structstacknode *top;/描向棧的抬針 linkstack:void Conversion(int n)/二十六進(jìn)制轉(zhuǎn)換函

16、數(shù)linkstack s:int x;s.top=NULL;dox=n%16;n=ii/16;stacknode *p;p=new (stacknode);p->next=s.top;s.top=p;s.top->data=x;while(n);printfC'ntt轉(zhuǎn)換以后的16進(jìn)制數(shù)值為：“);while(s.top) if (s.top->data<10)printf(,%dH,s.top->data);elseswitch (s.top->data) case 10: printf(,%c,VA,);break;case 11: printf(H%c*,B,);break;case 12: pri