首页  思维导图  详情

数据结构&算法

2021-03-30 10:18:48   0  举报





AI智能生成

常见的数据结构与常见的排序算法，每个都有文字描述和代码。内容都是根据我自己的学习和了解进行编写的。

数据结构与算法

作者其他创作

大纲/内容

算法

基本概念

算法就是为了解决某一个特定问题而规定的一系列的操作，是一组有序的指令的集合

数据结构与算法就是一对好兄弟

算法的五个特性

输入

一个算法有0个或多个输入

输出

至少有一个输出，没有输出的算法没有意义

有穷性

算法中执行指令的个数应该是有限的，执行有穷的步骤后能结束

确定性

对于特定的合法输入它的输出应该是唯一的

可行性

算法能够实现，并且在有限的时间内完成

算法的设计要求

正确性

没有语法错误，对于合法的输入能够产生满足要求的输出，对于特定的输入也能够产生正确的输出

可读性

算法另一个目的是为了交流，方便阅读

健壮性

对于不合理的要求，能够给出合理的提示信息，而不是崩溃

时间效率高与存储空间小

算法的评价

评价一个算法性能的优劣，实际上就是评价算法的资源占用率 计算机最重要的资源就是时间和空间

使用时间复杂度衡量程序运行需要的时间

使用空间复杂度衡量程序所占内存的大小

时间复杂度

程序中语句执行的次数

计算机程序运行时间的方法

事后统计

编程实现这个算法，统计所需要的时间

事前分析

采用渐近时间复杂度分析估算

渐近时间复杂度

简称时间复杂度。在进行算法分析时，语句总的执行次数，记作T(n)， 是关于问题规模n的函数，分析T(n)随着问题规模n的变化情况，确定T(n)的数量级

T(n) = O(f(n))，表示锁着问题规模n的增大，算法执行的时间增长率和f(n)函数的增长率相同， f(n)是问题规模n的一个函数

随着输入规模n的增大，T(n)增长越慢的算法越好

时间复杂度计算的一些原则

忽略常数项

计算次数为：2n + 1 时间复杂度为：O(n)

忽略低次项

计算次数为：n^2 + n 时间复杂度为：O(n^2)

可以忽略的原因

随着问题规模的增大，常数项和低次项对于结果的影响非常小， 所以常数项和低次项都可以忽略

时间复杂度分析

算法1

计算1+2+3+...+n的累加和，高斯算法

public static void sum2(int n){        int sum = n * (n + 1) / 2;        System.out.println("高斯sum = " + sum); }

总共执行了1次

顺序执行，时间复杂度：T(n) = O(1)，是常数阶

算法2

计算1+2+3+...+n的累加和

public static void sum1(int n){        int sum = 0;        for (int i = 1; i <= n; i++) {               sum += i;        }        System.out.println("for循环sum = " + sum); }

总共执行了 n + 1 次，1是常数对结果的影响不大，所以可以省略

时间复杂度：T(n) = O(n)，是线性阶

算法3

public static void method1(int n){        int i = 1;        int count = 0;        while (i <= n){               i = i * 2;               count++;        }        System.out.println("count==" + count); }

解得x如上，其中： 常数2对结果影响不大可以忽略，底数2也可以忽略

时间复杂度：T(n) = O(logn)

算法4

public static void method2(int n){        int count = 0;        int s = 0;        while (s <= n){               count++;               s = s + count;        }        System.out.println("count==" + count); }

假设循环执行了x次,count变量在循环过程中的值分别是：0,1,2,3,...x

在执行完第x次后循环结束,s<=n不成立时，s的值是： s = 0 + 1 + 2 + 3 + ... + x = x * (x + 1) / 2 = (x^2 + x)/2

时间复杂度：T(n) = O(n^2)

算法5

public static void method3(int n){        int count = 0;        for (int i = 1; i <= n; i++) {               for (int j = 1; j <= n; j++) {                      count++;               }        }        System.out.println("count=" + count); }

总共执行了n*n次

时间复杂度：T(n) = O(n^2)

数组的平均数

时间复杂度为：O(n)

常见时间复杂度的增长率

图解

空间复杂度

为了求解某一问题，在执行操作期间所需要的存储空间大小， 不包含用来存储输入所需要的空间

空间复杂度就是算法需要用到的额外空间

记作：S(n) = O(f(n))

结论：算法的空间复杂度是以时间复杂度为上限的

常见排序列表图

引自马士兵老师

排序算法宋词记忆法(引用自马士兵老师)

选泡插， 快归堆希统计基， 恩方恩老恩一三， 对恩加 K恩乘 K， 不稳稳稳不稳稳， 不稳不稳稳稳稳！

解析：        恩方：对应选、泡、插的平均时间复杂度        恩老恩：对应快、归、堆的平均时间复杂度        一三：对应希尔排序的平均时间复杂度        对恩加K：对应桶排序和计数排序的平均时间复杂度        恩乘K：对应基数排序的平均时间复杂度

算法的稳定性

两个相等的数字在数组排完顺序之后，它们的相对顺序可能会变化

写算法的原则

由简单到复杂

验证一步走一步

多打印中间结果

先局部后整体

没思路时先细分

先粗糙后精细

变量更名

语句合并

边界处理

如果很难下手，就把每个小模块都封装成方法，慢慢来

算法的验证

package pers.chenjiahao.algorithm.check; import pers.chenjiahao.algorithm.selection.MyselfSelectionSort; import java.util.Arrays; import java.util.Random; public class DataChecker { static int[] generateRandomArray(){ Random r = new Random(); int[] arr = new int[1000]; for (int i = 0; i < arr.length; i++) { arr[i] = r.nextInt(1000); } return arr; } static void check(){ int[] arr = generateRandomArray(); int[] arr2 = new int[arr.length]; System.arraycopy(arr,0,arr2,0,arr.length); Arrays.sort(arr); MyselfSelectionSort.selectionSort(arr2); boolean same = true; for (int i = 0; i < arr2.length; i++) { if (arr[i] != arr2[i]){ same = false; } } System.out.println(same == true ? "right" : "wrong"); } public static void main(String[] args) { check(); } }

常见算法汇总

1.高斯算法

计算1+2+3+...+n的累加和

算法思想：        sum = 1 + 2 + 3 + 4 + 5 + ... + 100        sum = 100 + 99 + 98 + 97 + 96 + ... + 1  每一项对应相加也就是二倍的sum        2倍的sum = 101 + 101 + 101 + 101 + ... + 101 一共有100个101        2 * sum = 100 * 101 解得：        sum = 100 * 101 / 2 即：        sum = n * (n + 1) / 2

2.选择排序

在一个数组中，从第一个位置开始在数组中寻找最小的数字， 找到最小的数字之后和第一个位置上的数字进行交换， 换完之后第一个位置就是最小的数字了，然后第一个位置不参与排序了， 再从第二个位置开始在数组中寻找最小的数字， 找到后和第二个位置上的数字交换，以此类推。。。。。。

怎么找最小的数：        每次将开始位置设置为最小数，        如果这个最小数大于下一个位置上的数字，将下一个位置上的数设置为最小数        如果比下一个位置上的数字小，那么最小数还是它本身        全部比较完之后，将最小数的位置和开始位置进行交换，这样就、完成了一次排序

代码

package pers.chenjiahao.algorithm.selection; /** * 自己写的选择排序 */ public class MyselfSelectionSort { public static void main(String[] args) { // 创建一个排序的数组 int[] arr = {8,5,5,2,64,38,65,4}; arr = selectionSort(arr); // 打印最终排序的结果 print(arr); } private static int[] selectionSort(int[] arr) { // arr.length - 1中 -1是因为最后一次就是本身不用比较了，小小的优化 for (int i = 0; i < arr.length - 1; i++) { // 定义一个变量存放最小值的下标，并将参与排序的第一个数的下标设为最小值的下标 int minIndex = i; for (int j = i + 1; j < arr.length; j++) { // 后面的数字比min还小就进行交换 if (arr[minIndex] > arr[j]){ // 修改最小值对应的下标 minIndex = j; } } // 判断一下有没有必要进行交换 if (i != minIndex){ // 进行开始位置和最小数位置的交换 swap(arr,i,minIndex); } // 打印每一次排序的结果 System.out.print("经过第" + i + "次排序之后，数组的内容" + ":"); print(arr); } return arr; } private static void print(int[] arr){ for (int k : arr) { System.out.print(k + " "); } System.out.println(); } private static void swap(int[] arr,int i,int minIndex){ int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } }

代码优化(每次找到最小值和最大值，对头和尾都进行交换)

package pers.chenjiahao.algorithm.selection.optimization; /** * 对选择排序进行优化 * 每次找到最小值和最大值 * 最小值放前面，最大值放后面 */ public class SelectionOptimization { public static void main(String[] args) { int[] arr = {5,3,6,10,8,1,7,9,4,2}; selectionOptimization(arr); } public static void selectionOptimization(int[] arr) { for (int i = 0; i < arr.length / 2; i++) { int minIndex = i; int maxIndex = arr.length - i - 1; for (int j = i + 1; j < arr.length - i; j++) { if (arr[minIndex] > arr[j]){ minIndex = j; continue; } if (arr[maxIndex] < arr[j]){ maxIndex = j; } } // 交换最小值 int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; // 交换最大值 temp = arr[maxIndex]; arr[maxIndex] = arr[arr.length - i - 1]; arr[arr.length - i - 1] = temp; System.out.println("第" + (i + 1) + "次排序"); System.out.println("更换的最小值坐标为:" + minIndex); System.out.println("更换的最大值坐标为:" + maxIndex); print(arr); System.out.println(); } } private static void print(int[] arr){ for (int i : arr) { System.out.print(i + " "); } } }

3.冒泡排序

整体思想：将数组中最大的数字像泡泡一样浮到最后一个位置上去，以此类推完成排序

每次都从第一个数字开始，两两比较，寻找最大的数字 如果前面的数字比后面的数字大，就交换位置， 如果前面的数字比后面的数字小，就不用交换位置， 继续下一组的比较。 比较原则：        0 1            1 2              2 3                 3 4                     ......

例：对9 6 1 3 5 进行冒泡排序

代码

package pers.chenjiahao.algorithm.bubble; public class MySelfBubbleSort { public static void main(String[] args) { int[] arr = {5,3,6,8,10,1,7,9,4,2}; // int[] arr = {9,1,2,3,4,5,6,7,8}; bubbleSort(arr); print(arr); } private static void bubbleSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { findMax(arr,i); } } private static void findMax(int[] arr, int i) { for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]){ swap(arr,j); } } } private static void swap(int[] arr, int j) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j+1] = temp; } private static void print(int[] arr){ for (int i : arr) { System.out.println(i + " "); } } }

代码优化(如果一次交换都没发生的话，证明数组已经排序完成了，这样就是最好的情况O(n)了)

package pers.chenjiahao.algorithm.bubble.optimization; public class BubbleSortOptimization { public static void main(String[] args) { int[] arr = {9,1,2,3,4,5,6,7,8}; bubbleSort(arr); print(arr); } private static void bubbleSort(int[] arr){ a:for (int i = arr.length - 1; i > 0 ; i--){ if (findMax(arr,i)){ break a; } } } private static boolean findMax(int[] arr,int n){ boolean flag = true; for (int j = 0; j < n; j++) { if (arr[j] > arr[j + 1]) { swap(arr,j); flag = false; } } return flag; } private static void swap(int[] arr,int j){ int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } private static void print(int[] arr){ for (int i = 0; i < arr.length; i++) { System.out.println(arr[i] + " "); } } }

4.插入排序

主要思想是需要比出来小的，如果前面的比后面的大，就换位置

从第二个位置上的数开始比较，每次都只会跟"前面"的数字进行比较， 如果比前面的数字小就进行交换，以此类推，直到找到合适的位置才结束这个数的排序 例如：        9 6 1 3 5        从第二个位置上的数字6开始向前比较，6比9小所以6和9交换位置，第一次排序结束，得到        6 9 1 3 5        从第三个位置上的数字1开始向前比较，1小于9所以1和9交换位置，得到        6 1 9 3 5        1再跟前面的6进行比较，1小于6所以1和6交换位置，第二次排序结束，得到        1 6 9 3 5         ......直到排完最后一个

对9 6 1 3 5进行排序

代码

package pers.chenjiahao.algorithm.insertion; public class MySelfInsertionSort { public static void main(String[] args) { int[] arr = {1,9,2,7,5,8,3,6,4}; insertionSort(arr); print(arr); } static void insertionSort(int[] arr){ // int i = 1; for (int i = 1; i < arr.length; i++) { findMin(arr,i); } } static void findMin(int[] arr, int i) { for (int j = i; j > 0; j--) { if (arr[j] < arr[j - 1]){ swap(arr,j); } } } static void swap(int[] arr,int j){ int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } static void print(int[] arr){ for (int i : arr) { System.out.println(i + " "); } } }

修改算法(用临时变量记录标记项，去掉swap方法)

将当前开始排序的数字存入到一个临时变量中， 最后直接插入到需要插入的位置，提前将后面的所有数字都后移

代码

package pers.chenjiahao.algorithm.insertion.optimization; public class InsertionSortUpdate { public static void main(String[] args) { int[] arr = {1,9,2,7,5,8,3,6,4}; insertionSort(arr); print(arr); } static void insertionSort(int[] arr){ // int i = 1; for (int i = 1; i < arr.length; i++) { int temp = arr[i]; findMin(arr,i,temp); } } static void findMin(int[] arr, int i,int temp) { for (int j = i; j > 0; j--) { if (temp < arr[j - 1]){ arr[j] = arr[j - 1]; }else { arr[j] = temp; break; } } } static void print(int[] arr){ for (int i : arr) { System.out.print(i + " "); } } }

5.希尔排序

改进的插入排序，比插入排序的效率高一些

相对插入排序来说，多了一个间隔的概念，先确定一个间隔，每这个间隔的数字成一组， 每一组进行相对位置上的排序（例如：这一组的下标是1 4 7 10 ，这组数排完序之后，下标还是1 4 7 10）， 然后向后推移，找下一组所有组都排完了之后，开始减小间隔，直至间隔为1排完一遍之后，完成了排序。 例如：         (9 6 3) (5 7 1) (4 2 8)         以3为间隔分成三组         9 5 4 、6 7 2 、3 1 8，三组分别排完序之后：         4 5 9 、2 6 7 、1 3 8，重新组成的数组为         (4 2 1)( 5 6 3)( 9 7 8)，即以间隔为3的排序完成，下来可以进行间隔为2的排序，然后按照间隔为1排序（插入排序）         排序完成

图解

间隔为4的排序，下图接

间隔为2和1的排序

间隔大的时候移动的次数少 间隔小的时候移动的距离短

间隔的选择

1.最常见的，arr.length / 2

2.Knuth序列，比/2效率高

希尔排序中通常用gap或h表示间隔 h = 1 h = 3*h + 1 h = 1 , 4 , 13 , ........

寻找最大间隔采用      int h = 1;      while (h <= arr.length / 3){           h = h * 3 + 1;      } 除以3的原因是，如果大于1/3的话，3*h+1就大于数组的长度了

代码

package pers.chenjiahao.algorithm.shell; public class ShellSort { public static void main(String[] args) { int[] arr = {9,6,11,3,5,12,8,7,10,15,14,4,1,13,2}; sort(arr); print(arr); } static void sort(int[] arr){ int h = 1; while (h <= arr.length / 3){ h = h * 3 + 1; } for (int gap = h; gap > 0; gap = (gap - 1) / 3) { for (int i = gap; i < arr.length; i++) { for (int j = i; j > gap - 1; j -= gap) { if (arr[j] < arr[j - gap]){ swap(arr,j,j - gap); } } } } } static void swap(int[] arr,int i,int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } static void print(int[] arr){ for (int i : arr) { System.out.print(i + " "); } } }

6.归并排序

主要的思想就是递归

如果数组没有排好顺序 首先对数组进行一分为二，如果想对这两半进行归并，必须要求子数组必须排好 如果想让子数组排好，必须对子数组分成两半进行归并，............. 直到不能分为止（子数组中有两个或者一个），然后开始从最小的子数组开始逐步归并

第一种情况（前半截和后半截都是有顺序的）

三个指针，新建一个新的数组，                      比较情况：                                    1和2，1比2小将1放入到新数组中                                    4和2，2比4小将2放入到新数组中                                     4和3，3比4小将3放入到新数组中                                    4和5，4比5小将4放入到新数组中                                    6和5，5比6小将5放入到新数组中                                    ................

代码

package pers.chenjiahao.algorithm.merge; public class MergeSort { public static void main(String[] args) { int[] arr = {1,4,7,8,3,6,9}; sort(arr); // print(arr); } static void sort(int[] arr){ merge(arr); } static void merge(int[] arr){ int mid = arr.length >> 1; int[] temp = new int[arr.length]; int i = 0; int j = mid + 1; int k = 0; while (i <= mid && j < arr.length){ // temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++]; if (arr[i] <= arr[j]){ temp[k++] = arr[i++]; // i++; // k++; }else { temp[k++] = arr[j++]; // j++; // k++; } } while (i<=mid){ temp[k++] = arr[i++]; } while (j<arr.length){ temp[k++] = arr[j++]; } print(temp); } static void swap(int[] arr,int i,int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } static void print(int[] arr){ for (int i : arr) { System.out.print(i + " "); } } }

第二种情况（使用到递归）

给merge方法添加三个参数左起点，右起点，右边界 目的是为了给子数组进行排序

例：对1,11,10,4,6,2,7,5,3,8,9进行归并

图解

图解中仅对第一次分组后的前一半进行的画图解释

代码

package pers.chenjiahao.algorithm.merge.update; /** * 前半截和后半截不一定是有顺序的，要使用到递归 */ public class MySelfMergeSortUpdate { public static void main(String[] args) { int[] arr = {1,4,6,7,10,11,2,3,5,8,9}; // int[] arr = {1,4,7,8,3,6,9}; // int[] arr = {1,11,10,4,6,2,7,5,3,8,9}; sort(arr,0,arr.length - 1); print(arr); } static void sort(int[] arr,int left,int right){ if (left == right) return; // int mid = left + (right - left) / 2; int mid = (right + left) / 2; // 给左边排序 sort(arr,left,mid); // 给右边排序 sort(arr,mid + 1,right); // 左右两边归并 merge(arr,left,mid + 1,right); } static void merge(int[] arr,int leftStart,int rightStart,int rightBound) { int mid = rightStart - 1; int[] temp = new int[rightBound - leftStart + 1]; int i = leftStart; int j = rightStart; int k = 0; while (i <= mid && j <= rightBound){ if (arr[i] <= arr[j]){ temp[k++] = arr[i++]; }else { temp[k++] = arr[j++]; } } while (i <= mid) temp[k++] = arr[i++]; while (j <= rightBound) temp[k++] = arr[j++]; for (int l = 0; l < temp.length; l++) { arr[leftStart + l] = temp[l]; } } static void print(int[] arr){ for (int i : arr) { System.out.print(i + " "); } } }

TimSort(改进的归并排序)

7.快速排序

在数组中先随便找一个数字，作为轴，比轴矮的排到前面，比轴高的排到后面， 此时，数组就被分成了两部分，在前半部分和后半部分，分别再找轴，再排。 重复以上的操作，直到分割完之后剩下一个元素的时候，开始返回(递归的结束条件)。

核心思想：依照每个轴排完之后，轴的位置就是这数字的位置，不用变了，                  再找下一个轴，以此类推

例如：对1，4，6，9，10，2，3，5，8，7排序

部分图解

第一种(以每个数组的最后一个位置为轴)

描述

选定每个数组中最后的数字作为轴， 数组从前往后开始遍历， 如果比轴小，就不动， 如果大于轴承，就和轴前面的数字进行交换，        用换回来的数字再跟轴比，如果比轴小，就不动，                                                如果大于轴，继续跟轴前面没有交换过的数字进行交换 以此类推

结束条件

定义一个索引值 == arr.length - 2，这个值代表的是倒数第二个数字的下标， 如果“排序的索引值”+ 1 == 这个索引值时，将最后位置的数和这个索引值上的数进行交换， 即这次的排序完成

例如：对1 6 9 10 2 5 8 7进行排序

一次比较的过程

完整的数组分割过程(1,6,10,8,2,5,9,7)

代码

package pers.chenjiahao.algorithm.quick; /** * 选定每个数组种最后的数字作为轴， * 数组从前往后开始遍历， * 如果比轴小，就不动， * 如果大于轴承，就和轴前面的数字进行交换， * 用换回来的数字再跟轴比，如果比轴小，就不动， * 如果大于轴，继续跟轴前面没有交换过的数字进行交换 * 以此类推 */ public class SimpleQuickSort { public static void main(String[] args) { // int[] arr ={1,6,2,9,10,11,5,8,7}; // int[] arr ={1,6,9,10,11,5,8,7}; // int[] arr ={1,6,9,10,2,5,8,7}; int[] arr ={1,6,10,8,2,5,9,7}; sort(arr,0,arr.length - 1); print(arr); } static void sort(int[] arr,int start,int end){ if (start == end + 1) return; // 排序 int retAxis = quick(arr,start,end); if (retAxis == -1) return; sort(arr,start,retAxis - 1); sort(arr,retAxis + 1,end); } static int quick(int[] arr,int startIndex,int axisIndex) { if (startIndex == axisIndex) return -1; // 数组的轴 int axis = arr[axisIndex]; // 轴的前一个位置的索引 int axisBeforeIndex = axisIndex - 1; while (startIndex != axisBeforeIndex){ if (arr[startIndex] > axis){ swap(arr,startIndex,axisBeforeIndex); // axisBeforeIndex前移一位 axisBeforeIndex--; // 重新校验这个数字 startIndex--; } startIndex++; } // 交换轴和axisBeforeIndex位置的数 axisBeforeIndex = arr[startIndex] > axis ? axisBeforeIndex : axisBeforeIndex + 1; swap(arr,axisIndex,axisBeforeIndex); // 返回现在轴的位置 return axisBeforeIndex; } /** * 将轴的位置交换到合适的位置 * @param arr 传入的数组 * @param axisIndex 轴的位置 * @param axisBeforeIndex 轴在数组中合适的位置 */ private static void swap(int[] arr, int axisIndex, int axisBeforeIndex) { int temp = arr[axisIndex]; arr[axisIndex] = arr[axisBeforeIndex]; arr[axisBeforeIndex] = temp; } static void print(int[] arr){ for (int i : arr) { System.out.print(i + " "); } System.out.println(); } }

第二种(两边同时找，找到之后直接做交换)

还是以数组的最后为轴，从左往右找第一个比轴大的数， 从右往左找第一个比轴小的数，让这两个数字直接做交换

一次的比较过程

以7为轴的第一次交换

完整的过程图解

代码

package pers.chenjiahao.algorithm.quick; /** * 两边同时找 * 还是以数组的最后为轴， * 从左往右找第一个比轴大的数， * 从右往左找第一个比轴小的数， * 让这两个数字直接做交换 */ public class MySelfQuickSort { public static void main(String[] args) { int[] arr = {9,3,2,8,1,6,5,4,7}; sort(arr,0,arr.length - 1); print(arr); } static void sort(int[] arr,int start,int end){ if (start == end + 1) return; int retAxisIndex = quick(arr,start,end); if (retAxisIndex == -1){ return; } sort(arr,start,retAxisIndex - 1); sort(arr,retAxisIndex + 1,end); } static int quick(int[] arr,int startIndex,int axisIndex) { if (startIndex == axisIndex){ return -1; } // 轴 int axis = arr[axisIndex]; // 从左往右找的索引 int leftStartIndex = startIndex; // 从右往左找的索引 int rightStartIndex = axisIndex - 1; // 存储第一个比轴大的数,将第一个值赋给它 int moreThanAxis; // 存储第一个比轴小的数 int lessThanAxis; while (true){ moreThanAxis = arr[leftStartIndex]; lessThanAxis = arr[rightStartIndex]; // 先从左往右找第一个比轴大的数 for (int i = leftStartIndex; i < axisIndex; i++) { if (arr[i] > axis){ moreThanAxis = arr[i]; break; } leftStartIndex++; } if (moreThanAxis < axis){ // 比轴大的数没找到，直接完成排序 return leftStartIndex; } // 从右往左找第一个比轴小的数 for (int j = rightStartIndex; j > leftStartIndex ; j--) { if (arr[j] < axis){ lessThanAxis = arr[j]; break; } rightStartIndex--; } if (lessThanAxis > axis){ // 比轴大的数字找到了，比轴小的数字没找到，轴和比轴大的数字直接交换 swap(arr,leftStartIndex,axisIndex); return leftStartIndex; } // 能走到这里说明，从左边找了一个大的，从右边找了一个小的，进行交换 swap(arr,leftStartIndex,rightStartIndex); // print(arr); } } static void swap(int[] arr, int axisIndex, int axisBeforeIndex) { int temp = arr[axisIndex]; arr[axisIndex] = arr[axisBeforeIndex]; arr[axisBeforeIndex] = temp; } static void print(int[] arr){ for (int i : arr) { System.out.print(i + " "); } System.out.println(); } }

精致代码

package pers.chenjiahao.algorithm.quick; public class QuickSort { public static void main(String[] args) { int[] arr = {7,3,2,6,8,1,9,5,4,10}; sort(arr,0,arr.length - 1); print(arr); } private static void sort(int[] arr, int leftBound, int rightBound) { if (leftBound >= rightBound) return; int retPivotIndex = partition(arr,leftBound,rightBound); sort(arr,leftBound,retPivotIndex - 1); sort(arr,retPivotIndex + 1,rightBound); } static int partition(int[] arr, int leftBound, int rightBound) { // 轴 int pivot = arr[rightBound]; int left = leftBound; int right = rightBound - 1; while (left <= right){ // 从左往右找第一个大于轴的位置 while (left <= right && arr[left] <= pivot) left++; // 从右往左找第一个小于轴的位置 while (left <= right && arr[right] > pivot) right--; if (left < right) swap(arr,left,right); } swap(arr,left,rightBound); return left; } static void swap(int[] arr,int i,int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } static void print(int[] arr){ for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }

第三种(Java内部使用的双轴快排)

思想，每次找两个轴，将数组分成三个区域， ******大前提：第一个轴比第二个小****** 第一个区域存放小于第一个轴的数， 第二个区域存放大于第一个轴小于第二个轴的区域， 第三个区域存放大于第二个轴的数

找轴

算出数组长度的1/7（记做A） 找到数组的终点，减去A，找到第一个数 再减去A，找到第二个数 再减去A，找到第三个数 再减去A，找到第四个数 再减去A，找到第五个数 将这五个数排好顺序（从小到大） *****如果这五个数有一个相等，就用单轴快排 *****如果这五个数都不相等，就选第二个和第四个数作为两个轴，使用双轴快排

图解（这里选定数组的第一个和最后一个数为轴）

代码

package pers.chenjiahao.algorithm.quick; public class DualPivotQuickSort { public static void main(String[] args) { // int[] arr = {9,3,2,6,8,1,7}; int[] arr = {6,3,2,7,4,5,9,8}; sort(arr,0,arr.length - 1); print(arr); } static void sort(int[] arr,int start,int end){ if(start >= end) return; int[] retPivot = dualQuick(arr,start,end); if (retPivot[0] == -1) return; // 左递归： sort(arr,start,retPivot[0] - 1); // 中递归： sort(arr,retPivot[0] + 1,retPivot[1] - 1); // 右递归： sort(arr,retPivot[1] + 1,end); } private static int[] dualQuick(int[] arr, int start, int end) { int[] retPivot = {-1,-1}; if (start == end) return retPivot; if (start + 1 == end){ if (arr[start] > arr[end]){ swap(arr,start,end); } return retPivot; } // k是每次判断的数字 int k = start + 1; // 左侧的点 int left = start; // 右侧的点 int right = end; // 最左侧的轴 int leftPivot = arr[left]; // 最右侧的轴 int rightPivot = arr[right]; // 要保证左侧的轴小于右侧的轴 if (leftPivot > rightPivot){ swap(arr,left,right); leftPivot = arr[left]; rightPivot = arr[right]; } while (k < right){ // 小于第一个轴，不动,left++,k++ if (arr[k] < leftPivot){ if (k - 1 != left){ swap(arr,k,left + 1); } left++; k++; continue; } // 大于第一个，小于第二个，不动 if (arr[k] > leftPivot && arr[k] < rightPivot){ k++; continue; } // 能走到这里说明，这个数大于第一个轴和第二个轴，right-- // 交换位置k上和right - 1上的数字 right--; swap(arr,k,right); } // 交换左侧的轴和left指针 swap(arr,start,left); // 交换右侧的轴和right指针 swap(arr,end,right); // 将两个轴返回 retPivot[0] = left; retPivot[1] = right; return retPivot; } static void swap(int[] arr,int i,int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } static void print(int[] arr){ for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }

8.计数排序

计数排序是桶排序思想中特殊的一种情况

非比较排序

适用场景：量大但是范围小        例如：企业中万名员工年龄排序                  快速得知高考名次

创建一个新的数组用来计数（全部初始化为0）， 这个数组的长度就是上述场景中范围的长度， 数组中对应的索引就是在范围中对应的数字

开始遍历数据：依次取得范围中的数字，当作数组的索引，给对应数组下标上的数加1

创建一个新的数组，和原来的数组一样长。将计数数组按照顺序存入

说白了就是记录了每个数出现了多少次

举例：公司中每个员工的职务（这个例子没啥意义，就是这种思想）

职务分为三个级别：A、B、C

张三   A 李四   B 王五   C 赵六   B 陈七   A

创建计数数组：数组的长度为3(因为范围为A、B、C) int[] arr = {0,0,0};

开始遍历数据        ①先读取到A，A对应的是计数数组的0位置（也就是0位置上的数组加1）            int[] arr = {1,0,0};        ②再读取到B            int[] arr = {1,1,0};        ③读取到C            int[] arr = {1,1,1};        ④读取到B            int[] arr = {1,2,1};        ⑤读取到A            int[] arr = {2,2,1};

最终：计数数组就是 int[] arr = {2,2,1};

创建新的数组，和原来的数组一样长 int[] newArr = new int[原员工数组的长度]

将计数数组中的数据按照一定的顺序存入 newArr = {A,A,B,B,C}; 解释：计数数组中第一个位置出现了两个A                            第二个位置出现了两个B                            第三个位置初夏了一个C

代码(存在问题，不稳定，而且如果从100~150开始就浪费了(因为索引都是从0开始的))

package pers.chenjiahao.algorithm.counting; import java.util.Arrays; /** * 不稳定， * 如果从100~150开始就浪费了(因为索引都是从0开始的) */ public class CountSort { public static void main(String[] args) { int[] arr = {2,4,2,3,7,1,1,0,0,5,6,9,8,5,7,4,0,9}; int[] result = sort(arr); System.out.println(Arrays.toString(result)); } static int[] sort(int[] arr){ int[] result = new int[arr.length]; int[] count = new int[10]; for (int i = 0; i < arr.length; i++) { count[arr[i]]++; } System.out.println(Arrays.toString(count)); for (int i = 0,j = 0; i < count.length; i++) { while (count[i]-- > 0) result[j++] = i; } return result; } }

解决浪费

找出范围的最小值，数组中全部减去最小值，最后给新数组中每个数再加上最小值

代码

package pers.chenjiahao.algorithm.counting; /** * 解决问题 * 如果从100~150开始就浪费了(因为索引都是从0开始的) */ public class MySelfCountSortUpdate { public static void main(String[] args) { int[] arr = {105,105,104,101,101,100,100,103,100,102,100,104}; int min = findMin(arr); sort(arr,min); } private static int findMin(int[] arr) { int min = arr[0]; for (int i = 1; i < arr.length; i++) { if (min > arr[i]) min = arr[i]; } return min; } static void sort(int[] arr,int min){ countSort(arr,min); } private static void countSort(int[] arr,int min) { // 创建一个计数数组,因为数的范围是100~105 所以计数数组的长度为6 int[] countArr = new int[6]; // 将arr中的数字全部减去做小的数 for (int i = 0; i < arr.length; i++) { arr[i] -= min; } // 开始遍历数据 for (int i = 0; i < arr.length; i++) { countArr[arr[i]]++; } // 创建一个与原来数组等长的数组，用来存储计数后的结果 int[] newArr = new int[arr.length]; // 将计数数组存储到新数组中 int k = 0; int j = 0; while (k < newArr.length){ for (int i = 0; i < countArr[j]; i++) { newArr[k++] = j + min; } j++; } for (int i : newArr) { System.out.print(i + " "); } } }

解决不稳定

采用累加数组

代码

package pers.chenjiahao.algorithm.counting; import java.util.Arrays; /** * 不稳定， * 如果从100~150开始就浪费了(因为索引都是从0开始的) */ public class CountSort { public static void main(String[] args) { int[] arr = {2,4,2,3,7,1,1,0,0,5,6,9,8,5,7,4,0,9}; System.out.println(Arrays.toString(arr)); int[] result = sort(arr); System.out.println(Arrays.toString(result)); } static int[] sort(int[] arr){ int[] result = new int[arr.length]; int[] count = new int[10]; for (int i = 0; i < arr.length; i++) { count[arr[i]]++; } System.out.println(Arrays.toString(count)); // for (int i = 0,j = 0; i < count.length; i++) { // while (count[i]-- > 0) result[j++] = i; // } // 对count数组进行累加 for (int i = 1; i < count.length; i++) { count[i] = count[i] + count[i - 1]; } System.out.println(Arrays.toString(count)); for (int i = arr.length - 1;i >= 0; i--) { result[--count[arr[i]]] = arr[i]; } return result; } }

9.基数排序

筒思想的一种

非比较排序

多关键字排序

排数字的时候，最大的数字有几位，就排几次

例如：对一组数进行排序

421 240 115 532 305 430 124

将每个数字的个、十、百位都可以当作是一种关键字

第一次：以个位上的数进行排序    得到：240 430 421 532 124 115 305

第二次：在第一次排序完的基础上，以十位上的数排序     得到：305 115 421 124 430 532 240

第三次：在第二次排序完的基础上，以百位上的数排序     得到：115 124 240 305 421 430 532

如果再有千位万位，以此类推

代码实现

package pers.chenjiahao.algorithm.radix; import java.util.Arrays; public class RadixSort { public static void main(String[] args) { int[] arr = {421,240,115,532,305,430,124}; int maxDigits = findMaxDigits(arr); int[] retArr = radixSort(arr,maxDigits); System.out.println("最终结果：" + Arrays.toString(retArr)); } private static int[] radixSort(int[] arr,int maxDigits) { int[] result = new int[arr.length]; int[] count = new int[10]; for (int i = 0; i < maxDigits; i++) { int division = (int) Math.pow(10,i); for (int j = 0; j < arr.length; j++) { int num = arr[j] / division % 10; count[num]++; } System.out.println(); System.out.println(Arrays.toString(count)); for (int m = 1; m < count.length; m++) { count[m] = count[m] + count[m - 1]; } System.out.println(Arrays.toString(count)); for (int n = arr.length - 1; n >= 0; n--) { int num = arr[n] /division % 10; result[--count[num]] = arr[n]; } // 将result中的值复制到arr中， System.arraycopy(result,0,arr,0,arr.length); // 初始化count数组全部为0 Arrays.fill(count,0); System.out.println("第"+ (i+1) +"次的结果为:" + Arrays.toString(result)); } return result; } private static int findMaxDigits(int[] arr) { int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (max < arr[i]) max = arr[i]; } return String.valueOf(max).length(); } }

实际中的例子：员工排序，先排年龄，再排工龄、再排身高体重.....

10.桶排序

给小数排序

也可以给小数同时乘以100，全部变成整数，先进行计算，最后再统一除以100输出

先用桶排序，分好，再用归并排序将每个桶中进行排序

例：采用桶+插实现的例子

package pers.chenjiahao.algorithm.bucket; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class BucketSort { public static void main(String[] args) { // 对12个小数进行排序 double[] arr = {0.0,0.12,0.18,0.93,0.45,0.76,0.89,0.03,0.55,0.98,0.67,1.0}; bucketSort(arr); } private static void bucketSort(double[] arr) { double[] retArr = new double[arr.length]; // 分为四个桶 [0.0,0.25) [0.25,0.5) [0.5,0.75) [0.75,1.0] List<Double> bucketList1 = new ArrayList<>(); List<Double> bucketList2 = new ArrayList<>(); List<Double> bucketList3 = new ArrayList<>(); List<Double> bucketList4 = new ArrayList<>(); List[] bucketArr = {bucketList1,bucketList2,bucketList3,bucketList4}; // 开始遍历源数组 for (int i = 0; i < arr.length; i++) { if (0.0 <= arr[i] && arr[i] < 0.25) bucketList1.add(arr[i]); if (0.25 <= arr[i] && arr[i] < 0.5) bucketList2.add(arr[i]); if (0.5 <= arr[i] && arr[i] < 0.75) bucketList3.add(arr[i]); if (0.75 <= arr[i] && arr[i] <= 1.0) bucketList4.add(arr[i]); } // 开始对每个bucketList进行排序 for (int i = 0; i < bucketArr.length; i++) { sort(bucketArr[i]); } System.out.println(Arrays.toString(bucketArr)); } private static void sort(List list) { for (int i = 1; i < list.size(); i++) { for (int j = i; j > 0 ; j--) { if ((double)list.get(j) < (double)list.get(j - 1)){ double temp = (double) list.get(j); list.set(j,list.get(j - 1)); list.set(j - 1,temp); } } } } }

11.堆排序

基本思想 （1）将待排序序列构造成一个大顶堆 （2）此时，整个序列的最大值就是堆顶的根节点 （3）将其与末尾元素进行交换，此时末尾就为最大值 （4）然后将剩余n - 1个元素重新构造成一个堆，这样会得到n个元素的次小值。          如此反复执行，便能得到一个有序序列了  在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到了一个有序序列了

具体实施方法： 1.将无需序列构建成一个堆，根据升序降序需求，选择大顶堆或者小顶堆 这里采用升序的思路 2.自左向右，自上而下，先找到最后一个非叶子结点。比较它的两个子结点，    再拿子结点中大的数组和这个非叶子结点进行比较，如果非叶子结点小，就换。    继续找下一个倒数的非叶子结点，以此类推，知道所有的非叶子结点都找完 3.将堆顶元素与末尾元素交换，将最大元素(堆顶的元素)与末尾元素进行交换。    这个数不再参与下一次的运算（排出了一个数） 3.以此类推，反复执行，直到没有非叶子结点，递归结束

例：对4 6 8 5 9进行排序

初始化数组

第一次排序完成后，9就不参与运算了。以此类推

详细图解

图解

代码

package pers.chenjiahao.algorithm.heap; import java.util.Arrays; public class HeapSort { public static void main(String[] args) { // 将数组进行升序排序 int[] arr = {4,6,8,5,9}; heapSort(arr); } // 堆排序的方法 static void heapSort(int[] arr){ int temp = 0; System.out.println("堆排序"); // 分布完成 // adjustHeap(arr,1,arr.length); // System.out.println("第一次" + Arrays.toString(arr)); // 4 9 8 5 6 // // adjustHeap(arr,0,arr.length); // System.out.println("第二次" + Arrays.toString(arr)); // 9 6 8 5 4 // arr.length / 2 - 1 得到最后一个非叶子结点 for (int i = arr.length / 2 - 1; i >= 0; i--) { adjustHeap(arr,i,arr.length); System.out.println(Arrays.toString(arr)); } // 5个数最大调四次 for (int j = arr.length - 1; j > 0; j--) { // 交换大顶堆的堆顶和最后一个数 temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; adjustHeap(arr,0,j); System.out.println(Arrays.toString(arr)); // 9 6 8 5 4 } System.out.println("last:" + Arrays.toString(arr)); // 9 6 8 5 4 } /** * 将一个数组（二叉树），调整成一个大顶堆 * 功能：将i所对应的非叶子结点作为根的树，调整成大顶堆 * 距离 int[] arr = {4,6,8,5,9}; -> i = 1 -> adjustHeap -> 得到{4,9,8,5,6} * @param arr 待调整的数组 * @param i 表示非叶子结点在数组中的索引 * @param length 表示对多少个元素进行调整，length是在逐渐减少的 */ static void adjustHeap(int[] arr,int i,int length){ // 先取出当前元素的值，保存在一个临时变量 int temp = arr[i]; // 开始调整 // int k = i * 2 + 1 k是i结点的左子结点 for (int k = i * 2 + 1; k < length; k = k * 2 + 1) { // 左子的值小于右子的值 if (k + 1 < length && arr[k] < arr[k+1]){ // k指向右子结点 k++; } if (arr[k] > temp){ arr[i] = arr[k]; // 把较大的值给到当前的非叶子结点 i = k; // !!! i指向k，继续循环比较 }else { break; } } // 将原来非叶子结点上的值放在i位置， // 如果arr[k] > temp i就相当于是k了下面那句话的意思就是arr[k] = temp; // 如果arr[k] <= temp i还是i，自己覆盖自己，等于没有变化 arr[i] = temp; } }

算法总结

冒泡：基本不用，太慢

选择：基本不用，不稳

插入：样本小且基本有序的时候效率比较高

数据结构

1.基本概念

数据

描述客观事物的数值、字符，能输入到计算机并且被计算机处理的各种符号的集合

数据就是信息在计算机中的表示

数据元素

数据元素就是数据的基本单位

在计算机程序中，通常把数据元素作为一个整体进行处理

例如： 描述学生信息的一条数据记录就是一个数据元素 描述一个点坐标的信息就是一个数据元素 数据元素通常由若干个数据项组成

例如： 描述学生信息中的姓名、学号、成绩都是数据项 点坐标中的横坐标、纵坐标就是数据项

数据对象

一组相同性质的数据元素的集合

例如： 学校中所有学生的集合就是数据对象 平面坐标系中所有的点的集合就是数据项

数据结构

相互之间存在的一种或多种特定关系的数据元素的集合

数据结构就是数据元素之间的关系

数据结构分为逻辑结构和物理结构

数据的逻辑结构有四种

集合：数据仅仅属于同一个集合，他们之间没有其他的相互关系

线性：描述一对一的关系

树形：描述一对多的关系

图形：描述多对多的关系

数据的逻辑结构一般采用二元组的形式定义

数据结构=(D,S)

D：数据元素的集合

S：D中元素之间的关系的集合

例1：集合

二元组：set = (D,S) D = {01,02,03,04,05,06} S  = {}

在set集合中，数据元素除了属于同一个集合外，不存在其他的关系，这就是集合的结构

图解

例2：线形

二元组：linearity = (D,S) D = {01,02,03,04,05,06} S = {<01,04>,<04,06>,<06,02>,<02,05>,<05,03>}

在数据结构linearity中，数据元素是有序的，有一个被称为“第一个”的数据元素（01） 还有一个被称为“最后一个”的元素（03），除了第一个元素外，其他每个元素都有一个直接前驱元素 除了最后一个元素外，其他每个元素都有一个直接后继的元素

数据元素之间是一对一的关系

图解

例3：树形

二元组：tree = (D,S) D = {01,02,03,04,05,06} S = {<01,02>,<01,03>,<02,04>,<02,05>,<03,06>}

在tree数据结构中，除了第一个元素（01）外，每个元素都有且只有一个直接前驱元素，每个元素可以有多个直接后继元素

数据元素之间是一对多的关系

图解

例4：图形

二元组：graph = (D,S) D = {01,02,03,04,05,06} S = {<01,02>,<01,03>,<02,05>,<05,06>,<06,02>,<05,04>,<04,05>}

在graph数据结构中，每个元素可以有多个直接前驱元素，每个元素也可以有多个直接后继元素

数据元素之间是多对多的关系

图解

数据的物理结构

数据的物理结构就是逻辑结构在计算机中的存储表示

两种存储表示形式

顺序存储

链式存储

顺序存储

顺序存储就是使用一块连续的存储空间，数据之间紧挨在一起 数据的前驱和后继的关系可以通过数据元素在内存中相对位置反映出来

图解

链式存储

数据元素的存储位置不是连续的，每个元素中都会保存下一个元素的存储位置

图解

2.抽象数据类型

abstract data type 简称：ADT

由一组数据模型及该模型上的一组操作组成

抽象数据类型一半使用一个三元组表示： ADT =（D，S，P） D：数据对象 S：D上的关系 P：D上的操作

在定义抽象数据类型时，可以使用以下的格式： ADT 抽象数据类型名{      数据对象：<数据对象的定义>      数据关系：<数据关系的定义>      数据操作：<基本操作的定义> }

抽象数据类型可以对应一个Java类，数据对象与数据关系可以通过类的成员变量来存储和表示，数据操作可以使用方法来实现

3.线性表

基本概念

linearity = (D,R) D = {a1,a2,a3,a4} R = {<a1,a2>,<a2,a3>,<a3,a4>} a1元素称为第一个元素，其他的元素都有一个直接前驱; a4元素称为最后一个元素，其他的元素都有一个直接后继

生活中的线性结构：排队

线性表的抽象数据类型

ADT List{        数据对象：D = {ai 属于某个数据类型，i = 0,1,2,3...}                         D = {a0,a1,a2,a3,a4 ... an},所有的元素都是同一个数据类型        数据关系：R = {<ai,a(i+1)>}        数据操作：                         getSize()：返回线性表中元素的个数                         isEmpty()：判断线性表是否为空，线性表为空返回true，否则返回false                         insert(i,e)：在线性表的i索引值位置插入元素e，如果索引值i越界，则报错                         contains(e)：在线性表中判断是否存在元素e，存在返回true                         indexOf(e)：返回元素e在线性表中的索引值，如果不存在元素e，则返回-1                         remove(e)：删除线性表中第一个与e相同的元素，删除成功返回删除的元素，元素不存在返回null                         remove(i)：删除线性表中指定索引值位置的元素，返回删除的元素，如果索引值i越界，则报错                         replace(i,e)：把线性表中索引值为i的元素替换为元素e，如果索引值i越界，则报错                         get(i)：返回线性表中索引值为i的元素，如果索引值i越界，则报错                         insertBefore(p,e)：在线性表中元素p的前面插入元素e                         insertAfter(p,e)：在线性表中元素p的后面插入元素e }

注：凡是涉及到索引的方法，都要先判断索引是否越界

一般来说抽象数据类型都会抽象成一个接口

MyList接口

使用Java中的接口来表示ADT中的数据操作，在使用类完成抽象数据类型时， 只要这个类实现接口即可完成抽象数据类型中定义的操作

package pers.chenjiahao.linearity.operator; /** * 通过接口定义一组线性表中的操作 */ public interface MyList {        int getSize(); // 返回线性表中的元素的个数        boolean isEmpty(); // 判断线性表是否为空        void insert(int i, Object e); // 在线性表的i索引值添加元素e        boolean contains(Object e); // 判断线性表中是否包含元素e        int indexOf(Object e); // 返回线性表中元素e的索引值        Object remove(Object e); // 删除线性表中第一个与e相同的元素，并返回该元素        Object remove(int i); // 删除线性表中索引值为i的元素，并返回该元素        Object replace(int i, Object e); // 使用元素e替换线性表中i位置的元素，并返回旧的元素        Object get(int i); // 返回索引值为i的元素        boolean insertBefore(Object p, Object e); // 在线性表元素p的前面插入元素e        boolean insertAfter(Object p, Object e); // 在线性表元素p的后面插入元素e }

线性表的顺序存储

基本概念

线性表的顺序存储就是使用一组地址连续的存储空间来依次存储线性表中的元素 以数据元素在计算机内存的地址相邻性来表示数据元素之间的关系 在Java中可以使用数组来存储线性表中的数据元素，数组就是一块连续的存储空间

原理

插入元素

图解

删除元素

图解

代码实现

创建一个MyArrayList类，实现MyList接口

完整代码

package pers.chenjiahao.linearity.queuestorageimpl; import pers.chenjiahao.linearity.operator.MyList; /** * 实现MyList接口 */ public class MyArrayList implements MyList { // 定义数组来保存数据元素 private Object[] elements; // 数组的默认初始化容量 private static final int DEFAULT_CAPACITY = 16; // 保存数据元素的个数 private int size; // 在创建的时候默认会给数组赋予一个初始化容量 public MyArrayList() { elements = new Object[DEFAULT_CAPACITY]; } // 自定义初始化容量 public MyArrayList(int initialCapacity) { elements = new Object[initialCapacity]; } // 返回元素的个数 @Override public int getSize() { return size; } // 判断线性表是否为空 @Override public boolean isEmpty() { return size == 0; } // 在线表的i位置插入元素e @Override public void insert(int i, Object e) { // 判断索引值i是否越界 if (i < 0 || i > size){ throw new IndexOutOfBoundsException(i + "越界"); } // 如果数组已满，对数组进行扩容 if (size >= elements.length){ // 数组扩容 expandSpace(); } // 从i开始，把元素依次后移 for (int j = size; j > i; j--) { elements[j] = elements[j-1]; } // 把元素e存储到i位置 elements[i] = e; // 元素的个数增加1 size++; } /** * 数组扩容 */ private void expandSpace() { // 定义一个更大的数组,默认按2倍大小扩容 Object[] newElements = new Object[elements.length * 2]; // 把原来数组的内容复制到新的数组中 for (int i = 0; i < elements.length; i++) { newElements[i] = elements[i]; } // 让原来的数组名指向新的数组 elements = newElements; } // 判断当前线性表中是否包含元素e @Override public boolean contains(Object e) { return indexOf(e) >= 0; } // 返回元素e在线性表中第一次出现位置的索引值，如果不存在返回-1 @Override public int indexOf(Object e) { // 判断e是否为空 if (e == null){ // 如果线性表中，用户可能添加了null for (int i = 0; i < size; i++) { if (elements[i] == null){ return i; } } }else { // 遍历数组 for (int i = 0; i < size; i++) { if (e.equals(elements[i])){ return i; } } } // 能走到这里说明元素不存在 return -1; } // 在线性表中删除第一个与e相同的元素 @Override public Object remove(Object e) { // 获取e在线性表中的索引值 int index = indexOf(e); if (index < 0){ // 线性表中不存在元素e return null; } return remove(index); } // 在线性表中删除指定索引值的元素 @Override public Object remove(int i) { // 判断i是否越界 if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + "越界"); } // 把要删除的元素保存起来 Object old = elements[i]; // 把i+1开始的元素，依次前移 for (int j = i; j < size - 1; j++) { elements[j] = elements[j + 1]; } // 把最后的元素放置为null elements[size - 1] = null; // 修改元素的个数 size--; return old; } // 把索引值为i的元素替换为e @Override public Object replace(int i, Object e) { // 判断是否越界 if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + "越界"); } // 保存原来的值 Object old = elements[i]; // 替换 elements[i] = e; // 把原来的元素值返回 return old; } // 返回指定位置的元素 @Override public Object get(int i) { // 判断是否越界 if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + "越界"); } return elements[i]; } // 在指定的元素前插入元素 @Override public boolean insertBefore(Object p, Object e) { // 先确定元素p在线性表中的位置 int index = indexOf(p); if (index < 0){ // p元素不存在，插入不成功 return false; } // 插入元素 insert(index,e); return true; } // 在指定的元素后插入元素 @Override public boolean insertAfter(Object p, Object e) { // 先确定元素p在线性表中的位置 int index = indexOf(p); if (index < 0){ // p元素不存在，插入不成功 return false; } // 插入元素 insert(index + 1,e); return true; } // 重写toString方法 @Override public String toString() { // 把线性表中每个元素连接起来，便利数组中已添加的元素 StringBuilder sb = new StringBuilder(); sb.append("["); for (int i = 0; i < size; i++) { sb.append(elements[i]); if (i < size - 1){ sb.append(","); } } sb.append("]"); return sb.toString(); } }

各个功能模块代码

1.getSize()

// 返回元素的个数 @Override public int getSize() { return size; }

2.isEmpty()

// 判断线性表是否为空 @Override public boolean isEmpty() { return size == 0; }

3.insert(int i, Object e)

// 在线表的i位置插入元素e @Override public void insert(int i, Object e) { // 判断索引值i是否越界 if (i < 0 || i > size){ throw new IndexOutOfBoundsException(i + "越界"); } // 如果数组已满，对数组进行扩容 if (size >= elements.length){ // 数组扩容 expandSpace(); } // 从i开始，把元素依次后移 for (int j = size; j > i; j--) { elements[j] = elements[j-1]; } // 把元素e存储到i位置 elements[i] = e; // 元素的个数增加1 size++; }

4.contains(Object e)

// 判断当前线性表中是否包含元素e @Override public boolean contains(Object e) { return indexOf(e) >= 0; }

5.indexOf(Object e)

// 返回元素e在线性表中第一次出现位置的索引值，如果不存在返回-1 @Override public int indexOf(Object e) { // 判断e是否为空 if (e == null){ // 如果线性表中，用户可能添加了null for (int i = 0; i < size; i++) { if (elements[i] == null){ return i; } } }else { // 遍历数组 for (int i = 0; i < size; i++) { if (e.equals(elements[i])){ return i; } } } // 能走到这里说明元素不存在 return -1; }

6.remove(Object e)

// 在线性表中删除第一个与e相同的元素 @Override public Object remove(Object e) { // 获取e在线性表中的索引值 int index = indexOf(e); if (index < 0){ // 线性表中不存在元素e return null; } return remove(index); }

7.remove(int i)

// 在线性表中删除指定索引值的元素 @Override public Object remove(int i) { // 判断i是否越界 if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + "越界"); } // 把要删除的元素保存起来 Object old = elements[i]; // 把i+1开始的元素，依次前移 for (int j = i; j < size - 1; j++) { elements[j] = elements[j + 1]; } // 把最后的元素放置为null elements[size - 1] = null; // 修改元素的个数 size--; return old; }

8.replace(int i, Object e)

// 把索引值为i的元素替换为e @Override public Object replace(int i, Object e) { // 判断是否越界 if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + "越界"); } // 保存原来的值 Object old = elements[i]; // 替换 elements[i] = e; // 把原来的元素值返回 return old; }

9.get(int i)

// 返回指定位置的元素 @Override public Object get(int i) { // 判断是否越界 if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + "越界"); } return elements[i]; }

10.insertBefore(Object p, Object e)

// 在指定的元素前插入元素 @Override public boolean insertBefore(Object p, Object e) { // 先确定元素p在线性表中的位置 int index = indexOf(p); if (index < 0){ // p元素不存在，插入不成功 return false; } // 插入元素 insert(index,e); return true; }

11.insertAfter(Object p, Object e)

// 在指定的元素后插入元素 @Override public boolean insertAfter(Object p, Object e) { // 先确定元素p在线性表中的位置 int index = indexOf(p); if (index < 0){ // p元素不存在，插入不成功 return false; } // 插入元素 insert(index + 1,e); return true; }

12.toString()

// 重写toString方法 @Override public String toString() { // 把线性表中每个元素连接起来，便利数组中已添加的元素 StringBuilder sb = new StringBuilder(); sb.append("["); for (int i = 0; i < size; i++) { sb.append(elements[i]); if (i < size - 1){ sb.append(","); } } sb.append("]"); return sb.toString(); }

13.private void expandSpace()

// 数组扩容 private void expandSpace() { // 定义一个更大的数组,默认按2倍大小扩容 Object[] newElements = new Object[elements.length * 2]; // 把原来数组的内容复制到新的数组中 for (int i = 0; i < elements.length; i++) { newElements[i] = elements[i]; } // 让原来的数组名指向新的数组 elements = newElements; }

测试类

package pers.chenjiahao.linearity.queuestorageimpl.test; import pers.chenjiahao.linearity.operator.MyList; import pers.chenjiahao.linearity.queuestorageimpl.MyArrayList; /** * 测试MyArrayList */ public class MyArrayListTest { public static void main(String[] args) { // 创建MyArrayList对象 MyList list1 = new MyArrayList(); // 判断是否为空 System.out.println(list1.isEmpty()); // true // 获取长度 System.out.println(list1.getSize()); // 0 // 添加元素 list1.insert(0,"aa"); list1.insert(1,"bb"); list1.insert(0,"cc"); System.out.println(list1.isEmpty()); // false System.out.println(list1.getSize()); // 3 // 把线性表中的内容打印输出 System.out.println(list1); // [cc,aa,bb] // 元素的索引值 System.out.println(list1.indexOf("cc")); // 0 System.out.println(list1.indexOf("bb")); // 2 System.out.println(list1.indexOf("dd")); // -1 // 判断是否存在 System.out.println(list1.contains("aa")); // true System.out.println(list1.contains("xx")); // false // 删除 list1.remove("dd"); // 删除不存在的元素，没有影响 System.out.println(list1); // [cc,aa,bb] list1.remove("bb"); System.out.println(list1); // [cc,aa] list1.remove(0); System.out.println(list1);// [aa] // 重新插入点数据 list1.insert(0,"xx"); list1.insert(0,"oo"); list1.insert(0,"yy"); System.out.println(list1); // [yy,oo,xx,aa] // 替换 list1.replace(0,"YY"); System.out.println(list1); // [YY,oo,xx,aa] // 返回值指定索引的元素 System.out.println(list1.get(0)); // YY System.out.println(list1.get(1)); // oo System.out.println(list1.get(3)); // aa // System.out.println(list1.get(4)); // 4越界 // 在指定元素的前面/后面插入元素 list1.insertBefore("oo","JJ"); System.out.println(list1); // [YY,JJ,oo,xx,aa] list1.insertAfter("oo","jj"); System.out.println(list1); // [YY,JJ,oo,jj,xx,aa] list1.insertAfter("TT","BB"); System.out.println(list1); // [YY,JJ,oo,jj,xx,aa] } }

特点

优点

顺序存储是使用数组实现的，数组可以通过索引值快速访问每个元素

图解

缺点

在插入/删除元素时，需要移动大量的元素

当线性表长度变化较大时，很难确定存储空间的容量

应用场景

适用于元素的插入/删除操作较少，主要是查询操作

线性表的链式存储

单向链表

基本概念

单向链表，也叫单链表

每个存储单元至少有两个域，一个用来存储数据，一个用来保存下个存储单元的引用

图解

原理

插入和删除元素

不需要移动元素

图解

代码实现

创建一个MySingleLink类，实现MyList接口

完整代码

package pers.chenjiahao.linearity.singlelinkimpl; import pers.chenjiahao.linearity.operator.MyList; public class MySingleLink implements MyList { // 表示头节点 private Node head; // 保存元素的个数 private int size; // 返回元素的个数 @Override public int getSize() { return size; } // 判断线性表是否为空 @Override public boolean isEmpty() { return size == 0; } // 在线性表中插入元素 @Override public void insert(int i, Object e) { // 判断索引值是否越界 if (i < 0 || i > size){ throw new IndexOutOfBoundsException(i + "越界"); } // 创建结点 Node newNode = new Node(e,null); // 头节点为null的情况，线性表还没被创建,刚添加的结点就是头结点 if (head == null){ head = newNode; }else { // 在0位置插入结点 if (i == 0){ // 修改新节点的next 域，指向原来的头节点 newNode.next = head; // 刚插入的节点就是新的头节点 head = newNode; }else { // 在其余的位置插入结点,先找到i-1这个结点 Node pNode = head; for (int j = 1; j < i; j++) { pNode = pNode.next; } // 给新结点的next先赋值 i 结点也就是pNode的next newNode.next = pNode.next; // 改变i-1位置结点的next，让pNode的next结点指向newNode pNode.next = newNode; } } // 元素个数+1 size++; } // 判断线性表中是否包含指定的元素 @Override public boolean contains(Object e) { return indexOf(e) >= 0; } // 返回元素e在线性表中第一次出现的索引值 @Override public int indexOf(Object e) { // 保存元素e的索引值 int index = 0; Node pNode = head; while (pNode != null){ if (e == null && pNode.data == null){ return index; }else if (e != null && e.equals(pNode.data)){ return index; } index++; pNode = pNode.next; } return -1; } // 从线性表中删除第一个与e相同的元素 @Override public Object remove(Object e) { // 找到元素e第一次出现的位置 int index = indexOf(e); if (index < 0){ // 元素不存在 return null; } return remove(index); } // 从线性表中删除指定索引的元素 @Override public Object remove(int i) { // 判断是否越界 if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + "越界"); } Node pNode = head; // 删除头结点(i为0时候) if (i == 0){ head = head.next; size--; return pNode.data; // 返回删除头结点的数据 } // 删除的是中间的元素，找到i-1结点 for (int j = 1; j < i; j++) { pNode = pNode.next; } // 保存删除结点的数据 Object old = pNode.next.data; // 将i - 1 结点的next指针与改变一下(让i-1的next指向i+1结点，相当于删除了i) pNode.next = pNode.next.next; size--; return old; } // 把线性表中i索引值位置的元素替换为e @Override public Object replace(int i, Object e) { // 判断是否越界 checkIndex(i); // 找到i结点 Node pNode = getNode(i); // 保存一下旧的数据 Object old = pNode.data; // 替换 pNode.data = e; return old; } // 返回线性表中i索引值的元素 @Override public Object get(int i) { // 判断是否越界 Node pNode = getNode(i); return pNode.data; } // 定义一个方法来检查索引值是否越界 private void checkIndex(int i){ if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + "越界"); } } // 定义一个方法返回i索引值的元素 private Node getNode(int i){ if (i < 0 || i>= size){ return null; } if (i == 0){ return head; } // 找到i结点 Node pNode = head; for (int j = 0; j < i; j++) { pNode = pNode.next; } return pNode; } // 在指定的元素p的前面插入元素e @Override public boolean insertBefore(Object p, Object e) { // 找p的索引位置 int index = indexOf(p); if (index < 0){ // 元素p不存在 return false; } insert(index,e); return true; } @Override public boolean insertAfter(Object p, Object e) { // 找p的索引位置 int index = indexOf(p); if (index < 0){ // 元素p不存在 return false; } insert(index + 1,e); return true; } // 重写toString()方法 @Override public String toString() { // 把链表中各个结点的数据与连接起来 StringBuilder sb = new StringBuilder(); sb.append("["); Node pNode = head; while (pNode != null){ sb.append(pNode.data); // 使用逗号分割 if (pNode.next != null){ sb.append(","); } // 指针向后移动 pNode = pNode.next; } sb.append("]"); return sb.toString(); } // 定义一个内部类表示单向链表中的结点 private class Node{ // 保存数据 Object data; // 保存下一个结点的引用 Node next; // 构造 public Node(Object data, Node next) { this.data = data; this.next = next; } } }

各个功能模块代码

1.getSize()

// 返回元素的个数 @Override public int getSize() { return size; }

2.isEmpty()

// 判断线性表是否为空 @Override public boolean isEmpty() { return size == 0; }

3.insert(int i, Object e)

// 在线性表中插入元素 @Override public void insert(int i, Object e) { // 判断索引值是否越界 if (i < 0 || i > size){ throw new IndexOutOfBoundsException(i + "越界"); } // 创建结点 Node newNode = new Node(e,null); // 头节点为null的情况，线性表还没被创建,刚添加的结点就是头结点 if (head == null){ head = newNode; }else { // 在0位置插入结点 if (i == 0){ // 修改新节点的next 域，指向原来的头节点 newNode.next = head; // 刚插入的节点就是新的头节点 head = newNode; }else { // 在其余的位置插入结点,先找到i-1这个结点 Node pNode = head; for (int j = 1; j < i; j++) { pNode = pNode.next; } // 给新结点的next先赋值 i 结点也就是pNode的next newNode.next = pNode.next; // 改变i-1位置结点的next，让pNode的next结点指向newNode pNode.next = newNode; } } // 元素个数+1 size++; }

4.contains(Object e)

// 判断线性表中是否包含指定的元素 @Override public boolean contains(Object e) { return indexOf(e) >= 0; }

5.indexOf(Object e)

// 返回元素e在线性表中第一次出现的索引值 @Override public int indexOf(Object e) { // 保存元素e的索引值 int index = 0; Node pNode = head; while (pNode != null){ if (e == null && pNode.data == null){ return index; }else if (e != null && e.equals(pNode.data)){ return index; } index++; pNode = pNode.next; } return -1; }

6.remove(Object e)

// 从线性表中删除第一个与e相同的元素 @Override public Object remove(Object e) { // 找到元素e第一次出现的位置 int index = indexOf(e); if (index < 0){ // 元素不存在 return null; } return remove(index); }

7.remove(int i)

// 从线性表中删除指定索引的元素 @Override public Object remove(int i) { // 判断是否越界 if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + "越界"); } Node pNode = head; // 删除头结点(i为0时候) if (i == 0){ head = head.next; size--; return pNode.data; // 返回删除头结点的数据 } // 删除的是中间的元素，找到i-1结点 for (int j = 1; j < i; j++) { pNode = pNode.next; } // 保存删除结点的数据 Object old = pNode.next.data; // 将i - 1 结点的next指针与改变一下(让i-1的next指向i+1结点，相当于删除了i) pNode.next = pNode.next.next; size--; return old; }

8.replace(int i, Object e)

// 把线性表中i索引值位置的元素替换为e @Override public Object replace(int i, Object e) { // 判断是否越界 checkIndex(i); // 找到i结点 Node pNode = getNode(i); // 保存一下旧的数据 Object old = pNode.data; // 替换 pNode.data = e; return old; }

9.get(int i)

// 返回线性表中i索引值的元素 @Override public Object get(int i) { // 判断是否越界 Node pNode = getNode(i); return pNode.data; }

10.insertBefore(Object p, Object e)

// 在指定的元素p的前面插入元素e @Override public boolean insertBefore(Object p, Object e) { // 找p的索引位置 int index = indexOf(p); if (index < 0){ // 元素p不存在 return false; } insert(index,e); return true; }

11.insertAfter(Object p, Object e)

// 在指定的元素p的后面插入元素e @Override public boolean insertAfter(Object p, Object e) { // 找p的索引位置 int index = indexOf(p); if (index < 0){ // 元素p不存在 return false; } insert(index + 1,e); return true; }

12.toString()

// 重写toString()方法 @Override public String toString() { // 把链表中各个结点的数据与连接起来 StringBuilder sb = new StringBuilder(); sb.append("["); Node pNode = head; while (pNode != null){ sb.append(pNode.data); // 使用逗号分割 if (pNode.next != null){ sb.append(","); } // 指针向后移动 pNode = pNode.next; } sb.append("]"); return sb.toString(); }

13.private void checkIndex(int i)

// 定义一个方法来检查索引值是否越界 private void checkIndex(int i){ if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + "越界"); } }

14.private Node getNode(int i)

// 定义一个方法返回i索引值的元素 private Node getNode(int i){ if (i < 0 || i>= size){ return null; } if (i == 0){ return head; } // 找到i结点 Node pNode = head; for (int j = 0; j < i; j++) { pNode = pNode.next; } return pNode; }

*****15.private class Node

// 定义一个内部类表示单向链表中的结点 private class Node{ // 保存数据 Object data; // 保存下一个结点的引用 Node next; // 构造 public Node(Object data, Node next) { this.data = data; this.next = next; } }

测试类

package pers.chenjiahao.linearity.singlelinkimpl.test; import pers.chenjiahao.linearity.singlelinkimpl.MySingleLink; /** * 测试单向链表 */ public class MySingleLinkTest { public static void main(String[] args) { // 创建链表 MySingleLink link = new MySingleLink(); // 判断链表是否为空 System.out.println(link.isEmpty()); // true // 获取元素个数 System.out.println(link.getSize()); // 插入元素 link.insert(0,"aa"); link.insert(0,"bb"); link.insert(0,"cc"); link.insert(0,"dd"); // 直接打印输出 System.out.println(link); // [dd,cc,bb,aa] // 判断元素是否存在 System.out.println(link.indexOf("dd")); // 0 System.out.println(link.indexOf("aa")); // 3 System.out.println(link.indexOf("xx")); // -1 System.out.println(link.contains("cc")); // true // 删除结点 System.out.println(link.remove("xx")); // null System.out.println(link.remove("bb")); // bb System.out.println(link); // [dd,cc,aa] System.out.println(link.remove(0)); System.out.println(link); // [cc,aa] // 返回元素，元素替换 System.out.println(link.get(0)); // cc System.out.println(link.replace(0,"CC")); // cc System.out.println(link); // [CC,aa] // 在指定元素的前面/后面插入元素 link.insertBefore("aa","bb"); link.insertAfter("bb","BB"); System.out.println(link); // [CC,bb,BB,aa] MySingleLink link2 = new MySingleLink(); } }

双向链表

基本概念

双向链表中，扩展了结点的结构，每个结点除了存储数据外，通过一个引用指向后继结点，再定义一个引用指向前驱结点

图解

原理

插入和删除元素

图解

代码实现

创建一个MyDualLinkedList类，实现MyList接口

完整代码

package pers.chenjiahao.linearity.duallinkedlistimpl; import pers.chenjiahao.linearity.operator.MyList; public class MyDualLinkedList implements MyList { // 指向头结点 private Node first; // 指向尾结点 private Node last; // 保存元素的个数 private int size; // 返回元素的个数 @Override public int getSize() { return size; } // 判断链表是否为空 @Override public boolean isEmpty() { return size == 0; } // 在指定的索引值插入元素 @Override public void insert(int i, Object e) { // 判断是否越界 if (i < 0 || i > size){ throw new IndexOutOfBoundsException(i + "越界"); } // 如果i==0，在头部添加元素 if (i == 0){ addFirst(e); }else if (i == size){ // 如果i==size，表示在尾部添加元素 addLast(e); }else{ // 找到i结点，在i结点的前面插入元素 Node pNode = getNode(i); Node prevNode = pNode.prev; // 生成新的结点 Node newNode = new Node(e,prevNode,pNode); // 修改前驱结点的next指向新节点 prevNode.next = newNode; // 修改后继结点的prev指向新节点 pNode.prev = newNode; // 元素加一 size++; } } // 返回索引值对应的结点 private Node getNode(int i) { Node pNode = first; for (int j = 0; j < i; j++) { pNode = pNode.next; } return pNode; } // 判断链表中是否包含指定的元素e，如果存在返回true @Override public boolean contains(Object e) { return indexOf(e) >= 0; } // 判断元素e在链表中第一次出现的位置，如果不存在该元素，返回-1 @Override public int indexOf(Object e) { // 保存元素e在链表中的索引值 int i = 0; // 依次遍历链表中的各个结点，比较结点的元素与指定的e是否一样 if (e == null){ for(Node pNode = first; pNode != null ; pNode = pNode.next){ if (pNode.data == null){ return i; } i++; } }else{ for(Node pNode = first; pNode != null ; pNode = pNode.next){ if (e.equals(pNode.data)){ return i; } i++; } } return -1; } // 从链表中删除指定的元素 @Override public Object remove(Object e) { // 先找到元素e对应的索引值 int index = indexOf(e); if (index < 0){ return null; } return remove(index); } // 从链表中删除指定索引值的元素，并返回删除的元素 @Override public Object remove(int i) { // 判断索引值是否越界 if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + "越界"); } // 找到i对应的结点 Node pNode = getNode(i); // 删除结点的前驱 Node prevNode = pNode.prev; // 删除结点的后继 Node nextNode = pNode.next; // 如果前驱结点为null if (prevNode == null){ // 删除的就是头结点 first = nextNode; }else { // 将prevNode中的next指向nextNode prevNode.next = nextNode; } // 如果后继节点为null if (nextNode == null){ // 删除的就是尾结点 last = prevNode; }else { // 将nextNode中的prev指向prevNode nextNode.prev = prevNode; } // 修改元素的个数 size--; return pNode.data; } // 修改指定索引值的元素，将原来的元素返回 @Override public Object replace(int i, Object e) { // 检查索引值是否越界 checkIndex(i); // 找到索引值为i的结点 Node pNode = getNode(i); // 存储原来的元素 Object oldData = pNode.data; // 修改结点的元素 pNode.data = e; return oldData; } // 返回指定索引值的元素 @Override public Object get(int i) { // 检查索引值是否越界 checkIndex(i); // 找到索引值为i的结点 return getNode(i).data; } // 在指定的元素p前面插入元素e @Override public boolean insertBefore(Object p, Object e) { // 找到p元素在哪 int index = indexOf(p); if (index < 0 ){ return false; } // 在p元素的前面插入元素e insert(index,e); return true; } // 在指定的元素后面插入元素e @Override public boolean insertAfter(Object p, Object e) { // 找到p元素在哪 int index = indexOf(p); if (index < 0 ){ return false; } // 在p元素的前面插入元素e insert(index + 1,e); return true; } // 校验是否越界的方法 private void checkIndex(int i){ if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + "越界"); } } // 在链表中，经常会有针对头元素与尾元素的操作 // 在尾部添加元素e public void addLast(Object e) { Node pNode = last; // 生成一个新的结点 Node newNode = new Node(e,last,null); if (pNode == null){ // 既是为结点，也是头结点 first = newNode; }else { pNode.next = newNode; } last = newNode; size++; } // 在头部添加元素e public void addFirst(Object e) { // 生成一个新的结点 Node newNode = new Node(e,null,first); /* 这种写法，如果first不存在，则会产生，空指针异常 // 将原先头结点的前驱指向这个新的结点 first.prev = newNode; // 将头节点的指针指向这个新的结点 first = newNode;*/ // 修改first指向新的结点 first = newNode; Node pNode = first.next; // 刚刚插入的头结点，既是头节点，也是尾节点 if (pNode == null){ last = newNode; }else { pNode.prev = newNode; } // 元素的个数+1 size++; } // 删除第一个元素，删除头元素 public Object removeFirst(){ return remove(0); } // 删除最后一个元素，删除尾元素 public Object removeLast(){ return remove(size - 1); } // 返回头元素 public Object getFirst(){ return get(0); } // 返回尾元素 public Object getLast(){ return get(size - 1); } // 重写toString @Override public String toString() { // 依次遍历各个节点，把元素转换为字符串 StringBuilder sb = new StringBuilder(); sb.append("["); for (Node node = first; node != null ; node = node.next) { sb.append(node.data); // 元素之间使用逗号分割 if (node != last){ sb.append(","); } } sb.append("]"); return sb.toString(); } // 定义一个内部类描述双向链表的结点 private class Node{ // 保存数据域 private Object data; // 保存前驱结点 private Node prev; // 保存后继结点 private Node next; public Node(Object data, Node prev, Node next) { this.data = data; this.prev = prev; this.next = next; } } }

各个功能模块代码

1.getSize()

// 返回元素的个数 @Override public int getSize() { return size; }

2.isEmpty()

// 判断链表是否为空 @Override public boolean isEmpty() { return size == 0; }

3.insert(int i, Object e)

// 在指定的索引值插入元素 @Override public void insert(int i, Object e) { // 判断是否越界 if (i < 0 || i > size){ throw new IndexOutOfBoundsException(i + "越界"); } // 如果i==0，在头部添加元素 if (i == 0){ addFirst(e); }else if (i == size){ // 如果i==size，表示在尾部添加元素 addLast(e); }else{ // 找到i结点，在i结点的前面插入元素 Node pNode = getNode(i); Node prevNode = pNode.prev; // 生成新的结点 Node newNode = new Node(e,prevNode,pNode); // 修改前驱结点的next指向新节点 prevNode.next = newNode; // 修改后继结点的prev指向新节点 pNode.prev = newNode; // 元素加一 size++; } }

4.contains(Object e)

// 判断链表中是否包含指定的元素e，如果存在返回true @Override public boolean contains(Object e) { return indexOf(e) >= 0; }

5.indexOf(Object e)

// 判断元素e在链表中第一次出现的位置，如果不存在该元素，返回-1 @Override public int indexOf(Object e) { // 保存元素e在链表中的索引值 int i = 0; // 依次遍历链表中的各个结点，比较结点的元素与指定的e是否一样 if (e == null){ for(Node pNode = first; pNode != null ; pNode = pNode.next){ if (pNode.data == null){ return i; } i++; } }else{ for(Node pNode = first; pNode != null ; pNode = pNode.next){ if (e.equals(pNode.data)){ return i; } i++; } } return -1; }

6.remove(Object e)

// 从链表中删除指定的元素 @Override public Object remove(Object e) { // 先找到元素e对应的索引值 int index = indexOf(e); if (index < 0){ return null; } return remove(index); }

7.remove(int i)

// 从链表中删除指定索引值的元素，并返回删除的元素 @Override public Object remove(int i) { // 判断索引值是否越界 if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + "越界"); } // 找到i对应的结点 Node pNode = getNode(i); // 删除结点的前驱 Node prevNode = pNode.prev; // 删除结点的后继 Node nextNode = pNode.next; // 如果前驱结点为null if (prevNode == null){ // 删除的就是头结点 first = nextNode; }else { // 将prevNode中的next指向nextNode prevNode.next = nextNode; } // 如果后继节点为null if (nextNode == null){ // 删除的就是尾结点 last = prevNode; }else { // 将nextNode中的prev指向prevNode nextNode.prev = prevNode; } // 修改元素的个数 size--; return pNode.data; }

8.replace(int i, Object e)

// 修改指定索引值的元素，将原来的元素返回 @Override public Object replace(int i, Object e) { // 检查索引值是否越界 checkIndex(i); // 找到索引值为i的结点 Node pNode = getNode(i); // 存储原来的元素 Object oldData = pNode.data; // 修改结点的元素 pNode.data = e; return oldData; }

9.get(int i)

// 返回指定索引值的元素 @Override public Object get(int i) { // 检查索引值是否越界 checkIndex(i); // 找到索引值为i的结点 return getNode(i).data; }

10.insertBefore(Object p, Object e)

// 在指定的元素p前面插入元素e @Override public boolean insertBefore(Object p, Object e) { // 找到p元素在哪 int index = indexOf(p); if (index < 0 ){ return false; } // 在p元素的前面插入元素e insert(index,e); return true; }

11.insertAfter(Object p, Object e)

// 在指定的元素后面插入元素e @Override public boolean insertAfter(Object p, Object e) { // 找到p元素在哪 int index = indexOf(p); if (index < 0 ){ return false; } // 在p元素的前面插入元素e insert(index + 1,e); return true; }

12.toString()

// 重写toString @Override public String toString() { // 依次遍历各个节点，把元素转换为字符串 StringBuilder sb = new StringBuilder(); sb.append("["); for (Node node = first; node != null ; node = node.next) { sb.append(node.data); // 元素之间使用逗号分割 if (node != last){ sb.append(","); } } sb.append("]"); return sb.toString(); }

13.private void checkIndex(int i)

// 校验是否越界的方法 private void checkIndex(int i){ if (i < 0 || i >= size){ throw new IndexOutOfBoundsException(i + "越界"); } }

14.private Node getNode(int i)

// 返回索引值对应的结点 private Node getNode(int i) { Node pNode = first; for (int j = 0; j < i; j++) { pNode = pNode.next; } return pNode; }

*****15.private class Node

// 定义一个内部类描述双向链表的结点 private class Node{ // 保存数据域 private Object data; // 保存前驱结点 private Node prev; // 保存后继结点 private Node next; public Node(Object data, Node prev, Node next) { this.data = data; this.prev = prev; this.next = next; } }

在链表中，经常会有针对头元素与尾元素的操作

addFirst(Object e)

// 在头部添加元素e public void addFirst(Object e) { // 生成一个新的结点 Node newNode = new Node(e,null,first); /* 这种写法，如果first不存在，则会产生，空指针异常 // 将原先头结点的前驱指向这个新的结点 first.prev = newNode; // 将头节点的指针指向这个新的结点 first = newNode;*/ // 修改first指向新的结点 first = newNode; Node pNode = first.next; // 刚刚插入的头结点，既是头节点，也是尾节点 if (pNode == null){ last = newNode; }else { pNode.prev = newNode; } // 元素的个数+1 size++; }

addLast(Object e)

// 在尾部添加元素e public void addLast(Object e) { Node pNode = last; // 生成一个新的结点 Node newNode = new Node(e,last,null); if (pNode == null){ // 既是为结点，也是头结点 first = newNode; }else { pNode.next = newNode; } last = newNode; size++; }

removeFirst()

// 删除第一个元素，删除头元素 public Object removeFirst(){ return remove(0); }

removeLast()

// 删除最后一个元素，删除尾元素 public Object removeLast(){ return remove(size - 1); }

getFirst()

// 返回头元素 public Object getFirst(){ return get(0); }

getLast()

// 返回尾元素 public Object getLast(){ return get(size - 1); }

测试类

package pers.chenjiahao.linearity.duallinkedlistimpl.test; import pers.chenjiahao.linearity.duallinkedlistimpl.MyDualLinkedList; public class MyDualLinkedListTest { public static void main(String[] args) { // 创建双向链表 MyDualLinkedList linkedList = new MyDualLinkedList(); System.out.println(linkedList.getSize()); System.out.println(linkedList.isEmpty()); linkedList.insert(0,"gg"); linkedList.insert(0,"jj"); linkedList.insert(1,"dd"); linkedList.insert(3,"mm"); System.out.println(linkedList); // 测试是否包含某个元素 System.out.println(linkedList.indexOf("jj")); System.out.println(linkedList.indexOf("mm")); System.out.println(linkedList.indexOf("DD")); System.out.println(linkedList.contains("xx")); System.out.println(linkedList.contains("gg")); // 删除指定的结点 System.out.println(linkedList.remove(0)); System.out.println(linkedList); System.out.println(linkedList.remove("mm")); System.out.println(linkedList); linkedList.replace(0,"xx"); System.out.println(linkedList.get(1)); System.out.println(linkedList); linkedList.insertBefore("xx","yy"); linkedList.insertBefore("xx","oo"); System.out.println(linkedList); // [yy,oo,xx,gg] linkedList.addFirst("TT"); linkedList.addLast("MM"); System.out.println(linkedList); System.out.println(linkedList.getFirst()); System.out.println(linkedList.getLast()); System.out.println(linkedList.removeFirst()); System.out.println(linkedList.removeLast()); System.out.println(linkedList); } }

顺序存储与链式存储实现线性表的比较

时间上

线性表的基本操作：查询、插入、删除

查询

顺序存储

直接通过索引值访问每个元素，实现了数组元素的随机访问

链式存储

每次都要从头结点或尾结点开始依次查找

插入与删除

顺序存储

需要移动大量的元素

链式存储

只需要修改结点的前驱和后继指针即可，不需要移动元素

总结

查询操作多

优先选择顺序存储

插入与删除操作多

优先选择链式存储

空间上

顺序存储

预先分配一块连续的存储空间，在使用过程中会出现闲置的空间

链式存储

存储空间是动态分配的，不会浪费空间

总结

如果线性表的长度经常变化，优先选择链式存储

如果线性表的长度变化不大，优先选择顺序存储

4.栈与队列

栈与队列，从逻辑结构上看，也是线性结构，是操作受限的线性结构

栈

基本概念

栈(Stack)，也称堆栈，是一种操作受限的线性表。

栈只允许在线性表的一段进行插入/删除等操作，不允许在其他位置插入/删除

在线性表中进行插入/删除的一段称为栈顶(top),栈顶保存的元素称为栈顶元素，相对的另一端称为栈底(bottom)

如果栈中没有数据元素称为空栈

向栈中插入元素，称为进栈/入栈/压栈，从栈中删除元素称退栈/出栈/弹栈

栈的插入/删除操作只允许在栈顶进行，后进栈的元素必定先出栈，称为先进后出或后进先出

图解

堆栈抽象数据类型

ADT Stack{        数据对象：D = {a0,a1,a2...an,ai是同一种数据类型的元素}        数据关系：R = {<ai,a(i+1)>}        基本操作：              getSize() 返回元素的个数              isEmpty()判断堆栈是否为空              push(Object e) 压栈              pop()  弹栈              peek() 返回栈顶元素 }

MyStack接口

package pers.chenjiahao.linearity.stackoperator; /** * 定义接口，定义栈的操作 */ public interface MyStack { int getSize(); // 判断栈的长度 boolean isEmpty(); // 判断栈是否为空 void push(Object e); // 压栈，入栈 Object pop(); // 弹栈，出栈 Object peek(); // 返回栈顶元素 }

顺序实现

基本概念

顺序栈可以通过数组存储堆栈的元素

堆栈的操作都在栈顶完成，选择数组中索引值较大的一端作为栈顶

代码实现

创建一个MyArrayStack类，实现MyStack接口

完整代码

package pers.chenjiahao.linearity.arraystack; import pers.chenjiahao.linearity.stackoperator.MyStack; /** * 栈的顺序实现 */ public class MyArrayStack implements MyStack { // 定义数组来保存栈的元素 private Object[] elements; // 栈的默认容量 private static final int DEFAULT_CAPACITY = 16; // 栈顶指针 private int top; // 无参构造中，对数组默认初始化 public MyArrayStack() { elements = new Object[DEFAULT_CAPACITY]; } // 有参构造中，指定栈的初始化大小 public MyArrayStack(int initialCapacity) { elements = new Object[initialCapacity]; } // 返回元素的个数 @Override public int getSize() { return top; } // 判断栈中是否为空 @Override public boolean isEmpty() { return top <= 0; } // 入栈/压栈 @Override public void push(Object e) { // 判断栈是否已满，如果已满，数组需要扩容 if (top >= elements.length){ // 定义一个更大的数组 Object[] newData = new Object[elements.length * 2]; // 将原来的数组的内容复制到大的数组中 for (int i = 0; i < elements.length; i++) { newData[i] = elements[i]; } // 让原来的数组名指向新的数组 elements = newData; } // 把元素存储到栈顶指针指向的位置 elements[top] = e; // 栈顶指针上移 top++; } // 出栈/弹栈 @Override public Object pop() { // 判断栈是否为空 if (top <= 0){ throw new StackOverflowError("栈已空"); } top--; // 栈顶指针下移 return elements[top]; } // 返回栈顶元素,不删除 @Override public Object peek() { // 判断栈是否为空 if (top <= 0){ throw new StackOverflowError("栈已空"); } return elements[top - 1]; } // 重写toString()，从栈顶到占底输出 @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("["); // 从栈顶到占地的顺序添加各个元素 for (int i = top - 1; i >= 0; i--) { sb.append(elements[i]); // 元素之间用逗号分割 if (i > 0){ sb.append(","); } } sb.append("]"); return sb.toString(); } }

各个功能模块代码

1.getSize()

// 返回元素的个数 @Override public int getSize() { return top; }

2.isEmpty()

// 判断栈中是否为空 @Override public boolean isEmpty() { return top <= 0; }

3.push(Object e)

// 入栈/压栈 @Override public void push(Object e) { // 判断栈是否已满，如果已满，数组需要扩容 if (top >= elements.length){ // 定义一个更大的数组 Object[] newData = new Object[elements.length * 2]; // 将原来的数组的内容复制到大的数组中 for (int i = 0; i < elements.length; i++) { newData[i] = elements[i]; } // 让原来的数组名指向新的数组 elements = newData; } // 把元素存储到栈顶指针指向的位置 elements[top] = e; // 栈顶指针上移 top++; }

4.pop()

// 出栈/弹栈 @Override public Object pop() { // 判断栈是否为空 if (top <= 0){ throw new StackOverflowError("栈已空"); } top--; // 栈顶指针下移 return elements[top]; }

5.peek()

// 返回栈顶元素,不删除 @Override public Object peek() { // 判断栈是否为空 if (top <= 0){ throw new StackOverflowError("栈已空"); } return elements[top - 1]; }

6.toString()

// 重写toString()，从栈顶到占底输出 @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("["); // 从栈顶到占地的顺序添加各个元素 for (int i = top - 1; i >= 0; i--) { sb.append(elements[i]); // 元素之间用逗号分割 if (i > 0){ sb.append(","); } } sb.append("]"); return sb.toString(); }

测试类

package pers.chenjiahao.linearity.arraystack.test; import pers.chenjiahao.linearity.arraystack.MyArrayStack; public class MyArrayStackTest { public static void main(String[] args) { // 创建栈 MyArrayStack stack = new MyArrayStack(); System.out.println(stack.isEmpty()); // true System.out.println(stack.getSize()); // 0 // 压栈 stack.push("aa"); stack.push("bb"); stack.push("cc"); stack.push("dd"); System.out.println(stack.isEmpty()); // false System.out.println(stack.getSize()); // 4 // 重写toString方法 System.out.println(stack); // [dd,cc,bb,aa] // 弹出栈顶元素 System.out.println(stack.peek()); // dd // 出栈 System.out.println(stack.pop()); // dd System.out.println(stack); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack); } }

链式实现

基本概念

使用链表作为栈的存储结构，有时也成为链栈

栈只允许在线性表的一端进行操作，可以选择链表的表头作为栈顶

第一个结点可以当作为栈底

不管是压栈还是弹栈，都要在链表的首结点进行

代码实现

创建一个MyLinkStack类，实现MyStack接口

完整代码

package pers.chenjiahao.linearity.linkstack; import pers.chenjiahao.linearity.stackoperator.MyStack; /** * 栈的链式存储 * 注：第一个定义的结点，相当于就是栈底 */ public class MyLinkStack implements MyStack { // 存储栈顶的引用 private Node top; // 保存栈中元素的个数 private int size; // 返回栈中元素的个数 @Override public int getSize() { return size; } // 判断栈是否为空 @Override public boolean isEmpty() { return size == 0; } // 入栈/压栈 @Override public void push(Object e) { // 根据元素生成结点，插入到链表的头部 Node pNode = new Node(e,top); // 修改top栈顶指针,指向新的结点 top = pNode; // 元素个数+1 size++; } // 出栈/弹栈 @Override public Object pop() { // 判断栈是否为空 if (size < 1){ throw new StackOverflowError("栈已空"); } // 保存原来栈顶元素 Object oldData = top.data; // 后移栈顶指针 top = top.next; size--; return oldData; } // 返回栈顶元素 @Override public Object peek() { // 判断栈是否为空 if (size < 1){ throw new StackOverflowError("栈已空"); } return top.data; } // 重写toString方法 @Override public String toString() { // 将链表中各个结点的数据给返回 StringBuilder sb = new StringBuilder(); sb.append("["); for (Node pNode = top; pNode != null; pNode = pNode.next){ sb.append(pNode.data); // 数据元素之间使用逗号分割 if (pNode.next != null){ sb.append(","); } } sb.append("]"); return sb.toString(); } // 定义一个内部类，描述链表中的结点 private class Node{ // 存储数据 Object data; // 存储下个结点的引用 Node next; public Node() { } public Node(Object data, Node next) { this.data = data; this.next = next; } } }

各个功能模块代码

1.getSize()

// 返回栈中元素的个数 @Override public int getSize() { return size; }

2.isEmpty()

// 判断栈是否为空 @Override public boolean isEmpty() { return size == 0; }

3.push(Object e)

// 入栈/压栈 @Override public void push(Object e) { // 根据元素生成结点，插入到链表的头部 Node pNode = new Node(e,top); // 修改top栈顶指针,指向新的结点 top = pNode; // 元素个数+1 size++; }

4.pop()

// 出栈/弹栈 @Override public Object pop() { // 判断栈是否为空 if (size < 1){ throw new StackOverflowError("栈已空"); } // 保存原来栈顶元素 Object oldData = top.data; // 后移栈顶指针 top = top.next; size--; return oldData; }

5.peek()

// 返回栈顶元素 @Override public Object peek() { // 判断栈是否为空 if (size < 1){ throw new StackOverflowError("栈已空"); } return top.data; }

6.toString()

// 重写toString方法 @Override public String toString() { // 将链表中各个结点的数据给返回 StringBuilder sb = new StringBuilder(); sb.append("["); for (Node pNode = top; pNode != null; pNode = pNode.next){ sb.append(pNode.data); // 数据元素之间使用逗号分割 if (pNode.next != null){ sb.append(","); } } sb.append("]"); return sb.toString(); }

*****private class Node

// 定义一个内部类，描述链表中的结点 private class Node{ // 存储数据 Object data; // 存储下个结点的引用 Node next; public Node() { } public Node(Object data, Node next) { this.data = data; this.next = next; } }

测试类

package pers.chenjiahao.linearity.linkstack.test; import pers.chenjiahao.linearity.linkstack.MyLinkStack; public class MyLinkStackTest { public static void main(String[] args) { // 创建链栈 MyLinkStack stack = new MyLinkStack(); System.out.println(stack.isEmpty()); // true System.out.println(stack.getSize()); // 0 // 压栈 stack.push("ppp"); stack.push("aaa"); stack.push("xxx"); stack.push("ooo"); System.out.println(stack); // [ooo,xxx,aaa,ppp] // 出栈 System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack); } }

栈的应用

1.进制转换

十进制转为别的进制

图解：十进制转为二进制

代码实现

package pers.chenjiahao.linearity.stackapplication.baseconversion; import pers.chenjiahao.linearity.arraystack.MyArrayStack; /** * 使用栈完成进制转换 */ public class BaseConversion { public static void main(String[] args) { System.out.println(convert(100,2)); // 1100100 System.out.println(convert(100,8)); // 144 // 十六进制要转换到相应的abcdef // System.out.println(convert(100,16)); } /** * 把一个十进制整数num转换decimal指定的进制 * @param num 接收的十进制整数 * @param decimal 指定进制 * @return 返回num这个整数对应的decimal进制的字符串 */ public static String convert(int num,int decimal){ // 保存余数 MyArrayStack stack = new MyArrayStack(); // 余数 int remainder = num % decimal; while (num != 0 ){ // 余数压栈 stack.push(remainder); num = num / decimal; remainder = num % decimal; } // 出栈，余数倒序 StringBuilder sb = new StringBuilder(); while(!stack.isEmpty()){ sb.append(stack.pop()); } return sb.toString(); } }

2.检测表达式中括号是否匹配

假设表达式中包含三种括号：()、[]、{}，这三种括号可以任意嵌套

对于任意一个左括号都需要一个对应的右括号匹配，最早出现的右括号应该与最早出现的左括号匹配

算法思路

读取整个表达式， 如果是左括号就直接入栈，等待与它对应的右括号出现 如果是右括号，则与当前栈顶的左括号判断是否匹配            如果不匹配，说明表达式不合法 如果是右括号，表示栈已空，表示不合法 读完整个表达式，堆栈不空，表示有左括号没匹配上，表达式不合法； 读完整个表达式，栈是空的表示所有括号都能匹配

代码实现

package pers.chenjiahao.linearity.stackapplication.bracketmatching; import pers.chenjiahao.linearity.arraystack.MyArrayStack; /** * 检测表达式中的括号是否匹配 */ public class BracketMatch { public static void main(String[] args) { System.out.println(bracketMath("([{}])")); // true System.out.println(bracketMath("([{{])")); // false System.out.println(bracketMath("([{}}])")); // false } // 检测expression表达式中的括号是否匹配 public static boolean bracketMath(String expresion){ // 定义一个栈用来保存各种左括号 MyArrayStack stack = new MyArrayStack(); // 遍历整个表达式，如果是左括号就入栈，如果是右括号就出栈,进行判断是否匹配 for (int i = 0; i < expresion.length(); i++) { // 取出表达式的每个字符 char cc = expresion.charAt(i); switch (cc){ case '(': case '[': case '{': stack.push(cc);// 左括号入栈 break; case '}': if (!stack.isEmpty() && stack.pop().equals('{')){ break; }else { return false; } case ']': if (!stack.isEmpty() && stack.pop().equals('[')){ break; }else { return false; } case ')': if (!stack.isEmpty() && stack.pop().equals('(')){ break; }else { return false; } } } // 表达式遍历完后，如果栈是空的，表示括号匹配 if (stack.isEmpty()){ return true; }else { return false; } } }

3.算术表达式的求值

四则运算的规则

先乘除后加减

先括号内，再括号外

从左到右进行运算

例：4+3+(6-10+2*3)*4

4+3+(6-10+2*3)*4

7+(6-10+2*3)*4

7+(-4+2*3)*4

7+(-4+6)*4

7+2*4

7+8

图解

算法思路

定义两个栈，一个存储操作符operator,一个存储操作数operand

读取表达式

如果是操作数就存储到operand操作数栈中

如果是操作符

操作符栈是空，直接入栈

把操作符栈中的栈顶操作符与当前操作符进行优先级比较

当前操作符优先级高，操作符入栈

当前操作符优先级低(栈顶操作符优先级高), 弹出栈顶操作符， 再从操作数栈中弹出两个操作数做运算， 将运算结果存储到操作数栈中， 继续判断当前的操作符与栈顶操作符的优先级

遍历完整个表达式，连个栈都不为空，依次弹出操作符栈中的操作符和操作数栈中的两个操作数进行计算，把结果再存储到操作数栈中

如果操作符栈不为空，或操作数栈中的数不止一个，则表达式错误

如果操作符栈为空，操作数栈中只有一个数字，返回这个数，即计算的答案

代码实现

package pers.chenjiahao.linearity.stackapplication.calculateexpression; import pers.chenjiahao.linearity.arraystack.MyArrayStack; /** * 使用栈来计算算数表达式的值 */ public class CalculateExpression { public static void main(String[] args) { String expression = "4+3+(6-10+2*3)*4"; double result = calculate(expression); System.out.println(result); } // 定义方法计算指定表达式的值 4+3+(6-10+2*3)*4 private static double calculate(String expression) { // 定义一个栈用与存储操作符 MyArrayStack operatorStack = new MyArrayStack(); // 定义一个栈用与存储操作数 MyArrayStack operandStack = new MyArrayStack(); // 遍历表达式中的操作数与操作符 for (int i = 0; i < expression.length(); i++) { // 取出每个符号 char cc = expression.charAt(i); // 如果cc是数字 if (Character.isDigit(cc)){ // 取出操作数 StringBuilder sb = new StringBuilder(); // 只要是数字就是操作数的一部分如果这里直接取出cc的话会有问题，比如说66+55 只会取走一个6 66被分割了，所以要处理一下 while (Character.isDigit(cc)){ sb.append(cc); i++; // 判断i++是否越界 if (i >= expression.length()){ // 说明表达式结束了 break; } // 如果没有到末尾，取出下一个字符 cc = expression.charAt(i); } // 操作数入栈 operandStack.push(sb.toString()); // 修正一下i，i在while中最后判断了一次，需要退回一次 i--; // 测试一下 System.out.println(sb); }else { // 如果是操作符 // 栈为空，直接将操作符入栈 if (operatorStack.isEmpty()){ operatorStack.push(cc); continue; } // 操作符栈不为空,取出栈顶的操作符 // 栈不为空的时候需要一直判断 while (!operatorStack.isEmpty()){ char op1 = (char) operatorStack.peek(); // 判断栈中操作符与当前操作符的优先级 if (compareOperator(op1,cc) < 0){ // 当前运算符的优先级高于栈顶运算符的优先级直接入栈 operatorStack.push(cc); break; }else if (compareOperator(op1,cc) == 0){ // 当前操作符的优先级等于栈顶运算符的优先级,只有一种情况：左一半小括号遇到右一半小括号的情况 // 栈中左一半小括号出栈 operatorStack.pop(); break; }else { // 栈顶操作符优先级高 // 取出两个操作数 // 如果操作数栈为空，也表示表达式错误 if (operandStack.isEmpty()){ throw new RuntimeException("表达式错误"); } double num1 = Double.parseDouble(operandStack.pop().toString()); // 如果操作数栈为空，也表示表达式错误 if (operandStack.isEmpty()){ throw new RuntimeException("表达式错误"); } double num2 = Double.parseDouble(operandStack.pop().toString()); // 取出栈顶操作符 char operator = (char) operatorStack.pop(); // 计算 num2 operator num1 double result = compute(num2,operator,num1); // 把结果存储到操作数栈中 operandStack.push(result); // 如果当前操作符栈为空，新的操作符应该入栈 if (operatorStack.isEmpty()){ operatorStack.push(cc); break; } } } } } // 当表达式遍历完后，如果操作符栈不为空，需要继续计算 while (!operatorStack.isEmpty()){ // 取出一个操作符 char operator = (char) operatorStack.pop(); // 取出两个操作数 // 如果操作数栈为空，也表示表达式错误 if (operandStack.isEmpty()){ throw new RuntimeException("表达式错误"); } double num1 = Double.parseDouble(operandStack.pop().toString()); // 如果操作数栈为空，也表示表达式错误 if (operandStack.isEmpty()){ throw new RuntimeException("表达式错误"); } double num2 = Double.parseDouble(operandStack.pop().toString()); // 计算 double result = compute(num2,operator,num1); // 操作数入栈 operandStack.push(result); } // 能走到这里说明操作符栈已经为空了，如果操作数栈中多余一个数，说明表达式错误 if (operandStack.getSize() > 1){ throw new RuntimeException("表达式错误"); } return Double.parseDouble(operandStack.pop().toString()); } /** * 计算num1 operator num2 表达式的值 * @param num2 先入栈的操作数 * @param operator 操作符 * @param num1 后入栈的操作数 * @return num1 operator num2 的结果 */ private static double compute(double num2, char operator, double num1) { switch (operator){ case '+': return num2 + num1; case '-': return num2 - num1; case '*': return num2 * num1; case '/': return num2 / num1; } return 0; } /** * 判断两个操作符的优先级 * @param op1 栈顶中的操作符 * @param op2 从表达式中取出的操作符 * @return 如果op1优先级高返回整数，如果op2优先级高返回负数 */ private static int compareOperator(char op1, char op2) { // 第一个操作符是+- 第二个操作符是*/( if (op1 == '+' || op1 == '-'){ if (op2 == '*' || op2 == '/' || op2 == '('){ // 能走都这里说明 op1 优先级低 return -1; } } // 第一个操作符是* / 第二个操作符是( if (op1 == '*' || op1 == '/'){ if (op2 == '('){ return -1; } } if (op1 == '('){ if (op2 == ')'){ return 0; }else { return -1; } } return 1; } }

队列

基本概念

队列(Queue)简称为队，也是一种受限的线性表

只允许在线性表的一段进行插入，在另一端进行删除

插入数据的一端称为队尾(rear)

删除数据的一段称为队首(front)

向队列添加数据称为入队/进队，新入队的元素称为队尾元素

从队列中删除元素称为出队或离队，元素出队之后，它的后续元素称为新的队首元素

队列是先进先出的(FIFO)

队列抽象数据类型

ADT Queue{        数据对象：D = {a0,a1,a2...an,ai是同一种数据类型的元素}        数据关系：R = {<ai,a(i+1)>}        基本操作：               getSize() 返回元素的个数               isEmpty()判断队列是否为空               enQueue(Object e) 入队               deQueue() 出队               peek() 返回队首的元素 }

MyQueue接口

package pers.chenjiahao.linearity.queueoperator; public interface MyQueue { int getSize(); // 返回元素的个数 boolean isEmpty();// 判断队列是否为空 void enQueue(Object e); // 入队 Object deQueue(); // 出队 Object peek();// 返回队首元素 }

顺序实现

基本概念

在队列的实现中，可以把数据设想为一个圆环，这种数组称为循环数组，用循环数组实现的队列称为循环队列

用front指针指向队首元素所在的单元，使用rear指针指向队尾元素所在单元的后一个单元

在元素入队时，将心如对的元素保存到rear指向的单元，然后rear指针后移

在元素出队时，将队首指针front指向的元素返回，然后front后移

图解

队列为空和队列已满的表示

图解

第一种方式

少用一个存储单元，当队尾指针rear的下一个单元是队首指针front时，停止入队

(rear+1)%capacity==front时表示队列已满

front==rear时表示队列为空

图解：表示队列已满

第二种方式

增设一个变量表示队列为空还是满，通常使用size变量表示元素的个数

当size==0时队列为空

当size==capacity时表示队列已满

代码实现

创建一个MyArrayQueue类，实现MyQueue接口

完整代码

package pers.chenjiahao.linearity.arrayqueue; import pers.chenjiahao.linearity.queueoperator.MyQueue; import pers.chenjiahao.linearity.queueoperator.exception.QueueEmptyException; /** * 队列的顺序存储实现 */ public class MyArrayQueue implements MyQueue { // 定义数组存储队列中的元素 private Object[] elements; // 设置初始化容量的默认值 private static final int DEFAULT_CAPACITY = 8; // 队首 private int front; // 队尾 private int rear; // 元素的个数 private int size; // 无参构造 public MyArrayQueue() { elements = new Object[DEFAULT_CAPACITY]; } // 指定初始化容量的构造 public MyArrayQueue(int initialCapacity) { elements = new Object[initialCapacity]; } // 返回元素的个数 public int getSize(){ return size; } // 判断队列是否为空 public boolean isEmpty(){ return size == 0; } // 入队 public void enQueue(Object e){ // 如果队列已满，可以对数组扩容 if (size >= elements.length){ expandQueue(); } // 把元素存储到rear指针指向的单元 elements[rear] = e; // rear指针后移 rear = (rear + 1) % elements.length; // 元素加一 size++; } // 出队 public Object deQueue(){ // 如果队列为空 if (size <= 0){ // 抛出队列为空异常 throw new QueueEmptyException("队列为空"); } // 队列不为空，把front指向的元素返回 Object old = elements[front]; // 将front指针后移 front = (front + 1) % elements.length; // 元素个数-1 return old; } // 返回队首元素 public Object peek(){ // 队列为空，抛出异常 if (size <= 0){ // 抛出队列为空异常 throw new QueueEmptyException("队列为空"); } return elements[front]; } // 队列的数组进行扩容 private void expandQueue() { // 定义一个更大的数组 Object[] newElements = new Object[elements.length * 2]; // 把原来的数组的内容赋值到新的数组中,这里需要注意，在旧的数组中，队首不一定是从0开始的 // 需要将旧数组放到新数组的0下标开始 for (int i = 0; i < size; i++) { newElements[i] = elements[front]; front = (front + 1) % elements.length; } // 让原来的数组名，指向新的数组 elements = newElements; // 调整新的队首和队尾指针 front = 0; rear = size; } }

各个功能模块代码

1.getSize()

// 返回元素的个数 public int getSize(){ return size; }

2.isEmpty()

// 判断队列是否为空 public boolean isEmpty(){ return size == 0; }

3.enQueue(Object e)

// 入队 public void enQueue(Object e){ // 如果队列已满，可以对数组扩容 if (size >= elements.length){ expandQueue(); } // 把元素存储到rear指针指向的单元 elements[rear] = e; // rear指针后移 rear = (rear + 1) % elements.length; // 元素加一 size++; }

4.deQueue()

// 出队 public Object deQueue(){ // 如果队列为空 if (size <= 0){ // 抛出队列为空异常 throw new QueueEmptyException("队列为空"); } // 队列不为空，把front指向的元素返回 Object old = elements[front]; // 将front指针后移 front = (front + 1) % elements.length; // 元素个数-1 return old; }

5.peek()

// 返回队首元素 public Object peek(){ // 队列为空，抛出异常 if (size <= 0){ // 抛出队列为空异常 throw new QueueEmptyException("队列为空"); } return elements[front]; }

private void expandQueue()

// 队列的数组进行扩容 private void expandQueue() { // 定义一个更大的数组 Object[] newElements = new Object[elements.length * 2]; // 把原来的数组的内容赋值到新的数组中,这里需要注意，在旧的数组中，队首不一定是从0开始的 // 需要将旧数组放到新数组的0下标开始 for (int i = 0; i < size; i++) { newElements[i] = elements[front]; front = (front + 1) % elements.length; } // 让原来的数组名，指向新的数组 elements = newElements; // 调整新的队首和队尾指针 front = 0; rear = size; }

测试类

package pers.chenjiahao.linearity.arrayqueue.test; import pers.chenjiahao.linearity.arrayqueue.MyArrayQueue; import pers.chenjiahao.linearity.queueoperator.MyQueue; /** * 测试顺序队列 */ public class MyArrayQueueTest { public static void main(String[] args) { MyQueue queue = new MyArrayQueue(); // 入队 queue.enQueue("a"); queue.enQueue("b"); queue.enQueue("C"); queue.enQueue("d"); // 返回队首元素 System.out.println(queue.peek()); // 出队 System.out.println(queue.deQueue()); System.out.println(queue.deQueue()); System.out.println(queue.deQueue()); System.out.println(queue.deQueue()); // System.out.println(queue.deQueue()); queue.enQueue("1"); queue.enQueue("2"); queue.enQueue("3"); queue.enQueue("4"); queue.enQueue("5"); queue.enQueue("6"); queue.enQueue("7"); queue.enQueue("8"); queue.enQueue("J"); queue.enQueue("Q"); queue.enQueue("K"); } }

链式实现

基本概念

使用单向链表来实现队列

把链表的头部作为队首，把链表的尾部作为队尾

图解

代码实现

创建一个MyLinkQueue类，实现MyQueue接口

完整代码

package pers.chenjiahao.linearity.linkqueue; import pers.chenjiahao.linearity.queueoperator.MyQueue; import pers.chenjiahao.linearity.queueoperator.exception.QueueEmptyException; /** * 队列的链式存储 */ public class MyLinkQueue implements MyQueue { // 队首 private Node front; // 队尾 private Node rear; // 元素的个数 private int size; // 返回元素的个数 @Override public int getSize() { return size; } // 判断队列是否为空 @Override public boolean isEmpty() { return size == 0; } // 入队 @Override public void enQueue(Object e) { // 生成一个结点 Node newNode = new Node(e,null); // 把结点连接到队列中 if (rear == null){ // 这是添加的第一个元素，既是头结点也是尾结点 rear = newNode; front = newNode; }else { // 把结点连接到队列的尾部 rear.next = newNode; // rear 指针指向新添加的元素 rear = newNode; } // 元素个数+1 size++; } // 出队 @Override public Object deQueue() { // 判断队列是否为空 if (size <= 0){ throw new QueueEmptyException("队列为空"); } // 保存要出队的数据 Object old = front.element; // 指针下移 front = front.next; // 如果出队后队列为空，调整尾指针 if (front == null){ rear = null; } // 元素-1 size--; return old; } // 返回队首元素 @Override public Object peek() { // 判断队列是否为空 if (size <= 0){ throw new QueueEmptyException("队列为空"); } return front.element; } // 内部类表示单向链表的结点 private class Node{ Object element; Node next; public Node(Object element, Node next) { this.element = element; this.next = next; } } }

各个功能模块代码

1.getSize()

// 返回元素的个数 @Override public int getSize() { return size; }

2.isEmpty()

// 判断队列是否为空 @Override public boolean isEmpty() { return size == 0; }

3.enQueue(Object e)

// 入队 @Override public void enQueue(Object e) { // 生成一个结点 Node newNode = new Node(e,null); // 把结点连接到队列中 if (rear == null){ // 这是添加的第一个元素，既是头结点也是尾结点 rear = newNode; front = newNode; }else { // 把结点连接到队列的尾部 rear.next = newNode; // rear 指针指向新添加的元素 rear = newNode; } // 元素个数+1 size++; }

4.deQueue()

// 出队 @Override public Object deQueue() { // 判断队列是否为空 if (size <= 0){ throw new QueueEmptyException("队列为空"); } // 保存要出队的数据 Object old = front.element; // 指针下移 front = front.next; // 如果出队后队列为空，调整尾指针 if (front == null){ rear = null; } // 元素-1 size--; return old; }

5.peek()

// 返回队首元素 @Override public Object peek() { // 判断队列是否为空 if (size <= 0){ throw new QueueEmptyException("队列为空"); } return front.element; }

private class Node

// 内部类表示单向链表的结点 private class Node{ Object element; Node next; public Node(Object element, Node next) { this.element = element; this.next = next; } }

测试类

package pers.chenjiahao.linearity.linkqueue.test; import pers.chenjiahao.linearity.linkqueue.MyLinkQueue; import pers.chenjiahao.linearity.queueoperator.MyQueue; public class MyLinkQueueTest { public static void main(String[] args) { MyQueue queue = new MyLinkQueue(); System.out.println(queue.getSize()); System.out.println(queue.isEmpty()); queue.enQueue("a"); queue.enQueue("b"); queue.enQueue("c"); System.out.println(queue.getSize()); System.out.println(queue.getSize()); System.out.println(queue.peek()); queue.deQueue(); System.out.println(queue.getSize()); System.out.println(queue.isEmpty()); } }

5.树

树的定义

树是由一个集合及该集合上的定义的一种关系构成的。集合中的元素称为树的结点，定义的关系称为父子关系，父子关系的树的结点之间建立一个层次结构。

树的递归定义：       树是由n(n>=0)个结点组成的有限集       当n=0时，称为空树；       当n>0时，就是一颗非空树:             （1）有且仅有一个特定的称为根的结点（root）;             （2）当n>1时，其他结点可以分为m(m>0)个互不相交的有限集T1，T2...，                      其中每个有限集又是一颗树，称为根节点的子树(SubTree)

在右图中，结点A是根节点，它包含T1和T2两棵树，T1={BDGHI},T2={CEFJ},每颗子树又是一颗树， 在T1子树中，B是根节点，在T2子树中，C是根节点

当n>0时，在非空树中，根节点是唯一的 当m>0时，某个结点的子树是没有限制的，并且各个子树肯定是不相交的