数据结构与算法-线性表-线性表的应用

1 线性表

1.5 线性表的应用

1.5.1 线性表的合并

在这里插入图片描述

【算法步骤】

分别获取 LA 表长 m 和 LB 表长 n 。
从 LB 中第 1 个数据元素开始，循环 n 次执行以下操作：
1. 从 LB 中查找第 i 个数据元素赋给 e ；
2. 在 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 成正比，而后在循环体内：
1. 从 LB 顺序表中获取元素 GetElem 的时间复杂度是 O(1) ；
2. 从 LA 顺序表中查找是否有相关元素 LocateELem，和表长 m 成正比；
3. 插入到 LA 顺序表 ListInsert，因为是插入末尾，所以时间复杂度是 O(1) ；

因此时间复杂度是：O(m*n) 。

链表实现分析：

ListLength 的时间复杂度和 LA 和 LB 的表长m、n成正比；
LB 顺序表要遍历一遍，这里和表长 n 成正比，而后在循环体内：
1. 从 LB 链表中获取元素 GetElem 的和表长 n 成正比；
2. 从 LA 链表中查找是否有相关元素 LocateELem，和表长 m 成正比；
3. 插入到 LA 链表表 ListInsert，链表的插入时间复杂度是 O(1) ；

因此时间复杂度是：O(m) + O(n) + O(n*(m+n)) + O(1)，取最高阶，忽略低阶，再根据书中假设 m > n，所以最终时间复杂度就是：O(m*n) 。

1.5.2 有序表的合并

在这里插入图片描述

顺序表实现

【算法步骤】

创建一个表长为 m+n 的空表 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(m+n)，因为多用了一个 m + n 的空间，所以空间复杂度 O(m+n)。

链表实现

【算法步骤】

指针 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;
}