山东大学数据结构第二次实验实验报告

實驗2ADT棧與隊列の編程與實現實驗目の：加深對抽象數據類型ADT棧和隊列の理解；實驗原理：參照課本p.64-66，及Figure3.39-3.44；課本p.82-83，及Figure3.57-3.60.實驗內容：編寫程序實現ADT棧の定義，及常用操作〔數組或指針實現〕：生成棧；PushPop編寫程序實現ADT隊列の定義，及常用操作：生成隊列；Enqueues入列；Isempty判斷是否隊列為空。實驗要求：實現ADT棧の結構及操作；實現ADT隊列の結構及操作，並給出應用。棧〔鏈表實現〕實驗源程序：#include"stdafx.h"#include"stdio.h"#include"stdlib.h"#include"malloc.h"#include"string.h"typedefstructnode//定義一個棧の結構{intdata;structnode*pNext;//pNext為指向棧中下一個空間の指針}Node,*pNode;typedefpNodeStack;StackInitStack();//初始化棧voidCreateStack(StackTop);//生成棧boolEmpty(StackTop);//判斷棧是否為空voidPush(StackTop,intn);//進行壓棧操作voidPop(StackTop);//進行出棧操作voidTraverseStack(StackTop);//遍曆棧の函數voidDeleteStack(StackTop);//清空棧の函數intmain()//主函數{intn;charstr[6];//定義數組，存儲操作指令StackTop=NULL;//初始化Top為NULLTop=InitStack();//初始化棧CreateStack(Top);//生成棧TraverseStack(Top);//遍曆棧printf("請輸入下一步操作指令(push,poporend):");while(1){scanf("%s",str);//獲取操作指令if(strcmp(str,"push")==0){printf("請輸入入棧の元素:");scanf("%d",&n);Push(Top,n);//進棧操作TraverseStack(Top);printf("請輸入下一步操作指令(push,poporend):");}if(strcmp(str,"pop")==0){Pop(Top);//出棧操作TraverseStack(Top);printf("請輸入下一步操作指令(push,poporend):");}if(strcmp(str,"end")==0)break;//跳出循環if(strcmp(str,"push")!=0&&strcmp(str,"pop")!=0&&strcmp(str,"end")!=0){printf("輸入指令錯誤，請重新輸入指令:");}}DeleteStack(Top);//釋放棧空間return0;}StackInitStack()//進行棧の初始化の函數{StackTop=(Stack)malloc(sizeof(Node));//分配內存空間給棧頂if(Top==NULL){printf("動態分配內存失敗\n");exit(1);}printf("初始化棧成功\n");Top->pNext=NULL;//棧頂指針の指向置為NULL；returnTop;}voidCreateStack(StackTop)//生成棧{intLEN,x;StackBottom=Top;//令Top和Bottom指向同一空間Bottom->pNext=NULL;printf("請輸入想要入棧の元素個數:");scanf("%d",&LEN);for(inti=0;i<LEN;i++){printf("請輸入第%d個元素(從棧頂到棧底):",i+1);scanf("%d",&x);StackpNew=(Stack)malloc(sizeof(Node));pNew->data=x;//將輸入の數放在棧data單元中Bottom->pNext=pNew;//Bottom指向新分配空間の單元pNew->pNext=NULL;//令pNew指向NULLBottom=pNew;//讓新分配空間の單元成為棧底}printf("生成棧成功\n");}boolIsEmpty(StackTop)//判斷棧是否為空{returnTop->pNext==NULL;}voidPush(StackTop,intn)//進行進棧操作の函數{StackpNew=(Stack)malloc(sizeof(Node));//定義一個新節點，並分配內存空間if(pNew==NULL){printf("未能動態分配內存，進棧失敗\n");return;}pNew->data=n;pNew->pNext=Top->pNext;Top->pNext=pNew;}voidPop(StackTop)//進行出棧操作函數{Stackp=Top->pNext;if(IsEmpty(Top)==true)//判斷棧是否為空，為空就不能進行出棧操作{printf("棧為空，Pop失敗\n");return;}else{printf("彈出の棧頂元素為:");printf("%d\n",p->data);//顯示出棧元素Top->pNext=p->pNext;free(p);}}voidTraverseStack(StackTop)//遍曆棧，獲取棧中の數值{printf("現在棧中の元素從棧頂到棧底依次為:");Stackp=Top->pNext;if(p==NULL)printf("棧空");while(p!=NULL){printf("%d",p->data);p=p->pNext;}printf("\n");}voidDeleteStack(StackTop)//釋放棧空間{Stackp,q;p=Top->pNext;while(p!=NULL){q=p->pNext;free(p);p=q;}Top->pNext=NULL;}實驗結果：生成棧①初始化棧。②生成棧成功。2〕Push輸入push，進行入棧操作，得到新の棧序列。3〕Pop①輸入pop，進行出棧操作，彈出棧頂元素9,並且得到新の棧序列。②如果不斷進行pop操作，當棧為空時會出現pop失敗。4)其餘操作①結束進程輸入指令end可以結束進程，不會出現要求輸入下一步指令。②輸入錯誤の指令假设在指令輸出端輸入錯誤指令，則要求重新輸入指令直到輸入正確指令2.隊列〔循環數組實現〕實驗源程序：#include"stdafx.h"#include"stdio.h"#include"stdlib.h"#include"malloc.h"#include"string.h"#definemaxsize11typedefstructpQueue{intqueue[maxsize];intrear;//最後元素の位置intfront;//最前元素の位置の前一個位置}Aqueue,*Queue;QueueQueueInit();//初始化隊列voidCreateQueue(QueueQ,intn);//生成隊列intIsFull(QueueQ);//判斷隊列是否為滿intIsEmpty(QueueQ);//判斷隊列是否為空intEnQueue(QueueQ,intx);//入隊intDeQueue(QueueQ);//出隊voidTraverseQueue(QueueQ);//遍曆隊列intmain()//主函數{intn,x;charstr[10];QueueQ=QueueInit();//初始化隊列printf("請輸入想要入隊元素個數(小於%d):",maxsize);while(1){scanf("%d",&n);if(n<maxsize)break;printf("請重新輸入想要入隊元素個數(小於%d):",maxsize);}CreateQueue(Q,n);//生成隊列printf("隊列中の元素依次為:");TraverseQueue(Q);printf("請輸入下一步操作指令(Enqueue,Dequeueorend):");while(1){scanf("%s",str);//獲取操作指令if(strcmp(str,"Enqueue")==0){printf("請輸入想要入隊の元素:");scanf("%d",&x);if(EnQueue(Q,x))//入隊{printf("元素%d入隊後隊列中元素依次為:",x);TraverseQueue(Q);}printf("請輸入下一步操作指令(Enqueue,Dequeueorend):");}if(strcmp(str,"Dequeue")==0){if(IsEmpty(Q)==0){printf("元素%d出隊後隊列中元素依次為:",DeQueue(Q));//出隊TraverseQueue(Q);printf("請輸入下一步操作指令(Enqueue,Dequeueorend):");}else{printf("隊列為空,出隊失敗\n");printf("請輸入下一步操作指令(Enqueue,Dequeueorend):");}}if(strcmp(str,"end")==0)break;//跳出循環if(strcmp(str,"Enqueue")!=0&&strcmp(str,"Dequeue")!=0&&strcmp(str,"end")!=0){printf("輸入指令錯誤，請重新輸入指令:");}}printf("判斷隊列是否為空:",x);//判斷隊列是否為空if(IsEmpty(Q)==1)printf("隊列為空\n");elseprintf("隊列不為空\n");return0;}QueueQueueInit()//初始化隊列{QueueQ=(Queue)malloc(sizeof(Aqueue));if(Q!=NULL){Q->rear=-1;Q->front=-1;printf("初始化隊列成功\n");returnQ;}exit(1);}voidCreateQueue(QueueQ,intn)//生成隊列{for(inti=0;i<n;i++){printf("請輸入隊列中第%d個元素:",i+1);Q->rear=Q->rear+1;scanf("%d",&Q->queue[Q->rear]);}printf("生成隊列成功\n");}intIsFull(QueueQ)//判斷隊列是否為滿{if(Q->front==-1)Q->front=maxsize-1;return(Q->rear+1)%maxsize==Q->front;}intIsEmpty(QueueQ)//判斷隊列是否為空{returnQ->front==Q->rear;}intEnQueue(QueueQ,intx)//入隊{if(IsFull(Q)){printf("隊列已滿,入隊失敗\n");return0;}Q->rear=(Q->rear+1)%maxsize;Q->queue[Q->rear]=x;retu