1、unit07动态分配内存空间动态分配内存空间7.17.1自由存储区内存分配自由存储区内存分配 7.1.1自由存储区自由存储区内存内存的分配与释放的分配与释放 7.1.2自由存储区自由存储区对象对象与构造函数与构造函数 7.1.3 浅复制与深复制浅复制与深复制 静态存储分配：静态存储分配：通常定义变量通常定义变量(或对象或对象)，编译器，编译器在编译时都可以根据该变量在编译时都可以根据该变量(或或对象对象)的类型知道所需内存空间的类型知道所需内存空间的大小，从而系统在适当的时候的大小，从而系统在适当的时候为它们分配确定的存储空间。为它们分配确定的存储空间。动态存储分配：动态存储分配：有些操作对象
2、只有在程序运行时有些操作对象只有在程序运行时才能确定，这样编译器在编译时才能确定，这样编译器在编译时就无法为他们预定存储空间，只就无法为他们预定存储空间，只能在程序运行时，系统根据运行能在程序运行时，系统根据运行时的要求进行内存分配，称为动时的要求进行内存分配，称为动态存储分配。动态分配都在态存储分配。动态分配都在自由自由存储区存储区中进行。中进行。7.1.17.1.1自由存储区自由存储区内存的分配与释放内存的分配与释放当程序运行到需要一个动态分配的变量或对象时，必须向系当程序运行到需要一个动态分配的变量或对象时，必须向系统统申请取得自由存储区申请取得自由存储区中的一块所需大小的存贮空间，用于
3、存中的一块所需大小的存贮空间，用于存贮该变量或对象。当不再使用该变量或对象时，也就是它的生贮该变量或对象。当不再使用该变量或对象时，也就是它的生命结束时，要命结束时，要显式释放显式释放它所占用的存贮空间，这样系统就能进它所占用的存贮空间，这样系统就能进行再次分配，做到重复使用有限的资源。行再次分配，做到重复使用有限的资源。申请和释放申请和释放自由存储区自由存储区中分配的存贮空间，分别使用中分配的存贮空间，分别使用newnew和和deletedelete的两个运算符来完成，其使用的格式如下：的两个运算符来完成，其使用的格式如下：指针变量名指针变量名=new=new 类型名类型名(初始化式初始化式
4、)；delete delete 指针名指针名;newnew运算符运算符返回返回的是一个指向所分配类型变量（对象）的的是一个指向所分配类型变量（对象）的指针指针。对所创建的变量或对象，都是通过该指针来间接操作的，。对所创建的变量或对象，都是通过该指针来间接操作的，而而动态创建的对象本身没有名字。动态创建的对象本身没有名字。动态分配与释放：动态分配与释放：7.1.17.1.1自由存储区自由存储区内存的分配与释放内存的分配与释放一般定义变量和对象时要用标识符命名，称一般定义变量和对象时要用标识符命名，称命名对象命名对象，而动，而动态的称态的称无名对象无名对象(请注意与栈区中的临时对象的区别，两者完请
5、注意与栈区中的临时对象的区别，两者完全不同：生命期不同，操作方法不同，临时变量对程序员是全不同：生命期不同，操作方法不同，临时变量对程序员是透明的透明的)。自由存储区自由存储区是不会自动在分配时做初始化的（包括是不会自动在分配时做初始化的（包括清零），所以必须用初始化式清零），所以必须用初始化式(initializer)(initializer)来显式初始化。来显式初始化。newnew表达式的操作：表达式的操作：从自由存储区分配对象，然后用括号中的值初始化该对象从自由存储区分配对象，然后用括号中的值初始化该对象。分配对象时，分配对象时，new表达式调用库操作符表达式调用库操作符new()：in
6、t*pi=new int(0);pi现在所指向的变量的存储空间是由库操作符现在所指向的变量的存储空间是由库操作符new()分配的，分配的，位于程序的自由存储区中，并且该对象未命名。位于程序的自由存储区中，并且该对象未命名。无名对象：无名对象：7.1.17.1.1自由存储区自由存储区内存的分配与释放内存的分配与释放自由存储区自由存储区i演示：演示：用初始化式用初始化式(initializer)(initializer)来显式初始化来显式初始化 int int*pi=new int(0);pi=new int(0);当当pipi生命周期结束时，生命周期结束时，必须释放必须释放pipi所指向的目标：
7、所指向的目标：delete pi;delete pi;注意这时释放了注意这时释放了pipi所指的目标的内存空间，也就是撤销了所指的目标的内存空间，也就是撤销了该目标，称动态内存释放（该目标，称动态内存释放（dynamic memory dynamic memory deallocationdeallocation），但），但指针指针pipi本身并没有撤销本身并没有撤销，该指针所占，该指针所占内存空间并未释放。内存空间并未释放。7.1.17.1.1自由存储区自由存储区内存的分配与释放内存的分配与释放数组动态分配格式：数组动态分配格式：指针变量名指针变量名=new=new 类型名类型名 下标表达式
8、下标表达式;Delete Delete 指向该数组的指针变量名指向该数组的指针变量名;说明：说明：两式中的两式中的方括号方括号必须配对使用。必须配对使用。如果如果delete语句中少了方括号，因编译器认为该指针是指语句中少了方括号，因编译器认为该指针是指向数组第一个元素的指针，会产生向数组第一个元素的指针，会产生回收不彻底回收不彻底的问题（的问题（只只回收了第一个元素所占空间回收了第一个元素所占空间），），加了方括号后就转化为指加了方括号后就转化为指向数组的指针，回收整个数组向数组的指针，回收整个数组。delete 的方括号中的方括号中不需要不需要填填数组元素数数组元素数，系统自知。，系统自知
9、。即使写了，编译器也忽略。即使写了，编译器也忽略。请注意请注意“下标表达式下标表达式”不是常量表达式不是常量表达式，即它的值不必，即它的值不必在编译时确定，在编译时确定，可以在运行时确定可以在运行时确定。7.1.17.1.1自由存储区自由存储区内存的分配与释放内存的分配与释放动态分配数组与动态分配数组与标准字符串类标准字符串类：标准字符串类标准字符串类string就是采用动态建立数组的方式解决就是采用动态建立数组的方式解决数组溢出的问题的，例数组溢出的问题的，例7.1所做的动态内存分配与释放，所做的动态内存分配与释放，在在string类对象中都是自动完成的，在程序中不需要也不类对象中都是自动完
10、成的，在程序中不需要也不允许再显式地为允许再显式地为string进行动态内存的分配与释放。进行动态内存的分配与释放。【例【例7.1】动态数组的建立与撤销】动态数组的建立与撤销7.1.17.1.1自由存储区自由存储区内存的分配与释放内存的分配与释放动态分配数组的特点：动态分配数组的特点：1.变量变量n在编译时没有确定的值，而是在运行中输入，在编译时没有确定的值，而是在运行中输入，按运行按运行时所需分配空间时所需分配空间，这一点是动态分配的优点，可克服数组，这一点是动态分配的优点，可克服数组“大开小用大开小用”的弊端，在表、排序与查找中的算法，若用的弊端，在表、排序与查找中的算法，若用动态数组，通
11、用性更佳。动态数组，通用性更佳。delete pc是将是将n个字符的空间个字符的空间释放，而用释放，而用delete pc则只释放了一个字符的空间；则只释放了一个字符的空间；2.如果有如果有char*pc1，令，令pc1=pc，同样可用，同样可用delete pc1 来释放该空间。尽管来释放该空间。尽管C+不对数组作边界检查，但不对数组作边界检查，但在自由在自由 存储区存储区 空间分配时，对数组分配空间大小是纪录在案的空间分配时，对数组分配空间大小是纪录在案的。3.没有初始化式（没有初始化式（initializer），），不可对数组初始化不可对数组初始化。7.1.17.1.1自由存储区自由存储
12、区内存的分配与释放内存的分配与释放（选读）（选读）多维数组动态分配：多维数组动态分配：new 类型名类型名下标表达式下标表达式1 下标表达式下标表达式2;建立一个动态三维数组建立一个动态三维数组float(*cp)3020;/指向一个指向一个30行行20列数组的指针列数组的指针cp=new float 15 30 20;/建立由建立由15个个30*20数组组成的数组；数组组成的数组；注意注意cp等效于三维数组名，但没有指出其边界，即等效于三维数组名，但没有指出其边界，即最高维的元素数量，就像指向字符的指针即等效一最高维的元素数量，就像指向字符的指针即等效一个字符串个字符串,不要把指向字符的指针
13、，说成指向字符串不要把指向字符的指针，说成指向字符串的指针的指针。这与数组的嵌套定义相一致。这与数组的嵌套定义相一致。7.1.17.1.1自由存储区自由存储区内存的分配与释放内存的分配与释放（选读）（选读）比较：比较：float(*cp)30 20;/三级指针三级指针float(*bp)20;/二级指针二级指针cp=new float 1 30 20;bp=new float 30 20;两个数组都是由两个数组都是由600个浮点数组成，前者是只有个浮点数组成，前者是只有一个元素一个元素的三维数组的三维数组，每个元素为，每个元素为30行行20列的二维数组，而另一列的二维数组，而另一个是有个是有3
14、0个元素的二维数组个元素的二维数组，每个元素为，每个元素为20个元素的一个元素的一维数组。维数组。删除这两个动态数组可用下式：删除这两个动态数组可用下式：delete cp;/删除（释放）三维数组删除（释放）三维数组delete bp;/删除（释放）二维数组删除（释放）二维数组【例【例7.2】动态创建和删除一个动态创建和删除一个m*n个元素的数组个元素的数组7.1.17.1.1自由存储区自由存储区的分配与释放的分配与释放指针使用的要点：指针使用的要点：1.动态分配失败动态分配失败。返回一个空指针（。返回一个空指针（NULL），表示发生了异），表示发生了异常，堆资源不足，分配失败。常，堆资源不足
15、，分配失败。指针删除与指针删除与自由存储区自由存储区空间释放空间释放。删除一个指针。删除一个指针p（delete p;）实际意思是删除了）实际意思是删除了p所指的目标（变量或对象等），所指的目标（变量或对象等），释放了它所占的自由存储区空间，而不是删除本身，释释放了它所占的自由存储区空间，而不是删除本身，释放自由存储区空间后，成了放自由存储区空间后，成了空悬指针空悬指针。空悬指针是程序。空悬指针是程序错误的一个根源）。建议这时将置空（错误的一个根源）。建议这时将置空（NULL）。）。3.new()和和delete()是可以重载的是可以重载的，它们都是类的静态，它们都是类的静态成员函数。程序员无
16、需显式声明它为静态的，系统自动成员函数。程序员无需显式声明它为静态的，系统自动定义为静态的。本教材不讨论定义为静态的。本教材不讨论new()和和delete()的重载。的重载。未重载时，调用全局库操作符未重载时，调用全局库操作符new()。7.1.17.1.1自由存储区自由存储区内存的分配与释放内存的分配与释放4内存泄漏（内存泄漏（memory leak）和重复释放）和重复释放。new与与delete 是配对使用的，是配对使用的，delete只能释放只能释放自由存储区自由存储区空间。空间。如果如果new返回的指针值丢失，则所分配的返回的指针值丢失，则所分配的自由存储区自由存储区空间空间无法回收
17、，称内存泄漏，同一空间重复释放也是危险的，无法回收，称内存泄漏，同一空间重复释放也是危险的，因为因为该空间可能已另分配该空间可能已另分配，所以必须妥善保存，所以必须妥善保存new返回的返回的指针，以保证不发生内存泄漏，也必须保证不会重复释放指针，以保证不发生内存泄漏，也必须保证不会重复释放自由存储区自由存储区内存空间。内存空间。5动态分配的变量或对象的生命期动态分配的变量或对象的生命期。无名对象的生命期无名对象的生命期并不依赖于建立它的作用域，比如在函数中建立的动态对并不依赖于建立它的作用域，比如在函数中建立的动态对象在函数返回后仍可使用象在函数返回后仍可使用。但必须记住释放该对象所占自。但必
18、须记住释放该对象所占自由存储区空间，并只能释放一次，在函数内建立，而在函由存储区空间，并只能释放一次，在函数内建立，而在函数外释放是一件很容易数外释放是一件很容易失控失控的事，往往会出错。的事，往往会出错。7.1.27.1.2自由存储区自由存储区对象与构造函数对象与构造函数 类对象动态建立与删除过程：类对象动态建立与删除过程：通过通过newnew建立的对象要调用构造函数，通过建立的对象要调用构造函数，通过deletedelete删除对象删除对象也要调用析构函数。也要调用析构函数。CGoods*pc;pc=new CGoods;/分配自由存储区空间，并构造一个无名的分配自由存储区空间，并构造一个
19、无名的CGoods对象；对象；.delete pc;/先析构，然后将内存空间返回给自由存储区；先析构，然后将内存空间返回给自由存储区；自由存储区自由存储区对象的生命期并不依赖于建立它的作用域，所以对象的生命期并不依赖于建立它的作用域，所以除非程序结束，除非程序结束，自由存储区自由存储区对象（无名对象）的生命期不会对象（无名对象）的生命期不会到期，并且需要显式地用到期，并且需要显式地用delete语句析构该类对象，上例执语句析构该类对象，上例执行行delete语句时，语句时，C+自动调用商品类的析构函数。自动调用商品类的析构函数。7.1.27.1.2自由存储区自由存储区对象与构造函数对象与构造函
20、数由自由存储区创建对象数组，只能调用默认由自由存储区创建对象数组，只能调用默认的构造函数，不能调用其他任何构造函数。如果的构造函数，不能调用其他任何构造函数。如果没有默认的构造函数，则不能创建对象数组。没有默认的构造函数，则不能创建对象数组。类对象初始化：类对象初始化：new后面类（后面类（class）类型可以有参数。这些参数即构造函数的）类型可以有参数。这些参数即构造函数的参数。但对参数。但对创建数组创建数组，则无参数，则无参数，只能调用默认的构造函数只能调用默认的构造函数。【例【例7.37.3】演示自由存储区对象分配和释放。】演示自由存储区对象分配和释放。7.1.3浅复制与深复制浅复制与深
21、复制 浅复制：浅复制：默认复制构造函数默认复制构造函数，可用一个类对象，可用一个类对象初始化另一个类对象，称为默认的初始化另一个类对象，称为默认的按成员复制，按成员复制，而不是而不是对整个类对象的对整个类对象的按位复制。按位复制。这称为这称为浅复制。浅复制。图图7.1 浅复制浅复制 P自 由 存自 由 存储 区 对储 区 对象象自 由 存自 由 存储 区储 区 对对象象PP 复制前复制前复制后复制后 如果类中有一个数据成员为指针，该类的一个对象如果类中有一个数据成员为指针，该类的一个对象obj1中中的这个指针的这个指针p，指向了动态分配的一个自由存储区对象，（参见，指向了动态分配的一个自由存储
22、区对象，（参见图图7.1复制前），如果用复制前），如果用obj1按成员复制了一个对象按成员复制了一个对象obj2，这时，这时obj2.p也指向同一个自由存储区对象。也指向同一个自由存储区对象。obj1obj1obj27.1.3浅复制与深复制复制浅复制与深复制复制当当浅复制浅复制析构时，如用默认的析构析构时，如用默认的析构函数，则动态分配的函数，则动态分配的自由存储区自由存储区对象不对象不能回收。如果在析构函数中有能回收。如果在析构函数中有“delete p;”语句，则如果先析构函数语句，则如果先析构函数obj1时，时，自由存储区自由存储区对象已经释放，以后再析构对象已经释放，以后再析构obj2
23、时出现了二次释放的问题。时出现了二次释放的问题。自由自由存储存储区区对对象象PP自由自由存储存储区区对对象象 图图7.2 深复制深复制 深复制：深复制：重新定义复制的构造函数，重新定义复制的构造函数，给每个对象独立分配一个自由存储区给每个对象独立分配一个自由存储区对象，称对象，称深复制深复制。这时先复制对象主这时先复制对象主体，再为体，再为obj2分配一个自由存储区对分配一个自由存储区对象，最后用象，最后用obj1的自由存储区对象复的自由存储区对象复制制obj2的自由存储区对象。的自由存储区对象。obj1obj27.1.3浅复制与深复制浅复制与深复制【例【例7.4】定义复制构造函数定义复制构造
24、函数（copy structor）和复制赋值操）和复制赋值操作符（作符（copy Assignment Operator）实现深复制。）实现深复制。学生类定义：学生类定义：class student char*pName;/为了演示深复制，不用为了演示深复制，不用string类类public:student();/默认构造函数默认构造函数 student(char*pname);/带参数构造函数带参数构造函数 student(student&s);/复制构造函数复制构造函数 student();/析构函数析构函数 student&operator=(student&s);/复制赋值操作符复制赋
25、值操作符检验主函数和运行结果检验主函数和运行结果7.1.3浅复制与深复制浅复制与深复制 提示：提示：自由存储区内存是最常见的需要自定义复制构自由存储区内存是最常见的需要自定义复制构造函数的资源，但不是唯一的，还有打开文件等也造函数的资源，但不是唯一的，还有打开文件等也需要自定义复制构造函数。需要自定义复制构造函数。如果类对象需要动态分配资源应该由构造函如果类对象需要动态分配资源应该由构造函数完成，而释放资源由析构函数完成，这时类也需数完成，而释放资源由析构函数完成，这时类也需要一个自定义的复制构造函数，实现对象的深复制。要一个自定义的复制构造函数，实现对象的深复制。由此可见，由此可见，构造函数
26、并非仅做初始化工作构造函数并非仅做初始化工作。7.1.3浅复制与深复制浅复制与深复制思考：思考：深入地考虑【例深入地考虑【例7.47.4】，如果数据域还有很多其他数】，如果数据域还有很多其他数据，甚至有好几个是动态建立的据，甚至有好几个是动态建立的C C字符串，深复制是不是太字符串，深复制是不是太复杂了？如果使用复杂了？如果使用C+C+标准字符串标准字符串stringstring作为成员对象（聚作为成员对象（聚合）合）是否就不需要考虑深复制了？是否就不需要考虑深复制了？的确是这样的，准确地说，的确是这样的，准确地说，string类的内部包含动态建立字类的内部包含动态建立字符数组的操作，其复制构
27、造函数是深复制。如果在符数组的操作，其复制构造函数是深复制。如果在student类中使用类中使用string类而不是类而不是C字符串，就不要再考虑深复制问字符串，就不要再考虑深复制问题了。也就是说，动态内存分配和深复制应该放在一个适当题了。也就是说，动态内存分配和深复制应该放在一个适当的层面上，一个更单纯的类定义中，如的层面上，一个更单纯的类定义中，如string类。在使用中，类。在使用中，把它作为一个成员对象，就像使用把它作为一个成员对象，就像使用string类对象那样。类对象那样。7.1.3浅复制与深复制浅复制与深复制探讨：探讨：最后进一步讨论类的封装。封装的更高境界最后进一步讨论类的封装
28、。封装的更高境界是在该类对象中一切都是完备的、自给自足的，不是在该类对象中一切都是完备的、自给自足的，不仅有数据和对数据的操作，还包括资源的动态安排仅有数据和对数据的操作，还包括资源的动态安排和释放。在需要时可以无条件地安全使用。标准和释放。在需要时可以无条件地安全使用。标准string类模板就是典型的例子。这样的类对象，作类模板就是典型的例子。这样的类对象，作为另一个类的成员对象使用时，就不会出任何问题。为另一个类的成员对象使用时，就不会出任何问题。这表明这表明聚合实现了完善的封装聚合实现了完善的封装。7.2 链表与链表的基本操作链表与链表的基本操作 线性表线性表是最简单，最常用的一种数据结
29、构。线性表的是最简单，最常用的一种数据结构。线性表的逻辑结构是逻辑结构是n个数据元素的有限序列（个数据元素的有限序列（a1,a2,an）。而）。而线性表的线性表的物理结构物理结构包括：顺序表，包括：顺序表，链表链表。7.2.1 单链表基本算法单链表基本算法 7.2.3 双向链表双向链表(选读选读)7.2.2单链表类型模板单链表类型模板 7.2.1 单链表基本算法单链表基本算法单链表单链表（Singly Linked list）：）：每个数据元素占用一个节点（每个数据元素占用一个节点（Node）。一个节点包含两）。一个节点包含两个域，一个域存放数据元素个域，一个域存放数据元素info，其数据类型
30、由应用问题决，其数据类型由应用问题决定；另一个存放指向该链表中下一个节点的指针定；另一个存放指向该链表中下一个节点的指针link。节点定义如下：节点定义如下：typedef int Datatype;/数据为整型数据为整型struct node Datatype info;node*link;在在C/C+中允许结构（或对象）成员是中允许结构（或对象）成员是结构自身的指针类型结构自身的指针类型，通过指针引用自身这种类型的结构。通过指针引用自身这种类型的结构。但结构成员决不能是结但结构成员决不能是结构自身类型构自身类型，即结构不能自己定义自己，这会导致一个无穷，即结构不能自己定义自己，这会导致一个
31、无穷递归的定义。递归的定义。7.2.1 单链表基本算法单链表基本算法单链表的第一个结点的地址可通过链表的表头指针单链表的第一个结点的地址可通过链表的表头指针head找到，找到，head在使用中千万不可丢失，否则链表整个丢失，内在使用中千万不可丢失，否则链表整个丢失，内存也发生泄漏。存也发生泄漏。infon-1 info2 info1 info0 head图图7.3 单链表结构单链表结构 单链表的插入与删除：单链表的插入与删除：只要改变链中结点指针的值，无需移动表中的元素，只要改变链中结点指针的值，无需移动表中的元素，就能实现插入和删除操作。就能实现插入和删除操作。插入算法有插入算法有三种三种情
32、况，我们希望在单链表中包含数据情况，我们希望在单链表中包含数据infoi的结点之前插入一个新元素，则的结点之前插入一个新元素，则infoi可在第一个结点，可在第一个结点，或在中间结点，如未找到，则把新结点插在链尾结点之后。或在中间结点，如未找到，则把新结点插在链尾结点之后。7.2.1 单链表基本算法单链表基本算法newnodeinfoxinfo0info1headhead插在链首：插在链首：首先新结点的首先新结点的link指针指向指针指向info0所在结点，然后，所在结点，然后，head指向指向新结点。即：新结点。即：newnodelink=head；/注意：链表操作次序非常重要注意：链表操作
33、次序非常重要head=newnode；7.2.1 单链表基本算法单链表基本算法infoxinfoi-1infoipnewnode插在中间：插在中间：首先用工作指针首先用工作指针p找到指定结点，而让指针找到指定结点，而让指针q指向紧跟其后的结指向紧跟其后的结点，令点，令infoi-1所在结点的所在结点的link指针指向新结点，而后让新结点指针指向新结点，而后让新结点的的link指向指向infoi所在结点。即：所在结点。即：newnodelink=p；/或或newnodelink=qlink；可用于插入某结点之后；可用于插入某结点之后qlink=newnode；7.2.1 单链表基本算法单链表基本
34、算法infoinfox x newnodepinfoinfon-1n-1 插在队尾：插在队尾：只要工作指针只要工作指针p找到队尾，即可链在其后：找到队尾，即可链在其后：plink=newnode；newnode=NULL;7.2.1 单链表基本算法单链表基本算法带表头结构的链表：带表头结构的链表：研究以上算法，插在链表第一个结点之前与其他结点之前的研究以上算法，插在链表第一个结点之前与其他结点之前的算法有所不同。要使算法中没有特殊者，可以给每一个链表算法有所不同。要使算法中没有特殊者，可以给每一个链表加上一个加上一个表头结点表头结点，如下图所示。，如下图所示。空表如下：空表如下：headinf
35、o0Infon-1info1head 下面分别介绍下面分别介绍带表头结构带表头结构的链表的生成链表算法、链表查的链表的生成链表算法、链表查找算法、插入一个结点的算法和删除一个结点的算法。找算法、插入一个结点的算法和删除一个结点的算法。7.2.1 单链表基本算法单链表基本算法headtailpinfo1tailpinfo0tail1.1.向后生成链表算法：向后生成链表算法：node*createdown()Datatype data;Node*head,*tail,*p;head=new node;/建立链表头结点建立链表头结点 tail=head;while(cindata)/回车结束回车结束
36、 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;/建立头结点建立头结点
37、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
38、;return p;/p为为NULL则未找到则未找到返回值为指针返回值为指针p，指向链表中找到的结点。，指向链表中找到的结点。4.4.在单链表的在单链表的p p节点后插入节点后插入：注意只有一种情况。注意只有一种情况。void insert(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;/如果要把该
39、节点移入另一个链中，则可将如果要把该节点移入另一个链中，则可将q返回。返回。7.2.2 单链表类型模板单链表类型模板【例【例7.5_h】单链表类模板单链表类模板。定义结点类：定义结点类：templateclass List;templateclass Node T info;/数据域数据域 Node*link;/指针域，注意结点类格式，尖括号中是参数名表，类模板实例化为类指针域，注意结点类格式，尖括号中是参数名表，类模板实例化为类public:Node();/生成头结点的构造函数生成头结点的构造函数 Node(const T&data);/生成一般结点的构造函数生成一般结点的构造函数 void
40、 InsertAfter(Node*p);/在当前结点后插入一个结点在当前结点后插入一个结点 Node*RemoveAfter();/删除当前结点的后继结点删除当前结点的后继结点 friend class List;/以以List为友元类，为友元类，List可直接访问可直接访问Node的私有函数的私有函数;定义链表类定义链表类:templateclass List Node*head,*tail;/链表头指针和尾指针链表头指针和尾指针public:List();/构造函数，生成头结点构造函数，生成头结点(空链表空链表)List();/析构函数析构函数 void MakeEmpty();/清空链
41、表，只余表头结点清空链表，只余表头结点 Node*Find(T data);/搜索数据域与搜索数据域与data相同的结点，返回该结点的地址相同的结点，返回该结点的地址 int Length();/计算单链表长度计算单链表长度 void PrintList();/打印链表的数据域打印链表的数据域 void InsertFront(Node*p);/可用来向前生成链表可用来向前生成链表 void InsertRear(Node*p);/可用来向后生成链表可用来向后生成链表 void InsertOrder(Node*p);/按升序生成链表按升序生成链表 Node*CreatNode(T data)
42、;/创建结点创建结点(孤立结点孤立结点)Node*DeleteNode(Node*p);/删除指定结点删除指定结点7.2.2 单链表类型模板单链表类型模板7.2.2 单链表类型模板单链表类型模板【例【例7.57.5】由键盘输入】由键盘输入1616个整数，以这些整数作为结点数据，个整数，以这些整数作为结点数据，生成两个链表，一个向前生成，一个向后生成，输出两个生成两个链表，一个向前生成，一个向后生成，输出两个表。然后给出一个整数在一个链表中查找，找到后删除它，表。然后给出一个整数在一个链表中查找，找到后删除它，再输出该表。清空该表，再按升序生成链表并输出。再输出该表。清空该表，再按升序生成链表并
43、输出。在本例中程序只需调用类模板中的成员函数就可以完成所在本例中程序只需调用类模板中的成员函数就可以完成所有链表操作。有链表操作。【例【例7.67.6】以学生类作为链表的数据类，完成学生档案的管】以学生类作为链表的数据类，完成学生档案的管理。理。7.2.2 单链表类型模板单链表类型模板讨论复制构造函数：讨论复制构造函数：在本例中没有给出在本例中没有给出Node类的复制构造函数，并非可以使用默认类的复制构造函数，并非可以使用默认的复制构造函数，而是避开了所有使用它的情况，本例中函数的参数的复制构造函数，而是避开了所有使用它的情况，本例中函数的参数和返回值仅使用指向和返回值仅使用指向Node的指针
44、，类定义中也没有用复制方式初始的指针，类定义中也没有用复制方式初始化。化。定义复制构造函数与类的实际意义和使用方式有关，并非只是深定义复制构造函数与类的实际意义和使用方式有关，并非只是深复制和浅复制的问题复制和浅复制的问题。通常对通常对Node类复制的结果应是一个孤立结点：类复制的结果应是一个孤立结点：template Node:Node(Node&node)info=node.data;link=NULL;link域值为域值为NULL。该函数与。该函数与Node的有参构造函数功能基本相同。考的有参构造函数功能基本相同。考虑到函数的参数和返回值仅使用指向虑到函数的参数和返回值仅使用指向Node
45、的指针，定义复制构造函的指针，定义复制构造函数已经没有实际意义数已经没有实际意义 单链表的复制构造函数和复制运算符是一个复杂的算法，与前文单链表的复制构造函数和复制运算符是一个复杂的算法，与前文所编的复制构造函数和复制运算符构造相去甚远了。所编的复制构造函数和复制运算符构造相去甚远了。7.2.3 双向链表（选读）双向链表（选读）双向链表引入：双向链表引入：考虑单链表只能找后继。如要找前驱，必须从表头开始搜考虑单链表只能找后继。如要找前驱，必须从表头开始搜索。为了克服这一缺点，可采用索。为了克服这一缺点，可采用双向链表双向链表（Double Linked Double Linked List)L
46、ist)。双向链表的。双向链表的结点有三个域结点有三个域：左链接指针左链接指针（llink)llink)，数据域（数据域（info)info)，右链接指针域右链接指针域(rlink)(rlink)。双向链表经常采。双向链表经常采用用带头结点的循环链表方式带头结点的循环链表方式。info0 infon-1.info1head(a)非空表非空表head(b)空表空表7.2.3 双向链表（选读）双向链表（选读）双向链表的访问：双向链表的访问：假设指针假设指针p p指向双向循环链表的某一个结点，那么，指向双向循环链表的某一个结点，那么，p-llinkp-llink指示指示P P所指结点的所指结点的前驱
47、结点前驱结点，p-rlinkp-rlink指示指示后继结点。后继结点。p-p-llink-rlinkllink-rlink指示本结点的前驱结点的后继结点，即本结点，指示本结点的前驱结点的后继结点，即本结点，间接访问符间接访问符-可以连续使用可以连续使用。pllink rlinkrlinkllink rlink前驱结点前驱结点 llink 本结点本结点 后继结点后继结点 间接访问符的使用间接访问符的使用【例【例7.77.7】双向链表类模板和结点类模板。】双向链表类模板和结点类模板。7.3 栈与队列的基本操作及其应用栈与队列的基本操作及其应用 栈和队都是特殊的线性表，限制存取位置的线性结构，可以由
48、顺序表实现，也可以由链表实现。7.3.1 栈栈 7.3.3队列队列 7.3.2 栈的应用（选读）栈的应用（选读）7.3.1 栈栈栈的基本概念：栈的基本概念：栈定义为只允许在表的一端进行插入和删除的线性表栈定义为只允许在表的一端进行插入和删除的线性表。允许进行插入和删除的一端叫做允许进行插入和删除的一端叫做栈顶栈顶(top)，而另一端叫，而另一端叫栈栈底底(bottom)。栈中没有任何元素时，称为空栈。栈中没有任何元素时，称为空栈。进栈时最先进栈的在最下面，最后的在最上面，后来进栈时最先进栈的在最下面，最后的在最上面，后来居上。而出栈时顺序相反，最后进栈的最先出栈，而最先居上。而出栈时顺序相反，
49、最后进栈的最先出栈，而最先进栈的进栈的a0最后出栈。所以栈又称作最后出栈。所以栈又称作后进先出（后进先出（LIFO：Last In First Out）的线性表）的线性表。栈可以用顺序表实现，称栈可以用顺序表实现，称顺序顺序栈；也可以用链表实现，栈；也可以用链表实现，称称链栈链栈。7.3.1 栈栈栈的基本操作：栈的基本操作：参见下图，设给定栈参见下图，设给定栈s=(a0，a1，an-1)，称，称a0为栈为栈底，底，an-1为栈顶。进栈时最先进栈的为栈顶。进栈时最先进栈的a0在最下面，在最下面，an-1在最在最上面。而出栈时顺序相反，最后进栈的上面。而出栈时顺序相反，最后进栈的an-1最先出栈，
50、而最最先出栈，而最先进栈的先进栈的a0最后出栈。最后出栈。a0an-2a1an-1bottom进栈进栈toptoptoptoptop出栈出栈图示为顺序栈。其中栈图示为顺序栈。其中栈底底bottom是指向栈数据是指向栈数据区的下一单元，这样判区的下一单元，这样判断是否为空栈会更方便，断是否为空栈会更方便，只需只需top与与bottom相同相同就是空栈。通常只有栈就是空栈。通常只有栈顶与操作有关。顶与操作有关。7.3.1 栈栈templateclass Stack int top;/栈顶指针（下标）栈顶指针（下标）T*elements;/动态建立的元素动态建立的元素 int maxSize;/栈最
