数据结构C++(11)

继承和抽象类

1.继承概念：
  基类中定义共同属性，而在派生类中定义虚函数：virtual T 方法() 则构成了抽象类。派生类中建立自己特定的方法来改写抽象类中的一般方法。
   C++中，继承是面向类定义的。派生类(子类)从基类(超类)继承数据和操作。派生类本身又可以使另一个继承层次的基类。
 

2.C++中的继承：
  基类：
    class BaseCL
    { <data and methods> =>
        private: {<Members>}  //只允许BaseCL成员访问
        protected:{<Members>} //允许SubCL和BaseCL的成员访问
        public:{<Members>} //允许所有客户程序访问
    }
  派生类：
    class SubCL:public BaseCL  //public 公有继承、private 私有继承、protected 保护继承
    { <data and methods>
    }
 
  当定义一个派生对象时，先执行基类的构造函数，然后再执行派生类的构造函数。
  若基类构造函数需要参数，则派生类构造函数必须显式调用此基类构造函数并传递所需参数（即将基类构造函数的名字和参数放到派生类构造函数的参数初始化列表中），但如果基类具有默认构造函数并设定了默认值，则派生类无需显式执行默认构造函数，最好进行显式调用。
   如基类构造函数：BaseCL(int n,char ch);
   派生类构造函数：SubCL(int n,char ch,int sz); //是基类构造函数的超集
   派生类构造函数调用： SubCL::SubCL(int n,char ch,int sz):BaseCL(n,ch),data(sz){}
  
【注意】在继承链中，析构函数调用的顺序则与构造函数正好相反：先调用派生类析构函数，再是成员对象的析构函数，最后调用基类的析构函数。如果派生类没有析构函数但基类有，则自动生成派生类的析构函数，此析构函数撤销派生类的成员并执行基类析构函数。

 继承中命名冲突调用问题：
    class BaseCL
     {  public:
            ...
            void F(void);
            void G(int x);
            ...
     };
    class SubCL:class BaseCL
     {  public:
            ...
            void F(void);
            void G(int x);
            ...
     };

   具体实现方法调用:
    void SubCL::G(float x) //派生类的G方法
    {  ...
       BaseCL::G(x);  //访问基类中的G方法使用BaseCL::
       ...
    };

    SubCL subObj;
    subObj.F();
    subObj.BaseCL::F(); //派生对象则使用BaseCL::访问基类方法

【注意】构造函数不能被继承，因此不能声明虚方法。如果基类构造函数需要参数，则派生类必须有自己的构造函数以调用基类的构造函数。友元关系(friend)不被继承。

3.多态性和虚函数
 C++用“动态绑定(dynamic binding)”和“虚成员函数”技术支持多态性。
 动态绑定：允许系统中的不同对象对同一消息作出特定于其类型的响应。在运行时动态确定。
 虚成员函数：在基类中声明虚成员(virtural)函数。
  class BaseCL
  { private: ...
    public:...
          virtual void F(int n);
          virtual int G(long m);
  };
  
  多态性允许那些带基类指针或引用变元的函数在派生类的虚函数新版本中被复用。
  
  虚方法和析构函数：
  当一个类需要分配动态内存时就必须定义类析构函数。如果类被用作基类，则析构函数必须是虚函数。
如果基类的析构函数不是虚函数，则用基类指针指向的派生对象的析构函数将得不到执行。
   class BaseCL
   {  ...
      public:
         BaseCL(...); //申请7个元素的数组
         ~BaseCL(void);//释放空间(非虚函数)
   }
   class SubCL:public BaseCL
   {  ...
      public:
         BaseCL(...);  //申请7个元素的数组
         ~SubCL(void); //释放空间（非虚函数）
   }

 BaseCL *p = new SubCL();
   delete p; //调用基类的析构函数

   由派生类所生成的动态数据将不会被释放。如果基类的析构函数被声明为虚函数，那么派生类的析构函数将被调用。这种情况下也要调用基类的析构函数，但要等到派生类的析构函数被调用之后。
 
   一般来说，如果类被用作继承层次结构中的基类，则一定要使其具有虚析构函数，即使建立一个什么也不做的析构函数。这确保了若派生类有析构函数则它可以被调用。
   virtural BaseCL::~BaseCL(void) {}

 4.抽象基类

class BaseCL
{  ...
 public:
   virtual void F(void)=0;
   virtual void G(void)=0;
};
class SubCL:public BaseCL
{ public:
    virtual void F(void); //由于未定义G，无法定义SubCL对象。该类任然为抽象基类，可供其它定义了函数G的派生类继承
};

SubCL sub; //无法编译，出错，不可以建立抽象基SubCL的对象实例
 
【注意】基类中的其他方法被声明为纯虚方法，在派生类中它们必须被重写。

5.迭代算子：

实际上它是假定有一些外部过程可以遍历表并维护表当前位置的记录。
对于数组或SeqList对象L，可以用循环和位置索引遍历表。对于Seqlist对象L，方法GetData用来访问数

据值：
for(pos=0;pos<ListSize();pos++)
{ cout<<L.GetData(pos)<<" ";}

对于二叉树、哈希表及词典，表遍历更复杂。表遍历问题解决方法：建立一个迭代算子类(iterator)，其

任务是对数据结构，如链表或树中的元素进行遍历。迭代算子被初始化时，当前指针指向表头位置(头、

根等)。迭代算子提供了允许我们在表中移动的方法Next()和EndOfList()。

Iterator类说明：
template <class T>
class Iterator
{ protected:
     int iterationComplete; //是否已到表尾标志，由派生类维护
  public:
     Iterator(void); //构造函数
     virtual void Next(void)=0;
     virtual void Reset(void)=0;
     virtual T& Data(void)=0; //数据检索/修改方法（访问当前表元素的数据值）
     virtual int EndOfList(void) const;//是否已到表尾
};

Iterator类的实现：
template <class T>
Iterator<T>::Iterator(void):iterationComplete(0){}  //构造函数置iterationComplete为0(false)

(1)表迭代算子派生：SeqListItrator
 SeqListIterator是派生类SeqList的友元函数，它被允许访问SeqList类的私有成员。
 template<class T>
 class SeqListIterator:public Iterator<T>
 { private:
      SeqList<T> *listPtr; //指向供遍历的SeqList指针
      Node<T> *prevPtr,*currPtr; //指向表中上一位置及当前位置的指针
   public: //构造函数
      SeqListIterator(SeqList<T>& lst);
      virtual void Next(void);
      virtual void Reset(void);
      virtual T& Data(void);  //必须定义的数据检索/修改方法
      void SetList(SeqList<T>& lst);
 };

SeqList<int> L;
 SeqListIterator<int> iter(L);
cout<<iter.Data();
iter.Next(); //移往表中下一位置
for(iter.Reset();!iter.EndOfList();iter.Next())
{ cout<<iter.Data()<<" "; }

建立SeqList迭代算子：
template<class T>
//构造函数，初始化基类并设置SeqList指针
SeqListIterator<T>::SeqListIterator(SeqList<T>& lst):Iterator<T>(),listPtr(&lst)
{ iterationComplete = listPtr->llistPtr.listEmpty();//置iterationComplete值
  Reset();//将迭代算子指向表头
}

template<class T>
void SeqListIterator<T>::Reset(void)
{ iterationComplete=listPtr->llist.ListEmpty(); //重置迭代算子状态
  if(listPtr->llist.front==NULL)
   return; //如果表为空，则返回
  prevPtr=NULL; //移动到表的头结点
  currPtr=listPtr->llist.front;
}

template<class T>
void SeqListIterator<T>::SetList(SeqList<T>& lst)
{ listPtr=&lst;
 //将遍历指向新表中的lst数据
  Reset();
}

//返回当前表元素的数据值
template<class T>
T& SeqListIterator<T>::Data(void)
{ if(listPtr->llist.ListEmpty()||currPtr==NULL) //如果表为空或遍历结束，则出错退出
  { cerr<<"Data:invalid reference!"<<endl;
    exit(1);
  }
  return currPtr->data;  //返回当前指针链表的数据
}

template<class T>
void SeqListIterator<T>::Next(void)
{ //若currPtr为NULL，则已到表尾
  if(currPtr==NULL)
   return;
  prevPtr=currPtr;
  currPtr=currPtr->NextNode();
  if(currPtr==NULL) //若已到达表尾，则iterationComplete值置为1
    iterationComplete=1;
}

【实例】统计商店雇员销售商品数量，并打印出雇员识别码和销售的总数量。雇员识别码(idIter)、销售信息(SalesList)、雇员销售商品量记录表(SalesPerson)
 #include<iostream.h>
 #include<fstream.h>
 #include"seqlist2.h"
 struct SalesPerson
 { int idno; //销售员id
   int units; //销售量记录
 };
 int operator==(const SalesPerson &a,const SalesPerson &b) //比较雇员的id号
 { return a.idno=b.idno;
 }
 void PrintTotalSales(SeqList<SalesPerson> & L,int id)
 { SalesPerson salesP={id,0};//定义SalesPerson,初始化其值为0
   SeqListIterator<SalesPerson> iter(L); //定义顺序表迭代算子并用它扫描表
   for(iter.Reset();!iter.EndOfList();iter.Next())
   { if(iter.Data() == salesP)
       salesP.units += (iter.Data()).units; //如果雇员号相同，那么增加其销售量
   }
   cout<< "Sales person"<<salesP.idno <<"Total Units Sold"<< salesP.units<<endl;
 }
 
void main(void)
{  SeqList<SalesPerson> salesList;
   SeqList<int> idList;
   ifstream salesFile; //存放输入数据的文件
   SalesPerson salesp;//存放输入的边路
   salesFile.open("sales.dat",ios::in| ios::nocreate);
   if(!salesFile)
   { cerr<<"File 'sales.dat' not found!";
      exit(1);
   }
   while(!salesFile.eof())
   { salesFile>>salesP.indo>>salesP.units;
     salesList.Insert(salesP); //读入数据将每条“idno-units”的记录插入到链表salesList中
     if(!idList.Find(salesP.idno)
     { idList.Insert(salesP.idno); //如果id没有在idList中找到，将其加入
     }
   }
   //为两个表建立迭代算子
   SeqListIterator<int> idIter(idList);
   SeqListIterator<SalesPerson> salesIter(salesList);
   for(idIter.Reset();!idIter.EndOfList();idIter.Next())
   { PrintTotalSales(salesList,idIter.Data());
   }

}
 
(2)数组迭代算子：ArrayIterator (arriter.h)
  为数组索引建立数组迭代算子。通过将地带算子初始化为从特定元素开始到另一个特定元素结束，应用程序中就可以不再用索引了(归并有序归并段)。多个迭代算子甚至可以同时遍历同一数组。
 template<class T>
 class ArrayIterator:public Iterator<T>
 { private:
     int currentIndex;
     int startIndex;
     int finishIndex;
     Array<T> *arr;
   public:
      ArrayItertor(Array<T>& A,int start=0,int finish=-1);//表示客户程序将数组中上一项的索引作为其上界
      virtual void Next(void);
      virtual void Reset(void);
      virtual T& Data(void);
 };

【实例】归并有序归并段

http://s10/middle/4a93cceagc93986f58599&690

  void Copy(ArrayIterator<int>& Source,ArrayIterator<int>& Dest)
  { while(!Source.EndOfList())
    { Dest.Data()=Source.Data();
      Source.Next();
      Dest.Next();
    }
  }
  //将两个归并段归并到数组A中。第一个归并段下标范围：lowIndex~endOfRun-1
  //第二个归并段下标范围:endOfRun~highIndex
  void Merge(Array<int>& A,int lowIndex,int endOfRunIndex，int highIndex)
  { Array<int> Out(A.ListSize()); //输出归并后的数组和输入的数组大小保持相同
    ArrayIterator<int> left(A,lowIndex,endOfRunIndex-1);
    ArrayIterator<int> right(A,endOfRunIndex,highIndex);
    ArrayIterator<int> output(Out); //将排序后的数据送入output
    while(!left.EndOfList()&&!right.EndOfList())
    { if(left.Data()<=right.Data())
      { output.Data()=left.Data();
        left.Next();
      }
      else
      { output.Data()=right.Data();
        right.Next(); 
      }
      output.Next(); //前移output
    }
   
    if(!left.EndOfList())
    {Copy(left,output);}
    else if(!right.EndOfList())
    {Copy(right,output);}
   
    output.Reset(); //重置Out的迭代算子并将Out数据拷回A中
    ArrayIterator<int> final(A); //用于拷贝回A中
    Copy(ouput,final);
 }

6.有序表OrderedList(派生类):
 template<class T>
 class OrderedList:public SeqList<T>
 { public:
      OrderedList(void);
      virtual void Insert(const T& item); //重写insert来得到有序表
  
 }；//除了Insert之外，所有表操作都直接取自SeqList,因为他不影响排序。

重写Insert方法的实现：
template<class T>
void OrderedList<T>::Insert(const T& item)
{ for(llist.Reset();llist.EndOfList();llist.Next())
  { if(item<llist.Data())
      break;
  }
 llist.InsertAt(item);
 size++;
}

【应用】长归并段(过滤预处理数据) 技术
  CharArray:[a k][g][c m t][e n][l][c r s][c][b f]
=>合并为4个归并段
[a g k][c e m n t][c l r s][b c f]
=>15元素过滤成3个5元素的有序归并段
[a c g k m][c e l n t][b c f r s]

 #include<iostream.h>
 #include "ordList.h"
 #include "array.h"
 #include "arriter.h"
 #include "random.h"
 //遍历整数数组并按每行10个整数输出所有表项
 void PrintList(Array<int>& A)
 { ArrayIterator<int> iter(A);
   int count;
   count=1;
   for(iter.Reset();!iter.EndOfList();iter.Next();count++)
   { cout<<iter.Data()<<" "
     if(count==0)
       cout<<endl;
   }
 }
  //从有序表L中删除表项并插入到数组A中，修改指针A中下一个下标的loadIndex值
 void Copy(OrderedList<int> &L,Array<int> &A,int &loadIndex)
 { while(!L.ListEmpty())
   { A[loadIndex++]=L.DeleteFront();
   }
 }
 void main(void)
 { Array<int> A(100);
   OrderedList<int> L; //有序表
   RandomNumber rnd;
   int i,loadIndex=0;
   //生成100个范围在100~999的随机数，用一25元素的有序表进行过滤。表满后，用copy将元素考别到数组A中
   for(i=1;i<=100;i++)
   { L.Insert(rnd.Random(900)+100);
     if(i%==0)
      Copy(L,A,loadIndex);
   }
   PrintList(A); //输出数组A中的最后结果
 }

7.异构表

异构(hetrogeneous)：具有不同类型对象的集合。引入新的程序设计技术来实现异构集合。
 假定表中每个对象都派生自一个公共基类。
异构数组：(举例粉刷3类不同的房屋,5个不同房屋地址)

http://s3/middle/4a93cceagc940af03ae72&690

class House
{ private:
     String id;
  public:
     House(void){id="House";}
     virtual void Paint(void){cout<<id;}
}
class WoodFrameHouse:public House
{ private:
     string id; //木质架构房子id
  public:
     WoodFrameHouse(void):House(){id="Wood Frame";}
     virtual void Paint(void)
     { cout<<"Painting a"<<id<<" ";
       House::Paint();
     }
};
...

  void main(void)
  { House * contractorList[5]; //房屋地址动态表
    RandomNumber rnd;
    for(int i=0;i<5;i++)
    {  switch(rnd.Random(3)) //随机选择房屋类型0,1,2创建对象，并将其地址赋给contractorList
       { case 0: contractorList[i]=new WoodFrameHouse; //粉刷木制房
                 break;
         case 1: contractorList[i]=new StuccoHouse; //粉刷水泥房
                 break;
         case 2: contractorList[i]=new VinylSideHouse; //粉刷乙烯衬边房
                 break;

        }
     }
     for(i=0;i<5;i++)
     { 
        contractorList[i]->paint();
     }

  }

8.异构链表：
  使用多态性技术，指针可以用于执行派生对象中的方法，而不管其类型如何。
#include "graphlib.h"
class NodeShape
{ protected:
     float x,y; //基点坐标
     int fillpat;//填充方式
     NodeShape *next; //指向下一结点的指针
  public:
     NodeShape(float h=0,float v=0,int fill=0);//构造函数
     virtual void Draw(void) const; //虚方法Draw
     //表处理方法
     void InsertAfter(NodeShape *p);
     NodeShape *DeleteAfter(void);
     NodeShape *Next(void);
};

http://s15/middle/4a93cceagc941440c978e&690

NodeShape类的实现：
 NodeShape::NodeShape(float h,float v,in fill):x(h),y(v),fillpat(fill)
 {next=this;} //链表是循环表，因粗初始化一个指向自身的结点
 派生链式几何类：
 class CircleFigure:public NodeShape //圆形类
 { protected:
      float radius; //定义圆的半径
   public:
      CircleFigure(float h,float v,float r,int fill);
      virtual void Draw(void) const;
 };
  CircleFigure::CircleFigure(float h,float v,float r,int fill):NodeShape(h,v,fill),radius(r){}
  void CircleFigure::Draw(void) const
 {NodeShape::Draw(); //设置基类Draw方法的填充模式
  DrawCircle(x,y,radius);
}

NodeShape listHeader,*p;
float x,y,radius,base,height;
p=&listHeader;
for(int i=0;i<4;i++)
{ cout<<"Enter x and y:"
  cin>>x>>y;
  if(i%2==0) //如果i是偶数，那么插入圆形
  { cout<<"Enter the radius for a circle:"
    cin>>radius;
    p->InsertAfter(new Circle(x,y,radius,i));
  }
  else //如果是奇数，则插入直角三角形
  { cout<<"Enter base and height for a right triangle:";
    cin>>base>>height;
    p->InsertAfter(new RightTriangle(x,y,base,height,i));
  }
  p=p->Next(); //p指向刚产生的结点
}

 遍历表和描画对象时“动态绑定”多态性的重要性：
 p=listHeader.Next(); //指针移动指向的每个结点实际指向一个Circle或RightTriangle的对象
 while(p!=&listHeader)
 { p->Draw(); //派生类的Draw方法被执行
   p=p->Next();
 }

================异构表的实现====================
格式：<图形类型> <基点x,y> <图形参数>
图形类型包括：c(circle)、r(rectangle)、t(right triangle)
基点：一对浮点数
图形参数：半径或边长

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include "graphlib.h"
#include "shapelst.h"
void main(void)
{ NodeShape listHeader,*p,*nFig; //定义循环表表头listHeader,当前指针p和图形指针nFig
  char figType; //定义三种图形类型符号
  int pat=0;//默认填充模式：不填充
  float x,y,radius,length,width,tb,th;
  fin.open("figures",ios:in|ios:nocreate);
  if(!fin)
   {cerr<<"Cannot open 'figures'<<endl;"
   exit(1);}
   p=&listHeader; //将p指向表头
   while(!fin.eof())
   { fin>>figType; //读入图形类型和基点
     if(fin.eof()){break;}
     fin>>x>>y;
     switch(figType)
     {case 'c': fin>>radius;
                nFig=new CirecleFigure(x,y,radius,pat);
                p->InsertAfter(nFig);//在头结点后插入nFig->CirecleFigure圆形结点
                break;
      case 'r': fin>>length>>width;
                nFig=new RectangleFigure(x,y,length,width,pat);
                p->InsertAfter(nFig);//在头结点后插入nFig->RectangleFigure矩形结点
                break;
      case 't': fin>>tb>>th;//输入三角形底tb和高th
                nFig=new RightTriangleFigure(x,y,tb,th,pat);
                p->InsertAfter(nFig);//在头结点后插入nFig->CirecleFigure直角三角形结点
                break;
     }
      pat=(pat+1);//填充方式值在12个图形完成以后加1(即换一种填充方式)
      p=p->Next(); //前移指针到表尾

   }
   InitGraphics(); //初始化图形系统

  //从第1个图形开始，遍历表并画出每个图形
   p=listHeader.Next();
   while(p!=&listHeader)
   { p->Draw();
     p=p->Next();
   }
   
   ViewPause(); //暂停下来，观察图形
   ShutdownGraphics();//关闭图形系统
}

=====================================================