数据结构两万字大总结（超详细教程）

大家好呀，我是小生🙈🙉🙊小生把数据结构的顺序表和链表做了一个大总结，希望在方便自己复习的时候也能帮助到大家。 文章很长建议先收藏再看不然担心下一次就找不大啦，哈哈🥳🥳🥳加油初学者，加油技术人！！

当然，小生建议大家在看这篇文章的时候大家可以结合数据结构栈和队列一起看哦，这样一套下来，线性结构基础就差不多了😎😎😎 大家直接点击就可以啦🏃‍♀️🏃‍♀️🏃‍♀️：
👇👇👇
五千字高效学习数据结构栈和队列

顺序表

一.🏠顺序表和线性表

1.1🚀认识线性表和顺序表

​对于很多初学者而言，总喜欢把顺序表和线性表混淆，那小生就把他们做个对比吧😎😎😎

线性表：线性表是N个具有相同特性的数据元素的有限序列。线性表不等同于顺序表，常见的线性表有：顺序表，链表，字符串，队列，栈等。都是属于线性结构。这里我们可以通过一个图来认识一下以后要学的顺序表和链表。

顺序表：是用一段连续的存储单元依次存储数据元素的线性结构，一般采用数组存储，进行数组的增删改查。因此，顺序表只是线性表的一小部分。

1.2.🚀构建静态顺序表

小生认为，静态顺序表的特点就是使用定长数组储存元素，无法进行扩容。既然我们了解到它的特点，那我们就来构建一下。🥳🥳🥳

//初始化静态顺序表
#define N 10               //长度根据需求定义，宏定义的目的是发现数组内存不够时可以只调整N的大小不必要再到后面的程序做更改，更为方便。
typedef int SLDataType;    //这里可以不重命名，小生这里是提升代码的规范性方便读者阅读。
typedef struct SeqList
{SLDataType arry[N];    //定长数组int size;              //代表有效数据的个数
}SeqList;

但是我们得知道静态顺序表储存容量是固定的，可变性不强，如果在实际开发中内存超出了所设定的最大内存只能不断改变N的大小，从而实现对静态顺序表的扩容但这种操作是很不方便的。因此我们在实际的应用中使用动态顺序表更多

1.3.🚀构建动态顺序表

那我们就来实现动态顺序表吧😎

//顺序表的动态存储
typedef struct SeqList
{SLDataType *arry;   //指向动态开辟的数组int size;           //用于记录有效数据的个数int capicity;       //用于记录容量空间的大小
}

1.4🚀malloc函数和realloc函数的区别

使用动态开辟的顺序表存储数据，在C语言中常用malloc和realloc函数开辟动态内存。小生在此就不做阐明了，相信大神们应该都知道吧，如果想深入了解的话详见： 深入了解realloc、malloc、以及calloc函数的区别.
相信大家看到这里已经大概认识了顺序表，那我们接下来就对动态顺序表进行一些基础操作。

二.🏠顺序表的接口与相应的操作

2.1🚀顺序表的初始化

2.11🚀传值和传址

在小生看来，初始化操作是比较简单的，只需将指向数组的指针置为空，并将容量和有效数据个数置为空即可。

void SeqListInit(SeqList s)  
{s.a = NULL;    //置为空s.size = 0;    //初始化为0s.capacity = 0;//初始化为0
}

但是这种方式行不行呢？让我们来测试一下：

#include <stdio.h>
typedef int SLDataType;
typedef struct SeqList
{int* a;int size;int capacity;
}SeqList;void SeqListInit(SeqList sl)
{sl.a = NULL;sl.size = 0;sl.capacity = 0;
}
int main()
{SeqList s;SeqListInit(s);return 0;
}

编译时发现出现错误

通过调用该函数并未对该顺序表完成初始化，这是由于形参和实参的问题所致，s和sl是不同两个结构体变量，传值的过程实际上就是拷贝的过程，形参是实参的拷贝，形参的改变不影响实参。
但是我们可以指针存储地址，再对指针进行解引用的方式改变实参，由此我们可以通过传址实现初始化顺序表

//顺序表的初始化
void SeqListInit(SeqList* psl)  //用一个结构体指针psl保存顺序表的地址
{psl->a = NULL;psl->capacity = 0;psl->size = 0;
}

由此我们可以自行测试一下

 #include <stdio.h>
typedef int SLDataType;
typedef struct SeqList
{int* a;int size;int capacity;
}SeqList;void SeqListInit(SeqList* psl)  //用一个结构体指针psl保存顺序表的地址
{psl->a = NULL;psl->capacity = 0;psl->size = 0;
}
int main()
{SeqList s;SeqListInit(&s);  //传送顺序表地址return 0;
}

2.12🚀实现顺序表初始化小结

要传送顺序表的地址而非结构体，通过指针解引用的方式实现改变实参的值，最终完成初始化。

2.2🚀顺序表的尾插操作

顺序表的尾插就是在最后一个有效元素后面增加新的元素，我们通过一组图片感受一下：

我们将41尾插到顺序表的后面覆盖了随机值，顺序表的有效元素增加了1。但是我们又不得不考虑下面这种情况。

此时顺序表的最大容量和其存储的有效元素个数相等，如果要进行尾插则需对该顺序表进行扩容。

 //顺序表的尾插void SeqListPushBack(SeqList* psl, SLDataType val)
{if (psl->capacity == psl->size)  //判断该顺序表是否已满{int* tmp = realloc(psl->a, sizeof(int) * psl->capacity);   //对顺序表进行扩容，在这里我们进行一倍的扩容if (tmp == NULL)  //判断内存是否分配成功{printf("Realloc fail/n");exit(-1);}else{psl->a = tmp;  psl->capacity *= 2;}}else{psl->a[psl->size] = val;psl->size++;  //元素的有效个数加1}
}

在这里也可以进行多倍扩容，如果进行N倍扩容只需执行int* tmp = relloc(psl->a, sizeof(int) * psl->capacity*N)即可，但是在实际的情况中为了放置一次性扩容太多从而导致内存浪费，我们一般只将其扩容为原来的两倍，大家仔细看看上述的程序看能否找出bug,如果当前的顺序表为空容量和有效元素都为0呢?那用这种方式无论对它如何扩容最后得出的结果永远都是扩容后的容量还是0，那我们需要对其初始容量赋予一个确定的值。可以用如下方式实现，而且我们发现在很多操作中都需要进行一空间的判断，那我们便用一个接口实现检查顺序表的空间的检查与扩容。

2.3.🚀检查顺序表的空间并扩容

为解决上述矛盾，我们可以通过一个函数实现对顺序表是否已满的检查与适当扩容。

 void CheckCapacity(SeqList* psl)
{if (psl->capacity == psl->size)  //判断顺序表空间是否已满{int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;  //如果容量为空则将其赋值为4，否则就对他扩容一倍SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);if (tmp == NULL){printf("Relloc fail\n");exit(-1);}else{psl->a = tmp;  psl->capacity = newCapacity;}}
}

这里又牵扯到新的问题，realloc的扩容问题，使用realloc进行扩容时分为两种扩容：原地扩容和异地扩容
我们来看看这两种扩容方式

原地扩容就是保证首地址不变，在后面开辟新的地址。但是如果我们所需要的内存过大，后面的内存无法满足我们的需求呢？4这时候我们便需要用到异地扩容了

异地扩容就是开辟一块新的空间并释放原来的空间，将顺序表存放在新的空间中。
方便大家理解，我们可以通过代码实现一下：

当所需要的空间不大时，relloc采用原地扩容，此时首地址不变相当于malloc，但如果我们将10变成100呢？

由打印的首地址可以看到，首地址改变，此时relloc采用的是异地扩容。这里小生推荐大家使用一个查资料的网站: cplusplus.com.
可以用来查有关C语言和C++的资料。（尽量用英文直接看）

弄明白realloc实现扩容的原理，我们通过接口将之前的尾插函数做修改。

//尾插
void SeqListPushBack(SeqList* psl, SLDataType val)
{CheckCapacity(psl); //调用检查函数并相应进行扩容psl->a[psl->size] = val;psl->size++;
}

2.4.🚀顺序表的尾删

void SeqListPopBack(SeqList* psl)
{assert(psl);  //断言处理psl->size--;  //有效数据减1
}

顺序表有有效区域和无效区域，有效区域储存有效数据，而其他部分可以视为是分配空间时多出的空间，存储的是系统的随机值，可以认为是无效数据。我们通过一个图来认识：

由此尾删只需要将有效数据减1即可，不需要将最后一个有效数据置为0，只需让下标减1即可，如图：

2.5.🚀顺序表的头插

通过移动插入val的数据

头插的过程就是先将顺序表全部往后移为头部预留空间，挪动的过程就是从末尾开始前面的元素不断覆盖后面的元素，但是此时要考虑空间是否已满的情况。用CheckCapacity函数进行检测与扩容。

//头插void SeqListPushFront(SeqList* psl,int val)
{assert(psl);  //防止传入的是空指针CheckCapacity(psl);//挪动数据，腾出头部空间int end = psl->size - 1;while (end >= 0){psl->a[end + 1] = psl->a[end];--end;}psl->a[0] = val;psl->size++;  //有效元素个数加1}

2.6.🚀顺序表的头删

头删比头插更加简单，因为头删的时候不需要考虑顺序表内存空间已满的情况。头删的过程就是从第二个元素开始将后面的元素依次覆盖前面的元素。

void SeqListPopFront(SeqList* psl)
{assert(psl);if (psl->size > 0){//挪动数据覆盖删除int begin = 1;while (begin < psl->size){psl->a[begin - 1] = psl->a[begin];begin++;}psl->size--;}}

2.7.🚀顺序表的指定位置插入

 //在pos位置插入val
void SeqListInsert(SeqList* psl, int pos, int val)
{assert(psl);CheckCapacity(psl);int end = psl->size - 1;  //end代表最后一个有效元素的下标while (end > pos){psl->a[end + 1] = psl->a[end];end--;}psl->a[pos] = val;psl->size++;
}

在下标为pos处插入一个数据val，应该让pos左边的数据不变让其右边的数据（包括原来pos处存的数据）向右挪动一个单位。但是别忘了要对内存进行检查和扩容，调用函数即可。我们用代码来实现一下吧：

 //在pos位置插入val
void SeqListInsert(SeqList* psl, int pos, int val)
{assert(psl);CheckCapacity(psl);int end = psl->size - 1;  //end代表最后一个有效元素的下标while (end > pos){psl->a[end + 1] = psl->a[end];  //end--;}psl->a[pos] = val;psl->size++;
}

2.8.🚀顺序表的指定位置删除

将pos位置里面的元素置空，并pos后面的元素向前挪动
! 用代码实现一下整个过程：

 void SeqListErase(SeqList* psl, int pos)
{assert(psl);  //断言处理assert(pos < psl->size); int begin = pos + 1;  //begin的位置是pos的后一个位置while (begin < psl->size){psl->a[begin - 1] = psl->a[begin];  //pos后面的数据从前开始依次覆盖前面位置的数据begin++;}psl->size--;
}

2.9.🚀顺序表的销毁

销毁顺序表就是将存有数据的顺序表强制初始化。将顺序表的容量和有效数据的个数都初始化为0，将指针a置为空

void SeqListDestroy(SeqList* psl)
{psl->a = NULL;psl->capacity = 0;psl->size = 0;
}

2.10.🚀顺序表达的打印

打印顺序表我们选择从前往后依次打印。打印的时候不改变顺序表的结构和各个位置的值，因此我们有两种打印方法，第一种直接传参，但是用形参拷贝该实参的时候为新参分配了一块新的内存，占用内存较多，但是传址后用指针接收的时候只为该指针分配了四个字节的内存，节省了空间。从而在大多数的情况下我们直接传址就可以了。

void SeqListPrint(SeqList* psl)
{for (int i = 0; i < psl->size; i++){printf("%d ", psl->a[i]);}printf("\n");
}

链表

一.🏠单链表

1.🚀链表的基本概念

链表是N个数据元素的有限序列，它的长度可根据需要增长或缩短，同之前的顺序表一样，属于线性表中的一种。顺序表是顺序存储结构但链表是链式存储结构。

单链表用结点存储了数据以及下一个结点的地址，因此结点一般分为多个部分，即数据域与指针域，数据域存储有效数据，指针域存储下一个结点的地址。，同时单链表有只有一个指针域，双链表有两个指针域。

2.🚀认识单链表与顺序表的区别与优缺点

这是两种不同的存储结构，我们先谈谈区别吧，顺序表是顺序存储结构，它的特点是逻辑关系上相邻的两个元素在物理位置上也相邻。但是链表不同，链式存储结构的特点是不需要逻辑上相邻的元素在物理位置上也相邻。因为链式存储结构可以通过结点中的指针域直接找到下一个结点的位置。
顺序表的优缺点：
1.优点：可以通过下标直接访问所需要的数据
2.缺点：不能按实际所需分配内存，只能使用malloc或者realloc函数进行扩容，容易实现频繁扩容，容易导致内存浪费与数据泄露等问题。
单链表的优缺点：
1.优点：可以按照实际所需创建结点增减链表的长度，更大程度地使用内存。
2.缺点：进行尾部或者任意位置上插入或删除时时间复杂度和空间复杂度较大，每次都需要通过指针的移动找到所需要的位置，相对于顺序表查找而言效率较低。

3.🚀单链表的基本操作

我们以下所指的单链表是单向不带头非循环链表

3.1.🚀基本操作的接口（基础）

单链表和顺序表类似，增删改查是对单链表基本的操作。我们先来浏览一下基础的接口!

3.2.🚀单链表的结构定义

单链表的结点分为两部分，数据域和指针域。因此我们可以定义一个如下结构的结点

typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* pNext;
}SLTNODE;

3.3.🚀结点的创建

因为在后续的增加链表的长度，创建一个结点在某种程度上就是先创建一个该结构体指针类型变量再对进行初始化最后返回这个变量，我们可以通过代码直接分析。我们先看一下有头结点链表的创建

SLTNODE* CreateNode(SLTDataType val)
{SLTNODE* pNew = (SLTNODE*)malloc(sizeof(SLTNODE));pNew->data = val;pNew->pNext = NULL;return pNew;
}

3.4.🚀分辨传送一级指针与二级指针

如果要改变链表的头指针就传二级指针，改变头指针不能传一级指针因为传送的过程就是拷贝的过程，相当于将头指针复制了一份，形参的改变不会影响实参，因此要改变链表的头指针需要传送二级指针。

3.5.🚀单链表的插入

3.51🚀单链表的头插

因为我们前面强调过，我们进行操作的单链表是不带头结点的，因此头插就非常方便，至于带头结点的单链表如何操作，也挺简单的，相信大神们都能自己写出来吧

//因为要改变头指针所以我们要传送头指针的地址，即二级结构体指针变量void SListPushFront(SLTNODE** ppHead, SLTDataType val)
{SLTNODE* pNew  = CreateNode(val);pNew->pNext = *ppHead;*ppHead = pNew;
}

3.52🚀单链表的尾插

尾插的时候要考虑单链表是否为空的情况，因为如果为空，我们要将头指针指向新的结点。

void SListPushBack(SLTNODE** ppHead, SLTDataType val)
{SLTNODE* pNew = CreateNode(val);//判断链表是否为空，若为空则将头指针指向新结点if (*ppHead == NULL){*ppHead = pNew;}else{SLTNODE* pTail = *ppHead;//通过循环让指针找到尾部while (pTail->pNext != NULL){pTail = pTail->pNext;}pTail->pNext = pNew;}}

不知道大神们有没有注意到我们循环的条件是pTail->pNext != NULL 可不可以改为pTail != NULL呢？乍一看好像没什么问题，但是真的没有问题吗？我们要好好思考一下~~

我们先看正确的循环条件pTail->pNext != NULL

为了方便我们在图里用pHead代替*ppHead此时pTail->pNext != NULL 成立，pTail指针后移此时pTail->pNext != NULL 成立，pTail指针后移

注意，此时后面没有结点了，则此时pTail所指向的结点里面的指针域存放的是空指针，即pTail->pNext为空，pTail刚好指向最后一个结点。我们再来看看循环条件为pTail != NULL的情况

此时pTail != NULL 成立，pTail指针后移

此时pTail != NULL 依然成立，pTail指针后移

此时pTail != NULL 依然成立，pTail指针后移

从上面我们可以发现，pTail != NULL这个条件执行时，当pTail指向尾结点时也不会停止，因此该循环条件是错误的

3.53🚀单链表的指定位置插入

3.531🚀在pos位置之前插入

这里我们要分两种情况，pos是第一个结点和pos不是第一个结点，如果pos为1就相当于头插，如果pos不为1就用两个指针通过循环找到pos和pos的前一个结点。

void SListInsert(SLTNODE** ppHead, SLTNODE* pos, SLTDataType val)
{//1.pos是第一个结点，在pos之前插入相当于头插if (*ppHead == pos){SListPushFront(ppHead, val);}//2.pos不是第一个结点SLTNODE* pPrev = NULL;SLTNODE* pMove = *ppHead;while (pMove != pos){pPrev = pMove;pMove = pMove->pNext;}SLTNODE* pNew = CreateNode(val);pPrev->pNext = pNew;pNew->pNext = pos;
}

这里我们用了两个指针，我们可以通过一个指针直接实现吗？我们试一下

void SListInsert(SLTNODE** ppHead, SLTNODE* pos, SLTDataType val)
{if (*ppHead == pos){SListPushFront(ppHead, val);}SLTNODE* pPrev = *ppHead;while(pPrev->pNext != pos){pPrev = pPrev->pNext;}SLTNODE* pNew = CreateNode(SLTDataType val);pPrev->pNext = pNew;pNew->pNext = pos;SLTNODE* pNew = CreateNode(val);pPrev->pNext = pNew;pNew->pNext = pos;
}

显而易见是可以的，因为pos指针已经确定了，因此不必像之前尾插的时候找尾，只需要找到pos前一个结点就行。

3.532🚀在位置pos之后插入

单链表可以通过前一个结点找到下一个结点，不能通过后面的结点找到前面的结点。因此，在pos位置后面插入就没必要向之前在pos位置之前插入时需要通过指针的循环移动找节点了，因为通过pos可以直接找到下一个结点

 void SListInsertAfter(SLTNODE * pos, SLTDataType val)
{assert(pos);SLTNODE* pNew = CreateNode(val);pNew->pNext = pos->pNext;pos->pNext = pNew;
}

3.6.🚀单链表的删除

删除和插入在一定程度上是相似的，可以类比一下~~~

3.61🚀单链表的头删

释放原来的第一个结点，头指针移动到下一个结点>

void SListPopFront(SLTNODE** ppHead)
{assert(*pHead);SLTNODE* next =  (*ppHead)->pNext;free(*ppHead);*ppHead = next;}

3.62🚀单链表的尾删

尾部删除时要考虑三种情况，链表是否为空，链表只有一个结点和链表有多个结点

void SListPopBack(SLTNODE** ppHead)
{//1.链表为空assert(*ppHead);//2.只有一个结点if ((*ppHead)->pNext == NULL){free(*ppHead);*ppHead = NULL;}//3.有两个及以上的结点SLTNODE* pPrev = NULL;SLTNODE* pTail = *ppHead;while (pTail->pNext != NULL){pPrev = pTail;pTail = pTail->pNext;}free(pTail);pPrev->pNext = NULL;
}

3.63🚀单链表的指定位置删除

当pos等于头指针时，相当于链表的头删，我们可以直接调用之前写过的头删函数SListPopFront()

void SListErase(SLTNODE** ppHead,SLTNODE* pos)
{if (pos == *ppHead){SListPopFront(*ppHead);}else{SLTNODE* pPrev = *ppHead;while (pPrev->pNext != pos){pPrev = pPrev->pNext;}pPrev->pNext = pos->pNext;free(pPrev);}
}

3.7.🚀单链表的查找

通过指针不断移动找到数据域里面存储对应数据的结点并返回指针

SLTNODE* SListFind(SLTNODE* pHead,SLTDataType val)
{SLTNODE* pMove = pHead;while (pMove != NULL) //while(pMove){if (pMove->data == val){return pMove;}}return NULL;
}

3.8.🚀单链表的销毁

销毁操作应该是最简单了啦，小生就不罗嗦了，相信大神们一看就懂

 void SListDestroy(SLTNODE** pphead)
{SLTNODE* pMove = *pphead;while (pMove !=NULL){SLTNODE* next = pMove->pNext;free(pMove);pMove = next;}*pphead = NULL;
}

学到这里，单链表的基础操作咱们就差不多啦🥳🥳🥳接下来让我们来看双链表吧。

二.🏠双向链表

1.🚀认识双向链表的结构

单链表中每个结点分为一个数据域和一个指针域，但是双链表却有两个指针域和一个数据域，我们来看一下：

但是我们这里的是带哨兵位的双链表，因此我们可以如下用代码实现：

typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;

2🚀.双向链表的操作

2.1🚀双向链表的接口预览

其实基础操作基本差不多，我们来看看双链表的几个操作吧😎😎😎

2.2🚀双向链表结点的创建

双链表的结构有很多，我们这里选择的是带哨兵的双链表

LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}

2.3🚀双链表的打印

和单链表差不多，打印双链表的时候只需传送头指针就可以啦😎😎😎

void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n\n");
}

2.4🚀双链表的初始化

LTNode* ListInit()
{LTNode* phead = BuyLTNode(0);phead->next = phead;phead->prev = phead;return phead;
}

2.5🚀双链表的尾删

void ListPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;free(tail);tail = NULL;tailPrev->next = phead;phead->prev = tailPrev;
}

2.6🚀双链表的头插

void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead->next, x);
}

2.7🚀双链表的查找

LTNode* ListFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

2.8🚀双链表的指定位置插入

双链表的首先要开辟一个节点，由于头插和任意位置的插入都会开辟一个节点，所以我们把这个功能封装成一个函数

void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyLTNode(x);LTNode* posPrev = pos->prev;newnode->next = pos;pos->prev = newnode;posPrev->next = newnode;newnode->prev = posPrev;
}

三.🏠认识八种链表的类型

在了解链表的类型之前，我们需要了解链表的几个特点：
1.单向和双向
2.带头和不带头
3.循环和非循环
我们可以通过组合的方式，如：单向带头循环链表，双向不带头非循环链表……
小生画几个图让大家大体认识一下

1.🚀单向带头循环链表

2.🚀单向带头非循环链表

3.🚀单向不带头循环链表

4.🚀单向不带头非循环链表

5.🚀双向带头循环链表

6.🚀双向带头非循环链表

7.🚀双向不带头循环链表

8.🚀双向不带头非循环链表

小生想说的话

家人们，当你学到这里的时候，你的顺序表和链表中的单链表还有双链表就已经把基础学好啦🥳🥳🥳后续小生会将循环链表也加上，小生会不断更新优质的内容来帮助大家的。加油，初学者，加油，技术人！！！😎😎😎