數(shù)據(jù)結構棧和隊列

數(shù)據(jù)結構棧和隊列數(shù)據(jù)結構棧和隊列/NUMPAGES15數(shù)據(jù)結構棧和隊列數(shù)據(jù)結構棧和隊列實驗二棧和隊列一、實驗目的1、掌握棧的特點(先進后出FILO)及基本操作，如入棧、出棧等，棧的順序存儲結構和鏈式存儲結構，以便在實際問題背景下靈活應用。2、掌握隊列的特點(先進先出FIFO)及基本操作,如入隊、出隊等，隊列順序存儲結構、鏈式存儲結構和循環(huán)隊列的實現(xiàn)，以便在實際問題背景下靈活應用。二、實驗內容1、順序棧的實現(xiàn)和運算；2、循環(huán)隊列的實現(xiàn)和運算；3、棧的運用—十進制轉八進制運算。三、實驗要求1、學生用C++/C完成算法設計和程序設計并上機調試通過；2、撰寫實驗報告，提供實驗測試數(shù)據(jù)和實驗結果；3、分析算法，要求給出具體的算法分析結果，包括時間復雜度和空間復雜度，并簡要給出算法設計小結和心得。四、實驗準備1、掌握棧和隊列這兩種抽象數(shù)據(jù)類型的特點，并能在相應的應用任務中正確選用它們；2、熟練掌握順序棧和循環(huán)隊列的基本操作實現(xiàn)算法，特別應注意棧滿和棧空的條件以及它們的描述方法，循環(huán)隊列中隊滿和隊空的描述方法。3、在學習順序棧的基本操作實現(xiàn)算法時，應注意：在書上給出的結構定義是采用了一種動態(tài)管理方式（不夠時，可以再分配），但在C語言中，用數(shù)組來存儲順序棧，是靜態(tài)分配，即不能隨機分配空間，這點易引起大家的誤解。五、實驗步驟1、編程實現(xiàn)順序棧的各種基本運算，并在此基礎上設計一個主程序，完成如下功能：(1)初始化順序棧；(2)給定一個元素，將此元素壓入此棧中；(3)將棧頂一個元素彈出此棧。2、編寫一個程序實現(xiàn)循環(huán)隊列的各種基本運算，并在此基礎上設計一個主程序，完成如下功能：(1)初始化循環(huán)隊列；(2)給定一個元素，將此元素插入此隊列中；(3)將隊頭一個元素出隊。3、棧的運用實例十進制轉八進制。六、實驗參考代碼1、順序棧的實現(xiàn)和運算；#include<stdio.h>#include<stdlib.h>#defineOK1#defineERROR0#defineOVERFLOW-2typedefintElemType;typedefintStatus;//棧的順序存儲表示#defineSTACK_INIT_SIZE100//存儲空間的初始分配量#defineSTACKINCREMENT10//存儲空間的分配增量typedefstruct{ElemType*base;ElemType*top;intstacksize;}SqStack;//構造一個空棧SStatusInitStack(SqStack&S){S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//判棧S是否為空棧StatusStackEmpty(SqStackS){if(S.top==S.base)returnOK;elsereturnERROR;}//入棧函數(shù)StatusPush(SqStack&S,ElemTypee){if(S.top-S.base>=S.stacksize){S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}//出棧函數(shù)StatusPop(SqStack&S,ElemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//輸出順序棧函數(shù)voidOutStack(SqStackS){int*p;if(S.top==S.base){printf("這是一個空棧！");}elsefor(p=S.top-1;p>=S.base;p--)printf("%6d",*p);printf("\n");}//主函數(shù)voidmain(){SqStacks;intcord;ElemTypea;printf("第一次使用必須初始化！\n");do{printf("\n主菜單\n");printf("1初始化順序棧");printf("2插入一個元素");printf("3刪除棧頂元素");printf("4結束程序運行");printf("\n\n");printf("請輸入您的選擇(1,2,3,4)");scanf("%d",&cord);printf("\n");switch(cord){case1:InitStack(s);OutStack(s);break;case2:printf("請輸入要插入的數(shù)據(jù)元素：a=");scanf("%d",&a);Push(s,a);printf("%d進棧之后的棧：",a);OutStack(s);break;case3:Pop(s,a);printf("棧頂元素%d出棧之后的棧：",a);OutStack(s);break;case4:exit(0);}}while(cord<=4);}2、循環(huán)隊列的實現(xiàn)和運算；#include<stdio.h>#include<stdlib.h>#defineOK1#defineERROR0#defineOVERFLOW-2typedefintQElemType;typedefintStatus;//隊列的順序存儲表示#defineMAXQSIZE100//存儲空間的初始分配量typedefstruct{QElemType*base;intfront;intrear;}SqQueue;//構造一個空隊列QStatusInitQueue(SqQueue&Q){Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;returnOK;}//判隊列是否為空StatusQueueEmpty(SqQueueQ){if(Q.rear==Q.front)returnOK;elsereturnERROR;}//入隊函數(shù)StatusEnQueue(SqQueue&Q,QElemTypee){if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}//出隊函數(shù)StatusDeQueue(SqQueue&Q,QElemType&e){if(Q.rear==Q.front)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}//輸出循環(huán)隊列函數(shù)voidOutQueue(SqQueueQ){intn,i;if(Q.front==Q.rear){printf("這是一個空隊列！");}else{n=(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;i=1;while(i<=n){printf("%6d",Q.base[(Q.front+i-1)%MAXQSIZE]);i++;}printf("\n");}}//主函數(shù)voidmain(){SqQueueq;intcord;QElemTypea;printf("第一次使用必須初始化！\n");do{printf("\n主菜單\n");printf("1初始化循環(huán)隊列");printf("2進隊一個元素");printf("3出隊一個元素");printf("4結束程序運行");printf("\n\n");printf("請輸入您的選擇(1,2,3,4)");scanf("%d",&cord);printf("\n");switch(cord){case1:InitQueue(q);//調用初始化算法;OutQueue(q);break;case2:printf("請輸入要插入的數(shù)據(jù)元素：a=");scanf("%d",&a);EnQueue(q,a);//調用進隊算法;printf("%d進隊之后的隊列：",a);OutQueue(q);break;case3:DeQueue(q,a);//調用出隊算法;printf("隊頭元素%d出隊之后的隊列：",a);OutQueue(q);break;case4:exit(0);}}while(cord<=4);}3、棧的應用—十進制轉八進制#include<stdio.h>#include<stdlib.h>#defineOK1#defineERROR0#defineOVERFLOW-2typedefintElemType;typedefintStatus;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{ElemType*base;ElemType*top;intstacksize;}SqStack;//構造一個空棧SStatusInitStack(SqStack&S){S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//判棧S是否為空棧StatusStackEmpty(SqStackS){if(S.top==S.base)returnOK;elsereturnERROR;}//入棧函數(shù)StatusPush(SqStack&S,ElemTypee){if(S.top-S.base>=S.stacksize){S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}//出棧函數(shù)StatusPop(SqStack&S,ElemType&e){if(S.top==S.base)returnERROR;e=*--