//自定义链表练习
#include <stdio.h>
#include <stdlib.h>
#include<iostream>
#include <string>

struct Node
{
    int data;
    struct Node *P_next;
};
struct Node *P_head = NULL;
struct Node *P_end = NULL;


//函数声明
//空头链表初始化
void InitListHead();
//创建节点
struct Node* CreateNode(int a);

//尾添加
void AddListTail(int a);
//头添加
void AddListHead(int a);
//任意位置添加
void AddListRand(int Index, int a);

//遍历链表
void ScanList();
//查找指定节点，并返回节点地址
struct Node* SelectNode(int a);

//删头
void DeleteHead();
//删除尾巴
void DeleteTail();
//删除指定节点
void DeleteNodeRand(int a);
//释放链表
void FreeList();



int main()
{
    printf("HEllo word\n");
    int data[]={1,2,3,4,5,6,7,8};
    struct Node *pt;
    
    InitListHead();
    for(int i =0 ;i< sizeof(data)/sizeof(int);i++)
    {
        pt = CreateNode(data[i]);
    /*    AddListHead(data[i]);*/
        AddListTail(data[i]);

    }
    //遍历链表
    printf("*******************当前链表为*******************************\n");
    ScanList();

    //查找某一个数值
    
/*
    struct Node *Find = SelectNode(3);
    if (Find == NULL)//返回为空，则未找到
    {
        printf("查无此数据");
    } 
    else
    {
        printf("查到此数据为 %d,地址为 %d\n",Find->data,Find);
    }*/

//  指定节点插入
/*
    AddListRand(3, 15);
    AddListRand(4, 15);
    printf("*********************分割符*******************************\n");
    //遍历链表
    ScanList();*/

//删除头
/*
    DeleteHead();
    printf("**********************分隔符，删除头后链表*****************\n");
    ScanList();*/


    //
    //删除尾
/*
    DeleteTail();
    printf("**************删除尾 之后**************\n");
    ScanList();*/
    

    //删除指定节点
/*
    DeleteNodeRand(2);
    printf("**************删除后*******************\n");
    ScanList();*/

    FreeList();
    system("pause");
    return 0;
}


//空头链表初始化
void InitListHead()
{
    //链表空头
    //P_head = (struct Node *)malloc(sizeof(struct Node));
    //P_head ->P_next = NULL;
    //P_end = P_head;

    struct Node *pt = (struct Node *)malloc(sizeof(struct Node));
    if (pt == NULL)
    {
        printf("节点创建失败");
    } 
    else
    {
        P_head = pt;
        P_head->P_next = NULL;
        P_end = P_head;
    }
    

}
//创建节点
struct Node* CreateNode(int a)
{
    struct Node *pt = (struct Node *)malloc(sizeof(struct Node));
    if (pt == NULL)
    {
        printf("节点创建失败");
        return NULL ;
    } 
    else
    {
        pt->data =a;
        pt->P_next = NULL;
    }
    

    return pt;
}

//尾添加
void AddListTail(int a)
{
    struct Node *pt = CreateNode( a );
    if (P_end == NULL )//链表仅有一个空头
    {
        P_head ->P_next = pt;
        P_end = pt;
    } 
    else //链表还有多个节点 .先链接，后移动尾指针
    {
        P_end ->P_next = pt;
        P_end = pt;
    }

}
//头添加
void AddListHead(int a)
{
    struct Node *pt = CreateNode( a );
    if (pt==NULL)
    {
        printf("内存不足");
        return ; 
    } 
    else //插入时候先连后断
    {
        pt->P_next =  P_head ->P_next;
        P_head ->P_next = pt;

    }




}
//任意位置添加
void AddListRand(int Index, int a)
{
    //struct Node *pt =SelectNode(Index);
    //if (P_head ->P_next == NULL) //空链表
    //{
    //    printf("在链表中为空");
    //        return;
    //}
    //// 找此节点
    //    
    //    if (pt == NULL)
    //    {
    //        printf("未找到此节点");
        //    return ; 
        //} 
        //else //找到此节点
        //{
        //  struct Node *Ptemp = CreateNode( a );
        //  if (pt == P_end)//找到的节点为尾巴，直接连接到尾巴
        //  {
        //      AddListTail(a);
        //  } 
        //  else
        //  {
        //      Ptemp->P_next = pt->P_next;
        //      pt->P_next = Ptemp;
        //  }


        //}
    //判断链表有没有东西
    if (NULL == P_head->P_next)
    {
        printf("链表无节点\n");
        return;
    }
    //找 index节点
    struct Node *pTemp = SelectNode(Index);
    if (NULL == pTemp)
    {
        printf("查无此节点\n");
        return;
    }

    //找到了，连接到指定位置
    //创建节点
    struct Node* pNode = CreateNode(a);
    //链接 //尾巴节点
    if (pTemp == P_end) 
    {
        AddListTail(a);
        printf("插入成功\n");
    }
    else
    {
        pNode->P_next = pTemp->P_next;
        pTemp->P_next = pNode;
        printf("插入成功\n");
    }
    
    
}

//遍历链表
void ScanList()
{
    struct Node *pt;
    pt = P_head->P_next;
    while(pt != NULL)
    {
        printf("节点数据为 %d\n",pt->data);
        pt = pt->P_next;
    }

}
//查找制定节点，并返回节点地址
struct Node* SelectNode(int a)
{
    struct Node *pt = P_head->P_next;
    while(pt != NULL)
    {
        if ( pt->data == a )
        {
            return pt;
        }
        pt = pt->P_next;
  
    }
    return NULL;
    
}

//删头
void DeleteHead()
{
    //判断空头后面是否还有节点
    if ( P_head ->P_next == NULL)
    {
        printf("链表无头\n");
        return;
    } 
    else
    {//先把节点保存，后链接，最后释放
        struct Node *PT = P_head ->P_next;
        P_head ->P_next = PT ->P_next;
        free(PT);
    }
}
//删除尾巴
void DeleteTail()
{
    
    //判断链表有没有东西
    if (NULL == P_head->P_next)
    {
        printf("链表无尾\n");
        return;
    }
    //有一个节点
    if (P_head->P_next == P_end)
    {
        free(P_end);
        P_head->P_next = NULL;
        P_end = P_head;
    }
    else
    {
        //找到尾节点的上一个
        struct Node* pTemp = P_head->P_next;

        while (pTemp != NULL)
        {
            if (P_end == pTemp->P_next)
            {
                break;
            }
            pTemp = pTemp->P_next;
        }
        //pTemp就是尾巴的前一个了
        //释放尾巴
        free(P_end);
        //变新尾巴
        P_end = pTemp;
        //尾巴的下一个赋值nULL
        P_end->P_next = NULL;
    }



}
//删除指定节点 删除中间节点，程序崩溃
void DeleteNodeRand(int a)
{
    struct Node* pT;
    
    //判断链表有没有东西
    if (NULL == P_head->P_next)
    {
        printf("链表无节点\n");
        return;
    }
    //找 index节点
    struct Node *pTemp  = SelectNode(a);
    if (NULL == pTemp)
    {
        printf("查无此数据的节点\n");
        return;
    }
    else //查到此节点
    {  
        if ( pTemp == P_end )
        {
            DeleteTail();
        }
        else if ( pTemp == P_head)
        {
            DeleteHead();
        }
        else
        {
            pT = P_head;
            while(pT->P_next != pTemp)
            {
                pT = pT ->P_next;
            }
            pT ->P_next  =  pTemp ->P_next;
            free(pTemp);

        }




    }





}
    

//释放链表
void FreeList()
{

    struct Node* pTemp = P_head;

    while (pTemp != NULL)
    {
        struct Node* pT = pTemp;
        pTemp = pTemp->P_next;
        free(pT);
    }
    P_head = NULL;
    P_end = NULL;
}