数据结构之线性表详细解答.docVIP

二章 线性表 线性表是最简单、最基本、也是最常用的一种线性结构。它有两种存储方法：顺序存储和链式存储，它的主要基本操作是插入、删除和检索等。 2.1 线性表的逻辑结构 2.1.1 线性表的定义 线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。在实际问题中线性表的例子是很多的，如学生情况信息表是一个线性表：表中数据元素的类型为学生类型; 一个字符串也是一个线性表：表中数据元素的类型为字符型，等等。 综上所述，线性表定义如下： 线性表是具有相同数据类型的n(n=0)个数据元素的有限序列，通常记为： (a1，a2，… ai-1，ai，ai+1，…an) 其中n为表长， n＝0 时称为空表。 表中相邻元素之间存在着顺序关系。将 ai-1 称为 ai 的直接前趋，ai+1 称为 ai 的直接后继。就是说：对于ai，当 i=2，...，n 时，有且仅有一个直接前趋 ai-1.，当i=1，2，...，n-1 时，有且仅有一个直接后继 ai+1，而 a1 是表中第一个元素，它没有前趋，an 是最后一个元素无后继。 需要说明的是：ai为序号为 i 的数据元素（i=1,2,…,n），通常我们将它的数据类型抽象为datatype，datatype根据具体问题而定，如在学生情况信息表中，它是用户自定义的学生类型; 在字符串中，它是字符型; 等等。 2.1.2 线性表的基本操作 在第一章中提到，数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在存储结构上的，因此下面定义的线性表的基本运算作为逻辑结构的一部分，每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。 线性表上的基本操作有： ⑴ 线性表初始化：Init_List(L) 初始条件：表L不存在 操作结果：构造一个空的线性表 ⑵ 求线性表的长度：Length_List(L) 初始条件：表L存在 操作结果：返回线性表中的所含元素的个数 ⑶ 取表元：Get_List(L,i) 初始条件：表L存在且1=i=Length_List(L) 操作结果：返回线性表L中的第ｉ个元素的值或地址 ⑷ 按值查找：Locate_List(L,x)，ｘ是给定的一个数据元素。 初始条件：线性表L存在 操作结果：在表L中查找值为ｘ的数据元素，其结果返回在L中首次出现的值为ｘ的那个元素的序号或地址，称为查找成功; 否则，在L中未找到值为ｘ的数据元素，返回一特殊值表示查找失败。 ⑸ 插入操作：Insert_List(L,i,x) 初始条件：线性表L存在，插入位置正确 (1=i=n+1,ｎ为插入前的表长)。 操作结果：在线性表L的第 i 个位置上插入一个值为 x 的新元素，这样使原序号为 i , i+1, ... , n 的数据元素的序号变为 i+1,i+2, ... , n+1，插入后表长=原表长+1。 ⑹ 删除操作：Delete_List(L,i) 初始条件：线性表L存在，1=i=n。 操作结果：在线性表L中删除序号为i的数据元素，删除后使序号为 i+1, i+2,..., n 的元素变为序号为 i, i+1,...,n-1，新表长＝原表长－１。 需要说明的是： 1. 某数据结构上的基本运算，不是它的全部运算，而是一些常用的基本的运算，而每一个基本运算在实现时也可能根据不同的存储结构派生出一系列相关的运算来。比如线性表的查找在链式存储结构中还会有按序号查找; 再如插入运算，也可能是将新元素ｘ插入到适当位置上等等，不可能也没有必要全部定义出它的运算集，读者掌握了某一数据结构上的基本运算后，其它的运算可以通过基本运算来实现，也可以直接去实现。 2. 在上面各操作中定义的线性表Ｌ仅仅是一个抽象在逻辑结构层次的线性表，尚未涉及到它的存储结构，因此每个操作在逻辑结构层次上尚不能用具体的某种程序语言写出具体的算法，而算法的实现只有在存储结构确立之后。 2.2 线性表的顺序存储及运算实现 2.2.1 顺序表 线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。因为内存中的地址空间是线性的，因此，用物理上的相邻实现数据元素之间的逻辑相邻关系是既简单，又自然的。如图 2.1 所示。设 a１的存储地址为Loc(a１)，每个数据元素占d个存储地址，则第i个数据元素的地址为： Loc(ai)=Loc(a１)+(i-1)*d 1=i=n 这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i个数据元素