引入

之前我们讲的都是线性表，它们有可以是顺序存储结构或者链式存储结构的数组、链表、栈、队列。我们之前讨论的线性结构都是一对一的。那什么不是一对一呢？例如妈妈的两个孩子，一个妈妈对应了两个孩子，这种一对多的数据结构，我们称之为树。当然了，以后还会有多对多的概念，今天我们先了解一下树的概念。

树的定义

树（Tree）是 n ($n\geq0$) 个结点的有限集。n=0 时，我们称之为空树。
在任意一棵非空树中：

• 有且仅有一个特定的称之为根（Root）的结点。
• 当 n>1 时，其余结点可分为 m($m\geq0$)个互补相交的有限集
• 有限集 T1、T2、….、Tm，其中每一个集合本身又是一棵树
• 我们称由这些有限集合构成的树，为根的子树（SubTree）。

上面的图中

• 根：A 结点是这棵树的根
• 结点：每一个圈都是一个结点
• 子树：B、C、D、E、F、G、H都是子树

引入

引入

引入

引入

引入

八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

简单思想

• 将大问题化简称小问题
• 8X8二维数组的任意一个位置
• 一行一行来检查，符合要求的就把0改成1
• 要求就是一列不能有1，一行不能有1，斜着不能有1
• 一行一行的递归是一部分、检查行列斜有没有棋子1是一部分
• 递归下去，然后回溯回来，就能将所有的情况列出来了。

引入

传说越南河内某间寺院有三根银棒

• 其中一根银棒上串 64 个金盘
• 金盘从上到下，由小至大。
• 一次只移动一片，不管在那根针上
• 但小片必须在大片上
• 从一根银棒按照同样的要求，全部移动到另外一根银棒上，任务完成

若传说属实，僧侣们需要 $2^{64}-1$步才能完成这个任务
若他们每秒可完成一个盘子的移动，就需要 5845 亿年才能完成。整个宇宙现在也不过 137 亿年。

汉诺塔玩具

(图片来自于维基百科)

引入

递归学习过编程的基本上都应该大体知道，但是递归的效率并不高，我们通常使用迭代循环，但我在探索未知的情况下，递归可能会更好。我们通过斐波那契数列来了解一下递归。

斐波那契数列

因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34…
即开始有一对儿兔子，然后3个月后兔子长大了，这对兔子会生一对儿兔子，之后的每个月这对儿兔子又生一对儿，假设兔子不会死亡，那么 N 个月后有多少对儿兔子。

理解

数列：1、1、2、3、5、8、13、21、34…
找到数列的规律之后，我们发现，3号数是1号+2号，6号数是4号+5号，即该数前两个数的和。

迭代循环解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <stdio.h>
int main(){
    int f1=1,f2=1,f3;
    //将第1、2个月的数先赋值，作为计算基底
    printf("%12d\t%12d\t",f1,f2);
    //由于已经赋值了，所以就先输出
    for(int i=3;i<41;i++){
        f3=f1+f2;
        printf("%12d\t",f3);
        //利用循环输出第三个月的数，也就是前两个月的和
        if(i%4==0){
            printf("\n");
        }
        //判断换行
        f1=f2;
        f2=f3;
        //将用于相加的两个数向前推移
    }
}

引入

前面我们讲了，如何初始化一个循环队列，今天我们就来讲讲如何在队列中插入和删除数据。

入队列操作

如何判断队列已经满了

利用取模这个思路判断满栈就是

• 就是让尾指针从头到尾不断的移动
• 利用取模，让尾指针不断的在0~4之间移动
• 如果尾指针指向了头部，也就是说
• 可以插入的位置等于队列的第一个结点的位置了
• 那就证明满栈了

1
2
3
4
5
6
7

void InsertQueue(struct Queue *q , int e){
    if((q->rear+1)% MAXSIZE==q->front){
        return;
    }
    q->base[q->rear]=e;
    q->rear = (q->rear+1) % MAXSIZE;
}

引入

我们之前说，队列我们一般使用的是链式存储结构，而不是顺序存储结构。我们今天就看看如何构造队列的顺序存储结构，然后看看顺序存储结构给队列带来了哪些问题。

想一想

我们假设，有一个队列

• 有 n 个元素
• 那么顺序存储结构就需要大于 n 的存储单元
• 数组下标 0 是头部，n 个元素存储在数组的前 n 个存储单元中。

（图片来自于鱼 C 工作室）

入队

• 0 号下标是队头
• 然后数据不断进来，不断移动队尾指针。
• 只需要将队尾指针+1即可
• 时间复杂度为 O ( 1 )