# include<stdio.h>
# include<malloc.h>
# include<stdlib.h>
typedef struct Node
{
int data;//数据域
struct Node * pNext; //指针域
}NODE, *PNODE;                                              //BODE等价于struct Node    PNODE等价于strucr Node *
PNODE create_list(void);                                   //函数声明
void traverse_list(PNODE pHead);                                 //对链表输出
bool is_empty(PNODE pHead);                                   //判断链表能否为空
int length_list(PNODE );                                     //返回值为链表的长度
bool insert_list(PNODE, int, int);                           //在第几个节点前插入一个节点，第一个int表示节点得位置第二个int表示数值
bool delete_list(PNODE, int, int);                             //删除第几个节点，第一个int是节点的位置，第二个int表示节点的值
void sort_list(PNODE);                                          //对链表排序
int main(void)
{
PNODE pHead = NULL;                                     //等价于strucr Node *pHead = NULL,这里的pHead是头结点的地址
pHead = create_list();                                  // create_list()功能：创建一个非循环单链表，并将该链表的头结点的地址返回
//traverse_list(pHead);                                   // traverse_list功能：输出链表中的每一个元素
//sort_list(pHead); //小到大排序
//insert_list(pHead, 3, 222); //在第三个节点前插入222
//traverse_list(pHead);                                   // traverse_list功能：输出链表中的每一个元素
//int len = length_list(pHead);
delete_list(pHead, 3, 0);
traverse_list(pHead);
return 0;
}
PNODE create_list(void)                                   //创建一个非循环单链表， 不需要参数，返回PNODE类型
{
int len;                                             //用来存放有效节点的个数
int i;
int val;                                             //用来临时存放用户输入的结点的值
PNODE pHead = (PNODE)malloc(sizeof(NODE));                   //  PNODE等价于strucr Node *   分配一个不存放有效数据的节点，既  头结点
if (NULL == pHead)
{
printf(“分配失败,程序终止”);
exit(-1);                                            //终止所在函数的程序，并返回-1，与return不同的是return只会终止同一级的程序
}
//分配动态内存后，要养成检测能否分配成功的习惯
PNODE pTail = pHead;                                    //把头结点的地址赋给pTail
pTail->pNext = NULL;                                    //将pTail的指针域定义为空，此时这个链表只要头结点，即这是一个空链表
printf(“请您输入生成的链表的节点个数： len = “);
scanf(“%d”, &len);
for (i=0; i < len; i++)
{
printf(“请输入第%d个节点的值:” , i+1);
scanf(” %d”,&val);
PNODE pNew = (PNODE)malloc(sizeof(NODE));            //定义一个NODE型数据变量，并分配动态内存
if (NULL == pNew)
{
printf(“分配失败,程序终止\n”);
exit(-1);                                           //终止所在函数的程序，并返回-1
}
//分配动态内存后，要养成检测能否分配成功的习惯
pNew->data = val;                                   //pNew为一个有效节点，此处为这个节点的数据域赋值
pTail->pNext = pNew;                                //执行此处后pTail指向pNew这个节点
pNew->pNext = NULL;                                 //将NULL赋给pNew这个节点的指针域
pTail = pNew;                                       //此时pTail这个节点等价于 pNew这个节点
//通过这四步的循环，每循环一次增加一个节点，并且将尾节点的指针域赋为空值
}
return pHead;                                           //原因是通过链表的头结点能确定整个链表故返回链表的头节点地址
}
void traverse_list(PNODE pHead)
{
PNODE p = pHead->pNext ;                                //定义PNODE型变量p，将pHead->pNext 赋给p
while (NULL != p)                                       //若p不为空，则输出它的数据域
{
printf(“%d “,p->data );
p = p->pNext ;                                      //将P向后移一个节点
}
printf(“\n”);
return;
}
int length_list(PNODE pHead)                               //接收头结点地址pHead
{
int len = 0;
PNODE p = pHead->pNext  ;
while ( p != NULL)                                     //判断节点指针域部位空
{
++len;                                             //若不为空，长度加一
p = p->pNext ;                                     //指针往后移一个节点
}
printf(“链表的长度为%d\n”,len);
return len;
}
void sort_list(PNODE pHead)                                  //表示接受PNODE类型变量的同时定义PNODE性变量pHead
{
int i, j, t;
PNODE p, q;                                              //定义定义变量
int len = length_list(pHead);                              //普通函数之间可以相互调用，这里定义了int型变量
for (i=0,p=pHead->pNext; i<len-1; ++i,p=p->pNext )
{
for (j =i+1,q=p->pNext;    j<len;    ++j,q=q->pNext )
{
if (p->data > q->data )                           //相似于数组(a[i] > a[j])
{
t= p->data;                                  //相似于数组t = a[i];
p->data = q->data;                           //相似于数组a[i] = a[j];
q->data = t;                                 //相似于数组a[j] = t;
}
}
/*根据冒泡排序改编，若把链表排序写得和数组排序非常相似，我们可以理解为泛型*/
}
return;
}
bool insert_list(PNODE pHead, int pos, int val)
{
int i =0;
PNODE p = pHead;
while (p != NULL && i < pos-1)//次循环功能为将p指向pos-1个节点，若不能则结束程序
{
p = p->pNext ;
++i; //p没向后一一个节点i就加一
}                             //到此处p指向pos-1个节点或p-Next为空
if (i>pos-1 || p==NULL) //若P为空或i>pos-1则结束程序
return false;
PNODE pNew = (PNODE)malloc(sizeof(NODE));//为变量pNew分配动态内存
if (NULL == pNew)
{
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 val)
{
int i =0;
PNODE p = pHead;
while (p != NULL && i < pos-1)//次循环功能为将p指向pos-1个节点，若不能则结束程序
{
p = p->pNext ;
++i; //p每后向后移一次个节点i就加一
}                             //到此处p指向pos-1个节点或p-Next为空
if (i>pos-1 || p==NULL) //若P为空或i>pos-1则结束程序
return false;
PNODE q = p->pNext; //q指向第pos个节点
/* val = q->data; //将要删除的值写入val
q = q->pNext; //此时q指向pos+1个元素，p指向pos-1个元素
p->pNext = q;*/ //运行后p指向Q
/*注释掉的方法没有释放删除节点的内存会造成内存泄漏*/
val = q->data;
p->pNext = p->pNext->pNext;//pos-1个节点 == pos+1个节点，所以此时pos个节点过后是pos+1个节点
free(q);//释放删除节点的内存
q = NULL;
printf(“你删除的元素是 %d\n”, val);
return true;
}