双向链表

在双向链表中，每个结点都有两个指针域，用于存放前驱结点地址和后继结点地址。与单链表相比，双向链表可以进行两个方向的查找。

1.初始化双向链表

1.1双向链表的储存结构

typedef struct DNode {
    int data;
    struct DNode* next,* prior;
}DNode, *DLinkList;

1.2双向链表的初始化

1.2.1头插法

1.2.1.1算法思想

先建立一个空链表
利用循环，每次读取数据，生成新结点，将读取的数据放在新结点的数据域中
将新结点插入当前链表的表头结点的后面
读取到结束标识9999结束

1.2.1.2算法设计

DLinkList Dlist_head_insert(DLinkList& DL) 
{
    DLinkList s;
    int x;
    DL = (DLinkList)malloc(sizeof(DNode));
    DL->next = NULL;
    DL->prior = NULL;
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (DLinkList)malloc(sizeof(DNode));
        s->data = x;//把读取的值 给新空间中的data成员
        s->next = DL->next;//让新结点的next指针指向链表的第一个元素
        if (DL->next!=NULL)
        { 
            DL->next->prior = s;
        }
        s->prior = DL;
        DL->next = s;
        scanf("%d", &x);
    }
    return DL;
}

1.2.2尾插法

1.2.2.1算法思想

先建立一个空链表L
利用循环，每次读取数据，生成新结点，将读取的数据放在相信结点的数据域中
增加一个新尾指针p，使之指向当前单链表的表尾
将新结点插入尾结点（也就是p指向的结点）的后面
p重新指向表尾
读取到结束标识9999停止

1.2.2.2算法设计

DLinkList Dlist_end_insert(DLinkList& DL) 
{
    DLinkList s,p;
    int x;
    DL = (DLinkList)malloc(sizeof(DNode));
    DL->next = NULL;
    DL->prior = NULL;
    p = DL;
    scanf("%d", &x);
    while (x != 9999) 
    {
        s = (DLinkList)malloc(sizeof(DNode));
        s->data = x;
        s->prior = p;
        p->next = s;
        s->next = NULL;
        p = p->next;
        scanf("%d", &x);
    }
    return DL;
}

2.双向链表的查

2.1按位置查找

问题要求:查找位置为a的元素

2.1.1算法思想

从头结点（L->next）开始顺着链域扫描，用指针p指向当前扫描的结点
用i做计数器，累计当前扫描过的节点数
当a==i时，返回p

2.1.2算法设计

DLinkList LocateElem(DLinkList& DL, int a)
{
    DLinkList p = DL;
    if (a < 1) 
    {
        printf("查询位置违法\n");
        return NULL;
    }
    int i = 0;
    while (p ->next!= NULL)
    {
        p = p->next;
        i++;
        if (i == a)
        {
            return p;
            break;
        }
    }
    printf("表长不够，查询不到该位置\n");
    return NULL;
}

2.2按值查找

问题要求:查找为a的元素

2.2.1算法思想

从头结点（L->next）开始顺着链域扫描，用指针p指向当前扫描的结点
用i做计数器，累计当前扫描过的节点数
判断扫描到结点的data域值是否等于a
如果不等于a，则接着扫描；等于a，则返回当前的在表的位置i

2.2.2算法设计

int LocateElem2(DLinkList DL, int a)
{
    DLinkList p = DL;
    int i = 0;
    while (p->next != NULL)
    {
        p = p->next;
        i++;
        if (p->data == a)
        {
            return i;
            break;
        }
    }
    return false;
}

3.双向链表的增（插入）

在表中的第i个位置前插入元素e

3.1算法思想

查找：在双向链表中找到第i-1个结点，并用指针p指示
申请：申请一个新结点s，将气数据域的值赋值为e
插入：通过修改指针域将新结点s挂入单链表L

3.2算法设计

bool InsertDList(DLinkList DL,int i,int e) 
{
    DLinkList p,s;
    p = LocateElem1(DL, i - 1);
    if (p != NULL&&p->next != NULL) 
    {
        s = (DLinkList)malloc(sizeof(DNode));
        s->data = e;
        s->next = p->next;
        p->next->prior = s;
        p->next = s;
        s->prior = p;
        return true;
    }
    printf("插入失败！\n");
    return false;
}

4.双向链表的删除

删除表中的第i个位置的元素

4.1算法思想

找到第i-1个结点，用指针p指示
用q指示第i个结点也就是（p->next）
将p指向结点的next指向q指向结点的下一个结点
删除第i个结点

4.2算法设计

bool DelDList(DLinkList DL,int i) 
{
    DLinkList p,q;
    p = LocateElem1(DL,i-1);

    if (p->next != NULL&&p != NULL) 
    {
        q = p->next; 
        p->next = q->next;
        if (q->next != NULL) 
        {
            q->next->prior = p;
        }
        free(q);
        return true;
    }
    return false;
}

5.双向链表的改

问题要求：修改单链表第i个元素的值

5.1算法思想

找到第i个元素,用p指示
修改它的data域的值为e

5.2算法设计

bool UpdataDList(LinkList DL,int i，int e)
{
    LinkList p = LocateElem1(L, i);//利用按序号查找的方法，找到i个结点
    if(NULL==p->next||NULL==p)
    {
        return false;
    }
    p->data=e;
    return true;
}

标签：结点,DL,next,链表,DLinkList,双链,NULL
From： https://www.cnblogs.com/wlb429/p/16732038.html

双链表