java - 数据结构，顺序表

野性酷女 2023-10-08 17:18 64阅读 0赞

1、顺序表和链表都属于数据结构的一部分。  
2、数据结构:C的数据结构和JAVA的数据结构有什么不一样啊?  
数据结构只是一个单独的学科，和语言没有关系。  
用不同的语言实现一样的逻辑。

## 一、线性表 ##

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储  
![在这里插入图片描述][135108304dfa41e1a2ecc84e6b25ca93.png]

## 二、顺序表 - ArrayList ##

### 2.1、概念及结构 ###

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

顺序表一般可以分为：

*  静态顺序表：使用定长数组存储。
 *  动态顺序表：使用动态开辟的数组存储

> 静态顺序表适用于确定知道需要存多少数据的场景.  
> 静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用  
> 相比之下动态顺序表更灵活, 根据需要动态的分配空间大小.  
> ![在这里插入图片描述][0a9f940fb13e40ab835fbb455d6d2919.png]

### 2.2、模拟实现顺序表 - MyArrayList ###

#### 2.2.1、顺序表的属性 ####

public class MyArrayList {
        
        //存储数据的数组
        public int[] elem;
        //usedSize 拿到的是 数组元素的有效个数
        public int usedSize;
    
        public MyArrayList(){
        
            //构造方法，初始化数组的大小为10
            this.elem = new int[10];
        }
    }

![在这里插入图片描述][0a9f940fb13e40ab835fbb455d6d2919.png]

#### 2.2.2、顺序表的方法 ####

###### 打印顺序表 ######

// 打印顺序表
        public void display() {
        
            for(int i = 0; i < usedSize; i++){
        
                System.out.print(elem[i] + " ");
            }
            System.out.println();
        }

![在这里插入图片描述][7eec1f03466443b0bfe61e800e2e0527.png]

###### 获取顺序表长度 ######

// 获取顺序表长度
        public int size() {
        
        	//usedSize 就是数组元素的有效数据个数，所以这就是顺序表的长度
            return usedSize;
        }

###### 在 pos 位置新增元素 ######

// 在 pos 位置新增元素
        public void add(int pos, int data) {
        
            if(pos < 0 || pos > usedSize){
        
                System.out.println(pos + "位置不合法，增加失败！");
                return;
            }
            if(isFull()) {
        
                //扩容，如果顺序表满了，就扩容，没有满就不扩容
                this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
            }
            //向后移元素
            for (int i = usedSize - 1; i > pos ; i--) {
        
                this.elem[i+1] = this.elem[i];
            }
            //插入元素
            this.elem[pos] = data;
            //有效数据+1
            usedSize++;
        }
    
        //判断数组是否满了,如果满了返回true，没有满返回false
        public boolean isFull(){
        
            return this.usedSize == this.elem.length;
        }

![在这里插入图片描述][1060408102934a60a4450e986816c55d.png]

###### 判定是否包含某个元素 ######

// 判定是否包含某个元素
        public boolean contains(int toFind) {
        
            for(int i = 0; i < usedSize; i++){
        
                if(elem[i] == toFind){
        
                    return true;
                }
            }
            return false;
        }

###### 查找某个元素对应的位置 ######

// 查找某个元素对应的位置,找到返回该元素下标，没找到返回-1
        public int search(int toFind) {
        
            for(int i = 0; i < this.usedSize; i++){
        
                if(elem[i] == toFind){
        
                    return i;
                }
            }
            return -1;
        }

###### 获取 pos 位置的元素 ######

// 获取 pos 位置的元素
        public int getPos(int pos) {
        
            if(pos < 0 || pos > this.usedSize){
        
                System.out.println("pos位置不合法！");
                return -1;
            }
            return this.elem[pos];
        }

###### 给 pos 位置的元素设为 value ######

// 给 pos 位置的元素设为 value
        public void setPos(int pos, int value) {
        
            if(pos < 0 || pos > this.usedSize){
        
                System.out.println("pos位置不合法！");
                return;
            }
            this.elem[pos] = value;
        }

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

// 查找某个元素对应的位置,找到返回该元素下标，没找到返回-1
        public int search(int toFind) {
        
            for(int i = 0; i < this.usedSize; i++){
        
                if(elem[i] == toFind){
        
                    return i;
                }
            }
            return -1;
        }
    
    
        //删除第一次出现的关键字key
        public void remove(int toRemove) {
        
            //判断顺序表是否为空
            if(this.usedSize == 0){
        
                System.out.println("顺序表为空，删除失败");
                return;
            }
            //index == -1,说明没有这个数据
            int index = search(toRemove);
            if(index == -1){
        
                System.out.println("没有你要找的数据");
                return;
            }
            //移动元素
            for(int i = index; i < this.usedSize-1; i++){
        
                this.elem[i] = this.elem[i+1];
            }
            //记录有效数据
            this.usedSize--;
        }

###### 清空顺序表 ######

public void clear() {
        
            this.usedSize = 0;
        }

###### 测试 ######

在进行测试的时候，两边中间都要测试

public class TestDome {
        
        public static void main(String[] args) {
        
            MyArrayList myArrayList = new MyArrayList();
            myArrayList.add(0,55);
            myArrayList.add(1,30);
            myArrayList.add(2,5);
            myArrayList.add(3,5);
            myArrayList.display();
    
            myArrayList.remove(55);
            myArrayList.display();
            myArrayList.clear();
            myArrayList.display();
    
        }
    }

#### 模拟实现 - MyArrayList ####

public class MyArrayList {
        
        //存储数据的数组
        public int[] elem;
        //usedSize 拿到的是 数组元素的有效个数
        public int usedSize;
    
        public MyArrayList(){
        
            //构造方法，初始化数组的大小为10
            this.elem = new int[10];
        }
    
        // 打印顺序表
        public void display() {
        
            for(int i = 0; i < usedSize; i++){
        
                System.out.print(elem[i] + " ");
            }
            System.out.println();
        }
    
        // 获取顺序表长度
        public int size() {
        
            return usedSize;
        }
    
        // 在 pos 位置新增元素
        public void add(int pos, int data) {
        
            if(pos < 0 || pos > usedSize){
        
                System.out.println(pos + "位置不合法，增加失败！");
                return;
            }
            if(isFull()) {
        
                //扩容，如果顺序表满了，就扩容，没有满就不扩容
                this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
            }
            //向后移元素
            for (int i = usedSize - 1; i > pos ; i--) {
        
                this.elem[i+1] = this.elem[i];
            }
            //插入元素
            this.elem[pos] = data;
            //有效数据+1
            usedSize++;
        }
    
        //判断数组是否满了,如果满了返回true，没有满返回false
        public boolean isFull(){
        
            return this.usedSize == this.elem.length;
        }
    
        //扩容，如果顺序表满了，就扩容
        public void dilatation(){
        
            if(this.usedSize == this.elem.length){
        
                this.elem = Arrays.copyOf(this.elem,this.elem.length*2);
            }
        }
    
        // 判定是否包含某个元素
        public boolean contains(int toFind) {
        
            for(int i = 0; i < usedSize; i++){
        
                if(elem[i] == toFind){
        
                    return true;
                }
            }
            return false;
        }
    
        // 获取 pos 位置的元素
        public int getPos(int pos) {
        
            if(pos < 0 || pos > this.usedSize){
        
                System.out.println("pos位置不合法！");
                return -1;
            }
            return this.elem[pos];
        }
        // 给 pos 位置的元素设为 value
        public void setPos(int pos, int value) {
        
            if(pos < 0 || pos > this.usedSize){
        
                System.out.println("pos位置不合法！");
                return;
            }
            this.elem[pos] = value;
        }
    
        // 查找某个元素对应的位置,找到返回该元素下标，没找到返回-1
        public int search(int toFind) {
        
            for(int i = 0; i < this.usedSize; i++){
        
                if(elem[i] == toFind){
        
                    return i;
                }
            }
            return -1;
        }
    
    
        //删除第一次出现的关键字key
        public void remove(int toRemove) {
        
            //判断顺序表是否为空
            if(this.usedSize == 0){
        
                System.out.println("顺序表为空，删除失败");
                return;
            }
            //index == -1,说明没有这个数据
            int index = search(toRemove);
            if(index == -1){
        
                System.out.println("没有你要找的数据");
                return;
            }
            //移动元素
            for(int i = index; i < this.usedSize-1; i++){
        
                this.elem[i] = this.elem[i+1];
            }
            //记录有效数据
            this.usedSize--;
        }
    
        // 清空顺序表
        public void clear() {
        
    //        for(int i = this.usedSize - 1; i <= 0; i--){
        
    //            this.elem[i] = 0;
    //        }
            this.usedSize = 0;
        }
    }

[135108304dfa41e1a2ecc84e6b25ca93.png]: https://img-blog.csdnimg.cn/135108304dfa41e1a2ecc84e6b25ca93.png
[0a9f940fb13e40ab835fbb455d6d2919.png]: https://img-blog.csdnimg.cn/0a9f940fb13e40ab835fbb455d6d2919.png
[7eec1f03466443b0bfe61e800e2e0527.png]: https://img-blog.csdnimg.cn/7eec1f03466443b0bfe61e800e2e0527.png
[1060408102934a60a4450e986816c55d.png]: https://img-blog.csdnimg.cn/1060408102934a60a4450e986816c55d.png