Skip to main content

双向循环链表

1. 基本概念

双向链表是在单向链表的每个结点中,再设置一个指向其前驱结点的指针域。

Zhi61t.png

由于这是一个双向链表,所以对于链表中的某一个结点 p ,它后继的前驱以及前驱的后继都是它自己。

p->next->prev = p = p->prev->next;

2. 双向循环链表

  • 双向循环链表的带头结点空链表为

ZhijrP.png

  • 非空的双向循环链表

ZhihOM.png

3. 双向链表结点的创建

typedef int DataType;

//双向循环链表结点结构体声明
typedef struct Node
{
DataType data; //数据域
struct Node *prev; //前驱指针域
struct Node *next; //后继指针域
}double_link_list;

4. 初始化

//初始化一条链表
double_link_list *list_init(void)
{
double_link_list *head = malloc(sizeof(double_link_list));
if(head != NULL)
{
//自循环:自己指向自己
head->next = head;
head->prev = head;

// 返回头结点地址
return head;
}
return NULL;
}

5. 结点的创建

//创建一个新结点
double_link_list *create_node(datatype data)
{
linknode *new = malloc(sizeof(double_link_list));
if(new != NULL)
{
//自循环:自己指向自己
new->data = data; //把数据保存到结点数据域
new->next = new;
new->prev = new;

// 返回头结点地址
return new;
}
return NULL;
}

6. 插入结点

  • 在两个结点之间插入结点:

Zhiy16.png

//新节点插入到任意两个相邻结点之间
// new:新结点
// prev:插入位置的前一个结点
// next:插入位置的后一个结点
void add_node(double_link_list *new, double_link_list *prev, double_link_list *next)
{
// printf("%s\n", __FUNCTION__);
prev->next = new;
new->prev = prev;
new->next = next;
next->prev = new;
}
  • 头插法和尾插法
//头插
// 在头结点后面添加一个结点
void inster_head(double_link_list *head, double_link_list *new)
{
//把新节点指向要插入位置的头结点和头结点的下一个
new->prev = head;
new->next = head->next;

// 把插入位置的后一个结点的prev从指向头改成指向new
head->next->prev = new;

// 把头的next指向新的节点new
head->next = new;
}
//尾插
// 在链表的尾巴之后添加一个结点, 实际上就是头的前面
void inster_tail(double_link_list *head, double_link_list *new)
{
//把新节点指向要插入位置的前一个结点和头结点
new->next = head;
new->prev = head->prev;

//把插入位置的前一个结点的next从指向head改成指向new
head->prev->next = new;

//把头结点的prev从原来的值改为指向new
head->prev = new;
}

// 尾插
void inster_tail(double_link_list *head, double_link_list *new)
{
add_node(new, head->prev, head);
}

// 头插
void inster_head(double_link_list *head, double_link_list *new)
{
add_node(new, head, head->next);
}

6. 遍历链表

// 向后遍历
void display_next_list(double_link_list *head)
{
display_prev_list *tmp = head;
for(; tmp->next != head; tmp = tmp->next)
{
printf("%d->", tmp->next->data);
}
printf("\n");
}

// 向前遍历
void display_prev_list(double_link_list *head)
{
display_prev_list *tmp = head;
for(; tmp->prev != head; tmp = tmp->prev)
{
printf("%d->", tmp->prev->data);
}
printf("\n");
}

7. 查找结点

// 查找某个结点
// 在哪条链表中查找
// 查找什么数据?
double_link_list *find_node(double_link_list *head, datatype data)
{
linknode *tmp = head;
for(; tmp->next != head; tmp = tmp->next)
{
if(tmp->next->data == data)
return tmp->next;
}
return NULL; //没找到
}

8. 删除结点

ZhnB6R.png

//从链表中删除一个结点
//把链表中的一个结点脱离出来,并未释放
double_link_list *remove_node(double_link_list *head, datatype data)
{
//查找要删除的结点,找到返回结点
double_link_list *f_node = NULL;
if( ( f_node = find_node(head, data) ) == NULL)
return NULL;

//把结点的前一个结点的next指向被删除节点的后一个结点
f_node->prev->next = f_node->next;

//把节点的后一个结点的prev指向被删除节点的前一个结点
f_node->next->prev = f_node->prev;

//返回删除的结点
return f_node;
}

9. 销毁结点

// 直接删除结点(会释放结点空间)
bool destory_node(double_link_list *head, datatype data)
{
double_link_list *d_node = NULL;
if( (d_node = remove_node(head, data)) == NULL )
return false; //没有这个节点

//把这个结点的前后指针,都指向空,并且释放空间
d_node->prev = NULL;
d_node->next = NULL;
free(d_node);

return true;
}

10. 更新结点

//更新结点
// 更新是哪一条链表
// 更新的是哪一个数据
// 更新的新数据是什么
bool updata_node(double_link_list *head, datatype old_data, datatype new_data)
{
double_link_list *f_node = NULL;
if( ( f_node = find_node(head, old_data) ) == NULL)
return false;

f_node->data = new_data;
return true;
}

11. 移动结点

//移动一个结点
//移动哪一条链表的结点
//移动的是哪一个数据的结点
//要移到那个数据之后
bool move_node(double_link_list *head, datatype src_data, datatype dest_data)
{
double_link_list *src_node = NULL;
double_link_list *dest_node = NULL;

//找到要移动到哪里
if( ( dest_node = find_node(head, dest_data) ) == NULL)
return false;

//找到要移动数据结点
if( ( src_node = find_node(head, src_data) ) == NULL)
return false;

//把节点的前一个节点的next指向被删除节点的后一个结点
src_node->prev->next = src_node->next;

//把节点的后一个节点的prev指向被删除节点的前一个结点
src_node->next->prev = src_node->prev;

//把这个src_node添加到dest_node之后
inster_head(dest_node, src_node);
return true;
}

12. main函数调用

int main(int argc, char *argv[])
{
//1. 创建一条链表
linknode *head = list_init();
if(head == NULL){
printf("链表初始化失败\n");
exit(0);
}

// 2. 初始化一些自然数
int i, n;

printf("请输入需要多少个自然数\n");
scanf("%d", &n);

for(i=1; i<=n; i++)
{
// 2.1 创建新结点
linknode *new = create_node(i);
if(new == NULL) {
printf("%d创建失败\n", i);
continue; //跳到条件判断,继续下一次循环
}

// 2.2 插入新结点
// inster_tail(head, new);
inster_head(head, new);
}

//3. 向后遍历链表
display_next_list(head);

//4. 查找4这个数据结点
linknode *f_node = find_node(head, 4);
if(f_node == NULL) {
printf("链表中没有数据4的这个节点\n");
}
else
printf("找到这个%d在链表中的节点地址:%p\n", f_node->data, f_node);

// 5. 删除链表中的某个节点
if( !destory_node(head, 4) )
printf("删除失败");
else{
printf("删除成功\n");
display_next_list(head);
}

// 6. 移动结点
move_node(head, 10, 2);
display_next_list(head);

// 7. 更新结点
updata_node(head, 6, 66);
display_next_list(head);

return 0;
}