l 5,R 65,J,T 5
@ots(Etsiminen ja lajittelu)
Etsiminen ja lajittelu ovat eräitä yleisimmin tietojenkäsittelyssä vastaan tulevia tilanteita. Esimerkiksi C-merkkijonon pituuden laskeminen on oikeastaan NUL-merkin paikan etsimistä.
õ(SECTION Etsiminen)õ õ(IXREF etsiminen)õ
õ(IXREF binäärihaku)õ
Etsimistä voidaan suorittaa monella tavalla. Mikäli tietorakenne ei tarjoa parempaa vaihtoehtoa, ei ole muuta mahdollisuutta kuin peräkkäishaku)õ. Järjestetystä taulukosta pystyttiin hakemaan binäärihaulla. Puumaisesta rakenteesta voidaan hakea puun ominaisuuksia käyttäen. Joskus voidaan tehdä avuksi hakemistoja, jotka ohjaavat haun suurinpiirtein oikealle paikalleen, josta sitten jatketaan jollakin toisella hakumenetelmällä.
õ(IXREF bsearch )õ
C-kielen kirjastosta löytyy funktio bsearch, joka etsii lajitellusta aineistosta binäärihaulla ja palauttaa NULL mikäli ei löydy ja muuten palauttaa osoittimen taulukon löytyneeseen alkioon. Funktion käyttö on vastaava kuin myöhemmin esiteltävän qsort -funktion käyttö, joten emme tässä puutu siihen enempää.
Kerhorekisterissä tietorakenne on varsin alkeellinen, eikä sitä ole ainakaan toistaiseksi edes järjestetty. Siis tietyn jäsenen etsiminen on suoritettava raakana peräkkäishakuna.
õ(BEGIN TEHTAVA)õ
õ(tehtots etsi_nimi)õ õ(IXREF etsi_nimi)õ
Kirjoita funktio etsi_nimi, joka etsii kerhosta ensimmäisen henkilön, jolla on TÄSMÄLLEEN parametrina annettu nimi. Funktio palauttaa nimessään löytöpaikan indeksin ja -1 jollei löydy.
Voitaisiinko aliohjelmaa käyttää apuna lisäyksessä tarkistamaan onko jäsen jo ennestään tiedostossa?
Voitaisiinko aliohjelmaa käyttää apuna korjaamisessa tarkistamaan onko nimi muuttunut sellaiseksi, joka on jo ennestään tiedostossa?
õ(END TEHTAVA)õ
õ(SUBSECTION wildmat)õ õ(IXREF wildmat)õ
Jos etsimisessä halutaan sallia jokerimerkkien käyttö, saattaa etsiminen johtaa joka tapauksessa peräkkäishakuun. Voitaisiin kuitenkin erotella erikoistapauksia:
Ankka Aku - voitaisiin käyttää mitä tahansa järkevää
järjestetyn joukon hakualgoritmia
Ankka* - voitaisiin etsiä järjestetystä joukosta 1. Ankka
ja tämän jälkeen loppu peräkkäishakuna
*Aku* - vaikea keksiä muuta kuin peräkkäishaku
Lähdimme kuitenkin alunperin oletuksesta, että kerhon koko on pieni. Siis tuskin peräkkäishakukaan vie kohtuuttomasti aikaa. Näin ollen käsittelemme kaikki hakutilanteet samalla tavalla.
Entäpä mikäli etsimisessä löytyy useita ehdon täyttäviä henkilöitä. Eräs tyypillinen tapa on tehdä aliohjelmapari:
etsi_ensimmainen
etsi_seuraava
Vähän samaa ideaa sovellettiin jo aikaisemmin palanen -aliohjelmassa.
õ(BEGIN TEHTAVA)õ
õ(tehtots etsi_nimi_alkaen)õ
Kirjoita funktio etsi_nimi_alkaen, joka etsii kerhosta nimeä aloittaen etsimisen parametrina välitetystä indeksistä. Tällä kertaa hakuehtona saa olla myös jono "*Aku*". Funktio palauttaa löytöpaikan indeksin tai -1, mikäli etsittävää ei löydy.
õ(END TEHTAVA)õ
õ(SUBSECTION Etsiminen taulukkoon)õ
õ(IXREF etsiminen, taulukkoon)õ
Toinen mahdollisuus etsimiseen on tallettaa taulukkoon kukin löytynyt ehdot täyttävä tietue. Määrittelemme tyypin
/* õ(FNAME2 etsilaj.5\kerho.h)õ */
typedef struct { /* Tietue jonka avulla voidaan pitää eri järjestyksiä. */
int max_koko; /* Indeksitaulukon maksimikoko. */
int indekseja; /* Taulukosta nyt käytetty indekseja. */
int *indeksit /* Osoitin indeksitaulukkoon (dynaaminen). */
} Jarjestys_tyyppi)õ; /* */
l 5,R 65,J,T 5
Jos seuraavasta aineistosta etsittäisiin vaikkapa hakuehdolla nimi=="*k*"
**jasenet ³ o ³
Jarjestys_tyyppi ÀÄÄÄÄÄÄÅÄÄÄÄÄÄÙ Jasen_tyyppi
etsi ÚÄÄÄ¿ ³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
max_koko ³ 7 ³ v ³Kassinen Katto³
indekseja³ 2 ³ ÚÄÄÄÄÄÄÄÄÄÄ¿ ³Katto ³
*indeksit³ o ³ ÚÄÄÄ>jasenet[0] ³ oÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄ>³3452 ³
ÀÄÅÄÙ ³ ÃÄÄÄÄÄÄÄÄÄÄ´ ³... ³
³ ³ jasenet[1] ³ oÄÄÄÄÄÅÄÄÄÄÄÄÄÄ¿ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
v ³ ÃÄÄÄÄÄÄÄÄÄÄ´ ³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÚÄÄÄ¿ ³ ÚÄ>jasenet[2] ³ oÄÄÄÄÄÅÄÄÄÄÄÄ¿ ³ ³Susi Sepe ³
0 ³ 0 ÃÄÄÙ ³ ÃÄÄÄÄÄÄÄÄÄÄ´ ³ ÀÄÄÄÄÄ>³Perämetsä ³
ÃÄÄÄ´ ³ ... ³ ³ ³ ³- ³
1 ³ 2 ÃÄÄÄÄÙ ÃÄÄÄÄÄÄÄÄÄÄ´ ³ ³... ³
ÃÄÄÄ´ ³ ³ ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
2 ³ ? ³ ÃÄÄÄÄÄÄÄÄÄÄ´ ³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÃÄÄÄ´ ³ ³ ÀÄÄÄÄÄÄÄ>³Ankka Aku ³
3 ³ ? ³ ÃÄÄÄÄÄÄÄÄÄÄ´ ³Ankkalinna ³
ÃÄÄÄ´ ³ ³ ³1234 ³
4 ³ ? ³ ÃÄÄÄÄÄÄÄÄÄÄ´ ³... ³
ÃÄÄÄ´ ³ ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
5 ³ ? ³ ÀÄÄÄÄÄÄÄÄÄÄÙ
ÃÄÄÄ´ osoitintaulukko henkilöihin
6 ³ ? ³
ÃÄÄÄ´
7 ³ ? ³ indeksitaulukko löytyneisiin
ÀÄÄÄÙ
l 5,R 65,J,T 5
löytyisi jasenet[0] ja jasenet[2], jotka täyttävät hakuehdon. Tällöin etsimisaliohjelma palauttaisi tämän tiedon seuraavasti:
Jarjestys_tyyppi etsi
ÚÄÄÄÄÄ¿
max_koko ³ 7 ³ 0 1 2 3 4 5 6
indekseja³ 2 ³ ÚÄÄÂÄÄÂÄÄÂÄÄÂÄÄÂÄÄÂÄÄ¿
*indeksit ³ oÄÄÅÄÄÄÄÄÄ>³ 0³ 2³ ?³ ?³ ?³ ?³ ?³
ÀÄÄÄÄÄÙ ÀÄÄÁÄÄÁÄÄÁÄÄÁÄÄÁÄÄÁÄÄÙ
Nyt tietäisimme heti, että meillä on kaksi löytynyttä, joten löytyneet voitaisiin tulostaa:
for (i=0; ijasenet[etsi.indeksit[i]])
õ(SUBSECTION Etsiminen valitun kentän mukaan)õ
Mitä jos haluamme etsiä jonkin tietyn kentän mukaan. Välitämme etsimisaliohjelmalle tiedoksi kentän numeron, jonka mukaan haluamme etsiä. Käytännössä osoittautuu helpoimmaksi välittää myös etsittävä isona tietueena (tai taulukkona), johon on täytetty nimenomaan etsittävään kenttään halutut tiedot.
õ(SUBSECTION etsi_indeksit (kerhoets.c))õ õ(IXREF etsi_indeksit)õ
õ(IXREF kerhoets.c)õ
/* õ(FNAME2 etsilaj.5\kerhoets.c)õ */
/****************************************************************************/
int /* */
etsi_indekseja( /* = löytyneiden kenttien lukumäärä */
Kerho_tyyppi *kerho ,/* s Kerho josta etsitään */
int kentta ,/* s Kentän numero, josta etsitään */
Haku_tyyppi *maski ,/* s Arvot joiden mukaan etsitään. */
Jarjestys_tyyppi *etsi /* t Taulukko jonne löytyneet talletetaan */
)
** Mikäli ketään ei löydy, laitetaan silti indeksit[0]=0, jotta siihen voidaan
** varmasti viitata.
**
** Algoritmi: Kokeillaan jokaista paikkaa ja merkitään löytymät ylös.
** Isot ja pienet kirjaimet samaistetaan.
----------------------------------------------------------------------------*/
{
char isana[80],imaski[80];
int j;
etsi->indekseja = 0; etsi->indeksit[0] = 0;
kopioi_jono(N_S(imaski),maski[kentta]);
jono_isoksi(imaski);
for (j=0; jjasenia; j++) { /* Tutkitaan kaikki jäsenet */
if (!kerho->jasenet[j]) continue; /* Ohitetaan NULL-osoittimet*/
kopioi_jono(N_S(isana),kentta_jonoksi(kentta,kerho->jasenet[j]));
jono_isoksi(isana);
if ( wildmat(isana,imaski)==0 ) {
etsi->indeksit[etsi->indekseja++] = j;
if ( etsi->indekseja >= etsi->max_koko ) break;
}
}
return etsi->indekseja;
}
l 5,R 65,J,T 5
õ(IXREF etsiminen, JA)õ
õ(IXREF etsiminen, TAI)õ
õ(IXREF JA, etsiminen)õ
õ(IXREF TAI, etsiminen)õ
Etsimistä voitaisiin hieman monipuolistaa siten, että voitaisiin laittaa ehto jokaiseen tutkittavan jasen-tietueen kenttään. Sitten löytymisen ehtona voisi olla, että jokin kentistä täsmää (TAI) tai että kaikki kentät täsmäävät (JA). Tämä voitaisiin ilmaista etsimisaliohjelmalle vaikkapa siten, että JA etsimisessä kentta=-1 ja TAI etsimisessä kentta=-2.
õ(BEGIN TEHTAVA)õ
õ(tehtots TAI-etsiminen)õ
Miten käyttäjä saisi TAI-etsimisen avulla vastauksen kysymykseen: Onko missään kentässä missään kohti sana aku?
õ(END TEHTAVA)õ
õ(SUBSECTION Haku_tyyppi)õ
Miksi välitimme etsimisaliohjelmalle muuttujan joka on tyyppiä Haku_tyyppi? Tähän on kaksi syytä.
Ensinnäkin on käyttäjän kannalta mukavaa, että jos hän on joskus hakenut nimihaussa nimellä "*aku*", niin seuraavassakin nimihaussa hänellä on oletuksena sama hakuehto. Siis eri kentissä viimeksi käytetyt hakuehdot kannattaa kukin säilyttää erikseen.
Toisaalta jos haluamme totetuttaa JA ja TAI -tyyppiset haut, tarvitsemme etsimisaliohjelmalle hakuehdon kullekin kentälle.
Haku_tyyppi voisi olla myös Jasen_tyyppi, mutta koska Jasen_tyypin kentillä on mahdollisuus saada myös numeerisia arvoja, ei numeeriseen kenttään pystyttäisi tallettamaan esimerkiksi hakuehtoa "4*" tai "<50". Siis Haku_tyyppi on parasta tehdä 2-ulotteiseksi taulukoksi
typedef char Haku_tyyppi[KENTTIA][40];
Toisaalta tyyppien esittelyvaiheessa KENTTIA arvo saattaa vielä olla tuntematon, joten hakutyyppi voidaan esitellä vain tavalliseksi merkkijonoksi
typedef char Haku_tyyppi)õ[40];
Jos esittelemme muuttujan haku ja varaamme sille tilaa calloc -funktiolla (kuten malloc, mutta parametrit hieman eri tavalla ja alustaa koko alueen nolliksi).
Haku_tyyppi *haku;
...
haku = calloc(KENTTIA,sizeof(Haku_tyyppi));
saamme kaksiulotteisin taulukon, johon voidaan viitata esimerkiksi:
strcpy(haku[2],"Mikonkatu*");
õ(SECTION Kenttä indeksin avulla)õ
Edellä oli kaikista helpoin ratkaisu tehdä kutsu kentta_jonoksi, joka palauttaa jäsenen pyydetyn kentän merkkijonona kentän tyypistä riippumatta. Olisimme tietysti voineet tehdä samanlaisen switch-rakenteen kuin laske_montako_muuta -funktiossakin. Tällöin molempiin aliohjelmiin tulisi samanlainen kokoelma lauseita! Siis parempi kirjoittaa aliohjelma tätä varten.
Tällä kertaa funktiolle ei viety työtilaa parametrina.
õ(BEGIN TEHTAVA)õ
õ(tehtots laske_montako_muuta)õ
Kirjoita funktio laske_montako_muuta käyttäen kentta_jonoksi funktiota.
õ(END TEHTAVA)õ
õ(SUBSECTION Tulos staattiseen muuttujaan)õ
Mihin funktio siis laittaa tuloksensa? Osa C:n standardikirjastojen funktiosta palauttaa esimerkiksi merkkijonon osoittimena staattiseen muuttujaan. Mekin olemme jo tehneet näin virheilmoituksen tapauksessa. Tässä tapauksessa voisimme menetellä siten, että tietyn kokoinen staattinen merkkijono on varattu funktion tulokselle. Haluttu jono kopioidaan sitten tälle alueelle ja alueen osoite palautetaan. Käytännössä tämä tietysti tarkoittaa sitä, ettei seuraava ohjelman osa toimisi halutulla tavalla:
char *jmaksu,*maksu;
...
jmaksu = kentta_jonoksi(9,jasen);
maksu = kentta_jonoksi(10,jasen);
if (strcmp(jmaksu,maksu)==0) ... /* VÄÄRIN! */
Miksei toimisi? Tietysti siksi, koska kumpikin kutsu laittaa tuloksen samaan paikkaan ja molemmat edellisistä osoitteista saisivat saman arvon.
Mitään ongelmaa ei kuitenkaan tule, mikäli funktion palauttamassa osoitteessa oleva jono kopioidaan aina heti kutsun jälkeen turvalliseen paikkaan:
kopioi_jono(N_S(isana),kentta_jonoksi(kentta,jasen));
õ(SUBSECTION kentta_jonoksi (kerhorak.c))õ
õ(IXREF kentta_jonoksi)õ
õ(IXREF kerhorak.c)õ
Kun aliohjelmaa ruvetaan suunnittelemaa, tulee ensiksi mieleen rakenne:
switch (kentta) {
case NIMIKENTTA: kopioi_jono(N_S(kentta_jonona),jasen->nimi); break;
case SOTUKENTTA: kopioi_jono(N_S(kentta_jonona),jasen->sotu); break;
...
case JMAKSUKENTTA: double_jonoksi(N_S(kentta_jonona),jasen->jmaksu,"%4.2lf");
break;
...
default : kopioi_jono(N_S(kentta_jonona),"VIRHE!"); break;
}
return kentta_jonona;
l 5,R 65,J,T 5
Rakenteessa ei ole mitään suurta vikaa! Kuitenkin saatetaan tehdä seuraavia huomioita:
õ(BEGIN HYPHENS)õ
double_jonoksi tekee myös kopioi_jono kutsun, siis numeerisissa tapauksissa niitä tulee turhaan useita
merkkijonon tapauksessa onkin ehkä turha kopioida jonoa apumuuttujaan; miksei palautettaisi suoraan merkkijonon osoitetta kentässä, onhan jono joka tapauksessa heti kopioitava muualle, mikäli jonoa mielitään käyttää pitempään (koska tulos tuli staattiseen muuttujaan)
myöhemmin kun etsimiseen lisätään <= hakuja ja toteutetaan lajittelu, täytyy jälleen kirjoittaa vastaavat rakenteet
õ(END HYPHENS)õ
Ratkaisu voi olla myös sellainen, että selvitetään ensin kentän tyyppi ja tyypin mukaan toimitaan seuraavasti:
/* õ(FNAME2 etsilaj.5\kerhorak.c)õ */
static)õ char kentta_jonona[80];
/****************************************************************************/
char /* */
*kentta_jonoksi( /* = jonon osoite */
int kentta ,/* s Kenttä, joka muutetaan jonoksi */
Jasen_tyyppi *jasen /* s Jäsen jonka kenttä otetaan */
)
{
void *p;
int tyyppi,i; double d;
tyyppi = kentan_tyyppi(kentta,jasen); p = kentan_osoite(kentta,jasen);
kentta_jonona[0]=0; /* Alustetaan tyhjäksi. */
switch (tyyppi) {
case Tsotu:
case Tjono:
return p;
case Tint:
i = *(int *)p;
if ( i == TYHJA_ARVO ) break;
sprintf(kentta_jonona,"%d",i);
break;
case Tdouble:
d = *(double *)p;
if ( d == TYHJA_ARVO ) break;
sprintf(kentta_jonona,"%4.2lf",d);
break;
default:
kopioi_jono(N_S(kentta_jonona),"VIRHE!"); break;
}
return kentta_jonona;
}
l 5,R 65,J,T 5
õ(SUBSECTION kentan_tyyppi ja kentan_osoite (kerhorak.c))õ
Likainen työ jätettiin jälleen aliohjelmille.
õ(IXREF kentan_tyyppi)õ
õ(IXREF kentan_osoite)õ
Funktio kentan_osoite olisi likipitäen samanlainen kuin aluksi kaavailemamme rakenne funktiolle kentta_jonoksi:
/****************************************************************************/
void /* NULL = tuntematon kentän numero */
*kentan_osoite( /* muut = osoitin kentän alkuun */
int nro ,/* s Kentän numero, jonka osoitin halutaan. */
Jasen_tyyppi *jasen /* s Jäsen, jonka kentän osoite halutaan */
)
{
if (!jasen) return NULL;
switch (nro) {
case NIMIKENTTA : return jasen->nimi;
case SOTUKENTTA : return jasen->sotu;
case KATUKENTTA : return jasen->katuosoite;
case POSTINROKENTTA : return jasen->postinumero;
case POSTIOSKENTTA : return jasen->postiosoite;
case KOTIPUHKENTTA : return jasen->kotipuhelin;
case TYOPUHKENTTA : return jasen->tyopuhelin;
case AUTOPUHKENTTA : return jasen->autopuhelin;
case LIITTYMISKENTTA: return &jasen->liittymisvuosi;
case JMAKSUKENTTA : return &jasen->jmaksu;
case MAKSUKENTTA : return &jasen->maksu;
case LISATIETOJAKENTTA: return jasen->lisatietoja;
default: return NULL;
}
}
Funktio kentan_tyyppi olisi aivan vastaava:
/****************************************************************************/
Tyypit /* -1 = tuntematon kentän numero */
kentan_tyyppi( /* muut = kentän tyyppi */
int nro ,/* s Kentän numero, jonka tyyppi halutaan. */
Jasen_tyyppi *jasen /* s Jäsen, jonka kentän tyyppi halutaan. */
)
{
if (!jasen) return -1;
switch (nro) {
case NIMIKENTTA : return Tjono;
case SOTUKENTTA : return Tsotu;
case KATUKENTTA : return Tjono;
case POSTINROKENTTA : return Tjono;
case POSTIOSKENTTA : return Tjono;
case KOTIPUHKENTTA : return Tjono;
case TYOPUHKENTTA : return Tjono;
case AUTOPUHKENTTA : return Tjono;
case LIITTYMISKENTTA: return Tint ;
case JMAKSUKENTTA : return Tdouble;
case MAKSUKENTTA : return Tdouble;
case LISATIETOJAKENTTA: return Tjono;
default: return -1;
}
}
l 5,R 65,J,T 5
Funktiossa kentan_tyyppi parametri jasen on tietenkin hieman turha. Pidämme sen kuitenkin mukana tulevia tarpeita varten!
Myöhemmin käänteistä funktiota jono_kentaksi kirjoitettaessa tarvitsemme myös funktion kentan_pituus, jottei tekstikentissä kopioida kentän ulkopuolelle.
õ(BEGIN TEHTAVA)õ õ(IXREF kentan_pituus)õ
õ(tehtots kentan_pituus)õ
Kirjoita funktio kentan_pituus(nro,jasen).
õ(END TEHTAVA)õ
õ(SECTION void * ja tyypinmuunnos)õ
õ(SUBSECTION void *)õ
õ(IXMASTER void *)õ
õ(IXREF void, osoitin)õ
õ(IXREF osoitin, void)õ
Funktio kentan_osoite esiteltiin void * -tyyppiseksi. Miksi? Koska emme kuitenkaan olisi heti voineet valita oikeata tyyppiä funktiolle. void-osoitin on sijoitusyhteensopiva muiden osoittimien kanssa, osoittimeen ei vain liity mitään tyyppiä.
Siis
void *p; double d; char *jono;
...
jono = p; /* OK! */
d = *p; /* EI OLE MIELEKÄS */
...
õ(SUBSECTION Tyypinmuunnos)õ
õ(IXMASTER tyypinmuunnos)õ
Sijoitus saadaan mielekkääksi käyttämällä tyypinmuunnosta:
d = *(double *)p;
Tässä void-osoitin p on aluksi muunnettu tyypinmuunnos operaattorilla (double *) osoittimeksi reaalilukuun ja tämän jälkeen otettu arvo tämän osoittimen osoittamasta paikasta.
Tyypinmuunnosta voidaan käyttää myös korostamaan laskennassa käytettävää tarkkutta:
double d; int n=3;
d = 1/n; /* d = 0 koska 1/n on kokonaisluku! */
d = 1/(double)n /* d = 0.3333... */
õ(SECTION enum)õ õ(IXMASTER enum)õ õ(IXMASTER lueteltu tyyppi)õ
õ(SUBSECTION Tyypit (kerho.h))õ
Edellä olemme käyttäneet nimiä Tjono, Tsotu jne. Nämä voisivat olla määritelty esimerkiksi:
#define Tjono 0 /* String-tyyppi */
#define Tsotu 1 /* Sotu-tyyppi */
#define Tint 2 /* Int-tyyppi */
#define Tdouble 3 /* Double-tyyppi */
Tässä määrittelyssä ei olisi mitään vikaa, mutta esitämme nyt toisen tavan tehdä määrittelyjä, joissa saadaan juokseva numerointi tietyille sanoille:
typedef enum { /* Kentillä käytettävät tietotyypit: */
Tjono)õ, /* Tyyppi string */
Tsotu)õ, /* Tyyppi sotulle */
Tint)õ, /* Tyyppi int */
Tdouble)õ /* Tyyppi double */
} Tyypit)õ;
l 5,R 65,J,T 5
Näin saadaan "uusi tyyppi" Tyypit, jonka arvoina voi olla Tjono, Tsotu, Tint ja Tdouble. Käytännössä vastaavien symbolien arvot ovat 0,1,2 ja 3. Etuna pelkkään #define määrittelyyn verrattuna on se, että jos jonkin muuttujan tyypiksi esitellään Tyypit, niin jotkin debuggerit osaavat tulostaa arvot näyttöön vastaavina symboleina.
Lisäksi enum -määrittelyn etuna on se, ettei itse tarvitse keksiä numerovastikkeita symboleille.
õ(SUBSECTION Syottovirhe_tyyppi)õ
Myös mjonot.h)õ -tiedostossa oleva
/* Vakiot syötön onnistumiselle */
#define SYOTTO_OK)õ 2
#define EI_MAHDU)õ 1
#define OLETUS)õ 0
#define TIEDOSTO_LOPPU)õ -1
#define VIRHE_SYOTOSSA)õ -2
l 5,R 65,J,T 5
voitaisiin esitellä tyyppinä
typedef enum {
VIRHE_SYOTOSSA = -2,
TIEDOSTO_LOPPU ,
OLETUS ,
EI_MAHDU ,
SYOTTO_OK
} Syottovirhe_tyyppi;
Muualla ohjelmassa ei tarvitsisi tehdä mitään muutoksia, mutta jos jokin muuttuja olisi esitelty
Syottovirhe_tyyppi paluu;
...
paluu = f_lue_jono(...
niin debuggeri saattaisi osata näyttää paluu muuttujan arvon vaikkapa muodossa /* OLETUS */.
õ(SUBSECTION Kentta_nrot (kerho.h))õ
Vastaavasti olemme esitelleet
typedef enum {
NIMIKENTTA)õ,
SOTUKENTTA)õ,
KATUKENTTA)õ,
POSTINROKENTTA)õ,
POSTIOSKENTTA)õ,
KOTIPUHKENTTA)õ,
TYOPUHKENTTA)õ,
AUTOPUHKENTTA)õ,
LIITTYMISKENTTA)õ,
JMAKSUKENTTA)õ,
MAKSUKENTTA)õ,
LISATIETOJAKENTTA)õ
} Kentta_nrot)õ;
õ(BEGIN TEHTAVA)õ
õ(tehtots Viikonpäivät)õ
Esitä sekä #define että enum avulla miten symboleille Su, Ma, Ti... saataisiin arvot 0,1,2...
õ(END TEHTAVA)õ
õ(BEGIN TEHTAVA)õ
õ(tehtots Pelikortit)õ
Esitä sekä #define että enum avulla miten symboleille Pata, Hertta, Risti ja Ruutu saataisiin arvot 0,1,2,3. Määrittele sitten Kortti_tyyppi-tietue, jossa on kortin maa ja arvo. Määrittele vielä tyyppi Korttipakka, jossa on 52 korttia jotka ovat tyyppiä Kortti_tyyppi.
õ(END TEHTAVA)õ
õ(SECTION Selailu)õ
Kun etsittävän ehdon täyttävät tietueet ovat löytyneet, voitaisiin niitä selailla suhteellisen helposti:
õ(SUBSECTION selaile (kerhoets.c))õ
õ(IXREF selailu)õ
õ(IXREF kerhoets.c)õ
suunta = 0;
while (1) {
- lisää kohdalla olevaan suunta
- korjaa sallitun välin sisälle
- tulosta kohdalla oleva
painettu = odota_nappain(sallitut,RET,VAIN_ISOT);
switch (painettu) {
case '-': suunta = -1; break;
case '+': suunta = 1; break;
default : return painettu;
}
}
õ(SUBSECTION Selaus_tyyppi (kerho.h))õ
Selailun tarvitsemia tietoja voitaisiin välittää vaikkapa tietueella:
typedef struct { /* Selauksessa apuna käytettävä tietue. */
char viesti[400]; /* Näytölle selausta varten tuleva viesti. */
char vali; /* Välimerkki, mikäli viesti joud. jatkam. */
char sallitut[80]; /* Kenttälistan sallitut valintakirjaimet. */
int kohdalla; /* selattavat-taulukon nyt kohd oleva alkio.*/
Jarjestys_tyyppi selattavat; /* Taulukko jossa selattavat indeksit. */
} Selaus_tyyppi)õ;
l 5,R 65,J,T 5
Viestinhän täytyy näytöllä vaihtua sen mukaan onko eteenpäin ja/tai taaksepäin edes mahdollista siirtyä.
õ(BEGIN TEHTAVA)õ
õ(tehtots Koko kerhon selailu)õ
Jos meillä on käytössä hakuehdon kysyminen, etsiminen ja selailu, niin tarvitseeko koko kerhon selaamista varten tehdä oma aliohjelma?
õ(END TEHTAVA)õ
õ(SECTION Lajittelu)õ õ(IXREF lajittelu)õ
Lajittelun vaatimia algoritmeja olemme käsitelleet jo aikaisemmin. Mikä tahansa aikaisemmin mainituista algoritmeista olisi helppo soveltaa jäsentaulukkoon. Kuitenkin lähes kaikki oppimamme algoritmit olivat kompleksisuudeltaan O(n2)õ). Jos jäsenmäärä kasvaa paljon yli sadan, tarkoittaa tämä suhteellisen hidasta lajittelua.
õ(IXMASTER qsort)õ
C-kielen standardikirjasto stdlib.h tarjoaa valmiin QuickSort)õ lajittelualiohjelman qsort, jonka kompleksisuus on O(n log n). Miten lajitteluohjelma voidaan tehdä yleiskäyttöiseksi? Idea on siinä, että lajiteltiin mitä aineistoa tahansa, niin lähes ainoa aineistosta riippuva seikka on se, miten päätetään kahdesta alkiosta kumpiko on toistaan suurempi vai ovatko ne samoja.
Siis alkioiden vertailun suorittava aliohjelma kirjoitetaan itse. Sitten tämän aliohjelman osoite viedään qsort aliohjelmalle, jolloin tarvittaessa qsort kutsuu tätä vertailijaa.
õ(SUBSECTION qsort)õ
õ(IXMASTER qsort)õ
Seuraavassa on eräs esimerkki qsort -aliohjelman käytöstä. Ohjelma arpoo (rand)õ) satunnaisen kokonaislukutaulukon ja tämän jälkeen järjestää sen. qsort kutsuu vertailualiohjelmaa kahdella osoitintyyppisellä muuttujalla, jotka osoittavat verrattaviin alkioihin. Osoittimet on määritelty void * -tyyppisiksi. Koska esimerkissämme alkiot ovat kokonaislukuja, pitää osoittimet käytön yhteydessä muuttaa int * -tyyppisiksi.
Vertailualiohjelman pitää palauttaa negatiivinen luku, mikäli 1. alkio on pienempi kuin toinen, 0 mikäli ne ovat samoja ja positiivinen luku, mikäli 1. on suurempi ("erotuksen etumerkki"). Siis tässä tapauksessa lukujen vähennyslasku tuottaa valmiiksi halutunlaisen tuloksen.
õ(IXREF const)õ
...
/* Alkioiden vertailufunktio. */
int sort_function(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
int main(void)
{
int i,x[KOKO];
for (i=0; i
l 5,R 65,J,T 5
qsort -aliohjelman kutsussa pitää kertoa lajiteltavan taulukon (osaa lajitella vain taulukoita) alkuosoite, koko alkioina sekä kunkin alkion koko, sekä vertailufunktion osoite.
Huomattakoon, ettei kutsun viimeinen parametri sort_function aiheuta kutsua aliohjelmaan sort_function, vaan välittää qsort aliohjelmalle lajittelufunktion osoitteen. Kääntäjä tietää tämän eron siitä, ettei funktion nimen perässä ole sulkuja!
õ(SUBSECTION const)õ õ(IXMASTER const)õ
Edellä const void *a tarkoitti vain sitä, että tällä korostetaan ettei aliohjelmassa muuteta osoittimen a osoittamaa muistipaikkaa. Jokin kääntäjä antaisi virheen sijoituksesta
*(int *)a = 5;
mutta osa kääntäjistä ei välitä tästäkään mitään. Siis const on lähinnä informatiivinen ja sen noudattaminen saattaa jäädä ohjelmoijan huoleksi!
õ(SUBSECTION volatile)õ õ(IXMASTER volatile)õ
const-määreelle lähes päinvastainen on volatile-määre (suom. epävakaa). Tällä korostetaan sitä, että jokin taustaprosessi tai rinnakkainen aliohjelma saattaa muuttaa muistipaikan sisältöä ilman mitään ohjelmassa näkyvää sijoitusta. Esimerkiksi tietoliikenneohjelmassa voisi olla muuttuja linja_varattu, jota muuttaisi taustalla toimiva kommunikointipaketti:
volatile int linja_varattu;
...
set_param(LINE_RESERVED,&linja_varattu);
...
dial_number("112"); /* soittelee taustalla kunnes pääsee läpi */
while ( linja_varattu && !lopetus() )
do_sound(VARATTU_AANI);
...
Esimerkissä voisi olla myös
const volatile int linja_varattu;
koska itse pääohjelmalla ei ole mielekästä sijoittaa arvoa ko. muuttujaan. Nämä ominaisuudet ovat kuitenkin edistyneempien kurssien asioita.
õ(SUBSECTION Permutaatiotaulu)õ õ(IXMASTER permutaatio)õ
Jäsenrekisteristä voitaisiin lajitella se taulukko, jossa on osoittimet jäseniin. Mikäli joku kuitenkin haluaisi säilyttää alkuperäisenkin järjestyksen, voisimme yrittää keksiä tapoja lajitella aineisto siten, että siihen olisi yhtäaikaa useita eri järjestyksiä.
Helpoin ratkaisu tähän on permutaatiotaulukoiden käyttö. Aikaisempi etsimisessä mallina ollut jäsenrekisteri voitaisiin lajitella vaikkapa nimen ja postinumeron mukaan:
**jasenet ³ o ³
Jarjestys_tyyppi ÀÄÄÄÄÄÄÅÄÄÄÄÄÄÙ Jasen_tyyppi
ÚÄÄÄ¿nimen_mukaan ³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
max_koko ³ 7 ³ v ³Kassinen Katto³
indekseja³ 3 ³ ÚÄÄÄÄÄÄÄÄÄÄ¿ ³Katto ³
*indeksit³ o ³ ÚÄÄÄ>jasenet[0] ³ oÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄ>³3452 ³
ÀÄÅÄÙ ³ ÃÄÄÄÄÄÄÄÄÄÄ´ ³... ³
³ ³ÚÄÄ>jasenet[1] ³ oÄÄÄÄÄÅÄÄÄÄÄÄÄÄ¿ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
v ³³ ÃÄÄÄÄÄÄÄÄÄÄ´ ³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÚÄÄÄ¿ ÚÅÅÄÄ>jasenet[2] ³ oÄÄÄÄÄÅÄÄÄÄÄÄ¿ ³ ³Susi Sepe ³
0 ³ 2 ÃÄÙ³³ ÃÄÄÄÄÄÄÄÄÄÄ´ ³ ÀÄÄÄÄÄ>³Perämetsä ³
ÃÄÄÄ´ ³³ ... ³ ³ ³ ³- ³
1 ³ 0 ÃÄÄÙ³ ÃÄÄÄÄÄÄÄÄÄÄ´ ³ ³... ³
ÃÄÄÄ´ ³ ³ ³ ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
2 ³ 1 ÃÄÄÄÙ ÃÄÄÄÄÄÄÄÄÄÄ´ ³ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÃÄÄÄ´ ³ ³ ÀÄÄÄÄÄÄÄ>³Ankka Aku ³
3 ³ ? ³ ÃÄÄÄÄÄÄÄÄÄÄ´ ³Ankkalinna ³
ÃÄÄÄ´ ³ ³ ³1234 ³
4 ³ ? ³ ÃÄÄÄÄÄÄÄÄÄÄ´ ³... ³
ÃÄÄÄ´ ³ ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
5 ³ ? ³ ÀÄÄÄÄÄÄÄÄÄÄÙ
ÃÄÄÄ´ osoitintaulukko henkilöihin
6 ³ ? ³
ÃÄÄÄ´
7 ³ ? ³ indeksitaulukko joka osoittaa järjestyksen
ÀÄÄÄÙ
l 5,R 65,J,T 5
Jarjestys_tyyppi nimen_mukaan
ÚÄÄÄÄÄ¿
max_koko ³ 7 ³ 0 1 2 3 4 5 6
indekseja³ 3 ³ ÚÄÄÂÄÄÂÄÄÂÄÄÂÄÄÂÄÄÂÄÄ¿
*indeksit ³ oÄÄÅÄÄÄÄÄÄ>³ 2³ 0³ 1³ ?³ ?³ ?³ ?³
ÀÄÄÄÄÄÙ ÀÄÄÁÄÄÁÄÄÁÄÄÁÄÄÁÄÄÁÄÄÙ
Jarjestys_tyyppi postin_mukaan
ÚÄÄÄÄÄ¿
max_koko ³ 7 ³ 0 1 2 3 4 5 6
indekseja³ 3 ³ ÚÄÄÂÄÄÂÄÄÂÄÄÂÄÄÂÄÄÂÄÄ¿
*indeksit ³ oÄÄÅÄÄÄÄÄÄ>³ 1³ 2³ 0³ ?³ ?³ ?³ ?³
ÀÄÄÄÄÄÙ ÀÄÄÁÄÄÁÄÄÁÄÄÁÄÄÁÄÄÁÄÄÙ
Lajittelu aloitetaan siten, että järjestettävä permutaatiotaulukko alustetaan johonkin järjestykseen. Esimerkiksi:
Jarjestys_tyyppi nimen_mukaan
ÚÄÄÄÄÄ¿
max_koko ³ 7 ³ 0 1 2 3 4 5 6
indekseja³ 3 ³ ÚÄÄÂÄÄÂÄÄÂÄÄÂÄÄÂÄÄÂÄÄ¿
*indeksit ³ oÄÄÅÄÄÄÄÄÄ>³ 0³ 1³ 2³ ?³ ?³ ?³ ?³
ÀÄÄÄÄÄÙ ÀÄÄÁÄÄÁÄÄÁÄÄÁÄÄÁÄÄÁÄÄÙ
^ ^
aÄÄÄÙ ÀÄÄÄÄb
Tämän jälkeen lajitteluohjelmalle annetaan lajiteltavaksi taulukko nimen_mukaan.indeksit. qsort välittää vertailualiohjelmalle verrattavaksi osoittimet a ja b. Meidän täytyy siis katsoa miten suhtautuvat toisiinsa nimet
kerho->jasenet[*(int *)a]->nimi
kerho->jasenet[*(int *)b]->nimi
Tämän homman hoitaa esimerkiksi strcmp -funktio, joka tosin järjestää skandit hieman väärään paikkaan, mutta olkoon tällä kertaa. Aliohjelma on helppo kirjoittaa uusiksi, mikäli ominaisuus haittaa enemmän. Vertailu on case-sensitive)õ, eli Zorro < aapinen!
õ(IXMASTER strcmp)õ
Jos haluamme lajittelusta aliohjelman, joka osaa järjestää minkä kentän mukaan tahansa, täytyisi kentän numero saada välitettyä vertailu-aliohjelmalle! Tätä mahdollisuutta qsort ei tarjoa, joten joudumme keksimään jonkin toisen ratkaisun.
õ(SUBSECTION Aliohjelmien yhteiset muuttujat)õ
Haluamme lisäksi säilyttää koko kerhorekisterin läpi säilyneen ominaisuuden, että meillä olisi mahdollista rinnakkain käsitellä useita eri kerhoja (!), joten myös kerho pitäisi välittää tavalla tai toisella vertailu-aliohjelmalle.
Aliohjelmien väliseen tiedonvälitykseen tehdään tietue, johon kasataan kaikki yhteisesti tarvittavat muuttujat. Ongelmassamme niitä on kentan_nro ja osoitin käyttämämme kerhon jasenet -taulukon alkuun. Siis ne tietueeseen.
õ(IXREF static)õ
õ(IXMASTER lajittele)õ
õ(IXMASTER vertaile)õ
typedef struct { /* Lajittelussa apuna käytettävä tietue. */
int kentan_nro; /* Kenttä jonka mukaan lajitellaan. */
Jasen_tyyppi **jasenet; /* Osoitin osoitintaulukon alkuun. */
} Vertaa_tyyppi)õ; /* */
static Vertaa_tyyppi VERTAA)õ; /* Tiedonvälitys lajittele -> vertaile */
int vertaile(const void *a, const void *b)
{
char st[40];
kopioi_jono(N_S(st),
kentta_jonoksi(VERTAA.kentan_nro,VERTAA.jasenet[*(int *)a]));
return (strcmp(
st,
kentta_jonoksi(VERTAA.kentan_nro,VERTAA.jasenet[*(int *)b]));
));
}
void lajittele(Kerho_tyyppi *kerho,Jarjestys_tyyppi *jarj,int kentan_nro)
{
int j,ind,max_ind;
if ( (kentan_nro < 0) || !jarj->jarjesta ) return;
if ( jarj->indekseja == 0 ) { /* Alustetaan perm. taulukko */
max_ind = jarj->max_koko;
if ( kerho->jasenia < max_ind ) max_ind = kerho->jasenia;
ind = 0;
for (j=0; jjasenet[j] ) /* NULL-jäseniä ei laiteta */
jarj->indeksit[ind++] = j;
jarj->indekseja = ind;
}
VERTAA.kentan_nro = kentan_nro;
VERTAA.jasenet = kerho->jasenet;
qsort( (void *)(jarj->indeksit), /* Lajiteltava taulukko */
jarj->indekseja, /* Taulukon alkioiden lukumäärä */
sizeof(jarj->indeksit[0]), /* Yksittäisen alkion koko */
vertaile); /* Vertailualiohjelman nimi */
}
l 5,R 65,J,T 5
lajittele -aliohjelma tekee tarvittavat alustukset, mm. laittaa permutaatiotaulukon johonkin järjestykseen (tässä tapauksessa ehdollisesti, eli jos taulukolla jo on järjestys, ei sitä sotketa), laittaa arvot yhteisille muuttujille ja kutsuu qsort -aliohjelmaa tarvittavilla parametreilla.
õ(BEGIN TEHTAVA)õ
õ(tehtots Etsimisen tuloksen lajittelu)õ
Tarvitseeko lajittele -aliohjelma muutoksia, jotta se voisi lajitella myös etsimisen tuloksena saadun taulukon? Miten etsimisen tulos lajiteltaisiin etsimisen päätteeksi?
õ(END TEHTAVA)õ
õ(BEGIN TEHTAVA)õ
õ(tehtots Selailu puhelinnumeron mukaan)õ
Miten käyttäjä voisi selata koko kerhon jäsenistöä puhelinnumeron mukaisessa järjestyksessä?
õ(END TEHTAVA)õ
õ(BEGIN TEHTAVA)õ
õ(TehtOts Vertailu isot ja pienet samaistaen)õ
Mikäli haluttaisiin järjestys, jossa aapinen < Zorro, pitäisi vertailun ajaksi isot ja pienet kirjaimet samaistaa. Ongelmaa voitaisiin ratkaista seuraavalla aliohjelmalla
int vertaile(const void *a, const void *b)
{
char ai[80],bi[80];
kopioi_jono(N_S(ai),kentta_jonoksi(VERTAA.kentan_nro,VERTAA.jasenet[*(int *)a]));
kopioi_jono(N_S(bi),kentta_jonoksi(VERTAA.kentan_nro,VERTAA.jasenet[*(int *)b]));
return strcmp(jono_isoksi(ai),jono_isoksi(bi));
}
l 5,R 65,J,T 5
Mitä vikaa aliohjelmassa kuitenkin on?
õ(END TEHTAVA)õ
õ(SECTION Oikeaoppinen lajittelu)õ
Käytännössä lajittelusta on hyvin tarkat säännöt. Esimerkiksi kirjaston lajittelusääntöjen mukaan kaikki välimerkit samaistetaan. Saksalaisessa lajittelussa Ä:t samaistetaan A kirjaimeen ja englantilaisessa McAnkka ja MacAnkka lajitellaan samaan kohtaan.
Näiden sääntöjen kirjoittaminen vertaile aliohjelmaan hidastaisi lajittelua huomattavasti. Käytännössä ongelma ratkaistaan siten, että lajittelussa käytetään avaimia, jotka muodostetaan ennen lajittelun alkua.
Esimerkiksi tyypissä Jasen_tyyppi voisi olla yksi ylimääräinen tietue, joka toimisi avaimena. Mikäli lajittelu tehdään nimen mukaan, muodostetaan nimestä lajittelusäännöt täyttävä avain tähän kenttään.
õ(IXMASTER avain)õ
saksa: Äystö Yrjö -> AYSTO YRJO
Gauá Karl F -> GAUSS KARL F
suomi: Äystö Yrjö -> \YST] YRJ] (koska ASCIIssa XYZ[\] )
Mikäli lajittelu tehtäisiin sotun mukaan, muodostettaisiin sotu-kentästä avain siten, että vuosiluku siirrettäisiin ensimmäiseksi, kuukausi seuraavaksi jne.
010245-123U -> 450201-123U
020347-123T -> 470302-123T
õ(SUBSECTION vertaile (kerhoets.c))õ
õ(IXREF avain)õ
Itse vertailu olisi
int vertaile(const void *a, const void *b)
{
return strcmp(VERTAA.jasenet[*(int *)a]->avain,VERTAA.jasenet[*(int *)b]->avain);
}
l 5,R 65,J,T 5
õ(SUBSECTION lajittele (kerhoets.c))õ
õ(IXREF lajittelu, avaimen mukaan)õ
lajittele aliohjelmaan lisättäisiin lauseet avaimien muodostamiseksi:
...
for (j=0; jindekseja; j++)
tee_avain(kentan_nro,kerho->jasenet[jarj->indeksit[j]]);
qsort(...
õ(SUBSECTION alusta_jarjestys (kerhoets.c) )õ
õ(IXREF alusta_jarjestys)õ
Kirjainten samaistus suoritettaisiin siten, että olisi käytössä taulukko, jossa olisi kunkin kirjaimen ASCII-koodiarvon kohdalla kirjaimelle uusi koodi, sen mukaan mihin kohti kirjain lajitellaan. Voisimme esimerkiksi numeroida:
0x20 = välimerkit
0x30 = '0'
0x31 = '1'
..
0x39 = '9'
0x41 = 'A' ja 'a' (saksassa myös 'Ä' ja 'ä')
0x42 = 'B' ja 'b'
...
Tätä varten tarvitsemme tyypin:
typedef struct { /* Avaimen muodostuksessa käytettä tyyppi */
int alustettu; /* Onko taulukko alustettu vai ei. */
char avainarvo[MERKKEJA]; /* Miten kukin kirjain muuttuu */
} Jarjestys_avain_tyyppi)õ; /*
static Jarjestys_avain_tyyppi
JARJESTYS)õ = {0,""}; /* Avaimen muodostuksessa käytettävä taul. */
l 5,R 65,J,T 5
Siis taulukko alustettaisiin seuraavasti:
JARJESTYS.alustettu = 1;
JARJESTYS.avainarvo[(unsigned char) ','] = 0x20;
JARJESTYS.avainarvo[(unsigned char) ' '] = 0x20;
...
JARJESTYS.avainarvo[(unsigned char) 'A'] = 0x41;
JARJESTYS.avainarvo[(unsigned char) 'a'] = 0x41;
JARJESTYS.avainarvo[(unsigned char) 'B'] = 0x42;
JARJESTYS.avainarvo[(unsigned char) 'b'] = 0x42;
...
JARJESTYS.avainarvo[(unsigned char) 'Ä'] = 0x5c;
JARJESTYS.avainarvo[(unsigned char) 'ä'] = 0x5c;
...
Ehkä on kuitenkin helpompi käyttää muutamaa makroa:
#define A_1)õ(mika,miksi) j->avainarvo[(unsigned char)mika] = miksi
#define A_A)õ(mi,mp,miksi) A_1(mi,miksi); A_1(mp,miksi)
/****************************************************************************/
void alusta_jarjestys)õ(Jarjestys_avain_tyyppi *j)
{
int i;
if (j->alustettu) return;
j->alustettu = 1;
for (i=0; i
l 5,R 65,J,T 5
Avain muodostetaan nyt JARJESTYS.avainarvo -taulukkoa käyttäen. Kuitenkin erikoistapaukset kuten Mac ja Mc täytyisi käsitellä ensin erikseen vaikkapa Mc -> Mac.
õ(BEGIN TEHTAVA)õ
õ(tehtots A_1 ja A_A)õ
Kirjoita auki muutama makrojen A_1 ja A_A esiintymä.
õ(END TEHTAVA)õ
õ(SUBSECTION tee_avain (kerhoets.c))õ õ(IXREF tee_avain)õ
/****************************************************************************/
void tee_avain(int kentan_nro, Jasen_tyyppi *jasen)
{
void *p; char s[20]; unsigned char *a;
int i; double d;
int tyyppi;
if (!JARJESTYS.alustettu) alusta_jarjestys(&JARJESTYS);
i = sizeof(jasen->avain);
if ( i < 20 ) {
printf("TEE AVAIN: Liian pieni avainkenttä!\n");
return;
}
tyyppi = kentan_tyyppi(kentan_nro,jasen);
p = kentan_osoite(kentan_nro,jasen);
switch (tyyppi) {
case Tjono:
kopioi_jono(N_S(jasen->avain),p);
poista_tyhjat(jasen->avain);
for (a=(unsigned char *)jasen->avain; *a; a++) {
*a = JARJESTYS.avainarvo[*a];
}
poista_tyhjat(jasen->avain);
return;
case Tsotu:
kopioi_jono(N_S(s),p); liita_jono(N_S(s)," ");
kopioi_jono(N_S(jasen->avain),s);
jasen->avain[0] = s[4]; /* Vaihdetaan pv ja vuosi keskenään! */
jasen->avain[1] = s[5];
jasen->avain[4] = s[0];
jasen->avain[5] = s[1];
return;
case Tint:
i = *(int *)p;
sprintf(jasen->avain,"%+05d",i);
if ( jasen->avain[0] == '-' ) jasen->avain[0]='+'-1; /* jotta - < + */
return;
case Tdouble:
d = *(double *)p;
sprintf(jasen->avain,"%+015.7lf",d);
if ( jasen->avain[0] == '-' ) jasen->avain[0]='+'-1; /* jotta - < + */
return;
default:
printf("TEE AVAIN: Ei ole kenttää %d!\n",kentan_nro);
return;
}
}
l 5,R 65,J,T 5
õ(BEGIN TEHTAVA)õ
õ(TehtOts tee_avain)õ
Miksi kokonais- ja reaaliluvut käsiteltiin kuten edellä eikä käyttäen aliohjelmaa kentta_jonoksi?
"Kommentoi" (eli miksi tehdään?) tee_avain aliohjelman jokainen rivi.
Miten MacAnkka ja McAnkka käsiteltäisiin?
Miten käsiteltäisiin Gauá?
õ(END TEHTAVA)õ
õ(SECTION Haku epäyhtälö -ehdoilla)õ õ(IXREF hakuehto)õ
Miten toteutaisimme haun sillä tavoin, että haku olisi mahdollista myös ehdoilla:
>=50
!=*ankka*
<=Kassinen
== eli etsitään tyhjää kenttää
Puuttuuko ohjelmastamme paljon, jotta tämä voitaisiin tehdä? Mistä yleensä on kyse?
Ensin pitäisi erottaa annetusta hakuehdosta onko kyseessä normaali haku vaiko epäyhtälöhaku. Miten tämä tehtäisiin? Tutkitaan onko hakuehdon alussa jokin merkkijonoista
"==", "!=", "<=" "<" ">" ">="
Mitenkä tutkittaisiin? Esimerkiksi:
if ( strstr(maski,"==") == maski )...
else if ( strstr(maski,"!=") == maski )...
...
õ(SUBSECTION EHDOT -taulukko (kerhoets.c))õ
Tällainen vertailu sopii, mikäli erikoisehtoja olisi hyvin vähän. Nyt niitä kuitenkin on suhteellisen monta, joten on ehkä helpompi tehdä taulukko, jossa on ehdot ja mitä ehdoilla tehdään:
/****************************************************************************/
typedef enum {
YHT,
ERIS,
PIEN,
PIENYHT,
SUUR,
SUURYHT
} Vertailu_oper_tyyppi)õ;
typedef struct {
char *ehto;
int pit;
Vertailu_oper_tyyppi kasky;
} Vertailu_tyyppi)õ;
static Vertailu_tyyppi EHDOT)õ[] = {
{ "" , 0, YHT},
{ "==", 2, YHT},
{ "!=", 2, ERIS},
{ "<=", 2, PIENYHT},
{ "<" , 1, PIEN},
{ ">=", 2, SUURYHT},
{ ">" , 1, SUUR},
{ NULL, 0, YHT}
};
l 5,R 65,J,T 5
õ(SUBSECTION tutki_tasmaako (kerhoets.c))õ
õ(IXREF tutki_tasmaako)õ
Aliohjelmassa etsi_indeksit muutetaan wildmat -kutsu kutsuksi tutki_tasmaako. Aliohjelma tarvitsee muutaman lisäparametrin, jotta tarpeen vaatiessa osataan muuttaa kenttiä avaimiksi. Miksikö avaimiksi? No tietysti siksi, että avain rakennettiin siten, että aakkosjärjestys, sotujen järjestys yms. pitävät paikkansa.
Aliohjelman aluksi etsitään onko kyse jostakin erikoisoperaatiosta. Mikäli ei ole toimitaan kuten ennenkin. Mikäli on kyse jostakin erikoisesta operaatiosta, poistetaan hakumaskin alusta operaatio.
/****************************************************************************/
int /* 1 = ei täsmää */
tutki_tasmaako( /* 0 = täsmää */
Jasen_tyyppi *jasen ,/* s Tutkittva jäsen */
char *ikentta ,/* s Kenttä muutettuna isoiksi kirjaimeksi */
char *maski ,/* s Maski muutettuna isoiksi kirjaimeksi */
int knro /* s Kentän numero. */
)
{
int i,tulos,ehto_ind=0; char *m; Jasen_tyyppi mjasen;
for (i=1; EHDOT[i].ehto; i++)
if ( strstr(maski,EHDOT[i].ehto) == maski ) {
ehto_ind = i; break;
}
m = maski+EHDOT[ehto_ind].pit;
switch ( EHDOT[ehto_ind].kasky ) {
case YHT:
return wildmat(ikentta,m);
case ERIS:
return !wildmat(ikentta,m);
case PIEN:
case PIENYHT:
case SUUR:
case SUURYHT:
jono_kentaksi(knro,&mjasen,m);
tee_avain(knro,&mjasen);
tee_avain(knro,jasen);
tulos = strcmp(jasen->avain,mjasen.avain);
switch ( EHDOT[ehto_ind].kasky ) {
case PIEN: return !(tulos<0);
case PIENYHT: return !(tulos<=0);
case SUUR: return !(tulos>0);
case SUURYHT: return !(tulos>=0);
}
default:
return 1;
}
}
l 5,R 65,J,T 5
õ(BEGIN TEHTAVA)õ
õ(tehtots tutki_tasmaako)õ
Miksi EHDOT taulukossa "<=" on ennen "<" operaatiota?
"Kommentoi" funktion tutki_tasmaako jokainen lause!
õ(END TEHTAVA)õ
õ(SECTION Lopuksi)õ
Tässä luvussa ohjelma on kerralla kehittynyt varsin paljon! Lukijan ei kuitenkaan pidä tälläkään kertaa erehtyä luulemaan, että kaikki olisi tehty kerralla ja oikein. Ohjelmaan on jälleen lisätty aina pienin mahdollinen lisä kerrallaan ja tämä on testattu.
Näin hitaasti edeten koko kokonaisuus on saatu valmiiksi. Välillä on jouduttu muuttamaan joidenkin aliohjelmien parametreja, jotta ne kävisivät myös jonkin toisen ongelman ratkaisemiseen.
Jos kaikki tässä luvussa esitetty yritettäisiin lisätä kerralla ohjelmaan, tulisi sen testaamisesta varsinainen ongelma: Kuka muistaa testata kaikki kohdat joihin lisäykset vaikuttivat?
Samoin tehdyistä ratkaisuista alkaa näkyä lävitse eräs ohjelmoinnin tärkeimpiä ominaisuuksia: pyrkimys yleisyyteen ja uudelleen käytettävyyteen. Nämä ovat olio-ohjelmoinnin tunnusmerkkejä, mutta niihin kannattaa pyrkiä jo normaalissakin ohjelmoinnissa. Näin ei tarvitse aloittaa olio-ohjelmoinnin kurssia sanoilla: "Unohtakaa kaikki mitä olette oppineet ohjelmoinnista".
õ(IXREF olio-ohjelmointi)õ