如何用顺序表实现有序表的合并操作？
- 内容介绍
- 文章标签
- 相关推荐
本文共计785个文字，预计阅读时间需要4分钟。
问题描述：已知线性表La和Lb中的数据元素按值非递减有序排列，现要将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。
已知数据：La=(1, 7, 8)Lb=(2, 4, 6, 8, 10, 11)
结果：Lc=(1, 2, 4, 6, 7, 8, 10, 11)
问题描述
已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。
La=(1,7,8) Lb=(2,4,6,8,10,11)→Lc=(1,2,4,6,7,8,8,10,11)
算法步骤
（1）创建一个空表Lc
（2）依次从La或Lb中摘取元素值较小的结点插入到表Lc的最后，直至其中一个表变空为止
（3）继续将La或Lb其中一个表的剩余结点插入在Lc表的最后
算法实现
void MergeList_Sq(SqList LA,SqList LB,SqList &LC)
{
pa=LA.elem;
pb=LB.elem;//指针pa和pb的初值分别指向两个表的第一个元素
LC.length=LA.length+LB.length;//新表长度为待合并两表的长度之和
LC.elem=new ElemType[LC.length];//为合并后的新表分配一个存储空间
pc=LC.elem;//指针pc指向新表的第一个元素
pa_last=LA.elem+LA.length-1;//指针pa_last指向LA的最后一个元素
pb_last=LB.elem+LB.length-1;//指针pb_last指向LB的最后一个元素
while(pa<=pa_last&&pb<=pb_last)//两个表都非空
{
if(*pa<*pb)//依次摘取两表中值较小的结点
*pc++=*pa++;
else
*pc++=*pb++;
}
while(pa<=pa_last)
*pc++=*pa++;//LB表已到达表尾，将LA中的剩余元素加入LC
while(pb<=pb_last)//LA表已到达表尾，将LB中剩余元素加入LC
*pc++=*pb++;
}
算法的时间复杂度是：O（ListLength(La)+ListLength(Lb)）
算法的空间复杂度是：O（ListLength(La)+ListLength(Lb)）
代码实现
#include<stdio.h>
#include<stdlib.h>
typedef int Status;
typedef int ElemType;
#define LIST_INIT_SIZE 100 //顺序表存储空间的初始分配量
#define LISTINCREMENT 10 //顺序表存储空间的分配增量
#define OVERFLOW -2 //堆栈上溢
typedef struct{
ElemType *elem;//存储空间基地址
int length; //当前长度
int listsize; //当前分配的存储空间大小
}SqList;
Status InitList_Sq(SqList &L){
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem){
exit(OVERFLOW);
}
L.length=0;
L.listsize=LIST_INIT_SIZE;
return 1;
}
Status ListInsert_Sq(SqList &L,int i,ElemType e){
if(i<1||i>L.length+1){
return 0;
}
ElemType *newbase;
ElemType *p,*q;
if(L.length>=L.listsize){
newbase=(ElemType*)realloc(L.elem,
(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase){
exit(OVERFLOW);
}
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;p--){
*(p+1)=*p;
}
*q=e;
L.length++;
return 1;
}
void PrintElem(ElemType e){
printf("%d ", e);
}
Status ListTraverse_Sq(SqList L,void (visit)(ElemType)){
for(int i=0;i<L.length;i++){
visit(L.elem[i]);
}
printf("\n");
return 1;
}
int ListLength_Sq(SqList L){
return L.length;
}
Status GetElem_Sq(SqList L,int i,ElemType *e){
if(i<1||i>L.length){
return 0;
}
*e=L.elem[i-1];
return 1;
}
void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){
ElemType *pa,*pb,*pc,*pa_last,*pb_last;
pa=La.elem;
pb=Lb.elem;
Lc.listsize=Lc.length=La.length+Lb.length;
pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));
if(!Lc.elem){
exit(OVERFLOW);
}
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
while(pa<=pa_last&&pb<=pb_last){ // 归并
if(*pa<=*pb){
*pc++=*pa++;
}else{
*pc++=*pb++;
}
}
while(pa<=pa_last){
*pc++=*pa++; // 插入La的剩余元素
}
while(pb<=pb_last){
*pc++=*pb++; // 插入Lb的剩余元素
}
}
int main(){
SqList La,Lb,Lc;
ElemType a[3]={1,7,8};
ElemType b[6]={2,4,6,8,10,11};
int i;
InitList_Sq(La); //初始化La
for(i=1;i<=3;i++){
ListInsert_Sq(La,i,a[i-1]);
}
InitList_Sq(Lb); //初始化Lb
for(i=1;i<=6; i++){
ListInsert_Sq(Lb,i,b[i-1]);
}
printf("La= "); ListTraverse_Sq(La, PrintElem);
printf("Lb= "); ListTraverse_Sq(Lb, PrintElem);
printf("合并La和Lb：Lc= ");
MergeList_Sq(La,Lb,Lc);
ListTraverse_Sq(Lc,PrintElem);
return 0;
}
本文共计785个文字，预计阅读时间需要4分钟。
问题描述：已知线性表La和Lb中的数据元素按值非递减有序排列，现要将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。
已知数据：La=(1, 7, 8)Lb=(2, 4, 6, 8, 10, 11)
结果：Lc=(1, 2, 4, 6, 7, 8, 10, 11)
问题描述
已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。
La=(1,7,8) Lb=(2,4,6,8,10,11)→Lc=(1,2,4,6,7,8,8,10,11)
算法步骤
（1）创建一个空表Lc
（2）依次从La或Lb中摘取元素值较小的结点插入到表Lc的最后，直至其中一个表变空为止
（3）继续将La或Lb其中一个表的剩余结点插入在Lc表的最后
算法实现
void MergeList_Sq(SqList LA,SqList LB,SqList &LC)
{
pa=LA.elem;
pb=LB.elem;//指针pa和pb的初值分别指向两个表的第一个元素
LC.length=LA.length+LB.length;//新表长度为待合并两表的长度之和
LC.elem=new ElemType[LC.length];//为合并后的新表分配一个存储空间
pc=LC.elem;//指针pc指向新表的第一个元素
pa_last=LA.elem+LA.length-1;//指针pa_last指向LA的最后一个元素
pb_last=LB.elem+LB.length-1;//指针pb_last指向LB的最后一个元素
while(pa<=pa_last&&pb<=pb_last)//两个表都非空
{
if(*pa<*pb)//依次摘取两表中值较小的结点
*pc++=*pa++;
else
*pc++=*pb++;
}
while(pa<=pa_last)
*pc++=*pa++;//LB表已到达表尾，将LA中的剩余元素加入LC
while(pb<=pb_last)//LA表已到达表尾，将LB中剩余元素加入LC
*pc++=*pb++;
}
算法的时间复杂度是：O（ListLength(La)+ListLength(Lb)）
算法的空间复杂度是：O（ListLength(La)+ListLength(Lb)）
代码实现
#include<stdio.h>
#include<stdlib.h>
typedef int Status;
typedef int ElemType;
#define LIST_INIT_SIZE 100 //顺序表存储空间的初始分配量
#define LISTINCREMENT 10 //顺序表存储空间的分配增量
#define OVERFLOW -2 //堆栈上溢
typedef struct{
ElemType *elem;//存储空间基地址
int length; //当前长度
int listsize; //当前分配的存储空间大小
}SqList;
Status InitList_Sq(SqList &L){
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem){
exit(OVERFLOW);
}
L.length=0;
L.listsize=LIST_INIT_SIZE;
return 1;
}
Status ListInsert_Sq(SqList &L,int i,ElemType e){
if(i<1||i>L.length+1){
return 0;
}
ElemType *newbase;
ElemType *p,*q;
if(L.length>=L.listsize){
newbase=(ElemType*)realloc(L.elem,
(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase){
exit(OVERFLOW);
}
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;p--){
*(p+1)=*p;
}
*q=e;
L.length++;
return 1;
}
void PrintElem(ElemType e){
printf("%d ", e);
}
Status ListTraverse_Sq(SqList L,void (visit)(ElemType)){
for(int i=0;i<L.length;i++){
visit(L.elem[i]);
}
printf("\n");
return 1;
}
int ListLength_Sq(SqList L){
return L.length;
}
Status GetElem_Sq(SqList L,int i,ElemType *e){
if(i<1||i>L.length){
return 0;
}
*e=L.elem[i-1];
return 1;
}
void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){
ElemType *pa,*pb,*pc,*pa_last,*pb_last;
pa=La.elem;
pb=Lb.elem;
Lc.listsize=Lc.length=La.length+Lb.length;
pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));
if(!Lc.elem){
exit(OVERFLOW);
}
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
while(pa<=pa_last&&pb<=pb_last){ // 归并
if(*pa<=*pb){
*pc++=*pa++;
}else{
*pc++=*pb++;
}
}
while(pa<=pa_last){
*pc++=*pa++; // 插入La的剩余元素
}
while(pb<=pb_last){
*pc++=*pb++; // 插入Lb的剩余元素
}
}
int main(){
SqList La,Lb,Lc;
ElemType a[3]={1,7,8};
ElemType b[6]={2,4,6,8,10,11};
int i;
InitList_Sq(La); //初始化La
for(i=1;i<=3;i++){
ListInsert_Sq(La,i,a[i-1]);
}
InitList_Sq(Lb); //初始化Lb
for(i=1;i<=6; i++){
ListInsert_Sq(Lb,i,b[i-1]);
}
printf("La= "); ListTraverse_Sq(La, PrintElem);
printf("Lb= "); ListTraverse_Sq(Lb, PrintElem);
printf("合并La和Lb：Lc= ");
MergeList_Sq(La,Lb,Lc);
ListTraverse_Sq(Lc,PrintElem);
return 0;
}