您的当前位置:首页正文

数据结构实验指导书

2020-08-24 来源:好走旅游网
目 录

数据结构实验总体要求....................................................................................................................1 实验一 复数四则运算....................................................................................................................2 实验二 集合的并、交和差运算.....................................................................................................5 实验三 算术表达式求值演示.........................................................................................................9 实验四 哈夫曼编/译码器.............................................................................................................13 实验五 内部排序算法比较...........................................................................................................17 附录.................................................................................................................................................20

I

数据结构实验总体要求

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

数据结构是一门实践性较强的软件基础课程,它在计算机软件教学中起着承上启下的作用,通过实验使学生在基本数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计与实现等方面加深对课程的理解,同时在程序设计方法以及上机操作等基本技能和科学作风方面受到较严格的训练。

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

(1)基础理论方面:从数据结构的类定义和对象的使用,以及存储表示和操作的实现两个层次,系统地学习和掌握常用的基本数据结构(包括数组、顺序表、多项式、字符串、链表、栈与队列、树和森林、二叉树、堆、集合、图、搜索结构、索引结构、散列结构等)及其不同的实现,了解并掌握分析、比较和选择不同数据结构、不同存储结构、不同算法的原则和方法,为后续课程的学习打好基础。

(2)实验技术方面:系统地学习和掌握程序设计方法、程序设计风格及在不同的存储结构上实现的算法的设计思想,从中体会和掌握选择结构的方法和算法设计的思考方式及技巧,提高分析问题和解决问题的能力。

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

使学生了解计算机应用中数据对象的特性,学会在应用中,根据现实世界中的问题选择适当的数据逻辑结构和存储结构以及相应算法,并且培养基本的、良好的程序设计技能。

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

学时:数据结构课程总学时为72学时,其中实验18学时,占总学时25%。 教学形式:本课程实验为综合性实验。要求学生课前预习实验指导书,写出预习报告,指导教师应概述实验的原理、方法及仪器使用等,并作针对性指导,具体实验步骤和结果分析、处理由学生独立完成。

1

实验一 复数四则运算

一、实验目的

本次实验的主要目的在于帮助读者熟悉抽象数据类型的表示和实现方法。抽象数据类型需借助固有数据类型来表示和实现,即利用高级程序设计语言中已存在的数据类型来说明新的结构,用已经实现的操作来组合新的操作,具体实现细节则依赖于所用语言的功能。通过本次实习还可以帮助读者复习高级语言的使用方法。 二、实验内容

设计一个可进行复数运算的演示程序。要求实现下列六种基本运算:1)由输入的实部和虚部生成一个复数;2)两个复数求和;3)两个复数求差;4)两个复数求积,5)从已知复数中分离出实部;6)从已知复数中分离出虚部。运算结果以相应的复数或实数的表示形式显示。 三、实验仪器、设备及材料

586以上微机 四、实验原理

复数在计算机中的表示及复数的四则运算规则。 五、实验步骤

1. 问题分析和任务定义; 2. 数据类型和系统设计; 3. 编码实现和静态检查; 4. 上机准备和上机调试; 5. 总结和整理实验报告。 六、实验报告要求

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

1. 需求分析; 2. 概要设计;

2

3. 详细设计; 4. 调试分析; 5. 经验和体会等; 6. 测试结果; 7. 附录。 七、实验注意事项

实验前先预习,完成问题分析和任务定义的工作。 八、测试数据

对下列各对数据实现求和。 (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;应输出“-1.23-i4.16” (4)0, 9.7;-2.1, -9.7;应输出“-2.1” (5)7.7, -8;-7.7, 0;应输出“-i8” 九、选做内容

实现算数的其他运算,如:两个复数相乘、求共轭等。 十、实验要点

typedef struct { double real; double img; }ComplexNumber;

十一、部分参考代码

void CreateComplexNumber(ComplexNumber *c,double a,double b) { c->real=a; c->img=b;

3

return; }

void AddComplexNumber(ComplexNumber *c,ComplexNumber c1,ComplexNumber c2) { c->real=c1.real+c2.real; c->img=c1.img+c2.img; return; }

void SubComplexNumber(ComplexNumber *c,ComplexNumber c1,ComplexNumber c2) { c->real=c1.real-c2.real; c->img=c1.img-c2.img; return; }

void MultiComplexNumber(ComplexNumber *c,ComplexNumber c1,ComplexNumber c2) { c->real=c1.real*c2.real-c1.img*c2.img; c->img=c1.real*c2.img+c1.img*c2.real; return; }

void ConComplexNumber(ComplexNumber *c,ComplexNumber c1) { c->real=c1.real; c->img=c1.img*(-1); return; }

4

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

一、实验目的

本次实验的主要目的在于帮助学生熟练掌握线性表的基本操作在两种存储结构上的实现,其中以各种链表的操作和应用作为重点内容。 二、实验内容

编制一个能演示执行集合的并、交和差运算的程序。集合元素限定小写字母字符[‘a’… ’z’]。演示程序以用户和计算机的对话方式执行。 三、实验仪器、设备及材料

586以上微机 四、实验原理

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

1. 问题分析和任务定义; 2. 数据类型和系统设计; 3. 编码实现和静态检查; 4. 上机准备和上机调试; 5. 总结和整理实验报告。 六、实验报告要求

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

1. 需求分析; 2. 概要设计; 3. 详细设计; 4. 调试分析;

5

5. 经验和体会等; 6. 测试结果; 7. 附录。 七、实验注意事项

实验前先预习,完成问题分析和任务定义的工作。 八、测试数据

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

Set1∪Set2 = “aegimnpra”,Set1∩Set2 = “ae”,Set1 – Set2 = “gimnz” (2)Set1 = 012oper4a6tion89”,Set2 = “error date”,

Set1∪Set2 = “adeinoprt”,Set1∩Set2 = “aeort”,Set1 – Set2 = “inp” 九、选作内容

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

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

(4)集合的元素类型推广到其他类型,甚至任意类型 十、实验要点

typedef char ElemType;

typedef struct ElemNode{ ElemType elem; struct ElemNode *next; }ElemNode,*Set;

十一、部分参考代码

/*-------------FunctionList------------------------------ int LengthOf(Set src) 返回一个集合的长度

void CreateSet(Set dest) 创建一个新的字母集合 限定a-z void EmptySet(Set dest) 清空一个集合,保留头结点

6

void DestroySet(Set dest) 销毁集合

void DisplaySet(Set src) 打印集合的所有元素

void AddElem(Set dest,ElemType e) 在链表尾部追加一个元素 void DelElem(Set dest,ElemType e) 删除集合中的一个元素一次 int ExistElem(Set dest,ElemType e) 判断元素是否存在于集合中

void ContactSet(Set dest,Set src) 连接一个集合到另一个集合 void MulSet(Set dest,Set src1,Set src2) 集合交运算 void AddSet(Set dest,Set src1,Set src2) 集合并运算 void SubSet(Set dest,Set src1,Set src2) 集合差运算 int ExistSubset(Set dest,Set src) 子集判断

void NegSet(Set dest,Set src) 求补集 */

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

int LengthOf(Set src) { int i=0; while(src->next!=NULL) { i++; src=src->next; } return i;

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

void CreateSet(Set dest) { ElemType ch; Set p=dest,n; for(;;) { ch=getchar(); if(ch=='\\n') break; if(ch<97||ch>122) continue; n=(Set)malloc(sizeof(ElemNode)); p->next=n; n->elem=ch; n->next=NULL; p=n; } return;

7

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

void EmptySet(Set dest) { Set p,n; while(dest->next!=NULL) { p=dest; n=p->next; for(;n->next!=NULL;) { p=n; n=n->next; } free(n); p->next=NULL; }

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

void DestroySet(Set dest) { EmptySet(dest); free(dest); }//销毁集合

void DisplaySet(Set src) { Set p; if(src->next==NULL) { printf(\"φ\"); return; } p=src; do { p=p->next; putchar(p->elem); } while(p->next!=NULL); }//打印集合的所有元素

8

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

一、实验目的

本次实验的目的在于使读者深入了解栈和队列的特性,以便在实际间题背景下灵活运用他们;同时还将巩固对这两种结构的构造方法的掌握。 二、实验内容

设计一个程序,演示用算符优先法对算术表达式求值的过程。要求以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用教科书表3. 1给出的算符优先关系,实现对算术四则混合运算表达式的求值,并仿照教科书的例3-1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。 三、实验仪器、设备及材料

586以上微机 四、实验原理

应用栈先进后出的特点判定表达式中运算符号的优先关系,实现表达式求值运算。 五、实验步骤

1. 问题分析和任务定义; 2. 数据类型和系统设计; 3. 编码实现和静态检查; 4. 上机准备和上机调试; 5. 总结和整理实验报告。 六、实验报告要求

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

1. 需求分析; 2. 概要设计; 3. 详细设计;

9

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)计算器的功能和仿真界面 十、实验要点

#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10

typedef int ElemType;

typedef struct{ ElemType *base; ElemType *top; int stacksize; }Stack;

十一、部分参考代码

int IfEmptyStack(Stack S) { if(S.base==S.top) return 1;

10

return 0; }

void InitStack(Stack &S) { S.base=(ElemType *)malloc( STACK_INIT_SIZE * sizeof(ElemType) ); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return;

}//创建一个空栈

void EmptyStack(Stack &S) { S.top=S.base; return; }

void Push(Stack &S,ElemType &e) { if(S.top-S.base>=S.stacksize) { S.base=(ElemType

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

S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return;

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

void Pop(Stack &S,ElemType &e) { if(S.top==S.base) return; e=*--S.top; return;

}//弹出栈顶元素

ElemType GetTop(Stack &S) { if(S.top==S.base) return 0; return *(S.top-1); }//取栈顶元素

11

void ShowStack(Stack S) {

ElemType *p=S.base; while(p!=S.top)

printf(\"%d \ return; }//打印栈

12

实验四 哈夫曼编/译码器

一、实验目的

树是应用极为广泛的数据结构,也是这门课程的重点。它的特点在于非线性。本实验突出了数据结构加操作的程序设计观点,希望达到熟悉各种存储结构的特性,以及如何应用树解决具体问题(即原理与应用的结合)等目的。 二、实验内容

利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。要求一个完整的系统应具有以下功能:

(1) I:初始化(Initialization)。从终端读入字符集大小,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。

(2) E:编码(Encoding)。利用以建好的哈夫曼树(如不在内存,则从文件hfmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。

(3) D:译码(Decoding)。利用己建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。

(4) P:印代码文件(Print )。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。

(5) T:印哈夫曼树(Tree printing).将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。

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

586以上微机 四、实验原理

最优二叉树生成方法或哈夫曼编码原理 五、实验步骤

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

13

2. 数据类型和系统设计; 3. 编码实现和静态检查; 4. 上机准备和上机调试; 5. 总结和整理实验报告。 六、实验报告要求

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

1. 需求分析; 2. 概要设计; 3. 详细设计; 4. 调试分析; 5. 经验和体会等; 6. 测试结果; 7. 附录。 七、实验注意事项

实验前先预习,完成问题分析和任务定义的工作。 八、测试数据

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

(2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVORITE”。

字符 频度 字符 频度

186 N 57

A 64 O 63

B 13 P 15

C 22 Q 1

D 32 R 48

E 103 S 51

F 21 T 80

G 15 U 23

H 47 V 8

I 57 W 18

J 1 X 1

K 5 Y 16

L 32 Z 1

M 20

九、选作内容

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

14

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

typedef struct{ char index; int weight; int parent,lchild,rchild; }HTNode,*HuffmanTree;

typedef char **HuffmanCode;

十一、部分参考代码

void Select(HuffmanTree &HT,int m,int &s1,int &s2){ int i; for(i=1;;i++){

if(HT[i].parent==0){ s1=i; i++; break; } }

for(;;i++){

if(HT[i].parent==0){ s2=i; i++; break; } } for(;i<=m&&HT[i].parent==0;i++){ if(HT[i].weightvoid BuildHuffmanTree(HuffmanTree &HT,char *c,int *w,int n){ HuffmanTree p; int m,s1,s2,i; if(n<=1) return; m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));

15

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; } 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].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } }

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n){ char *cd; int f,c,i,start; HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(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].lchild==c) cd[--start]='0'; else cd[--start]='1'; HC[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd); }

16

实验五 内部排序算法比较

一、实验目的

本次实验的目的在于通常实验掌握排序的基本概念,熟悉各种内部排序的方法。 二、实验内容

通过随机数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。要求对以下6种常用的内部排序算法进行比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。待排序表的表长不小于1000;其中的数据要用伪随机数产生程序产生,至少要用5组不同的输入数据作比较。比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换计为3次移动);最后要对结果做出简单分析,包括对各组数据得出结果波动大小的解释。

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

586以上微机 四、实验原理

各种排序算法。 五、实验步骤

1. 问题分析和任务定义; 2. 数据类型和系统设计; 3. 编码实现和静态检查; 4. 上机准备和上机调试; 5. 总结和整理实验报告。 六、实验报告要求

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

1. 需求分析; 2. 概要设计;

17

3. 详细设计; 4. 调试分析; 5. 经验和体会等; 6. 测试结果; 7. 附录。 七、实验注意事项

实验前先预习,完成问题分析和任务定义的工作。 八、测试数据

由随机数产生器生成 九、选作内容

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

(2)对不同的输入表长作试验、观察检查两个指示相对于表长的变化关系。还可以对稳定性作验证 十、实验要点

#define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量 */ #define LISTINCREMENT 2 /* 线性表存储空间的分配增量 */ typedef struct {

ElemType *elem; /* 存储空间基址 */ int length; /* 当前长度 */

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

typedef int* SqList;

十一、部分参考代码

void Init(SqList &LA) {

int i=1;

srand(time(NULL)); for(;i<=1000;i++)

18

*(LA+i)=rand(); return; }

void LoadData(SqList &LA,SqList &LB) {

int i=1;

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

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

19

附录

实验报告书写样例

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

零.问题描述

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

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

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

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

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

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

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抽象数据类型定义: 抽象数据类型表达 ADT Stack{

数据对象:D={Ai|Ai<=ElemSet,i=1,2,3,...}; 数据关系:R1={|Ai-1,Ai<=D,i2,3,...}

20

基本操作: InitStack(&S); 操作结果:初始化栈. DestroyStack(&S); 初始条件:栈已经存在. 操作结果:销毁栈. ClearStack(&S); 初始条件:栈已经存在. 操作结果:清除栈;置栈为空. IsEmptyStack(S); 初始条件:栈已经存在. 操作结果:若栈为空,返回TRUE;否则返回FALSE. GetStackLength(S); 初始条件:栈已经存在. 操作结果:返回栈元素的个数,即栈的长度. Push(&S,e); 初始条件:栈已经存在. 操作结果:把元素e压入栈S;栈长度加一. Pop(&S,&e); 初始条件:栈已经存在. 操作结果:把栈顶的元素弹出;栈长度减一. StackTraverse(S,void(*visit)()); 初始条件:栈已经存在且不为空. 操作结果:遍历栈,执行visit操作. GetStackTop(S,&e); 初始条件:栈存在且不为空. 操作结果:把栈顶部元素存储到e中. }ADT Stack;

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

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

数据关系:R1={|Ai-1,Ai<=D,i=2,3,...}; 基本操作: InitQueue(&Q) 操作结果:初始化队列. DestroyQueue(&Q) 初始条件:队列已经存在. 操作结果:销毁队列. ClearQueue(&Q) 初始条件:队列已经存在. 操作结果:清除队列内容;置队列为空. IsEmptyQueue(Q) 初始条件:队列已经存在.

21

操作结果:若队列为空队列,返回TRURE;否则返回TRUE. GetLength(Q) 初始条件:队列已经存在. 操作结果:返回从队列元素个数. Peek(Q,&e) 初始条件:队列已经存在且不为空. 操作结果:返回队列的队列头元素,也就是最先入列的元素. EnQueue(&Q,e) 初始条件:队列已经存在. 操作结果:元素e入列,队列长度加一. DeQueue(&Q,&e) 初始条件:队列已经存在且不为空. 操作结果:队列头元素出列,队列长度减一. QueueTraverse(Q,void(*visit)()) 初始条件:队列已经存在且不为空. 操作结果:遍历队列,执行visit操作. }ADT Queue;

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

数据对象:D={StackPark,StackTmp,QueueWait,intParkSize}; 数据关系:R1={} 基本操作: InitParkModel(&P); 操作结果:初始化ParkModel停车场模型,初始化Park,Tmp和Wait,初始化size(停车场长度). InitParkTime(&time); 操作结果:当车入停车场时,初始化进停车场的时间,以分钟为单位;把这个时间作为车的编号. GetParkedTime(&time); 操作结果:当车出停车场时,获取当前时间,和汽车的时间进行比较,得出这个差值. EnterPark(&P); 初始条件:停车场已初始化. 操作结果:车入停车场.若停车场已满,则入等候场. LeavePark(&P,&time,number); 初始条件:停车场已经存在.number是对车的依次编号. 操作结果:车出停车场.若车是停车场的最后一个,则出场;否则把它后面的车入临时场后出场. ClearPark(&P); 初始条件:停车场已经存在. 操作结果:情况停车场,所有的车都出场,清空临时场和等候场. DestroyPark(&P); 初始条件:停车场已经存在. 操作结果:毁坏停车场. }ADT ParkModel;

22

======================================================================================== 三.详细设计:

1.定义Park的struct如下: struct ParkModel{ Stack park;//停车场主栈 Stack tmp;//非栈顶车出场时的临时栈. Stack wait;//Park满时的等候队列. int size;//停车场的容量. }

2.InitParkModel初始化Park设计: InitParkModel(&P) { //初始化park //初始化tmp //初始化wait //初始化size }

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是车时间

23

//若number是栈长度,则说明是栈顶车出场, //则让该车出场并计费, //然后判断wait队列是否有车等候,若有车则入场 //若number小于栈长度,则说明是栈中间车出场, //则让number后面的车入tmp栈, //让该车出场并计费, //然后让tmp栈车入场, //接着判断wait队列是否有车等候,若有车则入场 }

7.ClearPark清场 ClearPark(&P) { //若Park为空,返回 //若Park不为空, //清空停车场,并计费 //清空赁市场,并计费 //清空等候队列 }

8.DestroyPark销毁停车场 DestroyPark(&P) { //清空停车场 //销毁停车场 }

=============================================================================== 四.调试分析:

=============================================================================== 五.测试结果:

=============================================================================== 六.编码实现*/

#include #include #include #include

/*定义停车场的容量宏*/ #ifndef _SizeOfParkModel #define _SizeOfParkModel 50 #endif

/*包含栈和队列的结构实现*/ #include\"DSLib.h\" /*定义停车场的结构*/ typedef struct{

24

Stack park;/*停车场主栈*/ Stack tmp;/*临时栈*/ Queue wait;/*等候队列*/ int size;/*停车场容量*/ }ParkModel;

/*初始化ParkModel停车场模型,初始化Park,Tmp和Wait,初始化size(停车场长度).*/ void InitParkModel(ParkModel *P){ /*初始化park*/ InitStack(&((*P).park)); /*初始化tmp*/ InitStack(&((*P).tmp)); /*初始化wait*/ InitQueue(&((*P).wait)); /*初始化size*/ (*P).size=_SizeOfParkModel; }

/*当车入停车场时,初始化进停车场的时间,以分钟为单位;把这个时间作为车的编号.*/ void InitParkTime(int *time){ /*获取当前日期*/ struct time now; /*获取时和分已经秒*/ gettime(&now); /*转化成分,赋值给time*/ (*time)=now.ti_hour*60+now.ti_min; }

/*当车出停车场时,获取当前时间,和汽车的时间进行比较,得出这个差值.*/ void GetParkedTime(int *time) { int now=0,tmp=0; /*注:time存储的是车入场的分钟, 调用InitParkTime(&tmpTime)获取当前分钟*/ InitParkTime(&now); /*把time和tmpTime的差值赋值给time.*/ tmp=now-(*time); /*若跨了24小时*/ if(tmp<0) { now+=24*60-(*time); (*time)=now; } /*若未跨24小时*/ else (*time)=tmp; return;

25

}

/*车入停车场.若停车场已满,则入等候场.*/ void EnterPark(ParkModel *P) { int time=1; BOOL isFull=FALSE; InitParkTime(&time); /*根据park长度和size判断是否停车场已满*/ if(GetStackLength((*P).park)>=(*P).size) isFull=TRUE; /*若已满,time入wait队列*/ if(isFull==TRUE) EnQueue(&((*P).wait),time); /*否则time入停车场栈*/ else { Push(&((*P).park),time); } return; }

/*车出停车场.若车是停车场的最后一个,则出场;否则把它后面的车入临时场后出场.*/ void LeavePark(ParkModel *P,int *time,int number) { int tmp=0,count=0,elem=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); } } /*若number小于栈长度,则说明是栈中间车出场,*/

26

else { /*则让number后面的车入tmp栈,*/ for(tmp=0;tmp/*情况停车场,所有的车都出场,清空临时场和等候场.*/ void ClearPark(ParkModel *P) { int count=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); /*time stored the time the car stayed in the park.*/ } /*清空等候队列*/ ClearQueue(&((*P).wait)); return;

27

}

/*毁坏停车场.*/

void DestroyPark(ParkModel *P) { /*清空停车场*/ ClearPark(P); /*销毁停车场*/ DestroyStack(&((*P).park)); DestroyStack(&((*P).tmp)); DestroyQueue(&((*P).wait)); return; }

/*主调用函数*/ void main() { int c=1,number=1; ParkModel p; InitParkModel(&p); /*Menu*/ for(;c!=0;) { /*printChoice*/clrscr();{ puts(\"0.Exit.\"); puts(\"1.EnterPark.\"); puts(\"2.Display the Park.\"); puts(\"3.Display the Tmp.\"); puts(\"4.Display the Wait.\"); puts(\"5.LeavePark.\"); puts(\"6.Clear Park.\"); puts(\"7.Destroy Park.\"); puts(\"Please enter your choice:\"); scanf(\"%d\ } /*process*/switch(c) { case 0: break; case 1: EnterPark(&p); break; case 2: puts(\"The content of Stack park is:\"); StackDisplay(p.park); sleep(2);

28

break; case 3: puts(\"The content of Stack tmp is:\"); StackDisplay(p.tmp); sleep(2); break; case 4: puts(\"The content of Queue wait is:\"); QueueDisplay(p.wait); sleep(2); case 5: if(GetStackLength(p.park)<=0) { puts(\"no parked car.\"); sleep(1); break; } printf(\"Enter the number which you want to leave park[1,%d]\\n:\ scanf(\"%d\ LeavePark(&p,&number,number); printf(\"the car's parketed time is:%d\\n\ puts(\"The content of Stack park is:\"); StackDisplay(p.park); sleep(2); break; case 6: puts(\"Now clear the park:\"); ClearPark(&p); sleep(2); break; case 7: puts(\"Now destroy the park:\"); DestroyPark(&p); sleep(2); break; } } DestroyPark(&p); }

/*七.附录: struct time

{

29

unsigned char unsigned char unsigned char unsigned char }; */

ti_min; ti_hour; ti_hund; ti_sec; /* Minutes * /* Hours *

/* Hundredths of seconds * /* Seconds *

30

因篇幅问题不能全部显示,请点此查看更多更全内容