c++的染色问题纠错

Question

#include <iostream>

using namespace std;

typedef struct Etype
{
    int number;
    int color;
}Etype;

typedef struct stack
{
    Etype*element;
    int top;
    int Maxsize;
}stack;

void creat(stack&L,int maxsize)
{
    L.Maxsize=maxsize;
    L.element=new Etype[L.Maxsize];
    L.top=-1;
}

bool isempty(stack&L)
{
    if(L.top==-1) return 1;
    return 0;
}

bool isfull(stack&L)
{
    if(L.top>=L.Maxsize-1) return 1;
    return 0;
}

bool push(stack&L,Etype&x)
{
    if(isfull(L)) return 0;
    else
    {
        L.top++; 
        L.element[L.top]=x;
        return 1;
    }
}

bool pop(stack&L,Etype&x)
{
    if(isempty(L)) return 0;
    else
    {
        x=L.element[L.top];
        L.top--;
        return 1;
    }
}

void output(stack&L)
{
    Etype x;
    while(!isempty(L))
    {
        pop(L,x);
        cout<<"     "<<x.number<<"                "<<x.color;
        cout<<endl;
    }
}

void matchcolor(int n,int s[4][4],int sum)
{
    stack L,Lkeep;                    //Lkeep用于储存中转数组 
    Etype g,db,dl;                    //g用于储存新的数据，db用于取出L中原有数据进行对比，dl用于该位数据无法成立后取出上位数据 
    int num=0;                        //num用于标记地域 
    int tc=0;                         //tc用于标记上一次循环时g是否放入 
    int col;
    g.number=num;
    g.color=col;
    push(L,g);
    num++;
    while(num<=sum-1&&num>=0)
    {
        if(tc)
        {
            num--;
            col=dl.color+1;           //返回上位数据，且颜色初值加1 
            tc=0;
        }
        else
        {
            col=1;
        }
        g.number=num;
        g.color=col;
        while(!isempty(L)&&g.color<=n)
        {
            pop(L,db);                          //一位一位取出进行对比 
            push(Lkeep,db);
            if(s[db.number][g.number]&&(db.color==g.color))
            {
                g.color++;
                while(!isempty(Lkeep))
                {
                    pop(Lkeep,db);
                    push(L,db);
                }                                 //颜色加1，且原L重置，进行重新对比 
                    
            }
        }
        if(g.color>n)                             //所有颜色取完该位依旧无解 
        {
            tc=1;
            while(!isempty(Lkeep))
            {
                pop(Lkeep,db);
                push(L,db);
            }
            pop(L,dl);                           //取出上位元素 
        }
        else
        {
            while(!isempty(Lkeep))
            {
                pop(Lkeep,db);
                push(L,db);
            }
            push(L,g);
            num++;                              //有解则重置L，且将新元素放入其中 
        }
    }
    if(num==sum) 
    {
        output(L);
    }
}

int main()
{
    int sum=4;
    int n=4;
    int s[4][4]={{0,1,0,0},{1,0,1,0},{0,1,0,0},{0,0,0,0}};
    matchcolor(n,s,sum);
    return 0;
}

能帮我看看为什么这段代码处理染色问题始终没有输出吗？
自己看了好久
return的数也有问题

Answer 1

可以发现问题出在 Etype g, db, dl; 和 g.color=col; 这两行代码处。

在使用 g 时，没有对其进行初始化赋值。因此在第一次判断 if(s[db.number][g.number]&&(db.color==g.color)) 时，g.color 的值为未知状态，因此无法得到正确结果。

修改方式: 在第 16 行处加入 g.number=-1; g.color=0; 进行初始化赋值，避免使用未知状态的 g。

另外，在第 44 行处，g.color <= n 条件判断应该改为 g.color < n，因为颜色编号是从 1 开始的。

修改后的代码如下：

#include <iostream>
 
using namespace std;
 
typedef struct Etype
{
    int number;
    int color;
} Etype;
 
typedef struct stack
{
    Etype* element;
    int top;
    int Maxsize;
} stack;
 
void creat(stack& L, int maxsize)
{
    L.Maxsize = maxsize;
    L.element = new Etype[L.Maxsize];
    L.top = -1;
}
 
bool isempty(stack& L)
{
    if (L.top == -1) {
        return true;
    }
    return false;
}
 
bool isfull(stack& L)
{
    if (L.top >= L.Maxsize - 1) {
        return true;
    }
    return false;
}
 
bool push(stack& L, Etype& x)
{
    if (isfull(L)) {
        return false;
    }
    L.top++;
    L.element[L.top] = x;
    return true;
}
 
bool pop(stack& L, Etype& x)
{
    if (isempty(L)) {
        return false;
    }
    x = L.element[L.top];
    L.top--;
    return true;
}
 
void output(stack& L)
{
    Etype x;
    while (!isempty(L))
    {
        pop(L, x);
        cout << "     " << x.number + 1 << "                " << x.color << endl;
    }
}
 
void matchcolor(int n, int s[4][4], int sum)
{
    stack L, Lkeep;                    //Lkeep用于储存中转数组 
    Etype g, db, dl;                   //g用于储存新的数据，db用于取出L中原有数据进行对比，dl用于该位数据无法成立后取出上位数据 
    creat(L, 100);
    creat(Lkeep, 100);
    g.number = -1;
    g.color = 0;
    push(L, g);
    int num = 0;                        //num用于标记地域 
    int tc = 0;                         //tc用于标记上一次循环时g是否放入 
    int col;
    while (num <= sum - 1 && num >= 0)
    {
        if (tc)
        {
            num--;
            col = dl.color + 1;           //返回上位数据，且颜色初值加1 
            tc = 0;
        }
        else
        {
            col = 1;
        }
        g.number = num;
        g.color = col;
        while (!isempty(L) && g.color < n)
        {
            pop(L, db);                          //一位一位取出进行对比 
            push(Lkeep, db);
            if (s[db.number][g.number] && (db.color == g.color))
            {
                g.color++;
                while (!isempty(Lkeep))
                {
                    pop(Lkeep, db);
                    push(L, db);
                }                                 //颜色加1，且原L重置，进行重新对比 
                   
            }
        }
        if (g.color >= n)                             //所有颜色取完该位依旧无解 
        {
            tc = 1;
            while (!isempty(Lkeep))
            {
                pop(Lkeep, db);
                push(L, db);
            }
            pop(L, dl);                           //取出上位元素 
        }
        else
        {
            while (!isempty(Lkeep))
            {
                pop(Lkeep, db);
                push(L, db);
            }
            push(L, g);
            num++;                              //有解则重置L，且将新元素放入其中 
        }
    }
    if (num == sum)
    {
        output(L);
    }
}
 
int main()
{
    int sum = 4;
    int n = 4;
    int s[4][4]= { {0, 1, 0, 0}, {1, 0, 1, 0}, {0, 1, 0, 0}, {0, 0, 0, 0} };
    matchcolor(n, s, sum);
    return 0;
}