c - 在 C 中以规范顺序排列多项式

Question

标签： csortingstructlinked-listpolynomials

Answer 1

The problem boils down to sorting a linked list, for which you need a suitable comparison function to determine the sort order for two terms on the list:

int compareTerms(const struct Node *a, const struct Node *b)
{
    int cmp;

    /* Compare X exponents. */
    cmp = (a->powX > b->powX) - (a->powX < b->powX);
    if (cmp != 0) {
        return cmp;
    }
    /* Compare Y exponents. */
    cmp = (a->powY > b->powY) - (a->powY < b->powY);
    if (cmp != 0) {
        return cmp;
    }
    /* Compare Z exponents. */
    cmp = (a->powZ > b->powZ) - (a->powZ < b->powZ);
#if 0
    if (cmp != 0) {
        return cmp;
    }
    /* Compare coefficients (why not?). */
    cmp = (a->coeff > b->coeff) - (a->coeff < b->coeff);
#endif
    return cmp;
}

(Change the #if 0 to #if 1 to compare the coefficients if all the exponents are equal.)

The function returns -1 if the first term has lower order than the second, 1 if the first term has higher order than the second, or 0 if they are of equal order.

The comparison function can be used by a function to sort the list of terms. For simplicity, an exchange sort is shown below:

void sortPolynomialTerms(struct Node **poly)
{
    while (*poly) {
        struct Node **next = &(*poly)->next;
        while (*next) {
            struct Node *n = *next;
            if (compareTerms(*poly, n) < 0) {
                *next = n->next;
                n->next = *poly;
                *poly = n;
            } else {
                next = &n->next;
            }
        }
        poly = &(*poly)->next;
    }
}

The sort function can be used as follows:

void printPolynomial(const struct Node *poly)
{
    while (poly)
    {
        printf("%d %d %d %.3f\n", poly->powX, poly->powY, poly->powZ, poly->coeff);
        poly = poly->next;
    }
}

void canonicalPolynomial(struct Node **poly)
{
    sortPolynomialTerms(poly);
    printPolynomial(*poly);
}

The parameter of sortPolynomialTerms and canonicalPolynomial is struct Node **poly because they may modify the pointer to the initial term *poly to point to a different initial term.

---

BONUS CONTENT

It is probably not worth it for short polynomials, but for polynomials containing many terms to be sorted, a merge sort will be more efficient than the exchange sort implemented above. Based on the sample code "listsort.c" for the page "Mergesort For Linked Lists" by Simon Tatham, the following version of sortPolynomialTerms uses a bottom-up merge sort:

void sortPolynomialTerms(struct Node **poly)
{
    /*
     * Bottom-up merge sort, based on:
     *
     * <https://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.c>
     *
     * Original copyright notice for linked source:
     *
     * This file is copyright 2001 Simon Tatham.
     * 
     * Permission is hereby granted, free of charge, to any person
     * obtaining a copy of this software and associated documentation
     * files (the "Software"), to deal in the Software without
     * restriction, including without limitation the rights to use,
     * copy, modify, merge, publish, distribute, sublicense, and/or
     * sell copies of the Software, and to permit persons to whom the
     * Software is furnished to do so, subject to the following
     * conditions:
     * 
     * The above copyright notice and this permission notice shall be
     * included in all copies or substantial portions of the Software.
     * 
     * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
     * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
     * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
     * NONINFRINGEMENT.  IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
     * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
     * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
     * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
     * SOFTWARE.
     */
    struct Node *head;      /* head of merged list */
    unsigned int sublen;    /* maximum length of sub-list */

    head = *poly;
    if (!head) {
        /* The list is empty, so does not need sorting. */
        return;
    }

    /* Start with sub-lists of maximum length 1. */
    sublen = 1;
    while (1) {
        struct Node *tail;      /* tail of merged list */
        struct Node *p;         /* pointer to node in first sub-list */
        struct Node *q;         /* pointer to node in second sub-list */
        struct Node *e;         /* pointer to node to add to merged list */
        unsigned int plen;      /* length of first sub-list */
        unsigned int qlen;      /* maximum length of second sub-list */
        unsigned int merges;    /* number of sub-list merges done */
        unsigned int i;

        /*
         * Construct a new merge list by merging one or more pairs
         * of sorted sub-lists of length up to `sublen`.
         */
        p = head;
        head = NULL;
        tail = NULL;
        merges = 0;
        while (p) {
            merges++;
            /* Step up to `sublen` places along from `p`. */
            q = p;
            plen = 0;
            for (i = 0; i < sublen; i++) {
                plen++;
                q = q->next;
                if (!q) {
                    break;
                }
            }

            qlen = plen;    /* upper bound on length of second sub-list */

            /*
             * Merge the two sub-lists onto the end of the new merge list.
             */
            while (plen || (qlen && q)) {
                /* Decide where the next element to merge comes from. */
                if (!plen || (qlen && q && compareTerms(p, q) < 0)) {
                    /* Take next element from second list `q`. */
                    e = q;
                    q = q->next;
                    qlen--;
                } else {
                    /* Take next element from first list `p`. */
                    e = p;
                    p = p->next;
                    plen--;
                }
                /* Add next element to the merged list. */
                if (tail) {
                    tail->next = e;
                } else {
                    head = e;
                }
                tail = e;
            }

            /* Advance to the next pair of sub-lists. */
            p = q;
        }
        /* Terminate the new merge list. */
        tail->next = NULL;

        /* Finish when no more than one pair of sub-lists needed merging. */
        if (merges <= 1) {
            break;
        }
        
        /* Double the maximum length of the sub-lists for the next merge. */
        sublen *= 2;
    }

    /* Update the link to the first node of the list. */
    *poly = head;
}