Lineárne vyhľadávanie, binárne vyhľadávanie, binárne vyhľadávacie stromy

Zhrnutie prednášky

Prednáška v jazyku C prakticky ukazuje vyhľadávanie v poli reťazcov. Najprv sa zo vstupného textového súboru s menami načíta neusporiadané pole (dvojrozmerné pole znakov s počítadlom prvkov) a vypíše sa pomocnou funkciou. Potom sa implementuje lineárne vyhľadávanie pomocou strcmp, ktoré prechádza pole prvok po prvku a pri neúspechu vykoná toľko porovnaní, koľko má pole prvkov (v príklade 12). Ako zrýchlenie sa navrhuje binárne vyhľadávanie, ktoré vyžaduje usporiadané pole, preto sa pole buduje usporiadane už pri načítaní: nový prvok sa vkladá insertion-sort spôsobom, pričom sa väčšie prvky posúvajú o jedno miesto dozadu, kým sa nenájde správne miesto. Na konci úseku sa ladí chyba v tomto usporiadanom načítaní.

• - Mená zo vstupného súboru sa načítavajú do dvojrozmerného poľa znakov s premennou pre počet prvkov.
• - Pri parametri funkcie s dvojrozmerným poľom je druhý rozmer povinný.
• - Lineárne vyhľadávanie porovnáva prvky postupne cez strcmp a vráti nález alebo -1.
• - Pri neúspešnom lineárnom hľadaní treba porovnať všetkých n prvkov (v príklade 12 porovnaní).
• - Binárne vyhľadávanie vyžaduje usporiadané pole, preto sa pole musí načítavať usporiadane.
• - Usporiadané vkladanie posúva väčšie prvky o jedno miesto dozadu a na uvoľnené miesto zapíše nový reťazec cez strcpy.
• - Po každom vložení sa zvýši počet prvkov v poli.

Zhrnutie pripravené s pomocou AI z prepisu videa.