数据结构实验指导书

学院

计算机与信息工程学院

《数据结构》

实

验

指

导

书

目录

数据结构实验总体要求1

实验一复数四则运算1

实验二集合的并、交和差运算4

实验三算术表达式求值演示8

实验四哈夫曼编/译码器11

实验五部排序算法比较15

附录17

1/29

数据结构实验总体要求

1.实验教学的地位和作用

数据结构是一门实践性较强的软件基础课程，它在计算机软件教学中起着承

上启下的作用，通过实验使学生在基本数据结构的逻辑特性和物理表示、数据结

构的选择和应用、算法的设计与实现等方面加深对课程的理解，同时在程序设计

方法以与上机操作等基本技能和科学作风方面受到较严格的训练。

2.本课程实验教学基本理论与技术容

（1）基础理论方面：从数据结构的类定义和对象的使用，以与存储表示和

操作的实现两个层次，系统地学习和掌握常用的基本数据结构（包括数组、顺序

表、多项式、字符串、链表、栈与队列、树和森林、二叉树、堆、集合、图、搜

索结构、索引结构、散列结构等）与其不同的实现，了解并掌握分析、比较和选

择不同数据结构、不同存储结构、不同算法的原则和方法，为后续课程的学习打

好基础。

（2）实验技术方面：系统地学习和掌握程序设计方法、程序设计风格与在

不同的存储结构上实现的算法的设计思想，从中体会和掌握选择结构的方法和算

法设计的思考方式与技巧，提高分析问题和解决问题的能力。

3.学生应达到的实验能力标准

使学生了解计算机应用中数据对象的特性，学会在应用中，根据现实世界中

的问题选择适当的数据逻辑结构和存储结构以与相应算法，并且培养基本的、良

好的程序设计技能。

4.学时、教学文件与教学形式

学时：数据结构课程总学时为72学时，其中实验18学时，占总学时25%。

教学形式：本课程实验为综合性实验。要求学生课前预习实验指导书，写出

预习报告，指导教师应概述实验的原理、方法与仪器使用等，并作针对性指导，

具体实验步骤和结果分析、处理由学生独立完成。

实验一复数四则运算

一、实验目的

本次实验的主要目的在于帮助读者熟悉抽象数据类型的表示和实现方法。抽

象数据类型需借助固有数据类型来表示和实现，即利用高级程序设计语言中已存

在的数据类型来说明新的结构，用已经实现的操作来组合新的操作，具体实现细

节则依赖于所用语言的功能。通过本次实习还可以帮助读者复习高级语言的使用

方法。

二、实验容

设计一个可进行复数运算的演示程序。要现下列六种基本运算：1）由输入的

实部和虚部生成一个复数；2）两个复数求和；3）两个复数求差；4）两个复数求积,

1/29

5）从已知复数中分离出实部；6）从已知复数中分离出虚部。运算结果以相应的复

数或实数的表示形式显示。

三、实验仪器、设备与材料

586以上微机

四、实验原理

复数在计算机中的表示与复数的四则运算规则。

五、实验步骤

1.问题分析和任务定义；

2.数据类型和系统设计；

3.编码实现和静态检查；

4.上机准备和上机调试；

5.总结和整理实验报告。

六、实验报告要求

实验报告开头就给出题目、班级、、学号和完成日期，并包括以下七个容：

1.需求分析；

2.概要设计；

3.详细设计；

4.调试分析；

5.经验和体会等；

6.测试结果；

7.附录。

七、实验注意事项

实验前先预习，完成问题分析和任务定义的工作。

八、测试数据

2/29

对下列各对数据实现求和。

(1)0；0；应输出“0”

(2)3.1,0：4.22,8.9；应输出“7.32+i8.9”

(3)-1.33,2.34；0.1,-6.5；应输出“7.23-i4.16”

(4)0,9.7；-2.1,-9.7；应输出

(5)7.7,-8;-7.7,0;应输出“T8”

九、选做容

实现算数的其他运算，如：两个复数相乘、求共辄等。

十、实验要点

typedefstruct

(

doubIereaI;

doubIeimg;

}CompIexNumber；

十一、部分参考代码

voidCreateCompIexNumber(CompIexNumber*c,doublea,doubIeb)

(

c->reaI=a;

c->img=b;

return;

)

voidAddCompIexNumber(CompIexNumber*c,CompIexNumberd,CompIexNumberc2)

(

c->real=c1.real+c2.real;

c->img=c1.img+c2.img;

return;

)

voidSubCompIexNumber(CompIexNumber*c,CompIexNumberd,CompIexNumberc2)

(

c->reaI=c1.reaI-c2.reaI;

c->img=c1.img-c2.img；

return;

3/29

)

voidMultiCompIexNumber(CompIexNumber*c,CompIexNumberd,CompIexNumberc2)

(

c->real=d.real*c2.real-d.img*c2.img;

c->img=d.reaI*c2.img+d.img*c2.reaI；

return;

1

voidConCompIexNumber(CompIexNumber*c,CompIexNumberc1)

(

c->reaI=c1.reaI;

c->img=c1.img*(-1);

return;

)

实验二集合的并、交和差运算

一、实验目的

本次实验的主要目的在于帮助学生熟练掌握线性表的基本操作在两种存储

结构上的实现，其中以各种链表的操作和应用作为重点容。

二、实验容

编制一个能演示执行集合的并、交和差运算的程序。集合元素限定小写字母

字符［'a'…'z'］。演示程序以用户和计算机的对话方式执行。

三、实验仪器、设备与材料

586以上微机

四、实验原理

利用链表的基本运算(插入、删除、查找与合并等)实现集合的基本运算。

五、实验步骤

1.问题分析和任务定义；

2.数据类型和系统设计；

3.编码实现和静态检查；

4.上机准备和上机调试;

4/29

5.总结和整理实验报告。

六、实验报告要求

实验报告开头就给出题目、班级、、学号和完成日期，并包括以下七个容：

1.需求分析；

2.概要设计；

3.详细设计；

4.调试分析；

5.经验和体会等；

6.测试结果；

7.附录。

七、实验注意事项

实验前先预习，完成问题分析和任务定义的工作。

八、测试数据

(1)Set1="magazine”,Set2="paper",

Set1USet2="aegimnpra”,Set1ClSet2="ae”,Set1-Set2=

"gimnz”

(2)Set1=012oper4a6tion89,>,Set2="errordate",

Set1USet2="adeinoprt”,Set1(~ISet2="aeort”,Set1-Set2=

“inp”

九、选作容

(1)集合元素的判定和子集判定运算

(2)求集合的补集

(3)集合的混合运算表达式求值

(4)集合的元素类型推广到其他类型，甚至任意类型

5/29

十、实验要点

typedefcharEIemType;

typedefstructE1emNode(

EIemTypeeIem;

structEIemNode*next;

}ElemNode,*Set;

十一、部分参考代码

/*-------------FunctionList-

intLengthOf(Setsrc)返回一个集合的长度

voidCreateSet(Setdest)创建一^个新的字母集合限定a-z

voidEmptySet(Setdest)清空一个集合，保留头结点

voidDestroySet(Setdest)销毁集合

voidDispIaySet(Setsrc)打印集合的所有元素

voidAddElem(Setdest,EIemTypee)在链表尾部追加一个元素

voidDeIEIem(Setdest,EIemTypee)删除集合中的一个元素一次

intExistEIem(Setdest,ElemTypee)判断元素是否存在于集合中

voidContactSet(Setdest,Setsrc)连接一个集合到另一个集合

voidMuISet(Setdest,Setsrd,Setsrc2)集合交运算

voidAddSet(Setdest,Setsrd,Setsrc2)集合并运算

voidSubSet(Setdest,Setsrc1,Setsrc2)集合差运算

intExistSubset(Setdest,Setsrc)子集判断

voidNegSet(Setdest,Setsrc)求补集

*/

//---------------BasicFunctions

intLengthOf(Setsrc)

(

inti=0;

whiIe(src->next!=NULL)

(

i++；

src=src->next;

)

returni;

}//返回一个集合的长度

voidCreateSet(Setdest)

6/29

ElemTypech；

Setp=dest,n;

for(;;)

(

ch=getchar();

if(ch='\n')break;

if(ch<97||ch>122)continue;

n二(Set)maIIoc(sizeof(EIemNode));

p->next=n;

n->eIem=ch;

n->next=NULL;

P二n;

)

return;

}//创建一个新的字母集合限定a-z

voidEmptySet(Setdest)

(

Setp,n;

while(dest->next!=NULL)

(

p=dest;

n=p->next;

for(;n->next!=NULL;)

(

P二n；

n=n->next;

)

free(n);

p->next=NULL;

)

}//清空一个集合，保留头结点

voidDestroySet(Setdest)

{

EmptySet(dest);

free(dest);

}〃销毁集合

voidDisplaySet(Setsrc)

Setp;

if(src->next==NULL)

7/29

printf("0");

return；

1

p=src;

do

(

p=p_>next;

putchar(p->eIem);

)

while(p->next!=NULL);

}//打印集合的所有元素

实验三算术表达式求值演示

一、实验目的

本次实验的目的在于使读者深入了解栈和队列的特性，以便在实际间题背景

下灵活运用他们；同时还将巩固对这两种结构的构造方法的掌握。

二、实验容

设计一个程序，演示用算符优先法对算术表达式求值的过程。要求以字符序

列的形式从终端输入语确的、不含变量的整数表达式。利用教科书表3.1给出

的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的例

3-1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。

三、实验仪器、设备与材料

586以上微机

四、实验原理

应用栈先进后出的特点判定表达式中运算符号的优先关系，实现表达式求值

运算。

五、实验步骤

1.问题分析和任务定义；

2.数据类型和系统设计；

3.编码实现和静态检查；

4.上机准备和上机调试;

8/29

5.总结和整理实验报告。

六、实验报告要求

实验报告开头就给出题目、班级、、学号和完成日期，并包括以下七个容:

1.需求分析；

2.概要设计；

3,详细设计；

4.调试分析；

5.经验和体会等；

6.测试结果；

7.附录。

七、实验注意事项

实验前先预习，完成问题分析和任务定义的工作。

八、测试数据

8;1+2+3+4；88-1*5：1024/4*8;1024/(4*8);(20+2)*(6/2);

3-3-3；8/(9-9)；2*(6+2*(3+6*(6+6)))；(((6+6)*6+3)*2+6)*2

九、选作容

(1)扩充运算符集，如增加乘方、单目减、赋值等运算

(2)运算量可以是变量

(3)运算量可以是实数类型

(4)计算器的功能和仿真界面

十、实验要点

#defineSTACK_INIT_SIZE100

#defineSTACKINCREMENT10

typedefintEIemType;

9/29

typedefstruct{

EIemType*base;

EIemType*top；

intstacksize;

}Stack;

十一、部分参考代码

intIfEmptyStack(StackS)

(

if(S.base==S.top)return1；

return0;

)

voidInitStack(Stack&S)

(

S.base=(ElemType*)maIIoc(STACK_INIT_SIZE*sizeof(ElemType));

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return;

}//创建一个空栈

voidEmptyStack(Stack&S)

(

S.top=S.base;

return;

)

voidPush(Stack&S,ElemType&e)

(

if(S.top-S.base>=S.stacksize)

(

S.base=(EIemType

*)reaIIoc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

S.top=S.base+S.stacksize;

S.stacksize十二STACKINCREMENT;

1

*S.top++-e；

return;

}〃插入元素e为新的栈顶元素

voidPop(Stack&S,EIemType&e)

10/29

if(S.top—S.base)return;

e=*-S.top;

return;

}〃弹出栈顶元素

EIemTypeGetTop(Stack&S)

{

if(S.top==S.base)return0;

return*(S.top-1);

}//取栈顶元素

voidShowStack(StackS)

(

ElemType*p=S.base;

while(p!=S.top)

printf("%d",*p++);

return;

}//打印栈

实验四哈夫曼编/译码器

一、实验目的

树是应用极为广泛的数据结构，也是这门课程的重点。它的特点在于非线性。

本实验突出了数据结构加操作的程序设计观点，希望达到熟悉各种存储结构的特

性，以与如何应用树解决具体问题(即原理与应用的结合)等目的。

二、实验容

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降

低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在

接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信

道)，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼

码的编/译码系统。要求一个完整的系统应具有以下功能：

(1)I:初始化(InitiaIization)。从终端读入字符集大小，以与n个字符和

n个权值，建立哈夫曼树，并将它存于文件hfmTree中。

(2)E:编码(Encoding)。利用以建好的哈夫曼树(如不在存，则从文件

hfmTree中读入)，对文件ToBeTran中的正文进行编码，然后将结果存入文件

CodeFiIe中。

(3)D:译码(Decoding)。利用己建好的哈夫曼树将文件CodeFiIe中的代码

进行译码，结果存入文件TextFiIe中。

11/29

(4)P：印代码文件(Print)o将文件CodeFile以紧凑格式显示在终端上，

每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。

(5)T:印哈夫曼树(Treeprinting).将已在存中的哈夫曼树以直观的方式

(树或凹入表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件

TreePrint中。

三、实验仪器、设备与材料

586以上微机

四、实验原理

最优二叉树生成方法或哈夫曼编码原理

五、实验步骤

1.问题分析和任务定义；

2.数据类型和系统设计；

3.编码实现和静态检查；

4.上机准备和上机调试；

5.总结和整理实验报告。

六、实验报告要求

实验报告开头就给出题目、班级、、学号和完成日期，并包括以下七个容：

1.需求分析；

2.概要设计；

3,详细设计；

4.调试分析；

5.经验和体会等；

6.测试结果；

7.附录。

七、实验注意事项

12/29

实验前先预习，完成问题分析和任务定义的工作。

八、测试数据

(1)利用教科书例6-2中的数据调试程度

(2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下

报文的编码和译码：“THISPROGRAMISMYFAVORITE”。

字符AB0DEFGHIJKLM

频度1866413223210321154757153220

字符N0PQRSTUVWXYZ

频度5763151485180238181161

九、选作容

(1)修改你的系统，实现对你的系统的原程序的编码和译码

(2)实现各个转换操作的源/目文件，均由用户在选择此操作时指定

十、实验要点

typedefstruct{

charindex;

intweight;

intparent,IchiId,rchiId;

}HTNode,*HuffmanTree；

typedefchar**HuffmanCode；

十一、部分参考代码

voidSeIect(HuffmanTree&HT,intm,int&s1,int&s2){

inti;

for(i=1;;i++){

if(HT[i].parent=O){

s1=i;

i++;

break;

)

)

for(;;i++){

if(HT[i].parent==0){

s2=i;

i++;

13/29

break;

)

)

for(;i<=m&&HT[i].parent==0;i++){

if(HT[i].weight<HT[s1].weight)

s1=i;

eIseif(HT[i].weight<HT[s2].weight)

s2=i;

)

)

voidBuiIdHuffmanTree(HuffmanTree&HT,char*c,int*w,intn){

HuffmanTreep;

intm,s1,s2,i;

if(n<=1)return;

m—2*n-1;

HT=(HuffmanTree)maIloc((m+1)*sizeof(HTNode));

for(p=HT,i=0;i<-n;++i,++p,++w,++c){

p->index=*c;

p->weight=*w;

p->parent=0;

p->lchild=0;

p->rchild=0;

1

HT[0].weight=n;

for(;i<=m;++i,++p){

p->index=0;

p->weight=0;

p->parent=0;

p->lchild=0;

p->rchild=0;

)

for(i=n+1;i<=m;++i){

Select(HT,i-1,s1,s2);

HT[s1].parent=i;

HT[s2].parent=i;

HT[i].IchiId=s1；

HT[i].rchild=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight;

1

)

voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,intn){

14/29

char*cd;

intf,c,i,start;

HC=(HuffmanCode)maIloc((n+1)*sizeof(char*));

cd=(char*)maIIoc(n*sizeof(char));

cd[n-1]='\0';

for(i=1;i<=n;++i){

start=n-1;

for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)

if(HT[f].Ichild=c)cd[—start]='0,;

eIsecd[—start]=1;

HC[i]=(char*)maIIoc((n-start)*sizeof(char));

strcpy(HC[i],&cd[start]);

)

free(cd);

)

实验五部排序算法比较

一、实验目的

本次实验的目的在于通常实验掌握排序的基本概念，熟悉各种部排序的方

法。

二、实验容

通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观

感受。要求对以下6种常用的部排序算法进行比较：起泡排序、直接插入排序、

简单选择排序、快速排序、希尔排序、堆排序。待排序表的表长不小于1000;

其中的数据要用伪随机数产生程序产生，至少要用5组不同的输入数据作比较。

比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换计为3

次移动)；最后要对结果做出简单分析，包括对各组数据得出结果波动大小的解

释。

三、实验仪器、设备与材料

586以上微机

四、实验原理

各种排序算法。

五、实验步骤

1.问题分析和任务定义；

15/29

2.数据类型和系统设计；

3.编码实现和静态检查；

4.上机准备和上机调试；

5.总结和整理实验报告。

六、实验报告要求

实验报告开头就给出题目、班级、、学号和完成日期，并包括以下七个容：

1.需求分析；

2.概要设计；

3.详细设计；

4.调试分析；

5.经验和体会等；

6.测试结果；

7.附录。

七、实验注意事项

实验前先预习，完成问题分析和任务定义的工作。

八、测试数据

由随机数产生器生成

九、选作容

(1)增加折半插入排序、二路插入排序、归并排序和基数排序等

(2)对不同的输入表长作试验、观察检查两个指示相对于表长的变化关系。

还可以对稳定性作验证

十、实验要点

#defineLIST_INIT_SIZE10/*线性表存储空间的初始分配量*/

#defineLISTINCREMENT2/*线性表存储空间的分配增量*/

typedefstruct

16/29

EIemType*eIem;/*存储空间基址*/

intIength;/*当前长度*/

intIistsize;/*当前分配的存储容量(以sizeof(ElemType)为单位)*/

}SqList;

typedefint*SqList;

十一、部分参考代码

voidInit(SqList&LA)

inti=1;

srand(time(NULL));

for(；i<=1000；i++)

*(LA+i)=rand();

return;

)

voidLoadData(SqList&LA,SqList&LB)

inti=1;

for(；i<=1000；i++)

*(LB+i)=*(LA+i);

附录

实验报告书写样例

题目：停车场问题的求解程序

零.问题描述

设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出.汽车在停车场

按照车辆

到达时间的先后顺序，一次由南向北排列（大门在最南端，最先到达的第一辆汽车停放在车场

的最北端），

若车场已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道

上的第一

17/29

辆车即可开入；当停车场的某辆车要开走时，在它之后进入的车辆必须退出车场为它让路，待

该辆车

开出大门外，其他车辆再按照原次序进入车场，每辆车停放在车场的车在它离开停车场时必

须按照它停

留的时间长短交纳费用.实为停车场编制按照上述要求进行管理的模拟程序.

一.需求分析：

1.用一个队列，两个栈实现程序.其中，

一个栈(Park)表示停车场.

一个栈(Tmp)表示当停车场中的一辆车要出去时，它后面的车所进的道.

一个队列(Wait)表示停车场满后来的车所进的道.

2.有车来时候,若停车场未满,则入Park栈.若停车场已满，则进入Wait队列.

3.当有车开走时，若是栈顶的车，则该车出栈；同时若Wait队列不为空，则队列元素依次出队,

并入栈；若

要开走的车不是栈顶的车，则让该车后面的车入栈到Tmp栈，等该车走后，先让Tmp的元素入

栈，若Wait队

列中还有元素，则入栈队列首的元素.

4.车以进入时的分钟数为编号入栈，如8:40分有车入栈，则栈元素的名称为：480+40=520.最

大的车牌号

码是23:59=1380+59=1439,确保了我们的栈和队列的ElemType为int时候不会溢出.

二.概要设计：

1.下面是栈的ADT抽象数据类型定义：

抽象数据类型表达

ADTStack{

数据对象：D={Ai|Ai<=ElemSet,i=1,2,3,...};

数据关系：R1={<Ai-1,Ai>|Ai-1,Ai<=D,i2,3,...}

基本操作：

lnitStack(&S);

操作结果：初始化栈.

DestroyStack(&S);

初始条件：栈已经存在.

操作结果：销毁栈.

ClearStack(&S);

初始条件：栈已经存在.

操作结果：清除栈；置栈为空.

IsEmptyStack(S);

初始条件：栈已经存在.

操作结果：若栈为空，返回TRUE;否则返回FALSE.

GetStackLength(S);

初始条件：栈已经存在.

操作结果：返回栈元素的个数，即栈的长度.

Push(&S,e);

初始条件：栈已经存在.

18/29

操作结果：把元素e压入栈S;栈长度加一.

Pop(&S,&e);

初始条件：栈已经存在.

操作结果：把栈顶的元素弹出；栈长度减一.

StackTraverse(S,void(*visit)());

初始条件：栈已经存在且不为空.

操作结果：遍历栈，执行visit操作.

GetStackTop(S,&e);

初始条件：栈存在且不为空.

操作结果:把栈顶部元素存储到e中.

}ADTStack;

2.下面是队列的ADT抽象数据类型表达：

抽象数据类型表达

ADTQueue{

数据对象:D={Ai|Ai<=ElemSet,i=1,2,3,...);

数据关系：R仁{〈AiT,Ai>|Ai-1,Ai<=D,i=2,3,...];

基本操作：

InitQueue(&Q)

操作结果：初始化队列.

DestroyQueue(&Q)

初始条件：队列已经存在.

操作结果：销毁队列.

ClearQueue(&Q)

初始条件：队列已经存在.

操作结果：清除队列容；置队列为空.

IsEmptyQueue(Q)

初始条件：队列已经存在.

操作结果：若队列为空队列，返回TRURE；否则返回TRUE.

GetLength(0)

初始条件：队列已经存在.

操作结果：返回从队列元素个数.

Peek(Q,&e)

初始条件：队列已经存在且不为空.

操作结果：返回队列的队列头元素，也就是最先入列的元素.

EnQueue(&Q,e)

初始条件：队列已经存在.

操作结果：元素e入列，队列长度加一.

DeQueue(&Q,&e)

初始条件：队列已经存在且不为空.

操作结果：队列头元素出列，队列长度减一.

QueueTraverse(Q,void(*visit)())

初始条件：队列已经存在且不为空.

操作结果：遍历队列,执行visit操作.

)ADTQueue;

19/29

3.定义停车场的ADT抽象数据类型为：

ADTParkModel{

数据对象：D={StackPark,StackTmp,QueueWait,intParkSize};

数据关系：R1={}

基本操作：

InitParkModeI(&P);

操作结果：初始化ParkModeI停车场模型，初始化Park,Tmp和Wait,初始化size(停

车场长度).

InitParkTime(&time);

操作结果：当车入停车场时，初始化进停车场的时间，以分钟为单位;把这个时间作

为车的编号.

GetParkedTime(&time);

操作结果：当车出停车场时，获取当前时间，和汽车的时间进行比较，得出这个差值.

EnterPark(&P);

初始条件：停车场已初始化.

操作结果：车入停车场.若停车场已满，则入等候场.

LeavePark(&P,&time,number);

初始条件：停车场已经存在.number是对车的依次编号.

操作结果：车出停车场.若车是停车场的最后一个，则出场；否则把它后面的车入临

时场后出场.

CIearPark(&P);

初始条件：停车场已经存在.

操作结果：情况停车场，所有的车都出场，清空临时场和等候场.

DestroyPark(&P);

初始条件：停车场已经存在.

操作结果：毁坏停车场.

}ADTParkModeI;

三.详细设计：

1.定义Park的struct如下：

structParkModel{

Stackpark;//停车场主栈

Stacktmp;//非栈顶车出场时的临时栈.

Stackwait;//Park满时的等候队列.

intsize;//停车场的容量.

1

2.InitParkModeI初始化Park设计:

InitParkModeI(&P)

(

〃初始化park

//初始化tmp

〃初始化wait

//初始化size

20/29

)

3.InitParkTime初始化时间

InitParkTime(&time)

(

//获取当前日期

//获取时和分

//转化成分，赋值给time

)

4.GetParkedTime获取车停留时间

GetParkedTime(&time)

(

//注:time存储的是车入场的分钟，

//调用InitParkTime(&tmpTime)获取当前分钟

//把time和tmpTime的差值赋值给time.

)

5.EnterPark车入停车场

EnterPark(&P)

(

//根据park长度和size判断是否停车场已满

〃若已满,time入wait队列

//否则time入停车场栈

)

6.LeavePark车出停车场

LeavePark(&P,&time,number)

(

〃若Park为空，返回

//number是车编号，time是车时间

〃若number是栈长度，则说明是栈顶车出场，

〃则让该车出场并计费，

//然后判断wait队列是否有车等候，若有车则入场

//若number小于栈长度，则说明是栈中间车出场，

//则让number后面的车入tmp栈，

//让该车出场并计费，

//然后让tmp栈车入场，

〃接着判断wait队列是否有车等候，若有车则入场

)

7.ClearPark清场

CIearPark(&P)

(

〃若Park为空，返回

〃若Park不为空，

//清空停车场，并计费

//清空赁市场，并计费

〃清空等候队列

21/29

)

8.DestroyPark销毁停车场

DestroyPark(&P)

(

//清空停车场

//销毁停车场

四.调试分析:

五.测试结果:

六.编码实现*/

#incIude<stdio.h>

#incIude<stdIib.h>

#include<dos.h>

#include<conio.h>

/*定义停车场的容量宏*/

#ifndef_SizeOfParkModeI

#define_SizeOfParkModeI50

#endif

/*包含栈和队列的结构实现*/

#include"DSLib.h"

/*定义停车场的结构*/

typedefstruct(

Stackpark;/*停车场主栈*/

Stacktmp;/*临时栈*/

Queuewait;/*等候队列*/

intsize;/*停车场容量*/

}ParkModeI;

/*初始化ParkModeI停车场模型，初始化Park,Tmp和Wait,初始化size(停车场长度).*/

voidInitParkModeI(ParkModeI*P){

/*初始化park*/

InitStack(&((*P).park));

/*初始化tmp*/

InitStack(&((*P).tmp));

/*初始化wait*/

InitQueue(&((*P).wait));

/*初始化size*/

(*P).size=_SizeOfParkModeI;

1

/*当车入停车场时，初始化进停车场的时间，以分钟为单位;把这个时间作为车的编号.*/

22/29

voidlnitParkTime(int*time){

/*获取当前日期*/

structtimenow;

/*获取时和分已经秒*/

gettime(&now);

/*转化成分，赋值给time*/

(*time)二now.ti_hour*60+now.ti_min；

)

/*当车出停车场时，获取当前时间，和汽车的时间进行比较，得出这个差值.*/

voidGetParkedTime(int*time)

(

intnow=0,tmp=0;

/*注：time存储的是车入场的分钟，

调用InitParkTime(&tmpTime)获取当前分钟*/

InitParkTime(&now);

/*把time和tmpTime的差值赋值给time.*/

tmp=now~(*time);

/*若跨了24小时*/

if(tmp<0)

(

now+=24*60-(*time);

(*time)=now；

1

/*若未跨24小时*/

eIse

(*time)=tmp;

return;

)

/*车入停车场.若停车场已满，则人等候场.*/

voidEnterPark(ParkModeI*P)

(

inttime=1;

BOOLisFull=FALSE;

InitParkTime(&time);

/*根据park长度和size判断是否停车场已满*/

if(GetStackLength((*P).park)>=(*P).size)

isFull=TRUE;

/*若已满，time入wait队列*/

if(isFull==TRUE)

EnQueue(&((*P).wait),time);

/*否则time入停车场栈*/

eIse

Push(&((*P).park),time);

23/29

)

return;

)

/*车出停车场.若车是停车场的最后一个，则出场；否则把它后面的车入临时场后出场.*/

voidLeavePark(ParkModeI*P,int*time,intnumber)

(

inttmp=0,count=0,eIem=0;

/*若Park为空，返回*/

if(P=NULL||IsEmptyStack((*P).park)二二TRUE)

return;

count=GetStackLength((*P).park);

/♦number是车编号，time是车停留时间

若number是栈长度，则说明是栈顶车出场，*/

if(count<=number)

{

/*则让该车出场并计费，*/

Pop(&((*P).park),&tmp);

GetParkedTime(&tmp);

(*time)二tmp;

/*然后判断wait队列是否有车等候，若有车则入场*/

if(IsEmptyQueue((*P).wait)二二FALSE)

(

DeQueue(&((*P).wait),&tmp);

EnterPark(P);

1

)

/*若number小于栈长度，则说明是栈中间车出场，*/

eIse

(

/*则让number后面的车入tmp栈,*/

for(tmp=0;tmp<count-number;tmp++)

(

Pop(&((*P).park),&elem);

Push(&((*P).tmp),elem);

)

/*则让该车出场并计费，*/

Pop(&((*P).park),&tmp);

GetParkedTime(&tmp);

(*time)=tmp;

/*然后让tmp栈车入场，*/

for(tmp=0;tmp<count-number;tmp++)

Pop(&((*P).tmp),&elem);

Push(&((*P).park),eIem)；

24/29

)

/*然后判断wait队列是否有车等候，若有车则入场*/

if(IsEmptyQueue((*P).wait)二二FALSE)

(

DeQueue(&((*P).wait),&tmp)；

EnterPark(P);

)

1

)

/*情况停车场，所有的车都出场，清空临时场和等候场.*/

voidCIearPark(ParkModeI*P)

(

intcount=0,tmp=0,time=0;

/*若Park为空，返回*/

if(P=NULL||IsEmptyStack((*P).park)=TRUE)

return;

count=GetStackLength((*P).park);

/*若Park不为空，

清空停车场，并计费*/

for(tmp=count;tmp>0;tmp―)

(

LeavePark(P,&time,tmp);