问题:将两个有序顺序表合并成一个有序顺序表。
算法思想:不断取两个顺序表表头,比较大小,将小者存入新的有序顺序表,直至其中一个表比较完毕,将另一个剩余的表全部存入新的顺序表。
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define Maxsize 50
int flag=1; //利用变量构造两个不同的有序表
typedef struct SqList{
int* data;
int length;
};
// ---------------------------- 初始化-----------------------------
bool InitList(struct SqList* L,int length)
{
L->data=(int*)malloc(sizeof(int)*(length));
int i=0;
for(i=0;i<length;i++)
{
L->data[i]=i*flag+1;
}
flag=2;
L->length=length;
return true;
}
void Delete_same(struct SqList* LL)
{
int i=0;
int j=1;
for(i=0,j=1;j<LL->length;j++)
{
if(LL->data[j]!=LL->data[i])
{
i++;
LL->data[i]=LL->data[j];
}
}
LL->length=i+1;
}
//------------------合并算法--------------------
bool merge(struct SqList* LL1,struct SqList* LL2,struct SqList* LL3)
{
if((LL1->length+LL2->length)>LL3->length)
return false;
int i=0;
int j=0;
int k=0;
while((i<LL1->length)&&(j<LL2->length))
{
if(LL1->data[i]<=LL2->data[j])
{
LL3->data[k]=LL1->data[i];
i++;
k++;
}
else
{
LL3->data[k]=LL2->data[j];
j++;
k++;
}
}
while(i<LL1->length)
{
LL3->data[k++]=LL1->data[i++];
}
while(j<LL2->length)
{
LL3->data[k++]=LL2->data[j++];
}
LL3->length=k;
return true;
}
void print(struct SqList *L)
{
int j=L->length;
int i=0;
for(i=0;i<j;i++)
{
printf("%d ",L->data[i]);
}
printf("\n");
}
int main()
{
//-------------------初始化顺序表--------------------
struct SqList L1;
struct SqList L2;
struct SqList L3;
if(InitList(&L1,10)==true)
{
printf("顺序表L1初始化成功!\n");
}
print(&L1);
printf("\n\n");
if(InitList(&L2,10)==true)
{
printf("顺序表L2初始化成功!\n");
}
print(&L2);
printf("\n\n");
if(InitList(&L3,20)==true)
{
printf("顺序表L3初始化成功!\n");
}
//print(&L3);
printf("\n\n");
if(merge(&L1,&L2,&L3)==true)
printf("合并成功!\n");
print(&L3);
printf("\n\n");
}
运行结果:
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/10409.html