在 C 中创建带有链表的多项式

Question

我正在使用 C 中的链表创建多项式，但遇到了问题。有人可以帮我修改我的代码吗？在create函数中，我刚刚创建了一个节点，我想将该节点放置在函数insert中的正确位置，然后我想要多项式p1 被返回。

我也无法理解 return 语句将如何工作。请告诉我我的方法代码中存在哪些错误。

struct node
{
    int cof;
    int exp;
    struct node *link;
};
struct node * create(struct node *q)
 {
  int i,n;
  printf("enter the number of nodes");
  scanf("%d",&n);
  struct node *ptr=(struct node *)malloc (sizeof(struct node));
  for(i=0;i<n;i++)
  {
                  printf("entre the coefficient and exponent respectivly");
                  scanf("%d%d",&ptr->cof,&ptr->exp);
                  ptr->link=NULL;
                  q=insert(ptr,q);
  }
  return q;
 }
struct node * insert(struct node *ptr,struct node *p)
 {
  struct node *temp,*b;
  if(p==NULL)
  p=ptr;
  else
  {
      if((p->exp)<(ptr->exp))
      {
                              ptr->link=p;
                              p=ptr;
      }
      else
      {
          temp=p;
          while((temp!=NULL)||((temp->link->exp)<(ptr->exp)))
          temp=temp->link;
          b=temp->link;
          temp->link=ptr;
          ptr->link=b;
      }
  }
  return p;
  }
void display(struct node *ptr)
 {
   struct node *temp;
  temp=ptr;
  while(temp!=NULL)
  {
                   printf("%d x ^ %d + ",temp->cof,temp->exp);
                   temp=temp->link;
  }
 }

 int main()
  {
  printf("enter the first polynomial");
  struct node *p1=NULL,*p2=NULL; 
  p1=(struct node *)malloc(sizeof(struct node));
  p2=(struct node *)malloc(sizeof(struct node));

  p1=create(p1);

  printf("entr secon dpolynimial");
  create(p2);

  display(p1);
  display(p2);

  getch();
  return 0;
 }

Answer 1

此代码至少适用于某些输入:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node
{
    int cof;
    int exp;
    struct node *link;
};

struct node *create(struct node *q);
struct node *insert(struct node *ptr, struct node *p);
void display(char const *tag, struct node *ptr);
void err_exit(char const *tag);

struct node *create(struct node *q)
{
    int i, n;
    printf("enter the number of nodes: ");
    if (scanf("%d", &n) != 1)
        err_exit("Read error (number of nodes)");
    for (i = 0; i < n; i++)
    {
        struct node *ptr = (struct node *)malloc(sizeof(struct node));
        if (ptr == 0)
            err_exit("Out of memory (1)");
        printf("enter the coefficient and exponent respectively: ");
        if (scanf("%d%d", &ptr->cof, &ptr->exp) != 2)
            err_exit("Read error (coefficient and exponent)");
        ptr->link = NULL;
        q = insert(ptr, q);
        display("after input", q);
    }
    return q;
}

struct node *insert(struct node *ptr, struct node *p)
{
    struct node *temp, *b;
    if (p == NULL)
        p = ptr;
    else
    {
        display("insert: p   = ", p);
        display("insert: ptr = ", ptr);
        if (p->exp < ptr->exp)
        {
            ptr->link = p;
            p = ptr;
        }
        else
        {
            temp = p;
            while ((temp->link != NULL) && (temp->link->exp < ptr->exp))
                display("insert: tmp = ", temp),
                temp = temp->link;
            display("insert: post loop", temp);
            b = temp->link;
            temp->link = ptr;
            ptr->link = b;
        }
    }
    return p;
}

void display(char const *tag, struct node *ptr)
{
    struct node *temp;
    const char *pad = "";
    temp = ptr;
    printf("%s: ", tag);
    while (temp != NULL)
    {
        printf("%s%d x ^ %d", pad, temp->cof, temp->exp);
        temp = temp->link;
        pad = " + ";
    }
    putchar('\n');
}

int main(void)
{
    printf("enter the first polynomial:\n");
    struct node *p1 = NULL, *p2 = NULL;

    p1 = create(p1);

    printf("enter the second polynomial:\n");
    p2 = create(p2);

    display("p1", p1);
    display("p2", p2);

    return 0;
}

void err_exit(char const *tag)
{
    fprintf(stderr, "%s\n", tag);
    exit(1);
}

修复包括:

• 测试 I/O 错误
• 添加标签显示功能
• 大量使用显示功能
• 添加错误退出功能并使用
• 主要修复:正确处理 insert() 中 while 循环中的测试:
  • 测试 temp->link 是否为空
  • 在测试有效性时使用 && 而不是 ||
• 改进 display() 中的打印(仅在分隔两个术语时输出 +；在末尾输出换行符)
• 不要在 main() 中泄漏内存。
• 不要将未初始化的内存传递给 create()。
• 不要忽略 create() 的返回。

运行示例:

enter the first polynomial:
enter the number of nodes: 3
enter the coefficient and exponent respectively: 2 2
after input: 2 x ^ 2
enter the coefficient and exponent respectively: 3 1
insert: p   = : 2 x ^ 2
insert: ptr = : 3 x ^ 1
insert: post loop: 2 x ^ 2
after input: 2 x ^ 2 + 3 x ^ 1
enter the coefficient and exponent respectively: 4 0
insert: p   = : 2 x ^ 2 + 3 x ^ 1
insert: ptr = : 4 x ^ 0
insert: post loop: 2 x ^ 2 + 3 x ^ 1
after input: 2 x ^ 2 + 4 x ^ 0 + 3 x ^ 1
enter the second polynomial:
enter the number of nodes: 5
enter the coefficient and exponent respectively: 1 0
after input: 1 x ^ 0
enter the coefficient and exponent respectively: 2 1
insert: p   = : 1 x ^ 0
insert: ptr = : 2 x ^ 1
after input: 2 x ^ 1 + 1 x ^ 0
enter the coefficient and exponent respectively: 4 6
insert: p   = : 2 x ^ 1 + 1 x ^ 0
insert: ptr = : 4 x ^ 6
after input: 4 x ^ 6 + 2 x ^ 1 + 1 x ^ 0
enter the coefficient and exponent respectively: 3 2
insert: p   = : 4 x ^ 6 + 2 x ^ 1 + 1 x ^ 0
insert: ptr = : 3 x ^ 2
insert: tmp = : 4 x ^ 6 + 2 x ^ 1 + 1 x ^ 0
insert: tmp = : 2 x ^ 1 + 1 x ^ 0
insert: post loop: 1 x ^ 0
after input: 4 x ^ 6 + 2 x ^ 1 + 1 x ^ 0 + 3 x ^ 2
enter the coefficient and exponent respectively: 9 3
insert: p   = : 4 x ^ 6 + 2 x ^ 1 + 1 x ^ 0 + 3 x ^ 2
insert: ptr = : 9 x ^ 3
insert: tmp = : 4 x ^ 6 + 2 x ^ 1 + 1 x ^ 0 + 3 x ^ 2
insert: tmp = : 2 x ^ 1 + 1 x ^ 0 + 3 x ^ 2
insert: tmp = : 1 x ^ 0 + 3 x ^ 2
insert: post loop: 3 x ^ 2
after input: 4 x ^ 6 + 2 x ^ 1 + 1 x ^ 0 + 3 x ^ 2 + 9 x ^ 3
p1: 2 x ^ 2 + 4 x ^ 0 + 3 x ^ 1
p2: 4 x ^ 6 + 2 x ^ 1 + 1 x ^ 0 + 3 x ^ 2 + 9 x ^ 3

有可能认为按指数排序无法正常工作，但代码不会崩溃。使用 valgrind 运行没有发现内存访问错误；不过，它就像众所周知的筛子一样泄漏。