#include "stdio.h"
#include "stdlib.h"
#include "function.h"
void main()
{
Sqlist L,L1,L2;
InitList(&L);
InitList(&L1);
InitList(&L2);
ListInsert(&L, 1, 3);//f(n)
ListInsert(&L, 2, 5);
ListInsert(&L, 1, 8);
ListInsert(&L, 1, 11);
ListInsert(&L1,1,2);
ListInsert(&L1,2,6);
ListInsert(&L1,3,8);
ListInsert(&L1,3,9);
ListInsert(&L1,3,11);
ListInsert(&L1,3,15);
ListInsert(&L1,3,20);
//对顺序表L进行排序
int tmp = 0;
for (int i = 0; i <L.length-1; i++)
{
for (int j = i + 1; j < L.length; j++) {
if (L.elem[i] > L.elem[j]) {
tmp = L.elem[i];
L.elem[i] = L.elem[j];
L.elem[j] = tmp;
}
}
}
tmp = 0;
for (int i = 0; i <L1.length - 1; i++)
{
for (int j = i + 1; j < L1.length; j++) {
if (L1.elem[i] > L1.elem[j]) {
tmp = L1.elem[i];
L1.elem[i] = L1.elem[j];
L1.elem[j] = tmp;
}
}
}
int k = 0;
int j = 0;
while ((k<L.length)&&(j<L1.length))
{
if (L.elem[k] <= L1.elem[j])
{
ListInsert(&L2, L2.length + 1, L.elem[k]);
k++;
}
else
{
ListInsert(&L2, L2.length + 1, L1.elem[j]);
j++;
}
}
if (k >= L.length) {
for (int i = j; i < L1.length; i++)
{
ListInsert(&L2, L2.length + 1, L1.elem[i]);
}
}
if (j>=L1.length) {
for (int i = k; i < L.length; i++)
{
ListInsert(&L2, L2.length + 1, L.elem[i]);
}
}
//输出顺序链表中的所有值
for (int i = 0; i < L2.length; i++)
{
printf("元素的第%d个值为%d\n", i + 1, L2.elem[i]);
}
}
该算法的时间复杂度为O(f(L1)+f(L))