数据结构算法之《双向链表的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 };