Tauruser

Enjoy Every Day
posts - 34, comments - 95, trackbacks - 0, articles - 5
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

算法与数据结构实验(二)

Posted on 2006-03-22 12:18 Tauruser 阅读(688) 评论(2)  编辑 收藏 引用 所属分类: 算法与数据结构

数组空间组织与链表空间组织的堆栈实现


为了增强实现的堆栈通用性,用堆栈实现进行模板化。代码如下:

//////////// //stack.h /////////////// /
////////////////////////////////////////////////

#ifndef stack_h_
#define  stack_h_
#include 
< iostream >
using   namespace  std;

template 
< class  T >   class  stack
{
public :
    
virtual   void  push( const  T  & x) = 0 ;
    
virtual   void  pop() = 0 ;
    
virtual  T Top()  const   =   0 ;
    
virtual   bool  IsEmpty()  const   = 0 ;
    
virtual   bool  IsFull()  const = 0 ;

}
;

#endif
//////////// segstack.cpp ///////////////
///////// 数组组织代码 ////////////////////////


#include 
" stack.h "

template 
< class  T >   class  SegStack:  public  stack < T >
{
public :
    SegStack(
int  mSize);
    
~ SegStack();
    
bool  IsEmpty()  const ;
    
bool  IsFull()  const ;
    
void  push( const  T  & x);
    
void  pop();
    T Top() 
const ;
    
// friend ostream& operator << (ostream& out,const SegStack<T>& seg);
    template  <   class  T >  friend ostream &   operator   <<  (ostream &   out , const  SegStack < T >&  seg); 
    
void  output(ostream &   out const ;

private :
    T 
* s;
    
int  maxSize;
    
int  top;
}
;

template 
< class  T >  SegStack < T > ::SegStack( int  mSize):top( - 1 )
{
    maxSize
= mSize;
    s 
=   new  T[maxSize];

}

template 
< class  T >  SegStack < T > :: ~ SegStack()
{
    delete []s;
}


template 
< class  T >   bool  SegStack < T > ::IsFull()  const
{        
    
return  (top == (maxSize - 1 ));
}


template 
< class  T >   bool  SegStack < T > ::IsEmpty()  const
{
    
return  (top ==- 1 );
}


template 
< class  T >   void  SegStack < T > ::push( const  T  & x)
{
    
if (IsFull())
    
{
        cout
<< " The stack is full " << endl;
    }
else
    
{
        s[
++ top] = x;
    }

}


template 
< class  T >   void  SegStack < T > ::pop()
{
    
if (IsEmpty())
    
{
        cout
<< " The stack is empty " << endl;
    }
else     
    
{
        top
-- ;
    }

}

template 
< class  T >  T SegStack < T > ::Top()  const
{
    
return  s[top];
}


template 
< class  T >   void  SegStack < T > ::output(ostream &   out const
{
    
out << " The stack list is: " ;
    
for ( int  i( 0 );i <= top;i ++ )
        
out << "   " << s[i];
    
// out<<endl;
}


template 
< class  T >  ostream &   operator   <<  (ostream &   out , const  SegStack < T >&  seg)
{
    
out << " The stack list is: " ;
    
for ( int  i( 0 );i <= seg.top;i ++ )
        
out << "   " << seg.s[i];
    
// out<<endl;
    
// seg.output(out);
     return   out ;
}
/////////////// linkstack.cpp ////////////
//////////// //链表实现 ///////////////////// //

#include  " stack.h "

template 
< class  T1 >   struct  Element
{
    T1 content;
    Element
*  next;
}
;
template 
< class  T1 >   class  LinkStack:  public  stack < T1 >
{
public :
    LinkStack();
    
~ LinkStack();
    
bool  IsEmpty()  const ;
    
bool  IsFull()  const ;
    
void  push( const  T1  & x);
    
void  pop();
    T1 Top() 
const ;
    template 
< class  T >  friend ostream &   operator << (ostream &   out const  LinkStack < T1 >&  linkstack);
    
void  output(ostream &   out const ;

private :

    Element
< T1 >*  top;
}
;
template 
< class  T1 >   bool  LinkStack < T1 > ::IsEmpty()  const
{
    
if (top == NULL)
        
return   true ;
    
else
        
return   false ;
}

template 
< class  T1 >   bool  LinkStack < T1 > ::IsFull()  const
{
    
return   false ;
}

template 
< class  T1 >  LinkStack < T1 > ::LinkStack():top(NULL)
{
}

template 
< class  T1 >  LinkStack < T1 > :: ~ LinkStack()
{
    
while (top != NULL)
    
{
        Element
< T1 >*  temp;
        temp
= top;
        top
= top -> next;
        delete temp;
    }

}


template 
< class  T1 >   void  LinkStack < T1 > ::push( const  T1  & x)
{
    Element
< T1 >*  temp = new  Element < T1 > ;
    temp
-> content = x;
    temp
-> next = top;
    top
= temp;
}

template 
< class  T1 >   void  LinkStack < T1 > ::pop()
{
    
if (top != NULL)
    
{
        Element
< T1 >*  temp;
        temp
= top;
        top
= top -> next;
        delete temp;
    }

    
}


template 
< class  T1 >  T1 LinkStack < T1 > ::Top()  const
{
    
return  top -> content;
    
}

template 
< class  T1 >  ostream &   operator << (ostream &   out const  LinkStack < T1 >&  linkstack)
{
    Element
< T1 >*  temp;
    temp
= linkstack.top;

    
out << " The stack list is: " ;
    
while (temp != NULL)
    
{
        
out << temp -> content << '   ' ;
        temp
= temp -> next;
    }


    
return   out ;
}

template 
< class  T1 >   void  LinkStack < T1 > ::output(ostream &   out const
{
    Element
< T1 >*  temp;
    temp
= top;

    
out << " The stack list is: " ;
    
while (temp != NULL)
    
{
        
out << temp -> content << '   ' ;
        temp
= temp -> next;
    }

}

没有写注释,有空再补上吧。

Feedback

# re: 算法与数据结构实验(二)  回复  更多评论   

2006-03-22 17:33 by 任我行
template < class T > class stack
{
public :
virtual void push( const T & x) = 0 ;
virtual void pop() = 0 ; // 这样子void 类型有些不妥吧。

# re: 算法与数据结构实验(二)  回复  更多评论   

2006-03-22 18:15 by Tauruser
嗯,你认为应该如何呢?
我知道有些stack结构直接用pop(),弹出并返回栈顶,但这个模板类已经有一个Top()函数可以做到这个,将pop()返回值设为void有什么不妥呢?

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理