1 線性表
1.5 線性表的應用
1.5.1 線性表的合并
【算法步驟】
- 分別獲取
LA表長m和LB表長n。 - 從
LB中第1個數據元素開始，循環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*(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;
}
【算法分析】
假設 LA 鏈表的長度為 m，LB 鏈表的長度為 n，m < n。分析其中的代碼，執行主體在 while 循環：
- 最好的情況，就是小的數字全部在 LA 中，這樣循環只要執行 m 次即可。
- 最差的情況 LA 中第一個元素是最小值，最后一個元素是最大值， 這樣 LA 和 LB 中的元素都要遍歷一遍，理論就是 m + n 次。
所以平均的時間復雜度就是 O(m+n) 。因為只需將原來兩個鏈表中結點之間的關系解除， 重新按元素值非遞減的關系將所有結點鏈接成一個鏈表即可，所以空間復雜度為 O(1) 。
)
