精华内容
下载资源
问答
  • 数据结构一 (简介)

    千次阅读 多人点赞 2018-07-12 17:09:00
    转载请标明出处: ...本文出自:【openXu的博客】...随着计算机应用领域的不断扩大,无论设计系统软件还是应用软件都会用到各种复杂数据结构。   一个好的程序无非是选择一个合理的数据结构和好的算法,而好的算法...

    版权声明:本文为openXu原创文章【openXu的博客】,未经博主允许不得以任何形式转载

    1、什么是数据结构

      数据结构主要学习用计算机实现数据组织和数据处理的方法;随着计算机应用领域的不断扩大,无论设计系统软件还是应用软件都会用到各种复杂的数据结构。

      一个好的程序无非是选择一个合理的数据结构和好的算法,而好的算法的选择很大程度上取决于描述实际问题所采用的数据结构,所以想编写出好的程序必须扎实的掌握数据结构

    1.1 数据结构的定义

    **数据:**人们利用文字符号、数据符号以及其他规定的符号对现实世界的事物及活动所做的抽象描述。从计算机的角度看,数据是所有能被输入到计算机中,并能被计算机处理的符号的集合。

    数据元素: 数据集合中的一个“个体”,是数据的基本单位

    数据结构: 是指数据以及相互之间的联系,可以看做是相互之间存在某种特定关系的数据元素的集合,因此可以把数据结构看成是带结构的数据元素的集合。

    数据结构包括以下几个方面:

    • 数据的逻辑结构

    是指数据元素之间的逻辑关系。比如一个表中的记录顺序反映了数据元素之间的逻辑关系,一个数组中元素的排列顺序也是数据元素之间的逻辑关系。

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

    数据元素及其逻辑关系在计算机存储器中的存储方式,一般只在高级语言的层次上来讨论存储结构。不同的逻辑结构有不同的存储结构

    • 数据的运算

    施加在该数据上的操作,是定义在数据的逻辑结构之上的,每种逻辑结构都有一组相应的运算。例如最常用的增删改查、更新、排序等。数据的运算最终需在对应的存储结构中用算法实现。

      一组数据,数据元素及其录顺序是一定的,但是可以用不同的逻辑结构表示,这样就有着不同的存储结构,对应着不同的运算算法。以上都属于数据结构的范畴

    为了更确切的描述一种数据结构,通常采用二元组表示:
        B = (D, R)
    其中,B是一种数据结构,它由数据元素的集合D,和D上二元关系的集合R所组成:

    D = {di|1≤i≤n,n≥0} n为D中结点个数
    R = {rj|1≤j≤m,m≥0} m为R中关系的个数

    示例:一个城市表,给出其逻辑结构的二元组表示

    城市区号说明
    Beijing010首都
    Shanghai021直辖市
    Changsha0731湖南省会
    Wuhan027湖北省会
    City = (D, R)
    D={Beijing, Shanghai, Changesha, Wuhan}
    R={r}
    r={<Beijign,Shanghai>, <Shanghai,Changsha>,<Changsha,Wuhan>}
    

    1.2 逻辑结构类型

      在不会产生混淆的前提下,常常将数据的逻辑结构简称为数据结构。数据的逻辑结构主要有一下几类:

    ①. 集合

    指数据元素之间除了“同属于一个集合”的关系外,别无其他关系
        这里写图片描述

    ②. 线性结构

    指该结构中的节点之间存在一对一的关系。特点是除了开始结点和终端结点,其余结点都有且仅有一个直接前驱,有且仅有一个直接后继。典型的例子就是“顺序表”
        这里写图片描述

    ③. 树形结构

    指该结构中的结点之间存在一对多的关系,其特点是每个结点最多只有一个直接前驱,但可以有多个直接后继,可以有多个终端结点。典型的树形结构**“二叉树”**
        这里写图片描述

    ④. 图形结构

    该结构中的结点之间存在多对多的关系。特点是每个结点的直接前驱和直接后继的个数都可以是任意的。因此,可能没有开始节点和终端结点,也可能有多个开始节点和终端结点。
        这里写图片描述

      树形结构和图形结构统称为非线性结构,该结构中的结点之间存在一对多或者多对多的关系

    示例:

    有一种数据结构B=(D, R),其中:
    D = {48,25,64,57,82,36,75}
    R = {r1 , r2}
    r1 = {<25,36>,<36,48>,<48,57>,<57,64>,<64,75>,<75,82>}
    r2 = {<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<82,75>}
    请画出其逻辑结构表示。

    解:对应图形如下,它是一种图形结构,其中r1(红线)为线性结构,r2(黑线)为树形结构
        这里写图片描述

    1.3 存储结构类型

    ①. 顺序存储结构

      把逻辑上相邻的结点存储在物理位置上相邻的存储单元里,结点之间的逻辑关系由存储单元的邻接关系体现。
      优点:节省存储空间(只存储结点的数据,结点之间逻辑关系没有占用存储空间)
      缺点:不便于修改,对结点的插入、删除运算时,可能要移动一系列的结点
        这里写图片描述

    ②. 链式存储结构

      该结构不要求逻辑上相邻的结点在物理位置上也相邻,结点间的逻辑关系由附加的指针字段表示。
      优点:便于修改,在进行插入、删除运算时,只需要修改相应结点的指针域,不需要移动结点
       缺点:与顺序存储方法相比存储空间的利用率较低(存储结点的逻辑关系需要占用空间)
        这里写图片描述

    ③. 索引存储结构

      在存储结点信息的同事还建立附加的索引表,索引表中的索引项一般形式为(唯一标识,地址),地址为指向结点的指针。这样大大提高数据查找的速度。
       优点:可以对结点随机访问。在插入、删除时只需要操作索引表中对应结点的存储地址,不必移动结点表中的结点数据,仍保持较高的数据修改运算效率。
      缺点:增加了索引表,降低了存储空间的利用率
        这里写图片描述

    ④. 哈希(散列)存储结构

      根据结点的关键字通过哈希函数直接计算出一个值,并将这个值作为该节点的存储地址。
      优点:查找速度快(可直接计算出要查询结点的地址)
      缺点:只存储结点的数据,不存储结点之间的逻辑关系。一般只合适要求对数据能快速查找和插入的场合

      这四种基本的存储方法即可单独使用,也可组合使用,同一种逻辑结构采用不同的存储方法可以得到不同的储存结构。应考虑运算方便及算法的时空要求 决定采用何种存储结构

    1.4 数据结构和数据类型

    数据类型:

      某种程序设计语言中已实现的数据结构。高级程序语言对程序中出现的变量、常量或表达式明确的说明他们所属的数据类型,不同数据类型取值范围不同,能进行的操作也不同。数据类型是一个值得集合和定义在此集合上的一组操作的总称。

      数据类型可分为简单类型(无法分割:整数、实数、字符、指针、枚举等)和结构类型(可分割:数组、字符串、自定义类型等)

    数据结构:

      是指计算机处理的数据元素的组织形式和相互关系,可以理解为是一个“抽象的”概念性的东西,而数据类型是对数据结构的实现。

    2、算法及其描述

    ###2.1 什么是算法

      数据元素之间的关系有逻辑关系和物理关系,对应的运算有逻辑结构上的运算功能和具体存储结构上的运算实现。把具体存储结构上的运算实现过程称为算法。

      算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示计算机的一个或多个操作。

    算法的五个重要特性:

    • 有穷性(能结束)
    • 确定性(只有一条执行路径)
    • 可行性(执行有限次能实现)
    • 有输入
    • 有输出

    ###2.2 算法描述

      算法可有多种描述方式,比如文字方式、语言方式、图形方式、表格方式等。

    3、算法分析

      在一个算法设计好后,还需要对其进行分析,确定一个算法的优劣。

    3.1 算法设计的目标

      算法设计应满足一下几条目标:正确性、可使用性(用户友好性)、可读性、健壮性(容错性)、高效率与低存储量需求

    ###3.2 算法效率分析

      通常有两种衡量算法效率的方法:事后统计法、事前分析估算法

    • 事后统计法

      缺点是必须执行程序,而且存在其他因素掩盖算法本质

    • 事前分析估算法:

      通常采用这种方法。撇开与计算机硬件、软件相关因素(计算机运行速度、编程语言、编译后机器语言代码质量),仅考虑算法本身的效率高低,可以认为一个特定的算法的运行工作量只依赖于问题的规模(用整数量n表示)。
      一个算法由控制语句(顺序、分支、循环)和原操作(固有数据类型的操作)构成,算法运行时间取决于两者的综合效果。算法执行时间大致为基本运算所需的时间和其运算次数的乘积。显然,一个算法执行基本运算的次数越少,其运行时间也就相对越少,所以算法的执行时间可以看成是其中基本运算执行的次数(T(n)),T(n)是问题规模n的某个函数f(n)。

    **示例:**求两个n阶方阵相加C=A+B的算法如下,分析其时间复杂度:

    void matrixAdd(int A[][], int B[][], int C[][]){
    	int n = A.length;    //语句①  执行1次
    	int i, j;
    	for(i = 0; i< n; i++) //语句②   执行n+1
    	for(j = 0; j< n; j++) //语句③   执行n(n+1)次
    		C[i][j] = A[i][j] + B[i][j]; //语句④  执行n²次
    }
    

    解:该算法包含四个可执行语句,语句①就是基本运算,语句②和语句③是循环语句,其控制变量要从0增加到n,当i=n才会终止,所以它们的频度都为n+1,但它们的循环体只执行n次,因此该算法所有语句频度之和为:
      T(n)=f(n)=1+ n+1+n(n+1)+n²=2n²+2n+2
      由于算法长度不一定,有的算法非常长,如果还按照这种方式计算就非常麻烦了。另一种方式是只分析影响算法执行时间的最主要部分即可,而不是每一步都详细的分析。

      这时候引入一个记号O(读大O,Order简写,指数量级),T(n)=O(f(n))表示算法时间复杂度取决于f(n)函数中最高阶,忽略其他低阶项和常系数,这样既可以简化T(n)的计算,又能客观的反应出当n很大时算法的时间性能,注意是n很大时,这样计算时间复杂度才有意义。所以上面示例中的答案就直接简化为T(n)=O(n²)。算法的时间复杂度使用大O(数量级)表示后,只需要分析影响算法执行时间的主要部分即可,不必对每一步都进行详细的分析。上面的示例中只需要分析两重循环最深层的语句④的频度即可:T(n)=n²=O(n²)。以后总是采用这种方式分析算法的时间复杂度。

    不同数量级对应的值存在的关系如下:

    O(1) 常数阶 < O(log2n)对数阶< O(n) 一重循环线性阶 < O(nlog2n) <O(n²)平方阶<O(n³)立方阶<O(2n)指数阶<O(n!)无穷

    3.3 算法存储空间分析

      一个算法的存储量包括输入数据所占空间、程序本身所占空间和辅助变量所占空间。在对算法进行存储空间分析时,只考虑辅助变量所占空间,所以空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度,一般也作为问题规模n的函数,以数量级形式给出,记做:
        S(n) = O(g(n))

    **示例:**有如下算法,调用语句为fun(a, n, 0),求其空间复杂度:

    void fun(int a[], int n, int k){
    	int i; //辅助变量
    	if(k==n-1){
    	    for(i=0;i<n;i++)
    	        System.out.println(a[i]);
    	}else{
    	    for(i=k;i<n;i++)
    	        a[i]=a[i]+i*i;
    	    fun(a,n,k+1); //递归调用
    	}
    }
    

    解:设fun(a,n, k)的临时空间大小为S(k),其中定义了一个辅助变量i,并有:
    这里写图片描述
    S(0) = 1+S(1)=1+1+S(2) =...=1+1+...+1+S(n-1) =1+1+...+1 (n个1)=O(n)
    所以调用fun(a,n,0)的空间复杂度为O(n)

    4、数据结构+算法=程序

      计算机软件最终成果都是以程序的形式表现的,数据结构和算法分析的目的是设计好的程序。程序设计的本质是对要处理问题选择好的数据结构,同时再次结构上施加一种好的算法。

    ①. 数据结构与算法

      选择数据结构时也要考虑其对算法的影响,数据结构对算法的影响主要有两方面:

      数据结构的存储能力:存储能力与所使用的空间大小成正比,体现了时间与空间的矛盾

      定义在数据结构上的运算:数据结构上定义了基本运算,有了好的运算,算法设计也就比较容易

    ②. 选择时的考虑

    • 数据结构要适应问题的状态描述
    • 数据结构应与所选择的算法相适应
    • 数据结构的选择同时要兼顾程序设计的方便
    • 灵活应用已有知识
    展开全文
  • 学习数据数据结构的意义

    千次阅读 2018-12-31 14:09:05
    什么是数据结构,为什么要学习数据结构数据结构是否是一门纯数学课程?它在专业课程体系中起什么样的作用?我们要怎么才能学好数据结构?… 相信同学们在刚开始《数据结构》这门课的学习时,心里有着类似前面几个...

    来源:我是码农,转载请保留出处和链接!

    本文链接:http://www.54manong.com/?id=18

    什么是数据结构,为什么要学习数据结构?数据结构是否是一门纯数学课程?它在专业课程体系中起什么样的作用?我们要怎么才能学好数据结构?… 相信同学们在刚开始《数据结构》这门课的学习时,心里有着类似前面几个问题的这样那样的疑问。希望下面的内容能帮助大家消除疑惑,下定决心坚持学好这门课:

    1 学习数据数据结构的意义

    数据结构是计算机科学与技术专业、计算机信息管理与应用专业,电子商务等专业的基础课,是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此,要想更好地运用计算机来解决实际问题,仅掌握几种计算机程序设计语言是难以应付当前众多复杂的课题。要想有效地使用计算机、充分发挥计算机的性能,还必须学习和掌握好数据结构的有关知识。打好“数据结构”这门课程的扎实基础,对于学习计算机专业的其他课程,如操作系统、数据库管理系统、软件工程、编译原理、人工智能、图视学等都是十分有益的。

    2 为什么要学习数据结构

    在计算机发展的初期,人们使用计算机的目的主要是处理数值计算问题。当我们使用计算机来解决一个具体问题时,一般需要经过下列几个步骤:首先要从该具体问题抽象出一个适当的数学模型,然后设计或选择一个解此数学模型的算法,最后编出程序进行调试、测试,直至得到最终的解答。例如,求解梁架结构中应力的数学模型的线性方程组,可以使用迭代算法来求解。

    由于当时所涉及的运算对象是简单的整型、实型或布尔类型数据,所以程序设计者的主要精力是集中于程序设计的技巧上,而无须重视数据结构。随着计算机应用领域的扩大和软、硬件的发展,非数值计算问题越来越显得重要。据统计,当今处理非数值计算性问题占用了85%以上的机器时间。这类问题涉及到的数据结构更为复杂,数据元素之间的相互关系一般无法用数学方程式加以描述。因此,解决这类问题的关键不再是数学分析和计算方法,而是要设计出合适的数据结构,才能有效地解决问题。下面所列举的就是属于这一类的具体问题。

    例1:图书馆信息检索系统。当我们根据书名查找某本书有关情况的时候;或者根据作者或某个出版社查找有关书籍的时候,或根据书刊号查找作者和出版社等有关情况的时候,只要我们建立了相关的数据结构,按照某种算法编写了相关程序,就可以实现计算机自动检索。由此,可以在图书馆信息检索系统中建立一张按书刊号顺序排列的图书信息表和分别按作者、书名、出版社顺序排列的索引表,如图1.1所示。由这四张表构成的文件便是图书信息检索的数学模型,计算机的主要操作便是按照某个特定要求(如给定书名)对图书馆藏书信息文件进行查询。

    诸如此类的还有学生信息查询系统、商场商品管理系统、仓库物资管理系统等。在这类文档管理的数学模型中,计算机处理的对象之间通常存在着的是一种简单的线性关系,这类数学模型可称为线性的数据结构。

    image.png

    例2:八皇后问题。在八皇后问题中,处理过程不是根据某种确定的计算法则,而是利用试探和回溯的探索技术求解。为了求得合理布局,在计算机中要存储布局的当前状态。从最初的布局状态开始,一步步地进行试探,每试探一步形成一个新的状态,整个试探过程形成了一棵隐含的状态树。如图1.2所示(为了描述方便,将八皇后问题简化为四皇后问题)。回溯法求解过程实质上就是一个遍历状态树的过程。在这个问题中所出现的树也是一种数据结构,它可以应用在许多非数值计算的问题中。

    image.png

    例3:教学计划编排问题。一个教学计划包含许多课程,在教学计划包含的许多课程之间,有些必须按规定的先后次序进行,有些则没有次序要求。即有些课程之间有先修和后续的关系,有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称作图的数据结构来表示,如图1.3所示。有向图中的每个顶点表示一门课程,如果从顶点vi到vj之间存在有向边<vi,vj>,则表示课程i必须先于课程j进行。由以上三个例子可见,描述这类非数值计算问题的数学模型不再是数学方程,而是诸如线性表、树、图之类的数据结构。因此,可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。

    学习数据结构的目的是为了了解计算机处理对象的特性,将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。与此同时,通过算法训练来提高学生的思维能力,通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高。

    3数据结构课程的内容

    数据结构与数学、计算机硬件和软件有十分密切的关系,它是介于数学、计算机硬件和计算机软件之间的一门计算机专业的核心课程,是高级程序设计语言、操作系统、编译原理、数据库、人工智能、图视学等课程的基础。同时,数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。

    数据结构课程重在讨论软件开发过程中的方案设计阶段、同时设计编码和分析阶段的若干基本问题。此外,为了构造出好的数据结构及其实现,还需考虑数据结构及其实现的评价与选择。因此,数据结构的内容包括三个层次的五个“要素”,如图1.3所示。

    image.png

    数据结构的核心技术是分解与抽象。通过分解可以划分出数据的三个层次;再通过抽象,舍弃数据元素的具体内容,就得到逻辑结构。类似地,通过分解将处理要求划分成各种功能,再通过抽象舍弃实现细节,就得到运算的定义。上述两个方面的结合使我们将问题变换为数据结构。这是一个从具体(即具体问题)到抽象(即数据结构)的过程。然后,通过增加对实现细节的考虑进一步得到存储结构和实现运算,从而完成设计任务。这是一个从抽象(即数据结构)到具体(即具体实现)的过程。熟练地掌握这两个过程是数据结构课程在专业技能培养方面的基本目标。

    结束语:数据结构作为一门独立的课程在国外是从1968年才开始的,但在此之前其有关内容已散见于编译原理及操作系统之中。20世纪60年代中期,美国的一些大学开始设立有关课程,但当时的课程名称并不叫数据结构。1968年美国唐.欧.克努特教授开创了数据结构的最初体系,他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。从20世纪60年代末到70年代初,出现了大型程序,软件也相对独立,结构程序设计成为程序设计方法学的主要内容,人们越来越重视数据结构。从70年代中期到80年代,各种版本的数据结构著作相继出现。目前,数据结构的发展并未终结,一方面,面向各专门领域中特殊问题的数据结构得到研究和发展,如多维图形数据结构等;另一方面,从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势,越来越被人们所重视。

    数据结构是计算机科学与技术专业、计算机信息管理与应用专业,电子商务等专业的基础课,是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此,要想更好地运用计算机来解决实际问题,仅掌握几种计算机程序设计语言是难以应付当前众多复杂的课题。要想有效地使用计算机、充分发挥计算机的性能,还必须学习和掌握好数据结构的有关知识。打好“数据结构”这门课程的扎实基础,对于学习计算机专业的其他课程,如操作系统、数据库管理系统、软件工程、编译原理、人工智能、图视学等都是十分有益的。

    在计算机发展的初期,人们使用计算机的目的主要是处理数值计算问题。当我们使用计算机来解决一个具体问题时,一般需要经过下列几个步骤:首先要从该具体问题抽象出一个适当的数学模型,然后设计或选择一个解此数学模型的算法,最后编出程序进行调试、测试,直至得到最终的解答。例如,求解梁架结构中应力的数学模型的线性方程组,可以使用迭代算法来求解。

    由于当时所涉及的运算对象是简单的整型、实型或布尔类型数据,所以程序设计者的主要精力是集中于程序设计的技巧上,而无须重视数据结构。随着计算机应用领域的扩大和软、硬件的发展,非数值计算问题越来越显得重要。据统计,当今处理非数值计算性问题占用了85%以上的机器时间。这类问题涉及到的数据结构更为复杂,数据元素之间的相互关系一般无法用数学方程式加以描述。因此,解决这类问题的关键不再是数学分析和计算方法,而是要设计出合适的数据结构,才能有效地解决问题。下面所列举的就是属于这一类的具体问题。

    例1:图书馆信息检索系统。当我们根据书名查找某本书有关情况的时候;或者根据作者或某个出版社查找有关书籍的时候,或根据书刊号查找作者和出版社等有关情况的时候,只要我们建立了相关的数据结构,按照某种算法编写了相关程序,就可以实现计算机自动检索。由此,可以在图书馆信息检索系统中建立一张按书刊号顺序排列的图书信息表和分别按作者、书名、出版社顺序排列的索引表。由这四张表构成的文件便是图书信息检索的数学模型,计算机的主要操作便是按照某个特定要求(如给定书名)对图书馆藏书信息文件进行查询。

    诸如此类的还有学生信息查询系统、商场商品管理系统、仓库物资管理系统等。在这类文档管理的数学模型中,计算机处理的对象之间通常存在着的是一种简单的线性关系,这类数学模型可称为线性的数据结构。

    例2:八皇后问题。在八皇后问题中,处理过程不是根据某种确定的计算法则,而是利用试探和回溯的探索技术求解。为了求得合理布局,在计算机中要存储布局的当前状态。从最初的布局状态开始,一步步地进行试探,每试探一步形成一个新的状态,整个试探过程形成了一棵隐含的状态树。(为了描述方便,将八皇后问题简化为四皇后问题)。回溯法求解过程实质上就是一个遍历状态树的过程。在这个问题中所出现的树也是一种数据结构,它可以应用在许多非数值计算的问题中。

    例3:教学计划编排问题。一个教学计划包含许多课程,在教学计划包含的许多课程之间,有些必须按规定的先后次序进行,有些则没有次序要求。即有些课程之间有先修和后续的关系,有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称作图的数据结构来表示。有向图中的每个顶点表示一门课程,如果从顶点vi到vj之间存在有向边<vi,vj>,则表示课程i必须先于课程j进行。

    由以上三个例子可见,描述这类非数值计算问题的数学模型不再是数学方程,而是诸如线性表、树、图之类的数据结构。因此,可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。

    学习数据结构的目的是为了了解计算机处理对象的特性,将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。与此同时,通过算法训练来提高学生的思维能力,通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高。

    image.png

    展开全文
  • 图解!24张图彻底弄懂九大常见数据结构

    万次阅读 多人点赞 2020-05-24 22:23:36
    数据结构想必大家都不会陌生,对于一个成熟的程序员而言,熟悉和掌握数据结构和算法也是基本功之一。数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合,特殊的结构在不同的应用场景中往往会带来不...

    ​数据结构想必大家都不会陌生,对于一个成熟的程序员而言,熟悉和掌握数据结构和算法也是基本功之一。数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合,特殊的结构在不同的应用场景中往往会带来不一样的处理效率。

    常用的数据结构可根据数据访问的特点分为线性结构和非线性结构。线性结构包括常见的链表、栈、队列等,非线性结构包括树、图等。数据结构种类繁多,本文将通过图解的方式对常用的数据结构进行理论上的介绍和讲解,以方便大家掌握常用数据结构的基本知识。

    本文提纲:

     1  数组

    数组可以说是最基本最常见的数据结构。数组一般用来存储相同类型的数据,可通过数组名和下标进行数据的访问和更新。数组中元素的存储是按照先后顺序进行的,同时在内存中也是按照这个顺序进行连续存放。数组相邻元素之间的内存地址的间隔一般就是数组数据类型的大小。

     2  链表

    链表相较于数组,除了数据域,还增加了指针域用于构建链式的存储数据。链表中每一个节点都包含此节点的数据和指向下一节点地址的指针。由于是通过指针进行下一个数据元素的查找和访问,使得链表的自由度更高。

    这表现在对节点进行增加和删除时,只需要对上一节点的指针地址进行修改,而无需变动其它的节点。不过事物皆有两极,指针带来高自由度的同时,自然会牺牲数据查找的效率和多余空间的使用。

    一般常见的是有头有尾的单链表,对指针域进行反向链接,还可以形成双向链表或者循环链表。

    链表和数组对比

    链表和数组在实际的使用过程中需要根据自身的优劣势进行选择。链表和数组的异同点也是面试中高频的考察点之一。这里对单链表和数组的区别进行了对比和总结。

     3  跳表

    从上面的对比中可以看出,链表虽然通过增加指针域提升了自由度,但是却导致数据的查询效率恶化。特别是当链表长度很长的时候,对数据的查询还得从头依次查询,这样的效率会更低。跳表的产生就是为了解决链表过长的问题,通过增加链表的多级索引来加快原始链表的查询效率。这样的方式可以让查询的时间复杂度从O(n)提升至O(logn)。

    跳表通过增加的多级索引能够实现高效的动态插入和删除,其效率和红黑树和平衡二叉树不相上下。目前redis和levelDB都有用到跳表。

    从上图可以看出,索引级的指针域除了指向下一个索引位置的指针,还有一个down指针指向低一级的链表位置,这样才能实现跳跃查询的目的。

     

     4  栈

    栈是一种比较简单的数据结构,常用一句话描述其特性,后进先出。栈本身是一个线性表,但是在这个表中只有一个口子允许数据的进出。这种模式可以参考腔肠动物...即进食和排泄都用一个口...

    栈的常用操作包括入栈push和出栈pop,对应于数据的压入和压出。还有访问栈顶数据、判断栈是否为空和判断栈的大小等。由于栈后进先出的特性,常可以作为数据操作的临时容器,对数据的顺序进行调控,与其它数据结构相结合可获得许多灵活的处理。

     

     5  队列

    队列是栈的兄弟结构,与栈的后进先出相对应,队列是一种先进先出的数据结构。顾名思义,队列的数据存储是如同排队一般,先存入的数据先被压出。常与栈一同配合,可发挥最大的实力。

     6  树

    树作为一种树状的数据结构,其数据节点之间的关系也如大树一样,将有限个节点根据不同层次关系进行排列,从而形成数据与数据之间的父子关系。常见的数的表示形式更接近“倒挂的树”,因为它将根朝上,叶朝下。

    树的数据存储在结点中,每个结点有零个或者多个子结点。没有父结点的结点在最顶端,成为根节点;没有非根结点有且只有一个父节点;每个非根节点又可以分为多个不相交的子树。

    这意味着树是具备层次关系的,父子关系清晰,家庭血缘关系明朗;这也是树与图之间最主要的区别。

    别看树好像很高级,其实可看作是链表的高配版。树的实现就是对链表的指针域进行了扩充,增加了多个地址指向子结点。同时将“链表”竖起来,从而凸显了结点之间的层次关系,更便于分析和理解。

    树可以衍生出许多的结构,若将指针域设置为双指针,那么即可形成最常见的二叉树,即每个结点最多有两个子树的树结构。二叉树根据结点的排列和数量还可进一度划分为完全二叉树、满二叉树、平衡二叉树、红黑树等。

    完全二叉树:除了最后一层结点,其它层的结点数都达到了最大值;同时最后一层的结点都是按照从左到右依次排布。

    满二叉树:除了最后一层,其它层的结点都有两个子结点。

    平衡二叉树

    平衡二叉树又被称为AVL树,它是一棵二叉排序树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

    二叉排序树:是一棵空树,或者:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉排序树。

    树的高度:结点层次的最大值

    平衡因子:左子树高度 - 右子树高度

    二叉排序树意味着二叉树中的数据是排好序的,顺序为左结点<根节点<右结点,这表明二叉排序树的中序遍历结果是有序的。(还不懂二叉树四种遍历方式[前序遍历、中序遍历、后序遍历、层序遍历]的同学赶紧补习!)

    平衡二叉树的产生是为了解决二叉排序树在插入时发生线性排列的现象。由于二叉排序树本身为有序,当插入一个有序程度十分高的序列时,生成的二叉排序树会持续在某个方向的字数上插入数据,导致最终的二叉排序树会退化为链表,从而使得二叉树的查询和插入效率恶化。

     

    平衡二叉树的出现能够解决上述问题,但是在构造平衡二叉树时,却需要采用不同的调整方式,使得二叉树在插入数据后保持平衡。主要的四种调整方式有LL(左旋)、RR(右旋)、LR(先左旋再右旋)、RL(先右旋再左旋)。这里先给大家介绍下简单的单旋转操作,左旋和右旋。LR和RL本质上只是LL和RR的组合。

    在插入一个结点后应该沿搜索路径将路径上的结点平衡因子进行修改,当平衡因子大于1时,就需要进行平衡化处理。从发生不平衡的结点起,沿刚才回溯的路径取直接下两层的结点,如果这三个结点在一条直线上,则采用单旋转进行平衡化,如果这三个结点位于一条折线上,则采用双旋转进行平衡化。

    左旋:S为当前需要左旋的结点,E为当前结点的父节点。

    左旋的操作可以用一句话简单表示:将当前结点S的左孩子旋转为当前结点父结点E的右孩子,同时将父结点E旋转为当前结点S的左孩子。可用动画表示:

    右旋:S为当前需要左旋的结点,E为当前结点的父节点。右单旋是左单旋的镜像旋转。

    左旋的操作同样可以用一句话简单表示:将当前结点S的左孩子E的右孩子旋转为当前结点S的左孩子,同时将当前结点S旋转为左孩子E的右孩子。可用动画表示:

    红黑树

    平衡二叉树(AVL)为了追求高度平衡,需要通过平衡处理使得左右子树的高度差必须小于等于1。高度平衡带来的好处是能够提供更高的搜索效率,其最坏的查找时间复杂度都是O(logN)。但是由于需要维持这份高度平衡,所付出的代价就是当对树种结点进行插入和删除时,需要经过多次旋转实现复衡。这导致AVL的插入和删除效率并不高。

    为了解决这样的问题,能不能找一种结构能够兼顾搜索和插入删除的效率呢?这时候红黑树便申请出战了。

    红黑树具有五个特性:

    1. 每个结点要么是红的要么是黑的。

    2. 根结点是黑的。

    3. 每个叶结点(叶结点即指树尾端NIL指针或NULL结点)都是黑的。

    4. 如果一个结点是红的,那么它的两个儿子都是黑的。

    5. 对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

    红黑树通过将结点进行红黑着色,使得原本高度平衡的树结构被稍微打乱,平衡程度降低。红黑树不追求完全平衡,只要求达到部分平衡。这是一种折中的方案,大大提高了结点删除和插入的效率。C++中的STL就常用到红黑树作为底层的数据结构。

    红黑树VS平衡二叉树

    除了上面所提及的树结构,还有许多广泛应用在数据库、磁盘存储等场景下的树结构。比如B树、B+树等。这里就先不介绍了诶,下次在讲述相关存储原理的时候将会着重介绍。(其实是因为懒)

     7  堆

    了解完二叉树,再来理解堆就不是什么难事了。堆通常是一个可以被看做一棵树的数组对象。堆的具体实现一般不通过指针域,而是通过构建一个一维数组与二叉树的父子结点进行对应,因此堆总是一颗完全二叉树。

    对于任意一个父节点的序号n来说(这里n从0算),它的子节点的序号一定是2n+1,2n+2,因此可以直接用数组来表示一个堆。

    不仅如此,堆还有一个性质:堆中某个节点的值总是不大于或不小于其父节点的值。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

    堆常用来实现优先队列,在面试中经常考的问题都是与排序有关,比如堆排序、topK问题等。由于堆的根节点是序列中最大或者最小值,因而可以在建堆以及重建堆的过程中,筛选出数据序列中的极值,从而达到排序或者挑选topK值的目的。

     

     8  散列表

    散列表也叫哈希表,是一种通过键值对直接访问数据的机构。在初中,我们就学过一种能够将一个x值通过一个函数获得对应的一个y值的操作,叫做映射。散列表的实现原理正是映射的原理,通过设定的一个关键字和一个映射函数,就可以直接获得访问数据的地址,实现O(1)的数据访问效率。在映射的过程中,事先设定的函数就是一个映射表,也可以称作散列函数或者哈希函数。

    散列表的实现最关键的就是散列函数的定义和选择。一般常用的有以下几种散列函数:

    直接寻址法:取关键字或关键字的某个线性函数值为散列地址。

    数字分析法:通过对数据的分析,发现数据中冲突较少的部分,并构造散列地址。例如同学们的学号,通常同一届学生的学号,其中前面的部分差别不太大,所以用后面的部分来构造散列地址。

    平方取中:当无法确定关键字里哪几位的分布相对比较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为散列地址。这是因为:计算平方之后的中间几位和关键字中的每一位都相关,所以不同的关键字会以较高的概率产生不同的散列地址。

    取随机数法:使用一个随机函数,取关键字的随机值作为散列地址,这种方式通常用于关键字长度不同的场合。

    除留取余法:取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要,一般取素数或者直接用 n。

    确定好散列函数之后,通过某个key值的确会得到一个唯一的value地址。但是却会出现一些特殊情况。即通过不同的key值可能会访问到同一个地址,这个现象称之为冲突。

    冲突在发生之后,当在对不同的key值进行操作时会使得造成相同地址的数据发生覆盖或者丢失,是非常危险的。所以在设计散列表往往还需要采用冲突解决的办法。

    常用的冲突处理方式有很多,常用的包括以下几种:

    开放地址法(也叫开放寻址法):实际上就是当需要存储值时,对Key哈希之后,发现这个地址已经有值了,这时该怎么办?不能放在这个地址,不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希,比如往后移动一个地址,如果没人占用,就用这个地址。如果超过最大长度,则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。

    再哈希法:在产生冲突之后,使用关键字的其他部分继续计算地址,如果还是有冲突,则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。

    链地址法:链地址法其实就是对Key通过哈希之后落在同一个地址上的值,做一个链表。其实在很多高级语言的实现当中,也是使用这种方式处理冲突的。

    公共溢出区:这种方式是建立一个公共溢出区,当地址存在冲突时,把新的地址放在公共溢出区里。

    目前比较常用的冲突解决方法是链地址法,一般可以通过数组和链表的结合达到冲突数据缓存的目的。

    左侧数组的每个成员包括一个指针,指向一个链表的头。每发生一个冲突的数据,就将该数据作为链表的节点链接到链表尾部。这样一来,就可以保证冲突的数据能够区分并顺利访问。

    考虑到链表过长造成的问题,还可以使用红黑树替换链表进行冲突数据的处理操作,来提高散列表的查询稳定性。

     

     9  图

    图相较于上文的几个结构可能接触的不多,但是在实际的应用场景中却经常出现。比方说交通中的线路图,常见的思维导图都可以看作是图的具体表现形式。

    图结构一般包括顶点和边,顶点通常用圆圈来表示,边就是这些圆圈之间的连线。边还可以根据顶点之间的关系设置不同的权重,默认权重相同皆为1。此外根据边的方向性,还可将图分为有向图和无向图。

    图结构用抽象的图线来表示十分简单,顶点和边之间的关系非常清晰明了。但是在具体的代码实现中,为了将各个顶点和边的关系存储下来,却不是一件易事。

    邻接矩阵

    目前常用的图存储方式为邻接矩阵,通过所有顶点的二维矩阵来存储两个顶点之间是否相连,或者存储两顶点间的边权重。

    无向图的邻接矩阵是一个对称矩阵,是因为边不具有方向性,若能从此顶点能够到达彼顶点,那么彼顶点自然也能够达到此顶点。此外,由于顶点本身与本身相连没有意义,所以在邻接矩阵中对角线上皆为0。

    有向图由于边具有方向性,因此彼此顶点之间并不能相互达到,所以其邻接矩阵的对称性不再。

    用邻接矩阵可以直接从二维关系中获得任意两个顶点的关系,可直接判断是否相连。但是在对矩阵进行存储时,却需要完整的一个二维数组。若图中顶点数过多,会导致二维数组的大小剧增,从而占用大量的内存空间。

    而根据实际情况可以分析得,图中的顶点并不是任意两个顶点间都会相连,不是都需要对其边上权重进行存储。那么存储的邻接矩阵实际上会存在大量的0。虽然可以通过稀疏表示等方式对稀疏性高的矩阵进行关键信息的存储,但是却增加了图存储的复杂性。

    因此,为了解决上述问题,一种可以只存储相连顶点关系的邻接表应运而生。

    邻接表

    在邻接表中,图的每一个顶点都是一个链表的头节点,其后连接着该顶点能够直接达到的相邻顶点。相较于无向图,有向图的情况更为复杂,因此这里采用有向图进行实例分析。

    在邻接表中,每一个顶点都对应着一条链表,链表中存储的是顶点能够达到的相邻顶点。存储的顺序可以按照顶点的编号顺序进行。比如上图中对于顶点B来说,其通过有向边可以到达顶点A和顶点E,那么其对应的邻接表中的顺序即B->A->E,其它顶点亦如此。

    通过邻接表可以获得从某个顶点出发能够到达的顶点,从而省去了对不相连顶点的存储空间。然而,这还不够。对于有向图而言,图中有效信息除了从顶点“指出去”的信息,还包括从别的顶点“指进来”的信息。这里的“指出去”和“指进来”可以用出度和入度来表示。

    入度:有向图的某个顶点作为终点的次数和。

    出度:有向图的某个顶点作为起点的次数和。

    由此看出,在对有向图进行表示时,邻接表只能求出图的出度,而无法求出入度。这个问题很好解决,那就是增加一个表用来存储能够到达某个顶点的相邻顶点。这个表称作逆邻接表。

    逆邻接表

    逆邻接表与邻接表结构类似,只不过图的顶点链接着能够到达该顶点的相邻顶点。也就是说,邻接表时顺着图中的箭头寻找相邻顶点,而逆邻接表时逆着图中的箭头寻找相邻顶点。

    邻接表和逆邻接表的共同使用下,就能够把一个完整的有向图结构进行表示。可以发现,邻接表和逆邻接表实际上有一部分数据时重合的,因此可以将两个表合二为一,从而得到了所谓的十字链表。

    十字链表

    十字链表似乎很简单,只需要通过相同的顶点分别链向以该顶点为终点和起点的相邻顶点即可。

    但这并不是最优的表示方式。虽然这样的方式共用了中间的顶点存储空间,但是邻接表和逆邻接表的链表节点中重复出现的顶点并没有得到重复利用,反而是进行了再次存储。因此,上图的表示方式还可以进行进一步优化。

    十字链表优化后,可通过扩展的顶点结构和边结构来进行正逆邻接表的存储:(下面的弧头可看作是边的箭头那端,弧尾可看作是边的圆点那端)

    data:用于存储该顶点中的数据;

    firstin指针:用于连接以当前顶点为弧头的其他顶点构成的链表,即从别的顶点指进来的顶点;

    firstout指针:用于连接以当前顶点为弧尾的其他顶点构成的链表,即从该顶点指出去的顶点;

    边结构通过存储两个顶点来确定一条边,同时通过分别代表这两个顶点的指针来与相邻顶点进行链接:

    tailvex:用于存储作为弧尾的顶点的编号;

    headvex:用于存储作为弧头的顶点的编号;

    headlink 指针:用于链接下一个存储作为弧头的顶点的节点;

    taillink 指针:用于链接下一个存储作为弧尾的顶点的节点;

    以上图为例子,对于顶点A而言,其作为起点能够到达顶点E。因此在邻接表中顶点A要通过边AE(即边04)指向顶点E,顶点A的firstout指针需要指向边04的tailvex。同时,从B出发能够到达A,所以在逆邻接表中顶点A要通过边AB(即边10)指向B,顶点A的firstin指针需要指向边10的弧头,即headlink指针。依次类推。

    十字链表采用了一种看起来比较繁乱的方式对边的方向性进行了表示,能够在尽可能降低存储空间的情况下增加指针保留顶点之间的方向性。具体的操作可能一时间不好弄懂,建议多看几次上图,弄清指针指向的意义,明白正向和逆向邻接表的表示。

     

     10  总结

    数据结构博大精深,没有高等数学的讳莫如深,也没有量子力学的玄乎其神,但是其在计算机科学的各个领域都具有强大的力量。本文试图采用图解的方式对九种数据结构进行理论上的介绍,但是其实这都是不够的。

    即便是简单的数组、栈、队列等结构,在实际使用以及底层实现上都会有许多优化设计以及使用技巧,这意味着还需要真正把它们灵活的用起来,才能够算是真正意义上的熟悉和精通。但是本文可以作为常见数据结构的一个总结,当你对某些结构有些淡忘的时候,不妨重新回来看看。

    ------------

    感兴趣可微信搜索【业余码农】,阅读更多技术干货!

    展开全文
  • 数据结构与算法常见笔试题

    万次阅读 多人点赞 2017-09-10 11:03:57
    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) 

     

    展开全文
  • 数据结构1800题及答案.pdf

    热门讨论 2011-12-04 17:11:44
    复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于( ) 【中科院计算所 1998 二、1 (2 分) 】 A.问题的规模 B. 待处理数据的初态 C. A 和B 3.计算机算法指的是(1) ,它必须具备(2) 这三个特性。 (1)...
  • 数据结构---C++版

    千次阅读 多人点赞 2020-02-11 13:45:11
    1.1 数据结构在程序设计中的作用 1)程序设计的实质是什么? 数据表示:将数据存储在计算机(内存)中 数据处理:处理数据,设计方案(算法) 1.2 计算机求解问题: 1)问题→抽象出问题的模型→求模型的解 问题——...
  • 数据结构中的时间复杂度的计算

    万次阅读 多人点赞 2017-09-07 18:51:32
    时间复杂度或称时间复杂性,又称计算复杂度,她说是算法有效的度量之一,时间复杂度是一个算法运行时间的相对度量,一个算法的运行时间长短,它大致等于执行一种简单操作所(赋值、比较、计算、转向、返回、输入和...
  • 数据结构:是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、(存储)物理结构和数据的运算三个部分。 为什么要学数据结构? 首先,因为数据结构作为...
  • 山东大学软件学院数据结构

    千次阅读 多人点赞 2019-12-12 10:48:30
    1.时间复杂性和空间复杂性,给一个算法,能分析时间复杂性 2.熟练掌握各种排序和搜索算法 3.矩阵的运算 第三章 1.给一个算法,熟练使用渐进符号 第四章 1.无 第五章 1.数组描述的插入、删除、优缺点 第六章...
  • 数据结构1

    千次阅读 2018-04-01 20:56:40
     数据结构相同,对应的存储结构也相同数据结构涉及数据的逻辑结构、存储结构和施加其上的操作3个方面数据结构操作的实现与存储结构有关定义逻辑结构时可不考虑存储结构2-3以下关于数据结构的说法中正确的是(A )。...
  • 深刻的体会到了,MongoDB可以不设计集合的结构和数据类型即可使用,但不代表它不需要数据结构设计。一个好的系统运作,肯定需要对MongoDB的数据结构进行合理的设计才能高效运行。当然,我也不建议在业务初期就进行...
  • 数据结构与算法学习笔记

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

    万次阅读 多人点赞 2018-04-29 11:53:50
    第一部分:Java数据结构要理解Java数据结构,必须能清楚何为数据结构数据结构:Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系。而各数据元素之间的相互关系,又...
  • 四种基本数据结构

    千次阅读 2019-03-18 09:29:46
    集合结构:该结构数据元素间的关系是“属于同一个集合”; 线性结构:该结构数据元素之间存在一对一的关系; 树形结构:该结构数据元素之间存在一对多的关系; 图形结构:该结构数据元素之间存在多对多的...
  • 数据结构与算法真的那么重要么?

    千次阅读 多人点赞 2019-03-25 13:41:04
    很多同学对数据结构与算法的第一印象,可能是觉得它复杂、深奥、难以理解。之所以会有这种观念,我认为主要是因为没有找到适合自己的学习方法及学习资料。其实学习任何知识点,只要找到对的学习方法和学习资料,都能...
  • 基于数据驱动设计复杂页面

    千次阅读 多人点赞 2018-09-01 15:10:23
    最近公司启动了一个新的版本,我负责的一个的模块中有一个很复杂的新建的页面,表格里嵌套表格,三层数据,数据级联,组件较多.交互复杂, 下面是我做的一个简略图,为了保密我已将需求细节隐藏.(PS:没有table组件的墨刀,...
  • 常用数据结构与常用算法,

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

    万次阅读 多人点赞 2018-03-06 10:11:00
    同一个问题,如何有效地存储数据,不同的数据结构产生什么样的算法复杂性,有没有更好的存储方法提高算法的效率?通过学习数据结构,更加准确和深刻地理解不同数据结构之间的共性和联系,学会选择和改进数据结构,...
  • 数据结构算法的描述和分析

    千次阅读 2018-08-17 19:25:49
    数据结构概论 高级语言程序设计在解决某一实际问题的一般步骤是:分析实际问题、确定数学模型、设计或选择一个求解此数学模型的算法、编写程序进行调试和测试解决问题等几个步骤。 例1:已知:游泳池的长length和...
  • 数据结构 耿国华老师讲

    千次阅读 2020-02-08 19:54:09
    第一讲$数据结构的基础 数据是表征客观事物的可记录可识别的符号集合。数据是信息处理的核心基础。 数据结构有关的基本概念术语: 1.数据 2.数据元素 3.数据对象 4.数据类型 5.数据类型 6.抽象数据类型 7.数据结构 ...
  • 数据结构真的很难学?

    千次阅读 2019-08-16 13:41:52
    在学习算法的同时,逐步熟练应用、改进数据结构,慢慢体会不同数据结构和算法策略的算法复杂性,最终学会利用数据结构改进和优化算法。这一阶段已经在数据结构之上,可以通过在ACM测试系统上刷各种算法题,体会数据...
  • 通用数据结构:数组,链表,树,哈希表 通用数据结构通过关键字的值来存储并查找数据,如报表,合同,记录,业绩等数据。通用数据结构可以用速度的快慢来分类,数组和链表是最慢的,树相对较快,哈希表是最快的。请...
  • 数据结构(c语言版)代码

    万次阅读 多人点赞 2019-01-07 13:42:00
    文档中源码及测试数据存放目录:数据结构\▲课本算法实现\▲01 绪论 概述 第一章作为绪论,主要介绍了数据结构与算法中的一些基本概念和术语。对于这些概念术语,我个人不推崇死记硬背,记住了当然好,记不住也...
  • 数据结构课程设计实验报告

    万次阅读 2017-06-08 21:54:02
    《算法与数据结构》课程设计报告  数据结构课程设计是在学完数据结构课程之后的实践教学环节。本实践教学是培养学生数据抽象能力,进行复杂程序设计的训练过程。要求学生能对所涉及问题选择合适的数据结构、存储...
  • 学习数据结构的意义和作用

    万次阅读 多人点赞 2018-09-03 22:48:45
    什么是数据结构,为什么要学习数据结构数据结构是否是一门纯数学课程?它在专业课程体系中起什么样的作用?我们要怎么才能学好数据结构?… 相信同学们在刚开始《数据结构》这门课的学习时,心里有着类似前面几个...
  • 数据结构第一章概论习题及答案

    千次阅读 2020-04-05 12:30:16
    1.数据表示 2.数据处理 3.数据 4.数据元素 5.逻辑关系 6.逻辑结构 7.结构 8.运算 9.基本运算 10.存储结构 11.顺序存储结构 12.链式存储结构 13.索引存储结构 14.散列存储结构 15.算法 16.运行终止的...
  • 数据结构知识点汇总

    万次阅读 多人点赞 2018-07-18 15:44:21
    4、栈通常采用的两种存储结构是(线性存储结构和链表存储结构) 5、队列具有(先进先出)的特征,栈具有(后进先出)的特征。 6、链表(插入和删除不需要移动元素,但是无法随机访问任一元素) 7、循环链表的主要...
  • 数据结构与算法Python语言描述》裘宗燕 笔记系列 该系列笔记结合PPT的内容整理的,方便以后复习,有需要的朋友可以看一下。 源码重新整理了 地址:https://github.com/StarsAaron/DS/tree/master   理解三个...
  • 如何理解数据结构中的抽象数据类型?

    万次阅读 多人点赞 2018-09-04 18:49:23
    抽象数据类型的标准格式 ADT 抽象数据类型名 { Data: 数据元素之间逻辑关系的定义; Operation: 操作1; 操作2; ... } 什么是抽象数据类型? 抽象数据类型(Abstract Data Type,ADT)是指一个数学...
  • 面试常考的常用数据结构与算法

    万次阅读 2017-12-07 09:57:34
    面试常考的常用数据结构与算法 数据结构与算法,这个部分的内容其实是十分的庞大,要想都覆盖到不太容易。在校学习阶段我们可能需要对每种结构,每种算法都学习,但是找工作笔试或者面试的时候,要在很短的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 990,601
精华内容 396,240
关键字:

数据结构的复杂性

数据结构 订阅