## 問題描述 > 將兩個有序的順序表合并成一個新的有序順序表，由函數返回結果順序表 ## 算法思想 > 本題實際就是歸并排序的一種特殊情況，因為兩個順序表皆有序，這樣我們只需要不斷的取下兩個順序表中表頭元素較小的那個數，然后將其存入新的順序表，最后看哪個表還有剩余，將剩下的部分直接添加到新的順序表后面即可。 ## 算法描述 ~~~ SqList* Merge(SqList *L1, SqList *L2) { SqList *L = (SqList*)malloc(sizeof(SqList)); int i = 0, j = 0, k = 0; while(i<L1->length&&j<L2->length){ if (L1->data[i] <= L2->data[j]){ L->data[k++] = L1->data[i++]; } else{ L->data[k++] = L2->data[j++]; } } while (i != L1->length){ L->data[k++] = L1->data[i++]; } while (j != L2->length){ L->data[k++] = L1->data[j++]; } L->length = k; return L; } ~~~ 具體代碼見附件 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> #define MaxSize 100 typedef int ElemType; typedef struct{ ElemType data[MaxSize]; int length; }SqList; SqList* Merge(SqList *, SqList *); void print(SqList*); int main(int argc, char* argv[]) { SqList SL1, SL2; SL1.length = 10; SL2.length = 10; for (int i = 0; i < SL1.length; i++){ SL1.data[i] = 2 * i + 1; } for (int i = 0; i < SL2.length; i++){ SL2.data[i] = 2 * i; } print(&SL1); print(&SL2); SqList *SL; SL = Merge(&SL1, &SL2); print(SL); return 0; } SqList* Merge(SqList *L1, SqList *L2) { SqList *L = (SqList*)malloc(sizeof(SqList)); int i = 0, j = 0, k = 0; while(i<L1->length&&j<L2->length){ if (L1->data[i] <= L2->data[j]){ L->data[k++] = L1->data[i++]; } else{ L->data[k++] = L2->data[j++]; } } while (i != L1->length){ L->data[k++] = L1->data[i++]; } while (j != L2->length){ L->data[k++] = L1->data[j++]; } L->length = k; return L; } void print(SqList *L){ for (int i = 0; i < L->length; i++){ printf("%4d", L->data[i]); } printf("\n"); } ~~~