第5-1讲线性表的应用.ppt

第5-1讲 线性表的应用 主讲人：陈红丽 一元多项式的加法 Status AddPolyn (polynomial Pa, polynomial Pb){ // 利用两个多项式的结点构成“和多项式” LNode *p,*q,*u,*pre; int x; p=pa-next; q=pb-next; pre=pa; while((p!=NULL) ((q!=NULL)){ if(p-data.exp q-data.exp){ … } else if(p-data.exp= =q-data.exp){ … } else{ … } } if(q!=NULL) pre-next=q; free(pb); }//AddPolyn * 第2章 线性表 * 数据结构 双向链表的操作特点： “查询” 和单链表相同 “插入” 和“删除”需要同时修改两个方向上的指针。 ai-1 ai e s-next = p-next; p-next = s; s-next-prior = s; s-prior = p; p s ai-1 ai 插入 ai+1 ai ai-1 删除 q=p-next； p-next = q-next; p-next-prior = p; delete( q); q p ai-1 六、有序表类型 ADT Ordered_List { 数据对象: S = { xi|xi ? OrderedSet ， i=1,2,…,n, n≥0 } 集合中 任意两个 元素之间 均可以 进行比较 数据关系:R = {xi-1, xi | xi-1, xi ? S, xi-1≤ xi, i=2,3,…,n } 回顾例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 指向 表示值为 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 相同的数据元素，则插入之 } } // union 算法时间复杂度：O(Lb_len×La_len) 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个数据元素赋给 e if (ListEmpty(La) || !equal (en, e)) { ListInsert(La, ++La_len, e); en = e; } // La中不存在和 e 相同的数据元素，则插入之 算法时间复杂度：O(Lb_len) 在计算机中，可以用一个线性表来表示: P = (p0, p1, …，pn) 一元多项