顺序存储合并
1. 编写一个用顺序存储结构实现将两个有序表合成一个有序表的算法
用数组写了个思路，如果你们要求用链表的话改一下就可以了：
/*
把num1 num2 合并，输出到num_merge
*/
void merge(int num1[],int num2[],int num_merge[]){
int length1 = sizeof(num1)/sizeof(int);
int length2 = sizeof(num2)/sizeof(int);
int i = 0,j = 0,length_merge = 0;
while(length_merge < length1 && i< length2){
if(num1[i]<num2[j]){
num_merge[length_merge++] = num1[i++];
}else if(num1[i]>num2[j]){
num_merge[length_merge++] = num2[j++];
}else{
num_merge[length_merge++] = num1[i++];
j++;
}
}
while(length_merge < length1){
num_merge[length_merge++] = num1[i++];
}
while(length_merge < length2){
num_merge[length_merge++] = num2[j++];
}
}
2. 数据结构：顺序表的合并（c语言）
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#defineLIST_INIT_SIZE10//线性表存储空间的初始分配量
#defineLISTINCREMENT2//线性表存储空间的分配增量
structSqList
{
int*elem;//存储空间基址
intlength;//当前长度
intlistsize;//当前分配的存储容量(以sizeof(int)为单位)
};
voidInitList(SqList&L)
{//操作结果：构造一个空的顺序线性表
L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));
if(!L.elem)
exit(0);//存储分配失败
L.length=0;//空表长度为0
L.listsize=LIST_INIT_SIZE;//初始存储容量
}
intListInsert(SqList&L,inti,inte)
{//初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1
//操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
int*newbase,*q,*p;
if(i<1||i>L.length+1)//i值不合法
return0;
if(L.length>=L.listsize)//当前存储空间已满,增加分配
{
if(!(newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int))))
exit(0);//存储分配失败
L.elem=newbase;//新基址
L.listsize+=LISTINCREMENT;//增加存储容量
}
q=L.elem+i-1;//q为插入位置
for(p=L.elem+L.length-1;p>=q;--p)//插入位置及之后的元素右移
*(p+1)=*p;
*q=e;//插入e
++L.length;//表长增1
return1;
}
voidPrint(SqList&L)
{
inti;
for(i=0;i<L.length;i++)
printf("%d",*(L.elem+i));
printf(" ");
}
//————————————————————————————————————
//函数①
voidMergeList1(SqListLa,SqListLb,SqList&Lc)
{
int*pa,*pa_last,*pb,*pb_last,*pc;
pa=La.elem;
pb=Lb.elem;
Lc.listsize=Lc.length=La.length+Lb.length;//不用InitList()创建空表Lc
pc=Lc.elem=(int*)malloc(Lc.listsize*sizeof(int));
if(!Lc.elem)//存储分配失败
exit(0);
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
while(pa<=pa_last&&pb<=pb_last)//表La和表Lb均非空
{//归并
if(*pa<*pb)
*pc++=*pa++;
elseif(*pa>*pb)
*pc++=*pb++;
else{
*pc++=*pa++;
pb++;
Lc.length--;
}
}
while(pa<=pa_last)//表La非空且表Lb空
*pc++=*pa++;//插入La的剩余元素
while(pb<=pb_last)//表Lb非空且表La空
*pc++=*pb++;//插入Lb的剩余元素
}
//————————————————————————————————————
//函数②
voidMergeList2(SqListLa,SqList&Lb,SqList&Lc)
{
int*pa,*pa_last,*pb,*pb_last,*pc;
pa=La.elem;
pb=Lb.elem;
Lc.listsize=Lc.length=La.length+Lb.length;//不用InitList()创建空表Lc
pc=Lc.elem=(int*)malloc(Lc.listsize*sizeof(int));
if(!Lc.elem)//存储分配失败
exit(0);
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
while(pa<=pa_last&&pb<=pb_last)//表La和表Lb均非空
{//归并
if(*pa<=*pb)
*pc++=*pa++;
else
*pc++=*pb++;
}
while(pa<=pa_last)//表La非空且表Lb空
*pc++=*pa++;//插入La的剩余元素
while(pb<=pb_last)//表Lb非空且表La空
*pc++=*pb++;//插入Lb的剩余元素
Lb.length=Lc.length;
Lb=Lc;
}
//————————————————————————————————————
//函数③
voidInverse(SqList&L){
inti,t;
for(i=0;i<L.length/2;i++)
{
t=*(L.elem+i);
*(L.elem+i)=*(L.elem+L.length-i-1);
*(L.elem+L.length-i-1)=t;
}
}
voidmain(){
SqListLA,LB,LC;
inta[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20};
inti;
InitList(LA);
InitList(LB);
InitList(LC);
for(i=0;i<4;i++)
ListInsert(LA,i+1,a[i]);
for(i=0;i<7;i++)
ListInsert(LB,i+1,b[i]);
printf("LA=");
Print(LA);
printf("LB=");
Print(LB);
printf(" ");
MergeList1(LA,LB,LC);
printf("①LC=");
Print(LC);
printf(" ");
MergeList2(LA,LB,LC);
printf("②LB=");
Print(LB);
printf(" ");
printf("③LC=");
Inverse(LC);
Print(LC);
}
3. 用顺序存储实现两个线性表合并
合并两个线性表中的元素，相同的元素只保留一个，代码如下：
#pragma once
#define ListSize 200
#include <iostream>
using namespace std;
typedef int DataType;
typedef struct
{
DataType list[ListSize];
int length;
}SeqList;
//初始化线性表
void InitList(SeqList *L)
{
L->length = 0;//把线性表长度置为0
}
//判断线性表是否为空,线性表为空返回1，否则返回0
int ListEmpty(SeqList L)
{
if (L.length == 0)
return 1;
else
return 0;
}
//按照序号查找
int GetElem(SeqList L, int i, DataType *e)
/*查找线性表中第i个元素，查找成功返回给e，并返回1表示成功，否则返回-1，表示失败*/
{
if (i<1 || i>L.length)
return -1;
else
*e = L.list[i - 1];
return 1;
}
//按照内容查找
int LocateElem(SeqList L, DataType e)
{
int i;
for (i = 0; i < L.length; i++)/*从第一个元素开始与e进行比较*/
if (L.list[i] == e) /*若存在与e相等的元素*/
return i + 1; /*返回该元素的在线性表中的序号*/
return 0; /*否则，返回0 */
}
//插入操作
int InsertList(SeqList *L, int i, DataType e)
/*在顺序表中的第i个位置插入元素e，插入成功返回1，插入不合法返回-1，顺序表满返回0.*/
{
int j;
if (i<1||i>L->length+1)/*在插入元素前，判断插入位置是否合法*/
{
cout <<"插入位置"<<i<<"不合法！" << endl;
return -1;
}
else if (L->length>=ListSize)/*在插入元素之前，判断顺序表是否已经满，不能插入元素*/
{
cout << "顺序表已经满，不能插入元素。" << endl;
return 0;
}
else
{
for (j = L->length; j >= i; j--)
/*将第i个位置以后的元素依次后移*/
{
L->list[j] = L->list[j - 1];
}
L->list[i - 1] = e;
L->length = L->length + 1;
return 1;
}
}
/*删除操作，删除第i个元素*/
int DeleteList(SeqList *L, int i, DataType *e)
{
int j;
if (L->length<=0)
{
cout << "顺序表表已空，不能进行删除！" << endl;
return 0;
}
else if (i<1||i>L->length)
{
cout << "删除位置不合适！" << endl;
return -1;
}
else
{
*e = L->list[i - 1];
for (j = i; j <= L->length - 1;j++)
{
L->list[j - 1] = L->list[j];
}
L->length = L->length - 1;
return 1;
}
}
/*求线性表的长度*/
int ListLength(SeqList L)
{
return L.length;
}
/*清空顺序表*/
void ClearList(SeqList *L)
{
L->length = 0;
}
(3)顺序存储合并扩展阅读
线性表的顺序存储结构，就是在内存中找到一块空间，通过占位的方式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空间中。
既然线性表的每个数据元素的类型相同，所以C语言（其他语言也相同）用一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。
顺序存储的属性
三个属性：
1、存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。
2、线性表的最大存储容量：数组的长度MaxSize.
3、线性表的当前长度：length。
4. 将两个顺序存储的有序表合并成一个有序表
将两个顺序存储的有序表合并成一个有序表的代码如下：
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define MaxSize 50
typedef struct
{
int data[MaxSize];
int length;
}SqList;
void ListInsert(SqList *L,int i,int e)
{
int j;
if(i<1||i>L->length+1)
exit(-1);
if(L->length>=MaxSize)
exit(-1);
for(j=L->length;j>=i;j--)
L->data[j]=L->data[j-1];
L->data[i-1]=e;
L->length++;
}
void DispList(SqList *L)
{
int i;
for(i=0;i<L->length;i++)
printf("%d ",L->data[i]);
printf("
");
}
void Exchange(SqList *A,SqList *B,SqList *C)
{
int i=0,j=0,k=0;
while(i<A->length&&j<B->length)
{
if(A->data[i]<B->data[j])
C->data[k++]=A->data[i++];
else if(A->data[i]>B->data[j])
C->data[k++]=B->data[j++];
}
while(i<A->length)
C->data[k++]=A->data[i++];
while(j<B->length)
C->data[k++]=B->data[j++];
C->length=k;
}
void main()
{
SqList *A,*B,*C;
A=(SqList*)malloc(sizeof(SqList));
A->length=0;
B=(SqList*)malloc(sizeof(SqList));
B->length=0;
C=(SqList*)malloc(sizeof(SqList));
C->length=0;
ListInsert(A,1,1);
ListInsert(A,2,3);
ListInsert(A,3,5);
ListInsert(A,4,7);
ListInsert(A,5,9);
ListInsert(B,1,2);
ListInsert(B,2,4);
ListInsert(B,3,6);
ListInsert(B,4,8);
ListInsert(B,5,10);
ListInsert(B,6,12);
Exchange(A,B,C);
printf("顺序表A：");
DispList(A);
printf("顺序表B：");
DispList(B);
printf("顺序表C：");
DispList(C);
}
(4)顺序存储合并扩展阅读：
第二种解法的核心代码
bool Merge(SeqList A, SeqList B, SeqList &C)
{//C为合并后的顺序表
if (A.length + B.length > C.MaxSize) return false;//超出最大存储空间
int i = 0, j = 0, k = 0;
while( i < A.length && j < B.length)
{
if (A.data[i] <= B.data[j])
C.data[k++] = A.data[i++];
else
C.data[k++] = B.data[j++];
}
while (i < A.length) C.data[k++] = A.data[i++];
while (j < B.length) C.data[k++] = B.data[j++];
C.length = k;
return true;
}
5. 数据结构（C语言版）：顺序存储结构上编程实现将两个有序表合成一个有序表，要完整程序，包括MAIN函数。
#include<stdio.h>
void merger(int d1[10],int t1,int d2[10],int t2,int result[20])
{ int k1=0,k2=0,k=0;
while(k1<t1 && k2<t2)
{ if(d1[k1]<d2[k2])
result[k++]=d1[k1++];
else
result[k++]=d2[k2++];
}
if(k1<t1)
for(k2=k1;k2<t1;k2++)
result[k++]=d1[k2];
else
for(k1=k2;k1<t2;k1++)
result[k++]=d2[k1];
}
int main()
{ int data1[10]={3,5,7,9,12,19,25,26,27},data2[10]={1,4,6,8,9,15,17,21},r[20];
int total1=6,total2=8,k;
merger(data1,total1,data2,total2,r);
for(k=0; k<total1+total2;k++)
printf("%d. %d\n",k+1,r[k]);
printf("\ntotal1=%d total2=%d",total1,total2) ;
system("pause");
}
6. 数据结构 c语言编写顺序表合并
/*
**太多错误了，包括语法和逻辑上的错误都有。。。。
**我修改了一下，现在可以了。
**请注意，下面我说的字符串均指纯数字字符串，这个程序中是以字符方式来处理成数字的
**输入的时候，第一次输入的必须是顺序串（否则还要加一个排序算法），
**不是顺序串的话输入也没有问题，但是第一个字符串不会被排序
**第二个字符串不要求顺序。因为是一个个插入第一个字符串的对应位置
**而且这里输入的会被按照单个字符来录入
**（即数组元素只能为0~9中的任一个整数），
**如果想要以多位数（比如一个数组元素为67、345、2351等）来作为一个数组元素，
**则要修改判断输入的部分（我只是根据你的来改的，不知道是不是你想要的结果）。
*/
#include<iostream>
//可去掉#include<stdlib.h>
using namespace std;
typedef int datatype;
#define maxsize 1024
typedef struct
{
datatype data[maxsize];
int last;
}sequenlist;
sequenlist *combine (sequenlist *scrptr,sequenlist *sinkptr);//添加函数声明
void main ()
{
sequenlist *Aptr,*Bptr,*Cptr;
Aptr = new sequenlist;//注意，要申请空间，初始化指针，下同
Bptr = new sequenlist;
Cptr = NULL;
//Cptr不用申请空间，因为后面有返回指针，这里初始为NULL，以防非法操作
char ch; //注意这里
int i=0;
//注意这里
do
{
ch = getchar();
Aptr->data[i]= ch - '0';//*Aptr.data[i]——>Aptr->data[i]
i++;
}
while (ch!='\n' && i<maxsize);
Aptr->last = i-1; //添加这句
i = 0;
do
{
ch = getchar();
Bptr->data[i]= ch - '0';//*Aptr.data[i]——>Aptr->data[i]
i++;
}
while (ch!='\n' && i<maxsize);
Bptr->last = i-1;
Cptr=combine(Aptr,Bptr);//注意这里
for(i=0;i<Cptr->last;i++)//注意
printf("%d",Cptr->data[i]);
delete Aptr;//前面new的，现在要delete，否则内存泄漏（虽然编译可通过）
delete Bptr;
Aptr = Bptr = Cptr = NULL;//这句可要可不要，只是一个习惯，即delete掉的指针要置空，以防非法操作。
}
void insertlist (sequenlist *lstptr,int x)//istpter——>lstptr
{
int i=0,j=0;
//没有do....until ();应用while
while(i<lstptr->last)
{
if (x<=lstptr->data[i])
break;
else i++;
}
if (lstptr->last>=maxsize)
{
printf ("overflow");
exit(0);//exit (overflow);overflow不是一个整数值
}
for (j=lstptr->last-1;j>=i;j--)//注意，j=lstptr->last-1
{
lstptr->data[j+1]=lstptr->data[j];
// lstptr->data[i]=x;
// lstptr->last++;
//这两句要放for外面
}
lstptr->data[i]=x;
lstptr->last++;
}
sequenlist *combine (sequenlist *scrptr,sequenlist *sinkptr)
{
//int x;不需要
int j;
for (j=0;j<sinkptr->last;j++)
insertlist (scrptr,sinkptr->data[j]);
return scrptr;//注意
}
打字不易，如满意，望采纳。
7. 将两个长度不超过10的有序整数集合A和B合并为一个有序整数集合C。请用数组（顺序存储结构）表示这两个集合
#include<stdio.h>
void read(int a[],int n)
{
int i;
for(i=0;i<n;i++)scanf("%d",&a[i]);
}
int main()
{
int a[1000],b[1000],c[2000];
int n,m,j,i,k=0;
scanf("%d%d",&n,&m);//输入两个数组的长度
read(a,n);//读入a数组
read(b,n);//读入b数组
i=0;
j=0;
while(i<n&&j<m)
{
while(i<n&&j<m&&a[i]<=b[j])
{
c[k++]=a[i];
i++;
}
while(i<n&&j<m&&b[j]<=a[i])
{
c[k++]=b[j];
j++;
}
}
while(i<n)
{
c[k++]=a[i];
i++;
}
while(j<m)
{
c[k++]=b[j];
j++;
}
for(i=0;i<k;i++)printf("%d ",c[i]);
puts("");
return 0;
}
8. 怎么将两个顺序存储的有序表合并成一个有序表
具体代码如下：
#include<stdio.h>
#include<stdlib.h>
#define MAX 40
typedef struct
{
int data[MAX];
int length;
}LinkList;
void Initial_List(LinkList * &l,int n)//初始化顺序表
{
int i=0;
l=(LinkList *)malloc(sizeof(LinkList));
l->length = 0;
for(;i<n;i++)
scanf("%d",l->data+i);
l->length = n;
}
void Link(LinkList *l1,LinkList *l2,LinkList * &l3)//连接顺序表
{
int i,j;
l3=(LinkList *)malloc(sizeof(LinkList));
l3->length = l1->length + l2->length;
for(i=0;i<l3->length;i++)
{
if(i<l1->length)
{
l3->data[i] = l1->data[i];
}
else
{
l3->data[i] = l2->data[i%(l1->length)];
}
}
for(i=0;i<l3->length;i++)
{
for(j=i+1;j<l3->length;j++)
{
if(l3->data[i]>l3->data[j])
{
int temp=l3->data[i];
l3->data[i]=l3->data[j];
l3->data[j]=temp;
}
}
}
}
void Disp_List(LinkList *l)
{
int i=0;
printf("output: ");
for(;i<l->length;i++)
printf("%d ",l->data[i]);
printf(" ");
}
int main()
{
LinkList *l1,*l2,*l3;
int n;
printf("请输入第一个序列的元素个数: ");
scanf("%d",&n);
printf("请输入第一个序列的所有元素: ");
Initial_List(l1,n);
printf("请输入第二个序列的元素个数: ");
scanf("%d",&n);
printf("请输入第二个序列的所有元素: ");
Initial_List(l2,n);
Link(l1,l2,l3);
Disp_List(l3);
return 0;
}
9. 关于两顺序表合并成一个顺序表的操作，怎么用C写，要注释，刚入门的菜鸟。
将两个有序数组合并成一个有序数组，方法请参考归并排序中的合并操作。