写在前面

时至七月末，开始着手专业课的复习。因为是科班出身，数据结构已经在一年级下就学过了，所以对书上的知识点都已经很熟悉。但时过境迁，岁月流逝，相隔两年的时间也让我对书中的细节有所遗忘，趁着暑假的功夫，好好捡一捡过往的记忆。

这篇文章主要记录的是数据结构的重点算法，针对西南交大历年考题量身定制了《算法三讲》。

分为三个部分。

其一是840考试的重点算法，主要针对最后一题的算法设计，内容极其重要，所以将他放在第一讲。
其二是王道数据结构的所有算法大题，难度较高，综合性较强，难度在真题之上。这一部分的内容要反复修炼，熟唸于心。
其三是840历年真题的所有算法的设计思路，进行拓展思考。

第一讲 840重点算法

写在前面

本讲内容的顺序按照考试重点考察频率的优先级进行安排，也就是说，最常考的内容会放到前面，不常考的放在后面。

2022.8.9 于成都·抚琴东南路

树与二叉树

二叉树顺序存储结构和二叉链表存储结构的相互转化的算法

1.将二叉树的链表存储形式转化为树的顺序存储形式

树的顺序存储结构，是利用完全二叉树的性质来定义的，不管一颗二叉树什么结构，他都可以补全成完全二叉树。

其实我们把二叉树的顺序表从1开始（有些也从0开始，此时他的左右孩子就变成了2i+1与2i+2）。此时他的左右孩子为2i与2i+1.

可以通过树的遍历算法实现，用树的结点来做索引，每次如果遇到空的情况，直接将该数组值变为‘0’.

//T为根节点 K数组用来存放数据 i表示该数组再数组中的下标 在这之前先将K数组全部初始化为‘0’

void TranstoArray(BiTree T,char K[],int i){
    if(T){
        K[i] = T->data;
        TranstoArray(T->lchild,K,2i);
        TranstoArray(T->rchild,K,2i+1);
    }else{
        K[i] = '0';//若T为空，说明上个结点的左或右孩子中必有空的情况
    }
}

2.将树的顺序存储结构转化为树的二叉链式存储结构

此时用数组K来索引，每次通过数组K的值来创建二叉树结点，所以要用“指针的指针”或者“指针的引用”，来创建一颗新的二叉树结构。

//T表示一个在主函数中定义的指针的地址（指针的指针）
//过程类似于二叉排序树，AVL的创建

void TranstoTable(BiTree *T,char K[],int i){
    if(K[i]!='0'){
      	BiTree temp = new BiNode;//用来申请新的空间
        temp->data = K[i];
        temp->lchild = temp->rchild = NULL;
        (*T) = temp;
        TranstoTable(&(*T)->lchild,K,2i);//每次通过改变左右指针的空间来继续创建
        TranstoTable(&(*T)->rchild,K,2i+1);
    }else{
        (*T) = NULL;
    }
}

上部分黑色重点标注的部分可能不太好理解，我自己在写代码的时候，也遇到了困惑。比如BiTree是什么？它传递的参数又是什么？什么是指针的指针？以上问题，我们在下面回答。

在写完代码之后，发觉自己对二叉树的链式定义有些遗忘了，在这里写一下二叉树的链式定义。

typedef struct BiTNode{
    ElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左、右孩子指针
}BiTNode,*BiTree；//注意这里的BiTree是指向BiTNode类型结点的指针

可以看到，BiTree是指向BiTNode这种结点的指针，那么在第一个算法中，我们用BiTree定义T时，实际上我们定义的是一个指向根节点的指针。

而在第二个算法中，我们定义了一个指向根节点指针的指针。为什么要这么做呢？这是我在复习时的一个疑惑。下面给出我的解释。如果在第二个算法中，直接使用BiTree定义根节点的指针，那么在 (*T) = temp;这部分代码，就会变成T = temp;这种形式，而这种形式实际上是一种地址的赋值，相当于temp与T指向了同一个地址，而这种只能改变指针所指的地址的内容，不能改变指针本身的指向。在函数调用时用指针或者引用做参数，表示把变量的地址传递给子函数，但是子函数只能修改指针所指变量的值，并不能修改指针的指向。如果想要修改指针的指向，就要用指针的指针，或者指针的引用。