数据结构-02线性表

1、第第2 2章章 线性表线性表教学要求：教学要求：理解线性表的概念掌握线性表的抽象数据类型和应具有的基本操作掌握线性表的顺序存储结构的实现方法掌握线性表的链表存储结构的实现方法掌握线性表的简单应用重点：重点：线性表的抽象数据类型线性表的顺序存储结构线性表的链式存储结构线性表的简单应用难点：难点：线性表算法的设计与实现线性表算法的设计与实现线性结构的线性结构的基本特征基本特征为为: :1集合中必存在唯一的集合中必存在唯一的“第一元素第一元素”；2集合中必存在唯一的集合中必存在唯一的 “最后元素最后元素” ；3除最后元素在外，均有除最后元素在外，均有 唯一的后继唯一的后继；4除第一元素之外，均有除第

2、一元素之外，均有 唯一的前驱唯一的前驱。线性结构线性结构是是一个数据元素的一个数据元素的有序（次序）集。有序（次序）集。线性表线性表是一种很简单的线性结构线性结构2.1 线性表的类型定义线性表的类型定义线性表：线性表是线性表：线性表是n个元素的有序序列。个元素的有序序列。它是很常用且很简单的一种数据结构。它是很常用且很简单的一种数据结构。（a1, a2, ai-1，ai, ai1 ，, an）n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表

3、个数，即表长。长。空表空表线性终点线性终点 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级012003010622陈建武陈建武男男 192003级电信级电信0301班班012003010704赵玉凤赵玉凤女女 182003级电信级电信0302班班012003010813王王 泽泽男男 192003级电信级电信0303班班012003010906薛薛 荃荃男男 192003级电信级电信0304班班012003011018王 春男 19192003级电信级电信0305班班： ：例例2 分析学生情况登记表是什么结构。分析学生情况登记表是什么结构。分析分析：数据元素都是同

4、类型（数据元素都是同类型（记录记录），元素间关系是线性的。），元素间关系是线性的。分析分析： 数据元素都是同类型（数据元素都是同类型（字母字母），）， 元素间关系是线性的。元素间关系是线性的。例例1 分析分析26 个英文字母组成的英文表的结构。个英文字母组成的英文表的结构。综上例：综上例：u线性表中的数据元素可以不同线性表中的数据元素可以不同u但同一个表中的元素必须具有相同的属性但同一个表中的元素必须具有相同的属性u 相邻数据元素之间存在序偶关系相邻数据元素之间存在序偶关系u线性表中每一个元素都有确定的位置，如线性表中每一个元素都有确定的位置，如a1是第是第1个数据元素，个数据元素，ai是第是

5、第i个数据元素个数据元素抽象数据类型线性表线性表的定义ADT List 数据对象数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 称 n 为线性表的表长表长; 当 n=0 时为空表空表。数据关系数据关系：R1 |ai-1 ,aiD, i=2,.,n 设线性表为 (a1，a2, . . . ，ai，. . . ，an)，称 i 为 ai 在线性表中的位序位序。 基本操作： 结构初始化操作结构销毁操作 引用型操作 加工型操作 ADT List InitList( &L )操作结果：操作结果：构造一个空的线性表L。初始化操作 结构销毁操作DestroyList( &L )初

6、始条件：操作结果：线性表 L 已存在。销毁线性表 L。ListEmpty( L )ListLength( L )PriorElem( L, cur_e, &pre_e )NextElem( L, cur_e, &next_e ) GetElem( L, i, &e )LocateElem( L, e, compare( ) )ListTraverse(L, visit( )引用型操作引用型操作加工型操作加工型操作 ClearList( &L )ListInsert( &L, i, e )ListDelete(&L, i, &e) 利用上述定义的线性表线性表可以实现其它更复杂的操作。例如假设:有

7、两个集合集合 A 和和 B 分别用两个线性表线性表 LA 和和 LB 表示，即：线性表中的数据元素为集合中的成员。现要求构造一个新的集合现要求构造一个新的集合AAB。例例 2-12-1 扩大线性表 LA，将属于线性表属于线性表LB 而不属于线性不属于线性表表LA 的元素插入到线性表插入到线性表 LA中中去。该问题演绎为对线性表的操作：集合集合 B集合集合 A从集合从集合B B取出物件取出物件, ,看集合看集合A A中是否存在该物件，如中是否存在该物件，如果不存在则放入果不存在则放入A A，如果存在则不放入。，如果存在则不放入。1从线性表LB中取出一个数据元素;2依值在线性表LA中进行查访; 3

8、若不存在，则插入之。GetElem(LB, i)e LocateElem(LA, e, equal( ) ListInsert(LA, n+1, e)操作步骤：操作步骤：4重复上述过程，直到访问到LB中所有元素。 GetElem(Lb, i, e); / 取取Lb中第中第i个数据元素赋给个数据元素赋给e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之void union(List &La, List Lb) La_len = ListL

9、ength(La); / 求线性表的长度求线性表的长度 Lb_len = ListLength(Lb); for (i = 1; i = Lb_len; i+) / union2.2 2.2 线性表类型的实现线性表类型的实现 - -顺序映象顺序映象最简单的一种顺序映象方法是：最简单的一种顺序映象方法是：令令 y y 的存储位的存储位置和置和 x x 的存储位置相邻的存储位置相邻。顺序映象顺序映象 以以 x x 的存储位置和的存储位置和 y y 的存储位置之间某的存储位置之间某种关系表示逻辑关系种关系表示逻辑关系。用一组地址连续地址连续的存储单元依次存放依次存放线性表中的数据元素 a1 a2 a

10、i-1 ai an线性表的线性表的起始地址起始地址称作线性表的基地址基地址以“存储位置相邻存储位置相邻”表示有序对，即：LOC(ai) = LOC(ai-1) + C 其中C为一一个数据元素所占存储量个数据元素所占存储量所有数据元素的存储位置均取决于第一个数据元所有数据元素的存储位置均取决于第一个数据元素的存储位置。素的存储位置。 LOC(ai) = LOC(a1) + (i-1)C 基地址基地址线性表顺序映像的线性表顺序映像的 C 语言描述语言描述typedef struct SqList; / 俗称 顺序表顺序表ElemType *elem; / 存储空间基址int length; / 当

11、前长度int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位)在在C C语言中，一维数组的机内表示就是顺序结构。因语言中，一维数组的机内表示就是顺序结构。因此，可用此，可用C C语言的一维数组实现线性表的顺序存储。语言的一维数组实现线性表的顺序存储。 typedef struct ElemType listMaxSize; int size; SqList; /* MaxSizeMaxSize表示数组的最大元素个数，表示数组的最大元素个数，listlist表示顺序表示顺序表的数组名，表的数组名，sizesize表示顺序表中当前存储的数据元素表示顺序表

12、中当前存储的数据元素个数，它必须满足个数，它必须满足sizeMaxSizesizeMaxSize，SqListSqList是该结构是该结构体的名字。体的名字。* */ /线性表的基本操作在顺序表中的应用线性表的基本操作在顺序表中的应用InitList(&L) / 结构初始化结构初始化LocateElem(L, e, compare() / 查找查找ListInsert(&L, i, e) / 插入元素插入元素ListDelete(&L, i) / 删除元素删除元素Status InitList_Sq( SqList& L ) / 构造一个空的线性表 / InitList_Sq算法时间复杂度时间

13、复杂度： O(1)L.elem = (ElemType*) malloc (LIST_ INIT_SIZE sizeof (ElemType);if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = LIST_INIT_SIZEreturn OK;如何实现定位线性表中元素的操作LocateElem(L, e, compare()先看一下查找的过程先看一下查找的过程:例如：顺序表23 75 41 38 54 62 17 L.elemL.lengthL.listsizee =38pppppi1 2 3 4 1 850p可见，其基本操作是：将顺序表

14、中的元素逐个和给定值e进行比较。 int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) /在顺序表中查询第在顺序表中查询第1 1个满足判定条件的数据元素，若个满足判定条件的数据元素，若存在，则返回它的位序，否则返回存在，则返回它的位序，否则返回0 0。 / LocateElem_Sq O( ListLength(L) )算法的算法的时间复杂度时间复杂度：i = 1; / i i 的初值为第的初值为第 1 1 元素的位序元素的位序p = L.elem; / p p 的初值为第的初值为第 1 1

15、元素的存储位置元素的存储位置while (i = L.length &!(*compare)(*p+, e) +i;if (i = L.length) return i;else return 0;(*compare)(*p+, e)如何实现插入元素到线性表的操作ListInsert(&L, i, e)首先分析首先分析:插入元素时，线性表的逻辑结构有逻辑结构有什么变化什么变化？ (a1, , ai-1, ai, , an) 改变为 (a1, , ai-1, e, ai, , an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean, 表的长度增加21 18 30 75 42 5

16、6 8721 18 30 75例如：ListInsert_Sq(L, 5, 66) L.length-10pppq87564266q = &(L.elemi-1); / q 指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;p Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序表L的第 i 个元素之前插入新的元素e, / i 的合法范围为 1iL.length+1 / ListInsert_Sq 算法时间复杂度算法时间复杂度: :O( ListLength(L) )

17、q = &(L.elemi-1); / q 指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移元素右移*q = e; / 插入e+L.length; / 表长增1return OK;元素右移元素右移考虑移动元素的平均情况考虑移动元素的平均情况: :假设在第 i 个元素之前插入的概率为， 则在长度为n 的线性表中插入一个元素所需移动元素次插入一个元素所需移动元素次数的期望值数的期望值为：ip11) 1(niiisinpE11) 1(11niisinnE2n若假定假定在线性表中任何一个位置上进行插入的

18、概率插入的概率都是相等相等的，则移动元素的期望值移动元素的期望值为：如何实现删除线性表中元素的操作ListDelete(&L, i, &e) ：首先分析：删除元素时，线性表的逻辑结构发生了什么变化？ (a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an)ai+1an, 表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 21 18 30 75 42 56 8721 18 30 75L.length-10pppq8756p = &(L.elemi-1);q = L.elem+L.length-1;for (+p;

19、 p = q; +p) *(p-1) = *p; 例如：ListDelete_Sq(L, 5, e) pStatus ListDelete_Sq (SqList &L, int i, ElemType &e) / ListDelete_Sqfor (+p; p = q; +p) *(p-1) = *p; / 被删除元素之后的元素左移被删除元素之后的元素左移-L.length; / 表长减表长减1 1return OK;算法时间复杂度算法时间复杂度为为: : O( ListLength(L)p = &(L.elemi-1); / p 为被删除元素的位置为被删除元素的位置e = *p; / 被删除

20、元素的值赋给被删除元素的值赋给 eq = L.elem+L.length-1; / 表尾元素的位置表尾元素的位置if (i L.length) return ERROR; / 删除位置不合法删除位置不合法考虑移动元素的平均情况考虑移动元素的平均情况: :假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素移动元素次数的期望值次数的期望值为：iqniidlinqE1)(nidlinnE1)(121n若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值移动元素的期望值为：问题：问题：、在顺序表中，第个元素前面插入一个元素，要、在顺序表中，第个元

21、素前面插入一个元素，要移动多少个元素？移动多少个元素？、在顺序表中，要删除第个元素，要移动多少个、在顺序表中，要删除第个元素，要移动多少个元素？元素？算法：顺序表的合并算法：顺序表的合并 已知顺序表已知顺序表LaLa和和LbLb按值非递减排列，归并两表，得到按值非递减排列，归并两表，得到新表新表LcLc也按值非递减排列。也按值非递减排列。 分析：分析：LcLc中的数据元素或者是中的数据元素或者是LaLa中的数据元素，或者中的数据元素，或者是是LbLb中的数据元素，则只要将中的数据元素，则只要将LaLa或或LbLb中的元素逐个插中的元素逐个插入到入到LcLc中即可。中即可。 设两个指针设两个指针

22、papa和和pbpb分别指向分别指向LaLa和和LbLb中的某个元素，若中的某个元素，若设设papa当前所指的元素为当前所指的元素为a a，pbpb当前所指的元素为当前所指的元素为b b，则，则当前应插入到当前应插入到LcLc中的元素中的元素c c为为 c=c=( () )； c=c=( () ) 很显然，指针很显然，指针papa和和pbpb的初值均为的初值均为1 1，在所指元素插入，在所指元素插入LcLc后，后，papa，pbpb在在LaLa或或LbLb中顺序后移。中顺序后移。void MergeList(SqList La,SqList Lb, SqList &Lc) pa=La.elem

23、; pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length; pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType);pa.last=La.elem+La.length-1;pb.last=Lb.elem+Lb.length-1; While (pa=pa.last & pb=pb.last) if(*pa=*pb) *pc+=*pa+; else *pc+=*pb+; while (pa=pa.last ) *pc+=*pa+;while (pbnext; j = 1; / p p指

24、向第一个结点，指向第一个结点，j j为计数器为计数器while (jnext; +j; / 顺指针向后查找，直到顺指针向后查找，直到 p p 指向第指向第 i i 个元素个元素 / 或或 p p 为空为空e = p-data; / 取得第取得第 i i 个元素个元素return OK;p &if ( !p | ji ) return ERROR; / 第第 i i 个元素不存个元素不存ai-1 线性表中ListInsert(&L, i, e)操作在单链表中的实现： 有序对有序对 变为变为 和和 eaiai-1因此，在单链表中第因此，在单链表中第 i i 个结点之前进行插入的基本个结点之前进行插

25、入的基本操作为操作为: :找到线性表中第找到线性表中第i-1i-1个结点，然后修改其指向个结点，然后修改其指向后继的指针。后继的指针。可见，在链表中插入结点只需要修改指针。但同时，可见，在链表中插入结点只需要修改指针。但同时，若要在第若要在第 i i 个结点之前插入元素，修改的是第个结点之前插入元素，修改的是第 i-1 i-1 个结点的指针。个结点的指针。 Status ListInsert_L(LinkList L, int i, ElemType e) / L 为带头结点的单链表的头指针，本算法为带头结点的单链表的头指针，本算法 / 在链表中第在链表中第i 个结点之前插入新的元素个结点之前

26、插入新的元素 e / LinstInsert_Lp = L; j = 0;while (p & j next; +j; / 寻找第寻找第 i-1 i-1 个结点个结点 Status GetElem_L(LinkList L, int i, ElemType &e) / L是带头结点的链表的头指针，以是带头结点的链表的头指针，以 e 返回第返回第 i 个元素个元素 / GetElem_L算法算法时间复杂度时间复杂度:p = L-next; j = 1; / p p指向第一个结点，指向第一个结点，j j为计数器为计数器while (jnext; +j; / 顺指针向后查找，直到顺指针向后查找，直到

27、 p p 指向第指向第 i i 个元素个元素 / 或或 p p 为空为空e = p-data; / 取得第取得第 i i 个元素个元素return OK;p &if ( !p | ji ) return ERROR; / 第第 i i 个元素不存个元素不存 Status ListInsert_L(LinkList L, int i, ElemType e) / L 为带头结点的单链表的头指针，本算法为带头结点的单链表的头指针，本算法 / 在链表中第在链表中第i 个结点之前插入新的元素个结点之前插入新的元素 e / LinstInsert_Lp = L; j = 0;while (p & j n

28、ext; +j; / 寻找第寻找第 i-1 i-1 个结点个结点if (!p | j i-1) return ERROR; / i i 大于表长加大于表长加1 1或者小于或者小于1 1 s = (LinkList) malloc ( sizeof (LNode); / 生成新结点s-data = e; s-next = p-next; p-next = s; / 插入return OK; eai-1aiai-1sp线性表中ListDelete (&L, i, &e)操作在链表中的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-1在单链表中删除第删除第 i i 个结点个结点的基

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

30、个结点，并令 p 指向其前趋if (!(p-next) | j i-1) return ERROR; / 删除位置不合理q = p-next; p-next = q-next; / 删除并释放结点e = q-data; free(q);return OK;ClearList(&L)操作在链表中的实现:void ClearList(&L) / 将单链表重新置为一个空表 while (L-next) p=L-next; L-next=p-next; / ClearListfree(p);算法时间复杂度：O(ListLength(L)如何从线性表得到单链表？如何从线性表得到单链表？链表是一个动态的结

31、构，它不需要予分配空间，因链表是一个动态的结构，它不需要予分配空间，因此此生成链表的过程生成链表的过程是一个结点是一个结点“逐个插入逐个插入” ” 的过程。的过程。例如，逆位序输入例如，逆位序输入 n n 个数据元素的值，建立带头结个数据元素的值，建立带头结点的单链表。点的单链表。例如，逆位序输入例如，逆位序输入 n n 个数据元素的值，建立带头结个数据元素的值，建立带头结点的单链表。点的单链表。操作步骤：操作步骤：1.建立一个建立一个“空表空表”；2.2.输入数据元素输入数据元素an， 建立结点并插入；建立结点并插入；3.3.输入数据元素输入数据元素an-1， 建立结点并插入；建立结点并插入

32、；ananan-14.4.依次类推，直至输入依次类推，直至输入a a1 1为止。为止。void CreateList_L(LinkList &L, int n) / 逆序输入 n 个数据元素，建立带头结点的单链表 / CreateList_L算法的算法的时间复杂度时间复杂度: O(Listlength(L)L = (LinkList) malloc (sizeof (LNode);L-next = NULL; / 先建立一个带头结点的单链表for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); scanf(&p-data); /

33、输入元素值 p-next = L-next; L-next = p; / 插入在单链表中设置头结点的好处在单链表中设置头结点的好处1 1、使空表和非空表统一。、使空表和非空表统一。2 2、在设计算法的时候，使首元结点和其他结点、在设计算法的时候，使首元结点和其他结点的处理一致。的处理一致。将两个有序链表合并为一个有序链表将两个有序链表合并为一个有序链表 已知单链表已知单链表LaLa和和LbLb按值非递减排列，归并两表，得到新表按值非递减排列，归并两表，得到新表LcLc也也按值非递减排列。按值非递减排列。 分析：分析：LcLc中的数据元素或者是中的数据元素或者是LaLa中的数据元素，或者是中的数

34、据元素，或者是LbLb中的中的数据元素，则只要将数据元素，则只要将LaLa或或LbLb中的元素逐个插入到中的元素逐个插入到LcLc中即可。中即可。 设两个指针设两个指针papa和和pbpb分别指向分别指向LaLa和和LbLb中的某个元素，若设中的某个元素，若设papa当前当前所指的元素为所指的元素为a a，pbpb当前所指的元素为当前所指的元素为b b，则当前应插入到，则当前应插入到LcLc中中的元素的元素c c为：为： c=c=( () )； c=c=( () ) 很显然，指针很显然，指针papa和和pbpb的初值均为的初值均为1 1，在所指元素插入，在所指元素插入LcLc后，后，papa，

35、pbpb在在LaLa或或LbLb中顺序后移。中顺序后移。void MergeList(SqList La,SqList Lb, SqList &Lc) pa=La.elem; pb=Lb.elem; Lc.listsize=Lc.length=La.length+Lb.length; pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType); pa.last=La.elem+La.length-1; pb.last=Lb.elem+Lb.length-1; While (pa=pa.last & pb=pb.last) if(*pa=*

36、pb) *pc+=*pa+; else *pc+=*pb+; while (pa=pa.last ) *pc+=*pa+; while (pbnext; pb=Lb-next; Lc=pc=La; While (pa & pb) if (pa-datadata) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next; pc-next=pa ? pa:pb; free(Lb);链表的优点链表的优点1、合理利用空间。合理利用空间。2 2、插入和删除时不用移动大量元素。、插入和删除时不用移动大量元素。上述定义的单链表实现线

37、性表的操作时存在如下上述定义的单链表实现线性表的操作时存在如下问题问题:改进链表的设置：改进链表的设置：1单链表的表长是一个隐含的值；单链表的表长是一个隐含的值； 1增加增加“表长表长”、“表尾指针表尾指针” 和和 “当前位置的指当前位置的指针针” 三个数据域；三个数据域；2在单链表的最后一个元素之后插入元素时，在单链表的最后一个元素之后插入元素时， 需遍历整个链表；需遍历整个链表；3在链表中，元素的在链表中，元素的“位序位序”的概念淡化了。的概念淡化了。2将基本操作中的将基本操作中的“位序位序 i ”改变为改变为“指针指针 p ”。 1. 1. 双向链表双向链表2.3.2 2.3.2 其它形

38、式的链表其它形式的链表typedef struct DuLNode ElemType data; / 数据域 struct DuLNode *prior; / 指向前驱的指针域 struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList;最后一个结点的指针域的指针又指回第一个结点的链表。 a1 a2 . an 2. 2. 循环链表循环链表和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。3. 3. 双向循环链表双向循环链表空表空表非空表非空表 a1 a2 . an双向链表的操作特点：双向链表的操作

39、特点：1.“1.“查询查询”和单链表相同。和单链表相同。2. 2. 插入插入”和和“删除删除”时需要同时修改两个方向上时需要同时修改两个方向上的指针。的指针。ai-1aies-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-1单循环链表的一个很重要的应用是若瑟夫环问题：n个人围成一圈，每人有一个各不相同的编号。选择一个人作为起点，然后顺时针从1到k数数，每数到k的人退出圈子，圈子缩小，再从下一个人

40、继续从1到k数数,重复上面过程。求最后退出圈子的那个人原来的编号。该问题是由古罗马著名史学家Josephus提出的问题演变而来，所以通常称之为Josephus问题。Josephus问题的解决需要采用循环链表，先构造一个有n个结点的不带头结点的单循环链表，在链表的某个结点开始从1计数，计到k-1时，将下一个结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，数到k-1，再将其下一个结点从单循环链表删除，直到剩下一个结点为止。2.4 2.4 一元多项式的表示nnnxpxpxppxp.)(2210在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示: P = (p0, p

41、1, ，pn)一元多项式一元多项式但是对于形如但是对于形如 S(x) = 1 + 3x10000 2x20000的多项式，上述表示方法合适吗？的多项式，上述表示方法合适吗？ 一般的，一元稀疏多项式一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中：其中：pi 是指数为ei 的项的非零系数， 0 e1 e2 em = n可以用下列线性表来表示：（p1, e1）, (p2, e2), , (pm,em) ） P999(x) = 7x3 - 2x12 - 8x999例如:可表示为 ( (7, 3), (-2, 12), (-8, 999) )ADT Polyno

42、mial 数据对象数据对象： 数据关系数据关系：抽象数据类型下的一元多项式的定义：D ai | ai TermSet, i=1,2,.,m, m0，TermSet 中的每个元素包含一个表示系数的实数和表示指每个元素包含一个表示系数的实数和表示指数的整数数的整数 R1 |ai-1 ,aiD, i=2,.,n，且ai-1中的指中的指数值数值ai中的指数值中的指数值 CreatPolyn ( &P, m )DestroyPolyn ( &P )PrintPolyn ( &P ) 基本操作基本操作：操作结果操作结果：输入 m 项的系数和指数， 建立一元多项式 P。初始条件初始条件：一元多项式 P 已存在。操作结果操作结果：销毁一元多项式 P。初始条