印刷すると、リンクリストから値が削除されます
-
06-07-2019 - |
質問
課題の一部として、2つの関数を作成する必要があります:
- リンクリストとして表される2つの自然数を合計する関数
- 同じ方法で表された数値を出力する関数。
何らかの理由で、両方の関数が個別に完全に正常に機能しますが、合計関数の結果で印刷関数を使用しようとすると、印刷関数の先頭で合計の値が変更され、間違った値。メインでprintfを使用して同じ値を印刷する場合、問題はありません。私のコードは以下に詳述されています。何か案は?
void main()
{
int a[1] = { 1 },
b[1] = { 2 };
int * *pa, **pb;
List lst1, lst2;
List sum;
pa = (int * *) malloc(sizeof(int * )); * pa = &a[0];
pb = (int * *) malloc(sizeof(int * )); * pb = &b[0];
lst1 = arrToList(pa, 1);
lst2 = arrToList(pb, 1);
addNumbers(lst1, lst2, &sum);
//printf("%d\n",*(sum.head->dataPtr));
printNumber(sum);
}
//a function that recieves a number represented ad a list and prints it
void printNumber(List num)
{
ListNode * curr;
int currData,
i,
number;
if (isEmptyList(num) == TRUE)
printf("the input was an empty list, nothing to print");
else
{
i = 0;
number = 0;
curr = num.head;
while (curr != NULL)
{
currData = *(curr - >dataPtr);
number = number + currData * ((int) pow(10, i));
curr = curr - >next;
i++;
}
printf("%d \n", number);
}
}
// a function that sums in list
// representation two numbers,
// each represented as a list
void addNumbers(List n1, List n2, List * sum)
{
ListNode * currN1;
ListNode * currN2;
ListNode * currSum;
int currN1N2Sum; //stores the sum of the current digits in n1 and n2
int carrier,
prevCarrier; //current and previous carriers that carries +1 to the
next digit of sum
if the lst sum was bigger then 9
if ((isEmptyList(n1) == TRUE) || (isEmptyList(n2) == TRUE))
printf("bad input =(");
else
{
currN1 = n1.head;
currN2 = n2.head; * sum = createEmptyList();
carrier = 0;
prevCarrier = 0;
while ((currN1 != NULL) && (currN2 != NULL))
{
currN1N2Sum = *(currN1->dataPtr) + *(currN2->dataPtr) + prevCarrier;
if (currN1N2Sum > 9)
{
carrier = 1;
currN1N2Sum = currN1N2Sum - 10;
}
currSum = creatNewListNode( & currN1N2Sum, NULL);
insertNodeToEnd(sum, currSum);
prevCarrier = carrier;
carrier = 0;
currN1 = currN1 - >next;
currN2 = currN2 - >next;
} //while ((currL1!=NULL)&&(currL2!=NULL))
while (currN1 != NULL)
{
currN1N2Sum = *(currN1 - >dataPtr) + prevCarrier;
currN1 = currN1 - >next;
if (prevCarrier != 0) prevCarrier = 0;
}
while (currN2 != NULL)
{
currN1N2Sum = *(currN2 - >dataPtr) + prevCarrier;
currN2 = currN2 - >next;
if (prevCarrier != 0) prevCarrier = 0;
}
} // ! ((isEmptyList(n1)==TRUE)||(isEmptyList(n2)==TRUE))
}
残りのコードは次のとおりです。
typedef struct listNode{
int* dataPtr;
struct listNode* next;
} ListNode;
typedef struct list
{
ListNode* head;
ListNode* tail;
} List;
List createEmptyList()//creates and returns an empty linked list
{
List res;
res.head = res.tail = NULL;
return res;
}
Bool isEmptyList ( List lst )//checks if a given list is empty or not
{
if (lst.head == NULL && lst.tail == NULL)
return TRUE;
else
return FALSE;
}
void insertDataToEnd ( List * lst, int *dataPtr ) //inserts new data to the end of an existing linked list
{
ListNode * newTail;
newTail = creatNewListNode ( dataPtr, NULL );
insertNodeToEnd(lst,newTail);
}
void insertNodeToEnd ( List * lst, ListNode * newTail )//insert an existing node to an existing linked list
{
if (isEmptyList(*lst) == TRUE )
insertNodeToStart ( lst,newTail );
else
{
(*lst).tail -> next = newTail;
newTail->next = NULL;
(*lst).tail = newTail;
}
}
ListNode * creatNewListNode ( int * dataPtr, ListNode * next )//inserts new node in an existing linked list
{
ListNode * res;
res = (ListNode *) malloc (sizeof(ListNode));
res -> dataPtr = dataPtr;
res -> next = next;
return res;
}
void insertNodeToStart ( List * lst, ListNode * newHead )//inserts node to the begining of a given linked list
{
if ( isEmptyList( *lst ) == TRUE )
{
(*lst).head = newHead;
(*lst).tail = newHead;
newHead -> next = NULL;
}
else
{
newHead -> next = (*lst).head;
(*lst).head = newHead;
}
}
解決
バグは関数addNumbersにあります。 合計を格納するノードを追加するとき、ローカル変数(スタックに格納されている)である変数currN1N2Sumへのポインターを渡します。 addNumbers関数が終了すると、ローカル変数のストレージは解放されます。その場所で見つかった値は変更されないため、ストレージが再利用されない限り、明らかに有効です。
これが、addNumbers関数が正しいという印象を受けた理由です。 printNumber関数を呼び出すと、ストレージが上書きされ、そこに別の値が見つかります。
これはバグを説明しています。
addNumbersには別の問題があります。 2桁の数字を追加しようとすると、currN1N2Sumの内容が新しい値で上書きされます。
すべきことは、バッファ(malloc)を割り当て、currN1N2Sumに含まれる値をそこに格納することです。バッファーへのポインターを新しいノードに渡します。
ところで:(* lst).head in lst-> headを変更できます。コードが読みやすくなります。
他のヒント
ノードを保持するためのデータ構造の定義方法、ノードの追加方法など、さらにコードを確認する必要があります。
次の行が疑わしい:
number=number+currData*((int)pow(10,i));
たとえば、123が1、2、および3ノードとして保存されているとします:
number = 0;
number = 0 + 1 * 1 = 1;
number = 1 + 2 * 10 = 21;
number = 21 + 3 * 100 = 321;
ただし、格納するノードが3、2、および1の場合は、次のようになります。
number = 0;
number = 0 + 3 * 1 = 3;
number = 3 + 2 * 10 = 23;
number = 23 + 1 * 100 = 123;
これはあなたの問題ですか?
createNewListNode()
の実装を見ることなく、これが問題であるかどうかはわかりませんが、次のことを考えてください:
addNumbers()
呼び出しから戻った後、 sum
リスト内の dataPtr
はどこを指しているのですか?
createEmptyListに問題があります。そこでresと呼ばれるリストを宣言し、構造を返しますが、この関数がその構造を返すと、その構造は無効になります。 (構造体の)mallocを使用してから、呼び出し元にポインターを返します。この関数は、最初に* sumで使用します。
これはchmikeが発見したバグと同様のバグなので、両方を修正する方が良いでしょう。
ポインタごとに混乱させているのではないかと思います... addNumbersでリスト「sum」を割り当てる方法は、非常に奇妙に思えます。 (そして、それが物事を壊していても驚かないでしょう...)
これらの変更を行ってください:
メイン:
List *sum;
<...>
addNumbers(lst1,lst2,sum); //Note the absence of the reference operator &
printNumbers(*sum);
(または、(リスト)ではなく(リスト*)を受け入れるようにprintNumbersを変更します)。
XDに役立ったことを願って
編集:
addNumbers()を呼び出す前に「sum」を割り当ててみてください。
lst1 = arrToList(pa, 1);
lst2 = arrToList(pb, 1);
sum = createEmptyList();
データ構造が少し変だと思う:S