李福腾の博客

图的表示方式二维数组表示（邻接矩阵）、链表表示（邻接表）数组加链表 图的创建和代码实现存储顶点String 使用 ArrayList import java.util.ArrayList;import java.util.Arrays;public class Graph { private int[][] edrges; private ArrayList<String> vertexList; private int numOfEdges; public static void main(String[] args) { //测试是否创建成功 int n = 5; String VertexValue[]={"A","B","C","D","E"}; Graph graph =new Graph(n); for (String valu ...

二叉排序树介绍对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大 特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点 二叉排序树的创建和遍历代码实现 public class BinarySotrTree { public static void main(String[] args) { int[] arr ={7,3,10,12,5,1,9}; BinarySortTre binarySortTre = new BinarySortTre(); for (int i = 0; i <arr.length ; i++) { binarySortTre.add(new Node(arr[i])); } //中序遍历 binarySortTre.infixOrder(); }}//创建二叉排序树class BinarySortTr ...

堆排序堆排序的基本介绍堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，他的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序 堆是具有以下性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆，注意：没有要求节点的左孩子的值和右孩子节点的值的大小关系。 每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆 堆排序的基本思想 将待排序序列构造成一个大顶堆 整个序列的最大值就是堆顶的根节点 将其与末尾元素进行交换，此时末尾就为最大值 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便得到一个有序序列了 代码实现public class HeapSort { public static void main(String[] args) { int arr[] = {4, 6, 8, 5, 9}; heapSort(arr); } //编写一个堆排序的方法 public static void heap ...

哈希表介绍散列表也叫哈希表，是根据关键码值而直接进行访问的数据结构，也就是说，它通过把关键码值映射到表中一个位置来访问计录，以加快查找的速度。这个映射函数叫做散列函数，存放计录的数组叫做散列表。 import java.util.Scanner;public class HashTabDemo { public static void main(String[] args) { //创建哈希表 HashTab hashTab = new HashTab(7); //写一个简单的菜单 String key =""; Scanner scanner = new Scanner(System.in); while (true){ System.out.println("add:添加雇员"); System.out.println("list:显示雇员"); ...

二分查找 有序数组进行二分查找 二分查找有两种 一种是递归，一种 是非递归 二分查找的思路分析 首先确定该数组的中间的下标 mid =(left+right)/2 接着让需要查找的数findVal和arr[mid]比较 findVal > arr[mid] 说明要找的数在mid右边，需要向右递归查找，findVal < arr[mid] 说明要找的数在mid左边，需要向左递归查找 findVal=arr[mid]说明找到，就返回 当 left>right就需要退出 代码实现 public class BinarySearch { public static void main(String[] args) { int arr[] = {1,8,10,89,1000,1234}; System.out.println(binarySearch(arr, 0, arr.length-1, 88)); } //二分查找 public ...

希尔排序 基本介绍 希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效率的版本，也称为缩小增量排序。 基本思想 希尔排序是把计录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。 代码实现【交换式】 public static void sellSort(int[] arr){ int temp =0; //第一层for循环时每一次的分组情况 for (int gap =arr.length / 2; gap >0 ; gap/=2) { for (int i =gap; i <arr.length ; i++) { for (int j = i-gap; j>=0 ; j-=gap) {//遍历各组中所有的元素 if (arr[j]>arr[j+gap]){ temp = ...

排序算法排序算法的介绍 排序算法是将一组数据，依指定的顺序进行排列的过程 排序的分类 内部排序 指将需要处理的所有数据都加载到内部存储器（内存）中进行排序。 外部排序法 数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。 算法的时间复杂度 时间频度：一个算法中的语句执行次数称为时间频度T(n) 常见的时间复杂度 常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n) 平方阶O(n^2) 立方阶O(n^3) K次方阶O(n^k) 指数阶O(2^n) 冒泡排序 基本介绍 通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，值较大的元素逐渐从前移向后部。 冒泡排序规则 一共进行数组大小-1次大的循环 每一趟循环的次数在逐渐减少 如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序，这个就是优化。 代码实现 public static void bubbleSort(int[] arr) { boolean flag = false;//标识变量，表示 ...

递归递归应用场景 迷宫问题（回溯） package sparsearray;public class migong { public static void main(String[] args) { //创建二维数组模拟迷宫 int[][] map =new int[8][7]; map[3][1] =1; map[3][2] =1; //使用1表示墙 for (int i = 0; i <7 ; i++) { map[0][i]=1; map[7][i]=1; } for (int i = 0; i <8 ; i++) { map[i][0] = 1; map[i][6] = 1; } //输出地图 for (int i = 0; i <8 ; i++)
...

栈（stack）栈的介绍 栈是一个先入后出的有序列表 栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶（Top）,另一端为固定的一端，称为栈底（Bottom）。 最先放入栈中的元素在栈底，最后放入的元素在栈顶。最后放入的元素先删除，最先放入的元素后删除。 数组模拟栈 思路分析 定义一个top来表示栈顶，初始化为-1 入栈操作，当有数据加入时，top++;stack[top]=data; 出栈操作，int value=stack[top];top–;return value 代码实现 class Arraystack { private int maxSize;//栈的大小 private int[] stack;//数组模拟栈，数据放到数组中 private int top = -1;//top 表示栈顶 初始化为-1 public Arraystack(int maxSize) { this.maxSize = maxSize; ...

链表单链表介绍和内存分布 链表是以节点的方式来存储的 每个节点包含data域，next域：指向下一个节点 链表的各个节点不一定是连续存储 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定。 单链表的创建和遍历带头节点的单链表 head节点 不存放具体数据，作用是表示单链表的头 单链表的最后一个节点next域指向为NULL 单链表的创建 先创建一个head头节点 后面我们每添加一个节点，就直接加入到链表的最后 遍历 通过一个辅助遍历，帮助遍历整个链表 单链表的代码实现 package sparsearray;public class SingleLinkedList { public static void main(String[] args) { //进行测试 //先创建节点 Heronode heronode1 =new Heronode(1, "宋江", "及时雨"); Heronode heronode2 =new Herono ...