【初阶数据结构与算法】初阶数据结构总结之顺序表、单链表、双链表、栈、队列、二叉树顺序结构堆、二叉树链式结构（附源码）

文章目录

• 一、顺序表
• 二、单链表
• 三、双链表
• 四、栈(先进后出)
• 五、队列
• 六、二叉树链式结构---堆
• 七、二叉树链式结构接口实现

   在之前我们学习了大部分初阶数据结构，我们现在从特点、优缺点以及应用场景大致总结一下，放出源码，如果想要看具体分析请移步本人前面的文章

一、顺序表

1. 顺序表的特点：顺序表（也称作线性表）是一种线性数据结构，其特点主要包括：
   （1）元素连续存储：顺序表的元素在内存中连续存储，每个元素都占有一个固定的位置，并且可以通过索引直接访问。
   （2）随机访问：由于元素连续存储，顺序表支持随机访问，即可以在常数时间内访问任意位置的元素。
   （3）存储密度高：顺序表不需要额外的指针或引用信息来存储元素之间的关系，因此存储密度较高，内存利用率较好。
   （4）物理顺序与逻辑顺序一致：顺序表中元素的物理存储顺序与其逻辑顺序一致，即元素在内存中的排列顺序与它们在顺序表中的顺序相同。
2. 顺序表的优点
   （1）访问速度快：由于支持随机访问，顺序表可以在常数时间内访问任意位置的元素，这使得顺序表在需要频繁访问元素的场景中表现出色。
   （2）易于实现：顺序表可以使用简单的数组来实现，因此其实现相对简单，易于理解和操作。
   （3）空间利用率高：顺序表不需要额外的指针或引用信息，因此其空间利用率较高，可以节省内存资源。
3. 顺序表的缺点
   （1）插入和删除操作慢：在顺序表中插入或删除元素时，需要移动其他元素的位置以保持元素的连续性。这导致插入和删除操作的时间复杂度较高，通常为O(n)，其中n是元素的数量。
   （2）静态顺序表的灵活性不高，动态顺序表则需要动态申请空间，会有一定消耗
4. 顺序表的应用场景
   （1）需要频繁访问元素的场景：由于顺序表支持随机访问，因此在需要频繁访问元素的场景中表现出色。例如，在实现查找算法时，顺序表可以高效地定位目标元素。
   （2）元素数量相对固定的场景：顺序表适用于元素数量相对固定的场景。如果元素数量频繁变化，则可能需要频繁地进行扩容或缩容操作，这会影响性能。
   （3）需要存储连续数据的场景：顺序表适用于需要存储连续数据的场景。例如，在图像处理、音频处理等地方中，通常需要处理连续的数据块，此时顺序表是一个合适的选择。
   （4）实现简单的数据结构：顺序表可以作为实现其他简单数据结构的基础。例如，可以使用顺序表来实现栈、队列等数据结构，这些数据结构在算法和数据结构中具有广泛的应用。
5. 顺序表源码：

#include #include #include #include typedef int type;typedef struct SL{ type* arr;int size;int capacity;}SL;#include \"SeqList.h\"//初始化void SLInit(SL* ps){ ps->arr = NULL;ps->size = ps->capacity = 0;}//销毁void SLDestroy(SL* ps){ if (ps->arr)free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;}//如果空间不够，进行扩容void SLcheckCapacity(SL* ps){ if (ps->capacity == ps->size){ ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;type* tmp = (type*)realloc(ps->arr, ps->capacity * sizeof(type));if (tmp == NULL){ perror(\"realloc\");exit(1);}ps->arr = tmp;tmp = NULL;}}//打印void SLPrint(SL* ps){ for (int i = 0; i < ps->size; i++){ printf(\"%d \", ps->arr[i]);}printf(\"\\n\");}//尾插void SLPushBack(SL* ps, type x){ assert(ps);SLcheckCapacity(ps);ps->arr[ps->size++] = x;}//头插void SLPushFront(SL* ps,type x){ assert(ps);SLcheckCapacity(ps);memcpy(ps->arr + 1, ps->arr, ps->size * sizeof(type));ps->arr[0] = x;ps->size++;}//尾删void SLPopBack(SL* ps){ assert(ps);assert(ps->size);ps->size--;}//头删void SLPopFront(SL* ps){ assert(ps);assert(ps->size);memmove(ps->arr, ps->arr + 1, --ps->size * sizeof(type));}//指定位置前插入数据void SLInsert(SL* ps, int pos, type x){ assert(ps);assert(pos >=0 && pos <= ps->size);memmove(ps->arr + pos + 1, ps->arr + pos, (ps->size - pos) * sizeof(type));ps->arr[pos] = x;ps->size++;}int SLFind(SL* ps, type x){ assert(ps);assert(ps->size);for (int i = 0; i < ps->size; i++){ if (ps->arr[i] == x)return i;}return -1;}//删除指定位置的数据void SLErase(SL* ps, int pos){ assert(ps);assert(ps->size);assert(pos >= 0 && pos <= ps->size);memmove(ps->arr + pos, ps->arr + pos + 1, (ps->size - pos - 1) * sizeof(type));ps->size--;}

二、单链表

1. 单链表的特点：单链表是一种线性数据结构，其特点主要体现在以下几个方面：
   （1）节点分散存储：单链表的节点在内存中不是连续存储的，每个节点包含数据域和指针域（或称为链域），指针域存储着下一个节点的地址。
   （2）链式存储结构：通过指针将各个节点连接起来，形成一条链式的存储结构。这种结构使得单链表在插入和删除节点时不需要移动其他节点的位置。
   （3）头指针唯一：单链表通常有一个头指针（或称为头节点），它指向链表的第一个节点（如果链表不为空）。头指针是链表的唯一入口。
   （4）节点访问需从头开始：由于节点在内存中不是连续存储的，因此不能通过索引直接访问任意位置的节点。需要从头指针开始，依次遍历链表，直到找到目标节点。

2. 单链表的优点
   （1）插入和删除操作灵活：在单链表中插入或删除节点时，只需要修改相邻节点的指针域，而不需要移动其他节点的位置。这使得单链表在插入和删除操作方面具有较高的灵活性。
   （2）动态调整大小：单链表不需要预先分配固定大小的存储空间，可以根据需要动态地增加或减少节点，从而适应不同规模的数据集合。
   （3）节省空间：对于稀疏的数据集合，单链表可以节省空间。因为不需要像数组那样为未使用的元素分配存储空间。

3. 单链表的缺点
   （1）访问速度慢：由于节点在内存中不是连续存储的，因此不能通过索引直接访问任意位置的节点。需要从头指针开始依次遍历链表，直到找到目标节点。这使得单链表在访问速度方面相对较慢。
   （2）需要额外的存储空间：每个节点都需要一个指针域来存储下一个节点的地址，这增加了额外的存储空间开销。
   （3）容易出现内存泄漏：在使用单链表时，需要小心管理节点的内存分配和释放。如果忘记释放已删除的节点所占用的内存，可能会导致内存泄漏问题。

4. 单链表的应用场景
   （1）需要频繁插入和删除操作的场景：由于单链表在插入和删除操作方面具有较高的灵活性，因此适用于需要频繁插入和删除操作的场景。例如，在实现动态数据结构（如动态数组、栈、队列等）时，可以考虑使用单链表。
   （2）元素数量不确定的场景：单链表可以根据需要动态地增加或减少节点，从而适应不同规模的数据集合。因此，适用于元素数量不确定的场景。
   （3）需要节省空间的场景：对于稀疏的数据集合，单链表可以节省空间。因为不需要为未使用的元素分配存储空间。例如，在实现稀疏矩阵时，可以考虑使用单链表来存储非零元素及其位置信息。
   （4）实现复杂数据结构：单链表可以作为实现其他复杂数据结构的基础。例如，可以使用单链表来实现图、树等数据结构中的节点和边

5. 源码：

#include #include #include typedef int SLTDateType;typedef struct SListNode{ SLTDateType data;struct SListNode* next;}SLTNode;//链表的打印void SLTPrint(SLTNode** pphead){ assert(pphead);SLTNode* pcur = *pphead;while (pcur){ printf(\"%d -> \", pcur->data);pcur = pcur->next;}printf(\"NULL\\n\");}//申请新节点SLTNode* SLTBuyNode(SLTDateType x){ SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));newnode->data = x;newnode->next = NULL;return newnode;}//链表的头插void SLTPushFront(SLTNode** pphead, SLTDateType x){ assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;}//链表的尾插void SLTPushBack(SLTNode** pphead, SLTDateType x){ assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){ *pphead = newnode;return;}SLTNode* pcur = *pphead;while (pcur->next){ pcur = pcur->next