北京邮电大学计算机学院数据结构第一章课件

PPT,a clickto unlimitedpossibilities01单击添加目录项标题02数据结构概述03数据结构基本概念04线性数据结构05非线性数据结构06图形数据结构数据结构是计算机存储和组织数据的方式数据结构包括线性结构、树形结构、图状结构和集合结构等数据结构研究的是数据的逻辑结构、物理结构和运算数据结构的目的是提高数据处理的效率和准确性线性结构数组、树形结构二叉图形结构无向集合结构集合、散列表哈希表、动态数据结构链表、栈、队列树、平衡树、堆图、有向图、网映射等散列表等动态数组、动态等等络等链表等数据结构是计算机科学的基础，是程序设计的核心数据结构决定了算法的效率和性能数据结构是解决实际问题的关键，如排序、查找、路径规划等数据结构是提高编程能力的重要途径，有助于理解程序设计的本质数据项数据的最小单位，数据元素之间的关系线性、不可再分树形、图状等数据元素数据的基本单位，数据结构的分类线性结构、由多个数据项组成树形结构、图状结构等数据项构成数据的基本数据项之间的关系数据线性关系数据项之间存单位项之间的相互联系和依赖在一对一的关系关系树形关系数据项之间存图形关系数据项之间存网状关系数据项之间存在一对多的关系在多对多的关系在复杂的相互关系线性结构元素之间存在一对一的关系树形结构元素之间存在一对多的关系图形结构元素之间存在多对多的关系集合结构元素之间没有明确的关系顺序存储将数链式存储将数索引存储通过散列存储通过据元素存储在连据元素存储在不索引表来查找数散列函数将数据元素映射到内存续的内存空间中，连续的内存空间据元素，如索引空间中，如散列如数组中，如链表文件表线性表由n个元素组成的有限序列，每个元素都有一个唯一的位置线性表的性质线性表的元素之间存在顺序关系，每个元素都有唯一的前驱和后继线性表的操作插入、删除、查找、更新等线性表的应用广泛应用于计算机科学、数学、物理等领域概念线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的数据元素优点可以快速访问任意位置的元素，实现随机存取缺点插入和删除操作需要移动大量元素，效率较低应用场景适用于频繁访问、较少插入和删除操作的场景链式存储将数据元素存放在连续的内存空间中，每个元素都有一个指针指向下一个元素优点插入和删除操作方便，不需要移动其他元素缺点查找操作需要从头开始遍历整个链表，效率较低应用场景适用于频繁插入和删除操作的场景，如队列、栈等数据结构l存储数据线性表可以用于存储数据，如数组、链表等l查找数据线性表可以用于查找数据，如二分查找、顺序查找等l排序数据线性表可以用于排序数据，如冒泡排序、快速排序等l操作数据线性表可以用于操作数据，如插入、删除、修改等定义树形数据结构是一种非线性数据结构，由节点和边组成，每个节点可以有多个子节点，但只有一个父节点性质树形数据结构具有层次结构，每个节点都有一个唯一的父节点，每个节点都可以有多个子节点特点树形数据结构具有递归性，每个节点都可以看作是一个独立的树形结构应用树形数据结构广泛应用于计算机科学、数学、生物学等领域，如二叉树、红黑树、B树等树形数据结构一种非线性数存储结构通常采用链表或数链表存储每个节点包含一个据结构，具有树形结构组进行存储数据域和一个指针域，指针域指向其子节点数组存储每个节点占据一个优缺点链表存储便于插入和应用场景树形数据结构广泛数组元素，通过索引访问子节删除，但查找效率较低；数组应用于文件系统、数据库系统、点编译器等领域存储查找效率较高，但插入和删除效率较低深度优先遍历（DFS）从根节点开始，沿广度优先遍历（BFS）从根节点开始，先添加添加着左子树一直走到底，然后返回到根节点，访问所有相邻的节点，然后再访问相邻节点标题再沿着右子树一直走到底，直到所有节点都标题的相邻节点，直到所有节点都被访问过被访问过层次遍历按照树的层次，从根节点开始，添加添加前序遍历先访问根节点，然后访问左子树，逐层访问所有节点，直到所有节点都被访问标题标题最后访问右子树过添加添加中序遍历先访问左子树，然后访问根节点，后序遍历先访问左子树，然后访问右子树，标题标题最后访问右子树最后访问根节点存储层次结构数据如文件系统、解决排序问题如堆排序、归并排目录结构等序等表示网络拓扑结构如计算机网络、解决最短路径问题如Dijkstra算电路设计等法、Floyd算法等解决搜索问题如二叉树、平衡树解决最小生成树问题如Prim算法、等Kruskal算法等定义图形数据结构是性质图形数据结构应用图形数据结构广特点图形数据结构具一种用于表示和存储图泛应用于计算机图形学、有直观、易于理解的特具有连通性、可达性、形数据的数据结构，它网络拓扑、地图绘制等点，便于人们理解和处路径长度等性质，这包括顶点、边和路径等领域理图形数据些性质对于解决图形元素问题非常重要添加项标题邻接矩阵用于表示图中顶点之间的邻接关系，适用于稠密图添加项标题邻接表用于表示图中顶点之间的邻接关系，适用于稀疏图添加项标题十字链表用于表示有向图的存储结构，可以快速找到某个顶点的所有出边和入边添加项标题邻接多重表用于表示无向图的存储结构，可以快速找到某个顶点的所有邻接顶点添加项标题边集数组用于表示无向图的存储结构，可以快速找到某个顶点的所有邻接顶点添加项标题关联矩阵用于表示带权图的存储结构，可以快速找到某个顶点的所有邻接顶点及其权值深度优先搜索（DFS）从根节点开始，广度优先搜索（BFS）从根节点开始，沿着一条路径搜索到底，然后回溯到根先访问所有相邻的节点，再访问相邻节点的相邻节点节点，再沿着另一条路径搜索到底拓扑排序按照某种顺序访问所有节点，循环检测检测图中是否存在环，如果存在，则无法进行拓扑排序使得每个节点在访问之前，其所有前驱节点都已经被访问过l图形数据结构在计算机图形学中的应用l图形数据结构在游戏开发中的应用l图形数据结构在虚拟现实中的应用l图形数据结构在图像处理中的应用。