第七章第七章 动态内存分配与数据结构动态内存分配与数据结构本章首先介绍程序运行时本章首先介绍程序运行时动态内存分配动态内存分配（dynamic dynamic memory allocationmemory allocation）的概念与方法。进一步讨论复制）的概念与方法。进一步讨论复制构造函数构造函数. .然后学习更多有关然后学习更多有关数据结构数据结构的基本知识，包括的基本知识，包括链表链表，栈栈，队队，二叉树二叉树等的基本算法和应用。等的基本算法和应用。模板模板是标准是标准C+实现代码复用的有力工具，特别是有关数据结构实现代码复用的有力工具，特别是有关数据结构的算法，本章继续使用。的算法，本章继续使用。自由存储区内存分配自由存储区内存分配 二叉树二叉树 （选读）（选读） 7.3 栈与队列的基本操作及其应用栈与队列的基本操作及其应用 7.2 链表与链表的基本操作链表与链表的基本操作 第七章第七章 动态内存分配与数据结构动态内存分配与数据结构自由存储区内存分配自由存储区内存分配 自由存储区自由存储区内存内存的分配与释放的分配与释放 自由存储区自由存储区对象对象与构造函数与构造函数 7.1.3 浅复制与深复制浅复制与深复制 静态存储分配：静态存储分配：通常定义变量通常定义变量( (或对象或对象) )，编译器，编译器在编译时都可以根据该变量在编译时都可以根据该变量( (或对或对象象) )的类型知道所需内存空间的大的类型知道所需内存空间的大小，从而系统在适当的时候为它小，从而系统在适当的时候为它们分配确定的存储空间。们分配确定的存储空间。动态存储分配：动态存储分配：有些操作对象只有在程序运行时有些操作对象只有在程序运行时才能确定，这样编译器在编译时才能确定，这样编译器在编译时就无法为他们预定存储空间，只就无法为他们预定存储空间，只能在程序运行时，系统根据运行能在程序运行时，系统根据运行时的要求进行内存分配，称为动时的要求进行内存分配，称为动态存储分配。动态分配都在态存储分配。动态分配都在自由自由存储区存储区中进行。中进行。自由存储区自由存储区内存的分配与释放内存的分配与释放当当程程序序运运行行到到需需要要一一个个动动态态分分配配的的变变量量或或对对象象时时，必必须须向向系系统统申申请请取取得得自自由由存存储储区区中中的的一一块块所所需需大大小小的的存存贮贮空空间间，用用于于存存贮贮该该变变量量或或对对象象。当当不不再再使使用用该该变变量量或或对对象象时时，也也就就是是它它的的生生命命结结束束时时，要要显显式式释释放放它它所所占占用用的的存存贮贮空空间间，这这样样系系统统就就能能进进行再次分配，做到重复使用有限的资源。行再次分配，做到重复使用有限的资源。 申请和释放申请和释放自由存储区自由存储区中分配的存贮空间，分别使用中分配的存贮空间，分别使用newnew和和deletedelete的两个运算符来完成，其使用的格式如下：的两个运算符来完成，其使用的格式如下：指针变量名指针变量名=new =new 类型名类型名( (初始化式初始化式) )；delete delete 指针名指针名; ;newnew运算符运算符返回返回的是一个指向所分配类型变量（对象）的的是一个指向所分配类型变量（对象）的指指针针。对所创建的变量或对象，都是通过该指针来间接操作的，。对所创建的变量或对象，都是通过该指针来间接操作的，而而动态创建的对象本身没有名字。动态创建的对象本身没有名字。 动态分配与释放：动态分配与释放： 自由存储区自由存储区内存的分配与释放内存的分配与释放一般定义变量和对象时要用标识符命名，称一般定义变量和对象时要用标识符命名，称命名对象命名对象，而动态，而动态的称的称无名对象无名对象( (请注意与栈区中的临时对象的区别，两者完全请注意与栈区中的临时对象的区别，两者完全不同：生命期不同，操作方法不同，临时变量对程序员是透明不同：生命期不同，操作方法不同，临时变量对程序员是透明的的) )。自由存储区自由存储区是不会自动在分配时做初始化的（包括清零）是不会自动在分配时做初始化的（包括清零），所以必须用初始化式，所以必须用初始化式(initializer)(initializer)来显式初始化。来显式初始化。newnew表达式的操作：表达式的操作：从自由存储区分配对象，然后用括号中的值初始化该对象从自由存储区分配对象，然后用括号中的值初始化该对象。分配对象时，分配对象时，new表达式调用库操作符表达式调用库操作符new()：int*pi=newint(0);pi现在所指向的变量的存储空间是由库操作符现在所指向的变量的存储空间是由库操作符new()分配的，分配的，位于程序的自由存储区中，并且该对象未命名。位于程序的自由存储区中，并且该对象未命名。 无名对象：无名对象： 自由存储区自由存储区内存的分配与释放内存的分配与释放自由存储区自由存储区i演示：演示：用初始化式用初始化式(initializer)(initializer)来显式初始化来显式初始化 int *pi=new int(0);int *pi=new int(0);当当pipi生命周期结束时，生命周期结束时，必须释放必须释放pipi所指向的目标：所指向的目标： delete pi;delete pi;注意这时释放了注意这时释放了pipi所指的目标的内存空间，也就是撤销了该所指的目标的内存空间，也就是撤销了该目标，称动态内存释放（目标，称动态内存释放（dynamic memory deallocationdynamic memory deallocation），），但但指针指针pipi本身并没有撤销本身并没有撤销，该指针所占内存空间并未释放。，该指针所占内存空间并未释放。 自由存储区自由存储区内存的分配与释放内存的分配与释放数组动态分配格式：数组动态分配格式：指针变量名指针变量名=new =new 类型名类型名 下标表达式下标表达式;Delete Delete 指向该数组的指针变量名指向该数组的指针变量名; ;说明：说明：两式中的两式中的方括号方括号必须配对使用。必须配对使用。如如果果delete语语句句中中少少了了方方括括号号，因因编编译译器器认认为为该该指指针针是是指指向向数数组组第第一一个个元元素素的的指指针针，会会产产生生回回收收不不彻彻底底的的问问题题（只只回回收收了了第第一一个个元元素素所所占占空空间间），加加了了方方括括号号后后就就转转化化为为指指向数组的指针，回收整个数组向数组的指针，回收整个数组。delete的方括号中的方括号中不需要不需要填填数组元素数数组元素数，系统自知。，系统自知。即使写了，编译器也忽略。即使写了，编译器也忽略。请注意请注意“下标表达式下标表达式”不是常量表达式不是常量表达式，即它的值不必，即它的值不必在编译时确定，在编译时确定，可以在运行时确定可以在运行时确定。自由存储区自由存储区内存的分配与释放内存的分配与释放动态分配数组与动态分配数组与标准字符串类标准字符串类：标准字符串类标准字符串类string就是采用动态建立数组的方式解决就是采用动态建立数组的方式解决数组溢出的问题的，例所做的动态内存分配与释放，在数组溢出的问题的，例所做的动态内存分配与释放，在string类对象中都是自动完成的，在程序中不需要也不允类对象中都是自动完成的，在程序中不需要也不允许再显式地为许再显式地为string进行动态内存的分配与释放。进行动态内存的分配与释放。【例【例7.1】动态数组的建立与撤销动态数组的建立与撤销自由存储区自由存储区内存的分配与释放内存的分配与释放动态分配数组的特点：动态分配数组的特点：1.变量变量n在编译时没有确定的值，而是在运行中输入，在编译时没有确定的值，而是在运行中输入，按运行按运行时所需分配空间时所需分配空间，这一点是动态分配的优点，可克服数组，这一点是动态分配的优点，可克服数组“大开小用大开小用”的弊端，在表、排序与查找中的算法，若用的弊端，在表、排序与查找中的算法，若用动态数组，通用性更佳。动态数组，通用性更佳。deletepc是将是将n个字符的空间释个字符的空间释放，而用放，而用deletepc则只释放了一个字符的空间；则只释放了一个字符的空间；2.如果有如果有char*pc1，令，令pc1=pc，同样可用，同样可用deletepc1来释放该空间。尽管来释放该空间。尽管C+不对数组作边界检查，但不对数组作边界检查，但在在自由自由存储区存储区空间分配时，对数组分配空间大小是纪录在案的空间分配时，对数组分配空间大小是纪录在案的。3.没有初始化式（没有初始化式（initializer），），不可对数组初始化不可对数组初始化。 自由存储区自由存储区内存的分配与释放内存的分配与释放（选读）（选读）多维数组动态分配：多维数组动态分配：new 类型名类型名下标表达式下标表达式1 下标表达式下标表达式2;建立一个动态三维数组建立一个动态三维数组float (*cp)3020 ; /指向一个指向一个30行行20列数组的指针列数组的指针cp=new float 15 30 20; /建立由建立由15个个30*20数组组成的数组；数组组成的数组；注意注意cp等效于三维数组名，但没有指出其边界，即等效于三维数组名，但没有指出其边界，即最高维的元素数量，就像指向字符的指针即等效一个最高维的元素数量，就像指向字符的指针即等效一个字符串字符串,不要把指向字符的指针，说成指向字符串的不要把指向字符的指针，说成指向字符串的指针指针。这与数组的嵌套定义相一致。这与数组的嵌套定义相一致。自由存储区自由存储区内存的分配与释放内存的分配与释放（选读）（选读）比较：比较：float(*cp) 30 20; /三级指针三级指针float (*bp) 20; /二级指针二级指针cp=new float 1 30 20;bp=new float 30 20;两个数组都是由两个数组都是由600个浮点数组成，前者是只有个浮点数组成，前者是只有一个元素一个元素的三维数组的三维数组，每个元素为，每个元素为30行行20列的二维数组，而另一列的二维数组，而另一个是有个是有30个元素的二维数组个元素的二维数组，每个元素为，每个元素为20个元素的一个元素的一维数组。维数组。删除这两个动态数组可用下式：删除这两个动态数组可用下式：delete cp; /删除（释放）三维数组删除（释放）三维数组delete bp; /删除（释放）二维数组删除（释放）二维数组【例【例7.2】动态创建和删除一个动态创建和删除一个m*n个元素的数组个元素的数组自由存储区自由存储区的分配与释放的分配与释放指针使用的要点：指针使用的要点：1. 动态分配失败动态分配失败。返回一个空指针（。返回一个空指针（NULL），表示发生了异常，），表示发生了异常，堆资源不足，分配失败。堆资源不足，分配失败。2.指针删除与指针删除与自由存储区自由存储区空间释放空间释放。删除一个指针。删除一个指针p（deletep;）实际意思是删除了）实际意思是删除了p所指的目标（变量或对象等），所指的目标（变量或对象等），释放了它所占的释放了它所占的自由存储区自由存储区空间，而不是删除本身，释空间，而不是删除本身，释放自由存储区空间后，成了放自由存储区空间后，成了空悬指针空悬指针。空悬指针是程序。空悬指针是程序错误的一个根源）。建议这时将置空（错误的一个根源）。建议这时将置空（NULL）。）。3.new()和和delete()是可以重载的是可以重载的，它们都是类的静态，它们都是类的静态成员函数。程序员无需显式声明它为静态的，系统自动成员函数。程序员无需显式声明它为静态的，系统自动定义为静态的。本教材不讨论定义为静态的。本教材不讨论new()和和delete()的重载。的重载。未重载时，调用全局库操作符未重载时，调用全局库操作符new()。自由存储区自由存储区内存的分配与释放内存的分配与释放4内存泄漏（内存泄漏（memory leak）和重复释放）和重复释放。new与与delete 是配对使用的，是配对使用的， delete只能释放只能释放自由存储区自由存储区空间。空间。如果如果new返回的指针值丢失，则所分配的返回的指针值丢失，则所分配的自由存储区自由存储区空间空间无法回收，称内存泄漏，同一空间重复释放也是危险的，无法回收，称内存泄漏，同一空间重复释放也是危险的，因为因为该空间可能已另分配该空间可能已另分配，所以必须妥善保存，所以必须妥善保存new返回的返回的指针，以保证不发生内存泄漏，也必须保证不会重复释放指针，以保证不发生内存泄漏，也必须保证不会重复释放自由存储区自由存储区内存空间。内存空间。5动态分配的变量或对象的生命期动态分配的变量或对象的生命期。无名对象的生命期无名对象的生命期并不依赖于建立它的作用域，比如在函数中建立的动态对并不依赖于建立它的作用域，比如在函数中建立的动态对象在函数返回后仍可使用象在函数返回后仍可使用。但必须记住释放该对象所占。但必须记住释放该对象所占自自由存储区由存储区空间，并只能释放一次，在函数内建立，而在函空间，并只能释放一次，在函数内建立，而在函数外释放是一件很容易数外释放是一件很容易失控失控的事，往往会出错。的事，往往会出错。 自由存储区自由存储区对象与构造函数对象与构造函数 类对象动态建立与删除过程：类对象动态建立与删除过程：通过通过newnew建立的对象要调用构造函数，通过建立的对象要调用构造函数，通过deletedelete删除对象删除对象也要调用析构函数。也要调用析构函数。CGoods*pc;pc=newCGoods;/分配自由存储区空间，并构造一个无名的分配自由存储区空间，并构造一个无名的CGoods对象；对象；.deletepc;/先析构，然后将内存空间返回给自由存储区；先析构，然后将内存空间返回给自由存储区；自由存储区自由存储区对象的生命期并不依赖于建立它的作用域，所以对象的生命期并不依赖于建立它的作用域，所以除非程序结束，除非程序结束，自由存储区自由存储区对象（无名对象）的生命期不会对象（无名对象）的生命期不会到期，并且需要显式地用到期，并且需要显式地用delete语句析构该类对象，上例执语句析构该类对象，上例执行行delete语句时，语句时，C+自动调用商品类的析构函数。自动调用商品类的析构函数。自由存储区自由存储区对象与构造函数对象与构造函数由由自自由由存存储储区区创创建建对对象象数数组组，只只能能调调用用默默认认的的构构造造函函数数，不不能能调调用用其其他他任任何何构构造造函函数数。如如果果没没有默认的构造函数，则不能创建对象数组。有默认的构造函数，则不能创建对象数组。类对象初始化：类对象初始化：new后面类（后面类（class）类型可以有参数。这些参数即构造函数的）类型可以有参数。这些参数即构造函数的参数。但对参数。但对创建数组创建数组，则无参数，则无参数，只能调用默认的构造函数只能调用默认的构造函数。【例【例7.37.3】演示自由存储区对象分配和释放。演示自由存储区对象分配和释放。浅复制与深复制浅复制与深复制 浅复制：浅复制：默认复制构造函数默认复制构造函数，可用一个类对象初，可用一个类对象初始化另一个类对象，称为默认的始化另一个类对象，称为默认的按成员复制，按成员复制，而不是对而不是对整个类对象的整个类对象的按位复制。按位复制。这称为这称为浅复制。浅复制。 图图7.1 浅复制浅复制 P自自 由由 存存储储 区区 对对象象自自 由由 存存储储 区区 对对象象PP 复制前复制前复制后复制后 如果类中有一个数据成员为指针，该类的一个对象如果类中有一个数据成员为指针，该类的一个对象obj1中中的这个指针的这个指针p，指向了动态分配的一个，指向了动态分配的一个自由存储区自由存储区对象，（参见对象，（参见图复制前），如果用图复制前），如果用obj1按成员复制了一个对象按成员复制了一个对象obj2，这时也，这时也指向同一个指向同一个自由存储区自由存储区对象。对象。obj1obj1obj2浅复制与深复制复制浅复制与深复制复制当当浅复制浅复制析构时，如用默认的析构析构时，如用默认的析构函数，则动态分配的函数，则动态分配的自由存储区自由存储区对象不对象不能回收。如果在析构函数中有能回收。如果在析构函数中有“delete p;”语句，则如果先析构函数语句，则如果先析构函数obj1时，时，自由存储区自由存储区对象已经释放，以后再析构对象已经释放，以后再析构obj2时出现了二次释放的问题。时出现了二次释放的问题。自自 由由存存 储储区区 对对象象PP自自 由由存存 储储区区 对对象象 图图7.2 深复制深复制 深复制：深复制：重新定义复制的构造函数，重新定义复制的构造函数，给每个对象独立分配一个给每个对象独立分配一个自由存储区自由存储区对象，称对象，称深复制深复制。这时先复制对象主这时先复制对象主体，再为体，再为obj2分配一个分配一个自由存储区自由存储区对对象，最后用象，最后用obj1的的自由存储区自由存储区对象复对象复制制obj2的的自由存储区自由存储区对象。对象。 obj1obj2浅复制与深复制浅复制与深复制【例【例7.4】定义复制构造函数定义复制构造函数 （copy structor）和复制赋值操）和复制赋值操作符（作符（copy Assignment Operator）实现深复制。）实现深复制。 学生类定义：学生类定义：classstudentchar*pName;/为了演示深复制，不用为了演示深复制，不用string类类public:student();/默认构造函数默认构造函数student(char*pname);/带参数带参数构造函数构造函数student(student&s);/复制构造函数复制构造函数student();/析构函数析构函数student&operator=(student&s);/复制赋值操作复制赋值操作符符检验检验主函数主函数和和运行结果运行结果浅复制与深复制浅复制与深复制提示：提示：自由存储区内存是最常见的需要自定义复制构自由存储区内存是最常见的需要自定义复制构造函数的资源，但不是唯一的，还有打开文件等也造函数的资源，但不是唯一的，还有打开文件等也需要自定义复制构造函数。需要自定义复制构造函数。如果类对象需要动态分配资源应该由构造函数如果类对象需要动态分配资源应该由构造函数完成，而释放资源由析构函数完成，这时类也需要完成，而释放资源由析构函数完成，这时类也需要一个自定义的复制构造函数，实现对象的深复制。一个自定义的复制构造函数，实现对象的深复制。由此可见，由此可见，构造函数并非仅做初始化工作构造函数并非仅做初始化工作。浅复制与深复制浅复制与深复制思考：思考： 深入地考虑【例深入地考虑【例7.47.4】，如果数据域还有很多其他数据，】，如果数据域还有很多其他数据，甚至有好几个是动态建立的甚至有好几个是动态建立的C C字符串，深复制是不是太复杂字符串，深复制是不是太复杂了？如果使用了？如果使用C+C+标准字符串标准字符串stringstring作为成员对象（聚合）作为成员对象（聚合）是否就不需要考虑深复制了？是否就不需要考虑深复制了？的确是这样的，准确地说，的确是这样的，准确地说，string类的内部包含动态建立字类的内部包含动态建立字符数组的操作，其复制构造函数是深复制。如果在符数组的操作，其复制构造函数是深复制。如果在student类中使用类中使用string类而不是类而不是C字符串，就不要再考虑深复制问字符串，就不要再考虑深复制问题了。也就是说，动态内存分配和深复制应该放在一个适当题了。也就是说，动态内存分配和深复制应该放在一个适当的层面上，一个更单纯的类定义中，如的层面上，一个更单纯的类定义中，如string类。在使用中，类。在使用中，把它作为一个成员对象，就像使用把它作为一个成员对象，就像使用string类对象那样。类对象那样。浅复制与深复制浅复制与深复制探讨：探讨：最后进一步讨论类的封装。封装的更高境界是最后进一步讨论类的封装。封装的更高境界是在该类对象中一切都是完备的、自给自足的，不仅在该类对象中一切都是完备的、自给自足的，不仅有数据和对数据的操作，还包括资源的动态安排和有数据和对数据的操作，还包括资源的动态安排和释放。在需要时可以无条件地安全使用。标准释放。在需要时可以无条件地安全使用。标准string类模板就是典型的例子。这样的类对象，作类模板就是典型的例子。这样的类对象，作为另一个类的成员对象使用时，就不会出任何问题。为另一个类的成员对象使用时，就不会出任何问题。这表明这表明聚合实现了完善的封装聚合实现了完善的封装。 7.2 链表与链表的基本操作链表与链表的基本操作 线性表线性表是最简单，最常用的一种数据结构。线性表的是最简单，最常用的一种数据结构。线性表的逻辑结构是逻辑结构是n个数据元素的有限序列（个数据元素的有限序列（a1,a2,an）。而）。而线性表的线性表的物理结构物理结构包括：顺序表，包括：顺序表，链表链表 。7.2.1 单链表基本算法单链表基本算法 7.2.3 双向链表双向链表(选读选读)单链表类型模板单链表类型模板 7.2.1 单链表基本算法单链表基本算法单链表单链表（Singly Linked list）：）： 每每个个数数据据元元素素占占用用一一个个节节点点（Node）。一一个个节节点点包包含含两两个个域域，一一个个域域存存放放数数据据元元素素info，其其数数据据类类型型由由应应用用问问题题决决定；另一个存放指向该链表中下一个节点的指针定；另一个存放指向该链表中下一个节点的指针link。节点定义如下：节点定义如下： typedefintDatatype;/数据为整型数据为整型structnodeDatatypeinfo;node*link;在在C/C+中允许结构（或对象）成员是中允许结构（或对象）成员是结构自身的指针类型结构自身的指针类型，通过指针引用自身这种类型的结构。通过指针引用自身这种类型的结构。但结构成员决不能是结但结构成员决不能是结构自身类型构自身类型，即结构不能自己定义自己，这会导致一个无穷，即结构不能自己定义自己，这会导致一个无穷递归的定义。递归的定义。 7.2.1 单链表基本算法单链表基本算法单链表的第一个结点的地址可通过链表的表头指针单链表的第一个结点的地址可通过链表的表头指针head找到，找到， head在使用中千万不可丢失，否则链表整个丢失，内在使用中千万不可丢失，否则链表整个丢失，内存也发生泄漏。存也发生泄漏。infon-1 info2 info1 info0 head图图7.3 单链表结构单链表结构 单链表的插入与删除：单链表的插入与删除：只要改变链中结点指针的值，无需移动表中的元素，就只要改变链中结点指针的值，无需移动表中的元素，就能实现插入和删除操作。能实现插入和删除操作。插入算法有插入算法有三种三种情况，我们希望在单链表中包含数据情况，我们希望在单链表中包含数据infoi的结点之前插入一个新元素，则的结点之前插入一个新元素，则infoi可在第一个结点，可在第一个结点，或在中间结点，如未找到，则把新结点插在链尾结点之后。或在中间结点，如未找到，则把新结点插在链尾结点之后。 7.2.1 单链表基本算法单链表基本算法newnodeinfoxinfo0info1headhead插在链首：插在链首： 首首先先新新结结点点的的link指指针针指指向向info0所所在在结结点点，然然后后，head指指向向新结点。即：新结点。即：newnodelink=head；/注意：链表操作次序非常重要注意：链表操作次序非常重要head=newnode；7.2.1 单链表基本算法单链表基本算法infoxinfoi-1infoipnewnode插在中间：插在中间： 首首先先用用工工作作指指针针p找找到到指指定定结结点点，而而让让指指针针q指指向向紧紧跟跟其其后后的的结结点点，令令infoi-1所所在在结结点点的的link指指针针指指向向新新结结点点，而而后后让让新新结结点点的的link指向指向infoi所在结点。即：所在结点。即：newnodelink=p；/或或newnodelink=qlink；可用于插入某结点之后；可用于插入某结点之后qlink=newnode；7.2.1 单链表基本算法单链表基本算法infoinfox x newnodepinfoinfon-1n-1插在队尾：插在队尾：只要工作指针只要工作指针p找到队尾，即可链在其后：找到队尾，即可链在其后：plink=newnode；=NULL;7.2.1 单链表基本算法单链表基本算法带表头结构的链表：带表头结构的链表：研研究究以以上上算算法法，插插在在链链表表第第一一个个结结点点之之前前与与其其他他结结点点之之前前的的算算法法有有所所不不同同。要要使使算算法法中中没没有有特特殊殊者者，可可以以给给每每一一个个链链表表加上一个加上一个表头结点表头结点，如下图所示。，如下图所示。空表如下：空表如下：headinfo0Infon-1info1head 下面分下面分别介介绍带表表头结构构的的链表的生成表的生成链表算法、表算法、链表表查找算法、插入一个找算法、插入一个结点的算法和点的算法和删除一个除一个结点的算法。点的算法。 7.2.1 单链表基本算法单链表基本算法headtailpinfo1tailpinfo0tail1. 1. 向后生成链表算法：向后生成链表算法：node *createdown() Datatype data;Node*head,*tail,*p; head=new node; /建立链表头结点建立链表头结点 tail=head;while(cindata) /回车结束回车结束 p=new(node);/每输入一个数申请一个结点每输入一个数申请一个结点p-info=data; /添入数据添入数据tail-link= p; /新结点接到链尾新结点接到链尾 tail=p; /尾指针到链尾尾指针到链尾 tail-link=NULL;/链尾加空指针，表示链结束链尾加空指针，表示链结束 return head; /返回头指针返回头指针 7.2.1 单链表基本算法单链表基本算法headinfo0 PPinfo12. 2. 向前生成链表算法：向前生成链表算法：node *createup() node *head,*p; Datatype data; head=new node; /建立头结点建立头结点 head-link=NULL; while(cindata) /建立的总是第一个结点建立的总是第一个结点 p=new node; p-info=data; p-link= head-link ;/新结点放在原链表前方新结点放在原链表前方 head-link=p; /头结点放新结点之前头结点放新结点之前 return head;7.2.1 单链表基本算法单链表基本算法3.3.链表查找算法链表查找算法( (按关键字按关键字) )查找：查找：node *traversal(node *head,Datatype data) node *p=head-link; while(p!=NULL&p-info!=data) p=p-link; return p; /p为为NULL则未找到则未找到返回值为指针返回值为指针p，指向链表中找到的结点。，指向链表中找到的结点。4. 4. 在单链表的在单链表的p p节点后插入节点后插入：注意只有一种情况。注意只有一种情况。voidinsert(node *p,Datatype x) node *q=new node; q-info=x; q-link=p-link; p-link=q;7.2.1 单链表基本算法单链表基本算法5. 5. 删除单链表节点删除单链表节点*p*p后面节点：后面节点：void del (node *p) node *q; q=p-link; p-link=q-link; delete q; /如果要把该节点移入另一个链中，则可将如果要把该节点移入另一个链中，则可将q返回。返回。7.2.2 单链表类型模板单链表类型模板【例】【例】单链表类模板单链表类模板。定义结点类：定义结点类：templateclassList;templateclassNodeTinfo;/数据域数据域Node*link;/指针域，注意结点类格式，尖括号中是参数名表，类模板实例化为类指针域，注意结点类格式，尖括号中是参数名表，类模板实例化为类public:Node();/生成生成头结点的构造函数头结点的构造函数Node(constT&data);/生成生成一般结点的构造函数一般结点的构造函数voidInsertAfter(Node*p);/在当前在当前结点后插入结点后插入一个结点一个结点Node*RemoveAfter();/删除当前结点的后继删除当前结点的后继结点结点friendclassList;/以以List为友元类，为友元类，List可直接访问可直接访问Node的私有函数的私有函数;定义链表类定义链表类: :templateclassListNode*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.57.5】由由键键盘盘输输入入1616个个整整数数，以以这这些些整整数数作作为为结结点点数数据据，生生成成两两个个链链表表，一一个个向向前前生生成成，一一个个向向后后生生成成，输输出出两两个个表表。然然后后给给出出一一个个整整数数在在一一个个链链表表中中查查找找，找找到到后后删删除除它它，再输出该表。清空该表，再按升序生成链表并输出。再输出该表。清空该表，再按升序生成链表并输出。在本例中程序只需调用类模板中的成员函数就可以完成所在本例中程序只需调用类模板中的成员函数就可以完成所有链表操作。有链表操作。【例【例7.67.6】以学生类作为链表的数据类，完成学生档案的管以学生类作为链表的数据类，完成学生档案的管理。理。7.2.2 单链表类型模板单链表类型模板讨论复制构造函数：讨论复制构造函数：在本例中没有给出在本例中没有给出Node类的复制构造函数，并非可以使用默认类的复制构造函数，并非可以使用默认的复制构造函数，而是避开了所有使用它的情况，本例中函数的参数的复制构造函数，而是避开了所有使用它的情况，本例中函数的参数和返回值仅使用指向和返回值仅使用指向Node的指针，类定义中也没有用复制方式初始的指针，类定义中也没有用复制方式初始化。化。定义复制构造函数与类的实际意义和使用方式有关，并非只是深定义复制构造函数与类的实际意义和使用方式有关，并非只是深复制和浅复制的问题复制和浅复制的问题。通常对通常对Node类复制的结果应是一个孤立结点：类复制的结果应是一个孤立结点：templateNode:Node(Node&node)info=;link=NULL;link域值为域值为NULL。该函数与。该函数与Node的有参构造函数功能基本相同。考的有参构造函数功能基本相同。考虑到函数的参数和返回值仅使用指向虑到函数的参数和返回值仅使用指向Node的指针，定义复制构造函的指针，定义复制构造函数已经没有实际意义数已经没有实际意义单链表的复制构造函数和复制运算符是一个复杂的算法，与前文单链表的复制构造函数和复制运算符是一个复杂的算法，与前文所编的复制构造函数和复制运算符构造相去甚远了。所编的复制构造函数和复制运算符构造相去甚远了。7.2.3 双向链表（选读）双向链表（选读） 双向链表引入：双向链表引入：考虑单链表只能找后继。如要找前驱，必须从表头开始搜考虑单链表只能找后继。如要找前驱，必须从表头开始搜索。为了克服这一缺点，可采用索。为了克服这一缺点，可采用双向链表双向链表（Double Linked Double Linked List)List)。双向链表的。双向链表的结点有三个域结点有三个域：左链接指针左链接指针（llink)llink)，数据域（数据域（info)info)，右链接指针域右链接指针域(rlink)(rlink)。双向链表经常采。双向链表经常采用用带头结点的循环链表方式带头结点的循环链表方式。 info0 infon-1. info1head(a)非空表非空表head(b)空表空表7.2.3 双向链表（选读）双向链表（选读）双向链表的访问：双向链表的访问：假设指针假设指针p p指向双向循环链表的某一个结点，那么，指向双向循环链表的某一个结点，那么，p-llinkp-llink指示指示P P所指结点的所指结点的前驱结点前驱结点，p-rlinkp-rlink指示指示后继结点。后继结点。p-p-llink-rlinkllink-rlink指示本结点的前驱结点的后继结点，即本结点，指示本结点的前驱结点的后继结点，即本结点，间接访问符间接访问符-可以连续使用可以连续使用。pllink rlinkrlinkllink rlink前前驱结点点 llink 本本结点点 后后继结点点间接访问符的使用间接访问符的使用【例【例7.77.7】双向链表类模板和结点类模板。双向链表类模板和结点类模板。7.3 栈与队列的基本操作及其应用栈与队列的基本操作及其应用 栈和队都是特殊的线性表，限制存取位置的线性结构，可以由顺序表实现，也可以由链表实现。 7.3.1 栈栈 7.3.3队列队列 7.3.2 栈的应用（选读）栈的应用（选读） 7.3.1 栈栈栈的基本概念：栈的基本概念： 栈定义为只允许在表的一端进行插入和删除的线性表栈定义为只允许在表的一端进行插入和删除的线性表。允许进行插入和删除的一端叫做允许进行插入和删除的一端叫做栈顶栈顶(top)，而另一端叫，而另一端叫栈栈底底(bottom)。栈中没有任何元素时，称为空栈。栈中没有任何元素时，称为空栈。进栈时最先进栈的在最下面，最后的在最上面，后来进栈时最先进栈的在最下面，最后的在最上面，后来居上。而出栈时顺序相反，最后进栈的最先出栈，而最先居上。而出栈时顺序相反，最后进栈的最先出栈，而最先进栈的进栈的a0最后出栈。所以栈又称作最后出栈。所以栈又称作后进先出（后进先出（LIFO：LastInFirstOut）的线性表）的线性表。栈可以用顺序表实现，称栈可以用顺序表实现，称顺序顺序栈；也可以用链表实现，栈；也可以用链表实现，称称链栈链栈。7.3.1 栈栈栈的基本操作：栈的基本操作： 参见下图，设给定栈参见下图，设给定栈s=(a0，a1，an-1)，称，称a0为栈为栈底，底，an-1为栈顶。进栈时最先进栈的为栈顶。进栈时最先进栈的a0在最下面，在最下面，an-1在最在最上面。而出栈时顺序相反，最后进栈的上面。而出栈时顺序相反，最后进栈的an-1最先出栈，而最最先出栈，而最先进栈的先进栈的a0最后出栈。最后出栈。a0an-2a1an-1bottom进栈进栈toptoptoptoptop出栈出栈图示为顺序栈。其中栈图示为顺序栈。其中栈底底bottom是指向栈数据是指向栈数据区的下一单元，这样判区的下一单元，这样判断是否为空栈会更方便，断是否为空栈会更方便，只需只需top与与bottom相同相同就是空栈。通常只有栈就是空栈。通常只有栈顶与操作有关。顶与操作有关。7.3.1 栈栈templateclassStackinttop;/栈顶指针（下标）栈顶指针（下标）T*elements;/动态建立的元素动态建立的元素intmaxSize;/栈最大容纳的元素个数栈最大容纳的元素个数public:Stack(int=20);/构造函数构造函数，栈如不指定大小，设为，栈如不指定大小，设为20元素元素Stack()deleteelements;voidPush(constT&data);/压栈压栈TPop();/弹出弹出，top-TGetElem(inti);/取数据取数据，top不变不变voidMakeEmpty()top=-1;/清空栈清空栈boolIsEmpty()constreturntop=-1;/判栈空判栈空boolIsFull()constreturntop=maxSize-1;/判栈满判栈满voidPrintStack();/输出输出栈内所有数据栈内所有数据【例【例7.8】顺序栈的类模板：顺序栈的类模板：7.3.1 栈栈voidmain()inti,a10=0,1,2,3,4,5,6,7,8,9,b10;Stackistack(10);for(i=0;i10;i+)istack.Push(ai);()cout栈满栈满endl;();for(i=0;i10;i+)bi=();()cout栈空栈空endl;for(i=0;i10;i+)coutbit;/注意先进后出注意先进后出coutendl;();/下溢出下溢出7.3.1 栈栈【例【例7.9_h】链栈的链栈的结点结点类模板：类模板： templateclassNode/链栈结点类模板链栈结点类模板Tinfo;Node*link;public:Node(Tdata=0,Node*next=NULL)info=data;link=next;friendclassStack;top 链栈链栈7.3.1 栈栈链栈类模板链栈类模板(无头结点链表无头结点链表)：templateclassStack/链栈类模板链栈类模板Node*top;/栈顶指针栈顶指针public:Stack()top=NULL;Stack();/析构函数析构函数voidPush(constT&data);/压栈压栈TPop();/弹出弹出TGetTop();/取栈顶元素取栈顶元素voidMakeEmpty();/清空栈清空栈boolIsEmpty()returntop=NULL;7.3.2 栈的应用（选读）栈的应用（选读）顺序栈和链栈逻辑功能是一样，尽管这里两个栈顺序栈和链栈逻辑功能是一样，尽管这里两个栈模板的成员函数功能选择稍有出入，因为模板的成员函数功能选择稍有出入，因为顺序栈可以顺序栈可以随机访问其中的元素随机访问其中的元素，而链栈只能顺序访问，而链栈只能顺序访问，但逻辑但逻辑上完全可以做到一样（物理结构不同）上完全可以做到一样（物理结构不同）。顺序栈必须。顺序栈必须先开一定大小内存空间，执行起来简单，速度快，可先开一定大小内存空间，执行起来简单，速度快，可能溢出。能溢出。链栈内存空间随用随开，不会溢出，但执行链栈内存空间随用随开，不会溢出，但执行复杂（不断地动态分配），速度慢。复杂（不断地动态分配），速度慢。 顺序栈和链栈比较：顺序栈和链栈比较：7.3.2 栈的应用（选读）栈的应用（选读）栈可用于栈可用于表达式的计算表达式的计算。现考虑最简单的。现考虑最简单的+、-、*、/四个运算符和结束符组成的算术表达式，只有四个运算符和结束符组成的算术表达式，只有两个优两个优先级先级，先，先*/，后，后+-。为实现运算符的优先级，采用两个栈：一个为实现运算符的优先级，采用两个栈：一个数栈数栈，一个一个运算符栈运算符栈。数栈暂存操作数，运算符栈暂存运算符。数栈暂存操作数，运算符栈暂存运算符。栈的使用栈的使用(表达式运算表达式运算)： NcbaOat1deNat1deOONt1at2t1at2t3aNt3aNOOb*c-t1d/e-t2t1-t2-t3a+t3-t4N：数栈：数栈O：运算符运算符 (a)(b)(c)(d)(e)设有：设有：a+b*c-d/e=；参见上图。；参见上图。从左向右扫描算术表达式从左向右扫描算术表达式，遇到，遇到操作操作数数，压入数栈压入数栈；遇到；遇到运算符运算符，则，则与运算符栈栈顶的运算符比较优先级与运算符栈栈顶的运算符比较优先级，若新的运算符优先级高，或运算符栈空，则压栈。否则将栈顶运算符若新的运算符优先级高，或运算符栈空，则压栈。否则将栈顶运算符出栈，与数字栈出栈的两个数据进行运算，结果压入数栈，再将新运出栈，与数字栈出栈的两个数据进行运算，结果压入数栈，再将新运算符压栈。继续扫描，直到遇到号，扫描结束。栈中数据继续按前算符压栈。继续扫描，直到遇到号，扫描结束。栈中数据继续按前面规则出栈。面规则出栈。7.3.2 栈的应用（选读）栈的应用（选读）【例例】模模拟拟简简单单计计算算器器，该该计计算算器器只只认认+ - * / 四四个个运运算算符符，输输入入为为整整数数。表表达达式式结结束束符符使使用用号号，清清空空栈栈用用c字字符符。使使用用z字符表示结束。字符表示结束。简易计算器类定义：简易计算器类定义：classCalculatorStackNstack;/使用链栈使用链栈StackOstack;public:Calculator(void);voidCal(void);/计算器运算程序计算器运算程序voidGetTwoNum(int&Num1,int&Num2);/取取数数voidCompute(charOpr);/读算式读算式voidClear(void);/清除清除7.3.3 队列队列 队列的基本概念：队列的基本概念：队列队列(Queue)(Queue)也是一种限定存取位置的线性表。它也是一种限定存取位置的线性表。它只允许在只允许在表的一端插入，而在另一端删除表的一端插入，而在另一端删除。允许插入的一端称为。允许插入的一端称为队尾队尾(rear)(rear)，允许删除的一端叫做，允许删除的一端叫做队头队头(front)(front)。每次在队尾加入新。每次在队尾加入新元素，加入称为元素，加入称为进队进队，删除称为，删除称为出队出队。队列的这种特性正好与。队列的这种特性正好与栈相反，叫做栈相反，叫做先进先出先进先出FIFO(First In First Out)FIFO(First In First Out)。 a0a1a2an-1front元素移动元素移动方向方向rear图队列图队列 图所示队列随队尾加入元素，队尾图所示队列随队尾加入元素，队尾(rear)不断向后移；而随不断向后移；而随队头元素的出队，则队头队头元素的出队，则队头(front)也不断后移，即也不断后移，即位置在变位置在变（如要位置不变，（如要位置不变，移动元素移动元素工作量也太大）。工作量也太大）。7.3.2 队列队列rearfrontADCABDECFHGBCD进队A进队空空队DCAB出出队EFGH进队rearfrontrearrearrearfrontfrontfront图图7.16顺序队列的插入和删除顺序队列的插入和删除 由图可见：空队由图可见：空队时指针（下标）时指针（下标）front和和rear在在一起都指向队前一起都指向队前方，当有元素进方，当有元素进队，则队，则rear后移；后移；有元素出队，则有元素出队，则front后移，最后移，最后分配给队的前后分配给队的前端不再被利用。端不再被利用。 顺序表队列的缺点：7.3.2 队列队列顺序表队列的改进：顺序表队列的改进：逻辑上的循环队列逻辑上的循环队列 注意，空队时注意，空队时rear=frontrear=front，满队时必须空一个位置，满队时必须空一个位置 7.3.2 队列队列循环队列循环队列浪费一个位置好像太可惜，特别在浪费一个位置好像太可惜，特别在该位置中存放一个很大的对象时。实际上该位置中存放一个很大的对象时。实际上对象很对象很大时，总是由索引（指针）来排队大时，总是由索引（指针）来排队。若想利用这。若想利用这个空间，必然加一个标志来表示队空个空间，必然加一个标志来表示队空/ /队满，进队队满，进队出队都要判断，使用上更不方便。出队都要判断，使用上更不方便。 用链表实现队列无此问题用链表实现队列无此问题 【例【例7.10】顺序存储方式的循环队列类模板顺序存储方式的循环队列类模板。【例【例7.11】链队类模板。链首出队，链尾入队。链队类模板。链首出队，链尾入队。无链表头结点方式。无链表头结点方式。二叉树（选读）二叉树（选读） 树形结构是一类重要的非线性数据，树和树形结构是一类重要的非线性数据，树和二叉树是常用的树形结构。二叉树是常用的树形结构。 7.4.2 二叉树的遍历二叉树的遍历 二叉树的概念二叉树的概念 7.4.3 排序二叉树排序二叉树 二叉树的概念二叉树的概念 （选读）（选读） 树（树（Tree）是由是由n（n0）个结点组成的有限集）个结点组成的有限集合。如合。如n=0，称为空树。非空树有一个特定的结点，称为空树。非空树有一个特定的结点，它只有直接后继，没有直接前驱，称之为根它只有直接后继，没有直接前驱，称之为根（root）。除根以外的其它结点划分为）。除根以外的其它结点划分为m（m0）个互不相交的有限集合个互不相交的有限集合T0，T1，Tm-1，每个，每个集合又是一棵树，称为根的子树（集合又是一棵树，称为根的子树（subtree）。每）。每棵子树的根结点有且仅有一个直接前驱，但可以有棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。这是一个递归方法定义的数据个或多个直接后继。这是一个递归方法定义的数据结构。结构。 树的概念：二叉树的概念（选读）二叉树的概念（选读） ABCDEFGIHJLKONM0层层1层层2层层3层层深深度度图图7.18 树的示意图树的示意图 结结点点，包包括括数数据据项项和和多多个个指指针针项项，指指针针项项数数目目并并不不固固定定，且且无无次序。次序。结结点点的的度度，结结点点所所拥拥有的子树数量。有的子树数量。叶叶结结点点，度度为为0的的结结点点，如如G，I，J，K，L，M，N，O结点。结点。分分支支结结点点，度度1的的结结点。点。孩孩子子结结点点，若若结结点点x有有子子树树，则则子子树树根根结结点点即为即为x的孩子结点。的孩子结点。树的术语：二叉树的概念（选读）二叉树的概念（选读） ABCDEFGIHJLKONM0层层1层层2层层3层层深深度度图图7.18 树的示意图树的示意图 双双亲亲结结点点，若若结结点点x有有孩孩子子，它它即即为为孩孩子的双亲。子的双亲。兄兄弟弟结结点点，同同一一双双亲亲的的结结点点互互称称为为兄兄弟。弟。结结点点的的层层次次，从从根根到到该该结结点点所所经经路路径径上的分支条数。上的分支条数。树树的的深深度度,树树中中结结点点的层次数。的层次数。树的度树的度，树中结点，树中结点度的最大值。度的最大值。 树的术语：二叉树的概念（选读）二叉树的概念（选读） 二二叉叉树树（Binary Tree）是是另另一一种种独独立立的的树树形形结结构构。二二叉叉树树是是结结点点的的一一个个有有限限集集合合，该该集集合合或或为为空空，或或是是由由一一个个根根结结点点及及两两棵棵树树分分别别称称为为左左子子树树和和右右子子树树的的（注注意意有有左左右右之之分分）互互不不相相交交的的二二叉叉树树组组成成，其其中中左左右右子子树树分分别别可可以以为为空空子子树树或或均均为为空空树树。这这也也是是一一个个递递归归的的定定义义。二二叉叉树树的的特点是：每个结点最多两个孩子，并且子树有左右之分。特点是：每个结点最多两个孩子，并且子树有左右之分。二叉树的基本性质：二叉树的基本性质：1二叉树的第二叉树的第i层上最多有层上最多有2i-1(i=1)个结点；个结点；2深度为深度为h的二叉树中最多有的二叉树中最多有2h-1个结点；个结点；3在任一棵二叉树中，有在任一棵二叉树中，有n0个叶子结点，有个叶子结点，有n2个度为个度为2的的结点，则有结点，则有n0=n2+1。树的概念：二叉树的概念（选读）二叉树的概念（选读） 【例】画出有三个结点的所有二叉树。【例】画出有三个结点的所有二叉树。解：结果见图，共解：结果见图，共5种。种。图图7.19 5种不同的三结点二叉树种不同的三结点二叉树 二叉树的概念（选读）二叉树的概念（选读） 满二叉树和完全二叉树：满二叉树和完全二叉树：分别如图和图，完全二叉树已有的结点排序与满二叉分别如图和图，完全二叉树已有的结点排序与满二叉树相同。树相同。 123456798101114131215图图7.20 满二叉树满二叉树 12345679810图图7.21 完全二叉树完全二叉树 二叉树的概念（选读）二叉树的概念（选读） 下面给出链式储存方式的二叉树。每个结点有三个域：下面给出链式储存方式的二叉树。每个结点有三个域：数据域、左孩子指针和右孩子指针，见图。数据域、左孩子指针和右孩子指针，见图。 lchildrchildinfo图图7.22 二叉树结点二叉树结点 二叉树的概念（选读）二叉树的概念（选读） 二叉树类结点类模板定义：二叉树类结点类模板定义：templateclassBinaryTree;templateclassNodeNode*lchild,*rchild;Tinfo;public:Node()lchild=NULL;rchild=NULL;Node(Tdata,Node*left=NULL,Node*right=NULL)info=data;lchild=left;rchild=right;二叉树的概念（选读）二叉树的概念（选读） TGetinfo()returninfo;/取得结点数据取得结点数据voidsetinfo(constT&data)info=data;/修改结点数据修改结点数据Node*Getleft()returnlchild;/取得左子树取得左子树Node*Getright()returnrchild;/取得右子树取得右子树voidsetleft(Node*left)lchild=left;/设置左指针设置左指针voidsetrightNode*right)rchild=right;/设置右指针设置右指针friendclassBinaryTree;/二叉树类说明为友元类二叉树类说明为友元类7.4.2 二叉树的遍历（选读）二叉树的遍历（选读） 二叉树的遍历二叉树的遍历( (binary tree traversal) )： 遵遵从从某某种种次次序序，查查巡巡二二叉叉树树的的所所有有结结点点，每每个个结结点点都都被被访访问问一一次次，而而且且仅仅访访问问一一次次。所所谓谓“访访问问”指指对对结结点点施行某些操作，但不破坏它原来的数据结构。施行某些操作，但不破坏它原来的数据结构。遍历二叉树有不同次序，规定先左后右，令遍历二叉树有不同次序，规定先左后右，令L L，R R，V V分别代表遍历一个结点的左右子树和访问该结点的操作，分别代表遍历一个结点的左右子树和访问该结点的操作，有三种方式：有三种方式：前序遍历（前序遍历（VLRVLR）中序遍历（中序遍历（LVRLVR）后序遍历（后序遍历（LRVLRV） 7.4.2 二叉树的遍历（选读）二叉树的遍历（选读） 遍历实遍历实例：例：前序遍历访问次序为前序遍历访问次序为ABDEGCFH。 图图7.23 二叉树遍历二叉树遍历 中序遍历结果为中序遍历结果为D B G E A F H C。后序遍历结果为后序遍历结果为D G E B H F C A。 7.4.2 二叉树的遍历（选读）二叉树的遍历（选读） 【例例】二二叉叉树树类类模模板板（其其中中二二叉叉树树生生成成借借用用二二叉叉排排序序树树，见见下下节节）。特特别别注注意意插插入入结结点点时时，第第二二参参数数为为指指针针的的引引用用！否否则则不不能能建建立立树树。为为什什么么？请请读读者者自自己己思思考考。本本例例采采用用简简单单的的接口函数，而把较复杂的算法作为私有函数。接口函数，而把较复杂的算法作为私有函数。 templateclassBinaryTreeNode*root;/二叉树的根指针二叉树的根指针voidInOrder(Node*Current);/中序遍历中序遍历voidPreOrder(Node*Current);/前序遍历前序遍历voidPostOrder(Node*Current);/后序遍历后序遍历voidInsert(constT&data,Node*&b);/插入结点插入结点，参数为引用！参数为引用！voidDestory(Node*Current);/删除树删除树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 二叉树的遍历（选读）二叉树的遍历（选读） 【例】某二叉树先序遍历为【例】某二叉树先序遍历为ABCEFDGHIJK，中序遍历为，中序遍历为ECFBDGAIHJK绘出该二叉树。绘出该二叉树。 ABCDEFGHIJK图图7.24 例二叉树例二叉树 按同样按同样方法推出方法推出A的右子的右子树。结果如图。可以证树。结果如图。可以证明已知先序和中序访问明已知先序和中序访问次序可以唯一确定一棵次序可以唯一确定一棵二叉树。二叉树。 解：解：由先序知由先序知A为根结点，而由为根结点，而由中序知中序知EFBDG为左子树，为左子树，IHJK为右子树。由先序中的为右子树。由先序中的BCEFDG知知B为左子树根结点，由中为左子树根结点，由中序中的序中的ECFBDG知知ECF为其为其左子树，而左子树，而DG为右子树。为右子树。再由先序再由先序CEF知知C为左子树根结为左子树根结点，由中序点，由中序ECF知知E为为C左子树，左子树，F为的右子树。再由先序为的右子树。再由先序DG知，知，D为为B的右子树根结点，由中序的右子树根结点，由中序DG知知G为为D的右子树。的右子树。7.4.3 排序二叉树排序二叉树 （选读）（选读） 二二叉叉排排序序树树（Binary Sorting Tree）又又称称二二叉叉搜搜索索树树（Binary Search Tree），是是一一种种特特殊殊结结构构的的二二叉叉数数，作作为为一一种种排排序序和和查查找找的的手手段段，对对应应有有序序表表的的对对半半查查找找，通常亦被称为数表。其定义也是递归的。通常亦被称为数表。其定义也是递归的。二叉排序树的定义：二叉排序树的定义：二叉排序树或者是空树或者是具有下述性质的二叉二叉排序树或者是空树或者是具有下述性质的二叉数，其左子树上所有结点的数据值均小于根结点的数据数，其左子树上所有结点的数据值均小于根结点的数据值；右子树上所有结点的数据值均大于等于根结点的数值；右子树上所有结点的数据值均大于等于根结点的数据值，左子树和右子树又各是一棵二叉排序树。据值，左子树和右子树又各是一棵二叉排序树。7.4.3 排序二叉树排序二叉树（选读）（选读） 二叉排序树用中序遍历就可以得到由小到大的有二叉排序树用中序遍历就可以得到由小到大的有序序列，如图可得有序序列序序列，如图可得有序序列8，10，11，12，15，16，18，22，24，26，29。 101826812222911241615图图7.24 二叉排序树例二叉排序树例 二叉排序树的遍历：二叉排序树的遍历：二叉排序树生成算法：二叉排序树生成算法：对任意一组数据元素序列对任意一组数据元素序列a0，a1，a2，an-1。要要生成二叉排序树生成二叉排序树的过程为：的过程为：1.令令a0为二叉树的根结点。为二叉树的根结点。2.若若a1a0，令，令a1为为a0左子树的根结点，否则左子树的根结点，否则a1为为a0右子树的根结点。右子树的根结点。3.如如ai小于根结点，则去左子树，否则去右子树，小于根结点，则去左子树，否则去右子树，按此法查找，直到成为空树，则安放此位置。这步按此法查找，直到成为空树，则安放此位置。这步就是插入算法。就是插入算法。 7.4.3 7.4.3 排序二叉树排序二叉树（选读）（选读） 7.4.3 排序二叉树（选读）排序二叉树（选读） templateNode* BinaryTree:Find(const T &data,Node *b) if(b!=NULL)Node *temp=b;while(temp!=NULL)if(temp-info=data)return temp;if(temp-inforchild;else temp=temp-lchild; return NULL;【例【例7.15】排序二叉树查找函数。】排序二叉树查找函数。算法：用中序遍历即可，但递归慢，下面为迭代查找算法。算法：用中序遍历即可，但递归慢，下面为迭代查找算法。第七章第七章 动态内存分配与数据结构动态内存分配与数据结构完完谢谢！自由存储区自由存储区内存的分配与释放内存的分配与释放【例【例7.17.1】【例】动态数组的建立与撤销【例】动态数组的建立与撤销#include #include using namespace std；int main()int n;char *pc;cout请输入动态数组的元素个数请输入动态数组的元素个数n; /在运行时确定，可输入在运行时确定，可输入25pc=new charn;strcpy(pc,“自由存储区内存的动态分配自由存储区内存的动态分配);coutpcendl;delete pc;/释放释放pc所指向的所指向的n个字符的内存空间个字符的内存空间return 0;自由存储区自由存储区内存的分配与释放内存的分配与释放【例【例7.27.2】 【例【例7.2】 动态创建和删除一个动态创建和删除一个m*n个元素的数组。采用个元素的数组。采用指针数指针数组方式组方式来完成二维数组的动态创建。来完成二维数组的动态创建。intm=4;/行数行数intn=6;/列数列数二维数组的动态创建：二维数组的动态创建：intmain()double*data;inti,j;data=newdouble*m;/设置行设置行if(data)=0)coutCouldnotallocate.Bye.;return-1; for(j=0;jm;j+)dataj=newdoublen;/设置列设置列if(dataj=0)coutCouldnotallocate.Bye.;return-1; 自由存储区自由存储区内存的分配与释放内存的分配与释放【例【例7.27.2】for (i=0;im;i+) for (j=0;jn;j+) dataij=i*n+j; /初始化数组元素初始化数组元素 display(data); de_allocate(data); return 0; 二维数组的撤销与内存释放：二维数组的撤销与内存释放：void de_allocate(double *data) for (int i=0;im;i+) delete datai; /注意撤销次序，先列后行，与设置相反注意撤销次序，先列后行，与设置相反 delete data; 自由存储区自由存储区对象与构造函数【例对象与构造函数【例7.3】类说明：类说明：class CGoods string Name; int Amount; float Price; float Total value;public: CGoods()cout调用默认构造函数调用默认构造函数endl; CGoods(string name,int amount ,float price)cout调用三参数构造函数调用三参数构造函数endl;Name=name; Amount=amount;Price=price; Total_value=price*amount; CGoods() cout调用析构函数调用析构函数endl;【例【例7.37.3】演示自由存储区对象分配和释放。】演示自由存储区对象分配和释放。自由存储区自由存储区对象与构造函数【例对象与构造函数【例7.3】使用：使用：int main() int n; CGoods *pc,*pc1,*pc2; pc=new CGoods(“夏利夏利2000”，10，118000); /调用三参数构造函数调用三参数构造函数 pc1=new CGoods(); /调用默认构造函数调用默认构造函数 cout输入商品类数组元素数输入商品类数组元素数n; pc2=new CGoodsn; /动态建立数组，不能初始化，调用动态建立数组，不能初始化，调用n次默认构造函数次默认构造函数 delete pc; delete pc1; delete pc2; return 0;例例 实现深复制实现深复制默认构造函数：默认构造函数：student:student() coutConstructor; pName=NULL; cout默认默认“endl;带参数带参数构造函数：构造函数：student:student(char *pname) coutConstructor; if(pName=new charstrlen(pname)+1) strcpy(pName,pname); coutpNameendl;例例 实现深复制实现深复制复制构造函数：复制构造函数：student:student(student&s)coutCopyConstructor;)if(pName=newcharstrlen(s.pName)+1);elsepName=NULL;coutpNameendl;析构函数：析构函数：student:student() coutDestructorpNameendl; if(pName) pName0=0; delete pName; /释放字符串释放字符串例例 实现深复制实现深复制复制赋值操作符：复制赋值操作符：student & student:operator=(student &s) coutCopy Assign operator; delete pName;/如原来已分配，应先撤销，再重分配如原来已分配，应先撤销，再重分配 ) if(pName=new charstrlen(s.pName)+1) ); else pName=NULL; coutpNameendl; return *this;int main(void)student s1(范英明范英明),s2(沈俊沈俊),s3;student s4=s1;s3=s2;return 0;例例 实现深复制实现深复制例例7.5_h 单链表类型模板单链表类型模板templateNode:Node()link=NULL;templateNode:Node(constT&data)info=data;link=NULL;templatevoidNode:InsertAfter(Node*p)p-link=link;link=p;templateNode*Node:RemoveAfter()Node*tempP=link;if(link=NULL)tempP=NULL;/已在链尾已在链尾,后面无结点后面无结点elselink=tempP-link;returntempP;例例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&tempP-info!=data)tempP=tempP-link;returntempP;/搜索成功返回该结点地址，不成功返回搜索成功返回该结点地址，不成功返回NULLtemplateintList:Length()/链表长度链表长度Node*tempP=head-link;intcount=0;while(tempP!=NULL)tempP=tempP-link;count+;returncount;例例7.5_h 单链表类型模板单链表类型模板链表类成员函数：链表类成员函数： templatevoidList:PrintList()/显示链表显示链表Node*tempP=head-link;while(tempP!=NULL)coutinfolink;coutendl;templatevoidList: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&tempP-link!=p)tempP=tempP-link;if(tempP-link=tail)tail=tempP;returntempP-RemoveAfter();/本函数所用方法可省一个工作指针，与本函数所用方法可省一个工作指针，与InsertOrder比较比较例例 单链表类型模板单链表类型模板例例7.5 单链表类型模板主函数单链表类型模板主函数voidmain()Node*P1;Listlist1,list2;inta16,i,j;cout请输入请输入16个整数个整数endl;for(i=0;iai;/随机输入随机输入16个整数个整数for(i=0;i16;i+)P1=list1.CreatNode(ai);list1.InsertFront(P1);/向前生成向前生成list1P1=list2.CreatNode(ai);list2.InsertRear(P1);/向后生成向后生成list2list1.PrintList();coutlist1长度：长度：list1.Length()endl;list2.PrintList();例例7.5 单链表类型模板主函数单链表类型模板主函数 cout请输入一个要求删除的整数请输入一个要求删除的整数j;P1=list1.Find(j);if(P1!=NULL)P1=list1.DeleteNode(P1);deleteP1;list1.PrintList();coutlist1长度：长度：list1.Length()endl;elsecout未找到未找到endl;list1.MakeEmpty();/清空清空list1for(i=0;i16;i+)P1=list1.CreatNode(ai);list1.InsertOrder(P1);/升序创建升序创建list1list1.PrintList();return0;例例7.6 学生档案的管理学生档案的管理#includeEx7_6.hclassstudentintid;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;booloperator!=(studentele)returnid!=;voidshow()coutidtnametsextagetaddresstengtphytmathtelectronendl;例例7.6 学生档案的管理学生档案的管理注意，链表类定义中输出函数注意，链表类定义中输出函数PrintList()改写为：改写为：templatevoidList:PrintList()Node*tempP=head-link;while(tempP!=NULL)tempP-();tempP=tempP-link;coutendl;在在student类中采用类中采用show()函数是一个无奈的选择，因为插函数是一个无奈的选择，因为插入运算符入运算符的重载在节才学，那时就不需要改写的重载在节才学，那时就不需要改写PrintList()，而在，而在student类中重载插入运算符类中重载插入运算符。例例7.6 学生档案的管理学生档案的管理intmain()constinth=4;inti,j;Node*P1;Listlist1,list2;studentnh=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;ih;i+)P1=list1.CreatNode(ni);list1.InsertFront(P1);/向前生成向前生成list1P1=list2.CreatNode(ni);list2.InsertRear(P1);/向后生成向后生成list2list1.PrintList();例例7.6 学生档案的管理学生档案的管理coutlist1长度：长度：list1.Length()endl;list2.PrintList();cout请输入一个要求删除的学生学号请输入一个要求删除的学生学号j;P1=list1.Find(j);/学号由构造函数转换为学生类学号由构造函数转换为学生类if(P1!=NULL)P1=list1.DeleteNode(P1);deleteP1;list1.PrintList();coutlist1长度：长度：list1.Length()endl;elsecout未找到未找到endl;list1.MakeEmpty();/清空清空list1for(i=0;ih;i+)P1=list1.CreatNode(ni);list1.InsertOrder(P1);/升序创建升序创建list1list1.PrintList();return0;【例【例7.7】双向链表类模板和结点类模板】双向链表类模板和结点类模板双链表结点模板类：双链表结点模板类：templateclassDblNodeTinfo;/数据域数据域DblNode*llink,*rlink;/前驱前驱(左链左链)、后继、后继(右链右链)指针指针public:DblNode(Tdata);/一般结点一般结点DblNode();/头结点头结点TGetinfo()returninfo;friendclassDblList;templateDblNode:DblNode()/一般结点一般结点llink=rlink=NULL;templateDblNode:DblNode(Tdata)info=data;/头结点头结点llink=NULL;rlink=NULL;【例【例7.7】双向链表类模板和结点类模板】双向链表类模板和结点类模板双链表模板类：双链表模板类：templateclassDblListDblNode*head,*current;public:DblList();/建立表头结点建立表头结点DblList();voidInsert(constT&data);/链尾插入链尾插入DblNode*Remove(DblNode*p);/删除定结点删除定结点voidPrint();/打印链表打印链表intLength();/计算链表长度计算链表长度DblNode*Find(Tdata);/搜索数据与定值相同的结点搜索数据与定值相同的结点voidMakeEmpty();/清空链表清空链表/其它操作其它操作;【例【例7.7】双向链表类模板和结点类模板】双向链表类模板和结点类模板下面分析几个成员函数：下面分析几个成员函数：templateDblList:DblList()/建立表头结点建立表头结点head=newDblNode();head-rlink=head-llink=head;current=NULL;templatevoidDblList:MakeEmpty()DblNode*tempP;/清空链表清空链表while(head-rlink!=head)tempP=head-rlink;head-rlink=tempP-rlink;/把头结点后的第一个结点从链中脱离把头结点后的第一个结点从链中脱离tempP-rlink-llink=head;/处理左指针处理左指针deletetempP;/删除删除(释放释放)脱离下来的结点脱离下来的结点current=NULL;/current指针恢复指针恢复【例【例7.7】双向链表类模板和结点类模板】双向链表类模板和结点类模板templatevoidDblList:Insert(constT&data)current=newDblNode;/新结点在链尾新结点在链尾current-info=data;current-rlink=head;/注意次序注意次序current-llink=head-llink;head-llink-rlink=current;head-llink=current;/最后做最后做templateDblNode*DblList:Remove(DblNode*p)/删除定结点删除定结点current=head-rlink;while(current!=head¤t!=p)current=current-rlink;if(current=head)current=NULL;else/结点摘下结点摘下p-llink-rlink=p-rlink;p-rlink-llink=p-llink;p-rlink=p-llink=NULL;returncurrent;【例【例7.8】顺序栈的类模板定义】顺序栈的类模板定义templateStack:Stack(intmaxs)maxSize=maxs;top=-1;elements=newTmaxSize;/建立栈空间建立栈空间assert(elements!=0);/分配不成功结束程序分配不成功结束程序templatevoidStack:PrintStack()for(inti=0;i=top;i+)coutelementsit;coutendl;templatevoidStack:Push(constT&data)assert(!IsFull();/栈满则退出程序栈满则退出程序elements+top=data;/栈顶指针先加栈顶指针先加1，元素再进栈，元素再进栈【例【例7.8】顺序栈的类模板定义】顺序栈的类模板定义templateTStack:Pop()assert(!IsEmpty();/栈已空则不能退栈，退出程序栈已空则不能退栈，退出程序returnelementstop-;/返回栈顶元素，同时栈顶指针退返回栈顶元素，同时栈顶指针退1templateTStack:GetElem(inti)assert(i=0);/超出栈有效数据则错，退出程序超出栈有效数据则错，退出程序returnelementsi;/返回指定元素，返回指定元素，top不变不变【例【例7.9_h】链栈的类模板定义】链栈的类模板定义templateStack:Stack()MakeEmpty();templatevoidStack:MakeEmpty()Node*temp;while(top!=NULL)temp=top;top=top-link;deletetemp;templatevoidStack:Push(constT&data)top=newNode(data,top);/链栈向前生成，新结点在链栈头链栈向前生成，新结点在链栈头【例【例7.9_h】链栈的类模板定义】链栈的类模板定义templateTStack:Pop()assert(!IsEmpty();Node*temp=top;Tdata=temp-info;top=top-link;/丢弃栈顶结点丢弃栈顶结点deletetemp;/释放栈顶结点释放栈顶结点returndata;/返回栈顶数据返回栈顶数据templateTStack:GetTop()assert(!IsEmpty();returntop-info;【例【例7.9】模拟简单计算器（选读）】模拟简单计算器（选读）voidCalculator:Clear()();voidCalculator:GetTwoNum(int&Num1,int&Num2)Num1=Nstack.Pop();Num2=();voidCalculator:Compute(charOpr)intNum1,Num2;if(Opr!=)GetTwoNum(Num1,Num2);switch(Opr)case+:Nstack.Push(Num2+Num1);break;/结果压栈结果压栈case-:Nstack.Push(Num2-Num1);break;case*:Nstack.Push(Num2*Num1);break;case/:Nstack.Push(Num2/Num1);break;case=:cout()ch1;if(ch1=0&ch1=0)strk+1=0;/数字串生成数字串生成Nstack.Push(atoi(str);/数字串转换为整数后压栈数字串转换为整数后压栈k=-1;【例【例7.9】模拟简单计算器（选读）】模拟简单计算器（选读）switch(ch1)casec:Clear();break;case+:case-:while()ch2=();/不会有比不会有比优先级低的优先级低的Compute(ch2);Ostack.Push(ch1);break;case=:while()ch2=();Compute(ch2);Compute(ch1);break;【例【例7.9】模拟简单计算器（选读）】模拟简单计算器（选读）case*:case/:while(!Ostack.IsEmpty()&b1)ch2=();/把栈顶运算符弹出把栈顶运算符弹出if(ch2=*|ch2=/)/比较优先级比较优先级Compute(ch2);/新的优先级并不高新的优先级并不高else/新的优先级高新的优先级高Ostack.Push(ch2);/先把原栈中的运算符压回去先把原栈中的运算符压回去b1=false;Ostack.Push(ch1);/再把新的运算符压栈再把新的运算符压栈b1=true;/此句保证乘除从左倒右进行此句保证乘除从左倒右进行break;if(ch1=z)b2=false;【例【例7.107.10】循环队列顺序表类模板】循环队列顺序表类模板templateclassQueueintrear,front;/队尾与队头队尾与队头T*elements;/存放队列元素的容器存放队列元素的容器intmaxSize;/队列最多可容纳元素个数队列最多可容纳元素个数+1public:Queue(intms=18);/建立队建立队Queue()deleteelements;boolIsEmpty()constreturnfront=rear; /判队空判队空boolIsFull()constreturn(rear+1)%maxSize=front;/判队满判队满intLength()constreturn(rear-front+maxSize)%maxSize;/求队中元素数，注意求余算法求队中元素数，注意求余算法voidEnQue(constT&data);/进队进队TDeQue();/出队出队TGetFront();/取队头数据取队头数据voidMakeEmpty()front=rear=0; /队置空（初始态）队置空（初始态）【例【例7.107.10】循环队列顺序表类模板】循环队列顺序表类模板voidmain()inti;Queueque;/默认为默认为18元素队列，可用元素队列，可用17charstr1=abcdefghijklmnop;/17个元素，包括串结束符个元素，包括串结束符();for(i=0;i17;i+)que.EnQue(str1i);if()cout队满队满;cout共有元素：共有元素：()endl;for(i=0;i17;i+)cout();/先进先出先进先出coutendl;if()cout队空队空;cout共有元素：共有元素：()endl;【例【例7.107.10】循环队列顺序表类模板】循环队列顺序表类模板templateQueue:Queue(intms)maxSize=ms;elements=newTmaxSize;rear=front=0;assert(elements!=NULL);/断言：分配成功断言：分配成功templatevoidQueue:EnQue(constT&data)assert(!IsFull();/断言：队列不满，不满才能进队断言：队列不满，不满才能进队rear=(rear+1)%maxSize;/队尾指针加队尾指针加1elementsrear=data;【例【例7.107.10】循环队列顺序表类模板】循环队列顺序表类模板templateTQueue:DeQue()assert(!IsEmpty();front=(front+1)%maxSize;/队头指针加队头指针加1returnelementsfront;/注意注意front指向现在队头的前一位置指向现在队头的前一位置templateTQueue:GetFront()assert(!IsEmpty();returnelements(front+1)%maxSize;/加加1才能返回队头数据才能返回队头数据链表结点类：链表结点类：templateclassNodeTinfo;Node*link;public:Node(Tdata=0,Node*l=NULL);friendclassQueue;templateNode:Node(Tdata,Node*l)info=data;link=l;【例【例7.117.11】链队类模板】链队类模板链队类模板：链队类模板：templateclassQueueNode*front,*rear;public:Queue()rear=front=NULL;/构造一个空链队构造一个空链队Queue();/析构函数析构函数boolIsEmpty()returnfront=NULL;/队空否？队空否？voidEnQue(constT&data);/进队进队TDeQue();/出队出队TGetFront();/查看队头数据查看队头数据voidMakeEmpty();/置空队列置空队列【例【例7.117.11】链队类模板】链队类模板intmain()inti;Queueque;/默认为默认为18元素队列，可用元素队列，可用17charstr1=abcdefghijklmnop;/17个元素，包括串结束符个元素，包括串结束符for(i=0;i17;i+)que.EnQue(str1i);for(i=0;i17;i+)cout();/先进先出先进先出coutendl;if()cout“队空队空”endl;return0;【例【例7.117.11】链队类模板】链队类模板【例【例7.117.11】链队类模板】链队类模板templatevoidQueue:MakeEmpty()Node*temp;while(front!=NULL)temp=front;front=front-link;deletetemp;templateQueue:Queue()MakeEmpty();templatevoidQueue:EnQue(constT&data)if(front=NULL)front=rear=newNode(data,NULL);elserear=rear-link=newNode(data,NULL);/链队向后生成链队向后生成【例【例7.117.11】链队类模板】链队类模板templateTQueue:DeQue()assert(!IsEmpty();Node*temp=front;Tdata=temp-info;/取队头结点中的数据取队头结点中的数据front=front-link;/队头出队队头出队deletetemp;/释放内存空间释放内存空间returndata;templateTQueue:GetFront()assert(!IsEmpty();returnfront-info;【例【例7.13】二叉树类模板】二叉树类模板 templatevoidBinaryTree:InOrder(Node*Current)if(Current!=NULL)/递归终止条件递归终止条件InOrder(Current-lchild);/中序遍历左子树中序遍历左子树coutinforchild);/中序遍历右子树中序遍历右子树templatevoidBinaryTree:PreOrder(Node*Current)if(Current!=NULL)coutinfolchild);PreOrder(Current-rchild);【例【例7.13】二叉树类模板】二叉树类模板templatevoidBinaryTree:PostOrder(Node*Current)if(Current!=NULL)PostOrder(Current-lchild);PostOrder(Current-rchild);coutinfot;/后序访问根结点后序访问根结点template/后序释放根结点后序释放根结点voidBinaryTree:Destory(Node*Current)if(Current!=NULL)Destory(Current-lchild);Destory(Current-rchild);deleteCurrent;【例【例7.13】二叉树类模板】二叉树类模板intmain()constintn=15;inti,an=10,5,15,8,3,18,13,12,14,16,20,1,4,6,9;BinaryTreebtree;btree.Creat(a,n);cout输入数据：输入数据：endl;for(i=0;in;i+)coutait;coutendl中序：中序：endl;();/中序遍历输出升序中序遍历输出升序coutendl前序：前序：endl;();coutendl后序：后序：endl;();coutendl;return0;templatevoid BinaryTree:Insert(const T &data,Node * &b) if(b=NULL) /已到空树已到空树 ,插入插入 b=new Node(data); if(b=NULL) cout空间不足空间不足endl; exit(1); else if(datainfo) Insert(data,b-lchild); /小于小于,去左子树查去左子树查 else Insert(data,b-rchild); /否否则则向向右右子子树树去去查查 template /建立一棵二叉排序树建立一棵二叉排序树void BinaryTree:Creat(T* data,int n) for(int i=0;in;i+) Insert(datai,root);建立二叉排序树算法建立二叉排序树算法 例例7.13建立建立例例例例7.13插入插入