数据结构Java实现----线性表与顺序表

我就是我 2021-11-08 21:56 426阅读 0赞

**一、****线性结构****：**

如果一个数据元素序列满足：

（1）除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素；

（2）第一个数据元素没有前驱数据元素；

（3）最后一个数据元素没有后继数据元素。

则称这样的数据结构为线性结构。

**二、****线性表****抽象数据类型：**

**1、线性表抽象数据类型的概念：**

线性表抽象数据类型主要包括两个方面：既数据集合和该数据集合上的操作集合。

数据集合：

可以表示为a0,a1,a2,...an-1,每个数据元素的数据类型可以是任意的类型。

操作集合包括如下：

> 1.求元素个数
> 
> 2.插入
> 
> 3.删除
> 
> 4.查找
> 
> 5.判断是否为空

**2、设计线性表抽象数据类型的Java接口：**

代码如下：

//线性表接口
    public interface List {
        //获得线性表长度
        public int size();
        //判断线性表是否为空
        public boolean isEmpty();
        //插入元素
        public void insert(int index,Object obj) throws Exception;
        //删除元素
        public void delete(int index) throws Exception;
        //获取指定位置的元素
        public Object get(int index) throws Exception;
    }

然后我们让子类去实现这个接口就行了。

**三、顺序表：（在物理存储结构上连续，大小固定）**

**1、顺序表的概念：**

计算机有两种基本的存储结构（物理存储结构）：顺序结构、离散结构。使用顺序结构实现的**线性表**称为**顺序表**。如下图所示：

[![d3384f05-39d1-46d9-a580-bf4b531d740c][]][d3384f05-39d1-46d9-a580-bf4b531d740c 1]

Java内存中，栈内存和堆内存占了很大一部分空间：栈内存的存储是顺序结构，堆内存的存储是离散结构。

**2、设计顺序表类：**

我们在上面第二段的List接口基础之上，设计一个顺序表：

（1）List.java:（线性表，和上面的第二段中代码一样）

//线性表接口
    public interface List {
        //获得线性表长度
        public int size();
        //判断线性表是否为空
        public boolean isEmpty();
        //插入元素
        public void insert(int index, Object obj) throws Exception;
        //删除元素
        public void delete(int index) throws Exception;
        //获取指定位置的元素
        public Object get(int index) throws Exception;
    }

**（2）SequenceList.java:（核心代码）**

1 public class SequenceList implements List {
     2 
     3     //默认的顺序表的最大长度
     4     final int defaultSize = 10;
     5     //最大长度
     6     int maxSize;
     7     //当前长度
     8     int size;
     9     //对象数组
    10     Object[] listArray;
    11 
    12 
    13     public SequenceList() {
    14         init(defaultSize);
    15     }
    16 
    17     public SequenceList(int size) {
    18         init(size);
    19     }
    20 
    21     //顺序表的初始化方法
    22     private void init(int size) {
    23         maxSize = size;
    24         this.size = 0;
    25         listArray = new Object[size];
    26     }
    27 
    28     @Override
    29     public void delete(int index) throws Exception {
    30         // TODO Auto-generated method stub
    31         if (isEmpty()) {
    32             throw new Exception("顺序表为空，无法删除！");
    33         }
    34         if (index < 0 || index > size - 1) {
    35             throw new Exception("参数错误！");
    36         }
    37         //移动元素
    38         for (int j = index; j < size - 1; j++) {
    39             listArray[j] = listArray[j + 1];
    40         }
    41         size--;
    42     }
    43 
    44     @Override
    45     public Object get(int index) throws Exception {
    46         // TODO Auto-generated method stub
    47         if (index < 0 || index >= size) {
    48             throw new Exception("参数错误！");
    49         }
    50         return listArray[index];
    51     }
    52 
    53     @Override
    54     public void insert(int index, Object obj) throws Exception {
    55         // TODO Auto-generated method stub
    56         //如果当前线性表已满，那就不允许插入数据
    57         if (size == maxSize) {
    58             throw new Exception("顺序表已满，无法插入！");
    59         }
    60         //插入位置编号是否合法
    61         if (index < 0 || index > size) {
    62             throw new Exception("参数错误！");
    63         }
    64         //移动元素
    65         for (int j = size - 1; j >= index; j--) {
    66             listArray[j + 1] = listArray[j];
    67         }
    68 
    69         listArray[index] = obj;  //不管当前线性表的size是否为零，这句话都能正常执行，即都能正常插入
    70         size++;
    71 
    72     }
    73 
    74     @Override
    75     public boolean isEmpty() {
    76         // TODO Auto-generated method stub
    77         return size == 0;
    78     }
    79 
    80     @Override
    81     public int size() {
    82         // TODO Auto-generated method stub
    83         return size;
    84     }
    85 }

我们来看一下第54行的插入操作insert()方法：如果需要在index位置插入一个数据，那么index后面的元素就要整体往后移动一位。这里面需要特别注意的是：

**插入操作：移动元素时，要从后往前操作，不能从前往后操作，不然元素会被覆盖的**。

**删除元素：移动元素时，要从前往后操作。**

（3）测试类：

public class Test {
    
        public static void main(String[] args) {
    
            SequenceList list = new SequenceList(20);
    
            try {
                list.insert(0, 100);
                list.insert(0, 50);
                list.insert(1, 20);
    
                for (int i = 0; i < list.size; i++) {
                    System.out.println("第" + i + "个数为" + list.get(i));
                }
    
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }

我们要注意插入的规则是什么，不然会觉得这个顺序表打印输出的顺序很奇怪。

运行效果：

[![0e1ffa91-ced8-4e2a-b247-9d19b51b2c19][]][0e1ffa91-ced8-4e2a-b247-9d19b51b2c19 1]

**3、顺序表效率分析：**

*  顺序表插入和删除一个元素的时间复杂度为O(n)。
 *  顺序表支持随机访问，顺序表读取一个元素的时间复杂度为O(1)。因为我们是可以通过下标直接访问的，所以时间复杂度是固定的，和问题规模无关。

**4、顺序表的优缺点：**

*  顺序表的优点是：支持随机访问；空间利用率高（连续分配，不存在空间浪费）。
 *  顺序表的缺点是：**大小固定（**一开始就要固定顺序表的最大长度）**；**插入和删除元素需要移动大量的数据。

**5、顺序表的应用：**

设计一个顺序表，可以保存100个学生的资料，保存以下三个学生的资料，并打印输出。

[![0393f396-1a75-4b69-927f-3e923f86d207][]][0393f396-1a75-4b69-927f-3e923f86d207 1]

代码实现：

(1)List.java:

和上面的代码保持不变

(2)SequenceList.java:

和上面的代码保持不变

(3)Students.java:学生类

//学生类
    public class Students {
    
        private String id;// 学号
        private String name;// 姓名
        private String gender;// 性别
        private int age;// 年龄
    
        public Students() {
    
        }
    
        public Students(String sid, String name, String gender, int age) {
            this.id = sid;
            this.name = name;
            this.gender = gender;
            this.age = age;
        }
    
    
        public String getId() {
            return id;
        }
    
        public void setId(String id) {
            this.id = id;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public String getGender() {
            return gender;
        }
    
        public void setGender(String gender) {
            this.gender = gender;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    
        public String toString() {
            return "学号：" + this.getId() + " 姓名：" + this.getName() + " 性别：" + this.getGender() + " 年龄:" + this.getAge();
        }
    
    }

(4)Test.java:

1 public class Test {
     2 
     3     /**
     4      * @param args
     5      */
     6     public static void main(String[] args) {
     7         // TODO Auto-generated method stub
     8         SequenceList list = new SequenceList(100);
     9 
    10         try {
    11             list.insert(list.size, new Students("S0001", "张三", "男", 18)); //第一个参数list.size代表的是：我每次都是在顺序表的最后一个位置（当前线性表的长度的位置）进行插入操作。这一行里，size是等于0
    12             list.insert(list.size, new Students("S0002", "李四", "男", 19));
    13             list.insert(list.size, new Students("S0003", "王五", "女", 21));
    14 
    15             for (int i = 0; i < list.size; i++) {
    16                 System.out.println(list.get(i));
    17             }
    18 
    19         } catch (Exception ex) {
    20             ex.printStackTrace();
    21         }
    22     }
    23 
    24 }

注意第11行的注释：第一个参数list.size代表的是：我每次都是在顺序表的最后一个位置（当前线性表的长度的位置）进行插入操作；这样的话，遍历时才是按照张三、李四、王五的顺序进行输出的。

运行效果：

[![b0ccde4d-daf2-42c6-91e3-4f2f7a4e4b61][]][b0ccde4d-daf2-42c6-91e3-4f2f7a4e4b61 1]

欢迎工作一到五年的Java工程师朋友们加入Java技术交流群：659270626  
群内提供免费的Java架构学习资料（里面有高可用、高并发、高性能及分布式、Jvm性能调优、Spring源码，MyBatis，Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多个知识点的架构资料）合理利用自己每一分每一秒的时间来学习提升自己，不要再用"没有时间“来掩饰自己思想上的懒惰！趁年轻，使劲拼，给未来的自己一个交代！

[d3384f05-39d1-46d9-a580-bf4b531d740c]: /images/20211108/7207d039ebe947189581e18f87cdcaa1.png
[d3384f05-39d1-46d9-a580-bf4b531d740c 1]: http://images0.cnblogs.com/blog/641601/201508/252153409069025.png
[0e1ffa91-ced8-4e2a-b247-9d19b51b2c19]: /images/20211108/595969261cc8449086f5dae575d12af3.png
[0e1ffa91-ced8-4e2a-b247-9d19b51b2c19 1]: http://images0.cnblogs.com/blog/641601/201508/252153423598269.png
[0393f396-1a75-4b69-927f-3e923f86d207]: /images/20211108/2a4a46c229d14899a23a11470131bd97.png
[0393f396-1a75-4b69-927f-3e923f86d207 1]: http://images0.cnblogs.com/blog/641601/201508/252153470003086.png
[b0ccde4d-daf2-42c6-91e3-4f2f7a4e4b61]: /images/20211108/fce69eda90234088a647c6332dd3d5e0.png
[b0ccde4d-daf2-42c6-91e3-4f2f7a4e4b61 1]: http://images0.cnblogs.com/blog/641601/201508/252153482502802.png