栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【数据结构】顺序表与ArrayList (上)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【数据结构】顺序表与ArrayList (上)

1. 线性表

      线性表是最基本、最简单、也是最常用的一种数据结构。线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。常见的线性表:顺序表、链表、栈、队列、字符串...

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

顺序表:  

链表: 

 2. 顺序表

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

2.1  顺序表底层的实现

2.1.1   打印顺序表

class SqList{
    public int[] elem ;
    public int usedSize;
    public static final int DEFAULT_SIZE = 10;
    public SqList() {
        this.elem = new int[DEFAULT_SIZE];
    }
    
    public void display(){
        for (int i = 0; i < this.usedSize; i++) {
            System.out.println(this.elem[i]+"  ");
        }
    }
}
public class ArrayList {
    public static void main(String[] args) {
        SqList  sqList = new SqList();
        sqList.display();
    }
}

2.1.2   在数组末尾新增元素

 思路:1.  判断数组是否已满,若满的话,需要进行扩容;

2.  其次在数组末尾插入新增元素。

class SqList{
    public int[] elem ;
    public int usedSize;
    public static final int DEFAULT_SIZE = 10;
    public SqList() {
        this.elem = new int[DEFAULT_SIZE];
    }
    
    public void add(int data){
         if (this.usedSize == this.elem.length){
             int[] elem = Arrays.copyOf(this.elem,2*this.elem.length);
         }
         this.elem[this.usedSize]=data;
         this.usedSize++;
    }
}
public class ArrayList {
    public static void main(String[] args) {
        SqList  sqList = new SqList();
        sqList.display();
        sqList.add(1);
        sqList.display();


    }
}

2.1.3 在pos位置新增元素

思路:1.  首先需要判断pos位置的合法性,即pos不能小于0或者pos不能大于usedSize;

2. 判断数组是否已满,若已满则需要扩容;

3. 最后将pos位置及其后面的元素向后面挪动,将pos位置腾出来,然后再将指定元素放入到pos位置

class SqList{
    public int[] elem ;
    public int usedSize;
    public static final int DEFAULT_SIZE = 10;
    public SqList() {
        this.elem = new int[DEFAULT_SIZE];
    }
    
    public void display(){
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+"  ");
        }
        System.out.println();
    }
    public void add(int pos,int val){
        if (pos <0 || pos >this.usedSize){
            System.out.println("所输入的pos位置不合法,请重新输入!");
        }
        if (this.usedSize == this.elem.length){
            int[] elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        for (int i = this.usedSize-1; i >=pos ; i--) {
            this.elem[i+1] = this.elem[i];
        }
        this.elem[pos]=val;
        this.usedSize++;
    }
}
public class ArrayList {
    public static void main(String[] args) {
        SqList  sqList = new SqList();
         sqList.add(1);
         sqList.add(2);
         sqList.add(3);
         sqList.add(4);
         sqList.add(5);
         sqList.display();
         sqList.add(2,4);
         sqList.display();


    }
}

2.1.4  判断是否包含某个元素

class SqList{
    public int[] elem ;
    public int usedSize;
    public static final int DEFAULT_SIZE = 10;
    public SqList() {
        this.elem = new int[DEFAULT_SIZE];
    }
    
    public void display(){
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+"  ");
        }
        System.out.println();
    }
    public boolean contains(int find){
        for (int i = 0; i < this.usedSize; i++) {
            if (find == this.elem[i]){
                return true;
            }
        }
        return false;
    }
}
public class ArrayList {
    public static void main(String[] args) {
        SqList  sqList = new SqList();
         sqList.add(1);
         sqList.add(2);
         sqList.add(3);
         sqList.add(4);
         sqList.add(5);
         sqList.display();
        boolean ret = sqList.contains(5);
        System.out.println(ret);

    }
}

2.1.5   查找某个元素的位置

class SqList{
    public int[] elem ;
    public int usedSize;
    public static final int DEFAULT_SIZE = 10;
    public SqList() {
        this.elem = new int[DEFAULT_SIZE];
    }
    
    public void display(){
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+"  ");
        }
        System.out.println();
    }
    public int indexOf(int toFind){
        for (int i = 0; i < this.usedSize; i++) {
            if (toFind == this.elem[i]){
                return i;
            }
        }
        return -1;
    }
}
public class ArrayList {
    public static void main(String[] args) {
        SqList  sqList = new SqList();
         sqList.add(1);
         sqList.add(2);
         sqList.add(3);
         sqList.add(4);
         sqList.add(5);
         sqList.display();
        int tmp = sqList.indexOf(4);
        System.out.println(tmp);

    }
}

2.1.6   获取pos位置的元素

思路:1. 首先判断pos位置的合法性,即pos不能小于0或者pos不能>=usedSize;

2. 判断顺序表是否为空;

3. 最后在获取pos位置的元素。

class SqList{
    public int[] elem ;
    public int usedSize;
    public static final int DEFAULT_SIZE = 10;
    public SqList() {
        this.elem = new int[DEFAULT_SIZE];
    }
    
    public void display(){
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+"  ");
        }
        System.out.println();
    }
    public int get (int pos){
        if (pos < 0 || pos >= this.usedSize){
            System.out.println("pos的位置不合法,请重新输入!");
        }
        if (this.usedSize == 0){
            System.out.println("顺序表为空!");
        }
        return this.elem[pos];

    }

}
public class ArrayList {
    public static void main(String[] args) {
        SqList  sqList = new SqList();
         sqList.add(1);
         sqList.add(2);
         sqList.add(3);
         sqList.add(4);
         sqList.add(5);
         sqList.display();
        int a = sqList.get(3);
        System.out.println(a);
    }
}

2.1.7   给 pos 位置的元素设为 value

思路:1. 首先判断pos位置的合法性,即pos不能小于0或者pos不能>=usedSize;

2. 判断顺序表是否为空;

3. 最后在获取pos位置的元素。

class SqList{
    public int[] elem ;
    public int usedSize;
    public static final int DEFAULT_SIZE = 10;
    public SqList() {
        this.elem = new int[DEFAULT_SIZE];
    }
    
    public void display(){
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+"  ");
        }
        System.out.println();
    }
    public int set (int pos,int data){
        if (pos < 0 || pos >= this.usedSize){
            System.out.println("pos的位置不合法,请重新输入!");
        }
        if (this.usedSize == 0){
            System.out.println("顺序表为空!");
        }
        return this.elem[pos]=data;
    }
}
public class ArrayList {
    public static void main(String[] args) {
        SqList  sqList = new SqList();
         sqList.add(1);
         sqList.add(2);
         sqList.add(3);
         sqList.add(4);
         sqList.add(5);
         sqList.display();
        int ret =sqList.set(2,8);
        System.out.println(ret);
    }
}

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

思路:1.  首先判断顺序表是否为空;

2.  需要找到关键字key的下标;

3.用key的下标后面的数一次往前面覆盖。

class SqList{
    public int[] elem ;
    public int usedSize;
    public static final int DEFAULT_SIZE = 10;
    public SqList() {
        this.elem = new int[DEFAULT_SIZE];
    }
    
    public void display(){
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+"  ");
        }
        System.out.println();
    }
    public int look(int key){
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == key){
                return i;
            }
        }
        return -1;
    }
    public void   remove(int key){
        if (this.usedSize == 0){
            System.out.println("顺序表为空!");
        }
        int indexOf = look(key);
        if(indexOf < 0 ){
            System.out.println("查无此数");
        }
        for (int j = indexOf; j < this.usedSize-1; j++) {
            this.elem[j] = this.elem[j+1];
        }

    }


}
public class ArrayList {
    public static void main(String[] args) {
        SqList  sqList = new SqList();
         sqList.add(1);
         sqList.add(2);
         sqList.add(3);
         sqList.add(4);
         sqList.add(5);
         sqList.display();

        sqList.remove(2);
        sqList.display();
    }
}

2.1.9  获取顺序表长度

class SqList{
    public int[] elem ;
    public int usedSize;
    public static final int DEFAULT_SIZE = 10;
    public SqList() {
        this.elem = new int[DEFAULT_SIZE];
    }
    
    public void display(){
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+"  ");
        }
        System.out.println();
    }
    public int size(){
        return this.usedSize;
    }
}
public class ArrayList {
    public static void main(String[] args) {
        SqList  sqList = new SqList();
         sqList.add(1);
         sqList.add(2);
         sqList.add(3);
         sqList.add(4);
         sqList.add(5);
         sqList.display();

        int ret = sqList.size();
        System.out.println(ret);
    }
}

2.1.10 清空顺序表

有两种情况:1. 如果顺序表里面存的是是基本数据类型:直接让this.usedSize=0.

class SqList{
    public int[] elem ;
    public int usedSize;
    public static final int DEFAULT_SIZE = 10;
    public SqList() {
        this.elem = new int[DEFAULT_SIZE];
    }
    
    public void display(){
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+"  ");
        }
        System.out.println();
    }
    public void clear(){
        this.usedSize = 0;
    }

}
public class ArrayList {
    public static void main(String[] args) {
        SqList  sqList = new SqList();
         sqList.add(1);
         sqList.add(2);
         sqList.add(3);
         sqList.add(4);
         sqList.add(5);
         sqList.display();

        sqList.clear();
        sqList.display();
    }
}

2. 如果数组里面存的是引用数据类型:遍历顺序表,给每个值都赋值给null。

class SqList{
    public int[] elem ;
    public int usedSize;
    public static final int DEFAULT_SIZE = 10;
    public SqList() {
        this.elem = new int[DEFAULT_SIZE];
    }
    
    public void display(){
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+"  ");
        }
        System.out.println();
    }
    public void clear(){
          for (int i = 0; i < this.usedSize; i++) {
            this.elem[i] = null;
        }
    }
}
public class ArrayList {
    public static void main(String[] args) {
        SqList  sqList = new SqList();
         sqList.add(1);
         sqList.add(2);
         sqList.add(3);
         sqList.add(4);
         sqList.add(5);
         sqList.display();

        sqList.clear();
        sqList.display();
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/938872.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号