在 C 中按规范顺序排列多项式
Arrange the Polynomial in Canonical Order in C
假设我有一个包含 3 个变量 (x, y, z) 的多项式，它不一定按规范顺序排列，我希望它采用标准形式，其中最左边的项具有最大指数，最右边的项具有最小的指数。例如案例：
原始多项式：
-7xy⁶ + 9xz - 8y⁷ +x⁷ + 4x⁵y⁴z² + 4xy²z³ + 3xy³
标准格式：
x⁷ + 4x⁵y³z² - 7xy⁶ + 3xy³ + 4xy²z³ + 9xz - 8y⁷
这可以在 Python 中轻松完成，但我在 C 中，我不知道应该如何完成。这是我用 struct 实现多项式的示例代码。为了让它看起来不那么混乱，我没有显示变量。相反，我的格式是：x exponent y exponent z exponent coefficient。示例：4(x^5)(y^3)(z^2) 是 5 3 2 4.
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int coeff;
int powX;
int powY;
int powZ;
struct Node* next;
};
void readPolynomial(struct Node** poly) /* ACCEPTS A POLYNOMIAL WITH N TERMS */
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
*poly = temp;
int terms;
scanf("%d\n", &terms);
for(int i = 0; i < terms; i++)
{
char entry[200];
fgets(entry, sizeof(entry), stdin);;
char * splitter;
splitter = strtok(entry," ");
temp->powX = atoi(splitter);
splitter = strtok(NULL, " ");
temp->powY = atoi(splitter);
splitter = strtok(NULL, " ");
temp->powZ = atoi(splitter);
splitter = strtok(NULL, " ");
temp->coeff = atoi(splitter);
temp->next = NULL;
if(i != terms-1)
{
temp->next = (struct Node*)malloc(sizeof(struct Node));
temp = temp->next;
temp->next = NULL;
}
}
}
void canonicalPolynomial(struct Node* poly)
{
while(poly != NULL)
{
printf("%d %d %d %d\n", poly->powX, poly->powY, poly->powZ, poly->coeff);
poly = poly->next;
}
}
int main()
{
struct Node* result = NULL;
readPolynomial(&result);
canonicalPolynomial(result);
return 0;
}
现在，canonicalPolynomial 只是以上述格式打印，但尚未按规范顺序打印。
输入：
7
1 6 0 -7
1 0 1 9
0 7 0 -8
7 0 0 1
5 3 2 4
1 2 3 4
1 3 0 3
预期输出：
7 0 0 1
5 3 2 4
1 6 0 -7
1 3 0 3
1 2 3 4
1 0 1 9
0 7 0 -8
更新：这是我的最新代码。我得到了正确的给定测试代码，但我错过了编译器中隐藏的代码。到目前为止，我的代码知道项何时具有系数 0，但不会打印它。我还能缺少什么？
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
struct Node
{
float coeff;
int powX;
int powY;
int powZ;
struct Node* next;
};
void readPolynomial(struct Node** poly)
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
*poly = temp;
int terms;
fscanf(stdin, "%d", &terms);
getchar();
char entry[999999];
char *splitter;
for(int i = 0; i < terms; i++)
{
fgets(entry, sizeof(entry), stdin);
splitter = strtok(entry," ");
temp->powX = atoi(splitter);
splitter = strtok(NULL, " ");
temp->powY = atoi(splitter);
splitter = strtok(NULL, " ");
temp->powZ = atoi(splitter);
splitter = strtok(NULL, " ");
temp->coeff = atof(splitter);
temp->next = NULL;
if(i != terms-1)
{
temp->next = (struct Node*)malloc(sizeof(struct Node));
temp = temp->next;
temp->next = NULL;
}
}
}
int compareTerms(const struct Node *a, const struct Node *b)
{
int cmp;
cmp = (a->powX > b->powX) - (a->powX < b->powX);
if (cmp != 0) {
return cmp;
}
cmp = (a->powY > b->powY) - (a->powY < b->powY);
if (cmp != 0) {
return cmp;
}
cmp = (a->powZ > b->powZ) - (a->powZ < b->powZ);
return cmp;
}
void sortPolynomialTerms(struct Node **poly)
{
struct Node *head;
unsigned int sublen;
head = *poly;
if (!head) {
return;
}
sublen = 1;
while (1) {
struct Node *tail;
struct Node *p;
struct Node *q;
struct Node *e;
unsigned int plen;
unsigned int qlen;
unsigned int merges;
unsigned int i;
p = head;
head = NULL;
tail = NULL;
merges = 0;
while (p) {
merges++;
q = p;
plen = 0;
for (i = 0; i < sublen; i++) {
plen++;
q = q->next;
if (!q) {
break;
}
}
qlen = plen;
while (plen || (qlen && q)) {
if (!plen || (qlen && q && compareTerms(p, q) < 0)) {
e = q;
q = q->next;
qlen--;
} else {
e = p;
p = p->next;
plen--;
}
if (tail) {
tail->next = e;
} else {
head = e;
}
tail = e;
}
p = q;
}
tail->next = NULL;
if (merges <= 1) {
break;
}
sublen *= 2;
}
*poly = head;
}
void printPolynomial(const struct Node *poly)
{
while (poly)
{
if(poly->coeff != 0)
{
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);
}
void addPolynomials(struct Node** result, struct Node* first, struct Node* second)
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->next = NULL;
*result = temp;
while(first && second)
{
if(compareTerms(first, second) < 0)
{
temp->coeff = second->coeff;
temp->powX = second->powX;
temp->powY = second->powY;
temp->powZ = second->powZ;
second = second->next;
}
else if(compareTerms(first, second) > 0)
{
temp->coeff = first->coeff;
temp->powX = first->powX;
temp->powY = first->powY;
temp->powZ = first->powZ;
first = first->next;
}
else
{
temp->coeff = first->coeff + second->coeff;
temp->powX = first->powX;
temp->powY = first->powY;
temp->powZ = first->powZ;
first = first->next;
second = second->next;
}
if(first && second)
{
temp->next = (struct Node*)malloc(sizeof(struct Node));
temp = temp->next;
temp->next = NULL;
}
}
while(first || second)
{
temp->next = (struct Node*)malloc(sizeof(struct Node));
temp = temp->next;
temp->next = NULL;
if(second)
{
temp->coeff = second->coeff;
temp->powX = second->powX;
temp->powY = second->powY;
temp->powZ = second->powZ;
second = second->next;
}
else if(first)
{
temp->coeff = first->coeff;
temp->powX = first->powX;
temp->powY = first->powY;
temp->powZ = first->powZ;
first = first->next;
}
}
}
int main()
{
struct Node* first = NULL;
struct Node* second = NULL;
struct Node* result = NULL;
readPolynomial(&first);
readPolynomial(&second);
addPolynomials(&result, first, second);
canonicalPolynomial(&result);
return 0;
}
排序链表最简单的方法是将其转换为常规列表，使用 qsort 然后转换回来。像这样：
// Converts a linked list to array
//
// Assumes that memory is already allocated for dest and that src is a proper
// linked list where the last element has NULL assigned to ->next
void linkedListToArray(struct Node *dest, struct Node *src) {
while(src) {
*dest = src;
dest++;
src = src->next;
}
}
您应该重新设计代码以更加模块化。链表的实现你应该大体研究一下，但是你真的应该写一个类似这样的函数：
void append(struct Node **list, int coeff, int px, int py, int pz) {
struct Node *node = malloc(sizeof *node);
*node = (struct Node) {.coeff = coeff, .powX = px, .powY = py, .powZ = pz };
if(*list == NULL) {
*list = node;
} else {
while((*list)->next) (*list) = (*list)->next;
(*list)->next = node;
}
}
您应该在 readPolynomial 中使用它，但也可以在将数组转换为链表的函数中使用它。
void arrayToLinkedList(struct Node **list, struct Node *arr, size_t size) {
for(size_t i = 0; i < size; i++)
append(list, &arr[i]);
}
当你有了以上的时候，你只需要写quicksort的compare函数就可以了。阅读有关如何完成的文档。然后你可以这样做：
struct Node *pol;
// Init code
struct Node *arr = malloc(sizeof *arr * size); // Calculate size before somehow
linkedListToArray(arr, pol);
qsort(arr, size, sizeof *arr, cmp);
struct Node *newPol;
arrayToLinkedList(&newPol, arr);
请注意，我已跳过所有错误检查以保持代码简短。
旧答案。我误解了这个问题，但 OP 提到他们喜欢评论中的答案。下面说的是如何将多项式变成标准形式，但我真正要回答的问题是如何将多项式归一化。
要将其转换为标准规范化形式，您基本上需要做两件事
找到度数最高的词
将所有项除以最高次数项的系数。
在处理多个变量时，确定最高次数的项是不明确的，因为次数只是 Node::powX + Node::powY + Node::powZ。但是在任何情况下，您都需要定义一个函数，该函数采用整个多项式和 returns 根据某些定义具有最高度数的节点。这是一种方法：
int degree(struct Node *term) {
return term->powX + term->powY + term->powZ;
}
struct Node *getTermWithHighestDegree(struct Node *pol) {
struct Node *ret = pol;
while(pol) {
if(degree(pol) > degree(ret)) ret = pol;
pol = pol->next;
}
}
然后简单地做：
void convertToNormalizedForm(struct Node *pol) {
struct Node *term = getTermWithHighestDegree(pol);
int coeff = term->coeff;
while(pol) {
pol->coeff /= coeff;
pol = pol->next;
}
}
但是请注意，您可能 运行 遇到几个问题，因为您将系数存储为整数。您可能想更改为浮点类型。
问题归结为对链表进行排序，为此您需要一个合适的比较函数来确定列表中两个术语的排序顺序：
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;
}
（如果所有指数都相等，则将#if 0更改为#if 1以比较系数。）
函数returns如果第一项的阶数低于第二项则为-1，如果第一项的阶数高于第二项则为1，如果它们的阶数相同则为0。
函数可以使用比较函数对术语列表进行排序。为简单起见，交换排序如下所示：
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;
}
}
排序功能可以这样使用：
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);
}
sortPolynomialTerms和canonicalPolynomial的参数是struct Node **poly，因为它们可能会修改指向初始项的指针*poly以指向不同的初始项。
奖励内容
短多项式可能不值得，但对于包含许多要排序的项的多项式，合并排序将比上面实现的交换排序更有效。基于 Simon Tatham 的示例代码“listsort.c" for the page "Mergesort For Linked Lists”，sortPolynomialTerms 的以下版本使用自下而上的归并排序：
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;
}
假设我有一个包含 3 个变量 (x, y, z) 的多项式，它不一定按规范顺序排列，我希望它采用标准形式，其中最左边的项具有最大指数，最右边的项具有最小的指数。例如案例：
原始多项式：
-7xy⁶ + 9xz - 8y⁷ +x⁷ + 4x⁵y⁴z² + 4xy²z³ + 3xy³
标准格式：
x⁷ + 4x⁵y³z² - 7xy⁶ + 3xy³ + 4xy²z³ + 9xz - 8y⁷
这可以在 Python 中轻松完成，但我在 C 中，我不知道应该如何完成。这是我用 struct 实现多项式的示例代码。为了让它看起来不那么混乱，我没有显示变量。相反，我的格式是：x exponent y exponent z exponent coefficient。示例：4(x^5)(y^3)(z^2) 是 5 3 2 4.
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int coeff;
int powX;
int powY;
int powZ;
struct Node* next;
};
void readPolynomial(struct Node** poly) /* ACCEPTS A POLYNOMIAL WITH N TERMS */
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
*poly = temp;
int terms;
scanf("%d\n", &terms);
for(int i = 0; i < terms; i++)
{
char entry[200];
fgets(entry, sizeof(entry), stdin);;
char * splitter;
splitter = strtok(entry," ");
temp->powX = atoi(splitter);
splitter = strtok(NULL, " ");
temp->powY = atoi(splitter);
splitter = strtok(NULL, " ");
temp->powZ = atoi(splitter);
splitter = strtok(NULL, " ");
temp->coeff = atoi(splitter);
temp->next = NULL;
if(i != terms-1)
{
temp->next = (struct Node*)malloc(sizeof(struct Node));
temp = temp->next;
temp->next = NULL;
}
}
}
void canonicalPolynomial(struct Node* poly)
{
while(poly != NULL)
{
printf("%d %d %d %d\n", poly->powX, poly->powY, poly->powZ, poly->coeff);
poly = poly->next;
}
}
int main()
{
struct Node* result = NULL;
readPolynomial(&result);
canonicalPolynomial(result);
return 0;
}
现在，canonicalPolynomial 只是以上述格式打印，但尚未按规范顺序打印。
输入：
7
1 6 0 -7
1 0 1 9
0 7 0 -8
7 0 0 1
5 3 2 4
1 2 3 4
1 3 0 3
预期输出：
7 0 0 1
5 3 2 4
1 6 0 -7
1 3 0 3
1 2 3 4
1 0 1 9
0 7 0 -8
更新：这是我的最新代码。我得到了正确的给定测试代码，但我错过了编译器中隐藏的代码。到目前为止，我的代码知道项何时具有系数 0，但不会打印它。我还能缺少什么？
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
struct Node
{
float coeff;
int powX;
int powY;
int powZ;
struct Node* next;
};
void readPolynomial(struct Node** poly)
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
*poly = temp;
int terms;
fscanf(stdin, "%d", &terms);
getchar();
char entry[999999];
char *splitter;
for(int i = 0; i < terms; i++)
{
fgets(entry, sizeof(entry), stdin);
splitter = strtok(entry," ");
temp->powX = atoi(splitter);
splitter = strtok(NULL, " ");
temp->powY = atoi(splitter);
splitter = strtok(NULL, " ");
temp->powZ = atoi(splitter);
splitter = strtok(NULL, " ");
temp->coeff = atof(splitter);
temp->next = NULL;
if(i != terms-1)
{
temp->next = (struct Node*)malloc(sizeof(struct Node));
temp = temp->next;
temp->next = NULL;
}
}
}
int compareTerms(const struct Node *a, const struct Node *b)
{
int cmp;
cmp = (a->powX > b->powX) - (a->powX < b->powX);
if (cmp != 0) {
return cmp;
}
cmp = (a->powY > b->powY) - (a->powY < b->powY);
if (cmp != 0) {
return cmp;
}
cmp = (a->powZ > b->powZ) - (a->powZ < b->powZ);
return cmp;
}
void sortPolynomialTerms(struct Node **poly)
{
struct Node *head;
unsigned int sublen;
head = *poly;
if (!head) {
return;
}
sublen = 1;
while (1) {
struct Node *tail;
struct Node *p;
struct Node *q;
struct Node *e;
unsigned int plen;
unsigned int qlen;
unsigned int merges;
unsigned int i;
p = head;
head = NULL;
tail = NULL;
merges = 0;
while (p) {
merges++;
q = p;
plen = 0;
for (i = 0; i < sublen; i++) {
plen++;
q = q->next;
if (!q) {
break;
}
}
qlen = plen;
while (plen || (qlen && q)) {
if (!plen || (qlen && q && compareTerms(p, q) < 0)) {
e = q;
q = q->next;
qlen--;
} else {
e = p;
p = p->next;
plen--;
}
if (tail) {
tail->next = e;
} else {
head = e;
}
tail = e;
}
p = q;
}
tail->next = NULL;
if (merges <= 1) {
break;
}
sublen *= 2;
}
*poly = head;
}
void printPolynomial(const struct Node *poly)
{
while (poly)
{
if(poly->coeff != 0)
{
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);
}
void addPolynomials(struct Node** result, struct Node* first, struct Node* second)
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->next = NULL;
*result = temp;
while(first && second)
{
if(compareTerms(first, second) < 0)
{
temp->coeff = second->coeff;
temp->powX = second->powX;
temp->powY = second->powY;
temp->powZ = second->powZ;
second = second->next;
}
else if(compareTerms(first, second) > 0)
{
temp->coeff = first->coeff;
temp->powX = first->powX;
temp->powY = first->powY;
temp->powZ = first->powZ;
first = first->next;
}
else
{
temp->coeff = first->coeff + second->coeff;
temp->powX = first->powX;
temp->powY = first->powY;
temp->powZ = first->powZ;
first = first->next;
second = second->next;
}
if(first && second)
{
temp->next = (struct Node*)malloc(sizeof(struct Node));
temp = temp->next;
temp->next = NULL;
}
}
while(first || second)
{
temp->next = (struct Node*)malloc(sizeof(struct Node));
temp = temp->next;
temp->next = NULL;
if(second)
{
temp->coeff = second->coeff;
temp->powX = second->powX;
temp->powY = second->powY;
temp->powZ = second->powZ;
second = second->next;
}
else if(first)
{
temp->coeff = first->coeff;
temp->powX = first->powX;
temp->powY = first->powY;
temp->powZ = first->powZ;
first = first->next;
}
}
}
int main()
{
struct Node* first = NULL;
struct Node* second = NULL;
struct Node* result = NULL;
readPolynomial(&first);
readPolynomial(&second);
addPolynomials(&result, first, second);
canonicalPolynomial(&result);
return 0;
}
排序链表最简单的方法是将其转换为常规列表，使用 qsort 然后转换回来。像这样：
// Converts a linked list to array
//
// Assumes that memory is already allocated for dest and that src is a proper
// linked list where the last element has NULL assigned to ->next
void linkedListToArray(struct Node *dest, struct Node *src) {
while(src) {
*dest = src;
dest++;
src = src->next;
}
}
您应该重新设计代码以更加模块化。链表的实现你应该大体研究一下，但是你真的应该写一个类似这样的函数：
void append(struct Node **list, int coeff, int px, int py, int pz) {
struct Node *node = malloc(sizeof *node);
*node = (struct Node) {.coeff = coeff, .powX = px, .powY = py, .powZ = pz };
if(*list == NULL) {
*list = node;
} else {
while((*list)->next) (*list) = (*list)->next;
(*list)->next = node;
}
}
您应该在 readPolynomial 中使用它，但也可以在将数组转换为链表的函数中使用它。
void arrayToLinkedList(struct Node **list, struct Node *arr, size_t size) {
for(size_t i = 0; i < size; i++)
append(list, &arr[i]);
}
当你有了以上的时候，你只需要写quicksort的compare函数就可以了。阅读有关如何完成的文档。然后你可以这样做：
struct Node *pol;
// Init code
struct Node *arr = malloc(sizeof *arr * size); // Calculate size before somehow
linkedListToArray(arr, pol);
qsort(arr, size, sizeof *arr, cmp);
struct Node *newPol;
arrayToLinkedList(&newPol, arr);
请注意，我已跳过所有错误检查以保持代码简短。
旧答案。我误解了这个问题，但 OP 提到他们喜欢评论中的答案。下面说的是如何将多项式变成标准形式，但我真正要回答的问题是如何将多项式归一化。
要将其转换为标准规范化形式，您基本上需要做两件事
找到度数最高的词
将所有项除以最高次数项的系数。
在处理多个变量时，确定最高次数的项是不明确的，因为次数只是 Node::powX + Node::powY + Node::powZ。但是在任何情况下，您都需要定义一个函数，该函数采用整个多项式和 returns 根据某些定义具有最高度数的节点。这是一种方法：
int degree(struct Node *term) {
return term->powX + term->powY + term->powZ;
}
struct Node *getTermWithHighestDegree(struct Node *pol) {
struct Node *ret = pol;
while(pol) {
if(degree(pol) > degree(ret)) ret = pol;
pol = pol->next;
}
}
然后简单地做：
void convertToNormalizedForm(struct Node *pol) {
struct Node *term = getTermWithHighestDegree(pol);
int coeff = term->coeff;
while(pol) {
pol->coeff /= coeff;
pol = pol->next;
}
}
但是请注意，您可能 运行 遇到几个问题，因为您将系数存储为整数。您可能想更改为浮点类型。
问题归结为对链表进行排序，为此您需要一个合适的比较函数来确定列表中两个术语的排序顺序：
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;
}
（如果所有指数都相等，则将#if 0更改为#if 1以比较系数。）
函数returns如果第一项的阶数低于第二项则为-1，如果第一项的阶数高于第二项则为1，如果它们的阶数相同则为0。
函数可以使用比较函数对术语列表进行排序。为简单起见，交换排序如下所示：
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;
}
}
排序功能可以这样使用：
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);
}
sortPolynomialTerms和canonicalPolynomial的参数是struct Node **poly，因为它们可能会修改指向初始项的指针*poly以指向不同的初始项。
奖励内容
短多项式可能不值得，但对于包含许多要排序的项的多项式，合并排序将比上面实现的交换排序更有效。基于 Simon Tatham 的示例代码“listsort.c" for the page "Mergesort For Linked Lists”，sortPolynomialTerms 的以下版本使用自下而上的归并排序：
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;
}