虎丘苏州网站建设,简单商城源码,wordpress加载速度太慢,wordpress下雪内容来源青岛大学数据结构与算法课程#xff0c;链接#xff1a;数据结构与算法基础#xff08;青岛大学-王卓#xff09;_哔哩哔哩_bilibili
绪论
数据结构概述
数据结构和算法的定义#xff1a;我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存…内容来源青岛大学数据结构与算法课程链接数据结构与算法基础青岛大学-王卓_哔哩哔哩_bilibili
绪论
数据结构概述
数据结构和算法的定义我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器内存中以及在此基础上为实现某个功能比如查找某个元素删除某个元素对所有元素进行排序而执行的相应操作这个相应的操作也叫算法 数据结构 个体 个体的关系
算法 对存储数据的操作 算法
解题的方法和步骤
算法的描述 自然语言英语中文 流程图传统流程图NS流程图 伪代码类语言类C语言 程序代码C语言程序java语言程序等
传统流程图 NS流程图 算法特性 有穷性一个算法必须总在执行有穷步之后结束且每一步都在有穷时间内完成 确定性算法中的每一条指令必须有确切的含义没有二义性在任何条件下只有唯一的一条执行路径即对于相同的输入只能得到相同的输出 可行性算法是可执行的算法描述的操作可以通过已经实现的基本操作执行有限次来实现 输入一个算法有零个或多个输入 输出一个算法有零个或多个输出 算法设计的要求 正确性 可读性 健壮性 高效性 衡量算法的标准时间复杂度、空间复杂度、难易程度和健壮性
时间复杂度记作
大概程序要执行的次数而非执行的时间
最坏时间复杂度指在最坏的情况下算法的时间复杂度
平均时间复杂度指在所有可能输入实例在等概率出现的情况下算法的期望运行时间
最好时间复杂度指在最好的情况下算法的时间复杂度 大O加法规则和乘法规则计算算法的时间复杂度 时间复杂度 按数量级递增顺序为
空间复杂度记作
算法执行过程中大概所占用的最大内存
算法要占用的空间 算法本身要占据的空间输入/输出指令常数变量等 算法要使用的辅助空间(临时变量的空间) 数据结构的地位特点
数据结构是软件中最核心的课程 程序 数据的存储 数据的操作 可以被计算机执行的语言 预备知识
地址内存单元的编号从0开始的非负整数范围0—FFFFFFFF[0—4G-1])
指针 指针就是地址地址就是指针 指针变量就是存放内存单元地址的变量 指针的本质是一个操作受限的非负整数
分类 基本类型的指针 指针和数组的关系
下标和指针的关系a[i] *(ai) 动态内存的分配和释放 需要加载头文件stdlib.h
C动态内存分配和释放 C中的参数传递 参数为引用类型是与C语言的不同之处 1传递引用给函数与传递指针的效果是一样的形参变化实参也发生变化
2引用类型作形参在内存中并没有产生实参的副本它直接对实参操作而一般变量作参数形参与实参就占用不同的存储单元所以形参变量的值是实参变量的副本。因此当参数传递的数据量较大时用引用比用一般变量传递参数的时间和空间效率都好。
3指针参数虽然也能达到与使用引用的效果但在被调函数中需要重复使用“指针变量名”的形式进行运算这很容易产生错误且程序的阅读性较差另一方面在主调函数的调用点处必须用变量的地址作为实参。 逻辑结构 集合结构 线性结构 树形结构 图状结构
存储结构 顺序结构 链式结构 索引结构 散列结构 抽象数据类型 数据对象 数据关系 基本操作
抽象数据类型 数据的逻辑结构抽象运算(运算的功能描述) 如何定义抽象数据类型
例圆的抽象数据类型 抽象数据类型的实现 线性表
线性表的定义和特点
线性表是具有相同特性的数据元素的一个有限序列 线性表的逻辑特征 案例
一元多项式的运算 图书信息管理系统 线性表的类型定义(线性表的抽象数据类型) 线性表的初始化销毁一个线性表重置线性表 判断线性表是否为空表求一个线性表的长度 获取元素查找和定位 求一个元素的前驱求一个元素的后继 在线性表中插入一个元素 删除第i个的元素对每个元素遍历 线性表的顺序表现和实现
线性表的顺序表示又称为顺序存储结构或顺序映像
顺序存储定义把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构
线性表的第 1 个数据元素 a1 的存储位置称作线性表的起始位置或基地址
线性表顺序存储结构占用一片连续的存储空间
为每个元素的存储单元
顺序表的特点以物理位置相邻表示逻辑关系任一元素均可随机存取
线性表定义模板 线性表的初始化 线性表的销毁 求线性表的长度和判断线性表是否为空 顺序表的取值 顺序表的查找算法顺序查找法 含有 个记录的表
顺序表的插入算法 平均移动次数
顺序表的删除算法 平均移动次数
顺序表的优缺点 线性表的链式表示和实现
线性表的链式表示又称为非顺序映像或链式映像
用一组物理位置任意的存储单元来存放线性表的数据元素。
这组存储单元既可以是连续的也可以是不连续的甚至是零散分布在内存中的任意位置上的
链表中元素的逻辑次序和物理次序不一定相同
单链表是由头指针唯一确定因此单链表可以用头指针的名字来命名
结点数据元素的存储映像
各结点由两个域组成 数据域存储元素数值数据 指针域存储直接后继结点的存储位置
链表n 个结点由指针链组成一个链表。它是线性表的链式存储映像称为线性表的链式存储结构
单链表结点只有一个指针域的链表称为单链表或线性链表
带头结点的单链表非空表和空表 单链表的存储结构 定义链表L通常用LinkList L定义结点指针通常用LNode *p
单链表的初始化即构造一个空表 判断一个链表是否为空 单链表的销毁 单链表的清空 求单链表的表长 单链表的取值取单链表中第 i 个元素的内容 单链表的查找查找指定数据的位置
1.返回地址 2.返回位置序号 平均时间效率为
单链表的插入在第i个结点前插入新结点 因为链表不需要移动元素只需要修改指针一般情况下时间复杂度为
单链表的删除删除第 i 个结点 因为链表不需要移动元素只需要修改指针一般情况下时间复杂度为
但是如果要在单链表中进行前插或删除操作由于要从头查找前驱结点所耗时间复杂度为
单链表的建立 头插法 时间复杂度为 尾插法 时间复杂度为 双链表结点有两个指针域的链表称为双链表
双向链表的结构定义 双向链表结构的对称性及操作 双向链表的插入 双向链表的删除 循环链表首尾相接的链表称为循环链表
带尾指针的循环链表 两个带尾指针的循环链表的合并 时间复杂度为
头指针是指向链表中第一个结点的指针
首元节点是指链表中存储第一个数据元素 a1 的结点
头结点是在链表的首元结点之前附设的一个结点 链表的特点 链式存储结构的优缺点 存储密度 顺序表和链表的比较 线性表的应用
线性表的合并 有序表的合并 用顺序表实现有序表的合并 用链表实现有序表的合并
案例分析与实现
一元多项式的运算用线性表只存系数指数为底标i
稀疏多项式的运算用顺序表存系数和指数但空间浪费较大用链表来实现
图书信息管理顺序表或链表 栈和队列
栈和队列的定义和特点
栈和队列是限定插入和删除只能在表的“端点”进行的线性表
栈只能插入和删除最后一个元素后进先出
队列只能插入最后一个元素和只能删除第一个元素先进先出
栈和队列是线性表的子集是插入和删除位置受限的线性表 栈的定义和特点
栈stack是一个特殊的线性表是限定仅在一端通常是表尾进行插入和删除操作的线性表又称为后进先出的线性表简称LIFO结构
表尾即an端称为栈顶Top表头a1端称为栈底Base
插入元素到栈顶即表尾的操作称为入栈
从栈顶即表尾删除最后一个元素的操作称为出栈
“入”压入PUSHx “出”弹出POPy 队列的定义和特点队列queue是一种先进先出的线性表在表一端插入表尾在另一端表头删除简称FIFO结构
栈的应用 进制转换余数先进后出 括号匹配的检验 表达式求值算符优先算法 队列的应用
舞伴问题
栈的表示和操作的实现
栈的顺序存储---顺序栈
栈的链式存储---链栈 顺序栈 Top指针指向栈顶元素之上的下标地址 Base指针指向栈底元素在顺序表中的位置 Stacksize表示栈可使用的最大容量 上溢栈已经满又要压入元素 下溢栈已经空还要弹出元素
顺序栈的表示 顺序栈的初始化 顺序栈的销毁 判断顺序栈是否为空栈 求顺序栈的长度 清空顺序栈 顺序栈的入栈 顺序栈的出栈 链栈 链栈是运算受限的单链表只能在链表头部进行操作 链表的头指针就是栈顶 不需要头结点 基本不存在栈满的情况 空栈相当于头指针指向空 插入和删除仅在栈顶处执行
链栈的表示链栈的指针域指针的方向与单链表中指针的方向相反 链栈的初始化 判断链栈是否为空 链栈的入栈 链栈的出栈 取栈顶元素 栈与递归
递归二叉树广义表斐波那契数列求阶乘迷宫问题Hanoi塔问题
递归问题——用分治法求解
分治法对于一个较为复杂的问题能够分解成几个相对简单的且解法相同或类似的子问题来求解
递归的优缺点 尾递归-循环结构 单向递归-循环结构 队列的表示和操作的实现
队列的存储结构为链队或顺序队常用循环顺序队
真溢出在顺序队列中由于数组空间不够而产生的溢出叫真溢出
假溢出顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出 顺序队列
顺序队列循环队列的表示 循环队列 循环队列解决队满队空时判断方法——少用一个元素空间 循环队列的初始化 求循环队列的长度 循环队列的入队 循环队列的出队 取对头元素 链队
链队列的类型定义 链队列的初始化 链队列的销毁 链队列的入队 链队列的出队 求链队列的对头元素 串、数组和广义表
串的定义
串——零个或多个任意字符组成的有限序列
真子串是指不包含自身的所有子串
主串包含子串的串相应地称为主串
字符位置字符在序列中的序号为该字符在串中的位置
子串位置子串第一个字符在主串中的位置
空格串由一个或多个空格组成的串与空串不同
所有的空串都是相等的
串的类型定义存储结构及其运算
顺序串
串的顺序存储结构 链串
串的链式存储结构 串的模式匹配算法
算法目的确定主串中所含子串模式串第一次出现的位置
算法种类 BF算法穷举法重点掌握 KMP算法速度快
BF算法算法思路是从主串S的每一个字符开始依次与子串T的字符进行匹配
时间复杂度 KMP算法主串S的指针i不必回溯提高算法效率
时间复杂度提高到 Next[j]求法 Next函数的改进 数组
多维数组 以行序为主序cJava
以列序为主序
特殊矩阵的压缩存储为多个相同的非零元素只分配一个存储空间对零元素不分配空间对称矩阵对角矩阵三角矩阵稀疏矩阵等
稀疏矩阵矩阵中非零元素的个数较少一般小于5%
对称矩阵将上三角或下三角矩阵存入一维数组中数组的下标表示该数前面还有多少数
三角矩阵 对角矩阵 稀疏矩阵 三元组法ijai存储各非零元素的值行列位置以及总行数总列数以及非零元素的个数 十字链表两个头指针一个行的头指针一个列的头指针两个指针域一个指向该数同一列的下个数另一个指向该数同一行的下个数
广义表 Fa,F递归广义表
广义表的性质 广义表和线性表的区别 广义表的基本运算 树和二叉树
树和二叉树的定义
树型结构 树的定义递归的定义 树的表示方式; 树的基本术语 二叉树的定义
二叉树的结构最简单规律性最强
所有树都能转为唯一对应的二叉树不失一般性 二叉树和树的区别 思考3个结点的二叉树有5种形态3个结点的树有2种形态
二叉树的5种基本形态 案例
数据压缩问题哈夫曼树 利用二叉树求表达式的值 二叉树的性质和存储结构 第 i 层至少有1个结点 深度为 k 时至少有 k 个结点 满二叉树 满二叉树在同样深度的二叉树中结点个数最多
满二叉树在同样深度的二叉树中叶子结点个数最多
完全二叉树 二叉树的顺序存储适合满二叉树和完全二叉树 二叉树的链式存储 如果经常操作左右孩子二叉链表 在 n 个结点的二叉链表中有 (n1) 个空指针域 如果经常操作双亲三叉链表
遍历二叉树和线索二叉树
遍历二叉树:顺着某一条搜索路径巡防二叉树中的结点使得每个结点均被访问一次而且仅被访问一次 二叉树求算术表达式3种遍历 时间复杂度 空间复杂度 先序遍历算法实现 中序遍历算法实现 后序遍历算法实现 中序遍历非递归算法栈 二叉树的层次遍历算法队列 二叉树的建立空用#表示 复制二叉树 计算二叉树深度 计算二叉树结点总数 计算二叉树叶子结点数 线索二叉树 先序线索二叉树 线索二叉树增设头结点 树和森林
树的存储结构 双亲表示法操作经常要找双亲 孩子链表经常操作孩子 带双亲的孩子链表 孩子兄弟表示法二叉树表示法二叉链表表示法
树与二叉树的交换 将树转化成二叉树 将二叉树转换成树 森林与二叉树的转化 树的遍历 先序遍历 后序遍历 层次遍历 森林的遍历 先序遍历 中序遍历
哈夫曼树及应用
判断树用于描述分类过程的二叉树
哈夫曼树的基本概念 哈夫曼树的构造算法贪心算法思想 哈夫曼树构造算法的实现 哈夫曼编码
前缀码 哈夫曼编码 哈夫曼编码的算法实现 文件的编码和解码
编码 解码 堆 堆必须是一棵完全二叉树
堆的第二性质堆序性根据堆序性可以把堆分为两类分别为大根堆和小根堆在大根堆中每个父节点元素都要大于他的子节点元素在小根堆中每个父节点元素都要小于他的子节点元素
堆的储存 若父节点为i则左子节点下标为2i1右子节点下标为2i2
堆的基本操作上滤和下滤
下滤将根节点下移的操作 上滤将子节点上移的操作
堆排序 堆的建立将无序序列转化为堆 堆排序算法 时间复杂度为 不管最好还是最坏时间复杂度都一样
空间复杂度为 不稳定的排序方式 图
图的定义和基本术语 图的存储结构 邻接矩阵表示法 无向图的邻接矩阵表示法 有向图的邻接矩阵表示法 网即有权图的邻接矩阵表示法 邻接矩阵的存储表示 采用邻接矩阵表示法创建无向网 邻接矩阵的空间复杂度为 邻接表
邻接表表示法链式 无向图 有向图 图的邻接表存储表示 采用邻接表表示法创建无向网 邻接矩阵多用于稠密图而邻接表多用于稀疏图 十字链表对有向图邻接表的缺点求结点的度困难的改进 邻接多重表对无向图邻接表的缺点每条边都要存储两遍的改进 图的遍历
深度优先搜索DFS 采用邻接矩阵表示图的深度优先搜索遍历 广度优先搜索BFS 按广度优先非递归遍历连通图 图的应用
1最小生成树 MST性质 构造最小生成树方法一普里姆Prim算法 普里姆Prim算法时间复杂度为 n为顶点数适合于稠密图
构造最小生成树方法二克鲁斯卡尔Kruskal算法 克鲁斯卡尔Kruskal算法时间复杂度为 e为边数适合于稀疏图 2最短路径 单源最短路径——用Dijkstra迪杰斯特拉算法 Dijkstra算法时间复杂度为 所有顶点间的最短路径—— Floyd弗洛伊德算法 3拓扑排序
有向无环图无环的有向图简称DAG图 AOV网和AOE网AOV网解决拓扑排序AOE网解决关键路径 AOV网的特点 拓扑排序 4关键路径 关键路径路径长度最长的路径 找关键活动 关键活动构成的路径就是关键路径
