1 00:00:00,000 --> 00:00:02,832 >> [Zenelejátszási] 2 00:00:02,832 --> 00:00:05,670 3 00:00:05,670 --> 00:00:08,560 >> DOUG LLOYD: OK, így a Ezen a ponton során, 4 00:00:08,560 --> 00:00:15,300 már lefedett sok az alapokat a C. Tudjuk, hogy sokat változók, tömbök, 5 00:00:15,300 --> 00:00:17,610 mutatók, minden, ami jó dolog. 6 00:00:17,610 --> 00:00:21,610 Ezek mind egyfajta beépített hogy lássa, mint a fundamentumok, 7 00:00:21,610 --> 00:00:23,880 de ennél többre vagyunk képesek, igaz? 8 00:00:23,880 --> 00:00:27,930 Tudjuk kombinálni a dolgokat valamint érdekes módon. 9 00:00:27,930 --> 00:00:31,010 >> És így csináljuk meg, kezdjük ágaznak, amit C ad nekünk, 10 00:00:31,010 --> 00:00:35,270 és meg kell kezdeni, hogy hozzon létre saját adatok szerkezetek segítségével ezeket épület 11 00:00:35,270 --> 00:00:40,590 blokkok együtt csinálni valamit igazán értékes, hasznos. 12 00:00:40,590 --> 00:00:43,420 Ennek egyik módja, amit tehetünk ez beszélni gyűjtemények. 13 00:00:43,420 --> 00:00:48,360 Szóval eddig is megvolt egyfajta adatok struktúra képviselő gyűjtemények 14 00:00:48,360 --> 00:00:51,030 A tetszik értékek, hasonló értékeket. 15 00:00:51,030 --> 00:00:52,350 Ez lenne egy tömbben. 16 00:00:52,350 --> 00:00:57,020 Van gyűjtemények egészek, vagy gyűjtemények karakterek és így tovább. 17 00:00:57,020 --> 00:01:00,890 >> Struktúrák is egyfajta adatok szerkezete az információgyűjtés, 18 00:01:00,890 --> 00:01:03,220 de ez nem gyűjtésére, mint értékek. 19 00:01:03,220 --> 00:01:08,090 Ez általában keverékek különböző adattípusok együtt belsejében egy dobozban. 20 00:01:08,090 --> 00:01:10,750 De ez önmagában nem használt lánc együtt 21 00:01:10,750 --> 00:01:16,920 vagy csatlakoztassa a hasonló tételek, mint egy tömb. 22 00:01:16,920 --> 00:01:20,960 A tömbök nagy elem felnéz, de visszahívás 23 00:01:20,960 --> 00:01:24,262 hogy ez nagyon nehéz szúrni egy tömb, 24 00:01:24,262 --> 00:01:26,470 hacsak mi behelyezése a A legvégén a tömbben. 25 00:01:26,470 --> 00:01:29,730 >> És a legjobb példa van mert ez a fajta behelyezése. 26 00:01:29,730 --> 00:01:31,650 Ha felidézzük videónkat elhelyezésének sort, 27 00:01:31,650 --> 00:01:34,110 volt egy csomó költségén részt, amelynek 28 00:01:34,110 --> 00:01:37,970 felvenni elemeket, és a több műszakos őket az útból, hogy illeszkedjen valamit 29 00:01:37,970 --> 00:01:41,290 a közepén a tömb. 30 00:01:41,290 --> 00:01:44,690 Tömbök is szenvednek a másik probléma, ami rugalmatlansága. 31 00:01:44,690 --> 00:01:47,150 Amikor egy tömböt, kapunk egy lövés is. 32 00:01:47,150 --> 00:01:49,790 Kapunk mondani, azt akarom, ez a sok eleme van. 33 00:01:49,790 --> 00:01:51,940 Lehet, hogy a 100, talán legyen 1000, talán 34 00:01:51,940 --> 00:01:55,930 legyen x ahol x jelentése egy szám, hogy a felhasználói adott nekünk egy azonnali, vagy a parancs 35 00:01:55,930 --> 00:01:56,630 vonal. 36 00:01:56,630 --> 00:01:59,905 >> De mi csak kap egy lövés, mi nem értem, hogy majd azt mondják, jaj, valójában én 37 00:01:59,905 --> 00:02:04,360 szükséges 101, vagy szükségem x plusz 20. 38 00:02:04,360 --> 00:02:07,910 Túl késő, mi már kijelentette, a tömb, és ha azt akarjuk, hogy 101 vagy x 39 00:02:07,910 --> 00:02:12,050 plusz 20, van, hogy állapítsa egy teljesen más tömb, 40 00:02:12,050 --> 00:02:15,540 másolja az összes elemet a tömb vége, és akkor mi van elég. 41 00:02:15,540 --> 00:02:19,880 És mi van, ha tévedünk újra, mi ha valóban szükség van 102, vagy x plusz 40, 42 00:02:19,880 --> 00:02:21,970 van, hogy ezt újra. 43 00:02:21,970 --> 00:02:26,250 Tehát ők nagyon rugalmatlan átméretezni adataink, 44 00:02:26,250 --> 00:02:29,360 de ha kombináljuk össze néhány Az alapokat, hogy mi már 45 00:02:29,360 --> 00:02:33,230 értesült mutatók és struktúrák, különösen a dinamikus memória 46 00:02:33,230 --> 00:02:36,180 elosztása a malloc, mi lehet, hogy ezeket a darabokat össze 47 00:02:36,180 --> 00:02:40,960 hogy hozzon létre egy új adatok structure-- egy egyszeresen láncolt lista talán say-- 48 00:02:40,960 --> 00:02:45,400 amely lehetővé teszi számunkra, hogy nő, és zsugorodik a gyűjtemény értékek 49 00:02:45,400 --> 00:02:48,800 és mi nem lesz elvesztegetett hely. 50 00:02:48,800 --> 00:02:53,320 >> Tehát újra, hívja ezt a gondolatot, ez a fogalom, egy láncolt lista. 51 00:02:53,320 --> 00:02:56,320 Különösen ez a videó vagyunk beszélünk egyszeresen láncolt lista, 52 00:02:56,320 --> 00:02:59,185 majd egy másik videó beszélgetünk mintegy kétszeresen láncolt listák, amelyek 53 00:02:59,185 --> 00:03:01,560 csak változata a téma itt. 54 00:03:01,560 --> 00:03:05,200 De egyszeresen láncolt lista áll csomópontok, 55 00:03:05,200 --> 00:03:08,559 csomópontok csak, hogy egy absztrakt term-- ez csak valami hívom 56 00:03:08,559 --> 00:03:10,350 ez egyfajta szerkezete alapvetően én vagyok? 57 00:03:10,350 --> 00:03:16,190 Csak megy, hogy ez egy node-- és ez csomópont két tag, vagy a két területen. 58 00:03:16,190 --> 00:03:20,300 Azt adatokat, általában egy egész, egy karakter úszó, 59 00:03:20,300 --> 00:03:23,790 vagy lehet más adattípus hogy már definiált típusú def. 60 00:03:23,790 --> 00:03:29,290 És tartalmaz egy mutatót egy másik csomópontot az azonos típusú. 61 00:03:29,290 --> 00:03:34,710 >> Tehát van két dolog belsejét ez a csomópont, adatok és mutatóját 62 00:03:34,710 --> 00:03:36,380 egy másik csomópont. 63 00:03:36,380 --> 00:03:39,370 És ha elkezd láthatóvá ezt, akkor gondolj rá 64 00:03:39,370 --> 00:03:42,280 mint egy lánc csomópontok vannak egymáshoz csatlakoztatva. 65 00:03:42,280 --> 00:03:45,070 Megvan az első csomópontot, akkor adatokat tartalmaz, és egy mutatót 66 00:03:45,070 --> 00:03:49,110 a második csomóponthoz, amely tartalmaz adatokat, és egy mutatót a harmadik csomópont. 67 00:03:49,110 --> 00:03:52,940 És hogy ezért nevezzük ezt a láncolt lista, ők kapcsolódnak egymáshoz. 68 00:03:52,940 --> 00:03:56,070 >> Mit jelent ez a különleges node szerkezet néz ki? 69 00:03:56,070 --> 00:04:01,120 Nos, ha visszahívja a videót meghatározó egyéni típusú, típusú def, 70 00:04:01,120 --> 00:04:05,400 tudjuk meg egy structure-- és írja meg egy szerkezetet, mint ez. 71 00:04:05,400 --> 00:04:11,240 tyepdef struct sllist, és akkor én vagyok szó használatával érték itt önkényesen 72 00:04:11,240 --> 00:04:13,891 jelzi, bármilyen típusú adatot igazán. 73 00:04:13,891 --> 00:04:16,890 Lehet hárítani integer vagy float, akkor lehetett volna, amit akarsz. 74 00:04:16,890 --> 00:04:19,389 Ez nem korlátozódik csupán egészek, vagy ilyesmi. 75 00:04:19,389 --> 00:04:22,790 Tehát az érték mindössze egy tetszőleges adatok típusát, majd egy mutatót 76 00:04:22,790 --> 00:04:26,310 egy másik csomópont azonos típusú. 77 00:04:26,310 --> 00:04:29,690 >> Nos, van egy kis fogás Itt a meghatározó struktúra 78 00:04:29,690 --> 00:04:33,030 ha ez egy önálló referenciális szerkezetet. 79 00:04:33,030 --> 00:04:35,340 Van, hogy egy ideiglenes Íme az én szerkezetet. 80 00:04:35,340 --> 00:04:37,640 A nap végén I egyértelműen akar nevezni 81 00:04:37,640 --> 00:04:43,030 sll csomópont, ami végső soron az új Íme egy részét az esetem meghatározása, 82 00:04:43,030 --> 00:04:47,450 de nem tudom használni sll csomópont a közepén ezt. 83 00:04:47,450 --> 00:04:51,430 Az ok pedig, én nem létrehozott egy típusú úgynevezett sll csomópont 84 00:04:51,430 --> 00:04:55,200 amíg nem hit ez az utolsó pont itt. 85 00:04:55,200 --> 00:04:59,720 Addig a pontig, azt kell, hogy legyen Egy másik módja annak, hogy olvassa el ezt a típusú adatokat. 86 00:04:59,720 --> 00:05:02,440 >> És ez egy önálló referenciális típusú adatokat. 87 00:05:02,440 --> 00:05:06,314 Ez, s egy adat típusát szerkezet, amely tartalmaz egy adat, 88 00:05:06,314 --> 00:05:08,480 és egy mutató egy másik szerkezete az azonos típusú. 89 00:05:08,480 --> 00:05:11,750 Szóval kell, hogy képes hivatkozni Ezen adatok típusa legalábbis átmenetileg, 90 00:05:11,750 --> 00:05:14,910 így adva, hogy egy átmeneti neve struct sllist 91 00:05:14,910 --> 00:05:18,540 lehetővé teszi számomra, hogy majd azt mondják, szeretnék egy mutatót egy másik struct sllist, 92 00:05:18,540 --> 00:05:24,690 Egy struct sllist csillag, majd miután már befejezte a meghatározása, 93 00:05:24,690 --> 00:05:27,220 Én most hívják ezt a fajta egy sll csomópontot. 94 00:05:27,220 --> 00:05:30,520 >> Szóval ezért látod van egy ideiglenes nevet itt, 95 00:05:30,520 --> 00:05:31,879 hanem állandó nevét. 96 00:05:31,879 --> 00:05:33,920 Néha lehet látni meghatározásai szerkezet, 97 00:05:33,920 --> 00:05:36,570 például, hogy a nem önálló referenciális, hogy 98 00:05:36,570 --> 00:05:39,390 nincs specifikátor nevét. 99 00:05:39,390 --> 00:05:43,040 Ez csak azt mondom typedef struct, nyissa kapcsos zárójel, majd határozza meg. 100 00:05:43,040 --> 00:05:45,620 De ha struct magától referenciális, mivel ez az egyik, 101 00:05:45,620 --> 00:05:49,010 akkor meg kell adnia a átmeneti típus neve. 102 00:05:49,010 --> 00:05:51,310 De végül is, most hogy ezt megtette, 103 00:05:51,310 --> 00:05:53,620 mi csak utalnak ezek a csomópontok, ezek az egységek, 104 00:05:53,620 --> 00:05:57,900 mint sll csomópontok célokra A többi ezt a videót. 105 00:05:57,900 --> 00:06:00,900 >> Rendben, tehát tudjuk, hogyan kell hozzon létre egy láncolt lista csomópontot. 106 00:06:00,900 --> 00:06:03,240 Tudjuk, hogyan kell meghatározni láncolt listájának csomópontot. 107 00:06:03,240 --> 00:06:06,670 Most, ha fogunk kezdeni használja őket, hogy információt gyűjtsön, 108 00:06:06,670 --> 00:06:10,360 van egy pár műtétekhez meg kell érteniük és dolgozni. 109 00:06:10,360 --> 00:06:12,860 Tudnunk kell, hogyan kell létrehozni A láncolt lista a semmiből. 110 00:06:12,860 --> 00:06:14,901 Ha nincs lista már, akarunk kezdeni egy. 111 00:06:14,901 --> 00:06:16,960 Tehát szükségünk van ahhoz, hogy hozzon létre egy láncolt lista, 112 00:06:16,960 --> 00:06:19,130 meg kell keresni valószínűleg linken keresztül lista 113 00:06:19,130 --> 00:06:21,830 találni egy elem keresünk. 114 00:06:21,830 --> 00:06:24,430 Meg kell, hogy tudja beszúrni új dolgokat a listán, 115 00:06:24,430 --> 00:06:25,930 azt akarjuk, hogy a listát, hogy képes növekedni. 116 00:06:25,930 --> 00:06:28,638 És hasonlóképpen, szeretnénk tudni törölni a dolgokat a listánkról, 117 00:06:28,638 --> 00:06:30,250 azt akarjuk, hogy a listát, hogy képes zsugorodni. 118 00:06:30,250 --> 00:06:32,160 És a végén a mi programok, különösen 119 00:06:32,160 --> 00:06:34,550 ha felidézni, hogy mi vagyunk dinamikusan memórialefoglalás 120 00:06:34,550 --> 00:06:38,337 építeni ezeket a listákat általában, szeretnénk felszabadítani az összes, hogy a memória 121 00:06:38,337 --> 00:06:39,670 ha végeztünk vele dolgozni. 122 00:06:39,670 --> 00:06:44,627 És ezért meg kell, hogy képes legyen törlése teljes kapcsolt lista egy sikertelen csapásra. 123 00:06:44,627 --> 00:06:46,460 Szóval menjünk át Néhány ilyen műveletek 124 00:06:46,460 --> 00:06:51,192 és hogyan lehet elképzelni őket, beszélgettek pszeudokódja kódot pontosan. 125 00:06:51,192 --> 00:06:53,150 Ezért szeretnénk létrehozni láncolt lista, így talán 126 00:06:53,150 --> 00:06:56,480 szeretnénk, hogy egy függvény definiálása ezzel a prototípus. 127 00:06:56,480 --> 00:07:01,690 sll csomópont csillag, hozzon létre, és én halad egy érv, néhány tetszőleges adat 128 00:07:01,690 --> 00:07:05,530 írja újra, néhány tetszőleges típusú adatokat. 129 00:07:05,530 --> 00:07:10,482 De én returning-- ezt a funkciót kell vissza hozzám egy mutatót, hogy egy egyszeresen 130 00:07:10,482 --> 00:07:11,190 láncolt lista csomópont. 131 00:07:11,190 --> 00:07:14,050 Ismét próbálunk létrehozni A láncolt lista a semmiből, 132 00:07:14,050 --> 00:07:17,900 így kell egy pointert a listán amikor végzek. 133 00:07:17,900 --> 00:07:19,420 >> Tehát mi a lépések itt? 134 00:07:19,420 --> 00:07:20,960 Nos, az első dolog, én vagyok eredménye, hogy dinamikusan 135 00:07:20,960 --> 00:07:22,550 osztja helyet egy új csomópontot. 136 00:07:22,550 --> 00:07:26,689 Ismét mi hozzuk létre a semmiből levegőt, így szükséges, hogy a malloc helyet érte. 137 00:07:26,689 --> 00:07:28,480 És persze azonnal miután malloc, 138 00:07:28,480 --> 00:07:31,692 mi mindig győződjön meg arról, hogy mi pointer-- nem kaptunk vissza null. 139 00:07:31,692 --> 00:07:33,650 Mert ha megpróbálunk hódolat null pointer, 140 00:07:33,650 --> 00:07:36,190 fogunk szenvedni segfault és nem akarjuk, hogy. 141 00:07:36,190 --> 00:07:39,510 >> Aztán azt akarjuk, hogy töltse ki a mezőt, akarjuk inicializálni az érték mezőbe 142 00:07:39,510 --> 00:07:41,690 és alapértéket a következő mezőbe. 143 00:07:41,690 --> 00:07:45,450 És akkor mi szeretnénk az alábbiakra: végül a függvény prototípus indicates-- akarunk 144 00:07:45,450 --> 00:07:49,940 vissza a mutató egy sll csomópontot. 145 00:07:49,940 --> 00:07:51,710 Szóval mit csinál ez kinézni vizuálisan? 146 00:07:51,710 --> 00:07:55,230 Nos, először is meg fogunk dinamikusan osztja helyet egy új sll csomópont, 147 00:07:55,230 --> 00:07:58,320 így malloc-- ez A vizuális ábrázolás 148 00:07:58,320 --> 00:08:00,020 A csomópont most létrehozott. 149 00:08:00,020 --> 00:08:02,757 És győződjön meg róla, ez nem null-- ebben az esetben, 150 00:08:02,757 --> 00:08:04,840 A kép nem lenne mutattak ki, ha ez nulla, 151 00:08:04,840 --> 00:08:07,298 mi lett volna elfogyott a memória, így vagyunk jó odamenni. 152 00:08:07,298 --> 00:08:10,200 Szóval most mi vagyunk a lépéssel C, formázza meg a csomópontok érték mezőbe. 153 00:08:10,200 --> 00:08:12,280 Nos, ez alapján a funkciót hívja használok itt, 154 00:08:12,280 --> 00:08:16,700 úgy néz ki, mint szeretnék átadni a 6., úgyhogy 6 Az Érték mezőben. 155 00:08:16,700 --> 00:08:18,865 Most, formázza meg a következő mezőbe. 156 00:08:18,865 --> 00:08:21,640 Nos, mit fogok ott csinálni, semmi sem jövő, igaz, 157 00:08:21,640 --> 00:08:23,600 ez az egyetlen dolog a listán. 158 00:08:23,600 --> 00:08:27,206 Szóval mi a következő dolog a listán? 159 00:08:27,206 --> 00:08:29,660 >> Nem szabad mutat sehova, ugye. 160 00:08:29,660 --> 00:08:33,600 Semmi mást nem, akkor mi az, az a koncepció, tudom, hogy ez nothing-- 161 00:08:33,600 --> 00:08:35,638 mutatókat semmi? 162 00:08:35,638 --> 00:08:37,929 Meg kell talán azt akarjuk, hogy egy null pointer van, 163 00:08:37,929 --> 00:08:40,178 és én képviseli a null mutatót csak egy piros doboz, 164 00:08:40,178 --> 00:08:41,559 nem tudunk tovább menni. 165 00:08:41,559 --> 00:08:44,430 Mint látni fogjuk egy kicsit később, mi lesz végül láncok 166 00:08:44,430 --> 00:08:46,330 A nyilak összekötő ezek a csomópontok együtt, 167 00:08:46,330 --> 00:08:48,480 de ha bejön a piros doboz, ami null, 168 00:08:48,480 --> 00:08:51,150 nem tudunk tovább menni, itt a vége a lista. 169 00:08:51,150 --> 00:08:53,960 >> És végül, mi csak szeretnénk vissza mutatót a csomóponton. 170 00:08:53,960 --> 00:08:56,160 Így hívjuk meg az új, és vissza fog térni az új 171 00:08:56,160 --> 00:08:59,370 így lehet használni bármilyen funkciót létrehozta. 172 00:08:59,370 --> 00:09:03,100 Tehát ott megy, Létrehoztunk egy egyszeresen láncolt lista csomópont a semmiből, 173 00:09:03,100 --> 00:09:05,920 és most van egy lista tudunk dolgozni. 174 00:09:05,920 --> 00:09:08,260 >> Most, mondjuk már Van egy nagy lánc, 175 00:09:08,260 --> 00:09:09,800 és meg akarjuk találni valamit. 176 00:09:09,800 --> 00:09:12,716 És azt akarjuk, hogy a funkció folyik vissza igaz vagy hamis, attól függően, 177 00:09:12,716 --> 00:09:15,840 arról, hogy létezik az érték a listán. 178 00:09:15,840 --> 00:09:18,160 A függvény prototípus, vagy nyilatkozatot adott funkció, 179 00:09:18,160 --> 00:09:23,320 nézhet this-- bool találni, és akkor szeretnénk átadni a két érvet. 180 00:09:23,320 --> 00:09:26,996 >> Az első, egy mutatót a első eleme a láncolt lista. 181 00:09:26,996 --> 00:09:29,620 Ez tulajdonképpen az, amit egy mindig szeretné nyomon követni, 182 00:09:29,620 --> 00:09:33,110 és valóban lehet valami, hogy Ön még fel a globális változót. 183 00:09:33,110 --> 00:09:35,360 Ha létrehozott egy listát, Mindig, mindig 184 00:09:35,360 --> 00:09:38,990 Nyomon szeretné követni az igen első eleme a listán. 185 00:09:38,990 --> 00:09:43,690 Így lehet hivatkozni a többi elemek csak a következő a láncot, 186 00:09:43,690 --> 00:09:47,300 anélkül, hogy tartani pointerek ép minden egyes eleme. 187 00:09:47,300 --> 00:09:50,920 Csak akkor kell nyomon követni az első egy, ha ők mind egymáshoz láncolva. 188 00:09:50,920 --> 00:09:52,460 >> És akkor a második dolog mi elhaladó újra 189 00:09:52,460 --> 00:09:54,376 önkényesen some-- bármilyen adattípust vagyunk 190 00:09:54,376 --> 00:09:59,640 keres ott van belül remélhetőleg egyik csomópont a listában. 191 00:09:59,640 --> 00:10:00,980 Tehát mi a lépések? 192 00:10:00,980 --> 00:10:04,250 Nos, az első dolog, amit tennie, hozunk létre egy keresztirányú mutatót 193 00:10:04,250 --> 00:10:06,015 rámutatva, hogy a listák fejét. 194 00:10:06,015 --> 00:10:08,890 Nos, miért csináljuk ezt, már Van egy mutató a listák vezetője, 195 00:10:08,890 --> 00:10:10,974 miért nem csak mozgatni, hogy az egyik körül? 196 00:10:10,974 --> 00:10:13,140 Nos, mint mondtam, ez tényleg fontos számunkra 197 00:10:13,140 --> 00:10:17,580 hogy mindig nyomon követni a legelső elem a listában. 198 00:10:17,580 --> 00:10:21,270 És így sokkal jobb hogy hozzon létre egy másolatot, hogy 199 00:10:21,270 --> 00:10:25,350 és használni, hogy mozogni így soha Véletlenül elmozdulni, vagy mindig 200 00:10:25,350 --> 00:10:30,430 Van egy mutató egy bizonyos ponton, amely jobbra az első eleme a listán. 201 00:10:30,430 --> 00:10:33,290 Tehát jobb, hogy hozzon létre egy második, hogy az általunk használt mozgatni. 202 00:10:33,290 --> 00:10:35,877 >> Aztán csak összehasonlítani, hogy Az érték mező a csomóponton 203 00:10:35,877 --> 00:10:38,960 az, amit keresünk, és ha ez Nem, mi csak lépjen a következő csomópontot. 204 00:10:38,960 --> 00:10:41,040 És mi csinálom, hogy újra és újra, és újra, 205 00:10:41,040 --> 00:10:44,811 amíg akár meg, az elem, vagy elérünk 206 00:10:44,811 --> 00:10:47,310 null-- elértük a végét A listán van, és nincs ott. 207 00:10:47,310 --> 00:10:50,540 Ez remélhetőleg cseng Önnek, mint csak lineáris keresés, 208 00:10:50,540 --> 00:10:54,430 mi csak lemásolják azt egyszeresen láncolt lista szerkezete 209 00:10:54,430 --> 00:10:56,280 ahelyett, hogy a tömb csinálni. 210 00:10:56,280 --> 00:10:58,210 >> Tehát itt egy példa egyszeresen láncolt lista. 211 00:10:58,210 --> 00:11:00,043 Ez az egyik áll Öt csomópontok, és van 212 00:11:00,043 --> 00:11:04,330 egy mutatót a fejét a listát, amely az úgynevezett listán. 213 00:11:04,330 --> 00:11:07,385 Az első dolog, amit akarok, újra létrehozni, hogy a bejárás mutató. 214 00:11:07,385 --> 00:11:09,760 Így most már két mutató Ezen a ponton, hogy ugyanaz a dolog. 215 00:11:09,760 --> 00:11:15,025 >> Most, itt megjegyezni azt is, én nem Van malloc minden helyet trav. 216 00:11:15,025 --> 00:11:18,970 Azt nem mondtam, trav egyenlő malloc valamit, hogy csomópont már létezik, 217 00:11:18,970 --> 00:11:21,160 hogy a tér a memóriában már létezik. 218 00:11:21,160 --> 00:11:24,290 Tehát minden, amit valójában csinál van létrehoz egy másik mutatót is. 219 00:11:24,290 --> 00:11:28,210 Én nem mallocing további hely, csak most már két mutató 220 00:11:28,210 --> 00:11:31,370 rámutatva, hogy ugyanaz a dolog. 221 00:11:31,370 --> 00:11:33,710 >> Szóval van 2, amit én keresek? 222 00:11:33,710 --> 00:11:37,220 Nos, nem, így ahelyett, hogy én vagyok fog átmenni a következőre. 223 00:11:37,220 --> 00:11:41,740 Tehát alapvetően azt mondanám, trav egyenlő trav következő. 224 00:11:41,740 --> 00:11:43,630 3, amit én keresek, nem. 225 00:11:43,630 --> 00:11:45,780 Szóval továbbra is megy keresztül, míg végül 226 00:11:45,780 --> 00:11:48,690 eljutni 6 ami azt, amit keresek alapozva, a függvényhívás 227 00:11:48,690 --> 00:11:51,600 Nekem van a csúcson ott, és így kész vagyok. 228 00:11:51,600 --> 00:11:54,150 >> Mi lenne, ha az elem vagyok keres nincs a listán, 229 00:11:54,150 --> 00:11:55,510 tart még mindig dolgozni? 230 00:11:55,510 --> 00:11:57,120 Nos, észreveheti, hogy a listán Itt finoman más, 231 00:11:57,120 --> 00:11:59,410 Ez is egy olyan dolog, ami Fontos a láncolt listák, 232 00:11:59,410 --> 00:12:01,780 Önnek nem kell megőrizni ezek az adott sorrendben. 233 00:12:01,780 --> 00:12:05,390 Próbálja ki Ön is szeretné, de lehet, hogy már észre, 234 00:12:05,390 --> 00:12:09,310 hogy mi nem követi nyomon a mi több elemet vagyunk. 235 00:12:09,310 --> 00:12:13,150 >> És ez a fajta egy kereskedelmi, hogy mi Van a láncolt lista versek tömbök, 236 00:12:13,150 --> 00:12:15,300 van az, nincs véletlen hozzáférésű többé. 237 00:12:15,300 --> 00:12:18,150 Nem lehet csak mondani, azt akarom, menni a 0. elem, 238 00:12:18,150 --> 00:12:21,410 vagy a 6. elem az én tömb, amit tehetünk egy tömbben. 239 00:12:21,410 --> 00:12:25,080 Nem tudok mondani akarok menni a 0. elem, vagy a 6. elem, 240 00:12:25,080 --> 00:12:30,360 vagy a 25. eleme én láncolt lista, nincs index velük kapcsolatban. 241 00:12:30,360 --> 00:12:33,660 És ez így nem igazán számít ha megőrizzük a listát érdekében. 242 00:12:33,660 --> 00:12:36,080 Ha azt szeretnénk, hogy Ön biztosan, de van 243 00:12:36,080 --> 00:12:38,567 nincs ok, miért kell kell őrizni bármilyen sorrendben. 244 00:12:38,567 --> 00:12:40,400 Tehát újra, próbáljuk meg megtalálja 6 ebben a listában. 245 00:12:40,400 --> 00:12:43,200 Nos, kezdjük a kezdődő, nem találunk 6, 246 00:12:43,200 --> 00:12:47,690 és akkor továbbra sem találni 6, amíg végül eljut ide. 247 00:12:47,690 --> 00:12:52,790 Szóval most trav pontot a csomópont amely 8 és hat nem ott. 248 00:12:52,790 --> 00:12:55,250 >> Így a következő lépés az lenne, hogy menjen a következő mutató, 249 00:12:55,250 --> 00:12:57,440 így mondják trav egyenlő trav következő. 250 00:12:57,440 --> 00:13:00,750 Nos, trav következő, jelzett A piros doboz van, null. 251 00:13:00,750 --> 00:13:03,020 Szóval van hová menj, és ezért ezen a ponton 252 00:13:03,020 --> 00:13:06,120 arra lehet következtetni, hogy elértük a végén a láncolt lista, 253 00:13:06,120 --> 00:13:07,190 és 6 nem ott. 254 00:13:07,190 --> 00:13:10,980 És akkor vissza kell hamis ebben az esetben. 255 00:13:10,980 --> 00:13:14,540 >> OK, hogyan tegyen be egy új csomópontot az láncolt lista? 256 00:13:14,540 --> 00:13:17,310 Így voltunk képesek létrehozni A láncolt lista a semmiből, 257 00:13:17,310 --> 00:13:19,370 de akkor ehhez felépíteni egy láncot, és nem 258 00:13:19,370 --> 00:13:22,620 hozzon létre egy csomó különböző listákat. 259 00:13:22,620 --> 00:13:25,700 Azt szeretnénk, hogy egy listát, hogy van egy csomó csomópontok benne, 260 00:13:25,700 --> 00:13:28,040 Nem egy csomó listák egyetlen csomópont. 261 00:13:28,040 --> 00:13:31,260 Tehát nem csak tartani a CREATE funkció a korábban megadott, most 262 00:13:31,260 --> 00:13:33,860 akar szúrni egy listáját, amely már létezik. 263 00:13:33,860 --> 00:13:36,499 >> Tehát ebben az esetben, megyünk átadni két érv, 264 00:13:36,499 --> 00:13:39,290 A mutatót a fejét, hogy láncolt lista, hogy szeretnénk felvenni. 265 00:13:39,290 --> 00:13:40,910 Ismét, ez miért olyan Fontos, hogy mindig 266 00:13:40,910 --> 00:13:43,400 nyomon követni azt, mert ez az egyetlen módja annak, hogy valóban 267 00:13:43,400 --> 00:13:46,690 hivatkoznia kell az egész lista Csak egy mutatót az első elemet. 268 00:13:46,690 --> 00:13:49,360 Tehát szeretnénk átadni a mutatót, hogy az első elem, 269 00:13:49,360 --> 00:13:52,226 és milyen értéket is szeretnénk felvenni a listára. 270 00:13:52,226 --> 00:13:54,600 És végül ez a funkció fog visszatérni egy mutatót 271 00:13:54,600 --> 00:13:57,980 hogy az új vezetője a láncolt lista. 272 00:13:57,980 --> 00:13:59,700 >> Milyen lépésekben itt szó? 273 00:13:59,700 --> 00:14:02,249 Nos, például csak létre, meg kell dinamikusan osztja 274 00:14:02,249 --> 00:14:05,540 hely egy új csomópontot, és ellenőrizze, Biztos, hogy ne fogyjon el a memóriában, újra, 275 00:14:05,540 --> 00:14:07,150 mert mi használ malloc. 276 00:14:07,150 --> 00:14:09,080 Aztán szeretne venni és helyezze be a csomópont, 277 00:14:09,080 --> 00:14:12,730 így fel a számot, amit Val, a csomópont. 278 00:14:12,730 --> 00:14:17,310 Azt akarjuk, hogy helyezze be a csomópontra Az elején a láncolt lista. 279 00:14:17,310 --> 00:14:19,619 >> Oka van annak, hogy én akarom ezt, és ez 280 00:14:19,619 --> 00:14:21,910 Lehet, hogy érdemes egy második szünetelteti a videót itt, 281 00:14:21,910 --> 00:14:25,860 és arra gondolok, miért akarná illessze elején egy kapcsolt 282 00:14:25,860 --> 00:14:26,589 listán. 283 00:14:26,589 --> 00:14:28,630 Ismét azt már korábban említettem hogy nem igazán 284 00:14:28,630 --> 00:14:33,020 számít, ha megőrizzük azt bármilyen érdekében, így lehet, hogy ez egy nyom. 285 00:14:33,020 --> 00:14:36,040 És láttad, hogy mi történne, ha akart az alábbiakra: vagy csak egy pillanatot 286 00:14:36,040 --> 00:14:37,360 ezelőtt, amikor megyünk a keresés akkor 287 00:14:37,360 --> 00:14:39,235 látta, hogy mi történne, ha akartuk 288 00:14:39,235 --> 00:14:41,330 beszúrni végén a listában. 289 00:14:41,330 --> 00:14:44,750 Mert nincs mutatót az a lista végére. 290 00:14:44,750 --> 00:14:47,490 >> Tehát az ok, hogy szeretnék beilleszteni az elején, 291 00:14:47,490 --> 00:14:49,380 azért van, mert meg tudom csinálni azonnal. 292 00:14:49,380 --> 00:14:52,730 Nekem van egy mutató az elején, és fogjuk látni ezt a vizuális második. 293 00:14:52,730 --> 00:14:55,605 De ha azt szeretné szúrni a végén, El kell kezdeni az elején, 294 00:14:55,605 --> 00:14:58,760 áthalad egészen a végéhez, majd tack be. 295 00:14:58,760 --> 00:15:01,420 Szóval ez azt jelentené, hogy behelyezése végén a lista 296 00:15:01,420 --> 00:15:04,140 válna o n működését, megy vissza 297 00:15:04,140 --> 00:15:06,720 hogy a vitát a számítási komplexitás. 298 00:15:06,720 --> 00:15:10,140 Ez lett belőle egy o n működését, ahol a lista egyre nagyobbak, és nagyobb, 299 00:15:10,140 --> 00:15:13,310 és nagyobb, ez lesz egyre nehezebb a forduláshoz valamit 300 00:15:13,310 --> 00:15:14,661 a végén. 301 00:15:14,661 --> 00:15:17,410 De ez mindig nagyon könnyű csapáson valamit az elején, 302 00:15:17,410 --> 00:15:19,060 Ön mindig az elején. 303 00:15:19,060 --> 00:15:21,620 >> És majd meglátjuk vizuális e újra. 304 00:15:21,620 --> 00:15:24,100 És akkor egyszer kész vagyunk, ha egyszer mi már be az új csomópontot, 305 00:15:24,100 --> 00:15:26,880 szeretnénk visszatérni a mutatót az új vezetője a láncolt lista, amely 306 00:15:26,880 --> 00:15:29,213 mivel mi behelyezése a kezdődő, valóban lesz 307 00:15:29,213 --> 00:15:31,060 egy mutatót a csomópont most létrehozott. 308 00:15:31,060 --> 00:15:33,280 Nézzük elképzelni ezt, mert azt hiszem, hogy segíteni fog. 309 00:15:33,280 --> 00:15:36,661 >> Tehát itt a lista, áll négy elem, egy csomópont, amely 15, 310 00:15:36,661 --> 00:15:38,410 amely rámutat, hogy egy csomópont tartalmazó 9, amely 311 00:15:38,410 --> 00:15:41,370 rámutat, hogy egy csomópont, amely 13, amely rámutat, hogy egy csomópont tartalmazó 312 00:15:41,370 --> 00:15:44,840 10, amely a null mutatót a következő mutatót 313 00:15:44,840 --> 00:15:47,010 úgy, hogy a vége a listán. 314 00:15:47,010 --> 00:15:50,200 Ezért szeretnénk beszúrni új csomópont, melynek értéke 12 315 00:15:50,200 --> 00:15:52,720 elején az e listát, mit csináljunk? 316 00:15:52,720 --> 00:15:58,770 Nos, először is malloc helyet a csomópontot, majd rakjuk 12 odabent. 317 00:15:58,770 --> 00:16:02,211 >> Így most már elérte a döntési pont, ugye? 318 00:16:02,211 --> 00:16:03,960 Van egy pár mutatókat, hogy mi lehet 319 00:16:03,960 --> 00:16:06,770 mozog, melyiket haladunk először? 320 00:16:06,770 --> 00:16:09,250 Nem kellene, hogy 12 pont Az új vezetője a list-- 321 00:16:09,250 --> 00:16:13,020 vagy megbocsát, kéne tenni 12 pont a régi lista élére? 322 00:16:13,020 --> 00:16:15,319 Vagy azt mondjuk, hogy a lista most kezdődik 12. 323 00:16:15,319 --> 00:16:17,110 Van egy különbség ott, és akkor nézd 324 00:16:17,110 --> 00:16:19,870 mi történik mind a második. 325 00:16:19,870 --> 00:16:23,350 >> De ez vezet nagy téma a tálaló, 326 00:16:23,350 --> 00:16:26,280 ami az, hogy az egyik legtrükkösebb dolog a láncolt listák 327 00:16:26,280 --> 00:16:30,980 az, hogy gondoskodjon a mutatók a megfelelő sorrendben. 328 00:16:30,980 --> 00:16:34,520 Ha mozgatja a dolgokat ki annak érdekében, akkor a végén véletlenül 329 00:16:34,520 --> 00:16:36,050 orphaning a többi a lista. 330 00:16:36,050 --> 00:16:37,300 És itt egy példa erre. 331 00:16:37,300 --> 00:16:40,540 Szóval menjünk a gondolattal of-- Nos, éppen most létrehozott 12. 332 00:16:40,540 --> 00:16:43,180 Tudjuk 12 lesz Az új lista élére, 333 00:16:43,180 --> 00:16:47,660 és így miért nem csak mozgatni A lista mutatóját van. 334 00:16:47,660 --> 00:16:49,070 >> OK, tehát ez jó. 335 00:16:49,070 --> 00:16:51,560 Tehát most, ha nem 12 következő pont? 336 00:16:51,560 --> 00:16:54,580 Úgy értem, vizuálisan láthatjuk hogy fog mutatni 15, 337 00:16:54,580 --> 00:16:57,250 mint az emberek, hogy tényleg nyilvánvaló számunkra. 338 00:16:57,250 --> 00:17:00,300 Hogyan működik a számítógép tudja? 339 00:17:00,300 --> 00:17:02,720 Nem kell semmit rámutatva, hogy 15 már, ugye? 340 00:17:02,720 --> 00:17:05,869 >> Elvesztettük minden képességét, hogy olvassa el 15. 341 00:17:05,869 --> 00:17:11,460 Nem tudjuk megmondani, az új melletti nyílra egyenlők valamit, nincs ott semmi. 342 00:17:11,460 --> 00:17:13,510 Sőt, most már árva a többi a lista 343 00:17:13,510 --> 00:17:16,465 ezzel, most már véletlenül tört a láncot. 344 00:17:16,465 --> 00:17:18,089 És mi persze nem akarom csinálni. 345 00:17:18,089 --> 00:17:20,000 >> Szóval menjünk vissza, és próbáljuk meg újra. 346 00:17:20,000 --> 00:17:24,060 Lehet, hogy a helyes dolog az, hogy hozzanak 12 következő mutatót 347 00:17:24,060 --> 00:17:28,290 a régi lista élére első, akkor tudjuk mozgatni a lista vége. 348 00:17:28,290 --> 00:17:30,420 És valóban, hogy a megfelelő sorrendben, hogy mi 349 00:17:30,420 --> 00:17:32,836 kell, hogy kövesse, mikor vagyunk dolgozó egyszeresen láncolt lista. 350 00:17:32,836 --> 00:17:36,460 Mi mindig szeretne csatlakozni a Új elem a listán, 351 00:17:36,460 --> 00:17:41,010 mielőtt vesszük, hogy milyen fontos lépés a változó 352 00:17:41,010 --> 00:17:43,360 ahol a fej a linkelt lista. 353 00:17:43,360 --> 00:17:46,740 Ismét, ez egy ilyen alapvető dolog, nem akarjuk elveszíteni követni. 354 00:17:46,740 --> 00:17:49,310 >> Ezért szeretnénk, hogy győződjön meg arról, hogy minden egymáshoz láncolva, 355 00:17:49,310 --> 00:17:52,040 mielőtt tovább megyünk, hogy a mutató. 356 00:17:52,040 --> 00:17:55,300 És így ez lenne a helyes sorrendben, amely kapcsolódni 12 a listához, 357 00:17:55,300 --> 00:17:57,630 akkor azt mondják, hogy a lista kezdődik a 12. 358 00:17:57,630 --> 00:18:00,860 Ha azt mondtuk a listán indul 12 és Ezután megpróbált csatlakozni a 12. a listán, 359 00:18:00,860 --> 00:18:02,193 már láttuk, mi történik. 360 00:18:02,193 --> 00:18:04,920 Elveszítjük a listában a hibát. 361 00:18:04,920 --> 00:18:06,740 >> OK, így még egy dolog beszélni. 362 00:18:06,740 --> 00:18:09,750 Mi van, ha azt akarjuk, hogy megszabaduljon Egy egész láncolt lista egyszerre? 363 00:18:09,750 --> 00:18:11,750 Ismét mi mallocing mindez teret, és így 364 00:18:11,750 --> 00:18:13,351 kell kiszabadítani, ha végeztünk. 365 00:18:13,351 --> 00:18:15,350 Tehát most, hogy törli a teljes láncolt lista. 366 00:18:15,350 --> 00:18:16,850 Nos, mit akarunk csinálni? 367 00:18:16,850 --> 00:18:20,460 >> Ha elértük a null pointer, mi akarjuk állítani, különben csak törölni 368 00:18:20,460 --> 00:18:23,420 a többi a listát, majd szabadíts meg. 369 00:18:23,420 --> 00:18:28,890 Törlés a többi a lista, majd szabadítani a jelenlegi csomópont. 370 00:18:28,890 --> 00:18:32,850 Mit szól hozzá, mint, milyen technikát kell beszélgettünk 371 00:18:32,850 --> 00:18:35,440 a korábban, hogy hangzik, mint a? 372 00:18:35,440 --> 00:18:39,560 Törlés mindenki más, akkor gyere vissza és törölje nekem. 373 00:18:39,560 --> 00:18:42,380 >> Ez a rekurzió tettük a probléma egy kicsit kisebb, 374 00:18:42,380 --> 00:18:46,910 azt mondjuk törölni mindenkinek más, akkor törölheti nekem. 375 00:18:46,910 --> 00:18:50,940 És tovább az úton, hogy a csomópont azt fogja mondani, törölje mindenki más. 376 00:18:50,940 --> 00:18:53,940 De végül mi lesz a pont, ahol a lista null, 377 00:18:53,940 --> 00:18:55,310 és ez a mi alapeset. 378 00:18:55,310 --> 00:18:57,010 >> Szóval vessünk egy pillantást erre, és hogy ez hogyan működik. 379 00:18:57,010 --> 00:18:59,759 Tehát itt a lista, hogy ez ugyanaz felsorolni mi csak beszélünk, 380 00:18:59,759 --> 00:19:00,980 és van az a lépéseket. 381 00:19:00,980 --> 00:19:04,200 Van egy csomó szöveget itt, de Remélhetőleg a vizualizáció segít. 382 00:19:04,200 --> 00:19:08,557 >> Tehát have-- és én is húzta a mi verem keret illusztráció 383 00:19:08,557 --> 00:19:10,890 a mi video hívás halom, és remélhetőleg mindezt 384 00:19:10,890 --> 00:19:13,260 együtt megmutatja, mi folyik itt. 385 00:19:13,260 --> 00:19:14,510 Tehát itt van a pszeudokódja kódot. 386 00:19:14,510 --> 00:19:17,830 Ha elérjük a null pointer, hagyja abba, különben 387 00:19:17,830 --> 00:19:21,320 törölje a többi a lista, akkor szabad a jelenlegi csomópont. 388 00:19:21,320 --> 00:19:25,700 Tehát most, list-- A mutató, hogy mi vagyunk 389 00:19:25,700 --> 00:19:28,410 halad, hogy elpusztítsa pontot és 12. 390 00:19:28,410 --> 00:19:33,340 12 nem egy null pointer, így vagyunk megy, hogy törölje a többi a lista. 391 00:19:33,340 --> 00:19:35,450 >> Mi törlésével többiek részt? 392 00:19:35,450 --> 00:19:37,950 Nos, ez azt jelenti, hogy egy hívja elpusztítani, mondván 393 00:19:37,950 --> 00:19:42,060 hogy 15 a kezdete a többi listát akarunk pusztítani. 394 00:19:42,060 --> 00:19:47,480 És így a hívás, hogy elpusztítsa 12 fajta tartásban. 395 00:19:47,480 --> 00:19:52,690 Fagyott ott vár a hívja, hogy elpusztítsa 15, hogy befejezze a munkát. 396 00:19:52,690 --> 00:19:56,280 >> Nos, 15 nem egy null pointer, és így fog mondani, rendben, 397 00:19:56,280 --> 00:19:58,450 Nos, törölje a többit a lista. 398 00:19:58,450 --> 00:20:00,760 A többi a lista kezd 9, és ezért most is csak 399 00:20:00,760 --> 00:20:04,514 várj, amíg nem törli az összes, hogy cucc, akkor gyere vissza, és törölje nekem. 400 00:20:04,514 --> 00:20:06,680 Nos 9 fog mondani, nos, Nem vagyok egy null pointer, 401 00:20:06,680 --> 00:20:09,020 így törölje a többit a lista itt. 402 00:20:09,020 --> 00:20:11,805 És így próbálja megsemmisíteni 13. 403 00:20:11,805 --> 00:20:15,550 13 azt mondja, nem vagyok null pointer, Ugyanez, átadja a bak. 404 00:20:15,550 --> 00:20:17,930 10 nem null pointer, 10 tartalmaz egy null mutató, 405 00:20:17,930 --> 00:20:20,200 de 10 önmaga nem nullmutató most, 406 00:20:20,200 --> 00:20:22,470 És ez így megy a bak is. 407 00:20:22,470 --> 00:20:25,560 >> És most felsorolni pont ott, Tényleg emlékeztet az some-- 408 00:20:25,560 --> 00:20:28,710 ha lenne több hely van a kép, ez a pont, hogy néhány véletlenszerű tér 409 00:20:28,710 --> 00:20:29,960 hogy nem tudjuk, mi az. 410 00:20:29,960 --> 00:20:34,680 Ez a nullmutató bár a lista van szó most meg ez értékei null. 411 00:20:34,680 --> 00:20:36,820 Ez mutatva legbelül, hogy piros doboz. 412 00:20:36,820 --> 00:20:39,960 Elérkeztünk egy null pointer, így meg tudjuk állítani, és már készen is vagyunk. 413 00:20:39,960 --> 00:20:46,230 >> És így, hogy a lila keret now-- a tetejére stack-- ez az aktív keret, 414 00:20:46,230 --> 00:20:47,017 de ez kész. 415 00:20:47,017 --> 00:20:48,600 Ha elértük a null pointer, hagyja abba. 416 00:20:48,600 --> 00:20:51,290 Nem csinálunk semmit, Nem szabad egy null pointer, 417 00:20:51,290 --> 00:20:55,070 mi nem malloc semmilyen helyet, és így készen vagyunk. 418 00:20:55,070 --> 00:20:57,590 Annak érdekében, hogy a funkció keret megsemmisül, és mi 419 00:20:57,590 --> 00:21:00,930 resume-- kezünkbe veszünk, ahol hagytuk le a következő legmagasabb, ami 420 00:21:00,930 --> 00:21:02,807 ez sötétkék kerettel itt. 421 00:21:02,807 --> 00:21:04,390 Tehát vedd fel ott, ahol abbahagytuk. 422 00:21:04,390 --> 00:21:06,598 Mi törölve a többi a listán már, így most mi vagyunk 423 00:21:06,598 --> 00:21:08,000 fog felszabadítani a jelenlegi csomópont. 424 00:21:08,000 --> 00:21:12,920 Tehát most is szabad ezt a csomópontot, és most elértük a funkció végét. 425 00:21:12,920 --> 00:21:16,810 És így a függvény keret megsemmisül, és mi vedd fel a fény kék. 426 00:21:16,810 --> 00:21:20,650 >> Tehát says-- Már done-- törlése a többi a listán, így 427 00:21:20,650 --> 00:21:23,140 szabad a jelenlegi csomópont. 428 00:21:23,140 --> 00:21:26,520 És most a sárga keret vissza a köteg tetején. 429 00:21:26,520 --> 00:21:29,655 És így látod, mi most tönkretéve a listán jobbról balra. 430 00:21:29,655 --> 00:21:33,710 431 00:21:33,710 --> 00:21:37,280 >> Mi történt volna, mégis, Ha mi tette a dolgokat, hogy rossz irányba? 432 00:21:37,280 --> 00:21:39,410 Csakúgy, mint amikor megpróbáltuk hogy egy elemet. 433 00:21:39,410 --> 00:21:41,909 Ha elrontotta a lánc, ha mi nem csatlakozhat a mutatók 434 00:21:41,909 --> 00:21:44,690 a helyes sorrendben, ha Csak kiszabadította az első elemet, 435 00:21:44,690 --> 00:21:47,420 ha csak megszabadult a A lista élére, most 436 00:21:47,420 --> 00:21:49,642 nincs lehetősége arra utalnak a többi a lista. 437 00:21:49,642 --> 00:21:51,350 És így lett volna árva mindent, 438 00:21:51,350 --> 00:21:53,880 mi lett volna, mi van nevezett memóriavesztés. 439 00:21:53,880 --> 00:21:56,800 Ha felidézzük a mi video A memória dinamikus, 440 00:21:56,800 --> 00:21:58,650 ez nem túl jó dolog. 441 00:21:58,650 --> 00:22:00,810 >> Szóval mint mondtam, több művelet 442 00:22:00,810 --> 00:22:04,010 hogy meg kell használni a munka A láncolt lista hatékonyan. 443 00:22:04,010 --> 00:22:08,430 És lehet, hogy észre kihagytam egyet, törlése egyetlen eleme egy csatlakoztatott 444 00:22:08,430 --> 00:22:09,064 listán. 445 00:22:09,064 --> 00:22:10,980 Az ok, hogy ezt tettem ez valójában egyfajta 446 00:22:10,980 --> 00:22:14,360 trükkös gondolkodni, hogyan kell törölni Egyetlen elem egyszeresen 447 00:22:14,360 --> 00:22:15,600 láncolt lista. 448 00:22:15,600 --> 00:22:19,950 Meg kell tudni, hogy átugorják valamit a listán, amely 449 00:22:19,950 --> 00:22:22,975 azt jelenti, hogy egy point-- vagyunk törölni akarja ezt node-- 450 00:22:22,975 --> 00:22:25,350 de ahhoz, hogy ez így ne vesszenek el adatok, 451 00:22:25,350 --> 00:22:30,530 szükségünk van, hogy csatlakoztassa a node ide, itt. 452 00:22:30,530 --> 00:22:33,390 >> Szóval valószínűleg azért, hogy rossz vizuális szempontból. 453 00:22:33,390 --> 00:22:36,830 Úgyhogy elején a listát, mi átrágja magát, 454 00:22:36,830 --> 00:22:40,510 akarjuk törölni a csomópontot. 455 00:22:40,510 --> 00:22:43,440 Ha csak törölni, mi már megtört a lánc. 456 00:22:43,440 --> 00:22:45,950 Ez a csomópont itt utal minden mást, 457 00:22:45,950 --> 00:22:48,260 ez tartalmazza a láncot Innen ki. 458 00:22:48,260 --> 00:22:51,190 >> Szóval mit kell tennünk ténylegesen után megkapjuk a pontig, 459 00:22:51,190 --> 00:22:56,670 van szükségünk, hogy lépjen vissza egyet, és csatlakoztassa a csomópont át a csomóponton, 460 00:22:56,670 --> 00:22:58,590 így tudjuk majd törölje az egyik a közepén. 461 00:22:58,590 --> 00:23:02,120 De egyedül láncolt listák nem adjon nekünk egy út visszafelé. 462 00:23:02,120 --> 00:23:05,160 Tehát meg kell tartani vagy két pointert, és mozgassa őket 463 00:23:05,160 --> 00:23:09,527 fajta off lépésben, egymás mögött Más, ahogy haladunk, vagy kap egy pontot 464 00:23:09,527 --> 00:23:11,110 majd küldeni egy másik mutatót keresztül. 465 00:23:11,110 --> 00:23:13,150 És mint látható, ez lehet, hogy egy kicsit rendetlen. 466 00:23:13,150 --> 00:23:15,360 Szerencsére van Egy másik módja annak, hogy megoldja ezt, 467 00:23:15,360 --> 00:23:17,810 amikor arról beszélünk, kétszeresen láncolt listák. 468 00:23:17,810 --> 00:23:20,720 >> Én Doug Lloyd, ez CS50. 469 00:23:20,720 --> 00:23:22,298