数据结构基础知识点

男娘i 2022-04-16 00:20 382阅读 0赞

### 声明：本内容主要是复习《数据结构(C语言)--严蔚敏等老师编写》的笔记 ###

**数据：**对客观事物的符号描述，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

**数据元素：**数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

**数据项：**一个数据元素有若干个数据项组成，且数据项是数据的不可分割的最小单位。

**数据对象：**性质相同的数据元素的集合，是数据的一个子集。

四者之间的关系如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FuZ2VsaWE2MjA_size_16_color_FFFFFF_t_70][]

**数据结构：**相互之间存在一种或多种关系特定关系的数据元素的集合。

**结构：**数据元素相互之间都不是孤立存在的，它们之间存在着某种关系，这种数据元素之间的关系称为结构。

**集合：**结构中的数据元素之间除了“同属于一个集合”的关系外，没有其他的关系了。（数据元素之间很松散）

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

**树形结构：**结构中的数据元素之间存在一个对多个的关系。（一对多）

**图状结构或网状结构：**结构中的数据元素存在多个对多个的关系。（多对多）                                                                                 ![20181114185708677.png][]

**数据结构的形式定义为：**数据结构是一个二元组Data\_Structure=(D，S )     D：数据元素的有限集，S是D上关系的有限集。

**逻辑结构：**结构中定义的“关系”描述的是数据元素之间的逻辑关系，因此又称为逻辑结构。

**存储结构（物理结构）：**数据结构在计算机中的表示（又称映像）称为数据的物理结构，又叫存储结构。

**元素：**在计算机中，可以用一个由若干位组合起来形成的一个位串表示一个数据元素，通常称这个位串为元素或结点。

**数据域：**当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。

数据元素之间的关系在计算机中有两种不同的表示方法：**顺序映像**和**非顺序映像**，因此得到两种不同的存储结构：**顺序存储结构**和**链式存储结构**。

**顺序映像的特点：**借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

**非顺序映像的特点：**借助指示元素存储地址的**指针**表示数据元素之间的逻辑关系。

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

**抽象数据类型：**指一个数学模型以及定义在该模型上的一组操作。仅仅取决于它的一组逻辑性，跟计算机内部如何实现无关。只要它的数学性质不变，其他的都不影响其外部的使用。

按照“值”的不同特性，高级程序语言中的数据类型可分为：非结构的**原子类型**，和**结构类型**。

**原子类型：**变量的值是不可分解的。

**固定聚合类型：**该类型的变量，其值有确定数目的成分按某种结构组成。

**可变聚合类型：**“值”的成本数目不确定。

**抽象数据类型可用以下三元组表示：**（D，S，P）  D：数据元素的有限集，S是D上的关系集，P是对D的基本操作集。

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

数据对象和数据关系的定义用伪码表示，基本操作的定义格式为：

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

基本操作有两种参数：**赋值参数**只为操作提供输入值；**引用参数**以&打头，除了可以提供输入值外，还将返回操作结果。

**初始条件：**描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。

**操作结果：**说明了操作正常完成之后，数据结构的变化状况和应返回的结构。若初始条件为空，则省略之。

例：抽象数据类型三元组的定义：

ADT Triplet{
    	数据对象：D={e1,e2,e3|e1,e2,e3∈ElemSet(定义了关系运算的某个集合)}
    	数据关系：R1={<e1,e2>,<e2,e3>}
    	基本操作：
    	InitTriplet(&T,v1,v2,v3)
    	操作结果：构造了三元组T，元素e1，e2和e3分别被赋以参数v1，v2和v3的值。
    	DestoryTriplet(&T)
    	操作结果：三元组T被销毁。
    	Get(T,i,&e)
    	初始条件：三元组T已经存在，1≤i≤3。
    	操作结果：用e返回T的第i元值。
    	put(&,i,e)
    	初始条件：三元组T已经存在，1≤i≤3。
    	操作结果：改变T的第i元值为e。
    	IsAscending(T)
    	初始条件：三元组T已经存在。
    	操作结果：如果T的3个元素按升序排列，则返回1，否则返回0。
    	IsDescending(T)
    	初始条件：三元组T已经存在。
    	操作结果：如果T的3个元素按降序排列，则返回1，否则返回0。
    	Max(T,&e)
    	初始条件：三元组T已经存在。
    	操作结果：用e返回T的3个元素中的最大值。
    	Min(T,&e)
    	初始条件：三元组T已经存在。
    	操作结果：用e返回T的3个元素中的最小值。
    }ADT Triplet

这本书使用的是C语言，因此后面有些例子使用的是C语言的编程方式。故我把书中对C语言编程风格截了下来，了解一下。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FuZ2VsaWE2MjA_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FuZ2VsaWE2MjA_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FuZ2VsaWE2MjA_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FuZ2VsaWE2MjA_size_16_color_FFFFFF_t_70 4][]

**算法：**对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。下面是其5个重要特性：

*  有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
 *  确定性：算法中的每一条指令必须有确切的含义，读者理解不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
 *  可行性：一个算法是可行的，即算法中的描述操作都是可以通过已经实现的基本运算执行有限次来实现的。
 *  输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。
 *  输出：一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。

**算法的设计要求：**正确性、可读性、健壮性、效率与低存储量需求。

**算法效率的度量：**事后统计的方法、事前分析估算的方法、机器执行指令的速度。

**算法时间的因素：**一个算法是由控制结构（顺序、分支和循环3种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。

**时间量度：**从算法中选取一种对与所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。

时间复杂度：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作 T(n)=O(F(n))，他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FuZ2VsaWE2MjA_size_16_color_FFFFFF_t_70]: /images/20220416/c4fb8fca3b9b480eb1a0691528ab1988.png
[20181114185708677.png]: /images/20220416/2ea861e8b6b647dc8b97bc0e118e83c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FuZ2VsaWE2MjA_size_16_color_FFFFFF_t_70 1]: /images/20220416/c75cc93fe547448090a2b61a108bb1fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FuZ2VsaWE2MjA_size_16_color_FFFFFF_t_70 2]: /images/20220416/e0d5d6e0d3d94414bfea85cf37a082b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FuZ2VsaWE2MjA_size_16_color_FFFFFF_t_70 3]: /images/20220416/e09dc3ab5dcc4a588f8dd4cb0483ef6d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FuZ2VsaWE2MjA_size_16_color_FFFFFF_t_70 4]: /images/20220416/e01f844257f747908d6060b923c74f33.png