4 数组

4.1 概念

数组：是相同类型数据的有序集合，相同类型的若干个数据，按照一定先后次序排列组合而成。其中，每一个数据称作一个数组元素，每个数组元素可以通过一个下标来访问它们

4.2 特点

  • 数组长度是确定的，数组一旦被创建，它的大小就是不可以改变的（有局限性）
  • 存放的元素类型相同
  • 元素可以是任何数据类型，包括基本类型和引用类型
  • 可以存放重复的元素

  • 下标：用来表示数组元素的顺序

    • 数组下标是从0开始，第一个元素下标为0，可以通过下标访问数组元素

4.3 数组的创建和应用

4.3.1 数组的初始化

一维数组

  • 等号左边：

    • 元素类型[] 数组名 例如：int[] arr
    • 元素类型 数组名[] 例如：int arr[]

  • 等号右边：

    • 静态初始化：（根据元素的个数来确定数组的长度）

      • new 元素类型[]{元素,元素…} 例如：new int[]{1, 3, 5}，代表有3个int类型元素的数组
      • {元素，元素…} 例如：{1, 3, 5}，代表是有3个元素的数组

    • 动态初始化：（根据元素的个数来确定数组的长度）

      • new 元素类型[5] 例如：new String[3]，代表是一个可以存放3个String类型元素的数组

  • 示例：

    • int arr[] = new int[3];
    • int arr[] = new int[]{1, 2, 3};
    • int[] arr = {4, 5, 6};

二维数组

  • 等号左边：

    • 元素类型[] 数组名 例如：int[][] arr
    • 元素类型 数组名[] 例如：int arr[][]

  • 等号右边：

    • 静态初始化：

      • new 元素类型[]{元素,元素…} 例如：new int[]{{1, 2, 3}, {4, 5}, {6}}
      • {元素，元素…} 例如：{{1, 2, 3}, {4, 5}, {6}}

    • 动态初始化：

      • new 元素类型[5] 例如：new String[3][2]代表可以存放3个元素，每个元素是可以存放2个String类型数据的数组

  • 示例：

    • int arr[][] = new int[3][2];
    • int arr[][] = new int[][]{{1, 2, 3}, {4, 5}, {6}};
    • int[][] arr = {{1, 2, 3}, {4, 5}, {6}};

4.3.2 数组的访问及遍历

  • 数组的访问

    • 通过下标进行访问 例如：arr[下标]

  • 数组的遍历

    • for循环遍历 例如：for (int i = 0; i < 数组.length; i++) {}

      • 可以进行数组遍历，并且可以在过程中对数组进行修改
      • 定义下标方式进行遍历

    • 增强for循环遍历（for each循环） 例如：for (数据类型 变量名 : 数组) {}

      • 只能进行遍历，不能对数据进行修改
      • for each遍历的效率比普通for循环高
      • 采用声明一个临时的变量来保存元素方式遍历，只能访问元素，不能使用这个变量来改变原来数组中的元素

4.3.3 代码示例

  1. /**
  2.  * 数组基本使用
  3.  */
  4. public class ArrayBase {
  5.     public static void main(String[] args) {
  6.         initArray();
  7.         visitArray();
  8.         dynamicInit();
  9.         traversalArray();
  10.         traversalArrayUpdate();
  12.         //String[] args 可以接收命令行参数
  13.         System.out.println(args); // [Ljava.lang.String;@74a14482
  14.         for (int i = 0; i < args.length; i++) {
  15.             System.out.println(args[i]);
  16.         }
  17.     }
  19.     // 数组的定义
  20.     public static void initArray() {
  21.         // 动态初始化
  22.         int arr[] = new int[3];
  24.         // 静态初始化
  25.         int arr1[] = new int[]{1, 2, 3};
  26.         int[] arr2 = {4, 5, 6};
  27.     }
  29.     // 通过下标访问数组
  30.     public static void visitArray() {
  31.         int[] in = new int[]{23,34,645,234,22,46};
  32.         // 下 标  ：          0   1  2   3  4  5
  34.         System.out.println(in); // [I@1b6d3586  地址
  35.         System.out.println(in.toString()); // [I@1b6d3586
  36.         System.out.println(in[0]); // 23
  37.         System.out.println(in[1]); // 34
  39.         // 修改数组中的数据
  40.         in[0] = 0;
  41.         System.out.println(in[0]); // 0
  42.     }
  44.     // 动态初始化
  45.     public static void dynamicInit() {
  46.         // 动态初始化
  47.         String str[] = new String[3];
  49.         System.out.println(str);  // [Ljava.lang.String;@4554617c
  50.         System.out.println(str.toString()); // [Ljava.lang.String;@4554617c
  52.         // 动态赋值
  53.         str[0] = "jason";
  54.         str[1] = "lyl";
  56.         System.out.println(str[0]); // jason
  57.         System.out.println(str[1]); // lyl
  58.         System.out.println(str[2]); // null -> String (引用数据类型)类型默认值为 null
  60.         int ar[] = new int[3];
  61.         System.out.println(ar[0]); // 0  int 类型默认值为 0
  62.     }
  64.     // 数组的遍历
  65.     public static void traversalArray() {
  66.         String[] str = new String[]{"张三","李四","王五","23","564"};
  68.         /*
  69.          * 第一种方式
  70.          * for循环遍历  快捷键： fori
  71.          * i : 下标
  72.          */
  73.         for (int i = 0; i < str.length; i++) {
  74.             System.out.println(str[i]);
  75.         }
  77.         /*
  78.          * 第二种方式
  79.          * foreach循环遍历  快捷键 iter   （iterator迭代）
  80.          * 把 str 中的数据一个一个给 s，并打印输出
  81.          */
  82.         for (String s : str) {
  83.             System.out.println(s);
  84.         }
  86.         // java.util 数组工具类
  87.         System.out.println(Arrays.toString(str));
  88.     }
  90.     // 遍历中修改数据 测试
  91.     public static void traversalArrayUpdate() {
  92.         int[] arr = new int[]{1, 3, 5};
  94.         // for循环修改数组 测试
  95.         for (int i = 0; i < arr.length; i++) {
  96.             arr[i] += 1;
  97.             System.out.println(arr[i]);           // 2  4  6
  98.         }
  99.         System.out.println(Arrays.toString(arr)); // 可以修改  [2, 4, 6]
  101.         // foreach循环修改数组 测试
  102.         for (int i : arr) {
  103.             i += 1;
  104.             System.out.println(i);                // 3  5  7
  105.         }
  106.         System.out.println(Arrays.toString(arr)); // 修改失败  [2, 4, 6]
  107.     }
  108. }
  1. /**
  2.  * 数组常见问题
  3.  */
  4. public class ArrayException {
  5.     public static void main(String[] args) {
  6.         /*
  7.          * 常见问题
  8.          *
  9.          * 数组下标越界异常
  10.          * 报错：Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 4
  11.          */
  12.         String[] str = new String[]{"张三","李四",null,"王五"};
  13. //        System.out.println(strr[4]);
  15.         /*
  16.          * 空指针异常
  17.          * 报错：java.lang.NullPointerException
  18.          */
  19.         String[] str2 = null;
  20. //        System.out.println(str2[0]);
  22. //        int len = str2.length; // NullPointerException
  24.         int len = str.length;  // 数组长度跟具体存储的数据多少有关，不是从0开始
  25.         System.out.println(len); // 4
  26.     }
  27. }
  1. /**
  2.  * 二维数组
  3.  */
  4. public class Array2d {
  5.     public static void main(String[] args) {
  6.         initArray2d();
  7.         visitArray2d();
  8.         traversalArray2d();
  9.     }
  11.     // 二维数组的初始化
  12.     public static void initArray2d() {
  13.         // 动态初始化
  14. //        int arr[][] = new int[3][2];
  16.         int arr[][] = new int[3][];
  17.         arr[0] = new int[2];
  18.         arr[1] = new int[2];
  19.         arr[2] = new int[2];
  21.         // 静态初始化
  22.         int arr1[][] = new int[][]{{1, 2, 3}, {4, 5}, {6}};
  23.         int[][] arr2 = {{1, 2, 3}, {4, 5}, {6}};
  24.     }
  26.     // 二维数组的访问及修改
  27.     public static void visitArray2d() {
  28.         int arr[][] = new int[][]{{1, 2, 3}, {4, 5}, {6}};
  29.         // 一维 下标                   0         1      2
  30.         // 二维 下标                 0  1  2    0  1    0
  32.         System.out.println(arr[0][2]); // 3
  34.         // 修改数据
  35.         arr[0][2] = 7;
  37.         System.out.println(Arrays.toString(arr)); // [[I@1b6d3586, [I@4554617c, [I@74a14482]
  39.         System.out.println(Arrays.toString(arr[0])); // [1, 2, 7]
  40.     }
  42.     // 二维数组的遍历
  43.     public static void traversalArray2d() {
  44.         int arr[][] = new int[][]{{1, 2, 3}, {4, 5}, {6}};
  45.         // 双重for循环
  46.         for (int i = 0; i < arr.length; i++) {
  47. //            System.out.println(arr[i]);
  48.             for (int j = 0; j < arr[i].length; j++) {
  49.                 System.out.println(arr[i][j]);
  50.             }
  51.         }
  52.     }
  53. }
  1. /**
  2.  * 数组练习
  3.  */
  4. public class ArrayTest {
  5.     public static void main(String[] args) {
  6.         int[] arr = new int[]{12,23,33,213,11,31,94};
  8.         testMaxAndMin(arr);
  9.         int sum = testSum(arr);
  10.         testAverage(arr, sum);
  11.         testReversal(arr);
  12.         testToString(arr);
  13.         testEqual(arr);
  15.         testVarages(110, 119, 120);
  16.         testVarages(arr);
  17.     }
  19.     /**
  20.      * 测试：求最值
  21.      * @param arr int[]
  22.      */
  23.     public static void testMaxAndMin(int[] arr) {
  24.         // 求数组最大值
  25.         int max = arr[0];
  26.         for (int i = 1; i < arr.length; i++) {
  27.             if(max < arr[i]){
  28.                 max = arr[i];
  29.             }
  30.         }
  31.         System.out.println("max：" + max);
  33.         // 求数组最小值
  34.         int min = arr[0];
  35.         for (int i = 1; i < arr.length; i++) {
  36.             if(max > arr[i]){
  37.                 max = arr[i];
  38.             }
  39.         }
  40.         System.out.println("min：" + min);
  41.     }
  43.     /**
  44.      * 测试：求数组总和
  45.      * @param arr int[]
  46.      * @return
  47.      */
  48.     public static int testSum(int[] arr) {
  49.         int sum = 0;
  50.         for (int i = 0; i < arr.length; i++) {
  51.             sum += arr[i];
  52.         }
  53.         System.out.println("总和: "+sum);
  54.         return sum;
  55.     }
  57.     /**
  58.      * 测试：求平均数
  59.      * @param arr int[]
  60.      * @param sum 数组总和
  61.      */
  62.     public static void testAverage(int[] arr, int sum) {
  63.         System.out.println("平均数："+sum/arr.length);
  64.     }
  66.     /**
  67.      * 测试：数组的反转
  68.      * @param arr int[]
  69.      */
  70.     public static void testReversal(int[] arr) {
  71.         System.out.println("原数组：" + Arrays.toString(arr));
  72.         for (int x = 0, y = arr.length-1; x<y; x++,y--) {
  73.             int temp = arr[x];
  74.             arr[x] = arr[y];
  75.             arr[y] = temp;
  76.         }
  77.         System.out.println("反转后：" + Arrays.toString(arr));
  78.     }
  80.     /**
  81.      * 测试：遍历数组元素
  82.      * @param arr int[]
  83.      */
  84.     public static void testToString(int[] arr) {
  85.         System.out.print("[");
  86.         for (int i = 0; i < arr.length; i++) {
  87.             System.out.print(arr[i]+" ");
  88.         }
  89.         System.out.print("]");
  90.         System.out.println();
  91.     }
  93.     /**
  94.      * 测试：判断是否相等
  95.      * @param arr int[]
  96.      */
  97.     public static void testEqual(int[] arr) {
  98.         int[] arr1 = arr;
  99.         // 判断两个数组是否相等
  100.         boolean bn = Arrays.equals(arr,arr1);
  101.         System.out.println("是否相等："+ bn);
  102.     }
  104.     /**
  105.      * 测试：解析可变长参数列表
  106.      * @param arr 可变长参数列表
  107.      */
  108.     public static void testVarages(int... arr) {
  109.         for (int i = 0; i < arr.length; i++) {
  110.             System.out.println(arr[i]);
  111.         }
  112.     }
  113. }
  1. /**
  2.  * 数组的拷贝
  3.  */
  4. public class ArrayTestCopy {
  5.     public static void main(String[] args) {
  6.         int[] arr = new int[]{12,23,33,213,11,31,94};
  8.         testArrayCopy(arr);
  9.         testArraysUtilCopy(arr);
  10.         testSystemArrayCopy(arr);
  11.         testClone(arr);
  12.         testArray2dCopy();
  13.     }
  15.     /**
  16.      * 浅拷贝和深拷贝区别
  17.      * @param arr
  18.      */
  19.     public static void testArrayCopy(int[] arr) {
  20.         // 浅拷贝 - 复制的是引用（引用原来的对象）
  21.         int[] arr1 = null;
  22.         arr1 = arr;
  24.         // 深拷贝 - 复制的是数据（重新创建了一个对象）
  25.         int[] arr2 = new int[arr.length];
  26.         for (int i = 0; i < arr.length; i++) {
  27.             arr2[i] = arr[i];
  28.         }
  30.         System.out.println("原数据 arr:" + arr);
  31.         System.out.println("浅拷贝 arr1:" + arr1);
  32.         System.out.println("深拷贝 arr2:" + arr2);
  34.         // 修改浅拷贝数组，会修改原来数组数据
  35.         arr1[0] = 100;
  36.         System.out.println("修改浅拷贝后原数据 会改变 arr: " + Arrays.toString(arr));
  37.         System.out.println("浅拷贝的数据            arr1: " + Arrays.toString(arr1));
  39.         // 修改深拷贝数组，不会修改原来数组数据
  40.         arr2[0] = 200;
  41.         System.out.println("修改深拷贝后原数据 不会改变 arr: " + Arrays.toString(arr));
  42.         System.out.println("深拷贝的数据              arr2: " + Arrays.toString(arr2));
  43.     }
  45.     /**
  46.      * Arrays工具类拷贝方法 - 深拷贝
  47.      * @param arr
  48.      */
  49.     public static void testArraysUtilCopy(int[] arr) {
  50.         int[] arr3 = Arrays.copyOf(arr,arr.length);
  51.         System.out.println(arr);
  52.         System.out.println(arr3);
  53.         System.out.println(Arrays.toString(arr));
  54.         System.out.println(Arrays.toString(arr3));
  55.     }
  57.     /**
  58.      * System.arraycopy(src,      srcPos,       dest,      destPos,         length);
  59.      * 复制数组解析：   （原数组，从原数组的起始位置，目标数组，目标数组的起始位置，要复制的数组长度）
  60.      * @param arr
  61.      */
  62.     public static void testSystemArrayCopy(int[] arr) {
  63.         int[] arr4 = new int[arr.length];
  64.         System.arraycopy(arr, 0 , arr4, 0, arr.length);
  65. //        int[] arr4 = new int[arr.length-1];
  66. //        System.arraycopy(arr, 1 , arr4, 0, arr.length-1);
  67.         System.out.println("arr4: " + Arrays.toString(arr4));
  68.         System.out.println(arr4 == arr);
  69.         System.out.println(Arrays.equals(arr4, arr));
  70.     }
  72.     /**
  73.      * clone()方法拷贝
  74.      * @param arr
  75.      */
  76.     public static void testClone(int[] arr) {
  77.         int[] clone = arr.clone();
  78.         System.out.println(clone == arr);              // false
  79.         System.out.println(clone.equals(arr));         // false
  80.         System.out.println(Arrays.equals(clone, arr)); // true
  81.         System.out.println(Arrays.toString(clone));
  82.     }
  84.     public static void testArray2dCopy() {
  85.         int[][] arr = new int[][]{{1,2,3},{4,5},{6}};
  86.         int[][] newArr = new int[3][];
  87.         System.arraycopy(arr, 0, newArr, 0, arr.length);
  89.         // 新旧二维数组的内部对象引用是指向同一个地方，所以如果修改数据，新旧数组会同时受到影响
  90.         System.out.println(Arrays.toString(arr));    // [[I@1b6d3586, [I@4554617c, [I@74a14482]
  91.         System.out.println(Arrays.toString(newArr)); // [[I@1b6d3586, [I@4554617c, [I@74a14482]
  93.         arr[0][0] = 100;
  94.         System.out.println(Arrays.toString(arr[0]));
  95.         System.out.println(Arrays.toString(newArr[0]));
  96.     }
  97. }

二维数组拷贝内存结构图分析

04-数组 - 图1

  1. /**
  2.  * 数组常用排序方法练习
  3.  */
  4. public class ArrayTestSort {
  5.     public static void main(String[] args) {
  6.         int[] arr = new int[]{3, 5, 8, 2, 1, 6, 9, 4, 7};
  8.         testArraysSort(arr);
  9.         testSelectSort(arr);
  10.         testSelectSortMoreEfficient(arr);
  11.         testBubbleSort(arr);
  13.         new ArraySortTest().testObjectSort();
  14.     }
  16.     /**
  17.      * 使用Arrays工具类方法,按升序排列数组
  18.      * @param arr
  19.      */
  20.     public static void testArraysSort(int[] arr) {
  21.         Arrays.sort(arr);
  22.         System.out.println("ArraysSort：" + Arrays.toString(arr));
  23.     }
  25.     /**
  26.      * 选择排序
  27.      * @param arr
  28.      */
  29.     public static void testSelectSort(int[] arr) {
  31.         for (int i = 0; i < arr.length; i++) {
  32.             for (int j = i+1; j < arr.length; j++) {
  33.                 if (arr[j] < arr[i]) {
  34.                     int temp = arr[i];
  35.                     arr[i] = arr[j];
  36.                     arr[j] = temp;
  37.                 }
  38.             }
  39.         }
  40.         System.out.println("SelectSort: " + Arrays.toString(arr));
  41.     }
  43.     /**
  44.      * 效率更高的方法
  45.      * @param arr
  46.      */
  47.     public static void testSelectSortMoreEfficient(int[] arr) {
  49.         // 效率较高的排序，减少交换次数，每次比较完后只进行一次交换
  50.         for (int i = 0; i < arr.length; i++) {
  51.             int k = i; // 定义k变量，假设下标为k的值最小
  52.             for (int j = i+1; j < arr.length; j++) {
  53.                 if (arr[j] < arr[k]) {
  54.                     k = j;
  55.                 }
  56.             }
  57.             if (k != i) {
  58.                 int temp = arr[i];
  59.                 arr[i] = arr[k];
  60.                 arr[k] = temp;
  61.             }
  62.         }
  64.         // 在for循环外部定义k和temp，这样不用每次在循环时重新在栈上分配空间，只分配一次
  65.         int k, temp;
  66.         for (int i = 0; i < arr.length; i++) {
  67.             k = i;
  68.             for (int j = i+1; j < arr.length; j++) {
  69.                 if (arr[j] < arr[k]) {
  70.                     k = j;
  71.                 }
  72.             }
  73.             if (k != i) {
  74.                 temp = arr[i];
  75.                 arr[i] = arr[k];
  76.                 arr[k] = temp;
  77.             }
  78.         }
  80.         System.out.println("SelectSortMoreEfficient: " + Arrays.toString(arr));
  81.     }
  83.     /**
  84.      * 冒泡排序
  85.      * @param arr
  86.      */
  87.     public static void testBubbleSort(int[] arr) {
  89.         // 第一种思路
  90.         for (int i = arr.length - 1; i >= 1; i--) {
  91.             for (int j = 0; j <= i - 1; j++) {
  92.                 if (arr[j] > arr[j+1]) {
  93.                     int temp = arr[j];
  94.                     arr[j] = arr[j+1];
  95.                     arr[j+1] = temp;
  96.                 }
  97.             }
  98.         }
  100.         // 另一种思路
  101.         for (int i=0; i<arr.length-1; i++){
  102.             for (int j = 0; j < arr.length-1-i; j++) {
  103.                 if (arr[j] > arr[j+1]){
  104. //                    int temp = arr[j];
  105. //                    arr[j] = arr[j+1];
  106. //                    arr[j+1] = temp;
  107.                     swap(arr, j);
  108.                 }
  109.             }
  110.         }
  112.         System.out.println("BubbleSort从小到大：" + Arrays.toString(arr));
  114.         // 从大到小排序
  115.         for (int i=0; i<arr.length-1; i++){
  116.             for (int j = 0; j < arr.length-1-i; j++) {
  117.                 if (arr[j] < arr[j+1]){ // 修改一下条件即可
  118. //                    int temp = arr[j];
  119. //                    arr[j] = arr[j+1];
  120. //                    arr[j+1] = temp;
  121.                     swap(arr, j);
  122.                 }
  123.             }
  124.         }
  126.         System.out.println("BubbleSort从大到小：" + Arrays.toString(arr));
  127.     }
  129.     /**
  130.      * 对象的排序
  131.      */
  132.     public void testObjectSort() {
  133.         Person[] people = new Person[5];
  134.         people[0] = new Person(160, 1000);
  135.         people[1] = new Person(180, 1000);
  136.         people[2] = new Person(170, 500);
  137.         people[3] = new Person(180, 500);
  138.         people[4] = new Person(170, 1500);
  140.         for (int i = people.length - 1; i >= 1; i--) {
  141.             for (int j = 0; j <= i - 1; j++) {
  142.                 if (people[j].compare(people[j+1]) < 0) {
  143.                     Person temp = people[j];
  144.                     people[j] = people[j+1];
  145.                     people[j+1] = temp;
  146.                 }
  147.             }
  148.         }
  150.         System.out.println(Arrays.toString(people));
  151.         for (int i = 0; i < people.length; i++) {
  152.             System.out.println(people[i]);
  153.         }
  154.     }
  156.     /**
  157.      * 交换位置
  158.      * @param arr
  159.      * @param j
  160.      */
  161.     private static void swap(int[] arr, int j) {
  162.         int temp = arr[j];
  163.         arr[j] = arr[j+1];
  164.         arr[j+1] = temp;
  165.     }
  167.     class Person {
  168.         private int height;
  169.         private double money;
  171.         Person(int height, double money) {
  172.             this.height = height;
  173.             this.money = money;
  174.         }
  176.         /**
  177.          * 自定义比较方法
  178.          * @param person
  179.          * @return  大于返回正数，小于返回负数，等于返回0
  180.          */
  181.         public int compare(Person person) {
  182.             return height > person.height ? 1
  183.                     : height < person.height ? -1
  184.                     : money > person.money ? 1
  185.                     : money < person.money ? -1
  186.                     : 0;
  187.         }
  189.         @Override
  190.         public String toString() {
  191.             return "Person{" +
  192.                     "height=" + height +
  193.                     ", money=" + money +
  194.                     '}';
  195.         }
  196.     }
  197. }
  1. /**
  2.  * 数组练习：数三减一
  3.  */
  4. public class ArrayTestCount3Quit {
  5.     public static void main(String[] args) {
  6.         testCount3Quit();
  7.         testCount3QuitObjectOriented();
  8.     }
  10.     /**
  11.      * 数三减一：普通方法
  12.      */
  13.     public static void testCount3Quit() {
  14.         // 初始化数组
  15.         boolean[] bn = new boolean[100];
  16.         for (int i = 0; i < bn.length; i++) {
  17.             bn[i]  = true;
  18.         }
  20.         int leftNum = bn.length; // 剩下的个数，剩下最后一个后停止
  21.         int index = 0;           // 下标标记，数完一圈后重新从0开始
  22.         int countNum = 0;        // 从0开始数，数到3后重新归零
  24.         while (leftNum > 1) {
  25.             if (bn[index] == true) {
  26.                 countNum++;
  27.                 if (countNum == 3) {
  28.                     bn[index] = false;
  29.                     countNum = 0;
  30.                     leftNum--;
  31.                 }
  32.             }
  34.             index++;
  36.             if (index == bn.length)
  37.                 index = 0;
  38.         }
  40.         for (int i = 0; i < bn.length; i++) {
  41.             if (bn[i] == true)
  42.                 System.out.println(i);
  43.         }
  44.     }
  46.     /**
  47.      * 数三减一：采用面向对象思想
  48.      */
  49.     public static void testCount3QuitObjectOriented() {
  50.         KidCircle kidCircle = new KidCircle(100);
  52. //        System.out.println(kidCircle.count);
  53. //        for (int i = 0; i < kidCircle.count; i++) {
  54. //            System.out.println(kidCircle.kids[i]);
  55. //        }
  57.         int countNum = 0;              // 从0开始数，数到3后重新归零
  58.         Kid currentKid = kidCircle.first;
  60.         while (kidCircle.count > 1) {
  61.             countNum++;
  62.             if (countNum == 3) {
  63.                 kidCircle.delete(currentKid);
  64.                 countNum = 0;
  65.             }
  66.             currentKid = currentKid.right;
  67.         }
  69.         System.out.println(kidCircle.first);
  70.         System.out.println(kidCircle.last);
  71.     }
  72. }
  74. /**
  75.  * 定义小朋友类
  76.  */
  77. class Kid {
  78.     int id;
  79.     Kid left;
  80.     Kid right;
  82.     Kid(int id) {
  83.         this.id = id;
  84.     }
  86.     @Override
  87.     public String toString() {
  88.         return "Kid{" +
  89.                 "id=" + id +
  90.                 " left_id=" + left.id +
  91.                 " right_id=" + right.id +
  92.                 '}';
  93.     }
  94. }
  96. /**
  97.  * 定义Kid圆圈类
  98.  */
  99. class KidCircle {
  100.     int count = 0; // 当前Kid圈总数
  101.     Kid first; // 第一个小朋友
  102.     Kid last;  // 最后一个小朋友
  103.     Kid[] kids;
  105.     /**
  106.      * 构造函数：构建小朋友手拉手圆圈
  107.      * @param total
  108.      */
  109.     KidCircle(int total) {
  110.         kids = new Kid[total];
  111.         for (int i = 0; i < total; i++) {
  112.             Kid kid = add(i);
  113.             kids[i] = kid;
  114.         }
  115.     }
  117.     /**
  118.      * 添加小朋友方法
  119.      * @param index
  120.      * @return
  121.      */
  122.     public Kid add(int index) {
  123.         index++;
  124.         Kid kid = new Kid(index);
  126.         if (index <= 0) {
  127.             return null;
  128.         } else if (index == 1) {
  129.             first = kid;
  130.             last = kid;
  131.             kid.left = kid;
  132.             kid.right = kid;
  133.         } else {
  134.             kid.left = last;
  135.             kid.right = first;
  136.             last.right = kid;
  137.             first.left = kid;
  138.             last = kid;
  139.         }
  141.         count++;
  142.         return kid;
  143.     }
  145.     /**
  146.      * 删除小朋友
  147.      * @param kid
  148.      */
  149.     public void delete(Kid kid) {
  150.         if (count <= 0) {
  151.             return;
  152.         } else if (count == 1) {
  153.             first = last = null;
  154.         } else {
  155.             kid.left.right = kid.right;
  156.             kid.right.left = kid.left;
  158.             if (kid == first) {
  159.                 first = kid.right;
  160.             }
  161.             if (kid == last) {
  162.                 last = kid.left;
  163.             }
  164.         }
  165.         count--;
  166.     }
  168.     @Override
  169.     public String toString() {
  170.         return "KidCircle{" +
  171.                 "count=" + count +
  172.                 ", first=" + first +
  173.                 ", last=" + last +
  174.                 '}';
  175.     }
  176. }