数据结构第二章线性表（一）①顺序表插入并递增有序（已知顺序表L中的元素递增有序排列，设计算法将元素x插入到表L中并保持表L仍递增有序）②删除顺序表元素③顺序表逆置

1、顺序表插入并递增有序

已知顺序表L中的元素递增有序排列，设计算法将元素x插入到表L中并保持表L仍递增有序。

/*顺序表插入并递增有序
已知顺序表L中的元素递增有序排列，设计算法将
元素x插入到表L中并保持表L仍递增有序。
*/
#include <iostream>
using namespace std;

const int MaxSize=100;
typedef int DataType;
DataType data[MaxSize];
int length=0;

void insertList(DataType elem)
{
   int i;
   for( i=length-1;i>=0&&data[i]>elem;i--)
   data[i+1]=data[i];
   data[i+1]=elem;
   length++;

}
void show()
{
    for(int i=0;i<length;++i)
        cout<<data[i]<<" ";
    cout<<endl;

}
int main()
{
    cin>>length;
    for(int i=0;i<length;++i)
        cin>>data[i];
    DataType x;
    cin>>x;
    insertList(x);
    show();
    return 0;
}

2、删除顺序表元素

在顺序表中删除所有元素值为x的元素，要求空间复杂度为O(1)。

/* 删除顺序表元素
在顺序表中删除所有元素值为x的元素，要求空间复杂度为O(1)。
 */
#include <iostream>
using namespace std;

const int MaxSize=100;
typedef int DataType;
DataType data[MaxSize];
int length;

void deleteList(DataType elem)
{
    int i=0;
    while(i<length&&data[i]!=elem)
        i++;
    for(int j=i+1;j<length;j++)
        if(data[j]!=elem)
            data[i++]=data[j];
    length=i;
}
void deleteList2(int elem)
{
    int i=0,j=0;
    while(i<length)
    {
        if(data[i]==elem)
            j++;
        else data[i-j]=data[i];
        i++;
    }
    length-=j;
}
void show()
{
    for(int i=0;i<length;++i)
        cout<<data[i]<<" ";
    cout<<endl;
}
int main()
{
    cin>>length;
    for(int i=0;i<length;++i)
        cin>>data[i];
    DataType x;
    cin>>x;
    deleteList(x);
    show();
    return 0;
}

3、顺序表逆置

以顺序表存储非空线性表，编写一个实现线性表就地逆置的算法。空间复杂度均是O(1)。

/* 
顺序表逆置
以顺序表存储非空线性表，编写一个实现线性表
就地逆置的算法。空间复杂度均是O(1)。
 */
#include <iostream>
using namespace std;

const int MaxSize=100;
typedef int DataType;
DataType data[MaxSize];
int length;

void reverseList( )
{
    int temp;
    for(int i=0;i<length/2;i++)
    {  temp=data[i];
       data[i]=data[length-i-1];
       data[length-i-1]=temp;
    }

}
void show()
{
    for(int i=0;i<length;++i)
        cout<<data[i]<<" ";
    cout<<endl;
}
int main()
{
    cin>>length;
    for(int i=0;i<length;++i)
        cin>>data[i];
    reverseList();
    show();
    return 0;
}