线性表之链式存储结构
线性表的链式存储结构特点
用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。这些数据可以存在内存未被占用的任意位置。
在顺序结构中,每个数据元素只需要存数据元素信息就可以了。
但在链式结构中,除了要存数据元素信息外,还要存储它的后继元素的存储地址。
对数据元素a_i来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素a_1的存储映像,称为节点(Node)。
对于线性表来说,总得有个头有个尾,链表也不例外。我们把链表中第一个节点的存储位置叫做头指针,那么整个链表的存取就必须是从头指针开始进行了。之后的每一个节点,其实就是上一个的后继指针指向的位置。想象一下,最后一个节点,它的指针指向哪里?
最后一个,当然就意味着直接后继不存在了,所以我们规定,线性链表的最后一个节点指针为“空”(通常用 NULL 或 “^” 符号表示)
为了更加方便地对链表进行操作,会在单链表的第一个节点前附设一个节点,称为头节点。头节点的数据域可以不存储任何信息。也可以存储如线性表的长度等附加信息,头节点的指针域存储指向第一个节点的指针。
线性表的链式存储头节点和头指针
头指针
- 头指针是指链表指向第一个节点的指针,若链表有头节点,则是指向头节点的指针。
- 头指针具有标识作用,所以常用头指针冠以链表的名字。
- 无论链表是否为空,头指针均不为空。头指针是链表的必要元素。
头节点
- 头节点是为了操作的统一和方便而设立的,放在第一个元素的节点之前,其数据域一般无意义。
- 有了头节点,对在第一元素节点前插入节点和删除第一节点,其操作与其他节点的操作就统一了。
- 头节点不一定是链表必须要素。
获得链表第 i 个数据的算法思路
声明一个指针 p 指向链表第一个节点,初始化 j 从 1 开始;
当 j < i 时,就遍历链表,让 p 的指针向后移动,不断指向下一节点,j 累加 1;
若到链表末尾 p 为空,则说明第 i 个节点不存在;
否则查找成功,返回节点 p 的数据。
从头开始找,直到找到第 i 个节点为止。由于这个算法的时间复杂度取决于 i 的为止,当 i=1 时,则不需遍历,第一个就取出数据了,而当 i=n 时则遍历 n-1 次才可以。因此最坏情况的时间复杂度是 O(n)。
单链表的结构中没有定义表长,所以不能事先直到要循环多少次,因此也就不方便使用 for 来控制循环。其主要核心思想就是“工作指针后移”,这其实也是很多算法的常用技术。
本作品采用《CC 协议》,转载必须注明作者和本文链接