双向链表基本操作

---

title: 双向链表基本操作
date: 2020-10-12 21:12:51
tags: 双向链表
categories: 数据结构

---

    双向链表的基本操作

1. 初始化一个空的双向链表
2. 尾插添加结点
3. 顺序随机掉头逆序打印双向链表
4. 按序号添加结点
5. 按序号删除结点

// 双向链表
#include <stdio.h>
#include <stdlib.h>

typedef struct linkList
{
    int data;
    struct linkList *next;
    struct linkList *prior;
} node, *list;

// 初始化一个空的双向链表
void InitList(list *ppHead)
{
    list p = (list)malloc(sizeof(node));
    *ppHead = p;
    p->data = 0;
    p->next = NULL;
}

// 向双向链表中批量添加5个值
void AddNode(list pHead)
{
    list temp = pHead;
    for (int i = 0; i < 6; i++)
    {
        list p = (list)malloc(sizeof(node));
        temp->next = p;
        p->data = i + 1;
        p->next = NULL;
        p->prior = temp;
        temp = temp->next;
    }
}
// 打印双向链表
void PrintList(list pFirstNode)
{
    // 先打印双向链表
    list temp = pFirstNode;
    printf("显示双向链表信息:\n");
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// 顺序然后逆序打印双向链表
void OrderAndReverseOrderPrint(list pHead)
{
    list temp = pHead;
    printf("利用双链表的特性实现先顺序打印然后逆序打印\n");
    while (temp->next != NULL)
    {
        printf("%d ", temp->next->data);
        temp = temp->next;
    }
    // 现在temp的值为最后一个结点的地址,然后顺着打印即可
    while (temp != pHead)
    {
        printf("%d ", temp->data);
        temp = temp->prior;
    }
    printf("\n");
}

// 按序号添加一个结点，i为序号，data为数据
void AddBySerial(list pHead, int i, int data)
{
    // 添加结点，要添加的结点的前一个结点的范围是
    // 0结点(头结点)一直到最后的NULL结点
    printf("在第 %d 个结点处插入数据为 %d 的结点\n", i, data);
    int j = 0;
    list temp = pHead;
    for (j = 0; j < i - 1 && temp != NULL; j++)
        temp = temp->next;
    if (temp == NULL || j > i - 1)
    {
        printf("传入的序号 %d 不在允许插入的范围内", i);
        return;
    }
    // 如果是要尾插，那么还需要特殊拿出来考虑，因为尾结点的后面没有结点了
    list p = (list)malloc(sizeof(node));
    p->data = data;
    if (temp->next == NULL)
    {
        p->next = NULL;
        p->prior = temp;
        temp->next = p;
        return;
    }
    p->next = temp->next;
    temp->next->prior = p;
    p->prior = temp;
    temp->next = p;
}

// 按照序号删除一个结点
void DeleteSerial(list pHead, int i)
{
    // temp 现在指向第一个结点
    list temp = pHead->next;
    int j;
    printf("删除序号为 %d 的结点\n", i);
    // 不同于单链表的删除，双向链表在删除结点时，直接找到要删除结点的
    // 地址即可，单链表需要找到被删除结点的前一个结点的地址
    for (j = 1; j < i && temp != NULL; j++)
        temp = temp->next;
    if (j > i || temp == NULL)
    {
        printf("找不到要删除的序号为 %d 结点\n", i);
        return;
    }
    // 要删除的是尾结点
    if (temp->next == NULL)
        temp->prior->next = NULL;
    else
    {
        temp->prior->next = temp->next;
        temp->next->prior = temp->prior;
    }
    free(temp);
    printf("%d 号结点删除成功!\n", i);
}
int main(void)
{
    list pHead = NULL;
    InitList(&pHead);
    AddNode(pHead);
    PrintList(pHead->next);
    // 数字为要删除的结点序号
    DeleteSerial(pHead, 0);
    DeleteSerial(pHead, 6);
    PrintList(pHead->next);
    OrderAndReverseOrderPrint(pHead);
    AddBySerial(pHead, 6, 6);
    PrintList(pHead->next);
    OrderAndReverseOrderPrint(pHead);

    AddBySerial(pHead, 1, 0);
    PrintList(pHead->next);
    OrderAndReverseOrderPrint(pHead);

}