数据结构——线性表知识总结_线性表知识梳理总结

 一、线性表的定义

是零个或多个具有相同类型的数据元素的有限序列。数据元素的个数定义为线性表的长度 。长度等于零时称为空表。一个非空表通常记为L ＝ ( a 1 ， a 2 ，……， a n ) 。

二、线性表的性质

每个数据元素的类型相同，每个元素之间存在唯一的顺序关系，如在英文字母表字母B的前面是字母A， 而字母B的后面是字母C。

三、线性表的抽象数据类型定义

ADT List

Data：

线性表中的数据元素具有相同类型，相邻元素具有前驱和后继关系 。

Operation：

InitList：

前置条件：线性表不存在

功能：线性表的初始化

后置条件：一个空的线性表

无输入输出

DestroyList： 

前置条件：线性表已存在

功能：销毁线性表

后置条件：释放线性表所占用的存储空间

无输入输出

Length ：

前置条件：线性表已存在

功能：求线性表的长度

后置条件：线性表不变

无输入，输出为线性表中数据元素的个数

Get ：

前置条件：线性表已存在

功能：在线性表中取序号为 i 的数据元素

后置条件：线性表不变

输入为元素的序号 i，如果序号合法，返回序号为 i 的元素值，否则抛出异常

Locate ：

前置条件：线性表已存在

输入：数据元素 x

功能：在线性表中查找值等于 x 的元素

输出：如果查找成功，返回元素 x 在表中的序号，否则返回 0

后置条件：线性表不变

Insert ：

前置条件：线性表已存在

输入：插入位置 i ；待插元素 x

功能：在线性表的第 i 个位置处插入一个新元素 x

输出：若插入不成功，抛出异常

后置条件：若插入成功，表中增加了一个新元素

Delete： 

前置条件：线性表已存在

输入：删除位置 i

功能：删除线性表中的第 i 个元素

输出：若删除成功，返回被删元素，否则抛出异常

后置条件：若删除成功，表中减少了一个元素

Empty ：

前置条件：线性表已存在

输入：无

功能：判断线性表是否为空表

输出：若是空表，返回 1 ，否则返回 0

后置条件：线性表不变

PrintList：

前置条件：线性表已存在

输入：无

功能：按位置的先后次序依次输出线性表中的元素

输出࿱