【数据结构】循环链表(circular linked list) && 双向链表(doubly linked list)

原创

短短的路走走停停

发布于 2019-05-13 20:54:43

2.4K0

发布于 2019-05-13 20:54:43

文章被收录于专栏：程序猿声

本节纲要

预备知识
顺序表(Sequential List)
单链表(Singly Linked List )
静态链表(Static list )
循环链表(circular linked list)
双向链表(doubly linked list)

05 循环链表

5.1什么是循环链表？

前面介绍了单链表，相信大家还记得相关的概念。其实循环链表跟单链表也没有差别很多，只是在某些细节上的处理方式会稍稍不同。

在此之前，大家可以先思考一个问题：单链表中，要找到其中某个节点只需要从头节点开始遍历链表即可，但是有些时候我们的想法是，能不能从任意节点开始遍历，也能找到我们需要的那个节点呢？

其实啊，这个实现也很简单自然，把整个链表串成一个环问题就迎刃而解了。所以，关于循环链表，我们有了如下的定义：

将单链表中的尾节点的指针域由NULL改为指向头结点，使整个单链表形成一个环，这种头尾相接的单链表就可以称之为**单循环链表，简称循环链表(circular linked list)。

5.2 循环链表图示

这里我们讨论的链表还是设置一个头结点（当然，链表并不是一定需要一个头结点）。

当链表为空的时候，我们可以有如下表示：

对于非空链表则可以这样表示：

不得不提的一点

对于循环链表这种设计，我们在遍历的时候的结束条件就不再是p为空的时候结束了。**而是p等于头结点的时候遍历才完成**。这一点希望大家切记。

再多说两句

我们知道，有了头结点，我们可以轻而易举访问第一个节点。但是当要访问最后一个节点时，却要将整个链表扫一遍，效率不可谓不低下……那么，有没有更好的办法呢？

当然是有的，只不过这里我们需要将循环链表再做一个小小的改进，具体表现为：

![image](http://upload-images.jianshu.io/upload_images/10386940-bd00afc352df53be..jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

从上图可以看出，我们抛弃了以往的头指针，取而代之的是采用一个尾指针指向了最后一个节点。而且，因为链表是循环的，当我们需要访问第一个节点时，也very easy！**只需要尾指针往后走一个就到前面了。**

5.3 循环链表代码

关于循环链表的插入删除等操作，其实是和单链表一样的。唯一不同的就是遍历的时候的结束条件不同而已。因此咱们在这里就不做过多篇幅的介绍，直接贴完整代码吧。

循环链表就是末尾指向头形成一个循环的链表.实现思路也很简单,大体把单链表代码做个小小的改动就OK了.这次还是封装在一个类里面吧.

CircleLinkList.h 类头文件,各种声明定义

#pragma once //VC防止头文件重复包含的一条预编译指令

#define status bool
#define OK true
#define ERROR false
#define YES true
#define NO false

template <typename DType>
class Node
{
public:
    DType data;
    Node * pnext;
};
template <typename DType>
class CCircleLinkList
{
private:
    Node<DType> *phead;
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 类的具体实现代码

#include "CircleLinkList.h"

#include <stdio.h>

template <typename DType>
CCircleLinkList<DType>::CCircleLinkList()
{
    cout << "链表创建" << endl;
    InitCList();
}

template <typename DType>
CCircleLinkList<DType>::~CCircleLinkList()
{
    cout << "链表销毁" << endl;
    DestoryCList();
}


//初始化链表
template <typename DType>
status CCircleLinkList<DType>::InitCList()
{
    Node<DType> * ph = new Node<DType>;
    if (ph != NULL)
    {
        ph->pnext = ph;    //尾指向头
        this->phead = ph; //头结点
        return OK;
    }

    return ERROR;

}

//获取链表长度(head_node is not included)
template <typename DType>
int CCircleLinkList<DType>::GetCListLength()
{
    int length = 0;
    Node<DType> * ph = this->phead;
    while (ph->pnext != this->phead)
    {
        length++;
        ph = ph->pnext;
    }
    return length;
}

//增加一个节点 前插法
template <typename DType>
status CCircleLinkList<DType>::AddCListNodeFront(DType idata)
{
    Node<DType> * pnode = new Node<DType>;
    if (pnode != NULL)
    {
        pnode->data = idata;
        pnode->pnext = this->phead->pnext;
        this->phead->pnext = pnode; //挂载

        return OK;
    }

    return ERROR;

}


//增加一个节点 尾插法
template <typename DType>
status CCircleLinkList<DType>::AddCListNodeBack(DType idata)
{
    Node<DType> * pnode = new Node<DType>;
    Node<DType> * ph = this->phead;
    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 <typename DType>
status CCircleLinkList<DType>::IsCListEmpty()
{
    if (this->phead->pnext == this->phead)
    {
        return YES;
    }

    return NO;
}
//获取指定位置节点值(注意，本程序规定0号为头节点，e获取节点的值)
template <typename DType>
status CCircleLinkList<DType>::GetCListIndexNode(DType *e, int index)
{
    Node<DType> * ph = this->phead;
    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 <typename DType>
status CCircleLinkList<DType>::DeleteCListIndexNode(DType *e, int index)
{
    Node<DType> * ph = this->phead;
    int i = 0; //计数器
    Node<DType> * q = nullptr;
    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 <typename DType>
status CCircleLinkList<DType>::SearchCListNode(DType SData, int *pindex)
{
    Node<DType> * ph = this->phead;
    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 <typename DType>
status CCircleLinkList<DType>::InsertCListNodeFront(DType IData, int index)
{
    Node<DType> * ph = this->phead;
    if (ph->pnext == this->phead || index < 1 || index > GetCListLength())
    {
        return ERROR; //异常 处理
    }
    int iCount = 0; //计数器
    Node<DType> * q = nullptr; //备用
    while (ph->pnext != this->phead)
    {
        iCount++;
        q = ph;
        ph = ph->pnext;
        if (iCount == index)
        {
            Node<DType> * p = new Node<DType>;
            p->data = IData;
            p->pnext = ph;
            q->pnext = p;   //前插
            return OK;
        }
    }
    return ERROR;
}
//指定位置后插
template <typename DType>
status CCircleLinkList<DType>::InsertCListNodeBack(DType IData, int index)
{
    Node<DType> * ph = this->phead;
    if (ph->pnext == this->phead || index < 1 || index > GetCListLength())
    {
        return ERROR; //异常 处理
    }
    int iCount = 0; //计数器
    Node<DType> * q = nullptr; //备用
    while (ph->pnext != this->phead)
    {
        iCount++;
        q = ph;
        ph = ph->pnext;
        if (iCount == index)
        {
            Node<DType> * p = new Node<DType>;
            q = ph;
            ph = ph->pnext; //后插就是后一个节点的前插咯
            p->data = IData;
            p->pnext = ph;
            q->pnext = p;
            return OK;
        }
    }
    return ERROR;
}
//清空链表(保留根节点)
template <typename DType>
status CCircleLinkList<DType>::ClearCList()
{
    Node<DType> * ph = this->phead;
    Node<DType> * q = nullptr; //防止那啥，野指针
    ph = ph->pnext;//保留头节点
    while (ph != this->phead)
    {
        q = ph;
        ph = ph->pnext;
        delete q; //释放
    }
    this->phead->pnext = this->phead;
    return OK;
}
//销毁链表(all delete)
template <typename DType>
status CCircleLinkList<DType>::DestoryCList()
{
    ClearCList();
    delete this->phead;//释放头结点 
    return OK;
}

template <typename DType>
status CCircleLinkList<DType>::DeleteCListNodeBack()
{
    Node<DType> * ph = this->phead;
    Node<DType> * q = nullptr; //备用
    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 <typename DType>
void CCircleLinkList<DType>::PrintCList()
{
    Node<DType> * ph = this->phead;
    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 测试代码

#include <iostream>
#include "CircleLinkList.h"
#include "CircleLinkList.cpp"

using namespace std;

int main()
{
    CCircleLinkList<int> * pMySList = new CCircleLinkList<int>;
    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 双向链表又是个什么表？

引言

我们都知道，在单链表中由于有next指针的存在，需要查找下一个节点的时间复杂度也只是O(1)而已。但是正如生活并不总是那么如意，当我们想再吃一吃回头草的时候，查找上一节点的时间复杂度却变成了O(n)，这真是让人头大。

![image](http://upload-images.jianshu.io/upload_images/10386940-945a0cc19f0a832c..jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

双向链表

不过我们老一辈的科学家早就想到了这个问题，并提出了很好的解决方法。在每个节点中再多加了一个指针域，**从而让一个指针域指向前一个节点，一个指针域指向后一个节点。**也正是如此，就有了我们今天所说的双向链表了。

>双向链表(doubly linked list)是在单链表的每个节点中，再设置一个指向其前驱节点的指针域。

6.2 双向链表图示

国际惯例，这里我们依旧引入了头结点这个玩意儿。不仅如此，为了增加更多的刺激，我们还引入了一个尾节点。

双向链表为空时

![image](http://upload-images.jianshu.io/upload_images/10386940-84672b6ea1a556d0..jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

双向链表在初始化时，要给首尾两个节点分配内存空间。**成功分配后，要将首节点的prior指针和尾节点的next指针指向NULL，这是之后用来判断空表的条件**。同时，当链表为空时，要将首节点的next指向尾节点，尾节点的prior指向首节点。

双向链表不为空时
image

每一个节点(首位节点除外)的两个指针域都分别指向其前驱和后继。

6.3 双向链表存储结构代码描述

双向链表一般可以采用如下的存储结构：

/*线性表的双向链表存储结构*/
typedef struct DulNode
{
    DataType data;
    struct DulNode *prior; //指向前驱的指针域
    struct DulNode *next; //指向后继的指针域
}DulNode, *DuLinkList;

6.4 双向链表的插入

其实大家别看多了一个指针域就怕了。这玩意儿还是跟单链表一样简单得一批，需要注意的就是理清各个指针之间的关系。该指向哪的就让它指向哪里去就OK了。具体的表现为：

代码描述也很简单：

s->prior=p;
s->next=p->next;
p->next->prior=s;
p->next=s;

6.5 双向链表的删除

删除操作和单链表的操作基本差不多的。都是坐下常规操作了。只是多了一个前驱指针，注意一下即可。如下图：

代码描述：

    p->prior->next=p->next;
    p->next->prior=p->prior;
    free(p);

6.6 双向链表的完整代码

其他操作基本和单链表差不多了。在这里就不再做过多赘述，大家直接看完整代码即可。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#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<pos){
        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：学有余力的小伙伴们，可以尝试一下结合这节课介绍的内容，做一个循环双向链表出来哦。