山東大學數(shù)據(jù)結(jié)構(gòu)第二次實驗實驗報告

1、實驗2 ADT棧與隊列的編程與實現(xiàn)實驗目的：加深對抽象數(shù)據(jù)類型ADT棧和隊列的理解；實驗原理：參照課本p. 64-66，及Figure3.39-3.44；課本 p. 82-83，及 Figure3.57-3.60.實驗內(nèi)容：編寫程序?qū)崿F(xiàn)ADT棧的定義，及常用操作(數(shù)組或指針實現(xiàn)):生成棧；PushPop編寫程序?qū)崿F(xiàn)ADT隊列的定義，及常用操作：生成隊列；Enqueues 入列；Isempty判斷是否隊列為空。實驗要求：實現(xiàn)ADT棧的結(jié)構(gòu)及操作；實現(xiàn)ADT隊列的結(jié)構(gòu)及操作，并給出應(yīng)用。1.棧(鏈表實現(xiàn)) 實驗源程序：#include stdafx.h#include stdio.h#includ

2、e stdlib.h#include malloc.h#include string.h typedef struct node int data;struct node *pNext;Node,*pNode;typedef pNode Stack;Stack InitStack();void CreateStack(Stack Top);bool Empty(Stack Top);void Push(Stack Top,int n);void Pop(Stack Top);void TraverseStack(Stack Top); void DeleteStack(Stack Top);

3、int main() int n;char str6;Stack Top=NULL;定義一個棧的結(jié)構(gòu)/pNext為指向棧中下一個空間的指針初始化棧生成棧判斷棧是否為空進行壓棧操作進行出棧操作遍歷棧的函數(shù)清空棧的函數(shù)主函數(shù)定義數(shù)組，存儲操作指令初始化Top為NULLTop=InitStack();初始化棧CreateStack(Top);生成棧TraverseStack(Top);遍歷棧printf(請輸入下一步操作指令(push,pop or end):);while(1)scanf(%s”,str);獲取操作指令if(strcmp(str,push)=0)printf(請輸入入棧的元素:)；

4、scanf(%d”,&n);Push(Top,n);進棧操作TraverseStack(Top);printf(請輸入下一步操作指令(push,pop or end):);if(strcmp(str,pop)=0)Pop(Top);出棧操作TraverseStack(Top);printf(請輸入下一步操作指令(push,pop or end):);if(strcmp(str,end)=0)break;跳出循環(huán)if(strcmp(str,push)!=0&strcmp(str,pop)!=0&strcmp(str,end)!=0)printf(輸入指令錯誤，請重新輸入指令:)；DeleteSt

5、ack(Top);釋放?？臻greturn 0;Stack InitStack()進行棧的初始化的函數(shù)Stack Top = (Stack)malloc(sizeof(Node); / 分配內(nèi)存空間給棧頂 if(Top=NULL) printf(動態(tài)分配內(nèi)存失敗n);exit(1);棧頂指針的指向置為NULL；printf(初始化棧成功n);Top-pNext = NULL; return Top;/生成棧void CreateStack(Stack Top) int LEN,x;Stack Bottom = Top;/令 Top 和 Bottom 指向同一空間Bottom-pNext = NU

6、LL;printf(請輸入想要入棧的元素個數(shù):)；scanf(%d”,&LEN);for(int i = 0; i data = x;Bottom-pNext = pNew;pNew-pNext = NULL;Bottom = pNew;printf(生成棧成功n);bool IsEmpty(Stack Top)return Top-pNext=NULL;void Push(Stack Top,int n)Stack pNew = (Stack)malloc(sizeof(Node);if(pNew=NULL)printf(未能動態(tài)分配內(nèi)存，進棧失敗n);return ;pNew-data =

7、 n;pNew-pNext = Top-pNext;Top-pNext = pNew;void Pop(Stack Top)Stack p=Top-pNext;if (IsEmpty(Top)=true)將輸入的數(shù)放在棧data單元中/Bottom指向新分配空間的單元/令 pNew 指向 NULL讓新分配空間的單元成為棧底/判斷棧是否為空進行進棧操作的函數(shù)定義一個新節(jié)點，并分配內(nèi)存空間進行出棧操作函數(shù)判斷棧是否為空，為空就不能進行出棧操作printf(棧為空，Pop 失敗n);return ;elseprintf(-彈出的棧頂元素為:)；printf(%d n,p-data);顯示出棧元素To

8、p-pNext=p-pNext;free(p);void TraverseStack(Stack Top)遍歷棧，獲取棧中的數(shù)值printf(-現(xiàn)在棧中的元素從棧頂?shù)綏５滓来螢?)；Stack p = Top-pNext;if(p=NULL)printf(棧空，while(p!=NULL)printf(%d ”,p-data);p = p-pNext;printf(n);void DeleteStack(Stack Top)釋放棧空間Stack p,q ;p=Top-pNext;while (p != NULL)q=p-pNext;free(p);p=q;Top-pNext=NULL;實驗結(jié)果

9、:1）生成棧初始化棧。初始化犢成功生成棧成功。成gr 攵入A.i; win3 sss ITITrlIT. 數(shù)到到到 1 n12233423 34舊的一 分-璟|戶丁目Wpup UI tLLU/ .2) Push輸入push，進行入棧操作，得到新的棧序列。kAfflUr1 L.122334!，底底底 .J戔毛黃 -IJIJIT- 教slsllgll 8am I |-】目-yl-,-L 口gPop輸入pop,進行出棧操作，彈出棧頂元素9,并且得到新的棧序列1叮中。！ Tri1223:3423 34(r end:底底底 3務(wù)戔務(wù)一 .，ITITJ-IIT 數(shù)到到到 ssI.I- . -IVTTT 煙

10、患杰擺序Kxr? AAA8XA麝9俑 為止P Op Llf tTLllj1 : pOp：923 34ikR-nijy v i :木 i l】口 /* 4，34 erLil)erLil)34 erLil)erLil)erLil):pUlh:P=P:P=P:P=P:poppush. pi：ip |：|I- HIId ) : p upUR-mU/ . I I riH -C、.上山 A 7 p L-p J UILLL.r .F9-Trr旨 _9 .-iT .2 3 41 2 3 .11 .111 .111 原底底Irf為止南*止#元為止#元為止#元為止差-為止之 J 一費一費一費石列一： 定定震序2京

11、下暨下暨下暨下4-E摩下， AAIAA ?空 n4）其余操作結(jié)束進程輸入指令end可以結(jié)束進程，不會出現(xiàn)要求輸入下一步指令。請輸入下一步操作指令Cpush. pop or end : end Press =iiiy key to continue輸入錯誤的指令若在指令輸出端輸入錯誤指令，則要求重新輸入指令直到輸入正確指令機置與_LLABMAA操止宅篦屁， -lyrl-r&d |-白II b p_ ystart2.隊列(循環(huán)數(shù)組實現(xiàn))實驗源程序：#include stdafx.h#include stdio.h#include stdlib.h#include malloc.h#include

12、string.h#define maxsize 11typedef struct pQueueint queuemaxsize;int rear;int front;Aqueue,*Queue;Queue QueueInit();void CreateQueue(Queue Q,int n);int IsFull(Queue Q);int IsEmpty(Queue Q);int EnQueue(Queue Q,int x);int DeQueue(Queue Q);void TraverseQueue(Queue Q);int main()int n,x;char str10;Queue Q

13、=QueueInit();最后元素的位置最前元素的位置的前一個位置初始化隊列生成隊列判斷隊列是否為滿判斷隊列是否為空/入隊出隊遍歷隊列/主函數(shù)初始化隊列printf(請輸入想要入隊元素個數(shù)(小于d):,maxsize);while(1)scanf(%d”,&n);if(nrear=-1;Q-front=-1;printf(初始化隊列成功n);return Q;exit(1);void CreateQueue(Queue Q,int n)生成隊列for(int i=0;irear=Q-rear+1;scanf(%d”,&Q-queueQ-rear);printf(生成隊列成功n);int IsF

14、ull(Queue Q)判斷隊列是否為滿if(Q-front=-1)Q-front=maxsize-1;return (Q-rear+1)%maxsize=Q-front;int IsEmpty(Queue Q)判斷隊列是否為空return Q-front=Q-rear;int EnQueue(Queue Q,int x)入隊if(IsFull(Q)printf(-隊列巳滿，入隊失敗n);return 0;Q-rear=(Q-rear+1)%maxsize;Q-queueQ-rear=x;return 1;int DeQueue(Queue Q)出隊Q-front=(Q-front+1)%ma

15、xsize;return Q-queueQ-front;獲取隊列中的數(shù)值void TraverseQueue(Queue Q)/遍歷隊列，if(IsEmpty(Q)=1)printf(隊列為空n);return;int front=Q-front;int rear=Q-rear;while (front!=rear)front=(front+1)%maxsize;printf(%d ”,Q-queuefront);printf(n);實驗結(jié)果如下：實驗結(jié)果：1）生成隊列；初始化隊列。遽岬勵，|舊1田7 -. -iIj-.J-l / W_i 出 I 5!.： rj 1 J 生成隊列成功。T小于方

16、 ii 22 33 44 55-712345mnag nft. 列要5IJ列5IJ5IJ 林PA隊PA饑青青青青青華工丁口 L范乙乙-1-1叱呸:-|：-.S1AF 一步 操作指專 En lue u % D e qu u e如 皿心:2) Enqueues 入列；操作指令輸入Enqueue，將66入列。素個數(shù)(小于11):11:22石11r青青青列要5IJ亂5IJ5II唄成一儕由為 11 ” 5 ddRR成偷元 ：66徹.啟|5板中無素依次為：11I歹垛 1F拍* n-q-ueue, ue22 33 queueor end）：Enqueue44 55 舶or ena/ .3) Isempty判

17、斷是否隊列為空。隊列不為空。ZZ 33 44 55 tj- i-EnqueiiH. IImiumuhX*A出青青青青青口Ira口 口Iffl功-，列要見51 I5IJ機列成i兀一壬-T-T.l 2 3 4 5cr endj : EiiiJUeiiP=素朗丁快后街卿八M,厄膈劃更云素依次為:L1 22 33 44 55 66 原孔下步操1?才s-（En叩mut . B只中姑口日;r嗎nd） ； end &隊列是杏為空:隊列不為空*LL|_UPAJpl 11 - | | _- r - - - - - - - - -、作指令Enqmia Dmqumue or end): end 空:隊列為空青青青8

18、?個元一蔑五X儀隊要器弟TI 于1511):1111):10隊列為空i踽姿ll 1. =_=. i -3_Li.y J-. e y COu e4）其他操作若輸入的元素個數(shù)超過數(shù)組能接受長度，需重新輸入。隊列為滿時，入隊失敗iTiqueiie . j_i & n u eue(小于11):9 11 22 33 44 EE 66 77 6S 99絲33 44 55能 ：nquene D e q_u eue 00匚*卻 4r i i：nquene D e q_u eue 10祈青青青青青青青青青77 S5 99ui- enl.) :Enqu eueui- enl.J : Enqu eueur erni?出隊操作。-7123 匾定定弟- -要刊列JJ1 2 3 .rll-l/- Z- - I測京大為c(.Ehqucu e.