数据结构(六)

冷不防 2022-08-20 10:10 154阅读 0赞

接着递归：

递归不仅可以自己调用别的函数，还可以调用自己：

![Center][]

求某个数的阶乘，先用循环实现：

![Center 1][]

除了循环，递归也可以实现：

与循环不同，递归的思路是已经知道1的阶乘是1，每次调用f函数，只需知道比它小1的数阶乘，n只需知道n-1的阶乘，n-1只需知道n-2的阶乘...直到1为止。

![Center 2][]

同理，n个数之和：

![Center 3][]

函数的调用：当在一个函数运行期间调用另一个函数时，在运行被调函数之前，系统需要完成3件事：

1.将所有的实际参数，返回地址等信息传递给被调函数保存。

2.为被调函数的局部变量（也包括形参）分配存储空间。

3.将控制转移到被调函数额入口。

从被调函数返回主调函数之前，系统也要完成3件事

1.保存被调函数的返回结果

2.释放被调函数的存储空间（静态内存而已）

3.依照被调函数保存的返回地址将控制转移到调用函数

不管是函数调用本身还是其他函数，实现原理都是压栈出栈。在系统内部是一样的。

实现递归要满足3个条件：

1.递归必须得有一个明确的中止条件。

2.该函数处理的数据规模必须在递减。

3.这个转化必须是可解的，不能是死递归。

循环和递归的优缺点：

递归：易于理解

速度慢

存储空间大

循环：不易理解

速度快

存储空间小

递归专题：汉诺塔算法：

#include<stdio.h>
    
    void hannouta(int n,char A,char B,char C)
    {
    	if(1==n)
    	{
    		printf("将编号为%d的盘子从%c柱子移到%c柱子\n",n,A,C);
    	}
    	else
    	{
    		hannouta(n-1,A,C,B);
    		printf("将编号为%d的盘子从%c柱子移到%c柱子\n",n,A,C);
    		hannouta(n-1,B,A,C);
    	}
    }
    
    int main(void)
    {
    	char ch1='A';
    	char ch2='B';
    	char ch3='C';
    	int n;
    	printf("请输入你要移动盘子的个数:");
    	scanf("%d",&n);
    	hannouta(n,ch1,ch2,ch3);
    	return 0;
    }

![Center 4][]

递归的应用：树和森林是以递归的形式实现的

树和图的很多算法也是基于递归实现的

很多数学公式是以递归方式定义的，比如：菲波拉契序列

总结：内存的分配是一维线性的，而现实生活的问题是复杂多样的，把复杂的问题转化为简单的存储就是数据结构

逻辑结构：人的思维

线性：数组

链表

栈和队列是特殊的线性结构

非线性：树

图

物理结构：计算机的思维

下面开始非线性结构：

树：树定义

专业定义：1.有且只有一个称为根的结点

2.有若干个互不相交的子树，这些树本身也是一棵树

通俗的定义：

1.树由结点和边组成

2.每个结点只有一个父结点，但可以有多个子结点

3.有一个结点例外，该结点没有父结点，此结点称为跟结点

树分类

树操作

树应用

[Center]: /images/20220731/53f6b8eb9ca84a9a9d04a7f73370b123.png
[Center 1]: /images/20220731/f7487a1f47704554aacc6876f2cab01e.png
[Center 2]: /images/20220731/0d6e6393d0db438f99c96393d85aa8d4.png
[Center 3]: /images/20220731/4549e68113034cb98a0fada0fd4a4776.png
[Center 4]: /images/20220731/f6c13dd039014e01822aaf599b5374a0.png