企业官网建设流程全解析

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*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;// 初始化指针域returnnewNode;// 返回创建的新节点}

功能：创建一个新节点，为其分配内存并初始化数据和指针域。使用malloc分配内存后必须检查是否分配成功。

2.3 单链表的核心操作

单链表的核心操作包括插入（头插、尾插、指定位置插）和删除（头删、尾删、指定位置删）两大类，下面我们逐一解析。

（1）插入操作

1. 尾插（SLTPushBack）

voidSLTPushBack(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）

1. 创建新节点
2. 新节点的next指针指向原来的头节点
3. 更新头指针，使其指向新节点

voidSLTPushFront(SLN**pphead,SLTDataType x){assert(pphead);// 确保二级指针不为空SLN*newNode=SLTBuyNode(x);// 创建新节点newNode->next=*pphead;// 新节点指向原来的头节点*pphead=newNode;// 新节点成为新的头节点}

3. 指定位置前插入（SLTInsert）

1. 找到pos的前一个节点prev
2. 让prev的next指向新节点
3. 让新节点的next指向pos

voidSLTInsert(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）

voidSLTInsertAfter(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）

voidSLTPopBack(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）

voidSLTPopFront(SLN**pphead){assert(pphead&&*pphead);// 不能对空指针解引用,因此pphead不能为空// 链表不能为空,因此*pphead不能为空// 保存头节点的下一个节点SLN*next=(*pphead)->next;free(*pphead);// 释放头节点*pphead=next;// 更新头节点}

注意：不能直接释放头节点后再找下一个节点，因为释放后指针就失效了，必须先保存下一个节点的地址。

3. 删除指定节点（SLTErase）

1. 找到pos的前一个节点prev
2. 让prev的next指向pos的next，跳过pos节点
3. 释放pos节点的内存
   

voidSLTErase(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后面的节点：

voidSLTEraseAfter(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)// 找到目标数据returnpcur;// 返回节点地址pcur=pcur->next;// 移动到下一个节点}returnNULL;// 未找到返回NULL}

2. 销毁链表（SLTDes）

释放链表所有节点的内存：

voidSLTDes(SLN**pphead){assert(pphead&&*pphead);// 参数合法性检查SLN*pcur=*pphead;// 遍历指针while(pcur){SLN*next=pcur->next;// 保存下一个节点地址free(pcur);// 释放当前节点pcur=next;// 移动到下一个节点}*pphead=NULL;// 头指针置空，避免野指针}

注意：销毁链表时必须逐个释放每个节点的内存，不能直接释放头节点，否则会导致内存泄漏。

测试代码与运行结果

我们通过test函数测试上述所有操作：

voidtest(){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 数据结构设计

// 联系人信息结构体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*pos=FindByName(*con,name);// 查找节点if(pos){SLTErase(con,pos);// 删除节点printf("删除成功！\n");}}

（4）保存与销毁

退出时将数据保存到文件并销毁链表：

voidDestroyContact(contact**con){SaveContact(*con);// 保存数据到文件SListDestroy(con);// 销毁链表，释放内存}