做汽车配件的都在那个网站做呀,手机网站功能,vps如何做网站步骤,建立了网站后如何发贴概述#xff1a; 链表作为 C 语言中一种基础的数据结构#xff0c;在平时写程序的时候用的并不多#xff0c;但在操作系统里面使用的非常多。不管是RTOS还是Linux等使用非常广泛#xff0c;所以必须要搞懂链表#xff0c;链表分为单向链表和双向链表#xff0c;单向链表很…概述 链表作为 C 语言中一种基础的数据结构在平时写程序的时候用的并不多但在操作系统里面使用的非常多。不管是RTOS还是Linux等使用非常广泛所以必须要搞懂链表链表分为单向链表和双向链表单向链表很少用使用最多的还是双向链表。单向链表懂了双向链表自然就会了。
文章目录
一、链表的概念 链表的构成
链表的操作: 双向链表
链表与数组的对比
二、链表的创建 三、链表的遍历
四、链表的释放 五、链表节点的查找
六、链表节点的删除
七、链表中插入一个节点
八、链表排序
九、双向链表的创建和遍历 十、双向链表插入节点 一、链表的概念
定义 链表是一种物理存储上非连续数据元素的逻辑顺序通过链表中的指针链接次序实现的一种线性存储结构。
特点 链表由一系列节点链表中每一个元素称为节点组成节点在运行时动态生成 malloc每个节点包括两个部分 一个是存储数据元素的数据域 另一个是存储下一个节点地址的指针域 图1 单向链表 链表的构成 链表由一个个节点构成每个节点一般采用结构体的形式组织例如
typedef struct studentint numchar name[20]struct student *next}STU; 链表节点分为两个域 数据域存放各种实际的数据如num、score等 指针域存放下一节点的首地址如next等. 图2 节点内嵌在一个数据结构中
链表的操作: 链表最大的作用是通过节点把离散的数据链接在一起组成一个表这大概就是链表 的字面解释了吧。 链表常规的操作就是节点的插入和删除为了顺利的插入通常一条链 表我们会人为地规定一个根节点这个根节点称为生产者。通常根节点还会有一个节点计 数器用于统计整条链表的节点个数具体见图3中的 root_node。 图3带根节点的链表 双向链表 双向链表与单向链表的区别就是节点中有两个节点指针分别指向前后两个节点其 它完全一样。有关双向链表的文字描述参考单向链表小节即可有关双向链表的示意图具体见图4 图4双向链表
链表与数组的对比 在很多公司的嵌入式面试中通常会问到链表和数组的区别。在 C 语言中链表与数 组确实很像两者的示意图具体见图5这里以双向链表为例。
图5 链表与数组的对比 链表是通过节点把离散的数据链接成一个表通过对节点的插入和删除操作从而实现 对数据的存取。而数组是通过开辟一段连续的内存来存储数据这是数组和链表最大的区 别。数组的每个成员对应链表的节点成员和节点的数据类型可以是标准的 C 类型或者是 用户自定义的结构体。数组有起始地址和结束地址而链表是一个圈没有头和尾之分 但是为了方便节点的插入和删除操作会人为的规定一个根节点。
二、链表的创建
第一步创建一个节点 第二步创建第二个节点将其放在第一个节点的后面第一的节点的指针域保存第二个节点的地址 第三步再次创建节点找到原本链表中的最后一个节点接着讲最后一个节点的指针域保存新节点的地址以此内推。 #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-nextNULL;}else //第二次及以后加入链表{while(p_mov-next!NULL){p_movp_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); //将新节点加入链表}
}三、链表的遍历
第一步输出第一个节点的数据域输出完毕后让指针保存后一个节点的地址 第二步输出移动地址对应的节点的数据域输出完毕后指针继续后移 第三步以此类推直到节点的指针域为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;}
}
四、链表的释放
重新定义一个指针q保存p指向节点的地址然后p后移保存下一个节点的地址然后释放q对应的节点以此类推直到p为NULL为止 //链表的释放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_movhead;//当没有到达最后一个结点的指针域时循环继续while(p_mov!NULL){//如果找到是当前结点的数据则返回当前结点的地址if(p_mov-num num)//找到了{return p_mov;}//如果没有找到则继续对比下一个结点的指针域p_movp_mov-next;}//当循环结束的时候还没有找到说明要查找的数据不存在返回NULL进行标识return NULL;//没有找到
}//按照姓名查找
STU * link_search_name(STU *head,char *name)
{STU *p_mov;p_movhead;while(p_mov!NULL){if(strcmp(p_mov-name,name)0)//找到了{return p_mov;}p_movp_mov-next;}return NULL;//没有找到
}
六、链表节点的删除 如果链表为空不需要删除 如果删除的是第一个结点则需要将保存链表首地址的指针保存第一个结点的下一个结点的 地址 如果删除的是中间结点则找到中间结点的前一个结点让前一个结点的指针域保存这个结 点的后一个结点的地址即可
//链表结点的删除
void link_delete_num(STU **p_head,int num)
{STU *pb,*pf;pbpf*p_head;if(*p_head NULL)//链表为空不用删{printf(链表为空没有您要删的节点);\return ;}while(pb-num ! num pb-next !NULL)//循环找要删除的节点{pfpb;pbpb-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;pbpf*p_head;if(*p_head NULL)// 链表为空链表{*p_head p_new;p_new-nextNULL;return ;}while((p_new-num pb-num) (pb-next !NULL) ){pfpb;pbpb-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-nextp_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;pfhead;if(headNULL){printf(链表为空,不用排序\n);return ;}if(head-next NULL){printf(只有一个节点不用排序\n);return ;}while(pf-next !NULL)//以pf指向的节点为基准节点{pbpf-next;//pb从基准元素的下个元素开始while(pb!NULL){if(pf-num pb-num){temp*pb;*pb*pf;*pftemp;temp.nextpb-next;pb-nextpf-next;pf-nexttemp.next;}pbpb-next;}pfpf-next;}
}
九、双向链表的创建和遍历
第一步创建一个节点作为头节点将两个指针域都保存NULL 第二步先找到链表中的最后一个节点然后让最后一个节点的指针域保存新插入节点的地址新插入节点的两个指针域一个保存上一个节点的地址一个保存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_headNULL) //当第一次加入链表为空时head执行p_new{*p_head p_new;p_new-front NULL;p_new-next NULL;}else //第二次及以后加入链表{while(p_mov-next!NULL){p_movp_mov-next; //找到原有链表的最后一个节点}p_mov-next p_new; //将新申请的节点加入链表p_new-front p_mov;p_new-next NULL;}
}void double_link_print(STU *head)
{STU *pb;pbhead;while(pb-next!NULL){printf(num%d score%d name:%s\n,pb-num,pb-score,pb-name);pbpb-next;}printf(num%d score%d name:%s\n,pb-num,pb-score,pb-name);printf(***********************\n);while(pb!NULL){printf(num%d score%d name:%s\n,pb-num,pb-score,pb-name);pbpb-front;}
}int main()
{STU *headNULL,*p_newNULL;int num,i;printf(请输入链表初始个数:\n);scanf(%d,num);for(i0;inum;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);
}十、双向链表插入节点
按照顺序插入结点 #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_headNULL) //当第一次加入链表为空时head执行p_new{*p_head p_new;p_new-front NULL;p_new-next NULL;}else //第二次及以后加入链表{while(p_mov-next!NULL){p_movp_mov-next; //找到原有链表的最后一个节点}p_mov-next p_new; //将新申请的节点加入链表p_new-front p_mov;p_new-next NULL;}
}void double_link_print(STU *head)
{STU *pb;pbhead;while(pb-next!NULL){printf(num%d score%d name:%s\n,pb-num,pb-score,pb-name);pbpb-next;}printf(num%d score%d name:%s\n,pb-num,pb-score,pb-name);printf(***********************\n);while(pb!NULL){printf(num%d score%d name:%s\n,pb-num,pb-score,pb-name);pbpb-front;}
}//双向链表的删除
void double_link_delete_num(STU **p_head,int num)
{STU *pb,*pf;pb*p_head;if(*p_headNULL)//链表为空不需要删除{printf(链表为空没有您要删除的节点\n);return ;}while((pb-num ! num) (pb-next ! NULL) ){pbpb-next;}if(pb-num num)//找到了一个节点的num和num相同删除pb指向的节点{if(pb *p_head)//找到的节点是头节点{if((*p_head)-nextNULL)//只有一个节点的情况{*p_headpb-next;}else//有多个节点的情况{*p_head pb-next;//main函数中的head指向下个节点(*p_head)-frontNULL;}}else//要删的节点是其他节点{if(pb-next!NULL)//删除中间节点{pfpb-front;//让pf指向找到的节点的前一个节点pf-nextpb-next; //前一个结点的next保存后一个结点的地址(pb-next)-frontpf; //后一个结点的front保存前一个结点的地址}else//删除尾节点{pfpb-front;pf-nextNULL;}}free(pb);//释放找到的节点}else//没找到{printf(没有您要删除的节点\n);}
}int main()
{STU *headNULL,*p_newNULL;int num,i;printf(请输入链表初始个数:\n);scanf(%d,num);for(i0;inum;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);}
