《数据结构(线性表、树、图)PPT》由会员分享，可在线阅读，更多相关《数据结构(线性表、树、图)PPT（56页珍藏版）》请在金锄头文库上搜索。
1、 数据结构数据结构第八章第八章第八章第八章 数据结构数据结构数据结构数据结构v数据结构概要数据结构概要1.数据结构数据结构定义定义：指数据元素的集合及元素之间的关系和构造方法，可以用二元组指数据元素的集合及元素之间的关系和构造方法，可以用二元组表示为：表示为：B=（A，R），其中），其中A是数据元素的非空有限集合，是数据元素的非空有限集合，R是是定义在定义在A上的关系的非空有限集合上的关系的非空有限集合。2.要达到的要达到的目标目标：(1)从问题入手，分析和研究数据结构的特性，选择适当的逻辑结构、存从问题入手，分析和研究数据结构的特性，选择适当的逻辑结构、存储结构及相应的操作方法。储结构及相应
2、的操作方法。(2)并掌握时间复杂度和空间复杂度的概念。并掌握时间复杂度和空间复杂度的概念。3. 按逻辑关系按逻辑关系分类分类线性结构线性结构(包括线性表、栈、队列、数组、串等包括线性表、栈、队列、数组、串等)非线性结构非线性结构(树、图树、图) 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构v一、线性表一、线性表最常见的一种线性结构，有两种存储方法：顺序存储和链式存储最常见的一种线性结构，有两种存储方法：顺序存储和链式存储1、定义定义：N个元素的有限序列，个元素的有限序列，n0，通常表示为（，通常表示为（a1,a2,an）2、特点特点：元素集合中存在唯
3、一称作元素集合中存在唯一称作“第一个第一个”和唯一和唯一“最后一个最后一个”元素，除第一个元素，除第一个元素外，每个元素均只有一个直接前驱；除最后一个元素外，序列中元素外，每个元素均只有一个直接前驱；除最后一个元素外，序列中的每个元素只有一个直接后继。的每个元素只有一个直接后继。3、存储结构存储结构：顺序存储结构顺序存储结构含义：用一组连续的存储单元存放线性表中的数据元素。含义：用一组连续的存储单元存放线性表中的数据元素。特点：逻辑相邻的元素，物理位置也相邻。特点：逻辑相邻的元素，物理位置也相邻。优点和缺点：存取方便，插入删除操作需要移动大量元素。优点和缺点：存取方便，插入删除操作需要移动大量
4、元素。 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构. 链式存储结构链式存储结构含义：含义： 存储数据元素的同时必须存储元素之间的关系。用节点来存储数据元素，存储数据元素的同时必须存储元素之间的关系。用节点来存储数据元素，节点地址可以连续，也可以不连续。节点地址可以连续，也可以不连续。节点结构：节点结构：节点的插入和删除操作节点的插入和删除操作 插入操作插入操作 删除操作删除操作 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构4.其他几种链表结构其他几种链表结构：双向链表：双向链表： 每个节点包含两个指针，分
5、别指出当前节点元素的直接前驱和直接每个节点包含两个指针，分别指出当前节点元素的直接前驱和直接后继。后继。循环链表：循环链表：静态链表：静态链表： 借助数组来描述线性表的链式存储结构借助数组来描述线性表的链式存储结构 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构v二、栈和队列二、栈和队列1. 栈栈定义定义只能通过它的一端来实现数据存储和检索的只能通过它的一端来实现数据存储和检索的线性结构，也称为后进先出（或先进后出）的线性结构，也称为后进先出（或先进后出）的线性表。线性表。基本运算基本运算初始化栈：初始化栈：InitStack(S)判栈空判栈空: St
6、ackEmpty入栈入栈:Push(S,x)出栈出栈:Pop(S)读栈顶元素读栈顶元素:Top(s)存储结构存储结构顺序存储顺序存储：（顺序栈）指用一组地址连续的存储单元依次存储自栈：（顺序栈）指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针顶到栈底的数据元素，同时附设指针top指示栈顶元素的位置。指示栈顶元素的位置。 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构链式存储链式存储（链栈）：为了克服（链栈）：为了克服顺序栈可能存在上溢的不足，采顺序栈可能存在上溢的不足，采用钻链表作为存储结构的栈。用钻链表作为存储结构的栈。栈的应用
7、：表达式求值，括号匹配，递归转非递归。栈的应用：表达式求值，括号匹配，递归转非递归。2. 队列队列定义：是一种先进先出（定义：是一种先进先出（FIFO）的线性表，只允许在表的一端插入元素，）的线性表，只允许在表的一端插入元素，表的另一端删除元素。表的另一端删除元素。基本运算：基本运算： (1)初始化队初始化队 InitQueue(Q) (2)判队空判队空 Empty(Q) (3)入队入队 EnQueue(Q,x) (4)出队出队 DeQueue(Q) (5)读队头元素读队头元素 FrontQue(Q) 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构队列
8、的存储结构队列的存储结构顺序存储（顺序队列）顺序存储（顺序队列） 利用一组地址连续的存储单元存放队列中的元素，同时设置队头指针和队尾利用一组地址连续的存储单元存放队列中的元素，同时设置队头指针和队尾指针，分别表示当前的队首元素和队尾元素。指针，分别表示当前的队首元素和队尾元素。 思考思考:(1)为什么要引入为什么要引入循环队列？循环队列？ (2)什么叫假溢出？如何形成的？什么叫假溢出？如何形成的？链式存储（链队列）链式存储（链队列）队列的应用：队列的应用：常用于需要排队的场合：比如操作系统中处理打印任务，离散事件的计算模常用于需要排队的场合：比如操作系统中处理打印任务，离散事件的计算模拟等。拟
9、等。 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构3 串串 即字符串，是一种特殊的线性表，它的数据元素仅由一个字符组成。即字符串，是一种特殊的线性表，它的数据元素仅由一个字符组成。串的串的定义定义是仅由字符构成的有限序列，是取值范围受限的线性表。一般记为：是仅由字符构成的有限序列，是取值范围受限的线性表。一般记为：S=a1a2an，其中，其中S是串名，单引号括起来的字符序列是串值。是串名，单引号括起来的字符序列是串值。几个相关的几个相关的基本概念基本概念空串：长度为零的串，不包含任何字符。空串：长度为零的串，不包含任何字符。空格串：由一个或多个空格组
10、成的串。空格串：由一个或多个空格组成的串。子子串串：由由串串中中任任意意长长度度的的连连续续字字符符构构成成的的序序列列称称为为子子串串。空空串串是是任任意意串串的的子串。子串。串相等：两个串长度相等，且对应位置上的字符也相同。串相等：两个串长度相等，且对应位置上的字符也相同。串比较：比较大小时，以串比较：比较大小时，以ASCII码值作为依据。码值作为依据。基本操作基本操作赋值赋值strAssign(s,t): 将串将串t赋给串赋给串s连接连接Concat(s,t) : 串串t接续在串接续在串s的尾部，形成一个新串。的尾部，形成一个新串。 数据结构数据结构第一部分：线性结构第一部分：线性结构第
11、一部分：线性结构第一部分：线性结构求串长求串长StrLength(s)串比较串比较StrCompare(s,t) 返回值返回值-1、0、1分别表示分别表示st求子串求子串SubString(s,start,len)串的串的存储结构存储结构静态存储静态存储(即串的顺序存储结构即串的顺序存储结构) 用一组地址连续的存储单元来存储串值的字符序列。（在程序设计语言中可用一组地址连续的存储单元来存储串值的字符序列。（在程序设计语言中可借助字符数组定义串的存储空间）。借助字符数组定义串的存储空间）。链式存储链式存储 用链表存储串中的字符，每个节点中可以存储一个字符，也可以存储多个用链表存储串中的字符，每个
12、节点中可以存储一个字符，也可以存储多个字符，注意存储密度问题字符，注意存储密度问题,因为它直接影响到串和处理效率。因为它直接影响到串和处理效率。串的串的模式匹配模式匹配即子串的定位操作，是各种串处理中最重要的运算之一。有以下两种算法：即子串的定位操作，是各种串处理中最重要的运算之一。有以下两种算法：（1）朴素模式匹配算法）朴素模式匹配算法基本思想：基本思想：P432（2）改进的模式匹配算法）改进的模式匹配算法基本思想：基本思想：P433 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构4 数组、矩阵和广义表数组、矩阵和广义表（1）数组）数组定义定义：线性
13、表的元素又是一个线性表，是定长线性表在维数上的一个扩张。：线性表的元素又是一个线性表，是定长线性表在维数上的一个扩张。特点特点： .数据元素数目固定数据元素数目固定 .数据元素具有相同数据类型数据元素具有相同数据类型 .数据元素的下标关系具有上下界的约束且下标有序数据元素的下标关系具有上下界的约束且下标有序两个两个基本运算基本运算 其一：给定一组下标，存取相应的数据元素；其一：给定一组下标，存取相应的数据元素； 其二：给定一组下标，修改相应的数据元素中某个数据项的值。其二：给定一组下标，修改相应的数据元素中某个数据项的值。存储结构存储结构由于数组一般不作插入和删除运算，所以数组中数据元素个数和
14、元素之间的由于数组一般不作插入和删除运算，所以数组中数据元素个数和元素之间的关系固定不变，因此适合采用顺序存储结构。关系固定不变，因此适合采用顺序存储结构。 .二维数组的存储方式有两种：二维数组的存储方式有两种： 行优先：行优先： 列优先：列优先： 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构（2）矩阵）矩阵在数据结构中，我们研究的是如何存储矩阵中的元素。在数据结构中，我们研究的是如何存储矩阵中的元素。特殊矩阵特殊矩阵 指矩阵中的元素分布有一定的规律的矩阵。例如：对称矩阵、三角矩阵、对指矩阵中的元素分布有一定的规律的矩阵。例如：对称矩阵、三角矩阵、对
15、 角矩阵。角矩阵。 存储时，可以将其压缩存储在一维数组中，并建立起每个非零元素在矩阵中的位置与其存储时，可以将其压缩存储在一维数组中，并建立起每个非零元素在矩阵中的位置与其一维护数组中的位置之间的对应关系。一维护数组中的位置之间的对应关系。稀疏矩阵稀疏矩阵非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律。非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律。 数据结构数据结构第一部分：线性结构第一部分：线性结构第一部分：线性结构第一部分：线性结构5 广义表广义表定义定义 是线性表的推广一，由零个或多个单元素或子表所组成的有限序列。一般记为：是线性表的推广一，由零个或多个单元
16、素或子表所组成的有限序列。一般记为：LS=（a1,a2,an）其中）其中ai(1=i=0）个节点的有限集合，当）个节点的有限集合，当n=0时，称为空树，在任一非空树中：时，称为空树，在任一非空树中： （1）有且仅有一个称为根的节点；）有且仅有一个称为根的节点； （2）其余节点可分为）其余节点可分为m (m=0) 个互不相交的有限集个互不相交的有限集T1、T2、 、Tm,其中其中Ti又都是一棵树，又都是一棵树， 并且乐为根节点的子树。并且乐为根节点的子树。 （递归定义）（递归定义）2、树的基本概念、树的基本概念 与树相关的概念有：与树相关的概念有： 双亲、孩子、兄弟双亲、孩子、兄弟节点的度、叶子节点、节点的层次、树的高度、有序（无序）树节点的度、叶子节点、节点的层次、树的高度、有序（无序）树 3、树的遍历、树的遍历 按照某种次序，获取树中全部节点的信息。按照某种次序，获取树中全部节点的信息。 数据结构数据结构第二部分第二部分第二部分第二部分 非线性结构非线性结构非线性结构非线性结构（二）二叉树的定义及基本运算、（二）二叉树的定义及基本运算、1、二叉树的定义：、二叉树的定义：二叉树或为空树
