Tip:
Highlight text to annotate it
X
>> [Musikgengivelse]
>> ZAMYLA CHAN: Den første ting du måske bekendtgørelse om fund er, at vi allerede
have kode skrevet til os.
Dette kaldes fordeling kode.
Så vi ikke bare skrive vores egen kode fra bunden længere.
Snarere, vi udfylder hulrum i nogle eksisterende kode.
>> Det find.c programmet beder for tal at fylde høstak, søger
høstak for en bruger indsendte nål, og det gør dette ved at kalde sortere og
søgning, funktioner defineret i helpers.c.
Så find.c er skrevet allerede.
Dit job er at skrive hjælpere.
>> Så hvad gør vi?
Vi gennemføre to funktioner.
Søg, som returnerer true, hvis en værdi er fundet i høstakken, vender tilbage
falsk, hvis værdien er ikke i høstakken.
Og så er vi også gennemføre slags som sorterer array kaldet værdier.
>> Så lad os tage fat søgning.
Søg i øjeblikket gennemføres som et lineær søgning, men du kan gøre meget
bedre end det.
Lineær søgning er implementeret i O n tid, hvilket er ganske langsomt.
Selv kan den søge enhver liste, det fik.
Dit job er at implementere binær søgning, der har kørt tid O af log n.
Det er temmelig hurtigt.
>> Men der er en bestemmelse.
Binær søgning kan kun søge gennem pre-sorterede lister.
Hvorfor er det?
>> Jamen så lad os se på et eksempel.
I betragtning af en matrix af værdier, høstak, vi kommer til at være på udkig
efter en nål.
Og i dette eksempel, heltallet tre.
Den måde, at binær søgning værker er, at Sammenligner vi den midterste værdi af
array til nålen, meget gerne, hvordan åbnede vi en telefonbog til midten
side i uge nul.
>> Så efter sammenligning af den midterste værdi til nålen, kan du kassere enten
venstre eller højre halvdel af array ved at stramme dine grænser.
I dette tilfælde, da tre vores nål, er mindre end 10, den midterste værdi,
højre bundet kan falde.
Men prøv at gøre dine grænser så stramt som muligt.
Hvis den midterste værdi ikke er den nål, så ved du at du ikke behøver at
medtage den i din søgning.
Så du har ret bundet kan stramme den søgning bounds bare en lille smule mere,
og så videre og så videre, indtil du finder din nål.
>> Så hvad betyder det pseudokode se ud?
Nå, mens vi stadig kigger gennem listen og stadig have elementer til
kigge i, tager vi midt på listen, og sammenligne det midterste værdi til
vores nål.
Hvis de er lige, så det betyder, at vi har fundet nålen og vi kan
returnere sandt.
>> Ellers, hvis nålen er mindre end den midterste værdi, så det betyder, at vi
kan skille den højre halvdel, og lige søge i venstre side af matrixen.
Ellers vil vi søge højre side af matrixen.
Og til sidst, hvis du ikke har nogen flere elementer tilbage til søgning, men du
har ikke fundet nålen endnu, så du return false fordi nålen
absolut ikke er i høstakken.
>> Nu er en pæn ting om dette pseudokode i binær søgning er, at det kan være
tolkes enten en iterativ eller rekursive gennemførelse.
Så det ville være rekursiv hvis du kaldte søgefunktionen i søgningen
kan fungere på hver halvdel af matrixen.
Vi dækker rekursion lidt senere i naturligvis, men ved, at det er et
mulighed, hvis du gerne vil prøve.
>> Lad os nu se på slags.
Sorter tager et array og heltal n, som er størrelsen af matrixen.
Nu er der forskellige typer slags, og du kan se på nogle
shorts til demoer og forklaringer.
Afkastet type til vores slags funktion er ugyldig.
Så det betyder, at vi ikke kommer at returnere eventuelle vifte af slags.
Vi er faktisk kommer til at ændre den meget array, der blev vedtaget i os.
>> Og det er muligt, fordi arrays er sendes som reference i C. Nu vil vi
se mere om dette senere, men væsentlig forskel mellem forbigående
i noget som et heltal og passerer i et array, er, at når du
passere i et heltal, C bare kommer til at lave en kopi af heltal og videregive
det til funktionen.
Den oprindelige variabel vil ikke blive ændret når funktionen er færdig.
Med et array på den anden side er det ikke kommer til at lave en kopi, og du vil
faktisk redigere meget matrix selv.
>> Så en form for sortering er udvælgelse slags.
Udvælgelsen sortere fungerer ved at starte på starten, og så skal du gentage
igen og finde det mindste element.
Og så skal du bytte at mindste elementet med den første.
Og så skal du flytte til det andet element Finder den næstmindste
element og derefter swap at med andet element i array, fordi
det første element allerede er sorteret.
Og så så du fortsætter til hver element i at identificere den mindste
værdi og bytte det ud.
>> For jeg er lig med 0, det allerførste element til n minus 1, er du nødt til at sammenligne
hver næste værdi efter det og finde indekset for den mindste værdi.
Når du finder den mindste værdi indekset, du kan bytte, at værdien af matrix
minimum og matrix I.
>> En anden type af slags, som du kan redskabet er boble slags.
Så boble sortere gentager over listen sammenligning af tilstødende elementer og
bytte de elementer, der er i den forkerte rækkefølge.
Og på denne måde, det største element vil boble til enden.
Og listen er sorteret engang ikke mere elementer er blevet byttet.
>> Så det er to eksempler på sortering algoritmer, som du kan gennemføre for
Find programmet.
Når du er færdig sortere, og du har gjort søgning, er du færdig.
Mit navn er Zamyla, og det er CS50.
>> [Musikgengivelse]