一维数据结构学习笔记
智子
2019-04-27 20:20:22
## 链表
链表:按顺序记录元素的线性数据结构。
其中的“顺序”是逻辑上的顺序，不一定是物理存储上的顺序。
链表分为单向与双向两种：
1.单向链表:每个元素只记录了下一个元素的位置。
2.双向链表:每个元素记录了上一个及下一个元素的位置。
代码实现：<!--more-->
```cpp
//用类来定义链表中的每个元素。
class Node {
public:
int v = 0;
Node * next = NULL, * prev = NULL;
/*前一个元素或者后一个元素可以不存在，所以必须要使用指针类型。*/
Node(int v = 0, Node * next = NULL, Node * prev = NULL):v(v), next(next), prev(prev) {}
};
```
### 链表常用操作:构造链表
通过实例化链表类，创建链表的每个元素并建立元素之间的关系。
代码实现：
```cpp
//构造一个只有头尾两个元素的链表。
Node* head = new Node();
Node* tail = new Node();
head -> next = tail;
tile -> prev = head;
```
### 链表常用操作:遍历链表
将链表头赋值给临时变量，然后不断寻找下一个元素直到空。
代码实现：
```cpp
Node* i = head;
while (i -> next != NULL) {
i = i -> next;
//需要对链表元素进行的操作
}
```
### 链表常用操作:插入元素
找到要插入元素的位置，一般是记录前一个元素。
重新设置插入位置两边的元素和插入元素的关系。
代码实现：
```cpp
//在元素p后面插入元素i
i -> next = p -> next;
i -> prev = p;
if (p -> next != NULL) {
p -> next -> prev = i;
}
p -> next = i;
```
注意:
> 1.修改关系的顺序.
>
> 2.特判插入链表头的情况。
### 链表常用操作:删除元素
首先，找到要删除的元素。
重新设置该元素的前后元素之间的关系，并根据需要释放元素。
代码实现：
```cpp
if (i -> next != NULL) {
i -> next -> prev = i -> prev;
}
if (i -> prev != NULL) {
i -> prev -> next = i -> next;
}
delete i;
```
注意:
> 如果有变量用来记录链表头，头被删除时要记得更新。
>
>链表尾同理。
### 链表 Q&A
**Q：**单向链表可以进行删除元素操作吗?
**A：**可以。通过预判下一个元素的方式，找到要删除元素的上一个元素，再更新下一个元素。
```cpp
if (pr -> next != NULL) {
pr -> next = pr -> next -> next;
}
```
当然，还是要特判删除链表头的情况。
**Q：**还有别的方式可以用来实现链表吗?
**A：**通常情况下，使用数组来实现链表会更加简便。
给每个元素一个编号(地址)，以代替指针的引用。
为了记录每个元素的属性，可以使用结构体、二维数组或者多个数组。
**Q：**用数组实现链表有哪些缺点?
**A：**1.数组必须一次性初始化，并且长度固定。2.删除元素不会真正的释放空间。
## 队列
从严格意义上来说，队列是一种特殊的链表，只支持添加队列尾元素和删除队列头元素两种操作。
或者说，队列是链表的子集。
### 队列常用操作:从队列尾部添加元素
创建一个新元素，将队尾元素的下一个元素指向新元素。
将队尾移动到新元素。
代码实现：
```cpp
Node* newTail = new Node();
tail -> next = newTail;
tail = newTail;
```
### 队列常用操作:从队列头部删除元素
记录队头元素。
将队头元素移动到它的下一个元素。根据需要释放旧的队头元素。
代码实现：
```cpp
Node* oldHead = head;
head = head -> next;
oldHead -> next = NULL;
```
注意：
> 还要特判队列为空的情况。
### 数组:一种特殊的队列
用两个整数表示数组的下标，作为队头和队尾的指针。
删除元素则将队头指针+1，添加元素则将队尾指针+1。
队头指针超过的队尾指针表示队列为空。
### 循环队列:循环重复利用被删除空间的数组队列
移动指针后如果超出了数组长度，则重置为0。
当尾指针追赶上头指针时，表示队列溢出。
定义：
```cpp
const int LENGTH = 100;
Node* queue[LENGTH];
int head = 0, tile = 0;
```
添加元素：
```cpp
bool push(Node* t) {
if(head != (tail + 2)) { // 判断满。
tail = (tail + 1) % LENGTH;
queue[tail] = t;
return true;
} else {
return false;
}
}
```
删除元素：
```cpp
Node* pop() {
if (head != (tail + 1)) { // 判断空。
Node* h = queue[head];
head = (head + 1) % LENGTH;
return h;
} else {
return NULL;
}
}
```
### 队列 Q&A
**Q：**队列是单向链表还是双向链表?
**A：**使用单向链表足以支持队列的操作。
**Q：**如果是双向队列，需要额外增加哪些操作?
**A：**添加时要设置新元素的前一个元素，删除时要清空新队头的前一个元素。
**Q：**数组队列有哪些优点与缺点?
**A：**优点：队列不需要删除中间元素，数组完全满足队列的操作要求。
缺点：删除掉的空间无法被重复利用。
**Q：**如何区分循环队列是满还是空?
**A：**有两种方案：
> 1.用一个额外的变量记录队列的元素个数。
>
> 2.将实际队列的容量变为数组长度-1，让队列空和满时的队尾指针在不同的位置。
本文代码采用的是第二种方案
## 栈
从严格意义上来说栈是一种特殊的链表，只支持添加栈尾元素和删除栈尾元素两种操作。
或者说，栈是链表的子集。
### 栈常用操作:从栈尾部添加元素
1.创建一个新元素。
2.将新元素的上一个元素指向栈尾元素。
3.将栈尾移动到新元素。
```cpp
Node* newTail = new Node();
newTail -> prev = tail;
tail = newTail;
```
注意：还要特判栈为空的情况。
### 栈常用操作:从栈尾部删除元素
1.记录栈尾元素。
2.将栈尾元素移动到它的上一个元素。
3.将旧栈尾元素的上一个元素置空。根据需要释放旧的栈尾元素。
```cpp
Node* oldTail = tail;
tail = tail -> prev;
oldTail -> prev = NULL;
```
注意：还要特判栈为空的情况。
### 数组:一种特殊的栈
用一个整数表示数组的下标，作为栈尾的指针。
添加元素则将栈尾指针+1，删除元素则将栈尾指针-1。
栈尾指针小于栈头元素的下标则表示栈为空。