C语言单向链表的表示与实现实例详解
作者:shichen2014 时间:2022-01-24 21:38:33
1.概述:
C语言中的单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。
链表中最简单的一种是单向链表,它包含两个域,一个信息域和一个指针域。这个链接指向列表中的下一个节点,而最后一个节点则指向一个空值。
如下图所示:
一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接
一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息,第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。
链表最基本的结构是在每个节点保存数据和到下一个节点的地址,在最后一个节点保存一个特殊的结束标记,另外在一个固定的位置保存指向第一个节点的指针,有的时候也会同时储存指向最后一个节点的指针。一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点,一直访问到需要的位置。但是也可以提前把一个节点的位置另外保存起来,然后直接访问。当然如果只是访问数据就没必要了,不如在链表上储存指向实际数据的指针。这样一般是为了访问链表中的下一个或者前一个节点。
相对于双向链表,这种普通的,每个节点只有一个指针的链表也叫单向链表,或者单链表,通常用在每次都只会按顺序遍历这个链表的时候(例如图的邻接表,通常都是按固定顺序访问的)。
2.程序实现:
/* c2-2.h 线性表的单链表存储结构 */
struct LNode
{
ElemType data;
struct LNode *next;
};
typedef struct LNode *LinkList; /* 另一种定义LinkList的方法 */
/* bo2-2.c 单链表线性表(存储结构由c2-2.h定义)的基本操作(12个) */
Status InitList(LinkList *L)
{ /* 操作结果:构造一个空的线性表L */
*L=(LinkList)malloc(sizeof(struct LNode)); /* 产生头结点,并使L指向此头结点 */
if(!*L) /* 存储分配失败 */
exit(OVERFLOW);
(*L)->next=NULL; /* 指针域为空 */
return OK;
}
Status DestroyList(LinkList *L)
{ /* 初始条件:线性表L已存在。操作结果:销毁线性表L */
LinkList q;
while(*L)
{
q=(*L)->next;
free(*L);
*L=q;
}
return OK;
}
Status ClearList(LinkList L) /* 不改变L */
{ /* 初始条件:线性表L已存在。操作结果:将L重置为空表 */
LinkList p,q;
p=L->next; /* p指向第一个结点 */
while(p) /* 没到表尾 */
{
q=p->next;
free(p);
p=q;
}
L->next=NULL; /* 头结点指针域为空 */
return OK;
}
Status ListEmpty(LinkList L)
{ /* 初始条件:线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE */
if(L->next) /* 非空 */
return FALSE;
else
return TRUE;
}
int ListLength(LinkList L)
{ /* 初始条件:线性表L已存在。操作结果:返回L中数据元素个数 */
int i=0;
LinkList p=L->next; /* p指向第一个结点 */
while(p) /* 没到表尾 */
{
i++;
p=p->next;
}
return i;
}
Status GetElem(LinkList L,int i,ElemType *e) /* 算法2.8 */
{ /* L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */
int j=1; /* j为计数器 */
LinkList p=L->next; /* p指向第一个结点 */
while(p&&j<i) /* 顺指针向后查找,直到p指向第i个元素或p为空 */
{
p=p->next;
j++;
}
if(!p||j>i) /* 第i个元素不存在 */
return ERROR;
*e=p->data; /* 取第i个元素 */
return OK;
}
int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ /* 初始条件: 线性表L已存在,compare()是数据元素判定函数(满足为1,否则为0) */
/* 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。 */
/* 若这样的数据元素不存在,则返回值为0 */
int i=0;
LinkList p=L->next;
while(p)
{
i++;
if(compare(p->data,e)) /* 找到这样的数据元素 */
return i;
p=p->next;
}
return 0;
}
Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)
{ /* 初始条件: 线性表L已存在 */
/* 操作结果: 若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱, */
/* 返回OK;否则操作失败,pre_e无定义,返回INFEASIBLE */
LinkList q,p=L->next; /* p指向第一个结点 */
while(p->next) /* p所指结点有后继 */
{
q=p->next; /* q为p的后继 */
if(q->data==cur_e)
{
*pre_e=p->data;
return OK;
}
p=q; /* p向后移 */
}
return INFEASIBLE;
}
Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e)
{ /* 初始条件:线性表L已存在 */
/* 操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继, */
/* 返回OK;否则操作失败,next_e无定义,返回INFEASIBLE */
LinkList p=L->next; /* p指向第一个结点 */
while(p->next) /* p所指结点有后继 */
{
if(p->data==cur_e)
{
*next_e=p->next->data;
return OK;
}
p=p->next;
}
return INFEASIBLE;
}
Status ListInsert(LinkList L,int i,ElemType e) /* 算法2.9。不改变L */
{ /* 在带头结点的单链线性表L中第i个位置之前插入元素e */
int j=0;
LinkList p=L,s;
while(p&&j<i-1) /* 寻找第i-1个结点 */
{
p=p->next;
j++;
}
if(!p||j>i-1) /* i小于1或者大于表长 */
return ERROR;
s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
s->data=e; /* 插入L中 */
s->next=p->next;
p->next=s;
return OK;
}
Status ListDelete(LinkList L,int i,ElemType *e) /* 算法2.10。不改变L */
{ /* 在带头结点的单链线性表L中,删除第i个元素,并由e返回其值 */
int j=0;
LinkList p=L,q;
while(p->next&&j<i-1) /* 寻找第i个结点,并令p指向其前趋 */
{
p=p->next;
j++;
}
if(!p->next||j>i-1) /* 删除位置不合理 */
return ERROR;
q=p->next; /* 删除并释放结点 */
p->next=q->next;
*e=q->data;
free(q);
return OK;
}
Status ListTraverse(LinkList L,void(*vi)(ElemType))
/* vi的形参类型为ElemType,与bo2-1.c中相应函数的形参类型ElemType&不同 */
{ /* 初始条件:线性表L已存在 */
/* 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */
LinkList p=L->next;
while(p)
{
vi(p->data);
p=p->next;
}
printf("\n");
return OK;
}
/* algo2-5.c 主程序 */
#include"c1.h"
typedef int ElemType;
#include"c2-2.h"
#include"bo2-2.c"
void CreateList(LinkList *L,int n) /* 算法2.11 */
{ /* 逆位序(插在表头)输入n个元素的值,建立带表头结构的单链线性表L */
int i;
LinkList p;
*L=(LinkList)malloc(sizeof(struct LNode));
(*L)->next=NULL; /* 先建立一个带头结点的单链表 */
printf("请输入%d个数据\n",n);
for(i=n;i>0;--i)
{
p=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
scanf("%d",&p->data); /* 输入元素值 */
p->next=(*L)->next; /* 插入到表头 */
(*L)->next=p;
}
}
void CreateList2(LinkList *L,int n)
{ /* 正位序(插在表尾)输入n个元素的值,建立带表头结构的单链线性表 */
int i;
LinkList p,q;
*L=(LinkList)malloc(sizeof(struct LNode)); /* 生成头结点 */
(*L)->next=NULL;
q=*L;
printf("请输入%d个数据\n",n);
for(i=1;i<=n;i++)
{
p=(LinkList)malloc(sizeof(struct LNode));
scanf("%d",&p->data);
q->next=p;
q=q->next;
}
p->next=NULL;
}
void MergeList(LinkList La,LinkList *Lb,LinkList *Lc)/* 算法2.12 */
{ /* 已知单链线性表La和Lb的元素按值非递减排列。 */
/* 归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列 */
LinkList pa=La->next,pb=(*Lb)->next,pc;
*Lc=pc=La; /* 用La的头结点作为Lc的头结点 */
while(pa&&pb)
if(pa->data<=pb->data)
{
pc->next=pa;
pc=pa;
pa=pa->next;
}
else
{
pc->next=pb;
pc=pb;
pb=pb->next;
}
pc->next=pa?pa:pb; /* 插入剩余段 */
free(*Lb); /* 释放Lb的头结点 */
Lb=NULL;
}
void visit(ElemType c) /* ListTraverse()调用的函数(类型要一致) */
{
printf("%d ",c);
}
void main()
{
int n=5;
LinkList La,Lb,Lc;
printf("按非递减顺序, ");
CreateList2(&La,n); /* 正位序输入n个元素的值 */
printf("La="); /* 输出链表La的内容 */
ListTraverse(La,visit);
printf("按非递增顺序, ");
CreateList(&Lb,n); /* 逆位序输入n个元素的值 */
printf("Lb="); /* 输出链表Lb的内容 */
ListTraverse(Lb,visit);
MergeList(La,&Lb,&Lc); /* 按非递减顺序归并La和Lb,得到新表Lc */
printf("Lc="); /* 输出链表Lc的内容 */
ListTraverse(Lc,visit);
}
标签:C语言,单向链表
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
关于java数组与字符串相互转换的问题
2021-08-08 18:50:31
Android scheme 跳转的设计与实现详解
2021-07-29 03:42:52
Android 中RecycleView实现item的点击事件
2023-10-21 18:59:13
Springmvc拦截器执行顺序及各方法作用详解
2023-06-10 08:11:46
深入学习Java 热部署的知识
2023-10-16 18:23:24
![](https://img.aspxhome.com/file/2023/3/71673_0s.png)
快速解决commons-fileupload组件无法处理自定义head信息的bug
2023-03-05 15:20:14
Java 改造ayui表格组件实现多重排序
2022-05-15 07:34:15
![](https://img.aspxhome.com/file/2023/1/64891_0s.jpg)
Spring Boot 开发环境热部署详细教程
2023-07-28 01:50:02
Java使用entrySet方法获取Map集合中的元素
2022-08-06 17:41:05
Java 数组元素倒序的三种方式(小结)
2022-04-01 22:59:19
使用Maven配置Spring的方法步骤
2023-02-05 18:37:46
Android实现底部支付弹窗效果
2022-06-12 13:39:43
![](https://img.aspxhome.com/file/2023/9/109229_0s.gif)
Java泛型变量如何添加约束
2021-06-02 23:12:06
java静态工具类注入service出现NullPointerException异常处理
2021-11-28 09:59:11
![](https://img.aspxhome.com/file/2023/0/88520_0s.jpg)
解析在内部循环中Continue外部循环的使用详解
2023-09-24 08:03:50
android开发之关闭所有的activity的方法
2022-01-16 18:21:29
Java编程Nashorn实例代码
2022-07-30 05:28:21
深入C#中使用SqlDbType.Xml类型参数的使用详解
2022-07-24 13:56:18
C#入门之定义类成员与接口实现
2023-05-25 09:50:58
C# 读写自定义的Config文件的实现方法
2022-09-08 23:22:35
![](https://img.aspxhome.com/file/2023/5/91365_0s.png)