数据结构与算法_javascript数据结构与算法,比如排序算法,递归算法 - CSDN
数据结构与算法 订阅
《数据结构与算法》是2013年人民邮电出版社出版的图书,作者是彭军、向毅。 展开全文
《数据结构与算法》是2013年人民邮电出版社出版的图书,作者是彭军、向毅。
信息
页    数
250页
作    者
彭军、向毅
定    价
34.00元
装    帧
平装
书    名
数据结构与算法
出版时间
2013年1月
开    本
16开
出版社
人民邮电出版社
ISBN
978-7-115-28770-0
数据结构与算法内容简介
本书是国家级双语教学示范课程《数据结构》的配套教材,根据教育部高等学校计算机科学与技术教学指导委员会制定的《高等学校计算机科学与技术专业发展战略研究报告暨专业规范》编写。全书每章均以数据的逻辑结构、存储结构和相应的算法实现为主线,并对算法的运算效率进行分析。全书分为8章,涵盖了各种常见数据结构。第1章主要介绍数据结构和算法分析的基本概念,第2~6章主要介绍典型的线性结构、树型结构和图型结构,第7~8章分别介绍查找和排序操作。  另外,每章后面附有习题和上机实验内容,上机实验提供了完整的、可运行的程序上机实验供读者参考,以加深读者对所学知识的理解和应用。  本书既可作为高等院校计算机及相关专业数据结构课程的教学用书,也可作为从事计算机工程与应用的广大读者的参考书。该书是国家级双语教学示范课程配套教材,以基本数据结构和算法设计策略为知识单元,系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法,主要内容包括线性表、树、图和广义表、算法设计策略以及查找与排序算法等。《数据结构与算法》注重理论与实践相结合,内容深入浅出,可以作为高等院校计算机学科相关专业的教材或参考书,同时对计算机科技工作者也有参考价值。
收起全文
精华内容
参与话题
  • 数据结构:是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、(存储)物理结构和数据的运算三个部分。 为什么要学数据结构? 首先,因为数据结构作为...

    系列文章

    第一章:基础知识

    第二章:线性表

    第三章:栈和队列 

    第四章:字符串和数组

    第五章:树和二叉树

    第六章:图

    第七章:排序算法


    前言

    数据结构:是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、(存储)物理结构和数据的运算三个部分

    为什么要学数据结构?

    首先,因为数据结构作为计算机专业的专业基础课程,是计算机考研的必考科目之一,如果打算报考计算机专业的研究生,你必须学好它;其次,数据结构是计算机软考、计算机等级考试等相关考试的必考内容之一,想要顺利通过这些考试,你也必须学好它;最后,数据结构还是你打算今后学习计算专业其他课程的基础,如操作系统、编辑原理、数据库管理系统、软件工程、人工智能等。总而言之,你既然已经与计算机接轨就必须掌握好它。

    如何学习数据结构?

    对于初学者来说,数据结构是门概念上比较抽象的课程,不是太容易掌握,需要构思和理解。万事开头难,只要你掌握了学习这门课的方法和技巧,就会变得很容易了。不管学什么,首先应该做好充分的心理准备,建立好自信心,拥有一颗战胜困难的决心,才能不畏惧、不退缩,直至胜利归来。其次,就是最好有C语言基础,这样学起来事半功倍,当然没有C语言基础也行,可以一边学数据结构一边巩固C语言知识。最后,就是多动手!多动手!多动手!重要的事情说三遍!只有亲自动手上机操作或用笔在纸上画画写写才能加深映像,方便理解记忆。?


    第一章:基础知识

    第1节:数据结构概述

      1.1 概念术语

      1.2数据的逻辑结构

      1.3数据的存储(物理)结构

      1.4抽象数据类型

      1.5算法

    1.6时间复杂度

    1.7空间复杂度

    第2节:C语言基础

    2.1 开发环境

    2.2 递归与非递归(重点)

    2.3参数传递

    2.4 结构体和联合体

    2.5 链表

    2.6 内存的分配与释放


     

    第1节:数据结构概述

    数据结构的主要任务是通过分析数据对象的结构特征,包括逻辑结构及数据对象之间的关系,然后把逻辑结构表示成计算机课实现的物理结构,从而便于计算机处理。

     

      1.1 概念术语

    (1)数据(Data)是能被计算机处理的符号或符号集合,含义广泛,可理解为“原材料”。如字符、图片、音视频等。

    (2)数据元素(data element)是数据的基本单位。例如一张学生统计表。

    (3)数据项(data item)组成数据元素的最小单位。例如一张学生统计表,有编号、姓名、性别、籍贯等数据项。

    (4)数据对象(data object)是性质相同的数据元素的集合,是数据的一个子集。例如正整数N={1,2,3,····}。

    (5)数据结构(data structure)是数据的组织形式,数据元素之间存在的一种或多种特定关系的数据元素集合。

    (6)数据类型(data type)是按照数据值的不同进行划分的可操作性。在C语言中还可以分为原子类型和结构类型。原字类型是不可以再分解的基本类型,包括整型、实型、字符型等。结构类型是由若干个类型组合而成,是可以再分解的。

     

      1.2数据的逻辑结构

    逻辑结构(logical structure)是指在数据中数据元素之间的相互关系。数据元素之间存在不同的逻辑关系构成了以下4种结构类型。

    (1)集合结构:集合的数据元素没有其他关系,仅仅是因为他们挤在一个被称作“集合”的盒子里。

    (2)线性结构:线性的数据元素结构关系是一对一的,并且是一种先后的次序,就像a-b-c-d-e-f-g·····被一根线穿连起来。

    (3)树形结构:树形的数据元素结构关系是一对多的,这就像公司的部门级别,董事长-CEO\CTO-技术部\人事部\市场部.....。

    (4)图结构:图的数据元素结构关系是多对多的。就是我们常见的各大城市的铁路图,一个城市有很多线路连接不同城市。

     

      1.3数据的存储(物理)结构

    存储结构(storage structure)也称为物理结构(physical structure),指的是数据的逻辑结构在计算机中的存储形式。数据的存储结构一般可以反映数据元素之间的逻辑关系。分为顺序存储结构和链式存储结构。

    (1)顺序存储结构:是把数据元素存放在一组存储地址连续的存储单元里,其数据元素间的逻辑关系和物理关系是一致的。

    (2)链式存储结果:是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的,数据元素的存储关系并不能反映其逻辑关系,因此需要借助指针来表示数据元素之间的逻辑关系。

     

    小结:数据的逻辑结构和物理结构是密切相关的,在学习数据的过程中会发现,任何一个算法的设计取决于选定的数据逻辑结构,而算法的实现依赖于所采用的存储结构。

     

      1.4抽象数据类型

    抽象数据类型(abstract data type,ADT)是描述具有某种逻辑关系的数据模型,并对在数学模型上进行的一组操作。抽象数据类型描述的是一组逻辑上的特性,与在计算机内部表示无关,计算机中的整数数据类型是一个抽象数据类型,不同处理器可能实现方法不同,但其逻辑特性相同,即加、减、乘、除等运算是一致的。“抽象”的意思是数据类型的数学抽象特性而不是指它们的实现方法。抽象数据类型体现了程序设计中的问题分解、抽象、信息隐藏等特性,可以把现实中的大问题分解为多个规模小且容易处理的小问题,然后建立起一个能被计算机处理的数据,并把每个功能模块的实现细节作为一个独立的单元,从而使具体实现过程隐藏起来。就类似建一栋房子,分成若干个小任务,如地皮规划、图纸设计、施工、装修等,整个过程与抽象数据类型中的问题分解类似。而搬砖人不需要了解图纸设计如何,设计图纸人员不需要了解施工的地基、砌墙的具体细节,装修工人不用关系图纸和搬砖过程,这就是抽象类型中的信息隐藏。

    抽象数据类型的概念可能让初学者不太容易理解。例如线性表的抽象数据类型的描述数据对象集合:线性表的数据对象集合为{a1,a2,a3,····,an},每个元素的类型均为DataType。其中,除了第一个元素a1外,每一个元素有且只有一个直接前驱元素;除了最后一个元素an外,每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的。

     

      1.5算法

    算法(algorithm)是解决特定问题求解步骤的描述,在计算机中表现为有限的操作序列。在数据类型建立起来之后,就要对这些数据类型进行操作,建立起运算的集合即程序。运算的建立、方法好坏直接决定着计算机程序原型效率的高低。

    (1)数据结构和算法的关系

    两者基友联系又有区别。联系是程序=算法+数据结构。数据结构是算法实现的基础,算法总是要依赖某种数据结构来实现的。算法的操作对象是数据结构。区别是数据结构关注的是数据的逻辑结构、存储结构有一集基本操作,而算法更多的是关注如何在数据结构的基本上解决实际问题。算法是编程思想,数据结构则是这些思想的基础。

    (2)算法的五大特性

    有穷性,是指算法在执行有限的步骤之后,自动结束而不是出现无限循环,并且每一个步骤在可接受的时间内完成。

    确定性,是指算法执行的每一步骤在一定条件下只有一条执行路径,也就是相同输入只能有一个唯一的输出结果。

    可行性,是指算法每一步骤都必须可行,能够通过有限的执行次数完成。

    输入,是指算法具有零个或多个输入。

    输出,是指算法至少有一个或多个输出。

     

    1.6时间复杂度

    在进行算法分析时,语句总是执行次数 T(n) 是关于问题规模 n 的函数。进而分析次数T(n)随规模n的变化情况并确定T(n)的数量级。算法的时间复杂度就是算法的时间度量,记作T(n) = O(f(n))。它表示随问题规模n的增大,算法的执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中,f(n)是问题规模n的某个函数。

    算法的时间复杂度是衡量一个算法好坏的重要指标。一般情况下,随着规模n的增大,次数T(n)的增长较慢的算法为最优算法。常见时间复杂度从小到大依次排列:O(1) < O(log2n) < O(n) < O(n²)<O(n³) ····<O(n!)

    例如:

    (a) 1;      // 时间复杂度为O(1)

    (b)for(i =1 ; i<=n ;i++){  x= x+1;}    // 时间复杂度为O(n),称为线性阶

    (c)for(i =1 ; i<=n ; i++){for(j=1;j<=n;j++){  x=x+1 } }  // 时间复杂度为O(n²),称为平方阶

     

    1.7空间复杂度

    空间复杂度(space complexity)作为算法所需存储空间的量度,记做S(n) = O (f(n))。其中,n为问题的规模;f(n)为语句关于n的所占存储空间的函数。

    一般情况下,一个程序在机器上运行时,除了需要存储程序本身的指令、常数、变量和输入数据外,还需要存储对数据操作的存储单位。若输入数据所占空间只取决于问题本身,和算法无关,这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常量,则称此算法为原地工作,空间复杂度为O(1)。

     

    第2节:C语言基础

    C语言作为数据结构的算法描述语言,广泛应用于系统软件和应用软件的开发。在真正开发学习数据结构知识之前,先复习一下C语言基础,为数据结构的学习扫清障碍。本节主要针对重点和难点部分详细讲解,包括开发环境、函数与递归、指针、参数传递、动态内存分配及结构体、联合体。

     

    2.1 开发环境

    C语言常见的开发环境有很多种,如LCC、Turbo C2.0、Visual C++、Borland C++,本章主要介绍使用最多的Turbo C 2.0和Visual C++ 6.0。

    (1)Turbo C 2.0 :1989年,美国Borland公司推出,简称TC。它集编辑、编译、连接和运行一体的C程序集成开发环境。界面简单、上手容易、使用方便,通过一个简单的主界面可以很容易编辑、编译和链接程序,也是初学者广发使用的开发工具。

    (2)Visual C++6.0:是强大的C/C++软件开发工具,使用非常广泛,已经成为首选的开发工具。利用它可以开发Windows SDK、MFC等应用程序。

     

    2.2 递归与非递归(重点)

    在数据结构与算法实践过程中,经常会遇到利用递归实现算法的情况。递归是一种分而治之、将复杂问题转换成简单问题的求解方法。使用递归可以使编写的程序简洁、结构清晰,程序的正确性很容易证明,不需要了解递归调用的具体细节。

    (1)函数的递归:就是函数自己调用自己,即一个函数在调用其他函数的过程中,又出现对自身的调用,这种函数称为递归函数。函数的递归调用就是自己调用自己,可以直接调用自己也可以间接调用。其中,在函数中直接调用自己称为函数的直接递归调用;如果函数f1调用了函数f2又再次调用了函数f1,这种调用的方式我们称之为间接递归调用。

    例1:利用递归求n! :有两种情况,当n=0递归结束,返回值为1 ;当n !=0时,继续递归。

    //递归求n!函数实现
    
    int factorial (int  n){
    
        if(n ==0 )
            return 1;
    
        else
            return n*factorial(n-1);
    }
    

      例2:已知有数组a[] ,要求利用递归实现求n个数中的最大值。

    a[] ={0,···,n-1};
    
    int findMax(int a[] ,int n){
    
        int  m ;
    
        if (n<=1)
            return a[0];
    
        else
        {
            m = findMax(a,n-1);
            return a[n-1] >= m ?a[n-1] : m ;//找到最大值
        }
    }

     

    (2)迭代与递归

    迭代与递归是程序设计中最常用的两种结构。任何能使用递归解决的问题都能使用迭代的方法解决。迭代和递归的区别是,迭代使用的是循环结构,递归使用的是选择结构。大量的递归会耗费大量的时间和内存,每次递归调用都会建立函数的一个备份,会占用大量的内存空间。迭代则不需要反复调用函数和占用额外的内存。对于较为简单的递归问题,可以利用简单的迭代将其转化为非递归。而对于较为复杂的递归问题,需要通过利用数据结构中的栈来消除递归。

    (3)指针

    是C语言中一个重要概念,也是最不容易掌握的内容。指针常常用在函数的参数传递和动态内存分配中。指针与数组相结合,使引用数组成分的形式更加多样化,访问数组元素的手段更加灵活;指针与结构体结合,利用系统提供的动态存储手段,能构造出各种复杂的动态数据结构;利用指针形参,使函数能实现传递地址形参和函数形参的要求。接下里会介绍指针变量的概念、指针与数组、函数指针与指针函数。

    指针是一种变量,也称之为指针变量,它的值不少整数、浮点数和字符,而是内存地址。指针的值就是变量的地址,而变量又拥有一个具体的值。因此,可以理解为变量名直接引用了一个值,指针间接地引用了一个值。

    指针可以与变量结合,也可以与数组结合使用。指针数组是一种存放一组变量的地址。数组指针是一个指针,表示该指针指向数组的指针。数组指针可以进行自增或自减运算,但是数组名则不能进行自增或自减运算,这是因为数组名是一个常量指针,它是一个常量,常量值是不能改变的。函数指针与指针函数同理。

     

    2.3参数传递

    (1)传值调用:分为实际参数和形式参数。例如:

    int GCD(int m ,int n);
    
    void main(){
        int a,b,v,
        v = GCD(a,b);  //实际参数
    }
    
    int GCD(int m ,int n){ //形式参数
        int r;
        r = m;
        do{
            m=n;
            n=r;
            r=m&n;
          }while(r);
    
        return n;
    }

    上面的函数参数传递属于参数的单向传递,即a和b可以把值传递给m和n,而不是可以把m和n传递给a和b。实际参数和形式参数的值的改变都不会互相收到影响。

    (2)传指针地址参数:略

     

    2.4 结构体和联合体

    也称共用体,是自定义的数据类型,用于构造非数值数据类型,在处理实际问题中应用非常广泛。数据结构中的链表、队列、树、图等结构都需要用到结构体。教师表结构体如下所示。

    //结构体类型
    struct teacher{
        //数据项
        int no;
        char name[20];
        char sex[4];
        char headship[8];
        char degree[6];
        long int phone;
    }

    与结构体一样,联合体也是一种派生的数据类型。但是与结构体不同的是,联合体的成员共享同一个存储空间。定义联合体一般形式如下所示。

    union 共用体名{
    
        成员列表;
    }
    变量列表;
    
    ——————————————————————————
    union data{
    
        int a ;
        float b;
        char c;
        double d;
    }abc;
    
    //或写成
    union data{
        int a;
        float b;
        char c;
        double d;
    };
    union data abc;
    
    

     

    2.5 链表

    在C语言中,处理已知数据可以使用数组。如果事先并不知道要处理的数据的个数,则需要使用链表结构。链表需要动态分配内存,链表的长度随时可以发生变化。链表有一个指针类型的成员指向自身,该指针指向与结构体一样的类型。例如如下语句:

    struct node{
        int data;
        struct data *next;
    }
    

    自引用结构体类型为struct node,该结构体类型有两个成员:整数成员data,指针成员next。成员next是指向结构体为struct node类型的指针。通过这种形式定义的结构体通过next指针把两个结构体变量连在一起。这种自引用结构体单元称为结点,结点之间通过箭头连接起来,构成一张表,称为链表。

    链表中第一个结点的指针称为头指针且可以访问链表的每一个结点。为了方便操作,在链表的第一个结点之前增加一个头结点。

    2.6 内存的分配与释放

    (1)malloc函数主要作用是分配一块长度为size的内存空间。void *malloc(unsigned int size);其中,size就是要分配的内存空间大小字节。使用时最好先检查一下是否分配成功,否则返回null,可以保证程序的正确运行。使用完分配后的空间要利用free函数及时释放。

    (2)free函数主要作用是将内存空间释放。void free (void *p); 其中,参数p指向要释放的内存空间。不能使用已经被free函数释放的内存空间。

     


    下一章:

    数据结构与算法——从零开始学习(二)线性表

     

     

    欢迎,😆大家关注公众号:(推送数据结构+算法+Java+人生感悟+理财知识+互联网事件等)

    展开全文
  • 常见数据结构与算法整理总结(上)

    万次阅读 多人点赞 2018-08-06 18:23:14
    下面是自己整理的常用数据结构与算法相关内容,如有错误,欢迎指出。 为了便于描述,文中涉及到的代码部分都是用Java语言编写的,其实Java本身对常见的几种数据结构,线性表、栈、队列等都提供了较好的实现,就是...

    数据结构是以某种形式将数据组织在一起的集合,它不仅存储数据,还支持访问和处理数据的操作。算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。下面是自己整理的常用数据结构与算法相关内容,如有错误,欢迎指出。

    为了便于描述,文中涉及到的代码部分都是用Java语言编写的,其实Java本身对常见的几种数据结构,线性表、栈、队列等都提供了较好的实现,就是我们经常用到的Java集合框架,有需要的可以阅读这篇文章。Java - 集合框架完全解析

    一、线性表
      1.数组实现
      2.链表
    二、栈与队列
    三、树与二叉树
      1.树
      2.二叉树基本概念
      3.二叉查找树
      4.平衡二叉树
      5.红黑树
    四、图
    五、总结

    一、线性表

    线性表是最常用且最简单的一种数据结构,它是n个数据元素的有限序列。

    实现线性表的方式一般有两种,一种是使用数组存储线性表的元素,即用一组连续的存储单元依次存储线性表的数据元素。另一种是使用链表存储线性表的元素,即用一组任意的存储单元存储线性表的数据元素(存储单元可以是连续的,也可以是不连续的)。

    数组实现

    数组是一种大小固定的数据结构,对线性表的所有操作都可以通过数组来实现。虽然数组一旦创建之后,它的大小就无法改变了,但是当数组不能再存储线性表中的新元素时,我们可以创建一个新的大的数组来替换当前数组。这样就可以使用数组实现动态的数据结构。

    • 代码1 创建一个更大的数组来替换当前数组
    int[] oldArray = new int[10];
    
    int[] newArray = new int[20];
    
    for (int i = 0; i < oldArray.length; i++) {
        newArray[i] = oldArray[i];
    }
    
    // 也可以使用System.arraycopy方法来实现数组间的复制        
    // System.arraycopy(oldArray, 0, newArray, 0, oldArray.length);
    
    oldArray = newArray;
    • 代码2 在数组位置index上添加元素e
    //oldArray 表示当前存储元素的数组
    //size 表示当前元素个数
    public void add(int index, int e) {
    
        if (index > size || index < 0) {
            System.out.println("位置不合法...");
        }
    
        //如果数组已经满了 就扩容
        if (size >= oldArray.length) {
            // 扩容函数可参考代码1
        }
    
        for (int i = size - 1; i >= index; i--) {
            oldArray[i + 1] = oldArray[i];
        }
    
        //将数组elementData从位置index的所有元素往后移一位
        // System.arraycopy(oldArray, index, oldArray, index + 1,size - index);
    
        oldArray[index] = e;
    
        size++;
    }

    上面简单写出了数组实现线性表的两个典型函数,具体我们可以参考Java里面的ArrayList集合类的源码。数组实现的线性表优点在于可以通过下标来访问或者修改元素,比较高效,主要缺点在于插入和删除的花费开销较大,比如当在第一个位置前插入一个元素,那么首先要把所有的元素往后移动一个位置。为了提高在任意位置添加或者删除元素的效率,可以采用链式结构来实现线性表。

    链表

    链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点组成,这些节点不必在内存中相连。每个节点由数据部分Data和链部分Next,Next指向下一个节点,这样当添加或者删除时,只需要改变相关节点的Next的指向,效率很高。

    单链表的结构

    下面主要用代码来展示链表的一些基本操作,需要注意的是,这里主要是以单链表为例,暂时不考虑双链表和循环链表。

    • 代码3 链表的节点
    class Node<E> {
    
        E item;
        Node<E> next;
    
        //构造函数
        Node(E element) {
           this.item = element;
           this.next = null;
       }
    }
    • 代码4 定义好节点后,使用前一般是对头节点和尾节点进行初始化
    //头节点和尾节点都为空 链表为空
    Node<E> head = null;
    Node<E> tail = null;
    • 代码5 空链表创建一个新节点
    //创建一个新的节点 并让head指向此节点
    head = new Node("nodedata1");
    
    //让尾节点也指向此节点
    tail = head;
    • 代码6 链表追加一个节点
    //创建新节点 同时和最后一个节点连接起来
    tail.next = new Node("node1data2");
    
    //尾节点指向新的节点
    tail = tail.next;
    • 代码7 顺序遍历链表
    Node<String> current = head;
    while (current != null) {
        System.out.println(current.item);
        current = current.next;
    }
    • 代码8 倒序遍历链表
    static void printListRev(Node<String> head) {
    //倒序遍历链表主要用了递归的思想
        if (head != null) {
            printListRev(head.next);
            System.out.println(head.item);
        }
    }
    • 代码 单链表反转
    //单链表反转 主要是逐一改变两个节点间的链接关系来完成
    static Node<String> revList(Node<String> head) {
    
        if (head == null) {
            return null;
        }
    
        Node<String> nodeResult = null;
    
        Node<String> nodePre = null;
        Node<String> current = head;
    
        while (current != null) {
    
            Node<String> nodeNext = current.next;
    
            if (nodeNext == null) {
                nodeResult = current;
            }
    
            current.next = nodePre;
            nodePre = current;
            current = nodeNext;
        }
    
        return nodeResult;
    }

    上面的几段代码主要展示了链表的几个基本操作,还有很多像获取指定元素,移除元素等操作大家可以自己完成,写这些代码的时候一定要理清节点之间关系,这样才不容易出错。

    链表的实现还有其它的方式,常见的有循环单链表,双向链表,循环双向链表。 循环单链表 主要是链表的最后一个节点指向第一个节点,整体构成一个链环。 双向链表 主要是节点中包含两个指针部分,一个指向前驱元,一个指向后继元,JDK中LinkedList集合类的实现就是双向链表。 循环双向链表 是最后一个节点指向第一个节点。

    二、栈与队列

    栈和队列也是比较常见的数据结构,它们是比较特殊的线性表,因为对于栈来说,访问、插入和删除元素只能在栈顶进行,对于队列来说,元素只能从队列尾插入,从队列头访问和删除。

    栈是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫作栈顶,对栈的基本操作有push(进栈)和pop(出栈),前者相当于插入,后者相当于删除最后一个元素。栈有时又叫作LIFO(Last In First Out)表,即后进先出。

    栈的模型

    下面我们看一道经典题目,加深对栈的理解。

    关于栈的一道经典题目

    上图中的答案是C,其中的原理可以好好想一想。

    因为栈也是一个表,所以任何实现表的方法都能实现栈。我们打开JDK中的类Stack的源码,可以看到它就是继承类Vector的。当然,Stack是Java2前的容器类,现在我们可以使用LinkedList来进行栈的所有操作。

    队列

    队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

    队列示意图

    我们可以使用链表来实现队列,下面代码简单展示了利用LinkedList来实现队列类。

    • 代码9 简单实现队列类
    public class MyQueue<E> {
    
        private LinkedList<E> list = new LinkedList<>();
    
        // 入队
        public void enqueue(E e) {
            list.addLast(e);
        }
    
        // 出队
        public E dequeue() {
            return list.removeFirst();
        }
    }

    普通的队列是一种先进先出的数据结构,而优先队列中,元素都被赋予优先级。当访问元素的时候,具有最高优先级的元素最先被删除。优先队列在生活中的应用还是比较多的,比如医院的急症室为病人赋予优先级,具有最高优先级的病人最先得到治疗。在Java集合框架中,类PriorityQueue就是优先队列的实现类,具体大家可以去阅读源码。

    三、树与二叉树

    树型结构是一类非常重要的非线性数据结构,其中以树和二叉树最为常用。在介绍二叉树之前,我们先简单了解一下树的相关内容。

    树 是由n(n>=1)个有限节点组成一个具有层次关系的集合。它具有以下特点:每个节点有零个或多个子节点;没有父节点的节点称为 根 节点;每一个非根节点有且只有一个 父节点 ;除了根节点外,每个子节点可以分为多个不相交的子树。

    树的结构

    二叉树基本概念

    • 定义

    二叉树是每个节点最多有两棵子树的树结构。通常子树被称作“左子树”和“右子树”。二叉树常被用于实现二叉查找树和二叉堆。

    • 相关性质

    二叉树的每个结点至多只有2棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。

    二叉树的第i层至多有2^(i-1)个结点;深度为k的二叉树至多有2^k-1个结点。

    一棵深度为k,且有2^k-1个节点的二叉树称之为 满二叉树 

    深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为 完全二叉树 

     

    • 三种遍历方法

    在二叉树的一些应用中,常常要求在树中查找具有某种特征的节点,或者对树中全部节点进行某种处理,这就涉及到二叉树的遍历。二叉树主要是由3个基本单元组成,根节点、左子树和右子树。如果限定先左后右,那么根据这三个部分遍历的顺序不同,可以分为先序遍历、中序遍历和后续遍历三种。

    (1) 先序遍历 若二叉树为空,则空操作,否则先访问根节点,再先序遍历左子树,最后先序遍历右子树。 (2) 中序遍历 若二叉树为空,则空操作,否则先中序遍历左子树,再访问根节点,最后中序遍历右子树。(3) 后序遍历 若二叉树为空,则空操作,否则先后序遍历左子树访问根节点,再后序遍历右子树,最后访问根节点。

    给定二叉树写出三种遍历结果

    • 树和二叉树的区别

    (1) 二叉树每个节点最多有2个子节点,树则无限制。 (2) 二叉树中节点的子树分为左子树和右子树,即使某节点只有一棵子树,也要指明该子树是左子树还是右子树,即二叉树是有序的。 (3) 树决不能为空,它至少有一个节点,而一棵二叉树可以是空的。

    上面我们主要对二叉树的相关概念进行了介绍,下面我们将从二叉查找树开始,介绍二叉树的几种常见类型,同时将之前的理论部分用代码实现出来。

    二叉查找树

    • 定义

    二叉查找树就是二叉排序树,也叫二叉搜索树。二叉查找树或者是一棵空树,或者是具有下列性质的二叉树: (1) 若左子树不空,则左子树上所有结点的值均小于它的根结点的值;(2) 若右子树不空,则右子树上所有结点的值均大于它的根结点的值;(3) 左、右子树也分别为二叉排序树;(4) 没有键值相等的结点。

    典型的二叉查找树的构建过程

    • 性能分析

    对于二叉查找树来说,当给定值相同但顺序不同时,所构建的二叉查找树形态是不同的,下面看一个例子。

    不同形态平衡二叉树的ASL不同

    可以看到,含有n个节点的二叉查找树的平均查找长度和树的形态有关。最坏情况下,当先后插入的关键字有序时,构成的二叉查找树蜕变为单支树,树的深度为n,其平均查找长度(n+1)/2(和顺序查找相同),最好的情况是二叉查找树的形态和折半查找的判定树相同,其平均查找长度和log2(n)成正比。平均情况下,二叉查找树的平均查找长度和logn是等数量级的,所以为了获得更好的性能,通常在二叉查找树的构建过程需要进行“平衡化处理”,之后我们将介绍平衡二叉树和红黑树,这些均可以使查找树的高度为O(log(n))。

    • 代码10 二叉树的节点
    class TreeNode<E> {
    
        E element;
        TreeNode<E> left;
        TreeNode<E> right;
    
        public TreeNode(E e) {
            element = e;
        }
    }

    二叉查找树的三种遍历都可以直接用递归的方法来实现:

    • 代码12 先序遍历
    protected void preorder(TreeNode<E> root) {
    
        if (root == null)
            return;
    
        System.out.println(root.element + " ");
    
        preorder(root.left);
    
        preorder(root.right);
    }
    • 代码13 中序遍历
    protected void inorder(TreeNode<E> root) {
    
        if (root == null)
            return;
    
        inorder(root.left);
    
        System.out.println(root.element + " ");
    
        inorder(root.right);
    }
    • 代码14 后序遍历
    protected void postorder(TreeNode<E> root) {
    
        if (root == null)
            return;
    
        postorder(root.left);
    
        postorder(root.right);
    
        System.out.println(root.element + " ");
    }
    • 代码15 二叉查找树的简单实现
    /**
     * @author JackalTsc
     */
    public class MyBinSearchTree<E extends Comparable<E>> {
    
        // 根
        private TreeNode<E> root;
    
        // 默认构造函数
        public MyBinSearchTree() {
        }
    
        // 二叉查找树的搜索
        public boolean search(E e) {
    
            TreeNode<E> current = root;
    
            while (current != null) {
    
                if (e.compareTo(current.element) < 0) {
                    current = current.left;
                } else if (e.compareTo(current.element) > 0) {
                    current = current.right;
                } else {
                    return true;
                }
            }
    
            return false;
        }
    
        // 二叉查找树的插入
        public boolean insert(E e) {
    
            // 如果之前是空二叉树 插入的元素就作为根节点
            if (root == null) {
                root = createNewNode(e);
            } else {
                // 否则就从根节点开始遍历 直到找到合适的父节点
                TreeNode<E> parent = null;
                TreeNode<E> current = root;
                while (current != null) {
                    if (e.compareTo(current.element) < 0) {
                        parent = current;
                        current = current.left;
                    } else if (e.compareTo(current.element) > 0) {
                        parent = current;
                        current = current.right;
                    } else {
                        return false;
                    }
                }
                // 插入
                if (e.compareTo(parent.element) < 0) {
                    parent.left = createNewNode(e);
                } else {
                    parent.right = createNewNode(e);
                }
            }
            return true;
        }
    
        // 创建新的节点
        protected TreeNode<E> createNewNode(E e) {
            return new TreeNode(e);
        }
    
    }
    
    // 二叉树的节点
    class TreeNode<E extends Comparable<E>> {
    
        E element;
        TreeNode<E> left;
        TreeNode<E> right;
    
        public TreeNode(E e) {
            element = e;
        }
    }

    上面的代码15主要展示了一个自己实现的简单的二叉查找树,其中包括了几个常见的操作,当然更多的操作还是需要大家自己去完成。因为在二叉查找树中删除节点的操作比较复杂,所以下面我详细介绍一下这里。

    • 二叉查找树中删除节点分析

    要在二叉查找树中删除一个元素,首先需要定位包含该元素的节点,以及它的父节点。假设current指向二叉查找树中包含该元素的节点,而parent指向current节点的父节点,current节点可能是parent节点的左孩子,也可能是右孩子。这里需要考虑两种情况:

    1. current节点没有左孩子,那么只需要将patent节点和current节点的右孩子相连。
    2. current节点有一个左孩子,假设rightMost指向包含current节点的左子树中最大元素的节点,而parentOfRightMost指向rightMost节点的父节点。那么先使用rightMost节点中的元素值替换current节点中的元素值,将parentOfRightMost节点和rightMost节点的左孩子相连,然后删除rightMost节点。
        // 二叉搜索树删除节点
        public boolean delete(E e) {
    
            TreeNode<E> parent = null;
            TreeNode<E> current = root;
    
            // 找到要删除的节点的位置
            while (current != null) {
                if (e.compareTo(current.element) < 0) {
                    parent = current;
                    current = current.left;
                } else if (e.compareTo(current.element) > 0) {
                    parent = current;
                    current = current.right;
                } else {
                    break;
                }
            }
    
            // 没找到要删除的节点
            if (current == null) {
                return false;
            }
    
            // 考虑第一种情况
            if (current.left == null) {
                if (parent == null) {
                    root = current.right;
                } else {
                    if (e.compareTo(parent.element) < 0) {
                        parent.left = current.right;
                    } else {
                        parent.right = current.right;
                    }
                }
            } else { // 考虑第二种情况
                TreeNode<E> parentOfRightMost = current;
                TreeNode<E> rightMost = current.left;
                // 找到左子树中最大的元素节点
                while (rightMost.right != null) {
                    parentOfRightMost = rightMost;
                    rightMost = rightMost.right;
                }
    
                // 替换
                current.element = rightMost.element;
    
                // parentOfRightMost和rightMost左孩子相连
                if (parentOfRightMost.right == rightMost) {
                    parentOfRightMost.right = rightMost.left;
                } else {
                    parentOfRightMost.left = rightMost.left;
                }
            }
    
            return true;
        }

    平衡二叉树

    平衡二叉树又称AVL树,它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。

    平衡二叉树

    AVL树是最先发明的自平衡二叉查找树算法。在AVL中任何节点的两个儿子子树的高度最大差别为1,所以它也被称为高度平衡树,n个结点的AVL树最大深度约1.44log2n。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

    红黑树

    红黑树是平衡二叉树的一种,它保证在最坏情况下基本动态集合操作的事件复杂度为O(log n)。红黑树和平衡二叉树区别如下:(1) 红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简单。(2) 平衡二叉树追求绝对平衡,条件比较苛刻,实现起来比较麻烦,每次插入新节点之后需要旋转的次数不能预知。点击查看更多

    四、图

    • 简介

    图是一种较线性表和树更为复杂的数据结构,在线性表中,数据元素之间仅有线性关系,在树形结构中,数据元素之间有着明显的层次关系,而在图形结构中,节点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。图的应用相当广泛,特别是近年来的迅速发展,已经渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。

    • 相关阅读

    因为图这部分的内容还是比较多的,这里就不详细介绍了,有需要的可以自己搜索相关资料。

    (1) 《百度百科对图的介绍》
    (2) 《数据结构之图(存储结构、遍历)》

     

    转载自http://www.jianshu.com/p/230e6fde9c75

    展开全文
  • 本课程涉及的数据结构与算法有,栈,队列,单向链表,双向循环链表,树,二叉树,搜索二叉树,平衡搜索二叉树,冒泡,选择,直插,希尔,,归并等,课程还涉及深度优先算法与广度优先算法等等。
  • 数据结构与算法基础(一)

    千次阅读 2019-06-02 18:40:27
    数据结构与算法,顾名思义,分为两个部分:数据结构算法。那它们各自具体概述是什么呢。让我们看以下两个图,简单明了。这里大概了解以下即可。 下面我们重点来讲以下线性结构。 首先线性结构分为: 1.以顺序...

    大家好 我是makasa
    这个栏目呢,我会按照我之前通过视频学习的一个笔记来记录.
    同时,通过写这几篇blog来巩固一下我的基础

    数据结构与算法,顾名思义,分为两个部分:数据结构、算法。那它们各自具体概述是什么呢。让我们看以下两个图,简单明了。这里大概了解以下即可。
    在这里插入图片描述
    在这里插入图片描述
    下面我们重点来讲以下线性结构。
    首先线性结构分为:
    1.以顺序存储方式存储的线性结构:
    ①数组(最大可取到长度-1、数组长度不可变)
    如何解决数组长度不可变:创建一个新数组,长度为原数组+1(添加)或者-1(删除)
    ②栈:(先进后出)例:子弹夹
    ③队列(先进先出)例:排队买票
    2.以链表存储方式存储的线性结构:

    ①单链表:
    在这里插入图片描述
    ②循环链表
    在这里插入图片描述
    ③双链表
    在这里插入图片描述

    然后,在这里呢,我们重点提一下数组里面的查找算法
    查找算法包括:
    ①线性查找:即定义一个数组、进行遍历,查找元素和数组元素相等即可
    二分查找(效率高):应用面不广,因为要求目标数组有序.

    下面贴一下数组的代码(增删改查)

    package cn.makasa;
    import java.util.Arrays;
    
    public class MyArray {
        //定义一个数组
        private int[] elements;
        //构造方法
        public MyArray(){
            elements = new int[0];
        }
        //返回数组的长度
        public int size(){
            return elements.length;
        }
    
        /**
        *	一、在数组末尾添加一个元素
        */
        public  void  add(int element) {
            //1.定义一个新的数组:长度为原数组长度+1
            int[] newArray = new int[elements.length + 1];
            //2.遍历原数组,把原数组的值赋值给新数组
            for (int i = 0; i < elements.length; i++) {
                newArray[i] = elements[i];
            }
            //3.在数组末尾添加一个元素:添加元素的下标 等于 原数组的长度 即:		     
            newArray[elements.length] = element;
            //4.把新数组赋值给原数组
            elements = newArray;
        }
    
      /**
        *	二、打印所有元素显示在控制台
      	*/
        public void show(){
            System.out.println(Arrays.toString(elements));
        }
    	 
      /**
        *	三、删除数组中的元素
        */
        public void delete(int index){
            //1.判断下标是否越界
            if (index< 0 || index > elements.length-1){
                throw new RuntimeException("下标越界");
            }
            //2.定义一个新数组 长度为原数组的长度-1
            int[] newArray = new int[elements.length-1];
            //3。遍历新数组,如果在删除元素之前的元素 :直接赋值 若在删除元素之后的元素:值加1
            for (int i = 0;i<newArray.length;i++){
                if(i<index){
                    newArray[i] = elements[i];
                }else {
                    newArray[i] = elements[i+1];
                }
            }
            //4.把新数组赋值给旧数组
            elements = newArray;
        }
    
        /**
        *  四、得到每一个元素
        */
        public int get(int index){
            return elements[index];
        }
      
        /**
        *  五、插入一个元素到指定位置
        */
    
        public void insert(int index,int element){
            //1.定义一个新数组 长度为原数组的长度+1
            int[] newArr = new int[elements.length+1];
            //2.遍历原数组,判断 如果i<index 直接赋值 如果新数组
            for(int i = 0;i<elements.length;i++){
                if (i<index){
                    newArr[i] = elements[i];
                }else {
                    newArr[i+1] = elements[i];
                }
            }
            newArr[index] = element;
            //替换原数组
            elements = newArr;
        }
    
    
        //替换指定位置的元素
        public void set(int index,int element){
            elements[index] = element;
        }
    
      /**
        *  六、线性查找
        */
        public int search(int target) {
            for(int i =0;i<elements.length;i++){
                if(elements[i] == target){
                    return i;
                }
            }
            return -1;
        }
    
      /**
        *  七、二分查找
        */
        public int binarySearch(int target){
            int begin = 0;
            int end = elements.length-1;
            int mid = (begin+end)/2;
            int index = -1;
            while (true){
                //什么情况下没有这个元素?
                //如果开始在结束位置之后或者重合,没有这个元素
                if(begin>=end){
                    return -1;
                }
                if(elements[mid] == target){
                    return mid;
                }else {
                    if (elements[mid]>target){
                        end=mid-1;
                    }else {
                        begin = mid+1;
                    }
                    mid = (begin+end)/2;
                }
            }
        }
    }
    

    测试类:

    package makasaTest;
    
    import cn.makasa.MyArray;
    
    public class testArray {
        public static void main(String[] args) {
      	    //创建数组对象
            MyArray ma = new MyArray();
            //获取数组长度
            int size = ma.size();
            System.out.println("原数组长度为"+size);
           
            //显示所有元素
            ma.show();
          
            //添加元素
            ma.add(9);
            ma.add(8);
            ma.add(7);
            ma.show();
           
            //删除某个元素
            ma.delete(1);
            ma.show();
            System.out.println(ma.get(1));
            System.out.println("==============");
           
           //插入一个元素
            ma.insert(0,100);
            ma.show();
            
            //修改元素
            ma.set(2,100);
            ma.show();
        }
    }
    

    输出结果:

    原数组长度为0
    []
    [9, 8, 7]
    [9, 7]
    7

    ============
    [100, 9, 7]
    [100, 9, 100]

    展开全文
  • 数据结构算法视频教程

    万人学习 2019-06-25 10:51:39
    数据结构算法视频培训课程,该教程主要是介绍在游戏开发中经常使用的数据结构,例如数组,链表,栈,队列,二叉树,递归等重要知识点讲解以及将它们里灵活的运用到算法里面。
  • 面试中常见的数据结构与算法

    万次阅读 2018-04-09 15:53:58
    2.1 O(n2) 算法 给定一数组,其大小为8个元素,数组内的数据无序。 6 3 5 7 0 4 1 2 冒泡排序:两两比较,将两者较少的升上去,第一次比较空间为0-(N-1)直到最后一轮比较空间为0-1 public class bubbleSort { ...

    第二章排序

    2.1 O(n2) 算法

    给定一数组,其大小为8个元素,数组内的数据无序。

    6 3 5 7 0 4 1 2

    • 冒泡排序:两两比较,将两者较少的升上去,第一次比较空间为0-(N-1)直到最后一轮比较空间为0-1
    public class bubbleSort {
    
        public static void main(String[] args) {
            int[] test = { 6, 3, 5, 7, 0, 4, 1, 2 };
            for (int i = 0; i < test.length - 1; i++) {
                for (int j = 0; j < test.length - i - 1; j++) {
                    if (test[j] > test[j + 1]) {
                        int temp = test[j];
                        test[j] = test[j + 1];
                        test[j + 1] = temp;
                    }
                }
            }
            for (int k = 0; k < test.length; k++) {
                System.out.println(test[k]);
            }
    
        }
    
    }
    
    • 选择排序:在第一趟遍历N个数据,找出其中最小的数值与第一个元素交换,第二趟遍历剩下的N-1个数据,找出其中最小的数值与第二个元素交换……第N-1趟遍历剩下的2个数据,找出其中最小的数值与第N-1个元素交换,至此选择排序完成。
    public class selectSort {
    
        public static void main(String[] args) {
            int[] test = { 6, 3, 5, 7, 0, 4, 1, 2 };
            for (int i = 0; i < test.length; i++) {
                int min = i;
                for (int j = i + 1; j < test.length; j++) {
                    if (test[min] > test[j]) {
                        min = j;
                    }
                }
                if (min != i) {
                    int temp = test[i];
                    test[i] = test[min];
                    test[min] = temp;
                }
            }
            for (int k = 0; k < test.length; k++) {
                System.out.println(test[k]);
            }
        }
    
    }
    • 插入排序:对于未排序数据,在已排序序列中从后向前扫描,找到相应的位置并插入。
    public class insertSort {
        public static void main(String[] args) {
            int[] test = { 6, 3, 5, 7, 0, 4, 1, 2 };
            for (int i = 0; i < test.length; i++) {
                for (int j = i; j > 0; j--) {
                    if (test[j] < test[j - 1]) {
                        int temp = test[j];
                        test[j] = test[j - 1];
                        test[j - 1] = temp;
                    } else {
                        break;
                    }
                }
            }
            for (int k = 0; k < test.length; k++) {
                System.out.println(test[k]);
            }
        }
    
    }
    

    2.2 O(nlogN) 算法

    • 归并排序:将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列(分治法),每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
    • 快速排序:任取一个分界值,大于划分值放在右边,小于划分值放在左边,然后分别递归处理划分值的左右两边。实现方法:将划分值放在数组最后的位置,然后初始化一个长度为0的小于等于空间放在最左边,接着从左到右遍历所有元素,如果当前元素大于划分值,继续遍历下一个元素,如果当前元素小于等于划分值,将当前数和小于等于空间的下一个数交换位置,小于等于空间向右扩一个位置,遍历完所有元素,直到最后一个数,将划分值与小于等于空间下一个元素交换。(一次完整划分过程)

    快排

    • 堆排序:堆是一种重要的数据结构,为一棵完全二叉树,底层如果用数组存储数据的话,假设某个元素为序号为i(Java数组从0开始,i为0到n-1),如果它有左子树,那么左子树的位置是2i+1,如果有右子树,右子树的位置是2i+2,如果有父节点,父节点的位置是(n-1)/2取整。分为最大堆和最小堆,最大堆的任意子树根节点不小于任意子结点,最小堆的根节点不大于任意子结点。所谓堆排序就是利用堆这种数据结构来对数组排序,我们使用的是最大堆。堆排序的大概步骤如下:(1)构建最大堆;(2)选择顶,并与第0位置元素交换;(3)由于步骤2的的交换可能破环了最大堆的性质,第0不再是最大元素,需要调用maxHeap调整堆(沉降法),如果需要重复步骤2。
    • 希尔排序:又称缩小增量排序”,其基本原理是,现将待排序的数组元素分成多个子序列,使得每个子序列的元素个数相对较少,然后对各个子序列分别进行直接插入排序,待整个待排序列“基本有序”后,最后在对所有元素进行一次直接插入排序,一般增量设置由大到小。

    2.3 O(N) 算法

    思想:不是基于比较,而是来自于桶排序,桶排序的基本思想则是把数则是arr划分为n个大小相同子区间(桶),每个子区间各自排序,最后合并。

    • 计数排序:需要占用大量空间,它仅适用于数据比较集中的情况。比如[0~100],[10000~19999]这样的数据,对每一个输入的元素arr[i],确定小于 arr[i] 的元素个数,假设有5个数小于 arr[i],所以 arr[i] 应该放在数组的第6个位置上。
    • 基数排序:实质为多关键字排序,思路是将待排数据里排序关键字拆分成多个排序关键字;第1个排序关键字,第2个排序关键字,第3个排序关键字等,然后,根据子关键字对待排序数据进行排序,如个位数,十位数,百位数等。

    经典排序算法的空间复杂度

    • O(1):插入排序、选择排序、冒泡排序、堆排序希尔排序
    • O(logN)~O(N):快速排序;
    • O(N):归并排序;
    • O(M): 计数排序、基数排序(和选择桶的数量有关)。

    经典排序算法的稳定性
    稳定性:假定待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,称这种排序算法是稳定的,否则称为不稳定的。

    • 稳定的排序算法:冒泡排序、插入排序、归并排序、计数排序、基数排序、桶排序
    • 不稳定的排序算法:选择排序、快速排序、希尔排序、堆排序

    第三章字符串

    • 字符串特点:广泛性(1)字符类型数组;(2)其它类型题目可以看做字符串类型题目。Java处理字符串须注意String类在Java中不可更改,可尝试StringBuffer类,StringBuilder类和toCharArray方法处理。
    • 字符串相关概念:回文;字串(连续);子序列(不连续);前缀树(Trie树);后缀树和后缀数组;匹配;字典序
    • 需掌握的操作:与数组有关的操作(增删改查);字符的替换;字符串的旋转
    • 常见类型:判断规则;数字运算;与数组操作有关的类型;字符计数;动态规划类型(最长公共字串等);搜索类型;高级算法与数据结构解决的问题。

    栈和队列

    • 基本性质:栈是先进后出,队列是先进先出;栈和队列在实现结构上可以有数组和链表两种形式(数组结构容易,链表涉及很多指针操作)
    • 栈结构基本操作:pop;top或peek;push;size
    • 双端队列:首尾都可以压入弹出元素;优先级队列:根据元素的优先级值,决定元素的弹出顺序,实为堆结构,并不是线性结构
    • 深度优先遍历用栈来实现,宽度优先用队列实现,平时使用的递归函数实际上用到了提供的函数系统栈。

    链表

    • 链表和数组区别:都是一种线性结构,数组是一段连续的存储空间,而链表空间不一定保证连续,为临时分配
    • 链表分类:按连接方向(单链表,双链表);按照有无环分类(普通链表,循环链表)
    • 代码实现的关键点:(1)链表调整函数的返回值类型,根据要求往往是节点类型;(2)处理链表过程中,先采用画图的方式理清逻辑;(3)对于边界条件处理。
    • 插入删除注意事项:(1)特殊处理链表为空,或者链表长度为1的情况;(2)注意插入操作的调整过程;(3)注意删除操作调整过程。注意点:头尾节点及空节点需要特殊考虑。
    • 单链表的翻转操作:(1)当链表为空或者长度为时,特殊处理;(2)对于一般情况如动画所示。

    单链表翻转

    二分搜索

    常见应用场景

    • 在有序序列中查找一个数,时间复杂度为O(logN);
    • 并不一定非要在有序序列中才得到应用。

    常见考察点

    • 对于边界条件的考察以及代码实现的能力

    常见题目变化

    • 给定处理或查找的对象不同;
    • 判断条件不同;
    • 要求返回的内容不同。

    重要提醒

    mid = (left + right)/2
    (left+right)可能会溢出,更安全的写法:
    mid = left + (right - left)/2

    位运算

    常见操作符

    • 算术运算常见操作符:+ - * / %
    • 位运算常见操作符:& | ^ ~ <<(左移右侧补0) >>(右移左侧补符号位) >>>(右移左侧补0)

    案例

    (1) 网页黑名单系统,垃圾邮件过滤系统,爬虫的网址判断重复系统,容忍一定程度的失误率,但对空间要求较严格 。
    布隆过滤器:可精确地代表一个集合;可精确判断某一元素是否在此集合中;精确程度由用户的具体设计决定;做到100%的精确即正确是不可能的。 布隆过滤器的优势在于,利用很少的空间可以做到精确率较高。

    这里写图片描述

    • 布隆过滤器的bitarray大小如何确定?
      大小为m(过小),样本数量为n(相较于m过大),失误率为p(过大)。
    举例输入:n = 100亿,p = 0.01%
    1. m = - n x lnp / (ln2)2 得到m = 19.19n 向上取整为20n,2000亿bit,约为25G。 2. k = ln2 x m/n = 0.7 x m/n = 14 因此需要14个彼此独立的哈希函数。 3. 此时失误率为(1 - e-nk/m)k = 0.006%,其中m = 20n, k = 14。
    %E7%94%9F%E6%88%90%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8.png

    (2) 不用任何额外变量交换两个整数的值

    给定整数a和b
    a = a0, b = b0
    a = a ^ b --> a = a0 ^ b0, b = b0;
    b = a ^ b --> a = a0 ^ b0, b = a0 ^ b0 ^ b0 = a0;
    a = a ^ b --> a = a0 ^ b0 ^ a0 = b0, b = a0;

    (3) 给定两个32位整数a和b,返回a和b中较大的,但是不能用任何比较判断。

    • 方法1:得到a - b的符号,根据该符号决定返回a或b。
    public static int flip(int n){
        return n ^ 1;
    }
    public static int sign(int n){
        return flip((n >> 31) & 1);
    }
    public static int getMax(int a, int b){
        int c = a - b;
        int scA = sign(c);
        int scB = flip(scA);
        return a = a * scA + b * scB;
    }

    方法一可能会有问题,当a = b溢出时,会发生错误。

    • 方法2
    public static int getMax(int a, int b){
        int c = a - b; 
        int as = sign(a); //a的符号,as == 1表示a为非负,as == 0表示a为负
        int bs = sign(b);  //b的符号,bs == 1表示a为非负,bs == 0表示b为负
        int cs = sign(c);  //a - b的符号
        int difab = as ^ bs;  //表示a和b是否符号不相同,不相同为1,相同为0
        int sameab = flip(difab);  //表示a和b是否符号相同,相同为1,不相同为0
        int returnA = difab + as + sameab + cs;
        int returnB = flip(returnA)
        return  a * returnA + b * returnB;
    }

    (3) 给定一个整型数组arr,其中只有一个数出现了奇数次,其他数都出现了偶数次,请打印这个数,要求时间复杂度为O(n),额外空间复杂度为O(1)。

    注意点:n与0异或结果为n,n与n异或结果为0。
    异或运算满足交换律,结合律。

    (4) 给定一个整型数组arr,其中有两个数出现了奇数次,其他数都出现了偶数次,请打印这个数,要求时间复杂度为O(n),额外空间复杂度为O(1)。

    (5) 请设置一种加密过程,完成对明文text的加密和解密工作。

    明文text,用户给定密码pw,假设密文为cipher。
    cipher = text ^ pw
    text = cipher ^ pw = text ^ pw ^ pw = text
    如果text长度大于pw,循环使用pw与text进行按位异或。

    排列组合

    概率组合题目分类

    1. 以高中数学为基础的古典概率计算方法;
    2. 斐波那契数和卡特兰数;
    3. 以选择题居多

    案例

    1. 在6x9的方格中,以左上角为起点,右下角为终点,每次只能向下或者向右走,请问一共有多少种不同的走法。
    解法:一共走13步,其中必然有5步向下,剩下的8步向右,所以一共有C13(5) = 1287.
    1. ABCDEFG七人战队,要求A必须站在B的左边,但不要求一定相邻,请问共有多少种排法?如果要求A必须在B的左边,并且一定要相邻,请问一共有多少种排法?
    不相邻:一共有7!种排法,其中一半的情况是A在B的左边,一半的情况是B在A的左边,所以第一种情况共有7!/2 = 2520种
    相邻:A和B看作为一个人,所以第二种情况为6! = 720
    1. A六个人排成一排,要求甲与乙不相邻,并且甲与丙不相邻的排法数是多少?
    方法一:
    6个人全排列6! = 720; 甲与乙相邻总数2 * 5! = 240; 甲与丙相邻总数2 * 5! = 240; 相交的情况(乙甲丙或丙甲乙)2 * 4! = 48720 - 240 -240 + 48 = 288
    方法二:
    考虑甲的位置 3 * 4! * 2 + 6 * 3! * 4 = 288
    1. 卡特兰数重要公式
      image
      image

    概率

    常见问题类型

    • 作为客观题出现;
    • 概率、期望计算;
    • 往往利用古典概率进行计算(组合数学)。

    概率的应用

    • 利用随机来改进著名算法(快速排序);
    • 随机数发生器(用给定的随机数发生器构造另一个);

    案例

    1. 8只球队,有3个强队,其余都是弱队,随机把它们分成四组比赛,每组两个队,问两强相遇的概率是多大?
    1. 首先求出8只球队分成4组比赛的方法数:7 x 5 x 3 x 1 = 105;
    2. 没有两强相遇的方法数:C5(3) x A3(3) = 60;
    3. (105 - 60)/105 = 3/7
    1. 三只蚂蚁从正三角形的三个顶点沿着边移动,速度是相同的,问他们碰头的概率是多少?
    方向相同不会相遇,所以(8 - 2)/8 =  3/4
    1. 某地区重男轻女,一个家庭如果生出一个女孩就一直生,直到生出男孩就停止生育。假设一胎只出生一个孩子,问时间足够长后,男女比例是会变为多少?
    男女比例依然为1:1
    1. 给定一个等概率随机产生1~5的随机数,除此之外,不能使用任何额外的随机机制,请实现等概率随机产生1~7的随机函数。
    1. 已经有等概率随机产生1、2、3、4、5的随机函数;
    2. 根据步骤1得到的结果减1,将得到f() → 0、1、2、3、4;
    3. f() x 5 → 0、5、10、15、20;
    4. f() x 5 + f()→ 0、1、2、3、4...24;
    注意:步骤4中的f()是分别调用的,不要化简。
    5. 如果步骤4产生的数大于20,则重复地进行步骤4,直到产生的结果在0~20之间;
    6. 步骤5的结果将等概率产生0~20,所以步骤5的结果%7之后等概率产生0~6;
    7. 步骤6的结果加1,将等概率产生1~7.
    

    大数据

    • 哈希函数(散列函数):拥有无限的输入值域;输入值相同时,返回值一样;输入值不同时,返回值可能一样,也可能不一样;不同输入值得到的哈希值,整体均匀的分布在输出域上
    1~3点性质是哈希函数的基础,第4点是评价一个哈希函数优劣的关键。MD5与SHA1算法都是经典的哈希函数算法,了解即可。
    • Map-Reduce和Hadoop逐渐成为面试热门
      1. Map阶段 –> 把大任务分成子任务。
      2. Reduce阶段 –>子任务并发处理,然后合并结果。
    注意点:备份的考虑,分布式存储的设计细节,以及容灾策略;任务分配策略与任务进度跟踪的细节设计,节点状态的呈现;多用户权限的控制。

    常见海量处理题目解题关键

    • 分而治之。通过哈希函数将大任务分流到机器上或分流成小文件;
    • 常用的hashMap或bitmap。
      难点:通讯、时间和空间的估算。
    • 一致性哈希算法

    动态规划

    CSDN博主:常敲代码手不抖
    1. 教你彻底学会动态规划——入门篇
    2. 教你彻底学会动态规划——进阶篇

    案例

    给定数组arr,arr中所有的值都为正数且不重复,每个值代表一种面值的货币,每种面值的货币可以使用任意张,再给定一个整数aim代表要找的钱数,求换钱有多少种方法。

    arr = [5、10、25、1], aim = 1000.

    暴力搜索方法–>记忆搜索方法–>动态规划方法–>状态继续化简后的动态规划方法

    • 暴力搜索
    1. 用0张5元的货币,让[10,25,1]组成剩下的1000,最终方法数记为---------------------------res1
    2. 用1张5元的货币,让让[10,25,1]组成剩下的995,最终方法数记为---------------------------res2
    3. 用2张5元的货币,让让[10,25,1]组成剩下的990,最终方法数记为---------------------------res3
    
    ...........................................................................................
    
    201. 用200张5元的货币,让让[10,25,1]组成剩下的0,最终方法数记为-------------------------res201
    定义递归函数:int p1(arr,index,aim),它的含义是如果用arr[index...N-1]这些面值的钱组成aim,返回总的方法数。
    • 记忆搜索
    arr = [510251], aim = 1000. p(index,aim) 结果表map
    1. 每计算完一个p(index,aim),都将结果放入到map中,index和aim组成共同key,返回结果为value;
    2. 要进入一个递归过程p(index,aim),先以index和aim注册的key在map中查询是否已经存在value,如果存在,则直接取值,如果不存在,才进行递归运算。
    • 动态规划
    如果arr长度为N,生成行数为N,列数为aim + 1的矩阵dp.dp[i][j]的含义是在使用arr[0...i]货币的情况下,组成钱数j有多少种方法。

    动态规划

    记忆搜索方法与动态规划方法的联系
    1. 记忆化搜索方法就是某种形态的动态规划方法;
    2. 记忆化搜索方法不关心到达某一个递归过程的路径,只是单纯地对计算过的递归过程进行记录,避免重复的递归过程;
    3. 动态规划的方法则是规定好每一个递归过程的计算顺序,依次进行计算,后面的计算过程严格依赖前面的计算过程;
    4. 两者都是空间换时间的方法,也都有枚举的过程,区别就在于动态规划规定计算顺序,而记忆搜索不用规定。
    什么是动态规划方法?
    1. 其本质是利用申请的空间来记录每一个暴力搜索的计算结果,下次要用结果的时候直接使用,而不再进行重复的递归过程;
    2. 动态规划规定每一种递归状态的计算顺序,依次进行计算。
    • 状态继续化简后动态规划方法
    动态规划方法中dp[i][j]等于如下值的累加:
    dp[i-1][j]
    dp[i-1][j-1*arr[i]]
    dp[i-1][j-2*arr[i]]
    dp[i-1][j-3*arr[i]]
    
    以上可以化简为:dp[i][j] = dp[i-1][j-arr[i]] + dp[i-1][j]
    
    暴力递归题目可以优化成动态规划方法的大体过程:
    1. 实现暴力递归方法;
    2. 在暴力搜索方法的函数中看看哪些参数可以代表递归过程;
    3. 找到代表递归过程的参数之后,记忆化搜索的方法非常容易实现,利用hashmap将部分递归值进行存储;
    4. 通过分析记忆化搜索的依赖路径,进而实现动态规划;
    5. 根据记忆化搜索方法该出动态规划方法,进而看看是否能化简,如果能化简,还能实现时间复杂度更低的动态规划方法。
    展开全文
  • 数据结构与算法基础知识(1)

    千次阅读 2018-07-08 19:33:29
    数据结构的定义分类 逻辑结构 物理结构 数据结构的定义 数据结构就是关系,是数据元素之间存在的一种或者多种特定关系的集合。 数据结构分为两类: a. 逻辑结构 b. 物理结构 逻辑结构: 数据对象中数据元素...
  •   2019-01-24 15:36:35 国外 IT 教育学院 Educative.io 创始人 Fahim ul Haq 写过一篇过万赞的文章《The top data structures you should know for your next coding interview》,总结了程...
  • 数据结构与算法】常见数据结构及基本操作

    万次阅读 多人点赞 2019-06-16 22:13:24
    数据结构与算法常见概念2.数据逻辑结构2.1线性结构2.2树形结构2.3图形结构2.4集合结构3.排序算法冒泡排序简单选择排序直接插入排序希尔排序堆排序归并排序快速排序4.查找算法顺序表查找有序表查找线性索引查找二叉...
  • 数据结构与算法学习笔记

    万次阅读 多人点赞 2020-04-22 10:56:22
    本文是王争老师的《算法与数据结构之美》的学习笔记,详细内容请看王争的专栏。有不懂的地方指出来,我做修改。 数据结构与算法思维导图 数据结构指的是“一组数据的存储结构”,算法指的是“操作数据的一组...
  • 数据结构与算法中的经典算法

    万次阅读 多人点赞 2018-07-20 02:30:53
    数据结构与算法之经典算法 常见数据结构与算法整理总结(上) 常见数据结构与算法整理总结(下) 二、针对性参考 1) 排序 数据结构与算法之经典排序 2)二叉树 数据结构与算法之二叉树+遍历+哈夫曼树 ...
  • 数据结构与算法(java版)

    万次阅读 多人点赞 2018-04-22 17:18:08
    数据结构与算法(java版)标签: java 数据结构 算法2017年12月28日 21:50:08102人阅读 评论(0) 收藏 举报 分类:数据结构与算法转自:http://blog.csdn.net/column/details/datastructureinjava.html 目录...
  • 本书下载链接: https://download.csdn.net/download/u010752028/10575288
  • 数据结构与算法分析 C语言描述(原书第2版)下载链接: https://pan.baidu.com/s/1VrsrvtCujFHbseuJjXJACA 提取码获取方式:关注下面微信公众号,回复关键字: 1136
  • 数据结构与算法视频推荐

    万次阅读 2017-11-14 18:13:20
    数据结构与算法视频推荐 https://www.bilibili.com/video/av2975983/index_1.html#page=1
  • 数据结构与算法分析 C++语言描述第四版.Mark Allen Weiss 可用于自学数据结构与算法数据结构与算法分析对于C++的学习至关重要,应该努力掌握好! 百度网盘: 链接:...
  • python数据结构与算法总结

    万次阅读 多人点赞 2019-04-24 09:48:14
    python常用的数据结构与算法就分享到此处,本月涉及数据结构与算法的内容有如下文章: 《数据结构算法对python意味着什么?》 《顺序表数据结构在python中的应用》 《python实现单向链表数据结构及其基本方法》...
  • 数据结构与算法书籍推荐

    万次阅读 多人点赞 2019-03-16 18:49:31
    学习数据结构与算法,还是很有必要看几本相关的书籍,但根据不同基础的人,合适看的书也不一样,因此,针对不同层次、不同语言的人,推荐几本市面上口碑不错的书。 1. 入门级 针对刚入门的同学,建议不要急着去看...
  • 数据结构与算法知识点总结—思维导图

    万次阅读 多人点赞 2020-04-20 22:50:54
    数据结构与算法是学习编程者的必修课,下面是我学习完之后的知识点梳理总结。 本来用xmind做的时候把重要知识点都附了博客链接,但是xmind导出来后打不开了。 不用担心我把相关内容放在了数据结构专栏里。 ...
  • (强烈推荐!!!)数据结构与算法学习

    万次阅读 多人点赞 2018-07-30 21:56:11
    基本算法 贪心算法:贪心算法&nbsp;作者:独酌逸醉 贪心算法:贪心算法精讲&nbsp;作者:3522021224 递归和分治:递归分治策略&nbsp;作者:zhoudaxia 图论 图的遍历(DFS和BFS):图的遍历&...
1 2 3 4 5 ... 20
收藏数 1,038,236
精华内容 415,294
关键字:

数据结构与算法