Helsingin yliopisto / Tietojenkäsittelytieteen laitos / Copyright © 2000 Jan Lindström. Tämän oppimateriaalin käyttö on sallittu vain yksityishenkilöille opiskelutarkoituksissa. Materiaalin käyttö muihin tarkoituksiin, kuten kaupallisilla tai muilla kursseilla, on kielletty.

---

58127-1 C-ohjelmointi - Syksy 2000 : Kertausta: Tietorakenne LISTA

---

Tämän kerran kertauksen tavoitteena on muodostaa kirjasto funktioita, joiden avulla voi käsitellä listoja. Kirjasto koostuu kahdesta tiedostosta: List.h ja List.c. Tiedoston List.h sisältö näyttää seuraavalta:

#ifndef MY_LIST_LIBRARY 
#define MY_LIST_LIBRARY

/* Määritellään listatyypit */

typedef struct listitem
{
    struct listitem *Next; /* Seuraava alkio listassa  */
    struct listitem *Prev; /* Edellinen alkio listassa */
    void *Data;            /* Tietoalkio               */
    unsigned long Size;    /* Tietoalkion koko         */
} ListItem;

typedef struct
{
    ListItem *Head;        /* Listan alku              */
    ListItem *Tail;        /* Listan loppu             */
    unsigned long Items;   /* Listan alkioiden lkm     */
} List;

/* Listakirjaston tukemat funktiot */

/* Luo uusi lista */
extern List *CreateList(void);

/* Luo lista-alkio */
extern ListItem *CreateItem(void *Data,unsigned long Size);

/* Lisää listan loppuun */
extern int AddTail(List *,ListItem *);

/* Lisää listan alkuun */
extern int AddHead(List *,ListItem *);

/* Laske listan pituus */
extern unsigned long ListLength(List *);

/* Tuhoa lista */
extern void DeleteList(List *);

/* Tulosta listan sisältö */
extern void PrintList(List *);

/* Tarkista onko lista tyhjä */

extern int EmptyList(List *);

#endif

Tiedoston List.c sisältö on seuraavaa:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "List.h"

int main(void);

int main(void)
{
    List *MunLista;
    ListItem *MunItem;
    char sana[256+1];

    if(!(MunLista = CreateList()))
    {
        printf("Jotain meni pieleen\n");
        exit(1);
    }

    while( gets(sana) != NULL )
    {
        if(!(MunItem = CreateItem((void *)sana,sizeof(sana))))
        {
            printf("Jotain meni pieleen\n");
            DeleteList(MunLista);
            exit(1);
        }

        AddTail(MunLista,MunItem);

        if(!(MunItem = CreateItem((void *)sana,sizeof(sana))))
        {
            printf("Jotain meni pieleen\n");
            DeleteList(MunLista);
            exit(1);
        }

        AddHead(MunLista,MunItem);
        printf("Nyt listassa on %ld alkiota\n",ListLength(MunLista));
    }

    PrintList(MunLista);
    DeleteList(MunLista);

    if ( EmptyList(MunLista) )
        printf("Lista on tyhjä\n");
    else
        printf("Listassa on vielä tavaraa\n");

    return 0;
}

/*
   Varataan muistia uudelle listalle ja alustetaan kentät 
*/
List *CreateList(void)
{
    List *uusi;

    if(!(uusi = (List *)malloc(sizeof(List))))
        return NULL;

    uusi->Head = NULL;
    uusi->Tail = NULL;
    uusi->Items = 0;

    return uusi;
}

/*
  Varataan muistia uudelle listan alkiolle ja alustetaan kentät
*/

ListItem *CreateItem(void *Data,unsigned long size)
{
    ListItem *uusi;

    /* Jos järkevää dataa ei ole annettu poistu */
    if (Data == NULL)
        return NULL;

    if(!(uusi = (ListItem *)malloc(sizeof(ListItem))))
        return NULL;

    if(!(uusi->Data = (void *)malloc(size)))
        return NULL;

    uusi->Next = NULL;
    uusi->Prev = NULL;
    memcpy(uusi->Data,Data,size);
    uusi->Size = size;

    return uusi;
}

/*
  Lisätään alkio listan loppuun
*/

extern int AddTail(List *lista,ListItem *item)
{
    if (lista == NULL || item == NULL )
        return 1;

    if ( lista->Head == NULL)
        lista->Head = lista->Tail = item;
    else
    {
        lista->Tail->Next = item;
        item->Prev = lista->Tail;
        lista->Tail = item;
    }

    lista->Items++;

    return 0;
}

/*
  Lisätään alkio listan alkuun
*/

extern int AddHead(List *lista,ListItem *item)
{
    if (lista == NULL || item == NULL )
        return 1;

    if ( lista->Head == NULL)
        lista->Head = lista->Tail = item;
    else
    {
        lista->Head->Prev = item;
        item->Next = lista->Head;
        lista->Head = item;
    }

    lista->Items++;

    return 0;
}

/* 
  'Lasketaan' listan pituus
*/
unsigned long ListLength(List *lista)
{
    if ( lista == NULL )
        return 0;
    else
        return lista->Items;
}

/*
  Tuhotaan koko lista
*/

void DeleteList(List *lista)
{
    ListItem *tmp;

    if ( lista == NULL )
        return;

    tmp = lista->Head;

    while(tmp != NULL)
    {
        tmp = lista->Head->Next;
        free(lista->Head->Data);
        free(lista->Head);
        lista->Head = tmp;
    }

    free(lista);
}

/*
  Tulostetaan koko lista
*/

void PrintList(List *lista)
{
    ListItem *tmp = lista->Head;

    printf("|");

    while(tmp != NULL)
    {
        printf("%s|",(char *)tmp->Data);
        tmp = tmp->Next;
    }
    printf("|-\n");
}

/*
  Tarkista onko lista tyhjä
*/

int EmptyList(List *lista)
{
    if ( lista == NULL)
        return 1;
    else if (lista->Head == NULL )
        return 1;
    else
        return 0;
}

---

Jan Lindström (Jan.Lindstrom@cs.Helsinki.FI)