IT评测·应用市场-qidao123.com

标题: 数据布局--顺序表(详解) [打印本页]

---

作者: 悠扬随风    时间: 2025-1-4 01:31
标题: 数据布局--顺序表(详解)

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

复制代码

点击这里了解更多内容

  
一、线性表

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

二、顺序表

顺序表是用一段物理地址一连的存储单元依次存储数据元素的线性布局，一般情况下接纳数组存储，在数组上完成数据的增删查改。
顺序表的实现：
   1.界说一个接口，内里放着需要实现的方法：

1. public interface Ilist {
2.     // 新增元素,默认在数组最后新增
3.     public void add(int data);
4.     boolean isFull();
5.     // 在 pos 位置新增元素
6.     public void add(int pos, int data);
7.     // 判定是否包含某个元素
9.     public boolean contains(int toFind);
10.     // 查找某个元素对应的位置
11.     public int indexOf(int toFind);
12.     // 获取 pos 位置的元素
13.     public int get(int pos);
14.     // 给 pos 位置的元素设为 value
15.     public void set(int pos, int value);
16.     //删除第一次出现的关键字key
17.     public void remove(int toRemove);
18.     // 获取顺序表长度
19.     public int size() ;
20.     // 清空顺序表
21.     public void clear();
22.     // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
23.     public void display() ;
24. }

复制代码

  2.界说一个mySeqlist类去继承接口，然后对，每个方法举行重写。

1. public class mySeqlist implements Ilist{
2.     public final int DEFALUT_CAPTICY=10;
3.     public int[] array;
4.     //定义起始数组大小为10
5.     public mySeqlist() {
6.         this.array =new int[DEFALUT_CAPTICY];
7.     }
9.     //顺序表的元素个数
10.     public int usesize;
11.     // 新增元素,默认在数组最后新增
12.     @Override
13.     public void add(int data) {
14.         
15.     }
17.     @Override
18.     public boolean isFull() {
19.         return false;
20.     }
22.     @Override
23.     public void add(int pos, int data) {
25.     }
27.     @Override
28.     public boolean contains(int toFind) {
29.         return false;
30.     }
32.     @Override
33.     public int indexOf(int toFind) {
34.         return 0;
35.     }
37.     @Override
38.     public int get(int pos) {
39.         return 0;
40.     }
42.     @Override
43.     public void set(int pos, int value) {
45.     }
47.     @Override
48.     public void remove(int toRemove) {
50.     }
52.     @Override
53.     public int size() {
54.         return 0;
55.     }
57.     @Override
58.     public void clear() {
60.     }
62.     @Override
63.     public void display() {
65.     }
66. }

复制代码

---

    接下来一个一个来实现这些方法，然后完成一个顺序表的实现。
    打印顺序表，留意：该方法并不是顺序表中的方法，为了方便看测试效果给出的.

2. @Override
3.     public void display() {
4.         for (int i = 0; i < usesize; i++) {
5.             System.out.print(array[i] + " ");
6.         }
7.     }
8.    

复制代码

---

   判断数组是否存储满了

1. @Override
2.     public boolean isFull() {
3.         return this.usesize==array.length;
4.     }

复制代码

---

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

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

复制代码

---

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

1.     @Override    public void add(int data) {    //判断数组是否存储满了        if(isFull()){            //假如忙了就扩容            grow();        }        array[usesize]=data;        usesize++;    }   
2. private int[] grow() {
3.         return this.array= Arrays.copyOf(this.array,2*this.array.length);
4.     }
6.     @Override
7.     public boolean isFull() {
8.         return this.usesize==array.length;
9.     }

复制代码

---

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

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

复制代码

运行效果：

---

   在 pos 位置新增元素
可以自界说一个异常，来判断输入的pos位置是否正当

1. public class posillegal extends RuntimeException{
2.     public posillegal(){
3.         super();
4.     }
5.     public posillegal(String S){
6.         super(S);
7.     }
8. }

复制代码

---

   界说一个方法来判断pos是否正当

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

复制代码

  在 pos 位置新增元素

1.    public void add(int pos, int data) {
2.         try{
3.             Check(pos);
4.             if(isFull()){
5.                 //如果忙了就扩容
6.                 grow();
7.             }
8.             for (int i = usesize; i >pos ; i--) {
9.                 array[i]=array[i-1];
10.             }
11.             array[pos]=data;
12.             usesize++;
13.         }catch (posillegal e){
14.             e.printStackTrace();
15.         }
16.     }

复制代码

测试：

---

点击这里了解什么是异常
  

1. 判定是否包含某个元素

复制代码

1. @Override
2.     public boolean contains(int toFind) {
3.         //先判断数组是否为空
4.         if(isempty()){
5.             return false;
6.         }
7.        if(Find(toFind)){
8.            return true;
9.        }
10.        return false;
11.     }
13.     private boolean isempty() {
14.         return usesize==0;
15.     }
17.     private boolean Find(int tofind) {
18.         for (int i = 0; i < usesize; i++) {
19.             if(array[i]==tofind){
20.                 return true;
21.             }
22.         }
23.         return false;
24.     }

复制代码

---

   获取值的下标

1.    @Override
2.     public int indexOf(int toFind) {
3.         for (int i = 0; i < usesize; i++) {
4.             if(array[i]==toFind){
5.                 return i;
6.             }
7.         }
8.         return -1;
9.     }

复制代码

---

   获取pos位置的值

1. @Override
2.     public int get(int pos) {
3.        try{
4.            Check(pos);
5.            return array[pos];
6.        }catch (posillegal e){
7.            e.printStackTrace();
8.        }
9.        return  -1;
10.     }

复制代码

---

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

1.   @Override
2.     public void set(int pos, int value) {
3.           array[pos]=value;
4.     }

复制代码

---

   去除某个值

1.   @Override
2.     public void remove(int toRemove) {
3.         if(isempty()){
4.             return;
5.         }
6.      int toremove=indexOf(toRemove);
7.         for (int i = toremove; i <usesize ; i++) {
8.             array[i]=array[i+1];
9.         }
10.         usesize--;
11.     }

复制代码

---

   求顺序表的长度

1. @Override
2.     public int size() {
3.         return usesize;
4.     }

复制代码

---

   清空顺序表

1.    @Override
2.     public void clear() {
3.           usesize=0;
4.     }

复制代码

---

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

1. public interface Ilist {
2.     // 新增元素,默认在数组最后新增
3.     public void add(int data);
4.     boolean isFull();
5.     // 在 pos 位置新增元素
6.     public void add(int pos, int data);
7.     // 判定是否包含某个元素
9.     public boolean contains(int toFind);
10.     // 查找某个元素对应的位置
11.     public int indexOf(int toFind);
12.     // 获取 pos 位置的元素
13.     public int get(int pos);
14.     // 给 pos 位置的元素设为 value
15.     public void set(int pos, int value);
16.     //删除第一次出现的关键字key
17.     public void remove(int toRemove);
18.     // 获取顺序表长度
19.     public int size() ;
20.     // 清空顺序表
21.     public void clear();
22.     // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
23.     public void display() ;
24. }

复制代码

  mySeqlist类

1. import java.util.Arrays;public class mySeqlist implements Ilist{    public final int DEFALUT_CAPTICY=10;    public int[] array;    //界说起始数组巨细为10    public mySeqlist() {        this.array =new int[DEFALUT_CAPTICY];    }    //顺序表的元素个数    public int usesize;    // 新增元素,默认在数组最后新增    @Override    public void add(int data) {    //判断数组是否存储满了        if(isFull()){            //假如忙了就扩容            grow();        }        array[usesize]=data;        usesize++;    }   
2. private int[] grow() {
3.         return this.array= Arrays.copyOf(this.array,2*this.array.length);
4.     }
6.     @Override
7.     public boolean isFull() {
8.         return this.usesize==array.length;
9.     }
10.     // 在 pos 位置新增元素    @Override    public void add(int pos, int data) {
11.         try{
12.             Check(pos);
13.             if(isFull()){
14.                 //如果忙了就扩容
15.                 grow();
16.             }
17.             for (int i = usesize; i >pos ; i--) {
18.                 array[i]=array[i-1];
19.             }
20.             array[pos]=data;
21.             usesize++;
22.         }catch (posillegal e){
23.             e.printStackTrace();
24.         }
25.     }
26.     private void Check(int pos) {
27.         if(pos<0||pos>usesize){
28.             throw new posillegal("pos位置不合法!!!");
29.         }
30.     }
31.     // 判定是否包含某个元素
32.     @Override
33.     public boolean contains(int toFind) {
34.         //先判断数组是否为空
35.         if(isempty()){
36.             return false;
37.         }
38.        if(Find(toFind)){
39.            return true;
40.        }
41.        return false;
42.     }
44.     private boolean isempty() {
45.         return usesize==0;
46.     }
48.     private boolean Find(int tofind) {
49.         for (int i = 0; i < usesize; i++) {
50.             if(array[i]==tofind){
51.                 return true;
52.             }
53.         }
54.         return false;
55.     }
56.    //获取值的下标    @Override
57.     public int indexOf(int toFind) {
58.         for (int i = 0; i < usesize; i++) {
59.             if(array[i]==toFind){
60.                 return i;
61.             }
62.         }
63.         return -1;
64.     }
65.     //获取pos位置的值    @Override
66.     public int get(int pos) {
67.        try{
68.            Check(pos);
69.            return array[pos];
70.        }catch (posillegal e){
71.            e.printStackTrace();
72.        }
73.        return  -1;
74.     }
75.    //把pos位置的元素设置酿成value    @Override
76.     public void set(int pos, int value) {
77.           array[pos]=value;
78.     }
79.    //去除某个值    @Override
80.     public void remove(int toRemove) {
81.         if(isempty()){
82.             return;
83.         }
84.      int toremove=indexOf(toRemove);
85.         for (int i = toremove; i <usesize ; i++) {
86.             array[i]=array[i+1];
87.         }
88.         usesize--;
89.     }
90.     //求顺序表的长度    @Override
91.     public int size() {
92.         return usesize;
93.     }
94.      //清空顺序表    @Override
95.     public void clear() {
96.           usesize=0;
97.     }
98.    //打印顺序表    @Override    public void display() {        for (int i = 0; i < usesize; i++) {            System.out.print(array[i] + " ");        }    }}

复制代码

---

   自界说 pos异常

1. public class posillegal extends RuntimeException{
2.     public posillegal(){
3.         super();
4.     }
5.     public posillegal(String S){
6.         super(S);
7.     }
8. }

复制代码

---

   测试类(测试仅供参考)

1. public class Test {
2.     public static void main(String[] args) {
3.         mySeqlist mylist=new mySeqlist();
4.         //新增
5.         mylist.add(1);
6.         mylist.add(6);
7.         mylist.add(10);
8.         mylist.add(2,8);
9.         mylist.display();
10.         System.out.println();
11.         //System.out.println(mylist.get(1));
12.         mylist.set(2,9);
13.         mylist.remove(6);
14.         mylist.display();
15.         System.out.println();
16.         System.out.println(mylist.size());
17.         mylist.clear();
18.         mylist.display();
19.     }
20. }

复制代码

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)

Powered by Discuz! X3.4