数据结构
数据结构分为顺序表，链表，栈，队列，堆，树，图
顺序表
顺序表的物理结构和逻辑结构都是连续的
去建立一个顺序表，我们需要先去了解底层是什么。
在脑海中很容易就会联想到数组，所以创建一个顺序表，首先要有一个数组。但是仅仅有数组是不够的，我们需要在其中对数据进行处理，那么其有效元素的个数以及容量自然是不可或缺的，所以
顺序表的结构就如下
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr;
int size;
int capacity;
}SL ; 我们现在并不知道我们需要在顺序表中处理什么类型的数据，所以我们用typedef来将类型重命名，这样就算后面需要更改类型，我们也不需要将类型一个一个 进行修改，只需要在typedef int SLDataType这里将int修改为需要的类型即可。
另外对于在结构体前加typedef是为了在后面需要使用该结构体的时候方便调用。如果没有使用typedef，那么在后期的调用需要以struct SL sl1来声明；但是使用后便只需SL sl1这样即可，在较大项目中就会有很大的用处
首先我们的顺序表肯定是需要先进行初始化的，要是不初始化，那么我们的ps就是NULL了，里面什么也没有，就连顺序表的结构都没有更别提去使用顺序表了
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->size = ps->capacity = 0;
}为了防止ps=NULL，我们可以使用函数assert(断言，头文件为<assert.h>)来保证不为NULL，如果为空，那么就会终止程序进行，如图所示
在对顺序表进行修改前，我们需要给它分配一块动态内存，必须要有内存，才可以将数据储存其中，然后在对其中数据进行处理。不仅仅是开始时需要分配动态内存，开始时分配的动态内存不是无限的，在后续加入数据是内存会不足，这时就需要在原有的空间之上另外开辟新的动态内存
void SLcheckCapacity(SL* ps)
{
assert(ps != NULL);
//空间不够
if (ps->size == ps->capacity)
{
int newrong = ps->capacity == 0 ? 4 : ps->capacity * 2;
//二倍增容
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newrong * sizeof(SLDataType));
if (tmp == NULL)
{
perror("");
exit(1);
}
ps->arr = tmp;
ps->capacity = newrong;//容量从新转到末尾
}
}总之，我们需要先去创建一个顺序表的结构，才能给它开辟一块空间，毕竟我们是要用顺序表的 结构的。换句话说，现在顺序表就像水桶，空间就像水。我们只有先有水桶，我们才可以装水。当然，其他工具也可以装水，但是我们要使用的是水桶！
那么下面来说说关于对顺序表数 据处理的几种常用方法
尾插
顾名思义，就是在顺序表的尾部进行数据的插入。那么该如何实现呢？
首先自然是判空了，即assert(ps!=NULL)
接着就是对于顺序表的空间容量进行检查，若不够自然需要分配更多的空间，通过调用上面提到的 SLcheckCapacity函数来判断空间是否充足，若不足可以在进行空间的开辟。
准备工作完成了之后就可以开始尾插了
对于我们的size，是有效元素个数，由于数组是由0开始的，所以size的位置指向的是最后一个元素后面的位置，我们的新数据就可以直接插到ps->arr[size]这个位置，再让size向后面移动一位，即size++
为了简便，我们可以将其合并为一行代码ps->arr[ps->size++] = x
由于这里是后置++，所以我们会先对原有的size进行使用再使其加1
void SLPushBack(SL * ps, SLDataType x)
{
assert(ps != NULL);
SLcheckCapacity(ps);
ps->arr[ps->size++] = x;
}其时间复杂度为O(1)
头插
与尾插相反，这是在顺序表的最前面插入数据。
相较于尾插，头插的时间复杂度就大的多了。前面的判空以及空间的检查都和尾插一样，这两个步骤在后面不再进行特殊说明，有区别的在于插入过程。
头插需要将所有的元素都向后移动一位，从而为头插腾出空间，所以其空间复杂度为O(N)
void SLPushHead(SL* ps, SLDataType x)
{
assert(ps);//等价于assert(ps != NULL)
SLcheckCapacity(ps);
//直接头插
//数据整体向后移一位
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
++ps->size;
}对于++ps->size，其含义是ps中的size加1，->的优先级大于++
尾删
顾名思义，就是删除最后面的元素，有手就行
void SLPopBack(SL* ps)
{
assert(ps && ps->size!=0);
--ps->size;
}我们不需要真正的把最尾部的元素删除，我们只需要把size往前移一位就行，这样在后续进行尾插的时候新元素会将要删除的元素覆盖
--ps->size中->的优先级大于--,所以其含义就是将size向后移动一位
时间复杂度是O(1)
头删
其和头插的操作差不多,是将除了第一个元素的其他元素向前移动,由于元素少了一个,所以让size向前移动一位
void SLPopHead(SL* ps)
{
assert(ps && ps->size);
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
--ps->size;
}其空间复杂度是O(N)
查找
对于顺序表,我们不仅仅要对其中元素进行修改,我们还需要查找我们所需要的元素的位置
我们只需要将自己想要查找的元素分别和所以元素遍历，再返回与其相同元素的地址
int SLFind(SL* ps, int pos, SLDataType x)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}
时间复杂度为O(N)
在指定位置前插入和删除数据
对于这个插入函数，我们需要三个参数void SLInsert(SL* ps, int pos, SLDataType x)，其中pos是指定的位置。我们只需要将从pos(包括pos)开始的元素向后面移动一位。如果我们从pos开始向后移动，那么pos后面的数据将会被覆盖。所以我们从最后面开始，将最后面的元素先向后移动，一直到pos向后面移动后停止，最后再将size++就完成了
空间复杂度为O(N)
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps && pos >= 0 && pos <= ps->size);
SLcheckCapacity(ps);
for (int i=ps->size;i>pos;i--)
{
ps->arr[i] = ps->arr[i-1];
}
ps->arr[pos] = x;
++ps->size;
}对于删除函数，就只需要两个参数了(因为不需要插入数据了)，和插入数据大同小异，只需要从pos开始将pos及其后面的元素向前移动一位，就可以覆盖pos前面的元素，由于减少了一个元素，所以size--
void SLErase(SL* ps, int pos)
{
assert(ps && pos >= 0 && pos <= ps->size);
for (int i = pos ; i < ps->size -1;i++)
{
ps->arr[i] = ps->arr[i + 1];
}
--ps->size;
}销毁
现在已经完成了常见的顺序表操作了，那就该讲讲销毁了。
只需要将ps中的arr的空间释放，再将arr赋值为NULL(若直接释放arr而不将其赋值为NULL，那么arr就会变为野指针，十分危险，就像野狗一样)，size和capacity赋值为0就完成了顺序表的销毁
void SLDesTroy(SL* ps)
{
if (ps->arr)
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}顺序表的储存方式是顺序储存，在内存中申请一块连续的空间，通过下标来进行储存。这也导致了插入和删除数据的效率低下，而且其在扩容时会二倍扩容，这也就导致了空间的浪费，但是顺序表也有一定的优点，其查找数据可以直接使用下标进行查找，非常方便，且其CPU缓存利用率高，所以顺序表的使用场景一般在需要元素高效储存和频繁访问的领域
链表
链表是由许多个结点构成的。所谓链表，顾名思义，就是像锁链一般的结构，其中的锁链就是链接每个结点之间的指针，所以其每个结点的结构中必然存在指针结构，去指向后面的结点。
链表有单链表和双链表之分，首先我们来聊一下单链表怎么实现
单链表需要储存一个和一个指针，所以他的的结点结构如下
typedef struct SListNode
{
SLDataType data;
struct SListNode* next;
}SLTNode;
既然我们已经构建好了结点的结构，那么接下来，我们需要对其进行引用
首先我们为结点开辟一块动态内存，当然开辟后我们需要判断是否开辟成功，若成功则让该函数的打他等于0，再让它的next指向下一个结点的地址,最后返回该结点的地址
SLTNode* SLTBuyNode(SLDataType x)
{
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
if (node == NULL)
{
perror("malloc fail!\n");
exit(1);
}
node->data = x;
node->next = NULL;
return node;
}对于链表的遍历，只需要通过上一个节点中的next找到下一个结点的地址。再打印出data即可，在后面的每一个操作都需要判空，在后面的操作中不在特殊说明
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur != NULL)
{
printf("%d -> ", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}尾插
在链表中，每一个元素都是一个结点，所以只需要在最后一个结点的后面加上一个结点就实现尾插了
在详细一点就是先申请一个结点，在这个结点中将data赋值，再将原链表的最后一个结点指向刚刚申请的结点，最后让刚刚申请的结点的next指向NULL，代码如下
void SLTpushBack(SLTNode** pphead, SLDataType x)
{
SLTNode* newnode = SLTBuyNode(x);
//链表为空
if (*pphead == NULL)
{
*pphead = newnode;
}
//链表非空，找尾结点
else
{
SLTNode* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;
}
ptail->next = newnode;
}
}头插
头插只需要申请结点，将该结点的next指向原链表的第一个结点就可以了。
这里需要传二级指针是因为我们不仅仅要使用头结点的地址，还需要对其进行修改，在传参的时候，一旦涉及到要对该参数进行修改，而且想要这种修改会影响到实参，那么就需要传比该参数更深层次的参数。例如想要改变变量就要传一级指针，想要改变一级指针就要传二级指针
void SLTpushFront(SLTNode** pphead, SLDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}尾删
这里的二级指针和头插的效果是一样的，如果只有一个结点，那么需要将空间释放并且将头结点的地址赋值为NULL
如果不是只有一个结点，那么只需要通过next找到尾结点,然后将尾结点释放并赋值为NULL
void SLTPopBack(SLTNode** pphead)
{
assert(pphead && *pphead);
//如果只有一个结点，需要特殊处理
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* prev = NULL;
SLTNode* ptail = *pphead;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
free(ptail);
ptail = NULL;
}
}
头删
只需要将头结点释放，再将头结点的next指向下一个结点
void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
前插
所谓前插就是在指定结点前面插入一个结点，实现方法也是十分简单，若是只有头结点，那么就需要改变头结点的地址了，若要插入的结点不是头结点，那么只需要让该结点连接在中间即可
void SLTInset(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
assert(pphead && pos);
SLTNode* newnode = SLTBuyNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}后插
如果只有一个结点，那么相当于尾插
对于一个具有多个结点的链表，我们只需要将它连接在该结点和其后面的结点之间即可
void SLTInsetAfter(SLTNode* pos, SLDataType x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode = pos->next;
pos->next = newnode;
}删除结点
要分两种情况,一种是有多个结点的链表，这种情况并不需要二级指针，只需要将该结点释放，再将其前后的结点相连接即可；第二中情况是只有一个结点的链表，这种情况需要用到二级指针，因为需要改变头结点的地址
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && pos);
if (*pphead != pos)
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
else
{
SLTPopFront(pphead);
}
}后删
只需要将通过该结点next找到后面的结点然后将其释放，再将其赋值为NULL，再将删除结点的前后相连即可
void SLTEraseAfter(SLTNode* pos)
{
assert(pos && pos->next);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}销毁
现在常见的对链表的操作已经实现了。最后就需要销毁链表了，由于需要将头结点赋值为NULL，所以我们需要将二级指针传参，在逐一将其释放即可
void SListDestroy(SLTNode** pphead)
{
SLTNode* pcur = *pphead;
SLTNode* next = NULL;
while (pcur)
{
next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
栈
在计算机的内存中也有栈，但是我们所说的栈和它有所不同，内存中的栈只是一块特殊的内存区域，用于储存函数调用时的相关信息，如局部变量， 函数参数，返回地址等，由系统自动管理；而数据结构中的栈是一种抽象的数据类型，具有先进后出的特点，仅仅允许在一端进行插入和删除
对于栈，上面也说到了栈的特点：（1）只在一端插入和删除数据（栈顶），另一端叫做栈底 （2）所有的数据都遵循先进后出的原则
栈的实现我们可以用链表或者顺序表的结构，这里我们选择顺序表结构，所以其结构为
typedef struct Stack
{
STDataType* arr;
int capacity; //栈的空间大小
int top; //栈顶
}ST;初始化
void STInit(ST* ps)
{
assert(ps);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
入数据
首先我们先用assert函数来判空，接着判断空间是否充足，若不够，则开辟新的空间，同时判断是否开辟成功，若成功，则将新地址赋值给arr，再将新的容量赋值给capacity
若空间充足，则直接将值插入，然后将top++，这里是top++，也就是先用再加
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//1.判断空间是否足够
if (ps->capacity == ps->top)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
//空间足够
ps->arr[ps->top++] = x;
}出数据
出数据只需要将top向后面移动一位，这样下一次入数据就会将其覆盖了
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
--ps->top;
}取栈顶数据
在取栈顶元素前，我们需要判断栈是否定义和是否为空，对于是否为空，我们定义一下函数StackEmpty来判断，其返回值类型是一个布尔类型
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}top指向的位置是栈顶的后面，所以取top-1的元素即可
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->arr[ps->top - 1];
}获取栈中有效元素个数
top就是有效元素的个数，所以直接返回top即可（数组是从0开始的，所以最后一个元素的下标比实际元素少一个，而top又是在最后一个元素后面，所以top就是有效元素个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}队列
队列相较于栈而言，其队尾也可以处理数据
队列当然也可以用顺序表或链表的结构实现，这里我们用链表实现
声明
typedef struct Queue
{
QueueNode* phead; //队头
QueueNode* ptail; //队尾
int size; //队列有效元素个数
}Queue;初始化
只需要将队头和队尾的指针指向NULL即可
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
}
插入
首先自然是开辟空间，然后将值存在data中，其中发next指向NULL
接着在判断原队列是否为空队列，pq指向的是队列的队头，若为空队列，则让队头队尾等于刚刚申请的结点；若不为空队列，让队尾中的next指向刚刚申请的结点，再让队尾为刚刚申请的结点即可
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc fail!\n");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
//队列为空，队头和队尾都是newnode
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
else {
//pq->ptail newnode
pq->ptail->next = newnode;
pq->ptail = pq->ptail->next;
}
}队头删除
若队列只有一个结点，那么将它释放，再将队头队尾指向NULL
若队列中有多个结点，将该结点释放，并将队头向后面移动一位
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
//只有一个结点
if (pq->phead == pq->ptail)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else {
//多个结点
QueueNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
--pq->size;
}有效元素个数
要想找到有效元素，只需要将队列遍历，当该结点的next指向NULL时结束即可
int QueueSize(Queue* pq)
{
//int size = 0;
//QueueNode* pcur = pq->phead;
//while (pcur)
//{
// size++;
// pcur = pcur->next;
//}
//return size;
return pq->size;
}取堆头数据
直接取队头的data即可
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}取队尾数据
直接取队尾的data即可
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->data;
}销毁
这里不需要传二级指针，我们并不需要将整个队列结构销毁，我们只需要恢复其初始化状态即可
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* pcur = pq->phead;
while (pcur)
{
QueueNode* next = pcur->next;
free(pcur);
pcur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}树
树是一种非线性的数据结构，是由n(n>=0)个有限结点组成的一个具有层次关系的集合
之所以叫做树是因为它长的很像树，其由一个根节点延伸出许多的结点构成，如图
根结点：根节点没有前驱结点。
除根节点外，其余结点被分成是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
因此树是被递归定义的
节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为2
叶节点：度为0的节点称为叶节点； 如上图：G、H、I节点为叶节点
非终端节点或分支节点：度不为0的节点； 如上图：B、D、C、E、F节点为分支节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为2
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m棵互不相交的树的集合称为森林；
对于树的表示，有很多方法，如双亲表示法，孩子表示法，孩子兄弟表示法等
二叉树
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
二叉树的特点：
每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
二叉树的子树有左右之分，其子树的次序不能颠倒。
在二叉树中还有一些特殊的二叉树
满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
这里我们采用双亲表示法
typedef char BTDataType;
//二叉树结点结构的定义
typedef struct BinaryTreeNode
{
BTDataType data;//值
struct BinaryTreeNode* left;//左
struct BinaryTreeNode* right;//右
}BTNode;那怎么遍历呢
这里有4中遍历方法,前序遍历，中序遍历，后序遍历
遍历
前序遍历
前序遍历的顺序是根左右，经过不断的递归从而达到将整个二叉树遍历的效果
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}中序遍历
中序遍历的顺序是左根右，经过不断的递归从而达到将整个二叉树遍历的效果
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}后序遍历
后序遍历是左右根，经过不断的递归从而达到将整个二叉树遍历的效果
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}以上是部分常用的数据结构
标签：ps,结点,NULL,入门,next,pq,数据结构,size From： https://blog.csdn.net/2401_87311360/article/details/143351794