文档介绍：第2章 线性表
线性表的基本概念
线性表的顺序存储
线性表的链式存储
线性表的应用
本章小结
有序表
1
精选ppt
线性表的基本概念
线性表的定义
线性表的运算
2
精选ppt
线性表的定义
线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度,用n表示,n≥0。
当n=0时,表示线性表是一个空表,即表中不包含任何元素。设序列中第i(i表示位序)个元素为ai(1≤i≤n)。
线性表的一般表示为:
(a1,a2,…ai,ai+1,…,an)
3
精选ppt
其中a1为第一个元素,又称做表头元素,a2为第二个元素,an为最后一个元素,又称做表尾元素。
例如,在线性表
(1,4,3,2,8,10)
中,1为表头元素,10为表尾元素。
4
精选ppt
线性表的运算
线性表的基本运算如下:
(1) 初始化线性表InitList(&L):构造一个空的线性表L。
(2) 销毁线性表DestroyList(&L):释放线性表L占用的内存空间。
5
精选ppt
(3) 判线性表是否为空表ListEmpty(L):若L为空表,则返回真,否则返回假。
(4) 求线性表的长度ListLength(L):返回L中元素个数。
(5) 输出线性表DispList(L):当线性表L不为空时,顺序显示L中各结点的值域。
(6) 求线性表L中指定位置的某个数据元素GetElem(L,i,&e):用e返回L中第 i(1≤i≤ListLength(L))个元素的值。
6
精选ppt
(7) 定位查找LocateElem(L,e):返回L中第1个值域与e相等的位序。若这样的元素不存在,则返回值为0。
(8) 插入数据元素ListInsert(&L,i,e):在L的第i(1≤i≤ListLength(L)+1)个元素之前插入新的元素e,L的长度增1。
(9) 删除数据元素ListDelete(&L,i,&e):删除L的第i(1≤i≤ListLength(L))个元素,并用e返回其值,L的长度减1。
7
精选ppt
假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示,即线性表中的数据元素即为集合中的成员。编写一个算法求一个新的集合C=A∪B,即将两个集合的并集放在线性表LC中。
解:本算法思想是:先初始化线性表LC,将LA的所有元素复制到LC中,然后扫描线性表LB,若LB的当前元素不在线性表LA中,则将其插入到LC中。算法如下:
8
精选ppt
void unionList(List LA,List LB,List &LC)
{
int lena,lenc,i;
ElemType e;
InitList(LC);
for (i=1;i<=ListLength(LA);i++)
/*将LA的所有元素插入到Lc中*/
{ GetElem(LA,i,e);
ListInsert(LC,i,e);
}
lena=ListLength(LA); /*求线性表的长度*/
lenB=ListLength(LB);
9
精选ppt
for (i=1;i<=lenb;i++)
{
GetElem(LB,i,e);
/*取LB中第i个数据元素赋给e*/
if (!LocateElem(LA,e))
ListInsert(LC,++lenc,e);
/*LA中不存在和e相同者,则插入到LC中*/
}
}
10
精选ppt