>> [MUZYKI]
>> DOUG LLOYD: OK, więc w ten punkt w czasie,
omówiliśmy wiele podstaw C Wiemy dużo o zmiennych, tablic,
wskaźniki, wszystko, co dobre rzeczy.
Ci są jakby zbudowany aby zobaczyć, jak podstaw,
ale możemy zrobić więcej, prawda?
Możemy łączyć rzeczy razem w interesujący sposób.
>> A więc zróbmy to, zacznijmy się rozwijać, co C daje nam,
i zacząć tworzyć własne dane konstrukcje wykorzystujące te budynek
bloki razem coś zrobić naprawdę cenne, przydatne.
Jednym ze sposobów możemy to zrobić mówić o zbiorach.
Tak więc do tej pory mieliśmy jeden rodzaj danych struktura reprezentująca kolekcje
od wartości, podobnie jak wartości.
To byłoby tablicą.
Mamy zbiory liczb całkowitych, lub zbiory znaków i tak dalej.
>> Struktury są również swego rodzaju danych Struktura zbierania informacji,
ale to nie jest do zbierania jak wartości.
Zwykle łączy różne typy danych razem wewnątrz jednej obudowie.
Ale to nie jest sam wykorzystywane do łańcucha razem
lub łączyć ze sobą podobne przedmioty, takie jak tablica.
Tablice są idealne dla Element patrzeć, ale przypominam sobie
że jest to bardzo trudne wstawić do tablicy,
chyba, że ​​mamy do wkładania w sam koniec tej tablicy.
>> A najlepszym przykładem mam za to jest Sortowanie przez wstawianie.
Jeśli pamiętacie nasz film na Sortowanie przez wstawianie,
nie było wiele Koszty udziału w konieczności
podnieść elementy, i przeniesienie ich się w sposób dopasować coś
w środku swojej tablicy.
Tablice również cierpią z powodu innego Problem, który jest brak elastyczności.
Kiedy zadeklarować tablicę, mamy jedną szansę na to.
Docieramy do powiedzenia, chcę to wiele elementów.
Może być 100, to może 1,000, to może
x, gdzie x to numer, który użytkownik dał nam na wiersz lub na komendzie
Linia.
>> Ale tylko jeden strzał na to, że nie daj się potem mówią, oh, właściwie,
potrzebne 101 lub Potrzebowałem X plus 20.
Za późno, my już ogłoszony tablica, a jeśli chcemy mieć 101 lub x
plus 20, musimy zadeklarować zupełnie inna tablica,
skopiować wszystkie elementy tablicy powyżej, a następnie mamy wystarczająco dużo.
A co, jeśli jesteśmy znowu źle, co jeśli rzeczywiście potrzeba 102 lub X plus 40,
musimy to zrobić ponownie.
Tak więc są bardzo nieelastyczne do zmiany rozmiaru nasze dane,
ale jeśli połączymy ze sobą pewne z podstaw już, że mamy
Dowiedziałem się o wskazówki i budowli, w szczególności z wykorzystaniem pamięci dynamicznej
Alokacja z malloc, że można umieścić te elementy razem
Aby utworzyć nowe dane structure-- A pojedynczo związane listy możemy say--
która pozwala nam się rozwijać i kurczyć zbiór wartości
i nie będziemy mieć żadnego marnował miejsca.
>> Więc znowu, my nazywamy ten pomysł, to pojęcie, połączonej listy.
W szczególności, w tym filmie jesteśmy mówisz pojedynczo połączonej listy,
a potem jeszcze wideo porozmawiamy o podwójnie związane listy, które
jest po prostu wariacja na temat tutaj.
Ale pojedynczo związane listy składa się z węzłów
węzły po prostu streszczenie term-- to jest po prostu coś Dzwonię
to swego rodzaju Struktura, w zasadzie, że jestem?
Tylko będzie to nazwać node-- i to węzeł ma dwóch członków, lub dwa pola.
Ma danych, zwykle całkowitą, pływak charakter,
czy może być jakiś inny typ danych które zostały zdefiniowane z typu def.
I zawiera wskaźnik inny węzeł tego samego typu.
>> Mamy więc dwie rzeczy wewnątrz węzeł, danych i wskaźnik
do innego węzła.
A jeśli zaczniesz wizualizować to można o tym myśleć
jak sieć węzłów są ze sobą połączone.
Mamy pierwszy węzeł, to zawiera dane, a wskaźnik
do drugiego węzła, zawierającym Dane, a wskaźnik trzeciego węzła.
A więc dlatego nazywamy go do połączonej listy, są one ze sobą powiązane.
>> Co to specjalny Struktura węzła wygląda?
Cóż, jeśli pamiętam z naszej wideo na definiowania własnych typów, z typu def,
możemy zdefiniować structure-- i wpisz zdefiniować strukturę tak.
tyepdef struct sllist, a następnie jestem przy użyciu wartości słowa tu arbitralnie
wskazać dowolny typ danych, naprawdę.
Można zdać się na liczbę całkowitą lub pływaka, możesz mieć co chcesz.
To nie jest ograniczona do zaledwie liczb całkowitych, lub coś w tym stylu.
Tak więc wartość jest tylko arbitralne Typ danych, a następnie wskaźnik
do innego węzła tego samego typu.
>> Teraz jest mały haczyk tutaj z definiowania struktury
kiedy to struktura siebie więzy.
Muszę mieć tymczasowy nazwa dla mojej konstrukcji.
Na koniec dnia I wyraźnie to nazwać
Węzeł SLL, to ostatecznie nowy wymienić część mojej definicji typu,
ale nie mogę korzystać z węzła SLL w środku tego.
Wynika to z faktu, że nie mają stworzył typ zwany węzeł SLL
dopóki nie uderzył ten punkt końcowy tutaj.
Do tego momentu, muszę mieć inny sposób odnieść się do tego typu danych.
>> I jest to samo referencyjna typ danych.
To; s do typu danych Struktura, która zawiera dane
i wskaźnik do innego Struktura tego samego typu.
Więc muszę być w stanie odnieść się do Ten typ danych, przynajmniej czasowo,
tak, nadając mu tymczasowy Nazwa struct sllist
Pozwala mi to powiedzieć chcę wskaźnik do innego sllist struct,
gwiazda struktura sllist, a następnie po tym, jak zakończył definicję,
Teraz mogę nazwać tego typu węzeł SLL.
>> Więc dlatego widzisz tam tymczasowa nazwa tutaj,
ale na stałe nazwę.
Czasami można zobaczyć definicje struktury,
Na przykład, nie jest siebie więzy, które
nie ma nazwy specyfikatora tutaj.
To po prostu powiedzieć typedef struct, otworzyć nawias klamrowy, a następnie zdefiniować.
Ale jeśli struktura jest samo więzy, jak ten jeden jest,
trzeba określić tymczasowa nazwa typu.
Ale w końcu, teraz że zrobiliśmy to,
możemy po prostu odnosi się do węzły te jednostki te,
jako SLL węzłów dla celów od pozostałej części tego obrazu.
>> W porządku, więc wiemy, jak stworzyć połączony węzeł listy.
Wiemy, jak zdefiniować węzeł wiązana listy.
Teraz, gdy mamy zamiar zacząć wykorzystując je do zbierania informacji,
jest kilka operacji mamy trzeba zrozumieć i pracować.
Musimy wiedzieć, jak tworzyć połączonej listy z powietrza.
Jeśli nie ma już żadnej listy, chcemy rozpocząć jeden.
Więc musimy być w stanie w celu utworzenia połączonej listy
musimy chyba szukać listę łącza
znaleźć element szukamy.
Musimy być w stanie wprowadzić nowe rzeczy do listy,
chcemy, aby nasza lista, aby móc się rozwijać.
I podobnie, chcemy być w stanie usunąć z naszej listy rzeczy,
chcemy, aby nasza lista, aby móc się kurczyć.
I na koniec nasze programy, szczególnie
jeśli przypomnieć, że jesteśmy dynamicznego przydzielania pamięci
budować te listy zwykle, chcemy uwalniania całego tej pamięci
kiedy skończymy pracę z nim.
A więc musimy być w stanie usunąć Cała lista połączone w jednym nie swoop.
Warto więc przejść przez Niektóre z tych działań
i jak możemy je wizualizować, rozmowy w kodzie pseudocode specjalnie.
Dlatego chcemy, aby utworzyć związane listy, więc być może
Aby zdefiniować funkcję z tego prototypu.
SLL gwiazda węzłów, tworzenie i olewam w jednym argumentem, niektóre arbitralne danych
wpisz ponownie jakiegoś dowolnego typu danych.
Ale ja returning-- tej funkcji powinny wróć do mnie wskaźnik, Do pojedynczo
związana węzłem listy.
Ponownie, staramy się stworzyć połączonej listy z powietrza,
więc muszę wskaźnik do że lista gdy skończę.
>> Więc jakie są kolejne etapy tutaj?
Cóż, pierwszą rzeczą, że jestem zamiar zrobić to dynamicznie
przydzielić miejsca dla nowego węzła.
Ponownie tworzymy go z cienkiej powietrza, więc musimy przestrzeni malloc dla niego.
I oczywiście, natychmiast po tym jak malloc,
zawsze upewnij się, że nasze pointer-- nie wrócić zerowy.
Bo jeśli spróbujemy poważanie pustego wskaźnika,
będziemy cierpieć wysypać, a my tego nie chcemy.
>> Następnie chcemy wypełnić pole, chcemy zainicjować pole wartości
i zainicjować następne pole.
A potem chcemy to-- końcu jak Prototyp funkcji indicates-- chcemy
zwraca wskaźnik do węzła SLL.
Co więc zrobić to wygląda wizualnie?
Cóż, najpierw jedziemy do dynamicznie przydzielić miejsca dla nowego węzła SLL,
więc malloc-- to reprezentacja wizualna
węzła właśnie utworzyliśmy.
A my upewnij się, nie jest null-- w tym wypadku
obraz nie będzie miał pokazał się, czy to null
mielibyśmy zabraknie pamięci, więc jesteśmy dobrze tam.
Więc teraz jesteśmy do punktu C, zainicjować pole wartości węzłów.
Cóż, na podstawie tej funkcji zadzwonić używam tutaj,
Wygląda na to, że chcą przekazać w 6, więc będę 6 w polu wartości.
Teraz, zainicjować następne pole.
No, co ja mam do zrobienia, nie ma nic obok, w prawo,
jest to jedyna rzecz na liście.
Więc jaka jest następna rzecz na liście?
>> To nie powinno wskazywać na cokolwiek, prawda.
Nic więcej tam, więc to, co jest koncepcja wiemy, że to nothing--
wskaźniki do niczego?
Powinno być może chcemy aby tam pustego wskaźnika,
a ja reprezentuje wartość null wyżeł, jak tylko czerwone pole,
nie możemy iść dalej.
Jak zobaczymy trochę później, będziemy mieć ewentualnie nawet łańcuchy
strzał podłączenia węzły te razem,
ale gdy trafisz czerwone pole, to null
nie możemy iść dalej, że to koniec listy.
>> I wreszcie, po prostu chcemy zwracają wskaźnik do tego węzła.
Więc nazwijmy go nowym, i wróci nowa
dzięki czemu może być stosowany w Funkcja to, co stworzył.
Więc nie idziemy, stworzyliśmy pojedynczo związane lista węzeł z powietrza,
a teraz mamy listę możemy pracować.
>> Teraz, powiedzmy, że już mają duży łańcuch
i chcemy znaleźć coś w nim.
I chcemy funkcję, która się dzieje powrót prawdziwe lub fałszywe, w zależności
od tego, czy wartość istnieje w tym wykazie.
Prototyp funkcji lub Deklaracja dla tej funkcji,
może wyglądać this-- bool znaleźć i Następnie chcemy przekazać w dwóch argumentów.
>> Pierwszy, to wskaźnik do Pierwszym elementem połączonej listy.
To jest rzeczywiście coś będziesz zawsze chcesz śledzić,
i rzeczywiście może być coś, co nawet umieścić w zmiennej globalnej.
Po utworzeniu listy, zawsze, zawsze
Aby śledzić bardzo Pierwszy element listy.
W ten sposób można zwrócić się do wszystkich innych Elementy by tuż po łańcuch,
bez konieczności utrzymania wskazówek nienaruszone do każdego elementu.
Wystarczy tylko śledzić pierwszy jeden, czy wszystkie są połączone w łańcuch.
>> A potem druga sprawa przekazujemy ponownie
jest arbitralnie some-- niezależnie od typu danych jesteśmy
szukasz jest wewnątrz z nadzieją jeden z węzłów w liście.
Więc jakie są kroki?
Cóż, pierwsze co robimy, jest tworzymy wskaźnik poprzeczny
wskazując na czele list.
Cóż, dlaczego to robimy, mamy już mieć wskaźnik na czele list,
dlaczego nie możemy się poruszać, że jeden wokół?
Cóż, tak właśnie powiedziałem, to naprawdę ważne dla nas
zawsze śledzić Pierwszy element listy.
A więc jest to rzeczywiście lepiej stworzyć duplikat, który,
i używać, aby poruszać się tak, że nigdy nie przypadkowo odejść, lub zawsze
mają wskaźnik w pewnym momencie, że jest w prawo na pierwszym elemencie listy.
Więc lepiej jest utworzyć Drugi, którego używamy, aby przenieść.
>> Następnie wystarczy porównać, czy Pole wartości w tym węźle
jest to, co szukasz, a jeśli jest to Nie, po prostu przejść do następnego węzła.
A my dalej robić, że nad, i więcej, i więcej,
aż albo znaleźć element, albo uderzymy
null-- dotarliśmy do końca listy i go tam nie ma.
Powinno to mam nadzieję, że pierścień dzwon do ciebie, jak tylko liniowy wyszukiwarka,
jesteśmy po prostu replikacji go w pojedynczo połączone struktury lista
zamiast przy użyciu tablicy, aby to zrobić.
>> Więc tutaj jest przykład pojedynczo połączonej listy.
Ten składa się z pięć węzłów, a my mamy
wskaźnik na czele Lista, która nazywa się lista.
Pierwszą rzeczą, którą chcesz zrobić, to ponownie utworzyć ten wskaźnik przejścia.
Więc mamy teraz dwa wskaźniki które wskazują na to samo.
>> Teraz, tutaj odnotować również, ja nie muszą malloc żadnego miejsca dla trav.
Nie powiedziałem trav równa malloc coś, że węzeł już istnieje,
że przestrzeń w pamięci, już istnieje.
Więc faktycznie robimy jest tworząc kolejny wskaźnik do niego.
Nie jestem mallocing dodatkowe miejsca, po prostu mają teraz dwa wskaźniki
wskazując tym samym.
>> Tak jest 2, co szukam?
Cóż, nie, tak, a nie jestem zamiar, aby przejść do następnego.
Więc w zasadzie powiedziałbym, trav równa TRAV obok.
Jest 3 co szukam, nie.
Więc nadal iść poprzez, aż ostatecznie
dostać się do 6, który jest to, czego szukam na podstawie wywołania funkcji
Mam na górze tam, i tak skończę.
>> A co, jeśli element jestem poszukuje nie jest na liście,
jest to nadal będzie działać?
Cóż, zauważysz, że lista tutaj jest nieco inny,
i to jest inna sprawa, że ​​to ważne z połączonych listach,
nie masz się zachować je w określonej kolejności.
Możesz, jeśli chcesz, ale można już zauważyć
że nie jesteśmy śledzenie jaki numer elementem jesteśmy.
>> I to jest jakby jednym handlu, które mieć z połączonej listy wersety tablic,
jest to, że nie mamy o dostępie swobodnym już.
Nie możemy po prostu powiedzieć, chcę aby przejść do elementu 0TH,
lub 6. elementem mojej tablicy, które można zrobić w tablicy.
Nie mogę powiedzieć, że chcą, aby przejść do Element 0-gi lub 6th Element,
lub 25. elementem mojego połączonej listy, nie ma indeksu z nimi związane.
I tak naprawdę nie ma znaczenia jeśli mamy zachować naszą listę, w porządku.
Jeśli chcesz Ciebie Na pewno można, ale nie
nie ma powodu, dlaczego muszą przechowuje się w dowolnej kolejności.
Więc jeszcze raz, spróbujmy znaleźć 6 na tej liście.
Cóż, możemy rozpocząć się poczynając, nie znajdziemy 6,
a następnie nie kontynuować znalezieniu 6, aż w końcu dostać się tutaj.
Więc teraz trav wskazuje na węzeł zawierające 8, sześć nie w środku.
>> Więc następnym krokiem będzie aby przejść do następnego wskaźnika,
więc powiedzieć, trav równa TRAV obok.
Cóż, trav następne, oznaczone czerwone pole nie jest puste.
Więc nie ma nigdzie indziej go, a więc w tym momencie
możemy stwierdzić, że osiągnęliśmy końcem połączonym listy
i 6, nie ma tam.
I to być zwrócone fałszywe w tym przypadku.
>> OK, w jaki sposób wprowadzić nowy węzeł w połączonej listy?
Więc byliśmy w stanie stworzyć połączonej listy znikąd,
ale prawdopodobnie chcesz zbudować łańcuch i nie
utworzyć kilka różnych list.
Chcemy mieć jedną listę, ma kilka węzłów w nim,
nie kilka list z jednego węzła.
Więc nie możemy po prostu zachować używając Tworzenie Funkcja zdefiniowaliśmy wcześniej, teraz my
Aby wstawić do Lista, która już istnieje.
>> Więc tym przypadku, będziemy przekazać w dwóch argumentów,
wskaźnik do głowy, że związane listy, które chcesz dodać do listy.
Ponownie, to dlaczego jest tak ważne, że zawsze
śledzić, bo jest to jedyny sposób, naprawdę
muszą odnosić się do całej listy jest tak by wskaźnik do pierwszego elementu.
Dlatego chcemy, aby przejść w sposób wskaźnik do tego pierwszego elementu,
i cokolwiek Cenimy chcesz dodać do listy.
I ostatecznie ta funkcja będzie zwracają wskaźnik
do nowego czele połączonej listy.
>> Jakie są kolejne etapy tutaj?
Cóż, tak jak w przypadku tworzenia, musimy dynamicznie przydzielać
przestrzeń dla nowego węzła, i sprawdź, pewność, że nie zabraknie pamięci, ponownie,
ponieważ używamy malloc.
Następnie chcemy wypełnić i wstawić węzeł,
więc umieścić numer, niezależnie od val jest do węzła.
Chcemy, aby wstawić węzeł na początek połączonej listy.
>> Jest powód, że Aby to zrobić, i to
może być warte podjęcia sekundę aby wstrzymać film tutaj,
i myśleć o tym, dlaczego miałbym chcieć wstaw na początku związane
lista.
Ponownie, już wcześniej wspomniałem że tak naprawdę nie ma
znaczenia, czy zachowamy go w dowolnym zamówienie, więc może to jakaś wskazówka.
I zobaczyłem, co by się stało, gdybyśmy chciał to-- lub tylko sekundę
temu, kiedy mieliśmy poprzez wyszukiwanie ci
widział, co może się stało, gdybyśmy starali
wstawić na koniec listy.
Ponieważ nie mają wskaźnik na koniec listy.
>> Więc dlatego, że nie chcę wstawić na początku
to dlatego, że mogę to zrobić natychmiast.
Mam wskaźnik na początku i zobaczymy to na wizualne w drugim.
Ale jeśli chcę wstawić na końcu, Muszę zacząć od początku,
przechodzić przez całą drogę do końca, a następnie przykleić ją na.
Tak, oznaczałoby to, że wstawienie na końcu listy
staną się o N Operacja, wracając
do naszej dyskusji złożoność obliczeniowa.
Że to stać się o pracy n, gdzie jako lista dostał większy i większy,
i większe, to będzie stawać się coraz trudniej hals coś
on na końcu.
Ale to jest zawsze bardzo łatwo hals coś na początku,
jesteś zawsze na początku.
>> I zobaczymy wizualną tego ponownie.
A potem, gdy skończymy, po mamy wstawiony nowy węzeł,
chcemy zwrócić naszą wskaźnik nowy szef połączonej listy, które
ponieważ jesteśmy wstawienie u początek, rzeczywiście będzie
wskaźnik do węzła po prostu stworzył.
Miejmy wizualizację tego, bo myślę, że to pomoże.
>> Więc oto nasza lista, składa się z cztery elementy, węzeł zawierający 15,
co wskazuje na węzeł zawierający 9, która
Wskazuje węzła zawierającej 13, co wskazuje na węzeł zawierający
10, który ma zerowy wskaźnik w kolejnym wskaźnikiem
tak, że to koniec listy.
Dlatego chcemy, aby wstawić nowy węzeł o wartości 12
na początku lista, co mamy robić?
Cóż, po pierwsze, że malloc przestrzeń dla węzeł, a następnie kładziemy 12 tam.
>> Więc teraz mamy osiągnięcia punkt decyzji, prawda?
Mamy kilka wskaźniki, które mogliśmy
przenieść, który z nich należy pierwszy ruch?
Powinniśmy się 12 wskaż polecenie nowy szef list--
i przepraszam, powinniśmy uczynić 12 wskazują na starym czele listy?
A może powinniśmy powiedzieć, że Teraz zaczyna się na liście 12.
Istnieje rozróżnienie tam, i przyjrzymy
przy czym dzieje się tak w drugim.
>> Jednak prowadzi to do świetny temat na pasku bocznym
który jest jednym z najtrudniejszych rzeczy z połączonych list
jest ułożenie wskazówki w prawidłowej kolejności.
Jeśli przenieść rzeczy w porządku, może skończyć się przypadkowo
osierocanie resztę listy.
A oto przykład tego.
Więc chodźmy na pomysł of-- dobrze, że właśnie stworzył 12.
Wiemy, że 12 będzie nowy szef listy,
więc dlaczego nie możemy się poruszać wskaźnik Lista tam zwrócić.
>> OK, więc to jest dobre.
Więc teraz, gdy ma 12 następny punkt?
Mam na myśli, wizualnie widać który to punkt do 15,
jak ludzie to naprawdę dla nas oczywiste.
Jak działa komputer wiedzieć?
Nie mamy nic wskazując na 15 już, prawda?
>> Straciliśmy żadnego zdolność do powoływania się na 15.
Nie możemy powiedzieć, nowa strzałkę obok równych coś, tam nic nie ma.
W rzeczywistości, mamy osieroconych reszta listy
w ten sposób, mamy przypadkowo uszkodzony łańcuch.
I na pewno nie chcesz, aby to zrobić.
>> Warto więc wrócić i spróbować jeszcze raz.
Być może to, co trzeba zrobić, jest ustawienie 12 w następny wskaźnik
do starego czele listy pierwszej, Następnie możemy przejść do listy powyżej.
Oraz tym, że jest to odpowiedniej kolejności, że my
należy postępować, gdy jesteśmy pracy z pojedynczo połączonej listy.
Zawsze chcemy podłączyć nowy element do listy,
Zanim podejmiemy tego rodzaju ważny krok zmiany
gdzie szef połączonej listy jest.
Ponownie, to takie podstawową rzeczą, Nie chcemy, aby stracić to.
>> Dlatego chcemy, aby upewnić się, że wszystko jest połączone w łańcuch,
zanim przejdziemy ten wskaźnik.
I tak będzie to prawidłowa kolejność, który jest połączenie 12 na liście
to znaczy, że lista zaczyna się 12.
Jeśli wspomniana lista zaczyna się o 12, a następnie próbował połączyć 12 do listy,
widzieliśmy już, co się dzieje.
Tracimy listę przez pomyłkę.
>> OK, więc jeszcze jedno o czym rozmawiać.
Co zrobić, jeśli chcemy pozbyć cała związana listy na raz?
Znowu jesteśmy mallocing wszystkie te miejsca, a więc
trzeba zwolnić go, gdy skończymy.
Teraz chcemy, aby usunąć cała lista powiązane.
Cóż, to, co chcemy zrobić?
>> Jeśli doszliśmy do pustego wskaźnika, możemy Aby zatrzymać, inaczej, po prostu usuń
reszta z listy, a następnie uwolnij mnie.
Usuń resztę listy, a następnie zwolnić bieżący węzeł.
Co to brzmi jak, technikę, mają rozmawialiśmy
o wcześniej Czy to brzmi jak?
Usuń wszyscy, a następnie wrócić i skasować mnie.
>> To rekurencji, jakie sprawiły, że Problem trochę mniejszy,
Mówimy usunięcie wszystkich indziej, to możesz mnie usunąć.
I dalej w dół drogi, że węzeł powie, usuń wszyscy.
Ale w końcu dojdziemy do Punkt, w którym lista jest null,
i to jest nasza sprawa bazowej.
>> Warto więc spojrzeć na to, i jak to może działać.
Więc oto nasza lista, to jest to samo listy byliśmy po prostu mówisz,
i tam kroki.
Jest dużo tekstu tutaj, ale mam nadzieję, że wizualizacja pomoże.
>> Więc have-- i również wyciągnął do ramki o naszej ilustracji
z naszego połączenia wideo w stosy, i mam nadzieję, że to wszystko
razem pokaże, co się dzieje.
Więc tutaj jest nasz kod pseudokod.
Jeśli dojdziemy null wskaźnik, zatrzymać, w przeciwnym razie,
usuń resztę listy, następnie zwolnić bieżący węzeł.
Więc teraz, list-- wskaźnik, że jesteśmy
przechodząc do niszczenia punktów do 12.
12 nie jest wskaźnikiem NULL, więc jesteśmy zamiar usunąć resztę listy.
>> Co jest usunięcie Reszta z nas uczestniczy?
Cóż, to znaczy, dokonywania zadzwonić do zniszczenia, mówiąc:
że 15 jest na początku Reszta listy chcemy zniszczyć.
A więc wezwanie do zniszczenia 12 jest trochę zawieszone.
To zamrożone tam, czekając na zadzwonić do zniszczenia 15, aby zakończyć swoją pracę.
>> Cóż, 15 nie jest wskaźnikiem NULL, a tak to się mówi, wszystko w porządku,
dobrze, usunąć resztę listy.
Reszta listy zaczyna na 9, a więc musimy po prostu
zaczekać do momentu usunięcia wszystkiego, rzeczy, a potem wrócić i skasować mnie.
Cóż 9 powie, dobrze, Nie jestem pusty wskaźnik,
tak, usuń resztę listę tutaj.
A więc spróbuj i zniszczyć 13.
13 mówi, że nie jestem pusty wskaźnik, samo, przechodzi złotówki.
10 nie jest wskaźnikiem NULL, 10 zawiera pustego wskaźnika,
ale 10 nie sama w sobie jest teraz wskaźnik NULL,
i tak przechodzi złotówki też.
>> A teraz lista punktów nie, to naprawdę zwraca się do some--
gdybym miał więcej miejsca na obraz, to zwraca się do jakiegoś losowego miejsca
że nie wiemy co to jest.
Jest to wskaźnik NULL choć lista jest dosłownie teraz ustawić to wartości null.
Jest skierowany bezpośrednio w tym czerwonym polu.
Dotarliśmy do pustego wskaźnika, więc możemy zatrzymać, i gotowe.
>> I tak, że rama jest now-- purpury u góry stack-- to aktywna ramka,
ale to się robi.
Jeśli doszliśmy pustego wskaźnika, stop.
My nic nie robimy, nie może uwolnić pustego wskaźnika,
nie malloc dowolny Przestrzeń i tak skończymy.
Więc tej ramki funkcji jest zniszczony, a my
resume-- możemy odebrać, gdzie zostawiliśmy się z kolejnym najwyższym jeden, który
Jest to ciemna niebieska ramka tutaj.
Więc możemy odebrać prawo w którym skończyliśmy.
Mamy usunięte reszty Lista już, więc teraz jesteśmy
zamiar uwolnić bieżących węzłów.
Więc teraz możemy uwolnić ten węzeł, a teraz dotarliśmy do końca funkcji.
I tak, że rama funkcja jest zniszczona, i odbiór na jasnoniebieskim jeden.
>> Więc to says-- Już done-- usuwanie reszty listy, tak
uwolnić bieżący węzeł.
A teraz żółta ramka jest powrotem na górze stosu.
A więc, jak widać, jesteśmy teraz zniszczenia listę od prawej do lewej.
>> Co by się stało, gdyby, gdybyśmy zrobili rzeczy w niewłaściwy sposób?
Tak jak kiedy próbowaliśmy dodać element.
Jeśli zawiedli łańcuch, jeśli to nie podłączyć wskaźniki
w odpowiedniej kolejności, jeśli będziemy tylko uwolnił pierwszy element,
jeśli tylko uwolnił szef liście, teraz my
nie sposób odnieść się do reszta listy.
I tak musielibyśmy osierocone wszystko,
mielibyśmy co zwany przeciek pamięci.
Jeśli pamiętacie z naszego filmu na dynamicznej alokacji pamięci,
że nie jest to bardzo dobra rzecz.
>> Tak jak powiedziałem, nie kilka operacji
że musimy użyć do pracy z listy skutecznie powiązane.
I można zauważyć, że pominięto jeden, usuwanie pojedynczy element z innej
lista.
Powód to zrobiłem Jest to właściwie rodzaj
trudne, aby myśleć o tym, jak usunąć pojedynczy element z punktu A pojedynczo
połączonej listy.
Musimy być w stanie przeskoczyć coś w liście, który
oznacza, że ​​dostać się do point-- my chcesz usunąć ten node--
ale aby zrobić to tak, że nie tracą żadnych informacji,
musimy połączyć to Węzeł tutaj, tutaj.
>> Więc pewnie zrobił źle z punktu widzenia.
Więc jesteśmy na początku naszej lista, jesteśmy przebiega przez,
Chcemy, aby usunąć ten węzeł.
Jeśli tylko go usunąć, mamy uszkodzony łańcuch.
Ten węzeł tutaj odnosi się do wszystkiego,
zawiera łańcuch stąd na zewnątrz.
>> Więc co trzeba zrobić w rzeczywistości po tym jak dostać się do tego punktu,
to musimy cofnąć się jeden, a podłączyć węzeł nad do tego węzła,
więc można następnie usunąć jeden w środku.
Ale pojedynczo związane listy nie zapewniają nam drogę, do tyłu.
Więc musimy je zachować dwa wskaźniki, i przenieść je
rodzaj off kroku, jeden za inne, jak idziemy, lub dostać się do punktu
a następnie wysłać kolejny wskaźnik, dzięki.
I jak widać, to może trochę niechlujnie.
Na szczęście mamy inny sposób na rozwiązanie, które,
kiedy mówimy o podwójnie połączonych listach.
>> Jestem Doug Lloyd, to CS50.