0

Получаю ошибку: Exception thrown: read access violation. pos1 was 0xFFFFFFFFFFFFFFFF.. Ошибка выскакивает на строке 137.

Условие задачи: объединить два отсортированных односвязных списка в новый, отсортированный по возрастанию список. (Merge)

Ни как не могу найти место, которое вызывает ошибку,сегодня первый день учу односвязные списки на си.

Заранее большое спасибо всем, кто придет на помощь!

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int val;
    struct Node* next;
} Node;
Node* list_sortedmerge(Node* L1, Node* L2);
void main() {
    Node * L1 = (Node*)malloc(sizeof(Node));
    if (!L1)
    {
        printf("Error! System would not allocate memory.");

        return;
    }
    L1->val = 2;
    Node* pos1 = L1;
    pos1 = pos1->next;
    pos1 = (Node*)malloc(sizeof(Node));
    pos1->val = 4;
    pos1 = pos1->next;
    pos1 = (Node*)malloc(sizeof(Node));
    pos1->val = 6;
    pos1 = pos1->next;
    pos1 = (Node*)malloc(sizeof(Node));
    pos1->val = 8;
    pos1->next = NULL;

    Node * L2 = (Node*)malloc(sizeof(Node));
    if (!L1)
    {
        printf("Error! System would not allocate memory.");

        return;
    }
    L2->val = 3;
    Node* pos2 = L2;
    pos2 = pos2->next;
    pos2 = (Node*)malloc(sizeof(Node));
    pos2->val = 4;
    pos2 = pos2->next;
    pos2 = (Node*)malloc(sizeof(Node));
    pos2->val = 7;
    pos2->next = NULL;
    Node* L3;
    L3 = list_sortedmerge(L1, L2);
    Node* pos3 = L3;
    while (pos3) {
        printf("%d",pos3->val);
        pos3 = pos3->next;
    }

}

Node* list_sortedmerge(Node* L1,Node* L2) {
    Node* pos1 = L1;
    Node* pos2 = L2;
    Node* head3=NULL;
    Node* pos3;
    //if L1 is NUll
    if (!L1)return head3 = L2;
    if (!L2)return head3 = L1;
    if (!L1 && !L2)return head3 = NULL;

    if (pos1->val < pos2->val) {
        head3= pos1;
        pos1 = pos1->next;
    }
    if (pos1->val > pos2->val) {
        head3 = pos2;
        pos2 = pos2->next;
    }
    pos3 = head3;
    while (pos1&&pos2)
    {
        if (pos1->val < pos2->val) {
            pos3->next = pos1;
            pos1 = pos1->next;
        }
        else if (pos1->val > pos2->next) {
            pos3->next = pos2;
            pos2 = pos2->next;
        }
        else {
            pos3->next = pos1;
            pos3 = pos3->next;
            pos3->next = pos2;
        }
        pos3 = pos3->next;
    }
    //if pos1 is not NULL, we copy all elements from position of pos1
    if(pos1)
    {
        pos3->next = pos1;
    }
    //if pos2 is not NULL, we copy all elements from position of pos2
    if (pos2)
    {
        pos3->next = pos2;
        
    }
    return head3;
}

1 ответ 1

1

Ну у вас тут с самого начала нет никакого списка - одни сплошные утечки памяти

void main ()
{
    Node *L1 = (Node *) malloc (sizeof (Node)); // выделяете память
    Node *pos1 = L1; // делаете копию указателя
    pos1 = pos1->next; // а теперь указателю присваиваете мусор, содержащийся в pos1->next
    // в результате выделенная память под объект утекает
    // и так несколько раз
    pos1 = (Node*)malloc(sizeof(Node));
    pos1->val = 4;
    pos1 = pos1->next;

Должно было быть что-то типа

pos1 = L1;
pos2 = (Node*)malloc(sizeof(Node));
pos1->next = pos2;
pos1 = pos2;
pos2 = (Node*)malloc(sizeof(Node));
pos1->next = pos2;

И проверять выделилась ли память нужно после каждого её выделения. Для этого и чтобы код не повторялся, можно сделать через цикл. Инициализацию списков (создание) лучше вынести в отдельную функцию.

int A[]{1, 1, 2, 5, 8, 10};
for(int i=0; i<sizeof(A); i++)
{
   pos2 = (Node*)malloc(sizeof(Node));
   if(!pos2) break; // или return; - проверка выделилась ли память
   pos2->val = A[i];
   pos1->next = pos2;
   pos1 = pos2;
}
pos1->next = NULL;

// или просто с разным шагом в цикле
for(int i=0; i<30; i+=2)
{ 
   .... 
   pos2->val = i;
}

Ну и в функции list_sortedmerge() замечаний достаточно. Третья проверка лишняя - если хоть один из списков пуст, то функция завершится на одной из первых проверок. И head3 - локальная переменная, присваивай ей значение в операторе return - нет смысла.

Node* list_sortedmerge (Node * L1, Node * L2)
{
  if (!L1)
    return head3 = L2; // можно просто return L2;
  if (!L2)
    return head3 = L1; // можно просто return L1;
  if (!L1 && !L2) // до этого условия программа не дойдет - выйдет на первом условии
    return head3 = NULL;  // можно просто return NULL;

Дальше интересно! Если значения у первых элементов списка равны, то вы ничего не делаете! Указатель на результирующий список остается равен NULL а вы его разыменовываете pos3->next = pos1;, что приводит к неопределенному поведению UB, чаще всего - крах программы.

// если значения равны, то ни одно из условий не выполняется  
  if (pos1->val < pos2->val)
    {     }
  if (pos1->val > pos2->val)
    {     }

// надо как-то так
  if (pos1->val < pos2->val)
    {    }
  else
    {    }

Далее двигаясь по спискам элементы объединяются в третий список. Нет необходимости отдельно обрабатывать ситуацию когда элементы равны. Можно сделать также, как в предыдущем фрагменте - а узел с таким же значением из другого списка обработается на следующей итерации цикла. Кроме того, в списках же могут быть одинаковые элементы.

while (pos1 && pos2)
{
    if (pos1->val < pos2->val)
    {
       pos3->next = pos1;
       pos1 = pos1->next;
    }
    else
    {
       pos3->next = pos2;
       pos2 = pos2->next;
    }
    pos3 = pos3->next;
}
2
  • спасибо большое! 21 сен 2022 в 12:39
  • Спасибо здесь - принятый ответ :)
    – DmitryK
    21 сен 2022 в 12:52

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.