常见数据结构与算法_常见的数据结构与算法 - CSDN
精华内容
参与话题
  • 数据结构与算法常见笔试题

    万次阅读 多人点赞 2017-09-10 22:25:46
    1.数据结构与算法常见笔试题   第一章 数据结构与算法 一.算法的基本概念 计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 1.算法的基本特征:可行性,确定性,有穷性,拥有足够的情报。 2....

    1.数据结构与算法常见笔试题  

     

    第一章 数据结构与算法

    .算法的基本概念

    计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。

    1.算法的基本特征:可行性,确定性,有穷性,拥有足够的情报。

    2.算法的基本要素:算法中对数据的运算和操作、算法的控制结构。

    3.算法设计的基本方法:列举法、归纳法、递推、递归、减半递推技术、回溯法。

    4.算法设计的要求:正确性、可读性、健壮性、效率与低存储量需求


    .算法的复杂度

    1.算法的时间复杂度:指执行算法所需要的计算工作量

    2.算法的空间复杂度:执行这个算法所需要的内存空间


    .数据结构的定义

    1.数据的逻辑结构:反映数据元素之间的关系的数据元素集合的表示。数据的逻辑结构包括集合、线形结构、树形结构和图形结构四种。

    2.数据的存储结构:数据的逻辑结构在计算机存储空间种的存放形式称为数据的存储结构。常用的存储结构有顺序、链接、索引等存储结构。


    .数据结构的图形表示

    在数据结构中,没有前件的结点称为根结点;没有后件的结点成为终端结点。插入和删除是对数据结构的两种基本运算。还有查找、分类、合并、分解、复制和修改等。


    .线性结构和非线性结构

    根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类型:线性结构和非线性结构。

    线性结构:非空数据结构满足:有且只有一个根结点;每个结点最多有一个前件,最多只有一个后件。非线性结构:如果一个数据结构不是线性结构,称之为非线性结构。

    常见的线性结构:线性表、栈、队列


    .线性表的定义

    线性表是n个元素构成的有限序列(A1A2A3……)。表中的每一个数据元素,除了第一个以外,有且只有一个前件。除了最后一个以外有且只有一个后件。即线性表是一个空表,或可以表示为(a1,a2,……an,其中ai(I=1,2,……n)是属于数据对象的元素,通常也称其为线性表中的一个结点。

    非空线性表有如下一些特征:

    1)有且只有一个根结点a1,它无前件;

    2)有且只有一个终端结点an,它无后件;

    3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n=0时称为空表。


    6.1线性表的顺序存储结构

    线性表的顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元素。

    线性表的顺序存储结构具备如下两个基本特征:

    1.线性表中的所有元素所占的存储空间是连续的;

    2.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

    线性表逻辑上相邻、物理也相邻,则已知第一个元素首地址和每个元素所占字节数,则可求出任一个元素首地址。

    假设线性表的每个元素需占用K个存储单元,并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系:

    LOC(ai+1)=LOC(ai)+K

    LOC(ai)=LOC(a1)+(i-1)*K     

    其中,LOC(a1)是线性表的第一个数据元素a1的存储位置,通常称做线性表的起始位置或基地址。

    因为在顺序存储结构中,每个数据元素地址可以通过公式①计算得到,所以线性表的顺序存储结构是随机存取的存储结构。

    在线性表的顺序存储结构下,可以对线性表做以下运算:

    插入、删除、查找、排序、分解、合并、复制、逆转


    6.1.1顺序表的插入运算

    线性表的插入运算是指在表的第i个位置上,插入一个新结点x,使长度为n的线性表(a1,a2aian)变成长度为n+1的线性表(a1,a2x,aian).

    该算法的时间主要花费在循环的结点后移语句上,执行次数是n-I+1

    I=n+1,最好情况,时间复杂度o(1)I=1,最坏情况,时间复杂度o(n)

    算法的平均时间复杂度为o(n)


    6.1.2顺序表的删除运算

    线性表的删除运算是指在表的第I个位置上,删除一个新结点x,使长度为n的线性表(a1,a2aian)变成长度为n-1的线性表(a1,a2ai-1,ai+1an).

    I=n,时间复杂度o(1),I=1,时间复杂度o(n) ,平均时间复杂度为o(n)


    6.2栈及其基本运算

    1. 什么是栈? 栈实际上也是一个线性表,只不过是一种特殊的线性表。栈是只能在表的一端进行插入和删除运算的线性表,通常称插入、删除这一端为栈顶(TOP),另一端为 栈底(BOTTOM)。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素,从而也是最先被删除的元素;栈底元素总是最先被插入的元素,从而也是最后 才能被删除的元素。

    假设栈S=a1,a2,a3,……an),则a1称为栈底元素,an称为栈顶元素。栈中元素按a1,a2,a3……an的次序进栈,退栈的第一个元素应该是栈顶元素。即后进先出。


    6.2.1栈的顺序存储及其运算

    S1M)作为栈的顺序存储空间。M为栈的最大容量。

    栈的基本运算有三种:入栈、退栈与读栈顶元素。

    入栈运算:在栈顶位置插入一个新元素。

    首先将栈顶指针进一(TOP+1),然后将新元素插入到栈顶指针指向的位置。

    退栈运算:指取出栈顶元素并赋给一个指定的变量。

    首先将栈顶元素赋给一个指定的变量,然后将栈顶指针退一(TOP-1

    读栈顶元素:将栈顶元素赋给一个指定的变量。栈顶指针不会改变。

    6.3.队列及其基本运算

    1.什么是队列

    队列是只允许在一端删除,在另一端插入的顺序表,允许删除的一端叫做对头,允许插入的一端叫做对尾。

    队列的修改是先进先出。往队尾插入一个元素成为入队运算。从对头删除一个元素称为退队运算。

    2.循环队列及其运算

    实际应用中,队列的顺序存储结构一般采用循环队列的形式。所谓循环队列,就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间。在循环队列中,,用队尾指针rear指向队列中的队尾元素,用排头指针front指向排头元素的前一个位置,因此,从排头指针front指向的后一个位置直到队 尾指针 rear指向的位置之间所有的元素均为队列中的元素。

    在实际使用循环队列时,为了能区分队满还是队列空,通常需要增加一个标志S

    队列空,则S=0rear=front=m     队列满,则S=1rear=front=m

    循环队列主要有两种基本运算:入队运算和退队运算

    入队运算

    指在循环队列的队尾加入一个新元素,首先rear=rear+1,rear=m+1时,置rear=1,然后将新元素插入到队尾指针指向的位置。当S=1rear=front,说明队列已满,不能进行入队运算,称为“上溢”。

    退队运算

    指在循环队列的排头位置退出一个元素并赋给指定的变量。首先front=front+1,并当front=m+1时,置front=1,然后将排头指针指向的元素赋给指定的变量。当循环队列为空S=0,不能进行退队运算,这种情况成为“下溢”。


    6.4线性单链表的结构及其基本运算

    1.线性单链表的基本概念

    组任意的存储单元存储线性表的数据元素,因此,为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素ai的存储映象,成为结点。它包括两个域:其中存储数据元素信息的域称为数据域,存储直接后继存储位置的域称为指针域。指针域中存储的信息称做指针或链。n个结点链结成一个链表,即为线性表(a1, a2,……,an)的链式存储结构。又由于此链表的每个结点中只包含一个指针域,故又称线性链表或单链表。

    有时,我们在单链表的第一个结点之前附设一个结点,称之为头结点,它指向表中第一个结点。头结点的数据域可以不存储任何信息,也可存储如线性表的长度等类的附加信息,头结点的指针域存储指向第一个结点的指针(即第一个元素结点的存储位置)。

    在单链表中,取得第I个数据元素必须从头指针出发寻找,因此,单链表是非随机存取的存储结构  链表的形式:单向,双向

    2.线性单链表的存储结构

    3.带列的栈与队列

    栈也是线性表,也可以采用链式存储结构。

    队列也是线性表,也可以采用链式存储结构。


    6.4.1线性链表的基本运算1.线性链表的插入2.线性链表的删除


    6.5双向链表的结构及其基本运算

    在双向链表的结点中有两个指针域,其一指向直接后继,另一指向直接前驱。


    6.6循环链表的结构及其基本运算

    是另一种形式的链式存储结构,它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。因此,从表中任一结点出发均可找到表中其他结点。


    7.树的定义

    树是一种简单的非线性结构。树型结构的特点:

    1.每个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点。

    2.每一个结点可以有多个后件结点,称为该结点的子结点。没有后件的结点称为叶子结点

    3.一个结点所拥有的后件个数称为树的结点度

    4.树的最大层次称为树的深度。


    7.1二叉树的定义及其基本性质

    7.1.1二叉树是另一种树型结构,它的特点是每个结点至多只有二棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。

    7.1.2二叉树的基本性质

    ①在二叉树的第I层上至多有2i-1个结点。

    ②深度为k的二叉树至多有2k-1个结点(k>=1)

    ③在任意一个二叉树中,度为0的结点总是比度为2的结点多一个;

    ④具有n 个结点的二叉树,其深度至少为[log2n]+1

    一棵深度为k且有2k-1个结点的二叉树称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。

    7.1.3满二叉树与完全二叉树

    满二叉树:除最后一层以外,每一层上的所有结点都有两个子结点。在满二叉树的第K层上有2K-1个结点,且深度为M的满二叉树右2M-1个结点

    完全二叉树:除最后一层以外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。具有N个结点的完全二叉树的深度为[log2n]+1

    完全二叉树总结点数为N

    N为奇数,则叶子结点数为(N+1/2N为偶数,则叶子结点数为N/2

    7.1.4二叉树的存储结构

    二叉树通常采用链式存储结构

    二叉树具有下列重要特性:

        性质1 在二叉树的第i层上至多有2i-1个结点(i1)

         利用归纳法容易证得此性质。

         i=1时,只有一个根结点。 显然,2i-1=20=1是对的。

         现在假定对所有的j1j

         由归纳假设:第i-1层上至多有2i-2个结点。由于二叉树的每个结点的度至多为2,故在第i层上的最大结点数为第i-1层上的最大结点数的2倍,即2*2i-2=2i-1

        性质2 深度为k的二叉树至多有2k-1个结点,(k1)

        由性质1可见,深度为k的二叉树的最大结点数为

    k                        k

    (i层上的最大结点数) =2i-1=2k -1

    i=1                     i=1

        性质3 对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1

     

         n1为二叉树T中度为1的结点数。因为二叉树中所有结点的度均小于或等于2所以其结点总数为

     

    n=n0+n1+n2 (61) 

         再看二叉树中的分支数。除了根结点外,其余结点都有一个分支进入,设B为分支总数,则n=B+1。由于这些分支是由度为12的结点射出的,所以又有B=n1+ 2n2

     

    n=n1+2*n2+1 (62) 

         于是得由式(61)(62)n0=n2+1

     

    7.1.5二叉树的遍历

    就是遵从某种次序,访问二叉树中的所有结点,使得每个结点仅被访问一次。一般先左后右。

    1.前序遍历DLR首先访问根结点,然后遍历左子树,最后遍历右子树。

    2.中序遍历LDR首先遍历左子树,然后根结点,最后右子树

    3.后序遍历LRD首先遍历左子树,然后遍历右子树,最后访问根结点。


    8.查找

    8.1顺序查找与二分查找

    1.顺序查找 在两种情况下只能用顺序查找:线性表为无序表、链式存储结构的有序表

    2.二分查找 只适用于顺序存储的有序表(从小到大)。

    对于长度为N的有序线性表,在最坏情况下,二分查找只需要比较log2N次,而顺序查找要比较N次。 排序:指将一个无序序列整理成按值非递减顺序排列的有序序列。


    8.2交换类排序法

    冒泡排序与快速排序法属于交换类的排序方法

    1.冒泡排序法 假设线性表的长度为N,则在最坏的情况下,冒跑排序需要经过N/2遍的从前往后的扫描和N/2遍的从后往前的扫描,需要的比较次数为NN-1/2

    2.快速排序法

    8.3选择类排序法 1.简单选择排序法2.堆排序法

    8.4插入类排序法 1.简单插入排序法2.希尔排序法

                             最坏情况下      最好情况下     说明

     交换排序      冒泡排序     n(n-1)/2            最简单的交换排序。在待排序的元素序列基本有序的前提下,效率最高

         快速排序      n(n-1)/2      O(Nlog2 N)     

     插入排序      简单插入排序     n(n-1)/2            每个元素距其最终位置不远时适用

         希尔排序      O(n1.5)           

     选择排序      简单选择排序     n(n-1)/2           

         堆排序      O(nlog2n)            适用于较大规模的线性表


    练习:

    1.栈和队列的共同特点是(只允许在端点处插入和删除元素)

    2.如果进栈序列为e1,e2,e3,e4,则可能的出栈序列是(e2,e4,e3,e1

    3.栈底至栈顶依次存放元素ABCD,在第五个元素E入栈前,栈中元素可以出栈,则出栈序列可能是(DCBEA

    4.栈通常采用的两种存储结构是(线性存储结构和链表存储结构)

    5.下列关于栈的叙述正确的是(D

         A.栈是非线性结构B.栈是一种树状结构C.栈具有先进先出的特征D.栈有后进先出的特征

    6.链表不具有的特点是(BA.不必事先估计存储空间      B.可随机访问任一元素

    C.插入删除不需要移动元素      D.所需空间与线性表长度成正比

    7.用链表表示线性表的优点是(便于插入和删除操作)

    8.在单链表中,增加头结点的目的是(方便运算的实现)

    9.循环链表的主要优点是(从表中任一结点出发都能访问到整个链表)

    10.线性表L=(a1,a2,a3,……ai,……an),下列说法正确的是(D

         A.每个元素都有一个直接前件和直接后件   B.线性表中至少要有一个元素

         C.表中诸元素的排列顺序必须是由小到大或由大到小

         D.除第一个和最后一个元素外,其余每个元素都有一个且只有一个直接前件和直接后件

    11.线性表若采用链式存储结构时,要求内存中可用存储单元的地址(D

    A.必须是连续的 B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以

    12.线性表的顺序存储结构和线性表的链式存储结构分别是(随机存取的存储结构、顺序存取的存储结构)

    13.树是结点的集合,它的根结点数目是(有且只有1

    14.在深度为5的满二叉树中,叶子结点的个数为(31

    15.具有3个结点的二叉树有(5种形态)

    16.设一棵二叉树中有3个叶子结点,有8个度为1的结点,则该二叉树中总的结点数为(13

    17.已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是(cedba

    18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFHDBGEACHF,则该二叉树的后序遍历为(DGEBHFCA

    19.若某二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是(gdbehfca

    20.数据库保护分为:安全性控制、 完整性控制 、并发性控制和数据的恢复。

     

    1. 在计算机中,算法是指(解题方案的准确而完整的描述)

    2.在下列选项中,哪个不是一个算法一般应该具有的基本特征(无穷性)

    说明:算法的四个基本特征是:可行性、确定性、有穷性和拥有足够的情报。

    3. 算法一般都可以用哪几种控制结构组合而成(顺序、选择、循环)

    4.算法的时间复杂度是指(算法执行过程中所需要的基本运算次数)

    5. 算法的空间复杂度是指(执行过程中所需要的存储空间)

    6. 算法分析的目的是(分析算法的效率以求改进)

    7. 下列叙述正确的是(C

    A.算法的执行效率与数据的存储结构无关

    B.算法的空间复杂度是指算法程序中指令(或语句)的条数

    C.算法的有穷性是指算法必须能在执行有限个步骤之后终止

    D.算法的时间复杂度是指执行算法程序所需要的时间

    8.数据结构作为计算机的一门学科,主要研究数据的逻辑结构、对各种数据结构进行的运算,以及(数据的存储结构)

    9. 数据结构中,与所使用的计算机无关的是数据的(C

    A.存储结构   B.物理结构    C.逻辑结构    D.物理和存储结构

    10. 下列叙述中,错误的是(B

    A.数据的存储结构与数据处理的效率密切相关

    B.数据的存储结构与数据处理的效率无关

    C.数据的存储结构在计算机中所占的空间不一定是连续的

    D.一种数据的逻辑结构可以有多种存储结构

    11. 数据的存储结构是指(数据的逻辑结构在计算机中的表示)

    12. 数据的逻辑结构是指(反映数据元素之间逻辑关系的数据结构)

    13. 根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为(线性结构和非线性结构)

    14. 下列数据结构具有记忆功能的是(CA.队列B.循环队列C.栈D.顺序表

    15. 下列数据结构中,按先进后出原则组织数据的是(B

    A.线性链表   B.栈           C.循环链表       D.顺序表

    16. 递归算法一般需要利用(队列)实现。

    17. 下列关于栈的叙述中正确的是(DA.在栈中只能插入数据B.在栈中只能删除数据

    C.栈是先进先出的线性表            D.栈是先进后出的线性表

    18. 栈底至栈顶依次存放元素ABCD,在第五个元素E入栈前,栈中元素可以出栈,则出栈序列可能是(DCBEA

    19.如果进栈序列为e1,e2,e3,e4,则可能的出栈序列是(e2,e4,e3,e1

    20. 由两个栈共享一个存储空间的好处是(节省存储空间,降低上溢发生的机率)

    21. 应用程序在执行过程中,需要通过打印机输出数据时,一般先形成一个打印作业,将其存放在硬盘中的一个指定(队列)中,当打印机空闲时,就会按先来先服务的方式从中取出待打印的作业进行打印。

    22.下列关于队列的叙述中正确的是(CA.在队列中只能插入数据B.在队列中只能删除数据  C.队列是先进先出的线性表           D.队列是先进后出的线性表

    23.下列叙述中,正确的是(DA.线性链表中的各元素在存储空间中的位置必须是连续的

    B.线性链表中的表头元素一定存储在其他元素的前面 C.线性链表中的各元素在存储空间中的位置不一定是连续的,但表头元素一定存储在其他元素的前面D.线性链表中的各元素在存储空间中的位置不一定是连续的,且各元素的存储顺序也是任意的

    24.下列叙述中正确的是(AA.线性表是线性结构     B.栈与队列是非线性结构

    C.线性链表是非线性结构                                 D.二叉树是线性结构

    25. 线性表L=(a1,a2,a3,……ai,……an),下列说法正确的是(D

    A.每个元素都有一个直接前件和直接后件      B.线性表中至少要有一个元素

    C.表中诸元素的排列顺序必须是由小到大或由大到小D.除第一个元素和最后一个元素外,其余每个元素都有一个且只有一个直接前件和直接后件

    26.线性表若采用链式存储结构时,要求内存中可用存储单元的地址(连续不连续都可以)

    27. 链表不具有的特点是(BA.不必事先估计存储空间           B.可随机访问任一元素

    C.插入删除不需要移动元素            D.所需空间与线性表长度成正比

    28. 非空的循环单链表head的尾结点(由p所指向),满足(p->next=head

    29.与单向链表相比,双向链表的优点之一是(更容易访问相邻结点)

    30. 在(D)中,只要指出表中任何一个结点的位置,就可以从它出发依次访问到表中其他所有结点。A.线性单链表           B.双向链表           C.线性链表           D.循环链表

    31. 以下数据结构属于非线性数据结构的是(CA.队列     B.线性表C.二叉树     D.栈

    32.树是结点的集合,它的根结点数目是(有且只有1

    33.具有3个结点的二叉树有(5种形态)

    34. 在一棵二叉树上第8层的结点数最多是(128) 注:2K-1

    35. 在深度为5的满二叉树中,叶子结点的个数为(16) 注:2n-1

    36. 在深度为5的满二叉树中,共有(31)个结点。 注:2n1

    37.设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点数为(350

    说明:完全二叉树总结点数为N,若N为奇数,则叶子结点数为(N+1/2;若N为偶数,则叶子结点数为N/2

    38. 设有下列二叉树,对此二叉树中序遍历的结果是(B

    AABCDEF     

    BDBEAFC

    CABDECF     

    DDEBFCA

    39.已知二叉树后序遍历序列是dabec,中序遍历序列debac,它的前序遍历序列是(cedba

    40. 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFHDBGEACHF,则该二叉树的后序遍历为(DGEBHFCA

    41.若某二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是(gdbehfca

    42. 串的长度是(串中所含字符的个数)

    43.设有两个串pq,求qp中首次出现位置的运算称做(模式匹配)

    44. N个顶点的连通图中边的条数至少为(N-1

    45.N个顶点的强连通图的边数至少有(N

    46.对长度为n的线性表进行顺序查找,在最坏情况下所需要的比较次数为(N

    47. 最简单的交换排序方法是(冒泡排序)

    48.假设线性表的长度为n,则在最坏情况下,冒泡排序需要的比较次数为(n(n-1)/2

    49. 在待排序的元素序列基本有序的前提下,效率最高的排序方法是(冒泡排序)

    50. 在最坏情况下,下列顺序方法中时间复杂度最小的是(堆排序)

    51. 希尔排序法属于(插入类排序)

    52. 堆排序法属于(选择类排序)

    53. 在下列几种排序方法中,要求内存量最大的是(归并排序)

    54. 已知数据表A中每个元素距其最终位置不远,为节省时间,应采用(直接插入排序)

    55. 算法的基本特征是可行性、确定性、 有穷性   和拥有足够的情报。

     

     

    1.一个算法通常由两种基本要素组成:一是对数据对象的运算和操作,二是算法的控制结构。

    1. 算法的复杂度主要包括时间复杂度和 空间 复杂度。

    2. 实现算法所需的存储单元多少和算法的工作量大小分别称为算法的空间复杂度和时间复杂度 。

    3.所谓数据处理是指对数据集合中的各元素以各种方式进行运算,包括插入、删除、查找、更改等运算,也包括对数据元素进行分析。

    4.数据结构是指相互有关联的 数据元素 的集合。

    5.数据结构分为逻辑结构与存储结构,线性链表属于 存储结构 。

    6.数据结构包括数据的 逻辑 结构和数据的存储结构。

    7. 数据结构包括数据的逻辑结构、数据的 存储结构 以及对数据的操作运算。

    8.数据元素之间的任何关系都可以用 前趋和后继 关系来描述。

    9.数据的逻辑结构有线性结构和非线性结构两大类。

    10.常用的存储结构有顺序、链接、 索引 等存储结构。

    11. 顺序存储方法是把逻辑上相邻的结点存储在物理位置   相邻 的存储单元中。

    12. 栈的基本运算有三种:入栈、退栈与读栈顶元素 。

    13. 队列主要有两种基本运算:入队运算与 退队运算 。

    14. 在实际应用中,带链的栈可以用来收集计算机存储空间中所有空闲的存储结点,这种带链的栈称为 可利用栈 。

    15.栈和队列通常采用的存储结构是 链式存储和顺序存储   

    16.当线性表采用顺序存储结构实现存储时,其主要特点是 逻辑结构中相邻的结点在存储结构中仍相邻 。

    17. 循环队列主要有两种基本运算:入队运算与退队运算。每进行一次入队运算,队尾指针就 进1

    18.当循环队列非空且队尾指针等于对头指针时,说明循环队列已满,不能进行入队运算。这种情况称为 上溢  

    19.当循环队列为空时,不能进行退队运算,这种情况称为 下溢 。

    20. 在一个容量为25的循环队列中,若头指针front=16,尾指针rear=9,则该循环队列中共有18个元素。注:当rear

    rear>front时,元素个数=rearfront

    21. 在一个容量为15的循环队列中,若头指针front=6,尾指针rear=9,则该循环队列中共有3个元素。

    22.顺序查找一般是指在 线性表 中查找指定的元素。

    23.在计算机中存放线性表,一种最简单的方法是 顺序存储 。

    24.在程序设计语言中,通常定义一个 一维数组 来表示线性表的顺序存储空间。

    25.在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数据元素值,称为数据域,另一部分用于存放指针,称为 指针域 。其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。

    26.在 线性单链表中 ,每一个结点只有一个指针域,由这个指针只能找到后继结点,但不能找到前驱结点。

    27. 为了要在线性链表中插入一个新元素,首先要给该元素分配一个 新结点 ,以便用于存储该元素的值。

    28. 在线性链表中删除一个元素后,只需要改变被删除元素所在结点的前一个结点的 指针域 即可。

    29. 用链表表示线性表的突出优点是 便于插入和删除操作 。

    30. 在树形结构中,树根结点没有   前件 。

    31. 在树结构中,一个结点所拥有的后件个数称为该结点的度。叶子结点的度为 0

    32. 设一棵二叉树中有3个叶子结点,8个度为1的结点,则该二叉树中总的结点数为13

    33. 设一棵完全二叉树共有739个结点,则在该二叉树中有370个叶子结点。

    34. 设一棵完全二叉树共有700个结点,则在该二叉树中有350个叶子结点。

    35. 在先左后右的原则下,根据访问根结点的次序,二叉树的遍历可以分为三种:前序遍历、 中序 遍历和后序遍历。

    36. 若串S="Program",则其子串的数目是29。 注:n(n+1)/2+1

    37. 若串S=MathTypes”,则其子串的数目是46

    38. 对长度为n的线性表进行插入一个新元素或删除一个元素时,在最坏情况下所需要的比较次数为n

    39. 在长度为n的有序线性表中进行顺序查找。最坏的情况下,需要的比较次数为  n   

    40. 在长度为n的有序线性表中进行二分查找。最坏的情况下,需要的比较次数为log2n

    41. 长度为n的顺序存储线性表中,当在任何位置上插入一个元素概率都相等时,插入一个元素所需移动元素的平均个数为n/2

    42. 排序是计算机程序设计中的一种重要操作,常见的排序方法有插入排序、 交换排序 和选择排序等。

    43. 快速排序法可以实现通过一次交换而消除多个 逆序 。

    44. 快速排序法的关键是对线性表进行 分割 。

    45. 冒泡排序算法在最好的情况下的元素交换次数为 0

    46. 在最坏情况下,冒泡排序的时间复杂度为 n(n-1) /2

    47. 对于长度为n的线性表,在最坏情况下,快速排序所需要的比较次数为n(n-1) /2

    48.在最坏情况下,简单插入排序需要比较的次数为 n(n-1) /2

    49.在最坏情况下,希尔排序需要比较的次数为 O(n1.5)。注:括号里是n1.5次方。

    50. 在最坏情况下,简单选择排序需要比较的次数为 n(n-1) /2

    51. 在最坏情况下,堆排序需要比较的次数为 o(nlog2n)

    52.对于输入为N个数进行快速排序算法的平均时间复杂度是O(Nlog2 N) 

     

    展开全文
  • 面试中常见数据结构与算法

    万次阅读 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. 根据记忆化搜索方法该出动态规划方法,进而看看是否能化简,如果能化简,还能实现时间复杂度更低的动态规划方法。
    展开全文
  • 下面是自己整理的常用数据结构与算法相关内容,如有错误,欢迎指出。 为了便于描述,文中涉及到的代码部分都是用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
     

    展开全文
  • 五、常见算法题 六、总结 一、概述 以前看到这样一句话,语言只是工具,算法才是程序设计的灵魂。的确,算法在计算机科学中的地位真的很重要,在很多大公司的笔试面试中,算法掌握程度的考察都占据了很大一部分...
    一、概述
    二、查找算法
    三、排序算法
    四、其它算法
    五、常见算法题
    六、总结

    一、概述

    以前看到这样一句话,语言只是工具,算法才是程序设计的灵魂。的确,算法在计算机科学中的地位真的很重要,在很多大公司的笔试面试中,算法掌握程度的考察都占据了很大一部分。不管是为了面试还是自身编程能力的提升,花时间去研究常见的算法还是很有必要的。下面是自己对于算法这部分的学习总结。

    算法简介

    算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。对于同一个问题的解决,可能会存在着不同的算法,为了衡量一个算法的优劣,提出了空间复杂度与时间复杂度这两个概念。

    时间复杂度

    一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记为 T(n) = O(f(n)) ,它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度。这里需要重点理解这个增长率。
    举个例子,看下面3个代码:

    1{++x;}
    
    2for(i = 1; i <= n; i++) { ++x; }
    
    3for(j = 1; j <= n; j++) 
            for(j = 1; j <= n; j++) 
                 { ++x; }
    
    上述含有 ++x 操作的语句的频度分别为1 、n 、n^2,
    
    假设问题的规模扩大了n倍,3个代码的增长率分别是1 、n 、n^2
    
    它们的时间复杂度分别为O(1)、O(n )、O(n^2)

    空间复杂度

    空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

    二、查找算法

    查找和排序是最基础也是最重要的两类算法,熟练地掌握这两类算法,并能对这些算法的性能进行分析很重要,这两类算法中主要包括二分查找、快速排序、归并排序等等。

    顺序查找

    顺序查找又称线性查找。它的过程为:从查找表的最后一个元素开始逐个与给定关键字比较,若某个记录的关键字和给定值比较相等,则查找成功,否则,若直至第一个记录,其关键字和给定值比较都不等,则表明表中没有所查记录查找不成功,它的缺点是效率低下。

    二分查找

    • 简介

    二分查找又称折半查找,对于有序表来说,它的优点是比较次数少,查找速度快,平均性能好。

    二分查找的基本思想是将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果
    x < a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x。

    二分查找的时间复杂度为O(logn)

    • 实现
    //给定有序查找表array 二分查找给定的值data
    //查找成功返回下标 查找失败返回-1
    
    static int funBinSearch(int[] array, int data) {
    
        int low = 0;
        int high = array.length - 1;
    
        while (low <= high) {
    
            int mid = (low + high) / 2;
    
            if (data == array[mid]) {
                return mid;
            } else if (data < array[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    三、排序算法

    排序是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。下面主要对一些常见的排序算法做介绍,并分析它们的时空复杂度。


    常见排序算法

    常见排序算法性能比较:


    常见排序算法

    上面这张表中有稳定性这一项,排序的稳定性是指如果在排序的序列中,存在前后相同的两个元素的话,排序前和排序后他们的相对位置不发生变化。
    下面从冒泡排序开始逐一介绍。

    冒泡排序

    • 简介

    冒泡排序的基本思想是:设排序序列的记录个数为n,进行n-1次遍历,每次遍历从开始位置依次往后比较前后相邻元素,这样较大的元素往后移,n-1次遍历结束后,序列有序。
    例如,对序列(3,2,1,5)进行排序的过程是:共进行3次遍历,第1次遍历时先比较3和2,交换,继续比较3和1,交换,再比较3和5,不交换,这样第1次遍历结束,最大值5在最后的位置,得到序列(2,1,3,5)。第2次遍历时先比较2和1,交换,继续比较2和3,不交换,第2次遍历结束时次大值3在倒数第2的位置,得到序列(1,2,3,5),第3次遍历时,先比较1和2,不交换,得到最终有序序列(1,2,3,5)。
    需要注意的是,如果在某次遍历中没有发生交换,那么就不必进行下次遍历,因为序列已经有序。可以通过排序时添加flag来实现。

    • 实现
    // 冒泡排序 注意 flag 的作用
    static void funBubbleSort(int[] array) {
    
        boolean flag = true;
    
        for (int i = 0; i < array.length - 1 && flag; i++) {
    
            flag = false;
    
            for (int j = 0; j < array.length - 1 - i; j++) {
    
                if (array[j] > array[j + 1]) {
    
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
    
                    flag = true;
                }
            }
        }
    
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }

    最佳情况下冒泡排序只需一次遍历就能确定数组已经排好序,不需要进行下一次遍历,所以最佳情况下,时间复杂度为O(n)

    最坏情况下冒泡排序需要n-1次遍历,第一次遍历需要比较n-1次,第二次遍历需要n-2次,…,最后一次需要比较1次,最差情况下时间复杂度为 O(n^2)

    简单选择排序

    • 简介

    简单选择排序的思想是:设排序序列的记录个数为n,进行n-1次选择,每次在n-i+1(i = 1,2,…,n-1)个记录中选择关键字最小的记录作为有效序列中的第i个记录。

    例如,排序序列(3,2,1,5)的过程是,进行3次选择,第1次选择在4个记录中选择最小的值为1,放在第1个位置,得到序列(1,3,2,5),第2次选择从位置1开始的3个元素中选择最小的值2放在第2个位置,得到有序序列(1,2,3,5),第3次选择因为最小的值3已经在第3个位置不需要操作,最后得到有序序列(1,2,3,5)。

    • 实现
    // 选择排序(非优化版)
    // 把0索引的元素,和索引1以后的元素都进行比较,第一次完毕,最小值出现在了0索引。同理,其他的元素就可以排好。
    static void funSelectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[i]) {
                    int temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                }
            }
        }
    }
    
    // 选择排序(优化版)
        static void funSelectSort2(int[] arr) {
            // 做第i趟排序
            for (int i = 0; i < arr.length - 1; i++) {
                int k = i;
                // 选最小的记录
                for (int j = i + 1; j < arr.length; j++) {
                    if (arr[j] < arr[k]) {
                        // 记下目前找到的最小值所在的位置
                        k = j;
                    }
                }
            // 在内层循环结束,也就找到本轮循环的最小的数之后,再进行交换
            if (k != i) {
                int temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }
        }
    }
    • 分析

    简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时,需进行n-1次比较;当i=2时,需进行n-2次比较;依次类推,共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2,即进行比较操作的时间复杂度为 O(n^2) ,进行移动操作的时间复杂度为 O(n) 。总的时间复杂度为 O(n^2)

    最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录。最坏情况下,即待排序记录初始状态是按第一条记录最大,之后的记录从小到大顺序排列,则需要移动记录的次数最多为3(n-1)。

    简单选择排序是不稳定排序。

    直接插入排序

    • 简介

    直接插入的思想是:是将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增1的有序表。

    例如,排序序列(3,2,1,5)的过程是,初始时有序序列为(3),然后从位置1开始,先访问到2,将2插入到3前面,得到有序序列(2,3),之后访问1,找到合适的插入位置后得到有序序列(1,2,3),最后访问5,得到最终有序序列(1,2,3,5).

    • 实现
    static void funDInsertSort(int[] array) {
    
        int j;
    
        for (int i = 1; i < array.length; i++) {
    
            int temp = array[i];
    
            j = i - 1;
    
            while (j > -1 && temp < array[j]) {
    
                array[j + 1] = array[j];
    
                j--;
            }
    
            array[j + 1] = temp;
    
        }
    
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }
    • 分析

    最好情况下,当待排序序列中记录已经有序时,则需要n-1次比较,不需要移动,时间复杂度为 O(n) 。最差情况下,当待排序序列中所有记录正好逆序时,则比较次数和移动次数都达到最大值,时间复杂度为 O(n^2) 。平均情况下,时间复杂度为 O(n^2) 。

    • 希尔排序

    希尔排序又称“缩小增量排序”,它是基于直接插入排序的以下两点性质而提出的一种改进:(1) 直接插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。(2) 直接插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。更多关于希尔排序的内容请百度

    • 归并排序

    归并排序是分治法的一个典型应用,它的主要思想是:将待排序序列分为两部分,对每部分递归地应用归并排序,在两部分都排好序后进行合并。

    例如,排序序列(3,2,8,6,7,9,1,5)的过程是,先将序列分为两部分,(3,2,8,6)和(7,9,1,5),然后对两部分分别应用归并排序,第1部分(3,2,8,6),第2部分(7,9,1,5),对两个部分分别进行归并排序,第1部分继续分为(3,2)和(8,6),(3,2)继续分为(3)和(2),(8,6)继续分为(8)和(6),之后进行合并得到(2,3),(6,8),再合并得到(2,3,6,8),第2部分进行归并排序得到(1,5,7,9),最后合并两部分得到(1,2,3,5,6,7,8,9)。

    //归并排序
        static void funMergeSort(int[] array) {
    
            if (array.length > 1) {
    
                int length1 = array.length / 2;
                int[] array1 = new int[length1];
                System.arraycopy(array, 0, array1, 0, length1);
                funMergeSort(array1);
    
                int length2 = array.length - length1;
                int[] array2 = new int[length2];
                System.arraycopy(array, length1, array2, 0, length2);
                funMergeSort(array2);
    
                int[] datas = merge(array1, array2);
                System.arraycopy(datas, 0, array, 0, array.length);
            }
    
        }
    
        //合并两个数组
        static int[] merge(int[] list1, int[] list2) {
    
            int[] list3 = new int[list1.length + list2.length];
    
            int count1 = 0;
            int count2 = 0;
            int count3 = 0;
    
            while (count1 < list1.length && count2 < list2.length) {
    
                if (list1[count1] < list2[count2]) {
                    list3[count3++] = list1[count1++];
                } else {
                    list3[count3++] = list2[count2++];
                }
            }
    
            while (count1 < list1.length) {
                list3[count3++] = list1[count1++];
            }
    
            while (count2 < list2.length) {
                list3[count3++] = list2[count2++];
            }
    
            return list3;
        }
    • 分析

    归并排序的时间复杂度为O(nlogn),它是一种稳定的排序,java.util.Arrays类中的sort方法就是使用归并排序的变体来实现的。

    快速排序

    快速排序的主要思想是:在待排序的序列中选择一个称为主元的元素,将数组分为两部分,使得第一部分中的所有元素都小于或等于主元,而第二部分中的所有元素都大于主元,然后对两部分递归地应用快速排序算法。

    快排原理:

    在要排的数(比如数组A)中选择一个中心值key(比如A[0]),通过一趟排序将数组A分成两部分,其中以key为中心,key右边都比key大,key左边的都key小,然后对这两部分分别重复这个过程,直到整个有序。

    整个快排的过程就简化为了一趟排序的过程,然后递归调用就行了。

    一趟排序的方法:
    1,定义i=0,j=A.lenght-1,i为第一个数的下标,j为最后一个数下标
    2,从数组的最后一个数Aj从右往左找,找到第一小于key的数,记为Aj;
    3,从数组的第一个数Ai 从左往右找,找到第一个大于key的数,记为Ai;
    4,交换Ai 和Aj
    5,重复这个过程,直到 i=j
    6,调整key的位置,把A[i] 和key交换
    假设要排的数组为:A[8] ={ 5 2 8 9 2 3 4 9 }
    选择 key = 5, 开始时 i=0,j=7
    index 0 1 2 3 4 5 6 7


    快速排序第一趟

    // 快速排序
    static void funQuickSort(int[] mdata, int start, int end) {
        if (end > start) {
            int pivotIndex = quickSortPartition(mdata, start, end);
            funQuickSort(mdata, start, pivotIndex - 1);
            funQuickSort(mdata, pivotIndex + 1, end);
        }
    }
    // 快速排序前的划分
    static int quickSortPartition(int[] list, int first, int last) {
    
        int pivot = list[first];
        int low = first + 1;
        int high = last;
    
        while (high > low) {
    
            while (low <= high && list[low] <= pivot) {
                low++;
            }
    
            while (low <= high && list[high] > pivot) {
                high--;
            }
    
            if (high > low) {
                int temp = list[high];
                list[high] = list[low];
                list[low] = temp;
            }
        }
    
        while (high > first && list[high] >= pivot) {
            high--;
        }
    
        if (pivot > list[high]) {
            list[first] = list[high];
            list[high] = pivot;
            return high;
        } else {
            return first;
        }
    }
    • 分析

    在快速排序算法中,比较关键的一个部分是主元的选择。在最差情况下,划分由n个元素构成的数组需要进行n次比较和n次移动,因此划分需要的时间是O(n)。在最差情况下,每次主元会将数组划分为一个大的子数组和一个空数组,这个大的子数组的规模是在上次划分的子数组的规模上减1,这样在最差情况下算法需要(n-1)+(n-2)+…+1= * O(n^2) * 时间。

    最佳情况下,每次主元将数组划分为规模大致相等的两部分,时间复杂度为O(nlogn)

    堆排序

    在介绍堆排序之前首先需要了解堆的定义,n个关键字序列K1,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):(1) ki <= k(2i)且 ki <= k(2i+1) (1 ≤ i≤ n/2),当然,这是小根堆,大根堆则换成>=号。

    如果将上面满足堆性质的序列看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有的非终端节点的值均不大于(或不小于)其左右孩子节点的值。

    堆排序的主要思想是:给定一个待排序序列,首先经过一次调整,将序列构建成一个大顶堆,此时第一个元素是最大的元素,将其和序列的最后一个元素交换,然后对前n-1个元素调整为大顶堆,再将其第一个元素和末尾元素交换,这样最后即可得到有序序列。

    • 实现
    //堆排序
    public class TestHeapSort {
    
        public static void main(String[] args) {
            int arr[] = { 5, 6, 1, 0, 2, 9 };
            heapsort(arr, 6);
            System.out.println(Arrays.toString(arr));
        }
    
        static void heapsort(int arr[], int n) {
    
            // 先建大顶堆
            for (int i = n / 2 - 1; i >= 0; i--) {
                heapAdjust(arr, i, n);
            }
    
            for (int i = 0; i < n - 1; i++) {
                swap(arr, 0, n - i - 1);
                heapAdjust(arr, 0, n - i - 1);
            }
        }
    
        // 交换两个数
        static void swap(int arr[], int low, int high) {
            int temp = arr[low];
            arr[low] = arr[high];
            arr[high] = temp;
        }
    
        // 调整堆
        static void heapAdjust(int arr[], int index, int n) {
    
            int temp = arr[index];
    
            int child = 0;
    
            while (index * 2 + 1 < n) {
    
                child = index * 2 + 1;
    
                // child为左右孩子中较大的那个
                if (child != n - 1 && arr[child] < arr[child + 1]) {
                    child++;
                }
                // 如果指定节点大于较大的孩子 不需要调整
                if (temp > arr[child]) {
                    break;
                } else {
                    // 否则继续往下判断孩子的孩子 直到找到合适的位置
                    arr[index] = arr[child];
                    index = child;
                }
            }
    
            arr[index] = temp;
        }
    }
    • 分析

    由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。堆排序时间复杂度也为O(nlogn),空间复杂度为O(1)。它是不稳定的排序方法。与快排和归并排序相比,堆排序在最差情况下的时间复杂度优于快排,空间效率高于归并排序。

    四、其他算法

    在上面的篇幅中,主要是对查找和常见的几种排序算法作了介绍,这些内容都是基础的但是必须掌握的内容,尤其是二分查找、快排、堆排、归并排序这几个更是面试高频考察点。(这里不禁想起百度一面的时候让我写二分查找和堆排序,二分查找还行,然而堆排序当时一脸懵逼…)下面主要是介绍一些常见的其它算法。

    递归

    • 简介

    在平常解决一些编程或者做一些算法题的时候,经常会用到递归。程序调用自身的编程技巧称为递归。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。上面介绍的快速排序和归并排序都用到了递归的思想。

    • 经典例子

    斐波那契数列,又称黄金分割数列、因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)。

    //斐波那契数列 递归实现
    static long funFib(long index) {
    
        if (index == 0) {
            return 0;
        } else if (index == 1) {
            return 1;
        } else {
            return funFib(index - 1) + funFib(index - 2);
        }
    }

    上面代码是斐波那契数列的递归实现,然而我们不难得到它的时间复杂度是O(2^n),递归有时候可以很方便地解决一些问题,但是它也会带来一些效率上的问题。下面的代码是求斐波那契数列的另一种方式,效率比递归方法的效率高。

    分治算法

    分治算法的思想是将待解决的问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后合并这些子问题的解来建立最终的解。分治算法中关键地一步其实就是递归地求解子问题。关于分治算法的一个典型例子就是上面介绍的归并排序。

    动态规划

    动态规划与分治方法相似,都是通过组合子问题的解来求解待解决的问题。但是,分治算法将问题划分为互不相交的子问题,递归地求解子问题,再将它们的解组合起来,而动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子子问题。动态规划方法通常用来求解最优化问题。

    动态规划典型的一个例子是最长公共子序列问题。

    常见的算法还有很多,比如贪心算法,回溯算法等等,这里都不再详细介绍,想要熟练掌握,还是要靠刷题,刷题,刷题,然后总结。

    五、常见算法题

    下面是一些常见的算法题汇总。

    不使用临时变量交换两个数

    static void funSwapTwo(int a, int b) {
    
        a = a ^ b;
        b = b ^ a;
        a = a ^ b;
    
        System.out.println(a + " " + b);
    }

    判断一个数是否为素数

    static boolean funIsPrime(int m) {
    
        boolean flag = true;
    
        if (m == 1) {
            flag = false;
        } else {
    
            for (int i = 2; i <= Math.sqrt(m); i++) {
                if (m % i == 0) {
                    flag = false;
                    break;
                }
            }
        }
    
        return flag;
    }

    其它算法题

    1、15道使用频率极高的基础算法题
    2、二叉树相关算法题
    3、链表相关算法题
    4、字符串相关算法问题

    六、总结

    以上就是自己对常见的算法相关内容的总结,算法虐我千百遍,我待算法如初恋,革命尚未成功,同志仍需刷题,加油,
    希望能打开Offer之路。

    展开全文
  • 常用数据结构与常用算法

    万次阅读 2018-08-08 20:32:54
    1. 常见数据结构 人们进行程序设计时通常关注两个重要问题,一是如何将待处理的数据存储到计算机内存中,即数据表示;二是设计算法操作这些数据,即数据处理。数据表示的本质是数据结构设计,数据处理的本质是算法...
  • 【数据结构与算法常见数据结构及基本操作

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

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

    万次阅读 多人点赞 2019-03-16 18:49:31
    学习数据结构与算法,还是很有必要看几本相关的书籍,但根据不同基础的人,合适看的书也不一样,因此,针对不同层次、不同语言的人,推荐几本市面上口碑不错的书。 1. 入门级 针对刚入门的同学,建议不要急着去看...
  • 目录 基础 c/c++ 代码优化及常见错误 ...除树和图外的数据结构可以使用STL: C++ STL的使用 数据结构 线性表 顺序表 循环左移(2010联考真题) 单链表 单链表相邻结点逆置(2019北邮考研真...
  • 人工智能之机器学习常见算法

    万次阅读 多人点赞 2019-04-11 11:18:17
    摘要之前一直对机器学习很感兴趣,一直没时间去研究,今天刚好是...这里IT经理网为您总结一下常见的机器学习算法,以供您在工作和学习中参考。 机器学习的算法很多。很多时候困惑人们都是,很多算法是一类算法,而有
  • 数据结构与算法目录

    万次阅读 多人点赞 2015-06-23 16:19:19
    数据结构与算法系列先...我们所学的数据结构这门课程就是研究这些内容的,只有弄清楚了这些,我们才可以用高效的算法与之结合,产生高效率的程序。掌握好数据结构的内容也是一个程序员的基本功,特别对于c/c++程序员。
  • 看了这么久小吴的文章,不知道你们有没有发现,目前文章中涉及到的编程代码有 Java、C++、Python、JavaScript 这么多种,但就算法而言,实际上这些算法的写法都大同小异,甚至有些地方都一模一样。 所以小伙伴们不...
  • 数据结构基础系列(9):排序

    万人学习 2018-10-22 21:38:03
    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第9部分排序,...
  • 机器学习常用算法总结

    万次阅读 2016-08-21 23:26:48
    本文总结一下常见的机器学习算法,以供参考。机器学习的算法很多,很多算法是一类算法,而有些算法又是从其他算法中延伸出来的。这里从两个方面进行总结,第一个方面是学习的方式,第二个方面是算法的类似性。 一、...
  • 一张图理解数据结构与算法的关系

    千次阅读 2019-04-23 11:15:00
    一句话:相互之间存在关系的数据元素的集合就是数据结构算法是解决特定问题的有限求解步骤。 一张图: 学习数据结构与算法有什么用呢?拿一个厨师的厨艺来比较的话,真正的大厨一般不是那种能做各种花样的...
  • 数据结构与算法学习心得

    万次阅读 2012-11-21 10:18:32
    数据结构与算法的内容还有很多。但是由于时间的关系,我并没有深入下去,尤其是查找时用到的平衡二叉树、B_和B+树,还有红黑树等等。希望以后有时间可以继续看。 首先,简要回顾一下学习的内容。简单的说,是“3+2...
  • 机器学习的13种算法和4种学习方法,推荐给大家

    万次阅读 多人点赞 2018-09-18 21:08:45
    很多时候困惑人们都是,很多算法是一类算法,而有些算法又是从其他算法中延伸出来的。这里,我们从两个方面来给大家介绍,第一个方面是学习的方式,第二个方面是算法的分类。 一、4大主要学习方式 1.监督式学习 ...
  • 数据结构与算法(一)概念梳理篇

    千次阅读 2016-04-22 21:38:59
    程序 = 数据结构 + 算法,至于我们平时用的语言,无论是C、C++、JAVA、Python、Golang等等,都肯定会用到各式各样的算法数据结构,数组,链表,排序,搜索等等,可以说数据结构算法就是程序的灵魂,同样的,也是...
  • 数据结构与算法-开篇

    千次阅读 2018-07-30 18:02:21
    数据结构与算法-开篇 先说一下数据结构,对于老司机来说就是数据的使用方法,如果非给个概念的话个人觉得数据之间相互存在的一种或多种特定的关系的元素的集合 逻辑结构 常见的数据对象中数据元素之间的相互...
  • 数据结构:是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、(存储)物理结构和数据的运算三个部分。 为什么要学数据结构? 首先,因为数据结构作为...
1 2 3 4 5 ... 20
收藏数 265,081
精华内容 106,032
关键字:

常见数据结构与算法