要考试了…慌

第一章 数据结构基础

基本概念和术语

基本概念

数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并且被计算机程序处理的符号的总称。它是计算机操作的对象的总称,是信息的载体

数据元素(Data Element):是数据(集合)中的一个“个体”,是组成数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。它是数据结构中讨论的基本单位

数据项:是数据结构中讨论的最小单位(不可分割)。数据元素可以是数据项的集合(组成数据元素的各个项)

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

结构的定义

结构(Structure):数据元素之间的相互关系

如指数据在逻辑上的关系,称为逻辑结构
如指数据在物理上的关系,称为物理结构

数据结构的定义

数据结构(Data Structure)
1、描述性定义:是相互之间存在一种或多种特定关系的数据元素的集合

四、数据结构的分类
1、从逻辑结构角度分

  • 线性结构:线性表、栈、队列
  • 非线性结构:图、树

2、从物理结构角度分

  • 存储结构:物理结构
  • 四种不同的存储结构
    • 1、顺序存储结构:用数据元素在存储器中的相对位置来表述数据元素之间的逻辑关系
    • 2、链式存储结构:在每一个数据元素中添加一个存放地址的指针,用此指针来表示数据元素之间的逻辑关系
    • 3、索引存储方法:该方法通常在存储节点信息的同时,还建立附加的索引表
    • 4、散列存储方法:根据结点的关键字直接计算出该结点的存储地址

算法和算法分析

算法

1、算法:是对特定问题求解步骤的一种描述。算法是指令的有限序列,,其中每一条指令表示一个或多个操作
2、算法具有以下五个特性

  • 1) 有穷性
  • 2) 确定性
  • 3) 可行性
  • 4) 输入
  • 5) 输入

3、算法设计的要求
评价一个好的算法有以下几个标准:

  • 正确性
    • 所设计的程序没有语法错误
    • 所设计的程序对于几组输入数据能够得出满足要求的结果
    • 所设计的程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得到满足要求的结果
    • 程序对于一切合法的输入数据都能产生满足要求的结果
  • 可读性
  • 健壮性
  • 效率与存储量需求

算法的描述

1、算法、语言、程序的关系

  • 1) 算法:描述了数据对象的元素之间的关系(包括数据逻辑关系、存储关系描述)
  • 2) 描述算法的工具:自然语言、框图、类c语言
  • 3) 程序是算法在计算机中的实现(与所用计算机及所用语言有关)

2、设计实现算法的过程步骤

  • 1) 找出与求解有关的数据元素之间的关系(建立结构关系)
  • 2) 确定在某一数据对象上所施加运算
  • 3) 考虑数据元素的存储表示
  • 4) 选择描述算法的语言
  • 5) 设计实现求解的算法,并用程序语言加以描述

算法的分析

1、性能评价
对问题规模 n 与该算法在运行时所占的空间 S 与所耗费的时间 T 给出一个数量关系的评价

2、时间与空间数量关系计算

数量关系评价 体现在时间——算法编程后在机器中所耗费时间
数量关系评价 体现在空间——算法编程后在机器中所占存储量

1)关于算法执行时间
事先分析事后测试

  • 事先分析:求出该算法的一个时间界限函数
  • 事后测试:收集此算法的执行时间和实际占用空间的统计资料

语句频度指该语句在算法中重复执行的次数

2)算法的时间复杂度
算法的时间度量记作 T(n) = O(f(n))
O(f(n))称作算法的渐进时间复杂度,简称时间复杂度

以下六种计算算法时间的多项式是最常用的。其关系为:

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3)

3)算法的空间复杂度
空间复杂度:算法所需存储空间的度量,记作:S(n) = O(f(n))
其中 n 为问题的规模(或大小)

抽象数据类型的表示与定义

1、数据类型
数据类型是一个值的集合和定义在此集合上的一组操作的总称
2、抽象数据类型
在数据结构中我们常用到抽象数据类型。ADT是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作