LinuxQuestions.org
Support LQ: Use code LQ3 and save $3 on Domain Registration
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 02-01-2010, 11:51 AM   #1
HarryBoy
Member
 
Registered: Apr 2008
Distribution: MontaVista Linux Version 4.0.1, Professional Edition
Posts: 215

Rep: Reputation: 16
Get a number between two numbers question


I need help with some c.

I have some code that opens a directory and reads in the names of files which are e.g. 0001, 0002, 0003 up to 9999.

I need to get all these numbers and then generate a new number that is not one of these numbers already.

here is my code to check the files in the directory

DIR *d;
struct dirent *dir;
int i = 0;

d = opendir( "//mydir//" );
if( d )
{

printf("Directory stream is now open\n");

while ((dir = readdir(d)) != NULL)
{

int num = atoi(dir->d_name);
printf("Filename=%s number=%d\n", dir->d_name, num);

if( num > 0 && num < 9999)//
{
//I need to add all my numbers to an array or list
// and then get a new number which is between 0 and 9999 //that does not include any of my added numbers
//Preferably the next logical number e.g. if i have 0,1,2,3 then i should get 4 as my next number

}

}


Can someone help me??

thanks
 
Old 02-01-2010, 12:38 PM   #2
Alien_Hominid
Senior Member
 
Registered: Oct 2005
Location: Lithuania
Distribution: Hybrid
Posts: 2,247

Rep: Reputation: 53
Create an int array n[10000] and set the value to 1 if the name is used, otherwise 0.

as in your example:
Code:
n[0] = 1;
n[1] = 1;
n[2] = 1;
n[3] = 1;
n[4] = 0;
and loop through searching for 0.

Another better and more difficult solution would be creating a singly linked list of unused names, which you could manage (add/remove members) dynamically.
Code:
struct slist
{
  int value;
  struct slist *bigger;
}

Last edited by Alien_Hominid; 02-01-2010 at 12:39 PM.
 
Old 02-01-2010, 01:31 PM   #3
carbonfiber
Member
 
Registered: Sep 2009
Location: Sparta
Posts: 237

Rep: Reputation: 46
HarryBoy: Are the names of the files represented by consecutive numbers? (is it possible to have only the following file names: 0001, 0002, 0004)

Alien_Hominid: why would the 'linked list' solution be better in this particular case?
 
Old 02-01-2010, 01:44 PM   #4
HarryBoy
Member
 
Registered: Apr 2008
Distribution: MontaVista Linux Version 4.0.1, Professional Edition
Posts: 215

Original Poster
Rep: Reputation: 16
Thanks guys, the names can be any numer e.g. 0001, 0002, 0099, 1234, 4567, 9999.

here is an attempt by me, please could you guys 'code review' it for me if possible?

Code:
const char* getstreamFileNo( void )
{
   char filename[4]; //holds the new file name
   DIR           *d;
   struct dirent *dir;
   int count = 0;
   int filenumbers[10000];
   int newfilenumber = 0;

   d = opendir( "//mydir//" );
   if( d )
   {

	 while ((dir = readdir(d)) != NULL)
	 {
	   int num = atoi(dir->d_name);

	   if( num > 0 && num < 9999)//Add number to
	   {
		filenumbers[count] = num;
		count++;
	   }

	 }

	 int i,j = 0 ;
	 bool bfound = false;
	 for( i=1; i<10000; i++ )//go through all numbers from 1-9999
	 {
	   bfound = false;
	   for( j=0; j<count; j++ )//go through all numbers in our array
	   {
		 if(i == filenumbers[j])
		 {
			 bfound = true;
			 break;
		 }
	   }
	   if( !bfound )
	   {
		 newfilenumber = i;
		 break;
	   }
	 }

	sprintf(filename,"%04d\n",newfilenumber);

     closedir(d);
   }

  return filename;
}

Last edited by HarryBoy; 02-01-2010 at 01:47 PM.
 
Old 02-01-2010, 01:51 PM   #5
PTrenholme
Senior Member
 
Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,153

Rep: Reputation: 331Reputation: 331Reputation: 331Reputation: 331
Actually, a double-linked list:
Code:
struct dlist {
  dirent * entry;
  struct dlist * prior;
  struct dlist * post;
}
might be a more general solution. Then a tree search could be used to find the "next" gap which (for a large set of directory entries) would be more efficient than a sequential search. By using a dirent structure pointer (properly allocated, of course) in the list, the solution would be easily generalized to non-numeric file names.
 
Old 02-01-2010, 02:07 PM   #6
PTrenholme
Senior Member
 
Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,153

Rep: Reputation: 331Reputation: 331Reputation: 331Reputation: 331
Re your code:
  • You will read the whole directory every time the function is called.
  • Your error condition is to return "0000" as the file name. It might make the calling program more efficient if you set an error flag that could be checked.
  • If, instead, you followed the suggestion of Alien_hominid, you would initialize filenumbers to all zeros, and then, when a number is found, set filenumber[num]=1 Then your check would be for (j=num;j<10000 && filenum[j];++j) rather than a nested loop.

Last edited by PTrenholme; 02-01-2010 at 02:08 PM.
 
Old 02-01-2010, 02:13 PM   #7
carbonfiber
Member
 
Registered: Sep 2009
Location: Sparta
Posts: 237

Rep: Reputation: 46
We are talking about finding a "missing number" between 1 and 9999. I'd take the easy array solution without thinking twice about it. I also consider it the superior approach because of the specifics of the task.

HarryBoy: Keep working on it, reread Alien_Hominid's initial suggestion.
 
Old 02-01-2010, 02:32 PM   #8
aspire1
Member
 
Registered: Dec 2008
Distribution: Ubuntu
Posts: 61

Rep: Reputation: 22
You could try using scandir as well, code not really tested so usual disclaimers apply:

Code:
int main(){
	
	int currentFreeNum = 1;

	
	struct dirent **namelist;
	int index = 0;
	
	int foundNumber = 0;

	int numOfDirs = scandir( ".", &namelist, 0, alphasort );


	if( numOfDirs> 0 )
	{

               while ( index < numOfDirs && ! foundNumber )
               {

                  int num = atoi( namelist[ index ]->d_name );

		  if( num > 0 && num < 9999){
			  
			  if( currentFreeNum < num ){
			  
				  foundNumber = 1;
			  }
			  else
			  {
				  currentFreeNum++;  
			  }
			  
			   printf("Filename %s number=%d\n", namelist[index]->d_name, num);
			   free( namelist[ index ] );
		  }
		  
              index++;
         }
	 
	 free( namelist );
	}
	
	if( foundNumber ){
		
		printf( "You can use number = %d\n", currentFreeNum );
	}
	else
	{
		printf( "No free numbers found.");
	}
}
 
Old 02-02-2010, 11:16 AM   #9
Alien_Hominid
Senior Member
 
Registered: Oct 2005
Location: Lithuania
Distribution: Hybrid
Posts: 2,247

Rep: Reputation: 53
Singly linked list is enough because:
  • OP needs a new number that is not one of already available numbers.
  • We select smallest number and remove it from the list - we do not need to loop through, we just take the first element.
 
Old 02-02-2010, 11:29 AM   #10
carbonfiber
Member
 
Registered: Sep 2009
Location: Sparta
Posts: 237

Rep: Reputation: 46
That seems to imply creating the complete list first, also, assume you read number N, how do you remove the associated element from the list? A better question would be: what is the representation of the singly-linked list?
 
Old 02-02-2010, 12:04 PM   #11
Alien_Hominid
Senior Member
 
Registered: Oct 2005
Location: Lithuania
Distribution: Hybrid
Posts: 2,247

Rep: Reputation: 53
http://en.wikipedia.org/wiki/Linked_...y-linked_lists

No, you read through directory listing. Assume 4 is missing, you add it to the list, then you find that 9 is missing, you add it to the list, etc, etc...
You get 4 -> 9 -> ...

While doubly linked list would be:

4 <-> 9 <->, which is unecessary because you always take lowest number first.
 
Old 02-02-2010, 12:46 PM   #12
carbonfiber
Member
 
Registered: Sep 2009
Location: Sparta
Posts: 237

Rep: Reputation: 46
Ah. I got it, you were saying that a singly linked list would suffice given the choice between singly linked and doubly linked. Quite.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to filter out number of lines which are not constant in numbers. manya Programming 7 12-31-2009 07:25 PM
sequence of numbers, how to extract which numbers are missing jonlake Programming 13 06-26-2006 04:28 AM
max number multicast addresses and port numbers tara Programming 2 11-20-2005 06:53 PM
Question about owner and groups being displayed as numbers nukey Slackware 5 09-21-2005 10:47 AM
Port numbers and domain name question yanik Linux - Networking 2 09-01-2005 05:38 PM


All times are GMT -5. The time now is 04:02 AM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration