线性表合并.cpp

使用C语言变成

#include <iostream.h>
#include <stdlib.h>
#include <iomanip.h>
#define MaxSize 100
typedef int datatype;
struct List //线性表结构定义
{datatype data[MaxSize];
 int size;
};
void InitList(List &L)//初始化线性表
{
    L.size=0;
}

void ClearList(List &L)//清空线性表
    {
    L.size=0;
    }

int ListLength(List &L)//线性表长度
    {
    return L.size;
    }

int ListEmpty(List &L)//判断线性表是否为空
    {
    return(L.size==0);
    }


datatype GetElem(List &L,int pos)//取线性表中的元素
  {
    if(pos<1 || pos>L.size)//若pos越界则退出程序
    {
    cout<<"pos is out range!"<<endl;
    exit(1);
    }
    return L.data[pos-1];
}//返回线性表中第pos个元素的值


void InsertRear(List &L, datatype item)//在线性表末尾添加元素
  {
    if(L.size==MaxSize)  //若表已满，则停止插入，退出程序运行
    {
    cout<<"List overflow!"<<endl;
    exit(1);
    }
    L.data[L.size]=item;//把item的值插人到表尾，即写入到最后一个元素的后一个位置上
    L.size++;
    }


void InsertFront(List &L,datatype item)//表头插入
{
    if(L.size==MaxSize)
    {
    cout<<"List overflow!"<<endl;
    exit(1);
    }
    for(int i=L.size-1;i>=0;i--)
    L.data[i+1]=L.data[i];
    L.data[0]=item;
    L.size++;
}



void TraverseList(List &L)//遍历线性表
{
    for(int i=0;i<L.size;i++)
    cout<<L.data[i]<<" ";
    cout<<endl;
	cout<<"\n\n";
 }


int Delete(List &L,  int i)//删除线性表中第i个元素
   { if(i<1||i>L.size) {
            cout<<"Index is out range!"<<endl;
            exit (1);
    }
     datatype x;
     x=L.data[i-1];
     for(int j=i-1; j<L.size-1; j++)
            L.data[j] = L.data[j+1];
     L. size --;
     return x;
}


void Insert(List &L, int i,  datatype x)//在线性表第i个位置插入元素
{
      if(i<1||i>L.size+1) {
             cout<<"Index is out range:"<<endl;
             exit (1);}
      if (L.size==MaxSize)
     {
             cout<<"List overflow"<<endl;
             exit (1);
     }
      for(int j=L.size-1; j>=i-1; j--)
             L.data[j+1] =L.data[j];
      L.data[i-1]=x;          
      L.size++;
}

void Merge(List &L1,List &L2,List &L)   //两个表并一个表 
{
	L.size=L1.size+L2.size;
    int i=0,j=0,k=0;
	while(i<=L1.size-1 && j<=L2.size-1)
		if(L1.data[i]>=L2.data[j])
		{ 
			L.data[k]=L1.data[i];
			i++;
			k++;
		}
		else
		{
			L.data[k]=L2.data[j];
			j++;
			k++;
		}
		while(i<=L1.size-1)
		{ 
			L.data[k]=L1.data[i];
			i++;
			k++;
		}
		while(j<=L2.size-1)
		{
			L.data[k]=L2.data[j];
			j++;
			k++;
		}

}

void main()//主程序
{List La,Lb,Lc;
 int n,i,x;
 InitList(La);
 InitList(Lb);
 InitList(Lc);
  cout<<"请输入第一张线性表元素个数:";
  cin>>n;
   if(n>MaxSize)
  {
	  cout<<"list overflow!\n";
	  return;
  }	
  cout<<"从键盘输入线性表元素:";
      for(i=1;i<=n;i++)
       {
        cin>>x;
        InsertRear(La,x);
       }
	
   cout<<endl;
   cout<<"现有La为:";
   TraverseList(La);

cout<<"请输入第二张线性表元素个数:";
  cin>>n;
   if(n>MaxSize)
  {
	  cout<<"list overflow!\n";
	  return;
  }	
  cout<<"从键盘输入线性表元素:";
      for(i=1;i<=n;i++)
       {
        cin>>x;
        InsertRear(Lb,x);
       }
	
   cout<<endl;
   cout<<"现在第一张线性表元素为:";
   TraverseList(Lb);

   Merge(La,Lb,Lc);
cout<<"合并后新的线性表为:";
   TraverseList(Lc);

}