数据结构复习.ppt

数据结构 主讲 刘仁芬 熟悉各名词 术语的含义 掌握基本概念 理解算法五个要素的确切含义 掌握计算语句频度和估算算法时间复杂度的方法 本章知识点 第一章绪论 1 1什么是数据结构 本章目录 1 2基本概念和术语 1 3抽象数据类型的表示和实现 第1章绪论 本节总结 1 4算法和算法分析 数据 data 对客观事物的符号表示 指所有能输入到计算机中并被计算机程序处理的符号的集合 计算机操作对象的总称 如整数 实数 字符串 图像 声音是数据 数据元素 dataelement 数据的基本单位 在计算机程序中通常作为一个整体进行考虑和处理 一个数据元素可由若干个数据项组成 数据项 dataitem 数据的不可分割的最小单位 如一本书的书目信息为一个数据元素 书目信息中的每一项 如书名 作者名 出版日期 组合项 为一个数据项 1 2基本概念和术语 数据对象是性质相同的数据元素的集合 是数据的一个子集 如整数数据对象是集合N 0 1 2 字母字符数据对象是集合C A B C Z 数据结构 datastructure 是相互之间存在一种或多种特定关系的数据元素的集合 结构 数据元素相互之间的关系 集合 数据元素间除 同属于一个集合 外 无其它关系线性结构 一个对一个 如线性表 栈 队列树形结构 一个对多个 如树图状结构 多个对多个 如图 根据数据元素间关系的不同特性 有四种基本结构 数据结构的形式定义为 数据结构是一个二元组Data Structure D S 其中 D是数据元素的有限集 S是D上关系的有限集 数据的逻辑结构 结构定义中的 关系 描述的是数据元素之间的逻辑关系 因此称为数据的逻辑结构 是对操作对象的一种数学描述 从操作对象抽象出来的数学模型 从逻辑关系上描述数据 与数据的存储无关 是独立于计算机的 数据的存储 物理 结构 是数据结构在计算机中的表示 又称映像 包括数据元素的表示和关系的表示 指数据元素及其关系在计算机存储器内的表示 存储结构是逻辑结构用计算机语言的实现 依赖于计算机语言 数据元素的表示 位 二进制数的一位 表示信息的最小单位 数据元素 结点 由若干位组合起来形成的一个位串 即数据元素在计算机中的映像 数据域 当数据元素由若干数据项组成时 位串中对应于各个数据项的子位串称为数据域 数据元素之间的关系的表示 关系都可以表示成有序对的集合 数据元素之间的关系的表示即有序对集合的映像 数据元素之间的关系的表示方法 顺序映像和非顺序映像 对应两种不同的存储结构 顺序存储结构和链式存储结构 顺序映像特点 是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系 中y的存储位置与x相差一个常量C C是一个隐含值 非顺序映像特点 是借助附加信息 指示元素存储地址的指针 来表示数据元素之间的逻辑关系 中附加信息与x存储在一起 指向y的存储地址 不同的编程环境数据结构的描述不同 比如高级语言就可以用数组来描述顺序存储结构 数据类型 是一个值的集合和定义在这个集上的一组操作的总称 数据类型分为两类 一类是非结构的原子类型 原子类型的值是不可分解的 如C语言中的基本类型 整型 实型 字符型和枚举 指针类型和空类型 另一种是结构类型 结构类型的值是由若干成分按某种结构组成的 因此是可以分解的 并且它的成分可以是结构的 也可以是非结构的 如数组是由若干分量组成 每个分量可以是整数 也可以是数组 结构类型可以看成由一种数据结构和定义在其上的一组操作组成 抽象数据类型 ADT 是指一个数学模型以及定义在该模型上的一组操作 抽象数据类型可用 D S P 三元组表示 其中 D是数据对象 S是D上的关系集 P是对D的基本操作集 D S 数据结构 D S P 抽象数据类型 抽象数据类型的特性 数据抽象 强调本质特征及所能完成的功能和外部接口 数据封装 将实体的外部特性和内部实现细节分离 并且隐藏实现细节 1 4算法和算法分析算法 algorithm 对特定问题求解步骤的一种描述 它是指令的有限序列 其中每一条指令表示一个或多个操作 算法着重于思想的描述 可能会省略很多细节 因此 算法需要进行适当修改才能变成程序在机器上实现 1 有穷性 一个算法必须总是在执行有穷步之后结束 且每一步都可在有穷时间内完成 2 确定性 算法的每一条指令必须有确切的含义 理解时不会产生二义性 并且在任何条件下都只有一条执行路径 3 可行性 一个算法是能行的 即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的 4 输入 一个算法有零个或多个输入 这些输入取自于某个特定的对象的集合 5 输出 一个算法有一个或多个输出 这些输出是同输入有着某些特定关系的量 算法特性 算法设计的要求 衡量算法优劣的标准正确性 算法应当满足具体问题的需求 4个层次程序不含语法错误程序中对于几组输入数据能够满足规格说明要求的结果程序对于精心选择的典型 苛刻而带有刁难性的几组输入数据能够满足规格说明要求的结果程序对于一切输入数据都能产生满足规格说明要求的结果可读性 算法主要是为了人的阅读和交流 其次才是机器执行 算法设计的要求 衡量算法优劣的标准健壮性 当输入的数据非法时 算法应当恰当地做出反映或进行相应处理 而不是产生莫名奇妙的输出结果 并且 处理出错的方法不应是中断程序的执行 而应是返回一个表示错误或错误性质的值 以便在更高的抽象层次上进行处理 效率与低存储量需求 效率指的是算法执行时间 存储量需求指算法执行构成中所需要的最大存储空间 算法 控制结构 原操作 固有数据类型的操作 算法的执行时间 原操作 i 执行次数 原操作 i 执行时间 原操作 i 执行次数对于研究问题来说是基本操作的原操作 以该基本操作重复执行的次数作为算法的时间量度 基本操作重复执行的次数被称为语句频度 是问题规模n的某个函数f n 随问题规模n的增大 算法执行时间的增长率和f n 的增长率相同 称做算法的渐近时间复杂度 简称时间复杂度 记作 T n O f n 算法的空间复杂度 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量 记作 S n O f n 输入和程序之外的额外空间 将a中整数序列重新排列成自小至大有序的整数序列 for i n 1 change TRUE i 1 i change FALSE change为元素进行交换标志for j 0 ja j 1 a j a j 1 change TRUE 一趟起泡S n O 1 原地工作 线性结构的特点 线性表的相关概念 线性表上定义的基本运算和用基本运算构造出的较复杂的运算 掌握顺序存储结构和链式存储结构的描述方法 以及各种基本操作的实现 能够从时间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合 使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题 本章知识点 第二章线性表 2 1线性表的类型定义 本章目录 2 2线性表的顺序表示和实现 2 3线性表的链式表示和实现 第2章线性表 本节总结 2 4一元多项式的表示及相加 线性结构的特点 在数据元素的非空有限集中 1 存在唯一的一个被称为第一个的数据元素 2 存在唯一的一个被称为最后一个的数据元素 3 除第一个之外 集合中的每个数据元素均只有一个前驱 4 除最后一个之外 集合中每个数据元素均只有一个后继 第2章线性表 线性表是一种最常用最简单的线性结构 2 1线性表的类型定义 线性表是n个数据元素的有限序列 抽象数据类型线性表的定义 ADTList 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 即数据元素的次序关系 ai是第i个数据元素 称i为ai在线性表中的位序 数据元素可以是字母字符 数 或者更复杂的记录 由多个数据项组成 称n为线性表的长度 称n 0时的线性表为空表 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素 元素之间的关系隐含在存储地址中 an ai a2 a1 b b L b i 1 L b n 1 L 存储地址 内存状态 图2 2线性表的顺序存储结构示意图设每个元素需占L个存储单元 以所占的第一个单元的存储地址作为数据元素的存储位置 b为第一个数据元素的存储位置 称为线性表的起始位置或者基地址 2 2线性表的顺序表示和实现 Loc ai Loc a1 i 1 L 每个元素所占用的存储单元个数 LOC a1 是线性表的起始地址或基地址 线性表中第i 1个数据元素的存储位置Loc ai 1 和第i个数据元素的存储位置Loc ai 之间满足下列关系 Loc ai 1 Loc ai L线性表的第i个数据元素ai的存储位置为 线性表的这种机内表示称作线性表的顺序存储结构或顺序映象 称这种存储结构的线性表为顺序表 以元素在计算机内的物理位置相邻来表示线性表中数据元素之间的逻辑关系 每个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数 因此 只要确定了线性表的起始位置 线性表中任一数据元素都可随机存取 所以线性表的顺序存储结构是一种随机存取的存储结构 defineLIST INIT SIZE100 线性表存储空间的初始分配量 defineLISTINCREMENT10 线性表存储空间的分配增量typedefstruct 定义一个SqList这样的类型 结构体类型 ElemType elem 存储空间基址 指示线性表基地址intlength 当前长度intlistsize 当前分配的存储容量 以sizeof ElemType 为单位 SqList 线性表的动态分配顺序存储结构 线性表的基本操作在顺序表中的实现 InitList Sq L 结构初始化 LocateElem Sq L e compare 查找 ListInsert Sq L i e 插入元素 ListDelete Sq L i 删除元素 算法2 在线性表中指定位置i前插入一个元素 a1 ai 1 ai an 改变为 a1 ai 1 e ai an 表的长度增加 例如 ListInsert Sq L 5 66 L length 1 0 87 56 42 66 q q e 插入e L length 表长增1 一般情况下 设Pi是在第i 1 i n 个数据元素之前插入一个元素的概率 在第i个元素之前插入一个元素时 需将第n个元素至第i个元素向后移动一个位置 即移动n i 1个元素 在长度为n的线性表中插入一个元素时所需移动元素次数的期望值 平均次数 为 插入时移动次数的期望值 平均次数 a1 ai 1 ai ai 1 an 改变为 a1 ai 1 ai 1 an ai 1 an 表的长度减少 算法3 在线性表中删除第i个元素 L length 1 0 87 56 p 例如 ListDelete Sq L 5 e 一般情况下 删除第i 1 i n 个元素时 需将第i 1至第n 共n i个 元素依次向前移动一个位置 qi是删除第i个元素的概率 在长度为n的线性表中删除一个元素时所需移动元素次数的期望值 平均值 为 删除第i个元素的移动次数的期望值 平均值 例如 顺序表 23754138546217 L length L listsize e 38 i 1 2 3 4 1 8 50 可见 基本操作是 将顺序表中的元素逐个和给定值e相比较 不相等后移 相等返回 算法4 在顺序表中查找是否存在和e相同的数据元素 intLocateElem Sq SqListL ElemTypee Status compare ElemType ElemType 在顺序表中查询第一个满足判定条件的数据元素 若存在 则返回它的位序 否则返回0i 1 i的初值为第1元素的位序p L elem p的初值为第1元素的存储位置while i L length LocateElem Sq 时间复杂度O L length 2 3线性表的链式表示和实现 线性表的链式存储结构特点 用一组任意的存储单元 可以是连续的 也可以是不连续的 存放线性表的数据元素 为了表示每个数据元素与其直接后继之间的逻辑关系 对数据元素ai来说 除了存储其本身的信息之外 还需存储一个指示其直接后继的信息 即直接后继的存储位置 这两部分信息组成数据元素ai的存储映象 称为结点 它含有两个域 存储数据元素信息的域称为数据域 存储直接后继存储位置的域称为指针域 指针域中存储的信息称作指针或链 数据域指针域 结点 2 3 1线性链表 n个结点链成一个链表 即为线性表 a1 a2 an 的链式存储结构 由于链表的每个结点中只包含一个指针域 又称线性链表或单链表 整个链表的存取需从头指针开始进行 头指针指示链表中第一个结点 即第一个数据元素的存储映象 的存储位置 由于最后一个数据元素没有直接后继 则线性表中最后一个结点的指针为空 NULL 指针为数据之间逻辑关系的映像 则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻 这种存储结构为非顺序映像或链式映像 typedefstructLNode ElemTypedata structLnode next LNode LinkList 线性表的单链表存储结构 L 图2 7带头结点的单链表 L a 非空表 b 空表 在单链表的第一个结点之前附设一个结点 称之为头结点 头结点的数据域可以不存储任何信息 也可存储如线性表的长度等类的附加信息 头结点的指针域存储指向第一个结点的指针 单链表的头指针指向头结点 若线性表为空表 则头结点的指针域为空 L 单链表操作的实现 GetElem L L i e 取第i个数据元素 ListInsert L L i e 插入数据元素 ListDelete L L i e 删除数据元素 CreateList L L n 生成含n个数据元素的链表 线性表的操作GetElem L L 3 e 在单链表中的实现 j 1 2 3 单链表是一种顺序存取的结构 为找第i个数据元素 必须先找到第i 1个数据元素 因此 查找第i个数据元素的基本操作为 从头到尾根据next指针域移动指针 令指针p始终指向线性表中第j个数据元素 比较j和i 当j i时 p指向第i个数据元素 或者移动到链表尾部时结束 线性表的操作ListInsert L i e 在单链表中的实现 有序对改变为和 s LinkList malloc sizeof LNode 生成新结点s data e s next p next p next s 插入returnOK s p 线性表的操作ListDelete L L i e 在链表中的实现 有序对和改变为 在单链表中删除第i个结点的基本操作为 找到线性表中第i 1个结点 修改其指向后继的指针 q p next p next q next e q data free q p q a1a2 an 和单链表的差别仅在于 判别链表中最后一个结点的条件不再是 后继是否为空 而是 后继是否为头结点 循环单链表 特点 最后一个结点的指针域指向头结点 整个链表形成一个环 由此 从表中任一结点出发均可找到其它结点 P35 空表 2 3 2循环链表 在每个结点中有两个指针域 一个指向直接后继 一个指向直接前驱 typedefstructDuLNode ElemTypedata structDuLNode prior structDuLNode next DuLNode DuLinkList 线性表的双向链表存储结构 2 3 3双向链表 双向循环链表 空表 非空表 a1a2 an 双向链表有循环表 链表中有两个环 在双向链表中 若d为指向表中某一结点的指针 即d为DuLinkList型变量 则显然有d next prior d prior next d 双向链表的操作特点 查询 和单链表相同 插入 和 删除 时需要同时修改两个方向上的指针 s next p next p next s s next prior s s prior p p s 插入 删除 p next p next next p next prior p p 删除 p prior next p next p next prior p prior p 1 了解线性表的逻辑结构特性是数据元素之间存在着线性关系 在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构 用前者表示的线性表简称为顺序表 用后者表示的线性表简称为链表 2 熟练掌握这两类存储结构的描述方法 以及线性表的各种基本操作的实现 3 综合比较线性表两种存储结构的不同特点及其适用场合 本章总结 线性表链式存储结构的特点 优点 空间合理利用 插入和删除不需要移动 缺点 实现某些操作不如顺序存储结构 线性表顺序存储结构特点 优点 关系上相邻的两个元素在物理位置上也相邻 因此可随机存取表中任一元素 存储位置可用一个简单 直观的公式来表示 缺点 插入或删除操作时 需大量移动元素 分析讨论 1 在表很长时 采用顺序方式时插入和删除元素的效率很低 只有在很少进行插入和删除运算的情况下 采用顺序表才是合适的 而线性链表的插入和删除运算效率总是很高 与表长无关 2 对线性表的长度或存储规模难以估计时 不宜采用顺序表 3 顺序表所占存储空间少 但要求是连续的存储单元 线性链表因为有指针域 所占存储空间大 但可以利用非连续单元 本章要点 栈和队列的定义和特点 熟练掌握栈类型的实现方法 特别应注意栈满和栈空的条件以及它们的描述方法 熟练掌握循环队列和链队列的基本操作实现算法 特别注意队满和队空的描述方法 能在相应的应用问题中正确选用它们 第三章栈和队列 本章目录 第3章栈和队列3 1栈3 2栈的应用举例3 3栈和递归的实现3 4队列 栈 后进先出的线性表 是限定仅在表尾进行插入和删除操作的线性表 表尾端为栈顶 表头端为栈底 不含元素的栈为空栈 3 1栈 3 1 1抽象数据类型栈的定义 设栈s a1 a2 ai an a1是栈底元素 an是栈顶元素 ADTStack 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 约定an端为栈顶 a1端为栈底 栈的抽象数据类型的定义 GetTop S e 初始条件 栈S已存在且非空 操作结果 用e返回S的栈顶元素 a1 a2 an Push S e 初始条件 栈S已存在 操作结果 插入元素e为新的栈顶元素 a1 a2 an e 入栈 Pop S e 初始条件 栈S已存在且非空 操作结果 删除S的栈顶元素 并用e返回其值 a1 a2 an an 1 出栈 栈有两种存储表示方法 顺序栈 链栈 顺序栈 即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 同时附设指针top指示栈顶元素在顺序栈中的存储位置 3 1 2栈的表示和实现 栈的顺序存储表示 defineSTACK INIT SIZE100 defineSTACKINCREMENT10 typedefstruct SElemType base SElemType top intstacksize 栈的最大容量 SqStack a1 a2 top base 栈的初始化操作为 按设定的初始分配量进行第一次存储分配 base称为栈底指针 在顺序栈中 它始终指向栈底的位置 若base值为NULL 表明栈结构不存在 称top为栈顶指针 初值指向栈底 即top base为栈空 每当插入新的栈顶元素时 指针top增1 删除栈顶元素时 指针top减1 因此 非空栈中的栈顶指针始终在栈顶元素的下一个位置上 top base top base top base top base 栈中的运算 1 设置空栈 2 取栈顶元素 3 插入一个新的栈顶元素 4 删除栈顶元素 StatusInitStack SqStack 基本操作的算法描述 构造一个空栈S StatusGetTop SqStackS SElemType 取栈顶元素 StatusPush SqStack 存储分配失败 入栈 S top S base S stacksize S stacksize STACKINCREMENT S top e returnOK StatusPop SqStack 出栈 例 设S是一个顺序栈 栈的最大容量stacksize 4 初始状态top base 10 S 4 base s top etop top 1 top 栈空 10进栈 S 4 top base top base 10 25 30 S 4 top base top top 1e s top 40出栈 top base stacksize 栈满 10 25 30 40 S 4 top base 由于栈结构具有的后进先出的固有特性 致使栈成为程序设计中常用的工具 以下是几个栈应用的例子 3 2 1数制转换 3 2栈的应用举例 3 2 2括号匹配的检验 3 2 3行编辑程序 3 2 4迷宫求解 3 2 5表达式求值 递归函数 一个直接调用自己或通过一系列的调用语句间接地调用自己的函数 3 3栈和递归的实现 递归算法 描述递归定义的函数或求解递归问题的过程称为递归算法 递归算法的实质 是将解问题规模N的较复杂的处理分解为问题规模小于N的较简单的处理 这些较简单的问题又分解为问题规模更小的更简单的问题处理 直到最简单的处理 然后这些规模小的简单问题的解综合为规模较大的问题的解 直到求到原问题的解 假设有3个分别命名为x y和z的塔座 在塔座x上插有n个直径大小各不相同 依小到大编号为l 2 n的圆盘 现要求将x轴上的n个圆盘移至z轴上并仍按同样顺序叠排 圆盘移动时必须遵循下列规则 1 每次只能移动一个圆盘 2 圆盘可以插在x y和z中的任一塔座上 3 任何时刻都不能将一个较大的圆盘压在较小圆盘之上 n阶Hanoi塔问题 voidhanoi intn charx chary charz 将塔座x上按直径由小到大且至上而下编号为1至n 的n个圆盘按规则搬到塔座z上 y可用作辅助塔座 if n 1 3move x 1 z 将编号为 的圆盘从x移到z4else 5hanoi n 1 x z y 将x上编号为 至n 1的 圆盘移到y z作辅助塔6move x n z 将编号为n的圆盘从x移到z7hanoi n 1 y x z 将y上编号为 至n 1的 圆盘移到z x作辅助塔8 9 介绍的是队列的逻辑结构定义及在两种存储结构 顺序存储结构和链式存储结构 上如何实现队列的基本运算 本章的重点是掌握队列在两种存储结构上实现的基本运算 难点是循环队列中对边界条件的处理 本节内容及重点 3 4队列 队列 是先进先出 FIFO 的线性表 只允许在表的一端进行插入 而在另一端进行删除元素的线性表 3 4 1队列的定义与运算 允许插入的一端叫队尾 允许删除的一端称为队头 假设队列q a1 a2 an a1是队头元素 an队尾元素 ADTQueue 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 约定其中a1端为队列头 an端为队列尾 基本操作 InitQueue Q 操作结果 构造一个空队列Q EnQueue Q e 初始条件 队列Q已存在 操作结果 插入元素e为Q的新的队尾元素 a1 a2 an e DeQueue Q e 初始条件 Q为非空队列 操作结果 删除Q的队头元素 并用e返回其值 a1 a2 an ADTQueue 队列的主要运算 1 设置一个空队列 2 读取队头元素 3 插入一个新的队尾元素 称为入队 4 删除队头元素 称为出队 一个链队列显然需要两个分别指示队头和队尾的指针 头指针 尾指针 才能唯一确定 为了操作方便 给链队列添加一个头结点 并令头指针指向头结点 空的链队列的判决条件为头指针和尾指针均指向头结点 3 4 2链队列 队列的链式表示和实现 链队列 用链表表示的队列 Q frontQ rear Q frontQ rear 空队列 链队列 链队列示意图 队头 队尾 Q rear next S Q rear S p Q front next Q front next p next Free p typedefstructQNode 结点类型QElemTypedata structQNode next QNode QueuePtr typedefstruct 链队列类型QueuePtrfront 队头指针QueuePtrrear 队尾指针 LinkQueue 单链队列 队列的链式存储结构 ADTQueue的表示和实现 StatusEnQueue LinkQueue StatusDeQueue LinkQueue 在队列的顺序存储结构中 除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外 需附设两个front和rear分别指示队列头元素及队列尾元素的位置 3 4 3循环队列 队列的顺序表示和实现 为在c语言中描述方便起见 在此约定 初始化建空队列时 令front rear 0 每当插入新的队列尾元素时 尾指针增1 每当删除队列头元素时 头指针增1 在非空队列中 头指针始终指向队列头元素 而尾指针始终指向队列尾元素的下一个位置 rear front 初始状态 rear front J4 J5 J6 0 1 2 3 4 5 rear front J8 J7 队空 一般情况 解决方案 少用一个元素空间 队空 Q front Q rear队满 Q rear 1 MAXQSIZE Q front 队满 defineMAXQSIZE100 最大队列长度typedefstruct QElemType base 初始化的动态分配存储空间intfront 头指针 若队列不空 指向队列头元素intrear 尾指针 若队列不空 指向 队列尾元素的下一个位置 SqQueue 循环队列 队列的顺序存储结构 StatusInitQueue SqQueue StatusEnQueue SqQueue StatusDeQueue SqQueue 1 掌握栈和队列类型的特点 并能在相应的应用问题中正确选用它们 2 熟练掌握栈类型的两种实现方法 特别应注意栈满和栈空的条件以及它们的描述方法 3 熟练掌握循环队列和链队列的基本操作实现算法 特别注意队满和队空的描述方法 4 理解递归算法执行过程中栈的状态变化过程 本章总结 本章要点 理解串匹配的KMP算法 熟悉NEXT函数的定义 学会手工计算给定模式串的NEXT函数值和改进的NEXT函数值 熟悉串的基本操作的定义 并能利用基本操作来实现串的其它各种操作的方法 掌握串的三种机内表示方法 第四章串 4 1串类型的定义 4 2串的表示和实现 4 3串的模式匹配算法 本章目录 第4章串 串 string 由零个或多个字符组成的有限序列 记为 s a1a2a3 an n 0 s是串的名 a1a2a3 an是串的值 ai 1 i n 可以是字母 数字或其它字符 串的长度 串中字符的数目n 空串 零个字符的串 它的长度为零 用 表示空串 空格串 由一个或多个空格组成的串 4 1串类型的定义 串是有限长的字符序列 由一对单引号相括 如 astring 串的抽象数据类型定义 ADTString 数据对象 D ai ai CharacterSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 串的逻辑结构和线性表极为相似 区别是串的数据对象约束为字符集 StrCompare S T 初始条件 串S和T存在 操作结果 若S T 则返回值 0 若S T 则返回值 0 若S T 则返回值 0 例如 StrCompare data state 0比较的实质是ASCII码值 串的比较是一个字符一个字符的比 按照ASCII码比较 不是比较串长度 串相等的条件 当两个串的长度相等且各个对应位置的字符都相等时才相等 StrLength S 初始条件 串S存在 操作结果 返回S的元素个数 称为串的长度 SubString Sub S pos len 初始条件 串S存在 1 pos StrLength S 且0 len StrLength S pos 1 操作结果 用Sub返回串S的第pos个字符起长度为len的子串 子串 串中任意个连续的字符组成的子序列 主串 包含子串的串 如 A STUDYING B DYI A为主串 B为子串 位置 字符在序列中的序号 子串在主串中的位置以子串的第一个字符在主串中的位置来表示 串的逻辑结构和线性表极为相似 区别是串的数据对象约束为字符集 串的基本操作和线性表有很大差别 在线性表的基本操作中 大多以 单个元素 作为操作对象 而在串的基本操作中 通常以 串的整体 作为操作对象 如 在串中查找某个子串 求取一个子串 在串的某个位置上插入一个子串以及删除一个子串等 一 串的定长顺序存储表示 二 串的堆分配存储表示 三 串的块链存储表示 串有3种机内表示方法 顺序 链式 若模式T中的每个字符依次和主串S中的一个连续的字符序列相等 则称匹配成功 函数值为和模式T中第一个字符相等的字符在主串S中的序号 否则称匹配不成功 函数值为零 模式匹配 子串的定位操作模式串 子串 线性结构中的数据元素都是非结构的原子类型 元素的值是不再分解的 数组和广义表可以看成是线性表的扩展 表中的数据元素本身也是一个数据结构 第5章数组和广义表 ADTArray 数据对象 ji 0 bi 1 i 1 2 nD aj1 ji jn n是数组的维数 bi第i维的长度 ji第i维下标 aj1 ji jn ElemSet 数据关系 R R1 R2 Rn Ri 0 jk bk 1 1 k n且k i 0 ji bi 2 aj1 ji jn aj1 ji 1 jn D i 2 n 5 1数组的定义 二维数组的定义 数据对象 D aij 0 i b1 1 0 j b2 1 数据关系 R ROW COL ROW 0 i b1 1 0 j b2 2 COL 0 i b1 2 0 j b2 1 两个关系仍是线性关系 特点 1 一旦建立数组 则结构中的数据元素个数和元素之间的关系就不再发生变动 因此采用顺序存储结构表示数组 2 数组是多维的结构 而存储空间是一个一维的结构 则用一组连续存储单元存放数组的数据元素就有个次序约定问题 5 2数组的顺序表示和实现 二维数组有两种存储方式 P921 以行序为主序 低次序优先 2 以列序为主序 高次序优先 例如 称为基地址或基址 以 行序为主序 的存储映象 二维数组A中任一元素aj1 j2的存储位置LOC j1 j2 LOC 0 0 j1 b2 j2 a0 1 a0 0 a0 2 a1 0 a1 1 a1 2 a0 1 a0 0 a0 2 a1 0 a1 1 a1 2 L L 式中 Loc 00 为元素a00的存储位置 即二维数组的起始存储位置 也称基地址 b1为二维数组的行数 b2为列数 aj1 j2代表其中第j1行 第j2列的那个元素 每个数据元素占L个存储单元 压缩存储 为多个值相同的元素只分配一个存储空间 对零元不分配空间 目的是节省存储空间 基本概念 特殊矩阵 值相同的元素或零元在矩阵中的分布有一定的规律 对称矩阵 三角矩阵 对角矩阵 反之 称为稀疏矩阵 5 3矩阵的压缩存储 稀疏矩阵的压缩存储方法 一 三元组顺序表 二 行逻辑链接的顺序表 三 十字链表 ADTGlist 数据对象 D ei i 1 2 n n 0 ei AtomSet或ei GList AtomSet为某个数据对象 数据关系 LR ei 1 ei D 2 i n 5 4广义表 列表 的定义 广义表是线性表的推广 是递归定义的线性结构 记作LS 1 2 n LS是广义表的名称 n为表的长度 i是表元素 它可以是广义表 称为子表 可以是单个元素 称为原子 n 0的广义表为空表 列表LS 1 2 n 是多层次的线性结构 列表的元素可以是子表 而子表的元素还可以是子表 由此 列表是一个多层次的结构 例如 D E F 其中 E a b c F d e D E F a d b c e 1 广义表中的数据元素有相对次序 2 广义表的长度定义为最外层的元素个数 3 广义表的深度定义为包含括弧的重数 原子的深度为0 空表的深度为1 4 广义表可以共享 例如 D E F A E E F是D的子表 不必列子表的值 而是通过子表的名称来应用 5 列表可以是一个递归的表 递归的深度无穷值 长度是有限值 列表LS 1 2 n 的结构特点 6 任何一个非空广义表LS 1 2 n 均可分解为 表头Head LS 1和表尾Tail LS 2 n 两部分 当广义表非空时 表的第一个元素 1称为广义表的表头 head 除此之外 其它元素组成的表 2 3 n 称为广义表的表尾 tail 1 了解数组的存储表示方法 并掌握数组在以行为主的存储结构中的地址计算方法 2 掌握对特殊矩阵 对称矩阵和对角矩阵 进行压缩存储时的下标变换公式 3 了解稀疏矩阵的两类压缩存储方法的特点和适用范围 领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法 本章总结 4 掌握广义表的结构特点及其存储表示方法 学会对非空广义表进行分解的分析方法 即可将一个非空广义表分解为表头和表尾两部分 树是以分支关系定义的层次结构 树结构在客观世界广泛存在 如人类社会的族谱和各种社会组织机构都可用树来表示 树在计算机领域中也广泛应用 如在编译程序中 可用树表示源程序的语法结构 又如在数据库系统中 树形结构也是信息的重要组织形式之一 树型结构是非线性数据结构 第6章树和二叉树 6 1树的定义和基本术语 6 2二叉树 6 3遍历二叉树和线索二叉树 6 4树和森林 6 6哈夫曼树与其应用 树 tree 是n n 0 个结点的有限集 在任意一棵非空树中 1 有且仅有一个特定的称为根的结点 2 当n 1时 其余结点可分为m m 0 个互不相交的有限集T1 T2 Tm 其中每一个集合本身又是一棵树 并且称为根的子树 6 1树的定义和基本术语 根 子树 数据对象D D是具有相同特性的数据元素的集合 若D为空集 则称为空树 否则 1 在D中存在唯一的称为根的数据元素root 2 当n 1时 其余结点可分为m m 0 个互不相交的有限集T1 T2 Tm 存在关系 Xi T1 其中每一棵子集本身又是一棵符合本定义的树 称为根root的子树 数据关系R ADTTree 基本术语 结点 结点的度 树的度 叶子 终端 结点 分支 非终端 结点 数据元素 若干指向子树的分支 结点拥有的子树数 树中所有结点的度的最大值 度为零的结点 度不为零的结点 D H I J M 子孙 以某结点为根的子树中的任一结点 A B C D E F G H I J M K L 孩子 结点的子树的根 双亲 该结点称为孩子的双亲 兄弟 同一个双亲的孩子之间互称兄弟 祖先 从根到该结点所经分支上的所有结点 有序树 子树之间存在确定的次序关系 不能互换 无序树 子树之间不存在确定的次序关系 树的深度 树中结点的最大层次 堂兄弟 其双亲在同一层的结点 结点的层次 假设根结点的层次为1 若某结点在第l层 则其子树的根结点层次为l 1 D H I J M 任何一棵非空树是一个二元组Tree root F 其中 root被称为根结点F被称为m棵子树的森林 森林 是m m 0 棵互不相交的树的集合 A root B C D E F G H I J M K L F 对比树型结构和线性结构的结构特点 线性结构 树型结构 第一个数据元素 无前驱 根结点 无前驱 最后一个数据元素 无后继 多个叶子结点 无后继 其它数据元素 一个前驱 一个后继 其它数据元素 一个前驱 多个后继 对比 6 2二叉树 二叉树 或为空树 或是由一个根结点加上两棵分别称为左子树和右子树的 互不相交的二叉树组成 A B C D E F G H K 根结点 左子树 右子树 特点 1 每个结点至多有二棵子树 即不存在度大于2的结点 2 二叉树的子树有左 右之分 且其次序不能任意颠倒 二叉树的五种基本形态 空树 只含根结点 L R R 右子树为空树 L 左子树为空树 左右子树均不为空树 二叉树的性质 性质1 在二叉树的第i层上至多有2i 1个结点 i 1 性质2 深度为k的二叉树上至多含2k 1个结点 k 1 性质3 对任何一棵二叉树 若它含有n0个叶子结点 n2个度为2的结点 则必存在关系式 n0 n2 1 两类特殊的二叉树 指的是深度为k且含有2k 1个结点的二叉树 满二叉树 树中所含的n个结点和满二叉树中编号为1至n的结点一一对应 完全二叉树 完全二叉树特点 1 叶子结点只可能在层次最大的两层上出现 2 对任一结点 若其右分支下子孙的最大层次为l 则其左分支下子孙的最大层次必为l或l 1 性质4 具有n个结点的完全二叉树的深度为 log2n 1 证明 设完全二叉树的深度为k则根据第二条性质得2k 1 第k层第一个结点的编号 n 2k 第k 1层第一个结点的编号 即k 1 log2n k因为k只能是整数 因此 k log2n 1 性质5 若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号 则对完全二叉树中任意一个编号为i的结点 1 若i 1 则该结点是二叉树的根 无双亲 如果i 1 编号为 i 2 的结点为其双亲结点 2 若2i n 则该结点无左孩子 否则 编号为2i的结点为其左孩子结点 3 若2i 1 n 则该结点无右孩子结点 否则 编号为2i 1的结点为其右孩子结点 二叉树的存储结构 二 链式存储结构 一 顺序存储结构 存储方式 用一组地址连续的存储单元依次自上而下 自左至右存储完全二叉树上的结点元素 即将完全二叉树上编号为i的结点元素存储在一维数组中下标为i 1的分量中 一 二叉树的顺序存储结构 对于一般二叉树 应将其每个结点与完全二叉树上结点相对照 存储在一维数组分量中 0 表示不存在此结点 例如 A B C D E F ABDCEF 012345678910111213 1 4 0 13 2 6 0表示不存在此结点 0 0 000000 二 二叉树的链式存储结构 1 二叉链表 2 三叉链表 A D E B C F root lchilddatarchild 结点结构 1 二叉链表 F 在n个结点的二叉链表中 有n 1个空指针域 typedefstructBiTNode 结点结构TElemTypedata structBiTNode lchild rchild 左右孩子指针 BiTNode BiTree lchilddatarchild 结点结构 C语言的类型描述如下 A D E B C F root 2 三叉链表 parentlchilddatarchild 结点结构 F 6 3遍历二叉树和线索二叉树 先左后右的遍历算法 先 根 序遍历 中 根 序遍历 后 根 序遍历 根 L R 先序遍历 中序遍历 后序遍历 a b c d e f a b c d e f a b c d e f 层次遍历 a b c d e f 先序遍历二叉树的递归算法描述 StatusPreorder BiTreeT Status visit TElemTypee 先序遍历二叉树if T if visit T data 访问根结点if Preorder T lchild visit 先序遍历左子树if Preorder T rchild visit returnOK 先序遍历右子树returnERROR 访问没有成功 elsereturnOK T为空树 中序遍历二叉树的递归算法描述 StatusInOrderTraverse BiTreeT Status visit TElemTypee 中序遍历二叉树if T if InOrderTraverse T lchild visit 中序遍历左子树if visit T data 访问根结点if InOrderTraverse T rchild visit returnOK 中序遍历右子树returnERROR 访问没有成功 elsereturnOK T为空树 见演示 后序遍历二叉树的递归算法描述 StatusPostorder BiTreeT Status visit TElemTypee 后序遍历二叉树if T if Postorder T lchild visit 后序遍历左子树if Postorder T rchild visit 后序遍历右子树if visit T data returnOK 访问根结点returnERROR 访问没有成功 elsereturnOK T为空树 见演示 statusInorderTraverse BiTreeT status Visit TelemTypee InitStack S p T while p StackEmpty S if p Push S p p p lchild 根指针进栈 遍历左子树else 根指针退栈 访问根结点 遍历右子树Pop S p if Visit p data returnERROR p p rchild else whileReturnOK InorderTraverse 中序遍历算法的非递归描述 算法2 根据中序遍历和先序遍历 或后序遍历才能确定一棵二叉树 先序 ABCDEFGHK中序 BDCAHGKFE后序 DCBHKGFEA 线索二叉树 何谓线索二叉树 线索链表的遍历算法如何建立线索链表 以这种结点结构构成的二叉链表作为二叉树的存储结构 叫作 线索链表 为了避免混淆 需改变结点结构 增加两个标志域 0lchild域指示结点的左孩子1lchild域指示结点的前驱0rchild域指示结点的右孩子1rchild域指示结点的后继 LTag RTag 遍历二叉树的结果是 求得结点的一个线性序列 A B C D E F G H K 例如 先序序列 ABCDEFGHK 中序序列 BDCAHGKFE 后序序列 DCBHKGFEA 指向结点前驱和后继的指针 称作 线索 加上线索的二叉树 称作 线索二叉树 ABCDEFGHK D C B E 对二叉树以某种次序遍历使其变为线索二叉树的过程叫做 线索化 不同的遍历顺序产生的线索二叉树相同吗 实线为指针 指向左 右子树 虚线为线索 指向前驱和后继 6 4树和森林 树的存储结构 一 双亲表示法 二 孩子表示法 三 孩子兄弟表示法 二叉树表示法或二叉链表表示法 一 双亲表示法 以一组连续空间存储树的结点 同时在每个结点中附设一个指示器指示其双亲结点在表中的位置 6G5 dataparent 数组下标 树的双亲表示法示例 0A 1 1B2C3D 000 4E5F 22 二 孩子表示法 A B C D E F G ABCEDFG ABCEDFG 三 孩子兄弟表示法 二叉树表示法或二叉链表表示法 对应 存储 存储 A B C E D ABCDE 6 4 2森林和二叉树的转换 对应 存储 存储 6 4 2森林和二叉树的转换 设森林F T1 T2 Tn T1 root t11 t12 t1m 二叉树B LBT Node root RBT 由森林转换成二叉树的转换规则为 若F 则B 否则