Sorted Insertion into a Combined List

Question

AoA,

I am trying to debug a problem in my circular linked list for 12 hours. The function accepts an ADT that has a start and cursor field. The initial dummy cell points to itself. Insert items. Repetition elements are not allowed.

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

The code takes an integer number of integers and then sorts them into the LL parameter. It is assumed that it will be used for dialing (hence why there are no duplicate entries).

Output for: 9, 8, 7, 6, 5, 4, 3, 2, 1

is .. 3, 4, 5, 6, 7, 8, 9 (what happened to the first two values?)

When entering something like: 7, 3, 5, 1, 9, 2

out is only 7, 9 (so it cannot handle values ​​separated by more than one .. oO)

Additional Information:

 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 is the pointer type for setCDT. setElementT, however, is a simple and simple int . Sorry for the ambiguity.

Answer 1

Some observations:

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

value == E inside the first loop is never satisfied, since the loop condition has value < E , so a value of equal to E will stop the iteration. Change the loop condition to <= E and just return if a duplicate is found instead of using flag .

The path in which flag == false also does not return a value (although due to the aforementioned error it is not available at the moment), as well as the memory allocated for newNode flows if the error with flag fixed and E already exists in the list.

The following if seems meaningless due to lack of { after else indentation is very misleading:

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

Moreover, it is not a typedef setADT as a pointer type, it is simply misleading and combined with constructions of the New(setADT) type New(setADT) , it almost certainly causes errors.

Meanwhile, in setNew , since there is only one node, replace newNode->start->next = newNode->cursor->next = newNode->start; on newNode->start->next = newNode->start ;

Summary of Changes:

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

If the error repeats, the error will most likely be in a different place.

Verification Code:

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