stack.h

九宫问题的深度和广度优先算法

/*********************************************************************************
 * stack.h
 * 定义栈类，用于三种算法的close表以及深度优先搜索的open表
***********************************************************************************/

class Stack{    //栈类
private:
    Data head,*loc;
    int len;
public:
    void init();    //初始化栈
    int length();    //返回栈的长度
    bool empty();    //判断栈是否为空
    void show();    //显示栈
    bool exist(DATATYPE *dt);    //判断元素是否在栈中已经出现过
    void push(DATATYPE *,Data **);    //数据入栈
    void pop(DATATYPE *,Data **);    //数据出栈
    Data * getTop(DATATYPE *);        //返回栈顶元素
};

void Stack::show(){
    if(empty()==true)    cout<<"stack is emtpy "<<endl;
    else    cout<<"there are "<<len<<" members in the stack"<<endl;
    Data *temp=loc;
    int i=0;
    while(temp){
        cout<<"step "<<i++<<" :"<<endl;
        showElement(temp->element);
        temp=temp->pid;
    }
}


bool Stack::exist(DATATYPE *dt){
    Data *temp=head.next;
    while(temp){
        if(memcmp(temp->element,dt,DATASIZE*sizeof(DATATYPE))==0)    return true;
        temp=temp->next;
    }
    return false;
}

Data *Stack::getTop(DATATYPE *dt){
    memcpy(dt,loc->element,DATASIZE*sizeof(DATATYPE));
    return loc;
}

void Stack::pop(DATATYPE *dt,Data **pid){
    if(empty()==true){
        cout<<"warning: pop stack error beacuse of stack is empty anykey to exit"<<endl;
        getchar();
        exit(1);
    }
    Data *temp=loc;
    loc=loc->pre;
    loc->next=NULL;
    memcpy(dt,temp->element,DATASIZE*sizeof(DATATYPE));
    *pid=temp->pid;
    delete temp;
    len--;
}

void Stack::push(DATATYPE *dt,Data **pid){
    Data *temp=loc;
    loc=loc->next=new Data;
    memcpy(loc->element,dt,DATASIZE*sizeof(DATATYPE));
    if(pid!=NULL)    loc->pid=*pid;
    else loc->pid=NULL;
    loc->next=NULL;
    loc->pre=temp;
    len++;
}

void Stack::init(){
    head.next=head.pid=head.pre=NULL;
    loc=&head;
    len=0;
}

int Stack::length(){
    return len;
}

bool Stack::empty(){
    return len==0? true:false;
}