《数据结构(Java版)》课程设计任务书.doc

课程设计任务书 课 程 名 称 数据结构 院（系、部、中心） 计算机工程学院 专 业 计算机科学与技术 班 级 软件101 起 止 日 期 2011.12.1212.16 指 导 教 师 叶核亚 1课程设计应达到的目的课程设计是巩固所学理论知识、提高程序设计能力的重要实践环节。数据结构课程设计的目的是，深入理解数据结构的基本理论，掌握对数据结构各种操作的算法设计方法，增强对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力，在实践中培养独立分析问题和解决问题的作风和能力。2课程设计题目及要求数据结构课程设计的要求是，综合运用数据结构的基础知识和算法设计的基本原则，独立编制一个具有中等规模的、一定难度的、解决实际问题的应用程序；通过题意分析、选择数据结构、算法设计、编制程序、调试程序、软件测试、结果分析、撰写课程设计报告等环节完成软件设计的全过程，完善算法并提高程序性能。参考选题及要求说明如下，选题次序的规则由各班级约定，要求每人一题，不重复，带*题较难。（1） 多边形表示和运算（顺序表）声明多边形类Polygon，使用顺序表存储多边形的多个坐标点Point类，支持插入、删除点，实现求多边形周长、面积等运算，以及共用边的两个多边形合并等操作，分析算法效率。（2） 多边形表示和运算（单链表）（3） 多边形表示和运算（循环双链表）（4） 学生成绩表的存储和管理（排序顺序表）声明学生类Student，使用排序顺序表存储和管理学生成绩表，实现以下功能： 提供学生对象的插入、删除、查找操作。 存储和管理学生的多门课程成绩。 提供学生成绩查询操作。 提供统计指定课程的平均值功能。 提供指定课程按优秀、良好、中等、及格、不及格五个等级统计人数功能。 指定学生成绩表按学号排序，或按成绩排序。 将学生信息写入记录文件，并能够从记录文件中读取学生信息。（5） 学生成绩表的存储和管理（单链表）（6） 学生成绩表的存储和管理（双链表）（7） 学生成绩表的存储和管理（循环双链表）（8） 学生成绩表的存储和管理（索引单链表（类似图的邻接表）（9） 学生成绩表的存储和管理（二叉排序树）（10） 二元多项式的表示和运算（排序顺序表）使用排序顺序表存储二元多项式，实现二元多项式相加和相乘等运算，分析算法效率。（11） 二元多项式的表示和运算（排序单链表）使用排序单链表存储二元多项式，实现二元多项式相加和相乘等运算，分析算法效率。（12） 二元多项式的表示和运算（排序循环双链表）（13） 三元多项式的表示和运算（排序顺序表）使用排序顺序表存储三元多项式，实现三元多项式相加和相乘等运算，分析算法效率。（14） 三元多项式的表示和运算（排序单链表）（15） 三元多项式的表示和运算（排序循环双链表）（16） *m元多项式的表示和运算（17） 字符串查找和替换实现文本文件的查找和替换字符串功能，并设置区分大小写、全字匹配、使用通配符等选项。（18） 使用栈计算表达式值改进例4.2计算表达式值，要求同时使用运算符栈和操作数栈，省略转换成后缀表达式过程，并增加关系等运算符，为各运算符约定优先级，设置若干优先级。将运算符及其优先级声明为运算符对象。（19） 求解素数环问题的所有解完善例4.3，给定一个初始序列，采用回溯法求解素数环问题的所有解。（20） *用递归算法求表达式值表达式的BNF语法定义见实验4。要求增加关系等运算符，为各运算符约定优先级，设置若干优先级。将运算符及其优先级声明为运算符对象。（21） *带变量的表达式求值设一个表达式中带有多个变量标识符，要求： 识别出其中所有变量标识符； 为所有变量标识符设置取值； 对于任意一组变量取值，求得表达式的运算结果值。（22） 矩阵类例5.1矩阵类增加深拷贝构造函数、矩阵相加（+）、矩阵转置、判断三角矩阵、判断对称矩阵、判断矩阵相等、矩阵相乘等功能。（23） 压缩存储下三角矩阵线性压缩存储下三角矩阵，实现构造函数、深拷贝、矩阵相加（+=和+）、比较相等、转置等功能。（24） 压缩存储上三角矩阵使用三角形的动态二维数组压缩存储上三角矩阵，实现构造函数、深拷贝、矩阵相加（+=和+）、比较相等、转置等功能。（25） 稀疏矩阵三元组顺序表稀疏矩阵三元组顺序表类增加深拷贝构造函数、矩阵相加(+)、比较相等、转置等功能。（26） 稀疏矩阵三元组排序顺序表使用排序顺序表作为成员变量声明稀疏矩阵三元组顺序表类，实现构造、深拷贝、矩阵相加（+=和+）、比较相等、转置等功能。（27） 稀疏矩阵三元组单链表使用单链表作为成员变量声明稀疏矩阵三元组单链表类，实现构造、深拷贝、矩阵相加（+=和+）、比较相等、转置等功能。（28） 稀疏矩阵三元组排序单链表使用排序单链表作为成员变量声明稀疏矩阵三元组单链表类，实现构造、深拷贝、矩阵相加（+=和+）、比较相等、转置等功能。（29） 稀疏矩阵三元组双链表使用双链表作为成员变量声明稀疏矩阵三元组双链表类，实现构造、深拷贝、矩阵相加（+=和+）、比较相等、转置等功能。（30） 稀疏矩阵三元组排序双链表使用排序双链表作为成员变量声明稀疏矩阵三元组双链表类，实现构造、深拷贝、矩阵相加（+=和+）、比较相等、转置等功能。（31） 稀疏矩阵三元组循环双链表使用循环双链表作为成员变量声明稀疏矩阵三元组循环双链表类，实现构造、深拷贝、矩阵相加（+=和+）、比较相等、转置等功能。（32） 稀疏矩阵三元组排序循环双链表使用排序循环双链表作为成员变量声明稀疏矩阵三元组循环双链表类，实现构造、深拷贝、矩阵相加（+=和+）、比较相等、转置等功能。（33） 稀疏矩阵行的单链表稀疏矩阵行的单链表类增加矩阵相加（+）、转置等功能。（34） 稀疏矩阵行的单链表使用排序单链表作为成员变量声明稀疏矩阵行的单链表类，实现构造、深拷贝、矩阵相加（+=和+）、比较相等、转置等功能。（35） 稀疏矩阵行的双链表使用双链表作为成员变量声明稀疏矩阵行的双链表类，实现构造、深拷贝、矩阵相加（+=和+）、比较相等、转置等功能。（36） 稀疏矩阵行的双链表使用排序循环双链表作为成员变量声明稀疏矩阵行的双链表类，实现构造、深拷贝、矩阵相加（+=和+）、比较相等、转置等功能。（37） 稀疏矩阵列的单链表声明稀疏矩阵三元组列的单链表类，实现构造、深拷贝、矩阵相加（+=和+）、比较相等、转置等功能。（38） 稀疏矩阵列的单链表使用排序单链表作为成员变量声明稀疏矩阵三元组列的单链表类，实现构造、深拷贝、矩阵相加（+=和+）、比较相等、转置等功能。（39） 稀疏矩阵列的双链表使用循环双链表作为成员变量声明稀疏矩阵三元组列的双链表类，实现构造、深拷贝、矩阵相加（+=和+）、比较相等、转置等功能。（40） 稀疏矩阵列的双链表使用排序循环双链表作为成员变量声明稀疏矩阵三元组列的双链表类，实现构造、深拷贝、矩阵相加（+=和+）、比较相等、转置等功能。（41） *稀疏矩阵三元组十字链表稀疏矩阵三元组十字链表类增加深拷贝、矩阵相加（+）、比较相等、转置等功能。（42） *不带表名的广义表以广义表双链表示不带表名的广义表类，增加广义表的删除、查找原子、比较相等、复制等操作；并增加功能，使之能表示递归表。（43） *带表名的广义表声明以广义表双链表示带表名的广义表类，实现广义表的遍历、插入、删除、查找原子、比较相等、复制等操作；并增加功能，使之能表示递归表。（44） 求二叉树中两结点最近的共同祖先结点采用二叉链表表示二叉树，返回两结点最近的共同祖先结点，判断是否子树。（45） 求一棵二叉树的所有直径及其路径长度（46） 静态三叉链表表示的二叉树声明静态三叉链表表示的二叉树类，实现第6章二叉树的基本操作，以及求最近祖先结点、求直径、以广义表构造并输出二叉树、判断是否为完全二叉树等操作，并与二叉链表存储结构进行比较。（47） *表达式二叉树采用创建表达式二叉树的方法计算表达式值。要求增加关系等运算符，为各运算符约定优先级，设置若干优先级。将运算符及其优先级声明为运算符对象。（48） 中序线索二叉树采用三叉链表结构表示中序线索二叉树，实现插入、删除、求父母结点等操作。（49） 先序线索二叉树构造先序线索二叉树，实现求后继结点、遍历、插入、删除、求父母结点等操作。（50） 后序线索二叉树构造后序线索二叉树，实现求前驱结点、遍历、插入、删除、求父母结点等操作。（51） *给定一个文本文件，统计其中字符使用频率，建立一棵Huffman树，采用变长的二进制位串表示字符的Huffman编码，计算压缩比，并设计Huffman编码的译码算法。（52） 采用三叉链表表示构造一棵Huffman树并求编码。（53） 树的父母孩子链表存储（横向凹入构造）以父母孩子链表存储树，以树的横向凹入表示构造或输出一棵树，支持插入结点和删除子树，判断是否子树。（54） 树的父母孩子链表存储（广义表构造）以父母孩子链表存储树，以树的广义表（字符串）表示构造或输出一棵树，支持插入结点和删除子树，判断是否子树。（55） 树的父母孩子兄弟三叉链表（横向凹入构造）为树的孩子兄弟链表结点增加指向父母结点的链，构成树的父母孩子兄弟三叉链表存储结构，以树的横向凹入表示构造或输出一棵树，支持插入结点和删除子树，判断是否子树。（56） 树的父母孩子兄弟三叉链表（广义表构造）以父母孩子兄弟三叉链表存储树，以树的广义表（字符串）表示构造或输出一棵树，支持插入结点和删除子树，判断是否子树。（57） 求树中两个结点最近的共同祖先结点，树的父母孩子链表存储。（58） 求树中两个结点最近的共同祖先结点，树的孩子兄弟链表存储。（59） 求树中两个结点最近的共同祖先结点，树的父母孩子兄弟链表存储。（60） 求一棵树的所有直径及其路径长度，树的父母孩子链表存储。（61） 求一棵树的所有直径及其路径长度，树的孩子兄弟链表存储。（62） 求一棵树的所有直径及其路径长度，树的父母孩子兄弟链表存储。（63） 以邻接表存储带权图，采用Prim算法求图的最小生成树和最短路径。（64） 以邻接表存储带权图，采用Dijkstra算法求图的单源最短路径。（65） 以邻接表存储带权图，采用Floyd算法求图所有顶点间的最短路径。（66） *返回两个顶点、的路径长度；当=时，返回0；当与不连通时，返回-1。算法与图的存储结构无关。（67） *返回两个顶点之间的所有路径及其路径长度，算法与图的存储结构无关。（68） *判断指定的一条路径是否为回路，算法与图的存储结构无关。（69） *判断一个无向图是否为连通图，算法与图的存储结构无关。（70） *判断一个有向图是否为强连通图，算法与图的存储结构无关。（71） *判断一个无向图是否为一棵树，算法与图的存储结构无关。（72） *求从一个图中任意一个顶点出发的所有遍历路径，算法与图的存储结构无关。（73） *图的邻接多重表表示采用邻接多重表表示存储无向图，实现插入、删除、遍历操作算法。（74） *图的邻接多重表表示采用邻接多重表表示存储有向图，实现插入、删除、遍历操作算法。（75） *以邻接多重表存储无向带权图，采用Prim算法求图的最小生成树。（76） *以邻接多重表存储无向带权图，采用Kruskal算法求图的最小生成树。（77） *以邻接多重表存储无向带权图，采用Dijkstra算法求图的单源最短路径。（78） *以邻接多重表存储有向带权图，采用Dijkstra算法求图的单源最短路径。（79） *以邻接多重表存储无向带权图，采用Floyd算法求图所有顶点间的最短路径。（80） *以邻接多重表存储有向带权图，采用Floyd算法求图所有顶点间的最短路径。（81） 统计字符出现次数在一个字符串中统计各字符的出现次数，分别采用顺序表和散列表存储，分析查找效率。（82） 统计单词出现次数从指定文本文件中统计出各单词及其出现次数，分别采用顺序表和散列表存储，分析查找效率。（83） 互异的随机数序列生成一个具有n个整数的互异随机数序列，范围是-sizesize。怎样实现互异？有哪些存储结构可以存储随机数序列？分析它们的特点、功能和查找效率，有哪些提高查找效率的措施？（84） 互异的排序随机数序列生成一个具有n个整数的互异的排序随机数序列，范围是-sizesize。有哪些存储结构可以存储随机数序列？分析它们的特点、功能和查找效率，有哪些提高查找效率的措施？（85） 选票统计设一次选举有n个候选人，设计一种选票格式及计票程序，统计所有选票数量、每个候选人的得票数和得票率，将候选人及其得票数和得票率按得票数降序排序输出。如果不限定候选人数，则可采用什么结构？分别说明所采用的数据结构和算法，分析各数据结构的查找性能，及查找和排序算法效率，说明查找性能与哪些因素有关，说明为提高查找效率通常采用的措施。（86） 电话簿的存储与查找（排序顺序表）采用排序顺序表存储电话簿数据元素，按姓氏排序，实现查找、增加和删除元素操作，分析各算法效率。（87） 电话簿的存储与查找（排序循环双链表）采用排序循环双链表存储电话簿数据元素，按姓氏排序，实现查找、增加和删除元素操作，分析各算法效率。（88） 电话簿的存储与查找（索引单链表）采用索引单链表（类似图的邻接表）存储电话簿数据元素，按姓氏建立索引表，每个索引项指向一条同姓的单链表，采用分块查找技术，支持增加和删除元素操作，分析各算法效率。索引表可按姓氏排序。（89） 电话簿的存储与查找（二叉排序树）采用二叉排序树存储电话簿数据元素，元素按姓氏排序，实现查找、插入和删除元素操作，分析各算法效率。（90） 电话簿的存储与查找（树形结构分类，树的广义表表示）设计电话簿存储结构，要求按类似以下树形结构分类，并将该棵树保存在文本文件中。实现查找、插入和删除元素操作，分析各算法效率。全部（同学（中学同学，大学同学，研究生同学），同事（计算机系，通信系）（91） 电话簿的存储与查找（树形结构分类，树的横向凹入）设计电话簿存储结构，要求按类似以下树形结构分类，并将该棵树保存在文本文件中。实现查找、插入和删除元素操作，分析各算法效率。全部同学中学同学大学同学研究生同学 同事计算机系通信系（92） 拼写检查准备一份英文或中文字库，对一篇指定文本进行拼写检查，发现并指出其中拼写错误的单词。（93） 统计获奖名单已知有n人报名参加某个比赛，设一三等奖的获奖名额分别为：x、y、z名等，将获奖名额方案保存在指定数组中。研究采用何种存储结构存储参赛者信息及比赛成绩？采用什么方法选择决定获奖者的效率最高？实现一种方案并分析算法效率。（94） *平衡二叉树声明平衡二叉树类，实现平衡二叉树的查找、插入和删除等操作。（95） 使用最小堆构造优先队列声明最小堆类MinHeap，支持插入、删除和返回最小值元素操作。使用最小堆构造优先队列，选择最小权值元素优先出队。（96） 使用最大堆构造优先队列声明最大堆类MaxHeap，支持插入、删除和返回最小值元素操作。使用最大堆构造优先队列，选择最大权值元素优先出队。（97） *使用最小堆构造Huffman树（98） *使用最小堆实现Prim算法求带权图的最小生成树（99） *使用最小堆实现Kruskal算法求带权图的最小生成树（100） *使用最小堆实现Dijkstra算法求带权图的单源最短路径（101） *使用最小堆实现Floyd算法求带权图所有顶点间的最短路径3课程设计任务及工作量的要求包括课程设计计算说