数据结构课程设计实验大纲new

1、数据结构课程设计课程实验大纲一、 课程名称：数据结构课程设计二、 课程性质：其他实践教学环节三、 实验学时：36学时四、 课程类型：独立设课五、 课程适用专业：计算机科学技术专业、计算机科学与技术专业（实验班）、软件工程专业六、 教学目的：了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。七、 实验教学项目表1项目线性结构及其应用时数16性质设计内容要求从

2、以下题目中任选一个一、学生信息管理系统问题描述：设计一个学生信息管理系统，实现对学生基本信息的添加、删除、修改和查询等操作。要求： 程序采用图形界面下进行交互的工作方式，完成如下功能：（1） 多种方式建立学生信息l 每个学生信息由学号、姓名、数学、英语和语文组成；l 可以通过手工录入每个学生信息，并在C盘下以StudentFile.txt保存；l 也可以导入某个路径下存放学生信息的文本文件。（2） 浏览所有学生信息。（3） 按照学号对所有学生信息进行升序、降序排列，并输出l 可选用冒泡、选择等算法；l 不仅输出屏幕显示，还需要写入存放学生信息的文件。（4） 按姓名、学号等方式，实现对学生信息精

3、确查询、模糊查询，并输出屏幕显示 l 精确查询结果演示查询“姓名是王五”同学信息，则输出 学号 姓名 数学 英语 语文 .2007112011 王五 88 90 78 .l 模糊查询结果演示查询姓“刘”的同学信息（输入“刘”），则输出 学号 姓名 数学 英语 语文 .2007112011 刘梅 88 90 78 .2007112011 刘强 87 80 98 .2007112011 刘星 86 70 58 .l 能够实现连续多次查询 （5） 学生信息的插入、删除、修改。l 通过插入、删除和修改后，保持所有学生信息的有序性；l 插入、删除和修改后，对存放所有学生信息的文件及时更新。（6） 数据的

4、统计功能l 统计每个学生的平均分和总分；l 统计每个科目的平均分和最高分、最低分；l 将上述统计结果，写入存放学生信息的文件。二、设计散列表实现电话号码查找系统要求：（1）为每个记录设计下列数据项：电话号码、用户名、地址等；（2）随机产生各记录，分别以电话号码和用户名为关键字建立散列表；（3）采用适当的方法解决冲突；（4）查找并显示给定电话号码的记录；（5）查找并显示给定用户名的记录。2项目栈与队列结构的应用时数16性质综合设计内容要求从以下题目中任选一个一、设计一个程序，求解算术表达式问题描述：以字符序列的形式从键盘输入语法正确的、不含变量的整数表达式，实现对算术四则混合运算表达式的求值。要

5、求：自己设计界面，使用适当的数据结构对运算符、操作作数进行处理。二、银行业务的模拟系统问题描述：设计一个银行业务模拟系统，模拟银行的业务运行并计算一天中客户在银行逗留的平均时间。银行有N（N的取值自己定义）个窗口对外接待客户，从早晨银行开门起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需在每个窗口前顺次排队，对于刚进入银行的客户，如果某个窗口的业务员正空闲，则可上前办理业务；反之，若N个窗口均有客户所占，他便会排在人数最少的队伍后面。要求：（1）在界面上可以设定银行的对外营业时间（银行的开门时间以及银行的关门时间）。（2）用人机交互的方式来输入客户的到达时间

6、以及客户的离开时间，用队列来存储客户的到达事件和客户的离开事件。（3）可以友好的显示出在某一天中整个银行系统中客户在银行逗留的平均时间。三、停车场管理系统问题描述：设计一个停车场管理系统，模拟停车场的运作。要求：（1） 要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理；（2） 要求处理的数据元素包括如下数据项：汽车“到达”或“离去”信息、汽车牌照及“到达”或“离去”的时刻；（3） 若是车辆到达，就输出汽车在停车场内或便道上的停车位置；若是车离去，就输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。（4） 完成该停车场的一些信息统计功能（

7、如每天到达/离开的车次，停车总时数、每天的停车费用等）。四、迷宫问题问题描述：用一个字符类型的二维数组表示迷宫，数组中的每个元素表示一个小方格，取值“0”（通道）或“1”（阻塞物）。设计一个模拟小老鼠走迷宫的程序，为小老鼠寻找一条从迷宫入口到迷宫出口的途径小方格最少的最短通路。要求：（1） 用随机函数设置迷宫（用户可以选择迷宫的大小，即多少行多少列）；（2） 选择合适的数据结构表示迷宫。（3） 迷宫入口处的下标是（x0，y0），出口处的下标是（x1，y1），由键盘输入。（4） 输出从入口到出口的最短通路（如存在）或不存在通路的信息。（5） 设计出友好的图形化界面，做到很好的人机交互。3项目树结

8、构及其应用时数20性质综合设计内容要求从以下题目中任选一个一、哈夫曼编码/译码器问题描述：设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件（后缀名.cod）；反过来，可将一个编码文件还原为一个文本文件(.txt)。要求：（1）输入一个待压缩的文本文件名，统计文本文件中各字符的个数作为权值，生成哈夫曼树；（2）将文本文件利用哈夫曼树进行编码，生成编码文件（后缀名cod）；（3）输入一个待解压的压缩文件名称，并利用相应的哈夫曼树将编码序列译码；（4）显示指定的编码文件和文本文件；（5）把哈夫曼编码用二进制位紧缩到一个变量中，利用位运算进行真正的数据压缩，并求压缩比。

9、（此选项选作）二、文件目录管理系统问题描述：文件是管理用户信息和应用程序的一种工具。每个文件有唯一的文件名，可以通过文件名访问文件，同时可对文件进行生成、删除及文件名修改等操作。文件系统对若干文件进行管理时将所有的文件目录组合在一起构成一个目录文件。通过对目录文件的管理达到“按名存取”的目的，目录文件常采用的组织结构是树型目录结构。要求：函数功能要划分好，程序要有必要的注释。用户通过界面菜单选择以下操作： （1） 生成文件，选择路径和文件名，实现对文件的生成。（2） 删除文件，对指定文件进行删除操作。（3） 修改文件，对指定文件进行内容修改或者文件名修改。（4） 输出该目录结构。4项目图结构及

10、其应用时数20性质综合设计内容要求从以下题目中任选一个一、设计一个校园导游程序，为来访的客人提供信息查询服务。要求：（1）设计学校的校园平面图，所含景点不少于10个，以图中顶点表示校内各景点，存放景点名称、代号、简介等信息，以边表示路径，存放路径长度等相关信息。（2）为来访客人提供图中任意景点相关信息的查询；（3）为来访客人提供从校门口到图中任意景点的问路查询；（4）为来访客人提供图中任意景点间的问路查询；（此项选作）二、最小生成树问题问题描述：已知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的

11、连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择这样一棵生成树，使总的耗费最小。即构造连通网的最小生成树的问题。要求：（1）建立城市交通网的存储结构。（注：数据输入可以是键盘输入或文件输入两种方式）（2）分别用Prim算法和Kruskal算法构造最小生成树，并输出最小生成树的代价及生成树的边。（注：结果的输出可以是屏幕输出和文件输出两种方式）5项目内部排序算法的性能分析时数16性质设计内容要求问题描述：设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。要求：（1）对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比

12、较；（2）待排序表的表长不小于1000，表中数据随机产生，至少用3组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）；（3）输出比较结果。八、 选题要求：在上面实验项目1、2、5中选一个小题做，在实验项目3、4中选择一个小题做，即一共需要完成两个小题。九、 课程设计报告要求：每个实验应该有相应的课程设计报告，包含如下内容：（1）问题描述及分析（2）功能模块及数据结构描述（3）主要算法流程描述（4）使用说明如何运行，如何输入测试数据，会出现的输出结果等，给出实例。（5）实验及总结调试过程中遇到的主要问题有哪些？如何解决的。有何结论？课程设计报告的格式要求

13、1字体设置要求为：（1）标题：黑体小四（2）正文内容：宋体小四号（3）表题与图题宋体五号（4）参考文献：宋体五号2表格每个表格应有表序和表题，表序和表题应写在表格上方正中，表序后空一格书写表题。3插图插图必须精心制作，线条粗细要合适，图面要整洁美观。每幅插图应有图序和图题，图序和图题应放在图位下方居中处。4各类参考文献的书写格式如下：连续出版物：序号作者.书名.刊名，年，卷号(期号)：起止页码专(译)著：序号作者.书名.(译者).出版地：出版者，出版年.起止页码论文集：序号作者.文章名.文集名.会议地点，年.起止页码学位论文：序号姓名.学位论文题目:XX学位论文，授予单位所在地：授予单位，授予年十、课程设计成绩评定：准确评定成绩是课程设计的重点。教师通过进度检查、设计答辩和报告评审的形式了解学生的设计水平。学生必须做两个小题目