线性表的定义及其运算

一、线性表的定义

线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列,通常记为:

(a1, a2,···,ai-1,ai,ai+1,···,an)。其中,n为数据元素个数,称为表长。当n=0时,称为空表。

表中相邻元素之间存在顺序关系:

将ai-1称为ai的直接前驱,ai+1称为ai的直接后继。
也就是说,对于ai
当i=2,···,n时,有且仅有一个直接前驱ai-1
当i=1,2,···,n-1时,有且仅有一个直接后继ai+1
a1是表中第一个数据元素,它没有前驱;
an是表中最后一个数据元素,它没有后继。

线性表的逻辑结构可表示为:

LinearList = (D, R)
其中,
D = {ai | 1≤i≤n, n≥0, ai∈DataType}
R = {r}
r={<ai, ai+1> | 1≤i≤n-1}
其中,DataType 为数据元素类型。

二、线性表的运算

数据结构的运算是在逻辑结构基础上定义的,而运算的具体实现是建立在存储结构上的,因此下面定义的线性表的基本运算作为逻辑结构的一部分,每一个操作的具体实现只有在确定线性表的存储结构之后才能完成。

线性表上的基本运算如下。

  1. 线性表初始化:void Initiate()

    初始条件:线性表不存在。

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

  2. 求线性表的长度:int Length()

    初始条件:线性表已存在。

    操作结果:返回线性表所含数据元素的个数。

  3. 取表元:DataType Get(int i)

    初始条件:表存在且1≤i≤Length()。

    操作结果:返回线性表的第 i 个数据元素的值。

  4. 按值查找:int Locate(DataType x)

    初始条件:线性表已存在,x 是给定的一个数据元素。

    操作结果:在线性表中查找值为 x 的数据元素,返回首次出现的值为 x 的那个数据元素的序号,称为查找成功;如果未找到值为 x 的数据元素,返回 0 表示查找失败。

  5. 插入操作:int Insert(DataType x, int i)

初始条件:线性表已存在。

操作结果:在线性表的第 i 个位置上插入一个值为 x 的新元素,使原序号为 i ,i+1,…,n 的数据元素的序号变为 i+1,i+2,…,n+1,插入后表长 = 原表长 +1,返回 1 表示插入成功;若线性表 L 中数据元素个数少于 i-1 个,则返回 0 表示插入失败。

  1. 删除操作:int Deleted(int i)

    初始条件:线性表已存在。

    操作结果:在线性表L中删除序号为i的数据元素,删除后使序号为i+1,i+2,…,n的元素变为序号i,i+1,…,n-1,新表长=原表长-1,返回1;若线性表中数据元素个数少于i,则返回0表示删除失败。

运算说明如下:

  1. 某数据结构上的基本运算不是它的全部运算,而是一些常用的基本运算。每一个基本运算在实现时也可能根据不同的存储结构派生出一系列相关的运算。例如,线性表的查找在链式存储结构中还会按序号查找;再如插入运算,也可能是将新元素 x 插入适当位置上等,不可能也没有必要全部定义出它的运算集。读者掌握某一数据结构上的基本运算后,其他运算可以通过基本运算来实现,也可以直接去实现。

  2. 在上面各操作中定义的线性表仅是一个抽象在逻辑结构层次的线性表,尚未涉及它的存储结构。因此,每个操作在逻辑结构层次上尚不能用具体的某种程序设计语言写出具体的算法,而算法的实现只有在存储结构确立之后。

三、线性表的抽象数据类型描述

上述这些运算可用抽象数据类型描述为:

ADT LinearList is

Data:
 	一个线性表L定义为
 	L=(a~1~, a~2~,···,a~i-1~,a~i~,a~i+1~,···,a~n~),
 	当 L=()时定义为一个空表。

Operation:
		void Initiate()    //线性表初始化
		int Length()     //求线性表的长度
		DataType Get(int i)   //取表元
		int Locate(DataType x)   //按值查找
		int Insert(DataType x,int i) //插入操作
		int Deleted(int i)    //删除操作
		END LinearList
用户头像
登录后发表评论