[工学]算法与数据结构第二章.pptVIP

第二章 线性表 2.1 线性表的概念 线性表(Linear List): 具有相同类型的若干元素(数据项)的有限序列： L=(a1,a2,..an) 其中，除第一个元素外，每个元素的前驱唯一；除最后一个元素外，每个元素的后继唯一。 例1： A=(a,b,c,..z) T=(12,34,21,9,10,2,100) 如果线性表L中的元素不是基本的，则可称为记录。 例2：学生登记表 线性表L中当前元素的个数称为表长。长度为0的表为空表。 在程序设计中如果一个线性表的长度有限制，则称为数组；如果表的长度没有限制则称为文件。 线性表的基本操作： List createNullList(void) 操作结果：产生一个空表； void DestroyList(List L) 初始条件：线性表L已存在。 操作结果：撤消线性表L。 void ClearList(List *L) 初始条件：线性表L已存在。 操作结果：将线性表L设置为空。 int IsNull(List L) 初始条件：线性表L已存在。 操作结果：若线性表L为空，则返回TRUE，否则返回FALSE。 int ListLength(List L) 初始条件：线性表L已存在。 操作结果：返回线性表L的长度。 Elemtype GetElem(List L,int i) 初始条件：线性表L已存在,0=iListLength(L)。 操作结果：返回线性表L第i个元素的值。 int LocateElem(List L,ElemType e,int compare()) 初始条件：线性表L已存在,compare()是数据元素的比较函数 操作结果：返回线性表L中第1个与e比较为真的元素的位置， 如果没有，则返回NULL *Elemtype PrioElem(List L,ElemType cur_e) 初始条件：线性表L已存在 操作结果：cur_e是线性表L中元素，且不是第1个， PrioElem 返回cur_e的直接前驱元素的指针； 否则为NULL. *Elemtype NextElem(List *L, ElemType cur_e) 初始条件：线性表L已存在 操作结果：cur_e是线性表L中元素，且不是最后一个， NextElem next返回cur_e的直接后继元素的指针； 否则为NULL. void ListInsertPre(List *L,int i,ElemType e) 初始条件：线性表L已存在,0=i=ListLength(L) 操作结果：在线性表L第i个元素之前插入元素e,L长度增1。 void ListDeletet(List *L,int i,ElemType *e) 初始条件：线性表L已存在,1=i=ListLength(L) 操作结果：删除线性表L第i个元素，e返回其值， L长度减1。 例、线性表LA、LB表示集合A、B，求A=A∪B 解：设LA=(3,6,4,8) LB=(3,2,6,4,5,9) 则结果： LA=(3,6,4,8,2,5,9) 即：将LB中没有在LA中出现的元素依次添加到LA中。 void union(List *LA,List LB)//LA返回集合并的结果 { la=ListLength(*LA); lb=ListLength(LB); for(i=0;ilb;i++) { e=GetElem(LB,i); //将LB中第i个元素取出赋给e if (LocateElem(*LA,e,equal())==NULL) ListInsert(LA,la,e); } }// end of union 时间复杂性：O(length(LA)*length(LB)) 2.2 线性表的顺序组织 L=(a1,a2,..an)，使用一组地址连续的存储单元存储L。使得L中各元素的存储位置满足： LOC(ai)=LOC(a0)+i*c i=0,1,2,..(ListLength(L)-1) 这里c是数据元素占有的存储大小。 在高级语言中，通常用数组描述顺序存储。 ?#define MAXNUM 100 //线性表的最大长度 struct SeqList{ DataType element[MAXNUM]; //存放线性表的数组 int n;