绪论(数据结构教程课件)

绪论(数据结构教程ppt课件)目录数据结构基本概念线性表栈和队列串、数组和广义表树和二叉树图论基础与图数据结构01数据结构基本概念数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构的定义根据数据元素间关系的不同，数据结构可分为线性结构、树形结构、图形结构等。数据结构的分类数据结构定义与分类数据类型数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。数据类型与抽象数据类型算法的定义算法的特性算法设计的要求算法分析算法与算法分析01020304算法是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。有穷性、确定性、可行性、输入、输出。正确性、可读性、健壮性、效率与低存储量需求。算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。02线性表123线性表是具有n个数据元素的有限序列线性表的定义创建、初始化、销毁、判空、清空、求长度、获取元素、修改元素、插入元素、删除元素等线性表的基本操作数据类型名称、数据对象集合、操作集合等线性表的抽象数据类型描述线性表定义及基本操作顺序存储结构的定义01用一段地址连续的存储单元依次存储线性表的数据元素顺序存储结构的基本操作实现02创建、初始化、销毁、判空、清空、求长度、获取元素、修改元素等操作的实现方法顺序存储结构的优缺点03无需为表示表中元素之间的逻辑关系而增加额外的存储空间；可以快速地存取表中任一位置的元素；插入和删除操作需要移动大量元素线性表顺序存储结构链式存储结构的定义用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的链式存储结构的基本操作实现创建、初始化、销毁、判空、清空、求长度、获取元素、修改元素等操作的实现方法链式存储结构的优缺点比顺序存储结构的存储密度小；链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针链接在一起；插入和删除操作只需修改指针，不需要移动大量元素线性表链式存储结构03栈和队列栈（Stack）是一种特殊的线性数据结构，其操作只能在表的一端进行，通常称为栈顶（top）。另一端称为栈底（bottom）。栈的基本操作包括入栈（push）：在栈顶插入一个元素。出栈（pop）：删除栈顶元素并返回其值。查看栈顶（peek/top）：返回栈顶元素的值，但不删除它。判断栈是否为空（isEmpty）：检查栈中是否还有元素。栈定义及基本操作使用栈来辅助计算后缀表达式或中缀表达式的值。表达式求值括号匹配函数调用检查一个包含括号（圆括号、方括号、花括号等）的表达式中的括号是否正确匹配。在程序执行过程中，使用栈来保存函数调用的信息，如函数参数、局部变量和返回地址等。030201栈应用举例010405060302队列（Queue）是一种特殊的线性数据结构，其操作在表的两端进行。一端称为队头（front），另一端称为队尾（rear）。队列的基本操作包括入队（enqueue）：在队尾插入一个元素。出队（dequeue）：删除队头元素并返回其值。查看队头（peek/front）：返回队头元素的值，但不删除它。判断队列是否为空（isEmpty）：检查队列中是否还有元素。队列定义及基本操作使用队列来管理待打印的文件，按照先进先出（FIFO）的原则进行打印。打印任务调度在操作系统中，使用队列来管理等待CPU处理的进程或线程，根据特定的调度算法进行任务分配。CPU任务调度在网络传输或文件读写过程中，使用队列作为缓冲区，暂时存储待处理的数据，以提高处理效率。缓冲处理队列应用举例04串、数组和广义表串的基本操作包括赋值操作、连接操作、求串长、比较操作、定位操作等。串的存储结构包括顺序存储结构和链式存储结构。串定义及基本操作串模式匹配算法是指在一个主串中寻找一个子串（模式串）的位置。常见的串模式匹配算法有：朴素模式匹配算法（Brute-Force算法）、KMP算法（Knuth-Morris-Pratt算法）、BM算法（Boyer-Moore算法）等。这些算法的时间复杂度不同，其中KMP算法和BM算法是较为高效的算法。串模式匹配算法数组（Array）是一种线性表数据结构，它用一组连续的内存空间来存储一组具有相同类型的数据元素。数组的基本操作包括：存取元素、插入元素、删除元素等。数组的存储结构是顺序存储结构，可以通过下标直接访问数组中的元素。数组定义及基本操作

特殊矩阵压缩存储方法特殊矩阵是指具有特殊性质或特殊形状的矩阵，如对称矩阵、三角矩阵、稀疏矩阵等。对于这些特殊矩阵，可以采用压缩存储方法来节省存储空间和提高运算效率。常见的特殊矩阵压缩存储方法有：对称矩阵的压缩存储、三角矩阵的压缩存储、稀疏矩阵的压缩存储等。广义表（GeneralizedList）是线性表的扩展，它允许列表中的元素不仅可以是原子类型，还可以是另一个广义表。广义表的基本操作包括：创建广义表、访问广义表元素、修改广义表元素、插入元素、删除元素等。广义表的存储结构通常采用链式存储结构，每个元素可以用一个结点来表示，结点中包含元素值和指向下一个结点的指针。广义表定义及基本操作05树和二叉树当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2、…、Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。树（Tree）是n（n≥0）个结点的有限集。n=0时称为空树。在任意一棵非空树中有且仅有一个特定的称为根（Root）的结点。树定义及基本术语表示树中的元素，包括数据项及若干指向其子树的分支。结点（Node）结点拥有的子树数。结点的度（Degree）树定义及基本术语03树的度树内各结点的度的最大值。01叶子（Leaf）或终端结点度为0的结点。02非终端结点或分支结点度不为0的结点。树定义及基本术语从根开始定义起，根为第1层，根的子结点为第2层，以此类推。结点的层次（Level）树中结点的最大层次。树的深度或高度双亲在同一层的结点。堂兄弟结点如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。有序树和无序树树定义及基本术语二叉树（BinaryTree）是n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。二叉树的五种基本形态：空二叉树、只有一个根结点、根结点只有左子树、根结点只有右子树、根结点既有左子树又有右子树。二叉树定义及性质二叉树的性质在二叉树的第i层上至多有2^(i-1)个结点（i≥1）。深度为k的二叉树至多有2^k-1个结点（k≥1）。对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。01020304二叉树定义及性质先序遍历（Pre-orderTraversal）：若二叉树为空，则空操作返回；否则先访问根结点，然后先序遍历左子树，最后先序遍历右子树。中序遍历（In-orderTraversal）：若二叉树为空，则空操作返回；否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树。后序遍历（Post-orderTraversal）：若二叉树为空，则空操作返回；否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。层序遍历（Level-orderTraversal）：若二叉树为空，则空操作返回；否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。二叉树遍历方法线索二叉树是对二叉树的每个结点增设两个标志位以及一条线索而得到的。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。这里以中序线索二叉树为例来说明线索二叉树的构造方法。中序线索二叉树的构造规则是：若将二叉树的中序遍历序列中的每个结点都看作是相应指针域为空的指针，则称这些指针为线索，而指向其前驱或后继的指针称为线索指针。加上线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(ThreadedBinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。线索二叉树树转换为二叉树的规则是：每个结点的左指针指向它的第一个孩子结点；右指针指向它在树上的下一个兄弟结点；对于树的根结点来说，由于没有前一个兄弟结点，所以它的右指针指向由它的所有孩子结点构成的链表的第一个孩子结点；对于其他任何结点来说，由于它的右指针指向它在树上的下一个兄弟结点，所以它的所有孩子结点的左指针均指向它本身。这样转换后的二叉树的左子树上树和森林转换为二叉树方法06图论基础与图数据结构图(Graph)由顶点(Vertex)和边(Edge)组成的数据结构，表示对象及其之间的关系。无向图(UndirectedGraph)边没有方向的图。有向图(DirectedGraph)边有方向的图，也称为有向网络。图论基本概念与术语图论基本概念与术语任意两个顶点之间都存在路径的图。连通图(ConnectedGraph)与顶点相关联的边的数量。对于有向图，分为入度(In-degree)和出度(Out-degree)。顶点的度(Degree)从一个顶点到另一个顶点所经过的边的序列。路径(Path)连通分量(ConnectedComponent)无向图中的极大连通子图。要点一要点二强连通图(StronglyConnectedGra…有向图中任意两个顶点都存在双向路径的图。图论基本概念与术语图数据结构表示方法邻接矩阵(AdjacencyMatri…用一个二维数组表示图中顶点之间的连接关系，适用于稠密图。邻接表(AdjacencyList)用链表或数组表示每个顶点的邻居顶点，适用于稀疏图。邻接多重表(AdjacencyMult…改进邻接表，减少存储空间，方便边的删除操作。十字链表(CrossList)用于有向图的存储结构，可以方便地找到任一顶点的入边和出边。图遍历算法通过栈或队列辅助实现深度优先遍历或广度优先遍历。非递归实现沿着树的深度遍历图的节点，尽可能深地搜索图的分支。深度优先遍历(Depth-FirstSearch,…按层次遍历图的节点，先访问离根节点近的节点。广度优先遍历(Breadth-FirstSearc…普里姆算法(Prim'sAlgorithm)从某一顶点开始构建生成树，每次选择代价最小的边加入生成树中，直到所有顶点都加入生成树为止。要点一要点