类也是一种数据结构_定义一个栈类,用于模拟一种具有后进先出特性的数据结构 - CSDN
  • 什么是数据结构

    万次阅读 2007-03-19 10:30:00
    数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成,即一个数据由那些成分数据构成,以什么方式... 数据结构是信息的一种组织方式,其目的是为了提高算法的效率,它通常与一组算
     
    
    数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成,即一个数据由那些成分数据构成,以什么方式构成,呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系,而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。  数据结构是信息的一种组织方式,其目的是为了提高算法的效率,它通常与一组算法的集合相对应,通过这组算法集合可以对数据结构中的数据进行某种操作。

     

    数据结构与算法总论

     (一)何谓数据结构
            数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成,即一个数据由那些成分数据构成,以什么方式构成,呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系,而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 数据结构是信息的一种组织方式,其目的是为了提高算法的效率,它通常与一组算法的集合相对应,通过这组算法集合可以对数据结构中的数据进行某种操作。

            数据结构主要研究什么?

            数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构,以及对数据的各种操作。因此,主要有三个方面的内容:数据的逻辑结构;数据的物理存储结构;对数据的操作(或算法)。通常,算法的设计取决于数据的逻辑结构,算法的实现取决于数据的物理存储结构。

            什么是数据结构?什么是逻辑结构和物理结构?

            数据是指由有限的符号(比如,"0"和"1",具有其自己的结构、操作、和相应的语义)组成的元素的集合。结构是元素之间的关系的集合。通常来说,一个数据结构DS 可以表示为一个二元组:

            DS=(D,S), //i.e., data-structure=(data-part,logic-structure-part)

            这里D是数据元素的集合(或者是"结点",可能还含有"数据项"或"数据域"),S是定义在D(或其他集合)上的关系的集合,S = { R | R : D×D×...},称之为元素的逻辑结构。 逻辑结构有四种基本类型:集合结构、线性结构、树状结构和网络结构。表和树是最常用的两种高效数据结构,许多高效的算法可以用这两种数据结构来设计实现。表是线性结构的(全序关系),树(偏序或层次关系)和图(局部有序(weak/local orders))是非线性结构。

            数据结构的物理结构是指逻辑结构的存储镜像(image)。数据结构 DS 的物理结构 P对应于从 DS 的数据元素到存储区M(维护着逻辑结构S)的一个映射:
            P(D,S) -- > M 存储器模型:一个存储器 M 是一系列固定大小的存储单元,每个单元 U 有一个唯一的地址 A(U),该地址被连续地编码。每个单元 U 有一个唯一的后继单元 U'=succ(U)。 P 的四种基本映射模型:顺序(sequential)、链接(linked)、索引(indexed)和散列(hashing)映射。
            因此,我们至少可以得到4×4种可能的物理数据结构:

            sequential (sets)
            linked lists
            indexed trees
            hash graphs

            (并不是所有的可能组合都合理)数据结构DS上的操作:所有的定义在DS上的操作在改变数据元素(节点)或节点的域时必须保持DS的逻辑和物理结构。

            DS上的基本操作:任何其他对DS的高级操作都可以用这些基本操作来实现。最好将DS和他的所有基本操作看作一个整体——称之为模块。我们可以进一步将该模块抽象为数据类型(其中DS的存储结构被表示为私有成员,基本操作被表示为公共方法),称之为ADT。作为ADT,堆栈和队列都是一种特殊的表,他们拥有表的操作的子集。 对于DATs的高级操作可以被设计为(不封装的)算法,利用基本操作对DS进行处理。

            好的和坏的DS:如果一个DS可以通过某种"线性规则"被转化为线性的DS(例如线性表),则称它为好的DS。好的DS通常对应于好的(高效的)算法。这是由计算机的计算能力决定的,因为计算机本质上只能存取逻辑连续的内存单元,因此如何没有线性化的结构逻辑上是不可计算的。比如对一个图进行操作,要访问图的所有结点,则必须按照某种顺序来依次访问所有节点(要形成一个偏序),必须通过某种方式将图固有的非线性结构转化为线性结构才能对图进行操作。

            树是好的DS——它有非常简单而高效的线性化规则,因此可以利用树设计出许多非常高效的算法。树的实现和使用都很简单,但可以解决大量特殊的复杂问题,因此树是实际编程中最重要和最有用的一种数据结构。树的结构本质上有递归的性质——每一个叶节点可以被一棵子树所替代,反之亦然。实际上,每一种递归的结构都可以被转化为(或等价于)树形结构。

            从机器语言到高级语言的抽象

            我们知道,算法被定义为一个运算序列。这个运算序列中的所有运算定义在一类特定的数据模型上,并以解决一类特定问题为目标。这个运算序列应该具备下列四个特征。 有限性,即序列的项数有限,且每一运算项都可在有限的时间内完成;确定性,即序列的每一项运算都有明确的定义,无二义性;可以没有输入运算项,但一定要有输出运算项;可行性,即对于任意给定的合法的输入都能得到相应的正确的输出。这些特征可以用来判别一个确定的运算序列是否称得上是一个算法。 但是,我们现在的问题不是要判别一个确定的运算序列是否称得上是一个算法,而是要对一个己经称得上是算法的运算序列,回顾我们曾经如何用程序设计语言去表达它。

            算法的程序表达,归根到底是算法要素的程序表达,因为一旦算法的每一项要素都用程序清楚地表达,整个算法的程序表达也就不成问题。

            作为运算序列的算法,有三个要素。 作为运算序列中各种运算的运算对象和运算结果的数据;运算序列中的各种运算;运算序列中的控制转移。这三种要素依序分别简称为数据、运算和控制。 由于算法层出不穷,变化万千,其中的运算所作用的对象数据和所得到的结果数据名目繁多,不胜枚举。最简单最基本的有布尔值数据、字符数据、整数和实数数据等;稍复杂的有向量、矩阵、记录等数据;更复杂的有集合、树和图,还有声音、图形、图像等数据。 同样由于算法层出不穷,变化万千,其中运算的种类五花八门、多姿多彩。最基本最初等的有赋值运算、算术运算、逻辑运算和关系运算等;稍复杂的有算术表达式和逻辑表达式等;更复杂的有函数值计算、向量运算、矩阵运算、集合运算,以及表、栈、队列、树和图上的运算等:此外,还可能有以上列举的运算的复合和嵌套。 关于控制转移,相对单纯。在串行计算中,它只有顺序、分支、循环、递归和无条件转移等几种。

            我们来回顾一下,自从计算机问世以来,算法的上述三要素的程序表达,经历过一个怎样的过程。 最早的程序设计语言是机器语言,即具体的计算机上的一个指令集。当时,要在计算机上运行的所有算法都必须直接用机器语言来表达,计算机才能接受。算法的运算序列包括运算对象和运算结果都必须转换为指令序列。其中的每一条指令都以编码(指令码和地址码)的形式出现。与算法语言表达的算法,相差十万八千里。对于没受过程序设计专门训练的人来说,一份程序恰似一份"天书",让人看了不知所云,可读性极差。 用机器语言表达算法的运算、数据和控制十分繁杂琐碎,因为机器语言所提供的指令太初等、原始。机器语言只接受算术运算、按位逻辑运算和数的大小比较运算等。对于稍复杂的运算,都必须一一分解,直到到达最初等的运算才能用相应的指令替代之。机器语言能直接表达的数据只有最原始的位、字节、和字三种。算法中即使是最简单的数据如布尔值、字符、整数、和实数,也必须一一地映射到位、字节和字中,还得一一分配它们的存储单元。对于算法中有结构的数据的表达则要麻烦得多。机器语言所提供的控制转移指令也只有无条件转移、条件转移、进入子程序和从子程序返回等最基本的几种。用它们来构造循环、形成分支、调用函数和过程得事先做许多的准备,还得靠许多的技巧。 直接用机器语言表达算法有许多缺点。
            大量繁杂琐碎的细节牵制着程序员,使他们不可能有更多的时间和精力去从事创造性的劳动,执行对他们来说更为重要的任务。如确保程序的正确性、高效性。程序员既要驾驭程序设计的全局又要深入每一个局部直到实现的细节,即使智力超群的程序员也常常会顾此失彼,屡出差错,因而所编出的程序可靠性差,且开发周期长。 由于用机器语言进行程序设计的思维和表达方式与人们的习惯大相径庭,只有经过较长时间职业训练的程序员才能胜任,使得程序设计曲高和寡。因为它的书面形式全是"密"码,所以可读性差,不便于交流与合作。因为它严重地依赖于具体的计算机,所以可移植性差,重用性差。这些弊端造成当时的计算机应用未能迅速得到推广。 克服上述缺点的出路在于程序设计语言的抽象,让它尽可能地接近于算法语言。 为此,人们首先注意到的是可读性和可移植性,因为它们相对地容易通过抽象而得到改善。于是,很快就出现汇编语言。这种语言对机器语言的抽象,首先表现在将机器语言的每一条指令符号化:指令码代之以记忆符号,地址码代之以符号地址,使得其含义显现在符号上而不再隐藏在编码中,可让人望"文"生义。其次表现在这种语言摆脱了具体计算机的限制,可在不同指令集的计算机上运行,只要该计算机配上汇编语言的一个汇编程序。这无疑是机器语言朝算法语言靠拢迈出的一步。但是,它离算法语言还太远,以致程序员还不能从分解算法的数据、运算和控制到汇编才能直接表达的指令等繁杂琐碎的事务中解脱出来。 到了50年代中期,出现程序设计的高级语言如Fortran,Algol60,以及后来的PL/l, Pascal等,算法的程序表达才产生一次大的飞跃。
            诚然,算法最终要表达为具体计算机上的机器语言才能在该计算机上运行,得到所需要的结果。但汇编语言的实践启发人们,表达成机器语言不必一步到位,可以分两步走或者可以筑桥过河。即先表达成一种中介语言,然后转成机器语言。汇编语言作为一种中介语言,并没有获得很大成功,原因是它离算法语言还太远。这便指引人们去设计一种尽量接近算法语言的规范语言,即所谓的高级语言,让程序员可以用它方便地表达算法,然后借助于规范的高级语言到规范的机器语言的"翻译",最终将算法表达为机器语言。而且,由于高级语言和机器语言都具有规范性,这里的"翻译"完全可以机械化地由计算机来完成,就像汇编语言被翻译成机器语言一样,只要计算机配上一个编译程序。 上述两步,前一步由程序员去完成,后一步可以由编译程序去完成。在规定清楚它们各自该做什么之后,这两步是完全独立的。它们各自该如何做互不相干。前一步要做的只是用高级语言正确地表达给定的算法,产生一个高级语言程序;后一步要做的只是将第一步得到的高级语言程序翻译成机器语言程序。至于程序员如何用高级语言表达算法和编译程序如何将高级语言表达的算法翻译成机器语言表达的算法,显然毫不相干。

     处理从算法语言最终表达成机器语言这一复杂过程的上述思想方法就是一种抽象。汇编语言和高级语言的出现都是这种抽象的范例。 与汇编语言相比,高级语言的巨大成功在于它在数据、运算和控制三方面的表达中引入许多接近算法语言的概念和工具,大大地提高抽象地表达算法的能力。 在运算方面,高级语言如Pascal,除允许原封不动地运用算法语言的四则运算、逻辑运算、关系运算、算术表达式、逻辑表达式外,还引入强有力的函数与过程的工具,并让用户自定义。这一工具的重要性不仅在于它精简了重复的程序文本段,而且在于它反映出程序的两级抽象。在函数与过程调用级,人们只关心它能做什么,不必关心它如何做。只是到函数与过程的定义时,人们才给出如何做的细节。用过高级语言的读者都知道,一旦函数与过程的名称、参数和功能被规定清楚,那么,在程序中调用它们便与在程序的头部说明它们完全分开。你可以修改甚至更换函数体与过程体,而不影响它们的被调用。如果把函数与过程名看成是运算名,把参数看成是运算的对象或运算的结果,那么,函数与过程的调用和初等运算的引用没有两样。利用函数和过程以及它们的复合或嵌套可以很自然地表达算法语言中任何复杂的运算。 在数据方面,高级语言如Pascal引人了数据类型的概念,即把所有的数据加以分类。每一个数据(包括表达式)或每一个数据变量都属于其中确定的一类。称这一类数据为一个数据类型。 因此,数据类型是数据或数据变量类属的说明,它指示该数据或数据变量可能取的值的全体。对于无结构的数据,高级语言如Pascal,除提供标准的基本数据类型--布尔型、字符型、整型和实型外,还提供用户可自定义的枚举类型、子界类型和指针类型。这些类型(除指针外),其使用方式都顺应人们在算法语言中使用的习惯。对于有结构的数据,高级语言如Pascal,提供了数组、记录、有限制的集合和文件等四种标准的结构数据类型。其中,数组是科学计算中的向量、矩阵的抽象;记录是商业和管理中的记录的抽象;有限制的集合是数学中足够小的集合的势集的抽象;文件是诸如磁盘等外存储数据的抽象。人们可以利用所提供的基本数据类型(包括标准的和自定义的),按数组、记录、有限制的集合和文件的构造规则构造有结构的数据。 此外,还允许用户利用标准的结构数据类型,通过复合或嵌套构造更复杂更高层的结构数据。这使得高级语言中的数据类型呈明显的分层。 高级语言中数据类型的分层是没有穷尽的,因而用它们可以表达算法语言中任何复杂层次的数据。 在控制方面,高级语言如Pascal,提供了表达算法控制转移的六种方式。
            (1)缺省的顺序控制";"。
            (2)条件(分支)控制:"if表达式(为真)then S1 else S2;" 。
            (3)选择(情况)控制:
            "Case 表达式 of
            值1: S1
            值2: S2
            ...
            值n: Sn
            end"
            (4)循环控制:
            "while 表达式(为真) do S;" 或
            "repeat S until 表达式(为真);" 或
            "for变量名:=初值 to/downto 终值do S;"
            (5)函数和过程的调用,包括递归函数和递归过程的调用。
            (6)无条件转移goto。
             
            这六种表达方式不仅覆盖了算法语言中所有控制表达的要求,而且不再像机器语言或汇编语言那样原始、那样繁琐、那样隐晦,而是如上面所看到的,与自然语言的表达相差无几。 程序设计语言从机器语言到高级语言的抽象,带来的主要好处是: 高级语言接近算法语言,易学、易掌握,一般工程技术人员只要几周时间的培训就可以胜任程序员的工作;高级语言为程序员提供了结构化程序设计的环境和工具,使得设计出来的程序可读性好,可维护性强,可靠性高;高级语言远离机器语言,与具体的计算机硬件关系不大,因而所写出来的程序可移植性好,重用率高; 由于把繁杂琐碎的事务交给了编译程序去做,所以自动化程度高,开发周期短,且程、序员得到解脱,可以集中时间和精力去从事对于他们来说更为重要的创造性劳动,以提高、程序的质量。

            数据结构、数据类型和抽象数据类型

            数据结构、数据类型和抽象数据类型,这三个术语在字面上既不同又相近,反映出它们在含义上既有区别又有联系。

            数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成,即一个数据由哪些成分数据构成,以什么方式构成,呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系,物理上的数据结构反映成分数据在计算机内的存储安排。数据结构是数据存在的形式。

            数据是按照数据结构分类的,具有相同数据结构的数据属同一类。同一类数据的全体称为一个数据类型。在程序设计高级语言中,数据类型用来说明一个数据在数据分类中的归属。它是数据的一种属性。这个属性限定了该数据的变化范围。为了解题的需要,根据数据结构的种类,高级语言定义了一系列的数据类型。不同的高级语言所定义的数据类型不尽相同。Pascal语言所定义的数据类型的种类。

            其中,简单数据类型对应于简单的数据结构;构造数据类型对应于复杂的数据结构;在复杂的数据结构里,允许成分数据本身具有复杂的数据结构,因而,构造数据类型允许复合嵌套;指针类型对应于数据结构中成分数据之间的关系,表面上属简单数据类型,实际上都指向复杂的成分数据即构造数据类型中的数据,因此这里没有把它划入简单数据类型,也没有划入构造数据类型,而单独划出一类。
            数据结构反映数据内部的构成方式,它常常用一个结构图来描述:数据中的每一项成分数据被看作一个结点,并用方框或圆圈表示,成分数据之间的关系用相应的结点之间带箭号的连线表示。如果成分数据本身又有它自身的结构,则结构出现嵌套。这里嵌套还允许是递归的嵌套。

            由于指针数据的引入,使构造各种复杂的数据结构成为可能。按数据结构中的成分数据之间的关系,数据结构有线性与非线性之分。在非线性数据结构中又有层次与网状之分。 由于数据类型是按照数据结构划分的,因此,一类数据结构对应着一种数据类型。数据类型按照该类型中的数据所呈现的结构也有线性与非线性之分,层次与网状之分。一个数据变量,在高级语言中的类型说明必须是读变量所具有的数据结构所对应的数据类型。最常用的数据结构是数组结构和记录结构。数组结构的特点是:

            成分数据的个数固定,它们之间的逻辑关系由成分数据的序号(或叫数组的下标)来体现。这些成分数据按照序号的先后顺序一个挨一个地排列起来。每一个成分数据具有相同的结构(可以是简单结构,也可以是复杂结构),因而属于同一个数据类型(相应地是简单数据类型或构造数据类型)。这种同一的数据类型称为基类型。所有的成分数据被依序安排在一片连续的存储单元中。 概括起来,数组结构是一个线性的、均匀的、其成分数据可随机访问的结构。由于这、种结构有这些良好的特性,所以最常被人们所采用。在高级语言中,与数组结构相对应的、数据类型是数组类型,即数组结构的数据变量必须说明为array [i] of T0 ,其中i是数组、结构的下标类型,而T0是数组结构的基类型。 记录结构是另一种常用的数据结构。它的特点是:与数组结构一样,成分数据的个数固定。但成分数据之间没有自然序,它们处于平等地位。每一个成分数据被称为一个域并赋予域名。不同的域有不同的域名。不同的域允许有不同的结构,因而允许属于不同的数据类型。与数组结构一样,它们可以随机访问,但访问的途径靠的是域名。在高级语言中记录结构对应的数据类型是记录类型。记录结构的数据的变量必须说明为记录类型。

            抽象数据类型的含义在上一段已作了专门叙述。它可理解为数据类型的进一步抽象。即把数据类型和数据类型上的运算捆在一起,进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开,使它们相互独立。对于抽象数据类型的描述,除了必须描述它的数据结构外,还必须描述定义在它上面的运算(过程或函数)。抽象数据类型上定义的过程和函数以该抽象数据类型的数据所应具有的数据结构为基础。

    (二)泛型设计和数据结构与算法
            下面我想再说说关于泛型程序设计模型对于数据结构和算法方面的最新推动,泛型思想已经把数据结构和算法方面的基本思想抽象到了一个前所未有的高度,现在有多种程序设计语言支持泛型设计,比如ADA,C++,而且据说在JAVA的下一版本和C#中也将对泛型设计进行全面的支持。

            先说说泛型设计的基本思想:泛型编程(generic programming,以下直接以GP称呼)是一种全新的程序设计思想,和OO,OB,PO这些为人所熟知的程序设计想法不同的是GP抽象度更高,基于GP设计的组件之间偶合度底,没有继承关系,所以其组件间的互交性和扩展性都非常高。我们都知道,任何算法都是作用在一种特定的数据结构上的,最简单的例子就是快速排序算法最根本的实现条件就是所排序的对象是存贮在数组里面,因为快速排序就是因为要用到数组的随机存储特性,即可以在单位时间内交换远距离的对象,而不只是相临的两个对象,而如果用联表去存储对象,由于在联表中取得对象的时间是线性的既O[n],这样将使快速排序失去其快速的特点。也就是说,我们在设计一种算法的时候,我们总是先要考虑其应用的数据结构,比如数组查找,联表查找,树查找,图查找其核心都是查找,但因为作用的数据结构不同将有多种不同的表现形式。数据结构和算法之间这样密切的关系一直是我们以前的认识。泛型设计的根本思想就是想把算法和其作用的数据结构分离,也就是说,我们设计算法的时候并不去考虑我们设计的算法将作用于何种数据结构之上。泛型设计的理想状态是一个查找算法将可以作用于数组,联表,树,图等各种数据结构之上,变成一个通用的,泛型的算法。这样的理想是不是很诱惑人?

            泛型编程带来的是前所未有的弹性以及不会损失效率的抽象性,GP和OO不同,它不要求你通过额外的间接层来调用函数:它让你撰写完全一般化并可重复使用的算法,其效率与针对特定数据结构而设计的算法旗鼓相当。我们大家都知道数据结构在C++中可以用用户定义类型来表示,而C++中的模板技术就是以类型作为参数,那么我可以想象利用模板技术可以实现我们开始的GP思想,即一个模板函数可以对于各种传递进来的类型起作用,而这些类型就可以是我们定义的各种数据结构。泛型算法抽离于特定类型和特定数据结构之外,使得其适应与尽可能的一般化类型,算法本身只是为了实现算法其需要表达的逻辑本质而不去被为各种数据结构的实现细节所干扰。这意味着一个泛型算法实际具有两部分。1,用来描叙算法本质逻辑的实际指令;2,正确指定其参数类型必须满足的性质的一组需求条件。到此,相信有不少人已经开始糊涂了,呵呵,不要紧。毕竟GP是一种抽象度非常高的程序设计思想,里面的核心就是抽象条件成为成为程序设计过程中的核心,从而取代了类型这在OO里面的核心地位,正是因为类型不在是我们考虑的重点,类型成为了抽象条件的外衣,所以我们称这样的程序思想为泛型思想------把类型泛化。

    (三)个人学习心得
            至于如何学习数据结构,我个人认为合适的方法是,首先从根本上就要认识到数据结构的本质,数据结构和算法之间的密切关系,以及数据结构的应用方法。不然我们很可能陷入各种数据结构的复杂特性中却还根本不知道到底什么才是数据结构的本质,学了很多很久却其实什么都没有弄明白,在这里我说点我个人的一点关于数据结构本质的东西:

            学好数据结构最重要的是对程序设计方式和程序语言概念和实现的理解int i;
            int i[];
            struct i{};
            ADT i{};
            到底有什么区别,这就是程序设计语言实现的问题了。
            定义了一种数据类型就是定义了一类操作
            int i,j;i=j+1;
            这样的操作在语言本身中实现了,也就是说你不需要关心这样的操作程序语言是如何完成的,所以int就是基本数据类型

            抽象了基本数据类型的就是数据结构。
            当你定义了
            ADT P{};
            的时候,比如如果P是链表,这就要你去实现它各种的操作。而且P能够完成的所有操作都必须由你去实现,而你实现得基础就是这些char int float *p...基本数据类型。这就是抽象数据类型。
            当你把类型定义完成后,剩下的就是算法去完成程序流程的控制。

            所以:数据结构+算法=程序

            还想说点的是,设计思想,程序设计语言,和数据结构,始终是促进计算机软件科学发展的最大动力。一般来说都是思想先与语言,然后出现支持这种思想和包含这样思想的数据类型的语言实现。

            具体说:
            面向机器编程 机器语言,汇编语言
            面向过程编程 C。。。。语言
            面向对象编程 JAVA C++
            当然思想毕竟只是思想,你可以用不同的语言实现。但必须说明的是只能用一个层面上的语言实现。 比如,机器语言,由于其语言本身抽象层很低,低到了就像给一个对象赋值的操作也要程序员进行位操作。为在语言实现这个层面上,它不支持。 为什么说C也可以进面向对象的编程呢?关键就在C很好的支持ADT了。他可以用复杂了ADT去代替C++中已经变成基本数据类型的CLASS,但是正是因为要用C完成OO,必须程序员来实现(定义ADT)。所以说,C不适合开发OO软件。而C++却恰恰把CLASS定义成了一个基本类型,这样就完成了OO这一个层次的抽象。当然由于C++是C的超集,他同样是完全支持面向过程的。

            说了这么多,就是想说说 数据结构和程序语言和设计思想的关系。当我们能把数据结构的学习和程序设计语言,程序设计想法相联系起来的时候,我想我们对数据结构本身的认识已经更加深刻了,我们学习到每一种的新的数据结构的时候我们不再恐慌,因为我们知道了任何一种数据结构都有其共同的共性和特殊的特性,每一种数据结构都是为了一个领域所现实的,从这一方面来说,数据结构本身就具有继承特性,我们可以用一个继承树来表示一个完整的数据结构体系,而每一种数据结构都是继承体系中的一个子节点。

            最后在这里我推荐几本我觉得比较出色的数据结构方面的教材:


            《数据结构与算法------面向对象的C++设计模式》 电子工业出版社出版。在amazon上是五星评价,个人认为其对数据结构的整体描叙和对各种应用算法十分出色。

            《Algorithm in c++ I-V》是RS的著作《Algorithm in c》的C++版本,完整的描叙了各种算法,amazon上五星评价,高等教育出版社有其影印版。

            《data structrus in C++ with STL》 使用C++标准模板库来描叙数据结构,是使用泛型设计的方法描叙数据结构的一本全面教材。清华出版了中文版,但有其影印版。


    展开全文
  • 数据结构:八大数据结构分类

    万次阅读 多人点赞 2018-09-05 18:23:28
    一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。 1、数组 数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0...

    本文目录:

    数据结构分类

    数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。
    常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示:
    这里写图片描述
    每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。

    1、数组

    数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。

    int[] data = new int[100];data[0]  = 1;
    

    优点:
    1、按照索引查询元素速度快
    2、按照索引遍历数组方便

    缺点:
    1、数组的大小固定后就无法扩容了
    2、数组只能存储一种类型的数据
    3、添加,删除的操作慢,因为要移动其他的元素。

    适用场景:
    频繁查询,对存储空间要求不大,很少增加和删除的情况。

    2、栈

    栈是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。 栈的特点是:先进后出,或者说是后进先出,从栈顶放入元素的操作叫入栈,取出元素叫出栈。
    这里写图片描述
    栈的结构就像一个集装箱,越先放进去的东西越晚才能拿出来,所以,栈常应用于实现递归功能方面的场景,例如斐波那契数列。

    3、队列

    队列与栈一样,也是一种线性表,不同的是,队列可以在一端添加元素,在另一端取出元素,也就是:先进先出。从一端放入元素的操作称为入队,取出元素为出队,示例图如下:
    这里写图片描述
    使用场景:因为队列先进先出的特点,在多线程阻塞队列管理中非常适用。

    4、链表

    链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。根据指针的指向,链表能形成不同的结构,例如单链表,双向链表,循环链表等。
    这里写图片描述
    链表的优点:
    链表是很常用的一种数据结构,不需要初始化容量,可以任意加减元素;
    添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可,所以添加,删除很快;

    缺点:
    因为含有大量的指针域,占用空间较大;
    查找元素需要遍历链表来查找,非常耗时。

    适用场景:
    数据量较小,需要频繁增加,删除操作的场景

    5、树

    是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

    • 每个节点有零个或多个子节点;
    • 没有父节点的节点称为根节点;
    • 每一个非根节点有且只有一个父节点;
    • 除了根节点外,每个子节点可以分为多个不相交的子树;

    在日常的应用中,我们讨论和用的更多的是树的其中一种结构,就是二叉树
    这里写图片描述
    二叉树是树的特殊一种,具有如下特点:

    1、每个结点最多有两颗子树,结点的度最大为2。
    2、左子树和右子树是有顺序的,次序不能颠倒。
    3、即使某结点只有一个子树,也要区分左右子树。

    二叉树是一种比较有用的折中方案,它添加,删除元素都很快,并且在查找方面也有很多的算法优化,所以,二叉树既有链表的好处,也有数组的好处,是两者的优化方案,在处理大批量的动态数据方面非常有用。

    扩展:
    二叉树有很多扩展的数据结构,包括平衡二叉树、红黑树、B+树等,这些数据结构二叉树的基础上衍生了很多的功能,在实际应用中广泛用到,例如mysql的数据库索引结构用的就是B+树,还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大,但算法上比较复杂,想学习的话还是需要花时间去深入的。

    6、散列表

    散列表,也叫哈希表,是根据关键码和值 (key和value) 直接进行访问的数据结构,通过key和value来映射到集合中的一个位置,这样就可以很快找到集合中的对应元素。

    记录的存储位置=f(key)

    这里的对应关系 f 成为散列函数,又称为哈希 (hash函数),而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里,这种存储空间可以充分利用数组的查找优势来查找元素,所以查找的速度很快。

    哈希表在应用中也是比较常见的,就如Java中有些集合类就是借鉴了哈希原理构造的,例如HashMap,HashTable等,利用hash表的优势,对于集合的查找元素时非常方便的,然而,因为哈希表是基于数组衍生的数据结构,在添加删除元素方面是比较慢的,所以很多时候需要用到一种数组链表来做,也就是拉链法。拉链法是数组结合链表的一种结构,较早前的hashMap底层的存储就是采用这种结构,直到jdk1.8之后才换成了数组加红黑树的结构,其示例图如下:
    这里写图片描述
    从图中可以看出,左边很明显是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。

    哈希表的应用场景很多,当然也有很多问题要考虑,比如哈希冲突的问题,如果处理的不好会浪费大量的时间,导致应用崩溃。

    7、堆

    堆是一种比较特殊的数据结构,可以被看做一棵树的数组对象,具有以下的性质:

    • 堆中某个节点的值总是不大于或不小于其父节点的值;

    • 堆总是一棵完全二叉树。

    将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

    堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆。
    (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2),满足前者的表达式的成为小顶堆,满足后者表达式的为大顶堆,这两者的结构图可以用完全二叉树排列出来,示例图如下:
    这里写图片描述
    因为堆有序的特点,一般用来做数组中的排序,称为堆排序。

    8、图

    图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。

    按照顶点指向的方向可分为无向图和有向图:
    这里写图片描述
    这里写图片描述
    图是一种比较复杂的数据结构,在存储数据上有着比较复杂和高效的算法,分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构,这里不做展开,读者有兴趣可以自己学习深入。

    展开全文
  • Java数据结构和算法()——开篇

    万次阅读 多人点赞 2019-09-18 12:31:42
    这篇文章里面不讲技术,抽空讲讲技术和通俗之间有一种奇特的关系,还有驱动力学习的东西。看的是——《Java数据结构和算法》一书,作者Robert Lafore。 目录 1)数据结构算法有什么用? 2)技术与通俗 3)驱动力...

    这篇文章里面不讲技术,抽空讲讲技术和通俗之间有一种奇特的关系,还有驱动力学习的东西。看的是——《Java数据结构和算法》一书,作者Robert Lafore。

    目录

    1)数据结构算法有什么用?

    2)技术与通俗

    3)驱动力学习


    1)数据结构算法有什么用?

    当你用着java里面的容器类很爽的时候,你有没有想过,怎么ArrayList就像一个无限扩充的数组,也好像链表之类的。好用吗?好用,这就是数据结构的用处,只不过你在不知不觉中使用了。

     

    校招会发现大公司考的就是这类的题目,刚开始不会考你java的线程,容器,多态什么的特性,考的就是你的基础,你的这些基础扎实,学其他不是问题。

     

    正如作者所说,用于现实世界的存储,我们使用的工具和建模。每种数据结构有自己的优点和缺点,想想如果Google的数据用的是数组的存储,我们还能方便地查询到所需要的数据吗。

    而算法,在这么多的数据中如何做到最快的插入,查找,删除,也是在追求更快。

     

    第一章也把数据库,面向对象,软件工程(原来整个软件工程项目的生命周期包括分析、设计、验证编码、测试、生产和维护几个阶段)讲了个大概

     

     

     

    2)技术与通俗

    大学里面那本严蔚敏的数据结构不厚,内容丰富,但是复杂问题的讲解方面篇幅这样就少了,比较难理解,c也不是很擅长,但是基本的思路还是有的。

    简单的链表,数组,堆栈,队列,图,几个排序算法。

     

    后面看到知乎涛吴的回答,当时很震撼,这里引用一下他的回答:

     

    如果说 Java 是自动档轿车,C 就是手动档吉普。数据结构呢?是变速箱的工作原理。你完全可以不知道变速箱怎样工作,就把自动档的车子从 A 开到 B,而且未必就比懂得的人慢。写程序这件事,和开车一样,经验可以起到很大作用,但如果你不知道底层是怎么工作的,就永远只能开车,既不会修车,也不能造车。如果你对这两件事都不感兴趣也就罢了,数据结构懂得用就好。但若你此生在编程领域还有点更高的追求,数据结构是绕不开的课题。

    Java 替你做了太多事情,那么多动不动还支持范型的容器类,加上垃圾收集,会让你觉得编程很容易。但你有没有想过,那些容器类是怎么来的,以及它存在的意义是什么?最粗浅的,比如 ArrayList 这个类,你想过它的存在是多么大的福利吗——一个可以随机访问、自动增加容量的数组,这种东西 C 是没有的,要自己实现。但是,具体怎么实现呢?如果你对这种问题感兴趣,那数据结构是一定要看的。甚至,面向对象编程范式本身,就是个数据结构问题:怎么才能把数据和操作数据的方法封装到一起,来造出 class / prototype 这种东西?

    此外,很重要的一点是,数据结构也是通向各种实用算法的基石,所以学习数据结构都是提升内力的事情。

     

    反正我有醍醐灌顶的感觉,好比说,我有在编程上更厉害的追求,怎么能死在数据结构上的感觉。

     

    其实要将一门难懂的技术通俗地讲给不懂的人听,需要很大的功力,包括之前我写的那篇《C与指针》刚开始的时候,那个C语言有什么用回答也是他写的,我很佩服这样的人。

     

    所以当你能把一件东西清楚的讲解给别人听,类似前几篇文章提到的橡皮鸭调试法一样,你搞懂了,摸清楚了。跟一个技术人士用技术的语言讲解,非专业人士通俗语言讲解。

     

    当然了,前提需要积累。具体可以参见一下CSDN里面关于罗升阳的访谈——

    专访罗升阳:老罗的Android之旅

    当时吓了我一跳,之前以为和那个老罗同个级别的年龄,后面发现好年轻的小伙子,积累,慢慢积累。

     

     

    3)驱动力学习

    当你看到你自己玩过的马里奥可以自己写出来的时候是不是心动了?顿时学习的驱动力是不是有了——我要做一个这样的东西出来,然后开始学,直到自己动手完成。

     

    当时我在大学里就在推算,按照我这个学习速度,10年之后那也可以牛逼哄哄啊。有些人为什么技术没有提升,几年之后还是那样,因为驱动力的东西,有段时间我曾经停下来过,Java的差不多都学完了,干什么?

     

    因为从J2SE到EE的东西,大体的看完做过,然后就有一段迷茫期了,驱动力也没有了。后面意识到自己太肤浅了,还有其他一些热门的框架没用,最好的单例你写出来了吗,虚拟机你深入了吗,Java还有很多经典书籍没看呢?

    以学习新知识为驱动力也是可以的,期间不停地学到新知识是很有成就感和很兴奋的东西——原来是这样xx。

     

    还有一种——目标驱动,当时要做一个网络相关的东西——想到了爬虫,然后以做出这东西为目的,收集资料,看别人的代码,这样的驱动力学习也是可以的。工作的时候,如果目标只放在工作的项目,每次的项目都有新的东西在里面,那是可以学到东西的,一成不变的话,只能自己去发掘了。

    不然哪有那个学习到半夜的——专访雷果国:从1.5K到18K 一个程序员的5年成长之路。

     

    我要学Python,学了之后会发现,原来真的很牛逼,可以尝试用Python写个爬虫,GoAgent之类的。这便是进步。

     

     

    扯了那么多,就是不希望自己只懂的用Java做xx系统,只懂得用容器而永远不知道里面是怎样的。这些作为根基的懂了,其他也好学。

     

    说回数据结构这个,为什么很多学生听课听得想睡,xx链表,双向链表,我排序都有N种,学生的想法是这不知道有什么用,你讲链表给我,我把它实现一次,完事。

     

    但当你生活中的编程问题需要解决的时候,你会发现到处都是数据结构的使用,像基金买入买出不是队列吗,先进先出;像简单的一个班级学生的数据保存,用个数组不就可以解决了吗;再复杂的游戏路线问题,这不是图的问题吗;Java里面有Tree这字的,其实不也是用到树的原理吗?

     

    种种下来,你会发现,原来现实问题和语言里面的封装,都是和这些有联系的,每当你学会一种,就会恍然大悟,这不就是当年西湖河畔的夏雨荷,就是这种感觉。而学生在没有想过这些问题和没真正去使用这些语言的封装类之前,是不会考虑到上面所说的东西的。

     

    所以,一大群学生趴在那里睡觉玩手机是正常的。

     

    后面自己意识到之后,马上去买了《Java数据结构和算法》,补回之前没学和没弄懂的。

     

    不想学好基础的程序员不是好的程序员。

    展开全文
  • 数据结构:是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、(存储)物理结构和数据的运算三个部分。 为什么要学数据结构? 首先,因为数据结构作为...

    系列文章

    第一章:基础知识

    第二章:线性表

    第三章:栈和队列 

    第四章:字符串和数组

    第五章:树和二叉树

    第六章:图

    第七章:排序算法


    前言

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

    为什么要学数据结构?

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

    如何学习数据结构?

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

    展开全文
  • 数据结构基础概念篇

    万次阅读 多人点赞 2017-11-14 13:44:24
    数据结构一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。数据:所有能被输入到计算机中,且能...
  • java 中几常用数据结构

    万次阅读 多人点赞 2016-07-25 19:26:46
    java中有几常用的数据结构,主要分为Collection和map两个主要接口(接口只提供方法,并不提供实现),而程序中最终使用的数据结构是继承自这些接口的数据结构类。其主要的关系(继承关系)有: (----详细参见java...
  • 数据结构(1)—— 数据结构的三大结构

    万次阅读 多人点赞 2016-09-09 23:34:39
    1 数据结构的三大结构计算机程序设计 = 数据结构 + 算法 数据结构研究变量的管理方式,算法研究解决特定问题的方法。 数据结构分三个层次:逻辑结构(抽象层)、物理结构(结构层)、运算结构(实现层)。1.1 数据...
  • redis的五种数据结构原理分析

    万次阅读 多人点赞 2018-11-13 15:51:08
    redis中的五种数据结构分析 应用场景分析 总结   关于Redis redis是个开源的使用C语言编写的个kv存储系统,是个速度非常快的非关系远程内存数据库。它支持包括String、List、Set、Zset、hash五种数据...
  • 数据结构(C语言版本)

    万次阅读 多人点赞 2018-04-22 19:42:32
    数据结构(C语言版本) 第1章 绪论 1.常用的数据结构类型:集合、线性、树形、图状。 2.数据结构: - 逻辑结构:数据元素之间的关系 - 存储结构:数据结构在计算机中的表示。存储结构分为:顺序存储结构和...
  • (二)数组是一种数据类型

    千次阅读 2017-04-13 09:13:42
    值得指出的是,也是本篇着重提出的一点是,数组也是一种数据类型,它本身是一种引用类型,比如说String是一个基本类型,而String[]就是一种引用类型了。与String相似,String[]也一样可以定义变量(定义数组的一种...
  • DS之何谓数据结构

    千次阅读 2015-03-25 22:17:22
     数据结构是计算机存储、组织数据的方式,数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。这是百度解释的数据结构定义。暂且不说理解起来有没有难度,就说数据结构到底是什么东西?恐怕至今还没有一...
  • 数据结构一 (简介)

    千次阅读 多人点赞 2019-07-04 11:20:44
    转载请标明出处: ...本文出自:【openXu的博客】 1、什么是数据结构   数据结构主要学习用计算机实现数据组织和数据处理的方法;...  个好的程序无非是选择个合理的数据结构和好的算法,而好的算法...
  • 小猪的数据结构辅助教程——前言

    万次阅读 多人点赞 2019-05-31 13:56:34
    数据结构(C语言版)》吧,而讲数据结构课程的一般也是老教授吧,这也是为何上数据结构 课会昏昏欲睡的大部分原因,写这套教程的目标就是想让大家有目的性地去学数据结构! 不至于学完什么都不会,当然也会挑1,2个...
  • 数据结构

    千次阅读 多人点赞 2018-10-06 18:16:15
    数据结构是指相互之间存在一种或者多种特定关系的数据元素集合。通常情况下,精心选择的数据结构可以带来更高效的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。 数据结构是ADT(抽象数据类型)的...
  • 数据结构:线性结构和非线性结构的理解

    千次阅读 多人点赞 2019-03-02 22:54:09
    数据结构中线性结构指的是数据元素之间存在着“”的线性关系的数据结构。线性结构是个有序数据元素的集合。 线性结构特点: 线性结构有唯一的首元素(第个元素) 线性结构有唯一的尾元素(最后个元素) ...
  • 数据结构(全)

    万次阅读 多人点赞 2015-11-23 17:13:28
    由于具体实现的方法有顺序、链接、索引、散列等多种,所以,一种数据结构可表示成一种或多种存储结构。 数据元素的机内表示(映像方法): 用二进制位(bit)的位串表示数据元素。通常称这种位串为节点(node)。当...
  • 以下数据结构中,()是非线性数据结构A:树(二叉树) B:字符串 C:队列 D:栈 E:线性表 F:二维数组 G:多维数组数据的逻辑结构分为线性结构和非线性结构。 常用的线性结构有:线性表,栈,队列,双队列,...
  • redis底层有6种数据结构,分别是简单动态字符串(SDS),链表,字典,跳跃表,整数集合,压缩列表。每种数据类型都有着2种以上的数据结构实现,在不同状态下会进行数据结构的转换。现在来看看这6种数据结构是什么吧...
  • 学习任何一种技术都应该先清楚它的基本概念,这是学习任何知识的起点!本文是讲述数据结构的基本概念,适合对数据结构已经有一定基础的程序员,更是适合想要学习数据结构的code一族!让我们开始PHP数据结构的篇章吧...
1 2 3 4 5 ... 20
收藏数 2,378,329
精华内容 951,331
关键字:

类也是一种数据结构