【Java 实现数据结构】线性表

旧城等待， 2022-02-04 04:57 184阅读 0赞

## 1、线性表 ##

**线性表（linear list）**是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。  
![在这里插入图片描述][20190506230238762.png]

## 2.顺序表 ##

##### 2.1概念及结构 #####

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。  
**顺序表一般可以分为：**  
1）静态顺序表：使用定长数组存储。  
2）动态顺序表：使用动态开辟的数组存储。

##### 2.2 接口实现： #####

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

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

public interface ISequence {
        
        //在pos位置插入val
        boolean add(int pos,Object data);
        //查找关键字key 找到返回key的下标，没有返回-1;
        int search(Object key);
        //查找是否包含关键字key是否在顺序表当中(这个和search有点冲突)
        boolean contains(Object key);
        //得到pos位置的值
        Object getPos(int pos);
        //删除第一次出现的关键字key
        Object remove(Object key);
        //得到顺序表的长度
        int size();
        //打印顺序表
        void display();
        //清空顺序表以防内存泄漏
        void clear();
    }

#### MySequenceImpl.java ####

import java.util.Arrays;
    
    public class MySequenceImpl implements ISequence {
        
    
        private Object[] elem;
        private int usedSize;//有效数据个数
        private static final int DEFAULT_SIZE = 10;
    
        public MySequenceImpl() {
        
            this.elem = new Object[DEFAULT_SIZE];
            this.usedSize = 0;
        }
    
        private boolean isFull() {
        
            /*if(this.usedSize == this.elem.length) {
                return true;
            }
            return false;*/
            return this.usedSize == this.elem.length;
        }
        
    	 //在pos位置插入val
        @Override
        public boolean add(int pos, Object data) {
        
            //1、pos位置的合法性进行判断
            if(pos < 0 || pos > this.usedSize) {
        
                return false;
            }
            //2、判断是否为满。
            if(isFull()){
        
                //2倍扩容
                //System.arraycopy();
                this.elem = Arrays.copyOf(this.elem,
                        2*this.elem.length);
            }
            for (int i = this.usedSize-1; i >= pos; i--) {
        
                this.elem[i+1] = this.elem[i];
            }
            this.elem[pos] = data;
            this.usedSize++;
            return true;
        }
    
        private boolean isEmpty() {
        
            return this.usedSize == 0;
        }
    
    	//查找关键字key 找到返回key的下标，没有返回-1;
        @Override
        public int search(Object key) {
        
            if(isEmpty()){
        
                return -1;
            }
            for (int i = 0; i < this.usedSize; i++) {
        
                if(this.elem[i].equals(key)){
        
                    return i;
                }
            }
            return -1;
        }
        
    	//查找是否包含关键字key是否在顺序表当中(这个和search有点冲突)
        @Override
        public boolean contains(Object key) {
        
            if(isEmpty()){
        
                return false;
            }
            for (int i = 0; i < this.usedSize; i++) {
        
                if(this.elem[i].equals(key)){
        
                    return true;
                }
            }
            return false;
        }
    
    	//得到pos位置的值
        @Override
        public Object getPos(int pos) {
        
            if(pos < 0 || pos >= this.usedSize){
        
                return null;
            }
            return this.elem[pos];
        }
    
    	//删除第一次出现的关键字key
        @Override
        public Object remove(Object key) {
        
            int index = search(key);
            if(index == -1) {
        
                return null;
            }
            Object data = this.elem[index];
            int i;
            for ( i = index; i < this.usedSize-1; i++) {
        
                this.elem[i] = this.elem[i+1];
            }
            this.usedSize--;
            this.elem[i+1] = null;
            return data;
        }
    
    	//得到顺序表的长度
        @Override
        public int size() {
        
            return this.usedSize;
        }
    
    	//打印顺序表
        @Override
        public void display() {
        
            for (int i = 0; i < this.usedSize; i++) {
        
                System.out.print(this.elem[i]+" ");
            }
            System.out.println();
        }
    
    	 //清空顺序表以防内存泄漏
        @Override
        public void clear() {
        
            for (int i = 0; i < this.usedSize; i++) {
        
                this.elem[i] = null;
            }
        }
    }

#### 测试类 TestDemo1.java ####

public class TestDemo1 {
        
    
        public static void main1(String[] args) throws InterruptedException {
        
            MySequenceImpl mySequence = new MySequenceImpl();
    
           /* for (int i = 0; i < 20; i++) {
                mySequence.add(i,i);
            }*/
            /*mySequence.add(19,"gao");*/
            mySequence.add(0,new Person());
            mySequence.add(1,new Person());
            mySequence.add(2,new Person());
            mySequence.display();
    
            mySequence.clear();
            Thread.sleep(1000);
            
            mySequence.display();
            Object res = mySequence.remove(8);
            System.out.println(res);
    
        }
    }

## 3、顺序表效率分析 ##

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

## 4、顺序表的优缺点 ##

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

[20190506230238762.png]: /images/20220204/e89e59bb4cf049cfabae20cfa216b82b.png