【木灵的程序工作室】数据结构的C/C++描述02.00：链表 · 单链表

写在前面：读本节，您可能得先读懂01：数组和动态数组，由于本节有超过200行的代码，所以您可能也得有一点读代码的能力和耐心。我会尽量保证代码风格良好。

链表

链表是另一个最基本的线性数据结构。
链表由若干单元组成，每一个单元都由实际存放的数据和下一个单元的地址组成。
可能不太好理解，以一个非常浅显的例子打个比方：

很多游戏都有一种解谜任务，开始的时候NPC告诉玩家密码的第一位是‘3'，然后说：想要知道密码的下一位，请去XXX地点。成功去XXX地点之后，得到一张字条，写着“密码的第二位是'4'，想要知道下一位，请去XXX地点”...
这就是一种逻辑上的链表。C/C++中的链表需要支持顺序访问和读写。

那么我们来简单实现一个链表：
构造一个链表需要两步：1、定义并创建节点 2、将节点连起来
首先定义节点：定义节点用到了C/C++中的结构体类型。

template<class elementType> 
struct node {
    elementType data;
    node<elementType> *next;
    node(elementType _data, node<elementType>* _next) {
        data = _data;
        next = _next;
    }
};

我们可以仅仅使用这一个结构体完成所有的链表操作。但是根据C++的封装思想，我们给它写一个类简单地封装起来：（事实上一般的OJ题目都是直接在结构体上使用指针操作的）
以下是类的架构：（本实现中，表头的数据(data)部分不存放任何有效信息）

template<class elementType> 
class chainList {
protected:
    node<elementType> *head = nullptr;
    int length = 0;
    bool validIndex(int index) { return index >= 0 && index < length; }
public:
    chainList();
    chainList(const chainList<elementType> &copyList);
    chainList(const vector<elementType> &copyVector);
    ~chainList();
    void makeEmpty();

    int size() const { return length; }
    bool empty() const { return length == 0; }
    chainList<elementType>& operator=(const chainList<elementType> &A);

    elementType& operator[](const unsigned int index);
    void pop(const unsigned int index);
    void push(elementType val, const unsigned int index);
    void merge(chainList<elementType> const &A);
};

简单实现一下：
构造函数：缺省构造函数、复制构造函数、由动态数组建立链表的构造函数和析构函数

template<class elementType> 
chainList<elementType>::chainList() {
    if (this->length != 0)
        this->makeEmpty();
    if (this->head == nullptr) this->head = new node<elementType>;
    this->length = 0;
}

template<class elementType>
chainList<elementType>::chainList(const chainList<elementType> &copyList) {
    if (this->length != 0)
        this->makeEmpty();
    if (this->head == nullptr) this->head = new node<elementType>;
    this->length = 0;
    *this = copyList;
}

template<class elementType>
chainList<elementType>::chainList(const vector<elementType> &copyVector) {
    if (this->length != 0)
        this->makeEmpty();
    if (this->head == nullptr) this->head = new node<elementType>;
    this->length = 0;
    if (copyVector.empty()) return;
    node<elementType> *str = head;
    for (int i = 0; i < copyVector.size(); i++) {
        node<elementType> *tempPtN = new node<elementType>(copyVector[i]);
        str->next = tempPtN;
        str = str->next;
    }
    this->length = copyVector.size();
}

template<class elementType>
chainList<elementType>::~chainList() {
    this->makeEmpty();
    delete head;
}

置空方法和赋值重载

template<class elementType>
void chainList<elementType>::makeEmpty() {
    node<elementType> *str = head -> next;
    while (str != nullptr) {
        node<elementType> *tempPtN = str->next;
        delete str;
        str = tempPtN;
    }
    head->next = nullptr;
}

template<class elementType>
chainList<elementType>& chainList<elementType>::operator=(const chainList<elementType> &A) {
    if (!this->empty()) this->makeEmpty();
    if (A.empty()) return *this;
    node<elementType> *strThis = head, *strThat = A.head;
    while (strThat != nullptr) {
        strThis->data = strThat->data;
        if (strThat->next != nullptr) {
            node<elementType> *tempPtN = new node<elementType>;
            strThis->next = tempPtN;
        }
        strThis = strThis->next, strThat = strThat->next;
    }
    this->length = A.length;
    return *this;
}

几个基本操作：

template<class elementType>
elementType& chainList<elementType>::operator[](const unsigned int index) {
    if (!this->validIndex(index)) throw("Invalid Index");
    node<elementType> *str = this->head;
    for (int i = 0; i < index + 1; i++){
        str = str->next;
    }
    return str->data;
}

template<class elementType>
void chainList<elementType>::pop(const unsigned int index) {
    if (!this->validIndex(index)) throw("Invalid Index");
    node<elementType> *str = this->head;
    for (int i = 0; i < index; i++){
        str = str->next;
    }
    node<elementType> *tempPtN = str->next;
    str->next = tempPtN->next;
    delete tempPtN;
    this->length--;
}

template<class elementType>
void chainList<elementType>::push(elementType val, const unsigned int index) {
    this->length++;
    if (!this->validIndex(index)) throw("Invalid Index");
    node<elementType> *str = this->head;
    for (int i = 0; i < index; i++){
        str = str->next;
    }
    node<elementType> *tempPtN = new node<elementType>(val, str->next);
    str->next = tempPtN;
}

template<class elementType>
void chainList<elementType>::merge(chainList<elementType> const &A) {
    chainList<elementType> tempChain(A);
    node<elementType> *str = this->head;
    while (str->next != nullptr) {
        str = str->next;
    }
    str->next = tempChain.head->next;
    this->length += tempChain.length;
    tempChain.head->next = nullptr;
};

这个链表的实现对于“有圈链表”是非常敏感的，只要链表存在圈，这个实现中的大部分方法就会陷入死循环。好在我们可以通过对方法的仔细调整来避免产生圈，只要用户以常规方式调用public成员，我们的链表的“无圈性”就得以保证。这也是面向对象编程的数据封装原则的优势所在。
关于一个链表是否有圈这一问题我会在以后的文章中讨论。

实际上使用如上的封装类操作链表的效率是低于用指针或者迭代器操作链表的。比如：使用封装类的重载运算符[]来遍历一个长度为n的链表所需的渐近时间复杂度是O(n^2)，而使用指针的next成员遍历一个长度为n的链表的渐近时间复杂度仅是O(n)。

何时使用表头以及为何使用表头？

在上述实现中，我们引入了一个不存放任何实际数据的表头节点。在某些情况下，我们也可以将该节点虚拟化为一个指向首个元素的指针。但是，就单链表而言，使用表头节点可以使链表的首个元素“去特殊化”，也就是对于首个元素的插入和删除操作的代码可以与其他元素完全一致，但如果使用虚拟的头指针，则可能需要对于首个元素的插入和删除操作作特殊处理。
但是，在某些特殊的链表（如循环链表）中，我们一般不使用头节点，而使用虚拟的头指针。

链表的直接应用

链表对于离散且稀疏的数据处理效率很高，比如基数排序、模拟多项式、并查集等。
简单讨论一下基于链表的并查集：

并查集

首先介绍一个离散数学中“等价关系”的概念：设R是非空集合A上的关系，如果R满足：
xRy <=> yRx（对称）/ xRx（自反）/ xRy and yRz => xRz
则称R是一个等价关系。常见的等价关系有：相等、双向连通等。
一群两两等价的元素可以形成一个集合，这个集合就叫等价类。我们所谓并查集就是用来描述这种等价类的。

例1：
现在有城市ABCDEFGH，其中A-B A-E B-C C-D C-E C-F有双向公路连通，G-H有双向公路连通，请各位简单画一下他们的连通图。
可以看到这个图分为了两个区域，第一块是ABCDEF，第二块是GH，在第一块的人没有办法到达第二块。这两块区域分别各自形成一个基于公路连接关系的等价类。
问：随机输入两个城市，请您判断它们之间是否存在着一条交通线

这个问题存在许多的解法，包括但不限于Dijkstra路径算法、深度优先搜索等，也可以使用并查集。我们先暂时挂起这个问题，先把并查集的实现写了：
并查集有很多种实现方式：比如树实现、散列实现、数组实现、矩阵实现、链表实现、图实现等。我们使用一个数组和“以数组下标做next的节点”的形式上的链表节点来实现这一数据结构。

注意UFS这一结构体的next变量是一个整形数而不是指针！！意识到这一点将是你理解这一并查集实现的关键一环

struct UFSNode {
    unsigned int classNum;
    unsigned int size;
    unsigned int next;
};

class UFSChain {
private:
    vector<UFSNode> arr;
public:
    UFSChain(int initSize = 0);
    void unite(int classA, int classB);
    int operator[](unsigned int index) { return arr[index].classNum; }
};

UFSChain::UFSChain(int initSize) : arr(initSize) {
    for (int i = 0; i < arr.size(); i++) {
        arr[i].classNum = i;
        arr[i].size = 1;
        arr[i].next = -1;
    }
}

void UFSChain::unite(int classA, int classB) {
/***********************************
*  arr[classA].classNum指classA的头节点的标号
*  那么(arr[arr[classA].classNum]就是classA的头节点
*  理解这一点非常重要
***********************************/
    if (arr[arr[classA].classNum].size > arr[arr[classB].classNum].size) {
        swap(classA, classB);  //选择对较小集合进行操作以获得更快的运行速度
    }
    int str = arr[classA].classNum;
    arr[arr[classB].classNum].size += arr[arr[classA].classNum].size; //只有首节点的size成员会被调用，因此只需要维护首节点的size
    while (arr[str].next != -1) {
        arr[str].classNum = classB;
        str = arr[str].next;
    }
    arr[str].classNum = arr[classB].classNum;
    arr[str].next = arr[classB].next;
    arr[arr[classB].classNum].next = classA;
}

需要注意的是，我们在之后讨论并查集的树实现的合并方法时也会有一个比较两个并查集大小的代码块，但是它的作用与上述链表实现中的大小比较完全不同。

静态链表

这个并查集实现提示了另一种链表实现方式的可行性，即通过“下一个元素的数组下标”作为next成员进行链接。
实际上，因为有一部分高级语言不支持指针(比如BASIC)，这种链表的实现也经常被使用。这种链表的实现方式被称为链表的游标实现或者静态链表(国内研究生入学考试试题中通用的名词就是静态链表)。

练习

1、简单考虑为什么对于有圈链表来说，上述实现会失效；考虑如何高效判断一个链表有圈
2、用并查集做例1

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 216,163评论 6赞 498
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,301评论 3赞 392
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 162,089评论 0赞 352
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,093评论 1赞 292
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,110评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,079评论 1赞 295
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,005评论 3赞 417
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,840评论 0赞 273
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,278评论 1赞 310
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,497评论 2赞 332
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,667评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,394评论 5赞 343
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,980评论 3赞 325
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,628评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,796评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,649评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,548评论 2赞 352