數(shù)據(jù)結構實驗報告鏈表合并停車場問題

1、本科生實驗報告實驗課程數(shù)據(jù)結構與算法分析學院名稱管理科學學院專業(yè)名稱信息與計算科學學生姓名學生學號指導教師樂千榿實驗地點6C402實驗成績 二 一四 年 十 月 二 一四 年 十二月實驗一 鏈表合并1 實驗內(nèi)容(1) 創(chuàng)建鏈表并對其進行輸出；(2) 利用指針實現(xiàn)對兩個線形鏈表的合并，并輸出其結果。2 數(shù)據(jù)結構與算法描述1）變量及函數(shù)的定義變量/函數(shù)名類 型說 明void main ()主函數(shù)main（）實現(xiàn)初始化操作，完成對子函數(shù)的調(diào)用 Node*MergeSList子函數(shù)定義一個指針函數(shù)，返回值類型為NODE類型的一個指針Node*CreatList()子函數(shù)創(chuàng)建鏈表void outlin(

2、Node *h)子函數(shù)輸出鏈表的值2）程序流程圖開始輸入a調(diào)用create輸入Biaon>a調(diào)用create輸入b輸入Biaon>ba>bYN調(diào)用hebing (p1,p2,a,b)調(diào)用hebing(p2,p1,a,b)A&&B空輸出b結束調(diào)用print調(diào)用print3 實驗數(shù)據(jù)與實驗結果（可用文字描述或貼圖的方式進行說明）1）測試數(shù)據(jù)x1= 1 2 3 x2=2 3 5 7 2）實驗結果 圖1 鏈表合并的運行結果4 程序代碼清單#include<stdio.h>#include<malloc.h>typedef struct Node

3、 /定義一個Node的結構體int data;Node *next; /*next表示指向鏈表的后一個元素Node;Node *s,*p;Node *MergeSList(Node *head1,Node *head2)/定義一個指針函數(shù)，返回值類型為NODE類型的一個指針Node *p1=NULL;Node *p2=NULL;Node *pcur;Node *head=NULL;/用于保存Merge之后的鏈表；/head=NULL; if(head1->next->data<head2->next->data)/找到兩個鏈表的兩個第一個節(jié)點中更小的一個節(jié)點hea

4、d=head1;p1=head1->next;p2=head2->next;elsehead=head2;p1=head1->next;p2=head2->next;pcur=head;while(p1!=NULL&&p2!=NULL)/遍歷兩個鏈表并比較，把更小的值接在pcur后,pcur只是一個臨時鏈表 if(p1->data<p2->data) pcur->next=p1;pcur=p1;p1=p1->next; elseif(p1->data>p2->data)/pcur->next=p2;p

5、cur=p2;p2=p2->next;else if(p1->data=p2->data)/如果存在相同，則刪除節(jié)點p2=p2->next;/*循環(huán)之后，兩個鏈表要么為都為空，要么其中一個不為空，因為結束循環(huán)的條件有限制*/if(p1!=NULL)/把剩余的節(jié)點再接在pcur后pcur->next=p1;if(p2!=NULL)pcur->next=p2;return head;Node *CreatList()int x;Node *headcur;headcur=(Node*)malloc(sizeof(Node);p=headcur;printf(&q

6、uot;x=");scanf("%d",&x);while(x!=-999)/輸入-999代表結束輸入s=(Node*)malloc(sizeof(Node);s->data=x;s->next=NULL;p->next=s;p=s; /把s的地址賦給P的下一個，再把s的地址給pscanf("%d",&x);return headcur;void outlin(Node *h)/輸出鏈表的值 Node *p;p=h->next;printf("Merged :n");while(p!=

7、NULL)printf("%d ",p->data);p=p->next;printf("n");int main()Node *head1,*head2,*head;printf("input the value of single list1n"); head1=CreatList();printf("input the value of single list2n");head2=CreatList(); head=MergeSList(head1,head2);outlin(head);retu

8、rn 0;實驗二 進制轉(zhuǎn)換1 實驗內(nèi)容（1）利用堆棧實現(xiàn)對任意進制的數(shù)的轉(zhuǎn)換；（2）堆棧的應用及操作。2 數(shù)據(jù)結構與算法描述1）變量及函數(shù)的定義變量/函數(shù)名類 型說 明voidmain()conversion(N,M);主函數(shù)main（） 實現(xiàn)初始化操作，完成對子函數(shù)的調(diào)用 Status Push(SqStack *S,SElemTypee); 子函數(shù)壓棧Status Pop(SqStack *S,SElemType *e); 出棧Status StackEmpty(SqStack *S); Status InitStack(SqStack *S); 建立一個空棧2） 程序流程圖輸出棧及轉(zhuǎn)換結

9、果商為0？余數(shù)進棧（存入數(shù)組）轉(zhuǎn)換后的十進制取余輸入要轉(zhuǎn)換的進制類型輸出轉(zhuǎn)換結果先轉(zhuǎn)換成十進制數(shù)輸入要輸入數(shù)的進制及輸入要轉(zhuǎn)換的數(shù)開始3 實驗數(shù)據(jù)與實驗結果（可用文字描述或貼圖的方式進行說明）1）測試數(shù)據(jù)N=255，r=162）實驗結果 圖1 進制轉(zhuǎn)換的運行結果4 程序代碼清單（可直接將可運行源代碼粘貼在下面的方框中）#include<stdio.h>#include<string.h> #include<stdlib.h> #define STACKINITSIZE 100#define STACKINCREMENT 10#define OK1#defin

10、e ERROR0#define OVERFLOW -1#define YES 1#define NO 0typedef int Status;typedef int SElemType;typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;/- 基本操作的函數(shù)原型說明 -Status Push(SqStack *S,SElemType e); /壓棧Status Pop(SqStack *S,SElemType *e); /出棧Status StackEmpty(SqStack *S); Status In

11、itStack(SqStack *S); /建立一個空棧Status InitStack(SqStack *S)S->base = (SElemType*)malloc(STACKINITSIZE * sizeof(SElemType);if(!S->base)exit(OVERFLOW); /存儲分配失敗S->top = S->base;S->stacksize = STACKINITSIZE;return OK;/ InitStackStatus StackEmpty(SqStack *S)return S->base = S->top;Statu

12、s Push(SqStack *S,SElemType e)if(S->top - S->base >= S->stacksize) /棧滿追加空棧S->base=(SElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S->base)exit(OVERFLOW); /存儲分配失敗S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;*S->top+ =

13、e;return OK;/PushStatus Pop(SqStack *S,SElemType *e)if(S->top=S->base) return ERROR;*e=*-(S->top); return OK;/Popint main()int N,r,e; SqStack S;InitStack(&S); printf("please input N,r:n"); /N是要轉(zhuǎn)換的數(shù)，r是要轉(zhuǎn)換的幾進制scanf("%d%d",&N,&r);while(N)Push(&S,N%r);N=N/r;p

14、rintf("the arranged NO,is:");while(!StackEmpty(&S)Pop(&S, &e); if(e>9) printf("%c",e+'A'-10); /十進制以上數(shù)用字母A、B、C.代替else printf("%d",e);return 0;實驗三 停車場計費1 實驗內(nèi)容（1） 理解線性結構的邏輯特性和存儲特性；（2）靈活運用鏈表，隊列，堆棧等多種結構的操作運算2 數(shù)據(jù)結構與算法描述1）變量及函數(shù)的定義變量/函數(shù)名類 型說 明void main()主

15、函數(shù) 實現(xiàn)初始化操作，完成對子函數(shù)的調(diào)用 void InitStack(SqStackCar *);子函數(shù) 初始化棧/int Pop(SqStackCar *,CarNode *);/int Push(SqStackCar *,CarNode *);int InitQueue(LinkQueueCar *); /初始化隊列/int EnQueue(LinkQueueCar *,QueueNode *,CarNode *);/int DeQueue(LinkQueueCar *,QueueNode,CarNode *);voidArrival(SqStackCar *,LinkQueueCar*

16、,QueueNode*,CarNode *); 車輛到達的函數(shù)voidLeave(SqStackCar*,SqStackCar*,LinkQueueCar *,CarNode *); 車輛離開的函數(shù)voidBill(CarNode *);打印賬單的函數(shù)voidList(SqStackCar,LinkQueueCar); 查詢的函數(shù)/void List1(SqStackCar *);/void List2(LinkQueueCar *);/void reachtime(CarNode *);/void leavetime(CarNode *);2）程序流程圖3 實驗數(shù)據(jù)與實驗結果（可用文字描述或

17、貼圖的方式進行說明）1）測試數(shù)據(jù)。2）實驗結果 圖1 停車場計費的運行結果4 程序代碼清單（可直接將可運行源代碼粘貼在下面的方框中）#include<stdio.h>#include<stdlib.h>#include<string.h>#include<time.h>#include <conio.h>#include <ctype.h>#define Max 3 /*停車場容量*/#define PS "abc" /*默認密碼*/#define MPS 3 /*失敗重試次數(shù)*/*定義全局變量*/fl

18、oat price; time_t start,end;/*定義時間的結構體,hour為時，min為分，sec為秒*/typedef struct time int hour; int min; int sec;Time;/*定義車的結構體*/typedef struct node char num10; /車牌號 Time reach; /保存車輛到達的時間 Time leave; /保存車輛離開的時間CarNode;/*定義棧結構*/typedef struct NODE CarNode *stackMax+1; int top;SqStackCar;/*定義隊列中的結點*/typedef

19、 struct car CarNode *data; struct car *next;QueueNode;/*定義隊列結構*/typedef struct Node QueueNode *head; QueueNode *rear;LinkQueueCar;/*-用到的所有函數(shù)（及函數(shù)聲明部分）-*/void InitStack(SqStackCar *); /初始化棧/int Pop(SqStackCar *,CarNode *);/int Push(SqStackCar *,CarNode *);int InitQueue(LinkQueueCar *); /初始化隊列/int EnQu

20、eue(LinkQueueCar *,QueueNode *,CarNode *);/int DeQueue(LinkQueueCar *,QueueNode,CarNode *);void Arrival(SqStackCar *,LinkQueueCar *,QueueNode *,CarNode *); /車輛到達的函數(shù)void Leave(SqStackCar *,SqStackCar *,LinkQueueCar *,CarNode *); /車輛離開的函數(shù)void Bill(CarNode *); /打印賬單的函數(shù)void List(SqStackCar,LinkQueueCar)

21、; /查詢的函數(shù)/void List1(SqStackCar *);/void List2(LinkQueueCar *);/void reachtime(CarNode *);/void leavetime(CarNode *);/*-關于管理員進入的密碼驗證部分-*/*輸入密碼,并返回輸入的值*/char *getpas(char *s,int n) char c; int i; memset(s,0,n); for (i = 0; i<n-1; i+) c=getch(); if (isprint(c) si=c='r'?'0':c; putchar

22、('*'); if (c='r') break; putchar('n'); return s;/*密碼驗證函數(shù)，如果通過驗證則返回1，否則返回0*/int login() char ap80; int fg=1; do if (strcmp(getpas(ap,80),PS)&&fg<=MPS) printf("n"); printf("tt-n"); printf("tt-輸入有誤，還有%d次機會!-n",MPS-fg); printf("tt-n&q

23、uot;); printf("tt 密碼："); fg+; else system("cls"); printf("nnnnn"); printf("tt-n"); printf("tt-密碼正確!-n"); printf("tt-n"); return 1; while (fg<=MPS); return 0;/*-主函數(shù)入口-*/void main()printf("nnnnnn"); printf("t n"); print

24、f("t n"); printf("t 小菜停車場 n"); printf("t n"); printf("tn"); printf("t n"); start=time(NULL); end=time(NULL);while(end-start<2) /延時2秒執(zhí)行以下程序 end=time(NULL);system("cls"); printf("nnnnn"); printf("tt*n");printf("tt

25、身份驗證 n");printf("tt*n"); printf("tt 請輸入密碼(默認abc)："); if (login() printf("tttttLoading"); start=time(NULL); end=time(NULL); while(end-start<2) /延時2秒執(zhí)行以下程序 end=time(NULL); system("cls");SqStackCar Enter,Temp; LinkQueueCar Wait; QueueNode q; CarNode e; in

26、t ch; InitStack(&Enter); InitStack(&Temp); InitQueue(&Wait); printf(" ._. n"); printf(" | _ | n");printf(" | I I | n");printf(" | I I | n");printf(" | I I | n");printf(" | I I | n");printf(" | I_I | n");printf(" !

27、_! n");printf(" ._. n");printf(" ._|_|_. n");printf(" |: _ | n");printf(" | CD-ROM | n");printf(" !_! nn");printf(" 單日停車場管理系統(tǒng)操作室n "); printf(" 請輸入收費標準(以秒為單位)："); scanf("%f",&price); while(1) system("cls&quo

28、t;); printf("nn"); printf("ttt*停車場最大容量：%d*n",Max); printf("ttt*停車場收費標準：%2.2f元/秒*n",price); printf("nnnn"); printf("ttt*n"); printf("ttt * 1-到達登記 *n"); printf("ttt * 2-離開登記 *n"); printf("ttt * 3-信息查詢 *n"); printf("tt

29、t * 0-退出 *n"); printf("ttt *n"); printf("tttt請選擇（1|2|3|0）："); scanf("%d",&ch); if(ch<0&&ch>3) printf("nttt您輸入的選項不存在，請重新選擇!n"); else system("cls"); switch(ch) case 1: Arrival(&Enter,&Wait,&q,&e); break; case 2: L

30、eave(&Enter,&Temp,&Wait,&e); break; case 3: List(Enter,Wait); break; case 0: printf("nnnnn"); printf("t*謝謝使用！*nt"); exit(0); default: break; else system("cls"); printf("nnnnn"); printf("tt*n"); printf("tt 無此權限 n"); printf(&q

31、uot;tt*n"); start=time(NULL); end=time(NULL);while(end-start<2) /延時2秒執(zhí)行以下程序 end=time(NULL); system("cls"); main(); /*-有關棧和隊列的函數(shù)部分-*/*初始化棧*/void InitStack(SqStackCar *s) int i; s->top=0; for(i=0;i<=Max;i+) s->stacki=NULL;/*入棧*/int Push(SqStackCar *S,CarNode *e) if(S->top

32、<Max)S->top+; S->stackS->top=e; return 1;else return 0;/*出棧*/int Pop(SqStackCar *S,CarNode *e) if(S->top!=0)e=S->stackS->top;S->top-; return 1;else return 0;/*初始化隊列*/int InitQueue(LinkQueueCar *Q) Q->head=(QueueNode *)malloc(sizeof(QueueNode); if(Q->head!=NULL) Q->he

33、ad->next=NULL; Q->rear=Q->head; return 1; else return 0;/*入隊列*/int EnQueue(LinkQueueCar *Q,QueueNode *t,CarNode *e) t=(QueueNode *)malloc(sizeof(QueueNode); t->data=e; t->next=NULL; if(Q->head=NULL) Q->rear = Q->head = t; return 0; elseQ->rear->next = t;Q->rear = t;p

34、rintf("nttt%s車進入便道等候！",e->num); return 1;/*出隊列*/int DeQueue(LinkQueueCar *Q,QueueNode *q,CarNode *e) if(Q->head!=Q->rear) q=Q->head; Q->head=q->next;e=q->data; if(q=Q->rear) Q->rear=Q->head; / free(q); return 1; elsereturn 0;/*-獲取進出的系統(tǒng)時間函數(shù)部分-*/*獲取進入停車場的時間*/voi

35、d reachtime(CarNode *c) struct tm *date; time_t curr; curr =time(NULL); date =localtime(&curr); printf("%d/%d/%d %d:%d:%dn",date->tm_year+1900,date->tm_mon+1,date->tm_mday,date->tm_hour,date->tm_min,date->tm_sec); c->reach.hour=date->tm_hour; c->reach.min=dat

36、e->tm_min; c->reach.sec=date->tm_sec;/*獲取離開停車場的時間*/void leavetime(CarNode *c) struct tm *date; time_t curr; curr =time(NULL); date =localtime(&curr); printf(" %d:%d:%dn",date->tm_hour,date->tm_min,date->tm_sec); c->leave.hour=date->tm_hour; c->leave.min=date-

37、>tm_min; c->leave.sec=date->tm_sec;/*-關于收費，打印賬單部分-*/void Bill(SqStackCar *Enter,CarNode *c) float s,m; printf("nn"); printf("ttt*n"); printf("ttt%s車到達的時間是： %d:%d:%dn",c->num ,c->reach.hour,c->reach.min, c->reach.sec); printf("ttt離開時間是：");

38、leavetime(c); /獲取其離開的時間 printf("ttt*n"); printf("ttt*收費標準：%2.2f元/秒*n",price); printf("ttt*n"); s=(c->leave.hour-c->reach.hour)*3600+(c->leave.min-c->reach.min)*60+(c->leave.sec-c->reach.sec)*price; /計算其收費printf("ttt共計:%2.2f元n",s);printf("

39、;ttt收取現(xiàn)金(元):");scanf("%f",&m);printf("nttt找零:%2.2f元",m-s);/*-關于到達離開停車場部分-*/*到達停車場的處理函數(shù)*/void Arrival(SqStackCar *Enter,LinkQueueCar *W,QueueNode *q, CarNode *p) p=(CarNode *)malloc(sizeof(CarNode); printf("nnnnn"); printf("tt*n"); flushall(); /用于清除輸入的

40、所有緩沖區(qū) printf("ttt請輸入車牌號(例:豫B1234):"); gets(p->num); q->data=p; if(Enter->top<Max) Push(Enter,p); printf("tt*n"); printf("ttt車號為%s的車進入停車場的%d位置！n",p->num,Enter->top); printf("ttt到達時間是："); reachtime(p); /獲取其進入停車場的時間 printf("nnn");print

41、f("ttt請按'Enter'返回："); getchar(); else printf("tt*n"); printf("ttt停車場已滿，請進入便道等候"); EnQueue(W,q,p); printf("nnn"); printf("ttt請按'Enter'返回："); getchar(); /*離開停車場的處理函數(shù)*/void Leave(SqStackCar *Enter,SqStackCar *Temp,LinkQueueCar *W,CarNode

42、 *p) int position; if(Enter->top>0) printf("nn"); printf("nttt請輸入車在車場的位置/1-%d/：",Enter->top); scanf("%d",&position); if(position>=1&&position<=Enter->top) while(Enter->top>position) /若輸入的車位置不是最后一個，則先讓之后的車進入臨時棧。 p=Enter->stackEnter-

43、>top; Pop(Enter,p); Push(Temp,p); printf("nttt%d號位置的車%s離開停車場！n",Enter->top,Enter->stackEnter->top->num); Bill(Enter,Enter->stackEnter->top); /打印要離開車輛的信息及收費賬單 Pop(Enter,Enter->stackEnter->top); /車輛離開 while(Temp->top>=1) /臨時棧中的車按原順序進入停車場 Pop(Temp,p); Push(Ent

44、er,p); if(W->head!=W->rear) /若便道上有車，則讓第一個停在便道上的車進入停車場 DeQueue(W,W->head,W->head->data); Push(Enter,W->head->data); printf("nnn"); printf("ttt*n"); printf("ttt便道車牌號為%s的車進入車場第%d號位置.",W->head->data->num,Enter->top); printf("nttt到達時間是："); reachtime(W->head->data); getchar(); else printf("nnn");printf(