美文网首页
双向链表&双向循环链表

双向链表&双向循环链表

作者: AlexChou | 来源:发表于2020-09-22 09:46 被阅读0次

    1. 双向链表

    1.1 结构与初始化

    双向链表
    • 单向链表只能找到后驱。
    • 双向链表能轻松地获取前驱和后继。
    • 插入时，不管是单向还是双向，都需要先找对应位置的前驱。
    • 删除时，由于双向链表可以访问前驱和后继，就不需要先找对应位置的前驱。
    #define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define NOT_FOUND -1

/* ElemType类型根据实际情况而定，这里假设为int */
typedef int ElemType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;

/*线性结构使用顺序表的方式存储*/

//链表结构设计
typedef struct Node {
    struct Node *prior;
    ElemType data;
    struct Node *next;
} Node, *LinkList;

Status InitList(LinkList *L)
{
    //产生头结点，并使用L指向此头结点
    *L = (LinkList)malloc(sizeof(Node));
    //存储空间分配失败
    if (*L == NULL) return ERROR;
    //将头结点的指针域置空
    (*L)->prior = NULL;
    (*L)->next = NULL;
    return OK;
}

    1.2 遍历

    Status ListTraverse(LinkList L)
{
    if (L == NULL) return ERROR; // 空表
    LinkList p = L->next; // 跳过头结点
    while (p) {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

    1.3 插入

    插入节点

    插入时，需要前一个节点来找到后一个节点。

    Status ListInsert(LinkList *L, int loc, ElemType elem)
{
    if (*L == NULL) return ERROR; // 空表
    LinkList p, q;
    p = *L;
    int i = 1;
    for (; p && i < loc; p = p->next, i++); // 找到idx位置
    if(!p || i > loc) return ERROR; // 第idx个元素不存在
    q = (LinkList)malloc(sizeof(Node));
    if (!q) return ERROR; // 没创建出来报错
    q->data = elem;
    q->next = p->next; // q的后继指向p的后继，p-next可能为NULL，q->next也不用显式赋值NULL
    p->next = q; // p的后继指向q
    if (q->next) q->next->prior = q; // q的后继的前驱指向q，最后可能为NULL
    q->prior = p; // q的前驱指向p
    return OK;
}

    1.4 删除

    删除节点

    找到被删除节点，让前后牵手就行了。

    Status ListDeleteLoc(LinkList *L, int loc, ElemType *elem)
{
    if (*L == NULL) return ERROR; // 空表
    LinkList p = (*L)->next;
    int i = 1;
    for (; p && i < loc; p = p->next, i++); // 找到idx位置
    if(!p || i > loc) return ERROR; // 第idx个元素不存在
    p->prior->next = p->next; // p的前驱的后继指向p的后继
    if (p->next) p->next->prior = p->prior; // p的后继的前驱指向p的前驱，最后可能为NULL
    *elem = p->data;
    free(p); // 释放被删除节点
    return OK;
}

    1.5 删除指定元素

    Status ListDeleteElem(LinkList *L, ElemType elem)
{
    if (*L == NULL) return ERROR; // 空表
    LinkList p = (*L)->next;
    while (p && p->data != elem) p = p->next; // 找到对应元素
    if(!p) return ERROR; // 元素elem不存在
    p->prior->next = p->next; // 将p的前驱指向p的后继
    if (p->next) p->next->prior = p->prior; // 将p的后继指向p的前驱，最后可能为NULL
    free(p); // 释放被删除节点
    return OK;
}

    1.6 更新指定位置

    Status ListUpdateElem(LinkList L, int loc, ElemType elem)
{
    if (L == NULL) return ERROR; // 空表
    LinkList p = L->next;
    int i = 1;
    for (; p && i < loc; p = p->next, i++); // 找到idx位置
    if(!p || i > loc) return ERROR; // 第idx个元素不存在
    p->data = elem;
    return OK;
}

    2. 循环双向链表

    2.1 结构与初始化

    线性双向链表 循环双向链表

    循环双向链表的创建实际就是双向链表的尾节点后驱指向头结点，头结点前驱指向尾节点，最终形成一个环。

    #define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define NOT_FOUND -1

/* ElemType类型根据实际情况而定，这里假设为int */
typedef int ElemType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;

/*线性结构使用顺序表的方式存储*/

//链表结构设计
typedef struct Node {
    struct Node *prior;
    ElemType data;
    struct Node *next;
} Node, *LinkList;

Status InitList(LinkList *L, ElemType elem)
{
    //产生头结点，并使用L指向此头结点
    *L = (LinkList)malloc(sizeof(Node));
    //存储空间分配失败
    if (*L == NULL) return ERROR;
    //将头结点的指针指向自己
    (*L)->prior = *L;
    (*L)->next = *L;
    (*L)->data = elem;
    return OK;
}

    依次输入创建双向循环链表：

    Status CreateList2(LinkList *L) {
    ElemType elem;
    LinkList tail = NULL;
    while (1) {
        scanf("%d", &elem); // 输入数据
        if (elem == 0) break; // 输入0时结束
        if (*L == NULL) { // 表是空的时候
            *L = (LinkList)malloc(sizeof(Node)); // 创建表头
            if (*L == NULL) return ERROR; // 没创建出来报错
            (*L)->data = elem; // 存入数据
            tail = *L; // 尾节点，方便后续添加
        } else { // 表不为空
            tail->next = (LinkList)malloc(sizeof(Node)); // 创建新节点
            if (!tail->next) return ERROR; // 没创建出来报错
            tail->next->data = elem; // 存入数据
            tail->next->prior = tail;
            tail = tail->next; // 之前的尾节点指向新节点
        }
    }
    tail->next = *L; // 形成环
    (*L)->prior = tail;
    return OK;
}

    2.1 正向遍历

    Status ListTraverse(LinkList L)
{
    LinkList p = L; // 从自己开始
    do {
        printf("%d ",p->data);
        p = p->next;
    } while (p != L); // 到自己的时候停止
    printf("\n");
    return OK;
}

    2.2 反向遍历

    Status ListTraverseBackwards(LinkList L)
{
    LinkList p = L->prior;
    do {
        printf("%d ",p->data);
        p = p->prior;
    } while (p != L->prior);
    printf("\n");
    return OK;
}

    2.3 插入

    插入节点

    插入时，不管是单向还是双向，都需要先找对应位置的前驱。

    Status ListInsert(LinkList *L, int loc, ElemType elem)
{
    if (*L == NULL || loc < 1) return ERROR; // 空表，位置非法
    LinkList tmp = (LinkList)malloc(sizeof(Node)); // 创建新节点
    if (!tmp) return ERROR; // 没创建出来报错
    tmp->data = elem; // 存入数据
    LinkList target = *L; // 不管loc是多少，都是从头开始找
    if (loc == 1) {
        for (; target->next != *L; target = target->next); // 找到头结点的前一个节点(尾节点)
        *L = tmp; // 头结点变为新节点
    } else {
        int idx = 1;
        for (; target->next != *L && idx < loc - 1; target = target->next, ++idx); // 找到loc结点的前一个节点
        if (target->next == *L || idx > loc - 1) return ERROR; // 找了一圈了，还没到指定位置，越界
    }
    tmp->next = target->next; // 新节点的后驱指向前一个节点的后驱
    target->next = tmp; // 前一个节点指向新节点
    tmp->next->prior = tmp; // 新节点后继的前驱指向新节点
    tmp->prior = target; // 新节点的前驱指向前一个节点
    return OK;
}

    2.4 删除

    删除节点

    删除时，由于双向链表可以访问前驱和后继，就不需要先找对应位置的前驱。

    Status ListDeleteLoc(LinkList *L, int loc, ElemType *elem)
{
    if (*L == NULL || loc < 1) return ERROR; // 空表，位置非法
    LinkList target = *L; // 不管loc是多少，都是从头开始找
    if (loc == 1) {
        if ((*L)->next == *L) { // 如果只有1个节点
            free(*L);
            *L = NULL;
            return OK;
        };
        *L = (*L)->next; // 头节点变为尾节点的下一个节点
    } else {
        int idx = 1;
        for (; target->next != *L && idx < loc; target = target->next, ++idx); // 找到loc节点
        if (target->next == *L || idx > loc) return ERROR; // 找了一圈了，还没到指定位置，越界
    }
    target->prior->next = target->next; // target的前驱指向target的后继
    target->next->prior = target->prior; // 将target的后继的前驱指向target的前驱
    *elem = target->data;
    free(target); // 释放被删除节点
    return OK;
}

    2.5 删除指定元素

    Status ListDeleteElem(LinkList *L, ElemType elem)
{
    if (*L == NULL) return ERROR; // 空表
    LinkList target = *L; // 都是从头开始找
    for (; target->next != *L && target->data != elem; target = target->next); // 找到elem元素所在节点
    if (target->next == *L && target->data != elem) return ERROR; // 找了一圈了，没有找到
    if (target->next == target->prior) { // 前驱和后继相等，说明只有一个节点
        free(target);
        *L = NULL;
        return OK;
    }
    target->prior->next = target->next; // target的前驱指向target的后继
    target->next->prior = target->prior; // 将target的后继的前驱指向target的前驱
    if (*L == target) *L = (*L)->next; // 如果是头节点，移动为下一个
    free(target); // 释放被删除节点
    return OK;
}

    相关文章

      网友评论

          本文标题：双向链表&双向循环链表

          本文链接：https://www.haomeiwen.com/subject/rgrhyktx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|双向链表&双向循环链表|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！