Java数据结构与算法—数组

àì夳堔傛蜴生んèń 2022-05-27 07:40 296阅读 0赞

本节目标：

1.掌握数组的特点

2.掌握有序数组、无序数组的操作

3.掌握数组中二分查找算法

# 数组 #

在Java中，数组是一种**效率最高**的存储和随机访问对象引用序列的方式，数组就是一个简单的**线性序列**，这使得元素访问非常快速，无论使用哪种类型的数组，数组标识符其实只是一个引用，指向在堆中创建的一个真实对象，这个（数组）对象用以保存指向其他对象的引用。数组是第一级对象，可以作为数组初始化语句的一部分隐式地创建此对象，或者用New表达式显示地创建。

数组的优点是效率高，但为此，所付出的代价就是数组对象的大小被固定。这也使得在工作中处理某些数据量不固定的情况下，数组并不实用。这时就需要优选容器，而不是数组。只有在已证明性能成为问题的时候，并且确定切换到数组对性能提高有帮助时，才应该将项目重构为使用数组。

优点：   
1、按照索引查询元素速度快   
2、能存储大量数据   
3、按照索引遍历数组方便

缺点：   
1、根据内容查找元素速度慢   
2、数组的大小一经确定不能改变。   
3、数组只能存储一种类型的数据   
4、增加、删除元素效率慢

5、未封装任何方法，所有操作都需要用户自己定义。

# 无序数组 #

/\*\*  
 \* 无序数组  
 \* 1.按添加元素顺序排序  
 \* 2.元素可重复  
 \*/  
public class MyArray \{  
private Long\[\] arr;  
private int length;//有效数据长度  
/\*  
 \* 无参构造，指定固定数据存储空间100  
 \*/  
public MyArray()\{  
arr = new Long\[100\];  
\}  
/\*  
 \* 有参构造，数据存储空间通过参数指定  
 \*/  
public MyArray(int maxsize)\{  
arr = new Long\[maxsize\];  
\}  
/\*\*  
 \* 添加元素  
 \* 添加到末尾  
 \* @param value  
 \* @return 数组长度  
 \*/  
public int insert(long value)\{  
arr\[length\] = value;  
length++;  
return length();  
\}  
/\*\*  
 \* 通过索引添加元素  
 \* 索引之后的元素依次后移一位  
 \* @param Index  
 \* @return 数组长度  
 \*/  
public int insertByIndex(int index, long newVal)\{  
if(index<0 || index>this.length)\{  
throw new ArrayIndexOutOfBoundsException();  
\}  
for (int i = this.length; i >= index; i--) \{//包括从末尾索引插入  
arr\[i+1\] = arr\[i\];//后移一位  
arr\[i\] = newVal;  
\}  
this.length++;  
return this.length;  
\}  
/\*\*  
 \* 遍历数组  
 \* @return   
 \*/  
public String display()\{  
StringBuffer buf = new StringBuffer();  
buf.append("\[ ");  
for (int i = 0; i < this.length ; i++) \{  
buf.append(arr\[i\] + " ");  
\}  
buf.append("\]");  
return buf.toString();  
\}  
/\*\*  
 \* 通过元素值查询  
 \* @param value  
 \* @return 返回查询到的第一个元素的下标  
 \*/  
public int findByValue(long value)\{  
int j ; //标志位，表示查找到元素的下标  
for (j = 0; j < this.length; j++) \{  
if(arr\[j\] == value)\{  
break;  
\}  
\}  
//如果标志位越界  
if (j == this.length) \{  
return -1;  
\}  
return j;  
\}  
/\*\*  
 \* 通过索引查找  
 \* @param index 索引值  
 \* @return 索引对应的元素值  
 \*/  
public long findByIndex(int index)\{  
if(index < 0 || index > this.length-1)\{  
throw new ArrayIndexOutOfBoundsException();  
\}  
return arr\[index\];  
\}  
/\*\*  
 \* 根据索引删除  
 \* @param index  
 \* @return 被删除的元素值  
 \*/  
public long deleteByIndex(int index)\{  
long delVal = arr\[index\];  
if(index < 0 || index > this.length-1)\{  
throw new ArrayIndexOutOfBoundsException();  
\}  
for(int i=index; i<this.length-1;i++)\{  
arr\[i\] = arr\[i+1\];  
\}  
this.length--;  
return delVal;  
\}  
/\*\*  
 \* 根据索引更新  
 \* @param index 索引  
 \* @param newVal 需要更新的值  
 \* @return 被更新的元素值  
 \*/  
public long update(int index ,long newVal)\{  
long oriVal = arr\[index\];  
if(index < 0 || index > this.length-1)\{  
throw new ArrayIndexOutOfBoundsException();  
\}else\{  
arr\[index\] = newVal;  
return oriVal;  
\}  
\}  
public int length()\{  
return this.length;  
\}

# 有序数组和二分查找 #

public class OrderArray \{  
private Long\[\] arr;//数据存储空间  
private int length;//数据存储空间大小  
/\*\*  
 \* 无参构造  
 \*/  
public OrderArray()\{  
arr = new Long\[100\];  
\}  
/\*\*  
 \* 有参构造  
 \* @param maxsize  
 \*/  
public OrderArray(int maxsize)\{  
arr = new Long\[maxsize\];  
\}  
/\*\*  
 \* 有序插入  
 \* @param value  
 \* @return 插入元素的下标  
 \*/  
    public int insert(long value)\{    
        int i;//标志位，插入位置的下标  
        for(i = 0; i<this.length; i++)\{  
        if (arr\[i\] >= value) \{  
break;  
\}  
        \}  
        //找到插入位置后，在插入前，依次将后面的元素后移一位  
        for (int j = this.length; j >i; j--) \{  
arr\[j\] = arr\[j-1\];  
\}  
        arr\[i\] = value;  
        this.length++;  
        return i;  
    \}   
    /\*\*  
     \* 二分查找  
     \* 前提是有序数组  
     \* @param searchVal   
     \* @return 查找元素的下标  
     \*/  
    public int binaryFind(long searchVal)\{    
        int middle = 0;    
        int low = 0;    
        int pow = this.length;    
        //不断循环进行二分查找    
        while(true)\{    
            middle = (low + pow) / 2;  //取得数组中间位置下标  
            if(arr\[middle\] == searchVal)    
                return middle;    
            else if(low > pow)    
                return -1;    
            else \{  
            if(arr\[middle\] > searchVal)  //中间值大于查询值，查找范围的最大下标设置为middle - 1  
            pow = middle - 1;    
            else    
            low = middle + 1;  //中间值小于查询值，查找范围的最小下标设置为middle + 1  
            \}   
        \}    
    \}    
      
public String display()\{  
StringBuffer buf = new StringBuffer();  
buf.append("\[ ");  
for (int i = 0; i < this.length ; i++) \{  
buf.append(arr\[i\] + " ");  
\}  
buf.append("\]");  
return buf.toString();  
\}

# 对象数组 #

public class Person \{    
    private String name;    //姓名    
    private int age;        //年龄    
    private String sex;     //性别    
      
    public Person(String name, int age, String sex) \{    
        this.name = name;    
        this.age = age;    
        this.sex = sex;    
    \}    
      
    public String getName() \{    
        return name;    
    \}    
    public void setName(String name) \{    
        this.name = name;    
    \}    
    public int getAge() \{    
        return age;    
    \}    
    public void setAge(int age) \{    
        this.age = age;    
    \}    
    public String getSex() \{    
        return sex;    
    \}    
    public void setSex(String sex) \{    
        this.sex = sex;    
    \}  
@Override  
public String toString() \{  
return "Person \[name=" + name + ", age=" + age + ", sex=" + sex + "\]";  
\}

public class PersonArray \{  
private Person\[\] arr; // 声明存储空间对象  
 int elems; // 空间大小  
  
  
// 默认构造函数  
public PersonArray() \{  
arr = new Person\[50\];  
\}  
  
  
public PersonArray(int max) \{  
arr = new Person\[max\];  
\}  
  
  
// 插入对象数据  
public void insert(Person person) \{  
arr\[elems\] = person;  
elems++;  
\}  
  
  
// 显示数据  
public void display() \{  
for (int i = 0; i < elems; i++) \{  
System.out.println(arr\[i\].toString());  
\}  
\}  
  
  
/\*\*  
 \* 根据属性查找  
 \* @param name  
 \* @return 符合条件的第一个对象的下标  
 \*/  
public int find(String name) \{  
int i;  
for (i = 0; i < elems; i++) \{  
if (arr\[i\].getName().equals(name))  
break;  
\}  
if (i == elems)  
return -1;  
return i;  
\}  
  
  
// 根据属性删除  
public void delete(String name) \{  
if (this.find(name) != -1) \{  
for (int i = find(name); i < elems-1; i++) \{  
arr\[i\] = arr\[i + 1\];  
\}  
\} else  
System.out.println("查找不到指定数据，删除失败");  
elems--;  
\}  
  
  
/\*\*  
 \* 根据对象删除  
 \* 删除符合条件的第一个对象  
 \* @param person  
 \*/  
public void delete(Person person) \{  
if (find(person.getName()) == -1)  
System.out.println("查找不到指定数据，删除失败");  
else  
for (int i = find(person.getName()); i < elems-1; i++) \{  
arr\[i\] = arr\[i + 1\];  
\}  
elems--;  
\}  
// 修改数据  
public void change(Person oldPerson, Person newPerson) \{  
if (-1 != find(oldPerson.getName()))  
arr\[find(oldPerson.getName())\] = newPerson;  
else  
System.out.println("查找不到指定数据，修改失败");  
\}  
\}