单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,应用软件设计,复习,2,：多态性及链表,内存垃圾回收的设计,class,CNewArray,LPBYTE pArray;,public:,CNewArray(,int,size=0),pArray=(size 0)?,new,BYTEsize:NULL;,CNewArray(),if,(pArray),delete,pArray;,operator,LPBYTE(),const,return,pArray;,;,用法：,CNewArray ar(10);,LPBYTE par=(LPBYTE)ar;,自动释放,内存垃圾回收的设计,template,class,CNewClass,TYPE*pClass;,public:,CNewClass(),pClass=,new,TYPE;,CNewClass(),if,(pClass),delete,pClass;,operator,TYPE*(),const,return,pClass;,;,内存垃圾回收的设计,class,CTest,int,a;,public,:,CTest():a(10),CTest(),;,实际调用：,CNewClass ob;,Test*p=(CTest*)ob;,自动释放,1,虚函数,虚函数的目的是告诉编译器，对于指向基类的指针而言，如果它派生类中有同名的函数（被重载），则优先执行派生类中的该函数。,Shape,Draw();,Circle,Draw();,基类指针,Shape,virtual,Draw();,Circle,virtual,Draw();,基类指针,基类指针只能访问基类的函数,基类指针可以访问派生类的函数,3,类型域和,switch,语句,class,Circle,int,DrawCircle();,class,Square,int,DrawSquare();,class,Triangle,int,DrawTriangle();,Circle c;Square s;Triangle t;,switch,(paint),case,0:c.DrawCircle();,break,;,case,1:s.DrawSquare();,break,;,case,2:t.DrawTriangle();,break,;,例,1,链表,用链表记录这些操作,我们希望将这些画图的动作记录下来。,由于各类的数据结构不同，所以只能记录各类对象的指针。,将这些指针记录到一个数组（,Array,）或链表（,List,）中。（下面着重讲链表，数组也一样）,注意：,记录到链表中只能是同一个类的指针！,所以上面这些操作无法记录到一个链表中，于是我们利用,派生类指针可转换成其基类指针,的功能，这样设计这些类。,设计作图类,class,Shape,int,Draw();,/base class,class,Circle:,public,Shape,/derived class,int,Draw();,class,Square:,public,Shape,/derived class,int,Draw();,class,Triangle:,public,Shape,/derived class,int,Draw();,设计作图类,设链表为,List,，里面记录着,Shape,的指针。,class,List,public,:,void operator,+=(Shape*);,Shape*,operator,(,int,index);,private,:,static,Shape*pFirst;,Shape*pNext;,;,问题：基类的指针访问派生类,Circle c;,List+=(Shape*),Square s;,List+=(Shape*),Triangle t;,List+=(Shape*),我们设想，要恢复记录时，只需：,for,(,int,i=0;i Draw();,派生类指针转换成基类指针,只能调用基类的函数,但这是基类的指针,?,用虚函数实现访问！,class,Shape,virtual,int,Draw();,/base class,class,Circle:,public,Shape,/derived class,virtual,int,Draw();,class,Square:,public,Shape,/derived class,virtual,int,Draw();,class,Triangle:,public,Shape,/derived class,virtual,int,Draw();,for,(,int,i=0;i Draw();,虽然是基类指针，但可优先执行派生类的有关函数,静态联编与动态联编,虚函数是为派生类重载基类的函数而设定的。,虚函数的设置导致重载函数指向的不确定性。（所谓虚函数由此得名）,静态联编,static binding,在编译的时候就被确定的虚函数,动态联编,dynamic binding,在运行时才被确定的虚函数,如果,Circle c;c.Draw();,这是静态联编！,如果,Circle c;Shape*ps=,ps-Draw();,这是动态联编！,抽象基类和具体类,抽象类就是不能实例化，只能做基类的类。所以称为,抽象基类。,abstruct base class,抽象类的唯一用途就是为其他类提供合适的基类。,例如前面的例子中的,Shape,，它不是一个具体的形状，只是从,circle,square,triangle,等具体图形中抽象出来的概念。所以应该将其设为抽象类。,class,Shape,virtual,int,Draw()=0;,纯虚函数的声明,只要有一个纯虚函数的类就是抽象基类，纯虚函数必须被派生类实现,！,4,多态性,多态性（,polymorphism),通过继承而相关的不同的类，他们的对象能够对同一个函数调用作出不同的响应。,virtual,Shape:Draw(),Circle:Draw(),Square:Draw(),Triangle:Draw(),for,(,int,i=0;i Draw();,形式相同而实质不同,！,多态性的特性,利用虚函数和多态性，程序员可以处理,普遍性,而让执行环境处理,特殊性,。,多态性提高了可扩展性：处理多态性行为的软件可用与接收消息的对象无关的方式编写。（利用动态联编的特性）,如：,插件技术,抽象类为类层次结构中的各个成员定义接口。,纯虚函数没有实体；,纯虚函数必须在派生类中实现。,尽管不能实例化抽象基类的对象，但却可以声明抽象基类的指针。例：如果,Shape,是抽象基类，,不能：,Shape Ob;,但可以：,Shape*pOb;,多态性特别适合于实现分层的软件系统。,输出代码,Employee*ptr;,/,基类指针,Boss b(“John”,”Smith”,800.00);,ptr=,/,指向派生类对象的基类指针,ptr-print();,/,动态联编,cout,earnings();,/,动态联编,b.print();,/,静态联编,cout,“earned$”Draw();,屏幕管理程序,不需重新编译！,Rectangle:Draw(),new!,5.1,线性表的链接存储,存储结点（,node,）的结构,单向链表的结构,H,双向链表的结构,B,data,p,1,p,2,p,m,a,1,a,i,a,n,a,1,a,i,a,n,5.2,单链表中插入结点（,Insert,）,a,c,b,a,c,b,链表,1),新建一结点,b,2),a,的指针指向,b,；,3),b,的指针指向,c,。,5.3,单链表中删除结点（,Delete,）,a,b,c,a,b,c,b,原链表,1),让,x,的指针指向,z,；,2),删除,y,结点。,单链表的插入：,struct,LNode,ElemType data;,LNode*next;,;,LNode a,c;,cin,a.data c.data;,a.next=,LNode b;,cin,b.data;,/create a new node,a.next=,/point to node b,b.next=,/point to node c,结点的定义,单链表的删除：,struct,LNode,ElemType data;,LNode*next;,;,LNode a,b,c;,cin,a.data b.data c.data;,a.next=,c.next=NULL;,a.next=,/point to node c,delete,b;,/delete node b,结点的定义,5.4,单向链表按顺序插入,new,一个新的结点；,LISTNODEPTR newPtr=new listNode;,设两个指针,LISTNODEPTR previousPtr,和,currentPtr,a,next,b,next,d,next,f,next,previousPtr,currentPtr,NULL,单向链表按顺序插入,3.While,循环，比较,currentPtr-data,与,newPtr-data,的值；每次循环时将,currentPtr,保留在,previousPtr,，而,currentPtr,移动到,next,。,4.,找到位置后修改指针。,previousPtr-nextPtr=newPtr;,newPtr-nextPtr=currentPtr;,a,next,b,next,d,next,f,next,previousPtr,currentPtr,c,next,NULL,5.5,单向链表按顺序删除,设两个指针,LISTNODEPTR previousPtr,和,currentPtr,遍历链表比较,currentPtr-data,的值，找到相等的结点。,a,next,b,next,c,next,d,null,previousPtr,currentPtr,CObList,解析,结点的定义：,struct,CNode,CNode*pNext;,CNode*pPrev;,CObject*data;,;,CObList,遍历,int,n=m_ObArray.GetSize();,for,(,int,i=0;iDraw(pDC);,-,for,(POSITION pos=m_obList.GetHeadPosition();pos!=NULL;),pShape=(CShape*)m_obList.GetNext(pos);,pShape-Draw(pDC);,