(数据结构课程设计201120122.docVIP

《数据结构》课程设计 2011-2012-2 题目一：池塘夜降彩色雨 【问题描述】：设计一个程序，演示美丽的“池塘夜雨”景色；色彩缤纷的雨点飘飘洒洒地从天而降，滴滴入水有声，溅起圈圈微澜。 【基本要求】：（1）雨点的空中出现位置、降落过程的可见程度、入水位置、颜色、最大水圈等，都是随机确定的； （2）多个雨点按照各自的随机参数和存在状态，同时演示在屏幕上。 （3）增加“电闪雷鸣”景象。 （4）增加风的效果，展现“风雨飘摇”的情景 题目二：哈夫曼编码器 【问题描述】：利用哈夫曼树实现编码并译码的系统。 【基本要求】：从终端读入一段字符集，系统自动统计出字符的个数n以及各个字符出现的次数w作为权值，建立哈夫曼树，并将哈夫曼树以凹入表示法的形式显示在屏幕上。利用已建好的哈夫曼树对字符进行编码，并将该段文字的编码存人一个文件code中，然后输出这段编码。 题目三：算术表达式求值演示 【问题描述】：表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示中缀表达式变为后缀表达式并对后缀表达式求值的过程。 【基本要求】：以字符序列的方式从终端输入语法正确的、不含变量的整数表达式。利用中缀表达式变为后缀表达式算法和后缀表达式的求值算法实现对算术四则混合运算表达式的求值，并演示出在求值中运算符栈、操作数栈、输入字符和主要操作的变化过程。 题目四：农夫过河问题 【问题描述】：从前，一个农夫带着一只狼，一只羊和一棵白菜过河（注意该狼已经被农夫驯服了，但还是会吃羊）。他要将所有东西安全的带到河的对岸。不幸的是河边只有一条小船，只能装下农夫和他的一样东西，并且农夫必须每次都随船过河，因为只有他能撑船。在无人看管的情况下，狼要吃羊，羊要吃白菜，因此农夫不能在河的某边岸上单独留下狼和羊，也不能单独留下羊和白菜。那么农夫如何才能使三样东西平安过河呢？ 【基本要求】：1、输出农夫过河问题求解的详细步骤。 2、分别采用深度优先有哪些信誉好的足球投注网站算法和广度优先有哪些信誉好的足球投注网站算法实现。 题目五：运动会分数统计 【问题描述】：参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目，项目编号内分别为1~m和m+1~m+w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。 【基本要求】：产生各学校的成绩单，内容包括各校所取得的各项成绩的项目号、名次（成绩）、姓名和得分；产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。 题目六：校园导游咨询 【问题描述】：设计一个校园导游程序，为来访的客人提供各种信息查询服务。 【基本要求】：（1）设计你的学校的校园平面图，所含景点不少于十个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 （2）为来访的客人提供图中任意景点相关信息的查询。 （3）求出校园平面图的最小生成树。 题目七：最小生成树问题 【问题描述】：若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。 【基本要求】：（1）利用普里姆算法和克鲁斯卡尔算法求网的最小生成树。 （2）利用堆排序实现选择权值最小的边。 （3）输出生成树中各条边以及他们的权值。 题目八：迷宫问题 【问题描述】：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 【基本要求】：1、编写一个求解迷宫的非递归程序，求得迷宫中所有可能的通路。 2、以方阵形式输出迷宫及其通路。 题目九：图遍历的演示 【问题描述】：很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。 【基本要求】：以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 题目十：内部排序算法比较 【问题描述】：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 【基本要求】：(1)对以下六种常用的内部排序算法进行比较：希尔排序、直接选择排序、快速排序、直接插入排序、堆排序、冒泡排序、。 （2）待排序表的表长和数据可以由用户自己确定，也可以由随机数产生程序自动产生；至少要用五组不同的输入数据作比较；比较的指标为关键字的比较次数和关键字的移动次数（关键