|
| linkede lister (lektie hjælp) Fra : Andreas Hjordt |
Dato : 12-12-01 00:57 |
|
Hej folkens jeg skal i forbindelse med en opgave lave en klasse til
håndtering af linkede lister. Jeg kan dog ikke få min remove metode til at
fungere efter hensigten (den sletter ikke).
Jeg overvejer om det ikke ville være smartere at lave det sådan at jeg også
har en pointer til den forgående liste? Jeg har indtryg af at det på den
måde ville være nemmer at slette data fra listen.
mvh
Andreas Hjordt
Nedenstående er mit bud på en template for linkede lister.
<-------tllist.cpp------->
#include "iostream.h"
#include "tllist.h"
template<class T>
void disp(tllist<T> myll);
template<class T>
void info(tllist<T> ll);
int main()
{
tllist<int > ll;
info(ll);
ll.push_head(5);
ll.push_end(6);
ll.push_end(7);
ll.remove(7); //virker ikke???
disp(ll);
info(ll);
ll.gdata(6);
cout << ll.get() << "\n";
return(0);
}
template<class T>
void disp(tllist<T> myll)
{
myll.ghead();
do
{
cout << myll.get() << "\n";
} while(myll.next());
}
template<class T>
void info(tllist<T> myll)
{
cout << "empty? " << myll.empty() << "\n";
cout << "head? " << myll.head() << "\n";
cout << "end? " << myll.end() << "\n";
cout << "size: " << myll.size() << "\n\n";
}
</-------tllist.cpp------->
<-------tllist.h------->
#include <libio.h>
template<class T>
class tllist
{
private:
struct node
{
T data;
node<T>* ptr_next;
};
node* ptr_head;
node* ptr_current;
int amount;
public:
tllist() { ptr_head = NULL; amount = 0; };
// ~tllist();
//properties
bool empty() { return(ptr_head == NULL); };
bool head() { return(empty() ? true : (ptr_current == ptr_head)); };
bool end() { return(ptr_current->ptr_next == NULL); };
int size() { return(amount); };
//move methods
//move current one place forward returns false if end of list is reached
bool next();
void ghead() { ptr_current = ptr_head; };
void gend() { while(next()); };
//move current to data given as arg
bool gdata(T );
// void gindex(int index) { for(int i = 0; i < index && next(); i++); };
//any use???????
//insert methods
void push_head(T );
void push_end(T );
void push(T );
bool push(T , T );
//get method
T get() { return(ptr_current->data); };
//remove method
//should remove entry equal to arg and return bool if data was removed
bool remove(T );
};
#include "tllist.h.cpp"
</-------tllist.h------->
</-------tllist.h.cpp------->
template<class T>
bool tllist<T>::remove(T data)
{
if(empty() || !gdata(data))
{
return(false);
}
node* ptr_tmp = new node;
ptr_tmp = ptr_current;
do
{
if(ptr_current->ptr_next == ptr_tmp)
{
if(end())
{
ptr_current->ptr_next = NULL;
}
else
{
ptr_current->ptr_next = ptr_tmp->ptr_next;
}
delete ptr_tmp;
next();
}
} while(next());
return(false);
}
template<class T>
bool tllist<T>::gdata(T data)
{
ghead();
do
{
if(get() == data)
{
return(true);
}
} while(next());
return(false);
}
template<class T>
bool tllist<T>::push(T after, T new_data)
{
if(empty() || !gdata(after))
{
return(false);
}
push(new_data);
return(true);
}
template<class T>
void tllist<T>::push(T new_data)
{
if(end())
{
push_end(new_data);
}
else if(empty())
{
push_head(new_data);
}
else
{
node* ptr_tmp = new node;
ptr_tmp->data = new_data;
ptr_tmp->ptr_next = ptr_current->ptr_next;
ptr_current->ptr_next = ptr_tmp;
ptr_current = ptr_tmp;
amount++;
}
}
template<class T>
void tllist<T>::push_end(T new_data)
{
if(empty())
{
push_head(new_data);
}
else
{
gend();
node* ptr_tmp = new node;
ptr_tmp->data = new_data;
ptr_tmp->ptr_next = NULL;
ptr_current->ptr_next = ptr_tmp;
ptr_current = ptr_tmp;
amount++;
}
}
template<class T>
void tllist<T>::push_head(T new_data)
{
node* ptr_tmp = new node;
ptr_tmp->data = new_data;
ptr_tmp->ptr_next = ptr_head;
ptr_current = ptr_head = ptr_tmp;
amount++;
}
template<class T>
bool tllist<T>::next()
{
if(!end())
{
ptr_current = ptr_current->ptr_next;
return(true);
}
return(false);
}
</-------tllist.h.cpp------->
| |
Jonas Meyer Rasmusse~ (12-12-2001)
| Kommentar Fra : Jonas Meyer Rasmusse~ |
Dato : 12-12-01 01:37 |
|
Hejsa
"Andreas Hjordt" <ahj@trition.dk> wrote in message
news:3c169cc6$0$25388$edfadb0f@dspool01.news.tele.dk...
[klip](en masse overflødig kode... prøv kun at poste den kode du har
problemer med.)
> ptr_current->ptr_next = ptr_tmp->ptr_next;
Du har lige sat ptr_tmp = ptr_current,
hvorfor at det her er det samme som ptr_current->ptr_next =
ptr_current->ptr_next,
og det er også derfor du ikke får slettet dit element.
husk at hvis du har en liste
A->B->C
og du vil slette B fra listen, så vil du gøre det nogenlunde sådan her
temp = a->next //gem en peger til B
A->next = A->next->next //sæt A til at pege på C istedet for B
delete next //slet B
mvh Jonas
| |
Andreas Hjordt (12-12-2001)
| Kommentar Fra : Andreas Hjordt |
Dato : 12-12-01 10:09 |
|
"Jonas Meyer Rasmussen" <meyer_remove_@diku.dk> wrote in message
news:9v68ql$r6k$1@eising.k-net.dk...
> Hejsa
>
> "Andreas Hjordt" <ahj@trition.dk> wrote in message
> news:3c169cc6$0$25388$edfadb0f@dspool01.news.tele.dk...
> [klip](en masse overflødig kode... prøv kun at poste den kode du har
> problemer med.)
Jeg havde håbet på et par generelle kommentare så derfor al den kode.
>
> > ptr_current->ptr_next = ptr_tmp->ptr_next;
>
> Du har lige sat ptr_tmp = ptr_current,
> hvorfor at det her er det samme som ptr_current->ptr_next =
> ptr_current->ptr_next,
> og det er også derfor du ikke får slettet dit element.
>
> husk at hvis du har en liste
> A->B->C
> og du vil slette B fra listen, så vil du gøre det nogenlunde sådan her
>
> temp = a->next //gem en peger til B
> A->next = A->next->next //sæt A til at pege på C istedet for B
> delete next //slet B
tak den tygger jeg lige på,
Andreas Hjordt
| |
Morten Brix Pedersen (12-12-2001)
| Kommentar Fra : Morten Brix Pedersen |
Dato : 12-12-01 08:06 |
|
Andreas Hjordt wrote:
> <-------tllist.cpp------->
>
> #include "iostream.h"
Husk at dette skal være:
#include <iostream>
Standard headers skal være indrammet i <>, og C++ headers har intet .h
suffix.
- Morten.
| |
Andreas Hjordt (12-12-2001)
| Kommentar Fra : Andreas Hjordt |
Dato : 12-12-01 10:14 |
|
"Morten Brix Pedersen" <morten@wtf.dk> wrote in message
news:3C1701DD.5050106@wtf.dk...
> Andreas Hjordt wrote:
>
> > <-------tllist.cpp------->
> >
> > #include "iostream.h"
>
>
> Husk at dette skal være:
>
> #include <iostream>
>
> Standard headers skal være indrammet i <>, og C++ headers har intet .h
> suffix.
>
Jeg er godt klar over at standard headers skal være indrammet i <> men at
c++ headers ikke typisk har .h ekstension det viste jeg ikke. Og det virker
fint både med og uden.
Kan du henvise til en standard, begrundelse eller bare given en mere
uddybende forklaring?
Andreas Hjordt
| |
Morten Brix Pedersen (12-12-2001)
| Kommentar Fra : Morten Brix Pedersen |
Dato : 12-12-01 11:27 |
|
Andreas Hjordt wrote:
> "Morten Brix Pedersen" <morten@wtf.dk> wrote in message
> news:3C1701DD.5050106@wtf.dk...
>>Standard headers skal være indrammet i <>, og C++ headers har intet .h
>>suffix.
>>
>>
>
> Jeg er godt klar over at standard headers skal være indrammet i <> men at
> c++ headers ikke typisk har .h ekstension det viste jeg ikke. Og det virker
> fint både med og uden.
> Kan du henvise til en standard, begrundelse eller bare given en mere
> uddybende forklaring?
Før C++ blev standardiseret, brugte man headersne med .h suffix, men
under denne process blev meget ændret i Standard C++ Library, blandt
andet blev der skiftet rundt på en del navne, og alt blev puttet i std::
namespace. For at skabe bagudskompatibilitet med eksisterende
implementationer, så besluttede man at fjerne .h (dette er sikkert ikke
hele grunden). I den færdige ISO C++ Standard, er <header> det korrekte
at bruge.
Du skal gøre det samme med C headers, istedet for <stdlib.h> skal du
bruge <cstdlib>. Dette giver også en bedre forskel imellem <string> og
<string.h>, hvor du nu angiver den sidste som <cstring>.
På de fleste systemer vil <iostream.h> og <iostream> være det samme, men
du bør altid bruge uden .h medmindre du skal understøtte en gammel compiler.
- Morten.
| |
|
|