试编写一个算法,将两个有序线性表合成一个有序线性表...最好是在c++上可以直接运行出来的

Question

如题所述

Answer 1

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
typedef int ElemType;
#define INITSIZE 100

typedef struct
{
ElemType *data;
int length;
int listsize;
}sqlist;

/*初始化*/
void initlist(sqlist *L,int n)
{
int i;
L->data =(ElemType *)malloc(sizeof(ElemType)*INITSIZE);
L->length=0;
for(i=1;i<=n;i++)
{
scanf("%d",&L->data[i-1]);
L->length++;
}
L->listsize=INITSIZE;
}

/*插入元素*/
int insert(sqlist *L,int i,ElemType x)
{
int j;
if(i<1||i>L->length+1) return 0;
if(L->length==L->listsize) //存储空间不够，增加一个
{
L->data=(ElemType *)realloc(L->data,(L->listsize+1)*sizeof(ElemType));
L->listsize++; //重置存储空间长度
}
for(j=L->length;j>=i;j--)
L->data[j]=L->data[j-1]; //将序号为i的结点及之后的结点后移
L->data[i-1]=x; //在序号为i处放入x
L->length++;

return 1;
}
/*归并 增序*/
void merge(sqlist A, sqlist B, sqlist *C)
{
int m =0, n=0;
while (m < A.length && n<B.length)
if(A.data[m]<B.data[n]) //将A的data[m]插入C尾部
{
insert(C,C->length+1,A.data[m]);
m++;
}
else //将B的data[n]插入C尾部
{
insert(C,C->length+1,B.data[n]);
n++;
}

while(m<A.length) //B完，将A的剩余部分插入C
{
insert(C,C->length+1,A.data[m]);
m++;
}
while(n<B.length) //A完，将B的剩余部分插入C
{
insert(C,C->length+1,B.data[n]);
n++;
}
}

/*归并 逆序*/
void merge1(sqlist A, sqlist B, sqlist *C)
{
int m =0, n=0;
while (m < A.length && n<B.length)
if(A.data[m]<B.data[n]) //将A的data[m]插入C头部
{
insert(C,1,A.data[m]);
m++;
}
else //将B的data[n]插入C头部
{
insert(C,1,B.data[n]);
n++;
}

while(m<A.length) //B完，将A的剩余部分插入C
{
insert(C,1,A.data[m]);
m++;
}
while(n<B.length) //A完，将B的剩余部分插入C
{
insert(C,1,B.data[n]);
n++;
}
}

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

/*主函数*/
void main()
{
int m=0,n=0;
sqlist A,B,C;
printf("please input the number of A elemtype M is:");
scanf("%d",&m);
initlist(&A,m);
printf("please input the number of B elemtype N is:");
scanf("%d",&n);
initlist(&B,n);
printf("merge A and B is C:\n");
C.data =(ElemType *)malloc(sizeof(ElemType)*INITSIZE);
C.length=0;
C.listsize=INITSIZE;
merge1(A,B,&C);
list(&C);

}

以上是在VC6.0上运行通过的。
//运行结果：

please input the number of A elemtype M is: 3
3 5 6
please input the number of B elemtype N is: 5
1 4 6 8 9

merge A and B is C:
9 8 6 6 5 4 3 1

Answer 2

#include <stdlib.h>
#define MAX_SIZE 50
int main()
{
int i, k1, k2;
int a1_len = 0, a2_len = 0;
int arr_1[MAX_SIZE];
int arr_2[MAX_SIZE];
int arr_result[MAX_SIZE*2];

// 输入 arr_1，arr_2 数组的值，通过排序算法将其排好序，假设由小到大排序
// 并在输入时将 arr_1 和 arr_2 的长度(即元素个数)分别保存到 a1_len 和 a2_len 中。
// 以下将 arr_1和arr_2中已经排好序的元素按序合并到arr_result中

k1 = 0; k2 = 0;
for(i = 0; k1 < a1_len && k2 < a2_len; i++)
{
if(arr_1[k1] < arr_2[k2])
{
arr_result[i] = arr_1[k1];
k1++;
}
else
{
arr_result[i] = arr_2[k2];
k2++;
}
}
// 采用笨一点的办法处理一下剩余的元素
for( ;k1 < a1_len; k1++, i++)
{
arr_result[i] = arr_1[k1];
}
for( ;k2 < a2_len; k2++, i++)
{
arr_result[i] = arr_2[k2];
}
// 完成！
// arr_result 中保存的是排大小顺序排列的合并元素
}

Answer 3

#include<stdio.h>
#include <malloc.h>
#include<limits.h>

void merge(int a[],int p,int q,int b[],int r,int s,int c[])
{int i,j,n1,n2,n,k,m;
n1=q-p+1;
n2=s-r+1;
int *l=(int *)malloc(sizeof(int)*(n1+1));
for(i=0;i<n1;i++)
l[i]=a[p+i-1];

int *t=(int *)malloc(sizeof(int)*(n2+1)); for(j=0;j<n2;j++)
t[j]=b[r+j-1];

l[n1]=INT_MAX;t[n2]=INT_MAX;
i=0;
j=0;
for(k=0;k<n1+n2;k++)
{if(l[i]<t[j]){c[k]=l[i];
i++;}
else {c[k]=t[j];
j++;}}
for(i=0;i<n1+n2;i++)
printf("%d ",c[i]);
printf("\n");
}

int main()
{
int i;
int arr[] = {4,5,9,1000,1001};
int arr2[] = {1,7,8,999,1003,1005};
int *res = (int*)malloc(sizeof(int) * 100);
merge(arr,1,5,arr2,1,6,res);
return 0;

}

Answer 4

比较简单，想为自己下。
的想法：
记住节点的值val，遍历链表节点，
如果当前节点是相同的值，值，然后删除该节点，
否则，更新val是当前节点的值。