线性结构是最简单而应用最广泛的一种数据结构，在不同的场合会采取不同的存储结构和实现方法。本模块将介绍一种简单的线性结构——线性表，就是同类型的元素排成的一个线性序列，并且介绍了线性表的两种实现方法，即顺序表和链表。如何来实现顺序表和链表？什么时候应该用顺序表，什么时候链表更好？这一模块可以让你学会使用线性表及其相关的一些操作，解决一些简单问题，并考察分析时间空间上的效率，例如约瑟夫问题。重点：线性结构的逻辑定义，线性表的各种分类，顺序表、链表的定义和相关操作。难点：注意顺序表、链表的各种时间空间效率讨论，包括插入删除检索等在各种概率分布情况下的讨论。链表要特别注意表头结点的作用，链表指针的正确操作。

　基本概念和术语

 

　　1、数据(Data)

　　数据是外部世界信息的载体，它能够被计算机识别、存储和加工处理，是计算机程序加工的原料。计算机程序处理各种各样的数据，可以是数值数据，如整数、实数或复数；也可以是非数值数据，如字符、文字、图形、图像、声音等。

 

 

　　2、数据元素(Data Element)和数(DataItem)　　数据元素是数据的基本单位，在计算机程序中通常被作为一个整体进行考虑和处理。数据元素有时也被称为元素、结点、顶点、记录等。一个数据元素可由若干个数据项(Data Item)组成。数据项是不可分割的、含有独立意义的最小数据单位，数据项有时也称为字段(Field)或域(Domain)。例如，在数据库信息处理系统中，数据表中的一条记录就是一个数据元素。这条记录中的学生学号、姓名、性别、籍贯、出生年月、成绩等字段就是数据项。数据项分为两种，一种叫做初等项，如学生的性别、籍贯等，在处理时不能再进行分割；另一种叫做组合项，如学生的成绩，它可以再分为数学、物理、化学等更小的项。                                                           　　　　　　     

 

　　3、数据对象(Data Object)数据对象是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是{0,±1,±2,±3,…}，字符数据对象是{a,b,c,…}。

 

　　4、数据类型(Data Type)

　　数据类型是高级程序设计语言中的概念，是数据的取值范围和对数据进行操作的总和。数据类型规定了程序中对象的特性。程序中的每个变量、常量或表达式的结果都应该属于某种确定的数据类型。例如，C#语言中的字符串类型（String，经常写为string）。一个String表示一个恒定不变的字符序列集合，所有的字符序列集合构成String的取值范围。我们可以对String进行求长度、复制、连接两个字符串等操作。

数据类型可分为两类：一类是非结构的原子类型，如C#语言中的基本类型（整型、实型、字符型等）；另一类是结构类型，它的成分可以由多个结构类型组成，并可以分解。结构类型的成分可以是非结构的，也可以是结构的。例如，C#语言中数组的成分可以是整型等基本类型，也可以是数组等结构类型。

 

　　5、数据结构(Data Structure)

　　数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素之间都不是孤立的，而是存在着一定的关系，这种关系称为结构(Structure)。根据数据元素之间关系的不同特性，通常有4类基本数据结构：

(1) 集合(Set)：如图1.1(a)所示，该结构中的数据元素除了存在“同属于一个集合”的关系外，不存在任何其它关系。

(2) 线性结构(Linear Structure)：如图1.1(b)所示，该结构中的数据元素存在着一对一的关系。

(3) 树形结构(Tree Structure)：如图1.1(c)所示，该结构中的数据元素存在着一对多的关系。

(4) 图状结构(Graphic Structure)：如图1.1(d)所示，该结构中的数据元素存在着多对多的关系。