首页 > 代码库 > 小猪的数据结构辅助教程——2.4 线性表中的循环链表

小猪的数据结构辅助教程——2.4 线性表中的循环链表

小猪的数据结构辅助教程——2.4 线性表中的循环链表

标签(空格分隔): 数据结构


本节学习路线图与学习要点

技术分享

学习要点

  • 1.了解单链表存在如何的缺点。暴露出来的问题
  • 2.知道什么是循环单链表,掌握单链表的特点以及存储结构
  • 3.掌握循环链表的一些基本操作的实现逻辑。最好能手撕代码

1.循环单链表的引入

技术分享


2.循环链表的特点以及存储结构

循环链表的特点:

上面也说了。比单链表略微高比格一点的地方就是:
链表最后一个结点的指针域指向了头结点而已,这样形成所谓的环。就是循环单链表了。呵呵!
特点的话有:
我们之前推断单链表是否为空:head -> next 是否为NULL就可以
而循环单链表仅仅需:head -> next 是否为head(自身)就可以
相关的操作和单链表还是比較类似的。

存储结构:(和单链表一样~)

typedef int ElemType;
typedef int Status;  
typedef struct LNode
{
    ElemType data;         //数据域
    struct LNode *next;   //指针域 
}LNode;  
typedef struct LNode *LinkList;

单链表的结构图

技术分享

如上图,增加我们的链表非常长的话。从表头找到表尾是非常费时的,所以循环链表往往是设置尾指针


而不是设置头指针。尾指针尾指针尾指针


3.相关基本操作的代码实现

1)构造空表

Status InitList(LinkList L)
{
    L = (LinkList)malloc(sizeof(LNode));
    if(!L)exit(ERROR);
    L ->next = L;   //自己指自己~(头节点指针域指向头结点) 
    return OK;
}

2)将表置空

void ClearList(LinkList L)
{
    LinkList p,q;
    L = L ->next;     //指向头结点 
    p = L ->next;    //指向第一个结点 
    while(p!=L)
    {
        q = p ->next;
        free(p);
        p = q;
    }
    L ->next = L; //自己指自己 
} 

3)推断是否为空表

有头节点的哦~

Status ListEmpty(LinkList L)
{
    return L!=L ->next?

FALSE:TRUE; }

4)销毁表

void DestoryList(LinkList L) 
{
    ClearList(L);  //将表置空
    free(L);    //释放头节点 
    L = NULL; 
}

5)获得表长度

int ListLength(LinkList L)
{
    int i = 0;
    LinkList p = L ->next;  //指向头结点 
    while(p != L)
    {
        i++;
        p = p ->next;
    } 
    return i;
} 

6)获得表中第i个元素的值

Status GetElem(LinkList L,int i,ElemType *e)
{
    int j = 1;
    LinkList p = L ->next ->next;   //指向第一个结点
    if(i <= 0||i >ListLength)return ERROR;  //推断插入位置是否合法 
    while(j < i)
    {
        j++;
        p = p ->next;
    } 
    e = p ->data;
    return OK;
} 

7)查找表中是否存在满足条件的元素

int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) 
{
    int i = 0;
    LinkList p = L ->next ->next;  //指向第一个结点
    while(p != L ->next)
    {
        i++;
        if(compare(p->data,e))return i;
        p = p ->next; 
    } 
    return 0;   //找不到,返回0 
}

8)获得某个节点的直接前驱

Status BeforeElem(LinkList L,ElemType choose,ElemType *before)
{
    LinkList q,p = L ->next ->next;  //指向第一个结点
    q = p ->next;  
    while(q != L ->next)
    {       
        if(q ->data == choose)
        {
            before = p ->data;
            return OK;
        }
        p = q; //继续后移
        q = q ->next; 
    }
    return ERROR;   
}

9)获得某个节点的直接后继

Status NextElem(LinkList L,ElemType choose,ElemType *behind)
{
    LinkList p = L ->next ->next;  //指向第一个结点
    while(p != L)
    {
        if(p ->data == choose)
        {
            behind = p ->next ->data;
            return OK;
        }
    }
}

10)往第i个位置插入元素

Status ListInsert(LinkList L,int i,ElemType e)
{
    LinkList s,p = L ->next;
    int j = 0;
    if(i <= 0 || i > ListLength(L) + 1)return ERROR;  //推断插入位置是否合法
    //寻找插入结点的前一个结点 
    while(j < i - 1) 
    {
        j++;
        p = p ->next;   
    }
    //生成新结点
    s = (LinkList)malloc(sizeof(LNode)); 
    s ->data = e; //将e赋值给新结点
    s ->next = p ->next; //新结点指向原来的第i个结点 
    p ->next = s;   //原i - 1个结点指向新结点 
    //假如插入的位置是表尾,把新的表尾地址给尾指针 
    if(p == L)
    {
        L = s;
    }
    return OK;
} 

步骤解析

普通的插入和单链表都是大同小异,普通结点插入的流程:

技术分享

而特殊情况就是,假如插入位置是尾结点的话。那么还须要让尾指针指向这个新插入的尾结点
就是上面的:L = s;

11)删除表中第i个元素

Status ListDelete(LinkList L,int i,ElemType *e)
{
    LinkList s,p = L ->next;
    int j = 0;
    if(i <= 0||i > ListLength(L))return ERROR;//推断删除位置是否合法 
    //寻找插入结点的前一个结点 
    while(j < i - 1) 
    {
        j++;
        p = p ->next;
    }
    s = p ->next;
    p ->next = s ->next; 
    e = s ->data;
    if(s == L)
    L = p;
    free(q);  //释放结点
    return OK; 
}

步骤解析

和插入一样,删除完后。还要考虑尾指针指向的位置

技术分享

假如删除的是尾结点的话,那么还要让L = p;指向删除结点的前一个节点~

12)遍历循环链表里的全部元素

void ListTraverser(LinkList L,void(*visit)(ElemType))
{
    LinkList p = L ->next ->next;   //指向第一个结点 
    while(p != L ->next)
    {
        visit(p ->data);
        p = p ->next;
    }
    printf("\n");
}

4.本节代码下载:

https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/List/list4.c

<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

小猪的数据结构辅助教程——2.4 线性表中的循环链表