山東大學(xué)數(shù)據(jù)結(jié)構(gòu)第二次實(shí)驗(yàn)實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn)2 ADT棧與隊(duì)列的編程與實(shí)現(xiàn)實(shí)驗(yàn)?zāi)康模杭由顚?duì)抽象數(shù)據(jù)類型ADT棧和隊(duì)列的理解；實(shí)驗(yàn)原理：參照課本p. 64-66，及Figure3.39-3.44；課本 p. 82-83，及 Figure3.57-3.60.實(shí)驗(yàn)內(nèi)容：編寫程序?qū)崿F(xiàn)ADT棧的定義，及常用操作(數(shù)組或指針實(shí)現(xiàn)):生成棧；PushPop編寫程序?qū)崿F(xiàn)ADT隊(duì)列的定義，及常用操作：生成隊(duì)列；Enqueues 入列；Isempty判斷是否隊(duì)列為空。實(shí)驗(yàn)要求：實(shí)現(xiàn)ADT棧的結(jié)構(gòu)及操作；實(shí)現(xiàn)ADT隊(duì)列的結(jié)構(gòu)及操作，并給出應(yīng)用。1.棧(鏈表實(shí)現(xiàn)) 實(shí)驗(yà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;定義一個(gè)棧的結(jié)構(gòu)/pNext為指向棧中下一個(gè)空間的指針初始化棧生成棧判斷棧是否為空進(jìn)行壓棧操作進(jìn)行出棧操作遍歷棧的函數(shù)清空棧的函數(shù)主函數(shù)定義數(shù)組，存儲(chǔ)操作指令初始化Top為NULLTop=InitStack();初始化棧CreateStack(Top);生成棧TraverseStack(Top);遍歷棧printf(請(qǐng)輸入下一步操作指令(push,pop or end):);while(1)scanf(%s”,str);獲取操作指令if(strcmp(str,push)=0)printf(請(qǐng)輸入入棧的元素:)；

4、scanf(%d”,&n);Push(Top,n);進(jìn)棧操作TraverseStack(Top);printf(請(qǐng)輸入下一步操作指令(push,pop or end):);if(strcmp(str,pop)=0)Pop(Top);出棧操作TraverseStack(Top);printf(請(qǐng)輸入下一步操作指令(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(輸入指令錯(cuò)誤，請(qǐng)重新輸入指令:)；DeleteSt

5、ack(Top);釋放?？臻greturn 0;Stack InitStack()進(jìn)行棧的初始化的函數(shù)Stack Top = (Stack)malloc(sizeof(Node); / 分配內(nèi)存空間給棧頂 if(Top=NULL) printf(動(dòng)態(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(請(qǐng)輸入想要入棧的元素個(gè)數(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(未能動(dòng)態(tài)分配內(nèi)存，進(jìn)棧失敗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讓新分配空間的單元成為棧底/判斷棧是否為空進(jìn)行進(jìn)棧操作的函數(shù)定義一個(gè)新節(jié)點(diǎn)，并分配內(nèi)存空間進(jìn)行出棧操作函數(shù)判斷棧是否為空，為空就不能進(jìn)行出棧操作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;實(shí)驗(yàn)結(jié)果

9、:1）生成棧初始化棧。初始化犢成功生成棧成功。成gr 攵入A.i; win3 sss ITITrlIT. 數(shù)到到到 1 n12233423 34舊的一 分-璟|戶丁目Wpup UI tLLU/ .2) Push輸入push，進(jìn)行入棧操作，得到新的棧序列。kAfflUr1 L.122334!，底底底 .J戔毛黃 -IJIJIT- 教slsllgll 8am I |-】目-yl-,-L 口gPop輸入pop,進(jìn)行出棧操作，彈出棧頂元素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 一費(fèi)一費(fèi)一費(fèi)石列一： 定定震序2京

11、下暨下暨下暨下4-E摩下， AAIAA ?空 n4）其余操作結(jié)束進(jìn)程輸入指令end可以結(jié)束進(jìn)程，不會(huì)出現(xiàn)要求輸入下一步指令。請(qǐng)輸入下一步操作指令Cpush. pop or end : end Press =iiiy key to continue輸入錯(cuò)誤的指令若在指令輸出端輸入錯(cuò)誤指令，則要求重新輸入指令直到輸入正確指令機(jī)置與_LLABMAA操止宅篦屁， -lyrl-r&d |-白II b p_ ystart2.隊(duì)列(循環(huán)數(shù)組實(shí)現(xiàn))實(shí)驗(yà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();最后元素的位置最前元素的位置的前一個(gè)位置初始化隊(duì)列生成隊(duì)列判斷隊(duì)列是否為滿判斷隊(duì)列是否為空/入隊(duì)出隊(duì)遍歷隊(duì)列/主函數(shù)初始化隊(duì)列printf(請(qǐng)輸入想要入隊(duì)元素個(gè)數(shù)(小于d):,maxsize);while(1)scanf(%d”,&n);if(nrear=-1;Q-front=-1;printf(初始化隊(duì)列成功n);return Q;exit(1);void CreateQueue(Queue Q,int n)生成隊(duì)列for(int i=0;irear=Q-rear+1;scanf(%d”,&Q-queueQ-rear);printf(生成隊(duì)列成功n);int IsF

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

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

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

17、斷是否隊(duì)列為空。隊(duì)列不為空。ZZ 33 44 55 tj- i-EnqueiiH. IImiumuhX*A出青青青青青口Ira口 口Iffl功-，列要見(jiàn)51 I5IJ機(jī)列成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 &隊(duì)列是杏為空:隊(duì)列不為空*LL|_UPAJpl 11 - | | _- r - - - - - - - - -、作指令Enqmia Dmqumue or end): end 空:隊(duì)列為空青青青8

18、?個(gè)元一蔑五X儀隊(duì)要器弟TI 于1511):1111):10隊(duì)列為空i踽姿ll 1. =_=. i -3_Li.y J-. e y COu e4）其他操作若輸入的元素個(gè)數(shù)超過(guò)數(shù)組能接受長(zhǎng)度，需重新輸入。隊(duì)列為滿時(shí)，入隊(duì)失敗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?出隊(duì)操作。-7123 匾定定弟- -要刊列JJ1 2 3 .rll-l/- Z- - I測(cè)京大為c(.Ehqucu e.