一维数据结构学习笔记

链表

链表:按顺序记录元素的线性数据结构。

其中的“顺序”是逻辑上的顺序，不一定是物理存储上的顺序。

链表分为单向与双向两种：

1.单向链表:每个元素只记录了下一个元素的位置。

2.双向链表:每个元素记录了上一个及下一个元素的位置。

代码实现： 

1
2
3
4
5
6
7
8
9
//用类来定义链表中的每个元素。
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) {}
};
### 链表常用操作:构造链表

通过实例化链表类，创建链表的每个元素并建立元素之间的关系。

代码实现： 

1
2
3
4
5
6
//构造一个只有头尾两个元素的链表。
Node* head = new Node(); 
Node* tail = new Node(); 

head -> next = tail;
tile -> prev = head;

链表常用操作:遍历链表

将链表头赋值给临时变量，然后不断寻找下一个元素直到空。

代码实现： 

1
2
3
4
5
Node* i = head;
while (i -> next != NULL) {
    i = i -> next;
    //需要对链表元素进行的操作
}

链表常用操作:插入元素

找到要插入元素的位置，一般是记录前一个元素。
重新设置插入位置两边的元素和插入元素的关系。

代码实现： 

1
2
3
4
5
6
7
//在元素p后面插入元素i
i -> next = p -> next;
i -> prev = p;
if (p -> next != NULL) {
    p -> next -> prev = i;
}
p -> next = i;
注意:

1.修改关系的顺序.

2.特判插入链表头的情况。

链表常用操作:删除元素

首先，找到要删除的元素。

重新设置该元素的前后元素之间的关系，并根据需要释放元素。 代码实现： 

1
2
3
4
5
6
7
if (i -> next != NULL) {
    i -> next -> prev = i -> prev;
}
if (i -> prev != NULL) {
    i -> prev -> next = i -> next;
}
delete i;
注意:

如果有变量用来记录链表头，头被删除时要记得更新。

链表尾同理。

链表 Q&A

Q： 单向链表可以进行删除元素操作吗?

A： 可以。通过预判下一个元素的方式，找到要删除元素的上一个元素，再更新下一个元素。 

1
2
3
if (pr -> next != NULL) {
    pr -> next = pr -> next -> next;
}
当然，还是要特判删除链表头的情况。

Q： 还有别的方式可以用来实现链表吗?

A： 通常情况下，使用数组来实现链表会更加简便。

给每个元素一个编号(地址)，以代替指针的引用。

为了记录每个元素的属性，可以使用结构体、二维数组或者多个数组。

Q： 用数组实现链表有哪些缺点?

A： 1.数组必须一次性初始化，并且长度固定。2.删除元素不会真正的释放空间。

队列

从严格意义上来说，队列是一种特殊的链表，只支持添加队列尾元素和删除队列头元素两种操作。

或者说，队列是链表的子集。

队列常用操作:从队列尾部添加元素

创建一个新元素，将队尾元素的下一个元素指向新元素。

将队尾移动到新元素。

代码实现： 

1
2
3
Node* newTail = new Node();
tail -> next = newTail;
tail = newTail;

队列常用操作:从队列头部删除元素

记录队头元素。

将队头元素移动到它的下一个元素。根据需要释放旧的队头元素。

代码实现： 

1
2
3
Node* oldHead = head;
head = head -> next;
oldHead -> next = NULL;
注意： > 还要特判队列为空的情况。

数组:一种特殊的队列

用两个整数表示数组的下标，作为队头和队尾的指针。

删除元素则将队头指针+1，添加元素则将队尾指针+1。

队头指针超过的队尾指针表示队列为空。

循环队列:循环重复利用被删除空间的数组队列

移动指针后如果超出了数组长度，则重置为0。

当尾指针追赶上头指针时，表示队列溢出。

定义： 

1
2
3
const int LENGTH = 100;
Node* queue[LENGTH];
int head = 0, tile = 0;

添加元素： 

1
2
3
4
5
6
7
8
9
bool push(Node* t) {
    if(head != (tail + 2)) { // 判断满。 
        tail = (tail + 1) % LENGTH; 
        queue[tail] = t;
        return true;
    } else {
        return false;
    }
}

删除元素： 

1
2
3
4
5
6
7
8
9
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.将栈尾移动到新元素。 

1
2
3
Node* newTail = new Node();
newTail -> prev = tail;
tail = newTail;
注意：还要特判栈为空的情况。

栈常用操作:从栈尾部删除元素

1.记录栈尾元素。
2.将栈尾元素移动到它的上一个元素。
3.将旧栈尾元素的上一个元素置空。根据需要释放旧的栈尾元素。 

1
2
3
Node* oldTail = tail;
tail = tail -> prev;
oldTail -> prev = NULL;
注意：还要特判栈为空的情况。

数组:一种特殊的栈

用一个整数表示数组的下标，作为栈尾的指针。

添加元素则将栈尾指针+1，删除元素则将栈尾指针-1。

栈尾指针小于栈头元素的下标则表示栈为空。