专栏首页mathor线性表(一)

线性表(一)

这算是数据结构的第一篇文章,在这篇文章里,我要讲的是最常用,最简单的一种数据结构——线性表。看到表这个字,不要想歪了,它不是一个二维表,而是个类似数组的一维存储结构。

线性表是一种典型的线性结构,线性结构的基本特点是数据元素有序且有限,在这种结构中:

① 存在一个唯一的被称为“第一个”的数据元素;

② 存在一个唯一的被称为“最后一个”的数据元素;

③ 除第一个元素外,每个元素均有唯一一个直接前驱;

④ 除最后一个元素外,每个元素均有唯一一个直接后继。

说概念估计有些抽象,看一下下面这张图

图1 线性表

第一个(首)元素就是$a_1$,最后一个(尾)元素就是$a_6$,除了$a_1$以外,每个元素前面都有元素,这就是前驱。除了$a_6$以外,每个元素后面都有元素,这就是后继。

下面我们看个线性表的实例——学生成绩表

图2 学生成绩表

这个线性表中的每个数据元素是每个学生所对应的一系列信息,它是由学号、姓名、性别和成绩四个数据项组成。

线性表的定义: n(n≥0)个数据元素的有限序列,记作:

    L = ($a_1$,$a_2$,…,$a_n$),$a_n$是表中数据元素,n是表长度(n = 0为空表),$a_1$称为线性表的第一个(首)结点,$a_n$称为线性表的最后一个(尾)结点。$a_1$,$a_2$…,$a_{i-1}$都是$a_i$的前驱,其中$a_{i-1}$是$a_i$的直接前驱;$a_{i+1}$,$a_{i+2}$,…,$a_n$都是$a_i$的后继,其中$a_{i+1}$是$a_i$的直接后继。

(重点)线性表的基本操作:

(1)InitList(&L)//Initiate:开始,着手

操作结果:构造一个空的线性表

(2)DestroyList(L)

初始条件:线性表L已经存在

操作结果:销毁线性表L

(3)ClearList(L)

线性表L存在,将其清空

(4)ListEmpty(L)

    L存在,若L为空表,返回True;否则返回False

(5)ListLength(L)

    L存在,返回L中数据元素个数

(6)GetElem(L,i,&e)

    L存在,用e返回L中第i个数据元素的值

(7)LocateElem(L,e,compare())

    L存在,compare()函数是数据元素判定函数,返回L中第1个与e满足compare()关系的数据元素的位置,若这样的数据元素不存在,则返回0

(8)PriorElem(L,cur_e,&pre_e)

    L存在,若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则返回false

(9)NextElem(L,cur_e,&next_e)

    L存在,若cur_e是L的数据元素,且不是最后一个,则用next_e返回他的后继,否则返回false

(10)ListInsert(&L,i,e)

    L存在,在L的第i个位置之前插入新的数据元素e,L的长度+1

(11)ListDelete(&L,i,&e)

    L存在,删除L的第i个数据元素,并用e返回其值,L的长度-1

看完这些函数是不是感觉有些懵,不要急,我会在下篇文章给出函数实现以及完整代码,接下来我要把线性表的一些性质讲完

线性表的顺序表示指的是用一组地址连续的存储单元以此存储线性表的数据元素,其特点是:逻辑上相邻的元素,物理位置上也是相邻的

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

在具体的及其环境下:设线性表的每个元素需要占用c个存储单元,则线性表中第i+1个数据元素的存储位置$LOC(a_{i+1})$和第i个数据元素的存储位置$LOC(a_{i})$之间满足关系:$LOC(a_{i+1}) = LOC(a_i) + c$,线性表的第i个数据元素$a_i$的存储位置为$LOC(a_{i+1}) = LOC(a_1) + (i-1)*c$

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Dancing Links算法

     Dancing Links算法主要用于解决精确覆盖问题,精确覆盖问题就的定义:给定一个由0-1组成的矩阵,是否能找到一个行的集合,使得每个集合中每一列恰好只包...

    mathor
  • 线性表(二)

    mathor
  • 子数组累加和为aim(小于等于aim)的三个问题

     这个和上面唯一的不同就是数组中只有正数,这里使用类似窗口移动的做法,给出两个指针,L,R表示窗口的左右边界 ,sum表示的是arr[L,R]之间的累加和,L,...

    mathor
  • css中的伪类与伪元素

    伪类的效果可以通过添加一个实际的类来达到,而伪元素的效果则需要通过添加一个实际的元素才能达到,这也是为什么他们一个称为伪类,一个称为伪元素的原因。 伪类的种类 ...

    前朝楚水
  • CSS中伪类与伪元素,你弄懂了吗?

    熟悉前端的人都会听过css的伪类与伪元素,然而大多数的人都会将这两者混淆。本文从解析伪类与伪元素的含义出发,区分这两者的区别,即使你有用过伪类与伪元素,但里面总...

    Javanx
  • 顺序表示的线性表——顺序表

    Zoctopus
  • 到底什么是数据结构?我认为是这样的

    最直观的就是数据库中的表:一张表就是一个数据对象,一条数据则是数据元素,数据项则是字段。

    小明爱学习
  • 【UI自动化-2】UI自动化元素定位专题

    UI自动化的学习,个人认为应该分五步走:环境搭建、元素定位、特殊场景处理、框架设计与搭建、测试平台开发。第一步的环境搭建其实没什么难度,都是固定的套路。今天就来...

    云深i不知处
  • 伪元素清除浮动(重要) 利用伪元素:after清除浮动

    让页面呈现多列布局时经常会使用 float:left/right ,可是浮动布局会导致父元素的高度为0(未设置高度的情况下),不会根据子元素的高度而变化,另外...

    IT人一直在路上
  • 数据结构 | 每日一练(49)

    1.已知线性表(a1 a2 a3 …an)按顺序存于内存,每个元素都是整数,试设计用最少时间把所有值为负

    闫小林

扫码关注云+社区

领取腾讯云代金券