数据结构图结构.pptxVIP

数据结构图结构2024-01-25

目录数据结构基本概念线性表及其顺序存储结构栈和队列及其应用树和二叉树及其应用图论基础与图算法设计查找与排序算法设计文件组织与外部存储管理

01数据结构基本概念

是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。数据元素一个数据元素可以由若干个数据项组成，数据项是数据不可分割的最小单位。数据项是相互之间存在一种或多种特定关系的数据元素的集合。数据结构数据与数据结构定义

原子类型结构类型抽象数据类型数据类型的操作数据类型及操作其值不可再分的数据类型。抽象数据组织及与之相关的操作。其值可以再分解为若干成分（分量）的数据类型。插入、删除、查找、排序等。

是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。定义数据抽象、数据封装。特性实现程序设计与程序实现的分离，使得设计可以在不考虑实现细节的情况下进行，从而提高了软件设计的效率和质量。作用抽象数据类型（ADT）

02线性表及其顺序存储结构

123线性表是具有n个数据元素的有限序列。线性表的定义包括初始化、插入、删除、查找、遍历等。线性表的基本操作线性表是一种抽象数据类型，可以用一个二元组来表示。线性表的抽象数据类型描述线性表定义及基本操作

03顺序存储结构的优缺点优点是存取速度快，缺点是插入和删除操作需要移动大量元素。01顺序存储结构的定义用一段地址连续的存储单元依次存储线性表的数据元素。02顺序存储结构的实现通常使用数组来实现顺序存储结构。顺序存储结构原理及实现

顺序表在多项式计算中的应用01多项式可以用一个线性表来表示，每个元素表示多项式中的一项。顺序表在稀疏矩阵中的应用02稀疏矩阵中的非零元素可以用一个线性表来表示，以节省存储空间。顺序表在图书管理系统中的应用03图书信息可以用一个线性表来表示，每个元素表示一本书的信息。顺序表应用举例

03栈和队列及其应用

010405060302栈（Stack）是一种特殊的线性数据结构，其元素的添加和移除遵循后进先出（LIFO,LastInFirstOut）的原则。栈的基本操作包括入栈（Push）：在栈顶添加元素。出栈（Pop）：移除栈顶元素并返回。查看栈顶（Peek/Top）：返回栈顶元素但不移除。判断栈是否为空（IsEmpty）：检查栈中是否有元素。栈定义及基本操作

队列（Queue）也是一种特殊的线性数据结构，其元素的添加和移除遵循先进先出（FIFO,FirstInFirstOut）的原则。队列定义及基本操作

入队（Enqueue）在队列尾部添加元素。出队（Dequeue）移除队列头部的元素并返回。队列定义及基本操作

查看队首（Peek/Front）返回队列头部的元素但不移除。查看队尾（Back）返回队列尾部的元素但不移除。判断队列是否为空（IsEmpty）检查队列中是否有元素。队列定义及基本操作

利用栈可以方便地处理算术表达式中的括号和运算符优先级问题。表达式求值在程序执行过程中，函数调用会形成一个调用栈，用于保存函数调用的上下文信息。函数调用栈和队列应用举例

浏览器的前进后退功能：通过维护两个栈，分别记录用户浏览过的页面，实现前进和后退功能。栈和队列应用举例

打印机通常使用队列来管理多个打印任务，按照先进先出的原则依次处理任务。打印任务管理操作系统中的任务调度器通常使用队列来管理待处理的任务，确保每个任务都能得到公平的处理机会。CPU任务调度在网络通信中，发送方和接收方通常使用队列来缓存待发送或接收的数据包，以确保数据的顺序传输和可靠接收。网络数据传输栈和队列应用举例

04树和二叉树及其应用

树是一种非线性数据结构，由节点和边组成，具有层次关系。树中节点的度是指该节点的子树个数，树的度是指树中所有节点的最大度数。树中节点分为根节点、叶子节点和内部节点，根节点没有前驱，叶子节点没有后继，其余节点为内部节点。树的深度是指树中节点的最大层次数，高度是指从根节点到最远叶子节点的最长路径上的节点数。树基本概念和性质

二叉树是一种特殊的树，每个节点最多只有两个子节点，分别称为左子节点和右子节点。二叉树的遍历是指按照某种规则访问二叉树中的每个节点，常见的遍历方式有前序遍历、中序遍历和后序遍历。二叉树的查找操作可以在二叉搜索树中进行，查找过程从根节点开始，根据节点值和查找值的大小关系，在左子树或右子树中继续查找，直到找到目标节点或遍历到空节点为止。二叉树的五种基本形态包括空二叉树、只有一个根节点的二叉树、只有左子树或右子树的二叉树、以及左右子树均非空的二叉树。二叉树定义及基本操作

树和二叉树应用举例表