chgz的个人博客分享 http://blog.sciencenet.cn/u/chgz

博文

实现了Binary Search Tree 的感想

已有 2308 次阅读 2015-8-15 03:12 |系统分类:科研笔记|关键词:学者

最近看了《Data Structures using C++(D.S. Malik,2010)这本书,实现了Binary Search Tree (BST)的代码,书中给的代码并不完全,ADT中少量的函数作为练习让读者自己思考动手完成。通过阅读这本书,我对C++语言有了更加深刻的理解,学会使用了模板类,学会使用了函数作为参数,学会了模板的编译和应该注意的细节,同时也对递归和回溯有了更加深入的理解;以此书的阅读为驱动,让我学会使用了g++编译器,以及C++11的新特性。这些是阅读这本书带了的一些收获。在我即将阅读完此书时,我想把实现BST的感想写于下面:

l   对某个问题来说,使用链表或者使用BST都可以解决该问题。之所以选择这个而不选择那个基于对程序的性能要求来考虑的,比如,要求执行时间的效率高,占用空间少等。数组存储型链表在搜索方面占优,插入、删除方面吃亏;指针型链表在插入、删除方面占优,而在搜索方面吃亏;但是,BST综合了二者的优点。显然,对应同一个问题来说,选用了BST,就意味着程序的性能有了很大的提高。虽然,现在电脑的硬件发展突飞猛进,CPU的运行速度一再提高,我们现在不像以前那样对程序的性能做强制的要求了,但是在好多种情况下,还是要考虑算法和程序的性能,这也是《算法设计与分析》课程存在的必要性。

l   之前大学时,多《数据结构》课程学习的不深入,认为listBST是用来解决不同的问题的,通过BST的实现,我认识到了:不同的数据结构可以用来解决同一个编程问题。比如在本书中,出现了2次,使用Stack后,将一个递归算法转化为迭代。学习了数据结构以后,让我们有了更多的手段和武器解决同一个问题。

l   学习《数据结构》,最好亲自实现它们,通过实实在在的程序运行,来理解其中的机理。仅仅看书本,会让人感觉到许多概念虚无缥缈,没有一个感性的认识;而实现它后,在编码的同时,你在思考为什么这样,在程序运行后你会根据算法推测为什么是这样的运行结果,所有的这个过程都在促进你的思考。你思考的越多,你理解的就越深刻。比如树的height概念,level概念等等。

l   《数据结构》在软件项目编程中的粒度比较小,但通过该课程学习到的算法的设计与分析方法是任何项目都需要的。具体的数据结构,每个语言中library中都会包含,我们不能因此否定数据结构课程的必要性,重要的是通过这些一个个具体数据结构的设计过程学会算法的设计方法。

上面只是我的粗浅的认识,在以后的学习中,我的认识还会加深。




https://m.sciencenet.cn/blog-1062644-913166.html

上一篇:感悟“简单事情”
下一篇:不解的一个问题--关于学位论文抄袭检测

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2023-2-6 01:10

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部