数据结构-顺序表的实现（Java）

• 数据结构篇
• • 第一章 线性表-顺序表
• 前言
• 一、线性表概述
• • 1.什么是线性表
  • 2.线性表的特征
  • 3.线性表的分类
• 二、实现代码
• 总结

       数据结构，用直白的话来说就是把数据元素按照
   一定的关系组织起来的集合，用来操作和存储数据。本
   系列文章主要用java语言来描述各种数据结构。

线性表即若干个数据元素的有序序列，如同生活中的排队一样，如下图：

A在B的前边，则称A是B的前驱元素；D在C的后边，则称D是C的后继元素。

1. 第一个数据元素没有前驱，这个元素被称为头节点；

2. 最后一个元素没有后继，这个元素被称为尾节点；

3. 除第一个和最后一个元素外，有且仅有一个前驱元素和一个数据元素；

   将以上用数学语言来描述：
   a1 a2 a3 … ai-1 ai ai+1 … an

1. 顺序表：地址连续；
2. 链表：地址不连续。

package.sequence:

public class SequenceList implements Iterable {
    private T[] elem;//存储元素的数组
    private int N;//当前线性表的长度

    //创建容量为capacity的SequenceList对象
    public SequenceList(int capacity){
        this.elem = (T[]) new Object[capacity];
        this.N = 0;
    }

    //空置线性表
    public void clear(){
        this.N = 0;
    }

    //判断线性表是否为空，是返回true,否返回false;
    public boolean isEmpty(){
        return this.N == 0;
    }

    //获取线性表中元素的个数；
    public int length(){
        return N;
    }

    //读取并返回表中第i个元素的值
    public T get(int i){
        return elem[i];
    }

    //在线性表i索引元素之前插入一个值为t的元素
    public void insert(int i,T t){
        //扩容操作
        if (N == elem.length){
            resize(2 * elem.length);
        }
        
        //1.第一步：把索引i处及i以后的元素向后移动一位；
        for (int index = N; index > i; index--) {
            elem[index] = elem[index-1];
        }
        //2.第二步：把t元素放到i处；
        elem[i] = t;

        N++;
    }

    //向线性表中添加元素
    public void insert(T t){
        //扩容操作：
        if (N == elem.length){
            resize(2 * elem.length);
        }
        elem[N++] = t;
    }

    //删除并返回线性表第i个数据元素
    public T remove(int i){
        if (N < elem.length/4){
            resize(elem.length / 2);
        }
        
        //1.获取第i个数据元素
        T t = elem[i];
        //2.索引位置后的所有元素依次向前移动
        for (int index = i; index < elem.length-1; index++) {
            elem[index] = elem[index+1];
        }
        N--;
        return elem[i];
    }

    //返回线性表首次出现指定元素的位置序号，若不存在，则返回-1；
    public int indexOf(T t){
        for (int i = 0; i < elem.length; i++) {
            if (t.equals(elem[i])){
                return i;
            }
        }
        return -1;
    }

    //顺序表容量可变：
    public void resize(int newSize){
        //定义一个临时数组，指向原数据
        T[] temp = elem;
        //创建一个新数组
        elem = (T[]) new Object[newSize];
        //将原数组的值赋值给新数组
        for (int i = 0; i < N; i++) {
            elem[i] = temp[i];
        }
    }

//提供遍历：
    @Override
    public Iterator iterator() {
        return new SIterator();
    }


    private class SIterator implements Iterator{
        private int pointer;//定义一个指针

        public SIterator(){
            this.pointer = 0;
        }

        @Override
        public boolean hasNext() {
            return pointer < N;
        }

        @Override
        public Object next() {
            return elem[pointer++];
        }
    }
}

线性表提供遍历：
实现Iterable接口；可通过API查看得Iterable接口中的iterator（）方式其作用是返回一个iterator对象：

iterator是一个接口不能直接new对象，我们定义一个内部类，使其实现iterator接口，并重写next（）方法和hasnext（）方法，就可以在测试类中遍历顺序表中的元素了。

顺序存储结构的优点：
1. 不需要再表中的元素逻辑关系而增加额外的存储空间，
2. 可以通过索引（基于数组）快速获取表中的任意位置的元素。
缺点：
1.插入和删除的操作需要移动其他的元素，“牵一发而动全身”；
2.可能会产生大量的存储空间碎片。

基于以上顺序表的缺点，下一篇我们将讨论线性表的另一种存储结构 — 链表。