Работа с массивами через указатели, адреса. Функция сортировки выбором любого массива

@Messian · Регистрация: 06.02.2014

Author24 — интернет-сервис помощи студентам

Надо было написать программу сортировки с использованием функций из учебника. соответственно Compare, Find_minimum_index, Swap и SwapChar. Ввод и вывод я таки сделал с помощью шаблонов, а остальное как то так. Так как по сути void указатель в функции - это обычный указатель неопределенного типа, то принимать на вход он должен адрес первого элемента массива. (array или &array - непринципиально?).
Функции из учебника, а значит а приори рабочие. Но сортировки как таковой нет. Последний элемент идет в начало массива, остальные сдвигаются. Отладка показывает непонятные цифры в compare.
Шаблонами в этих функциях пользоваться нельзя.

C++

#include "stdafx.h"
#include "iostream"
#include "conio.h"
using namespace std;
 
typedef int(*CompareFunctionType) (void *, void *);
 
 
template < class T >
void input(T *arr, int le)
{
 
    for (int i = 0; i<le; i++)
 
        cin >> arr[i];
}
template< class N >
void output(N* arr, int le)
{
    for (int i = 0; i<le; i++)
 
        cout << arr[i];
}
 
 
int CompareInt0to9(void *first_pointer, void *second_pointer) //принимает на вход адреса и смотрит что под ними
{
    int *first_element_int_pointer = (int *)first_pointer;
    int *second_element_int_pointer = (int *)second_pointer;
    return *first_element_int_pointer - *second_element_int_pointer;  
}
 
int CompareCharAtoZ(void *first_pointer, void *second_pointer)
{
    char *first_element_int_pointer = (char *)first_pointer;
    char *second_element_int_pointer = (char *)second_pointer;
    return *second_element_int_pointer - *first_element_int_pointer;
}
 
void SwapChar(char *first_pointer, char *second_pointer)//меняет местами два байта
{
    char temp = *first_pointer;
 
    *first_pointer = *second_pointer;
 
    *second_pointer = temp;
 
    return;
}
void Swap(void *first_pointer, void *second_pointer, int width)// меняет местами два адреса
{
    for (int byte_number = 0; byte_number < width; ++byte_number)
    {
        SwapChar((char *)first_pointer + byte_number, (char *)second_pointer + byte_number);
    }
    return;
}
 
int FindMinimumIndex(void *data_array, int width, CompareFunctionType compare_function_pointer, int first_index, int last_index)
{
    char *bytevise_array = (char *)data_array;//для удобства работы с void взят //char у которого размер ячейки 1 байт
    int minimum_index = first_index;
    int minimum_byte_number = minimum_index * width;//адаптируем размер ячейки под нужный формат
    int current_byte_number = 0;
    for (int element_number = first_index; element_number <= last_index; ++element_number)
    {
        current_byte_number = element_number * width;//номер байта- начало адреса i-го элемента
        if ((*compare_function_pointer) (&bytevise_array[current_byte_number], &bytevise_array[minimum_byte_number]) < 0)
        {
            minimum_byte_number = current_byte_number;
        }
    }
    minimum_index = minimum_byte_number / width; //возвращаем индекс
    return minimum_index;
}
 
void SelectionSort(void * input_data, int length, CompareFunctionType compare_function_pointer, int width)
{
    int i;
    int sa;
    for (i = 0; i<length; i++)
    {
 
        sa = FindMinimumIndex(&input_data, width, compare_function_pointer, i, length);
        char *bytevise_array = (char *) input_data;
        Swap(&bytevise_array[i*width], &bytevise_array[sa*width], width);
    }
}
 
void main()
{
    int arr[5];// пока что обычный int стат. массив на 5 элементов
 
    int length = 5;
 
 
    const int N = 2;
 
    CompareFunctionType compareFunctionPointers[N];
    compareFunctionPointers[0] = &CompareInt0to9;
    compareFunctionPointers[1] = &CompareCharAtoZ;
 
 
    input(arr, length);
 
    int width = 4;
 
    SelectionSort(&arr, length, compareFunctionPointers[0], width);
 
    output(arr, length);
 
    _getch();
}

@Messian · 24.12.2014, 00:30 **[ТС]**

Рабочий код:

C++

#include "stdafx.h"
#include "iostream"
#include "conio.h"
using namespace std;
 
typedef int(*CompareFunctionType) (void *, void *);
 
 
template < class T >
void input(T *arr, int le)
{
 
    for (int i = 0; i<le; i++)
 
        cin >> arr[i];
}
template< class N >
void output(N* arr, int le)
{
    for (int i = 0; i<le; i++)
 
        cout << arr[i];
}
 
 
int CompareCharAtoZ(void *first_pointer, void *second_pointer)
{
    char *first_element_int_pointer = (char *)first_pointer;
    char *second_element_int_pointer = (char *)second_pointer;
    return *first_element_int_pointer - *second_element_int_pointer;
}
 
int CompareInt0to9(void *first_pointer, void *second_pointer)
{
    int *first_element_int_pointer = (int *)first_pointer;
    int *second_element_int_pointer = (int *)second_pointer;
    return *first_element_int_pointer - *second_element_int_pointer;
}
 
void SwapChar(char *first_pointer, char *second_pointer)
{
    char temp = *first_pointer;
 
    *first_pointer = *second_pointer;
 
    *second_pointer = temp;
 
    return;
}
void Swap(void *first_pointer, void *second_pointer, int width)
{
    for (int byte_number = 0; byte_number < width; byte_number++)
    {
        SwapChar((char *)first_pointer + byte_number, (char *)second_pointer + byte_number);
    }
    return;
}
 
 
int FindMinimumIndex( char *z, int l, int width, CompareFunctionType compare_function_pointer, int j)
{
    int k=0;
    
    char *t;
    t = z;
 
    for (int i = width; i < l * width-width*j; i++)
    {
        if (compare_function_pointer(&z[i], t)<0)
        {
            t = &z[i];
            k = i;
        }
        i = i + width - 1;
    }
    return j+(k / width);
}
 
void SelectionSort(void * input_data, int length, CompareFunctionType compare_function_pointer, int width)
{
    int i;
    int sa;
    for (i = 0; i<length-1; i++)
    {
        char *z = (char*)input_data;
        char *ad = (char*)input_data;
        z = &z[i*width];
        sa = i;
        sa = FindMinimumIndex( z, length, width, compare_function_pointer, sa);
 
        Swap(&ad[i*width], &ad[sa*width], width);
    }
}
 
void main()
{
    int intarr[5];
    char chararr[5];
    int length=5,n;
 
 
    const int N = 2;
 
    CompareFunctionType compareFunctionPointers[N];
    compareFunctionPointers[0] = &CompareInt0to9;
    compareFunctionPointers[1] = &CompareCharAtoZ;
 
 
    //cout << "Input array size\n";
    //cin >> length;
    //arr = new int[length];
 
    cout << "Input kind of array: \n";
    cout << "0: Integer type array" << "\n1: Char type array\n";
    cin >> n;
    cout << "Input array elements\n";
 
    if (n == 0)
    {
        input(intarr, length);
        int width = sizeof(intarr[0]);
        SelectionSort(&intarr, length, compareFunctionPointers[n], width);
        output(intarr, length);
    }
    else
    {
        input(chararr, length);
        int width = sizeof(chararr[0]);
        SelectionSort(&chararr, length, compareFunctionPointers[n], width);
        output(chararr, length);
    }
 
    _getch();
}

	24.12.2014, 00:30

Опции темы