数据结构的基本概念

数据结构主要包括 基本术语、逻辑结构和物理结构

数据结构概论 - 图1

基本概念

1、数据(Data) ：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。

2、数据元素(Data Element) ：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。 一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。

3、数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合 C={‘A’,’ B’,’C,…} 。

4、数据结构(Data Structure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。

5、数据类型(Data Type)：指的是一个值的集合和定义在该值集上的一组操作的总称。数据类型是和数据结构密切相关的一个概念。 在 C 语言中数据类型有：基本类型和构造类型。 数据结构不同于数据类型， 也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。

6、抽象数据类型(Abstract Data Type ，简称 ADT)：是指一个数学模型以及定义在该模型上的一组操作。 ADT 的定义仅是一组逻辑特性描述， 与其在计算机内的表示和实现无关。因此，不论 ADT 的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。 ADT 的形式化定义是三元组：ADT=(D，S，P) 其中：D 是数据对象，S 是 D 上的关系集，P 是对 D 的基本操作集。

数据结构概论 - 图2

逻辑结构

数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的 “关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。

元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型：

① 集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。

② 线性结构：结构中的数据元素之间存在一对一的关系。

③ 树型结构：结构中的数据元素之间存在一对多的关系。

④ 图状结构或网状结构：结构中的数据元素之间存在多对多的关系。

数据结构概论 - 图3

逻辑结构（数据结构）的分类

  1. 线性结构：线性表、栈、队列、串
  2. 非线性结构：树、图、多维数组、广义表

数据结构概论 - 图4

说明：

  • 逻辑结构与数据元素本身的形式、内容无关
  • 逻辑结构与数据元素的相对位置无关
  • 逻辑结构与所含结点个数无关
  • 逻辑结构与计算机无关

物理结构

物理结构是数据结构在计算机内存中的存储，包括数据元素的存储和元素之间的关系的表示。

简单的说，数据结构在计算机中的存储形式叫物理结构或者存储结构

数据结构概论 - 图5

根据逻辑结构在物理结构中表达形式的不同，可以把物理结构分为四大类：

  1. 顺序结构
    数据元素在内存中按序连续存储, 用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)
    数据结构概论 - 图6

    1. 占用一大片连续内存空间

    2. 不需要额外空间存储逻辑关系，总空间需求最少

    3. 通过物理位置关系反映逻辑关系通过

    4. 可顺序访问，支持随机访问

    5. 通过数组实现

    6. 数据元素的插入和删除操作通过移动元素完成

  2. 链式结构
    在每一个数据元素中增加存放另一个元素地址的指针，用该指针来表示数据元素之间的逻辑关系。
    数据结构概论 - 图7

    1. 不要求占用连续内存空间

    2. 不仅要存储数据，还要存储数据之间的关系，故总空间需求较大

    3. 通过指针反映逻辑关系

    4. 逻辑连续，物理可不连续

    5. 只可顺序访问，不支持随机访问

    6. 存在标记：头指针

    7. 数据元素的插入和删除操作通过修改指针完成：定位插入点/删除点的直接前驱/后继位置。

  3. 索引结构
    除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。
    数据结构概论 - 图8

    1. 不要求占用连续内存空间

    2. 不仅要存储数据，还要存储关系，故总空间需求较大

    3. 通过索引表记录逻辑关系

    4. 逻辑连续，物理可不连续

    5. 可顺序访问，支持随机访问

    6. 数据元素的插入和删除操作通过修改索引表中相关数据元素的存储地址进行

    7. 需要额外存储空间：通过索引表存储逻辑关系

    8. 需要额外操作时间：对索引表进行维护

  4. 散列结构
    散列存储方法:散列存储，又称hash存储，是一种试图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。
    数据结构概论 - 图9

    1. 物理位置通过哈希函数计算得到

    2. 逻辑连续，物理可不连续

    3. 可顺序访问，由于存在冲突，仅支持部分随机访问

    4. 重点：散列函数和解决冲突方法

数据操作

数据结构的主要运算包括：

⑴ 建立(Create)一个数据结构；

⑵ 消除(Destroy)一个数据结构；

⑶ 从一个数据结构中删除(Delete)一个数据元素；

⑷ 把一个数据元素插入(Insert)到一个数据结构中；

⑸ 对一个数据结构进行访问(Access)；

⑹ 对一个数据结构(中的数据元素)进行修改(Modify)；

⑺ 对一个数据结构进行排序(Sort)；

⑻ 对一个数据结构进行查找(Search)。

v

算法

算法的概念和评价

什么是算法

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

需要注意的是算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。

数据结构概论 - 图10

描述算法的主要方法

  1. 伪语言
  2. 自然语言
  3. 程序设计语言（或类程序设计语言）
  4. 流程图（包括传统流程图和 N-S 结构图）

算法的特性

① 有穷性： 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

② 确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。

③ 可行性： 一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。

④ 输入： 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。

⑤ 输出： 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。

算法评价

① 正确性(Correctness )： 算法应满足具体问题的需求。

② 可读性(Readability)： 算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。

③ 健壮性(Robustness)： 算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。

④ 通用性(Generality)： 算法应具有一般性 ，即算法的处理结果对于一般的数据集合都成立。

⑤ 效率与存储量需求： 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。

复杂度分析

时间复杂度

时间复杂度的定义

算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。其方法通常有两种：

  1. 事后统计：计算机内部进行执行时间和实际占用空间的统计。
    问题：必须先运行依据算法编制的程序；依赖软硬件环境，容易掩盖算法本身的优劣；没有实际价值。

  2. 事前分析：求出该算法的一个时间界限函数。与此相关的因素有：

    • 依据算法选用何种策略；
    • 程序设计的语言；
    • 编译程序所产生的机器代码的质量；
    • 机器执行指令的速度；
    • 问题的规模；
    • 数据的初始状态。

撇开软硬件等有关部门因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模（通常用 n 表示），或者说，它是问题规模的函数。即：算法中基本操作重复执行的次数是问题规模 n 的某个函数，其时间量度记作 T(n)=O(f(n))，称作算法的渐近时间复杂度，简称时间复杂度。一般地，常用最深层循环内的语句中的原操作的执行频度(重复执行的次数)来表示。

“O”的定义： 若 f(n)是正整数 n 的一个函数，则 O(f(n))表示 M≥0 ，使得当 n ≥ n0时，| f(n) | ≤ M | f(n0) | 。

复杂度的阶

表示时间复杂度的阶有：

O(1) ：常量时间阶 O (n)：线性时间阶 O(㏒ n) ：对数时间阶 O(n ㏒ n) ：线性对数时间阶 O(n^k)：k≥2，k次方时间阶

以下六种计算算法时间的多项式是最常用的。其关系为： O(1) < O(㏒ n ) < O(n) < O(n ㏒ n) < O(n^2) < O(n^3)

指数时间的关系为：O(2^n) < O(n!) < O(n^n)

常量时间阶
  1. {++x;s=0;}

将x自增看成是基本操作，则语句频度为１，时间复杂度为Ｏ(1)。 将s=0也看成是基本操作，则语句频度为２，时间复杂度仍为Ｏ(1)

线性时间阶
  1. for(i=1;i<=n;++i){
  2.     ++x;
  3.     s+=x;
  4. }

语句频度为：2n，其时间复杂度为：O(n)，即为线性阶。

平方阶
  1. for(i=1;i<=n;++i){
  2. 　　　　for(j=1;j<=n;++j){
  3. 　　　　    ++x;
  4. 　　　　    s+=x;
  5. 　　　　}
  6. }

语句频度为：2n2，其时间复杂度为：O(n2)，即为平方阶。

三次方阶
  1. //两个n阶方阵的乘法
  2. for(i=1，i<=n;++i){
  3.     for(j=1;j<=n;++j){
  4.         c[i][j]=0;
  5.         for(k=1;k<=n;++k){
  6.             c[i][j] += a[i][j] * b[k][j];
  7.         }
  8.     }
  9. }

由于是一个三重循环，每个循环从1到n，则总次数为：n×n×n=n3　时间复杂度为T(n)=O(n3)

对数阶
count=1;
while(count<N){
    count *= 2;
}

设：程序需要执行 k 次， 则 k = f（n）

当执行k 次时： count 2 2 …… 2 即：count = count * 2^k

即：count * 2^k < N 得：k < log2n (以2为底n的对数)

递归

// 求整数n(n>=0) 阶乘
int fact (int n){
    if(n <=1) return 1;
    return n * fact(n-1);
}

递归的三要素：

  • 初始条件
  • 终止条件
  • 转移条件（状态转移）

求解如下图：

数据结构概论 - 图11

总结

数据结构概论 - 图12

空间复杂度

空间复杂度的定义

空间复杂度(Space complexity) ：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记作：S(n)=O(f(n)) 其中： n 为问题的规模(或大小)

程序运行时存储空间一般包括三个方面：

➢ 程序代码；

➢ 执行数据；

➢ 辅助空间/临时变量；

一般地，算法的空间复杂度指的是辅助空间。

例如： 一维数组 a[n]： 空间复杂度 O(n) ； 二维数组 a[n] [m]： 空间复杂度 O(n*m)

or(i=1;i<=n;++i)
　　for(j=1;j<=n;++j)
　　{++x;s+=x;}

临时变量为：i,j，s，x；空间复杂度为：O(1)，即常量阶。

// 求整数n(n>=0) 阶乘
int fact (int n){
    if(n <=1) return 1;
    return n * fact(n-1);
}

递归的特点是先调用，后执行，所以在调用时现将数据压到栈中，最后再执行。所以空间复杂度为 O(n)