关于链表
请具体讲一下链表。
全部回答
链表属于数据结构的范畴。数据结构包含两方面的内容：一是数据，二是数据与
数据之间存在的关系。例如，某大学有一个课题组，课题组有一位导师，带有两个研究
生，每个研究生又负责指导三个本科生，这样，就形成了"导师-研究生-本科生"的数
据链关系。
实际上，数据元素具有广泛的含义，一般说来，现实世界中客观存在的一切 个体都可以是数据元素，例如常见的计算机部件如"内存"、"硬盘"、"显卡"等都可以 认为是"计算机"的数据元素。 总之，在数据处理领域中，每一个需要处理的对象都可以 抽象成数据元素。
数据结构中的数据元称为结点，数据结构由结点的非空有限集合和结点之间关系 的有限集合组成。两数据对象之间的关系可用数据偶来表示。若数据a与数据b有关系， 记成数据偶(a,b)，并称a是b的前驱结点，b是a的后继结点。
数据结构按其结点间的关 系分类，可分为线性表(单链表)、栈、队列、树、二叉树、图等（本教材主要介绍链表 、栈、队列、二叉树的概念及其应用）。程序存储数据结构的主要方法有顺序存储和链 接存储两种。
顺序存储可用大家目前都已经很熟悉的数组来实现；链式存储中，每个结 点除其数据部分外，还有一个指向后继结点的指针，用于指向结点的后继结点，以体现 结点之间的关系。 其中线性表是最简单的数据结构。
本章所介绍的链表与前面介绍的数组同属于线性表，两者的不同点在于：数组是 顺序存储结构，数组中的各个元素在存储位置上是相邻的；而链表是链式存储结构，链 表中的元素并不能够保证存储位置的相邻，也就是说物理上不一定连续。
由于数组的存 储是利用数组元素的物理存储空间的相邻性来表示数组元素之间的逻辑相邻，显然它具 有存储结构简单、存储利用率高、存取速度快、查找方便等优点，但是这种存储方式在 某些时候应用起来却是十分不方便，效率比较低。
尤其是在进行插入或者删除操作的时 候，通常情况下都要移动大量的数据元素以保证存储在相邻空间的两个元素在逻辑上是 相邻的，极端情况如删除数组的首元素或在首元素之前插入数据，这样这个数组中的所 有数据要全部被移动一次。
而且，由于目前大量使用的还是定长数组，其存储空间大小 通常是在程序第一次为数组分配空间的时候就确定下来了，对于一些具体的情况，经常 难以确定数组的大小，那就不得不为数组分配一个足够大的内存空间以保证程序的正常 运行，这样就造成了内存空间的不必要的浪费。
对于动态数组，也可以采用在数组增长 的时候重新分配内存，然后将原始数据拷贝到新的数组的做法，当然，其效率可想而知 。 链表的链式存储结构恰是针对数组的不足而设计的，它是一种以链式结构存储的 线性表。
由于是链式结构，它可以快速地进行元素的插入和删除操作而不需要移动大量 的数据，只要进行简单的指针指向的操作就可以了；链表中数据元素的存储空间是在程 序运行过程中动态分配的，可以根据实际需要扩展或释放存储空间，这在一定程度上避 免了存储空间的浪费。
链表中的所有数据元素都分别存储在一个个具有相同数据结构的结点里面。结点 是链表的基本存储单元，一个结点与一个数据元素一一对应。每个结点内部都是内存中 一块连续的存储空间，一般来说各个结点的存储空间是不连续的。
前面已经介绍，链表 是链式存储的，那么如何实现链式存储呢？解决的办法是定义一个结构体，保存链表结 点的数据，这个结构体中包含有指向下一个同结构结点的指针。 链表的存储结构在内存 空间上通常由两个域组成，一个称为数据域data，另一个称为指针域link。
数据域用 来存储用户的数据，而指针域是一个结点结构类型的指针，用来指向下一个结点的位置 。链表结点的结构定义方式举例如下： struct stu { int num ; float value ; char name [20] ; … struct stu * next ; 指针域link }; 上述结构就是典型的链表结构，如果利用上述结构定义一系列结构体变量，则这 些变量可以认为是该链表上的结点。
定义在该链表结构上的任何一个结点均包含了 struct stu的所有属性，在这个链表的结点中声明了一个整型变量num、一个实型变量 value和一个字符型数组name。
结点数据域中的所有数据均可以声明为系统提供的或者 自己定义的任何类型的变量。 在struct stu结构中，又声明了一个该结点类型的指针 变量next，这个指针是一个动态指针，用来指向下一个结点，通过next指针，一个个 结点被依次连接起来，就形成了链表，如图11-1所示。
为了更清楚地理解链表的结构 ，图11-2表示了链表在内存中的存储情况。 从这个存储示意图可以看出，原来一段连 续的内存空间，如图11-2(a)，经过一段运行后两个相邻结点的存储空间未必是连续的 ，链表所占的内存空间的大小随着结点的插入或者删除而增减。
图11-1 链表存储结构示意图 图11-2 链表存储情况示意图 图11-2b说明：指针first指向结点a0；结点a0的指针域的指针指向结点a1；结 点a1的指针域的指针指向结点a2；结点a2的指针域的指针指向结点a3。
如何结束一个 链表呢？办法很简单，只要将链表中最后一个结点的指针域next 指向NULL，就表示该 结点已经是链表的最后一个结点了。特殊情况如空链表，first指向NULL。
。
实际上，数据元素具有广泛的含义，一般说来，现实世界中客观存在的一切 个体都可以是数据元素，例如常见的计算机部件如"内存"、"硬盘"、"显卡"等都可以 认为是"计算机"的数据元素。 总之，在数据处理领域中，每一个需要处理的对象都可以 抽象成数据元素。
数据结构中的数据元称为结点，数据结构由结点的非空有限集合和结点之间关系 的有限集合组成。两数据对象之间的关系可用数据偶来表示。若数据a与数据b有关系， 记成数据偶(a,b)，并称a是b的前驱结点，b是a的后继结点。
数据结构按其结点间的关 系分类，可分为线性表(单链表)、栈、队列、树、二叉树、图等（本教材主要介绍链表 、栈、队列、二叉树的概念及其应用）。程序存储数据结构的主要方法有顺序存储和链 接存储两种。
顺序存储可用大家目前都已经很熟悉的数组来实现；链式存储中，每个结 点除其数据部分外，还有一个指向后继结点的指针，用于指向结点的后继结点，以体现 结点之间的关系。 其中线性表是最简单的数据结构。
本章所介绍的链表与前面介绍的数组同属于线性表，两者的不同点在于：数组是 顺序存储结构，数组中的各个元素在存储位置上是相邻的；而链表是链式存储结构，链 表中的元素并不能够保证存储位置的相邻，也就是说物理上不一定连续。
由于数组的存 储是利用数组元素的物理存储空间的相邻性来表示数组元素之间的逻辑相邻，显然它具 有存储结构简单、存储利用率高、存取速度快、查找方便等优点，但是这种存储方式在 某些时候应用起来却是十分不方便，效率比较低。
尤其是在进行插入或者删除操作的时 候，通常情况下都要移动大量的数据元素以保证存储在相邻空间的两个元素在逻辑上是 相邻的，极端情况如删除数组的首元素或在首元素之前插入数据，这样这个数组中的所 有数据要全部被移动一次。
而且，由于目前大量使用的还是定长数组，其存储空间大小 通常是在程序第一次为数组分配空间的时候就确定下来了，对于一些具体的情况，经常 难以确定数组的大小，那就不得不为数组分配一个足够大的内存空间以保证程序的正常 运行，这样就造成了内存空间的不必要的浪费。
对于动态数组，也可以采用在数组增长 的时候重新分配内存，然后将原始数据拷贝到新的数组的做法，当然，其效率可想而知 。 链表的链式存储结构恰是针对数组的不足而设计的，它是一种以链式结构存储的 线性表。
由于是链式结构，它可以快速地进行元素的插入和删除操作而不需要移动大量 的数据，只要进行简单的指针指向的操作就可以了；链表中数据元素的存储空间是在程 序运行过程中动态分配的，可以根据实际需要扩展或释放存储空间，这在一定程度上避 免了存储空间的浪费。
链表中的所有数据元素都分别存储在一个个具有相同数据结构的结点里面。结点 是链表的基本存储单元，一个结点与一个数据元素一一对应。每个结点内部都是内存中 一块连续的存储空间，一般来说各个结点的存储空间是不连续的。
前面已经介绍，链表 是链式存储的，那么如何实现链式存储呢？解决的办法是定义一个结构体，保存链表结 点的数据，这个结构体中包含有指向下一个同结构结点的指针。 链表的存储结构在内存 空间上通常由两个域组成，一个称为数据域data，另一个称为指针域link。
数据域用 来存储用户的数据，而指针域是一个结点结构类型的指针，用来指向下一个结点的位置 。链表结点的结构定义方式举例如下： struct stu { int num ; float value ; char name [20] ; … struct stu * next ; 指针域link }; 上述结构就是典型的链表结构，如果利用上述结构定义一系列结构体变量，则这 些变量可以认为是该链表上的结点。
定义在该链表结构上的任何一个结点均包含了 struct stu的所有属性，在这个链表的结点中声明了一个整型变量num、一个实型变量 value和一个字符型数组name。
结点数据域中的所有数据均可以声明为系统提供的或者 自己定义的任何类型的变量。 在struct stu结构中，又声明了一个该结点类型的指针 变量next，这个指针是一个动态指针，用来指向下一个结点，通过next指针，一个个 结点被依次连接起来，就形成了链表，如图11-1所示。
为了更清楚地理解链表的结构 ，图11-2表示了链表在内存中的存储情况。 从这个存储示意图可以看出，原来一段连 续的内存空间，如图11-2(a)，经过一段运行后两个相邻结点的存储空间未必是连续的 ，链表所占的内存空间的大小随着结点的插入或者删除而增减。
图11-1 链表存储结构示意图 图11-2 链表存储情况示意图 图11-2b说明：指针first指向结点a0；结点a0的指针域的指针指向结点a1；结 点a1的指针域的指针指向结点a2；结点a2的指针域的指针指向结点a3。
如何结束一个 链表呢？办法很简单，只要将链表中最后一个结点的指针域next 指向NULL，就表示该 结点已经是链表的最后一个结点了。特殊情况如空链表，first指向NULL。
。
热点推荐
热度TOP
-
-
-
牙齿感觉有电一样是怎么回？
63人阅读
-
转轮术是什么意思
0人阅读
-
大岭山男科哪里看的好
0人阅读
-
长春早孕检查费用
1人阅读
相关推荐
加载中...