会计信息系统网站建设流程图,湖南百度推广开户,网站前端怎么做,北京市建设局网站目录 前言#xff1a; 线性表
顺序表 接口的实现
一. 打印顺序表
二.新增元素,默认在数组最后新增
三.在 pos 位置新增元素
四.判定是否包含某个元素 五. 查找某个元素对应的位置 六.获取 pos 位置的元素
七.给 pos 位置的元素设为 value
八.删除第一次出现的关键字k…目录 前言 线性表
顺序表 接口的实现
一. 打印顺序表
二.新增元素,默认在数组最后新增
三.在 pos 位置新增元素
四.判定是否包含某个元素 五. 查找某个元素对应的位置 六.获取 pos 位置的元素
七.给 pos 位置的元素设为 value
八.删除第一次出现的关键字key
九.获取顺序表长度
十.清空顺序表
ArrayList的遍历
ArrayList的问题及思考 前言
什么是List
在集合框架中List是一个接口继承自Collection。 站在数据结构的角度来看List就是一个线性表即n个具有相同类型元素的有限序列在该序列上可以执行增删改查以及变量等操作。
List中提供了好的方法具体如下 注意List是个接口并不能直接用来实例化。 如果要使用必须去实例化List的实现类。在集合框架中ArrayList和LinkedList都实现了List接口。 本篇我们开始 ArrayList的学习 线性表 线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列... 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。 顺序表 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。 接口的实现 先初始化数组 有效数字现在为useSize 模拟实现接口里面的所有的功能 也基本上就学会了顺序表的所有功能 实现在MyArrayList这个类中重写 一. 打印顺序表 打印顺序表比较简单知道它的userSize遍历一遍就可以 public void display() {for (int i 0; i useSize ; i) {System.out.print(elem[i] );}System.out.println();} 二.新增元素,默认在数组最后新增 思路 直接找到userSize位置直接赋值就行 有效数组userSize为4 假如我们需要添加5直接在下标为4的位置上赋值 添加完userSize 考虑问题要全如果数组满了我们需要给它扩容已被才可以添加 所有得先判断是否数组满了如果满了先扩容再添加 代码实现
public void add(int data) {//判断if(useSize 5) {elem Arrays.copyOf(elem,elem.length*2);}//添加elem[useSize] data;useSize;} 效果 三.在 pos 位置新增元素 在1下标添加11 应该把1下标后面的元素往后面移动 从userSzie-1下标开始向右移动 并且得先从最右边的元素开始移动 最后userSize 考虑情况 另外pos下标值不能小于0或者大于usersize 代码实现 public void add(int pos, int data) {//先检查是否数组满了吗if(useSize 5) {elem Arrays.copyOf(elem,elem.length*2);}// 判断pos是否合法if(pos 0 || pos useSize) {//抛出异常throw new PosException(pos未知不合法 pos);}for (int i useSize - 1; i pos ; i--) {elem[i1] elem[i];}elem[pos] data;useSize;} 四.判定是否包含某个元素 遍历整个数组再判断 代码实现 public boolean contains(int toFind) {for (int i 0; i useSize; i) {if(elem[i] toFind) {return true;}}return false;} 五. 查找某个元素对应的位置 代码实现 public int indexOf(int toFind) {for (int i 0; i useSize; i) {if(elem[i] toFind) {return i;}}return -1;} 六.获取 pos 位置的元素 这里的pos不能等于userSize了否则越界了 代码实现 public int get(int pos) {判断pos是否合法if(pos 0 || pos useSize) {//抛出异常throw new PosException(pos未知不合法 pos);}return elem[pos];} 七.给 pos 位置的元素设为 value
代码实现 public void set(int pos, int value) {// 判断pos是否合法if(pos 0 || pos useSize) {//抛出异常throw new PosException(pos未知不合法 pos);}elem[pos] value;} 八.删除第一次出现的关键字key 先判断顺序表是否为空 空的不可以删除的 删除结束userSize-- 代码实现 public void remove(int toRemove) {if(useSize 0){throw new EmptyException(顺序表为空);}//获取toRemove下标int index indexOf(toRemove);for (int i index; i useSize - 1 ; i) {elem[i] elem[i1];}useSize--;} 九.获取顺序表长度 public int size() {return useSize;} 十.清空顺序表 public void clear() {useSize 0;}以上基本上就是顺序表所有的基本操作 ArrayList的遍历
一直接打印 二for循环遍历 三. for each遍历 四.使用迭代器 ArrayList的问题及思考 1. ArrayList底层使用连续的空间任意位置插入或删除元素时需要将该位置后序元素整体往前或者往后搬移故时间复杂度为O(N) 2. 增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。 当在ArrayList任意位置插入或者删除元素时就需要将后序元素整体往前或者往后 搬移时间复杂度为O(n)效率比较低因此ArrayList不适合做任意位置插入和删除比较多的场景。 接下来我们会进行 LinkedList(链表)的学习
