数据结构课程设计教学大纲.docx

数据结构课程设计教学大纲

第一篇：数据结构课程设计教学大纲《数据结构课程设计》教学大纲DataStructureCourseDesign一、课程的性质、教学目的和要求《数据结构》是计算机软件的一门基础课程，计算机科学各领域及有关的应用软件都要用到各种类型的数据结构。学好数据结构对掌握实际编程能力是很有帮助的。为了学好《数据结构》，必须编写一些在特定数据结构上的算法，通过上机调试，才能更好地掌握各种数据结构及其特点，同时提高解决计算机应用实际问题的能力。二、设计要点1．设计和调试过程要规范化。①需求分析将题目中要求的功能进行叙述分析，并且设计解决此问题的数据存储结构，（有些题目已经指定了数据存储的，按照指定的设计），设计或叙述解决此问题的算法，描述算法建议使用流程图，进行算法分析指明关键语句的时间复杂度。给出实现功能的一组或多组测试数据，程序调试后，将按照此测试数据进行测试的结果列出来。对有些题目提出算法改进方案，比较不同算法的优缺点。如果程序不能正常运行，写出实现此算法中遇到的问题，和改进方法。②源程序（可以是一组源程序，即详细设计部分）源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环。2．课程设计实习报告的书写格式①设计题目（任选其一）②运行环境（软、硬件环境）③算法设计的思想④算法的流程图⑤算法设计分析⑥源代码⑦运行结果分析⑧收获及体会3．实施方式可设2-3人一题，安排在《数据结构》课程开课学期布置题目，然后在期末前两周完成。三．设计要求学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。课程设计按照教学要求需要1周时间完成，1周中每天至少要上6-8小时的机来调试C语言设计的程序，总共至少要上机调试程序30小时。为保证质量，需要每个学生将每天的上机调试程序的时间记录下来，作为评判成绩的标准之一。四．设计题目1、校园导游程序[问题描述]用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。[基本要求]（1）查询各景点的相关信息；（2）查询图中任意两个景点间的最短路径。（3）查询图中任意两个景点间的所有路径。（4）增加、删除、更新有关景点和道路的信息。[选作内容]（1）求多个景点的最佳（最短）游览路径。（2）区分机动车道和人行道。（3）实现导游图的仿真界面。2、算术表达式求值[问题描述]一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。[基本要求]（1）从键盘读入一个合法的算术表达式，输出正确的结果。（2）显示输入序列和栈的变化过程。[选作内容]扩充运算符集合。引入变量操作数。操作数类型扩充到实数。3、文学研究助手[问题描述]文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。[基本要求]英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。[测试数据]以你的源程序模拟英文小说，程序语言保留字集作为待统计的词汇集。[实现提示]设小说中的词汇一律不跨行。这样，每读入一行，就统计每个词在这行中的出现次数。出现位置所在行的行号可以用链表存储。若某行中出现了不止一次，不必存多个相同的行号。如果读者希望达到选作部分（1）和（2）所提出的要求，则首先应把KMP算法改写成如下的等价形式，再将它推广到多个模式的情形。[选作内容]（1）模式匹配要基于KMP算法。（2）整个统计过程中只对小说文字扫描一遍以提高效率。（3）假设小说中的每个单词或者从行首开始，或者前置以一个空格符。利用单词匹配特点另写一个高效的统计程序，与KMP算法统计程序进行效率比较。（4）推广到更一般的模式集匹配问题，并设待查模式串可以跨行（提示：定义操作getachar）4.迷宫求解[问题描述]可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；[基本要求]含有两个以上的迷宫图，由用户选择哪一张迷宫图；实现深度优先、广度优先两种回溯法。在上交资料中请写明：存储结构、基本算法（可以使用