C语言单向链表的表示与实现实例详解
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语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
- 这篇文章主要介绍了c语言实现找最大值最小值位置查找,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04