/*
	Name: SeqList_Rel
	Copyright: 
	Author: huowolf 
	Date: 06/07/15 21:49
	Description: 顺序表的有关增强练习 
*/

#include <iostream>
using namespace std;
#define MAXSIZE 100

typedef int ElemType;
struct SeqList
{
	ElemType elems[MAXSIZE];
    int last;	
};

void InitList(SeqList &l);
int InsertList(SeqList &l,int i,ElemType e);
void CreateList(SeqList &l);
void Output(SeqList &l);
void OrderInsert(SeqList &l,ElemType x);
void MultyDelete(SeqList &l,int i,int k);
void Delsame(SeqList &L);
void Invert(SeqList &L);

SeqList L;
int main()
{
	
	InitList(L);
	CreateList(L);
	Output(L);
	/*
	int x;
	cout<<"请输入一个你要有序插入的元素:";
	cin>>x;
	OrderInsert(L,x);
	Output(L);
	
	int a,b;
	cout<<"请输入你要開始删除的位置i,以及要删除的个数k:";
	cin>>a>>b;
	MultyDelete(L,a,b);
	Output(L);
    

    int item;
    cout<<"请输入你要删除的元素";
    cin>>item;
    DeleteItem(L,item);
    Output(L);
    
    Delsame(L);	
    Output(L);
    */
    Invert(L);
    Output(L);
	return 0;
}

void InitList(SeqList &l)
{
    l.last = -1;    
}

 
int InsertList(SeqList &l,int i,ElemType e)		//1<=i<=L->last+2 
 {
    if(i<1 || i>l.last+2)
    {
        cout<<"插入位置i非法。"<<endl;
        return -1;
    }
    if(i>MAXSIZE-1)
    {
        cout<<"表已满，无法插入。"<<endl;
        return -1;
    }
	for(int j=l.last+1;j>=i;j--)
		l.elems[j]=l.elems[j-1]; 
		   
    l.elems[i-1] = e;	//插入 (第i个元素的下标是i-1) 
    l.last++;
    return 0;
}

void CreateList(SeqList &l)
{
    cout<<"请依次输入数据，并以-1作为结束标记:"<<endl;
    int n;
    cin>>n; 
    while(n!=-1)
    {
        InsertList(l,l.last+2,n);
        cin>>n;
    }   
}

void Output(SeqList &l)
{
	cout<<"遍历该顺序表例如以下："<<endl; 
    for(int i=0;i<=l.last;i++)
    {
        cout<<l.elems[i]<<" ";
    }
    cout<<endl; 
}

/*
该函数实现下面功能：
已知顺序表L单调递增。将X插入线性表的适当位置
以保持线性表的有序性。
 
*/
void OrderInsert(SeqList &l,ElemType x) 
{
	int i=l.last;
	while(i>=0&&x<l.elems[i])
	{
		l.elems[i+1]=l.elems[i];
	 	i--;
	}
	l.elems[i+1]=x;
	l.last++;
}

/*
从顺序表中删除自第i个元素開始的k个元素 
*/
void MultyDelete(SeqList &l,int i,int k)
{
	if(l.last+1-i+1<k)
		cout<<"參数有误。你要删除的区间元素不足"<<k<<"个"<<endl;
	int m,j;
	for(m=i-1,j=k+i-1;j<=l.last;j++) 
		l.elems[m++]=l.elems[j];
	l.last=m-1; 
} 

/*
编写一时间复杂度为O(n),空间复杂度为O(1)的算法。
删除线性表中所以值为item的元素 
*/
void DeleteItem(SeqList &l,ElemType item)
{
	int i=0,k=0;
	while(i<=l.last)
	{
		if(l.elems[i]!=item) l.elems[k++]=l.elems[i];
		i++;
	}
	l.last=k-1;
}  

/*
编写一时间复杂度为O(n^2),空间复杂度为O(1)的算法。
删除所以值相等的多余元素 
*/
void Delsame(SeqList &L)
{

	int i=0,k;
	for(int j=1;j<=L.last;j++)
	{
		//假设当前元素L.elems[j]和L.elems[0...i]中的某一元素相等,就break
		for(k=0;k<=i;k++)if(L.elems[k]==L.elems[j])break;
		//假设上面运行了break,也就是有同样元素..那么则有k<=i
		//假设没有运行break..则一定有k>i
		if(k>i)L.elems[++i]=L.elems[j];//把当前元素L.elems[j]追加到以完毕的有序区中 
	}
	L.last = i;
}

//实现顺序表的就地逆置算法 
void Invert(SeqList &L)
{
	int i,j,t;
	i=0;j=L.last;
	while(i<j)
	{
		t=L.elems[i]; L.elems[i]=L.elems[j]; L.elems[j]=t;
		i++;j--;
	}
}