资源描述：
《简化 sax第二章线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章线性表本章主要介绍下列内容线性表的类型定义线性表的顺序存储结构线性表的链式存储结构线性表的应用举例2.1线性表的类型定义1、线性表的定义线性表是由n（n≥0）个类型相同的数据元素组成的有限序列。通常表示成下列形式：L=(a1,a2,...,ai-1,ai,ai+1,...,an)其中：L为线性表名称，习惯用大写书写；ai为组成该线性表的数据元素，习惯用小写书写；线性表中数据元素的个数被称为线性表的长度当n=0时，线性表为空，又称为空线性表。表中相邻元素之间存在着前后次序关系．将ai-1称为ai的直接前驱，将ai＋1,称为ai的直接后继。线性表举例：La=(34,89,
2、765,12,90,-34,22)//数据元素类型为int。Ls=(H,W,C)//数据元素类型为字符型。Lb=(book1,book2,...,book100)//数据元素类型为下列所示的结构类型：structbookinfo{intNo;/*图书编号*/char*name;/*图书名称*/char*auther;/*作者名称*/...;};L=(a1,a2,...,ai-1,ai,ai+1,...,an)2、线性表的四个特点：1）存在唯一的一个被称作“第一个”的数据元素。2）存在唯一的一个被称作“最后一个”的数据元素。3）除第一个之外，集合中的每个数据元素均
3、只有一个前驱。4）除最后一个外，集合中的每个数据元素均只有一个后继。3、线性表的抽象数据类型定义ADTList{数据对象：D={ai
4、ai∈ElemSet,i=1,2,…，n,n≥0}数据关系：R={
5、ai-1,ai∈D,i=2,3,…,n}基本操作：InitList(&L);操作结果：构造一个空的线性表L。DestroyList(&L);初始条件：线性表L已存在。操作结果：销毁线性表L。ClearList(&L);初始条件：线性表L已存在。操作结果：将L重置为空表。ListEmpty(L);初始条件：线性表L已存在。操作结果：若L空表，则返回TRUE,否
6、则返回FALSEListLength(L);初始条件：线性表L已存在。操作结果：返回L中数据元素的个数。GetElem(L,i,&e);初始条件：线性表L已存在，1≤i≤ListLength(L)。操作结果：用e返回L中第i数据元素的值。LocateElem(L,e,equal);初始条件：线性表L已存在。操作结果：返回L中第1个与e相等数据元素的位序。若这样的数据元素不存在，则返回值为0。PriorElem(L,cur_e,&pre_e);初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无意
7、义。NextElem(L,cur_e,&next_e);初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是第一个，则用next_e返回他的后继，否则操作失败，next_e无意义。ListInsert(&L,i,e);初始条件：线性表L已存在，1≤i≤ListLength(L)+1。操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。ListDelete(&L,i,&e);初始条件：线性表L已存在且非空，1≤i≤ListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。}ADTList例2-1：归并两个线性表L
8、A和LB，使LA包含LA中的全部元素和LB的不包含在LA中的元素。归并运算说明：1)LB中与LA中相同的元素不归并到LA中；2)不另建新线性表，需要扩大表LA，将LB中需要并入的元素插入到LA中；3)LB中需要并入的元素作为LA的尾元素插入。伪码表示的算法：voidunion(List&La,ListLb){//将所有在线性表LB中但不在LA中的数据元素插入到LA中La_len=ListLength(La);Lb_len=ListLength(lb);//求线性表的长度for(i=1;i<=Lb_len;i++){ GetElem(Lb,i,&e);//取LB中的第
9、i个数据元素赋值给eif(!LocateElem(La,e,equal))ListInsert(La,++La_len,e);//LA中不存在和e相同的数据元素，则插入之。}//for}//union2.2线性表的顺序存储及操作实现2.2.1顺序存储线性表的顺序存储是把线性表的数据元素放在一组地址连续的存储单元中。（以元素在计算机内存储器内的物理位置来体现互为前驱和后继的逻辑关系，线性表中相邻的元素在内存储器内也相邻）假设每个元素占用l(小写L)个存储单元，线性表中第一个元素的存储地址LOC(a1)=b，那麽线性表
