制作：崔广才 www.cms.cust.edu.cn.

Presentation on theme: "制作：崔广才 www.cms.cust.edu.cn."— Presentation transcript:

1 制作：崔广才

2 第二章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表
第二章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 线性链表 循环链表 双向链表 2.4 一元多项式的表示及相加

3 2.1 线性表的类型定义 线性表(Linear List) ： 由n(n0)个数据元素(结点)a1,a2,…,an组成的有限序列.
常常将非空的线性表(n>0)记作：(a1,a2,…,ai,…,an) 这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。 同一个线性表中的元素必须属于同一种数据类型. 例1、26个大写英文字母组成的字母表 （‘A’,‘B’,…, ‘Z’） 例2、某校从1978年到1983年各种型号的计算机拥有量的变 化情况。 （6，17，28，50，92，188）

4 2.1 线性表的类型定义 （2，3，4，…，J，Q，K，A） 例3、学生健康情况登记表如下： 例4、一副扑克的点数 姓 名 学 号 性 别
姓 名 学 号 性 别 年龄 健康情况 王小林 790631 男 18 健康 陈 红 790632 女 20 一般 刘建平 790633 21 张立立 790634 17 神经衰弱 …….. ……. 例4、一副扑克的点数 （2，3，4，…，J，Q，K，A）

5 2.1 线性表的类型定义 线性表的逻辑特征： 线性表的逻辑结构是一种典型的线性结构。 1)在非空的线性表，有且仅有一个开始结点a1，它没
2)有且仅有一个终端结点an，它没有直接后继，而仅 有一个直接前趋an-1； 3)其余的内部结点ai(2in-1)都有且仅有一个直接 前趋a i-1和一个直接后继ai+1。 线性表的逻辑结构是一种典型的线性结构。

6 2.1 线性表的类型定义 抽象数据类型线性表的定义如下： ADT List { 数据对象：
D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } //称 n 为线性表的表长; //称 n=0 时的线性表为空表。 数据关系： R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n } //设线性表为 (a1，a2, ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序。

7 基本操作： InitList( &L ) 操作结果： 构造一个空的线性表L DestroyList( &L ) 初始条件： 操作结果：
ClearList( &L ) 初始条件： 操作结果： 线性表L已存在 将L重置为空表 （线性表置空）

8 基本操作： ListEmpty( L ) （线性表判空） 初始条件： 线性表L已存在。 操作结果： 若L为空表，则返回TRUE，否则LSE。
ListLength( L ) 返回L中元素个数。 （求线性表的长度） GetElem( L, i, &e ) （求线性表中某个数据元素） 初始条件： 操作结果： 线性表L已存在，且 1≤i≤ListLength(L) 用e 返回L中第 i 个元素的值。

9 基本操作： PriorElem( L, cur_e, &pre_e ) 初始条件： 操作结果： 线性表L已存在。
若cur_e是L的元素，但不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。 （求数据元素的前驱） LocateElem( L, e, compare( ) ) （定位函数） 线性表L已存在，e为给定值，compare( )是元素判定函数。 返回L中第1个与e满足关系compare( )的元素的位序。若这样的元素不存在，则返回值为0。

10 基本操作： NextElem( L, cur_e, &next_e ) （求数据元素的后继） 初始条件： 操作结果： 线性表L已存在。
若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。 ListInsert( &L, i, e ) （插入数据元素） 初始条件： 操作结果： 线性表L已存在， 且 1≤i≤LengthList(L)+1 在L的第i个元素上插入新的元素e, L的长度增1。

11 基本操作： ListDelete(&L, i, &e) （删除数据元素） 初始条件：
操作结果： 线性表L已存在且非空， 1≤i≤LengthList(L) 删除L的第i个元素，并用e返回其值，L的长度减1。

12 } ADT List 基本操作： ListTraverse(L, Visit( )) （遍历线性表）
初始条件： 操作结果： 线性表L已存在。Visit() 为某个访问函数。 依次对L的每个元素调用函数Visit( )。一旦visit( )失败，则操作失败。 } ADT List

13 利用上述定义的线性表,可以实现其它复杂的操作
例 2-1 假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。 现要求生成一个新的集合A＝A∪B。 上述问题可演绎为： 要求对线性表作如下操作： 扩大线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。

14 算法2.1 void union(List &La，List Lb) { //将所有在线性表Lb中但不在La中的数据元素插入到La中
La-len=ListLength(La); Lb-len=ListLength(Lb); for(i=1;i<=Lb-len;i++) { GetElem(Lb, i, e); if(!LocateElem(La, e, equal)) ListInsert(La, ++La-len, e); } }//在逻辑结构上的算法实现 算法2.1

15 2．分别从 LA和LB中取得当前元素 ai 和 bj；
现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按 值非递减有序排列。 如 LA=（3, 5, 8, 11） LB=（2, 6, 8, 9, 11, 15, 20） 则LC=（2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20) 算法思想： 1．初始化 LC 为空表； 2．分别从 LA和LB中取得当前元素 ai 和 bj； 3．若 ai≤bj，则将 ai 插入到 LC 中，否则将bj 插入到 LC 中； 4．重复 2 和 3 两步，直至 LA 或 LB 中元素被取完为止； 5．将 LA 表或 LB 表中剩余元素复制插入到LC 表中。

16 void mergelist (List La，List Lb，List &lc){
//已知线性表La和Lb中的数据元素按值非递减排序, //归并La和Lb得到新的线性表Lc,Lc的数据元素也按非递减排序 InitList(lc); i=j=1;k=0; la_len=ListLength(la); lb_len=ListLength(lb); while((i<=la_len)&&(j<=lb_len)){ GetElem(la，i，ai); GetElem(lb，j，bj); if(ai <= bj){ ListInsert(lc，++k，ai); ++i; } else{ ListInsert(lc，++k，bj); ++j; } }//end while

17 while(i<=la-len){ GetElem(la，i++， ai); ListInsert(lc，++k， ai);
while(j<=lb-len){ GetElem(lb，j++， bj); ListInsert(lc，++k， bj); } }//end mergelist 算法2.2

18 2.2 线性表的顺序表示和实现 线性表的起始地址， 称作线性表的基地址 一、顺序表
把线性表的元素按逻辑顺序依次存放在一组地址连续的存储单元里,用这种方法存储的线性表简称顺序表。 a1 a2 … ai-1 ai … an 线性表的起始地址， 称作线性表的基地址

19 2.2 线性表的顺序表示和实现 以“存储位置相邻”表示有序对<ai-1，ai>
即：LOC(ai) = LOC(ai-1) + L 一个数据元素所占存储量 所有数据元素的存储位置均取决于 第一个数据元素的存储位置 LOC(ai) =LOC(a1) + (i-1)×L ↑基地址

20 2.2 线性表的顺序表示和实现 #define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量 #define LISTINCREMENT 10 typedef struct{ ElemType *elem; // 存储空间基址 int length; // 当前数据元素的个数(即线性表的长度) int listsize; // 当前分配的存储容量 // (以sizeof(ElemType)为单位) } Sqlist;

21 2.2 线性表的顺序表示和实现 二、顺序表上实现的基本操作 注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist
类型的顺序表，则表中第i个元素是L.elem[i-1]。 1、初始化 Status InitList_sq(SqList &L){ L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; }//end of InitList_sq 算法时间复杂度： O(1)

22 2.2 线性表的顺序表示和实现 p p p p … 0 1 2 3 4 5 6 … LIST-INIT-SIZE-1 L.elem
… p p p p L.length= L.listsize= LIST-INIT-SIZE

23 … an a1 a2 … ai-1 ai … an a1 a2 … ai-1 ai e 2.2 线性表的顺序表示和实现
2、插入算法 线性表的插入操作是指在表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素x，使长度为n的线性表. (a1, …, ai-1, ai, …, an) 改变为(a1, …, ai-1, e, ai, …, an) <ai-1, ai> <ai-1, e>, <e, ai> a1 a2 … ai-1 ai … an a1 a2 … ai-1 ai … an e 表的长度增加

24 Status ListInsert_Sq(SqList &L, int i, ElemType e) {
// 在顺序表L的第 i 个元素上插入新的元素e If(i<1||i>L.Length+1) return ERROR; 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; }//end if q = &(L.elem[i-1]); // q 指示插入位置 for (p = &(L.elem[L.length-1]); p >= q; --p) *(p+1) = *p; // 插入位置及之后的元素右移 *q = e; ++L.length; // 表长增1 return OK; } // ListInsert_Sq 算法时间复杂度为: O( L.length )

25 void *realloc(ptr, newsize)功能:
把由ptr所指向的已分配的内存大小变为由newsize所确定的新的大小. newsize值可以小于或大于原先的值,若分配成功,函数返回新分配的内存的首址,并把原先块的内容拷贝到新块中,信息不会丢失;否则,函数将返回空指针.

26 例如：ListInsert_Sq(L, 5, 66) 21 18 30 75 42 56 87 q p L:
L.length-1 q p L: q = &(L.elem[i-1]); // q 指示插入位置

27 例如：ListInsert_Sq(L, 5, 66) 21 18 30 75 42 56 87 q p L:
L.length-1 for (p = &(L.elem[L.length-1]); p >= q; --p) *(p+1) = *p;

28 例如：ListInsert_Sq(L, 5, 66) 21 18 30 75 42 56 87 q p L:
87 L.length-1 for (p = &(L.elem[L.length-1]); p >= q; --p) *(p+1) = *p;

29 例如：ListInsert_Sq(L, 5, 66) 21 18 30 75 42 56 87 q p L: 66
87 56 L.length-1 q p L: 66 for (p = &(L.elem[L.length-1]); p >= q; --p) *(p+1) = *p;

30 考虑移动元素的平均情况: 假设在第 i 个元素上插入的概率为 ， 则在长度为n 的线性表中插入一个元素所需移动元素次数的为： 若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的次数为：

31 a1 a2 … ai-1 ai ai+1 … an a1 a2 … ai-1 ai+1 … an 2.2 线性表的顺序表示和实现
3、删除(算法2.5) (a1, …, ai-1, ai, ai+1, …, an) 改变为(a1, …, ai-1, ai+1, …, an) <ai-1, ai>, <ai, ai+1> <ai-1, ai+1> a1 a2 … ai-1 ai ai+1 … an a1 a2 … ai-1 ai+1 … an 表的长度减少

32 2.2 线性表的顺序表示和实现 Status ListDelete_sq(Sqlist&L，int I，ElemType &e) { if(i<1 || i>L.length) return ERROR; p=&(L.Elem[i-1]); e=*p; q=L.elem+L.length-1; for(++p；p<=q；++p) *(p-1)=*p; L.length--; return OK; } //end ListDelete_sq 算法时间复杂度为: 元素左移 O( ListLength(L))

33 例如：ListDelete_Sq(L, 5, e)
p = &(L.elem[i-1]); q = L.elem+L.length-1; for (++p; p <= q; ++p) *(p-1) = *p; q p p p p L.length-1 56 87

34 考虑移动元素的平均情况: 假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素次数的为： 若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的为：

35 2.2 线性表的顺序表示和实现 4、定位 (算法2.6) 算法的时间复杂度为： O( ListLength(L) )
Status LocateElem_sq(SqList L,ElemType e){ i=1; p=L.elem; while(i<=L.length && （*p++!=e)) ++i; if(i<=L.length) return i; else return 0; }//end LocateElem_sq 算法的时间复杂度为： O( ListLength(L) )

36 例如：顺序表（定位） L.listsize L.elem L.length p p p p p p i 1 8 3 4 1 2 e = 38 50 4

37 算法的时间复杂度为 O(La.length+Lb.length)
5、顺序表的合并(算法2.7) void MergeList_Sq(SqlList La,SqlList Lb,SqlList &Lc){ 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++; while(pb<=pb_last) *pc++=*pb++; }//end MergeList_Sq 算法的时间复杂度为 O(La.length+Lb.length)

38 2.2 线性表的顺序表示和实现 顺序表的优点： 顺序表的缺点： 1）无须为表示数据元素之间的关系而增加额外存储空间。
2）可方便地随机存取表中任一元素。 顺序表的缺点： 插入和删除时需移动大量元素。

39 2.3 线性表的链式表示和实现 2.3.1 线性链表 用一组任意的存储单元来依次存放线性表的数据元素，这组存储单元既可以是连续的，也可以是不连续的。 为了能正确表示数据元素间的逻辑关系，在存储每个元素自身信息的同时，还必须存储指示其直接后继的信息（即存储位置），这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构。 按指针域，线性链表分为单链表、循环链表和双向链表。

40 2.3 线性表的链式表示和实现 一、单链表 每一个结点只有一个指针域。 整个单链表可有头指针唯一确定。 空指针 
…… 160 lat 205 jat 110 fat 130 bat Null mat …. 170 eat 135 cat ……. 200 hat 165 头指针 空指针 a1 a2 an   头指针 例、线性表(bat，cat，eat， fat，hat，jat，lat，mat) 的单链表。 bat cat mat   头指针

41 2.3 线性表的链式表示和实现 为了操作方便，增设一个头结点。 1、单链表的存储结构定义 typedef struct LNode{
a1 an   头指针 a2 头结点 表结点 首结点 1、单链表的存储结构定义 typedef struct LNode{ Elemtype data; struct LNode *next; }Lnode, *LinkList;

42 2.3 线性表的链式表示和实现 注意区分头结点、头指针、首结点 考虑：为什么设置头结点？
如果没有头结点，在进行插入、删除等操作时，对首结点的操作比其它结点复杂。 如果增加头结点，则对首结点的操作与其它结点一致。

43 2.3 线性表的链式表示和实现 2、基本操作在单链表上的实现 （1）取元素(算法2.8)//取第i个元素
Status GetElem_L(LinkList L,int i,ElemType &e){ p=L->next; j=1; while(p && j<i){ p=p->next; ++j; } if(!p||j>i) return ERROR; e=p->data; return OK; }//end GetElem_L

44 2.3 线性表的链式表示和实现 算法分析 基本操作：移动元素，移动次数与i有关 最坏的时间复杂度O(n)。

45 2.3 线性表的链式表示和实现 S->next=p->next; P->next=s; 2、基本操作在单链表上的实现
（2）插入(算法2.9) 插入操作是将值为e的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。 插入过程：1）定位；2）插入。 ai-1  头指针 ai e a1 p p p p S->next=p->next; P->next=s;

46 2.3 线性表的链式表示和实现 具体算法如下： Status ListInsert_L(LinkList &L,El;emType e，int i) { p=L; j=0; while(p&& j<i-1){p=p->next;++j;} if(!p|| j>i-1) return error; s=(LinkList)malloc(sizeof(Lnode)); s->data=e; s->next=p->next; p->next=s; return OK; }//end ListInsert_L

47 以上算法的时间复杂度均为O(n)。 上述算法里动态申请新结点空间时未加错误处理，可作下列 处理：
p=(listnode*)malloc(sizeof(listnode)) if(p==NULL) { error(〝No space for node can be obtained〞); return ERROR; } 以上算法的时间复杂度均为O(n)。

48 2.3 线性表的链式表示和实现 算法分析 算法的时间主要耗费在查找操作上， 故时间复杂度为O(n）。

49 2.3 线性表的链式表示和实现 （3）删除(算法2.10) 删除操作是将表的第i个结点删去。 删除过程：1）定位；2）删除。  p p p
ai-1  头指针 ai a1 ai+1 p p p p q q=p->next; p->next=q->next;

50 2.3 线性表的链式表示和实现 具体算法如下： Status ListDelete_L (LinkList &L, int i, ElemType &e) { p=L; 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; }//end ListDelete_L

51 2.3 线性表的链式表示和实现 算法分析 算法的时间主要耗费在查找操作上，故最坏时间复杂度为O(n）
链表上实现插入和删除运算，无须移动结点，仅需修改指针。

52 2.3 线性表的链式表示和实现 2、基本操作在单链表上的实现 （4）建立单链表 假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符‘\n’为输入结束标记。动态地建立单链表的常用方法有如下两种  头插法建表(算法2.11) 该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。

53 2.3 线性表的链式表示和实现 void CreateList_L(LinkList &L,int n) {//逆位序输入n个元素的值，建立带头结点的单链表 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; }//end for }end CreatList_L

54 2.3 线性表的链式表示和实现 尾插法建表 头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。

55 void Creater(LinkList &L int n ) { LNode. p，
void Creater(LinkList &L int n ) { LNode *p，*r; //r为尾指针L=(LinkList)malloc(sizeof(LNnode)); L->next=NULL; r=NULL; for(i=n;i>0;i--){ p=(LinkList)malloc(sizeof(LNnode)); scanf(&p–>data); if(L->next==NULL) { L->next=p; r=p;} else r–>next=p; r=p; } if (r!=NULL) r–>next=NULL; }//end Creater

56 链表的合并(算法2.12) void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){ //La和Lb按元素值非递减排序,合并为Lc pa=La->next; pb=Lb->next; Lc=pc=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); }end MergeList

57 pa=La->next; pb=Lb->next; Lc=pc=La;
pc,Lc c La a  pa d Lb f b h  pb

58 pc->next=pa; pc=pa; pa=pa->next;
La a c  pc pa Lc d Lb f b h  pb

59 pc->next=pb;pc=pb;pb=pb->next;
La a c  pa Lc d Lb f b h  pc pb

60 pc La a c  Lc Pa=  Lb b d f h  pb

61 pc La a c Lc Lb b d f h  pb

62 2.3 线性表的链式表示和实现 二、循环链表 循环链表时一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。 单循环链表： 在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简称为单循环链表。 为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：

63 2.3 线性表的链式表示和实现 …. a1 an head ⑴ 非空表 ⑵ 空表 head …. a1 an rear
(3) 仅设指针的循环链表

64 循环链表基本操作的实现 基本操作与单链表类似 由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像单链表那样判断p或 p-->next是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等.

65 2.3 线性表的链式表示和实现 2.3.3 双链表//单链表的缺点：找不到前驱 双向链表(Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域pre。这样形成的链表中有两个方向不同的指针，故称为双向链表。形式描述为： typedef struct DulNode{ ElemType data; struc DulNode *pre，*next; }DulNode *DuLinkList;

66 a1 a2 … ... an ^ 空表 p 非空表 (p—>pre)—>next p (p—>next)—>pre
=

67 a1 a2 … ... an ^ p s e 双向链表的前插操作 (算法2.18) 1. S->pre=p->pre;
2. P->pre->next=s; 考虑：1和4能不能交换？ 1和2能不能交换？ 3和4能不能交换？ 3. S->next=p; 4. P->pre=s;

68 p 非空表 删除双向链表的第i个元素(算法2.18) ai-1 ai+1 ai an
1.p->pre->next=p->next;

69 p 非空表 ai-1 ai ai+1 an 1.p->pre->next=p->next;

70 ai an p ai+1 ai-1 非空表 1. p->pre->next=p->next;
2. p->next->pre=p->pre;

71 an ai+1 ai-1 非空表 1. p->pre->next=p->next;
2. p->next->pre=p->pre; 3. free(p);

72 注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。

73 2.4 一元多项式的表示及相加 在计算机中，可以用一个线性表来表示: P = (p0, p1, …，pn) 但是对于形如
P(x) = 1 + 3x10000 – 2x20000 的多项式，上述表示方法是否合适？

74 2.4 一元多项式的表示及相加 一般情况下，一元稀疏多项式可写成 其中：pi 为指数ei项的非零系数
0≤ e1 < e2 < ┄ < em = n 可以下列线性表表示: （（p1, e1）, (p2, e2), ┄, (pm,em) ）

75 例如: 可用线性表 ( (7, 3), (-2, 12), (-8, 999) ) 表示 2.4 一元多项式的表示及相加
P999(x) = 7x3 - 2x12 - 8x999 可用线性表 ( (7, 3), (-2, 12), (-8, 999) ) 表示

76 2.4 一元多项式的表示及相加 抽象数据类型一元多项式的定义如下： ADT Polynomial { 数据对象：
数据关系： D＝{ ai | ai ∈TermSet, i=1,2,...,m, m≥0 TermSet 中的每个元素包含一个 表示系数的实数和表示指数的整数 } R＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n 且ai-1中的指数值＜ai中的指数值 }

77 2.4 一元多项式的表示及相加 初始条件：一元多项式 P 已存在。 操作结果：销毁一元多项式 P。 基本操作：
CreatPolyn ( &P, m ) 操作结果：输入 m 项的系数和指数， 建立一元多项式 P。 DestroyPolyn ( &P ) 初始条件：一元多项式 P 已存在。 操作结果：销毁一元多项式 P。 PrintPolyn ( &P ) 初始条件：一元多项式 P 已存在。 操作结果：打印输出一元多项式 P。

78 PolynLength( P ) AddPolyn ( &Pa, &Pb ) SubtractPolyn ( &Pa, &Pb ) … … } ADT Polynomial 初始条件：一元多项式 P 已存在。 操作结果：返回一元多项式 P 中的项数。 初始条件：一元多项式 Pa 和 Pb 已存在。 操作结果：完成多项式相加运算，即： Pa = Pa＋Pb，并销毁一元多项式 Pb。

79 一元多项式的实现： typedef OrderedLinkList polynomial; // 用带表头结点的有序链表表示多项式
结点的数据元素类型定义为: typedef struct { // 项的表示 float coef; // 系数 int expn; // 指数 } term, ElemType;

80 void CreatPolyn ( polynomail &P, int m ) {
// 输入m项的系数和指数，建立表示一元多项式的有序链表P } // CreatPolyn InitList (P); h=gethead(P); e.coef = 0.0; e.expn = -1; SetCurElem (h, e); // 设置头结点的数据元素 for ( i=1; i<=m; ++i ) { // 依次输入 m 个非零项 } scanf (e.coef, e.expn); if (!LocateElem ( P, e, q, (*cmp)()) ) { if (MakeNode (s,e)) InsFirst ( q, s ); 注意: 1.输入次序不限; 2.指数相同的项只能输入一次

81 Status AddPolyn ( polynomial &Pa, polynomial &Pb) {
// 利用两个多项式的结点构成“和多项式” Pa = Pa＋Pb ha=GetHead(Pa);hb=GetHead(Pb); qa=NextPos(Pa,ha);qb=NextPos(Pb,hb); while (qa&&qb) { a=GetCurElem(qa); b=GetCurElem(qb); switch (*cmp(a,b)) { case -1: { // 多项式Pa中当前结点的指数值小 ha=qa;qa=NextPos(Pa,qa); break; }

82 case 0: { // 两者的指数值相等 sum= a.coef + b.coef ;
if ( sum!= 0.0 ) SetCurElem(qa,sum); ha=qa;} else{ DelFirst(ha,sum);FreeNode(qa); } 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; } }//end switch }//end while if(!ListEmpty(Pb)) Append(Pa,qb); FreeNode(hb); } // AddPolyn

83 本章小结 1.了解线性表的逻辑结构特性(数据元素之间存在着 线性关系)，在计算机中表示这种关系的两类不同
的存储结构是顺序存储结构和链式存储结构。用 前者表示的线性表简称为顺序表，用后者表示的 线性表简称为链表。 2.熟练掌握这两类存储结构的描述方法，以及线性表 的各种基本操作的实现。 3.能够从时间和空间复杂度的角度综合比较线性表两种 存储结构的不同特点及其适用场合。

84 作业 书面作业: p13: 2.5题 p14: 2.6题,2.9题 p18: 2.22题, 2.32题 上机作业:
实现一元多项式的表示及相加