>> [MUSIC Playing]
>> ZAMYLA Chan: Az első dolog, amit értesítést találni, hogy már
már kódot írt nekünk.
Ez az úgynevezett elosztási kód.
Szóval nem csak írásban, a saját kódot a semmiből többé.
Inkább mi kitöltésével üregek néhány már meglévő kódot.
>> A beolvasása sikertelen program rákérdez a számok , hogy töltse ki a szénakazalban, megkeresi a
szénaboglya a felhasználó benyújtott tű, és ez teszi ezt hívja a fajta és a
keresés funkciók meghatározása A helpers.c.
Tehát elérése sikertelen van írva már.
Az Ön feladata, hogy írjon segítők.
>> Szóval, mit csinálunk?
Mi végrehajtása két funkciója van.
Search, amely igazat ad vissza, ha az érték megtalálható a szénakazalban, visszatérő
hamis, ha az érték nem a szénakazalban.
És akkor mi is végrehajtási sort amely rendezi a tömb neve értékeket.
>> Úgyhogy kezelni keresést.
Keresés jelenleg megvalósításra lineáris keresés, de akkor sokat
jobb annál.
Lineáris keresés megvalósítható O n idő, ami elég lassú.
Bár, ez lehet keresni minden lista adott hozzá.
Az Ön feladata, hogy végre bináris keresés, amely a futási idő O log n.
Ez elég gyors.
>> De van egy kikötés.
Bináris keresés csak keresni a előválogatva listákat.
Miért van ez?
>> Nos, nézzük meg egy példát.
Mivel az értékek tömbjét, a szénakazalban, fogunk keresni
egy tűt.
És ebben a példában, Az egész három.
Az út, hogy a bináris keresés működik, hogy a összehasonlítjuk a közép értéke
A tömb a tű, ugyanúgy, mint, hogy hogyan nyitottunk egy telefonkönyv a középső
oldal hét nulla.
>> Tehát miután összehasonlítva a közép-értéket a tű, akkor dobja ki vagy a
a bal vagy a jobb fele a tömb szigorításával a határokat.
Ebben az esetben, mivel három, a tű, kevesebb, mint 10, a középső érték,
jobbra kötött csökkentheti.
De próbálja meg, hogy a határt szoros amennyire csak lehetséges.
Ha a középső érték nem a tűt, akkor tudja, hogy nem kell
tartalmazza azt a keresésben.
Szóval igazad van kötve húzza meg a Keresés korlátok csak egy kicsit nagyobb,
és így tovább és így tovább, amíg megtalálni a tűt.
>> Mit is jelent a pszeudokód néz ki?
Nos, míg mi még mindig keresi a a listát, és még elemek
nézz vesszük a közepén a listán, és hasonlítsa össze a középső értéket
a tű.
Ha ők azonos, akkor ez azt jelenti, hogy már találta a tűt, és mi is
vissza igaz.
>> Ellenkező esetben, ha az kisebb, mint a tű a középső érték, akkor ez azt jelenti,
eldobhatja a jobb felét, és csak keresés a bal oldalán a tömb.
Ellenkező esetben, akkor keresni a jobb oldalán a tömb.
És a végén, ha nincs több elem maradt keresni, de
nem találtam a tűt még, akkor vissza hamis, mert a tű
biztosan nem a szénakazalban.
>> Most egy szép dolog ez pszeudokódja bináris keresés, hogy lehet
értelmezhető vagy egy iteratív vagy rekurzív végrehajtás.
Így lenne rekurzív, ha hívják A keresési funkció a keresési
működni mindkét fele a tömb.
Majd kiterjed a rekurzió egy kicsit később, a Természetesen, de tudom, hogy ez egy
lehetőség, ha szeretne kipróbálni.
>> Most nézzük meg a sort.
Sort vesz egy tömb, és az egész n, ami a méret a tömb.
Most vannak különböző típusú a fajta, és nézd meg néhány
rövidnadrág bemutatók és magyarázatok.
A visszatérési típus számára szortírozás érvénytelen.
Tehát ez azt jelenti, hogy nem megyünk vissza minden tömb a sort.
Mi valóban meg fog változni az igen tömb, amit át belénk.
>> És ez azért lehetséges, mert a tömbök által elfogadott referencia C. Most majd
még több erről később, de a lényeges különbség múló
valami, mint egy egész és múló egy tömb, az, hogy ha
át az egész, a C csak megy, másolatot készíteni, amely egész és adja át
azt a funkciót.
Az eredeti változót nem változik ha a funkció befejeződött.
Egy sor, másrészt, ez nem megy, hogy egy példányt, és azt is megtudhatod
valóban szerkesztése Nagyon tömböt.
>> Tehát az egyik fajta rendezés a kiválasztás sort.
A kiválasztás sort működik kezdve az elején, és akkor iterációkhoz
át, és megtalálja a legkisebb elem.
És akkor a csere, hogy a legkisebb elem az első.
És akkor lépjen a második elem , Meg a következő kisebb
elemet, majd a csere, hogy a a második elem a tömbben, mivel
Az első elem már rendezve.
És igen, akkor is minden elem azonosítása a legkisebb
érték és csere ki.
>> Mert értéke 0, az első elem n mínusz 1, fogsz összehasonlítani
minden következő érték után és megtalálni az index a minimális értéket.
Ha megtalálta a minimális érték index, lehet cserélni az érték a tömb
minimum és array I.
>> Egy másik típusú fajta, amit lehet munkagép buborék sort.
Tehát bubble sort végighalad a listán összehasonlítva a szomszédos elemeket és
csere az elemeket, amelyek vannak rossz sorrendben.
És így, a legnagyobb elem majd buborék a végén.
És a lista sorrendje egyszer nem több elemeket cserélték.
>> Tehát azok két példa a sort algoritmusok, amit végre a
a find programot.
Miután befejeztük sort, és akkor már végzett keresés, akkor véged.
A nevem Zamyla, és ez CS50.
>> [MUSIC Playing]