算法与数据结构_javascript数据结构与算法,比如排序算法,递归算法 - CSDN
算法与数据结构 订阅
《算法与数据结构》是2008年国防工业出版社出版的图书,作者是张永、李睿、年福忠。 展开全文
《算法与数据结构》是2008年国防工业出版社出版的图书,作者是张永、李睿、年福忠。
信息
开    本
16开
出版社
国防工业出版社
ISBN
9787118058529
作    者
张永、李睿、年福忠
定    价
¥30.00
类    别
图书 >> 计算机/网络 >> 数据库 >> 数据库理论
装    帧
平装
页    数
296
字    数
438000
印次 
1
丛书名
普能高等院校“十一五”规划教材
书    名
算法与数据结构
出版时间
2008-8-1
算法与数据结构内容简介
本书概念清晰,逻辑严密,重点突出,将抽象的描述与具体的实现结合,便于教学,也使初学者容易掌握其重点内容,有利于自学。本书的算法描述和实现采用类c和C语言。本书可以作为计算机科学与技术、信息与计算科学和相关专业的本科或大专教材。 [1] 
收起全文
精华内容
参与话题
  • 数据结构:是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、(存储)物理结构和数据的运算三个部分。 为什么要学数据结构? 首先,因为数据结构作为...

    系列文章

    第一章:基础知识

    第二章:线性表

    第三章:栈和队列 

    第四章:字符串和数组

    第五章:树和二叉树

    第六章:图

    第七章:排序算法


    前言

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

    为什么要学数据结构?

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

    如何学习数据结构?

    对于初学者来说,数据结构是门概念上比较抽象的课程,不是太容易掌握,需要构思和理解。万事开头难,只要你掌握了学习这门课的方法和技巧,就会变得很容易了。不管学什么,首先应该做好充分的心理准备,建立好自信心,拥有一颗战胜困难的决心,才能不畏惧、不退缩,直至胜利归来。其次,就是最好有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

    展开全文
  • 数据结构与算法学习笔记

    万次阅读 多人点赞 2020-04-22 10:56:22
    数据结构与算法思维导图 数据结构指的是“一组数据的存储结构”,算法指的是“操作数据的一组方法”。 数据结构是为算法服务的,算法是要作用再特定的数据结构上的。 最常用的数据结构预算法: 数据结构:数组、...

    本文是王争老师的《算法与数据结构之美》的学习笔记,详细内容请看王争的专栏 。有不懂的地方指出来,我做修改。

     

    数据结构与算法思维导图

    数据结构指的是“一组数据的存储结构”,算法指的是“操作数据的一组方法”。
    数据结构是为算法服务的,算法是要作用再特定的数据结构上的。

    最常用的数据结构预算法:

    • 数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Tire树
    • 算法: 递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法

    1  算法的复杂度

    1.1大O复杂度表示法

     公式:

     

    T(n)表示代码执行的时间; n表示数据规模的大小; f(n) 表示每行代码执行的次数总和。因为这是一个公式, 所以用f(n)来表示。公式中的O,表示代码的执行时间T(n)与f(n)表达式成正比。

          所以,第一个例子中的T(n) = O(2n+2),第二个例子中的T(m) = 0(2n2 +2n+3)。这就是大O时间复杂度表示法。大O时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

          当n很大时,你可以把它想象成10000、100000。 而公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略。我们只需要记录-个最大量级就可以了,如果用大O表示法表示刚讲的那两段代码的时间复杂度,就可以记为: T(n) = O(n); T(n)= 0(n2)。
     

    1.2.复杂度分析法则

    1)单段代码看高频:比如循环。
    2)多段代码取最大:比如一段代码中有单循环和多重循环,那么取多重循环的复杂度。
    3)嵌套代码求乘积:比如递归、多重循环等
    4)多个规模求加法:比如方法有两个参数控制两个循环的次数,那么这时就取二者复杂度相加。

     

    1.3 时间复杂度分析

    • 只关注循环执行次数最多的一段代码
    • 加法法则:总复杂度等于量级最大的那段代码的复杂度
    • 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

    1.4 几种常见时间复杂度实例分析

    多项式阶:随着数据规模的增长,算法的执行时间和空间占用,按照多项式的比例增长。包括,
    O(1)(常数阶)、O(logn)(对数阶)、O(n)(线性阶)、O(nlogn)(线性对数阶)、O(n^2)(平方阶)、O(n^3)(立方阶)
    非多项式阶:随着数据规模的增长,算法的执行时间和空间占用暴增,这类算法性能极差。包括,
    O(2^n)(指数阶)、O(n!)(阶乘阶)

    • O(1) :

    常量级时间复杂度,只要代码的执行时间不随 n 的增大而增长,这样代码的时间复杂度我们都记作 O(1)。

    • O(logn)、O(nlogn)
    i=1;
    while(i<=n) {
        i = i*2;
    }

    x=log2n,所以,这段代码的时间复杂度就是 O(log2n)

    • O(m+n)、O(m*n)

     

    int cal(int m, int n) {
        intsum_1=e;
        inti=1;
        for(;iくm;++i){
            sum_1=sum1+i;
        }
        int sum_2=0;
        int j=1;
        for (;jくn;+j){
            sum_2=sum_2+j;
        }
        return sum_1 + sum_2;
    }
    

    从代码中可以看出,m和n是表示两个数据规模。我们无法事先评估m和n谁的量级大,所以我们在表示复杂度的时候,就不能简单地利用加法法则,省略掉其中一个。所以,上面代码的时间复 杂度就是0(m+n)。

    针对这种情况,原来的加法法则就不正确了,我们需要将加法规则改为: T1(m) + T2(m) = O(f(m) + g(n))。但是乘法法则继续有效: T1(m)*T2(n) = O(f(m) * f(n))。

    1.5 空间复杂度分析

    表示算法的存储空间与数据规模之间的增长关系。

    void print(int n) {
        inti=0;
        int[] a = new int[n];
        for (i; i <n; ++i) {
            a[i] =i* i;
        }
        for(i=n-1;i>=0;--i){
            print out a[i]
        }
    }

    跟时间复杂度分析一样,我们可以看到,第2行代码中,我们申请了一个空间存储变量i,但是它是常最阶的,跟数据规模n没有关系,所以我们可以忽略。第3行申请了一个大小为n的int类型数组,除此之外,剩下的代码都没有占用更多的空间,所以整段代码的空间复杂度就是O(n)。

    我们常见的空间复杂度就是O(1)、O(n)、 O(n2), 像O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且,空间复杂度分析比时间复杂度分析要简单很多。所以,对于空间复杂度,掌握刚我说的这些内容已经足够了。

    1.6 复杂度增长趋势图:

    最好情况时间复杂度、最坏时间复杂度、平均情況时间复杂度、均摊时间复杂度。

    一、复杂度分析的4个概念
    1.最坏情况时间复杂度:代码在最理想情况下执行的时间复杂度。
    2.最好情况时间复杂度:代码在最坏情况下执行的时间复杂度。
    3.平均时间复杂度:用代码在所有情况下执行的次数的加权平均值表示。
    4.均摊时间复杂度:在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高级别复杂度且发生具有时序关系时,可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

    二、为什么要引入这4个概念?
    1.同一段代码在不同情况下时间复杂度会出现量级差异,为了更全面,更准确的描述代码的时间复杂度,所以引入这4个概念。
    2.代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下,是不需要区别分析它们的。

    三、如何分析平均、均摊时间复杂度?
    1.平均时间复杂度
    代码在不同情况下复杂度出现量级差别,则用代码所有可能情况下执行次数的加权平均值表示。
    2.均摊时间复杂度
    两个条件满足时使用:1)代码在绝大多数情况下是低级别复杂度,只有极少数情况是高级别复杂度;2)低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。

    数组

    线性表:   线性表就是数据排成像一条线一样的结构.每个现行表上的数据最多只有前和后两个方向.常见的线性表结构:数组,链表、队列、栈等。

     

    什么是数组:

    1.  数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据
    2.  连续的内存空间和相同类型的数据(随机访问的前提)
    3. 优点:两限制使得具有随机访问的特性缺点:删除,插入数据效率低
    • 数组怎么根据下标随机访问的?

    通过寻址公式:a[i]_address = base_address + i * data_type_size
    其中data_type_size表示数组中每个元素的大小,base_address 是首元素地址,i数组下标。

     

    为何数组插入和删除低效:

    插入:
    若有一元素想往int[n]的第k个位置插入数据,需要在k-n的位置往后移。
    最好情况时间复杂度 O(1)

    如果数组中的数据不是有序的,也就是无规律的情况下,可以直接把第k个位置上的数据移到最后,然后将插入的数据直接放在第k个位置上。

    最坏情况复杂度为O(n)


    平均负责度为O(n)

    2. 低效的插入和删除
    1) 插入:从最好O(1) 最坏O(n) 平均O(n)
    2) 插入:数组若无序,插入新的元素时,可以将第K个位置元素移动到数组末尾,把心的元素,插入到第k个位置,此处复杂度为O(1)。作者举例说明
    3) 删除:从最好O(1) 最坏O(n) 平均O(n)
    4) 多次删除集中在一起,提高删除效率
    记录下已经被删除的数据,每次的删除操作并不是搬移数据,只是记录数据已经被删除,当数组没有更多的存储空间时,再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。

     

    链表

    • 什么是链表

    1.和数组一样,链表也是一种线性表。
    2.从内存结构来看,链表的内存结构是不连续的内存空间,是将一组零散的内存块串联起来,从而进行数据存储的数据结构。
    3.链表中的每一个内存块被称为节点Node。节点除了存储数据外,还需记录链上下一个节点的地址,即后继指针next。

     

    • 链表的特点

    1.插入、删除数据效率高O(1)级别(只需更改指针指向即可),随机访问效率低O(n)级别(需要从链头至链尾进行遍历)。


    2.和数组相比,内存空间消耗更大,因为每个存储数据的节点都需要额外的空间存储后继指针。

    • 常用链表

    1.单链表


    1)每个节点只包含一个指针,即后继指针。
    2)单链表有两个特殊的节点,即首节点和尾节点。为什么特殊?用首节点地址表示整条链表,尾节点的后继指针指向空地址null。
    3)性能特点:插入和删除节点的时间复杂度为O(1),查找的时间复杂度为O(n)。

     

    2.循环链表


    1)除了尾节点的后继指针指向首节点的地址外均与单链表一致。
    2)适用于存储有循环特点的数据,比如约瑟夫问题。

     

    3.双向链表


    1)节点除了存储数据外,还有两个指针分别指向前一个节点地址(前驱指针prev)和下一个节点地址(后继指针next)。
    2)首节点的前驱指针prev和尾节点的后继指针均指向空地址。
    3)性能特点:
    和单链表相比,存储相同的数据,需要消耗更多的存储空间。
    插入、删除操作比单链表效率更高O(1)级别。以删除操作为例,删除操作分为2种情况:给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况,单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除,时间复杂度为O(n)。对于第二种情况,要进行删除操作必须找到前驱节点,单链表需要从头到尾进行遍历直到p->next = q,时间复杂度为O(n),而双向链表可以直接找到前驱节点,时间复杂度为O(1)。
    对于一个有序链表,双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置p,每一次查询时,根据要查找的值与p的大小关系,决定是往前还是往后查找,所以平均只需要查找一半的数据。

    4.双向循环链表:

    首节点的前驱指针指向尾节点,尾节点的后继指针指向首节点。

    • 选择数组还是链表?

    1.插入、删除和随机访问的时间复杂度
    数组:插入、删除的时间复杂度是O(n),随机访问的时间复杂度是O(1)。
    链表:插入、删除的时间复杂度是O(1),随机访问的时间复杂端是O(n)。

    2.数组缺点
    1)若申请内存空间很大,比如100M,但若内存空间没有100M的连续空间时,则会申请失败,尽管内存可用空间超过100M。
    2)大小固定,若存储空间不足,需进行扩容,一旦扩容就要进行数据复制,而这时非常费时的。
    3.链表缺点
    1)内存空间消耗更大,因为需要额外的空间存储指针信息。
    2)对链表进行频繁的插入和删除操作,会导致频繁的内存申请和释放,容易造成内存碎片,如果是Java语言,还可能会造成频繁的GC(自动垃圾回收器)操作。
    4.如何选择?
    数组简单易用,在实现上使用连续的内存空间,可以借助CPU的缓冲机制预读数组中的数据,所以访问效率更高,而链表在内存中并不是连续存储,所以对CPU缓存不友好,没办法预读。
    如果代码对内存的使用非常苛刻,那数组就更适合。

    • 应用

    1.如何分别用链表和数组实现LRU缓冲淘汰策略?
    1)什么是缓存?
    缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非广泛的应用,比如常见的CPU缓存、数据库缓存、浏览器缓存等等。
    2)为什么使用缓存?即缓存的特点
    缓存的大小是有限的,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?就需要用到缓存淘汰策略。
    3)什么是缓存淘汰策略?
    指的是当缓存被用满时清理数据的优先顺序。
    4)有哪些缓存淘汰策略?
    常见的3种包括先进先出策略FIFO(First In,First Out)、最少使用策略LFU(Least Frenquently Used)、最近最少使用策略LRU(Least Recently Used)。
    5)链表实现LRU缓存淘汰策略
    当访问的数据没有存储在缓存的链表中时,直接将数据插入链表表头,时间复杂度为O(1);当访问的数据存在于存储的链表中时,将该数据对应的节点,插入到链表表头,时间复杂度为O(n)。如果缓存被占满,则从链表尾部的数据开始清理,时间复杂度为O(1)。
    6)数组实现LRU缓存淘汰策略
    方式一:首位置保存最新访问数据,末尾位置优先清理
    当访问的数据未存在于缓存的数组中时,直接将数据插入数组第一个元素位置,此时数组所有元素需要向后移动1个位置,时间复杂度为O(n);当访问的数据存在于缓存的数组中时,查找到数据并将其插入数组的第一个位置,此时亦需移动数组元素,时间复杂度为O(n)。缓存用满时,则清理掉末尾的数据,时间复杂度为O(1)。
    方式二:首位置优先清理,末尾位置保存最新访问数据
    当访问的数据未存在于缓存的数组中时,直接将数据添加进数组作为当前最有一个元素时间复杂度为O(1);当访问的数据存在于缓存的数组中时,查找到数据并将其插入当前数组最后一个元素的位置,此时亦需移动数组元素,时间复杂度为O(n)。缓存用满时,则清理掉数组首位置的元素,且剩余数组元素需整体前移一位,时间复杂度为O(n)。(优化:清理的时候可以考虑一次性清理一定数量,从而降低清理次数,提高性能。)
    2.如何通过单链表实现“判断某个字符串是否为水仙花字符串”?(比如 上海自来水来自海上)
    1)前提:字符串以单个字符的形式存储在单链表中。
    2)遍历链表,判断字符个数是否为奇数,若为偶数,则不是。
    3)将链表中的字符倒序存储一份在另一个链表中。
    4)同步遍历2个链表,比较对应的字符是否相等,若相等,则是水仙花字串,否则,不是。
    六、设计思想
    时空替换思想:“用空间换时间” 与 “用时间换空间”
    当内存空间充足的时候,如果我们更加追求代码的执行速度,我们就可以选择空间复杂度相对较高,时间复杂度小相对较低的算法和数据结构,缓存就是空间换时间的例子。如果内存比较紧缺,比如代码跑在手机或者单片机上,这时,就要反过来用时间换空间的思路。

     

     

    队列

     

    什么是队列:

    队列是一种受限的线性表数据结构,只支持两个操作:

    入栈push()和出栈pop0,队列跟非常相似,支持的操作也 ,很有限,最基本的操作也是两个:入队enqueue(),放一个数据到队列尾部;出队dequeue0),从队列头部取一个元素。

    特点:

    1 . 队列跟栈一样,也是一种抽象的数据结构。

    2. 具有先进先出的特性,支持在队尾插入元素,在队头删除元素。

     

    实现:

    队列可以用数组来实现,也可以用链表来实现。

    用数组实现的栈叫作顺序栈,用链表实现的栈叫作链式栈。

    同样,用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列。

    基于数组的队列:

    代码代码

    实现思路:

    实现队列需要两个指针:一个是head指针,指向队头;一个是tail指针,指向队尾。你可以结合下面这幅图来理解。当a,b,c,d依次入队之后,队列中的head指针指向下标为0的位置, tail指针指向下标为4的位置。

    当我们调用两次出队操作之后,队列中head指针指向下标为2的位置, tail指针仍然指向下标为4的位置.

    随着不停地进行入队、出队操作, head和tail都会持续往后移动。当tail移 . ,动到最右边,即使数组中还有空闲空间,也无法继续往队列中添加数据了。这个问题该如何解决呢?

    在出队时可以不用搬移数据。如果没有空闲空间了,我们只需要在入队时,再集中触 ,发一次数据的搬移操作。

    当队列的tail指针移动到数组的最右边后,如果有新的数据入队,我们可以将 head到tail之间的数据,整体搬移到数组中0到tail-head的位置。

    基于链表的实现: 

    需要两个指针: head指针和tail指针,它们分别指向链表的第一个结,点和最后一个结点。

    如图所示,入队时, tail->next= new node, tail = tail->next:出队时, head = head->next.

     

    循环队列:

    我们刚才用数组来实现队列的时候,在tail==n时,会有数据搬移操作,这样入队操作性能就会受到影响。那有没有办法能够避免数据搬移呢?我们来看看循环队列的解决思路。循环队列,顾名思义,它长得像一个环。原本数组是有头有尾的,是一条直线。现在我们把首尾相,连,板成了一个环。我画了一张图,你可以直观地感受一下。

    我们可以看到,图中这个队列的大小为8,当前head-4, tail-7,当有一个新的元素a入队时, .我们放入下标为7的位置。但这个时候,我们并不把tail更新为8,而是将其在环中后移一位,到下标为0的位置。当再有一个元素b入队时,我们将b放入下标为0的位置,然后tail加1更新为1,所以,在a, b依次入队之后,循环队列中的元素就变成了下面的样子:

    队列为空的判断条件是head == tail,但队列满的判断条件就稍微有点复杂了。我画了一张队列满的图,你可以看一下,试着总结一下规律,

    就像我图中画的队满的情况, tail=3, head-4, n=8,所以总结一下规律就是: (3+1)%8-4,多画几张队满的图,你就会发现,当队满时, (tail+1)%n=head..你有没有发现,当队列满时,图中的tail指向的位置实际上是没有存储数据的。所以,循环队列会浪费一个数组的存储空间。

    解决浪费一个存储空间的思路:定义一个记录队列大小的值size,当这个值与数组大小相等时,表示队列已满,当tail达到最底时,size不等于数组大小时,tail就指向数组第一个位置。当出队时,size—,入队时size++

    阻塞队列和并发队列(应用比较广泛)

    阻塞队列其实就是在队列基础上增加了阻塞操作。

    简单来说,就是在队列为空的时候,从队头取数 , 据会被阻塞。因为此时还没有数据可取,直到队列中有了数据才能返回;如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。

    你应该已经发现了,上述的定义就是一个"生产者-消费者模型" !是的,我们可以使用阻塞队列,轻松实现一个"生产者-消费者模型" !这种基干阴寒队列实现的"生产者-消费者模型" ,可以有效地协调生产和消费的速度。当"生产 , 者"生产数据的速度过快, "消费者"来不及消费时,存储数据的队列很快就会满了。这个时候,生产者就阻塞等待,直到"消费者"消费了数据, "生产者"才会被唤醒继续"生产而且不仅如此,基于阻塞队列,我们还可以通过协调"生产者"和"消费者"的个数,来提高数据,的处理效率。比如前面的例子,我们可以多配置几个"消费者" ,来应对一个"生产者"

     

    小结:

    队列最大的特点就是先进先出,主要的两个操作是入队和出队。

    它既可以用数组来实现,也可以用链表来实现。用数组实现的叫顺序队列,用链表实现的叫链式队列。

    长在数组实现队列的时候,会有数据搬移操作,要想解决数据搬移的问题,我们就,需要像环一样的循环队列。要想写出没有bug的循环队列实现代码,关键要确定好队空和队满的,判定条件。

    阻塞队列、并发队列,底层都还是队列这种数据结构,只不过在之上附加了很多其他功能。阻塞队列就是入队、出队操作可以阴寒,并发队列就是队列的操作多线程安全。

    递归

     

    一、什么是递归?

    1.递归是一种非常高效、简洁的编码技巧,一种应用非常广泛的算法,比如DFS深度优先搜索、前中后序二叉树遍历等都是使用递归。
    2.方法或函数调用自身的方式称为递归调用,调用称为递,返回称为归。
    3.基本上,所有的递归问题都可以用递推公式来表示,比如
    f(n) = f(n-1) + 1; 
    f(n) = f(n-1) + f(n-2);
    f(n)=n*f(n-1);

    二、为什么使用递归?递归的优缺点?

    1.优点:代码的表达力很强,写起来简洁。
    2.缺点:空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。

    三、什么样的问题可以用递归解决呢?

    一个问题只要同时满足以下3个条件,就可以用递归来解决:
    1.问题的解可以分解为几个子问题的解。何为子问题?就是数据规模更小的问题。
    2.问题与子问题,除了数据规模不同,求解思路完全一样
    3.存在递归终止条件

    四、如何实现递归?

    1.递归代码编写
    写递归代码的关键就是找到如何将大问题分解为小问题的规律,并且基于此写出递推公式,然后再推敲终止条件,最后将递推公式和终止条件翻译成代码。
    2.递归代码理解
    对于递归代码,若试图想清楚整个递和归的过程,实际上是进入了一个思维误区。
    那该如何理解递归代码呢?如果一个问题A可以分解为若干个子问题B、C、D,你可以假设子问题B、C、D已经解决。而且,你只需要思考问题A与子问题B、C、D两层之间的关系即可,不需要一层层往下思考子问题与子子问题,子子问题与子子子问题之间的关系。屏蔽掉递归细节,这样子理解起来就简单多了。
    因此,理解递归代码,就把它抽象成一个递推公式,不用想一层层的调用关系,不要试图用人脑去分解递归的每个步骤。

    递归的关键是终止条件
    五、递归常见问题及解决方案

    1.警惕堆栈溢出:可以声明一个全局变量来控制递归的深度,从而避免堆栈溢出。
    2.警惕重复计算:通过某种数据结构来保存已经求解过的值,从而避免重复计算。

    六、如何将递归改写为非递归代码?

    笼统的讲,所有的递归代码都可以改写为迭代循环的非递归写法。如何做?抽象出递推公式、初始值和边界条件,然后用迭代循环实现。

    排序



    一、排序方法与复杂度归类
    (1)几种最经典、最常用的排序方法:冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。
    (2)复杂度归类
    冒泡排序、插入排序、选择排序 O(n^2)
    快速排序、归并排序 O(nlogn)
    计数排序、基数排序、桶排序 O(n)

    二、如何分析一个“排序算法”?
    <1>算法的执行效率
    1. 最好、最坏、平均情况时间复杂度。
    2. 时间复杂度的系数、常数和低阶。
    3. 比较次数,交换(或移动)次数。
    <2>排序算法的稳定性
    1. 稳定性概念:如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。
    2. 稳定性重要性:可针对对象的多种属性进行有优先级的排序。
    3. 举例:给电商交易系统中的“订单”排序,按照金额大小对订单数据排序,对于相同金额的订单以下单时间早晚排序。用稳定排序算法可简洁地解决。先按照下单时间给订单排序,排序完成后用稳定排序算法按照订单金额重新排序。
    <3>排序算法的内存损耗
    原地排序算法:特指空间复杂度是O(1)的排序算法。

    常见的排序算法:

     


    冒泡排序


    冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求,如果不满足就让它俩互换。

    代码:

      public int[] bubbleSort(int[] a) {
            int n = a.length;
            if (n<=1) {
                return a;
            }
            for (int i = 0; i < n; i++) {
                //提前退出冒泡循环的标志
                boolean flag = false;
                for (int j = 0; j < n-i-1; j++) {
                    if (a[j]>a[j+1]) {//
                        int temp = a[j];
                        a[j] = a[j+1];
                        a[j+1] = temp;
    
                        flag = true;//表示有数据交换
                    }
                    if (!flag) {
                        break; //没有数据交换(说明已排好序无需再进行冒泡),提前退出
                    }
                }
            }
            return a;
        }


    四、插入排序


    插入排序将数组数据分成已排序区间和未排序区间。初始已排序区间只有一个元素,即数组第一个元素。在未排序区间取出一个元素插入到已排序区间的合适位置,直到未排序区间为空。

    代码:

        public int[] insertionSort(int[] a) {
    		int n = a.length;
    		if (n<=1) return a;
    		
    		for (int i = 1; i < n; i++) {
    			int value = a[i];
    			int j = i-1;
    			for (; j >=0; j--) {
    				if (a[j] > value) {
    					a[j+1] = a[j];//移动数据
    				}else {
    					break;
    				}
    			}
    			a[j+1] = value;//插入数据
    		}
    		
    		return a;
    	}


    五、选择排序


    选择排序将数组分成已排序区间和未排序区间。初始已排序区间为空。每次从未排序区间中选出最小的元素插入已排序区间的末尾,直到未排序区间为空。
    代码:

    public int[] selectionSort(int[] a) {
    		int n = a.length;
    		
    		for (int i = 0; i < a.length - 1; i++) {
    			for (int j = i+1; j < a.length; j++) {
    				//交换
    				if (a[i] > a[j]) {
    					int temp = a[i];
    					a[i] = a[j];
    					a[j] = temp;
    				}
    			}
    		}
    		
    		return a;
    	}

    归并排序

    如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

     实现思路:

    merge-sort(p...r)表示,给下标从p到r之间的数组排序。我们将这个排序问题转化为了两个子问 ,题, merge_sort(p...q)和merge-sort(q+1..r),其中下标q等于p和r的中间位置,也就是, (p+r)/2,当下标从p到q和从q+1到r这两个子数组都排好序之后,我们再将两个有序的子数组合并在一起,这样下标从p到r之间的数据就也排好序了。

    代码:

     // 归并排序算法, a是数组,n表示数组大小
      public static void mergeSort(int[] a, int n) {
        mergeSortInternally(a, 0, n-1);
      }
    
      // 递归调用函数
      private static void mergeSortInternally(int[] a, int p, int r) {
        // 递归终止条件
        if (p >= r) return;
    
        // 取p到r之间的中间位置q
        int q = (p+r)/2;
        // 分治递归
        mergeSortInternally(a, p, q);
        mergeSortInternally(a, q+1, r);
    
        // 将A[p...q]和A[q+1...r]合并为A[p...r]
        merge(a, p, q, r);
      }
    
      private static void merge(int[] a, int p, int q, int r) {
        int i = p;
        int j = q+1;
        int k = 0; // 初始化变量i, j, k
        int[] tmp = new int[r-p+1]; // 申请一个大小跟a[p...r]一样的临时数组
       
        // 1 排序
        while (i<=q && j<=r) {
          if (a[i] <= a[j]) {
            tmp[k++] = a[i++]; // i++等于i:=i+1
          } else {
            tmp[k++] = a[j++];
          }
        }
    
        // 2 判断哪个子数组中有剩余的数据
        int start = i;
        int end = q;
        if (j <= r) {
          start = j;
          end = r;
        }
    
        // 3 将剩余的数据拷贝到临时数组tmp
        while (start <= end) {
          tmp[k++] = a[start++];
        }
    
        // 4 将tmp中的数组拷贝回a[p...r]
        for (i = 0; i <= r-p; ++i) {
          a[p+i] = tmp[i];
        }
      }
    

    merge是这样执行的:

    代码分析:

     

     

     

    快速排序

    快排的思想:    如果要排序数组中下标从p到r之间的一组数据,我们选择p到r之间的任意一个数据作为pivot (分区点) 。-我们遍历p到r之间的数据,将小于pivot的放到左边,将大于pivot的放到右边,将pivot放到中间。经过这一步骤之后,数组p到r之间的数据就被分成了三个部分,前面p到q-1之间都是小于pivot的,中间是pivot,后面的q+1到r之间是大于pivot的。

    快排利用的分而治之的思想

     

    线性排序:

    时间复杂度O(n)

    我们把时间复杂度是线性的排序算法叫作线性排序(Linear sort)常见的线性算法有: 桶排序、计数排序、基数排序

    特点:

    非基于比较的排序算法 

     

    桶排序

     

    桶排序,顾名思义,会用到“桶" ,核心思想是将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序。桶内排完序之后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了。

    对排序的数据要求苛刻:

    1, 要排序的数据需要很容易就能划分成m个桶,并且,桶与桶之间有着天然的大小顺序。

    2 ,数据在各个桶之间的分布是比较均匀的。

    3 ,桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中,数据量比较大,内存有限,无法将数据全部加载到内存中。

     

     

    计数排序

    计数排序只能用在数据范围不大的场景中,如果数据范围k比要排序的数据n大很多,就不适合用计数排序了。

    计数排序只能给非负整数排序,如果要排序的数据是其他类型的,要将其在不改变相对大小的情况下,转化为非负整数。

    代码:

     // 计数排序,a是数组,n是数组大小。假设数组中存储的都是非负整数。
      public static void countingSort(int[] a) {
    	int n = a.length;
        if (n <= 1) return;
    
        // 查找数组中数据的范围
        int max = a[0];
        for (int i = 1; i < n; ++i) {
          if (max < a[i]) {
            max = a[i];
          }
        }
    
        // 申请一个计数数组c,下标大小[0,max]
        int[] c = new int[max + 1];
        for (int i = 0; i < max + 1; ++i) {
          c[i] = 0;
        }
    
        // 计算每个元素的个数,放入c中
        for (int i = 0; i < n; ++i) {
          c[a[i]]++;
        }
    
        // 依次累加
        for (int i = 1; i < max + 1; ++i) {
          c[i] = c[i-1] + c[i];
        }
    
        // 临时数组r,存储排序之后的结果
        int[] r = new int[n];
        // 计算排序的关键步骤了,有点难理解
        for (int i = n - 1; i >= 0; --i) {
          int index = c[a[i]]-1;
          r[index] = a[i];
          c[a[i]]--;
        }
    
        // 将结果拷贝会a数组
        for (int i = 0; i < n; ++i) {
          a[i] = r[i];
        }
      }

    散列表

    什么是散列表:

    散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。

    原理:

    散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是0(1)的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组标标,从对应的数组下标的位置取数据。

    散列函数的设计要求:

    1. 散列函数计算得到的散列值是一个非负整数;.
    2. 如果key1 = key2,那hash(key1) == hash(key2);
    3. 如果key1 != key2,那hash(key1)  !=  hash(key2),

    散列函数的设计不能太复杂,散列函数生成值要尽可能随机并且均匀分布

    如果不符合3 那么就出现了散列冲突,散列冲突是无法避免的

    解决散列冲突的方法有两种: 

    开放寻址法(open addressing)和链表法(chaining)

    开放寻址法:如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。

    装在因子:  散列表中一定比例的空闲槽位。公式: 散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

    装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降。

    链表法:

    链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它要简单很多。我们来看这个图,在散列表中,每个"桶(bucket) "或者"槽(slot) "会对应一条链表,所有散列值相同的元素我们都放到相同槽位对应的链表中。

     

     

    展开全文
  • 算法与数据结构】必备知识点汇总

    千次阅读 多人点赞 2019-08-19 15:32:12
    1.数据结构基础 2.线性表(顺序存储、链式存储) 元素之间是有顺序的:第一个元素无前驱,最后一个元素无后继,其他元素都有前驱和后继 顺序存储结构:用一段地址连续的存储单元一次存储线性表的数据元素(存取...

    码字不易,喜欢请点赞!!!
    1.数据结构基础
    2.线性表(顺序存储、链式存储)

    • 元素之间是有顺序的:第一个元素无前驱,最后一个元素无后继,其他元素都有前驱和后继
    • 顺序存储结构:用一段地址连续的存储单元一次存储线性表的数据元素(存取时间复杂度为O(1),插入或删除时间复杂度为O(N),适合数据量不大并且存取操作多的数据)
    • 优缺点
      在这里插入图片描述
    • 链式结构:元素信息+后继元素的地址(读取、插入、删除:时间复杂度O(N))
    • 头指针:链表第一个结点的存储位置;
    • 尾结点:后继不存在,即最后一个结点的指针为空;
    • 头结点:第一个结点前设一个结点,可以不存储任何信息,也可以存储长度等附加信息
      在这里插入图片描述
    • 优缺点
      在这里插入图片描述

    3.

    4.队列、循环队列

    5.串

    6.树

    • 节点的度:节点的分支数目

    • 树的度:树内各个节点的度的最大值

    • 叶节点、终端节点:度为0的点

    • 树的深度:树中节点的最大层次
      在这里插入图片描述

    • 二叉树:n个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根节点和两颗互不相交、分别称为根节点的左子树和右子树的二叉树组成。

    • 二叉树的5种形态
      在这里插入图片描述

    • 满二叉树
      在这里插入图片描述

    • 完全二叉树
      在这里插入图片描述

    • 二叉树的性质

    • 二叉树的第i层,最多有2i12^{i-1}结点

    • 深度为k的二叉树,最多有2k12^k-1个节点

    • 具有n个结点的完全二叉树的深度为[log2n]+1[log_2^n]+1([x]表示对x下取整)

    • 二叉树T,叶子节点数为n0n_0,度为2的节点数为n2n_2,则n0n_0 = n2n_2 + 1
      因为节点数n = n0n_0 + n1n_1 + n2n_2 = 2n2n_2 + n1n_1 + 1
      所以:n0n_0 = n2n_2 + 1
      在这里插入图片描述

    • 对于完全二叉树的节点i:

    • 二叉树的存储

    • 一维数组存储:使用一维数组按照顺序存储,对于不存在的节点使用空来占位

    • 二叉链表:lchild+data+rchild形式
      在这里插入图片描述

    • 二叉树的遍历:前序遍历、中序遍历、后序遍历、层序遍历(逐层遍历)

    • 已知前序中序,可以确定一颗二叉树

    • 已知后序中序,可以确定一颗二叉树

    • 已知前序后序不可以确定一颗二叉树

    • 树、森林、二叉树的转换

    • 树转换成二叉树

    1.加线:兄弟节点之间加一条线
    2.去线:对每个节点只保留第一个子节点的连线,删除其他子节点的连线
    3.层次调整:第一个子节点为左孩子,兄弟节点转成第一个子节点的右孩子
    

    eg:
    在这里插入图片描述

    • 森林转成二叉树
    #森林由多棵树组成,将森林中每一颗树都视为兄弟,按照兄弟的办法来处理
    1.将每棵树转成二叉树
    2.将后面的树的根节点作为前面的树的根节点的右孩子
    

    eg:
    在这里插入图片描述

    • 二叉树转成树
    #树转成二叉树的逆过程
    1.加线:左孩子的所有右孩子,与左孩子的父节点连接起来。
    2.去线:删除原二叉树中的所有右孩子连线。
    3.层次调整:旋转
    

    eg:
    在这里插入图片描述

    • 二叉树转成森林
    #如果根节点有右孩子,则是森林,没有孩子,则是一棵树
    1.先将根节点的右孩子线删除,拆成多颗二叉树
    2.然后对每个二叉树执行拆分成树的操作
    

    eg:
    在这里插入图片描述

    • 树与森林的遍历

    • 树的遍历:先根遍历、后根遍历
      在这里插入图片描述
      在这里插入图片描述

    • 森林的遍历:前序遍历、后续遍历
      在这里插入图片描述
      前序遍历结果:ABCDEFGHJI
      后序遍历结果:BCDAFEJHIG
      在这里插入图片描述

    • 哈夫曼树

    • 简介
      在这里插入图片描述

    1.节点的带权路径:节点到根之间的路径长度与节点权值的乘积
    2.树的带权路径:树中所有节点的带权路径之和
    3.哈夫曼树:带权路径长度WPL最小的二叉树,称为哈夫曼树,也叫最优二叉树
    

    二叉树a的WPL=51+152+403+304+104=315
    二叉树b的WPL=5
    3+153+402+302+102=220
    这个结果意味着,如果有10000个学生需要计算,那么二叉树a的判断方法需要计算31500次,而二叉树b的方法需要计算22000次。

    • 哈夫曼树构造
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述

    7.图

    • 定义
      在这里插入图片描述

    • 无向边:顶点之间没有方向,称这条边为无向边,用无序偶对(vi,vj)(v_i,v_j)来表示

    • 有向边:顶点之间有方向,称这条边为有向边,也称为弧,用有序偶对&lt;vi,vj&gt;&lt;v_i,v_j&gt;来表示,如果图中任意两个顶点的边都是有向边,则称该图为有向图,要区分开弧尾vjv_j和弧头viv_i

    • 无向图:如果任意两个顶点之间都存在边,则称该图为无向完全图,含有n个顶点的无向完全图有n(n1)/2n(n−1)/2条边。

    • 有向图:如果任意两个顶点间都存在方向互为相反的两条弧,则称为有向完全图。含有n个顶点的有向完全图有n(n1)n(n−1)条边。

    • 连通图:无向图中,如果两个顶点之间有路径,说明两顶点是连通的,如果对于图中任意两个顶点都是连通的,则称该无向图是连通图。

    • 极大连通子图称为连通分量:需要是1.子图;2.子图是连通的;3.连通子图含有极大顶点数;4.具有极大顶点数的连通子图包含依附这些顶点的所有边。

    • :无向图顶点的边数叫度,有向图的顶点分为出度和入度。

    • 生成树、森林:无向图中连通且n个顶点有n-1条边叫生成树;有向图中一个顶点入度为0,其余顶点入度为1称为有向树;一个有向图由若干个有向树构成生成森林

    • 图的存储结构
      由于图的结构比较复杂,任意两点之间都可能存在联系,因此不能用简单的顺序存储结构来表示。

    • 邻接矩阵

    邻接矩阵的存储方式:两个数组来表示图;
    一个一维数组存储图中顶点的信息;
    一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
    

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    • 邻接表
    临近矩阵的问题:对边数相对顶点数较少的图,这种结构是对存储空间的极大浪费,太稀疏。
    

    在这里插入图片描述

    邻接表:将数组与链表结合起来
    

    无向图:
    在这里插入图片描述
    有向图:
    在这里插入图片描述
    带权有向图:
    在这里插入图片描述

    • 十字链表
    在有向图中,邻接表是有缺陷的,关心了出度问题,要想知道入度,就必须遍历整个图;
    反之逆邻接表解决了入度却不能解决出度;
    那能否将邻接表与逆邻接表结合起来呢?
    答案是肯定的,于是就有了一种新的有向图的存储方法:十字链表法。
    

    在这里插入图片描述

    • 邻接多重表

    • 边集数组
      边集数组是由两个一维数组构成。一个是存储顶点的信息;另一个是存储边的信息,这个边数组每个数据元素有一条边的起点下标(begin)、终点下标(end)和权(weight)组成。
      在这里插入图片描述

    • 图的遍历:深度优先搜索、广度优先搜素

    • 深度优先搜索:

    • 广度优先遍历:类似于树的层序遍历

    • 深度优先更适合目标比较明确,以找到目标为主的情况,广度优先更适合在不断扩大遍历访问时找到最优解的情况。

    • 最小生成树

    • 定义:给定一个无向图,如果他的某个子图中,任意两个顶点都能互相连通并且是一棵树,那么这棵树就叫做生成树,如果边上有权值,那么使得边权和最小的生成树叫做最小生成树。即构成连通网的最小代价生成树称为最小生成树。

    • 实际问题:我们要在n个城市中建立一个通信网络,则连通这n个城市需要布置n-1一条通信线路,这个时候我们需要考虑如何在成本最低的情况下建立这个通信网?

    • 普里姆算法—Prim算法:适合稠密图
      【算法思想】:Prime算法是一种贪心算法,它最初将无向连通图G中所有顶点V分成两个顶点集合VA和VB。在计算过程中VA中的点为已经选好连接入生成树的点,否则属于VB。最开始的时候VA只包含任意选取的图G中的一个点u,其余的点属于VB,每次添加一个VB中的点到VA,该点是集合VB到集合VA中距离最小的一个点。直到V个顶点全部属于VA,算法结束。显然出发点不同,最小生成树的形态就不同,但边权和的最小值是唯一的。
      eg:
      下面我们对下面这幅图求其最小生成树:
      在这里插入图片描述
      假设我们从顶点v1开始,所以我们可以发现(v1,v3)边的权重最小,所以第一个输出的边就是:v1—v3=1:
      在这里插入图片描述
      然后,我们要从v1和v3作为起点的边中寻找权重最小的边,首先了(v1,v3)已经访问过了,所以我们从其他边中寻找,发现(v3,v6)这条边最小,所以输出边就是:v3—-v6=4
      在这里插入图片描述
      然后,我们要从v1、v3、v6这三个点相关联的边中寻找一条权重最小的边,我们可以发现边(v6,v4)权重最小,所以输出边就是:v6—-v4=2.
      在这里插入图片描述
      然后,我们就从v1、v3、v6、v4这四个顶点相关联的边中寻找权重最小的边,发现边(v3,v2)的权重最小,所以输出边:v3—–v2=5
      在这里插入图片描述
      然后,我们就从v1、v3、v6、v4,v2这2五个顶点相关联的边中寻找权重最小的边,发现边(v2,v5)的权重最小,所以输出边:v2—–v5=3
      在这里插入图片描述
      最后,我们发现六个点都已经加入到集合U了,我们的最小生成树建立完成。
      【算法步骤】
      选定图中的任意一个顶点v0,从v0开始生成最小生成树。
      (1)初始化dist[v0]=0,其他点的距离值dist[i]=∞。其中dist[i]表示集合VB中的点到VA中的点的距离值。
      (2)经过N次如下步骤操作,最后得到一棵含N个顶点,N-1条边的最小生成树:
      ①选择一个未标记的点k,并且dist[k]的值是最小的
      ②标记点k进入集合VA
      ③以k为中间点,修改未标记点j,即VB中的点到VA的距离值
      (3)得到最小生成树T。

    • 克鲁斯卡算法—Kruskal算法:适合稀疏图
      【算法思想】:Kruskal算法也是一种贪心算法,它是将边按权值排序,每次从剩下的边集中选择权值最小且两个端点不在同一集合的边加入生成树中,反复操作,直到加入了n-1条边。
      【算法步骤】
      (1)将G中的边按权值从小到大快排。
      (2)按照权值从小到大依次选边。若当前选取的边加入后使生成树T形成环,则舍弃当前边,否则标记当前边并计数。
      (3)重复(2)的操作,直到生成树T中包含n-1条边,否则当遍历完所有边后,选取不到n-1条边,表示最小生成树不存在。
      【算法实现】Kruskal算法
      算法的关键在于如何判定新加入的边会不会使图G’产生环,在这里用并查集,如果新加入的边的两个端点在并查集的同一集合中,说明存在环,需要舍弃这条边,否则保留当前边,并合涉及的两个集合。

    • 最短路径

    • 迪杰斯特拉算法(Dijkstra):单源最短路径
      【算法思想】:首先将图中的顶点分成两组,第一组S中包括已经确定最短路径的顶点(初始情况包含源点);第二组V-S中包括还未确定最短路径的顶点。然后按照路径长度递增的顺序计算源点到各顶点的最短路径,逐个将第二组中的数据加入到第一组中,直到S = V。
      在这里插入图片描述
      【算法实现】Dijkstra
      【动态演示】
      这里写图片描述

    • 弗洛伊德算法(Floyd):任意两个点对最短路径
      【算法思想】:用简单的语言来解释,就是对于点Vi到Vj的距离,如果存在点Vk,使得点Vi到点Vk的距离加上点Vj到点Vk的距离之和小于点Vi到Vj的距离,那么就用点Vi到点Vk的距离加上点Vj到点Vk的距离之和去替代点Vi到Vj的距离。在这里插入图片描述
      【算法实现】Floyd
      【结果展示】
      在这里插入图片描述

    8.查找和排序算法

    • 顺序查找
    • 二分查找(折半查找)
    • Hash查找
    • 二叉排序树:左子树小于根节点,右子树大于根节点
    • 冒泡排序
    • 短冒泡排序
    • 选择排序
    • 插入排序
    • 希尔排序
    • 归并排序
    • 快速排序
    • 堆排序:大根堆(每个节点的值都大于其左右子节点的值);小根堆(每个节点的值都小于其左右子节点的值)
      在这里插入图片描述

    参考链接:
    https://blog.csdn.net/Asher117/article/details/89306091
    https://blog.csdn.net/Asher117/article/details/89351068
    https://blog.csdn.net/Asher117/article/details/93647879
    https://mp.weixin.qq.com/s/GjqKMEwLHq16FaXdoHy8xA
    https://blog.csdn.net/jiaoyangwm/article/details/80808235
    https://blog.csdn.net/dengpei187/article/details/51899550
    https://mp.weixin.qq.com/s/Oyk7_vR3KtIBXf5AnhmWNQ
    https://blog.csdn.net/qq_39826163/article/details/81660819
    https://mp.weixin.qq.com/s/LCs2wmfCGw9oc3d1hkJn2w
    https://mp.weixin.qq.com/s/Iul7pHHiAsun80Dad9jqkw
    https://blog.csdn.net/qq_38499859/article/details/79122634
    https://blog.csdn.net/Asher117/article/details/89500637

    展开全文
  • 数据结构与算法】常见数据结构及基本操作

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

    万次阅读 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 { ...
  • 在线练习在线编程面试数据结构算法贪心算法位运算复杂度分析视频教程面试宝典计算机科学资讯文件结构在线练习LeetCodeVirtual JudgeCareerCupHackerRankCodeFightsKattisHackerEarthCodilityCode ForcesCode ...
  • 常用数据结构与常用算法

    万次阅读 2018-08-08 20:32:54
    1. 常见数据结构 人们进行程序设计时通常关注两个重要问题,一是如何将待处理的数据存储到计算机内存中,即数据表示;...可以看出数据结构算法是程序的两个重要组成部分,数据结构是指数据的逻辑结构和存储方法...
  • 数据结构与算法(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
  • 数据结构与算法中的经典算法

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

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

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

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

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

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

    万次阅读 多人点赞 2014-11-17 22:23:35
    1. 2. 很酷的各种排序演示:
  • (强烈推荐!!!)数据结构与算法学习

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

算法与数据结构