数据结构 线性表算法例题讲解.docx
需积分: 10 116 浏览量
2021-02-08
18:16:17
上传
评论
收藏 203KB DOCX 举报
数据结构 线性表 算法例题讲解
例 1：合并 LA,LB 中的元素到 LA 中
算法实现：void union (List &La, List Lb){
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);
}
}
算法分析：本题，思路明确，算法的实现也较为简单。需要注意的就是参数 La 既是输入
又是输出。而 Lb 仅为输入。ListLength 为一个求线性表长度的函数。GetElem 函数是
将 Lb 中的第 i 个元素赋值给 e。e 在 LocateElem 中要和 La 中的所有元素一一对比。
LocateElem 函数的意思是，在 La 中，如果有元素和 e 满足 equal 的关系，则整个函数
返回第一个满足此关系的元素值。如果查遍整个数组，也没有这样的元素。则返回 0。
存在疑问：这个算法的时间复杂度为 O（La_len*Lb_len），可是 LocateElem 函数只是
寻找第一个与 e 满足 equal 关系的元素。为什么，时间复杂度中要乘上的是 La_len? 猜
想：时间复杂度的计算并不是绝对精准的计算。它的来去存在一定误差。这里按照 La 中
没有任何元素和 Lb 中元素相同考虑。即 LA∩LB=∅。
例 2：已知 LA 和 LB 中的数据元素按值非递减有序排列。将 LA 和 LB 合并到 LC 并也按照
非递减排列。
算法实现：void MergeList(List La,List Lb,List &Lc){
InitList(Lc);
I=j=1;k=0;
La_len=ListLength(La); Lb_len=ListLength(Lb); //求线性表 La 和 Lb 的长度
while((i<=La_len)&&(j<=Lb_len)){ //当 La 或 Lb 其中一个为空时，循环结
束，
GetElem(La,i,ai);GetElem(Lb,j,bj); 需要开始特殊处理
If(ai<=bj) {ListInsert(Lc,++k,ai);++i;}
else {ListInsert(Lc,++k,bj);++j;}
}
while (i<=La_len){
GetElem(La,i++,ai);ListInsert(Lc,++k,ai);
}
while (j<=Lb_len){
GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);
}
评论0
最新资源