0

Пытаюсь написать программу обхода графа в ширину. При выполнении, после задания вершины начала обхода, программа завершает работу:

Process returned -1073741819 (0xC0000005)

Как это исправить? Проблема, как я думаю, в моей попытке реализации очереди и функций для работы с ней, но в чем конкретно и как это исправить - я понять не могу.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node *next;
} Node;

void adding_to_queue(int peak, Node *queue)
{
    if(queue == NULL){
        queue = (Node*)malloc(sizeof(Node));
        queue->data = peak;
        queue->next = NULL;
    } else {
        Node *cur = queue;
        while(cur->next != NULL){
            cur = cur->next;
        }
        cur->next = (Node*)malloc(sizeof(Node));
        cur->next->data = peak;
        cur->next->next = NULL;
    }
}

int delete_from_queue(Node *queue)
{
    int peak = queue->data;
    if(queue->next != NULL) queue = queue->next;
    else queue = NULL;

    return peak;
}

int is_full(int *numbers_of_peaks, int amount_of_peaks)
{
    int i = 0, result = -1;
    for(i = 0; i < amount_of_peaks; ++i)
    {
        if(numbers_of_peaks[i] != 2) result = 1;
    }
    if(result == -1) result = 0;

    return result;
}

int **adjancency_matrix_creating(int amount_of_peaks)
{
    int i = 0, j = 0;

    int **adjacency_matrix;
    adjacency_matrix = (int**)malloc(amount_of_peaks * sizeof(int*));

    for (i = 0; i < amount_of_peaks; i++)
    {
        adjacency_matrix[i] = (int*)malloc(amount_of_peaks * sizeof(int));
    }

    //заполняем матрицу смежности
    for(i = 0; i < amount_of_peaks; ++i)
    {
        printf("С какими вершинами смежна %d вершина? После введите 0\n", i+1);

        int is_scanf = -1, peak = -1;
    //заполняем смежные вершины
        while(peak)
        {
            is_scanf = scanf("%d", &peak);

            if(is_scanf)
            {
                adjacency_matrix[i][peak-1] = 1;
            }
        }
    //заполняем остальное
        for(j = 0; j < amount_of_peaks; ++j)
        {
            if(adjacency_matrix[i][j] != 1)
            {
                adjacency_matrix[i][j] = 0;
            }
        }
    }
    //вывод матрицы смежности
    printf("\nМатрица смежности:\n");

    for(i = 0; i < amount_of_peaks; ++i)
    {
        for(j = 0; j < amount_of_peaks; ++j)
        {
            printf("%d ", adjacency_matrix[i][j]);
        }
        printf("\n");
    }

    return adjacency_matrix;
}

int main()
{
    //Запрашиваем количество вершин и матрицу смежности
    system("chcp 1251");

    int amount_of_peaks = 0, i = 0, j = 0;

    printf("Сколько вершин в графе? ");
    scanf("%d", &amount_of_peaks);

    int **adjacency_matrix = adjancency_matrix_creating(amount_of_peaks);

    //обход
    Node *queue = NULL;

    int peak_start;
    int *numbers_of_peaks = (int*)malloc(amount_of_peaks * sizeof(int));

    for(i = 0; i < amount_of_peaks; ++i)
    {
        numbers_of_peaks[i] = 0;
    }

    printf("С какой вершины начать обход? ");
    scanf("%d", &peak_start);

    peak_start = peak_start-1;

    adding_to_queue(peak_start, queue);

    numbers_of_peaks[peak_start] = 1;

    int current_peak, checking = -1;

    do
    {
        current_peak = delete_from_queue(queue);

        if(numbers_of_peaks[current_peak] == 1)
        {
            for(i = 0; i < amount_of_peaks; ++i)
            {
                if(adjacency_matrix[current_peak][i] == 1)
                {
                    if(numbers_of_peaks[i] == 0)
                    {
                        adding_to_queue(i, queue);
                        numbers_of_peaks[i] = 1;
                    }
                }
            }
            numbers_of_peaks[current_peak] = 2;
            printf("Обработанная вершина: %d\n", current_peak);

            checking = is_full(numbers_of_peaks, amount_of_peaks);
        }
    } while(checking);

    for(i = amount_of_peaks-1; i >= 0; i--)
    {
        free(adjacency_matrix[i]);
    }

    free(adjacency_matrix);

    return 0;
}
2
  • Функция adding_to_queue никак не возвращает новое значение queue в вызывающий код. Одна и та же ошибка в который раз. ru.stackoverflow.com/questions/607542/… 20 июн 2019 в 22:42
  • Что видно в отладчике?
    – Cerbo
    21 июн 2019 в 11:14

1 ответ 1

0

Намекаем, что передавать очередь нужно по ссылке (т.е. указатель на указатель).

void adding_to_queue(int peak, Node **queue)
{
    if((*queue) == NULL){
        (*queue) = (Node*)malloc(sizeof(Node));
        (*queue)->data = peak;
        (*queue)->next = NULL;
    } else {
        Node *cur = (*queue);

и т.д. Это как раз позволит увидеть изменённый адрес очереди у вызывающей функции.

Но правильнее конечно сделать структуру отдельную:

typedef
struct {
  Node * begin ;
}
MyQueue;

void adding_to_queue(int peak, MyQueue *queue){
   if(queue->begin == NULL){
            queue->begin = (Node*)malloc(sizeof(Node));
            queue->begin->data = peak;
            queue->begin->next = NULL;
        } else {
            Node *cur = queue->begin;
1
  • спасибо, помогло!
    – xingfu
    21 июн 2019 в 18:27

Ваш ответ

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

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