Сортировка слиянием с указателем на массив указателей не работает - PullRequest
Новая
       24

Сортировка слиянием с указателем на массив указателей не работает

2 голосов
/ 02 августа 2020

Здравствуйте, у меня есть эта реализация сортировки слиянием: 

    void merge(Person **arr[], int firstElement, int midElement, int lastElement)
{
    int firstHalfSize = midElement - firstElement + 1;
    int secondHalfSize = lastElement - midElement;
    Person *firstHalfArray[firstHalfSize];
    Person *secondHalfArray[secondHalfSize];

    char *p;
    char *s;

    for (int i = 0; i < firstHalfSize; i++)
    {
        firstHalfArray[i] = *arr[firstElement + i];
    }

    for (int j = 0; j < secondHalfSize; j++)
    {
        secondHalfArray[j] = *arr[midElement + 1+ j];

    }

    int index1 = 0;
    int index2 = 0;
    int mergedArrIndex = firstElement;

    while (index1 < firstHalfSize && index2 < secondHalfSize)
    {

        if ((*firstHalfArray)[index1].id <= (*secondHalfArray)[index2].id)
        {
            arr[mergedArrIndex] = &firstHalfArray[index1];
            index1++;
        }
        else
        {
            arr[mergedArrIndex] = &secondHalfArray[index2];
            index2++;
        }
        mergedArrIndex++;
    }

    while (index1 < firstHalfSize)
    {
        arr[mergedArrIndex] = &firstHalfArray[index1];
        mergedArrIndex++;
        index1++;
    }

    while(index2 < secondHalfSize)
    {
        arr[mergedArrIndex] = &secondHalfArray[index2];
        mergedArrIndex++;
        index2++;
    }
}

void mergeSort(Person **arr, int firstElement, int lastElement)
{
    if (firstElement < lastElement)
    {
        int midElement = (firstElement + lastElement) / 2;
        mergeSort(arr, firstElement, midElement);
        mergeSort(arr, midElement + 1, lastElement);
        merge(&arr, firstElement, midElement, lastElement);

    }
}

И указатель на массив структур, который Person *arrPersons Структура человека выглядит следующим образом: 

typedef struct Person
{
    char name[MAX_LENGTH_LINE];
    long id;
    float age;
} Person;

Я вызываю функцию в основном с помощью: 

mergeSort(&arrPersons, 0, 19);

(у меня есть список из 20 человек), где arrPersons определяется как Person *arrPersons И я пытаюсь отсортировать все этих лиц по их id. Я не понимаю, почему моя сортировка слиянием не работает, я продолжаю получать ошибку сегментации. Спасибо за помощь

Ответы [ 2 ]

2 голосов
/ 02 августа 2020

Использование этого исходного кода: 

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


#define MAX_LENGTH_LINE 50


typedef struct Person
{
    char name[MAX_LENGTH_LINE];
    long id;
    float age;
} Person;
 
 
void merge(Person **arr[], int firstElement, int midElement, int lastElement)
{
    int firstHalfSize  = midElement  - firstElement + 1;
    int secondHalfSize = lastElement - midElement;
    Person *firstHalfArray[firstHalfSize];
    Person *secondHalfArray[secondHalfSize];

    //char *p;
    //char *s;

    for (int i = 0; i < firstHalfSize; i++)
    {
        firstHalfArray[i] = *arr[firstElement + i];
    }

    for (int j = 0; j < secondHalfSize; j++)
    {
        secondHalfArray[j] = *arr[midElement + 1+ j];

    }

    int index1 = 0;
    int index2 = 0;
    int mergedArrIndex = firstElement;

    while (index1 < firstHalfSize && index2 < secondHalfSize)
    {

        if ((*firstHalfArray)[index1].id <= (*secondHalfArray)[index2].id)
        {
            arr[mergedArrIndex] = &firstHalfArray[index1];
            index1++;
        }
        else
        {
            arr[mergedArrIndex] = &secondHalfArray[index2];
            index2++;
        }
        mergedArrIndex++;
    }

    while (index1 < firstHalfSize)
    {
        arr[mergedArrIndex] = &firstHalfArray[index1];
        mergedArrIndex++;
        index1++;
    }

    while(index2 < secondHalfSize)
    {
        arr[mergedArrIndex] = &secondHalfArray[index2];
        mergedArrIndex++;
        index2++;
    }
}

void mergeSort(Person **arr, int firstElement, int lastElement)
{
    if (firstElement < lastElement)
    {
        int midElement = (firstElement + lastElement) / 2;
        mergeSort(arr, firstElement, midElement);
        mergeSort(arr, midElement + 1, lastElement);
        merge(&arr, firstElement, midElement, lastElement);

    }
}



int main( void )
{
    Person *arrPersons;
    arrPersons = malloc( sizeof( Person ) * 20 );
    
    mergeSort(&arrPersons, 0, 19);
}

Ниже приведены результаты выполнения программы через gdb

gdb untitled2
....

(gdb) br main
Breakpoint 1 at 0xa3b: file untitled2.c, line 87.

(gdb) r
Starting program: untitled2 

Breakpoint 1, main () at untitled2.c:87
87  {

(gdb) c
Continuing.

Program received signal SIGSEGV, Segmentation fault.
0x0000555555554827 in merge (arr=0x7fffffffde88, firstElement=0, midElement=0, 
    lastElement=1) at untitled2.c:33

33          secondHalfArray[j] = *arr[midElement + 1+ j];
(gdb) bt

#0  0x0000555555554827 in merge (arr=0x7fffffffde88, firstElement=0, 
    midElement=0, lastElement=1) at untitled2.c:33
#1  0x0000555555554a30 in mergeSort (arr=0x7fffffffdf70, firstElement=0, 
    lastElement=1) at untitled2.c:79
#2  0x0000555555554a04 in mergeSort (arr=0x7fffffffdf70, firstElement=0, 
    lastElement=2) at untitled2.c:77
#3  0x0000555555554a04 in mergeSort (arr=0x7fffffffdf70, firstElement=0, 
    lastElement=4) at untitled2.c:77
#4  0x0000555555554a04 in mergeSort (arr=0x7fffffffdf70, firstElement=0, 
    lastElement=9) at untitled2.c:77
#5  0x0000555555554a04 in mergeSort (arr=0x7fffffffdf70, firstElement=0, 
    lastElement=19) at untitled2.c:77
#6  0x0000555555554a6e in main () at untitled2.c:91
(gdb) 

line 77 mergeSort(arr, firstElement, midElement);
Line 79 merge(&arr, firstElement, midElement, lastElement);
Line 33 secondHalfArray[j] = *arr[midElement + 1+ j];

Where
j = 0

Вышеупомянутое должно быть всем, что вам нужно знать, чтобы исправить программа.

Примечание: я не давал полям массива Person каких-либо определенных c значений.

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

Следует отметить, что ** не используется при передаче параметров

1 голос
/ 02 августа 2020

Что произошло?

Применение & к массиву приведет к указателю на массив . Итак, &arrPersons - это указатель на массив Person. Применение & к указателю на массив приведет к получению указателя на указатель на массив . Это то, что действительно перешло в merge. Итак, arr in merge - это указатель, указывающий на одиночный элемент указателя на массив. Таким образом, доступ к arr со смещением, отличным от нуля, вызовет ошибку индекса вне диапазона.

Передача по значению

Обычно параметры в функции C передаются по значению например: 

void f(int x);
f(val);

Вызывающий копирует значение перед передачей его в f. Таким образом, изменение x в f не влияет на val в вызывающей стороне.

Передача по ссылке

Некоторым функциям необходимо изменить переменную в вызывающей стороне. Они должны передавать аргумент по ссылке.

В C знаменитый способ передачи по ссылке - передать указатель на функцию, например: 

void f(int *p);
f(&val);

p is указатель. Таким образом, f может получить доступ к val с помощью *p.

Примечание : По сути, передачи по ссылке нет. Указатель передачи может делать почти то же самое, что и передача по ссылке. Но точно, он передает значение указателя.

Как передать массив по ссылке на функцию?

Массив превратится в указатель при его передаче. c -fqa 6.3 :

Ссылка на объект типа array-of-T, который появляется в выражении, превращается (за тремя исключениями) в указатель на его первый элемент; тип результирующего указателя - указатель на T.

Так что прямая передача массива в указатель-приемник функции прекрасна.

например, рассмотрим пример кода: 

void f(int *p);
int a[4];
f(a);

a можно напрямую перейти к f. А в функции f, p будет указателем, указывающим на первый элемент a.

В этом случае

Принять указатель на массив необязательно. Простая передача массива в функцию будет работать.

...