#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;
}
linked list problem
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)
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"?
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...
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]
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]
The problem must lie with the IF statement within add_to_list
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...
hope this helps,
bangz.
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.
This is a double linked, circular, template list with dummy-node.
All comments are in Icelandic though.
And yeah, this is a long post...
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;}///////////////////////////////////////////////////////////////////////////////////
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]
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.
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.
here''s a working version
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.
#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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement