本文引自【数据结构(C语言版)严蔚敏 吴伟民】
文章目录
- 1.1 什么是数据结构
- 1.2 基本概念和术语
- 1.3 抽象数据类型的表示与实现
- 1.4 算法和算法分析
- 1.4.1 算法
- 1.4.2算法设计的要求
- 1.4.3 算法设计的度量
- 1.4.4 算法设计的存储空间需求
1.1 什么是数据结构
一般来说,用计算机解决一个具体问题时,大致需要经过下列几个步骤:首先要从具体问题抽象出一个适当的数学模型,然后设计一个解此数学模型的算法,最后编出程序进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题,从中提取操作的对象,并找出这些操作对象之间含有的关系,然后用数学的语言加以描述。例如,求解梁架结构中应力的数学模型为线性方程组;预报人口增长情况的数学模型为微分方程。然而更多的非数值计算问题无法用数学方程加以描述。
-
例1图书馆的书目检索系统自动化问题
-
例2 计算机和人对弈问题
-
例3 多叉路口交通灯的管理问题
综上3个例子可见,描述这类非数值计算问题的数学模型不再是数学方程,而是诸如表、树和图之类的数据结构。因此,简单说来,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
图1.4 数据结构的地位图
1.2 基本概念和术语
数据结构是计算机科学中研究数据组织、存储和管理的学科，它涉及到各种数据的表示、操作和处理。下面是一些基本概念和术语的定义，以及相应的举例解释：
-
数据结构（Data Structure）：
定义：数据结构是指数据元素之间存在的一种或多种特定关系的集合。
举例：数组、链表、栈、队列等。 -
数据元素（Data Element）：
定义：数据结构中的基本单位，通常是具有意义的单个数据项。
举例：在一个整数数组中，每个整数就是一个数据元素。 -
数据项（Data Item）：
定义：数据元素中不可分割的最小单位，通常与实际问题中的某个属性或特征相关联。
举例：在一个学生信息记录中，姓名、年龄、性别等就是数据项。 -
数据类型（Data Type）：
定义：数据元素的集合以及定义在该集合上的一组操作的总称。
举例：整数、浮点数、字符、字符串等都是数据类型。 -
逻辑结构（Logical Structure）：
定义：数据元素之间的逻辑关系，不考虑其在计算机内部的存储表示和实现方式。
举例：线性结构（如数组、链表）、非线性结构（如树、图）等。 -
存储结构（Storage Structure）：
定义：数据在计算机内部的存储表示方式，通常包括数据元素的存储位置和关系。
举例：数组可以使用连续的内存空间来存储，而链表则是通过指针将各个节点连接起来的。 -
抽象数据类型（Abstract Data Type，ADT）：
定义：数据类型的数学模型及其定义在该模型上的一组操作。
举例：栈、队列、树等都可以通过ADT来描述其操作和性质，而具体的实现则可以采用不同的数据结构。
ADT 抽象数据类型名 {数据对象: <数据对象的定义>,数据关系: <数据关系的定义>,基本操作: <基本操作的定义>
}
1.3 抽象数据类型的表示与实现
- 预定义常量类型
// 函数结果状态代码
#define TRUE 1 // 逻辑真
#define FALSE 0 // 逻辑假#define OK 1 // 操作成功
#define ERROR 0 // 操作失败
#define INFEASIBLE -1 // 不可行操作
#define OVERFLOW -2 // 内存溢出// Status 是函数的返回类型，其值是函数结果状态代码
typedef int Status;- 数据结构的表示(存储结构)用类型定义(typedef)描述。数据元素类型约定为ElemType,由用户在使用该数据类型时自行定义。
- 基本操作的算法都用以下形式的函数描述:
函数类型 函数名(函数参数表)(// 算法说明语句序列
} // 函数名//举例：
#define OK 1
#define ERROR 0
typedef int Status;
// 初始化三元组
Status InitTriplet(int** T, int v1, int v2, int v3) {// 算法说明: 分配内存并初始化三元组，使其包含三个元素，分别为v1, v2, v3*T = (int*)malloc(3 * sizeof(int));if (*T == NULL) {return ERROR; // 内存分配失败}(*T)[0] = v1;(*T)[1] = v2;(*T)[2] = v3;return OK;
} // InitTriplet
- 赋值语句
1. 简单赋值
变量名 = 表达式;
示例: int a = 5;2. 串联赋值
变量名1 = 变量名2 = … = 变量名k = 表达式;
示例:
int a, b, c;
a = b = c = 10;3. 成组赋值
(变量名1, 变量名2, ..., 变量名k) = (表达式1, 表达式2, ..., 表达式k);
示例:
int a, b, c;
(a, b, c) = (1, 2, 3); // C语言不支持此语法，这是一个假设的示例4. 结构赋值
结构名 = 结构名;
结构名 = (值1, ..., 值k);
示例:
struct Point {<
