【数据结构】线性表和顺序表

简介: 【数据结构】线性表和顺序表

框架


线性表


  • n 个具有相同特征的数据元素的有限序列
    常见的线性表:顺序表、链表、栈、队列…

  • 线性表在逻辑上是线性结构,也就是连续的一条直线
    但在物理结构上不一定是连续的,线性表在物理上存储时,通常以数组链式结构的形式进行存储

顺序表

  • 顺序表其实就是一个数组,是用一段物理地址连续的存储单元依次存储数据元素的线性结构
  • 其访问速度比较快,给定下标情况下,速度为 O (1)
  • 适用于经常进行下标查找或者更新的操作

顺序表实现逻辑

  1. 创建一个 IList 接口,用来放所有相关的方法
  2. 创建一个 MyArrayList 类,数组成员变量 int[ ] elem 用来放数据,整形成员变量 usedSize 用来记录数组里面的数据个数
  3. MyArrayList 类里面实现 IList 接口,并重写里面的方法

各种方法的实现

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

  • 直接返回 usedSize == elem.length 即可,相等为 true,不相等为 false
@Override
    public boolean isFull() {
        return usedSize == elem.length;
    }

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

  1. 首先用 isFUll() 方法判断数组是否装满,若装满,就调用 ArrayscopyOf(elem, 2*elem.length) 方法对数组进行扩容
  2. 将第 usedSize 位的数组元素赋值为 data
  3. usedSize++;
@Override
    public void add(int data) {
        if(isFull()){
            //如果满了,就扩容为原来的两倍
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedSize] = data;
        usedSize++;
    }

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

  1. 首先判断传入的参数 pos 是否合法
  • 我们创建一个 checkPosOfAdd(int pos) 方法来进行判断,
  • (pos < 0 || pos >= usedSize) ,则抛出一个自定义异常 PosNotLegalException
  1. 再用 isFull() 方法判断数组是否装满,若装满,就调用 ArrayscopyOf(elem, 2*elem.length) 方法对数组进行扩容
  2. 移动元素,将后面的元素从后往前依次向后移一位 elem[usedSize] = elem[usedSize - 1];
  3. 插入元素,elem[pos] = data;
  4. usedSize++;
@Override
    public void add(int pos, int data) {
        //判断输入的 pos 是否合法
        try{
            checkAddPos(pos);
        }catch (PosNotLegalException e){
            e.printStackTrace();
        }
        //判断数组是否装满
        if(isFull()){
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        //移动元素
        for (int i = usedSize - 1; i >= pos; i--) {
            elem[i + 1] = elem[i];
        }
        //插入元素
        elem[pos] = data;
        usedSize++;
    }
void checkPosOfAdd (int pos)——检查传入 add 方法中的 pos 是否合法
  • 若不合法则抛出一个自定义异常 PosNotLegalException
private void checkPosOfAdd(int pos) throws PosNotLegalException{  
    if(pos < 0 || pos > usedSize){  
        //自定义一个异常类:PosNotLegalException  
        throw new PosNotLegalException("pos位置不合法");    
    }
}

PosNotLegalException——传入参数不合法的自定义异常
  • 继承自运行时异常 RuntimeException
public class PosNotLegalException extends RuntimeException{  
    public PosNotLegalException(String msg) {  
        super(msg);  
    }
}

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

  1. 遍历数组 usedSize 次
  2. elem[i] == toFind 时,return true;
  3. 找不到,return false;
public boolean contains(int toFind) {  
    //只需要寻找useSize次  
    for (int i = 0; i < usedSize; i++) {  
        if(elem[i]==toFind){  
            return true;  
        }    
    }   
    return false;  
}

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

  1. 遍历数组 usedSize
  2. elem[i] == toFind 时,return i;
  3. 找不到,return 0;
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是否合法
  • 创建 checkPosOfGetAndSet(int pos) 方法来进行判断
  • (pos < 0 || pos > usedSize),则抛出自定义异常 PosNotLegalException
  1. 合法,return elem[pos];
public int get(int pos) {  
    try{  
        checkPosOfGet(pos);  
    }catch (PosNotLegalException e){  
        e.printStackTrace();  
    }    return elem[pos];  
}

void checkPosOfGetAndSet (int pos)——判断输入 get 和 set 方法的值是否合法
  • 若不合法则抛出一个自定义异常 PosNotLegalException
private void checkPosOfGet (int pos) throws PosNotLegalException{  
    if(pos < 0 || pos > usedSize){  
        throw new PosNotLegalException("pos位置不合法");  
    }
}

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

  1. 判断传入的参数pos是否合法
  • 调用 checkPosOfGetAndSet(int pos) 方法来进行判断
  • (pos < 0 || pos > usedSize),则抛出自定义异常 PosNotLegalException
  1. 赋值:elem[pos] == value;
public void set(int pos, int value) {  
    try {  
        checkPosOfGetAndSet(pos);  
    } catch (PosNotLegalException e) {  
        e.printStackTrace();  
    }    
    elem[pos] = value;  
}

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("没有要找的关键字");  
    }    for (int i = pos; i < usedSize - 1; i++) {  
        elem[i] = elem[ i + 1];  
    }    this.usedSize--;  
}

void removeAll (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; i++) {  
        int pos = indexOf(toRemove);  
        if (pos != -1) {  
            for (int j = pos; j < usedSize - 1; j++) {  
                elem[j] = elem[j + 1];  
            }            
            usedSize--;  
        }    
    }
}

void clear ()——清空顺序表

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


相关文章
|
23小时前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
12 3
|
1天前
|
存储 C语言
探索C语言数据结构:利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录,包括初始化、添加、删除、查找和保存联系人信息的操作,以及自定义结构体用于存储联系人详细信息。
11 2
|
23小时前
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
16 6
|
4天前
|
存储 算法 索引
【数据结构】——顺序表
【数据结构】——顺序表
|
5天前
|
存储
数据结构1——顺序表
数据结构1——顺序表
13 1
|
28天前
|
存储 Java 程序员
【数据结构】初识集合&深入剖析顺序表(Arraylist)
Java集合框架主要由接口、实现类及迭代器组成,包括Collection和Map两大类。Collection涵盖List(有序、可重复)、Set(无序、不可重复),Map则由键值对构成。集合通过接口定义基本操作,具体实现由各类如ArrayList、HashSet等提供。迭代器允许遍历集合而不暴露其实现细节。List系列集合元素有序且可重复,Set系列元素无序且不可重复。集合遍历可通过迭代器、增强for循环、普通for循环及Lambda表达式实现,各有适用场景。其中ArrayList实现了动态数组功能,可根据需求自动调整大小。
33 11
|
1天前
01(数据结构考研)线性表相关操作代码
01(数据结构考研)线性表相关操作代码
12 0
|
5天前
|
存储 C语言
数据结构之线性表的初始化及其操作
数据结构之线性表的初始化及其操作
12 0
|
6天前
|
存储 C语言 索引
数据结构--顺序表
数据结构--顺序表
|
6天前
|
算法 Java 测试技术
数据结构 —— Java自定义代码实现顺序表,包含测试用例以及ArrayList的使用以及相关算法题
文章详细介绍了如何用Java自定义实现一个顺序表类,包括插入、删除、获取数据元素、求数据个数等功能,并对顺序表进行了测试,最后还提及了Java中自带的顺序表实现类ArrayList。
9 0