《数据结构与算法分析课程设计》任务书2012版

2012级数据结构与算法分析课程设计任务书

（适应于2012级软件工程专业12201801-3,12201807-9班）

一、课程设计的目的与要求

1．教学目的

《数据结构与算法设计》课程设计是软件工程、网络工程、数字媒体技术专业学生的重要实践性环节。通过本课程设计，学生可以了解数据结构、算法设计的基本方法与基本原理，掌握软件设计中数据的组织，算法的设计，为今后从事实际工作打下基础。同时，作为整个实践教学体系一部分，系统培养学生采用面向对象的方法分析问题与解决问题的能力及团体组织与协作能力。

2．教学要求

从课程设计的目的出发，通过设计工作的各个环节，达到以下教学要求： 1．掌握各类基本数据结构及其实现； 2．掌握不同数据结构的实际应用；

3．培养利用数据结构并对实际应用问题进行算法设计的能力。 4．编程简练，程序功能齐全，能正确运行。 5．说明书、流程图要清楚，规范

6．课题完成后必须按要求提交课程设计报告，格式规范，内容详实。

二、课程设计的内容与安排

序号 项目名称 时间 内容提要 安排 为宿舍管理人员编写一个宿舍管理查询软件，建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插目的要求 教学方式 1 宿舍管理查询系统 入排序等任选一种) 查询菜单: (用二分查找实现以下操作) A. 按姓名查询 B. 按学号查询 C. 按房号查询 功能：输入一页文字，程序可以1周 掌握顺序表、链表实现线性表的基本操作。 室内指导 1．掌握结构体数组的表示和存储。 2. 掌握线形表的存储和操2

文章编辑 统计出文字、数字、空格的个数。 1周 静态存储一页文章，每行最多不室内指导

超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。 存储结构使用线性表，分别用几个子函数实现相应的功能； 输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。 输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出\全部字母数\、\数字个数\、\空格个数\、\文章总字数\（3）输出删除某一字符串后的文章； 设计散列表实现电话号码查找系统：1) 设每个记录有下列数据项：电话号码、用户名、地址； 2) 从键盘输入各记录，分别以电1．掌握结构体数组的表示和存储。 1周 2. 掌握链表的存储和操作。 3．掌握文件的操作。 话号码和用户名为关键字建立散列表； 3) 采用一定的方法解决冲突； 4) 查找并显示给定电话号码的记录； 5) 查找并显示给定用户名的记录。 1）对中序输入串进行合法性判断，若不合法重新输入，否则建作。 3．掌握文件的操作。 3 散列表的设计与实现 室内指导 4 算术运算式的转换及求值 立表达式二叉树。 2）转换为后缀表达式（逆波兰式） 1周 3）转换为前缀表达式（波兰式） 4）计算表达式的值 5）输出计算结果及转换后串。 1． 已知二叉树的后序、中序序列，恢复此二叉树； 2． 求二叉树高度、分支结点数和叶子结点数； 3．插入结点到指定位置、删除指定结点； 4．将二叉树中所有结点的左右子树交换。 5．对二叉树进行层序、非递归中序遍历。 1．掌握二叉树的概念和性质及基本操作 2. 掌握栈的概念和操作 室内指导 1．掌握二叉树的概念和性质 1周 2. 掌握任意二叉树存储结构。 3．掌握任意二叉树的基本操作。 5 二叉树操作 室内指导

哈夫曼树与哈夫曼码 1．输入一个文本，统计各字符出现的频度，输出结果 2．使用字符出现的频度构造哈夫曼树 1．掌握哈夫曼树的建树原理 6 3．确定和输出各字符的哈夫曼码 1周 4．输入一个由0和1组成的代码序列，翻译并输出与之对应的文体，若最后的代码子序列不能译为文本，则输出相关信息 （1） 字符串采用数组存储，建立两个字符串String1和String2。输出两个字符串。 （2） 将字符串String2的头n个字符添加到String1的尾部。输出结果。 （3） 查找串String3在串String1中的位置，若String3在String1中不存在，则插入String3在String1中的m位置上。输出结果。 （4） 求任意子字符串SUBSTR及删除子字符串。 （5） 求字符串的单词个数。 设计内容和要求： （1） 建立两个链表A和B，链表元素个数分别为m和n个。 （2） 假设元素分别为(x1,x2,…xm)，和(y1,y2, …yn)。把它们合并成一个线形表C，使得： 当m>=nn>m时时，，1周 1周 室内指码逻辑结构和存储结构。 导 2. 掌握哈夫曼树与哈夫曼3．掌握哈夫曼树与哈夫曼码的基本操作。 1．掌握顺序表的建立。 2．掌握顺序表的基本操作。 3．掌握串的基本操作。 7 字符串的操作 室内指导 8 实现两个链表的合并 C=x1,y1,x2,y2,…xn,yn,…,xm 当C=y1,x1,y2,x2,…ym,xm,…,yn 输出线形表C （3） 用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。 （4） 能删除指定单链表中指定位子和指定值的元素。 对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，1．掌握线性链表的建立。 室内指2．掌握线性链表的基本操作。 导 1．掌握图的邻接表存贮结构。 1周 2．掌握队列的基本运算实现。 3．掌握图的邻接表的算法实现。 9 图的广度周游 然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索周游。 室内指导

4．掌握图的广度优先搜索周游算法实现。 1．掌握图的邻接表存贮结对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，构。 2．掌握堆栈的基本运算实1周 现。 3．掌握图的邻接表的算法实现。 4．掌握图的深度优先搜索周游算法实现。 问题描述：给出n个学生的考试成绩表，成绩表包括学生的学号、姓名、考试成绩（高等数学、英语、物理），设计一个简单的成绩管理程序。基本要求：（1）建立成绩表，能够插入、删除、修改学生的成绩记录；（2）按任一单科成绩排序；(3) 计算每名学生的1、 掌握线性表的创建及基本操作； 2、 掌握基本排序 3、 复习文件相关的操作 （1）用顺序结构表示成绩1周 单，完成任务（1）～（6）， 成绩为及格； （2）用链表表示成绩单，完成任务（1）～（6），且软件容错能力强，成绩为中等 10 图的深度周游 然后利用堆栈的五种基本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现图的深度优先搜索周游 11 成绩管理 平均成绩；(4) 统计任一单科成绩不及格的学生人数, 输出不及格人数及不及格的学生名单(5) 根据平均成绩将成绩表按由高到低的次序排列，统计每名学生在考试中获得的名次，分数相同的为同一名次，按名次输出成绩表。(6) 成绩表保存在文件中, 可以从文件读取数据。 考核要求： （1）用链表表示多项式，问题描述：设计一个简单一元多项式计算器。基本要求：(1)输入完成任务（1）～（4），成绩为及格 （2）满足考核（1）的要求，同时能够输入变量的值，计算出多项式的结果，成绩中等，特别注意不能用X^N计算，否则等同于没有完成提高要求。 问题描述：从任一省会出发，走遍所有省会，给出某种评价指标，然后根据该指标由计算机选择最考核要求：（1）不要求画图，用数字或文字表示省1周 会，给出漫游路线，达到基本要求，成绩可为优秀。 （2）鼓励画图，用不同颜色的线画出漫游路线 12 一元多项式简单计算 并建立多项式； (2)输出多项式； 1周 (3)两个多项式相加，输出结果多项式； (4)两个多项式相减，输出结果多项式。 13 漫游中国 优的漫游路线。基本要求：（1）建立以省会为节点，以是否相邻为边的一个无向赋权图；（2）只能选择陆路和水路交通；(3) 每条