37.2° Blog

1.头插法创建双链表

问题

头插法创建双链表

算法思想

• 注意在插入结点时的操作；
• 更新新结点的后继指针；
• 若后继结点不为空，更新后继结点的前驱指针；
• 更新新结点的前驱指针；
• 更新前驱结点的后继指针。

代码

void createHeadDuLinkList(DuLinkList& DL, ElemType* arr, int arrLength)
{
    DL = (DuLinkNode*)malloc(sizeof(DuLinkNode));
    DL->next = NULL;
    DL->prior = NULL;
    DuLinkNode* tmpNode = NULL;
    for (int i = 0; i < arrLength; i++)
    {
        tmpNode = (DuLinkNode*)malloc(sizeof(DuLinkNode));
        tmpNode->data = arr[i];
        // 在DL头结点中插入tmpNode结点
        // 更新结点的后继指针
        tmpNode->next = DL->next;
        // 若后继结点不为空，更新后继节点的前驱指针
        if (DL->next != NULL)
            DL->next->prior = tmpNode;
        // 更新新结点的前驱指针
        tmpNode->prior = DL;
        // 更新前驱结点的后继指针
        DL->next = tmpNode;
    }
}

2. 双链表结点删除

问题

双链表结点的删除操作

算法思想

• 更新前驱结点的后继指针
• 若后继指针存在，更新后继结点的前驱指针

代码

void deleteDuLinkListNode(DuLinkNode* pNode)
{
    // 更新前驱结点的后继指针
    pNode->prior->next = pNode->next;
    // 若后继指针存在，更新后继结点的前驱指针
    if (pNode->next != NULL)
        pNode->next->prior = pNode->prior;
    free(pNode);
}

3.遍历

• 向后遍历

while(p != NULL)
{
    p = p->next;
}

• 前向遍历

while(p != NULL)
{
    p = p->prior;
}

• 前向遍历（跳过头节点）

while(p->prior != NULL)
{
    p = p->prior;
}

4. 双链表prior指针域排序

问题

设计一个算法，将带头结点的双向链表中的原有顺序保存在每个结点的next域中，而prior域将所有结点按其值从小到大的顺序连接起来。

算法思想

• 将头结点（不存数据）和头结点后的第一个数据结点的prior指针连成一个环，将后续数据结点插入环中；
• 待插入结点从第二个结点开始，使用next指针循环遍历后续结点，依次插入prior指针连成的环中；

代码

void orderPriorDuLinkList(DuLinkList DL)
{
    // 头结点，不存储任何数据
    DuLinkNode* headNode = DL;
    // 将头结点和头结点之后第一个数据结点的prior指针连成环，将后续数据插入环中
    headNode->next->prior = headNode;
    headNode->prior = headNode->next;
    // 从第二个数据结点开始插入，顺着next指针，依次插入
    DuLinkNode* insertNode = headNode->next->next;
    DuLinkNode* pNode = NULL;
    DuLinkNode* preNode = NULL;
    // 从前往后依次取数据结点
    while (insertNode != NULL)
    {
        // 每一轮查找从头结点沿着prior指针查找
        preNode = headNode;
        pNode = headNode->prior;
        // 因现将prior指针连成一个环，headNode为头指针，遍历结束表尾为headNode
        // 寻找插入位置，当pNode结点的值大于待插入结点，
        // 将待插入结点插入pNode之前（preNode）之后
        while (pNode != headNode && pNode->data < insertNode->data)
        {
            preNode = pNode;
            pNode = pNode->prior;
        }
        // 将preNode的prior指针指向待插入指针
        preNode->prior = insertNode;
        // 待插入指针指向pNode，就将待插入指针插入值pNode之前（preNode）之后
        insertNode->prior = pNode;
        // 更新待插入结点
        insertNode = insertNode->next;
    }
}