數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告鏈表合并停車場問題

1、本科生實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)課程數(shù)據(jù)結(jié)構(gòu)與算法分析學(xué)院名稱管理科學(xué)學(xué)院專業(yè)名稱信息與計(jì)算科學(xué)學(xué)生姓名學(xué)生學(xué)號(hào)指導(dǎo)教師樂千榿實(shí)驗(yàn)地點(diǎn)6C402實(shí)驗(yàn)成績 二 一四 年 十 月 二 一四 年 十二月實(shí)驗(yàn)一 鏈表合并1 實(shí)驗(yàn)內(nèi)容(1) 創(chuàng)建鏈表并對(duì)其進(jìn)行輸出；(2) 利用指針實(shí)現(xiàn)對(duì)兩個(gè)線形鏈表的合并，并輸出其結(jié)果。2 數(shù)據(jù)結(jié)構(gòu)與算法描述1）變量及函數(shù)的定義變量/函數(shù)名類 型說 明void main ()主函數(shù)main（）實(shí)現(xiàn)初始化操作，完成對(duì)子函數(shù)的調(diào)用 Node*MergeSList子函數(shù)定義一個(gè)指針函數(shù)，返回值類型為NODE類型的一個(gè)指針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結(jié)束調(diào)用print調(diào)用print3 實(shí)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)結(jié)果（可用文字描述或貼圖的方式進(jìn)行說明）1）測試數(shù)據(jù)x1= 1 2 3 x2=2 3 5 7 2）實(shí)驗(yàn)結(jié)果 圖1 鏈表合并的運(yùn)行結(jié)果4 程序代碼清單#include<stdio.h>#include<malloc.h>typedef struct Node

3、 /定義一個(gè)Node的結(jié)構(gòu)體int data;Node *next; /*next表示指向鏈表的后一個(gè)元素Node;Node *s,*p;Node *MergeSList(Node *head1,Node *head2)/定義一個(gè)指針函數(shù)，返回值類型為NODE類型的一個(gè)指針Node *p1=NULL;Node *p2=NULL;Node *pcur;Node *head=NULL;/用于保存Merge之后的鏈表；/head=NULL; if(head1->next->data<head2->next->data)/找到兩個(gè)鏈表的兩個(gè)第一個(gè)節(jié)點(diǎn)中更小的一個(gè)節(jié)點(diǎn)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)/遍歷兩個(gè)鏈表并比較，把更小的值接在pcur后,pcur只是一個(gè)臨時(shí)鏈表 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é)點(diǎn)p2=p2->next;/*循環(huán)之后，兩個(gè)鏈表要么為都為空，要么其中一個(gè)不為空，因?yàn)榻Y(jié)束循環(huán)的條件有限制*/if(p1!=NULL)/把剩余的節(jié)點(diǎn)再接在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代表結(jié)束輸入s=(Node*)malloc(sizeof(Node);s->data=x;s->next=NULL;p->next=s;p=s; /把s的地址賦給P的下一個(gè)，再把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;實(shí)驗(yàn)二 進(jìn)制轉(zhuǎn)換1 實(shí)驗(yàn)內(nèi)容（1）利用堆棧實(shí)現(xiàn)對(duì)任意進(jìn)制的數(shù)的轉(zhuǎn)換；（2）堆棧的應(yīng)用及操作。2 數(shù)據(jù)結(jié)構(gòu)與算法描述1）變量及函數(shù)的定義變量/函數(shù)名類 型說 明voidmain()conversion(N,M);主函數(shù)main（） 實(shí)現(xiàn)初始化操作，完成對(duì)子函數(shù)的調(diào)用 Status Push(SqStack *S,SElemTypee); 子函數(shù)壓棧Status Pop(SqStack *S,SElemType *e); 出棧Status StackEmpty(SqStack *S); Status InitStack(SqStack *S); 建立一個(gè)空棧2） 程序流程圖輸出棧及轉(zhuǎn)換結(jié)

9、果商為0？余數(shù)進(jìn)棧（存入數(shù)組）轉(zhuǎn)換后的十進(jìn)制取余輸入要轉(zhuǎn)換的進(jìn)制類型輸出轉(zhuǎn)換結(jié)果先轉(zhuǎn)換成十進(jìn)制數(shù)輸入要輸入數(shù)的進(jìn)制及輸入要轉(zhuǎn)換的數(shù)開始3 實(shí)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)結(jié)果（可用文字描述或貼圖的方式進(jìn)行說明）1）測試數(shù)據(jù)N=255，r=162）實(shí)驗(yàn)結(jié)果 圖1 進(jìn)制轉(zhuǎn)換的運(yùn)行結(jié)果4 程序代碼清單（可直接將可運(yùn)行源代碼粘貼在下面的方框中）#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); /建立一個(gè)空棧Status InitStack(SqStack *S)S->base = (SElemType*)malloc(STACKINITSIZE * sizeof(SElemType);if(!S->base)exit(OVERFLOW); /存儲(chǔ)分配失敗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); /存儲(chǔ)分配失敗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)換的幾進(jì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); /十進(jìn)制以上數(shù)用字母A、B、C.代替else printf("%d",e);return 0;實(shí)驗(yàn)三 停車場計(jì)費(fèi)1 實(shí)驗(yàn)內(nèi)容（1） 理解線性結(jié)構(gòu)的邏輯特性和存儲(chǔ)特性；（2）靈活運(yùn)用鏈表，隊(duì)列，堆棧等多種結(jié)構(gòu)的操作運(yùn)算2 數(shù)據(jù)結(jié)構(gòu)與算法描述1）變量及函數(shù)的定義變量/函數(shù)名類 型說 明void main()主

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

16、,QueueNode*,CarNode *); 車輛到達(dá)的函數(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í)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)結(jié)果（可用文字描述或

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

18、oat price; time_t start,end;/*定義時(shí)間的結(jié)構(gòu)體,hour為時(shí)，min為分，sec為秒*/typedef struct time int hour; int min; int sec;Time;/*定義車的結(jié)構(gòu)體*/typedef struct node char num10; /車牌號(hào) Time reach; /保存車輛到達(dá)的時(shí)間 Time leave; /保存車輛離開的時(shí)間CarNode;/*定義棧結(jié)構(gòu)*/typedef struct NODE CarNode *stackMax+1; int top;SqStackCar;/*定義隊(duì)列中的結(jié)點(diǎn)*/typedef

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

20、eue(LinkQueueCar *,QueueNode *,CarNode *);/int DeQueue(LinkQueueCar *,QueueNode,CarNode *);void Arrival(SqStackCar *,LinkQueueCar *,QueueNode *,CarNode *); /車輛到達(dá)的函數(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 *);/*-關(guān)于管理員進(jìn)入的密碼驗(yàn)證部分-*/*輸入密碼,并返回輸入的值*/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;/*密碼驗(yàn)證函數(shù)，如果通過驗(yàn)證則返回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次機(jī)會(huì)!-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) /延時(shí)2秒執(zhí)行以下程序 end=time(NULL);system("cls"); printf("nnnnn"); printf("tt*n");printf("tt

25、身份驗(yàn)證 n");printf("tt*n"); printf("tt 請(qǐng)輸入密碼(默認(rèn)abc)："); if (login() printf("tttttLoading"); start=time(NULL); end=time(NULL); while(end-start<2) /延時(shí)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(" 請(qǐng)輸入收費(fèi)標(biāo)準(zhǔn)(以秒為單位)："); scanf("%f",&price); while(1) system("cls&quo

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

29、t * 0-退出 *n"); printf("ttt *n"); printf("tttt請(qǐng)選擇（1|2|3|0）："); scanf("%d",&ch); if(ch<0&&ch>3) printf("nttt您輸入的選項(xiàng)不存在，請(qǐng)重新選擇!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 無此權(quán)限 n"); printf(&q

31、uot;tt*n"); start=time(NULL); end=time(NULL);while(end-start<2) /延時(shí)2秒執(zhí)行以下程序 end=time(NULL); system("cls"); main(); /*-有關(guān)棧和隊(duì)列的函數(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;/*初始化隊(duì)列*/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;/*入隊(duì)列*/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車進(jìn)入便道等候！",e->num); return 1;/*出隊(duì)列*/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;/*-獲取進(jìn)出的系統(tǒng)時(shí)間函數(shù)部分-*/*獲取進(jìn)入停車場的時(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;/*獲取離開停車場的時(shí)間*/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;/*-關(guān)于收費(fèi)，打印賬單部分-*/void Bill(SqStackCar *Enter,CarNode *c) float s,m; printf("nn"); printf("ttt*n"); printf("ttt%s車到達(dá)的時(shí)間是： %d:%d:%dn",c->num ,c->reach.hour,c->reach.min, c->reach.sec); printf("ttt離開時(shí)間是：");

38、leavetime(c); /獲取其離開的時(shí)間 printf("ttt*n"); printf("ttt*收費(fèi)標(biāo)準(zhǔn)：%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; /計(jì)算其收費(fèi)printf("ttt共計(jì):%2.2f元n",s);printf("

39、;ttt收取現(xiàn)金(元):");scanf("%f",&m);printf("nttt找零:%2.2f元",m-s);/*-關(guān)于到達(dá)離開停車場部分-*/*到達(dá)停車場的處理函數(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請(qǐng)輸入車牌號(hào)(例:豫B1234):"); gets(p->num); q->data=p; if(Enter->top<Max) Push(Enter,p); printf("tt*n"); printf("ttt車號(hào)為%s的車進(jìn)入停車場的%d位置！n",p->num,Enter->top); printf("ttt到達(dá)時(shí)間是："); reachtime(p); /獲取其進(jìn)入停車場的時(shí)間 printf("nnn");print

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

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

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

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