阅读量:0
单链表
1. 单链表
- 单链表是一种线性的数据结构，其中的结点通过指针链接在一起。与数组不同，单链表中的结点不一定存储在连续的内存位置上。每个节点包含两部分：一是存储的数据，另一个是指针——指向列表中的下一个元素的地址。它可以动态地添加或删除元素，而不用大规模移动其他元素。
1.1 单链表的优缺点
- 单链表的优点
- 动态大小：随时添加或删除元素。
- 插入和删除操作快：不需要移动元素，只需要更新指针。
- 单链表的缺点
- 访问速度慢：要访问链表中的某个元素，需要从头开始遍历链表。
- 额外的空间开销：每个节点都需要额外的指针空间。
1.2 单链表的基本操作
- 创建空链表：初始化一个头指针指向 NULL。
- 插入节点——头插
- 插入节点——尾插
- 插入节点——指定位置之前插入
- 插入节点——指定位置之后插入
- 删除节点：——尾删
- 删除节点——头删
- 删除节点——指定位置的结点
- 删除节点——指定位置之后的结点
- 查找节点：可以在链表中查找具有特定值的节点。
- 打印链表：可以按顺序访问链表中的每个节点。
- 销毁链表：释放链表中所有节点所占的内存。
2.实现单链表的代码准备
SList.h: 头文件- 头文件包含了单链表相关的数据结构的定义和函数声明。它是公共接口，用于获取其他源文件如何使用单链表的功能等信息。同时保持代码的清晰性和可维护性。
SList.c: 实现文件- 实现文件包含了单链表功能的具体实现细节。隐藏实现细节，便于维护和更新。使头文件更加精简，只包含必要的声明，具体的实现则在 .c 文件中进行。
Test.c: 测试文件- 测试文件用于测试单链表的功能。包含主函数 main 以及一系列测试用例来验证单链表的正确性。确保测试代码不会干扰到单链表的实现，使测试变得更加独立。
3. 顺序表代码实现
在实现顺序表时需要用到的头文件：<stdio.h>,<stdlib.h>,<assert.h>
3.1 单链表结构体的定义
在SList.h中定义数据结构：
#include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLTDataType; typedef struct SListNode { SLTDataType data;//存储节点的实际数据 struct SListNode* next;//指向下一个节点的指针 }SLTNode; typedef int SLTDataType;typedef：关键字 typedef 用于定义类型别名，即为现有的类型起一个新的名字。SLTDataType;：这里定义了一个类型别名SLTDataType，它实际上就是 int 类型。
typedef struct SListNode { ... } SLTNode;struct SListNode：定义了一个SListNode的结构体类型。SLTDataType data;：结构体中包含一个data的成员，其类型为SLTDataType（即int）。struct SListNode* next;：结构体中包含一个名为next的成员，它指向SListNode类型的指针，用于连接单链表中的下一个节点。
SLTNodeSLTNode：这是typedef为struct SListNode定义的一个类型别名。
3.2 声明单链表中需要实现的功能
在SList.h中声明：
#include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; //链表的打印 void SLTPrint(SLTNode* phead); //开辟空间 SLTNode* SLTBuyNode(SLTDataType x); //头部插入删除/尾部插入删除 void SLTPushBack(SLTNode** pphead, SLTDataType x); void SLTPushFront(SLTNode** pphead, SLTDataType x); void SLTPopBack(SLTNode** pphead); void SLTPopFront(SLTNode** pphead); //查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x); //在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //删除pos节点 void SLTErase(SLTNode** pphead, SLTNode* pos); //在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x); //删除pos之后的节点 void SLTEraseAfter(SLTNode* pos); //销毁链表 void SListDesTroy(SLTNode** pphead); 3.3 单链表的打印
- 为了方便其他功能在测试时更加直观的观察，先实现单链表的打印,遍历单链表：
//链表的打印 void SLTPrint(SLTNode* phead) { SLTNode* pcur = phead; while (pcur != NULL) { printf("%d -> ", pcur->data); pcur = pcur->next; } printf("NULL\n"); } 3.4 为需要插入的数据创建新节点
- 分配内存：
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));：使用malloc函数为新节点分配内存。这里分配的内存大小为sizeof(SLTNode)，即新节点的大小。
- 检查内存分配结果：
if (newnode == NULL)：检查 malloc 函数是否成功分配内存。如果 newnode 为 NULL，说明内存分配失败。perror("malloc fail!");：如果内存分配失败，使用 perror 函数输出错误信息。
exit(1);：如果内存分配失败，使用 exit(1) 终止程序执行。1 是一个非零值，表示程序异常终止。
- 初始化新节点：
newnode->data = x;：将新节点的数据域设置为传入的参数 x。newnode->next = NULL;：将新节点的next指针设置为NULL。这表示新节点是链表的最后一个节点（如果链表为空）或新节点还没有与链表连接起来。
返回新节点：return newnode;：返回指向新节点的指针。
SLTNode* SLTBuyNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail!"); exit(1); } newnode->data = x; newnode->next = NULL; return newnode; } 3.5 单链表——头插
- 参数检查：
assert(pphead);：确保传入的指针pphead不是NULL。如果pphead是NULL，assert会断言失败，避免后续代码试图访问未初始化的指针。
- 创建新节点：
SLTNode* newnode = SLTBuyNode(x);：调用SLTBuyNode函数创建一个新的节点，并将数据 x 存储在新节点中。
- 更新新节点的 next 指针：
newnode->next = *pphead;：将新节点的next指针设置为当前链表的头结点。将新节点与原链表连接起来。
- 更新头指针：
*pphead = newnode;：更新头指针pphead，使其指向新节点。确保了pphead指向链表的新头结点。
//头插 void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = SLTBuyNode(x);//为头插申请空间 newnode->next = *pphead;//将新数据与原来头节点联系起来 *pphead = newnode;//保证指针pphead里面始终指向头节点 } 3.6 单链表——头删
- 参数检查：
assert(pphead && *pphead)：保证传入的指针pphead不是NULL，并且pphead指向的链表头结点也不为NULL。如果pphead或者*pphead是NULL，assert会断言失败，避免后续代码试图访问未初始化的指针或删除空节点。 - 保存下一个节点的指针：
SLTNode* next = (*pphead)->next;：获取当前链表头结点的下一个节点的指针。在删除头结点之后，将头指针更新为下一个节点。 - 释放头结点占用的内存：
free(*pphead);：释放当前链表头结点占用的内存。确保资源的有效回收，避免内存泄漏。 - 更新头指针：
*pphead = next;：更新头指针pphead，使其指向下一个节点。如果链表中只有一个节点，那么next为NULL，这将使pphead也指向NULL，表示链表为空。
//头删 void SLTPopFront(SLTNode** pphead) { assert(pphead && *pphead); SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; } 3.7 单链表——尾插
- 参数检查：
assert(pphead);：保证传入的指针pphead不是NULL。如果pphead是NULL，assert会断言失败，避免后续代码试图访问未初始化的指针。 - 创建新节点：
SLTNode* newnode = SLTBuyNode(x);：调用SLTBuyNode函数创建一个新的节点，并将数据 x 存储在新节点中。SLTBuyNode函数为新节点分配内存，并初始化节点。 - 处理空链表的情况：
if (*pphead == NULL)：检查链表是否为空。如果是空链表，则直接将新节点设置为头结点。*pphead = newnode;：将新节点设置为头结点，此时链表中只有一个节点。 - 处理非空链表的情况：
SLTNode* ptail = *pphead;：定义一个指针ptail，初始化为链表的头结点。while (ptail->next != NULL)：遍历链表直到找到最后一个节点。ptail = ptail->next;：移动ptail指针到下一个节点。ptail->next = newnode;：将新节点连接到链表的末尾。
//链表的尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = SLTBuyNode(x); //空链表和非空链表两种情况 if (*pphead == NULL) { *pphead = newnode; } else { SLTNode* ptail = *pphead; //找尾 while (ptail->next != NULL) { ptail = ptail->next; } ptail->next = newnode; } } 3.8 单链表——尾删
- 参数检查：
assert(pphead && *pphead);：确保传入的指针pphead不是NULL，并且pphead指向的链表头结点也不为NULL。如果pphead或者*pphead是NULL，assert会断言失败，避免后续代码试图访问未初始化的指针或删除空节点。
- 处理空链表的情况：
if (*pphead == NULL)：检查链表是否为空。如果链表为空，那么*pphead保持为NULL，表示链表仍然为空。*pphead = NULL;：如果链表已经为空，那么再次设置*pphead为NULL
- 处理非空链表的情况：
SLTNode* ptail = *pphead;：定义一个指针ptail，初始化为链表的头结点。SLTNode* prev = *pphead;：定义另一个指针prev，初始化为链表的头结点。prev用于记录最后一个节点的前一个节点。while (ptail->next != NULL)：遍历链表直到找到最后一个节点。prev = ptail;：移动prev指针到下一个节点。ptail = ptail->next;：移动 ptail 指针到下一个节点。free(ptail);：释放最后一个节点占用的内存。ptail = NULL;：将ptail设置为NULL，以避免悬空指针。prev->next = NULL;：将最后一个节点的前一个节点的next指针设置为NULL，切断与最后一个节点的链接。
//尾删 void SLTPopBack(SLTNode** pphead) { assert(pphead && *pphead); if ((*pphead) == NULL) { *pphead = NULL; } else { SLTNode* ptail = *pphead; SLTNode* prev = *pphead; while (ptail->next != NULL) { prev = ptail; ptail = ptail->next; } free(ptail); ptail = NULL; prev->next = NULL; } } 3.9 单链表 ——查找
- 初始化指针：
SLTNode* pcur = phead;：定义一个指针pcur，初始化为链表的头结点。
- 遍历链表：
while (pcur)：遍历链表，只要pcur不为NULL（即还有节点未遍历），就继续循环。
- 检查节点数据：
if (pcur->data == x)：检查当前节点是否等于查找的目标值 x。return pcur;：如果找到了匹配的节点，立即返回该节点的指针。
- 移动指针：
pcur = pcur->next;：如果没有找到匹配的节点，则将pcur指针移动到下一个节点，继续搜索。
- 返回结果：
- 如果遍历完整个链表都没有找到匹配的节点，则返回
NULL。
- 如果遍历完整个链表都没有找到匹配的节点，则返回
//查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* pcur = phead; while (pcur) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; } 3.10 在指定位置之前插入
- 参数检查：
- assert(pphead && *pphead);：确保传入的指针
pphead不是NULL，并且pphead指向的链表头结点也不为NULL。如果pphead或者*pphead是NULL，assert会断言失败,避免后续代码试图访问未初始化的指针。 - assert(pos);：确保
pos参数不是NULL，pos指向链表中的一个有效节点。
- assert(pphead && *pphead);：确保传入的指针
- 创建新节点：
- SLTNode* newnode = SLTBuyNode(x);：调用
SLTBuyNode函数创建一个新的节点，并将数据x存储在新节点中。
- SLTNode* newnode = SLTBuyNode(x);：调用
- 处理头插的情况：
- if (pos == *pphead)：如果
pos指向的是链表的头结点，那么这实际上是一个头插操作。 - SLTPushFront(pphead, x);：调用
SLTPushFront函数执行头插操作。
- if (pos == *pphead)：如果
- 处理非头插的情况：
- SLTNode* prev = *pphead;：定义一个指针
prev，初始化为链表的头结点。 - while (prev->next != pos)：遍历链表，直到找到
pos的前一个节点。 - prev = prev->next;：移动
prev指针到下一个节点。 - newnode->next = pos;：将新节点的
next指针设置为pos。 - prev->next = newnode;：将
pos的前一个节点的next指针设置为新节点。
- SLTNode* prev = *pphead;：定义一个指针
//指定位置插入之前数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead && *pphead); assert(pos); SLTNode* newnode = SLTBuyNode(x); //若pos == *pphead,说明头插，可以直接调用头插函数 if (pos == *pphead) { SLTPushFront(pphead, x); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } newnode->next = pos; prev->next = newnode; } } 3.11 在指定位置之后插入
- 参数检查：
assert(pos);：确保 pos 不是 NULL。 - 创建新节点：
SLTNode* newnode = SLTBuyNode(x);：调用 SLTBuyNode 函数创建一个新的节点，并将数据 x 存储在新节点中。 - 更新新节点的 next 指针：
newnode->next = pos->next;：将新节点的 next 指针设置为 pos 节点的下一个节点。将新节点与原链表连接起来。 - 更新 pos 节点的 next 指针：
pos->next = newnode;：将 pos 节点的 next 指针设置为新节点。将 pos 节点与新节点连接起来。
//在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = SLTBuyNode(x); newnode->next = pos->next; pos->next = newnode; } 3.12 在指定位置之前插入
- 参数检查：确保
pphead和*pphead都不是NULL，并且pos也不是NULL。 - 创建新节点：使用
SLTBuyNode函数创建新节点，并设置新节点的数据域。 - 处理头插的情况：如果
pos指向的是头结点，直接调用头插函数。 - 处理非头插的情况：
- 遍历链表找到
pos的前一个节点。 - 将新节点的
next指针设置为pos。 - 将
pos的前一个节点的next指针设置为新节点。
- 遍历链表找到
//指定位置插入之前数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead && *pphead); assert(pos); SLTNode* newnode = SLTBuyNode(x); //若pos == *pphead,说明头插，可以直接调用头插函数 if (pos == *pphead) { SLTPushFront(pphead, x); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } newnode->next = pos; prev->next = newnode; } } 3.13 删除指定位置pos节点
1.参数检查：确保 pphead 和 *pphead 都不是 NULL，并且 pos 也不是 NULL。
2. 处理头节点删除的情况：如果 pos 指向的是头结点，直接调用头删函数。
3. 处理非头节点删除的情况：
- 遍历链表找到
pos的前一个节点。 - 修改
pos的前一个节点的next指针，跳过pos。 - 释放
pos节点占用的内存，并将pos设置为NULL。
void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead && *pphead); assert(pos); if (pos == *pphead)//pos是头节点 { SLTPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } } 3.14 删除指定节点pos之后的节点
- 参数检查：确保
pos和pos->next都不是NULL。 - 保存要删除的节点：使用
del指针指向要删除的节点。 - 修改
pos节点的next指针：将pos节点的next指针设置为del节点的下一个节点。 - 释放
del节点占用的内存：释放del节点占用的内存。 - 将
del设置为NULL：将 del 设置为NULL，避免悬空指针。
//删除pos之后的结点 void SLTEraseAfter(SLTNode* pos) { assert(pos && pos->next); SLTNode* del = pos->next; pos->next = del->next; free(del); del = NULL; } 3.15 销毁链表
- 参数检查：确保
pphead和*pphead都不是NULL。 - 遍历链表并释放内存：
- 使用
pcur指针遍历链表。 - 保存当前节点的下一个节点的指针。
- 释放当前节点占用的内存。
- 移动
pcur指针到下一个节点。
- 使用
- 设置头指针为
NULL：遍历完成后，将头指针设置为NULL。
//销毁链表 void SListDesTroy(SLTNode** pphead) { assert(pphead && *pphead); SLTNode* pcur = *pphead; while (pcur) { SLTNode* next = pcur->next; free(pcur); pcur = next; } *pphead = NULL; } 4.完整代码
SList.h:
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; //链表的打印 void SLTPrint(SLTNode* phead); //开辟空间 SLTNode* SLTBuyNode(SLTDataType x); //头部插入删除/尾部插入删除 void SLTPushBack(SLTNode** pphead, SLTDataType x); void SLTPushFront(SLTNode** pphead, SLTDataType x); void SLTPopBack(SLTNode** pphead); void SLTPopFront(SLTNode** pphead); //查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x); //在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //删除pos节点 void SLTErase(SLTNode** pphead, SLTNode* pos); //在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x); //删除pos之后的节点 void SLTEraseAfter(SLTNode* pos); //销毁链表 void SListDesTroy(SLTNode** pphead); SList.c:
#pragma once #include "SList.h" //链表的打印 void SLTPrint(SLTNode* phead) { SLTNode* pcur = phead; while (pcur != NULL) { printf("%d -> ", pcur->data); pcur = pcur->next; } printf("NULL\n"); } //开辟空间 SLTNode* SLTBuyNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail!"); exit(1); } newnode->data = x; newnode->next = NULL; return newnode; } //链表的尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = SLTBuyNode(x); //空链表和非空链表两种情况 if (*pphead == NULL) { *pphead = newnode; } else { SLTNode* ptail = *pphead; //找尾 while (ptail->next != NULL) { ptail = ptail->next; } ptail->next = newnode; } } //头插 void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = SLTBuyNode(x);//为头插申请空间 newnode->next = *pphead;//将新数据与原来头节点联系起来 *pphead = newnode;//保证指针pphead里面始终指向头节点 } //尾删 void SLTPopBack(SLTNode** pphead) { assert(pphead && *pphead); if ((*pphead) == NULL) { *pphead = NULL; } else { SLTNode* ptail = *pphead; SLTNode* prev = *pphead; while (ptail->next != NULL) { prev = ptail; ptail = ptail->next; } free(ptail); ptail = NULL; prev->next = NULL; } } //头删 void SLTPopFront(SLTNode** pphead) { assert(pphead && *pphead); SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; } //查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* pcur = phead; while (pcur) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; } //指定位置插入之前数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead && *pphead); assert(pos); SLTNode* newnode = SLTBuyNode(x); //若pos == *pphead,说明头插，可以直接调用头插函数 if (pos == *pphead) { SLTPushFront(pphead, x); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } newnode->next = pos; prev->next = newnode; } } //在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = SLTBuyNode(x); newnode->next = pos->next; pos->next = newnode; } //删除pos结点 void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead && *pphead); assert(pos); if (pos == *pphead)//pos是头节点 { SLTPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } } //删除pos之后的结点 void SLTEraseAfter(SLTNode* pos) { assert(pos && pos->next); SLTNode* del = pos->next; pos->next = del->next; free(del); del = NULL; } //销毁链表 void SListDesTroy(SLTNode** pphead) { assert(pphead && *pphead); SLTNode* pcur = *pphead; while (pcur) { SLTNode* next = pcur->next; free(pcur); pcur = next; } *pphead = NULL; } Test.c:
#define _CRT_SECURE_NO_WARNINGS 1 #include "SList.h" void SListTest() { //测试尾插 SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 3); SLTPushBack(&plist, 1); SLTPushBack(&plist, 4); SLTPrint(plist); SLTPushBack(&plist, 5); SLTPushBack(&plist, 2); SLTPushBack(&plist, 0); SLTPrint(plist); //测试头插 SLTPushFront(&plist, 0); SLTPushFront(&plist, 2); SLTPushFront(&plist, 5); SLTPrint(plist); //测试尾删 SLTPopBack(&plist); SLTPopBack(&plist); SLTPopBack(&plist); SLTPrint(plist); //测试头删 SLTPopFront(&plist); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); //测试查找 SLTNode* find = SLTFind(plist, 3); if (find == NULL) { printf("没有找到！\n"); } else { printf("找到了！\n"); } //测试指定位置之前插入数据 /*SLTNode* find = SLTFind(plist, 3);*/ SLTInsert(&plist, find, 520); SLTPrint(plist); //测试指定位置之后插入数据 SLTInsertAfter(find,1314); SLTPrint(plist); 测试删除pos结点 //SLTErase(&plist, find); //SLTPrint(plist); //测试删除pos之后结点 SLTEraseAfter(find); SLTPrint(plist); //销毁链表 SListDesTroy(&plist); SLTPrint(plist); } int main() { SListTest(); return 0; } 