【数据结构】(顺序表的Java与C++实现及经典应用)

从入坑到入土的坑就是顺序表,珍惜最基础的数据结构,当然也要掌握好这个数据结构大厦的基石,顺序表的实现形式给很多复杂的数据结构形式提供了简单实现的方案,在有些时候,用顺序表的实现并非是差的选择(♥◠‿◠)ﾉ

顺序表的Java实现

Java代码是对顺序表的简单数组实现，对于顺序表的任何操作都可以利用数组来实现，但是往往使用数组时需要对数组的长度进行估计，这也很不符合实际也是很大的缺陷，但是在Java等现代语言中均不需要再对数组的长度进行估算，若数组长度达到了最大值可以用相应的方法进行扩充建立一个新的顺序表，当然对于顺序表的实现即使是数组实现但也有插入和删除需要大量移动数组带来的时间复杂度的问题。

//Java代码实现
package SquenceList;

public class Sqlist {

	private static int MAXSIZE;
	private static int[] sqlist;
	private static int length;
	//用最大数组长度来初始化顺序表
	public Sqlist(int MAXSIZE){
		this.sqlist = new int[MAXSIZE];
		this.MAXSIZE=MAXSIZE;
		this.length=0;
	}
	//用数组来初始化顺序表
	public Sqlist(int[] arr) {
		for(int i=0;i<arr.length;i++) {
			sqlist[i] = arr[i];
		}
		this.length = arr.length;
	}
	//对由数组实现的顺序表进行扩充
	public void expandList(){
	    int[] newarr = new int[arr.length*2]
	    for(int i=0;i<arr.length;i++){
	        newarr[i]=arr[i]
	    }
	    arr = newarr;
	}
	//向顺序表指定位置插入元素
	public int listInsert(int i, int e) 
	{
		if(i<1) {
			System.out.println("非法插入位置");
			return -1;
		}else if(this.length == this.MAXSIZE) {
			System.out.println("顺序表已满");
			return -2;
		}
		for(int k=length-1;k>=i-1;k--) {
			sqlist[k+1]=sqlist[k];  //数组中插入位置及其后的元素均向后移动一位
		}
		sqlist[i-1]=e;  //将制定元素插入此位置
		this.length++;  //插入后的顺序表长度+1
		return 0;
	}
	//清空顺序表
	public void listClear() {
		this.length = 0;  //仅用来判断是否为空，直接将长度设置为0
	}
	//判断顺序表是否为空
	public boolean isEmpty() {
		return this.length==0;
	}
	//获取指定位置的顺序表元素
	public static int getElem(int i) {
		if(i<1||i>length)
		{
			System.out.println("获取位置不合法");
			return -1;
		}
		return sqlist[i-1];
		
	}
	//获取制定元素的位置信息
	public int getIndex(int e, int i) {
		for(int j=0;j<=length-1;j++)
		{
			if(sqlist[j]==e) {
				i=j++;
				return i;
			}
		}
		System.out.println("顺序表中无对应元素");
		return 0;
	}
	//打印顺序表
	public static void printList() {
		for(int i=0;i<=length-1;i++)
		{
			int t=i+1;
			System.out.println("第"+t+"个元素为"+sqlist[i]);
		}
	}
	//删除顺序表指定位置的元素
	public static int listDelete(int i) {
		if(i<1||i>length)
		{
			System.out.println("删除位置不合法");
			return -1;
		}
		for(int j=i;j<=length-1;j++)
		{
			sqlist[j-1]=sqlist[j];
		}
		length--;
		return 0;
	}
	public static void main(String[] args) {
		Sqlist sqlist = new Sqlist(5);
		for(int i=1;i<=4;i++)
		{
			sqlist.listInsert(i, i);
		}
		printList();
		System.out.println("第3个元素为"+getElem(3));
		System.out.println("删除第二个元素后的顺序表的内容为：")
		listDelete(2);
		printList();
	}
}

顺序表的C++实现

C++代码实现顺序表的实现由于有指针的牵制而使得代码的实现比较复杂，需要多加理解和记忆。

//建立顺序表的存储结构
typedef struct
{
    int *elem;
    int length;
}SqList;
//构造一个空的顺序表
int InitList(SqList &L)
{
    L.elem=new ElemType[maxsize];
    if(!L.elem) exit(overflow);
    L.length=0;
    return ok;
}
//顺序表的插入
int ListInsert(SqList &L,int i,int e)
{
    if((i<1)||(i>L.length+1)) return error; //插入位置是否合法的判断
    if(L.length==maxsize)  return error;
    for(int j=L.length-1;j>=i-1;j--)
        L.elem[j+1]=L.elem[j];  //插入后元素位置的移动变化
    L.elem[i-1]=e;
    ++L.length;
    return ok;
}
//顺序表元素的获取
int GetElem(SqList L,int i,int &e)
{
    if(i<1||i>L.length) return error;
    e=L.elem[i-1];
    return e;
}
//判断值是否相等
int EqualList(int a,int b)
{
    if(a==b)
        return ok;
    else
        return error;
}
//判断顺序表中是否存在值为e的元素
int LocateElem(SqList L,ElemType e,int EqualList(int a, int b))
{
    int i=1;
    int *p=L.elem;
    while(i<=L.length&&!EqualList(*p++,e))
        ++i;
    if(i<=L.length)
        return 1;
    else
        return 0;


}
//顺序表的打印
void PrintList(SqList L)
{
    for(int i=0; i<L.length; i++)
    {
        cout<<L.elem[i]<<" ";
    }
    cout<<endl;

}
//顺序表表示集合的并集
void MergeList(SqList LA,SqList LB,SqList & LC)
{
   int m,n,e;
   m=LA.length;n=LB.length;
   for(int i=1;i<=n;i++)
   {
       GetElem(LB,i,e);  //获取B中第i个元素并返回给e
       if(!LocateElem(LA,e,EqualList) )
           {
               ListInsert(LA,++m,e);    //将e插在LC的最后
           }
   }
   for(int i=1;i<=m;i++)
    {
        GetElem(LA,i,e);   //获取A中第i个元素并赋给e
        ListInsert(LC,i,e);
    }

}

int Mixture(SqList LA,SqList LB,SqList &LC)
{//a与b的交集
    int m,n,e;
    m=LA.length;
    n=LB.length;
    int j=0;
    SqList p=m<=n?LA:LB;
    SqList q=m>n?LA:LB;
    for(int i=1;i<=p.length;i++)
    {
        GetElem(p,i,e);
        if(LocateElem(q,e,EqualList))
        {
            ListInsert(LC,++j,e);
        }
    }
    if(LC.length)
        return ok;
    else
        return error;
}

int Different(SqList LA,SqList LB,SqList &LC)
{//求A-B的集合
    int m=LA.length;
    int e;
    int j=0;
    for(int i=1;i<=m;i++)
    {
        GetElem(LA,i,e);
        if(!LocateElem(LB,e,EqualList))
            ListInsert(LC,++j,e);
    }
    if(LC.length)
        return ok;
    else
        return error;
}

int main()
{
    SqList LA,LB;
    InitList(LA);
    InitList(LB);

    cout<<"线性表a的长度："<<endl;
    int la;
    cin>>la;
    cout<<"请输入a中的元素："<<endl;
    int e;
    for(int i=1;i<=la;i++)
    {
        cin>>e;
        ListInsert(LA,i,e);
    }
    cout<<"A中的元素:"<<endl;
    PrintList(LA);
    cout<<"线性表b的长度："<<endl;
    int lb;
    cin>>lb;
    cout<<"请输入b中的元素："<<endl;
    for(int i=1;i<=lb;i++)
    {
        cin>>e;
        ListInsert(LB,i,e);
    }
    cout<<"B中的元素"<<endl;
    PrintList(LB);

    cout<<"A并B:";
    SqList LC1;
    InitList(LC1);
    MergeList(LA,LB,LC1);
    PrintList(LC1);

    cout<<"A交B：";
    SqList LC2;
    InitList(LC2);
    Mixture(LA,LB,LC2);
    PrintList(LC2);


    cout<<"A差B：";
    SqList LC3;
    InitList(LC3);
    Different(LA,LB,LC3);
    PrintList(LC3);

    return 0;
}