在 C 中用链表显示多项式
Displaying polynomials with linked list in C
我正在尝试编写代码来创建和显示多项式。我的第一个问题是：“我是否正确使用链表？”。第二个是：“为什么我不能显示多项式？”我希望它们显示为：如果有 2 个单项式，多项式应显示为； -->(1.0 X 0) -->(1.0 X 3)--E 第一个是系数，第二个是指数。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//this will be the structure named node
struct node
{
int exp; //this line represents the exponent/power b for a*x^b
int coeff; //this line represents the coefficient a for a*x^b
struct node *next; //this line represents the pointer which will point to the next node
};
struct node *create_new_nodes(struct node *m);
struct node *insert(struct node *ptr, struct node *k);
void display(char const *tag, struct node *ptr);
struct node *create_new_nodes(struct node *m)
{
int i;
int n;
printf("Enter the number of nodes: ");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
struct node *ptr = malloc(sizeof(struct node));
printf("Enter the coefficient (a for a*x^b): ");
scanf("%d", &ptr->coeff);
printf("Enter the exponent/power (b for a*x^b): ");
scanf("%d", &ptr->exp);
ptr->next = NULL;
}
return m;
}
void display(char const *tag, struct node *ptr)
{
struct node *temp;
temp = ptr;
printf("%s: ", tag);
while (temp != NULL)
{
printf("-->(%d X %d)--E", temp->coeff, temp->exp);
temp = temp->next;
}
putchar('\n');
}
int main(void)
{
struct node *p1 = NULL, *p2 = NULL;
p1 = create_new_nodes(p1);
p2 = create_new_nodes(p2);
display("p1", p1);
display("p2", p2);
return 0;
}
这段代码的输出：
Enter the number of nodes: 2
Enter the coefficient (a for a*x^b): 1
Enter the exponent/power (b for a*x^b): 2
Enter the coefficient (a for a*x^b): 2
Enter the exponent/power (b for a*x^b): 3
Enter the number of nodes: 2
Enter the coefficient (a for a*x^b): 3
Enter the exponent/power (b for a*x^b): 4
Enter the coefficient (a for a*x^b): 6
Enter the exponent/power (b for a*x^b): 5
p1:
p2:
如您所见，p1 和 p2 未显示。
我不得不提一下，我在编写这段代码的某些部分时从互联网上获得了帮助。所以，有些部分我不明白。如果可能的话，我也想澄清一下。
void display(char const *tag, struct node *ptr)
{
struct node *temp;
const char *pad;
temp = ptr;
printf("%s: ", tag);
while (temp != NULL)
{
printf("-->(%d X %d)--E", temp->coeff, temp->exp);
temp = temp->next;
pad = " + ";
}
putchar('\n');
}
在这部分代码中，我没有明白为什么要使用temp和tag函数。
我可能错了，但在函数中
struct node *create_new_nodes(struct node *m)
看起来return类型和参数都是指针。所以说真的，你 returning
struct node **m
不确定这是否是问题所在，但如果是，当您这样做时可能会出现同样的问题
printf("-->(%d X %d)--E", temp->coeff, temp->exp);
当 temp 是 ptr 即 struct node*。所以你真的是在说 (**node).coeff。但这只是我累的观察，如果有效请忽略我。
让我们帮你解决。您不需要完整的通用 linked-list 实现，您只需要创建、显示和删除功能。由于您的列表只是 link 个具有 exp 和 coeff 的结构，您可以在每次调用创建函数时简单地构建一个新列表。您不需要为创建函数提供参数，只需声明该函数的本地列表指针，然后 return 完成后指向分配列表中第一个节点的指针。
如评论中所述，除非您 检查 return使用的输入函数（未提及，但同样重要，检查每个分配的 return）
您与创建函数的目标相去不远，只是您从未 link 将列表中的节点放在一起。您确实希望在分配后初始化 next 指针 NULL，但您还必须将列表中任何现有的结束节点 next 指针设置为指向新节点。这就是您在“linked-list”中创建“link”的方式。
让我们使用您的创建函数（我已将其重命名为 create_poly_list()），基本上您可以声明函数本地的 head 和 tail 列表指针（tail 指针临时用于构建列表），然后 return head 完成后在调用方返回赋值（此处为 main() ）。所以你真正需要的只是声明你的列表指针，然后按顺序添加每个节点，例如
struct node *head = NULL, *tail = NULL; /* temporary list pointers */
...
if (head == NULL) /* add first node */
head = tail = ptr;
else {
tail->next = ptr; /* set last node ->next to new node */
tail = ptr; /* update tail to new node */
}
...
return head; /* return pointer to start of list */
然后在 main() 中，您只需为每个多项式调用 create_poly_list()，例如
p1 = create_poly_list();
p2 = create_poly_list();
现在让我们整理一下，以便您验证每个输入和分配，returning NULL 输入或分配失败（如果分配了内存，请记住 free() 所有内存在防止内存泄漏失败之前），例如
struct node *create_poly_list (void) /* no parameter required */
{
int i, n;
struct node *head = NULL, *tail = NULL; /* temporary list pointers */
fputs ("\nEnter the number of nodes: ", stdout);
if (scanf("%d", &n) != 1)
return NULL;
for (i = 0; i < n; i++)
{
struct node *ptr = malloc (sizeof *ptr);
if (!ptr) { /* validate EVERY allocation */
while (head) { /* if nodes in list */
struct node *victim = head; /* free all nodes (or leak) */
head = head->next;
free (victim);
}
return NULL; /* now return NULL on error */
}
ptr->next = NULL; /* initialize next ptr NULL */
fputs ("\nEnter the coefficient (a for a*x^b) : ", stdout);
if (scanf ("%d", &ptr->coeff) != 1) {
fputs ("error: invalid integer input.\n", stderr);
/* you would likewise need to free prior nodes here */
return NULL;
}
fputs ("Enter the exponent/power (b for a*x^b): ", stdout);
if (scanf("%d", &ptr->exp) != 1) {
fputs ("error: invalid integer input.\n", stderr);
/* you would likewise need to free prior nodes here */
return NULL;
}
if (head == NULL) /* add first node */
head = tail = ptr;
else {
tail->next = ptr; /* set last node ->next to new node */
tail = ptr; /* update tail to new node */
}
}
return head; /* return pointer to start of list */
}
您的 display() 功能很好，但您应该检查 ptr 是否为 NULL（例如，列表为空）以在尝试时通知用户列表状态显示空列表，例如
void display (char const *tag, struct node *ptr)
{
if (!ptr) { /* validate list not NULL */
puts ("(list-empty)");
return;
}
struct node *temp = ptr;
printf("%s: ", tag);
while (temp) {
printf("-->(%d X %d)--E", temp->coeff, temp->exp);
temp = temp->next;
}
putchar('\n');
}
这里需要在每个列表用完后释放内存。 （是的，内存将在程序退出时释放，但大概您不会总是编写在 main() 中创建所有列表的简单程序）。尽早养成良好的内存管理习惯。您只需要一个简单的删除列表功能，例如
void del_list (struct node *list)
{
while (list) {
struct node *victim = list;
list = list->next;
free (victim);
}
}
总而言之，您将拥有：
#include <stdio.h>
#include <stdlib.h>
struct node {
int exp;
int coeff;
struct node *next;
};
struct node *create_poly_list (void) /* no parameter required */
{
int i, n;
struct node *head = NULL, *tail = NULL; /* temporary list pointers */
fputs ("\nEnter the number of nodes: ", stdout);
if (scanf("%d", &n) != 1)
return NULL;
for (i = 0; i < n; i++)
{
struct node *ptr = malloc (sizeof *ptr);
if (!ptr) { /* validate EVERY allocation */
while (head) { /* if nodes in list */
struct node *victim = head; /* free all nodes (or leak) */
head = head->next;
free (victim);
}
return NULL; /* now return NULL on error */
}
ptr->next = NULL; /* initialize next ptr NULL */
fputs ("\nEnter the coefficient (a for a*x^b) : ", stdout);
if (scanf ("%d", &ptr->coeff) != 1) {
fputs ("error: invalid integer input.\n", stderr);
/* you would likewise need to free prior nodes here */
return NULL;
}
fputs ("Enter the exponent/power (b for a*x^b): ", stdout);
if (scanf("%d", &ptr->exp) != 1) {
fputs ("error: invalid integer input.\n", stderr);
/* you would likewise need to free prior nodes here */
return NULL;
}
if (head == NULL) /* add first node */
head = tail = ptr;
else {
tail->next = ptr; /* set last node ->next to new node */
tail = ptr; /* update tail to new node */
}
}
return head; /* return pointer to start of list */
}
void display (char const *tag, struct node *ptr)
{
if (!ptr) { /* validate list not NULL */
puts ("(list-empty)");
return;
}
struct node *temp = ptr;
printf("%s: ", tag);
while (temp) {
printf("-->(%d X %d)--E", temp->coeff, temp->exp);
temp = temp->next;
}
putchar('\n');
}
void del_list (struct node *list)
{
while (list) {
struct node *victim = list;
list = list->next;
free (victim);
}
}
int main(void)
{
struct node *p1 = NULL, *p2 = NULL;
p1 = create_poly_list();
p2 = create_poly_list();
putchar ('\n');
display("p1", p1);
display("p2", p2);
del_list (p1);
del_list (p2);
return 0;
}
(注意:为什么你把string.h包括进来有点令人困惑...)
例子Use/Output
$ ./bin/poly_list
Enter the number of nodes: 2
Enter the coefficient (a for a*x^b) : 2
Enter the exponent/power (b for a*x^b): 6
Enter the coefficient (a for a*x^b) : 3
Enter the exponent/power (b for a*x^b): 7
Enter the number of nodes: 3
Enter the coefficient (a for a*x^b) : 1
Enter the exponent/power (b for a*x^b): 3
Enter the coefficient (a for a*x^b) : 3
Enter the exponent/power (b for a*x^b): 5
Enter the coefficient (a for a*x^b) : 5
Enter the exponent/power (b for a*x^b): 7
p1: -->(2 X 6)--E-->(3 X 7)--E
p2: -->(1 X 3)--E-->(3 X 5)--E-->(5 X 7)--E
内存Use/Error检查
在您编写的任何动态分配内存的代码中，您对分配的任何内存块负有 2 责任：(1) 始终保留指向内存块的起始地址，因此，(2) 当不再需要它时可以释放。
您必须使用内存错误检查程序来确保您不会尝试访问内存或写入 beyond/outside 您分配的块的边界，尝试读取或基于未初始化的条件跳转值，最后，确认您释放了所有已分配的内存。
对于Linux valgrind是正常的选择。每个平台都有类似的内存检查器。它们都很简单易用，只需运行你的程序就可以了。
$ valgrind ./bin/poly_list
==23402== Memcheck, a memory error detector
==23402== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==23402== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==23402== Command: ./bin/poly_list
==23402==
Enter the number of nodes: 2
Enter the coefficient (a for a*x^b) : 2
Enter the exponent/power (b for a*x^b): 6
Enter the coefficient (a for a*x^b) : 3
Enter the exponent/power (b for a*x^b): 7
Enter the number of nodes: 3
Enter the coefficient (a for a*x^b) : 1
Enter the exponent/power (b for a*x^b): 3
Enter the coefficient (a for a*x^b) : 3
Enter the exponent/power (b for a*x^b): 5
Enter the coefficient (a for a*x^b) : 5
Enter the exponent/power (b for a*x^b): 7
p1: -->(2 X 6)--E-->(3 X 7)--E
p2: -->(1 X 3)--E-->(3 X 5)--E-->(5 X 7)--E
==23402==
==23402== HEAP SUMMARY:
==23402== in use at exit: 0 bytes in 0 blocks
==23402== total heap usage: 7 allocs, 7 frees, 2,128 bytes allocated
==23402==
==23402== All heap blocks were freed -- no leaks are possible
==23402==
==23402== For counts of detected and suppressed errors, rerun with: -v
==23402== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
始终确认您已释放所有分配的内存并且没有内存错误。
检查一下，如果您还有其他问题，请告诉我。
我正在尝试编写代码来创建和显示多项式。我的第一个问题是：“我是否正确使用链表？”。第二个是：“为什么我不能显示多项式？”我希望它们显示为：如果有 2 个单项式，多项式应显示为； -->(1.0 X 0) -->(1.0 X 3)--E 第一个是系数，第二个是指数。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//this will be the structure named node
struct node
{
int exp; //this line represents the exponent/power b for a*x^b
int coeff; //this line represents the coefficient a for a*x^b
struct node *next; //this line represents the pointer which will point to the next node
};
struct node *create_new_nodes(struct node *m);
struct node *insert(struct node *ptr, struct node *k);
void display(char const *tag, struct node *ptr);
struct node *create_new_nodes(struct node *m)
{
int i;
int n;
printf("Enter the number of nodes: ");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
struct node *ptr = malloc(sizeof(struct node));
printf("Enter the coefficient (a for a*x^b): ");
scanf("%d", &ptr->coeff);
printf("Enter the exponent/power (b for a*x^b): ");
scanf("%d", &ptr->exp);
ptr->next = NULL;
}
return m;
}
void display(char const *tag, struct node *ptr)
{
struct node *temp;
temp = ptr;
printf("%s: ", tag);
while (temp != NULL)
{
printf("-->(%d X %d)--E", temp->coeff, temp->exp);
temp = temp->next;
}
putchar('\n');
}
int main(void)
{
struct node *p1 = NULL, *p2 = NULL;
p1 = create_new_nodes(p1);
p2 = create_new_nodes(p2);
display("p1", p1);
display("p2", p2);
return 0;
}
这段代码的输出：
Enter the number of nodes: 2
Enter the coefficient (a for a*x^b): 1
Enter the exponent/power (b for a*x^b): 2
Enter the coefficient (a for a*x^b): 2
Enter the exponent/power (b for a*x^b): 3
Enter the number of nodes: 2
Enter the coefficient (a for a*x^b): 3
Enter the exponent/power (b for a*x^b): 4
Enter the coefficient (a for a*x^b): 6
Enter the exponent/power (b for a*x^b): 5
p1:
p2:
如您所见，p1 和 p2 未显示。
我不得不提一下，我在编写这段代码的某些部分时从互联网上获得了帮助。所以，有些部分我不明白。如果可能的话，我也想澄清一下。
void display(char const *tag, struct node *ptr)
{
struct node *temp;
const char *pad;
temp = ptr;
printf("%s: ", tag);
while (temp != NULL)
{
printf("-->(%d X %d)--E", temp->coeff, temp->exp);
temp = temp->next;
pad = " + ";
}
putchar('\n');
}
在这部分代码中，我没有明白为什么要使用temp和tag函数。
我可能错了，但在函数中
struct node *create_new_nodes(struct node *m)
看起来return类型和参数都是指针。所以说真的，你 returning
struct node **m
不确定这是否是问题所在，但如果是，当您这样做时可能会出现同样的问题
printf("-->(%d X %d)--E", temp->coeff, temp->exp);
当 temp 是 ptr 即 struct node*。所以你真的是在说 (**node).coeff。但这只是我累的观察，如果有效请忽略我。
让我们帮你解决。您不需要完整的通用 linked-list 实现，您只需要创建、显示和删除功能。由于您的列表只是 link 个具有 exp 和 coeff 的结构，您可以在每次调用创建函数时简单地构建一个新列表。您不需要为创建函数提供参数，只需声明该函数的本地列表指针，然后 return 完成后指向分配列表中第一个节点的指针。
如评论中所述，除非您 检查 return使用的输入函数（未提及，但同样重要，检查每个分配的 return）
您与创建函数的目标相去不远，只是您从未 link 将列表中的节点放在一起。您确实希望在分配后初始化 next 指针 NULL，但您还必须将列表中任何现有的结束节点 next 指针设置为指向新节点。这就是您在“linked-list”中创建“link”的方式。
让我们使用您的创建函数（我已将其重命名为 create_poly_list()），基本上您可以声明函数本地的 head 和 tail 列表指针（tail 指针临时用于构建列表），然后 return head 完成后在调用方返回赋值（此处为 main() ）。所以你真正需要的只是声明你的列表指针，然后按顺序添加每个节点，例如
struct node *head = NULL, *tail = NULL; /* temporary list pointers */
...
if (head == NULL) /* add first node */
head = tail = ptr;
else {
tail->next = ptr; /* set last node ->next to new node */
tail = ptr; /* update tail to new node */
}
...
return head; /* return pointer to start of list */
然后在 main() 中，您只需为每个多项式调用 create_poly_list()，例如
p1 = create_poly_list();
p2 = create_poly_list();
现在让我们整理一下，以便您验证每个输入和分配，returning NULL 输入或分配失败（如果分配了内存，请记住 free() 所有内存在防止内存泄漏失败之前），例如
struct node *create_poly_list (void) /* no parameter required */
{
int i, n;
struct node *head = NULL, *tail = NULL; /* temporary list pointers */
fputs ("\nEnter the number of nodes: ", stdout);
if (scanf("%d", &n) != 1)
return NULL;
for (i = 0; i < n; i++)
{
struct node *ptr = malloc (sizeof *ptr);
if (!ptr) { /* validate EVERY allocation */
while (head) { /* if nodes in list */
struct node *victim = head; /* free all nodes (or leak) */
head = head->next;
free (victim);
}
return NULL; /* now return NULL on error */
}
ptr->next = NULL; /* initialize next ptr NULL */
fputs ("\nEnter the coefficient (a for a*x^b) : ", stdout);
if (scanf ("%d", &ptr->coeff) != 1) {
fputs ("error: invalid integer input.\n", stderr);
/* you would likewise need to free prior nodes here */
return NULL;
}
fputs ("Enter the exponent/power (b for a*x^b): ", stdout);
if (scanf("%d", &ptr->exp) != 1) {
fputs ("error: invalid integer input.\n", stderr);
/* you would likewise need to free prior nodes here */
return NULL;
}
if (head == NULL) /* add first node */
head = tail = ptr;
else {
tail->next = ptr; /* set last node ->next to new node */
tail = ptr; /* update tail to new node */
}
}
return head; /* return pointer to start of list */
}
您的 display() 功能很好，但您应该检查 ptr 是否为 NULL（例如，列表为空）以在尝试时通知用户列表状态显示空列表，例如
void display (char const *tag, struct node *ptr)
{
if (!ptr) { /* validate list not NULL */
puts ("(list-empty)");
return;
}
struct node *temp = ptr;
printf("%s: ", tag);
while (temp) {
printf("-->(%d X %d)--E", temp->coeff, temp->exp);
temp = temp->next;
}
putchar('\n');
}
这里需要在每个列表用完后释放内存。 （是的，内存将在程序退出时释放，但大概您不会总是编写在 main() 中创建所有列表的简单程序）。尽早养成良好的内存管理习惯。您只需要一个简单的删除列表功能，例如
void del_list (struct node *list)
{
while (list) {
struct node *victim = list;
list = list->next;
free (victim);
}
}
总而言之，您将拥有：
#include <stdio.h>
#include <stdlib.h>
struct node {
int exp;
int coeff;
struct node *next;
};
struct node *create_poly_list (void) /* no parameter required */
{
int i, n;
struct node *head = NULL, *tail = NULL; /* temporary list pointers */
fputs ("\nEnter the number of nodes: ", stdout);
if (scanf("%d", &n) != 1)
return NULL;
for (i = 0; i < n; i++)
{
struct node *ptr = malloc (sizeof *ptr);
if (!ptr) { /* validate EVERY allocation */
while (head) { /* if nodes in list */
struct node *victim = head; /* free all nodes (or leak) */
head = head->next;
free (victim);
}
return NULL; /* now return NULL on error */
}
ptr->next = NULL; /* initialize next ptr NULL */
fputs ("\nEnter the coefficient (a for a*x^b) : ", stdout);
if (scanf ("%d", &ptr->coeff) != 1) {
fputs ("error: invalid integer input.\n", stderr);
/* you would likewise need to free prior nodes here */
return NULL;
}
fputs ("Enter the exponent/power (b for a*x^b): ", stdout);
if (scanf("%d", &ptr->exp) != 1) {
fputs ("error: invalid integer input.\n", stderr);
/* you would likewise need to free prior nodes here */
return NULL;
}
if (head == NULL) /* add first node */
head = tail = ptr;
else {
tail->next = ptr; /* set last node ->next to new node */
tail = ptr; /* update tail to new node */
}
}
return head; /* return pointer to start of list */
}
void display (char const *tag, struct node *ptr)
{
if (!ptr) { /* validate list not NULL */
puts ("(list-empty)");
return;
}
struct node *temp = ptr;
printf("%s: ", tag);
while (temp) {
printf("-->(%d X %d)--E", temp->coeff, temp->exp);
temp = temp->next;
}
putchar('\n');
}
void del_list (struct node *list)
{
while (list) {
struct node *victim = list;
list = list->next;
free (victim);
}
}
int main(void)
{
struct node *p1 = NULL, *p2 = NULL;
p1 = create_poly_list();
p2 = create_poly_list();
putchar ('\n');
display("p1", p1);
display("p2", p2);
del_list (p1);
del_list (p2);
return 0;
}
(注意:为什么你把string.h包括进来有点令人困惑...)
例子Use/Output
$ ./bin/poly_list
Enter the number of nodes: 2
Enter the coefficient (a for a*x^b) : 2
Enter the exponent/power (b for a*x^b): 6
Enter the coefficient (a for a*x^b) : 3
Enter the exponent/power (b for a*x^b): 7
Enter the number of nodes: 3
Enter the coefficient (a for a*x^b) : 1
Enter the exponent/power (b for a*x^b): 3
Enter the coefficient (a for a*x^b) : 3
Enter the exponent/power (b for a*x^b): 5
Enter the coefficient (a for a*x^b) : 5
Enter the exponent/power (b for a*x^b): 7
p1: -->(2 X 6)--E-->(3 X 7)--E
p2: -->(1 X 3)--E-->(3 X 5)--E-->(5 X 7)--E
内存Use/Error检查
在您编写的任何动态分配内存的代码中，您对分配的任何内存块负有 2 责任：(1) 始终保留指向内存块的起始地址，因此，(2) 当不再需要它时可以释放。
您必须使用内存错误检查程序来确保您不会尝试访问内存或写入 beyond/outside 您分配的块的边界，尝试读取或基于未初始化的条件跳转值，最后，确认您释放了所有已分配的内存。
对于Linux valgrind是正常的选择。每个平台都有类似的内存检查器。它们都很简单易用，只需运行你的程序就可以了。
$ valgrind ./bin/poly_list
==23402== Memcheck, a memory error detector
==23402== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==23402== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==23402== Command: ./bin/poly_list
==23402==
Enter the number of nodes: 2
Enter the coefficient (a for a*x^b) : 2
Enter the exponent/power (b for a*x^b): 6
Enter the coefficient (a for a*x^b) : 3
Enter the exponent/power (b for a*x^b): 7
Enter the number of nodes: 3
Enter the coefficient (a for a*x^b) : 1
Enter the exponent/power (b for a*x^b): 3
Enter the coefficient (a for a*x^b) : 3
Enter the exponent/power (b for a*x^b): 5
Enter the coefficient (a for a*x^b) : 5
Enter the exponent/power (b for a*x^b): 7
p1: -->(2 X 6)--E-->(3 X 7)--E
p2: -->(1 X 3)--E-->(3 X 5)--E-->(5 X 7)--E
==23402==
==23402== HEAP SUMMARY:
==23402== in use at exit: 0 bytes in 0 blocks
==23402== total heap usage: 7 allocs, 7 frees, 2,128 bytes allocated
==23402==
==23402== All heap blocks were freed -- no leaks are possible
==23402==
==23402== For counts of detected and suppressed errors, rerun with: -v
==23402== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
始终确认您已释放所有分配的内存并且没有内存错误。
检查一下，如果您还有其他问题，请告诉我。