Jak sortować nazwy plików za pomocą cyfr i alfabetów w porządku w C?

Question

Użyłem poniższy kod do sortowania plików w kolejności alfabetycznej i sortuje pliki, jak pokazano na rysunku:

for(int i = 0;i < maxcnt;i++) 
{ 
    for(int j = i+1;j < maxcnt;j++) 
    {   
     if(strcmp(Array[i],Array[j]) > 0) 
     {    
      strcpy(temp,Array[i]);  
      strcpy(Array[i],Array[j]);  
      strcpy(Array[j],temp);  
     }  
    } 
} 

Ale muszę go rozwiązać jak kolejność widoczne w programie Windows Explorer

Jak sortować w ten sposób? Proszę o pomoc

Answer 1

Dla odpowiedzi C, poniżej jest zamiennikiem dla strcasecmp(). Ta funkcja rekurencyjnie obsługuje ciągi zawierające zmienne podciągi numeryczne i nieliczbowe.Można go używać z 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; 
} 

Uwagi:

• Windows musi stricmp() zamiast Unix równoważne strcasecmp().
• Powyższy kod (oczywiście) daje niepoprawne wyniki, jeśli numery są naprawdę duże.
• Zaczynające się zera są tutaj ignorowane. W moim obszarze jest to funkcja, a nie błąd: zazwyczaj chcemy, aby UALpasował do UAL123. Ale to może, ale nie musi być to, czego potrzebujesz.
• Zobacz także Sort on a string that may contain a number i How to implement a natural sort algorithm in c++?, chociaż odpowiedzi tam, lub w ich linkach, są z pewnością długie i chaotyczne w porównaniu z powyższym kodem, o około współczynnik co najmniej czterech.

Answer 2

Co chcesz zrobić, to wykonać „naturalne sortowania”. Here is a blog post o tym, tłumacząc implementację w Pythonie. Here to moduł perla, który go wykonuje. Wydaje się również, że podobne pytanie jest dostępne pod adresem How to implement a natural sort algorithm in c++?

Answer 3

Naturalne sortowanie to sposób, w jaki musisz się tutaj udać. Mam działający kod dla mojego scenariusza. Prawdopodobnie możesz z niego skorzystać, zmieniając go zgodnie z Twoimi potrzebami:

#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()); 
    } 

Answer 4

Twoim problemem jest to, że masz interpretację części nazwy pliku.

W porządku leksykograficznym Slide1 jest przed Slide10, który jest przed Slide5.

Oczekujesz Slide5 przed Slide10 jak masz interpretację podciągi 5 i 10 (jako liczby całkowite).

Będziesz mieć więcej problemów, jeśli masz nazwę miesiąca w nazwie pliku i spodziewałbyś się, że będą one uporządkowane według daty (tj. W styczniu przed sierpniem). Będziesz musiał dostosować sortowanie do tej interpretacji (a "naturalna" kolejność będzie zależeć od twojej interpretacji, nie ma żadnego ogólnego rozwiązania).

Innym podejściem jest formatowanie nazw plików w sposób zgodny z sortowaniem i zgodnością leksykograficzną. W twoim przypadku użyjesz wiodących zer i stałej długości dla numeru. Tak więc Slide1 staje się Slide01, a następnie zobaczysz, że ich sortowanie leksykograficzne da wynik, który chciałbyś mieć.

Jednak często nie można wpłynąć na wyjście aplikacji, a tym samym nie można wymusić bezpośrednio formatu.

Co robię w takich przypadkach: napisz mały skrypt/funkcję, która zmienia nazwę pliku na prawidłowy format, a następnie użyj standardowych algorytmów sortowania, aby je posortować. Zaletą tego jest to, że nie musisz dostosowywać sortowania i możesz używać istniejącego oprogramowania do sortowania. Z drugiej strony są sytuacje, w których nie jest to możliwe (nazwy plików muszą być ustalone).

Answer 5

Biorąc pod uwagę, że ma to c++ tag, można opracować na odpowiedź @Joseph Quinsey i stworzyć natural_less funkcji mają być przekazane do biblioteki standardowej.

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); 
} 

Wziąłem czas, aby napisać kod pracy jako ćwiczenie https://github.com/kennethlaskoski/natural_less

Answer 6

Modyfikowanie this odpowiedź:

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() funkcja:

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

Zastosowanie:

#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")); 
}