第2章 线性表
第2章 线性表
• 2.1 线性表的基本概念 • 2.2 线性表的顺序存储 • 2.3 线性表的链式存储结构 • 2.4 一元多项式的表示及相加
1
第2章 线性表
2.1 线性表的类型定义 从本章开始到第四章讨论的线性表、栈、队列
和串的逻辑结构都属于线性结构。在线性结构中， 元素之间存在一个对一个的相互关系，其逻辑特征 为：在数据元素的非空有限集中：
{elemtype vec[List_INIT]；
int lenght； }sequenlist ；
13
第2章 线性表
在上面描述中，顺序表是一个结构体类型。其 中，vec成员（又称为数据域）指线性表数据元素所 占用的存储空间，而lenght成员（又称为长度域） 则用于存储线性表长度，它表示线性表最后一个元 素在向量中的位置，elemtype 则为线性表中数据元 素类型。
基本操作：
以下是一些常用操作，以函数方式出现
ห้องสมุดไป่ตู้
…… } ADT list
7
第2章 线性表
2.1.2 线性表的运算
常见的线性表的基本运算： （1）置空表ClearList(L)：将线性表L置成空表。 （2）求长度ListLenght(L)：求给定线性表L中数 据元素的个数。 （3）取元素GetElem(L,i,&e)：用e返回线性表L中 的第i个数据元素。 （4）插入ListInsert(&L,i, e)：在线性表L中第i个 位置之前插入新的元素e,L的长度加1。
8
第2章 线性表
（5）删除ListDelete (&L,i,&e)：删除L中第i个元素， 并用e返回其值，L的长度减1。 （6）判定ListEmpty(L)：若L为空表，则返回true, 否则返回false。
利用基本运算可以实现线性表的其它复杂运算。 需要指出的是，这里给出的只是定义在逻辑结构上 的抽象运算，即只关心这些运算是“做什么”的，至 于“怎样实现”则依赖于所选定的存储结构。
（1）存在唯一的一个被称为“起始”的数据元 素。
（2）存在唯一的一个被称为“终端”的元素。
2
第2章 线性表
（3）除起始元素外，其它每个元素有且仅有一个 直接前趋。
（4）除终端元素之外，其它每个元素有且仅有一 个直接后继。
本章的基本内容：线性表的逻辑结构定义和各 种存储结构、描述方法及其建立在这两种存储结构 上的运算实现。
线性表中第 i 个数据元素 a i 的存储位置计算公
式为：
LOC (ai ) LOC (a1 ) (i 1) l
L 是每个元素占用的存储单元
10
第2章 线性表
这样，一旦起始地址LOC（a1）（图2.2中设为b） 和一个数据元素占用的存储单元的大小（L值）确定 下来，就可求出任一个数据元素的存储地址，显然， 这种表便于进行随机访问，因此，顺序表是一种随机 存取的结构。
置； (5)线性表的长度可以根据需要增长或缩短。
6
第2章 线性表
抽象数据类型线性表的定义格式
ADT list {
ElemSet 是某个确定的、将由用户自行定 义的、含某个关系运算的数据对象
数据对象： D {ai | ai ElemSet , i 1,2,...,n,n 0 }
数据关系： R1 { ai1,ai | ai1,ai D,i 1,2,...,n }
9
第2章 线性表
2.2 线性表的顺序表示和实现
顺序表是线性表的顺序存储结构，即按顺序存储 方式构成的线性表的存储结构。其存储方式是：线性 表的第一个元素存放在个一片连续的存储空间开始位 置处，第二个元素紧跟着存放在第一元素之后…，以 此类推。
利用顺序表来存储线性表，可借助数据元素在计 算机内的物理位置相邻特性来表示线性表中数据元素 之间的线性逻辑关系。
14
第2章 线性表
2.2.2 顺序表上的基本运算
本节讨论在定义线性表顺序存储结构之后， 如何在这种结构上实现有关数据运算。下面重点 讨论线性表的顺序表的建立、数据元素的插入和 删除运算。
15
第2章 线性表
3. 顺序表的常用算法
算法1 顺序表的建立 (P23 算法2.3)
输入n个整数，产生一个存储这些整数的顺序表A的函数如下：
11
第2章 线性表
12
第2章 线性表
在具体实现时，可利用高级程序设计语言中的
一维数组即向量来为线性表的顺序存储开辟存储空
间，存储空间大小应大于等于线性表长度，用一个
整型变量来表示线性表的长度，从而可将顺序表描
述为：
# define List_INIT 100 typedef int elemtype ； /* elemtype表示元素类型， 此处设为 int */ typedef struct
typedef int vector [ m ] 定义了一个新的类型，顺序表中n小于或等于m
main() { vector B;
int j,n; cin>>n; create(B,n); for (j=1;j<=n;j++)
线性表的结点之间的逻辑关系符合线性结构 的逻辑特征，是一种线性结构。
5
第2章 线性表
线性表的特点： (1)同一线性表中的元素必定具有相同特性； (2) 相邻数据元素之间存在着序偶关系； (3) 线性表中元素个数n(n>=0)为线性表的长度,当n=0
时称为空表； (4)在非空线性表中，每个数据元素都有一个确定的位
最后一个数据元素，又称为终端结点。
4
第2章 线性表
当i=1，2，…，n-1时，ai 有且仅有一个直接
后继 ai1 ；当i =2，3，…n 时， ai 有且仅有
一个直接前趋 ai1 。注意这里 ai （1≤ i≤ n）
仅仅是一个抽象的符号，其具体含义，在不同的情 况下各不相同，它可以是一个数，一条记录或一个 符号，甚至是更复杂的信息。例如，英文字母表(A， B，……Z)是一个线性表，职工工资表等。
3
第2章 线性表
2.1.1 线性表的逻辑结构
在实际应用中，线性表是最常用而且最简单的一种数据 结构。
线性表定义：线性表是由n个数据元素组成的有限序列， 其中，n即数据元素的个数，定义为线性表的长度，当n为 零时称为空表，一般将n>0时的线性表记为：
(a1, a2 , ai , , an )
a 其中，a1是第一个数据元素，又称为起始结点， n 是