数据结构的上机作业答案

实验1： 1）熟悉Vc 6.0环境 2）用两种算法实现1-1/x+1/x*x-1/x*x*x+1/x*x*x*x….， 注（algo1-1,algo1-2） 实验2：线性表 1） 顺序表的合并：实现书中P26中算法2.7，La=1 2 3 4 5, Lb=2 4 6 8 10。要求得到合并后的Lc=1 2 3 4 5 6 8 10 注(algo2-4 ) 2） 一元多项式加法：Pa=Pa+Pb，并销毁一元多项式Pb 3） 一元多项式乘法：Pa=Pa*Pb，并销毁一元多项式Pb 实验3：栈和队列 1） 利用栈求解迷宫问题；行列各为10（包括外墙），迷宫内墙单元数为18。 2） 利用栈和递归求解Hanoi塔问题，圆盘数3。 3） 利用非循环顺序队列采用广度搜索法求解迷宫问题（一条路径）；行列各为5（包括外墙），迷宫内墙单元数为2。 实验4：串 1） 模式匹配改进算法：KMP算法，实现书中4.6,4.7,4.8算法。 实验5： 数组和广义表 1） 求稀疏矩阵的加，乘和转置矩阵。 2） 求广义表的深度。 实验6：树和二叉树 1） 求赫夫曼编码。（w存放n个字符的权值（均>0），构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC） 实验7：图 1）实现教科书中图7.33的程序，并能求出任意两点的最短路径。 实验8：动态存储管理 1） 边界标识法，程序实现教科书中算法8.1 2） 伙伴系统，程序实现教科书中算法8.2 实验9：查找 1） 哈希表的查找及其分析：以书中图9-25为例。 实验10：内部排序 1） 以书中10-4的数据，程序实现直接插入排序，折半排序和2路插入排序。 2） 以书中图10.6的数据，程序实现快速排序。 3） 以书中图10.9的数据，程序实现树形选择排序。 4） 以书中图10.13的数据，程序实现归并排序。 5） 以书中图10.14的数据，程序实现链式基数排序。 实验11： 外部排序 1） 以书中图11.4的数据，程序实现多路平衡归并排序。 2）以书中图11.5的数据，程序实现置换-选择排序。 实验12：文件 1）以书中图12.4的数据，程序实现顺序文件。