笔记
1.二叉树的补充
1.1二叉树的创建
shu.h
#ifndef SHU_H
#define SHU_H
#include <myhead.h>
typedef char datatype;
//定义节点类型
typedef struct Node
{
datatype data;//数据域
struct Node*L;//左孩子指针
struct Node*R;//右孩子指针
}bitree,*bitreeptr;
//创建二叉树
bitreeptr tree_create();
//先序遍历
void prio_order(bitreeptr B);
//中序遍历
void in_order(bitreeptr B);
//后序遍历
void post_order(bitreeptr B);
#endif shu.c
#include "shu.h"
//创建二叉树
bitreeptr tree_create()
{
datatype data=0;
scanf(" %c",&data);
if(data=='#')
{
return NULL;
}
bitreeptr p=(bitreeptr)malloc(sizeof(bitree));
if(NULL==p)
{
return NULL;
}
p->data=data;
p->L=tree_create();//递归创建左子树
p->R=tree_create();//递归创建右子树
return p;
}
//先序遍历
void prio_order(bitreeptr B)
{
//判断逻辑
if(NULL==B)
{
return ;
}
//输出数据域
printf("%c\t",B->data);
//先序遍历左子树
prio_order(B->L);
//先序遍历右子树
prio_order(B->R);
}
//中序遍历
void in_order(bitreeptr B)
{
//判断逻辑
if(NULL==B)
{
return ;
}
//中序遍历左子树
in_order(B->L);
//输出数据域
printf("%c\t",B->data);
//中序遍历右子树
in_order(B->R);
}
//后序遍历
void post_order(bitreeptr B)
{
//判断逻辑
if(NULL==B)
{
return ;
}
//后序遍历左子树
post_order(B->L);
//后序遍历右子树
post_order(B->R);
//输出数据域
printf("%c\t",B->data);
}main.c
#include "shu.h"
int main(int argc, char const *argv[])
{
bitreeptr B=tree_create();
if(NULL==B)
{
printf("创建失败\n");
return -1;
}
printf("创建成功\n");
printf("先序遍历后的结果为:\n");
prio_order(B);
putchar(10);
printf("中序遍历后的结果为:\n");
in_order(B);
putchar(10);
printf("后序遍历后的结果为:\n");
post_order(B);
putchar(10);
return 0;
}
2.算法
一、算法的相关概念
程序 = 数据结构 + 算法
算法是程序设计的灵魂，结构是程序设计的肉体
算法：计算机解决问题的方法或步骤
1.1 算法的特性
1> 确定性：算法中每一条语句都有确定的含义，不能模棱两可
2> 有穷性：程序执行一段时间后会自动结束
3> 输入：至少有零个或多个输入
4> 输出：至少一个或多个输出
5> 可行性：经济可行性、社会可行性、能够运行
1.2 算法的设计要求
1> 正确性：给定合理的输入数据，能够得到正确的结果
2> 健壮性：对于给定的不合理的输入数据，能够给出相应的处理措施
3> 可读性：程序核心代码写注释、程序代码有缩进、程序代码命名规范
4> 高效率：要求时间复杂度要尽可能低
5> 低存储：要求空间复杂度尽可能低
1.3 时间复杂度
1> 算法时间复杂度计算公式：T(n) = O(f(n));
T(n):时间复杂度
n:表示问题的规模
f(n) :是问题规模与执行次数之间的函数
O(f(n)):使用O阶记法，记录算法时间复杂度
2> 时间复杂度推导
3> 常见的时间复杂度
二、排序算法
根据数据元素的关键字，安照升序或降序的方式将数据元素重新排列的过程称为排序
2.1 排序的分类
1> 交换类排序：冒泡排序、快速排序
2> 选择类排序：简单选择排序、堆排序
3> 插入类排序：直接插入排序、折半插入排序
4> 归并排序：二路归并、多路归并
2.2 冒泡排序（O(N^2)）
1> 在排序过程中，越大（小）的数据，经由交换后，会慢慢的“浮”到顶端，如同气泡一样
2> 冒泡排序原理
1.比较相邻元素，如果第一个比第二个大（小）则交换
2. 经过一趟排序后会使最大（最小）的元素落到最后 重复上面的步骤，直到没有任何一对数字需要比较为止
3. 当某一趟的排序过程中，出现没有数据交换的过程，则结束整个排序
2.3 选择排序
1> 概念：每次从待排序序列中，找到最大（小）值，将其与待排序序列的第一个进行交换
2> 原理
1、从待排序序列中选择最值
2、如果最值不是待排序序列的第一个，则进行交换
3、从剩余待排序序列中，继续重复前两次的操作，直到，待排序序列为空
2.4 直接插入排序
1> 每次从待排序序列中，选择第一个，将其插入到已排序序列中
2> 原理
1、选取待排序序列中的第一个元素
2、跟前面的元素依次比较，如果前面的比当前元素大（小），则将前面的元素后移一位
3、直到出现前面的不比当前的大（小）或者已经到最前面了，将选取的元素，放入空位置上
4、对于待排序序列中的所有元素，重复上述操作
2.5排序的时间复杂度
2.6所有代码
#include <myhead.h>
//定义冒泡排序
void bubble_sort(int*arr,int n)
{
for (int i = 1; i <n; i++)//躺数
{
int flag=0;//判断是否在排列中改变
for (int j = 0; j < n-i; j++)
{
if(arr[j]>arr[j+1])
{
flag=1;//设置标志
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
//说明t上一趟的排序中，没有进行数据交换
if(flag==0)
{
break;
}
}
printf("排序成功\n");
}
//定义选择排序
void select_sort(int *arr,int n)
{
int mini=0;
for (int i = 0; i < n; i++)
{
mini=i;
for (int j=i+1;j<n;j++)
{
if (arr[mini]>arr[j])
{
mini=j;//更新最小值下标
}
}
//判断最小值f是否是第一个元素
if (mini!=i)
{
//将最小值与待排序列的第一个交换
int temp=arr[mini];
arr[mini]=arr[i];
arr[i]=temp;
}
}
printf("排序成功\n");
}
//定义直接插入排序
void insert_sort(int *arr,int n)
{
int j=0;
int i=0;
for (i=1;i<n;i++)//不断从待排序序列中选元素
{
int temp=arr[i];//将待排序的第一个备份
for (j=i-1;temp<=arr[j]&&j>=0;j--)
{
//将元素后移
arr[j+1]=arr[j];
}
arr[j+1]=temp;//将元素放入对应位置
}
printf("排序成功\n");
}
//定义一趟快速排序
//返回值是基准最终下标
//arr 数组起始地址
//low 要排序容器最小下标
//high 要排序容器最大下标
int part_sort(int *arr,int low,int high)
{
//选择基准
int X=arr[low];//把第一个元素当为基准
while (high>low)//让循环进行的条件
{
//判断high所在的元素是否比基准大
while (arr[high]>=X&&high>low)//为了基准不错位
{
high--;
}
arr[low]=arr[high];//将小的值向前放
//判断low所在的元素是否比基准小
while (arr[low]<=X&&high>low)//为了基准不错位
{
low++;
}
arr[high]=arr[low];//将大的值向后放
}
//将基准的位置就选出来了，此时high=low
arr[low]=X;//将基准放回指定位置
return X;//返回基准下标
}
//定义快速排序函数
void quick_sort(int *arr,int low,int high)
{
if (low>=high)
{
return;//只有一个元素，无需排序，递归出口
}
//不止一个元素时
int mid=part_sort(arr,low,high);//进行一趟排序//因为值传递 所以low和high的值不会改变
//对左半部分快排
quick_sort(arr,low,mid-1);
//对右半部分快排
quick_sort(arr,mid+1,high);
}
//输出
void output(int *arr,int n)
{
printf("目前元素分别是:");
for (int i = 0; i < n; i++)
{
printf("%d\t",arr[i]);
}
printf("\n");
}
/******************主函数*********************/
int main(int argc, char const *argv[])
{
int arr[]={3,8,2,4,5,9,6,1,7};
int len=sizeof(arr)/sizeof(arr[0]);
output(arr,len);
//冒泡排序bubble_sort(arr,len);
//选择排序select_sort(arr,len);
//直接插入排序insert_sort(arr,len);
//快速排序
quick_sort(arr,0,len-1);
output(arr,len);
return 0;
}