Natürliche Sortierung in C - "Array von Strings, die Zahlen und Buchstaben enthalten"

Question

Suche nach einem bewährten Arbeitsalgorithmus für die Produktion. Ich habe dieses Beispiel gesehen aber ich habe im Internet oder in Büchern nicht viel anderes gefunden.

z.B.. datei_10.txt > datei_2.txt

Gracias.

Answer 1

Hier ist eine (getestete) Vergleichsfunktion, die diese Aufgabe erfüllt. Sie versteht nur ganze Zahlen ohne Vorzeichen, keine ganzen Zahlen mit Vorzeichen oder Fließkommazahlen:

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

Wenn Sie es verwenden möchten mit qsort verwenden Sie diese Hilfsfunktion:

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

Und Sie können etwas tun in der Größenordnung von

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

Answer 2

Die grundlegende Sortierfunktion wäre die Standard-C qsort() . Sie ist so parametrisiert, dass sie eine Vergleichsfunktion annimmt, und die Vergleichsfunktion ist das, was Sie schreiben müssten, um die natürliche Ordnung zu erreichen.

Ihre Frage mit Querverweis enthält eine C-Implementierung einer Vergleichsfunktion.

Eine Google-Suche "natürliche Sortierung c" zeigt eine SourceForge Umsetzung.

Answer 3

Ich gehe davon aus, dass Sie die C-Standardbibliothek bereits kennen qsort() Funktion:

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

Der letzte Parameter ist ein Funktionszeiger , d.h. Sie können ihr jede beliebige Funktion übergeben. Sie könnten verwenden strcmp() aber das würde zu ASCIIbetisch führen, und Sie wollen ja eine natürliche Sortierung.

In diesem Fall könnten Sie ganz einfach eine schreiben:

#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
          }
      }
}

Einige der else s könnte geklärt werden, wenn Sie einfach return früh, aber es gibt eine Grundstruktur. Siehe ctype.h für Funktionen wie isalpha() (wenn ein Zeichen Teil des Alphabets ist), isdigit() , isspace() und mehr.

Answer 4

Hier ist eine Version für Qt, die auch Unicode unterstützt:

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

}