数据结构 第一章

数据结构(严蔚敏版)

第一章

什么是数据结构

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

基础概念和术语

数据(Data)：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称，它是计算机程序加工的“原料”。

数据元素(Data Element)：数据的基本单元，在计算机程序中通常作为一个整体进行考虑和处理。

• 数据项(Data Item)：有时一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。

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

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

• 结构：数据元素相互之间的关系称为结构(Structure)

  • 基本结构：
    • 集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。
    • 线性结构：存在一个对一个的关系。
    • 树形结构：存在一个对多个的关系。
    • **图状结构或网状结构：**存在多个对多个的关系。

• 形式化定义：数据结构是一个二元组：$DataStructure = (D, S)$ 其中，D是数据元素的有限集，S是D上关系的有限集。

**物理结构：**数据结构在计算机中的表示(又称映像)称为数据的物理结构，又称存储结构。包括数据元素的表示和关系的表示，

• 位(bit)：在计算机中表示信息的最小单位是二进制数的一位，叫做位。
• 元素(Element)/结点(Node)：在计算机中，我们可以用由若干位组合形成的一个位串表示一个数据元素，通常称这个位串为元素或结点。
• 数据域(Data Field)：当数据元素由若干个数据项组成时，位串中对应于各个数据项的子位串称为数据域。
• 元素或结点可看成是数据元素在计算机中的映像。

顺序/非顺序：

• 顺序映像/非顺序映像
• 顺序存储结构与链式存储结构：
  • 顺序映像：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
  • 非顺序映像：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

**数据类型：**数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

• 按值分类：
  • 非结构的原子类型：原子类型的值是不可分解的。
  • 结构类型：结构类型的值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。

抽象数据类型(ADT)：一个数学模型以及定义在该模型上的一组操作。

• 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即无论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。
• 抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。
• 分类：
  • 原子类型：属原子类型的变量的值是不可分解的。
  • 结构类型：
    • 固定聚合类型：属该类型的变量，其值由确定数目的成分按某种结构组成。**
    • 可变聚合类型：构成可变类型“值”的成分的数目不确定。
• **形式化定义：**抽象数据类型可用三元组$(D, S, P)$表示。其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。

抽象数据类型的表示与实现

类C语言

算法与算法分析

算法

**算法：**算法是对特定问题求解步骤的一种描述，它是指令的有穷序列，其中每一条指令表示一个或多个操作。

• 重要特性：
  • 有穷性：算法必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。
  • 确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
  • 可行性：即算法中描述的操作是可以通过已经实现的基本运算执行有限次来实现的。
  • 输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。
  • 输出：一个算法有一个或多个的输出，这些输出是通输入有着某些特定关系的量。

算法设计的要求

• 正确性：
• 可读性
• 鲁棒性
• 效率与低存储量需求

算法效率的度量

时间度量：

• 事后统计的方法：
  • 缺陷：
    • 必须先运行依据算法编制的程序。
    • 所得时间的统计量依赖于计算机的硬件，软件等环境因素。
• 事前分析估算的方法
  • 取决因素：
    • 依据的算法选用何种策略。
    • 问题的规模。
    • 书写程序的语言。
    • 编译程序所产生的机器代码的质量。
    • 机器执行指令的速度。