第一章 概论

• 引言
• 基本概念和术语
  • 数据、数据元素和数据项
  • 数据的逻辑结构
  • 数据的存储结构
  • 运算
• 算法及描述
• 算法分析
  • 时间复杂度
  • 空间复杂度
• 本书组织结构
• 小结

1.1 引言

1、数据结构的概念

数据结构（data structure）是指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方式，以及定义在该组数据上的一组操作。

计算机解决问题的步骤：

1. 建立数学模型
2. 设计算法
3. 编程实现算法

数据结构主要研究：

1. 数据（计算机加工对象）的逻辑结构
2. 实现各种基本操作的算法

算法 + 数据结构 = 程序

数据结构主要研究

1.2 基本概念和术语

1.2.1 数据、数据元素和数据项

基本术语

• 数据（data）所有被计算机存储、处理的对象
• 数据元素（data element）数据的基本单元，是运算的基本单元。常常又称为元素
• 数据项（data item）数据元素常常还可以分为若干个数据项，数据的不可分割的最小标识单元

数据（对象）、数据元素和数据项构成了数据组织的三个层次，如下图所示：

在数据库中 数据项 又称为字段或域。它是数据的不可分割的最小标识单位。

实际问题中的数据称为：原始数据

数据结构：相互之间存在一种或者多种特定关系的数据元素的集合

数据结构

• 数据的逻辑结构
• 数据的存储结构
• 数据的基本运算

从宏观上看，数据、数据元素和数据项 实际上反映了数据组织的三个层次，数据可由若干数据元素组成，而数据元素又可由若干数据项组成。

1.2.2、逻辑结构（logical structure）

指数据元素之间的结构关系。与数据元素本身的形式、内容、相对位置，个数无关

逻辑结构的种类分为四种

1. 集合：任意两个结点之间都没有邻接关系，组织形式松散 0:0
2. 线性结构：结点按逻辑关系依次排列形成一条“锁链” 1:1
3. 树形结构：具有“分支、层次”特性，上层的结点可以与下层多个结点相邻接，但下层结点只能和上层的一个结点相邻接 1：N
4. 图结构：任何两个结点都可以邻接。最复杂 N：N

特别注意：

1. 逻辑结构与数据元素本身形式、内容无关
2. 逻辑结构与数据元素的相对位置无关
3. 逻辑结构与所含结点个数无关

1.2.3、存储结构（物理结构：physical structure）

指数据结构在机内的表示，数据的逻辑机构在机内的实现。

数据在计算机内的表现形式称为：数据的存储结构

存储结构的主要部分

• 存储结点（每个存储结点存放一个数据元素）
• 数据元素之间关联方式的表示
• 数据的存储包含：数据元素的的存储及其逻辑关系的存储
• 存储结构可分为：顺序存储结构、链式存储结构、索引存储方式和散列存储方式等。
• 顺序存储结构与链式存储结构最基本，应该重点掌握。如何操作，各有什么特点、什么时候选择顺序结构、什么时候选择链式结构

1. 顺序存储方式
   1. 指所有存储结点存放在一个连续的存储区里。利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。
   2. 顺序的方法：将元素存储到一片连续的存储区
   3. 特点
      1. 预先分配好长度，需要预估存储数据需要的存储量
      2. 插入和删除需要移动其他元素
      3. 存取快捷，是随机存取结构
2. 链式存储方式
   1. 指每个存储结点除了含有一个数据元素外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点，用指针表示数据元素之间的逻辑关系
   2. 这种存储结构是给结点附加一个指针字段，指出其后继结点的位置，即存放结点的存储单元分为两部分：数据项 + 指针项
   3. 特点
      1. 动态分配，不需要预先确定内存分配
      2. 插入和删除不需要异动其他元素
      3. 非随机存取结构
3. 索引存储方式
   1. 借助索引表中的索引指示各存储结点的存储位置
4. 散列存储方式
   1. 用散列函数指示各结点的存储位置

1.2.4、运算

运算是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。

线性表、栈和队列 中的元素具有相同的逻辑结构（即线性结构），但有不同的运算集，它们是不同的数据结构。

1.3、算法及其描述

算法规定了求解给定类型问题所需的 所有“处理步骤” 以及 “执行顺序”，使 给定类型问题能在 有限时间 内被机械的求解。

算法必须使用某种语言描述

• 程序
• 介于自然语言和程序设计语言的伪代码
• 非形式算法（自然语言）
• 框图（N-S图）

本教材使用类C语言描述算法

1.4、算法分析

运算的实现是指该运算的算法。
一个算法规定了求解给定问题所需的处理步骤及其执行顺序。使得给定问题能在有限时间内被求解。

评价算法好坏的因素包括以下几个方面：

• 正确性
  • 能正确地实现预定的功能，满足具体问题的需要
• 易读性
  • 易于阅读、理解和交流，便于调试、修改和扩充
• 健壮性
  • 即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果
• 时空性
  • 一个算法的时空性是指该算法的时间性能（或时间效率）和空间性能（或空间效率），前者是算法包含的计算量，后者是算法需要的存储量。

1.4.1、时间复杂度

解决同一问题的算法可以有很多种。我们希望从中选出最优的算法，效率高或者存储空间小。为此，需要对算法进行评估，分析。

通常考虑两个度量

• 时间复杂度
  • 算法运行时需要的总步数，通常是问题规模的函数。
• 空间复杂度
  • 算法执行时所占用的存储空间，通常是问题规模的函数。

如何确定算法的计算量

• 合理地选择一种或几种操作作为“标准操作”，无特殊说明，默认以赋值语句作为标准操作
• 确定每个算法共执行多少次标准操作，并将此次数规定为该算法的计算量
• 以算法在所有输入下的计算量的最大值作为算法的计算量，称为算法的最坏情况时间复杂度
• 以算法在所有输入下的计算量的加权平均值作为算法的计算量，称为算法的平均情况时间复杂度
• 最坏情况时间复杂度和平均情况时间复杂度通称为时间复杂度

常见的时间复杂度按数量级递增排列依次为：

1. 常数O(1)
2. 对数阶O($log_2n$)
3. 线性阶O(n)
4. 线性对数阶O($nlog_2n$)
5. 平方阶O($n^2$)
6. 多项式阶O($n^c$)
7. 指数阶O($C^n$)

我们将时间复杂度记为输入数据规模n的函数，若求解问题需要执行$n^2$次操作，则记作O($n^2$)

1.4.2、空间复杂度