链表

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

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

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

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

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

代码实现:<!--more-->

//用类来定义链表中的每个元素。
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) {}
};

链表常用操作:构造链表

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

代码实现:

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

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

链表常用操作:遍历链表

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

代码实现:

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

链表常用操作:插入元素

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

代码实现:

//在元素p后面插入元素i
i -> next = p -> next;
i -> prev = p;
if (p -> next != NULL) {
    p -> next -> prev = i;
}
p -> next = i;

注意:

1.修改关系的顺序.

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

链表常用操作:删除元素

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

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

if (i -> next != NULL) {
    i -> next -> prev = i -> prev;
}
if (i -> prev != NULL) {
    i -> prev -> next = i -> next;
}
delete i;

注意:

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

链表尾同理。

链表 Q&A

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

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

if (pr -> next != NULL) {
    pr -> next = pr -> next -> next;
}

当然,还是要特判删除链表头的情况。

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

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

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

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

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

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

队列

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

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

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

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

将队尾移动到新元素。

代码实现:

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

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

记录队头元素。

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

代码实现:

Node* oldHead = head;
head = head -> next;
oldHead -> next = NULL;

注意:

还要特判队列为空的情况。

数组:一种特殊的队列

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

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

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

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

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

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

定义:

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

添加元素:

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

删除元素:

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.将栈尾移动到新元素。

Node* newTail = new Node();
newTail -> prev = tail;
tail = newTail;

注意:还要特判栈为空的情况。

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

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

Node* oldTail = tail;
tail = tail -> prev;
oldTail -> prev = NULL;

注意:还要特判栈为空的情况。

数组:一种特殊的栈

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

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

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