# 数据结构

**Repository Path**: sanxp/data-structure

## Basic Information

- **Project Name**: 数据结构
- **Description**: 数据结构存储图床和markdown笔记与代码
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-09-05
- **Last Updated**: 2022-01-10

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 数据结构与算法





## 1. 绪论



### 1.1 数据结构的起源



​	**数据结构是研究计算机存储、组织数据的方式以及他们之间的关系和操作的学科**



+ 1968年，数据结构作为一门独立的课程
+ 在计算机相关专业中开始接受 《数据结构》的 “折磨”
+ 程序设计 = 数据结构 + 算法





### 1.2 基本概念以及术语



<h4>数据</h4>

+ 是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合
+ 数据不仅仅包含整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型
+ 也就是说，我们这里说的数据，其实就是符号，而且这些符号必须具备两个前提
  1. 可以输入到计算机中
  2. 能被计算机程序处理



<h4>数据元素</h4>

+ 组成数据的、有一定意义的基本单位
+ 在计算机中通常作为整体处理，也被称为 **记录**
+ 可以理解为 C 语言中结构体创建的结构体变量
+ 可以理解为 C++ 中通过类的实例化出的对象
  + 人类中，人就是数据元素
  + 狗类中，狗就是数据元素



<h4>数据项</h4>

+ 一个数据元素可以是由若干个数据项组成的
+ 数据项是数据不可分割的最小单位
+ 可以理解为 C++ 类对象中的属性
  + 人对象中，可以有 眼睛、鼻子、嘴巴、手、脚、姓名、年龄...这些数据项

> 真正讨论问题时，数据元素才是数据结构中建立数据模型的重点





<h4>数据对象</h4>

+ 性质相同的数据元素的 ==集合==，是数据的子集
+ 性质相同
  + 是指元素具有 **相同数量和类型的数据项**

~~~cpp
//以下 3 个类中他们的 “数据项” 并不相同
struct Person1
{
    char m_Name[64];
    int m_Age;
};

struct Person2
{
    char m_Name[64];
    char m_Age[32];
};

struct Person3
{
    char m_Name[64];
    int m_Age;
    int m_Height;
};
~~~



+ 集合

~~~cpp
int main()
{
    struct Person1 m_Array[]
    {
        // data
        {"aaa", 10},
        {"bbb", 20},
        {"ccc", 30}
    };

    return EXIT_SUCCESS;
}
~~~



> 在不产生混淆的情况下，我们都将数据对象简称为数据





<h3>数据结构</h3>

+ 结构，简单的理解就是关系
+ 严格点说，结构是指各个组成部分相互搭配和排列的方式
+ 现实世界中，不同数据元素之间，不是独立的，而是存在 **特定的关系** ，我们将这些关系统称为结构

> 是相互之间存在一种或多种特定关系的数据元素的集合



为编写出一个好的程序，必须分析待处理对象的特性以及各个处理对象之间存在的关系

这也是研究数据结构的意义所在

可以理解为专业的厨师，在切不同的食材的时候，会挑选不同的刀具







### 1.3 逻辑结构与物理结构

按照不同的角度，我们把数据结构分为 ==逻辑结构== 和 ==物理结构==



#### 1.3.1 逻辑结构

指数据对象中数据元素之间的相互关系，其实这也是我们今后最需要关注的问题



逻辑结构分为以下 **四种**：

​	`将每个数据元素看作一个结点，用圆圈表示`

​	`元素之间的逻辑关系用结点之间的连线表示，如果这个关系是有方向的，那么用带箭头的连线表示`



<h4>1. 集合结构</h4>

+ 集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系
+ 各个数据元素是平等的
+ 集合关系类似于数学中的集合

<img src="https://cdn.jsdelivr.net/gh/MagicCD/picture-C-/img/image-20210905214624182.png" alt="image-20210905214624182" style="zoom:80%;" />

<h4>2. 线性结构</h4>

+ 线性结构中的元素之间是 **一对一** 的关系
+ 除了 第一个数没有 前区，最后一个数没有 后继，其余的数都有唯一的 前区和后继

<img src="https://gitee.com/sanxp/data-structure/raw/master/img/image-20210905224426308.png" alt="image-20210905224426308" style="zoom:80%;" />

<h4>3. 树形结构</h4>

+ 树形结构中是数据元素之间存在一种 **一对多** 的层次关系
+ 用 比例表达就是  1: n

<img src="https://gitee.com/sanxp/data-structure/raw/master/img/image-20210905224845814.png" alt="image-20210905224845814" style="zoom:80%;" />

<h4>4. 图形结构</h4>

+ 图形结构的数据元素是 **多对多** 的关系
+ 用 比例表达就是  n:n，意味着 2 关联的 1、4、8、5 既是 前区 又是 后继

<img src="https://gitee.com/sanxp/data-structure/raw/master/img/image-20210905225031268.png" alt="image-20210905225031268" style="zoom:80%;" />

#### 1.3.2 物理结构

说完了逻辑结构，再说 **物理结构**，也有的书称为 **存储结构**



+ 指数据的逻辑结构在计算机中的存储形式，共分为 2种：==顺序存储和链式存储==

> 顺序存储其实就是数组



<h4>数据存储</h4>

+ 是把数据元素存放在地址连续的存储单元里，其数据的逻辑关系和物理关系是一致的
+ 数组就是这样的顺序存储结构

![image-20210905231256966](https://gitee.com/sanxp/data-structure/raw/master/img/image-20210905231256966.png)

<h4>链式存储</h4>



链式存储也称为链表，我们用指针来寻找下一个元素的地址



如果所有问题用顺序存储就能解决，一切就好办了

实际上，总会有人插队、退队，使整个结构处于变化之中，显然用顺序存储并不方便



+ 把数据元素放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的
+ 数据元素的存储关系并不能反映其逻辑关系
+ 因此需要用一个 ==指针存放数据元素的地址==，这样通过地址就可以找到相关联数据元素的位置

![image-20210905231854874](https://gitee.com/sanxp/data-structure/raw/master/img/image-20210905231854874.png)

<font color="red">显然，链式存储就灵活多了，数据存在哪里并不重要，只要有一个指针存放了相应的地址即可</font>



**总结：**

![image-20210905232128188](https://gitee.com/sanxp/data-structure/raw/master/img/image-20210905232128188.png)

![image-20210905232148273](https://gitee.com/sanxp/data-structure/raw/master/img/image-20210905232148273.png)













## 2. 算法





### 2.1 算法的定义

**算法（Algorithm）**

如今普遍认可的对算法的定义是：

<font color="seagreen">算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作</font>



+ 现实世界中的问题千奇百怪，当然算法也就千变万化，没有通用的算法可以解决所有的问题
+ 甚至解决一小个问题，很优秀的算法却不一定适合他





### 2.2 数据结构与算法的关系

数据结构只是静态的描述了数据元素之间的关系，高效的程序需要在数据结构的基础上设计和选择算法

+ 算法是为了解决实际问题而设计的
+ 数据结构是算法需要处理的问题载体
+ 数据结构与算法相辅相成







### 2.3 算法的比较

**需求：**

现在我们需要写一个 求 1+2+3+......+100的结果程序，你应该怎么写呢？

大多数人马上会写出下面的 C++ 代码（或其他语言）

~~~cpp
int main()
{
    int i, sum = 0, n = 101;

    for (i = 1; i < n; i++)
    {
        sum = sum + i;
    }

    cout << sum << endl;

    system("pause");
    return 0;
}
~~~



当然，如果这个问题让高斯去做，他可能会写出如下代码

~~~cpp
int main()
{
    int sum = 0, n = 100;

    sum = (1 + n) * n / 2;

    cout << sum << endl;

    system("pause");
    return 0;
}
~~~



很显然，无论是从人类还是计算机的角度看，高斯的算法效率会高出很多

这就是一个好的算法会让你的程序更加高效



### 2.4 算法的特性

算法具有 5 个基本的特征：**输入、输出、有穷性、确定性和可行性**