1、第二章第二章 线性表线性表2.1 线性表的类型定义线性表的类型定义2.3 线性表类型的实现线性表类型的实现 链式映象链式映象2.4 一元多项式的表示一元多项式的表示2.2 线性表类型的实现线性表类型的实现 顺序映象顺序映象线性结构的线性结构的基本特征基本特征为为:1集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；2集合中必存在唯一的一个集合中必存在唯一的一个“最后元素最后元素”；3除最后元素之外，均有除最后元素之外，均有 唯一的后继唯一的后继；4除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱。线性结构线性结构 是是 一个数据元素的一个数据元素的有序（次序）集有
2、序（次序）集线性表线性表是一种最简单的线性结构线性结构2.1线性表的类型定义线性表的类型定义1 线性表的逻辑结构l 线性表(Linear List)：由n(n)个数据元素(结点)a1，a2，an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作：(a1，a2，an)l 这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。l例1、26个英文字母组成的字母表l （A，B，C、Z）l例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。l（6，17，28，50，92，188）姓名学号性别年龄健康情况王小林
3、790631 男 18 健康陈红790632 女 20 一般刘建平790633 男 21 健康张立立790634 男 17 神经衰弱.综合上述例子，我们可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1；其余的内部结点ai(2in-1)都有且仅有一个直接前趋a i-1和一个直接后继a i+1。线性表是一种典型的线性结构。l数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。l抽象数据类型线性表的定义为：P19 抽象数据类型线性表线性表的定义如下：A
4、DT 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)初始条件：操作结果：线性
5、表 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)初始条件：操作结果：线性表L已存在。返回L中元素个数。（求线性表的长度）PriorElem(L,cur_e,&pre_e)初始条件
6、：操作结果：线性表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已存在，且 1iLengthList(L)。用 e 返回L中第 i 个元素的值。（求线性表中某个数据元素）LocateElem(L,e,compare()初始条件：操作结果：线性表L已
7、存在，e为给定值，compare()是元素判定函数。返回L中第中第1个个与e满足满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。（定位函数）ListTraverse(L,visit()初始条件：操作结果：线性表L已存在，Visit()为某个访问函数。依次依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。（遍历线性表）加工型操作加工型操作 ClearList(&L)PutElem(&L,i,&e)ListInsert(&L,i,e)ListDelete(&L,i,&e)ClearList(&L)初始条件：操作结果：线性表L已存在。将L重置为空
8、表。（线性表置空）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。（删除数据元素）利用上述定义的线性表线性表 可以实现其它更复杂的操作例例 2-2例例
9、2-3例例 2-1 假设:有两个集合集合 A 和和 B 分别用两个线性表线性表 LA 和和 LB 表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合现要求一个新的集合AAB。例例 2-1 要求对线性表作如下操作：扩大线性表 LA，将存在于线性表存在于线性表LB 中中而不存在于线性表不存在于线性表 LA 中中的数据元素插入到线性表插入到线性表 LA 中中去。上述问题可演绎为：1从线性表LB中依次察看每个数据元素;2依值在线性表LA中进行查访;3若不存在，则插入之。GetElem(LB,i)e LocateElem(LA,e,equal()ListInsert(LA,n+1,e)操作
10、步骤：操作步骤：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);/求线性表的长度求线性表的长度 Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)/union 已知已知一个非纯集合非纯集合 B，试构造构造一个纯集合纯集合 A，使使 A中只包含中只包
11、含 B 中所有值各中所有值各不相不相 同的数据元素同的数据元素。仍选用线性表线性表表示集合。例例 2-2集合集合 B集合集合 A从集合 B 取出物件放入集合 A要求集合A中同样物件不能有两件以上同样物件不能有两件以上因此，算法的策略应该和例算法的策略应该和例2-1相同相同void union(List&La,List Lb)La_len=ListLength(La);Lb_len=ListLength(Lb);/union GetElem(Lb,i,e);/取取Lb中第中第 i 个数据元素赋给个数据元素赋给 e if(!LocateElem(La,e,equal()ListInsert(La,
12、+La_len,e);/La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之for(i=1;i=Lb_len;i+)InitList(La);/构造(空的)线性表LA若线性表中的数据元素相互之间可以比较比较，并且数据元素在线性表中依值非递减或非依值非递减或非递增有序递增有序排列，即 aiai-1 或 aiai-1(i=2,3,n)，则称该线性表为有序表有序表(Ordered List)(Ordered List)。试改变结构，以有序表有序表表示集合。例如例如：（2，3，3，5，6，6，6，8，12）对集合 B 而言，值相同的数据元素必定相邻；值相同的数据元素必定相邻；
13、对集合 A 而言，数据元素依值从小至大的顺序插入。数据元素依值从小至大的顺序插入。因此，数据结构改变了，数据结构改变了，解决问题的策略也相应要改变。解决问题的策略也相应要改变。void purge(List&La,List Lb)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(ListEmpty(La)|!equal(en,e)ListInsert(La,
14、+La_len,e);en=e;/La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之void MergeList(List La,List 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);
15、/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;while(i=La_len)/当La不空时 GetElem(La,i+,ai);ListInsert(Lc,+k,ai);/插入插入 La 表中剩余元素表中剩余元素 while(j=Lb_len)/当Lb不空时 GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);/插入插入
16、 Lb 表中剩余元素表中剩余元素最简单的一种顺序映象方法是：最简单的一种顺序映象方法是：令令 y y 的存储位置和的存储位置和 x x 的存储位置的存储位置相邻相邻。顺序映象顺序映象 以以 x 的存储位置和的存储位置和 y 的存储位置的存储位置之间某种关系表示逻辑关系之间某种关系表示逻辑关系。用一组地址连续地址连续的存储单元 依次存放依次存放线性表中的数据元素 a1 a2 ai-1 ai an线性表的线性表的起始地址起始地址称作线性表的基地址基地址以“存储位置相邻存储位置相邻”表示有序对 即：LOC(ai)=LOC(ai-1)+C 一个数据元素所占存储量一个数据元素所占存储量所有数据元素的存储
17、位置均取决于所有数据元素的存储位置均取决于 第一个数据元素的存储位置第一个数据元素的存储位置 LOC(ai)=LOC(a1)+(i-1)C 基地址基地址顺序映像的顺序映像的 C 语言描述语言描述typedef struct SqList;/俗称 顺序表顺序表#define LIST_INIT_SIZE 80 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量ElemType*elem;/存储空间基址int length;/当前长度int listsize;/当前分配的存储容量 /(以sizeof(ElemType)为单位)线性表的基本操作在
18、顺序表中的实现线性表的基本操作在顺序表中的实现InitList(&L)/结构初始化结构初始化LocateElem(L,e,compare()/查找查找ListInsert(&L,i,e)/插入元素插入元素ListDelete(&L,i)/删除元素删除元素1.初始化操作初始化操作Status InitList_Sq(SqList&L)/构造一个空的线性表 /InitList_Sq算法时间复杂度时间复杂度：O(1)L.elem=(ElemType*)malloc(LIST_ INIT_SIZE sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L.length=
19、0;L.listsize=LIST_INIT_SIZEreturn OK;2.查找操作（或定位操作）例如：顺序表23 75 41 38 54 62 17L.elemL.lengthL.listsizee=38pppppi 1 2 3 4 1 850p可见，基本操作是：将顺序表中的元素逐个和给定值 e 相比较。int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)/在顺序表中查询第一个满足判定条件的数据元素，在顺序表中查询第一个满足判定条件的数据元素，/若存在，则返回它的位序，否则返回若存在，则返回它的位
20、序，否则返回 0 0/LocateElem_Sq O(ListLength(L)算法的算法的时间复杂度时间复杂度为：为：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)3.插入操作线性表操作 ListInsert(&L,i,e)的实现：首先分析首先分析:插入元素时，线性表的逻辑结构逻辑结构发生什么变化发生什么
21、变化？(a1,ai-1,ai,an)改变为 (a1,ai-1,e,ai,an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean,表的长度增加 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;-p)*(p+1)=*p;/插入位置及之后的元素右移
22、元素右移*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=newbase;/新基址 L.listsize+=LISTINCREMENT;/增加存储容量if(i L.length+1)return ERROR;/插入位置不合法21 18 30 75 4
23、2 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 个元素之前插入的概率为 ，则在长度为n 的线性表中插入一个元素所需插入一个元素所需移动元素次数的期望值移动元素次数的期望值为：ip11)1(niiisinpE11)1(11niisinnE2n 若假定假定在线性表中任何一个位置上进行插入插入的概率的概率都是相等相等的，则移动
24、元素的期望值移动元素的期望值为：4.删除操作线性表操作 ListDelete(&L,i,&e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？(a1,ai-1,ai,ai+1,an)改变为 (a1,ai-1,ai+1,an)ai+1 an,表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 Status ListDelete_Sq (SqList&L,int i,ElemType&e)/ListDelete_Sqfor(+p;p=q;+p)*(p-1)=*p;/被删除元素之后的元素左移被删除元素之后的元素左移-L.length;/表长减表长减1 1retur
25、n OK;算法时间复杂度算法时间复杂度为为:O(ListLength(L)p=&(L.elemi-1);/p 为被删除元素的位置为被删除元素的位置e=*p;/被删除元素的值赋给被删除元素的值赋给 eq=L.elem+L.length-1;/表尾元素的位置表尾元素的位置if(i L.length)return ERROR;/删除位置不合法删除位置不合法元素左移元素左移考虑移动元素的平均情况考虑移动元素的平均情况:假设删除第 i 个元素的概率为 ,则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值移动元素次数的期望值为：iqniidlinqE1)(nidlinnE1)(121n若假定在线
26、性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值移动元素的期望值为：21 18 30 75 42 56 8721 18 30 75L.length-10pppq8756p=&(L.elemi-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;
27、/取得第取得第 i i 个元素个元素return OK;ai-1 线性表的操作 ListInsert(&L,i,e)在单链表中的实现：有序对有序对 改变为改变为 和和 eaiai-1 因此，在单链表中第因此，在单链表中第 i 个结点之前进个结点之前进行插入的基本操作为行插入的基本操作为:找到线性表中第找到线性表中第i-1i-1个结点，然后修改个结点，然后修改其指向后继的指针。其指向后继的指针。可见，在链表中插入结点只需要修改可见，在链表中插入结点只需要修改指针。但同时，若要在第指针。但同时，若要在第 i 个结点之前个结点之前插入元素，修改的是第插入元素，修改的是第 i-1 个结点的指个结点的指
28、针。针。Status ListInsert_L(LinkList L,int i,ElemType e)/L 为带头结点的单链表的头指针，本算法为带头结点的单链表的头指针，本算法 /在链表中第在链表中第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=(LinkList)malloc(sizeof(LNode);/生
29、成新结点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 个结点个结点的基本基本操作操作为:找到线性表中第找到线性表中第i-1i-1个结点，修个结点，修改其指向后继的指针。改其指向后继的指针。ai-1aiai+1ai-1q=p-next;p-next=q-next;e=q-data;free(q);pq Status ListDelete_L(LinkList L,in
30、t 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)return ERROR;/删除位置不合理q=p-next;p-next=q-next;/删除并释放结点e=q-data;free(q);return OK;操作 ClearList(&L)在链表中的实现:void ClearList(&L)/将单链表重新置为一个空表 wh
31、ile(L-next)p=L-next;L-next=p-next;/ClearListfree(p);算法时间复杂度：O(ListLength(L)如何从线性表得到单链表？如何从线性表得到单链表？链表是一个动态的结构，它不需要链表是一个动态的结构，它不需要予分配空间，因此予分配空间，因此生成链表的过程生成链表的过程是一个结点是一个结点“逐个插入逐个插入”的过程。的过程。例如：逆位序输入例如：逆位序输入 n n 个数据元素的值，个数据元素的值，建立带头结点的单链表。建立带头结点的单链表。操作步骤：操作步骤：一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素an，建立结点并插
32、入；建立结点并插入；三、输入数据元素三、输入数据元素an-1，建立结点并插入；建立结点并插入；ananan-1四、依次类推，直至输入四、依次类推，直至输入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)
33、;scanf(&p-data);/输入元素值 p-next=L-next;L-next=p;/插入四、一个带头结点的线性链表类型四、一个带头结点的线性链表类型typedef struct LNode /结点类型结点类型 ElemType data;struct LNode *next;*Link,*Position;Status MakeNode(Link&p,ElemType e);/分配由 p 指向的值为e的结点，并返回OK，/若分配失败，则返回 ERRORvoid FreeNode(Link&p);/释放 p 所指结点链表类型（略）；链表基本操作；（从略）1.双向链表双向链表五、其它形式
34、的链表五、其它形式的链表typedef struct DuLNode ElemType data;/数据域 struct DuLNode *prior;/指向前驱的指针域 struct DuLNode *next;/指向后继的指针域 DuLNode,*DuLinkList;最后一个结点的指针域的指针又指回第一个结点的链表 a1 a2 .an 2.循环链表循环链表 和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。双向循环链表双向循环链表空表空表非空表非空表 a1 a2 .an双向链表的操作特点：双向链表的操作特点：“查询查询”和单链表相同。和单
35、链表相同。“插入插入”和和“删除删除”时需要同时修时需要同时修改两个方向上的指针。改两个方向上的指针。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六、有序表类型六、有序表类型ADT Ordered_List 数据对象数据对象:S=xi|xi OrderedSet，i=1,2,n,n0 集合中任意两个元素之间均可以进行比较数据关系数据关系:R=|xi-1,xi S,xi-1 xi,i=2,3,n 回顾例
36、回顾例2-2的两个算法的两个算法 LocateElem(L,e,&q,int(*compare)(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 指向指向
37、表示值为表示值为 88 的元素应插入的元素应插入在该指针所指结点之后。在该指针所指结点之后。void union(List&La,List Lb)/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 个数据元素赋给个数据元素赋给 e if(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在和中不存在和 e 相同的数据元素，则插入之相同的
38、数据元素，则插入之 /union算法时间复杂度：算法时间复杂度：O(n2)void purge(List&La,List Lb)/Lb为有序表 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(ListEmpty(La)|!equal(en,e)ListInsert(La,+La_len,e);en=e;/La中不存在和中不存在和 e 相同的数据元素，则插入
39、之相同的数据元素，则插入之算法时间复杂度：算法时间复杂度：O(n)nnnxpxpxppxp.)(2210在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示:P=(p0,p1,，pn)1.1.一元多项式的线性表表示一元多项式的线性表表示但是对于形如但是对于形如 S(x)=1+3x10000 2x20000的多项式，上述表示方法是否合适？的多项式，上述表示方法是否合适？一般情况下的一元稀疏多项式一元稀疏多项式可写成 Pn(x)=p1xe1+p2xe2+pmxem其中其中：pi 是指数为ei 的项的非零系数，0 e1 e2 em=n可以下列线性表表示：（p1,e1）,(p2,e2)
40、,(pm,em)）P999(x)=7x3-2x12-8x999例如例如:可用线性表 (7,3),(-2,12),(-8,999)表示ADT Polynomial 数据对象数据对象：数据关系数据关系：2.抽象数据类型一元多项式的定义如下：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)基
41、本操作基本操作：操作结果操作结果：输入 m 项的系数和指数，建立一元多项式 P。初始条件初始条件：一元多项式 P 已存在。操作结果操作结果：销毁一元多项式 P。初始条件初始条件：一元多项式 P 已存在。操作结果操作结果：打印输出一元多项式 P。PolynLength(P)AddPolyn(&Pa,&Pb)SubtractPolyn(&Pa,&Pb)ADT Polynomial初始条件初始条件：一元多项式 P 已存在。操作结果操作结果：返回一元多项式 P 中的项数。初始条件初始条件：一元多项式 Pa 和 Pb 已存在。操作结果操作结果：完成多项式相加运算，即：Pa=PaPb，并销毁一元多项式 P
42、b。17787178522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxxxA-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 22 7 5 17 3.一元多项式相加实例与规则q-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8
43、ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre-1pa7 0 11 1 22 7 5 17 设设p,q分别指向分别指向A,B中某一结点，中某一结点，p,q初值是第一结点初值是第一结点比较p-exp与q-expp-exp exp:p结点是结果多项式中的一项，p后移,q不动p-exp q-exp:q结点是结果多项式中的一项，将q插在p之前,q后移,p不动p-exp=q-exp:系数相加0：从A表中删去p,释放p,q，p,q后移0：修改p系
44、数域,释放q，p,q后移直到p或q为NULL 若q=NULL，结束 若p=NULL，将B中剩余部分连到A上即可l运算规则4.一元多项式的实现：一元多项式的实现：typedef struct /项项的表示 float coef;/系数系数 int expn;/指数指数 term,ElemType;typedef OrderedLinkList polynomial;/用带表头结点的有序链表表示多项式用带表头结点的有序链表表示多项式结点的数据元素类型定义为:Status CreatPolyn(polynomail&P,int m)/输入输入m项的系数和指数，建立表示一元多项式的有序链表项的系数和指
45、数，建立表示一元多项式的有序链表P/CreatPolynInitList(P);e.coef=0.0;e.expn=-1;SetCurElem(h,e);/设置头结点的数据元素for(i=1;i=m;+i)/依次输入 m 个非零项return OK;scanf(e.coef,e.expn);if(!LocateElem(P,e,(*cmp)()if(!InsAfter(P,e)return ERROR;注意注意:1.输入次序不限输入次序不限;2.指数相同的项只能输入一次。指数相同的项只能输入一次。Status AddPolyn(polynomial&Pc,polynomial&Pa,polyn
46、omial&Pb)/利用两个多项式的结点构成“和多项式”Pc=PaPb if(DelAfter(Pa,e1)a=e1.expn else a=MAXE;if(DelAfter(Pb,e2)b=e2.expn else b=MAXE;while(!(a=MAXE&b=MAXE)/AddPolynswitch(*cmp(e1,e2)case-1:/多项式多项式PA中当前结点的指数值小中当前结点的指数值小 break;case 0:/两者的指数值相等两者的指数值相等 e1.coef=a.coef+b.coef;if(a.coef!=0.0)InsAfter(Pc,e1);break;case 1:/
47、多项式多项式PB中当前结点的指数值小中当前结点的指数值小 break;本章小结本章小结1.1.了解线性表的逻辑结构特性是数据元素之间了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。用后者表示的线性表简称为链表。2.2.熟练掌握这两类存储结构的描述方法，以及熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。线性表的各种基本操
48、作的实现。3.3.能够从时间和空间复杂度的角度综合比较线性能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。表两种存储结构的不同特点及其适用场合。习习 题题 二二1什么是顺序存储结构？什么是链式存储结构？2线性表的顺序存储结构和链式存储结构各有什么特点？3设线性表中数据元素的总数基本不变，并很少进行插入或删除工作，若要以最快的速度存取线性表中的数据元素，应选择线性表的何种存储结构？为什么?4线性表的主要操作有哪些？5简述数组与顺序存储结构线性表的区别和联系。6顺序表和链表在进行插入操作时，有什么不同？7画出下列数据结构的图示：顺序表 单链表 双链表 循环链表8试给出求顺序表长度的算法。9若顺序表A中的数据元素按升序排列，要求将x插入到顺序表中的合适位置，以保证表的有序性，试给出其算法。10试将一个无序的线性表A=(11,16,8,5,14,10,38,23)转换成一个按升序排列的有序线性表（用链表实现）。
