2、抽象数据类型线性表 ●c| earlist(&"L 初始条件:线性表L已经存在。 操作结果:将L置为空表。 ● ListEmpty(L ●初始条件:线性表L已经存在。 操作结果:若L为空表,则返回TRUE,否则返回 FALSE。 北京邮电大学自动化学院
北京邮电大学自动化学院 6 ⚫ ClearList(&L) ⚫ 初始条件：线性表L已经存在。 ⚫ 操作结果：将L置为空表。 2、抽象数据类型线性表 ⚫ ListEmpty(L) ⚫ 初始条件：线性表L已经存在。 ⚫ 操作结果：若L为空表，则返回TRUE，否则返回 FALSE
抽象数据类型线性表 ListLength(l) 初始条件:线性表L已经存在。 操作结果:返回L中数据元素个数。 GetElem(L, i, &e) 初始条件:线性表L已经存在, <isListlength(L)。 操作结果:用e返回L中第i个数据元素的值。 o LocateElem (L, e, compare) 初始条件:线性表L已经存在, compare是数据元素判定函数。 操作结果:返回L中第一个与e满足关系 compare的数据元素的 位序。若这样的元素不存在,则返回值为零为 北京邮电大学自动化学院
北京邮电大学自动化学院 7 ⚫ ListLength(L) ⚫ 初始条件：线性表L已经存在。 ⚫ 操作结果：返回L中数据元素个数。 2、抽象数据类型线性表 ⚫ GetElem(L, i, &e) ⚫ 初始条件：线性表L已经存在，iListlength(L)。 ⚫ 操作结果：用e返回L中第i个数据元素的值。 ⚫ LocateElem(L, e, compare()) ⚫ 初始条件:线性表L已经存在,compare是数据元素判定函数。 ⚫ 操作结果：返回L中第一个与e满足关系compare()的数据元素的 位序。若这样的元素不存在，则返回值为零为
2、抽象数据类型线性表 ListInsert(&L, i, e) 初始条件:线性表L已经存在,且1i≤ Listlength(L+1。 操作结果:在L中第个位置之前插入新的数据元素e,L的长度加1 o Listdelte(&L,i, &e) ●初始条件:线性表L已经存在且非空,且1≤i≤ Listlength(L)。 ●操作结果:删除L中的第i个数据元素,并用e返回其值,L的长度 减1。 3 ADT List 北京邮电大学自动化学院
北京邮电大学自动化学院 8 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
3、例题 例21利用两个线性表LA和LB分别表示两个集合A和B,现要 求一个新的集合A=AUB。只要从线性表LB中依次取得每个数 据元素,并依值在线性表LA中进行査访,若不存在,则插入。 o void union (List &La, List Lb)i La-en= Listlength(La); Lb-en= Listlength(Lb);线性表长 for(i=1; i<=Lb-len; i++)i Getelem(Lb,i,e);/取Lb中的第个i元素赋给e if(! Locate Elem(La, e, equal))Listinsert(La, ++La-en, e) La中不存在和e相同的数据元素,则插入 1 3/union 北京邮电大学自动化学院
北京邮电大学自动化学院 9 ⚫ 例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、例题
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,15,20) ●从上面的问题要求可知,Lc中的数据元素或是LA中的数据元 素,或是LB中的数据元素,则只要先设LC为空表,然后将LA或 LB中的元素逐个插入到Lc中即可。设两个指针j分别指向LA 和LB中某个元素,设当前所指的元素为a,j当前所指的元素为 b,则当前应插入到Lc中的元素c为 1,当axb时 北京邮电大学自动化学院 10
北京邮电大学自动化学院 10 ⚫ 例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，15，20） = ，当 时 当 时 b a b a a b c , 3、例题 ⚫ 从上面的问题要求可知，LC中的数据元素或是LA中的数据元 素，或是LB中的数据元素，则只要先设LC为空表，然后将LA或 LB中的元素逐个插入到LC中即可。设两个指针i和 j分别指向LA 和LB中某个元素，设i当前所指的元素为a，j当前所指的元素为 b，则当前应插入到LC中的元素c为