2线性表(福建教师招考信息技术算法和程序部分)

1、第二章 线形表1、线性表(Linear List) ：定义：由n(n0)个数据据元素(结点)a1，a2， an组成的有有限序列列。记作作：L=(a1，a2，ai-1，ai，ai+1，an)其中数据据元素的的个数n定义为为表的长长度。当当n=0时称为为空表，常常将将非空的的线性表表(n0)这这里的的数据元元素ai(1in)只是一一个抽象象的符号号，其具具体含义义在不同同的情况况下可以以不同。例1、26个英英文字母母组成的的字母表表（A，B，C、Z）例2、某某校从1978年到1983年各种种型号的的计算机机拥有量量的变化化情况。（6，17，28，50，92，188）例3、学学生健康康情况登登记表如

2、如下：例4、一一副扑克克的点数数（2，3，4，J，Q，K，A）姓 名学 号性 别年龄 健康情况王小林790631 男 18 健康陈 红790632 女 20 一般刘建平790633 男 21 健康张立立790634 男 17 神经衰弱 . . .线性表元素及元元素之间间的关系系为线性性线性：（1）有且仅仅有一个个开始节节点（该该节点只只有一个个后继节节点，没没有前趋趋节点）（2）有且仅仅有一个个结束节节点（该该节点只只有一个个前趋节节点，没没有后继继节点）（3）除首节节点，其其余节点点有且仅仅有一个个前趋k1k2k3k4k1k2k3（4）除尾节节点，其其余节点点有且仅仅有一个个后继数据的运运算

3、是定定义在逻逻辑结构构上的，而运算算的具体体实现则则是在存存储结构构上进行行的。线性表的的类型定定义抽象数据据类型线线性表的的定义ADTList数据对象象：D ai |aiElemSet, i=1,2,.,n,n0数据关系系：R1|ai-1 ,aiD,i=2,.,n基本操作作： 初始始化InitList(&L )操作结果果：构造造一个空空的线性性表L。 结构构销毁DestroyList(&L )初始条件件：线性性表L已已存在。操作结果果：销毁毁线性表表L。 引用用型操作作 ListEmpty( L)初始条件件：线性性表L已已存在。操作结果果：若L为空表表，则返返回TRUE，否则FALSE。Li

4、stLength(L )初始条件件：线性性表L已已存在。操作结果果：返回回L中元元素个数数。ADTListGetElem(L,i,&e )初始条件件：线性性表L已已存在，1iLengthList(L)操作结果果：用e返回L中第i个元素素的值。LocateElem(L,e,compare() )初始条件件：线性性表L已已存在，compare()是是元素判判定函数数。操作结果果：返回回L中第1个与e满足关系compare()的元素素的位序序。若这这样的元元素不存存在，则则返回值值为0。PriorElem( L, cur_e,&pre_e)初始条件件：线性性表L已已存在。操作结果果：若cur_e是L

5、的元素素，但不不是第一一个，则则用pre_e 返回回它的前前驱，否否则操作作失败，pre_e无无定义。NextElem(L,cur_e,&next_e)初始条件件：线性性表L已已存在。操作结果果：若cur_e是L的元素素，但不不是最后后一个，则用next_e返返回它的的后继，否否则操作作失败，next_e无定义义。ListTraverse(L,visit( )初始条件件：线性性表L已已存在。操作结果果：依次对L的每每个元素素调用函函数visit()。一一旦visit()失败，则操作作失败。ADTList 加工工型操作作 ClearList(&L )初始条件件：线性性表L已已存在。操作结果果：将

6、L重置为为空表。PutElem(L,i,&e )初始条件件：线性性表L已已存在，1iLengthList(L)操作结果果：L中中第i个个元素赋赋值同e的值。ListInsert(&L,i,e )初始条件件：线性性表L已已存在，1iLengthList(L)+1操作结果果：在L的第i个元素素之前插插入新的的元素e，L的的长度增增1。ListDelete(&L,i,&e)初始条件件：线性性表L已已存在且且非空，1iLengthList(L)操作结果果：删除除L的第第i个元元素，并并用e返返回其其值，L的长度度减1。 ADTList举例假设线性性表L=(23,56,89,76,18),i=3,x=5

7、6,y=88,则对对L的一一组操作作及结果果如下：ListLength(L )/所得得结果为为5GetElem(L,i,&e)/所得得结果为为89PriorElem( L,x, &pre_e)/所得得结果为为23NextElem(L,x, &next_e)/所得得结果为为89LocateElem(L,x,equal)/所得得结果为为2ListInsert(&L,i,y) /所得结结果为(23,56,88,89,76,18)ListDelete(&L,i+1, &e)/所得结结果为(23,56,88,76,18)89如何实现现线性表表的其它它操作例2-1 利用用两个线线性表LA和LB分别别表示两

8、两个集合合A和B，现要要求一个个新的集集合A=AB。设计思想想：扩大线性性表LA，将存存在于线线性表LB中而而不存在在于线性性表LA中的数数据元素素插入到到线性表表LA中中去。分下列三三步进行行：1从线线性表LB中依依次取得得每个数数据元素素;2依值值在线性性表LA中进行行查访;3若不不存在，则插入入之。A=AB算法描述述：/将将所有在在线性表表Lb中中但不在在La中中的数据据元素插插入到La中void Union(List &La，List Lb)/求求线性表表的长度度La-len=ListLength(La);Lb-len=ListLength(Lb);for( i=1;i=Lb-len;

9、 i+)/取取Lb中中第i个个数据元元素赋给给eGetElem(Lb，i，e);/La中中不存在在和e 相同同的数据据元素，则插入入之if(!LocateElem( La，e，equal)ListInsert(La，+La-en，e); /UnionA=AB时间复杂杂度分析析：GetElem取遍Lb表元元素需Lb_len=ListLength(Lb)次；循环体内内的Locate操作作平均需需ListLength(La)次次最坏情况况为：ListLength(La)总的时间间复杂度度：OListLength(Lb)* ListLength(La)例 2-1-2已知一个个非纯集集合B，试构构造集合

10、合A，要要求集合合A中只只包含集集合B中中所有值值不相同同的数据据元素。设计思想想：解法一：同上例，分别以以线性表表LA和和LB表表示集合合A和B，则首首先初始始化线线性表LA为空空表，之之后的操操作和例例2-1完全相相同。解法二：仍以线性性表表示示集合。只是求求解之前前先对线线性表LB中的的数据据元素进进行排序序，即线线性表LB中的的数据元元素依其其值从小小到大大有序排排列，则则值相同同的数据据元素必必相邻。则上述述操作作中的第第二步就就不需要要进行从从头至尾尾的查询询。A =Bvoid purge(List&La,List Lb) /已已知线性性表Lb中的数数据元素素依值非非递减有有序排列

11、列，现构构造线性性表La，/使使La中中只包含含Lb中中所有值值不相同同的数据据元素InitList（La）；/初初始化La为空空表La_len=ListLength(La);Lb_len=ListLength(Lb);/求求线性表表的长度度for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);/取取Lb中第i个数据据元素赋赋给eif( ListEmpty( La )|!equal(en，e)ListInsert(La,+La_len,e);/La中不不存在和和 e相相同的的数据元元素，则则插入入之en= e;/en，La中的已已插入元元素 / for / purgeA =B

12、时间复杂杂度分析析：GetElem取遍Lb表元元素需Lb_len=ListLength(Lb)次；解法一:循环体内内的Locate操作作平均需需ListLength(Lb)次次故时间复复杂度为为：O(ListLength2(LB)；解法二的的时间复复杂度：循环体内内的基本本操作与与表长无无关故时间复复杂度为为：O(ListLength(Lb)C =AB例2-2巳巳知线性性表LA和线性性表LB中的数数据元素素按值非非递减有有序排列列，现要要求将LA和LB归并并为一个个新的线线性表LC，且且LC中中的元素素仍按值值非递减减有序排排列。设计思想想：1、LC为空表表，用来来存放LA和LB的元元素2、表

13、LA和LB的元元素逐一一进行比比较取小小者放入入表LC中3、插入入表LA或表LB中剩剩余的元元素算法描述述：/已已知线性性表La和Lb中的元元素按值值非递减减排列列。/归归并La和Lb得到新新的线性性表Lc，Lc的元元素也按按值非递递减排列列。void MergeList(List La,List Lb,List &Lc) InitList(Lc);i =j= 1;k =0;La_len=ListLength(La);Lb_len=ListLength(Lb);while(i=La_len)&(j=Lb_len)/La和Lb均非非空GetElem(La,i,ai);GetElem(Lb,j,b

14、j);if(ai=bj)ListInsert(Lc,+k,ai);+i;elseListInsert(Lc,+k,bj);+j;C =ABwhile(i=La_len)GetElem(La,i+, ai);ListInsert(Lc,+k, ai);while(j=Lb_len)GetElem(Lb,j+, bj);ListInsert(Lc,+k, bj); / MergeListC =AB时间复杂杂度分析析：该算法中中包含了了三个WHILE语句句，其中中，第一一个处理理了某一一张表的的全部元元素和另另一张表表的部分分元素；后两个个WHILE循循环只可可能有一一个执行行，用来来完成将将未归并

15、并到LC中的的余下部部分元素素插入到到LC中中。“插入”是估量量归并算算法时间间复杂度度的基本本操作，其语句句频度为为：LENGTH（LA）+LENGTH（LB）该算法的的时间复复杂度为为：O（LENGTH（LA）+LENGTH（LB）若LA和LB的元素个个数为同同数量级级n，则该该算法的的时间间复杂度度为:O(n)线性表的的顺序表表示和实实现一、线性性表的顺顺序存储储结构顺序表：线性表的的顺序存存储结构构把线性表表的结点点按逻辑辑顺序（顺序）依依次存放放在一组组地址连续的存储单单元里。1、线性性表的地地址计算算：假设线性性表的每每个元素素需占用用l个存储单单元，并并以所占占的第一一个单元元的

16、存储储地址作作为数据据元素的的存储位位置（首首地址）。则线线性表中中第i+1个数据元元素的存存储位置置LOC( ai+1)和第i个数据元素素的存储储位置LOC(ai)之间满足足下列关关系：LOC(ai+1) =LOC(ai) +l线性表的的第i个个数据元元素ai的存储储位置为为：LOC(ai) =LOC(a1) +(i-1)*l存储示意意：线性表的的顺序存存储用数组实实现线性性表（顺顺序存储储、顺序序表）线性表元元素：a1、a2、a3、a4.数组元素素：a0、a1、a2、a3线性关系系：a1a2a3a4数组下标标大小注意：C语言中的的数组下下标从“0”开始，因因此，若若L是Sqlist类型的顺

17、顺序表，则表中中第i个元素是是l.datai-1。ElemType*getElem(intpos);/若若1=pos=cursize,则则返回指指示第pos个个元素/的位位置;否否则返回回NULLintLocation(ElemType&e);/返返回其值值和e所所指元素素值相同同的数据据元素在在线性/表中中的序号号，若不不存在这这样的数数据元素素，则返返回0/modificationvoidclearList(void);StatusputElem(intpos,constElemType&e);/若若1=pos=cursize,则则修改线线性表中中第pos个数数/据元元素的值值，并且且返回

18、OK;否否则不不进行修修改并返返/回ERRORStatusInsert (intpos,constElemType&e);/若若1=pos=cursize+1, 则插插入元素素e在线线性表/中第第pos个数据据元素之之前，并并且返返回OK;否否则不/进行行插入并并返回ERRORStatus*Delete(intpos, ElemType&e);/若若1=posMAXLISTSIZE)?MAXLISTSIZE:size;elemPtr =newElemTypesize;cursize =0;插入示意意：插入运算算插入运算算问题描述述以a1开开始的线线性表中中在第i个个元素前前插入一一个新元元素n

19、ew_node。a1a2ai-1aiana1a2ai-1newnodeai+1aianai+1插入运算算从ai开开始向后后移动从an开开始向前前每个元元素向后后移一格格a1a2ai-1aiai+1.anaiaiaiaia1a2ai-1aiai+1ananai+1aifor( j=i;j i;j-)L.elem j+1 =L.elem j;newnode算法思想想： 进行行合法性性检查，1=i=n+1； 利用用线性表表是否已已满； 将第第n个至至第i个个元素逐逐一后移移一个单单元； 在第第i个位位置处插插入新元元素； 将表表的长度度加1。StatusListInsert_Sq(Sqlist&L，

20、int i， ElemTypee) /在在顺序序线性表表L中第第 i个个位置置之前插插入新的的元素e/i的的合法法值为1 iListLength_Sq(L)+ 1if(i L.length+1)returnERROR; / i值值不合法法if(L.length=L.ListSize)exit(overflow);for(i=L.length-1;i=I-1;i-)L.elemi+1=L.elemi;L.elemI-1=x;l.length+;删除示意意：anai删除运算算删除运算算问题描述述：删除除第i个个元素算法实现现分析a1a2aianai1a1a2ai1ai+1ananai+1删除运算算

21、算法实现现分析从an开开始向前前逐个元元素向前前移动从ai1开始向后后逐个元元素向前前移动a1a2ai+1aianai-1anananfor( i=L.length-1;i i;i-)L.elem i-1 =L.elem i;a1a2ai-1aiai+1anfor( i=i;i L.length-1;i+)L.elem i=L.elem i+1;算法思想想： 进行行合法性性检查，i是否否满足1=i=n； 判线线性表是是否已空空，v.last=0； 将第第i+1至第n个元素素逐一向向前移一一个位置置； 将表表的长度度减1。StatusListDelete_Sq(SqList&L,inti,Ele

22、mType&e)/ListDelete_Sqfor(+p;p = q; +p)*(p-1)= *p;/被删除元元素之后后的元素素左移-L.length;/表长减1returnOK;算法时间间复杂度度为:O(ListLength(L)p =&(L.elemi-1);/p为被删除除元素的的位置e =*p;/被删除元元素的值值赋给eq =L.elem+L.length-1;/表尾元素素的位置置if(i L.length)returnERROR;/删除位置置不合法法元素左移移考虑移动动元素的的平均情情况: 假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值

23、为：若假定在在线性表表中任何何一个位位置上进进行删除除的概率都是相等的，则移动元素素的期望望值为：p21 18 30 75 42 56 8721 18 30 75L.length-10ppq8756p =&(L.elemi-1);q =L.elem+L.length-1;for(+p;p = q; +p)*(p-1)= *p;例如：ListDelete_Sq(L, 5, e)pintLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)/在顺序表表中查询询第一个个满足判判定条件件的数据据元素，/若存在，则返回回它的

24、位位序，否否则返回回 0/LocateElem_SqO(ListLength(L) )算法的时间复杂杂度为：i =1;/i 的初初值为第第 1元元素的的位序p =L.elem;/p 的初初值为第第 1元元素的的存储位位置while(i=L.length&!(*compare)(*p+, e)+i;if(i=L.length)returni;elsereturn0;(*compare)(*p+, e)利用顺序序表类实实现线性性表的其其它操作作例如：顺顺序表23 75 41 38 54 62 17L.elemL.length = 7L.listsizee =38pppppi12341850p可见，

25、基基本操作作是，将顺序表表中的元元素逐个和给给定值e相比较。集合归并并：#include#includeSqList.hSqListmerge(Sqlist&a,SqList&b)ElemType*ai,*bj;intm =a.Length( );intn =b.Length( );SqListc(m+n);inti =1;intj =1;intk =c.Length( );while(i=m)&(j=n)ai= a.getElem(i);bj= b.getElem(j);switch(compare(*ai,*bj) case1:case0:c.Insert(+k, ai);i+;break

26、;case1:c.Insert(+k, bj);j+;break;default:;/switch/while利用顺序序表类实实现线性性表的其其它操作作while(i=m)ai= a.getElem(i+);c.Insert(+k, ai);while(j next=next;next =p;Node*Node:deleteAfter(void)/删删除并返返回后继继结点Node*s =next;next =s next;returns;L线性表的的操作GetElem(L, i, &e)在单链表表中的实实现:211830754256pppj123因此，查查找第i个个数据元元素的基基本操作作为：

27、移动指针针，比较较 j和和i单链表是是一种顺顺序存取取的结构构，为找找第i 个数数据元素素，必须须先找到到第i-1个个数据据元素。令指针p始终指向线性表中中第j个数据元元素StatusGetElem_L(LinkListL,inti,ElemType&e)/L是带头结结点的链链表的头头指针，以e 返回回第i 个元元素/GetElem_L算法时间复杂杂度为:O(ListLength(L)p =L-next;j =1;/p指向第第一个结结点，j为计数数器while(p&jnext;+j;/顺指针向向后查找找，直到到 p指指向第第 i个个元素素/或 p为为空if(!p | ji)returnERRO

28、R;/第 i个个元素素不存在在e =p-data;/取得第i个个元素returnOK;ai-1线性表的的操作ListInsert(&L,i,e)在单链表表中的实实现：有序对改变为 和 eaiai-1因此，在在单链表表中第i个个结点之之前进行行插入的的基本操操作为:找到线性性表中第第i-1个结点点，然后后修改其其指向后后继的指指针。可见，在在链表中中插入结结点只需需要修改改指针。但同时时，若要要在第i个个结点之之前插入入元素，修改的的是第i-1 个结结点的指指针。StatusListInsert_L(LinkListL,inti,ElemTypee)/L为带头结结点的单单链表的的头指针针，本算算

29、法/在链表中中第i个个结点点之前插插入新的的元素e/LinstInsert_L算法的时间复杂杂度为:O(ListLength(L)p =L;j= 0;while(p&j next;+j;/寻找第i-1 个结结点if(!p|j i-1)returnERROR;/i 大于于表长或或者小于于1s =newLNode;/生生成新结结点s-data =e;s-next =p-next;p-next =s;/插插入returnOK; eai-1aiai-1sp线性表的操作ListDelete (&L,i,&e)在链表中中的实现现:有序对 和改变为ai-1aiai+1ai-1在单链表表中删除第i 个结结点的

30、基本操作作为:找到线性性表中第第i-1个结点点，修改改其指向向后继的的指针。ai-1aiai+1ai-1q =p-next;p-next =q-next;e =q-data;free(q);pqStatusListDelete_L(LinkListL,inti,ElemType&e)/删除以L为为头指针针(带头头结点)的单链链表中第第 i个个结点点/ListDelete_L算法的时间复杂杂度为:O(ListLength(L)p =L;j= 0;while(p-next&j next;+j;/寻寻找第i个个结点，并令p指指向其前前趋if(!(p-next)|j i-1)returnERROR;/

31、删删除位置置不合理理q =p-next;p-next =q-next;/删删除并释释放结点点e =q-data;free(q);returnOK;操作ClearList(&L)在链表中中的实现现:voidClearList(&L)/将单链表表重新置置为一个个空表while(L-next)p=L-next;L-next=p-next;/ClearListfree(p);算法时间复杂杂度：O(ListLength(L)如何从线线性表得得到单链链表？链表是一一个动态态的结构构，它不不需要予予分配空空间，因因此生成链表表的过程程是一个结结点“逐个插入入” 的过过程。例如：逆位序输输入n 个数数据元素素

32、的值，建立带头头结点的的单链表表。操作步骤骤：1、建立立一个“空表”；2、输入入数据元元素an，建立结点点并插入入；3、输入入数据元元素an-1，建立结点点并插入入；ananan-14、依次次类推，直至输输入a1为止。如何从线线性表得得到单链链表？链表是一一个动态态的结构构，它不不需要予予分配空空间，因因此生成链表表的过程程是一个结结点“逐个插入入” 的过过程。voidCreateList_L(LinkList&L,intn)/逆序输入入 n个个数据据元素，建立带带头结点点的单链链表/CreateList_L算法的时间复杂杂度为:O(Listlength(L)L =(LinkList)mall

33、oc(sizeof(LNode);L-next =NULL;/先建立一一个带头头结点的的单链表表for(i= n; i0;-i)p =(LinkList)malloc(sizeof(LNode);scanf(&p-data);/输入元素素值p-next =L-next;L-next= p;/插入回顾2.1节中三个个例子的的算法，看一下下当线性性表分别别以顺序序存储结结构和链链表存储储结构实实现时，它们的的时间复复杂度为为多少？voidunion(List&La,ListLb)La_len=ListLength(La);Lb_len=ListLength(Lb);for(i= 1;i = Lb_

34、len;i+)GetElem(Lb, i, e);if(!LocateElem(La, e, equal()ListInsert(La, +La_len,e);/for/union控制结构构：基本操作作：for循循环GetElem,LocateElem和ListInsert当以顺序映像像实现抽象象数据类类型线性性表时为为:O(ListLength(La)ListLength(Lb) 当以链式映像像实现抽象象数据类类型线性性表时为为:O(ListLength(La)ListLength(Lb)例2-1算法时间间复杂度度 voidpurge(List&La,ListLb)InitList(LA);

35、La_len=ListLength(La);Lb_len=ListLength(Lb);for(i= 1;i = Lb_len;i+)GetElem(Lb, i, e);if(ListEmpty(La)|!equal(en,e)ListInsert(La, +La_len,e);en =e;/for/purge控制结构构：基本操作作：for循环GetElem和ListInsert当以顺序映像像实现抽象象数据类类型线性性表时为为:O(ListLength(Lb)当以链式映像像实现抽象象数据类类型线性性表时为为:O(ListLength2(Lb) )例2-2算法时间间复杂度度voidMergeLi

36、st(ListLa,ListLb,List&Lc)InitList(Lc);i =j= 1;k=0;La_len=ListLength(La);Lb_len= ListLength(Lb);while(i=La_len)&(j=Lb_len)GetElem(La, i, ai);GetElem(Lb, j, bj);if(ainext =L.current-next;L.current-next=s;if(L.tail =L.current)L.tail =s;L.current=s;returnOK;StatusDelAfter(LinkList&L,ElemType&e )/若当前指指针及

37、其其后继在在链表中中，则删删除线性性链表L中当前前/指针所指指结点之之后的结结点，并并返回OK;否则返回回ERROR。/DelAfterif(!(L.current&L.current-next)returnERROR;q =L.current-next;L.current-next=q-next;if(L.tail =q)L.tail= L.current;e=q-data;FreeNode(q);returnOK;例一StatusListInsert_L(LinkListL,int i, ElemType e)/在带头结结点的单单链线性性表L 的第第 i个个元素素之前插插入元素素 e/Li

38、stInsert_L利用上述述定义的的线性链链表如何何完成线线性表表的其它它操作？if(!LocatePos(L, i-1)returnERROR;/i值不合法法，第i-1 个结结点不存存在if(InsAfter(L, e)returnOK;/完成插入elsereturnERROR;StatusMergeList_L(LinkList&Lc,LinkList&La,LinkList&Lb，int(*compare)(ElemType,ElemType)/归并有序序表La和Lb,生成新新的有序序表Lc,/并在归并并之后销销毁La和Lb,/compare为指定的的元素大大小判定定函数/MergeL

39、ist_L例二if(!InitList(Lc)returnERROR;/存储空间间分配失失败while(!( a=MAXC&b=MAXC)/La或Lb非空LocatePos(La,0);LocatePos(Lb, 0);/当前指针针指向头头结点if(DelAfter(La, e)a =e;/取得La表表中第一一个元素素 aelsea =MAXC;/MAXC为常量最最大值if(DelFirst(Lb, e)b =e;/取得Lb表表中第一一个元素素 belseb =MAXC;/a和b为两表中中当前比比较元素素DestroyList(La);DestroyList(Lb);/销毁链表表La和Lbre

40、turnOK;if(*compare)(a,b)next =p-next;p-next= s;s-next-prior= s;s-prior =p;psai-1ai插入ai-1删除aiai+1p-next =p-next-next;p-next-prior= p;pai-1ADTOrdered_List数据对象象:S =xi|xiOrderedSet，i=1,2,n, n0 集合中任意两个个元素之间间均可以进行比较较数据关系系:R = |xi-1, xi S,xi-1xi, i=2,3,n回顾例2-2的两个算算法六、有序序表类型型基本操作作：LocateElem(L,e,&q,int(*com

41、pare)(ElemType,ElemType)初始条件件：有序表表L已存在。操作结果果：若有序序表L中存在元元素e，则q指示L中第一个值值为e的元素的位置，并返回回函数值值TRUE；否则q指示第一个大大于e的元素的的前驱的位置，并返回回函数值值FALSE。Compare是一个有有序判定定函数(12,23, 34,45,56, 67,78,89, 98,45)例如:若e =45,则q指向若 e=88,则 q指指向表示值为为 88 的元元素应插插入在该该指针所所指结点点之后。voidunion(List&La,ListLb)/Lb为为线性表表InitList(La);/构造(空空的)线线性表LA

42、La_len=ListLength(La);Lb_len=ListLength(Lb);for(i= 1;i = Lb_len;i+)GetElem(Lb,i,e);/取Lb中中第i 个数数据元素素赋给eif(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不不存在和和 e相相同的的数据元元素，则则插入之之/union算法时间间复杂度度：O(n2)voidpurge(List&La,ListLb)/Lb为有有序表InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);/求线性表表

43、的长度度for(i= 1;i = Lb_len;i+) /purgeGetElem(Lb,i,e);/取Lb中中第i个个数据元元素赋给给 eif(ListEmpty(La)|!equal(en,e)ListInsert(La,+La_len,e);en= e;/La中不不存在和和 e相相同的的数据元元素，则则插入之之算法时间间复杂度度：O(n)2.4一一元多多项式的的表示在计算机机中，可可以用一一个线性性表来表表示:P =(p0, p1, ，pn)但是对于于形如S(x) =1+ 3x10000 2x20000的多项式式，上述述表示方方法是否否合适？一元多项项式一般情况况下的一元稀疏疏多项式式可写成Pn(x)=p1xe1+ p2xe2+ pmxem其中：pi是指数为为ei的项的非非零系数数，0e1 e2 em= n可以下列列线性表表表示：（p1, e1）,(p2, e2), (pm,em) ）P999(x)=7x3- 2x12- 8x999例如:可用线性性表( (7,3),(-2,12), (-8,999)表示ADTPolynomial数据对象象：数据关系系：抽象数据据类型一一元多项项式的定定义如下下：Dai| aiTermSet,