分享
 
 
 

数据结构拾遗---序

王朝other·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

数据结构拾遗

一 序

常感喟大二的日子,初学数据结构的时候,曾有个念头萦绕于心:既然成熟的数据结构,便都如此(诸如线性表、树等),已经定型,为何不送入工具词典,就当工具一般需要时查一查如何写,却还要单独开一门课?

时光流逝,大四了,几经回首,刹那间觉得往日的错误的会意,故准备小加整理,送我天下朋友,认真体会数据结构的精要,为此行业,为你我之事业尽力耳。

数据结构为何重要?

为什么不把它送工具词典?为什么,众多网友谈起,都一致认为它是计算机专业与非专业的一个很好的分水岭?学习它,当报何种态度?乃至成什么状态?

若干年前,流行一个公式:

程序=算法+数据结构

我想大家都是熟悉的。这是一个基本的视角,来看待我们的程序。程序是我们计算机专业人员面对现实问题给出的一个模型,一种解决方案。在这个模型中,数据结构是基本因素之一。

这不是偶然的。数据结构,研究的是数据的存储与组织形式,计算机即使为巧妇,也绝对离不开它要处理的数据。数据组织,将深刻的影响你的解题思路,这是上述公式的意义。

如果你看一看现在的大学计算机专业的教学计划,你就会发现这个公式的烙印,还是相当明显的。记得去年还与人争论,大学应该以什么语言为教学语言,结果我是c++的卫道者,现在看来,一门计算机语言,目的不在于让你学结构化程序设计而自卑,也不在于让你学面向对象程序设计而自傲,目的只有一个:让你在与计算机交流的过程,体会计算机解决问题的方式!

当你意识到这一点,以后的路,其实你就可以慢慢的自己走了。

这“以后的路”,比较关键的两点就是算法与数据结构了。数据结构,是让你体会计算机解决问题的方式之途中又一关键站,深化理解计算机解决问题的方式与其中的艺术性,是我们学习这门课程的根本目的。可惜,当年身在庐山中啊。

以此态度,学习数据结构,学习数据组织对问题的解决之深刻影响,为你我之责任。

举例说明。

例1, 排序问题。大家都知道,基于关键码直接比较的排序算法中,平均效率比较好的一个是快速排序。然而对于下面的数据,存储若干String的数组,要求对所有的String进行排序,应该如何做?

在此基础上排序,问题在于移动String,会对排序的效率有很大影响;估计时,除了N,还得考虑String的平均长度M,读者可以做一做这项工作。

但是,我们可以考虑改变数据的组织形式,采用更有效的数据结构,比如对本问题,如果要建 立在已给的数据结构上,我们可以加入一个数组索引,形成如下数据结构:

仅对作为访问String之根据的指针进行排序,String的移动问题不是给解决了吗?

例2, 排序二叉树的不平衡问题与Trie结构。

显然大家知道,排序二叉树的深度,与建立它的序列中的序有很大关系。比如你拿序列

2,7,24,33,36,47,125,324

来建立一个排序二叉树,它的深度竟成了序列的长度。毫无疑问这是个问题。

为何如此,如何解决?数据结构课程告诉我们,原因是排序二叉树是一种基于对象空间分解而组织的数据结构,关键码范围的分解由对象来驱动的。解决方案之一,就是另一种数据结构,避免对象空间分解,改为基于关键码空间分解,则为Trie结构。由后者组织的数据形式,就可以一定程度上避免上述问题。

你现在是否有认同感?

当然,认识、理解计算机解决问题的方式,绝没有就此停止。后面的路还很长。但学习数据结构,就要抱着这样的态度,认识到它的根本性,以及灵活性,去深入的学习,深入的思考。这是一个应有的状态。

网友happycock 曾经深入的讨论过数据结构(大家可以参看他的专栏),自然我也就没有必要详细的去重复。所以我的简短的总结,便叫“数据结构拾遗”,与大家讨论一些普通教材所忽略的,或我认为需要强调的观点,并尽力使它们有趣、有用。

但因个人时间问题,前后或许会有延迟,还请见谅。同样的原因,我不再以程序实现为主,而是尽量的多使用图示说明。当然,也不那么成体系的。

总而言之,我们都承担一份自己的责任,共同进步。由此,或许我有很多考虑不周的地方,间或错误的观点,请大家不要吝啬,指出以免误人。先行谢过。

是为序。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有