线性表(一)

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

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

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

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

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

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

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

图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 条评论
登录 后参与评论

相关文章

来自专栏liulun

Nim教程【七】

这是国内第一个关于Nim的系列教程 先说废话 很开心,在今天凌晨快一点多的时候拿到了 nim-lang.com;nim-lang.cn;nim-lang.net...

1875
来自专栏人工智能LeadAI

Python中对字节流/二进制流的操作:struct模块简易使用教程

前言 前段时间使用Python解析IDX文件格式的MNIST数据集,需要对二进制文件进行读取操作,其中我使用的是struct模块。查了网上挺多教程都写的挺好的,...

3965
来自专栏程序员与猫

常见的正则表达式解读释义

又名:写给正在学习前端的女友看的常见正则表达式解读。原文发布于 https://www.zybuluo.com/wddpct/note/728081 。 ...

1769
来自专栏机器学习算法与Python学习

python基础-数据类型与变量

转载于:廖雪峰的官方网站-python教程 数据类型 计算机顾名思义就是可以做数学计算的机器,因此,计算机程序理所当然地可以处理各种数值。但是,计算机能处理的远...

3377
来自专栏吴伟祥

(待整理完)正则表达式30分钟入门教程

Regular Expression(regex、regexp或RE):记录文本规则的代码

813
来自专栏浪淘沙

Python学习总结3--Python基础

    a = 100 if a >= 0:     print(a) else:     print(-a) 其中,#为注...

501
来自专栏Python爬虫与数据挖掘

Python正则表达式初识(六)

续分享Python正则表达式基础,今天给大家分享的正则表达式特殊符号是“[]”。中括号十分实用,其有特殊含义,其代表的意思是中括号中的字符只要满足其中任意一个就...

653
来自专栏PHP技术

php面试题(二)

1 <?php echo count (false); $a = count ("567") + count(null) + count(false); ec...

3228
来自专栏Android机器圈

数据结构----线性表顺序和链式结构的使用(c)

PS:在学习数据结构之前,我相信很多博友也都学习过一些语言,比如说java,c语言,c++,web等,我们之前用的一些方法大都是封装好的,就java而言,里面使...

573
来自专栏mukekeheart的iOS之旅

Java基础学习(学习IT企业必读的324个JAVA面试题.pdf 整理)

一、Java程序基础 javac 文件名.java    编译程序    java 类名               运行java程序 代码规范中,一下几点要注...

2099

扫码关注云+社区