[线性表](5)双向链表

之前我们学习了顺序表，单链表，循环链表，静态链式，动态链式，动态顺序表等，都是通过联合结构体来进行内存操作

以上讨论的所有链式存储结构的结点中只有一个指示直接后继结点的指针域，由此，从某个结点出发，只能顺指针往后寻查其他结点，若要寻查结点的直接前置，则需从表头指针出发。

换句话来说，在单链表中，NextElem的执行时间为O(1)，而PriorElem的执行时间为O(n)。为了克服单链表这种单向性的缺点，可利用双向链表(double linked list)

顾名思义，在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前驱，在C语音中可描述如下：

typedef struct DuLNode
{
    ElemType data;
    struct DuLNode* prior;
    struct DuLNode* next;
}DuLNode, * DuLinkList;

和单链的循环表类似，双向链表也可以由循环表，如下图所示，链表中存有两个环。

在双向链表中，若d为指向表中某一结点的指针(即d为DuLinkList型变量)，则显然有：d->next->prior=d->prior->next=d

这个表示恰当的反映了这种结构特性，在双向链表中，有些操作如：LinstLength，GetElem和LocateElem等仅需涉及一个方向的指针，则它们的算法描述和线性链表的操作相同

但在插入、删除时有很大的不同，在双向链表中需同时修改两个方向上的指针。如下图所示：

删除示例图

插入结点示意图

上述两种操作的算法如下：

Status ListInsert_DuL(DuLinkList& L, int i, Elemtype)
//在带头结点的双向循环线性表L中第i个位置之前插入元素e
//i的合法值为1<=i<=表长+1;
{
    if (!(p = GetElemP_DuL(L, i)))//在L中确定插入位置指针p
    {
        return ERROR;//i等于表长加1时，p指向头结点，i大于表长加1时，p=NULL
    }

    if (!(s = (DuLinkList)malloc(sizeof(DuLNode))))
    {
        return ERROR;
    }

    s->data = e;
    s->prior = p->prior;

    p->prior->next = s;
    p->next = p;
    p->prior = s;

    return OK

}

删除功能：

Status ListDelete_DuL(DuLinkList& L, int i, ElemType& e)
//删除带头结点的双链循环线性表L的第i个元素，i的合法值为1<=i<=表长
{
    if (!(p = GetElemP_DuL(L, i)))//在L中确定第i个元素的位置指针p
    {
        return ERROR;//p=NULL,即第i个元素不存在
    }
    e = p->data;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    return OK
}

上述两种操作用C语言实现为：

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>
typedef struct DuLNode
{
    int data;
    struct DuLNode* prior;
    struct DuLNode* next;
}DuLNode,*DuLinkList;
DuLinkList L, node, p, s;

DuLinkList GetElemP_DuL(DuLinkList, int);
void InfoElem();
void ListInsert_DuL(DuLinkList, int, int);
void ListDelete_DuL(DuLinkList, int, int*);
int main()
{
    L = (DuLinkList)malloc(sizeof(DuLNode));
    L->next = L;
    L->prior = L;

    int a = 10, i, e;
    while (a)
    {
        InfoElem();
        a--;
    }
    s = L->next;
    while (s != L)
    {
        printf("%d ", s->data);
        s = s->next;
    }

    printf("\n请输入需要插入的位置：");
    scanf("%d", &i);
    printf("\n请输入需要插入的元素：");
    scanf("%d", &e);
    ListInsert_DuL(L, i, e);

    printf("\n请输入需要删除的位置：");
    scanf("%d", &i);
    ListDelete_DuL(L, i, &e);
    printf("\n删除的元素为：%d", e);

    system("pause");
    return 0;
}

void ListInsert_DuL(DuLinkList L, int i, int e)
//在带头结点的双向循环线性表L中第i个位置之前插入元素e
//i的合法值为1<=i<=表长+1;
{
    if (!(p = GetElemP_DuL(L, i)))//在L中确定插入位置指针p
    {
        printf("位置不合法");
        return 0;//i等于表长加1时，p指向头结点，i大于表长加1时，p=NULL
    }

    if (!(node = (DuLinkList)malloc(sizeof(DuLNode))))
    {
        printf("内存分配失败");
        return 0;

    }
    node->data = e;

    node->prior = p->prior;
    node->next = p;

    p->prior->next = node;
    p->prior = node;

    printf("插入成功\n");

    p = L->next;
    while (p != L)
    {
        printf("%d ", p->data);
        p = p->next;
    }

}

void ListDelete_DuL(DuLinkList L, int i, int* e)
//删除带头结点的双链循环线性表L的第i个元素，i的合法值为1<=i<=表长
{
    if (!(p = GetElemP_DuL(L, i)))//在L中确定第i个元素的位置指针p
    {
        return 0;//p=NULL,即第i个元素不存在
    }
    *e = p->data;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);

    printf("删除成功\n");
    p = L->next;
    while (p != L)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}

DuLinkList GetElemP_DuL(DuLinkList L,int i)
{
    p = L;
    int count = 0;
    while (p->next != L)
    {
        p = p->next;
        count++;
        if (count == i)
        {
            return p;
        }
    }
    return 0;
}

void InfoElem()
{
    node = (DuLinkList)malloc(sizeof(DuLNode));
    scanf("%d", &node->data);

    p = L;
    while (p->next != L)
    {
        p = p->next;
    }
    node->prior = p;
    p->next->prior = node;

    node->next = p->next;
    p->next = node;
}

VS2019下运行结果：

从上述讨论中可以看到，由于链表在空间的合理利用上和插入、删除时不需要移动等优点，因此在很多场合下，它是线性表的首选存储结构。

然而，它也存在着实现某些基本操作，如求线性表的长度时不如顺序存储结构的缺点，另一方面，由于在链表中，结点之间的关系用指针来表示，则数据元素在线性表中的“位序”的概念已淡化。

而被数据元素在线性表中的“位置”所代替，为此，从实际应用角度出发重新定义线性表及其基本操作。

一个带头结点的线性表类型定义如下：

typedef struct LNode
{
    //结点类型
    ElemType data;
    struct LNode *next
}*Link,*Position;

typedef struct
{
    //链表类型
    Link head, tail;//分别指向线性链表中的头结点和最后一个结点
    int len;//指示线性链表中的数据元素的个数
}LinkList;

Status MakeNode(Link& p, ElemType e);
//分配由p指向的值为e的结点，并返回OK，若分配失败，则返回ERROR

void FreeNode(Link& p);
//释放p所指向的结点

Status InitList(LinkList& L);
//构建一个新链表L

Status DestroyList(LinkList& L)
//销毁线性表L，L不再存在

Status ClearList(LinkList& L);
//将线性表L重置为空表，并释放原链表的结点空间

Status InsFirst(Link h, Link s);
//已知h指向线性链表的头结点，将s所指结点插入在第一个结点之前

Status DelFirst(Link h, Link& q);
//已知h指向线性链表的头结点，删除链表中第一个结点并以q返回

Status Append(LinkList& L, Link s);
//将指针s所指(彼此以指针相链)的一串结点链接在线性链表L的最后一个结点
//之后，并改变链表L的尾指针指向新的尾结点

Status Remove(LinkList& L, Link& q);
//删除线性链表L中的尾结点并以q返回，改变链表L的尾指针指向新的尾结点

Status InsBefore(LinkList& L, Link& p, Link s);
//已知p指向线性链表L中的第一个结点，将s所指结点插入在p所指结点之前
//并修改指针p指向新插入的结点

Status InsAfter(LinkList& L, Link& p, Link s);
//已知p指向线性链表L中的第一个结点，将s所指结点插入到o所指结点之后
//并修改指针p指向新插入的结点

Status SerCurElem(Link& p, ElemType e);
//已知p指向线性链表中的一个结点，用e更新p所指结点内的值

ElemType GetCurElem(Link p);
//已知p指向线性链表中的一个结点，返回p所指结点中的数据元素

Status ListEmpty(LinkList L);
//若线性链表L为空表，则返回TRUE，否则返回FALSE

int ListLength(LinkList L);
//返回线性表L中元素个数

Position GetHead(LinkList L);
//返回线性链表中头结点的个数

Position GetLast(LinkList L);
//返回线性链表L中最后一个结点的位置

Position PriorPos(LinkList L, Link p);
//已知p指向线性链表在L中的一个结点，返回p所指结点的直接前驱的位置
//若无前驱，则返回NULL

Position NextPos(LinkList L, Link p);
//已知p指向线性链表在L中的一个结点，返回p所指结点的直接后继的位置
//若无后继，则返回NULL

Status LocatePos(LinkList L, int i, Link& p);
//用p指示线性链表L中第i个结点的位置，并返回OK，i值不合法时返回ERROR

Position LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType);
//返回线性表链表L中第1个与e满足函数compare()判断关系的元素位置
//若不存在这样的元素，则返回NULL

Status ListTraverse(LinkList L, Status(*visit));
//依次对L的每个元素调用函数visit（），一旦visit（）失败，则操作失败

上述操作具体实现请看——基本操作补充笔记，补充笔记所有操作基于单链上

上述定义的线性链表的基本操作中，除了DestroyList、ClearList、Remove、InsBe-fore、PriorPos、LocatePos、LocateElem和ListTraverse的时间复杂度和表长成正比之外，其他操作的时间复杂度都和表长无关，Append操作的时间复杂度则和插入的结点数成正比。

利用做这些基本操作，容易实现如在第i个元素之前插入元素或删除第i个元素。或合并两个线性表等操作，如下列算法所示：

Status ListInsert_L(LinkList L, int i, int e)
//在带头结点的单链线性表L的第i个元素之前插入元素e
{
    Link h,s;
    if (!LocatePos(L, i - 1, h))
    {
        return ERROR; //i值不合法
    }
    if (!MakeNode(s, e))
    {
        return ERROR;//结点分配失败
    }

    InsFirst(h, s);//对于从第i个结点开始的链表，第i-1个结点是它的头结点
    {
        return OK;
    }
}

合并链表：

Status MergeList_L(LinkList La, LinkList Lb, LinkList Lc,
                                              int (*compare)(int,int))
//已知单链表La和Lb的元素按值非递减排列
//归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列

{
    Link ha, hb, pa, pb, q;
    int a, b;
    if (!InitList(Lc))
    {
        return ERROR;//存储空间分配失败
    }
    ha = GetHead(La);
    hb = GetHead(Lb);//ha和hb分别指向La和Lb的头结点
    pa = NextPos(Lb,ha);
    pb = NextPos(Lb,hb);//pa和pb分别指向La和Lb中当前节点

    while (pa && pb)
    {
        a = GetCurElem(pa);
        b = GetCurElem(pb);

        if ((*compare)(a, b) <= 0)
        {
            DelFirst(hb, q);
            Append(Lc, q);
            pa = NextPos(La, ha);
        }
        else
        {
            DelFirst(hb, q);
            Append(Lc, q);
            pa = NextPos(La, hb);
        }
    }
    if (pa)
    {
        Append(Lc, pa);
    }
    else
    {
        Append(Lc, pb);
    }
    FreeNode(ha);
    FreeNode(hb);
}

完整的C语言测试代码如下：

#define OK 1
#define ERROR 0

#include<stdio.h>
#include<stdlib.h>

typedef int Status;

typedef struct LNode
{
    int data;
    struct LNode* next;
}*Link,*Position;

typedef struct
{
    Link head, tail;
    int len;
}LinkList;
LinkList La, Lb, Lc;
Status InitList(LinkList*);
Status MergeList_L(LinkList, LinkList, LinkList, int(*compare)(int, int));
Status InfoElem(LinkList);
Position GetLast(LinkList);
Position GetHead(LinkList);
Position NextPos(LinkList, Link);
int GetCurElem(Link);
int Maxcompare(int, int);
Status DelFirst(Link, Link*);
Status Append(LinkList, Link);
void FreeNode(Link);
Status ListTraverse(LinkList, Status(*visist)(Link));
Status PRINTF(Link);

int main()
{
    if (!InitList(&La))
    {
        return ERROR;
    }
    if (!InitList(&Lb))
    {
        return ERROR;
    }

    int i, j;
    printf("请输入La中的元素个数：");
    scanf_s("%d", &i);
    while (i)
    {
        InfoElem(La);
        i--;
    }
    ListTraverse(La, PRINTF);

    printf("\n请输入Lb中的元素个数：");
    scanf_s("%d", &j);
    while (j)
    {
        InfoElem(Lb);
        j--;
    }
    ListTraverse(Lb, PRINTF);

    MergeList_L(La, Lb, Lc,Maxcompare);

    //ListTraverse(Lc, PRINTF);

    system("pause");
    return 0;

}
Status InitList(LinkList *L)
{
    L->head = (Link)malloc(sizeof(struct LNode));
    if (L->head == NULL)
    {
        return ERROR;
    }
    L->head->next = NULL;
    L->len = 0;
    return OK;
}

Status InfoElem(LinkList L)
{
    Link node;
    node = (Link)malloc(sizeof(struct LNode));
    printf("请输入元素：");
    scanf_s("%d", &node->data);
    L.tail = GetLast(L);
    node->next = L.tail->next;
    L.tail->next = node;
    L.tail = node;
    L.len++;
    return OK;
}

Position GetLast(LinkList L)
{
    Link last;
    last = L.head;
    while (last->next != NULL)
    {
        last = last->next;
    }
    return last;
}
Position GetHead(LinkList L)
{
    return L.head;
}
Position NextPos(LinkList L, Link p)
{
    if (p->next == NULL)
    {
        return 0;
    }
    return p->next;
}
int GetCurElem(Link p)
{
    return p->data;
}
int Maxcompare(int a, int b)
{
    if (a <= b)
    {
        return 0;
    }
    return 1;
}
Status DelFirst(Link h, Link* s)
{
    Link q;
    q = h->next;
    h->next = q->next;
    q->next = NULL;
    *s = q;
    return OK;
}
Status Append(LinkList L, Link s)
{
    Link q;
    q = L.head;
    while (q->next != NULL)
    {
        q = q->next;
    }
    q->next = s;
    L.tail = s;
}

void FreeNode(Link q)
{
    free(q);
    q = NULL;
}
Status ListTraverse(LinkList L, Status(*visist)(Link))
{
    printf("开始观察：");
    Link q = L.head->next;
    while (q != NULL)
    {
        if (!(visist(q)))
        {
            return ERROR;
        }
        else
        {
            q = q->next;
        }
    }
}
Status PRINTF(Link q)
{
    printf("%d ", q->data);
    return OK;
}

Status MergeList_L(LinkList La, LinkList Lb, LinkList Lc, int(*compare)(int, int))
{
    Link ha, hb, pa, pb, q, pc;
    int a, b;

    if (!InitList(&Lc))
    {
        return ERROR;
    }
    ha = GetHead(La);
    hb = GetHead(Lb);
    pa = NextPos(La, ha);
    pb = NextPos(Lb, hb);

    int i = 0;
    while (pa && pb)
    {
        i++;
        a = GetCurElem(pa);
        b = GetCurElem(pb);

        if (((*compare)(a, b) <= 0))
        {
            printf("pa:第%d次：%d\n", i, pa->data);
            DelFirst(ha, &q);
            Append(Lc, q);
            pa = NextPos(La, ha);
        }
        else
        {
            printf("\n");
            printf("pb第%d次：%d\n", i, pb->data);
            DelFirst(hb, &q);
            Append(Lc, q);
            pb = NextPos(Lb, hb);
        }
    }

    if (pa)
    {
        Append(Lc, pa);
        printf("pb第%d次：%d\n", i+1, pa->data);
    }
    else
    {
        Append(Lc, pb);
        printf("pb第%d次：%d\n", i+1, pb->data);
    }
    pc = Lc.head->next;
    printf("\n\nLc：");
    ListTraverse(Lc, PRINTF);

    FreeNode(ha);
    FreeNode(hb);

    return OK;
}

本文链接：