数据结构中的基础概念

朱雀 2022-05-26 12:50 207阅读 0赞

**数据：**数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。  
数据包括：整形、实型、布尔型、图像、声音、字符等等。

**数据元素：**数据元素是组成数据的基本单位，是数据集合的个体；  
**数据对象：**数据对象是性质相同的数据元素的集合，是数据的一个子集。如字符集合C=\{‘A’,’B’,’C,…\} 。  
**数据项：**一个数据可以由一个或多个数据项组成，数据项是对客观事物某一方面特性的数据描述，是有独立含义的最小单元；  
        数据特点：  
1. 可被计算机接收（与计算机的关联性）  
2. 可被加工；  
        数据构成：  
1. **数据元素**—组成数据的基本单位（是数据集合的个体）  
2. **数据对象**—性质相同的数据元素的集合（是数据集合的子集）  
**数据结构：** 数据结构是指相互之间存在一种或多种特定关系的数据元素集合；  
       数据结构的形式定义为:  
数据结构是一个二元组 , 数据结构的形式定义为:  
数据结构是一个二元组  
        Data\_Structures = (D, R)  
        其中:D 是数据元素的有限集，  
        R 是 D上关系的有限集。

**数据类型:**  数据类型是一组性质相同的值集合以及定义在这个集合上的一组操作的总称，可简单理解为：数据类型在一种程序设计语言中，变量所具有的数据种类。

数据类型可分为两大类：**(1)原子类型**，原子类型的值是不可再分的，如：C语言中提供的整形、实型和字符型及指针；**(2) 结构类型**，结构类型的值是由若干成分按照某种结构组合而成的，因此是可以分解的，并且它的成分可以是原子的也可以是结构的；

--------------------

**抽象数据类型（Abstract Data Type,ADT）：**抽象数据类型定义了一个数据对象、数据对象中个元素之间的结构关系以及一组数据的操作；抽象数据类型最重要的特点是数据抽象和信息屏蔽；

数据元素之间的关系应该具体包含三个方面：数据的逻辑结构、数据的物理结构和数据的运算集合；  
       **逻辑结构：**逻辑结构是指数据元素之间的逻辑关系描述。  
       根据数据元素之间关系的不同特性，通常有以下四类基本结构：

①：集合结构：数据元素之间除了同属与一个集合外，无任何其他关系；  
②：线性结构：结构中的数据元素之间存在着一对一的线性关系；  
③：树状结构：结构中的数据元素之间存在着一对多的层次关系；  
④：图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系；

由于集合中关系只属于或不属于这种简单的属于关系，可以用其他的结构代替它，故数据的四类基本逻辑结构可概括为：  
逻辑结构：  
1. 线性结构—线性表、栈、队列、字符串、数组、广义表  
2. 非线性结构—图、树  
       存储结构（物理结构）：是逻辑结构在计算机中的存储映像，包括数据元素映像和关系映像；

--------------------

**算法：**算法时规则的有限集合，是为解决特定问题而规定的一系列操作。算法+数据结构 = 程序；

**算法的特性：**  
①：有限性：有限步骤内正常结束，不能形成无限循环；  
②：确定性：算法中的每一个步骤必须有确定含义，无二义性；  
③：可行性：原则上能精确运行，操作可通过已实现的基本运算执行有限次而完成；  
④：输入：有0个或多个输入；  
⑤：输出：至少有一个或多个输出。  
       最基本的特性是：**有限性、确定性和可行性**；  
       **算法、语言、程序的关系：**  
①算法：描述数据对象之间的关系（包括数据逻辑关系、存储关系描述）；  
②描述算法的工具：算法可用自然语言、框图或高级设计语言描述；  
③：程序是算法在计算机中的实现。  
简而言之：语言是描述算法的工具，程序是算法的实现。

**算法的执行时间：**算法的执行时间是指算法中所有语句执行时间的总和。每条语句的执行时间等于该条语句的执行次数乘以执行一次所需实际时间；

**语句频度：**语句频度是指该语句在一个算法中重复执行的次数。一个算法时间耗费就是该算法中所有语句的频度之和。

**算法的时间复杂度：**算法的时间复杂度就是算法时间度量，记作：T(n) = O(f(n)),f(n)一般是算法中最大的语句频度。它表示随着问题规模n的增大，算法的执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度（算法的频度之和）；  
数据结构中常用的时间复杂度计数有以下七种：

1.  O(1) ：常数型
2.  O (n)：线性型
3.  O(n^2):平方型
4.  O(n^3):立方型
5.  O(㏒n) ：对数型
6.  O(n㏒n) ：线性对数型（二维型）
7.  O（2^n）：指数型

以下六种计算算法时间复杂度的多项式是最常用的。其关系为：  
`O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)`

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

以下面程序段为例，进行时间复杂度的分析。  
       步骤1：先把所有语句改为基本操作。

/*执行频度*/
    for (i = 0; i<n; i++)                              // n
        for (j = 0; j<n; j++)                          // n*n
        {
            c[i][j] = 0;                               // n^2
            for (k = 0; k<n; k++)                      // n^2*n
                c[i][j] = c[i][j] + a[i][k] * b[k][j]; // n^3
        }
    }

步骤2：分析每一条语句的语句频度，标到每条语句后边， 如上  
       步骤3 ： 统计总的语句频度： n+n^2+n^2+2\*n^3  
       步骤4：判断最大语句频度为n^3，所以时间复杂度为O(n^3)。  
其中O表示等价无穷小。

**算法的时间复杂度为: T(n)=O(2n^3 + 2n^2 + n)=O(n^3)**

**算法的空间复杂度：**算法的空间复杂度S(n)定义为该算法所耗费的存储空间的数量级,它是问题规模n的函数。  
       该存储空间一般包括三个方面：

*  指令常数变量所占用的存储空间(程序本身);
 *  输入数据所占用的存储空间(输入数据);
 *  辅助(存储)空间(辅助变量)。  
        一般地，算法的空间复杂度指的是辅助空间。  
        一维数组a\[n\]： 空间复杂度 O(n)  
        二维数组a\[n\]\[m\]： 空间复杂度 O(n\*m)  
        例如：我们在交换两个变量的定义了一个临时变量temp;那么其空间复杂度就为O(1);

**数据结构的基本操作：**

①插入：在数据结构中的指定位置增添新的数据元素；  
②删除：删除数据结构中某个指定的数据元素；  
③更新：改变数据结构中某个元素的值，在概念上等价于删除和插入操作的组合；  
④查找：在数据结构中寻找满足某个特定条件的数据元素（包括位置和值）；  
⑤排序：（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使数据元素按值由小到大或由大到小排列。