数据结构实验：堆栈设计与应用-精简.doc

实验名称：实验三 堆栈设计与运用（实验报告） 实验目的： 1.熟悉堆栈的概念，加深对堆栈的理解； 2.掌握对堆栈的设计与运用。 实验内容： 1.设计自己的顺序堆栈（只处理整数，非通用，数据元素类型直接定义为int），实现堆栈的基本功能：入栈、出栈; 2.对上述功能进行测试，编写一个停车场管理程序，该停车场只有一个门，实现车的进入和开出的记录，还可以记录停车场是否为空，是否已满，这和堆栈的功能差不多。 实验方法： 1.堆栈的基本操作： a.初始化顺序栈 初始化顺序栈就是构造一个空的顺序栈，只需要把栈顶指针置为-1，初始化链栈就是构造一个空的链栈，先生成头结点，然后让top指针指向头结点。 b．判空栈 顺序表只需判断栈顶指针是否为-1，链栈只需判断头结点的指针域是否为空。 c.入栈 操作为：a.生成新节点；b.在栈顶位置插入新节点。 d.出栈 操作步骤为：a.判断所给栈是否为空，若空则产生下溢出错误，退出算法；b.删除栈顶元素 e.取栈顶元素 该操作获取栈顶元素的值，但栈顶元素并不出栈 f.销毁栈 操作过程为,凑头结点开始依次删除所有结点。 2.问题转化 对于停车场管理，假设该停车厂只能停放n辆汽车，且宽度只能停放一辆汽车，只能按照车辆到达的时间的先后顺序依次停放，这就是入栈和出栈，然后检测停车场是否停满。实现该功能就是相当于对堆栈进行基本的操作，只要调用相应操作的函数即可。 程序代码： 主程序 #include”carstop.h” void main() { SqStack park,way; LinkQueue pavement; int choice; InitStack(park); /*初始化停车场*/ InitStack(way); /*初始化让路的临时栈*/ do { printf(\n 停车场管理系统 \n); printf(\n------------------主菜单----------------------\n); printf ( ************************************************************** \n); printf(1.车辆到达 2.车辆离开3显示停车场信息0.退出系统\n) printf ( **************************************************************\n ); printf(\n请选择(1,2,3,0)：); scanf(%d,choice); if(choice0 choice3) continue; switch(choice) { case 1:Reach(park,pavement);break; /*车辆到达停车场*/ case 2:Leave(park,way,pavement,UnitPrice);break; /*车辆离开*/ case 3:DispPark(park);break; /*显示停车场信息*/ case 0:exit(0); /*退出主程序*/ default: break; } }while(1); } carstop.h #includestdio.h #include stdlib.h #include malloc.h /*顺序栈存储结构*/ #define STACKSIZE 2 //停车场容量 typedef struct{ char lisence[10]; int type; clock_t reach; clock_t leave; int stop; }CarInfo; typedef CarInfo DataType; typedef struct { DataType items[STACKSIZE]; int top; }SqStack; /*算法3-1初始化顺序栈*/ int InitStack(SqStack *S) { S-top=-1; return 1; } /*算法3-2判空栈*/ int StackEmpty(SqStack S) { if(S.top==-1) return 1; else return 0; } /*算法3-3入栈*/ int Push(SqStack *S,DataType e) { if(S-top=STACKSIZE-1) { printf(堆栈已满，不能完成入栈操作！\n); return 0; } S-top++; S-items[S-top]=e; return 1; } /*算法3-4出栈*/ int Pop(SqSt