文档介绍：线性结构的特点:在数据元素中的非空有限集中
(1)存在唯一的一个被称作“第一”的数据元素;
(2)存在唯一的一个被称作“最后一个”的数据元素;
(3)除第一个外,集合中的每一个数据元素均只有一个前驱;
(4)除最后一个外,集合中的每一个数据元素均只有一个后继。
第二章线性表
1、线性表
线性表(Linear List) :一个线性表是n个数据元素的有限序列。例如:
例1、26个英文字母组成的字母表
(A,B,C、…、Z)
例2、某校从1999年到2003年各种型号的计算机拥有量的变化情况。
(6,17,28,50,92,188)
线性表的类型定义
在稍复杂的线性表中,一个数据元素可以由若干个数据项组成。在这种情况下,常把数据元素称为记录,含有大量记录的线性表又称为文件。
例3、学生健康情况登记表如下:
姓名
学号
性别
年龄
健康情况
王小林
790631
男
18
健康
陈红
790632
女
20
一般
刘建平
790633
男
21
健康
张立立
790634
男
17
神经衰弱
……..
……..
…….
…….
…….
1、线性表
综合上述三个例子可见,线性表中的数据元素可以是各种各样的,但同一线性表中的元素必定具有相同特征,即属同一数据对象,相邻数据元素之间存在着序偶关系。若将线性表记为:
(a1,…,a i-1,ai,a i+1…,an)
则表中ai-1领先于ai,ai领先于a i+1 ,称ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素。
当i=1,2,…,n-1时,ai有且仅有一个直接后继,当i=2,3,…,n时, ai有且仅有一个直接前驱。
线性表中的元素的个数n(n 0)定义为线性表的长度,n=0时称为空表。
1、线性表
ADT List{
数据对象:={ai|aiElemSet,i=1,2,…,n,n0}
数据关系:R1={<ai-1,ai>| ai-1,ai, D,i=2,…,n}
基本操作:
InitList(&L)
操作结果:构造一个空的线性表L。
2、抽象数据类型线性表
DestroyList(&L)
初始条件:线性表L已经存在。
操作结果:销毁线性表L。
ClearList(&L)
初始条件:线性表L已经存在。
操作结果:将L置为空表。
2、抽象数据类型线性表
ListEmpty(L)
初始条件:线性表L已经存在。
操作结果:若L为空表,则返回TRUE,否则返回FALSE。
ListLength(L)
初始条件:线性表L已经存在。
操作结果:返回L中数据元素个数。
2、抽象数据类型线性表
GetElem(L, i, &e)
初始条件:线性表L已经存在,iListlength(L)。
操作结果:用e返回L中第i个数据元素的值。
LocateElem(L, e, compare())
初始条件:pare是数据元素判定函数。
操作结果:pare()的数据元素的位序。若这样的元素不存在,则返回值为零为。
2、抽象数据类型线性表
ListInsert(&L ,i ,e)
初始条件:线性表L已经存在,且1 i Listlength(L)+1。
操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1
Listdelte(&L ,i ,&e)
初始条件:线性表L已经存在且非空,且1 i Listlength(L)。
操作结果:删除L中的第i个数据元素,并用e返回其值,L的长度减1。
……
} ADT List
例2-1 利用两个线性表LA和LB分别表示两个集合A和B,现要求一个新的集合A=A∪B。只要从线性表LB中依次取得每个数据元素,并依值在线性表LA中进行查访,若不存在,则插入。
void union(List &La,List Lb) {
La-len=Listlength(La); Lb-len=Listlength(Lb);//线性表长
for (i=1; i<=Lb-len; i++) {
GetElem(Lb,i,e);//取Lb 中的第个i元素赋给e
if(!LocateElem(La, e, equal)) Listinsert(La, ++La-en, e);
//La中不存在和e相同的数据元素,则插入
} }//union
3、例题
例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列,现要求将LA和LB归并为一个新的线性表LC,且LC中的元素仍按值非递减有序排列。
例 LA=(3,5,8,11), LB=(2,6,8,9,11,15,20)
则 LC=(2,3,5,6,8,8,9,11,11,1