数据结构严蔚敏课件第6章

数据结构严蔚敏课件第章6•绪论•线性表•栈和队列•树和图•查找和排序01绪论数据结构课程的重要性数据结构是计算机科学和信息技术专业的重要基础课程，是计算机科学与技术专业学科的核心课程之一数据结构课程主要研究数据的逻辑结构、物理结构以及基本操作，为后续的算法设计与分析、操作系统、编译原理等课程提供必要的基础数据结构课程对于培养学生的数据抽象思维、问题解决能力以及软件开发能力具有重要意义数据结构的基本概念数据数据元素数据项数据结构数据的基本单位，一个数据元素中的一个具体数据元素之间的相互关数据是信息的符号表示，数据元素可以由若干个单位，是数据的最小单系，这种关系反映了客是计算机处理的对象数据项组成位观事物的内在联系数据结构的分类010203线性结构树形结构图形结构线性结构是最基本的数据树形结构是一种层次化的图形结构是一种复杂的网结构，包括线性表、栈、数据结构，包括二叉树、状数据结构，包括图、有队列等多叉树等向图、无向图等02线性表线性表的定义和基本操作线性表的定义线性表是一种具有n个元素的有限序列，每个元1素都有一个唯一的下标，下标从0开始递增线性表的基本操作插入、删除、查找、修改等2线性表的特点元素之间是一对一的关系，即每个元素只有一个3前驱和一个后继线性表的顺序存储结构顺序存储结构的定义将线性表中的元素按照逻辑顺序依次存储在一片连续的存储单元中顺序存储结构的优点存取速度快，时间复杂度为O1顺序存储结构的缺点需要预先分配存储空间，会造成空间浪费；插入和删除操作需要移动大量元素，时间复杂度较高线性表的链式存储结构链式存储结构的定义链式存储结构的缺点将线性表中的元素按照逻辑顺序存储在一系列离散的存储单元中，每个元存取速度较慢，时间复杂度为On；素占用一个存储单元，并利用指针链需要额外的空间来存储指针接相邻元素链式存储结构的优点无需预先分配存储空间，可以动态地扩展和收缩；插入和删除操作只需修改指针，时间复杂度较低03栈和队列栈的定义和基本操作定义栈是一种特殊的线性表，只允许在表的一端进行插入和删除操作基本操作push（入栈）、pop（出栈）、p ee k（查看栈顶元素）、isEmpty（判断栈是否为空）等栈的存储结构顺序存储结构使用数组实现，通过数组下标来定位元素，时间复杂度为O1链式存储结构使用链表实现，通过指针来链接元素，时间复杂度为O1队列的定义和基本操作定义队列是一种特殊的线性表，只允许在表的一端进行插入操作，在另一端进行删除操作基本操作enqueue（入队）、dequeue（出队）、isEmpty（判断队列是否为空）等队列的存储结构顺序存储结构使用数组实现，通过数组下标来定位元素，时间复杂度为On链式存储结构使用链表实现，通过指针来链接元素，时间复杂度为O104树和图树的定义和基本操作树的定义树的分类树的遍历树的插入和删除树是由节点和边组成的数据结根据节点的度数，树可以分为树的遍历是指按照某种顺序访在树中插入和删除节点需要遵构，其中节点表示对象，边表二叉树、三叉树、多叉树等问树中的节点，可以分为前序循一定的规则，以保证树的完示对象之间的关系树是一种根据节点是否有分支，树可以遍历、中序遍历和后序遍历整性层次结构，其中每个节点可以分为有序树和无序树有多个子节点，但只能有一个父节点树的存储结构链式存储结构每个节点包含指向其子节点的指针，顺序存储结构形成一个链表结构链式存储结构适用于任意结构的树将树中的节点按照层次顺序存储在数组中，每个节点占用固定数量的存储单元顺序存储结构适用于完全二叉树散列存储结构将树中的节点按照散列函数映射到哈希表中，以加快查找速度散列存储结构适用于需要快速查找的应用场景图的定义和基本操作图的定义图的分类图是由节点和边组成的数据结构，其中节根据边的方向性，图可以分为有向图和无点表示对象，边表示对象之间的关系图向图根据节点的度数，图可以分为稠密是一种无向、有向或混合型的数据结构图和稀疏图图的遍历图的连通性图的遍历是指按照某种顺序访问图中的节图的连通性是指从一个节点到另一个节点点和边，可以分为深度优先遍历和广度优是否存在路径，可以分为强连通图、单向先遍历连通图和连通图等图的存储结构邻接矩阵使用一个矩阵来表示图中节点之间的关系，矩阵中的元素表示两个节点之间是否有边相连邻接矩阵适用于稠密图邻接表使用链表来表示图中节点之间的关系，每个节点包含一个链表，链表中的元素表示与该节点相连的节点邻接表适用于稀疏图05查找和排序查找的基本概念和方法查找的基本概念查找是从数据结构中找出满足特定条件元素的过程查找操作的效率取决于数据结构的选择和查找算法的优劣哈希查找线性查找利用哈希函数将关键字转化为数据结构中从数据结构的第一个元素开始，逐个比较，的位置信息，直接访问该位置进行查找直到找到目标元素或遍历完整个数据结构分块查找二分查找将数据结构分成若干块，每块内部有序，适用于有序数据结构，通过将数据结构分通过块首元素进行索引，再在块内进行查成两半，每次比较中间元素与目标元素的找大小，缩小查找范围排序的基本概念和方法选择排序每次从未排序部分找到最小（或冒泡排序最大）元素，将其放到已排序部插入排序分的末尾将未排序部分第一个元素与已排通过相邻元素比较和交换，使得序部分元素逐个比较，找到合适较大的元素逐渐向数组尾部移动的位置插入排序的基本概念快速排序选择一个基准元素，将数组分为排序是将数据结构中的元素按照两部分，一部分小于基准，一部某种顺序重新排列的过程排序分大于基准，递归地对两部分进操作的效率取决于排序算法的优行排序劣查找和排序的性能分析时间复杂度空间复杂度稳定性分析查找和排序算法在不分析查找和排序算法所需分析查找和排序算法是否同情况下的时间复杂度，的额外空间，如递归过程保持相等元素的相对顺序如最好、平均和最坏情况中所需的栈空间等稳定性对于某些应用场景下的时间复杂度非常重要THANK YOU。