1、数据结构与数据库实验课作业和要求实验一、线性表的应用：稀疏一元多项式运算器实验目的: 熟练掌握指针和链表操作的基本功 熟练掌握数组操作的基本功 模块化程序设计（程序的分层结构、函数的功能和接口） 人机交互界面设计（界面美观，使用方便、操作的弹性好） 源程序的书写风格（缩进式，加注释，可读性要好） 对程序健壮性的处理 程序的调试技术训练(debug 方法和测试数据的选择) 时空效率实验学时：第 1,2,3,4 次实验完成实验内容：基本功能（必做）：1. 创建2. 显示3. 复制4. 求和5. 求差6. 求值7. 销毁8. 清空9. 修改（插入新的结点、删除已有结点、修改已有结点的系数和指数）拓展
2、功能（选做）：10. 微分（N 阶导数）11. 不定积分12. 定积分13. 乘法和乘方14. 除法15. 最大公约式和最小公倍式16. 多项式的四则运算（如 “(1+2*3)/4”）数据组织： 多项式用带头结点的单链表表示 用指针数组存放 N 个多项式的头指针存储结构示意图:用户操作界面：推荐用菜单驱动实验二、栈的应用实验目的： 掌握栈的后进先出特点 掌握栈的表示和实现技术 掌握如何运用栈的特点来构建算法实验内容（在题目 16 中任选 1 题）：题目 1. 简单的行编辑器（提高难度：实现对文本文件的编辑）题目 2. 括号配对检验（提高难度：实现对括号优先级的检测）题目 3. 波兰式计算（提高
3、难度：操作数为浮点数）题目 4. 逆波兰式计算（提高难度：操作数为浮点数） 题目 5. 中缀式计算（提高难度：操作数为浮点数）题目 6. 迷宫求解（提高难度: 随机迷宫、最短路径的提取）附加题：一般表达式的计算，即在表达式中包含其他函数的运算，如: 2.53*tan(sin(1.2)+cos(3.5)实验学时：第 5 次实验课当堂完成实验三、二叉树的运算实验目的： 掌握二叉树的递归特性 掌握二叉树的常用存储结构-二叉链表 掌握二叉树的创建、遍历等基本运算 了解递归函数的执行过程，学会编写递归程序实验内容：（在题目 1、2 中任选 1 题）题目 1. 二叉树运算 1. 创建二叉树2. 遍历二叉树
4、（先序、中序、后序、层序遍历）3. 二叉树的计算（二叉树的结点数、叶子数、高度、宽度等）4. 二叉树的处理（复制、销毁）题目 2.哈夫曼编码和解码1. 输入电文串2. 统计电文字符集和每种字符在电文中出现的次数3. 构建 huffman 树4. 产生每种字符的 huffman 编码5. 将电文串翻译成比特流6. 对电文比特流进行解码附加题：用 huffman 压缩技术实现对文件的压缩和解压缩处理实验学时：第 6 次实验课当堂完成实验四、图实验目的： 掌握图的两种存储结构: 邻接矩阵表示法和邻接表表示法 掌握图的 DFS 遍历和 BFS 遍历的算法 学会利用图的模型来编程解决实际应用问题实验内容
5、：（在题目 1、2、3 中任选 1 题）题目 1. 图的遍历1. 创建图 G（任选邻接矩阵或邻接表）2. 显示图3. 深度优先搜索遍历图4. 广度优先搜索遍历图5. 在图中插入顶点6. 在图中插入边题目 2: 求通讯网的最小代价生成树1. 输入通讯网 G2. 用 Prim 算法构建 G 的最小生成树并输出3. 用 Kruskal 算法构建 G 的最小生成树并输出题目 3. 铁路交通网的最短路径1. 输入铁路交通网 G2. 用 Dijkstra 算法计算从始发站到终点站的最短路径实验学时：第 7 次实验课当堂完成实验五、哈希表实验目的： 掌握哈希表的定义和特点 掌握哈希函数的构造方法和解决冲突的
6、技术，实现哈希造表 掌握哈希表的查找、插入和删除技术 掌握哈希表平均查找长度 ASL 的计算方法实验内容：（1-5 必做，其他选做）1. 输入关键字序列；2. 用除留余数法构建哈希函数，用线性探测法解决冲突，构建哈希表 HT1；3. 用除留余数法构建哈希函数，用拉链法解决冲突，构建哈希表 HT2；4. 分别对 HT1 和 HT2 计算在等概率情况下查找成功和查找失败的 ASL；5. 分别在 HT1 和 HT2 中查找给定的关键字，给出比较次数6. 在 HT1 中删除指定的关键字7. 在 HT1 中插入新的关键字实验学时：第 8、9 次实验课完成实验六 数据库 SQL 语言实验目的：1.熟悉本实
7、验所使用的 DBMS 环境：SQL SERVER 2005, 学会使用 SQL SERVER 客户端工具查询分析器。2.完成 SQL 语言的基本操作：1）创建表2）插入、删除 、修改、查询。3）创建视图实验内容： 1.下载 SQL Server 客户端工具： http:/192.168.50.203/querytool.rar,解压后执行isqlw.exe， 【SQL SERVER(s)】输入 192.168.50.211， 【连接使用】选择“SQL server 身份验证” ，登录名和密码都是 student。 此外，也可以使用实验室机器桌面上的 SQL Server Management
8、Studio Express 登录。登录后显示如下界面，则可以执行 sql 语句了。要注意，pubs 数据库是系统样例数据库，里面提供了 titles 等实验中用到的示例表，student 用户对其只有查询权，不可以修改。学生可以在 student 数据库中创建自己的表，创建表时请按照题目中要求的命名规则来命名。在操作数据库是要注意当前数据库是 pubs 还是 student，可以在界面面的 combox 选择窗口中 选择，也可以使用命令 use pubs 更改当前数据库。2熟悉 pubs 数据库中各个 table 的定义和关系。http:/192.168.50.203/pubs.pdf 3.
9、查询操作(在 pubs 数据库中执行)：1） 无条件查询 查找 pub 库中 authors 表的全部信息。2） 简单条件查询 查找 titles 表中全部书号及书名。 查找 titles 表中价格在 $1518 元之间的书的书名。 查找 titles 表中书名以 T 开头的书号, 书名。 对其他样例表构造各种简单查询条件，进行查询。3） 多条件查询 查找书名起始字符为 T，价格小于$16 元的书名及价格。 查找书名起始字符不为 T 的, 价格大于$16 元的书号, 书名及价格。4） 用连接操作（或嵌套查询）进行查询 对表 titles, publishers 进行查询: 查找出版社的名称以及
10、所出的书名。 对表 authors, titleauthor, titles 进行查询: 查找作者的姓、名和所写的书名。5） 对查询结果排序 查找作者的姓、名、电话号码，并按作者姓、名排列。 查找书名和书的价格，按书价由大到小的次序排列。6） 使用函数进行查找 列出有多少类书。 列出书的定价有多少种。 列出书价最低的书名和书价。 查出书价最高的书名及书价。 列出当年销量的总和。4.表和视图创建及插入1） 建表：创建两个表 S*和 T*，并插入下面内容，其中*是本人的学号( 下同)。S*Title author t_no price QTY计算机原理 张一平 S3092 20.80 200C 语
11、言程序设计 李华 H1298 15.30 300数据库原理 王家树 D1007 22.70 150计算机网络 高明 S5690 18.90 230软件工程 鲁廷璋 S2005 35.00 200T*t_no Page pub-dateS3092 304 1986D1007 280 1993S5006 315 1987S5690 300 1993H1298 210 19892） 用子查询方式建新表 SS*（包含 title 和 price 两个属性） 。3） 用子查询方式建视图 VS*（包含 title 和 QTY 两个属性） 。5.记录的删除与更新1） 删除书名为“计算机网络”的元组。2） 把书价调整到原来价格的 95%。3） 把书号以 D 开头的那些书的书价减掉 2.00 元。实验拓展1）创建存储过程。2）编写简单的数据库应用：可以基于 ASP、PHP 网页。实验学时：第 10 次实验课当堂完成
