【数据结构与算法】常见数据结构及基本操作

喜欢ヅ旅行 2022-01-22 02:17 356阅读 0赞

### 数据结构及基本操作 ###

*  1.数据结构与算法常见概念：
 *  2.数据结构：
 *   *  2.1线性结构：
     *   *  基本概念
         *  数组
         *  字符串
         *  队列
         *  栈
         *  链表
     *  2.2树形结构
     *   *  基本概念
         *  二叉树的递归遍历
         *  二叉树的非递归遍历
     *  2.3图形结构
     *  2.4集合结构
 *  3.资源链接

总结《大话数据结构》和《C++Primer》，文后附《大话数据结构》和《C++Primer》第五版下载链接，本文相关代码均由C++编写。

# 1.数据结构与算法常见概念： #

**数据**：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。  
**数据元素**：是组成数据的，有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。  
**数据结构**：是相互之间存在一种或多种特定关系的数据元素的集合。  
**数据结构的逻辑结构**：数据对象中数据元素之间的相互关系，分为线性结构、树形结构、图形结构以及集合结构。  
**数据结构的物理结构**：数据的逻辑结构在计算机中的存储形式，分为顺序存储和链式存储（不连续存储）。

**算法**：解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。  
**算法五个基本特性**：输入、输出、有穷性、确定性和可行性。  
**算法时间复杂度O(n)**：常数阶、线性阶、平方阶、对数阶、立方阶、nlogn阶、指数阶。  
**耗时排序**：O(1)<O(logn)<O(n)<O(nlgn)<O( x 2 x^\{2\} x2)<O( x 3 x^\{3\} x3)<O( 2 n 2^\{n\} 2n)<O(n!)<O( n n n^\{n\} nn)

# 2.数据结构： #

## 2.1线性结构： ##

### 基本概念 ###

**线性结构**：数据元素之间是一对一的关系。  
![在这里插入图片描述][20190604205539374.PNG]  
**线性表**：零个或多个数据元素的有限序列。  
**区分数组长度与线性表的长度**：  
数组长度是指存放线性表的存储空间的长度，存储分配后这个值是不变的。  
线性表的长度是线性表中数据元素的个数，随着线性表的插入与删除，这个值是在变换的。  
![在这里插入图片描述][20190605102541429.PNG]**线性表的顺序存储**：用一段连续的存储单元依次存储线性表的数据元素。（通常使用一维数组实现顺序存储结构）  
**线性表的链式存储**：除了存储本身的信息之外，还需存储一个指示后继的信息。  
**顺序存储的插入步骤：**  
a.线性表长度大于等于数组长度，抛出异常  
b.插入位置不合适，抛出异常（判断插入位置与0和最大值的大小）  
c.从最后一个元素开始向前变量，将它们都向后移动一位  
d.将要插入的元素填入指定位置  
e.表长加一  
**顺序存储的删除步骤：**  
a.线性表是否为空  
b.删除位置不合适，抛出异常（判断插入位置与0和最大值的大小）  
c.取出删除元素  
d.从删除元素的位置遍历到最后一个元素位置，将它们前移一位  
e.表长减一  
***链式存储的插入与删除在链表中介绍***  
**顺序存储和链式存储使用场景**：如果频繁使用查找，很少进行插入和删除，易采用顺序存储。如果需要频繁插入和删除，易采用链式存储。

### 数组 ###

[数组及基本操作][Link 1]

### 字符串 ###

[字符串及基本操作][Link 2]

### 队列 ###

[队列及基本操作][Link 3]

### 栈 ###

[栈及基本操作][Link 4]

### 链表 ###

[链表及基本操作][Link 5]

## 2.2树形结构 ##

### 基本概念 ###

**树形结构**：数据元素之间存在一对多的层次关系  
![在这里插入图片描述][201906042101020.PNG]  
**度**：结点拥有的子树数  
**叶结点/终端结点**：度为0的结点  
**树的度**：树内各结点的度的最大值  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzMDUxMg_size_16_color_FFFFFF_t_70]  
**结点间关系图**：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzMDUxMg_size_16_color_FFFFFF_t_70 1]  
**树的深度/高度**：树中结点的最大层次  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzMDUxMg_size_16_color_FFFFFF_t_70 2]  
**二叉树**：是N（N>=0）个结点的有限集合，该集合或为空集（空二叉树），或者由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。  
![在这里插入图片描述][20190616210425838.PNG]  
**满二叉树**：所有分支结点都存在左子树和右子树，并且所有非叶子节点都在同一层上  
![在这里插入图片描述][20190616211356363.PNG]  
**完全二叉树**：对一棵具有n个结点的二叉树按层序编号，如果编号i（1<= i <= n）的结点与同样深度的满二叉树中的编号i 的结点在二叉树的位置完全相同，则这棵二叉树称为完全二叉树  
![在这里插入图片描述][2019061621193146.PNG]  
**二叉树的特点**：

1.  每个结点最多只有两颗子树
2.  左右子树是有顺序的
3.  即使某结点只有一颗子树，也要区分是右子树还是左子树

**二叉树的性质**：

1.  在二叉树的第i层上至多有 2 i − 1 2^\{i-1\} 2i−1个结点（i>=1）
2.  深度为k的二叉树至多有 2 k 2^\{k\} 2k\-1个结点(k>=1)
3.  对任何一棵二叉树T，如果其终端结点数为 n 0 n\_\{0\} n0，此二叉树至多有 2 k 2^\{k\} 2k\-1个结点
4.  具有n个结点的完全二叉树的深度为\[ l o g 2 log\_\{2\} log2n\]+1(\[x\]表示不大于x的最大整数）
5.  n个结点的完全二叉树按层序编号（参考上图），对任意一个结点i有：  
    a. 如果i=1,则i是二叉树的根，如果i>1,其双亲是\[i/2\]  
    b. 如果2i>n，则结点i无左孩子  
    c. 如果2i+1>n，则结点i无右孩子（否则其右孩子为2i+1）

### 二叉树的递归遍历 ###

[二叉树的遍历（递归）][Link 6]

### 二叉树的非递归遍历 ###

未完待续……

## 2.3图形结构 ##

**图形结构**：数据元素的多对多的关系  
![在这里插入图片描述][20190604210132205.PNG]

## 2.4集合结构 ##

**集合结构**：数据元素除了同属于一个集合外，它们之间没有其他关系。  
![在这里插入图片描述][20190604210903140.PNG]

# 3.资源链接 #

[《大话数据结构》+《C++Primer》PDF百度云盘链接][C_Primer_PDF]  
提取码：6a7b

[20190604205539374.PNG]: /images/20220122/3a212bfd6078460bb677ba679606ad0e.png
[20190605102541429.PNG]: /images/20220122/e98254ae55c84fba89283ca169798be6.png
[Link 1]: https://blog.csdn.net/weixin_43930512/article/details/91040416
[Link 2]: https://blog.csdn.net/weixin_43930512/article/details/91041396
[Link 3]: https://blog.csdn.net/weixin_43930512/article/details/91048690
[Link 4]: https://blog.csdn.net/weixin_43930512/article/details/91048917
[Link 5]: https://blog.csdn.net/weixin_43930512/article/details/91382416
[201906042101020.PNG]: /images/20220122/771e680485ac4cd4a538166a869b74da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzMDUxMg_size_16_color_FFFFFF_t_70]: /images/20220122/91d70aca8c814b55a025f775c6689750.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzMDUxMg_size_16_color_FFFFFF_t_70 1]: /images/20220122/7b16356a84294edaa222f1b40e3a739f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzMDUxMg_size_16_color_FFFFFF_t_70 2]: /images/20220122/e757bdc3eae249188f3aac1b933ee55b.png
[20190616210425838.PNG]: /images/20220122/a6a09eeb1de44ce293bf15bd386689ed.png
[20190616211356363.PNG]: /images/20220122/3246a48086004c7580cc5a604b574b62.png
[2019061621193146.PNG]: /images/20220122/e8fb8867edf04e51943a4a1a2bbe10d6.png
[Link 6]: https://blog.csdn.net/weixin_43930512/article/details/92426962
[20190604210132205.PNG]: /images/20220122/af9377541da0401f977f86938fc359e1.png
[20190604210903140.PNG]: /images/20220122/16dac9ed76214c6e9acd337b6fbe914f.png
[C_Primer_PDF]: https://pan.baidu.com/s/1Ag2oK_lYPf_xHgTSrQ6kXg