关键词:
为一个特定的任务选择最好的数据结构和算法是开发高性能软件的一个关键。
数据结构是以某种形式将数据组织在一起的集合(collection)。数据结构不仅存储数据,还支持访问和处理数据的操作。
在面向对象思想里,一种数据结构也被认为是一个容器(container)或者容器对象(container object),它是一个能存储其他对象(常称为数据或元素)的对象。定义一种数据结构从本质上讲就是定义一个类。数据结构应该使用数据域存储数据,并提供方法支持查找,插入和删除等操作。因此,创建一个数据结构就是创建这个类的一个实例。然后可以使用这个实例上的方法来操作这个数据结构,例如,向该数据结构中插入一个元素,或者从这个数据结构中删除一个元素。
java提供了很多能有效组织和操作数据的数据结构。这些数据结构 通常称为java集合框架(Java Conllections Framework)。
collection接口为线性表、向量、栈、队列,优先队列以及集合定义了共同的操作。
Java集合框架支持以下两种类型的容器:
一种是为了存储一个元素集合,简称为集合(collection)
另一种是为了存储键/值对,称为映射表(map)
现在我们把注意力集中在以下集合上,键值对后续再做介绍
List用于存储一个有序元素集合。
Set用于存储一组不重复的元素。
Stack用于存储采用后进先出方式处理的对象。
Queue用于存储采用先进先出方式处理的对象。
Priority Queue用于存储按照优先级顺序处理的对象。
这些集合的通用特性再接口中定义,而实现在具体类中提供。
Collection接口是处理对象集合的根接口,公共方法如下
注:方法addAll、removeAll、retainAll类似于集合上的并、差、交运算。
注:Collection接口中的有些方法是不能再具体子类中实现的。再这种情况下,这些方法会抛出异常java.lang.UnsupportedOperationException,它是RuntimeException异常类的一个子类。这样设计很好,可以在自己的项目中使用。如果一个方法在子类中没有意义,可以按如下方式实现它:
pub1ic void someMethod() throw new UnsupportedOperationException("Method not supported");
迭代器
每种集合都是可迭代的(Iterable)。可以获得集合的Iterator对象来遍历集合中的所有元素。
Iterator是一种经典的设计模式,用于在不需要暴露数据是如何保存在数据结构的细节的情况下,来遍历一种数据结构。
线性表
List接口继承自Collection,定义了一个用于顺序存储元素的集合。可以使用它的两个具体类ArrayList和LinkedList来创建一个线性表
Comparator接口
线性表和集合的静态方法
向量类和栈类
队列和优先队列
示例:表达式求值
/** * 使用两个栈(operandStack,operatorStack)分别存放操作数和操作符 * 阶段1:扫描表达式 ,(15+2)*5-23,从左到右扫描表达式,提取出操作数和操作符以及括号 * 1.如果提取的是操作数,则将其压入operandStack。 * 2.如果提取的是+或者-号运算符,处理operatorStack栈顶所有的运算符,并将提取到的运算符压入到operatorStack * 3.如果提取的是*或者/号运算符,处理operatorStack栈顶所有的*和/运算符,并将提取到的运算符压入到operatorStack * 4.如果提取的是(,将提取到的运算符压入到operatorStack。 * 5.如果提取的是),重复处理来自operatorStack栈顶的运算符,直到遇到(为止。 * 阶段2:清除栈 * 重复处理来自operatorStack栈顶的运算符,直到operatorStack栈为空 * * */ public class EvaluateExpression public static void main(String[] args) System.out.println("请输入一个整数的简单运算表达式,比如:( 15 + 2 ) * 5 - 23"); Scanner input = new Scanner(System.in); String expression = input.nextLine(); int ret = evaluateExpression(expression); System.out.println(expression + " = " + ret); input.close(); /** * 计算表达式 * @param expression 表达式 * @return 结果 */ public static int evaluateExpression(String expression) //创建operandStack存储操作数 Stack<Integer> operandStack = new Stack<>(); //创建operatorStack存储操作符 Stack<Character> operatorStack = new Stack<>(); //在表达式的操作符前后 添加空格,以便于提取操作数和操作符 expression = insertBlanks(expression); //提取操作数及操作符 String[] tokens = expression.split(" "); //阶段1:扫描表达式 for(String token : tokens) if(token.length() == 0) continue;//如果为 else if(token.charAt(0) == ‘+‘ || token.charAt(0) == ‘-‘ ) //处理运算符栈顶的所有+,-,*,/ while(!operatorStack.isEmpty() && ( operatorStack.peek() == ‘+‘ || operatorStack.peek() == ‘-‘ || operatorStack.peek() == ‘*‘ || operatorStack.peek() == ‘/‘)) processAnOperator(operandStack,operatorStack); //将+或者-压入operatorStack operatorStack.push(token.charAt(0)); else if (token.charAt(0) == ‘*‘ || token.charAt(0) == ‘/‘ ) while(!operatorStack.isEmpty() && ( operatorStack.peek() == ‘*‘ || operatorStack.peek() == ‘/‘)) processAnOperator(operandStack,operatorStack); operatorStack.push(token.charAt(0)); else if (token.trim().charAt(0) == ‘(‘) operatorStack.push(‘(‘); else if(token.trim().charAt(0) == ‘)‘) while(!operatorStack.isEmpty() && ( operatorStack.peek() != ‘(‘)) processAnOperator(operandStack,operatorStack); operatorStack.pop();//弹出( else operandStack.push(Integer.valueOf(token)); //阶段2:清空栈 while(!operatorStack.isEmpty()) processAnOperator(operandStack,operatorStack); return operandStack.pop(); /** * 在表达式的操作符前后 添加空格,以便于提取操作数和操作符 * @param expression 表达式 * @return 添加空格后的表达式 */ private static String insertBlanks(String expression) String result = ""; for(int i = 0; i < expression.length(); i++) if(expression.charAt(i) == ‘(‘ || expression.charAt(i) == ‘)‘ || expression.charAt(i) == ‘+‘ || expression.charAt(i) == ‘-‘ || expression.charAt(i) == ‘*‘ || expression.charAt(i) == ‘/‘) result += " " + expression.charAt(i) + " "; else result += expression.charAt(i) ; return result; private static void processAnOperator(Stack<Integer> operandStack,Stack<Character> operatorStack) char op = operatorStack.pop(); int num1 = operandStack.pop(); int num2 = operandStack.pop(); if(op == ‘+‘) operandStack.push(num2 + num1); else if(op == ‘-‘) operandStack.push(num2 - num1); else if(op == ‘*‘) operandStack.push(num2 * num1); else if(op == ‘/‘) operandStack.push(num2 / num1);
编程练习题:
1.(按字母升序显示单词)编写一个程序,从文本文件读取单词,并按字母的升序显示所有的单词(可重复)。单词必须以字母开始。
2.编写一个测试程序,在一个链表上存储500万个整数,分别使用iterator和get(index)的遍历时间。
3.编程实现编组符号对
圆括号:(和)
花括号:和
方括号:[和]
注意:符号不能交错,编写程序检测编组符号是否正确匹配。
4
顺序表栈与队列(代码片段)
一、顺序表引入1什么是线性表1在程序中,经常需要将一组数据元素作为整体管理和使用,需要创建这种元素组,用变量记录它们,传进传出函数等。2一组数据中包含的元素个数可能发生变化(增加或删除元素)。3对于这种需... 查看详情
22计算机408考研—数据结构—线性表栈队列数组(代码片段)
2022计算机考研408—数据结构—线性表、栈、队列、数组手把手教学考研大纲范围内的线性表、栈、队列、数组22考研大纲数据结构要求的是C/C++,笔者以前使用的都是Java,对于C++还很欠缺,如有什么建议... 查看详情
22计算机408考研—数据结构—线性表栈队列数组(代码片段)
2022计算机考研408—数据结构—线性表、栈、队列、数组手把手教学考研大纲范围内的线性表、栈、队列、数组22考研大纲数据结构要求的是C/C++,笔者以前使用的都是Java,对于C++还很欠缺,如有什么建议... 查看详情
线性表栈和队列
一、线性表(list)1、定义:有序、有限的数据序列,其中的每个数据称为元素(element)。 注:在这里本文中所指的元素的数据类型相同。2、基本概念:空(empty)、长度(length)、头(head)、尾(tail)、有序表(sortedlist... 查看详情
22计算机408考研—数据结构—线性表栈队列数组(代码片段)
2022计算机考研408—数据结构—线性表、栈、队列、数组手把手教学考研大纲范围内的线性表、栈、队列、数组22考研大纲数据结构要求的是C/C++,笔者以前使用的都是Java,对于C++还很欠缺,如有什么建议... 查看详情
22计算机408考研—数据结构—线性表栈队列数组(代码片段)
2022计算机考研408—数据结构—线性表、栈、队列、数组手把手教学考研大纲范围内的线性表、栈、队列、数组22考研大纲数据结构要求的是C/C++,笔者以前使用的都是Java,对于C++还很欠缺,如有什么建议... 查看详情
表栈和队列(代码片段)
目录1、抽象数据类型2、表ADT2.1、表的简单数组实现2.2、简单链表3、JavaCollectionsAPI中的表3.1、Collection接口3.2、Iterator接口3.3、List接口、ArrayList类和LinkedList类3.4、例子:remove方法对LinkedList类的应用3.5、关于ListInterator本系列讨论... 查看详情
线性表--08---优先队列(代码片段)
文章目录优先队列背景:分类:1.最大优先队列树--07---堆的实现最大优先队列API设计代码实现测试:2.最小优先队列最大堆最小堆最小优先队列API设计代码实现测试:3.索引优先队列实现思路步骤一:步骤二:步骤三:方法q... 查看详情
数据结构--栈队列树(代码片段)
文章目录线性表栈队列二叉树线性表线性表是一种可以在任意位置进行插入和删除数据元素操作的、由n(n>=0)个相同类型数据元素a0、a1、a2,…,a(n-1)组成的线性结构。线性表是一种最简单的线性结构。特点:除... 查看详情
[datastructure]线性数据结构之稀疏数组链表栈和队列java代码实现
线性数据结构线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。相对应于线性结构,非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后继。线性数据结构具有以下特征:1.... 查看详情
[datastructure]线性数据结构之稀疏数组链表栈和队列java代码实现
线性数据结构线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。相对应于线性结构,非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后继。线性数据结构具有以下特征:1.... 查看详情
第二章之线性表栈队列和线性表
线性表的存储结构(主要有两种):1、定长的顺序存储结构,也称顺序表或向量型的一维数组结构。数据结点之间的逻辑关系是通过数据结点的存储位置来反映的。2、边长的线性结构存储结构、大多实现为链接式存储结构。数... 查看详情
线性表--优先队列(代码片段)
目录前言一、优先队列简介二、优先队列的适用场景三、优先队列的实现方式四、二叉堆实现的优先队列4.1二叉堆的定义4.2二叉堆的基本操作4.3优先队列的基本操作4.4手写二叉堆实现优先队列4.5使用heapq模块实现优先队列总结... 查看详情
堆和优先队列(代码片段)
什么是优先队列???我们在常见的线性结构中,已经知道什么是普通队列了,普通队列就是一种“先进先出,后进后出”的数据结构,即普通队列的出队顺序和入队顺序是一样的,但我们的优先队列,它的出队顺序和入队顺序无关... 查看详情
栈和队列
PS:栈和队列其实也是一种线性表栈是限定只能只能在队尾进行插入和删除的线性表队列是只允许在一段插入、另一端进行删除的线性表。=================栈的顺序存储结构============================================两栈共享空间=================... 查看详情
优先队列和堆(代码片段)
什么是优先队列? 优先队列也是一种队列,只不过不同的是,优先队列的出队顺序是按照优先级来的;在有些情况下,可能需要找到元素集合中的最小或者最大元素,可以利用优先队列ADT来完成操作,优先队列ADT是一种数据... 查看详情
数据结构复习--栈和队列--栈(代码片段)
...的两种数据结构,在软件设计中应用很多。栈和队列也是线性结构,线性表,栈和队列这三种数据元素和数据元素间的逻辑完全相同。差别是线性表的操作不受限制,而栈和队列的操作收到限制,栈的操作只能在表的一端进行,队列... 查看详情
堆和优先级队列2:java实现堆和优先级队列(代码片段)
1.什么是优先级队列在C++和java等库中,都提供了优先级队列这个容器,java中的优先级队列是PriorityQueue。其实底层就是一个堆的结构,只不过将堆封装了一层而已。其实名字叫个优先级队列,但总觉得和队列... 查看详情