设顺序表a中的数据元素递增有序，试设计一个算法，将x插入到顺序表的适当位置，以保持该表的有序性。

设顺序表a中的数据元素递增有序，试设计一个算法，将x插入到顺序表的适当位置，以保持该表的有序性。

//1.设顺序表a中的数据元素递增有序，试设计一个算法，将x插入到顺序表的适当位置，以保持该表的有序性。
#include<iostream> 
using namespace std;
typedef int T;  
using namespace std;  


//类的定义 
template <class T>  
class SqList   //顺序表类 
{  
private:  
        T *elem; //表首址 
int length; //表长 
int listsize;//表容量 
public:  
        SqList(int m) ;//构造函数， 创建容量为m的空表 
        ~SqList();//析构函数，删除表空间 
void CreateList(int n);//创建具有n个元素的线性表 
void Insert(int i,T e);//在表中第i个位置插入元素 
int Locate(T e);//元素定位 
void ListDisp();//输出表元素 
};  
//类的实现 
template<class T>  
SqList<T>::SqList(int m)  
{//构建函数，创建一表容量为m的空表 
    elem=new T[m];// 申请表空间 
    length=0;// 空表，表长为0 
    listsize=m;//表容量为m 
}  

template<class T>  
SqList<T>::~SqList()//析构函数 
{//释放表空间 
delete [] elem;  
    length=0;   
    listsize=0;   
}  

template<class T>  
void SqList<T>::CreateList(int n)  
{//创建表长度为n的顺序表 
if(n>listsize) throw"参数非法";  
int step,chushi;  
cout<<"请依次输入初始值和步长：";  
cin>>chushi>>step;  
for(int i=1;i<=n;i++)  
        elem[i-1]=chushi+(i-1)*step;  
    length=n;  
}  

template<class T>  
void SqList<T>::Insert (int i,T e)  
{// 在第i个位置插入元素，如不能插入，显示异常信息 
if(length>=listsize) throw "上溢";  
if(i<1||i>length+1) throw "插入位置异常";  
for(int j=length;j>=i;j--)  
        elem[j]=elem[j-1];  
    elem[i-1]=e;  
    length++;  
}  

template<class T>  
int SqList<T>::Locate (const T e)  
{// 元素定位，若找到，返回该元素在表中的位序；末找到，返回0。 
for(int i=0;i<length;i++)  
if(elem[i]<=e&&elem[i+1]>=e) return i+1;  
return 0;  
}  

template <class T>  
void SqList<T>::ListDisp()  
{//显示表内容 
for(int i=0;i<length;i++)  
    {  
cout<<elem[i]<<"\t";  

    }  
cout<<endl;  
}  

//主函数 
void main()  
{  
int n,I;  
    T e;  
    SqList<int> L(20);  
cout<<"请输入要创建的顺序表中元素个数:";  
cin>>n;  
cout<<endl;  
    L.CreateList(n);  
cout<<endl;     
    L.ListDisp();  
cout<<endl;  
cout<<"请输入插入元素的值:";  
cin>>e;  
    I=L.Locate(e);  
cout<<endl;  
    L.Insert(I+1,e);  //返回的I为插入数e的前一个数的位置 
    L.ListDisp();  
cout<<endl;  
}