当前位置:博客首页>>C/C++ >> 阅读正文

双向链表的实现(头插尾插和删除、遍历)

作者: 郑晓 分类: C/C++, 数据结构 发布于: 2017-03-09 12:38 浏览:5,886 评论(2)


关于双向链表和循环链表,维基上的解释是:

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

循环链表是一种链式存储结构,它的最后一个结点指向头结点,形成一个环。因此,从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致,差别仅仅在于算法中的循环条件有所不同。


#include
#include
//定义链接节点结构 包含了节点的数据域、前后指针域
typedef struct node {
char *data;
struct node *next;
struct node *prior;
} node;
//定义链表结构 包含链表头节点指针、链表长度
typedef struct {
node *head;
int len;
}LinkedList;
//初始化双向链表 包括生成表头,初始化表长度
LinkedList * init() {
LinkedList *L = NULL;
L = (LinkedList *)malloc(sizeof(LinkedList));
node *head = (node *)malloc(sizeof(node));
head->next = head;
head->prior= head;
L->head = head;
L->len = 0;
return L;
}
//向链表头部插入数据
void add_to_head(LinkedList *L, char *data) {
node *dnode = (node *)malloc(sizeof(node));
dnode->data = data;
dnode->next = L->head->next;
dnode->prior= L->head;
L->head->next->prior = dnode;
L->head->next = dnode;
L->len++;
}
//向链表尾部插入数据
void add_to_tail(LinkedList *L, char *data) {
node *dnode = (node *)malloc(sizeof(node));
dnode->data = data;
dnode->next = L->head;
dnode->prior= L->head->prior;
dnode->prior->next = dnode;
L->head->prior = dnode;
L->len++;
}
//从链表中删除下标为index的节点,index从0开始。
//index在链表前半段时从头部遍历 index在链表后半段时从头部逆向遍历
void del_data(LinkedList *L, int index) {
if(index > L->len) {
printf("index error");
return;
}
node * node_tmp = NULL;
int i=0;
if(index < L->len/2) {
node_tmp = L->head->next;
for(i=0; inext;
}
} else {
node_tmp = L->head->prior;
for(i=0; ilen-index; i++) {
node_tmp = node_tmp->prior;
}
}
node_tmp->prior->next = node_tmp->next;
node_tmp->next->prior = node_tmp->prior;
free(node_tmp);
L->len--;
}
//遍历并打印链表(正向)
void foreach(LinkedList *L) {
node *n = L->head->next;
while(n != L->head) {
printf("%s\n", n->data);
n = n->next;
}
}
//遍历并打印链表(逆向)
void rforeach(LinkedList *L) {
node *n = L->head->prior;
while(n != L->head) {
printf("%s\n", n->data);
n = n->prior;
}
}
int main() {
LinkedList *L;
L = init();
add_to_tail(L, "C");
add_to_tail(L, "C++");
add_to_tail(L, "C#");
add_to_tail(L, "java");
add_to_tail(L, "php");
add_to_tail(L, "python");
add_to_tail(L, "ruby");
add_to_tail(L, "object-c");
printf("打印链表\n");
foreach(L);
printf("删除index=2的元素 打印链表\n");
del_data(L, 2);
foreach(L);
printf("逆向打印链表\n");
rforeach(L);
return;
}

以上代码的运行结果:

       

本文采用知识共享署名-非商业性使用 3.0 中国大陆许可协议进行许可,转载时请注明出处及相应链接。

本文永久链接: https://www.zh30.com/doubly-linked-list-1.html

双向链表的实现(头插尾插和删除、遍历):目前有2 条留言

用户评论头像 啊啊啊发表于 2020年12月16日 15:16[回复]

大神牛啊
Raymond[1周前]
给力啊, 终于找到一个能用的方法了
啊啊啊啊啊[1周前]
真的三个都是错的
123[1周前]
有没有pull时出现过js或css文
wj[1周前]
墙了
郑晓[3周前]
恭喜

用户评论头像 啊啊啊发表于 2020年12月16日 15:15[回复]

牛逼啊 大神

发表评论

change vcode