#include <stdlib.h>

 #include <malloc.h>

 #include <stdio.h>

 typedef struct Node

 {

     int data;

     struct Node *pNext;

 }NODE,*PNODE;

 PNODE create_list(void);

 void traverse_list(PNODE);

 bool is_empty(PNODE pHead);

 int length_list(PNODE);

 bool insert_list(PNODE, int, int);

 bool delete_list(PNODE,int,int*);

 void sort_list(PNODE);

 int main(void)

 {

     PNODE pHead = NULL;

     int val;

     pHead = create_list();

     sort_list(pHead);

     if (delete_list(pHead, , &val))

     {

         printf("delete %d ok!\n",val);

     }

     else

     {

         printf("delete wrong");

     }

     traverse_list(pHead);

     int len = length_list(pHead);

     if (is_empty(pHead))

     {

         printf("list is empty!");

     }

     else

     {

         printf("list isn't empty！");

     }

     return ;

 }

 PNODE create_list(void)

 {

     int len;

     int val;//用于存放用户输入的结点的值

     printf("请输入链表的长度：len=");

     scanf("%d", &len);

     PNODE pHead = (PNODE)malloc(sizeof(Node));

     if (NULL == pHead)

     {

         printf("分配失败，程序终止!");

         exit(-);

     }

     PNODE pTail = pHead;

     pTail->pNext = NULL;

     for (int i = ; i < len; ++i)

     {

         printf("请输入第%d个节点的值", i + );

         scanf("%d", &val);

         PNODE pNew = (PNODE)malloc(sizeof(Node));

         if (NULL == pNew)

         {

             printf("分配失败，程序终止!");

             exit(-);

         }

         pNew->data = val;

         pTail->pNext = pNew;

         pNew->pNext = NULL;

         pTail = pNew;

     }

     return pHead;

 }

 void traverse_list(PNODE pHead)

 {

     PNODE p = pHead->pNext;

     while (NULL != p)

     {

         printf("%d", p->data);

         p = p->pNext;

     }

     printf("\n");

 }

 bool is_empty(PNODE pHead)

 {

     if (NULL == pHead->pNext)

     {

         return true;

     }

     return false;

 }

 int length_list(PNODE pHead)

 {

     int length = ;

     PNODE p = pHead->pNext;

     while (NULL != p)

     {

         length++;

         p = p->pNext;

     }

     return length;

 }

 void sort_list(PNODE pHead)

 {

     int i, j, t;

     int len = length_list(pHead);

     PNODE p, q;

     for (i = , p = pHead->pNext; i < len - ; ++i, p=p->pNext)

     {

         for (j = i + , q = p->pNext; j < len; ++j, q = q->pNext)

         {

             if (p->data > q->data)

             {

                 t = p->data;

                 p->data = q->data;

                 q->data = t;

             }

         }

     }

     return;

 }

 //在pHead指向链表的第pos个节点的前面插入一个新的节点，该节点的值为value,pos从1开始

 bool insert_list(PNODE pHead, int pos, int value)

 {

     int i = ;

     PNODE p = pHead;

     while (NULL != p && i < pos - )

     {

         p = p->pNext;

         ++i;

     }

     if (i > pos -  || NULL == p)

         return false;

     PNODE pNew = (PNODE)malloc(sizeof(NODE));

     if (NULL == pNew)

     {

         printf("动态分配内存失败！\n");

         exit(-);

     }

     pNew->data = value;

     PNODE q = p->pNext;

     p->pNext = pNew;

     pNew->pNext = q;

     return true;

 }

 bool delete_list(PNODE pHead, int pos, int *pVal)

 {

     int i = ;

     PNODE p = pHead;

     while (NULL != p->pNext && i < pos - )

     {

         p = p->pNext;

         ++i;

     }

     if (i > pos -  || NULL == p->pNext)

     {

         return false;

     }

     PNODE q = p->pNext;

     *pVal = q->data;

     //删除p节点后面的节点

     p->pNext = p->pNext->pNext;

     free(q);

     q = NULL;

     return true;

 }

 /*

 1.链表的删除，比如删除p后的节点，如何操作？有时很容易遗漏free(r)的操作，导致内存泄漏。

 可以如下操作：

 r = p->next;

 p->next = r->next;

 free(r);

 */