2021-08-04 21:41 已编辑江苏理工学院 C++

关注

数据结构：基本概念和算法分析

基本概念和算法分析

基本概念

数据（data）——能输入到计算机并能被计算机程序处理的符号的总称
- 非常广泛的概念，一般我们讨论的都是数据，一般分为数值型数据和非数值型数据两种。
数据元素（data element）——数据的基本单位（例如整型数，字符串，结构等），通常作为一个整体考虑，由若干个数据项组成
- 数据项是数据的最小单位，不可再分。
数据对象（data object）——性质相同的数据元素的集合，是数据的子集
- 是一个集合，比如说班上的所有学生。

他们之间的有这样的大小关系：
数据 > 数据对象 > 数据元素 > 数据项

数据结构（data structure）——是相互之间存在一种或多种特定关系的数据元素的集合
- 数据结构分成两块，一是数据，二是结构，所谓结构即相互关系。

数据结构是一门描述计算机处理对象和它们之间的关系以及相应的处理方法的学科。

（数据对象、数据关系、基本操作）

结构——数据元素之间不是孤立存在的，他们之间的相互关系称为结构。

故数据结构是个二元组 Data_Structure=(D,S)，其中，D是数据元素的有限集，S代表D上元素之间关系（结构）的有限集。

可以说数据结构 = 数据 + 结构。

例：
在计算机科学中，复数可取如下定义：复数是一种数据结构，即 Complex=(C,R), 
其中:C是含有两个实数的集合{c1,c2}; R={P},
其中有序偶<c1,c2>表示c1是复数的实部，c2是复数的虚部，而P是定义在集合C上的一种关系{<c1,c2>},比如c1±c2i

逻辑结构

定义

二元组这样对数据结构的定义仅是从操作对象角度出发的一种数学描述，也就是从操作对象抽象出的数学模型。结构定义中的关系也就是数据的逻辑结构。他的特点是：

描述数据之间的逻辑关系
与数据存储无关，独立于计算机
是从具体问题中抽象而来的数学模型

分类

数据结构大体上分为：

线性结构：有且仅有一个开始结点和终端结点，所有结点最多有一个直接前趋和一个直接后继。

如：线性表，栈，队列，串

非线性结构：一个结点可能有多个直接前趋、直接后继。

如：树，图

也可分为四种基本逻辑结构：

集合：同属于一个集合
线性结构：一对一
树形结构：一对多
图状结构：多对多

存储结构

定义

物理结构又称存储结构是数据结构在计算机中的表示或叫映像。

我们可以用由若干个位(bit)组合而成的位串表示一个数据元素，通常称这个位串为元素或结点。
当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。
所以元素（或结点）即位串可看成数据元素在计算机中的映像。

分类

结构在计算机中有两种不同的表示方法：

顺序映像——顺序存储结构
非顺序映像——链式存储结构

四种基本的存储结构：

顺序存储结构：用一组连续的存储单元，依次存储元素，逻辑关系依托存储位置表示。
链式存储结构：用任意的存储单元，依靠指针表示元素之间的逻辑关系。
索引存储结构（*）
散列存储结构（*）

如图所示：

现有两个复数 $z_1=3.0-2.3i,z_2=-0.7+4.8i$ ，左图用顺序存储结构的特点是，像一维数组一样，依次存储元素。右图是链式存储结构，以指针的形式在3.0的后面存储指针指向-2.3的存储位置0415。

二者之间的关系

存储结构是逻辑关系与元素本身的映像。
数据的逻辑结构和物理结构是密切相关的两个方面。
逻辑结构是数据结构的抽象，存储结构是数据结构的实现，二者综合建立起数据元素之间的关系。
算法的设计取决于逻辑结构，而算法的实现依赖于存储结构。

数据类型

定义

类型的概念使其规定了在程序执行期间的变量或表达式的取值范围以及其上的操作。

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

所以说数据结构的作用是1.约束取值范围 2.约束操作。

抽象数据类型

定义

抽象数据类型 ADT（Abstract Data Type）是指一个数学模型以及定义在其上的一组操作。它的定义取决于数据的逻辑结构，而与存储结构无关。

抽象数据类型和数据类型实质上是一个概念，因为他们的定义都是取决于其数学特性，对于用户来说是相同的。因此抽象的意义，就在于其具有更丰富的数学抽象特性。

一个含抽象数据类型的软件模块通常应含定义、表示和实现3个部分，目前我们只谈定义。

抽象数据类型可用三元组Data_Structure_Operation $= (D, S, P)$ 表示，分别是数据对象，数据关系，基本操作。甚至可以直接称为数据结构和其上操作的二元组。

格式

ADT 抽象数据类型名{
    数据对象:<数据对象的定义>
    数据关系:<数据关系的定义>
    基本操作:<基本操作的定义>
}ADT 抽象数据类型名

其中，数据对象和数据关系的定义用伪代码描述，基本操作的定义格式为

基本操作名(参数表)
    初始条件:<初始条件的描述>
    操作结果:<操作结果描述>

基本操作参数有两种，赋值参数和引用参数。

赋值参数：只为操作提供输入值

引用参数：以&打头，除可提供输入值外，还返回操作结果。
初始条件：操作执行前数据结构和参数应满足的条件

若不满足，则操作失败，返回相应错误信息。
操作结果：操作正常完成之后，数据结构的变化状况和应返回的结果

算法分析

算法定义

算法是对特定问题求解步骤的一种描述，它是指令的有限序列。

有穷性

执行步骤有穷，步骤执行时间有穷。
确定性

每一条指令含义明确，算法只有唯一的执行路径
可行性

所有操作都能通过有限次基本运算实现
输入

输入可以有也可以没有，但输出至少要有一个

设计要求

正确性
可读性
健壮性

当输入数据非法时，也能做出适当的反应进行处理，而不是产生莫名其妙的结果。

处理错误的方法应是返回一个表示错误性质的值，而不是打印错误信息且中止程序的执行。
效率与低存储量需求

执行时间短且空间占用少。目前由于计算机飞速发展，实际中更注重时间复杂度。

效率度量

算法执行时间依托算法所编制程序在计算机上运行的时间来体现。像牛客网的刷题训练就是采用计算机内部计时的方法，但老师也说过没什么用，因为这种度量的方法很大程度上受制于计算机本身的硬软条件。这表明使用绝对时间衡量算法的效率是不合适的。因此，人们常常采用事前估算的方法。

一特定算法的“工作量大小”，我们认为依赖于问题的规模（通常用整数n表示）。算法中基本操作被重复执行的次数是问题规模n的某个函数 $f (n)$ ，算法的时间度量记为
$T (n) = O (f (n))$
它表示二者增长率相同，称为算法的渐进时间复杂度，简称时间复杂度。一般，最深层循环内的语句的原操作执行次数即频度，就是 $T (n)$ 。

//1.
for(i=0;i<100;i++){
   
    x++;}
//2.
for(i=0;i<n;i++){
   
    x++;}
//3.
for(i=0;i<n;i++)
    for(j=0;j<n;j++){
   
        x++;}

这三段程序的时间复杂度分别为 $O(1),O(n),O(n^2)$ ，分别称为常数阶，线性阶，平方阶。另外常见的时间复杂度还有对数阶 $O (l o g n)$ ，指数阶 $O(2^n)$ ，阶乘阶 $n!$ 等。

由图我们可以看出，我们尽量多选用多项式阶 $O(n^k)$ 的算法，而不是指数阶 $O(k^n)$ 的算法。

例题

为兼具准确性和实用性，我们通常使用大O渐进表示法来表示算法时间复杂度。

Example 1

for(int i=0;i<n;i++){
   
    for(int j=0;j<n;j++){
   
        count++;
    }
}
for(int k=0;k<2*n;k++){
   
    count2++;
}
int M=10;
while(M--){
   
    count3++;
}

该算法总共执行准确次数为 $n^2+2×n+10$ ，但是我们只需要最高阶来表示，即 $T(n)=O(n^2)$ 。因为当n趋向于无穷时，只有 $n^2$ 对时间复杂度的影响最大，其他基本可以忽略。

Example 2

int BinarySearch(int *arr,int size,int key){
    int left=0;
    int right=n;
    while(left<=right){
        int mid=left+((right-left)>>1);
        if(arr[mid]<key){
            left=mid+1;
        }
        else if(arr[mid]>key){
            end=mid-1;
        }
        else
            return mid;   
    }
    return -1;
}

该算法分最好最坏两种情况：