What is your current program, after incorporating whiteflags' updated suggestion?
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
This is my current program:
So the bugs for the moment are that it crashes when I input a 1 letter word, or when the duplicate letters are located at the end of the list. I suppose adding in some testcases would fix that, but this last bug I have is what's puzzling me the most.Code:#include <stdio.h> #include <stdlib.h> #define ALPHABET 26 typedef struct Node { char letter; struct Node *next; } NodeT; int isNum(char *); NodeT *addNode(NodeT *); NodeT *addLetter(NodeT *); void printList(NodeT *); NodeT *removeDupes(NodeT *); void freeList(NodeT *); int main(int argc, char **argv) { int length = 0; int seed = 0; NodeT *head1 = NULL; NodeT *head2 = NULL; int i = 0; if (argc != 3 || !isNum(argv[1]) || !isNum(argv[2])) { fprintf(stderr, "Usage: ./llrandword " "wordlength randomseed\n"); return EXIT_FAILURE; } length = atoi(argv[1]); seed = atoi(argv[2]); srandom(seed); for(i=0; i<length; i++) { head1 = addNode(head1); } head1 = addLetter(head1); printList(head1); putchar('\n'); head2 = head1; head2 = removeDupes(head1); printList(head2); putchar('\n'); freeList(head1); freeList(head2); return EXIT_SUCCESS; } int isNum(char *string) { int isNum = 1; while(*string != '\0') { if (*string < '0' || *string > '9') { isNum = 0; } string++; } return isNum; } NodeT *addNode(NodeT *list) { NodeT *new = NULL; NodeT *cur = NULL; new = malloc(sizeof(NodeT)); if (new == NULL) { fprintf(stderr, "Out of memory\n"); exit(1); } if (list == NULL) { list = new; } else { cur = list; while (cur->next != NULL) { cur=cur->next; } cur->next = new; } new->next = NULL; return list; } NodeT *addLetter(NodeT *head) { NodeT *cur = NULL; int r = 0; int rand = 0; for(cur = head; cur != NULL; cur = cur->next) { r = random(); rand = r % ALPHABET; cur->letter = 'a'+rand; } return head; } void printList(NodeT *head) { NodeT *cur = NULL; for (cur=head; cur != NULL; cur=cur->next) { printf("%c", cur->letter); if(cur->next != NULL) { printf("->"); } } } NodeT *removeDupes(NodeT *head) { NodeT *cur = NULL; NodeT *tmp = NULL; for(cur=head; cur->next != NULL; cur = cur->next) { if (cur->letter == cur->next->letter) { tmp = cur->next->next; free(cur->next); cur->next = tmp; } } return head; } void freeList(NodeT *head) { NodeT *cur = head; NodeT *tmp = NULL; while (cur != NULL) { tmp = cur->next; free(cur); cur = tmp; } }
What my expected output should be:
What I get:$ ./llrandword 10 4747
e->p->h->h->b->t->t->t->t->o
e->p->h->b->t->o
Notice the consecutive t's. This one has me stumped...$ ./llrandword 10 4747
e->p->h->h->b->t->t->t->t->o
e->p->h->b->t->t->o
Ah, that's because the loop considers each "next" node in turn. The problem is, when you have more than two consecutive duplicates, this means that the "current" node is not considered again. For example:Originally Posted by Mentallic
t1 -> t2 -> t3 -> u
t1 == t2, so we remove t2 to get:
t1 -> t3
But on the next iteration of the loop, the current is now t3, and since t3's next node is not a duplicate, there is no removal, hence you get the output:
t -> t -> u
To fix this, you will need to avoid changing the current node unless there is no duplicate. I think changing the for loop to a while loop would be appropriate.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
Nice work spotting that!
I have that bug fixed now with my removeDupes function currently as
But I'm still getting a crash when I ask for a 1 letter word...Code:NodeT *removeDupes(NodeT *head) { NodeT *cur = head; NodeT *tmp = NULL; while (cur->next != NULL) { if (cur->letter == cur->next->letter) { if (cur->next->next != NULL) { tmp = cur->next->next; free(cur->next); cur->next = tmp; } else { cur->next = NULL; } } else { cur = cur->next; } } return head; }
Personally, I tested with this implementation:
Code:NodeT *removeDupes(NodeT *head) { NodeT *current = head; if (current) { NodeT *next = current->next; while (next) { if (current->letter == next->letter) { current->next = next->next; free(next); } else { current = next; } next = current->next; } } return head; }Set breakpoints and step through your code until you find where the crash happens. The mistake should be somewhere before that point.Originally Posted by Mentallic
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
It should also crash if your list contains more than one letter (although it doesn't crash on my computer either for cases >1 letter).
The reason is the following:
head1 and head2 point to the same list. With "freeList(head1)" you free all allocated memory. With "freeList(head2)" you want to free the same memory a second time (you never allocate any new memory for head2). Using free a second time is undefined behavior.Code:head2 = head1; head2 = removeDupes(head1); printList(head2); putchar('\n'); freeList(head1); freeList(head2);
Look also at the output of valgrind:
You don't have to free head2.Code:$ valgrind -q ./test 3 4747 e->p->h e->p->h ==2314== Invalid read of size 4 ==2314== at 0x804890B: freeList (test.c:137) ==2314== by 0x80486E1: main (test.c:49) ==2314== Address 0x41ec02c is 4 bytes inside a block of size 8 free'd ==2314== at 0x402AE46: free (vg_replace_malloc.c:427) ==2314== by 0x804891B: freeList (test.c:138) ==2314== by 0x80486D5: main (test.c:48) ==2314== ==2314== Invalid free() / delete / delete[] / realloc() ==2314== at 0x402AE46: free (vg_replace_malloc.c:427) ==2314== by 0x804891B: freeList (test.c:138) ==2314== by 0x80486E1: main (test.c:49) ==2314== Address 0x41ec028 is 0 bytes inside a block of size 8 free'd ==2314== at 0x402AE46: free (vg_replace_malloc.c:427) ==2314== by 0x804891B: freeList (test.c:138) ==2314== by 0x80486D5: main (test.c:48) ==2314==
Bye, Andreas
Well, my own makes more sense to me, but I do appreciate some of the techniques you've used, such as letting next = cur->next.
I also found it crashes after my first freeList, which makes sense. I'm unsure with how to change it though. Yes, removing freeList(head2) would make it work, but I'm still seeing a problem with it If I make head2 the duplicate removed version of head1, then when I go to free head1 (since it's now head2), I'll only be freeing up to the new NULL pointer in head2 - so I'll have memory leaks.
Yeah it's weird that it works for >1.
Sorry, I don't understand what you mean.
"head2" isn't really necessary at all in your program because it is just a copy of "head1".
In "removeDupes()" you free the memory of all the nodes you remove from the list. In "freeList()" you free all nodes which are still in the list. Where do you see a memory leak?
That's what "undefined behavior" means. It may work or it may not, nobody knows :-).Yeah it's weird that it works for >1.
Bye, Andreas
Oh yeah... Staring at the terminal and seeing all those outputs of my program has given me the wrong idea
I would've guessed that undefined behaviour means that it will do different things in varying situations, but once you pinpoint the situation you're dealing with, you can surely reason as to why it's doing it the way it's doing it.
At least, that's sometimes the case in the mathematical sense of the word "undefined".
Yeah most people feel that way, and it's not wrong to feel that way. However, there is a big advantage to putting in the effort to understand code which someone else has written when it is simpler than your own. The benefit is far beyond ending up with better code; If you can get yourself to think a little differently about the problem, in a way that is simpler, then you really start to understand what you're doing a whole lot better. It can be very unexpectedly enlightening.
Speaking personally, it is doing precisely that, many years ago, which got me to where I am, in my ability to write very simple code about anything right from the outset. I'm known at work as being one of the fastest churners of code, without compromising on quality. It's not just the raw programming knowledge, it's definitely the mindset also.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
That would be equivalent to:
Code:if (current != NULL) { while (next != NULL) {
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)