数据结构学习(一)

数据结构绪论

数据结构基础概念

  • 数据(Data):描述客观事物的数值、字符,能被机器输入且处理的的各种符号的集合。

  • 数据元素(Data Element):组成数据的基本单位,是数据集合的个体。一条记录就是一个数据元素。

  • 数据对象(Data Object):性质相同的数据元素的集合,是数据的一个子集。

  • 数据结构(Data Structure):指相互之间存在一种或多种特定关系的数据元素集合。即数据元素之间的相互关系,即数据的组织形式。一句话总结:带有结构的数据元素的集合

  • 数据类型(Data Type):一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。即值域、定义域及运算集合。

  • 抽象数据类型(Abstract Data Type):定义了一个数据对象,数据对象中各元素之间的结构关系,以及一组处理数据的操作。包括定义和实现两方面,其中定义是独立于实现的。

    ADT 三要素:

    • 数据元素
    • 数据关系
    • 数据操作

数据结构内容

  • 逻辑结构:数据元素之间逻辑关系描述。

    四种基本数据逻辑结构表现为四种数据元素关系:

    • 集合结构:属于关系
    • 线性结构:一对一的线性关系
    • 树形结构:一对多的层次关系
    • 图形结构:多对多的任意关系
  • 存储结构(物理结构):逻辑结构在计算机中存储映像,是逻辑结构在计算机中的实现。包括数据元素的表示和关系的表示。

    数据元素之间关系在计算机中表示方法:

    • 顺序映像,一组连续单元,如数组。
    • 非顺序映像,一组任意存储单元,如链表。
  • 运算集合

算法与算法描述

  • 算法(algorithm)定义:规则的有限集合,是为解决特定问题而规定一系列操作。
  • 算法特性:
    • 有限性:有限步骤
    • 确定性:无二义性
    • 输入:有多个或0个输入
    • 输出:至少有一个输出
    • 可行性:原则上能精确进行,操作可通过已实现的基本运算执行有限次而完成
  • 算法设计要求:
    • 正确性
    • 可读性
    • 健壮性(鲁棒性):对非法输入的抵抗能力
    • 高效率与低存储量
  • 算法描述:自然语言、框图、高级语言

算法性能评价

  • 性能评价:问题规模 N 的函数

  • 数量关系评价:时间和空间

    • 算法执行时间:本质是语句执行次数的比较

    • 语句频度:该语句在一个算法中的重复执行的次数

    • 算法的时间复杂度:

      T(n)=O(f(n))

      例如:

    for (int i = 0; i 

    这样的一段代码其时间复杂度为

    o(n^2)

    再例如,下方有一个算法的执行时间

    f(n)=2n^3+2n^2+n

    其时间复杂度为

    o(n^3)

    但这样一个算法只是理论上可行,但实际上不可行,因为其执行次数上升太快,程序无法实现。

    • 最坏时间复杂度:算法在最坏情况下基本操作执行时间的上界。

    例如,冒泡排序算法最坏时间复杂度为

    o(n^2)

    而其最好时间复杂度为

    o(n)
    • 算法空间复杂度:以存储单元个数刻画随问题规模增加的函数 f(n),是考虑程序运行时占用内存的大小,记作
      S(n)=O(f(n))

发表评论