第二章线性表

1、 线性结构的线性结构的特点特点： 在数据元素的有限集合中：在数据元素的有限集合中：l存在存在的一个被称作的一个被称作“”的数据元素的数据元素l存在存在的一个被称作的一个被称作“”的数据元素的数据元素l除第一个外，集合中的每个数据元素均除第一个外，集合中的每个数据元素均l除最后一个外，集合中的每个数据元素均除最后一个外，集合中的每个数据元素均2.1 线性表的类型定义线性表的类型定义2.3 线性表类型的实现线性表类型的实现 链式映象链式映象2.4 一元多项式的表示一元多项式的表示2.2 线性表类型的实现线性表类型的实现 顺序映象顺序映象2.5 小结及习题小结及习题l定义：一个线性表是定义：一个线性

2、表是n n个数据元素的有限序列个数据元素的有限序列niaaaa,21如例例1 英文字母表（英文字母表（A,B,C,Z)是一个线性表是一个线性表例例2学号姓名年龄001张三18002李四19数据元素数据元素l特征：特征：u元素个数元素个数n(n0) 称为称为表长度，表长度，n=0空表空表u1in时时uai的直接的直接前驱前驱是是ai-1，a1无直接前驱无直接前驱uai的直接的直接后继后继是是ai+1，an无直接后继无直接后继u元素同构元素同构（属于同一数据对象）（属于同一数据对象），且不能出现缺项，且不能出现缺项 记录记录文件文件抽象数据类型线性表线性表的定义如下：ADT List 数据对象数据

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

4、p;L )初始条件：操作结果：线性表 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( )引用型操作引用型操作: : ListEmpty( L )初始条件：操作结果：线性表L已存在。若L为空表，则返回TRUE，否则FALSE。（线性表判空）ListLength( L )初始条件

5、：操作结果：线性表L已存在。返回L中元素个数。（求线性表的长度） PriorElem( L, cur_e, &pre_e )初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。（求数据元素的前驱）NextElem( L, cur_e, &next_e )初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。（求数据元素的后继）GetElem( L, i, &e ) 初始条件： 操作结果：线性表L已存在，

6、且 1iLengthList(L)用 e 返回L中第 i 个元素的值。（求线性表中某个数据元素）LocateElem( L, e, compare( ) )初始条件：操作结果：线性表L已存在，e为给定值， compare( )是元素判定函数。返回L中第中第1个个与e满足满足关系compare( )的元素的位序。若这样的元素不存在，则返回值为0。（定位函数） ListTraverse(L, visit( )初始条件：操作结果：线性表L已存在。Visit() 为某个访问函数。依次依次对L的每个元素调用函数visit( )。一旦visit( )失败，则操作失败。（遍历线性表）加工型操作加工型操作 C

7、learList( &L )ListInsert( &L, i, e )ListDelete(&L, i, &e) ClearList( &L )初始条件：操作结果：线性表L已存在。将L重置为空表。（线性表置空） ListInsert( &L, i, e )初始条件：操作结果：线性表L已存在， 且 1iLengthList(L)+1在L的第i个元素之前插入插入新的元素e，L的长度增1。（插入数据元素）ListDelete(&L, i, &e)初始条件：操作结果：线性表L已存在且非空， 1iLengthList(L)删除L的第i个元

8、素，并用e返回其值，L的长度减1。（删除数据元素）利用上述定义的线性表线性表 可以实现其它更复杂的操作例例 2-2例例 2-3例例 2-1 假设:有两个集合集合 A 和和 B 分别用两个线性表线性表 LA 和和 LB 表示，即：线性表中的数据元素即为集合中的成员。 现要求一个新的集合现要求一个新的集合AAB。例例 2-1 要求对线性表作如下操作：扩大线性表 LA，将存在于线性表存在于线性表LB 中中而不存在于线性表不存在于线性表 LA 中中的数据元素插入到线性表插入到线性表 LA 中中去。上述问题可演绎为：1从线性表LB中依次察看每个数据元素;2对其在线性表LA中进行比较; 3若不存在，则插入

9、之。GetElem(LB, i,e) LocateElem(LA, e, equal( ) ListInsert(LA, +n, e)操作步骤：操作步骤： 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 = ListLength(La); / 求线性表的长度求线性表的

10、长度 Lb_len = ListLength(Lb); for (i = 1; i = Lb_len; i+) / union 已知已知一个 B，试构造构造一个 A，使使 A 包含包含 B 中所有出现过中所有出现过的数据元素的数据元素。仍选用线性表线性表表示集合。例例 2-2集合集合 B集合集合 A从集合 B 取出物件放入集合 A且集合A中同样物件不能有两件以上同样物件不能有两件以上因此，算法的策略应该和例算法的策略应该和例2-1相似相似void union(List &La, List Lb) La_len=ListLength(La); Lb_len=ListLength(Lb);

11、 / union GetElem(Lb, i, e); / 取取Lb中第中第 i 个数据元素赋给个数据元素赋给 e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之for (i = 1; i = Lb_len; i+) InitList(La); / 构造(空的)线性表LA 若线性表中的数据元素相互之间可以比较比较，并且数据元素在线性表中依值非递减依值非递减或非递增非递增有序有序排列，即 aiai-1 或 aiai-1(i = 2,3,

12、n)，则称该线性表为试改变结构，以有序表有序表表示集合。例如例如:（2，3，3，5，6，6，6，8，12）对集合 B 而言， 值相同的数据元素必定相邻值相同的数据元素必定相邻对集合 A 而言， 数据元素依值从小至大的顺序插入数据元素依值从小至大的顺序插入因此，数据结构改变了，数据结构改变了， 解决问题的策略也相应要改变。解决问题的策略也相应要改变。例例 2-2 已知已知一个非纯集合非纯集合 B，试构造构造一个纯集合纯集合 A，使使 A 包含包含 B 中所有出现过的数据元素中所有出现过的数据元素。 （用非递减有序的顺序表表示A、B）void purge(List &La, List Lb

13、) InitList(La); La_len = ListLength(La); Lb_len =ListLength(Lb); / 求线性表的长度求线性表的长度 for (i = 1; i = Lb_len; i+) / purge GetElem(Lb, i, e); / 取取Lb中第中第i个数据元素赋给个数据元素赋给 eif (!equal (en, e) ListInsert(La, +La_len, e); en = e; / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之则则 归并两个“其数据元素按值非递减有其数据元素按值非递减有序排列序排列”的有序

14、表 LA 和 LB，求得有序表 LC 也具有同样特性。设设 La = (a1, , ai, , an), Lb = (b1, , bj, , bm) Lc = (c1, , ck, , cm+n)且且已由(a1, , ai-1)和(b1, ,bj-1)归并得归并得 (c1, , ck-1)jijjiikbabbaac例例 2-3k = 1, 2, , m+n1初始化初始化 LC 为空表；为空表；基本操作：2分别从分别从 LA和和LB中取得当前元素中取得当前元素 ai 和和 bj；3若若 aibj，则将，则将 ai 插入到插入到 LC 中，否则将中，否则将 bj 插入到插入到 LC 中；中；4重

15、复重复 2 和和 3 两步，直至两步，直至 LA 或或 LB 中元素中元素 被取完为止；被取完为止；5将将 LA 表或表或 LB 表中剩余元素复制插入到表中剩余元素复制插入到 LC 表中。表中。 / La 和 Lb 均非空，i = j = 1, k = 0 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) / 将 ai 插入到 Lc 中 ListInsert(Lc, +k, ai); +i; else / 将 bj 插入到 Lc 中 ListInsert(Lc, +k, bj); +j; void MergeList(List La, L

16、ist Lb, List &Lc) / 本算法将非递减的有序表 La 和 Lb 归并为 Lc / merge_listwhile (i = La_len) & (j = Lb_len) / La 和和 Lb 均不空均不空 while (i=La_len) / 若 La 不空while (j=Lb_len) / 若 Lb 不空InitList(Lc); / 构造空的线性表 Lci = j = 1; k = 0;La_len = ListLength(La);Lb_len = ListLength(Lb); while (i = La_len) / 当La不空时 GetElem(L

17、a, i+, ai); ListInsert(Lc, +k, ai); / 插入插入 La 表中剩余元素表中剩余元素 while (j = Lb_len) / 当Lb不空时 GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入插入 Lb 表中剩余元素表中剩余元素最简单的一种顺序映象方法是：最简单的一种顺序映象方法是： 令令 y y 的存储位置和的存储位置和 x x 的存储位置的存储位置相邻相邻。顺序映象顺序映象 以以 x 的存储位置和的存储位置和 y 的存储位置的存储位置之间某种关系表示逻辑关系之间某种关系表示逻辑关系 用一组地址连续地址连续的存储

18、单元 依次存放依次存放线性表中的数据元素 a1 a2 ai-1 ai an线性表的线性表的起始地址起始地址，称作线性表的基地址基地址以“存储位置相邻存储位置相邻”表示有序对 即：LOC(ai) = LOC(ai-1) + C 所有数据元素的存储位置均取决于所有数据元素的存储位置均取决于 第一个数据元素的存储位置第一个数据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)C 基地址基地址顺序映象的顺序映象的 C 语言描述语言描述typedef struct SqList; / 也称 顺序表顺序表#define LIST_INIT_SIZE 80 / 线性表存储空间的初始分配量#d

19、efine LISTINCREMENT 10 / 线性表存储空间的分配增量ElemType *elem; / 存储空间基址int length; / 当前长度int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位)线性表的基本操作在顺序表中的实现线性表的基本操作在顺序表中的实现InitList(&L) / 结构初始化结构初始化LocateElem(L, e, compare() / 查找查找ListInsert(&L, i, e) / 插入元素插入元素ListDelete(&L, i) / 删除元素删除元素Status Ini

20、tList_Sq( SqList& L, int maxsize ) / 构造一个最大容量为 maxsize 的顺序表 / InitList_Sq算法时间复杂度时间复杂度：O(1)L.elem = new ElemTypemaxsize; / 为顺序表分配大小为 maxsize 的数组空间if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = maxsize;return OK;顺序表的查找 例如：23 75 41 38 54 62 17L.elemL.length = 7L.listsizee =38pppppi 1 2 3 4 1

21、 850p查找的基本操作是查找的基本操作是: : 将顺序表中的将顺序表中的 元素逐个和给定元素逐个和给定 值值e e相比较。相比较。查找成功，返回i值！查找不成功，返回0！p int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在顺序表中查询第一个满足判定条件的数据元素，在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回 0 0 / LocateElem_Sq O( ListLength(L) )算法的算法的时间复杂度时间复

22、杂度为：为：i = 1; / i i 的初值为第的初值为第 1 1 元素的位序元素的位序p = L.elem; / p p 的初值为第的初值为第 1 1 元素的存储位置元素的存储位置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) 改变

23、为a1 a2 ai-1 ai ana1 a2 ai-1 ai ean, 表的长度增加(a1, , ai-1, e, ai, , an) Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序表L的第 i 个元素之前插入新的元素e, / i 的合法范围为 1iL.length+1 / ListInsert_Sq 算法时间复杂度算法时间复杂度为为: :O( ListLength(L) )q = &(L.elemi-1); / q 指示插入位置for (p = &(L.elemL.length-1); p = q; -

24、p) *(p+1) = *p; / 插入位置及之后的元素右移元素右移*q = e; / 插入e+L.length; / 表长增1return OK;元素右移元素右移（合法性检查、分配空间满需追加空间等）（合法性检查、分配空间满需追加空间等）if (L.length = L.listsize) / 当前存储空间已满，增加分配 newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); / 存储分配失败 L.elem = newba

25、se; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容量if (i L.length+1) return ERROR; / 插入位置不合法21 18 30 75 42 56 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考虑移动元素的平均情况考虑移动元素的平均情况: : 假设在第 i 个元素之前插入的

26、概率为 ， 则在长度为n 的线性表中插入一个元素所需插入一个元素所需移动元素次数的期望值移动元素次数的期望值为：ip11) 1(niiisinpE11) 1(11niisinnE2n 若假定假定在线性表中任何一个位置上进行插入插入的概率的概率都是相等相等的，则移动元素的期望值移动元素的期望值为：线性表操作 ListDelete(&L, i, &e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？ (a1, , ai-1, ai, ai+1, , an) 改变为ai+1 an, 表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 (a1, ,

27、ai-1, ai+1, , an)Status 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; / 被删除元素的值赋给被删除元素的值赋给 eq = L.elem+L.length-

28、1; / 表尾元素的位置表尾元素的位置if (i L.length) return ERROR; / 删除位置不合法删除位置不合法元素左移元素左移考虑移动元素的平均情况考虑移动元素的平均情况: : 假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值移动元素次数的期望值为：iqniidlinqE1)(nidlinnE1)(121n若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值移动元素的期望值为：21 18 30 75 42 56 8721 18 30 75L.length-10pppq8756p = &(L.ele

29、mi-1);q = L.elem+L.length-1;for (+p; p next; j = 1; / p p指向第一个结点，指向第一个结点，j j为计数器为计数器while (p & jnext; +j; / 顺指针向后查找，直到顺指针向后查找，直到 p p 指向第指向第 i i 个元素个元素 / 或或 p p 为空为空if ( !p | ji ) return ERROR; / 第第 i i 个元素不存在个元素不存在e = p-data; / 取得第取得第 i i 个元素个元素return OK;ai-1 线性表的操作 ListInsert(&L, i, e) 在单链表

30、中的实现： 有序对有序对 改变为改变为 和和 eaiai-1 因此，在单链表中第因此，在单链表中第 i 个结点之前进个结点之前进行插入的基本操作为行插入的基本操作为: 找到线性表中第找到线性表中第i-1i-1个结点，然后修改个结点，然后修改其指向后继的指针。其指向后继的指针。 可见，在链表中插入结点只需要修改可见，在链表中插入结点只需要修改指针。但同时，若要在第指针。但同时，若要在第 i 个结点之前个结点之前插入元素，修改的是第插入元素，修改的是第 i-1 个结点的指个结点的指针。针。 Status ListInsert_L(LinkList L, int i, ElemType e) / L

31、 为带头结点的单链表的头指针，本算法为带头结点的单链表的头指针，本算法 / 在链表中第在链表中第i 个结点之前插入新的元素个结点之前插入新的元素 e / LinstInsert_L算法的算法的时间复杂度时间复杂度为为:O(ListLength(L)p = L; j = 0;while (p & j next; +j; / 寻找第寻找第 i-1 个结点个结点if (!p | j i-1) return ERROR; / i 大于表长或者小于大于表长或者小于1 s = new LNode; / 生成新结点s-data = e; s-next = p-next; p-next = s; /

32、插入return OK; eai-1aiai-1sp在链表的第在链表的第i个位置上插入元素：个位置上插入元素： （先查找插入位置）前插（先查找插入位置）前插/后插后插 O(n)；在指针在指针p所指的结点上插入元素：所指的结点上插入元素： 前插前插O(n),后插后插O(1) 前插如何改进前插如何改进?的操作ListDelete (&L, i, &e)在链表中的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-1 在单链表中删除第删除第 i i 个结点个结点的基本基本操作操作为:找到线性表中第找到线性表中第i-1i-1个结点，修个结点，修改其指向后继的指针。改其指向

33、后继的指针。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 个结点，并令 p 指向其前趋if (!(p-next) | j i-1) re

34、turn 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)如何从线性表得到单链表？如何从线性表得到单链表？链表是一个动态的结构，它不需要链表是一个动态的结构，它不需要预分配空间，因此

35、预分配空间，因此生成链表的过程生成链表的过程是一个结点是一个结点“逐个插入逐个插入” ” 的过程。的过程。1、由表头插入：得到逆序 - 头插法2、由表尾插入：得到正序 - 尾插法例如：逆位序输入例如：逆位序输入 n n 个数据元素的值，个数据元素的值， 建立带头结点的单链表。建立带头结点的单链表。操作步骤：操作步骤：一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素an， 建立结点并插入；建立结点并插入；三、输入数据元素三、输入数据元素an-1， 建立结点并插入；建立结点并插入；ananan-1四、依次类推，直至输入四、依次类推，直至输入a a1 1为止。为止。void H

36、CreateList_L(LinkList &L, int n) / 逆序输入 n 个数据元素，建立带头结点的单链表 / HCreateList_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); / 输入元素值 p-next = L-next; L-next = p; / 插

37、入void TCreateList_L(LinkList &L, int n) / 顺序输入 n 个数据元素，建立带头结点的单链表 / TCreateList_L算法的算法的时间复杂度时间复杂度为:O(Listlength(L)L = (LinkList) malloc (sizeof (LNode);L-next = NULL; / 先建立一个带头结点的空单链表 / q始终指向表尾结点用上述定义的单链表实现线性表的操作时，用上述定义的单链表实现线性表的操作时，存在的存在的问题问题： 改进链表的设置：改进链表的设置：1单链表的表长是一个隐含的值；单链表的表长是一个隐含的值； 1增加增加

38、“表长表长”、“表尾指针表尾指针” 和和 “当前当前位置的位置的 指针指针” 三个数据域；三个数据域；2在单链表的最后一个元素之后插入元素时，在单链表的最后一个元素之后插入元素时， 需遍历整个链表；需遍历整个链表；3在链表中，元素的在链表中，元素的“位序位序”概念淡化，结点的概念淡化，结点的 “位置位置”概念加强。概念加强。2将基本操作中的将基本操作中的“位序位序 i ”改变为改变为“指针指针 p ”。 1. 双向链表双向链表四、其它形式的链表四、其它形式的链表typedef struct DuLNode ElemType ; / 数据域 struct DuLNode ; / 指向前驱的指针域

39、 struct DuLNode ; / 指向后继的指针域 DuLNode, *DuLinkList; 最后一个结点的指针域的指针又指回第一个结点的链表。 a1 a2 . an 2. 循环链表循环链表 和单链表的差别在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。如何判空？双向循环链表双向循环链表空表空表非空表非空表 a1 a2 . an双向链表的操作特点：双向链表的操作特点：u“查询查询” ” 和单链表相同和单链表相同u“插入插入” ” 和和“删除删除”时需要同时时需要同时 修改两个方向上的指针。修改两个方向上的指针。ai-1aies-next = p-ne

40、xt; p-next = s;s-next-prior = s; s-prior = p;psai-1ai插入插入ai-1aies-prior = p- prior ; p- prior = s;s-next =p ; s- prior -next = s;pai-1ai若在指针p所指结点之前插入结点,如何实现此插入算法？s双向链表插入结点时算法有多种，关键是不要断链：只要不先执行 p- prior = s p- prior = s 语句 即可。ai-1删除删除aiai+1p-next = p-next-next;p-next-prior = p;pai-1u如何删除指针p所指结点？ai-1a

41、iai+1ai-1ppp-next -next - prior = p;p-next = p-next-next;五、有序表类型五、有序表类型ADT Ordered_List 数据对象数据对象: S = xi|xi OrderedSet ， i=1,2,n, n0 集合中任意两个元素之间均可以进行比较数据关系数据关系: :R = | xi-1, xi S, xi-1 xi, i=2,3,n 基本操作：基本操作： LocateElem( L, e, &q, int(*compare)(ElemType,ElemType) )初始条件初始条件：有序表L已存在。操作结果操作结果：若有序表L中

42、存在元素e，则 q指示L中第一个值为第一个值为 e 的元素的元素的位置，并返回函数值TRUE；否则 q 指示第一个大第一个大于于 e 的元素的前驱的元素的前驱的位置，并返回函数值FALSE。Compare是一个是一个有序判定函数有序判定函数( 12, 23, 34, 45, 45, 56, 67, 78, 89, 98)例如例如:若若 e = 45, 则则 q 指向指向 若若 e = 88, 则则 q 指向指向表示值为表示值为 88 的元素应插入的元素应插入在该指针所指结点之后。在该指针所指结点之后。nnnxpxpxppxp.)(2210在计算机中，可以用一个线性表来表示在计算机中，可以用一个

43、线性表来表示: P = (p0, p1, ，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 Polynomial 数据对象数据对象： 数据关系数据关系：抽象数据类型一元多项式的定义如下：D ai | ai TermSet, i=1,2,.,m, m0 TermSet 中的每个元素包含一个每个元素包含一个 表示系数的实数和表示指数的整数表示系数的实数和表示指数的整数 R1 |ai-1 ,aiD, i=2,.,n 且ai-1中的指数