數(shù)據(jù)結(jié)構(gòu) 棧 C語言實現(xiàn)

1、數(shù)學(xué)與信息技術(shù)學(xué)院20162017（下）學(xué)年計科專業(yè)2015級數(shù)據(jù)結(jié)構(gòu)實驗報告 3 學(xué)號：2015201018 姓名：汪繼超實驗名稱棧的應(yīng)用完成時間2017.04.01一.實驗?zāi)康?掌握棧的概念及其數(shù)據(jù)結(jié)構(gòu)的特點。2掌握兩個順序棧共享存儲空間的概念。3熟練掌握利用順序棧實現(xiàn)棧的基本運算，特別注意棧滿及?？盏臈l件及它們的描述方法。4加強編輯與調(diào)試C語言程序的能力。二.實驗要求1 要求界面設(shè)計友好2 采用順序棧完成。3 注意類C和C的轉(zhuǎn)換。4 上機調(diào)試通過，認(rèn)真書寫實驗報告。三.實驗原理 棧是兩種特殊的線性表。棧是限定只能在表的一端進行插入和刪除的線性表，它又稱為“后進先出”表；由于棧是線性表的一

2、種特例，所以它可以使用順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，棧的順序存儲結(jié)構(gòu)稱為順序棧，棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧。順序存儲結(jié)構(gòu)可用一維數(shù)組來實現(xiàn)，而鏈?zhǔn)酱鎯Y(jié)構(gòu)可用指針來實現(xiàn)。四.實驗內(nèi)容利用順序棧的運算，編寫將任意一個十進制整數(shù)轉(zhuǎn)換成二至九之間的任一進制數(shù)并輸出。實驗過程：/*注：此程序為棧的操作實現(xiàn)與應(yīng)用*/#include #include #include #include #include #define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int SElemType;typedef int QElemType;/*棧的存儲結(jié)

3、構(gòu)*/typedef structSElemType *base; /*棧低指針*/SElemType *top; /*棧頂指針*/int stacksize; /*棧當(dāng)前已分配的所有空間，不是已使用的空間長度*/SqStack;/*start*隊列的存儲結(jié)構(gòu)*/typedef struct QNodeQElemType data; struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;/*隊列的存儲結(jié)構(gòu)*end*/*函數(shù)聲明*/SElemType GetTop(SqSta

4、ck *S;void Push(SqStack *S,SElemType e;bool SEmpty(SqStack *S;SElemType Pop(SqStack *S;void main(;/括號匹配-startvoid match(SqStack *Schar str20;int i=0,flag;fflush(stdin;printf("n Please enter a string: "scanf("%s",&str;while(stri!='0'&&flag!=0switch(stricase 

5、9;(':Push(S,'('break;case '':if(*(S->top-1='('flag=1;Pop(S;else flag=0; break;case '':Push(S,''break;case '':if(*(S->top-1=''flag=1;Pop(S;else flag=0; break;case '':Push(S,''break;case '':if(*(S->top-1='

6、'flag=1;Pop(S;else flag=0; break;default :flag=0;break;i+;if(flag=1&&(SEmpty(S=0printf("n success!n"else printf("n error!n"/括號匹配-end/Queue逆置-startLinkQueue * InitQ(LinkQueue *Q;Q=(LinkQueue *malloc(sizeof(LinkQueue;Q->front=Q->rear=(QueuePtrmalloc(sizeof(QNode;i

7、f(!Q->front exit(1;Q->front->next=NULL;printf("Successful Q!"return Q;void EnQ(LinkQueue *Q,QElemType e /入隊QueuePtr p;p=(QueuePtrmalloc(sizeof(QNode;if(!p exit(1;p->data=e;p->next=NULL;Q->rear->next=p;Q->rear=p;int DeQ(LinkQueue *Q /出隊int e;QueuePtr p;if(Q->front

8、=Q->rear return 0;elsep=Q->front->next;e=p->data;Q->front->next=p->next;if(Q->rear=p Q->rear=Q->front;free(p;return e;void algo3(LinkQueue *Q,SqStack *S /逆置int d;while(!(Q->front=Q->reard=DeQ(Q;Push(S,d;while(SEmpty(S EnQ(Q,Pop(S;void tes(LinkQueue *Q,SqStack *S /

9、逆置主調(diào)函數(shù)int i,e,n;printf("n您要輸入的數(shù)據(jù)條數(shù)是："scanf("%d",&n;printf("n請輸入需逆置數(shù)據(jù)："for(i=0;i scanf("%d",&e;EnQ(Q,e;algo3(Q,S;printf("n逆置后的數(shù)據(jù)順序："while(!(Q->front=Q->rearprintf("%3d",DeQ(Q; printf("n"free(Q;/Queue逆置-end/回文-startvoi

10、d Huiwen(LinkQueue *Q,SqStack *Schar str20;int i=0,flag;fflush(stdin;printf("n Please enter a string: "scanf("%s",&str;while(stri!='0'Push(S,stri;EnQ(Q,stri;i+;while(SEmpty(S&&flag!=0if(DeQ(Q=Pop(S flag=1;else flag=0;if(flag=1printf("n success!n"else

11、 printf("n error!n"/回文-endSqStack * InitStack( /*1.初始化棧*/SqStack *S;S=(SqStack *malloc(sizeof(SqStack;S->base=(SElemType *malloc(STACK_INIT_SIZE*sizeof(SElemType;if(!S | !S->base exit(1;S->top=S->base;S->stacksize=STACK_INIT_SIZE;return S;bool SEmpty(SqStack *S /*2.判?？?/if(S

12、->top=S->base return 0;else return 1; /*1表示棧不空*/void Push(SqStack *S,SElemType e /*3.入棧*/if(S->top-S->base >= S->stacksize S->base=(SElemType *realloc(S->base,(S->stacksize+STACKINCREMENT*sizeof(SElemType;if(!S->base exit(1;printf("n空間不夠，開辟新空間成功！n"S->top=S-

13、>base+S->stacksize;S->stacksize +=STACKINCREMENT;*S->top+=e;SElemType Pop(SqStack *S /*4.出棧*/if(S->top=S->basereturn 0;printf("nThe sequence stack is empty!"else return *(-S->top;void display(SqStack *S /*5.打印*/int e;SqStack *T;T=InitStack(; /*1.新構(gòu)建一個棧T*/while(SEmpty(S

14、e=Pop(S;Push(T,e;/*2.將出棧打印的元素入棧T*/printf("%5d",e; /*當(dāng)棧不空依次打印*/while(SEmpty(T Push(S,Pop(T;/*3.將棧T中元素出棧并入棧到棧S中*/free(T;printf("n"int StackLength(SqStack *S /*6.統(tǒng)計棧長度*/printf("n統(tǒng)計得棧的長度為：%dn",(S->top-S->base;return (S->top-S->base;void search(SqStack *S,SElemTy

15、pe e /*7.查找*/int count=0,flag=0;SqStack *T;T=InitStack(;while(SEmpty(Sif(e=GetTop(Scount+;flag=1;printf("n%d 已找到元素：%dn",count,e;Push(T,Pop(S;while(SEmpty(T Push(S,Pop(T;free(T;if(flag=0 printf("n沒有找到元素：%dn",e;void modify(SqStack *S,SElemType e /*8.修改*/int e1,count=0,flag=0,a;SqSt

16、ack *T;T=InitStack(;while(SEmpty(Sif(e=GetTop(S count+;flag=1;printf("n%d 已找到元素：%dn",count,e;printf("n1.修改 2.不修改："scanf("%d",&a;switch(acase 1:e1=Pop(S;printf("n將元素%d修改為：",e; scanf("%d",&e1;Push(S,e1;printf("n修改成功！n"/除輸入1之外的情況都不做任何操

17、作Push(T,Pop(S;while(SEmpty(T Push(S,Pop(T;free(T;if(flag=0 printf("n沒有找到元素：%dn",e;void ClearStack(SqStack *S /*9.清空棧*/S->top=S->base;printf("n清空棧成功！n"void DestoryStatck(SqStack *S /*10.銷毀棧*/ S->top=S->base; free(S->base; S->base=NULL; S->top=NULL;S->stacks

18、ize=0;free(S;printf("n銷毀棧成功！n" SElemType GetTop(SqStack *S /*11.取棧頂元素*/if(S->top=S->baseprintf("nThe sequence stack is empty!n"return 0;else return *(S->top-1; /*區(qū)別于Pop中的*-S->top,*(S->top-1不改變S->top指針的指向*/ /進制轉(zhuǎn)換模塊-startvoid jinzhizhuanhuan(SqStack *Schar a;int n

19、,x,x1,q;dodosystem("cls"printf(" 歡迎來到十進制轉(zhuǎn)換為二至九進制桟運算中心nn"printf("請輸入您要轉(zhuǎn)換為的進制數(shù)2-9："fflush(stdin;scanf("%d",&n;if(n>9|n<2printf("n輸入錯誤！請重新輸入！n"system("pause"while(n>9|n<2;printf("n請輸入您要轉(zhuǎn)換的十進制數(shù)："fflush(stdin;scanf(&quo

20、t;%d",&x;x1=x;while(x!=0q=x%n;x /=n;Push(S,q;printf("n%d轉(zhuǎn)換成%d進制數(shù)為：",x1,n;/display(S;while(SEmpty(S printf("%d",Pop(S; /*當(dāng)棧不空依次打印*/printf("nn是否繼續(xù)進行(y or n: "fflush(stdin;/清空在此前輸入緩沖區(qū)a=getchar(;while(a='y'|a='Y'/進制轉(zhuǎn)換模塊-end/棧的全部操作實現(xiàn)模塊-startvoid Menu

21、2( printf(" 棧的操作實現(xiàn) nn"printf(" *菜單*n" printf(" * 1.初始化棧 2.判?？?*n" printf(" * 3.入棧 4.出棧 *n" printf(" * 5.打印 6.統(tǒng)計棧長度 *n"printf(" * 7.查找 8.修改 *n"printf(" * 9.清空棧 10.銷毀棧 *n" printf(" * 11.取棧頂元素 0.退出 *n"printf(" *n"

22、 void caozuoshixian(SqStack *Sint i,e,n,c,flag;char a;system("cls"doMenu2(;printf("n請選擇你需要操作的步驟(0-11: "fflush(stdin; /*清空在此前輸入緩沖區(qū)*/scanf("%d",&n;if(n>=0 && n<=11 flag=1;elseflag=0;system("cls"printf("您輸入有誤，請重新選擇!n"while(flag=0;while

23、(flag=1switch(n /*當(dāng)程序執(zhí)行到這里時，表明跳出上一個do-while */case 1:S=InitStack(;printf("n初始化棧成功！n"break; /*1.初始化棧，因為程序一開始做了初始化，所以這里是做重復(fù)工作，僅只是作為初學(xué)者強調(diào)棧初始化概念！*/case 2:c=SEmpty(S;if(c=0 printf("n當(dāng)前棧為空！n"else printf("n當(dāng)前棧不為空！n"break; /*2.判?？?/case 3:printf("n請輸入您要入棧的元素條數(shù)："scanf(

24、"%d",&n;if(n<=0printf("n輸入不合法！n"break;printf("n請依次輸入入棧的元素："for(i=0;i scanf("%d",&e;Push(S,e;printf("n數(shù)據(jù)錄入成功！n"break; /*3.入棧*/case 4:if(S->top=S->base printf("nThe sequence stack is empty!n"else printf("n元素%d已出棧！n"

25、,Pop(S;break; /*4.出棧*/case 5:printf("n棧當(dāng)前數(shù)據(jù)："display(S;break; /*5.打印*/case 6:StackLength(S;break; /*6.統(tǒng)計棧長度*/case 7:printf("n請輸入您要查找的元素："scanf("%d",&e;search(S,e;break; /*7.查找*/case 8:printf("n請輸入您要修改的元素："scanf("%d",&e;modify(S,e;break; /*8.修

26、改*/case 9:ClearStack(S;break; /*9.清空棧*/case 10:DestoryStatck(S;break; /*10.銷毀棧*/case 11:if(S->top=S->base printf("nThe sequence stack is empty!n"else printf("n取得棧頂元素：%d n",GetTop(S;break; /*11.取棧頂元素*/case 0:main(;break;default:printf("n您輸入有誤，請重新選擇!n"break;/goto st

27、art;printf("n是否繼續(xù)進行(y or n: "fflush(stdin;/清空在此前輸入緩沖區(qū)a=getchar(;if(a='y'|a='Y'flag=1;system("cls" /*清屏*/Menu2(; /*調(diào)用菜單函數(shù)*/printf("請再次選擇你需要操作的步驟(0-11: "fflush(stdin; /清空在此前輸入緩沖區(qū)scanf("%d",&n;else flag=0;/棧的全部操作實現(xiàn)模塊-endvoid Menu( printf(" 歡迎使用棧的操作實現(xiàn)與應(yīng)用系統(tǒng) nn"printf(" *菜單*n" printf(" * 1.棧運算之十進制整數(shù)轉(zhuǎn)換 2.棧的操作實現(xiàn) *n" printf(" * 3.逆置實現(xiàn) 4.括號匹配 *n" printf(" * 5.回文檢測 0.退出 *n"printf(" *n" void main(char b;int n;LinkQueue *Q;Q=InitQ(;SqStack *S;S=InitStack(;system("color 0A"syst