数据结构--顺序表(详解)

                                         欢迎大家来到我的博客~欢迎大家对我的博客提出指导，有错误的地方会改进的哦·~

点击这里了解更多内容

一、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。
顺序表的实现：

1.定义一个接口，里面放着需要实现的方法：

public interface Ilist {// 新增元素,默认在数组最后新增public void add(int data);boolean isFull();// 在 pos 位置新增元素public void add(int pos, int data);// 判定是否包含某个元素public boolean contains(int toFind);// 查找某个元素对应的位置public int indexOf(int toFind);// 获取 pos 位置的元素public int get(int pos);// 给 pos 位置的元素设为 valuepublic void set(int pos, int value);//删除第一次出现的关键字keypublic void remove(int toRemove);// 获取顺序表长度public int size() ;// 清空顺序表public void clear();// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的public void display() ;
}

2.定义一个mySeqlist类去继承接口，然后对，每个方法进行重写。

public class mySeqlist implements Ilist{public final int DEFALUT_CAPTICY=10;public int[] array;//定义起始数组大小为10public mySeqlist() {this.array =new int[DEFALUT_CAPTICY];}//顺序表的元素个数public int usesize;// 新增元素,默认在数组最后新增@Overridepublic void add(int data) {}@Overridepublic boolean isFull() {return false;}@Overridepublic void add(int pos, int data) {}@Overridepublic boolean contains(int toFind) {return false;}@Overridepublic int indexOf(int toFind) {return 0;}@Overridepublic int get(int pos) {return 0;}@Overridepublic void set(int pos, int value) {}@Overridepublic void remove(int toRemove) {}@Overridepublic int size() {return 0;}@Overridepublic void clear() {}@Overridepublic void display() {}
}

---

接下来一个一个来实现这些方法，然后完成一个顺序表的实现。

打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的.

@Overridepublic void display() {for (int i = 0; i < usesize; i++) {System.out.print(array[i] + " ");}}

---

判断数组是否存储满了

@Overridepublic boolean isFull() {return this.usesize==array.length;}

---

数组存储满了，然后想插入数据就得进行扩容。

private int[] grow() {return this.array= Arrays.copyOf(this.array,2*this.array.length);}

---

新增元素,默认在数组最后新增

    @Overridepublic void add(int data) {//判断数组是否存储满了if(isFull()){//如果忙了就扩容grow();}array[usesize]=data;usesize++;}private int[] grow() {return this.array= Arrays.copyOf(this.array,2*this.array.length);}@Overridepublic boolean isFull() {return this.usesize==array.length;}

---

再生成一个test类,每写完一个方法，然后测试是否成功

public class Test {public static void main(String[] args) {mySeqlist mylist=new mySeqlist();//新增mylist.add(1);mylist.add(6);mylist.add(10);mylist.display();}
}

运行结果：

---

在 pos 位置新增元素
可以自定义一个异常，来判断输入的pos位置是否合法

public class posillegal extends RuntimeException{ public posillegal(){super();}public posillegal(String S){super(S);}
}

---

定义一个方法来判断pos是否合法

   private void Check(int pos) {if(pos<0||pos>usesize){throw new posillegal("pos位置不合法!!!");}}

在 pos 位置新增元素

   public void add(int pos, int data) {try{Check(pos);if(isFull()){//如果忙了就扩容grow();}for (int i = usesize; i >pos ; i--) {array[i]=array[i-1];}array[pos]=data;usesize++;}catch (posillegal e){e.printStackTrace();}}

测试：

---

点击这里了解什么是异常

判定是否包含某个元素

@Overridepublic boolean contains(int toFind) {//先判断数组是否为空if(isempty()){return false;}if(Find(toFind)){return true;}return false;}private boolean isempty() {return usesize==0;}private boolean Find(int tofind) {for (int i = 0; i < usesize; i++) {if(array[i]==tofind){return true;}}return false;}

---

获取值的下标

   @Overridepublic int indexOf(int toFind) {for (int i = 0; i < usesize; i++) {if(array[i]==toFind){return i;}}return -1;}

---

获取pos位置的值

@Overridepublic int get(int pos) {try{Check(pos);return array[pos];}catch (posillegal e){e.printStackTrace();}return  -1;}

---

把pos位置的元素设置变成value

  @Overridepublic void set(int pos, int value) {array[pos]=value;}

---

去除某个值

  @Overridepublic void remove(int toRemove) {if(isempty()){return;}int toremove=indexOf(toRemove);for (int i = toremove; i <usesize ; i++) {array[i]=array[i+1];}usesize--;}

---

求顺序表的长度

@Overridepublic int size() {return usesize;}

---

清空顺序表

   @Overridepublic void clear() {usesize=0;}

---

好了，到这里整个顺序表就差不多完成了。下面是完整代码：

Ilist 接口

public interface Ilist {// 新增元素,默认在数组最后新增public void add(int data);boolean isFull();// 在 pos 位置新增元素public void add(int pos, int data);// 判定是否包含某个元素public boolean contains(int toFind);// 查找某个元素对应的位置public int indexOf(int toFind);// 获取 pos 位置的元素public int get(int pos);// 给 pos 位置的元素设为 valuepublic void set(int pos, int value);//删除第一次出现的关键字keypublic void remove(int toRemove);// 获取顺序表长度public int size() ;// 清空顺序表public void clear();// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的public void display() ;
}

mySeqlist类

import java.util.Arrays;public class mySeqlist implements Ilist{public final int DEFALUT_CAPTICY=10;public int[] array;//定义起始数组大小为10public mySeqlist() {this.array =new int[DEFALUT_CAPTICY];}//顺序表的元素个数public int usesize;// 新增元素,默认在数组最后新增@Overridepublic void add(int data) {//判断数组是否存储满了if(isFull()){//如果忙了就扩容grow();}array[usesize]=data;usesize++;}private int[] grow() {return this.array= Arrays.copyOf(this.array,2*this.array.length);}@Overridepublic boolean isFull() {return this.usesize==array.length;}// 在 pos 位置新增元素@Overridepublic void add(int pos, int data) {try{Check(pos);if(isFull()){//如果忙了就扩容grow();}for (int i = usesize; i >pos ; i--) {array[i]=array[i-1];}array[pos]=data;usesize++;}catch (posillegal e){e.printStackTrace();}}private void Check(int pos) {if(pos<0||pos>usesize){throw new posillegal("pos位置不合法!!!");}}// 判定是否包含某个元素@Overridepublic boolean contains(int toFind) {//先判断数组是否为空if(isempty()){return false;}if(Find(toFind)){return true;}return false;}private boolean isempty() {return usesize==0;}private boolean Find(int tofind) {for (int i = 0; i < usesize; i++) {if(array[i]==tofind){return true;}}return false;}//获取值的下标@Overridepublic int indexOf(int toFind) {for (int i = 0; i < usesize; i++) {if(array[i]==toFind){return i;}}return -1;}//获取pos位置的值@Overridepublic int get(int pos) {try{Check(pos);return array[pos];}catch (posillegal e){e.printStackTrace();}return  -1;}//把pos位置的元素设置变成value@Overridepublic void set(int pos, int value) {array[pos]=value;}//去除某个值@Overridepublic void remove(int toRemove) {if(isempty()){return;}int toremove=indexOf(toRemove);for (int i = toremove; i <usesize ; i++) {array[i]=array[i+1];}usesize--;}//求顺序表的长度@Overridepublic int size() {return usesize;}//清空顺序表@Overridepublic void clear() {usesize=0;}//打印顺序表@Overridepublic void display() {for (int i = 0; i < usesize; i++) {System.out.print(array[i] + " ");}}
}

---

自定义 pos异常

public class posillegal extends RuntimeException{public posillegal(){super();}public posillegal(String S){super(S);}
}

---

测试类(测试仅供参考)

public class Test {public static void main(String[] args) {mySeqlist mylist=new mySeqlist();//新增mylist.add(1);mylist.add(6);mylist.add(10);mylist.add(2,8);mylist.display();System.out.println();//System.out.println(mylist.get(1));mylist.set(2,9);mylist.remove(6);mylist.display();System.out.println();System.out.println(mylist.size());mylist.clear();mylist.display();}
}

欧耶！！！我学会啦！！！