北理工數(shù)據(jù)結構作業(yè)2

1、第三章作業(yè)1、 寫出下列程序段的輸出結果。viod main ( ) Stack S;char x, y;InitStack (S);x=c; y=k;Push(S, x); Push(S, a); Push(S, y);Pop(S, x); Push(S, t); Push(S, x);Pop(S, x); Push(S, s);while ( ! StackEmpty(S) ) Pop(S, y); printf (y);printf(x); 答：stack2、 簡述下列算法的功能（棧的元素類型SElemType為int）。（1）Ststus algo1(Stack S) int I, n

2、, A255; n=0; while ( ! StackEmpty(S) ) n+; Pop(S, An); for ( i=1; i<=n; i+ ) Push(S, An); 答：實現(xiàn)棧中元素的逆置（2）Status algo2(Stack S, int e) Stack T; int d; InitStack (T); while ( ! StackEmpty(S) ) Pop(S, d); if ( d!=e ) Push(T, d); while ( ! StackEmpty(T) ) Pop (T, d); Push (S, d); 答：通過棧T的輔助刪除棧S中所有值為e的元

3、素3、 設有4個元素1、2、3、4依次進棧，而出棧操作可隨時進行（進出棧可任意交錯進行，但要保證進棧次序不破壞1、2、3、4的相對次序），請寫出所有可能的出棧次序。答：共14種情況，順序如下：1234，1243，1324，1342，1432，2134，2143，2314，2341，2431，3421，3241，3214，4321。4、 寫出下列程序段的輸出結果（隊列中的元素類型QelemType為char）。viod main ( ) Queue Q; InitQueue(Q);char x=e, y=c;EnQueue(Q, h); EnQueue(Q, r); EnQueue(Q, y);

4、DeQueue(Q, x); EnQueue(Q, x);DeQueue(Q, x); EnQueue(Q,a);while ( ! QueueEmpty(Q) ) DeQueue(Q, y); printf(y);答：cha5、 簡述下列算法的功能（棧和隊列的元素類型均為int）。void algo3(Queue &Q) Stack S; int d; InitStack (S); while ( ! QueueEmpt(Q) ) DeQueue(Q, d); Push(S, d);while ( ! StackEmpty(S) ) Pop(S, d); EnQueue(Q, d);

5、 答：利用棧S將隊列Q中的元素進行逆置。6、 為了充分利用空間，將兩個棧共同存儲在長度為n的一維數(shù)組中，共享數(shù)組空間。設計兩個棧共享一維數(shù)組的存儲表示方式，畫出示意圖。答：設計兩個棧Stack1和Stack2共享數(shù)組空間，Stack1的棧底放在數(shù)組的首端，Stack2的棧底放在數(shù)組的尾端，分別向兩個棧中存儲相應的元素，兩個棧的棧頂分別向數(shù)組中間擴展。當總的存儲空間不大于數(shù)組長度時，數(shù)組空間將得到最大利用。當兩個棧占滿整個數(shù)組空間時，這時兩個棧共享一個長度為n的數(shù)組空間，再向棧中放元素時會發(fā)生上溢。0（Stack1底）12Stack1頂Stack2頂n-3n-2n-1（Stack2底）實驗二1、

6、簡單計算器。請按照四則運算加、減、乘、除、冪（）和括號的優(yōu)先關系和慣例，編寫計算器程序。要求： 從鍵盤輸入一個完整的表達式，以回車作為表達式輸入結束的標志。 輸入表達式中的數(shù)值均為大于等于零的整數(shù)。中間的計算過程如果出現(xiàn)小數(shù)也只取整。例如，輸入：4+2*5=輸出：14 輸入：(4+2)*(2-10)=輸出：-48程序如下：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define OK 1#define ERROR 0#define OVERFLOW -2#define STACK_INIT_SI

7、ZE 100 /存儲空間初始分配量#define STACKINCREMENT 10 /存儲空間分配增量typedef struct/定義運算符棧數(shù)據(jù)類型 char *base; char *top; int stacksize;SqStack1;typedef struct/定義操作數(shù)棧數(shù)據(jù)類型 int *base; int *top; int stacksize;SqStack2;int InitStack1(SqStack1 &S)/構造一個空的運算符棧 S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); if(!S.base)

8、 exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;/InitStack1int InitStack2(SqStack2 &S)/構造一個空的操作數(shù)棧 S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;/InitStack2char GetTop1(SqStack1 S)/若棧不空，則用ch

9、ar型元素e返回S的棧頂元素，并返回OK；否則返回ERROR char e; if(S.top=S.base) return ERROR; e=*(S.top-1); return e;/GetTop1int GetTop2(SqStack2 S)/若棧不空，則用int型元素e返回S的棧頂元素，并返回OK；否則返回ERROR int e; if(S.top=S.base) return ERROR; e=*(S.top-1); return e;/GetTop2int Push1(SqStack1 &S,char e)/插入char型元素e為新的棧頂元素 if(S.top-S.base

10、>=S.stacksize) S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;/Push1int Push2(SqStack2 &S,int e)/插入int型元素e為新的棧頂元素 if(S.top-S.base>=S.stacksize) S.base=(int *)re

11、alloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;/Push2int Pop1(SqStack1 &S,char &e)/若棧不空，則刪除S的棧頂元素，用char型元素e返回其值，并返回OK；否則返回ERROR if(S.top=S.base) return ERROR; e=*-S.top; return OK;

12、/Pop1int Pop2(SqStack2 &S,int &e)/若棧不空，則刪除S的棧頂元素，用int型元素e返回其值，并返回OK；否則返回ERROR if(S.top=S.base) return ERROR; e=*-S.top; return OK;/Pop2char Precede(char a,char b)/比較兩個相繼出現(xiàn)的運算符a和b間的優(yōu)先級關系switch(a)case '+':switch(b)case'+':return'>'break;case'-':return'>

13、;'break;case'*':return'<'break;case'/':return'<'break;case'(':return'<'break;case')':return'>'break;case'=':return'>'break;case'':return'<'break;case'-':switch(b)case'+&#

14、39;:return'>'break;case'-':return'>'break;case'*':return'<'break;case'/':return'<'break;case'(':return'<'break;case')':return'>'break;case'=':return'>'break;case'':ret

15、urn'<'break;case'*':switch(b)case'+':return'>'break;case'-':return'>'break;case'*':return'>'break;case'/':return'>'break;case'(':return'<'break;case')':return'>'break;

16、case'=':return'>'break;case'':return'<'break;case'/':switch(b)case'+':return'>'break;case'-':return'>'break;case'*':return'>'break;case'/':return'>'break;case'(':return&#

17、39;<'break;case')':return'>'break;case'=':return'>'break;case'':return'<'break;case'':switch(b)case'+':return'>'break;case'-':return'>'break;case'*':return'>'break;case

18、9;/':return'>'break;case'(':return'<'break;case')':return'>'break;case'=':return'>'break;case'':return'>'break;case'(':switch(b)case'+':return'<'break;case'-':return'<

19、'break;case'*':return'<'break;case'/':return'<'break;case'(':return'<'break;case')':return'='break;case'':return'<'break;case')':switch(b)case'+':return'>'break;case'-':

20、return'>'break;case'*':return'>'break;case'/':return'>'break;case')':return'>'break;case'=':return'>'break;case'':return'>'break;case'#':switch(b)case'+':return'<'brea

21、k;case'-':return'<'break;case'*':return'<'break;case'/':return'<'break;case'(':return'<'break;case'=':return'='break;case'':return'<'break;/Precedeint pow(int a,int b)/求冪函數(shù) int x; for(x=1;b

22、>0;b-) x=x*a; return x;/powint Operate(int a,char theta,int b)/操作數(shù)a和b進行運算 switch(theta)case'+':return(a+b);case'-':return(a-b);case'*':return(a*b);case'/':return(a/b);case'':return(pow(a,b);/Operateint In(char c)/判斷字符c是否為運算符if(c!='+'&&c!='-'&&c!='*'&&c!='/'&&c!=