Deleting first items in lists located in an array

Dev Shed Forums Sponsor:

September 2nd, 2003, 02:26 PM

CMorjan

Junior Member

Join Date: Sep 2003

Posts: 7

Time spent in forums: < 1 sec
Reputation Power: 0

Deleting first items in lists located in an array

I am writing a genetic simulation program, am fairly new to C, and especially new to using pointers.

My problem is working with an array of lists. I've successfully added elements to each list within the array, but have only been able to delete elements if they are not the first in the list. The program compiles fine, but crashes as soon as I try to free the memory for the first element in one of the lists. Probably this is due to my inexperience in properly using pointers for double (or higher?) indirection. The program is rather long so I'm including only the relevant excerpts. The major relevant part on deleting list items is taken directly from good ol' Dietel & Dietel's C:How to Program 3rd ed. (Fig.12.3 to be exact). Although they go over using double indirection to delete the first element in a list, their example doesn't deal with lists within an array. I would greatly appreciate any advice, thanks!

****
#define NPOPS 2

struct listNode {
float genotypes[ 4 ];
struct listNode *nextPtr;
};

typedef struct listNode ListNode;
typedef ListNode *ListNodePtr;

void initialize( ListNode array[]);
void insert( ListNodePtr *, float, float, float, float );
void delete( ListNodePtr * );

ListNode Pop[ NPOPS ];

int main()
{
ListNodePtr startPtr = NULL;

initialize( Pop );

startPtr = &Pop[0];

insert( &startPtr, 1, s, 0, 0 );

/* Then I manipulate the lists through some genetic simulations, these work fine */

delete (&startPtr );

return 0;
}

/* Here is the part that is causing me problems, the problem part is highlighted in red (I can't get this vB thing to work right with indenting, I've never used it before, sorry! )*/

void delete ( ListNodePtr *sPtr )
{
ListNodePtr previousPtr, currentPtr, tempPtr;

if ( 0 == (*sPtr)->genotypes[0] ) {
tempPtr = *sPtr;
*sPtr = ( *sPtr )->nextPtr;
free( tempPtr );
}

previousPtr = *sPtr;
currentPtr = ( *sPtr )->nextPtr;

while ( currentPtr != NULL && currentPtr->genotypes[0] != 0 ) {
previousPtr = currentPtr;
currentPtr = currentPtr->nextPtr;
}

if ( currentPtr != NULL ) {
tempPtr = currentPtr;
previousPtr->nextPtr = currentPtr->nextPtr;
free( tempPtr );
}
}

September 2nd, 2003, 02:55 PM

f'lar

ASP.Net MVP

Join Date: Aug 2003

Location: WI

Posts: 4,378

Time spent in forums: 1 Month 2 Weeks 2 Days 11 h 5 m 4 sec
Reputation Power: 1509

This smells like homework, so I'm not including any actual code. If it's not, sorry for the presumption.

Before you advance your pointer to the next pointer in the list you need to make sure that there is a next pointer in the list. This may not be what's causing your problem, but it's still something you should check for.

__________________
Primary Forum: .Net Development
Holy cow, I'm now an ASP.Net MVP!

[Moving to ASP.Net] | [.Net Dos and Don't for VB6 Programmers]

http://twitter.com/jcoehoorn

September 3rd, 2003, 09:12 AM

CMorjan

Junior Member

Join Date: Sep 2003

Posts: 7

Time spent in forums: < 1 sec
Reputation Power: 0

Thanks, but it still won't remove the first item on the list, even when there are subsequent items. By the way, this isn't homework, I'm doing postdoctoral research...

September 3rd, 2003, 12:25 PM

murugesan

Dinesh_P_V

Join Date: Aug 2003

Location: India

Posts: 259

Time spent in forums: 12 h 1 m 3 sec
Reputation Power: 0

Re:Deleting first items in lists located in an array

I got the thing what you have done. Definitely free( tempPtr ); will not work
This is because
startPtr = &Pop[0];
points to statically allocated memory and not a dynamic one.
Static memory cannot be freed by free function.
You can use free only when you allocate dynamic memory allocation
using
malloc or calloc or new.

-Murugesan

September 3rd, 2003, 12:56 PM

CMorjan

Junior Member

Join Date: Sep 2003

Posts: 7

Time spent in forums: < 1 sec
Reputation Power: 0

OK, that makes sense! I might need to initialize my array in a different way, then, or try to get around it by assigning the values of the first element of the list to the values of the second one (and then getting rid of the second element). Thanks!

September 3rd, 2003, 01:22 PM

CMorjan

Junior Member

Join Date: Sep 2003

Posts: 7

Time spent in forums: < 1 sec
Reputation Power: 0

Yep, here is the code that works. I assigned the first element in the list the values in the second item, and then it deletes the second item. For the purposes of my program, I'll never have an empty list in the array (like trying to delete the first item without a second one existing), so it shouldn't cause any more problems. Here's the code:

Code:

#define NPOPS 2		  /* number of populations */

struct listNode {
   float genotypes[ 4 ];
   struct listNode *nextPtr;
};


typedef struct listNode ListNode;
typedef ListNode *ListNodePtr;

void delete( ListNode array[] );
ListNode Pop[ NPOPS ];

int main()
{
   ListNodePtr startPtr = NULL;
   
   startPtr = &Pop[0]; 

   delete( Pop );

   return 0;
}

void delete ( ListNode Pop[] )
{
   ListNodePtr previousPtr, currentPtr, tempPtr, sPtr;
   int i, j;

   for (i=0; i<= NPOPS-1; i++ ) {

      sPtr = &Pop[i];

      previousPtr = sPtr;
      currentPtr = ( sPtr )->nextPtr;

      if ( 0 == (sPtr)->genotypes[0]) {
         currentPtr = ( sPtr )->nextPtr;
         for (j=0; j<=3; j++ )
         previousPtr->genotypes[j]=currentPtr->genotypes[j];
         currentPtr->genotypes[0] = 0;
      }

      previousPtr = sPtr;
      currentPtr = ( sPtr )->nextPtr;

      while ( currentPtr != NULL && currentPtr->genotypes[0] != 0 ) {
         previousPtr = currentPtr;
         currentPtr = currentPtr->nextPtr;
      }

      if ( currentPtr != NULL ) {
         tempPtr = currentPtr;
         previousPtr->nextPtr = currentPtr->nextPtr;
         free( tempPtr );
      }
   }
}

September 3rd, 2003, 11:24 PM

murugesan

Dinesh_P_V

Join Date: Aug 2003

Location: India

Posts: 259

Time spent in forums: 12 h 1 m 3 sec
Reputation Power: 0

Deleting first items in lists located in an

I think you don't get me.

For the program to work
what you should do is
dont assign startptr to &pop[0]
instead assign it to
(Listnode) malloc(sizeof(Listnode));
Similarly assign the nextptr value also in the same manner.
That will work

-Murugesan

September 3rd, 2003, 11:26 PM

murugesan

Dinesh_P_V

Join Date: Aug 2003

Location: India

Posts: 259

Time spent in forums: 12 h 1 m 3 sec
Reputation Power: 0

Re:Deleting first items in lists located in an

September 4th, 2003, 10:29 AM

CMorjan

Junior Member

Join Date: Sep 2003

Posts: 7

Time spent in forums: < 1 sec
Reputation Power: 0

Thanks, that would have worked, too...in the meantime, I fixed one of the more basic problems that I had with the program, I should have made an array of pointers to ListNodes, not an array of ListNodes. I also could get rid of an extra function that initialized the array, and now lists are added using the same insert function that I had before. Finally the delete function works properly. Who knows if I'll ever *really* understand pointers!! Here's what works now:

Code:

#define SIZE 10
#define NPOPS 2	

struct listNode {
   float genotypes[ 4 ];
   struct listNode *nextPtr;
};


typedef struct listNode ListNode;
typedef ListNode *ListNodePtr;

void insert( ListNodePtr *, float, float, float, float );
void delete( ListNodePtr * );
ListNodePtr Pop[ NPOPS ];

int main()
{
   ListNodePtr startPtr = NULL;

   for ( i = 0; i <= NPOPS - 1; i++ )
    Pop[i] = NULL;
   
   for ( i = 1; i <= NPOPS-1; i++ ) 
      insert (&(Pop[i]), SIZE, 0, 0, 0); 

   for ( i = 0; i <= NPOPS - 1; i++ )
      delete( &(Pop[i]) );

   return 0;
}

void delete ( ListNodePtr *sPtr )
{
   ListNodePtr previousPtr, currentPtr, tempPtr;
   int i, j;

      if ( 0 == (*sPtr)->genotypes[0]) {
         tempPtr = *sPtr;
         *sPtr = ( *sPtr )->nextPtr;
         free( tempPtr );
      }

      previousPtr = *sPtr;
      currentPtr = ( *sPtr )->nextPtr;

      while ( currentPtr != NULL && currentPtr->genotypes[0] != 0 ) {
         previousPtr = currentPtr;
         currentPtr = currentPtr->nextPtr;
      }

      if ( currentPtr != NULL ) {
         tempPtr = currentPtr;
         previousPtr->nextPtr = currentPtr->nextPtr;
         free( tempPtr );
      }
}

#10

September 4th, 2003, 11:27 PM

murugesan

Dinesh_P_V

Join Date: Aug 2003

Location: India

Posts: 259

Time spent in forums: 12 h 1 m 3 sec
Reputation Power: 0

Deleting first items in lists located in an array

Hello CMorjan,
I dont get what you are doing here in the delete function
previousPtr = *sPtr;
currentPtr = ( *sPtr )->nextPtr;
while ( currentPtr != NULL && currentPtr->genotypes[0] !=
0 )
{
previousPtr = currentPtr;
currentPtr = currentPtr->nextPtr;
}
if ( currentPtr != NULL )
{
tempPtr = currentPtr;
previousPtr->nextPtr = currentPtr->nextPtr;
free( tempPtr );
}
Already you are clearing the memory in the for loop of
for ( i = 0; i <= NPOPS - 1; i++ )
delete( &(Pop[i]) );
This will clear pop[i] in the first step of the delete function. After that why you want to clear the other things ? in delete function
The code u wrote won't work
Ok Let me know what you want to do?
I think you want to create a linear linked list. Is that right ?

-Murugesan

#11

September 8th, 2003, 10:21 AM

CMorjan

Junior Member

Join Date: Sep 2003

Posts: 7

Time spent in forums: < 1 sec
Reputation Power: 0

Hi Murugesan,

what I'm doing in that section of the delete function

Code:

previousPtr = *sPtr; 
currentPtr = ( *sPtr )->nextPtr; 
while ( currentPtr != NULL && currentPtr->genotypes[0] != 
0 ) 
{ 
previousPtr = currentPtr; 
currentPtr = currentPtr->nextPtr; 
} 
if ( currentPtr != NULL ) 
{ 
tempPtr = currentPtr; 
previousPtr->nextPtr = currentPtr->nextPtr; 
free( tempPtr ); 
}

is deleting any other member of the list that has a "0" in a particular cell...I don't think the for loop
for (i=0; i<= NPOPS-1; i++ )
delete( &Pop[i])) deletes the whole list in the first step of the delete function, just the first member of the list at address pop[i] (and then assigns the second member of the list as the new first member at that particular address in pop[i]). Does this make sense? It's working fine in my program so far...
Thanks!
-c

#12

September 8th, 2003, 12:30 PM

murugesan

Dinesh_P_V

Join Date: Aug 2003

Location: India

Posts: 259

Time spent in forums: 12 h 1 m 3 sec
Reputation Power: 0

Re: Deleting first items in lists located in an array

I am not able to collect the point what you say.
Ok.
Let me have some walk on linked list.
I think u need to create a linked list where each node has some variable to be stored(in your case genotypes)
For this you can have the following code (REMEMBER I had NOT compiled it)

struct listNode {
float genotypes[ 4 ];
struct listNode *nextPtr;
};

typedef struct listNode ListNode;
typedef ListNode *ListNodePtr;

//There is no need for the initialize function. You can do it in
//the insert function itself also no need to to use the array

int main()
{
ListNodePtr startPtr = (ListnodePtr)malloc(sizeof(ListNode));

...........
}
void insert( ListNodePtr * sptr, float, float, float, float )
{
while(sptr->nextptr!=NULL)
sptr=sptr->nextptr
sptr->nextptr=(ListnodePtr)malloc(sizeof(ListNode));
sptr=sptr->nextptr;
//assign values to sptr members
sptr->next=NULL;
}
void delete(ListNodePtr * sptr)
{
Listnodeptr tmp=sptr->next;
while(1)
{
delete sptr;
sptr=tmp;
if(sptr==NULL)
break;
tmp=sptr->next
}
}

HTH
-Murugesan

#13

September 9th, 2003, 04:25 PM

CMorjan

Junior Member

Join Date: Sep 2003

Posts: 7

Time spent in forums: < 1 sec
Reputation Power: 0

Hi Murugesan,

Thanks! I also found that the initialize function wasn't needed, once I got some other issues straightened out. I'm still using an array because my program simulates many subpopulations arranged in a grid, so a 2 X 2 array (Pop) with each address as a list of subpopulation genotypes seems to be most convenient. At any rate, my program is running...I'll keep my fingers crossed...

-C

Deleting first items in lists located in an array

Developer Shed Advertisers and Affiliates