计算机二级公共基础知识(算法数据结构)总结

野性酷女 2021-09-25 01:34 336阅读 0赞

> 博客目的在于复习一些基础知识，尤其数据结构相关的知识

### 目录 ###

*  一、算法
 *   *  1 定义：
     *  2 基本特性
     *  3 基本要素：
     *  4 基本结构：
     *  5 时间复杂度：
     *  6 空间复杂度：
 *  二、数据结构
 *   *  1 定义：
     *  2 数据结构的逻辑结构分类：
     *  3 数据结构的存储结构分类
     *  4 数据结构的运算
     *  5.1 数据结构的逻辑结构-》线性表
     *  5.2 数据结构的逻辑结构-》栈
     *  5.3 数据结构的逻辑结构-》队列
     *  5.4 数据结构的逻辑结构-》线性链表
     *  5.5 数据结构的逻辑结构-》树
     *   *  基本概念
         *  二叉树
         *  树的遍历
     *  6 查找技术
     *   *  6.1 顺序查找
         *  6.2 二分查找
     *  7 排序
     *   *  快速排序
     *  总结

# 一、算法 #

## 1 定义： ##

解决问题完整准确的描述（程序 = 算法 + 数据）

例如：可以将勾股定理公式 a²+b²=c² 看成一个算法，知道了a 和 b的值求c

## 2 基本特性 ##

<table> 
 <thead> 
  <tr> 
   <th>特性</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>可行性</td> 
   <td>计算机硬件可支持运算该算法</td> 
  </tr> 
  <tr> 
   <td>有穷性</td> 
   <td>不出现死循环的情况</td> 
  </tr> 
  <tr> 
   <td>足够的情报</td> 
   <td>应该有输入信息和输出信息</td> 
  </tr> 
 </tbody> 
</table>

## 3 基本要素： ##

<table> 
 <thead> 
  <tr> 
   <th>要素</th> 
   <th>举例</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>算术运算</td> 
   <td>加减乘除</td> 
  </tr> 
  <tr> 
   <td>逻辑运算</td> 
   <td>与或非</td> 
  </tr> 
  <tr> 
   <td>关系运算</td> 
   <td>大于小于等</td> 
  </tr> 
  <tr> 
   <td>数据传输</td> 
   <td>输入输出赋值等</td> 
  </tr> 
 </tbody> 
</table>

## 4 基本结构： ##

*  顺序
 *  选择
 *  循环

## 5 时间复杂度： ##

执行算法的计算工作量（基本运算次数）

## 6 空间复杂度： ##

执行算法需要的内存空间

时间复杂度和空间复杂度无必然联系

# 二、数据结构 #

## 1 定义： ##

**数据**：数据元素的集合

**数据元素**：若干数据项组成，数据项为数据最小单位

**结构**：数据元素之间的关系

**数据结构**： 相互关联的数据元素的集合

例如：
    
    一年由春夏秋冬四季组成
    
    数据元素：春夏秋冬
    
      数据项：1~12的月份
    
       结构：春夏秋冬按顺序运转
    
    一年按照春夏秋冬的顺序来运转，组成一年的光景，
    
    我们将一年看成是一个存储了四季，四季包含各个相关月份的顺序数据结构。

## 2 数据结构的逻辑结构分类： ##

数据元素的逻辑关系（前后关系）

<table> 
 <thead> 
  <tr> 
   <th>分类</th> 
   <th>代表项</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>线性</td> 
   <td>栈，队列、线性表</td> 
   <td>其特点是所有数据在一条线上，只有一个头和一个尾</td> 
  </tr> 
  <tr> 
   <td>非线性</td> 
   <td>树、图</td> 
   <td>例如 - 父亲 和 儿子女儿的关系，他们可以看成是一个树关系，父亲是根节点，儿子女儿是子节点</td> 
  </tr> 
 </tbody> 
</table>

## 3 数据结构的存储结构分类 ##

数据的逻辑结构在计算机存储空间中的存放方式

<table> 
 <thead> 
  <tr> 
   <th>分类</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>顺序存储</td> 
   <td>一块连续的存储空间</td> 
  </tr> 
  <tr> 
   <td>链式存储</td> 
   <td>通过指针域进行关联起来的一块存储空间</td> 
  </tr> 
 </tbody> 
</table>

## 4 数据结构的运算 ##

*  插入
 *  删除
 *  查找
 *  排序

## 5.1 数据结构的逻辑结构-》线性表 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70_pic_center]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 2]

## 5.2 数据结构的逻辑结构-》栈 ##

它是一种特定的线性表  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 3]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 4]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 5]

## 5.3 数据结构的逻辑结构-》队列 ##

队列也是一种特定的线性表  
队尾插入元素，队头删除元素  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 6]  
在 rear端进行插入元素，在front进行删除元素  
插入一个元素 rear指针向上移动  
删除一个元素front指针向上移动

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 8]  
***上面第（3）点，应该是s=容量或s=0***

## 5.4 数据结构的逻辑结构-》线性链表 ##

线性表的存储方式有两种： **顺序 和 链式** ， 一般采用顺序存储

1.  线性表的顺序存储结构又称为顺序表
2.  线性表的的链式存储结构又称为线性链表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 9]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 10]

## 5.5 数据结构的逻辑结构-》树 ##

它是非线性结构  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 11]

### 基本概念 ###

<table> 
 <thead> 
  <tr> 
   <th>概念</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>根结点</td> 
   <td>图中的A点即为根结点，无父结点只有子结点的结点</td> 
  </tr> 
  <tr> 
   <td>结点的度</td> 
   <td>结点所拥有子树的个数称为结点的度，A的度是3</td> 
  </tr> 
  <tr> 
   <td>树的度</td> 
   <td>树中所有节点的度的最大值成为该树的度</td> 
  </tr> 
  <tr> 
   <td>叶子结点</td> 
   <td>度为0的结点 ，图中的 K L M N H J 都是叶子结点</td> 
  </tr> 
  <tr> 
   <td>树的深度（高度）</td> 
   <td>树中所有节点的层次的最大值称为该树的深度，图中为4层</td> 
  </tr> 
 </tbody> 
</table>

### 二叉树 ###

有限结点集合（可为空），每一个结点最多有两颗子树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 12]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 13]

完全二叉树，最多缺少右边结点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 14]  
**二叉树的特性**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 15]  
**其中 log运算是向下取整**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 16]

### 树的遍历 ###

一共三种：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70_pic_center 1]

*  前序遍历 根左右
 *  中序遍历 左根右
 *  后序遍历 左右根

所谓前、中、后可以看成是针对根结点而言，可参考上面的图。  
一开始就访问根结点的就是前序遍历。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 17]  
**前序遍历 第一个输出的一定是 根节点**

## 6 查找技术 ##

### 6.1 顺序查找 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 18]  
顺序查找适用于所有的线性表

### 6.2 二分查找 ###

二分查找适用于顺序存储的有序线性表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 19]

**注意：即使是有序线性表，如果采用链式存储，也只能顺序查找**

## 7 排序 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 20]

### 快速排序 ###

第一个为划分基准  
从右到左顺序找比基准小的数进行交换  
从左到右顺序找比基准大的数进行交换  
重复上面的动作  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 21]

## 总结 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 22]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70_pic_center]: /images/20210923/48d15fa001de4195a4a0d890b0cb9f1e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70]: /images/20210923/434c40873c3a4ba1ac46cb2904ef7af3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 1]: /images/20210923/e076d510a9e44296b546b8e455d58a2b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 2]: /images/20210923/5fc4274f910c4d1eb76c2dd58842bea1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 3]: /images/20210923/76e7e179494c4e4791918d579d20d080.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 4]: /images/20210923/b594945482534887937954d87df038d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 5]: /images/20210923/c6de1be801504e7b9586116fb57160a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 6]: /images/20210923/8096464cf45345e4909bd85ebd326112.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 7]: /images/20210923/8c506be71b574cb0a87f3908cc10c55a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 8]: /images/20210923/05616e942ca6477f827c7138bc3a4e77.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 9]: /images/20210923/0440cc94038c4a9da20b6818110802fd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 10]: /images/20210923/02f2b9a602804c8bbef67c248a302d9a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 11]: /images/20210923/1d733ee6e9764171b4c6f6009ed3fb32.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 12]: /images/20210923/b760cb7b3b3c4c87a5878f143da9ed79.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 13]: /images/20210923/513058e801e64de8b7569f3047ad118b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 14]: /images/20210923/98c4fc4da6944257bff3f6bf783baef1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 15]: /images/20210923/1832a156a5b649b482f772883ff1f871.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 16]: /images/20210923/2e4b6b17d02f4351980f5fcc873331e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210923/471e6a0935774b7f849aba767567516b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 17]: /images/20210923/1a6c5c15b6c54ae5b9b98f43882a0897.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 18]: /images/20210923/3be7407865a44e2f8ce7d23e7adee2c6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 19]: /images/20210923/1304e8ef763d4987a68dc40c6b7bd98b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 20]: /images/20210923/0f09ea41c1374db7a7e28520b501e11d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 21]: /images/20210923/f2a9a567b7ef4b299ba9dccff84c18b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d6dDE5ODgxMTIz_size_16_color_FFFFFF_t_70 22]: /images/20210923/18e2c42fe03d478c8fd04c68e698aa30.png