数据结构与算法应用课程设计.doc

数据结构与算法应用综合课程设计要求与指导数据结构是一门实践性很强的课程，只靠读书和做习题是不能提高实践能力的，尤其是在数据结构中要解决的问题更接近于实际。所以要求学生在学习过程中，结合实际问题进行相应的课程设计与实践，自己分析问题、设计数据结构和算法，再编写代码上机调试和测试程序，以达到解决实际问题，培养数据结构的应用能力与实践能力。一、 课程设计的要求1、熟练掌握各种数据结构的逻辑结构特性、存储结构与常用操作算法；2、能分析课程设计的相应题目，结合理论学习考虑用一种或多种数据结构来解决问题；3、能分析并设计在某种数据结构下解决问题的步骤即算法；4、熟练掌握面向对象程序设计思想方法与编译系统的使用方法，能较好地编写程序实现数据结构与算法，解决实际问题5、能较好地进行程序的静态检查与动态调试与测试6、能按要求写好课程设计报告二、 课程设计的目的1、深入理解和掌握书本上的理论知识，将书本上的知识变“活”2、理论与实践相结合，学会如何把书本上的数据结构和算法的知识用于解决实际问题，培养数据结构的应用能力和软件工程所需要的实践能力3、进行软件工作的规范训练，初次体会软件开发的一般简单过程4、培养团队合作精神和良好的科学作风以及沟通能力三、 课程设计的工作步骤1、明确课程设计小组构成与分工每一小组由2人组成，各同学可自由组合。每小组选择后面课程设计备选题目中的一个，共同完成问题分析和任务定义、数据类型和系统设计后，2人协商分工进行程序设计与调试。每个同学必须有明确而又互不相同的工作任务，并保证工作量一致。在课程设计中还要注意两人的协调与合作。2、问题分析和任务定义首先充分分析和理解问题，明确问题要求做什么，限制条件是什么，即明确“做什么”。如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么，是否接受非法的输入，对非法输入的回答方式是什么等等2、数据类型和系统设计1)逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并定义主程序模块和各抽象数据类型，画出模块之间调用关系图2)详细设计：定义相应的存储结构(写出数据存储结构的类型定义)并写出各过程和函数的算法3、3、编码实现和静态检查1)编码实现：把算法设计的结果用程序设计语言程序写出来。每个函数体，即不计首部和规格说明部分，一般不要超过40行，最长不得超过60行，否则应分成更小的函数。要控制IF语句连续嵌套的深度。首先可以在一个程序文件中实现，然后做成头文件形式的软件模块，随着工作的积累，这些成熟的软件模块也会越来越丰富，当常用的数据结构都以抽象数据类型的形式实现以后，其他问题编程的工作也就会比较顺手了。抽象数据类型的实现作为头文件必须包含进工程文件。2) 静态检查：通过阅读或给别人讲解自己的程序深入全面理解程序逻辑，检查是否有明显错误，加入一些注释。可用简单的数据试人工运行程序，此时数据规模应比较小，而且考虑到各种情况，如空表、空二叉树、一个结点二叉树、两个结点二叉树等各种情况。应访遍程序的各条路径(即各分支的情况)。通过静态检查程序由于疏漏而产生的错误，也可为接下去的动态调试找到一种“程序感觉”4、上机准备和上机调试首先，应熟悉Microsoft Visual C+5.0/6.0的开发环境。在运行时可能发生以下三种类型的错误：语法错误、连接错误、运行错误前两种错误一般由系统提示指出，一般按语言的语法和系统的环境要求加以改正即可。第三种错误与算法和程序有关，大致又有两种情况：一种是因为存储结构使用不当引起的，例如最常见的无效指针和数组下标越界等；另一种是纯粹的逻辑性错误，如程序不能正常终止、输出与问题的要求有出入等，在很大程度上是由于控制条件考虑不周所至。这类错误是初学数据结构编程者最易犯的毛病，而当运行出现这类错误时又往往感到束手无策。为了从程序中忙地排除这类错误，首要是能对错误的出处准确定位，常用的简便办法是利用集成环境提供的Debug功能加以定位。在程序中适当位置临时加入一些反映调试信息的输出语句，以此来反映动态运行善有时也比较有效。调试中出现的警告性提示，也不能轻易放过，必须究其原因排除之。对某一组数据运行成功，并不意味程序正确。在进行整个程序的联调时，要特别注意对多组数据模型进行试验，并分别选择几种具有一般性和特殊性的数据进行调试，用测试数据(包括正确的数据和错误的数据)测试程序是否能得到正确结果，程序健壮性(容错处理)怎样等？因为本材料不是讲解Microsoft Visual C+的专门手册性读物，有关Visual C+本身的知识内容的讲解，请读者参考相关的书籍。可带一本C+程序设计教材或Visual C+操作手册，进行调试。5、总结和整理课程设计报告课程设计报告应包括以下几部分内容1）题目、姓名、学号、完成日期，见封面附件2）问题描述包括题目内容，基本要求，测试数据3）需求分析： 输入的形式和输入值的范围 输出的形式 程序所能达到的功能 测试数据要求4）概要设计：抽象数据类型的定义，各程序模块之间的调用关系，各类之间的继承关系5）详细设计定义所有类，写出每个操作的算法，主程序也可按需要写出算法，函数调用关系图6）调试分析：遇到的问题及解决的方法 经验与体会7）用户使用说明简单说明怎样使用你的程序，特别是对使用中应注意的问题加以说明8）测试结果：列出输入输出结果附录：源程序本示例中的分析、描述与实现均是在以C语言的形式，用到了C+对C的扩展，代码是在VC+6.0中调试成功的。有些同学反映主程序不会写，大家可在示例程序中了解简单主程序的写法，并在这里通过两个例子体会主函数如何调用各模块，从而统一协调地完成要求的。需要强调的是决不是仅有此一种方法，事实上，在主函数中常作的类似的事情都还可以在主程序中写成其他函数，以让主函数所作的主要工作能更清晰。9)总结：详细注明小组中每位同学负责的工作、课程设计过程的收获、遇到问题以及解决问题的思路和方法、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对数据结构课程的认识等内容10)附录：将程序清单及程序附上四、 评分办法：课程设计成绩=上机考勤10%+程序及其调试40%(程序的规范性10%、功能实现情况20%、程序调试能力10%)+设计报告质量50%(流程规范15%，设计合理15%，报告撰写15%，分工合理5%)程序的规范：应养成良好的程序书写规范，需要注意：注释，命名规则，格式等。源代码作为设计报告附件提交。流程规范性：报告中显示出来的设计过程按规范的步骤进行：问题分析、系统设计、代码编写、测试与调试，每个步骤均在报告中描述清楚。设计合理性：在查询参考文献、问题分析的基础上，认真完成系统的设计，模块设计合理、数据类型设计合理、类的设计合理、算法设计合理报告撰写：认真书写设计报告，要求：逻辑合理、内容翔实、格式规范、排版工整、语句通顺。无设计报告者以及严重抄袭他人设计者，成绩为不及格。五、 课程设计报告示例：本材料以一个简单的题目来说明课程设计报告的格式与内容，每一个题目都不同，每个同学课程设计后的心得体会与收获与不同，请注意准确完整地描述课程设计的步骤与成果。数据结构课程设计报告 封面(见封面模板)一、问题描述1、题目内容：利用链表表示家电信息，实现链表的初始化、创建表、插入、 删除、更新数据、打印、查询以及链式结构的有序表与文件之间的数据转换。2、基本要求：由用户输入一组数据包括家电名称、品牌型号、单价、及数量， 以结点中单价值的非减序列体现着有序性。3、测试数据：链表初始数据为彩电、TCL超平29英寸、2100元、234台，冰箱、海尔、1800元、 302台，洗衣机、小鸭、1200元、105台二、需求分析1、本程序用以实现家电信息的初始化、创建表、插入、删除、更新数据、打印、查询以及有序表与文件之间的数据转换。2、程序运行后显示提示信息，由用户输入家电相关信息来创建有序链表。3、在创建好后，用户可根据需要选择所要的操作。4、数据信息应包含家电名称、品牌型号、单价、及数量。三、概要设计为实现上述程序功能，应以有序链表表示家电信息。为此需要有序表和结构体两个 抽象数据类型。1、结构体的抽象数据类型定义为： ADT goods 数据对象：d=char name10; char sname10; int price; int num; ADT goods 2、有序表的抽象数据类型定义为： ADT OrderedList lnode *listcreate_l(goods *a,int n) 初始条件： 运行结果： ADT OrderedList 数据关系：同属于一个结点 基本操作：lnode *listcreate_l(goods *a,int n) 操作结果：构造一个有序链表。 node *listinsert_l(lnode *l,goods a) 初始条件：有序链表已经存在。 操作结果：插入一个结点，此结点信息为a。 lnode *listdelete_l(lnode *l,goods e) 初始条件：有序链表已经存在。 操作结果：删除e结点。 lnode *listchange_l(lnode *l,goods e) 初始条件：有序链表已经存在。 操作结果：用e的信息更换有序表中与e同名的结点的信息。 void listsearch_l(lnode *l,char *sname) 初始条件：有序链表已经存在。 操作结果：查询结点中名为sname的结点的相关信息。 void listtraverse_l(lnode *l) 初始条件：有序链表已经存在。 操作结果：打印有序链表中的信息。 3、本程序包含三个模块： 主程序模块：进行简要说明 结构体模块：进行简要说明 有序表模块：进行简要说明模块之间的关系如图所示：(加一模块结构图)四、详细设计1、元素类型、结点类型、指针类型。 typedef struct char name20; char sname20; int price; int num; goods;2、有序表类型。 typedef struct lnode goods data; struct lnode *next; lnode,*linklist;部分操作实现的伪代码算法如下：1）lnode *listcreate_l(goods *a,int n) for (int k=0;kn;+k) for (int j=0;jn-k-1;j+) if (aj.priceaj+1.price) goods b; strcpy(,); strcpy(b.sname,aj.sname); b.price=aj.price; b.num=aj.num; strcpy(,aj+1.name); strcpy(aj.sname,aj+1.sname); aj.price=aj+1.price; aj.num=aj+1.num; strcpy(aj+1.name,); strcpy(aj+1.sname,b.sname); aj+1.price=b.price; aj+1.num=b.num; /if /for /倒用起泡法对结构体数组以price为关键字进行排序lnode *l=NULL;lnode *s;for (int i=0;,); strcpy(s-data.sname,ai.sname); s-data.price=ai.price; s-data.num=ai.num; s-next=l;l=s; return l; /创建链表并返回头指针 /listcreate_l()2）lnode *listinsert_l(lnode *l,goods a)lnode *q=l;lnode *r=l; lnode *p=new lnode; strcpy(,); strcpy(p-data.sname,a.sname);p-data.price=a.price;p-data.num=a.num; /把goods结构体的内容复制给结点指针pwhile (a.priceq-data.price&q)r=q;q=q-next; if (q=l)p-next=l;l=p; /p插在头结点之前elseif (q=NULL) r-next=p;p-next=NULL;/p插在最后一个结点后面else r-next=p;p-next=q; /p插在中间的一般情况 return l; /listinsert_l()3）lnode *listdelete_l(lnode *l,goods e)lnode *p=l; lnode *r=l; while (strcmp(p-data.sname,e.sname)&p) r=p; p=p-next; if (p=l)l=p-next; /删除结点为头结点else if (p-next=NULL) r-next=NULL; /删除结点为最后一个结点else r-next=p-next; /删除结点为一般情形 if (!p) cout删除项目不在产品信息中，请确认后在输入，谢谢！data.sname) p=p-next; if (p)strcpy(,); strcpy(p-data.sname,e.sname); p-data.price=e.price; p-data.num=e.num; /用e的信息替换结点p的信息else cout更新信息与产品信息中的所有规格都不匹配，确认后在输入，谢谢！data.sname) p=p-next; data.sname data.price data.numnext;i+; /用i记录产品总类个数infiendl;while(l) data.sname data.priceyuan data.num台endl; data.sname data.price data.num next; /打开d：information并从中写入信息 /listtraverse_l()打印信息4、主函数的算法： void main() cout进入程序请按1，退出请按0m; while (m) cout创建请按1；其它操作请按2n; switch (n) case 1: cout请输入产品种类数量和相关信息：n;a=new goodsn;for (int i=0;ai.sname ai.priceai.num;lnode *l; l=listcreate_l(a,n);listtraverse_l(l); break; case 2: cout插入请按3；删除请按4；更新请按5；查询请按6;打印请按7.n;a=new goodsn;for (int i=0;ai.sname ai.priceai.num; /利用文件流创建文件流对象以读方式 lnode *l; /打开d：information并从中读入信息 l=listcreate_l(a,n); int j;cinj; switch (j)case 3: cout请输入要插入产品的相关信息：m.snamem.pricem.num;lnode *p=listinsert_l(l,m);listtraverse_l(p);break; case 4: cout请输入要删除项目的相关信息：m.snamem.pricem.num;lnode *p=listdelete_l(l,m);listtraverse_l(p);break; case 5: cout请输入要更改项目的相关信息：m.snamem.pricem.num;lnode *p=listchange_l(l,m);listtraverse_l(p);break; case 6: cout请输入要查询项目的名称：m;listsearch_l(l,m);break; case 7: cout公司库存产品相关信息如下：endl;listtraverse_l(l);break; /switch() /switch() /while() cout进入程序请按1，退出请按0m; cout查看最新产品信息请到d：information(2).endl; /main()五、调试分析：调试过程中经常出现运行时出现错误提示而没有结果的情况，经检查是指针处理的问题六、使用说明 程序运行后用户根据提示信息输入产品信息，按照提示运行就可以了。七、测试结果 所采用的测试数据和测试结果如下：进入程序请按1，退出请按01创建请按1；其它操作请按21 请输入产品种类数量和相关信息：3冰箱 海尔 1800 302 彩电 TCL超平29英寸 2100 234 洗衣机 小鸭 1200 105 此是d盘的information的内容为：3洗衣机 小鸭 1200yuan 105台 洗衣机 小鸭 1200 105冰箱 海尔 1800yuan 302台 冰箱 海尔 1800 302彩电 TCL超平29英寸 2100yuan 234台 彩电 TCL超平29英寸 2100 234进入程序请按1，退出请按01创建请按1；其它操作请按22插入请按3；删除请按4；更新请按5；查询请按6;打印请按7.3请输入要插入产品的相关信息：DVD 康佳 1350 169 此是d盘的information的内容为：4 洗衣机 小鸭 1200yuan 105台 洗衣机 小鸭 1200 105DVD 康佳 1350yuan 169台 DVD 康佳 1350 169冰箱 海尔 1800yuan 302台 冰箱 海尔 1800 302 彩电 TCL超平29英寸 2100yuan 234台 彩电 TCL超平29英寸 2100 234进入程序请按1，退出请按01创建请按1；其它操作请按22插入请按3；删除请按4；更新请按5；查询请按6;打印请按7.4请输入要删除项目的相关信息：DVD 康佳 1350 169 此是d盘的information的内容为：3 洗衣机 小鸭 1200yuan 105台 洗衣机 小鸭 1200 105冰箱 海尔 1800yuan 302台 冰箱 海尔 1800 302彩电 TCL超平29英寸 2100yuan 234台 彩电 TCL超平29英寸 2100 234进入程序请按1，退出请按0 1创建请按1；其它操作请按22插入请按3；删除请按4；更新请按5；查询请按6;打印请按7.5 请输入要更改项目的相关信息：彩电 TCL超平29英寸 2000 153 此是d盘的information的内容为：3洗衣机 小鸭 1200yuan 105台 洗衣机 小鸭 1200 105冰箱 海尔 1800yuan 302台 冰箱 海尔 1800 302彩电 TCL超平29英寸 2000yuan 153台 彩电 TCL超平29英寸 2000 153进入程序请按1，退出请按0 1创建请按1；其它操作请按22插入请按3；删除请按4；更新请按5；查询请按6;打印请按7.6请输入要查询项目的名称：TCL超平29英寸彩电 TCL超平29英寸 2000 153进入程序请按1，退出请按01创建请按1；其它操作请按22插入请按3；删除请按4；更新请按5；查询请按6;打印请按7.7公司库存产品相关信息如下：洗衣机 小鸭 1200yuan 105台冰箱 海尔 1800yuan 302台彩电 TCL超平29英寸 2000yuan 153台进入程序请按1，退出请按00查看最新产品信息请到d：information.Press any key to continue八、课程设计总结： 请同学们根据自己在课程设计中的经验、教训和收获进行总结九、附录源文件清单xxxx.cpp-主程序xxx.h-头文件，内含类的定义xxx.cpp-类中各函数的实现程序文件六、 课程设计备选题目注：每个题目后面注明了该题目最多允许的人数题目一、约瑟夫环问题(1人)设计目的：掌握单向循环链表的建立；掌握单向循环链表的操作。问题描述：编号是1,2,n的n个人按照顺时针方向围坐一圈,每个人只有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。请设计一个程序求出出列顺序。设计要求：利用单向循环链表存储结构模拟此过程,按照出列的顺序输出各个人的编号。测试数据：m的初值为20,n=7,7个人的密码依次为3,1,7,2,4,7,4,首先m=6,则正确的输出是什么？输入数据：建立输入函数处理输入的数据,输入m的初值n,输入每个人的密码,建立单向循环链表。输出形式：建立一个输出函数,将正确的出列顺序输出。实现提示：程序运行后，首先要求用户指定初始报数的上限值，然后读入各人的密码。可设n=30。循环链表不需要头结点，请注意空表和非空表的区别。题目二、一元稀疏多项式计算器(2人)问题描述：设计一个一元稀疏多项式的简单计算器 基本要求：一元稀疏多项式简单计算器 的基本功能是： 1)输入并建立多项式2)输出多项式，输出形式为按指数升幂排列的各项的系数与指数序列，如： 3x3+5x8-2x15 的输出形式为：3 ，3，5，8，-2，153)多项式a与b相加，建立多项式a+b, 并输出结果4)多项式a与b相减，建立多项式a-b, 并输出结果选作内容：1)计算多项式在x处的值，x由键盘输入2)求多项式a和b相乘的结果3)多项式的输出形式为类数学表达式，例如：3x3+5x8-2x15的输出形式为3x3+5x8-2x15, 注意系数值为1或-1的项不要输出1，如x8, -x4等。题目三、运动会分数统计程序的设计 问题描述：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）设计要求：1). 可以输入各个项目的前三名或前五名的成绩；2)能统计各学校总分，3)可以按学校编号、学校总分、男女团体总分排序输出；4). 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。测试数据：要求使用全部合法数据、整体非法数据、局部非法数据进行程序测试，以保证程序的稳定。题目四：航空客运订票系统(不做) 问题描述：航空客运订票的业务活动包括：查询航线、客票预订和办理退票等。试设计一个航空客运订票系统，以使上述业务可以借助计算机来完成 基本要求：1) 每条航线所涉及的信息有：终点站名、航班号、飞机号、飞行周日(星期几)、乘员定额、余票量、已订票的客户名单(包括姓名、订票量、舱位等级1、2、3)以及等候替补的客户名单(包括姓名、所需票量)； 2) 作为示意系统，全部数据可以只放在内存中3) 系统能实现的操作和功能如下：A、查询航线：根据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额B、承办订票业务：根据客户提出的要求(航班号、订票数额)查询该航班票额情况，若尚有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于订票额，则需要重新询问客户要求。若需要，可登记排队候补；C、承办退票业务：根据客户提供的情况(日期、航班)，为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其它排队候补的客户。测试数据：自行指定实现提示：两个客户名单可分别由线性表和队列实现。为查找方便，已订票客户的线性表应按客户姓名有序，并且，为插入和删除方便，应以链表作存储结构。由于预约的人数无法预计，队列也应以链表作存储结构。整个系统需汇总各条航线的情况登录在一张线性表上，由于航线基本不变，可采用顺序存储结构，并按航班有序或按终点站名有序。每条航线是这张表上的一个记录，包含上述8个域、其中乘员名单域为指向乘员名单链表的头指针，等候替补的客户名单域为分别指向队头和队尾的指针。选作内容：当客户订票要求不能满足时，系统可向客户提供到达同一目的地的其它航线情况。还可充分发挥自己的想象力，增加你的系统的功能和其它服务项目。题目五：停车场管理 (2人)问题描述：设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 基本要求：以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”的信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 测试数据：设n=2，输入数据为：（A，l，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表示离去（Departure）；E表示输入结束（End）。 实现提示：需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 题目六：火车车厢重排问题(2人)详细问题见教材P107-109页设计要求：设计一个程序能够设定火车车厢数、缓冲轨数，在输入车厢号码序列后，能显示重排过程，如果没有解也要显示相应提示题目七：表达式求值问题(2人)问题描述：假设表达式只包含+、-、4个双目运算符，且运算符本身不具有二义性。设计要求：设计程序，要求输入一个表达式后，要能正确地解释表达式，并按四则运算规则输出最后的计算结果提示：先保存算符之间的优先关系，再采用课件上的算符优先法，进行计算选作：1)如果要求输出每一步的计算过程，应如何修改算法 2)如果运算符包含括号且括号可以嵌套，应如何修改算法题目八：迷宫问题(2人)问题描述：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。试设计一个程序，对任意设定的迷宫，求出条从入口到出口的通路，或得出没有通路的结论。基本要求：首先实现以链表作存储结构的栈类型，然后编写一个求解迷宫的程序。求得的通路以三元（I,j,d）的形式输出，其中：（I,j）指出迷宫中的一个坐标，d表示走到下一个坐标的方向。测试数据： 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0实现提示：可以二维数组存储迷宫数据，通常设定入点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中的任一位置，均可约定有东西南北四个方向可通。题目九、银行业务模拟：(2人) 问题描述：客户业务分为两种。第一种是申请从银行得到一笔资金，即取款或借款。第二种是向银行投入一笔资金，即存款或还款。银行有两个服务窗口，相应的有两个队列。客户到达银行后先排第一个队。处理每个客户业务时，如果属于第一种，且申请额超出银行现存资金总额而得不到满足，则立即排入第二队等候，直至满足时才离开银行，否则业务处理完后立即离开银行。每接待完一个第二种业务的客户，则顺序检查和处理（如果可能）第二个队列的客户，对能满足的申请者予以满足，不能满足者重新排到第二个队列的队尾。注意，在此检查过程中，一旦银行资金总额少于或等于刚才第一个队列中最后一个客户（第二种业务）被接待之前的数额，或者本次已将第二个队列检查或处理了一遍，就停止检查（因为此时已不可能还有能满足者）转而继续接待第一个队列的客户。任何时刻都只开一个窗口。假设检查不需要时间。营业时间结束时所有客户立即离开银行。写一个上述银行业务的事件驱动模拟系统，通过模拟方法求出客户在银行内逗留的平均时间。(与题目十一有类似之处，可参看题目十一)题目十、模拟操作系统中的进程调度(2人)问题描述：在多任务的操作系统（OS, Operating System）中，同一时间内存在多个程序（作业）同时执行，每个程序都以一个进程（process）来执行。但在计算机中通常只有一个处理机（CPU），为了保证所有程序都能执行，将所有待执行的作业插入进程队列（process queue），然后采用特定的进程调度算法进行调度。设计要求：1）（必做）时间片轮转算法操作系统中仅设置一个进程队列，记录所有待执行的作业。调度算法每次从队列中取出一个进程执行1个时间片（time slice），若进程执行完毕则退出内存。否则，将剩余时间片数减1后，重新插入作业队列末尾等待再次调度。新的进程到达时，插入队列尾。提示：每个进程在输入时，需描述下面的特征： 进程名（可用字符串或用整数简单表示） 到达时间（可用整数表示，以时间片为单位） 所需执行时间（整数，以时间片为单位）2）（选做）多级反馈队列调度算法为了快速响应短作业，同时可以执行长时间的作业，可以采用下面的调度算法。（1）OS设置有多个就绪队列（用Qi, i=1,2, . ,n表示），用于存放等待处理的进程，每个队列的优先权（priority）各不相同，从第一个到最后一个依次降低；（2）各个队列中进程执行的时间片大小各不相同，优先级越高的队列时间片越小，各个队列的时间片可按下面的规定：每一个队列时间片都比前一个队列时间片长1倍；（3）当一个进程进入内存后，先放入第一队列Q1末尾，按先来先响应的原则排队等待处理。该进程执行时若在规定的时间片内完成，则处理完毕，可撤离系统，若第一个时间片结束时尚未完成，则该进程转入第二队列Q2的末尾排队等待处理，依次下去，直至转到最后一个队列中。（4）仅当第i个队列Qi为空，才能调度第i+1队列Q(i+1)中的进程运行。如果第i队列中某进程正在执行，又有新进程进入第1i-1中任何队列，则此时正在运行的进程放回第i队列末尾，运行新进程。提示：多级反馈队列调度算法中的每个调度队列需说明：队列编号、优先权（可用整数表示）、时间片测试要求：进程不少于5个；最终要给出每个进程执行的起止时间、进程的执行顺序和整个服务所需的总的时间；队列的存储方式可采用循环队列、链队列。选作部分要求：队列不少于4个、时间片可选为1进程名ABCDE到达时间01234服务时间43424题目十一：排队问题的系统仿真(3人)用队列结构可以模拟现实生活中的很多排队现象。例如车站候车、医院候诊、等候理发等各种排队现象都可以通过程序进行仿真，并由此预测客流等多种经营指标，为经办人员的决策提供有价值的量化指标。现以理发馆的运作情况为模型，讨论排队问题的系统仿真。假设理发馆设有N把理发椅，可同时为N位顾客进行理发。顾客进门时，若有空闲理发椅，则立即入座理发；否则依次排队候理，一旦有顾客理完发离去时，排在队头的顾客便开始理发。假若理发馆每天连续营业T小时（只要有顾客等待，理发椅就不空），通过仿真的算法预测一天内顾客在理发馆内的平均逗留时间（包括理发所需时间和排队等候的时间）和排队等候理发的人数的平均值（排队长度的平均值）。为求出上述两个平均值，仿真程序要统计一天内每个顾客自进门到出门之间在理发馆逗留的时间和每个需排队等候的顾客进门排队时的队伍