C语言静态链表和动态链表
1. 静态链表
结构体中的成员可以是各种类型的指针变量,当一个结构体中有一个或多个成员的基类型是本结构体类型时,则称这种结构体为“引用自身的结构体”。如:
struct link { char ch; struct link *p; } a;
p是一个可以指向 struct link 类型变量的指针成员。因此,a.p = &a 是合法的表达式,由此构成的存储结构如图1所示。
图1 引用自身的结构体
例1 一个简单的链表
#include <stdio.h> struct node { int data; struct node *next; }; typedef struct node NODETYPE; int main() { //a是头结点,b是中间节点,c是尾节点 //h是基类型为NODETYPE的指针,指向头结点 //p是基类型为NODETYPE的指针,用于遍历链表 NODETYPE a, b, c, *h, *p; //给变量中的data赋值 a.data = 10; b.data = 20; c.data = 30; //将节点相连 h = &a; a.next = &b; b.next = &c; c.next = '\0'; //移动p,使之依次指向a、b、c,输出它们data中的值 p = h; while (p) { printf("%d\t", p->data); p = p->next; //p顺序后移 } printf("\n"); return 0; } STRUCT_LIST
STRUCT_LIST
以上程序中所定义的结构体类型 NODETYPE 共有两个成员:成员 data 是整型;成员 next 是指针类型,其基类型是 NODETYPE 类型。
a、b、c 是 NODETYPE 结构体类型变量,h 和 p 是指向 NODETYPE 结构体类型的指针变量。执行程序后,形成如图2所示的存储结构体:指针 h 中存放变量 a 的地址,变量 a 的成员 a.next 中存放变量 b 的地址……,最后一个变量 c 的成员 c.next 置为 '\0'(NULL)。这样就把同一类型的结构体变量 a、b、c “链接”到一起,形成所谓的“链表”,变量 a、b、c 称为链表的节点。
在此例中,链接到一起的每个节点(结构体变量 a、b、c)都是通过定义,由系统在内存中开辟了固定的、不一定连续的存储单元。在程序执行过程中,不可能人为的再产生新的存储单元,也不能认为的使已开辟的存储单元消失。这种链表成为“静态链表”。
图2 链表存储结构示意图
2.动态链表的概念
到目前为止,凡是遇到处理“批量”数据时,我们都是利用数组来存储。定义数组必须(显式的或隐含的)指明元素的个数,从而也就限定了一个数组中存放的数据量。在实际应用中,一个程序在每次运行时要处理的数据的数目通常并不确定。如果数组定义的小了,就没有足够的空间存放数据,定义大了又浪费存储空间。
对于这种情况,如果能在程序执行过程中,根据需要随时开辟存储空间,不需要时再随时释放,就能比较合理的使用存储空间。C 语言的动态存储分配提供了这种可能性。每次动态分配的存储单元,其地址不一定是连续的,而所需处理的批量数据往往是一个整体,各数据之间存在着接序关系。链表的每个节点中,除了要有存放数据本身的数据域外,至少还需要有一个指针域,用它来存放下一个节点元素的地址,以便通过这些指针把各节点连接起来(如图3)。由于链表每个存储单元都由动态存储分配获得,故称这样的链表为“动态链表”。
需要强调的是:动态链表中,每个节点没有自己的名字,只能靠指针维系节点之间的接序关系。一旦某个节点的指针“断开”,后续节点就再也无法找寻。
图3 带有头结点的单向链表
每个链表都用一个“头指针”变量来指向链表的开始,如图3中的 head。也就是说,在 head 中存放了链表的第一个节点的地址。在这个链表中,我们设置了一个“头结点”,这个节点的数据域中不存放数据(根据需要也可以不设头结点)。链表最后一个节点的指针域不存放地址,置为 '\0'(NULL) 值,标志着链表的结束。上述链表的每个节点都只有一个指针域,每个指针域存放着下一个节点的地址。因此,这种链表只能从当前节点找到后继节点,故称为“单向链表”。
相关文章
- 这篇文章主要为大家详细介绍了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实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25- 这篇文章主要介绍了c语言实现找最大值最小值位置查找,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04