[数据结构] 线性表和顺序表
目录
线性表
顺序表的实现
顺序表各个方法的实现
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位置的元素设为value
void 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;
@Override public 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)——删除所有出现的关键字
- 使用 for 循环多次调用
indexOf()方法，若pos != -1，则继续操作- 移动元素，将后面的元素从后往前依次向后移一位 `elem[pos] = elem[pos + 1];
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; }