专栏首页我是东东强数据结构之线性表

数据结构之线性表

全文概要


线性表实现有两种方式,一种为顺序表,另一种为链表。本文分别介绍了顺序线性表单向链表双向链表循环链表的基本结构,并给出了相应的C++类代码实现。

线性表(Linear List)


顺序表(Sequential List)


在顺序实现中,数据存储在一个长度为maxSize,数据类型为ElemType数组中,并用count记录在数组中的线性表的实际元素个数。由于顺序表本质是个数组,故其中逻辑位置连续的结点,其物理存储空间也连续。

顺序表的类声明及定义如下:

Header

Implementation

SqList.h

SqList.cc

单链表(Linked List)


单链表是一种最简单的线性表的链式存储结构,单链表也称为线性链表,用它来存储线性表时,每个数据元素用一个结点(node)来存储,一个结点由两个域组成,一个是存放数据元素的val,称为数据域,一个是存储指向此链表下一个结点的指针next,称为指针域

单链表结点的类声明及定义如下:

Header

Implementation

Node.h

Node.cc

单链表在表头通常会增加一个没有存储数据元素的结点,称之为”头结点“,在单链表中增加头结点虽然增加了存储空间,但算法实现更简单,效率更高。头结点的地址可从指针head找到,指针head也称为”头指针“,其它结点的地址则由其前驱结点的next域得到。

单链表用结点中的指针域来表示数据元素之间的逻辑关系,这样逻辑上相邻的两个元素并不要求物理存储位置也相邻。即在链表中,逻辑位置连续的结点,物理存储空间不必连续

简单线性链表(Simple Linked List)

线性链表简单实现为数据成员只有头指针

简单线性链表的类声明及定义如下:

Header

Implementation

SimpleLinkList.h

SimpleLinkList.cc

单链表简单实现基础上增加了表示当前位置的序号curPosition,指向当前位置的指针curPtr,以及元素总个数count

线性链表的类声明及定义如下:

Header

Implementation

LinkList.h

LinkList.cc

双向链表(Double Linked List)


前面介绍的单链表的结点结构中只有一个指向后继的指针域,即next,这样便只能从左往右进行查找其它结点,如要查找前驱,则只有从表头出发进行查找,效率较低,双向链表通过在其结点结构中存储两个指针域backnext,分别指向该结点前驱和后继。

双向链表结点的类声明及定义如下:

Header

Implementation

DblNode.h

DblNode.cc

简单双向链表(Simple Double Linked List)

简单双向链表的类声明及定义如下:

Header

Implementation

SimpleDbLinkList.h

SimpleDbLinkList.cc

双向链表(Double Linked List)

在双向链表简单实现基础上增加了表示当前位置的序号curPosition,指向当前位置的指针curPtr,以及元素总个数count

双向链表的类声明及定义如下:

Header

Implementation

DbLinkList.h

DbLinkList.cc

循环链表(Circular Linked List)


循环链表是另一种形式的线性表链式存储结构,它的结点结构与普通单链表相同,不同的是在循环链表中尾结点的next域不为空,而是指向起头结点,这样就将单链表首尾相接成为一个环。故而,循环链表判空的条件为:head->next == head

简单循环链表(Simple Circular Linked List)

简单循环链表的类声明及定义如下:

Header

Implementation

SimpleCircLinkList.h

SimpleCircLinkList.cc

循环链表(Circur Linked List)

在循环链表简单实现基础上增加了表示当前位置的序号curPosition,指向当前位置的指针curPtr,以及元素总个数count

循环链表的类声明及定义如下:

Header

Implementation

CircLinkList.h

CircLinkList.cc

参考资料


[1]数据结构与算法(C++版) - 唐宁九主编 [2]数据结构(用面向对象方法与C++语言描述) - 殷人昆主编

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 常见算法之二叉树遍历

    所谓遍历二叉树,就是遵从某种次序,顺着某一条搜索路径访问二叉树中的各个结点,使得每个结点均被访问一次,而且仅被访问一次。本文详细介绍了二叉树的前序(又称先序)、...

    我是东东东
  • 数据结构之栈与队列(优先队列/堆)

    栈与队列是两种重要的特殊线性表,从结构上讲,两者都是线性表,但从操作上讲,两者支持的基本操作却只是线性表操作的子集,是操作受限制的线性表。栈与队列两者最大的区别...

    我是东东东
  • 交换机与路由器详细比较

    作为计算机网络中最重要的两种数据包转发设备,交换机和路由器在功能设计方面既存在本质差别,又包含诸多相似之处,本文从两种设备的工作原理出发,详细介绍了它们之间的种...

    我是东东东
  • [微服务架构 ]Saga 模式| 如何使用微服务实现业务事务 第一部分

    最强大的事务类型之一称为两阶段提交,当第一个事务的提交取决于第二个事务的完成时,它是摘要。特别是当您必须同时更新多个实体时,例如确认订单和立即更新库存时,它非常...

    首席架构师智库
  • 收藏 | 统计学最全思维导图,附下载链接

    本文用一系列「思维导图浅入深的总结了「统计学」领域的基础知识,是对之前系列文章做的一次完整的梳理,也是我至今为止所有与统计有关的学习笔记。众所周知,「统计学」是...

    用户2769421
  • cssjshtml ajax+echart折线图

    葫芦
  • Bootstrap响应式前端框架笔记十三——警告框与进度条

        在Bootstrap中,使用alert相关类可以实现简洁的警告框控件,示例如下:

    珲少
  • [AI新知] Azure机器学习正式推出时间序列预测功能

    微软为时间序列预测加入了多项新功能,包括考量时间序列资料的交叉验证,以及将资料加入时间处理,成为额外的资料特征

    阿泽
  • 经典Bug永流传---每周一“虫”(十)

    不是每个浏览器都支持gzip的,如何知道客户端是否支持gzip呢,抓包,看请求头中有个Accept-Encoding来标识对压缩的支持。原理是:当客户端请求到服...

    厦门-安仔
  • 灵异留白事件——图片下方无故留白

    本人在实践过程中偶尔遇见此等不解的状况,但往往睁一只眼闭一只眼,采取另外的方式了,而今看到原博主的一篇文章,大受启发,希望对各位博友也有所帮助~

    超然

扫码关注云+社区

领取腾讯云代金券