数据结构实验报告——实验三

 

第二篇：数据结构实验报告(实验三 停车场管理)

            韶     关     学     院

      学  生  实  验  报  告  册

实验课程名称：数据结构与算法

实验项目名称：实验三  栈和队列及其应用

停车场管理

实验类型（打√）：（基础   、综合   、设计√   ）

院    系：信息工程学院计算机系   专  业：*****

姓    名：***                    学  号：*****

指导老师：陈正铭

              韶关学院教务处编制

一、实验预习报告内容

                                                   预习日期：20##年 4 月 16 日

                     二、实验原始（数据）记录

实验时间： 20## 年 4  月 18 日（星期三   第 7，8 节）

实验同组人：

                            三、实验报告内容
                                        20##年 4 月 20 日

注：1、如有个别实验的实验报告内容多，实验报告册页面不够写，或有识图，画图要求的，学生应根据实验指导老师要求另附相同规格的纸张并粘贴在相应的“实验报告册”中。

2、实验报告册属教学运行材料，院系（中心）应按有关规定归档保管。 

【源程序】

#include<stdio.h>

#include<stdlib.h>

#include<iostream.h>

typedef int Status; //元素类型

int flag=0;

typedef struct{

int carnumber;  //车号

int time; //汽车“到”或“离”的时刻

}SElemType;

//以下是对栈数据类型的定义

#define STACK_INIT_SIZE 2

#define STACKINCREMENT 1

typedef struct{

    SElemType *base;  

    SElemType *top; 

    int stacksize; 

}SqStack;

Status InitStack(SqStack &s){    

//构造一个空栈S

    s.base=(SElemType * )malloc

(STACK_INIT_SIZE * sizeof(SElemType));

    if(!s.base) exit(0);

    s.top=s.base;

    s.stacksize=STACK_INIT_SIZE;

    return 1;

}

Status Push(SqStack &s,SElemType e){

//插入元素e为新的栈顶元素

if(s.top-s.base>=s.stacksize){//栈满

s.base=(SElemType * ) realloc

(s.base,(s.stacksize+STACKINCREMENT) * sizeof(SElemType));

if(!s.base) exit(0);  //存储分配失败

s.top=s.base+s.stacksize;

s.stacksize+=STACKINCREMENT;

}

*s.top++=e;

return 1;

}

Status Pop(SqStack &s,SElemType &e){

//若栈不空，则删除s的栈顶元素，用e返回其值，并返回OK，否则返回ERROR

    if(s.top==s.base) return 0;

    e=*--s.top;

    return 1;

}

//以下是对队列数据类型的定义

typedef struct QNode{

    SElemType data;

    struct QNode *next;

}QNode,*QueuePtr;

typedef struct{

    QueuePtr front;

    QueuePtr rear;

}LinkQueue;

Status InitQueue(LinkQueue &Q){ 

//构造一个空队列Q

    Q.front=Q.rear

=(QueuePtr)malloc(sizeof(QNode));

    if(!Q.front) exit(0);

    Q.front->next=NULL;

    return 1;

}

Status EnQueue(LinkQueue &Q,SElemType e){  //插入元素e为新的队尾元素

QueuePtr p;

p=(QueuePtr)malloc(sizeof(QNode));

if(!p) exit(0);

p->data=e;p->next=NULL;

Q.rear->next=p;

Q.rear=p;

return 1;

}

Status DeQueue(LinkQueue &Q,SElemType &e){//若队列不空，则删除Q的对头元素，用e返回其值，并返回OK，否则返回ERROR

    QueuePtr p;

    if(Q.front==Q.rear) return 0;

    p=Q.front->next;

    e=p->data;

    p->next=NULL;

    Q.front->next=p->next;

    if(Q.rear==p) Q.rear=Q.front;

    free(p);

    return 1;

}

//对汽车到达时的处理

void CarArrival(SqStack &s,LinkQueue &Q){

SElemType e;

cout<<"请输入车号:";

cin>>e.carnumber;

cout<<"请输入到达时刻:";

cin>>e.time;

if(s.top-s.base>s.stacksize){

EnQueue(Q,e);

cout<<"--------------------------------\n";

cout<<"|车号|  停车位置   | 到达时刻  |\n";

cout<<"--------------------------------\n";

cout<<"|"<<e.carnumber<<"| 停在便道上等待|"<<e.time<<"        |"<<"\n";

cout<<"--------------------------------\n";

}

else{

Push(s,e);

*s.top++=e;

cout<<"-------------------------------\n";

cout<<"|车号|  停车位置  | 到达时刻  |\n";

cout<<"-------------------------------\n";

cout<<"|"<<e.carnumber<<"| 停在停场内"<<++flag<<"号位|"<<e.time<<"      |"<<"\n";

cout<<"-------------------------------\n";

}

}

void CarDeparture(SqStack &s,LinkQueue &Q){

    SqStack T;   //临时倒车处

    int money;//停留时刻

    SElemType a,e;

    int carnumber,time;;

    InitStack(T);//构造临时倒车处

    cout<<"请输入车号:"<<endl;

    cin>>carnumber;

    cout<<"请输入离去时刻:"<<endl;

    cin>>time;

    a=*(s.top-1);

    do{

        Pop(s,e);Push(T,e);

        *s.top--=e;

        a=*(s.top-1);

    }while(e.carnumber!=carnumber);

    Pop(s,e);

    money=time-e.time;

cout<<"韶关学院停车场收费单   \n";

cout<<"--------------------------------\n";

cout<<"|车号   |到达时刻  |离去时刻  |停留时刻  |费用(元)  |\n";

cout<<"--------------------------------\n";

cout<<"|"<<carnumber<<"|"<<e.time<<"        |"<<time<<"|"<<money<<" |"<<money*2<<"         |"<<"\n";

cout<<"--------------------------------\n";

    flag--;

    while(T.base!=T.top){

        Pop(T,e);

*s.top++=e;

}

    while(Q.front!=Q.rear){

        if(s.top-s.base<s.stacksize){

            DeQueue(Q,e);

            Push(s,e);     

            *s.top++=e;

        }

    }

    if(s.top-s.base> STACK_INIT_SIZE){

cout<<"\n便道上有车进入停车场!"<<"\n此车停在"<<++flag<<"车位"<<endl;

     }

}

void shurujiesu(){

cout<<"\n\n输入结束（END)!\n\n";

}

void main()

{   char choice;

    SqStack s;//s为停车场

    LinkQueue Q;//Q为便道

    InitStack(s);InitQueue(Q);

    cout<<"----------------------------\n";

    cout<<|*********欢迎使用广东省韶关学院停车场管理系统**********| \n";

    cout<<"|==========================|\n";

    cout<<"\n|A、汽车到达       | \n";

    cout<<"\n|D、汽车离开       | \n";

    cout<<"\n|E、输入结束       | \n";

    cout<<"\n|Q、退出本系统     | \n";

    cout<<"\n|------------------| \n";

    cout<<" 请选择所需要的操作功能(A,D,E,Q):";

    do{

        cin>>choice;

        switch(choice){

        case'A':

            CarArrival(s,Q);break;

        case'D':

            CarDeparture(s,Q);break;

        case'E':

            shurujiesu();break;

        case'Q':

            exit(0);

        }

        cout<<"请选择所需要的操作功能(A,D,E,Q):";

    }while(1);

}