您的位置:首页 > 娱乐 > 八卦 > 【数据结构】顺序表

【数据结构】顺序表

2024/12/23 16:14:16 来源:https://blog.csdn.net/yj20040627/article/details/140241855  浏览:    关键词:【数据结构】顺序表

目录

  • 线性表
    • 线性表的定义
  • 顺序表
    • 顺序表接口的实现
      • 默认构造方法
      • 将顺序表的底层容量设置为initcapacity
      • 尾插
      • 在 pos 位置新增元素
      • 判定是否包含某个元素
      • 查找某个元素对应的位置
      • 获取 pos 位置的元素
      • 给 pos 位置的元素设为 value
      • 删除第一次出现的关键字key
      • 获取顺序表长度
      • 清空顺序表
  • Java中的ArrayList
    • 实现的接口
    • 构造方法
    • 常用方法
  • 顺序表的优劣
    • 优点
    • 缺点
  • 练习

在这里插入图片描述

线性表

我们要讲顺序表,就不得不先讲线性表,因为顺序表是线性表的一种。

线性表的定义

线性表顾名思义就是将数据像线一样组织起来的表。
可以联想现实中排队来理解。

线性表的特征:

  • 线性表的数据元素之间有顺序。
  • 除了首元素和尾元素,每个元素都有一个前驱和后继。

顺序表

顺序表是用一段物理地址连续的存储单元就像人挨人排队一样,
依次存储数据元素的线性结构,一般情况下采用数组存储。
在数组上完成数据的增删查改。
顺序表的样子

顺序表接口的实现

自己实现一个顺序表(存储int类型数据),将顺序表作为一个类,我们实现一些接口即一些成员方法来实现数据的增删查改。

public class SeqList {private int[] elem;private int usedSize;// 默认构造方法SeqList(){   }// 将顺序表的底层容量设置为initcapacitySeqList(int initcapacity){   }// 新增元素,默认在数组最后新增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 位置的元素设为 valuepublic void set(int pos, int value) {   }//删除第一次出现的关键字keypublic void remove(int toRemove) {   }// 获取顺序表长度public int size() { return 0; }// 清空顺序表public void clear() {   }}

默认构造方法

我们默认最开始开辟10个空间的数据。

private static final int DEFAULT_SIZE = 10;public SeqList() {this.elem= new int[DEFAULT_SIZE];}

将顺序表的底层容量设置为initcapacity

传入数组长度,以数组长度来开辟空间。

private static final int DEFAULT_SIZE = 10;public SeqList(int initcapacity) {this.elem= new int[initcapacity];}

尾插

新增元素,默认在数组最后新增。
考虑要点:

  • 当前顺序表是否已经满了,满了就增加空间。
  • 增加了一个元素usedSize加1。
 public void add(int data) {if(isFull()){elem = Arrays.copyOf(elem,elem.length * 2);}elem[usedSize++] = data;}/*** 判断当前的顺序表是不是满的!** @return true:满   false代表空*/private boolean isFull() {return usedSize == elem.length;}

在 pos 位置新增元素

在pos下标插入元素。
注意事项:

  • 当前顺序表是否已经满了,满了就增加空间。
  • 给的pos位置是否合法,不合法就抛异常。
  • 使用从后向前循环遍历将pos位置后的元素后移。
  • 增加了一个元素usedSize加1。
private boolean checkPosInAdd(int pos) throws PosIllegalException{if(pos < 0 || pos > usedSize){throw new PosIllegalException("位置不合法");}return true;}// 在 pos 位置新增元素public void add(int pos, int data) {try{if(checkPosInAdd(pos)){if(isFull()){elem = Arrays.copyOf(elem,elem.length * 2);}for (int i = usedSize; i > pos ; i--) {elem[i] = elem[i-1];}elem[pos] = data;usedSize++;}}catch(PosIllegalException e){e.printStackTrace();}}

判定是否包含某个元素

看给定的数据是否包含在该顺序表中。
直接循环遍历即可,找到返回true,没有返回false。

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

查找某个元素对应的位置

看给定的数据在该顺序表中下标。
直接循环遍历即可,找到返回下标,没有返回-1。

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

获取 pos 位置的元素

将pos位置的元素输出。
注意事项:

  • 检查pos是否合法
public int get(int pos) {try{if(checkPosInAdd(pos)){return elem[pos];}}catch(PosIllegalException e){e.printStackTrace();}return 0;}

给 pos 位置的元素设为 value

将pos位置元素修改。
注意事项:

  • 检查pos是否合法。
public void set(int pos, int value) {try{if(checkPosInAdd(pos)){elem[pos] = value;}}catch(PosIllegalException e){e.printStackTrace();}}

删除第一次出现的关键字key

将第一次出现的key删除。
注意事项:

  • 循环遍历查找。
  • 用找到的key后面的元素一一向前面覆盖。
  • usedSize减1。
public void remove(int key) {for (int i = 0; i < usedSize; i++) {if(elem[i] == key){for (int j = i; j < usedSize - 1; j++) {elem[j] = elem[j + 1];}usedSize--;}}}

获取顺序表长度

获取顺序表的长度在这就是指有用数据的个数,即usedSize。

public int size() {return usedSize;}

清空顺序表

将顺序表中的内容置为空。
注意事项:

  • 因为真正顺序表存储泛型,一一遍历将元素置为空,下面用置为0代替。
  • UsedSize也置为0。
public void clear() {for (int i = 0; i < usedSize; i++) {elem[i] = 0;}usedSize = 0;}

Java中的ArrayList

在Java中提供了ArrayList类来表示顺序表。

实现的接口

实现的接口

接口说明:

  1. RandomAccess接口表示支持随机访问。
  2. Cloneable接口表示支持克隆。
  3. Serializable接口表示支持序列化。

构造方法

Java提供了3个构造方法如表:

方法方法用途介绍
ArrayList()无参构造
ArrayList(Collection<? extends E> c)利用其他 Collection 构建 ArrayList
ArrayList(int initialCapacity)指定顺序表初始容量

常用方法

提供的常用方法和我们上面自己实现的差不多。
常用方法

顺序表的优劣

优点

顺序表的优点有如下几个方面:

  1. 支持随机访问。
  2. 给定下标查询快。

缺点

  1. 空间不够需要扩容,会有内存的浪费。
  2. 头部和中间的插入删除要摞动数据。

练习

练习的链接如下:
杨辉三角

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com