数据结构-4-双循环链表

//双循环链表

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


typedef struct Node                 //定义结点结构体
{
    int data;
    struct Node* pre;
    struct Node* next;
}Node;


Node* initList()                            //初始化头结点，创建链表
{
    Node* L = (Node*)malloc(sizeof(Node));  //为头结点分配动态内存空间
    L -> data = 0;                          //初始化头结点的data
    L -> pre = L;                           //初始化头结点的pre，指向自己
    L -> next = L;                          //初始化头结点的next，指向next
    return L;
}


void headInsert(Node* L, int data)              //头结点
{
    Node* node = (Node*)malloc(sizeof(Node));   //为新结点分配动态内存空间
    node -> data = data;                        //为新结点赋值
    node -> next = L -> next;                   //将头结点的next的值 赋值给 新结点的next
    node -> pre = L;                            //将头头结点的地址 赋值给 新结点的pre
    L -> next -> pre = node;                    //将新结点的地址 赋值给 原来头结点的下一个结点的pre
    L -> next = node;                           //将新结点的地址 赋值给 头结点的next 
    L -> data ++;                               //头结点data++
}


void tailInsert(Node* L, int data)              //尾插法
{
    Node* node = L;                             //将头结点的地址 赋值给 node
    while (node->next != L)                     //判断node是否是最后一个结点
    {                                           //如果不是
        node = node -> next;                    //更新node
    }
    Node* n = (Node*)malloc(sizeof(Node));      //为新结点分配动态内存空间
    n -> data = data;                           //为新结点赋值
    n -> pre = node;                            //将原来最后一个结点的地址 赋值给 新结点的pre
    n -> next = L;                              //将头结点的地址 赋值给 新结点的next
    L -> pre = n;                               //将新结点的地址 赋值给 头结点的pre
    node -> next = n;                           //将新结点的地址 赋值给 原来最后一个结点的next
    L -> data ++;                               //头结点data++
}


int delete(Node* L, int data)                       //删除结点
{
    Node* node = L -> next;                         //将头结点的next的值 赋值给 node
    while (node != L)                               //判断node 是否是 头结点
    {
        if (node -> data == data)                   //判断node是否是目标结点
        {
            node -> pre -> next = node -> next;     //将目标结点的next的值 赋值给 目标结点的pre指向的结点的next
            node -> next -> pre = node -> pre;      //将目标结点的pre的值  赋值给 目标结点的next指向的结点的pre
            free(node);                             //释放目标结点的动态内存空间
            L -> data --;                           //头结点的data--
            return 1;                               //返回 1
        }
        node = node -> next;                        //如果不是目标结点，更新node
    }
    return 0;                                       //返回 0
}

void printList(Node* L)                         //打印链表
{
    Node* node = L->next;                       //将头结点的next的值 赋值给 node
    while(node != L)                            //判断node 是否是 目标结点
    {       
        printf("%d -> ", node->data);           //打印node的值
        node = node->next;                      //更新node
    }
    printf("NULL\n");                           ///打印NULL
}


int main()
{
    Node* L = initList();           //初始化链表
    headInsert(L, 1);               //头插 1
    headInsert(L, 2);               //头插 2
    headInsert(L, 4);               //头插 4
    headInsert(L, 5);               //头插 5
    printList(L);                   //打印链表
    tailInsert(L, 6);               //尾插 6
    tailInsert(L, 7);               //尾插 7
    printList(L);                   //打印链表
    delete(L, 7);                   //删除 7
    printList(L);                   //打印链表
    return 0;
}