数据结构分为两部分：

线性：线性表，栈(先进后出)，队列（先进先出）

线性表存储方式：顺序-》数组     链式-》指针

线性1对1 树状1对多 图多对多

但数组的读取效率最快

（有头或无头）链式分为：单向链表：单向不循环和单向循环

                                          双向链表：双向不循环和双向循环

树：递归

关于标签页的切换：gt

顺序存储线性表

看了网上别人的文章，以前对ifndef的含义一直有些困惑。现在终于明白了。

以下文件在"os_cpu.h"中。

#ifndef __OS_CPU_H__
#define __OS_CPU_H__ 

/*

中间有许多定义啦声明啦！；；

*/

#endif /*__OS_CPU_H__*/

这样，在编译阶段（ifndef是在编译阶段起作用滴！）假设有两个文件同时include了这个文件（os_cpu.h），这两个文件如果一个先编译了，那么__OS_CPU_H__就被定义了。当编译到第二个文件的时候，那么在开始的判断（ifnef）就会自动跳出os_cpu.h这个文件的重复编译。这样就避免了重复编译文件。。

数据操作：增删插入销毁

 如果执行了return语句，那么后面的语句将会不执行。当前函数只要执行了return，之后的代码是不可能执行的

我们知道，一个Makefile中只有一个最终目标，就是第一个目标，上面的代码中，显然就是 all，那么all的依赖元素有2个，分别为main1和main2，而make具有自动推导，make在生成all的时候，自然要自动推导出main1和main2，这样我们就能通过一个Makefile生成了2个目标，分别是main1和main2，而这两个都是可执行程序，很巧妙的用法。
可以使用

线性存储表的代码：

 

 

 

 

 

 

 

 

单向链表的实现

链表主要分为数据域和指针域（用于指向下一个节点位置）

有头链表和无头链表：

 如果用插入的话需要知道插入地点前面节点的信息。

有头链表的实现：

 

 

 

 

 

 

 无头链表的实现：

 

 

 

 

 

两个多项式的合并：

使用双链表合并

 

 

 

 

 

 约瑟夫游戏（单向循环链表也就是首尾连接）当每经历固定值跳跃后将对应节点删除

 

 

 有两种创建方式：1.将所有链表创建完成后将最后一个链表的next指针指向第一个链表，2.每创建一个新链表都将其与第一个链表相连

第二种更好

 

 

 

 

双向链表的实现

在这一节我们要进行代码的规范化，也就是注重通用性以及效率

头节点设定：

两种插入方式：首部和尾部

首部：在头节点与第一个节点之间

尾部：插在头节点之前也就是最后一个节点之后

在两个节点之间插入一个新的节点可以通过以下方式：

只通过插入节点和其他一个节点便可以进行插入。

写数据库的时候需要考虑通用性，我们不知道用户数据结构是什么样的，所以我们需要用户自己来构建打印数据函数，而我们只需要规定函数类型就好

设置一个万用函数来接收用户函数：

用户需要做的：

关于函数名的发现：

节点数据结构的新形式：

以往的形式：

现阶段：

也就是说知道存储空间的首地址就可以

由于较早版本c不支持0数组所以可以用data【1】，只不过申请内存时要减4个字节。

char数组可以memcpy对原有的数据进行复制会将符号全部复制过来，相当于将malloc申请的空白属性的空间进行原有数据格式设置。所以可以直接使用原数据格式进行操作。

关于memcpy：

关于snprintf：

类似于sprintf，将格式化的字符串写入指定的缓冲区，可以限制写入的最大字符数以避免缓冲区溢出。

例如：

关于sizeof和strlen：

封装成类的体现：

首先是指向函数的指针定义：

注意上面所说的p和*p可以互用

主要改变在：

主要是将函数的调用进行了一次结构体封装。

除了上面的封装，还有一种目标是尽可能的减少函数内容的暴露，在.h文件中只告诉用户函数的使用方式：

内核双向链表赏析

内核对于节点的插入只有一个插入函数，就是将一个节点插入到两个节点中间，通过输入节点地址的不同可以实现首插和尾插

首部插入：

尾部插入：

内核中的节点类型往往是这种类型：

我们需要下面代码来进行节点地址的计算：

（TYPE )0,将 0 强制转换为 TYPE 型指针，即p = (TYPE )0，从而得到一个类型为TYPE*的空指针，那么 p->MEMBER 就是 MEMBER 这个元素了，而&(p->MEMBER)就是MENBER的地址，由于这个结构体的实际起始地址为0，这样就巧妙的获取了TYPE中的偏移量。再把结果强制转换为size_t型的就OK了，size_t其实也就是long int，当然在不同位数上类型可能不同，但是在这里肯定是足够大了。
定义一个成员变量类型的指针，先将传入的ptr保存下来在这个局部变量里，第二步将成员变量的指针强制转换成char*,然后减去成员变量在结构体中的偏移量，这样就得到了结构体的首地址，强制转换成结构体的type*类型，最终实现的功能就是从成员变量的指针获取到了该成员变量所属的结构体的指针。

栈的实现

顺序存储栈

顺序存储的最大缺点在于数据储存空间需要固定设置。

链式存储栈

首先需要设置一个头节点，栈入相当于首部插入，栈出相当于首部删除。

在之前的双向表的基础上进行二次封装：

队列的实现

顺序存储：

不循环队列：

当入队时，head指向头部且位置不变，tail随着储存内容的加入不断移动，指向当前已占储存位置的下一块空间，当head==tail则队列为空，tail大于下标则为满。

当出队时，tail指向尾部且位置不变，head随着储存内容的取出不断移动，当head==tail则队列为空，head小于下标则为满。

循环队列：

在不循环队列的基础上，实现当head和tail在超过某一下标后会回到头部的功能，以此实现循环：

如果以不循环队列判断队列满或空的标准来看，在循环队列中满和空的判定都是head==tail，这样是不行的，所以需要将head指向的空间不能存储数据以此来判断是否为满，并且tail指向当前存储空间，而不是下一块空间。

链式存储

在链表的基础上进行封装：

栈和队列的应用：计算器

分为两个栈一个用来存储‘（’或者+-等等运算符，一个用来存储数值。获得一个字符串，从头开始分别入栈。

关于运算符部分当实现‘）’入栈，看是否有‘（’，便可以出栈计算再将结果入栈。而+-等入栈时先判断与当前栈内符号优先级对比，若栈内优先级高就不要入栈，先对栈内进行计算入栈，再进行比对，也就是说，栈内的计算发生在符号优先级比较之后。

具体代码如下：

栈和队列的应用：求中算法

即有三个栈和一个队，每个时间会有队中的一个数据出队，按照优先级加入三个栈的优先级最高的一个，栈满则将栈内所有出栈入队，再将其加入优先级更低的栈中，会有一个时间点所有的数据都入队，且入队的数据大小顺序一致，则探究这个时间点是多少是求中算法。

具体代码如下：

静态库和动态库的实现

静态库：

ldd观察llist关联动态库，.so代表动态库，.a代表静态库，后面.数字代表版本号

用.o文件生成静态库

将.h和.a文件分别发到相应文件夹。

然后就可以直接调用不需要依赖原有的llist.c llist.h文件

并且对于llist.h的引用也可以变为<>

动态库：

若是想添加其他路径即非标准路径，需要修改文件在加载。

生成动态库：

-I:指定头文件路径，-L：指定库路径，但若是标准路径可以省略

如果同一个文件分别做成动态和静态库，会先连接动态库。

非root用户可以自己创建路径：

并且对于有依赖关系的库，需要将其依赖的库一起链接，并且对于库文件的改动有时需要重载路径

树

分为：顺序存储，链式存储。

顺序存储所需空间太大，且容易浪费。

链式存储：

遍历方式：按层遍历，先序，中序，后序。

链式二叉树的实现：

规定数据比当前节点小便向左，大就向右

树的程序与递归思想紧密相关，因为每一个节点都有父节点和子节点，结构一样：

结果：

类似于中序遍历。

平衡二叉树：

调整节点，使得任意节点的左右节点个数的差值在1以内。通过不断的选取根节点并进行旋转。

平衡过去的二叉树仍然保持左边小右边大的规则。

树的遍历：

通过调整print-s的顺序可以实现先序中序后序的遍历。

按层遍历：

通过队列来达到要求：将根节点放入队列中，出队到根节点时将根节点的左右节点放到队列。后面依次出队依次放入。

树转存为广义表实例：

将树写成下列类似于先序遍历的形式：

将树转换为广义表：

将广义表转换为树：

搜索树实例：

创建指针矩阵和数据，以空间换时间：

俄罗斯方块的程序设计

图形相关

1.ansi_vt

 常  用  ANSI  控  制  码  表

  【光标控制】
 ┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
 ┃  控  制  码  ┃                说                    明       ┃
 ┣━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃    [X;YH     ┃  将光标移至第 X 行，第 Y 列的位置。           ┃
 ┣━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃     [nA      ┃  光标上移 n 列。<<若至屏幕顶端则无效>>        ┃
 ┣━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃     [nB      ┃  光标下移 n 列。<<若至屏幕底端则无效>>        ┃
 ┣━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃     [nC      ┃  光标向右 n 行。<<若已至屏幕最右端则无效>>    ┃
 ┣━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃     [nD      ┃  光标向左 n 行。<<若已至屏幕最左端则无效>>    ┃
 ┣━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃     [6n      ┃  报告光标位置。                               ┃
 ┣━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃     [s       ┃  保存目前的光标位置。                         ┃
 ┣━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃     [u       ┃  取出保存的光标位置来使用。                   ┃
 ┣━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃     [?25l    ┃    隐藏光标                                   ┃
 ┣━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃     [?25h    ┃    显示光标                                   ┃
 ┗━━━━━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

  【屏幕控制】
 ┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
 ┃  控  制  码  ┃                说                    明       ┃
 ┣━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃     [2J      ┃  清除屏幕。 <<功能和 DOS 的 CLS 命令一样>>    ┃
 ┣━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃     [K       ┃  将光标位置开始至本列结束的所有字符清除。     ┃
 ┗━━━━━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

  【显示字符属性控制】
 ┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
 ┃  控  制  码  ┃                说                    明       ┃
 ┣━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃              ┃设定显示字符的属性状态。                       ┃
 ┃[n1;n2;......m┃若有两个以上设定则以分号将代码(n1;n2;..)隔开   ┃
 ┃              ┃除非重新设定，否则原设定之属性一直被保留。     ┃
 ┗━━━━━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

 ┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
 ┃   代   码    ┃                意                    义       ┃
 ┣━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃      0       ┃  所有属性 OFF，即返回正常显示模式 (Normal)    ┃
 ┃      1       ┃  高亮度显示 (Bright)                          ┃
 ┃      4       ┃  加下划线 (Underline) (注1)                   ┃
 ┃      5       ┃  闪烁显示 (Flash) (注2)                       ┃
 ┃      7       ┃  反相显示 (Inverse)                           ┃
 ┃      8       ┃  不可见 (Invisable)                           ┃
 ┣━━━━━━┳━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃ 前景 ┃ 背景  ┃                颜                    色       ┃
 ┣━━━━━━╋━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃  30  ┃  40   ┃  黑色                                         ┃
 ┃  31  ┃  41   ┃  红色                                         ┃
 ┃  32  ┃  42   ┃  绿色                                         ┃
 ┃  33  ┃  43   ┃  黄色                                         ┃
 ┃  34  ┃  44   ┃  蓝色                                         ┃
 ┃  35  ┃  45   ┃  紫红色                                       ┃
 ┃  36  ┃  46   ┃  青蓝色                                       ┃
 ┃  37  ┃  47   ┃  白色                                         ┃
 ┗━━━━━━┻━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ 

【字体控制】
 ┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
 ┃  控  制  码  ┃                说                    明       ┃
 ┣━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃     [0I      ┃  恢复正常字体                                 ┃
 ┣━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃     [1I      ┃  宋体                                         ┃
 ┣━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃     [2I      ┃  黑体                                         ┃
 ┣━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
 ┃     [3I      ┃  楷体                                         ┃
 ┗━━━━━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

ANSI控制码的说明
例如:
echo -ne "\33[32m" 可以将字符的显示颜色改为绿色
echo -ne "\33[3;1H" 可以将光标移到第3行第1列处
具体的摘抄一些如下：
\33[0m 关闭所有属性
\33[1m 设置高亮度
\33[4m 下划线
\33[5m 闪烁
\33[7m 反显
\33[8m 消隐
\33[30m -- \33[37m 设置前景色
\33[40m -- \33[47m 设置背景色
\33[nA 光标上移n行
\33[nB 光标下移n行
\33[nC 光标右移n行
\33[nD 光标左移n行
\33[y;xH设置光标位置
\33[2J 清屏
\33[K 清除从光标到行尾的内容
\33[s 保存光标位置
\33[u 恢复光标位置
\33[?25l 隐藏光标
\33[?25h 显示光标

[ <parameters> m 设置显示属性. 同样的序列可以设置一个或多个属性.

par 作用
0 所有属性重设为默认值
1 设置边框
2 设置亮度减半(用一种颜色模拟另一种颜色)
4 设置底纹(用一种颜色模拟另一种颜色)
(用于模拟的颜色由using ESC ] ...设置)
5 设置闪烁
7 设置反转视频(reverse video)
10 重设选定映像,显示控制标记,
反转元素标记.
11 选择空映像,设置显示控制标记,
重设反转标记.
12 选择空映像,设置显示控制标记,
重设反转标记.(在完成映像表转
换之前反转标记引起每一字节的
高位反转.)
21 设置正常亮度(和 ECMA-48 不兼容)
22 设置正常亮度
24 关闭下划线
25 不闪烁
27 反转视频关闭
30 黑色背景
31 红色前景
32 绿色前景
33 棕色前景
34 蓝色前景
35 品红前景
36 孔雀蓝前景
37 白色前景
38 打开下划线,设置默认前景色
39 关闭下划线,设置默认前景色
40 黑色背景
41 红色背景
42 绿色背景
43 棕色背景
44 蓝色背景
45 品红背景
46 孔雀蓝背景
47 白色背景
49 设置默认背景色

例如：

2.关于图形使用framebuffer首先判断/dev/lab0是否存在，并且需要ctrl alt f1打开虚拟控制台才能看到图形，ctrl alt f7回到原桌面。

vga的改变

对于只读文件的修改可以先：set noreadonly，再修改，当然是在root情况下。

/+单词实现快速查找。

输入设备相关

ctrl + c中断循环

会出现

因为将enter也进行了输入，变成了a

若要解决，改变为：

回显的作用：

并发相关：

在一个无限循环中，添加信号软中断，当接收到信号时立刻执行，实现类似于并发的效果

实现效果：