数据结构--线性表

简介
线性表是数据结构中最简单、最重要的结构形式之一，是最经常遇到的一种操作对象，在程序设计语言和程序设计中广泛使用。本章将系统地讨论其存储、运算及应用。


线性结构是最简单且最常用的数据结构。线性表是一种典型的线性结构。

线性表的概念

1． 线性表的定义
线性表（linear list）是具有相同类型的n（n≥0）个数据元素a0，a1，…an-1组成的有限序列。其中n 称为线性表的长度，当n=0时称为空线性表，n>0时称为非空表。


二、说明
1、一个线性表可以一个标识符来命名，如：
A=(a0,a1,a2,...,an-1)

2、线性表中的数据元素要求具有相同类型，它的数据类型可以根据具体情况而定，我们将它的类型设定为elemtype，表示某一种具体的已知数据类型。它可以是一个数、一个字符或一个字符串，也可以由若干个数据项组成。

3、特征
从线性表的定义可以看出线性表的特征：
（1）有且仅有一个开始结点(表头结点)a0，它没有直接前驱，只有一个直接后继;
（2）有且仅有一个终端结点(表尾结点)an-1，它没有直接后继，只有一个直接前驱;
（3）其它结点都有一个直接前驱和直接后继；
（4）元素之间为一对一的线性关系。
4、线性表中数据元素的相对位置是确定的，如果把一个线性表中的数据元素的位置做改动，那么变动后的线性表与原来的线性表是两个不同的线性表。

a1,a2,...ai-1, ai ,ai+1,...,an

线性表是一种典型的线性结构，对应的逻辑结构图如图2-1所示。

例1：某小从1996到2002年的计算机拥有量可表示为线性表：
（123，234，333，444，456，567，677）

例2：26个英文字母 (A,B,C……,Z)

例3：某中学的成绩表

学号	姓名	数据结构	英语	操作系统	离散
010701	张明	78	86	65	98
010702	李可	43	76	67	87
......	......	......	......	......	......
010731	王特	65	76	76	98

线性表的逻辑结构特征

对于非空的线性表:
　① 有且仅有一个开始结点a₁，没有直接前趋，有且仅有一个直接后继a₂；
　 ② 有且仅有一个终结结点a_n，没有直接后继，有且仅有一个直接前趋a_n-1；
　③ 其余的内部结点a_i（2≤i≤n-1）都有且仅有一个直接前趋a_i-1和一个a_i+1。