1、第 2章 线性表本章内容2.1 线性表的基本概念 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 顺序表与链表的比较 2.5 线性表的应用举例（约瑟夫环问题） 小 结习题 22.1 线性表的基本概念2.1.1 线性表的定义1线性表的定义线性表是具有相同数据类型的 n（ n0）个数据元素的有限序列，通常记为：(a1,a2, a i-1,ai,ai+1,a n)其中， n为表长，当 n=0时称为空表。 在线性表中相邻元素之间存在着顺序关系。如对于元素 ai 而言， ai-1 称为 ai 的直接前驱， ai+1称为 ai 的直接后继。 2.1 线性表的基本概念2线性表举例（ 1）简单的线
2、性表。例如， 26个英文字母表： (a,b,c,d,e,f,g,x,y,z )又例如一周七天：(1,2,3,4,5,6,7)（ 2）复杂的线性表。例如，在第 1章概述中引用的一个学生信息登记表，如表 1-1所示。学生信息登记表可以是用户自定义的学生类型。在复杂的线性表中，常把数据元素称为记录（Record），它由若干个数据项（ Item）组成，而含有大量记录的线性表又称为文件（ File）。2.1 线性表的基本概念3线性表的特点（ 1）有且仅有一个开始结点（ a1），它没有直接前驱；（ 2）有且仅有一个终端结点（ an），它没有直接后继；（ 3）除了开始结点和终端结点以外，其余的结点都有且仅有
3、一个直接前驱和一个直接后继。 2.1 线性表的基本概念4线性表的二元组表示线性表如果用二元组进行描述如下：Linearity=(D,R)数据对象： D= ai |1in,n0数据关系： | ai-1,ai D,1in 关系中 是一个序偶的集合，它表示线性表中数据元素的相邻关系，即 ai-1领先于 ai。2.1 线性表的基本概念2.1.2 线性表的基本操作线性表的基本操作如下。（ 1）初始化线性表 InitList(L)。（ 2）求线性表的长度 GetLength(L)。（ 3）按位置查找操作 GetElem(L, i, x)。（ 4）按值查找操作 Locate(L,x)。（ 5）插入操作 In
4、sElem(L,i,x)。（ 6）删除操作 DelElem(L,i,x)。（ 7）显示操作 DispList(L)。2.2 线性表的顺序存储 2.2.1 顺序表1顺序表的定义数据结构在内存中的表示通常有两种形式，即顺序存储表示和链式存储表示。线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的数据元素，我们把用这种存储形式存储的线性表称为顺序表。线性表的顺序存储表示又称为顺序表。顺序表的逻辑顺序和物理顺序是一致的。2.2 线性表的顺序存储假设顺序表 (a1,a2,ai-1,ai,ai+1,an)，每个数据元素占用 d个存储单元，则元素 ai的存储位置为：Loc(ai)= Loc(a1)+(i-1)d 1in其中， Loc(a1)是顺序表第一个元素 a1的存储位置，通称为顺序表的起始地址。顺序存储结构示意图如图 2-1所示。2.2 线性表的顺序存储 图 2-1 顺序存储结构示意图 存 储 地址 内存内容Loc(a1) a1Loc(a1)+d a2 Loc(a1)+(i-1)d ai Loc(a1)+(n 1)d an
