【数据结构】单链表（C）

depth: 3 title: 目录一、单链表的概念及结构1.1 什么是单链表单链表是一种物理存储结构非连续、非顺序的线性数据结构其数据元素的逻辑顺序通过节点间的指针链接来实现。形象地说单链表的结构类似于火车车厢每节车厢节点独立存在车厢之间通过连接装置指针关联可以灵活地增加或移除车厢节点而不影响其他部分1.2 节点的组成单链表的每个节点包含两个关键部分数据域存储当前节点的数据可以是整型、字符型、自定义类型等指针域保存下一个节点的地址相当于下一节车厢的钥匙用C语言结构体表示如下structSListNode{intdata;// 数据域以整型为例structSListNode*next;// 指针域指向 next 节点};1.3 单链表的特点逻辑连续性节点通过指针链接在逻辑上形成连续的序列物理离散性节点在内存中通常不连续存储由操作系统动态分配动态性无需预先分配固定大小的内存可根据需要动态申请和释放节点遍历性必须从表头开始通过指针依次访问后续节点无法随机访问二、单链表的实现2.1 类型定义在实现操作函数前首先需要定义单链表节点的数据类型和节点结构具体如下typedefintSLTDataType;// 定义单链表存储的数据类型此处为inttypedefstructSListNode{SLTDataType data;// 节点存储的数据structSListNode*next;// 指针用于保存下一个节点的地址}SLN;这种定义方式允许我们灵活处理不同类型的数据只需修改SLTDataType的定义即可。2.2 基础工具函数在实现核心操作前我们需要先实现一些基础工具函数用于节点创建和链表打印。1. 链表打印函数voidSLTPrint(SLN*phead){SLN*pcurphead;// 遍历指针while(pcur!NULL){printf(%d - ,pcur-data);pcurpcur-next;// 移动到下一个节点}printf(NULL\n);// 链表结束标识}2. 节点创建函数SLN*SLTBuyNode(SLTDataType x){SLN*newNode(SLN*)malloc(sizeof(SLN));// 分配节点内存if(newNodeNULL)// 内存分配失败检查{perror(malloc fail!);exit(1);// 异常退出程序}newNode-datax;// 初始化数据域newNode-nextNULL;// 初始化指针域returnnewNode;// 返回创建的新节点}功能创建一个新节点为其分配内存并初始化数据和指针域。使用malloc分配内存后必须检查是否分配成功。2.3 单链表的核心操作单链表的核心操作包括插入头插、尾插、指定位置插和删除头删、尾删、指定位置删两大类下面我们逐一解析。1插入操作1. 尾插SLTPushBackvoidSLTPushBack(SLN**pphead,SLTDataType x){assert(pphead);// 确保二级指针不为空SLN*newNodeSLTBuyNode(x);// 创建新节点// 空链表if(*ppheadNULL){*ppheadnewNode;// 新节点成为头节点}// 非空链表else{// 找到尾节点SLN*ptail*pphead;while(ptail-next)// 当 next不为NULL时继续移动{ptailptail-next;}ptail-nextnewNode;// 尾节点指向新节点}}为什么使用二级指针当链表为空时我们需要修改头指针本身让它指向新节点而不是修改头指针指向的内容一级指针只能修改指向的内容二级指针才能修改指针本身调用示例SLN*plistNULL;// 初始化空链表SLTPushBack(plist,1);// 传入plist的地址SLTPushBack(plist,2);2. 头插SLTPushFront创建新节点新节点的next指针指向原来的头节点更新头指针使其指向新节点voidSLTPushFront(SLN**pphead,SLTDataType x){assert(pphead);// 确保二级指针不为空SLN*newNodeSLTBuyNode(x);// 创建新节点newNode-next*pphead;// 新节点指向原来的头节点*ppheadnewNode;// 新节点成为新的头节点}3. 指定位置前插入SLTInsert找到pos的前一个节点prev让prev的next指向新节点让新节点的next指向posvoidSLTInsert(SLN**pphead,SLN*pos,SLTDataType x){assert(pphead*ppheadpos);// 参数合法性检查// 如果pos是头节点直接调用头插if(pos*pphead){SLTPushFront(pphead,x);}else{SLN*prev*pphead;// 用于找到pos的前一个节点SLN*newNodeSLTBuyNode(x);// 创建新节点// 找到pos的前一个节点while(prev-next!pos){prevprev-next;}// 插入新节点prev-nextnewNode;newNode-nextpos;}}4. 指定位置后插入SLTInsertAftervoidSLTInsertAfter(SLN*pos,SLTDataType x){assert(pos);// 确保pos不为空SLN*newNodeSLTBuyNode(x);// 创建新节点// 先连接新节点和pos的下一个节点newNode-nextpos-next;// 再连接pos和新节点pos-nextnewNode;}注意必须先将新节点连接到pos的下一个节点再将pos连接到新节点顺序不能颠倒。2删除操作1. 尾删SLTPopBackvoidSLTPopBack(SLN**pphead){// 确保二级指针和链表不为空assert(pphead*pphead);// 链表只有一个节点if((*pphead)-nextNULL){free(*pphead);// 释放头节点*ppheadNULL;// 头指针置空}// 链表有多个节点的情况else{SLN*prev*pphead;// 记录尾节点的前一个节点SLN*ptail*pphead;// 用于找到尾节点// 找到尾节点while(ptail-next){prevptail;ptailptail-next;}free(ptail);// 释放尾节点prev-nextNULL;// 前节点的next置空}}注意必须找到尾节点的前一个节点释放尾节点内存后要将前节点的next置空特殊处理只有一个节点的情况2. 头删SLTPopFrontvoidSLTPopFront(SLN**pphead){assert(pphead*pphead);// 不能对空指针解引用,因此pphead不能为空// 链表不能为空,因此*pphead不能为空// 保存头节点的下一个节点SLN*next(*pphead)-next;free(*pphead);// 释放头节点*ppheadnext;// 更新头节点}注意不能直接释放头节点后再找下一个节点因为释放后指针就失效了必须先保存下一个节点的地址。3. 删除指定节点SLTErase找到pos的前一个节点prev让prev的next指向pos的next跳过pos节点释放pos节点的内存voidSLTErase(SLN**pphead,SLN*pos){assert(pphead*ppheadpos);// 参数合法性检查// 如果pos是头节点直接调用头删if(pos*pphead){SLTPopFront(pphead);}else{SLN*prev*pphead;// 找到pos的前一个节点while(prev-next!pos){prevprev-next;}prev-nextpos-next;// 跳过pos节点free(pos);// 释放pos节点内存posNULL;// 避免野指针}}4. 删除指定节点后的数据SLTEraseAfter删除指定节点pos后面的节点voidSLTEraseAfter(SLN*pos){assert(pospos-next);// 确保pos和pos-next不为空SLN*delpos-next;// 要删除的节点pos-nextdel-next;// pos指向删除的下一节点free(del);// 释放内存delNULL;// 避免野指针}3其他常用操作1. 查找SLTFind查找指定数据的节点遍历链表返回第一个数据域等于x的节点地址未找到则返回NULL。SLN*SLTFind(SLN*phead,SLTDataType x){SLN*pcurphead;// 遍历指针while(pcur)// 遍历整个链表{if(pcur-datax)// 找到目标数据returnpcur;// 返回节点地址pcurpcur-next;// 移动到下一个节点}returnNULL;// 未找到返回NULL}2. 销毁链表SLTDes释放链表所有节点的内存voidSLTDes(SLN**pphead){assert(pphead*pphead);// 参数合法性检查SLN*pcur*pphead;// 遍历指针while(pcur){SLN*nextpcur-next;// 保存下一个节点地址free(pcur);// 释放当前节点pcurnext;// 移动到下一个节点}*ppheadNULL;// 头指针置空避免野指针}注意销毁链表时必须逐个释放每个节点的内存不能直接释放头节点否则会导致内存泄漏。测试代码与运行结果我们通过test函数测试上述所有操作voidtest(){SLN*plistNULL;// 初始化空链表// 尾插测试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*retSLTFind(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*ret1SLTFind(plist,88);SLTEraseAfter(ret1);printf(删除指定节点后的数据后: );SLTPrint(plist);// 99 - 88 - 2 - 3 - NULL// 销毁链表SLTDes(plist);printf(销毁链表后: );SLTPrint(plist);// NULL}二级指针的使用总结在单链表操作中是否需要使用二级指针遵循以下原则当操作需要修改头指针的值时如头插、头删、尾插空链表、销毁链表等必须使用二级指针当操作不需要修改头指针的值时如打印、查找、指定位置后插入等使用一级指针即可三、单链表的应用通讯录3.1 数据结构设计// 联系人信息结构体typedefstructPersonInfo{charname[NAME_MAX];// 姓名charsex[SEX_MAX];// 性别intage;// 年龄chartel[TEL_MAX];// 电话charaddr[ADDR_MAX];// 地址}PeoInfo;// 链表节点定义数据域为联系人信息typedefstructSListNode{PeoInfo data;// 存储联系人信息structSListNode*next;// 指针域}SLTNode;typedefstructSListNodecontact;// 通讯录类型别名3.2 核心功能实现1初始化通讯录从本地文件加载历史数据到链表voidInitContact(contact**con){LoadContact(con);// 从 contact.txt 读取数据}2添加联系人通过尾插法将新联系人插入链表voidAddContact(contact**con){PeoInfo info;// 输入联系人信息姓名、性别、年龄等scanf(%s %s %d %s %s,info.name,info.sex,info.age,info.tel,info.addr);SLTPushBack(con,info);// 尾插操作}3删除联系人根据姓名查找并删除节点voidDelContact(contact**con){charname[NAME_MAX];printf(请输入要删除的姓名);scanf(%s,name);contact*posFindByName(*con,name);// 查找节点if(pos){SLTErase(con,pos);// 删除节点printf(删除成功\n);}}4保存与销毁退出时将数据保存到文件并销毁链表voidDestroyContact(contact**con){SaveContact(*con);// 保存数据到文件SListDestroy(con);// 销毁链表释放内存}