本科数据结构课程设计大纲.doc

数据结构课程设计教学大纲（）学院：计算机科学与技术学院专业：计算机科学与技术周数：2周 学分：2一、课程设计的目的和任务1、提高对数据逻辑结构的特点以及存储表示方式的认识，培养在具体应用中选择合适的数据结构和存储结构的能力；2、熟悉软件开发的基本过程，初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等阶段的基本任务和技能方法；3、培养学生的算法设计和算法分析能力，提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法、作风和相互合作的精神。二、课程设计的主要内容与要求1. 课程设计选题（一个题目为一个小组，每小组2人）1 文章编辑功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"（3）输出删除某一字符串后的文章；2 通讯录的制作设计目的：用数据结构中的双向链表作数据结构，结合C/C+语言基本知识。编写一个通讯录管理系统。以把所学数据结构知识应用到实际软件开发中去。设计内容：本系统应完成一下几方面的功能：输入信息enter();显示信息display( );查找以姓名作为关键字 search( );删除信息delete( );存盘save ( );装入load( ) ;设计要求：1) 每条信息至包含 ：姓名（NAME ）街道（STREET）城市（CITY）邮编（EIP）国家（STATE）几项2) 作为一个完整的系统，应具有友好的界面和较强的容错能力3) 上机能正常运行，并写出课程设计报告3宿舍管理查询软件任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：采用交互工作方式建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)查询菜单: (用二分查找实现以下操作)按姓名查询按学号查询房号查询打印任一查询结果（可以连续操作）4顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。 设有一元多项式Am(x)和Bn(x). Am(x)=A0+A1x1+A2x2+A3x3+ +Amxm Bn(x)=B0+B1x1+B2x2+B3x3+ +Bnxn 请实现求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。要求： 1) 首先判定多项式是否稀疏2) 分别采用顺序和动态存储结构实现；3) 结果M(x)中无重复阶项和无零系数项；4) 要求输出结果的升幂和降幂两种排列情况5 二叉排序树的实现 用顺序和二叉链表作存储结构 1） 回车('n')为输入结束标志,输入数列L，生成一棵二叉排序树T；2） 对二叉排序树T作中序遍历，输出结果；3） 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；6学生搭配问题 一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴. 请设计一系统模拟动态地显示出上述过程,要求如下:1) 输出每曲配对情况2) 计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值.3) 尽量设计出多种算法及程序,可视情况适当加分 提示:用队列来解决比较方便. 7敢死队问题 有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。 排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。 要求：至少采用两种不同的数据结构的方法实现。8长整数四则运算 要求见严蔚敏习题集P801.49停车场管理 要求见严蔚敏习题集P962.110魔王语言解释 要求见严蔚敏习题集P972.211车厢调度 要求见严蔚敏习题集P972.312算术表达式求值演示 要求见严蔚敏习题集P992.513银行业务模拟 要求见严蔚敏习题集P1002.614电梯模拟 要求见严蔚敏习题集P1022.815重言式判别 要求见严蔚敏习题集P1485.116哈夫曼编码译码器 要求见严蔚敏习题集P1485.217图遍历的应用 要求见严蔚敏习题集P1505.318全国交通咨询模拟 要求见严蔚敏习题集P1515.819图书管理 要求见严蔚敏习题集P1666.320平衡二叉树操作的演示 要求见严蔚敏习题集P1666.421员工管理系统问题描述：每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。系统能够完成员工信息的查询、更新、插入、删除、排序等功能。要求：（1） 排序：按不同关键字，对所有员工的信息进行排序。（2） 查询：按特定条件查找员工。（3） 更新：按编号对某个员工的某项信息进行修改。（4） 插入：加入新员工的信息。（5） 删除：按编号删除已离职的员工的信息。22 各种内排序算法的比较1、问题描述 对本章的各种排序方法（直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序和归并排序）的时间性能进行比较。2、 基本要求（1）设计并实现上述各种排序算法；（2）对正序和逆序的初始排列分别调用上述排序算法，并比较时间性能；（3）对随机产生的初始排列分别调用上述排序算法，并比较时间性能。3、 设计思想上述各种排序方法都是基于比较的内排序，其时间主要消耗在排序过程中进行的记录的比较和移动，因此，统计在相同数据状态下不同排序算法的比较次数和移动次数，即可实现比较各种排序算法的目的。思考题如果测算每种排序算法所用的实际时间，应如何修改排序算法？ 2、课程设计调研 根据具体题目要求，由学生查阅指导教师提供的参考书目，以设计小组为单位进行需求分析，初步明确所选用的逻辑结构和存储结构。3、课程设计方案制定根据讨论，明确解决问题的基本算法，完成每个部分的算法设计说明（可以是描述算法的流程图）和每个程序中使用的存储结构设计说明。4、课程设计报告的要求课程设计报告：（保存在word 文档中，文件名要求 按照"姓名-学号-课程设计报告"起名，如文件名为"张三-001-课程设计报告".doc ）按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成；其中包括:a)需求分析：在该部分中叙述，每个模块的功能要求b)概要设计在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。c）详细设计各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。d）调试分析测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。e）设计总结：课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对数据结构课程的认识等内容三、课程设计的指导在设计的第一周周三之前教师必须完成对学生的设计方案的检查，保证无原则性的设计错误；在第一周后半周和第二周必须保证每天和学生见面，指导学生解决设计和调试中出现的问题。四、课程设计的质量标准与成绩考核课程设计结束时，要求学生写出课程设计报告（附源程序），可运行的软件系统。课程设计成绩分两部分，设计报告占30，设计作品占70。其中设计报告雷同者按不合格处理；设计作品的成绩必须由教师亲自对学生的程序进行检查，先由学生对自己的设计框架和实现过程进行介绍，再由教师至少对学生提出4个与程序有关的不同层次的问题，根据学生的对问题的回答和介绍情况并参考设计过程中的表现给予打分。评分过程要考虑到不同题目的难度差异性。成绩分为优秀、良好、中、及格，不及格五级。五、课程设计的工作进度安排设计前一周周末，学生选题；第一周周三以前完成需求分析和概要设计；第二周周五以前完成程序调试，写出设计报告；第二周周五设计汇报答辩。六、课程设计的组织管理与要求本课程设计计划2学分，共2周。在学院领导的指导下，由系主任负责整体组织和管理。指导教师负责相应小组的设计指导工作。