數(shù)據(jù)結構實驗二

PAGE第1頁共9頁華北水利水電學院數(shù)據(jù)結構實驗報告2011～2012學年第二學期2011級計算機專業(yè)班級：2011179學號：201117914姓名：劉珍實驗二棧和隊列及其應用實驗目的：1．掌握棧的特點(先進后出FILO)及基本操作，如入棧、出棧等，棧的順序存儲結構和鏈式存儲結構，以便在實際問題背景下靈活應用。2．掌握隊列的特點(先進先出FIFO)及基本操作，如入隊、出隊等，隊列順序存儲結構、鏈式存儲結構和循環(huán)隊列的實現(xiàn)，以便在實際問題背景下靈活運用。實驗內(nèi)容：1．鏈棧的建立、入棧、出棧操作。2．環(huán)形隊列的建立、入隊、出隊操作。3．停車場管理。設停車場內(nèi)只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內(nèi)按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內(nèi)某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。實現(xiàn)提示：以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，對每一組輸入數(shù)據(jù)進行操作后的輸出數(shù)據(jù)為：若是車輛到達，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時間和應交納的費用（在便道上停留的時間不收費）。棧以順序結構實現(xiàn)，隊列以鏈表（帶頭結點）實現(xiàn)。需另設一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結構實現(xiàn)。輸入數(shù)據(jù)按到達或離去的時刻有序。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項：汽車的牌照號碼和進入停車場的時刻。設n=2,輸入數(shù)據(jù)為：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，其中，‘A’表示到達；‘D’表示離去，‘E’表示輸入結束。實驗要求：C/C++完成算法設計和程序設計并上機調(diào)試通過。撰寫實驗報告，提供實驗結果和數(shù)據(jù)。寫出算法設計小結和心得。程序源代碼：1，2放在一快寫：#include<stdio.h>#include<malloc.h>#defineOK1#defineERROR0#defineOVERFLOW-2typedefintelemtype;typedefintstatus;typedefstructQNode{elemtypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;typedefstructlnode{elemtypedata;structlnode*next;}stacknode,*linkstack;statusinitstack(linkstacktop){top->next=NULL;}statusisempty(linkstacktop){if(top->next==NULL)returnOK;returnERROR;}statuspush(linkstacktop,elemtypee){stacknode*p;p=(stacknode*)malloc(sizeof(stacknode));if(p==NULL)returnERROR;p->data=e;p->next=top->next;top->next=p;returnOK;}statuspop(linkstacktop,elemtype*e){if(isempty(top))returnERROR;stacknode*p=top->next;*e=p->data;top->next=p->next;free(p);returnOK;}statusshstack(linkstacktop){ stacknode*p; p=(stacknode*)malloc(sizeof(stacknode)); p->next=top->next; while(p->next!=NULL){ printf("%d",p->next->data); p->next=p->next->next; } returnOK;}statusinitqueue(LinkQueue*q){ (*q).front=(*q).rear=(QueuePtr)malloc(sizeof(QNode)); if(!(*q).front)exit(OVERFLOW); (*q).front->next=NULL; returnOK;}statusenqueue(LinkQueue*q,elemtypee){ QueuePtrp=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW); p->data=e; p->next=NULL; (*q).rear->next=p; (*q).rear=p; returnOK;}statusdequeue(LinkQueue*q,elemtype*e){ if((*q).front==(*q).rear)returnERROR; QueuePtrp; p=(*q).front->next; *e=p->data;//注意 (*q).front->next=p->next; if((*q).rear==p)(*q).rear==(*q).front; free(p); returnOK;}voidmain(){ linkstacks; s=(linkstack)malloc(sizeof(stacknode)); initstack(s); printf("進入棧的4個元素依次為：\n"); for(inti=0;i<4;i++) { elemtypea; scanf("%d",&a); push(s,a); } printf("\n棧頂?shù)綏５椎脑匾来螢?；\n"); shstack(s); elemtypeb,c,d; pop(s,&b); pop(s,&c); pop(s,&d); push(s,b); printf("\n\n出棧的元素為:"); printf("%d",c); printf("%d\n",d); printf("\n現(xiàn)在棧中的元素為："); shstack(s); LinkQueueq; initqueue(&q); elemtypea; printf("\n\n\n請輸入5個進隊的元素:\n"); for(inti=0;i<5;i++) {scanf("%d",&a);enqueue(&q,a); } printf("\n元素的出列為:\n"); for(inti=0;i<5;i++) { elemtypee; dequeue(&q,&e); printf("%d",e); }}3中代碼：#include"iostream.h"intN;constintM=5;//M為單元時間的收費值structcinfo//定義棧中元素的類型{intcnum;intatime;};structstack//定義棧{cinfocstack[3000];//這里隨便定義一個數(shù)字表示數(shù)組的長度,因為后inttop;//面會根據(jù)用戶輸入的N值作為停車場能夠停車的intsize;//數(shù)量.};structnode//定義隊列節(jié)點的類型{node*next;intnnum;};structqueue//定義隊列{node*front,*rear;};voidinitstack(stack*s)//初始化棧{s->top=-1;}intinstack(stack*s,cinfox)//元素進棧{//int元素進棧n;if(s->top==N-1){cout<<"Stackisfull!"<<endl;return0;}else{s->cstack[++s->top]=x;return1;}}cinfooutstack(stack*s)//元素出棧{cinfoy;if(s->top<0){um=NULL;y.atime=NULL;returny;}else{s->top--;returns->cstack[s->top+1];}}voidinitqueue(queue*q)//初始化隊列{q->front=newnode;q->rear=q->front;q->front->next=NULL;q->front->nnum=0;}voidinqueue(queue*q,intnum1)//元素進隊列{node*p;p=newnode;p->nnum=num1;p->next=NULL;q->rear->next=p;q->rear=p;q->front->nnum++;}intoutqueue(queue*q)//元素出隊列{node*p;intn;if(q->front==q->rear)return0;else{p=q->front->next;q->front->next=p->next;if(p->next==NULL)q->rear=q->front;n=p->nnum;deletep;q->front->nnum--;returnn;}}voidcarrival(stack*s,queue*q,cinfox)//處理車輛到達的情況{intf;f=instack(s,x);if(f==0){inqueue(q,um);cout<<"TheNumber"<<um<<""<<"carparkintothepos"<<q->front->nnum<<""<<"oftheroad."<<endl;}else{cout<<"TheNumber"<<um<<""<<"carparkintothepos"<<s->top+1<<""<<"oftheroom."<<endl;}}voidcarleave(stack*s1,stack*s2,queue*q,cinfox)//處理車輛離開{node*p;cinfoy;inta,n=0;while((s1->top>-1)&&(n==0)){y=outstack(s1);if(um!=um){a=instack(s2,y);}elsen=1;}if(um==um){cout<<"Thenumber"<<um<<""<<"carwanttoleave,thechargeis"<<""<<(x.atime-y.atime)*M<<""<<"yuan!"<<endl;while(s2->top>-1){y=outstack(s2);n=instack(s1,y);}a=outqueue(q);if(a!=0){um=a;y.atime=x.atime;n=instack(s1,y);cout<<"TheNumber"<<um<<""<<"carparkintothepos"<<s1->top+1<<""<<"oftheroom."<<endl;}}else{while(s2->top>-1){y=outstack(s2);n=instack(s1,y);}p=q->front;n=0;while(p->next!=NULL&&n==0){if(p->next->nnum!=um)p=p->next;else{p->next=p->next->next;q->front->nnum--;if(p->next=NULL)q->rear=q->front;cout<<"Thenumber"<<um<<""<<"wanttoleavefromtheroad."<<endl;n=1;}}if(n==0){cout<<"Youhaveenteredawrongnumber!"<<endl;}}}voidmain()//主程序{//intmaxsize;cout<<"Start，WrittenbyZIGZ"<<endl<<endl<<endl;cout<<"PleaseenteranumberasthemaxsizeoftheroomStack:"<<endl;cin>>N;//這里N將作為棧能存放元素的數(shù)量while(N<=0){cout<<"Oh!Youhaveenterawrongnumber,'N'shouldabove0.Pleaseenteranothernumberagain:"<<endl;cin>>N;}//stack*max;//max->size=maxsize;charch1;stack*s1,*s2;queue*q;cinfox;intflag;s1=new