顺序表的相关操作

public class DS3_0723{ //属性 private int[] a; private int size; //构造方法 public DS3_0723(){ a=new int[2]; size=0; } //増 //尾插 public void pushBack(int element) { ensureCapacity(); a[size]=element; size++; } //头插 public void pushFront(int element) { ensureCapacity(); for(int i=size-1;i>=0;i--){ a[i+1]=a[i]; } a[0]=element; size++; } //中间插入 时间复杂度为O(n) public void insert(int index, int element) { if(index<0||index>size){ System.err.println("输入下标有误，请重新输入！"); return; } ensureCapacity(); for(int i=size-1;i>=index;i--){ a[i+1]=a[i]; } a[index]=element; size++; } //删 //尾删 public void popBack() { if(size<=0){ System.err.println("顺序表为空"); return; } size--; a[size]=0; } //头删 public void popFront() { if(size<=0){ System.err.println("顺序表为空"); return; } for(int i=0;i<=size-2;i++){ a[i]=a[i+1]; } size--; //a[size]=0; //array[--size] = 0; } //中间删除 public void earse(int index) { if(size<=0){ System.err.println("顺序表为空"); return; } if(index<0||index>size){ System.err.println("输入下标有误，请重新输入！"); return; } for(int i=index;i<=size-2;i++){ a[i]=a[i+1]; } size--; a[size]=0; } // 删除掉某一个元素，如果出现多次，删除第一次出现的 public void remove(int element) { int index=searchIndex(element); if(index!=-1){ earse(index); } } //删掉所有与element相等的数 public void removeAll(int element) { //1.时间复杂度:O(n^2) 空间复杂度：O(1) // int index; // while((index=searchIndex(element))!=-1){ // earse(index); // } //2.时间复杂度: O(n) 空间复杂度: O(n) // int[] newArray=new int[a.length]; // int j=0; // for(int i=0;i<size;i++){ // if(a[i]!=element){ // newArray[j++]=a[i]; // } // } // a=newArray; // size=j; //3.时间复杂度：O(n) 空间复杂度：O(1) int j=0; for(int i=0;i<size;i++){ if(a[i]!=element){ a[j++]=a[i]; } } size=j; } // 查 //返回某数的下标 public int searchIndex(int element){ for(int i=0;i<size;i++){ if(a[i]==element){ return i; } } return -1; } //返回某下标对应的数 public int searchElement(int index){ if(index<0||index>size){ System.err.println("输入下标有误，请重新输入！"); return -1; } return a[index]; } // 改 public void change(int index,int element){ if(index<0||index>size){ System.err.println("输入下标有误，请重新输入！"); return; } a[index]=element; } //打印 public void print() { System.out.print("当前顺序表为:"); for(int i=0;i<size;i++){ System.out.print(a[i]+" "); } System.out.println(); System.out.println("当前容量为："+a.length); System.out.println(); } //保证内存够用，否则扩容 private void ensureCapacity() { if(size<a.length){ return; } int newCapacity=a.length*2; int[] newArray=new int[newCapacity]; for(int i=0;i<size;i++){ newArray[i]=a[i]; } a=newArray; } public static void main(String[] args){ DS3_0723 data=new DS3_0723(); data.print(); data.pushBack(1); data.pushBack(6); data.pushBack(7); data.print();//1 6 7 data.pushFront(30); data.pushFront(3); data.pushFront(10); data.print();//10 3 30 1 6 7 data.insert(2,200);//10 3 200 30 1 6 7 data.insert(0,11);//11 10 3 200 30 1 6 7 data.insert(3,11);//11 10 3 11 200 30 1 6 7 data.insert(7,3); data.print();//11 10 3 11 200 30 1 3 6 7 data.insert(11,1);//报错 data.popBack(); data.print();//11 10 3 11 200 30 1 3 6 data.popFront(); data.print();//10 3 11 200 30 1 3 6 data.earse(2); data.print();//10 3 200 30 1 3 6 data.remove(200); data.print();//10 3 30 1 3 6 data.removeAll(3); data.print();//10 30 1 6 data.searchIndex(30);//下标为1 data.searchElement(3);//6 data.change(1,10); data.print();//10 10 1 6 data.change(13,3); data.print();//报错 } }