0%

绪论

绪论

1.数据结构的定义

  • 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

2.数据

  • 对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称 。
  • 例如:数字、字符、声音、图形、图像等信息 。

3.数据对象

  • 性质相同的数据元素的集合,是数据的一个子集

4.数据元素(结点或记录)是数据的基本单位,数据项(域)是数据的最小单位

5.逻辑结构

  • 描述数据元素之间的逻辑关系
  • 与数据的存储无关,独立于计算机
  • 是从具体问题抽象出来的数学模型
  • 可分为 集合,线性结构,树形结构,图形结构。

6.物理结构(存储结构)

  • 数据元素及其关系在计算机存储器中的存储方式
  • 数据结构在计算机中的表示
  • 可分为4大类:顺序、链式、索引、散列

7.算法原地工作是指辅助空间不随着数据规模的增大儿增大,不是说不需要辅助空间

8.栈和队列属于逻辑结构而非存储结构,他们的实现才是属于存储结构

9.程序需要算法和数据结构结合才能实现,仅仅把算法用某种计算机语言来描述不能称之为程序

10.抽象数据类型的表示

  • 数据对象
  • 数据关系
  • 基本操作

11.算法的定义

  • 对特定问题求解步骤的一种描述,是指令的有限序列

12.算法的特性

  • 输入输出
  • 有穷性
  • 确定性
  • 可行性

13.评价算法优劣的基本标准

  • 正确性
    • 程序中不含语法错误;
    • 程序对于几组输入数据能够得出满足要求的结果;
    • 程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果;
    • 程序对于一切合法的输入数据都能得出满足要求的结果。
      (通常以第三层意义上的正确性作为衡量一个算法是否合格的标准)
  • 可读性
    • 算法主要是为了人的阅读和交流,其次才是为计算机执行,因此算法应该易于人的理解;
    • 另一方面,晦涩难读的算法易于隐藏较多错误而难以调试。
  • 健壮性
    • 指当输入数据 非法时,算法恰当的做出反应或进行相应处理,而不是产生莫名其妙的输出结果。
    • 处理出错的方法,不应是中断程序的执行,而应是返回一个表示错误或错误性质的值,以便在更高的抽象层次上进行处理
  • 高效性
    • 包括时间和空间两个方面
    • 时间高效指算法设计合理,执行效率高,可以用时间复杂度来度量;
    • 空间高效是指算法占用存储容量合理,可以用空间复杂度来度量。
    • 两者都与问题的规模有关。

14算法的时间复杂度取决于问题的规模和待处理数据的状态;算法的时间复杂度是由嵌套最深层语句的频度决定的。