数据结构和算法学习--排序算法简介
数据结构和算法学习--排序算法简介1. 排序算法的介绍排序也称排序算法(Sort Algorithm),排序是将一组数据，依指定的顺序进行排序的过程。2. 排序的分类：（1）内部排序：指将需要处理的所有数据都加载到内部存储器（内存）中进行排序。（2）外部排序法：数据量过大，无法全部加载到内存中，需要借助外部存储（文件等）进行排序。（3）常见的排序算法分类：3. 算法的时间复杂度3.1 度量一个程序（算法）执行时间的两种方法（1）事后统计的方法 这种方法可行, 但是有两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件、...
数据结构学习--递归-八皇后问题（回溯法）
数据结构学习--递归-八皇后问题（回溯法）一、八皇后问题介绍八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。二、八皇后问题算法思路分析（1）第一个皇后先放第一行第一列（2）第二个皇后放在第二行第一列、然后判断是否OK,如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适的（3）继续第三个皇后，还是第一列、第二列......直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解（4）...
数据结构学习--递归-迷宫问题
数据结构学习--递归-迷宫问题迷宫问题代码实现public class MiGong { public static void main(String[] args) { //先创建一个二维数组，模拟迷宫 //地图 int[][] map = new int[8][7]; //使用1表示墙 //上下全部置为1 for(int i=0;i<7;i++){ map[0][i]=1; map[7][i]=1; } ...
数据结构学习--递归简述
数据结构学习--递归简述一、递归应用场景看个实际应用场景，迷宫问题(回溯)， 递归(Recursion)二、递归的概念简单的说：递归就是方法自己调用自己，每次调用时传入不同的变量，递归有助于编程者解决复杂的问题，同时可以让代码变得简洁。三、递归调用机制两个递归调用案例：（1）打印问题（2）阶乘问题使用图解方式说明递归调用机制代码示例public class RecursionTest { public static void main(String[] args) { test(4); int res = factorial(3); ...
数据结构学习--中缀表达式转换为后缀表达式
数据结构学习--中缀表达式转换为后缀表达式前言大家看到，后缀表达式适合计算机进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发中，我们需要将中缀表达式转成后缀表达式。步骤1. 初始化两个栈：运算符栈s1和储存中间结果的栈s2; 2. 从左至右扫描中缀表达式; 3. 遇到操作数时，将其压s2; 4. 遇到运算符时，比较其与s1栈顶运算符的优先级; 4.1 如果s1为空，或栈顶运算符为左括号"(",则直接将此运算符入栈; 4.2 否则，若优先级比栈顶运算符的高，也将运算符压入s1; 4.3 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)...
数据结构学习--逆波兰计算器
数据结构学习--逆波兰计算器完成一个逆波兰计算器，要求完成如下任务：（1）输入一个逆波兰表达式（后缀表达式），使用栈 (Stack),计算其结果 （2）支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。思路分析：例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:(1). 从左至右扫描，将3和4压入堆栈；(2). 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；(3). 将5入栈；(4). 接下来是×运算符，因此弹出5和7，计算出7×5=...
数据结构学习--逆波兰表达式
数据结构学习--逆波兰表达式一、前缀表达式（1）前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前 （2）举例说明： (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6前缀表达式的计算机求值从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素和次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果例如：(3+4) X 5-6对应的前缀表达式就是- X + 3 4 5 6, 针对前缀表达式求值步骤如下： 1. 从右至左扫描，将6、5、4、3压入堆栈 2. 遇到+运算符，因...
数据结构学习--栈实现综合计算器（中缀表达式）
数据结构学习--栈实现综合计算器（中缀表达式）使用栈来实现综合计算器思路图解使用栈完成表达式的计算 思路通过一个 index 值（索引），来遍历我们的表达式如果我们发现是一个数字,就直接入数栈如果发现扫描到是一个符号, 就分如下情况3.1 如果发现当前的符号栈为 空，就直接入栈3.2 如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符， 就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈， 如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.当表达式扫描完毕，就顺序的从 数栈和符号栈...
数据结构学习--栈（一）
数据结构学习--栈（一）一、栈的一个实际需求请输入一个表达式计算式:[7*2*2-5+1-5+3-3] 点击计算【如下图】请问: 计算机底层是如何运算得到结果的？ 注意不是简单的把算式列出运算,因为我们看这个算式 7 2 2 - 5, 但是计算机怎么理解这个算式的(对计算机而言，它接收到的就是一个字符串)，我们讨论的是这个问题。-> 栈二、栈的介绍（1）栈的英文为(stack)（2）栈是一个先入后出(FILO-First In Last Out)的有序列表。（3）栈（stack）是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化...
数据结构学习--单向环形链表
数据结构学习--单向环形链表一、单向环形链表的应用场景Josephu(约瑟夫、约瑟夫环) 问题Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。二、单向环...