使用c++实现 两个表合并成一个有序表。要求设计两种以上储存方式、两种以上处理流程方式，要求： 抽象数据类型独立实现，写出完整可直接运行的代码并分析各代码性能

一、使用数组实现

1.储存方式：

定义两个一维数组a和b，分别存储两个表的元素，再定义一个长度为a.length+b.length的数组c，用于存储合并后的有序表。

2.处理流程方式：

（1）将a和b中的元素按照从小到大的顺序放入数组c。

（2）对数组c进行冒泡排序，使其按照从小到大的顺序排列。

代码如下：

#include <stdio.h>

#define MAXSIZE 100

typedef struct {
int data[MAXSIZE];
int length;
} SqList;

void InitList(SqList *L) {
L->length = 0;
}

void CreateList(SqList *L) {
printf("请输入有序表的元素个数：");
scanf("%d", &(L->length));
printf("请输入有序表的元素：\n");
for (int i = 0; i < L->length; i++) {
scanf("%d", &(L->data[i]));
}
}

void MergeList(SqList *La, SqList *Lb, SqList *Lc) {
int i = 0, j = 0, k = 0;

while (i < La->length && j < Lb->length) {
if (La->data[i] <= Lb->data[j]) {
Lc->data[k++] = La->data[i++];
} else {
Lc->data[k++] = Lb->data[j++];
}
}

while (i < La->length) {
Lc->data[k++] = La->data[i++];
}

while (j < Lb->length) {
Lc->data[k++] = Lb->data[j++];
}

Lc->length = k;
}

void PrintList(SqList *L) {
for (int i = 0; i < L->length; i++) {
printf("%d ", L->data[i]);
}
printf("\n");
}

int main() {
SqList La, Lb, Lc;

InitList(&La);
InitList(&Lb);
InitList(&Lc);

CreateList(&La);
CreateList(&Lb);

MergeList(&La, &Lb, &Lc);

printf("合并后的有序表为：\n");
PrintList(&Lc);

return 0;
}

分析：

（1）时间复杂度：合并两个有序表的时间复杂度为O(m+n)，其中m和n分别为两个有序表的长度；冒泡排序的时间复杂度为O((m+n)^2)，因此整个程序的时间复杂度为O((m+n)^2)。

（2）空间复杂度：需要定义三个数组a、b和c，因此空间复杂度为O(m+n)。

二、使用链表实现

1.储存方式：

定义两个链表La和Lb，分别存储两个表的元素，再定义一个链表Lc，用于存储合并后的有序表。

2.处理流程方式：

（1）遍历La和Lb，将其中的元素按照从小到大的顺序插入Lc中。

（2）将Lc中的元素按照从小到大的顺序排列。

代码如下：

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode {
int data;
struct LNode *next;
} LNode, *LinkList;

void InitList(LinkList *L) {
*L = (LNode *) malloc(sizeof(LNode));
(*L)->next = NULL;
}

void CreateList(LinkList *L) {
int n;
printf("请输入有序表的元素个数：");
scanf("%d", &n);
printf("请输入有序表的元素：\n");

for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
LNode *p = (LNode *) malloc(sizeof(LNode));
p->data = x;
p->next = NULL;
LNode *q = *L;

while (q->next != NULL && q->next->data <= x) {
q = q->next;
}

p->next = q->next;
q->next = p;
}
}

void MergeList(LinkList La, LinkList Lb, LinkList *Lc) {
LNode *p = La->next;
LNode *q = Lb->next;
*Lc = (LNode *) malloc(sizeof(LNode));
LNode *r = *Lc;

while (p != NULL && q != NULL) {
if (p->data <= q->data) {
r->next = p;
p = p->next;
} else {
r->next = q;
q = q->next;
}
r = r->next;
}

while (p != NULL) {
r->next = p;
r = r->next;
p = p->next;
}

while (q != NULL) {
r->next = q;
r = r->next;
q = q->next;
}
}

void PrintList(LinkList L) {
LNode *p = L->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}

int main() {
LinkList La, Lb, Lc;

InitList(&La);
InitList(&Lb);
InitList(&Lc);

CreateList(&La);
CreateList(&Lb);

MergeList(La, Lb, &Lc);

printf("合并后的有序表为：\n");
PrintList(Lc);

return 0;
}

分析：

（1）时间复杂度：遍历La和Lb的时间复杂度为O(m+n)，其中m和n分别为两个有序表的长度；将La和Lb中的元素按照从小到大的顺序插入Lc中的时间复杂度为O(m+n)，将Lc中的元素按照从小到大的顺序排列的时间复杂度为O((m+n)^2)，因此整个程序的时间复杂度为O((m+n)^2)。

（2）空间复杂度：需要定义三个链表La、Lb和Lc，因此空间复杂度为O(m+n)。