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