嵌入式入门Day24

数据结构Day5

树形结构
- 相关概念
- 二叉树
- - 相关概念
  - 二叉树的状态
  - 二叉树性质
  - 二叉树的存储
  - 二叉树根据已有序列推出树的结构
  - - 练习
算法
- 相关概念
- 算法特性
- 算法的设计要求
- 时间复杂度
- 排序算法
- - 冒泡排序（改良版）
  - 选择排序（O(n^2)）
  - 直接插入排序（O（n^2））
  - 快速排序

在这里插入图片描述

树形结构

二叉树

二叉树的状态

一共五种：空二叉树、只有根节点、只有根节点和左孩子，只有根节点和右孩子，全部都有
二叉树状态

二叉树性质

在二叉树的第 i 层上最多有 2^(i-1)个节点
在二叉树的前n层最多有 2^n - 1个节点
在二叉树中，叶子节点的个数，总比度为2的节点个数多1
在二叉树上，如果第i个节点存在左孩子，那么其左孩子一定是第 2i个节点，如果存在右孩子，那么一定是第2i+1个节点

二叉树的存储

顺序存储
顺序存储时，需要给空节点留出空间，会浪费大量的存储空间，所以一般用于存储完全二叉树，不适合存储普通的二叉树
链式存储
使用两个指针分别指向左右孩子

存储结构

typedef char datatype
typedef struct Tree
{datatype data; 		//数据域struct Tree *L; 	//左孩子指针struct Tree *R; 	//右孩子指针
}Tree , TreePtr;

二叉树创建

TreePtr tree_create()
{datatype ch; 		//存储数据scanf("%c", &ch); 	//输入数据getchar(); 			//吸收垃圾字符if(ch == '#') 		//设定#表示空子树{return NULL;}//申请节点封装数据TreePtr B = (TreePtr)malloc(sizeof(Tree));//创建左子树B->L = tree_create();//创建右子树B->R = tree_create();return B; 			//返回树指针
}

二叉树遍历
- 先序遍历：先访问根结点，然后访问左孩子节点最后访问右孩子节点
- 中序遍历：先访问左孩子节点，访问根结点，最后访问右孩子节点
- 后序遍历：先访问左孩子，再访问右孩子，最后访问根结点

//先序遍历
void pri_order(TreePtr B)
{//判断树是否合法if(NULL == B){return;}//输出数据域printf("%c\t", B->data);//递归调用输出左右子树pri_order(B->L);pri_order(B->R);
}
//中序遍历
void mid_order(TreePtr B)
{//判断树是否合法if(NULL == B){return;}//递归调用输出左子树mid_order(B->L);//输出数据域printf("%c\t", B->data);//递归调用输出右子树mid_order(B->R);
}
//后序遍历
void post_order(TreePtr B)
{//判断树是否合法if(NULL == B){return;}//递归调用输出左右子树post_order(B->L);post_order(B->R);//输出数据域printf("%c\t", B->data);
}

二叉树根据已有序列推出树的结构

必须要有中序遍历，再加任意一个遍历就可以推出输的结构
口诀：先后序定顺序，中序遍历分左右

练习

在这里插入图片描述

算法

算法特性

确定性：算法的每一条语句都有确定的含义，不能模棱两可
有穷性：程序执行一定时间后会自动结束的性质
输入：至少有0个或多个输入，这里的输入，不限于输入语句
输出：至少一个或多个输出，这里的输出，不限于输出语句
可行性：经济可行性、社会可行性

算法的设计要求

正确性：对所有正确的输入数据都能得到对应正确的结果
健壮性：对不合法的输入数据，能够给出合理的输出，例如 switch中的default模块
可读性：要求核心代码有注释、命名要规范、代码有缩进等等
高效率：要求算法的时间复杂度要低
低存储：要求空间复杂度要低

时间复杂度

时间复杂度是一个算法的时间量度，正常情况下，没有办法使用时间来衡量一个算法的。
由于代码行数和一个程序执行的时间成正比，所以，我们就粗略得使用基本代码行与时间构建起一个对应关系式，该关系式就是时间复杂度。
在这里插入图片描述

常见的时间复杂度

在这里插入图片描述

排序算法

冒泡排序（改良版）

之前的冒泡排序在排序的过程中就可能已经排序完成了，剩下的时候还在进行无意义的遍历，此时我们添加一个标志flag来检测每次遍历时，是否发生了交换变量这个过程，如果有一次变量完全没有进行交换变量，说明这个数组已经完成了排序，后面的过程就无需进行了。

//冒泡排序
void buble_sort(int *arr, int len)
{for(int i = 1; i < len; i++){int flag = 0;  		//标记是否进行变量交换for(int j = 0; j < len-i; j++){if(arr[j] > arr[j+1]){flag = 1; 	//标志位置1//交换变量int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}//每一趟比较结束后，判断是否进行过变量交换if(0 == flag){break;	 		//提前结束冒泡排序}}printf("排序成功\n");
}

选择排序（O(n^2)）

就是不断从待排序序列中选择最大值（小值），放入到已排序序列中

void select_sort(int *arr, int n)
{for(int i = 0; i < n; i++){int mini = i; 	//将待排序列的第1个元素当做最小值//遍历待排序列for(int j = i; j < n; j++){if(arr[mini] > arr[j]){mini = j; 		//更新下标}}//检查最值是否发生变化if(i != mini){//交换变量int temp = arr[i];arr[i] = arr[mini];arr[mini] = temp;}}printf("排序成功\n");
}

直接插入排序（O（n^2））

不断的取出待排序列的第一个元素，然后在已排序列中寻找合适的位置插入

void insert_sort(int *arr, int len)
{int i,j;		//循环变量for(i = 1; i < len; i++){//备份待处理数据temp = arr[i];//遍历已排序列for(j = i-1; j > 0 && temp <= arr[j]; j--){arr[j+1] = arr[j]; 		//当前元素后移}//将备份数据填入j+1的位置arr[j+1];}printf("排序成功\n");
}

快速排序

设定一个基准，将大于和小于的基准分别放在这个数据的两边，然后在对已经分区的地方重复这个操作，当分区只有一个数据时就排列完成。

void quick_sort(int *arr, int low, int high);
int  quick_part(int *arr, int low, int high);void quick_sort(int *arr, int low, int high)
{//递归出口if(low >= high || low < 0 || high < 0){return;}//进行一次快排，并存储中点的值int mid = quick_part(arr,low,high);//对剩下的分区进行快排quick_sort(arr, low, mid-1);quick_sort(arr, mid+1, high);
}//单次快排
void quick_part(int *arr, int low, int high)
{//设定基准int x = arr[low];//循环条件，低位下标必须小于高位下标while(low < high){//每次移动完都检查下标，当前标记的数值若大于基准则检查下一个while(arr[high] > x && low < high){high--;}//小于则进行交换arr[low] = arr[high];//每次移动完都检查下标，当前标记值若小于基准值则检查下一个while(arr[low] < x && low < high){low++;}//若大于则进行交换arr[high] = arr[low];}//将基准值填入中间位置arr[low] = x;//返回基准的位置，以便后递归使用return low;
}