SZIMP2

A MathWikiből
(Változatok közti eltérés)
1 132. sor: 1 132. sor:
 
   b.bal=NULL;
 
   b.bal=NULL;
 
   b.jobb=NULL;
 
   b.jobb=NULL;
 +
  return 0;
 +
}
 +
 +
== 5. gyakorlat (2007-03-10) ==
 +
 +
A mutatók és struktúrák használatát gyakoroljuk. Bináris keresőfák majd csak a következő gyakorlaton lesznek.
 +
 +
A feladat: Az óvódai évbúcsúztatón kiszámolással döntik el, hogy a csoportból ki lesz az két gyerek, aki Barbapapa elménytábor-bérletet nyer. A csoport tornasorba áll, a két széle összekapcsolódik, majd a legmagasabbtól csökkenő sorrendben elmondanak egy kiszámolós mondókát. Akire az utolsó szótag jut, kiesik, majd a kiszámoló a következő gyerektől újraindul mindaddig, amíg több, mint 2 gyerek van. A feladat meghatározni, hogy a gyerekek milyen sorrendben esnek ki, és melyik két gyerek marad bent utoljára.
 +
 +
A gyerekeket tornasorban 1-től N-ig számozzuk (az első a legmagasabb és az N-edik a legalacsonyabb), a mondóka K szótagból áll. 10000 >= N >= 2 és 10000000 >= K >= 1. A bemenet minden sorában N és K található. Minden bemeneti sorhoz egy kimeneti sort kell előállítani: az sor elejére a kieső gyerekek sorszáma kerül (a kiesés sorrendjében) szóközzel elválasztva, majd egy szóköz, majd egy pontosvessző, majd egy szóköz, majd a bennmaradó két gyerek sorszáma szóközzel elválasztva (először az utolsó kiesőre rákövetkező, majd az őrá következő).
 +
 +
A megoldásban minden gyerekhez fel kell venni egy struktúrát (benne a gyerek sorszámával és a következő gyerekre mutató mutatóval).
 +
 +
Példa bemenet:
 +
 +
9 1
 +
9 2
 +
9 1000
 +
8 10000000
 +
 +
A példa bemenethez tartozó kimenet:
 +
 +
1 2 3 4 5 6 7 ; 8 9
 +
2 4 6 8 1 5 9 ; 3 7
 +
1 9 7 4 3 2 5 ; 6 8
 +
8 3 7 6 5 1 ; 2 4
 +
 +
Az alábbi vázlatból lehet kiindulni (~/szimp2/gyerekki.c):
 +
 +
#include <stdio.h>
 +
 +
struct gyerek {
 +
  int szam;
 +
  struct gyerek *kov;
 +
};
 +
 +
struct gyerek t[10000];
 +
 +
int main(void) {
 +
  int n, k;
 +
  iny i;
 +
  /** Az akt változó minden kiszámolás kezdete előtt arra a gyerekre mutat, aki
 +
    * _után_ a kiszámolás elkezdődik. A kiszámolás végeztével pedig arra a
 +
    * gyerekre mutat, aki _után_ a kiszámolás utolsó szótagja esik.
 +
    */
 +
  struct gyerek *akt;
 +
  while (2==scanf("%d%d", &n, &k)) {
 +
    for (i=0;i<n;i++) {
 +
      ...
 +
    }                 
 +
    t[n-1].kov=&t[0];
 +
    akt=...;
 +
    ...
 +
    printf("; %d %d\n", ...egyikutolso, ...masikutolso);
 +
  }
 
   return 0;
 
   return 0;
 
  }
 
  }

A lap 2007. március 10., 00:01-kori változata

Ez a wikioldal a 2007 februárjától az alkalmazott matematikusok számára Informatika 2 (más néven SZIMP2) tárgy honlapja.

Tartalomjegyzék

Oktatók

  • Az előadásokat és a gyakorlatokat tartja Szabó Péter <pts+i@math.bme.hu>, beceneve pts.
  • A házi feladatokat és a ZH-kat javítja, a konzultációk egy részét tartja Sisak Áron <aron@math.bme.hu>.

Egyéb személyek:

Hallgatók

A gyakorlati ismeretek kellő elsajátításához elengedhetetlen, hogy a gyakorlati kurzuson mindenki saját számítógéppel dolgozzon. Az H.27-es laborban 14 munkára alkalmas gép van, amiből hallgatók számára kényelmesen használható 12 db. A biztonság kedvéért az egyik gépet hagyjuk meg tartaléknak, tehát van 11 gép, 3 gyakorlati kurzus, és összesen 33 hallgató, akiket a fentiek miatt 3 egyenlő részre kell osztani. A felosztás 2007-02-16 (pénteken) 9:10-kor, az előadás előtti 5 percben fog megtörténni. Két lehetséges megvalósuás van.

  1. A hallgatók egyeztetnek, majd összeállítanak egy nekik megfelelő felosztást, és azt írásban benyújtják a jelzett időpontban. A formai követelmények: 3 lista lesz, melyeken a tárgyat felvett hallgatók felhasználónevei vannak egyértelműen szétosztva. Minden hallgató pontosan egy listán szerepel. Minden listán minimum 11, maximum 12 felhasználónév található.
  2. Ha a fenti felosztás nem kerül benyújtásra a jelzett időpontban, akkor az előzetes gyakorlati kurzusbeosztás lép életbe (lásd lent).

Indokolt esetben utólag is lehet cserélni (2 hallgató egymás között cserél). A csere módja: a hallgatók egymással egyeztetnek, majd mindketten küldenek pts-nek és a másik hallgatónak egy e-mailt legalább 24 órával a korábbi gyakorlat előtt.

A Neptunban levő hallgatói kurzus-hozzárendelés módosításának intézésével a hallgatóknak nem kell törődniük.

Aktuális gyakorlati kurzusbeosztás (közös megegyezéssel):

  • végleges kedd 14:15-re:
    • bartazsu Barta Zsuzsanna
    • btimi Borsos Katalin
    • czirakit Cziráki Tamás
    • zsero Erő Zsolt
    • farbas Fárbás Tamás
    • kristofh Hörömpöly Kristóf
    • jgabor Janecskó Gábor
    • macsakos Mácsai Ákos
    • molnarg Molnár Gábor
    • semdan Semler Dániel
    • tbarbara Tőke Barbara
    • wlaci Winkler László
  • végleges kedd 15:15-re:
    • szape Szabó Péter
    • szbence Szűcs Benedek
    • agiesze Esze Ágnes
    • daraib Darai Borbála
    • diagy Győri Klaudia
    • dsziraki Sziráki Dorottya
    • hutivi Hutvágner Ivett
    • jocika Pinczés József
  • végleges péntek 8:15-re: (a kivéve munkanapok helyett ugyanazon héten kedd 15:15-re kell jönni)
    • csizbal Csizmadia Balázs (kivéve február 23., március 2.)
    • gszj Göbölös-Szabó Julianna (kivéve március 2., március 9.)
    • vhalasz Halász Veronika (kivéve március 9., és március 23.)
    • istvanko Kolossváry István (kivéve március 23., és március 30.)
    • rkozma Kozma Róbert Thijs (kivéve március 30., április 6.)
    • nagyal Nagy Attila (kivéve április 6., április 13.)
    • pintye Pintye Norbert (kivéve április 13., április 20.)
    • sepsir Sepsi Róbert (kivéve április 20., április 27.)
    • tuzcsaba Tűz Csaba (kivéve április 27., május 4.)
    • urbane Urbán Eszter (kivéve május 4., május 11.)
    • szabov Szabó Viktor (kivéve május 11., május 18.)
    • fukoildi Fűkő Ildikó (kivéve május 18., feburár 23.)
    • csata Csata Árpád (kivéve március 2., március 9.)
    • gubeka Gubek Andrea (kivéve március 9., március 23.)
    • kbotond Koszta Botond (kivéve március 23., és március 30.)
    • mikulan Mikulán Attila (kivéve március 30., április 6.)
    • ivajda Vajda István

Tárgykövetelmények

A szorgalmi időszakban teljesítendő:

  • A kiadott házi feladatok megoldása és beadása a SIO rendszerbe. Csak azt a feladatot kell beadni, amelynek a beadási határideje ezen a wikioldalon szerepel. Addig kell próbálkozni, amíg a rendszer OK-val el nem fogadja a megoldást. Az el nem fogadott megoldás és a meg sem kisérelt megoldás is 0 pontot ér feladatonként. Az elfogadott megoldás 1 pontot ér.
  • Az első ZH megírása. A ZH valószínűleg papíralapú lesz. Az első ZH témája: C programozási nyelv és egyszerű algoritmusok. Csak azt kell tudni, ami előadáson vagy gyakorlaton elhangzott. Puskát lehet majd használni.
  • A második ZH megírása. A ZH valószínűleg számítógéppel megoldandó lesz. A második ZH témája: Ruby programozási nyelv és objektum-orientált programozás. Csak azt kell tudni, ami előadáson vagy gyakorlaton elhangzott. Puskát lehet majd használni.

A félévközi jegy a fentieket összesítve kerül meghatározásra.

Katalógus

A gyakorlatok látogatása kötelező, minden gyakorlaton van katalógus.

Az előadások látogatása nem kötelező.

A hallgatók munkája

Előadáson a hallgatók figyelnek és jegyzetelnek. Legalább annyit leírnak, amennyi a táblára kerül.

Gyakorlaton a gyakorlat ideje alatt a hallgatók megcsinálják a kitűzött feladatot. Minden hallgatónak saját számítógépe van, amivel a feladatot megoldja. A gyakorlatvezető segít, és ellenőrzi is a megoldást. Amelyik hallgató kész van, és unatkozik, plusz feladatot kér vagy talál ki magának, és azt is megoldja. Gyakorlaton általában nem kell jegyzetelni. Füzetbe jegyzetelés helyett ajánlott tömören, de egyértelműen fájlba írni. A begépelendő kódrészleteket a hallgatók megkapják fájlban.

Gyakorlaton a hallgatók úgy ülnek le, hogy minden kezdő mellé üljön egy profi. Profinak számít az, aki az alábbiakból sokat tud: Linux grafikus felületek haladó felhasználói szintű ismerete, Linux parancssor felhasználói szintű ismerete, hatékony munka Linux parancssorban, hatékony munka Midnight Commanderben, angol nyelvtudás, jó hibadiagnosztizálási és hibajavítási készség, az órán kívül is gyakran használ Linuxot, tetszőleges programozási nyelv hobbi-szintű ismerete, tetszőleges programozási nyelv munkaerőpiacon versenyképes ismerete, ismeretlen program működésének megértése weben fellelhető információk alapján, ismeretlen program működésének megértése man page alapján, tetszőleges program telepítése Windowsra, tetszőleges program telepítése valamely Linux-disztribúcióra. A profinak nem kell ismernie se a C nyelvet, se a Ruby nyelvet.

A hallgatók otthon tanulnak, például az ajánlott irodalomból, esetleg az órai jegyzetükből. A ZH-kra való felkészülés legjobb eszköze a gyakorlás: az elmélet bebiflázása helyett sokkal eredményesebb (a ZH és a jövő szempontjából is) egy adott feladatot adott módon megoldó program elkészítése, vagy ilyen példaprogramok tanulmányozása.

A hallgatók egyénileg (pl. otthon vagy a számítógép-laborban) megcsinálják a házi feladatokat, és beküldik a SIO rendszerbe. A beküldéshez internetelérés (web) szükséges.

A hallgatók megírják a ZH-kat.

A hallgatók a félév végén beiratják a jegyet.

Ajánlott szoftverek

C nyelvhez Linux alatt ajánlott:

  • sima szövegszerkesztő: kate
  • fordítóprogram: gcc
  • fejlesztőkörnyezet: Kdevelop
  • egyéb segédprogramok: strace, valgrind

C nyelvhez Windows alatt ajánlott:

Ruby nyelvhez Linux alatt ajánlott:

Ruby nyelvhez Windows alatt ajánlott:

Erő Zsolt egy Live CD-t készít, amin a fenti linuxos szoftverek megtalálhatók, és hosszadalmas telepítés nélkül kipróbálhatók.

Tananyag

  • algoritmusok C nyelven
  • objektum-orientált programozás Ruby nyelven

Ajánlott irodalom:

Konvenciók

A konvenciók mind a hallgatók, mind az oktatók számára kötelezően betartandók.

  • A tárggyal kapcsolatos fájlokat mindenki a ~/szimp2 mappába helyezze.
  • Minden fájlnév és mappanév kisbetűs.
  • A fájlnevek ékezetes betűket nem tartalmaznak.
  • A forrásfájlok (*.c és *.rb) ékezetes betűket nem tartalmaznak.
  • Minden program forráskódja külön (*.c vagy *.rb) fájlba kerül. Tehát nem írunk felül egyetlen korábban létrehozott fájlt sem, hanem lemásoljuk a fájlt, és más néven mentjük el. A más néven mentés még a fájl tartalmának módosítása előtt történik.
  • A sor elején levő szóközök számának megállapításánál betartjuk a beljebb kezdési szabályt (C nyelvhez lásd az 1. gyakorlat anyagában).

A gcc-parancssor elemeinek jelentése

Ezt nem kell tudni, csak egy hallgató kérésére, érdekességképp került fel a wikibe. Az alábbi parancsot elemezzük:

$ gcc -W -Wall -s -O2 -lm -o <program> <program>.c
  • gcc: a fordítóprogram neve. A GNU C Compiler és egyben a GNU Compiler Collection rövidítése. Házi feladat a Wikipédián utánanézni, mi az a GNU.
  • -Wall: a legfontosabb figyelmeztető üzeneteket (warning) bekapcsolja
  • -W: még néhány fontos figyelmeztető üzenetet bekapcsol
  • -s: a fölösleges részeket (pl. nyomkövetési információk és szimbólumok) eltávolítja kimenetből. Nélküle nagyobb lenne a kimenet.
  • -O2: bekapcsolja a második szintű optimalizálást. A harmadik szintű azért rossz, mert a kód lassan fordul, és túl nagy lesz. Az első szintű azért rossz, mert a kód túl lassú lesz, és esetleg túl nagy is. Vannak egyéb szintek is, például alapból a nulladik szint érvényes. Nem nulla, hanem nagy O betű van a kapcsolóban.
  • -lm: a matematikai függvényeket (pl. sqrt és cos) tartalmazó matematikai függvénykönyvtárat teszi elérhetőve. Emellett a forráskódban szerepelnie kell még az #include <math.h>-nak is a matematikai függvényekhez. Nem egyes, hanem kis l betű van a kapcsolóban.
  • -o <program>: a kimeneti futtatható fájl nevét adja meg
  • <program.c>: bemeneti forrásfájl nevét adja meg

Kismillió egyéb fordítási opciója is van még a gcc-nek (lásd még man gcc és info gcc), ezek a tárgy elvégzése szempontjából nem érdekesek.

1. gyakorlat (2007-02-13 és 2007-02-16)

A gyakorlat célja, hogy a C nyelvű programozáshoz használandó eszközökkel megismerkedjünk. A bemutatott eszközök: kate, gcc, terminálablak. A gyakorlatnak nem célja megtanítani, hogy a program (pl. hello100.c) hogyan működik, miért azt csinálja, amit csinál, ezt majd előadáson tanuljuk meg.

Az szimp2 mappát és a tartalmát csupa kisbetűvel kell létrehozni, vagy ha nagybetűs lett, akkor át kell nevezni kisbetűre.

A Kate nevű szövegszerkesztőt használjuk.

~/szimp2/hello.c:

#include <stdio.h>
int main(void) {
  printf("Hello, World!\n");
  return 0;
}

A sor elején levő szóközök (ún indentation) nem a gép számára, hanem a programot olvasó ember számára hasznosak.

Hasznos parancsok (csak a $ utáni részt kell begépelni, a többit a gép írja ki).

$ mkdir ~/szimp2
$ cd ~/szimp2
$ kate hello.c
$ gcc -W -Wall -s -O2 -o hello hello.c
$ ./hello
Hello, World!

Windows alatt a kipróbálás úgy történik, hogy Dev-C++-ban lefordítjuk, majd kézzel futtatjuk. A futtatáshoz tehát nem a Dev-C++ Run menüpontját választjuk (mert az a futás befejeztével eltünteti az ablakot), hanem kézzel nyitunk egy parancssor-ablakot, a megfelelő cd paranccsal belépünk a megfelelő mappába, majd ott dir paranccsal megnézzünk, milyen .exe fájlok vannak (pl. hello.exe), és azok egyikét futtatjuk (pl. hello paranccsal).

~/szimp2/hello100.c:

#include <stdio.h>
int main(void) {
  int c;
  for (c=0;c<100;c++) {
    printf("Hello, World!\n");
  }
  return 0;
}

A sor elején levő szóközök számára vonatkozó beljebb kezdési szabály (sokféle változata lehetséges, itt csak a tárgy keretében használatosat értelmezzük):

  • Beljebb kezdésre csak szóközöket használunk, tabulátort nem.
  • A záró kapcsos zárójel sosem kerül egy sor végére, hanem előtte mindig soremelés van. A soremelés és a záró kapcsos zárójel közé pontosan annyi szóköz kerül, ahány szóköz volt a hozzá tartozó nyitó kapcsos zárójelet tartalmazó sor elején.
  • Minden egyéb sor elején pontosan kétszer annyi szóköz van, ahány (bezáratlan) kapcsos zárójelen belül van az adott sor.

A beljebb kezdéshez hasznos tippek:

  • A Kate (főleg Enter leütésekor) hajlamos a sor elején 8 egymás utáni szóközöt 1 db tabulátorra cserélni. Ez nekünk nem kívánatos, úgyhogy beszéljük le róla: ikszeljük be a File / Configure Kate / Editor / Indentation / Use spaces instead of tabs to indent jelölőnégyzetet.
  • Egyes fejlesztőkörnyezetnek van Smart indent opciója. Ezt kapcsoljuk át Autoindentre. Sajnos Dev-C++-ban csak Smart indent van. A Smart indent azt csinálja, hogy a soreleji szóközöket igyekszik kváziintelligensen magától meghatározni, pl. ha a sor elején beírunk egy záró kapcsot, magától csökkenti a soreleji szóközök számát. Néha jól, néha rosszul. Inkább kapcsoljuk ki, mint hogy figyelnünk kelljen a hibázásaira, és folyamatosan küzdenünk kelljen vele.

Hasznos parancsok:

$ cd ~/szimp2
$ kate hello100.c
$ gcc -W -Wall -s -O2 -o hello100 hello100.c
$ ./hello100
Hello, World!
...
Hello, World!
$ ./hello100 | wc -l
100
$ ./hello100 >hello100.out
$ kate hello100.out
$ ./negyzet100 | more
$ ./negyzet100 | less

~/szimp2/negyzet100.c:

#include <stdio.h>
int main(void) {
  int c;
  for (c=0;c<=100;c++) {
    printf("szam: %3d, negyzete: %5d\n", c, c*c);
  }
  return 0;
}

~/szimp2/kettohatvany100.c:

#include <stdio.h>
int main(void) {
  int c;
  for (c=0;c<=100;c++) {
    printf("szam: %3d, kettohatvany: %d\n", c, 1<<c);
  }
  return 0;
}

Az a<<b művelet a-t megszorozza 2 a b-edikennel, és visszaadja az eredményt. Hasonlóa az a>>b, de ő szorzás helyett oszt (a 0 felé kerekítve).

Figyeljük meg, hogy 1<<31 már negatív, és 1<<32 == 1. Ezek a túlcsordulás miatt vannak.

1. előadás (2007-02-16)

Megtanultuk:

  • bemenet
  • kimenet
  • processzor
  • memória
  • program
  • bájt: 1 bájt == 8 bit; 0..255
  • folyamatábra
  • *
  • +
  • <<
  • < <= == > >=
  •  !=
  • a=b=0
  • if
  • for
  • while
  • goto
  • printf-ből a %d és a \n
  • getchar: while (0<=(c=getchar()))
  • putchar
  • else: csak érintettük. Példa: if (a<0) b=-1; else b=1;

~/szimp2/bajtszamlalo.c:

/* Megszámolja és kiírja, hogy a bemenet hány bájtból áll.
 * `n=n+1' helyett `n++'-ot írtunk.
 */
#include <stdio.h>
int main(void) {
  int n=0;
  while (0<=getchar()) n++;
  printf("%d\n", n);
  return 0;
}

Kipróbálás:

$ echo sok | ./bajtszamlalo
4
$ echo -n sok | ./bajtszamlalo
3

~/szimp2/sorszamlalo.c:

/* Megszámolja és kiírja, hogy a bemenet hány sorból áll.
 * Az utolsó sor nem számít, ha nincs a végén soremelés.
 */
#include <stdio.h>
int main(void) {
  int c, n=0;
  while (0<=(c=getchar())) {
    if (c=='\n') n++;
  }
  printf("%d\n", n);
  return 0;
}

Kipróbálás:

 $ ls /bin/bash /usr/bin/id /dev/null /etc/inputrc | ./sorszamlalo
 4

2. gyakorlat (2007-02-20)

A gyakorlat megkezdése előtt ezt az útmutatót mindenki figyelmesen olvassa el, a gyakorlaton pedig figyelmesen kövesse. A figyelmes követésnek része, hogy a bemásolandókat pontosan másoljuk be, a fájlnevet pontosan úgy adjuk meg, ahogy le van írva, minden karakter számít (tehát nem inputrc, hanem ~/.inputrc).

Ugyanazt a parancsot sosem írjuk be kétszer, hanem a korábbi beírást hasznosítjuk újra.

A PageUp-pal és PageDown-nal történő history-kereséshez az ~/.inputrc fájlukba írjuk bele:

set meta-flag on
set input-meta on
set convert-meta off
set output-meta on
"\e[5~": history-search-backward
"\e[6~": history-search-forward

Ezután vagy nyissunk új terminálablakot, vagy adjuk ki:

$ bind -f ~/.inputrc

Az aktuális terminálablakban használhatjuk a history parancsot, egy már becsukott terminálablak esetén pedig a ~/.bash_history fájlt. Érdemes e fájlból a legfontosabb parancsokat másik fájlba írni, mert a bash a régi bejegyzéseket eldobja. A limit megnövelhető, ha a ~/.bashrc-nkbe elhelyezzük az alábbi sort:

export HISTSIZE=9999    

Ha egy programnak többször akarjuk ugyanazt a bemenetet adni, akkor a bemenetet írjuk be fájlba (pl. prog.in), és irányítsuk át. Ennek segítségével könnyen ellenőrizhető, hogy a program két változata (prog1 és prog2) ugyanazt a kimenetet produkálja-e:

$ ./prog1 <prog.in >prog1.out
$ ./prog2 <prog.in >prog2.out
$ diff prog1.out prog2.out

A diff program kimenetét kell figyelni.

Ha a program bemenetét UNIX-on a terminálon gépeljük be, akkor az alábbiakra figyeljünk:

  • Egy egész sort be kell írni (és Enter-rel lezárni), és a program csak ezután kapja meg az egész sort.
  • A sorvégi Enter-t a program '\n'-ként kapja.
  • A bemenet végét (EOF, -1) Enter, majd Ctrl-D lenyomásával jelezhetjük. Ezután a program következő getchar() hívása -1-et ad vissza, a scanf() pedig (általában) nullát.
  • Windows alatt Ctrl-D helyett Enter, Ctrl-Z, Enter.
  • Ha Ctrl-C-t nyomunk, az örökre megszakítja a program futását, tehát ha a program kilépés előtt még kiírt volna valamit, akkor azt már nem fogja kiírni.

Számkitalálós program (embergondol.c: ember gondol, gép talál ki):

#include <stdio.h>
int main(void) {
  int a=1, b=100, f, c;
  printf("Gondolj egy szamot %d es %d kozott (zart)!\n", a, b);
  while (a!=b) {
    f=(a+b)/2;
    printf("Nagyobb, mint %d?\n", f);
    while ((c=getchar())=='\n') {}
    if (c=='i') a=f+1;
    else if (c=='n') b=f;
  }
  return 0;
}

A program találja ki a gondolt számot. Az ember i-vel vagy n-nel válaszol pl. arra a kérdésre, hogy A gondolt szám nagyobb, mint 50?. Az ember válaszát getchar()-ral kel beolvasni.

Az alábbira már nem jutott kedden idő, pedig jóval egyszerűbb, mint az embergondol.

Számkitalálós program (gepgondol.c: gep gondol, ember talál ki):

#include <stdio.h>
#include <math.h>
#include <time.h>
int main(void) {
  int a=1, b=100;
  int gondolt, tipp;
  srand(time());
  gondolt=rand()%(b-a)+a;
  printf("Gondoltam egy szamot %d es %d kozott (zart), talald ki!\n", a, b);
  while (1) {
    printf("Mit tippelsz?\n");
    scanf("%d",&tipp);
    if (gondolt>tipp) {
      printf("A gondolt szam nagyobb, mint %d\n", tipp);
    } else {
      printf("A gondolt szam nem nagyobb, mint %d\n", tipp);
    }
  }
  return 0;
}

2. előadás (2007-02-23)

Megtanultuk:

  • egydimenziós tömbök definiálása és deklarálása
  • [0..(n-1)] indexeljük az n elemű tömböt
    • tömbelem hozzáférése nagyon gyors (konstans időben történik)
    • nagy félrecímzés általában gyors és feltűnő, kicsi félrecímzés alattomos és nehezen felderíthető hibához vezet
    • gyakorlaton lesz még szó ezek felderítéséről
  • több (pl. kettő) dimenziós tömbök definiálása és deklarálása
  • tömbelemek inicializálása (for) ciklussal, pl. angol abc, mátrix kinullázása
  • hogyan lehet beszúró rendezéssel egy tömböt rendezni
    • költsége O(n2), viszont nincs járulékos tárhely igénye
    • működik láncolt listákra is
      • az elemhozzáférés tömbnél konstans, listánál O(n) időigényű
      • az elem beszúrása listánál O(1), tömbnél O(n) időigényű
    • #define MAX 0x100 után a fordító MAX-ot 0x100-ra fogja mindig kicserélni
    • az algoritmus működéséről egy szép animáció: http://www.cs.bme.hu/~gsala/alg_anims/3/isort-e.html
  • hogyan lehet mátrixot transzponálni
  • a "%6d" formázó sztringgel a printf a 6-nál nem több számjegyű számokat „szépen”, jobbra igazítva fogja kiírni
  • a 0x100 az hexadecimális, azaz 16-os számrendszerben vett 100, tehát 256

~/szimp2/beszurorendezes.c:

/* A bemenetről beolvasott számokat beszúró rendezéssel rendezi,
 * majd kiírja a kimenetre.
 */
#include <stdio.h>
#define MAX 0x10
int main(void) {
  int tomb[MAX], elem, i, j; 
  for(i = 0; i != MAX; i++)
    scanf("%d", &tomb[i]);
  for (i = 1; i < MAX; i++) {
    elem = tomb[i];
    j = i-1;
    while (j >= 0 && tomb[j] > x) {
      tomb[j+1] = tomb[j];
      j--;
    }
    tomb[j+1] = elem;
  }
  for(i = 0; i != MAX; i++)
    printf("%d \n", tomb[i]);
  return 0;
}

Kipróbálás:

$ ./beszurorendezes > rendezett # és beírunk 16 álvéletlen számot
86 36 16 58 2 64 40 7 14 31 50 96 54 18 76 61 
$ sort -n | diff rendezett -    # és beírjuk pontosan ugyanazokat a számokat
86 36 16 58 2 64 40 7 14 31 50 96 54 18 76 61 
# és itt semmit sem szabad kiírnia, hiszen nincs eltérés a Unixos és az
# általunk írt rendezés eredménye között

~/szimp2/matrixtranszponalas.c:

#include <stdio.h>
int main(void) {
  int a[10][6], b[6][10], n, m;

  for (n=0; n < 10; n++) {
    printf("Ird be a(z) %d. sort (6 db számot):\n", n+1);
    for(m=0; m < 6; m++) {
      scanf("%d", &a[n][m]);
    }
  }

  for (n=0; n < 10; n++) 
    for(m=0; m < 6; m++)
      b[m][n] = a[n][m];

  for (n=0; n < 6; n++) {
    for(m=0; m < 10; m++) {
      // persze kiirhatnank a[m][n]-et is, es akkor nem is kell transzponalni
      printf("%6d ", b[n][m]);
    }
    printf("\n");
  }
  return 0;
}

Ez nem volt előadáson, de érdekes:

~/szimp2/matrixtranszponalas_helyben.c:

#include <stdio.h>
int main(void) {
  int a[6][6], c;
  unsigned n, m;
  for (n=0; n < 6; n++) {
    printf("Ird be a(z) %d. sort (6 db számot):\n", n+1);
    for (m=0; m < 6; m++) {
      scanf("%d", &a[n][m]);
    }
  }
  for (n=0; n < 6; n++) {
    for (m=n+1; m < 6; m++) {
      c=a[n][m]; a[n][m]=a[m][n]; a[m][n]=c;
    }
  }
      
  for (n=0; n < 6; n++) {
    for (m=0; m < 6; m++) {
      printf("%6d ", a[n][m]);
    }
    printf("\n");
  }
  return 0;
}

3. gyakorlat (2007-02-27, 2007-03-02)

A feladat az egymilliónál kisebb prímszámok kiírása volt Eratoszthenészi szita segítségével, ~/szimp2/erszita1.c néven.

~/szimp2/erszita1.c:

/* Esze Ágnes megoldása alapján */
#include <stdio.h>
int main (void) {
  int i,j;
  char tomb[1000000];
  for(i=2;i<1000000;i++) {
    tomb[i]=0;
  }
  for(i=2;i<1000000;i++) {
    if (tomb[i]!=1){
      printf("%d\n", i);
      for (j=2*i; j<1000000; j+=i) {
        tomb[j]=1;
      }
    }
  }
  return 0;
}

Kipróbálás:

$ cd ~/szimp2
$ gcc -W -Wall -s -O2 -o erszita1 erszita1.c
$ ./erszita1 | wc  -l
78498
$ ./erszita1 | head -5
2
3
5
7
11
$ ./erszita1 | tail -5
999953
999959
999961
999979
999983

Ezután javítani kellett a program sebességén úgy, hogy az 1000 fölötti prímek többszöröseit ne húzza ki (tehát nincs tomb[p]=1), mert azokat már az 1000 alatti prímek többszöröseként már kihúzta. Ehhez az alábbi módosítások voltak szükségesek:

  • Ha a talált prím p, akkor csak p*p-től 999999-ig kell kihúzni a többszörösöket.
  • Amikor p*p először nő 999999 fölé, kilépünk a for-ciklusból, és egy második for-ciklisban kiírjuk az 1000 fölötti prímeket.

~/szimp2/erszita2.c:

/* Esze Ágnes megoldása alapján */
#include <stdio.h>
int main (void) {
  int i,j;
  char tomb[1000000];
  for(i=2;i<1000000;i++) {
    tomb[i]=0;
  }
  for(i=2;i<1000000;i++) {
    if (i*i>=1000000)
      goto hoppa;
    if (tomb[i]!=1){
      printf("%d\n", i);
      for (j=i*i; j<1000000; j+=i) {
        tomb[j]=1;
      }
    }
  }
 hoppa:
  for(;i<1000000;i++) {
    if (tomb[i]!=1)
      printf("%d\n", i);
  }
  return 0;
}

Kipróbálás ugyanúgy, mint erszita1 esetén, de erszita1 helyett erszita2-vel.

Harmadik, szorgalmi feladatként azt kellett megoldani, hogy a páros számokkal nem is foglalkozunk (kivéve a 2-t), a páros indexeket a tömbből is kihagyjuk. Tehát például a p=13-nak megfelelő hely a tomb[6], a p=17-nek megfelelő hely pedig a tomb[8].

Ehhez tomb[valami] helyett elég tomb[valami/2]-t kell írni, és kettesével kell ugrálni.

~/szimp2/erszita3.c

/* Esze Ágnes megoldásából indulva */
#include <stdio.h>
int main (void) {
  int i,j;
  char tomb[500000];
  for(i=0;i<500000;i++) {
    tomb[i]=0;
  }
  printf("2\n");
  for(i=2;i<1000000;i+=2) {
    if (i*i>=1000000)
      goto hoppa;
    if (tomb[i/2]!=1){
      printf("%d\n", i);
      for (j=i*i; j<1000000; j+=i) {
        tomb[j/2]=1;
      }
    }
  }
 hoppa:
  for(;i<1000000;i+=2) {
    if (tomb[i/2]!=1)
      printf("%d\n", i);
  }
  return 0;
}

Érdemes egymás mellett összevetni az erszita2.c-t és az erszita3.c-t.

3. előadás (2007-03-02)

A függvényekről és a rekurzióról volt szó. Ezeket a fogalmakat vettük:

  • függvény
  • visszatérési érték
  • paraméter
  • lokális változó
  • érték szerinti paraméterátadás
  • cím szerinti paraméterátadás
  • mellékhatás
  • rekurzió

Az alábbi megoldás nem jól cserél, mert érték szerint veszi át a-t és b-t, tehát a hívás pillanatában lemásolja, és csak a másolatot cseréli, noha az eredetit kéne:

void rosszcsere(int a, int b) {
  int abak=a;
  a=b;
  b=abak;
}
int main(void) {
  int x=5, y=6;
  printf("csere elott x=%d, y=%d\n", x, y); /* 5, 6 */
  rosszcsere(&x, &y);
  printf("csere utan  x=%d, y=%d\n", x, y); /* 5, 6 -- rossz */
  return 0;
}

Példa cím szerinti paraméterátadásra (~/szimp2/csere.c; ez már jó, és szerepelt is a táblán):

void csere(int *a, int *b) {
  int abak=*a;
  *a=*b;
  *b=abak;
}
int main(void) {
  int x=5, y=6;
  printf("csere elott x=%d, y=%d\n", x, y);
  csere(&x, &y);
  printf("csere utan  x=%d, y=%d\n", x, y);
  return 0;
}

Példa a hatványozás rekurzív számolására (~/szimp2/pow.c):

/** Visszadja a az alap**kitevo hatványozás eredményét.
 * Csak akkor működik helyesen, ha kitevo>=0.
 * pow(0,0)==1
 */
int pow(int alap, int kitevo) {
  if (kitevo<=0) return 1;
  return alap*pow(alap, kitevo-1);
}

Példa moduláris hatványozás rekurzív számolására (~/szimp2/powmod.c):

/** Visszadja a az alap**kitevo hatványozás eredményének modulo modulus vett
 * maradékát.
 * Csak akkor működik helyesen, ha alap>=0 és kitevo>=0 és modulus>=2.
 * powmod(0,0,modulus)==1
 */
int powmod(int alap, int kitevo, int modulus) {
  if (kitevo<=0) return 1;
  return ((alap%modulus)*pow(alap, kitevo-1, modulus))%modulus;
}

Példa moduláris hatványozás rekurzív számolására az előzőnnél gyorsabban (~/szimp2/powmod2.c):

/** Visszadja a az alap**kitevo hatványozás eredményének modulo modulus vett
 * maradékát.
 * Csak akkor működik helyesen, ha alap>=0 és kitevo>=0 és modulus>=2.
 * powmod2(0,0,modulus)==1
 */
int powmod2(int alap, int kitevo, int modulus) {
  int ret;
  if (kitevo<=0) return 1;
  alap%=modulus;
  ret=powmod2(alap, kitevo/2, modulus);
  if (ret!=0) {
    ret=(ret*ret)%modulus;
    if (kitevo%2!=0) ret=(alap*ret)%modulus;
  }
  return ret;
}

A fenti powmod2 például 5 a 11-edikent modulo 10 így számolja ki:

o=5 % 10;
p=o*o % 10;
q=5*p*p % 10;
r=5*q*q % 10;
return r;

Csemegeként (nem kerül számonkérésre) következzen a powmod2 olyan változata, ami a lokális változók értékét nem módosítja (~/szimp2/powmod3.c):

/** Visszadja a az alap**kitevo hatványozás eredményének modulo modulus vett
 * maradékát.
 * Csak akkor működik helyesen, ha alap>=0 és kitevo>=0 és modulus>=2.
 * powmod2(0,0,modulus)==1
 */
int powmod3(int alap, int kitevo, int modulus) {
  int ret;
  if (kitevo<=0) return 1;
  return powmod3b(alap%modulus, kitevo, modulus);
}
/** Csak akkor működik helyesen, ha alap>=0 és alap<modulus és modulus>=2 és
 * kitevo>=0.
 */
int powmod3b(int alap, int kitevo, int modulus) {
  return powmod3c(alap, kitevo, modulus, powmod3b(alap, kitevo/2, modulus));
}
/** Csak akkor működik helyesen, ha alap>=0 és alap<modulus és modulus>=2 és
 * kitevo>=0.
 */
int powmod3c(int alap, int kitevo, int modulus, int fele) {
  if (fele==0) return 0;
  return powmod3d(alap, kitvo, modulus, (fele*fele)%modulus);
}
/** Csak akkor működik helyesen, ha alap>=0 és alap<modulus és modulus>=2 és
 * kitevo>=0.
 */
int powmod3d(int alap, int kitevo, int modulus, int felnegyzet) {
  if (kitevo%2==0) return felnegyzet;
  return (alap*felnegyzet)%modulus;
}

Megjegyzés: a powmod3 függvény Cékla nyelven is működik. A Cékla nyelvet majd a Deklaratív programozás tárgy keretében fogjuk tanulni.

Példa a faktoriális rekurzív számolására (~/szimp2/fakt.c):

int fakt(int n) {
  if (n<2) return 1;
  return n*fakt(n-1);
}

Példa a faktoriális rekurzív számolására akkumulátorral és jobbrekurzióval (~/szimp2/fakt2.c; nem kell érteni, hogy miért jobb a fakt2, mint a fakt):

int fakt2(int n) {
  return fakt2b(n, 1);
}
/** n!*szorzo -t adja vissza. */
int fakt2b(int n, int szorzo) {
  if (n<2) return szorzo;
  return fakt2b(n-1, szorzo*n);
}

Példa a Fibonacci-sorozat rekurzív számolására (~/szimp2/fib.c; ez szerepelt is a táblán előadáson):

int fib(int n) {
  if (n<2) return n;
  return fib(n-1)+fib(n-2);
}

Miért olyan lassú fib(1000)-t kiszámolni? Azért, mert fib(1000)-hez pl. fib(1)-et és fib(2)-t rengetegszer kell kiszámolni, noha elég lenne egyszer is. Ilyenkor az iteratív (értsd: for-ciklusos) megoldás jóval gyorsabb:

Példa a Fibonacci-sorozat iteratív számolására (~/szimp2/fib2.c; ez is szerepelt a táblán):

int fib(int n) {
  int a, b, regib;
  if (n<2) return n;
  a=0; b=1;
  while (n>1) {
    regib=b; b+=a; a=regib;
    n--;
  }
  return b;
}

Példa a legrövidebb közös részstring hosszának rekurzív meghatározására (~/szimp2/lkrh.c). Ezt még nem kell érteni.

int max(int a, int b) {
  return a>b ? a : b;
}
int lkrh(char *s, char *t) {
  if (*s=='\0') return 0; /* ha az s üres, akkor lkrh==0 */
  if (*s=='\0') return 0; /* ha a  t üres, akkor lkrh==0 */
  if (*s==*t) { /* az első karakter azonos */
    return 1+lkrh(s+1, t+1);
  } else {
    return max(lkrh(s+1, t), lkrh(s, t+1));
  }
}

A fenti lkrh függvény túl lassú, mert rekurzív hívásakor ugyanarra az s--t párra többször is meghívódik (és tovább hívja magát rekurzívan). Jó lenne az első hívás után letárolni az eredményt.

4. gyakorlat (2007-03-06, 2007-03-09)

Ezen a gyakorlaton a függvények használatát gyakorljuk:

  • a kód egyszerűsítése az ismétlődő feladatok függvénybe rakásával
  • érték szerinti paraméterátadás
  • rekurzió
  • érték módosítása cím szerinti paraméterátadással
  • több érték visszadása cím szerinti paraméterátadással

Törtszámösszeadó programot fogunk írni. Minden tört egy egész értékű számálálóból és egy nem nulla egész értékű nevezőből áll. A tört értéke a számláló és a nevező hányadosa. Egy tört egyszerűsítve van, ha a nevezője pozitív, és a számláló és a nevező legnagyobb közös osztója 1. Két tört összeadása úgy történik, hogy először egyszerűsítjük őket (külön-külön); majd képezzük a két nevező legkisebb közös többszörösét; bővítjük mindkét törtét úgy, hogy a közös nevezőjük a legkisebb közös többszörös legyen; a bővített számlálókat összeadjuk; az eredményt egyszerűsítjük.

A törtszámösszeadó program a bemenetről beolvas négy egész számot: as, an, bs, bn, majd kiszámolja az as/an' és bs/bn törtek összegét, és perjellel elválasztva kiírja az eredmény számlálóját (es) és nevezőjét (en) egy sorba. Ezután a következő feladványsor beolvasásásval folytatja.

Példa bemenet (~/szimp2/tortad1.in):

1 2 3 4
3 4 5 -6
3 4 -5 6
-3 4 5 6
3 6 30 20

Példa kimenet (~/szimp2/tortad1.exp):

5/4
-1/12
-1/12
1/12
2/1

A megírandó program vázlata (~/szimp2/tortad.c):

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

/** Az a és b pozitív egész számok legnagyobb közös osztóját adja vissza.
 * Tilos negatív számmal hívni.
 */
int lnko(int a, int b) {
  if (a<0 || b<0) abort();
  ... /* Euklideszi algoritmus: ha a==0, akkor b, egyébként ... rekurzió */
}

/** Az a és b pozitív egész számok legkisebb közös többszörösét adja vissza.
 * Tilos 0-val vagy negatív számmal hívni.
 */
int lkkt(int a, int b) {
  if (a<1 || b<1) abort();
  ... /* használjuk az lnko()-t */
}

/** Az s/n törtet egyszerűsíti. A negatívságot felviszi a számlálóba, és
 * mindkét számot leosztja a legnagyobb közös osztójukkal. Nulla nevezővel
 * tilos meghívni.
 */
void egyszerusit(int *s, int *n) {
  if (*n==0) abort();
  ...
}

/** Az as/an törthöz hozzáadja a bs/bn törtet, és az eredményt az es/en
 * törtben adja vissza.
 */
void osszead(int as, int an, int bs, int bn, int *es, int *en) {
  ... /* egyszerűsít, közös nevezőre hoz, összead, egyszerűsít */
}

int main(void) {
  int as, an, bs, bn, es, en;
  while (4==scanf("%d%d%d%d", &as, &an, &bs, &bn)) {
    ... /* az osszead() függvényt kell megfelelő paraméterekkel meghívni */
    ... printf("%d\n", es); /* en-t is ki kell még írni egy perjel után */
  }
  return 0;
}

A kész program (~/szimp2/tortad.c):

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

/** Az a és b pozitív egész számok legnagyobb közös osztóját adja vissza.
 * Tilos negatív számmal hívni.
 */
int lnko(int a, int b) {
  if (a<0 || b<0) abort();
  if (a==0) return b;
  return lnko(b%a, a);
}

/** Az a és b pozitív egész számok legkisebb közös többszörösét adja vissza.
 * Tilos 0-val vagy negatív számmal hívni.
 */
int lkkt(int a, int b) {
  if (a<1 || b<1) abort();
  return a/lnko(a,b)*b;
  /* ^^^ először osztunk, utána szorzunk, hogy ne legyen túlcsordulás */
}

/** Az s/n törtet egyszerűsíti. A negatívságot felviszi a számlálóba, és
 * mindkét számot leosztja a legnagyobb közös osztójukkal. Nulla nevezővel
 * tilos meghívni.
 */
void egyszerusit(int *s, int *n) {
  int c;
  if (*n==0) abort();
  if (*n<0) {
    *n=-*n;
    *s=-*s;
  }
  if (*s<0) {
    c=lnko(-*s,*n);
  } else {
    c=lnko(*s,*n);
  }
  /* a c-t jobb előre kiszámolni, mert ha lent c helyére lkno(*s,*n) kerülne,
   * akkor a második lnko(*s,*n) már a módosított s-sel számolna, ami nem jó
   */
  *s/=c;
  *n/=c;
  /* nincs return, mert void a visszatérési érték */
}

/** Az as/an törthöz hozzáadja a bs/bn törtet, és az eredményt az es/en
 * törtben adja vissza.
 */
void osszead(int as, int an, int bs, int bn, int *es, int *en) {
  egyszerusit(&as,&an);
  egyszerusit(&bs,&bn);
  *en=lkkt(an,bn);
  *es=(*en/an)*as+(*en/bn)*bs;
  egyszerusit(&*es,&*en);
  /* ^^^ az & az egyszerusit() deklarációjában levő * miatt kell */
  /* ^^^ a  * az osszead()     deklarációjában levő * miatt kell */
  /* ^^^ megjegyzés: &* kihagyható, csak didaktikai okokból van bent */
}

int main(void) {
  int as, an, bs, bn, es, en;
  while (4==scanf("%d%d%d%d", &as, &an, &bs, &bn)) {
    osszead(as, an, bs, bn, &es, &en);
    printf("%d/%d\n", es, en);
  }
  return 0;
}

A kipróbálás előtt készítsük el a mintabemenetet (~/szimp2/tortad1.in) és a mintakimenetet (~/szimp2/tortad1.exp), lásd fent. Ezután kipróbálható:

$ cd ~/szim2p
$ gcc -W -Wall -s -O2 -o tortad tortad.c
$ ./tortad <tortad1.in
5/4
-1/12
-1/12
1/12
2/1
$ ./tortad <tortad1.in >tortad1.out
$ diff tortad1.exp tortad1.out
$ _

4. előadás (2007-03-09)

Vettük a bináris fa definícióját, az alábbi fogalmakkal:

  • csúcs
  • él
  • gyerek
  • szülő
  • bináris fa (ha minden csúcsnak 0, 1 vagy 2 gyereke van)
  • gyökér
  • belső csúcs (akinek van gyereke -- akár a gyökér is lehet belső csúcs)
  • levél (akinek nincs gyereke -- akár a gyökér is lehet levél)
  • bal részfa
  • jobb részfa

Vettük a bináris keresőfát. A bináris keresőfa olyan bináris fa, melynek minden csúcsában egy érték szerepel, és minden csúcsára igaz, hogy a bal részfában szereplő értékek mind legfeljebb akkorák, mint a csúcsban szereplő érték, és a jobb részfában szereplő értékek mind legalább akkorák, mint a csúcsban szereplő érték. Néha kikötik, hogy egy érték csak egyszer szerepelhet (ez egyszerűsíti a bináris fában végzett műveleteket).

Példa bináris keresőfára (az órán is ez volt a táblán):

      0
     / \
    /   \
   -5    3
  / \     \
-10  -5    42
    / \
   -5  -2

Alapműveletek bináris keresőfákkal:

  • keresés
  • új érték beszúrása
  • érték törlése

Egyéb művelet bináris keresőfákkal:

  • kiegyensúlyozás: a fa átalakítása a benne levő értékek megtartásával úgy, hogy a magassága (jóval) kisebb legyen.

Példa kiegyensúlyozásra:

  1
 / \
0   2                          3
     \                        / \
      3                      /   \
       \            -->     /     \
        4                  1       5
         \                / \     / \
          5              0   2   4   6
           \
            6

Kiegyensúlyozott fa (ez egy nem túl precíz fogalom): olyan bináris fa, amelynek minden csúcsára igaz, hogy a bal részfában nagyjából ugyanannyi csúcs van, mint a jobb részfában.

Részfa magassága: a részfa gyökerétől egyik leveléig menő leghosszabb úton levő csúcsok száma. (A definícióból következik, hogy egy levél magassága 1.)

AVL-fa (precíz fogalom, a kiegyensúlyozott fák egy fajtája): olyan bináris fa, melynek minden csúcsára igaz, hogy a bal részfa magassága és a jobb részfa magassága közti különbség -1, 0 vagy +1.

Keresés bináris keresőfában: A feladat az, hogy keressünk egy olyan csúcsot a fában, ahol az adott érték szerepel. Ha több ilyen csúcs is van, akkor bármelyik jó.

A bináris fában való keresés (rekurzív) algoritmusa:

  1. A gyökértől indulunk.
  2. Ha az aktuális csúcsban a kívánt érték szerepel, készen vagyunk.
  3. Ha a bal részfa nem üres, és az aktuális csúcsban a kívánt értéknél nagyobb érték szerepel, a bal részfa gyökerével folytatjuk (a 2. lépéstől).
  4. Ha a jobb részfa nem üres, és az aktuális csúcsban a kívánt értéknél kisebb érték szerepel, a jobb részfa gyökerével folytatjuk (a 2. lépéstől).
  5. A keresést befejezzük, az adott érték nem található meg a fában.

Beszúrás bináris keresőfába: A feladat az, hogy szúrjunk be a fába egy új értéket úgy, hogy az továbbra is bináris keresőfa maradjon.

Látható, hogy a keresés legfeljebb annyi lépésből áll, amennyi a fa magassága. AVL-fánál (és sok egyéb kiegyensúlyozott fánál is) egy n csúcsot tartalmazó fa magassága O(log n), tehát a keresés gyors. Szélsőséges esetben, például ha a fa csúcsainak csak jobboldali gyerekük van, az egész fát be kellhet járni (O(n)).

C nyelvben a bináris fák kezeléséhez struktúrákat használunk. A kapcsolódó fogalmak:

  • struktúra (struct)
  • mező
  • struktúra mérete
  • mező kezdőcíme a struktúrában
  • bájtra igazítás (alignment)

PC (i386, x86) architektúrán az igazítások:

  • char esetén 1
  • short esetén 2
  • minden más (pl. int, long, float, double, struktúra és mutató) esetben 4

Példa struktúra definiálására:

struct pelda {
  int a, b;
  char c;
  double d;
};

A példa struktúra mérete igazítás nélkül 4+4+1+8 bájt lenne, igazítással viszont 4+4+1+3+8 bájt, mivel a double típusú változónak 4-gyel osztható címen kell kezdődnie, így 4+4+1 helyett a 4+4+1+3 címen kezdődik.

Példa struktúra használatára:

struct pelda egyik, masik;
egyik.a=5; egyik.b=6; egyik.c='x', egyik.d=egyik.a/2.0;
masik=egyik; /* minden mezőt lemásol */
masik.a=egyik.b; masik.b=egyik.a; 

Vettük még előadáson a mutató (pointer) fogalmát. A mutató egy adott típusú érték kezdőcímét tartalmazza. Mutató deklarálásához a változónév elé tegyünk egy csillagot:

  • int p;: a p változó egy int értéket tartalmaz
  • int *p;: a p változó egy int értékre mutató mutatót tartalmaz
  • int **p;: a p változó egy int értékre mutató mutatóra mutató mutatót tartalmaz
  • char **argv;: az argv változó egy char értékre mutató mutatóra mutató mutatót tartalmaz
  • struct pelda *oda;: az oda változó egy pelda típusnevű struktúrára mutató mutatót tartalmaz

Egy adott változó kezdőcíméhez a változónév elé tegyünk egy & jelet (ésjelet):

  • int a, *p; p=&a;: a p mutató az a (int típusú) változó kezdőcímét tartalmazza
  • int t[5], *p; p=&t[3];: a p mutató a t (int típusú elemekből álló) tömb 3-adik elemédik kezdőcímét tartalmazza
  • struct pelda egyik; int *p; p=&egyik.b;; a p mutató az egyik (pelda típusnevű) struktúra b mezőjének kezdőcímét tartalmazza

A fordított művelethez, tehát egy mutató által mutatott memóriaterület értékéhez a mutató elé tegyünk csillagot:

  • int a=5, *p; *p=&a; a=20; *p+=22; printf("%d", *p);: az a-t először 5-ről 20-ra változtatja, majd megnöveli 22-vel, majd kiírja (a 42-t)
  • struct pelda egyik; char *p=&egyik.c; *p=5;: az egyik (pelda típusnevű) struktúra c mezőjének értékét 5-re változtatja

Speciális mutató a NULL (#include <stdlib.h> kell neki), ami nem mutat érvényes memóriaterületre. Példa használatára:

  • int a, *p=NULL; a=*p;: a második értékadás Segmentation fault-ot (Szegmens hiba) okoz, a program futása megszakad. Megjegyzés: Segmentation fault más programokban máshogy is előállhat.

Vegyük észre, hogy a függvényeknél megtanult cím szerinti paraméterátadásnál mutató átadása történik (pl. a törtösszeadós példában egyszerusit(&as,&es);), és a függvényen belül a kód csak a mutatót követi (pl. *s/=c;).

A bináris fa egy csúcsát struktúraként definiáljuk:

struct csucs {
  int ertek;
  struct csucs *bal;
  struct csucs *jobb;
};

Példa a fenti bináris fa azon részfájának létrehozására, ami a 3-ból indul lefele (~/szimp2/fapelda1.p):

#include <stdlib.h> /* a NULL miatt */
int main(int argc, char**argv) {
  struct csucs a, b;
  a.ertek=3;
  a.bal=NULL;
  a.jobb=&b;
  b.ertek=42;
  b.bal=NULL;
  b.jobb=NULL;
  return 0;
}

5. gyakorlat (2007-03-10)

A mutatók és struktúrák használatát gyakoroljuk. Bináris keresőfák majd csak a következő gyakorlaton lesznek.

A feladat: Az óvódai évbúcsúztatón kiszámolással döntik el, hogy a csoportból ki lesz az két gyerek, aki Barbapapa elménytábor-bérletet nyer. A csoport tornasorba áll, a két széle összekapcsolódik, majd a legmagasabbtól csökkenő sorrendben elmondanak egy kiszámolós mondókát. Akire az utolsó szótag jut, kiesik, majd a kiszámoló a következő gyerektől újraindul mindaddig, amíg több, mint 2 gyerek van. A feladat meghatározni, hogy a gyerekek milyen sorrendben esnek ki, és melyik két gyerek marad bent utoljára.

A gyerekeket tornasorban 1-től N-ig számozzuk (az első a legmagasabb és az N-edik a legalacsonyabb), a mondóka K szótagból áll. 10000 >= N >= 2 és 10000000 >= K >= 1. A bemenet minden sorában N és K található. Minden bemeneti sorhoz egy kimeneti sort kell előállítani: az sor elejére a kieső gyerekek sorszáma kerül (a kiesés sorrendjében) szóközzel elválasztva, majd egy szóköz, majd egy pontosvessző, majd egy szóköz, majd a bennmaradó két gyerek sorszáma szóközzel elválasztva (először az utolsó kiesőre rákövetkező, majd az őrá következő).

A megoldásban minden gyerekhez fel kell venni egy struktúrát (benne a gyerek sorszámával és a következő gyerekre mutató mutatóval).

Példa bemenet:

9 1
9 2
9 1000
8 10000000

A példa bemenethez tartozó kimenet:

1 2 3 4 5 6 7 ; 8 9
2 4 6 8 1 5 9 ; 3 7
1 9 7 4 3 2 5 ; 6 8
8 3 7 6 5 1 ; 2 4

Az alábbi vázlatból lehet kiindulni (~/szimp2/gyerekki.c):

#include <stdio.h>

struct gyerek {
  int szam;
  struct gyerek *kov;
};

struct gyerek t[10000];

int main(void) {
  int n, k;
  iny i;
  /** Az akt változó minden kiszámolás kezdete előtt arra a gyerekre mutat, aki
   * _után_ a kiszámolás elkezdődik. A kiszámolás végeztével pedig arra a 
   * gyerekre mutat, aki _után_ a kiszámolás utolsó szótagja esik.
   */
  struct gyerek *akt;
  while (2==scanf("%d%d", &n, &k)) {
    for (i=0;i<n;i++) {
      ...
    }                  
    t[n-1].kov=&t[0];
    akt=...;
    ...
    printf("; %d %d\n", ...egyikutolso, ...masikutolso);
  }
  return 0;
}

5. előadás (2007-03-10)

A bináris keresőfák megismerését folytatjuk. Célunk, hogy meg tudjuk írni a bináris keresőfába való beszúrás algoritmusát.

A bináris keresőfába való beszúrás (rekurzív) algoritmusa:

  1. A gyökértől, pontosabban a gyökér kezdőcímétől indulunk.
  2. Paraméterként kapjuk az aktuálisan vizsgálandó részfa gyökerének címét. (Üres fa esetén van lényeges különbség: az üres fa gyökere ugyanis NULL, az üres fa gyökerének címe pedig az a memóriaterület, ahol a NULL-t majd átírjuk másra.)
  3. Ha az aktuális gyökér NULL, akkor cseréljük le a beszúrandó csúcsra: a csúcs értéke a beszúrandó érték legyen, a bal és jobb mutatók pedig NULL-ok legyenek.
  4. Ha a beszúrandó érték megegyezik az aktuális gyökérben található értékkel, és az aktuális gyökérnek nincs bal gyereke, folytassuk a jobb részfával (a 3. lépéstől). (Az algoritmus e lépés nélkül is jól működne.)
  5. Ha a beszúrandó érték legfeljebb akkora, mint az aktuális gyökérben található érték, akkor folytassuk a bal részfával (a 3. lépéstől).
  6. Folytassuk a jobb részfával (a 3. lépéstől).

Programban:

#include <stdlib.h> /* a NULL miatt */

struct csucs {
  int ertek;
  struct csucs *bal;
  struct csucs *jobb;
};

/** Beszúrja a gyoker részfába az uj csúcsot levélként (és egyben NULL-t tesz
 * az uj csúcs bal és jobb mutatóiba.
 */
void beszur(struct csucs **gyoker, struct csucs *uj) {
  while (*gyoker!=NULL) {
    if ((*uj).ertek<=(*gyoker).ertek) {
      gyoker=&(*gyoker).bal;
    } else {
      gyoker=&(*gyoker).jobb;
    }
  }
  *gyoker=uj;
  (*uj).bal=NULL;
  (*uj).jobb=NULL;
}

int main(void) {
  struct csucs *gyoker=NULL;
  struct csucs na, nb, nc, nd, ne, nf, ng, nh;
  na.ertek=  0; beszur(&gyoker, &na);
  nb.ertek= -5; beszur(&gyoker, &nb);
  nc.ertek=-10; beszur(&gyoker, &nc);
  nd.ertek= -5; beszur(&gyoker, &nd);
  ne.ertek= -5; beszur(&gyoker, &ne);
  nf.ertek= -2; beszur(&gyoker, &nf);
  ng.ertek=  3; beszur(&gyoker, &ng);
  nh.ertek= 42; beszur(&gyoker, &nh);
  return 0;
}

Vegyük észre, hogy ha más sorrendben szúrjuk be a csúcsokat, más fát kapunk.

Hogyan lehet kirajzolni egy bináris keresőfát? A legegyszerűbb rekurzívan:

void kirajzol(struct csucs *gyoker, int nszokoz) {
  int i;
  if (gyoker!=NULL) {
    for (i=nszokoz; n>0; n--) putchar(' ');
    printf("%d\n", (*gyoker).ertek);
    kirajzol((*gyoker).bal,  nszokoz+2);
    kirajzol((*gyoker).jobb, nszokoz+2);
  }
}

Hogyan lehet lemásolni egy bináris keresőfát? Ehhez szükség van annyi szabad memóriára, amennyit a másolat számára szükséges. Memóriafoglaláshoz a malloc függvényt használhatjuk. A malloc(n) hívás lefoglal egy n hosszúságú memóriaterületet, és visszadja a kezdőcímét. Felszabadítható a free függvénnyel, vagy ha elmulasztjuk, akkor az operációs rendszer felszabadítja, amikor a program kilép.

T típusú memóriaterület foglalása és felszabadítása:

#include <stdlib.h> /* a malloc() miatt kell */
...
  T *p;
  ...
  p=(T*)malloc(sizeof(T));
  ...
  free(p);

Mostmár le tudjuk másolni a fát:

/** Lemásolja a részfát, és visszadja a másolat gyökerének címét. */
struct csucs *lemasol(struct csucs *gyoker) {
  /** Az mgyoker a másolat gyökere. */
  struct csucs *mgyoker;
  if (gyoker==NULL) return NULL;
  mgyoker=(struct csucs*)malloc(sizeof(struct csucs));
  (*mgyoker).ertek=(*gyoker).ertek;
  (*mgyoker).bal =lemasol((*gyoker).bal );
  (*mgyoker).jobb=lemasol((*gyoker).jobb);
}

Házi feladatok

A házi feladatokat a SIO rendszer segítségével kell beadni. Csak azokat kell beadni, amelyeknek a beadási határideje itt fel van tüntetve.

A többi SIO-beli feladatot szorgalmi feladatként lehet beadni. A szorgalmi feladatok megoldása elmélyíti a hallgató tudását, növeli a hallgató gyakorlati rátermettségét, és nagyban segíti a ZH-ra való felkészülést.

Technikai részletek

A C fordításhoz használt szoftver a gcc, verziószám gcc (GCC) 3.4.6 (Debian 3.4.6-4), a házi feladatokat a következő módon fordítjuk:

$ gcc -x c -O2 -std=c99 -pedantic-errors -static -o <forrásfájl>.o <forrásfájl> -lm

A feladat megoldásakor előbb nem a fenti paranccsal, hanem az alábbival érdemes előbb kipróbálni a fordítást:

$ gcc -W -Wall -s -O2 -std=c99 -pedantic-errors -lm -o <program> <program>.c

Ez azért jó, mert a -W -Wall sok hasznos figyelmeztető üzenetet megjelenít, és ily módon a hibákra hamar felhívja a figyelmet.

Fontos, hogy a beadott C forrásfájlok .c-re végződjenek, ellenkező esetben a rendszer fordítási hibát jelez (Compile error).

A main függvénynek return 0;-ra kell végződnie.

Tipp: ha kipróbáláskor Szegmens hiba (Segmentation fault) a hibaüzenet, akkor a nagyobb tömböket ki kell vinni a main() fölé. Például így jobb:

int nagytomb[10000000];
int main(void) {
  ...
  return 0;
}

Tipp: ha kipróbáláskor Szegmens hiba (Segmentation fault) a hibaüzenet, akkor a nagyobb tömbök alaptípusa csökkenthető (például int-ről char-ra, ha elég csak 0..255-ig tárolni a tömbben). Például így jobb:

char nagytomb[10000000];
int main(void) {
  ...
  return 0;
}

Kiírt házi feladatok

kód leírás beadási határidő
uc https://sioweb.math.bme.hu/user.phtml?op=inc&id=6 2007. március 31., 24:00 CET
lcuc https://sioweb.math.bme.hu/user.phtml?op=inc&id=7 2007. március 31., 24:00 CET
pow2count https://sioweb.math.bme.hu/user.phtml?op=inc&id=38 2007. március 31., 24:00 CET
primecount https://sioweb.math.bme.hu/user.phtml?op=inc&id=205 2007. március 31., 24:00 CET
matmul https://sioweb.math.bme.hu/user.phtml?op=inc&id=206 2007. március 31., 24:00 CET

A házi feladatok listája elérhető a SIO rendszerben is: https://sioweb.math.bme.hu/user.phtml?op=zadania

Személyes eszközök