Ordinati inserimento nella lista concatenata

Question

AoA,

Sto cercando di eseguire il debug di un problema nella mia lista concatenata circolare per 12 ore ora. La funzione accetta un ADT che ha un campo di inizio e di cursore. La cella fittizia iniziale indica se stessa. Inserire elementi Gli elementi di ripetizione non sono ammessi.

int setInsertElementSorted(setADT buffer, setElementT E) 
    { 
     bool isUnique = true; 
     cellT *previous; 

     previous = buffer->start; 
     buffer->cursor = buffer->start->next; 

     while(buffer->cursor != buffer->start){ 
      if(buffer->cursor->value == E){ 
       isUnique = false; 
      } else if(E < buffer->cursor->value) 
       break; 
       else { 
       previous = buffer->cursor; 
       buffer->cursor = buffer->cursor->next; 
      } 
     } 

     if(isUnique != false){ 
      cellT *newNode = malloc(sizeof(cellT)); 
      newNode->value = E; 
      previous->next = newNode; 
      newNode->next = buffer->cursor; 

      buffer->count++; 
      return (buffer->count); 
      } 
    } 

Il codice contiene una serie di numeri interi e quindi li ordina nel parametro LL. Dovrebbe essere usato per un set (quindi perché non ripetere le voci).

L'uscita: 9, 8, 7, 6, 5, 4, 3, 2, 1

è .. 3, 4, 5, 6, 7, 8, 9 (che fine la primi due valori)

Quando si introduce qualcosa come:? 7, 3, 5, 1, 9, 2

out è solo 7, 9 (quindi non può gestire valori separati da più di un .. oO)

Ulteriori informazioni:

typedef struct cellT { 
    int value; 
    struct cellT *next; 
} cellT; 

struct setCDT{ 
    int count; 
    cellT *start; 
    cellT *cursor; 
}; 

setADT setNew() 
{ 
    setADT newNode = malloc(sizeof(struct setCDT)); 
    newNode->start = newNode->cursor = malloc(sizeof(cellT)); 
    newNode->start->next = newNode->cursor->next = newNode->start; 
    newNode->count = 0; 
    return (newNode); 
} 

setADT è un tipo di puntatore per impostareCDT. setElementT, tuttavia, è semplicemente un semplice int. Ci scusiamo per l'ambiguità.

Answer 1

Alcune osservazioni:

while(buffer->cursor != buffer->start && buffer->cursor->value < E){ 
    if(buffer->cursor->value == E) // never true 

Il value == E all'interno del primo occhiello è mai vero, poiché la condizione del ciclo ha value < E, quindi incontrando un valore pari a E si fermava iterazione. Modificare la condizione del loop su <= E e semplicemente su return se viene trovato un duplicato invece di utilizzare lo flag.

Il percorso dove flag == false anche non restituisce un valore (anche se a causa del problema di cui sopra non è raggiungibile al momento), e anche la memoria allocata per newNode perdite se l'insetto con flag è fisso e E esiste nel lista già.

Il seguente if sembra inutile, ed a causa di non { dopo else il rientro è molto fuorviante:

if(buffer->cursor != buffer->start){ 
    newNode->next = buffer->cursor; // would be harmless in both branches 
    previous->next = newNode;  // done in both branches 
} else        // always using { } would make this clear 
    previous->next = newNode; 
    buffer->count++; 
    return (buffer->count); 

Inoltre, non typedef setADT come un tipo di puntatore, è solo fuorviante e combinato con costrutti come New(setADT) è quasi certo di causare bug.

Nel frattempo in setNew, poiché è presente un solo nodo, sostituire newNode->start->next = newNode->cursor->next = newNode->start; con newNode->start->next = newNode->start;

Sintesi delle novità:

int setInsertElementSorted(struct setCDT * const buffer, const int E) { 
    cellT *newNode; 
    cellT *previous = buffer->start; 
    buffer->cursor = previous->next; 

    while (buffer->cursor != buffer->start && buffer->cursor->value <= E) { 
     if (buffer->cursor->value == E) { 
      return buffer->count; // duplicate value 
     } 
     previous = buffer->cursor; 
     buffer->cursor = buffer->cursor->next; 
    } 
    if ((newNode = malloc(sizeof(*newNode)))) { 
     newNode->value = E; 
     newNode->next = buffer->cursor; 
     previous->next = newNode; 
     buffer->count++; 
    } 
    return buffer->count; 
} 

Se il bug persiste, l'errore è probabile che sia altrove.

Codice di prova:

int main (int argc, char **argv) { 
    struct setCDT *list = setNew(); 
    for (int i = 1; i < argc; ++i) { 
     setInsertElementSorted(list, atoi(argv[i])); 
    } 
    list->cursor = list->start; 
    while ((list->cursor = list->cursor->next) != list->start) { 
     (void) printf("%d\n", list->cursor->value); 
    } 
    return EXIT_SUCCESS; 
}