线性表(一)

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

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

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

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

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

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

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

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

相关文章

来自专栏python学习路

数据结构与算法(二)

排序与搜索 排序算法(英语:Sorting algorithm)是一种能将一串数据依照特定顺序进行排列的一种算法。 排序算法的稳定性 稳定性:稳定排序算法会让原...

3418
来自专栏后端之路

双向队列之ArrayDeque

背景 前几篇主要介绍的都是java的普通集合,包括list,set,map等 本篇要介绍和ArrayList对应的ArrayDeque 上一篇和Deque相关的...

2968
来自专栏desperate633

HashSet实现原理分析(Java源码剖析)add(E e)remove(Object o)iterator()小结

本文将深入讨论HashSet实现原理的源码细节。在分析源码之前,首先我们需要对HashSet有一个基本的理解。

2093
来自专栏包子铺里聊IT

How to find the lowest common ancestor in a tree 最近公共祖先

[题目] 求二叉树的任意两个节点的最近公共祖先。 此题有多个扩展问题: 如果只查询一次,二叉树给出向上(parent)链接和不给向上链接时分别有什么解法,最佳空...

2624
来自专栏小灰灰

JDK容器学习之TreeMap (一) : 底层数据结构

TreeMap 在日常的工作中,相比较与HashMap而言,TreeMap的使用会少很多,即使在某些场景,需要使用到排序的Map时,也更多的是选择 Linke...

2309
来自专栏Android机动车

Java 基础(五)——集合源码解析 Set

前面我们学了 List 集合。我们知道 List 是一个有序的集合,可以根据元素的整数索引访问元素,并且允许重复。

921
来自专栏java学习

来测试一下你对数据结构中的栈和队列的了解有多少?

选择题 1.向一个栈顶指针为top的链栈中插入一个结点s,执行( )。 A.top.next=s; B.s.next=top.next ;top.next=s;...

6069
来自专栏Java技术栈

Java List面试题汇总

1、你知道的List都有哪些? 2、List和Vector有什么区别? 3、List是有序的吗? 4、ArrayList和LinkedList的区别?分别用在什...

3699
来自专栏androidBlog

HashMap及HashTable源码解析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

691
来自专栏编程理解

数据结构(二):二叉搜索树(Binary Search Tree)

二分法的查找过程是,在一个有序的序列中,每次都会选择有效范围中间位置的元素作判断,即每次判断后,都可以排除近一半的元素,直到查找到目标元素或返回不存在,所以

2561

扫码关注云+社区