一、循环单链表与循环双链表的对比二、实现带头结点的循环单链表List.h#pragmaonce#includestdio.h#includestdlib.h#includestdbool.h// 实现带头结点的循环单链表// 定义结点的结构typedefintElemType;typedefstructLNode{ElemType data;structLNode*next;}LNode,*LinkList;// 循环单链表的初始化boolInitList(LinkListL);// L是头结点的地址的别名// 判断实现带头结点的循环单链表是否为空表即链表中是否存储了有效数据,若为空返回true,否则返回falseboolEmpty(LinkList L);// L接收头结点的地址// 判断p指向的结点是否为循环单链表的尾结点如果是返回true,否则返回falseboolisTail(LinkList L,LNode*p);// L接收头结点的地址List.cpp#define_CRT_SECURE_NO_WARNINGS1#includeList.h// 循环单链表的初始化boolInitList(LinkListL)// L是头结点的地址的别名{// 开辟头结点的空间L(LNode*)malloc(sizeof(LNode));if(LNULL)// 表示头结点的空间开辟失败returnfalse;L-nextL;// 为了构成一个环头结点的next指针需要指向头结点returntrue;}// 判断实现带头结点的循环单链表是否为空表即链表中是否存储了有效数据,若为空返回true,否则返回falseboolEmpty(LinkList L)// L接收头结点的地址{assert(L);// 头结点的地址不能为NULLif(L-nextL)// 当头结点的next指针指向头结点时表示链表为空returntrue;elsereturnfalse;}// 判断p指向的结点是否为循环单链表的尾结点如果是返回true,否则返回falseboolisTail(LinkList L,LNode*p)// L接收头结点的地址{assert(L!NULLp!NULL);// 头结点的地址不能为NULLp指向的结点的地址也不能为NULLif(p-nextL)//循环单链表中尾结点的next指针指向头结点returntrue;elsereturnfalse;}Test.cpp#define_CRT_SECURE_NO_WARNINGS1#includeList.hvoidtest(){// 创建一个头指针(即指向头结点的指针)LNode*pNULL;// 测试循环双链表的初始化InitList(p);}intmain(){test();return0;}三、实现带头结点的循环双链表List.h#pragmaonce#includestdio.h#includestdlib.h#includestdbool.h// 实现带头结点的循环双链表typedefintElemType;typedefstructDNode{ElemType data;// 结点中的数据域存储一个整数structDNode*prior;// 指向前一个结点structDNode*next;// 指向后一个结点}DNode,*DLinkList;// 将struct DNode重命名为DNode将struct DNode*重命名为DLinkList// 因此DNode*与DLinkList完全等价// 循环双链表的初始化boolInitDLinkList(DLinkListL);// L是头结点的地址的别名// 判断循环双链表是否为空表(即链表中是否存储了有效数据)。若为空返回true否则返回falseboolEmpty(DLinkList L);// L接收头结点的地址// 判断p指向的结点是否为尾结点。若是尾结点返回true否则返回falseboolisTail(DLinkList L,DNode*p);// L接收头结点的地址// 在p指向的结点后插入s指向的结点boolInsertNextDNode(DNode*p,DNode*s);// 删除p指向的结点的后面一个结点boolDeleteNextDNode(DLinkList L,DNode*p);// L接收头结点的地址List.cpp#define_CRT_SECURE_NO_WARNINGS1#includeList.h// 循环双链表的初始化boolInitDLinkList(DLinkListL)// L是头结点的地址的别名{// 开辟头结点的空间L(DNode*)malloc(sizeof(DNode));// L指向头结点if(LNULL)// 表示头结点的空间开辟失败returnfalse;L-priorL-nextL;// 为了构成一个环状需要让头结点的next指针与prior指针均指向头结点returntrue;}// 判断循环双链表是否为空表(即链表中是否存储了有效数据)。若为空返回true否则返回falseboolEmpty(DLinkList L)// L接收头结点的地址{assert(L);// 头结点的地址不能为NULLif(L-nextL)// 当头结点的next指针指向头结点时表示循环双链表为空returntrue;elsereturnfalse;}// 判断p指向的结点是否为尾结点。若是尾结点返回true否则返回falseboolisTail(DLinkList L,DNode*p)// L接收头结点的地址{assert(L!NULLp!NULL);// 头结点的地址不能为NULLp指向的结点的地址也不能为NULLif(p-nextL)// 尾结点的next指针指向头结点returntrue;elsereturnfalse;}// 在p指向的结点后插入s指向的结点boolInsertNextDNode(DNode*p,DNode*s){if(pNULL||sNULL)// 当p或s指向的结点无效时无法指向删除操作returnfalse;s-nextp-next;s-priorp;p-next-priors;// 如果实现的是双链表这句代码在尾结点后插入新结点时会导致对空指针的解引用。p-nexts;returntrue;}// 删除p指向的结点的后面一个结点boolDeleteNextDNode(DLinkList L,DNode*p)// L接收头结点的地址{if(pNULL||p-nextL)//当p指向的结点无效或者p指向的结点的后一个结点是头结点时均不能执行删除操作returnfalse;DNode*delep-next;// dele指向待删除的结点p-nextdele-next;dele-next-priorp;// 如果实现的是双链表这句代码在删除尾结点时会导致对空指针的解引用。free(dele);deleNULL;returntrue;}Test.cpp#define_CRT_SECURE_NO_WARNINGS1#includeList.hvoidtest(){// 创建一个头指针(即指向头结点的指针)DNode*pNULL;// 测试循环双链表的初始化InitDLinkList(p);}intmain(){test();return0;}