2009-6-1
一、大型作业(课程设计)题目与内容。
1.1 算术表达式求值。
输入一个算术表达式，其中操作数必须为实数，运算符包括加、减、乘、除、小（圆）括号，试编写程序实现：
1.用算符优先法求表达式的值。
2.用下列方法求表达式的值：
1)先生成表达式二叉树；
(2)根据表达式二叉树求表达式的值；
(3)先序遍历表达式二叉树；
(4)中序遍历表达式二叉树，要求恢复必要的括号；
(5)后序遍历表达式二叉树，根据后序遍历序列（逆波兰式）求表达式的值；要求能用文件形式存放表达式二叉树，同时能从文件中读入保存的表达式二叉树。
1.2 二叉排序树基本操作的实现。
1.用二叉链表作存储结构
(1)以回车('')为输入结束标志，输入数列l,生成二叉排序树t；
(2)对二叉排序树t作中序遍历，输出结果；
(3)计算二叉排序树t的平均查找长度，输出结果；
(4)输入元素x,查找二叉排序树t,若存在含x的结点，则删除该结点，并作中序遍历(执行操作2)；否则输出信息“无结点x”；
5)判断二叉排序树t是否为平衡二叉树，输出信息“ok！”/no！”；
(6)再用数列l,生成平衡二叉排序树bt:当插入新元素之后，发现当前的二叉排序树bt不是平衡二叉排序树，则立即将它转换成新的平衡二叉排序树bt；
(7)计算平衡的二叉排序树bt的平均查找长度，输出结果。
1.3 图的基本操作的实现。
(1)自选存储结构，输入含n个顶点（用字符表示顶点）和e条边的图g；
(2)求每个顶点的度，输出结果；
(3)指定任意顶点x为初始顶点，对图g作dfs遍历，输出dfs顶点序列(提示：使用一个栈实现dfs)；
4)指定任意顶点x为初始顶点，对图g作bfs遍历，输出bfs顶点序列(提示：使。
用一个队列实现bfs)；
(5)输入顶点x,查找图g:若存在含x的顶点，则删除该结点及与之相关连的边，并作dfs遍历(执行操作3)；否则输出信息“无顶点x”；
(6)判断图g是否是连通图，输出信息“ok！”/no！”；
(7)如果选用的存储结构是顶点数组和邻接矩阵，则用顶点数组和邻接矩阵的数据信息生成图g的邻接表，即复制图g,然后再执行操作(2)；反之亦然。
1.4无向网及其应用
输入若干个旅游城市信息，以及若任意两个城市间通航（车），输入票价，里程，试编写程序实现：
(1)输入创建以城市为顶点的该无向网（要求输入的无向网是连通的）；
(2)求解连通n个城市的总里程最小方案；
(3)任指定两个城市a、b，求从a出发到b的最佳路线（如费用最低或距离最近）；
*(4)从某城市出发，选择若干城市旅游，最后回到出发点，设计一种最佳方案；
*(5) 用图形方式显示无向网，每次选取一种方案时，在图上显示方案图。
注：*(4)、*5)可选做，该题也可以某城市多个旅游景点为背景。
1.5.哈希表及其应用。
建立一个小型信息管理系统（可以是图书、人事、学生、物资、商品等任何信息管理系统）。要求：
1)使用哈希查找表存储信息；
2)实现查找、插入、删除、统计、输出等功能；
3)尝试使用多种哈希函数和冲突解决方法，并通过实际运行测试给出自己的评价。
二、说明和要求。
1.上述5个大型作业题任选3题完成，选作带“*”号的内容；
2.每一种操作用c(或c++)函数实现；
3.下学期第3周五交“大型作业报告书”,有下列所有内容：
1)说明所完成的大型作业题目和内容；
2)简要说明所采用的数据结构及其存储结构（约300个字）；
3)简要说明算法的设计思想（约800个字）；
4)若选作第2题，分析对比未平衡化的二叉排序树和平衡化了的二叉排序树的查找效率(最好情况、最坏情况和平均情况的比较关键字的次数(约400个字)；
5)分析时间复杂度(约200个字)；
6)写出心得和总结（约800个字）；
7)提交打印的程序清单，要求在关键位置加注释；
8)提交电子版c源程序清单；
9)在“报告书”首页写上班号、学号(序号)、姓名。
数据结构课程设计
课程设计说明书 题目哈夫曼编码问题的设计和实现。课程名称数据结构课程设计。院 系 部 中心。专业。班级。学生姓名。学号。设计地点。指导教师。设计起止时间 2008 年6月 2日至 2008 年 6月 6 日。目录。1 问题描述 2 1.1 题目内容 2 1.2 基本要求 2 1.3 测试数据 2 2...
数据结构课程设计
数据结构 课程设计。实验报告。学院 信息工程学院。班级 姓名 学号 指导老师 题目2 一元多项式的计算。1 实验目的。1 掌握链表的灵活运用 2 学习链表初始化和建立一个新的链表 3 知道怎样去实现链表删除结点操作与插入结点 4 理解链表的基本操作 包括数据域数据的相加 并能灵活运用。2 实验内容。...
数据结构课程设计
班级 信计 1102 姓名 李娜娜。学号 1108060209 设计日期 2013.07.15 西安科技大学计算机学院 1.实验题目 编制一个演绎扫雷游戏的程序。2.问题描述。做一个n x m的扫雷游戏，每个方格包含两种状态 关闭 closed 和打开 opened 初始化时每个方格都是关闭的，一个...