文章目录

前言一、循环双链表的定义二、循环双链表的结构三、循环双链表的常用操作结语附录

---

前言

        之前学习的双链表结构，可以实现从表中任一结点出发找到链表中的其他结点，但是该结构如果要从头结点开始查找尾结点，那么就需要通过遍历查找尾结点，这种情况下双链表的效率较低，为了解决这个缺点，将其改进为循环双链表，以此来提高查找效率。

一、循环双链表的定义

        循环双链表是对双链表的改进，将尾结点与头结点建立连接，使得尾结点可以直接查找到头结点，头结点也能够直接查找到头结点，以此来提高查找的效率。

二、循环双链表的结构

结构图 代码描述

#define ElemType int //循环双链表结点结构 typedef struct Node { ElemType data; //数据域 struct Node *prio; //前驱结点指针域 struct Node *next; //后继结点指针域 }Node, *PNode; //双链表结点管理结构 typedef struct List { PNode first; //指向首结点（首结点不存放数据） PNode last; //指向尾结点 int size; //记录有效结点数 }List;

三、循环双链表的常用操作

初始化循环双联链表

//初始化双链表 void InitDCList(List *list) { //申请头结点空间 Node *s = (Node *)malloc(sizeof(Node)); assert(s != NULL); //将头结点连接入管理结点 list->first = list->last = s; //设置前驱指针指向（指向头结点） list->first->prio = list->last; //设置后继结点指向（指向尾结点） list->last->next = list->first; list->size = 0; }

获取结点

//获取结点 Node* _buynode(ElemType x) { Node *s = (Node *)malloc(sizeof(Node)); assert(s != NULL); s->data = x; s->next = s->prio = NULL; return s; }

尾插

void push_back(List *list, ElemType x) { //获取结点 Node *s = _buynode(x); //将插入结点与头结点连接 s->next = list->last->next; s->next->prio = s; //将插入结点与上一尾结点连接 s->prio = list->last; list->last->next = s; //修改双向链表管理结点的尾指针 list->last = s; list->size++; }

头插

//头插 void push_front(List *list, ElemType x) { //获取插入结点 Node *s = _buynode(x); //连接新插入结点和其下一个结点 s->next = list->first->next; s->next->prio = s; //插入结点和头结点 s->prio = list->first; list->first->next = s; //如果这个结点是第一个有效结点，需要更改管理结点尾指针的指向 if(list->first == list->last) list->last = s; list->size++; }

查看循环双链表数据

//查看循环双链表数据 void show_list(List *list) { //指向第一个有效结点 Node *p = list->first->next; //将所有有效结点输出 while(p != list->first) { printf("%d-->",p->data); p = p->next; } printf("Nul.\n"); }

尾删

//尾删 void pop_back(List *list) { //如果没有有效结点，那么不进行删除 if(list->size == 0) return; //设置管理结点的尾部指针指向 Node *p = list->last; list->last = list->last->prio; //删除结点 p->next->prio = p->prio; p->prio->next = p->next; free(p); list->size--; }

头删

//头删 void pop_front(List *list) { //如果没有有效结点不进行删除 if(list->size == 0) return; //删除结点 Node *p = list->first->next; p->next->prio = p->prio; p->prio->next = p->next; //如果只有一个有效结点，需要更改管理结点尾指针指向 if(list->size == 1) list->last = list->first; list->size--; }

按值插入(由小到大的顺序)

//按值插入(由小到大的顺序) void insert_val(List *list, ElemType x) { Node *p = list->first;//先指向头结点 //查找要插入结点的位置 while(p->next!=list->last && p->next->data < x) p = p->next; //如果插入的位置在最后，则进行尾插 if(p->next==list->last && p->next->data<x) { push_back(list,x); } else //普通插入 { Node *s = _buynode(x); s->next = p->next; s->next->prio = s; s->prio = p; p->next = s; list->size++; } }

查找某一个值所在的位置

//查找某一个值所在的位置 Node* find(List *list, ElemType key) { //从第一个有效结点位置开始查找 Node *p = list->first->next; while(p != list->first && p->data != key) p = p->next; //如果没有找到返回空 if(p == list->first) return NULL; return p; }

获取有效结点个数

//获取有效结点个数 int length(List *list) { return list->size; }

按值删除

//按值删除 void delete_val(List *list, ElemType key) { //如果没有有效结点，则无需删除 if(list->size == 0) return; //查找要删除结点所在的位置 Node *p = find(list,key); //如果没有找到，无需删除 if(p == NULL) { printf("要删除的数据不存在.\n"); return; } //如果这个结点是尾结点，则进行尾删 if(p == list->last) { pop_back(list); } else//否则进行普通删除 { p->next->prio = p->prio; p->prio->next = p->next; free(p); list->size--; } }

排序(按照由小到大排序)

//排序(按照由小到大排序) void sort(List *list) { //如果有效结点数小于等于1，则无需排序 if(list->size==0 || list->size==1) return; //将原来的循环双链表，分解成两条 Node *s = list->first->next; Node *q = s->next; list->last->next = NULL; list->last = s; list->last->next = list->first; list->first->prio = list->last; //从第二条链表中不断拿取元素按值插入(由小到大)到第一条循环链表中 while(q != NULL) { //拿取元素 s = q; q = q->next; //按值插入（由小到大） Node *p = list->first;//查找插入位置 while(p->next!=list->last && p->next->data < s->data) p = p->next; if(p->next==list->last && p->next->data<s->data) {//尾插 s->next = list->last->next; s->next->prio = s; s->prio = list->last; list->last->next = s; list->last = s; } else {//普通插入 s->next = p->next; s->next->prio = s; s->prio = p; p->next = s; } } }

逆置

//逆置 void resver(List *list) { //如果有效结点数小于等于1，则无需排序 if(list->size==0 || list->size==1) return; //将原来的循环双链表，分解成两条 Node *p = list->first->next; Node *q = p->next; list->last->next = NULL; list->last = p; list->last->next = list->first; list->first->prio = list->last; //从第二条链表中不断拿取元素头插到第一条循环链表中 while(q != NULL) { //获取元素 p = q; q = q->next; //头插 p->next = list->first->next; p->next->prio = p; p->prio = list->first; list->first->next = p; } }

清空有效结点

//清空有效结点 void clear(List *list) { //如果没有结点 if(list->size == 0) return; //从第一个有效结点开始 Node *p = list->first->next; while(p != list->first) { //清空释放有效结点（头删） p->next->prio = list->first; list->first->next = p->next; free(p); p = list->first->next; } list->last = list->first; list->size = 0; }

销毁循环双链表

//销毁循环双链表 void destroy(List *list) { //清空释放所有有效结点 clear(list); free(list->first); //清空管理结点 list->first = list->last = NULL; }

结语

        对循环双链表的介绍就到这里，希望这篇文章能够给予你一些帮助。

附录

以下提供循环双链表的测试代码

DCList.h

#ifndef __DCLIST_H__ #define __DCLIST_H__ #include<stdio.h> #include<malloc.h> #include<assert.h> #define ElemType int //循环双链表结点结构 typedef struct Node { ElemType data; //数据域 struct Node *prio; //前驱结点指针域 struct Node *next; //后继结点指针域 }Node, *PNode; //双链表结点管理结构 typedef struct List { PNode first; //指向首结点（首结点不存放数据） PNode last; //指向尾结点 int size; //记录有效结点数 }List; Node* _buynode(ElemType x); void InitDCList(List *list); void push_back(List *list, ElemType x); void push_front(List *list, ElemType x); void show_list(List *list); void pop_back(List *list); void pop_front(List *list); void insert_val(List *list, ElemType x); Node* find(List *list, ElemType key); int length(List *list); void delete_val(List *list, ElemType key); void sort(List *list); void resver(List *list); void clear(List *list); void destroy(List *list); #endif //__DCLIST_H__

DCList.cpp

#include"DCList.h" //获取结点 Node* _buynode(ElemType x) { Node *s = (Node *)malloc(sizeof(Node)); assert(s != NULL); s->data = x; s->next = s->prio = NULL; return s; } //初始化双链表 void InitDCList(List *list) { //申请头结点空间 Node *s = (Node *)malloc(sizeof(Node)); assert(s != NULL); //将头结点连接入管理结点 list->first = list->last = s; //设置前驱指针指向（指向头结点） list->first->prio = list->last; //设置后继结点指向（指向尾结点） list->last->next = list->first; list->size = 0; } //尾插 void push_back(List *list, ElemType x) { //获取结点 Node *s = _buynode(x); //将插入结点与头结点连接 s->next = list->last->next; s->next->prio = s; //将插入结点与上一尾结点连接 s->prio = list->last; list->last->next = s; //修改双向链表管理结点的尾指针 list->last = s; list->size++; } //头插 void push_front(List *list, ElemType x) { //获取插入结点 Node *s = _buynode(x); //连接新插入结点和其下一个结点 s->next = list->first->next; s->next->prio = s; //插入结点和头结点 s->prio = list->first; list->first->next = s; //如果这个结点是第一个有效结点，需要更改管理结点尾指针的指向 if(list->first == list->last) list->last = s; list->size++; } //查看循环双链表数据 void show_list(List *list) { //指向第一个有效结点 Node *p = list->first->next; //将所有有效结点输出 while(p != list->first) { printf("%d-->",p->data); p = p->next; } printf("Nul.\n"); } //尾删 void pop_back(List *list) { //如果没有有效结点，那么不进行删除 if(list->size == 0) return; //设置管理结点的尾部指针指向 Node *p = list->last; list->last = list->last->prio; //删除结点 p->next->prio = p->prio; p->prio->next = p->next; free(p); list->size--; } //头删 void pop_front(List *list) { //如果没有有效结点不进行删除 if(list->size == 0) return; //删除结点 Node *p = list->first->next; p->next->prio = p->prio; p->prio->next = p->next; //如果只有一个有效结点，需要更改管理结点尾指针指向 if(list->size == 1) list->last = list->first; list->size--; } //按值插入(由小到大的顺序) void insert_val(List *list, ElemType x) { Node *p = list->first;//先指向头结点 //查找要插入结点的位置 while(p->next!=list->last && p->next->data < x) p = p->next; //如果插入的位置在最后，则进行尾插 if(p->next==list->last && p->next->data<x) { push_back(list,x); } else //普通插入 { Node *s = _buynode(x); s->next = p->next; s->next->prio = s; s->prio = p; p->next = s; list->size++; } } //查找某一个值所在的位置 Node* find(List *list, ElemType key) { //从第一个有效结点位置开始查找 Node *p = list->first->next; while(p != list->first && p->data != key) p = p->next; //如果没有找到返回空 if(p == list->first) return NULL; return p; } //获取有效结点个数 int length(List *list) { return list->size; } //按值删除 void delete_val(List *list, ElemType key) { //如果没有有效结点，则无需删除 if(list->size == 0) return; //查找要删除结点所在的位置 Node *p = find(list,key); //如果没有找到，无需删除 if(p == NULL) { printf("要删除的数据不存在.\n"); return; } //如果这个结点是尾结点，则进行尾删 if(p == list->last) { pop_back(list); } else//否则进行普通删除 { p->next->prio = p->prio; p->prio->next = p->next; free(p); list->size--; } } //排序(按照由小到大排序) void sort(List *list) { //如果有效结点数小于等于1，则无需排序 if(list->size==0 || list->size==1) return; //将原来的循环双链表，分解成两条 Node *s = list->first->next; Node *q = s->next; list->last->next = NULL; list->last = s; list->last->next = list->first; list->first->prio = list->last; //从第二条链表中不断拿取元素按值插入(由小到大)到第一条循环链表中 while(q != NULL) { //拿取元素 s = q; q = q->next; //按值插入（由小到大） Node *p = list->first;//查找插入位置 while(p->next!=list->last && p->next->data < s->data) p = p->next; if(p->next==list->last && p->next->data<s->data) {//尾插 s->next = list->last->next; s->next->prio = s; s->prio = list->last; list->last->next = s; list->last = s; } else {//普通插入 s->next = p->next; s->next->prio = s; s->prio = p; p->next = s; } } } //逆置 void resver(List *list) { //如果有效结点数小于等于1，则无需排序 if(list->size==0 || list->size==1) return; //将原来的循环双链表，分解成两条 Node *p = list->first->next; Node *q = p->next; list->last->next = NULL; list->last = p; list->last->next = list->first; list->first->prio = list->last; //从第二条链表中不断拿取元素头插到第一条循环链表中 while(q != NULL) { //获取元素 p = q; q = q->next; //头插 p->next = list->first->next; p->next->prio = p; p->prio = list->first; list->first->next = p; } } //清空有效结点 void clear(List *list) { //如果没有结点 if(list->size == 0) return; //从第一个有效结点开始 Node *p = list->first->next; while(p != list->first) { //清空释放有效结点（头删） p->next->prio = list->first; list->first->next = p->next; free(p); p = list->first->next; } list->last = list->first; list->size = 0; } //销毁循环双链表 void destroy(List *list) { //清空释放所有有效结点 clear(list); free(list->first); //清空管理结点 list->first = list->last = NULL; }

Main.cpp

#include"DCList.h" void main() { List mylist; InitDCList(&mylist); ElemType Item; Node *p = NULL; int select = 1; while(select) { printf("**************************************\n"); printf("* [1] push_back [2] push_front *\n"); printf("* [3] show_list [4] pop_back *\n"); printf("* [5] pop_front [6] insert_val *\n"); printf("* [7] find [8] length *\n"); printf("* [9] delete_val [10] sort *\n"); printf("* [11] resver [12] clear *\n"); printf("* [13*] destroy [0] quit_system *\n"); printf("**************************************\n"); printf("请选择:>"); scanf("%d",&select); if(select == 0) break; switch(select) { case 1: printf("请输入要插入的数据(-1结束):>"); while(scanf("%d",&Item),Item != -1) { push_back(&mylist,Item); } break; case 2: printf("请输入要插入的数据(-1结束):>"); while(scanf("%d",&Item),Item != -1) { push_front(&mylist,Item); } break; case 3: show_list(&mylist); break; case 4: pop_back(&mylist); break; case 5: pop_front(&mylist); break; case 6: printf("请输入要插入的数据:>"); scanf("%d",&Item); insert_val(&mylist,Item); break; case 7: printf("请输入要查找的数据:>"); scanf("%d",&Item); p = find(&mylist,Item); if(p == NULL) { printf("要查找的数据在链表中不存在.\n"); } break; case 8: printf("双向循环链表的长度为:> %d \n",length(&mylist)); break; case 9: printf("请输入要删除的值:>"); scanf("%d",&Item); delete_val(&mylist,Item); break; case 10: sort(&mylist); break; case 11: resver(&mylist); break; case 12: clear(&mylist); break; //case 13: // destroy(&mylist); // break; default: printf("输入的命令错误,请重新输入.\n"); break; } } destroy(&mylist); }