`
zhangshixi
  • 浏览: 675579 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

一维数组

数据结构 
阅读更多

数组是一组具有某种共同特性的原元素集合，它是应用非常广泛的数据存储结构，具有如下特点：

    1. 数组在定义时，不能分配存储空间，在定义完后，才给数组分配存储空间。

    2. 数组根据下标存取元素。

    3. 数组使用时，会进行边界检查。

    4. 数组既可以保存基本类型(基本类型数组)，也可以保存对象引用(对象数组)。

下面为针对一维数组进行的插入、删除、查找的基本实现，为了方便说明，只在数组中存放了基本类型数据，如果想改为对象数组，原理相同。其中：

    1. 代码清单一：为固定长度的无序一维数组的Java实现。

    2. 代码清单二：为固定长度的有序一维数组的Java实现，查找时采用二分法进行查找。

    3. 代码清单三：为可变长度的无序一维数组的Java实现。构造时不必考虑数组的空间大小，亦可在构造后，释放掉增长的多余空间。

 

package com.zhangsx.array;

/**
 * 无序一维数组的Java实现。
 * 构造好以后，数组长度固定。
 * 
 * @author ZhangShixi
 */
public class Array {

    private long[] array;
    private int size;

    /**
     * 构造指定尺寸大小的数组。
     * @param size 数组尺寸大小
     */
    public Array(int size) {
        array = new long[size];
        size = 0;
    }

    /**
     * 获取数组的元素数目。
     * @return 元素数目
     */
    public int size() {
        return size;
    }

    /**
     * 向数组中插入一个元素。
     * @param value 要插入的元素
     */
    public void insert(long value) {
        array[size] = value;
        size++;
    }

    /**
     * 查找数组中的指定元素。
     * @param value 查找元素的关键字
     * @return 如果查找到，返回true；反之，返回false。
     */
    public boolean find(long value) {
        int count;
        for (count = 0; count < size; count++) {
            if (array[count] == value) {
                break;
            }
        }
        if (count == size) {
            return false;
        }
        return true;
    }

    /**
     * 查找数组中指定下下标的元素。
     * @param index 要查找的元素的下标
     * @return 要查找的元素
     */
    public long get(int index) {
        return array[index];
    }

    /**
     * 删除数组中的指定元素。删除元素后，后序元素将逐个前移。
     * @param value 要删除的元素的关键字
     * @return 如果删除成功，返回true；反之，返回false。
     */
    public boolean delete(long value) {
        int count;
        for (count = 0; count < size; count++) {
            if (array[count] == value) {
                break;
            }
        }
        if (count == size) {
            return false;
        } else {
            for (int next = count; next < size; next++) {
                array[next] = array[next + 1];
            }
            size--;
            return true;
        }
    }
}

 

package com.zhangsx.array;

/**
 * 有序一维数组的Java实现。
 * 构造好以后，数组长度固定。
 * 
 * @author ZhangShixi
 */
public class OrderedArray {

    private long[] array;
    private int size;

    /**
     * 获取数组的元素数目。
     * @return 元素数目
     */
    public int size() {
        return size;
    }

    /**
     * 向数组中插入一个元素。
     * 插入后，数组中的元素仍是按关键字有序排列的。
     * @param value 要插入的元素
     */
    public void insert(long value) {
        int index;
        for (index = 0; index < size; index++) {
            if (array[index] > value) {
                break;
            }
        }
        for (int count = index; count < size; count++) {
            array[count + 1] = array[count];
        }
        array[index] = value;
        size++;
    }

    /**
     * 查找数组中的指定元素。
     * 采用二分法查找实现。
     * @param value 要查找的元素的关键字
     * @return 要查找的元素在数组中的下标
     */
    public int find(long value) {
        int start = 0;
        int end = size - 1;
        int index;

        while (true) {
            index = (start + end) / 2;
            if (array[index] == value) {
                return index;
            } else if (end >= start) {
                if (array[index] < value) {
                    start = index + 1;
                } else {
                    end = index - 1;
                }
            } else {
                return size;
            }
        }
    }
    
    /**
     * 查找数组中指定下下标的元素。
     * @param index 要查找的元素的下标
     * @return 要查找的元素
     */
    public long get(int index) {
        return array[index];
    }

    /**
     * 删除数组中的指定元素。删除元素后，后序元素将逐个前移。
     * @param value 要删除的元素的关键字
     * @return 如果删除成功，返回true；反之，返回false。
     */
    public boolean delete(long value) {
        int index = find(value);
        if (index == size) {
            return false;
        } else {
            for (int count = index; count < size; count++) {
                array[count] = array[count + 1];
            }
            size--;
            return true;
        }
    }
}

 

package com.zhangsx.array;

/**
 * 可变长度的无序一维数组的Java实现。
 * 可用其替代原始不可变长度的无序一维数组，使用时不必考虑空间大小。
 * 在向数组中插入数据时，如果数组已满，则会自动增长空间大小。
 * 当数据小于50时，长度默认为50；当数据大于50时，每次扩展的长度为原数组长度的10%。
 * cutOut()方法提供了修剪数组多余空间的实现，使用户在使用后，可释放掉增长的多余空间。
 * 
 * @author ZhangShixi
 */
public class VariableArray {

    private long[] array;
    private int size;
    // 增长因子
    private static final int GROWTH_FACTOR = 10;

    /**
     * 默认构造器
     */
    public VariableArray() {
        array = new long[0];
        size = 0;
    }

    /**
     * 获取数组的元素数目。
     * @return 元素数目
     */
    public int size() {
        return size;
    }

    /**
     * 获取数组的总长度。
     * @return 数组长度
     */
    public int length() {
        return array.length;
    }

    /**
     * 向数组中插入一个元素。
     * @param value 要插入的元素
     */
    public void insert(long value) {
        if (size == array.length) {
            changeCapacity();
        }
        array[size] = value;
        size++;
    }

    /**
     * 查找数组中的指定元素。
     * @param value 查找元素的关键字
     * @return 如果查找到，返回true；反之，返回false。
     */
    public boolean find(long value) {
        int count;
        for (count = 0; count < size; count++) {
            if (array[count] == value) {
                break;
            }
        }
        if (count == size) {
            return false;
        }
        return true;
    }

    /**
     * 查找数组中指定下下标的元素。
     * @param index 要查找的元素的下标
     * @return 要查找的元素
     */
    public long get(int index) {
        return array[index];
    }

    /**
     * 删除数组中的指定元素。删除元素后，后序元素将逐个前移。
     * @param value 要删除的元素的关键字
     * @return 如果删除成功，返回true；反之，返回false。
     */
    public boolean delete(long value) {
        int index;
        for (index = 0; index < size; index++) {
            if (array[index] == value) {
                break;
            }
        }
        if (index == size) {
            return false;
        } else {
            for (int count = index; count < size; count++) {
                array[count] = array[count + 1];
            }
            size--;
            return true;
        }
    }

    /**
     * 改变数组容量。
     */
    private void changeCapacity() {
        long[] temp = new long[getNewlength()];
        System.arraycopy(array, 0, temp, 0, size);
        array = temp;
    }

    /**
     * 裁剪多余空间。
     */
    public void cutOut() {
        if (array.length > size) {
            long[] temp = new long[size];
            System.arraycopy(array, 0, temp, 0, size);
            array = temp;
        }
    }

    /**
     * 计算增长后的数组的新长度。
     * @return 新长度
     */
    private int getNewlength() {
        return array.length < 50
                ? 50 : array.length + array.length / GROWTH_FACTOR;
    }
}

  

2
顶
0
踩
分享到：
| Java数据类型
评论
2 楼 wangyanwei2011 2014-11-11  
第二个类缺少构造函数
public OrderedArray(int size) { 
        array = new long[size]; 
        size = 0; 
    } 
1 楼 rancedxk 2010-06-11  
经测试: 
Array t = new Array(5);
for(int i=5;i>0;i--){
t.insert(i);
}
for(int i=0;i<5;i++){
System.out.print(t.get(i));
}
//返回值为[b]12222[/b]

证明楼主写的第二个有序数组类中的插入元素方法是有问题的
引用

    /** 
     * 向数组中插入一个元素。 
     * 插入后，数组中的元素仍是按关键字有序排列的。 
     * @param value 要插入的元素 
     */ 
    public void insert(long value) {  
        int index;  
        for (index = 0; index < size; index++) {  
            if (array[index] > value) {  
               break;  
            }  
        }  
        for (int count = index; count < size; count++) {  
            array[count + 1] = array[count];  
        }  
        array[index] = value;  
        size++;  
    }

这样的结果是，数组中只保留最后两次插入的元素值！
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    C++一维数组二维数组写入txt，从txt中读取数据存到一维数组二维数组

    1. **一维数组**：一维数组是线性数据结构，可以看作是一系列相同类型元素的集合。声明一维数组时，需要指定数组的类型和大小。例如，`int arr[10]` 定义了一个包含10个整数的一维数组。 2. **二维数组**：二维数组...

    LabVIEW创建一维数组

    一维数组是基本的数组，多维数组是在一维数组的基础上创建的。一维数组的创建过程如下。 　（1）创建数组框架。在前面板窗口控件选板中选择控件“新式→数组、矩阵与簇→数组，置于前面板窗口的空白处，如图1所示。...

    使用Excel两个一维数组构造二维数组.rar

    一维数组可以理解为一个行或列，而二维数组则类似于表格，由多个行和列组成。本案例"使用Excel两个一维数组构造二维数组.rar"重点讲解如何通过Excel的数组公式，将两个一维数组合并成一个二维数组，并进行加法运算。...

    Q1064245.zip c#winform如何实现一维数组转二维数组并保存在某处

    在C#编程中，一维数组到二维数组的转换是一个常见的操作，特别是在处理表格数据或者在Windows Forms（WinForm）应用程序中创建控件布局时。本篇将详细讲解如何进行这种转换以及如何保存二维数组的数据。 首先，让...

    一维数组滤波_一维数组滤波_

    "一维数组滤波"指的是对一维序列数据进行处理，以消除噪声、平滑数据或提取特定频率成分。在这个场景中，描述提到的是使用平均值滤波方法来实现这一目的。 一维数组滤波的核心是数组，它是数据结构的一种，用于存储...

    4-14_lv一维数组中所有元素之和_

    "4-14_lv一维数组中所有元素之和"是一个关于如何在LV中计算一维数组所有元素和的小程序。下面将详细解释这个主题。 一、一维数组的概念 一维数组可以看作是一条线性序列，其中每个元素都有一个唯一的索引。在LV中，...

    labview一维数组转二维数组

    一维数组转二维数组

    一维数组题目8道题带答案

    在这个“一维数组题目8道题带答案”资源中，我们可以期待找到一系列与一维数组相关的练习题，旨在帮助学习者理解和熟练掌握在Unity C#环境中操作数组的技巧。 1. **数组的基本概念**： - 一维数组是线性数据结构，...

    二维数组转一维数组

    将labview内二维数组方便的转化为一维数组使用

    C# json 一维数组 和 二维数组的转换

    C# json 一维数组 和 二维数组的转换 写的非常详细，对大家有帮助

    labview删除一维数组中的所有0元素

    在LabVIEW编程环境中，删除一维数组中的所有0元素是一个常见的操作，特别是在处理数据过滤、数据分析或信号处理等任务时。下面将详细讲解如何在LabVIEW中实现这一功能。 首先，我们需要理解LabVIEW的基本概念。...

    C++两个一维数组相加求和

    本问题主要探讨了如何在C++中实现两个一维数组的相加求和。下面将详细阐述这一过程及其涉及的关键知识点。 首先，我们创建了两个一维整型数组`arr1`和`arr2`，分别初始化为`{1, 2, 3, 4, 5}`和`{6, 7, 8, 9, 10}`。...

    VB 矩阵按列存入一维数组

    在VB（Visual Basic）编程中，处理矩阵数据时，我们可能会遇到需要将二维矩阵的数据转换成一维数组的情况。这通常发生在数据传输、计算优化或内存管理等场景中。本篇将详细介绍如何在VB中实现矩阵按列存入一维数组的...

    k-means对一维数组进行聚类的代码，适合初学者

    本篇只讨论基本的代码实现，由于只是对一维数组的聚类，距离公式上比较简单：distance = |a – b| 适合初学者理解最基本的原理 所谓一维数组 比如： [12, 3, 56, 89, 78, 2, 12, 45, 255, 236] 以下代码实现的是对一...

    数据结构与算法 一维数组-二维数组-三维数组

    在本主题中，我们将深入探讨一维数组、二维数组和三维数组的概念，以及如何使用模板来实现这些数据结构。这些基础知识在编程中至关重要，尤其是在处理大量数据时。 一维数组是最基础的数据结构之一，它是一个有序的...

    利用Excel公式将二维数组按列转换为一维数组.rar

    在Excel中，处理数据时经常会遇到需要将二维数组转换为一维数组的情况。二维数组通常由多行多列组成，而一维数组则只有一行或一列。这种转换在数据分析、公式应用等方面非常常见，有助于简化计算和提高效率。在本...

    1.6 编程基础之一维数组 python版.zip

    标题中的“1.6 编程基础之一维数组 python版.zip”表明这是一个关于Python编程的基础教程，特别聚焦在使用Python处理一维数组的概念和实践。一维数组在Python中通常表现为列表（list），是编程中常见且基础的数据...

    用一维数组表现的顺序存储结构

    本文将深入探讨一种基础且重要的数据结构——顺序存储结构，特别是在一维数组中的应用。数组，作为最基础的数据结构之一，它在计算机编程中扮演着至关重要的角色。 顺序存储结构是一种线性的数据组织方式，其中元素...

    关于C++信息学竞赛一维数组及其应用52个源文件及试题

    例5.3 一维数组输入n个数，计算所有元素的和，求出最大的元素和最小的元素 1 利用for循环,计算输出1+2+…+100的和 2 输出1—100之间所有偶数。 3 输出1—100之间所有奇数。 4 分别计算1--100之间所有的偶数和、...

Magicbox
Global site tag (gtag.js) - Google Analytics