>> [MUZYKA GRA]
>> ZAMYLA Chandler: Pierwszą rzeczą, którą może Zawiadomienie o znalezisku jest to, że już
Kod napisany nie dla nas.
Jest to tak zwany kod dystrybucji.
Więc nie tylko pisanie własne kod od zera już.
Raczej jesteśmy wypełniania pustek w pewnym uprzednio istniejącym kodzie.
>> Program find.c monituje o numerach wypełnić stóg siana, wyszukiwania
stóg siana w igle składane przez użytkownika, i robi to przez wywołanie rodzaju i
wyszukiwania, funkcje zdefiniowane w helpers.c.
Więc find.c napisano już.
Twoim zadaniem jest napisać pomocników.
>> Więc co robimy?
Jesteśmy realizacji dwóch funkcji.
Wyszukiwarka, która zwraca true, jeśli wartość znajduje się w stogu siana, wracając
false, jeśli wartość jest nie w stogu siana.
A potem mamy również realizację rodzaju które sortuje tablicę o nazwie wartości.
>> Zajmijmy się więc poszukiwania.
Wyszukiwanie jest obecnie realizowany jako Wyszukiwanie liniowe, ale można to zrobić o wiele
lepiej.
Szukaj liniowy realizowany jest w O czasu n, które jest dość powolna.
Chociaż, może to sprawdzić każda lista podana do niego.
Twoim zadaniem jest wdrożenie wyszukiwanie binarne, które prowadzi razem Ö log n..
To dość szybko.
>> Ale jest warunek.
Binary wyszukiwania może wyłącznie przez wstępnie posortowanych list.
Dlaczego tak jest?
>> No spójrzmy na przykład.
Biorąc pod uwagę, tablica wartości, stóg siana, będziemy szukać
igły.
I w tym przypadku, całkowitą trzy.
Sposób, że wyszukiwarka działa jest to, że binarny Porównując wartość środku
Tablica z igłą, tak jak jak otworzyliśmy książkę telefoniczną na środku
strona w tygodniu zerowym.
>> Więc po porównaniu wartości środku igły, można odrzucić albo
w lewo lub w prawo pół tablicy dokręcając swoje granice.
W tym przypadku, ponieważ trzy nasze igła jest mniejsza niż 10, to wartość środkowy
prawo związane może zmniejszyć.
Ale spróbuj zrobić swoje granice tak mocno, jak to możliwe.
Jeśli wartość środkowa nie jest igła, to wiesz, że nie musisz się
umieścić go w wyszukiwaniu.
Tak masz rację związany może dokręcić wyszukiwania granice tylko trochę więcej,
i tak dalej, i tak dalej, aż Ci znaleźć igłę.
>> Więc co pseudokod wygląda?
Cóż, gdy my wciąż patrząc przez lista i jeszcze elementy do
spojrzeć w, bierzemy na środku listy, i porównać tę wartość do środkowego
nasza igła.
Jeśli są równe, to znaczy mamy znaleźć igłę i możemy
return true.
>> W przeciwnym razie, jeśli igła jest mniejsza niż wartość środkowa, to znaczy, że
może odrzucić prawą połowę, a tylko szukaj po lewej stronie tablicy.
W przeciwnym razie będziemy szukać prawej stronie tablicy.
I na koniec, jeśli nie ma żadnych więcej elementów lewo, ale można szukać
nie znalazłem swoją igłę jeszcze, to return false, ponieważ igły
na pewno nie jest w stogu siana.
>> Teraz miłe rzeczy na temat tego Pseudokod w poszukiwaniu binarnym, który może być
interpretować albo jako iteracyjny lub rekurencyjna realizacja.
Więc byłoby rekurencyjny jeśli nazywa Funkcja wyszukiwania w poszukiwaniu
funkcjonować na każdej połowie tej tablicy.
Omówimy rekursji nieco później w Oczywiście, ale wiem, że jest to
opcję, jeśli chcesz, aby spróbować.
>> Teraz spójrzmy na sortowanie.
Sortuj pobiera tablicę i całkowitą n, która jest rozmiar tablicy.
Teraz są różne rodzaje od rodzaju i można spojrzeć na niektóre
spodenki dla dema i objaśnienia.
Powrót do naszego typu Funkcja sortowania jest nieaktualna.
Więc to oznacza, że ​​nie będziemy powrót żadnej tablicy z rodzaju.
Jesteśmy rzeczywiście będzie zmienić bardzo Tablica została przekazana do nas.
>> I to jest możliwe, ponieważ tablice są przekazywane przez referencję w C, teraz będziemy
zobacz więcej o tym później, ale Zasadnicza różnica między biegiem
w coś takiego jak liczba całkowita i przemijania w tablicy, jest to, że kiedy
przekazać w postaci liczby całkowitej, C jest po prostu będzie zrobić kopię tej liczby całkowitej i przekazać
jej funkcji.
Zmienna oryginalna nie zostanie zmieniony po zakończeniu funkcji.
Z tablicy, z drugiej strony, jest nie zamierza wykonać kopię, a będziesz
faktycznie edycji bardzo sama tablica.
>> Więc jeden rodzaj sortowanie jest Sortuj wybór.
Wybór sortowania zaczynają się prace początek, a następnie iteracyjne
nad i znaleźć najmniejszy element.
A następnie zamienić, że najmniejsza Element z pierwszym.
A następnie przejść do drugiego elementu , Znaleźć następna najmniejsza
Element, a następnie zamienić, że z Drugi element macierzy, ponieważ
Pierwszy element jest już posortowana.
I tak to nadal dla każdego elementem identyfikacji najmniejsza
wartości i zamiana go.
>> Bo jest równa 0, pierwszy element, n minus 1, masz zamiar porównać
każda następna wartość po tym i znaleźć Wskaźnik wartości minimalnej.
Po znalezieniu indeksu wartości minimalnej, można zamienić tę wartość z tablicy
Minimalna i tablicy I.
>> Innym rodzajem rodzaju, że można wdrożenia jest sortowanie bąbelkowe.
Tak iteracje bańka na listę sortowania porównywanie sąsiednich elementów i
ciężkich elementów, które są w złej kolejności.
I w ten sposób największy elementem będzie bańka do końca.
A lista jest posortowana po nie więcej elementy zostały zamienione.
>> To są dwa przykłady rodzaju algorytmy, które można wdrożyć do
Program find.
Po zakończeniu sortowania, a ty wykonane wyszukiwanie, skończysz.
Nazywam się Zamyla, i to jest CS50.
>> [MUZYKA GRA]