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 that you have read and understand our privacy policy and code of conduct.

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