Archived

This topic is now archived and is closed to further replies.

linked list problem

This topic is 5668 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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"?

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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;
}

///////////////////////////////////////////////////////////////////////////////////

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites