复习总结最终版：数据结构
一、数据结构概念
（一）衡量代码的质量和效率
1.时间复杂度：数据量的增长与程序运行时间的增长所呈现的比例函数
①O(1):程序时间维持恒定
②O(logn)：程序刚开始运行时间可能增长较快，但经过一定数据量后，程序运行时间趋于恒定
③O（n）：程序运行时间随数据量增长呈现固定的比例关系
④O(nlogn)
⑤O(n^2)...
2.空间复杂度：数据量的增长与程序占据空间的增长所呈现的比例函数
（二）顺序表（数组）和链表区别：
1.顺序表（数组）
存储空间连续；*访问元素方便；无法利用小空间；元素个数有限制；插入和删除效率低
2.链表
存储空间不需要连续；访问元素不方便；可以利用小空间；元素个数无限制；插入和删除效率高
二、单向链表
（一）定义节点类型：
typedef int datatype;
typedef struct node{
datatype data; //存放数据空间
struct node *pnext; //存放下一个节点地址
}linknode;
（二）空白头节点创建（必须将节点地址返回）：不存放数据，为保证链表操作的便利性。pnext赋值为NULL，表示该节点为最后一个节点
linknode *create_empty_linklist(void)
{
linknode *ptmpnode = NULL;
ptmpnode = malloc(sizeof(linknode));
if(NULL == ptmpnode)
{
perror("malloc fail");
return NULL;
}
ptmp->pnext = NULL;
return ptmpnode;
}
（三）头插法：pnext存放plinkhead的地址
（四）遍历：循环条件：ptmpnode ！= NULL
（五）尾插法
（六）链表销毁：用快慢指针，free（pslow）。传参为二级指针，销毁完链表后用来修改linknode *plinkhead这个一级指针的值为NULL，避免成为野指针
（七）链表的删除：数据对比相等时，前一个链表pnext指向本节点的pnext，释放本节点，本节点指针指向上一个节点pnext。else两个节点同步向前。
（八）链表查找，链表修改
（九）查找中间节点：while(pfst != NULL && pfast->pnext != NULL) //判断本身和下一个节点
{
pfast = pfast->pnext->pnext; //除头节点只有一个节点，则它指向空了已经
pslow = pslow->pnext;
}
return pslow;
（十）查找倒数第k个节点：先让快指针走while（k--）
{
pfast = pfast->pnext;
}
（十一）不知道头节点删除指定节点：使本节点值和后节点值一样，删除后节点
（十二）链表倒置：从头节点断开，使再依次使用头插法插入头节点后。后面让头节的pnext指向插入节点
while(ptmpnode != NULL)
{
pcurnode = ptmpnode;
ptmpnode = ptmpnode->pnext; //
pcurnode->pnext = plinkhead->pnext; //这个操作会改变ptmpnode的pnext，如果在最后ptmpnode = ptmpnode->pnext; ptmpnode = NULL
plinkhead->pnext = pcurnode;
}
（十三）链表排序
1.冒泡排序
while (1)
{
ptmpnode1 = phead->pnext;
ptmpnode2 = phead->pnext->pnext;
if (pend == ptmpnode2) //最后只剩最小的数在第一个
{
break;
}
while (ptmpnode2 != pend) //pend刚开始等于NULL
{
if (ptmpnode1->data > ptmpnode2->data)
{
tmpdata = ptmpnode1->data;
ptmpnode1->data = ptmpnode2->data;
ptmpnode2->data = tmpdata;
}
ptmpnode1 = ptmpnode1->pnext;
ptmpnode2 = ptmpnode2->pnext;
}
pend = ptmpnode1; //pend每次循环完向前移移位
}
2.选择排序
while(pfirstnode->pnext != NULL)
{
pminnode = pfirstnode;
while(ptmpnode != NULL)
{
if(ptmpnode->data < pminnode->data)
{
pminnode = ptmpnode;
}
ptmpnode = ptmpnode->pnext;
}
if(pminnode != pfirstnode) //pminnode不在第一个位置
{
tmpdata = pfirstnode->data;
pfirstnode->data = pminnode->data;
pminnode->data = tmpdata;
}
pfirstnode = pfirstnode->pnext; //最小数在前面放，每次向后移一位，留倒数最后一个不用比
ptmpnode = pfirstnode->pnext; //外层循环结束记得将ptmpnode重新定位在pfirstnode的pnext位置
}
（十四）判断链表是否有环（00-图）
1.判断链表是否有环：用快（走两步）慢（走一步）指针，快指针等于满指针即有环
2.计算环长：指针从相遇点开始走到该节点为止（ptmp != pslow）,计数值起始为1
3.环入口位置：从相遇点走的指针和从开头走的指针相遇的位置
4函数:int circle_linklist(linknode *phead, int *pcircle_exit,int *pcircle_len,linknode **ppcircle_entrance)
通过此函数通过指针，将结果赋给定义的变量
void circle_linklist(linknode *phead, int *pcircle_exit,int *pcircle_len,linknode **ppcircle_entrance)
{
linknode *pfast = NULL;
linknode *pslow = NULL;
linknode *ptmpnode = NULL;
linknode *pstartnode = NULL;
//1.判断链表是否有环
pfast = phead->pnext;
pslow = phead->pnext;
*pcircle_exit = 0;
while(1)
{
pfast = pfast->pnext;
if (NULL == pfast)
{
break;
}
pfast = pfast->pnext; //走一步判断一次
if (NULL == pfast)
{
break;
}
pslow = pslow->pnext;
if (pfast == pslow) //相遇时结束
{
*pcircle_exit = 1;
break;
}
}
//2.计算环长
int len = 1;
ptmpnode = pslow->pnext;
while (ptmpnode != pslow)
{
len++;
ptmpnode = ptmpnode->pnext;
}
*pcircle_len = len;
//3.找环入口
pstartnode = phead->pnext;
ptmpnode = pslow;
while (pstartnode != ptmpnode)
{
pstartnode = pstartnode->pnext;
ptmpnode = ptmpnode->pnext;
}
*pcircle_entrence = ptmpnode;
}
三、双向链表、循环链表、内核链表（参考单向链表）
（一）循环链表
1.定义双向节点：头节点data不存数据，让ppre和pnext指向自己
2.头插：头节点后插。不要将头节点值覆盖，先指向头节点指向的值。
3.尾插：头节点前插。
4.遍历：从头结点后一个开始，头节点为结束标志
5.查找
6.修改
7.删除
8.销毁：(->)优先级高于（*）。从头节点的下一个开始销毁，遍历到头节点结束，然后销毁头节点前一个和头节点。
（二）内核链表：双向循环链表，每个节点包含指向前驱节点和后继节点的指针
1.普通链表节点包含数据，内核链表数据中包含链表节点
2.应用场景
进程管理：Linux 内核使用链表来管理进程。例如，所有的进程描述符通过链表连接起来，方便进行进程的创建、调度、销毁等操作。
设备驱动：在设备驱动中，链表用于管理设备相关的数据结构。比如，系统中所有同类设备的设备描述符可以通过链表组织起来，方便驱动程序对设备进行统一管理和操作。
内存管理：内核内存管理模块也会用到链表，用于管理空闲内存块，将空闲的内存块通过链表连接起来，在分配和释放内存时，通过操作链表来快速找到合适的内存块。
（三）链表、栈、队列特点
1.三者都是一种线性结构
2.栈只允许在栈顶位置入栈和出栈
3.链表可以在任意位置插入和删除
4.队列只能在队尾入队，队头出队
四、栈（瓶子里塞东西）
（一）栈分类
1.空栈：栈针指向内容为空，先赋值栈针再偏移
2.满栈：栈针指向栈顶位置，栈针先偏移再赋值
4.减栈：栈增长方向从高地址向低地址
5.增栈：栈增长方向从低地址向高地址
（二）顺序栈（37页）、链式栈（链表实现、基于内核链表实现）
五、队列（管道里塞东西）：（42页），循环队列和链式队列
六、二叉树
（一）概念：非线性结构一对多
1.节点：组成树形结构的一个小的单元
①根节点：只有后继没有前驱
②分支节点
③叶子节点
2.层：根节点层数为1，以后每层层数+1
3.树的层数 = 高度 = 深度：用最高层表示
4.度：后继节点的个数
（二）二叉树（01-图）
1.概念：属性结构中所有节点度数最大位2，称为二叉树
2.满二叉树
①第k层节点个数：2的k-1次方
②前k层节点个数：2的k次方-1
3.完全二叉树：节点编号为n，左孩子为2n，右孩子为2n+1，展开后是连续的
（三）完全二叉树遍历方式
1.深度优先遍历（DFS）：
①前（先）序遍历:跟左右
②中序遍历：左根右
③后续遍历：左右根
2广度优先遍历（BFS）：层序遍历：逐层从左到右一次遍历
（四）完全二叉树操作（50页）
七、哈希表
（一）概念
1.哈希算法：将数据通过哈希算法映射成一个键值，存取都通过键值实现高效存储和查找，时间复杂度尽可能降至O（1）
2.哈希碰撞：多个数据通过哈希算法得到的键值相同
（二）哈希表
1.构建哈希表存放0-100之间的数据
2.哈希算法选择：将所有数据的个位作为键值（02-图）
3.哈希表插入（rand()获取随机数）
linknode *phashtable[INDEX]; //0-9十个指针,每个都相当于头节点
int insert_hashtable(int tmpdata)
{
int key = 0;
key = tmpdata % INDEX; //计算获取到键值
linknode **pptmpnode = NULL; //指向结构体指针的指针，可修改指向结构体指针的指向
linknode *pnewnode = NULL; //插入元素使用
//起始存储对应键值地址。结束时pptmpnode里面存储比他临界小的pnext指针的地址，这个指针也是指向比他临界大数据的指针
for(pptmpnode = &phashtable[key]; *pptmpnode != NULL && (*pptmpnode)->data < tmpdata;pptmpnode = &(*pptmpnode)->pnext)
{
}
pnewnode = malloc(sizeof(linknode));
if(NULL == pnewnode)
{
perror("malloc fail");
return -1;
}
pnewnode->data = tmpdata;
pnewnode->pnext = *pptmpnode; //修改他pnext
*pptmpnode = pnewnode; //修改比他临界小的pnext这个指针，让他指向插入节点
}
5.哈希表遍历
4.元素查找
5.哈希表销毁
八、排序查找算法（62页）
（一）冒泡排序（O（n的2次方））：相邻两个比较，每次将最大值放在最后
（二）选择排序（O（n的2次方））：用一个变量存最小值下标，每次假设为第一个，若不是则交换。
（三）插入排序（O（n的2次方））
（四）希尔排序（O（nlogn））
（五）快速排序（O（nlogn））
（六）折半（二分）查找（O（logn））
（七）顺序查找（O（n））
九、Makefile
（一）概念：工程管理工具，主要用来管理代码编译
（二）要生成的文件：依赖的文件
要生成的方式
（三）$^: 所有依赖的文件 $@：要生成的文件
十、ubuntu(vim)快捷键
（一）:vsp + 文件名,在vim中打开另一个文件
（二）ctrl + ww:切换vim中窗口。在 Vim 处于普通模式（未输入编辑命令时的模式）下，按 Ctrl + w 再接着按方向键（h 左、j 下、k 上、l 右），就能在不同的分屏窗口之间切换
（三）删除、复制和粘贴：无（：）直接ndd,nyy,p
（四）两个vim终端切换：按住Alt和Tap，然后方向键控制
（五）u撤回
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
25
0- 0
已为社区贡献2条内容
所有评论(0)