数据结构算法之《双向链表的ADMFS)全部操作

一、【头文件】：

#pragma once
#ifdef __cplusplus
extern "C"
{
#endif

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

    typedef struct Node
    {
        int Data;
        struct Node* P_Pre;
        struct Node* P_Next;
    }Node;

    typedef struct DoubleList
    {
        Node* P_Head;
        Node* P_Tail;
    }DoubleList;

    //初始化节点
    void InitNode(Node* P_Node, int Data);
    //正向显示链表
    void Show(DoubleList List);
    //反向显示链表
    void ShowRev(DoubleList List);
    //头部插入
    void PushHead(DoubleList* P_List, int Data);
    //尾部插入
    void PushBack(DoubleList* P_List, int Data);
    //查找节点（从头到尾）
    Node* FindNode(DoubleList List, int Obj);
    //查找节点（从尾到头）
    Node* FindNodeRev(DoubleList List, int Obj);
    //指定位置插入节点
    void InsertNode(DoubleList* List, int Rear, int InsData);
    //指定位置插入节点
    void InsertNode(DoubleList* P_List, int Rear, int InsData);
    //删除指定节点
    void DeleteNode(DoubleList* P_List, int DelData);
    //修改指定节点
    void Modification(DoubleList List, int OldData, int NewData);
    //销毁链表
    void Destroy(DoubleList* P_List);
    //快速排序
    void QuickSort(Node* P_Begin, Node* P_End);
    //分段（辅助快速排序）
    Node*  Segmentation(Node* P_Begin, Node* P_End);
    //数据交换（辅助排序）
    void Swap(Node* Pa, Node* Pb);
#ifdef __cplusplus
}
#endif
 

二、【源文件】：

#include "stdafx.h"
#include "dulheader.h"

//初始化节点
void InitNode(Node* P_Node, int Data)
{
    P_Node->P_Next = P_Node->P_Pre = NULL;
    P_Node->Data = Data;
}

//正向显示链表
void Show(DoubleList List)
{
    printf("%8s%10s%15s\n", "前驱", "后继", "值");
    while (NULL != List.P_Head)
    {
        printf("%p\t%p\t%d\n", List.P_Head->P_Pre, List.P_Head->P_Next, List.P_Head->Data);
        List.P_Head = List.P_Head->P_Next;
    }
    //换行
    puts("");
}

//反向显示链表
void ShowRev(DoubleList List)
{
    printf("%8s%10s%15s\n", "前驱", "后继", "值");
    while (NULL != List.P_Tail)
    {
        printf("%p\t%p\t%d\n", List.P_Tail->P_Pre, List.P_Tail->P_Next, List.P_Tail->Data);
        List.P_Tail = List.P_Tail->P_Pre;
    }
    //换行
    puts("");
}

//头部插入
void PushHead(DoubleList* P_List, int Data)
{
    //创建一个新节点
    Node* P_New = (Node*)malloc(sizeof(Node));
    //初始化新节点
    InitNode(P_New, Data);

    if (P_List->P_Head == NULL&&P_List->P_Tail == NULL)
    {
        //没有节点的情况

        //头指针和尾指针一样
        P_List->P_Head = P_List->P_Tail = P_New;
    }
    else
    {
        //有节点的情况

        //只针对头指针

        //改变头节点的前驱
        P_List->P_Head->P_Pre = P_New;
        //改变新节点的后继
        P_New->P_Next = P_List->P_Head;
        //重新定义头指针
        P_List->P_Head = P_New;
    }

}

//尾部插入
void PushBack(DoubleList* P_List, int Data)
{
    //创建一个新节点
    Node* P_New = (Node*)malloc(sizeof(Node));
    //初始化新节点
    InitNode(P_New, Data);

    if (P_List->P_Head == NULL && P_List->P_Tail == NULL)
    {
        //没有节点的情况

        //头指针和尾指针一样
        P_List->P_Head = P_List->P_Tail = P_New;
    }
    else
    {
        //有节点的情况

        //只针对尾指针

        //改变尾节点后继
        P_List->P_Tail->P_Next = P_New;
        //改变新节点的前驱
        P_New->P_Pre = P_List->P_Tail;
        //重新的定义尾指针
        P_List->P_Tail = P_New;
    }
}

//查找节点（从头到尾）
Node* FindNode(DoubleList List, int Obj)
{
    //穷举
    while (NULL != List.P_Head)
    {
        if (List.P_Head->Data == Obj)
        {
            return List.P_Head;
        }
        List.P_Head = List.P_Head->P_Next;
    }
    return NULL;
}

//查找节点（从尾到头）
Node* FindNodeRev(DoubleList List, int Obj)
{
    //穷举
    while (NULL != List.P_Tail)
    {
        if (List.P_Tail->Data == Obj)
        {
            return List.P_Tail;
        }
        List.P_Tail = List.P_Tail->P_Pre;
    }
    return NULL;
}

//指定位置插入节点
void InsertNode(DoubleList* P_List, int Rear, int InsData)
{
    if (NULL == P_List->P_Head&&NULL == P_List->P_Tail)
    {
        //如果没有节点，那还插个毛啊。
        return;
    }
    else
    {
        Node* P_Res = FindNode(*P_List, Rear);
        if (NULL != P_Res)
        {
            //如果找到了就创建一个节点
            Node* P_New = (Node*)malloc(sizeof(Node));
            InitNode(P_New, InsData);

            if (P_Res == P_List->P_Tail)
            {
                //如果“P_Res”等于尾指针
                P_New->P_Pre = P_List->P_Tail;
                P_List->P_Tail->P_Next = P_New;
            }
            else
            {
                P_New->P_Pre = P_Res;
                P_New->P_Next = P_Res->P_Next;
                P_Res->P_Next = P_New;
            }
        }

    }
}

//删除指定节点
void DeleteNode(DoubleList* P_List, int DelData)
{
    if (NULL == P_List->P_Head&&NULL == P_List->P_Tail)
    {
        //没有节点的情况
        return;
    }
    else
    {
        Node* P_Res = FindNode(*P_List, DelData);
        if (NULL != P_Res)
        {
            if (P_Res == P_List->P_Head)
            {
                //若“P_Res”等于头结点
                P_List->P_Head = P_List->P_Head->P_Next;
                free(P_Res);
                P_Res = NULL;
            }
            else if (P_Res != P_List->P_Head&&P_Res != P_List->P_Tail)
            {
                //若“P_Res”等于头尾区间内的节点
                P_Res->P_Pre->P_Next = P_Res->P_Next;
                P_Res->P_Next->P_Pre = P_Res->P_Pre;
                free(P_Res);
                P_Res = NULL;
            }
            else
            {
                //若“P_Res”等于尾结点
                P_List->P_Tail = P_List->P_Tail->P_Pre;
                P_List->P_Tail->P_Next = NULL;
                free(P_Res);
                P_Res = NULL;
            }
        }
    }
}

//修改指定节点
void Modification(DoubleList List, int OldData, int NewData)
{
    if (NULL == (List.P_Head) && NULL == (List.P_Tail))
    {
        return;
    }
    else
    {
        Node* P_Res = FindNode(List, OldData);
        if (NULL != P_Res)
        {
            P_Res->Data = NewData;
        }
    }
}

//销毁链表
void Destroy(DoubleList* P_List)
{
    while (NULL != P_List->P_Head)
    {
        DeleteNode(P_List, P_List->P_Head->Data);
        P_List->P_Head = P_List->P_Head->P_Next;
    }
}

//快速排序
void QuickSort(Node* P_Begin, Node* P_End)
{
    if (P_Begin != P_End)
    {
        Node* Pi = Segmentation(P_Begin, P_End);
        QuickSort(P_Begin, Pi);
        QuickSort(Pi->P_Next, P_End);
    }
}
//分段（辅助快速排序）
Node*  Segmentation(Node* P_Begin, Node* P_End)
{
    int Key = P_Begin->Data;
    Node* Pi = P_Begin;
    for (Node* Pj = Pi->P_Next; Pj!= NULL; Pj = Pj->P_Next)
    {
        if (Key < Pj->Data)
        {
            Pi = Pi->P_Next;
            Swap(Pi, Pj);
        }
    }

    Swap(P_Begin, Pi);
    return Pi;
}

//数据交换（辅助排序）
void Swap(Node* Pa, Node* Pb)
{
    int Temp = Pa->Data;
    Pa->Data = Pb->Data;
    Pb->Data = Temp;
}
 

三、【主函数】

// demos.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#include "dulheader.h"
#include <time.h>

int _tmain(int argc, _TCHAR* argv[])
{
    printf("\n程序选择效果如下：\n");
    /*******************头部插入*******************/
#if 0
    DoubleList List = { 0 };

    for (int i = 0; i < 10; i++)
    {
        PushHead(&List, i);
    }

    Show(List);
    ShowRev(List);
#endif 

    /*******************尾部插入*******************/
#if 0
    DoubleList List = { 0 };

    for (int i = 0; i < 10; i++)
    {
        PushBack(&List, i);
    }

    Show(List);
    ShowRev(List);
#endif 

    /*******************正向查找节点*******************/
#if 0
    DoubleList List = { 0 };

    for (int i = 0; i < 10; i++)
    {
        PushBack(&List, i);
    }

    Show(List);
    ShowRev(List);

    Node* P_Res[10] = { 0 };

    for (int i = 0; i < 10; i++)
    {
        if (NULL != FindNode(List, i))
        {
            P_Res[i] = FindNode(List, i);
        }
    }
    for (int i = 0; i < 10; i++)
    {
        NULL != P_Res[i] ? printf("%d\n", P_Res[i]->Data) : 0;
    }

#endif 

    /*******************反向查找节点*******************/
#if 0
    DoubleList List = { 0 };

    for (int i = 0; i < 10; i++)
    {
        PushBack(&List, i);
    }

    Show(List);
    ShowRev(List);

    Node* P_Res[10] = { 0 };

    for (int i = 0; i < 10; i++)
    {
        if (NULL != FindNode(List, i))
        {
            P_Res[i] = FindNodeRev(List, i);
        }
    }
    for (int i = 0; i < 10; i++)
    {
        NULL != P_Res[i] ? printf("%d\n", P_Res[i]->Data) : 0;
    }

#endif 

    /*******************指定位置插入节点*******************/
#if 0
    DoubleList List = { 0 };

    for (int i = 0; i < 10; i++)
    {
        PushBack(&List, i);
    }

    Show(List);
    InsertNode(&List, 0, 100);
    InsertNode(&List, 5, 100);
    InsertNode(&List, 9, 100);
    InsertNode(&List, 179, 100);
    Show(List);

#endif 

    /*******************删除指定节点*******************/
#if 0
    DoubleList List = { 0 };

    for (int i = 0; i < 10; i++)
    {
        PushBack(&List, i);
    }

    Show(List);
    DeleteNode(&List, 0);
    DeleteNode(&List, 5);
    DeleteNode(&List, 9);
    DeleteNode(List, 199, 2018);
    Show(List);

#endif 

    /*******************修改指定节点*******************/
#if 0
    DoubleList List = { 0 };

    for (int i = 0; i < 10; i++)
    {
        PushBack(&List, i);
    }

    Show(List);
    Modification(List, 0, 2018);
    Modification(List, 5, 2018);
    Modification(List, 9, 2018);
    Modification(List, 199, 2018);
    Show(List);

#endif 

    /*******************销毁链表*******************/
#if 0
    DoubleList List = { 0 };

    for (int i = 0; i < 10; i++)
    {
        PushBack(&List, i);
    }

    Show(List);
    Destroy(&List);
    Show(List);

#endif 

    /*******************快速排序*******************/
#if 1
    DoubleList List = { 0 };
    srand((unsigned int)time(NULL));
    for (int i = 0; i < 10; i++)
    {
        PushBack(&List, rand() % 100);
    }

    Show(List);
    QuickSort(List.P_Head, NULL);

    Show(List);

#endif 
    system("pause");

    return 0;
}

四、【程序运行效果】