[Powered by Google Translate] [Rozdział 6: Mniej Comfortable] [Nate Hardison] [Harvard University] [To jest CS50.] [CS50.TV] Dobrze. Witamy w dziale 6. W tym tygodniu będziemy mówić o strukturach danych w przekroju, głównie dlatego, że w tym tygodniu problemu ustawić na spellr robi cała masa różnych struktury danych eksploracji. Istnieje kilka różnych sposobów, można przejść do zestawu problemów, i więcej struktur danych znasz, tym więcej fajnych rzeczy można zrobić. 

Więc zaczynajmy. Najpierw będziemy rozmawiać o stosy, stosu i kolejki struktury danych, że będziemy o tym mówić. Stosy i kolejki są naprawdę pomocne, gdy zaczynamy mówić o wykresach, którego nie będziemy robić tak dużo teraz. Ale oni są naprawdę dobrze zrozumieć jedną z wielkich podstawowych struktur danych CS. Opis w specyfikacji zestaw problemów, jeśli wyciągnij go, opowiada o stosach jako pokrewny stos tac gastronomicznych, że masz w stołówce w salach jadalnych gdzie, kiedy personel dining przychodzi i stawia zasobników stołować po ich czyścić je, one stosu je jeden na drugim. I wtedy, gdy dzieci są w celu zdobycia pożywienia, ciągną się zasobniki pierwszy góry jeden, a następnie jeden pod nią, a następnie jeden poniżej. Tak więc, w efekcie, pierwszy podajnik personel dining odłożyć jest ostatnim, który jest zdjęty. Ostatni, że personel dining wprowadzone jest pierwszą, która zostanie zdjęta na kolację. W zestawie problemu w specyfikacji, którą można pobrać, jeśli jeszcze go nie masz, mówimy o modelowanie stucture danych stosu przy użyciu tego rodzaju struktury. 

Więc co tu mamy, to jest podobne do tego, co zostało przedstawione w wykładzie wyjątkiem wykładu przedstawiliśmy to z liczb całkowitych, w przeciwieństwie do char * s. To będzie stos przechowujący co? Daniel? Co my przechowywania tego stosu? [Daniel] Strings? >> Jesteśmy przechowywania ciągów w tym stosie, dokładnie. Wszystko, co musisz mieć, aby utworzyć stos jest tablicą danego pojemności, które w tym przypadku, pojemność będzie wielkimi literami, ponieważ jest stała. , A następnie, w uzupełnieniu do tablicy wszystkie potrzebne śledzenie jest obecny rozmiar tablicy. Warto zauważyć tutaj, że to fajne jest to, że mamy do tworzenia struktury danych ułożone na szczycie innej struktury danych, tablicy. Istnieją różne sposoby, aby wdrożyć stosy. Nie zrobi to dość jeszcze, ale mam nadzieję, że po wykonaniu linkowane listy problemów zobaczysz, jak łatwo można zaimplementować stos na górze połączonej listy, jak również. Ale teraz będziemy trzymać się tych tablic. Więc jeszcze raz, wszystko, czego potrzebujesz to tablica i po prostu trzeba śledzić rozmiar tablicy. [Sam] Przepraszam, dlaczego jest tak, że pan powiedział, że stos jest na szczycie ciągów? Dla mnie wydaje się, że ciągi są w stos. [Hardison] Tak. Tworzymy bierzemy naszą strukturę danych do tablicy - to jest dobre pytanie. Więc pytanie jest, dlaczego, dla ludzi, którzy oglądają ten online, to dlaczego mówi się, że stos jest na szczycie strun, bo tu wygląda jak struny są wewnątrz stosu? Co jest zupełnie inaczej. Co miałem na myśli to, że mamy strukturę danych tablicy. Mamy tablicę char * s, to tablicę ciągów, i mamy zamiar dodać do tego, aby stworzyć ułożone struktury danych. 

Więc stos jest nieco bardziej skomplikowana niż tablicy. Możemy używać tablicy zbudować stos. Więc to, gdzie mówimy, że stos jest zbudowany na górze tablicy. Podobnie, jak powiedziałem wcześniej, możemy zbudować stos na górze połączonej listy. Zamiast używać tablicy do przechowywania naszych elementów, możemy użyć połączonej listy trzymać nasze elementy i zbudować stos wokół niego. Przejdźmy przez kilka przykładów, patrząc na niektóre kodu, zobaczyć, co się właściwie dzieje. Po lewej stronie, mam zwalony co to struct stos będzie wyglądać w pamięci jeśli pojemność zostały # definiuje się cztery. Mamy nasze cztery elementu tablicy char *. Mamy łańcuchy [0], smyczki [1], łańcuchy [2], nicie [3], , a następnie, że w zeszłym przestrzeń dla naszej całkowitej wielkości. Czy to ma sens? Okay. To jest to, co się stanie, jeśli to, co robię na prawo, który będzie mój kod, to po prostu stwierdzenie, struct, struct stos nazywane s. To jest to, co mamy. Ustanawia ona ten ślad w pamięci. Pierwsze pytanie o to, jakie są zawartość tej struktury stosu? Teraz są one niczym, ale nie są one zupełnie nic. Są tego rodzaju śmieci. Nie mamy pojęcia, co jest w nich. Kiedy deklarujemy s stosu, po prostu rzuca, że ​​w dół na szczycie pamięci. To trochę tak jak stwierdzenie, a nie int i inicjalizacji. Nie wiem, co jest w środku. Można przeczytać, co tam jest, ale to nie może być super pomocny. Jedną rzeczą, którą chcesz, aby zawsze pamiętać, aby zrobić to zainicjować cokolwiek musi być zainicjowany. W tym przypadku, mamy zamiar zainicjować rozmiar wynosi zero, dlatego, że zamierza okazać się dla nas bardzo ważne. Możemy pójść dalej i zainicjować wszystkie wskaźniki, wszystko char s *, być jakiś zrozumiały wartość, prawdopodobnie null. Ale to nie jest konieczne, że całkowicie to zrobić. 

Teraz, dwa główne operacje na stosach są? Ktoś pamięta z wykładu, co zrobić ze stosami? Tak? [Stella] Pushing i popping? >> Dokładnie. Pchanie i popping to dwa główne operacje na stosach. A co Push zrobić? >> To stawia coś na górze stosu, a następnie popping zdejmuje. [Hardison] Dokładnie. Więc popychanie pcha coś na górze stosu. To jak oddanie pracowników jadalni tacę jadalną na ladę. I popping bierze tacę jadalną off stosu. Przejdźmy przez kilka przykładów tego, co się dzieje kiedy wcisnąć rzeczy do stosu. Gdybyśmy mieli naciskać ciąg "Hello" na nasz stosu jest to, co nasz diagram będzie wyglądał tak jak teraz. Zobacz, co się dzieje? Mamy wepchnięty do pierwszego elementu naszej tablicy ciągów i podniósł naszą liczbę rozmiar będzie 1. Więc jeśli spojrzymy na różnicę między dwoma zjeżdżalniami, tutaj było 0, tu przed naciśnięciem. Tu jest po naciśnięciu. Przed naciśnięciem po push. A teraz mamy jeden element w naszej stosie. Jest to ciąg znaków "hello", a to jest to. Wszystko inne w tablicy, w naszej tablicy ciągów, nadal śmieci. Nie zainicjowany go. Powiedzmy, że wcisnąć inny ciąg na nasz stos. Będziemy naciskać "świat" w tym czasie. Więc widać, "świat" tu idzie na górze "hello", Ilość i rozmiar wzrasta do 2. Teraz możemy wcisnąć "CS50", i że pójdzie na wierzchu ponownie. Jeśli wrócimy, można zobaczyć, jak mamy popychanie rzeczy na wierzchu stosu. A teraz mamy do pop. Kiedy wpadliśmy coś z stosu, co się stało? Ktoś widzi różnicę? Jest to dość subtelne. [Student] rozmiar. >> Tak, zmienił się rozmiar. 

Co jeszcze spodziewać się zmienić? [Student] Łańcuchy, too. >> Racja. Łańcuchy też. Okazuje się, że kiedy robisz to w ten sposób, ponieważ nie jesteśmy kopiowanie elementów do naszego komina, tak naprawdę nie trzeba nic robić, możemy po prostu użyć rozmiaru śledzenie liczby rzeczy w naszej tablicy tak, że kiedy pojawi znowu, znowu po prostu zmniejszyć naszą wielkość w dół do 1. Nie ma potrzeby, aby faktycznie przejść i zastąpić wszystko. Trochę funky. Okazuje się, że zazwyczaj po prostu zostawić wszystko w spokoju, bo to mniej pracy dla nas zrobić. Jeśli nie mamy wrócić i zastąpić coś, to dlaczego to robisz? Kiedy więc pojawiają się dwa razy w stosie, to wszystko robi, to zmniejszamy rozmiar A kilka razy. I znowu, to tylko dlatego, że nie jesteśmy kopiowania rzeczy do naszego komina. Tak? Śmiało. [Student, niezrozumiały] >> I co wtedy się dzieje po naciśnięciu coś znowu? Po naciśnięciu coś znowu, gdzie to idzie? Dokąd ona, Basil? >> Into ciągów [1]? >> Racja. Dlaczego nie pójść na ciągi [3]? [Basil] Bo zapomniałem, że było coś w ciągach [1] i [2]? [Hardison] Dokładnie. Nasz stos zasadniczo, "zapomniał", że był trzymając się niczego w ciągach [1] lub łańcuchy [2], więc kiedy push "woot", to po prostu, że stawia na element na strunach. [1] Czy są jakieś pytania na temat jak to działa, na poziomie podstawowym? [Sam], więc nie jest w żaden sposób dynamiczny, w odniesieniu do ilości lub w odniesieniu do wielkości stosu? [Hardison] Dokładnie. To jest - w tym, że nie było to dynamicznie growning stosu. Jest to stosu, które może pomieścić co najwyżej cztery char * s, co najwyżej czterech rzeczy. Jeśli mielibyśmy spróbować nacisnąć jeden piąta rzecz, co myślisz powinno się zdarzyć? [Studenci, niezrozumiały] [Hardison] Dokładnie. Istnieje wiele rzeczy, które mogą się wydarzyć. Mogłaby ona seg winy, w zależności od tego, co było - jak dokładnie zostaliśmy realizacji back-end. To może zastąpić. Może mieć to przepełnienie bufora, które mówiliśmy w klasie. Jaki byłby najbardziej oczywistą rzeczą, że może być zastąpiony jeśli próbowała wcisnąć dodatkowe rzeczy na naszej stos? Więc mowa przepełnienie bufora. Co może być rzeczą, która się nadpisać lub nadepnął na jeśli przepełniła przypadkowo, próbując wcisnąć dodatkowe rzeczy? [Daniel, niezrozumiały] >> Możliwe. Ale na początku, co może się zdarzyć? Co jeśli próbowała wcisnąć jeden czwarta rzecz? To może zastąpić rozmiar, przynajmniej z tego wykresu pamięci, które mamy. 

W opisie zestawu problemów, co jest, co mamy zamiar być wdrożenie dziś co chcę zrobić, to return false. Nasza metoda Push będzie zwracać wartość logiczną, oraz, że wartość logiczna będzie prawdziwa jeśli uda Push i false jeśli nie możemy wcisnąć nic więcej, ponieważ stos jest pełny. Przejdźmy przez trochę tego kodu teraz. Tu jest nasza funkcja push. Nasza funkcja nacisk na stosie ma zamiar wziąć w ciągu umieścić na stosie. To się zwróci true, jeśli ciąg powodzeniem pchnął na inny stos i false. Wszelkie sugestie na temat tego, co może być dobrą rzeczą, aby zrobić tutaj? [Sam] Jeśli wielkość równa zdolności następnie powrócić fałsz? [Hardison] Bingo. Niezła robota. Jeśli rozmiar jest pojemność, mamy zamiar wrócić false. Nie możemy umieścić coś więcej w naszej stosie. W przeciwnym razie, chcemy umieścić coś na górze stosu. Co to jest "top stosu", początkowo? [Daniel] rozmiar 0? Rozmiar 0 >>. Jaki jest szczyt stosu po jednej rzeczy na stosie? Missy, wiesz? [Missy] One. Rozmiar >> jest, dokładnie. Ciągle dodanie do wielkości, i za każdym razem jesteś wprowadzenie nowego elementu w wielkości indeksu w tablicy. Możemy to zrobić z tego rodzaju jednolinijkowych, jeśli to ma sens. Więc mamy naszą tablicę ciągów, jedziemy do niego dostęp w indeksie wielkości, i jesteśmy po prostu będzie przechowywać nasz char * w tam. Zauważ, jak nie ma kopiowanie ciąg tutaj dzieje, no dynamiczna alokacja pamięci? A następnie Missy wychowany, co teraz mamy zrobić, bo mamy przechowywać ciąg w odpowiednim miejscu w tablicy, i powiedziała, że ​​musimy zwiększyć rozmiar o jeden tak, że jesteśmy gotowi na kolejny push. Więc możemy zrobić z s.size + +. W tym momencie, mamy wepchnięty naszej tablicy. Jaka jest ostatnia rzecz, którą musimy zrobić? [Student] Zwraca true. Powrót >> prawda. Więc to jest bardzo proste, bardzo prosty kod. Nie za dużo. Po owinięte wokół twojej głowie jak stos działa jest to bardzo proste do wykonania. 

Teraz, następna część to ciąg popping off stosu. Mam zamiar dać wam trochę czasu na pracę na tym trochę mało. To prawie zasadniczo odwrotnością tego, co zrobiliśmy tutaj, w push. Co zrobiłem jest faktycznie - oops. Mam uruchomieniu systemu jakieś urządzenie tutaj, a także w urządzenia, Mam podciągnięte problemu ustawić 5 specyfikacji. Jeśli przybliżyć tutaj widzimy, że jestem w cdn.cs50.net/2012/fall/psets/pset5.pdf. Czy wy pobrać ten kod, który jest umieszczony tutaj section6.zip? Dobrze. Jeśli tego nie zrobiłeś, zrób to teraz, naprawdę szybko. Zrobię to w moim oknie terminala. I rzeczywiście zrobił to tutaj. Tak. Tak, Sam? >> Mam pytanie, dlaczego nie powiedziałeś s.string 's wsporniki o rozmiarze = str? Co to jest str? Jest zdefiniowana gdzieś przed, lub - o, w char * str? [Hardison] Tak, dokładnie. To był argument. >> Oh, w porządku. Przepraszam. [Hardison] Jesteśmy określający ciąg do pchania w. Inne pytanie, które mogą wymyślić, że tak naprawdę nie było tu mówić o braliśmy za pewnik, że mieliśmy tę zmienną o nazwie s które było w zasięgu i dostępnej dla nas. Wzięliśmy za pewnik, że to było s struct stos. Więc patrząc na to pchającej kodu, widać, że robimy rzeczy z tego łańcucha, który dostał przekazanego ale potem nagle, mamy dostęp s.size, jak, skąd s pochodzi? W kodzie, że będziemy patrzeć w archiwum sekcji i rzeczy, które będziesz robił w swoim problemie ustawia, zrobiliśmy nasz stack struct zmienną globalną tak, że możemy mieć do niego dostęp w wszystkich naszych funkcji różnych bez konieczności ręcznego przekazać go i przekazać je przez referencję, nie wszystkie tego rodzaju rzeczy do niego. Jesteśmy po prostu oszukuje trochę, jeśli chcesz, aby rzeczy ładniejsze. I to jest coś, co robimy tutaj, ponieważ jest to dla zabawy, to jest łatwiejsze. Często zobaczysz ludzie robią to, jeśli ma jedną dużą strukturę danych , która jest eksploatowana na w ich programie. 

Wróćmy nad do urządzenia. Czy każdy z powodzeniem uzyskać section6.zip? Wszyscy rozpakuj go za pomocą section6.zip rozpakować? Jeśli pójdziesz do sekcji 6 katalogu - aah, w każdym miejscu - i listy co tu widzisz, że masz trzy różne pliki. c. Masz kolejki, SLL, która jest pojedynczo-linked lista oraz stos. Po otwarciu stack.c, widać, że mamy ten struct zdefiniowany dla nas, Dokładna struktura, że ​​właśnie mówi się w slajdach. Mamy naszą zmienną globalną na stosie, mamy naszą funkcję push a my mamy naszą pop funkcję. Powiem kod dla odepchnąć się na slajdzie tutaj ale to, co chcę wam zrobić, to najlepiej, jak potrafisz, idź i wdrożenie pop funkcję. Po realizacji, można skompilować z make stos, a następnie uruchom otrzymany plik wykonywalny stosu, i że będzie działał cały ten kod testu na dół to w menu głównym. I główny zajmuje faktycznie dokonywania push i pop połączenia i upewnić się, że wszystko idzie po całej prawej stronie. Również inicjuje rozmiar stosu tutaj więc nie musisz się martwić o inicjowanie tego. Można założyć, że został poprawnie zainicjowany przez czas, że masz do niego dostęp w pop funkcji. Czy to ma sens? Tak więc zaczynamy. Jest Push kod. Dam wam 5 lub 10 minut. A jeśli masz jakiekolwiek pytania w międzyczasie, gdy jesteś kodowania, poproś go głośno. Więc jeśli masz do kłucia, po prostu zapytaj. Daj mi znać, niech wszyscy wiedzą. Praca z sąsiadem też. [Daniel] Właśnie wdrażanie pop teraz? >> Tylko pop. Choć można skopiować realizację naciśnięciem jeśli chcesz tak, że próby będą działać. Ponieważ trudno jest przetestować rzeczy z dostaniem się do - lub, że trudno przetestować rzeczy wychodziły z komina, jeśli nie ma nic w stosie, aby rozpocząć. 

Co to ma być pop powrocie? Element z wierzchu stosu. To ma się uzyskać element z wierzchu stosu i zmniejszyć wielkość stosu a teraz straciliśmy element na szczycie. A potem wrócisz element na górze. [Student, niezrozumiały] [Hardison] Więc co się stanie, jeśli to zrobić? [Student, niezrozumiały] Co kończy się dzieje, to prawdopodobnie jesteś dostępu albo Element, który nie został zainicjowany jeszcze, więc Twoja kalkulacja z których ostatni element jest wyłączony. Więc tutaj, jeśli zauważysz, w push, mamy dostęp do ciągów w s.size elementu bo to nowy indeks. Jest to nowy szczyt stosu. Natomiast w pop, s.size będzie obok miejsca, przestrzeń, która znajduje się na szczycie wszystkich elementów w swoim stosie. Więc najwyżej położony element nie jest na s.size, ale raczej jest pod nim. 

Innych rzeczy do zrobienia, kiedy - w pop, jest to trzeba zmniejszyć rozmiar. Jeśli pamiętasz z powrotem do naszego małego diagramu tu, naprawdę, jedyne, co widzieliśmy dzieje kiedy zadzwoniliśmy pop Rozmiar był że spadła, pierwszy 2, a następnie do 1. Następnie, gdy pchnął nowy element o, to iść w odpowiednim miejscu. [Basil] Jeśli s.size jest 2, to nie byłoby to do elementu 2, a potem chcesz pop tego elementu off? Więc jeśli poszliśmy do - >> Więc spójrzmy na to jeszcze raz. Jeśli jest to nasz stack w tym momencie i wzywamy pop, w której indeks jest najwyżej położony element? [Basil] W 2, ale to będzie pop 3. >> Racja. Więc to, gdzie nasz rozmiar jest 3, ale chcemy, aby wyjąć elementu o indeksie 2. To takie typowe dla rodzaju, przez jednego, że trzeba się z zerowym indeksowania tablic. Więc chcę pop trzeci element, ale trzeci element nie jest w indeksie 3. A powodem nie mamy zrobić tego minus 1, gdy jesteśmy popychanie jest, ponieważ teraz można zauważyć, że na samej górze element, gdybyśmy wcisnąć coś innego na stosie w tym punkcie, chcielibyśmy przesunąć o indeksie 3. A tak się składa, że ​​rozmiar i wskaźniki kolejce kiedy pchania. 

Kto ma działającą implementację stosu? Masz pracy stos jeden. Czy masz pop pracuje jeszcze? [Daniel] Tak. Myślę, że tak. Program >> ucieka i nie seg Błąd, to drukowanie? Czy to wydrukować "sukces", kiedy go uruchomić? Tak. Producent stos, uruchom go, jeśli wypisuje "sukces" i nie wykracza boom wtedy wszystko jest dobrze. Dobrze. Chodźmy do urządzenia bardzo szybko, i będziemy przechodzić przez to. Jeśli spojrzymy na to, co tu się dzieje z popem, Daniel, co było pierwszą rzeczą, którą zrobiłem? [Daniel] Jeśli s.size jest większe niż 0,. [Hardison] Dobra. I dlaczego to robisz? [Daniel] Aby upewnić się, że jest coś w środku stosu. [Hardison] Racja. Chcesz przetestować, aby upewnić się, że s.size jest większa niż 0; inaczej, co chcesz, aby się stało? [Daniel] zwróć NULL? Zerowy Powrót >>, dokładnie. Tak więc, jeśli s.size jest większe niż 0,. Więc co zrobimy? Co mamy zrobić, gdy stos nie jest pusty? [Stella] You zmniejszyć rozmiar? >> You zmniejszyć rozmiar, okay. Więc jak to zrobić? >> S.size--. [Hardison] Great. I co wtedy zrobiłeś? [Stella] A potem powiedziałem powrót s.string [s.size]. [Hardison] Great. W przeciwnym razie zwróci null. Tak, Sam? [Sam] Dlaczego to nie trzeba być s.size + 1? [Hardison] Plus 1? >> Tak. >> Jasne. [Sam] myślałem, bo bierzesz 1 out, następnie masz zamiar się z powrotu nie jeden, że prosiła. [Hardison] I to było właśnie to, że rozmawiamy o tej całej kwestii 0 indeksów. Jeśli więc Powiększ tutaj. Jeśli spojrzeć na tego faceta tutaj, można zobaczyć, że kiedy pojawiają, jesteśmy popping element o indeksie 2. 

Więc zmniejszyć nasze rozmiaru, potem nasz rozmiar pasuje do naszego indeksu. Jeśli nie będziemy zmniejszać rozmiar, potem musimy zrobić rozmiar -1 a następnie ubytek. Great. Wszystko dobrze? Wszelkie pytania w tej sprawie? Istnieje wiele różnych sposobów, w tym, jak i zapisu. W rzeczywistości, możemy zrobić coś jeszcze - możemy zrobić w jednej linijce. Możemy zrobić jednego wiersza powrót. Tak naprawdę możemy zmniejszyć przed wrócimy by to robić. Więc wprowadzenie - przed s.size. To sprawia, że ​​linia bardzo gęsta. W przypadku, gdy różnica między - s. Wielkości i s.size-- jest to, że postfix - nazywają to postfix powodu - jest po s.size-- Oznacza to, że jest s.size oceniane w celu znalezienia indeksu Obecnie, jak gdy linia jest wykonywane, a to - dzieje się po linii zostanie wykonany. Po elementem na s.size indeksu jest dostępny. I to nie jest to, co chcemy, bo chcemy ubytek nastąpi pierwsze. Othewise, jedziemy do dostępu do tablicy, skutecznie, poza granicami. Zamierzamy być dostęp element nad tym, że tak naprawdę chcesz uzyskać dostęp. Tak, Sam? >> Czy to szybciej lub użyć mniej pamięci RAM, aby w jednej linii, czy nie? [Hardison] Szczerze mówiąc, to naprawdę zależy. [Sam, niezrozumiały] >> Tak, to zależy. Można robić sztuczki kompilatora uzyskać kompilatora do uznania, że ​​zazwyczaj, wyobrażam sobie. 

Więc już wspomniałem trochę o tych rzeczy optymalizacji kompilatora że można to zrobić w gromadzeniu, i to jest jedna z tych rzeczy, które kompilator może być w stanie dowiedzieć się, jak Hej, może uda mi się to wszystko zrobić w jednej operacji, w przeciwieństwie do ładowania różnych rozmiarach w pamięci RAM, zmniejszanie go, zapisując go z powrotem, a następnie ładowanie go ponownie przetwarzanie resztę tego działania. Ale zazwyczaj, nie, to nie jest coś takiego że zamierza uczynić swój program znacznie szybciej. Jeszcze jakieś pytania na stosach? 

Więc popychanie i popping. Jeśli chcecie wypróbować edycję hakerów, co zrobiliśmy w wydaniu hakerów faktycznie odszedł i uczynił ten stos rośnie dynamicznie. Wyzwaniem jest tu głównie w pchającej funkcji dowiedzieć się, jak zrobić, że tablica rosnąć jak przeć coraz więcej elementów na do stosu. To faktycznie nie za dużo dodatkowego kodu. Wystarczy wywołanie - trzeba pamiętać, aby wywołania malloc tam prawidłowo, a następnie dowiedzieć się, kiedy masz zamiar zadzwonić realloc. To zabawa, wyzwanie, jeśli jesteś zainteresowany. 

Ale na razie, przejdźmy dalej, i porozmawiajmy o kolejkach. Przewiń tutaj. Kolejka jest blisko rodzeństwem stosie. Więc w stosie rzeczy, które zostały wprowadzone w ostatnim Były to pierwsze rzeczy, aby następnie zostać przywrócony. Mamy ten ostatni do, pierwszy z lub LIFO, zamawiania. Natomiast w kolejce, jak można oczekiwać od kiedy stoisz w kolejce, pierwszym, który się w kolejce, to pierwszą rzeczą, aby dostać się do kolejki, Jest to pierwsza rzecz, która zostanie pobrana z kolejki. Kolejki są również często stosowane, gdy mamy do czynienia z wykresami, jak rozmawialiśmy krótko z stosów a kolejki są również przydatne dla kilka innych rzeczy. Jednym jest rzeczą, że często próbuje się utrzymać na przykład sortowana lista elementów. I można to zrobić z tablicy. Można zachować posortowaną listę rzeczy w tablicy, ale gdzie, który dostaje trudne jest wtedy zawsze musisz znaleźć odpowiednie miejsce, aby włożyć kolejną rzecz. Więc jeśli masz tablicę liczb, 1 do 10, i chcesz rozszerzyć, że do wszystkich liczb od 1 do 100, i dostajesz te numery w kolejności losowej i próbuje utrzymać wszystko posortowane jak przejść, możesz skończyć konieczności zrobić wiele zmienia. W przypadku niektórych rodzajów kolejek i pewnych typów podstawowych struktur danych, rzeczywiście można przechowywać dość proste. Nie masz jeszcze coś dodać, a następnie przetasować całą rzecz za każdym razem. Ponadto nie trzeba zrobić wiele przesunięcie elementów wewnętrznych wokół. Kiedy patrzymy na kolejki, widać, że - również w queue.c w kodzie sekcji - struct że mamy wam jest naprawdę podobna do struktury, że dała ci na stosie. 

Jest jeden wyjątek od tej, i że jeden wyjątek jest to, że mamy tę dodatkową liczbę całkowitą o nazwie Głowa, i głowa o to do śledzenia na czele kolejki, lub pierwszy element w kolejce. Z komina, byliśmy w stanie śledzić elementu że byliśmy do pobierania, lub górę stosu, przy użyciu tylko wielkość, podczas gdy w kolejce, mamy do czynienia z przeciwległych końcach. Próbujemy tack rzeczy na końcu, ale potem wrócić rzeczy z przodu. Tak skutecznie, z głową, mamy wskaźnik początku kolejki Rozmiar i daje indeks koniec kolejki tak, że możemy odzyskać rzeczy z głowy i dodać rzeczy do ogona. Podczas gdy w stosie, to były zawsze tylko do czynienia z wierzchu stosu. Nigdy nie było dostępu do stosem. Mamy tylko dodane rzeczy na górę i wziął się rzeczy z góry więc nie trzeba, że ​​dodatkowe pole wewnątrz naszej struktury. Czy to generalnie ma sens? Dobrze. Tak, Charlotte? [Charlotte, niezrozumiały] [Hardison] To wielkie pytanie, i to taki, który pojawił się na wykładzie. Może idąc przez kilka przykładów zilustruje, dlaczego nie chcemy użyć strings [0] jako kierownika kolejki. 

Więc wyobraź sobie, że mamy kolejkę, będziemy nazywać to kolejka. Na początku, kiedy to właśnie instancja, kiedy właśnie ogłosiła, że ​​nie byliśmy zainicjowany niczego. To wszystko bzdury. Więc oczywiście chcemy się upewnić, że mamy zainicjować zarówno wielkość i pola głowa do 0, coś uzasadnione. Możemy także pójść dalej i wartość null z elementów w naszej kolejce. I aby ten schemat pasuje zauważyć, że teraz nasza kolejka może pomieścić tylko trzy elementy; natomiast nasz stack mogły pomieścić cztery, nasza kolejka może pomieścić tylko trzy. A to tylko w celu dopasowania diagramu. Pierwszą rzeczą, która dzieje się tutaj to my enqueue ciąg "hi". I tak jak zrobiliśmy to z komina, nic strasznie tu inne, rzucamy ciąg na co ciągów [0] i zwiększamy nasz rozmiar o 1. Mamy enqueue "bye", to dostaje wprowadzone. Tak to wygląda jak stos dla większości. Zaczęliśmy tu nowy element, nowy element, rozmiar utrzymuje rośnie. Co się dzieje w tym momencie, kiedy chcemy coś z kolejki? Kiedy chcemy z kolejki, który jest elementem, który chcemy z kolejki? [Basil] Strings [0]. >> Zero. Dokładnie tak, Basil. Chcemy pozbyć się pierwszego ciągu, tym razem, "Hi". Więc co było Inna sprawa, że ​​się zmieniło? Zauważ, kiedy wpadliśmy coś z stosu, po prostu zmienił rozmiar, ale tutaj mamy kilka rzeczy, które zmieniają się. Nie tylko zmienić rozmiar, ale zmiany głowy. To jest powrót do punktu Charlotte wcześniej: dlaczego mamy tę głowę, jak również? Czy jest sens teraz, Charlotte? >> Jakby. [Hardison] Rodzaj? Więc co się stało, kiedy rozkolejkowywana? Co głowa to zrobić teraz jest interesujące? [Charlotte] Oh, ponieważ zmieniły się - w porządku. Rozumiem. Ponieważ głowica - gdzie głowa wskazuje na zmiany w zakresie lokalizacji. To już nie zawsze zero jeden indeks. >> Tak, dokładnie. Co się stało, gdyby dequeueing wysoką elementu zostało zrobione i nie mamy tego pola głowy bo byliśmy zawsze nazywając ten ciąg na 0 indeksu szef naszej kolejki, wtedy musielibyśmy przenieść resztę kolejki w dół. Musielibyśmy przesunąć "bye" od strun [1] do strun [0]. I smyczki [2] aż do struny. [1] I chcemy to zrobić dla całej listy elementów, cały szereg elementów. A gdy robimy to z tablicy, że robi się naprawdę kosztowne. Więc, nie wielkiego. Mamy tylko trzy elementy naszej tablicy. Ale jeśli mieliśmy kolejkę tysiąca elementów lub milion elementów, a potem nagle, zaczniemy kilka Dequeue wzywa wszystkich w pętli, rzeczy są naprawdę będzie spowalniać, ponieważ zmienia wszystko w dół stale. Wiesz, przesunięcie o 1, przesunięcie o 1, przesunięcie o 1, przesunięcie o 1. Zamiast wykorzystać tę głowę, nazywamy to "wskaźnik", choć tak naprawdę to nie wskaźnik w ścisłym znaczeniu, to nie jest typ wskaźnika. To nie int * lub char * lub coś w tym jest. Ale to wskazanie lub wskazania głowę naszej kolejki. Tak? 

[Student] Jak Dequeue wiem po prostu zasnąć, co jest w głowie? [Hardison] Jak Dequeue umieć zasnąć, co znajduje się w głowie? Prawo >> tak. >> Co to patrząc na to tylko, co pole głowa jest ustawiona. Tak więc w tym pierwszym przypadku, jeśli przyjrzymy się właśnie tutaj, nasza głowa jest 0, 0 index. >> Racja. [Hardison] Więc po prostu mówi w porządku, dobrze, element o indeksie 0, ciąg "hi", Element jest na czele naszej kolejki. Więc jedziemy z kolejki tego faceta. I to będzie element, który zostanie zwrócony do rozmówcy. Tak, Saad? >> Więc głowa zasadzie ustawia - gdzie idziesz do indeksu to? To początek tego? >> Tak. >> Okay. [Hardison] To staje się nowy początek naszej tablicy. Więc kiedy usunie z niej coś, wszystko co musisz zrobić, to przejść do elementu o indeksie q.head, i będzie to element, który chcesz odłączyć z kolejki. Trzeba też zmniejszyć rozmiar. Zobaczymy za chwilę, gdy robi się trochę trudne z tym. Mamy z kolejki, a teraz, jeśli enqueue ponownie, gdzie mamy enqueue? Gdzie pójść następny element w naszej kolejce? Że chcemy enqueue ciąg "CS". Do której indeks to pójdzie? [Studenci] Strings [2]. >> Two. Dlaczego 2 a nie 0? [Basil] Bo teraz głowa jest 1, tak jak to jest na początku listy? [Hardison] Racja. I, co oznacza koniec listy? O czym my używany do oznaczać koniec naszej kolejki? Głowa jest głową naszego kolejce, początek naszej kolejki. Co to jest koniec naszej kolejki? [Studenci] rozmiar. >> Size, dokładnie. Tak więc nasze nowe elementy iść w rozmiarze, a elementy, które zdjąć spaść na głowę. Kiedy skolejkowania następny element, mamy wprowadzenie go w rozmiarze. [Student] Przed umieszczeniem że chociaż rozmiar był 1, prawda? [Hardison] Racja. Więc nie dość w rozmiarze. + Rozmiar nie, +1, ale głowa +. Ponieważ wszystko przesunięte o kwotę głowy. Więc, teraz mamy kolejkę wielkości 1, który rozpoczyna się od indeksu 1. Ogon jest indeks 2. Tak? 

[Student] Co się dzieje, gdy z kolejki strings [0], a łańcuch 'sloty pamięci prostu się opróżnić, w zasadzie, lub po prostu zapomnieć? [Hardison] Tak. W tym sensie, po prostu zapomina je. Jeśli byliśmy przechowywania kopii nich - wiele struktur danych często zapisywać swoje własne kopie elementów tak, że osoba zarządzająca struktury danych nie trzeba się martwić gdzie wszystkie te wskaźniki idą. Struktura danych trzyma się wszystko trzyma na wszystkich egzemplarzach, aby upewnić się, że wszystko nadal odpowiednio. Jednakże, w tym przypadku po prostu tych strukturach, dla uproszczenia, nie tworzenia kopii wszystkiego co mamy przechowywanie w nich. [Student] Więc to jest ciągła tablica -? >> Tak. Jeśli spojrzymy na to, co było definicja tej struktury, to jest. To jest po prostu zwykła tablica, jakbyś zobaczył, tablica char * s. Czy to -? >> Tak, zastanawiałam się jeśli będziesz w końcu zabraknie pamięci, do pewnego stopnia, jeśli wszystkie te puste miejsca w swojej tablicy? [Hardison] Tak, to jest dobry punkt. 

Jeśli spojrzymy na to, co się stało teraz w tym miejscu, mamy wypełniony naszą kolejkę, to wygląda. Ale tak naprawdę nie wypełni naszą kolejkę bo mamy kolejkę, która jest rozmiar 2, ale zaczyna się od indeksu 1, bo tam nasz wskaźnik głowa. Jak mówisz, że element na strunach [0], o indeksie 0, nie jest tak naprawdę istnieje. To nie leży w naszej kolejce już. My po prostu nie przeszkadzało iść i go zastąpić, gdy rozkolejkowywana go. Dlatego, mimo że wygląda na to, że zabrakło pamięci, naprawdę nie. To miejsce jest dostępne dla nas w użyciu. Właściwe zachowanie, jeśli mielibyśmy spróbować i pierwszy rozkolejkowania coś jak "cześć", które pojawiają bye off. Teraz nasza kolejka zaczyna się od indeksu 2 i ma wielkość 1. A teraz, jeśli spróbujemy i enqueue coś ponownie, powiedzmy 50, 50 powinny znaleźć się w tym miejscu o indeksie 0 bo jest jeszcze dostępna dla nas. Tak, Saad? [Saad] Czy to dzieje się automatycznie? [Hardison] To nie dzieje się to automatycznie. Musisz zrobić matematyki aby to działało, ale w istocie to, co zrobiliśmy to my właśnie owinięta. [Saad] I to jest w porządku, czy to ma dziurę w środku to? [Hardison] To jest, jeśli możemy math działać prawidłowo. 

I okazuje się, że to naprawdę nie jest trudno zrobić z operatorem mod. Więc tak jak zrobiliśmy to z Cezarem i rzeczy crypto, pomocą mod, możemy dostać rzeczy do zawinięcia i wracamy wokół i wokół i wokół z naszej kolejki, utrzymując, że wskaźnik głowa porusza. Zauważ, że rozmiar jest zawsze szanując liczbę elementów rzeczywistości w kolejce. I to tylko wskazówka, że ​​głowa trzyma wypady rowerowe. Jeśli spojrzymy na to, co się tutaj stało, jeśli wrócimy do początku, i po prostu zobaczyć, co się dzieje w głowie kiedy enqueue coś, nic się nie stało w głowę. Kiedy kolejkowane coś innego, nic się nie stało w głowę. Szybko, jak to rozkolejkowywana coś, głowa idzie w górę o jeden. Mamy kolejkowane coś, nic nie dzieje się w głowę. Kiedy usunie z niej coś, nagle głowa zostanie zwiększony. Kiedy enqueue coś, nic nie dzieje się w głowę. 

Co by się stało w tym momencie, jakbyśmy byli z kolejki coś znowu? Wszelkie myśli? Co by się stało w głowę? Co powinno się stać z głową gdybyśmy dequeue coś innego? Głowa teraz jest o indeksie 2, co oznacza, że ​​na czele kolejki jest strings [2]. [Student] Które zwraca 0? >> Warto powrócić do 0. Należy owinąć powraca, dokładnie. Do tej pory, za każdym razem zadzwoniliśmy z kolejki, byliśmy dodając jeden do głowy, dodać jeden do głowy, dodać jeden do głowy, dodać jeden w głowę. Jak tylko wskaźnik głowy dostaje się do ostatniego indeksu w naszej tablicy, wtedy mamy do zawijania go wokół na początku, wrócić do 0. [Charlotte] Co określa zdolność kolejki w stosie? [Hardison] W tym przypadku, właśnie zostały używając # zdefiniowana stała. >> Okay. [Hardison] W rzeczywistej. Plik C, można iść i błoto z nim trochę bitów i sprawiają, że tak duża lub tak mało jak chcesz. [Charlotte] Więc kiedy robisz mu kolejkę, jak zrobić komputer wie jak duży chcesz stos być? [Hardison] To wielkie pytanie. Istnieje kilka sposobów. Jednym z nich jest po prostu zdefiniować go z przodu i powiedzieć, że to będzie kolejka, która ma 4 elementów lub 50 elementów lub 10.000. Innym sposobem jest robić to, co ludzie robią wydanie hakerów i tworzenie funkcji, aby Twoja kolejka rośnie dynamicznie więcej rzeczy po dodaniu w. 

[Charlotte] Więc iść z pierwszej opcji, co składnia używasz aby poinformować program, co jest rozmiar kolejki? [Hardison] Ah. Więc z tego wyjdziemy. Wciąż jestem w stack.c tutaj, więc jestem po prostu będzie przewijać się do góry tutaj. Możesz sprawdzić to tutaj? To jest # define pojemności 10. A to jest prawie dokładnie taka sama składnia, że ​​mamy do kolejki. Wyjątkiem w kolejce, że mamy dodatkowe pole struct tutaj. [Charlotte] Oh, myślałem, pojemność oznacza zdolność do łańcucha. [Hardison] Ah. >> Że to jest maksymalna długość słowa. >> Jasne. Tak. Pojemność tutaj - to świetny punkt. I to jest coś, co jest trudne bo to, co mamy zgłaszać tutaj jest tablica char * s. Tablica wskaźników. To jest tablica znaków. To jest chyba to, co widziałem, kiedy już deklarując swoje bufory dla pliku I / O, kiedy byłaś tworząc ciągi ręcznie na stosie. Jednak to, co my tu mamy to tablica char * s. Więc jest to tablica wskaźników. Właściwie, jeśli Powiększ się i patrzymy na to, co się tu dzieje w prezentacji, można zobaczyć, że rzeczywiste elementy, dane znakowe nie są przechowywane w tablicy sam. Co jest przechowywane w naszej tablicy tu są wskaźnikami do danych znakowych. Okay. Więc widzieliśmy jak wielkość kolejki jest tak jak z komina, rozmiar zawsze szanuje liczbę elementów w kolejce. Po wykonaniu 2 kolejkuje, rozmiar jest 2. Po dokonaniu Dequeue rozmiar jest teraz 1. Po wykonaniu kolejnego Enqueue rozmiar jest z powrotem do 2. Więc rozmiar zdecydowanie przestrzega liczbę elementów w kolejce, a następnie szef odsuwa rowerze. To idzie z 0-1-2, 0-1-2, 0-1-2. I za każdym razem wywołujemy Dequeue, wskaźnik zostaje zwiększony głowa do następnego indeksu. A jeśli szef ma zamiar przejść w pętli powraca do 0. Więc z tym, możemy napisać rozkolejkowania funkcję. I zamierzamy opuścić Dodaje funkcję dla wy wdrożyć zamiast. 

Kiedy usunie z niej elementu z naszej kolejki, , co było pierwszą rzeczą, że Daniel zrobił, gdy zaczęliśmy pisać pop funkcję stosów? Pozwól mi usłyszeć od kogoś, kto nie mówi jeszcze. Zobaczmy, Saad, pamiętasz co Daniel zrobił jak pierwszą rzeczą, kiedy pisał pop? [Saad] nie było, to było - >> on testowany na coś. [Saad] Jeśli rozmiar jest większy niż 0. >> Dokładnie. A co to było za badanie? [Saad] To było badanie, aby zobaczyć, czy jest coś w środku tablicy. [Hardison] Tak. Dokładnie. Więc nie można wyskoczyć coś z komina, czy jest pusty. Podobnie, nie można z kolejki nic z kolejki, jeśli jest pusty. Co jest pierwszą rzeczą jaką należy zrobić w naszej funkcji Dequeue tutaj, jak myślisz? [Saad] Jeśli rozmiar jest większy niż 0? >> Tak. W tym przypadku, mam właściwie tylko testowane, aby zobaczyć, czy jest 0. Jeśli jest 0, możemy powrócić null. Ale dokładnie to samo logika. I niech nadal się z tym. Jeśli rozmiar nie jest 0, gdzie jest element, który chcemy z kolejki? [Saad] Na głowie? >> Dokładnie. Możemy tylko wyciągnąć pierwszy element w naszej kolejce przez dostęp do elementu w głowicy. Nic szalony. Po tym, co powinniśmy zrobić? Co musi się stać? Jaka była druga rzecz, że rozmawialiśmy o tym w Dequeue? Dwie rzeczy muszą się zdarzyć, ponieważ nasza kolejka się nie zmieniło. [Daniel] Zmniejszenie rozmiaru. >> Musimy zmniejszyć rozmiar i zwiększać głowę? Dokładnie. Aby zwiększyć głowę, nie możemy po prostu ślepo zwiększyć głowę, pamiętam. Nie możemy po prostu zrobić queue.head + +. Musimy także ten mod przez pojemności. I dlaczego mod przez pojemność, Stella? [Stella] Ponieważ ma do zawinięcia. >> Dokładnie. Mod przez nas, ponieważ ma zdolności do zawijania powraca do 0. Więc teraz, w tym momencie, możemy zrobić to, co powiedział Daniel. Możemy zmniejszyć rozmiar. A następnie po prostu może zwrócić element, który był na początku kolejki. To wygląda trochę gnarly na początku. Może masz pytanie. Przepraszam? 

[Sam] co jest najpierw na początku kolejki? Gdzie to iść? [Hardison] Pochodzi z czwartej linii od dołu. Po przetestować, aby upewnić się, że nasza kolejka nie jest pusta, możemy wyciągnąć char * najpierw musimy wyciągnąć element, który siedzi przy indeksie głowy naszej tablicy, naszej tablicy smyczki, >> i telefon, że pierwszy? [Hardison] I nazywamy to pierwsze. Tak. Wystarczy śledzić na tym, dlaczego uważasz, że musieliśmy to zrobić? [Sam] Każdy pierwszy jest po prostu powrót q.strings [q.head]? >> Tak. >> Ponieważ robimy to zmieniających q.head z funkcją MOD, i nie ma sposobu, aby to zrobić w ciągu linii powrotnej również. [Hardison] Dokładnie. Jesteś na miejscu. Sam jest całkowicie na miejscu. Powodem musieliśmy wyciągnąć pierwszy element w naszej kolejce i zapisać je w zmiennej dlatego ten wiersz gdzie właśnie q.head, istnieje operator mod tam nie coś, co możemy zrobić, to i go w życie na głowie bez - w jednej linii. Więc rzeczywiście wyciągnąć pierwszy element, a następnie ustawić głowę, dopasować rozmiar, a następnie powrócić element, że wyciągnięta. I to jest coś, co zobaczymy później wymyślić związane listy, jak bawić się z nimi. Często kiedy uwolnienie lub usuwania powiązanych list trzeba pamiętać, następny element, obok wskaźnika z połączonej listy Przed oddaniem bieżącego. Bo inaczej wyrzucić informacje o to, co zostało na liście. Teraz, jeśli się do danego urządzenia, można otworzyć queue.c--x z tego. Więc jeśli mogę otworzyć queue.c, pozwól mi powiększyć tutaj zobaczysz, że masz podobne wyglądającego pliku. Podobne wyglądający plik, co mieliśmy wcześniej z stack.c. Mamy naszą struct do kolejki określonej tak, jak widzieliśmy na slajdach. 

Mamy Dodaje funkcję, która jest dla Ciebie zrobić. I mamy rozkolejkowania funkcję tutaj. Dequeue funkcja w pliku jest niewykonane, ale będę umieścić go z powrotem w programie PowerPoint, tak aby można ją wpisać, jeśli chcesz. Tak przez kolejne 5 minut lub tak, macie pracować Kolejkuj który jest prawie na odwrót z kolejki. Nie musisz dostosować głowę kiedy skolejkowania, ale co masz do regulacji? Rozmiar. Więc kiedy enqueue głowa pozostaje nietknięty, rozmiar zostanie zmieniony. Ale zajmuje to trochę - trzeba będzie się bawić z tym mod aby dowiedzieć się dokładnie, co indeks nowy element należy umieścić w. Więc dam wam trochę, umieścić usunie z niej z powrotem na slajdzie, i jak macie pytania, krzyczeć je tak, że możemy wszyscy mówią o nich jako grupie. Ponadto, z rozmiaru don't - kiedy zmienić rozmiar, zawsze można po prostu - masz do mod rozmiar kiedykolwiek? [Daniel] L. >> Nie masz mod rozmiar, prawa. Ponieważ rozmiar będzie zawsze, jeśli Jeste - przy założeniu, że zarządzanie rzeczy właściwie, Rozmiar zawsze będzie w zakresie od 0 do 3. Gdzie masz mod kiedy robisz Enqueue? [Student] Tylko w głowie. >> Tylko w głowie, dokładnie. I dlaczego masz mod w ogóle Kolejkuj? Kiedy jest sytuacja, w której trzeba by mod? [Student] Jeśli masz rzeczy w przestrzeni, jak na przestrzeni 1 i 2, a następnie trzeba było coś dodać na 0. [Hardison] Tak, dokładnie. Więc jeśli Twój wskaźnik głowa jest na samym końcu, lub jeśli rozmiar oraz Twoja głowa jest większa, czy raczej będzie się owinąć wokół kolejki. 

Więc w tej sytuacji, że mamy tutaj na slajdzie teraz, jeśli chcę enqueue coś teraz, chcemy enqueue coś o indeksie 0. Więc jeśli spojrzeć na których 50 idzie, a ja nazywam enqueue 50, nie przechodzi się na dole. To idzie w 0 indeksu. Zastępuje on "Hi", który został już wyjęty z kolejki. [Daniel] Nie dbasz, że usunie z niej już? Dlaczego nic z głowy w Kolejkuj? [Hardison] Oh, więc nie jesteś modyfikacji głowicy, przepraszam. Ale trzeba użyć operatora mod, gdy masz dostęp do element, który chcesz enqueue gdy masz dostęp Kolejnym elementem w kolejce. [Basil] Ja tego nie zrobiłem, i mam "sukces" na tam. [Daniel] Oh, rozumiem, co mówisz. [Hardison] Więc nie zrobił - po prostu zrobiła na q.size? [Basil] Tak. Właśnie zmienił strony, nie zrobiłem nic z głowy. [Hardison] W rzeczywistości nie trzeba zresetować głowę być cokolwiek, ale kiedy indeks do tablicy ciągów, trzeba rzeczywiście iść do przodu i obliczyć gdzie Kolejnym elementem jest bo witka stos, następny element w stosie zawsze w indeksie odpowiadających wielkości. Jeśli spojrzymy na nasz funkcji Push stosu, zawsze możemy rzucać w naszym nowym elementem w prawo na wielkość indeksu. Mając na uwadze, ze w kolejce, nie możemy tego zrobić bo jeśli jesteśmy w tej sytuacji, jeśli kolejkowane 50 nasz nowy ciąg pójdzie w prawo na strunach [1] których nie chcemy robić. Chcemy mieć nowy łańcuch iść o indeksie 0. 

Czy ktoś - tak? [Student] Mam pytanie, ale to naprawdę nie jest związane. Co to znaczy, gdy ktoś po prostu wywołuje coś pred wskaźnik? Co to jest nazwa skrót? Wiem, że to tylko nazwa. [Hardison] Pred wskaźnik? Zobaczmy. W jakim kontekście? [Student] To było dla wkładki. Mogę zapytać, później, jeśli chcesz bo to naprawdę nie jest związane, ale po prostu - [Hardison] Z kodem insert Dawida z wykładu? Możemy wyciągnąć, że i porozmawiać o tym. Porozmawiamy o tym dalej, raz mamy do połączonych listach. 

Więc bardzo szybko sprawdzić, co enqueue funkcja wygląda. Co było pierwszą rzeczą, że ludzie starali się robić w enqueue linii? W tej kolejce? Podobny do tego, co zrobił dla stosu pchania. Co zrobiłeś, Stella? [Stella, niezrozumiały] [Hardison] Dokładnie. Jeśli (q.size POJEMNOŚCI ==) - Muszę wystawić szelki we właściwym miejscu - return false. Przybliż trochę. Okay. Teraz, co jest kolejną rzeczą, że mieliśmy zrobić? Podobnie jak w przypadku stosu i dodaje się na właściwym miejscu. A więc to, co było dobre miejsce, aby wstawić to? Ze stosem to wielkość indeksu, z tym, że to nie do końca to. [Daniel] Mam q.head--lub - q.strings? >> >> Tak. q.strings [q.head + q.size mod CAPACITY]? [Hardison] Prawdopodobnie chcesz umieścić nawiasy wokół tego tak, że jesteśmy coraz odpowiednie pierwszeństwo i tak że jest cleart wszystkim. I ustawić równe? >> Aby ulicy? >> Aby ul. Great. A teraz, co jest ostatnią rzeczą, że mamy do czynienia? Podobnie jak to miało miejsce w stosie. >> Zwiększ rozmiar? >> Zwiększ rozmiar. Boom. , A następnie, od rozrusznika kodem właśnie wrócił false domyślnie chcemy to zmienić na true, jeśli wszystko idzie przez i wszystko idzie dobrze. Dobrze. To dużo informacji dla sekcji. Nie jesteśmy całkiem koniec. Chcemy mówić bardzo szybko o listach pojedynczo-linked. Powiem to tak, możemy wrócić do niego później. Ale wróćmy do naszej prezentacji na slajdach tylko kilka. Więc enqueue jest TODO, teraz zrobiliśmy to. 

Teraz rzućmy okiem na list pojedynczo-linked. Rozmawialiśmy o nich nieco trochę więcej w wykładzie. Jak wielu z was widział demo gdzie mieliśmy ludzi niezgrabnie wskazując na każdego innych numerów i gospodarstwo? >> Byłem w tym. >> Co nie myślicie? Zrobiłem, mam nadzieję demystify te trochę? Z listy, okazuje się, że mamy do czynienia z tego rodzaju, które zamierzamy połączyć węzeł. Zważywszy, że z kolejki i stosu musieliśmy przypisać struktury, że chcemy zadzwonić kolejkę w stosie, mieliśmy te nowe kolejki w rodzaju stosu, tutaj lista jest tak naprawdę składa się z kilka węzłów. W ten sam sposób, że ciągi są tylko kilka znaków wszystko ułożone obok siebie. Połączonej listy jest tylko węzeł i inny węzeł, a inny węzeł i inny węzeł. I zamiast rozbijając wszystkie węzły ze sobą i przechowywanie ich ciągły wszystkie obok siebie w pamięci, mając ten następny wskaźnik umożliwia przechowywanie węzłów gdziekolwiek, na chybił trafił. Rodzaj, a następnie przewodem do ich razem z jednego punktu do drugiego. 

A co było zaletą, że miał ponad tablicy? Powyżej przechowywania wszystkiego contiguously prostu trzymaliśmy się obok siebie? Pamiętasz? Tak? Dynamiczna alokacja pamięci >>? Dynamiczna alokacja pamięci >> w jakim sensie? [Student] W, że można zachować dzięki czemu jest większe i nie trzeba, aby przenieść całą tablicę? [Hardison] Dokładnie. Więc z tablicy, gdy chcesz umieścić nowy element w środku, trzeba zmieniać wszystko, aby przestrzeń. I tak jak rozmawialiśmy z kolejki, dlatego utrzymać ten wskaźnik głowy, tak, że nie jesteśmy nieustannie zmienia rzeczy. Bo to ma drogie, jeśli masz duży wachlarz a ty ciągle robi te losowe wprowadzeniu. Zważywszy, że z listy, wszystko co musisz zrobić, to wyrzucić go na nowym węźle dostosować wskaźniki, i gotowe. Co do bani ten temat? Abstrahując od faktu, że to nie jest tak łatwo pracować jako tablica? Tak? [Daniel] Cóż, myślę, że o wiele trudniej jest uzyskać dostęp do konkretnego elementu w połączonej listy? [Hardison] Nie można po prostu przeskoczyć do dowolnego elementu na środku połączonej listy. Jak można to zrobić w zamian? >> Trzeba przejść przez to wszystko. [Hardison] Tak. Musisz przejść przez jedną na raz, jeden na raz. Jest to ogromny - to ból. Co jest inny - nie ma innego upadek tego. [Basil] Nie można iść do przodu i do tyłu? Musisz iść w jednym kierunku? [Hardison] Tak. Jak więc rozwiązać, że czasami? [Basil] podwójnie-linked list? >> Dokładnie. Jest podwójnie związane list. Są też - przepraszam? 

[Sam] Czy to sam, jak użycie pred rzeczą, która - Właśnie sobie przypomniałem, że to, co nie jest pred rzecz jest? Czy nie jest to w między podwójnie i pojedynczo? [Hardison] Przyjrzyjmy się, co dokładnie robi. Tak więc zaczynamy. Oto kod lista. Tutaj mamy predptr, tutaj. Czy to, co pan mówi? Tak to było - on uwolnienie listy i próbuje przechowywać wskaźnik do niego. To nie jest to podwójnie, pojedynczo Linked-list. Możemy porozmawiać o tym później, ponieważ to mówi o uwolnieniu listy i chcę pokazać inne rzeczy najpierw. ale to jest po prostu - jest pamiętanie wartości ptr [Student] Oh, to wskaźnik poprzedzający? >> Tak. Tak, że możemy wtedy zwiększamy ptr sam zanim to wolne co predptr jest. Ponieważ nie możemy za darmo, a następnie wywołać ptr ptr = ptr obok, prawda? To byłoby złe. Zobaczmy więc, z powrotem do tego faceta. 

Inne złą rzeczą jest to, że podczas gdy list z tablicy mamy tylko wszystkie elementy się ułożone obok siebie, Tutaj również mamy wprowadził ten wskaźnik. Więc jest dodatkowy fragment pamięci, że jesteśmy konieczności korzystania dla każdego elementu, że jesteśmy przechowywanie w naszej liście. Dostajemy elastyczność, ale to wiąże się z kosztami. Pochodzi z tych kosztów w czasie, i pochodzi z tego kosztu pamięci też. Czas w tym sensie, że mamy przejść przez każdego elementu w tablicy aby znaleźć jeden na indeksie 10, lub że byłby indeks 10 w tablicy. 

Po prostu bardzo szybko, kiedy wykres z tych list zazwyczaj trzymamy się na czele listy lub pierwszego wskaźnika na liście i pamiętać, że jest to prawdziwy wskaźnik. To tylko 4 bajty. To nie rzeczywisty węzeł sama w sobie. Więc widać, że nie ma w nim wartość int, nie obok wskaźnika w nim. Jest to dosłownie tylko wskaźnik. To będzie wskazywać na coś, co jest rzeczywiste struct node. [Sam] wskaźnik zwany węzeł? >> To jest - nie. Jest to wskaźnik na coś węzła typu. Jest to wskaźnik do struktury węzła. >> Oh, w porządku. Diagram po lewej, kod po prawej stronie. Możemy ustawić go na wartość null, co jest dobrym sposobem, aby rozpocząć. Gdy schemat, musisz albo napisać to za nieważną lub umieścić linię przez to podoba. 

Jednym z najprostszych sposobów do pracy z listami, i prosimy o nie zarówno prepend i dołączyć, aby zobaczyć różnice między nimi, ale poprzedzenie jest zdecydowanie łatwiejsze. Kiedy dołączy, to jest tam, gdzie - kiedy dokleja (7), idziesz i utworzyć struct node i ustawić pierwszy punkt do niego, bo teraz, skoro poprzedzany go, nie będzie na początku na liście. Jeśli prepend (3), który tworzy inny węzeł, ale teraz 3 jest przed 7. Więc jesteśmy w istocie popychanie rzeczy na naszej liście. Teraz widać, że dokleja, czasami ludzie nazywają to push, bo jesteś pchanie nowy element na liście. Jest także łatwy do usunięcia z przodu listy. Więc ludzie często nazywają to pop. I w ten sposób, możesz emulować stos za pomocą połączonej listy. Ups. Niestety, teraz dostajemy do dopisywania. Więc tutaj poprzedzany (7), teraz prepend (3). Jeśli mamy coś innego na poprzedzany tej liście, jeśli poprzedzany (4), wtedy musielibyśmy 4, a następnie 3 i 7. Więc możemy pop i usunąć 4, usuń 3, wyjmij 7. Często bardziej intuicyjny sposób, aby myśleć o to z dopisywania. Tak już diagramu, co to będzie wyglądać z dołączania tutaj. Tutaj, dołączany (7) nie wygląda inaczej bo jest tylko jeden element na liście. I dołączanie (3) stawia go na końcu. Może widzisz teraz sprawę z append jest to, że od kiedy tylko wiedzieć, gdzie początek listy jest aby dołączyć do listy trzeba chodzić przez całą drogę na liście aby dostać się do końca, zatrzymać, a następnie zbudować węzeł i wszystko wyłożenia. Podłączyć wszystkie rzeczy się. Więc z dokleja, jak po prostu oszukany przez to bardzo szybko, kiedy dołączy do listy, jest to dość proste. 

Dokonać w nowy węzeł, wiążą się z dynamicznej alokacji pamięci. Więc robimy struct node pomocą malloc. Więc malloc używamy bo że będzie uchylenie pamięć dla nas na później dlatego, że nie chcę tego - chcemy pamięć ta utrzyma się przez dłuższy czas. I otrzymujemy wskaźnik do miejsca w pamięci, że po prostu przydzielone. Używamy rozmiaru węzła, nie sumują pola. Nie ręcznie wygenerować liczbę bajtów, zamiast tego używamy sizeof abyśmy wiedzieli dostajemy odpowiednią liczbę bajtów. Dbamy, aby sprawdzić, że nasze wezwanie malloc udało. To jest coś, co chcesz robić w ogóle. Na nowoczesnych maszynach, uruchomiony z pamięci, nie coś, co łatwo jest chyba że przydział mnóstwo rzeczy i podejmowania ogromną listę, ale jeśli budujemy rzeczy dla, powiedzmy, jak iPhone lub Android, ty masz ograniczone zasoby pamięci, zwłaszcza jeśli robisz coś intensywne. Więc dobrze, aby w praktyce. 

Zauważ, że użyłem kilka różnych funkcji tutaj że widziałeś, że są trochę nowych. Więc fprintf jest tak jak printf chyba pierwszy argument jest strumień, do którego chcesz drukować. W tym przypadku chcemy wydrukować na standardowe ciąg błędu różni się od standardowego outstream. Domyślnie pokazuje się w tym samym miejscu. To także drukuje na terminalu, ale można - korzystania z tych poleceń, dowiedziałem się o, techniki przekierowania dowiedziałeś się o wideo Tommy'ego za zestaw problemów 4, można skierować ją w różnych obszarach, a następnie wyjść, tu, wychodzi swoim programie. To jest w istocie jak powrót z main, wyjątkiem używamy wyjścia bo tu powrót nie będzie nic robić. Nie jesteśmy w głównym, więc powrót nie wyjść z programu, jak chcemy. Więc używamy funkcji wyjścia i nadać mu kod błędu. To tutaj możemy ustawić nowy węzeł w pole wartości, jego pole i jest równy i, a potem podłączyć go. Wyznaczamy nowy węzeł następny wskaźnik, aby wskazywał pierwszy i najpierw się punktem do nowego węzła. Te pierwsze linie kodu, mamy właściwie budowy nowego węzła. Nie ostatnie dwie linie tej funkcji, ale te pierwsze. Rzeczywiście można wyciągnąć do funkcji, do funkcji pomocnika. To się często to, co mogę zrobić, to, I wyciągnąć ją do funkcji, Ja nazywam to coś węzła kompilacji i że trzyma prepend funkcja dość mały, to tylko 3 linie czasu. Mogę zadzwonić do mojej funkcji budowania węzłów, a potem wszystko drut. 

Ostatnią rzeczą chcę pokazać wam, i pozwolę zrobić append i to wszystko na własną rękę, jest jak iterować listę. Istnieje kilka różnych sposobów, aby iterować listę. W tym przypadku, mamy zamiar znaleźć długość listy. Więc zaczynamy o długości = 0. Jest to bardzo podobne do pisania strlen do łańcucha. To jest to, co chcę wam pokazać, to dla pętli tutaj. To wygląda trochę modny, nie jest to zwykle int i = 0, i <cokolwiek, i + +. Zamiast to inicjowanie naszą zmienną n być początek listy. I kiedy nasz iterator zmienna nie jest pusta, możemy iść dalej. To dlatego, że zgodnie z konwencją, koniec naszej listy będzie null. A następnie, aby zwiększyć, a nie robi + +, związane równoważne lista + + n = n-> następne. 

Dam ci wypełnić luki tutaj, ponieważ jesteśmy poza czasem. Ale o tym pamiętać podczas pracy nad swoimi psets spellr. Linked list, jeśli wdrożenie tabeli mieszania, na pewno bardzo się przydają. I posiadające ten idiom w pętli na rzeczy, że życie o wiele łatwiejsze, mam nadzieję. Wszelkie pytania, szybko? [Sam] Czy możesz wysłać wypełniony SLL i SC? [Hardison] Tak. Będę wysyłać wypełnione slajdy i wypełniony stos SLL i queue.cs. [CS50.TV]