老狗啃骨头之数据结构-引言
source link: http://www.veiking.cn/blog/1010-page.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
老狗啃骨头之数据结构-引言_老狗啃骨头_Veiking百草园-知识点滴,日常分享
我们存在的现实世界，是具象的，生活中的各种东西，是几十年反复加强的概念，锅碗瓢盆啤酒饮料矿泉水…但计算机是一个抽象世界，计算机是尝试用抽象的数据，来描述这个具象的世界，我们说，学计算机、学编程，这个东西一定要搞好，现实世界里的概念是如何在计算机里体现的，这时候，数据结构，就是这个体现最基础的东西，其重要性不言而喻
最近有不少朋友都在刷LeetCode 的题，挺有意思，想上学那会儿，严蔚敏老师的那本数据结构，翻得是相当熟练，顺势去鼓捣 ACM ，颇有趣味。工作之后，这有些东西却是慢慢模糊起来，于是想弄一波笔记，给自己长长记性，重温昔日的乐趣。先贴个严老师那时候课本的样子，致敬一下：
数据结构，是咱们计算机科班的必修课，上学那会儿不少同学一开始也是很头痛，为什么呢？个人理解，数据结构这门课，难，倒也不难，但它是一个概念的重塑，所以一开始，对于不少同学就是折磨。
我们存在的现实世界，是具象的，生活中的各种东西，是几十年反复加强的概念，锅碗瓢盆啤酒饮料矿泉水…但计算机是一个抽象世界，计算机是尝试用抽象的数据，来描述这个具象的世界，我们说，学计算机、学编程，这个东西一定要搞好，现实世界里的概念是如何在计算机里体现的，这时候，数据结构，就是这个体现最基础的东西，其重要性不言而喻。
也有人问，数据结构怎么学才能学好啊，其实这种基础的东西，没什么捷径，多练习，在校同学一定要趁着没啥事儿的时候，多照着书撸撸代码，严蔚敏的那本书就挺好了。就好比我们说一个数组，你在怎么打比喻，再怎么去解释，去理解，都是比较肤浅的，直接写个程序，往里塞元素，塞不进去，往里取元素，取不了… 报几下异常，再弄个排序左左右右玩一轮，基本这辈子都忘不了数组这个东西了。
数据结构，不同教材都尝试做一个比较贴又准确的名称定义，但作为一个老狗，再回头去看看，感觉有些还是拧巴，我们不管教材了，当然看看还是好。聊数据结构，就不能不提算法，数据结构就是各种特点的概念盒子、架子，是物件，摆在那里，是个死的，是一个被定义但没有灵魂的东西；算法就是各种折腾的方式、使用的技巧，死的东西折腾起来，就活了，生灵活现！
还拿数组说事儿，一个数组，放在那里有什么意思，一定要玩起来，怎么查怎么找，左一个排序，右一个查找，怎么能再快点，还能不能再快点，出错了再试试….于是，贤者云：
对，说一百圈，我们就是要搞程序的，絮叨完之后，接下来会有几篇笔记，我们将通过程序实践，来重温那些典型的数据结构及其算法。
数据结构，就是数据的结构。我们说数据在计算机里，我们一般说其逻辑结构，简单归类，主要是两种：线性结构和非线性结构。
线性结构，线，顾名思义，一条绳，一根棍，一节管子，一组高铁… 现实中可以明确找出两头的，必须按着顺序来的，都可以拟化成线性结构，所以线性结构一般这么去抽象：
线性结构是一个有序集合；
有且仅有一个开始结点和一个终端结点；
所有结点都最多只有一个直接前结点和一个直接后结点。
我们经常说的，数组、链表，就是典型的线性结构，栈啊队列啊，也都是。
非线性结构，就是相对线性结构而言，排除法，现实中，所有不符合线性结构特点的，都可以拿来拟化。如果说线性结构是相对简单的、独立的，非线性结构就是它的的复杂化、关系化，是一种延伸。一段铁轨，线性，铁路组网，就是非线性；蜘蛛拉丝，线性的吧，编织成网，就是非线性。
所以非线性结构的一个典型特征，就是其节点可以和多个节点有连接关系。
我们经常说的，树、图，都是非线性的。
避免误人子弟，一定要说一下，不少教材，都会明确指出：数组和链表（广义表）是非线性结构。这个在学生考试的时候千万别被我坑了，一定要按照书上的来，考试的时候，他说啥就是啥！
这个是为什么呢，因为，这是一个太过于严谨和刻板的学术定义：一维数组是可以勉强算线性结构，但也有二维数组啊，还有三维四维多维啊，数组元素也可以是各种东西啊…链表（广义表）也差不多类似原因，所以数组和链表（广义表）是非线性结构。
这里来个插曲，小扯一下，这种问题差不多是研究学问研究的有点那啥，更容易给新手学习上带来混乱，这是整体抽象和具体细节的胡搅蛮缠：绳子怎么能拟化成线性概念呢？拿放大镜看，绳子是有很多股更小的纤维缠绕编织而成，复杂的厉害呢，怎么可能是线性的；拿电子显微镜再看，更不得了，这都是各种奇形怪状的碳氢氧氮组成的有机分子，各种钩拉缠绕在相互作用….这不可能是线性概念能说的——所以，绳子是非线性的！
有时候一些概念定义是尝试帮助我们学习的工具，是帮助工具，不是真理，也没什么对错，要知道所以然所以不然，懂了就真懂了，学问勿成学究，它爱是啥是啥，当然，考试还是要走大纲。
好了，聒噪至此，浪费大家时间，略表歉意，稍息片刻，接下来我们就简单的过一下，常见的八种数据结构。
Recommend
-
8
插入排序，一般是说直接插入排序，是一种最直观最简单的排序算法。插入排序的原理是依次将未排序的数据元素插入已完成排序的有序数列，如此往复，最终完成所有数据的排序。在插入排序中，往前遍历的时候，遇到等值的元素就直接插入结...
-
4
简单选择排序是一种相对简单直观的基础排序算法，每一次都做简单选择，每一次都选出最大或最小。选择排序的核心思想就是：在遍历的过程中，每次都选数据样本中最小的数据，放在首位。看起来简单纯朴吧，从第一个元素开始，每次都取剩...
-
5
归并排序是一种非常典型的分治策略应用排序算法，简而概括：分而排之，合而并之。归并排序，据说是冯·诺伊曼在1945年首次提出。冯·诺伊曼，是现代计算机科学发展史上开天辟地的大佬之一，不单单是计算机领域，这哥们在整个数学、量子...
-
8
老狗啃骨头之数据结构-栈和队列_老狗啃骨头_Veiking百草园-知识点滴,日常分享 栈和队列也是比较常见的数据结构，它们是比较特殊的线性表。相对于数组和链表，栈和队列是一种更具特性的场景应用，栈和队列都可...
-
4
冒泡排序是交换排序，是一种简单直观的排序算法。冒泡的算法原理是逐次循环遍历，比较两个相邻的元素，将小的（或大的）往前调。这样，每一轮都能得到一个最小的（或最大的），剩下的重复这个操作，最后完成排序。这个算法的名字，每...
-
5
老狗啃骨头之算法-排序算法总结_老狗啃骨头_Veiking百草园-知识点滴,日常分享 关于排序的算法，还有很多种。还有一些排序算法的思想，在不同的使用场景下再结合其它的算法逻辑，又可以衍生出新的算法设计。比...
-
5
天地玄黄，宇宙洪荒……千年以前，南梁周大侍郎，用一夜白头给我们留下了包罗万象又朗朗上口的童谣，得以千年唱诵，这是古人原始纯真的智慧。但浩瀚如宇宙，细微如尘沙，世间如此繁杂，计算机是搞不懂的，计算机的一零世界努力模拟，也...
-
5
老狗啃骨头之数据结构-小说算法_老狗啃骨头_Veiking百草园-知识点滴,日常分享 一般说，随着数据结构复杂度和解决问题的复杂度的增长，时间复杂度也是随之增长的。在相同的资源条件下，空间复杂度和时间复杂度...
-
6
老狗啃骨头之数据结构-图和散列表_老狗啃骨头_Veiking百草园-知识点滴,日常分享 图也是典型的非线性数据结构，相较于树，更为复杂。线性表和树在逻辑结构上都是没有回路的，图就不一样了，图任意两个元素，都...
-
2
老狗啃骨头之数据结构-树和堆_老狗啃骨头_Veiking百草园-知识点滴,日常分享 树在实际应用中非常广泛，较为具体的是，我们用到的Mysql数据库的索引，就是用B+树实现的；很多Hash结构，底层也是用到了红黑树。...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK