下载掌阅APP，畅读海量书库
立即打开
本节将通过大家熟悉的问题引出线性结构的概念及线性结构要解决的问题。
线性结构是一种简单的数据。 线性结构，常见于日常生活中以及一些数学抽象中。下面来看一些常见问题，思考其所涉及的数据具有怎样的特征，可以采用什么样的数据存储方式，以及需要进行哪些数据处理。
问题1： 日常生活中常见学生的成绩单、通讯录、单位的职工工资表以及图书馆的图书书目等，这些表单具有一个共同的特点，就是由一行行结构相同的数据构成。对这些表单经常进行的操作是修改、查找、插入和删除。
问题2： 日常生活中，将洗好的盘子由下往上摆放起来，使用的时候再从上至下依次取出，如果用计算机模拟这一过程，盘子之间的逻辑关系是线性结构，处理盘子的取出顺序需要遵循“后摆放先取出”的原则。
问题3： 日常生活中排队购物、汽车进出站、到银行办理业务等事务处理过程，如果用计算机来模拟，一般需要遵循“先来先服务”的处理原则。
问题4： 程序设计语言对函数嵌套调用的实现，需要保存调用点的数据，并按照调用的顺序后调用先返回。调用的过程是线性的，返回的过程也是线性的，只是返回的过程与调用的过程正好相反。
问题5： 实现一元多项式的存储表示及加、减、乘等运算。由于一元多项式的每一项都是由系数和指数构成的，因此可将一元多项式抽象地表示为由系数和指数构成的序偶序列，各个序偶之间的逻辑关系是线性的。为便于运算，可以约定按照指数递增的顺序排列。
问题6： 计算机的存储单元是线性结构的，程序设计语言如何将多维数组存储到线性结构的存储空间中？
问题7： 文本编辑软件如何实现对文本的处理。该处理实际上是对一个大字符串进行建立、插入、删除、取字符串、字符串匹配，以及对字符串中的字符做标记等操作。而字符串的逻辑结构是以字符为元素的线性结构。
上述所有问题所涉及的数据元素的逻辑关系都属于线性结构，即元素之间至多有唯一前驱或唯一后继的数据关系，所不同的是，这种结构中数据元素的类型或需要进行的操作等方面有所区别，本章将详细介绍常用线性结构数据的存储表示以及常用操作的实现。
在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。线性表是具有 相同数据类型的 n（n≥0）个数据元素的有限序列，通常记为
其中， n为表长，n=0时称为空表 。
表中相邻元素之间存在着次序关系。a i-1 称为a i 的直接前驱，a i+1 称为a i 的直接后继。也就是说，对于a i ，当i=2，…，n时，有且仅有一个直接前驱a i-1 ；当i=1，2，…，n-1时，有且仅有一个直接后继a i+1 ；而a 1 是表中的第一个元素，它没有前驱，a n 是最后一个元素，它没有后继。
需要说明的是，a i 为序号为i的数据元素（i=1，2，…，n），通常将它的数据类型抽象为DataType，DataType的具体结构由具体问题而定。例如，在学生成绩表中，它是用户自定义的学生类型；在棋盘布局问题中，它是矩阵类型；在表示字符串时，它是字符型；等等。为了方便数据处理，假设DataType中总包含整型字段key。
在第1章中提到过，数 据的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在存储结构上的 ，因此下面定义线性表的基本运算作为逻辑结构的一部分，每一个运算的具体实现只有在确定了线性表的存储结构之后才能完成。
线性表的基本运算主要有以下几种。
1） 线性表的初始化： Init_List（L）。运算结果是构造一个空的线性表。
2） 求线性表的长度： Length_List（L）。运算结果是返回线性表中所含元素的个数。
3） 取表元： GetList（L，i）。若表L存在且1≤i≤Length_List（L），运算结果是返回线性表L中的第i个元素的值或地址。
4） 按值查找： Locate_List（L，x），x是给定的一个数据元素。若线性表L存在，运算结果是在表L中查找值为x的数据元素。若结果返回为L中首次出现的值为x的那个元素的序号或地址，称为查找成功；否则，在L中未找到值为x的数据元素，返回一特殊值表示查找失败。
5） 插入： InsertList（L，i，x）。若线性表L存在，插入位置1≤i≤n+1（n为插入前的表长），运算结果是在线性表L的第i个位置上插入一个值为x的新元素，这样使原序号为i，i+1，…，n的数据元素的序号变为i+1，i+2，…，n+1，插入后，新表长=原表长+1。
6） 删除： DeleteList（L，i）。若线性表L存在，删除位置1≤i≤n（n为删除前的表长），运算结果是在线性表L中删除序号为i的数据元素，删除后原序号为i+1，i+2，…，n的元素的序号变为i，i+1，…，n-1，新表长=原表长-1。
说明：
1） 某数据结构上的基本运算，不是它的全部运算，而是一些基础运算，而每一个基本运算在实现时也可能根据不同的存储结构派生出一系列相关的运算 。例如，线性表的删除运算还会有删除某个特定值的元素；插入运算也可能是将新元素x插入到适当位置上。不可能也没有必要定义出它的全部运算，读者掌握了某一数据结构上的基本运算后，其他的运算可以通过基本运算来实现，也可以直接实现。
2）在上面各运算中定义的线性表L仅仅是一个抽象在逻辑结构层次的线性表，尚未涉及它的存储结构，因此，每个运算在逻辑结构层次上尚不能用具体的某种程序设计语言写出具体的算法，而 算法只有在存储结构确立之后才能实现 。
在Java语言中可以用接口（Interface）的形式定义线性表的ADT中的公有方法。
