一维数据结构学习笔记

一维数据结构学习笔记

链表

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

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

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

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。

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

文章作者: Helium
文章链接: https://keepthethink.github.io/archives/1580237458/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Heliumの博客