c - 使用基于指针的链表计算多项式和时指针分配中的逻辑错误

Question

我正在尝试编写一个程序，使用指针和链表在 C 中执行两个多项式的加法。看起来像这样:

ideone.com 上的实时代码.

1    #include<stdio.h>
2    #include<malloc.h>
3    
4    typedef struct PolyTerm PolyTerm;
5    
6    struct PolyTerm
7    {
8       int coeff;
9       int exp;
10      PolyTerm *next;
11    };
12    
13    void printPoly(PolyTerm *pPoly)
14    {
15      if(pPoly == NULL)
16      {
17          printf("\n");
18          return;
19      }
20      printf("%de%d",pPoly->coeff,pPoly->exp);
21      if(pPoly->next != NULL)
22          printf(" + ");
23      printPoly(pPoly->next);
24    }
25    
26    void printPolyTerm(PolyTerm *pPoly)
27    {
28      if(pPoly != NULL)
29          printf("%de%d",pPoly->coeff,pPoly->exp);
30    }
31    
32    void createPolyTerm(int pCoeff, int pExp, PolyTerm **pPoly)
33    {
34      PolyTerm *tempPolyTerm;
35      if(*pPoly == NULL)
36      {
37          tempPolyTerm = (PolyTerm *)malloc(sizeof(PolyTerm));
38          tempPolyTerm -> coeff = pCoeff;
39          tempPolyTerm -> exp = pExp;
40          
41          *pPoly = tempPolyTerm;
42      }
43      else
44      {
45          (*pPoly)->coeff = pCoeff;   
46          (*pPoly)->exp = pExp;
47          (*pPoly)->next = (PolyTerm *)malloc(sizeof(PolyTerm));
48          (*pPoly)->next->next = NULL;
49      }
50    }
51    
52    void addPoly(PolyTerm **pFirstPoly,PolyTerm **pSecondPoly, PolyTerm **sumPoly)
53    {
54      PolyTerm *sumPolyIterator = *sumPoly;
55      PolyTerm *sumPolyIteratorParent = *sumPoly;
56      PolyTerm *firstPolyCurrentTerm = *pFirstPoly;
57      PolyTerm *secondPolyIterator = *pSecondPoly;
58      
59      while(firstPolyCurrentTerm != NULL)
60      {
61          //find if current exp exist in sumPoly
62          while(sumPolyIterator != NULL)
63          {
64              printf("-Sum: ");       
65              printPoly(*sumPoly);   //in last iteration, prints 6e0 + 9e1
66              printf("inner while 1\n");
67              printf("sumPolyIterator:%de%d\n",sumPolyIterator->coeff,sumPolyIterator->exp);
68              *sumPolyIteratorParent = *sumPolyIterator;
69              if(sumPolyIterator->exp == firstPolyCurrentTerm->exp)
70                  break;
71              sumPolyIterator = sumPolyIterator->next;
72              printf("-Sum: ");
73              printPoly(*sumPoly);   //in last iteration, prints 9e1, where did 6e0 went?
74          }
75          
76          if(sumPolyIterator == NULL)
77          {
78              //if the exp is not present in sum yet, create it
79              sumPolyIterator = (PolyTerm *)malloc(sizeof(PolyTerm)); 
80              sumPolyIteratorParent->next = sumPolyIterator;
81          }
82          
83          sumPolyIterator->exp += firstPolyCurrentTerm->exp;
84          sumPolyIterator->coeff = firstPolyCurrentTerm->coeff;
85          
86          //iterate through second polynomial to find all terms with same exp
87          while(secondPolyIterator != NULL)
88          {
89              if(secondPolyIterator->exp == firstPolyCurrentTerm->exp)
90              {
91                  sumPolyIterator->coeff += secondPolyIterator->coeff;
92              }
93              secondPolyIterator = secondPolyIterator->next;
94          }
95          
96          //reset to first term
97          sumPolyIterator = *sumPoly;
98          secondPolyIterator = *pSecondPoly;
99          
100         firstPolyCurrentTerm = firstPolyCurrentTerm->next;
101     }
102    }
103    
104    void main()
105    {
106     PolyTerm *firstPolyTerm = NULL;   
107     createPolyTerm(1,0,&firstPolyTerm);
108     createPolyTerm(2,1,&(firstPolyTerm->next));           
109     createPolyTerm(3,2,&(firstPolyTerm->next->next));
110     
111     PolyTerm *secondPolyTerm = NULL;
112     createPolyTerm(5,0,&secondPolyTerm);
113     createPolyTerm(7,1,&(secondPolyTerm->next));           
114     createPolyTerm(9,2,&(secondPolyTerm->next->next));
115     
116     PolyTerm *sumPolyFirstTerm = (PolyTerm *)malloc(sizeof(PolyTerm));
117     PolyTerm **sumPoly = &sumPolyFirstTerm;
118     addPoly(&firstPolyTerm,&secondPolyTerm,&sumPolyFirstTerm);
119     
120     printPoly(firstPolyTerm);
121     printPoly(secondPolyTerm);
122     printPoly(sumPolyFirstTerm);
123    }

输出为:

-Sum: 0e0
inner while 1
sumPolyIterator:0e0
-Sum: 6e0
inner while 1
sumPolyIterator:6e0
-Sum: 6e0
-Sum: 6e0 + 9e1
inner while 1
sumPolyIterator:6e0
-Sum: 6e0 + 9e1
-Sum: 6e0 + 9e1
inner while 1
sumPolyIterator:9e1
-Sum: 9e1
1e0 + 2e1 + 3e2
5e0 + 7e1 + 9e2
9e1 + 12e2

两个多项式 1e0 + 2e1 + 3e2 和 5e0 + 7e1 + 9e2 的总和为 6e0+9e1+12e2。但是，在最后一行它打印 9e1 + 12e2。似乎第一项 6e0 在某些指针分配中丢失了。所以我尝试将 printf 语句放在前缀 -Sum 中。正如您在输出中看到的，以 -Sum 为前缀的最后一行是 -Sum: 9e1，而以 -Sum 为前缀的倒数第二行> 是 -Sum: 6e0 + 9e1。所以这似乎是第一个术语 6e0 丢失的地方。我已经对代码进行了注释，指出这些 -Sum 前缀行的打印位置(它在 addPoly() 方法中的第一个内部 while 循环，第 65 行和 73 行)，但我是无法理解为什么会发生这种情况。

Answer 1

首先，由于使用了未初始化的数据，您的程序无法开箱即用。它偶然在 ideone 上工作，但在一般情况下它一定会像在我的系统上那样失败。示例:在 createPolyTerm 中，您创建了 tempPolyTerm，其中字段 next 根本没有初始化，因此它包含垃圾。但是，您将继续，就像将 next 设置为 NULL 一样。又如:sumPolyFirstTerm是通过malloc分配缓冲区创建的，没有初始化任何成员。但是，在 addPoly 中，您将其传递到 printPoly 中，期望在 next 字段中出现 NULL。

如果您依赖于分配时缓冲区数据始终设置为零，请使用 calloc而不是 malloc，至少这是让你的程序在我的系统上运行的方法。

好吧，回到你的麻烦。看起来以下字符串包含错误

*sumPolyIteratorParent = *sumPolyIterator;

您可能希望将父迭代器指向基迭代器的当前位置，但您使用了取消引用并更新了 PolyTerm 本身，而不是更改迭代器。使用这个替换程序看起来工作正常:

sumPolyIteratorParent = sumPolyIterator;