假设我有一个包含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 exponenty exponentz exponentcoefficient。示例：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("%dn", &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 %dn", 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 %.3fn", 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;
}
问题归结为对链表进行排序，为此您需要一个合适的比较函数来确定列表上两个项的排序顺序：
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以比较系数。(
如果第一个项的阶数低于第二个项，则函数返回-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 %.3fn", 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的指针以指向不同的初始项。
奖金含量
对于短多项式来说，这可能不值得，但对于包含许多待排序项的多项式，合并排序将比上面实现的交换排序更有效。基于样本代码"；listsort.c"；对于页面"；"为链接列表合并排序"；由Simon Tatham编写，以下版本的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;
}
对链表进行排序的最简单方法是将其转换为常规列表，使用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。但在任何情况下，您都需要定义一个函数，该函数采用整个多项式，并根据某些定义返回具有最高次数的节点。这里有一种方法：
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;
}
}
但是，请注意，您可能会遇到一些问题，因为您将系数存储为整数。您可能需要更改为浮点类型。