动态内存分配ppt课件

1、第七章第七章 动态内存分配动态内存分配本章首先介绍程序运行时动态内存分配本章首先介绍程序运行时动态内存分配dynamic dynamic memory allocationmemory allocation的概念与方法。到目前为止，本的概念与方法。到目前为止，本教材介绍的程序设计中，变量和对象在内存中的分配都教材介绍的程序设计中，变量和对象在内存中的分配都是编译器在编译程序时安排好了的，这带来了极大的不是编译器在编译程序时安排好了的，这带来了极大的不便，如数组必须大开小用，指针必须指向一个已经存在便，如数组必须大开小用，指针必须指向一个已经存在的变量或对象。动态内存分配解决了这个问题。本章将的

2、变量或对象。动态内存分配解决了这个问题。本章将进一步讨论拷贝构造函数；还要学习更多有关数据结构进一步讨论拷贝构造函数；还要学习更多有关数据结构的基本知识，包括栈，队，二叉树等的基本算法和应用。的基本知识，包括栈，队，二叉树等的基本算法和应用。模板是标准模板是标准C+C+实现代码复用的有力工具，特别是有关实现代码复用的有力工具，特别是有关数据结构的算法。本章继续使用模板介绍算法。数据结构的算法。本章继续使用模板介绍算法。7.1 堆内存分配堆内存分配 7.5 MFC对象和对象和Windows对象的关系对象的关系 7.4二叉树二叉树 7.3 栈与队列的基本操作及其应用栈与队列的基本操作及其应用 7.

3、2 链表与链表的基本操作链表与链表的基本操作 第七章第七章 动态内存分配动态内存分配 7.6 图书流通管理系统设计图书流通管理系统设计链表类应用链表类应用 7.1 堆内存分配堆内存分配 7.1.1堆内存的分配与释放堆内存的分配与释放 7.1.2 堆对象与构造函数堆对象与构造函数 7.1.3 浅拷贝与深拷贝浅拷贝与深拷贝 C/C+C/C+定义了定义了4 4个内存区间：代码区，个内存区间：代码区，全局变量与静态变量区，局部变量区全局变量与静态变量区，局部变量区即栈区，动态存储区，即堆即栈区，动态存储区，即堆heapheap区或自由存储区区或自由存储区free storefree store）。）。

4、通常定义变量或对象），编译器在通常定义变量或对象），编译器在编译时都可以根据该变量或对象编译时都可以根据该变量或对象的类型知道所需内存空间的大小，从的类型知道所需内存空间的大小，从而系统在适当的时候为他们分配确定而系统在适当的时候为他们分配确定的存储空间。这种内存分配称为静态的存储空间。这种内存分配称为静态存储分配存储分配有些操作对象只有在程序运行时才能有些操作对象只有在程序运行时才能确定，这样编译器在编译时就无法为确定，这样编译器在编译时就无法为他们预定存储空间，只能在程序运行他们预定存储空间，只能在程序运行时，系统根据运行时的要求进行内存时，系统根据运行时的要求进行内存分配，这种方法称为动

5、态存储分配。分配，这种方法称为动态存储分配。所有动态存储分配都在堆区中进行。所有动态存储分配都在堆区中进行。7.1.1 堆内存的分配与释放堆内存的分配与释放当程序运行到需要一个动态分配的变量或对象时，必须向系统申请取当程序运行到需要一个动态分配的变量或对象时，必须向系统申请取得堆中的一块所需大小的存贮空间，用于存贮该变量或对象。当不再使得堆中的一块所需大小的存贮空间，用于存贮该变量或对象。当不再使用该变量或对象时，也就是它的生命结束时，要显式释放它所占用的存用该变量或对象时，也就是它的生命结束时，要显式释放它所占用的存贮空间，这样系统就能对该堆空间进行再次分配，做到重复使用有限的贮空间，这样系

6、统就能对该堆空间进行再次分配，做到重复使用有限的资源。资源。在在C+中，申请和释放堆中分配的存贮空间，分别使用中，申请和释放堆中分配的存贮空间，分别使用new和和delete的的两个运算符来完成，其使用的格式如下：两个运算符来完成，其使用的格式如下：指针变量名指针变量名=new 类型名类型名(初始化式初始化式)；delete 指针名指针名;new运算符返回的是一个指向所分配类型变量对象的指针。对所运算符返回的是一个指向所分配类型变量对象的指针。对所创建的变量或对象，都是通过该指针来间接操作的，而动态创建的对象创建的变量或对象，都是通过该指针来间接操作的，而动态创建的对象本身没有名字。本身没有名

7、字。 7.1.1 堆内存的分配与释放一般定义变量和对象时要用标识符命名，称命名对象，而动一般定义变量和对象时要用标识符命名，称命名对象，而动态的称无名对象态的称无名对象( (请注意与栈区中的临时对象的区别，两者完请注意与栈区中的临时对象的区别，两者完全不同：生命期不同，操作方法不同，临时变量对程序员是全不同：生命期不同，操作方法不同，临时变量对程序员是透明的透明的) )。堆区是不会自动在分配时做初始化的包括清零），。堆区是不会自动在分配时做初始化的包括清零），所以必须用初始化式所以必须用初始化式(initializer)(initializer)来显式初始化。来显式初始化。newnew表达表达

8、式的操作序列如下：从堆区分配对象，然后用括号中的值初式的操作序列如下：从堆区分配对象，然后用括号中的值初始化该对象。从堆区分配对象时，始化该对象。从堆区分配对象时，newnew表达式调用库操作符表达式调用库操作符new()new()。例如：。例如： int int * *pi=new int(0);pi=new int(0);它与下列代码序列大体等价：它与下列代码序列大体等价：int ival=0;int ival=0;int int * *pi=&ival;pi=&ival;只是只是pipi现在所指向的变量是由库操作符现在所指向的变量是由库操作符new()new()分配的，位

9、于程分配的，位于程序的堆区中，并且该对象未命名。序的堆区中，并且该对象未命名。 7.1.1 堆内存的分配与释放堆堆i下面看演示：下面看演示：用初始化式用初始化式(initializer)(initializer)来显式初始化来显式初始化 int int * *pi=new int(0);pi=new int(0);当当pipi生命周期结束时，生命周期结束时，必须释放必须释放pipi所指向的目标：所指向的目标： delete pi;delete pi;注意这时释放了注意这时释放了pipi所指的目标的内存空间，也就是撤销了所指的目标的内存空间，也就是撤销了该目标，称动态内存释放该目标，称动态内存释

10、放dynamic memory dynamic memory deallocationdeallocation），但指针），但指针pipi本身并没有撤销，它自己仍然本身并没有撤销，它自己仍然存在，该指针所占内存空间并未释放。存在，该指针所占内存空间并未释放。 7.1.1 堆内存的分配与释放堆内存的分配与释放对于数组进行动态分配的格式为：对于数组进行动态分配的格式为：指针变量名指针变量名=new =new 类型名类型名 下标表达式下标表达式;delete delete 指向该数组的指针变量名指向该数组的指针变量名; ;两式中的方括号是非常重要的，两者必须配对使两式中的方括号是非常重要的，两者必须

11、配对使用，如果用，如果deletedelete语句中少了方括号，因编译器认语句中少了方括号，因编译器认为该指针是指向数组第一个元素的指针，会产生为该指针是指向数组第一个元素的指针，会产生回收不彻底的问题只回收了第一个元素所占空回收不彻底的问题只回收了第一个元素所占空间），加了方括号后就转化为指向数组的指针，间），加了方括号后就转化为指向数组的指针，回收整个数组。回收整个数组。delete delete 的方括号中不需要填的方括号中不需要填数组元素数，系统自知。即使写了，编译器也忽数组元素数，系统自知。即使写了，编译器也忽略。略。请注意请注意“下标表达式不是常量表达式，即它的值下标表达式不是常量

12、表达式，即它的值不必在编译时确定，可以在运行时确定。不必在编译时确定，可以在运行时确定。7.1.1 堆内存的分配与释放堆内存的分配与释放【例【例7.1】动态数组的建立与撤销】动态数组的建立与撤销#include #include void main()int n;char *pc;cout请输入动态数组的元素个数请输入动态数组的元素个数n; /在运行时确定，可输入在运行时确定，可输入17pc=new charn; /申请申请17个字符可装个字符可装8个汉字和一个结束符的内存空间个汉字和一个结束符的内存空间strcpy(pc,堆内存的动态分配堆内存的动态分配);coutpcendl;delete

13、 pc;/释放释放pc所指向的所指向的n个字符的内存空间个字符的内存空间return ;7.1.1 堆内存的分配与释放堆内存的分配与释放动态分配数组有三个特点：动态分配数组有三个特点：变量变量n在编译时没有确定的值，而是在运行中输入，按运在编译时没有确定的值，而是在运行中输入，按运行时所需分配堆空间，这一点是动态分配的优点，可克行时所需分配堆空间，这一点是动态分配的优点，可克服数组服数组“大开小用的弊端，在表、排序与查找中的算大开小用的弊端，在表、排序与查找中的算法，若用动态数组，通用性更佳。法，若用动态数组，通用性更佳。delete pc是将是将n个字个字符的空间释放，而用符的空间释放，而用

14、delete pc则只释放了一个字符的空则只释放了一个字符的空间；间；如果有一个如果有一个char *pc1，令，令pc1=p，同样可用，同样可用delete pc1来来释放该空间。尽管释放该空间。尽管C+不对数组作边界检查，但在堆空不对数组作边界检查，但在堆空间分配时，对数组分配空间大小是纪录在案的。间分配时，对数组分配空间大小是纪录在案的。没有初始化式没有初始化式initializer），不可对数组初始化。），不可对数组初始化。 7.1.1 堆内存的分配与释放堆内存的分配与释放多维数组动态分配：多维数组动态分配：new 类型名类型名下标表达式下标表达式1 下标表达式下标表达式2;建立一个动

15、态三维数组建立一个动态三维数组float (*cp)3020 ; /指向一个指向一个30行行20列数组列数组的指针的指针cp=new float 15 30 20; /建立由建立由15个个30*20数组组成的数组；数组组成的数组；注意注意cp等效于三维数组名，但没有指出其边界，即等效于三维数组名，但没有指出其边界，即最高维的元素数量，就像指向字符的指针即等效一最高维的元素数量，就像指向字符的指针即等效一个字符串个字符串,不要把指向字符的指针，说成指向字符串不要把指向字符的指针，说成指向字符串的指针。这与数组的嵌套定义相一致。的指针。这与数组的嵌套定义相一致。7.1.1 堆内存的分配与释放堆内存

16、的分配与释放比较：比较：float(*cp) 30 20; /三级指针；三级指针；float (*bp) 20; /二级指针；二级指针；cp=new float 1 20 30;bp=new float 30 20;两个数组都是由两个数组都是由600个浮点数组成，前者是只有个浮点数组成，前者是只有一个元素的三维数组，每个元素为一个元素的三维数组，每个元素为30行行20列的二列的二维数组，而另一个是有维数组，而另一个是有30个元素的二维数组，每个元素的二维数组，每个元素为个元素为20个元素的一维数组。删除这两个动态个元素的一维数组。删除这两个动态数组可用下式：数组可用下式：delete cp;

17、/删除释放三维数组；删除释放三维数组；delete bp; /删除释放二维数组；删除释放二维数组；7.1.1 堆内存的分配与释放堆内存的分配与释放【例【例7.2】 动态创建和删除一个动态创建和删除一个m*n个元素的数组。采用指针数组方个元素的数组。采用指针数组方式来完成二维数组的动态创建。式来完成二维数组的动态创建。const int m=4; /行数行数const int n=6; /列数列数先看二维数组的动态创建：先看二维数组的动态创建：void main() double *data; data = new double*m; /设置行设置行 if (data ) = 0) cout C

18、ouuld not allocate. Bye .;exit(-1); for(int j=0;jm;j+) dataj = new doublen; /设置列设置列 if (dataj = 0) cout Couuld not allocate. Bye .;exit(-1); for (int i=0;im;i+) for (int j=0;jn;j+) dataij=i*n+j;/初始化数组元素初始化数组元素 display(data); de_allocate(data); return; 7.1.1 堆内存的分配与释放堆内存的分配与释放再看二维数组的撤销与内存释放：再看二维数组的撤销

19、与内存释放：void de_allocate(double *data) for (int i=0;im;i+) delete datai; /注意撤销次序，先列后行，与设置相反注意撤销次序，先列后行，与设置相反 delete data; 在在VC+平台上演示本例。平台上演示本例。指针使用的几个问题：指针使用的几个问题：动态分配失败。返回一个空指针动态分配失败。返回一个空指针NULL），表示发生），表示发生了异常，堆资源不足，分配失败。了异常，堆资源不足，分配失败。指针删除与堆空间释放。删除一个指针指针删除与堆空间释放。删除一个指针pdelete p;）实际）实际意思是删除了意思是删除了p所指

20、的目标变量或对象等），释放了它所占的堆空所指的目标变量或对象等），释放了它所占的堆空间，而不是删除本身，释放堆空间后，成了空悬指针。间，而不是删除本身，释放堆空间后，成了空悬指针。7.1.1 堆内存的分配与释放堆内存的分配与释放内存泄漏内存泄漏memory leak和重复释放。和重复释放。new与与delete 是配对使用的，是配对使用的， delete只能释放堆空间。如果只能释放堆空间。如果new返回的指针值丢失，则所分配的堆空间无法回收，称返回的指针值丢失，则所分配的堆空间无法回收，称内存泄漏，同一空间重复释放也是危险的，因为该空间可内存泄漏，同一空间重复释放也是危险的，因为该空间可能已另

21、分配，所以必须妥善保存能已另分配，所以必须妥善保存new返回的指针，以保证返回的指针，以保证不发生内存泄漏，也必须保证不会重复释放堆内存空间。不发生内存泄漏，也必须保证不会重复释放堆内存空间。动态分配的变量或对象的生命期。无名对象的生命期动态分配的变量或对象的生命期。无名对象的生命期并不依赖于建立它的作用域，比如在函数中建立的动态对并不依赖于建立它的作用域，比如在函数中建立的动态对象在函数返回后仍可使用。我们也称堆空间为自由空间象在函数返回后仍可使用。我们也称堆空间为自由空间free store就是这个原因。但必须记住释放该对象所就是这个原因。但必须记住释放该对象所占堆空间，并只能释放一次，在

22、函数内建立，而在函数外占堆空间，并只能释放一次，在函数内建立，而在函数外释放是一件很容易失控的事，往往会出错。释放是一件很容易失控的事，往往会出错。 7.1.2堆对象与构造函数堆对象与构造函数 通过通过new建立的对象要调用构造函数，通过建立的对象要调用构造函数，通过deletee删除对象删除对象也要调用析构函数。也要调用析构函数。CGoods *pc;pc=new CGoods; /分配堆空间，并构造一个无名的分配堆空间，并构造一个无名的CGoods对象；对象；.delete pc; /先析构，然后将内存空间返回给堆；先析构，然后将内存空间返回给堆； 堆对象的生命期并不依赖于建立它的作用域，

23、所以除非程序堆对象的生命期并不依赖于建立它的作用域，所以除非程序结束，堆对象无名对象的生命期不会到期，并且需要显式结束，堆对象无名对象的生命期不会到期，并且需要显式地用地用delete语句析构堆对象，上面的堆对象在执行语句析构堆对象，上面的堆对象在执行delete语句时，语句时，C+自动调用其析构函数。自动调用其析构函数。正因为构造函数可以有参数，所以正因为构造函数可以有参数，所以new后面类后面类class类型也可类型也可以有参数。这些参数即构造函数的参数。但对创建数组，则无以有参数。这些参数即构造函数的参数。但对创建数组，则无参数，并只调用缺省的构造函数。见下例类说明：参数，并只调用缺省的

24、构造函数。见下例类说明：7.1.2堆对象与构造函数堆对象与构造函数class CGoods char Name21; int Amount; float Price; float Total value;public: CGoods(); /缺省构造函数。缺省构造函数。 /因已有构造函数，系统不会自动生成，必须显式说明。因已有构造函数，系统不会自动生成，必须显式说明。 CGoods(char* name,int amount ,float price) strcpy(Name,name); Amount=amount; Price=price; Total_value=price*amount

25、; 7.1.2堆对象与构造函数堆对象与构造函数下面注意如何使用：下面注意如何使用：void 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;

26、7.1.2堆对象与构造函数堆对象与构造函数这里再次强调：由堆区创建对象数这里再次强调：由堆区创建对象数组，只能调用缺省的构造函数，不能调组，只能调用缺省的构造函数，不能调用其他任何构造函数。如果没有缺省的用其他任何构造函数。如果没有缺省的构造函数，则不能创建对象数组。构造函数，则不能创建对象数组。7.1.3浅拷贝与深拷贝浅拷贝与深拷贝 缺省拷贝构造函数，可用一个类对象初始化另一个缺省拷贝构造函数，可用一个类对象初始化另一个类对象，称为缺省的按成员拷贝，而不是对整个类对象类对象，称为缺省的按成员拷贝，而不是对整个类对象的按位拷贝。这称为浅拷贝。的按位拷贝。这称为浅拷贝。 P堆对堆对象象堆对堆对象

27、象PP 图图7.1 浅拷贝浅拷贝 拷贝前拷贝后拷贝后 7.1.3浅拷贝与深拷贝浅拷贝与深拷贝如果类中有一个数据成员为指针，如果类中有一个数据成员为指针，该类的一个对象该类的一个对象obj1中的这个指针中的这个指针p，指向了动态分配的一个堆对象，（参指向了动态分配的一个堆对象，（参见图见图7.1拷贝前），如果用拷贝前），如果用obj1按成员按成员拷贝了一个对象拷贝了一个对象obj2，这时，这时obj2.p也也指向同一个堆对象。当析构时，如用指向同一个堆对象。当析构时，如用缺省的析构函数，则动态分配的堆对缺省的析构函数，则动态分配的堆对象不能回收。如果在析构函数中有象不能回收。如果在析构函数中有“

28、delete p;”语句，则如果先析构函数语句，则如果先析构函数obj1时，堆对象已经释放，以后再析时，堆对象已经释放，以后再析构构obj2时出现了二次释放的问题。这时出现了二次释放的问题。这时就要重新定义拷贝的构造函数，给时就要重新定义拷贝的构造函数，给每个对象独立分配一个堆对象，称深每个对象独立分配一个堆对象，称深拷贝。这时先拷贝对象主体，再为拷贝。这时先拷贝对象主体，再为obj2分配一个堆对象，最后用分配一个堆对象，最后用obj1的的堆对象拷贝堆对象拷贝obj2的堆对象。的堆对象。 堆对堆对象象PP堆对堆对象象 图图7.2 深拷贝深拷贝 7.1.3浅拷贝与深拷贝浅拷贝与深拷贝例例7.3定

29、义拷贝定义拷贝copy structor和拷贝赋值操作符和拷贝赋值操作符copy Assignment Operator实现深拷贝。实现深拷贝。 学生类定义：学生类定义：class studentchar *pName; /指针成员指针成员public:student();student(char *pname);student(student &s); /拷贝构造函数拷贝构造函数student();student & operator=(student &s); /拷贝赋值操作符拷贝赋值操作符;缺省构造函数：缺省构造函数：student:student()coutCo

30、nstructor;pName=NULL;cout缺省缺省endl;7.1.3浅拷贝与深拷贝浅拷贝与深拷贝带参数构造函数：带参数构造函数：student:student(char *pname) coutConstructor; if(pName=new charstrlen(pname)+1) strcpy(pName,pname); coutpNameendl;拷贝构造函数：拷贝构造函数：student:student(student &s) coutCopy Constructor; if(s.pName) if(pName=new charstrlen(s.pName)+1)

31、strcpy(pName,s.pName); /加一不可少，否则串结束符冲了其他信息，析构会出错！加一不可少，否则串结束符冲了其他信息，析构会出错！ else pName=NULL; coutpNameendl;7.1.3浅拷贝与深拷贝浅拷贝与深拷贝析构函数：析构函数：student:student() coutDestructorpNameendl; if(pName) pName0=0; delete pName; /释放字符串释放字符串拷贝赋值操作符：拷贝赋值操作符：student & student:operator=(student &s) coutCopy Assi

32、gn operator; delete pName; /如原来已分配，应先撤销，再重分配如原来已分配，应先撤销，再重分配 if(s.pName) if(pName=new charstrlen(s.pName)+1) strcpy(pName,s.pName); else pName=NULL; coutpNamedata) /回车结束回车结束 p1=new(node);/每输入一个数申请一个结点每输入一个数申请一个结点p1-info=data; /添入数据添入数据p0-link= p1; /新结点接到链尾新结点接到链尾 P0=p1; /尾指针到链尾尾指针到链尾 tail-next=NULL;

33、/链尾加空指针，表示链结束链尾加空指针，表示链结束 return head; /返回头指针返回头指针 7.2.1 单链表基本算法单链表基本算法headinfo0 PPinfo12. 向前生成链表算法向前生成链表算法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 ;/新结点放在原链表前方新结点放在原链表前方

34、head-link=p; /头结点放新结点之前头结点放新结点之前 return head;7.2.1 单链表基本算法单链表基本算法3.链表查找算法链表查找算法Traversal），按数据关键字查），按数据关键字查找：找：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. 在单链表的在单链表的p节点后插入一个信息域为节点后

35、插入一个信息域为x的新节点的新节点注意只有一种情况了）。注意只有一种情况了）。void insert(node p,Datatype x) node *q=new node; q-info=x; q-link=p-link; p-link=q;7.2.1 单链表基本算法单链表基本算法5. 删除单链表节点删除单链表节点*p后面节点后面节点void del (node *p) node *q; q=p-link; p-link=q-link; delete q; /如果要把该节点移入另一个链中，则可将如果要把该节点移入另一个链中，则可将q返回。返回。7.2.2 单链表类型模板单链表类型模板【例【例

36、7.4_h】单链表类模板。】单链表类模板。 首先看结点组织，采用结点类，凡与结点数据和指针操作有关函数首先看结点组织，采用结点类，凡与结点数据和指针操作有关函数作为成员函数作为成员函数:templateclass List;templateclass Node T info; /数据域数据域 Node *link; /指针域指针域public: Node(); /生成头结点的构造函数生成头结点的构造函数 Node(const T & data); /生成一般结点的构造函数生成一般结点的构造函数 void InsertAfter(Node* p); /在当前结点后插入一个结点在当前结点后

37、插入一个结点 Node* RemoveAfter(); /删除当前结点的后继结点删除当前结点的后继结点 friend class List; /以以List为友元类，为友元类，List可直接访问可直接访问Node的私有函数的私有函数;7.2.2 单链表类型模板单链表类型模板看结点类成员函数看结点类成员函数:template Node:Node()link=NULL;template Node:Node(const T & data)info=data;link=NULL;templatevoid Node:InsertAfter(Node* p)p-link=link;link=p;t

38、emplateNode* Node:RemoveAfter()Node* tempP=link;if(link=NULL) tempP=NULL; /已在链尾已在链尾,后面无结点后面无结点else link=tempP-link;return tempP;再定义链表类，操作包括建立有序链表、搜索遍历、插入、删除、再定义链表类，操作包括建立有序链表、搜索遍历、插入、删除、取数据等取数据等: templateclass List Node *head,*tail; /链表头指针和尾指针链表头指针和尾指针public: List(); /构造函数，生成头结点构造函数，生成头结点(空链表空链表) Li

39、st(); /析构函数析构函数 void MakeEmpty(); /清空一个链表，只余表头结点清空一个链表，只余表头结点 Node* Find(T data); /搜索数据域与搜索数据域与data相同的结点，返回该结点的地址相同的结点，返回该结点的地址 int Length(); /计算单链表长度计算单链表长度 void PrintList(); /打印链表的数据域打印链表的数据域 void InsertFront(Node* p); /可用来向前生成链表可用来向前生成链表 void InsertRear(Node* p); /可用来向后生成链表可用来向后生成链表 void InsertOr

40、der(Node *p); /按升序生成链表按升序生成链表 Node*CreatNode(T data); /创建一个结点创建一个结点(孤立结点孤立结点) Node*DeleteNode(Node* p); /删除指定结点删除指定结点;7.2.2 单链表类型模板单链表类型模板7.2.2 单链表类型模板单链表类型模板链表类成员函数：链表类成员函数：templateList:List() head=tail=new Node();templateList:List() MakeEmpty();delete head;templatevoid List:MakeEmpty() Node *tempP

41、; while(head-link!=NULL) tempP=head-link; head-link=tempP-link; /把头结点后的第一个结点从链中脱离把头结点后的第一个结点从链中脱离 delete tempP; /删除删除(释放释放)脱离下来的结点脱离下来的结点 tail=head; /表头指针与表尾指针均指向表头结点，表示空链表头指针与表尾指针均指向表头结点，表示空链template Node* List:Find(T data) Node *tempP=head-link; while(tempP!=NULL&tempP-info!=data) tempP=tempP-

42、link; return tempP; /搜索成功返回该结点地址，不成功返回搜索成功返回该结点地址，不成功返回NULL7.2.2 单链表类型模板单链表类型模板templateint List:Length() Node* tempP=head-link; int count=0; while(tempP!=NULL) tempP=tempP-link;count+; return count;templatevoid List:PrintList() Node* tempP=head-link; while(tempP!=NULL) coutinfolink; coutendl;templat

43、evoid List:InsertFront(Node *p) p-link=head-link;head-link=p; if(tail=head) tail=p;templatevoid List:InsertRear(Node *p) p-link=tail-link;tail-link=p;tail=p;templateNode* List:CreatNode(T data) Node*tempP=new Node(data);return tempP;templatevoid List:InsertOrder(Node *p) Node *tempP=head-link,*tempQ

44、=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:DeleteNode(Node* p) Node* tempP=head; while(t

45、empP-link!=NULL&tempP-link!=p) tempP=tempP-link; if(tempP-link=tail) tail=tempP; return tempP-RemoveAfter(); /本函数所用方法可省一个工作指针，与本函数所用方法可省一个工作指针，与InsertOrder比较比较7.2.2 7.2.2 单链表类型模板单链表类型模板7.2.2 单链表类型模板单链表类型模板【例【例7.47.4】由键盘输入】由键盘输入1616个整数，以这些整数作为结点数据，个整数，以这些整数作为结点数据，生成两个链表，一个向前生成，一个向后生成，输出两个生成两个链表，一

46、个向前生成，一个向后生成，输出两个表。然后给出一个整数在一个链表中查找，找到后删除它，表。然后给出一个整数在一个链表中查找，找到后删除它，再输出该表。清空该表，再按升序生成链表并输出。再输出该表。清空该表，再按升序生成链表并输出。在在VC+VC+平台上演示本例。平台上演示本例。在本例中程序只需调用类模板中的成员函数就可以完成所在本例中程序只需调用类模板中的成员函数就可以完成所有链表操作。有链表操作。7.2.3 双向链表双向链表 考虑顺序表中总是可以很方便地找到表元素的前驱和后继，考虑顺序表中总是可以很方便地找到表元素的前驱和后继，但单链表只能找后继。如要找前驱，必须从表头开始搜索。为但单链表只

47、能找后继。如要找前驱，必须从表头开始搜索。为了克服这一缺点，可采用双向链表了克服这一缺点，可采用双向链表Double Linked List)Double Linked List)。双。双向链表的结点有三个域：左链接指针向链表的结点有三个域：左链接指针llink)llink)，数据域，数据域info)info)，右链接指针域右链接指针域(rlink)(rlink)。双向链表经常采用带头结点的循环链表。双向链表经常采用带头结点的循环链表方式。方式。 info0 infon-1. info1head(a) 非空表非空表head(b)空表空表7.2.3 双向链表双向链表假设指针假设指针p p指向双向

48、循环链表的某一个结点，那么，指向双向循环链表的某一个结点，那么，p-p-llinkllink指示指示P P所指结点的前驱结点，所指结点的前驱结点，p-rlinkp-rlink指示后继结指示后继结点。点。p-llink-rlinkp-llink-rlink指示本结点的前驱结点的后继结点，指示本结点的前驱结点的后继结点，即本结点，间接访问符即本结点，间接访问符-可以连续使用。可以连续使用。pllink rlinkrlinkllink rlink前驱结点前驱结点 llink 本结点本结点 后继结点后继结点 间接访问符的使用间接访问符的使用在在VC+平台上演示例平台上演示例7.5双向链表类模板和结点类

49、模板。双向链表类模板和结点类模板。7.3 栈与队列的基本操作及其应用栈与队列的基本操作及其应用 栈和队都是特殊的线性表，限制存栈和队都是特殊的线性表，限制存取位置的线性结构，可以由顺序表实现，取位置的线性结构，可以由顺序表实现，也可以由链表实现。也可以由链表实现。 7.3.1 栈与应用栈与应用 7.3.2队列队列 7.3.1 栈与应用栈与应用栈定义为只允许在表的一端进行插入和删除的线性表。栈定义为只允许在表的一端进行插入和删除的线性表。允许进行插入和删除的一端叫做栈顶允许进行插入和删除的一端叫做栈顶(top)，而另一端叫栈，而另一端叫栈底底(bottom)。栈中没有任何元素时，称为空栈。参见下

50、图，。栈中没有任何元素时，称为空栈。参见下图，设给定栈设给定栈s=(a0，a1，an-1)，称，称a0为栈底，为栈底，an-1为栈为栈顶。进栈时最先进栈的顶。进栈时最先进栈的a0在最下面，在最下面，an-1在最上面，后来在最上面，后来居上。而出栈时顺序相反，最后进栈的居上。而出栈时顺序相反，最后进栈的an-1最先出栈，而最先出栈，而最先进栈的最先进栈的a0最后出栈。所以栈又称作后进先出最后出栈。所以栈又称作后进先出LIFO：Last In First Out的线性表。的线性表。 栈可以用顺序表实现，称顺序栈；也可以用链表实现，栈可以用顺序表实现，称顺序栈；也可以用链表实现，称链栈。称链栈。a0

51、an-2a1an-1bottom进栈进栈toptoptoptoptop出栈出栈图示为顺序栈。其中栈底图示为顺序栈。其中栈底bottom是指向栈数据区的下是指向栈数据区的下一单元，这样判断是否为空一单元，这样判断是否为空栈会更方便，只需栈会更方便，只需top与与bottom相同就是空栈。通常相同就是空栈。通常只有栈顶与操作有关。只有栈顶与操作有关。7.3.1 栈与应用栈与应用顺序栈的类模板定义：顺序栈的类模板定义：templateclass Stack int top; /栈顶指针下标）栈顶指针下标） T *elements; /动态建立的元素动态建立的元素 int maxSize; /栈最大容

52、纳的元素个数栈最大容纳的元素个数public: Stack(int=20); /栈如不指定大小，设为栈如不指定大小，设为20元素元素 Stack()delete elements; void Push(const T &data); /压栈压栈 T Pop(); /弹出，弹出，top- T GetElem(int i); /取数据，取数据，top不变不变 void MakeEmpty()top= -1; /清空栈清空栈 bool IsEmpty() constreturn top= -1; /判栈空判栈空 bool IsFull() constreturn top=maxSize-1;

53、 /判栈满判栈满 void PrintStack(); /输出栈内所有数据输出栈内所有数据;7.3.1 栈与应用栈与应用template Stack:Stack(int maxs) maxSize=maxs; top=-1; elements=new T maxSize; /建立栈空间建立栈空间 assert(elements!=0); /分配不成功结束程序分配不成功结束程序template void Stack:PrintStack() for(int i=0;i=top;i+) coutelementsit; coutendl;template void Stack:Push(const

54、T &data) assert(!IsFull(); /栈满则退出程序栈满则退出程序 elements+top=data; /栈顶指针先加栈顶指针先加1，元素再进栈，元素再进栈template T Stack:Pop() assert(!IsEmpty(); /栈已空则不能退栈，退出程序栈已空则不能退栈，退出程序 return elementstop-; /返回栈顶元素，同时栈顶指针退返回栈顶元素，同时栈顶指针退1template T Stack:GetElem(int I) assert(i=0); /超出栈有效数据则错，退出程序超出栈有效数据则错，退出程序 return eleme

55、ntsi; /返回栈顶元素，返回栈顶元素，top不变不变在在VC+平台上演示例平台上演示例7.6顺序栈的类模板的应用。顺序栈的类模板的应用。7.3.1 栈与应用栈与应用链栈的类模板链栈的类模板: templateclass Stack;templateclass Node /链栈结链栈结点类模板点类模板T info;Node *link;public:Node(T data=0,Node *next=NULL)info=data;link=next;friend class Stack;top 链栈7.3.1 栈与应用栈与应用templateclass Stack /链栈类模板，无头结点链表链

56、栈类模板，无头结点链表Node *top; /栈顶指针栈顶指针public:Stack()top=NULL;Stack();void Push(const T &data); /压栈压栈T Pop(); /弹出弹出T GetTop(); /取栈顶元素取栈顶元素void MakeEmpty(); /清空栈清空栈bool IsEmpty()return top=NULL;template Stack:Stack()MakeEmpty();templatevoid Stack:MakeEmpty()Node *temp;while(top!=NULL)temp=top;top=top-lin

57、k;delete temp; 7.3.1 栈与应用栈与应用template void Stack:Push(const T &data) top=new Node(data,top); /链栈向前生成，新结点在链栈链栈向前生成，新结点在链栈头头template T Stack:Pop()assert(!IsEmpty();Node *temp=top;T data=temp-info;top=top-link; /丢弃栈顶结点丢弃栈顶结点delete temp; /释放栈顶结点释放栈顶结点return data; /返回栈顶数据返回栈顶数据template T Stack:GetTop

58、()assert(!IsEmpty();return top-info;7.3.1 栈与应用栈与应用顺序栈和链栈逻辑功能是一样，尽管这里两个栈顺序栈和链栈逻辑功能是一样，尽管这里两个栈模板的成员函数功能选择稍有出入，因为顺序栈可以模板的成员函数功能选择稍有出入，因为顺序栈可以随机访问其中的元素，而链栈只能顺序访问，但逻辑随机访问其中的元素，而链栈只能顺序访问，但逻辑上完全可以做到一样物理结构不同）。顺序栈必须上完全可以做到一样物理结构不同）。顺序栈必须先开一定大小内存空间，执行起来简单，速度快，可先开一定大小内存空间，执行起来简单，速度快，可能溢出。链栈内存空间随用随开，不会溢出，但执行能溢出

59、。链栈内存空间随用随开，不会溢出，但执行复杂不断地动态分配），速度慢。复杂不断地动态分配），速度慢。 NcbaOat1deNat1deOONt1at2t1at2t3aNt3aNOOb*c-t1d/e-t2t1-t2-t3a+t3-t4N：数栈：数栈 O：运算符：运算符 (a) (b) (c) (d) (e) 表达式运算 栈可用于表达式的计算。现考虑最简单的栈可用于表达式的计算。现考虑最简单的+、-、*、/四个运算符和结束符四个运算符和结束符组成的算术表达式，只有两个优先级，先组成的算术表达式，只有两个优先级，先*/，后，后+-。设有：。设有：a+b*c-d/e= 为实现运算符的优先级，采用两个

60、栈：一个数栈，一个运算符栈。数栈暂为实现运算符的优先级，采用两个栈：一个数栈，一个运算符栈。数栈暂存操作数，运算符栈暂存运算符。从左向右扫描算术表达式，遇到操作数，存操作数，运算符栈暂存运算符。从左向右扫描算术表达式，遇到操作数，压入数栈；遇到运算符，则与运算符栈栈顶的运算符比较优先级，若新的运压入数栈；遇到运算符，则与运算符栈栈顶的运算符比较优先级，若新的运算符优先级高，或运算符栈空，则压栈。否则将栈顶运算符出栈，与数字栈算符优先级高，或运算符栈空，则压栈。否则将栈顶运算符出栈，与数字栈出栈的两个数据进行运算，结果压入数栈，再将新运算符压栈。继续扫描，出栈的两个数据进行运算，结果压入数栈，再将新运算符压栈。继续扫描，直到遇到号，扫描结束。栈中数据继续按前面规则出栈。直到遇到号，扫描结束。栈中数据继续按前面规则出栈。 7.3.1 栈与应用栈与应用【例