第2章 双向链表
双向链表
概念
对链表而言，双向均可遍历是最方便的，另外首尾相连循环遍历也可大大增加链表操作的便捷性。因 此，双向循环链表，是在实际运用中是最常见的链表形态。
基本操作
与普通的链表完全一致，双向循环链表虽然指针较多，但逻辑是完全一样。
基本的操作包括：
1. 节点设计
2. 初始化空链表
3. 增删节点
4. 链表遍历
5. 销毁链表
节点设计
双向链表的节点只是比单向链表多了一个前向指针。示例代码如下所示：
typedef int DATA;
typedef struct node
{
// 以整型数据为例
DATA data;
// 指向相邻的节点的双向指针
struct node *prev;
struct node *next;
}NODE;初始化
所谓初始化，就是构建一条不含有效节点的空链表。 以带头结点的双向循环链表为例，初始化后，其状态如下图所示：
在初始空链表的情况下，链表只有一个头结点，下面是初始化示例代码：
int dlist_create(NODE** head,DATA data)
{
// 创建新节点（申请内存空间）
NODE *pNew = (NODE*)malloc(sizeof(NODE));
if(!pNew)
return -1;
// 给节点赋初值
pNew -> data = data;
// 前后指针默认都指向NULL
pNew -> prev = pNew -> next = NULL;
// 将新节点作为头节点
*head = pNew;
return 0;
}
插入节点
与单链表类似，也可以对双链表中的任意节点进行增删操作，常见的有所谓的头插法、尾插法等， 即：将新节点插入到链表的首部或者尾部，示例代码是：
头插法：将新节点插入到链表的头部
// 将新节点pNew，插入到链表的首部
int dlist_addHead(NODE** head,DATA data)
{
// 创建新节点并申请内存
NODE *pNew = (NODE*)malloc(sizeof(NODE));
if(!pNew)
return -1;
// 给新节点赋值
pNew -> data = data;
pNew -> prev = NULL;
// 后针指向头指针
pNew -> next = *head;
// 如果头指针存在
if(*head)
// 头指针的前指针指向新节点
(*head) -> prev = pNew;
// 新插入的节点作为新的头节点
*head = pNew;
return 0;
}
// 将新节点pNew，插入到链表的尾部
int dlist_addTail(NODE** head,DATA data)
{
// 创建节点并申请内存
NODE *pNew = (NODE*)malloc(sizeof(NODE));
if(!pNew)
return -1;
// 初始化节点
pNew -> data = data;
pNew -> prev = NULL;
pNew -> next = NULL;
// 用来记录尾节点，默认头节点就是尾节点
NODE* p = *head;
if(!p)
{
// 头节点不存在，新插入的节点作为头节点
*head = pNew;
return 0;
}
// 通过循环，查找尾节点
while(p -> next)
{
p = p -> next;
}
// 尾节点的后指针指向新插入的节点
p -> next = pNew;
// 新插入的节点的前指针指向尾节点
pNew -> prev = p;
// 此时的新节点作为了新的尾节点
return 0;
}
中间插法：将新节点插入到链表的指定位置
// 将新节点pNew，插入到链表的指定位置
int dlist_insert(NODE** head,DATA pos,DATA data)
{
NODE *pNew = (NODE*)malloc(sizeof(NODE));
if(!pNew)
return -1;
pNew -> data = data;
pNew -> prev = NULL;
pNew -> next = NULL;
NODE* p = *head, *q = NULL;
if(!p)
{
*head = pNew;
return 0;
}
if(memcmp(&(p -> data),&pos,sizeof(DATA)) == 0)
{
pNew -> next = p;
p -> prev = pNew;
*head = pNew;
return 0;
}
while(p)
{
if(memcmp(&(p -> data),&pos,sizeof(DATA)) == 0)
{
pNew -> next = p;
pNew -> prev = q;
p -> prev = pNew;
q -> next = pNew;
return 0;
}
q = p;
p = p -> next;
}
q -> next = pNew;
pNew -> prev = q;
return 0;剔除节点
注意，从链表中将一个节点剔除出去，并不意味着要释放节点的内容。当然，我们经常在剔除了一个 节点之后，紧接着的动作往往是释放它，但是将“剔除”与“释放”两个动作分开，是最基本的函数封装的 原则，因为它们虽然常常连在一起使用，但它们之间并无必然联系，例如：当我们要移动一个节点的 时候，实质上就是将“剔除”和“插入”的动作连起来，此时就不能释放该节点了。
在双向链表中剔除指定节点的示例代码如下：
// 将data对应的节点从链表中剔除
int dlist_delete(NODE** head,DATA data)
{
NODE* p = *head;
if(!p)
return -1;
if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0)
{
if(p -> next == NULL)
{
*head = NULL;
free(p);
return 0;
}
*head = p -> next;
p -> next -> prev = NULL;
free(p);
return 0;
}
while(p)
{
if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0)
{
p -> prev -> next = p -> next;
if(p -> next == NULL)
p -> prev -> next = NULL;
else
p -> next -> prev = p -> prev;
free(p) ;
return 0;
}
p = p -> next;
}
return -1;
}链表的遍历
对于双向循环链表，路径可以是向后遍历，也可以向前遍历。
下面是根据指定数据查找节点，向前、向后遍历的示例代码，假设遍历每个节点并将其整数数据输 出：
// 根据指定数据查找节点
NODE* dlist_find(const NODE* head,DATA data)
{
const NODE* p = head;
while(p)
{
if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0)
return (NODE*)p;
p = p -> next;
}
return NULL;
}
// 向前|向后遍历
void dlist_showAll(const NODE* head)
{
const NODE* p = head;
while(p)
{
printf("%d ",p -> data);
p = p -> next;// 向后遍历
// p = p -> prev;// 向前遍历
}
printf("\n");
}
修改链表
我们也可以针对链表中的数据进行修改，只需要提供一个修改的源数据和目标数据即可。 示例代码如下：
int dlist_update(const NODE* head,DATA old,DATA newdata)
{
NODE* pFind = NULL;
if(pFind = dlist_find(head,old))
{
pFind -> data = newdata;
return 0;
}
return -1;
}销毁链表
由于链表中的各个节点被离散地分布在各个随机的内存空间，因此销毁链表必须遍历每一个节点，释 放每一个节点。
| 注意： 销毁链表时，遍历节点要注意不能弄丢相邻节点的指针 |
示例代码如下：
void dlist_destroy(NODE** head)
{
NODE *p = *head, *q = NULL;
while(p)
{
q = p;
p = p -> next;
free(q);
}
*head = NULL;
}
完整案例
dlist.h
#ifndef __DLIST_H
#define __DLIST_H
typedef int DATA;
typedef struct node
{
DATA data;
struct node *prev;// 前驱指针
struct node *next;// 后继指针
}NODE;
// 创建链表（初始化）
int dlist_create(NODE**,DATA);
// 向链表插入数据（头插法）
int dlist_addHead(NODE** head,DATA data);
// 向链表插入数据（尾插法）
int dlist_addTail(NODE** head,DATA data);
// 向链表插入数据（中间插法）
int dlist_insert(NODE** head,DATA pos,DATA data);
// 链表数据查询
NODE* dlist_find(const NODE* head,DATA data);
// 链表数据更新
int dlist_update(const NODE* head,DATA old,DATA newdata);
// 链表数据遍历
void dlist_showAll(const NODE* head);
// 链表数据删除
int dlist_delete(NODE** head,DATA data);
// 链表回收
void dlist_destroy(NODE** head);
#endif
#include "dlist.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int dlist_create(NODE** head,DATA data)
{
NODE *pNew = (NODE*)malloc(sizeof(NODE));
if(!pNew)
return -1;
pNew -> data = data;
pNew -> prev = pNew -> next = NULL;
*head = pNew;
return 0;
}
int dlist_addHead(NODE** head,DATA data)
{
NODE *pNew = (NODE*)malloc(sizeof(NODE));
if(!pNew)
return -1;
pNew -> data = data;
pNew -> prev = NULL;
pNew -> next = *head;
if(*head)
(*head) -> prev = pNew;
*head = pNew;
return 0;
}
int dlist_addTail(NODE** head,DATA data)
{
NODE *pNew = (NODE*)malloc(sizeof(NODE));
if(!pNew)
return -1;
pNew -> data = data;
pNew -> prev = NULL;
pNew -> next = NULL;
NODE* p = *head;
if(!p)
{
*head = pNew;
return 0;
}
while(p -> next)
{
p = p -> next;
}
p -> next = pNew;
pNew -> prev = p;
return 0;
}
int dlist_insert(NODE** head,DATA pos,DATA data)
{
NODE *pNew = (NODE*)malloc(sizeof(NODE));
if(!pNew)
return -1;
pNew -> data = data;
pNew -> prev = NULL;
pNew -> next = NULL;
NODE* p = *head, *q = NULL;
if(!p)
{
*head = pNew;
return 0;
}
if(memcmp(&(p -> data),&pos,sizeof(DATA)) == 0)
{
pNew -> next = p;
p -> prev = pNew;
*head = pNew;
return 0;
}
while(p)
{
if(memcmp(&(p -> data),&pos,sizeof(DATA)) == 0)
{
pNew -> next = p;
pNew -> prev = q;
p -> prev = pNew;
q -> next = pNew;
return 0;
}
q = p;
p = p -> next;
}
q -> next = pNew;
pNew -> prev = q;
return 0;
}
int dlist_delete(NODE** head,DATA data)
{
NODE* p = *head;
if(!p)
return -1;
if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0)
{
if(p -> next == NULL)
{
*head = NULL;
free(p);
return 0;
}
*head = p -> next;
p -> next -> prev = NULL;
free(p);
return 0;
}
while(p)
{
if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0)
{
p -> prev -> next = p -> next;
if(p -> next == NULL)
p -> prev -> next = NULL;
else
p -> next -> prev = p -> prev;
free(p) ;
return 0;
}
p = p -> next;
}
return -1;
}
NODE* dlist_find(const NODE* head,DATA data)
{
const NODE* p = head;
while(p)
{
if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0)
return (NODE*)p;
p = p -> next;
}
return NULL;
}
int dlist_update(const NODE* head,DATA old,DATA newdata)
{
NODE* pFind = NULL;
if(pFind = dlist_find(head,old))
{
pFind -> data = newdata;
return 0;
}
return -1;
}
void dlist_destroy(NODE** head)
{
NODE *p = *head, *q = NULL;
while(p)
{
q = p;
p = p -> next;
free(q);
}
*head = NULL;
}
void dlist_showAll(const NODE* head)
{
const NODE* p = head;
while(p)
{
printf("%d ",p -> data);
p = p -> next;
}
printf("\n");
}
dlist_main.c
#include "dlist.h"
#include <stdio.h>
#define OP 2
int main(void)
{
NODE* head = NULL;
int a[] = {1,3,5,7,9};
int n = sizeof a / sizeof a[0];
register int i = 0;
for(; i < n; i++)
dlist_addTail(&head,a[i]);
dlist_showAll(head);
while(1)
{
#if (OP == 0)
DATA data;
NODE *pFind = NULL;
printf("请输入要查找的数据(-1 退出):");
scanf("%d",&data);
if(data == -1)
break;
if(!(pFind = dlist_find(head,data)))
{
puts("查找的数据不存在,请重试...");
continue;
}
printf("在内存地址为 %p 的内存空间中找到了 %d\n",&(pFind->data),pFind->data);
#elif (OP == 1)
DATA data;
NODE *pFind = NULL;
printf("请输入要插入位置的数据(-1 退出):");
scanf("%d",&data);
if(data == -1)
break;
if(dlist_insert(&head,data,407))
{
puts("插入失败,请重试...");
continue;
}
dlist_showAll(head);
#else
DATA data;
NODE *pFind = NULL;
printf("请输入要删除位置的数据(-1 退出):");
scanf("%d",&data);
if(data == -1)
break;
if(dlist_delete(&head,data))
{
puts("删除失败,请重试...");
continue;
}
dlist_showAll(head);
#endif
}
dlist_destroy(&head);
puts("=====回收后====");
dlist_showAll(head);
return 0;
}
循环双向链表【扩展】
案例代码
循环双向链表是在双向链表的基础上进行了改动，整体改动不是很大，请看下面代码：
dclist.h
#ifndef __DCLIST_H
#define __DCLIST_H
typedef int DATA;
typedef struct node
{
DATA data;
struct node *prev;
struct node *next;
}NODE;
int dclist_add(NODE** head,DATA data);
int dclist_delete(NODE** head,DATA data);
NODE* dclist_find(const NODE* head,DATA data);
int dclist_update(const NODE* head,DATA old,DATA newdata);
void dclist_showAll(const NODE* head);
void dclist_destroy(NODE** head);
#endif
dclist.c
#include "dclist.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
static NODE* dclist_create_node(DATA data)
{
NODE* p = (NODE*)malloc(sizeof(NODE));
if(!p)
return NULL;
p -> data = data;
p -> prev = p;
p -> next = p;
return p;
}
/*
@argument: new: 待插入的节点
@argument: prev: 插入后节点的上一个节点
@argument: next: 插入后节点的下一个节点
*/
static void __dclist_add(NODE* new, NODE* prev,NODE* next )
{
new -> prev = prev;
new -> next = next;
prev -> next = new;
next -> prev = new;
}
int dclist_add(NODE** head,DATA data)
{
if(*head == NULL)
{
*head = dclist_create_node(data);
int ret = (*head)?0:-1;
return ret ;
}
NODE *new = dclist_create_node(data);
if(!new)
return -1;
__dclist_add(new,(*head)->prev,*head);
return 0;
}
static void __dclist_delete(NODE* del, NODE* prev,NODE* next )
{
prev -> next = next;
next -> prev = prev;
free(del);
}
int dclist_delete(NODE** head,DATA data)
{
if(*head == NULL)
return -1 ;
NODE *del = dclist_find(*head,data);
if(!del)
return -1;
NODE* p = *head;
if(del == p) //删除的是头节点
{
if(p -> next == p) // 唯一的头节点
{
*head = NULL;
free(p);
return 0;
}
p -> prev -> next = p -> next;
p -> next -> prev = p -> prev;
*head = p -> next;
free(p);
return 0;
}
__dclist_delete(del,del->prev,del->next);
return 0;
}
NODE* dclist_find(const NODE* head,DATA data)
{
const NODE* p = head;
while(p)
{
if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0)
return (NODE*)p;
p = p -> next;
if(p == head)
break;
}
return NULL;
}
int dclist_update(const NODE* head,DATA old,DATA newdata)
{
NODE* pFind = dclist_find(head,old);
if(!pFind)
return -1;
pFind -> data = newdata;
return 0;
}
void dclist_showAll(const NODE* head)
{
const NODE* p = head;
while(p)
{
printf("%d ",p -> data);
p = p -> next;
if(p == head)
break;
}
printf("\n");
}
void dclist_destroy(NODE** head)
{
if(*head == NULL)
return ;
NODE* p = *head,*q = NULL;
p -> prev -> next = NULL;
while(p)
{
q = p ;
p = p -> next;
free(q);
if(p == *head)
break;
}
*head = NULL;
}
dclist_main.c
#include <stdio.h>
#include "dclist.h"
#define DELETE
int main(void)
{
NODE* head = NULL;
int a[] = {1,3,5,7,9,11,13};
int n = sizeof a / sizeof a[0];
register int i = 0;
for(; i < n ; i++)
dclist_add(&head,a[i]);
dclist_showAll(head);
DATA data ;
while(1)
{
#ifdef DELETE
printf("请输入要删除的数据:");
scanf("%d",&data);
if(data == -1)
break;
if(dclist_delete(&head,data) < 0)
{
puts("删除失败,请重试");
continue;
}
dclist_showAll(head);
#else
NODE *pFind = NULL;
printf("请输入要查找的数据:");
scanf("%d",&data);
if(data == -1)
break;
if(!(pFind = dclist_find(head,data)))
{
puts("查找的数据不存在,请重试");
continue;
}
printf("查找数据:%d 内存地址:%p\n",pFind -> data, &(pFind -> data));
#endif
}
dclist_destroy(&head);
puts("====销毁后=====");
dclist_showAll(head);
return 0;
}
适用场合
经过单链表、双链表的学习，可以总结链表的适用场合：
适合用于节点数目不固定，动态变化较大的场合
适合用于节点需要频繁插入、删除的场合 适合用于对节点查找效率不十分敏感的场合
内存监测(valgrind)
安装: sudo apt-get install valgrind
格式: valgrind [options] prog-and-args
例子： valgrind --tool=memcheck --leak-check=full --log-file=./result.txt ./dlist
注意: 在使用valgrind 工具进行内存监测时，要求可执行程序在编译时，要为gcc 编译器指定 -g 选项；
章节作业
（双向循环链表）
【1】用双向循环链表存储若干自然数，并将其奇偶重排输出。
比如：
链表中存储： 1 2 3 4 5 6 7 8 9 …
将其重排成： 1 3 5 7 9 … 8 6 4 2 （奇数升序偶数降序）
解析 从右到左，从最末一个元素开始往前遍历；遇到奇数记下位置，遇到偶数则移动到链表的末尾。
示例代码
// 双向循环链表：奇偶数重排
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
// 链表节点
typedef struct DNode
{
int data;
struct DNode *prior;
struct DNode *next;
}DNode, *DLinkList;
void perror_exit(const char *info)
{
perror(info);
exit(0);
}
/*************************
initialize the list
**************************/
void init_list(DLinkList *p2head)
{
if((*p2head=(DNode *)malloc(sizeof(DNode))) == NULL){
perror("malloc faild");
exit(1);
}
(*p2head)->prior = (*p2head)->next = *p2head;
}
/****************
insert node
*****************/
void insert(DLinkList head, int num)
{
DLinkList pnew;
if((pnew=(DNode *)malloc(sizeof(DNode))) == NULL)
perror_exit("malloc failed");
pnew->data = num;
/***********************************************
insert the new node onto the tail
***********************************************/
pnew->prior = head->prior;
head->prior->next = pnew;
pnew->next = head;
head->prior = pnew;
}
/********************
change the list
*********************/
void rerange(DLinkList old_list, DLinkList new_list)
{
DLinkList p = old_list->next;
//check the next two elements, prevent recycling
while((p->next!=old_list) && (p->next->next!=old_list)){
insert(new_list, p->data);
p = p->next->next;
}
//the list endup with an odd number
if(p->next == old_list){
insert(new_list, p->data);
p = p->prior;
if(p != old_list){
while(p->prior->prior!=old_list){
insert(new_list, p->data);
p = p->prior->prior;
}
insert(new_list, p->data);
}
}
//the list endup with an even number
else{
insert(new_list, p->data);
p = p->next;
insert(new_list, p->data);
while(p->prior->prior!=old_list){
p = p->prior->prior;
insert(new_list, p->data);
}
}
}
/*************
show list
**************/
void show(DLinkList head)
{
DNode *p=head->next;
while(1){
printf("%d ", p->data);
if(p->next == head)
break;
p = p->next;
}
printf("\n");
}
int main(int argc, char **argv)
{
int n;
scanf("%d", &n); // 输入所需链表的长度
// 创建空链表
DLinkList head;
init_list(&head);
// 依次插入节点
int i;
for(i=n; i>0; --i)
{
insert(head, n-i+1);
}
show(head);
/* arange the list */
DLinkList new_list;
init_list(&new_list);
rerange(head, new_list);
show(new_list);
return 0;
}