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

typedef struct Data
{
    int x;
}    *data;

typedef struct Node
{
    struct Data data; //数据域
    struct Node* pNext; //指针域
}NODE, * PNODE; //NODE等价于struct Node    PNODE等价于struct Node *
int length=0;//链表长度

//函数声明
PNODE create_list(void);  //创建链表
void traverse_list(PNODE pHead);  //遍历链表
bool is_empty(PNODE pHead);  //判断链表是否为空
int length_list(PNODE);  //求链表长度
bool insert_list(PNODE pHead, int pos, int val);    //任意插入 在pHead所指向链表的第pos个节点的前面插入一个新的结点，该节点的值是val， 并且pos的值是从1开始
bool Rinsert_list(PNODE pHead, int count);            //尾插法
bool Linsert_list(PNODE pHead, int count);            //头插法
bool delete_list(PNODE pHead, int pos, int* pVal);  //删除链表第pos个节点，并将删除的结点的值存入pVal所指向的变量中,  并且pos的值是从1开始
void sort_list(PNODE pHead);  //对链表进行排序

//创建一个链表
PNODE create_list(void)
{
    int len;  //用来存放有效节点的个数
    int i;
    int val; //用来临时存放用户输入的结点的值

    //分配了一个不存放有效数据的头结点
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (NULL == pHead)
    {
        printf("分配失败, 程序终止!\n");
        exit(-1);
    }
    PNODE pTail = pHead;
    pTail->pNext = NULL;

    printf("请输入您需要生成的链表节点的个数: len = ");
    scanf_s("%d", &len);

    for (i = 0; i < len; ++i)
    {
        printf("请输入第%d个节点的值: ", i + 1);
        scanf_s("%d", &val);

        PNODE pNew = (PNODE)malloc(sizeof(NODE));//申请内存大小为node 类型为pnode
        if (NULL == pNew)
        {
            printf("分配失败, 程序终止!\n");
            exit(-1);                            //退出
        }
        pNew->data.x = val;        
        pTail->pNext = pNew;
        pNew->pNext = NULL;
        pTail = pNew;
        length++;
    }

    return pHead;
}

//遍历链表
void traverse_list(PNODE pHead)
{
    PNODE p = pHead->pNext;

    while (NULL != p)
    {
        printf("%d  ", p->data.x);
        p = p->pNext;//一个一个递推直到最后一个到指向为空
    }
    printf("\n");

    return;
}

//求长度
int length_list(PNODE pHead)
{
    PNODE p = pHead->pNext;
    int len = 0;

    while (NULL != p)
    {
        ++len;
        p = p->pNext;
    }

    return len;
}

//判断是否为空
bool is_empty(PNODE pHead)
{
    if (NULL == pHead->pNext)
        return true;
    else
        return false;
}

//在pHead所指向链表的第pos个节点的前面插入一个新的结点，该节点的值是val， 并且pos的值是从1开始
bool insert_list(PNODE pHead, int pos, int val)
{
    int i = 0;
    PNODE p = pHead;

    while (NULL != p && i < pos - 1)
    {
        p = p->pNext;
        ++i;
    }

    if (i > pos - 1 || NULL == p)
        return false;

    //如果程序能执行到这一行说明p已经指向了第pos-1个结点,但第pos-1个节点是否存在无所谓
    //分配新的结点
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if (NULL == pNew)
    {
        printf("动态分配内存失败!\n");
        exit(-1);
    }
    pNew->data.x = val;
    length++;

    //将新的结点存入p节点的后面
    PNODE q = p->pNext;
    p->pNext = pNew;
    pNew->pNext = q;

    return true;
}

//尾插法
bool Rinsert_list(PNODE pHead ,int count)
{
    int val;
    int t = length+1;
    for (int i = t; i < (t +count); i++)
    {
        printf_s("尾插请输入\n");
        scanf_s("%d", &val);
        insert_list(pHead, i, val);
    }
    return 1;
}

//头插法
bool Linsert_list(PNODE pHead, int count)
{    
    int val;
    PNODE p = pHead;
    for (int i = 0; i < count; i++)
    {
        printf_s("头插法插入\n");
        scanf_s("%d", &val);
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if (NULL == pNew)
        {
            printf("动态分配内存失败!\n");
            exit(-1);
        }
        pNew->data.x = val;
        length++;
        pNew->data.x = val;
        pNew->pNext = p->pNext;
        p->pNext = pNew;
    }    

//删除链表
bool delete_list(PNODE pHead, int pos, int* pVal)
{
    int i = 0;
    PNODE p = pHead;

    while (NULL != p->pNext && i < pos - 1)
    {
        p = p->pNext;
        ++i;
    }

    if (i > pos - 1 || NULL == p->pNext)
        return false;

    //如果程序能执行到这一行说明p已经指向了第pos-1个结点，并且第pos个节点是存在的
    PNODE q = p->pNext;  //q指向待删除的结点
    *pVal = q->data.x;

    //删除p节点后面的结点
    p->pNext = p->pNext->pNext;
    length--;
    //释放q所指向的节点所占的内存
    free(q);
    q = NULL;

    return true;

}

#pragma once
#include"stdio.h"
#include"stdlib.h"
struct Data
{
    int x;
    int y;
};
//节点
struct Node
{
    Data data;//数据
    struct Node* pnext;
};
//链表
struct List
{
    Node* pfront;//第一个节点的指针
    Node* prear;//最后一个节点的指针
    int count;  //有多少节点
};

int    ListInit(List** pplist);//初始化节点
int    IsEmpty(List* plist);//判断节点
void InserList(List* plist, Node* pnode);//添加节点
void TraverList(List* plist, void(*Traver)(Node* pnode));

#include"stdio.h"
#include"stdlib.h"
#include"list.h"


//数据


//初始化链表
/*
   功能 ：初始化链表 成功返回0 ，否则为1
*/
int ListInit(List** pplist)
{
    *(pplist) = (List*)malloc(sizeof(pplist));
    if (NULL==*pplist)
    {
        return 0;
    }
    else
    {
        (*pplist)->pfront = NULL;
        (*pplist)->prear = NULL;
        (*pplist)->count = 0;
    }
    return 1;
}
//判断链表是否为空
int IsEmpty(List* plist)
{
    if (plist->count == 0)
        return 1;
    else
        return 0;

 }
//插入节点
void InserList(List* plist, Node* pnode)
{
    if (IsEmpty(plist))
    {
        plist->pfront = pnode;//令第一个节点
    }
    else
    {
        plist->prear->pnext = pnode;
    }
    plist->prear = pnode;
    plist->count++;
}
/*回调函数
函数
指针Traver
指向 返回值类型为 void 参数为node*
 */
void TraverList(List* plist, void(*Traver)(Node* pnode))
{
    Node* ptemp = plist->pfront;//ptemp指向第一个节点
    int listsize = plist->count;//有几个节点

        while (listsize)
        {
            Traver(ptemp);
            ptemp = ptemp->pnext;
            listsize--;
        }
}


int main()
{
    List* plist;//定义一个指针
    ListInit(&plist);//创建链表
    Node* pnode;//定义一个节点
     pnode = (Node*)malloc(sizeof(Node));
        pnode->data.x = 5;
        pnode->data.y = 5;
        pnode->pnext = NULL;

        InserList(plist,pnode);
        printf("%d",pnode->data.x);
        free(pnode);
        printf("%d", pnode->data.x);
    return 0;
}