广州网站营销推广设计,重庆森林为什么叫这个名字,无锡网络公司服务,网站引导页面文章目录一、单链表的概念及结构1.1 什么是单链表#xff1f;1.2 节点的组成1.3 单链表的特点二、单链表的实现2.1 类型定义2.2 基础工具函数1. 链表打印函数2. 节点创建函数2.3 单链表的核心操作#xff08;1#xff09;插入操作1. 尾插#xff08;SLTPushBack#xff09…
文章目录一、单链表的概念及结构1.1 什么是单链表1.2 节点的组成1.3 单链表的特点二、单链表的实现2.1 类型定义2.2 基础工具函数1. 链表打印函数2. 节点创建函数2.3 单链表的核心操作1插入操作1. 尾插SLTPushBack2. 头插SLTPushFront3. 指定位置前插入SLTInsert4. 指定位置后插入SLTInsertAfter2删除操作1. 尾删SLTPopBack2. 头删SLTPopFront3. 删除指定节点SLTErase4. 删除指定节点后的数据SLTEraseAfter3其他常用操作1. 查找SLTFind2. 销毁链表SLTDes测试代码与运行结果二级指针的使用总结三、单链表的实际应用实现通讯录3.1 数据结构设计3.2 核心功能实现1初始化通讯录2添加联系人3删除联系人4保存与销毁四、总结单链表作为数据结构中的重要成员在计算机科学领域有着广泛的应用。它凭借灵活的内存管理和高效的插入删除操作成为许多算法和系统的基础组件。一、单链表的概念及结构
1.1 什么是单链表
单链表是一种物理存储结构非连续、非顺序的线性数据结构其数据元素的逻辑顺序通过节点间的指针链接来实现。形象地说单链表的结构类似于火车车厢
每节车厢节点独立存在车厢之间通过连接装置指针关联可以灵活地增加或移除车厢节点而不影响其他部分
1.2 节点的组成
单链表的每个节点包含两个关键部分
数据域存储当前节点的数据可以是整型、字符型、自定义类型等指针域保存下一个节点的地址相当于下一节车厢的钥匙 用C语言结构体表示如下
struct SListNode {int data; // 数据域以整型为例struct SListNode* next; // 指针域指向 next 节点
};1.3 单链表的特点
逻辑连续性节点通过指针链接在逻辑上形成连续的序列物理离散性节点在内存中通常不连续存储由操作系统动态分配动态性无需预先分配固定大小的内存可根据需要动态申请和释放节点遍历性必须从表头开始通过指针依次访问后续节点无法随机访问
二、单链表的实现
2.1 类型定义
在实现操作函数前首先需要定义单链表节点的数据类型和节点结构具体如下
typedef int SLTDataType; // 定义单链表存储的数据类型此处为inttypedef struct SListNode
{SLTDataType data; // 节点存储的数据struct SListNode* next; // 指针用于保存下一个节点的地址
}SLN;这种定义方式允许我们灵活处理不同类型的数据只需修改SLTDataType的定义即可。
2.2 基础工具函数
在实现核心操作前我们需要先实现一些基础工具函数用于节点创建和链表打印。
1. 链表打印函数
void SLTPrint(SLN* phead)
{SLN* pcur phead; // 遍历指针while (pcur ! NULL){printf(%d - , pcur-data);pcur pcur-next; // 移动到下一个节点}printf(NULL\n); // 链表结束标识
}2. 节点创建函数
SLN* SLTBuyNode(SLTDataType x)
{SLN* newNode (SLN*)malloc(sizeof(SLN)); // 分配节点内存if (newNode NULL) // 内存分配失败检查{perror(malloc fail!);exit(1); // 异常退出程序}newNode-data x; // 初始化数据域newNode-next NULL; // 初始化指针域return newNode; // 返回创建的新节点
}功能创建一个新节点为其分配内存并初始化数据和指针域。使用malloc分配内存后必须检查是否分配成功。
2.3 单链表的核心操作
单链表的核心操作包括插入头插、尾插、指定位置插和删除头删、尾删、指定位置删两大类下面我们逐一解析。
1插入操作
1. 尾插SLTPushBack void SLTPushBack(SLN** pphead, SLTDataType x)
{assert(pphead); // 确保二级指针不为空SLN* newNode SLTBuyNode(x); // 创建新节点// 空链表if (*pphead NULL){*pphead newNode; // 新节点成为头节点}// 非空链表else{// 找到尾节点SLN* ptail *pphead;while (ptail-next) // 当 next不为NULL时继续移动{ptail ptail-next;}ptail-next newNode; // 尾节点指向新节点}
}为什么使用二级指针
当链表为空时我们需要修改头指针本身让它指向新节点而不是修改头指针指向的内容一级指针只能修改指向的内容二级指针才能修改指针本身
调用示例
SLN* plist NULL; // 初始化空链表
SLTPushBack(plist, 1); // 传入plist的地址
SLTPushBack(plist, 2);2. 头插SLTPushFront
创建新节点新节点的next指针指向原来的头节点更新头指针使其指向新节点 void SLTPushFront(SLN** pphead, SLTDataType x)
{assert(pphead); // 确保二级指针不为空SLN* newNode SLTBuyNode(x); // 创建新节点newNode-next *pphead; // 新节点指向原来的头节点*pphead newNode; // 新节点成为新的头节点
}3. 指定位置前插入SLTInsert
找到pos的前一个节点prev让prev的next指向新节点让新节点的next指向pos
void SLTInsert(SLN** pphead, SLN* pos, SLTDataType x)
{assert(pphead *pphead pos); // 参数合法性检查// 如果pos是头节点直接调用头插if (pos *pphead){SLTPushFront(pphead, x);}else{SLN* prev *pphead; // 用于找到pos的前一个节点SLN* newNode SLTBuyNode(x); // 创建新节点// 找到pos的前一个节点while (prev-next ! pos){prev prev-next;}// 插入新节点prev-next newNode;newNode-next pos;}
}4. 指定位置后插入SLTInsertAfter void SLTInsertAfter(SLN* pos, SLTDataType x)
{assert(pos); // 确保pos不为空SLN* newNode SLTBuyNode(x); // 创建新节点// 先连接新节点和pos的下一个节点newNode-next pos-next;// 再连接pos和新节点pos-next newNode;
}注意必须先将新节点连接到pos的下一个节点再将pos连接到新节点顺序不能颠倒。
2删除操作
1. 尾删SLTPopBack void SLTPopBack(SLN** pphead)
{// 确保二级指针和链表不为空assert(pphead *pphead);// 链表只有一个节点if ((*pphead)-next NULL){free(*pphead); // 释放头节点*pphead NULL; // 头指针置空}// 链表有多个节点的情况else{SLN* prev *pphead; // 记录尾节点的前一个节点SLN* ptail *pphead; // 用于找到尾节点// 找到尾节点while (ptail-next){prev ptail;ptail ptail-next;}free(ptail); // 释放尾节点prev-next NULL; // 前节点的next置空}
}注意
必须找到尾节点的前一个节点释放尾节点内存后要将前节点的next置空特殊处理只有一个节点的情况
2. 头删SLTPopFront void SLTPopFront(SLN** pphead)
{assert(pphead *pphead); // 不能对空指针解引用,因此pphead不能为空// 链表不能为空,因此*pphead不能为空// 保存头节点的下一个节点SLN* next (*pphead)-next;free(*pphead); // 释放头节点*pphead next; // 更新头节点
}注意不能直接释放头节点后再找下一个节点因为释放后指针就失效了必须先保存下一个节点的地址。
3. 删除指定节点SLTErase
找到pos的前一个节点prev让prev的next指向pos的next跳过pos节点释放pos节点的内存
void SLTErase(SLN** pphead, SLN* pos)
{assert(pphead *pphead pos); // 参数合法性检查// 如果pos是头节点直接调用头删if (pos *pphead){SLTPopFront(pphead);}else{SLN* prev *pphead; // 找到pos的前一个节点while (prev-next ! pos){prev prev-next;}prev-next pos-next; // 跳过pos节点free(pos); // 释放pos节点内存pos NULL; // 避免野指针}
}4. 删除指定节点后的数据SLTEraseAfter
删除指定节点pos后面的节点
void SLTEraseAfter(SLN* pos)
{assert(pos pos-next); // 确保pos和pos-next不为空SLN* del pos-next; // 要删除的节点pos-next del-next; // pos指向删除的下一节点free(del); // 释放内存del NULL; // 避免野指针
}3其他常用操作
1. 查找SLTFind
查找指定数据的节点遍历链表返回第一个数据域等于x的节点地址未找到则返回NULL。
SLN* SLTFind(SLN* phead, SLTDataType x)
{SLN* pcur phead; // 遍历指针while (pcur) // 遍历整个链表{if (pcur-data x) // 找到目标数据return pcur; // 返回节点地址pcur pcur-next; // 移动到下一个节点}return NULL; // 未找到返回NULL
}2. 销毁链表SLTDes
释放链表所有节点的内存
void SLTDes(SLN** pphead)
{assert(pphead *pphead); // 参数合法性检查SLN* pcur *pphead; // 遍历指针while (pcur){SLN* next pcur-next; // 保存下一个节点地址free(pcur); // 释放当前节点pcur next; // 移动到下一个节点}*pphead NULL; // 头指针置空避免野指针
}注意销毁链表时必须逐个释放每个节点的内存不能直接释放头节点否则会导致内存泄漏。
测试代码与运行结果
我们通过test函数测试上述所有操作
void test()
{SLN* plist NULL; // 初始化空链表// 尾插测试SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);printf(尾插后: );SLTPrint(plist); // 1 - 2 - 3 - 4 - NULL// 头插测试SLTPushFront(plist, 5);SLTPushFront(plist, 6);printf(头插后: );SLTPrint(plist); // 6 - 5 - 1 - 2 - 3 - 4 - NULL// 尾删测试SLTPopBack(plist);printf(尾删后: );SLTPrint(plist); // 6 - 5 - 1 - 2 - 3 - NULL// 头删测试SLTPopFront(plist);printf(头删后: );SLTPrint(plist); // 5 - 1 - 2 - 3 - NULL// 查找测试SLN* ret SLTFind(plist, 5);if (ret ! NULL)printf(找到了数据5的节点\n);// 指定位置前插入测试SLTInsert(plist, ret, 99);printf(指定位置前插入后: );SLTPrint(plist); // 99 - 5 - 1 - 2 - 3 - NULL// 指定位置后插入测试SLTInsertAfter(ret, 88);printf(指定位置后插入后: );SLTPrint(plist); // 99 - 5 - 88 - 1 - 2 - 3 - NULL// 删除指定节点测试SLTErase(plist, ret);printf(删除指定节点后: );SLTPrint(plist); // 99 - 88 - 1 - 2 - 3 - NULL// 删除指定节点后的数据测试SLN* ret1 SLTFind(plist, 88);SLTEraseAfter(ret1);printf(删除指定节点后的数据后: );SLTPrint(plist); // 99 - 88 - 2 - 3 - NULL// 销毁链表SLTDes(plist);printf(销毁链表后: );SLTPrint(plist); // NULL
}二级指针的使用总结
在单链表操作中是否需要使用二级指针遵循以下原则
当操作需要修改头指针的值时如头插、头删、尾插空链表、销毁链表等必须使用二级指针当操作不需要修改头指针的值时如打印、查找、指定位置后插入等使用一级指针即可
三、单链表的实际应用实现通讯录
单链表的动态性使其非常适合实现通讯录功能以下是核心实现思路
3.1 数据结构设计
// 联系人信息结构体
typedef struct PersonInfo {char name[NAME_MAX]; // 姓名char sex[SEX_MAX]; // 性别int age; // 年龄char tel[TEL_MAX]; // 电话char addr[ADDR_MAX]; // 地址
} PeoInfo;// 链表节点定义数据域为联系人信息
typedef struct SListNode {PeoInfo data; // 存储联系人信息struct SListNode* next; // 指针域
} SLTNode;
typedef struct SListNode contact; // 通讯录类型别名3.2 核心功能实现
1初始化通讯录
从本地文件加载历史数据到链表
void InitContact(contact** con) {LoadContact(con); // 从 contact.txt 读取数据
}2添加联系人
通过尾插法将新联系人插入链表
void AddContact(contact** con) {PeoInfo info;// 输入联系人信息姓名、性别、年龄等scanf(%s %s %d %s %s, info.name, info.sex, info.age, info.tel, info.addr);SLTPushBack(con, info); // 尾插操作
}3删除联系人
根据姓名查找并删除节点
void DelContact(contact** con) {char name[NAME_MAX];printf(请输入要删除的姓名);scanf(%s, name);contact* pos FindByName(*con, name); // 查找节点if (pos) {SLTErase(con, pos); // 删除节点printf(删除成功\n);}
}4保存与销毁
退出时将数据保存到文件并销毁链表
void DestroyContact(contact** con) {SaveContact(*con); // 保存数据到文件SListDestroy(con); // 销毁链表释放内存
}四、总结
单链表作为一种基础且灵活的数据结构其核心价值在于
动态内存管理无需预先分配固定大小的空间节省内存高效插入删除在已知节点位置时插入删除操作时间复杂度为 O(1)广泛的适用性作为子结构支撑哈希表、图等复杂数据结构也可直接用于实现通讯录、任务队列等应用
