今日内容:
一. 二叉树
二级指针 – 很多问题
一个一个带入 – 假设二叉树为空 – 数据插入到二叉树中
删除一个节点 –
1.找节点
2.找新爹
如果要删除的结点的左子树存在 – 将左子树插入到右子树上
3.提一级
将 要删除的结点的父节点 指向 要删除的结点的右子树
int a = 100;
int* p = &a;
int** pp = &p;
**pp
完成
二. 基本排序和查找算法
4个排序算法 + 2个查找算法
1.冒泡排序算法
举例:
初始状态: 9 7 5 3 1
第一趟 : 7 5 3 1 9 (4次)
第二趟 : 5 3 1 7 9 (4次)
第三趟 : 3 1 5 7 9 (4次)
第四趟 : 1 3 5 7 9 (4次)
目前来看 : n个数据需要比较n-1趟, 每趟需要比较n-1次
优化
初始状态: 9 7 5 3 1
第一趟 : 7 5 3 1 9 (4次)
第二趟 : 5 3 1 7 9 (3次)
第三趟 : 3 1 5 7 9 (2次)
第四趟 : 1 3 5 7 9 (1次)
目前来看 : n个数据需要比较n-1趟, 每趟需要比较n-i次
初始状态: 0 1 7 5 3
第一趟 : 0 1 5 3 7 (4次)
第二趟 : 0 1 3 5 7 (3次)
第三趟 : 0 1 3 5 7 (2次)
------------------------------第四趟可以省略
第四趟 : 0 1 3 5 7 (1次)
目前来看 : 如果发现某趟排序[没有发生数据交换]说明排序完成了2.插入排序
定义一个变量暂存备份被插入的数据, 然后拿着被插入的额数据 在前面有序的数列中从后向前扫描, 找到对应的位置插入即可
初始状态:
10 30 20 15 60 //无序数列
10 30 20 15 60
-- -- -- -- --
0 1 2 3 4 数组下标
1.下标为0的数据先不要移动, 让其在原先的位置上
2.要插入的数据是30
int inserted = 30;
30从后向前比较, 和10比较, 10<30, 10(0) 30(1)
10 30
-- -- -- -- --
0 1 2 3 4 数组下标
3.要插入的数据是20
int inserted = 20;
20从后向前比较, 和30比较, 20<30, 20(1) 30(2)
和10比较, 20>10, 10(0) 20(1) 30(2)
10 20 30
-- -- -- -- --
0 1 2 3 4 数组下标
4.要插入的数据是15
int inserted = 15;
15从后向前比较, 和30比较, 15<30, 15(2) 30(3)
和20比较, 15<20, 15(1) 20(2) 30(3)
和10比较, 15>10, 10(0) 15(1) 20(2) 30(3)
10 15 20 30
-- -- -- -- --
0 1 2 3 4 数组下标
5.要插入的数据是60
int inserted = 60;
60从后向前比较, 和30比较, 60>30, 30(3) 60(4)
10 15 20 30 60
-- -- -- -- --
0 1 2 3 4 数组下标
被插入的数据 - 从第二个数据开始插入 mkdir sort
vim sort.h
vim sort.c
vim main.c
