icp备案网站管理员有负责吗,短视频培训机构,投标建设用地是哪个网站,logo设计在线生成免费u钙学好数据结构#xff0c;就等于成功了一半。 程序是对现实的模拟#xff0c;现实是由时间和空间组成的#xff0c;高效的人都是用最少的时间、最少的空间来做最伟大的事#xff0c;程序亦是如此。我们要选择最合理的算法和最合理的数据结构#xff0c;来写最好的代码… 学好数据结构就等于成功了一半。 程序是对现实的模拟现实是由时间和空间组成的高效的人都是用最少的时间、最少的空间来做最伟大的事程序亦是如此。我们要选择最合理的算法和最合理的数据结构来写最好的代码这也正是时间复杂度和空间复杂度的要求。
所以学好数据结构选择合理的数据结构降低时空复杂度就等于成功了一半。
我们可以将数据结构分为两大部分线性数据结构和非线性数据结构。
线性数据结构数据元素之间的关系是一对一的。非线性数据结构数据元素之间的关系不是一对一的。
线性数据结构 数据元素之间的关系是一对一的。可以简单地记忆为一根绳子不分叉 这是嘛意思呢
可以这么理解我有一根绳子上面打了好多结我随便找到一个结点不管往哪一端捋都只能找到一个点除非到头了导致没结点了。说白了就是这根绳子没有分叉。
比如我们生活中的排队就是这个模型。你前后最多都只有一个人也就是一对一的。
这个模型有很多衍生物我们来逐个看下。
1. 顺序表 顺序表是紧密相邻的线性数据结构。便于查找元素不便于插入和删除元素。 也就是说顺序表的所有元素都是一个挨一个的。
比如军训时候的排队所有人都在操场内再比如核酸检测时的排队所有人都在检测亭附近前一个人挨着后一个人紧密相邻。
所以顺序表的特点就是相邻
这样就有一个明显的特点因为我们彼此是挨着的那么就等于排好了队。那么我只要知道某个人的位置就能找到他。
那么我们就可以根据这个特点给每个元素定个编号然后根据编号直接找到对应的元素。如下图所示 我们要找第 ii 个人也就是 aiai直接去第 i−1i−1 位置即可这样非常快不用一个一个数。
那有人就说了既然这么方便我们直接全部用顺序表不就行了吗不行
这样找着是很快但是你发现了吗如果少了一个元素后面的所有元素都要往前挪一步插入一个元素后面所有元素都要往后挪一步。就像排队有人插队和离队后面所有人都要挪一步。
那么能不能不挪呢如果不挪就留了个空位那么空位前后的人就没有相邻元素了那么就从空位开始断开了那么就不是顺序表了。所以不行必须挪
综上所述顺序表的特点就是便于查找元素不便于插入和删除元素
那么有没有啥法子能插入和删除时候不挪呢这样就可以专门用来针对低素质群体了。
有链表
2. 链表 链表是非直接相邻的顺序表。便于插入删除不便于查找。 链表跟顺序表是一对“杠精”只要记住顺序表的特点反过来就是链表的特点。顺序表的元素是一个挨一个的链表就是不挨的。
有人可能会问了这不对啊不挨着怎么找到前一个或者后一个元素要是找不到就不是线性表了。
可以找到就是要费点劲。
比如我在北京我爸爸在上海不相邻我能找到他吗能啊我直接根据地址开车过去就行了虽然费劲但是也能找到啊并且这个地址也只能找到他啊。这也满足一对一的关系。
这找得也太费劲了确实费劲。有人要找我但他只有我爷爷的地址就先找到了我爷爷问他要了我爸的地址然后找到了我爸要了我的地址最后根据地址找到了我。
从这里可以看到链表的查找步骤不是直接报个序号就行的而是需要从头开始挨个往下找所以查找费劲也就不便于查找。
那么为什么要这么设计呢因为这样便于插入和删除。比如有一天我爸去了国外那么他只要把我的地址给我爷爷就行了我和我爷爷都不需要搬家这样找我的人还是按照之前的步骤就行如果有一天我爸回来了那么他把他自己的地址给我爷爷然后我把我自己的地址给他就行了仍然不需要搬家。如果是顺序表就惨了估计搬家都搬吐血了。
从这里我们可以看到链表的设计是不需要相邻的它通过上一个元素持有下一个元素的地址来找到下一个元素插入/删除时只需要改变地址即可不需要挪动位置。这样非常便于插入和删除但是不便于查找。
这样通过地址连起来就像一条“链”一样如下图所示 如果我们删除了 aiai我们只需要将 ai−1ai−1 指向的地址改成 ai1ai1 即可。插入元素同理。
所以链表的特点是便于插入删除 不便于查找。
3. 栈 栈是先进后出FILO的线性结构。 栈是一种抽象的数据结构它只要求元素满足先进后出不要求你是怎么存放的。
比如只有一个门的公交车第一个进去的最后才能出来比如冰柜里的雪糕第一个放进去的最后才被取出来再比如碗里的饺子第一个放进去的最后才被吃掉。
这些都有一个特点只有一个口因为只有一个口所以导致最先进去的最后才出来所以就叫先进后出或者叫作 FILOFirst In Last Out。
那么这有啥用呢难不成就是专门用来模拟吃饺子的非也
因为栈是先进后出的所以特别适合用来模拟历史的回溯也就是说逆流而上追溯历史将历史“倒放”一遍。
历史的回放这是啥比如我们打开浏览器打开一个个页面我们关闭的一定是最后打开的换句话说最先打开的反而最后关闭。也就是说如果我们打开的顺序是A-B-C-D那么我们关闭的顺序就是 D-C-B-A。
这给我们的感觉就是将历史记录倒放了一遍。这正是栈的特点。
历史明明是“前天-昨天-今天”这样过来的但是我们回到过去的话却是“今天-昨天-前天”这样经过的这就是对历史的回溯。
栈最常用的地方就是计算机的函数调用不管何种语言最先被调用的一定最后返回比如
functionA() {functionB();
}functionB() {functionC();
}调用顺序是: functionA() - functionB()- functionC()。返回顺序是: functiuonC() - functioB()- functionA()。
functionC()最后被调用却最先被执行完然后把结果返回给functionB()functionB()再执行完毕返回把结果返回给functionA()。
这就是栈最常用的地方所以我们经常说函数栈也就是这个道理。
其实我们可以广义地概括一下栈的使用场景具有对称性。凡是具有对称性要求的场景都优先考虑使用栈。
比如上面的页面返回例子A-B-C-D 和 D-C-B-A这是以 D 为对称轴左右对称的。上面的函数调用也是以functionC()为对称轴左右对称的。
换句话说FILO 就是以最后进来最先出去的那个为对称轴左右对称的凡是有这种要求的都以优先考虑栈。
4. 队列 队列是先进先出FIFO的线性结构。 队列是一种抽象的数据结构它要求元素满足先进先出不要求元素怎么存放。
比如两个门的公交车前面进、后面出那么先进入的人就会先出来再比如汽车排队隧道先进入的先出来。
它们也都有一个特点两个口因为两个口一个进一个出那么先进去的肯定先跑到出口所以就叫先进先出或者叫作 FIFOFirst In First Out。
可以看到队列跟栈相反更适合人们的思维因为它是公平的
它可以用于模拟日常的大部分操作比如下载先点击的就先下载只有前面的下载完了才轮到后面的再比如12306 买票的候补先点击候补的优先出票。
因为队列是先进先出的所以就特别适合对历史的回放。也就是说按照历史顺序将历史“重新演绎一遍”。
比如我们开发一个直播间先进直播间的人肯定排在前面。这时候就可以使用队列。
因为队列是先进先出的也是符合人们正常思维的所以凡是不需要使用栈的地方都可以使用队列。
非线性数据结构 数据元素之间的关系是一对多或者多对多的。 非线性数据结构的关系可能是一对多或者是多对多。一对多的我们称为树多对多的我们称为图。
1. 树 树是一对多的数据结构。适合有层级关系的场景。 我们知道树只有一个根但是却有多个分支每个分支又有多个分支。这特别适合用来模拟分层的场景比如组织结构图、大纲图还有脑图。
最常见的场景就是分页了。
比如从一亿个人中找到一个名字叫张三的人假设名字都不重复怎么找呢一个一个去对比名字是否叫张三吗这太费劲了。
我们可以这样做
先按照名字个数分组两个字名字的分到 A 组三个字名字的分到 B 组四个字名字的分到 C 组。针对每一组再按照姓氏分姓王的分到王组姓张的分到张组。然后针对每个姓氏组再按照名字的笔画分组“三”有 3 笔就被分到 3 组。
这样我们就好找了。张三两个字去 A 组姓张去张组名字是 3 笔去 3 组。也就是A 组的张组的 3 组。这里只有几千个人了很好找了。
这里的整个一亿人就是一棵树A 组、B 组、C 组分别是主枝干王组、张组是次一级枝干1 组、2 组、3 组又是次一级枝干每个人都是一片叶子。
可以看到有明显的层次关系这样划分得更清晰也更好找。
再比如书的目录、部门的组织关系等等都很适合用树来表示。
到这里我们总结下树的特点一对多有层级关系适合分页。
2. 图 图是多对多的数据结构。适合没有层级的网状关系。 既然树适合有层级的场景那么没有层级的呢就可以用图了。
比如手机联系人我有我家人的、我朋友的家人又有家人的家人又有他们的朋友的……如此就形成了一张大网这张网里的所有人都是平等关系又都是多对多的这就适合用图来表示了。
假如我们要做一个城市的地图或者要做一个朋友圈关系网我们就可以采用图。
有人说图是平级关系那么我们的城市地图有拥挤程度朋友圈也有重要朋友和不重要朋友怎么表示呢这个就可以使用加权图了这是更详细的划分了本章我们不做过多介绍。
这里说的“层级”不是关系的重要程度而是是否存在着主次关系如果有了主次关系那就不适合使用图了。
图的使用除了日常的模型模拟之外还有路径规划、拓扑排序等很多场景我们后面会细讲。
总结
本章从整体讲解了数据结构的划分以及它们的特点和使用场景有点流水账的味道。我们再来梳理和回顾一下。
线性数据结构元素之间是一对一的关系。非线性数据结构元素之间是一对多或多对多的关系。顺序表紧密相邻的线性数据结构便于查找不便于插入删除。链表不相邻的线性数据结构便于插入删除不便于查找。栈先入后出的线性数据结构适合对历史的回溯。队列先入先出的线性数据结构适合对历史的回放。树一对多的非线性数据结构适合有层级关系的场景。图多对多的非线性数据结构适合无层级关系的场景。
我们这部分讲的内容都是抽象的并不涉及具体的实现因为我们只有先从顶层了解了它们的概念和特点后再带着这些已有理解去看具体实现会有更深刻的印象记得也更牢。后面我们就从具体的实现来看一下每一种数据结构的具体使用场景以及在代码中的精彩表现。 程序员的必修课 - 奔波儿灞取经 - 掘金小册数据结构计算机网络操作系统设计模式软硬兼修深入浅出带你夯实程序员基本功。「程序员的必修课」由奔波儿灞取经撰写610人购买https://s.juejin.cn/ds/BoPu7q4/
