链表是一种采用“链式”存储结构存储的线性表。链表的数据元素所占的存储单元地址可以是连续的,也可以是不连续的,可根据需要临时、动态地申请分配相应的存储空间,数据元素之间的逻辑关系可以用“链”来表达。
本教程操作环境:windows7系统、Dell G3电脑。
为了克服顺序表存储结构的缺点,充分利用存储空间和提高运行效率,线性表可以采用另一种存储结构——链式存储结构。线性表的链式存储结构简称“链表(link list)”
链表的数据元素所占的存储单元地址可以是连续的,也可以是不连续的,可根据需要临时、动态地申请分配相应的存储空间,数据元素之间的逻辑关系可以用“链”来表达。
链表的插入和删除不需要移动数据元素,只需要修改链即可实现。
链表分类:
1.按链表内存分配实现的方式分类
①动态链表
②静态链表
2.按链接方式分类
①单链表
②循环链表
③双链表
(它们均为动态链表)
为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系,对于每个数据元素ai,除了存储本身的信息外,还需要存储一个指示其直接后继的信息(后继的存储位置-地址)。
存储数据元素信息的域称为数据域,存储直接后继位置的域称为指针域,指针域中存储的信息称为指针或链。
这两部分信息组成数据元素ai的存储映像,称为结点。
n个结点链成一个链表,即为线性表(a1,a2,a3,...,an)的链式存储结构,因为链表的每个结点中只包含一个指针域,所以称为单链表。
对于线性表来说,总有个头有个尾,链表也不例外。链表中指向单链表第一个结点的指针叫做头指针,整个链表的存取必须从头指针开始进行,之后的每个结点都是上个结点的后继指针指向的位置。链表的最后一个结点的指针为“空(通常用NULL表示)”——空指针。
为了方便实现链表的各种运算,在单链表的第一个数据结点之前设一个类型相同的结点,该结点称为头结点。
头结点的数据域可以存储一个特殊的标志信息如链表的长度,也可以不存储任何数据。
链表的第一个数据结点和最后一个结点又称为首结点和尾结点。
头指针:
头结点:
/*线性表的单链表存储结构*/ /*结点定义*/ typedef struct Node { ElemType data; struct Node *next; }Node; /*单链表定义*/ typedef struct Node *LinkList;
假设存储元素e的结点为s,将s插入到ai结点后面,如何操作?
思考:两句插入代码能否交换?
不能,如果调换过来,会导致ai+1等后面的元素无法找到,因为s的指针域没有指向ai+1的地址。
假设存储元素ai的结点为q,要实现将结点q删除单链表的操作。
存储方式:
时间性能:
①查找
②插入和删除
空间性能:
更多相关知识,请访问常见问题栏目!
以上是链表是一种采用什么存储结构存储的线性表的详细内容。更多信息请关注PHP中文网其他相关文章!