数据库2——线性表.ppt

2. 双向链表 typedef struct DuLNode { ElemType data; // 数据域 struct DuLNode *prior; // 指向前驱的指针域 struct DuLNode *next; // 指向后继的指针域 } DuLNode, *DuLinkList; 空表 非空表 a1 a2 … ... an 3.双向循环链表 双向链表的操作特点： “查询” 和单链表相同。 “插入” 和“删除”时需要同时修改两个方向上的指针。 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 p-next = p-next-next; p-next-prior = p; 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。 基本操作： … … … … ｝ADT Ordered_List 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(n2) 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(n) 2.4 一元多项式的表示 在计算机中，可以用一个线性表来表示: P = (p0, p1, …，pn) 一元多项式 但是对于形如 S(x) = 1 + 3x10000 – 2x20000 的多项式，上述表示方法是否合适？ 一般情况下的一元稀疏多项式可写成