数据结构与算法-双向链表&双向循环链表

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;
}

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,294评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,493评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,790评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,595评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,718评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,906评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,053评论 3赞 410
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,797评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,250评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,570评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,711评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,388评论 4赞 332
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,018评论 3赞 316
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,796评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,023评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,461评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,595评论 2赞 350