数据结构 - 线性表
[TOC]
前言
程序（Program）= 算法（Algorithm）+ 数据结构（Data Structure）
对于常用数据结构，有如下几种：
- 数组（Array）
- 链表（Linked List）
- 栈（Stack）
- 队列（Queue）
- 树（Tree）
- 图（Graph）
- 哈希表（Map）
- 集合（Set）
其中，数组，链表，栈 和 队列 都属于 线性表（即由零个或多个数据元素组成的有限序列）
本篇主要对 线性表 进行简介。
注：下文中的代码只是用于从底层原理对上层数据结构的实现，未经过严格的单元测试，可能存在严重漏洞，但着重于理解即可。
数组（Array）
定义：数组（Array）指的是用一段地址连续的存储单元依次存储线性表的数据元素。如下图所示：
Array
特性：存取数据时间复杂度为 ，插入/删除数据时间复杂度为
（对于尾元素的插入/删除时间复杂度为
）。
因此，数组适用于插入/删除操作较少，随机访问/获取较多的场景。
基本操作：存储，获取，插入，删除
#pragma once
#ifndef __ARRAY_H__
#define __ARRAY_H__
#include <iostream>
#include <stdexcept>
namespace {
void check(const void *arr, int arrayLength = 0, int pos = 0) throw(std::exception, std::out_of_range) {
if (arr == nullptr) {
throw std::exception("Null Pointer Exception!");
}
if (pos < 0 || pos >= arrayLength) {
throw std::out_of_range("index out of range!");
}
}
}
template<typename T> void store(T arr[], int arrLength, int pos, T value) throw(std::exception, std::out_of_range) {
check(arr, arrLength, pos);
arr[pos] = value;
}
template<typename T> T get(const T arr[], int arrLength, int pos) throw(std::exception, std::out_of_range) {
check(arr, arrLength, pos);
return arr[pos];
}
template<typename T> void insert(T arr[], int arrLength, int pos, T value) throw(std::exception, std::out_of_range) {
check(arr, arrLength, pos);
for (int i = arrLength - 1; i > pos; --i) {
arr[i] = arr[i - 1];
}
arr[pos] = value;
}
template<typename T> T remove(T arr[], int arrLength, int pos) throw (std::exception, std::out_of_range) {
check(arr, arrLength, pos);
T ele = arr[pos];
for (int i = pos + 1, cur = pos; i < arrLength; ++i) {
arr[cur++] = arr[i];
}
return ele;
}
#endif // __ARRAY_H__
链表（Lined List）
线性表有两种存储方式：顺序存储结构 和 链式存储结构。
注：顺序存储结构 的典型使用就是 数组。
定义：链式存储结构 与 顺序存储结构 的不同之处在于：其相邻两个元素在内存中不一定是相邻的，每个链式结点（Node）一般包含两个域：数据域 和 指针域 。数据域 存储的是数据元素信息，指针域 存储的是下一结点的地址。如下图所示：
LinkedList
因此，链表的一般表现形式如下所示：
template<typename T> struct Node {
Node(T ele, Node<T> *next) :element(ele), pNext(next) {}
T element; // 数据域
struct Node<T> *pNext; // 指针域
};
template<typename T> class LinkedList {
public:
LinkedList(Node<T> head) {
this->pHead = new Node<T>(NULL, head);
}
LinkedList(const std::initializer_list<T> &nodes) {
Node<T> *pNext = nullptr;
for (auto iter = std::rbegin(nodes); iter != std::rend(nodes); ++iter) {
Node<T> *p = new Node<T>(*iter, pNext);
pNext = p;
}
this->pHead = new Node<T>(NULL, pNext);
}
~LinkedList() {
Node<T> *pNode = this->pHead->pNext;
delete this->pHead;
Node<T> *pTemp = nullptr;
while (pNode) {
pTemp = pNode->pNext;
delete pNode;
pNode = pTemp;
}
}
}
#endif
-
一般把链表的第一个结点称为 头指针，但有时为了方便操作，会在头指针前面增加一个结点：头结点，头结点的数据域为空，指针域指向第一个结点。
链表的最后一个结点称为 尾指针，尾指针的指针域指向空。
头结点
-
链表的存取必须从头指针开始进行，依次遍历，直到某个结点的指针域（即尾指针）指向空才结束。
特性：插入/删除时间复杂度为 （实际上插入/删除前要先遍历到该插入结点，因此，插入/删除的实际时间复杂度为
，而后续该点的所有插入/删除操作时间复杂度才为
）。
因此，对于插入/删除数据越频繁的操作，链表的效率就越明显。
基本操作：存储，获取，插入，删除，清空
// LinkedList.h
#pragma once
#ifndef __LINKED_LIST__
#define __LINKED_LIST__
#include <initializer_list>
template<typename T> struct Node {
Node(T ele, Node<T> *next) :element(ele), pNext(next) {}
T element; // 数据域
struct Node<T> *pNext; // 指针域
};
template<typename T> class LinkedList {
public:
LinkedList(Node<T> head) {
this->pHead = new Node<T>(NULL, head);
}
LinkedList(const std::initializer_list<T> &nodes) {
Node<T> *pNext = nullptr;
for (auto iter = std::rbegin(nodes); iter != std::rend(nodes); ++iter) {
Node<T> *p = new Node<T>(*iter, pNext);
pNext = p;
}
this->pHead = new Node<T>(NULL, pNext);
}
~LinkedList() {
this->clear();
delete this->pHead;
}
Node<T>* operator[](int pos) const {
Node<T> *p = this->pHead;
int curPos = 0;
while (curPos++ <= pos) {
p = p->pNext;
}
return p;
}
public:
// 插入：在第 pos 位置插入 value
Node<T>* insert(int pos, T value) {
Node<T> *pNode = this->pHead;
int curPos = 0;
while (pNode && curPos++ < pos) {
pNode = pNode->pNext;
}
Node<T> *p = new Node<T>(value, pNode->pNext);
pNode->pNext = p;
return p;
}
// 删除：删除第 pos 位置的结点
bool remove(int pos) {
int curPos = 0;
Node<T> *p = this->pHead;
while (p && curPos++ < pos) {
p = p->pNext;
}
if (!p) {
return false;
}
Node<T> *pNodePos = p->pNext;
p->pNext = p->pNext->pNext;
delete pNodePos;
return true;
}
// 改：设置 pos 位置的值
bool set(int pos,T value) {
int curPos = 0;
Node<T> *pNode = this->pHead;
while (pNode && curPos++ <= pos) {
pNode = pNode->pNext;
}
if (!pNode) {
return false;
}
pNode->element = value;
return true;
}
// 查：获取 pos 位置的值
Node<T> *get(int pos) {
int curPos = 0;
Node<T> *pNode = this->pHead;
while (pNode && curPos++ <= pos) {
pNode = pNode->pNext;
}
return pNode;
}
// 清空
void clear() {
Node<T> *p = this->pHead->pNext;
while(p && p->pNext != nullptr) {
Node<T> *temp = p;
p = p->pNext;
delete temp;
}
delete p;
this->pHead->pNext = nullptr;
}
private:
Node<T> *pHead = nullptr; //头结点
};
#endif
-
对于 单链表 来说，由于其每个结点都只存储了其后继结点指针，因此，单链表只具备向后遍历，不具备访问前驱结点功能。为了解决这个问题，就出现了 循环链表。
-
循环链表 按照实现方式不同，又可以分为 单循环链表 和 双向链表。
-
单循环链表：仅仅只是将 单链表 的终端结点的指针域由指向空指针改为指向头结点，这样就将整张单链表形成一个环了，因此也被称为 循环链表（circular linked list）。
-
双向链表：无论是 单链表 还是 循环链表，都只具备单向遍历功能。而 双向链表 的结构使其每个结点都具备前向/后向遍历功能，因为 双向链表 的每个结点都包含了一个指向前驱结点的指针域和一个指向后继结点的指针域，如下所示：
template<typename T> struct Node { T element; // 数据域 struct Node<T> *pNext; // 指针域：后继结点 struct Node<T> *pFront; // 指针域：前驱结点 };
-
栈（Stack）
定义：栈（Stack）是限定只在表尾进行插入和删除操作的线性表。
特性：栈的操作只有入栈和出栈，并且具备 后进先出（LIFO） 特点。
Stack
基本操作：压栈，出栈
注：栈的实现可以基于线性表的 顺序存储结构（即数组） 或者是 链式存储结构（即链表）。
-
基于数组实现：栈底层结构采用数组，则通常将下标为 0 的索引作为栈底。压栈时，将数据依次存放入数组尾部，同时记录此时索引位置，作为栈顶指数器。出栈时，先根据当前栈顶指数器（即数组尾元素索引）获取栈顶元素，然后将栈顶指数器减 1，当空栈时，将栈顶指数器置为 -1，表示栈已空。
-
基于链表实现：因为栈都需要一个栈顶指示器来表示栈是否已经到头，而链表的头指针即为第一个结点，因此，可以将链表的头指针作为栈底，当栈顶指示器指向头指针时（由于作为栈底，头指针的指针域指向空，而不是指向下一个结点），表示到达栈顶，此时如果执行出栈操作，则返回头指针元素，并将栈顶指示器置为空，表明栈已空。当压栈时，对给定元素创建一个链表结点，并将其指针域指向前一个结点，同时将栈顶指示器指向当前这个结点。
顺序栈（采用数组实现）的优点是实现简单，存取时定位方便，缺点是创建时底层数组大小固定，无法扩容。而链栈（采用链表实现）的优点是栈的长度可以无限大，缺点是每个栈元素都额外携带一个指向上一个元素结点的指针域，内存开销大一些。
我们采用链表的形式实现栈。
// Stack.h
#pragma once
#ifndef __STACK_H__
#define __STACK_H__
#include <initializer_list>
#include <stdexcept>
template<typename T> struct Node {
Node(T ele, Node *prev) :element(ele), prev(prev) {}
T element;
Node *prev;
};
template<typename T>
class Stack {
public:
Stack() = default;
Stack(const std::initializer_list<T> datas){
for (auto &data : datas) {
this->push(data);
}
}
~Stack() {
this->clear();
}
const T& operator[](int index) const {
int cur = 0;
Node<T> *p = top;
while (p && cur++ < index) {
p = p->prev;
}
return p ? p->element : NULL;
}
public:
void clear() {
Node<T> *p = top;
Node<T> *temp = nullptr;
while (p) {
temp = p->prev;
delete p;
p = temp;
}
}
void push(const T &value) {
Node<T> *p = new Node<T>(value, top);
top = p;
}
T pop() throw(std::exception) {
if (top == nullptr) {
throw std::exception("stack is empty!");
}
T value = top->element;
Node<T> *p = top;
top = top->prev;
delete p;
return value;
}
private:
Node<T> *top = nullptr; // 栈顶指示器
};
#endif
队列（Queue）
定义：队列（Queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
特性：队列只具有入队和出队操作，并且具备 先进先出（FIFO） 特点，从队尾插入，从队头取出。
Queue
基本操作：入队，出队。
队列与栈类似，同样可以由线性表的 顺序存储结构（即数组） 或 链式存储结构（即链表） 来进行实现。
-
基于数组实现：入队时，直接把元素放置到数组的当前尾位置即可，出队时，由于队列只能在对头出队，因此数组索引为 0 的元素就会被移出，然后还需把数组后面的内容依次复制前进一个位置。因此，在基于数组实现的队列中，插入操作的时间复杂度为
，而删除操作的时间复杂度为
。
注：数组实现的一个改进方法就是定义头尾两个索引，插入数据时，头索引不变，尾索引递增，删除数据时，头索引递增，尾索引不变。若数据插入超出数组大小，则插入可添加到数组开头位置，形成一个环形数组。只要头索引不等于尾索引，就表示队列不为空。这样子，插入和删除操作的时间复杂度都为
-
基于链表实现：由于队列具备入队，出队操作，因此，其一般都配备有相应的队头指针和队尾指针，分别指向当前入队，出队位置。初始时，队头指针和队尾指针都指向链表头结点；入队时，队尾指针指向该新元素结点，出队时，队头指针（即头结点）指针域指向下一个结点，如果此时出队的是队尾指针，则出队后，还需将队尾指针指向头结点。基于链表实现的队列其入队，出队的时间复杂度均为
下面以基于链表的方式实现队列：
#pragma once
#ifndef __QUEUE_H__
#define __QUEUE_H__
#include <initializer_list>
template<typename T>
struct Node {
Node(T ele, Node<T> *next) :element(ele), pNext(next) {}
T element;
Node<T> *pNext;
};
template<typename T>
class Queue {
public:
Queue() = default;
Queue(std::initializer_list<T> datas) {
for (auto &data : datas) {
this->enqueue(data);
}
}
~Queue() {
this->clear();
delete this->pFront;
}
public:
void clear() {
Node<T> *p = nullptr;
while (this->pFront != this->pRear) {
this->dequeue();
}
}
Queue& enqueue(const T &value) {
Node<T> *p = new Node<T>(value, nullptr);
this->pRear->pNext = p;
this->pRear = p;
return *this;
}
T dequeue() {
if (this->pFront == this->pRear) {
return NULL;
}
Node<T> *p = this->pFront->pNext;
T value = p->element;
this->pFront->pNext = p->pNext;
if (p == this->pRear) {
this->pRear = this->pFront;
}
delete p;
return value;
}
private:
Node<T> *pFront = new Node<T>(NULL, nullptr); // 队头指针:指向链表头结点
Node<T> *pRear = pFront; // 队尾指针
};
#endif
