线性表（三）-双向链表的表示与实现

在上一篇文章中线性双链表，我们分析并讨论了线性表的链式存储结构. 链存储结构表示的线性表主要分为三种类型: 单链接列表，单循环链接列表和双循环链接列表. 单链列表和单循环链列表已在上一篇文章中进行了解释. 本文将分析并讨论链式存储结构中双链表的实现原理.

线性表格概述

线性表（1）-序列表

线性表（二）-单链表的表示与实现

线性表（三）-双向链表的表示与实现

双向链接列表中的每个节点除了后继指针字段之外，还具有前驱指针字段. 像单链表一样，双链表也具有两个结构: 引导节点和非引导节点. 具有前导节点的双向链表更为常见. 另外，双链表还可以具有循环和非循环两种结构，并且更经常使用循环结构的双链表. 本文仅讨论带有前导节点的双向循环链表的实现.

在双循环链表中线性双链表，每个节点包括三个字段，即数据字段，下一个字段和优先级字段，其中数据字段是数据字段，下一个字段是指向后续节点的指针字段，优先级字段是指向前一节点的指针字段. 下图显示了双向循环链表的节点的结构.

用C语言表示的双向循环链接列表总结如下:

typedef struct Node{
    DataType   data;//存放数据
    struct Node *next; //存放指向后继结点的指针
    struct Node *prior; //存放指向前驱结点的指针
} DLNode;

在单链表中找到当前节点的后继节点并不困难. 您可以使用当前节点的下一个指针，但是要查看当前节点的前驱节点，必须再次从头指针头开始. 对于需要频繁搜索当前节点的后继节点和当前节点的前驱节点的程序，使用单个链表的时间效率非常低，而双链表是有效解决问题的最佳选择这种类型的问题.

带有前导节点的双向循环链表的如下图所示.

在双向循环链接列表中，如果指针p指向双向循环链接列表中的第i个节点，则p-> next指向第i + 1个节点，p-> next-> prior仍指向到第i个节点Node，即p-> next-> prior == p;同样，p-> prior指向第i-1个节点，p-> prior-> next仍然指向第i个节点，即p-> prior-> next == p.

在初始化操作之前，头指针参数head没有特定的地址值. 在初始化操作期间，header指针参数head仅获得特定的地址值，并且该地址值应返回给调用函数，因此head指针的参数head应该设计为指针的指针类型.

void ListInitiate(DLNode **head) {
    *head = (DLNode *) malloc(sizeof(DLNode));
    (*head)->prior = *head;
    (*head)->next = *head;
}

双循环链表的第i个头位于头节点（

）在位置之前插入数据元素x的节点. 如果插入成功，则返回1. 如果插入失败，则返回0.

int ListInsert(DLNode *head, int i, DataType x) {
    DLNode *p = head->next;
    int j = 0;
    while (p != head && j < i) {
        p = p->next;
        j++;
    }
    if (j != i) {
        printf("插入的位置错误");
        return 0;
    }
    DLNode *s = (DLNode *) malloc(sizeof(DLNode));
    s->data = x;
    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;
    return 1;
}

首先在链表中的第i个位置找到节点，用p表示. 动态申请节点存储空间并由指针s指示，并将数据元素x分配给新节点的数据元素字段s-> data = x；修改新节点的前驱节点的指针，使其指向p的前驱节点: S-> prior = p-> prior，p的前驱节点的后继节点的指针指向新节点s: p ->优先级->下一个= s. 新节点s的后续节点指针指向p: s-> next = p. p的前体节点指针指向s.

插入操作如下图所示:

删除带有头节点的双循环链表的第i个（

）节点. 删除的节点的数据字段值由x带回来. 如果删除成功，则返回1，如果删除失败，则返回0.

int ListDelete(DLNode *head, int i, DataType *x) {
    DLNode *p = head->next;
    int j = 0;
    while (p->next != head && j < i) {
        p = p->next;
        j++;
    }
    *x = p->data;
    if(j!=i){
        printf("删除位置参数错误");
        return 0;
    }
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    return 1;
}

首先在链表中的第i个位置找到节点，用p表示. 将第i个节点的数据元素的值分配给x: * x = p-> data. 修改p的前驱节点的后继节点的指针，使其指向p的后继节点: p-> prior-> next = p-> next. 指向修改p的后继节点的前任节点的指针指向p的前任节点.

删除操作如下图所示:

int ListLength(DLNode *head){
    DLNode *p = head;
    int size = 0;
    while (p->next != head){
        p = p->next;
        size++;
    }
    return size;
}

指针变量p指向循环之前的头节点，并且将计数变量大小分配为0. 循环结束的条件是p-> next！= head. 在循环中，每次指针p指向下一个节点的值时，计数变量的大小都会增加1. 该函数返回计数变量的大小.

像单链表一样，双循环链表的节点空间由程序动态请求，并且系统仅负责自动回收程序中静态分配的内存空间.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-244287-1.html