10 replies to this topic

[0xFACEB004]

Here is my solution for the Josephus Problem (of user inputted sized circle and "magic" number) using a circularly linked list.

 

Any suggestions on what I could have, or should have, done differently for better efficiency or best practices?

#include <stdio.h>
#include <stdlib.h>


typedef struct node{
	unsigned childNum;
	struct node* next;
}node;

unsigned findSolution(unsigned size, unsigned n){
	node* firstChild = (node*)malloc(sizeof(node));
	node* lastChild = (node*)malloc(sizeof(node));
	node* currentChild = (node*)malloc(sizeof(node));
	node* trailNode = (node*)malloc(sizeof(node));
	node* p; /* used to delete node */

	firstChild->childNum = 0;

	/* if the size of the list to be created is only 1 child, return as the solution */
	if(size == 1) return size;
	
	/* create the circlularly linked list of size - 1 */
	for(unsigned i = 1; i < size; i++){
		node* nextChild = (node*)malloc(sizeof(node));
		nextChild->childNum = i;
		nextChild->next = NULL;

		if(firstChild->childNum < 1){
			firstChild = nextChild;
			lastChild = nextChild;
		}else{
			lastChild->next = nextChild;
			lastChild = nextChild;
		}
	}
	/* create the last node */
	node* nextChild = (node*)malloc(sizeof(node));
	nextChild->childNum = size;
	lastChild->next = nextChild;
	lastChild = nextChild;
	lastChild->next = firstChild;
	
	
	/* iterate the list and delete the nth node until currentChild points to itself */
	currentChild = firstChild;
	while(currentChild != NULL && currentChild->next != currentChild){
		if(n > 1){
			for(unsigned i = 1; i < n; i++){
				trailNode = currentChild;
				currentChild = currentChild->next;
			}		
			/* delete this child */
			trailNode->next = trailNode->next->next;
			p = currentChild;
			currentChild = currentChild->next;
			free(p);
		}else{
			/* n == 1, remove every child */
			p = currentChild;
			/* if the next child is the last child, point it to itself to exit loop */
			if(currentChild->next = lastChild){
				lastChild->next = lastChild;
			}
			currentChild = currentChild->next;
			free(p);
		}
	}
		
	/* only 1 node remaining -- this is the solution */
	return currentChild->childNum;

}

int main(void){
	unsigned size = 0;
	unsigned n = 0;
	
	do{
		printf_s("How many children are in the circle -- must be > 0: ");
		scanf_s("%u", &size);
		printf_s("Remove every nth child -- value for n must be > 0: ");
		scanf_s("%u", &n);
		printf_s("\n\n");
	}while(size < 1 || n < 1);
		
	printf_s("Computing the answer...");
	printf_s("\n\n\nChild number %li is the winner.", findSolution(size, n));
	for(;;);
	return 0;
}

[0xDEADBEEF]

It looks like you've got a few memory leaks there;

 

I'd probably separate out the code which building the list from the code doing the checking, to make it cleaner.

 

Finally, your special case of n==1 can be evaluated in constant time.

[gonerogue]

Yes, you do have memory leaks.

Is good to run the program under a runtime analysis tool to see this kind of problems.

I have run your program under valgrind, here is the report:

$ valgrind --leak-check=full ./test
==1791== Memcheck, a memory error detector
==1791== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al.
==1791== Using Valgrind-3.6.0.SVN-Debian and LibVEX; rerun with -h for copyright info
==1791== Command: ./test
==1791== 
How many children are in the circle -- must be > 0: 100
Remove every nth child -- value for n must be > 0: 4
 
 
Computing the answer...
 
 
Child number 34 is the winner.==1791== 
==1791== HEAP SUMMARY:
==1791==     in use at exit: 40 bytes in 5 blocks
==1791==   total heap usage: 104 allocs, 99 frees, 832 bytes allocated
==1791== 
==1791== 8 bytes in 1 blocks are definitely lost in loss record 1 of 5
==1791==    at 0x4023F50: malloc (vg_replace_malloc.c:236)
==1791==    by 0x80484C5: findSolution (test.c:11)
==1791==    by 0x80486E3: main (test.c:87)
==1791== 
==1791== 8 bytes in 1 blocks are definitely lost in loss record 2 of 5
==1791==    at 0x4023F50: malloc (vg_replace_malloc.c:236)
==1791==    by 0x80484D4: findSolution (test.c:12)
==1791==    by 0x80486E3: main (test.c:87)
==1791== 
==1791== 8 bytes in 1 blocks are definitely lost in loss record 3 of 5
==1791==    at 0x4023F50: malloc (vg_replace_malloc.c:236)
==1791==    by 0x80484E3: findSolution (test.c:13)
==1791==    by 0x80486E3: main (test.c:87)
==1791== 
==1791== 8 bytes in 1 blocks are definitely lost in loss record 4 of 5
==1791==    at 0x4023F50: malloc (vg_replace_malloc.c:236)
==1791==    by 0x80484F2: findSolution (test.c:14)
==1791==    by 0x80486E3: main (test.c:87)
==1791== 
==1791== 8 bytes in 1 blocks are definitely lost in loss record 5 of 5
==1791==    at 0x4023F50: malloc (vg_replace_malloc.c:236)
==1791==    by 0x8048521: findSolution (test.c:24)
==1791==    by 0x80486E3: main (test.c:87)
==1791== 
==1791== LEAK SUMMARY:
==1791==    definitely lost: 40 bytes in 5 blocks
==1791==    indirectly lost: 0 bytes in 0 blocks
==1791==      possibly lost: 0 bytes in 0 blocks
==1791==    still reachable: 0 bytes in 0 blocks
==1791==         suppressed: 0 bytes in 0 blocks
==1791== 
==1791== For counts of detected and suppressed errors, rerun with: -v
==1791== ERROR SUMMARY: 5 errors from 5 contexts (suppressed: 13 from 8)

Edited by gonerogue, 21 February 2014 - 04:51 AM.

[0xFACEB004]

Thank you both very much!

[0xFACEB004]

OK, here is the update code...but I have a problem. VS is reporting two memory leaks, which I can't seem to do anything about.

 

The first is the last node of the list (lastChild), which is allocated in buildList. It is freed in findSolution, but still is reported as a leak.

 

The second is trailNode. The problem there is that when there are only two nodes left in the list, one will be currentChild, the other will be trailNode. Once the node to be deleted is selected, which will be currentChild, currentChild->next will point to trailNode -- and upon deletion of the selected node, currentChild and trailNode will be the same. And once I free currentChild, trailNode is freed as well, right? If I attempt to free trailNode after freeing currentChild the program crashes with this error:

 

 

And this is all of the information it gives me:

 

 

 

Here is the output from the memory check:

Detected memory leaks!
Dumping objects ->
c:\...\main.cpp(54) : {163} normal block at 0x000C6088, 8 bytes long.
 Data: <        > CD CD CD CD CD CD CD CD 
c:\...\main.cpp(15) : {63} normal block at 0x000C4468, 8 bytes long.
 Data: <        > CD CD CD CD CD CD CD CD 
Object dump complete.

 

 

Here is the complete code with changes Evan suggested. Any idea how to correct these issues?

#define _CRTDBG_MAP_ALLOC /* required for debugging memory leaks in Visual Studio -- Microsoft specific */
#include <stdlib.h>
#include <crtdbg.h> /* required for debugging memory leaks in Visual Studio -- Microsoft specific */
#include <stdio.h>


typedef struct node{
	unsigned childNum;
	struct node* next;
}node;


node* buildList(node* firstChild, unsigned size){
	node* lastChild = (node*)malloc(sizeof(node));

	firstChild->childNum = 0;
	

	/* create the circlularly linked list of size - 1 */
	for(unsigned i = 1; i < size; i++){
		if(i == 1){
			firstChild->childNum = i;
			firstChild->next = lastChild;
			lastChild = firstChild;
		}else{
			node* nextChild = (node*)malloc(sizeof(node));
			nextChild->childNum = i;
			nextChild->next = NULL;

			lastChild->next = nextChild;
			lastChild = nextChild;
		}
	}
	/* create the last node */
	node* nextChild = (node*)malloc(sizeof(node));
	nextChild->childNum = size;
	lastChild->next = nextChild;
	lastChild = nextChild;
	lastChild->next = firstChild;		
			
	return firstChild;
}


unsigned findSolution(unsigned size, unsigned n){	
	/* if the size of the list to be created is only 1 child, return size as the solution,
	   or if n == 1 every child will be deleted, last child is solution -- which == size */
	if(size == 1 || n == 1){
		return size;
	}else{
		node* currentChild = (node*)malloc(sizeof(node));
		currentChild = buildList(currentChild, size);
		node* trailNode = (node*)malloc(sizeof(node));
		node* p;
	
		/* iterate the list and delete the nth node until currentChild points to itself */
		while(currentChild != NULL && currentChild->next != currentChild){
			for(unsigned i = 1; i < n; i++){
				trailNode = currentChild;
				currentChild = currentChild->next;
			}		
			/* delete this child */
			trailNode->next = trailNode->next->next;
			p = currentChild;
			currentChild = currentChild->next;
			free(p);
		}
		/* only 1 node remaining -- this is the solution */
		int solution = currentChild->childNum;
		free(currentChild);
				
		return solution;
	}	
}


int main(void){
	unsigned size = 0;
	unsigned n = 0;
	
	do{
		printf_s("How many children are in the circle -- must be > 0: ");
		scanf_s("%u", &size);
		printf_s("Remove every nth child -- value for n must be > 0: ");
		scanf_s("%u", &n);
		printf_s("\n\n");
	}while(size < 1 || n < 1);
		
	printf_s("Computing the answer...");
	printf_s("\n\n\nChild number %li is the winner.", findSolution(size, n));

	_CrtDumpMemoryLeaks(); /* dump memory leaks for debugging in Visual Studio -- Microsoft specific */

	for(;;);
	return 0;
}

[0xDEADBEEF]

you allocate trailNode, but then the first thing you do is assign it to another value. So that appears to be leaking. Fix that and see if there are any other leaks, I can't currently see any others.

[0xFACEB004]

you allocate trailNode, but then the first thing you do is assign it to another value. So that appears to be leaking. Fix that and see if there are any other leaks, I can't currently see any others.

 

Thanks Even, that fixes the problem with trailNode. And here is the dump afterwards:

Detected memory leaks!
Dumping objects ->
c:\...\main.cpp(15) : {60} normal block at 0x00721578, 8 bytes long.
 Data: <        > CD CD CD CD CD CD CD CD 
Object dump complete.

But I know that the node this is referring to (lastChild in buildList) is being freed in findSolution. So am I to assume that this is just a false positive and not worry about it?

[0xDEADBEEF]

Ok, think i've got it. You're creation logic is a little too complicated, hence why its hard to see.

 

Notice that if i == 1, you set firstChild->next to lastChild (the initially created one.) But then, lastChild becomes firstChild.

 

Then when i == 2, you point lastChild->next to nextChild. Now Remeber from above that lastChild is actually firstChild. Therefore before you assign the next pointer to nextChild, it was actually pointing to the original value of lastChild. Hence the memory leak.

 

Also this shows that the creation function isn't creating a loop of size n, but n-1.

 

I think there's a few things you can do to simplify your creation a bit. First return a pointer to the start of the loop rather than take one in. 

ie.

 

node* buildList(unsigned size) { ... }

 

For the building of the list, you've got two parts; first create a linked list, then point the end to the start. So something like this is required:

create node start;
 
create pointer to node p;
for(int i=1;i<size;++i) {
    create node next;
    p-> next := next;
    p = p->next;
}
 
p->next = start;
return start;

[0xFACEB004]

Thank you Evan! No memory leaks now.

 

My buildList function is now:

node* buildList(unsigned size){
	node* firstChild = (node*)malloc(sizeof(node));
	node* lastChild = (node*)malloc(sizeof(node));

	
	/* create the circlularly linked list of size */
	firstChild->childNum = 1;
	firstChild->next = lastChild;
	
	for(unsigned i = 2; i <= size; i++){
		node* nextChild = (node*)malloc(sizeof(node));
		nextChild->childNum = i;
		nextChild->next = NULL;

		lastChild->next = nextChild;
		lastChild = nextChild;
		
	}
	/* last node points to first */
	lastChild->next = firstChild;		
			
	return firstChild;
}

And I found a logic error in my findSolution function:

/* iterate the list and delete the nth node until currentChild points to itself */
while(currentChild != NULL && currentChild->next != currentChild){
    for(unsigned i = 1; i < n; i++){
	...
    }		
    ...
}

I should have started the loop at 0 instead of 1, which explains why correct answers were still being returned even though the list was sized n-1.


Here, again is the corrected, complete code -- with no memory leaks:

#include <stdlib.h>
#include <stdio.h>


typedef struct node{
	unsigned childNum;
	struct node* next;
}node;


node* buildList(unsigned size){
	node* firstChild = (node*)malloc(sizeof(node));
	node* lastChild = (node*)malloc(sizeof(node));

	
	/* create the circlularly linked list of size */
	firstChild->childNum = 1;
	firstChild->next = lastChild;
	
	for(unsigned i = 2; i <= size; i++){
		node* nextChild = (node*)malloc(sizeof(node));
		nextChild->childNum = i;
		nextChild->next = NULL;

		lastChild->next = nextChild;
		lastChild = nextChild;
		
	}
	/* last node points to first */
	lastChild->next = firstChild;		
			
	return firstChild;
}


unsigned findSolution(unsigned size, unsigned n){	
	/* if the size of the list to be created is only 1 child, return size as the solution,
	   or if n == 1 every child will be deleted, last child is solution -- which == size */
	if(size == 1 || n == 1){
		return size;
	}else{
		node* currentChild = buildList(size);
		node* trailNode;
		node* p;
	
		/* iterate the list and delete the nth node until currentChild points to itself */
		while(currentChild != NULL && currentChild->next != currentChild){
			for(unsigned i = 0; i < n; i++){
				trailNode = currentChild;
				currentChild = currentChild->next;
			}		
			/* delete this child */
			trailNode->next = trailNode->next->next;
			p = currentChild;
			currentChild = currentChild->next;
			free(p);
		}
		/* only 1 node remaining -- this is the solution */
		int solution = currentChild->childNum;
		free(currentChild);
						
		return solution;
	}	
}


int main(void){
	unsigned size = 0;
	unsigned n = 0;
	
	do{
		printf_s("How many children are in the circle -- must be > 0: ");
		scanf_s("%u", &size);
		printf_s("Remove every nth child -- value for n must be > 0: ");
		scanf_s("%u", &n);
		printf_s("\n\n");
	}while(size < 1 || n < 1);
		
	printf_s("Computing the answer...");
	printf_s("\n\n\nChild number %li is the winner.", findSolution(size, n));

	for(;;);
	return 0;
}

[0xDEADBEEF]

Glad you got it sorted.

[AbhishekMaheshwari]

Assume link list is circular link list, then have two functions like this and call eliminate with the index you want to skip after each execution.

public int RemoveAt(int index)
{
int value = 0;
Node current = first;
do
{
if (current.Counter == index)
{
value = current.Data;
}
current = current.Next;
} while (current != first);
return value;
}

public int Eliminate(int m)
{
int value = 0;
Node current = first;
Node nextNode;

Reference:- http://tech.queryhom...ing-linked-list