首页 > 其他 > 详细

七、线性表的链式存储结构

时间:2018-08-17 23:22:21      阅读:269      评论:0      收藏:0      [点我收藏+]

1、问题引入

开发数组类模板的原因在于:在创建基于顺序存储结构的线性表时,发现这样的线性表可能被误用,因为重载了数组访问操作符,使用时跟数组类似,但是线性表和数组有很大的区别,所以激发了新的需求:开发数组类替换C++原生数组类,因为原生数组类也存在着很大缺陷,使用不方便。

基于顺序存储结构的线性表的另一个缺点:插入或删除元素时,涉及到大量数据元素的移动,对于效率的影响非常大

一个新的需求:在插入或删除元素时不需要大量移动数据元素的一种数据结构,即基于链式存储结构的线性表

2、链式结构的定义

为了表示每个数据元素于其直接后继元素之间的逻辑关系;数据元素除了存储本身的信息外,还需要存储其直接后继的信息。

技术分享图片

\(a_i\)\(a_{i+1}\)是线性表中的两个相邻数据元素,在物理内存中无相邻关系。

一个数据元素包含了两部分:\(a_i\)是数据元素本身的数据信息,还有一个地址信息,地址是第\(i\)个元素的直接后继,即第\(i+1\)个的元素在内存中的地址信息。换句话说就是如果找到了第\(i\)个元素,不仅可以得到第\(i\)个元素的本身的值之外,还可以得到第\(i+1\)个元素在内存中的位置

3、链式存储逻辑结构

基于链式存储结构的线性表中,每个结点都包含数据域和指针域

  • 数据域:存储数据元素本身
  • 指针域:存储相邻结点的地址

技术分享图片

两种线性表名称统一:

  • 顺序表:基于顺序存储结构的线性表
  • 链表:基于链式存储结构的线性表
    • 单链表:每个结点只包含直接后继的地址信息
    • 循环链表:单链表的最后一个结点的直接后继为第一个结点
    • 双向链表:单链表中的结点包含直接前驱和后继的地址信息
    • 双向循环链表......

4、链表中的基本概念

  • 头结点:链表中的辅助结点,包含指向第一个数据元素的指针;不包含任何数据信息,是为了简化代码进行辅助
  • 数据结点:链表中代表数据元素的结点,表现形式为:(数据元素,地址)
  • 尾结点:链表中的最后一个数据结点。单独放出的原因:尾结点包含的地址信息直接决定了链表的性质,地址信息为空,就是单链表;地址为第0个元素的地址信息,就是循环链表;地址信息为随机值,就是一个非法链表

5、单链表

5.1 单链表中的结点定义

// 用struct定义类,默认属性是public
// T是泛指类型,链表可以存储各种类型的数据
struct Node : public Object
{
    T value;
    Node* next; // 指向后继结点的指针
}

5.2 单链表的内部结构

技术分享图片

头结点在单链表中的意义是:辅助数据元素的定位,方便插入和删除操作,因此,头结点不存储实际的数据元素。

5.3 在目标位置处插入数据元素

  1. 从头结点开始,通过current指针定位到目标位置

  2. 从堆空间申请新的Node结点

  3. 执行操作

    node->value = e;
    node->next = current->next;
    current->next - node;

5.4 在目标位置删除数据元素

  1. 从头结点开始,通过previous指针定位到目标位置的前一个地址

  2. 使用toDel指针指向需要删除的结点

  3. 执行操作:

    toDel = previous->next;
    previous->next = toDel->next;
    delete toDel;

6、小结

链表中的数据元素在物理内存中无相邻关系

链表中的结点都包含数据域和指针域

头结点用于辅助数据元素定位,方便插入和删除操作

插入和删除操作需要保证链表的完整性

七、线性表的链式存储结构

原文:https://www.cnblogs.com/chenke1731/p/9495573.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!