Ivan wrote:
>>Har du fundet en løsning, ellers kan jeg godt støve et eksempel af.
>>Det ville dog være rart at vide om du vil lave det i C eller C++,
>>og om du har andre krav til listen (f.ex enkelt/dobbelt link).
>>
>>/b
>
>
> Har ikke fået løst noget endnu. Det er i C++ og ja du må meget gerne komme
> med et eks.
>
Man kan lave linkede lister på mange måder, jeg vil vise én der ikke
er speciel for C++, den kan også bruges i C. Nogen vil måske mene at det
ikke er den "rigtige" måde at lave en hægtet liste i C++, hvilket nok
også er rigtigt, på den anden side viser det nogle principper, der også
gælder for C++. Desuden ville en rigtig C++ programør nok ikke lave sin
egen hægtede liste, men bruge noget fra STL.
Man kunne kalde metoden der bruges her for: "cirkulær dobbelt hægtet liste".
Man starter med at definere en data struktur:
typedef struct LL_struct_type
{
struct LL_struct_type *prev;
struct LL_struct_type *next;
char first_name[MAX_NAME];
char last_name[MAX_NAME];
}LL_struct_type;
first_name og last_name er kun med for eksemplets skyld. Det der er
vigtigt at bemærke er at prev og next der bliver brugt til at linke
med er en del af "bruger" data strukturen, hvilket betyder at man
ikke skal allokere plads til link strukturen og data strukturen
hver for sig. Det giver et lidt mere effektiv program, men nogen
vil nok sige at det ikke er så pæn en indkapsling. (prev er en
forkortelse for previous.)
Næste punkt er at definere roden af listen:
LL_struct_type s_list = {&s_list, &s_list, "", ""};
Det bør bemærkes at s_list.next og s_list.prev bliver sat til at
pege på listen, det er vigtigt ellers vil resten ikke virke.
Fordelen ved dette er at man, når man indætter et element i listen,
ikke behøver at bekymre sig om om det er det første element i listen,
og når man fjerner et element i listen skal man heller ikke gøre noget
specielt for det sidste element.
s_list.first_name og s_list.last_name bliver aldrig brugt, så man kan
godt sige at man spilder noget memory, jeg vil dog mene at det er
uden betydning i normale tilfælde.
Nu er vi så klar til at indsætte et element (node) i listen, til dette
laver vi lige en lille macro:
#define LL_PUT_IN_LIST_LAST(list_, node_) \
do{ \
(node_)->prev = (list_).prev; \
(node_)->next = &(list_); \
(list_).prev->next = node_; \
(list_).prev = node_; \
}while(0)
Det ses heraf at node bliver sat ind i listen som dennes prev.
Man kan så bruge makroen på følgende måde:
bool make_new_node(char *first_name, char *last_name)
{
LL_struct_type *node;
if((node = (LL_struct_type *)malloc(sizeof(LL_struct_type))) == NULL)
return false;
strcpy(node->first_name, first_name);
strcpy(node->last_name, last_name);
LL_PUT_IN_LIST_LAST(s_list, node);
return true;
}
Man kan så lave en lille makro til at fjerne en node fra
listen:
#define LL_GET_FROM_LIST_FIRST(list_, node_) \
do{ \
node_ = (list_).next; \
(list_).next = (list_).next->next; \
(list_).next->prev = &(list_); \
}while(0)
Det ses at man udtager list.next, dvs fra den modsatte ende af
den man indsatte i.
Denne bruges på følgende måde:
LL_struct_type *s;
LL_GET_FROM_LIST(s_list, s);
Den opmærksomme læser vil have bemærket at LL_GET_FROM_LIST_FIRST
ikke checker om der er elementer i listen, så det må brugeren
gøre inden, til det formål laver vi lige en macro:
#define LL_LIST_EMPTY(list_) ((list_).next == &(list_))
Man kan bruge denne på følgende måde:
if(LL_LIST_EMPTY(s_list))
printf("List is empty\n);
else
printf("List is not empty\n);
Man kan gennemløbe listen på følgende måde:
LL_struct_type *s;
for(s = s_list.next; s != &s_list; s = s->next)
printf("%s %s\n", s->first_name, s->last_name);
Jeg har lavet et lille demoprogram der bruger ovenstående og
som viser lidt mere avancerede operationer som f.ex. at sortere
en hægtet liste. Sourcen er lidt for lang til at jeg vil poste
det her, så intereserede må downloade den her:
http://home20.inet.tele.dk/midgaard/linklist.zip
/b