• 8.1 Perusasioita
• 8.2 Tietueet ja funktiot
• 8.3 Tietueet taulukossa
• 8.4 Osoittimet tietueisiin
• 8.5 Osoittimet rakenteisiin (PINO)
• 8.6 Dynaamisia rakenteita (LISTA)
• 8.7 Rekursiivisia rakenteita (PUU)
• 8.8 Sovellusesimerkki: Harva taulukko

8 Rakenteet ja Dynaaminen muistinhallinta

8.1 Perusasioita

struct piste
{
    int x;
    int y;
};

Tunnus voi puuttua. Tietueen kenttien tunnukset (x ja y yllä) voivat olla samoja kuin tietueen tai muuttujien nimet - yhteydestä selviää aina mitä samannimisistä tunnuksista tarkoitetaan.

#include <stdio.h>  
#include <math.h>

struct piste 
{ 
  int x;
  int y;  
}; 
  
double eta ( int, int, int, int );  
double etat ( struct piste,  struct piste );  
struct suorak { struct piste p1; struct piste p2; } ala;  
double pala ( struct suorak );  

int main (void)
{
       int x = 4, y = 3;
       double etal, eta2, pinta;
       struct piste eka, toka, alar={0,0};
       eka.x = x; eka.y = y;
       toka = eka;
       toka.y++;
       printf("Etaisyyksia pisteesta"
       " (%d,%d) :\n",alar.x, alar.y);
       etal =  eta(alar.x, alar.y,eka.x, eka.y);
       printf("(%d,%d) on %g.\n",  eka.x, eka.y, etal);
       eta2 = etat ( alar, toka );
       printf("(%d,%d) on  %g.\n",  toka.x, toka.y, eta2);
       ala.p1 = eka;
       toka.x++;
       ala.p2 = toka;
       pinta = pala ( ala );
       printf("Suorakaiteen: "  "(%d,%d)--(%d,%d) pintala on %g.\n",ala.p1.x,
         ala.p1.y, ala.p2.x, ala.p2.y, pinta);
       return 0;
     }

     double eta ( int x1, int y1, int x2, int y2)
     {
         return  ( sqrt(pow((double)x2-x1,2) + pow((double)y2-y1,2)));
     }

     double etat ( struct piste p1, struct piste p2 )
     {
         return ( sqrt(pow((double)p2.x-p1.x,2.0) + pow((double)p2.y-p1.y,2.0) ));
     }

     double pala ( struct suorak k )
     {
         return ( ((double)k.p2.x-k.p1.x ) * ( (double)k.p2.y-k.p1.y  ));
     }

8.2 Tietueet ja funktiot

• kopiointi ja sijoitus,
• osoitteen ottaminen (&) sekä
• kenttiin viittaaminen.

• kentittäin,
• koko tietue ja
• osoitin tietueeseen.

struct piste *op;  
op = &eka;  
printf("Piste = (%d,%d)\n",  
( * op ) .x, ( * op ) .y ) ;

Osoittimet tietueisiin ovat tavallisia ja vaihtoehtoisena (lyhennys ) merkintänä on

  p->kentta  

8.3 Tietueet taulukossa

Aigorilmi:  
 Toista niin kauan kuin sanoja on 
   Lue sana  
   Jos sana on tunnus  
      niin etsi binaarihaulla sanaa varattujen sanojen luettelosta
      jos löytyi niin kasvata ao laskuria 
 Tulosta esiintymistiheydet 

sizeof joku-kohde tai  
sizeof (tyypin tunnus)

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

     struct varattu 
     {
          char *sana; 
          int lkm;  
     } vtaulu[] =   
     {
      {"auto", 0},  
      {"break", 0}, {"case", 0}, {"char", 0},  
     /* tästä poistettu monta paria */  
      {"unsigned", 0}, {"void", 0},  
      {"volatile", 0}, {"while", 0} 
     }; 
      
     #define VSANOJA (sizeof vtaulu / sizeof (struct varattu ))
       
     #define MAXPIT 1024
       
     int binhaku ( char *, struct varattu *, int ) ;  
      
     int main (void) 
     {  
       int n;  
       char *sana;  
       char rivi[MAXPIT];

       printf("VSANOJA %d\n",VSANOJA);

       while (gets(rivi) != NULL)
       {
          
          sana = strtok(rivi," ");

          while( sana != NULL)
          {
              if ( isalpha(sana[0]))
              {  
                  if ( (n = binhaku(sana,vtaulu, VSANOJA)) >=0 )  
                      vtaulu[n].lkm++;
              }
              sana = strtok(NULL," ");
          }
       }

       for ( n = 0; n < VSANOJA; n++) 
       {
           if ( vtaulu[n].lkm > 0 )  
               printf ( "%4d %s\n", vtaulu[n].lkm,vtaulu[n].sana);  
       }

       return 0;  
     } 
     int binhaku (char *sana, struct varattu vtaulu[], int koko)
     {  
         int osui, ala, yla, keski; 
         ala = 0; yla = koko -1; 

         while ( ala <= yla ) 
         { 
             keski = ( ala + yla ) >> 1;  
             osui = strcmp(sana, vtaulu[keski].sana);
             if ( osui < 0  )
                 yla = keski - 1;  
             else if ( osui > 0 ) 
                 ala = keski + 1; 
             else  
                 return keski; 
         }  
         return -1; 
     }  

8.4 Osoittimet tietueisiin

 
...
int luesana ( char *, int ); 
struct varattu *binhaku(char *, struct varattu *, int);  

/*lasketaan varattujen sanojen frekvenssit -kaytetaan osoittimia*/  

int main (void) 
{  
    struct varattu *pv; 
    char *sana;  
    char rivi[MAXPIT];

    while (gets(rivi) != NULL)
    {
        sana = strtok(rivi," ");

        while( sana != NULL)
        {
            if ( isalpha(sana[0]))
            {  
                if ( (pv = binhaku(sana,vtaulu, VSANOJA)) >=0 )  
                    pv->lkm++;
            }
            sana = strtok(NULL," ");
        }
    }

    for ( pv = vtaulu; pv < vtaulu + VSANOJA; pv++) 
        if ( pv->lkm > 0 )  
            printf("%4d %s\n",  pv->lkm, pv->sana); 

    return 0;  
}  
 
/*binaarihaku -palauttaa osoittimen*/  
struct varattu *binhaku (char *sana, struct varattu *pv, int koko)  
{  
    int osui;  
    struct varattu *ala = &pv[0], *yla = &pv[koko], *keski;  

    while ( ala < yla ) 
    {  
         keski = ala + ( yla - ala) /2; 

         if ( (osui = strcmp(sana, keski->sana) < 0 ) 
             yla = keski - 1;  
         else if ( osui > 0 ) 
             ala = keski + 1; 
         else  
             return keski; 
    }  
    return NULL; 
}  

8.5 Osoittimet rakenteisiin: PINO

Pino-operaatioita ovat :

• luodaan tyhjä pino,
• lisätään uusi alkio pinon päälle,
• noudetaan ja poistetaan alkio pinon päältä,
• -lasketaan pinon korkeus ja
• ilmoitetaan onko pino tyhjä vai ei.

/*********************************** 
1. Pino-operaatiot liitetaan mukaan:  
#include "pino.h"  

2. Pinon tyyppi on Pino ja omapino määritellään. 
 Pino P, *omapino = &P;
  
3. pinoon talletetaan int-tyypin arvoja, kun rivillä  

typedef int Pino_alkio;  

on int. 

Tyypin int voi vaihtaa. Vaihto tehdään vain alla  
olevalle vastaavalle riville.  
***********************************/ .  
 
#include <stdio.h> 
#include <stdlib.h> 
#include <limits.h>
  
typedef int Pino_alkio;  

struct tietue
{  
    Pino_alkio sana;  
    struct tietue *seur; 
};  

typedef struct tietue *Pino;  

/* varataan uusi tietue muistista */ 

struct tietue *uusi(void );  

/* luodaan pino */  

void p_luo ( Pino * );  

/* palauttaa arvon 1 jos pino tyhja, muuten arvon O */  

int p_tyhja ( Pino * );  

/* lisataan alkio pinon paalle */ 

void p_push ( Pino_alkio , Pino * );  

/* poistetaan alkio pinon paalta ja palautetaan poistettu alkio */  

Pino_alkio p_pop ( Pino * );  

/* palautetaan pinon korkeus */ 

int p_korkeus ( Pino * );

  
struct tietue *uusi ( void ) 
{  
    return ( (struct tietue *) malloc ( sizeof(struct tietue) ) );
}
  
void p_luo ( Pino *p )  
{ 
    *p = NULL;
    return;
}

int p_tyhja ( Pino *p ) 
{  
    return ( p == NULL );
}
  
void p_push ( Pino_alkio s, Pino *p )  
{  
    struct tietue *apu = uusi();
    apu->sana = s;
  
    if ( p_tyhja ( p ) ) 
    { 
        apu->seur = NULL; 
        *p = apu;
     } 
     else 
     {  
        apu->seur = *p, 
        *p = apu
     }
  
     return;
}  

Pino_alkio p_pop ( Pino *p ) 
{  
    Pino_alkio s;  
    struct tietue *irti;  

    if ( p_tyhja ( p ) ) 
    { 
          printf("virhe -pino tyhja \n"); 
          return INT_MIN;
    }  
    else
    {  
        s = (*p)->sana;
        irti = *p;
        *p = (*p)->seur; 
        free(irti); 
        return s;  
    }
}

int p_korkeus ( Pino *pp ) 
{  
    int korkeus = 0; 
    Pino *p = *pp;  

    for ( ; p != NULL; p = p->seur ) 
        korkeus++;  

    return korkeus;
}

8.6 Dynaamisia rakenteita (LISTA)

#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

#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;
}

8.7 Rekursiivisia rakenteita (PUU)

Puun solmulla voi olla korkeintaan kaksi lasta. Kunkin solmun vasen alipuu sisältää aakkosjärjestyksessä juurta edellä olevia sanoja ja oikea alipuu perässä olevia sanoja.

Puun solmussa on:

• osoitin sanaan
• lukumaaralaskuri
• osoitin vasempaan lapseen (alipuuhun)
• osoitin oikeaan lapseen (alipuuhun)

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

struct solmu
{ 
    char *sana; 
    int lkm; 
    struct solmu *vas, *oik; 
}; 

#define MAXPIT 100 

struct solmu *puuhun( struct solmu *, char * ); 
void tulostapuu( struct solmu * ); 
int luesana (char *, int ); 

/* sanojen esiintymien lkm:t */ 

int main (void) 
{ 
    struct solmu *puu; 
    char sana[MAXPIT]; 
    puu = NULL; 

    while(luesana(sana,MAXPIT) != EOF) )
        if ( isalpha(sana[O]) ) 
            puu = puuhun (puu, sana ); 

    tulostapuu ( puu ); 

    return 0; 
} 

struct solmu *tietue( void ); 
char *talteen( char * ); 

/* lisaa solmu puuhun */ 

struct solmu *puuhun( struct solmu *p, char *s ) 
{ 
    int osui;

    if ( p == NULL) 
    { /*lisaa*/ 
        p = tietue(); 
        /*uusi tietue*/ 
        p- >sana = talteen ( s); 
        p->lkm = 1; 
        p->vas = p->oik = NULL; 
     } 
     else if ( (osui = strcmp(s,p->sana) == 0 ) )
         p->lkm++; /*sana oli jo*/ 
     else if ( osui < 0)
         /*vas alipuu?*/ 
         p->vas = puuhun ( p->vas, s ); 
     else /*oik alipuu?*/ 
         p->oik = puuhun ( p->oik, s ); 

     return p; 
} 

/*tulosta puu sisajarjestyksessa (vas-juuri-oik)*/ 

void tulostapuu ( struct solmu *p )
{ 
    if ( p != NULL) 
    { 
        tulostapuu ( p->vas ); 
        printf ( "%4d %s\n", p->lkm, p->sana);
        tulostapuu ( p->oik ); 
     } 
} 

#include <stdlib.h> 

/*varaa tila solmulle*/ 

struct solmu *tietue( void ) 
{ 
    return ( (struct solmu *) malloc (sizeof(struct solmu) ) ); 
} 

/*kopioi sanan talteen*/ 

char *talteen( char *s ) 
{ 
    char *p; 
    p = (char *) malloc(strlen(s) + 1); 

    if ( p != NULL ) strcpy ( p,s ); 
    return p; 
} 

#include "luesana.c"

8.8 Sovellusesimerkki: Harva taulukko

Esimerkiksi:

Taulukko       : | 12 | 0  | 22 | 75 | 2  | 0 | 0  | 45 |
Harva taulukko : | 12 | 22 | 75 |  2 | 45 |

Tämä ei vielä riitä siis. Harvassa taulukossa täytyy tallettaa itse alkioiden lisäksi myös alkion indeksi ja itse taulukon koko. Määritellään ensin harvalle taulukolle tietorakenne, joka perustuu listojen käyttöön tiedostoon HarvaTaulukko.h.

#ifndef HARVATAULUKKO
#define HARVATAULUKKO 1

#include
#include

/* Harvan taulukon alkioiden tietorakenteen määrittely */
typedef struct halkio
{
    struct halkio *next;   /* Seuraava alkio  */
    struct halkio *prev;   /* Edellinen alkio */
    int           value;   /* Alkion arvo     */
    unsigned long index;   /* Alkion indeksi  */
} Harva_Alkio;

typedef struct
{
    unsigned long itemcnt; /* Taulukon koko   */
    Harva_Alkio *head;     /* Taulukon alku   */
    Harva_Alkio *tail;     /* Taulukon loppu  */
} Harva_Taulukko;

/* Funktiot */

Harva_Taulukko *alusta_htaulu(void);
Harva_Alkio *varaa_alkio(void);
int alkio(Harva_Taulukko *ht,unsigned long index);
Harva_Taulukko *iterate(Harva_Taulukko *hta, Harva_Taulukko *htb, 
  Harva_Alkio* (*fptr)(const Harva_Alkio *,const Harva_Alkio *));
Harva_Alkio *summa(const Harva_Alkio *ha,const Harva_Alkio *hb);
void lisaa(Harva_Taulukko *ht,Harva_Alkio *ha);
void print(Harva_Taulukko *ht);
void vapauta(Harva_Taulukko *ht);

#endif

Esimerkin vuoksi toteutetaan tietorakenteelle seuraavat operaatiot:

• Harva_Taulukko *alusta_htaulu(void), joka luo tyhjän harvan taulukon.
• Harva_Alkio *varaa_alkio(void), joka varaa dynaamisesti muistia uudelle alkiolle.
• int alkio(Harva_Taulukko *ht,unsigned long index), joka palauttaa harvan taulukon i:nen alkion, eli normaalista taulukosta palauttaisi arvon ht[i-1].
• Harva_Taulukko *iterate(Harva_Taulukko *hta, Harva_Taulukko *htb, Harva_Alkio* (*fptr)(const Harva_Alkio *,const Harva_Alkio *)), joka läpikäy kaikki alkiot harvoista taulukoista hta ja htb sekä jokaiselle alkioparille kutsuu parametrinä annettua funktiota, jonka paluuarvoista luodaan uusi harva taulukko.

Toteutus on sijoitettu tiedostoon HarvaTaulukko.c, mutta tehdään se tässä yksi funktio kerrallaan. Aloitetaan alustuksesta:

#include "HarvaTaulukko.h"

int main(int, char **);

int main(int argc, char **argv)
{
    Harva_Taulukko *hta,*htb,*htc;
    Harva_Alkio    *ha;
    
    hta = alusta_htaulu();
    htb = alusta_htaulu();

    ha = varaa_alkio();
    ha->value = 5;
    ha->index = 0;
    lisaa(hta,ha);
    ha = varaa_alkio();
    ha->value = 2;
    ha->index=3;
    lisaa(hta,ha);
    ha = varaa_alkio();
    ha->value = 7;
    ha->index=4;
    lisaa(hta,ha);
    ha = varaa_alkio();
    ha->value = 3;
    ha->index=5;
    lisaa(hta,ha);
    hta->itemcnt = 6;

    ha = varaa_alkio();
    ha->value = 5;
    ha->index = 0;
    lisaa(htb,ha);
    ha = varaa_alkio();
    ha->value = 4;
    ha->index=2;
    lisaa(htb,ha);
    ha = varaa_alkio();
    ha->value = 3;
    ha->index=3;
    lisaa(htb,ha);
    ha = varaa_alkio();
    ha->value = 7;
    ha->index=7;
    lisaa(htb,ha);

    htb->itemcnt = 8;
    
    print(hta);
    print(htb);

    htc = iterate(hta,htb,summa);
    print(hta);
    print(htb);
    print(htc);
    vapauta(hta);
    vapauta(htb);
    vapauta(htc);
    return 0;
}

/* Funktiolla alustetaan tyhjä harva taulukko. */
Harva_Taulukko *alusta_htaulu(void)
{
    Harva_Taulukko *ht = NULL;

    if (!( ht = (Harva_Taulukko *)malloc(sizeof(Harva_Taulukko))))
    {
        printf("Muisti ei riitä, lopetetaan...\n");
        exit(1);
    }

    ht->itemcnt  = 0;
    ht->head     = NULL;
    ht->tail     = NULL;

    return ht;
}


/* Funktiolla varataan muistitilaa harvan taulukon alkiota varten */
Harva_Alkio *varaa_alkio(void)
{
    Harva_Alkio *alkio;

    if (!( alkio = (Harva_Alkio *)malloc(sizeof(Harva_Alkio))))
    {
        printf("Muisti ei riitä, lopetetaan...\n");
        exit(1);
    }

    alkio->next  = NULL;
    alkio->prev  = NULL;
    alkio->index = 0;
    alkio->value = 0;
    
    return alkio;
}

/* Funktiolla palautetaan harvasta taulukosta haluttu alkio tai
   NULL jos alkiota ei ole taulukossa */

int alkio(Harva_Taulukko *ht,unsigned long index)
{
    Harva_Alkio *alkio = NULL;

/* Jos indeksi virheellinen palauta tyhjä alkio */
    if ( index < 0 || index > ht->itemcnt )
        return 0;

/* Tyhjä harva taulukko */
    if ( ht->itemcnt == 0 )
        return 0;

/* Erikoistapaukset alku ja loppu */
    if ( ht->head->index == index) return ht->head->value;
    if ( ht->tail->index == index) return ht->tail->value;

/* Pakko etsiä */

    alkio = ht->head->next;

    while ( alkio != NULL )
    {
        if ( alkio->index < index )
           alkio = alkio->next;
        else if (alkio->index == index)
           return alkio->value;
        else
           return 0;
    }

    return 0;
}

/* Funktiolla läpikäydään kaksi harvaa taulukkoa ja kutsutaan
jokaiselle alkiolle parametrinä annettu funktiota, jonka tuloksista
rakennetaan uusi harva taulukko */

Harva_Taulukko *iterate(Harva_Taulukko *hta, Harva_Taulukko *htb, 
Harva_Alkio* (*fptr)(const Harva_Alkio *,const Harva_Alkio *))
{
    Harva_Taulukko *ht = NULL;
    Harva_Alkio    *nha = NULL;
    Harva_Alkio    *ha,*hb;

    ha = hta->head;
    hb = htb->head;
    ht = alusta_htaulu();

    while( ha != NULL || hb != NULL )
    {
        if ( ha == NULL      || hb->index < ha->index )
        {
            nha = varaa_alkio();
            nha->index = hb->index;
            nha->value = hb->value;
            lisaa(ht,nha);
            hb = hb->next;
        }
        else if ( hb == NULL || ha->index < hb->index )
        {
            nha = varaa_alkio();
            nha->index = ha->index;
            nha->value = ha->value;
            lisaa(ht,nha);
            ha = ha->next;
        }
        else
        {
            nha = fptr(ha,hb);

            if ( nha->value != 0)
                lisaa(ht,nha);
            else
                free(nha);
            
            ha = ha->next;
            hb = hb->next;
        }
    }

    ht->itemcnt = hta->itemcnt > htb->itemcnt ? hta->itemcnt: htb->itemcnt;
    return ht;
}

/* Funktio lisää uuden alkion harvan taulukon loppuun */
void lisaa(Harva_Taulukko *ht,Harva_Alkio *nha)
{
    if ( ht->tail == NULL)
    {
        ht->tail = nha;
        ht->head = nha;
    }
    else
    {
        ht->tail->next = nha;
        nha->prev = ht->tail;
        ht->tail = nha;
    }
}

/* Lasketaan kahden alkion summa. Oletus: alkiot kokonaislukuja */
Harva_Alkio *summa(const Harva_Alkio *ha,const Harva_Alkio *hb)
{
    Harva_Alkio *nha;

    nha = varaa_alkio();

    nha->index = ha->index;
    nha->value = ha->value + hb->value;
    return nha;
}

/* Funktio tulostaa harvan taulukon alkiot */
void print(Harva_Taulukko *ht)
{
   Harva_Alkio *ha = ht->head;
   int index = 0;
   
   while( ha != NULL )
   {
   	if ( index == ha->index )
   	{
   	    printf("|%d|",ha->value);
            ha = ha->next;
        }
   	else
   	    printf("|0|");

        index++;
   }
   
   while ( index < ht->itemcnt)
   {
       printf("|0|");
       index++;
   }
   
   printf("\n");
}

/* Funktio vapauttaa harvan taulukon varaaman muistitilan */
void vapauta(Harva_Taulukko *ht)
{
    Harva_Alkio *ha = ht->head;
    Harva_Alkio *tmp;
    
    while( ha != NULL )
    {
    	tmp = ha->next;
        free(ha);
        ha = tmp;
    }
    
    free(ht);
}

Tässä toteutuksessa on ongelmana se, että se toimii vain summa-funktion suhteen. Luennoilla on käsitelty tapa, jolla toteutus saadaan toimimaan myös erotuksen ja kertolaskun suhteen. Jakolasku vaatisi enemmän työtä.