数据结构和算法 Data Structure and Algorithm

参考链接： 后向链与前向链之间的差异

数据结构和算法 Data Structure and Algorithm 

1.链表 (Linked List) 

1.1 概念 

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。 

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。 

当数据量不大时(比如只有一万个数据)，顺序表在所有方面的表现全都优于链表。就连在插入和删除时也是如此。因为链表插入新的结点要构造对象，这是非常耗时的；而在删除时，同于现代的计算机进行复制操作的效率极高，因为表现不比链表差。链表删除时还要执行析构操作，所以会慢不少。当顺序表长度大于一定的值时，插入和删除操作速度就会变得不如链表。链表的缺点主要在于按元素序号随机访问时效率低下。一些其它数据结构，比如图和树，在形式上也类似链表。(当然也有基于顺序表的实现) 

1.2 链表和数组的区别 

https://zhuanlan.zhihu.com/p/52440208 

在知道同类数据的数量范围且不超过静态内存容许值时用数组，编程简单快速。 当你处理权的同类数据的数据量未知时，或者数据量超过静态数组定义范围时，就要用链表。 

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 

普通数组在用户的静态数据空间中分配内存，链表在操作系统的堆中动态分配内存。 

从逻辑结构上来说，这两种数据结构都属于线性表。所谓线性表，就是所有数据都排列在只有一个维度的“线”上，就像羊肉串一样，把数据串成一串。对其中任意一个节点来说，除了头尾，只有一个前趋，也只有一个后继。 

从物理上来说，即在内存中，这两种逻辑结构所对应的物理存储分布上看，数组占用的是一块连续的内存区，而链表在内存中，是分散的，因为是分散的，就需要一种东西把他们串起来，这样才能形成逻辑上的线性表，不像数组，与生俱来具有“线性”的成分。因为链表比数组多了一个“串起来”的额外操作，这个操作就是加了个指向下个节点的指针，所以对于链表来说，存储一个节点，所要消耗的资源就多了。也正因为这种物理结构上的差异，导致了他们在访问、增加、删除节点这三种操作上所带来的时间复杂度不同。 

对于访问，数组在物理内存上是连续存储的，硬件上支持“随机访问”，所谓随机访问，就是你访问一个a[3]的元素与访问一个a[10000]，使用数组下标访问时，这两个元素的时间消耗是一样的。但是对于链表就不是了，链表也没有下标的概念，只能通过头节点指针，从每一个节点，依次往下找，因为下个节点的位置信息只能通过上个节点知晓(这里只考虑单向链表)，所以访链表中的List(3)与List(10000)，时间就不一样了，访问List(3)，只要通过前两个节点，但要想访问List(10000)，不得不通过前面的9999个节点；而数组是一下子就跳到了a[10000]，无需逐个访问a[10000]之前的这些个元素。所以对于访问，数组和链表时间复杂度分别是O(1)与O(n)，方式一种是“随机访问”，一种是“顺序访问”。 

1.3 静态链表和动态链表 

静态链表和动态链表是线性表链式存储结构的两种不同的表示方式。 1、静态链表是用类似于数组方法实现的，是顺序的存储结构，在物理地址上是连续的，而且需要预先分配地址空间大小。所以静态链表的初始长度一般是固定的，在做插入和删除操作时不需要移动元素，仅需修改指针。 2、动态链表是用内存申请函数(malloc/new)动态申请内存的，所以在链表的长度上没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址不连续，要通过指针来顺序访问。 

静态链表：静态链表就是长度大小固定的，链式存储的线性表。 链式存储结构：它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点. 

–静态链表– 使用静态链表存储数据，需要预先申请足够大的一整块内存空间，也就是说，静态链表存储数据元素的个数从其创建的那一刻就已经确定，后期无法更改。 

比如，如果创建静态链表时只申请存储 10 个数据元素的空间，那么在使用静态链表时，数据的存储个数就不能超过 10 个，否则程序就会发生错误。 

不仅如此，静态链表是在固定大小的存储空间内随机存储各个数据元素，这就造成了静态链表中需要使用另一条链表(通常称为”备用链表”)来记录空间存储空间的位置，以便后期分配给新添加元素使用，如图 2 所示。 

这意味着，如果你选择使用静态链表存储数据，你需要通过操控两条链表，一条是存储数据，另一条是记录空闲空间的位置。 

–动态链表– 使用动态链表存储数据，不需要预先申请内存空间，而是在需要的时候才向内存申请。也就是说，动态链表存储数据元素的个数是不限的，想存多少就存多少。 

同时，使用动态链表的整个过程，你也只需操控一条存储数据的链表。当表中添加或删除数据元素时，你只需要通过 malloc 或 free 函数来申请或释放空间即可，实现起来比较简单。 

1.4 如何判断链表是否有环 

https://www.jianshu.com/p/95cd7eb17856 

问题3的证明： 

1.5 链表&跳表 

https://blog.csdn.net/ian_she/article/details/104345037 

2.堆, 栈 

3.指针 

编程语言中的一个对象 

在计算机科学中，指针(Pointer)是编程语言中的一个对象，利用地址，它的值直接指向(points to)存在电脑存储器中另一个地方的值。由于通过地址能找到所需的变量单元，可以说，地址指向该变量单元。因此，将地址形象化的称为“指针”。意思是通过它能找到以它为地址的内存单元。 [1] 在高级语言中，指针有效地取代了在低级语言，如汇编语言与机器码，直接使用通用暂存器的地方，但它可能只适用于合法地址之中。指针参考了存储器中某个地址，通过被称为反参考指针的动作，可以取出在那个地址中存储的值。作个比喻，假设将电脑存储器当成一本书，一张内容记录了某个页码加上行号的便利贴，可以被当成是一个指向特定页面的指针；根据便利粘贴面的页码与行号，翻到那个页面，把那个页面的那一行文字读出来，就相当于是对这个指针进行反参考的动作。 

在信息工程中指针是一个用来指示一个内存地址的计算机语言的变量或中央处理器(CPU)中寄存器(Register)【用来指向该内存地址所对应的变量或数组】。指针一般出现在比较接近机器语言的语言，如汇编语言或C语言。面向对象的语言如Java一般避免用指针。指针一般指向一个函数或一个变量。在使用一个指针时，一个程序既可以直接使用这个指针所储存的内存地址，又可以使用这个地址里储存的函数的值。 

4.队列 (Queue) 

4.1 概念 

https://www.jianshu.com/p/5dac973feda2 

队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。先进先出(FIFO)。 

题目：

队列的应用--击鼓传花大逃杀

题目描述

你和你的 39 个同学外出露营，晚上无聊时，大家围在火堆边做游戏。游戏规则如下：40人围成一个圈，其中一人被指定为第一个人，顺时针报数到第七人，就将他杀死。之后，下一个活着的人继续报数，每次都是杀死第七个人。直到只剩一人时，游戏结束。如果你并不想死，那么应该坐到哪里才能成为最后一人？(假设第一个报数者的位置记为1)

解题思路

如果能想到将这个问题抽象为一个简单队列的问题，那么就已经解决了一大半。

    报数而不被杀的人：相当于从队首出队再从队尾入队；

    被杀的人：只出队；

    留到最后的人：当队列长度为1时，再出队一次，返回。

def dataosha(name_list, kill_num=7):

    """击鼓传花大逃杀"""

    Q = Queue()

    for name in name_list:

        Q.enqueue(name)

    while Q.size() > 1:

        for _ in range(kill_num - 1):  # 这里没有用到_，只是为了循环而已

            Q.enqueue(Q.dequeue())

        print("Kill:", Q.dequeue())

    return Q.dequeue()

name_list = []

for i in range(40):

    name_list.append(i + 1)

print("Safe number:", dataosha(name_list))

队列是一种有次序的数据集合，其特征是新数据项的添加总发生在一端(通常称为“尾 rear”端)，而现存数据项的移除总发生在另一端(通常称为“首front”端)。

当数据项加入队列，首先出现在队尾，随着队首数据项的移除，它逐渐接近队首。

队列特征

  (1)先进先出或先到先服务；

  (2)队列只有一个入口和一个出口。

  (3)不允许数据项直接插入队中，也不允许从中间移除数据项。

4.2 Python3中 deque队列、list、栈的区别 

https://blog.csdn.net/qq_34979346/article/details/83540389 

deque是Python中stack和queue的通用形式，也就是既能当做栈使用，又能当做双向队列，list是单向队列.

队列和栈是两种数据结构，其内部都是按照固定顺序来存放变量的，二者的区别在于对数据的存取顺序： 

•    队列是，先存入的数据最先取出，即“先进先出”。

•    栈是，最后存入的数据最先取出，即“后进先出”。

5.树 trie 

5.1 概念 

https://www.cnblogs.com/ceo-python/p/11625093.html 

一、树的定义

树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并具有层次关系的结构。它非常类似于自然界中的树。

树的递归定义：

树(Tree)是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：

(1)有且仅有一个特定的称为根(Root)的结点；

(2)其余的结点可分为m(m≥0)个互不相交的子集Tl，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subree)。

二、二叉树的定义

二叉树是由n(n≥0)个结点组成的有限集合、每个结点最多有两个子树的有序树。它或者是空集，或者是由一个根和称为左、右子树的两个不相交的二叉树组成。

特点：

(1)二叉树是有序树，即使只有一个子树，也必须区分左、右子树；

(2)二叉树的每个结点的度不能大于2，只能取0、1、2三者之一；

(3)二叉树中所有结点的形态有5种：空结点、无左右子树的结点、只有左子树的结点、只有右子树的结点和具有左右子树的结点。

树的前 中 后 序 遍历 

https://blog.csdn.net/weixin_41275510/article/details/82287948 非线性结构 每个元素可以有多个前驱和后继 

5.1 有树根 

6.基础数据结构总汇 

https://blog.csdn.net/qq_33414271/article/details/78516443 

7.图 Graph 

图由顶点和边组成。如果图中顶点是有序的，则称之为有向图。 由顶点组成的序列，称为路径。 除了可以对图进行遍历外，还可以搜索图中任意两个顶点之间的最短路径。 

在python中，可利用字典 {键:值} 来创建图。 图中的每个顶点，都是字典中的键，该键对应的值为“该顶点所指向的图中其他的顶点”。 

有向图，无向图 

列表相加： 

8.线性表 

线性表(linear list)是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。 

将具有“一对一”关系的数据“线性”地存储到物理空间中，这种存储结构就称为线性存储结构(简称线性表)。 

使用线性表存储的数据，如同向数组中存储数据那样，要求数据类型必须一致，也就是说，线性表存储的数据，要么全不都是整形，要么全部都是字符串。一半是整形，另一半是字符串的一组数据无法使用线性表存储。 

前驱元素和后继元素 

9.序列 

所谓序列，指的是一块可存放多个值的连续内存空间，这些值按一定顺序排列，可通过每个值所在位置的编号(称为索引)访问它们。 

为了更形象的认识序列，可以将它看做是一家旅店，那么店中的每个房间就如同序列存储数据的一个个内存空间，每个房间所特有的房间号就相当于索引值。也就是说，通过房间号(索引)我们可以找到这家旅店(序列)中的每个房间(内存空间)。 

10.# JSON 数据结构 

https://blog.csdn.net/sinat_17775997/article/details/80667381  

JSON支持的数据类型：  

浮点表示(浮点数)：即小数的位数可动 ,如:3.12*e2, 0.312*e3  

nall表示0  

json对象和json字符串的区别和相互转换

json对象，首先说到对象的概念，对象的属性是可以用：对象.属性进行调用的

数据类型： 嵌套对象、数组、字符串、数字、布尔值或空值。

布尔值(Booleans)是一个逻辑值，只有true和false。

嵌套，指的是在已有的表格、图像或图层中再加进去一个或多个表格、图像或图层，亦或两个物体有装配关系时，将一个物体嵌入另一物体的方法。可理解为镶嵌、套用。

JSON解析两条规则：1.如果看到是{ }–>使用JSONObject 2.如果看到的[ ]–>使用JSONArray解析

较为复杂的键值对：   

11.快速排序 

https://www.cnblogs.com/sfencs-hcy/p/10602598.html 

快速排序的实现同样使用分治法，它的原理是从序列中选择一个值作为基准值，然后分成比基准值小的序列集合和比基准值小的序列集合和与基准值相等的序列集合。 

–时间复杂度– 

理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。 最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n2)。 

快速排序的时间复杂度有最优情况与最坏情况 

最优情况为每一次的基准值都正好为序列的中位数，时间复杂度为nlog(n) 

最坏情况为每一次的基准值都恰好是序列的最大值或最小值，时间复杂度为n^2。有意思的是如果每次选第一个数做基准值，但每次这个数又是最小值，那么序列本身就是有序的，但时间复杂度也是最高的 

要想 

要想优化时间复杂度，基准值的选择很关键，可以使用类似的从序列中选几个数，再求出他们的中位数做基准值 

–空间复杂度– 

空间复杂度：用来评估算法内存占用大小的一个式子 

12.归并排序 

分治法的思想：分解，解决，合并 

Ps: 伪代码(Pseudocode)是一种非正式的，类似于英语结构的，用于描述模块结构图的语言。 

13.插入算法 

def insertionSort(arr):

    for i in range(1, len(arr)):

        key = arr[i]

        j = i - 1

        while j >= 0 and key < arr[j]:

            arr[j + 1] = arr[j]

            j -= 1

        arr[j + 1] = key

arr = [12, 11, 13, 5, 6]

insertionSort(arr)

print("排序后的数组:")

for i in range(len(arr)):

    print("%d" % arr[i])

14.算法 时间复杂度 空间复杂度