数据结构试验指导书

1、数据结构实验指导书、乙刖百数据结构是软件工程等专业的一门核心基础课程，也是很多高校考研专业课之一。它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好数据结构的关键。为了更好地配合学生实验，特编写实验指导

2、书。一、实验目的更好的理解算法的思想、培养算法设计、分析及程序调试能力。二、实验要求1、每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据及预期输出数据。2 、独立完成或在指导教师的帮助下，完成实验项目，得出正确的实验结果。3 、遵守实验室规章制度、不缺席、按时上、下机。4 、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣10分。5 、实验项目有一次未完成，扣5分，两次以上未完成者，平时成绩以零分记，不允许参加期末考试。三、实验环境VC+6.0或其它C+集成环境四、说明1 、本实验的所有算法中元素类型可以根据实际需要选

3、择。2 、实验题目中带*者为较高要求，学生可自选；其余部分为基本内容，必须完成，否则实验不合格。3 、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解，以便为考研做一定的准备。4、所有实验项目布置在在线评测系统平台（OnlineJudgeSystem）上，校内访问IP:59.73.73.133,每位学生需实名注册账号，并将完成的实验项目在平台上提交，平台能够实现自动评测。五、参考书目数据结构（C+斑言描述）王红梅等清华大学出版社DATASTRUCTUREWITHC+WilliamFord,WilliamTopp清华大学出版社（影印版）实

4、验一线性表的操作3实验二栈、队列的操作4实验三二叉树的操作5实验四图的操作12实验五查找14实验六排序15实验七综合实验16实验八停车场管理18实验九窗口管理19实验一线性表的操作实验类型：设计性实验要求：必修实验学时：4学时一、实验目的：基于线性表顺序表类和链表类，实现线性表的相关算法。二、实验要求：1、掌握线性表顺序表类和链表类的特点。掌握线性表的常见算法。2、在评测系统平台提交相应的实验项目，并提交电子版实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容：1 .设计一个静态数组存储结构的顺序表类，要求编程实现如下任务

5、：建立一个线性表，首先依次输人数据元素1,2,3,10,然后删除数据元素6,最后依次显示当前线性表中的数据元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过50个。2 .设计一个带头结点的单链表类，要求：(1)生成一个整数线性表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数(尽量利用已知的存储空间)。(2)设计一个测试主函数，实际运行验证所设计单链表类的正确性。3 .设计一个不带头结点的单链表类，要求：(1)不带头结点单链表类的成员函数包括取数据元素个数、插入元素、删除所有值为k的元素、取数据元素。(提示：要考虑在第一个数据元素结点前插入和删除第一个数据元

6、素结点时与在其他位置插入和删除其他位置结点时的不同情况。)(2)设计一个测试主函数，实际运行验证所设计循环单链表类的正确性。4 .设计一个仅设置尾指针的无头结点的循环单链表类，实现约瑟夫环问题；问题描述：设编号为1,2,n(n>0)个人按顺时针方向围坐-圈，每人持有一个正整数密码。开始时任意给出一个报数上限值m从第一个人开始顺时针方向自1起顺序报数。报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1起顺序报数.如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，并给出出列人的编号序列。测试数据：n=7,7个人的密码依次为3,1,7,2

7、,4,8,4初始报数上限值m=20*5.设计一个带头结点的循环双向链表类，要求：(1)带头结点循环双向链表类：获取元素个数、插入、删除、取数据元素等。(2)设计一个测试主函数，实际运行验证所设计循环双向链表类的正确性。*6.设计一个单链表实现一元多项式求和问题。要求：(1)设计存储结构表示一元多项式；(2)设计算法实现一元多项式相加。实验二栈、队列的操作实验类型：验证性实验要求：必修实验学时：2学时一、实验目的：基于栈类和队列类，实现栈和队列的常见算法，并结合线性表类实现有关串的操作。二、实验要求：1、掌握栈、队列、串的特点。掌握特殊线性表的常见算法。2、提交实验报告，报告内容包括：目的、要求

8、、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容：1. 堆栈类测试和应用问题。要求：(1) 设计一个主函数实现对顺序堆栈类和链式堆栈类代码进行测试。测试方法为：依次把数据元素1,2,3,4,5入栈，然后出栈堆栈中的数据元素并在屏幕上显示。(2) 定义数据元素的数据类型为如下形式的结构体：structDataTypechartaskname10;/任务名inttaskno;/任务号；设计一个包含5个数据元素的测试数据，并设计一个主函数实现依次把5个数据元素入栈，然后出栈堆栈中的数据元素并在屏幕上显示。2 .队列类测试和应用问题。要求：设计一个主函数对循环队

9、列类和链式队列类代码进行测试.测试方法为：依次把数据元素1,2,3,4,5入队，然后出队中的数据元素并在屏幕上显示。3 .设计串采用顺序存储结构，编写函数实现两个串的比较Compare(S,T)。要求比较结果有大于、等于和小于三种情况。* 4.设计算法利用栈类实现把十进制整数转换为二至九进制之间的任一进制输出。* 5.设计串采用静态数组存储结构，编写函数实现串的替换Replace(S,start,T,V),即要求在主串S中，从位置start开始查找是否存在子串T,若主串S中存在子串T,则用子串V替换子串T,且函数返回1;若主串S中不存在子串T,则函数返回0。并要求设计主函数进行测试。一个测试例

10、子为：S="Iamastudent,T=“student",V="teacher”。* 6.输入一个C+钺达式，实现表达式求值算法。注意问题1 .重点理解栈、队列和串的算法思想，能够根据实际情况选择合适的存储结构。2 .栈、队列的算法是后续实验的基础(树、图、查找、排序等)。实验三二叉树的操作实验类型：设计性实验要求：必修实验学时：2学时一、实验目的：基于教材给定的二叉树类，实现二叉树的有关操作。二、实验要求：1、掌握二叉树、哈夫曼树和树的特点。掌握它们的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设

11、计技巧、心得体会。三、实验内容：1 .设计实现二叉树类，要求：(1)编写一个程序，首先建立不带头结点的二叉链式存储结构的二叉树，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息，最后再测试查找函数和撤销函数的正确性。(2)实现二叉树层次遍历的非递归算法。(3)编写一主函数来验证算法实现。2 .假设二叉树采用链式存储结构进行存储，编写一个算法，输出一个二叉树的所有叶子结点，并统计叶子结点个数。*3.设计实现二叉线索链表类，要求：(1)编写一个程序，首先建立中序线索链表的二叉树，然后实现中序线索链表的遍历算法。(2)编写一主函数来验证算法实现。* 4.编写求二叉树

12、高度的函数。* 5.编写创建哈夫曼树和生成哈夫曼编码的算法。* 6.假设二叉树采用链式存储结构进行存储，试设计一个算法，输出从每个叶子结点到根结点的路径。* 7.假设二叉树采用链式存储结构进行存储，试设计一个算法，求二叉树的宽度(即具有结点数最多的层次上结点总数)四、程序样例1 .二叉树二叉链表结点声明template<classT>structBiNode(Tdata;BiNode<T>*lchild,*rchild;)；二叉链表类声明template<classT>classBiTreepublic:BiTree()root=NULL;无参构造函数，初始

13、化一棵空的二叉树BiTree(BiNode<T>*root);有参构造函数，初始化一棵二叉树，其前序序列由键盘输入BiTree();析构函数,voidPreOrder(BiNode<T>*root);voidInOrder(BiNode<T>*root);voidPostOrder(BiNode<T>*root);voidLeverOrder(BiNode<T>*root);private:释放二叉链表中各结点的存储空间前序遍历二叉树中序遍历二叉树/后序遍历二叉树层序遍历二叉树BiNode<T>*root;指向根结点的头指

14、针voidCreat(BiNode<T>*root);voidRelease(BiNode<T>*root););有参构造函数调用析构函数调用二叉树的层序遍历算法LeverOrdertemplate<classT>voidBiTree:LeverOrder(BiNode<T>*root)front=rear=0;采用顺序队列，并假定不会发生上溢if(root=NULL)return;Q+rear=root;while(front!=rear)q=Q+front;cout<<q->data;if(q->lchild!=NUL

15、L)Q+rear=q->lchild;if(q->rchild!=NULL)Q+rear=q->rchild;二叉树的构造函数算法BiTreetemplate<classT>BiTree:BiTree(BiNode<T>*root)creat(root);template<classT>voidBiTree二Creat(BiNode<T>*root)cin>>ch;if(ch='#')root=NULL;建立一棵空树elseroot=newBiNode<T>生成一个结点root->d

16、ata=ch;Creat(root->lchild);递归建立左子树Creat(root->rchild);递归建立右子树)二叉树的后序遍历递归算法PostOrdertemplate<classT>voidBiTree:PostOrder(BiNode<T>*root)递归调用的结束条件if(root=NULL)return;elsePostOrder(root->lchild);PostOrder(root->rchild);cout<<root->data;)后序递归遍历root的左子树后序递归遍历root的右子树/访问根结

17、点的数据域)二叉树的后序遍历非递归算法PostOrdertemplate<classT>voidBiTree:PostOrder(BiNode<T>*root)top=-1;采用顺序栈，并假定栈不会发生上溢while(root!=NULL|top!=-1)while(root!=NULL)top+;stop.ptr=root;stop.flag=1;root=root->lchild;)while(top!=-1&&stop.flag=2)root=stop-.ptr;cout<<root->data;)if(top!=-1)st

18、op.flag=2;root=stop.ptr->rchild;)PreOrder)二叉树前序遍历递归算法template<classT>voidBiTree:PreOrder(BiNode<T>*root)递归调用的结束条件if(root=NULL)return;elsecout<<root->data;PreOrder(root->lchild);PreOrder(root->rchild);/访问根结点的数据域/前序递U3遍历root的左子树前序递归遍历root的右子树)二叉树的前序遍历非递归算法PreOrdertemplate

19、<classT>voidBiTree:PreOrder(BiNode<T>*root)top=-1;采用顺序栈，并假定不会发生上溢while(root!=NULL|top!=-1)while(root!=NULL)(cout<<root->data;s+top=root;root=root->lchild;if(top!=-1)root=stop-;root=root->rchild;二叉树的析构函数算法BiTreetemplate<classT>BiTree:BiTree(BiNode<T>*root)Releas

20、e(root);voidBiTree二Release(BiNode<T>*root)if(root!=NULL)Releaseroot->lchild);释放左子树Releaseroot->rchild);释放右子树deleteroot;二叉树的中序遍历递归算法InOrdertemplate<classT>voidBiTree:InOrder(BiNode<T>*root)if(root=NULL)return;递归调用的结束条件elseInOrder(root->lchild);中序递归遍历root的左子树cout<<root

21、->data;/访问根结点的数据域InOrder(root->rchild);中序递归遍历root的右子树2 .线索链表线索链表结点声明enumflagChild,Thread;/枚举类型，枚举常量Child=0,Thread=1template<classT>structThrNodeTdata;ThrNode<T>*lchild,*rchild;flagltag,rtag;线索链表类声明template<classT>classInThrBiTree(public:InThrBiTree(ThrNode<T>*root);构造函数

22、，建立中序线索链表-InThrBiTree();析构函数，释放线索链表中各结点的存储空间ThrNode*Next(ThrNode<T>*p);/查找结点p的后继voidInOrder(ThrNode<T>*root);中序遍历线索链表private:ThrNode<T>*root;指向线索链表的头指针voidCreat(ThrNode<T>*root);构造函数调用voidThrBiTree(ThrNode<T>*root);构造函数调用;中序线索链表构造函数算法InThrBiTreetemplate<classT>InT

23、hrBiTree:InThrBiTree(ThrNode<T>*root)(Creat(root);pre=NULL;ThrBiTree(root);template<classT>voidInThrBiTree:Creat(ThrNode<T>*root)(cin>>ch;if(ch='#')root=NULL;建立一棵空树elseroot=newThrNode<T>生成一个结点，左右标志均置0root->data=ch;root->ltag=0;root->rtag=0;Creat(root-&g

24、t;lchild);递归建立左子树Creat(root->rchild);递归建立右子树template<classT>voidInThrBiTree二ThrBiTree(ThrNode<T>*root)if(root=NULL)return;ThrBiTree(root->lchild);if(!root->lchild)/对root的左指针进行处理root->ltag=1;root->lchild=pre;/设置pre的前驱线索if(!root->rchild)root->rtag=1;/对root的右指针进行处理if(pr

25、e->rtag=1)pre->rchild=root;设置pre的后继线索pre=root;ThrBiTree(root->rchild);中序线索链表查找后继的算法Nexttemplate<classT>ThrNode<T>*InThrBiTree:Next(ThrNode<T>*p)if(p->rtag=1)q=p->rchild;右标志为1,可直接得到后继结点elseq=p->rchild;/工作指针初始化，while(q->ltag=0)查找最左下结点q=q->lchild;returnq;)中序线索链

26、表查找后继的算法Nexttemplate<classT>voidInThrBiTree:InOrder(ThrNode<T>*root)(if(root=NULL)return;如果线索链表为空，则空操作返回p=root;while(p->ltag=0)查找中序遍历序列的第一个结点p并访问p=p->lchild;cout<<p->data;while(p->rchild!=NULL)当结点p存在后继，依次访问其后继结点(p=Next(p);cout<<p->data;)中序线索链表构造函数算法InThrBiTreet

27、emplate<classT>InThrBiTree:InThrBiTree(ThrNode<T>*root)(Creat(root);pre=NULL;ThrBiTree(root);)template<classT>voidInThrBiTree二Creat(ThrNode<T>*root)(cin>>ch;if(ch='#')root=NULL;建立一棵空树elseroot=newThrNode<T>生成一个结点，左右标志均置0root->data=ch;root->ltag=0;root

28、->rtag=0;Creat(root->lchild);递归建立左子树Creat(root->rchild);递归建立右子树)template<classT>voidInThrBiTree二ThrBiTree(ThrNode<T>*root)if(root=NULL)return;ThrBiTree(root->lchild);if(!root->lchild)/对root的左指针进行处理root->ltag=1;root->lchild=pre;/设置pre的前驱线索)if(!root->rchild)root->

29、;rtag=1;/对root的右指针进行处理if(pre->rtag=1)pre->rchild=root;设置pre的后继线索pre=root;ThrBiTree(root->rchild);)3 .哈夫曼树voidHuffmanTree(elementhuffTree,intw,intn)初始化/构造n棵只含有根结点的二叉树/n-1次合并在huffTree中找权值最小的两个结点i1和i2将i1和i2合并，则i1和i2的双亲是kfor(i=0;i<2*n-1;i+)(huffTreei.parent=-1;huffTreei.lchild=-1;huffTreei.r

30、child=-1;for(i=0;i<n;i+)huffTreei.weight=wi;for(k=n;k<2*n-1;k+)(Select(huffTree,i1,i2);huffTreei1.parent=k;huffTreei2.parent=k;huffTreek.weight=huffTreei1.weight+huffTreei2.weight;huffTreek.lchild=i1;huffTreek.rchild=i2;注意问题1 .注意理解有关树的各种递归算法的执行步骤。2 .注意字符类型数据在输入时的处理。3 .重点理解如何利用栈结构实现非递归算法。实验四图的操

31、作实验类型：设计性实验要求：必修实验学时：2学时一、实验目的：基于给定的图类，实现图的遍历等有关的操作。二、实验要求：1、掌握图的特点，利用图的邻接矩阵和邻接表的存储结构实现图的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容：1 .设计无向图的邻接矩阵图类，实现如下操作：(1)实现邻接矩阵的构造，深度优先、广度优先遍历；(2)实现最小生成树算法；(3)实现最短路径算法；(4)设计主函数，输入数据，测试各算法。2 .设计有向图的邻接表类，实现深度优先非递归遍历、广度优先遍历和拓扑排序，并设计主函数输入数

32、据进行测试。*3.设计邻接表类，设计一个算法，输出图G中从顶点u到顶点v的长度为l的所有简单路径。四、程序样例：请在下列邻接表和邻接矩阵的基础上自习添加其它任务1 .图的邻接表类structArcNode/定义边表结点(intadjvex;邻接点域ArcNode*next;template<classT>structVertexNode定义顶点表结点(Tvertex;ArcNode*firstedge;);constintMaxSize=10;图的最大顶点数template<classT>classALGraph(public:ALGraph(Ta,intn,inte)

33、;构造函数，初始化一个有n个顶点e条边的图ALGraph;析构函数，释放邻接表中各边表结点的存储空间TGetVex(inti);/取图中第i个顶点数据信息将图中第i个顶点的数据域置为value/在图中插入一个顶点，其编号为i,值为value删除图中第i个顶点/在图中插入一条边，其依附的两个顶点的编号为/在图中删除一条边，其依附的两个顶点的编号为深度优先遍历图广度优先遍历图存放顶点表的数组图的顶点数和边数voidPutVex(inti,Tvalue);voidInsertVex(inti,Tvalue);voidDeleteVex(inti);voidInsertArc(inti,intj);v

34、oidDeleteArc(inti,intj);voidDFSTraverse(intv);voidBFSTraverse(intv);private:VertexNodeadjlistMaxSize;intvertexNum,arcNum;.图的邻接矩阵类constintMaxSize=10;图中最多顶点个数template<classT>classMGraphpublic:构造函数，初始化具有n个顶点e条边的图i个顶点数据信息将图中第i个顶点的数据域置为value/在图中插入一个顶点，其编号为i,值为value删除图中第i个顶点/在图中插入一条边，其依附的两个顶点的编号为i和j

35、/在图中删除一条边，其依附的两个顶点的编号为i和j深度优先遍历图广度优先遍历图存放图中顶点的数组存放图中边的数组图的顶点数和边数MGraph(Ta,intn,inte);MGraph()析构函数TGetVex(inti);取图中第voidPutVex(inti,Tvalue);voidInsertVex(inti,Tvalue);voidDeleteVex(inti);voidInsertArc(inti,intj);voidDeleteArc(inti,intj);voidDFSTraverse(intv);voidBFSTraverse(intv);private:TvertexMaxSi

36、ze;intarcMaxSizeMaxSize;intvertexNum,arcNum;注意问题1 .注意理解各算法实现时所采用的存储结构。2 .注意区别正、逆邻接矩阵。实验五查找实验类型：设计性实验要求：必修实验学时：2学时一、实验目的：参照各种查找算法程序样例，实现查找的常见算法。二、实验要求：1、掌握各种查找算法的特点，测试并验证查找的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容：1,建立有序表，采用折半查找实现某一已知的关键字的查找。2 .利用折半查找算法在一个有序表中插入一个元素，并保持表

37、的有序性。3 .建立顺序表，统计表中重复元素个数。5 .根据给定的二叉排序树类的定义，验证二叉排序树的各个成员函数。4,哈希表类设计。要求：(1)哈希函数采用除留余数法，哈希冲突解决方法分别采用链地址法和线性探测法;(2)各自设计一个测试程序进行侧试。注意问题1 .注意理解折半查找的适用条件(链表能否实现折半查找？)。2 .注意理解静态查找、动态查找概念。3 .比较各种查找算法的各自特点，能够根据实际情况选择合适的查找方法。实验六排序实验类型：设计性实验要求：必修实验学时：2学时一、实验目的：利用各种排序算法，实现不同数据量时的排序算法所花时间的比较。二、实验要求：1、设计List类，实现各种

38、排序算法，并测试不同数据量时算法所花时间的比较。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容：设计List类，实现以下任务1、构造函数随机生成一组关键字序列2 、实现简单选择排序、直接插入排序和冒泡排序。3 、实现希尔排序算法。4 、实现快速排序算法(取第一个记录或中间记录作为基准记录)。5 、实现堆排序算法。* 6、快速排序的非递归算法。* 7、实现折半插入排序。* 8、采用链式存储实现简单选择排序、直接插入排序和冒泡排序。*9、双向起泡排序。在起泡排序中，若待排序序列为正序，只需一趟扫描，而待排序序列为反

39、序时，需进行n-1趟扫描。对于初始序列(94,10,12,18,42,44,67)只需扫描2趟，而对于初始序列(12,18,42,44,67,94,10)就需扫描6趟。造成这种不对称的原因：每趟扫描仅能使最小数据下沉一个位置，如果改变扫描方向，情况正好相反，即每趟从后往前扫描，都能使当前无序区中最大数据上浮一个位置。为了改变上述两种情况下的不对称性，可以在排序过程中交替改变扫描方向，称之为双向起泡排序。10、main中定义类对象，设计一个菜单，实现测试各个排序所花时间。注意问题：注意理解各种算法的思想、了解算法的适用情况及时间复杂度，能够根据实际情况选择合适的排序方法。随机函数rand(),初

40、始化随机发生器函数srand(time(0).实验七综合实验实验类型：综合性实验要求：必修实验学时：2学时一、实验目的：通过该实验是学生能够综合数据结构所学的知识，自行分析、设计，学会对一个实际问题分析、综合、设计的能力。二、实验要求1、掌握数据结构所学的内容，分析给定实验内容并设计出程序，然后运行，同时分析几种不同方法的效率。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容：选作项目1设计一个简单个人电话号码查询系统1 .问题描述：人们在日常中经常要查找某个人或某个单位的电话号码，本实验将实现一个简单的个人电话

41、号码查询系统，根据用户输入信息(例如姓名等)进行快速查询。2、基本要求(1)在外存上，用文件保存电话号码信息；(2)在内存中，设计数据结构存储电话信息；(3)提供查询功能；根据姓名实现快速查询；(4)提供其他功能，例如插入、删除、修改等；3、设计思想由于要管理的电话号码信息很多，而且要在程序运行后仍然保存电话号码信息，所以电话号码信息采用文件的形式存放在外存上。在系统运行时，要将电话号码信息从文件调入内存来进行查询等操作，为了接收文件中内容，要有一个数据结构与之对应，可以设计如下结构类型的数组来接收数据：constintmax=10structTeleNumber(Stringname;Str

42、ingphoneNumber;StringmobileNumber;Stringemail;Telemax;为了实现对电话号码的快速查询，可以将上述结构数组排序，以便应用折半查找，但数组中实现插入和删除操作的代价较高。如果记录频繁进行插入或删除操作，可以考虑采用二叉排序数组织电话号码信息，则查询和维护都能获得较高的时间性能；另外也可以考虑直接使用哈希表表结构存储电话号码信息，请同学根据实际情况自己选择。4、详细分析采用几种不同方法实现的效率。选作项目2利用单向链表，设计一个学生管理系统，能够实现学生信息管理及文件读写。主要功能有学生信息录入，数据输出，基本信息查询（按学号、姓名），成绩查询，数据统计，文件读写等。实验八停车场管理实验类型：综合性实验要求：必修实验学时：2学时【实验内容与要求】设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列(大门在最南端，最先到达的第一辆车停放在车场的最北端)，若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则