2.2.1 顺序表 以上定义的函数可在程序设计中引用,例如,上述算法2.2可改写为下列可在主函数中调用的函数。 |
当然,在调用前还需要对元素类型 ElemType 和作为参数的函数 equal() 加以明确定义。 |
|||
void purge(SqList &La, SqList Lb) { // 构造顺序表 La,使其只包含 Lb 中所有值不相同的数据元素, // 算法不改变顺序表 Lb bool b; int Lb_len = Listlength( Lb ); // 求线性表 Lb 的长度 InitList( La,Lb_len ); // 创建一个空的线性表 La int La_len = 0; for ( i = 1; i <= Lb_len; i++ ) // 依次处理 Lb 中每个元素 { b = GetElem( Lb, i, e ); // 取Lb中第 i 个数据元素赋给 e if ( !LocateElem( La, e, equal( ) ) ) { ++La_len; b = ListInsert( La,La_len,e ); // 当 La 中不存在和 e 值相同的 } // 数据元素时,进行插入 } // for } // purge |
La 中元素个数不超过 Lb 中的元素个数,故设 La 的最大空间和 Lb 相同。 学习了下一节讨论的内容之后将容易分析出,此算法的时间复杂度仅取决于操作 LocateElem 的时间复杂度。由于每次插入都在表尾进行,因此 ListInsert 在此函数中实际的时间复杂度是常量级的,而其它操作对顺序表类型而言,显然都是常量级的。 |