数据结构:线性表的实现

本文阅读 3 分钟
首页 代码,Java 正文

img

img

增删元素的话,线性结构要保证元素的连续性 img

动态数组是顺序存储结构具体实现的核心思想

img

  • a1是a2的直接前驱
  • a2是a1的直接后继
  • 除了第一个元素a1以外,其他元素都有唯一的直接前驱
  • 除了最后一个元素an以外,其他元素都有唯一的直接后继
  • n表示线性表的长度,当n=0,称为空表

因为线性结构可以有顺序存储结构和链式存储结构实现,那么我i吗就可以把对线性结构的共同操作进行抽取,定义出线性结构的接口 img

public interface List <E> extends Iterable<E>{ 
    public void add(E element);
    public void add(int index,E element);
    public void remove(E element);
    public E remove(int index);
    public E set(int index,E element);
    public E get(int index);
    //获取元素个数
    public int size();
    public int indexOf(E  element);
    public boolean contains(E element);
    public boolean isEmpty();
    public void clear();
    /** * 根据比较器定义的比较规则来进行比较大小 */
    public void sort(Comparator<E> c);
    public List<E> subList(int fromIndex,int toIndex);
}

属性

img

构造器

img

把数组转换为线性表的方法

img

判断是否需要扩容和缩容问题

扩容 img 缩容 img

添加元素的方法

img

删除元素的方法

img

修改元素的值

@Override
    public E set(int index, E element) { 
        if (index < 0 || index >= size) { 
            throw new IllegalArgumentException("set index out of bounds");
        }
        E old = data[index];
        data[index] = element;
        return old;
    }

获取元素的值

@Override
    public E get(int index) { 
        if (index < 0 || index >= size) { 
            throw new IllegalArgumentException("get index out of bounds");
        }
        return data[index];

    }

获取线性表元素个数

@Override
    public int size() { 
        return size;
    }

获取线性表中数组容量

public int getCapacity() { 
        return data.length;
    }

获取元素在线性表下标

@Override
    public int indexOf(E element) { 
        for (int i = 0; i < size; i++) { 
            if (element.equals(data[i])) { 
                return i;
            }
        }
        return -1;
    }

判断是否包含某个元素

@Override
    public boolean contains(E element) { 

        return indexOf(element) != -1;
    }

判断线性表是否为空

@Override
    public boolean isEmpty() { 
        return size == 0;
    }

清空线性表

@Override
    public void clear() { 
        for (int i = 0; i < data.length; i++) { 
            data[i] = null;
        }
        size = 0;

    }

返回子线性表

/** * [formIndex,toIndex] * 要判断索引是否有效 * 根据索引,来返回子线性表 * * @param fromIndex * @param toIndex * @return */
    @Override
    public List<E> subList(int fromIndex, int toIndex) { 
        if (fromIndex < 0 || fromIndex >= size) { 
            throw new IllegalArgumentException("角标越界");
        }
        if (toIndex < 0 || toIndex >= size) { 
            throw new IllegalArgumentException("角标越界");
        }
        if (fromIndex > toIndex) { 
            throw new IllegalArgumentException("角标越界");
        }
        ArrayList<E> subList = new ArrayList<>();
        for (int i = fromIndex; i < toIndex; i++) { 
            subList.add(data[i]);
        }
        return subList;
    }

判断两个线性表是否相等

img

打印线性表的不同方式

@Override
    public String toString() { 
        StringBuilder builder = new StringBuilder(String.format("ArrayList:%d/%d[", size, data.length));
        if (isEmpty()) { 
            builder.append("]");//ArrayList:0/10;
        } else { 
            for (int i = 0; i < size; i++) { 
                builder.append(data[i]);
                if (i != size - 1) { 
                    builder.append(",");
                } else { 
                    builder.append("]");
                }
            }
        }
        return builder.toString();
    }

    /** * 获取ArrayList的迭代器,foreach遍历线性表it.hasNext(),it.next()来遍历 * * @return */
    @Override
    public Iterator<E> iterator() { 


        return new ArrayListIterator();


    }
    class ArrayListIterator implements Iterator<E>{ 
        /** * 判断之后是否有元素 * @return */
        private int cur=0;
        @Override
        public boolean hasNext() { 
            return cur<size;
        }

        /** * 如果后面一个元素存在,则先把元素返回再把指针后移 * @return */
        @Override
        public E next() { 
            return data[cur++];
        }
    }

img

本文为互联网自动采集或经作者授权后发布,本文观点不代表立场,若侵权下架请联系我们删帖处理!文章出自:https://zengyihong.blog.csdn.net/article/details/125701135
-- 展开阅读全文 --
安全面试之XSS(跨站脚本攻击)
« 上一篇 07-24

发表评论

成为第一个评论的人

热门文章

标签TAG

最近回复