数据结构(一)数据结构概述


数据结构大致包含以下几种存储结构:

  • 线性表,还可以细分为顺序表链表队列
  • 结构,包括普通树,二叉树线索二叉树等;
  • 存储结构;

线性表

线性表结构存储的数据是可以依次排列的,每个数据前后只有一个数据排列,具备这种“一对一”关系的数据就可以使用线性表来存储。

例如,存储类似于{1,3,5,7,9}这样的数据时,各元素依次排列,每个元素前后有且仅有一个元素与之相邻(除首尾元素),因此可以使用线性表存储。

线性表并不是一种具体的存储结构,它包含顺序存储结构和链式存储结构,是顺序表和链表的统称。

1.顺序表

顺序表简单的理解,就是常用的数组,例如:


图1:顺序表结构

由于顺序表结构的底层实现借助的就是数组,对于初学者来说,可以把顺序表等价为数组,但实则并不是这样。

2.链表

使用顺序表(底层靠数组实现)时,需要提前申请一定大小的存储空间,这块存储空间的物理地址是连续的 图1所示。

链表则完全不同,使用链表存储数据时,是随用随申请,因此数据的存储位置是分离的,换句话说,数据的存储位置是随机的。

为了给各个数据块建立“依次排列”的关系,链表给各数据块增设一个指针,每个数据块的指针都指向下一个数据块(最后一个数据块指向null),这样数据块就建立了“依次排序”的关系,也就形成了链表。如图2

图2:链表结构

3.栈和队列

栈和队列隶属于线性表,是特殊的线性表,因为他们对线性表中元素的进出做了明确的要求。

栈中的元素只能从线性表的一端进出(另一端封死),且要遵循“先入后出”的原则,即先进栈的元素后出栈。


图3:栈结构

队列中的元素只能从线性表的一端进入,从另一端出,且要遵循“先入先出”的特点,即先进队列的元素也要先出队列。如图4


图4:队列结构

树存储结构适合存储具有“一对多”关系的数据


图5:树结构

如图5所示,其中张平只有一个父亲,但他却有两个孩子,这就是“一对多”的关系,满足这种关系的数据可以使用树存储结构。


图存储结构适合存储具有“多对多”关系的数据。


图6:图结构

如图6所示,从V1可以到达V2、V3、V4,同样从V2、V3、V4也可以到达V1,这就是“多对多”的关系,满足这种关系的数据可以使用图存储结构。


算法的时间复杂度和空间复杂度

1.好算法的标准

  • 对于一个问题的算法来说,首先必须能够解决这个问题(准确性
  • 通过这个算法编写的程序要求在任何情况下不能崩溃(健壮性
  • 准确性健壮性都满足之后,要考虑算法运行时间(时间复杂度)和算法所需的内存空间大小(空间复杂度

人们对于软件或者 APP 的运行效率有极高的要求,例如对于网页打开的忍耐极限是 6 秒甚至更短,如果你设计的网页打开的时间超过 6 秒,多数人会在 4 秒甚至 3 秒的时候毫不犹豫地关掉而去浏览其他网页。在这个大背景下,一个好的“算法”更注重的是时间复杂度,而空间复杂度只要在一个合理的范围内就可以。

2.时间复杂度的计算

算法的时间复杂度,主要看算法中使用到的循环结构中代码循环的次数(称为频度),次数越少,时间复杂度越低。

时间复杂度的表示

O(频度) 这种表示方式称为大“O”记法

例如:
a) ++x; s=0;
b) for (int i=1; i<=n; i++) { ++x; s+=x; }
c) for (int i=1; i<=n; i++) { for (int j=1; i<=n; j++) { ++x; s+=x; } }
对上述例子而言,a的时间复杂度为O(1),b的时间复杂度为O(n),c的时间复杂度为O(n2)

如果a、b、c组成一断程序,name算法的时间复杂度为O(n2+n+1)
但这么表示是不对的,还需要对n2+n+1进行简化
简化过程分为3步:

  • 去掉运行时间中的所有加法常数 (例如n2+n+1 直接变为n2+n
  • 只保留最高项(n2+n变为n2
  • 如果最高项的系数不是1 去掉系数(例如2n2变为n2

所以最终a、b、c合并而成的代码的时间复杂度为O(n2)

3.常用时间复杂度的排序

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n2)平方阶 < O(n3)立方阶< O(2n)指数阶

4.算法复杂度速查表

图7:颜色描述提示
图8:数据结构操作复杂度

图9:数组排序算法复杂度

图10:图操作复杂度

图11:堆操作复杂度

图12:大O复杂度图表

5.时间换空间与空间换时间

算法的时间复杂度和空间复杂度可以相互转化。

谷歌浏览器相比于其他的浏览器,运行速度要快。是因为它占用了更多的内存空间,以空间换取了时间。

算法中,例如判断某个年份是否为闰年时,如果想以时间换取空间,算法思路就是:当给定一个年份时,判断该年份是否能被4或者400整除,如果可以,就是闰年。

如果想以空间换时间的话,判断闰年的思路就是:把所有的年份先判断出来,存储在数组中(年份和数组下标对应),如果是闰年,数组值是1,否则是0;当需要判断某年是否为闰年时,直接看对应的数组值是1还是0,不用计算就可以马上知道。


数据的逻辑结构和物理结构

逻辑结构

数据的逻辑结构,简单的理解,就是指数据间的逻辑关系
数据之间的逻辑关系可细分为三类

  • “一对一”:类似集合{1,2,3,4,…,n}这类的数据,每个数据的左侧有且仅有一个数据与其相邻(除1外);同样,每个数据的右侧也只有一个数据与其相邻(除n外),所有的数据都是如此,就说数据之间是“一对一”关系

  • “一对多”:一个节点下面有多个节点,就是”一对多”关系 (树)

  • “多对多”:多个节点对多个节点 且互相可达,他们就是“多对多”关系(图)

三种存储结构分别存储这三类逻辑关系的数据,换句话说:
1.线性表用于存储具有“一对一”逻辑关系的数据
2.树结构用于存储具有“一对多”关系的数据
3.图结构用于存储具有“多对多”关系的数据

物理结构

数据的存储结构,也就是物理结构,指的是数据在物理存储空间上选择集中存放还是分散存放。

图13:数据的物理存储方式

如果选择集中存储,就使用顺序存储结构;反之,就使用链式存储。至于如何选择,主要取决于存储设备的状态以及数据的用途。

集中存储(底层实现使用的是数组)需要使用一大块连续的物理空间,假设要存储大小为 1G 的数据,若存储设备上没有整块大小超过 1G 的空间,就无法使用顺序存储,此时就要选择链式存储,因为链式存储是随机存储数据,占用的都是存储设备中比较小的存储空间,因此有一定几率可以存储成功。

并且,数据的用途不同,选择的存储结构也不同。将数据进行集中存储有利于后期对数据进行遍历操作,而分散存储更有利于后期增加或删除数据。因此,如果后期需要对数据进行大量的检索(遍历),就选择集中存储;反之,若后期需要对数据做进一步更新(增加或删除),则选择分散存储。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 215,923评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,154评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 161,775评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,960评论 1 290
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,976评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,972评论 1 295
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,893评论 3 416
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,709评论 0 271
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,159评论 1 308
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,400评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,552评论 1 346
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,265评论 5 341
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,876评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,528评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,701评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,552评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,451评论 2 352