线性表

线性表（linear list）是具有相同数据类型的 $n (n >= 0)$ 个数据元素的有限序列，其中 $n$ 为表长，当 $n = 0$ 时线性表是一个空表。若用 $L$ 命名线性表，则其一般表示为

L = (a_{1}, a_{2}, ..., a_{i}, a_{i + 1}, ..., a_{n})

$a_{1}$ 是唯一的“第一个”数据元素，又称表头元素； $a_{n}$ 是唯一的“最后一个”数据元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继（“直接前驱”和“前驱”、“直接后继”和”后继”通常被视为同义词）。以上就是线性表的逻辑特性，这种线性有序的逻辑结构正是线性表名字的由来。

由此，我们得出线性表的特点如下：

表中元素的个数有限。
表中元素具有逻辑上的顺序性，表中元素有其先后次序。
表中元素都是数据元素，每个元素都是单个元素。
表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念。

在稍复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件。

顺序表

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。

定义

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

第 1 个元素存储在线性表的起始位置, 第 $i$ 个元素的存储位置后面紧接着存储的是第 $i + 1$ 个元素，称 $i$ 为元素 $a_{i}$ 在线性表中的位序。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。

位序 = 下标+1

顺序表：用顺序存储的方式实现线性表。

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系体现。

优点：

随机访问，即可以在 $O (1)$ 时间内找到第 $i$ 个元素
存储密度高，每个节点只存储数据元素

缺点：

拓展容量不方便
插入，删除操作不方便，需要移动大量元素

实现

插入操作：
- 最好情况
  
  在表尾插入，元素后移语句将不执行，最好时间复杂度为 $O (1)$ 。
- 最坏情况
  
  在表头插入，元素后移语句将执行 $n$ 次，最坏时间复杂度为 $O (n)$ 。
- 平均情况
  
  假设 $p_{i} = \frac{1}{n + 1}$ 是在第 $i$ 个位置上插入一个结点的概率，则在长度为 $n$ 的线性表中插入一个结点时，所需移动结点的平均次数为
  $i = 1 \sum n + 1 p_{i} (n - i + 1) = i = 1 \sum n + 1 \frac{1}{n + 1} (n - i + 1) = \frac{1}{n + 1} i = 1 \sum n + 1 (n - i + 1) = \frac{1}{n + 1} \frac{n ( n + 1 )}{2} = \frac{n}{2}$
  平均时间复杂度为 $O (n)$ 。
删除操作：
- 最好情况
  
  删除表尾元素，不用移动元素，最好时间复杂度为 $O (1)$ 。
- 最坏情况
  
  删除表头元素，需移动除表头元素外的所有元素，最坏时间复杂度为 $O (n)$ 。
- 平均情况
  
  假设 $p_{i} = \frac{1}{n}$ 是在第 $i$ 个位置上插入一个结点的概率，则在长度为 $n$ 的线性表中插入一个结点时，所需移动结点的平均次数为
  $i = 1 \sum n p_{i} (n - i) = i = 1 \sum n \frac{1}{n} (n - i) = \frac{1}{n} i = 1 \sum n (n - i) = \frac{1}{n} \frac{n ( n - 1 )}{2} = \frac{n - 1}{2}$
  平均时间复杂度为 $O (n)$ 。
按值查找：
- 最好情况
  
  查找的元素就在表头，仅需比较一次，时间复杂度为 $O (1)$ 。
- 最坏情况
  
  查找的元素在表尾(或不存在)时，需要比较 $n$ 次，时间复杂度为 $O (n)$ 。
- 平均情况
  
  假设 $p_{i} = \frac{1}{n}$ 是查找的元素在第 $i (1 <= i <= L . l e n g t h)$ 个位置上的概率，则在长度为 $n$ 的线性表中查找值为 $e$ 的元素所需比较的平均次数为
  $i = 1 \sum n p_{i} \times i) = i = 1 \sum n \frac{1}{n} \times i = \frac{1}{n} \frac{n ( n + 1 )}{2} = \frac{n + 1}{2}$
  平均时间复杂度为 $O (n)$ 。

链表

单链表

线性表的链式存储又称单链表。它是指通过一组任意的存储单元来存储线性表中的数据元素（这组存储单元可以是连续的，也可以是不连续的）。

每个数据元素 $a_{i}$ 除存放元素自身的信息外，还需要存放一个指向其后继的指针。这两部分信息组成的数据元素 $a_{i}$ 的存储映像称为结点。 $n$ 个结点( $a_{i}$ ( $1$ ⇐ $i$ ⇐ $n$ )的存储映像)链结成一个链表，即线性表的链式存储结构。

由于链表的每个结点中只包含一个指针域，故又称线性链表或单链表。

指针域中存储的信息称做指针或链。

单链表节点结构：

data（数据域，存放数据元素）	next（指针域，存放其后继结点的地址）

typedef struct LNode {
	int data;
	struct LNode *next;
   } LNode, *LinkList;

优点：不需要大量连续空间、改变容量方便。

缺点：不能随机存取、要耗费一定空间存放指针。

初始化链表

不带头节点
```
// 初始化数组
void InitList(LinkList &L) {
	L = nullptr;// C++ 11标准是 nullptr，以前是 NULL
}
```
使用起来更加麻烦。
- 对第一个数据结点和后续数据结点的处理需要不同的代码逻辑；
- 对空表和非空表的处理需要不同的代码逻辑；

带头结点

// 初始化数组
void InitList(LinkList &L) {
	L = new LNode;
	L->next = nullptr;
}

使用起来与不带头结点相比更加方便

指定节点插入元素

// 后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p, int e) {
  if (p != nullptr) {
     LNode *q;
     q = new LNode;
     q->data = e;
     q->next = p->next;
     p->next = q;
     return true;
  } else {
   	return false;
  }
}

// 前插操作：在p结点之前插入元素e
bool InsertPriorNode(LNode *p, int e) {
  if (p != nullptr) {
     LNode *q;
     q = new LNode;
     q->next = p->next;
     p->next = q;
     q->data = p->data;
     p->data = e;
     return true;
  } else {
   	return false;
  }
}

按位序插入

// 按位序插入（带头结点）
bool ListInsert(LinkList &l, int i, int e) {
  if (i >= 1) {
    LNode *p = l;
    for (int j = 0; j < i - 1 && p != nullptr; j++) {
      p = p->next;
    }
    if (p == nullptr)return false;
    // 要插入的新结点 q
    LNode *q;
    q = new LNode;
    q->data = e;
    q->next = p->next;
    p->next = q;
    return true;
  } else {
    return false;
  }
}

// 按位序插入（不带头结点）
bool ListInsert(LinkList &l, int i, int e) {
  if (i >= 1) {
    if (i == 1){
      LNode *t;
      t = new LNode;
      t->data = e;
    	t->next = l;
      l = t;
      return true;
    }
    LNode *p = l;
    for (int j = 1; j < i - 1 && p != nullptr; j++) {
      p = p->next;
    }
    if (p == nullptr)return false;
    // 要插入的新结点 q
    LNode *q;
    q = new LNode;
    q->data = e;
    q->next = p->next;
    p->next = q;
    return true;
  } else {
    return false;
  }
}

指定结点删除元素

未知区域	LNode（要删除的结点）	LNode	可知区域

// 删除指定结点p
bool DeleteNode(LNode *p) {
  if (p != nullptr) {
    LNode *q = p->next;
    p->data = p->next->data;
    p->next = q->next;
    delete q;
    return true;
  } else {
    return false;
  }
}

如果不知道要删除的结点的前面一个结点，就只能从头开始遍历链表找到前一个结点。

按位序删除

// 按位序删除（带头结点）
bool ListDelete(LinkList &l, int i, int &e) {
  if (i >= 1) {
    LNode *p = l;
    for (int j = 0; j < i - 1 && p != nullptr; j++) {
      p = p->next;
    }
    if (p == nullptr || p->next == nullptr)return false;
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    delete q;
    return true;
  } else {
    return false;
  }
}

按位查找

// 按位查找（带头结点）
LNode *GetElem(LinkList l, int i) {
  if (i > 0) {
    LNode *res = l;
    for (int j = 0; j < i && res != nullptr; j++) {
      res = res->next;
    }
    return res;
  } else {
    return nullptr;
  }
}

按值查找

// 按值查找（带头结点）
LNode *LocateElem(LinkList l, int e) {
  LNode *res = l->next;
  while (res != nullptr && res->data != e) {
    res = res->next;
  }
  return res;
}

单链表的建立

给定多个数据元素，存储到一个单链表中

尾插法

// 正向建立单链表（带头结点）
LinkList List_TailInsert(LinkList &l) {
  l = new LNode;
  LNode *end = l;
  LNode *s;
  int input;
  cin >> input;
  while (input != 0) {
    s = new LNode;
    s->data = input;
    end->next = s;
    end = s;
    cin >> input;
  }
  end->next = nullptr;
  return l;
}

前插法

// 逆向建立单链表（带头结点）
LinkList List_HeadInsert(LinkList &l) {
  l = new LNode;
  l->next = nullptr;
  LNode *s;
  int input;
  cin >> input;
  while (input != 0) {
    s = new LNode;
    s->data = input;
    s->next = l->next;
    l->next = s;
    cin >> input;
  }
  return l;
}

双链表

单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点(插入、删除操作时)，只能从头开始遍历，访问后继结点的时间复杂度为 $O (1)$ ,访问前驱结点的时间复杂度为 $O (n)$ 。

为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针 prior 和 next，分别指向其前驱结点和后继结点

typedef struct DNode { //定义双链表结点类型
    int data; //数据域
    struct DNode *prior, *next; //前驱和后继指针
} DNode, *DLinklist;

以下实现均是带头结点

初始化

// 初始化双链表
void InitDLinkList(DLinklist &l) {
  l = new DNode;
  l->next = nullptr;
  l->prior = nullptr;
}

插入

// 在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s) {
  if (p != nullptr && s != nullptr) {
    s->next = p->next;
    s->prior = p;
    if (p->next != nullptr) {
      p->next->prior = s;
    }
    p->next = s;
    return true;
  } else {
    return false;
  };
}

删除

// 删除p结点的后继结点
bool DeleteNextDNode(DNode *p) {
  if (p != nullptr) {
    DNode *q = p->next;
    if (q != nullptr) {
      p->next = q->next;
      q->next->prior = p;
      delete q;
      return true;
    } else {
      return false;
    }
  } else {
    return false;
  }
}

循环链表

循环单链表

循环单链表和单链表的区别在于，表中最后一个结点的指针不是 NULL，而改为指向头结点，从而整个链表形成一个环。

typedef struct LNode {
	int data;
	struct LNode *next;
} LNode, *LinkList;

循环单链表的插入、删除算法与单链表的几乎一样，所不同的是若操作是在表尾进行，则执行的操作不同，以让单链表继续保持循环的性质。

因为循环单链表是一个“环”，因此在任何一个位置上的插入和删除操作都是等价的，无须判断是否是表尾。

// 初始化一个循环单链表
void InitList(LinkList &l) {
  l = new LNode;
  l->next = l;
}

循环双链表

循环双链表与循环单链表类似，不同的是在循环双链表中，头结点的 prior 指针要指向表尾结点。

静态链表

静态链表借助数组来描述线性表的链式存储结构，结点也有数据域 data 和指针域 next, 与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址(数组下标)，又称游标。

和顺序表一样，静态链表也要预先分配一块连续的内存空间。

#define MaxSize 50
typedef struct {
    int data;
    int next;
} SLinkList[MaxSize];
// 等价于
#define MaxSize 50
struct Node {
    int data;
    int next;
};
typedef struct Node SLinkList[MaxSize];

优点：

插入删除不需要大量移动元素

缺点：

不能随机存取，只能从头结点开始依次往后查找
容量固定不可变

使用场景：

不支持指针的低级语言
数据元素数量固定不变的场景（如操作系统的文件分配表 FAT）

顺序表和链表的比较

存取(读写)方式
- 顺序表可以顺序存取，也可以随机存取
- 链表只能从表头顺序存取元素
逻辑结构与物理结构
- 采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。
- 采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的
查找、插入和删除操作
- 对于按值查找
  - 顺序表无序时，两者的时间复杂度均为 $O (n)$ ；
  - 顺序表有序时，可采用折半查找，此时的时间复杂度为 $O (lo g_{2} n)$
- 对于按序号查找
  - 顺序表支持随机访问，时间复杂度为 $O (1)$
  - 链表的平均时间复杂度为 $O (n)$ 。
- 顺序表的插入、删除操作，平均需要移动半个表长的元素。
- 链表的插入、删除操作，只需修改相关结点的指针域即可。由于链表的每个结点都带有指针域，故而存储密度不够大。
空间分配
- 顺序存储
  - 在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新元素，则会出现内存溢出，因此需要预先分配足够大的存储空间。预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。
  - 动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。
- 链式存储的结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效。

😶‍🌫️ Notes

探索

最近

TS 笔记

常用工具函数

Promise和Async

Express实现用户认证

事件循环(Event Loop)

在 Express 中使用 Mongose

线性表

线性表

顺序表

定义

实现

链表

单链表

双链表

循环链表

循环单链表

循环双链表

静态链表

顺序表和链表的比较

关系图谱

目录