数组和自定义队列

  一、数组

     1、数组的定义 （数组的局限性）

          数组是java中最基本的一种数据结构，用于存放一系列类型相同的数据，这些类型相同的数据的集合就是数组。
          数组可以当成一个容器，用来存放自己想放的东西。
          数组的长度在创建时就已经固定了，一旦创建，长度便不能更改。

 

     2、数组的分类

          数组可以分为：一维数组、二维数组、多维数组

 

     3、定义数组的格式

         常用的有三种格式：

         第一种是：数据类型  [ ] 数组名  = new 数据类型[数组长度];
         第二种是：数据类型  [ ] 数组名  = {数值,...};
         第三种是：数据类型  [ ] 数组名  = new 数据类型[ ]{数值,...};

         也可以先声明数组，再实例化数组

         数据类型 [ ]  数组名 ；

         数组名  =   new 数据类型[数组长度];
                    =  {数值,...};
                    =  new 数据类型[ ]{数值,...};

         二维数组的定义与一维的基本类似：

         第一种是：数据类型  [ ][ ]  数组名  = new 数据类型[数组长度][数组长度] ;
         第二种是：数据类型  [ ][ ]  数组名  = {{数值},{数值},{数值},...};
         第三种是：数据类型  [ ][ ]  数组名  = new 数据类型[ ][ ]{{数值},{数值},{数值},...};
         也可以先声明数组，再实例化数组

         数据类型 [ ][ ]  数组名 ；

         数组名  =   new 数据类型[数组长度][数组长度] ;
                    =  {{数值},{数值},{数值},...};
                    =  new 数据类型[ ][ ]{{数值},{数值},{数值},...};

     4、使用数组的基本用法及应注意的问题

          数组长度是固定的；

          数组时有序的；

          数组中每一个元素都有唯一的索引位置，索引值从0开始，最大值为数组长度-1，

          如：

             int[] array = {3,4,6};

             array[0] = 3;

             array[1] = 3;

             array[2] = 3;

             如果运行array[3]；则会出现数组越界的错误；

          取得数组的长度，可以通过  数组名.length得到  数组array的长度为：array.length

          取得数组元素值，一般通过  数组名[索引值] 得到 array[1]

 

     5、数组的排序

          一维数组的排序：

          冒泡排序：

             把数组想象成一个垂直的柱体，其中按最小的元素在顶部，最大的元素在底部排序，就是冒泡排序。

             冒泡排序从顶部或底部开始扫描，对相邻的两个元素进行比较，i的取值是0~array.length-2,

             如果array[i]>array[i+1]，则交换两个数的值，把小的数浮到顶部，大的数沉到底部；

             冒泡排序的算法很简单，但是进行了很多重复的比较，造成时间效率比较低，冒泡排序的时间效率

             为O(n*n)

             具体实现如下：

 

      

// 冒泡排序 public static int[] maoPao(int[] x) { for (int i = 0; i < x.length; i++) { for (int j = i + 1; j < x.length; j++) { if (x[i] > x[j]) { int temp = x[i]; x[i] = x[j]; x[j] = temp; } } } return x; }

 

             选择排序

             选择排序就是在位置上对数组中的元素进行交换，使它们从原来不合适的位置移到按照一定位置排好的

             位置上。即先找出数组中最小的元素，再与第一个元素进行交换，再把剩余的i-1个元素中最小的放到第二个位置

             上， 直到排序完成。

 

// 选择排序 public static int[] xuanZe(int[] x) { for (int i = 0; i < x.length; i++) { int lowerIndex = i; // 找出最小的一个索引 for (int j = i + 1; j < x.length; j++) { if (x[j] < x[lowerIndex]) { lowerIndex = j; } } // 交换 int temp = x[i]; x[i] = x[lowerIndex]; x[lowerIndex] = temp; } return x; }

 

 

          插入排序

             插入排序是先考虑数组中的前两个元素x[0],x[1]，如果后一个数x[1]小于前一个数x[0]就交换两个数的位置，然

             后再考虑第三个元素x[2]，如果x[2]比前两个都小，则把x[2]移到x[0]，前两个依次后移;如过x[2]小于x[1]大

             于x[0]，则只交换x[1]和x[2]；如果x[2]比前两个都大则不需要交换。就这样把每个元素都插入到合适的置上

 

 

// 插入排序 public static int[] caRu(int[] x) { for (int i = 1; i < x.length; i++) { for (int j = i; j > 0; j--) { if (x[j] < x[j - 1]) { int temp = x[j]; x[j] = x[j - 1]; x[j - 1] = temp; } } } return x; }

 

 

 

 

          希尔排序

             希尔排序是先对原始数组的各部分进行排序，待整个数组“基本有序”时，再对整个数组进行排序，这样就提高

             了排序的效率。

 

// 希尔排序 public static int[] shell(int[] x) { // 分组 for (int increment = x.length / 2; increment > 0; increment /= 2) { // 每个组内排序 for (int i = increment; i < x.length; i++) { int temp = x[i]; int j = 0; for (j = i; j >= increment; j -= increment) { if (temp < x[j - increment]) { x[j] = x[j - increment]; } else { break; } } x[j] = temp; } } return x; }

 

 

 

 

 

 

             此外还有堆排序、快速排序、归并排序、基数排序等，今天暂不做总结。

          二维数组的排序：

             冒泡排序：

                我以两种方法实现了二维数组的冒泡排序，一种是先对行或列进行排序，再对二维数组排序；另一种是先把

                二维数组转化为一维数组进行排序，再把一维数组转换成二维数组。

 

 

// 对数组中的元素从小到大排序：采用冒泡排序法 public static int[][] maoPao(int[][] a){ for(int k=0;k<a.length*a[0].length;k++){ for(int i=0;i<a.length;i++){ for(int j=0;j<a[i].length;j++){ //为每一行进行排序 if((j+1)%a[i].length != 0){ if(a[i][j]>a[i][j+1]){ int temp=a[i][j]; a[i][j]=a[i][j+1]; a[i][j+1]=temp; } } else { //为每一列进行排序 if(i+1 != a.length){ if(a[i][j] > a[i+1][(j+1)%a[i].length]){ int temp = a[i][j]; a[i][j] = a[i+1][(j+1)%a[i].length]; a[i+1][(j+1)%a[i].length]=temp; } } } } } } //或者： //把二维数组转换为一维数组再排序 int[] a2 = new int[qty]; for(i=0;i<rows;i++) { for(j=0;j<cols;j++) { a2[i*cols+j] = a1[i][j]; } } for(i=0;i<qty-1;i++) { for(j=i+1;j<qty;j++) { if(a2[i]>a2[j]) { temp = a2[i]; a2[i] = a2[j]; a2[j] = temp; } } } //把排序后的一维数组又转换回二维数组 for(i=0;i<rows;i++) { for(j=0;j<cols;j++) { a1[i][j] = a2[i*cols+j]; } }

 

二、自定义队列

      1、小谈自定义队列

           由于之前看过一点点儿数据结构的书，知道有一个队列，与堆栈的“先进后出”不同，队列是“先进先出的”，队

        列删元素只能在队头，添加元素只能在队尾，队列可以用数组，也可以用链表。但现在学的这个自定义队列可以有

           比较多的功能，可以在任意位置添加或删除一个元素，原来，此“队列”非彼“队列”啊！

 

      2、自定义队列与数组相比的好处（为什么要用自定义队列）

           已经创建好的数组不能再添加一个元素；

           数组也不可以删除一个元素，将后面的元素向前移一位；

           数组也不能将一个数组追加到另一个数组末尾；

           但这些功能都可以通过自定义队列列来实现

       3、自定义队列的实现

             1：向队尾添加数据
             2：在队尾删除数据
             3：在指定位置添加数据
             4：在指定位置删除数据
             5：返回指定位置的数据
             6：返回队列中数据的个数

             7：修改指定位置的元素值

             8：将一个队列追加到另一个队列后面

             下面是我写的简单实现：

 

//1、向队尾添加数据 public void add(Student stu){ //新建一个比原数组长度大一的数组 Student[] tempList = new Student[stuList.length + 1]; //把原数组数据一次复制到新数组中 for(int i=0;i<stuList.length;i++){ tempList[i] = stuList[i]; } //把数据放入最后一个位置 tempList[stuList.length] = stu; //交换两个数组 stuList = tempList; } //2、在队尾删除数据 public void remove(){ //新建一个比原数组长度小一的数组 Student[] tempList = new Student[stuList.length - 1]; //把原数组数据一次复制到新数组中 for(int i=0;i<stuList.length - 1;i++){ tempList[i] = stuList[i]; } //交换两个数组 stuList = tempList; } //3、在指定位置添加数据 public void insert(int index, Student stu){ //新建一个比原数组长度大一的数组 Student[] tempList = new Student[stuList.length + 1]; //把原数组数据index之前的数据复制到新数组中 for(int i=0;i<index;i++){ tempList[i] = stuList[i]; } //把新插入的放入index位置 tempList[index-1] = stu; //把剩下的元素向后错一位放入新数组中 for(int i=index;i<stuList.length+1;i++){ tempList[i]=stuList[i-1]; } //交换两个数组 stuList = tempList; } //4、在指定位置删除数据 public Student delete(int index){ //新建一个比原数组长度小一的数组 Student[] tempList = new Student[stuList.length - 1]; //把原数组数据index之前的数据复制到新数组中 for(int i=0;i<index;i++){ tempList[i] = stuList[i]; } //把剩下的元素向后前一位放入新数组中 for(int i=index;i<stuList.length-1;i++){ tempList[i]=stuList[i+1]; } //交换两个数组 stuList = tempList; return null; } //5、返回指定位置的数据 public Student get(int index){ return stuList[index]; } //6、返回队列中数据的个数 public int size(){ return stuList.length; } //7、修改指定位置的元素值 public void update(int index,Student stu){ //新建一个与原数组长度相同的数组 Student[] tempList = new Student[stuList.length]; //把原数组数据index之前的数据复制到新数组中 for(int i=0;i<index;i++){ tempList[i] = stuList[i]; } //把修改后的的放入index位置 tempList[index] = stu; //把剩下的元素放入新数组中 for(int i=index+1;i<stuList.length;i++){ tempList[i]=stuList[i]; } //交换两个数组 stuList = tempList; } //8、将一个队列追加到另一个队列后面 public void addList(ZDList zdlist){ //新建一个数组，长度为原数组长度加上追加的数组长度 Student[] tempList = new Student[stuList.length +zdlist.size() ]; //把原数组数据一次复制到新数组中 for(int i=0;i<stuList.length;i++){ tempList[i] = stuList[i]; } //把数组追加 for(int i=stuList.length;i<tempList.length;i++){ tempList[i]=zdlist.get(i-stuList.length); } //tempList[stuList.length] = stu; //交换两个数组 stuList = tempList; }

 

        4、使用泛型定义一个通用的自定义队列

           泛型，就是在创建队列时，指定队列中所放对象的类型。在定义泛型时，我们用到了E 和Object:

           其中泛型E 表示可以匹配所有的类型(基本数据类型除外)
           Object 是java所有类的父类

           泛型与队列区别不大，以上面的在队尾添加数据为例来说明泛型：

//向队尾添加数据 public void add(E stu){ //新建一个比原数组长度大一的数组 Object[] tempList = new Object[stuList.length + 1]; //把原数组数据一次复制到新数组中 for(int i=0;i<stuList.length;i++){ tempList[i] = stuList[i]; } //把数据放入最后一个位置 tempList[stuList.length] = stu; //交换两个数组 stuList = tempList; }

 

 

      5.队列的优化

         队列的优化就是将泛型定义成一个类，方便以后的使用