queue.h

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

/**************************************************************************
 * queue.h
 * 定义队列类，用广度优先的open表
**************************************************************************/

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


void Queue::show(){
    if(empty()==true)    cout<<"nothing to print, queue is empty"<<endl;
    else cout<<"there are "<<len<<" members in the queue: "<<endl;
    Data *temp=head.next;
    while(temp){
        showElement(temp->element);
        temp=temp->next;
    }
}


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

Data * Queue::getTop(DATATYPE *dt){
    memcpy(dt,head.next->element,DATASIZE*sizeof(DATATYPE));
    return head.next;
}

void Queue::pop(DATATYPE *dt,Data **pid){
    if(empty()==true) {
        cout<<"warning: pop queue error beacuse of can not pop a empty queue anykey to exit"<<endl;
        getchar();
        exit(1);
    }
    Data *temp=head.next;
    memcpy(dt,temp->element,DATASIZE*sizeof(DATATYPE));
    *pid=temp->pid;
    head.next=temp->next;
    if(head.next)    head.next->pre=&head;
    delete temp;
    len--;
    if(len==0)    loc=&head;
}

void Queue::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 Queue::init(){
    head.next=head.pid=head.pre=NULL;
    loc=&head;
    len=0;
}

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

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