1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:05,120 [Musiikki soi] 3 00:00:05,120 --> 00:00:12,026 4 00:00:12,026 --> 00:00:12,900 SPEAKER 1: Selvä. 5 00:00:12,900 --> 00:00:14,600 Kaikki tervetulleita takaisin osiosta. 6 00:00:14,600 --> 00:00:18,660 Toivottavasti kaikki ovat onnistuneesti toipunut tietokilpailun 7 00:00:18,660 --> 00:00:19,510 viime viikolla. 8 00:00:19,510 --> 00:00:22,564 Tiedän, että se on hieman hullu joskus. 9 00:00:22,564 --> 00:00:25,230 Kuten sanoin aiemmin, jos olet sisällä keskihajonta, 10 00:00:25,230 --> 00:00:28,188 eivät oikeastaan ​​välitä siitä, erityisesti ja vähemmän mukava jakso. 11 00:00:28,188 --> 00:00:30,230 Se siitä, missä sinun pitäisi olla. 12 00:00:30,230 --> 00:00:32,850 >> Jos teit suurta, niin mahtava. 13 00:00:32,850 --> 00:00:33,650 Kunnia teille. 14 00:00:33,650 --> 00:00:36,149 Ja jos tuntuu tarvitset hieman enemmän apua, ole hyvä 15 00:00:36,149 --> 00:00:38,140 rohkeasti päästä ulos tahansa TF: iä. 16 00:00:38,140 --> 00:00:40,030 Olemme kaikki täällä auttamassa. 17 00:00:40,030 --> 00:00:40,960 >> Siksi me opetamme. 18 00:00:40,960 --> 00:00:44,550 Siksi olen täällä joka maanantai sinulle kaverit ja virka torstaisin. 19 00:00:44,550 --> 00:00:48,130 Joten ota rohkeasti kertoa minulle jos olet huolissasi mitään 20 00:00:48,130 --> 00:00:52,450 tai jos on mitään tietokilpailu että haluat todella puuttua. 21 00:00:52,450 --> 00:00:56,940 >> Joten tämän päivän esityslistaa on kaikki noin tietorakenteita. 22 00:00:56,940 --> 00:01:01,520 Jotkut näistä ovat vain olemaan juuri saada sinut perehdytetään näitä. 23 00:01:01,520 --> 00:01:04,870 Et voi koskaan toteuttaa niitä tässä luokassa. 24 00:01:04,870 --> 00:01:08,690 Jotkut heistä tulet, kuten oman oikeinkirjoitusopas PSET. 25 00:01:08,690 --> 00:01:11,380 >> Sinulla on valintasi välillä hash taulukoita ja yrittää. 26 00:01:11,380 --> 00:01:13,680 Niin me varmasti menee yli ne. 27 00:01:13,680 --> 00:01:18,690 Se tulee olemaan varmasti enemmän laatuaan korkean tason jakso tänään, vaikka, 28 00:01:18,690 --> 00:01:22,630 koska siellä on paljon niitä, ja jos menimme toteutuksen yksityiskohdat 29 00:01:22,630 --> 00:01:26,490 kaikkia näitä, emme jopa saada läpi liittyvät luettelot 30 00:01:26,490 --> 00:01:28,520 ja ehkä hieman hash taulukoita. 31 00:01:28,520 --> 00:01:31,200 >> Niin vastaa minulle. 32 00:01:31,200 --> 00:01:33,530 Emme aio olla tekemässä niin paljon koodaus tällä kertaa. 33 00:01:33,530 --> 00:01:36,870 Jos sinulla on kysyttävää siitä tai haluat nähdä sen täytäntöön 34 00:01:36,870 --> 00:01:39,260 tai kokeile itse, Olen ehdottomasti suositella 35 00:01:39,260 --> 00:01:44,250 menossa study.cs50.net, joka on esimerkkejä kaikista näistä. 36 00:01:44,250 --> 00:01:46,400 Se täytyy minun PowerPoint kanssa toteaa, että me 37 00:01:46,400 --> 00:01:50,860 taipumus käyttää sekä joitakin ohjelmointi harjoituksia, erityisesti asioita 38 00:01:50,860 --> 00:01:55,250 kuten liittyvät luettelot ja binary Puut pinot ja vihjeitä. 39 00:01:55,250 --> 00:01:59,590 Joten hieman korkealla tasolla, mikä Voisi olla kiva teitä. 40 00:01:59,590 --> 00:02:01,320 >> Niin, että, me päästä alkuun. 41 00:02:01,320 --> 00:02:03,060 Ja myös, yes-- tietokilpailuja. 42 00:02:03,060 --> 00:02:06,550 Luulen, että useimmat teistä, jotka ovat Oma osio on tietokilpailuja, 43 00:02:06,550 --> 00:02:12,060 mutta joku tulee sisään tai jostain syystä ei, he ovat täällä edessä. 44 00:02:12,060 --> 00:02:12,740 >> Joten liittyvät luettelot. 45 00:02:12,740 --> 00:02:15,650 Tiedän tällainen menee takaisin ennen tietokilpailun. 46 00:02:15,650 --> 00:02:17,940 Se oli viikko ennen että olemme oppineet tästä. 47 00:02:17,940 --> 00:02:21,040 Mutta tässä tapauksessa, me vain Mene vähän enemmän syvyyttä. 48 00:02:21,040 --> 00:02:25,900 >> Joten miksi ehkä päätämme linkitetty lista yli array? 49 00:02:25,900 --> 00:02:27,130 Mikä erottaa ne? 50 00:02:27,130 --> 00:02:27,630 Kyllä? 51 00:02:27,630 --> 00:02:30,464 >> Yleisö: Voit laajentaa sidoksissa luetella vs. array: n kiinteä koko. 52 00:02:30,464 --> 00:02:31,171 SPEAKER 1: Oikea. 53 00:02:31,171 --> 00:02:33,970 Array on kiinteä koko taas linkitetty lista on vaihteleva koko. 54 00:02:33,970 --> 00:02:36,970 Joten jos emme tiedä miten paljon haluamme säilyttää, 55 00:02:36,970 --> 00:02:39,880 linkitetty lista antaa meille suuri tapa tehdä se, koska voimme vain 56 00:02:39,880 --> 00:02:43,730 lisätä toisen solmun ja lisäyksiä toinen solmu ja lisätä toiseen solmuun. 57 00:02:43,730 --> 00:02:45,750 Mutta mikä voisi olla kompromissi? 58 00:02:45,750 --> 00:02:49,521 Muistaako kukaan vaihtokauppa välillä paneelit ja liittyvät luettelot? 59 00:02:49,521 --> 00:02:50,020 Mmhmm? 60 00:02:50,020 --> 00:02:51,460 >> Yleisö: Sinun käydä läpi koko matkan 61 00:02:51,460 --> 00:02:53,738 kautta linkitetty lista löytää elementti luettelosta. 62 00:02:53,738 --> 00:02:55,570 Array, voit vain löytää elementti. 63 00:02:55,570 --> 00:02:56,278 >> SPEAKER 1: Oikea. 64 00:02:56,278 --> 00:02:57,120 Joten arrays-- 65 00:02:57,120 --> 00:02:58,500 >> Yleisö: [kuulumaton]. 66 00:02:58,500 --> 00:03:01,090 >> SPEAKER 1: Kun paneelit, meillä on mitä kutsutaan random access. 67 00:03:01,090 --> 00:03:04,820 Tarkoittaa, että jos me haluamme sitä, mitä on koskaan viidennen pisteen lista 68 00:03:04,820 --> 00:03:07,230 tai viides kohta meidän array, voimme vain napata se. 69 00:03:07,230 --> 00:03:10,440 Jos se on linkitetty lista, meillä on kerrata läpi, eikö? 70 00:03:10,440 --> 00:03:14,020 Joten pääsy elementin array on vakio aika, 71 00:03:14,020 --> 00:03:19,530 taas linkitetty lista se olisi todennäköisesti lineaarisen ajan, koska ehkä 72 00:03:19,530 --> 00:03:21,370 Meidän elementti on aina lopussa. 73 00:03:21,370 --> 00:03:23,446 Meidän täytyy etsiä kaikkea. 74 00:03:23,446 --> 00:03:25,320 Joten kaikki nämä tiedot rakenteet olemme menossa 75 00:03:25,320 --> 00:03:29,330 olla menoja hieman enemmän aikaa, mitä plussia ja negatiivit. 76 00:03:29,330 --> 00:03:31,480 Kun ehkä haluamme käyttää yksi yli muiden? 77 00:03:31,480 --> 00:03:34,970 Ja se on eräänlainen isompi asia ottaa pois. 78 00:03:34,970 --> 00:03:40,140 >> Joten meillä on täällä määritelmä solmun. 79 00:03:40,140 --> 00:03:43,040 Se on kuin yksi osa meidän linkitetty lista, eikö? 80 00:03:43,040 --> 00:03:46,180 Joten me kaikki tunnemme meidän typedef structs, 81 00:03:46,180 --> 00:03:47,980 josta menimme ohi tarkastelun viime kerralla. 82 00:03:47,980 --> 00:03:53,180 Se oli lähinnä vain luoda toinen tietotyyppi, että voisimme käyttää. 83 00:03:53,180 --> 00:03:57,930 >> Ja tässä tapauksessa, se on jonkin verran solmussa että pitää jotkut kokonaisluku. 84 00:03:57,930 --> 00:04:00,210 Ja mitä sitten on toinen osa täällä? 85 00:04:00,210 --> 00:04:03,192 86 00:04:03,192 --> 00:04:05,677 Kukaan? 87 00:04:05,677 --> 00:04:06,680 >> Yleisö: [kuulumaton]. 88 00:04:06,680 --> 00:04:07,020 >> SPEAKER 1: Joo. 89 00:04:07,020 --> 00:04:08,400 Se on osoitin seuraavaan solmuun. 90 00:04:08,400 --> 00:04:12,610 Joten tämä pitäisi oikeastaan ​​olla täällä. 91 00:04:12,610 --> 00:04:18,790 Tämä on osoitin tyyppiä solmu seuraavaan asia. 92 00:04:18,790 --> 00:04:22,410 Ja sitähän he kattaa meidän solmu. 93 00:04:22,410 --> 00:04:24,060 Cool. 94 00:04:24,060 --> 00:04:29,390 >> Okei, joten haulla, koska olimme vain sanomalla ennen käsin, jos olet 95 00:04:29,390 --> 00:04:31,840 menossa etsiä, olet todella kerrata 96 00:04:31,840 --> 00:04:33,660 kautta linkitetty lista. 97 00:04:33,660 --> 00:04:38,530 Joten jos etsit numero 9, meillä alkaisi meidän pään 98 00:04:38,530 --> 00:04:41,520 ja joka osoittaa meille alussa meidän linkitetty lista, eikö? 99 00:04:41,520 --> 00:04:44,600 Ja me sanomme, OK, ei tämä solmu sisältää numero 9? 100 00:04:44,600 --> 00:04:45,690 Ei? 101 00:04:45,690 --> 00:04:47,500 >> Okei, siirry seuraavaan. 102 00:04:47,500 --> 00:04:48,312 Seuraa sitä. 103 00:04:48,312 --> 00:04:49,520 Sisältääkö se numero 9? 104 00:04:49,520 --> 00:04:50,570 Ei. 105 00:04:50,570 --> 00:04:51,550 Seuraa seuraavaan. 106 00:04:51,550 --> 00:04:55,490 >> Joten meidän on todella kerrata kautta linkitetty lista. 107 00:04:55,490 --> 00:05:00,070 Emme voi vain mennä suoraan jossa 9 on. 108 00:05:00,070 --> 00:05:05,860 Ja jos te todella haluavat nähdä joitakin pseudo-koodin sinne. 109 00:05:05,860 --> 00:05:10,420 Meillä on joitakin hakutoiminto täällä joka vie in-- mitä se aikoo ryhtyä? 110 00:05:10,420 --> 00:05:13,110 111 00:05:13,110 --> 00:05:14,320 Mitä mieltä olet? 112 00:05:14,320 --> 00:05:15,960 Niin helppo. 113 00:05:15,960 --> 00:05:17,784 Mikä tämä on? 114 00:05:17,784 --> 00:05:18,700 Yleisö: [kuulumaton]. 115 00:05:18,700 --> 00:05:20,366 SPEAKER 1: numero etsimme. 116 00:05:20,366 --> 00:05:20,980 Oikea? 117 00:05:20,980 --> 00:05:22,875 Ja mitä tämä vastaa? 118 00:05:22,875 --> 00:05:25,020 Se on osoitin? 119 00:05:25,020 --> 00:05:26,000 >> Yleisö: solmu. 120 00:05:26,000 --> 00:05:28,980 >> SPEAKER 1: solmun listaan että me tarkastelemme, eikö? 121 00:05:28,980 --> 00:05:33,700 Joten meillä on joitakin solmut ovat osoittimen täällä. 122 00:05:33,700 --> 00:05:37,240 Tämä on seikka, joka tulee todella kerrata kautta listallamme. 123 00:05:37,240 --> 00:05:39,630 Asetimme se sama listata koska se on vain 124 00:05:39,630 --> 00:05:44,380 jossa se on yhtä suuri kuin alkaa meidän linkitetty lista. 125 00:05:44,380 --> 00:05:50,660 >> Ja vaikka se ei ole nolla, kun taas meillä on vielä asioita listallamme, 126 00:05:50,660 --> 00:05:55,580 tarkista, että solmulla on numero etsimme. 127 00:05:55,580 --> 00:05:57,740 Return true. 128 00:05:57,740 --> 00:06:01,070 Muuten, päivittää sitä, eikö? 129 00:06:01,070 --> 00:06:04,870 >> Jos se on tyhjä, me poistu meidän while-silmukka ja return false 130 00:06:04,870 --> 00:06:08,340 koska se tarkoittaa, että emme ole löytäneet sitä. 131 00:06:08,340 --> 00:06:11,048 Onko kaikki saavat miten se toimii? 132 00:06:11,048 --> 00:06:11,548 OK. 133 00:06:11,548 --> 00:06:14,940 134 00:06:14,940 --> 00:06:20,260 >> Joten ollen sinun on kolme eri tapaa. 135 00:06:20,260 --> 00:06:25,250 Voit liittää alkuun, voit liittää ja voit lisätä lajitelma. 136 00:06:25,250 --> 00:06:28,215 Tässä tapauksessa olemme aikoo tehdä prepend. 137 00:06:28,215 --> 00:06:33,380 Tietääkö kukaan miten nämä kolmessa tapauksessa saattaa vaihdella? 138 00:06:33,380 --> 00:06:36,920 >> Niin prepend tarkoittaa, että laitat se edessä listasi. 139 00:06:36,920 --> 00:06:39,770 Niin se tarkoittaisi, että ei väliä mitä solmu on, ei väliä 140 00:06:39,770 --> 00:06:43,160 mitä arvo on, olet menossa laittaa se täällä edessä, OK? 141 00:06:43,160 --> 00:06:45,160 Se tulee olemaan ensimmäinen elementti luettelosta. 142 00:06:45,160 --> 00:06:49,510 >> Jos liität sen, se tulee mennä takaisin listasi. 143 00:06:49,510 --> 00:06:54,010 Ja työnnä lajitelma tarkoittaa olet aio laittaa itse siihen paikkaan 144 00:06:54,010 --> 00:06:57,700 jos se pitää linkitetty lista järjestetty. 145 00:06:57,700 --> 00:07:00,810 Jälleen, miten käytät ne ja kun käytät 146 00:07:00,810 --> 00:07:02,530 ne vaihtelevat teidän tapauksessa. 147 00:07:02,530 --> 00:07:05,834 148 00:07:05,834 --> 00:07:07,750 Jos se ei tarvitse lajitellaan, prepend yleensä 149 00:07:07,750 --> 00:07:10,460 olla mitä useimmat ihmiset käyttää, koska et 150 00:07:10,460 --> 00:07:15,680 täytyy käydä läpi koko lista löytää lopulta lisätä sen, eikö? 151 00:07:15,680 --> 00:07:17,720 Voit vain kiinni se oikein. 152 00:07:17,720 --> 00:07:21,930 >> Joten me menemme läpi lisäys 1 juuri nyt. 153 00:07:21,930 --> 00:07:26,360 Niin yksi asia, että aion Suosittelemme tätä PSET 154 00:07:26,360 --> 00:07:29,820 on kiinnittää asioita, kuten aina. 155 00:07:29,820 --> 00:07:35,130 On hyvin tärkeää, että päivität sinun viitteitä oikeassa järjestyksessä 156 00:07:35,130 --> 00:07:38,620 koska jos ne ajan tasalle hieman epäkunnossa, 157 00:07:38,620 --> 00:07:42,210 aiot päätyä menettää osia listasi. 158 00:07:42,210 --> 00:07:49,680 >> Niin esimerkiksi tässä tapauksessa olemme kertoo pää vain pisteen 1. 159 00:07:49,680 --> 00:07:56,070 Jos me vain tehdä tallentamatta tähän 1, 160 00:07:56,070 --> 00:07:58,570 meillä ei ole aavistustakaan, mitä 1 pitäisi osoittaa nyt 161 00:07:58,570 --> 00:08:02,490 koska olemme menettäneet mitä pää huomautti. 162 00:08:02,490 --> 00:08:05,530 Niin yksi asia muistaa kun olet tekemässä prepend 163 00:08:05,530 --> 00:08:09,630 on pelastaa mitä pää osoittaa ensin, 164 00:08:09,630 --> 00:08:15,210 sitten siirtää sen, ja sitten päivittää mitä uusi solmu pitäisi osoittaa. 165 00:08:15,210 --> 00:08:20,870 166 00:08:20,870 --> 00:08:22,560 Tässä tapauksessa tämä on yksi tapa tehdä se. 167 00:08:22,560 --> 00:08:25,440 >> Joten jos olisimme tehneet sen tällä tavalla jos me vain osoittaa uudelleen pää, 168 00:08:25,440 --> 00:08:30,320 menetämme pohjimmiltaan meidän Koko lista, eikö? 169 00:08:30,320 --> 00:08:38,000 Yksi tapa tehdä se on saada 1 pisteen seuraava, ja sitten on pää kohta 1. 170 00:08:38,000 --> 00:08:42,650 Tai voit tehdä ikään kuin väliaikainen varastointi, joka puhuin. 171 00:08:42,650 --> 00:08:45,670 >> Mutta uudelleen kohdentamisesta sinun osoittimet oikeassa järjestyksessä 172 00:08:45,670 --> 00:08:48,750 tulee olemaan hyvin, hyvin tärkeää, että tämä PSET. 173 00:08:48,750 --> 00:08:53,140 Muuten, olet menossa on hash pöytä tai kokeilla, joka on juuri olemaan 174 00:08:53,140 --> 00:08:56,014 vain osa sanoista haluavat ja sitten you're-- mmhmm? 175 00:08:56,014 --> 00:08:58,930 Yleisö: Mikä oli väliaikainen varastointi asia puhuit? 176 00:08:58,930 --> 00:09:00,305 SPEAKER 1: väliaikainen varastointi. 177 00:09:00,305 --> 00:09:02,760 Joten periaatteessa toisen Tavallaan voisi tehdä tämän 178 00:09:02,760 --> 00:09:07,650 on tallentaa johtaja jotain, kuten säilytä se väliaikainen muuttuja. 179 00:09:07,650 --> 00:09:11,250 Määrittää sen 1 ja sitten päivittää 1 kohtaan 180 00:09:11,250 --> 00:09:13,830 mihin tahansa pään käytetään osoittamaan. 181 00:09:13,830 --> 00:09:16,920 Tällä tavalla on ilmeisesti enemmän tyylikäs, koska olet 182 00:09:16,920 --> 00:09:20,770 ei tarvita tilapäisen arvon, mutta vain tarjoamalla toinen tapa tehdä se. 183 00:09:20,770 --> 00:09:23,999 184 00:09:23,999 --> 00:09:25,790 Ja emme oikeastaan ​​ole Joissakin koodi tähän. 185 00:09:25,790 --> 00:09:28,080 Joten linkitetty lista, me todella on koodia. 186 00:09:28,080 --> 00:09:31,930 Niin laita tänne, tämä on prepending. 187 00:09:31,930 --> 00:09:34,290 Joten tämä tulee sen kärjessä. 188 00:09:34,290 --> 00:09:38,820 >> Joten ensimmäinen asia, sinun täytyy Luo uusi solmu, tietenkin, 189 00:09:38,820 --> 00:09:40,790 ja tarkista NULL. 190 00:09:40,790 --> 00:09:43,250 Aina hyvä. 191 00:09:43,250 --> 00:09:47,840 Ja sitten sinun täytyy määrittää arvot. 192 00:09:47,840 --> 00:09:51,260 Aina kun luot uuden solmun, et en tiedä mitä se on suunnattu seuraavaan, 193 00:09:51,260 --> 00:09:54,560 joten haluat alustaa sen null. 194 00:09:54,560 --> 00:09:58,760 Jos se ei päädy osoittaa jotain muuten, se saa antaa uudelleen ja se on hieno. 195 00:09:58,760 --> 00:10:00,740 Jos se on ensimmäinen asia luettelossa, se tarvitsee 196 00:10:00,740 --> 00:10:04,270 osoittamaan NULL koska se listan loppuun. 197 00:10:04,270 --> 00:10:12,410 >> Niin sitten lisätä sitä, näemme täällä määrität seuraavan arvon meidän solmun 198 00:10:12,410 --> 00:10:17,380 olla mitä pää on, joka on mitä meillä oli täällä. 199 00:10:17,380 --> 00:10:19,930 Sitähän me juuri teimme. 200 00:10:19,930 --> 00:10:25,820 Ja sitten me määrittämällä pään pisteeseen meidän uusi solmu, koska muistan, 201 00:10:25,820 --> 00:10:31,090 Uutta on joissakin osoitin solmuun, ja se on juuri sitä, mitä pää on. 202 00:10:31,090 --> 00:10:34,370 Juuri siksi me on tämä nuoli accessor. 203 00:10:34,370 --> 00:10:37,030 204 00:10:37,030 --> 00:10:37,530 Cool? 205 00:10:37,530 --> 00:10:38,130 Mmhmm? 206 00:10:38,130 --> 00:10:41,100 >> Yleisö: Onko meillä alustaa uusia vieressä NULL ensin, 207 00:10:41,100 --> 00:10:44,240 vai voimmeko vain alustaa sen pää? 208 00:10:44,240 --> 00:10:48,210 >> SPEAKER 1: Uusi Seuraava täytyy olla NULL aloittaa 209 00:10:48,210 --> 00:10:53,760 koska et tiedä jos se tulee olemaan. 210 00:10:53,760 --> 00:10:56,100 Myös tämä on tavallaan Aivan kuten paradigma. 211 00:10:56,100 --> 00:10:59,900 Asetat sen yhtä NULL vain tehdä Varmista, että kaikki perusteet kuuluvat 212 00:10:59,900 --> 00:11:04,070 ennen kuin teet mitään siirtämisellä jotta olet aina varmaa, että se tulee 213 00:11:04,070 --> 00:11:08,880 osoittavan erityistä arvoa vs. kuin roskat arvo. 214 00:11:08,880 --> 00:11:12,210 Sillä, joo, asetamme uusi ensi automaattisesti, 215 00:11:12,210 --> 00:11:15,420 mutta se on enemmän aivan kuten hyviä käytäntöjä sen alustamiseen 216 00:11:15,420 --> 00:11:19,270 tällä tavalla ja sitten siirtää. 217 00:11:19,270 --> 00:11:23,420 >> OK, joten kaksinkertaisesti sidottu luetteloiden nyt. 218 00:11:23,420 --> 00:11:24,601 Mitä ajattelet? 219 00:11:24,601 --> 00:11:26,350 Mikä on erilaista kanssa kaksinkertaisesti liittyvät luettelot? 220 00:11:26,350 --> 00:11:30,750 221 00:11:30,750 --> 00:11:34,300 >> Joten meidän linkitettyjen listojen, voimme liikkua vain yhteen suuntaan, eikö? 222 00:11:34,300 --> 00:11:35,270 Meillä on vain seuraava. 223 00:11:35,270 --> 00:11:36,760 Emme voi vain mennä eteenpäin. 224 00:11:36,760 --> 00:11:40,300 >> Kanssa kaksin verroin linkitetty lista, Voimme myös liikkua taaksepäin. 225 00:11:40,300 --> 00:11:44,810 Joten emme ole vain numero, jonka haluamme säilyttää, 226 00:11:44,810 --> 00:11:50,110 meillä kun se viittaa seuraavaan ja jos me vain tuli. 227 00:11:50,110 --> 00:11:52,865 Joten tämä mahdollistaa jotkut paremmin läpikäyminen. 228 00:11:52,865 --> 00:11:56,620 229 00:11:56,620 --> 00:12:01,240 >> Joten kaksinkertaisesti sidottu solmuja, hyvin samankaltainen, eikö? 230 00:12:01,240 --> 00:12:05,000 Ainoa ero on nyt meillä on seuraava ja edellinen. 231 00:12:05,000 --> 00:12:06,235 Se on ainoa ero. 232 00:12:06,235 --> 00:12:09,570 233 00:12:09,570 --> 00:12:14,790 >> Joten jos me liittää alkuun tai append-- me ei ole mitään koodia tähän asti here-- 234 00:12:14,790 --> 00:12:17,830 mutta jos olit yrittää aseta se, tärkeintä 235 00:12:17,830 --> 00:12:19,980 on sinun täytyy tehdä että olet osoitetaan 236 00:12:19,980 --> 00:12:23,360 sekä edellisen ja Seuraava osoitin oikein. 237 00:12:23,360 --> 00:12:29,010 Joten tässä tapauksessa sinun ei vain alustaa seuraavan, 238 00:12:29,010 --> 00:12:31,820 alustat edellinen. 239 00:12:31,820 --> 00:12:36,960 Jos olemme kärjessä listan, me olisi paitsi pää yhdenvertaisen uusia, 240 00:12:36,960 --> 00:12:41,750 mutta meidän uutta edellinen pitäisi viittaavat päähän, eikö? 241 00:12:41,750 --> 00:12:43,380 >> Se on ainoa ero. 242 00:12:43,380 --> 00:12:47,200 Ja jos haluat enemmän käytännön kanssa Näiden kanssa liittyvät luettelot, jossa asennat 243 00:12:47,200 --> 00:12:49,900 kanssa poistamalla, Insert osaksi valikoituja lista, 244 00:12:49,900 --> 00:12:52,670 tutustu study.cs50.net. 245 00:12:52,670 --> 00:12:54,870 On joukko suuria harjoituksia. 246 00:12:54,870 --> 00:12:55,870 Olen erittäin suositella niitä. 247 00:12:55,870 --> 00:12:59,210 Toivon, että meillä oli aikaa käydä niitä läpi mutta siellä on paljon tietorakenteita 248 00:12:59,210 --> 00:13:01,530 päästä läpi. 249 00:13:01,530 --> 00:13:02,650 >> OK, niin hash taulukoita. 250 00:13:02,650 --> 00:13:07,070 Tämä on luultavasti hyödyllinen vähän oman PSET 251 00:13:07,070 --> 00:13:11,090 täällä, koska aiot olla täytäntöön yksi näistä, tai yrittää. 252 00:13:11,090 --> 00:13:12,200 Pidän todella hash taulukoita. 253 00:13:12,200 --> 00:13:13,110 Ne ovat aika siistiä. 254 00:13:13,110 --> 00:13:17,080 >> Joten periaatteessa mitä tapahtuu, on tiiviste 255 00:13:17,080 --> 00:13:22,050 on, kun me todella tarvitsemme pikaista lisäys, poisto ja haku. 256 00:13:22,050 --> 00:13:25,010 Nämä ovat asioita, joita olemme priorisoinnin hajautustaulua. 257 00:13:25,010 --> 00:13:29,500 He voivat saada melko suuri, mutta kuten näemme kanssa yrittää, 258 00:13:29,500 --> 00:13:33,040 on olemassa asioita, jotka ovat paljon suurempia. 259 00:13:33,040 --> 00:13:38,330 >> Mutta pohjimmiltaan, kaikki hash pöytä on hash-funktio 260 00:13:38,330 --> 00:13:47,215 joka kertoo mikä ämpäri laittaa jokaisen tietosi, jokainen teidän osia. 261 00:13:47,215 --> 00:13:51,140 Yksinkertainen tapa ajatella hajautustaulun on, että se on vain ämpärillistä asioita, 262 00:13:51,140 --> 00:13:51,770 oikeassa? 263 00:13:51,770 --> 00:13:59,720 Joten kun olet lajittelu asioita kuten ensimmäisen kirjaimen nimensä, 264 00:13:59,720 --> 00:14:01,820 se on ikään kuin hajautustaulun. 265 00:14:01,820 --> 00:14:06,180 >> Joten jos olisin ryhmään te on ryhmiin kuka nimi alkaa 266 00:14:06,180 --> 00:14:11,670 kanssa tänne, tai kuka syntymäpäivä on tammi-, helmi-, maalis-, 267 00:14:11,670 --> 00:14:15,220 mitä tahansa, joka on tosiasiallisesti luodaan tiiviste. 268 00:14:15,220 --> 00:14:18,120 Se on vain luoda kauhat voit lajitella elementit 269 00:14:18,120 --> 00:14:19,520 jotta voit löytää ne helpommin. 270 00:14:19,520 --> 00:14:22,300 Joten tällä tavalla, kun tarvitsen löytää yksi teistä, 271 00:14:22,300 --> 00:14:24,680 Minulla ei ole etsiä läpi jokaisen teidän nimiä. 272 00:14:24,680 --> 00:14:29,490 En voi olla kuin, oh, tiedän että Danielle syntymäpäivä on in-- 273 00:14:29,490 --> 00:14:30,240 Yleisö: --April. 274 00:14:30,240 --> 00:14:30,948 SPEAKER 1: huhtikuussa. 275 00:14:30,948 --> 00:14:33,120 Joten odotan minun huhtikuu ämpäri, ja tuurilla, 276 00:14:33,120 --> 00:14:38,270 hän tulee olemaan ainoa siellä ja aikani oli vakio siinä mielessä, 277 00:14:38,270 --> 00:14:41,230 katsoo, että jos minun täytyy katsoa läpi koko joukko ihmisiä, 278 00:14:41,230 --> 00:14:43,090 se vie paljon kauemmin. 279 00:14:43,090 --> 00:14:45,830 Niin hash taulukot ovat oikeastaan ​​vain kauhat. 280 00:14:45,830 --> 00:14:48,630 Helppo tapa ajatella niitä. 281 00:14:48,630 --> 00:14:52,930 >> Joten erittäin tärkeä asia tiiviste on hash funktio. 282 00:14:52,930 --> 00:14:58,140 Niin mitä minä juuri puhui, kuten ensimmäinen kirjain ETUNIMESSÄSI 283 00:14:58,140 --> 00:15:01,450 tai syntymäpäivä kuukausi, nämä ovat ajatuksia, jotka 284 00:15:01,450 --> 00:15:03,070 todella korreloivat hajautusfunktio. 285 00:15:03,070 --> 00:15:08,900 Se on vain tapa päättää, mitkä ämpäri olisit elementti menee, OK? 286 00:15:08,900 --> 00:15:14,850 Joten tämä PSET, voit etsiä melko paljon mitään tiivistefunktiota haluat. 287 00:15:14,850 --> 00:15:16,030 >> Ei tarvitse olla oma. 288 00:15:16,030 --> 00:15:21,140 On joitakin todella hienoja niistä ulos siellä tehdä kaikenlaisia ​​hulluja matematiikka. 289 00:15:21,140 --> 00:15:25,170 Ja jos haluat tehdä oikoluku huippunopea, 290 00:15:25,170 --> 00:15:27,620 Haluan ehdottomasti tutkia yksi niistä. 291 00:15:27,620 --> 00:15:32,390 >> Mutta on myös yksinkertaiset, kuten laskentatehoa 292 00:15:32,390 --> 00:15:39,010 summa sanoja, kuten jokainen kirjain on useita. 293 00:15:39,010 --> 00:15:39,940 Laske summa. 294 00:15:39,940 --> 00:15:42,230 Joka määrittää ämpäri. 295 00:15:42,230 --> 00:15:45,430 Niillä on myös helppo niitä, jotka ovat aivan kuin kaikki on täällä, 296 00:15:45,430 --> 00:15:47,050 kaikki B: n täällä. 297 00:15:47,050 --> 00:15:48,920 Yksi näistä. 298 00:15:48,920 --> 00:15:55,770 >> Periaatteessa se vain kertoo, mitä taulukkoindeksin sinun elementti pitäisi mennä. 299 00:15:55,770 --> 00:15:58,690 Vain päättää bucket-- se on kaikki hash-funktio on. 300 00:15:58,690 --> 00:16:04,180 Joten tässä meillä on esimerkki, joka on vain ensimmäinen kirjain merkkijono 301 00:16:04,180 --> 00:16:05,900 että olin juuri puhu. 302 00:16:05,900 --> 00:16:11,900 >> Joten sinulla on joitakin hash, joka on juuri ensimmäinen kirjain merkkijono miinus, 303 00:16:11,900 --> 00:16:16,090 joka antaa sinulle numero välillä 0 ja 25. 304 00:16:16,090 --> 00:16:20,790 Ja mitä haluat tehdä, on Varmista, että tämä on 305 00:16:20,790 --> 00:16:24,110 kokoa hash table-- kuinka monta kauhat olemassa. 306 00:16:24,110 --> 00:16:25,860 Monet näistä hajautusfunktioita, he 307 00:16:25,860 --> 00:16:31,630 menossa palaamassa arvoja, jotka pitää olla reilusti määrä kauhat 308 00:16:31,630 --> 00:16:33,610 että sinulla todella on teidän tiiviste, 309 00:16:33,610 --> 00:16:37,240 joten sinun täytyy tehdä varma ja mod ne. 310 00:16:37,240 --> 00:16:42,190 Muuten, se tulee sanoa, Voi, se olisi ämpäri 5000 311 00:16:42,190 --> 00:16:46,040 mutta sinulla on vain 30 kauhat teidän tiiviste. 312 00:16:46,040 --> 00:16:49,360 Ja tietysti me kaikki tiedämme, että on menossa aiheuttaa joitakin hulluja virheitä. 313 00:16:49,360 --> 00:16:52,870 Joten varmista mod mukaan kokoa tiiviste. 314 00:16:52,870 --> 00:16:58,430 315 00:16:58,430 --> 00:16:58,930 Cool. 316 00:16:58,930 --> 00:17:00,506 Niin törmäyksiä. 317 00:17:00,506 --> 00:17:02,620 On kaikille hyvä tähän mennessä? 318 00:17:02,620 --> 00:17:03,120 Mmhmm? 319 00:17:03,120 --> 00:17:05,900 >> Yleisö: Miksi se palauttaa tällaisen massiivisen arvo? 320 00:17:05,900 --> 00:17:09,210 >> SPEAKER 1: Riippuen algoritmi että hash funktio käyttää. 321 00:17:09,210 --> 00:17:12,270 Jotkut heistä tekevät hullu kertominen. 322 00:17:12,270 --> 00:17:16,270 Ja se kaikki noin saada tasainen jakautuminen, 323 00:17:16,270 --> 00:17:18,490 joten he tekevät joitakin todella hulluja asioita joskus. 324 00:17:18,490 --> 00:17:20,960 Siinä kaikki. 325 00:17:20,960 --> 00:17:22,140 Entä muuta? 326 00:17:22,140 --> 00:17:22,829 OK. 327 00:17:22,829 --> 00:17:24,480 >> Niin törmäyksiä. 328 00:17:24,480 --> 00:17:29,270 Periaatteessa, kuten sanoin aiemmin, parhaassa tapauksessa, 329 00:17:29,270 --> 00:17:32,040 mitään ämpäri katson on menossa on yksi asia, 330 00:17:32,040 --> 00:17:34,160 joten minun ei tarvitse katsoa ollenkaan, eikö? 331 00:17:34,160 --> 00:17:37,040 En myöskään tiedä, se on olemassa tai se on ei, ja sitähän me todella haluamme. 332 00:17:37,040 --> 00:17:43,960 Mutta jos meillä on kymmeniä tuhansia mittauspisteiden ja pienempi kuin määrä 333 00:17:43,960 --> 00:17:48,700 kauhat, me aiomme olla yhteentörmäyksiä, joissa lopulta jotain 334 00:17:48,700 --> 00:17:54,210 joutuu päätyä ämpäri, joka on jo elementti. 335 00:17:54,210 --> 00:17:57,390 >> Joten kysymys on, mitä teemme tässä tapauksessa? 336 00:17:57,390 --> 00:17:58,480 Mitä teemme? 337 00:17:58,480 --> 00:17:59,300 Meillä on jo jotain siellä? 338 00:17:59,300 --> 00:18:00,060 Me vain heittää sen pois? 339 00:18:00,060 --> 00:18:00,700 >> Ei. 340 00:18:00,700 --> 00:18:01,980 Meidän täytyy pitää molemmat. 341 00:18:01,980 --> 00:18:06,400 Niin samalla tavalla kuin me tyypillisesti tee, joka on mitä? 342 00:18:06,400 --> 00:18:08,400 Mikä on tietorakenne me juuri puhuneet? 343 00:18:08,400 --> 00:18:09,316 Yleisö: linkitetty lista. 344 00:18:09,316 --> 00:18:10,500 SPEAKER 1: linkitetty lista. 345 00:18:10,500 --> 00:18:16,640 Niin nyt, sen sijaan, että kukin näistä kauhat vain ottaa yksi osa, 346 00:18:16,640 --> 00:18:24,020 se tulee sisältämään liittyy luettelo elementtejä, jotka olivat hajauttamat siihen. 347 00:18:24,020 --> 00:18:27,588 OK, ei kaikille sellaista saada tuon ajatuksen? 348 00:18:27,588 --> 00:18:30,546 Koska emme voineet olla array sillä emme tiedä, kuinka paljon 349 00:18:30,546 --> 00:18:31,730 tulevat olemaan siellä. 350 00:18:31,730 --> 00:18:36,540 Linkitetyn listan avulla voimme on vain tarkka määrä, joka 351 00:18:36,540 --> 00:18:38,465 hajautetaan tuohon ämpäri, eikö? 352 00:18:38,465 --> 00:18:42,260 353 00:18:42,260 --> 00:18:50,500 >> Niin lineaarinen luotaa on pohjimmiltaan tämä idea-- 354 00:18:50,500 --> 00:18:52,300 se on yksi tapa käsitellä törmäyksen. 355 00:18:52,300 --> 00:18:58,010 Mitä voit tehdä on, jos tässä tapauksessa, marja hashed osaksi 1 356 00:18:58,010 --> 00:19:01,130 ja meillä on jo jotain siellä, et vain 357 00:19:01,130 --> 00:19:04,840 pitää käynnissä kunnes löydät tyhjä paikka. 358 00:19:04,840 --> 00:19:06,370 Se on yksi tapa käsitellä sitä. 359 00:19:06,370 --> 00:19:09,020 Toinen tapa käsitellä se on mitä me juuri 360 00:19:09,020 --> 00:19:12,280 called-- liittyvät lista on nimeltään ketjutus. 361 00:19:12,280 --> 00:19:20,510 >> Joten tämä idea toimii, jos teidän tiiviste luulet 362 00:19:20,510 --> 00:19:24,150 on paljon suurempi kuin tietueesi tai jos 363 00:19:24,150 --> 00:19:28,870 haluavat yrittää minimoida ketjuttamalla kunnes se on ehdottoman välttämätöntä. 364 00:19:28,870 --> 00:19:34,050 Niin yksi asia on lineaarinen luotaa tarkoittaa luonnollisesti 365 00:19:34,050 --> 00:19:37,290 että tiivistefunktio ei ole aivan yhtä hyödyllinen 366 00:19:37,290 --> 00:19:42,200 koska aiot päätyä käyttämään teidän tiivistefunktiota, saada piste, 367 00:19:42,200 --> 00:19:46,400 voit lineaarinen koetin alas jotkut paikka, joka on käytettävissä. 368 00:19:46,400 --> 00:19:49,670 Mutta nyt, tietenkin, mitään muuta, joka päätyy sinne, 369 00:19:49,670 --> 00:19:52,050 olet menossa on etsi entisestään alas. 370 00:19:52,050 --> 00:19:55,650 >> Ja siellä on paljon enemmän Haku kustannuksella että 371 00:19:55,650 --> 00:19:59,820 menee syöttämällä elementti teidän tiiviste nyt, eikö? 372 00:19:59,820 --> 00:20:05,640 Ja nyt kun menet ja yrittää löytää Berry taas, olet menossa hash se, 373 00:20:05,640 --> 00:20:07,742 ja se aikoo sanoa, Oi, katso ämpäri 1, 374 00:20:07,742 --> 00:20:09,700 ja se ei tule olemaan ämpäri 1, niin olet 375 00:20:09,700 --> 00:20:11,970 täytyy kulkea läpi näitä muita. 376 00:20:11,970 --> 00:20:17,720 Joten se on joskus hyödyllistä, mutta useimmissa tapauksissa, 377 00:20:17,720 --> 00:20:22,660 aiomme sanoa, että ketjutus on mitä haluat tehdä. 378 00:20:22,660 --> 00:20:25,520 >> Joten puhuimme aiemmin. 379 00:20:25,520 --> 00:20:27,812 Sain hieman ennen itseäni. 380 00:20:27,812 --> 00:20:33,560 Mutta ketjutus on periaatteessa, että Jokaisen segmentin teidän tiiviste 381 00:20:33,560 --> 00:20:36,120 on vain linkitetty lista. 382 00:20:36,120 --> 00:20:39,660 >> Joten muulla tavoin tai enemmän teknisiä tapa, ajatella hajautustaulun 383 00:20:39,660 --> 00:20:44,490 on, että se on vain joukko linkitettyjä listoja, jotka 384 00:20:44,490 --> 00:20:49,330 Kun olet kirjoittanut sanakirja ja yrität ladata sitä, 385 00:20:49,330 --> 00:20:52,070 Tarkoitan sitä joukko liittyvät luettelot 386 00:20:52,070 --> 00:20:54,390 se on paljon helpompaa voit alustaa. 387 00:20:54,390 --> 00:20:57,680 >> Yleisö: Niin tiiviste on kooltaan ennalta määrätty, 388 00:20:57,680 --> 00:20:58,980 kuten [kuultavissa] kauhat? 389 00:20:58,980 --> 00:20:59,220 >> SPEAKER 1: Oikea. 390 00:20:59,220 --> 00:21:01,655 Joten sillä on tietty määrä kauhat, että olet determine-- 391 00:21:01,655 --> 00:21:03,530 jonka te pitäisi vapaasti pelata. 392 00:21:03,530 --> 00:21:05,269 Se voi olla melko viileä mitä tapahtuu 393 00:21:05,269 --> 00:21:06,810 kuin muutat useita kauhoja. 394 00:21:06,810 --> 00:21:09,410 395 00:21:09,410 --> 00:21:11,510 Mutta joo, se on asettaa useita kauhoja. 396 00:21:11,510 --> 00:21:15,360 Mitä voit sovittaa niin monia elementtejä kuin tarvitset 397 00:21:15,360 --> 00:21:19,350 on tämä erillinen ketjutus missä ovat sidoksissa luettelot kunkin ämpäri. 398 00:21:19,350 --> 00:21:22,850 Tämän tarkoittaa, että tiiviste on täsmälleen koko 399 00:21:22,850 --> 00:21:25,440 että tarvitset sitä olla, eikö? 400 00:21:25,440 --> 00:21:27,358 Se idea liittyy luetteloita. 401 00:21:27,358 --> 00:21:30,850 402 00:21:30,850 --> 00:21:32,480 Cool. 403 00:21:32,480 --> 00:21:38,780 >> Joten kaikki OK siellä? 404 00:21:38,780 --> 00:21:39,801 Selvä. 405 00:21:39,801 --> 00:21:40,300 Ah. 406 00:21:40,300 --> 00:21:41,860 Mitä juuri tapahtui? 407 00:21:41,860 --> 00:21:42,960 Todella nyt. 408 00:21:42,960 --> 00:21:45,250 Arvaa joku tappaa minut. 409 00:21:45,250 --> 00:21:52,060 >> OK aiomme mennä yrittää, jotka ovat vähän hullu. 410 00:21:52,060 --> 00:21:53,140 Pidän hash taulukoita. 411 00:21:53,140 --> 00:21:54,460 Minusta he todella siistiä. 412 00:21:54,460 --> 00:21:56,710 Yrittää ovat viileä, too. 413 00:21:56,710 --> 00:21:59,590 >> Joten ei kukaan muista, mitä kokeilla on? 414 00:21:59,590 --> 00:22:01,740 Olisit mennyt yli se lyhyesti luennolla? 415 00:22:01,740 --> 00:22:04,570 416 00:22:04,570 --> 00:22:06,377 Muistatko sellainen miten se toimii? 417 00:22:06,377 --> 00:22:08,460 Yleisö: Olen vain nyökkää että me ei mennä sen yli. 418 00:22:08,460 --> 00:22:09,626 SPEAKER 1: Emme mene sen yli. 419 00:22:09,626 --> 00:22:13,100 OK, olemme todella menossa Yli se nyt on, mitä sanomme. 420 00:22:13,100 --> 00:22:14,860 >> Yleisö: Se for haku puu. 421 00:22:14,860 --> 00:22:15,280 >> SPEAKER 1: Joo. 422 00:22:15,280 --> 00:22:16,196 Se haku puu. 423 00:22:16,196 --> 00:22:16,960 Mahtava. 424 00:22:16,960 --> 00:22:23,610 Niin yksi asia huomata tässä on se, että me etsivät yksittäisiä merkkejä 425 00:22:23,610 --> 00:22:24,480 täällä, eikö? 426 00:22:24,480 --> 00:22:29,710 >> Joten ennen meidän hajautusfunktio, me katsoivat sanoja kokonaisuutena, 427 00:22:29,710 --> 00:22:32,270 ja nyt etsimme lisää hahmoja, eikö? 428 00:22:32,270 --> 00:22:38,380 Joten meillä on Maxwell tänne ja Mendel. 429 00:22:38,380 --> 00:22:47,840 Joten periaatteessa try-- tapa ajatella tässä on, että jokainen taso täällä 430 00:22:47,840 --> 00:22:49,000 on joukko kirjaimia. 431 00:22:49,000 --> 00:22:53,310 432 00:22:53,310 --> 00:22:55,790 Joten tämä on juurisolmu täällä, eikö? 433 00:22:55,790 --> 00:23:01,980 Tämä on kaikki kirjaimet kirjaimille alussa jokaisen sanan. 434 00:23:01,980 --> 00:23:06,480 >> Ja mitä haluat tehdä, on sanoa, OK, meillä on joitakin M sana. 435 00:23:06,480 --> 00:23:10,590 Aiomme etsiä Maxwell, joten menemme M. ja M-pistettä koko 436 00:23:10,590 --> 00:23:14,800 muu joukko, jossa jokainen sana, niin kauan kuin on olemassa 437 00:23:14,800 --> 00:23:17,044 on sana, joka on koska toinen kirjain, 438 00:23:17,044 --> 00:23:19,460 niin kauan kuin siellä on sana, joka on B toinen kirjain, 439 00:23:19,460 --> 00:23:24,630 se on osoitin menossa joitakin ensi array. 440 00:23:24,630 --> 00:23:29,290 >> Ei luultavasti ole Sana, joka MP jotain, 441 00:23:29,290 --> 00:23:32,980 Joten P-asentoon tässä array, se olisi vain NULL. 442 00:23:32,980 --> 00:23:38,840 Se sanoisi, OK, ei ole sana joka on M seurasi P, OK? 443 00:23:38,840 --> 00:23:43,100 Joten jos ajattelemme sitä, kukin yksi näistä pienemmistä asioista 444 00:23:43,100 --> 00:23:47,990 on itse asiassa yksi näistä suurten taulukoiden välille Z. 445 00:23:47,990 --> 00:23:55,064 Joten mikä voisi olla yksi niistä asioista, joka on eräänlainen epäkohta kokeilla? 446 00:23:55,064 --> 00:23:56,500 >> Yleisö: paljon muistia. 447 00:23:56,500 --> 00:23:59,940 >> SPEAKER 1: Se on ton muistin, eikö? 448 00:23:59,940 --> 00:24:08,750 Jokainen näistä lohkojen tässä edustaa 26 paikkaa, 26 alkiotaulukon. 449 00:24:08,750 --> 00:24:13,680 Joten yrittää saada uskomattoman tilaa raskas. 450 00:24:13,680 --> 00:24:17,100 >> Mutta ne ovat erittäin nopeita. 451 00:24:17,100 --> 00:24:22,540 Niin uskomattoman nopea, mutta todella tilaa tehoton. 452 00:24:22,540 --> 00:24:24,810 Sellainen täytyy selvittää ulos, mitä haluat. 453 00:24:24,810 --> 00:24:29,470 Nämä ovat todella hienoja teidän PSET, mutta ne vievät paljon muistia, 454 00:24:29,470 --> 00:24:30,290 joten käyt kauppaa pois. 455 00:24:30,290 --> 00:24:31,480 Joo? 456 00:24:31,480 --> 00:24:34,300 >> Yleisö: Olisiko mahdollista perustaa kokeilla ja sitten 457 00:24:34,300 --> 00:24:37,967 Kun sinulla on kaikki tiedot siihen, että te need-- 458 00:24:37,967 --> 00:24:39,550 En tiedä, jos se olisi järkevää. 459 00:24:39,550 --> 00:24:42,200 Olin päästä eroon kaikista Null-merkit, mutta sitten 460 00:24:42,200 --> 00:24:42,910 et voi indeksoida them-- 461 00:24:42,910 --> 00:24:43,275 >> SPEAKER 1: Tarvitset silti niitä. 462 00:24:43,275 --> 00:24:44,854 >> YLEISÖ: - samalla tavalla joka kerta. 463 00:24:44,854 --> 00:24:45,520 SPEAKER 1: Joo. 464 00:24:45,520 --> 00:24:50,460 Tarvitset NULL merkkiä antaa te tiedätte, jos siellä ei ole sana siellä. 465 00:24:50,460 --> 00:24:52,040 Ben Oliko sinulla jotain haluat? 466 00:24:52,040 --> 00:24:52,540 OK. 467 00:24:52,540 --> 00:24:54,581 Okei, joten olemme menossa mennä hieman enemmän 468 00:24:54,581 --> 00:24:58,920 osaksi teknisiä yksityiskohtia takana yrittää ja työskennellä läpi esimerkki. 469 00:24:58,920 --> 00:25:01,490 >> OK, joten tämä on sama asia. 470 00:25:01,490 --> 00:25:06,290 Ottaa huomioon, linkitetty lista, tärkein jollaisia ​​of-- mitä sana haluan? - 471 00:25:06,290 --> 00:25:08,350 kuten rakennuspalikka oli solmu. 472 00:25:08,350 --> 00:25:12,280 Vuonna kokeilla, meillä on myös solmu, mutta se on määritelty eri tavoin. 473 00:25:12,280 --> 00:25:17,000 >> Joten meillä on joitakin bool että edustaa onko sana todella 474 00:25:17,000 --> 00:25:23,530 olemassa tässä paikassa, ja sitten meillä on joukko here-- tai pikemminkin, 475 00:25:23,530 --> 00:25:27,840 tämä on osoitin joukko 27 merkkiä. 476 00:25:27,840 --> 00:25:33,339 Ja tämä on, tässä tapauksessa, tämä 27-- Olen varma, että kaikki teistä ovat kuin, odota, 477 00:25:33,339 --> 00:25:34,880 on 26 kirjainta aakkosissa. 478 00:25:34,880 --> 00:25:36,010 Miksi meillä on 27? 479 00:25:36,010 --> 00:25:37,870 >> Joten riippuen tavalla toteuttaa tämän, 480 00:25:37,870 --> 00:25:43,240 tämä on peräisin PSET että sallittu heittomerkit. 481 00:25:43,240 --> 00:25:46,010 Joten siksi ylimääräistä yksi. 482 00:25:46,010 --> 00:25:50,500 Sinulla on myös joissakin tapauksissa null terminaattori 483 00:25:50,500 --> 00:25:53,230 on sisällytetty yhdeksi merkkejä, että se saa olla, 484 00:25:53,230 --> 00:25:56,120 ja se, miten ne tarkistaa katso jos se on sanan lopussa. 485 00:25:56,120 --> 00:26:01,340 Jos olet kiinnostunut, tutustu Kevinin video study.cs50, 486 00:26:01,340 --> 00:26:04,790 sekä Wikipediassa on joitakin hyviä resursseja siellä. 487 00:26:04,790 --> 00:26:09,000 >> Mutta aiomme käydä läpi vain eräänlainen miten voit työskennellä läpi yrittää 488 00:26:09,000 --> 00:26:11,010 jos olet antanut yhden. 489 00:26:11,010 --> 00:26:16,230 Meillä on siis erittäin yksinkertainen täällä, että on ilmaisu "bat" ja "Zoom" niihin. 490 00:26:16,230 --> 00:26:18,920 Ja kuten näemme täällä, Tässä vähän tilaa täällä 491 00:26:18,920 --> 00:26:22,560 edustaa meidän bool että sanoo, kyllä, tämä on sana. 492 00:26:22,560 --> 00:26:27,060 Ja sitten tämä on meidän paneelit merkkiä, eikö? 493 00:26:27,060 --> 00:26:33,480 >> Joten aiomme käydä läpi löytää "bat" tässä yrittää. 494 00:26:33,480 --> 00:26:38,340 Joten alkaa huipulla, eikö? 495 00:26:38,340 --> 00:26:46,290 Ja me tiedämme, että b vastaa Toinen indeksi, toinen elementti 496 00:26:46,290 --> 00:26:47,840 tässä array, koska a ja b. 497 00:26:47,840 --> 00:26:51,340 Joten noin toinen. 498 00:26:51,340 --> 00:26:58,820 >> Ja se sanoo, OK, viileä, seuraa, että otetaan Seuraava array, sillä jos muistamme, 499 00:26:58,820 --> 00:27:02,160 se ei ole, että jokainen näistä sisältää todella elementti. 500 00:27:02,160 --> 00:27:07,110 Jokainen näistä paneelit sisältää osoittimen, eikö? 501 00:27:07,110 --> 00:27:10,030 Se on tärkeä ero tehdä. 502 00:27:10,030 --> 00:27:13,450 >> Tiedän, että tämä on menossa be-- yrittää ovat todella vaikea päästä ensimmäistä kertaa, 503 00:27:13,450 --> 00:27:15,241 joten vaikka tämä on toisen tai kolmannen kerran 504 00:27:15,241 --> 00:27:18,370 ja se on vielä sellainen näennäisestä vaikeaa, 505 00:27:18,370 --> 00:27:21,199 Lupaan jos menet katsella lyhyt jälleen huomenna, 506 00:27:21,199 --> 00:27:22,740 se luultavasti tehdä paljon enemmän järkeä. 507 00:27:22,740 --> 00:27:23,890 Se vie paljon sulattaa. 508 00:27:23,890 --> 00:27:27,800 Olen edelleen joskus olen kuten, odota, mitä kokeilla? 509 00:27:27,800 --> 00:27:29,080 Miten käytän tätä? 510 00:27:29,080 --> 00:27:33,880 >> Olemme siis B tässä tapauksessa joka on meidän toinen indeksi. 511 00:27:33,880 --> 00:27:40,240 Jos meillä olisi vaikkapa C tai d tai mikä tahansa muu kirjain, 512 00:27:40,240 --> 00:27:45,810 meidän täytyy kartoittaa, että takaisin indeksiin meidän array että vastaa. 513 00:27:45,810 --> 00:27:56,930 Joten me ryhtyisimme kuten rchar ja me vain vähennä pois kartoittamaan se 0-25. 514 00:27:56,930 --> 00:27:58,728 Kaikki hyvä miten me kartta meidän merkkiä? 515 00:27:58,728 --> 00:28:00,440 OK. 516 00:28:00,440 --> 00:28:05,980 >> Joten menemme toinen ja me nähdä, että, kyllä, se ei ole NULL. 517 00:28:05,980 --> 00:28:07,780 Voimme siirtyä tähän seuraavaan array. 518 00:28:07,780 --> 00:28:12,300 Joten menemme tähän seuraavaan array täällä. 519 00:28:12,300 --> 00:28:15,500 >> Ja me sanomme, OK, nyt me täytyy nähdä, jos on täällä. 520 00:28:15,500 --> 00:28:18,590 On null tai tekee sen tosiasiallisesti liikkua eteenpäin? 521 00:28:18,590 --> 00:28:21,880 Joten todella liikkuu eteenpäin tässä array. 522 00:28:21,880 --> 00:28:24,570 Ja me sanomme, OK, t on meidän viimeinen kirjain. 523 00:28:24,570 --> 00:28:27,580 Joten menemme t-indeksi. 524 00:28:27,580 --> 00:28:30,120 Ja sitten siirrymme eteenpäin koska siellä on toinen. 525 00:28:30,120 --> 00:28:38,340 Ja tämä toinen sanoo periaatteessa, että kyllä, se sanoo, että on sana here-- 526 00:28:38,340 --> 00:28:41,750 että jos et noudata tätä polku, olet saapunut 527 00:28:41,750 --> 00:28:43,210 klo sana, jonka tiedämme olevan "lepakko". 528 00:28:43,210 --> 00:28:43,800 Kyllä? 529 00:28:43,800 --> 00:28:46,770 >> Yleisö: Onko standardi on, että kuten indeksi 0 ja sitten on eräänlainen 1 530 00:28:46,770 --> 00:28:47,660 tai olla lopussa? 531 00:28:47,660 --> 00:28:48,243 >> SPEAKER 1: Ei. 532 00:28:48,243 --> 00:28:55,360 Joten jos me katsomme taaksepäin meidän ilmoitus täällä, se on bool, 533 00:28:55,360 --> 00:28:59,490 niin se on sen oma elementti omassa solmussa. 534 00:28:59,490 --> 00:29:03,331 Joten se ei ole osa array. 535 00:29:03,331 --> 00:29:03,830 Cool. 536 00:29:03,830 --> 00:29:08,370 Joten kun päätämme sanan ja olemme Tämän array, mitä haluamme tehdä 537 00:29:08,370 --> 00:29:12,807 on tehdä tarkistus on tämä sana. 538 00:29:12,807 --> 00:29:14,390 Ja tässä tapauksessa, se palaisi kyllä. 539 00:29:14,390 --> 00:29:17,220 540 00:29:17,220 --> 00:29:24,090 >> Niin Komitea suosittelee, että me tiedämme, että "eläintarha" - Tiedämme ihmisinä että "eläintarha" on sana, 541 00:29:24,090 --> 00:29:24,820 oikeassa? 542 00:29:24,820 --> 00:29:28,990 Mutta eivät yritä täällä olisi sanoa, ei, se ei ole. 543 00:29:28,990 --> 00:29:33,980 Ja se sanoisi, että koska me eivät ole nimenneet sitä sanaa täällä. 544 00:29:33,980 --> 00:29:40,440 Vaikka emme voi kulkea kautta tähän array, 545 00:29:40,440 --> 00:29:43,890 tämä yrittää sanoa, että ei, eläintarha ei ole sanakirjaa 546 00:29:43,890 --> 00:29:47,070 koska meillä ei nimennyt sen sellaiseksi. 547 00:29:47,070 --> 00:29:52,870 >> Joten yksi tapa tehdä that-- Anteeksi, tämä yksi. 548 00:29:52,870 --> 00:29:59,450 Joten tässä tapauksessa, "eläintarha" ei ole sana, mutta se on meidän yrittää. 549 00:29:59,450 --> 00:30:05,690 Mutta tässä yksi, että haluamme sitä käyttöön sana "sauna", mitä tapahtuu 550 00:30:05,690 --> 00:30:08,260 on me seuraamme through-- b, t. 551 00:30:08,260 --> 00:30:11,820 Olemme tässä array, ja menemme etsimään h. 552 00:30:11,820 --> 00:30:15,220 >> Tässä tapauksessa, kun katsokaa osoitin h, 553 00:30:15,220 --> 00:30:17,890 se osoittaa NULL, OK? 554 00:30:17,890 --> 00:30:20,780 Joten jos se on nimenomaisesti viittaa toiseen array, 555 00:30:20,780 --> 00:30:25,000 oletat, että kaikki osoittimet Tässä array osoittavat nollaamaan. 556 00:30:25,000 --> 00:30:28,270 Joten tässä tapauksessa, h osoittaa nollaamaan joten emme voi tehdä mitään, 557 00:30:28,270 --> 00:30:31,540 niin se myös palauttaa väärä, "kylpy" ei ole täällä. 558 00:30:31,540 --> 00:30:34,102 559 00:30:34,102 --> 00:30:35,810 Joten nyt olemme todella menossa läpi 560 00:30:35,810 --> 00:30:39,790 miten me oikeastaan ​​sanoa että "eläintarha" on meidän yrittää. 561 00:30:39,790 --> 00:30:42,920 Miten voimme lisätä "eläintarha" meidän kokeilla? 562 00:30:42,920 --> 00:30:47,810 Niin samalla tavalla, että aloitimme meidän linkitetty lista, aloitamme juureen. 563 00:30:47,810 --> 00:30:50,600 Jos olet epävarma, alkavat juuri näitä asioita. 564 00:30:50,600 --> 00:30:53,330 >> Ja me sanomme, OK, z. 565 00:30:53,330 --> 00:30:55,650 z olemassa tässä, ja se tekee. 566 00:30:55,650 --> 00:30:58,370 Joten olet siirtyessään seuraava array, OK? 567 00:30:58,370 --> 00:31:01,482 Ja sitten seuraava, sanomme, OK, ei o olemassa? 568 00:31:01,482 --> 00:31:03,000 Se tekee. 569 00:31:03,000 --> 00:31:04,330 Tämä taas. 570 00:31:04,330 --> 00:31:08,670 >> Ja niin meidän seuraava, olemme sanoneet, OK, "eläintarha" on jo olemassa täällä. 571 00:31:08,670 --> 00:31:12,440 Kaikki meidän täytyy tehdä, on asettaa tämän yhdenvertaisen on totta, että on olemassa sana siellä. 572 00:31:12,440 --> 00:31:15,260 Jos olisit seurannut kaiken jopa ennen tätä hetkeä, 573 00:31:15,260 --> 00:31:17,030 se sana, niin juuri aseta se yhtä tällaista. 574 00:31:17,030 --> 00:31:17,530 Kyllä? 575 00:31:17,530 --> 00:31:22,550 >> Yleisö: Niin tekee, että tarkoittaa, että "ba" on sana myös? 576 00:31:22,550 --> 00:31:24,120 >> SPEAKER 1: Ei. 577 00:31:24,120 --> 00:31:28,870 Joten tässä tapauksessa, "ba" saisimme täällä, sanoisimme on se sana, 578 00:31:28,870 --> 00:31:31,590 ja se olisi silti mitään. 579 00:31:31,590 --> 00:31:32,822 OK? 580 00:31:32,822 --> 00:31:33,740 Mmhmm? 581 00:31:33,740 --> 00:31:36,360 >> Yleisö: Niin kun se on sana ja sanot kyllä, niin se 582 00:31:36,360 --> 00:31:38,380 sisältää mennä m? 583 00:31:38,380 --> 00:31:42,260 >> SPEAKER 1: Eli tämä on tekemistä with-- lataat tämän. 584 00:31:42,260 --> 00:31:43,640 Sanot "eläintarha" on sana. 585 00:31:43,640 --> 00:31:47,020 Kun menet check-- kuten, että haluat sanoa, 586 00:31:47,020 --> 00:31:49,400 ei "eläintarha" olemassa tässä sanakirjassa? 587 00:31:49,400 --> 00:31:54,200 Olet vain menossa etsimään "eläintarha" ja sitten tarkistaa, jos se on sana. 588 00:31:54,200 --> 00:31:57,291 Et koskaan tule liikkumaan läpi m, koska se ei ole 589 00:31:57,291 --> 00:31:58,290 mitä etsit. 590 00:31:58,290 --> 00:32:02,690 591 00:32:02,690 --> 00:32:08,070 >> Joten jos me todella halusimme lisätä "kylpy" tähän kokeilla, 592 00:32:08,070 --> 00:32:11,390 tekisimme saman asian kuten teimme "eläintarha" 593 00:32:11,390 --> 00:32:15,380 paitsi näkisimme, että kun me yrittää saada h, sitä ei ole olemassa. 594 00:32:15,380 --> 00:32:20,090 Voit siis ajatella tätä yrittää lisätä uuden solmun linkitetyn listan, 595 00:32:20,090 --> 00:32:27,210 joten meidän olisi lisätä toisen yksi näistä paneelit, kuten niin. 596 00:32:27,210 --> 00:32:35,670 Ja mitä sitten teemme, me vain asettaa h osa tätä array osoittaa tämän. 597 00:32:35,670 --> 00:32:39,430 >> Ja sitten mitä haluamme tehdä täällä? 598 00:32:39,430 --> 00:32:43,110 Lisää se yhtä totta koska se on sana. 599 00:32:43,110 --> 00:32:46,350 600 00:32:46,350 --> 00:32:48,150 Cool. 601 00:32:48,150 --> 00:32:48,700 Tiedän. 602 00:32:48,700 --> 00:32:51,170 Yrittää eivät ole kaikkein jännittävä. 603 00:32:51,170 --> 00:32:54,250 Luota minuun, tiedän. 604 00:32:54,250 --> 00:32:58,040 >> Niin yksi asia on ymmärrettävä kanssa yrittää, Sanoin, ne ovat hyvin tehokkaita. 605 00:32:58,040 --> 00:33:00,080 Joten olemme nähneet ne vievät ton tilaa. 606 00:33:00,080 --> 00:33:01,370 He jotenkin hämmentävää. 607 00:33:01,370 --> 00:33:03,367 Joten miksi emme koskaan käyttää näitä? 608 00:33:03,367 --> 00:33:05,450 Käytämme näitä, koska he uskomattoman tehokas. 609 00:33:05,450 --> 00:33:08,130 >> Joten jos olet koskaan etsimässä ylös sana, olet vain 610 00:33:08,130 --> 00:33:10,450 jota rajoittavat pituus sana. 611 00:33:10,450 --> 00:33:15,210 Joten jos etsit sana, joka on pituudeltaan viisi, 612 00:33:15,210 --> 00:33:20,940 olet vain koskaan menossa on tehdä korkeintaan viisi vertailuja, OK? 613 00:33:20,940 --> 00:33:25,780 Niin se tekee periaatteessa vakio. 614 00:33:25,780 --> 00:33:29,150 Kuten paikoilleen ja haku ovat periaatteessa vakio aikaa. 615 00:33:29,150 --> 00:33:33,750 >> Joten jos et voi koskaan saada jotain vakioaikavälein, 616 00:33:33,750 --> 00:33:35,150 joka on yhtä hyvä kuin sen saa. 617 00:33:35,150 --> 00:33:37,990 Et voi saada parempaa kuin vakio aikaa näitä asioita. 618 00:33:37,990 --> 00:33:43,150 Niin että on yksi valtava ansioita yrittää. 619 00:33:43,150 --> 00:33:46,780 >> Mutta se on paljon tilaa. 620 00:33:46,780 --> 00:33:50,380 Joten sinulla sellainen on päätettävä mikä on sinulle tärkeää. 621 00:33:50,380 --> 00:33:54,700 Ja nykypäivän tietokoneissa, tila, joka yrittää saattaa kestää jopa 622 00:33:54,700 --> 00:33:57,740 ehkä ei vaikuta teille, että paljon, mutta ehkä 623 00:33:57,740 --> 00:34:01,350 olet tekemisissä jotain joka on paljon, paljon enemmän asioita, 624 00:34:01,350 --> 00:34:02,810 ja yritä ei ole järkevää. 625 00:34:02,810 --> 00:34:03,000 Kyllä? 626 00:34:03,000 --> 00:34:05,610 >> Yleisö: Odota, niin sinulla on 26 kirjaimet joka ikinen? 627 00:34:05,610 --> 00:34:07,440 >> SPEAKER 1: mmhmm. 628 00:34:07,440 --> 00:34:08,570 Joo, olet 26. 629 00:34:08,570 --> 00:34:16,984 Sinulla on joitakin on sana merkki ja sitten Sinulla on 26 viitteitä jokainen. 630 00:34:16,984 --> 00:34:17,775 Ja he point-- 631 00:34:17,775 --> 00:34:20,280 >> Yleisö: Ja jokainen 26, heillä kummallakin on 26? 632 00:34:20,280 --> 00:34:21,500 >> SPEAKER 1: Kyllä. 633 00:34:21,500 --> 00:34:27,460 Ja siksi, kuin pystyt katso, se laajenee melko nopeasti. 634 00:34:27,460 --> 00:34:28,130 Selvä. 635 00:34:28,130 --> 00:34:32,524 Joten aiomme päästä puita, jotka Tunnen on helpompaa ja luultavasti 636 00:34:32,524 --> 00:34:36,150 olla mukava pieni armonaikaa alkaen yrittää siellä. 637 00:34:36,150 --> 00:34:39,620 Joten toivottavasti useimmat teistä nähnyt puun ennen. 638 00:34:39,620 --> 00:34:41,820 Ei niinku ihan ulkopuolella olevat, jotka minä 639 00:34:41,820 --> 00:34:44,340 en tiedä, jos joku meni ulkona äskettäin. 640 00:34:44,340 --> 00:34:49,230 Kävin omena poiminta tänä viikonloppuna, ja Jestas, se oli kaunis. 641 00:34:49,230 --> 00:34:52,250 En tiennyt lehdet voisi näyttää, että aika. 642 00:34:52,250 --> 00:34:53,610 >> Joten tämä on vain puu, eikö? 643 00:34:53,610 --> 00:34:56,790 Se on vain joku solmu, ja se viittaa joukko muita solmuja. 644 00:34:56,790 --> 00:34:59,570 Kuten näette täällä, tämä on eräänlainen toistuva teema. 645 00:34:59,570 --> 00:35:03,720 Solmut osoittava solmut on eräänlainen pohjimmiltaan monien tietorakenteita. 646 00:35:03,720 --> 00:35:06,670 Se vain riippuu siitä, miten me ne viittaavat toisiinsa 647 00:35:06,670 --> 00:35:08,600 ja miten me kulkea niiden kautta, ja miten me 648 00:35:08,600 --> 00:35:14,500 aseta asioita, joka määrittää niiden ominaisuudet ovat erilaiset. 649 00:35:14,500 --> 00:35:17,600 >> Joten vain joitakin terminologiaa, jota olen käyttänyt aiemmin. 650 00:35:17,600 --> 00:35:20,010 Niin juuri on mitä on huipulla. 651 00:35:20,010 --> 00:35:21,200 se missä olemme aina aloittaa. 652 00:35:21,200 --> 00:35:23,610 Voit ajatella sitä päätä myös. 653 00:35:23,610 --> 00:35:28,750 Mutta puita, meillä on taipumus kutsuvat sitä juuri. 654 00:35:28,750 --> 00:35:32,820 >> Mitään alareunassa here-- aivan, erittäin bottom-- 655 00:35:32,820 --> 00:35:34,500 pidetään lehtiä. 656 00:35:34,500 --> 00:35:37,210 Niin se menee yhdessä koko puun juttu, eikö? 657 00:35:37,210 --> 00:35:39,860 Lehdet ovat reunoilla teidän puu. 658 00:35:39,860 --> 00:35:45,820 >> Ja sitten meillä on myös pari Ehdot puhua solmuja suhteessa 659 00:35:45,820 --> 00:35:46,680 toisiinsa. 660 00:35:46,680 --> 00:35:49,700 Joten meillä on vanhempi, lapset ja sisarukset. 661 00:35:49,700 --> 00:35:56,260 Joten tässä tapauksessa, 3 on vanhempi 5, 6 ja 7. 662 00:35:56,260 --> 00:36:00,370 Joten vanhempi on mitä on yhden askeleen edellä mitä olet 663 00:36:00,370 --> 00:36:02,940 viitaten, niin juuri kuten sukupuu. 664 00:36:02,940 --> 00:36:07,090 Toivottavasti tämä on kaikki hieman hieman enemmän intuitiivinen kuin yrittää. 665 00:36:07,090 --> 00:36:10,970 >> Sisarukset ovat kaikki, jotka ovat sama vanhempi, eikö? 666 00:36:10,970 --> 00:36:13,470 He ovat samalla tasolla täällä. 667 00:36:13,470 --> 00:36:16,960 Ja sitten, kun olin sanomalla, lapset ovat vain 668 00:36:16,960 --> 00:36:22,630 mikä on yksi askel alla -solmu, OK? 669 00:36:22,630 --> 00:36:23,470 Cool. 670 00:36:23,470 --> 00:36:25,610 Joten binääripuu. 671 00:36:25,610 --> 00:36:31,450 Voiko kukaan arvata yksi ominaisuudet binääripuun? 672 00:36:31,450 --> 00:36:32,770 >> Yleisö: Max kaksi lehteä. 673 00:36:32,770 --> 00:36:33,478 >> SPEAKER 1: Oikea. 674 00:36:33,478 --> 00:36:34,640 Joten max kaksi lehteä. 675 00:36:34,640 --> 00:36:39,730 Joten tässä yksi ennen, meillä oli tämä yksi että oli kolme, mutta binaarisen puun, 676 00:36:39,730 --> 00:36:45,000 sinulla on max kaksi lasta vanhempi, eikö? 677 00:36:45,000 --> 00:36:46,970 On toinenkin mielenkiintoinen ominaisuus. 678 00:36:46,970 --> 00:36:51,550 Tietääkö kukaan, että? 679 00:36:51,550 --> 00:36:52,620 Binääripuu. 680 00:36:52,620 --> 00:37:00,350 >> Joten binääripuu on kaikki on the-- tämä ei ole sorted-- 681 00:37:00,350 --> 00:37:05,320 mutta lajiteltu binääripuun, kaiken oikealla 682 00:37:05,320 --> 00:37:08,530 on suurempi kuin vanhemman, ja kaikki vasemmalla 683 00:37:08,530 --> 00:37:10,035 on vähemmän kuin vanhempi. 684 00:37:10,035 --> 00:37:15,690 Ja että on ollut tietokilpailu kysymys ennen, niin hyvä tietää. 685 00:37:15,690 --> 00:37:19,500 Joten miten me määrittelemme tämän, taas, meillä on toinen solmu. 686 00:37:19,500 --> 00:37:21,880 Tämä näyttää hyvin samankaltainen kuin mitä? 687 00:37:21,880 --> 00:37:28,336 688 00:37:28,336 --> 00:37:28,836 Kaksin verroin 689 00:37:28,836 --> 00:37:29,320 >> Yleisö: Linked luettelot 690 00:37:29,320 --> 00:37:31,100 >> SPEAKER 1: kaksinkertainen linkitetty lista, eikö? 691 00:37:31,100 --> 00:37:33,690 Joten jos me korvata tämän edellisen ja seuraavan, 692 00:37:33,690 --> 00:37:35,670 tämä olisi kaksin verroin linkitetty lista. 693 00:37:35,670 --> 00:37:40,125 Mutta tässä tapauksessa, me oikeastaan on vasen ja oikea ja se on siinä. 694 00:37:40,125 --> 00:37:41,500 Muuten, se on täsmälleen sama. 695 00:37:41,500 --> 00:37:43,374 Meillä on edelleen elementin etsit, 696 00:37:43,374 --> 00:37:45,988 ja sinulla on vain kaksi osoitinta menossa mitä seuraavaksi. 697 00:37:45,988 --> 00:37:49,210 698 00:37:49,210 --> 00:37:51,870 Joo, niin binäärihakupuu. 699 00:37:51,870 --> 00:37:57,665 Jos huomaamme, kaiken täällä on enemmän than-- 700 00:37:57,665 --> 00:37:59,850 tai kaiken heti on täällä 701 00:37:59,850 --> 00:38:02,840 on suurempi kuin, kaikki tässä alle. 702 00:38:02,840 --> 00:38:06,980 703 00:38:06,980 --> 00:38:14,000 >> Joten jos me etsiä, se pitäisi näyttää melkein binäärihaku 704 00:38:14,000 --> 00:38:14,910 täällä, eikö? 705 00:38:14,910 --> 00:38:17,640 Paitsi sijaan etsivät klo puoli array, 706 00:38:17,640 --> 00:38:21,720 Olemme vain katsomalla joko vasen puolella tai oikealla puolella puu. 707 00:38:21,720 --> 00:38:24,850 Joten se saa hieman yksinkertaisempi, luulen. 708 00:38:24,850 --> 00:38:29,300 >> Joten jos juuri on NULL, ilmeisesti se on vain väärä. 709 00:38:29,300 --> 00:38:33,470 Ja jos se on olemassa, ilmeisesti se on totta. 710 00:38:33,470 --> 00:38:35,320 Jos se on alle, haemme vasemmalle. 711 00:38:35,320 --> 00:38:37,070 Jos se on suurempi kuin, haemme oikeutta. 712 00:38:37,070 --> 00:38:39,890 Se on aivan kuin binäärihaku, vain eri tietorakenne 713 00:38:39,890 --> 00:38:40,600 että käytämme. 714 00:38:40,600 --> 00:38:42,790 Sen sijaan, array, se on vain binääripuu. 715 00:38:42,790 --> 00:38:45,820 716 00:38:45,820 --> 00:38:48,090 >> OK, pinot. 717 00:38:48,090 --> 00:38:51,550 Ja myös näyttää siltä, ​​että me saattaa olla hieman aikaa. 718 00:38:51,550 --> 00:38:54,460 Jos teemme niin, olen onnellinen mennä minkä tahansa tämän uudelleen. 719 00:38:54,460 --> 00:38:56,856 OK, niin pärjää. 720 00:38:56,856 --> 00:39:02,695 Muistaako kukaan mitä stacks-- mitään ominaisuuksia pino? 721 00:39:02,695 --> 00:39:05,550 722 00:39:05,550 --> 00:39:10,400 >> OK, joten useimmat meistä, luulen, syödä ruokailu halls-- 723 00:39:10,400 --> 00:39:13,100 niin paljon kuin emme haluaisi. 724 00:39:13,100 --> 00:39:16,900 Mutta tietenkin, voit ajatella pino kirjaimellisesti aivan kuten pino tarjottimia 725 00:39:16,900 --> 00:39:18,460 tai pino asioita. 726 00:39:18,460 --> 00:39:21,820 Ja mikä on tärkeää on ymmärrettävä, että se on 727 00:39:21,820 --> 00:39:26,850 something-- ominaisuus että me kutsumme sitä by-- on LIFO. 728 00:39:26,850 --> 00:39:28,450 Onko kukaan tiedä, mitä se tarkoittaa? 729 00:39:28,450 --> 00:39:29,070 Mmhmm? 730 00:39:29,070 --> 00:39:30,650 >> Yleisö: last in, first out. 731 00:39:30,650 --> 00:39:32,250 >> SPEAKER 1: Oikea, last in, first out. 732 00:39:32,250 --> 00:39:36,585 Joten jos me tiedämme, jos olemme pinoaminen asioita ylös, helpointa napata off-- 733 00:39:36,585 --> 00:39:39,570 ja ehkä ainoa asia, jota emme voi napata pois, jos meidän pino on iso enough-- 734 00:39:39,570 --> 00:39:40,850 on, että top elementti. 735 00:39:40,850 --> 00:39:43,460 Joten mitä laitettiin last-- kuten näemme täällä, 736 00:39:43,460 --> 00:39:46,370 mikä oli ajanut useimmissa recently-- on 737 00:39:46,370 --> 00:39:51,160 olemaan ensimmäinen asia, että me kupsahtaa, OK? 738 00:39:51,160 --> 00:39:56,324 >> Joten mitä meillä täällä on toinen typedef struct. 739 00:39:56,324 --> 00:39:58,740 Tämä on todella aivan kuten pikakurssin tietorakenne, 740 00:39:58,740 --> 00:40:01,650 joten siellä on paljon heitetään sinua kaverit. 741 00:40:01,650 --> 00:40:02,540 Tiedän. 742 00:40:02,540 --> 00:40:04,970 Niin vielä toinen struct. 743 00:40:04,970 --> 00:40:06,740 Yay rakenteita. 744 00:40:06,740 --> 00:40:16,660 >> Ja tässä tapauksessa, se on jonkin verran osoitin array, joka on jonkin verran kapasiteettia. 745 00:40:16,660 --> 00:40:20,830 Joten tämä on meidän pino täällä, kuten meidän todellinen array 746 00:40:20,830 --> 00:40:22,520 että pitelee meidän elementtejä. 747 00:40:22,520 --> 00:40:24,850 Ja sitten täällä on joitakin koko. 748 00:40:24,850 --> 00:40:31,170 >> Ja tyypillisesti, jotka haluat säilyttää Seuraa kuinka suuri pino on 749 00:40:31,170 --> 00:40:36,180 koska mitä se tulee sallia voit tehdä on, jos tiedät koon, 750 00:40:36,180 --> 00:40:39,170 sen avulla voit sanoa, OK, olen teholla? 751 00:40:39,170 --> 00:40:40,570 Voinko lisätä mitään muuta? 752 00:40:40,570 --> 00:40:44,650 Ja se kertoo myös jossa ylin stäkistäsi 753 00:40:44,650 --> 00:40:48,180 on niin tiedät mitä voi itse ottaa pois. 754 00:40:48,180 --> 00:40:51,760 Ja se todella tulee olla hieman selvempi täällä. 755 00:40:51,760 --> 00:40:57,350 >> Joten push, yksi asia, jos olivat koskaan toteuttaa push, 756 00:40:57,350 --> 00:41:01,330 kuten juuri kerroin, sinun pino on rajoitettu koko, eikö? 757 00:41:01,330 --> 00:41:03,990 Meidän joukko oli jonkin verran kapasiteettia. 758 00:41:03,990 --> 00:41:04,910 Se jono. 759 00:41:04,910 --> 00:41:08,930 Se on kiinteä koko, joten meidän täytyy varmista, että emme ole entistä enemmän 760 00:41:08,930 --> 00:41:11,950 meidän array kuin me todella on tilaa. 761 00:41:11,950 --> 00:41:16,900 >> Joten kun luot push toiminto, ensimmäinen asia mitä tehdä, on sanoa, OK, 762 00:41:16,900 --> 00:41:18,570 minulla on tilaa minun pino? 763 00:41:18,570 --> 00:41:23,330 Koska jos en, anteeksi, En voi tallentaa elementti. 764 00:41:23,330 --> 00:41:28,980 Jos en, niin haluat tallentaa se on pinon päällä, eikö? 765 00:41:28,980 --> 00:41:31,325 >> Ja siksi olemme seurata meidän kokoa. 766 00:41:31,325 --> 00:41:35,290 Jos emme seurata meidän kokoa, emme tiedä, mihin se. 767 00:41:35,290 --> 00:41:39,035 Emme tiedä, kuinka paljon ovat meidän array jo. 768 00:41:39,035 --> 00:41:41,410 Kuten ilmeisesti on olemassa keinoja että ehkä sinä voisit tehdä sen. 769 00:41:41,410 --> 00:41:44,610 Voisit alustaa kaiken NULL ja sitten tarkistaa uusimmat NULL, 770 00:41:44,610 --> 00:41:47,950 mutta paljon helpompi asia on juuri sanoa, OK, seurata koko. 771 00:41:47,950 --> 00:41:51,840 Kuten Tiedän, että olen neljä elementtiä minun array, niin seuraava asia 772 00:41:51,840 --> 00:41:55,930 että laitamme, olemme aiotaan säilyttää indeksillä 4. 773 00:41:55,930 --> 00:42:00,940 Ja sitten, tietenkin, tämä tarkoittaa, että olet onnistuneesti ajanut jotain 774 00:42:00,940 --> 00:42:03,320 päälle pinoon, mutta et haluavat lisätä kokoa 775 00:42:03,320 --> 00:42:08,880 jotta tiedät missä olet niin että voit työntää enemmän asioita. 776 00:42:08,880 --> 00:42:12,730 >> Joten jos yritämme pop jotain pois pinosta, 777 00:42:12,730 --> 00:42:16,072 mikä voisi olla ensimmäinen asia että haluamme tarkistaa? 778 00:42:16,072 --> 00:42:18,030 Yrität ottaa jotain pois teidän pinoon. 779 00:42:18,030 --> 00:42:21,710 780 00:42:21,710 --> 00:42:24,781 Oletko varma, että siellä on jotain teidän pinoon? 781 00:42:24,781 --> 00:42:25,280 Ei. 782 00:42:25,280 --> 00:42:26,894 Mikä siis haluamme tarkistaa? 783 00:42:26,894 --> 00:42:27,810 >> Yleisö: [kuulumaton]. 784 00:42:27,810 --> 00:42:29,880 SPEAKER 1: Tarkista koko? 785 00:42:29,880 --> 00:42:31,840 Koko. 786 00:42:31,840 --> 00:42:38,520 Joten haluamme tarkistaa, onko Meidän koko on suurempi kuin 0, OK? 787 00:42:38,520 --> 00:42:44,970 Ja jos on, niin me haluamme vähentää meidän kokoa 0 ja palata siihen. 788 00:42:44,970 --> 00:42:45,840 Miksi? 789 00:42:45,840 --> 00:42:49,950 >> Ensimmäisessä vaihtoehdossa olimme työntää, me työnnetään se 790 00:42:49,950 --> 00:42:52,460 päälle koko ja sitten päivitetään koko. 791 00:42:52,460 --> 00:42:57,850 Tässä tapauksessa olemme decrementing koko ja sitten ottaa se pois, nyppiminen se 792 00:42:57,850 --> 00:42:58,952 meidän array. 793 00:42:58,952 --> 00:42:59,826 Miksi voisimme tehdä? 794 00:42:59,826 --> 00:43:04,800 795 00:43:04,800 --> 00:43:11,811 Joten jos minulla on yksi asia minun pino, mikä olisi minun kokoa tässä vaiheessa? 796 00:43:11,811 --> 00:43:13,140 1. 797 00:43:13,140 --> 00:43:15,180 >> Ja missä on elementti 1 tallennetaan? 798 00:43:15,180 --> 00:43:17,621 Mitä indeksi? 799 00:43:17,621 --> 00:43:18,120 Yleisö: 0. 800 00:43:18,120 --> 00:43:19,060 SPEAKER 1: 0. 801 00:43:19,060 --> 00:43:22,800 Joten tässä tapauksessa, me aina täytyy tehdä sure-- 802 00:43:22,800 --> 00:43:27,630 sijaan palaavat koko miinus 1, koska me 803 00:43:27,630 --> 00:43:31,730 tietää, että tekijä on menossa säilytettävä 1 vähemmän 804 00:43:31,730 --> 00:43:34,705 mitä meidän koko on, tämä vain hoitaa homman. 805 00:43:34,705 --> 00:43:36,080 Se on hieman enemmän tyylikäs tavalla. 806 00:43:36,080 --> 00:43:41,220 Ja me vain dekrementoidaan meidän koon ja palata sitten koko. 807 00:43:41,220 --> 00:43:42,330 Mmhmm? 808 00:43:42,330 --> 00:43:45,300 >> Yleisö: Luulen vain yleisesti, Miksi näin tietorakenne 809 00:43:45,300 --> 00:43:47,800 olla hyödyllistä? 810 00:43:47,800 --> 00:43:50,660 >> SPEAKER 1: Se riippuu yhteydessä. 811 00:43:50,660 --> 00:43:57,420 Joten joidenkin teoriaa, jos olet työskennellyt with-- OK, 812 00:43:57,420 --> 00:44:02,750 anna minun nähdä, jos siellä on hyödyllistä yksi että on hyödyllistä enemmän kuin ulkopuolella 813 00:44:02,750 --> 00:44:05,420 CS. 814 00:44:05,420 --> 00:44:15,780 Pinot, aina kun tarvitset seurata jotain, 815 00:44:15,780 --> 00:44:20,456 on viimeksi lisätty on kun olet menossa haluavat käyttää pinon. 816 00:44:20,456 --> 00:44:24,770 >> Ja en voi ajatella hyvä Esimerkkinä juuri nyt. 817 00:44:24,770 --> 00:44:29,955 Mutta aina viimeisimmän asia on tärkeintä sinulle, 818 00:44:29,955 --> 00:44:31,705 se kun pino tulee olemaan hyötyä. 819 00:44:31,705 --> 00:44:35,797 820 00:44:35,797 --> 00:44:39,330 Yritän ajatella, jos siellä on hyvä tähän. 821 00:44:39,330 --> 00:44:43,720 Jos ajattelen hyvä esimerkki seuraavassa 20 minuuttia, aion ehdottomasti kertoa. 822 00:44:43,720 --> 00:44:49,455 >> Mutta kaiken kaikkiaan, jos on jotain, kuten sanoin useimmat, jossa viimeisin 823 00:44:49,455 --> 00:44:52,470 on tärkeintä, että on jossa pino tulee pelata. 824 00:44:52,470 --> 00:44:58,860 Ottaa huomioon, että jonot ovat tavallaan päinvastainen. 825 00:44:58,860 --> 00:44:59,870 Ja kaikki pikku koirat. 826 00:44:59,870 --> 00:45:00,890 Eikö tämä suuri, eikö? 827 00:45:00,890 --> 00:45:03,299 Tunnen pitäisi vain pupu video 828 00:45:03,299 --> 00:45:05,090 aivan keskellä osio te 829 00:45:05,090 --> 00:45:08,870 koska tämä on voimakas kohta. 830 00:45:08,870 --> 00:45:10,480 >> Niin jono. 831 00:45:10,480 --> 00:45:12,710 Periaatteessa jono on kuin viiva. 832 00:45:12,710 --> 00:45:15,780 Te varmasti käyttää tätä jokapäiväistä, aivan kuten meidän ruokasalia. 833 00:45:15,780 --> 00:45:18,160 Joten meidän täytyy mennä ja saada meidän tarjottimet, olen 834 00:45:18,160 --> 00:45:21,260 että sinulla on jonottaa pyyhkäistä tai saada ruokaa. 835 00:45:21,260 --> 00:45:24,650 >> Joten ero täällä on, että tämä on FIFO. 836 00:45:24,650 --> 00:45:30,090 Joten jos LIFO viimeksi vuonna, ensin out, FIFO on first in, first out. 837 00:45:30,090 --> 00:45:33,400 Joten tämä on silloin, mitä laitat ensimmäisessä on tärkein. 838 00:45:33,400 --> 00:45:35,540 Joten jos odottivat vuonna line-- voitte 839 00:45:35,540 --> 00:45:39,130 Kuvittele, jos meni mene saada uusi iPhone 840 00:45:39,130 --> 00:45:42,800 ja se oli pino jossa viimeinen henkilö linjassa sai sen ensin, 841 00:45:42,800 --> 00:45:44,160 ihmiset tappavat toisiaan. 842 00:45:44,160 --> 00:45:49,800 >> Joten FIFO, olemme kaikki hyvin tuttuja kanssa todellisessa maailmassa täällä, 843 00:45:49,800 --> 00:45:54,930 ja se kaikki on tekemistä itse Tällainen uudestaan ​​tämän koko linjan 844 00:45:54,930 --> 00:45:56,900 ja jonotuksen rakenne. 845 00:45:56,900 --> 00:46:02,390 Joten taas pino, meillä on push ja pop. 846 00:46:02,390 --> 00:46:06,440 Kanssa jonoon, meillä on enqueue ja dequeue. 847 00:46:06,440 --> 00:46:10,910 Joten enqueue tarkoittaa periaatteessa laita se päälle takaisin, 848 00:46:10,910 --> 00:46:13,680 ja dequeue keinot toteuttaa pois edestä. 849 00:46:13,680 --> 00:46:18,680 Joten meidän tietorakenne on hieman monimutkaisempi. 850 00:46:18,680 --> 00:46:21,060 Meillä on toinen asia pitää kirjaa. 851 00:46:21,060 --> 00:46:25,950 >> Joten ilman päätä, tämä Juuri pino, eikö? 852 00:46:25,950 --> 00:46:27,900 Tämä on sama rakenne kuin pino. 853 00:46:27,900 --> 00:46:32,480 Ainoa asia erilainen nyt on meidän on tämä pää, joka mitä luulet 854 00:46:32,480 --> 00:46:34,272 aikoo seurata? 855 00:46:34,272 --> 00:46:35,510 >> Yleisö: ensimmäinen. 856 00:46:35,510 --> 00:46:38,685 >> SPEAKER 1: Oikea, Ensimmäinen asia, että panemme. 857 00:46:38,685 --> 00:46:41,130 Vetäjänä jonossa. 858 00:46:41,130 --> 00:46:42,240 Kuka on ensimmäisenä jonossa. 859 00:46:42,240 --> 00:46:45,300 860 00:46:45,300 --> 00:46:49,420 Okei, joten jos teemme enqueue. 861 00:46:49,420 --> 00:46:52,720 862 00:46:52,720 --> 00:46:55,920 Jälleen, joilla on jokin Näiden tietorakenteita, 863 00:46:55,920 --> 00:46:59,760 koska olemme tekemisissä array, Meidän täytyy tarkistaa, jos meillä on tilaa. 864 00:46:59,760 --> 00:47:03,290 >> Tämä on ikään kuin kertasin te, jos avaat tiedoston, 865 00:47:03,290 --> 00:47:04,760 sinun täytyy tarkistaa null. 866 00:47:04,760 --> 00:47:08,330 Mitään näistä pinot ja jonot, tarvitset 867 00:47:08,330 --> 00:47:13,420 onko siellä tilaa, koska olemme kyseessä on kiinteä koko array, 868 00:47:13,420 --> 00:47:16,030 kuten näemme here-- 0, 1 kaikki jopa 5. 869 00:47:16,030 --> 00:47:20,690 Joten mitä me teemme tässä tapauksessa on tarkistaa nähdä, jos meillä on vielä tilaa. 870 00:47:20,690 --> 00:47:23,110 On meidän koko pienempi kuin kapasiteetti? 871 00:47:23,110 --> 00:47:28,480 >> Jos näin on, meidän täytyy säilyttää se hännän ja päivitämme koko. 872 00:47:28,480 --> 00:47:30,250 Joten mikä voisi häntä olla tässä tapauksessa? 873 00:47:30,250 --> 00:47:32,360 Se ei ole erikseen kirjoitettu ulos. 874 00:47:32,360 --> 00:47:33,380 Miten me tallentaa sen? 875 00:47:33,380 --> 00:47:34,928 Mikä olisi hännän olla? 876 00:47:34,928 --> 00:47:38,600 877 00:47:38,600 --> 00:47:40,190 >> Joten kävele tässä esimerkissä. 878 00:47:40,190 --> 00:47:44,590 Joten tämä on taulukon koko 6, eikö? 879 00:47:44,590 --> 00:47:49,220 Ja meillä on juuri nyt, meidän koko on 5. 880 00:47:49,220 --> 00:47:55,240 Ja kun panemme sen, se tulee mennä viidenteen indeksi, eikö? 881 00:47:55,240 --> 00:47:57,030 Joten säilytä häntää. 882 00:47:57,030 --> 00:48:05,600 >> Toinen tapa kirjoittaa häntä olisi vain meidän array indeksi koko, eikö? 883 00:48:05,600 --> 00:48:07,560 Tämä on koko 5. 884 00:48:07,560 --> 00:48:11,490 Seuraava asia on menossa mennä 5. 885 00:48:11,490 --> 00:48:12,296 Cool? 886 00:48:12,296 --> 00:48:13,290 OK. 887 00:48:13,290 --> 00:48:16,350 Se saa hieman monimutkaisempi kun alamme Messing kanssa pää. 888 00:48:16,350 --> 00:48:17,060 Kyllä? 889 00:48:17,060 --> 00:48:20,090 >> Yleisö: Tarkoittaako tämä sitä, että me olisi todennut array, joka 890 00:48:20,090 --> 00:48:23,880 oli viisi elementtiä pitkä ja Sitten me lisäämme sen päälle? 891 00:48:23,880 --> 00:48:24,730 >> SPEAKER 1: Ei. 892 00:48:24,730 --> 00:48:27,560 Joten tässä tapauksessa, tämä on pino. 893 00:48:27,560 --> 00:48:31,760 Tämä olisi julistettava koska taulukon koko 6. 894 00:48:31,760 --> 00:48:37,120 Ja tässä tapauksessa, me on vain yksi välilyönti vasemmalle. 895 00:48:37,120 --> 00:48:42,720 >> OK, niin yksi asia on tässä tapauksessa, jos meidän pää on 0, 896 00:48:42,720 --> 00:48:45,270 Sitten me vain voi lisätä sitä kokoa. 897 00:48:45,270 --> 00:48:51,020 Mutta se saa hieman hankalampaa koska itse asiassa, ne 898 00:48:51,020 --> 00:48:52,840 ei ole dia tähän, joten aion 899 00:48:52,840 --> 00:48:56,670 vetää yhteen, koska se ei ole aivan näin yksinkertainen, kun olet 900 00:48:56,670 --> 00:48:59,230 alkaa päästä eroon asioita. 901 00:48:59,230 --> 00:49:03,920 Joten taas pinon olet aina vain 902 00:49:03,920 --> 00:49:08,920 murehtia, mitä kokoa on kun lisäät jotain, 903 00:49:08,920 --> 00:49:15,710 jossa jono sinun täytyy myös tehdä Varmista, että pää on osuus, 904 00:49:15,710 --> 00:49:20,760 koska cool juttu jonoja on, että jos et ole kapasiteettia, 905 00:49:20,760 --> 00:49:23,040 voit itse tehdä sen kietoa. 906 00:49:23,040 --> 00:49:28,810 >> OK, joten yksi thing-- oh, tämä on kauheaa liitu. 907 00:49:28,810 --> 00:49:31,815 Yksi asia harkita tapaus. 908 00:49:31,815 --> 00:49:35,514 909 00:49:35,514 --> 00:49:37,140 Me vain tehdä viisi. 910 00:49:37,140 --> 00:49:41,810 OK, joten me aiomme sanoa pää on täällä. 911 00:49:41,810 --> 00:49:46,140 Tämä on 0, 1, 2, 3, 4. 912 00:49:46,140 --> 00:49:54,210 >> Pää on siellä, ja ole hyvä, mitä niissä on. 913 00:49:54,210 --> 00:49:58,340 Ja haluamme lisätä jotain, eikö? 914 00:49:58,340 --> 00:50:01,170 Niin asia, että meidän täytyy tietää, että pää on aina 915 00:50:01,170 --> 00:50:05,620 Siirrymme tällä tavalla ja sitten silmukka takaisin noin, OK? 916 00:50:05,620 --> 00:50:10,190 >> Joten tässä jonossa on tilaa, eikö? 917 00:50:10,190 --> 00:50:13,950 Se on tila alusta, eräänlainen vastakohta. 918 00:50:13,950 --> 00:50:17,920 Joten mitä meidän täytyy tehdä, on meillä täytyy laskea häntää. 919 00:50:17,920 --> 00:50:20,530 Jos tiedät, että pää ei ole liikkunut, häntää 920 00:50:20,530 --> 00:50:24,630 on vain sinun array indeksi koon. 921 00:50:24,630 --> 00:50:30,000 >> Mutta todellisuudessa, jos käytät jono, pää on todennäköisesti päivitetään. 922 00:50:30,000 --> 00:50:33,890 Joten mitä sinun tarvitsee tehdä, on oikeastaan ​​laskea häntä. 923 00:50:33,890 --> 00:50:39,990 Joten mitä teemme, on tämä kaava täällä, jotka aion antaa teille 924 00:50:39,990 --> 00:50:42,680 kaverit ajattelevat, ja niin me puhumme siitä. 925 00:50:42,680 --> 00:50:49,567 926 00:50:49,567 --> 00:50:50,400 Joten tämä on kapasiteettia. 927 00:50:50,400 --> 00:50:55,890 928 00:50:55,890 --> 00:50:59,660 >> Joten tämä todella antaa sinulle tapa tehdä se. 929 00:50:59,660 --> 00:51:03,205 930 00:51:03,205 --> 00:51:04,330 Koska tässä tapauksessa, mitä? 931 00:51:04,330 --> 00:51:09,205 Meidän pää on 1, meidän koko on 4. 932 00:51:09,205 --> 00:51:11,760 933 00:51:11,760 --> 00:51:18,490 Jos me mod että 5, saamme 0, mikä on kun meidän pitäisi syöttää sitä. 934 00:51:18,490 --> 00:51:23,320 935 00:51:23,320 --> 00:51:26,080 >> Niin sitten seuraavassa tapauksessa jos tekisimme tämän, 936 00:51:26,080 --> 00:51:33,390 sanomme, OK, katsotaanpa dequeue jotain. 937 00:51:33,390 --> 00:51:34,390 Me dequeue tätä. 938 00:51:34,390 --> 00:51:37,740 Otamme tämä elementti, eikö? 939 00:51:37,740 --> 00:51:47,930 >> Ja nyt meidän pää osoittaa täällä, ja haluamme lisätä toinen juttu. 940 00:51:47,930 --> 00:51:52,470 Tämä on pohjimmiltaan takaisin meidän linja, eikö? 941 00:51:52,470 --> 00:51:55,450 Jonot voi kietoa array. 942 00:51:55,450 --> 00:51:57,310 Se on yksi tärkeimmistä eroista. 943 00:51:57,310 --> 00:51:58,780 Pinot, et voi tehdä tätä. 944 00:51:58,780 --> 00:52:01,140 >> Kanssa jonot, voit koska kaikki asiat 945 00:52:01,140 --> 00:52:03,940 on, että tiedät mitä oli viimeksi lisätty. 946 00:52:03,940 --> 00:52:10,650 Koska kaikki on menossa lisätä Tämän vasemmalle suuntaan, tässä tapauksessa, 947 00:52:10,650 --> 00:52:16,480 ja sitten kietoa, voit jatketaan ottamalla uusia elementtejä 948 00:52:16,480 --> 00:52:18,830 edessä array koska se ei ole oikeastaan 949 00:52:18,830 --> 00:52:20,640 edessä array enää. 950 00:52:20,640 --> 00:52:26,320 Voit ajatella alusta array missä päätäsi todella on. 951 00:52:26,320 --> 00:52:29,710 >> Joten tämä kaava on, miten voit laskea häntä. 952 00:52:29,710 --> 00:52:32,780 953 00:52:32,780 --> 00:52:35,610 Onko se järkevää? 954 00:52:35,610 --> 00:52:36,110 OK. 955 00:52:36,110 --> 00:52:39,400 956 00:52:39,400 --> 00:52:44,040 OK, dequeue, ja sitten teillä 10 minuuttia 957 00:52:44,040 --> 00:52:48,840 kysyä minulta mitään tarkentavia kysymyksiä haluat, koska tiedän, että se on hullua. 958 00:52:48,840 --> 00:52:51,980 >> Okei, joten samassa way-- En tiedä, jos te huomanneet, 959 00:52:51,980 --> 00:52:53,450 mutta CS on kyse kuvioita. 960 00:52:53,450 --> 00:52:57,370 Asiat ovat melko sama, vain pieniä parannuksia. 961 00:52:57,370 --> 00:52:58,950 Niin sama juttu täällä. 962 00:52:58,950 --> 00:53:04,040 Meidän täytyy tarkistaa, jos me itse on jotain meidän jonossa, eikö? 963 00:53:04,040 --> 00:53:05,960 Sanovat, OK, on ​​meidän koko suurempi kuin 0? 964 00:53:05,960 --> 00:53:06,730 Cool. 965 00:53:06,730 --> 00:53:10,690 >> Jos teemme, sitten siirrymme meidän pään, joka minä juuri osoittanut täällä. 966 00:53:10,690 --> 00:53:13,870 Päivitämme pää olla yksi enemmän. 967 00:53:13,870 --> 00:53:18,390 Ja sitten me dekrementoidaan meidän kokoa ja palauttaa elementin. 968 00:53:18,390 --> 00:53:21,000 969 00:53:21,000 --> 00:53:26,250 >> Siellä on paljon enemmän konkreettisia koodi study.cs50.net, 970 00:53:26,250 --> 00:53:29,440 ja olen erittäin suositella menossa sen kautta, jos sinulla on aikaa, 971 00:53:29,440 --> 00:53:30,980 vaikka se on vain pseudo-koodin. 972 00:53:30,980 --> 00:53:35,980 Ja jos kaverit haluavat puhua kautta että minun kanssani one, kerro minulle 973 00:53:35,980 --> 00:53:37,500 tietää. 974 00:53:37,500 --> 00:53:38,770 Olen mielelläni. 975 00:53:38,770 --> 00:53:42,720 Tietorakenteita, jos otat CS 124, luultavasti 976 00:53:42,720 --> 00:53:47,830 tietää, että tietorakenteita saada hyvin hauskaa ja tämä on vasta alkamassa. 977 00:53:47,830 --> 00:53:50,350 >> Tiedän siis, se on vaikeaa. 978 00:53:50,350 --> 00:53:51,300 Se on OK. 979 00:53:51,300 --> 00:53:52,410 Kamppailemme. 980 00:53:52,410 --> 00:53:53,630 En vieläkään. 981 00:53:53,630 --> 00:53:56,660 Joten älä murehdi liikaa sitä. 982 00:53:56,660 --> 00:54:02,390 >> Mutta se on pohjimmiltaan sinun pikakurssin tietorakenteita. 983 00:54:02,390 --> 00:54:03,400 Tiedän, että se on paljon. 984 00:54:03,400 --> 00:54:06,860 Onko mitään, me haluaisin mennä uudestaan? 985 00:54:06,860 --> 00:54:09,400 Mitä me haluamme puhua kautta? 986 00:54:09,400 --> 00:54:10,060 Kyllä? 987 00:54:10,060 --> 00:54:16,525 >> Yleisö: Tästä esimerkiksi niin Uuden häntä on 0 kyseisenä? 988 00:54:16,525 --> 00:54:17,150 SPEAKER 1: Kyllä. 989 00:54:17,150 --> 00:54:18,230 Yleisö: OK. 990 00:54:18,230 --> 00:54:24,220 Niin sitten menee läpi, sinun on 1 plus 4 or-- 991 00:54:24,220 --> 00:54:27,671 >> SPEAKER 1: Niin sanoitte, kun haluamme mennä tekemään tätä uudelleen? 992 00:54:27,671 --> 00:54:28,296 Yleisö: Joo. 993 00:54:28,296 --> 00:54:38,290 Joten jos olit miettiminen out-- missä voit laskettaessa hännän että? 994 00:54:38,290 --> 00:54:44,260 >> SPEAKER 1: Niin hännän oli in-- muutin tähän. 995 00:54:44,260 --> 00:54:52,010 Joten tässä esimerkissä täällä, tämä oli array me tarkastelemme, OK? 996 00:54:52,010 --> 00:54:54,670 Joten meillä on asiat 1, 2, 3, ja 4. 997 00:54:54,670 --> 00:55:05,850 Joten meillä on pää on 1 klo Tässä vaiheessa, ja meidän koko vastaa 4 998 00:55:05,850 --> 00:55:07,050 tässä vaiheessa, eikö? 999 00:55:07,050 --> 00:55:08,960 >> Te kaikki samaa mieltä siitä, että näin on? 1000 00:55:08,960 --> 00:55:14,620 Joten emme päätä plus koko, joka antaa meille 5, ja sitten me mod 5. 1001 00:55:14,620 --> 00:55:20,690 Saamme 0, joka kertoo meille, että 0 on missä on häntä, jossa meillä on tilaa. 1002 00:55:20,690 --> 00:55:22,010 >> Yleisö: Mikä korkki? 1003 00:55:22,010 --> 00:55:23,520 >> SPEAKER 1: kapasiteettia. 1004 00:55:23,520 --> 00:55:24,020 Anteeksi. 1005 00:55:24,020 --> 00:55:29,640 Tämä on siis kokoa array. 1006 00:55:29,640 --> 00:55:35,210 1007 00:55:35,210 --> 00:55:36,047 Kyllä? 1008 00:55:36,047 --> 00:55:39,210 >> Yleisö: [kuulumaton] ennen palaamme elementti? 1009 00:55:39,210 --> 00:55:46,270 >> SPEAKER 1: Eli siirrymme pää tai palauttaa hetki? 1010 00:55:46,270 --> 00:55:52,680 Joten jos siirrymme yhden, dekrementoidaan koko? 1011 00:55:52,680 --> 00:55:54,150 Pidä kiinni. 1012 00:55:54,150 --> 00:55:55,770 Olen ehdottomasti unohdin toiseen. 1013 00:55:55,770 --> 00:56:00,646 1014 00:56:00,646 --> 00:56:01,990 Ei se haittaa. 1015 00:56:01,990 --> 00:56:04,980 Ei ole toista kaavaa. 1016 00:56:04,980 --> 00:56:09,980 Joo, mitä haluaisi palata pää ja sen jälkeen takaisin. 1017 00:56:09,980 --> 00:56:13,270 >> Yleisö: OK, koska tässä kohta, pää oli 0, 1018 00:56:13,270 --> 00:56:18,452 ja sitten haluat palata indeksi 0 ja sitten tehdä pään 1? 1019 00:56:18,452 --> 00:56:19,870 >> SPEAKER 1: Oikea. 1020 00:56:19,870 --> 00:56:22,820 Mielestäni on olemassa toinen kaava ikään kuin tämä. 1021 00:56:22,820 --> 00:56:26,970 Minulla ei ole sen päällä päähäni En halua antaa sinulle väärä. 1022 00:56:26,970 --> 00:56:35,470 Mutta mielestäni se on täysin voimassa sanoa, OK, säilytä tämä element-- riippumatta 1023 00:56:35,470 --> 00:56:40,759 pää n elementti is-- dekrementoidaan sinun koon, siirrä pään yli, ja paluu 1024 00:56:40,759 --> 00:56:41,800 mitä se elementti on. 1025 00:56:41,800 --> 00:56:44,760 Se on täysin pätevä. 1026 00:56:44,760 --> 00:56:45,260 OK. 1027 00:56:45,260 --> 00:56:48,360 1028 00:56:48,360 --> 00:56:53,560 Minusta tuntuu, tämä ei ole kuten most-- et ole 1029 00:56:53,560 --> 00:56:55,740 kävelen pois täältä kuten, kyllä, tiedän yrittää. 1030 00:56:55,740 --> 00:56:56,880 Sain sen kaiken. 1031 00:56:56,880 --> 00:56:57,670 Ei se mitään. 1032 00:56:57,670 --> 00:57:00,200 Lupaan. 1033 00:57:00,200 --> 00:57:05,240 Mutta tietorakenteita ovat jotain, se vie paljon aikaa tottua. 1034 00:57:05,240 --> 00:57:10,010 Luultavasti yksi vaikeimmista asioita, luulen, että kurssin. 1035 00:57:10,010 --> 00:57:15,330 >> Joten se varmasti vie toistoa ja etsivät at-- I 1036 00:57:15,330 --> 00:57:20,050 ei oikein tiedä linkitettyjen listojen kunnes tein liian paljon heidän kanssaan, 1037 00:57:20,050 --> 00:57:22,550 samalla tavalla, etten todella ymmärtää osoittimet 1038 00:57:22,550 --> 00:57:27,040 kunnes olen joutunut opettamaan sitä kaksi vuotta ja tehdä omaa psets kanssa. 1039 00:57:27,040 --> 00:57:28,990 Se vie paljon toistoa ja aikaa. 1040 00:57:28,990 --> 00:57:32,600 Ja lopulta se tavallaan klikkaa. 1041 00:57:32,600 --> 00:57:36,320 >> Mutta sillä välin, jos sinulla on sellainen korkean tason ymmärrystä siitä, mitä 1042 00:57:36,320 --> 00:57:39,321 nämä tekevät, niiden etuja ja cons-- joka on mitä 1043 00:57:39,321 --> 00:57:41,820 me todella yleensä korostavat, varsinkin intro kurssin. 1044 00:57:41,820 --> 00:57:45,511 Kuten, miksi käytämme kokeile yli array? 1045 00:57:45,511 --> 00:57:48,010 Kuten, mitkä ovat positiivisia ja negatiivit, kumpaa näistä? 1046 00:57:48,010 --> 00:57:51,610 >> Ja ymmärtää kompromisseja kunkin näistä rakenteista 1047 00:57:51,610 --> 00:57:54,910 on mitä on paljon tärkeämpää juuri nyt. 1048 00:57:54,910 --> 00:57:58,140 Siellä voi olla yksi hullu kysymys tai kaksi, joka on 1049 00:57:58,140 --> 00:58:03,710 pyydämme teitä toteuttaa push tai toteuttaa pop tai enqueue ja dequeue. 1050 00:58:03,710 --> 00:58:07,340 Mutta suurin osa, jolla se korkeampaa ymmärrystä ja enemmän 1051 00:58:07,340 --> 00:58:09,710 on intuitiivinen käsitys on tärkeämpää kuin itse 1052 00:58:09,710 --> 00:58:11,250 pysty toteuttamaan sitä. 1053 00:58:11,250 --> 00:58:14,880 >> Se olisi todella mahtavaa, jos te kaikki voisi mennä ulos ja mennä toteuttamaan kokeilla, 1054 00:58:14,880 --> 00:58:19,720 mutta ymmärrämme se ei välttämättä järkevin asia juuri nyt. 1055 00:58:19,720 --> 00:58:23,370 Mutta voit omassa PSET, jos haluat sen, ja sitten saat käytännössä 1056 00:58:23,370 --> 00:58:27,200 ja sitten ehkä sinun todella ymmärtää se. 1057 00:58:27,200 --> 00:58:27,940 Kyllä? 1058 00:58:27,940 --> 00:58:30,440 >> Yleisö: OK, niin mitkä ovat Meidän tarkoitus käyttää PSET? 1059 00:58:30,440 --> 00:58:31,916 Tarvitseeko minun käyttää yksi heistä? 1060 00:58:31,916 --> 00:58:32,540 SPEAKER 1: Kyllä. 1061 00:58:32,540 --> 00:58:34,199 Joten sinulla on valintasi. 1062 00:58:34,199 --> 00:58:36,740 Oletan tässä tapauksessa voimme puhua PSET hieman 1063 00:58:36,740 --> 00:58:40,480 koska juoksin läpi näitä. 1064 00:58:40,480 --> 00:58:47,779 Joten teidän PSET, sinulla on valinta yrittää tai hash taulukoita. 1065 00:58:47,779 --> 00:58:49,570 Jotkut ihmiset yrittävät ja käyttää kukinta suodattimet, 1066 00:58:49,570 --> 00:58:51,840 mutta ne eivät varsinaisesti ole oikeita. 1067 00:58:51,840 --> 00:58:55,804 Koska niiden todennäköisyyspohjainen luonteen, ne antavat vääriä positiivisia joskus. 1068 00:58:55,804 --> 00:58:57,095 He viileä tutkia, vaikka. 1069 00:58:57,095 --> 00:58:59,030 Suosittelen näköinen niitä ainakin. 1070 00:58:59,030 --> 00:59:03,260 Mutta sinulla on valinnanvaraa välinen tiiviste ja kokeilla. 1071 00:59:03,260 --> 00:59:06,660 Ja se tulee olemaan, jos lataat oman sanakirjan. 1072 00:59:06,660 --> 00:59:09,230 >> Ja sinun täytyy valita teidän hajautusfunktio, 1073 00:59:09,230 --> 00:59:13,420 sinun täytyy valita, kuinka monta kauhat sinulla on, ja se vaihtelee. 1074 00:59:13,420 --> 00:59:17,440 Kuten jos sinulla on enemmän kauhat, Ehkä se ajaa nopeammin. 1075 00:59:17,440 --> 00:59:22,790 Mutta ehkä sinä tuhlaat paljon tilaa, että tapa, vaikka. 1076 00:59:22,790 --> 00:59:26,320 Sinun täytyy tajuta se. 1077 00:59:26,320 --> 00:59:27,140 Mmhmm? 1078 00:59:27,140 --> 00:59:29,875 >> Yleisö: Sanoit aiemmin, että voimme käyttää muita hash toimintoja, 1079 00:59:29,875 --> 00:59:31,750 että emme tarvitse luoda hajautusfunktio? 1080 00:59:31,750 --> 00:59:32,666 >> SPEAKER 1: Kyllä, aivan. 1081 00:59:32,666 --> 00:59:38,150 Joten kirjaimellisesti oman hajautusfunktio, Google "hajautusfunktio" 1082 00:59:38,150 --> 00:59:40,770 ja etsiä hienoja niistä. 1083 00:59:40,770 --> 00:59:43,250 Et ole odotettavissa rakentaa oma hash toimintoja. 1084 00:59:43,250 --> 00:59:46,100 Ihmiset viettävät teesiä näitä asioita. 1085 00:59:46,100 --> 00:59:50,250 >> Joten älä ole huolissasi rakentaa oma. 1086 00:59:50,250 --> 00:59:53,350 Etsi yksi verkossa aloittaa. 1087 00:59:53,350 --> 00:59:56,120 Jotkut heistä joudut manipuloida hieman 1088 00:59:56,120 --> 00:59:59,430 varmistaa paluun tyypit täsmää ja vaikka mitä, niin alussa, 1089 00:59:59,430 --> 01:00:02,420 Voisin suositella käyttäen jotain helppoa, että ehkä juuri 1090 01:00:02,420 --> 01:00:04,680 hajautustaulu- ensimmäistä kirjainta. 1091 01:00:04,680 --> 01:00:08,760 Ja sitten kun sinulla on, että työ-, sisällyttämällä jäähdytin hajautusfunktio. 1092 01:00:08,760 --> 01:00:09,260 Mmhmm? 1093 01:00:09,260 --> 01:00:13,020 >> Yleisö: Olisiko yrittää olla tai tehokas, mutta vain vaikeampi, like-- 1094 01:00:13,020 --> 01:00:15,880 >> SPEAKER 1: Niin kokeilla, luulen, on intuitiivisesti vaikea toteuttaa 1095 01:00:15,880 --> 01:00:18,310 mutta on erittäin nopea. 1096 01:00:18,310 --> 01:00:20,620 Kuitenkin vie enemmän tilaa. 1097 01:00:20,620 --> 01:00:25,270 Jälleen, voit optimoida nämä molemmat vuonna eri tavoin ja on olemassa keinoja to-- 1098 01:00:25,270 --> 01:00:26,770 Yleisö: Miten me arvostellaan tätä? 1099 01:00:26,770 --> 01:00:27,540 Onko se matter-- 1100 01:00:27,540 --> 01:00:29,164 >> SPEAKER 1: Eli olet arvostellaan normaalilla tavalla. 1101 01:00:29,164 --> 01:00:31,330 Olet menossa arvostellaan suunnitteluun. 1102 01:00:31,330 --> 01:00:36,020 Miten tahansa tehdä, haluatko varmista, että se on yhtä tyylikäs kuin se voi olla 1103 01:00:36,020 --> 01:00:38,610 ja niin tehokas kuin se voi olla. 1104 01:00:38,610 --> 01:00:41,950 Mutta jos haluat kokeilla tai hash taulukko, niin kauan kuin se toimii, 1105 01:00:41,950 --> 01:00:45,350 olemme tyytyväisiä, että. 1106 01:00:45,350 --> 01:00:48,370 Ja jos käytät jotain että hash ensimmäistä kirjainta, se on hieno, 1107 01:00:48,370 --> 01:00:51,410 kuten ehkä kuten suunnittelu-viisas. 1108 01:00:51,410 --> 01:00:53,410 Olemme myös päästä kohta tässä semester-- 1109 01:00:53,410 --> 01:00:55,340 En tiedä, jos kaverit noticed-- jos olet 1110 01:00:55,340 --> 01:00:58,780 PSET laadut laskevan hieman koska suunnittelu ja vaikka mitä, 1111 01:00:58,780 --> 01:00:59,900 se on täysin hieno. 1112 01:00:59,900 --> 01:01:02,960 Se on tulossa pisteeseen, jossa sinun ohjelmat monimutkaistuvat. 1113 01:01:02,960 --> 01:01:04,830 On enemmän paikkoja voit parantaa. 1114 01:01:04,830 --> 01:01:06,370 >> Joten se on täysin normaalia. 1115 01:01:06,370 --> 01:01:08,810 Se ei ole, että olet huonommin teidän PSET. 1116 01:01:08,810 --> 01:01:11,885 Se on vain Meitä kovemmin sinua nyt. 1117 01:01:11,885 --> 01:01:13,732 Joten jokainen tunne sitä. 1118 01:01:13,732 --> 01:01:14,940 Minä vain arvostellaan kaikki psets. 1119 01:01:14,940 --> 01:01:16,490 Tiedän, jokainen tunne sitä. 1120 01:01:16,490 --> 01:01:19,600 >> Joten älä olla huolissaan siitä. 1121 01:01:19,600 --> 01:01:23,580 Ja jos sinulla on kysyttävää ennen psets tai miten voit parantaa, 1122 01:01:23,580 --> 01:01:27,760 Yritän ja kommentoida erityisiä paikkoja, mutta joskus se on myöhäistä 1123 01:01:27,760 --> 01:01:30,840 ja saan väsynyt. 1124 01:01:30,840 --> 01:01:34,885 Onko muita asioita noin tietorakenteita? 1125 01:01:34,885 --> 01:01:37,510 Olen varma, että kaverit eivät todellakaan halua puhua niitä enää, 1126 01:01:37,510 --> 01:01:42,650 mutta jos on, olen onnellinen mennä niiden yli, samoin kuin mitään 1127 01:01:42,650 --> 01:01:45,580 luento viime viikko tai viime viikolla. 1128 01:01:45,580 --> 01:01:51,580 >> Tiedän, viime viikolla oli kaikki tarkastelu, joten olemme ehkä ohitetaan joitakin arvostelu 1129 01:01:51,580 --> 01:01:54,190 alkaen luento. 1130 01:01:54,190 --> 01:01:58,230 Muita kysymyksiä voin vastata? 1131 01:01:58,230 --> 01:01:59,350 OK, kaikki hyvin. 1132 01:01:59,350 --> 01:02:02,400 No, te ulos 15 minuuttia etuajassa. 1133 01:02:02,400 --> 01:02:08,370 >> Toivon, että tämä oli semi-hyödyllinen ainakin, ja minä näen teidät ensi viikolla, 1134 01:02:08,370 --> 01:02:12,150 ja torstain virka. 1135 01:02:12,150 --> 01:02:15,285 Onko pyytää välipalat ensi viikolla, se juttu? 1136 01:02:15,285 --> 01:02:17,459 Koska unohdin karkkia tänään. 1137 01:02:17,459 --> 01:02:19,750 Ja minä toin karkkia viimeksi viikko, mutta se oli Columbus Day, 1138 01:02:19,750 --> 01:02:25,400 joten ei ollut kuin kuusi henkilöä, jotka oli neljä pussia karkkia itselleen. 1139 01:02:25,400 --> 01:02:28,820 Voin tuoda starbursts uudelleen, jos haluat. 1140 01:02:28,820 --> 01:02:29,580 Starbursts? 1141 01:02:29,580 --> 01:02:32,250 OK, kuulostaa hyvältä. 1142 01:02:32,250 --> 01:02:35,050 On suuri päivä, kaverit. 1143 01:02:35,050 --> 01:02:39,510