二次元同好交流新大陆
扫码下载App
汇聚2000万达人的兴趣社区下载即送20张免费照片冲印
扫码下载App
温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
阅读(64263)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
在LOFTER的更多文章
loftPermalink:'',
id:'fks_',
blogTitle:'c语言_链表实例讲解(两个经典例子)',
blogAbstract:'
更多详情，请查看我的新主页：
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}7340人阅读
& & & & & 链表概述
　　 链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量，以head表示，它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。因此，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。
&&&&&&& 链表的各类操作包括：学习单向链表的创建、删除、& 插入（无序、有序）、输出、& 排序（选择、插入、冒泡）、反序等等。
&&&&&& 单向链表的图示：
&&&&&& ----&[NULL]
&&&&& head
&&&&& 图1：空链表
&&&&&& ----&[p1]----&[p2]...----&[pn]----&[NULL]
&&&&& head&& p1-&next& p2-&next&& pn-&next
&&&&& 图2：有N个节点的链表
&&&&& 创建n个节点的链表的函数为：
&&&&& 输出链表中节点的函数为：
&&&&&& 单向链表的删除图示：
&&&&&& ----&[NULL]
&&&&&& head
&&&&&& 图3：空链表
&&&&& 从图3可知，空链表显然不能删除
&&&&& ----&[1]----&[2]...----&[n]----&[NULL]（原链表）
&&&&& head&& 1-&next& 2-&next&& n-&next
&&&&& ----&[2]...----&[n]----&[NULL]（删除后链表）
&&&&& head&& 2-&next&& n-&next
&&&&& 图4：有N个节点的链表，删除第一个节点
&&&&& 结合原链表和删除后的链表，就很容易写出相应的代码。操作方法如下：
&&&&& 1、你要明白head就是第1个节点，head-&next就是第2个节点；
&&&&&& 2、删除后head指向第2个节点，就是让head=head-&next,OK这样就行了。
&&&&&& ----&[1]----&[2]----&[3]...----&[n]----&[NULL]（原链表）
&&&&&& head&& 1-&next& 2-&next& 3-&next&& n-&next
&&&&&& ----&[1]----&[3]...----&[n]----&[NULL]（删除后链表）
&&&&& head&& 1-&next& 3-&next&& n-&next
&&&&& 图5：有N个节点的链表，删除中间一个（这里图示删除第2个）
&&&&& 结合原链表和删除后的链表，就很容易写出相应的代码。操作方法如下：
&&&&& 1、你要明白head就是第1个节点，1-&next就是第2个节点，2-&next就是第3个节点；
&&&&&&2、删除后2，1指向第3个节点，就是让1-&next=2-&next。
&&&&& 删除指定学号的节点的函数为：
&&&&&& 单向链表的插入图示：
&&&&&& ----&[NULL]（原链表）
&&&&& head
&&&&& ----&[1]----&[NULL]（插入后的链表）
&&&&& head&& 1-&next
&&&&& 图7 空链表插入一个节点
&&&&& 结合原链表和插入后的链表，就很容易写出相应的代码。操作方法如下：
&&&& 1、你要明白空链表head指向NULL就是head=NULL；
&&&& 2、插入后head指向第1个节点，就是让head=1,1-&next=NULL,OK这样就行了。
&&&& ----&[1]----&[2]----&[3]...----&[n]----&[NULL]（原链表）
&&&& head&& 1-&next& 2-&next& 3-&next&& n-&next
&&&& ----&[1]----&[2]----&[x]----&[3]...----&[n]----&[NULL]（插入后的链表）
&&&& head&& 1-&next& 2-&next& x-&next& 3-&next&& n-&next
&&&& 图8：有N个节点的链表，插入一个节点（这里图示插入第2个后面）
&&&& 结合原链表和插入后的链表，就很容易写出相应的代码。操作方法如下：
&&& 1、你要明白原1-&next就是节点2，2-&next就是节点3；
&&& 2、插入后x指向第3个节点,2指向x，就是让x-&next=2-&next,1-&next=x。
&&& 插入指定节点的后面的函数为：
&&&&&& 单向链表的反序图示：
&&&&&& ----&[1]----&[2]----&[3]...----&[n]----&[NULL]（原链表）
&&&&&& head&& 1-&next& 2-&next& 3-&next&& n-&next
&&&&& [NULL]&----[1]&----[2]&----[3]&----...[n]&----（反序后的链表）
&&&&&&&&&&&&&& &1-&next& 2-&next& 3-&next&& n-&next& head
&&&&&&&&& 图9：有N个节点的链表反序
&&&&&&&&& 结合原链表和插入后的链表，就很容易写出相应的代码。操作方法如下：
& &&&&&&& 1、我们需要一个读原链表的指针p2,存反序链表的p1=NULL（刚好最后一个节点的next为NULL）,还有一个临时存储变量p；
&&&&&&&&& 2、p2在原链表中读出一个节点，我们就把它放到p1中，p就是用来处理节点放置顺序的问题；
&&&&&&&& &3、比如，现在我们取得一个2,为了我们继续往下取节点，我们必须保存它的next值，由原链表可知p=2-&
&&&&&&&&& 4、然后由反序后的链表可知，反序后2-&next要指向1，则2-&next=1;
&&&&&&&&&&5、好了，现在已经反序一个节点，接着处理下一个节点就需要保存此时的信息：
&&&&&&&&&&p1变成刚刚加入的2，即p1=2;p2要变成它的下一节点，就是上面我们保存的p,即p2=p。
&&&&&&&&& 反序链表的函数为：
&&&&&&&&& 对链表进行选择排序的基本思想就是反复从还未排好序的那些节点中，选出键值（就是用它排序的字段，我们取学号num为键值）最小的节点，依次重新组合成一个链表。
&&&&&&&& 我认为写链表这类程序，关键是理解：head存储的是第一个节点的地址，head-&next存储的是第二个节点的地址；任意一个节点p的地址，只能通过它前一个节点的next来求得。
&&&&&&& 单向链表的选择排序图示：
&&&&&&&& ----&[1]----&[3]----&[2]...----&[n]----&[NULL]（原链表）
&&&&&&&& head&& 1-&next& 3-&next& 2-&next&& n-&next
&&&&&&&& ----&[NULL]（空链表）
&&&&&&& first
&&&&&&& tail
&&&&&&&& ----&[1]----&[2]----&[3]...----&[n]----&[NULL]（排序后链表）
&&&&&&&& first&& 1-&next& 2-&next& 3-&next&& tail-&next
&&&&&&&& 图10：有N个节点的链表选择排序
&&&&&&& 1、先在原链表中找最小的，找到一个后就把它放到另一个空的链表中；
&&&&&&& 2、空链表中安放第一个进来的节点，产生一个有序链表,并且让它在原链表中分离出来（此时要注意原链表中出来的是第一个节点还是中间其它节点）；
&&&&&&& 3、继续在原链表中找下一个最小的，找到后把它放入有序链表的尾指针的next,然后它变成其尾指针；
&&&&&&&&对链表进行选择排序的函数为：
&&&&&&&&&& 对链表进行直接插入排序的基本思想就是假设链表的前面n-1个节点是已经按键值（就是用它排序的字段，我们取学号num为键值）排好序的，对于节点n在这个序列中找插入位置，使得n插入后新序列仍然有序。按照这种思想，依次对链表从头到尾执行一遍，就可以使无序链表变为有序链表。
&&&&&&&& 单向链表的直接插入排序图示：
&&&&&&&& ----&[1]----&[3]----&[2]...----&[n]----&[NULL]（原链表）
&&&&&&& head&& 1-&next& 3-&next& 2-&next&& n-&next
&&&&&&&& ----&[1]----&[NULL]（从原链表中取第1个节点作为只有一个节点的有序链表）
&&&&&&& head
&&&&&&& 图11
&&&&&&& ----&[3]----&[2]...----&[n]----&[NULL]（原链表剩下用于直接插入排序的节点）
&&&&&&& first&& 3-&next& 2-&next&& n-&next
&&&&&&& 图12
&&&&&&& ----&[1]----&[2]----&[3]...----&[n]----&[NULL]（排序后链表）
&&&&&&& head&& 1-&next& 2-&next& 3-&next&& n-&next
&&&&&&& 图13：有N个节点的链表直接插入排序
&&&&&& 1、先在原链表中以第一个节点为一个有序链表，其余节点为待定节点。
&&&&&& 2、从图12链表中取节点，到图11链表中定位插入。
&&&&&& 3、上面图示虽说画了两条链表，其实只有一条链表。在排序中，实质只增加了一个用于指向剩下需要排序节点的头指针first罢了。
&&&&&& 这一点请读者务必搞清楚，要不然就可能认为它和上面的选择排序法一样了。
&&&&&& 对链表进行直接插入排序的函数为：
&&&&&&&& 对链表进行冒泡排序的基本思想就是对当前还未排好序的范围内的全部节点，自上而下对相邻的两个节点依次进行比较和调整，让键值（就是用它排&序的字段，我们取学号num为键值）较大的节点往下沉，键值较小的往上冒。即：每当两相邻的节点比较后发现它们的排序与排序要求相反时，就将它们互换。
&&&&&&& 单向链表的冒泡排序图示：
&&&&&&& ----&[1]----&[3]----&[2]...----&[n]----&[NULL]（原链表）
&&&&&& head&& 1-&next& 3-&next& 2-&next&& n-&next
&&&&&& ----&[1]----&[2]----&[3]...----&[n]----&[NULL]（排序后链表）
&&&&&& head&& 1-&next& 2-&next& 3-&next&& n-&next
&&&&&& 图14：有N个节点的链表冒泡排序
&&&&& 任意两个相邻节点p、q位置互换图示:
&&&&& 假设p1-&next指向p，那么显然p1-&next-&next就指向q,
&&&&& p1-&next-&next-&next就指向q的后继节点，我们用p2保存
&&&&& p1-&next-&next指针。即：p2=p1-&next-&next，则有：
&&&&&& [& ]----&[p]----------&[q]----&[& ]（排序前）
&&&&&& p1-&next& p1-&next-&next& p2-&next
&&&&&& 图15
&&&&&& [& ]----&[q]----------&[p]----&[& ]（排序后）
&&&&&&&图16
&&&&& 1、排序后q节点指向p节点，在调整指向之前，我们要保存原p的指向节点地址，即：p2=p1-&next-&next；
&&&&& 2、顺着这一步一步往下推,排序后图16中p1-&next-&next要指的是p2-&next,所以p1-&next-&next=p2-&
&&&&& 3、在图15中p2-&next原是q发出来的指向，排序后图16中q的指向要变为指向p的，而原来p1-&next是指向p的，所以p2-&next=p1-&
&&&&& 4、在图15中p1-&next原是指向p的，排序后图16中p1-&next要指向q,原来p1-&next-&next（即p2)是指向q的，所以p1-&next=p2;
&&&&& 5、至此，我们完成了相邻两节点的顺序交换。
&&&&& 6、下面的程序描述改进了一点就是记录了每次最后一次节点下沉的位置，这样我们不必每次都从头到尾的扫描，只需要扫描到记录点为止。&因为后面的都已经是排好序的了。
&&&&&& 对链表进行冒泡排序的函数为：
&&&&&&& 有序链表插入节点示意图：
&&&&&&& ----&[NULL]（空有序链表）
&&&&&&& head
&&&&&& 图18：空有序链表（空有序链表好解决，直接让head指向它就是了。）
&&&&&& 以下讨论不为空的有序链表。
&&&&&&& ----&[1]----&[2]----&[3]...----&[n]----&[NULL]（有序链表）
&&&&&&& head&& 1-&next& 2-&next& 3-&next&& n-&next
&&&&&& 图18：有N个节点的有序链表
&&&&&& 插入node节点的位置有两种情况：一是第一个节点前，二是其它节点前或后。
&&&&&& ----&[node]----&[1]----&[2]----&[3]...----&[n]----&[NULL]
&&&&&& head& node-&next& 1-&next& 2-&next& 3-&next&& n-&next
&&&&&&&图19：node节点插在第一个节点前
&&&&&& ----&[1]----&[2]----&[3]...----&[node]...----&[n]----&[NULL]
&&&&& head&& 1-&next& 2-&next& 3-&next&&& node-&next& n-&next
&&&&&& 插入有序链表的函数为：
综上所述，链表的各类操作函数的完整代码如下：
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：7369次
排名：千里之外当前访客身份：游客 [
当前位置：
发布于 日 0时,
建立一个学生成绩的线性链表，对其实现插入，删除，输出，最后销毁。
代码片段(2)
1.&[代码]demo1&&&&
#include &stdio.h&
#include &stdlib.h&
struct grade {
struct grade *
typedef struct grade NODE;
//typedef为C语言的关键字，作用是为一种数据类型定义一个新名字。
//使用typedef目的一般有两个，一个是给变量一个易记且意义明确的新名字，
//另一个是简化一些比较复杂的类型声明。
struct grade *create();
//创建链表
void insert(NODE *head,NODE *pnew,int i);
//插入链表
void pdelete(NODE *head,int i);
//删除列表
void display(NODE *head);
//输出链表
void Pfree(NODE *head);
//销毁链表
int main(int argc, char *argv[]) {
struct grade *head,*
head=create();
if (head==NULL)
printf("输出创建的链表：");
display(head);
pnew=(NODE *)malloc(sizeof(NODE));
if (pnew==NULL) {
printf("创建失败！");
pnew-&score=88;
insert(head,pnew, 3);
//将新节点插入节点3的后面
printf("插入后的链表：");
display(head);
pdelete(head,3);
//删除节点3
printf("删除后的链表：");
display(head);
Pfree(head);
struct grade *create() {
NODE *head,*tail,*
head=(NODE *)malloc(sizeof(NODE));
//创建头节点。
if (head==NULL) { //创建失败返回
printf("创建失败！");
return NULL;
head-&next=NULL;
//头节点指针域置NULL
// 开始时尾指针指向头节点
printf("输入学生成绩：");
while (1) { //创建链表
scanf("%d",&score);
if (score&0) //成绩为负是退出循环
pnew=(NODE *)malloc(sizeof(NODE));
//创建新节点
if (pnew==NULL) { //创建失败返回
printf("创建失败！");
return NULL;
pnew-&score=
//新节点数据域存放输入的成绩
pnew-&next=NULL;
//新节点指针域置NULL
tail-&next=
//新节点插入到表尾
//为指针指向当前的尾节点
//返回创建链表的头指针
void insert(NODE *head,NODE *pnew,int i) {
NODE *p; //当前指针
for (j=0; j&i&&p!=NULL; j++) //p指向要插入的第i个节点
if (p==NULL) { //节点i不存在
printf("与插入的节点不存在！");
pnew-&next=p-&
//插入节点的指针域指向第i个节点的后继节点
//犟第i个节点的指针域指向插入的新节点
void pdelete(NODE *head,int i) {
NODE *p,*q;
if (i==0) //删除的是头指针，返回
for (j=1; j&i&&p-&next!=NULL; j++)
//将p指向要删除的第i个节点的前驱节点
if (p-&next==NULL) { //表明链表中的节点不存在
printf("不存在！");
//q指向待删除的节点
p-&next=q-&
//删除节点i，也可写成p-&next=p-&next-&next
//释放节点i的内存单元
void display(NODE *head) {
for (p=head-& p!=NULL; p=p-&next)
printf("%d ",p-&score);
printf("\n");
void pfree(NODE *head) {
NODE *p,*q;
while (p-&next!=NULL) { //每次删除头节点的后继节点
p-&next=q-&
free(head);
//最后删除头节点
void Pfree(NODE *head) {
NODE *p,*q;
while (p-&next!=NULL) {
p-&next=q-&
2.&[代码]demo2&&&&
#include &stdio.h&
#include &malloc.h&
#include &conio.h&
#include &stdlib.h&
//链表单元定义，链表相关变量
struct student {
struct student *
//输入数据创建链表
void input() {
struct student *
printf("\n\n请输入学生的信息以学号为0结束:\n");
printf("ID\t成绩\n");
if ((tmp=(struct student *)malloc(sizeof(struct student)))==NULL) {
printf("\n错误!不能申请所需的内存!\n");
scanf("%d\t%f",&tmp-&id,&tmp-&score);
tmp-&next=NULL;
if (tmp-&id!=0) {
if (head==NULL) {
pthis-&next=
pthis=pthis-&
} while (tmp-&id!=0);
free(tmp);
//搜索链表找到第一个符合条件的项目输出
void search(int id) {
printf("\n\n查询结果\n");
printf("ID\t成绩\n");
printf("-------------------------------\n");
if (head==NULL) {
printf("\n错误!没有数据!\n");
while (pthis!=NULL) {
if (pthis-&id==id) {
printf("%d\t%.2f\n",pthis-&id,pthis-&score);
pthis=pthis-&
printf("\n没有找到!\n");
//列表输出链表中的所有项
void list() {
printf("\n\n数据列表\n");
printf("ID\t成绩\n");
printf("-------------------------------\n");
if (head==NULL) {
printf("错误,没有数据!\n");
while (pthis!=NULL) {
printf("%d\t%.2f\n",pthis-&id,pthis-&score);
pthis=pthis-&
//插入数据
void insert() {
struct student *
if (head==NULL) {
printf("\n\n数据不存在，无法插入!\n");
printf("\n请输入插入点:\n");
scanf("%d",&p);
if (p&0) {
printf("输入不合法!");
printf("\n\n请输入学生的信息:\nID\t成绩\n");
if ((tmp=(struct student *)malloc(sizeof(struct student)))==NULL) {
printf("\n错误!不能申请所需的内存!\n");
scanf("%d\t%f",&tmp-&id,&tmp-&score);
tmp-&next=NULL;
if (tmp-&id!=0) {
if (p==0) {
tmp-&next=
for (i=0; i&p-1; i++) {
if (pthis-&next-&next==NULL) {
printf("\n找不到插入点，您输入的数据太大!\n");
pthis=pthis-&
tmp-&next=pthis-&
pthis-&next=
printf("\n数据无效!\n");
free(tmp);
//追加数据
void append() {
struct student *
printf("\n\n请输入学生的信息:\nID\t成绩\n");
if ((tmp=(struct student *)malloc(sizeof(struct student)))==NULL) {
printf("\n错误!不能申请所需的内存!\n");
scanf("%d\t%f",&tmp-&id,&tmp-&score);
tmp-&next=NULL;
if (tmp-&id!=0) {
if (head==NULL) {
while (pthis-&next!=NULL) {
pthis=pthis-&
pthis-&next=
free(tmp);
printf("\n数据无效!\n");
//删除数据
void del() {
struct student *
if (head==NULL) {
printf("\n\n没有数据，无法删除!\n");
printf("\n\n请输入要删除的记录号:\n");
scanf("%d",&p);
if (p&0) {
printf("\n输入不合法!\n");
if (p==0) {
head=pthis-&
free(pthis);
for (i=0; i&p-1; i++) {
pthis=pthis-&
if (pthis-&next==NULL) {
printf("\n\n指定记录不存在，无法删除!\n");
tmp=pthis-&
pthis-&next=pthis-&next-&
free(tmp);
//程序主函数
void main() {
char command=0;
printf("\n\n\t 菜单\n");
printf("-------------------------------\n");
printf("\ta,输入数据\n");
printf("\tb,查询记录\n");
printf("\tc,数据列表\n");
printf("\td,追加记录\n");
printf("\te,插入记录\n");
printf("\tf,删除记录\n");
printf("\tg,退出系统\n");
printf("-------------------------------\n");
printf("\t请选择:");
command=getch();
//命令处理
switch (command) {
if (head==NULL) {
printf("\n\n数据已经存在！\n");
printf("\n\n要查询的ID:");
scanf("%d",&id);
search(id);
} while (command!='g');
开源中国-程序员在线工具：
相关的代码(2689)
开源从代码分享开始
mickelfeng的其它代码