[Powered by Google Translate] [Rozdział 6] [Więcej Comfortable] [Rob Bowden] [Harvard University] [To jest CS50.] [CS50.TV] 

Możemy udać się do naszej sekcji pytań. Wysłałem adres URL miejsca wcześniej. Początek sekcji pytań powiedzieć- widocznie nie jestem całkowicie unsick-jest to bardzo proste pytanie po prostu to, co jest valgrind? Co valgrind zrobić? Ktoś chce powiedzieć, co valgrind robi? [Student] Kontrole wyciekiem pamięci. Tak, valgrind jest ogólny sprawdzania pamięci. To, w końcu, mówi, jeśli masz jakieś przecieki pamięci, co jest głównie to, czego używasz go, ponieważ jeśli chcesz dobrze w zestawie problem lub jeśli chcesz dostać się na wielkim statku, trzeba mieć żadnych przecieków pamięci w ogóle, oraz w przypadku gdy masz przeciek pamięci, że nie można znaleźć, również pamiętać, że w każdym przypadku otwierania pliku i jeśli nie zamknąć, to wyciek pamięci. 

Wiele osób poszukuje jakiegoś węzła, który oni nie zwalniając kiedy tak naprawdę, nie zamknąć słownika w etapie pierwszym. Informuje także, jeśli masz jakieś nieważne czyta lub pisze co oznacza, że ​​jeśli spróbujesz ustawić wartość to jest poza koniec stosu i nie zdarzy się seg winy ale valgrind go łapie, jak nie powinno być rzeczywiście pisanie tam, a więc na pewno nie powinien mieć żadnej z tych albo. Jak używać Valgrind? Jak używać Valgrind? 

To ogólne pytanie niby go uruchomić i patrzeć na wyjściu. Wyjście jest ogromny wiele razy. Jest też zabawa błędy gdzie jeśli masz jakieś strasznie źle dzieje się w pętli, to będzie to w końcu powiedzieć: "Zbyt wiele błędów. Mam zamiar zatrzymać liczenie teraz ". Jest to w zasadzie tekstowych wyjście, że trzeba analizować. W końcu powie to żadnych wycieków pamięci, które masz, Jak wiele bloków, które mogą być przydatne, ponieważ jeśli jest to jeden blok unfreed, to jest to zazwyczaj łatwiej znaleźć niż 1.000 bloki unfreed. 1.000 bloki unfreed prawdopodobnie oznacza jesteś nie zwalniając połączonego listy w odpowiedni sposób, czy coś. To się valgrind. 

Teraz mamy naszą sekcję pytań, których nie trzeba pobrać. Możesz kliknąć na moje imię i pociągnij je w przestrzeni. Kliknij teraz na mnie. Wersja 1 będzie stos, które robimy w pierwszej kolejności. Wersja 2 będzie kolejka, a wersja 3 będzie pojedynczo połączonej listy. Zaczynając od naszego stosu. Jak mówi tutaj, stos jest jednym z najbardziej podstawowych, podstawowe struktury danych informatyki. Bardzo prototypowy przykład Stos tac w sali jadalnej. Jest to w zasadzie, kiedy tylko zostały wprowadzone do komina ktoś powie: "O, jak stos tac". Można umieścić zasobników up. Potem, gdy idziesz do ściągania podajnika pierwszy podajnik wychodzi wyciągnął jest ostatnim, który został wprowadzony na stos. Stos także-jak to mówi tu mamy segment pamięci zwany stos. I dlaczego jest on nazywany stos? 

Bo jak struktury danych stosu, popycha i wyskakuje ramek stosu na stos, gdzie stosu ramki są jak określonego połączenia funkcji. I jak stos, zawsze będziesz musiał wrócić z wywołaniem funkcji, zanim będzie można dostać się do niższych ramek stosu ponownie. Nie można mieć główną wywołać bar wywołać foo bar i powrócić do głównej bezpośrednio. To zawsze musi przestrzegać poprawnej stos pchania i popping. Dwie operacje, jak powiedziałem, to push i pop. Są to uniwersalne warunki. Powinieneś wiedzieć, i połóż w kategoriach stosów nie wiem co. Zobaczymy, kolejki są trochę inne. To naprawdę nie ma uniwersalnego terminu, ale push i pop są uniwersalne dla stosów. Push jest po prostu umieścić na stosie. Pop jest zdjąć ze stosu. I widzimy tutaj mamy typedef struct stos, mamy więc ciągi char **. Nie daj się zastraszyć żadnej **. To będzie w końcu jest tablica łańcuchów lub tablica wskaźników do znaków, gdzie wskaźniki do znaków bywają ciągi. To nie musi być ciągi, ale tutaj, to będziemy w ciągi. 

Mamy tablicę ciągów. Mamy rozmiar, co oznacza, ile elementy są obecnie na stosie, a następnie mamy zdolność, która jest jak wiele elementów może być na stosie. Pojemność powinna rozpocząć jako coś większego niż 1, ale rozmiar ma zamiar rozpocząć w 0. Teraz są w zasadzie trzy sposoby można myśleć stosie. Cóż, jest prawdopodobnie więcej, ale są dwa sposoby można wdrożyć za pomocą tablicy, czy można wdrożyć przy użyciu połączonej listy. Połączone listy są rodzajem trywialny aby stosy od. Jest to bardzo łatwe do wykonania przy użyciu stosu połączonych list, więc, jedziemy do stosu przy użyciu tablic a następnie za pomocą tablic, tam również dwa sposoby, można o tym myśleć. Wcześniej, kiedy powiedział, że mamy zdolność do stosu, więc możemy dopasować element na stosie. 

Jeden sposób, to może się zdarzyć, to tak szybko, jak trafisz 10 elementy, a następnie gotowe. Być może wiesz, że istnieje górna granica 10 rzeczy na świecie że nigdy nie będziesz mieć więcej niż 10 rzeczy na stosie, w takim przypadku można mieć górną granicę wielkości twojego stacka. Albo możesz mieć swój stack jest nieograniczona, ale jeśli robisz tablicę, to oznacza, że ​​za każdym razem trafisz 10 elementów, wtedy będziesz miał wzrosnąć do 20 elementów, a gdy trafisz 20 elementów, będziesz musiał rozwijać swoją tablicę 30 elementów lub 40 elementów. Będziesz musiał zwiększyć pojemność, która jest, co mamy zamiar zrobić. Za każdym razem możemy osiągnąć maksymalny rozmiar naszego stosu kiedy wcisnąć coś jeszcze dalej, będziemy potrzebować, aby zwiększyć wydajność. Tutaj mamy zadeklarowane jako bool Push push (char * str). Char str * jest ciąg, że naciskają na stosie, i bool mówi tylko, czy nam się udało, czy nie. 

Jak nie? Co to jest tylko okoliczność, że można myśleć gdzie musimy wrócić fałsz? Tak. [Student] Jeśli jest pełna i używamy ograniczonego stosowania. Tak, więc jak można zdefiniować-odpowiedział jeśli jest to pełne i używamy ograniczoną realizację. Wtedy na pewno wrócimy false. Jak tylko trafiliśmy 10 rzeczy na tablicy, nie możemy zmieścić 11, więc return false. Co, jeśli to jest nieograniczona? Tak. Jeśli nie można rozwinąć tablicę z jakiegoś powodu. Tak, więc pamięć jest zasobem ograniczonym, iw końcu, jeśli mamy zachować rzeczy spychając na stosie w kółko, będziemy próbować i przydzielić większą tablicę, aby dopasować większa pojemność i malloc lub cokolwiek używamy będzie return false. Cóż, malloc zwróci null. 

Pamiętaj, że za każdym razem kiedyś zadzwonić malloc, powinno być sprawdzanie, czy zwraca NULL albo że jest odliczenie poprawności. Ponieważ chcemy mieć nieograniczony stos, Jedyny przypadek, będziemy się zwracać wartość false jest, jeśli staramy się zwiększenie zdolności i malloc lub cokolwiek zwraca false. Następnie pop przyjmuje żadnych argumentów, i zwraca łańcuch, który jest na górze stosu. Cokolwiek ostatnio na stos, co pop powraca, a także usuwa ze stosu. I zauważyć, że zwraca null, jeśli nie ma nic na stos. Jest zawsze możliwe, że stos jest pusty. W Javie, jeśli jesteś przyzwyczajony do tego, lub innych języków, próbuje wyskoczyć z pustego stosu może spowodować wyjątek, czy coś. 

Ale w C, null jest trochę dużo przypadków, w jaki sposób rozwiązania tych problemów. Wracając nieważne jest to, jak będziemy oznaczać, że stos jest pusty. Poniżej przedstawiamy kod, który będzie testować swój stosu funkcjonalność, wdrożenia wcisnąć i pop. To nie będzie dużo kodu. Będę-faktycznie, zanim to zrobimy, hint, hint- jeśli nie widziałeś, malloc nie jedyną funkcją jest która przydziela pamięć na stercie dla Ciebie. Istnieje rodzina funkcji Alloc. Pierwszy to malloc, która masz w zwyczaju. Potem jest calloc, który robi to samo, malloc, ale będzie zera wszystko dla ciebie. Jeśli kiedykolwiek chciał ustawić wszystko na null po mallocing coś nie powinno być używane tylko calloc na pierwszym miejscu zamiast pisać dla pętli do zera obecnie cały blok pamięci. 

Realloc jest jak malloc i ma wiele szczególnych przypadków, ale w zasadzie to, co robi, jest realloc zajmuje wskaźnik, które zostały już przydzielone. Realloc jest funkcja ma być zwrócenie uwagi na tutaj. To zajmuje wskaźnik, który już wrócił z malloc. Powiedzmy, że żądać od malloc wskaźnik z 10 bajtów. Potem zdajesz sobie sprawę, chciał 20 bajtów, więc zadzwonić realloc tego wskaźnika z 20 bajtów, i realloc automatycznie kopiować wszystko dla Ciebie. Jeśli po prostu nazywa malloc ponownie, tak jak ja masz bloku 10 bajtów. Teraz potrzebuję bloku 20 bajtów, więc jeśli malloc 20 bajtów, następnie trzeba ręcznie skopiować w ciągu 10 bajtów z pierwszych rzeczy, do drugiej rzeczy, a następnie wolne pierwsze. Realloc zajmie to za Ciebie. 

Wskazówka podpis będzie void *, który jest właśnie zwracając wskaźnik do bloku pamięci, Następnie void * ptr. Można myśleć o void * jako ogólny wskaźnik. Ogólnie rzecz biorąc, nie mamy do czynienia z void *, ale malloc zwraca void *, a potem to tylko używane jak To jest rzeczywiście będzie char *. Poprzedni void *, który został zwrócony przez malloc teraz będą przekazywane do realloc, a następnie rozmiar to nowa liczba bajtów, które chcesz przeznaczyć, tak więc nowe zdolności. Dam ci kilka minut, i robią to w naszej przestrzeni. Start z wersji 1. Wpadnę po ciebie o wystarczająco dużo czasu, mam nadzieję, że w celu realizacji Push, a potem dam ci kolejną przerwę zrobić pop. Ale to naprawdę nie jest dużo kodu jest w ogóle. Większość kodu jest prawdopodobnie rzeczy rozwija, rozszerzając możliwości. Dobra, nie ma ciśnienia być całkowicie wykonane, ale tak długo, jak czujesz, że jesteś na dobrej drodze, to jest dobre. 

Czy ktoś ma jakiś kod, oni czują się komfortowo ze mną ciągnie się? Tak, tak, ale czy ktoś ma żadnego kodu można podciągnąć? Ok, można uruchomić, zapisać go, co to jest? Zawsze zapominam, że krok. Ok, patrząc na dostarczaniu, chcesz wyjaśnić swój kod? [Tablica] pierwsze, że zwiększenie wielkości. Myślę, że może powinienem, że-tak, zwiększyłem rozmiar, i sprawdzić, czy jest mniejsza niż pojemność. A jeśli jest to mniej niż pojemność, dodać do tablicy, które już masz. A jeśli tak nie jest, pomnożyć możliwości przez 2, i realokacji tablicy ciągów do czegoś z większym rozmiarze zdolności teraz. A jeśli to się nie powiedzie, to poinformować użytkownika i zwraca fałsz, a jeśli to jest w porządku, to mogę umieścić napis w nowym miejscu. 

[Rob B.] Również zauważyć, że użyliśmy ładny operatory bitowe tutaj pomnożyć przez 2. Pamiętaj, lewy shift zawsze będzie mnożona przez 2. Prawy shift jest dzielona przez 2, tak długo, jak to możliwe, że oznacza to podzielić przez 2, jak w całkowitej podzielona przez 2. Może obciąć 1 tu czy tam. Ale przesunięcie w lewo o 1 zawsze będzie pomnożyć przez 2, chyba przepełnienie granice liczby całkowitej, a potem nie będzie. Komentarz z boku. Lubię robić, to nie będzie do zmiany kodu jakikolwiek sposób, ale podoba mi się zrobić coś takiego. To rzeczywiście będzie zrobić to nieco dłużej. Może to nie przypadek, aby pokazać doskonały to jest, ale lubię go w segmencie tych bloków- dobrze, jeśli to, jeśli się stanie, to mam zamiar zrobić coś, i funkcja jest wykonywana. I nie trzeba wtedy przewijać moje oczy w dół funkcji aby zobaczyć, co dzieje się po innym. To, czy to jeśli się zdarzy, po prostu wrócić. Ma też ładne dodatkowe korzyści poza tym wszystko obecnie przesunięta w lewo raz. I nie trzeba już-jeśli kiedykolwiek blisko absurdalnie długie linie, to te 4 bajty może pomóc, a także bardziej na lewo coś jest, mniej przytłoczeni czujesz, jeśli lubisz-w porządku, muszę zapamiętać Jestem obecnie w pętli wewnątrz z innego wewnątrz pętli for. Wszędzie można to zrobić natychmiast, I trochę jak. Jest to całkowicie opcjonalne i nie przewiduje się w żaden sposób. 

[Student] Czy należy rozmiar - w stanie, nie uda? Stan fail tu nie udało się nam realloc, więc tak. Zauważ, jak w stanie negatywnej, prawdopodobnie, chyba, że ​​darmowe rzeczy później, jesteśmy zawsze zawiedzie bez względu na to, ile razy próbujemy wcisnąć coś. Jeśli będziemy przeć, wciąż zwiększający rozmiary, mimo że nie stawiają nic na stos. Zazwyczaj nie zwiększamy wielkość aż po tym, jak udało się umieścić go na stosie. Chcemy to zrobić, powiedzieć, czy tu i tu. I wtedy zamiast powiedzieć s.size pojemności ≤, to mniej niż zdolności, tylko dlatego, że przeniósł się gdzie wszystko było. 

I pamiętaj, że jedynym miejscem, które moglibyśmy return false jest tutaj, gdzie realloc zwróciło null, i jeśli zdarzy się zapamiętać błąd standardowy, może warto rozważyć tę sprawę, w której chcesz wydrukować błąd standardowy, tak fprintf stderr zamiast drukowania bezpośrednio wyjście standardowe. Znowu, nie oczekuje się, ale jeśli jest to błąd, wpisz printf, to może chcesz, aby drukować na standardowe wyjście błędów, zamiast standardowego out. 

Ktoś ma coś jeszcze do uwagi? Tak. [Student] można przejść nad [niesłyszalny]? [Rob B.] Tak, rzeczywisty binariness z niego lub po prostu co to jest? [Student] Więc go pomnożyć przez 2? [Rob B.] Tak, w zasadzie. Binarnie ziemi, zawsze mamy nasz zestaw cyfr. Przesunięcie tego Wystawione przez 1 zasadzie wstawia go tutaj z prawej strony. Powrót do tego, po prostu pamiętać, że wszystko w formacie binarnym jest potęgą 2, więc to oznacza 2 do 0, Ten 2 do 1, w tym 2 do 2. Wstawiając 0 po prawej stronie teraz, po prostu przenieść wszystko od nowa. Co było do 0 2 jest teraz 2 do 1, jest 2 do 2. Po prawej stronie, że włożona jest koniecznie będzie 0, co ma sens. Jeśli kiedykolwiek pomnożyć liczbę przez 2, to nie skończy się dziwnie, więc 2 do 0 miejsce należy 0, i to jest to, co pół ostrzegał przed jest, jeśli się zdarzają, aby przesunąć poza liczbę bitów w liczby całkowitej, to ten 1 ma zamiar skończyć się wyłączyć. To jedyne zmartwienie jeśli zdarzy ci się mieć do czynienia z naprawdę dużych możliwościach. Ale w tym momencie, to masz do czynienia z tablicą miliardy rzeczy, które mogą nie pasować do pamięci tak. 

Teraz możemy przejść do muzyki pop, która jest jeszcze łatwiejsze. Można zrobić to tak, jeśli zdarzy ci się pop całą masę, a teraz jesteś na pół mocy ponownie. Można realloc aby zmniejszyć ilość pamięci masz, ale nie trzeba się martwić o to, więc tylko przypadek realloc będzie rośnie pamięć, nigdy kurczy pamięci co zamierza zrobić pop bardzo proste. Teraz kolejek, które będzie jak stosy, ale kolejność, że masz trochę rzeczy jest odwrócony. Prototypowy przykład kolejce jest linia, więc myślę, że gdybyś był angielski, to bym powiedział, prototypowy przykład kolejki jest kolejka. Tak jak w wierszu, jeśli jesteś pierwszą osobą w kolejce, można oczekiwać, aby być pierwszą osobą, z linii. Jeśli jesteś ostatnią osobą w linii, będą ostatnią osobą do serwisu. Nazywamy to wzór FIFO, natomiast stosu był wzór LIFO. Te słowa są dość powszechne. 

Podobnie jak stosy iw przeciwieństwie do tablic, kolejki zazwyczaj nie zezwala na dostęp do elementów w środku. Tutaj, stos, mamy push i pop. Tu stało się ich powołałem Kolejkuj i usunie. Słyszałem także je nazywa shift i unshift. Słyszałem, że ludzie mówią push i pop się również do kolejek. Słyszałem, wstawianie, usuwanie, tak naciskać i pop, jeśli mówisz o stosach, jesteś pchania i popping. Jeśli mówisz o kolejkach, można odebrać słowa chcesz użyć do wstawiania i usuwania, a nie ma zgody na to, co powinno być tzw. Ale tutaj mamy Kolejkuj i usunie. Teraz, struct wygląda niemal identycznie jak struct stosu. Ale musimy śledzić głowy. Myślę, że mówi się tu, ale po co nam głowę? Prototypy są zasadniczo identyczne z push i pop. Można myśleć o tym, jak naciśnięcie i popu. Jedyną różnicą jest to, pop powraca zamiast ostatniego, to pierwszy powrót. 2, 1, 3, 4, lub coś. I tutaj jest początek. Nasza kolejka jest pełny, więc nie ma w niej cztery elementy. Koniec naszej kolejki jest obecnie 2, a teraz idziemy na wstawić coś innego. 

Kiedy chcemy wstawić, że coś innego, co zrobiliśmy dla wersji stosu jest, że przedłużyliśmy nasz blok pamięci. Jaki jest problem z tym? [Student] 2 przesuwa się. Co powiedziałem wcześniej o końcu kolejki, to nie ma sensu, że zaczynamy od 1, to chcemy Dequeue 1, następnie Dequeue 3, następnie Dequeue 4, następnie Dequeue 2, a następnie usunie z niej ten. Nie możemy użyć realloc teraz lub co najmniej, trzeba użyć realloc w inny sposób. Ale pewnie nie tylko funkcję realloc. Będziesz musiał ręcznie skopiować pamięć. 

Znajdują się dwie funkcje, aby skopiować pamięć. Jest memcopy i memmove. Jestem obecnie czytania stron podręcznika, aby zobaczyć, który z nich masz zamiar użyć. Okay, memcopy, różnica jest że memcopy i memmove, jeden obsługuje sprawę prawidłowo gdzie jesteś kopiowania do regionu, który dzieje się pokrywają region jesteś kopiowaniu. Memcopy nie poradzę. Memmove robi. Można myśleć o problemie, jak- powiedzmy, że chcesz skopiować tego faceta, te cztery do tego faceta. W końcu, co tablica powinna wyglądać kopia jest po 2, 1, 2, 1, 3, 4, a następnie kilka rzeczy na końcu. Ale to zależy od kolejności, w jakiej rzeczywiście kopiować, ponieważ, jeśli nie brać pod uwagę fakt, że w regionie mamy do kopiowania zachodzi jeden mamy kopiowaniu, to może zrobimy tak jak początek tutaj, skopiować 2 na miejsce chcemy się udać, następnie przenieść nasze wskazówki do przodu. 

Teraz będziemy się tutaj i tutaj, a teraz chcemy skopiować ten facet to facet i przenieść nasze wskazówki do przodu. Co zamierzamy skończyć się to 2, 1, 2, 1, 2, 1 zamiast odpowiedniego 2, 1, 2, 1, 3, 4, ponieważ 2, 1 overrode oryginalny 3, 4. Memmove uchwyty, które w pełnym zakresie. W tym przypadku, w zasadzie tylko zawsze używać memmove bo obsługuje go prawidłowo. Generalnie nie należy wykonywać żadnych gorzej. Chodzi o to, a nie od początku i w ten sposób kopiowania tak jak my po prostu nie tutaj, to zaczyna się od końca i kopiuje w, iw tym przypadku, nigdy nie można mieć problem. Nie ma wydajność utracone. Zawsze używaj memmove. Nie martw się o memcopy. I to, gdzie będziesz musiał osobno memmove owinięty wokół część kolejce. Nie martw się, jeśli nie całkowicie wykonane. To jest trudniejsze niż stosu, push i pop. 

Ktoś ma jakiś kod, możemy współpracować? Nawet jeśli zupełnie niekompletne? [Student] Tak, to jest całkowicie niekompletna, choć. Kompletnie niekompletny jest w porządku tak długo, jak my-można zapisać zmiany? I zapomnieć, że za każdym razem. Okay, ignorując, co się dzieje, kiedy trzeba zmienić rozmiar rzeczy. Całkowicie ignorować resize. Wyjaśnij ten kod. Ja kontroli pierwsze Jeżeli rozmiar jest mniejszy niż na wstępie kopii a następnie po tym, wstawić-biorę głowę + rozmiar, i upewnić się, że otacza pojemności macierzy, i wstawić nowy ciąg w tej pozycji. Następnie zwiększyć rozmiar i zwróci true. 

[Rob B.] Jest to zdecydowanie jeden z tych przypadków, w których masz zamiar chcesz używać mod. Każdy rodzaj wypadku, w którym został owijania wokół, jeśli uważasz, owijając się dookoła, natychmiastowa myśl powinna być mod. W szybkiej optymalizacji / make kod jeden wiersz krótszy, można zauważyć, że linia bezpośrednio po ten jeden jest to tylko rozmiar + +, więc scalić, że do tej linii, wielkość + +. Teraz tu mamy przypadek gdzie nie ma wystarczającej ilości pamięci, więc podnosimy naszą zdolność przy 2. Myślę, że można mieć ten sam problem, ale można ignorować to teraz, gdzie jeśli nie udało się zwiększyć pojemność, następnie będziesz chciał zmniejszyć moc o 2 ponownie. Kolejna krótka notatka jest jak można zrobić + =, można też zrobić << =. Prawie wszystko może iść przed równymi, + =, | =, & =, << =. Char * nowy jest nasz nowy blok pamięci. O, tutaj. 

Co ludzie myślą o rodzaju naszego nowego bloku pamięci? [Student] Powinno być char **. Wracając do naszej struktury tu, strings jest co mamy realokacji. Wykonujemy cały nowy dynamiczny przechowywania elementów w kolejce. Co mamy zamiar być przypisanie do stringów jest co mamy mallocing teraz, a więc nowy będzie char **. To będzie tablica łańcuchów. Więc co jest w przypadku, w których mamy zamiar wrócić fałsz? [Student] powinniśmy robić char *? [Rob B.] Tak, dobre połączenie. [Student] Co to było? [Rob B.] Chcieliśmy zrobić rozmiar char *, ponieważ nie jesteśmy już- to byłby rzeczywiście bardzo duży problem, ponieważ sizeof (char) będzie 1. Sizeof char * będzie 4, tak wiele razy, gdy masz do czynienia z wskazówki, masz tendencję do uciec z nim, ponieważ wielkość i rozmiar int int * na systemie 32-bitowym będą samo. Ale tutaj, sizeof (char) i sizeof (char *) są teraz będzie tak samo. 

Co to jest sytuację, w której zwracamy fałsz? [Student] Nowy jest null. Tak, jeśli nowy jest null, zwracamy false, i mam zamiar rzucić tu [Student] [niesłyszalne] [Rob B.] Tak, to jest w porządku. Można albo zrobić 2 razy pojemność lub Shift pojemności 1 i tylko ustawić go tutaj lub cokolwiek. Zrobimy to jak miał. Pojemność >> = 1. I nigdy nie będziesz musiał martwić się o utratę tego 1 w miejsce bo zostawili przesunięty o 1, więc 1 na miejsce koniecznie 0, więc prawo przesunięcia o 1, to wciąż będzie dobrze. [Student] Czy trzeba to zrobić przed powrotem? [Rob B.] Tak, to sprawia, że ​​absolutnie nie ma sensu. 

Załóżmy teraz zamierzamy skończyć powrotem prawda do końca. Sposób będziemy robić te memmoves, Musimy być ostrożni z tym, jak je zrobić. Czy ktoś ma jakieś sugestie, jak my ich? Oto nasz start. Nieuchronnie, chcemy rozpocząć na początku ponownie i rzeczy, kopia w stamtąd, 1, 3, 4, 2. Jak to zrobić? Po pierwsze, muszę patrzeć na stronie podręcznika memmove ponownie. Memmove, kolejność argumentów jest zawsze ważne. Chcemy, aby nasze miejsce pierwsze, drugie źródło, trzeci wymiar. Istnieje wiele funkcji, które w odwrotnej źródło i cel. Cel podróży, źródło wydaje się być spójne nieco. Move, co to jest powrót? Zwraca wskaźnik do miejsca przeznaczenia, niezależnie od przyczyny, że warto. Mogę zdjęcie czytać, ale chcemy, aby przenieść się do naszego celu. 

Co jest naszym celem będzie? [Student] Nowy. [Rob B.] Tak, a gdzie jesteśmy kopiowania z? Pierwszą rzeczą, którą kopiujesz to 1, 3, 4. To, co jest w tym-1, 3, 4. Jaki jest adres tej 1? Jaki jest adres tej 1? [Student] [niesłyszalne] [Rob B.] Head + adres pierwszego elementu. Jak dostajemy pierwszy element tablicy? [Student] Queue. [Rob B.] Tak, q.strings. Pamiętaj, że tu nasza głowa jest 1. Cholernie go. Po prostu myślę, że to magicznie Oto nasza głowa jest 1. Zamierzam zmienić kolor też. I tu jest łańcuchami. To, możemy albo napisać go tak jak my tutaj z głowy + q.strings. Wiele osób również napisać go i q.strings [głowa]. To nie jest ani trochę mniej wydajny. Można by pomyśleć o tym, jak są dereferencji go, a następnie uzyskiwanie adresu, ale kompilator będzie przetłumaczyć go do tego, co mieliśmy przed tak, q.strings + głowica. Albo tak, jak chcesz myśleć. 

I ile bajtów chcemy skopiować? [Student] Pojemność - głowa. Pojemność - głowa. A potem zawsze można napisać przykład dowiedzieć się, czy to prawda. [Student] To musi być podzielona przez 2 wtedy. Tak, więc myślę, że możemy użyć rozmiaru. Mamy jeszcze rozmiar bycia- przy wielkości, mamy wielkość równą 4. Nasz rozmiar to 4. Nasza głowa jest 1. Chcemy skopiować te 3 elementy. To rozsądek sprawdzić czy rozmiar - głowica jest prawidłowo 3. I tu wracać, jak powiedziałem wcześniej, gdybyśmy zdolności, wtedy musielibyśmy podzielić przez 2 bo już uprawiane nasze możliwości, więc zamiast tego, mamy zamiar wykorzystać rozmiar. Że egzemplarze tej części. Teraz musimy skopiować drugą część, część, która jest na lewo od początku. 

Że zamierza memmove w jakiej pozycji? [Student] Rozmiar Plus - głowa. Tak, tak, mamy już skopiowane w wielkości - bajty głowy, a więc tam, gdzie chcemy, aby skopiować bajtów pozostałych jest nowy a następnie rozmiar minus-dobrze, liczba bajtów mamy już skopiowane w. A potem dokąd kopiowania z? [Student] Q.strings [0]. [Rob B.] Tak, q.strings. Mogliśmy albo zrobić i q.strings [0]. Jest to znacznie mniej, niż ten często. Jeśli jest to tylko będzie 0, wtedy postrzegają q.strings. To gdzie mamy kopiowanie z. Ile bajtów nam zostało skopiować? >> [Student] 10. Racja. [Student] Czy musimy pomnożyć 5 - 10 razy wielkość bajtów lub coś? Tak, tak, to gdzie-co dokładnie mamy kopiowanie? [Student] [niesłyszalne] Jaki jest rodzaj rzeczy mamy do kopiowania? [Student] [niesłyszalne] Tak, tak, char * s, że jesteśmy kopiowania, nie wiemy, gdzie te pochodzą. No, gdzie oni wskazując, jak struny, to w końcu popychając ją na kolejkę lub enqueuing na kolejki. Gdzie te pochodzą, nie mamy pojęcia. Musimy tylko śledzić char * s sami. Nie chcemy skopiować rozmiar - bajtów głowy. Chcemy skopiować rozmiar - głowica char * s, więc mamy zamiar pomnożyć to przez sizeof (* char). Sam tu, głowa * sizeof (char *). 

[Student] Co o [niesłyszalne]? To właśnie tutaj? [Student] Nie, poniżej, że rozmiar - głowa. [Rob B.] To tutaj? Arytmetyczna wskaźnika. Jak arytmetyka wskaźnik idzie do pracy jest automatycznie mnoży przez rozmiar typu, że mamy do czynienia. Tak jak tutaj, nowy + (rozmiar - głowica) jest dokładnie odpowiednikiem & New [size - Head] aż oczekujemy, że działa poprawnie, ponieważ jeśli mamy do czynienia z int tablicy, to nie robimy indeksu przez int- lub jeśli jest to od wielkości 5 i chcesz 4-ej, to indeks do int tablica [4]. Ci nie-[4] * rozmiar wew. Że obsługuje go automatycznie, a tym przypadku jest dosłownie odpowiednik, więc składnia wspornik jest po prostu się być konwertowane do tego tak szybko, jak skompilować. To jest coś, co musisz uważać, że podczas dodawania rozmiar - głowica dodawania nie jeden bajt. Jesteś dodanie jednego char *, który może być jedno bajtów lub cokolwiek. 

Inne pytania? Okay, Dequeue będzie łatwiejsze. Dam ci chwilę na wdrożenie. Aha, i myślę, że to jest ta sama sytuacja, gdy co enqueue przypadku, jeśli mamy enqueuing null, Może chcemy poradzić, może nie. Nie będzie to jeszcze raz tutaj, ale sam, jak naszym przypadku stosu. Jeśli enqueue null, możemy chcieć go zignorować. Ktoś ma jakiś kod można podciągnąć? [Student] Mam tylko z kolejki. Wersja 2 jest to, że-w porządku. Chcesz wyjaśnić? [Student] Po pierwsze, upewnij się, że jest coś w kolejce Rozmiar i spada do 1. Musisz to zrobić, a następnie powrót głowę a następnie przesuń głowę 1. Okay, więc nie jest to przypadek rogu mamy do rozważenia. Tak. [Student] Jeśli Twoja głowa jest na ostatnim elemencie potem nie chcesz głowa wskazać poza tablicę. 

Tak, więc jak tylko głową uderza koniec naszej tablicy, gdy z kolejki, nasza głowa powinna być modded powrotem do 0. Niestety, nie możemy tego zrobić w jednym kroku. Chyba tak pewnie to naprawić to będzie char *, co mamy powrót, niezależnie od nazwy zmiennej chce być. Następnie chcemy mod przez głowę naszej zdolności a następnie powrócić ret. Wiele osób tutaj mogą do- jest to przypadek-Zobaczysz zrobić osoby, głowa jest większa od mocy, czy głowę - pojemność. A to tylko pracy wokół tego, co mod jest. Szef mod pojemność = jest znacznie czystsze z owijania wokół niż gdyby głowa większa od głowy pojemności - pojemność. 

Pytania? Okay, ostatnią rzeczą, zostawiliśmy to naszej listy. Może zostać użyty do niektórych zachowań połączonej listy jeśli nie powiązany list w swoim hash tabel, jeśli nie tabeli mieszania. Gorąco polecam ten hash tabeli. Mogłeś już szereg Trie, ale stara się trudniejsze. W teorii, są asymptotycznie lepiej. Ale wystarczy spojrzeć na wielkim statku, i stara się nie robić lepiej i zajmują więcej pamięci. Wszystko o stara kończy się gorzej więcej pracy. To właśnie rozwiązanie Davida Malan zawsze jest jest on zawsze swoje posty trie rozwiązanie, i zobaczymy, gdzie obecnie jest. Co miał mocy, David J? On jest # 18, tak że nie jest strasznie zły, i że będzie to jeden z najlepszych stara można myśleć lub jedna z najlepszym z Trie próbuje. Czy to nie jest nawet jego oryginalne rozwiązanie? Czuję trie rozwiązania są bardziej w tym zakresie zastosowania RAM. 

Idź w dół do samej góry, a zużycie RAM jest w jednej cyfry. Przejdź w dół w kierunku dna, a następnie zaczniesz widzieć próbuje gdzie można uzyskać absolutnie ogromne zużycie pamięci RAM, i próbuje się trudniejsze. Nie całkowicie warto ale doświadczenie edukacyjnych jeśli nie jeden. Ostatnią rzeczą jest naszą listę, i te trzy rzeczy, stosy, kolejki, listy, a także połączone każda kolejna rzecz, którą kiedykolwiek zrobić w informatyce zakłada, że ​​posiadamy znajomość tych rzeczy. Są po prostu tak podstawą wszystkiego. 

Linked list, a tu mamy pojedynczo połączonej listy będzie nasza realizacja. Co to znaczy, pojedynczo połączone w przeciwieństwie do podwójnie powiązane? Tak. [Student] To tylko wskazuje na kolejny wskaźnik, a nie do wskaźników, jak ten, przed nim i po nim jeden. Tak, więc w formie graficznej, co ja zrobiłem? Mam dwie rzeczy. Mam obraz i obraz. W formacie obrazu, nasze pojedynczo połączone listy, nieuchronnie, mamy jakiś wskaźnik na czele naszej listy, a następnie w naszej liście, musimy tylko wskaźniki, a może to wskazuje na null. To będzie typowy rysunek pojedynczo liście powiązane. Podwójnie połączonej listy można przejść do tyłu. Jeśli wezmę dowolny węzeł na liście, a następnie można zawsze dostać się do innego węzła w, jeżeli jest to listy dwukierunkowe. Ale gdybym ci trzeci węzeł z listy i to pojedynczo połączonej listy, żaden sposób nie jesteś kiedykolwiek dostanie do węzłów pierwszym i drugim. I nie ma korzyści i detriments i jeden oczywisty jest Ci zajmują więcej rozmiar, i trzeba śledzić, gdzie te rzeczy są wskazując teraz. Ale interesują nas tylko pojedynczo połączone. 

Kilka rzeczy, które będziemy mieć do wdrożenia. Twoja typedef struct node, int i: struct node * next; węzeł. To typedef powinien być spalany w waszych umysłach. Quiz 1 powinno być jak dać typedef z węzła połączonej listy i powinieneś być w stanie natychmiast bazgroły, że w dół nawet nie myśląc o tym. Chyba kilka pytań, dlaczego musimy struct tutaj? Dlaczego nie możemy powiedzieć węzła *? [Student] [niesłyszalne] Tak. Jedyną rzeczą, która określa węzeł jako rzecz jest typedef sama. Ale od tego momentu, gdy jesteśmy rodzaju analizowania przez tą definicją węzła struct, nie skończyliśmy nasz typedef jeszcze, więc od typedef nie zostało zakończone, Węzeł nie istnieje. Ale struct node robi, a ten węzeł w tutaj, może to być również nazywane niczego innego. To może być nazywany N. Może być ona wywołana linked węzeł lista. Może być ona wywołana nic. Ale ten węzeł struct musi być wywoływana to samo, co ten węzeł struktury. To, co nazywasz to musi być również tutaj, również i tak, że drugi punkt odpowiedzi na pytanie dlatego-Wiele razy, gdy widzisz structury i typedef w elemencie, zobaczysz anonimowych przypisać struktury, gdzie można po prostu zobaczyć typedef struct, Realizacja struct, słownik, czy cokolwiek innego. 

Dlaczego tutaj nie trzeba powiedzieć węzeł? Dlaczego nie może być anonimowy struct? To prawie taka sama odpowiedź. [Student] Musisz odwołać się do niej w ramach struktury. Tak, w ramach struktury, trzeba odwołać się do samej struktury. Jeśli nie da struct nazwę, jeśli jest anonimowy struct, nie można odwoływać się do niego. I last but not least one powinny być w całości nieco proste, i powinny pomóc osiągnąć jeśli piszesz to w dół że robisz coś źle, jeśli tego rodzaju rzeczy nie mają sensu. Last but not least, dlaczego to ma być * węzeł struct? Dlaczego nie może być po prostu struct węzeł następny? [Student] Wskaźnik do następnej struktury. To nieuniknione, co chcemy. Dlaczego nigdy nie mógł to być węzeł struct następny? Dlaczego to musi być struct node * next? Tak. [Student] To jak nieskończoną pętlę. Tak. [Student] To wszystko będzie w jednym. Tak, tylko, że jak zrobimy rozmiaru czy coś. Rozmiar struktury jest zasadniczo + lub - niektóre wzór tu czy tam. Jest to w zasadzie będzie to suma wielkości rzeczy w struktury. To właśnie tutaj, nie zmieniając niczego, rozmiar będzie łatwe. Wielkość węzła struct będzie rozmiar I Standard + z następnym. Wielkość I będzie 4. Rozmiar następnego będzie 4. Wielkość węzła struct będzie 8. Jeśli nie ma *, myśląc o sizeof, następnie sizeof (i) będzie 4. Wielkość węzła struct następny będzie rozmiar I Standard + węzła struct kolejnego Rozmiar + z I Standard + struct kolejnego węzła. Byłoby nieskończonej rekurencji węzłów. Dlatego to jest to, jak rzeczy mają być. 

Ponownie, zdecydowanie zapamiętać, że lub przynajmniej zrozumieć tyle, że możesz być w stanie Powodem przez co powinno wyglądać. Rzeczy, które zamierzamy chcą wprowadzić. Jeśli długość listy- można oszukać i zachować wokół globalny długość czy coś, ale nie będziemy tego robić. Będziemy liczyć długość listy. Mamy zawiera, tak, że w zasadzie jak wyszukiwanie, więc mamy związane listę liczb całkowitych, aby sprawdzić czy całkowita jest w połączonej listy. PREPEND będzie wprowadzić na początku na liście. Append będzie wstawić na końcu. Insert_sorted będzie wstawić do sortowanie pozycji na liście. Insert_sorted rodzaju zakłada się, że nigdy nie używane prepend lub dołączyć w złych sposobów. 

Insert_sorted kiedy wdrożenie insert_sorted- powiedzmy mamy naszej listy. To jest to, co obecnie wygląda, 2, 4, 5. Chcę wkładki 3, tak długo, jak długo jest już sama lista posortowane łatwo jest znaleźć gdzie 3 należy. I zaczynają się od 2. Okay, 3 jest większa niż 2, więc chcę iść dalej. Oh, 4 jest zbyt duży, więc wiem, 3 będzie przejść między 2 i 4, i muszę naprawić wskaźniki i wszystkie rzeczy. Ale jeśli nie będziemy ściśle stosować insert_sorted, jak powiedzmy I dołączy 6, wtedy moja linked lista będzie coraz to. Teraz nie ma sensu, więc dla insert_sorted, można po prostu założyć, że lista jest sortowana, choć istnieją operacje co może spowodować, że nie mają być sortowane, i to jest to. Znajdź przydatne insert-tak to główne rzeczy, które będziemy mieć do wdrożenia. 

Na razie, poświęć chwilę uwagi długości i zawiera, i te powinny być stosunkowo szybkie. Zbliża czasu zamknięcia, więc ktoś ma coś na długość lub zawiera? Będą się być niemal identyczne. [Student] Długość. Zobaczmy rewizji. Okay. Chcesz wyjaśnić? [Student] po prostu utworzyć węzeł wskaźnik i zainicjować go do pierwszego, który jest naszym zmiennej globalnej, , a potem sprawdzić, czy to jest zerowy, więc nie dostać SEG usterkę i zwraca 0, jeśli tak jest. W przeciwnym razie, w pętli, śledzenie terminie całkowitą ile razy mam dostęp do następnego elementu listy i w tej samej operacji, również dostęp do przyrostu, że rzeczywista elementu a ja ciągle się sprawdzić, czy to jest null, i jeśli jest pusta, to przerywa i po prostu zwraca liczbę elementów mam dostęp. 

[Rob B.] Czy ktoś ma jakieś uwagi na temat czegokolwiek? To wygląda dobrze poprawności mądry. [Student] Nie sądzę, trzeba węzeł == null. Tak, więc jeśli węzeł == null 0 powrotu. Ale jeśli node == null to ta-oh, jest kwestia poprawności. To było po prostu jesteś powrotu i, ale to nie jest w zakresie teraz. Trzeba tylko int i, tak i = 0. Ale jeśli węzeł jest pusta, to i nadal będzie 0, i zamierzamy wrócić 0, więc ta sprawa jest identyczna. Inną powszechną rzeczą jest przechowywanie deklaracji z wewnątrz węzła pętli for. Można powiedzieć, oh, no. Trzymajmy to jak ta. Prawdopodobnie umieścić int i = 0 tutaj następnie węzeł * node = pierwszy tutaj. I to jest chyba jak-pozbyć się tego teraz. Prawdopodobnie jest to w jaki sposób to napisałem. Można również, patrząc na to w ten sposób. To dla struktury pętli tutaj powinny być prawie tak naturalne dla ciebie jak dla int i = 0 i jest mniejsza niż długość tablicy I + +. Jeżeli tak jest, w jaki sposób iteracyjne nad tablicy, jest to, w jaki sposób iteracyjne nad połączonej listy. 

To powinno być drugą naturą w pewnym momencie. Mając to na uwadze, to będzie prawie to samo. Będziesz chcą iterować połączonej listy. Jeśli węzeł-nie mam pojęcia, jaka jest wartość jest wywoływana. Gałąź i. Jeśli wartość w tym węźle = i zwraca true, i to jest to. Zauważ, że jedynym sposobem kiedykolwiek wrócimy false jest jeśli iterować całej listy połączonej i nigdy nie wracać prawda więc to co to robi. Jako side note-prawdopodobnie nie będzie dostać się do dołączania lub dołączy. 

Szybkie ostatnia uwaga. Jeśli widzisz słowa kluczowego static, więc powiedzmy, że static int count = 0, potem liczą + +, można w zasadzie myśleć o nim jako zmiennej globalnej, chociaż właśnie powiedziałem to nie jest to, jak będziemy realizować długość. Robię to tutaj, a następnie liczyć + +. Każdy sposób możemy wprowadzić do naszego węzła połączonej listy jesteśmy zwiększający nasz licznik. Punktem jest to, co statyczne keyword oznacza. Gdybym tylko miał int count = 0 byłoby regularne stary zmienną globalną. Oznacza to, co statyczne int Ilość jest, że jest to w tym zmienna globalna pliku. To jest możliwe w innym pliku, lubię myśleć Pset 5, jeśli już się rozpoczęły. Masz zarówno speller.c i masz dictionary.c, a jeśli po prostu zadeklarować coś globalnego, a następnie coś w speller.c mogą być dostępne w dictionary.c i odwrotnie. Zmienne globalne są dostępne dla każdego pliku. C, ale zmienne statyczne są dostępne tylko w ramach samego pliku, tak wewnątrz sprawdzania pisowni lub wewnątrz dictionary.c, jest to rodzaj jak ja deklaruję zmienną do rozmiaru mojego tablicy lub wielkości mojej liczby słów w słowniku. Ponieważ nie chcę, aby zadeklarować zmienną globalną, że każdy ma dostęp do I tak naprawdę tylko dbam o to dla własnych celów. 

Dobrą rzeczą jest to również cały stuff kolizji nazw. Jeśli inny plik próbuje użyć zmiennej globalnej o nazwie count, sprawy idą bardzo, bardzo źle, tak to ładnie utrzymuje rzeczy bezpieczne, a tylko można do niego dostęp, i nikt inny nie może, a jeśli ktoś deklaruje zmienną globalną o nazwie count, to nie będzie przeszkadzać w zmiennej statycznej o nazwie count. To, co jest statyczne. Jest to plik zmienną globalną. 

Pytania na cokolwiek? Wszystko gotowe. Bye. [CS50.TV]