[数据结构] 线性表和顺序表

目录

 线性表

顺序表的实现

顺序表各个方法的实现

boolean isFull() -- 判断数组是否放满 :

void add(int data) -- 在数组末尾插入新元素 : 

void add(int pos,int data) -- 在指定位置插入元素 : 

boolean contain(int toFind) -- 判断是否包含某个元素

int indexOf(int toFind) -- 查找某个对应元素的位置

int get(int pos) -- 获取pos位置的元素

void set(int pos,int value) -- 将pos位置的元素设为value

void remove (int toRemove)——删除第一次出现的关键字

void removeAll (int toRemove)——删除所有出现的关键字

void clear ()——清空顺序表

---

 线性表

线性表是n个具有相同特性的数据元素的有限序列.线性表是一种在实际中广泛应用的数据结构,常见的线性表: 顺序表, 链表, 栈, 队列...

线性表在逻辑上是线性结构,也就是说连续的一条直线.但是在物理结构上并不一定是连续的,线性表在屋里上存储时,通常以数组和链式结构的形式存储.

 

顺序表的实现

1. 创建一个IList 接口, 用来放所有相关方法

public interface IList {boolean isFull(); // 判断数组是否放满void add(int data); // 在数组末尾新增元素void add(int pos,int data); // 给指定位置插入数据boolean contain(int toFind); // 判断是否包含某个元素int indexOf(int toFind); // 查找某个对应元素的位置int get(int pos); // 获取pos位置的元素void set(int pos,int value);// 将pos位置的元素设为valuevoid remove(int toRemove); // 删除第一次出现的关键字void removeAll(int roRemove); // 删除所有出现的关键字void clear(); // 清空顺序表
}

2.创建一个MyArrayList 类, 数组成员变量 int[] elem 用来放数据, 整形成员变量usedSize 用来记录数组里面的数据个数

3.在 MyArrayList 类里面实现IList 接口, 并重写里面的方法

顺序表各个方法的实现

boolean isFull() -- 判断数组是否放满 :

直接返回usedSize == elem.length 即可,相等为true, 不等为false

public boolean isFull() {return size == elem.length;}

void add(int data) -- 在数组末尾插入新元素 : 

1.先用isFull()方法判断数组是否放满,若装满,就调用Arrays的copyOf(elem,2*elem.length)方法对数组进行扩容

2.将第usedSize位的数组元素赋值为data

3.usedSize++

public void add(int data) {if(isFull()) {elem = Arrays.copyOf(elem,elem.length * 2); // 如果满了就扩容为原来的两倍}elem[size] = data;size++;}

void add(int pos,int data) -- 在指定位置插入元素 : 

1.首先判断传入的参数pos是否合法:

                1).创建一个checkPosOfAdd(int pos)方法来进行判断

                2).若(pos < 0 || pos >= usedSize) ,则抛出一个自定义异常 PosNotLegalException

2.再用isFull()方法判断数组是否装满,若装满,调用Arrays的copyOf(elem,2*elem.length)方法对数组进行扩容

3.移动元素,将后面的元素从后往前依次向后移动一位elem[usedSize] = elem[usedSize - 1]

4.插入元素,elem[pos] = data

5.usedSize++

public void add(int pos, int data) {// 判断pos是否合法try {checkAddPos(pos);} catch (PosNotLegalException e) {e.printStackTrace();}// 判断数组是否放满if(isFull()) {elem = Arrays.copyOf(elem,2*elem.length);}// 移除元素for (int i = usedSize - 1;i >= pos;i--) {elem[i+1] = elem[i];}elem[pos] = data;usedSize++;}

void checkAddPos(int pos) -- 检查传入add方法中的pos是否合法 : 

                若不合法则抛出一个自定义异常 PosNotLegalException

private void checkAddPos(int pos) {if(pos < 0 || pos >= usedSize) {throw new PosNotLegalException("pos位置不合法");}}

PosNotLegalException -- 传入参数不合法的自定义异常

                继承自运行时异常 RuntimeException

public class PosNotLegalException extends RuntimeException{public PosNotLegalException(String msg) {super(msg);}
}

boolean contain(int toFind) -- 判断是否包含某个元素

1.遍历数组

2.当elem[i] == toFind 时, return true;

3.找不到,return false

public boolean contain(int toFind) {for (int i = 0;i < usedSize;i++) {if(elem[i] == toFind) {return true;}}return false;}

int indexOf(int toFind) -- 查找某个对应元素的位置

1.遍历数组

2.当elem[i] == toFind 时, return i;

3.找不到 return -1;

public int indexOf(int toFind) {for (int i = 0;i < usedSize;i++) {if(elem[i] == toFind) {return i;}}return -1;}

int get(int pos) -- 获取pos位置的元素

1.判断传入的参数pos是否合法

        1)创建 checkPosOfGetAndSet(int pos) 方法来进行判断

        2)若 (pos < 0 || pos >= usedSize) , 则抛出自定义异常 PosNotLegalException

2.合法, return elem[pos]

public int get(int pos) {try {checkPosOfGetAndSet(pos);} catch (PosNotLegalException e) {e.printStackTrace();}return elem[pos];}private void checkPosOfGetAndSet(int pos) {if(pos < 0 || pos >= usedSize) {throw new PosNotLegalException("pos位置不合法");}}

void set(int pos,int value) -- 将pos位置的元素设为value

1. 判断传入的参数pos是否合法

        1).调用checkPosOfGetAndSet(int pos) 方法来判断

        2).若 (pos < 0 || pos >= usedSize) , 则抛出自定义异常 PosNotLegalException

2.赋值: elem[pos] == value;

@Overridepublic void set(int pos, int value) {try {checkPosOfGetAndSet(pos);} catch (PosNotLegalException e) {e.printStackTrace();}elem[pos] = value;}
private void checkPosOfGetAndSet(int pos) {if(pos < 0 || pos >= usedSize) {throw new PosNotLegalException("pos位置不合法");}}

void remove (int toRemove)——删除第一次出现的关键字

1.调用 indexOf() 方法，获取关键字的下标，并对下标进行判断，若 pos == -1，则输出“未找到”

2. 移动元素，将后面的元素从后往前依次向后移一位 elem[pos] = elem[pos + 1];

3.usedSize--;

public void remove(int toRemove) {int pos = indexOf(toRemove);if(pos == -1) {System.out.println("没有要找的关键字");return;}for(int i = pos;i < usedSize-1;i++) {elem[i] = elem[i+1];}usedSize--;}

void removeAll (int toRemove)——删除所有出现的关键字

1. 使用 for 循环多次调用 indexOf() 方法，若 pos != -1，则继续操作
2. 移动元素，将后面的元素从后往前依次向后移一位 `elem[pos] = elem[pos + 1];
3. usedSize--;

public void removeAll(int toRemove) {for(int i = 0;i < usedSize;) {int pos = indexOf(toRemove);if(pos != -1) {for(int j = pos;j < usedSize - 1;j++) {elem[j] = elem[j+1];}usedSize--;} else {break;}}}

void clear ()——清空顺序表

• 因为是基本类型，直接 usedSize = 0 即可
• 若是引用类型，则需将每一个位置的数据都置为 null (防止内存泄露)

public void clear() {usedSize = 0;}