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

typedef struct Node
{
    int data;               //数据域
    struct Node * pNEXT;    //指针域

}Node,* pNode;  //别名 Node 等于struct Node, pNode 等于struct * Node;

//创建链表
pNode create_list();
//遍历链表
void traverse_list(pNode pHead);  //确定一个链表参数只要一个 【头节点】
//数组长度
int length_list(pNode pHead);
//判断链表是否为空
bool is_empty(pNode pHead);

//排序
void order_list(pNode pHead);
//插入
bool insert_list(pNode pHead,int pos,int val);
//删除
bool delete_list(pNode pHead,int pos,int * pVal);

int main(void)
{   
    pNode pHead = NULL;     //struct Node * pHead = NULL;  （指针要先定义有指向，后使用）

    pHead = create_list();  //头节点的地址
    traverse_list(pHead);
    
    if(insert_list(pHead,2,33)){
        printf("插入成功 \n");
        traverse_list(pHead);
    }else{
        printf("插入失败，无该指定位置！ \n");
    }

    int val;
    if(delete_list(pHead,2,&val)){
        printf("删除元素成功，删除的元素为：%d \n", val);
        traverse_list(pHead);
    }else{
        printf("删除失败，无该指定位置！\n");
    }

    printf("升序排序");
    order_list(pHead);  //排序
    traverse_list(pHead);

    int i = length_list(pHead);
    printf("链表的元素为lenght = %d \n", i);

    if(is_empty(pHead)){
        printf("链表为空 \n");
    }else{
        printf("链表不为空 \n");
    }


    return 0;
}
//创建链表
pNode create_list()  //返回一个地址 （链表头地址）
{
    int length;
    int i;
    int data;  //存放数据值

    pNode pHead = (Node *)malloc(sizeof(Node));  //创建一个头节点（不存放数据）标识这个链表
    if(pHead == NULL){
        printf("分配内存失败");
        exit(-1);
    }

    Node * pTail = pHead;   //头节点也是尾节点
    pHead->pNEXT = NULL;    //创建一个尾节点（其中指针区为NULL）,初始时，挂在头节点。即 头节点也是尾节点（尾节点的标志就是指针域为空）

    printf("请输入要创建链表的个数");
    scanf("%d", &length);

    for(i=0;i<length;i++)       
    {   
        printf("请输入链表的%d个元素",i+1);
        scanf("%d", &data);

        pNode pNew = (Node *)malloc(sizeof(Node));  //开辟一个node 空间

        if(pNew == NULL){
            printf("分配内存失败");
            exit(-1);
        }

        pNew->data = data;
        pTail->pNEXT = pNew;  //新节点覆盖尾节点
        pNew->pNEXT = NULL;   //新挂到头节点的pNEXT为空代表（尾节点），即尾节点被新加入的链表的节点取代。
        pTail = pNew;         // == 新加入的节点 等于 尾节点
    }
    return pHead;
}
//遍历链表
void traverse_list(pNode pHead)     //一直遍历到最后一个NODE，node->pNext == NULL为空时退出。
{
    pNode p = pHead->pNEXT; //头结点的指向指针

    while( p != NULL){
    
        printf("%d ", p->data);
        p = p->pNEXT;
    }
    printf("\n");
}
//链表长度
int length_list(pNode pHead)
{
    int len = 0;
    pNode p = pHead->pNEXT;

    while(p != NULL){    //循环直到，下一个节点的指针域为空为止
        p = p->pNEXT;    //跳到下个节点
        len++;
    }
    return len;
}
//是否为空
bool is_empty(pNode pHead)
{
    if(pHead->pNEXT = NULL){    //头节点的指针域是否为空
        return true;    
    }else{
        return false;
    }
}
//链表排序
void order_list(pNode pHead)   //冒泡法排序，值改变链表中的值
{
    pNode p,q;
    int temp;
    
    for(p = pHead->pNEXT; p->pNEXT!=NULL; p = p->pNEXT) //从第二个节点开始，判断下一个节点的指针域是否为空
    {
        for(q = p->pNEXT; q!=NULL; q = q->pNEXT)        //从p的下一个指针开始，直到这个节点指针域为空
        {   
            if(p->data > q->data){
                temp = p->data;
                p->data = q->data;
                q->data = temp;
            }
        }
    }
}
//指定位置插入元素
bool insert_list(pNode pHead,int pos,int val)
{
    int i =0; //指向要插入的位置的前一个
    pNode p = pHead;

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

    if(i>pos-1 || p == NULL){
        return false;
    }
    
    //新开辟一个节点空间【储存节点数据域和指针域】
    pNode pNew = (pNode)malloc(sizeof(Node));
    if(pNew == NULL){
        printf("分配内存失败");
        exit(-1);
    }
    pNew->data = val;


    //在要插入的那个位置插入
    pNode q = p->pNEXT;   //原先插入位置后一位
    p->pNEXT = pNew;      //插入位置的后一位变成插入的
    pNew->pNEXT = q;      //原先插入位置的后一位跟在新插入的后面

    return true;
}

//指点位置删除元素
bool delete_list(pNode pHead,int pos,int * pVal)
{
    int i = 0;
    pNode p = pHead;
    while(p->pNEXT != NULL && i<pos-1)  //指向要删除的那个元素位置
    {
        p = p->pNEXT;  
        i++;
    }

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

    //要删除的那个节点
    pNode qDel = p->pNEXT;
    //删除节点的那个节点的数据域(返回给主函数，通过指针的方式)
    *pVal = qDel->data;
    
    p->pNEXT = p->pNEXT->pNEXT; //直接指向该元素的后一个， （跳过要删除的那个）
    free(qDel); //释放空间
    
    return true;
}