模版——容器，迭代器

题：

试用多态实现线性表（队列、串、堆栈），要求具备线性表的基本操作：插入、删除、测长等。【美国著名软件企业GS公司2007年11月面试题】

解析：

队列、串、堆栈都可以实现push、pop、测长等操作。现在要求用多态去实现，就要建立一个线性表的共性模版，来实现以上的功能。

答案：程序源代码与解释如下

 // P101_example2.cpp : Defines the entry point for the console application.  
//  
 
#include "stdafx.h"  
#include <iostream>  
 
template <typename T> 
struct tcontainer 
{ 
    virtual void push(const T&) = 0;    //插入  
    virtual void pop() = 0; //删除  
    virtual const T& begin() = 0;   //  
    virtual const T& end() = 0; //  
    virtual size_t size() = 0;  //返回长度  
}; 
 
template <typename T> 
struct tvector : public tcontainer<T> 
{ 
    static const size_t _step = 100;    //一次增加容量的大小  
private: 
    size_t _size;   //实际元素的个数  
    size_t _cap;    //已分配的容量  
    T* buf; //首地址  
public: 
    tvector() 
    { 
        _size = 0;  //初始化容器实际大小  
        _cap = _step;   //初始化容器容量的大小为_step  
        buf = 0;    //首地址需要动态分配内存  
        re_capacity(_cap);  //此时buf为空，即要设置buf初始值，配了100个元素的空间  
    } 
    ~tvector() 
    { 
        free(buf);  //释放内存  
    } 
    void re_capacity(size_t s)  //调整容量  
    { 
        if(!buf)    //buf初始为空  
        { 
            buf = (T*)malloc(sizeof(T)*s); 
        } 
        else 
            buf = (T*)realloc(buf,sizeof(T)*s); //在buf基础上调整容量  
    } 
    virtual void push(const T& v) 
    { 
        if(_size >= _cap)    //超过容量  
            re_capacity(_cap += _step); 
        buf[_size++] = v; 
    } 
    virtual void pop()  //删除最后一个元素  
    { 
        if(_size) 
            _size--; 
    } 
    virtual const T& begin()    //返回第一个元素  
    { 
        return buf[0]; 
    } 
    virtual const T& end()  //返回最后一个元素  
    { 
        if(_size) 
            return buf[_size-1]; 
    } 
    virtual size_t size()   //返回容量的大小  
    { 
        return _size; 
    } 
    const T& operator[](size_t i)   //取第i个元素  
    { 
        if(i >= 0 && i < _size) 
            return buf[i]; 
    } 
}; 
int _tmain(int argc, _TCHAR* argv[]) 
{ 
    tvector<int> v; 
    for(int i = 0; i < 1000; ++i) 
    { 
        v.push(i); 
    } 
    for(int i = 0; i < 1000; ++i) 
    { 
        std::cout<<v[i]<<std::endl; 
    } 
    return 0; 
} 

// P101_example2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

template <typename T>
struct tcontainer
{
 virtual void push(const T&) = 0; //插入
 virtual void pop() = 0; //删除
 virtual const T& begin() = 0; //
 virtual const T& end() = 0; //
 virtual size_t size() = 0; //返回长度
};

template <typename T>
struct tvector : public tcontainer<T>
{
 static const size_t _step = 100; //一次增加容量的大小
private:
 size_t _size; //实际元素的个数
 size_t _cap; //已分配的容量
 T* buf; //首地址
public:
 tvector()
 {
  _size = 0; //初始化容器实际大小
  _cap = _step; //初始化容器容量的大小为_step
  buf = 0; //首地址需要动态分配内存
  re_capacity(_cap); //此时buf为空，即要设置buf初始值，配了100个元素的空间
 }
 ~tvector()
 {
  free(buf); //释放内存
 }
 void re_capacity(size_t s) //调整容量
 {
  if(!buf) //buf初始为空
  {
   buf = (T*)malloc(sizeof(T)*s);
  }
  else
   buf = (T*)realloc(buf,sizeof(T)*s); //在buf基础上调整容量
 }
 virtual void push(const T& v)
 {
  if(_size >= _cap) //超过容量
   re_capacity(_cap += _step);
  buf[_size++] = v;
 }
 virtual void pop() //删除最后一个元素
 {
  if(_size)
   _size--;
 }
 virtual const T& begin() //返回第一个元素
 {
  return buf[0];
 }
 virtual const T& end() //返回最后一个元素
 {
  if(_size)
   return buf[_size-1];
 }
 virtual size_t size() //返回容量的大小
 {
  return _size;
 }
 const T& operator[](size_t i) //取第i个元素
 {
  if(i >= 0 && i < _size)
   return buf[i];
 }
};
int _tmain(int argc, _TCHAR* argv[])
{
 tvector<int> v;
 for(int i = 0; i < 1000; ++i)
 {
  v.push(i);
 }
 for(int i = 0; i < 1000; ++i)
 {
  std::cout<<v[i]<<std::endl;
 }
 return 0;
}

补充：软件开发 , C++ ,