c++ - 使用链表对多项式进行匹配、加法和乘法

Question

所以我正在编写一个由乘法函数实现组成的程序，但是，我在编写 3 个函数时遇到了问题:匹配、加法和乘法。

匹配函数应该判断 2 个多项式是否相同。如果是，则返回 true，否则返回 false。

添加函数只是添加 2 个多项式。

乘法只是产生 2 个多项式的乘积。

我对如何开始这些功能感到困惑。任何建议或反馈都会有所帮助。太感谢了。

class Dlist
{
private:
Node* front;
public:
Dlist(Node* f = NULL){front = f;}

void insertInOrder(int c, int x, int y)
{
    Node* nn = new Node;
    nn->coef = c;
    nn->xdeg = x;
    nn->ydeg = y;
    int nsum = x + y;

    Node* p = front;


    if(front == NULL){
        front = nn;
        return;
    }
    while(p != NULL){
        if(x == p->xdeg && y == p->ydeg){
            p->coef += c;
            return;
        }
        p = p->next;
    }
    p = front;
    if(nsum > p->xdeg + p->ydeg){
        nn->next = p;
        front = nn;
        return;
    }
    else{
        while(p->next != NULL && p->next->xdeg + p->next->ydeg > nsum){
            p = p->next;
        }
    }
    nn->next = p->next;
    p->next = nn;
    return;
};

void print()
{
    Node* p = front;
    while(p != NULL){
        cout << p->coef << "/" << p->xdeg << "/" << p->ydeg << " -> ";
        p = p->next;
    }
    cout << "NULL" << endl;
    return;
};

int degree()
{
    Node* p = front;
    int maxd = 0;

    while(p != NULL){
        if(maxd < p->xdeg + p->ydeg){
            maxd = p->xdeg + p->ydeg;
        }
        p = p->next;
    }

    return maxd;
};

void coefficient(int input)
{
    Node* p = front;
   int index = 0;
   while(p != NULL){
        p = p->next;
        index++;
   }
   if(input < 0){
        cout << "Does not exist." << endl;
        return;
   }
   else if(input > index){
        cout << "Does not exist." << endl;
        return;
   }
   p = front;
   for(int i = 0; i != input; i++){
        p = p->next;
   }
   cout << p->coef << endl;
   return;
}
void sum()
{


}

};

Answer 1

如果我们考虑每个算法的伪代码，您可能会有类似的东西

function match(poly1,poly2):
    if(length(poly1) != length(poly2)) return false
    foreach term1 in poly1:
        boolean termmatched=false
        foreach term2 in poly2:
            if matchterms(term1,term2):
                termmatched = true
                break
        endfor
        if not termmatched:
            return false
    endfor
    return true
endfunction

因此，此搜索首先检查每个多项式中的项数是否相同。然后对于第一个多项式中的每个项，检查第二个多项式中是否有匹配的项。如果没有项匹配，则多项式不匹配，我们可以立即返回。

这确实假设您在第二个多项式中不能有一个项可以匹配第一个多项式中的两个不同项。一种更复杂的方法可能会为第二个多项式的每个项设置一个标志，以检查它是否已经匹配。

对于相加，您想要找到匹配并相加系数的任何项。如果没有匹配项，则只需添加该术语。在这里您可能想使用一个标志来检测第二个多项式中的哪些项匹配。或者，您可以从第二个多项式中删除匹配项。

function add(poly1,poly2):
    boolean flags[length(poly2)] // array of flags all false
    polynomial result = empty polynomial
    foreach term1 in poly1:
        boolean termmatched=false
        int i=0
        foreach term2 in poly2:
            if matchterms(term1,term2):
                result.add(new term(term1.coef+term2.coef,term1.xdeg,term1.ydeg))
                flags[i]=true   // mark flag for second term as matched
                termmatched = true
                break
             ++i
        endfor
        if not termmatched:
            result.add(new term(term1.coef,term1.xdeg,term1.ydeg))
    endfor

    i =0
    foreach term2 in poly2:
        if( not flags[i]) 
            result.add(new term(term1.coef,term1.xdeg,term1.ydeg))
    endfor
endfunction

乘法可能更棘手。这有点取决于你的多项式类。一个好的多项式类将有一个 add 方法，该方法将遍历所有现有项以检查匹配

class polynomial

methods add(coef,xord,yord):
    foreach term:
        if match(term,xord,yord):
            term.coef += coef
            return
    endfor
    // add a new term on the end of the linked list
    insertInOrder(coef,xord,yord)

用这个方法乘法就变成了

function multiply(poly1,poly2):
    result = new polynomial
    foreach term1 in poly1:
        foreach term2 in poly2:
            result.add( term1.coef*term2.coef,
                term1.xord + term2.xord,
                term1.yord + term2.yord)
        endfor
     endfor
     return result
 endfunction

使用这种智能相加方法，两个多项式的相加现在变得微不足道了

function add(poly1,poly2):
    result = new polynomial
    foreach term1 in poly1:
        result.add(term1.coef,term1.xord,term1.yord)
    endfor
    foreach term2 in poly2:
        result.add(term2.coef,term2.xord,term2.yord)
    endfor
    return result
endfunction