「数据结构 三」C 语言实现循环链表

  • 作者原创,转载请注明出处。

个人博客:renzhe.name

本文主要讲述循环链表,双向链表。

循环链表

循环链表是一种链式存储结构,它的最后一个结点指向头结点,形成一个环。因此,从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致,差别仅仅在于算法中的循环条件有所不同。

在单链表中,判别条件为 p != NULLp->next != NULL,而循环单链表的判别条件为 p != Lp->next != L

具体代码可以访问下面 GitHub 链接。

循环列表

双向链表

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

在双向链表中,若 d 为指向向某一结点的指针,则显然有下面代码:

d->next->prior = d->prior->next = d

在双向循环链表中,有些操作和只需要涉及一个方向指针,算法描述和线性链表的操作相同,但是插入和删除时有很大的不同,在双向链表中需要修改两个方向指针。这里只给出了插入和删除的 C 语言实现代码,具体完整代码可以查看文末 GitHub 链接。

双向链表中的插入

/**
 * 初始条件:双向链表 L 存在,且 1 <= i <= ListLength(L) + 1
 * 操作结果:在 L 中第 i 个元素前插入新的元素 e,L 的长度加 1
 * @param L
 * @param i
 * @param e
 * @return
 */
Status ListInsert(DuLinkList L, int i, ElemType e) {
    DuLinkList p, s;
    if (i < 1 || i > (ListLength(L) + 1)) { //i 值不合法
        return ERROR;
    }
    p = GetElemP(L, i - 1);
    if (!p) { //在 L 中确定第 i 个元素的前驱位置指针 p
        return ERROR; // p = NULL 时,第 i 个元素不存在
    }
    s = (DuLinkList)malloc(sizeof(struct DuLNode));
    if (!s) {
        exit(OVERFLOW);
    }
    s->data = e;
    s->prior = p; //在 i - 1 个元素后插入
    s->next = p->next;
    p->next->prior = s;
    p->next = s;
    return OK;
}

这里使用了一个 GetElemP() 函数确定第 i 个元素位置的指针 p,具体代码如下:

/**
 * 返回 L 中第 i 个元素的地址,若 i = 0 返回头结点,若 i 不存在,返回 NULL
 * @param L
 * @param i
 * @return
 */
DuLinkList GetElemP(DuLinkList L, int i) {
    DuLinkList p = L; //p 指向头结点
    if (i < 0 || i > ListLength(L)) { //i 值不合法
        return NULL;
    }
    for (int j = 1; j <= i; j++) {
        p = p->next;
    }
    return p;
}

双向链表的删除

/**
 * 初始条件:双向链表 L 存在且非空,且 1 <= i <= ListLength(L)
 * 操作结果:删除 L 中的第 i 个元素并用 e 返回其值,L 的长度减 1
 * @param S
 * @param i
 * @param e
 * @return
 */
Status ListDelete(DuLinkList L, int i, ElemType *e) {
    DuLinkList p;
    p = GetElemP(L, i);
    if (!p) { //在 L 中确定第 i 个元素的位置指针 p
        return ERROR; //p = NULL 是,第 i 个元素不存在,也就是 i 值不合法
    }
    *e = p->data;
    p->prior->next = p->next; //修改被删除结点的前驱结点的后继指针
    p->next->prior = p->prior; //修改被删除结点的后继结点的前驱指针
    free(p);
    return OK;
}

想要查看源码可以访问下面 github 链接,如果觉得不错,请给个 Star。

循环列表
双向循环链表

本文属数据结构系列持续更新中

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢? 可以...
    rainchxy阅读 2,040评论 0 6
  • 本文内容取自于小甲鱼的数据结构与算法。http://www.jianshu.com/p/230e6fde9c75 ...
    阿阿阿阿毛阅读 2,936评论 0 7
  • 1.线性表的定义 线性表:零个或多个数据元素的有限序列序列:也就是说元素之间是有顺序的,若元素存在多个,则第一个元...
    e40c669177be阅读 2,099评论 6 15
  • 在上一篇文章中我们简单说了数据结构的概念和数据结构与算法的一些关系,这一篇文章的内容是关于线性表的东西,主要有线性...
    硅谷小虾米阅读 1,300评论 1 3
  • 本文内容:1、 什么是链表?2、 链表共分几类?3、 链表的 C 实现! 总表:《数据结构?》 工程代码 Gith...
    半纸渊阅读 40,068评论 0 54