第二章 线性表 2.1 线性表的类型定义 2.2线性表的顺序存储 2.3线性表的链式存储 2.4一元多项式的表示和相加.

Presentation on theme: "第二章 线性表 2.1 线性表的类型定义 2.2线性表的顺序存储 2.3线性表的链式存储 2.4一元多项式的表示和相加."— Presentation transcript:

1 第二章 线性表 2.1 线性表的类型定义 2.2线性表的顺序存储 2.3线性表的链式存储 2.4一元多项式的表示和相加

2 2.1线性表的类型定义 线性表的定义 线性表是n(n>=0)个数据元素的有限序列，表中各个元素具有相同地属性，表中相邻元素间存在“序偶”关系。 记做：(a1,a2,…….ai-1,ai,ai+1,…,an-1,an ) ai-1称为ai 的直接前驱元素，ai+1是ai的直接后继元素 线性表的长度：表中的元素个数 n 位序：i称元素ai在线性表中的位序

3 线性表的ADT定义 }ADT List ADT List{ 数据对象: D={ai|aiElemset,i=1,2…n, n≥0}
数据关系: R={<ai-1,ai>|ai-1,ai  D, i=2,…n} 基本操作: InitList(&L) Destroy(&L) ClearList(&L) ListEmpty(L) ListLength(L) GetElem(L,i,&e) 1<=i<= ListLength (L) LocateItem(L,e,compare()) PriorElem(L,Cur_e,&pre_e) NextElem(L,cur_e,&next_e) ListInsert(&L,i,e) <=i<= ListLength (L)+1 ListDelete(&L,i,&e) 1<=i<= ListLength (L) ListTraverse(L) }ADT List

4 【例】对两个线性表La、Lb表示的集合A和B，求一个新集合A＝AUB
从Lb中取一个元素(重复直至遍历全部Lb元素) 在La中查询 若La中不存在，则将其插入La 【例】对一个非纯集合B，构造一个纯集合A，使A中只包涵B中不同值的成员。同上，只是创建La。 【例】判断两个集合是否相等。构造C＝A 【例】已知线性表La、Lb中数据元素按值非递减排列，现要求将La和Lb归并为一新的线性表Lc,且Lc也非递减排列。

5 2.2线性表的顺序表示和实现 顺序表——线性表的顺序存储表示 #define LIST_INIT_SIZE 100 (C规范)
#define LISTINCREMENT 10 Typedef Struct { Elemtype * elem; int length; int listsize; }SqList;

6 顺序表中基本操作的实现 Ein=Σpi(n-i+1)=n/2 Edl=Σpi(n-i)=(n-1)/2 初始化操作 InitList_Sq
查找元素操作 LocateElem_Sq O(n) 插入元素操作 ListInsert_Sq O(n) 删除元素操作 ListDelete_Sq O(n) 归并操作 MergeList_Sq O(n+m) 插入和删除操作的时间分析： Ein=Σpi(n-i+1)=n/2 Edl=Σpi(n-i)=(n-1)/2 对比算法

7 查找元素操作 时间复杂度O(n)

8 插入元素操作 时间复杂度O(n)

9 删除元素操作 时间复杂度O(n)

10 顺序表其它算法举例* 比较两个顺序表的大小 (逐个比较元素字符) 时间复杂度O(Min(A.length,B.length))
用尽量少得辅助空间将前m个元素和后n个元素互换 exchange1 时间复杂度：O(m×n) invert 时间复杂度：O(t-s+1) exchange2 时间复杂度：O(m+n)

11 2.3线性表的链式表示和实现 2.3.1线性链表（单链表和指针） typedef struct LNode{
数据域（data）和指针域（next） 存储表示 typedef struct LNode{ ElemType data; Struct LNode *next; }LNode, *LinkList;

12 单链表种类 不带头结点单链表 带头结点单链表

13 常见指针操作*

14 单链表的基本操作 求线性表的长度 时间复杂度：O(n)

15 查找元素操作 时间复杂度：O(n)

16 插入结点操作 ：前插、后插 时间复杂度：前插O(n)、后插O(1)

17 删除结点操作 时间复杂度O(n)

18 单链表的其它操作举例 【例】逆序创建链表 时间复杂度O(n)

19 逆置单链表 时间复杂度O(n)*

20 【例】以单链表表示线性表实现集合的并 * void union_L( LinkList &La, LinkList &Lb ) {
if (!La) {La = Lb;return;} while ( Lb ) { s = Lb; Lb = Lb->next; p = La; while ( p && p->data != s ->data ) { //查找 pre = p; p = p->next; }//while if ( p ) delete s; //找到 else { pre->next = s; s->next = NULL;} //插入 }// while }// union_L 时间复杂度O(m×n) 对比算法2.1

21 【算法改进】Lb中元素只需要和原La元素比较*
void union_L( LinkList &La, LinkList &Lb ) { if (!La) La = Lb;return; q=La; while(q->next) q=q->next; //先找到链表La尾部q pre=q; //pre为并操作以后的尾部 while ( Lb ) { s = Lb; Lb = Lb->next; p = La; while ( p !=q->next&& p->data != s ->data )p =p->next; if ( p!=q->next ) delete s; else { pre->next = s; pre=s} }// while(Lb) s->next=NULL; }// union_L

22 数据有序性对链表的影响——有序表* 【例】 两个带头结点的有序单链表La、Lb分别表示集合A、B，求C=AUB? 时间复杂度 O(n)
对比：无序表完成同样功能的时间复杂度为O(n*n)

23 静态链表 #define MAXSIZE 1000 //链表最大长度 Typedef struct { ElemType data;
int cur; }component,SLinkList[MAXSIZE]; int LocateElem_SL(SLinkList S ,ElemType e);//查找元素 int InitSpace_SL(SLinkList &space); //生成备用链表 int Malloc_SL(SLinkList &space); //返回可用下标 int Free_SL(SLinkList &space, int k);//回收k下标节点 求集合(A-B)U(B-A)

24 静态链表实现(A-B)U(B-A) A={c,b,e,g,f,d} B={a,b,n,f} (A-B)(B-A) A 8 2 c 3 b
Space(0：11) 8 1 2 c 3 b 4 e 5 g 6 f 7 d 9 10 11 Space(0：11) 6 1 2 c 4 3 n e 5 g 7 f 9 d 8 a 10 11 (A-B)(B-A) A A={c,b,e,g,f,d} B={a,b,n,f}

25 2.3.2循环链表 什么是循环链表 判断表尾的循环条件： 通常循环链表有头结点 最后一个结点的指针指向头结点 一般设置尾指针，而不设头指针
空的循环链表是头结点指针指向自己 判断表尾的循环条件： 不是p==NULL，而是p是否等于头指针（尾指针）。

26 单循环链表

27 * 【例】 两个带头结点的循环有序链表，表示集合A、B，完成C=A U B 时间复杂度 O(n+m)
在头元素中放最大元素MAX 简化操作 ,时间复杂度 O(n+m), 时间略长，算法表达略简单

28 2.3.3双向链表 概念：两个指针，分别指向前驱和后继， 双向链表一般都是循环带头结点的。 typedef struct DuLNode{
ElemType data; struct DuLNode *prior; struct DuLNode *next; }DuLNode, *DuLinkList;

29 双向循环链表

30 插入结点操作 时间复杂度O(1)

31 删除结点操作 时间复杂度O(1)

32 单链表的实际应用改进 Status MakeNode(Link &p,ElemType e);//分配由p指向值为e的结点
typedef struct LNode{ ElemType data; Struct LNode *next; }*Link, *Position; typedef struct { Link head,tail; int len; }LinkList; Status MakeNode(Link &p,ElemType e);//分配由p指向值为e的结点 void FreeNode(Link &p); //释放由p指向的结点 Status InitList(LinkList &L) //注意这里的L是一个结构体 Status InsFirst(Link h,link s);//h头结点，插在第一位置 … Status ListInsert(LinkList &L,int i,ElemType e); Status MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc);

33 2.4一元多项式的表示和相加 一元多项式Pn(x)=p0+p1x1+p2x2+…+pnxn
用((p0,e0), (p1,e1), …,(pn,en),)表示 ，是线性表 typedef struct{ float coef; //系数 int expn; //指数 }term,ElemType;

34 数据对象: D={ai|aiTermSet,i=1,…m }
ADT Polynomial{ 数据对象: D={ai|aiTermSet,i=1,…m } 数据关系: R={<ai-1,ai>|ai-1D,aiD,ei-1<ei} 基本操作: CreatePolyn(&p,m) AddPolyn(&pa,&pb) 初始条件：一元多项式pa、pb已经存在 操作结果：完成pa=pa+pb SubtractPolyn(&pa,&pb) … … } ADT Polynomial;

35 一元多项式相加链表示意图

36 顺序表和链表的综合比较 线性表的长度能否预先确定？处理过程中变化范围如何？ 对线性表的操作形式如何？ 长度确定、变化小时用顺序表
长度变化大、难以估计最大长度时宜采用链表 对线性表的操作形式如何？ 查询操作多、删除和插入操作少时使用顺序表 频繁插入和删除操作宜采用链表

37 谢谢！

38 void Union(List &La, List Lb) { // 算法2.1
// 将所有在线性表Lb中但不在La中的数据元素插入到La中 int La_len,Lb_len,i; ElemType e; 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)) // La中不存在和e相同的数据元素 ListInsert(La, ++La_len, e); // 插入 } } // union

39 void MergeList(List La, List Lb, List &Lc) { // 算法2.2
// 已知线性表La和Lb中的元素按值非递减排列。归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。 int i= j=1, k=0; InitList(Lc); La_len = ListLength(La); Lb_len = ListLength(Lb); while ((i <= La_len) && (j <= Lb_len)) { // La和Lb均非空 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai <= bj) { ListInsert(Lc, ++k, ai); i; } else { ListInsert(Lc, ++k, bj); ++j; } } while (i <= La_len) { GetElem(La, i++, ai); ListInsert(Lc, ++k, ai); } while (j <= Lb_len) { GetElem(Lb, j++, bj); ListInsert(Lc, ++k, bj);} } // MergeList

40 Status InitList_Sq(SqList &L) { // 算法2.3
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if (!L.elem) return ERROR; // 存储分配失败 L.length = 0; // 空表长度为0 L.listsize = LIST_INIT_SIZE; // 初始存储容量 return OK; } // InitList_Sq

41 Status ListInsert_Sq(SqList &L, int i, ElemType e) { // 算法2.4
// 在顺序线性表L的第i个元素之前插入新的元素e，1≤i≤ListLength_Sq(L)+1 ElemType *p; if (i < 1 || i > L.length+1) return ERROR; // i值不合法 if (L.length >= L.listsize) { // 当前存储空间已满，增加容量 ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType)); if (!newbase) return ERROR; // 存储分配失败 L.elem = newbase; // 新基址 L.listsize += LISTINCREMENT; // 增加存储容量 } ElemType *q = &(L.elem[i-1]); // q为插入位置 for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p; // 元素右移 *q = e; // 插入e ++L.length; // 表长增1 return OK; } // ListInsert_Sq 可以使用 malloc吗

42 Status ListDelete_Sq(SqList &L, int i, ElemType &e) { // 算法2.5
// 在L中删除第i个元素，并用e返回其值。1≤i≤ListLength_Sq(L)。 ElemType *p, *q; if (i<1 || i>L.length) return ERROR; // i值不合法 p = &(L.elem[i-1]); // p为被删除元素的位置 e = *p; // 被删除元素的值赋给e q = L.elem+L.length-1; // 表尾元素的位置 for (++p; p<=q; ++p) *(p-1) = *p; // 被删除元素之后的元素左移 --L.length; // 表长减1 return OK; } // ListDelete_Sq

43 int LocateElem_Sq(SqList L, ElemType e,
Status (*compare)(ElemType, ElemType)) { // 算法2.6 // 在顺序线性表L中查找第1个值与e满足compare()的元素的位序。 // 若找到，则返回其在L中的位序，否则返回0。 int i; ElemType *p; i = 1; // i的初值为第1个元素的位序 p = L.elem; // p的初值为第1个元素的存储位置 while (i <= L.length && !(*compare)(*p++, e)) ++i; if (i <= L.length) return i; else return 0; } // LocateElem_Sq

44 ElemType *pa,*pb,*pc,*pa_last,*pb_last;
void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) { // 算法2.7 // 已知顺序线性表La和Lb的元素按值非递减排列。归并得到新的顺序线性表Lc。 ElemType *pa,*pb,*pc,*pa_last,*pb_last; pa = La.elem; pb = Lb.elem; Lc.listsize = Lc.length = La.length+Lb.length; pc = Lc.elem = (ElemType *)malloc(Lc.listsize*sizeof(ElemType)); if (!Lc.elem) exit(OVERFLOW); // 存储分配失败 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++; // 插入La的剩余元素 while (pb <= pb_last) *pc++ = *pb++; // 插入Lb的剩余元素 } // MergeList

45 void exchang1( SqList &A, int m, int n ) {
// 本算法实现顺序表中前 m 个元素和后 n 个元素的互换 for (k = 1; k<=n; k++ ) { w = A.elem[m+k-1]; for ( j=m+k-1; j>=k; j-- ) A.elem[j] = A.elem[j-1]; A.elem[k-1] = w; } // for } // exchang1 O(m*n)

46 void invert( ElemType &R[]，int s， int t ){
// 本算法将数组 R 中下标自 s 到 t 的元素逆置，即将( Rs, Rs+1, …, Rt-1, Rt ) 改变为( Rt, Rt-1, …, Rs+1, Rs ) for ( k=s; k<=(s+t)/2; k++ ) { w = R[k]; R[k] = R[t-k+s]; R[t-k+s] = w; }//for }// invert void exchange2( SqList &A; int m; int n ) { // 本算法实现顺序表中前 m 个元素和后 n 个元素的互换 invert( A.elem, 0, m+n-1 ); invert( A.elem, 0, n-1 ); invert( A.elem, n, m+n-1 ); } // exchange2

47 int ListLength_L( LinkList L )
p=L->next; k=0; while ( p ) { k++; p=p->next; // k 计非空结点数 }//while return k; } // ListLength_L

48 何时成立？ Status GetElem_L(LinkList &L,int i, ElemType &e) { // 算法2.8
// 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR LinkList p; p = L->next; int j = 1; // 初始化，p指向第一个结点，j为计数器 while (p && j<i) { // 顺指针向后查找直到p指向第i个元素或p为空 p = p->next; ++j; } if ( !p || j>i ) return ERROR; // 第i个元素不存在 e = p->data; // 取第i个元素 return OK; } // GetElem_L 何时成立？

49 Status ListInsert_L(LinkList &L, int i, ElemType e) { // 算法2.9
// 在带头结点的单链线性表L的第i个元素之前插入元素e LinkList p,s; int j = 0; p = L; while (p && j < i-1) { // 寻找第i-1个结点 p = p->next; ++j; } if (!p || j > i-1) return ERROR; // i小于1或者大于表长 s = (LinkList)malloc(sizeof(LNode)); // 生成新结点 s->data = e; s->next = p->next; // 插入L中 p->next = s; return OK; } // LinstInsert_L

50 Status ListDelete_L(LinkList &L, int i, ElemType &e) { // 算法2.10
// 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 LinkList p,q; p = L; int j = 0; while (p->next && j < i-1) { // 寻找第i个结点，并令p指向其前趋 p = p->next; j; } if (!(p->next) || j > i-1) return ERROR; // 删除位置不合理 q = p->next; p->next = q->next; // 删除并释放结点 e = q->data; free(q); return OK; } // ListDelete_L 对比前页 为何不是p？

51 void CreateList_L(LinkList &L, int n) { // 算法2.11
// 逆位序输入n个元素的值，建立带表头结点的单链线性表L LinkList p; int i; L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; // 先建立一个带头结点的单链表 for (i=n; i>0; --i) { p = (LinkList)malloc(sizeof(LNode)); // 生成新结点 scanf(&p->data); // 改为一个随机生成的数字(200以内) p->next = L->next; L->next = p; // 插入到表头 } } // CreateList_L

52 void InvertLinkedList( LinkList &L )
p = L; L = NULL; // 设逆置后的链表的初态为空表 while ( p ) { // p 为待逆置链表的头指针 s = p; p = p->next; // 从 p 所指链表中删除第一个结点(s 结点) s->next = L; L = s; // 将 s 结点插入到逆置表的表头 } } // InvertLinkedList

53 void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {
// 已知单链线性表La和Lb的元素按值非递减排列。 // 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。 LinkList pa, pb, pc; pa=La->next; pb = Lb->next;Lc = pc = La;// Lc的头结点=La头结点 while (pa && pb) { if (pa->data <= pb->data) { pc->next = pa; pc = pa; pa = pa->next; } else { pc->next = pb; pc = pb; pb = pb->next; } } pc->next = pa ? pa : pb; // 插入剩余段 free(Lb); // 释放Lb的头结点 } // MergeList_L

54 int LocateElem_SL(SLinkList S, ElemType e) {// 算法2.13
int i; i = S[0].cur; // i指示表中第一个结点 while (i && S[i].data != e) i = S[i].cur; // 在表中顺链查找 return i; } // LocateElem_SL void InitSpace_SL(SLinkList space) { // 算法2.14 // 将一维数组space中各分量链成一个备用链表 // space[0].cur为头指针, "0"表示空指针 for (int i=0; i<MAXSIZE-1; ++i) space[i].cur = i+1; //前space[0..MAXSIZE-2].cur指向后一个 space[MAXSIZE-1].cur = 0; } // InitSpace_SL

55 int Malloc_SL(SLinkList &space) {
// 若备用空间链表非空，则返回分配的结点下标，否则返回0 int i = space[0].cur; if (space[0].cur) space[0].cur = space[space[0].cur].cur; return i; } // Malloc_SL void Free_SL(SLinkList &space, int k) { // 将下标为k的空闲结点回收到备用链表 space[k].cur = space[0].cur; space[0].cur = k; } // Free_SL

56 P作用？ void difference(SLinkList &space, int &S) {
// 依次输入集合A和B的元素，在一维数组space中建立表示集合(A-B)∪(B-A) 的静态链表, S为头指针。假设备用空间足够大，space[0].cur为头指针。 InitSpace_SL(space); S = Malloc_SL(space); r = S; scanf(m,n); //r指向S最后结点 for (j=1; j<=m; ++j) { i =Malloc_SL(space);scanf(space[i].data);space[r].cur = i; r = i; } space[r].cur = 0; // 尾结点的指针为空 for (j=1; j<=n; ++j) { // 依次输入B的元素,若不在当前表中,则插入,否则删除 scanf(b); p = S; k = space[S].cur; // k指向集合A中第一个结点 while (k!=space[r].cur && space[k].data!=b) { p = k; k = space[k].cur; }//p跟随k if (k == space[r].cur) { // 当前表中不存在该元素,插入在r所指结点之后， i = Malloc_SL(space); space[i].data = b; space[i].cur = space[r].cur; space[r].cur = i; //插在r后第一个元素前 } else {// 该元素已在表中,删除之 space[p].cur = space[k].cur; Free_SL(space, k); if (r == k) r = p; // 若删除的是尾元素，则需修改尾指针 }//else }//for } // difference P作用？

57 void union_OL( LinkList &La，LinkList &Lb ) {
// La 和 Lb 分别为表示集合 A 和 B 的循环链表的头指针，求 C=A∪B，操作 // 完成之后，La为表示集合C 的循环链表的尾指针，集合A和B的链表不再存在 pa = La->next->next; pb = Lb->next->next; rc = La->next; // pa 指向 A 中当前考察的结点,rc 指向 C 当前的表尾 while ( pa!=La->next && pb!=Lb->next ) { if ( pa->data < pb->data ) {rc->next = pa; rc = pa; pa = pa->next; } else if ( pa->data > pb->data ){ rc->next = pb; rc = pb; pb = pb->next; } else { // 链接A的元素，释放B的结点，pa、pb分别指向各自下一元素 rc->next = pa; rc = pa; pa = pa->next; qb = pb; pb = pb->next; delete qb; }//else }//while if ( pb == Lb->next ) rc->next = pa; // 链接 A 的剩余段 else { // 链接 B 的剩余段 rc->next = pb; pb = Lb->next; // pb 指向 B 的头结点 Lb->next = La->next; La = Lb; // 构成 C 的循环链 free(pb); // 释放 B 表的表头 } // union_OL

58 Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) {
// 在带头结点的双链循环线性表L的第i个元素之前插入元素e， // i的合法值为1≤i≤表长+1。 if (!(p = GetElemP_DuL(L, i))) // 在L中确定第i个元素的位置指针p return ERROR; // p=NULL, 即第i个元素不存在 if (!(s = (DuLinkList)malloc(sizeof(DuLNode)))) return ERROR; s->data = e; s->prior = p->prior; p->prior->next = s; s->next = p; p->prior = s; return OK; } // ListInsert_DuL

59 Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e) {
// 删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长 DuLinkList p; if (!(p = GetElemP_DuL(L, i))) // 在L中确定第i个元素位置指针p return ERROR; // p=NULL, 即第i个元素不存在 e = p->data; p->prior->next = p->next; p->next->prior = p->prior; free(p); return OK; } // ListDelete_DuL

60 Status MergeList_L(NLinkList &La, NLinkList &Lb, NLinkList &Lc,
int (*compare)(ElemType, ElemType)) { // 算法2.21 // 已知单链线性表La和Lb的元素按值非递减排列。 // 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。 if (!InitList(Lc)) return ERROR; // 存储空间分配失败 ha = GetHead(La); hb = GetHead(Lb); // ha和hb分别指向La和Lb的头结点 pa = NextPos(La, ha); pb = NextPos(Lb, hb); // pa和pb分别指向La和Lb中当前结点 while (pa && pb) { // La和Lb均非空 a = GetCurElem(pa); b = GetCurElem(pb); if ((*compare)(a, b)<=0) { // a≤b DelFirst(ha, q); Append(Lc, q); pa = NextPos(La, pa); } else {DelFirst(hb, q); Append(Lc, q); pb = NextPos(Lb, pb); } } // while if (pa) Append(Lc, pa); // 链接La中剩余结点 else Append(Lc, pb); // 链接Lb中剩余结点 FreeNode(ha); FreeNode(hb); // 释放La和Lb的头结点 return OK; } // MergeList_L

61 q指向小于e的最大值结点 void CreatPolyn(PLinkList &P, int m) { // 算法2.22
// 输入m项的系数和指数，建立表示一元多项式的有序链表P InitList(P); h = GetHead(P); e.coef = 0.0; e.expn = -1; SetCurElem(h, e); // 设置头结点 for (i=1; i<=m; ++i) { // 依次输入m个非零项 scanf ("%f,%d\n",&e.coef, &e.expn); if (!LocateElem(P, e,q, cmp)) { // 当前链表中不存在该指数项 if (MakeNode(s,e)) InsFirst(q, s); // 生成结点并插入链表 } else i--; // 如果没有产生插入，则将i值减1 } } // CreatPolyn q指向小于e的最大值结点

62 ha表示已处理的最后一个结点？ cmp如何定义？ void AddPolyn(PLinkList &Pa, PLinkList &Pb) {
// 多项式加法：Pa = Pa＋Pb，利用两个多项式的结点构成"和多项式"。 ha = GetHead(Pa); hb = GetHead(Pb); qa = NextPos(Pa,ha); qb = NextPos(Pb,hb); while (qa && qb) { // Pa和Pb均非空 a = GetCurElem (qa); b = GetCurElem (qb);// a和b为两表中当前比较元素 switch (*cmp(a,b)) { case -1: // 多项式PA中当前结点的指数值小 ha = qa; qa = NextPos (Pa, qa); break; case 0: // 两者的指数值相等 sum = a.coef + b.coef ; if (sum != 0.0) { // 修改多项式PA中当前结点的系数值 temp.coef=sum; temp.expn=a.expn; SetCurElem(qa, temp) ; ha = qa;} else {DelFirst(ha, qa); FreeNode(qa); } // 删除多项式PA中当前结点 DelFirst(hb, qb); FreeNode(qb); qb = NextPos(Pb, hb); qa = NextPos(Pa, ha); break; case 1: // 多项式PB中当前结点的指数值小 DelFirst(hb, qb); InsFirst(ha, qb); qb = NextPos(Pb, hb); ha = NextPos(Pa, ha); break; } // switch } // while if (!Empty(Pb)) Append(Pa, qb); FreeNode(hb); } // AddPolyn ha表示已处理的最后一个结点？ cmp如何定义？