数据结构实验报告链表合并停车场问题

1、本科生实验报告实验课程数据结构与算法分析学院名称管理科学学院专业名称信息与计算科学学生姓名学生学号指导教师乐千桤实验地点6C402实验成绩 二 一四 年 十 月 二 一四 年 十二月实验一 链表合并1 实验内容(1) 创建链表并对其进行输出；(2) 利用指针实现对两个线形链表的合并，并输出其结果。2 数据结构与算法描述1）变量及函数的定义变量/函数名类 型说 明void main ()主函数main（）实现初始化操作，完成对子函数的调用 Node*MergeSList子函数定义一个指针函数，返回值类型为NODE类型的一个指针Node*CreatList()子函数创建链表void outlin(

2、Node *h)子函数输出链表的值2）程序流程图开始输入a调用create输入Biaon>a调用create输入b输入Biaon>ba>bYN调用hebing (p1,p2,a,b)调用hebing(p2,p1,a,b)A&&B空输出b结束调用print调用print3 实验数据与实验结果（可用文字描述或贴图的方式进行说明）1）测试数据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)/定义一个指针函数，返回值类型为NODE类型的一个指针Node *p1=NULL;Node *p2=NULL;Node *pcur;Node *head=NULL;/用于保存Merge之后的链表；/head=NULL; if(head1->next->data<head2->next->data)/找到两个链表的两个第一个节点中更小的一个节点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)/如果存在相同，则删除节点p2=p2->next;/*循环之后，两个链表要么为都为空，要么其中一个不为空，因为结束循环的条件有限制*/if(p1!=NULL)/把剩余的节点再接在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;实验二 进制转换1 实验内容（1）利用堆栈实现对任意进制的数的转换；（2）堆栈的应用及操作。2 数据结构与算法描述1）变量及函数的定义变量/函数名类 型说 明voidmain()conversion(N,M);主函数main（） 实现初始化操作，完成对子函数的调用 Status Push(SqStack *S,SElemTypee); 子函数压栈Status Pop(SqStack *S,SElemType *e); 出栈Status StackEmpty(SqStack *S); Status InitStack(SqStack *S); 建立一个空栈2） 程序流程图输出栈及转换结

9、果商为0？余数进栈（存入数组）转换后的十进制取余输入要转换的进制类型输出转换结果先转换成十进制数输入要输入数的进制及输入要转换的数开始3 实验数据与实验结果（可用文字描述或贴图的方式进行说明）1）测试数据N=255，r=162）实验结果 图1 进制转换的运行结果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;/- 基本操作的函数原型说明 -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是要转换的数，r是要转换的几进制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); /十进制以上数用字母A、B、C.代替else printf("%d",e);return 0;实验三 停车场计费1 实验内容（1） 理解线性结构的逻辑特性和存储特性；（2）灵活运用链表，队列，堆栈等多种结构的操作运算2 数据结构与算法描述1）变量及函数的定义变量/函数名类 型说 明void main()主

15、函数 实现初始化操作，完成对子函数的调用 void InitStack(SqStackCar *);子函数 初始化栈/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 *); 车辆到达的函数voidLeave(SqStackCar*,SqStackCar*,LinkQueueCar *,CarNode *); 车辆离开的函数voidBill(CarNode *);打印账单的函数voidList(SqStackCar,LinkQueueCar); 查询的函数/void List1(SqStackCar *);/void List2(LinkQueueCar *);/void reachtime(CarNode *);/void leavetime(CarNode *);2）程序流程图3 实验数据与实验结果（可用文字描述或

17、贴图的方式进行说明）1）测试数据。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 /*失败重试次数*/*定义全局变量*/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;/*-用到的所有函数（及函数声明部分）-*/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 *); /车辆到达的函数void Leave(SqStackCar *,SqStackCar *,LinkQueueCar *,CarNode *); /车辆离开的函数void Bill(CarNode *); /打印账单的函数void List(SqStackCar,LinkQueueCar)

21、; /查询的函数/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;/*密码验证函数，如果通过验证则返回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;/*-主函数入口-*/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秒执行以下程序 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秒执行以下程序 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(" 单日停车场管理系统操作室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秒执行以下程序 end=time(NULL); system("cls"); main(); /*-有关栈和队列的函数部分-*/*初始化栈*/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;/*-获取进出的系统时间函数部分-*/*获取进入停车场的时间*/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收取现金(元):");scanf("%f",&m);printf("nttt找零:%2.2f元",m-s);/*-关于到达离开停车场部分-*/*到达停车场的处理函数*/void Arrival(SqStackCar *Enter,LinkQueueCar *W,QueueNode *q, CarNode *p) p=(CarNode *)malloc(sizeof(CarNode); printf("nnnnn"); printf("tt*n"); flushall(); /用于清除输入的

40、所有缓冲区 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(); /*离开停车场的处理函数*/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(