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

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

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）

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）

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

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 在线性表中的位序。

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

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

基本操作： 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。

基本操作： 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。

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

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

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

算法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

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 表中。

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

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

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

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

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

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)

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

… 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 表的长度增加

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 )

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

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

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

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

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

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

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 表的长度减少

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))

例如：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 21 18 30 75 42 56 87 L.length-1 21 18 30 75 56 87

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

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) )

例如：顺序表（定位） L.listsize 23 75 41 38 54 62 17 L.elem L.length p p p p p p i 1 8 3 4 1 2 e = 38 50 4

算法的时间复杂度为 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)

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

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

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   头指针

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

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

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

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

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;

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

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

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

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;

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

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

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

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

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

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

链表的合并(算法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

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

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

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

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

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

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

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

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

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

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

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;

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

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

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

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

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

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

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

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

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中的指数值 }

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

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

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

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.指数相同的项只能输入一次

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; }

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

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

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