《數(shù)據(jù)結(jié)構(gòu)》實驗二

1、華北水利水電大學(xué)數(shù)據(jù)結(jié)構(gòu)實驗報告20152016學(xué)年 第一學(xué)期 2013級 計算機(jī)科學(xué)與技術(shù)專業(yè)班級：2013156學(xué)號：20135607姓名：馮浩亮實驗二棧和隊列及其應(yīng)用實驗題目:棧和隊列及其應(yīng)用實驗內(nèi)容:1 病人看病模擬程序編寫一個程序，反映病人到醫(yī)院看病，排隊看醫(yī)生的情況。在病人排隊過程中，主要重復(fù)兩件事:(1) 病人到達(dá)診室，將病歷本交給護(hù)士，排到等待隊列中候診。(2) 護(hù)士從等待隊列中取出一位病人的病歷，該病人進(jìn)入診室就診。要求采用帶頭結(jié)點的單鏈表作為隊列，模擬病人等待就診這一過程。程序采用菜單方式，其選項及 功能說明如下：(1) 排隊一一輸入排隊病人的病歷號，加入到病人排隊隊列中。

2、(2) 就診一一病人排隊隊列中最前面的病人就診，并將其從隊列中刪除。(3) 查看隊列一一從隊首到隊尾輸出所有病人的病歷號。(4) 不再排隊，余下依次就診一一從隊首到隊尾列出所有的排隊病人的病歷號，并退出運(yùn)行。(5) 下班一一退出運(yùn)行。2. 停車場管理設(shè)停車場是一個可停放 n輛車的狹長通道，且只有一個大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時間的先后順序，依次由北向南排列(大門在最南端，最先到達(dá)的第一輛車停放在車場的最北段)，若停車廠內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一 輛車跡可開入；停車場內(nèi)某輛車要離開時，在它之后進(jìn)入的車連必須先退出車廠為它

3、讓路，待該車輛開出 大門外，其他車輛再按原次序進(jìn)入車場，每輛停放在車場的車在它離開停車時必須按它停留的時間長短繳 納費用。編寫按上述要求進(jìn)行管理的模擬程序?？梢詫⑼＼噲龆x成一個順序棧s0,便道定義成一個鏈隊列 q,而停車場中的某輛車要離開，則在它后面進(jìn)停車場的車必須讓道，讓其離開，所以必須有一個臨時的順序棧si，存放讓道的車輛。當(dāng)有車輛進(jìn)停車場時，若棧s0不滿，則直接進(jìn)入棧 S0;若棧s0滿，則進(jìn)入便道(鏈隊列q)。若有S0中車輛x離開時，先讓在 x后面進(jìn)棧的車從s0退棧并進(jìn)入棧si中，讓x離開并收取停車費(在便道上 停留的時間不收費)，然后再把si中所有元素退棧并重新進(jìn)入s0棧，最后，將鏈

4、隊列q中的隊頭元素出隊并進(jìn)棧到s0中。三、實驗要求:1. 使用C語言完成算法設(shè)計和程序設(shè)計并上機(jī)調(diào)試通過。2. 撰寫實驗報告，提供實驗結(jié)果和數(shù)據(jù)。3. 寫出算法設(shè)計小結(jié)和心得。四、程序源代碼:1. #include <stdio.h> #include <malloc.h> typedef int QElemType;typedef struct nodeQElemType data; struct node *next; Qnode,*QueuePtr; typedef structQnode *front; Qnode *rear; LinkQueue;void m

5、enu() / 菜單函數(shù) printf("n");printf("計科 156 班 201315607n");printf("n");printf("*病人看病模擬程序 *n");printf("1.排隊 n");printf("2.就診 n");printf("3.查看隊列n");printf("4.不在排隊n");printf("5.下班 n");printf("*n");printf(&qu

6、ot;n");void InitQueue(LinkQueue &Q)/ 構(gòu)造一個空隊列 Q Q.front=Q.rear=(Qnode*)malloc(sizeof(Qnode); Q.front->next=NULL;void DestroyQueue(LinkQueue &Q)/ 銷毀隊列 Qwhile(Q.front)Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;void EnQueue(LinkQueue &Q,QElemType e)/插入隊尾元素e為Q的新的隊尾元素int i=1;

7、Qnode *a = (Qnode *)malloc(sizeof(Qnode); a->data=e;a->next=NULL;Q.rear->next=a;Q.rear=a;printf(”您排在第：%d號 n",i+);void DeQueue(LinkQueue &Q)/ 就診，并且刪除頭結(jié)點if(Q.front=Q.rear) return ;/判斷Qnode *p = (Qnode *)malloc(sizeof(Qnode);p=Q.front->next;printf(" 就診患者病歷號： %d",p->dat

8、a);Q.front->next=p->next;if(Q.rear=p) Q.rear=Q.front;free(p); printf("n");void prin(LinkQueue Q)/ 查看就診隊列，即輸出現(xiàn)有隊列QueuePtr p;p=Q.front->next;printf(" 現(xiàn)有排隊患者 :");while(p!=NULL)printf("%d ",p->data);p=p->next;printf("n");main()int Cz,e;LinkQueue Q;I

9、nitQueue(Q);menu();while(Cz)printf("t 【輸入操作】 ： ");scanf("%d",&Cz);switch(Cz)case(1):printf(" 輸入病歷號 :"); scanf("%d",&e); EnQueue(Q,e);break;case(2):DeQueue(Q);break;case(3):prin(Q);break;case(4):prin(Q);DestroyQueue(Q);Cz=0;break; case(5):Cz=0;break;if(

10、Cz=0) printf("ntt 謝謝使用 !n");return 0;2. #include <stdio.h>#include <stdlib.h> #include <string.h>#include <time.h>#define max 3 #define price 1 int b=1; typedef struct int day;時間結(jié)點int hour; int min;車牌號 進(jìn)入停車場的時間 進(jìn)入停車場的位置TIME; / typedef struct char num10; / TIME time;

11、 / int n; / information;/ 棧結(jié)構(gòu)體定義 typedef struct node information data;struct node *next;stacknode; stacknode *top1,*top2;/ 隊列結(jié)構(gòu)體定義 typedef structinformation data; stacknode *front,*rear;LQueue;LQueue *Q;/ 初 始 化 車 輛 進(jìn)入停車費用計算函數(shù)車輛駛出出場函數(shù)初始化隊列函數(shù)車輛進(jìn)入候車便道函數(shù)判斷候車便道有無等待車候車區(qū)車輛出隊從候車便道進(jìn)入停車場函顯示停車場所有信息函數(shù)int i;prin

12、tf("ttt* * printf("tttt printf("ttt| printf("ttt| printf("ttt| printf("ttt| printf("ttt| printf("ttt*n");停車場管理系統(tǒng) n"); 車輛進(jìn)入停車場 車輛離開停車場 顯示停車場內(nèi)所有車輛信息 顯示候車區(qū)內(nèi)所有車輛信息 退出 |n");*n");1.2.3.4.5.|n");|n");|n");|n");while(i!=5)printf

13、("t 請輸入選項 1-5:"); scanf("%d",&i);switch(i)case 1:stacknode *Init();/ 棧的初始化stacknode *into(stacknode *top1,LQueue *Q);int expenses(stacknode *p,int x,int y); / stacknode *leave(stacknode *top1,char str,LQueue *Q);/LQueue *InitLQue(); / LQueue *wait(LQueue *q,stacknode *s);/int

14、 EmptyLQue(LQueue *q);/輛函數(shù)stacknode *out(LQueue *q);/stacknode *LQinto(stacknode *p,stacknode *top1);/數(shù)void show(stacknode *top1); / void T_shou(LQueue *Q); / 顯示候車區(qū)信息 /* 函數(shù)部分 */ 主函數(shù)void main()char str10; Q=InitLQue();top1=Init();top2=Init(); Q=InitLQue();top1=into(top1,Q);break;case 2:printf("

15、請輸入離開車輛的車牌號： "); scanf("%s",str);top1=leave(top1,str,Q);break;case 3:show(top1);break;case 4:T_shou(Q);break;case 5:exit(1);default:printf(" 輸入錯誤，請重新輸入 1 5:"); break;/* 子函數(shù) */ 初始化stacknode *Init()stacknode *top;top=(stacknode *)malloc(sizeof(stacknode);top=NULL;return top;/

16、初始化車輛進(jìn)入stacknode *into(stacknode *top1,LQueue *Q)stacknode *p,*q;time_t rawtime; / 調(diào)用系統(tǒng)時間函數(shù)struct tm *timeinfo; /時間結(jié)點time(&rawtime);timeinfo=localtime(&rawtime);p=(stacknode *)malloc(sizeof(stacknode); if(p=NULL)printf(" 內(nèi)存分配失敗 ");return top1;printf(" 請輸入進(jìn)入停車場車輛的車牌號 :");s

17、canf("%s",p->data.num);q=top1;while(q!=NULL)if(strcmp(p->data.num,q->data.num)=0) printf(" 車牌號輸入有誤，該車已進(jìn)入 !");return top1;q=q->next;p->data.time.day=timeinfo->tm_mday;p->data.time.hour=timeinfo->tm_hour;p->data.time.min=timeinfo->tm_min;p->data.n=b

18、;if(b>max)printf(" 停車場已滿 , 請在便道等候 !n");wait(Q,p);return top1;if(top1=NULL)p->next=NULL;top1=p;elsep->next=top1;top1=p;b+;printf(" 車輛進(jìn)入停車場成功，時間已經(jīng)自動載入 !n");printf(" 車 牌 為 %s 的 汽 車 駛 入 時 間 為 :%d 號 %d 點 %d n",top1->data.num,top1->data.time.day,top1->data.t

19、ime.hour,top1->data.time.min);return top1;/ 停車費用計算函數(shù)int expenses(stacknode *p,int x1,int x2,int x3)int w;if(x3!=0)w=(x1*24+x2+1-(p->data.time.day*24+p->data.time.hour)*price;elsew=(x1*24+x2-(p->data.time.day*24+p->data.time.hour)*price;return w;/ 車輛駛出出場函數(shù)stacknode *leave(stacknode *to

20、p1,char str,LQueue *Q)int i,day,hour,min; time_t rawtime; struct tm *timeinfo; time(&rawtime); timeinfo=localtime(&rawtime); day=timeinfo->tm_mday; hour=timeinfo->tm_hour; min=timeinfo->tm_min; stacknode *p,*q;if(top1=NULL)printf(" 停車場沒有車輛 !n");return top1;q=(stacknode *)m

21、alloc(sizeof(stacknode); if(p=NULL)printf(" 內(nèi)存分配失敗 ");return top1;q=top1; while(q!=NULL) if(strcmp(q->data.num,str)=0) break;q=q->next;if(q=NULL)!n");printf(" 輸入有誤，該車輛不在停車場 return top1;for(i=top1->data.n;i>q->data.n;i-)p=(stacknode *)malloc(sizeof(stacknode); if(p=

22、NULL)printf(" 內(nèi)存分配失敗 ");return top1; strcpy(p->data.num,top1->data.num); p->data.time=top1->data.time; p->data.n=top1->data.n-1;top1=top1->next;if(top2=NULL)p->next=NULL;top2=p;elsep->next=top2;top2=p;top1=top1->next;while(top2!=NULL)p=(stacknode *)malloc(size

23、of(stacknode);if(p=NULL)printf(" 內(nèi)存分配失敗 ");return top1;p->data.n=top2->data.n;strcpy(p->data.num,top2->data.num);p->data.time=top2->data.time;p->next=top1;top1=p;top2=top2->next;if(EmptyLQue(Q)p=out(Q);p->data.n-;top1=LQinto(p,top1);elseb-;printf(”車牌為 s的汽車駛出時間為：d

24、 號4點4分門”,q->data.num,day,hour,min);printf(”車輛駛出停車場需要繳納的費用為:%d元n”,expenses(q,day,hour,min);return top1;/ 隊列函數(shù)初始化LQueue *InitLQue()LQueue *Q;stacknode *p;Q=(LQueue *)malloc(sizeof(LQueue);p=(stacknode *)malloc(sizeof(stacknode);p->next=NULL;Q->front=Q->rear=p;return Q;/ 候車區(qū)隊列入隊LQueue *wait

25、(LQueue *q,stacknode *s) s->next=NULL; q->rear->next=s; q->rear=s;return q;/ 判斷候車便道有無車輛等待int EmptyLQue(LQueue *q)if(q->front=q->rear)return 0;elsereturn 1;/ 候車區(qū)車輛出隊stacknode *out(LQueue *q)stacknode *p;p=q->front->next; if(q->front->next=q->rear)q->rear=q->fron

26、t;return p;else q->front->next=p->next; p->next=NULL;return p;/ 候車隊列進(jìn)入停車場stacknode *LQinto(stacknode *p,stacknode *top1) p->next=top1;top1=p;return top1;/ 顯示停車場內(nèi)所有車輛信息void show(stacknode *top1)printf(" 停車場內(nèi)全部車輛信息表 n"); if(top1=NULL)printf(" 停車場內(nèi)無車 !n");elseprintf(" 車牌號 進(jìn)入時間 位置 n");while(top1!=NULL)printf(" %s %d 號 %d 點 %d 分 第 %d 位 n",top1->data.num,top1->data.time.day,top1->data.time.hour,top1->data.time.min,top1->data.n);top1=top1->next;/ 顯示候車區(qū)的汽車信息void T_sho