目录
一、双向链表
双向链表示意图
指针永远指向内存开始的区域
二、双向链表的基本操作
1、创建双向链表
struct DouLinkList* CreateDouLinkList()
// 定义函数，返回双向链表结构体指针，用于创建双向链表头节点
{
struct DouLinkList* dl = (struct DouLinkList*) malloc(sizeof(struct DouLinkList)); // 为双向链表头节点分配内存
if(NULL == dl) // 检查内存分配是否失败
{
fprintf(stderr,"CreateDouLinkList malloc\n"); // 向标准错误输出内存分配失败信息
return NULL; // 分配失败，返回空指针
}
dl->head = NULL; // 初始化头节点的head指针为NULL，表示空链表
dl->clen = 0; // 初始化链表长度计数器为0
return dl; // 返回创建好的双向链表头节点指针
}
2、头插法插入节点
（1）图解：
第一种情况：第一个插入
第二种情况：
（2）算法实现：
int InsertHeadDouLinkList(struct DouLinkList* dl, struct DATATYPE* data)
// 定义头部插入函数，参数为链表指针和数据指针，返回操作状态（0成功，非0失败）
{
struct DouNode * newnode = (struct DouNode*)malloc(sizeof(struct DouNode)); // 为新节点分配内存
if(NULL == newnode) // 检查新节点内存分配是否失败
{
fprintf(stderr,"inserthead malloc\n"); // 输出插入节点时内存分配失败的错误信息
return 1; // 分配失败，返回错误码1
}
memcpy(&newnode->data,data,sizeof(struct DATATYPE)); // 将数据拷贝到新节点的数据域
newnode->next = NULL; // 初始化新节点的后继指针为NULL
newnode->prev = NULL; // 初始化新节点的前驱指针为NULL
newnode->next = dl->head; // 新节点的后继指向原链表头节点
if(dl->head) // 若原链表非空（存在头节点）
{
dl->head->prev = newnode; // 原头节点的前驱指向新节点
}
dl->head = newnode; // 更新链表头节点为新节点
dl->clen++; // 链表长度加1
return 0; // 插入成功，返回0
}
3、遍历打印链表
int ShowDouLinkList(struct DouLinkList* dl,DIR dir)
// 定义遍历函数，参数为链表指针和遍历方向枚举值，返回操作状态（0成功）
{
struct DouNode* tmp = dl->head; // 定义临时指针tmp，初始指向链表头节点
if(FORWADR == dir) // 若遍历方向为正向（假设FORWADR为正向枚举值）
{
while(tmp) // 正向遍历，直到tmp指向NULL（链表末尾）
{
// 输出节点数据（假设data包含姓名、性别、年龄、分数字段）
printf("%s %c %d %d\n",tmp->data.name,tmp->data.sex,tmp->data.age,tmp->data.score);
tmp = tmp->next; // tmp后移至下一个节点
}
}
else if(BACKWADR == dir) // 若遍历方向为反向（假设BACKWADR为反向枚举值）
{
while(tmp->next) // 先移动到链表尾节点（通过判断next是否为NULL）
{
tmp = tmp->next;
} // 循环结束后tmp指向尾节点
while(tmp) // 从尾节点开始反向遍历，直到tmp指向NULL（头节点的前驱）
{
// 输出节点数据（与正向相同）
printf("%s %c %d %d\n",tmp->data.name,tmp->data.sex,tmp->data.age,tmp->data.score);
tmp = tmp->prev; // tmp前移至上一个节点
}
}
return 0; // 遍历完成，返回0
}
4、判断双链表是否为空
int IsEmptyDouLinkList(struct DouLinkList* dl)
{
return 0 == dl->clen; // 若链表长度(clen)为0，返回1（真），否则返回0（假）
}
5、获取双链表长度
int GetSizeDouLinkList(struct DouLinkList* dl)
{
return dl->clen; // 直接返回链表长度(clen)
}
6、尾插法插入节点
（1）图解
第一种情况（与头插第一种情况类似）
第二种：
（2）算法实现
int InserTailDouLinkList(struct DouLinkList* dl, struct DATATYPE* data)
{
if (IsEmptyDouLinkList(dl)) // 检查链表是否为空
{
return InsertHeadDouLinkList(dl, data); // 空链表时调用头插法插入
}
else
{
struct DouNode* tmp = dl->head; // 临时指针指向头节点
while (tmp->next) // 遍历到链表最后一个节点（tmp->next为空时停止）
{
tmp = tmp->next; // 后移指针
}
struct DouNode* newnode = malloc(sizeof(struct DouNode)); // 分配新节点内存
if (newnode == NULL) // 内存分配失败
{
fprintf(stderr, "InserTailDouLinkList malloc\n"); // 输出错误信息到标准错误
return 1; // 返回错误码1
}
// 初始化新节点
memcpy(&newnode->data, data, sizeof(struct DATATYPE)); // 复制数据到新节点
newnode->next = NULL; // 新节点的next指针指向NULL（尾节点特性）
newnode->prev = NULL; // 初始化为NULL（后续会重新指向前驱节点）// 连接链表
newnode->prev = tmp; // 新节点的前驱指向最后一个节点tmp
tmp->next = newnode; // tmp的后继指向新节点dl->clen++; // 链表长度加1
}
return 0; // 插入成功，返回0
}
7、指定位置插入节点
（1）图解：
（2）算法实现：
int InserPosDouLinkList(struct DouLinkList* dl, struct DATATYPE* data, int pos)
{
int len = GetSizeDouLinkList(dl); // 获取当前链表长度
if (pos < 0 || pos > len) // 检查位置是否合法（0 ≤ pos ≤ len）
{
return 1; // 非法位置，返回错误码1
}
if (0 == pos) // 插入位置为头部（pos=0）
{
return InsertHeadDouLinkList(dl, data); // 调用头插法插入
}
else if (pos == len) // 插入位置为尾部（pos=链表长度）
{
return InserTailDouLinkList(dl, data); // 调用尾插法插入
}
else // 插入位置在中间（1 ≤ pos ≤ len-1）
{
struct DouNode* newnode = malloc(sizeof(struct DouNode)); // 分配新节点内存
if (newnode == NULL) // 内存分配失败
{
fprintf(stderr, "InserTailDouLinkList malloc\n"); // 输出错误信息
return 1; // 返回错误码1
}
// 初始化新节点
memcpy(&newnode->data, data, sizeof(struct DATATYPE)); // 复制数据到新节点
newnode->next = NULL; // 初始化为NULL（后续会重新指向后继节点）
newnode->prev = NULL; // 初始化为NULL（后续会重新指向前驱节点）struct DouNode* tmp = dl->head; // 临时指针指向头节点
int i;
for (i = 0; i < pos - 1; ++i) // 遍历到插入位置的前一个节点（pos-1处）
{
tmp = tmp->next; // 后移指针
}
// 双向链表指针重连
newnode->next = tmp->next; // 新节点的后继指向tmp的原后继
newnode->prev = tmp; // 新节点的前驱指向tmp
tmp->next->prev = newnode; // tmp原后继的前驱指向新节点
tmp->next = newnode; // tmp的后继指向新节点
}
return 0; // 插入成功，返回0
}
8、查找（按姓名查找双链表节点）
（1）算法实现：
struct DouNode* FindDouLinkList(struct DouLinkList* dl, char *name)
{if(IsEmptyDouLinkList(dl))
{
return NULL;
}
struct DouNode* tmp = dl->head; // 定义临时指针tmp，指向链表头节点
while (tmp) // 遍历链表，直到tmp为NULL（指向空节点时停止）
{
if (strcmp(tmp->data.name, name) == 0) // 比较当前节点data中的name字段与目标name
{
return tmp; // 若匹配成功，返回当前节点指针
}
tmp = tmp->next; // 移动指针到下一个节点
}
return NULL; // 遍历结束未找到匹配节点，返回NULL
}
（2）调用：
9、修改链表的指定节点
int ModifyDouLinkList(struct DouLinkList* dl, char *name, struct DATATYPE* data)
{
// 调用FindDouLinkList函数，根据name在双链表dl中查找节点
// 将找到的节点指针赋给ret，如果没找到返回NULL
struct DouNode* ret = FindDouLinkList(dl, name);
if (NULL == ret) // 判断是否找到节点
{
return 1; // 没找到节点，返回1表示修改失败
}
// 使用memcpy函数将data所指向的数据内容，复制到找到节点（ret）的数据部分
// 复制的长度为struct DATATYPE的大小
memcpy(&ret->data, data, sizeof(struct DATATYPE));
return 0; // 成功修改节点数据，返回0表示操作成功
}
10、逆序双向链表
int RevertDouLinkList(struct DouLinkList* dl) {
// 获取链表长度
int len = GetSizeDouLinkList(dl);
// 长度小于2无需反转
if (len < 2) {
return 1;
}
// 定义前驱指针（初始NULL）
struct DouNode* Prev = NULL;
// 当前节点指针（从头节点开始）
struct DouNode* Tmp = dl->head;
// 下一节点指针（保存当前节点的后继）
struct DouNode* Next = Tmp->next;
// 循环反转指针
while (1) {
// 当前节点的前驱指向原后继
Tmp->prev = Next;
// 当前节点的后继指向原前驱
Tmp->next = Prev;
// 前驱指针后移到当前节点
Prev = Tmp;
// 当前节点后移到原后继
Tmp = Next;
// 若当前节点为空，结束循环
if (NULL == Tmp) {
break;
}
// 下一节点后移（提前保存原后继的后继）
Next = Next->next;
}
// 头指针指向新的头节点（原尾节点）
dl->head = Prev;
// 返回成功标识
return 0;
}
11、删除链表指定节点
int DeleteDouLinkList(struct DouLinkList* dl, char* name) {
// 查找指定name的节点
struct DouNode* tmp = FindDouLinkList(dl, name);
// 若节点不存在，返回失败
if (NULL == tmp) {
return 1;
}
// 处理头节点情况
if (tmp == dl->head) {
// 头指针后移
dl->head = dl->head->next;
// 若新头节点存在，更新其前驱为NULL
if (dl->head) {
dl->head->prev = NULL;
}
}
// 处理尾节点情况（next为空）
else if (NULL == tmp->next) {
// 若当前节点有前驱，断开前驱与当前节点的连接
if (tmp->prev) {
tmp->prev->next = NULL;
}
// 若无前驱（说明只剩当前节点），置头指针为NULL
else {
dl->head = NULL;
}
}
// 处理中间节点情况
else {
// 若存在后继节点，更新其后继的前驱指针
if (tmp->next) tmp->next->prev = tmp->prev;
// 若存在前驱节点，更新其前驱的后继指针
if (tmp->prev) tmp->prev->next = tmp->next;
}
// 释放目标节点内存
free(tmp);
// 链表长度减一
dl->clen--;
// 返回成功标识
return 0;
}
12、销毁链表
int DestroyDouLinkList(struct DouLinkList* dl) {
// 获取头节点指针
struct DouNode* tmp = dl->head;
// 循环释放所有节点
while (tmp) {
// 头指针后移到下一个节点
dl->head = dl->head->next;
// 释放当前节点内存
free(tmp);
// tmp指向新的头节点（继续循环释放）
tmp = dl->head;
}
// 释放链表头结构自身内存
free(dl);
// 返回成功标识
return 0;
}
调用：
三、扩展：工程管理工具（makefile）
1、当三个以上的.c编译时：
（1）vi Makefile（makefile也可，推荐用首字母大写），进入下面的页面进行编写（也可在资源管理器中打开：
出现羊头标志即可）
版本一：
1、 a.out: main.c ./doulink.c // 规则1 ，生成可执行文件，其中./a.out为目标，冒号后的为依赖（输入结束回车）
2、 gcc main.c doulink.c //前面必须为Tab键空格
3、
4、clean: //可删除目标文件
5、 rm a.out
版本二：（推荐使用）
版本二示例：
（2）make （编译命令，默认只走第一条规则）
（3）./app （运行，版本一运行命令为 ./a.out）
2、扩展命令：make clean （删除中间产生的文件）。