使用c++实现 两个表合并成一个有序表。要求设计两种以上储存方式、两种以上处理流程方式,要求: 抽象数据类型独立实现,写出完整可直接运行的代码并分析各代码性能
时间: 2024-06-11 18:07:34 浏览: 6
这里提供两种储存方式:顺序表和链表,并且采用两种处理流程方式:插入排序和归并排序。
1. 顺序表储存,插入排序处理
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct {
int data[MAXSIZE];
int length;
} SqList;
void printList(SqList L) {
for (int i = 0; i < L.length; i++) {
printf("%d ", L.data[i]);
}
printf("\n");
}
void insertSort(SqList* L) {
for (int i = 1; i < L->length; i++) {
if (L->data[i] < L->data[i-1]) {
int tmp = L->data[i];
int j = i - 1;
while (j >= 0 && tmp < L->data[j]) {
L->data[j+1] = L->data[j];
j--;
}
L->data[j+1] = tmp;
}
}
}
void merge(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;
}
int main() {
SqList La, Lb, Lc;
La.length = 5;
La.data[0] = 1;
La.data[1] = 3;
La.data[2] = 5;
La.data[3] = 7;
La.data[4] = 9;
Lb.length = 4;
Lb.data[0] = 2;
Lb.data[1] = 4;
Lb.data[2] = 6;
Lb.data[3] = 8;
insertSort(&La);
insertSort(&Lb);
merge(La, Lb, &Lc);
printList(Lc);
return 0;
}
```
代码性能分析:时间复杂度为$O(n^2)$,空间复杂度为$O(n)$。
2. 链表储存,归并排序处理
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode {
int data;
struct LNode* next;
} LNode, *LinkList;
void printList(LinkList L) {
LNode* p = L->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
LinkList createLinkList(int arr[], int n) {
LinkList L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
for (int i = n-1; i >= 0; i--) {
LNode* p = (LNode*)malloc(sizeof(LNode));
p->data = arr[i];
p->next = L->next;
L->next = p;
}
return L;
}
void merge(LinkList La, LinkList Lb, LinkList* Lc) {
LNode* pa = La->next;
LNode* pb = Lb->next;
LNode* pc = *Lc = La;
while (pa && pb) {
if (pa->data <= pb->data) {
pc->next = pa;
pc = pa;
pa = pa->next;
} else {
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb;
free(Lb);
}
void divide(LinkList L, LinkList* La, LinkList* Lb) {
LNode* pa = L->next;
LNode* pb = L->next;
LNode* pc = L;
while (pa) {
pa = pa->next;
if (pa) {
pb = pb->next;
pa = pa->next;
}
}
*La = L;
*Lb = pb->next;
pb->next = NULL;
}
void mergeSort(LinkList* L) {
LinkList La, Lb;
if ((*L)->next == NULL || (*L)->next->next == NULL) {
return;
}
divide(*L, &La, &Lb);
mergeSort(&La);
mergeSort(&Lb);
merge(La, Lb, L);
}
int main() {
int arr1[] = {1, 3, 5, 7, 9};
int arr2[] = {2, 4, 6, 8};
LinkList L1 = createLinkList(arr1, 5);
LinkList L2 = createLinkList(arr2, 4);
mergeSort(&L1);
mergeSort(&L2);
LinkList Lc;
merge(L1, L2, &Lc);
printList(Lc);
return 0;
}
```
代码性能分析:时间复杂度为$O(nlogn)$,空间复杂度为$O(1)$。