数据结构（2.1）-线性表的顺序表示

￡神魔★判官ぃ 2021-09-23 04:06 279阅读 0赞

顺序表使用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。线性表中元素的位序是从1开始的。

**特点：**  
1. 具有随机访问的特性，即通过首地址和元素序号可以在O(1)时间内找到指定元素。  
2. 元素存储密度高，每个节点只存储数据元素。  
3. 逻辑上相邻的元素物理上也相邻，因此，插入和删除操作需要移动大量元素。

**时间复杂度：**

1.  插入操作：  
    最好情况–在表尾插入O(1)  
    最坏情况–在表头插入O(n)  
    平均情况–O(n)
2.  删除操作：  
    最好情况–在表尾删除O(1)  
    最坏情况–删除表头元素O(n)  
    平均情况–O(n)
3.  查找操作：  
    索引查找–O(1)  
    按值查找–最好情况，查找元素就在表头O(1)  
    最坏情况，查找元素在表尾O(n)  
    平均情况O(n)

顺序表的Java实现：  
接口部分：

/** * @author zfr * */
    public interface ISeqList<T> {
        /** * 判断线性表是否为空 * @return */
        boolean isEmpty();
        /** * 返回线性表的长度 * @return */
        int length();
        /** * 返回第i（i>=0）个元素 * @param i * @return */
        T get(int i);
        /** * 设置第i个元素的值 * @param i * @param x */
        void set(int i,T x);
        /** * 插入x作为第i个元素 * @param i * @param x */
        void insert(int i,T x);
        /** * 在线性表尾部添加元素x * @param x */
        void append(T x);
        /** * 删除第i个元素，并返回该元素的值 * @param i * @return */
        T remove(int i);
        /** * 删除所有元素 */
        void removeAll();
        /** * 查找并返回首次出现元素key的位置 * @param key * @return */
        int search(T key);
        /** * 打印线性表 */
        void print();
    }

实现部分：

package 线性表;
    
    public class SeqList<T> implements ISeqList<T> { 
        /** * 成员变量 表示表的长度 */
        protected int length;
        /** * 成员变量，对象数组 */
        protected Object[] data;
        /** * 默认构造函数，创建默认容量的空表 */
        public SeqList() {
            // TODO Auto-generated constructor stub
            this(20);
        }
        /** * 构造方法，创建容量为size的表 * @param size */
        public SeqList(int size) {
            // TODO Auto-generated constructor stub
            this.data=new Object[size];//创建长度为size的数组
            this.length = 0;//初始长度为0
        }
        /** * 判断是否为空表 */
        @Override
        public boolean isEmpty() {
            // TODO Auto-generated method stub
            return this.length==0;
        }
        /** * 返回表的长度 */
        @Override
        public int length() {
            // TODO Auto-generated method stub
            return length;
        }
        /** * 返回表中第i个元素的值 */
        @SuppressWarnings("unchecked")
        @Override
        public T get(int i) {
            // TODO Auto-generated method stub
            if(i>=0 && i<length)
                return (T) data[i];
            return null;
        }
        /** * 设置第i个元素的值为x */
        @Override
        public void set(int i, T x) {
            // TODO Auto-generated method stub
            if(x==null)
                return ;
            if(i>=0 && i<length)
                data[i] = x;
            else
                throw new IndexOutOfBoundsException(i+"");//抛出越界异常
        }
        /** * 在第i个位置插入元素x */
        @Override
        public void insert(int i, T x) {
            // TODO Auto-generated method stub
            if(x==null)
                return;
            //数组已满 需要扩容
            if(data.length==length){
                  Object[] temp = this.data;
                  this.data=new Object[length*20];
                  for(int j=0;j<length;j++){
                      this.data[j]=temp[j];
                  }
            }
            //下标容错
            if(i<0)
                i=0;
            if(i>this.length)
                i=this.length;
            //元素后移
            for(int j=this.length;j>i;j--){
                this.data[j]=this.data[j-1];
            }
            //为第i个位置赋值
            this.data[i]=x;
            length++;
        }
        /** * 在末尾加入元素x */
        @Override
        public void append(T x) {
            // TODO Auto-generated method stub
            insert(this.length,x);
        }
        /** * 删除第i个位置的元素 */
        @Override
        public T remove(int i) {
            // TODO Auto-generated method stub
            if(this.length==0||i<0||i>=this.length)
                return null;
            //记录该位置为元素
            T old = (T) this.data[i];
            for(int j=i;j<length-1;j++){
                this.data[j]=this.data[j+1];
            }
            this.length--;
            return old;
        }
        /** * 删除所有元素 */
        @Override
        public void removeAll() {
            // TODO Auto-generated method stub
            this.length=0;
        }
        /** * 查找元素key第一次出现的位置 */
        @Override
        public int search(T key) {
            // TODO Auto-generated method stub
            for(int i=0;i<length;i++)
            {
                if(this.data[i].equals(key))
                    return i;
            }
            return -1;
        }
        /** * 打印顺序表 */
        @Override
        public void print() {
            // TODO Auto-generated method stub
            for(int i=0;i<length;i++){
                System.out.print(this.data[i]+" ");
            }
            System.out.println();
        }
        /** * 比较两个顺序表是否相等 */
        @Override
        public boolean equals(Object obj) {
            // TODO Auto-generated method stub
            return super.equals(obj);
        }
        /** * 将顺序表转换为字符串 */
        @Override
        public String toString() {
            // TODO Auto-generated method stub
            String str="";
            if(this.length>0)
                str+=this.data[0].toString();
            for(int i=1;i<this.length;i++)
                str+=","+this.data[i].toString();
            return str;
        }
    
    }