数据结构与算法

发表于 更新于

0.0 PTA实录

0.1.1 最大子列和plus

  • 如何利用语句先后顺序记录上一条信息pre_start_tag
void sum_max_sequence(void)
{
    long long int this_sum, max_sum;
    int start_tag, end_tag, pre_start_tag, neg_tag;
    
    start_tag = pre_start_tag = end_tag = 0;
    this_sum = max_sum = 0;
    neg_tag = 1;

    for (int i = 0; i < num; i++)
    {
        if (list[i] >= 0) {
            neg_tag = 0;
        }
        this_sum += list[i];
        if (this_sum > max_sum)
        {
            max_sum = this_sum;
            end_tag = i;
            pre_start_tag = start_tag; // 我没有想到的代码！
        }
        if (this_sum < 0)
        {
            this_sum = 0;
            start_tag = i+1;
        } 
    }
    

    if(neg_tag) // 输出0，第一个和最后一个数
        printf("%lld %d %d\n", max_sum, list[0], list[num-1]);
    else if (max_sum == 0)
    {
        printf("0 0 0\n");
    }
    
    else
        printf("%lld %d %d\n", max_sum, list[pre_start_tag], list[end_tag]);
}

0.1.2 二分查找

  • 不递归，用循环实现二分查找线性表
Position BinarySearch( List L, ElementType X )
{
    Position mid, start, end;
    start = 1;
    end = L->Last;

    while (start <= end)
    {
        mid = (start + end) / 2;
        if (L->Data[mid] == X)
        {
            return mid;
        }
        else if (L->Data[mid] > X)
        {
            end = mid-1;
        }
        else if (L->Data[mid] < X)
        {
            start = mid+1;
        }
    }
    return NotFound;
}

0.2.1 一元多项式的乘法与加法

  1. 操作链表或指针，一定要来一个temp变量copy原来的链表！不然顺序就没了！
  2. 不是结构链表（存储的值>=2）的话不需要专门写一个插入函数
  3. 在运算之前一定要先检查有没有0，值不值得算，并且加上相应的处理代码
  4. 记得释放！free()用起来
  5. 有序插入链表：
    1. 要把链表遍历几次，每次都要找到可以插入的位置（按指数大小排序的位置）
    2. 处理系数为0的情况（不用插入，直接修改值）
    3. 插入链表：temp->next = rear->next; rear->next = temp; rear = rear->next;
  6. 仔细读题，把一些细节处理到位，如末尾不输出空格

0.2.2 两个有序链表的合并

  1. 5步：初始化、rear做下标、比较赋值（不需要新增项，只需要指向目标项！记得更新下标，非常重要hh）、处理剩余项，free()

0.3.1 树的同构

  1. “最大N，层序遍历结果相同，但树不同”测试不通过：程序逻辑有问题，先判断了是否空，再判断是否值不同。把确认树是同构的代码return 1放在排除树是同构的代码return 0后面，即可解决问题。
int Isomorphic(Tree R1, Tree R2) // R1、R2是两个下标
{
    if ((R1 == Null && R2 != Null) || (R2 == Null && R1 != Null) ) // 一个空一个非空，不一样
        return 0;
    if (T1[R1].Element != T2[R2].Element) // 值不一样
        return 0;
    if (R1 == Null && R2 == Null) 
    // 排除法，前面的树都没返回0，直到叶节点才返回1
        return 1;
    /* 记得加return！ */
    if (T1[R1].Left == Null && T2[R2].Left == Null) // 左子树空，看右子树
        return Isomorphic(T1[R1].Right, T2[R2].Right);
    if ( ((T1[R1].Left!=Null) && (T2[R2].Left!=Null)) && 
        (T1[T1[R1].Left].Element) == (T2[T2[R2].Left].Element)) {
        // 左子树都不空，且左子树是同一棵树
        return Isomorphic(T1[R1].Left, T2[R2].Left);
        return Isomorphic(T1[R1].Right, T2[R2].Right);
    }
    else {
        // 左子树都不空，但两边交换了
        return Isomorphic(T1[R1].Left, T2[R2].Right);
        return Isomorphic(T1[R1].Right, T2[R2].Right);
    }
}

0.3.3 Tree Traversals Again

  • 本题的核心思想是：两种遍历就能确定一棵树。那么如何依靠前序遍历和中序遍历，得到树的后序遍历结果呢？
  1. 根据前序遍历结果，容易确定树的根；树根是最后一个输出的，放后序数组最后一个位置
  2. 根据树根和中序遍历结果，划分树
  3. 递归上面两步，把树划分好，按顺序填入左右节点、根节点即可
  • solve()函数仅仅做了两件事：放好根节点和叶节点，真简洁， hecd真精妙！

0.4.1 判断是否按同一颗二叉搜索树

  1. 流程：读入数据（基准树，节点数+数据数），按顺序处理数据；读入数据
  2. 处理方法：首先构造基准树，然后处理数据。通过在基准树内按顺序查找节点，来判断是否同一颗树（寻找一个节点，必须经过已经查找过的节点，这就是同一颗搜索树；而二叉树保证了数据的位置）

0.4.2 List Leaves

  • 用结构数组建树，判断叶节点并设置flag，用层序遍历输出
// Tree是int 表示下标，树用结构数组T1[MaxTree]实现
void LevelorderTraversal ( Tree BT )
{ 
    Queue Q; 
    Tree T;

    if ( BT == Null ) return; /* 若是空树则直接返回 */
    
    Q = CreateQueue(MaxTree); /* 创建空队列Q */
    AddQ( Q, T1[BT].Element );
    while ( !IsEmpty(Q) ) {
        T = DeleteQ( Q );
        if (T1[T].flag) {
            printf("%d", T); /* 访问取出队列的结点 */
            if ( !IsEmpty(Q) ) // 保证格式
                printf(" ");
        }
        if ( T1[T].Left != Null )
            AddQ( Q, T1[T1[T].Left].Element );
        if ( T1[T].Right != Null )
            AddQ( Q, T1[T1[T].Right].Element );
    }
}

0.4.5 Root of AVL Tree

  • 使用树高来判断需不需要平衡，因此需要注意更新树高
  • 基本上按照示例代码编写了右旋与右左旋
  • 双旋只需要两次单旋就可实现！
  • GetHeight(AVLTree)函数需要注意传入树为空的情况

0.5.7 最小堆的路径

  • 堆最好的表示方式是数组（完全二叉树）
  • 插入堆从底部开始，把大于插入值的节点顺位下去

0.5.8 File Transfer 算法优化

按秩归并

  • 让树不要越长越高，不要成为单链表
  • 如何避免树会越来越高？把矮的树连接到高的树上，根节点下标-n代表n树高
    1. 比高度
    2. 比规模

路径压缩

  • 不是把连接的节点组织成单分支树，而是根-叶，所有节点直接指向父节点！
  • 尾（伪）递归：编译器自动转换为循环

0.7.4 哈利·波特的考试（打瞌睡）

  • 使用Floyd算法找出任意两点的最短路径，再比较每一行最长的路径，找出最小的那个

1.0 基本概念

1.1 什么是数据结构

  • 如何在书架上摆放图书？
    • 这个问题不科学，没有告诉我们书架长什么样。不一样规模的问题，处理起来的难度不一样。
    • 两个问题：新书如何插入、如何查找。
    • 方法
      1. 随便放（插入一步到位，找书很难）
      2. 二分查找，按字母排放（查找很容易，插入需要一本一本往后放）
      3. 书城，按书的类别分，再细分（图书规模变小，查找、插入难度也变小）问题：每类书的规模不同，预留多少空间；类别分的多细？
    • 总结：解决问题方法的效率，跟数据的组织方式有关
  • 循环与递归
    • 数据量达到10w时，递归罢工
    • 总结：解决问题方法的效率，跟空间的利用效率有关
  • 用time.h统计调用函数所用时间
#include<time.h>

clock_t start, stop; // clock()返回类型clock_t
double duration; // 以秒为单位

start = clock();
// MyFunction();
stop = clock();
duration = ((double)(stop-start)) / CLK_TCK;

printf("duration: %lf", duration);
- 总结：解决问题方法的效率，跟算法的巧妙程度有关系
  • 什么是数据结构
    • 数据对象在计算机中的组织方式就是数据结构
      • 逻辑结构
      • 物理结构
    • 数据对象必定与一系列加在其上的操作相关联
    • 完成这些操作所用的方法就是算法
  • ADT：描述数据结构的方法
    • 只描述数据对象集和相关操作集 “是什么” ，并不涉及 “如何做到” 的问题
    • int, float, double 用宏定义 ElementType 代替
    • 不考虑用二维数组还是十字链表

1.2 什么是算法

  • 算法
    • 有限指令集
    • 接受输入或不需要输入
    • 产生输出
    • 一定在有限步骤后终止
    • 每条指令必须
      1. 明确无歧义
      2. 计算机处理范围内（如递归别爆内存）
      3. 伪代码，不依赖特定语言和实现手段
    • 例子
/* 将N个整数List[0]...List[N-1]进行非递减排序 */
void SelectionSort(int List[], int N) 
{
    for (i = 0; i < N; i++) {
        MinPosition = ScanForMin( List, i, N–1 );
        /* 从List[i]到List[N–1]中找最小元,并将其位置赋给MinPosition */
        Swap( List[i], List[MinPosition] );
        /* 将未排序部分的最小元换到有序部分的最后位置 */
    }
}
  • 什么是好的算法
    • 空间复杂度S(n)和时间复杂度T(n)
    • S(n)：递归PrintN(int N)占用跟N大小呈线性增长；而循环始终占用1个函数空间
    • T(n)：多项式例子，直接算的方法执行(1+2+…+n)次乘法，巧妙方法只执行n次乘法
      • Tworst(n)和Tavg(n)T_worst(n)\text{和}T_avg(n)
    • 复杂度运算
      1. 两算法分别有复杂度T1(n)=O(f1(n)), T2(n)=O(f2(n))T_1(n) = O(f_1(n)),\ T_2(n) = O(f_2(n))
        • T1(n)+T2(n)=max(O(f1(n)),  O(f2(n)))T_1(n) + T_2(n) = max(O(f_1(n)),\; O(f_2(n)))
        • T1(n)×T2(n)=O(f1(n))×O(f2(n))T_1(n) \times T_2(n) = O(f_1(n)) \times O(f_2(n))
      2. T(n)是关于n的k阶多项式，那么T(n)=Θ(nk)T(n) = \Theta(n^k)
      3. for循环：循环体复杂度 * 循环次数
      4. if-else分支：if条件判断和两个分支部分复杂度，取最大的那个
  • 例子：判断下面代码的复杂度 O(N3)O(N^3)
/*if-else分支：if条件判断和两个分支部分复杂度，取最大的那个*/
if ( A > B ) { // n^3
    for ( i=0; i<N; i++ ) // n
        for ( j=N*N; j>i; j-- ) // n^2
            A += B; // 1
}
else {  // 4n^2
    for ( i=0; i<N*2; i++ ) // 2n
        for ( j=N*2; j>i; j-- )  // 2n
            A += B; // 1
}

线性表

如何用程序表示多项式？

  • 关键信息：1) 项数n; 2) 系数a以及指数i
  • array: a[i]:项xi的系数aia[i]: \text{项}x^i\text{的系数}a_i, f(x)=4x5−3x2+1f(x) = 4x^5-3x^2+1
    • 表示成：a[6] = {1, 0, -3, 0, 0, 4}
    • 问题：x+3x2000x+3x^{2000}需要2001大小的数组，浪费，循环无效0
  • 把多项式看成 (a, j) 二元组，用结构数组，只表示非0项（两个数组，一个表示系数，一个表示指数）
  • 链表
typedef struct PolyNode *Polynomial;
struct PolyNode {
    int coef;
    int expon;
    Polynomial link;
}

什么是线性表

  • 类型名称：线性表List
  • 数据对象集：线性表是n个元素构成的有序序列
  • 操作集
List MakeEmpty() // 初始化空线性表
ElementType FindKth(int K, List L) // 根据位置K，返回相应元素
int Find(ElementType X, List L)  // 寻找X第一次出现的位置
void Insert(ElementType X, int i, List L) // 在位序i前插入一个新元素X
void Delete(int i, List L) // 删除指定位序i的元素；
int Length(List L) // 返回线性表L的长度n
  • 在矩阵的多重链表表示中，第i行的head和第i列的head实际上是同一个结点 对
  • 下面的统计列表长度函数是否正确？ 错
int Length(List *PtrL) {  
    List *p = PtrL;  
    int j = 0;  
    while (p) {  
        p++; // 错误，应为p = p->next; 
        j++;  
    }  
    return j; 
}

树

  • 分层次组织在管理上具有更高的效率
  • 两种查找
    • 静态
    • 动态：不仅查找，还有插入、删除
  • 哨兵
    • 可以少些一个判断分支：把array[0]=K，设0（哨兵项）为K，则每次到0比为K，退出循环；同时少了条件判断，提高效率
  • 二分查找：必须用数组，顺序存放
  • 题目：在二分查找的程序实现中，如果left和right的更新不是取mid+1和mid-1而是都取mid，程序也是正确的（错误）
  • 树：摆脱了数组这种结构限制，可以动态查找
    • 有一个m棵树的集合（也叫森林）共有k条边，问这m颗树共有多少个结点？
    • m + k个，如图，1棵树4条边
  A    // root
 / \   // side
B   C  // tree
 \   \
  D   E
  • 术语
    • degree：节点子树个数
    • 树的度：节点最大度
    • leaf：无子树节点
    • sibling：兄弟节点
  • 树的表示（链表）：儿子兄弟表示法（二叉树） 统一结构
  • 题目：一棵度为m的树有n个节点。若每个节点直接用m个链指向相应的儿子，则表示这个树所 需要的总空间是n*(m+1）（假定每个链以及表示节点的数据域都是一个单位空间)。当采用 儿子/兄弟（FirstChild/NextSibling）表示法时，所需的总空间是3n。一个数据、两个指针（二子、兄弟）

二叉树

  • 第k层最多2k−12^{k-1}个节点
  • 任何二叉树满足下面关系 n0=n2+1n_0 = n_2 + 1，推导：边的总数S=n0+n1+n2−1=0∗n0+n1∗1+n2∗2S = n_0 + n_1 + n_2 - 1 = 0*n_0 + n_1*1 + n_2*2
   A
  / \
 B   C // N2 = 3
/ \ /
D E F
 / \ \
J   K H // N0 = 4
  • 完全二叉树用数组很方便，可以完全顺序编号：并且可以容易地找出子节点、父节点；可以把树填充成完全二叉树，然后用数组存放（会造成空间浪费）

二叉树遍历

  • 递归方法：同样路径，不同打印顺序
    1. 先序(preOrder)：根节点，先序遍历左子树、右子树
    2. 中序(inOrder)：中序左子树，根节点，中序右子树
    3. 后序(postOrder)：后序左子树，后序右子树，根节点
  • 非递归遍历：用堆栈
    1. 中序：遇到一个结点，就把它压栈，并去遍历它的左子树；当左子树遍历结束后，从栈顶弹出这个结点并访问它；然后按其右指针再去中序遍历该结点的右子树

层序遍历

  • 二叉树：线性化序列
  • 遍历二叉树：二维变一维
  • 难点：不访问父节点就找不到子节点；访问了左节点，右节点怎么办（保存：堆栈、队列）
  • 队列实现
    • 把子节点全部放进队列，依次出队

树的应用

  1. 求树叶节点的个数
  2. 求树的深度
  3. 实现前缀、后缀、中缀（不准）表达式
  4. 必须有中序遍历，再加上其他方式遍历，才可以唯一确定一颗二叉树
  • 题目：已知有颗5个结点的二又树，其前序遍历序列是a???？，中序遍历序列是a？??？，可以断定 A.该树根结点是a，且没有左子树
    前序遍历：根->左->右；中序：左->根->右；由此可判断

二叉搜索树

  • 二分查找：事先有效组织数据
  • 二叉树：比线性结构更好组织；所有的左子节点要比根节点小，右子节点要比根节点大
  • 删除：右子树最小元素替代或左子树最大元素替代（这两个元素一定只有1个节点）

平衡二叉树

  • 左右两边节点、高度差不多
  • 平衡因子Balace Factor: BF(T)=hL−hRBF(T) = h_L - h_R
  • 最少几个节点才能构造一个4层平衡二叉树？7个（保持高度差=1）
    A
   / \
  B   C
 / \  /
 D  E F
/
G

堆

  • 不按顺序处理，按优先级
  • 优先队列(Priority Queue)：特殊的队列，按优先权（关键字）大小取元素
  • 用完全二叉树存储，任何节点都比左右子节点要大
  • 建堆时，最坏情况下需要挪动元素次数是等于树中各结点的高度和。问：对于元素个数为 12的堆，其各结点的高度之和是多少？10，3+2+2+1+1+1=10 要看棵树举例子节点的举例

哈夫曼树

哈弗曼编码

  • 不等长编码

哈夫曼树（最小/优二叉树）

  • 寻找最有效的检索树
  • 生成步骤
    • 每次把权值最小的两棵二叉树合并
  • 哈弗曼树的左子树也是哈弗曼树
  • 用最小堆实现
    • 找到两个最小的
    • 堆顶为两个值合并值
  • 同一组权值，哈弗曼树不一定同构，但是WPL一样

不等长编码

  • 问题：二义性
  • 解决二义性：任何字符的前缀码都不是另一字符编码的前缀；让所有编码都落在二叉树的叶节点上（哈弗曼树实现最优）
  • 题目：
    下列方案中哪个不可能是哈夫曼编码？
    A. 00, 100, 101, 110, 111
    画*处无节点,度为1
   / \
  0   1
 / * / \
0   0  1
   /\  /\
  0 1  0 1

并、查集

  • 思路：
    1. 10台电脑看成10个集合
    2. 互相连接的电脑xy对应的集合合并
    3. 判别xy是否属于同一集合，即可知两台电脑是否连通

图

  • 树是一种特殊的图
  • 表示多对多关系
  • 包含
    • 一组定点
    • 一组边
    • 有向边，只能从一边到另一边，不能回去
  • 强大的数据结构
  • 图的两条边可以代表一种关系
  • 六度空间：任意两个人可以通过不超过六个人认识

实际问题：

  • 怎么走最快？（最短路径）
  • 怎么修路使村村通的花费最少（地铁线路）

术语

  • 无向图、有向图
  • 带权重的图：网络

程序表示

  • 邻接矩阵 G[N][N]，N个顶点从0到N-1编号
    • G[i][j] = 1 若<vi,vj><v_i, v_j>是G中的边；否则为0
    • 稀疏时存了很多0，浪费空间；也浪费时间（要扫描数组）
  • 邻接表 G[N]指针数组，对于矩阵每行一个链表，只存非0元素
    • 一定要够稀疏才合算
    • 无向图很好算度；有向图不好计算
    • 不好检查任意一对顶点是否存在边

图的遍历

  • DFS(Depth First Search)与BFS(Breadth First Search)
    • DFS：原路返回（栈），相当于树的前序遍历
    • BFS：相当于树的层序遍历
  • 为什么需要两种遍历？
    • BFS在目标距离近的时候非常好使；目标距离远的时候就需要DFS节省算力

最短路径问题

  • 从起点到终点的权值之和
  • 单源与多源
    • 从固定点出发，求最短路
    • 从任一点求最短路

排序和查找算法

  • 一万个数起步的排序
  • 基于比较的排序
  • 只讨论内部排序（可以在内存里一次性排完）；外部排序（内存一次装不下）
  • 稳定性： 相等数据，排序前后相对位置不变
  • 没有一种排序是任何情况下最快最好的

简单排序

冒泡排序

  • 最大的泡泡沉底
  • 对链表和数组都没问题
  • 问题：对于7个数进行冒泡排序，最坏情况下需要进行的比较次数为 21次(6+5+4+3+2+1)

插入排序

  • 从最后一位开始往前比较大小，选择好插入位置
  • 好处：不是交换排序

逆序对

  • 每次交换正好消去1个逆序对
  • 最好情况T(N, I) = O(N + I)
  • 定理：N个元素平均有N(N-1)/4个逆序对
  • 定理：任意两两交换算法，平均时间复杂度为N2N^2
  • 想要提高算法效率，每次消去不止1个逆序对，每次交换相隔较远的逆序对

希尔排序(Shell Sort)

  • 每隔n个进行插入排序
  • 减少n直到1为止(n/2)
  • 在8 4 2 1时，可能每次排序都不会起作用，最好是互质的

堆排序

选择排序

  • 最多换n-1次
  • 瓶颈在如何寻找最小元（最小堆）

堆排序（选择排序改进）

  • 算法1：建立最小堆，每次从最小堆里弹出一个元素(N logN)
    • 需要额外空间
  • 算法2：最大堆，每次弹出堆顶并与最小元素交换

归并排序

  • 有序子列的归并
  • 指针：存位置的就是指针，可以是存下标