数据结构-线性表|顺序表|链表(下)

1

1

1

哈喽。各位小伙伴好久不见,热心的小编赶在开学季又来给大家送上满满的干货了。祝大家开心快乐!

继上两次咱们聊了顺序表、单链表、静态链表等知识。那么热爱学习的小编这次又来给大家推送新的知识了,今天要讲的知识是循环链表和双向链表,这节讲完,线性表这部分就算完结撒花了。好了,废话不多说,咱们开始学习吧……

内容提要:

*预备知识

*顺序表(Sequential List)

*单链表(Singly Linked List )

*静态链表(Static list )

*循环链表(circular linked list)

*双向链表(doubly linked list)

05 循环链表

5.1什么是循环链表?

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

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

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

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

5.2 循环链表图示

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

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

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

不得不提的一点

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

再多说两句

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

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

从上图可以看出,我们抛弃了以往的头指针,取而代之的是采用一个尾指针指向了最后一个节点。而且,因为链表是循环的,当我们需要访问第一个节点时,也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),这真是让人头大。

双向链表

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

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

6.2 双向链表图示

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

双向链表为空时

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

双向链表不为空时

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

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

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

1

END

1

-The End-

原文发布于微信公众号 - 数据魔术师(gh_39567a079597)

原文发表时间:2018-03-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏钟绍威的专栏

Properties+重温Map+本地计数器Map方法Properties的方法用Properties的好处

昨天想写一个记账本,发现并不能把项目名称与内容关联起来,于是乎我想到了map,可是又不知道map储存到文件中又怎么读出来,幸好今天遇到了properties ...

2027
来自专栏Python攻城狮

MySQL中char、varchar和text的区别

它们的存储方式和数据的检索方式都不一样。 数据的检索效率是:char > varchar > text 空间占用方面,就要具体情况具体分析了。

824
来自专栏LeetCode

LeetCode 162. Find Peak Element

题目大意:在一个数组中寻找一个峰值,题目的最后一句话是一个关键,如果没有这句话,我想大多数首先想到的就是一个一个的判断,这样的话算法复杂度是O(n),实际上本题...

930
来自专栏java工会

Java开发者容易犯的十个错误

Arrays.asList()将返回一个数组内部是私有静态类的ArrayList,这不是java.util.ArrayList类,java.util.Array...

1070
来自专栏小勇DW3

LinkedHashMap 源码分析

LinkedHashMap 继承自 HashMap,在 HashMap 基础上,通过维护一条双向链表,解决了 HashMap 不能随时保持遍历顺序和插入顺序一致...

1753
来自专栏WeaponZhi

轻松初探Python(六)—函数

这是「AI 学习之路」的第 6 篇,「Python 学习」的第 6 篇 题外话 这周工作日 5 天,我并没有更新文章,但大家并不要以为小之懒惰了。正好相反,自从...

3617
来自专栏Java3y

Java集合总结【面试题+脑图】,将知识点一网打尽!

2755
来自专栏Java Web

Java 面试知识点解析(一)——基础知识篇

2475
来自专栏Java3y

LinkedHashMap就这么简单【源码剖析】

1604
来自专栏CaiRui

Mysql-7-mysql函数

1.数学函数   用来处理数值数据方面的运算,主要的数学函数有:绝对值函数,三角函数,对数函数,随机函数。使用数学函数过程中,如果有错误产生,该函数会返回nul...

1997

扫码关注云+社区

领取腾讯云代金券