第四章数据结构-线性表

1、第三部分第三部分 线性结构线性结构 线性关系线性关系 (Linear Relation)（也称为（也称为线性结构线性结构）是）是指在数据元素的非空有限集中有且仅有一个被称为指在数据元素的非空有限集中有且仅有一个被称为“首元素首元素”的数据元素，有且仅有一个被称为的数据元素，有且仅有一个被称为“尾尾元素元素”的数据元素，其余数据元素均有且仅有一个的数据元素，其余数据元素均有且仅有一个直接直接前驱元素前驱元素，有且仅有一个直接，有且仅有一个直接后继元素后继元素。第四章第四章 线性表线性表目标目标 什么是线性表？什么是线性表？( (即线性表抽象数据类型即线性表抽象数据类型) ) 线性表的存储结构及基

2、本运算的实现线性表的存储结构及基本运算的实现 线性表的应用线性表的应用( (主要是单链表的应用主要是单链表的应用) )3 34.14.1 线性表的类型定义线性表的类型定义一、线性表的类型定义一、线性表的类型定义 线性表线性表是是n (n 0)个具有相同特性的数据个具有相同特性的数据元素的有限序列。记作：元素的有限序列。记作： （a1, a2, , ai-1, ai, ai+1, , an） 其中，相邻的数据元素之间存在其中，相邻的数据元素之间存在序偶序偶的关的关系，即系，即ai-1领先于领先于ai, ai领先于领先于ai+1(i=1,2,n-1), 称称 ai-1是是ai的的直接前驱元素直接前

3、驱元素，ai+1是是 ai 的的直接后直接后继元素继元素。 a1, a2, ai-1均称为均称为ai的的前驱元素前驱元素；ai+1, ai+2, an均称为均称为ai的的后继元素后继元素4 4二、相关定义二、相关定义 线性表的长度：线性表的长度：线性表所含的数据元素个数线性表所含的数据元素个数 n 称称为线性表的长度（为线性表的长度（the length of list）。）。 空线性表：空线性表：把长度为零的线性表（即不包含任何把长度为零的线性表（即不包含任何数据元素的线性表）称为空线性表（数据元素的线性表）称为空线性表（empty list），），简称简称空表空表。 位序：位序：我们说我们

4、说a1是线性表是线性表L的第的第1个数据元素，个数据元素，ai是是线性表线性表L的第的第i个数据元素，个数据元素，an是线性表的第是线性表的第n个数个数据元素，这里的据元素，这里的1、2、i和和n分别称为分别称为a1、a2、ai和和an在在L中的位序（中的位序（Position Number in List）。）。5 5三、线性表的几个基本运算三、线性表的几个基本运算 InitListInitList (&L) (&L) 初始化初始化运算运算 ListEmptyListEmpty (L) (L) 判空判空运算运算 ListFullListFull(L) (L) 判满判满运算运算

5、 CreateListCreateList(L) (L) 创建创建运算运算 ListLengthListLength (L) (L) 求长度求长度运算运算 LocateElemLocateElem (L, e) (L, e) 定位定位运算或称为运算或称为查找查找运算运算 ListInsertListInsert (&L, (&L, i i, e) , e) 插入插入运算运算 ListDeleteListDelete (&L, (&L, i i, &e) , &e) 删除删除运算运算 VisitListVisitList(L, (L, i i, &

6、amp;e) , &e) 访问访问运算运算6 64.24.2 线性表的顺序存储表示线性表的顺序存储表示1 1、顺序表、顺序表 线性表的顺序存储结构线性表的顺序存储结构即用即用一组地址连续的一组地址连续的存储存储单元来单元来依次依次存放线性表中的数据元素。即用地址上的存放线性表中的数据元素。即用地址上的相邻关系来表示数据元素逻辑上的相邻关系。采用顺相邻关系来表示数据元素逻辑上的相邻关系。采用顺序存储的线性表简称为序存储的线性表简称为顺序表顺序表(Sequential List)。 a1 a2 ai-1 ai an线性表的起始地址线性表的起始地址称作线性表的称作线性表的基地址基地址nimi

7、jaLocaLocnimiaLocaLocnimaLocaLocijiii,.,3 , 2,)()()(,.,3 , 2,) 1()()(,.,3 , 2,)()(11 用用Loc(Loc(a ai)i)表示数据元素表示数据元素a ai i的存储地址的存储地址，并假，并假设设每个数据元素占每个数据元素占m m个存储单元个存储单元，则有，则有: :a1a2a3anbb+mb+2mb+(n-1)*m姓名1地址1电话1姓名2地址2电话2.姓名n地址n电话nbb+lb+(n-1)*lx“姓名姓名”需要占用的存储单元需要占用的存储单元y“地址地址”需要占用的存储单元需要占用的存储单元Locn(i)=b+

8、(i-1)*l+xLocp(i)=b+(i-1)*l+x+y第第i个元素的个元素的“地址地址”项项的存储地址：的存储地址：第第i个元素的个元素的“电话电话”项项的存储地址：的存储地址：例：例：89 92 2、顺序表类型定义、顺序表类型定义静态存储分配静态存储分配 #define MAX 100 typedef struct ElemType dataMAX; int len; sqlist;动态存储分配动态存储分配 typedef struct ElemType *data; int len; int listsize; sqlist_d;1010例如例如 线性表线性表L (a1, a2, a

9、3, a4, a5, a6) 的顺序存储结构图如的顺序存储结构图如下：下：sqlist L;a1a2a3a4a5a6012345 MAX-1L.len6文本L.dataa1a2a3a4a5a6012345 MAX-1L.len6文本L.data611113 3、顺序表中基本运算的实现及算法分析、顺序表中基本运算的实现及算法分析l初始化操作初始化操作 InitListInitListl查找元素操作查找元素操作 LocateElemLocateEleml插入元素操作插入元素操作 ListInsertListInsertl删除元素操作删除元素操作 ListDeleteListDelete1212l

10、初始化初始化操作操作 InitList_sq算法算法4.1 int InitList_sq(SqList *L)(*L).len = 0;return 0; /表示初始化成功表示初始化成功O(1)静态存储分配方式下实现上述基本运算静态存储分配方式下实现上述基本运算1313l 查找元素查找元素操作操作 LocateElem_sq算法算法4.7int LocateElem_sq(SqList L, ElemType e) int i; if(1 = ListEmpty_sq(L) return 0; /查找失败查找失败 for(i = 0; i L.len & L.datai != e;

11、i+); if(i L.len) return i + 1; /查找成功返回数据元素的位序查找成功返回数据元素的位序 return 0; /查找失败查找失败O(n)1414l 插入元素插入元素操作操作 ListInsert_sq在在顺序表顺序表指定位置指定位置插入一个插入一个数据元素数据元素的的过程过程：StepStep1 1 将原来第将原来第i i个位置上的元素至最后一个个位置上的元素至最后一个元素统统向后平移一位（假设顺序表在插入前没元素统统向后平移一位（假设顺序表在插入前没有满），这样做既可以保证被平移的这些元素之有满），这样做既可以保证被平移的这些元素之间和没被平移的元素之间的逻辑关系

12、不被破坏间和没被平移的元素之间的逻辑关系不被破坏（它们的物理位置仍相邻），同时又将第（它们的物理位置仍相邻），同时又将第i i个位个位置空出来；置空出来；StepStep2 2 将待插入元素插入到第将待插入元素插入到第i i个位置上；个位置上；StepStep3 3 线性表长度加线性表长度加1 1。1515例：例：在下图所示在下图所示顺序表顺序表的的第第4 4个位置上插入一个新个位置上插入一个新的数据元素的数据元素5 50 0。湖北工业大学计算机学院湖北工业大学计算机学院 沈华沈华1616算法算法4.8int ListInsert_sq(SqList *L, int i, ElemType e

13、) int j; if(i (*L).len + 1) return -1; if(1 = ListFull_sq(*L) return -2; for(j = (*L).len; j = i; j-) (*L).dataj = (*L).dataj-1; (*L).datai-1 = e; (*L).len+; return 0; 1717时间复杂度分析时间复杂度分析u最好情况最好情况：在第在第n n+1+1个位置上插入一个新元素，个位置上插入一个新元素，时间开销为时间开销为O O(1)(1)；u最坏情况最坏情况：第第1 1个位置上插入一个新元素，时个位置上插入一个新元素，时间开销为间开销为

14、O O( (n n) )；u平均情况平均情况：用用p pi i表示在第表示在第i i个位置上插入的可能个位置上插入的可能性，用性，用l li i表示需要向后移动的数据元素个数。假表示需要向后移动的数据元素个数。假设是在等概率的情况下进行分析，那么有：设是在等概率的情况下进行分析，那么有：1111111(1)(1)(1)1)11122nniiiin nnplninnnnn 故在平均情况下的时间复杂度为故在平均情况下的时间复杂度为O O( (n n) )。1818l 删除元素操作删除元素操作 ListDelete_sq删除删除顺序表顺序表指定位置上指定位置上数据元素数据元素的的过程过程：StepS

15、tep1 1 记录下将要被删除的第记录下将要被删除的第i i个元素的值；个元素的值；StepStep2 2 将原来第将原来第i i + 1 + 1个位置上的元素至最后一个位置上的元素至最后一个元素统统向前平移一位（假设顺序表在删除前不个元素统统向前平移一位（假设顺序表在删除前不空），这样做既可以保证被平移的这些元素之间和空），这样做既可以保证被平移的这些元素之间和没被平移的元素之间的逻辑关系不被破坏（它们的没被平移的元素之间的逻辑关系不被破坏（它们的物理位置仍相邻），同时又存储了新的逻辑关系物理位置仍相邻），同时又存储了新的逻辑关系（即使得（即使得a ai-1i-1和和a ai+1i+1的存储

16、位置相邻）的存储位置相邻）；StepStep3 3 线性表长度线性表长度减减1 1；Step4 Step4 返回被删除的数据元素的值返回被删除的数据元素的值。1919例例：删除删除下图所示下图所示顺序表第顺序表第4 4个位置上的数据元素个位置上的数据元素。2020算法算法4.10int ListDelete_sq(SqList *L, int i, ElemType *e) int j; if(i (*L).len) return -1; if(1 = ListEmpty_sq(*L) return -2; *e = (*L).datai - 1; for(j = i + 1; j next

17、= NULL; return 0; /初始化成功初始化成功O(1)3232l 单链表的创建单链表的创建 CreateList_link头部创建法思路：头部创建法思路：逆位序输入逆位序输入 n n 个数据元素的值，个数据元素的值，建立带头结点的单链表。建立带头结点的单链表。算法思路：算法思路： a a 建立一个建立一个“空表空表”； b b 输入数据元素输入数据元素a an n，建立结点，建立结点并插入；并插入； c c 输入数据元素输入数据元素a an-1n-1，建立结点，建立结点并插入；并插入； d d 依次类推，直至输入依次类推，直至输入a a1 1为止。为止。ananan-1算法算法 4

18、.15 (创建创建带头结点带头结点的单链表的单链表)-头部创建法头部创建法int CreateList_link_head(LinkList head, int n) int i; LNode *p = NULL; ElemType temp; if(n = 1; i-) p = (LNode *)malloc(sizeof(LNode); if(NULL = p) return -2; printf(“please input no.%d datas value:n”, i); scanf(“%d”, &temp); p - data = temp; p - next = head

19、- next; head - next = p; return 0; O(n)思考：思考：怎样实现从怎样实现从表头到表尾正向创表头到表尾正向创建单链表算法？建单链表算法？湖北工业大学计算机学院湖北工业大学计算机学院 沈华沈华3434算法算法 4.17 (创建创建带头结点带头结点的单链表的单链表)-尾部创建法尾部创建法int CreateList_link_tail(LinkList head, int n) int i; ElemType temp; LNode *p = NULL, *q = head; if(n = 0) return -1; for(i = 1; i data = tem

20、p; p - next = NULL; q - next = p; q = p; return 0; O(n)3535l 查找元素查找元素操作操作 LocateElem_link算法算法 4.20 (基于基于带头结点带头结点的单链表的单链表)int LocateElem_link(LinkList head, ElemType e) int count = 1; LNode *p = head - next; while(NULL != p & p - data != e) p = p - next; count +; if(NULL = p) return 0; return cou

21、nt;O(n)36pabxqq-next=p-next;p-next=q;逻辑关系变化图逻辑关系变化图l 插入元素插入元素操作操作 ListInsert_link在合法的第在合法的第i个位置上插入一个新结点个位置上插入一个新结点的的基本基本处理过程如下（在处理过程如下（在i合法的情况下）：合法的情况下）： 查找到第查找到第i 1个结点；个结点； 生成新数据元素对应的结点，并将其值存生成新数据元素对应的结点，并将其值存入结点的入结点的data域；域； 在第在第i个位置上插入新结点。个位置上插入新结点。3737算法算法 4.21 (基于基于带头结点带头结点的单链表的单链表)int ListInse

22、rt_link(LinkList head, int i, ElemType e) int count = 0; LNode *p = head, *q = NULL; while(count next; count+; if(count i 1 | NULL = p) return -1; q = (LNode *)malloc(sizeof(LNode); if(NULL = q) return -2; q - data = e; q - next = p-next; p - next = q; retrun 0; O(n)3838l 删除元素删除元素操作操作 ListDelete_lin

23、k删除第删除第i个个数据元素数据元素的的基本处理过程如下（在基本处理过程如下（在i合法的情况下）：合法的情况下）： 查找到第查找到第i 1个结点（注意，查找的过程个结点（注意，查找的过程中，还要保证供删除的第中，还要保证供删除的第i个结点存在）；个结点存在）； 记录将被删除的数据元素的值记录将被删除的数据元素的值； 删除第删除第i个结点。个结点。3939算法算法 4.23 (基于基于带头结点带头结点的单链表的单链表)int ListDelete_link(LinkList head, int i, ElemType *e) int count = 0; LNode *p = head, *q

24、= NULL; if(1 = ListEmpty_link(head) return -1; while(count next) p = p - next; count+; if(count i 1 | NULL = p - next) return -2; q = p - next; *e = q - data; p - next = q - next; free(q); retrun 0; O(n)总结：总结： 虽然在单链表中插入或删除元素时无须移动虽然在单链表中插入或删除元素时无须移动元素，但为寻查第元素，但为寻查第i i个元素，需执行个元素，需执行GETElem_lGETElem_l运

25、运算。因此上述两个运算的时间复杂度均为算。因此上述两个运算的时间复杂度均为O(n)O(n)。单链表的单链表的优点优点：插入删除元素无须移动数据插入删除元素无须移动数据单链表的单链表的缺点缺点：不能随机存取，浪费存储空间不能随机存取，浪费存储空间4041414.4 4.4 线性表的其他链式存储结构线性表的其他链式存储结构l 静态链表静态链表l 双向链表双向链表l 循环链表循环链表例如：例如：设有一个包含设有一个包含4个元素（个元素（A,B,D,E）的线性表，其）的线性表，其链式结构和静态链式结构的存储状态。链式结构和静态链式结构的存储状态。A A20122012E EnullnullB B201

26、62016D D20042004(a)链式存储状态链式存储状态 head20002005201020202015data next1 1A A3 3E E-1-1B B4 4D D2 2 12354data cur 0(b)静态链式存储状态静态链式存储状态42静态链表静态链表-用一维数组描述单链表用一维数组描述单链表 本本教材教材将将下标下标为为0 0的数组单元的数组单元处处理为不存放任何数理为不存放任何数据元素，因此可以据元素，因此可以把它看作是静态单把它看作是静态单链表的链表的头结点头结点，是，是整个静态单链表的整个静态单链表的入口。入口。用用-1-1表示空表示空指针指针NULLNULL。

27、4343 在静态单链表中，为在静态单链表中，为了便于为新进入静态单链了便于为新进入静态单链表的数据元素分配所需的表的数据元素分配所需的存储空间，必须时刻了解存储空间，必须时刻了解一维数组中一维数组中空闲数组单元空闲数组单元的情况，也就是说，需要的情况，也就是说，需要时刻维护一个由时刻维护一个由空闲数组空闲数组单元构成的静态单链表单元构成的静态单链表。01324568791a1a3a2a4a52435-167-1free_h1A3E0B4D2 12354data cur 0插入插入元素元素C：C45特点：特点：插入删除无需移动数据元素，节省存储空间；插入删除无需移动数据元素，节省存储空间；但仍存

28、在存储空间难以扩容，不能随机存取的问题。但仍存在存储空间难以扩容，不能随机存取的问题。算法描述：算法描述：P39-41free_hfree_h结点表示结点表示:datadataindicatorindicatordata数据域，数据域，存放数据元素存放数据元素indicator指向后继元素的数组下标指向后继元素的数组下标类型描述类型描述:#define MAX 100typedef structElemType data;int indicator;SLNode;typedef structSLNode storeMAX; int free_h;SeqLinkList;4646双向链表双向链表

29、 在单链表的每个结点里再增加一个指向其直在单链表的每个结点里再增加一个指向其直接前趋的指针域接前趋的指针域priorprior。这样就形成了链表中有两。这样就形成了链表中有两个方向不同的链，故称为个方向不同的链，故称为双向链表双向链表。nextdataprior数据域数据域datadata: :用来存放数据元素的值。用来存放数据元素的值。指针域指针域( (也称为链域也称为链域)prior)prior: :用来存放数据元素直接用来存放数据元素直接前趋的存储位置。前趋的存储位置。指针域指针域( (也称为链域也称为链域)next)next: :用来存放数据元素直接用来存放数据元素直接后继的存储位置。

30、后继的存储位置。 结点表示结点表示:4747heada2a1anheada2a1anhead或或空双向链表图示：空双向链表图示：非空双向链表图示：非空双向链表图示：双向链表的类型定义双向链表的类型定义 typedef struct DNode ElemType data; struct DNode *prior, *next; DNode, *DulLinkList;注意：注意：第第i-1个结点个结点的右指针和第的右指针和第i+1个个结点的左指针都指向结点的左指针都指向第第i个结点。个结点。4848双向链表中双向链表中插入运算插入运算 I. 在在p结点的后面插入结点的后面插入q结点结点q -

31、next = p - next;q - prior = p;p - next - prior = q; /或者为或者为q - next - prior = q;p - next = q; /或者为或者为q - prior - next = q;4949II. 在在p结点的前面插入结点的前面插入q结点结点q - next = p;q - prior = p - prior;p - prior - next = q; /或者为或者为q - prior - next = q;p - prior = q; /或者为或者为q - next - prior = q;5050双向链表中双向链表中删除运算删除

32、运算p - prior - next = p - next;p - next - prior = p - prior;free(p);5151循环链表循环链表-一种头尾相接的链表一种头尾相接的链表一、单向循环链表（单链环）一、单向循环链表（单链环） 在单链表中，将尾元结点的指针域在单链表中，将尾元结点的指针域NULL改改为指向头结点为指向头结点(在带头结点的单链表中在带头结点的单链表中)或首元结或首元结点点(在不带头结点的单链表中在不带头结点的单链表中)，就得到了，就得到了单向循单向循环链表环链表，并简称为，并简称为单链环单链环。5252 I 空单链环空单链环 II 仅带头指针的非空单链环仅带

33、头指针的非空单链环 III 仅带尾指针的非空单链环仅带尾指针的非空单链环headanheada1antaila15353循环链表和单链表的差别循环链表和单链表的差别 判别链表中最后一个结点的条件不同：判别链表中最后一个结点的条件不同：单链表单链表 p-next=NULLp-next=NULL循环链表循环链表 p-next=Headp-next=Head5454二、双向循环链表二、双向循环链表 在双向链表中，将头结点和尾元结点链接起来在双向链表中，将头结点和尾元结点链接起来就构成了就构成了双向循环链表双向循环链表，简称为，简称为双链环双链环。heada2a1anhead I 空双链环空双链环 I

34、I 非空双链环非空双链环5555顺序表和链表的比较顺序表和链表的比较当当线性表的长度变化较大线性表的长度变化较大，频繁进行插入删除操，频繁进行插入删除操作，难以估计其存储规模时作，难以估计其存储规模时 采用采用链表链表作为存储结构为好（若表的插入和删作为存储结构为好（若表的插入和删除主要除主要发生在表的首尾两端，发生在表的首尾两端，采用采用单链环尾指单链环尾指针表示针表示为宜）为宜） 。当当线性表的长度变化不大线性表的长度变化不大，操作主要是进行查找操作主要是进行查找，很少做插入和删除操作，为了节约存储空间很少做插入和删除操作，为了节约存储空间 采用采用顺序表顺序表作为存储结构。作为存储结构。

35、4.5 4.5 一元多项式的表示和相加一元多项式的表示和相加1 1、一元多项式表示、一元多项式表示 A(x)=aA(x)=am mx xe em m+a+am-1m-1x xe em-1m-1+ +.+a.+a1 1x xe e1 1 其中其中,a,ai i是指数为是指数为e ei i项的非零系数项的非零系数, ,而而e ei i(0=ei=n)(0=ei=n)满足满足0=e0=e1 1ee2 2eem m=n=n。问题：问题：采用那种存储形式？采用那种存储形式？方案一：采用顺序存储方案一：采用顺序存储以系数作为一个数据元素，用一组数组依次存以系数作为一个数据元素，用一组数组依次存放放eiei

36、从从0 0的数据元素。的数据元素。优点：优点：做多项式相加操作简单。做多项式相加操作简单。缺点：缺点：当较大时可能非常浪费存储空间。当较大时可能非常浪费存储空间。例：例： A(x) = 1 + 3x10000 2x20000改进：改进：按指数从低到高依次存储元素按指数从低到高依次存储元素(ai(ai，ei)ei)问题：问题：对于多项式的读操作用此存储方便，但对于多对于多项式的读操作用此存储方便，但对于多项式相加、相减操作修改系数指数需移动元素项式相加、相减操作修改系数指数需移动元素方案二：方案二：采用链式存储采用链式存储将每一个系数非零项用一个结点表示。将每一个系数非零项用一个结点表示。结点形

37、式：结点形式：其中，其中，coefcoef代表代表系数域系数域，expexp代表代表指数域指数域，nextnext代代表表指针域指针域。例如例如：A(x)=3xA(x)=3x1414+2x+2x8 8+1+12 81 0 3 14ahcoefcoef expexpnextnext例如例如：加法操作的实现：设有两个多项式：加法操作的实现：设有两个多项式 A(x)=5xA(x)=5x1717+9x+9x8 8+3x+7+3x+7 B(x)=-9x B(x)=-9x8 8+22x+22x7 7+8x+8x可用两个不带表头结点的单链表表示如下：可用两个不带表头结点的单链表表示如下：9 9 8 83 3

38、 1 15 5 1717ah22227 78 8 1 1 9 9 8 8bh7 7 0 0 相加的运算规则：相加的运算规则： 指数相同项相加若和不为零，则构成指数相同项相加若和不为零，则构成“和和多项式多项式”中的一项，所有指数不相同的项均复抄到中的一项，所有指数不相同的项均复抄到“和多项式和多项式”中。中。相加结果为：相加结果为：C(X)=5x17+22x7+11x+722227 711111 15 51717ah7 70 0 2 2、存储结构描述、存储结构描述 typedef struct termtypedef struct term float coef; float coef; in

39、t exp; int exp; struct term struct term * * next; next; term, term, * * polynom; polynom;3 3、算法实现、算法实现方法一：方法一：使用使用papa和和pbpb指针分别沿着两个链表向表尾移动，以指指针分别沿着两个链表向表尾移动，以指示当前被检测的结点。当示当前被检测的结点。当paNULLpaNULL且且pbNULLpbNULL时，可能出现时，可能出现种情况：种情况：(1)pa-exppb-exp：将将pa所指结点的数据域写入一所指结点的数据域写入一个新的结点，并将新结点插入到个新的结点，并将新结点插入到ch

40、链表尾，链表尾，pa指针移向指针移向下一个元素。下一个元素。(2) pa-exp=pb-exp：将将pa和和pb所指结点的系数相加，所指结点的系数相加，若结果不为零则产生一个新结点，将系数和结果写入数若结果不为零则产生一个新结点，将系数和结果写入数据域，并插入到据域，并插入到ch链表尾。链表尾。pa和和pb指针都移向下一个元指针都移向下一个元素。素。(3) pa-expexp：将将pb所指结点的数据域写入一所指结点的数据域写入一个新的结点，并将新结点插入到个新的结点，并将新结点插入到ch链表尾，链表尾，pb指针移向指针移向下一个元素。下一个元素。相加过程演示：直到直到qa或或qb为为NULL若

41、若qa=NULL，将将B中剩余部分中剩余部分复制复制C上即可上即可若若qb=NULL，将将A中剩余部分中剩余部分复制复制C上即可上即可9831517ah22781-98bh70papapapapbpbpbchpc22711151770pcpcpcpcpb=NULLpa=NULL算法实现：算法实现：/ /* *建立以系数为建立以系数为c,c,指数为指数为e e的新结点的新结点, ,并把它插在并把它插在pcpc所指结点的后面所指结点的后面. .链表后链表后pcpc指向新链入的结点指向新链入的结点* */ /void attach(float c, int e, polynom void attac

42、h(float c, int e, polynom * *pc)pc) term term * *s;s; s=new term; s=new term; s-coef=c; s-coef=c; s-exp=e; s-exp=e; ( (* *pc)-next=s;pc)-next=s; * *pc=s;pc=s; / /* *以以ahah和和bhbh为头指针的单链表分别表示多项式为头指针的单链表分别表示多项式A(x)A(x)和和B(x),chB(x),ch为为表示表示A(x)A(x)与与B(x)B(x)和的多项式和的多项式C(x)C(x)的链表头指针。为便于复算，的链表头指针。为便于复算，本

43、算法不破坏本算法不破坏A(x)A(x)与与B(X),C(x)B(X),C(x)另辟空间。多项式另辟空间。多项式A(x)A(x)和和B(x)B(x)均无表头结点均无表头结点* */ /void PolyAdd1(polynom ah, polynom bh, polynom &ch)void PolyAdd1(polynom ah, polynom bh, polynom &ch) polynom pa,pb,pc,q; polynom pa,pb,pc,q; float x; int k; float x; int k; pa=ah; pb=bh; ch=new term; p

44、c=ch; pa=ah; pb=bh; ch=new term; pc=ch; while(pa!=NULL & pb!=NULL) while(pa!=NULL & pb!=NULL) if(pa-exppb-exp) k=1; if(pa-exppb-exp) k=1; else if(pa-exp=pb-exp) k=2; else if(pa-exp=pb-exp) k=2; else k=3; else k=3; switch(k) switch(k) case 1:attach(pa-coef, pa-exp, &pc); case 1:attach(pa-

45、coef, pa-exp, &pc); pa=pa-next;break; pa=pa-next;break; case 2:x=pa-coef+pb-coef; case 2:x=pa-coef+pb-coef; if(x!=0) attach(x, pa-exp, &pc); if(x!=0) attach(x, pa-exp, &pc); pa=pa-next;pb=pb-next;break; pa=pa-next;pb=pb-next;break; case 3:attach(pb-coef, pb-exp, &pc); case 3:attach(pb-coef, pb-exp, &pc); pb=pb-next; pb=pb-next; while(pb!=NULL)while(pb!=NULL) attach(pb-coef, pb-exp, &pc); pb=pb-next;attach(pb-coef, pb-exp, &pc); pb=pb-next; while(pa!=NULL) while(pa!=