数据结构-绪论

数据结构

发布日期: 2025-10-11

文章字数: 3.2k

阅读时长: 12 分

1. 基本概念和术语

数据 (Data)

定义 | 数据 (Data): 数据是信息的载体, 是描述客观事物属性的数, 字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合.

对于计算机来说, 就是二进制的 0 和 1

数值型数据: 整数, 定点数, 浮点数
非数值型数据: 文字数据

数据元素 (Data Element)

定义 | 数据元素 (Data Element): 是数据的基本单位, 通常作为一个整体进行考虑和处理 (最小单位是 bit).

数据项 (Data Item)

定义 | 数据项 (Data Item): 一个数据元素可由若干数据项组成, 数据项是构成数据元素的不可分割的最小单位.

我们要根据实际的业务需求来确定什么是数据元素, 什么是数据项
数据元素又称为元素, 结点, 记录 (record)

数据结构 (Data Structure)

结构: 各个元素之间的关系 (relationships among elements)

数据结构 (Data Structure):

形式定义: 某一数据对象的所有数据成员之间的关系. 记为: $\text{Data\_Structure} = \{ D, S \}$ 其中, D 是某一数据对象, S 是该对象中所有数据成员之间的关系的有限集合.

例: 复数的数据结构定义 (complex number)

数据对象 (Data Object)

数据对象 (Data Object): 具有相同性质的数据元素的集合, 是数据的一个子集

整数数据对象 $N = \{0,\pm1, \pm2, \dots\}$
字符数据对象 $C = \{'A','B','C',\cdots, 'F'\}$
俱乐部会员表数据对象 (club member table)

数据处理 (Data Processing)

数据处理 (Data Processing): 将数据通过人力或机器, 将收集到的数据加以系统的处理, 归纳出有价值的信息

排序, 归并, 编辑, 计算, 查找, 查询, 分类, 变换等

数据结构 (Data Structure) 的三要素 (Three Elements)

(1) 逻辑结构 (Logical Structure) — 数据结构之间的逻辑关系是什么

从逻辑关系上描述数据, 与数据的存储无关;
从具体问题抽象出来的数据模型 (data model)
与数据元素本身的形式, 内容无关

数据的逻辑结构分类

线性结构: 线性表, 栈 (stack), 队列 (queue), 数组 (array), 串 (string)
非线性结构: 树 (tree), 图 (graph 或 network), 广义表, 多维数组

四个基本结构:

集合 (Set): 各个元素同属一个集合, 别无其他关系

线性结构 (Linear): 数据元素之间是一对一的关系. 除了第一个元素, 所有元素都有唯一前驱; 除了最后一个元素, 所有元素都有唯一后继

树形结构 (Tree): 数据元素之间是一对多的关系

网状结构 (Graph): 数据元素之间是多对多的关系

(2) 物理结构 (Physical Structure) — 如何用计算机表示数据元素的逻辑关系

顺序存储 (Sequential Storage): 把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中, 元素之间的关系由存储单元的邻接关系来体现

链式存储 (Linked Storage): 逻辑上相邻的元素在物理位置上可以不相邻, 借助指示元素存储地址的指针来表示元素之间的逻辑关系

索引存储 (Indexed Storage): 在存储元素信息的同时, 还建立附加的索引表. 索引表中的每项称为索引项, 索引项的一般形式是 (关键字, 地址)

散列存储 (Hash Storage): 根据元素的关键字直接计算出该元素的存储地址, 又称哈希 (Hash) 存储

若采用顺序存储, 则各个数据元素在物理上必须是连续的; 若采用非顺序存储, 则各个元素在物理上可以是离散的
数据的存储结构会影响存储空间分配的方便程度
数据的存储结构会影响对数据运算的速度

存储方式	逻辑相邻是否物理相邻	额外信息	优点	缺点
顺序存储 (Sequential)	是	无	随机访问快	插入/删除慢
链式存储 (Linked)	否	指针/引用	插入/删除快	额外指针开销
索引存储 (Indexed)	否	索引表	查找加速	维护索引成本
散列存储 (Hash)	否	哈希函数	访问接近 O(1)	冲突与退化

(3) 数据的运算 (Operations) — 施加在数据上的运算包括运算的定义和实现

运算的定义是针对逻辑结构的, 运算的实现是针对存储结构的, 指出运算的具体操作步骤

抽象数据类型 (Abstract Data Type, ADT)

数据类型 (Data Type): 一个值的集合和定义在这个值集上的一组操作的总称

C 语言中的基本数据类型: int (整型), char (字符型), float (浮点型), double (双精度型), void (无值)

抽象数据类型 (Abstract Data Type, ADT): 是指一个数学模型以及定义在此数学模型上的一组操作

逻辑特性, 与在计算机内的表示与实现无关
抽象数据类型 $=$ 数据结构 $+$ 定义在此数据结构上的一组操作

矩阵的抽象数据类型: 矩阵 + (求转置, 加, 乘, 求逆, 求特征值)

//complex.h
//隐藏数据表示，不提供具体的说明
typedef struct complex *Complex; 
Complex COMPLEXinit(float , float);
float Re(Complex);
float Im(Complex);
Complex COMPLEXmult(Complex, Complex);
Complex COMPLEXadd(Complex, Complex);
void showComplex(Complex );

抽象数据类型的描述:

抽象数据类型可用(D,P,S)三元组表示

D是数据对象
S是D上的关系集
P是对D的基本操作集

ADT 抽象数据类型名 {
  数据对象：〈数据对象的定义〉
  数据关系：〈数据关系的定义〉
  基本操作：〈基本操作的定义〉
} ADT 抽象数据类型名

数据对象,数据关系用伪码描述;基本操作定义格式为:

基本操作名（参数表）
初始条件：〈初始条件描述〉
操作结果：〈操作结果描述〉

基本操作有两种参数:赋值参数只为操作提供输入值;引用参数以&打头,除可提供输入值外,还将返回操作结果
“初始条件”描述了操作执行之前数据结构和参数应满足的条件,若不满足,则操作失败,并返回相应出错信息
“操作结果”说明了操作正常完成之后,数据
结构的变化状况和应返回的结果.

抽象数据类型的表示和实现:
抽象数据类型可以通过固有数据类型(高级编程语言中已实现的数据类型)来实现:

抽象数据类型	数据对象	基本操作
类 class	数据成员	成员函数(方法)

在C++中,类的成分(数据成员和成员函数)可以有三种访问级别:

private 私有成分(只允许类的成员函数进行访问)
protected 保护成分(只允许类的成员函数及其子孙类进行访问)
public 公有成分(允许类的成员函数,类的实例及其子孙类,子孙类的实例进行访问)

2. 程序的产生

五个阶段:

需求(输入,输出)
设计(编写算法)
分析(选择最佳算法)
细化与编码(编写程序)
验证(程序验证,测试,调试)

算法分析

算法定义

为了解决某类问题而规定的一个有限长的操作序列

特性

有穷性:算法在执行有穷步后能结束
确定性:每步定义都是确切,无歧义
可行性:每一条运算应足够基本
输入:有0个或多个输入
输出:有一个或多个输出

算法设计例子:选择排序 (Selection Sort)

问题:递增排序
解决方案:逐个选择最小数据
代码如下:

void SelectSort(int a[], int n)
{
  for (int i = 0; i < n - 1; i++)
  {
    int k = i;
    // 从a[i]查到a[n-1], 找最小整数, 在a[k]
    for (int j = i + 1; j < n; j++)
    {
      if (a[i] < a[j])
      {
        k = j;
        a[i] ^= a[j];
        a[j] ^= a[i];
        a[i] ^= a[j];// 邪修,用来交换数值
      }
    }
  }
}

性能分析与度量

评价标准

算法的评价标准:

正确性:包括不含语法错误,对几组数据运行正确,对典型,苛刻的数据运行正确,对所有数据运行正确
可读性:
效率:高效,低存储需要.(算法执行时间短,同时所占用的存储空间小)
健壮性:当输入非法数据时,算法也能作出适当反应,而不会出现莫名其妙的输出结果

时间复杂度 (Time Complexity)

后期测试(实测)

算法的后期测试:
在算法中的某些部位插装时间函数time(),测定算法完成某一功能所花费时间

double start, stop;
time (&start);
int k = seqsearch (a, n, x);
time (&stop);
double runTime = stop - start;
printf (" %d%d\n " , n, runTime);

事前估计(分析)

算法的事前估计:

运行时间 = 算法中每条语句执行时间之和
每条语句执行时间 = 该语句的执行次数(频度)* 语句执行一次所需时间
语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量,很难确定
设每条语句执行一次所需时间为单位时间,则一个算法的运行时间就是该算法中所有语句的频度之和

定义与表示法

时间复杂度:算法中语句重复执行次数的数量级是时间复杂度.
表示方法: $T(n) = O(f(n))$

$T(n)$ 称做渐进时间复杂度,简称时间复杂度
$f(n)$ 表示基本操作重复执行的次数,是 $n$ 的某个函数,随问题规模 $n$ 的增大,算法执行时间的增长率和 $f(n)$ 的增长率属于同一数量级
$O$ 表示 $f(n)$ 和 $T(n)$ 只相差一个常数倍

示例 1:常数时间打印(O(1))

下面看两个代码.
代码一:

void print(int a[]) 
{
  int i = 0;
  cout << a[i];
  i++;
  cout << a[i];
}

结论:时间复杂度为 $O(1)$

示例 2:线性时间打印(O(n))

代码二:

void print (int a[], int n) 
{
  int i = 0;
  for(i = 0;i < n; i++)
    cout << a[i];
}

结论:时间复杂度为 $O(n)$

示例 3:顺序查找 (Sequential Search, 平均复杂度 O(n))

再来看一个代码:

int seqsearch(int a[], int n, int x)
{
  // 在a[0],...,a[n - 1]中搜索x
  int i = 0;
  while(i < n && a[i] != x)
    i++;
  if(i == n)
    return -1;
  return i;
}