艺术家个人网站设计,想做网站濮阳网站建设,昆明市建设厅官方网站,wordpress微交易1 线性表
1.5 线性表的应用
1.5.1 线性表的合并 【算法步骤】
分别获取 LA 表长 m 和 LB 表长 n 。从 LB 中第 1 个数据元素开始#xff0c;循环 n 次执行以下操作#xff1a; 从 LB 中查找第 i 个数据元素赋给 e #xff1b;在 LA 中查找元素 e #xff0c;如果不存在循环 n 次执行以下操作 从 LB 中查找第 i 个数据元素赋给 e 在 LA 中查找元素 e 如果不存在则将 e 插在表 LA 的最后。
【代码实现】
顺序表实现
// 合并两个线性表顺序表实现。
// 将所有在线性表 LB 中但不在 LA 中的数据元素插入到 LA 中。
void MergeList_Sq(SqList *LA, SqList *LB)
{int m ListLength(LA);int n ListLength(LB);for (int i 1; i n; i){ElemType e;GetElem(LB, i, e); // 获取 LB 中的第 i 个元素if (!LocateELem(LA, e)) // 如果 LA 中没有该元素{ListInsert(LA, m, e); // 插入到 LA 的末尾}}
}ListLength、GetElem、LocateELem、ListInsert 可以参考之前顺序表章节的实现。
链表实现链表的实现方式和顺序表几乎一致就是把链表 LA 和 LB 的类型修改为 LinkList 即可。
// 合并两个线性表链表实现。
// 将所有在线性表 LB 中但不在 LA 中的数据元素插入到 LA 中。
void MergeList(LinkList *LA, LinkList *LB)
{int m ListLength(LA);int n ListLength(LB);for (int i 1; i n; i){ElemType e;GetElem(LB, i, e); // 获取 LB 中的第 i 个元素if (!LocateELem(LA, e)) // 如果 LA 中没有该元素{ListInsert(LA, m, e); // 插入到 LA 的末尾}}
}【算法分析】
顺序表实现分析
ListLength 的时间复杂度是 O(1) LB 顺序表要遍历一遍这里和表长 n 成正比而后在循环体内 从 LB 顺序表中获取元素 GetElem 的时间复杂度是 O(1) 从 LA 顺序表中查找是否有相关元素 LocateELem和表长 m 成正比插入到 LA 顺序表 ListInsert因为是插入末尾所以时间复杂度是 O(1)
因此时间复杂度是O(m*n) 。
链表实现分析
ListLength 的时间复杂度和 LA 和 LB 的表长m、n成正比 LB 顺序表要遍历一遍这里和表长 n 成正比而后在循环体内 从 LB 链表中获取元素 GetElem 的和表长 n 成正比从 LA 链表中查找是否有相关元素 LocateELem和表长 m 成正比插入到 LA 链表表 ListInsert链表的插入时间复杂度是 O(1)
因此时间复杂度是O(m) O(n) O(n*(mn)) O(1)取最高阶忽略低阶再根据书中假设 m n所以最终时间复杂度就是O(m*n) 。
1.5.2 有序表的合并 顺序表实现
【算法步骤】
创建一个表长为 mn 的空表 LC。指针 pc 初始化指向 LC 的第一个元素。指针 pa 和 pb 初始化分别指向 LA 和 LB 的第一个元素。当指针 pa 和 pb 均未到达相应表尾时则依次比较 pa 和 pb 所指向的元素值从 LA 或 LB 中“摘取”元素值较小的结点插人到 LC 的最后。如果 pb 已到达 LB 的表尾依次将 LA 的剩余元素插人 LC 的最后。如果 pa 已到达 LA 的表尾依次将 LB 的剩余元素插人 LC 的最后。
【代码实现】
// 合并两个有序表顺序表实现。
Status MergeList(SqList *LA, SqList *LB, SqList *LC)
{LC-maxsize LC-length LA-length LB-length; // 合并后的最大长度LC-elem (ElemType *)malloc(LC-length * sizeof(ElemType)); // 分配初始空间if (LC-elem NULL){return OVERFLOW;}ElemType *pc LC-elem; // pc 指向合并后的顺序表的第一个元素ElemType *pa LA-elem; // pa 指向第一个顺序表ElemType *pb LB-elem; // pb 指向第二个顺序表ElemType *pa_last pa LA-length - 1; // pa 指向第一个顺序表的最后一个元素ElemType *pb_last pb LB-length - 1; // pb 指向第二个顺序表的最后一个元素while (pa pa_last pb pb_last) // 只要两个顺序表都没有遍历完{if (pa-x pb-x) // 如果第一个顺序表的元素小于第二个顺序表的元素*pc *pa; // 将第一个顺序表的元素放入合并后的顺序表else*pc *pb; // 将第二个顺序表的元素放入合并后的顺序表}while (pa pa_last) // 如果第一个顺序表还有元素*pc *pa; // 将第一个顺序表的元素放入合并后的顺序表while (pb pb_last) // 如果第二个顺序表还有元素*pc *pb; // 将第二个顺序表的元素放入合并后的顺序表return OK;
}【算法分析】
第一个 while 循环执行的次数是 m n - LA或LB表剩余未插入到LC表的元素个数 次主要是取决于顺序表中的数字情况不管怎么样这个循环最终执行完毕后一定有一个顺序表的元素全部插入到 LC 表中。而后面的两个循环就是处理另外一个顺序表将该顺序表的剩余元素插入到 LC 表中所以执行次数就是 m n 次时间复杂度 O(mn)因为多用了一个 m n 的空间所以空间复杂度 O(mn)。
链表实现
【算法步骤】
指针 pa 和 pb 初始化分别指向 LA 和 LB 的第一个结点。LC 的结点取值为 LA 的头结点。指针 pc 初始化指向 LC 的头结点。当指针 pa 和 pb 均未到达相应表尾时则依次比较 pa 和 pb 所指向的元素值从 LA 或 LB 中“摘取”元素值较小的结点插入到 LC 的最后。将非空表的剩余段插入到 pc 所指结点之后。释放 LB 的头结点。
【代码实现】
// 合并两个有序表链表实现。
Status MergeList(LinkList *LA, LinkList *LB, LinkList *LC)
{LNode *pa (*LA)-next; // 指向链表LA的第一个结点LNode *pb (*LB)-next; // 指向链表LB的第一个结点LC LA; // 将链表LA的头结点赋值给LCLNode *pc *LC; // 指向合并后的链表的头结点while (pa ! NULL pb ! NULL) // 遍历到链表LA或LB的末尾{if (pa-data.x pb-data.x) // 如果链表LA的当前结点小于等于链表LB的当前结点{pc-next pa; // 将链表LA的当前结点添加到合并后的链表中pc pa; // 移动到下一个结点pa pa-next; // 移动到下一个结点}else{pc-next pb; // 将链表LB的当前结点添加到合并后的链表中pc pb; // 移动到下一个结点pb pb-next; // 移动到下一个结点}}pc-next pa ! NULL ? pa : pb; // 将剩余的结点添加到合并后的链表中free(*LB); // 释放链表LB头结点的内存(*LB) NULL; // 将链表LB的头结点指针置为NULLreturn OK;
}【算法分析】
假设 LA 链表的长度为 mLB 链表的长度为 nm n。分析其中的代码执行主体在 while 循环
最好的情况就是小的数字全部在 LA 中这样循环只要执行 m 次即可。最差的情况 LA 中第一个元素是最小值最后一个元素是最大值 这样 LA 和 LB 中的元素都要遍历一遍理论就是 m n 次。
所以平均的时间复杂度就是 O(mn) 。因为只需将原来两个链表中结点之间的关系解除 重新按元素值非递减的关系将所有结点链接成一个链表即可所以空间复杂度为 O(1) 。
