Need help with doubly linked lists

Started by NerdJNerdBird March 02, 2002 09:09 AM

10 comments, last by NerdJNerdBird 22 years, 11 months ago

Author

122

March 02, 2002 09:09 AM

      
struct bullet{

  int type, charge;
  float x, y, angle, speed;
  bullet *next;
  bullet *prev;

};

bullet *curpoint;
bullet *head = NULL;

void deletebullet(bullet *todel){

  if (head == todel){
    if (head->next != NULL)
      head = head->next;
    else
      head = NULL;

    if (head != NULL)
      head->prev = NULL;

  } else if (todel-> next == NULL){
    todel->prev->next = NULL;
  } else{
    todel->next->prev = todel->prev;
    todel->prev->next = todel->next;
  }

  delete todel;
}

void addbullet(int type, float x, float y, float angle, float speed, int charge){
  
  bullet *newbullet = new bullet;

  newbullet->type = type;
  newbullet->x = x;
  newbullet->y = y;
  newbullet->angle = angle;
  newbullet->speed = speed;
  newbullet->charge = charge;
  newbullet->next = NULL;
  newbullet->prev = NULL;

  if (head == NULL){
     head = newbullet;
  } else{
    for(curpoint = head; curpoint->next != NULL; curpoint = curpoint->next)
    {}

    curpoint->next = newbullet;
    newbullet->prev = curpoint;
	
  }

}

What is wrong with this? If I comment out the delete todel; line it doesn't crash but if I leave it uncommented it crashes. The addbullet function is also included just incase i'm doing something wrong in there. Nothing crashes in there, just the delete bullet function. I've thought about this for a long time and I don't see whats wrong! Edited by - NerdJNerdBird on March 2, 2002 10:33:31 AM

LessBread

1,415

March 02, 2002 09:23 AM

quote:
Original post by NerdJNerdBird
Wait, how can I post this code so that it spaces correctly? I tryed manually spacing it without tabs and it doesn''t work. Sorry, i''ve never done it before.

To preserve spacing wrap with [code&] [/code]
To put code in a highlighted block wrap with [source] [/source]

  struct bullet{	int type, charge;	float x, y, angle, speed;	bullet *next;	bullet *prev;};bullet *curpoint;bullet *head = NULL;void deletebullet(bullet *todel){  if (head == todel){    if (head->next != NULL)      head = head->next;    else      head = NULL;    if (head != NULL)      head->prev = NULL;  } else if (todel-> next == NULL){    todel->prev->next = NULL;  } else{    todel->next->prev = todel->prev;    todel->prev->next = todel->next;  }  delete todel;}void addbullet(int type, float x, float y, float angle, float speed, int charge){    bullet *newbullet = new bullet;  newbullet->type = type;  newbullet->x = x;  newbullet->y = y;  newbullet->angle = angle;  newbullet->speed = speed;  newbullet->charge = charge;  newbullet->next = NULL;  newbullet->prev = NULL;  if (head == NULL){     head = newbullet;  } else{	for(curpoint = head; curpoint->next != NULL; curpoint = curpoint->next)	{}	curpoint->next = newbullet;	newbullet->prev = curpoint;	  }}

"I thought what I'd do was, I'd pretend I was one of those deaf-mutes." - the Laughing Man

NerdJNerdBird

Author

122

March 02, 2002 09:35 AM

Thank you! Now more details on my problem. If I shoot, like 10 times, the first 9 bullets delete correctly but the last bullet crashes my program. If I shoot 1 bullet when it is off the screen and supposed to be deleted it crashes. So if there is only 1 bullet in the linked list and it is trying to be deleted it crashes.

LessBread

1,415

March 02, 2002 09:42 AM

if (todel->next == NULL){todel->prev->next = NULL;

todel == todel->prev->next

you might be wiping the memory too soon

"I thought what I'd do was, I'd pretend I was one of those deaf-mutes." - the Laughing Man

NerdJNerdBird

Author

122

March 02, 2002 09:49 AM

else if (todel-> next == NULL){
todel->prev->next = NULL;

Correct me if I''m wrong but isn''t that just like saying, "If it''s at the end of the list (signifyed by the ->next being NULL) then you cut it off the list (by setting the previous node''s next pointer to be NULL). Thats the way I see it but I could definitely be wrong since my program crashes.

It only crashes on the last bullet though, which should be the head. So i''m thinking its a problem with the first conditional.

Darqtiger

122

March 02, 2002 09:53 AM

Here is my suggestion :

  struct bullet{int type, charge;float x, y, angle, speed;bullet *next;bullet *prev;};// here you had only the head.  if you don''t// have a tail you don''t really have a doubly// linked list because there is no where to // traverse backward frombullet *head = 0;bullet *tail = 0;void deletebullet(bullet *todel){    bullet *temp;    if(!head && !tail)        return;    for(temp = head; temp; temp = temp->next)    {        if(temp == todel)            break;    }    if(temp == head)    {        if(head->next)        {            head = head->next;            head->prev = 0;            delete todel;                    }        else        {            delete todel;            head = tail = 0;        }    }    else if(temp == tail)    {        if(tail->prev)        {            tail->prev->next = 0;            tail = tail->prev;                        delete todel;        }    }    else    {        if(temp->prev && temp->next)        {            temp->prev->next = temp->next;            temp->next->prev = temp->prev;            delete todel;        }    }}void addbullet(int type, float x, float y, float angle, float speed, int charge){    if (head == NULL)    {        head = new bullet();        head->type = type;        head->x = x;        head->y = y;        head->angle = angle;        head->speed = speed;        head->charge = charge;        head->next = 0;        head->prev = 0;        tail = head;    }     else    {        		tail->next	= new bullet();        tail->next->prev = tail;        tail->next->next = 0;        tail = tail->next;                tail->type = type;        tail->x = x;        tail->y = y;        tail->angle = angle;        tail->speed = speed;        tail->charge = charge;    }}

Hope that helps.

NerdJNerdBird

Author

122

March 02, 2002 10:05 AM

Hey darqtiger, your code works great! Thanks!

One thing I don't understand though is that for loop you have in the delete function. The end result is temp = todel right? Well if you delete that for loop and just do bullet *temp = todel; it crashes the program when you it trys to delete!

I think that is what is going wrong in my program maybe.

*update*
No, Thats not whats wrong. I have no idea! I tryed putting a forloop like you did but my program still crashes.

Edited by - NerdJNerdBird on March 2, 2002 11:10:27 AM

Darqtiger

122

March 02, 2002 10:25 AM

Well you are right that you don''t actually "need" the for loop.

I put that there out of force of habit. It basicly goes through the list to make sure that the node you want to delete is actually in the list.

If the node isn''t in the list then at the end of the list temp will be zero so all of the tests should fail and delete won''t actually get called on todel.

Are you only adding and deleting with those two functions? And do you only have one list?

NerdJNerdBird

Author

122

March 02, 2002 11:21 AM

Yes, those are the only 2 functions I have to deal with the linked list and right now that is the only linked list. I will have a linked list of enemies later in development though.

NerdJNerdBird

Author

122

March 02, 2002 11:31 AM

Actually, now its crashing even with your code. The first time it worked so I just thought it would work all the time but occasionally it will work with my code. So if you know your code is right and I know my code is right then perhaps it was another section of code?

  void updatebullets(){  bool deleteprev = false;  for(curpoint=head;curpoint!=NULL;curpoint=curpoint->next){    //modify bullets    if (deleteprev){	deletebullet(curpoint->prev);	deleteprev = false;    }		    if ((x < -SCREEN_X/2) || (x > SCREEN_X/2) ||	(y > SCREEN_Y/2) || (y < -SCREEN_Y/2)){	if (curpoint->next != NULL)	    deleteprev = true;				else	    deletebullet(curpoint);    }  }}

Need help with doubly linked lists

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Need help with doubly linked lists

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines