回顾：
1.数据结构
栈
先进后出
操作栈顶
队列
先进先出FIFO
入队操作队尾
出队操作队首
单链表
struct node {
数据;
struct node *next;
};
双链表
struct node {
数据;
struct node *next, *prev;
};
描述链表的结构体
struct list {
struct node head/*head;
struct node tail/*tail;
};
二叉树
有序二叉树：左小于右
先序 / 中序 / 后序
struct node {
数据：
struct node *left, *right;
};
利用递归函数实现操作
2. gdb代码调试工具(单步跟踪调试程序)
使用步骤：
-
编译程序时，一定要加-g选项（调试选项）
gcc -g -o helloworld helloworld.c //一定要添加-g选项 -
调试程序需要启动gdb命令，立马出现gdb的命令提示符：(gdb)
gdb命令格式：gdb 可执行程序文件名 例如： gdb helloworld -
掌握几个gdb命令
(gdb)l // l = list;罗列源代码 (gdb)b // b = breakpoint=断点 // b 15就是在15行设置一个断点 (gdb)r //r = run;启动运行程序，CPU就从main函数开始依次向下运行，知道遇到断点 (gdb)s // s = step 下一步; 让CPU继续向下执行一条语句，如果碰到函数，会让CPU进入函 数继续跟踪 //如果输入n(next),也就是下一步，但是CPU不会进入函数内存跟踪，直接调用函数 完毕 (gdb)p 变量名 //查看变量的值 (gdb)p /x 变量名 //查看变量的值，按照16进制 格式输出 (gdb)q //quit ，退出gdb命令
3. 常用算法
4个排序算法和2个查找算法：
3.1 冒泡排序算法
例如：
初始状态： 9 7 5 3 1
第一趟： 7 5 3 1 9 9>7交换位置,9>5交换,9>3交换,9>1交换
第二趟： 5 3 1 7 9 7>5交换位置,7>3交换位置,7>1交换位置,7<9不交换
第三趟： 3 1 5 7 9 5>3交换位置,5>1交换位置,5<7不交换,5<9不交换
第四趟： 1 3 5 7 9 3>1交换,3<5不交换,3<7不交换,3<9不交换
目前来看：N个数需要N-1躺排序，每趟需要N-1次比较
第一步优化：N个数需要N-1趟排序，每趟需要N-1-i次比较 减1是因为下标是从0开始的
第二步优化：
初始状态： 0 7 5 3 1
第一趟： 0 5 3 1 7
第二趟： 0 3 1 5 7
第三趟： 0 1 3 5 7
如果发现某一趟的排序中，没有发火时呢个数据的囧啊换，那么就认为排序完成
参考代码：文件夹bubble_sort
https://gitee.com/cui-qinghe/c-study-notes.git 代码
3.2 插入排序算法
例如：
初始状态：10 30 20 15 5 //无序的
原始想法：//有序的
5 10 15 20 30
原始想法思路：从无序的数列中取出数据单独存放成一个有序的数列
弊端：需要额外开辟内存空间来存放有序数据列
解决办法：原地完成插入，不需要额外开辟大量内存空间
原地实现插入流程：
初始状态：10 30 20 15 5 //无序的
定义一个变量保存要被插入的数据，思路：
10 30 20 15 5 直接从第二个数据插
优点：节省了内存空间，只需一个变量保存被插入的数据即可原地完成排序
3.3 选择排序算法
例如：
初始状态：9 5 7 3 1 //无序
原始想法：1 3 5 7 9 //有序
思路：从一个数列中找最小数放到第一个位置，然后从剩余的无序数列中再找一个最小数
放在无序的第一个位置，依次排下去
弊端：需要额外开辟内存空间内存来存放有序数据列
解决方法：
初始状态：9 5 7 3 1
原地解决：1 5 7 3 9
1 3 7 5 9
1 3 5 7 9
1 3 5 7 9
参考代码：select_sort文件夹
https://gitee.com/cui-qinghe/c-study-notes.git 代码
3.4 快速排序
例如：
0 10 80 30 50 40 70 20 9 100
思路：不管在站在哪个数上去看，它左边的数小于它，它右边的树大于它（跟有序二叉树一样）
原始实现：站在50来看，进行一次分组得到：把比50小的放左边，大的放右边：
0 10 30 40 50 60 70 90 80 100 // 更接近有序
然后再对50左边的数进行再次分组，把比30小的放左边，大的放右边，
再然后队50右边的数进行再次分组，把比90小的放左边，小的放右边
0 20 10 30 40 50 60 80 70 90 100 //又接近有序
以此类推：对30左边右边进行各种分组，对90左边和右边各种分组
直到分到没有数或者只有一个数
弊端：需要开辟内存空间来存放不断趋近有序数列
0 10 80 30 60 50 40 70 20 90 100
50为基准：0 10 30 20 40 50 60 70 90 80 100
30，90为基准：0 20 10 30 40 50 60 80 70 90 100
20,80为基准：0 10 20 30 40 50 60 70 80 90 100
10,70为基准：0 10 20 30 40 50 60 70 80 90 100
问：怎样能够实现原地分组呢?
答：定义三个游标来实现原地分组(p = pivot=基准)
初始：
0 10 80 30 60 50 40 70 20 90 100
i
p
j
50为基准进行依次(将来定义变量来缓存)：
0 10 20 30 40 50 80 70 60 90 100
i
p
j
参考代码：quick_sort
https://gitee.com/cui-qinghe/c-study-notes.git 代码
3.5 查找算法:线性查找，二分查找（折半查找）
1.线性查找：
在数列中挨个匹配要找的数据
对数据的有序性没有要求
参靠代码：find
2.二分查找（折半查找）
切记：二分查找的前提是的数据必须有序，否则用不了
原理：目标找60
10 20 30 40 50 60 70
对数列对半，然后拿60跟40比较，如果相等，说明找到了
如果不相等，发现60大于40，说明60一定在40的右边
然后对40右边50 60 70再对半分，然后拿60跟中间的60进行比较，发现相等，说明找到了
如果不相等，并且小于，在左边继续对半分
如果不相等，并且大于，在右边继续对半分
参考代码：find
https://gitee.com/cui-qinghe/c-study-notes.git 代码