* etsiminen taulukkoon
* lajittelu valmiilla qsort- aliohjelmalla
* permutaatiotaulukko
* "oikeaoppinen lajittelu" Etsiminen ja lajittelu ovat eräitä yleisimmin tietojenkäsittelyssä vastaan tulevia tilanteita. Esimerkiksi C- merkkijonon pituuden laskeminen on oikeastaan NUL- merkin paikan etsimistä.
HUOM! Tämän luvun ohjelmalistaukset ovat "pseudo"- koodia, ja niissä voi olla pieniä syntaksivirheitä.
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.
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äishakuLä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_seuraavaVähän samaa ideaa sovellettiin jo aikaisemmin palanen - aliohjelmassa.
class cJarjestys { /* Luokka jonka avulla voidaan pitää eri järjestyksiä. */
int max_koko; /* Indeksitaulukon maksimikoko. */
int indekseja; /* Taulukosta nyt käytetty indekseja. */
int *indeksit /* Osoitin indeksitaulukkoon (dynaaminen). */
...
}; Jos seuraavasta aineistosta etsittäisiin vaikkapa hakuehdolla nimi=="*k*"
**jasenet | o |
cJarjestys +------+------+ cJasen
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 +--+ | +----------| | +----->|Takametsä |
+---| | ... | | | |- |
1 | 2 +----+ +----------| | |... |
+---| | | | +-------------+
2 | ? | +----------| | +-------------+
+---| | | +------->|Ankka Aku |
3 | ? | +----------| |Ankkalinna |
+---| | | |1234 |
4 | ? | +----------| |... |
+---| | | +-------------+
5 | ? | +----------+
+---| osoitintaulukko henkilöihin
6 | ? |
+---|
7 | ? | indeksitaulukko löytyneisiin
+---+
löytyisi jasenet[0] ja jasenet[2], jotka täyttävät hakuehdon. Tällöin etsimisaliohjelma palauttaisi tämän tiedon seuraavasti:
cJarjestys 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; i<etsi.Indekseja(); i++) Kerho- >Jasenet()- >anna(etsi.anna(i)).tulosta(cout)
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 toteuttaa JA ja TAI - tyyppiset haut, tarvitsemme etsimisaliohjelmalle hakuehdon kullekin kentälle.
cHaku voisi olla myös cJasen, mutta koska cJasen kentillä on mahdollisuus saada myös numeerisia arvoja, ei numeeriseen kenttään pystyttäisi tallettamaan esimerkiksi hakuehtoa "4*" tai "<50". Siis cHaku on parasta tehdä merkkijono taulukoksi
class cHaku {
string kentat[KENTTIA];
...
}
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;
}
}
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.
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.
...
/* 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<KOKO; i++) x[i] = rand();
tulosta(x);
qsort((void *)x,KOKO,sizeof(x[0]),sort_function);
tulosta(x);
return 0;
}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!
int ali(const int *a)
{
int b;
*a = 5; // Laiton sijoitus, koska const osoitin ei saa muuttaa kohdettaan
a = b; // Sallittu sijoitus, kohde ei muutu.
}
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.
Helpoin ratkaisu tähän on permutaatiotaulukoiden käyttö. Aikaisempi etsimisessä mallina ollut jäsenrekisteri voitaisiin lajitella vaikkapa nimen ja postinumeron mukaan:
**jasenet | o |
cJarjestys +------+------+ 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 +-+|| +----------| | +----->|Takametsä |
+---| || ... | | | |- |
1 | 0 +--+| +----------| | |... |
+---| | | | | +-------------+
2 | 1 +---+ +----------| | +-------------+
+---| | | +------->|Ankka Aku |
3 | ? | +----------| |Ankkalinna |
+---| | | |1234 |
4 | ? | +----------| |... |
+---| | | +-------------+
5 | ? | +----------+
+---| osoitintaulukko henkilöihin
6 | ? |
+---|
7 | ? | indeksitaulukko joka osoittaa järjestyksen
+---+
cJarjestys nimen_mukaan
+-----+
max_koko | 7 | 0 1 2 3 4 5 6
indekseja| 3 | +--------------------+
*indeksit | o--+------>| 2| 0| 1| ?| ?| ?| ?|
+-----+ +--------------------+
cJarjestys 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:
cJarjestys 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!
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.
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. Seuraavasta esimerkistä puuttuvat saantimetodit, joten se on vain hahmotelma:
typedef struct { /* Lajittelussa apuna käytettävä tietue. */
int kentan_nro; /* Kenttä jonka mukaan lajitellaan. */
cKerho *kerho; /* Lajiteltava kerho */
} tVertaa; /* */
static tVertaa VERTAA; /* Tiedonvälitys lajittele - > vertaile */
int vertaile(const void *a, const void *b)
{
string s1,s2;
s1 = VERTAA.kerho->anna(*(int *)a).kentta_jonoksi(VERTAA.kentan_nro,);
s2 = VERTAA.kerho->anna(*(int *)b).kentta_jonoksi(VERTAA.kentan_nro,);
return (strcmp(s1.c_str(),s2.c_str());
}
void cKerho::lajittele(cJarjestys *jarj,int kentan_nro)
{
int j,ind,max_ind;
if ( (kentan_nro < 0) || !jarj- >jarjesta ) return;
if ( jarj- >Indekseja() == 0 ) { /* Alustetaan perm. taulukko */
for (j=0; j<jasenia; j++)
jarj- >lisaa(j);
}
VERTAA.kentan_nro = kentan_nro;
VERTAA.kerho = this;
qsort( (void *)(jarj- >Indeksit()), /* Lajiteltava taulukko */
jarj- >Indekseja(), /* Taulukon alkioiden lukumäärä */
sizeof(jarj- >anna(0)), /* Yksittäisen alkion koko */
vertaile); /* Vertailualiohjelman nimi */
}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.
int vertaile(const void *a, const void *b)
{
string s1,s2;
s1 = VERTAA.kerho->anna(*(int *)a).kentta_jonoksi(VERTAA.kentan_nro,);
s2 = VERTAA.kerho->anna(*(int *)b).kentta_jonoksi(VERTAA.kentan_nro,);
jono_isoksi(s1); jono_isoksi(s2);
return (strcmp(s1.c_str(),s2.c_str());
}
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.
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
int vertaile(const void *a, const void *b)
{
return strcmp(VERTAA.kerho->anna(*(int *)a).avain,
VERTAA.kerho->anna(*(int *)b).avain);
}
... for (j=0; j<jarj- >Indekseja(); j++) anna(jarj- >anna(j)).tee_avain(kentan_nro); qsort(...
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 luokan:
cJarjestys_avain { /* Avaimen muodostuksessa käytettä tyyppi */
char avainarvo[MERKKEJA]; /* Miten kukin kirjain muuttuu */
void alusta();
public:
cJarjestys_avain() { alusta(); )
int Avainarvo(int i) { return avainarvo[i]; }
} ;
static cJarjestys_avain JARJESTYS;Taulukko alustettaisiin seuraavasti:
void cJarjestys_avain::alusta() {
avainarvo[(unsigned char) ','] = 0x20;
avainarvo[(unsigned char) ' '] = 0x20;
...
avainarvo[(unsigned char) 'A'] = 0x41;
avainarvo[(unsigned char) 'a'] = 0x41;
avainarvo[(unsigned char) 'B'] = 0x42;
avainarvo[(unsigned char) 'b'] = 0x42;
...
avainarvo[(unsigned char) 'Ä'] = 0x5c;
avainarvo[(unsigned char) 'ä'] = 0x5c;
...
}Ehkä on kuitenkin helpompi käyttää muutamaa makroa:
#define A_1 (mika,miksi) avainarvo[(unsigned char)mika] = miksi
#define A_A (mi,mp,miksi) A_1(mi,miksi); A_1(mp,miksi)
/****************************************************************************/
void cJarjestys_avain::alusta() {
{
int i;
for (i=0; i<MERKKEJA; i++) A_1(i,0x20); /* Kaikki tuntemat. merkit välil. */
A_1('0',0x30); A_1('1',0x31); A_1('2',0x32); A_1('3',0x33); A_1('4',0x34);
A_1('5',0x35); A_1('6',0x36); A_1('7',0x37); A_1('8',0x38); A_1('9',0x39);
A_A('A','a',0x41); A_A('B','b',0x42); A_A('C','c',0x43);
A_A('D','d',0x44); A_A('E','e',0x45); A_A('F','f',0x46);
A_A('G','g',0x47); A_A('H','h',0x48); A_A('I','i',0x49);
A_A('J','j',0x4a); A_A('K','k',0x4b); A_A('L','l',0x4c);
A_A('M','m',0x4d); A_A('N','n',0x4e); A_A('O','o',0x4f);
A_A('P','p',0x50); A_A('Q','q',0x51); A_A('R','r',0x52);
A_A('S','s',0x53); A_A('T','t',0x54); A_A('U','u',0x55);
A_A('V','v',0x56); A_A('W','w',0x57); A_A('X','x',0x58);
A_A('Y','y',0x59); A_A('Z','z',0x5a);
A_A('[sinvcircumflex]','',0x59);
A_A('Å','å',0x5b); A_A('Ä','ä',0x5c); A_A('Ö','ö',0x5d);
}
#undef A_1
#undef A_AAvain muodostetaan nyt JARJESTYS.avainarvo - taulukkoa käyttäen. Kuitenkin erikoistapaukset kuten Mac ja Mc täytyisi käsitellä ensin erikseen vaikkapa Mc - >Mac.
/****************************************************************************/
void cJasen::tee_avain(int kentan_nro)
{
void *p; char s[20]; unsigned char *a;
int i; double d;
int tyyppi;
i = sizeof(avain);
if ( i < 20 ) {
printf("TEE AVAIN: Liian pieni avainkenttä!\n");
return;
}
tyyppi = kentan_tyyppi(kentan_nro);
p = kentan_osoite(kentan_nro);
switch (tyyppi) {
case Tjono:
kopioi_jono(N_S(avain),p);
poista_tyhjat(avain);
for (a=(unsigned char *)avain; *a; a++) {
*a = JARJESTYS.avainarvo[*a];
}
poista_tyhjat(avain);
return;
case Tsotu:
kopioi_jono(N_S(s),p); liita_jono(N_S(s)," ");
kopioi_jono(N_S(avain),s);
avain[0] = s[4]; /* Vaihdetaan pv ja vuosi keskenään! */
avain[1] = s[5];
avain[4] = s[0];
avain[5] = s[1];
return;
case Tint:
i = *(int *)p;
sprintf(avain,"%+05d",i);
if ( avain[0] == '- ' ) avain[0]='+'- 1; /* jotta - < + */
return;
case Tdouble:
d = *(double *)p;
sprintf(avain,"%+015.7lf",d);
if ( avain[0] == '- ' ) avain[0]='+'- 1; /* jotta - < + */
return;
default:
printf("TEE AVAIN: Ei ole kenttää %d!\n",kentan_nro);
return;
}
}
>=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 )... ...
/****************************************************************************/
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}
};
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ää */
cJasen::tutki_tasmaako( /* 0 = täsmää */
const char *maski ,/* s Maski muutettuna isoiksi kirjaimeksi */
int knro /* s Kentän numero. */
)
{
int i,tulos,ehto_ind=0; const char *m; cJasen mjasen;
char ikentta[80]; // Kentän knro sisältö isoksi muutettuna merkkijonona
kopioi_jono(N_S(ikentta),kentta_jonoksi(knro));
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:
mjasen.sijoita(knro,m);
mjasen.tee_avain(knro);
tee_avain(knro);
tulos = strcmp(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;
}
}
// Vakioilla // #definellä const YHT = 0; #define YHT 0 const ERIS = 1; #define ERIS 1 const PIEN = 2; #define PIEN 2 const PIENYHT = 3; #define PIENYHT 3 const SUUR = 4; #define SUUR 4 const SUURYHT = 5; #define SUURYHT 5
Oman tyypin Vertailu_oper_tyyppi luomisella on kuitenkin se etu, että voidaan tehdä myös muuttuja joka on samaa tyyppiä. Tällaiseen muuttujaan ei voi sijoittaa muita arvoja (vaikka muuttuja olisikin todellisuudessa tyyppiä int). Lisäksi useat debuggerit näyttävät luettelotyyppisen muuttujan arvon nimellä eikä mitään sanomattomalla kokonaisluvulla.
Hyvässä ohjelmassa on jokaista selvästi eri luettelomaista tyyppiä kohti tehty oma luettelo ja käytetään vain ko. luettelotyypin tyyppisiä muuttujia. Esimerkiksi aliohjelmien virhepalautukset voisivat olla luettelotyyppiä. Valitettavasti luettelotyypin arvon tulostaminen tulostaa vain kokonaisluvun. Usein tulostuksia varten joudutaan tyypin rinnalle tekemään vähän EHDOT- taulukon kaltainen taulukko, jolla tyyppejä voidaan muuttaa selväkielisiksi ja päinvastoin.
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ä.