return OK; }
void ListTraverse(LinkList L,void(*vi)(ElemType)) /* vi的形参类型为ElemType */
{ /* 初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数vi() */ LinkList p=L->next;
while(p) { vi(p->data); p=p->next; } printf(\}
LNode* Build_Node()/* 头插法建立带头结点的单链表 */ {
LNode *head,*p; int x;
head=(LNode*)malloc(sizeof(LNode));; head->next=NULL;
printf(\输入各结点的值,以0结束:\while(EOF!=(scanf(\{
p=(LNode*)malloc(sizeof(LNode)); p->data=x;
p->next=head->next; head->next=p; }
return head; }
void Print_Node(LinkList L) /* 打印单链表 */ { LinkList p=L->next;
while(p) { printf(\ printf(\}
int Count_Node(LNode *head) { LNode *p=head->next; int num=0;
while(p!=NULL){num++;p=p->next;} return num; }
main() {
int *a;/*用a来存储单链表中的第n个元素*/ int *b;/*用b来存储删除单链表中的第n个元素*/ int c;/*用来存储单链表长度*/
15
int *d;/*用来存储前驱*/ int *f;/*用来存储后继*/
int *g;/*用来存储所找元素的位置*/ int i,m,n; LinkList La;
InitList(La); /*初始化单链表La*/
printf(\链表演示程序********************\\n\ printf(\请输入链表结点数： \ scanf(\
printf(\请输入用来建立链表的数:\\n\ i=1;
for (i=1;i<=m;i++) { scanf(\ ListInsert(La,i,n);
}
printf(\您建立的链表为：\ Print_Node(La);
printf(\判断此链表是否非空：\ if(ListEmpty(La)) printf(\空!\\n\
else printf(\非空!+长度为%d\\n\
printf(\请输入你要在链表中取元素的位置：\ scanf(\
GetElem(La,n,a);/*取单链表中第n个元素并用a存储*/ printf(\你要取的第%d个元素a=%d\\n\ Print_Node(La);
ListDelete(La,3,b);/*删除单链表中第三个元素并用b存储*/ Print_Node(La);
ListInsert(La,4,9);/*在第4个元素前插入9*/ Print_Node(La);
c=ListLength(La);/*求单链表长度*/
printf(\请输入你要求前驱的元素的值：\ scanf(\
PriorElem(La,n,d);/*求n的前驱*/ printf(\元素%d的前缀为%d\\n\
printf(\请输入你要求后继的元素的值：\ scanf(\
NextElem(La,n,f);/*求n的后继*/ printf(\元素%d的后继为%d\\n\ g=LocateElem(La,4);/*定位操作*/ printf(\ printf(\ return 0; }
16
实验四 栈和队列的基本操作
一、 实验目的
a) b) c)
掌握栈和队列的顺序存储结构和链式存储结构; 掌握栈和队列的基本特点; 掌握栈和队列的基本运算。
二、 实验内容
1. 对于键盘输入的任意一个非负的十进制整数，输出与其等值的八进制数。
提示：由于上述的计算过程是从低位到高位顺序产生的八进制数的各个数位，而打印输出，一般来说应从高位到地位进行，恰好和计算过程相反。因此可以先将计算过程中得到的八进制数的各位进栈，待相对应的八进制数的各位均产生以后，再使其按顺序出栈，并打印输出。即得到了与输入的十进制数相对应的八进制数。
将十进制数N和其它d进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单方法基于下列原理：即除d取余法。例如：(1348)10=(2504)8
N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2
从中我们可以看出，最先产生的余数4是转换结果的最低位，这正好符合栈的特性即后进先出的特性。所以可以用顺序栈来模拟这个过程。
2.设某汽车加油站的有两台油泵，每台油泵为一辆汽车加油的时间为d分钟。现已知该加油站的到车率1辆/g分钟。用计算机来模拟该汽车加油站的工作情况。
提示：首先，用一个容量为m的循环队列来组织等待加油的汽车，并对到达加油站的汽车按先后顺序用自然数给予编号。假设循环队列的存储空间用一维数组模拟。算法参考教材46页至50页。
3.选做题
设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚，依次从停车场最里面向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已停放n辆车，则后面来的车辆只能停放在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如果有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进入停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编制一个程序模拟该停车场的管理。
提示：以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以
17
顺序结构实现，队列以链表实现。需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。
设n=2,输入数据为：（?A?，1，5），（?A?，2，10），（?D?，1，15），（?A?，3， 20）， （?A?，4，25），（?A?，5，30），（?D?，2，35），（?D?，4，40），（?E?，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，?A?表示到达；?D?表示离去，?E?表示输入结束.
三、实验步骤
在微型计算机上调试编写的程序，记录运行结果。
四、参考算法
/*停车场管理系统*/ #include
/*------------------------------------------------------------------------------*/ #define MAX 2 /*车库容量*/
#define price 0.05 /*每车每分钟费用*/ typedef struct time
{
int hour;
int min;
}Time; /*时间结点*/ typedef struct node
{
char num[10]; Time reach; Time leave;
}CarNode; /*车辆信息结点*/ typedef struct NODE {
CarNode *stack[MAX+1]; int top;
}SeqStackCar; /*模拟车站*/ typedef struct car
{
CarNode *data; struct car *next; }QueueNode; typedef struct Node
{
QueueNode *head; QueueNode *rear;
}LinkQueueCar; /*模拟通道*/
18
void InitStack(SeqStackCar *); /*初始化栈*/ int InitQueue(LinkQueueCar *); /*初始化便道*/
int Arrival(SeqStackCar *,LinkQueueCar *); /*车辆到达*/
void Leave(SeqStackCar *,SeqStackCar *,LinkQueueCar *); /*车辆离开*/ void List(SeqStackCar,LinkQueueCar); /*显示存车信息*/ void main() {
SeqStackCar Enter,Temp; LinkQueueCar Wait; int ch;
InitStack(&Enter); /*初始化车站*/
InitStack(&Temp); /*初始化让路的临时栈*/ InitQueue(&Wait); /*初始化通道*/ while(1) {
printf(\车辆到达\printf(\车辆离开\printf(\列表显示\printf(\退出系统\\n\while(1) {
scanf(\
if(ch>=1&&ch<=4)break;
else printf(\请选择： 1|2|3|4.\}
switch(ch) {
case 1:Arrival(&Enter,&Wait);break; /*车辆到达*/
case 2:Leave(&Enter,&Temp,&Wait);break; /*车辆离开*/ case 3:List(Enter,Wait);break; /*列表打印信息*/ case 4:exit(0); /*退出主程序*/ default: break; }
} }
void InitStack(SeqStackCar *s) /*初始化栈*/ {
int i;
s->top=0;
for(i=0;i<=MAX;i++)
s->stack[s->top]=NULL;
}
19