数据结构1：顺序表

• 1.数据结构与线性表
• 2. 顺序表
• 3.顺序表的实现

========================================================================

• 数据结构（Data Structure）是一门研究数据的组织和管理的学科。往往从外在表现为一组数据的集合或者容器。
• 元素（Element）：被管理的原子数据，元素类型不限；
• 集合(Collection)：存放元素的容器，需要借助一定的数据机构的知识对元素进行组织；
• 遍历（Traversal）/ 迭代（Iterate）: 在数据结构的语境中，往往表示对一个集合中的数据按照一定顺序处理一次；
• 线性表：是n个相同特性数据元素的有限序列；是在实际使用中重要的且广泛使用的数据结构；
• 常见的线性表：顺序表、链表、队列、栈、字符串…
  

• 顺序表：是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。
• 迭代器：每种容器(Collection)都是具备迭代能力(Iterable)的，每一种容器（数据结构类）都有实现迭代器（接口）的方法，都能实现对元素没差别的的迭代；

例：

public class TestArrayList {
    public static void main(String[] args) {
        //创建一个顺序表：
        ArrayList arrayList = new ArrayList<>();

        //增加add元素Element
        arrayList.add("A");
        arrayList.add("B");
        arrayList.add("C");
        arrayList.add("A");
        System.out.println(arrayList);
        arrayList.add(1,"N");
        System.out.println(arrayList);

        //删除操作
        //删除顺序表中位置下标为index 的 元素，并返回该元素
        String atr=arrayList.remove(1);
        System.out.println(atr);
        System.out.println(arrayList);
        //删除顺序表中第一个出现的该元素
        arrayList.remove("B");

        //修改操作
        arrayList.set(1, "W");
        System.out.println(arrayList);
        //获取操作
        String s=arrayList.get(0);
        System.out.println(s);

        //遍历顺序表，判断顺序表中是否与参数相等的元素
        boolean c=arrayList.contains("W");
        boolean d=arrayList.contains("A");
        System.out.println(c);
        System.out.println(d);

        //查找元素位置，找到返回下标，反之返回-1；
        //从前往后遍历查找
        int index = arrayList.indexOf("W");
        System.out.println(index);
        //从后往前遍历查找第一个出现该元素的位置：
        int i=arrayList.lastIndexOf("A");
        System.out.println(arrayList);
        System.out.println(i);

        //获取顺序表元数个数：
        int n=arrayList.size();
        System.out.println(n);

        //判断顺序表是否为空：
        boolean e=arrayList.isEmpty();
        System.out.println(e);

        //遍历顺序表：
        //(1)循环遍历的方法：
        for (int j = 0; j < arrayList.size(); j++) {
            System.out.printf(arrayList.get(j)+" ");
        }

        System.out.println();

        //(2)利用迭代器Iterator遍历顺序表
        Iterator it=arrayList.iterator();
        while(it.hasNext()){
            System.out.printf(it.next()+" ");
        }
        System.out.println();

        //(3)通过for-each 遍历整个顺序表
        for (String S:arrayList) {
            System.out.println(S);
        }

        //清空顺序表
        arrayList.clear();
        System.out.println(arrayList);
    }
}

该实现方法没有实现泛型，只针对字符串类型；

package dataStructure.ArrayList;

public class MyArrayList {
    private String[] data;
    private int size;
    private int capacity=100;

    //构造方法：
    public MyArrayList(){
        data =new String[capacity];
    }
    //扩容操作:
    public void realloc(){
        capacity=capacity*2;
        String[] dataNew=new String[capacity];
        for(int i=0;i=capacity){
            realloc();
        }
        data[size]=e;
        size++;
        return true;
    }
    public void add(int index,String e){
        if (index==size){
            data[size]=e;
            size++;
            return;
        }
        if (index<0||index>size){
            return;
        }
        for(int i=size-1;i>=index;i--){
            data[i+1]=data[i];
        }
        data[index]=e;
        size++;
    }

    //删除操作：
    public String remove(int index){
        if (index<0||index>size-1){
            return null;
        }
        for(int i=index;i=size){
            return false;
        }
        for(int j=i;jsize-1){
            return null;
        }
        return data[index];
    }
    //set操作：
    public void set(int index,String e){
        if(index<0||index>size-1){
            return;
        }
        data[index]=e;
    }

    //包含操作：
    public boolean contains(String e){
        for (int i=0; i=0;i--){
            if(e.equals(data[i])){
                return i;
            }
        }
        return -1;
    }

    public void clear(){
        size=0;
    }
    public int size(){
        return size;
    }
    public boolean isEmpty(){
        return size==0;
    }

    @Override
    public String toString() {
        StringBuffer stringBuffer=new StringBuffer();
        stringBuffer.append("[");
        for (int i = 0; i < size; i++) {
            stringBuffer.append(data[i]);
            if ((i