C语言实现单链表，并完成链表常用API函数：
1.链表增、删、改、查。
2.打印链表、反转打印、打印环形链表。
3.链表排序、链表冒泡排序、链表快速排序。
4.求链表节点个数（普通方法、递归方法）。
5.链表反转（普通方法、递归方法）。
6.链表合并。
7.获取链表中间节点。
8.判断链表是否有环。
LinkList.h :
#include <stdio.h>
#include <stdlib.h> struct LinkNode
{
int data;
struct LinkNode *pNext;
}; typedef struct LinkNode Node; //简化类型 void init(Node *phead); //初始化
Node *addBack(Node *phead, int data); //尾插法：尾部添加节点
void addHead(Node *phead, int data); //头插法：头部添加节点 void ShowAll(Node *phead); //显示链表
void revShowAll(Node *phead); //反转显示链表
void ShowCircleLink(Node *phead); //显示环形链表 Node *searchFirst(Node *phead, int findData); //查找 Node *changeFirst(Node *phead, int findData, int newData); //修改 Node *delFirst(Node *phead, int delData); //删除 Node *insertFirst(Node *phead, int insertData,int newData); //插入 void bubbleSort(Node *phead); //冒泡排序 void quickSort(Node *pbegin, Node *pback); //快速排序法：（双冒泡）
Node *fen(Node *pbegin, Node *pback); //分段 int getNum1(Node *phead); //求链表节点个数
int getNum2(Node *phead); //求链表节点个数(递归) Node *revList1(Node *phead); //链表反转(普通方法)
Node *revList2(Node *phead); //链表反转(递归方法) //将链表phead1和phead2合并到phead3，并返回链表phead3
Node *mergeList(Node *phead3, Node *phead1, Node *phead2); //链表合并 Node *getMid(Node *phead); //获取链表的中间节点 int judgeCircle(Node *phead); //判断链表是否有环
LinkList.c :
#include "LinkList.h" //初始化
void init(Node *phead)
{
phead->pNext = NULL;
phead->data = ;
} //显示链表
void ShowAll(Node *phead)
{
if (phead == NULL)
return;
else
{
printf("%4d", phead->data);
//printf("%d,%p,%p\n", phead->data, phead, phead->pNext);
ShowAll(phead->pNext); //跳到下一个节点 }
} //反转显示链表
void revShowAll(Node *phead)
{
if (phead == NULL)
return;
else
{
printf("%d,%p,%p\n", phead->data, phead, phead->pNext);
ShowAll(phead->pNext); //跳到下一个节点 }
} //显示环形链表
void ShowCircleLink(Node *phead)
{
if (phead == NULL)
return;
else
{
Node *p = phead;
for (; p->pNext != phead; p = p->pNext)
printf("%4d", p->data); printf("%4d", p->data); //还需要再打印最后一个元素 }
} //尾插法：尾部添加节点 (改变了头指针，改变一个指针，要么二级指针，要么用返回值给指针赋值，这里采用返回值)
Node *addBack(Node *phead, int data)
{
Node *pnew = malloc(sizeof(Node)); //构建新的节点
pnew->data = data; //新节点赋值
pnew->pNext = NULL; if (phead == NULL) //phead为空，直接连接
phead = pnew;
else
{
Node *ptemp = phead; //备份一下头指针
while (ptemp->pNext != NULL)
{
ptemp = ptemp -> pNext; //循环前进
}
ptemp->pNext = pnew; //链接
} return phead;
} //头插法：头部添加节点 (采用二级指针的方法)
void addHead(Node **pphead, int data)
{
Node *pnew = malloc(sizeof(Node)); //构建新的节点
pnew->data = data; //新节点赋值
pnew->pNext = NULL; if(*pphead==NULL)
pphead = pnew;
else
{
pnew->pNext = *pphead;
*pphead = pnew;
}
} //查找
Node *searchFirst(Node *phead, int findData)
{
for (Node *p = phead; p != NULL; p = p->pNext)
{
if (p->data == findData)
{
return p; //返回找到的指针位置
}
} return NULL;
} //修改
Node *changeFirst(Node *phead, int findData, int newData)
{
for (Node *p = phead; p != NULL; p = p->pNext)
{
if (p->data == findData)
{
p->data = newData;
return p; //返回找到的指针位置
}
} return NULL;
} //删除
Node *delFirst(Node *phead, int delData)
{
Node *p1=NULL, *p2=NULL; //此时需要双指针
p1 = phead; //保存头结点 while (p1 != NULL)
{
if (p1->data != delData)
{
p2 = p1; //p2保存的是p1的上一个位置
p1 = p1->pNext;
}
else
break;
} if (p1 != phead)
{
p2->pNext = p1->pNext; //跳过p1
free(p1); //删除p1
}
else
{
phead = phead->pNext;
free(p1); //头部删除
} return phead;
} //插入
Node *insertFirst(Node *phead, int insertData, int newData)
{
Node *p1 = NULL, *p2 = NULL; //此时需要双指针
p1 = phead; //保存头结点 while (p1 != NULL)
{
if (p1->data != insertData)
{
p2 = p1; //p2保存的是p1的上一个位置
p1 = p1->pNext; //向前移动
}
else
break;
} Node *pnew = malloc(sizeof(Node)); //构建新的节点
pnew->data = newData; //新节点赋值
pnew->pNext = NULL; if (phead == p1)
{
pnew->pNext = phead; //保存头结点
phead = pnew; //头部插入
}
else
{
pnew->pNext = p1;
p2->pNext = pnew; //插入
} return phead;
} //冒泡排序
void bubbleSort(Node *phead)
{
//数组可以随机访问任何一个元素，可以规避一些比较
//链表找到N个元素，必须先遍历N-1个元素
for (Node *p1 = phead; p1 != NULL; p1 = p1->pNext)
{
for (Node *p2 = phead; p2 != NULL; p2 = p2->pNext)
{
if (p1->data < p2->data)
{
int temp;
temp = p1->data;
p1->data = p2->data;
p2->data = temp;
}
}
}
} Node *fen(Node *pbegin, Node *pback)
{
int key = pbegin->data; //以第一个数据为分段 Node *p = pbegin; //第一个节点
Node *q = pbegin->pNext; //第二个节点 while (q != pback)
{
if (q->data < key)
{
p = p->pNext; //循环下一个节点 int temp = p->data; //交换
p->data = q->data;
q->data = temp;
}
q = q->pNext; //循环第二个指针 printf("\n枢轴为：(%d)", key);
printf("\n此时数：");
ShowAll(pbegin); } int temp = p->data; //交换
p->data = pbegin->data;
pbegin->data = temp; printf("\n\n交换值：");
ShowAll(pbegin);
printf("\n-----------------------------------------------"); return p;
} //快速排序法：（双冒泡）
void quickSort(Node *pbegin,Node *pback)
{
if (pbegin != pback)
{
Node *pfen = fen(pbegin, pback); //取中间点，分成两段分别再进行快排 quickSort(pbegin, pfen); //前半段快排
quickSort(pfen->pNext, pback); //后半段快排
}
} //求链表节点个数(普通方法)
int getNum1(Node *phead)
{
int i = ;
for (; phead != NULL; phead = phead->pNext)
{
i++;
}
return i;
} //求链表节点个数(递归)
int getNum2(Node *phead)
{
if (phead == NULL)
return ;
else
return + getNum2(phead->pNext);
} //链表反转(普通方法)
Node *revList1(Node *phead)
{
if (phead == NULL || phead->pNext == NULL)
return phead;
else
{
Node *pre = NULL;
Node *pcur = NULL;
Node *pnext = NULL; pre = phead;
pcur = phead->pNext;
while (pcur != NULL)
{
pnext = pcur->pNext; //备份下一个节点
pcur->pNext = pre; //第一个节点指向NULL,此时pre指向NULL(指针反转) pre = pcur; //前进
pcur = pnext; //轮替前进
} phead->pNext = NULL; //注意尾节点置空
phead = pre;
} return phead;
} //链表反转(递归方法)
Node *revList2(Node *phead)
{
if (phead == NULL || phead->pNext == NULL)
return phead;
else
{
Node *pnext = phead->pNext; //顺序 Node *Head = revList2(pnext); //轮询所有的节点，递归调用 pnext->pNext = phead; phead->pNext = NULL; //逆序 return Head;
}
} //链表合并
Node *mergeList(Node *phead3, Node *phead1, Node *phead2)
{
Node *pcur1 = phead1;
Node *pcur2 = phead2; while (pcur1 != NULL || pcur2 != NULL)
{
if (pcur1 != NULL && pcur2 != NULL)
{
if (pcur1->data < pcur2->data)
{
phead3 = addBack(phead3, pcur1->data);
pcur1 = pcur1->pNext;
}
else
{
phead3 = addBack(phead3, pcur2->data);
pcur2 = pcur2->pNext;
}
}
else
{
while (pcur1 != NULL)
{
phead3 = addBack(phead3, pcur1->data);
pcur1 = pcur1->pNext;
}
while (pcur2 != NULL)
{
phead3 = addBack(phead3, pcur2->data);
pcur2 = pcur2->pNext;
} break;
}
} return phead3;
} //获取链表的中间节点
Node *getMid(Node *phead)
{
if (phead == NULL || phead->pNext == NULL)
return phead;
else
{
Node *p1 = phead; //一次前进一步
Node *p2 = phead; //一次前进两步 while (p2->pNext != NULL) //注意循环条件,而不是p2 != NULL
{
p1 = p1->pNext;
p2 = p2->pNext;
if (p2->pNext != NULL)
p2 = p2->pNext;
} return p1;
}
} //判断链表是否有环
int judgeCircle(Node *phead)
{
int flag = ;
for (Node *p1 = phead, *p2 = phead; p1 != NULL && p2 != NULL; p1 = p1->pNext, p2 = p2->pNext) //死循环
{
if(p2->pNext!=NULL) //p2一次前进两步，而p1一次前进一步
p2 = p2->pNext; if (p1 == p2)
{
flag == ; //p1追上了p2，有环
break;
} } return flag;
}
main.c :
#include "LinkList.h" void main()
{
Node *phead = NULL;
//init(phead); //初始化，头结点不分配内存，这里不能初始化头结点 phead = addBack(phead, ); //尾插
phead = addBack(phead, );
phead = addBack(phead, );
phead = addBack(phead, );
phead = addBack(phead, );
phead = addBack(phead, ); //addHead(&phead, 9); //头插
//addHead(&phead, 22);
//addHead(&phead, 41);
//addHead(&phead, 18);
//ShowAll(phead); //Node *pfind = searchFirst(phead, 13);
//pfind->data = 33;
//ShowAll(phead); //Node *pchange = changeFirst(phead, 14,93);
//ShowAll(phead); //ShowAll(phead);
//printf("\n\n");
//phead = delFirst(phead, 24);
//ShowAll(phead); //printf("\n\n");
//insertFirst(phead, 11, 100);
//ShowAll(phead); printf("排序前：");
ShowAll(phead);
printf("\n\n"); //bubbleSort(phead);
quickSort(phead, NULL); printf("\n\n");
printf("排序后：");
ShowAll(phead);
printf("\n"); printf("%d\n", getNum2(phead)); phead = revList1(phead);
ShowAll(phead);
printf("\n");
phead = revList2(phead);
ShowAll(phead);
printf("\n"); Node *phead1 = NULL;
phead1 = addBack(phead1, );
phead1 = addBack(phead1, );
phead1 = addBack(phead1, );
phead1 = addBack(phead1, );
phead1 = addBack(phead1, ); Node *phead2 = NULL;
phead2 = addBack(phead2, );
phead2 = addBack(phead2, );
phead2 = addBack(phead2, );
phead2 = addBack(phead2, ); printf("\n\n\n");
ShowAll(phead1);
printf("\n");
ShowAll(phead2);
printf("\n"); Node *phead3 = NULL;
phead3 = mergeList(phead3, phead1, phead2);
ShowAll(phead3);
printf("\n"); Node *pmid = getMid(phead3);
printf("%d\n", pmid->data); Node *phead4 = NULL;
phead4 = addBack(phead4, );
phead4 = addBack(phead4, );
phead4 = addBack(phead4, );
phead4 = addBack(phead4, );
phead4 = addBack(phead4, );
phead4 = addBack(phead4, );
phead4 = addBack(phead4, ); Node *p = phead4;
for (; p->pNext != NULL; p = p->pNext)
{
}
p->pNext = phead4; ShowCircleLink(phead4); //打印环形链表
printf("\n");
printf("%d\n", judgeCircle(phead4)); system("pause");
}