Возврат связанного списка из функции приводит к ошибке: «Доступ к участнику по неправильному адресу» происходит в несуществующей строке
У меня проблема в Leetcode: мне нужно добавить два числа из связанного списка, а затем вернуть связанный список из addTwoNumbers.
Подробности раздела об ошибках
Вот мой полный код:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
int findOOM(int num);
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
int valueL1 = 0, valueL2 = 0, valueTotal;
struct ListNode* temp = l1;
int loopNo = 0;
do {
valueL1 += (temp->val) * (10^loopNo);
temp = temp->next;
loopNo++;
} while (temp != NULL);
temp = l2;
loopNo = 0;
do {
valueL2 += (temp->val) * (10^loopNo);
temp = temp->next;
loopNo++;
} while (temp != NULL);
valueTotal = valueL1 + valueL2;
int order = findOOM(valueTotal);
struct ListNode* result = malloc(sizeof(struct ListNode));
temp = result;
int valTemp;
for (int i = 0; i < order; i++) {
valTemp = valueTotal - ((valueTotal /= 10) * 10);
temp->val = valTemp;
if (i != order) {
temp->next = malloc(sizeof(struct ListNode));
temp = temp->next;
}
}
return result;
}
int findOOM(int num) {
int OOM = 0;
while(num > 0) {
OOM++;
num /= 10;
}
return OOM;
}
и сообщение об ошибке гласит: Строка 70: Символ 15: ошибка времени выполнения: доступ к элементу по смещенному адресу 0xbebebebebebebebe для типа «struct ListNode», который требует выравнивания по 8 байтам [ListNode.c] 0xbebebebebebebebe: примечание: здесь указывает указатель
Мой код доходит только до строки 56, однако в сообщениях об ошибках упоминается ошибка в строке 70.
Код, как видно на скриншоте, не компилируется.
Я попытался вернуть функцию с предоставленными связанными списками в качестве входных данных (т. е. l1 и l2), и код компилируется (хотя ответ неверен, разумеется).
Возможно, у кого-нибудь есть идеи, что я сделал не так? Это то, как я неправильно определил свой «результат»?
Вместо того чтобы полагаться на загадочные сообщения об ошибках от онлайн-компиляторов, попробуйте запустить компилятор и отладчик на своем локальном компьютере. Такие инструменты, как valgrind, предоставят вам гораздо более полезную диагностику.
Кроме того, чтобы получить хорошую помощь на этом сайте, вам следует включить минимально воспроизводимый пример, который можно компилировать и запускать как есть. В опубликованном вами фрагменте нет определений типов, заголовков, функций main и т. д.; кто-то, желающий протестировать это, должен будет добавить все эти вещи и, вероятно, просто не станет беспокоиться и перейдет к чужому посту.
Очень дикая догадка: возможно, где-то у вас есть указатель next, который не инициализирован, или вы не установили последний узел, указывающий на NULL. Поскольку вы не предоставили нам часть своего кода, которая инициализирует списки или как вызывается addTwoNumbers, я не могу знать наверняка. Еще одна причина для минимально воспроизводимого примера; люди часто пытаются опубликовать только ту часть кода, которую они считают «релевантной», но очень часто они ошибаются, и ошибка находится в какой-то части кода, которую они не включили. Это просто трата времени всех.
@NateEldredge, возможно, у меня нет основной функции, поскольку это проблема Leetcode, и я предполагаю, что она вызывается для тестовых случаев, предусмотренных проблемой? Вот ссылка на проблему: leetcode.com/problems/add-two-numbers/description
Я не использую Leetcode, но если бы я это делал, у меня был бы свой main() и несколько дополнительных тестовых примеров, чтобы я мог проверить его локально.
Ответы 1
- У вашего алгоритма есть несколько проблем.
- Нам не обязательно использовать
pow(), а^зарезервировано для побитового исключающего ИЛИ в C. - Ваш алгоритм вычисления
valueL1иvalueL2может вызвать переполнение для больших чисел. - Неверный цикл создания результирующего связанного списка.
Алгоритм
Мы создаем дозорный узел и указатель текущего узла, равный дозорному узлу. Это необходимо для создания связанного списка для окончательного результата, чтобы у нас был доступ к заголовку связанного списка.
Мы присваиваем
carryноль и проверяем, являются лиlist1илиlist2NULLили у нас есть ненулевое значениеcarry:- Мы устанавливаем текущий
sumнаcarry. Еслиlist1неNULL, мы добавляем его текущее значение узла кsumи перемещаем указатель на следующий узел. Мы делаем то же самое дляlist2. - Новый керри -
sum / 10. - Мы создаем указатель узла (
p). Мы устанавливаем значениеsum % 10, а следующий узел —NULL. - В конце мы устанавливаем текущий узел на
p.
- Мы устанавливаем текущий
Код
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2) {
struct ListNode sentinel;
struct ListNode *curr = &sentinel;
sentinel.next = NULL;
int carry = 0;
while (l1 != NULL || l2 != NULL || carry != 0) {
int sum = carry;
if (l1 != NULL) {
sum += l1->val;
l1 = l1->next;
}
if (l2 != NULL) {
sum += l2->val;
l2 = l2->next;
}
carry = sum / 10;
struct ListNode *p = (struct ListNode *)malloc(sizeof(struct ListNode));
p->val = sum % 10;
p->next = NULL;
curr->next = p;
curr = p;
}
return sentinel.next;
}
struct ListNode *p(int val) {
struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
node->val = val;
node->next = NULL;
return node;
}
void print_linked_list(struct ListNode *head) {
while (head != NULL) {
printf("%d -> ", head->val);
head = head->next;
}
printf("NULL\n");
}
int main() {
struct ListNode *l1 = p(2);
l1->next = p(4);
l1->next->next = p(3);
struct ListNode *l2 = p(5);
l2->next = p(6);
l2->next->next = p(4);
struct ListNode *res = addTwoNumbers(l1, l2);
print_linked_list(res);
return 0;
}
Принты
7 -> 0 -> 8 -> NULL
Может быть связано, а может и нет, но
10^loopNo— это не возведение в степень в C, это xor. Встроенного оператора для целочисленных степеней нет, поэтому вам придется делать это вручную с повторным умножением. (powпредназначен для чисел с плавающей запятой и не подходит для целых чисел.)