首页 > 代码库 > 顺序表的有关增强练习

顺序表的有关增强练习

/*
	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--; } }


顺序表的有关增强练习