第2课 数据结构基础(一)

数据结构基本概念

小伙伴们，在前面学习了Python的基础知识后，我们终于可以开始学习数据结构的内容了。和前面的内容相比，数据结构学习起来比较枯躁，希望大家能够打起精神，把这部分的内容扎实地学好。

那什么是数据结构呢？简单的说，数据结构不关注数值计算，而是关注数据与数据之间的关系，以及如何操作这些有关系的数据。从“结构”这个词我们也可以看出，他强调的是数据与数据之间如何发生联系，如何互相影响，如何又结合在一起。我们常常把这种关系分为逻辑关系与物理关系两种。那么对应关系组织的数据我们就叫逻辑结构和物理结构

首先说物理结构，他主要是研究数据对象是如何在计算机中存储的，在Python中，我们可能不太会关注这类问题。因为Python语言是一个比较高级的语言，对于数据在物理内存中存储我们不用太关心（但也完全不是不关心），所以我们可以把这部分内容先稍微摆一摆，但是在后面的内容中，我们也会顺带稍微提一提。

再来说逻辑结构，这是我们今后要着重关注的部分。他着重研究数据与数据之间依据一定的逻辑关系组织形成的数据对象。逻辑结构有以下四种结构：

集合结构

集合结构是由一堆无序的，不重复的同一类型的数据元素组成的组合。元素之间并没有相互的关系，只是他们同属于一个集合。

线性结构

线性结构中的元素都是一对一的关系，从这个关系中我们可以看出，元素之间除了第一个元素和最后一个元素以外，其他所有的关系是一对一的。同时这也暗含了说明元素在这种结构是有顺序的。（因为只有有顺序才能一对一）

非线性结构

有线性结构，我们就有非线性结构。自然我们能想到的结构有一对多，和多对多。以下几种非线性结构比较典型：

树形结构

树形结构中，每一个结点都会有0-N个结点与之相对应，如下图所示：

图形结构

图形结构中的元素， 每一个结点都是多对多的关系。

数据结构的常用操作

我们说过，我们学习数据结构，是要学习数据结构中元素之间的关系和如何操作他们，一般一种数据结构，他将会有以下这些常规的操作：

• 查找：查找就是在数据结构里查找满足一定条件的元素。一般是给定一个某字段的值，找具有该字段值的元素。
• 插入：往数据结构中增加新的元素。
• 删除：把指定的元素从数据结构中去掉。
• 更新：改变指定元素的一个或多个字段的值。

除去这些常规操作，针对一些特定的数据结构，还会有不同的操作，比如较为常见的还有：排序、求最大值等操作。

线性表

这一节内容主要讨论线性结构，在线性结构中，大多数语言都会讨论两种形式的数据结构：数组（Array）和链表（Linked List)。 数组和链表的都表示一对一的数据关系，再简单说就是有顺序的数据集合。他俩最大的不同就是数组在计算机内存中是以顺序的结构排列的， 而链表在计算机内存中是以链式的结构排列的，请看下图中的示例：

这两种方式各有优劣，下面我们以Python语言为描述语言，进行两种数据结构的学习。

数组(Array)

首先学习数组。数组的概念就是一组有顺序排列的数据。在Python中，数组类型可以很方便地使用Python提供的list类型来完成。首先我们来看一看数组的插入操作。

数组的插入操作

首先看看数组的最基本的插入操作，先看比如有一数组array, 长度为n,现在需要在位置i处插入数值val，那么需要做哪些操作呢？

从图中我们可以看到，如果当val占用了第i处的位置的时候，则原来第i处数值应当移动到i+1处，而原来i+1处的值就会被移动到i+2处…… 以此类推, 当最后一个值n-1处的值就会被移动到n处了。但是当前我们的数组array的大小只有n，再往外移动就会出错，所以你需要给数组开辟新的内存空间。整个操作可见下图：

将以上的操作整理一下，我们将插入操作整理成以下步骤：

1. 插入值时先在列表末尾开辟新的空间(如果本来空间够的话则不用)。
2. 从新数组的末尾(即n处)开始往前遍例直到位置i+1，同时将当前位置的前一位置的数赋值到当前的位置中。
3. 将第i处位置的数改为待插入的数val。
4. 插入操作结束。

下面使用Python代码来实现以上过程。

from typing import List

def insert(array: List[int], i: int, val: int):
    pos = len(array)
    array.append(0)
    while pos > i:
        array[pos] = array[pos-1]
        pos -= 1
    array[i] = val 

从上面的代码，我们可以得出，数组的插入操作的最坏时间复杂度是\(O(n)\)，这个情况发生在在数组首个元素前插入元素。

数组的删除操作

有了插入操作的经验，我们要删除数组中的第i处的元素，就很快可以得出下面的步骤：

1. 从i处往后遍例至数组的末尾，在遍例过程中需要将下一位置处的数值覆盖当前位置的值。
2. 数组的长度由n变为n-1，释放最后一个元素所占的内存空间。

整个过程可以看下图的示意。

小伙伴尝试一下，是否能够写出删除元素的代码：

def delete(array: List[int], i: int):
    """ 此函数将删除array中，第i处的整数 """

同样的，可以很快看出数组的删除操作的最坏时间复杂度是\(O(n)\)，这种情况发生在删除数组首个元素时。

数组的查找操作

这里我们可以分为按位置查找和按数值查找。

• 按位置查找，只要给定位置i， 我们可以很快使用array[i]直接获得他其中的数据，此步的时间复杂度是\(O(1)\)。
• 如果按照给定数值val查找，上学期中，我们学习过穷举法查找, 二分查找和符号表查找 三种方法，三种方法的时间计算复杂度是\(O(N)\), \(O(logN)\)和\(O(1)\)，小伙伴尝试自己回忆一下，是否能够写出这三种算法。(要注意，二分查找算法对数组是有一定要求的)

数组的更新（修改）操作

这里我们同样可以分为按位置更新和按数值更新两种操作。

• 按给定位置i更新，我们只需使用array[i] = val即可完成数值更新，此操作复杂度为\(O(1)\)。
• 按给定数值val更新，则与查找类似，当查找到当前val值时，将那个位置的数值更新为val即可，这个操作与查找算法的复杂度类似，这里不再写出，大家一定要进行复习。

Python中的list操作

实际上，在Python中，list类型已经内置了这些操作，大家可以直接使用python提供的list来实现数组数据结构。如果不是必要情况和题目要求，大家在平常中应该尽量使用库中提供的方法，而不是自己写一个。以上过程是要求大家掌握基本的数组操作的原理，而list自带的方法是非常稳定，并且经过充分优化过的。下面是list对应的一些基本操作。

操作	list 方法
插入	list.insert(index, value)
删除index处元素	del list[index]
删除值为obj的元素	list.remove(obj)
查找元素值为obj的位置	list.index(obj)

链表(Linked List)

与数组不同，链表不要求数据在计算机中在内存中按照顺序存储，只要数据之间保持了正确的联系即可。 所以聪明的你可以想到，每一个组成链表的元素中不仅仅保存数据了，他还必须保存指向下一节点的信息，以保证数据是一一对应的。这样的一组数据（原本保存的数据与指向下一节点信息的数据）叫做节点(Node)。 在Python中，可以很快写出下面的Node类定义：

class Node:
    # 当next参数省略时，默认值为None
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

这样我们就定义了一个链表的节点，其中Node类中，val用于存储数据，next用于保存下一个节点的位置。

next不是保存了一个对象吗？为什么说他保存了下一个节点的位置？实际上，Python在使用类构造方法创建对象时，并不直接把对象存储到变量中，而是在计算机中开辟一块合适的内存区域用于存放对象中的数据，最后仅仅把这块内存区域的地址返回，保存到了变量中。 简单地说，我们可以将next看成是一个地址，他指向了下一个节点对象的地址。我们通过这个地址，就能够访问到下一个节点了。

链表的创建

首先先要创建一个变量，用于记录链表的起始位置，我们叫他头节点（head)。

class LinkedList:
    def __init__(self):
        self.head = None

链表刚开始建立时，表中没有任何节点，所以在构造方法中，头节点值为None。

self.head = None

下面我们需要在末尾插入一个节点，数值为val，可以分为以下两种情况： 1. 链表内为空，即head is None, 可以直接新建一个节点，并使用head指向新建节点即可; 2. 链表不为空，即head is not None。

def append(self, val):
    if self.head is None:
        self.head = Node(val)
        return self.head
    # 在链表的尾部插入一个节点，需要先找到尾部节点：
    tail = self.head
    while tail.next is not None:
        tail = tail.next

    # 此时找到了tail节点，因为tail.next是None了，不存在下一个结点了。
    # 这时把tail.next指向我们新建的结点就OK了
    tail.next = Node(val)
    return tail.next

操作可看下图：

链表节点的插入

上面在链表的创建中，我们先找到尾节点，然后在尾结点添加新的节点就行。下面我们讨论在链表的中间插入新的节点。

假设已经给定节点node，现在要求在该节点后新增值为val的节点。 要在给定节点之后增加结点，是一个稍微有些复杂的操作，因为你要保持住整个链表的逻辑联系。

首先我们可以考虑到如果node.next is None的话，那么说明这个node节点是尾节点。这样可以很快就插入新建的节点。

如果node节点是在链表中间的话，要插入一个新的节点，则需要特别小心。 如图所示，图中的需要在红色虚线处插入一个数值为val的节点

整个操作其实很简单，把node.next 指向新增的节点，然后把新增节点的next指向原先node.next就行。

那下一步我们要将node.next保存在temp中，防止待会儿node.next指向新节点后把这个节点的地址弄丢了。

接下来把node.next指向新增的节点p。

然后把p的next指向temp指向的节点，就完成了整个操作。

def insert(self, node: Node, val) -> Node:
    self.size += 1
    if node.next is None:
        node.next = Node(val)
        return node.next
    else:
        temp = node.next
        p = Node(val)
        node.next = p
        p.next = temp
        return p

删除节点

下图中node表示待删除的节点

首先我们要找到指向node的前一个节点prev，我们一般把这个节点叫前驱(Predecessor), 把node所指向的后一个节点叫做后继（Successor）。

最后将前驱节点的next指向node的next所指向的节点就完成了删除操作。

下面是完整的删除节点的代码。

def delete(self, node: Node) -> Node:
    prev = self.head

    while prev and prev.next != node:
        prev = prev.next

    if prev is None:
        # 说明给定要删除的节点不存在在链中，直接返回None
        return None

    # 此时prev指向的是node的前驱节点。
    prev.next = node.next
    # 将待删除的节点的`next`设置为None
    node.next = None
    self.size -= 1
    return node

查找节点

查找节点有两种方法，可以按目标值查找，也可以按照索引查找。

• 按目标值查找：

  def find(self, target) -> Node:
      p = self.head
      while p and p.val != target:
          p = p.next
  
      # 如果p目前为None, 说明没有找到含有目标值的节点
      if not p:
          return None
      else:
          return p
  

• 按照索引查找：

  def get(self, index: int) -> Node:
      if index >= self.size:
          return None
      p = self.head
      i = 0
      while i < index:
          p = p.next
          i += 1
  
      return p
  

更新节点

与查找节点类似，只要查找到要更新的节点，即可更新。大家可以自己完成这两个方法。

完成课堂练习

作业

完成C003一题