8/2/2024数据结构与程序设计14.3 Linked Stack with safeguardsnDestructor 析构函数nProblem?for (int i = 0; i 1000000; i+) Stack small;small.push(some data);8/2/2024数据结构与程序设计24.3.1 析构函数nA destructor is a special method in a class that is automatically executed on objects of the class immediately before they go out of scope.nThe client does not need to call a destructor explicitly and does not even need to know it is present. Destructors are often used to delete dynamically allocated objects that would otherwise become garbage.8/2/2024数据结构与程序设计34.3.1 析构函数nThe destructor must be declared as a class method without return type and without parameters. Its name is given by adding a to the corresponding class name. Hence, the prototype for a Stack destructor is:nStack : Stack( );8/2/2024数据结构与程序设计44.3.1 析构函数n析构函数的实现析构函数的实现Stack : Stack( ) / Destructor/* Post: The Stack is cleared. */while (!empty( )pop( );8/2/2024数据结构与程序设计54.3.2 Overloading the assignment OperatornProblem?Stack outer_stack;for (int i = 0; i entry); while (original_node-next != NULL) original_node = original_node-next; new_copy-next = new Node (original_node-entry); new_copy = new_copy-next; top_node = new_top; / and replace them with new entries.8/2/2024数据结构与程序设计11操作符重载P134 !void Stack:operator = (const Stack &original) /*Post: The Stack is reset as a copy of Stack original.*/ if(this=&original)return; while (!empty() / Clean out old Stack entries pop(); Node *new_top, *new_copy, *original_node = original.top_node; if (original_node = NULL) new_top =NULL; else / Duplicate the linked nodes new_copy = new_top = new Node (original_node-entry); while (original_node-next != NULL) original_node = original_node-next; new_copy-next = new Node (original_node-entry); new_copy = new_copy-next; top_node = new_top; / and replace them with new entries.8/2/2024数据结构与程序设计124.3.3 The Copy Constructor P135nProblem void destroy_the_stack (Stack copy) /在此调用在此调用copy的析构函数的析构函数int main( )Stack vital_data;destroy_the_stack(vital_data);/在此调用在此调用vital_data的析构函数的析构函数/结果结果vital_data中的栈空间被两次释放中的栈空间被两次释放8/2/2024数据结构与程序设计13解决方法，拷贝构造函数nIf we include a copy constructor as a member of our Stack class, our copy constructor will be invoked whenever the compiler needs to copy Stack objects. n两种情况下拷贝构造函数被自动调用：n（1）在参数传递时，在上例中，实参vital_data向形参copy传值时，拷贝构造函数被调用。n（2）在用已有的对象定义新的对象时，拷贝构造函数被调用。nStack s1;nStack s2 = s1; /此时将自动调用拷贝构造函数nStack *s3 = new stack(s1); /此时将自动调用拷贝构造函数8/2/2024数据结构与程序设计14拷贝构造函数的定义nFor any class, a standard way to declare a copy constructor is as a constructor with one argument that is declared as a constant reference to an object of the class.nHence, a Stack copy constructor would normally have thenfollowing prototype:nStack : Stack(const Stack &original);8/2/2024数据结构与程序设计15拷贝构造函数的实现n1. Deal with the case of copying an empty Stack.n2. Copy the first node.n3. Run a loop to copy all of the other nodes.8/2/2024数据结构与程序设计16Copy Constructor ? P136Stack:Stack (const Stack &original) / copy constructor/*Post: The Stack is initialized as a copy of Stack original.*/ Node *new_copy, *original_node = original.GetTop(); if (original_node = NULL) top_node = NULL; else / Duplicate the linked nodes. top_node = new_copy = new Node(original_node-entry); while (original_node-next != 0) original_node = original_node-next; new_copy-next = new Node(original_node-entry); new_copy = new_copy-next; 8/2/2024数据结构与程序设计17noriginal_node top_node new_copy 8/2/2024数据结构与程序设计18The ExtStackn下面通过继承给出Linked_stack的完整实现。8/2/2024数据结构与程序设计19类的继承ntemplatenstruct Node n/ data membersn Node_entry entry;n Node *next;n/ constructorsn Node();n Node(Node_entry item, Node *add_on = 0);n;8/2/2024数据结构与程序设计20类的继承ntemplatenclass Stacknpublic:n/ Standard Stack methodsn Stack();n bool empty() const;n Error_code push(const Node_entry &item);n Error_code pop();n Error_code top(Node_entry &item) const;n/ New method add heren Node *GetTop() const;n/ Safety features for linked structuresn Stack();nprotected:n Node *top_node;n;8/2/2024数据结构与程序设计21类的继承ntemplatenclass StackExt: public Stacknpublic:n StackExt();n StackExt(const Stack &original);n void operator =(const Stack &original);n StackExt();n;8/2/2024数据结构与程序设计22关于继承（1）1. 派生类的定义class ： private: ;public: ;protected: ;复习复习8/2/2024数据结构与程序设计23关于继承（2）的一般格式为： ，. ， 而又可为 private public protected复习复习8/2/2024数据结构与程序设计24nclass A: public C .;nclass A: protected C .;nclass A: private C .;public: int x;potected:int yprivate:int z; C.A 1. public1. public派生方式：派生方式：使基类的公有成员和保护成员在派生类中仍然是公使基类的公有成员和保护成员在派生类中仍然是公有成员和保护成员，而基类的私有成员不可在派生类中被存取。有成员和保护成员，而基类的私有成员不可在派生类中被存取。2. protected2. protected派生方式：派生方式：使基类的公有成员和保护成员在派生类中都变为使基类的公有成员和保护成员在派生类中都变为保护成员，而基类的私有成员不可在派生类中被存取。保护成员，而基类的私有成员不可在派生类中被存取。3. private3. private派生方式：派生方式：使基类的公有成员和保护成员在派生类中都变为私使基类的公有成员和保护成员在派生类中都变为私有成员，而基类的私有成员不可在派生类中被存取。有成员，而基类的私有成员不可在派生类中被存取。 复习复习8/2/2024数据结构与程序设计25关于继承（2）复习复习8/2/2024数据结构与程序设计26关于继承（3）n派生类中可出现四种成员： 1) 不可访问的成员 - 基类的private私有成员被继承过来后，这些成员在派生类中是不可访问的。 2) 私有成员 - 包括在派生类中新增加的private私有成员以及从基类私有继承过来的某些成员。这些成员在派生类中是可以访问的。 3) 保护成员 - 包括在派生类中新增加的potected保护成员以及从基类继承过来的某些成员。这些成员在派生类中是可以访问的。 4) 公有成员 - 包括在派生类中新增加的public公有成员以及从基类公有继承过来的基类的public成员。这些成员不仅在派生类中可以访问，而且在建立派生类对象的模块中，也可以通过对象来访问它们。 复习复习8/2/2024数据结构与程序设计27派生类构造和析构次序n构造：基类成员自身n析构：自身成员基类 成员和基类的构造按类中声明的次序，析构反序。复习复习8/2/2024数据结构与程序设计28关于构造函数和析构函数的调用次序n#include iostream.hnclass basenpublic:nbase();nbase();n;复习复习8/2/2024数据结构与程序设计29关于构造函数和析构函数的调用次序n#include base.hnbase:base()ncoutbase construction!endl;nnbase:base()ncoutbase destruction!endl;n复习复习8/2/2024数据结构与程序设计30关于构造函数和析构函数的调用次序n#include base.hnclass self: public basenpublic:nself();nself();n;复习复习8/2/2024数据结构与程序设计31关于构造函数和析构函数的调用次序n#include self.hnself:self()ncoutself construction!endl;nnself:self()ncoutself destruction!endl;n复习复习8/2/2024数据结构与程序设计32关于构造函数和析构函数的调用次序n#include self.hnclass child: public selfnpublic:nchild();nchild();n;复习复习8/2/2024数据结构与程序设计33关于构造函数和析构函数的调用次序n#include child.hnchild:child()ncoutchild construction!endl;nnchild:child()ncoutchild destruction!endl;n复习复习8/2/2024数据结构与程序设计34关于构造函数和析构函数的调用次序n#include child.hnvoid main()nchild c;n复习复习8/2/2024数据结构与程序设计35关于构造函数和析构函数的调用次序Result(目录InheritClass下程序)nbase construction!nself construction!nchild construction!nchild destruction!nself destruction!nbase destruction!复习复习8/2/2024数据结构与程序设计36C+ 基础知识n派生类可以直接访问该类其他对象的protected基类成员，以及该类其他对象的protected和private成员。n派生类可以直接访问其基类中的protected成员，不能直接访问其基类对象中的protected成员。复习复习8/2/2024数据结构与程序设计37C+ 基础知识例程AboutClassnclass Fathernprotected:nint a1;nprivate:nint a2;npublic:nFather();nvoid printFather();nvoid printFather(Father & f);n;复习复习8/2/2024数据结构与程序设计38C+ 基础知识例程AboutClassnFather:Father()na1=1;na2=2;nnvoid Father:printFather()ncouta1 a2;nnvoid Father:printFather(Father & f)ncoutf.a1 f.a2;n/为内部访问，可以访问f中的私有成员复习复习8/2/2024数据结构与程序设计39C+ 基础知识例程AboutClassnclass Child:public Fathernprotected:nint b1;nprivate:nint b2;npublic:nChild();nvoid printChild();n/void printFather(Father & f);nvoid printChild(Child & c);n;复习复习8/2/2024数据结构与程序设计40C+ 基础知识例程AboutClassnChild:Child()nb1=3;nb2=4;nnvoid Child:printChild()ncouta1:a1 ;n/couta2:a2 ;ncoutb1:b1 ;ncoutb2:b2 ;n复习复习8/2/2024数据结构与程序设计41C+ 基础知识例程AboutClassnvoid Child:printChild(Child & c)ncouta1:c.a1 ;n/couta2:c.a2 ;ncoutb1:c.b1 ;ncoutb2:c.b2 ;n/为内部访问，可以访问c中的私有和保护成员复习复习8/2/2024数据结构与程序设计42C+ 基础知识例程AboutClassn/void Child:printFather(Father & f)n/couta1:f.a1 ;n/coutf.a2;n/n/不能访问f中的保护和私有成员，为对象间的访问复习复习8/2/2024数据结构与程序设计43C+ 基础知识例程AboutClassnvoid main()nFather f1,f2;nChild c1,c2;ncoutendlHere is f1.printFather:endl;nf1.printFather();ncoutendlHere is f1.printFather(f2):endl;nf1.printFather(f2);ncoutendlHere is c1.printChild:endl;nc1.printChild();ncoutendlHere is c1.printChild(c2):endl;nc1.printChild(c2);ncoutendlHere is c1.printFather:endl;nc1.printFather();ncoutendlHere is c1.printFather(f1):endl;nc1.printFather(f1);ncoutendl;n /coutf1.a1; coutf1.a2; /外部访问外部访问n /coutc1.a1; coutc1.a2;/外部访问外部访问n /coutc1.b1; coutc1.b2;/外部访问外部访问n复习复习8/2/2024数据结构与程序设计44ResultnHere is f1.printFather:n1 2nHere is f1.printFather(f2):n1 2nHere is c1.printChild:na1:1 b1:3 b2:4nHere is c1.printChild(c2):na1:1 b1:3 b2:4nHere is c1.printFather:n1 2nHere is c1.printFather(f1):n1 2复习复习8/2/2024数据结构与程序设计45C+ 基础知识例程AboutClass2n公有派生和私有派生npublic and private复习复习8/2/2024数据结构与程序设计46C+ 基础知识例程AboutClass2nclass Child:private Fathernprotected:nint b1;nprivate:nint b2;npublic:nChild();nvoid printChild();n/void printFather(Father & f);nvoid printChild(Child & c);n;复习复习8/2/2024数据结构与程序设计47C+ 基础知识例程AboutClass2复习复习8/2/2024数据结构与程序设计48C+ 基础知识例程AboutClass2nclass Grandson:public Childnpublic:nvoid printGrandson();n;nvoid Grandson:printGrandson()n/couta1:a1 ;n/couta2:a2 ;ncoutb1:b1 ;n/coutb2:b2 ;n复习复习8/2/2024数据结构与程序设计49C+ 基础知识例程AboutClass2nvoid main()nFather f1,f2;nChild c1,c2;nGrandson g1;ncoutendlHere is f1.printFather:endl;nf1.printFather();ncoutendlHere is f1.printFather(f2):endl;nf1.printFather(f2);ncoutendlHere is c1.printChild:endl;nc1.printChild();ncoutendlHere is c1.printChild(c2):endl;nc1.printChild(c2);复习复习8/2/2024数据结构与程序设计50C+ 基础知识例程AboutClass2n/coutendlHere is c1.printFather:endl;n/c1.printFather();n/coutendlHere is c1.printFather(f1):endl;n/c1.printFather(f1);ncoutendlHere is g1.printChild():endl;ng1.printChild();ncoutendlHere is g1.printChild(c2):endl;ng1.printChild(c2);ncoutendlHere is g1.printGrandson():endl;ng1.printGrandson();ncoutendl;n复习复习8/2/2024数据结构与程序设计51ResultnHere is f1.printFather:n1 2nHere is f1.printFather(f2):n1 2nHere is c1.printChild:na1:1 b1:3 b2:4nHere is c1.printChild(c2):na1:1 b1:3 b2:4nHere is g1.printChild():na1:1 b1:3 b2:4nHere is g1.printChild(c2):na1:1 b1:3 b2:4nHere is g1.printGrandson():nb1:3复习复习8/2/2024数据结构与程序设计52Copy Constructor ? P136templateStackExt:StackExt(const Stack &original) / copy constructor/*Post: The Stack is initialized as a copy of Stack original.*/ Node *new_copy, *original_node = original.GetTop(); if (original_node = NULL) top_node = NULL; else / Duplicate the linked nodes. top_node = new_copy = new Node(original_node-entry); while (original_node-next != 0) original_node = original_node-next; new_copy-next = new Node(original_node-entry); new_copy = new_copy-next; 8/2/2024数据结构与程序设计53操作符重载=templatevoid StackExt:operator = (const Stack &original) / Overload assignment/*Post: The Stack is reset as a copy of Stack original.*/ Node *new_top, *new_copy, *original_node = original.GetTop(); if (original_node = NULL) new_top =NULL; else / Duplicate the linked nodes new_copy = new_top = new Node(original_node-entry); while (original_node-next != NULL) original_node = original_node-next; new_copy-next = new Node(original_node-entry); new_copy = new_copy-next; while (!empty() / Clean out old Stack entries pop(); top_node = new_top; / and replace them with new entries.8/2/2024数据结构与程序设计54Class StackExt App#includeLinkStackExt.cppvoid main()Stacknumbers;StackExtnumbersExt;int n;double item;coutplease input an integer n followed by n decimal numbers.n;for(int i=0; iitem;numbers.push(item); numbersExt=numbers; /调用被重载的操作符调用被重载的操作符=StackExtnumbersExt2(numbers);/调用调用copy构造函数构造函数 cout endl Result of numbers: endl; 8/2/2024数据结构与程序设计55Class StackExt App while (!numbers.empty() numbers.top(item);cout item ;numbers.pop();cout endl Result of numbersExt: endl; while (!numbersExt.empty() numbersExt.top(item);cout item ;numbersExt.pop();cout endl Result of numbersExt2: endl; while (!numbersExt2.empty() numbersExt2.top(item);cout item ;numbersExt2.pop(); cout top_node;8/2/2024数据结构与程序设计60解决方案二 P134templatevoid StackExt:operator = (const Stack &original) Node *new_top, *new_copy, *original_node = original.GetTop(); if (original_node = NULL) new_top =NULL; else / Duplicate the linked nodes new_copy = new_top = new Node(original_node-entry); while (original_node-next != NULL) original_node = original_node-next; new_copy-next = new Node(original_node-entry); new_copy = new_copy-next; while (!empty() / Clean out old Stack entries pop(); top_node = new_top; / and replace them with new entries.8/2/2024数据结构与程序设计61C+ 基础知识-操作符重载的讨论n未使用new或指针的相同类或结构体的对象间是可以用=进行赋值操作的，但如果对=进行了操作符重载后，则按照重载函数调用。8/2/2024数据结构与程序设计62C+ 基础知识#includeclass Myclassprotected:int a1;private:int a2;public:Myclass();void set(int a1, int a2);/void operator =(const Myclass &original);void print();8/2/2024数据结构与程序设计63C+ 基础知识Myclass:Myclass()a1=1;a2=2;void Myclass:set(int a1, int a2)this-a1=a1;this-a2=a2;/void Myclass:operator =(const Myclass &original)/a1=original.a1 + 100;/a2=original.a2 + 100;/void Myclass:print()couta1 a2;8/2/2024数据结构与程序设计64C+ 基础知识nvoid main()nMyclass m1;nMyclass m2;ncoutendlHere is m1:endl;nm1.set(3,4);nm1.print();nm2=m1;ncoutendlHere is m2:endl;nm2.print();ncoutendl;n8/2/2024数据结构与程序设计65Result-运算符没有重载nHere is m1:n3 4nHere is m2:n3 48/2/2024数据结构与程序设计66Result-如果=运算符被重载nHere is m1:n3 4nHere is m2:n103 1048/2/2024数据结构与程序设计67C+ 基础知识n目录Equals下例程8/2/2024数据结构与程序设计68C+ 基础知识n使用了new或指针的相同类或结构体的对象间是不可以用=进行赋值操作的，必须对=进行了操作符重载后，才能赋值。否则两个类的指针指向相同的内存地址，出现dangling pointer。nBOOK P1338/2/2024数据结构与程序设计69C+ 基础知识n目录Equals2下例程nSafe Link Stack的实现。8/2/2024数据结构与程序设计70作业讲解nP91 E4ntemplatenError_code MyQueue:serve()n if(count=0) return underflow;n count-;n for(int i=0;icount;i+)entryi=entryi+1;n rear-;n return success;n8/2/2024数据结构与程序设计71作业讲解Conversion下例程可以对2，4，8进制进行转换，不能对16进制转换。如何改进成可以对16进制转换的例程ConversionAll.8/2/2024数据结构与程序设计72作业讲解nvoid main()nn int n, r, item;n char itemchar;n stack numbers; / declares and initializes a stack of numbersn cout 输入要转化的十进制数输入要转化的十进制数N： n;n cout 输入要转化的进制数输入要转化的进制数r： r;n while(n)n item=n%r;n if (item10) itemchar=item+1-1; / 1-1=0n else itemchar=item+A-10;n numbers.push(itemchar);n n=n/r;n n while (!numbers.empty() n cout numbers.top() ;n numbers.pop();n n cout next = new_rear;n rear = new_rear;n n return success;n8/2/2024数据结构与程序设计78Linked Queues-Queue front rear new_rear.8/2/2024数据结构与程序设计79Linked Queues-Queue nError_code Queue:serve()n/*nPost: The front of the Queue is removed. If the Queuen is empty, return an Error_code of underflow.n*/nn if (front =0) return underflow;n Node *old_front = front;n front = old_front-next;n if (front = 0) rear = 0; /处理队列只剩下一个元素时，出处理队列只剩下一个元素时，出队的情况队的情况n delete old_front;n return success;n8/2/2024数据结构与程序设计80Linked Queues-Queue front old_front rear .8/2/2024数据结构与程序设计81Linked Queues-Extended_queuenclass Extended_queue: public Queue npublic:n int size() const;n void clear();n Error_code serve_and_retrieve(Queue_entry &item);n;8/2/2024数据结构与程序设计82Linked Queues-Extended_queueint Extended_queue:size() const/*Post: Return the number of entries in the Extended_queue.*/ Node *p = front; int count = 0; while (p !=0) p = p-next; count+; return count;8/2/2024数据结构与程序设计83Linked Queues-Mainnvoid main()nQueue que1, que2;nExtended_queue extque1;nint n;nchar item;ncoutplease input a integer n followed by n charsn;nfor(int i=0;iitem; /字符队列字符队列n que1.append(item);nn 8/2/2024数据结构与程序设计84Linked Queues-Mainn que2=que1;ncoutendlPrint Que1:endl;n while(!que1.empty()nque1.retrieve(item);ncoutitem ;nque1.serve();nncoutendlPrint Que2:endl;n while(!que2.empty()nque2.retrieve(item);ncoutitem ;nque2.serve();n8/2/2024数据结构与程序设计85Linked Queues-Mainncoutendln please input another integer n followed by n charsn;nfor(i=0;iitem;/整数队列整数队列n extque1.append(item);nncoutendlextque1_size=extque1.size()endl;ncoutendlPrint extque1:endl;n while(!extque1.empty()n extque1.serve_and_retrieve(item);n coutitem ;nncoutendl;n8/2/2024数据结构与程序设计86Resultnplease input a integer n followed by n charsn3na b cnPrint Que1:na b cnPrint Que2:na b cnplease input another integer n followed by n charsn5n1 2 3 4 5nextque1_size=5nPrint extque1:n1 2 3 4 58/2/2024数据结构与程序设计87Linked Queues 上机练习nP140 E1，E4