de tri des tableaux char *

Question

I ont une structure de données

struct record { 
    char cont[bufferSize]; 
    record *next; 
}; 

Quand j'ajouter de nouveaux enregistrements à cette structure, je veux qu'ils soient classés par ordre alphabétique. J'ai fait cette fonction, qui ajoute record au bon endroit (par ordre alphabétique) dans la liste chaînée:

record *start=NULL, *p, *x; 

void recAdd(char*temp) { 
     p = new record; 
     temp[strlen(temp)] = '\0'; 
     for (int j=0;j<bufferSize;j++) p->cont[j] = temp[j]; 
     if (start==NULL) start=p; 
     else { 
      x=start; 
      int c=0; 
      while (recComp(x->cont,p->cont) <= 0 && x->next != NULL) { 
        x=x->next; 
        c++; 
      } 
      if (c == 0) { 
       p->next=start; 
       start=p; 
      } 
      else { 
       x=start; 
       for (int i=0;i<c;i++) x=x->next; 
       p->next=x->next; 
       x->next=p; 
      } 
     } 
     for (int j=0;j<bufferSize;j++) temp[j] = NULL; 
    }; 

Mais d'une certaine manière, il ne règle pas les choses. Quel est le problème avec ma fonction?

Answer 1

Votre code est un bordel. Il y a un certain nombre de problèmes à la fois sémantiques et logiques, mais fondamentalement la logique qui décide où insérer de nouveaux nœuds est la plus erronée. Changez-le à cette (note mon nouveau code dans le bloc else):

void recAdd(const char*t) { 
     char temp[bufferSize]; 
     strcpy(temp, t); 
     p = new record; 
     temp[strlen(temp)] = '\0'; 
     for (int j=0;j<bufferSize;j++) p->cont[j] = temp[j]; 
     if (start==NULL) { start=p; start->next = 0; } 
     else { 
      record* x = start; 
      record* prev = 0; 
      while(x && recComp(x->cont, p->cont) <= 0) 
      { 
       prev = x; 
       x = x->next; 
      } 

      // p is a new node. p, x and prev are arranged thusly: 
      // prev -> p -> x 
      // if prev is null, p is a new head 
      // if x is null, p is a new tail 
      // otherwise, p is inserted between prev and x 

      if(!prev) 
      { 
       p->next = start; 
       start = p; 
      } 
      else if(!x) 
      // note this block and the next one could be combined. 
      // done this way for clarity. 
      { 
       prev->next = p; 
       p->next = 0; 
      } 
      else 
      { 
       p->next = x; 
       prev->next = p; 
      } 
     } 
     for (int j=0;j<bufferSize;j++) temp[j] = NULL; 
    }; 

mais le fait que vous avez eu assez de mal à écrire ce code que vous le demandez de l'aide à fixer illustre un point important: le meilleur le code est un code que vous n'avez jamais à écrire. Vous avez écrit à la fois une structure de type liste chaînée (c'est-à-dire des os vides) et un algorithme de tri. Les deux sont défectueux, et les deux ont des versions fonctionnelles, testées et efficaces disponibles dans le cadre des bibliothèques C++ standard. Vous devriez les utiliser. Utilisez des chaînes à la place de char * s. Utilisez des vecteurs au lieu de votre liste liée. Utilisez sort au lieu de votre algorithme de tri à la main. Pris ensemble, tout votre code peut être remplacé par ceci:

vector<string> records; 

// this for block just populates the vector with random strings 
for(int i = 0; i < 10; ++i) 
{ 
    string s; 
    for(int j = 0, jx = 3+(rand()/(RAND_MAX/10)); j < jx; ++j) 
     s += 'A'-1+(rand()/(RAND_MAX/26)); 
    cout << s << endl; 
    records.push_back(s); 
} 

sort(records.begin(), records.end()); 
copy(records.begin(), records.end(), ostream_iterator<string>(cout, " ")); 

Pourquoi rouler à la main un tas de choses et de vous exposer à d'innombrables défauts lorsque vous pouvez utiliser des outils qui fonctionnent déjà et faites ce que vous voulez?

Answer 2

Peut-être que je ne réponds pas à votre question, mais pourquoi n'utilisez-vous pas la STL? Il fera le tri pour vous; vous ne devriez pas avoir à écrire des routines de tri comme celle-ci ces jours-ci.

Answer 3

Quelques conseils:

• utilisation strcmp pour comparer des chaînes
• préfèrent utiliser des pointeurs vers l'intérieur de votre char struct. Cela vous permet de les assigner aveuglément sans copie et il ne sera pas perdre de l'espace dans votre struct
• si vous avez vraiment besoin de les copier utiliser strdup pour allouer de nouvelles chaînes
• garder trace de deux éléments actuels plutôt qu'un seul, ce évitera de compter combien vous en avez déjà parcouru et de parcourir la liste deux fois quand vous aurez trouvé la bonne position

Answer 4

Vous pouvez rendre la vie beaucoup plus facile si vous implémentez un tri simple d'insertion en utilisant le vecteur STL (le vecteur a un membre 'insérer').

ce code sera beaucoup plus propre aussi :)

recherche cplusplus.com pour des exemples de là-bas, vous trouverez utile.

Answer 5

Comme d'autres l'ont déjà suggéré, le STL rend la vie beaucoup plus facile. Il semble que tout ce dont vous avez besoin est un conteneur trié de chaînes:

#include <iostream> 
#include <set> 
#include <string> 

int main() 
{ 
    std::set<std::string> words; 
    words.insert("hello"); 
    words.insert("beautiful"); 
    words.insert("world"); 

    for (std::set<std::string>::const_iterator it = words.begin(); it != words.end(); ++it) 
    { 
     std::cout << *it << std::endl; 
    } 
}