順序存儲合並
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寫，要注釋，剛入門的菜鳥。
將兩個有序數組合並成一個有序數組，方法請參考歸並排序中的合並操作。