第一章 绪论

第一章 绪论

---

概要

1.研究内容

2.数据结构定义

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

基本概念和术语

1.常用名词

• 数据（Data）
  • 是对客观事物的符号表示，能输入到计算机中的符号的总称。
• 数据元素 （data element）
  • 是数据的基本单位，通常作为一个整体而考虑和处理。
• 数据项 （data item）
  • 一个数据元素可由若干个数据项组成，数据项是数据不可分割的最小单位。
    

and：还可以以结构体为例解释

struct date
{
    char name[50];
    int id;
    int age;
}q[N];
//q[i]可以理解为数据元素
//q[i].id q[i].name q[i].age可以理解为数据项
1
2
3
4
5
6
7
8

• 数据对象 （data object）
  • 性质相同的数据元素的集合，是数据的一个子集。
• 结构（Structure）
  • 是组成整体的各部分的关系和关联。
• 数据结构（ Data Structure）
  • 数据结构是相互之间存在一种或多种特定关系的数据元素的集合，也可称其为逻辑结构。

2.四种基本数据结构(逻辑结构)

• 集合：数据元素之间只有同属一个集合的关系
• 线性：数据元素之间存在一对一的关系
• 树：数据元素之间存在一对多的关系
• 图：数据元素之间存在多对多的关系
  

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

• 顺序映像
  • 用元素的相对位置来表示数据元素之间的逻辑关系。
• 非顺序映像
  • 用元素存储地址的指针表示数据元素之间的逻辑关系。

4.数据类型

是一组性质相同的值的集合以及定义于这个值 集合上的一组操作的总称。

• 作用
  • 约束变量的内存空间
  • 约束变量或常量的取值范围
  • 约束变量或常量的操作。

算法和算法分析

1.算法的基本概念

• 算法的五个特性
  • 有穷性、确定性、可行性、0个或多个输入、1个或多个输出
• 算法的设计要求
  • 正确性、可读性、健壮性、高效率、低存储

2.算法效率的度量

算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，记作：T(n) = O(f(n))

• 基本算法：最深的大括号所包含的语句

  • if后括号里比较语句的是基本操作
  • for后大括号里的是基本操作

• f(n)的求法：一般用频度表达式中增长最快的项表示，并将其常数去掉 。

• 几种情况

  • 常量阶：基本表达式是常数 O(1)

• 常见的时间复杂度

  • 常数阶 O(1)，对数阶 O(log n)，线性阶 O(n)，线性对数阶 O(nlog n)，平方阶 O(n2)，立方阶 O(n3)，…， k 次方阶O(nk)，指数阶 O(2n)，阶乘阶 O(n!)。

  • 常见的算法的时间 复杂度之间的关系为：

    O(1)

算法的存储空间需求

• 空间复杂度：

  • 算法所需存储空间的度量，
  • 记作：S(n)=O( f(n) ) 其中 n 为问题的规模。

• 空间计算

  • 算法本身的存储空间
  • 输入数据的存储空间
  • 算法在运行过程中临时占用的存储空间(包括函数形参)
  • 记作：S(n)=O( f(n) ) 其中 n 为问题的规模。

• 空间计算

  • 算法本身的存储空间
  • 输入数据的存储空间
  • 算法在运行过程中临时占用的存储空间(包括函数形参)