当前位置：首页 > news >正文

链表最终章——双向链表及其应用

news 2025/6/28 7:49:17

———————————本文旨在交流探讨计算机知识，欢迎交流指正————————————

上一章，我们介绍了链表的循环扩展，但是，单向链表毕竟是单向查询的，就算是经过循环来查找，终究是效率偏低，下面，我们来介绍一种工程项目中运用更加广泛的一种链表结构：双向链表——：

根据此结构，我们可以发现，虽然代码复杂度增加了，但是由于此结构是双向的，操作更加便捷，下面，我将演示各模块内容：

首先，是结构的构建：

typedef int Element;
typedef struct _node {Element val;struct _node *next;struct _node *prev;
} DNode, DList;/* 使用一个带头节点的双向循环链表，头节点让用户来管理，提供初始化接口 */
void initDList(DList *header);
void releaseDList(DList *header);// 实现头插、尾插
void insertDListHeader(DList *header, Element val);
void insertDListRear(DList *header, Element val);
// 显示链表
void showDList(const DList *header);
// 删除一个元素
void delDList(DList *header, Element e);

注：此为.h头文件里的内容，若先用头文件封装再放在.c文件里面使用，最后在main.c文件里面测试，很好的保证了产品内容的安全性与代码便捷性。

1、这一次，为了让代码更加简洁规范，我们使用static的模式构建加入和删除两大基本模块：

//next是已知的待插入位置节点的下一个节点；
//prev是已知的待插入节点的上一个节点（前置节点）；//插入
static void addDNode(DNode *new_node, DNode *prev, DNode *next) {next->prev = new_node;//待插入节点下一个节点的上一个节点是新节点；new_node->next = next;//新节点的下一个是上一个节点；new_node->prev = prev;新节点上一个是前置节点prev->next = new_node;前置节点下一个是新节点
}//删除
static void delDNode(DNode *prev, DNode *next) {next->prev = prev;//某节点下一个节点的前一个是某节点上一个节点；prev->next = next;//某节点上一个节点的下一个是某节点下一个节点；
}

2、然后，我们再在此基础上完成增删改查的基本操作：

1、初始化：

void initDList(DList* header) {header->val = 0;//初始化头结点的数值域为0header->next = header->prev = header;//头结点的前置节点和后置节点都初始化指向头结点
}

2、增添操作：

void insertDListHeader(DList* header, Element val) {DNode *new_node = malloc(sizeof(DNode));//malloc申请空间建立一个新节点new_node->val = val;//新节点赋值；addDNode(new_node, header, header->next);//函数操作++header->val;
}
//头插法;void insertDListRear(DList* header, Element val) {DNode *new_node = malloc(sizeof(DNode));new_node->val = val;addDNode(new_node, header->prev, header);++header->val;
}
//尾插法；

3、删除操作

void delDList(DList* header, Element e) {// 1. 找到这个元素，就可以删除，不需要再找到前置节点DNode *pos = header->next;while (pos != header && pos->val != e) {pos = pos->next;}// 2. 找到没有？if (pos != header) {	// 找到delDNode(pos->prev, pos->next);pos->next = pos->prev = NULL;free(pos);--header->val;} else {printf("Not find %d element!\n", e);}

4、展示函数（若对工程有疑问和对const有疑问可以看本专栏的第一篇内容）

void showDList(const DList* header) {DNode *pos = header->next;printf("show: ");while (pos != header) {printf("\t%d", pos->val);pos = pos->next;}printf("\n");
}
//简单的循环打印，不过多赘述；

5、最后，是销毁链表的函数：

void releaseDList(DList* header) {DNode *pos = header->next;DNode *tmp = NULL;while (pos != header) {tmp = pos;delDNode(pos->prev, pos->next);pos = pos->next;free(tmp);--header->val;}
}
//逐个销毁

最后附上各文件代码：

1、doubleList.h:

#ifndef DOUBLE_LIST_H
#define DOUBLE_LIST_Htypedef int Element;
typedef struct _node {Element val;struct _node *next;struct _node *prev;
} DNode, DList;/* 使用一个带头节点的双向循环链表，头节点让用户来管理，提供初始化接口 */
void initDList(DList *header);
void releaseDList(DList *header);// 实现头插、尾插
void insertDListHeader(DList *header, Element val);
void insertDListRear(DList *header, Element val);
// 显示链表
void showDList(const DList *header);
// 删除一个元素
void delDList(DList *header, Element e);#endif //DOUBLE_LIST_H

2、doubleList.c

#include "doubleList.h"//doubleList.h文件封装的函数名
#include <stdlib.h>
#include <stdio.h>static void addDNode(DNode *new_node, DNode *prev, DNode *next) {next->prev = new_node;new_node->next = next;new_node->prev = prev;prev->next = new_node;
}static void delDNode(DNode *prev, DNode *next) {next->prev = prev;prev->next = next;
}void initDList(DList* header) {header->val = 0;header->next = header->prev = header;
}void releaseDList(DList* header) {DNode *pos = header->next;DNode *tmp = NULL;while (pos != header) {tmp = pos;delDNode(pos->prev, pos->next);pos = pos->next;free(tmp);--header->val;}
}void insertDListHeader(DList* header, Element val) {DNode *new_node = malloc(sizeof(DNode));new_node->val = val;addDNode(new_node, header, header->next);++header->val;
}void insertDListRear(DList* header, Element val) {DNode *new_node = malloc(sizeof(DNode));new_node->val = val;addDNode(new_node, header->prev, header);++header->val;
}void showDList(const DList* header) {DNode *pos = header->next;printf("show: ");while (pos != header) {printf("\t%d", pos->val);pos = pos->next;}printf("\n");
}void delDList(DList* header, Element e) {// 1. 找到这个元素，就可以删除，不需要再找到前置节点DNode *pos = header->next;while (pos != header && pos->val != e) {pos = pos->next;}// 2. 找到没有？if (pos != header) {	// 找到delDNode(pos->prev, pos->next);pos->next = pos->prev = NULL;free(pos);--header->val;} else {printf("Not find %d element!\n", e);}
}

3、main.c

#include <stdio.h>
#include "doubleList.h"DList stu_table;int main() {initDList(&stu_table);for (int i = 0; i < 5; ++i) {// insertDListHeader(&stu_table, i + 100);insertDListRear(&stu_table, i + 100);}insertDListHeader(&stu_table, 60);insertDListHeader(&stu_table, 80);showDList(&stu_table);printf("====================\n");delDList(&stu_table, 102);showDList(&stu_table);releaseDList(&stu_table);printf("num: %d\n", stu_table.val);showDList(&stu_table);return 0;
}

————————————希望能对你有所帮助！！！————————————————

查看全文

http://www.lryc.cn/news/575879.html