数据结构课程设计题目.doc

选题要求：1. 一人一题，不得相同；2. 如果要选以下所给参考题目以外的，请务必给我确认后再做；第1周做设计，第2周写报告；1 图的建立与拓扑排序以邻接矩阵的方式确定一个图，完成：建立并显示出它的邻接链表；对该图进行拓扑排序，显示拓扑排序的结果，并随时显示入度域的变化情况；2 图的建立与关键路径以邻接矩阵的方式确定一个图，完成：建立并显示出它的邻接链表；给出它的关键路径（要求：显示出VE，VL，E，L，L-E的结果）。3 图的建立与与最小生成树以邻接矩阵的方式确定一个图，完成：建立并显示出它的邻接链表；分别用普里姆算法和克鲁斯卡尔算法构造其最小生成树，随时显示其构造的过程；4 图的建立与最短路径以邻接矩阵的方式确定一个图，完成：建立并显示出它的邻接链表；给出某一确定顶点到所有其它顶点的最短路径；5.图的建立与广度优先遍历以邻接矩阵的方式确定一个图，完成：建立并显示出它的邻接链表；进行广度优先遍历，显示遍历的结果，（并随时显示队列的入、出情况）；6. 二叉树的各种遍历方法的实现建立一棵二叉树，完成：对它进行先序、中序、后序遍历;给出遍历过程中栈的变化情况；7哈夫曼编码与译码 (1)输入一组字符集的大小、字符及权值，建立哈夫曼树，显示该哈夫曼树，并给出每个字符的哈夫曼编码 (2)给出一串字符，按照已建立的哈夫曼树进行编码，显示结果或存入文件 (3)用(2)的结果，按照哈夫曼树进行译码。8. 二叉排序树的建立和删除给出一组关键值，建立相应的二叉排序树，完成结点的删除操作。要求可以实现删除根结点、叶子结点以及其它任意结点的功能；随时显示操作的结果。9. 多种排序方法的算法实现几种排序，随时给出某一趟的变化情况直接插入排序、折半插入排序、希尔排序；冒泡排序、快速排序；简单选择排序(4)堆排序10. 算术表达式处理算法实现要求是：(1)从键盘输入一个表达式，如（23-（45.2-2.8）/5=(2)支持+，-，/,( )等符号 (3)支持运算符的优先级(4)支持括号的嵌套(5)支持小数点及负数 (6)有查错功能，如非法字符，小数点过多（如3.44.3），括号不匹配等错误。11. 任意长的整数加法问题描述：设计一个程序实现两个任意长的整数的求和运算。基本要求：利用双向循环链表，设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000。12. 串的查找和替换问题描述：打开一篇英文文章，在该文章中找出所有给定的单词，然后对所有给定的单词替换为另外一个单词，再存盘13. 一元多项式简单计算问题描述：设计一个一元多项式简单的计算器。基本要求：一元多项式简单计算器的基本功能为： (1) 输入并建立多项式；(2)输出多项式；(3)两个多项式想加，建立并输出和多项式；(4)两个多项式相减，建立并输出差多项式。 实现提示：可选择带头结点的单向循环链表或单链表存储多项式，头结点可存放多项式的参数，如项数等。 14. 八皇后问题 要求：试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法，并给出所有的解。 提示：在国际象棋上放置皇后时，任何一个皇后的水平、竖直和斜45都不能有另一个皇后。解决该问题采用逐次试探的方法，即采用递归调用putchess函数的方法。首先将第一个皇后放于第一行第一列，然后开始向下一行递归。每一步递归中，首先检测待放置位置是否与已放置的皇后冲突，如不冲突，则进行下一行的放置，否则，选择该行的下一个位置进行检测。如整行的位置都冲突，则回到上一行，重新选择位置。 15. 稀疏矩阵运算器 问题描述 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。 基本要求以三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示而运算结果的矩阵则以通常的阵列形式列出。 实现提示 1首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。可设矩阵的行数和列数均不超过20。 2程序可以对三元组的输入顺序加以限制，例如，按行优先。 3在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可用二维数组存放。16. 迷宫问题 问题描述：迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 要求：在给出入口和出口的前提下，给出动态的迷宫行走路线。17. 括号匹配问题问题描述：假设一个算术表达式中可包含三种括号：圆括号，方括号和花括号且这三种括号可按任意次序嵌套使用。试利用栈的运算，编写判别给定表达式中所含括号是否正确配对出现的算法。18 . 运算器 问题描述：加减乘运算器。 要 求：使用给定文件进行输入输出，必须采用双向链表实现任意位数的正负整数或小数的加法、减法和乘法运算。每个结点存储一位数字。算出的结果若是小数，整数部分的高位若为0要去掉，小数部分的低位若为0要去掉，若0085.56700，最后结果应为85.567。 文件说明：给定的文件a*.txt为第一个数，b*.txt为第二个数，要求加法产生的结果存储在add*.txt中，减法产生的结果存储在sub*.txt中，乘法产生的结果存储在mul*.txt中，*为对应的一组数据.19.文章编辑功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；20. 电话号码查询系统问题描述：设计一个电话号码查询系统，要求采用哈希表方法实现查找，实现分别按电话号码排序和用户排序的功能 设计要求： 1 设每个记录有下列数据项：电话号码、用户名、地址。 2 从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表。 3 采用再哈希法解决冲突。 4 查找并显示给定电话号码的记录。 5 查找并显示