编写一个算法，把一个顺序表分拆成两个部分，使顺序表中不大于0的元素位于左端，大于0的元素位于右端。要求不占用额外的存储空间。例如，顺序表（88，－9，－28，19，－31，22，－50，62，－76）经拆分后变成（－76，－9，－28，－50，－31，22，19，62，88）。

Question

 编写一个算法，把一个顺序表分拆成两个部分，使顺序表中不大于0的元素位于左端，大于0的元素位于右端。要求不占用额外的存储空间。例如，顺序表（88，－9，－28，19，－31，22，－50，62，－76）经拆分后变成（－76，－9，－28，－50，－31，22，19，62，88）。用c++实现

Answer 1

#include <stdio.h>
#include <stdlib.h>
#define ListSize 200
typedef int DataType;
#include "SeqList.h"
void SplitSepList(SeqList *L);
void main()
{
    int i,flag,n;
    DataType e;
    SeqList L;
    int a[]={88,-9,-28,19,-31,22,-50,62,-76};
    InitList(&L);                //初始化顺序表l
    n=sizeof(a)/sizeof(a[0]);
    for(i=1;i<=n;i++)   //将数组a的元素插入顺序表L中
    {
        if(InsertList(&L,i,a[i-1])==0)
        {
            printf("位置不合法");
            return;
        }
    }
    printf("顺序表L中的元素:\n");
    for(i=1;i<=L.length;i++)  //输出顺序表L中的每个元素
    {
        flag=GetElem(L,i,&e);  //返回顺序表L中的每个元素到e中
        if(flag==1)
            printf("%4d",e);
    }
    printf("\n");
    printf("顺序表L调整后（左边元素小于等于0，右边元素大于等于0）:\n");
    SplitSepList(&L);   //调整顺序表
    for(i=1;i<=L.length;i++)  //输出调整后顺序表L中所有元素
    {
        flag==GetElem(L,i,&e);
        if(flag==1)
            printf("%4d",e);
    }
    printf("\n");
}

void SplitSepList(SeqList *L)
{
    int i,j;  //定义两个指示器 i 和 j
    DataType e;
    i=0;j=(*L).length-1;  //指示器 i 和 j 分别指示顺序表的左端和右端元素
    while(i<j)
    {
        while(L->list[i]<=0)  //i 遇到小于等于0的元素
            i++;  //略过
        while(L->list[j]>0)  //j 遇到大于0的元素
            j--;   //略过
        if(i<j)   //交换 i 和 j 指向的元素
        {
            e=L->list[i];
            L->list[i]=L->list[j];
            L->list[j]=e;
        }
    }
}