【数据结构】循环链表(circular linked list) && 双向链表(doubly linked list)
更多精彩尽在微信公众号【程序猿声】微信公众号本节纲要预备知识顺序表(Sequential List)单链表(Singly Linked List )静态链表(Static list )循环链表(circular linked list)双向链表(doubly linked list)05 循环链表5.1什么是循环链表？前面介绍了单链表，相信大家还记得相关的概念。其实循环链表跟单链表也没有差别很多，只是在某些细节上的处理方式会稍稍不同。
在此之前，大家可以先思考一个问题：单链表中，要找到其中某个节点只需要从头节点开始遍历链表即可，但是有些时候我们的想法是，能不能从任意节点开始遍历，也能找到我们需要的那个节点呢？
其实啊，这个实现也很简单自然，把整个链表串成一个环问题就迎刃而解了。所以，关于循环链表，我们有了如下的定义：
将单链表中的尾节点的指针域由NULL改为指向头结点，使整个单链表形成一个环，这种头尾相接的单链表就可以称之为**单循环链表，简称循环链表(circular linked list)。
5.2 循环链表图示这里我们讨论的链表还是设置一个头结点（当然，链表并不是一定需要一个头结点）。
当链表为空的时候，我们可以有如下表示：image对于非空链表则可以这样表示：image不得不提的一点代码语言：txt复制对于循环链表这种设计，我们在遍历的时候的结束条件就不再是p为空的时候结束了。**而是p等于头结点的时候遍历才完成**。这一点希望大家切记。再多说两句代码语言：txt复制我们知道，有了头结点，我们可以轻而易举访问第一个节点。但是当要访问最后一个节点时，却要将整个链表扫一遍，效率不可谓不低下……那么，有没有更好的办法呢？代码语言：txt复制当然是有的，只不过这里我们需要将循环链表再做一个小小的改进，具体表现为：代码语言：txt复制代码语言：txt复制从上图可以看出，我们抛弃了以往的头指针，取而代之的是采用一个尾指针指向了最后一个节点。而且，因为链表是循环的，当我们需要访问第一个节点时，也very easy！**只需要尾指针往后走一个就到前面了。**5.3 循环链表代码关于循环链表的插入删除等操作，其实是和单链表一样的。唯一不同的就是遍历的时候的结束条件不同而已。因此咱们在这里就不做过多篇幅的介绍，直接贴完整代码吧。
循环链表就是末尾指向头形成一个循环的链表.实现思路也很简单,大体把单链表代码做个小小的改动就OK了.这次还是封装在一个类里面吧.
CircleLinkList.h 类头文件,各种声明定义
代码语言：txt复制#pragma once //VC防止头文件重复包含的一条预编译指令
#define status bool
#define OK true
#define ERROR false
#define YES true
#define NO false
template
class Node
{
public:
DType data;
Node * pnext;
};
template
class CCircleLinkList
{
private:
Node
public:
CCircleLinkList();
~CCircleLinkList();
public:
//初始化链表
status InitCList();
//获取链表长度
int GetCListLength();
//增加一个节点 前插法
status AddCListNodeFront(DType idata);
//增加一个节点 后插法
status AddCListNodeBack(DType idata);
//判断链表是否为空
status IsCListEmpty();
//获取指定位置节点值(注意，本程序规定0号为头节点，e获取删除元素)
status GetCListIndexNode(DType *e, int index);
//删除指定位置节点(e获取删除元素)
status DeleteCListIndexNode(DType *e, int index);
//查找链表中指定值(pindex获取位置0==>not found)
status SearchCListNode(DType SData, int *pindex);
//指定位置前插
status InsertCListNodeFront(DType IData, int index);
//指定位置后插
status InsertCListNodeBack(DType IData, int index);
//清空链表(保留根节点)
status ClearCList();
//销毁链表(all delete)
status DestoryCList();
//尾部删除一个元素
status DeleteCListNodeBack();
//打印链表 此函数根据实际情况而定
void PrintCList();
};CircleLinkList.cpp 类的具体实现代码
代码语言：txt复制#include "CircleLinkList.h"
#include
template
CCircleLinkList
{
cout << "链表创建" << endl;
InitCList();
}
template
CCircleLinkList
{
cout << "链表销毁" << endl;
DestoryCList();
}
//初始化链表
template
status CCircleLinkList
{
Node
if (ph != NULL)
{
ph->pnext = ph; //尾指向头
this->phead = ph; //头结点
return OK;
}
return ERROR;
}
//获取链表长度(head_node is not included)
template
int CCircleLinkList
{
int length = 0;
Node
while (ph->pnext != this->phead)
{
length++;
ph = ph->pnext;
}
return length;
}
//增加一个节点 前插法
template
status CCircleLinkList
{
Node
if (pnode != NULL)
{
pnode->data = idata;
pnode->pnext = this->phead->pnext;
this->phead->pnext = pnode; //挂载
return OK;
}
return ERROR;
}
//增加一个节点 尾插法
template
status CCircleLinkList
{
Node
Node
if (pnode != NULL)
{
while (ph->pnext != this->phead)
{
ph = ph->pnext;
}
pnode->data = idata;
pnode->pnext = this->phead;
ph->pnext = pnode; //挂载
return OK;
}
return ERROR;
}
//判断链表是否为空
template
status CCircleLinkList
{
if (this->phead->pnext == this->phead)
{
return YES;
}
return NO;
}
//获取指定位置节点值(注意，本程序规定0号为头节点，e获取节点的值)
template
status CCircleLinkList
{
Node
int i = 0; //计数器
if (ph->pnext == this->phead || index < 1 || index > GetCListLength())
{
return ERROR; //异常 处理
}
while (ph->pnext != this->phead)
{
i++;
ph = ph->pnext;
if (i == index)
{
*e = ph->data;
return OK;
}
}
return ERROR;
}
//删除指定位置节点(e获取删除元素)
template
status CCircleLinkList
{
Node
int i = 0; //计数器
Node
if (ph->pnext == this->phead || index < 1 || index > GetCListLength())
{
return ERROR; //异常 处理
}
while (ph->pnext != this->phead)
{
i++;
q = ph; //保存备用
ph = ph->pnext;
if (i == index)
{
*e = ph->data;
q->pnext = ph->pnext; //删除出局
delete ph;
return OK;
}
}
return ERROR;
}
//查找链表中指定值(pindex获取位置 0==>not found)
template
status CCircleLinkList
{
Node
int iCount = 0;//计数器
while (ph->pnext != this->phead)
{
iCount++;
ph = ph->pnext;
if (ph->data == SData)
{
*pindex = iCount;
return YES;
}
}
*pindex = 0;
return NO;
}
//指定位置前插
template
status CCircleLinkList
{
Node
if (ph->pnext == this->phead || index < 1 || index > GetCListLength())
{
return ERROR; //异常 处理
}
int iCount = 0; //计数器
Node
while (ph->pnext != this->phead)
{
iCount++;
q = ph;
ph = ph->pnext;
if (iCount == index)
{
Node
p->data = IData;
p->pnext = ph;
q->pnext = p; //前插
return OK;
}
}
return ERROR;
}
//指定位置后插
template
status CCircleLinkList
{
Node
if (ph->pnext == this->phead || index < 1 || index > GetCListLength())
{
return ERROR; //异常 处理
}
int iCount = 0; //计数器
Node
while (ph->pnext != this->phead)
{
iCount++;
q = ph;
ph = ph->pnext;
if (iCount == index)
{
Node
q = ph;
ph = ph->pnext; //后插就是后一个节点的前插咯
p->data = IData;
p->pnext = ph;
q->pnext = p;
return OK;
}
}
return ERROR;
}
//清空链表(保留根节点)
template
status CCircleLinkList
{
Node
Node
ph = ph->pnext;//保留头节点
while (ph != this->phead)
{
q = ph;
ph = ph->pnext;
delete q; //释放
}
this->phead->pnext = this->phead;
return OK;
}
//销毁链表(all delete)
template
status CCircleLinkList
{
ClearCList();
delete this->phead;//释放头结点
return OK;
}
template
status CCircleLinkList
{
Node
Node
if (ph->pnext == this->phead)
{
return ERROR; //链表都空了还删鸡毛
}
while (ph->pnext != this->phead)
{
q = ph;
ph = ph->pnext;
}
q->pnext = this->phead;
delete ph;
return OK;
}
template
void CCircleLinkList
{
Node
if (ph->pnext == this->phead)
{
cout << "链表为空，打印鸡毛" << endl;
return;
}
int i = 1;
cout << "===============print list================" << endl;
while (ph->pnext != this->phead)
{
ph = ph->pnext;
cout << "node[" << i++ << "] = " << ph->data << endl;
}
}CircleLinkListTest.cpp 测试代码
代码语言：txt复制#include
#include "CircleLinkList.h"
#include "CircleLinkList.cpp"
using namespace std;
int main()
{
CCircleLinkList
cout << pMySList->IsCListEmpty() << endl;
pMySList->AddCListNodeFront(111);
pMySList->AddCListNodeFront(222);
pMySList->AddCListNodeFront(333);
cout << "链表长度" << pMySList->GetCListLength() << endl;
pMySList->PrintCList();
pMySList->AddCListNodeBack(444);
pMySList->AddCListNodeBack(555);
pMySList->AddCListNodeBack(666);
pMySList->PrintCList();
cout << pMySList->IsCListEmpty() << endl;
cout << "链表长度" << pMySList->GetCListLength() << endl;
int GetElem, GetIndex;
pMySList->GetCListIndexNode(&GetElem, 2);
cout << "Got Elem = " << GetElem << endl;
pMySList->GetCListIndexNode(&GetElem, 6);
cout << "Got Elem = " << GetElem << endl;
pMySList->GetCListIndexNode(&GetElem, 4);
cout << "Got Elem = " << GetElem << endl;
pMySList->DeleteCListIndexNode(&GetElem, 1);
cout << "del Elem = " << GetElem << endl;
pMySList->DeleteCListIndexNode(&GetElem, 3);
cout << "del Elem = " << GetElem << endl;
pMySList->PrintCList();
pMySList->SearchCListNode(555, &GetIndex);
cout << "Search Index = " << GetIndex << endl;
pMySList->SearchCListNode(111, &GetIndex);
cout << "Search Index = " << GetIndex << endl;
pMySList->SearchCListNode(666, &GetIndex);
cout << "Search Index = " << GetIndex << endl;
pMySList->InsertCListNodeFront(333, 1);
pMySList->InsertCListNodeFront(444, 4);
pMySList->PrintCList();
pMySList->InsertCListNodeBack(777, 3);
pMySList->InsertCListNodeBack(888, 5);
pMySList->PrintCList();
pMySList->DeleteCListNodeBack();
pMySList->PrintCList();
pMySList->DeleteCListNodeBack();
pMySList->PrintCList();
pMySList->DeleteCListNodeBack();
pMySList->PrintCList();
return 0;
}代码未经严谨测试,如果有误,欢迎指正.
06 双向链表(doubly linked list)6.1 双向链表又是个什么表？引言代码语言：txt复制我们都知道，在单链表中由于有next指针的存在，需要查找下一个节点的时间复杂度也只是O(1)而已。但是正如生活并不总是那么如意，当我们想再吃一吃回头草的时候，查找上一节点的时间复杂度却变成了O(n)，这真是让人头大。代码语言：txt复制双向链表
代码语言：txt复制不过我们老一辈的科学家早就想到了这个问题，并提出了很好的解决方法。在每个节点中再多加了一个指针域，**从而让一个指针域指向前一个节点，一个指针域指向后一个节点。**也正是如此，就有了我们今天所说的双向链表了。代码语言：txt复制>双向链表(doubly linked list)是在单链表的每个节点中，再设置一个指向其前驱节点的指针域。6.2 双向链表图示国际惯例，这里我们依旧引入了头结点这个玩意儿。不仅如此，为了增加更多的刺激，我们还引入了一个尾节点。
双向链表为空时代码语言：txt复制代码语言：txt复制双向链表在初始化时，要给首尾两个节点分配内存空间。**成功分配后，要将首节点的prior指针和尾节点的next指针指向NULL，这是之后用来判断空表的条件**。同时，当链表为空时，要将首节点的next指向尾节点，尾节点的prior指向首节点。双向链表不为空时
image代码语言：txt复制每一个节点(首位节点除外)的两个指针域都分别指向其前驱和后继。6.3 双向链表存储结构代码描述双向链表一般可以采用如下的存储结构：
代码语言：txt复制/*线性表的双向链表存储结构*/
typedef struct DulNode
{
DataType data;
struct DulNode *prior; //指向前驱的指针域
struct DulNode *next; //指向后继的指针域
}DulNode, *DuLinkList;6.4 双向链表的插入其实大家别看多了一个指针域就怕了。这玩意儿还是跟单链表一样简单得一批，需要注意的就是理清各个指针之间的关系。该指向哪的就让它指向哪里去就OK了。具体的表现为：
image代码描述也很简单：
代码语言：txt复制s->prior=p;
s->next=p->next;
p->next->prior=s;
p->next=s; 6.5 双向链表的删除删除操作和单链表的操作基本差不多的。都是坐下常规操作了。只是多了一个前驱指针，注意一下即可。如下图：
image代码描述：
代码语言：txt复制 p->prior->next=p->next;
p->next->prior=p->prior;
free(p);6.6 双向链表的完整代码其他操作基本和单链表差不多了。在这里就不再做过多赘述，大家直接看完整代码即可。
代码语言：txt复制#include
#include
#include
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int status;
typedef int elemtype;
typedef struct node{
elemtype data;
struct node * next;
struct node * prior;
}node;
typedef struct node* dlinklist;
status visit(elemtype c){
printf("%d ",c);
}
/*双向链表初始化*/
status initdlinklist(dlinklist * head,dlinklist * tail){
(*head)=(dlinklist)malloc(sizeof(node));
(*tail)=(dlinklist)malloc(sizeof(node));
if(!(*head)||!(*tail))
return ERROR;
/*这一步很关键*/
(*head)->prior=NULL;
(*tail)->next=NULL;
/*链表为空时让头指向尾*/
(*head)->next=(*tail);
(*tail)->prior=(*head);
}
/*判定是否为空*/
status emptylinklist(dlinklist head,dlinklist tail){
if(head->next==tail)
return TRUE;
else
return FALSE;
}
/*尾插法创建链表*/
status createdlinklisttail(dlinklist head,dlinklist tail,elemtype data){
dlinklist pmove=tail,pinsert;
pinsert=(dlinklist)malloc(sizeof(node));
if(!pinsert)
return ERROR;
pinsert->data=data;
pinsert->next=NULL;
pinsert->prior=NULL;
tail->prior->next=pinsert;
pinsert->prior=tail->prior;
pinsert->next=tail;
tail->prior=pinsert;
}
/*头插法创建链表*/
status createdlinklisthead(dlinklist head,dlinklist tail,elemtype data){
dlinklist pmove=head,qmove=tail,pinsert;
pinsert=(dlinklist)malloc(sizeof(node));
if(!pinsert)
return ERROR;
else{
pinsert->data=data;
pinsert->prior=pmove;
pinsert->next=pmove->next;
pmove->next->prior=pinsert;
pmove->next=pinsert;
}
}
/*打印链表*/
status printplist(dlinklist head,dlinklist tail){
/*dlinklist pmove=head->next;
while(pmove!=tail){
printf("%d ",pmove->data);
pmove=pmove->next;
}
printf("\n");
return OK;*/
dlinklist pmove=head->next;
while(pmove!=tail){
visit(pmove->data);
pmove=pmove->next;
}
printf("\n");
}
/*返回第一个值为data的元素的位序*/
status locateelem(dlinklist head,dlinklist tail,elemtype data){
dlinklist pmove=head->next;
int pos=1;
while(pmove&&pmove->data!=data){
pmove=pmove->next;
pos++;
}
return pos;
}
/*返回表长*/
status listlength(dlinklist head,dlinklist tail){
dlinklist pmove=head->next;
int length=0;
while(pmove!=tail){
pmove=pmove->next;
length++;
}
return length;
}
/*删除链表中第pos个位置的元素，并用data返回*/
status deleteelem(dlinklist head,dlinklist tail,int pos,elemtype *data){
int i=1;
dlinklist pmove=head->next;
while(pmove&&i pmove=pmove->next; i++; } if(!pmove||i>pos){ printf("输入数据非法\n"); return ERROR; } else{ *data=pmove->data; pmove->next->prior=pmove->prior; pmove->prior->next=pmove->next; free(pmove); } } /*在链表尾插入元素*/ status inserttail(dlinklist head,dlinklist tail,elemtype data){ dlinklist pinsert; pinsert=(dlinklist)malloc(sizeof(node)); pinsert->data=data; pinsert->next=NULL; pinsert->prior=NULL; tail->prior->next=pinsert; pinsert->prior=tail->prior; pinsert->next=tail; tail->prior=pinsert; return OK; } int main(void){ dlinklist head,tail; int i=0; elemtype data=0; initdlinklist(&head,&tail); if(emptylinklist(head,tail)) printf("链表为空\n"); else printf("链表不为空\n"); printf("头插法创建链表\n"); for(i=0;i<10;i++){ createdlinklisthead(head,tail,i); } traverselist(head,tail); for(i=0;i<10;i++){ printf("表中值为%d的元素的位置为",i); printf("%d位\n",locateelem(head,tail,i)); } printf("表长为%d\n",listlength(head,tail)); printf("逆序打印链表"); inverse(head,tail); for(i=0;i<10;i++){ deleteelem(head,tail,1,&data); printf("被删除的元素为%d\n",data); } traverselist(head,tail); if(emptylinklist(head,tail)) printf("链表为空\n"); else printf("链表不为空\n"); printf("尾插法创建链表\n"); for(i=0;i<10;i++){ //inserttail(head,tail,i); createdlinklisttail(head,tail,i); } printplist(head,tail); }PS：学有余力的小伙伴们，可以尝试一下结合这节课介绍的内容，做一个循环双向链表出来哦。 完整结语关于线性表大体内容三节课基本讲完了。不过还有很多好玩的操作，比如链表的逆序，合并，排序等等。这些内容咱们下次有空再聊吧。祝大家学有所成！