Как отсортировать имена файлов с номерами и алфавитами в порядке, указанном в C?

Ответ 1

При ответе C следующая замена для strcasecmp(). Эта функция рекурсивно обрабатывает строки, содержащие переменные числовые и нечисловые подстроки. Вы можете использовать его с помощью qsort():

int strcasecmp_withNumbers(const void *void_a, const void *void_b) {
   const char *a = void_a;
   const char *b = void_b;

   if (!a || !b) { // if one doesn't exist, other wins by default
      return a ? 1 : b ? -1 : 0;
   }
   if (isdigit(*a) && isdigit(*b)) { // if both start with numbers
      char *remainderA;
      char *remainderB;
      long valA = strtol(a, &remainderA, 10);
      long valB = strtol(b, &remainderB, 10);
      if (valA != valB)
         return valA - valB;
      // if you wish 7 == 007, comment out the next two lines
      else if (remainderB - b != remainderA - a) // equal with diff lengths
         return (remainderB - b) - (remainderA - a); // set 007 before 7
      else // if numerical parts equal, recurse
         return strcasecmp_withNumbers(remainderA, remainderB);
   }
   if (isdigit(*a) || isdigit(*b)) { // if just one is a number
      return isdigit(*a) ? -1 : 1; // numbers always come first
   }
   while (*a && *b) { // non-numeric characters
      if (isdigit(*a) || isdigit(*b))
         return strcasecmp_withNumbers(a, b); // recurse
      if (tolower(*a) != tolower(*b))
         return tolower(*a) - tolower(*b);
      a++;
      b++;
   }
   return *a ? 1 : *b ? -1 : 0;
}

Примечания:

• Для Windows требуется stricmp(), а не эквивалент Unix strcasecmp().
• Вышеприведенный код (очевидно) даст неверные результаты, если числа действительно большие.
• Ведущие нули здесь игнорируются. В моей области это особенность, а не ошибка: мы обычно хотим, чтобы UAL0123 соответствовал UAL123. Но это может быть или не быть тем, что вам нужно.
• См. также Сортировка по строке, которая может содержать число и Как реализовать алгоритм естественной сортировки в С++?, хотя ответы там или в их ссылках, безусловно, длинны и бессвязны по сравнению с указанным выше кодом примерно на коэффициент не менее четырех.

Ответ 2

Что вы хотите сделать, это выполнить "Natural Sort". Вот сообщение в блоге об этом, объясняя, как это реализовано в python. Здесь - это модуль perl, который его выполняет. Также существует вопрос, похожий на Как реализовать алгоритм естественной сортировки в С++?

Ответ 3

Естественная сортировка - это то, как вы должны это делать. У меня есть рабочий код для моего сценария. Вероятно, вы можете использовать его, изменив его в соответствии с вашими потребностями:

    #ifndef JSW_NATURAL_COMPARE
    #define JSW_NATURAL_COMPARE
    #include <string>
    int natural_compare(const char *a, const char *b);
    int natural_compare(const std::string& a, const std::string& b);
    #endif
    #include <cctype>
    namespace {
      // Note: This is a convenience for the natural_compare 
      // function, it is *not* designed for general use
      class int_span {
        int _ws;
        int _zeros;
        const char *_value;
        const char *_end;
      public:
        int_span(const char *src)
        {
          const char *start = src;
          // Save and skip leading whitespace
          while (std::isspace(*(unsigned char*)src)) ++src;
          _ws = src - start;
          // Save and skip leading zeros
          start = src;
          while (*src == '0') ++src;
          _zeros = src - start;
          // Save the edges of the value
          _value = src;
          while (std::isdigit(*(unsigned char*)src)) ++src;
          _end = src;
        }
        bool is_int() const { return _value != _end; }
        const char *value() const { return _value; }
        int whitespace() const { return _ws; }
        int zeros() const { return _zeros; }
        int digits() const { return _end - _value; }
        int non_value() const { return whitespace() + zeros(); }
      };
      inline int safe_compare(int a, int b)
      {
        return a < b ? -1 : a > b;
      }
    }
    int natural_compare(const char *a, const char *b)
    {
      int cmp = 0;
      while (cmp == 0 && *a != '\0' && *b != '\0') {
        int_span lhs(a), rhs(b);
        if (lhs.is_int() && rhs.is_int()) {
          if (lhs.digits() != rhs.digits()) {
            // For differing widths (excluding leading characters),
            // the value with fewer digits takes priority
            cmp = safe_compare(lhs.digits(), rhs.digits());
          }
          else {
            int digits = lhs.digits();
            a = lhs.value();
            b = rhs.value();
            // For matching widths (excluding leading characters),
            // search from MSD to LSD for the larger value
            while (--digits >= 0 && cmp == 0)
              cmp = safe_compare(*a++, *b++);
          }
          if (cmp == 0) {
            // If the values are equal, we need a tie   
            // breaker using leading whitespace and zeros
            if (lhs.non_value() != rhs.non_value()) {
              // For differing widths of combined whitespace and 
              // leading zeros, the smaller width takes priority
              cmp = safe_compare(lhs.non_value(), rhs.non_value());
            }
            else {
              // For matching widths of combined whitespace 
              // and leading zeros, more whitespace takes priority
              cmp = safe_compare(rhs.whitespace(), lhs.whitespace());
            }
          }
        }
        else {
          // No special logic unless both spans are integers
          cmp = safe_compare(*a++, *b++);
        }
      }
      // All else being equal so far, the shorter string takes priority
      return cmp == 0 ? safe_compare(*a, *b) : cmp;
    }
    #include <string>
    int natural_compare(const std::string& a, const std::string& b)
    {
      return natural_compare(a.c_str(), b.c_str());
    }

Ответ 4

Принимая во внимание, что у этого есть тег c++, вы можете уточнить ответ @Joseph Quinsey и создать функцию natural_less, которая будет передана в стандартную библиотеку.

using namespace std;

bool natural_less(const string& lhs, const string& rhs)
{
    return strcasecmp_withNumbers(lhs.c_str(), rhs.c_str()) < 0;
}

void example(vector<string>& data)
{
    std::sort(data.begin(), data.end(), natural_less);
}

Я потратил время, чтобы написать какой-то рабочий код в качестве упражнения https://github.com/kennethlaskoski/natural_less

Ответ 5

Изменение этого ответа:

bool compareNat(const std::string& a, const std::string& b){
    if (a.empty())
        return true;
    if (b.empty())
        return false;
    if (std::isdigit(a[0]) && !std::isdigit(b[0]))
        return true;
    if (!std::isdigit(a[0]) && std::isdigit(b[0]))
        return false;
    if (!std::isdigit(a[0]) && !std::isdigit(b[0]))
    {
        if (a[0] == b[0])
            return compareNat(a.substr(1), b.substr(1));
        return (toUpper(a) < toUpper(b));
        //toUpper() is a function to convert a std::string to uppercase.
    }

    // Both strings begin with digit --> parse both numbers
    std::istringstream issa(a);
    std::istringstream issb(b);
    int ia, ib;
    issa >> ia;
    issb >> ib;
    if (ia != ib)
        return ia < ib;

    // Numbers are the same --> remove numbers and recurse
    std::string anew, bnew;
    std::getline(issa, anew);
    std::getline(issb, bnew);
    return (compareNat(anew, bnew));
}

toUpper():

std::string toUpper(std::string s){
    for(int i=0;i<(int)s.length();i++){s[i]=toupper(s[i]);}
    return s;
    }

Использование:

#include <iostream> // std::cout
#include <string>
#include <algorithm> // std::sort, std::copy
#include <iterator> // std::ostream_iterator
#include <sstream> // std::istringstream
#include <vector>
#include <cctype> // std::isdigit

int main()
{
    std::vector<std::string> str;
    str.push_back("20.txt");
    str.push_back("10.txt");
    str.push_back("1.txt");
    str.push_back("z2.txt");
    str.push_back("z10.txt");
    str.push_back("z100.txt");
    str.push_back("1_t.txt");
    str.push_back("abc.txt");
    str.push_back("Abc.txt");
    str.push_back("bcd.txt");

    std::sort(str.begin(), str.end(), compareNat);
    std::copy(str.begin(), str.end(),
              std::ostream_iterator<std::string>(std::cout, "\n"));
}

Ответ 6

Ваша проблема в том, что у вас есть интерпретация частей файла.

В лексикографическом порядке Slide1 находится перед Slide10, который до Slide5.

Вы ожидаете Slide5 до Slide10, поскольку у вас есть интерпретация подстрок 5 и 10 (как целые числа).

У вас возникнут проблемы, если у вас есть имя месяца в имени файла, и ожидали, что их закажут по дате (т.е. январь до августа). Вам нужно будет настроить сортировку для этой интерпретации (и "естественный" порядок будет зависеть от вашей интерпретации, нет общего решения).

Другой подход - форматировать имена файлов таким образом, чтобы ваша сортировка и лексикографический порядок совпадали. В вашем случае вы должны использовать начальные нули и фиксированную длину для числа. Таким образом, Slide1 становится Slide01, а затем вы увидите, что сортировка их лексикографически даст результат, который вы хотели бы иметь.

Однако часто вы не можете влиять на вывод приложения и, следовательно, не можете напрямую форматировать свой формат.

Что я делаю в таких случаях: напишите небольшую функцию script/, которая переименует файл в соответствующий формат, а затем используйте стандартные алгоритмы сортировки для их сортировки. Преимущество этого заключается в том, что вам не нужно адаптировать сортировку и использовать существующее программное обеспечение для сортировки. С другой стороны, бывают ситуации, когда это невозможно (поскольку имена файлов должны быть исправлены).