链表作为C语言中一种基础的数据结构，在平时写程序的时候用的并不多，但在操作系统里面使用的非常多。不管是RTOS还是Linux等使用非常广泛，所以必须要搞懂链表，链表分为单向链表和双向链表，单向链表很少用，使用最多的还是双向链表。单向链表懂了双向链表自然就会了。
定义：
链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。
特点：
链表由一系列节点（链表中每一个元素称为节点）组成，节点在运行时动态生成（malloc），每个节点包括两个部分：
一个是存储数据元素的数据域
图1 单向链表
链表由一个个节点构成，每个节点一般采用结构体的形式组织，例如：
typedef struct student｛
int num；
char name[20]；
struct student* next；
}STU;
链表节点分为两个域
数据域：存放各种实际的数据，如：num、score等
图2 节点内嵌在一个数据结构中
链表最大的作用是通过节点把离散的数据链接在一起，组成一个表，这大概就是链表的字面解释了吧。链表常规的操作就是节点的插入和删除，为了顺利的插入，通常一条链表我们会人为地规定一个根节点，这个根节点称为生产者。通常根节点还会有一个节点计数器，用于统计整条链表的节点个数，具体见图3中的root_node。
图3 带根节点的链表
双向链表与单向链表的区别就是节点中有两个节点指针，分别指向前后两个节点，其它完全一样。有关双向链表的文字描述参考单向链表小节即可，有关双向链表的示意图具体见图4
图4 双向链表
在很多公司的嵌入式面试中，通常会问到链表和数组的区别。在C语言中，链表与数组确实很像，两者的示意图具体见图5，这里以双向链表为例。
第一步：创建一个节点
#include<stdio.h>
#include<stdlib.h>//定义结点结构体
//定义链表结点的结构体
typedef struct student{
int num;//学号
int score;//分数
char name[20];//姓名
struct student* next;//指向下一个结点的指针
}STU;
//创建链表头部的函数
void link_creat_head(STU **p_head,STU *p_new){
STU *p_mov = *p_head;
if(*p_head == NULL){//当第一次加入链表为空时，head指向p_new
*p_head = p_new;
p_new->next = NULL;
}else{//第二次及以后加入链表
while(p_mov->next != NULL){
p_mov = p_mov->next;//找到原有链表的最后一个节点
}
p_mov->next = p_new;//将新申请的节点加入链表
p_new->next = NULL;
}
}
//主函数
int main(){
STU *head = NULL,*p_new = NULL;
int num,i;
printf("请输入链表初始个数:\n");
scanf("%d",&num);
for(i=0;i<num;i++){
p_new = (STU*)malloc(sizeof(STU));//申请一个新节点
printf("请输入学号、分数、名字:\n");//给新节点赋值
scanf("%d%d%s",&p_new->num,&p_new->score,p_new->name);
link_creat_head(&head,p_new);//将新节点加入链表
}
return 0;
}
第三步：以此类推，直到节点的指针域为NULL
//链表的遍历
void link_print(STU *head){
STU *p_mov;//定义新的指针保存链表的首地址，防止使用head改变原本链表
p_mov=head;//当指针保存最后一个结点的指针域为NULL时，循环结束
while(p_mov != NULL){
//先打印当前指针保存结点的指针域
printf("num=%d score=%d name:%s\n",p_mov->num,p_mov->score,p_mov->name);
//指针后移，保存下一个结点的地址
p_mov=p_mov->next;
}
}
//链表的释放
void link_free(STU **p_head){
//定义一个指针变量保存头结点的地址
STU *pb = *p_head;
while(*p_head != NULL){
//先保存p_head指向的结点的地址
pb=*p_head;//p_head保存下一个结点地址
*p_head=(*p_head)‐>next;//释放结点并防止野指针
free(pb);
pb=NULL;
}
}
先对比第一个结点的数据域是否是想要的数据，如果是就直接返回，如果不是则继续查找下一个结点，如果到达最后一个结点的时候都没有匹配的数据，说明要查找数据不存在
//链表的查找
//按照学号查找
STU* link_search_num(STU *head,int num){
STU *p_mov;//定义的指针变量保存第一个结点的地址
p_mov=head;//从头节点开始遍历链表
while(p_mov != NULL){//当没有到达最后一个结点的指针域时循环继续
//如果找到是当前结点的数据，则返回当前结点的地址
if(p_mov->num == num){//找到了
returnp_mov;
}
//如果没有找到，则继续对比下一个结点的指针域
p_mov=p_mov->next;
}
//当循环结束的时候还没有找到，说明要查找的数据不存在，返回NULL进行标识
return NULL;//没有找到
}
//按照姓名查找
STU* link_search_name(STU*head,char*name){
STU* p_mov;//定义的指针变量保存第一个结点的地址
p_mov=head;//从头节点开始遍历链表
while(p_mov != NULL){
//如果找到是当前结点的数据，则返回当前结点的地址
if(strcmp(p_mov->name,name)==0){//找到了
return p_mov;
}
//如果没有找到，则继续对比下一个结点的指针域
p_mov=p_mov->next;
}
//如果循环结束时还没有找到，说明要查找的数据不存在，返回NULL进行标识
return NULL;//没有找到
}
//链表结点的删除
void link_delete_num(STU **p_head,int num){
STU *pb,*pf;
pb=pf=*p_head;
if(*p_head == NULL){//链表为空，不用删
printf("链表为空，没有您要删的节点");
return;
}
while(pb->num!=num && pb->next!=NULL){//循环找，要删除的节点
pf=pb;
pb=pb->next;
}
if(pb->num == num){//找到了一个节点的num和num相同
if(pb == *p_head){//要删除的节点是头节点
//让保存头结点的指针保存后一个结点的地址
*p_head=pb->next;
}else{
//前一个结点的指针域保存要删除的后一个结点的地址
pf->next=pb->next;
}
//释放空间
free(pb);
pb=NULL;
}else{//没有找到
printf("没有您要删除的节点\n");
}
}
链表中插入一个结点，按照原本链表的顺序插入，找到合适的位置
情况（按照从小到大）：
如果链表没有结点，则新插入的就是第一个结点。
如果新插入的结点的数值最小，则作为头结点。
如果新插入的结点的数值在中间位置，则找到前一个，然后插入到他们中间。
如果新插入的结点的数值最大，则插入到最后。
//链表的插入：按照学号的顺序插入
void link_insert_num(STU **p_head,STU *p_new){
STU *pb,*pf;
pb=pf=*p_head;
if(*p_head == NULL){//链表为空链表
*p_head=p_new;
p_new->next=NULL;
return;
}
while((p_new->num >= pb->num)&&(pb->next != NULL)){
pf=pb;
pb=pb->next;
}
if(p_new->num < pb->num){//找到一个节点的num比新来的节点num大，插在pb的前面
if(pb == *p_head){//找到的节点是头节点，插在最前面
p_new->next=*p_head;
*p_head=p_new;
}else{
pf->next=p_new;
p_new->next=pb;
}
}else{//没有找到pb的num比p_new->num大的节点，插在最后
pb->next=p_new;
p_new->next=NULL;
}
}
如果链表为空，不需要排序。
如果链表只有一个结点，不需要排序。
先将第一个结点与后面所有的结点依次对比数据域，只要有比第一个结点数据域小的，则交换位置。
交换之后，拿新的第一个结点的数据域与下一个结点再次对比，如果比他小，再次交换，依次类推。
第一个结点确定完毕之后，接下来再将第二个结点与后面所有的结点对比，直到最后一个结点也对比完毕为止。
//链表的排序
void link_order(STU *head){
STU *pb,*pf,temp;
pf=head;
if(head == NULL){
printf("链表为空,不用排序\n");
return;
}
if(head->next== NULL){
printf("只有一个节点，不用排序\n");
return;
}
while(pf->next != NULL)//以pf指向的节点为基准节点，
{
pb=pf->next;//pb从基准元素的下个元素开始
while(pb != NULL)
{
if(pf->num > pb->num)
{
temp=*pb;
*pb=*pf;
*pf=temp;
temp.next=pb->next;
pb->next=pf->next;
pf->next=temp.next;
}
pb=pb->next;
}
pf=pf->next;
}
}
第一步：创建一个节点作为头节点，将两个指针域都保存NULL
#include<stdio.h>
#include<stdlib.h>//定义结点结构体
//定义双向链表的结点结构体
typedef struct student{
int num;//学号
int score;//分数
char name[20];//姓名
struct student* front;//保存上一个结点的地址
struct student* next;//保存下一个结点的地址
}STU;
//创建双向链表头部的函数
void double_link_creat_head(STU **p_head,STU *p_new){
STU *p_mov =* p_head;
if(*p_head == NULL){//当第一次加入链表为空时，head指向p_new
*p_head=p_new;
p_new->front=NULL;
p_new->next=NULL;
}else{//第二次及以后加入链表
while(p_mov->next!=NULL){
p_mov=p_mov->next;//找到原有链表的最后一个节点
}
p_mov->next=p_new;//将新申请的节点加入链表
p_new->front=p_mov;
p_new->next=NULL;
}
}
//双向链表的打印函数
void double_link_print(STU *head){
STU *pb=head;
while(pb->next != NULL){
printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);
pb=pb->next;
}
printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);
printf("***********************\n");
//反向打印链表
while(pb != NULL){
printf("num=%dscore=%dname:%s\n",pb->num,pb->score,pb->name);
pb=pb->front;
}
}
//主函数
int main(){
STU *head=NULL,*p_new=NULL;
intnum,i;
printf("请输入链表初始个数:\n");
scanf("%d",&num);
for(i=0;i<num;i++){
p_new=(STU*)malloc(sizeof(STU));//申请一个新节点
printf("请输入学号、分数、名字:\n");//给新节点赋值
scanf("%d%d%s",&p_new->num,&p_new->score,p_new->name);
double_link_creat_head(&head,p_new);//将新节点加入链表
}
double_link_print(head);
return0;
}
按照顺序插入结点
#include<stdio.h>
#include<stdlib.h>//定义结点结构体
typedef struct student{
//数据域
int num;//学号
int score;//分数
char name[20];//姓名
//指针域
struct student* front;//保存上一个结点的地址
struct student* next;//保存下一个结点的地址
}STU;
void double_link_creat_head(STU **p_head,STU *p_new){
STU *p_mov=*p_head;
if(*p_head == NULL){//当第一次加入链表为空时，head指向p_new
*p_head=p_new;
p_new->front=NULL;
p_new->next=NULL;
}else{//第二次及以后加入链表
while(p_mov->next != NULL){
p_mov=p_mov->next;//找到原有链表的最后一个节点
}
p_mov->next=p_new;//将新申请的节点加入链表
p_new->front=p_mov;
p_new->next=NULL;
}
}
void double_link_print(STU *head){
STU *pb=head;
while(pb->next != NULL){
printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);
pb=pb->next;
}
printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);
printf("***********************\n");
//反向打印链表
while(pb != NULL){
printf("num=%dscore=%dname:%s\n",pb->num,pb->score,pb->name);
pb=pb->front;
}
}
//双向链表的删除
void double_link_delete_num(STU **p_head,int num){
STU *pb,*pf;
pb=*p_head;
if(*p_head == NULL){//链表为空，不需要删除
printf("链表为空，没有您要删除的节点\n");
return;
}
while((pb->num != num) && (pb->next != NULL)){
pb=pb->next;
}
if(pb->num == num){//找到了一个节点的num和num相同，删除pb指向的节点
if(pb == *p_head){//找到的节点是头节点
if((*p_head)->next == NULL){//只有一个节点的情况
*p_head=pb->next;
}else{//有多个节点的情况
*p_head=pb->next;
(*p_head)->front=NULL;
}
}else{//要删的节点是其他节点
if(pb->next != NULL){//删除中间节点
pf=pb->front;
pf->next=pb->next;
(pb->next)->front=pf;
}else{//删除尾节点
pf=pb->front;
pf->next=NULL;
}
}
free(pb);//释放找到的节点
}else{//没找到
printf("没有您要删除的节点\n");
}
}
int main(){
STU *head=NULL,*p_new=NULL;
intnum,i;
printf("请输入链表初始个数:\n");
scanf("%d",&num);
for(i=0;i<num;i++){
p_new=(STU*)malloc(sizeof(STU));//申请一个新节点
printf("请输入学号、分数、名字:\n");//给新节点赋值
scanf("%d%d%s",&p_new->num,&p_new->score,p_new->name);
double_link_creat_head(&head,p_new);//将新节点加入链表
}
double_link_print(head);
printf("请输入您要删除的节点的num:\n");
scanf("%d",&num);
double_link_delete_num(&head,num);
double_link_print(head);
return0;
}
本文转自，如有侵权，请联系删除。