1

Тема: qsort

Наскільки я розумію, функція qsort повинна міняти місцями елементи, якщо cmp повертає додатне значення. cmp("4", "2") повертає -2, тому qsort не повинна міняти їх. Але якщо ввести
3
4
01
2,
то отримаємо 2014.

#include <iostream>
using namespace std;

int cmp(const void* str1, const void* str2)
{
    char* s1 = (char*)str1, *s2 = (char*)str2;
    int l = min(strlen(s1), strlen(s2));
    if (strncmp(s1, s2, l) || strlen(s1) == strlen(s2)) return -strncmp(s1, s2, l);
    unsigned char i = l;
    if (strlen(s1) > strlen(s2))
    {
        while (s1[i] == s1[l-1] && i < strlen(s1)) ++i;
        return s1[l-1]-s1[i];
    }
    if (strlen(s1) < strlen(s2))
    {
        while (s2[i] == s2[l-1] && i < strlen(s2)) ++i;
        return s2[l-1]-s2[i];
    }
}

int main()
{
    /*char s1[10], s2[10];
    cin >> s1 >> s2;
    cout << cmp(s1, s2);*/
    short N;
    char S[101];
    cin >> N;
    char** A = new char*[N];
    for (char i = 0; i < N; ++i)
    {
        cin >> S;
        A[i] = new char[strlen(S)];
        strcpy(A[i], S);
    }
    qsort(A, N, 4, cmp);
    for (char i = 0; i < N; ++i) cout << A[i];
    cout << endl; system("pause");
    return 0;
}

2

Re: qsort

Прочитайте в стандарті визначення функції. Як гадаєте, чому там в параметрах функції порівняння показчики?

Подякували: mshcherba1

3

Re: qsort

Не знаю.

4

Re: qsort

Бо вона приймає не елементи, а показчики на них. У вас елементи - це показчики на рядки, отже, функція має приймати...

Подякували: mshcherba1

5

Re: qsort

...покажчики на покажчики на рядки. І як це зробити?

6

Re: qsort

void **str1, очевидно же.

Подякували: mshcherba1

7

Re: qsort

Але тепер
error C2664: 'qsort' : cannot convert parameter 4 from 'int (__cdecl *)(const void **,const void **)' to 'int (__cdecl *)(const void *,const void *)'

8

Re: qsort

Вибачте, не подивився, як ви передаєте...

char* s1 = *(char**)str1, *s2 = *(char**)str2;
Подякували: mshcherba1

9

Re: qsort

Все одно помилка C2664

10

Re: qsort

Заголовок має бути такий самий, як першого разу

Подякували: mshcherba1

11

Re: qsort

У вас елементи - це показчики на рядки.
А можна зробити так, щоб елементи були рядками?

12

Re: qsort

В C/C++ є велика купа різних типів, які використовуються як рядки. В C рядків немає взагалі, а є масиви char-ів, які обробляються стандартними функціями, як рядки, якщо там наприкінці є '\0', і покажчики на ці масиви. В C++ є std::string. Є аналоги для wchar_t. І кожен фреймворк пропонує ще щось своє велосипедне.
Відповідно, якщо вам треба, щоб елементи були рядками - юзайте std::string. Або змиріться із тим, що покажчик на ланцюжок char-ів в пам'яті, що зачінчується нулем - це і є рядок.

Подякували: mshcherba1

13

Re: qsort

Як перевірити функцію cmp на деяких двох рядках, які я вводжу з клавіатури?

14

Re: qsort

Якщо ввести
2
88
89, то виведе 8988, тобто 89 має стояти перед 88 (так і має бути), але якщо ввести
5
87
88
89
8
47, то виведе 888898747. Тут вже 89 стоїть після 88.

#include <iostream>
using namespace std;

int cmp(const void* str1, const void* str2)
{
    char* s1 = *(char**)str1, *s2 = *(char**)str2;
    int l = min(strlen(s1), strlen(s2));
    if (strncmp(s1, s2, l) || strlen(s1) == strlen(s2)) return -strncmp(s1, s2, l);
    unsigned char i = l;
    if (strlen(s1) > strlen(s2))
    {
        while (s1[i] == s1[l-1] && i < strlen(s1)) ++i;
        return s1[i]-s1[l-1];
    }
    else
    {
        while (s2[i] == s2[l-1] && i < strlen(s2)) ++i;
        return s2[i]-s2[l-1];
    }
}

int main()
{
    /*char** s1 = 0, **s2 = 0;
    //char** p1 = 0, **p2 = 0;
    cin >> *s1 >> *s2;
    //*p1 = s1; *p2 = s2;
    cout << cmp(*s1, *s2);*/
    short N;
    char S[101];
    cin >> N;
    char** A = new char*[N];
    for (char i = 0; i < N; ++i)
    {
        cin >> S;
        A[i] = new char[strlen(S)+1];
        strcpy(A[i], S);
    }
    qsort(A, N, 4, cmp);
    for (char i = 0; i < N; ++i) cout << A[i];
    //for (char i = 0; i < N; ++i) delete A[i];
    delete [] A;
    cout << endl; system("pause");
    return 0;
}

15

Re: qsort

Знову якась проблема з покажчиками?

16

Re: qsort

Ви не могли б відкрити нам таємницю - що той cmp робить? За якою ознакою він має сортувати рядки?

17

Re: qsort

Ось умова задачі:
Задача Strip На довгій смужці записується велике число, після чого смужка розрізається на кілька частин таким чином, що на кожній частині буде одна або кілька цифр.  Відомо, що до розрізання на смужці було записано максимальне число. Напишіть програму, яка відновить це число.

Технічні умови
Програма Strip читає з пристрою стандартного введення N (1≤N≤100) – кількість частин, на які була розрізана смужка. Кожен з наступних N рядків містить частину стрічки - одне число від 1 до 100 цифр. Гарантується, що хоча б на одній із частин перша цифра відмінна від нуля.  Програма виводить на екран одне число – максимальне число до розрізання.

18

Re: qsort

Після того, як я втретє не зміг правильно сформулювати умову першості, забив на всі порівняння і пішов "в лоб":

Прихований текст
int cmp(const void* str1, const void* str2)
{  
  char* s1 = *(char**)str1, *s2 = *(char**)str2;
  char buf1[101], buf2[101];
  strcpy( buf1, s1 );
  strcat( buf1, s2 ); //в buf1 - s1+s2
  strcpy( buf2, s2 );
  strcat( buf2, s1 ); //в buf2 - s2+s1
  return strcmp( buf2, buf1 ) ; //якщо s2+s1>s1+s2, то повертаємо додатнє значення і qsort міняє рядки
}

Звісно, треба відлагодити, але ідея, сподіваюся, зрозуміла.

Подякували: mshcherba, YurkoFlisk2

19

Re: qsort

http://www.olymp.vinnica.ua/index_ua.ph … task=Strip
Набирає 26 балів з 40

20

Re: qsort

На непройдених тестах видає неправильну відповідь чи timelimit(на NetOI дуже жорсткі обмеження по часу)?