Back to General and Gameplay Programming

linked list problem

General and Gameplay Programming Programming

Started by sut June 05, 2002 01:04 PM

8 comments, last by sut 21 years, 10 months ago

sut

122

Author

June 05, 2002 01:04 PM

i have made the following simple program that uses a link list, however it doesn''t work. here''s the code: (by the way, i know storing the first list in every other list is a waste, but i''ll change that later)

  
#include <stdio.h>

typedef struct list_element
{
  struct list_element *start;
  int data;
  struct list_element *previous;
  struct list_element *next;
} list_element;


add_to_list(list_element *the_list, int data)
{
  list_element *new_element;
  new_element = (list_element*)malloc(sizeof(list_element));
  new_element->data = data;

  if(the_list == NULL)
  {
    new_element->start = new_element;
    new_element->previous = NULL;
    new_element->next = NULL;
    the_list = new_element;
    printf("it''s a new list\n");
  }
  else
  {
    new_element->start = the_list->start;
    new_element->next = the_list->next;
    the_list->next = new_element;
    new_element->previous = the_list;
    printf("it''s an old list\n");
  }
}


int main(int argc, char *argv[])
{
  list_element *enemy_list = NULL;

  add_to_list(enemy_list, 4);
  add_to_list(enemy_list, 2);
  add_to_list(enemy_list, 5);
  add_to_list(enemy_list, 12);

  return 1;
}

now when i run this it writes "it''s a new list" four times, however shouldn''t it only write that once, then the next three should be "it''s an old list"?

Ekas78

122

June 05, 2002 01:13 PM

The easist way to fix this is to print "thru" all the links. That will show you whats wrong.

______________________________Only dead fish go with the main-stream.

sut

122

Author

June 05, 2002 01:19 PM

well i assumed that because the list always seems to be NULL, each link will be isolated (as the next and previous values are set to NULL) and therefore can''t be cycled through...

krad7

122

June 05, 2002 01:20 PM

The problem is simple...
ur addlist should either return a pointer to list_element created (just return the first node itself) or the argument should be a double pointer like shown below..
add_to_list(list_element **the_list, int data)

OR

list_element* add_to_list(list_element *the_list, int data)..

so in the main, for the first method call something like this..
add_to_list(&enemy_list,data);

for the 2nd one,

enemy_list = add_to_list(enemy_list,data)..

also, ur else part in the add_to_list function is incorrect.. check it out buddy.. simple error..

Slow and steady wins the race.

[edited by - krad7 on June 5, 2002 6:40:41 PM]

Slow and steady wins the race.

bangz

119

June 05, 2002 01:23 PM

The problem must lie with the IF statement within add_to_list

  if(the_list == NULL)

i dont think you can do that sort of comparision on a struct, although u can do it on a variable within it.

the following should work ok as long as none of ur values are ever NULL...

  if(the_list->data == NULL)

hope this helps,
bangz.

FrikkaSoft

122

June 05, 2002 01:34 PM

This is a double linked, circular, template list with dummy-node.
All comments are in Icelandic though.
And yeah, this is a long post...

  // þessi klasi er hringdengdur tvítengdur listi með dummy-node.// #include <iostream>using namespace std;template <class T>class C2TListi{	template <class T>	struct node	{		T data;		node<T>* next;		node<T>* prev;		// Smiður sem frumstillir data, next og prev. Sá sami og var í seinasta lokaprófi.		// Ef engin færibreyta er gefin er kallað í færibreytulasan smið fyrir tagið T.		node( const T& data=T(), node* next_p=0, node* prev_p=0)		: data(data), next(next_p), prev(prev_p)		{			// Ef annarhvor eða báðir bendarnir eru 0, þá neda þeir á sjálfan sig			if (next_p == 0) next = this;			if (prev_p == 0) prev = this;		}	};		// skilar bendi á réttan hnút miðað við data	node<T>* FindBefore(const T& data);	// skilar bendi á hnút á ákveðnu indexi	node<T>* GetAt( int index);		// bendir á tómt stak sem er notað sem dummy-node	node<T>* head;	// fjöldi staka í listanum	int  size;public:	// færibreytulaus smiður	C2TListi()  { size=0; head=new node<T>(); }	// afritatökusmiður eða copy constructor	C2TListi( C2TListi<T>& l) { size=0; head=new node<T>(); *this = l; }	// eyðir eða destructor	~C2TListi() 	{		while(size) RemoveAt(size-1); 		head->next=0; head->prev=0; delete head; head=0; 	}		// almennar aðgerðir	node<T>* AddLast(T data);	node<T>* AddInOrder(T data);	node<T>* Insert(T data, int index);	node<T>* RemoveAt(int index); 	int GetSize() { return size; } const	// yfirskrifaðir virkjar	friend ostream& operator << (ostream& out, const C2TListi& l);	friend bool operator == (C2TListi& lhs,C2TListi& rhs);	C2TListi<T>& operator = (C2TListi<T>& rhs); };///////////////////////////////////////////////////////////////////////////////////template <class T>C2TListi<T>::node<T>* C2TListi<T>::AddLast(T data){	// Set stakið aftast. Eftir þessa línu verða	// newnode->next = head og newnode->prev = head->prev	node<T>* newnode = new node<T>(data, head, head->prev );		// uppfærum þá seinasta stakið þannig að það bendi á newnode,	// newnode er þá seinasta stakið	head->prev->next = newnode;	// uppfærum fyrsta stakið þannig að það bendi á seinasta stakið	// sem nú er newnode	head->prev = newnode;	size++;	return newnode;}///////////////////////////////////////////////////////////////////////////////////template <class T>C2TListi<T>::node<T>* C2TListi<T>::AddInOrder(T data){		// fáum bendi á hnútinn sem á að vera á undann nýja hnútnum	node<T>* afterme = FindBefore(data);	// athugum hvort listinn er tómur, bætum þá bara aftast	if (afterme == 0) 		return AddLast(data);		// Frumstillum data, next og prev í newnode, mjög líkt og í AddLast	node<T>* newnode = new node<T>(data, afterme->next, afterme );		// uppfærum hnútana tvo sem eiga að koma á undan og eftir newnode	afterme->next->prev = newnode;	afterme->next = newnode;	size++;	return newnode;}///////////////////////////////////////////////////////////////////////////////////template <class T>C2TListi<T>::node<T>* C2TListi<T>::FindBefore(const T& data){	// þetta fall skilar bendi á stak sem þessi tala (data) á að 	// koma á eftir, raðað er í hækkandi röð.	// ef listinn er tómur, þá skila 0	if (size==0) return 0;	// notum temp til að ferðast í gegnum listann	node<T>* temp = head->next;	// á meðan við erum ekki kominn út á enda listans og við erum	// ekki kominn á réttan stað í listanum	for(int i=0; i<size && data>temp->data; i++, temp=temp->next);	// okkur er algeg sama hvar á að setja þetta, skilum því bara hnútnum	// á undan. Ef ekki væri notaður dummy-node væru einhverjar if setningar 	// settar hér	return temp->prev;	}///////////////////////////////////////////////////////////////////////////////////template <class T>C2TListi<T>::node<T>* C2TListi<T>::GetAt( int index ){	if (index < 0 || index > size-1) 		return 0;		node<T>* temp=head->next;	// athugum hvort það er fljótlegra að fara áfram eða afturábak	if (index <= (size-1)/2)		for(int i=0; i<index; temp=temp->next, i++);	else		for(int i=0; i<=(size-index); temp=temp->prev, i++);	return temp;}///////////////////////////////////////////////////////////////////////////////////template <class T>C2TListi<T>::node<T>* C2TListi<T>::RemoveAt(int index){	// fáum bendi á þann sem á að eyða	node<T>* removeme = GetAt(index);		// ef satt þá hefur index líklega verið vitlaust	if (removeme == 0) 		return 0;	// fáum bendi á hnútinn sem á að skila, sem er hnúturinn á undan 	// þeim sem á að eyða	node<T>* temp = removeme->prev;		// uppfærum hnútana tvo sem eru á undan og eftir þannig að þeir bendi	// fram hjá removeme hnútnum	removeme->prev->next = removeme->next;	removeme->next->prev = removeme->prev;	// svona til öryggis	removeme->next = 0;	removeme->prev = 0;	// eyðum honum loks	delete removeme;	removeme = 0;	size--;	// skilum bendinum á undan 	return temp;	}///////////////////////////////////////////////////////////////////////////////////template <class T>C2TListi<T>::node<T>* C2TListi<T>::Insert(T data, int index){	if (index == 0)	{		// bætum við hnút fremst, eða strax á eftir hausnum		node<T>* newnode = new node<T>(data, head->next, head);				// uppfærum hnútana tvo sem eiga að koma á undan og eftir newnode		head->next->prev = newnode;		head->next = newnode;		size++;					return newnode;	}	else	{		// fáum bendi á hnútinn sem á að vera á undan innsetningunni		node<T>* afterme = GetAt(index-1);			// ef satt þá hefur index líklega verið vitlaust		if (afterme == 0) 			return 0;		// Frumstillum data, next og prev í newnode, mjög líkt og í AddLast		node<T>* newnode = new node<T>(data, afterme->next, afterme);		// uppfærum hnútana tvo sem eiga að koma á undan og eftir newnode		afterme->next->prev = newnode;		afterme->next = newnode;		size++;				return newnode;	}}///////////////////////////////////////////////////////////////////////////////////template <class T>ostream& operator << (ostream& out, const C2TListi<T>& l){	// sæki bendi á fyrsta hnútinn í listanum l	C2TListi<T>::node<T>* temp = l.head->next;		// fer í gegnum listann og skrifa út gildið í hverjum hnút.	for(int i=0; i<l.size; i++)	{		cout << temp->data << endl;		temp = temp->next;	}	// hægt að láta operator << skila void, en nú er hægt að 	// gera "cout << l1 << l2"	return out;}///////////////////////////////////////////////////////////////////////////////////template <class T>C2TListi<T>& C2TListi<T>::operator = (C2TListi<T>& rhs){	if (this == &rhs)		return *this;		// hreinsum listann þannig að aðeins hausinn (dummy-node) er eftir	while(size) RemoveAt(size-1); 		head->next=head; 	head->prev=head; 		// förum í gegnum rhs listann og kóperum alla hnútana þar yfir í þennan lista	for(int i=0; i<rhs.size; i++)		Insert(rhs.GetAt(i)->data, i);	return *this;}///////////////////////////////////////////////////////////////////////////////////template <class T>bool operator == (C2TListi<T>& lhs, C2TListi<T>& rhs){	if (&lhs == &rhs) 		return true;	if (lhs.GetSize() != rhs.GetSize())		return false;		// fáum bendi á fyrstu hnútana í hvorum listanum	C2TListi<T>::node<T>* lhstemp = lhs.head->next;	C2TListi<T>::node<T>* rhstemp = rhs.head->next;	// förum í gegnum öll stökin og berum saman milli lista, ef data er á einhverjum 	// stað ekki eins eru listarnir ekki nákvæmlega eins, þá skilum við fara false	for(int i=0; i<lhs.GetSize(); i++)	{		if (lhstemp->data != rhstemp->data)			return false;		lhstemp = lhstemp->next;		rhstemp = rhstemp->next;			}	// öll stökin eru eins, skilum true	return true;}///////////////////////////////////////////////////////////////////////////////////

Friðrik Ásmundsson

krad7

122

June 05, 2002 05:42 PM

quote:Original post by bangz
The problem must lie with the IF statement within add_to_list

if(the_list == NULL)

i dont think you can do that sort of comparision on a struct, although u can do it on a variable within it.

the following should work ok as long as none of ur values are ever NULL...

if(the_list->data == NULL)

hope this helps,
bangz.

the_list is a pointer, so you should check if its NULL or not, checking data might give seg faults incase the_list is NULL..

Slow and steady wins the race.

[edited by - krad7 on June 5, 2002 6:43:58 PM]

[edited by - krad7 on June 5, 2002 6:44:30 PM]

Slow and steady wins the race.

bangz

119

June 06, 2002 07:48 AM

damn... u got me there!

is there any way of getting code from the source boxes? When I copy and paste it shoves it all on one line :S

bangz.

Stoffel

250

June 06, 2002 08:28 AM

Edit (or quote?) the post, then copy/paste the code from there.

bangz

119

June 06, 2002 12:05 PM

here''s a working version

  #include <stdio.h>#include <stdlib.h>typedef struct list_element{  struct list_element *start;  int data;  struct list_element *previous;  struct list_element *next;} list_element;list_element *add_to_list(list_element *the_list, int data){  list_element *new_element;  new_element = (list_element*)malloc(sizeof(list_element));  new_element->data = data;  if(the_list == NULL)  {    new_element->start = new_element;    new_element->previous = NULL;    new_element->next = NULL;    the_list = new_element;    printf("it''s a new list\n");  }  else  {    new_element->start = the_list->start;    new_element->next = the_list->next;    the_list->next = new_element;    new_element->previous = the_list;    printf("it''s an old list\n");  }  return new_element;}int main(int argc, char *argv[]){  list_element *enemy_list = NULL;  enemy_list=add_to_list(enemy_list, 4);  enemy_list=add_to_list(enemy_list, 2);  enemy_list=add_to_list(enemy_list, 5);  enemy_list=add_to_list(enemy_list, 12);  return 1;}

add_to_list returns new_element* which then gets stored as enemy_list when its called. The problem was that enemy_list wasn''t getting updated, i''ve tested it and it works!

hope this helps,
bangz.

linked list problem

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

linked list problem

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines