首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【数据结构】循环链表(circular linked list) && 双向链表(doubly linked list)

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

原创
作者头像
短短的路走走停停
发布2019-05-13 20:54:43
1.9K0
发布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 循环链表图示

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

  • 当链表为空的时候,我们可以有如下表示:
image
image
  • 对于非空链表则可以这样表示:
image
image
  • 不得不提的一点
对于循环链表这种设计,我们在遍历的时候的结束条件就不再是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
    image
每一个节点(首位节点除外)的两个指针域都分别指向其前驱和后继。

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

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

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

6.4 双向链表的插入

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

image
image

代码描述也很简单:

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

6.5 双向链表的删除

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

image
image

代码描述:

    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:学有余力的小伙伴们,可以尝试一下结合这节课介绍的内容,做一个循环双向链表出来哦。

完整结语

关于线性表大体内容三节课基本讲完了。不过还有很多好玩的操作,比如链表的逆序,合并,排序等等。这些内容咱们下次有空再聊吧。祝大家学有所成!

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 更多精彩尽在微信公众号【程序猿声】
  • 本节纲要
  • 05 循环链表
    • 5.1什么是循环链表?
      • 5.2 循环链表图示
        • 5.3 循环链表代码
        • 06 双向链表(doubly linked list)
          • 6.1 双向链表又是个什么表?
            • 6.2 双向链表图示
              • 6.3 双向链表存储结构代码描述
                • 6.4 双向链表的插入
                  • 6.5 双向链表的删除
                    • 6.6 双向链表的完整代码
                    • 完整结语
                    领券
                    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档