數據結構實驗——棧(附程序).doc

實驗二 棧一、實驗目的 1.了解棧的特性。 2.掌握棧的順序表示和實現。 3.掌握棧的鏈式表示和實現。二、實驗內容 實驗2.1棧的順序表示和實現 編寫一個程序實現順序棧的各種基本運算，并在此基礎上設計一個主程序，完成如下功能： (1)初始化順序棧。 (2)插入元素。 (3)刪除棧頂元素。 (4)取棧頂元素。 (5)遍歷順序棧。 (6)置空順序棧。 實驗2. 2棧的鏈式表示和實現 編寫一個程序實現鏈棧的各種基本運算，并在此基礎上設計一個主程序，完成如下功能： (1)初始化鏈棧。 (2)鏈棧置空。 (3)入棧。 (4)出棧。 (5)取棧頂元素。 (6)遍歷鏈棧。 順序棧#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef structint *base;int *top;int stacksize;SqStack;int InitStack(SqStack &S)S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int);if(!S.base)exit(0);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return 0;/初始化順序棧int Push(SqStack &S,int e)if(S.top-S.base=S.stacksize)S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int);if(!S.base)exit(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return 0;/插入元素eint Pop(SqStack &S,int e)if(S.top=S.base)return 0;e=*-S.top;printf(刪除的棧頂元素%5d,e);printf(n);return 0;/刪除棧頂元素eint Gettop(SqStack &S,int e)if(S.top=S.base)return 0;e=*(S.top-1);printf(返回的棧頂元素%5d,e);printf(n);return 0;/返回棧頂元素evoid PrintStack(SqStack &S) int *k; printf(順序棧中的元素：n); for(k=S.base;k!=S.top;k+)printf(%5d,*k); printf(n);/遍歷順序棧void ClearStack(SqStack &S)S.top=S.base;/置空順序棧void main()int e,i,n; SqStack S;InitStack(S);printf(1插入頂元素；2刪除頂元素；3返回頂元素；4置空順序棧；0結束運行n); printf(n);printf(n);printf(n); printf(n);printf(n); printf(選擇: ); scanf(%d,&n);printf(n);printf(n); while(n!=0) switch(n) case 1:printf(插入棧頂元素);scanf(%d,&e);Push(S,e);PrintStack(S);printf(n);printf(n);break;case 2:Pop(S,e);PrintStack(S);printf(n);printf(n);break;case 3:Gettop(S,e);printf(n);printf(n);break;case 4:printf(已置空順序棧);ClearStack(S);printf(n);printf(n);break; printf(選擇: );scanf(%d,&n);printf(n);printf(n); printf(結束運行。再見！n);鏈式棧#include#includetypedef struct SNode int data; struct SNode *next;SNode,*Stack;typedef structStack top;int length;SqStack;/定義鏈式棧的結構體int InitStack(SqStack &S)S.top=NULL;S.length=0;return 0;/初始化鏈式棧int Push(SqStack &S,int e)Stack p;p=(Stack)malloc(sizeof(SNode);if(!p)exit(0);p-data=e;p-next=S.top;S.top=p;S.length+;return 0;/插入元素eint Pop(SqStack &S)if(!S.top)return 0;elseStack q;q=S.top;S.top=S.top-next;-S.length;free(q); return 0;/刪除棧頂元素eint GetTop(SqStack &S)if(!S.top)return 0;elseprintf(返回棧頂元素%5dn,S.top-data);return 0;/返回棧頂元素int PrintStack(SqStack &S)Stack p;printf(鏈式隊列中的元素);p=S.top;if(S.top!=NULL)while(p!=NULL)printf(%5d,p-data);p=p-next;elseprintf(隊列為空n);printf(n);return 0;/遍歷鏈式棧int ClearStack(SqStack &S)S.top=NULL;printf(已置空鏈式棧);printf(n);return 0;/置空鏈式棧void main()SqStack S;int e,m;printf(n);printf(n);printf(n);printf(n);printf(1插入元素；2刪除元素；3返回棧頂元素4置空鏈式棧0結束運行n);printf(n);printf(n);printf(n);InitStack(S); printf(n);printf(n);printf(選擇: ); scanf(%d,&m);printf(n);printf(n); while(m!=0) switch(m) case 1:printf(插入元素：);scanf(%d,&e);Push(S,e);PrintStack(S);printf(n);printf(n);break;case 2:Pop(S);PrintStack(S);printf(n);printf(n);break;case 3: