文章目录
线性表
线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。线性表的逻辑上是连续的,物理上不一定连续的，比如数组它在逻辑上和物理上都是连续的,但是链表在逻辑上是连续的在物理上是不连续的。常见的线性表有数组,栈,队列,链表。
数组在内存的存储
链表在内存的存储
线性表定义如下
线性表是具有相同数据类型的n（n≥0）个类型相同的数据元素组成的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同，它可以是一个数或一个符号，也可以是一页书，甚至其他更复杂的信息。线性表通常记为：（a1，…，ai－1，，ai，ai＋1，，…，an），其中n为表长，n＝0时称为空表。表中相邻元素之间存在着顺序关系，ai－1领先于ai，ai领先于ai＋1，称ai－1是ai的直接前驱元素，ai＋1是ai的直接后继元素。当i＝1，2，…，n－1时，ai有且仅有一个直接后继；当i＝2，3，…，n时，ai有且仅有一个直接前驱ai－1；当i＝1，2，…，n－1时，有且仅有一个直接后继ai＋1，而a1是表中第一个元素，它没有前驱，an是最后一个元素，无后继。
前驱:线性表中除了第一个元素以外都有前驱
后继:线性表中除了最后一个元素以外都有后继
顺序表
顺序表是用一段物理地址连续的存储单元依次存储元素的线性结构。一般情况下采用数组存储,在数组上完成数据的增删查改。像Java中的ArrayList就是顺序表,底层是一个Object数组。接下来就使用数组来实现一个简单的顺序表。
接口实现
public class SeqList { // 打印顺序表 public void display() { } // 新增元素,默认在数组最后新增 public void add(int data) { } // 在 pos 位置新增元素 public void add(int pos, int data) { } // 判定是否包含某个元素 public boolean contains(int toFind) { return true; } // 查找某个元素对应的位置 public int indexOf(int toFind) { return -1; } // 获取 pos 位置的元素 public int get(int pos) { return -1; } // 给 pos 位置的元素设为 value public void set(int pos, int value) { } //删除第一次出现的关键字key public void remove(int toRemove) { } // 获取顺序表长度 public int size() { return 0; } // 清空顺序表 public void clear() { } }
属性
private static final int capacity = 3;//初始化数组的容量 private int elem[];//存储元素的数组 private int userSized;//记录顺序表中元素的个数
构造方法
使用无参构造在创建顺序表的时候,为其分配默认的容量
public MyArrayList() { this.size = 0; elementData = new int[CAPACITY]; }
常用方法
打印顺序表
遍历数组即可
/** * 打印顺序表中的数据 */ public void display() { for (int i = 0; i < this.userSized; i++) { System.out.print(this.elem[i] + " "); } System.out.println(); }
添加元素
默认在数组末尾添加元素
/** * 新增元素,默认在数组末尾添加元素 * * @param element */ public void add(int element) { if (isFull()) {//对数组进行判断是否已经满了,满了则2倍扩容 this.elementData = Arrays.copyOf(this.elementData, this.elementData.length * 2); } this.elementData[this.size++] = element; }
在指定位置插入元素
在数组中插入一个元素,并不是使用数组直接访问该位置然后进行修改这个位置的值,这不是插入而是修改。在顺序表中定义一个size属性,记录数组中元素的个数,假设现在数组中有8个元素,那么size指向的位置是在数组中元素的后一个位置,我们可以将从指定插入位置到size-1位置的元素都往后挪一个位置出来,然后再将要插入的元素插入即可。
假设数组长度为11,在数组的索引2处插入一个99，插入过程如下图。
/** * 在指定位置插入元素 * * @param index * @param element */ public void add(int index, int element) { if (isFull()) {//判断是否已满 this.elementData = Arrays.copyOf(this.elementData, this.elementData.length * 2); } //判断index合法 if (index < 0 || index > this.size) { return; } //从要插入元素的位置开始将元素都后移 for (int i = this.size-1; i >= index; i--) { this.elementData[i + 1] = this.elementData[i]; } //插入元素 this.elementData[index] = element; this.size++; }
判定是否包含某个元素
直接遍历数组找到目标值
/** * 判断数组中是否包含该元素 * @param toFind * @return */ public boolean contains(int toFind) { if (isEmpty()){ return true; } for (int i=0;i<this.size;i++) { if (this.elementData[i]==toFind) { return true; } } return false; }
查找某个元素对应的位置(头到尾) /**
/** * 查找某个元素对应的位置(从头到尾) * @param toFind * @return */ public int indexOf(int toFind) { for (int i = 0; i < this.size; i++) { if (this.elementData[i] == toFind) { return i; } } return -1; }
查找某个元素对应的位置(尾–>头)
/** * 查找某个元素对应的位置(从尾都头) * @param toFind * @return */ public int lastIndexOf(int toFind) { for (int i=this.size-1;i>=0;i--) { if (this.elementData[i] == toFind) { return i; } } return -1; }
获得pos位置的值
首先进进判空,在判断pos是否合法,最后直接访问。
/** * pos 位置的元素 * @param pos * @return */ public int get(int pos) { if (isEmpty()) { throw new RuntimeException("MyArrayList为空"); } if (pos < 0 || pos > this.size) { throw new RuntimeException("pos位置不合法"); } return this.elementData[pos]; }
设置pos位置的值
首先进进判空,在判断pos是否合法,最后直接修改。
/** * 给 pos 位置的元素设为 value * @param pos * @param value */ public void set(int pos, int value) { if (pos < 0 || pos > this.size) { throw new RuntimeException("pos不合法"); } this.elementData[pos] = value; }
删除第一次出现的关键字
先找到要删除的位置,然后判断该位置是否合法,然后该位置后面的元素都往前移动一个位置,就可以完成删除。
/** * 删除第一次出现的关键字key * @param key */ public void remove(int key) { int index = searchIndex(key); if (index<0||index>this.size) { throw new RuntimeException("index不合法"); } for (int i=index; i<this.size-1; i++) { this.elementData[i] = this.elementData[i+1]; } this.size--; }
获取顺序表的长度
直接返回size即可
/** * 返回数组的长度 * * @return */ public int size() { return this.size; }
清空顺序表
注意:如果是基本类型,直接将size置空,如果是引用类型要将所有元素置为null,再将size置为0。
/** * 清空数组 */ public void clear(){ this.size = 0; }
顺序表所有的源代码
package com.kc.demo; import java.util.Arrays; public class MyArrayList { private static int[] elementData; private static final int CAPACITY = 5;//初始化数组的容量 private int size; public MyArrayList() { this.size = 0; elementData = new int[CAPACITY]; } /** * 遍历数组 */ public void display() { for (int i = 0; i < this.size; i++) { System.out.print(this.elementData[i] + " "); } System.out.println(); } /** * 新增元素,默认在数组末尾添加元素 * * @param element */ public void add(int element) { if (isFull()) { this.elementData = Arrays.copyOf(this.elementData, this.elementData.length * 2); } this.elementData[this.size++] = element; } /** * 在指定位置插入元素 * * @param index * @param element */ public void add(int index, int element) { if (isFull()) { this.elementData = Arrays.copyOf(this.elementData, this.elementData.length * 2); } //判断index合法 if (index < 0 || index > this.size) { return; } for (int i = this.size-1; i >= index; i--) { this.elementData[i + 1] = this.elementData[i]; } this.elementData[index] = element; this.size++; } /** * 删除第一次出现的关键字key * @param key */ public void remove(int key) { int index = searchIndex(key); if (index<0||index>this.size) { throw new RuntimeException("index不合法"); } for (int i=index; i<this.size-1; i++) { this.elementData[i] = this.elementData[i+1]; } this.size--; } /** * 查找该元素数组中第一次出现的位置 * @param key * @return */ private int searchIndex(int key){ for (int i=0;i<this.size;i++) { if (this.elementData[i]==key) { return i; } } return -1; } /** * 判断数组中是否包含该元素 * @param toFind * @return */ public boolean contains(int toFind) { if (isEmpty()){ return true; } for (int i=0;i<this.size;i++) { if (this.elementData[i]==toFind) { return true; } } return false; } /** * 判断数组是否已经满了 * @return */ private boolean isFull() { if (this.size == CAPACITY) { return true; } return false; } /** * 查找某个元素对应的位置(从头到尾) * @param toFind * @return */ public int indexOf(int toFind) { for (int i = 0; i < this.size; i++) { if (this.elementData[i] == toFind) { return i; } } return -1; } /** * 查找某个元素对应的位置(从尾都头) * @param toFind * @return */ public int lastIndexOf(int toFind) { for (int i=this.size-1;i>=0;i--) { if (this.elementData[i] == toFind) { return i; } } return -1; } /** * 给 pos 位置的元素设为 value * @param pos * @param value */ public void set(int pos, int value) { if (pos < 0 || pos > this.size) { throw new RuntimeException("pos不合法"); } this.elementData[pos] = value; } /** * pos 位置的元素 * @param pos * @return */ public int get(int pos) { if (isEmpty()) { throw new RuntimeException("MyArrayList为空"); } if (pos < 0 || pos > this.size) { throw new RuntimeException("pos位置不合法"); } return this.elementData[pos]; } /** * 判断数组是否为空 * @return */ private boolean isEmpty() { return this.size == 0; } /** * 返回数组的长度 * * @return */ public int size() { return this.size; } /** * 清空数组 */ public void clear(){ this.size = 0; } }
总结
各位看官如果觉得文章写得不错，点赞评论关注走一波！谢谢啦！
