链表定义：
1、 n个节点离散分配
2、 彼此通过指针相连
3、 每个节点只有一个前驱节点，每个节点只有一个后继节点
4、 首节点没有前驱节点，尾节点没有后续节点
专业术语：
1、 首节点：链表第一个存放有效数值的节点，位于链表的第二位
2、 尾节点：最后一个有效节点
3、 头节点：首节点前面的一个节点，位于链表的起始位置，不存放有效数值，指针指向首节点，存在的意义是使得对链表的操作更为方便
4、 头指针：指向头节点的指针变量
5、 尾指针：指向尾节点的指针变量
确定一个链表需要的最少参数：头指针（通过头指针可以推出链表其余所有的信息）
链表分类：
1、 单链表：每个节点分为一个数据域一个指针域，由上一个节点的指针域指向下一个节点构成链表
2、 双链表：每个节点分为一个数据域和两个指针域，两节点互相指向彼此构成双链表
3、 循环链表：能通过任何一个节点找到其他所有节点
4、 非循环链表
单链表实现及细节
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Node{
int data; //数据域
struct Node * pNext; //指针域
}NODE ,*PNODE;
PNODE InitList(void);
/**操作结果：构造一个线性表*/
bool DestoryList(PNODE pHead);
/**初始条件：线性表已存在
* 操作结果：线性表被销毁
*/
void ClearList(PNODE pHead);
/**初始条件：线性表已存在
* 操作结果：将其重置为空
*/
bool ListEmpty(PNODE pHead);
/**初始条件：线性表已存在
* 操作结果：若表为空，返回TURE，否则返回FALSE
*/
int ListLength(PNODE pHead);
/**初始条件：线性表已存在
* 操作结果：返回表中数据元素个数
*/
int GetElem(PNODE pHead,int i);
/**初始条件：线性表已存在
* 操作结果，返回表中第i个元素
*/
void ListInstert(PNODE pHead,int val,int i);
/**初始条件：线性表已存在
* 操作结果：在表中第i个位置之前插入元素val
*/
int ListDelete(PNODE pHead,int val,int i);
/**初始条件：线性表已存在且非空
* 操作结果：删除表内的第i个数据元素，并用val返回其值
*/
void ListSort(PNODE pHead);
/**初始条件：线性表一存在且非空
* 操作结果：表内数据由小至大排列
*/
void ListPut(PNODE pHead);
/**初始条件：线性表存在且非空
* 操作结果：输出表内数据
*/
int main()
{
PNODE pHead=NULL;
int i,val,t,temp;
pHead=InitList();
ListPut(pHead);
printf("链表长度为：%d\n",ListLength(pHead));
ListSort(pHead);
printf("排序后的链表：");
ListPut(pHead);
printf("在第几个节点前插入元素：");
scanf("%d",&i);
printf("请输入插入元素的数值：");
scanf("%d",&val);
ListInstert(pHead,val,i);
printf("插入后的链表：");
ListPut(pHead);
printf("删除第几个节点：");
scanf("%d",&t);
printf("被删除的元素为：%d\n",ListDelete(pHead,temp,t));
printf("删除后的链表：");
ListPut(pHead);
printf("链表被清空后：");
ClearList(pHead);
ListPut(pHead);
return 0;
}
PNODE InitList(void) //生成链表
{
int i,len,val;
PNODE pHead=(PNODE)malloc(sizeof(NODE)); //此处不能直接用PNODE pHead，因为这样是生成局部变量，离开此函数之后会被系统收回，导致以后的操作没有操作对象
PNODE pTail; //pTail是一个尾指针，用于指示链表尾的位置，这样后面的pNew才知道链表末尾的地址，才能与前面的节点相连（用的尾插法）
pTail=pHead;
if(NULL==pHead){ //若pHead==NULL则说明pHead生成失败，则后面的操作就无从谈起，exit(-1)表示直接结束退出程序
printf("分配空间失败，程序结束\n");
exit(-1);
}
printf("请输入链表长度：");
scanf("%d",&len);
for(i=0;i<len;i++){
printf("请输入第%d个元素的值：",i+1);
scanf("%d",&val);
PNODE pNew=(PNODE)malloc(sizeof(NODE));//此处用malloc的原因与上方相同
if(NULL==pNew){ //此处作用与上方相同
printf("分配空间失败，程序结束\n");
exit(-1);
}
pNew->data=val;
pNew->pNext=NULL;
pTail->pNext=pNew; //pTail指向的是链表的末尾节点，而链表生成使用的是尾插法，所以只需让最后一个节点指向新生成的pNew即可，这样循环就生成了链表
pTail=pNew; //在pNew链接到链表末尾时，原来pTail指向的节点就不再是尾节点，pNew作为新的尾节点，因此pTail要指向新生成的pNew来保持指向尾节点
}
return pHead;
}
bool DestoryList(PNODE pHead)
{
PNODE p=pHead,q=pHead;
while(p->pNext!=NULL){
q=p;
p=p->pNext;
free (q);
}
free (pHead);
}
void ClearList(PNODE pHead)
{
PNODE p=pHead;
while(p!=NULL){
p->data=0;
p=p->pNext;
}
}
bool ListEmpty(PNODE pHead)
{
if(NULL==pHead->pNext){
return true;
}else{
return false;
}
}
int ListLength(PNODE pHead)
{
int i=0;
PNODE p=pHead;
while(p->pNext!=NULL){
i++;
p=p->pNext;
}
return i;
}
int GetElem(PNODE pHead,int i)
{
int j=0,t;
PNODE p=pHead;
while(j!=i){
p=p->pNext;
t=p->data;
j++;
}
return t;
}
void ListInstert(PNODE pHead,int val,int i)//在第i个节点前插入一个节点，其中数据域为val
{
int j=0;
PNODE p=pHead;
while(j<i-1){
p=p->pNext;
j++;
}
PNODE pNew=(PNODE)malloc(sizeof(NODE));
pNew->data=val;
pNew->pNext=p->pNext; //这里要先让pNew链接到后面的链表，才能完成插入的功能。如果先让pNew前面的的部分链接到pNew，那么就找不到后面的链表的地址，当然也可以用一个新的PNODE类型的变量指向pNew的下一个节点，但是这样一来就会变得比较麻烦
p->pNext=pNew;
}
int ListDelete(PNODE pHead,int val,int i) //删除链表内第i个节点，并用val返回这个节点的数据域
{
int j=0;
PNODE p=pHead,q;
while(j<i-1){
p=p->pNext; //p指向要删除的元素的前一个元素
q=p->pNext; //q指向要删除的元素，为后面的返回其数据域做准备
j++;
}
val=q->data; //因为要返回被删除的元素的数据域，而要被删除的元素在删除后便不能得到它的数据域，所以要用一个变量暂存其数据域
p->pNext=p->pNext->pNext; //要删除链表中的一个元素，只需要让这个元素的前一个元素越过这个要删除的元素指向它的后一个元素即可
free(q);
return val;
}
void ListSort(PNODE pHead) //单链表的冒泡排序
{
PNODE tail=pHead; //尾指针
PNODE h=pHead->pNext;
PNODE p=h,q=h,f=h; //p,q,f都指向链表的第一个有效元素即首节点，其中p恒为首指针，用于指示首节点位置，q每个循环像后移动一次，用于交换相邻两个节点的数据域，f指向q的前一个节点，用于尾指针pTail向前移动
int t; //交换两个节点数据域的中间变量
while(tail->pNext!=NULL){ //通过循环使尾指针指向尾节点
tail=tail->pNext;
}
while(p!=tail){ //此处讲解见文末
while(q!=tail){
if(q->data>q->pNext->data){
t=q->data;
q->data=q->pNext->data;
q->pNext->data=t;
}
f=q;
q=q->pNext;
}
q=p;
tail=f;
}
}
void ListPut(PNODE pHead)
{
PNODE p=pHead->pNext;
while(p!=NULL){
printf("%d ",p->data);
p=p->pNext;
}
printf("\n");
}
单链表冒泡排序详解：
void ListSort(PNODE pHead)
{
PNODE tail=pHead;
PNODE h=pHead->pNext;
PNODE p=h,q=h,f=h;
int t;
while(tail->pNext!=NULL){
tail=tail->pNext;
}
while(p!=tail){
while(q!=tail){
if(q->data>q->pNext->data){
t=q->data;
q->data=q->pNext->data;
q->pNext->data=t;
}
f=q;
q=q->pNext;
}
q=p;
tail=f;
}
}
算法大意：pTail指向尾节点，p恒指向首节点，标记首节点位置方便以后操作，q由p向pTail移动，同时交换所指的相邻两节点的数据域，f指向p指向的节点的前一个节点，用于在p到达pTail之后使pTail向前移动一个位置。依次循环最终实现冒泡排序
下举一例：
