实验内容:
有两个有序线性表,分别为A1(2,4,6,7,10 )和A2(1,3,5,6,7,12 ),试将其合并为一个按从小到大顺序的线性表,如A3(1,2,3,4,5,6,6,7,7,10,12),并遍历输出其结果。
按要求编程实现:
1、采用顺序表实现操作;
2、采用单链表实现 操作。
计算机小白编程无能,我只做了顺序表的一个源文件和头文件,但是主函数编着就各种问题了,求帮助!
头文件:
#ifndef SeqList_H
#define SeqList_H
const int MaxSize=20; //线性表最多有20个元素
template <class T> //定义模板类SeqList
class SeqList
{
public:
SeqList( ) {length=0;} //无参构造函数
SeqList(T a[ ], int n); //有参构造函数
~SeqList( ) { } //析构函数为空
int Length( ) {return length;} //求线性表的长度
T Get(int i); //按位查找,取线性表的第i个元素
int Locate(T x ); //按值查找,求线性表中值为x的元素序号
void Insert(int i, T x); //在线性表中第i个位置插入值为x的元素
T Delete(int i); //删除线性表的第i个元素
void PrintList( ); //遍历线性表,按序号依次输出各元素
private:
T data[MaxSize]; //存放数据元素的数组
int length; //线性表的长度
};
#endif
源文件#include<iostream>using namespace std;#include "SeqList.h"template <class T> SeqList:: SeqList(T a[ ], int n){ if (n>MaxSize) throw "参数非法"; for (i=0; i<n; i++) data[i]=a[i]; length=n;}template <class T> void SeqList::Insert(int i, T x){ if (length>=MaxSize) throw "上溢"; if (i<1 | | i>length+1) throw "位置";for (j=length; j>=i; j--) data[j]=data[j-1]; data[i-1]=x;length++;}
判断
while(pa->next!=null&&pb->next!=null)
{
if(pa->data>pb->data) pb->data插入到新建c链表的的表尾。pb=pb->next;
if(pa->data<pb->data) pa->data 插入c表为。 pa=pa->next;
}
最后没查完的链表剩余部分整体连接到c的表尾。用指针。很简单。
这是有序表的。你想用泛型编程的话,改造一下就行了。
#include<iostream>
const int MaxLen=100;
typedef struct
{
int data[MaxLen];
int Len;
}seqlist;
void initial_list(seqlist *L)//初始化;
{
L->Len=0;
}
void list_getdata(seqlist *L) //输入线性表
{
std::cout<<"输入线性表长度:";
std::cin>>L->Len;
std::cout<<"输入数据:" ;
for(int i=0;i<L->Len;i++)
std::cin>>L->data[i];
}
int list_Len(seqlist L)//获得线性表的长度;
{
std::cout<<"线性表长度为:" ;
return(L.Len);
}
void get_element(seqlist L,int i) //找到第i个数据 ;
{
int x;
if(i<1||i>L.Len)
std::cout<<"超出范围,错误"<<std::endl;
else x=L.data[i-1];
std::cout<<"第"<<i<<"个数据为:" ;
std::cout<<x<<std::endl;
}
void get_locate(seqlist L,int x)//找到值等于x的数据位于线性表的第几个元素;
{
for(int i=0;i<L.Len;i++)
{
if(L.data[i]==x)
std::cout<<i+1;
else
std::cout<<"error:无此数据";
}
}
void list_insert(seqlist *L,int i,int x)//将x插入线性表的第i个位置;
{
int j;
if(L->Len==MaxLen)
std::cout<<"溢出"<<std::endl;
else if(i<1||i>L->Len+1)
std::cout<<"插入位置错误"<<std::endl;
else
{
for(j=L->Len;j>i-1;j--)
L->data[j]=L->data[j-1];
L->data[i-1]=x;
L->Len++;
}
}
void list_delete(seqlist *L,int i)//删除第i个元素;
{
if(L->Len<=0)
std::cout<<"溢出出错"<<std::endl;
else if(i>L->Len||i<1)
std::cout<<"删除位置出错"<<std::endl;
else
for(int j=i-1;j<L->Len-1;j++)
L->data[j]=L->data[j+1];
L->Len--;
}
void list_print(seqlist L)//输出线性表;
{
std::cout<<"线性表为:"<<std::endl;
for(int i=0;i<L.Len;i++)
std::cout<<L.data[i]<<' ';
}
bool list_b_include_a(seqlist *A,seqlist *B)//判断包含关系;
{
int i,j;
bool suc;
for(i=0;i<A->Len;i++)
{
j=0;suc=0;
while(j<B->Len&&suc==0)
if(A->data[i]==B->data[j])
suc=1;
else j++;
if(suc==0) return false;
}
if(suc==1) return true;
}
bool list_b_include_a_YouXu(seqlist *A,seqlist*B)//判断有序数列包含关系
{
int ia=0,ib=0;
while(ia<A->Len&&ib<B->Len)
if(A->data[ia]==B->data[ib])
{
ia++;
ib++;
}
else if(A->data[ia]>B->data[ib]) ib++;
else return false;
if(ia==A->Len) return true;
else return false;
}
void list_combin(seqlist *A,seqlist *B)//合并两个表
{
int m=A->Len;
for(int i=0;i<B->Len;i++)
{
list_insert(A,m+i+1,B->data[i]);
}
list_print(*A);
}
void list_combin_YouXu(seqlist *A,seqlist *B,seqlist *C)//合并有序数列
{
int ia=0,ib=0,ic=0;
while(ia<A->Len&&ib<B->Len)
if(A->data[ia]==B->data[ib])
{
C->data[ic++]=A->data[ia++];
C->data[ic++]=B->data[ib++];
}
else if(A->data[ia]<B->data[ib])
C->data[ic++]=A->data[ia++];
else C->data[ic++]=B->data[ib++];
while(ia<A->Len) C->data[ic++]=A->data[ia++];
while(ib<B->Len) C->data[ic++]=B->data[ib++];
C->Len=ic;
}
int main()
{
/*seqlist L1;
initial_list(&L1);
std::cout<<list_Len(L1)<<std::endl;
list_getdata(&L1);
//std::cout<<std::endl;
std::cout<<list_Len(L1);
std::cout<<std::endl;
get_element(L1,3);
list_print(L1);
list_insert(&L1,4,127);
std::cout<<std::endl;
list_print(L1);
list_delete(&L1,2);
std::cout<<'\n';
list_print(L1);
*/
/* int i=1; ;
while(i==1)
{
std::cout<<"**********判断La是否是Lb的子集***********"<<std::endl;
seqlist La,Lb;
list_getdata(&La);//La={1,3,8}
list_print(La);
list_getdata(&Lb);//Lb={2,1,8,6,9,3}
list_print(Lb);
std::cout<<list_b_include_a(&La,&Lb);
std::cout<<"是否继续?"<<"1:是 2:否"<<std::endl;
std::cin>>i;
} */
std::cout<<"合并俩个线性表"<<std::endl;
seqlist L1,L2,L3;
list_getdata(&L1);
list_getdata(&L2);
//list_combin(&L1,&L2);
list_combin_YouXu(&L1,&L2,&L3);
list_print(L3);
return 0;
}