Кадндидат-студентски изпит по информатика на C++

С++ решаваня на задачи по информатика, от кандидатстудентски изпити

Универсална функция за сортиране на С++, чрез използване на указател към callback функция за сравнение

4 коментара

Езикът С++ предоставя различни възможности, чрез които да се реализаира унивесалност на дадена функция. Една такава възможност е използването на шаблони (templates),  а другиа е наследство от c, при което може да се декларират указатели от функционален тип  – указател който ще се насочи към функция с определен прототип (тип на върнат резултат и брой и тип на входните параметри).

Техниката за която ще разгледаме тук ще е чрез указател към функционален тип, или така наречените callback функции.

Условие на задачата:
Да се състави универсална функция на С++, която реализира метод за сортиране  ( за простота ще ползваме метода на пряка селекция ) на  елементи от всеки стандартен или потребителски тип.

Описание на решението:
Функцията която ще реши задачата е universal_sort, която приема следните параметри:

  1. void *array – указател към масива, който ще се сортира;
  2. unsigned int size – броя елементи на масива;
  3. unsigned int elem_size – броя байтове заемащ един елемент на масива;
  4. int (*fcallback)(void*, void*) – указател с име fcallback, към функция връщаща цяло число за резултат и имаща 2 указателя от тип void *,  за входни параметри;

Тъй като масивът е от тип void *, то за да достигаме до всеки негов елемент се ползва указател от тип char *, който да се пренасочва последователно към всеки следващ елемент при обхождането. Пренасочването на указателя става, като ползва брояча и го умножава по броя байтове заемащ един елемент от масива. Сравненията се извършвват от fcallback функцията, която се подава като входен параметър. Тя се извиква с указателите, които са насочени към началните адреси към съответните елементи на масива. Сравняващата fcallback функция трябва да връща число:

  • по-малко от нула, ако 1-вият елемент е по-малък от втория
  • 0, ако двата елемента са равни
  • по-голямо от нула, ако 2-рият елемент е по-голям от първия

Така универсалната функция изисква реализиране на подходяща функция за сравнение, която да се подаде като параметър. Функцията за сравнение има параметри от тип void *, така че те при реализацията, техният тип трябва да се промени до нужния такъв.

Реализирана е и функция my_memcpy, която копира определено количество байтове от даден начален адрес, към друг начален адрес. Така, ако копирате 4 байта от указател сочещ към тип инт, до друг указател сочещ отново към същия тип, то това ще е равносилно на присвояване на стойност. Същото може да се ползва и за присвояване на низове или всякакъв друг тип, стига да укажете точният брой байтове, които ще се копират. Вместо тази функция, може да се ползва memcpy, която прави същото, тук целта е да се покаже как действа и затова е реализирана.

С++ код на решението:


/*
 ============================================================================
 Name        : universal_sort.cpp
 Author      : Ivan Stoyanov
 Version     :
 Copyright   : Stoqnoff
 Description : Функция за универсално сортиране
 ============================================================================
 */

#include <iostream>
#include<cstring>

using namespace std;

/* Функция която копира size на брой байта от паметта, сочена от
   указателя src в паметта сочена от указателя dest.
   За по голямо бързодействие се копират по 8 байта ( sizeof(long long int) ),
   като остатакът се коират байт по байт.
*/
void my_memcpy(void const *dest, void const *src, unsigned size )
{
    long long int * pi1 = (long long int *)dest;
    long long int * pi2 = (long long int *)src;

    int k1,k2, bytes;
    bytes = sizeof(long long int);
    k1 = size/bytes;
    k2 = size%bytes;

    // копира по sizeof(long long int) байта
    int i=0;
    while(i++<k1) *pi1++=*pi2++;

    // Декларира и насочва указатели от char, към първия не копиран(не записан) байт
    char * pc1 = (char *)dest+k1*bytes;
    char * pc2 = (char *)src+k1*bytes;

    // копира остатъка байт по байт
    i=0;
    while(i++<k2) *pc1++=*pc2++;
}


/**
 * array - указател на който ще се предаде масив с данни от мпроизволен тип,
 * size - размера на масива
 * fcallback - указател към функция връщаща тип int и имаща 2 параметъра
 * от тип void*. Задава се (*fcallback) за да не го разпознае като int *
 */
void universal_sort( void *array, unsigned int size, unsigned int elem_size, int (*fcallback)(void*, void*) )
{
    // Следва реализация на метода на прряка селекция,universal_sort който е бавен метод
    // но целта тук е да се покаже самата функция как се реализира
    //---------------------------------------------------------------------

    char *parr = (char *)array;

    // Резултата от сравнението върнато от fcallback се присвоява на cmp
    int cmp, pos;
    char *buff = new char[elem_size];
    for(int i=0; i<size; i++) {
        pos = i;
        for(int j=i+1; j<size; j++) {
            cmp = (*fcallback)(parr+j*elem_size, parr+pos*elem_size);
            if( cmp < 0 ) pos=j;
        }

        if(i!=pos) {
            // може да се ползва и  функцията memcpy от cstring
            my_memcpy(buff, parr+pos*elem_size, elem_size);
            my_memcpy(parr+pos*elem_size, parr+i*elem_size, elem_size);
            my_memcpy(parr+i*elem_size, buff, elem_size);
        }
    }

    delete[] buff;
}


/* Функция за сравняване на символи */
int cmp_chars(void * c1, void * c2)
{
    char * pc1 = (char *) c1;
    char * pc2 = (char *) c2;

    if(*pc1 < *pc2) return -1;
    else if(*pc1 == *pc2) return 0;
    else return 1;
}

/* Функция за сравняване на цели числа */
int cmp_nums(void * n1, void * n2)
{
    int * pn1 = (int *) n1;
    int * pn2 = (int *) n2;

    if(*pn1 < *pn2) return -1;
    else if(*pn1 == *pn2) return 0;
    else return 1;
}

/* Функция за сравняване на низове */
int cmp_srings(void *s1, void *s2)
{
    return strcmp( (char const *)s1,  (char const *)s2 );
}


// Главна функция
int main()
{
	// Сортира масив от символи
    char chars[] = {'s', 'c', 'f', 'a', 'r'};
    universal_sort(chars, 5, sizeof(char), cmp_chars);
    for(int i=0; i<5; i++){
        std::cout << chars[i] << ", ";
    }
    std::cout << std::endl;

    // Сортира масив от числа
    int nums[] = {2, 8, 3, 21, 1, 9};
    universal_sort(nums, 6, sizeof(int), cmp_nums);
    for(int i=0; i<6; i++){
        std::cout << nums[i] << ", ";
    }
    std::cout << std::endl;


    // Сортира масив от низове
    int n=3;
    char strings[][21] = {
    		"string1",
    		"second",
    		"first"
    };

    universal_sort(strings, n, sizeof(char)*21, cmp_srings);
    for(int i=0; i<n; i++){
    	std::cout << strings[i] << ", ";
    }
    std::cout << std::endl;

    return 0;
}



/*
Ако дефинираме следния потребителски тип:
typedef int (*SortCompareCallback)(void*, void*);
то тогава може да заменим параметъра
	int (*fcallback)(void*, void*)
със
	SortCompareCallback fcallback
*/

Written by Stoyanoff

21/09/2012 в 15:47

4 коментара

Subscribe to comments with RSS.

  1. Браво, господине

    Мартин Христев

    24/04/2020 at 09:16

  2. Пич, имаш грешка при обяснението на fcallback функцията – какво връща тя:

    ако 1-вият елемент е по-малък от втория

    е също като:

    ако 2-рият елемент е по-голям от първия

    Али Баба

    14/05/2014 at 10:28

  3. Добре структорирана задача и е обяснено на достъпен език. Трябва да има повече такива примери.

    Слави Вазов

    12/11/2012 at 13:33

  4. Браво! Най-после някой да започне да обяснява нещата на достъпен и разбираем език! И задачите, и решенията и обясненията са супер!

    златанова

    05/11/2012 at 11:47


Вашият коментар

Попълнете полетата по-долу или кликнете върху икона, за да влезете:

WordPress.com лого

В момента коментирате, използвайки вашия профил WordPress.com. Излизане /  Промяна )

Google photo

В момента коментирате, използвайки вашия профил Google. Излизане /  Промяна )

Twitter picture

В момента коментирате, използвайки вашия профил Twitter. Излизане /  Промяна )

Facebook photo

В момента коментирате, използвайки вашия профил Facebook. Излизане /  Промяна )

Connecting to %s

%d блогъра харесват това: