Java数据结构和算法

2022/9/10 1:23:07

本文主要是介绍Java数据结构和算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一、简介

编程好比是一辆汽车,而数据结构和算法是汽车内部的变速箱。一个开车的人不懂变速箱的原理也是能开车的,同理一个不懂数据结构和算法的人也能编程。但是如果一个开车的人懂变速箱的原理,比如降低速度来获得更大的牵引力,或者通过降低牵引力来获得更快的行驶速度。那么爬坡时使用1档,便可以获得更大的牵引力;下坡时便使用低档限制车的行驶速度。回到编程而言,比如将一个班级的学生名字要临时存储在内存中,你会选择什么数据结构来存储,数组还是ArrayList,或者HashSet,或者别的数据结构。如果不懂数据结构的,可能随便选择一个容器来存储,也能完成所有的功能,但是后期如果随着学生数据量的增多,随便选择的数据结构肯定会存在性能问题,而一个懂数据结构和算法的人,在实际编程中会选择适当的数据结构来解决相应的问题,会极大的提高程序的性能。

1.1 数据结构

数据结构是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。

通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

1.1.1 数据结构的基本功能

①、如何插入一条新的数据项
②、如何寻找某一特定的数据项
③、如何删除某一特定的数据项
④、如何迭代的访问各个数据项,以便进行显示或其他操作

1.1.2 常用的数据结构

对于数组,你们所说的查找快,我想只是随机查找快,因为知道数组下标,可以按索引获取任意值。

但是你要查找某个特定值,对于无序数组,还是需要遍历整个数组,那么查找效率是`O(n)·,效率是很低的(有序数组按照二分查找算法还是很快的)。

插入快,是在数组尾部进行插入,获取到数组的最后一个索引下标,加1进行赋值就可以了。

删除慢,除开尾部删除,在任意中间或者前面删除,后面的元素都要整体进行平移的,所以也是比较慢的。

综上所述:对于数组,随机查找快,数组尾部增删快,其余的操作效率都是很低的。

20171124223229656-408723583.png

1.2 算法

算法简单来说就是解决问题的步骤。

Java中,算法通常都是由类的方法来实现的。前面的数据结构,比如链表为啥插入、删除快,而查找慢,平衡的二叉树插入、删除、查找都快,这都是实现这些数据结构的算法所造成的。后面我们讲的各种排序实现也是算法范畴的重要领域。

1.2.1 算法的五个特征

①、有穷性:对于任意一组合法输入值,在执行又穷步骤之后一定能结束,即:算法中的每个步骤都能在有限时间内完成。
②、确定性:在每种情况下所应执行的操作,在算法中都有确切的规定,使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下,算法都只有一条执行路径。
③、可行性:算法中的所有操作都必须足够基本,都可以通过已经实现的基本操作运算有限次实现之。
④、有输入:作为算法加工对象的量值,通常体现在算法当中的一组变量。有些输入量需要在算法执行的过程中输入,而有的算法表面上可以没有输入,实际上已被嵌入算法之中。
⑤、有输出:它是一组与“输入”有确定关系的量值,是算法进行信息加工后得到的结果,这种确定关系即为算法功能。

1.2.2 算法的设计原则

①、正确性:首先,算法应当满足以特定的“规则说明”方式给出的需求。其次,对算法是否“正确”的理解可以有以下四个层次:

一、程序语法错误。
二、程序对于几组输入数据能够得出满足需要的结果。
三、程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果。
四、程序对于一切合法的输入数据都能得到满足要求的结果。

PS:通常以第层意义的正确性作为衡量一个算法是否合格的标准。

②、可读性:算法为了人的阅读与交流,其次才是计算机执行。因此算法应该易于人的理解;另一方面,晦涩难懂的程序易于隐藏较多的错误而难以调试。
③、健壮性:当输入的数据非法时,算法应当恰当的做出反应或进行相应处理,而不是产生莫名其妙的输出结果。并且,处理出错的方法不应是中断程序执行,而是应当返回一个表示错误或错误性质的值,以便在更高的抽象层次上进行处理。
④、高效率与低存储量需求:通常算法效率值得是算法执行时间;存储量是指算法执行过程中所需要的最大存储空间,两者都与问题的规模有关。

前面三点正确性,可读性和健壮性相信都好理解。对于第四点算法的执行效率和存储量,我们知道比较算法的时候,可能会说“A算法比B算法快两倍”之类的话,但实际上这种说法没有任何意义。

因为当数据项个数发生变化时,A算法和B算法的效率比例也会发生变化,比如数据项增加了50%,可能A算法比B算法快三倍,但是如果数据项减少了50%,可能A算法和B算法速度一样。

所以描述算法的速度必须要和数据项的个数联系起来。也就是“大O”表示法,它是一种算法复杂度的相对表示方式,这里我简单介绍一下,后面会根据具体的算法来描述。

  • 相对(relative):你只能比较相同的事物。你不能把一个做算数乘法的算法和排序整数列表的算法进行比较。但是,比较2个算法所做的算术操作(一个做乘法,一个做加法)将会告诉你一些有意义的东西;
  • 表示(representation):大O(用它最简单的形式)把算法间的比较简化为了一个单一变量。这个变量的选择基于观察或假设。例如,排序算法之间的对比通常是基于比较操作(比较2个结点来决定这2个结点的相对顺序)。这里面就假设了比较操作的计算开销很大。但是,如果比较操作的计算开销不大,而交换操作的计算开销很大,又会怎么样呢?这就改变了先前的比较方式;
  • 复杂度(complexity):如果排序10,000个元素花费了我1秒,那么排序1百万个元素会花多少时间?在这个例子里,复杂度就是相对其他东西的度量结果。

然后我们在说说算法的存储量,包括:

  • 程序本身所占空间;
  • 输入数据所占空间;
  • 辅助变量所占空间;

一个算法的效率越高越好,而存储量是越低越好。

二、抽象数据类型(ADT)

在介绍抽象数据类型的时候,我们先看看什么是数据类型,听到这个词,在Java中我们可能首先会想到像int,double这样的词,这是Java中的基本数据类型,一个数据类型会涉及到两件事:

①、拥有特定特征的数据项
②、在数据上允许的操作

比如Java中的int数据类型,它表示整数,取值范围为:-2147483648~2147483647,还能使用各种操作符,+、-、*、/等对其操作。数据类型允许的操作是它本身不可分离的部分,理解类型包括理解什么样的操作可以应用在该类型上。

那么当年设计计算机语言的人,为什么会考虑到数据类型?

我们先看这样一个例子,比如,大家都需要住房子,也都希望房子越大越好。但显然,没有钱,考虑房子没有意义。于是就出现了各种各样的商品房,有别墅的、复式的、错层的、单间的……甚至只有两平米的胶囊房间。这样做的意义是满足不同人的需要。

同样,在计算机中,也存在相同的问题。计算1+1这样的表达式不需要开辟很大的存储空间,不需要适合小数甚至字符运算的内存空间。于是计算机的研究者们就考虑,要对数据进行分类,分出来多种数据类型。比如int,比如float

虽然不同的计算机有不同的硬件系统,但实际上高级语言编写者才不管程序运行在什么计算机上,他们的目的就是为了实现整形数字的运算,比如a+b等。他们才不关心整数在计算机内部是如何表示的,也不管CPU是如何计算的。于是我们就考虑,无论什么计算机、什么语言都会面临类似的整数运算,我们可以考虑将其抽象出来。抽象是抽取出事物具有的普遍性本质,是对事物的一个概括,是一种思考问题的方式。

抽象数据类型(ADT)是指一个数学模型及定义在该模型上的一组操作。它仅取决于其逻辑特征,而与计算机内部如何表示和实现无关。比如刚才说得整型,各个计算机,不管大型机、小型机、PC、平板电脑甚至智能手机,都有“整型”类型,也需要整形运算,那么整型其实就是一个抽象数据类型。

更广泛一点的,比如我们刚讲解的栈和队列这两种数据结构,我们分别使用了数组和链表来实现,比如栈,对于使用者只需要知道pop()push()方法或其它方法的存在以及如何使用即可,使用者不需要知道我们是使用的数组或是链表来实现的。

ADT的思想可以作为我们设计工具的理念,比如我们需要存储数据,那么就从考虑需要在数据上实现的操作开始,需要存取最后一个数据项吗?还是第一个?还是特定值的项?还是特定位置的项?回答这些问题会引出ADT的定义,只有完整的定义了ADT后,才应该考虑实现的细节。

这在我们Java语言中的接口设计理念是相通的。

三、前缀、中缀、后缀表达式

前面我们介绍了三种数据结构,第一种数组主要用作数据存储,但是后面的两种栈和队列我们说主要作为程序功能实现的辅助工具,其中在介绍栈时我们知道栈可以用来做单词逆序,匹配关键字符等等,那它还有别的什么功能吗?以及数据结构与本篇博客的主题前缀、中缀、后缀表达式有什么关系呢?

3.1 人如何解析算术表达式

如何解析算术表达式?或者换种说法,遇到某个算术表达式,我们是如何计算的:

①、求值3+4-5

这个表达式,我们在看到3+4后都不能直接计算3+4的值,知道看到4后面的-号,因为减号的优先级和前面的加号一样,所以可以计算3+4的值了,如果4后面是*或者/,那么就要在乘除过后才能做加法操作,比如:

②、求值3+4*5

这个不能先求3+4的值,因为4后面的*运算级别比前面的+高。通过这两个表达式的说明,我们可以总结解析表达式的时候遵循的几条规则:

①、从左到右读取算式。
②、已经读到了可以计算值的两个操作数和一个操作符时,可以计算,并用计算结果代替那两个操作数和一个操作符。
③、继续这个过程,从左到右,能算就算,直到表达式的结尾。

3.2 计算机如何解析算术表达式

对于前面的表达式3+4-5,我们人是有思维能力的,能根据操作符的位置,以及操作符的优先级别能算出该表达式的结果。但是计算机怎么算?

计算机必须要向前(从左到右)来读取操作数和操作符,等到读取足够的信息来执行一个运算时,找到两个操作数和一个操作符进行运算,有时候如果后面是更高级别的操作符或者括号时,就必须推迟运算,必须要解析到后面级别高的运算,然后回头来执行前面的运算。我们发现这个过程是极其繁琐的,而计算机是一个机器,只认识高低电平,想要完成一个简单表达式的计算,我们可能要设计出很复杂的逻辑电路来控制计算过程,那更不用说很复杂的算术表达式,所以这样来解析算术表达式是不合理的,那么我们应该采取什么办法呢?

请大家先看看什么是前缀表达式,中缀表达式,后缀表达式:这三种表达式其实就是算术表达式的三种写法,以3+4-5为例

①、前缀表达式:操作符在操作数的前面,比如+-543
②、中缀表达式:操作符在操作数的中间,这也是人类最容易识别的算术表达式3+4-5
③、后缀表达式:操作符在操作数的后面,比如34+5-

上面我们讲的人是如何解析算术表达式的,也就是解析中缀表达式,这是人最容易识别的,但是计算机不容易识别,计算机容易识别的是前缀表达式和后缀表达式,将中缀表达式转换为前缀表达式或者后缀表达式之后,计算机能很快计算出表达式的值,那么中缀表达式是如何转换为前缀表达式和后缀表达式,以及计算机是如何解析前缀表达式和后缀表达式来得到结果的呢?

3.3 后缀表达式

后缀表达式,指的是不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则)。

由于后缀表达式的运算符在两个操作数的后面,那么计算机在解析后缀表达式的时候,只需要从左向右扫描,也就是只需要向前扫描,而不用回头扫描,遇到运算符就将运算符放在前面两个操作符的中间(这里先不考虑乘方类似的单目运算),一直运算到最右边的运算符,那么就得出运算结果了。既然后缀表达式这么好,那么问题来了:

①、如何将中缀表达式转换为后缀表达式?

对于这个问题,转换的规则如下:

一、先自定义一个栈

package com.ys.poland;
 
public class MyCharStack {
    private char[] array;
    private int maxSize;
    private int top;
     
    public MyCharStack(int size){
        this.maxSize = size;
        array = new char[size];
        top = -1;
    }
     
    //压入数据
    public void push(char value){
        if(top < maxSize-1){
            array[++top] = value;
        }
    }
     
    //弹出栈顶数据
    public char pop(){
        return array[top--];
    }
     
    //访问栈顶数据
    public char peek(){
        return array[top];
    }
     
    //查看指定位置的元素
    public char peekN(int n){
        return array[n];
    }
     
    //为了便于后面分解展示栈中的内容,我们增加了一个遍历栈的方法(实际上栈只能访问栈顶元素的)
    public void displayStack(){
        System.out.print("Stack(bottom-->top):");
        for(int i = 0 ; i < top+1; i++){
            System.out.print(peekN(i));
            System.out.print(' ');
        }
        System.out.println("");
    }
     
    //判断栈是否为空
    public boolean isEmpty(){
        return (top == -1);
    }
     
    //判断栈是否满了
    public boolean isFull(){
        return (top == maxSize-1);
    }
 
}

二、前缀表达式转换为后缀表达式

package com.ys.poland;
 
public class InfixToSuffix {
    private MyCharStack s1;//定义运算符栈
    private MyCharStack s2;//定义存储结果栈
    private String input;
     
    //默认构造方法,参数为输入的中缀表达式
    public InfixToSuffix(String in){
        input = in;
        s1 = new MyCharStack(input.length());
        s2 = new MyCharStack(input.length());
    }
    //中缀表达式转换为后缀表达式,将结果存储在栈中返回,逆序显示即后缀表达式
    public MyCharStack doTrans(){
        for(int j = 0; j < input.length(); j++){
            System.out.print("s1栈元素为:");
            s1.displayStack();
            System.out.print("s2栈元素为:");
            s2.displayStack();
            char ch = input.charAt(j);
            System.out.println("当前解析的字符:"+ch);
            switch (ch) {
            case '+':
            case '-':
                gotOper(ch,1);
                break;
            case '*':
            case '/':
                gotOper(ch,2);
                break;
            case '(':
                s1.push(ch);//如果当前字符是'(',则将其入栈
                break;
            case ')':
                gotParen(ch);
                break;
            default:
                //1、如果当前解析的字符是操作数,则直接压入s2
                //2、
                s2.push(ch);
                break;
            }//end switch
        }//end for
         
        while(!s1.isEmpty()){
            s2.push(s1.pop());
        }
        return s2;
    }
     
    public void gotOper(char opThis,int prec1){
        while(!s1.isEmpty()){
            char opTop = s1.pop();
            if(opTop == '('){//如果栈顶是'(',直接将操作符压入s1
                s1.push(opTop);
                break;
            }else{
                int prec2;
                if(opTop == '+' || opTop == '-'){
                    prec2 = 1;
                }else{
                    prec2 = 2;
                }
                if(prec2 < prec1){//如果当前运算符比s1栈顶运算符优先级高,则将运算符压入s1
                    s1.push(opTop);
                    break;
                }else{//如果当前运算符与栈顶运算符相同或者小于优先级别,那么将S1栈顶的运算符弹出并压入到S2中
                    //并且要再次再次转到while循环中与 s1 中新的栈顶运算符相比较;
                    s2.push(opTop);
                }
            }
             
        }//end while
        //如果s1为空,则直接将当前解析的运算符压入s1
        s1.push(opThis);
    }
     
    //当前字符是 ')' 时,如果栈顶是'(',则将这一对括号丢弃,否则依次弹出s1栈顶的字符,压入s2,直到遇到'('
    public void gotParen(char ch){
        while(!s1.isEmpty()){
            char chx = s1.pop();
            if(chx == '('){
                break;
            }else{
                s2.push(chx);
            }
        }
    }
}

三、测试

@Test
public void testInfixToSuffix(){
    String input;
    System.out.println("Enter infix:");
    Scanner scanner = new Scanner(System.in);
    input = scanner.nextLine();
    InfixToSuffix in = new InfixToSuffix(input);
    MyCharStack my = in.doTrans();
    my.displayStack();
}

四、结果

五、分析

②、计算机如何实现后缀表达式的运算?

package com.ys.poland;
 
public class CalSuffix {
    private MyIntStack stack;
    private String input;
     
    public CalSuffix(String input){
        this.input = input;
        stack = new MyIntStack(input.length());
         
    }
     
    public int doCalc(){
        int num1,num2,result;
        for(int i = 0; i < input.length(); i++){
            char c = input.charAt(i);
            if(c >= '0' && c <= '9'){
                stack.push((int)(c-'0'));//如果是数字,直接压入栈中
            }else{
                num2 = stack.pop();//注意先出来的为第二个操作数
                num1 = stack.pop();
                switch (c) {
                case '+':
                    result = num1+num2;
                    break;
                case '-':
                    result = num1-num2;
                    break;
                case '*':
                    result = num1*num2;
                    break;
                case '/':
                    result = num1/num2;
                    break;
                default:
                    result = 0;
                    break;
                }//end switch
                 
                stack.push(result);
            }//end else
        }//end for
        result = stack.pop();
        return result;
    }
     
    public static void main(String[] args) {
        //中缀表达式:1*(2+3)-5/(2+3) = 4
        //后缀表达式:123+*123+/-
        CalSuffix cs = new CalSuffix("123+*523+/-");
        System.out.println(cs.doCalc()); //4
    }
}

3.4 前缀表达式

前缀表达式,指的是不包含括号,运算符放在两个运算对象的前面,严格从右向左进行(不再考虑运算符的优先规则),所有的计算按运算符出现的顺序。

注意:后缀表达式是从左向右解析,而前缀表达式是从右向左解析。

①、如何将中缀表达式转换为前缀表达式?

②、计算机如何实现前缀表达式的运算?

参考

  • 数据结构和算法


这篇关于Java数据结构和算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程