线性表

1、线性表的定义 线性表(List):零个或多个数据元素的有限序列

第一个元素无前驱,最后一个元素无后继,其他元素都有且只有一个前驱和后继。然后,线性表强调是有限的,

线性表元素的个数n(n≥0)定义为线性表的长度,当n=0时,成为空表。

2、线性表的抽象数据类型

对于不同的应用,线性表的基本操作是不同的,上述操作是最基本的,对于实际问题中涉及的关于线性表的更复杂操作,完全可以用这些基本操作的组合来实现。

3、线性表的顺序存储结构

3.1顺序存储定义

线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。 存储单元存储数据元素

3.2顺序存储结构的插入与删除 3.2.1

插入

删除1

删除2

3.2.2线性表顺序存储结构的优缺点 优点: ①无须为表示表中元素之间的逻辑关系而增加额外的存储空间 ②可以快速地存取表中任一位置的元素

缺点: ①插入和删除操作需要移动大量元素 ②当线性表长度变化较大时,难以确定存储空间的容量 ③造成存储空间的“碎片”

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

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。这就意味着,这些数据元素可以存在内存未被占用的任意位置 以前在顺序结构中,每个数据元素只需要存数据元素信息,现在链式结构中,除了要存储元素信息外,还要存储它的后继元素的存储地址。

头指针与头结点的异同

image.png

结点由存放数据元素的数据域以及存放后继结点地址的指针域组成。

单链表结构与顺序存储结构优缺点

image.png

结论:若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构。若需要频繁插入和删除时,宜采用单链表结构。

5、静态链表

C语言具有指针能力,使得它可以非常容易操作内存中的地址和数据,但有些语言没有指针,可以用数组代替。 我们让数组的元素都是由两个数据域组成,data 和cur。也就是说,数组的每一个下标都对应一个data和一个cur。数据域data,用来存放数据元素,也就是通常我们要处理的数据,而游标cur相当于单链表中国的nexe指针,存放该元素的后继在数组中的下标。 我们把这种用数组描述的链表叫做静态链表,这种描述方法还有起名叫做游标实现法。

假设我们已经将数据存入静态链表,比如分别存放着“甲”、“乙”、“丁”、“戊”、“己”、“庚”等数据,则它将处于下图状态:

此时“甲”这里存有下一元素“乙”的游标2,“乙”则存有下一元素“丁”的下标3,而“庚”是最后一个有值元素,所以它的cur设置为0。而最后一个元素的cur则因“甲”是第一有值元素而存有它的下标为1.而第一个元素则因空闲空间的第一个元素下标为7,所以它的cur存有7。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java进阶之路

ArrayList 源码剖析

13000
来自专栏desperate633

LintCode 子集题目代码

8530
来自专栏趣学算法

数据结构 第4-2讲 双向链表

链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢?

12840
来自专栏marsggbo

链表、头指针、头结点

 图1为线性表(ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG)的逻辑状态。头指针 指示链表中第一个结点(即第一个数据元素...

24370
来自专栏赵俊的Java专栏

LeetCode 804 Unique Morse Code Words

首先为每个单词的每个字符进行转码, 将转码后的数据放到 Set 集合中, 最后返回 Set 的长度。

11040
来自专栏xingoo, 一个梦想做发明家的程序员

二叉堆

容易证明: 一棵高为h的完全二叉树有2^h 到 2^(h+1)-1个结点。 这就意味着,完全二叉树的高是[logN] 特点: 任意位置i: 左儿子在位置2i上,...

21280
来自专栏Golang语言社区

问题帖子--Concurrent Read/Write Map

DK1.5 引入了 concurrent package, 提供了更多的concurrent 控制方法。 还提供了一个 ConcurrentHashMap 类...

35750
来自专栏Java帮帮-微信公众号-技术文章全总结

HashSet 源码分析【面试+工作】

在工作中,经常有这样的需求,需要判断某个ID是否在某个组的管理之下等,就需要查询该组下的ID放到一个集合中,且集合中元素不能有重复,之后判断该集合是否包含我们的...

12630
来自专栏软件开发 -- 分享 互助 成长

java中大数类的学习

java中提供了大数类BigInteger和BigDecimal分别表示大整数类和大浮点数类,这两个类都在java.math.*包中,因此每次必须在开头处引用该...

25350
来自专栏Java3y

List集合就这么简单【源码剖析】

22240

扫码关注云+社区

领取腾讯云代金券