数据结构与算法知识框架计算机二级公共基础笔记
2022-10-31 10:44:21 0 举报AI智能生成
数据结构与算法知识框架计算机二级公共基础笔记
作者其他创作
大纲/内容
算法
算法的概念
1.概念
算法是指解题方案的准确而具体的描述
2.算法的特征
可行性
能够实现，能够达到预期目标
确定性
每一个步骤具有明确定义，不允许摸棱两可
有穷性
有限的时间，有限的步骤完成
足够的情报
输入的初始状态正确
算法的方法
举例法
一一举例，是否存在，有多少种可能。枚举法
归纳法
从少量特殊的情况分析找出一般的情况
递推
从已知条件出发，逐次推出所要求的中间结果和最后结果
递归
将问题逐层分解，最后归结为一些简单的问题。
分治法
也称“减半递推技术”例如二分法求解实根
回溯法
寻找线索，不断试探。
算法的复杂度
时间复杂度
是指执行算法所需的计算工作量，工作量即为所需基本运算的次数来度量
空间复杂度
是指执行算法所需的内存空间，包括算法程序，原始数据的内存空间，以及执行程序时的额外空间
数据结构
概念
<font color="#0076b3">数据结构是指相互有关联的数据元素的集合</font>
带有结构的数据元素的集合
一个是要有元素，另一个是要有关系
逻辑结构
所谓的数据的逻辑结构是指反映数据元素之间的逻辑关系的数据结构
基本关系：
前后件关系
存储结构
存储结构是指数据的逻辑结构在计算机实际存储空间的存放形式
数据的运算
基本运算
插入与删除
其他运算
查找，分类，合并，分解，复制，修改
数据结构的分类
线形结构（线形表）
条件
1.有且只有一个根节点
2.每一个结点最多有一个前件，也最多有一个后件
特征
插入和删除一个 结点后，还是线性表
非线性结构
如果一个数据结构不是线形表，则是非线形表
线性表
概念
线性表是由n个元素组成的一个有序列表，表中的每一个数据元素，除了第一个外，有且只有一个前件,除了最后一个外，有且只有一个后件
线性表的顺序存储结构
线性表中的所有元素所占的存储空间是连续的
子主题
线性表的各数据在存储空间上是按照逻辑顺序依次存放
线性表的插入运算
在插入的位置包括该位置的元素及其后面的元素往后移动
超过空间还插入元素发生的是“上溢”错误
子主题
线性表的删除运算
所谓的删除就是覆盖掉原来的数据
在空的线性表进行删除发生的是“下溢”错误
子主题
线性表的缺点
数据操作需要移动大量的数据元素
容易发生上溢错误
存储空间不方便分配
栈和队列
栈
概念
栈是一种特殊的线性表
特殊在于其删除与插入只能在一端进行
特点
先进后出
栈顶
允许插入与删除的一端
栈底
不允许插入与删除的一端
栈的顺序存储结构
跟线性表的顺序存储结构一样
子主题
子主题
入栈运算
在栈顶插入一个新的元素
退栈运算
取除栈顶的元素并赋给一个指定的变量
读栈运算
将栈顶元素赋给一个表量
队列
概念
队列也是一种特殊的线性表
特殊子在于元素总是插入到线性表的末尾，并且元素总是从线性表的头部去除（删除）
特点
先进先出
队列的存储结构
队列的顺序存储结构一般用循环队列的形式
子主题
子主题
队尾
允许插入的一端
队头
允许删除的一端
入队运算
往队列的队尾插入一个元素
退队运算
从队列的队头删除一个元素
线性链表
概念
线性表的链式存储结构称为线性链表
组成
数据域
存放数据元素值
指针域
用于存放指针
特殊结点
第一个结点
HEAD
最后一个结点
NULL或者0
存储
存储空间既可以连续又可以不连续
子主题
子主题
用途
既可以用于线性结构，有可以用于非线性结构
运算
线性链表的运算都是基于指针的操作
线性链表的插入：分配一个新节点
子主题
线性链表的删除：回收该元素的节点
子主题
循环链表
头尾相连的链表
子主题
树与二叉树
树
概念
树是一种简单的非线性结构，其有明显的层级结构，形状如树，由此而得名
子主题
根节点
没有前件的结点
叶子结点
没有后件的结点
子结点
每一个结点的后件称子结点
父结点
每一个结点的前件称父结点
结点的度
一个结点的后件个数称结点的度
树的度
所有结点中的最大的度称树的度
树的深度
树的最大层次称为树的深度
五层深度的树
存储形式
树通常用多重链表表示
公式
树中的结点数=树中所有结点的度之和+1
二叉树
概念
非空二叉树只有一个根结点，每一个结点最多有两棵子树，称左子树和右子树
性质
性质1：第k层上最多有2^(k-1)个结点
性质2：深度为m，最多的结点为2^m-1
性质3：度为0的结点数总是比度为2的结点数多1个
性质4：具有深度为n个结点数的二叉树，其深度至少是log_2 N +1
满二叉树
除最后一层外，每一层上的所有结点数都有两个子结点
子主题
完全二叉树
除最后一层外，每一层的结点数均达到最大值，并且在最后一层上只缺少右边的若干结点
子主题
存储方式
二叉树通常采用的是链式存储结构
子主题
二叉树的遍历
原则
先左后右，根据根结点的访问次序不同，分为三种
前序遍历
先访问跟结点
子主题
中序遍历
中间访问根结点
子主题
后序遍历
最后访问根结点
子主题
常用算法
查找技术
顺序查找
一般用于线性表中查找特定的元素，从第一个开始，逐个比较，直到找到，或者没有。
最坏情况次数：n
二分法查找
只适用于顺序存储的有序表（有序表是指线性表的元素按值非递减排序，允许元素相等）
最坏情况下遍历：log2(N)次
排序技术
交换排序法
概念
所谓的交换排序法是指借助数据元素之间的相互交换进行排序的一种方法
冒泡排序法
1.有多少个元素就进行多少轮的循环
2.每一轮，不断的将两个相邻的元素比较，然后交换位置，第一轮就得到了一个最值放在最后，其他元素再重复操作直到有序
3.下一轮的比较中，不再比较上一轮得到的最大值。
最坏情况的比较：n(n-1)/2次
快速排序法
取出一个元素，将大于该元素的放在一边，小于该元素的放在一边，将线性表分成了两部分，再对两边进行同样操作直到有序
示意图
子主题
最坏情况的比较：n(n-1)/2次
注意：实际过程中，快速排序法比冒泡排序法快
插入排序法
概念
所谓插入排序法是指将无序的各元素插入到有序的线性表中
简单插入法
把第一个元素当成有序表，取后面的元素，依次插入到有序表中，插入的原则是小的插到前面，大的插到后面直到有序
最坏比较：n(n-1)/2次
希尔排序法
将整个无序列表分成若干个小的子序表分别进行排序
比较：n^1.5
选择排序法
概念
选择排序法是指从整个线性表中选择一个最值，将它交换到最前面，剩余的也是同样的操作
简单选择法
扫描整个线性表，取出最小值放在前面，后续元素同样操作直到有序
比较：n(n-1)/2次
堆排序法
对于满二叉树进行选择排序，原则是跟结点最大，父结点大于子结点
比较：N*log_2 N
动态仿真表示过程：https://www.cnblogs.com/onepixel/articles/7674659.html
0 条评论
下一页
