base.txt

基本数据结构类的定义和实现: MyStack ,MyPoint,MyArc,Graph,MyQueuesMyStack为构造的一个通用的C++模版堆栈类 MyPoint为一个坐标结构MyArc为带权的

#ifndef BASE_H
#define BASE_H

#include<list>
using namespace std;

/*
MyStack 堆栈类的结构   [ 0         1 ... curlen ...   size]
              [栈底(bottom)     ... prt   ...     ]
*/
#define BASESIZE 64     //默认堆栈数组空间大小（8*8）,可以自扩充

template <class Type> 
class MyStack
{
private:
    Type *bottom;     // 元素存放的动态数组       

    int size,ptr; // 堆栈大小和当前栈顶元素索引
public: 
    //构造函数
    MyStack()       
    {
        bottom=new Type[BASESIZE];ptr=-1;size=BASESIZE;
    };
    
    //析构函数
    ~MyStack(){delete []bottom;};

    //清栈还原
    inline void clear()
    {
        if(bottom!=NULL)
              delete []bottom;
    bottom=new Type[size];
        ptr=-1;         
    };

    //判栈空
    inline bool IsEmpty()
    {
        if(ptr==-1) return true;
        else return false;
    }

    //入栈
    int push(Type e);
    //出栈
    int pop(Type &e);
    //获得栈顶元素
    int top(Type &e);
    int settop(Type e);
    // 用callback函数对栈从低向上遍历
    void traverse(void callback(Type *),Type *); 
private:
    inline int extent()
    {
        int s=size;
        Type *temp=new Type[size];
        for(int i=0;i<s;i++)
              temp[i]=bottom[i];
        size*=2;
        clear();
        ptr=s+1;
        for(int i=0;i<s;i++)
              bottom[i]=temp[i];
        delete [] temp;
        return size;
    }

};


/*
MyStack的实现 
*/

/*压栈*/
template <class Type> 
int MyStack<Type>::push(Type e) // 
{         
    if(++ptr==size) extent();
    bottom[ptr]=e;     
    return ptr; 
}

/*出栈*/
template <class Type> 
int MyStack<Type>::pop(Type &e) // 
{
    if(ptr==-1)
              return -2;//栈空，返回 -2 ！
    else     
        e=bottom[ptr--];     
    return ptr;
}

/*获取栈顶元素*/
template <class Type>
int MyStack<Type>::top(Type &e) // 
{
    if(ptr==-1)
        return -1;//栈空,返回 -1 ！
    else
        e=bottom[ptr];
    return ptr;
}

/*设置栈定元素*/
template <class Type>
int MyStack<Type>::settop(Type e) //
{
    if(ptr==-1)
        return -1;//栈空,返回 -1 ！
    else
        bottom[ptr]=e;
    return ptr;
}

/*用callback函数对栈从低向上遍历*/
template <class Type>
void MyStack<Type>::traverse(void callback(Type *),Type *e)
{
    if(callback!=NULL)
    {
        for(int i=0;i<=ptr;i++)
        {
              e=&bottom[i];
              callback(e);
        }
    }
}; // 

/*
MyPoint 坐标结构   
*/
typedef struct MyPoint
{
    int x, y;
} *pMyPoint;

//
/*
表示边的类
*/
class MyArc
{
public:
    int m_beginVex;
    int m_endVex;
    int m_weight;
    MyArc(int beginVex,int endVex,int weight);
    MyArc(){}
    bool operator < (const MyArc& arc)
    {
        return m_weight<arc.m_weight;
    }
    bool operator == (const MyArc& arc)
    {
        return m_weight==arc.m_weight;
    }
    bool operator > (const MyArc& arc)
    {
        return m_weight>arc.m_weight;
    }
};

MyArc::MyArc(int beginVex,int endVex,int weight):m_beginVex(beginVex),m_endVex(endVex),m_weight(weight)
{}

/*
用邻接矩阵表示的图类，可以带权，权不可以为0
*/
class Graph
{
public:
    int m_vexnum;
    int m_arcnum;
    int *m_pmatrix;
public:
    ~Graph();
    Graph(int vexnum);
    Graph(int vexnum,int *pmatrix);
    void insert(MyArc arc);//按权值大小排序插入
    bool bound(int x);   //判断顶点x是否已与其它顶点连通
};

//构造函数
Graph::Graph(int vexnum)
{
    m_pmatrix=new int[vexnum*vexnum];
    m_vexnum=vexnum;m_arcnum=0;
    for(int i=0;i<vexnum*vexnum;++i) m_pmatrix[i]=0;

}

//构造函数
Graph::Graph(int vexnum,int *pmatrix)
{
    m_vexnum=vexnum;
    // m_arcnum=arcnum;
    m_pmatrix=new int[m_vexnum*m_vexnum];
    for(int i=0;i<m_vexnum*m_vexnum;++i)
        m_pmatrix[i]=pmatrix[i];
}

//测试 顶点x是否已与其他点连通
bool Graph::bound(int x)
{
    for(int i=0;i<m_vexnum;++i) if(m_pmatrix[x+i*m_vexnum]!=0) return true;
    return false;
}

//在邻接表中连通 arc表示的边，并且设置权
void Graph::insert(MyArc arc)
{
    m_pmatrix[arc.m_beginVex*m_vexnum+arc.m_endVex]=arc.m_weight;
    m_pmatrix[arc.m_endVex*m_vexnum+arc.m_beginVex]=arc.m_weight;
    ++m_arcnum;
}


Graph::~Graph()
{
    delete[] m_pmatrix;
}

/*
自定义队列，用于存放连通图，或按权排列后的边
*/
class MyQueues
{
public:
    list<MyArc> m_list;
    MyQueues(){}
    void insert(const MyArc& arc);//边按权值插入队列中合适位置,
    void InsertGraph(const Graph &graph);//将图的连通分量插入队列
    MyArc pop();
};

//边出队
MyArc MyQueues::pop()
{
    MyArc arc=m_list.front();
    m_list.pop_front();                                   
    return arc;
}

//边按权值插入队列中合适位置,
void MyQueues::insert(const MyArc& arc)
{
    list<MyArc>::iterator pos=m_list.begin();
    while(pos!=m_list.end())
    {
        if(*pos>arc) break;
        else ++pos;
    }
    m_list.insert(pos,arc);
}

//将图的连通分量插入队列
void MyQueues::InsertGraph(const Graph &graph)
{
    for(int i=0;i<graph.m_vexnum;++i)
    {
        for(int j=i+1;j<graph.m_vexnum;++j)
              if(graph.m_pmatrix[i*graph.m_vexnum+j]) insert(MyArc(i,j,graph.m_pmatrix[i*graph.m_vexnum+j]));
    }
}

#endif