Data Structure (SEU 2021 Spring) Review

Print Friendly, PDF & Email

数据结构期末复习

期末:70%,满分 100

  • 选择:20
  • 填空:10
  • 问答:50
  • 编程:20

Chapter 1 – 绪论

\text{Algorithms} + \text{Data Structures} = \text{Programs}

四种逻辑结构

  1. 线性结构
  2. 树型结构
  3. 图状结构
  4. 集合

抽象数据类型

抽象数据类型可以定义是三元组:
ADT=(D,S,P)
其中:D是数据对象,
SD上的关系集,
P是对D的基本操作集。

算法分析

  • 算法特性:有穷、确定、可行、输入、输出
  • 评价标准:正确、可读、健壮、效率、通用
  • 效率度量:渐近时间复杂度、空间复杂度

一般地,算法的空间复杂度指的是辅助空间

Chapter 2 – 线性表

前驱、后继

两种存储方式

线性、链形

时间复杂度的计算

集合的“并”运算

线性表的合并

书 P42

void MergeList(List& LA, List& LB) {
    int m = ListLength(LA);
    int n = ListLength(LB);
    // 和书上不一样,我这里下标按照国际惯例,从 0 开始
    // 注意良好习惯的养成,不能和教材那样
    // 顺带吐槽一句,教材的代码都不是等宽字体,出版太不专业了
    for (int i = 0; i != m; i++) {
        GetElem(LB, i, e);
        if (!LocateElem(LA, e)) {
            // 如果 LA 中不存在元素 e,将其插入再 LA 最后
            ListInsert(LA, m++, e);
        }
    }
}

时间复杂度O(m\times n)

有序表的合并

书 P43
每次只需要再LALB中最小的那两个中选择即可,这是有序表带来的好处。

时间复杂度O(m + n)

循环链表

判断为空用 head == rear

双向链表

尤其插入删除操作

Chapter 3 – 栈和队列

栈有顺序栈和链栈。

链栈的单链表指向是从栈顶指向栈底。

// 栈顶指针 HS,插入指针 p
s->link = HS; // 指针向下指
HS = s;       // 更新栈顶指针

队列

循环队列

判断为空用 front == rear
判断为满用 (rear + 1) % MAXQSIZE == front

链队

判断为空用 front == rear

Chapter 4 – 串

Brute-Force

// 返回模式 T 在主串 S 中第 pos 个字符开始第一次出现的位置,
// 不存在则返回 0
int index_BF(SString S, SString T, int pos) {
    i = pos;
    j = 1;
    // 两个串均未比较到串尾
    while (i <= S.length && j <= T.length) {
        if (S.ch[i] == T.ch[j]) {
            i++;
            j++;
            // 继续比较后续字符
        } else {
            // 指针后退重新比较
            // 这里 i 走到刚开始的后面一个位置
            // (注意,j 是从 1 开始,很不好的习惯!)
            i = i - j + 2;
            j = 1;
        }
    }
}

最好情况平均时间复杂度O(n + m)
最坏情况平均时间复杂度O(n\times m)

KMP

每当一趟匹配过程出现字符不相等时,主串指示器不用回溯,而是利用已经得到的“部分匹配”结果,将模式串的指示器向右“滑动”尽可能远的一段距离后,继续进行比较。

示例:
next 函数手动计算示例1
next 函数手动计算示例2

规律总结为:1 对应 0,2 对应 1,之后的考虑这个序号前面一个(不包括自己)能够与开头有多少重合的长度,这个长度加 1 就是 next 值。

// 返回模式 T 在主串 S 中第 pos 个字符开始第一次出现的位置,
// 不存在则返回 0
int index_KMP(SString S, SString T, int pos) {
    i = pos;
    j = 1;
    // 两个串均未比较到串尾
    while (i <= S.length && j <= T.length) {
        if (j == 0 || S.ch[i] == T.ch[j]) {
            i++;
            j++;
            // 继续比较后续字符
        } else {
            // 指针不用回溯
            // 模式串向右移动
            j = next[j];
        }
    }
    if (j > T.length) {
        // 匹配成功
        return i - T.length;
    } else {
        // 匹配失败
        return 0;
    }
}

计算 next 值:

void get_next(SString T, int next[]) {
    int i = 1;
    next[1] = 0;
    j = 0;
    while (i < T.length) {
    if (j == 0 || T.ch[i] == T.ch[j]) {
        // 继续符合,那就加一
        next[++i] = ++j;
    } else {
        // 又不符合了,那么根据原来的原理,就是 next[j]
        j = next[j];
    }
}

时间复杂度O(m+n)

next 的修正:

void get_nextval(SString T, int nextval[]) {
    i = 1;
    nextval[1] = 0;
    j = 0;
    while (i < T.length) {
    if (j == 0 || T.ch[i] == T.ch[j]) {
        i++;
        j++;
        if (T.ch[i] != T.ch[j]) {
            nextval[i] = j;
        } else {
            // 如果还是相等,我们还可以多跳一些
            nextval[i] = nextval[j];
        }
    } else {
        // 又不符合了,那么根据原来的原理,就是 nextval[j]
        j = nextval[j];
    }
}

Chapter 5 – 数组与广义表

数组

稀疏矩阵

稀疏矩阵的转置
设矩阵列数为 Cols,对矩阵三元组表扫描Cols 次。第 k 次检测列号为 k 的项。
第 k 次扫描找寻所有列号为 k 的项,将其行号变列号、列号变行号,顺次存于转置矩阵三元组表。
时间复杂度O ( nu\times tu )

快速转置算法的思想为:对原矩阵A扫描一遍,保存A中每一列号非零元的个数,立即确定在转置矩阵 B 三元组表中的位置,并装入它。
时间复杂度O ( nu + tu )

十字链表

typedef struct OLNode {
    int i ,j ;      // 行号和列号
    Elemtype e ;    // 元素值
    struct  OLNode  *down , *right ;
} OLNode, *OLink;   // 非 0 元素结点

typedef struct {
    int mu, nu, tu;
    OLink *rhead ;  //行列链表头指针向量
    OLink *chead ;
} CrossList;

广义表

广义表中括号的最大层数称为表深 (度)

据说只考深度的判断。

Chapter 6 – 树与二叉树

二叉树的链式存储

二叉链表,三叉链表

二叉树遍历

教材 P121

以下前序、中序、后续均只给出了非递过算法,递归算法比较好理解。

递归可以让你写出程序,而迭代则能让你写出好程序。”所以,在这里我们不应该只满足于递归算法。(迭代效率高于递归)

前序

DLR

先访问自己,既想要先把左孩子给访问了,又不忘同时把右孩子揣在兜里。

void PreOrderTraverse(BiTree T) {
    InitStack(S);
    // p 是节点的指针
    p = T;
    q = new BiTNode;
    while (p)
    {
        // 管他三七二十一,访问了再说
        visit(p->data);

        // 先顾虑右孩子
        if (p->rchild) {
            // 如果有右孩子,就先存着
            Push(S, p->rchild);
        }

        // 再访问左孩子
        if (p->lchild) {
            // 还有左孩子,继续偏袒他,优先访问!
            p = p->lchild;
        } else {
            // Em, 没有左孩子了,算了,右孩子还有库存
            Pop(S, p);
        }
    }
}

中序

LDR

非递归中序遍历算法(一路向左使用栈存储自己的足迹,出栈时访问该节点,并访问右子树)

void InOrderTraverse(BiTree T) {
    InitStack(S);
    // p 是节点的指针
    p = T;
    q = new BiTNode;
    while (p || !StackEmpty(S))
    {
        if (p) {
            // 根指针进栈,遍历左子树
            Push(S, p);
            p = p->lchild;
        } else { // 走到底啦,是时候回头了
            // 走回上一步(即栈顶节点)
            Pop(S, q);
            // 访问这个节点
            visit(q->data);
            // 遍历右子树
            p = q->rchild;
        }
    }
}

后序

LRD

无私奉献的家长啊!优先左孩子,当左孩子交回访问权时,父节点将其传给了右孩子。只有当他们两个全部访问过才轮到自己。那么,这里两次回到自己,但只有第二次才访问,所以需要标记(tag)来记录。

void PostOrderTraverse(BiTree T) {
    InitStack(S);
    // p 是节点的指针
    p = T;
    // w 是带有标记的节点(瞎取了一个类型,Em,看得懂就行)
    w = new BiTNode_with_tag;
    do {
        // w 主要还是这个 p 的遍历指针
        w.ptr = p;
        // 默认标记为 L(左子树)之前要 enum BTNodeTag { L, R };
        w.tag = L;
        int keep_going = 1;
        while (keep_going && !StackEmpty(S)) {
            // 看看访问列表里还有谁
            Pop(S, w);
            p = w.ptr;
            switch (w.tag) {
            case L: // 第一次返回父节点
                // 第一次经过,不访问,留着下一次再访问
                // 不过 tag 要修改,表示已经访问过一次了
                w.tag = R;
                Push(S, w);
                // 马上去右孩子了,不用继续往库存里找了
                keep_going = 0;
                p = p->rchild;
                break;
            case R: // 第二次返回父节点
                // 尽完自己的义务,终于可以访问自己了
                visit(p);
                break;
            }
        }
    } while (!StackEmpty(S));
}

层次

使用队列辅助,在处理上一层时,将其下一层的结点直接进到队列(的队尾)。
在上一层结点遍历完后,下一层结点正好处于队列的队头,可以继续访问它们。
算法是非递归的。

void LevelOrderTraverse(BiTree T) {
    // p 是节点的指针
    p = T;
    if (!p) return;
    InitQueue(Q);
    visit(p);
    // 根节点入队
    EnQueue(Q, p);
    while (!QueneEmpty(Q)) {
        // 一次访问一个,出队
        DeQueue(Q, p);
        if (p->lchild) {
            // 访问左孩子并入队
            visit(p->lchild);
            EnQueue(Q, p->lchild);
        }
        if (p->rchild) {
            // 访问右孩子并入队
            visit(p->rchild);
            EnQueue(Q, p->rchild);
        }
    }
}

深度优先

  • 先根次序遍历:和对应二叉树前序遍历结果一样
  • 后根次序遍历:和对应二叉树中序遍历结果一样

广度优先

层次遍历

线索式中序遍历的前驱后继

Huffman 树

Chapter 7 – 图

基本概念

  • 顶点的度
  • 路径
  • 连通图与连通分量(非强连通图的极大强连通子图叫做强连通分量

最小生成树

教材 P165

Prim 算法

选点

精髓:Em,像是转发广告,凡是邀请到新用户(就是边的其中一个端点已有,另一个一定不在这个已选出的集合内),且新用户最好(此处就是权值最小啦),他就入伙!最终实力壮大,将整个世界囊括进来了,过程结束。

假设N=(V,E)是连通网,TEN上最小生成树中边的集合。

  1. U=\{u_0\}(u_0\in V), TE=\{\}
  2. 在所有u\in U, v\in V-U的边(u,v)\in E中找一条权值最小的边加入集合TE,同时v_0并入U
  3. 重复 2,直至U=V为止。

此时TE必有n-1条边,则T=(V,TE)N的最小生成树。

时间复杂度O(n^2)

Kruskal 算法

选边

精髓:一直要便宜货,一直寻找权值最小的边(但是发现形成环了会浪费的话那就不要了),直至所有的都被囊括进来了。

  1. 最初先构造一个只有 n 个顶点, 没有边的非连通图 T = \{ V, \varnothing \}, 图中每个顶点自成一个连通分量。
  2. 当在 E 中选到一条具有最小权值的边时, 若该边的两个顶点落在不同的连通分量上,则将此边加入到 T 中; 否则将此边舍去,重新选择一条权值最小的边。
  3. 如此重复下去, 直到所有顶点在同一个连通分量上为止。

时间复杂度O(e\log e)(主要时间花在了给所有的边权值排序的过程上了)

图的存储

邻接矩阵、邻接表

个人觉得题目写起来会比较容易,因为在原理上不会有太多困难。

DFSBFS

深度优先遍历(DFS)

DFS
解决方案:

广度优先遍历(BFS)

BFS
解决方案:队列

拓扑排序

书 P176

Pro Tip: 不应该出现闭环
拓扑排序就是将 AOV-图所有顶点排成一个线性序列。
过程

  1. 在有向图中选一个无前驱的顶点(indegree 为 0)且输出它。
  2. 从图中删除该顶点和所有以它为尾的弧。
  3. 重复 1 和 2,直至不存在无前驱的顶点(没有环的话就是全部输出)。
  4. 若此时输出的顶点数小于有向图中的顶点数,则说明有向图中存在环,否则输出的序列极为一个拓扑序列。
// 有向图 G 用邻接表存储
// 若 G 无回路,生成一个拓扑序列 topo[]
// 并返回状态 (OK 或 ERROR)
Status TopologicalSort(ALGraph G, int topo[]) {
    // 各顶点 indegree 存在这个数组中
    FindInDegree(G, indegree);
    InitStack(S);
    for (int i = 0; i < G.vexnum; i++) {
        if (!indegree[i]) { // same as if (indegree[i] == 0)
            // indegree 为 0 的入栈
            Push(S, i);
        }
    }

    int m = 0;
    while (!StackEmpty(S)) {
        // 栈顶 v_i 出栈
        Pop(S, i);
        // 将这个点存入 topo 数组中,计数加一
        topo[m++] = i;
        // p 指向 v_i 的第一个邻接点
        p = G.vertices[i].firstarc;

        // while 循环内容:删除所有相邻的边
        while (p) { // same as while (p != nullptr)
            // v_k 为 v_i 的邻接顶点
            k = p->adjvex;
            indegree[k]--;
            if (!indgree[k]) {
                // 现在,这个顶点也沦落为 indegree 的顶点(等着被消灭吧)
                Push(S, k);
            }
            // 下一个邻接顶点
            p = p->nextarc;
        }
        p = G.vertices[i].firstarc;
    }
    if (m < G.vecnum) {
        // 图 G 存在回路
        return ERROR;
    } else {
        // 拓扑排序已完成
        return OK;
    }
}

关键路径

完成整个工程所需的时间取决于从源点到汇点的最长路径长度, 即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。

  1. 事件v_i的最早发生时间ve(i)
    ve(0)=0
    ve(i)=\max \{ve(k)+w_{k,i}\}\quad <\!v_k,v_i\!>\in T, 1\leqslant i\leqslant n-1

  2. 事件v_i的最迟发生时间vl(i)
    vl(n-1)=ve(n-1)
    vl(i)=\min \{vl(k)-w_{i,k}\}\quad <\!v_k,v_i\!>\in T, 0\leqslant i\leqslant n-2

  3. 活动a_i=<\!v_j,v_k\!>的最早开始时间e(i)
    e(i)=ve(j)

  4. 活动a_i=<\!v_j,v_k\!>的最迟发生时间l(i)
    l(i)=vl(k)-w_{j,k}

e(i)=l(i),则活动a_i是关键活动。

最短路径

Dijkstra算法

Dijkstra算法

Chapter 8 – 查找

顺序表查找

二叉搜索树

书 P198

又名:二叉排序树

最优的二叉搜索树的任何子树都是最优二叉搜索树。

插入操作

void InsertBST(BSTree& T, ElemType T) {
    if (!T) { // same as if (T == nullptr)
        // 这就是走到该插入的位置了,因为指针已经是  nullptr 了
        S = new BSTNode;
        S->data = e;
        S->lchild = S->rchild = nullptr;
        // 插入进去
        T = S;
    } else if (e.key < T->data.key) {
        // 进左子树
        InsertBST(T->lchild, e);
    } else if (e.key > T->data.key) {
        // 进右子树
        InsertBST(T->rchild, e);
    } // otherwise: e.key == T->data.key,已有这个元素,不需要做任何操作
}

时间复杂度O(\log n)(主要时间用在查找上)

删除操作

  • 删除叶结点,只需将其双亲结点指向它的指针清零,再释放它即可。
  • 被删结点右子树为空,可以拿它的左子女结点顶替它的位置,再释放它。
    右子树为空
  • 被删结点左子树为空,可以拿它的右子女结点顶替它的位置,再释放它。
    左子树为空
  • 被删结点左、右子树都不为空,可以在它的右子树中寻找中序下的第一个结点(关键字最小,也就是右子树的左节点一路向左的最后一个节点,而且有一个利好消息,这个节点自己是没有左孩子的,就很好处理!),用它的值填补到被删结点中,再来处理这个结点的删除问题。
    左右子树都不为空

二叉平衡树

书 P205

一棵 AVL 树或者是空树,或者是具有下列性质的二叉搜索树:它的左子树和右子树都是 AVL 树,且左子树和右子树的高度之差的绝对值不超过1
每个结点附加一个数字,给出该结点左子树的高度减去右子树的高度所得的高度差,这个数字即为结点的平衡因子bf。
平衡化旋转有两类:

  • 单旋转 (左旋和右旋)
  • 双旋转 (左平衡和右平衡)

如果在某一结点发现高度不平衡,停止回溯。从发生不平衡的结点起,沿刚才回溯的路径取直接下两层的结点。
如果这三个结点处于一条直线上,则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转。
如果这三个结点处于一条折线上,则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。
zig-zag

右单旋转 (RotateRight)

LL型:在结点A的左子女的左子树中插入新结点,该子树高度增1导致结点A的平衡因子变成2,出现不平衡。为使树恢复平衡,让结点A顺时针旋转。
单右旋转

左单旋转 (RotateLeft)

RR型:在结点A的右子女的右子树中插入新结点,该子树高度增1导致结点A的平衡因子变成2,出现不平衡。为使树恢复平衡,让结点A反时针旋转。
单左旋转

先左后右双旋转 (RotationLeftRight)

LR型:在结点A的左子女的右子树中插入新结点,该子树高度增1导致结点A的平衡因子变为-2,造成不平衡。
以结点C为旋转轴,将结点B反时针旋转,以C代替原来B的位置。
左右双旋1

再以结点C为旋转轴,将结点A顺时针旋转。使之平衡化。
左右双旋2

直接看结果的话,就是将 C 提上来,B 和 A 一左一右,A 接上 C 的右孩子。

先右后左双旋转 (RotationRightLeft)

RL型:这个类似于 先左后右双旋转。

AVL 树的插入

例如,输入关键字序列为 { 16, 3, 7, 11, 9, 26, 18, 14, 15 },插入和调整过程如下。
AVL插入1
AVL插入2
AVL插入3
AVL插入4
AVL插入5

B树

书 P210

散列表

书 P219

  • 散列查找法:Hash Search

  • 散列函数的构造:数字分析法(事先知道关键字每一位上个数字的分布情况)、平方取中法(直接取树平方后的中间几位)、折叠法(将数字割成各部分,叠加求和)、除留余数法

  • 处理冲突的解办法 (重点):开放地址法、链地址法

    开放地址法
    思路:冲突后探测下一个可以的位置。

    1. 线性探测法(假想为循环表,逐个向下寻找,增量序列为 d_i=1,2,3,\cdots,m-1
    2. 二次探测法(增量序列为 d_i=1^2,-1^2,2^2,-2^2,3^2,\cdots,+k^2,-k^2\ (k\leqslant m/2)
    3. 伪随机探测法(d_i=\text{伪随机数序列}

    链地址法
    思路:相同地址的记录放在同一个单链表里(同义词链表)

  • 散列表的查找:平均查找长度

Chapter 9 – 排序

排序算法的 C++ 实现见我的 GitHub 仓库:TVJ_Sort

插入排序

这个简单,分为直接插入排序折半插入排序,区别仅在查找插入的位置上。

稳定

冒泡排序

冒泡排序(Bubble Sort)和快速排序(Quick Sort)都属于交换排序,基本思想是两两比较待排序元素的排序码,如发生逆序(即排列顺序与排序后的次序正好相反),则交换之。直到所有元素都排好序为止。只不过这两者在比较、交换的实现上有很大的差异。

稳定

希尔排序

书 P239

不稳定

选择排序

简单选择排序

亦称为“直接选择排序”。

不稳定

树形选择排序

亦称为“锦标赛排序”。

快速排序

书 P243

快排的过程可以看我的博客 快速排序

// 表中从 r[low..high] 排序,返回枢轴的位置
int Partition(SqList& L, int low, int high) {
    // 闲着也是闲着,0 这个位置就可以用来记录枢轴数据
    L.r[0] = L.r[low];
    int pivotkey = L.r[low].key;
    // 两个指针还没有碰到一起,则继续
    while (low < high) {
        // high 指针向左移
        while (low < high && L.r[high].key >= pivotkey) high--;
        L.r[low] = L.r[high];
        // low 指针向右移
        while (low < high && L.r[low].key <= pivotkey) low++;
        L.r[high] = L.r[low];
    }
    // 枢轴自己的值是时候回来了
    L.r[low] = L.r[0];
    // low 就是我们要的枢轴的值
    return low;
}

堆排序

书 P249
以大根堆为示例,亦可以是小根堆。

步骤

  1. 调整为最大堆,并交换r[1]r[n]r[n]则是关键字最大的记录。
  2. r[1..n-1]重新调整为堆,交换r[1]r[n-1],则r[n-1]为关键字次大的记录。
  3. 循环 n-1 次,直到交换了 r[1]r[2]为止,得到了单调不减的有序数列。

调整堆

只需调整含最后一个元素的一路即可。

我们调整的是“身在其位,不谋其政”的节点,也就是子女节点都比他大了,他就该退位,但是说不定依然不行,还没孙子大[Doge],就这样一路向下检查。
这样的检查应该从最低层的开始检查起,因而效果是总体从下往上,每一个检查的点都由上往下。

// r[s+1..m] 已经是堆,现在将 r[s..m] 调整为以 r[s] 为根的大根堆
void HeapAdjust(Sqlist& L, int s, int m) {
    Key_Type rc = L.r[s];
    for (int j = 2 * s; j <= m; j *= 2) {
        // 先选出两个子女节点大的那一个进行和父节点比较
        if (j < m && L.r[j].key < L.r[j + 1].key) j++;
        if (rc.key >= L.r[j].key) {
            // 父节点终于比两个孩子大了,篡位的游戏终于结束啦,把 rc 插回去
            L.r[s] = rc;
        } else {
            // 把父节点的位置给占了(别担心他老人家,rc 已存下来了)
            L.r[s] = L.r[j];
            s = j;
            // 这孩子还有希望,继续向上爬!
        }
    }
}

void QSort(SqList& L, int low, int high) {
    if (low < high) {
        // 分治的分界点(枢轴)
        int pivotloc = Partition(L, low, high);
        // 递归调用(左边和右边分别)
        QSort(L, low, pivotloc - 1);
        QSort(L, pivotloc + 1, high);
    }
}

void QuickSort(SqList& L) {
    QSort(L, 1, L.length);
}

建初堆

void CreateHeap(SqList& L) {
    n = L.length;
    // 反复调整即可(显然,叶节点不需要考虑)
    for (int i = n / 2; i > 0; i--) {
        HeapAdjust(L, i, n);
    }
}

堆排序

void HeapSort(SqList& L) {
    // 生成大根堆
    CreateHeap(L);
    for (int i = L.length; i > 1; i--) {
        // 交换堆顶记录和未排序的部分的最后一个记录
        swap(L.r[1], L.r[i]);
    }
}

性能分析

复杂度 最好情况 最坏情况 平均情况
时间复杂度 O(n\log n) O(n^2) O(n\log n)
空间复杂度 O(\log n) O(n) O(\log n)

归并排序

书 P254

过程:两个两个一组,一级一级向上合并。(而写的时候递归即逐渐拆分,直至还剩两个元素的时候)

// 将有序表 R[low..mid] 和 R[mid+1..high] 归并为有序表 T[low..high]
void Merge(RedType R[], RedType T[], int low, int high) {
    int i = low, j = mid + 1, k = low;
    while (i <= mid && j <= high) {
        if (R[i].key <= R[j].key) {
            T[k++] = R[i++];
        } else {
            T[k++] = R[j++];
        }
        // 现在还会有一个有序表还有剩余,不管是谁,全部走一遍看看就行了
        while (i <= mid)  T[k++] = R[i++];
        while (j <= high) T[k++] = R[j++];
    }
}

// R[low..high] 归并后放入 T[low..high]
void MSort(RedType R[], RedType T[], int low, int high) {
    if (low == high) {
        // 这其实就是递归的终止条件
        T[low] = R[low];
    } else {
        // 其实书上 P255 的代码写的是有问题的:
        // 虽然这个相加除以二效果一样,但是运算是先计算 high + low 的,
        // 也就是在 high + low 的计算就可能会发生溢出,这是我们所不希望的。
        int mid = low + (high - low) / 2;
        // 左边一半排序
        MSort(R, S, low, mid);
        // 右边一半排序
        MSort(R, S, mid + 1, high);
        // 合并
        Merge(S, T, low, mid, high);
    }
}

说归并排序需要额外的空间存储,其实没有必要的,归并排序的意义其实就是为链表而生,甚至单链表也可以!这真是太神奇了!这是我用 C++ 写的 tvj::forward_list 仿照 MSVC 的写法写的单链表的排序。

    template<typename Elem>
    typename forward_list<Elem>::Node* forward_list<Elem>::_inplace_merge(Node* first_, Node* mid_, Node* last_, bool is_ascending) {
        auto i = first_->succ;
        auto j = mid_->succ;
        auto pre_end = last_->succ;
        auto h = first_;
        while (i && i != mid_->succ && j && j != last_->succ) {
            if ((i->data < j->data) ^ !is_ascending) {
                h = h->succ = i;
                i = i->succ;
            } else {
                h = h->succ = j;
                j = j->succ;
            }
        }
        while (i && i != mid_->succ) {
            h = h->succ = i;
            i = i->succ;
        }
        while (j && j != last_->succ) {
            h = h->succ = j;
            j = j->succ;
        }
        h = pre_end;
        return (last_->data < mid_->data) ^ !is_ascending ? mid_ : last_;
    }

    template<typename Elem>
    typename forward_list<Elem>::Node* forward_list<Elem>::_sort2(Node* first, bool is_ascending) {
        if (is_ascending ^ (first->succ->data < first->succ->succ->data)) {
            auto tmp = first->succ->data;
            first->succ->data = first->succ->succ->data;
            first->succ->succ->data = tmp;
        }
        return first->succ->succ;
    }

    template<typename Elem>
    typename forward_list<Elem>::Node* forward_list<Elem>::_sort(Node* first, size_t bound, bool is_ascending) {
        if (bound == 0) return nullptr;
        if (bound == 1) return first->succ;
        if (bound == 2) return _sort2(first, is_ascending);
        const auto half_bound = bound / 2;
        const auto mid_node = _sort(first, half_bound, is_ascending);
        const auto last_node = _sort(mid_node, bound - half_bound, is_ascending);
        return _inplace_merge(first, mid_node, last_node, is_ascending);
    }

    template<typename Elem>
    void forward_list<Elem>::sort(bool is_ascending) {
        _sort(head, size_, is_ascending);
    }

基数排序

书 P256

思路就是先排低位再排高位,由于队列中先后顺序是保证的,当最高位也排完时,可以数据已经排好序了。

void RadixSort(SLList& L) {
    for (int i = 0; i != L.recnum; i++) {
        L.r[i].next = i + 1;
    }
    L.r[L.recnum].next = 0;
    for (int i = 0; i < L.keynum; i++) {
        // 分配,也就是按照特定的那一位入不同的队列
        Distribute(L.r, i, f, e);
        // 收集,也就是按照顺序排好队,从队里出来。
        Collect(L.r, i, f, e);
    }
}

加粗标题内容为 Teddy van Jerry 较为生疏的内容。


ALL RIGHTS RESERVED © 2021 Teddy van Jerry
欢迎转载,转载请注明出处。
https://blog.teddy-van-jerry.org/data-structure/data-structure-seu-2021-spring-review

2 Responses

  1. Adamancy Li says:

    好耶,我的数据结构没挂!

  2. bcnaqlbvi tmohg ixyapfz mbsc qfigpjdigiwhuit

Leave a Reply

Your email address will not be published. Required fields are marked *