首页 > 代码库 > 数据结构3——数组、集合

数据结构3——数组、集合

1:数组是所有高级语言中必备的数据结构储存类型,但是数组有一个明显的缺点:必须提前知道数组内存的大小。这对于需要动态扩展的情况而言,无疑是一个弊端。

  因此创造了一个Vector 类来扩展数组的内存大小。

  1 package com.hone.set;
  2 
  3 //总体的操作集合:扩充数组内存大小,添加,删除,修改,查找
  4 public class MyVector {
  5     
  6     private Object[] elementData;        //定义一个数组
  7     private int elementCount;            //定义数组中元素的个数
  8     
  9     
 10     //定义一个方法用于扩种数组的内存,同传入一个规定的最小内存量
 11     public void ensureCapacity(int minCapacity){
 12         int  oldCapacity=elementData.length;        //获得元数组的长度
 13         if(minCapacity>oldCapacity){            //同时判断要求的最小内存量是否大于原数组的内存,否则无意义
 14             Object[] oldData=http://www.mamicode.com/elementData;        //同时将数组中的元素传入到一个数组中,方便待会儿传入扩充数组中
 15             int newCapacity=oldCapacity*2;        //实现真正的扩充内存作用
 16             if (minCapacity>newCapacity) {        //判断新的内存容量是否满足要求
 17                 newCapacity=minCapacity;
 18             }
 19             elementData=http://www.mamicode.com/new Object[newCapacity];    //将新的数组内存大小传入到原数组中
 20             System.arraycopy(oldData, 0, elementData, 0, elementCount);
 21         }
 22     }
 23     
 24     //定义一个构造函数,当用户不传入自己值的时候,设定默认的值
 25     public MyVector(){
 26         this(10);
 27     }
 28 
 29     //定义一个构造函数,用户自己定义所需要数组内存的大小
 30     public MyVector(int i) {
 31         elementData=http://www.mamicode.com/new Object[i];
 32         elementCount=0;
 33     }
 34     
 35     
 36     //该方法用于在默认的index处,传入一个属性值
 37     /*
 38      * 总体的思路是:首先将原来数组从index开始向后面移动一个位置,空出index的位置
 39      * 然后将element元素复制给index处
 40      */
 41     public void add(int index, Object element){
 42         //首先防止越界
 43         if(index>elementCount){
 44             System.out.println("请输入在数组范围内的下标值");
 45         }
 46         ensureCapacity(elementCount+1);                //扩充数组的大小
 47         System.arraycopy(elementData, index, elementData, index+1, elementCount-index);
 48         elementData[index]=element;
 49         elementCount++;
 50     }
 51     
 52     //同时也可以在数组的最后面直接添加元素
 53     public void add( Object element){
 54         add(elementCount, element);
 55     }
 56     
 57     
 58     //修改index处的元素
 59     public void set(int index , Object element){
 60         //首先防止越界
 61         if(index>elementCount){
 62             System.out.println("请输入在数组范围内的下标值");
 63         }
 64         elementData[index]=element;
 65     }
 66     
 67     //获取index处元素的位置
 68     public Object get(int index){
 69         //首先防止越界
 70         if(index>elementCount){
 71             System.out.println("请输入在数组范围内的下标值");
 72         }
 73         return elementData[index];
 74     }
 75     
 76     //获取数组的大小
 77     public int size(){
 78         return elementCount;
 79     }
 80     
 81     //查找element元素在数组中的下标位置
 82     public int indexOf(Object element){
 83         for (int i = 0; i < elementCount; i++) {
 84             if (element.equals(elementData[i])) 
 85                 return i;
 86         }
 87         return -1;        //返回-1表示没有找到对应的元素或者传入的是一个空值
 88     }
 89     
 90     //判断数组中是否包含某个元素
 91     public boolean contain(Object element){
 92         return indexOf(element)>=0;
 93     }
 94     
 95     //删除下标为index的元素
 96     public void remove(int index){
 97         //首先防止越界
 98         if(index>elementCount||index < 0){
 99             System.out.println("请输入在数组范围内的下标值");
100         }
101         System.arraycopy(elementData, index+1, elementData, index, elementCount-index-1);
102         elementCount--;
103         elementData[elementCount]=null;
104     }
105     
106     //删除element的元素
107     public void removeElement(Object element){
108         int i =indexOf(element);
109         remove(i);
110     }
111 }

1.1:必须说明的是Vector类只支持对象数组,不支持基本数据类型,基本的数据类型必须包装为相应的对象类。

2:集合

集合特征:无序且不重复。

操作集合:

  • 集合是否包含
  • 集合是否相等
  • 集合是否为空
     1 package com.hone.set;
     2 
     3 //设定一个集合类
     4 public class Set {
     5     private MyVector values = new MyVector();
     6     //添加一个元素,这里面必须添加一个不重复的元素
     7     public void add(Object element){
     8         if (element==null) return ;
     9         if (values.indexOf(element)< 0) {
    10             values.add(element);
    11         }
    12     }
    13     
    14     //删除element的元素
    15     public void remove(Object element){
    16         values.removeElement(element);
    17     }
    18     
    19     //判断集合中是否包含某个元素
    20     public boolean contain(Object element){
    21         return values.contain(element);
    22     }
    23     
    24     //检查是否包含某个集合
    25     public boolean include(Object obj){
    26         if (obj instanceof Set) {
    27             Set mySet=(Set) obj;
    28         int count=0;        //用于计数
    29         while (count<values.size()) {
    30             Object ele=values.get(count);        //获取count点对应的元素值
    31             count ++;
    32             if (contain(ele)) 
    33                 return true;
    34             }
    35             return false;
    36         }
    37         else
    38             return false;
    39     }
    40     
    41     //判断两个集合是否相等
    42     public boolean eqauls(Object obj){
    43         if (obj instanceof Set) {
    44             Set myset=(Set) obj;
    45             if (include(myset)&&myset.include(this)) {
    46                 return true;
    47             }
    48             else return false;
    49         }
    50         else return false;
    51     }
    52 
    53     //获取集合的大小
    54     public int size(){
    55         return values.size();
    56     }
    57     //同时判断集合是否为空
    58     public boolean isEmpty(){
    59         return values.size()>0;
    60     }
    61     
    62     //输出集合中的元素
    63     public void print(){
    64         for (int i = 0; i < values.size(); i++) {
    65             System.out.print(values.get(i)+"  ");
    66         }
    67     }
    68 }

     

 

数据结构3——数组、集合