数据结构
1.数据类型
【原子类型】：
是不可以在分解的基本数据类型，包含整型，浮点型，字符型等。
【结构类型】：
由若干类型组合而成，是可以再分解的，例如，整型数组就是由若干整型数据组
成的
2.抽象数据类型
指一个数学模型以及定义在该模型上的一组操作
比如使用到坐标，xyz 坐标
3.数据结构 类型
集合结构：
一群数据归类到一个集合中，集合有包含关系，交集，并集，包含等等
线性结构
元素之间的关系是一对一的
常用的线性结构有：
线性表、栈、队列、双队列、数组、串。
树形结构
元素是一对多的层级关系
常见的树形结构:
二叉树、B树、哈夫曼树、红黑树等
图形结构
数据元素之间的关系是多对多的
常见的图形结构：邻近矩阵、邻接表。
顺序存储结构
把数据元素存放在地址连续的存储单元里，内存地址也是连续的
数组：
它的元素是一个接一个，在内存空间中的地址也是连续的
栈：
连续的存储结构
链式存储结构
数据元素放在任意的存储单元里，可以连续也可以不连续
堆：
既可以非连续存储分配，也可以分配连续地址
4.算法是什么？
算法就是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并
且每个指令表示一个或者多个操作
特性：
输入输出
有输入有输出
有穷性
计算过程不是无穷的或死循环的
确定性
确定的步骤有确定的结果，不是未知结果
可行性
每一步都能通过执行有限次数完成
设计要求：
正确性
正常数据有正常唯一结果，非正常数据有对应返回
可读性
尽量便于阅读，理解和交流
健壮性
考虑边界性，当输入数据不合法时，算法也能做出相关处理，而不是产生异常和
莫名其妙的结果
时间效率高和存储量低
时间和空间的最优解
时间复杂度
常数阶
有限常数次都是O（1）时间复杂度
比如 1000，10000 都是
线性阶
for (int i = 0; i < n; i++) {
// 时间复杂度为O(n)的操作
}
对较大数n的遍历时间复杂度O（n）
对数阶
int i = 1;
while (i < n) {
i = i * 2;
}
在循环体内，i每次都乘以2倍，即为2^x = n，可以得出次数x为以2为低n的对
数x = log2n。根据推导大O阶的方法，去除最高阶项的常数，即为O(logn)。
平方阶
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 时间复杂度为O(n^2)的操作
}
}
循环嵌套n*n，时间复杂度为O(n^2)
对比：
O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(n^3)
< O(2^n) < O(n!) < O(n^n)
空间复杂
和时间复杂度类似，只不过，空间复杂是计算存储空间的遍历 ，也是O（x）
主要是对数据进行操作的辅助空间
线性表
顺序表
Array，list 都是顺序表，通过下表获取或者删除数据
单链表
//定义结点
typedef struct KNodeInfo{
KElementType data;
struct KNodeInfo *next;
}Node;
由数据和next指针组成
结点p数据：
p->data
结点p下一个接到：
p->next
删除结点q
//q指向要删除的结点
q = p->next;
//将q的后继赋值给p的后继
p->next = q->next;
//将q结点中的数据赋值给e
*e = q->data;
//释放内存
free(q);
插入结点s
//生成新结点s
s = (KLinkList)malloc(sizeof(Node));
//将e赋值给s的数值域
s->data = e;
//将p的后继结点赋值给s的后继
s->next = p->next;
//将s赋值给p的后继
p->next = s;
遍历单链表
while (p) {
p = p->next;
// printf
}
清空单链表
//指向第一个结点
p = (*head)->next;
while (p) {
//遍历删除每个结点，并释放内存
q = p->next;
free(p);
p = q;
}
单向循环链表
空循环链表
只有一个结点，它的next指针指向自己
判断是否单向循环链表？
双指针，一个定位标记，一个遍历，最终会相等
遍历循环链表
// 2.遍历循环链表
void traverseCircleList(LinkList L) {
//判断链表是否为空
if(!L) {
printf("链表为空！\n");
return;
}
LinkList temp;
temp = L;
do {
printf("%6d", temp->data);
temp = temp->next;
}while (temp != L) ;
printf("\n");
}
插入和删除同单向链表
双向链表
//定义结点
typedef struct KNode{
KElementType data; //数据
struct KNode *prior; //前驱指针
struct KNode *next; //后继指针
}Node;
为什么要双向？
如果要删除一个指定结点q，需要将q上一个结点指向下一个结点，
单向链表可以获取next，但是前一个结点无法获取，1 要么提前记录了 2要么从
表头开始遍历 。
这样成本太高，如果新增一个prioe 前指针，那么问题就简单
操作： 同单向链表，只是多了一个前指针设置
顺序栈
先进后出 FILO
//顺序栈结构
typedef struct KSqueueStack{
KStackElementType data[MAXSIZE];
int top; //用于栈顶指针
}SqStack;
栈置空
KStatus clearStack(SqStack *S) {
S->top = -1;
}
顺序栈获取长度
//4. 获取栈长度
int getLength(SqStack S) {
return S.top + 1;
}
栈顶元素
//栈空，则返回错误
if (S.top == -1) return ERROR;
*e = S.data[S.top];
入栈
//6. 压栈
KStatus push(SqStack *S, KStackElementType e) {
//判断是否 栈满
if (S->top == MAXSIZE -1) return ERROR;
S->data[++(S->top)] = e;
return OK;
}
========解释====================
//1. 栈顶指针+1;
//2. 将新插入的元素赋值给栈顶空间
//S->top ++;
//S->data[S->top] = e;
出栈
//判断是否栈空
if(S->top == -1) return ERROR;
*e = S->data[S->top--];
======解释==
//1. 将要删除的栈顶元素赋值给e
//2. 栈顶指针--;
//*e = S->data[S->top];
//S->top--;
链式栈
链式栈的栈顶不再是简单int 记录长度，而是增加结点，形成链
结点结构：
//链栈结点
typedef struct KStackNode {
KStackElementType data; //结点数据
struct KStackNode *next; //指向下一个结点的指针
}StackNode, *LinkStackPtr;
链栈结构：
//链栈结构
typedef struct KLinkStack {
LinkStackPtr top; //栈顶结点
int count; //栈大小
}LinkStack;
压栈
//6. 压栈
KStatus push(LinkStack *S, KStackElementType e) {
//1. 创建一个新结点，
LinkStackPtr newNode = (LinkStackPtr)malloc(sizeof(StackNode));
//2. 赋值给新结点
newNode->data = e;
//3. 插入新结点到栈顶结点后面
//3.1 把当前的栈顶元素的结点指针指向直接后继结点
newNode->next = S->top;
//3.2 将新结点赋值给栈顶指针
S->top = newNode;
//栈大小+1
S->count++;
return OK;
}
出栈
//7. 出栈
KStatus pop(LinkStack *S, KStackElementType *e) {
LinkStackPtr p;
if (isEmpty(*S)) return ERROR;
//1. 将栈顶元素赋值给*e
*e = S->top->data;
//2. 将栈顶结点赋值给p
p = S->top;
//3. 使得栈顶指针下移一位, 指向后一结点
S->top = S->top->next;
//4. 释放p结点
free(p);
//栈大小减1
S->count--;
return OK;
}
队列
是一种先进先出(First In First Out)的线性表，也就是FIFO
通常，称进数据的一端为 "队尾"，出数据的一端为 "队头"，称入队和出队
单向队列
注意
底层使用的是数组
需预先申请一块足够大的内存空间初始化顺序队列
需要定义两个指针（top 和 rear）分别用于指向顺序队列中的队头元素和队尾元
素
空队列：双指针都指向同一个地址
插入数据后：头指针指向第一个数据，尾指针指向最后一个数据后面那个空位置
（不是最后一个数据）
删除数据（出队列）top指针是移动，这样连续地址上前后端都会出现空缺
如果直接不断插入就会溢出，因为头指针前有空位没有利用
如果出队列后，全部移动，性能不佳
下面介绍循环队列
循环队列
前面介绍出队列后，top指针前有连续区域不能利用，如果是循环队列，那就么
有这个问题了。
/* 循环队列的顺序存储结构 */
typedef struct KQueue
{
KQueueElementType data[MAXSIZE];
int front; /* 头指针 */
int rear; /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}KQueue;
Q.front 前针 ， Q.rear 后指针
队列为空
Q.front == Q.rear
队列已满
Q.front = Q.rear + 1表示堆满
也就是当剩余最后一个空间当时候，不再插入数据，【插满了就无法判断是空还
是满队列】
入队
//判断队列是否满了
if (isFull(*Q)) {
return ERROR;
}
//将元素e赋值给队尾
Q->data[Q->rear] = e;
//rear指针向后移动一位，若到最后则转到数组头部
Q->rear = (Q->rear + 1) % MAXSIZE;
return OK;
出队
if (isEmpty(*Q)) return ERROR;
//从队头取出元素赋值给e
*e = Q->data[Q->front];
//front指针向后移动一位，删除对头元素
Q->front = (Q->front + 1) % MAXSIZE;
堆
物理上，一般基于线性数据结构
（如数组、向量、链表等）的一种数据结构
比如：【 1，2，3，4，5 】
逻辑上，是二叉树结构
是基于 完全二叉树 和 搜索二叉树 之间的排序
搜索二叉树 下， 结点 2 左孩子 3，右孩子是4 。
堆的结点2 ，它左可以3，也可以4，只要比孩子结点小就行（小根堆）
内存空间
堆的存储空间可以是非连续的，需要用户管理，适合链表结构，不像栈是完全连
续空间
根据根节点是最大值还是最小 来划分
大根堆： 结点都大于孩子结点，根结点是最大的
小根堆：根结点是最小的，所有结点都小于它的孩子结点
堆插入数据
为了满足大小根堆 规则，插入的数据不是简单的插入首尾
元素上移这个操作和这个树的深度有关系因此需要O(log n)的时间复杂度
大根堆
max-heap
尾部插入数据
判断比父结点大，就交换，继续比较父结点，直到比父结点小，或者自己成为根
结点
小根堆
min-heap
尾部插入
判断比父结点大就交换，直到根结点
删除数据
删除结点后，都需要重新判断父子结点大大小，进行交换
数组 和 堆二叉树 转换
搜索
比如大根堆：搜索8，如果搜索到某个结点是7，那么7及其子节点不需要再搜索
了
堆的搜索效率不是很高
效率
堆 不管是插入，删除，还是搜索，都不是很高效，因此Swift才推荐用户对使用
结构体，因为结构体存储在栈上，效率高