C++电子课件(中)第七章.ppt

第七章动态内存分配与数据结构 本章首先介绍程序运行时动态内存分配 dynamicmemoryallocation 的概念与方法 进一步讨论复制构造函数 然后学习更多有关数据结构的基本知识 包括链表 栈 队 二叉树等的基本算法和应用 模板是标准C 实现代码复用的有力工具 特别是有关数据结构的算法 本章继续使用 7 1自由存储区内存分配 7 4二叉树 选读 7 3栈与队列的基本操作及其应用 7 2链表与链表的基本操作 第七章动态内存分配与数据结构 7 1自由存储区内存分配 7 1 1自由存储区内存的分配与释放 7 1 2自由存储区对象与构造函数 7 1 3浅复制与深复制 静态存储分配 无论全局或局部变量 对象 编译器在编译时都可以根据该变量 对象 的类型知道所需内存空间的大小 从而系统在适当的时候为它们分配确定的存储空间 尤其是数组 动态存储分配 有些操作对象只有在程序运行时才能确定 这样编译器在编译时就无法为他们预定存储空间 只能在程序运行时 系统根据运行时的要求进行内存分配 称为动态存储分配 动态分配都在自由存储区中进行 7 1 1自由存储区内存的分配与释放 当程序运行到需要动态分配变量或对象时 必须向系统申请取得自由存储区中的一块所需大小的存贮空间 用于存贮该变量或对象 当不再使用该变量或对象时 也就是它的生命结束时 要显式释放它所占用的存贮空间 这样系统就能进行再次分配 做到重复使用有限的资源 申请和释放自由存储区中分配的存贮空间 分别使用new和delete的两个运算符来完成 其使用的格式如下 指针变量名 new类型名 初始化式 delete指针名 new运算符返回的是一个指向所分配类型变量 对象 的指针 对所创建的变量或对象 都是通过该指针来间接操作的 而动态创建的对象本身没有名字 动态分配与释放 7 1 1自由存储区内存的分配与释放 一般定义变量和对象时要用标识符命名 称命名对象 而动态的称无名对象 请注意与栈区中的临时对象的区别 两者完全不同 生命期不同 操作方法不同 临时变量对程序员是透明的 自由存储区是不会自动在分配时做初始化的 包括清零 所以必须用初始化式 initializer 来显式初始化 new表达式的操作 从自由存储区分配对象 然后用括号中的值初始化该对象 分配对象时 new表达式调用库操作符new int pi newint 0 pi现在所指向的变量的存储空间是由库操作符new 分配的 位于程序的自由存储区中 并且该对象未命名 无名对象 7 1 1自由存储区内存的分配与释放 自由存储区 i 演示 用初始化式 initializer 来显式初始化int pi newint 0 当pi生命周期结束时 必须释放pi所指向的目标 deletepi 注意这时释放了pi所指的目标的内存空间 也就是撤销了该目标 称动态内存释放 dynamicmemorydeallocation 但指针pi本身并没有撤销 该指针所占内存空间并未释放 7 1 1自由存储区内存的分配与释放 数组动态分配格式 指针变量名 new类型名 下标表达式 delete 指向该数组的指针变量名 说明 两式中的方括号必须配对使用 如果delete语句中少了方括号 因编译器认为该指针是指向数组第一个元素的指针 会产生回收不彻底的问题 只回收了第一个元素所占空间 加了方括号后就转化为指向数组的指针 回收整个数组 delete 的方括号中不需要填数组元素数 系统自知 即使写了 编译器也忽略 请注意 下标表达式 不是常量表达式 即它的值不必在编译时确定 可以在运行时确定 7 1 1自由存储区内存的分配与释放 动态分配数组与标准字符串类 标准字符串类string就是采用动态建立数组的方式解决数组溢出的问题的 例7 1所做的动态内存分配与释放 在string类对象中都是自动完成的 在程序中不需要也不允许再显式地为string进行动态内存的分配与释放 例7 1 动态数组的建立与撤销 7 1 1自由存储区内存的分配与释放 动态分配数组的特点 1 变量n在编译时没有确定的值 而是在运行中输入 按运行时所需分配空间 这一点是动态分配的优点 可克服数组 大开小用 的弊端 在表 排序与查找中的算法 若用动态数组 通用性更佳 delete pc是将n个字符的空间释放 而用deletepc则只释放了一个字符的空间 2 如果有char pc1 令pc1 pc 同样可用delete pc1来释放该空间 尽管C 不对数组作边界检查 但在自由存储区空间分配时 对数组分配空间大小是纪录在案的 3 没有初始化式 initializer 不可对数组初始化 7 1 1自由存储区内存的分配与释放 选读 多维数组动态分配 new类型名 下标表达式1 下标表达式2 建立一个动态三维数组float cp 30 20 指向一个30行20列数组的指针cp newfloat 15 30 20 建立由15个30 20数组组成的数组 注意cp等效于三维数组名 但没有指出其边界 即最高维的元素数量 就像指向字符的指针即等效一个字符串 不要把指向字符的指针 说成指向字符串的指针 这与数组的嵌套定义相一致 7 1 1自由存储区内存的分配与释放 选读 比较 float cp 30 20 三级指针float bp 20 二级指针cp newfloat 1 30 20 bp newfloat 30 20 两个数组都是由600个浮点数组成 前者是只有一个元素的三维数组 每个元素为30行20列的二维数组 而另一个是有30个元素的二维数组 每个元素为20个元素的一维数组 删除这两个动态数组可用下式 delete cp 删除 释放 三维数组delete bp 删除 释放 二维数组 例7 2 动态创建和删除一个m n个元素的数组 7 1 1自由存储区的分配与释放 指针使用的要点 1 动态分配失败 返回一个空指针 NULL 表示发生了异常 堆资源不足 分配失败 2 指针删除与自由存储区空间释放 删除一个指针p deletep 实际意思是删除了p所指的目标 变量或对象等 释放了它所占的自由存储区空间 而不是删除 本身 释放自由存储区空间后 成了空悬指针 空悬指针是程序错误的一个根源 建议这时将 置空 NULL 3 new 和delete 是可以重载的 它们都是类的静态成员函数 程序员无需显式声明它为静态的 系统自动定义为静态的 本教材不讨论new 和delete 的重载 未重载时 调用全局库操作符new 7 1 1自由存储区内存的分配与释放 4 内存泄漏 memoryleak 和重复释放 new与delete是配对使用的 delete只能释放自由存储区空间 如果new返回的指针值丢失 则所分配的自由存储区空间无法回收 称内存泄漏 同一空间重复释放也是危险的 因为该空间可能已另分配 所以必须妥善保存new返回的指针 以保证不发生内存泄漏 也必须保证不会重复释放自由存储区内存空间 5 动态分配的变量或对象的生命期 无名对象的生命期并不依赖于建立它的作用域 比如在函数中建立的动态对象在函数返回后仍可使用 但必须记住释放该对象所占自由存储区空间 并只能释放一次 在函数内建立 而在函数外释放是一件很容易失控的事 往往会出错 7 1 2自由存储区对象与构造函数 类对象动态建立与删除过程 通过new建立的对象要调用构造函数 通过delete删除对象也要调用析构函数 CGoods pc pc newCGoods 分配自由存储区空间 并构造一个无名的CGoods对象 deletepc 先析构 然后将内存空间返回给自由存储区 自由存储区对象的生命期并不依赖于建立它的作用域 所以除非程序结束 自由存储区对象 无名对象 的生命期不会到期 并且需要显式地用delete语句析构该类对象 上例执行delete语句时 C 自动调用商品类的析构函数 7 1 2自由存储区对象与构造函数 由自由存储区创建对象数组 只能调用默认的构造函数 不能调用其他任何构造函数 如果没有默认的构造函数 则不能创建对象数组 类对象初始化 new后面类 class 类型可以有参数 这些参数即构造函数的参数 但对创建数组 则无参数 只能调用默认的构造函数 例7 3 演示自由存储区对象分配和释放 7 1 3浅复制与深复制 浅复制 默认复制构造函数 可用一个类对象初始化另一个类对象 称为默认的按成员复制 而不是对整个类对象的按位复制 这称为浅复制 图7 1浅复制 如果类中有一个数据成员为指针 该类的一个对象obj1中的这个指针p 指向了动态分配的一个自由存储区对象 参见图7 1复制前 如果用obj1按成员复制了一个对象obj2 这时obj2 p也指向同一个自由存储区对象 obj1 obj1 obj2 7 1 3浅复制与深复制复制 当浅复制析构时 如用默认的析构函数 则动态分配的自由存储区对象不能回收 如果在析构函数中有 deletep 语句 则如果先析构函数obj1时 自由存储区对象已经释放 以后再析构obj2时出现了二次释放的问题 自由存储区对象 P P 自由存储区对象 图7 2深复制 深复制 重新定义复制的构造函数 给每个对象独立分配一个自由存储区对象 称深复制 这时先复制对象主体 再为obj2分配一个自由存储区对象 最后用obj1的自由存储区对象复制obj2的自由存储区对象 obj1 obj2 7 1 3浅复制与深复制 例7 4 定义复制构造函数 copystructor 和复制赋值操作符 copyAssignmentOperator 实现深复制 学生类定义 classstudent char pName 为了演示深复制 不用string类public student 默认构造函数student char pname 带参数构造函数student student 复制赋值操作符 检验主函数和运行结果 7 1 3浅复制与深复制 提示 自由存储区内存是最常见的需要自定义复制构造函数的资源 但不是唯一的 还有打开文件等也需要自定义复制构造函数 如果类对象需要动态分配资源应该由构造函数完成 而释放资源由析构函数完成 这时类也需要一个自定义的复制构造函数 实现对象的深复制 由此可见 构造函数并非仅做初始化工作 7 1 3浅复制与深复制 思考 深入地考虑 例7 4 如果数据域还有很多其他数据 甚至有好几个是动态建立的C字符串 深复制是不是太复杂了 如果使用C 标准字符串string作为成员对象 聚合 是否就不需要考虑深复制了 的确是这样的 准确地说 string类的内部包含动态建立字符数组的操作 其复制构造函数是深复制 如果在student类中使用string类而不是C字符串 就不要再考虑深复制问题了 也就是说 动态内存分配和深复制应该放在一个适当的层面上 一个更单纯的类定义中 如string类 在使用中 把它作为一个成员对象 就像使用string类对象那样 7 1 3浅复制与深复制 探讨 最后进一步讨论类的封装 封装的更高境界是在该类对象中一切都是完备的 自给自足的 不仅有数据和对数据的操作 还包括资源的动态安排和释放 在需要时可以无条件地安全使用 标准string类模板就是典型的例子 这样的类对象 作为另一个类的成员对象使用时 就不会出任何问题 这表明聚合实现了完善的封装 7 2链表与链表的基本操作 线性表是最简单 最常用的一种数据结构 线性表的逻辑结构是n个数据元素的有限序列 a1 a2 an 而线性表的物理结构包括 顺序表 链表 7 2 1单链表基本算法 7 2 3双向链表 选读 7 2 2单链表类型模板 7 2 1单链表基本算法 单链表 SinglyLinkedlist 每个数据元素占用一个结点 Node 一个结点包含两个域 一个域存放数据元素info 其数据类型由应用问题决定 另一个存放指向该链表中下一个结点的指针link infon 1 info2 info1 info0 head 图7 3单链表结构 单链表的第一个结点的地址可通过链表的表头指针head找到 借助结点的指针域 可以从第一个结点开始顺序遍历链表所有结点 head不可丢失 否则链表整个丢失 内存发生泄漏 7 2 1单链表基本算法 结点定义如下 typedefintDatatype 数据为整型structnode Datatypeinfo node link 在C C 中允许结构 或对象 成员是结构自身的指针类型 通过指针引用自身这种类型的结构 但结构成员决不能是结构自身类型 即结构不能自己定义自己 这会导致一个无穷递归的定义 7 2 1单链表基本算法 单链表的插入与删除 只要改变链中结点指针的值 无需移动表中的元素 就能实现插入和删除操作 插入算法有三种情况 我们希望在单链表中包含数据infoi的结点之前插入一个新元素 则infoi可在第一个结点 或在中间结点 如未找到 则把新结点插在链尾结点之后 7 2 1单链表基本算法 newnode infox info0 info1 head 插在链首 首先新结点的link指针指向info0所在结点 然后 head指向新结点 即 newnode link head 注意 链表操作次序非常重要head newnode 7 2 1单链表基本算法 infox infoi 1 infoi p newnode 插在中间 首先用工作指针p找到指定结点 而让指针q指向紧跟其后的结点 令infoi 1所在结点的link指针指向新结点 而后让新结点的link指向infoi所在结点 即 newnode link p 或newnode link q link 可用于插入某结点之后q link newnode 7 2 1单链表基本算法 infox newnode p infon 1 插在队尾 只要工作指针p找到队尾 即可链在其后 p link newnode newnode link NULL 7 2 1单链表基本算法 带表头结构的链表 研究以上算法 插在链表第一个结点之前与其他结点之前的算法有所不同 要使算法中没有特殊者 可以给每一个链表加上一个表头结点 如下图所示 空表如下 下面分别介绍带表头结构的链表的生成链表算法 链表查找算法 插入一个结点的算法和删除一个结点的算法 7 2 1单链表基本算法 head tail p info1 tail p tail 1 向后生成链表算法 node createdown Datatypedata Node head tail p head newnode 建立链表头结点tail head while cin data Ctrl z结束p new node 每输入一个数申请一个结点p info data 添入数据tail link p 新结点接到链尾tail p 尾指针到链尾tail link NULL 链尾加空指针 表示链结束returnhead 返回头指针 7 2 1单链表基本算法 head info0 P P info1 2 向前生成链表算法 node createup node head p Datatypedata head newnode 建立头结点head link NULL while cin data 建立的总是第一个结点p newnode p info data p link head link 新结点放在原链表前方head link p 头结点放新结点之前 returnhead 7 2 1单链表基本算法 3 链表查找算法 按关键字 查找 node traversal node head Datatypedata node p head link while p NULL 7 2 1单链表基本算法 5 删除单链表结点 p后面结点 voiddel node p node q q p link p link q link deleteq 如果要把该结点移入另一个链中 则可将q返回 7 2 2单链表类型模板 例7 5 h 单链表类模板 定义结点类 templateclassList 前向引用声明templateclassNode Tinfo 数据域Node link 指针域 注意结点类格式 尖括号中是参数名表 类模板实例化为类public Node 生成头结点的构造函数Node constT 定义链表类 templateclassList Node head tail 链表头指针和尾指针public List 构造函数 生成头结点 空链表 List 析构函数voidMakeEmpty 清空链表 只余表头结点Node Find Tdata 搜索数据域与data相同的结点 返回该结点的地址intLength 计算单链表长度voidPrintList 打印链表的数据域voidInsertFront Node p 可用来向前生成链表voidInsertRear Node p 可用来向后生成链表voidInsertOrder Node p 按升序生成链表Node CreatNode Tdata 创建结点 孤立结点 Node DeleteNode Node p 删除指定结点 7 2 2单链表类型模板 7 2 2单链表类型模板 例7 5 由键盘输入16个整数 以这些整数作为结点数据 生成两个链表 一个向前生成 一个向后生成 输出两个表 然后给出一个整数在一个链表中查找 找到后删除它 再输出该表 清空该表 再按升序生成链表并输出 在本例中程序只需调用类模板中的成员函数就可以完成所有链表操作 例7 6 以学生类作为链表的数据类 完成学生档案的管理 7 2 2单链表类型模板 讨论复制构造函数 在本例中没有给出Node类的复制构造函数 并非可以使用默认的复制构造函数 而是避开了所有使用它的情况 本例中函数的参数和返回值仅使用指向Node的指针 类定义中也没有用复制方式初始化 定义复制构造函数与类的实际意义和使用方式有关 并非只是深复制和浅复制的问题 通常对Node类复制的结果应是一个孤立结点 templateNode Node Node link域值为NULL 该函数与Node的有参构造函数功能基本相同 考虑到函数的参数和返回值仅使用指向Node的指针 定义复制构造函数已经没有实际意义单链表的复制构造函数和复制运算符是一个复杂的算法 与前文所编的复制构造函数和复制运算符构造相去甚远了 7 2 3双向链表 选读 双向链表引入 考虑单链表只能找后继 如要找前驱 必须从表头开始搜索 为了克服这一缺点 可采用双向链表 DoubleLinkedList 双向链表的结点有三个域 左链接指针 llink 数据域 info 右链接指针域 rlink 双向链表经常采用带头结点的循环链表方式 7 2 3双向链表 选读 双向链表的访问 假设指针p指向双向循环链表的某一个结点 那么 p llink指示P所指结点的前驱结点 p rlink指示后继结点 p llink rlink指示本结点的前驱结点的后继结点 即本结点 间接访问符 可以连续使用 例7 7 双向链表类模板和结点类模板 7 3栈与队列的基本操作及其应用 栈和队都是特殊的线性表 限制存取位置的线性结构 可以由顺序表实现 也可以由链表实现 7 3 1栈 7 3 3队列 7 3 2栈的应用 选读 7 3 1栈 栈的基本概念 栈定义为只允许在表的一端进行插入和删除的线性表 允许进行插入和删除的一端叫做栈顶 top 而另一端叫栈底 bottom 栈中没有任何元素时 称为空栈 进栈时最先进栈的在最下面 最后的在最上面 后来居上 而出栈时顺序相反 最后进栈的最先出栈 而最先进栈的最后出栈 所以栈又称作后进先出 LIFO LastInFirstOut 的线性表 栈可以用顺序表实现 称顺序栈 也可以用链表实现 称链栈 7 3 1栈 栈的基本操作 参见下图 设给定栈s a0 a1 an 1 称a0为栈底 an 1为栈顶 进栈时最先进栈的a0在最下面 an 1在最上面 而出栈时顺序相反 最后进栈的an 1最先出栈 而最先进栈的a0最后出栈 a0 an 2 a1 an 1 bottom 进栈 top top top top top 出栈 图示为顺序栈 其中栈底bottom是指向栈数据区的下一单元 这样判断是否为空栈会更方便 只需top与bottom相同就是空栈 通常只有栈顶与操作有关 7 3 1栈 templateclassStack inttop 栈顶指针 下标 T elements 动态建立的元素intmaxSize 栈最大容纳的元素个数public Stack int 20 构造函数 栈如不指定大小 设为20元素 Stack delete elements voidPush constT 输出栈内所有数据 例7 8 顺序栈的类模板 7 3 1栈 voidmain inti a 10 0 1 2 3 4 5 6 7 8 9 b 10 Stackistack 10 for i 0 i 10 i istack Push a i if istack IsFull cout 栈满 endl istack PrintStack for i 0 i 10 i b i istack Pop if istack IsEmpty cout 栈空 endl for i 0 i 10 i cout b i t 注意先进后出cout endl istack Pop 下溢出 7 3 1栈 例7 9 h 链栈的结点类模板 templateclassNode 链栈结点类模板Tinfo Node link public Node Tdata 0 Node next NULL info data link next friendclassStack 链栈 7 3 1栈 链栈类模板 无头结点链表 templateclassStack 链栈类模板Node top 栈顶指针public Stack top NULL Stack 析构函数voidPush constT 7 3 2栈的应用 选读 顺序栈和链栈逻辑功能是一样 尽管这里两个栈模板的成员函数功能选择稍有出入 因为顺序栈可以随机访问其中的元素 而链栈只能顺序访问 但逻辑上完全可以做到一样 物理结构不同 顺序栈必须先开一定大小内存空间 执行起来简单 速度快 可能溢出 链栈内存空间随用随开 不会溢出 但执行复杂 不断地动态分配 速度慢 顺序栈和链栈比较 7 3 2栈的应用 选读 栈可用于表达式的计算 现考虑最简单的 四个运算符和结束符 组成的算术表达式 只有两个优先级 先 后 为实现运算符的优先级 采用两个栈 一个数栈 一个运算符栈 数栈暂存操作数 运算符栈暂存运算符 栈的使用 表达式运算 b c t1 d e t2 t1 t2 t3 a t3 t4 N 数栈O 运算符 a b c d e 设有 a b c d e 参见上图 从左向右扫描算术表达式 遇到操作数 压入数栈 遇到运算符 则与运算符栈栈顶的运算符比较优先级 若新的运算符优先级高 或运算符栈空 则压栈 否则将栈顶运算符出栈 与数字栈出栈的两个数据进行运算 结果压入数栈 再将新运算符压栈 继续扫描 直到遇到 号 扫描结束 栈中数据继续按前面规则出栈 7 3 2栈的应用 选读 例7 9 模拟简单计算器 该计算器只认 四个运算符 输入为整数 表达式结束符使用 号 清空栈用 c 字符 使用 z 字符表示结束 简易计算器类定义 classCalculator StackNstack 使用链栈StackOstack public Calculator void voidCal void 计算器运算程序voidGetTwoNum int 清除 7 3 3队列 队列的基本概念 队列 Queue 也是一种限定存取位置的线性表 它只允许在表的一端插入 而在另一端删除 允许插入的一端称为队尾 rear 允许删除的一端叫做队头 front 每次在队尾加入新元素 加入称为进队 删除称为出队 队列的这种特性正好与栈相反 叫做先进先出FIFO FirstInFirstOut 图7 15队列 图7 15所示队列随队尾加入元素 队尾 rear 不断向后移 而随队头元素的出队 则队头 front 也不断后移 即位置在变 如要位置不变 移动元素工作量也太大 7 3 2队列 图7 16顺序队列的插入和删除 由图可见 空队时指针 下标 front和rear在一起都指向队前方 当有元素进队 则rear后移 有元素出队 则front后移 最后分配给队的前端不再被利用 顺序表队列的缺点 7 3 2队列 顺序表队列的改进 逻辑上的循环队列 注意 空队时rear front 满队时必须空一个位置 7 3 2队列 循环队列浪费一个位置好像太可惜 特别在该位置中存放一个很大的对象时 实际上对象很大时 总是由索引 指针 来排队 若想利用这个空间 必然加一个标志来表示队空 队满 进队出队都要判断 使用上更不方便 用链表实现队列无此问题 例7 10 顺序存储方式的循环队列类模板 例7 11 链队类模板 链首出队 链尾入队 无链表头结点方式 7 4二叉树 选读 树形结构是一类重要的非线性数据 树和二叉树是常用的树形结构 7 4 2二叉树的遍历 7 4 1二叉树的概念 7 4 3排序二叉树 7 4 1二叉树的概念 选读 树 Tree 是由n n 0 个结点组成的有限集合 如n 0 称为空树 非空树有一个特定的结点 它只有直接后继 没有直接前驱 称之为根 root 除根以外的其它结点划分为m m 0 个互不相交的有限集合T0 T1 Tm 1 每个集合又是一棵树 称为根的子树 subtree 每棵子树的根结点有且仅有一个直接前驱 但可以有0个或多个直接后继 这是一个递归方法定义的数据结构 树的概念 7 4 1二叉树的概念 选读 图7 18树的示意图 结点 包括数据项和多个指针项 指针项数目并不固定 且无次序 结点的度 结点所拥有的子树数量 叶结点 度为0的结点 如G I J K L M N O结点 分支结点 度 1的结点 孩子结点 若结点x有子树 则子树根结点即为x的孩子结点 树的术语 7 4 1二叉树的概念 选读 图7 18树的示意图 双亲结点 若结点x有孩子 它即为孩子的双亲 兄弟结点 同一双亲的结点互称为兄弟 结点的层次 从根到该结点所经路径上的分支条数 树的深度 树中结点的层次数 树的度 树中结点度的最大值 树的术语 7 4 1二叉树的概念 选读 二叉树 BinaryTree 是另一种独立的树形结构 二叉树是结点的一个有限集合 该集合或为空 或是由一个根结点及两棵树分别称为左子树和右子树的 注意有左右之分 互不相交的二叉树组成 其中左右子树分别可以为空子树或均为空树 这也是一个递归的定义 二叉树的特点是 每个结点最多两个孩子 并且子树有左右之分 二叉树的基本性质 1 二叉树的第i层上最多有2i 1 i 1 个结点 2 深度为h的二叉树中最多有2h 1个结点 3 在任一棵二叉树中 有n0个叶子结点 有n2个度为2的结点 则有n0 n2 1 树的概念 7 4 1二叉树的概念 选读 例7 12 画出有三个结点的所有二叉树 解 结果见图7 19 共5种 图7 195种不同的三结点二叉树 7 4 1二叉树的概念 选读 满二叉树和完全二叉树 分别如图7 20和图7 21 完全二叉树已有的结点排序与满二叉树相同 图7 20满二叉树 图7 21完全二叉树 7 4 1二叉树的概念 选读 下面给出链式储存方式的二叉树 每个结点有三个域 数据域 左孩子指针和右孩子指针 见图7 22 图7 22二叉树结点 7 4 1二叉树的概念 选读 二叉树类结点类模板定义 templateclassBinaryTree templateclassNode Node lchild rchild Tinfo public Node lchild NULL rchild NULL Node Tdata Node left NULL Node right NULL info data lchild left rchild right 7 4 1二叉树的概念 选读 TGetinfo returninfo 取得结点数据voidsetinfo constT 二叉树类说明为友元类 7 4 2二叉树的遍历 选读 二叉树的遍历 binarytreetraversal 定义 遵从某种次序 查巡二叉树的所有结点 每个结点都被访问一次 而且仅访问一次 所谓 访问 指对结点施行某些操作 但不破坏它原来的数据结构 遍历二叉树有不同次序 规定先左后右 令L R V分别代表遍历一个结点的左右子树和访问该结点的操作 有三种方式 前序遍历 VLR 中序遍历 LVR 后序遍历 LRV 7 4 2二叉树的遍历 选读 遍历实例 前序遍历访问次序为ABDEGCFH 图7 23二叉树遍历 中序遍历结果为DBGEAFHC 后序遍历结果为DGEBHFCA 7 4 2二叉树的遍历 选读 例7 13 二叉树类模板 其中二叉树生成借用二叉排序树 见下节 特别注意插入结点时 第二参数为指针的引用 否则不能建立树 为什么 请读者自己思考 本例采用简单的接口函数 而把较复杂的算法作为私有函数 templateclassBinaryTree Node root 二叉树的根指针voidInOrder Node Current 中序遍历voidPreOrder Node Current 前序遍历voidPostOrder Node Current 后序遍历voidInsert constT 删除树 7 4 2二叉树的遍历 选读 public BinaryTree root NULL 空树构造函数 BinaryTree Destory root 析构函数voidCreat T data intn 建立 排序 二叉树voidInOrder InOrder root 中序遍历 公有函数为接口voidPreOrder PreOrder root 前序遍历 公有函数为接口voidPostOrder PostOrder root 后序遍历 公有函数为接口 检验主函数 7 4 2二叉树的遍历 选读 例7 14 某二叉树先序遍历为ABCEFDGHIJK 中序遍历为ECFBDGAIHJK绘出该二叉树 图7 24例7 14二叉树 按同样方法推出A的右子树 结果如图7 23 可以证明已知先序和中序访问次序可以唯一确定一棵二叉树 解 由先序知A为根结点 而由中序知ECFBDG为左子树 IHJK为右子树 由先序中的BCEFDG知B为左子树根结点 由中序中的ECFBDG知ECF为其左子树 而DG为右子树 再由先序CEF知C为左子树根结点 由中序ECF知E为C左子树 F为的右子树 再由先序DG知 D为B的右子树根结点 由中序DG知G为D的右子树 7 4 3排序二叉树 选读 二叉排序树 BinarySortingTree 又称二叉搜索树 BinarySearchTree 是一种特殊结构的二叉数 作为一种排序和查找的手段 对应有序表的对半查找 通常亦被称为数表 其定义也是递归的 二叉排序树的定义 二叉排序树或者是空树或者是具有下述性质的二叉数 其左子树上所有结点的数据值均小于根结点的数据值 右子树上所有结点的数据值均大于等于根结点的数据值 左子树和右子树又各是一棵二叉排序树 7 4 3排序二叉树 选读 二叉排序树用中序遍历就可以得到由小到大的有序序列 如图7 24可得有序序列 8 10 11 12 15 16 18 22 24 26 29 图7 24二叉排序树例 二叉排序树的遍历 二叉排序树生成算法 对任意一组数据元素序列 a0 a1 a2 an 1 要生成二叉排序树的过程为 1 令a0为二叉树的根结点 2 若a1 a0 令a1为a0左子树的根结点 否则a1为a0右子树的根结点 3 如ai小于根结点 则去左子树 否则去右子树 按此法查找 直到成为空树 则安放此位置 这步就是插入算法 7 4 3排序二叉树 选读 7 4 3排序二叉树 选读 templateNode BinaryTree Find constT 例7 15 排序二叉树查找函数 算法 用中序遍历即可 但递归慢 下面为迭代查找算法 第七章动态内存分配与数据结构 完 谢谢 7 1 1自由存储区内存的分配与释放 例7 1 例7 1 动态数组的建立与撤销 include includeusingnamespacestd intmain intn char pc cout n 在运行时确定 可输入25pc newchar n strcpy pc 自由存储区内存的动态分配 cout pc endl delete pc 释放pc所指向的n个字符的内存空间return0 7 1 1自由存储区内存的分配与释放 例7 2 例7 2 动态创建和删除一个m n个元素的数组 采用指针数组方式来完成二维数组的动态创建 选读 intm 4 n 6 行数与列数二维数组的动态创建 intmain double data inti j data newdouble m 建立指向组成二维数组各行的指针数组if data 0 cout Couldnotallocate Bye return 1 for j 0 j m j data j newdouble n 建立各行if data j 0 cout Couldnotallocate Bye return 1 7 1 1自由存储区内存的分配与释放 例7 2 for i 0 i m i for j 0 j n j data i j i n j 数组元素赋值display data 略de allocate data return0 二维数组的撤销与内存释放 voidde allocate double data inti for i 0 i m i delete data i 注意撤销次序 与设置相反delete data 7 1 2自由存储区对象与构造函数 例7 3 类说明 classCGoods stringName intAmount floatPrice floatTotal value public CGoods cout 调用默认构造函数 endl CGoods stringname intamount floatprice cout 调用三参数构造函数 endl Name name Amount amount Price price Total value price amount CGoods cout 调用析构函数 endl 例7 3 演示自由存储区对象分配和释放 7 1 2自由存储区对象与构造函数 例7 3 使用 intmain intn CGoods pc pc1 pc2 pc newCGoods 夏利2000 10 118000 调用三参数构造函数pc1 newCGoods 调用默认构造函数cout n pc2 newCGoods n 动态建立数组 不能初始化 调用n次默认构造函数 deletepc deletepc1 delete pc2 return0 例7 4实现深复制 默认构造函数 student student cout Constructor pName NULL cout 默认 endl 带参数构造函数 student student char pname cout Constructor if pName newchar strlen pname 1 strcpy pName pname cout pName endl 例7 4实现深复制 复制构造函数 student student student 析构函数 student student cout Destructor pName endl if pName pName 0 0 delete pName 释放字符串 例7 4实现深复制 复制赋值操作符 student intmain void students1 范英明 s2 沈俊 s3 students4 s1 s3 s2 return0 例7 4实现深复制 例7 5 h单链表类型模板 templateNode Node link NULL templateNode Node constT 例7 5 h单链表类型模板 链表类成员函数 templateList List head tail newNode templateList List MakeEmpty deletehead templatevoidList MakeEmpty 清空链表Node tempP while head link NULL tempP head link head link tempP link 把头结点后的第一个结点从链中脱离deletetempP 删除 释放 脱离下来的结点tail head 表头指针与表尾指针均指向表头结点 表示空链 例7 5 h单链表类型模板 链表类成员函数 templateNode List Find Tdata Node tempP head link while tempP NULL 例7 5 h单链表类型模板 链表类成员函数 templatevoidList PrintList 显示链表Node tempP head link while tempP NULL coutinfolink coutvoidList InsertFront Node p p link head link head link p if tail head tail p templatevoidList InsertRear Node p p link tail link tail link p tail p 链表类成员函数 templatevoidList InsertOrder Node p Node tempP head link tempQ head tempQ指向tempP前面的一个结点while tempP NULL if p infoinfo break 找第一个比插入结点大的结点 由tempP指向tempQ tempP tempP tempP link tempQ InsertAfter p 插在tempP指向结点之前 tempQ之后if tail tempQ tail tempQ link templateNode List CreatNode Tdata Node tempP newNode data returntempP 例7 5 h单链表类型模板 链表类成员函数 templateNode List DeleteNode Node p Node tempP head while tempP link NULL 本函数所用方法可省一个工作指针 与InsertOrder比较 例7 5 h单链表类型模板 例7 5单链表类型模板主函数 voidmain Node P1 Listlist1 list2 inta 16 i j cout a i 随机输入16个整数for i 0 i 16 i P1 list1 CreatNode a i list1 InsertFront P1 向前生成list1P1 list2 CreatNode a i list2 InsertRear P1 向后生成list2list1 PrintList cout list1长度 list1 Length endl list2 PrintList 例7 5单链表类型模板主函数 cout j P1 list1 Find j if P1 NULL P1 list1 DeleteNode P1 deleteP1 list1 PrintList cout list1长度 list1 Length endl elsecout 未找到 endl list1 MakeEmpty 清空list1for i 0 i 16 i P1 list1 CreatNode a i list1 InsertOrder P1 升序创建list1list1 PrintList return0 例7 6学生档案的管理 include Ex7 6 h classstudent intid stringname charsex intage stringaddress floateng phy math electron 英语 物理 数学和电子学成绩public student int 0 string char 0 int 0 string float 0 0 float 0 0 float 0 0 float 0 0 booloperator studentele returnid ele id booloperator studentele returnid ele id voidshow cout id t name t sex t age t address t eng t phy t math t electron endl 例7 6学生档案的管理 注意 链表类定义中输出函数PrintList 改写为 templatevoidList PrintList Node tempP head link while tempP NULL tempP info show tempP tempP link cout endl 在student类中采用show 函数是一个无奈的选择 因为插入运算符 的重载在9 3 3节才学 那时就不需要改写PrintList 而在student类中重载插入运算符 例7 6学生档案的管理 intmain constinth 4 inti j Node P1 Listlist1 list2 studentn h student 6004327 张菲 m 19 北京路58号 80 85 90 78 student 6004121 关雨 w 19 天津路64号 88 75 91 68 student 6004118 刘蓓 w 18 上海路37号 78 95 81 88 student 6004219 赵昀 m 18 重庆路95号 78 95 81 88 for i 0 i h i P1 list1 CreatNode n i list1 InsertFront P1 向前生成list1P1 list2 CreatNode n i list2 InsertRear P1 向后生成list2list1 PrintList 例7 6学生档案的管理 cout j P1 list1 Find j 学号由构造函数转换为学生类if P1 NULL P1 list1 DeleteNode P1 deleteP1 list1 PrintList cout list1长度 list1 Length endl elsecout 未找到 endl list1 MakeEmpty 清空list1for i 0 i h i P1 list1 CreatNode n i list1 InsertOrder P1 升序创建list1list1 PrintList return0 例7 7 双向链表类模板和结点类模板 双链表结点模板类 templateclassDblNode Tinfo 数据域DblNode llink rli