数据结构-3-双链表

//双链表

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

#define TRUE 1
#define FALSE 0


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


Node* initList()                            //初始化链表
{
    Node* L = (Node*)malloc(sizeof(Node));  //创建链表头结点，分配动态内存空间
    L -> data = 0;                          //初始化链表结点数
    L -> pre = NULL;                        //初始化pre
    L -> next = NULL;                       //初始化next
    return L;                               //返沪Node类型的指针L
}


void headInsert(Node* L, int data)           //头插法
{
    Node* node = (Node*)malloc(sizeof(Node));//开辟结点动态内存空间
    node -> data = data;                     //结点赋值
    node -> next = L -> next;                //将头结点next指向的结点地址 赋值给 新的结点
    node -> pre = L;                         //新结点的pre指向头结点
    if (L -> next)                           //判断头结点的next是否是NULL
    {                                        //如果不为空
        L -> next -> pre = node;             //将新结点的地址 赋值给 头结点下一个结点的 pre
        L -> next = node;                    //将新结点的地址 赋值给 头结点的next
    }
    else                                     //当链表中只有头结点时
    { 
        L -> next = node;                       //将新结点的地址 赋值给 头结点的next
    }
    L -> data ++;                               //头结点数据++
}

void tailInsert(Node* L, int data)              //尾插法
{
    Node* node = L;                             //将头结点的地址 赋值给 node
    Node* n = (Node*)malloc(sizeof(Node));      //为新结点开辟空间
    n -> data = data;                           //为新结点赋值
    while (node -> next)                        //遍历到链表最后一个结点
    {
        node = node -> next;                    //更新node
    }                                           //node此时为尾结点
    n -> next = node -> next;                   //将尾结点next指向的地址 赋值给 新结点的next     
    node -> next = n;                           //将尾结点的next指向n   
    n -> pre = node;                            //将新结点的pre指向原来的尾结点
    L -> data ++;                               //头结点数据++
}



int delete(Node* L, int data)                   //删除结点
{                                  
    Node* node = L->next;                       //将头结点next指向的地址 赋值给 node
    while (node)                                //如果node不为空结点
    {                             
        if (node -> data == data)               //如果node是目标结点 
        {     
            node -> pre -> next = node -> next; //将node的next 赋值给 node上一个结点的next
            if (node -> next)                   //如果node不是尾结点
            {                                       
                node -> next -> pre = node -> pre;  //将node的pre 赋值给 node下一结点的pre
            }
            L -> data --;                       //头结点数据 --
            free(node);                         //释放node的空间
            return TRUE;                        //找到目标值，删除成功
        }
        node = node -> next;                    //node更新为下一结点
    }
    return FALSE;                               //未找到值，删除失败
}


void printList(Node* L)                         //打印链表
{
    Node* node = L -> next;                     //将头结点指向的结点 赋值给 node
    while (node)                                //当node不为空时， 
    {
        printf("%d -> ", node -> data);         //打印node的值
        node = node -> next;                    //更新node为下一个结点
    }
    printf("NULL\n");                           //当node为空结点时打印NULL
}


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