Естественная сортировка в C - «массив строк, содержащий цифры и буквы»

Question

Ищем проверенный алгоритм работы для производства. видел этот пример но больше ничего не нашел в Интернете или в книгах.

т.е. file_10.txt> file_2.txt

Спасибо.

Answer 1

Вот (проверенная) функция сравнения, которая выполняет эту работу. Он понимает только целые числа без знака, целые числа без знака или с плавающей запятой:

#include <stdlib.h>
#include <ctype.h>

/* like strcmp but compare sequences of digits numerically */
int strcmpbynum(const char *s1, const char *s2) {
  for (;;) {
    if (*s2 == '\0')
      return *s1 != '\0';
    else if (*s1 == '\0')
      return 1;
    else if (!(isdigit(*s1) && isdigit(*s2))) {
      if (*s1 != *s2)
        return (int)*s1 - (int)*s2;
      else
        (++s1, ++s2);
    } else {
      char *lim1, *lim2;
      unsigned long n1 = strtoul(s1, &lim1, 10);
      unsigned long n2 = strtoul(s2, &lim2, 10);
      if (n1 > n2)
        return 1;
      else if (n1 < n2)
        return -1;
      s1 = lim1;
      s2 = lim2;
    }
  }
}

Если вы хотите использовать его с qsort, используйте эту вспомогательную функцию:

static int compare(const void *p1, const void *p2) {
  const char * const *ps1 = p1;
  const char * const *ps2 = p2;
  return strcmpbynum(*ps1, *ps2);
}

И вы можете сделать что-то порядка

qsort(lines, next, sizeof(lines[0]), compare);

Answer 2

Базовая функция сортировки будет стандартной C qsort(). Он параметризован для использования функции сравнения, а функция сравнения - это то, что вам нужно написать для выполнения естественного упорядочения.

Ваш вопрос с перекрестными ссылками включает реализацию функции сравнения на языке Си.

В поиске Google "натуральная сортировка c" показана реализация SourceForge .

Answer 3

Полагаю, вы уже знаете функцию стандартной библиотеки C qsort():

void qsort(void *base,
           size_t nel,
           size_t width,
           int (*compar)(const void *, const void *);

Этот последний параметр является указателем на функцию , что означает, что вы можете передать ему любую функцию. На самом деле вы могли бы использовать strcmp(), но это дало бы вам ASCIIbetical, а вам определенно нужен естественный вид.

В этом случае вы могли бы написать довольно легко:

#include <ctype.h>

int natural(const char *a, const char *b)
{
    if(isalpha(*a) && isalpha(*b))
      {
        // compare two letters
      }
    else
      {
        if(isalpha(*a))
          {
            // compare a letter to a digit (or other non-letter)
          }
        else if(isalpha(*b))
          {
            // compare a digit/non-letter to a letter
          }
        else
          {
            // compare two digits/non-letters
          }
      }
}

Некоторые из else могут быть очищены, если вы просто return рано, но есть базовая структура. Проверьте ctype.h для таких функций, как isalpha() (если символ является частью алфавита), isdigit(), isspace() и т. Д.

Answer 4

Вот версия для Qt, которая также поддерживает Unicode:

int strcmpbynum(const QString& s1, const QString &s2) {
int i1 = 0; // index in string
int i2 = 0;
while (true) {
    if (s2.length() == i2) // both strings identical or s1 larger than s2
        return s1.length() == i1 ? 0 : 1;
    if (s1.length() == i1) return -1; // s1 smaller than s2

    unsigned short u1 = s1[i1].unicode();
    unsigned short u2 = s2[i2].unicode();

    if (u1 >= '0' && u1 <= '9' && u2 >= '0' && u2 <= '9') {
        // parse both numbers completely and compare them
        quint64 n1 = 0; // the parsed number
        quint64 n2 = 0;
        int l1 = 0; // length of the number
        int l2 = 0;
        do {
            ++l1;
            n1 = n1 * 10 + u1 - '0';
            if (++i1 == s1.length()) break;
            u1 = s1[i1].unicode();
        } while (u1 >= '0' && u1 <= '9');
        do {
            ++l2;
            n2 = n2 * 10 + u2 - '0';
            if (++i2 == s2.length()) break;
            u2 = s2[i2].unicode();
        } while (u2 >= '0' && u2 <= '9');
        // compare two numbers
        if (n1 < n2) return -1;
        if (n1 > n2) return 1;
        // only accept identical numbers if they also have the same length
        // (same number of leading zeros)
        if (l1 < l2) return -1;
        if (l1 > l2) return 1;
    } else {
        // compare digit with non-digit or two non-digits
        if (u1 < u2) return -1;
        if (u1 > u2) return 1;
        ++i1;
        ++i2;
    }
}

}