数据结构实验和课程设计指导书.docx

《数据结构实验和课程设计指导书.docx》由会员分享，可在线阅读，更多相关《数据结构实验和课程设计指导书.docx（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验和课程设计指导书数据结构课程组数据结构课程组广东工业大学计算机学院广东工业大学计算机学院20162016 年年目录第 1 章概述1.1课程、教材和实验课程、教材和实验1.2作业和实验安排作业和实验安排第 2 章算法设计实验和上机2.1数据结构习题概述数据结构习题概述2.2算法设计的上机作业要求算法设计的上机作业要求2.3算法设计上机作业算法设计上机作业第 3 章抽象数据类型的实现3.1 实验概要实验概要3.2 实验目的实验目的3.3 预习与参考预习与参考3.4 实验要求和设计指标实验要求和设计指标3.5 实验仪器设备和材料实验仪器设备和材料3.6 调试及结果测试调试及结果测试3.7

2、 考核形式考核形式3.8 实验报告要求实验报告要求3.9 思考题思考题3.10 示例示例第 4 章课程设计4.1课程设计概述课程设计概述4.2课程设计时间和内容课程设计时间和内容4.3课程设计步骤课程设计步骤4.4课程设计考核形式和评分标准课程设计考核形式和评分标准第 1 章概述1.1 课程、教材和实验课程、教材和实验数据结构是计算机科学的算法理论基础和软件设计的技术基础，主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现。数据结构不仅是计算机专业的核心课程，而且已成为其他理工专业的热门选修课。课程的教学要求之一是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯,其重要程度决不亚于

3、知识传授。因此，在数据结构的整个教学过程中,完成习题作业和上机实习是两个至关重要的环节。习题的作用在于帮助学生深入理解教材内容,巩固基本概念,达到培养良好程序设计能力和习惯的目的。从认知的程度划分，数据结构的习题通常可分为三类：基础知识题、算法设计题和综合实习题。基础知识题主要是检查对概念知识的识记和理解，一般可作为学生自测题。算法设计题的目的是练习对原理方法的简单应用，多数是要求在某种数据存储结构上实现某一操作，是数据结构的基础训练，构成了课外作业的主体。综合实习题则训练对知识的综合应用和软件开发能力，主要是针对具体应用问题，选择、设计、和实现抽象数据类型（ADT）的可重用模块，并以此为基础

4、开发满足问题要求的小型应用软件，应将其看作软件工程的综合性基础训练的重要一环，给予足够的重视。本实验指导书为采用自编教材的数据结构课程而编写：吴伟民等.数据结构.广东工业大学计算机学院，2016。数据结构是实践性很强的课程，光是“听”和“读”是绝对不够的。在努力提高课堂教学的同时，必须大力加强对作业实践环节的要求和管理。国内外先进院校一般都要求修读数据结构的学生每周应不少于 4 个作业机时，而且有一套严格的作业和实习规范和成绩评定标准，形成行之有效的教学质量保证体系。教学经验表明，严格实施作业和实习的规范，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将能起到显著的促进作用。数据结

5、构及其算法的教学难点在于它们的抽象性和动态性。虽然在书本教材和课堂授课（板书或投影胶片）中采用图示可以在一定程度上化抽象为直观，但很难有效展现数据结构的瞬间动态特性和算法的作用过程。我们自主研发的“C 程序可视化运行调试集成环境 AnyviewC”，以及基于 AnyviewC 开发的数据结构、C 程序设计、离散数学等课程的“编程作业与实验可视化网络平台”，打破了程序运行调试黑箱。学生可通过 AnyviewC 平台可在线编写和可视化调试自己编写的程序，并接受系统的实时自动测评，极大提高了学生程序设计训练的效率和效果。教师也可从繁重的书面作业批改工作中解脱出来，转到有针对性的现场指导和习题讲评上。

6、借助于互联网，AnyviewC 平台将实验室“全天候”和“跨时空”地拓广到每位学生个人的微机或移动终端上。1.2作业和实验安排作业和实验安排根据教学计划，本学期数据结构课程：1 课堂理论课 48 学时。2 实验室研讨课 16 学时。3 课程知识测验。主要题型是简答题，随课程进度完成测验。4 在“AnyviewC 编程作业与实验可视化网络平台”上机完成约 46 道必做题，学有余力的同学还可以加做选做题。5 抽象数据类型的实现。实现一组抽象数据类型，并对所采用的存储结构和相关操作的实现进行讨论。6 课程设计（一周综合性实验）。第 2 章算法设计实验和上机2.1数据结构习题概述数据结构习题概述数据结

7、构的习题分为“基础知识题”和“算法设计题”两类。在课程网站上，“基础知识题”主要供学生进行自测和复习之用，目的是帮助学生深化理解教科书的内容，澄清基本概念、理解和掌握数据结构中分析问题的基本方法和算法要点，为完成算法设计题做准备。“算法设计题”则侧重于基本程序设计技能的训练，相对于实习题而言，这类编程习题属于偏重于编写功能单一的“小”程序的基础训练，然而，它是进行复杂程序设计的基础，是本课程习题作业的主体和重点。各章的题量根据教学内容的多少和重要程度而定，几乎对教科书的每一小节都安排了对应的习题。2.2算法设计的上机作业要求算法设计的上机作业要求1使用 Anyview C 语言和算法书写规范写

8、出书面作业的算法（函数），作为上机前的准备。需要强调的是“算法的可读性”。初学者总是容易忽视这一点。算法不仅是开发程序的基础，还是一种在程序设计者之间交流解决问题方法的手段。因此，可读性具有头等的重要性。不可读的算法是没有用的，由它得到的程序极容易产生很多隐藏很深的错误，且难以调试正确。一般地说，宁要一个可读性好、逻辑清晰简单、但篇幅较长的算法，也不要篇幅较小但晦涩难懂的算法。算法的正确性力求在设计算法的过程中得到保证，然而一开始做不到这一点也没多大关系，可以逐步做到。算法设计的正确方法是：首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略逐一地解决子问题

9、，最后严格按照和使用本章后面提供的算法书写规范和类 C 语言完成算法的最后版本。按照规范书写算法是一个值得高度重视的问题。在基础训练中就贯彻这一规范，不但能够有助于写出“好程序”，避免形成一系列难以纠正且遗害无穷的程序设计坏习惯，而且能够培养软件工作者应有的严谨的科学工作作风。2对函数进行静态检查修改，形成准备上机的程序文本。多数初学者在编好程序后处于以下两种状态之一：一种是对自己的“精心作品”的正确性确信不疑；另一种是认为上机前的任务已经完成，查纠错误是上机的工作。这两种态度是极为有害的。事实上，非训练有素的程序设计者编写的程序长度超过 50 行时，极少不含有除语法错误以外的错误。上机动态调

10、试决不能代替静态检查，否则调试效率将是极低的。静态检查主要有两种方法，一是用一组测试数据手工执行程序（通常应先分模块检查）；二是通过阅读或给别人讲解自己的程序而深入全面地分析理解程序逻辑，在这个过程中再加入一些注解和断言。如果程序中逻辑概念清楚，后者将比前者有效。3在“Anyview C 编程作业与实验可视化网络平台”编辑提交程序，并在系统的自动测试和提示下，调试程序，直到能通过系统的测试。“Anyview C 编程作业与实验可视化网络平台”提供了程序可视化运行和调试的环境，为进行数据结构教学的师生提供了算法设计作业程序的可视化自动测试环境。可在该集成环境编辑 C源程序，并对其进行可视化运行、

11、分析和调试。通过设置断点、单步或变换速度的连续运行，可在多个窗口上动态观察程序执行时的数据变量的物理和逻辑 2D 或 3D 视图，使得程序运行期间本来不可见的程序对数据的处理过程和数据之间的动态抽象关系全部可视化。在提交算法设计作业程序时，系统自动进行可视化测试，评判作业程序的正确性。通过对比“标准结果视图”和“作业结果视图”，作业者可对自己的程序进行直观的分析和排错。关于该作业系统的使用，请参阅系统的帮助文档。在调试过程中可以不断借助系统的可视 DEBUG 的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，这时不应“苦思冥想”，而应动手确定疑点，通过修改程序来证实它或绕过它

12、。4在调试程序的过程中，做好调试笔记，记录心得体会。调试正确后，认真整理源程序及其注释，记录带有完整注释的且格式良好的源程序清单和结果。一道算法设计作业文档包括：（1）上机前编写并经过静态检查的程序文本；（2）调试笔记；（3）最后程序文本，及通过时间。第 3 章抽象数据类型的实现3.13.1 实验概要实验概要实验项目名称实验项目名称:抽象数据类型的实现抽象数据类型的实现实验项目性质实验项目性质:设计性实验设计性实验所属课程名称所属课程名称:数据结构数据结构实验计划学时实验计划学时:6 63.23.2 实验目的实验目的对某组具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此

13、基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。进而达到熟练地运用本课程中的基础知识及技术的目的。3.33.3 预习与参考预习与参考1确定要实现的抽象数据类型，并对基本操作做适当的选取和增加；2选择存储结构，并写出相应的类型定义；3设计各基本操作的实现算法，并表达为函数形式；4设计测试方案，编写主函数；5将上述 4 步的结果写成预习报告。3.43.4 实验要求和设计指标实验要求和设计指标以教材中讨论的各种抽象数据类型为对象，利用 C 语言的数据类型表示和实现其中某个抽象数据类型。可选的抽象数据类型如下表所列：编号编号抽象数据类型抽象数据类型基

14、本难度基本难度存储结构存储结构1 1栈和队列栈和队列1.01.0顺序顺序和和链接链接2 2线性表线性表1.01.0顺序顺序和和链接链接3 3哈希表哈希表1.11.1任选任选4 4二叉树二叉树1.21.2任选任选5 5堆堆1.21.2任选任选6 6二叉排序树二叉排序树1.21.2任选任选7 7平衡二叉树平衡二叉树1.31.3任选任选8 8树树1.21.2任选任选9 9并查集并查集1.21.2任选任选1010B B 树树1.41.4任选任选1111有向图有向图1.31.3任选任选1212无向图无向图1.31.3任选任选1313有向带权图有向带权图1.31.3任选任选注：如果基本操作数量较多，可选择

15、实现其中一个基本操作子集。实验要求如下：1首先了解设计的任务，然后根据自己的基础和能力从中选择一题。一般来说，选择题目应以在规定的时间内能完成，并能得到应有的锻炼为原则。若学生对教材以外的相关题目较感兴趣，希望选作实验的题目时，应征得指导教师的认可，并写出明确的抽象数据类型定义及说明。2.实验前要作好充分准备，包括：理解实验要求，掌握辅助工具的使用，了解该抽象数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。3.实验时严肃认真，要严格按照要求独立进行设计，不能随意更改。注意观察并记录各种错误现象，纠正错误，使程序满足预定的要求，实验记录应作为实验报告的一部分。4.实验后要及时总结

16、，写出实验报告，并附所打印的问题解答、程序清单，所输入的数据及相应的运行结果。3.53.5 实验仪器设备和材料实验仪器设备和材料计算机学院实验中心。编程环境：AnyviewCL 可视化编程环境、TC+、C+Builder、VC+或 Java。3.63.6 调试及结果测试调试及结果测试调试内容应包括：调试过程中遇到的问题是如何解决的以及对实验的讨论与分析；基本操作的时间复杂度和空间复杂度的分析和改进设想。列出对每一个基本操作的测试结果，包括输入和输出，测试数据应完整和严格。3.73.7 考核形式考核形式考核形式以实验过程和实验报告相结合的方式进行。实验报告作为整个设计性实验评分的书面依据。设计性

17、实验的成绩评定以选定题目的难易度、完成情况和实验报告为依据综合评分。从总体来说，所实现的抽象数据类型应该全部符合要求，类型定义，各基本操作的算法以及存储结构清晰；各模快测试运行正确；程序的结构合理；设计报告符合规范。3.83.8 实验报告要求实验报告要求实验结束后要写出实验报告，以作为整个设计性实验评分的书面依据和存档材料。实验报告是反映学生实验效果的最主要的依据，也是学生正确地表达问题、综合问题和发现问题的能力的基本培养手段，因而是非常重要的内容。本设计性实验的报告要包括以下几项内容：（1）设计任务、要求及所用软件环境或工具；（2）抽象数据类型定义以及各基本操作的简要描述；（3）所选择的存储

18、结构描述及在此存储结构上各基本操作的实现；（4）程序清单（计算机打印），输入的数据及各基本操作的测试结果；（5）实验总结和体会。实验报告以规定格式的电子文档书写、打印并装订，排版及图表要清楚、工整。3.93.9 思考题思考题对设计性实验进行总结和讨论，包括本实验的优、缺点，数据存储结构的特点，与其它存储结构之间的比较等。通过总结，可以对抽象数据类型有更全面、深入的认识，这是设计性实验不可缺少的重要内容。这部分内容应作为实验报告中的一个组成部分。3.103.10 示例示例1.题目题目采用字符类型为元素类型和无头结点单链表为存储结构，实现抽象数据类型 List。ADT List数据对象数据对象：D

19、 ai|aiElemSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,aiD,i=2,.,n 基本操作基本操作：SetEmpty(&L)操作结果：构造一个空的线性表 L。Destroy(&L)初始条件：线性表 L 已存在。操作结果：销毁线性表 L。Length(L)初始条件：线性表 L 已存在。操作结果：返回 L 中元素个数。Get(L,i,&e)初始条件：线性表 L 已存在，1iLengthList(L)。操作结果：用 e 返回 L 中第 i 个元素的值。Locate(L,e,compare()初始条件：线性表 L 已存在，compare()是元素判定函数。操作结果：返回

20、L 中第 1 个与 e 满足关系 compare()的元素的位序。若这样的元素不存在，则返回值为 0。Insert(&L,i,e)初始条件：线性表 L 已存在，1iLengthList(L)+1。操作结果：在 L 的第 i 个元素之前插入新的元素 e，L 的长度加 1。Delete(&L,i,&e)初始条件：线性表 L 已存在且非空，1iLengthList(L)。操作结果：删除 L 的第 i 个元素，并用 e 返回其值，L 的长度减 1。Display(L)初始条件：线性表 L 已存在。操作结果：依次输出 L 的每个元素。ADT List2存储结构定义存储结构定义公用头文件 DS0.h:#i

21、nclude#include#include#include#include#define TRUE1#define FALSE0#define OK1#define ERROR0#define IBFEASIBLE-1#define OVERFLOW-2#define MAXLEN20#define MAXSIZE 20typedef int Status;typedef char ElemType;/*元素类型为字符类型*/（1）顺序存储结构#define LIST_INIT_SIZE 20/*线性表存储空间的初始分配量*/#define LISTINCREMENT10/*线性表存储空间的

22、分配增量*/typedef structElemType*elem;/*存储空间基址*/intlength;/*当前长度*/intlistsize;/*当前分配的存储容量*/SqList;（2）无头结点单链表存储结构typedef struct LNode ElemType data;struct LNode*next;LNode,*LList;/*不带头结点单链表类型*/（3）带头结点单链表存储结构typedef struct LNode/*结点类型*/ElemType data;struct LNode*next;LNode,*Link,*Position;typedef struct L

23、inkList /*链表类型*/Link head,tail;/*分别指向线性链表中的头结点和最后一个结点*/int len;/*指示线性链表中数据元素的个数*/LinkList;3.算法设计算法设计（1）顺序存储结构Status SetEmpty(SqList&L)/*构造一个空的顺序线性表*/L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)return OVERFLOW;/*存储分配失败*/L.length=0;/*空表长度为 0*/L.listsize=LIST_INIT_SIZE;/*初始存储容量*

24、/return OK;Status Destroy(SqList&L)/*销毁顺序线性表 L*/free(L.elem);L.elem=NULL;L.length=0;L.listsize=0;return OK;int Length(SqList L)/*求表长*/return L.length;Status Get(SqList&L,int i,ElemType&e)/*获取第 i 元素*/if(iL.length)return ERROR;e=*(L.elem+i-1);return OK;int Locate(SqList L,ElemType x)/*确定 x 在表中的位序*/Ele

25、mType*p;int i=1;/*i 的初值为第 1 个元素的位序*/p=L.elem;/*p 的初值为第 1 个元素的存储位置*/while(i=L.length&*p+!=x)+i;if(i=L.length)return i;elsereturn 0;Status Insert(SqList&L,int i,ElemType e)/*操作结果：在 L 中第 i 个位置之前插入新的数据元素 e，L 的长度加 1*/ElemType*newbase,*q,*p;if(iL.length+1)/*i 值不合法*/return ERROR;if(L.length=L.listsize)/*当前

26、存储空间已满,增加分配*/newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)return OVERFLOW;/*存储分配失败*/L.elem=newbase;/*新基址*/L.listsize+=LISTINCREMENT;/*增加存储容量*/q=L.elem+i-1;/*q 为插入位置*/for(p=L.elem+L.length-1;p=q;-p)*(p+1)=*p;/*插入位置及之后的元素右移*/*q=e;/*插入 e*/+L.length;/*表长增 1*/

27、return OK;Status Delete(SqList&L,int i,ElemType&e)/*初始条件：顺序线性表 L 已存在，1iListLength(L)*/*操作结果：删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度减 1*/ElemType*p,*q;if(i L.length)/*i 值不合法*/return ERROR;p=L.elem+i-1;/*p 为被删除元素的位置*/e=*p;/*被删除元素的值赋给 e*/q=L.elem+L.length-1;/*表尾元素的位置*/for(+p;p=q;+p)/*被删除元素之后的元素左移*/*(p-1)=*p;L.

28、length-;/*表长减 1*/return OK;Status Display(SqList L)/*依次显示表中元素*/ElemType*p;int i;p=L.elem;printf();for(i=1;inext;free(q);q=L;return OK;int Length(LList L)/*求表长*/int n=0;while(L!=NULL)n+;L=L-next;return n;Status Get(LList L,int i,ElemType&e)/*获取第 i 元素*/int j=1;while(jnext;j+;if(L!=NULL)e=L-data;return

29、 OK;else return ERROR;/*位置参数 i 不正确*/int Locate(LList L,ElemType x)/*确定 x 在表中的位序*/int n=1;while(L!=NULL&L-data!=x)L=L-next;n+;if(L=NULL)return 0;else return n;Status Insert(LList&L,int i,ElemType e)/*插入第 i 元素*/int j=1;LList s,q;s=(LList)malloc(sizeof(LNode);s-data=e;q=L;if(i=1)s-next=q;L=s;return OK;

30、else while(jnext!=NULL)q=q-next;j+;if(j=i-1)s-next=q-next;q-next=s;return OK;else return ERROR;/*位置参数 i 不正确*/Status Delete(LList&L,int i,ElemType&e)/*删除第 i 元素*/int j=1;LList q=L,t;if(i=1)e=q-data;L=q-next;free(q);return OK;else while(jnext!=NULL)q=q-next;j+;if(q-next!=NULL&j=i-1)t=q-next;q-next=t-ne

31、xt;e=t-data;free(t);return OK;else return ERROR;/*位置参数 i 不正确*/void Display(LList L)/*依次显示表中元素*/printf(单链表显示:);if(L=NULL)printf(链表为空!);else if(L-next=NULL)printf(%cn,L-data);else while(L-next!=NULL)printf(%c-,L-data);L=L-next;printf(%c,L-data);printf(n);（3）带头结点单链表带头结点单链表Status SetEmpty(LinkList&L)/*置

32、带头结点的空单链表*/Link p;p=(Link)malloc(sizeof(LNode);/*生成头结点*/if(p)p-next=NULL;L.head=L.tail=p;L.len=0;return OK;elsereturn ERROR;Status Destroy(LinkList&L)/*销毁线性链表 L，L 不再存在*/Link p,q;if(L.head!=L.tail)/*不是空表*/p=q=L.head-next;L.head-next=NULL;while(p!=L.tail)p=q-next;free(q);q=p;free(q);free(L.head);L.hea

33、d=L.tail=NULL;L.len=0;return OK;int Length(LinkList L)/*返回线性链表 L 中元素个数*/return L.len;Status Get(LinkList L,int i,ElemType&e)/*获取第 i 元素*/*i=0 为头结点*/Link p;int j;if(iL.len)return ERROR;else p=L.head;for(j=1;jnext;e=p-data;return OK;int Locate(LinkList L,ElemType x)/*确定 x 在表中的位序*/int i=0;Link p=L.head;

34、do p=p-next;i+;while(p&p-data!=x);/*没到表尾且没找到满足关系的元素*/if(!p)return 0;elsereturn i;Status Insert(LinkList&L,int i,ElemType e)/*插入第 i 元素*/int j=0;Link s,q;s=(Link)malloc(sizeof(LNode);s-data=e;q=L.head;while(jnext!=NULL)q=q-next;j+;if(j=i-1)s-next=q-next;q-next=s;if(L.tail=q)L.tail=s;L.len+;return OK;e

35、lse return ERROR;/*位置参数 i 不正确*/Status Delete(LinkList&L,int i,ElemType&e)/*删除第 i 元素*/int j=0;Link q=L.head,t;while(jnext!=NULL)q=q-next;j+;if(q-next!=NULL&j=i-1)t=q-next;q-next=t-next;e=t-data;if(L.tail=t)L.tail=q;free(t);L.len-;return OK;else return ERROR;/*位置参数 i 不正确*/void Display(LinkList L)/*依次显

36、示表中元素*/Link p;printf(单链表显示:);if(L.head=L.tail)printf(链表为空!);else p=L.head-next;while(p-next!=NULL)printf(%c-,p-data);p=p-next;printf(%c,p-data);printf(n);4测试测试（1）顺序存储结构顺序存储结构SqList head;void main()/*主函数*/char e,c;int i,n,select,x1,x2,x3,x4,m,g;SetEmpty(head);n=random(8);/*随机产生表长*/for(i=1;i0&select 5

37、);（2）无头结点单链表无头结点单链表LList head;void main()/*主函数*/char e,c;int i,n,select,x1,x2,x3,x4,m,g;SetEmpty(head);n=random(8);/*随机产生表长*/for(i=1;i0&select 5);（3）带头结点单链表带头结点单链表LinkList head;void main()/*主函数*/char e,c;int i,n,select,x1,x2,x3,x4,m,g;SetEmpty(head);n=random(8);/*随机产生表长*/for(i=1;i0&selectFloor），则预置

38、14 个 t 后（减速）转到 E2。否则重复 E7。E8.下降一层 除了方向相反之外，与 E7 类似，但那里的 51 和 14 个 t 此时分别改为 61 和23 个 t（电梯下降比上升慢）。E9.置不活动指示器 置 D2 为 0 并调用 Controler 函数（E9 是由 E3 预置的，但几乎总是被E6 取消了）。（6）当电梯须对下一个方向作出判定时，便在若干临界时刻调用 Controler 函数。该函数有以下要点：C1.需要判断？若 StateIdle，则返回。C2.应该开门？如果电梯处于 E1 且 CallUp1,CallDown1或 CallCar1非 0，则预置 20 个t 后启动

39、 E3，并返回。C3.有按钮按下？找最小的 jFloor，使得 CallUpj,CallDownj或 CallCarj非 0，并转到C4。但如果不存在这样的 j，那么，如果 Controler 正为 E6 所调用，则置 j 为 1，否则返回。C4.置 State 如果 Floorj，则置 State 为 GoingDown；如果 Floorj，则置 State 为 GoingUp。C5.电梯静止？如果电梯处于 E1 而且 j1，则预置 20 个 t 后启动 E6。返回。（7）由上可见，关键是设计合适的数据结构，按时序管理系统中所有乘客和电梯的动作。选做内容选做内容（1）增加电梯数量，模拟多梯系

40、统。（2）某高校的一座 30 层住宅楼有三部自动电梯，每梯最多载客 15 人。大楼每层八户，每户平均 3.5 人，每天早晨平均每户有 3 人必须在 7 时之前离开大楼去上班或上学。模拟该电梯系统，并分析分别在一梯、二梯和三梯运行情况下，下楼高峰期间各层的住户应提前多少时间候梯下楼？研究多梯运行最佳策略。题目题目 7 7哈希表设计哈希表设计（难度系数：1.0）问题描述问题描述针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过 R，完成相应的建表和查表程序。基本要求基本要求假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有 30 个，取平均查找长度的上限为

41、2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。测试数据测试数据取读者周围较熟悉的 30 个人的姓名。实现提示实现提示如果随机函数自行构造，则应首先调整好随机函数，使其分布均匀。人名的长度均不超过 19个字符(最长的人名如：庄双双（Zhang Shuangshuang）。字符的取码方法可直接利用 C 语言中的toascii 函数，并可对过长的人名先作折叠处理。选做内容选做内容(1)从教科书上介绍的几种哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较它们的地址冲突率(可以用更大的名字集合作试验)。(2)研究这 30 个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定

42、不发生地址冲突。(3)在哈希函数确定的前提下尝试各种不同处理冲突的方法，考查平均查找长度的变化和造好的哈希表中关键字的聚簇性。题目题目 8 8最小生成树问题最小生成树问题（难度系数：1.1）问题描述问题描述若要在 n 个城市之间建设通讯网络，只需要架设 n-1 条线路即可。如何以最低的经济代价建设这个通讯网，是一个网的最小生成树问题。基本要求基本要求（1）利用克鲁斯卡尔算法求网的最小生成树。（2）实现并查集。以此表示构造生成树过程中的连通分量。（3）以文本形式输出生成树中各条边以及他们的权值。测试数据测试数据参见本题集中的习题。实现提示实现提示通讯线路一旦建立，必然是双向的。因此，构造最小生成

43、树的网一定是无向网。设图的顶点数不超过 30 个，并为简单起见，网中边的权值设成小于 100 的整数，可利用 C 语言提供的随机数函数产生。图的存储结构的选取应和所作操作向适应。为了便于选择权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边(带权)的数组表示图。选做内容选做内容利用堆排序实现选择权值最小的边。题目题目 9 9表达式类型的实现表达式类型的实现（难度系数：1.2）问题描述问题描述一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式 Expression 的操作。基本要求基本要求假设算术表达式 Express

44、ion 内可以含有变量（az）、常量（09）和二元运算符（+,-,*,/,(乘幂)）。实现以下操作：（1）ReadExpr(E)-以字符序列的形式输入语法正确的前缀表示式并构造表达式 E。（2）WriteExpr(E)-用带括弧的中缀表示式输出表达式 E。（3）Assign(V,c)-实现对变量 V 的赋值（V=c），变量的初值为 0。（4）Value(E)对算术表达式 E 求值。(5)CompoundExpr(P,E1,E2)构造一个新的复合表达式(E1)P(E2)。测试数据测试数据（1）分别输入 0;a;-91;+a*bc;+*15x2*8x;+*3x3*2x2x6 并输出。（2）每当输入

45、一个表达式后，对其中的变量赋值，然后对表达式求值。实现提示实现提示（1）在读入表达式的字符序列的同时，完成运算符和运算数（整数）的识别处理，以及相应的运算。（2）在识别出运算数的同时，要将其字符形式转换成整数形式。（3）用后根遍历的次序对表达式求值。（4）用中缀表示输出表达式 E 时，适当添加括号，以正确反映运算的优先次序。选做内容选做内容（1）增加求偏导数运算 Diff(E,V)求表达式 E 对变量 V 的导数。（2）在表达式中添加三角函数等初等函数的操作。（3）增加常数合并操作 MergeConst(E)合并表达式 E 中所有常数运算。例如，对表达式E=(2+3-a)*(b+3*4)进行合

46、并常数的操作后，求得 E=(5-a)*(b+12)。题目题目 1010内部排序算法比较内部排序算法比较（难度系数：1.1）问题描述问题描述在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。基本要求基本要求(1)对以下 6 种常用的内部排序算法进行比较：起泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序。(2)待排序表的表长不小于 100；其中的数据要用伪随机数产生程序产生；至少要用 5 组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数(关键

47、字交换计为3 次移动)。(3)最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。测试数据测试数据由随机数产生器生成。实现提示实现提示主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如，正序、逆序和不同程度的乱序。注意采用分块调试的方法。选做内容选做内容(1)增加折半折入排序，二路插入排序，归并排序，基数排序等。(2)对不同的输入表长作试验，观察检查两个指标相对于表长的变化关系。还可以对稳定性作验证。题目题目 1111多关键字排序多关键字排序（难度系数：1.0）问题描述问题描述多关键字的排序有其一定的实用范围。例如：在

48、进行高考分数处理时，除了需对总分进行排序外，不同的专业对单科分数的要求不同，因此尚需在总分相同的情况下，按单科的分数排出考生录取的次序。基本要求基本要求（1）假设待排序的记录数不超过 1000，表中记录的关键字数不超过 5，各个关键字的范围均为 0 至 100。按用户给定的进行排序的关键字的优先关系，输出排序结果。（2）约定按 LSD 法进行多关键字的排序。在对各个关键字进行排序时采用两种策略：其一是利用稳定的内部排序法，其二是利用“分配”和“收集”的方法。并综合比较这两种策略。测试数据测试数据由随机数产生器生成。实现提示实现提示用 5 至 8 组数据比较不同排序策略所需时间。由于是按 LSD

49、 方法进行排序，则对每个关键字均可进行整个序列的排序，但在利用通常的内部排序方法进行排序时，必须选用稳定的排序方法。借助“分配”和“收集”策略进行的排序，如同一趟“基数排序”，由于关键字的取值范围为 0 至 100，则分配时将得到 101 个链表。选做内容选做内容增添按 MSD 策略进行排序，并和上述两种排序策略进行综合比较。题目题目 1212平衡二叉树操作的演示平衡二叉树操作的演示（难度系数：1.3）问题描述问题描述利用平衡二叉树实现一个动态查找表。基本要求基本要求实现动态查找表的三种基本功能：查找、插入和删除。测试数据测试数据由读者自行设定。实现提示实现提示(1)初始，平衡二叉树为空树，操

50、作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。每次插入或删除一个结点后，应更新平衡二叉树的显示。(2)平衡二叉树的显示可采用如 6.3 题要求的凹入表形式，也可以采用图形界面画出树形。(3)教科书已给出查找和插入算法，本题重点在于对删除算法的设计和实现。假设要删除关键字为 x 的结点。如果 x 不在叶子结点上，则用它左子树中的最大值或右子树中的最小值取代 x。如此反复取代，直到删除动作传递到某个叶子结点。删除叶子结点时，若需要进行平衡变换，可采用插入的平衡变换的反变换（如，左子树变矮对应于右子树长高）。选做内容选做内容(1)合并两棵平衡二叉树。(2)把一棵平衡二叉树分裂