内容发布更新时间 : 2024/12/23 23:25:53星期一 下面是文章的全部内容请认真阅读。

对《数据结构》教材中算法的改进与优化

: Data Structure（using C++ language）edited by Zhanli Zhu belongs to new century serial textbooks for computer science undergraduate study, and is adopted by some universities.However, weaknesses can be found in the textbook, except for obvious printing errors，the design of Algorithm can be optimized further. Given the weaknesses，this article provides improvement and optimization. 0引言

《数据结构》课程是计算机专业和信息专业的专业基础课，早期一般用清华大学出版严蔚敏编的《数据结构》[2]作为教材，由于该教材是以类C 作为算法描述语言，而C语言的参数传递和指针运算的复杂性，对于刚掌握C语言的初学者，将类C的算法转换成C语言，很难作到变量设计合理，参数传递正确。早期的西安交大出版社出版朱战立编的《数据结构》（使用C语言）的算法全部采用C语言描述，不用作任何修改就可以上机运行，这方面，该教材无疑为初学的学生提供了极大的方便。因此，我们一直选用该教材作为《数据结构》课程的参考书。后来虽然教材选用了C++语言作为算法的描述语言[3]，但我们还是保留选用朱战立编《数据结构》（使用C++语言）[1]作为参考教材.多

年的教学实践中，我们发现该教材还存在一些不足，除了明显的印刷错误外，算法设计也存在一定的错误，有的算法可以作进一步的优化。下面就几个方面提出我们的看法，以就教于大家。 1在Huffman编码的算法中，混淆了叶子结点数和编码的位数

在Huffman编码的算法中，作者混淆了叶子结点个数与编码的位数。n是Huffman树的叶子结点个数，MaxBit是编码的最大位数。由n个结点的哈夫曼树haffTree[]构造哈夫曼编码haffCode[]的函数修改如下，修改处用注释表示。

这里的MaxBit被说明为常量10，所以这个算法当叶子结点数不超过10时，上机运行完全可以通过，但当叶子结点数超过了10，算法就会出现问题，如作上面的修改，则问题清除。这个错误在C语言的版本就出现，到C++语言版本还是存在。 2删除顶点v和与顶点v 相关的所有边的优化算法 以邻接矩阵为存储结构的图，删除与顶点v相关的所有边的算法，原算法如下：

删除与顶点v相关的所有边，只找与v有关的顶点即可，没有必要对所有的顶点都作检查，优化为：

虽然增加几行编码，但这样把一个原复杂度为O（n2）的算法，转化为复杂度为O（n）的算法。 3利用监视哨可以优化直接插入排序算法 直接插入排队序原算法如下：

voidInsertSort(Datatype a[],int n)

//用直接插入法对a[1]―a[n]排序， a[0]为监视哨