Сортировка списка по всем полям в любых направлениях. Использовать указатели на функции

@Michail97 · Регистрация: 18.09.2016

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

В общем, я запутался.
Вот задание.
Необходимо разработать программу согласно варианту
задания. При реализации использовать указатели на
функции и (или) массивы указателей на функции.
--------------------------------------------------
Дан список записей типа ТОВАР
(размер списка и его элементы вводятся пользователем).
Упорядочить список по любому из полей в любом направлении.
Поле и направление выбирает пользователь. В функцию сортировки
должен передаваться указатель на функцию сравнения двух элементов. (20 баллов).
ТОВАР:
- наименование товара (строка 15 символов);
- единицы измерения (строка 5 символов);
- цена (вещественное число с двумя знаками после запятой);
- количество (целое положительное число).
То, что накалякано

C

#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
typedef struct
{
    char  name[16];
    char  mesr[6];
    double price;
    int count;
}Good;
typedef Good *Ptr;
typedef int (*Pfun)( void *, void * );
int cmpNM ( void *, void * );
int cmpCNT( void *, void * );
void sortbychoice( Ptr , int, size_t, void (*), Pfun ); 
void swap ( Ptr , Ptr );
int main( int argc, char *argv[ ] )
{
    //printf( "%d",  offsetof( Good, count) );
    int d = 0, count;
    printf( "Enter count of lists: ");
    while( !d || count <= 0)
    {
        d = scanf( "%d", &count );
        if( !d || count <= 0 ) { while( getchar( ) != '\n' ); printf( "Repeat: "); }
    }
    fflush( stdin );
    int i;
    Ptr list = (Good*)calloc( count, sizeof(Good));
    for( i = 0; i < count; i++ ) { printf( "Name|Measure|Price|Count: " ); scanf( "%s%s%lf%d", list[i].name, list[i].mesr, &list[i].price, &list[i].count ); while( getchar( ) != '\n' );}
 
    //
 
    //sortbychoice( list, count, sizeof(char)*15, list[i].name, cmpNM );
    sortbychoice( list, count, offsetof( Good, count ), &list[i].count, cmpCNT);
    for( i = 0; i < count; i ++ ) printf( "Name: %s | Measure: %s | Price: %3.2lf | Count: %03d\n", list[i].name, list[i].mesr, list[i].price, list[i].count );
    system( "pause" );
    getch( );
    return 0;
}
 
void swap ( Ptr arg1, Ptr arg2 )
{
   Good temp = *arg1;
   *arg1 = *arg2;
   *arg2 = temp;
   return;
}
int cmpNM( void * arg1, void * arg2 )
{
    if( strcmp( (char*)arg1, (char*)arg2 ) == 1 ) return 1;
    else return 0;
}
int cmpCNT( void * arg1, void *arg2 )
{
    if(*((int*)arg1) > *((int*)arg2)) return 1;
    else return 0;
}
void sortbychoice ( Ptr good, int count, size_t size, void *arr, Pfun fun  )
{
     Ptr mass = good;
     int i, j, im;
     char * ar = ( char* )arr; 
     for( i = 0; i < count - 1; i++ ){
        im = i;
        for( j = i + 1; j < count; j++ ) if( fun( (void*)( ar + im*size),  (void*)( ar + j * size )) ) im = j;
        swap( &mass[i], &mass[im] );
     }
     return;
}

Добавлено через 3 минуты
дело в том, что я не могу понять, как мне обращаться к началу памяти одного и того же поля в массиве структур. Делал такое с обычными массивами, вроде всё работало. Вот как делал:

C

void SortArray( void *array, unsigned num, size_t size, int (*fun)(void *arg1, void *arg2), void (*fun1)( void *arg1, void *arg2))
{
    int i, j;
    int imin, imax;
    char *ptr = (char* )array; // указатель на начало памяти массива
    for( i = 0; i < num - 1; i += 2 )
    {
        imin = i;
        for( j = i + 2; j < num; j += 2 )
        if( fun( (void*)(ptr + imin*size), (void*)(ptr + j*size)) > 0 ) imin = j;
                fun1( ptr + i*size, ptr + imin*size);// смещение указателя на size бацтов массив
    }
 for( i = 1; i < num - 1; i += 2 )
    {
        imax = i;
        for( j = i + 2; j < num; j += 2 )
        if( fun( (void*)(ptr + imax*size), (void*)(ptr + j*size)) < 0 ) imax = j;
                fun1( ptr + i*size, ptr + imax*size );// смещение указателя на size бацтов массив
    }
}

Добавлено через 32 минуты

Сообщение от Michail97

//sortbychoice( list, count, sizeof(char)*15, list[i].name, cmpNM );
* * sortbychoice( list, count, offsetof( Good, count ), &list[i].count, cmpCNT);

На эти строки на намекать. Исправил

Добавлено через 3 минуты
В общем, для сортровки по кол - ву работает вроде.

C

void sortbychoice ( Ptr good, int count, void *arr, Pfun fun  )
{
     Ptr mass = good;
     int i, j, im;
     char * ar = ( char * )arr; // указатель на начало памяти выбранного поля аргумента arg
     for( i = 0; i < count - 1; i++ ){
        im = i;
        for( j = i + 1; j < count; j++ ) if( fun( (void*)( ar + im*sizeof( Good)),  (void*)( ar + j * sizeof(Good) )) ) im = j;
        swap( &mass[i], &mass[im] );
     }
     return;
}

Сейчас попробую со строками также провернуть

Добавлено через 9 минут
В общем, пока работает. Если найдёте грабли ещё, укажите, пожалуйста.

C

#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
typedef struct
{
    char  name[16];
    char  mesr[6];
    double price;
    int count;
}Good;
typedef Good *Ptr;
typedef int (*Pfun)( void *, void * );
int cmpNM ( void *, void * );
int cmpCNT( void *, void * );
void sortbychoice( Ptr , int, void (*), Pfun ); // для 1 - ого аргумента необходимо передать 2 - ой указатель
void swap ( Ptr , Ptr );
int main( int argc, char *argv[ ] )
{
    //printf( "%d",  offsetof( Good, count) );
    int d = 0, count;
    printf( "Enter count of lists: ");
    while( !d || count <= 0)
    {
        d = scanf( "%d", &count );
        if( !d || count <= 0 ) { while( getchar( ) != '\n' ); printf( "Repeat: "); }
    }
    fflush( stdin );
    int i;
    Ptr list = (Good*)calloc( count, sizeof(Good));
    for( i = 0; i < count; i++ ) { printf( "Name|Measure|Price|Count: " ); scanf( "%s%s%lf%d", list[i].name, list[i].mesr, &list[i].price, &list[i].count ); while( getchar( ) != '\n' );}
 
    //
 
    sortbychoice( list, count,list[0].name, cmpNM );
    //sortbychoice( list, count, &list[0].count, cmpCNT);
    for( i = 0; i < count; i ++ ) printf( "Name: %s | Measure: %s | Price: %3.2lf | Count: %03d\n", list[i].name, list[i].mesr, list[i].price, list[i].count );
    system( "pause" );
    getch( );
    return 0;
}
 
void swap ( Ptr arg1, Ptr arg2 )
{
   Good temp = *arg1;
   *arg1 = *arg2;
   *arg2 = temp;
   return;
}
int cmpNM( void * arg1, void * arg2 )
{
    if( strcmp( (char*)arg1, (char*)arg2 ) == 1 ) return 1;
    else return 0;
}
int cmpCNT( void * arg1, void *arg2 )
{
    if(*((int*)arg1) > *((int*)arg2)) return 1;
    else return 0;
}
void sortbychoice ( Ptr good, int count, void *arr, Pfun fun  )
{
     Ptr mass = good;
     int i, j, im;
     char * ar = ( char * )arr;
     for( i = 0; i < count - 1; i++ ){
        im = i;
        for( j = i + 1; j < count; j++ ) if( fun( (void*)( ar + im*sizeof( Good)),  (void*)( ar + j * sizeof(Good) )) ) im = j;
        swap( &mass[i], &mass[im] );
     }
     return;
}

@shvyrevvg · 03.05.2017, 14:12

C

#include  <stdio.h>
#include  <stdlib.h>
#include  <string.h>
 
#define MAXNAME 16
#define MAXUNIT 6
 
typedef int (*Pf)(void*, void*);
 
typedef struct {
    char  name[MAXNAME];
    char  unit[MAXUNIT];
    double price;
    int quantity;
} Product;
 
Product *product_list_alloc(int count)
{
    Product * list = malloc(count * sizeof(*list));
    return list;
}
 
void product_list_free(Product *list)
{
    free(list);
}
 
void product_list_imput(Product *list, int count)
{
    for (size_t i=0; i<count; i++) 
    { 
        printf("Name|Measure|Price|Count: "); 
        scanf("%s %s %lf %d", list[i].name, list[i].unit, 
              &list[i].price, &list[i].quantity); 
    }
 
}
 
void product_list_print(Product *list, int count)
{
    for (size_t i=0; i<count; i++) 
    { 
        printf( "Name: %s | Measure: %s | Price: %3.2lf | Count: %3d\n", 
               list[i].name, list[i].unit, list[i].price, list[i].quantity );
    }
 
}
 
static void swap(void *x, void *y, size_t l) {
   char *a = x, *b = y, c;
   while(l--) {
      c = *a;
      *a++ = *b;
      *b++ = c;
   }
}
 
static void sort(char *array, size_t size, int (*cmp)(void*,void*), int begin, int end) {
   if (end > begin) {
      void *pivot = array + begin;
      int l = begin + size;
      int r = end;
      while(l < r) {
         if (cmp(array+l,pivot) <= 0) {
            l += size;
         } else if ( cmp(array+r, pivot) > 0 )  {
            r -= size;
         } else if ( l < r ) {
            swap(array+l, array+r, size);
         }
      }
      l -= size;
      swap(array+begin, array+l, size);
      sort(array, size, cmp, begin, l);
      sort(array, size, cmp, r, end);
   }
}
 
void quicksort (void *array, size_t nitems, size_t size, int (*cmp)(void*,void*)) {
   sort(array, size, cmp, 0, nitems*size);
}
 
int name_cmp(void *a, void *b) 
{ 
    Product *p1 = a;
    Product *p2 = b;
    return strcmp(p1->name, p2->name); 
}
int name_rcmp(void *a, void *b) 
{ 
    Product *p1 = a;
    Product *p2 = b;
    return strcmp(p2->name, p1->name); 
}
 
int quantity_cmp(void *a, void *b) 
{ 
    Product *p1 = a;
    Product *p2 = b;
    return (p1->quantity - p2->quantity); 
}
int quantity_rcmp(void *a, void *b)
{ 
    Product *p1 = a;
    Product *p2 = b;
    return (p2->quantity - p1->quantity); 
}
 
int main(void)
{
    int count;
    Pf cmps[4] = {name_cmp, name_rcmp, quantity_cmp, quantity_rcmp};
    
    printf("Enter count of lists: "); 
    scanf("%d", &count);
    
    Product *products = product_list_alloc(count);
    
    product_list_imput(products, count);
    
    product_list_print(products, count);
    
    int ncmp = 3;
    
    quicksort(products, count, sizeof(*products), cmps[ncmp]);
    
    product_list_print(products, count);
    
    product_list_free(products);
    
    return 0;
}

@Michail97 · 03.05.2017, 17:42 **[ТС]**

shvyrevvg, спасибо. Ваша программа хороша, но я ещё как бы по учебной программе не проходил быстрые и медленные сортировки. Следующей темой рекурсия и по ней 3 лабы.) Хоара знаю, но мало использую. Пока что только выбор.
Можете посмотреть код? Всё ли терпимо?

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
typedef enum { FALSE, TRUE } Bool;
typedef struct
{
    char  name[16];
    char  mesr[6];
    double price;
    int count;
}Good;
typedef Good *Ptr;
typedef int (*Pfun)( void *, void *, Bool );
int cmpNM_MSR ( void *, void *, Bool ); // сравнитель по названию или по единице измерения
int cmpCNT( void *, void *, Bool ); // сравнитель по кол - ву
int cmpPRC( void *, void *, Bool ); // сравнитель по цене
void sortbychoice( Ptr , int, void (*), Pfun, Bool ); // сортировка
int main( int argc, char *argv[ ] )
{
    int d = 0, count;
    printf( "Enter count of lists: ");
    while( !d || count <= 0)
    {
        d = scanf( "%d", &count );
        if( !d || count <= 0 ) { while( getchar( ) != '\n' ); printf( "Repeat: "); }
    }
    fflush( stdin );
    int i;
    Ptr list = (Good*)calloc( count, sizeof(Good));
    for( i = 0; i < count; i++ ) { printf( "Name|Measure|Price|Count: " ); scanf( "%s%s%lf%d", list[i].name, list[i].mesr, &list[i].price, &list[i].count ); while( getchar( ) != '\n' );}
    Pfun sort_by[ ] = { cmpNM_MSR, cmpPRC, cmpCNT }; // меню из указателей на функции
    while ( 1 )
    {
        printf( "\nWhat kind of sort you choose?\n1 - sort by name;\n2 - sort by measure;\n3 - sort by price;\n4 - sort by count;\n5 - exit.\n" );
        int flag; scanf( "%d", &flag);
        Bool bl;
        if ( flag != 5 ) { printf( "Sort direction? \n0 - Descendingly;\n1 - Ascending.\n");  scanf( "%d", (int*)(&bl) ); }
    switch( flag )
    {
        case 1: sortbychoice( list, count,list[0].name, sort_by[0], bl ); break;
        case 2: sortbychoice( list, count,list[0].mesr, sort_by[0], bl ); break;
        case 3: sortbychoice( list, count, &list[0].price, sort_by[1], bl ); break;
        case 4: sortbychoice( list, count, &list[0].count, sort_by[2], bl ); break;
        default: if ( flag != 5 ) { printf( "Program hasn't such feature!\n" );}
    }
    if ( flag == 5) break;
    for( i = 0; i < count; i ++ ) printf( "Name: %s | Measure: %s | Price: %3.2lf | Count: %03d\n", list[i].name, list[i].mesr, list[i].price, list[i].count );
    }
    //
    //sortbychoice( list, count, &list[0].price, cmpPRC );
    //sortbychoice( list, count,list[0].mesr, cmpNM_MSR );
    //sortbychoice( list, count,list[0].name, cmpNM_MSR );
    //sortbychoice( list, count, &list[0].count, cmpCNT);
    //for( i = 0; i < count; i ++ ) printf( "Name: %s | Measure: %s | Price: %3.2lf | Count: %03d\n", list[i].name, list[i].mesr, list[i].price, list[i].count );
    system( "pause" );
    getch( );
    return 0;
}
 
void swap ( Ptr arg1, Ptr arg2 )
{
   Good temp = *arg1;
   *arg1 = *arg2;
   *arg2 = temp;
   return;
}
int cmpNM_MSR( void * arg1, void * arg2, Bool flag )
{
    if( flag )
    {
    if( strcmp( (char*)arg1, (char*)arg2 ) == 1 ) return 1;
    else return 0;
    }
    else
    {
    if( strcmp( (char*)arg1, (char*)arg2 ) == -1 ) return 1;
    else return 0;
    }
}
int cmpCNT( void * arg1, void *arg2, Bool flag )
{
    if( flag )
    {
    if(*((int*)arg1) > *((int*)arg2)) return 1;
    else return 0;
    }
    else
    {
    if(*((int*)arg1) < *((int*)arg2)) return 1;
    else return 0;
    }
}
int cmpPRC( void *arg1, void *arg2, Bool flag )
{
    if( flag )
    {
    if(*((double*)arg1) > *((double*)arg2)) return 1;
    else return 0;
    }
    else
    {
    if(*((double*)arg1) < *((double*)arg2)) return 1;
    else return 0;
    }
}
void sortbychoice( Ptr good, int count, void *arr, Pfun fun, Bool flag  )
{
     Ptr mass = good;
     int i, j, im;
     char * ar = ( char * )arr;
     for( i = 0; i < count - 1; i++ ){
        im = i;
        for( j = i + 1; j < count; j++ ) if( fun( (void*)( ar + im*sizeof( Good)),  (void*)( ar + j * sizeof(Good) ), flag ) ) im = j;
        swap( &mass[i], &mass[im] );
     }
     return;
}

@shvyrevvg · 03.05.2017, 18:10

Сообщение от Michail97

Можете посмотреть код? Всё ли терпимо?

Имена странные, с ходу, не понятно что означают Good, Ptr(указатель на что?)

Сообщение от Michail97

C

while( !d || count <= 0)
* * {
* * * * d = scanf( "%d", &count );
* * * * if( !d || count <= 0 ) { while( getchar( ) != '\n' ); printf( "Repeat: "); }
* * }

Тут какая-то магия

Сообщение от Michail97

C

1	fflush( stdin );

fflush-ить ввод не стоит, он для вывода предназначен. Тем более Вы раньше в цикле getchar() гоняли, почему тут также не сделать?

Сообщение от Michail97

C

1	Ptr list = (Good*)calloc( count, sizeof(Good));

Имена странные, вроде как list Ptr, а приводится к Good*, почему calloc, а не malloc?

Сообщение от Michail97

C

1	for( i = 0; i < count; i++ ) { printf( "Name\|Measure\|Price\|Count: " ); scanf( "%s%s%lf%d", list[i].name, list[i].mesr, &list[i].price, &list[i].count ); while( getchar( ) != '\n' );}

Почему все в одну строку?

Сообщение от Michail97

C

switch( flag )
* * {
* * * * case 1: sortbychoice( list, count,list[0].name, sort_by[0], bl ); break;
* * * * case 2: sortbychoice( list, count,list[0].mesr, sort_by[0], bl ); break;
* * * * case 3: sortbychoice( list, count, &list[0].price, sort_by[1], bl ); break;
* * * * case 4: sortbychoice( list, count, &list[0].count, sort_by[2], bl ); break;
* * * * default: if ( flag != 5 ) { printf( "Program hasn't such feature!\n" );}
* * }

Снова какая-то магия непонятная

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

@Michail97 · 03.05.2017, 18:55 **[ТС]**

shvyrevvg,
1. Ну да имена так себе. Согласен, если смотреть со стороны непонятно.
2. Магия служит для предотвращения ввода недопустимых символов и отрицательных чисел.

3. Флашить согласен. Нестандартное поведение функции - освобождение потока ввода. Просто решил разнообразить, а не писат всё время getchar)
4. Да, можно было преобразовать к типу ptr, а не good. За это бы получил

5. В одну строку, потому что не хочется растягивать код)
6. Заменил все комператоры на sort_by в зависимости от индекса. Комператоры для имени и единицы измерения совпадают, поэтому 2 раза ноль.
7. функция сортировки довольно простая, даже не требует знать, какого типа данные, только надо передать указатель на начало памяти нужного поля в структуре, а потом с периодом, равным памяти структуры прыгать по полям массива структур. В общем, мне ваш код все равно больше нравится. Как пройду быстрые сортировки, сразу же буду использовать qsort частенько.

Добавлено через 4 минуты
shvyrevvg, calloc по определению предназначен для массивов, malloc для чего угодно, как в принципе и calloc. Разницы большой не вижу.

@shvyrevvg · 03.05.2017, 19:19

Сообщение от Michail97

Как пройду быстрые сортировки, сразу же буду использовать qsort частенько.

Можно и без qsort

C

void swap(void *x, void *y, size_t l) {
   char *a = x, *b = y, c;
   while(l--) {
      c = *a;
      *a++ = *b;
      *b++ = c;
   }
}
 
void sort (void *array, size_t nitems, size_t size, int (*cmp)(void*,void*)) 
{
   int end = nitems*size;
   for(int i = 0 ; i < (end - size); i+=size) 
   {        
       for(int j = 0 ; j < (end - i - size); j+=size) 
       {  
           if(cmp(array + j, array+j+size)>0)
           {           
               swap(array+j+size, array+j, size);
           }
        }
    }
}

@Michail97 · 03.05.2017, 19:28 **[ТС]**

shvyrevvg, ниет, стремиться надо к быстрому, а пузырёк по своей воле я никогда не буду использовать.

@Michail97 94 / 41 / 23 Регистрация: 18.09.2016 Сообщений: 379
	03.05.2017, 18:55 [ТС]	5
	shvyrevvg, 1. Ну да имена так себе. Согласен, если смотреть со стороны непонятно. 2. Магия служит для предотвращения ввода недопустимых символов и отрицательных чисел. 3. Флашить согласен. Нестандартное поведение функции - освобождение потока ввода. Просто решил разнообразить, а не писат всё время getchar) 4. Да, можно было преобразовать к типу ptr, а не good. За это бы получил 5. В одну строку, потому что не хочется растягивать код) 6. Заменил все комператоры на sort_by в зависимости от индекса. Комператоры для имени и единицы измерения совпадают, поэтому 2 раза ноль. 7. функция сортировки довольно простая, даже не требует знать, какого типа данные, только надо передать указатель на начало памяти нужного поля в структуре, а потом с периодом, равным памяти структуры прыгать по полям массива структур. В общем, мне ваш код все равно больше нравится. Как пройду быстрые сортировки, сразу же буду использовать qsort частенько. Добавлено через 4 минуты shvyrevvg, calloc по определению предназначен для массивов, malloc для чего угодно, как в принципе и calloc. Разницы большой не вижу. 0

@Michail97 94 / 41 / 23 Регистрация: 18.09.2016 Сообщений: 379
	03.05.2017, 19:28 [ТС]	7
	shvyrevvg, ниет, стремиться надо к быстрому, а пузырёк по своей воле я никогда не буду использовать. 1

Сортировка списка по всем полям в любых направлениях. Использовать указатели на функции

Решение