数据结构的操作之线性表

easthomeRT

程序里经常需要将一组（某类型的）元素作为整体管理和使用

该组数据里元素个数可能变化（可以加入或删除元素）

有可能需要把这样一组元素看成一个序列，元素在序列里的位置和 顺序可能表示实际应用中某种有意义的信息或关系

这样一组元素（的序列）的抽象就是线性表（简称表）。线性表是 一种元素集合，其中还记录着元素间的一种顺序关系

线性表是最基本的一种数据结构

在程序里应用很广泛

还常作为更复杂的数据结构的实现基础

例如整数的表，字符串的表，某种复杂结构的表等

Python 的 list 和 tuple 支持这类需要，可看作是线性表的实现

概念：

抽象讨论线性表时，考虑一个基本元素集合 E = {e0，…，eN-1}，其中 的元素可能是某个类型的成员

表是元素的有穷序列，有 0 个或多个元素 (e0，e1, …，en-1)，n≥0

元素的位置称为其下标，下标从 0 开始编号（也可选择从 1 开始）

表中元素的个数称为表的长度，长度为 0 的表是空表

元素间基本关系是下一个关系：<e0, e1>,<e1,e2 >,…,<en-2, en-1>，  这是一种顺序关系（线性关系）

线性表是一种线性结构。在一个非空线性表里：

存在唯一的 “首元素”，唯一的“尾元素”（末元素）

除首元素外，表中每个元素都有且只有一个前驱元素

除尾元素外，表中每个元素都有且只有一个后继元素

可以把线性表作为数学对象建立抽象模型。

从实际角度看，线性表是一种组织数据元素的结构。作为一种抽象的数 据结构，需要从两个角度考虑

从实现者角度需要考虑两个问题：1，如何把该结构内部的数据组 织好（为它设计一种合适的表示）；2，如何提供一套有用而且必 要的操作，并有效实现这些操作。显然两者相关

从使用者角度，需考虑该结构提供了哪些操作，如何有效使用以解 决自己的问题。实际使用会对表的实现者提出一些要求

两种角度既有统一又有分工。情况与函数的定义与使用类似

数据结构的表示完全是内部的东西，外面看不到。但它会对这一数 据结构上各种操作的实现和性质产生重要影响

对复杂的数据结构，由于存在多种可能表示（后面会看到），设计 时需要考虑的因素很多，利弊得失的权衡可能困难而复杂

东方瑞通成立于1998年，总部在北京，分别在上海、广州、天津、武汉、济南、深圳、成都、重庆、杭州和西安建立了直营分部，全国拥有超过40间专业培训教室、40多位专职讲师及180多位签约讲师；作为国内企业级IT高级技术&管理培训的领军机构，为数千家企业客户提供员工外派（公开课）和团体定制培训服务，累计培训专业人才数十万名。