绪论原创

数据结构三要素
数据的逻辑结构

# 基本定义

『数据(data)』是信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。『数据』是计算机程序加工的原料。
『数据元素』是『数据』的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干「数据项」组成。
「数据项(data element)」是构成数据元素的不可分割的最小的单位，也成为字段、域、属性。

如：学生记录作为一个数据元素，它由学号、姓名、性别等数据项组成。

「数据对象(data object)」是具有相同性质的数据元素的集合，是数据的一个子集。

如，整数数据对象的集合；大写字母的数据对象就是集合{'A','B',...,'Z'}

「数据类型」是一个值的集合和定义在此集合上的一组操作的总称。分为：

原子类型。其值不可再分的数据类型。如：整型、实型、字符型、枚举类型等。
结构类型。其值可以再分解为若干成分(分量)的数据类型。如：数组、结构体等。
抽象数据类型(ADT, abstract data type)。抽象数据组织及与之相关的操作。如：集合与集合的并、交、差运算。

可以用ADT定义一个完整的数据结构。描述了数据的逻辑结构和抽象运算，通常用(数据对象，数据关系，基本操作集)这样的三元组来表示，从而构成一个完整的数据结构定义。

「数据结构(data structure)」是数据元素之间存在一种或多种特定关系的集合。「结构(structre)」是指数据元素之间的相互关系，即数据的组织形式。

数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

# 逻辑结构

『逻辑结构』是指数据元素之间的逻辑关系，即从逻辑关系上描述数据，是抽象的，独立于数据的存储结构。

数据的逻辑结构

# 逻辑结构分类

# 集合结构

各个数据在一个集合内。各个数据之间并无关系。

这里的关系是指数据关系。

# 线性结构

呈线性排列，一对一，除头尾2个数据外，其他数据都有唯一一个前驱和后继。头无前驱，尾无后继。

# 树形结构

一对多关系。又分为：一般树、二叉树。

# 图形结构

多对多关系。又分为：有向图、无向图。

# 存储结构

『存储结构』是数据结构在计算机中的表示(又称映像)，也称物理结构，即如何存储，怎么存储。是具体的。包括数据元素的表示和关系的表示，依赖于数据的逻辑结构和计算机语言。

# 存储结构分类

# 顺序存储

把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中。

提示

优点：

可以实现随机存取

> 随机存取是指，通过一个公式就能拿到任意一个数据

每个元素占用最少的空间

警告

缺点：
只能使用整块的存储单元，会产生较多的碎片。

碎片是指定义或申请了相关空间，但是并未存储相关数据。

# 链式存储

不要求逻辑逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。

提示

优点：
可以充分利用所有存储单元，不会出现碎片显现

警告

缺点：

需要额外的空间来存放下一个结点的指针。
只能实现顺序存取。即只能通过指针，挨个查找才能找到对应的数据。

# 索引存储

在存储元素的信息的同时，还建立附件的索引表。索引表中的每项称为「索引项」，索引项的一般形式是(关键字，地址)。

提示

优点：
检索速度快。

警告

缺点：

附件的索引表占用额外的存储空间。
增删数据也要修改索引表，会花费较多时间。

# 散列存储

根据元素的关键字直接计算出该元素的存储地址，又称哈希(Hash)存储。

提示

优点：
检索、增加和删除结点的操作快。

警告

缺点：
若散列(哈希)函数不好，则可能出现冲突，而解决冲突会增加时间和空间开销。

# 算法 algorithm

$定义$ 对特定问题求解步骤的一种描述，它是指令的有限序列，每条指令表示一个或多个操作。。

# 算法特性

有穷性。一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
确定性。算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
输入。一个算法有零个或多个输入，这些输入取自与某个特定的对象的集合。
输出。一个算法有一个或多个输出，这些输入是与输入有着某种特定关系的量。

警告

算法和程序的区别：
程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。

# 算法评价

算法效率的度量是通过时间复杂度和空间复杂度来描述的。

# 时间复杂度

算法中所有语句的频度之和记为T(n).

频度，是指语句执行的次数。
算法中基本运算(最深层循环内的语句)的频度与T(n)同数量级，因此通常采用算法中基本运算的频度f(n)来分许算法的时间复杂度。记为。其中，n是问题的规模，是问题规模n的某个函数。

时间复杂度的叫法，必须连着字母O。O的含义是T(n)的数量级。通俗来讲即取极限。

常见时间复杂度，性能排列：

最高阶数越小说明算法的时间性能越好！
辅助记忆：常对幂指阶。

# 性能解释

是按算法中，使用频率最高的语句来计算时间复杂度的。

笔记

时间复杂度最终结果是极限结果，是要忽略高阶项系数和低阶项，如：
某一算法执行的次数为，则该算法时间复杂度为：

O(1)
语句执行一次。
```
inx x=2;
whlie(x<n/2>)
   x=2*x;
```
设该语句公执行了t次，则，故,，最终时间复杂度为
O(n)
```
int sum=0,i=1;
while(i<n>){
  sum = sum+i;
  i++;
}
```
执行频率最高的是while循环体中的语句，一共执行n次。

for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
sum=sum+1;
}
}

对于外层循环，相当于内部时间复杂度为`O(m)`的语句在循环`n`次。所以时间复杂度为：$T(n)=O(m*n)$,若`m=n`，则$T(n)=O(n^2)$
4. $O(nlog_2n)$
 ```c
 int x=2;
 for(int i=0; i < n ; i++){
   x=0;
   while(x<n/2)
      x=2*x;
 }

执行频率最高的语句是x=2*x;，该语句内层循环执行了次，外层循环执行了n次，所以
5.
6.
7.
8.

# 空间复杂度

是指在算法运行过程中所使用的辅助空间的大小。记为：。

除了需要存储算法本身的指令、常数、变量和输入数据外，还需要存储对数据进行操作的工作单元和储存一些为实现计算所需信息的辅助空间。
若输入数据所占空间只取决于问题本身，和算法无关，这样只需分析该算法在实现时间所需的辅助单元即可。
算法原地工作是指算法所需的辅助空间是常量，即O(1)。

# 如何选择好的算法

首先考虑的是算法的正确性，即对于一切合法的输入数据，该算法经过有限时间的执行都能得到正确的结构。
其次还要考虑：
- 时间复杂性，即执行算法所耗费的时间。
- 空间复杂性，即执行算法所耗费的存储空间，主要是辅助空间。
- 可读性和可操作性，即算法应易于理解、易于编程、易于调试等。

# 如何设计好一个算法

正确性，能够正确地解决求解问题。
可读性，应具有良好的可读性，以帮助人们理解。
健壮性，输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
高效率与低存储需求。

上次更新: 2022/06/30, 14:46:07

顺序表基础知识→