【数据结构与算法】之数组

大家好，欢迎来到IT知识分享网。

数组

前言：最近把 Java 复习了一遍，有时间就捋一捋数据结构的知识，前面的数组、链表、栈、队列都相对容易理解，但是整理成文章，也要花一些时间。

一、什么是数组

（一）数组的定义

数组是多个相同类型 的数据按一定顺序排列的集合，数组是使用最广泛的数据储存结构。因为创建数组会在内存中开辟一整块连续的空间，数组名指向这块连续空间的首地址。所以数组作为顺序储存结构来实现线性表。

（二）数组的分类

无序数组：数组中的数据无序排列，数据排列顺序为先到先得。先添加的数据排在前面，即其索引较小；后添加的数据排在后面，即其索引较大。

有序数组：数组中的数据是按关键字 升序（或降序）排列的。

无序数组与有序数组的差别：

1. 查找数组元素的 search() 方法，无序数组用线性查找，有序数组可用二分查找，提高效率。
2. 增加数组元素的 add() 方法，无序数组无需排序，有序数组需要将数据排序。

二、为什么要用数组

（一）数组的优点

• 无须为表示线性表中数据之间的逻辑关系而增加额外的存储空间。
• 可以快速地存取表中任一位置的数据。

（三）数组的缺点

• 插入和删除操作需要移动大量数据。
• 当数据个数不确定时，难以确定存储空间的容量。
• 容易造成存储空间的”碎片”。

三、如何操作数据

（一）有序数组

设想你的一款游戏需要记录姓名和分数，GameEntry 类记录了此玩家的姓名和分数，很好的满足了你的需求，代码如下：

 / * 记录姓名和分数的类 * * @author likezhen * @version 1.0 */ public class GameEntry { 
    private String name; private int score; public GameEntry(String name, int score) { 
    this.name = name; this.score = score; } public String getName() { 
    return name; } public int getScore() { 
    return score; } @Override public String toString() { 
    return "(" + this.name + ", " + this.score + ")"; } } 

ScoreBoard 类提供了基本的增加，删除，二分查找等操作，能够满足操作元素的基本需求。代码如下：

 / * 有序数组，提供增、删、查等方法 * * @author likezhen * @version 1.0 */ public class ScoreBoard { 
    private int numEntries = 0; private GameEntry[] board; public ScoreBoard(int capacity) { 
    board = new GameEntry[capacity]; } public int getSize() { 
    return numEntries; } public void add(GameEntry e) { 
    int newScore = e.getScore(); if (numEntries < board.length || newScore > board[numEntries - 1].getScore()) { 
    if (numEntries < board.length) numEntries++; // int j = numEntries - 1; while (j > 0 && board[j - 1].getScore() < newScore) { 
    board[j] = board[j - 1]; j--; } board[j] = e; } else throw new ArrayException("添加失败，数组已满"); } public GameEntry delete(int i) { 
    if (i < 0 || i > numEntries) throw new IndexOutOfBoundsException("无效的位置: " + i); GameEntry temp = board[i]; for (int j = i; j < numEntries - 1; j++) board[j] = board[j + 1]; board[numEntries - 1] = null; numEntries--; return temp; } public int BinarySearch(int searchKey) { 
    int low = 0; int high = numEntries - 1; while (low <= high) { 
    int middle = (low + high) / 2; int midVal = board[middle].getScore(); if (searchKey < midVal) low = middle + 1; else if (searchKey > midVal) high = middle - 1; else return middle; } return -(low + 1); } public void display() { 
    for (int i = 0; i < numEntries; i++) System.out.println(board[i]); } } 

ScoreBoardApp 为测试类。

 / * 有序数组的测试类 * * @author likezhen * @version 1.0 */ public class ScoreBoardApp { 
    public static void main(String[] args) { 
    ScoreBoard scoreBoard = new ScoreBoard(5); scoreBoard.add(new GameEntry("Josn", 158)); scoreBoard.add(new GameEntry("Brown", 780)); scoreBoard.add(new GameEntry("Fork", 450)); scoreBoard.add(new GameEntry("Bale", 350)); scoreBoard.add(new GameEntry("Tick", 999)); System.out.println("--------排行榜--------"); scoreBoard.display(); scoreBoard.add(new GameEntry("Rill", 555)); System.out.println("--------更新后的排行榜--------"); scoreBoard.display(); int i = scoreBoard.BinarySearch(350); System.out.println("索引位置：" + i); scoreBoard.delete(0); scoreBoard.delete(4); System.out.println("--------删除后的排行榜--------"); scoreBoard.display(); } } 

测试结果如下：

D:\Java\jdk\bin\java.exe --------排行榜-------- (Tick, 999) (Brown, 780) (Fork, 450) (Bale, 350) (Josn, 158) --------更新后的排行榜-------- (Tick, 999) (Brown, 780) (Rill, 555) (Fork, 450) (Bale, 350) 索引位置：4 --------删除后的排行榜-------- (Brown, 780) (Rill, 555) (Fork, 450) Process finished with exit code 0 

（二）有序数组

Person 类记录了年龄与姓名。

 class Person { 
    private String lastName; private String firstName; private int age; public Person(String lastName, String firstName, int age) { 
    this.lastName = lastName; this.firstName = firstName; this.age = age; } @Override public String toString() { 
    return "Person{" + "lastName='" + lastName + '\'' + ", firstName='" + firstName + '\'' + ", age=" + age + '}'; } public String getLastName() { 
    return this.lastName; } } 

 / * 无序数组，提供增、删、查等方法 * * @author likezhen * @version 1.0 */ class ObjectArray { 
    private Person[] person; private int nElems; public ObjectArray(int maxSize) { 
    person = new Person[maxSize]; nElems = 0; } public int search(String lastName) { 
    int i; for (i = 0; i < nElems; i++) { 
    if (person[i].getLastName().equals(lastName)) { 
    break; } } if (i == nElems) return -1; else return i; } public void add(String lastName, String firstName, int age) { 
    if (nElems >= person.length) { 
    throw new ArrayException("添加失败，数组已满"); } else { 
    person[nElems] = new Person(lastName, firstName, age); nElems++; } } public boolean delete(String lastName) { 
    int i = search(lastName); if (i == -1) { 
    return false; } else for (int j = i; j < nElems - 1; j++) person[j] = person[j + 1]; person[nElems - 1] = null; nElems--; return true; } public void display() { 
    for (int i = 0; i < nElems; i++) System.out.println(person[i]); } } 

 / * 无序数组的测试类 * * @author likezhen * @version 1.0 */ class ObjectArrayApp { 
    public static void main(String[] args) { 
    int maxSize = 5; ObjectArray arr; arr = new ObjectArray(maxSize); System.out.println("--------添加元素后--------"); arr.add("Tom", "Patty", 15); arr.add("Brown", "Yelo", 52); arr.add("Holly", "Case", 35); arr.add("Adams", "Herry", 13); arr.add("Andy", "Marry", 26); arr.display(); int i = arr.search("Brown"); System.out.println("索引位置：" + i); System.out.println("--------删除有效元素后--------"); if (arr.delete("Tom")) System.out.println("删除成功"); else System.out.println("删除失败"); arr.display(); System.out.println("--------删除无效元素后--------"); if (arr.delete("Tim")) System.out.println("删除成功"); else System.out.println("删除失败"); arr.display(); } } 

D:\Java\jdk\bin\java.exe com.arrry.second.www.ObjectArrayApp --------添加元素后-------- Person{ 
   lastName='Tom', firstName='Patty', age=15} Person{ 
   lastName='Brown', firstName='Yelo', age=52} Person{ 
   lastName='Holly', firstName='Case', age=35} Person{ 
   lastName='Adams', firstName='Herry', age=13} Person{ 
   lastName='Andy', firstName='Marry', age=26} 索引位置：1 --------删除有效元素后-------- 删除成功 Person{ 
   lastName='Brown', firstName='Yelo', age=52} Person{ 
   lastName='Holly', firstName='Case', age=35} Person{ 
   lastName='Adams', firstName='Herry', age=13} Person{ 
   lastName='Andy', firstName='Marry', age=26} --------删除无效元素后-------- 删除失败 Person{ 
   lastName='Brown', firstName='Yelo', age=52} Person{ 
   lastName='Holly', firstName='Case', age=35} Person{ 
   lastName='Adams', firstName='Herry', age=13} Person{ 
   lastName='Andy', firstName='Marry', age=26} Process finished with exit code 0 

对于无序数组，只需要增加在最后一个元素的后面，所以 add ()方法为 O(1)。删除和有序数组的情况相同。线性查找，遍历数组，search()方法为 O(N)。