线性表、栈、队列、串和数组都属于线性结构。

2.1 线性表的定义和特点

定义:由n个数据特性相同的元素构成的有限序列称为线性表。(n=0为空表)

如:26个英文字母的字母表;学生基本信息表。

非空的线性表或者线性结构特点:

(1) 存在唯一的一个被称作“第一个”的数据元素,表头元素;

(2) 存在唯一的一个被称作“最后一个”的数据元素。表位元素;

(3) 除第一个之外,结构中的每个数据元素均只有一个前驱;

(4) 除最后一个外,结构中的每个数据元素均只有一个后继。

2.2 案例引入

案例2.1: 一元多项式的运算

案例2.2: 稀疏多项式的运算

案例2.3: 图书信息管理系统

2.3 线性表的类型定义

线性表的抽象数据类型定义:

ADT List{

数据对象:D={ai|ai属于Elemset,i=1,2,…,n,n>=0}

数据关系:R={<ai-1,ai>|ai-1,ai属于D,i=2,…,n}

基本操作:

InitList(&L)

操作结果:构造一个空的线性表L。

DestroyList(&L)

初始条件:线性表L已经存在。

操作结果:销毁线性表L。

Clearlist(L)

初始条件:线性表L已经存在。

操作结果:将L置于空表。

ListEmpty(L)

初始条件:线性表L已经存在。

操作结果:将L置于空表。

ListLengh(L)

初始条件:线性表L已经存在。

操作结果:返回L中数据元素个数。

GetElem(L,I,&e)

初始条件:线性表L已经存在,且1=<i=<ListLengh(L)

操作结果:用e返回L中第i个数据元素的值。

LocateElem(L,e)

初始条件:线性表L已经存在。

操作结果:返回L中第i个数据元素的值与e相同的元素的位置。若这样的数不存在,则返回值为0。

PriorElem(L,cur_e,&pre_e)

初始条件:线性表L已经存在。

操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回其前驱,否则操作失败,pre_e无定义。

NextElem(L,cur_e,&next_e)

初始条件:线性表L已经存在。

操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回其前驱,否则操作失败,next_e无定义。

ListInsert(&L,i,e)

初始条件:线性表L已经存在,且1=<i=<ListLengh(L)+1

操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1。

ListDelete(&L,i)

初始条件:线性表L已经存在且非空,且1=<i=<ListLengh(L)

操作结果:删除L中第i个数据元素,L的长度减1。

TraveseList(L)

初始条件:线性表L已经存在且非空。

操作结果:对线性表L进行遍历,在遍历过程中对L每个结点访问一次。