link.h

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

/*********************************************************************************
 * link.h
 * 定义链表类，用于A*算法中的open表
*********************************************************************************/

class Link: public Queue{    //链表类
private:
    Data head;
    F fhead;        //估价函数临时表
    int len;
public:
    void init();    //链表初始化
    void show();    //显示链表
    void push(DATATYPE *,Data **);    //数据入队
    void pop(DATATYPE *,Data **);    //数据出队
};    


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




void Link::init(){
    head.next=head.pid=head.pre=NULL;
    fhead.next=NULL;
    len=0;
}




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



void Link::push(DATATYPE *dt,Data **pid){
    int gx,hx;
    int n,m,k;
    Data *temp,*loc;    
    F *ftemp;
    hx=k=0;
    /**//************************* 计算启发函数 h(x)    **************************/
    for(n=0;n<LINE;n++)        
        for(m=0;m<ROW;m++)
            if(dt[k++]!=sg[n][m]) hx++;
    /**//************************* 计算 g(x) ************************************/
    if(fhead.next!=NULL){    //fhead表中存在数据
        for(ftemp=fhead.next;ftemp;ftemp=ftemp->next)
            if(ftemp->addr=*pid){
                gx=ftemp->gx+1;
                break;
            }
            if(ftemp==NULL){
                puts("can not caculate function g(x), program will exit");
                exit(1);
            }
    }
    else{    //fhead表为空
        gx=0;    //根节点
    }
    /**//******************************创建新数据********************************/
    temp=new Data;    
    memcpy(temp->element,dt,DATASIZE*sizeof(DATATYPE));        //将dt复制给temp
    temp->gx=gx;            
    temp->hx=hx;
    if(pid!=NULL)    temp->pid=*pid;
    else temp->pid=NULL;
    temp->pre=temp->next=NULL;
    /**//******************************将数据添加到链表中**********************/
    if(head.next==NULL){    //链表为空
        head.next=temp;
        temp->pre=&head;
        temp->next=NULL;
        ++len;
        return    ;
    }
    else{    //链表不空
        loc=head.next;
        while(1){
            if((temp->gx+temp->hx)<=(loc->gx+loc->hx)){
                loc->pre->next=temp;
                temp->pre=loc->pre;
                temp->next=loc;
                loc->pre=temp;
                ++len;
                return;
            }
            else if(loc->next==NULL){
                loc->next=temp;
                temp->next=NULL;
                temp->pre=loc;
                ++len;
                return;
            }
            else{
                loc=loc->next;
            }
        }
    }
}