數據結構第三章(棧與隊列)習題參考答案

　　一基礎知識題

　　設將整數依次進棧但只要出棧時棧非空則可將出棧操作按任何次序夾入其中請回答下述問題

　　()若入出棧次序為Push() Pop()Push()Push() Pop() Pop( )Push() Pop( )則出棧的數字序列為何(這裡Push(i)表示i進棧Pop( )表示出棧)?

　　() 能否得到出棧序列和?並說明為什麼不能得到或者如何得到

　　()請分析的種排列中哪些序列是可以通過相應的入出棧操作得到的

　　鏈棧中為何不設置頭結點?

　　答鏈棧不需要在頭部附加頭結點因為棧都是在頭部進行操作的如果加了頭結點等於要對頭結點之後的結點進行操作反而使算法更復雜所以只要有鏈表的頭指針就可以了

　　循環隊列的優點是什麼? 如何判別它的空和滿?

　　答循環隊列的優點是它可以克服順序隊列的假上溢現象能夠使存儲隊列的向量空間得到充分的利用判別循環隊列的空或滿不能以頭尾指針是否相等來確定一般是通過以下幾種方法一是另設一布爾變量來區別隊列的空和滿二是少用一個元素的空間每次入隊前測試入隊後頭尾指針是否會重合如果會重合就認為隊列已滿三是設置一計數器記錄隊列中元素總數不僅可判別空或滿還可以得到隊列中元素的個數

　　設長度為n的鏈隊用單循環鏈表表示若設頭指針則入隊出隊操作的時間為何? 若只設尾指針呢?

　　答當只設頭指針時出隊的時間為而入隊的時間需要n因為每次入隊均需從頭指針開始查找找到最後一個元素時方可進行入隊操作若只設尾指針則出入隊時間均為因為是循環鏈表尾指針所指的下一個元素就是頭指針所指元素所以出隊時不需要遍歷整個隊列

　　指出下述程序段的功能是什麼?

　　() void Demo(SeqStack *S){

　　int i; arr[] ; n= ;

　　while ( StackEmpty(S)) arr[n++]=Pop(S);

　　for (i= i< n; i++) Push(S arr[i]);

　　} //Demo

　　() SeqStack S S tmp;

　　DataType x;

　　//假設棧tmp和S已做過初始化

　　while ( ! StackEmpty (&S))

　　{

　　x=Pop(&S) ;

　　Push(&tmpx);

　　}

　　while ( ! StackEmpty (&tmp) )

　　{

　　x=Pop( &tmp);

　　Push( &Sx);

　　Push( &S x);

　　}

　　() void Demo( SeqStack *S int m)

　　{ // 設DataType 為int 型

　　SeqStack T; int i;

　　InitStack (&T);

　　while (! StackEmpty( S))

　　if(( i=Pop(S)) !=m) Push( &Ti);

　　while (! StackEmpty( &T))

　　{

　　i=Pop(&T); Push(Si);

　　}

　　()void Demo( CirQueue *Q)

　　{ // 設DataType 為int 型

　　int x; SeqStack S;

　　InitStack( &S);

　　while (! QueueEmpty( Q ))

　　{x=DeQueue( Q); Push( &Sx);}

　　while (! StackEmpty( &s))

　　{ x=Pop(&S); EnQueue( Qx );}

　　}// Demo

　　() CirQueue Q Q; // 設DataType 為int 型

　　int x i m = ;

　　 // 設Q已有內容 Q已初始化過

　　while ( ! QueueEmpty( &Q) )

　　{ x=DeQueue( &Q ) ; EnQueue(&Q x); m++;}

　　for (i=; i< n; i++)

　　{ x=DeQueue(&Q) ;

　　EnQueue( &Q x) ; EnQueue( &Q x);}

　　答

　　()程序段的功能是將一棧中的元素按反序重新排列也就是原來在棧頂的元素放到棧底棧底的元素放到棧頂此棧中元素個數限制在個以內

　　()程序段的功能是利用tmp棧將一個非空棧的所有元素按原樣復制到一個空棧當中去

　　()程序段的功能是將一個非空棧中值等於m的元素全部刪去

　　()程序段的功能是將一個循環隊列反向排列原來的隊頭變成隊尾原來的隊尾變成隊頭

　　()首先指出程序可能有印刷錯誤for語句中的n應為m才對這段程序的功能是將隊列的所有元素復制到隊列中去但其執行過程是先把隊列的元素全部出隊進入隊列然後再把隊列的元素復制到隊列中

　　二算法設計題

　　回文是指正讀反讀均相同的字符序列如abba和abdba均是回文但good不是回文試寫一個算法判定給定的字符向量是否為回文(提示將一半字符入棧)

　　解根據提示算法可設計為

　　//ishuiwenh 存為頭文件

　　int IsHuiwen( char *S)

　　{

　　SeqStack T;

　　int i l;

　　char t;

　　InitStack( &T);

　　l=strlen(S); //求向量長度

　　for ( i=; i

　　Push( &T S[i]);

　　while( !EmptyStack( &T))

　　{

　　// 每彈出一個字符與相應字符比較

　　t=Pop (&T);

　　if( t!=S[li]) { return ;}// 不等則返回

　　}

　　return ; // 比較完畢均相等則返回

　　}

　　// 以下程序用於驗證上面的算法

　　//以下是棧定義( 存為stackh)

　　//出錯控制函數

　　#include

　　void Error(char * message)

　　{

　　fprintf(stderr Error: %s\nmessage);

　　exit();

　　}

　　// 定義棧類型

　　#define StackSize

　　typedef char Datatype;

　　typedef struct{

　　Datatype data[StackSize];

　　int Top;

　　} SeqStack;

　　void InitStack( SeqStack *S)

　　{

　　//初始化(置空棧)

　　S>Top=;

　　}

　　int EmptyStack(SeqStack *S)

　　{ //判棧空

　　return S>Top == ;

　　}

　　int FullStack (SeqStack *S)

　　{ // 判棧滿

　　return S>Top==StackSize;

　　}

　　void Push (SeqStack *S Datatype x)

　　{ //進棧

　　if(FullStack(S))

　　Error(Stack overflow);

　　S>data[++S>Top]=x;

　　}

　　Datatype Pop(SeqStack *S)

　　{ // 出棧(退棧)

　　if (EmptyStack( S) )

　　Error( Stack underflow);

　　return S>data[S>Top];

　　}

　　//取棧頂元素(略)

　　//以下是主程序

　　#include

　　#include stackh>

　　#include ishuiwenh

　　void main( )

　　{

　　char Str[]=;

　　printf(輸入一個字符串:\n);

　　scanf(%sStr);

　　if( IsHuiwen(Str))

　　printf( \n這個字符串是回文);

　　else printf(\n這個字符串不是回文);

　　}

　　附肖平來信指出問題

　　個人認為如題目所言abba和abdba均是回文但對於這兩種回文需要區別對待原算法在判斷類似abdba的回文時會認為其不是回文而與題意相違背!

　　我的編程思想是設置一個float型的變量用於存放字符串的長度再利用取整函數對長度為奇數的回文進行判別若將字符串長度附給一整型變量那麼無論該整形變量除任何整數其結果仍然是一整數因此必須設一實型變量!判斷結束後若是回文返回不是則返回

　　我的算法如下已驗證通過

　　int HuiWen(char *p)

　　{

　　int i;

　　float t;

　　SeqStack S;

　　InitStack(&S);

　　t=strlen(p);

　　for(i=;i<=t/;i++)

　　Push(&Sp[i]);

　　if(floor(t/)!=(t/)) //針對abdba類的回文

　　i++;

　　while(p[i]!=\)

　　if(Pop(&S)==p[i])

　　i++;

　　else

　　return();

　　}

　　=================================================

　　也可以直接用字符指針而不用字符數組來處理只需對算法稍作修改!

　　算法如下已驗證通過

　　int HuiWen(char *p)

　　{

　　int i;

　　float t;

　　SeqStack S;

　　InitStack(&S);

　　t=strlen(p);

　　for(i=;i<=t/;i++p++)

　　Push(&S*p);

　　if(floor(t/)!=(t/)) //針對abdba類的回文

　　p++;

　　while(*p!=\)

　　if(Pop(&S)==*p)

　　p++;

　　else

　　return();

　　}

　　利用棧的基本操作寫一個將棧S中所有結點均刪去的算法void Cle
From:http://tw.wingwit.com/Article/program/sjjg/201311/23676.html