logo资料库

数据结构知识点总结（超全）.docx

发布时间：2022-06-16 发布人：admin 分类：说明书 资料大小：15.74M 资料格式：docx 举报 版权申诉
第1页 / 共73页
第2页 / 共73页
第3页 / 共73页
第4页 / 共73页
第5页 / 共73页
第6页 / 共73页
第7页 / 共73页
第8页 / 共73页
资料共73页，剩余部分请下载后查看
    第一章 基本概念
    1.1 数据关系
    1.2 逻辑结构和物理结构
    第二章 算法
    2.1 算法特性
    2.2 算法设计的要求：
    2.3 算法时间复杂度
    2.4 算法时间复杂度
    2.5 总结
    第三章、线性表
    3.1 线性表的抽象数据类型
    3.2 线性表的顺序存储结构
    3.2.1 数组计算方法
    3.2.2 顺序存储结构的插入与删除
    3.3 线性表的链式存储结构
    3.3.1 顺序存储结构不足的解决方法
    3.3.2 线性表链式存储结构定义
    3.3 线性表的链式存储结构
    3.4 单链表的读取、插入与删除
    3.5 单链表结构与顺序存储结构的优缺点
    3.6 静态链表
    3.7 循环链表
    3.8 循环链表
    第四章 栈与队列
    4.1 栈的定义
    4.2 栈的抽象数据类型
    4.3 队列（queue）的定义
    第五章 串
    第六章 树
    6.1 树的定义
    6.2 二叉树的定义
    6.2.1 特殊二叉树
    6.2.2 二叉树的性质
    6.2.3 二叉树的存储结构
    6.3 二叉树的遍历
    6.4 树、森林、二叉树的转换
    6.4.2 森林转换为二叉树
    6.4.3 二叉树转换为树
    6.4.4 二叉树转换为森林
    6.5 树与森林的遍历
    6.6 哈夫曼树
    第七章 图
    7.1 图的定义
    7.2 图的存储结构
    7.2.1 邻接矩阵
    7.2.2 邻接表
    7.2.3 十字链表
    7.2.4 邻接多重表
    7.2.5 边集数组
    7.3 图的遍历
    7.3.1 深度优先遍历（深度优先搜索Depth_First_Search,DFS）
    7.3.2 广度优先遍历（广度优先搜索，Breadth_First_Search,BFS）
    7.4 最小生成树
    7.5 最短路径
    第八章 查找
    8.1 查找的方法
    8.2 二叉树排序
    第九章 排序
    9.1 排序的稳定性
    9.2 冒泡排序
    9.3 简单选择排序法
    9.4 直接插入排序
    9.5 希尔排序
    9.6堆排序
    9.7 归并排序
    9.8 快速排序
    第一章 基本概念 1.1 数据关系 数据项→→数据元素→→数据对象→→数据 数据项：数据项组成数据元素，数据项是不可分割的最小单位 数据元素：组成数据的基本单位 数据对象：性质相同的数据元素的集合 数据：描述客观事物的符合 数据结构：相互之间存在一种或多种特定关系的数据元素的集合 1.2 逻辑结构和物理结构 逻辑结构：数据对象中数据元素的相互关系  逻辑结构包括：集合结构、线性结构、树形结构、图形结构 物理结构：数据的逻辑结构在计算机中的存储形式，也就是将数据元素存储到存储器  物理结构包括：顺序存储结构、链式存储结构  顺序存储结构：把数据元素存放在地址连续的存储单元，数据间逻辑关系和物理关 系是一样的  链式存储结构：把数据元素存储到任意存储单元中，这些单元可以是连续的也可以 是不连续的 链式存储很灵活，不用在意存储的位置，只要有一个存放地址的指针就好了。 第二章 算法 算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，且每条指令 表示一个或多个操作。
    2.1 算法特性 输入、输出、有穷性、确定性、可行性  输入输出：算法具有输入和输出  有穷性：算法不会出现无限循环，并且每个步骤可在可接受时间内完成  确定性：每个步骤都有确定的含义  可行性：算法的每一步都是可行的，也就是每一步都能够通过执行的有限次完成 2.2 算法设计的要求：  正确性  可读性  健壮性  时间效率高、存储量低 2.3 算法时间复杂度 在进行算法分析时，语句总的执行次数 T(n)是关于问题规模 n 的函数，进而分析 T(n) 随着 n 的变化情况而确定 T(n)的数量级。 时间复杂度，也就是算法的时间度量，表示岁问题规模 n 的增大，算法执行时间的增长 率和 f(n)的增长率相同。 一般情况下，随着 n 的增大，T(n)增大最慢的方法是最优算法 用大写的 O()来体现算法复杂度的记法，称为大 O 法。 如何推导时间复杂度： 1、常数阶：O(1) 2、线性阶：O(n) 关键在于分析循环结构内部情况，下面程序复杂度为 O(n) int i for (i=0;i
    //时间复杂度为 O（1）的程序 } 3、对数阶：O(log n) int count=1; while(countx=log2n2x=n−>x=log2n，所以时间复杂度为 O(log n) 4、平方阶：O(n^2) int i,j; for(i=0;i
    2.4 算法时间复杂度 2.5 总结
    第三章、线性表 线性表（List）：零个或多个数据元素的有限序列  元素之间是有顺序的：第一个元素无前驱，最后一个元素无后继，其他元素都有前驱和后 继  线性表强调是有限的 数学表达： 3.1 线性表的抽象数据类型
    3.2 线性表的顺序存储结构 顺序存储结构：用一段地址连续的存储单元一次存储线性表的数据元素 线性表存储结构代码： 顺序存储结构的三个属性：  存储空间的起始位置：数组 data，它的存储位置就是存储空间的存储位置  线性表的最大存储容量：数组长度 MaxSize
     线性表的当前长度：length 3.2.1 数组计算方法 数据元素的序号和存放它的数组下标之间的对应关系： 第 i+1 个数据元素和第 i 个数据元素存储位置的关系： LOC(ai+1)=LOC(ai)+cLOC(ai+1)=LOC(ai)+c(c 为每个数据元素所占存储单元) −1)∗c 第 i 个数据元素可以由 a1 推出：LOC(ai)=LOC(a1)+(i−1)∗cLOC(ai)=LOC(a1)+(i 线性表的存取时间性能为：O(1) 3.2.2 顺序存储结构的插入与删除 （1）获取元素 时间复杂度为 O(1)O(1) （2）插入
    （3）删除 （4）时间复杂度  如果插入最后一个位置，或删除最后一个位置，时间复杂度为 O(1)O(1)  如果插入第一个位置，或删除第一个元素，时间复杂度为 O(n)O(n)  平均的情况：插入第 i 个位置，或删除第 i 个元素，需要移动 n-i 个元素，根据概率原 理，每个位置插入或删除可概率是相同的，所以最终平均移动次数和最中间那个元素 的移动次数相等为 n−1nn−1n，所以时间复杂度还是 O(n)O(n)  总结：读取的时候，复杂度为 O(1)O(1)，插入或删除复杂度为 O(n)O(n)，说明其适 合元素个数不太变换，而存储操作更多的数据。 （5）线性表顺序存储结构的优缺点
    分享到：
    赞 收藏

    相关推荐

    资料库

    行业

    共收录7266份资料，累计15个分类，关注成员有19位，主要包括：物流,旅游,餐饮零售,网络游戏,咨询,金融,电子政务,外包,教育,制造,医疗,嵌入式,互联网,交通,电信

    热门标签

    物流 旅游 餐饮零售 网络游戏 咨询 金融 电子政务 外包 教育 制造 医疗 嵌入式 互联网 交通 电信

    最新资料