一起来看看C语言线性表的线性链表
定义
链表是通过一组任意的存储单元来存储线性表中的数据元素,每一个结点包含两个域:存放数据元素信息的域称为数据域,存放其后继元素地址的域称为指针域。因此n个元素的线性表通过每个结点的指针域连接成了一个“链条”,称为链表。若此链表的每个结点中只包含一个指针域,则被称为线性链表或单链表。
线性表的链式存储结构,它不需要用地址连续的存储单元来实现,因为它不要求逻辑上相邻的两个数据元素物理位置上也相邻,它是通过“指针”建立起数据元素之间的逻辑关系。
链表是由一个个结点构成的,结点定义如下:
typedef struct node { DataType data; struct node *next; } Linklist;
线性链表的存取必须从表头指针开始,表头指针指示线性链表中第一个结点的存储单位置。由于线性表最后一个数据元素没有直接后继,则线性链表中的最后一个结点的指针域为“空”(NULL)。
为了使用方便可以在第一个元素的前面增加一个结点(被称为头节点),该节点的数据域为空,指针域中存储线性链表的第一个元素所在的结点(表头结点)的存储地址。如果为空表,则指针域为空。
因此空链表也分为带有头结点的空链表和不带头结点的空链表。若有头结点,头结点的数据域为空,指针域为空,则说明该链表为空链表;若没有头结点,表头指针为空指针,则说明该链表为空链表。
1.插入
假设要在线性表的两个数据元素a和b之间插入一个数据元素x,p为指向结点a的指针。为了插入数据元素x,首先要生成一个数据域为x的新结点,s为指向新增节点的指针,然后使新增节点的指针域指向b(p->next),结点a的指针域指向新增节点(s)。
int InsertLinkList(LinkList *H, int i, DataType x) /*在有头结点的线性链表H中第i个位置前插入元素x*/ { LinkList *p; LinkList *s; int j = 0; p = H; while (p && j<i-1) { p = p->next; j++; }/*循环直到p指向第i-1个元素*/ if (!p) return -1;/*i大于表长加1*/ s = (LinkList *)malloc(sizeof(LinkList)); s->data = x; s->next = p->next;/*插入数据元素x*/ p->next = s; return 1; }
2.建立线性链表
1)头插法
建立线性链表应从空表开始,每读入一个数据元素则申请一个结点,然后插在链表的头结点与第一个结点之间。记头结点为H,申请的结点为s,按照上述插入算法,操作步骤为:
s->next = H->next; H->next = s;
再加上新建头结点、读入数据元素、申请结点等步骤,可编程如下:
LinkList *CreateLinkList_front() { LinkList *H;/*H表示头结点*/ LinkList *s; char x;/*设数据元素的类型为char*/ H = (LinkList *)malloc(sizeof(LinkList));/*为头结点申请内存空间*/ H->next = NULL; scanf(" %c", &x); while (x!=flag)/*flag为结束创建过程的标志,如'#'等*/ { s = (LinkList *)malloc(sizeof(LinkList)); s->data = x; s->next = H->next; H->next = s; scanf(" %c", &x); } return H; }
因为是在链表的头部插入,读入数据的顺序和线性表中的逻辑顺序是相反的。
2)尾插法
在表头插入建立线性链表方法简单,但读入数据元素的顺序与生成的链表中元素的顺序是相反的,若希望次序一致,则用尾插法。因为每次是将新结点插入到链表的尾部,所以需加入一个指针用来始终指向链表中的尾结点,以便能够将新结点插入到链表的尾部。
在前面,我们介绍了插入算法,在这里可以通过调用插入算法,即定义一个变量int i = 1;,调用前面的函数InsertLinkList(H, i, x);,每插入一个数据元素,便使i++;,这样就可一直保持在链表的尾部插入。
LinkList *CreateLinkList_rear() { LinkList *H; DataType x;/*设DataType为数据元素的类型*/ int i = 1; H = (LinkList *)malloc(sizeof(LinkList)); H->next = NULL; scanf(&x);/*读入数据元素的值*/ while (x!=flag) { InsertLinkList(H, i, x);/*调用插入算法*/ i++; scanf(&x); } return H; }
但是这样使得算法的时间复杂度比头插法要高出了一个数量级,因为每次在尾部插入数据元素时,都要重新调用InsertLinkList()函数,使指针重新从表头指针开始指向尾结点。
因此我们可以使指针(记为p)一直指向链表中的尾结点,然后让新结点(记为s)按照插入算法插入链表的尾部。只需修改上述代码的while循环即可实现:
LinkList *CreateLinkList_rear() { LinkList *H, *p, *s; DataType x;/*设DataType为数据元素的类型*/ H = (LinkList *)malloc(sizeof(LinkList)); H->next = NULL; scanf(&x);/*读入数据元素的值*/ p = H; while (x!=flag) { s = (LinkList *)malloc(sizeof(LinkList)); s->data = x; s->next = NULL; p->next = s; p = p->next; scanf(&x); } return H; }
3.删除
假设链表中有a, b, c3个数据元素,要删除数据元素a和数据元素c中间的数据元素b时,仅需修改数据元素a所在的结点的指针域。假设指针p指向数据元素a,用语句表示就是:
p->next = p->next->next;
添加一个指针变量q,让q指向数据元素b,当改变数据元素a所在的结点的指针域后,即可释放q的内存,即释放数据元素b所占的内存。进一步地,调用函数时传入标志变量i,可实现删除第i个数据元素。
int DeleteLinkList(LinkList *H, int i) /*在有头结点的线性链表H中删除第i个元素*/ { LinkList *p; LinkList *q; int j = 0; p = H; while (p->next && j<i-1) { p = p->next; j++; }/*循环直到p指向第i-1个元素*/ if (!(p->next)) return -1;/*删除节点不合法*/ q = p->next; p->next = q->next;/*删除第i个数据元素*/ free(q);/*释放第i个数据元素所占内存*/ return 1; }
对比插入算法和删除算法,while循环的功能同样是使p指向第i-1个元素,为什么插入算法的循环条件为p && j<i-1,而删除算法的循环条件是p->next && j<i-1?能否将删除算法的循环条件也改为p && j<i-1?
这是因为,在链表根本没有i-1个元素的情况下,循环条件为p && j<i-1的循环运行结果为p指向尾结点的下一个结点即p=NULL,而循环条件为p->next && j<i-1的循环运行结果为p指向尾结点即p≠NULL。若将删除算法的循环条件也改为p && j<i-1,在链表根本没有i-1个元素的情况下,while循环后面的语句if (!(p->next))将会造成非法内存访问,因为此时p=NULL,我们无法访问空指针指向的内容。
4.查找
查找结点使用的算法是线性查找法(顺序查找法),即从链表的第一个结点开始,顺着指针链一个一个比较,相等则查找成功,返回结点位置;如果比较到最后也没有相等的,则查找不成功,返回空。
LinkList *SearchLinkList(LinkList *H, DataType x) /*在线性链表H中查找值为x的结点,找到后返回其指针,否则返回空*/ { LinkList *p = H->next;/*p指向线性链表的第一个数据元素*/ while (p!=NULL && p->data!=x) p = p->next; return p; }
若要返回值为x的结点在链表中的位序,则可使用一个标记变量i,记录结点的位序;若找不到则返回-1。修改程序如下:
int SearchLinkList(LinkList *H, DataType x) /*在线性链表H中查找值为x的结点,找到后返回其在链表中的位序,否则返回-1*/ { LinkList *p = H->next;/*p指向线性链表的第一个数据元素*/ int i = 1; while (p!=NULL && p->data!=x) { p = p->next; i++; } if (p != NULL) return i; else return -1; }
5.求线性链表的表长
设H是带头结点的线性链表(线性表的长度不包括头结点),求线性链表的表长的操作与上述查找某结点在链表中的位序相似。
int LinkListLength(LinkList *H) { LinkList *p = H;/*p指向头结点*/ int n = 0; while (p->next) { p = p->next; n++; }/*p所指的是第n个结点*/ return n; }
总结
本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注猪先飞的更多内容!
原文出处:https://blog.csdn.net/weixin_60921752/article/details/122152
相关文章
- 这篇文章主要为大家详细介绍了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语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...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实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25- 这篇文章主要介绍了c语言实现找最大值最小值位置查找,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04