1 00:00:00,000 --> 00:00:02,832 [MŪZIKA ATSKAŅOTĀSSKAN MŪZIKA] 2 00:00:05,670 --> 00:00:10,485 DUGS LOJSDAGS LOIDS: Labi, tāpēctātad šajā kursa punktā mēs esam 3 00:00:10,485 --> 00:00:15,300 apskatījuši daudzus C valodas pamatus. 4 00:00:15,300 --> 00:00:16,455 Mēs daudz zinām par mainīgajiem lielumiem, masīviem, rādītājiem un 5 00:00:16,455 --> 00:00:17,610 visu to labovisām tām noderīgajām lietām. 6 00:00:17,610 --> 00:00:20,745 Tie visi ir iebūvēti, lai tos uzskatītu par pamatiem, taču mēs varam 7 00:00:20,745 --> 00:00:23,880 darīt vairāk, vai ne? 8 00:00:23,880 --> 00:00:27,930 Mēs varam apvienot lietas interesantā veidā. 9 00:00:27,930 --> 00:00:32,150 Un tāpēc darīsim to, sāksim atzarot no tāizvērst to, ko mums sniedz 10 00:00:32,150 --> 00:00:36,370 C, un sāksim veidot savas datu struktūras, izmantojot šos veidojošos 11 00:00:36,370 --> 00:00:40,590 blokus kopā, lai paveiktu kaut ko patiešām vērtīgu, noderīgu. 12 00:00:40,590 --> 00:00:42,005 Viens no veidiem, kā mēs to varam izdarīt, ir runāt par 13 00:00:42,005 --> 00:00:43,420 kolekcijāmdatu kopām. 14 00:00:43,420 --> 00:00:47,225 Līdz šim mums ir bijusi viena veida datu struktūra līdzīgu vērtību, 15 00:00:47,225 --> 00:00:51,030 līdzīgu vērtību kolekcijasdatu kopu attēlošanai. 16 00:00:51,030 --> 00:00:52,350 Tas būtu masīvs. 17 00:00:52,350 --> 00:00:54,685 Mums ir veselu skaitļu kolekcijasdatu kopas vai rakstzīmju 18 00:00:54,685 --> 00:00:57,020 kolekcijasdatu kopas un tā tālāk. 19 00:00:57,020 --> 00:01:00,120 Struktūras ir arī sava veida datu struktūra informācijas vākšanai, 20 00:01:00,120 --> 00:01:03,220 taču tā nav paredzēta līdzīgu vērtību apkopošanai. 21 00:01:03,220 --> 00:01:08,090 TasTā parasti sajauc dažādus datu tipus vienā lodziņā. 22 00:01:08,090 --> 00:01:12,505 Bet tas pats par sevi netiek izmantots, lai savienotu kopā vai 23 00:01:12,505 --> 00:01:16,920 savienotu līdzīgus vienumus, piemēram, masīvukā, piemēram, masīvs. 24 00:01:16,920 --> 00:01:20,103 Masīvi ir lieliski piemēroti elementu meklēšanai, taču atcerieties, 25 00:01:20,103 --> 00:01:23,286 ka tos ir ļoti grūti ievietot masīvā, ja vien mēs neievietojam šī 26 00:01:23,286 --> 00:01:26,470 masīva pašās beigās. 27 00:01:26,470 --> 00:01:29,730 Un labākais piemērs tam ir ievietošanas kārtošana. 28 00:01:29,730 --> 00:01:33,583 Ja atceraties mūsu video par ievietošanas kārtošanu, bija daudz 29 00:01:33,583 --> 00:01:37,436 izdevumu, kas saistīti ar elementu paņemšanu un pārvietošanu, lai 30 00:01:37,436 --> 00:01:41,290 kaut ko ievietotu jūsu masīva vidū. 31 00:01:41,290 --> 00:01:44,690 Masīvi cieš arī no citas problēmas, kas ir neelastība. 32 00:01:44,690 --> 00:01:47,150 Kad mēs deklarējam masīvu, mēs iegūstam vienu šāvienuiespēju. 33 00:01:47,150 --> 00:01:49,790 Mums jāsakavaram pateikt, ka es vēlos tik daudz elementu. 34 00:01:49,790 --> 00:01:53,210 Var būt 100, 1000, var būt x, kur x ir skaitlis, ko lietotājs mums 35 00:01:53,210 --> 00:01:56,630 norādījis uzvednē vai komandrindā. 36 00:01:56,630 --> 00:02:00,495 Bet mēs to saņemam tikai vienu reizi, mēs nevaram pateikt, ak, 37 00:02:00,495 --> 00:02:04,360 patiesībā man vajadzēja 101 vai man vajadzēja x plus 20. 38 00:02:04,360 --> 00:02:08,086 Par vēlu, mēs jau esam deklarējuši masīvu, un, ja mēs vēlamies iegūt 39 00:02:08,086 --> 00:02:11,813 101 vai x plus 20, mums ir jādeklarē pavisam cits masīvs, jāpārkopē 40 00:02:11,813 --> 00:02:15,540 visi masīva elementi, un tad mums ir pietiekami daudz. 41 00:02:15,540 --> 00:02:18,755 Un ko darīt, ja mēs atkal kļūdāmies, ja mums tiešām ir nepieciešams 42 00:02:18,755 --> 00:02:21,970 102 vai x plus 40, mums tas ir jādara vēlreiz. 43 00:02:21,970 --> 00:02:25,802 Tāpēc tie ir ļoti neelastīgi, lai mainītu mūsu datu izmērus, taču, ja 44 00:02:25,802 --> 00:02:29,635 mēs apvienojam dažus pamatus, ko jau esam iemācījušies par rādītājiem 45 00:02:29,635 --> 00:02:33,468 un struktūrām, jo īpaši izmantojot dinamisko atmiņas piešķiršanu ar 46 00:02:33,468 --> 00:02:37,301 mallocmalloc, mēs varam apvienot šīs daļas, lai izveidotu jaunu. datu 47 00:02:37,301 --> 00:02:41,134 struktūrastruktūru — atsevišķi saistīts sarakstssaistītu sarakstu, ko 48 00:02:41,134 --> 00:02:44,967 mēs varētu teikt —, kas ļauj mums palielināt un samazināt vērtību 49 00:02:44,967 --> 00:02:48,800 kolekcijudatu kopu, un mēs netērēsim vietu. 50 00:02:48,800 --> 00:02:53,320 Tātad atkal mēs šo ideju, šo jēdzienu saucam par saistīto sarakstu. 51 00:02:53,320 --> 00:02:56,066 KonkrētiProti, šajā videoklipā mēs runājam par atsevišķi saistītu 52 00:02:56,066 --> 00:02:58,813 sarakstu, un pēc tam citā videoklipā mēs runāsim par divkārši 53 00:02:58,813 --> 00:03:01,560 saistītiem sarakstiem, kas šeit ir tikai tēmas variants. 54 00:03:01,560 --> 00:03:04,490 Bet atsevišķi saistīts saraksts sastāv no mezgliem, mezgli ir tikai 55 00:03:04,490 --> 00:03:07,420 abstrakts termins — tas ir tikai kaut kas, ko es saucunosaucu, tā ir 56 00:03:07,420 --> 00:03:10,350 sava veida struktūra, vai es esmune? 57 00:03:10,350 --> 00:03:13,270 Vienkārši nosauksim to par mezglu — un šim mezglam ir divi 58 00:03:13,270 --> 00:03:16,190 dalībniekidivi elementi vai divi lauki. 59 00:03:16,190 --> 00:03:18,723 Tam ir dati, parasti vesels skaitlis, rakstzīmju pludiņšpeldošā 60 00:03:18,723 --> 00:03:21,256 punkta skaitlis, vai kāds cits datu tips, ko esat definējisdefinējuši 61 00:03:21,256 --> 00:03:23,790 ar tipu typedef. 62 00:03:23,790 --> 00:03:29,290 Un tajā ir rādītājs uz citu tāda paša veida mezglu. 63 00:03:29,290 --> 00:03:36,380 Tātad šajā mezglā ir divas lietas: dati un rādītājs uz citu mezglu. 64 00:03:36,380 --> 00:03:39,330 Un, ja sākat to vizualizēt, varat domāt par to kā par mezglu ķēdi, 65 00:03:39,330 --> 00:03:42,280 kas ir savienoti kopā. 66 00:03:42,280 --> 00:03:45,695 Mums ir pirmais mezgls, tajā ir dati un rādītājs uz otro mezglu, kurā 67 00:03:45,695 --> 00:03:49,110 ir dati, un rādītājs uz trešo mezglu. 68 00:03:49,110 --> 00:03:52,940 Un tāpēc mēs to saucam par saistīto sarakstu, tie ir saistīti kopā. 69 00:03:52,940 --> 00:03:56,070 Kā izskatās šī īpašā mezgla struktūra? 70 00:03:56,070 --> 00:03:59,180 Ja atceraties mūsu videoklipu par pielāgoto tipu definēšanu, 71 00:03:59,180 --> 00:04:02,290 izmantojot tipu deftypedef, mēs varam definēt struktūru, betun tips 72 00:04:02,290 --> 00:04:05,400 definēttype define šādu struktūru. 73 00:04:05,400 --> 00:04:09,645 tyepdeftypedef struct sllist, un tad es patvaļīgi izmantoju vārdu 74 00:04:09,645 --> 00:04:13,891 vērtību, lai norādītu jebkuru datu tipu. 75 00:04:13,891 --> 00:04:15,390 Jūs varētu nodot veselu skaitli vai peldētpeldošā punkta skaitli, 76 00:04:15,390 --> 00:04:16,890 jums var būt viss, ko vēlaties. 77 00:04:16,890 --> 00:04:19,389 Tas neaprobežojas tikai ar veseliem skaitļiem vai kaut ko tamlīdzīgu. 78 00:04:19,389 --> 00:04:22,849 Tātad vērtība ir tikai patvaļīgs datu tips un pēc tam rādītājs uz 79 00:04:22,849 --> 00:04:26,310 citu tāda paša veida mezglu. 80 00:04:26,310 --> 00:04:29,670 Tagad šeit ir neliela nozīmeaizķeršanās, definējot struktūru, ja tā 81 00:04:29,670 --> 00:04:33,030 ir pašreferences struktūra. 82 00:04:33,030 --> 00:04:35,340 Man ir jābūt pagaidu nosaukumam manai struktūrai. 83 00:04:35,340 --> 00:04:39,376 Galu galā es to nepārprotami vēlos saukt par sll node, kas galu galā 84 00:04:39,376 --> 00:04:43,413 ir mana tipa definīcijas jaunā nosaukuma daļa, taču es nevaru 85 00:04:43,413 --> 00:04:47,450 izmantot sll node šī savienojuma vidū. 86 00:04:47,450 --> 00:04:51,325 Iemesls ir tāds, ka es neesmu izveidojis tipu, ko sauc par sll node, 87 00:04:51,325 --> 00:04:55,200 līdz es šeit sasniedzu pēdējo punktu. 88 00:04:55,200 --> 00:04:57,460 Līdz šim brīdim man ir jābūt citam veidam, kā atsaukties uz šo datu 89 00:04:57,460 --> 00:04:59,720 veidu. 90 00:04:59,720 --> 00:05:02,440 Un tas ir pašreferences datu tips. 91 00:05:02,440 --> 00:05:05,460 Tas ir datu tips struktūrai, kurā ir dati, un rādītājs uz citu tāda 92 00:05:05,460 --> 00:05:08,480 paša veida struktūru. 93 00:05:08,480 --> 00:05:12,228 Tāpēc man ir jābūt iespējai vismaz īslaicīgi atsaukties uz šo datu 94 00:05:12,228 --> 00:05:15,976 tipu, tāpēc, piešķirot tam pagaidu nosaukumu struct sllist, es varu 95 00:05:15,976 --> 00:05:19,724 pateikt, ka vēlos rādītāju uz citu struct sllist, struct sllist 96 00:05:19,724 --> 00:05:23,472 zvaigznistar, un pēc tam pabeidzu definīciju, tagad varu saukt šo 97 00:05:23,472 --> 00:05:27,220 tipu par sll mezglunode. 98 00:05:27,220 --> 00:05:29,549 Tāpēc jūs redzat, ka šeit ir pagaidu nosaukums, bet šeit pastāvīgs 99 00:05:29,549 --> 00:05:31,879 nosaukums. 100 00:05:31,879 --> 00:05:35,634 Dažkārt var tikt rādītas, piemēram, struktūras definīcijas, kas nav 101 00:05:35,634 --> 00:05:39,390 pašreferences, kurām šeit nav norādīts precizējošs nosaukums. 102 00:05:39,390 --> 00:05:41,215 Tas vienkārši teiktu typedef struct, atveriet cirtaini 103 00:05:41,215 --> 00:05:43,040 figūriekavafigūriekavas un pēc tam definējiet to. 104 00:05:43,040 --> 00:05:46,025 Bet, ja jūsu struktūra ir pašreference, kā tas ir šajā gadījumā, jums 105 00:05:46,025 --> 00:05:49,010 ir jānorāda pagaidu tipa nosaukums. 106 00:05:49,010 --> 00:05:51,973 Bet galu galā, tagad, kad esam to izdarījuši, mēs varam vienkārši 107 00:05:51,973 --> 00:05:54,936 atsaukties uz šiem mezgliem, šīm vienībām kā maziem mezgliemsll nodes 108 00:05:54,936 --> 00:05:57,900 pārējā šī videoklipa nolūkos. 109 00:05:57,900 --> 00:06:00,900 Labi, tāpēctātad mēs zinām, kā izveidot saistītā saraksta mezglu. 110 00:06:00,900 --> 00:06:03,240 Mēs zinām, kā definēt saistītā saraksta mezglu. 111 00:06:03,240 --> 00:06:06,800 Tagad, ja mēs sāksim tos izmantot informācijas vākšanai, mums ir 112 00:06:06,800 --> 00:06:10,360 jāsaprot dažas darbības un ar tām jāstrādā. 113 00:06:10,360 --> 00:06:12,860 Mums ir jāzina, kā no zila gaisa izveidot saistīto sarakstu. 114 00:06:12,860 --> 00:06:14,901 Ja vēl nav saraksta, mēs vēlamies to sākt. 115 00:06:14,901 --> 00:06:18,365 Tāpēc mums ir jāspēj izveidot saistīto sarakstu, iespējams, ir 116 00:06:18,365 --> 00:06:21,830 jāmeklē saišu sarakstā, lai atrastu elementu, ko meklējam. 117 00:06:21,830 --> 00:06:23,880 Mums ir jāspēj sarakstā ievietot jaunas lietas, mēs vēlamies, lai 118 00:06:23,880 --> 00:06:25,930 mūsu saraksts varētu augt. 119 00:06:25,930 --> 00:06:28,090 Un līdzīgi, mēs vēlamies, lai mēs varētu izdzēst lietas no sava 120 00:06:28,090 --> 00:06:30,250 saraksta, mēs vēlamies, lai mūsu saraksts varētu sarukt. 121 00:06:30,250 --> 00:06:33,390 Un mūsu programmu beigās, it īpaši, ja atceraties, ka mēs parasti 122 00:06:33,390 --> 00:06:36,530 dinamiski piešķiram atmiņu, lai izveidotu šos sarakstus, mēs vēlamies 123 00:06:36,530 --> 00:06:39,670 atbrīvot visu šo atmiņu, kad esam pabeiguši darbu ar to. 124 00:06:39,670 --> 00:06:44,627 Un tāpēc mums ir jāspēj dzēst visu saistīto sarakstu vienā piegājienā. 125 00:06:44,627 --> 00:06:47,909 Tāpēc apskatīsim dažas no šīm darbībām un to, kā tās varētu 126 00:06:47,909 --> 00:06:51,192 vizualizēt, runājot īpašikonkrēti pseidokoda kodā. 127 00:06:51,192 --> 00:06:53,836 Tāpēc mēs vēlamies izveidot saistīto sarakstu, tāpēc varbūt mēs 128 00:06:53,836 --> 00:06:56,480 vēlamies definēt funkciju ar šo prototipu. 129 00:06:56,480 --> 00:07:01,005 sll node star, izveidojietcreate, un es nododu vienu argumentu, atkal 130 00:07:01,005 --> 00:07:05,530 kaut kādu patvaļīgu datu tipu, kādu patvaļīgu datu tipu. 131 00:07:05,530 --> 00:07:08,360 Bet es atgriežos — šai funkcijai ir jāatgriež man rādītājs, uz 132 00:07:08,360 --> 00:07:11,190 atsevišķi saistītu saraksta mezglu. 133 00:07:11,190 --> 00:07:14,545 Atkal mēs cenšamies no zila gaisa izveidot saistīto sarakstu, tāpēc 134 00:07:14,545 --> 00:07:17,900 man ir nepieciešams rādītājs uz šo sarakstu, kad esmu pabeidzis. 135 00:07:17,900 --> 00:07:19,420 Tātad, kādi soļi šeit ir saistītiiesaistīti? 136 00:07:19,420 --> 00:07:22,550 Pirmā lieta, ko es darīšu, ir dinamiski piešķirt vietu jaunam mezglam. 137 00:07:22,550 --> 00:07:26,689 Atkal mēs to veidojam no zila gaisa, tāpēc mums ir jāatrod vieta. 138 00:07:26,689 --> 00:07:28,356 Un, protams, uzreiz pēc tam, kad mēs esam izspiedušipiešķīruši vietu, 139 00:07:28,356 --> 00:07:30,024 mēs vienmēr pārbaudām, vai mūsu rādītājs — mums nav atgriezts nulles 140 00:07:30,024 --> 00:07:31,692 rādītājs. 141 00:07:31,692 --> 00:07:33,941 Jo, ja mēs cenšamies neievērot nulles rādītāju, mēs cietīsim no 142 00:07:33,941 --> 00:07:36,190 bloķēšanas, un mēs to nevēlamies. 143 00:07:36,190 --> 00:07:38,940 Tad mēs vēlamies aizpildīt lauku, mēs vēlamies inicializēt vērtības 144 00:07:38,940 --> 00:07:41,690 lauku un inicializēt nākamo lauku. 145 00:07:41,690 --> 00:07:45,815 Un tad mēs vēlamies — galu galā, kā norāda funkcijas prototips — mēs 146 00:07:45,815 --> 00:07:49,940 vēlamies atgriezt rādītāju uz sll nodemezglu. 147 00:07:49,940 --> 00:07:51,710 Tātad, kā tas izskatās vizuāli? 148 00:07:51,710 --> 00:07:54,480 Vispirms mēs dinamiski atvēlēsim vietu jaunam sll nodemezglam, tāpēc 149 00:07:54,480 --> 00:07:57,250 mēs mallocējammalloc — tas ir tikko izveidotā mezgla vizuāls 150 00:07:57,250 --> 00:08:00,020 attēlojums. 151 00:08:00,020 --> 00:08:02,446 Un mēs pārbaudām, vai tas nav nullesnulle — šajā gadījumā attēls 152 00:08:02,446 --> 00:08:04,872 netiktu parādīts, ja tas būtu nulle, mums būtu beigusies atmiņa, 153 00:08:04,872 --> 00:08:07,298 tāpēc mēs varam tur doties. 154 00:08:07,298 --> 00:08:08,749 Tātad tagad mēs ejam uz darbību C, inicializējiet mezglu vērtības 155 00:08:08,749 --> 00:08:10,200 lauku. 156 00:08:10,200 --> 00:08:13,450 Pamatojoties uz šo funkciju izsaukumu, ko izmantoju šeit, izskatās, 157 00:08:13,450 --> 00:08:16,700 ka es vēlos nokārtotiet uz 6, tāpēc vērtību laukā likšu 6. 158 00:08:16,700 --> 00:08:18,865 Tagad inicializējiet nākamo lauku. 159 00:08:18,865 --> 00:08:21,232 Nu, ko es tur darīšu, tālāk nekā nav, labipareizi, tas ir vienīgais, 160 00:08:21,232 --> 00:08:23,600 kas sarakstā. 161 00:08:23,600 --> 00:08:27,206 Tātad, kāda ir nākamā lieta sarakstā? 162 00:08:27,206 --> 00:08:29,660 Tam nevajadzētu ne uz ko norādīt, vai ne. 163 00:08:29,660 --> 00:08:32,649 Tur nekā cita nav, tāpēc kāds ir mūsu zināmais jēdziens, kas ir 164 00:08:32,649 --> 00:08:35,638 nekas — norādesrādītāji uz neko? 165 00:08:35,638 --> 00:08:38,598 Varbūt mēs vēlamies tur ievietot nulles rādītāju, un es attēlošu 166 00:08:38,598 --> 00:08:41,559 nulles rādītāju kā tikai sarkanu lodziņu, mēs nevaram iet tālāk. 167 00:08:41,559 --> 00:08:44,756 Kā mēs redzēsim nedaudz vēlāk, galu galā mums būs bultu ķēdes, kas 168 00:08:44,756 --> 00:08:47,953 savienos šos mezglus, taču, noklikšķinot uz sarkanā lodziņa, tas ir 169 00:08:47,953 --> 00:08:51,150 nulle, mēs nevaram iet tālāk, tas ir saraksta beigas. 170 00:08:51,150 --> 00:08:53,960 Un visbeidzot, mēs vienkārši vēlamies atgriezt rādītāju uz šo mezglu. 171 00:08:53,960 --> 00:08:56,665 Tāpēc mēs to nosauksim par jaunu un atgriezīsim jaunu, lai to varētu 172 00:08:56,665 --> 00:08:59,370 izmantot jebkurā funkcijā, kas to izveidoja. 173 00:08:59,370 --> 00:09:02,645 Tā nu mēs esam izveidojuši atsevišķi saistītu saraksta mezglu, un 174 00:09:02,645 --> 00:09:05,920 tagad mums ir saraksts, ar kuru varam strādāt. 175 00:09:05,920 --> 00:09:07,860 Tagad pieņemsim, ka mums jau ir liela ķēde, un mēs vēlamies tajā kaut 176 00:09:07,860 --> 00:09:09,800 ko atrast. 177 00:09:09,800 --> 00:09:12,820 Un mēs vēlamies funkciju, kas atgriezīs patieso vai nepatieso vērtību 178 00:09:12,820 --> 00:09:15,840 atkarībā no tā, vai šajā sarakstā ir kāda vērtība. 179 00:09:15,840 --> 00:09:19,580 Funkcijas prototips vai šīs funkcijas deklarācija varētu izskatīties 180 00:09:19,580 --> 00:09:23,320 šādi - bool find, un tad mēs vēlamies nodot divus argumentus. 181 00:09:23,320 --> 00:09:26,996 Pirmais ir rādītājs uz saistītā saraksta pirmo elementu. 182 00:09:26,996 --> 00:09:29,034 Tas patiesībā ir kaut kas tāds, kam vienmēr vēlēsities sekot līdzi, 183 00:09:29,034 --> 00:09:31,072 un patiesībā tas var būt kaut kas tāds, ko pat ievietojat globālā 184 00:09:31,072 --> 00:09:33,110 mainīgāmainīgajā. 185 00:09:33,110 --> 00:09:36,050 Kad esat izveidojis sarakstu, jūs vienmēr vēlaties sekot līdzi 186 00:09:36,050 --> 00:09:38,990 pirmajam saraksta elementam. 187 00:09:38,990 --> 00:09:41,760 Tādā veidā jūs varat atsaukties uz visiem pārējiem elementiem, 188 00:09:41,760 --> 00:09:44,530 vienkārši sekojot ķēdei, nesaglabājot norādes neskartasneskartus 189 00:09:44,530 --> 00:09:47,300 rādītājus uz katru elementu. 190 00:09:47,300 --> 00:09:49,110 Jums tikai ir jāseko līdzi pirmajam tikai tad, ja tie visi ir 191 00:09:49,110 --> 00:09:50,920 savienoti kopā. 192 00:09:50,920 --> 00:09:53,826 Un tad otrā lieta, ko mēs atkal nododam, ir patvaļīgi daži — 193 00:09:53,826 --> 00:09:56,733 neatkarīgi no tā, kādu datu veidu mēs meklējam, tas, cerams, atrodas 194 00:09:56,733 --> 00:09:59,640 vienā no saraksta mezgliem. 195 00:09:59,640 --> 00:10:00,980 Tātad, kādi ir soļi? 196 00:10:00,980 --> 00:10:03,497 Pirmkārt, mēs izveidojam šķērsvirzienatransversālo rādītāju, kas 197 00:10:03,497 --> 00:10:06,015 norāda uz saraksta galvu. 198 00:10:06,015 --> 00:10:08,494 Kāpēc mēs to darām, mums jau ir rādītājs uz sarakstupie saraksta 199 00:10:08,494 --> 00:10:10,974 galvas, kāpēc mēs to vienkārši nepārvietojam? 200 00:10:10,974 --> 00:10:14,277 Nu, kā es tikko teicu, mums ir ļoti svarīgi vienmēr sekot līdzi 201 00:10:14,277 --> 00:10:17,580 saraksta pirmajam elementam. 202 00:10:17,580 --> 00:10:21,863 Tāpēc labāk ir izveidot tā dublikātu un izmantot to, lai pārvietotos, 203 00:10:21,863 --> 00:10:26,146 lai mēs nekad nejauši neatkāptosneaizvirzītos projām, vai arī mums 204 00:10:26,146 --> 00:10:30,430 vienmēr ir rādītājs, kas atrodas tieši uz saraksta pirmā elementa. 205 00:10:30,430 --> 00:10:33,290 Tāpēc labāk ir izveidot otru, ko izmantojam pārvietošanai. 206 00:10:33,290 --> 00:10:35,180 Pēc tam mēs vienkārši salīdzinām, vai vērtību lauks šajā mezglā ir 207 00:10:35,180 --> 00:10:37,070 tas, ko mēs meklējam, un, ja tā nav, mēs vienkārši pārejam uz nākamo 208 00:10:37,070 --> 00:10:38,960 mezglu. 209 00:10:38,960 --> 00:10:41,743 Un mēs turpinām to darīt atkal un atkal, un vēl, līdz mēs vai nu 210 00:10:41,743 --> 00:10:44,526 atrodam elementu, vai arī nospiežam nulli — esam sasnieguši saraksta 211 00:10:44,526 --> 00:10:47,310 beigas, un tā tur nav. 212 00:10:47,310 --> 00:10:50,300 Cerams, ka tam vajadzētu zvanīt jums atgādināt kā tikai lineārai 213 00:10:50,300 --> 00:10:53,290 meklēšanailineāro meklēšanu. Mēs to tikai atkārtojam atsevišķi 214 00:10:53,290 --> 00:10:56,280 saistītā saraksta struktūrā, nevis izmantojam masīvu. 215 00:10:56,280 --> 00:10:58,210 Tātad, šeit ir atsevišķi saistīta saraksta piemērs. 216 00:10:58,210 --> 00:11:01,270 Šis sastāv no pieciem mezgliem, un mums ir rādītājs uz saraksta 217 00:11:01,270 --> 00:11:04,330 galvu, ko sauc par sarakstu. 218 00:11:04,330 --> 00:11:05,857 Pirmā lieta, ko mēs vēlamies darīt, ir vēlreiz izveidot šo 219 00:11:05,857 --> 00:11:07,385 šķērsošanastransversālo rādītāju. 220 00:11:07,385 --> 00:11:08,572 Tāpēc tagad mums ir divas norādesdivi rādītāji, kas norāda uz vienu 221 00:11:08,572 --> 00:11:09,760 un to pašu. 222 00:11:09,760 --> 00:11:15,025 Tagad ievērojiet arī šeit, man nebija jāatstāj vieta trav. 223 00:11:15,025 --> 00:11:18,092 Es neteicu, ka trav ir vienāds ar malloc kaut koequals malloc 224 00:11:18,092 --> 00:11:21,160 something, katas mezgls jau pastāv, katā vieta atmiņā jau pastāv. 225 00:11:21,160 --> 00:11:24,290 Tāpēc viss, ko es patiesībā daru, ir izveidot citu rādītāju. 226 00:11:24,290 --> 00:11:27,830 Es neizmantoju papildu atstarpivietu, tikai tagad ir divas 227 00:11:27,830 --> 00:11:31,370 norādesdivi rādītāji, kas norāda uz vienu un to pašu. 228 00:11:31,370 --> 00:11:33,710 Tātad, vai 2 ir tas, ko es meklēju? 229 00:11:33,710 --> 00:11:37,220 Nu` nē, tā vietā es pāriešu uz nākamo. 230 00:11:37,220 --> 00:11:41,740 Tātad būtībā es teiktu, trav ir vienāds arequals trav kā nākamo. 231 00:11:41,740 --> 00:11:43,630 Vai es meklēju 3, nē. 232 00:11:43,630 --> 00:11:46,286 Tāpēc es turpinu iet cauri, līdz galu galā nokļūstu līdz 6, ko es 233 00:11:46,286 --> 00:11:48,943 meklēju, pamatojoties uz funkcijas izsaukumu, kas man ir augšpusē, un 234 00:11:48,943 --> 00:11:51,600 es esmu pabeidzis. 235 00:11:51,600 --> 00:11:53,555 Ko darīt, ja elementselementa, kuru meklēju, nav sarakstā, vai tas 236 00:11:53,555 --> 00:11:55,510 joprojām darbosies? 237 00:11:55,510 --> 00:11:57,600 Ņemiet vērā, ka saraksts šeit ir smalkimazliet atšķirīgs, un šī ir 238 00:11:57,600 --> 00:11:59,690 vēl viena lieta, kas ir svarīga saistītajos sarakstos. Jums tie nav 239 00:11:59,690 --> 00:12:01,780 jāsaglabā noteiktā secībā. 240 00:12:01,780 --> 00:12:05,545 Ja vēlaties, varat, taču, iespējams, jau esat pamanījis, ka mēs 241 00:12:05,545 --> 00:12:09,310 nesekojam uz totam, kurāpie kāda skaitļa elementāelementa atrodamies. 242 00:12:09,310 --> 00:12:11,306 Un tas ir viens no darījumiem, kas mums ir ar saistītiem 243 00:12:11,306 --> 00:12:13,303 sarakstasaistīto sarakstu pantupretstatā masīviem, vai mums vairs nav 244 00:12:13,303 --> 00:12:15,300 nejaušas piekļuves. 245 00:12:15,300 --> 00:12:18,355 Mēs nevaram vienkārši pateikt, es gribu pāriet uz 0. elementu vai 6. 246 00:12:18,355 --> 00:12:21,410 elementu savā masīvā, ko es varu darīt masīvā. 247 00:12:21,410 --> 00:12:25,885 Es nevaru teikt, ka vēlos pāriet uz saistītā saraksta 0. vai 6. 248 00:12:25,885 --> 00:12:30,360 elementu, vai 25. elementu, ar tiem nav saistīts rādītājs. 249 00:12:30,360 --> 00:12:33,660 Un tāpēc nav īsti svarīgi, vai mēs saglabājam savu sarakstu kārtībā. 250 00:12:33,660 --> 00:12:36,113 Ja vēlaties, jūs noteikti varat, bet nav iemesla, kāpēc tie ir 251 00:12:36,113 --> 00:12:38,567 jāsaglabā jebkurākaut kādā secībā. 252 00:12:38,567 --> 00:12:40,400 Tātad vēlreiz, mēģināsim atrast 6 šajā sarakstā. 253 00:12:40,400 --> 00:12:44,045 Nu, mēs sākam no sākuma, mēs neatrodam 6, un tad mēs turpinām, 254 00:12:44,045 --> 00:12:47,690 neatrodam 6, līdz galu galā nonākam šeit. 255 00:12:47,690 --> 00:12:52,790 Tāpēc šobrīd trav norāda uz mezglu, kurā ir 8, un seši tur nav. 256 00:12:52,790 --> 00:12:55,115 Tātad nākamais solis būtu pāriet uz nākamo rādītāju, tāpēc sakiet, ka 257 00:12:55,115 --> 00:12:57,440 trav ir vienāds arequals trav nextkā nākamo. 258 00:12:57,440 --> 00:13:00,750 Nu, trav next, ko norāda sarkanais lodziņš, ir nulle. 259 00:13:00,750 --> 00:13:03,970 Tātad vairs nav, kur iet, un tāpēc šobrīd mēs varam secināt, ka esam 260 00:13:03,970 --> 00:13:07,190 sasnieguši saistītā saraksta beigas un 6 tajā nav. 261 00:13:07,190 --> 00:13:10,980 Un šajā gadījumā tas tiktu atgriezts kā nepatiess. 262 00:13:10,980 --> 00:13:14,540 Labi, kā saistītajā sarakstā ievietot jaunu mezglu? 263 00:13:14,540 --> 00:13:17,233 TāpēcTātad mēs esam varējuši izveidot saistītu sarakstu no 264 00:13:17,233 --> 00:13:19,926 nekurienes, taču mēs, iespējams, vēlamies izveidot ķēdi, nevis 265 00:13:19,926 --> 00:13:22,620 izveidot dažādu sarakstu kopumu. 266 00:13:22,620 --> 00:13:25,330 Mēs vēlamies, lai būtu viens saraksts, kurā būtu virkne mezglu, nevis 267 00:13:25,330 --> 00:13:28,040 sarakstu ķekarskopums ar vienu mezglu. 268 00:13:28,040 --> 00:13:29,980 Tāpēc mēs nevaram vienkārši turpināt izmantot iepriekš definēto 269 00:13:29,980 --> 00:13:31,920 funkciju IzveidotCreate function, tagad mēs vēlamies ievietot to 270 00:13:31,920 --> 00:13:33,860 sarakstā to, kas jau pastāv. 271 00:13:33,860 --> 00:13:36,575 Tātad šajā gadījumā mēs nodosim divus argumentus — norādirādītāju uz 272 00:13:36,575 --> 00:13:39,290 šī saistītā saraksta sākumugalvu, kuru mēs vēlamies papildināt. 273 00:13:39,290 --> 00:13:41,756 Atkal, tāpēc ir tik svarīgi, lai mēs vienmēr tam sekotu līdzi, jo 274 00:13:41,756 --> 00:13:44,223 vienīgais veids, kā mums patiešām ir jāatsaucas uz visu sarakstu, ir 275 00:13:44,223 --> 00:13:46,690 tikai ar rādītāju uz pirmo elementu. 276 00:13:46,690 --> 00:13:49,458 Tāpēc mēs vēlamies nodot rādītāju šim pirmajam elementam un jebkurai 277 00:13:49,458 --> 00:13:52,226 vērtībai, ko mēs vēlamies pievienot sarakstam. 278 00:13:52,226 --> 00:13:55,103 Un galu galā šī funkcija atgriezīs rādītāju uz saistītā saraksta 279 00:13:55,103 --> 00:13:57,980 jauno galvu. 280 00:13:57,980 --> 00:13:59,700 Kādas darbības šeit ir ietvertas? 281 00:13:59,700 --> 00:14:02,183 Tāpat kā izveides gadījumā, mums ir dinamiski jāpiešķir vieta jaunam 282 00:14:02,183 --> 00:14:04,666 mezglam un vēlreiz jāpārbauda, vai mums nav beigusies atmiņa, jo mēs 283 00:14:04,666 --> 00:14:07,150 izmantojam mallocmalloc. 284 00:14:07,150 --> 00:14:09,940 Pēc tam mēs vēlamies aizpildīt un ievietot mezglu, tāpēc ievietojiet 285 00:14:09,940 --> 00:14:12,730 mezglā numuruskaitli neatkarīgi no tā, kas ir val. 286 00:14:12,730 --> 00:14:17,310 Mēs vēlamies ievietot mezglu saistītā saraksta sākumā. 287 00:14:17,310 --> 00:14:20,403 Ir iemesls, kāpēc es vēlos to darīt, un, iespējams, ir vērts nedaudz 288 00:14:20,403 --> 00:14:23,496 pauzēt videoklipu un padomāt par to, kāpēc es vēlos ievietot saistītā 289 00:14:23,496 --> 00:14:26,589 saraksta sākumā. 290 00:14:26,589 --> 00:14:29,804 Atkal jau iepriekš minēju, ka nav īsti svarīgi, vai mēs to saglabājam 291 00:14:29,804 --> 00:14:33,020 kādā secībā, tāpēc varbūt tas ir pavediens. 292 00:14:33,020 --> 00:14:35,790 Un jūs redzējāt, kas notiktu, ja mēs to vēlētos, vai tikai pirms 293 00:14:35,790 --> 00:14:38,560 sekundes, kad veicām meklēšanu, jūs varētuvarējāt redzēt, kas varētu 294 00:14:38,560 --> 00:14:41,330 notikt, ja mēs mēģinātu ievietot saraksta beigās. 295 00:14:41,330 --> 00:14:44,750 Jo mums nav rādītāja uz saraksta beigām. 296 00:14:44,750 --> 00:14:47,065 Tāpēc iemesls, kokāpēc es vēlētos ievietot sākumā, ir tāpēc, ka es to 297 00:14:47,065 --> 00:14:49,380 varu izdarīt nekavējoties. 298 00:14:49,380 --> 00:14:52,730 Man sākumā ir rādītājs, un mēs to redzēsim vizuālā veidā pēc sekundes. 299 00:14:52,730 --> 00:14:55,745 Bet, ja es gribu ievietot beigās, man ir jāsāk no sākuma, jāšķērso 300 00:14:55,745 --> 00:14:58,760 līdz galam un tad jāpieliekjāpievieno. 301 00:14:58,760 --> 00:15:01,413 Tātad tas nozīmētu, ka ievietošana saraksta beigās kļūtu par o no n 302 00:15:01,413 --> 00:15:04,066 darbībudarbības, atgriežoties pie mūsu diskusijas par skaitļošanas 303 00:15:04,066 --> 00:15:06,720 sarežģītību. 304 00:15:06,720 --> 00:15:09,367 Tā būtu kļuvusi par o no n operācijasdarbības, kur, sarakstam kļūstot 305 00:15:09,367 --> 00:15:12,014 arvien lielākam, arvien lielākam un lielākam, beigās būs arvien 306 00:15:12,014 --> 00:15:14,661 grūtāk kaut ko pieminētpievienot. 307 00:15:14,661 --> 00:15:16,860 Bet vienmēr ir ļoti viegli kaut ko pielikt sākumā, jūs vienmēr esat 308 00:15:16,860 --> 00:15:19,060 sākumā. 309 00:15:19,060 --> 00:15:21,620 Un mēs to redzēsim vēlreiz. 310 00:15:21,620 --> 00:15:23,980 Kad esam pabeiguši, kad esam ievietojuši jauno mezglu, mēs vēlamies 311 00:15:23,980 --> 00:15:26,340 atgriezt savu rādītāju uz jauno saistītā saraksta galvenigalvu, kas, 312 00:15:26,340 --> 00:15:28,700 tā kā mēs ievietojam sākumā, faktiski būs rādītājs uz mezglu., ko mēs 313 00:15:28,700 --> 00:15:31,060 tikko izveidojām. 314 00:15:31,060 --> 00:15:33,280 Vizualizēsim to, jo es domāju, ka tas palīdzēs. 315 00:15:33,280 --> 00:15:36,712 Tātad, šeit ir mūsu saraksts, tas sastāv no četriem elementiem, 316 00:15:36,712 --> 00:15:40,145 mezgla, kurā ir 15, kas norāda uz mezglu, kurā ir 9, kas norāda uz 317 00:15:40,145 --> 00:15:43,577 mezglu, kurā ir 13, kas norāda uz mezglu, kurā ir 10, kuram ir nulles 318 00:15:43,577 --> 00:15:47,010 rādītājs kā nākamais rādītājs. tasTās ir saraksta beigas. 319 00:15:47,010 --> 00:15:49,865 Tātad mēs vēlamies ievietot jaunu mezglu ar vērtību 12 šī saraksta 320 00:15:49,865 --> 00:15:52,720 sākumā. Ko mums darīt? 321 00:15:52,720 --> 00:15:58,770 Vispirms mēs atvēlam vietu mezglam un pēc tam ievietojam 12. 322 00:15:58,770 --> 00:16:02,211 Tātad tagad mēs esam sasnieguši lēmuma pieņemšanas punktu, vai ne? 323 00:16:02,211 --> 00:16:04,490 Mums ir pāris norādesrādītāju, ko mēs varētu pārvietot, kuru 324 00:16:04,490 --> 00:16:06,770 vajadzētu pārvietot vispirms? 325 00:16:06,770 --> 00:16:08,853 Vai mums vajadzētu likt 12 punktus jaunajamjaunajai saraksta 326 00:16:08,853 --> 00:16:10,936 priekšgalamgalvai vai, atvainojiet, vai 12 punktus likt 327 00:16:10,936 --> 00:16:13,020 vecajamvecajai saraksta vadītājamgalvai? 328 00:16:13,020 --> 00:16:15,319 Vai arī jāsaka, ka saraksts tagad sākas ar 12.? 329 00:16:15,319 --> 00:16:19,870 Tur ir atšķirība, un mēs pēc mirkļa apskatīsim, kas notiek ar abiem. 330 00:16:19,870 --> 00:16:23,573 Bet tas noved pie lieliskas tēmas sānjoslai, proti, viena no 331 00:16:23,573 --> 00:16:27,276 sarežģītākajām lietām saistītajos sarakstos ir sakārtot rādītājus 332 00:16:27,276 --> 00:16:30,980 pareizā secībā. 333 00:16:30,980 --> 00:16:33,515 Ja izvedīsiet lietas no ierindas, varat nejauši kļūt par 334 00:16:33,515 --> 00:16:36,050 bāreņiemiznīcināt pārējo saraksta daļu. 335 00:16:36,050 --> 00:16:37,300 Un šeit ir piemērs tam. 336 00:16:37,300 --> 00:16:40,540 Tātad, pieņemsim, ka mēs tikko esam izveidojuši 12. 337 00:16:40,540 --> 00:16:42,913 Mēs zinām, ka 12 būs jaunaisjaunā saraksta vadītājsgalva, un kāpēc 338 00:16:42,913 --> 00:16:45,286 gan mēs vienkārši nepārvietojamtāpēc varbūt vienkārši pārvietosim 339 00:16:45,286 --> 00:16:47,660 saraksta rādītāju uz turieni. 340 00:16:47,660 --> 00:16:49,070 Labi, tas ir labi. 341 00:16:49,070 --> 00:16:51,560 Tātad, kur tagad ir 12 nākamais punktsrāda? 342 00:16:51,560 --> 00:16:54,405 Es domāju, ka vizuāli mēs varam redzēt, ka tas norādīs uz 15, jo mums 343 00:16:54,405 --> 00:16:57,250 kā cilvēkiem tas ir patiešām acīmredzams. 344 00:16:57,250 --> 00:17:00,300 Kā dators zina? 345 00:17:00,300 --> 00:17:02,720 Mums vairs nav nekā, kas norāda uz 15, vai ne? 346 00:17:02,720 --> 00:17:05,869 Mēs esam zaudējuši jebkādu spēju atsaukties uz 15. 347 00:17:05,869 --> 00:17:08,664 Mēs nevaram teikt, ka jaunā bultiņa ir vienāda ar kaut ko, tur nekā 348 00:17:08,664 --> 00:17:11,460 nav. 349 00:17:11,460 --> 00:17:13,962 Faktiski, šādi rīkojoties, mēs esam atstājuši bāreņuiznīcinājuši 350 00:17:13,962 --> 00:17:16,465 pārējo sarakstu, mēs nejauši esam pārrāvuši ķēdi. 351 00:17:16,465 --> 00:17:18,089 Un mēs noteikti nevēlamies to darīt. 352 00:17:18,089 --> 00:17:20,000 Tāpēc atgriezīsimies un mēģināsim vēlreiz. 353 00:17:20,000 --> 00:17:24,145 Varbūt pareizi ir vispirms iestatīt 12. nākamo rādītāju uz veco 354 00:17:24,145 --> 00:17:28,290 saraksta galvu, pēc tam varam pārvietot sarakstu. 355 00:17:28,290 --> 00:17:30,563 Un patiesībā tā ir pareizā secība, kas mums jāievēro, strādājot ar 356 00:17:30,563 --> 00:17:32,836 atsevišķi saistītu sarakstu. 357 00:17:32,836 --> 00:17:38,098 Mēs vienmēr vēlamies pievienot jauno elementu sarakstam, pirms veicam 358 00:17:38,098 --> 00:17:43,360 tik svarīgu soli, mainot to, kur atrodas saistītā saraksta galva. 359 00:17:43,360 --> 00:17:46,740 Atkal, tā ir tik būtiska lieta, ka mēs nevēlamies to zaudēt. 360 00:17:46,740 --> 00:17:49,390 Tāpēc pirms rādītāja pārvietošanas mēs vēlamies pārliecināties, ka 361 00:17:49,390 --> 00:17:52,040 viss ir savienots kopā. 362 00:17:52,040 --> 00:17:54,835 Un tā būtu pareizā secība, proti, savienot 12 ar sarakstu, pēc tam 363 00:17:54,835 --> 00:17:57,630 teikt, ka saraksts sākas ar 12. 364 00:17:57,630 --> 00:17:59,911 Ja mēs teicām, ka saraksts sākas ar 12, un pēc tam mēģinājām 365 00:17:59,911 --> 00:18:02,193 pievienot sarakstam 12, mēs jau esam redzējuši, kas notiek. 366 00:18:02,193 --> 00:18:04,920 Mēs sarakstu zaudējam kļūdas dēļ. 367 00:18:04,920 --> 00:18:06,740 Labi, vēl viena lieta, par ko runāt. 368 00:18:06,740 --> 00:18:08,245 Ko darīt, ja mēs vēlamies uzreiz atbrīvoties no visa saistītā 369 00:18:08,245 --> 00:18:09,750 saraksta? 370 00:18:09,750 --> 00:18:11,550 Atkal, mēs bloķējamizmantojam visu šo vietu, tāpēc mums tā ir 371 00:18:11,550 --> 00:18:13,351 jāatbrīvo, kad esam pabeiguši. 372 00:18:13,351 --> 00:18:15,350 Tāpēc tagad mēs vēlamies izdzēst visu saistīto sarakstu. 373 00:18:15,350 --> 00:18:16,850 Nu, ko mēs gribam darīt? 374 00:18:16,850 --> 00:18:19,040 Ja esam sasnieguši nulles rādītāju, mēs vēlamies apstāties, pretējā 375 00:18:19,040 --> 00:18:21,230 gadījumā vienkārši izdzēsiet pārējo sarakstu un pēc tam atbrīvojiet 376 00:18:21,230 --> 00:18:23,420 mani. 377 00:18:23,420 --> 00:18:26,155 Izdzēsiet pārējo saraksta daļu un pēc tam atbrīvojiet pašreizējo 378 00:18:26,155 --> 00:18:28,890 mezglu. 379 00:18:28,890 --> 00:18:32,165 Kā tas izklausās, par kādu tehniku mēs iepriekš runājām, vaikā tas 380 00:18:32,165 --> 00:18:35,440 izklausās? 381 00:18:35,440 --> 00:18:39,560 Izdzēsiet visus pārējos, pēc tam atgriezieties un izdzēsiet mani. 382 00:18:39,560 --> 00:18:43,235 Tā ir rekursija, mēs esam padarījuši problēmu mazliet mazāku, mēs 383 00:18:43,235 --> 00:18:46,910 sakām, ka izdzēsiet visus pārējos, tad varat izdzēst mani. 384 00:18:46,910 --> 00:18:50,940 Un tālāk pa ceļuceļam šis mezgls teiks: dzēst visus pārējos. 385 00:18:50,940 --> 00:18:53,125 Bet galu galā mēs nonāksim līdz vietai, kur saraksts ir nulle, un tas 386 00:18:53,125 --> 00:18:55,310 ir mūsu pamata gadījumspamatgadījums. 387 00:18:55,310 --> 00:18:57,010 Apskatīsim to un kā tas varētu darboties. 388 00:18:57,010 --> 00:18:58,995 Tātad, šeit ir mūsu saraksts, tas ir tas pats saraksts, par kuru mēs 389 00:18:58,995 --> 00:19:00,980 tikko runājām, un tur ir norādītas darbības. 390 00:19:00,980 --> 00:19:04,200 Šeit ir daudz teksta, bet cerams, ka vizualizācija palīdzēs. 391 00:19:04,200 --> 00:19:07,220 Mēs esam izdarījuši — un es arī izvilku mūsu steka kadru ilustrāciju 392 00:19:07,220 --> 00:19:10,240 no mūsu video par zvanu skursteņiemizsaukuma stekiem, un cerams, ka 393 00:19:10,240 --> 00:19:13,260 tas viss kopā parādīs notiekošo. 394 00:19:13,260 --> 00:19:14,510 Tātad, šeit ir mūsu pseidokoda kods. 395 00:19:14,510 --> 00:19:17,915 Ja sasniedzam nulles rādītāju, apstājieties, pretējā gadījumā 396 00:19:17,915 --> 00:19:21,320 izdzēsiet pārējo sarakstu un pēc tam atbrīvojiet pašreizējo mezglu. 397 00:19:21,320 --> 00:19:24,865 Tāpēc šobrīd uzskaitietsaraksts — rādītājs, kuru mēs virzām, lai 398 00:19:24,865 --> 00:19:28,410 iznīcinātu, punktusnorāda uz 12. 399 00:19:28,410 --> 00:19:33,340 12 nav nulles rādītājs, tāpēc mēs dzēsīsim pārējo sarakstu. 400 00:19:33,340 --> 00:19:35,450 Kas ir mūsu pārējo iesaistīto personu dzēšana? 401 00:19:35,450 --> 00:19:38,755 Tas nozīmē, ka jāaicinaizsaukumu iznīcināt, sakot, ka 15 ir sākums 402 00:19:38,755 --> 00:19:42,060 pārējam sarakstam, kuru vēlamies iznīcināt. 403 00:19:42,060 --> 00:19:44,770 Un tāpēc aicinājumsizsaukums iznīcināt 12 ir sava veidatāds kā 404 00:19:44,770 --> 00:19:47,480 aizturēts. 405 00:19:47,480 --> 00:19:50,085 Tas tur ir sasalisiesaldēts, gaidot aicinājumu iznīcināt 15, lai 406 00:19:50,085 --> 00:19:52,690 pabeigtu savu darbu. 407 00:19:52,690 --> 00:19:55,570 Nu, 15 nav nulles rādītājs, un tāpēc tas saka: labi, labi, izdzēsiet 408 00:19:55,570 --> 00:19:58,450 pārējo sarakstu. 409 00:19:58,450 --> 00:20:00,471 Pārējā saraksta daļa sākas ar 9, tāpēc mēs vienkārši pagaidīsim, līdz 410 00:20:00,471 --> 00:20:02,492 izdzēsīsit visu šo saturu, un pēc tam atgriezīsimies un izdzēsīsim 411 00:20:02,492 --> 00:20:04,514 mani. 412 00:20:04,514 --> 00:20:06,767 Nu, 9 teiks, nu, es neesmu nulles rādītājs, tāpēc izdzēsiet pārējo 413 00:20:06,767 --> 00:20:09,020 sarakstu no šejienes. 414 00:20:09,020 --> 00:20:11,805 Un tāpēc mēģiniet iznīcināt 13. 415 00:20:11,805 --> 00:20:13,677 13 saka: es neesmu nulles rādītājs, tas pats, tas nokārtonoveļ 416 00:20:13,677 --> 00:20:15,550 atbildību uz nākamo. 417 00:20:15,550 --> 00:20:17,856 10 nav nulles rādītājs, 10 satur nulles rādītāju, bet 10 pats par 418 00:20:17,856 --> 00:20:20,163 sevi šobrīd nav nulles rādītājs, tāpēc tas arī uzņemasneuzņemas 419 00:20:20,163 --> 00:20:22,470 atbildību. 420 00:20:22,470 --> 00:20:24,966 Un tagad uzskaitīt punktussaraksts norāda uz turieni, tas tiešām 421 00:20:24,966 --> 00:20:27,463 norādītu uz dažiem — ja man attēlā būtu vairāk vietas, tas norādītu 422 00:20:27,463 --> 00:20:29,960 uz kādu nejaušu vietu, par kuru mēs nezinām, kas tas ir. 423 00:20:29,960 --> 00:20:32,320 Tomēr tas ir nulles rādītājs, saraksts burtiski tagad ir iestatīts kā 424 00:20:32,320 --> 00:20:34,680 nulles vērtības. 425 00:20:34,680 --> 00:20:36,820 Tas rāda tieši tajā sarkanajā lodziņā. 426 00:20:36,820 --> 00:20:39,960 Mēs sasniedzām nulles rādītāju, tāpēc varam apstāties, un viss. 427 00:20:39,960 --> 00:20:43,488 Un tā, ka purpursarkanais rāmis tagad atrodas steka augšdaļā, tas ir 428 00:20:43,488 --> 00:20:47,017 aktīvais rāmis, taču tas ir pabeigts. 429 00:20:47,017 --> 00:20:48,600 Ja esam sasnieguši nulles rādītāju, apstājieties. 430 00:20:48,600 --> 00:20:51,835 Mēs neko nedarām, mēs nevaram atbrīvot nulles rādītāju, mēs 431 00:20:51,835 --> 00:20:55,070 neizmantojām atstarpivietu, un tas ir darītsizdarīts. 432 00:20:55,070 --> 00:20:57,649 Tātad šis funkciju rāmis tiek iznīcināts, un mēs turpinām darbu — mēs 433 00:20:57,649 --> 00:21:00,228 turpinām no vietas, kur mēs to pārtraucām, ar nākamo augstāko, kas ir 434 00:21:00,228 --> 00:21:02,807 šis tumši zilais rāmis. 435 00:21:02,807 --> 00:21:04,390 Tāpēc mēs turpinām tur, kur pārtraucām. 436 00:21:04,390 --> 00:21:06,195 Mēs jau esam izdzēsuši pārējo sarakstu, tāpēc tagad mēs atbrīvosim 437 00:21:06,195 --> 00:21:08,000 pašreizējos mezglus. 438 00:21:08,000 --> 00:21:10,460 Tātad tagad mēs varam atbrīvot šo mezglu, un tagad esam sasnieguši 439 00:21:10,460 --> 00:21:12,920 funkcijas beigas. 440 00:21:12,920 --> 00:21:14,865 Un tā tas funkciju rāmis tiek iznīcināts, un mēs paņemam pie gaiši 441 00:21:14,865 --> 00:21:16,810 zilāsākam izmantot gaiši zilo. 442 00:21:16,810 --> 00:21:19,975 Tā saka — es jau esmu izdarījis — dzēst pārējo sarakstu, tāpēc 443 00:21:19,975 --> 00:21:23,140 atbrīvojiet pašreizējo mezglu. 444 00:21:23,140 --> 00:21:26,520 Un tagad dzeltenais rāmis ir atkal uz kaudzessteka augšpusē. 445 00:21:26,520 --> 00:21:29,655 Un, kā redzat, mēs tagad iznīcinām sarakstu no labās uz kreiso pusi. 446 00:21:33,710 --> 00:21:37,280 Tomēr, kas būtu noticis, ja mēs būtu rīkojušies nepareizi? 447 00:21:37,280 --> 00:21:39,410 Tāpat kā tad, kad mēģinājām pievienot elementu. 448 00:21:39,410 --> 00:21:41,968 Ja mēs sajaucām ķēdi, ja mēs nesavienojām rādītājus pareizajā secībā, 449 00:21:41,968 --> 00:21:44,526 ja mēs tikko atbrīvojām pirmo elementu, ja mēs vienkārši atbrīvojām 450 00:21:44,526 --> 00:21:47,084 saraksta galvgaligalvu, tagad mums nav iespējas atsaukties uz pārējo 451 00:21:47,084 --> 00:21:49,642 sarakstu. 452 00:21:49,642 --> 00:21:51,761 Un tā mēs visu būtu palikuši bāreņiiznīcinājuši, mums būtu tā sauktā 453 00:21:51,761 --> 00:21:53,880 atmiņas noplūde. 454 00:21:53,880 --> 00:21:56,265 Ja atceraties no mūsu video par dinamisko atmiņas piešķiršanu, tas 455 00:21:56,265 --> 00:21:58,650 nav īpaši labi. 456 00:21:58,650 --> 00:22:01,330 Tātad, kā jau teicu, ir vairākas darbības, kas mums ir jāizmanto, lai 457 00:22:01,330 --> 00:22:04,010 efektīvi strādātu ar saistīto sarakstu. 458 00:22:04,010 --> 00:22:06,537 Un jūs, iespējams, pamanījāt, ka es vienu izlaidu, izdzēšot vienu 459 00:22:06,537 --> 00:22:09,064 elementu no saistītā saraksta. 460 00:22:09,064 --> 00:22:11,242 Iemesls, kāpēc es to darīju, ir tāds, ka patiesībā ir diezgan 461 00:22:11,242 --> 00:22:13,421 sarežģīti domāt par to, kā izdzēst vienu elementu no atsevišķi 462 00:22:13,421 --> 00:22:15,600 saistīta saraksta. 463 00:22:15,600 --> 00:22:19,332 Mums ir jāspēj izlaist kaut ko sarakstā, kas nozīmē, ka mēs nonākam 464 00:22:19,332 --> 00:22:23,065 pie punkta — mēs vēlamies dzēst šo mezglu — bet, lai to 465 00:22:23,065 --> 00:22:26,797 padarītuizdarītu un nezaudētu informāciju, mums tas ir jāsavieno. 466 00:22:26,797 --> 00:22:30,530 mezglsšis mezgls ir jāsavieno šeit, šeit. 467 00:22:30,530 --> 00:22:33,390 Tāpēc es, iespējams, izdarīju to nepareizi no vizuālā viedokļa. 468 00:22:33,390 --> 00:22:36,950 Tātad mēs esam sava saraksta sākumā, mēs turpinām, mēs vēlamies dzēst 469 00:22:36,950 --> 00:22:40,510 šo mezglu. 470 00:22:40,510 --> 00:22:43,440 Ja mēs to vienkārši izdzēsīsim, mēs esam pārrāvuši ķēdi. 471 00:22:43,440 --> 00:22:45,850 Šis mezgls šeit attiecas uz visu pārējo, tas satur ķēdi no šī 472 00:22:45,850 --> 00:22:48,260 brīžašejienes uz priekšu. 473 00:22:48,260 --> 00:22:51,703 Tas, kas mums faktiski jādara, kad esam nonākuši līdz šim punktam, ir 474 00:22:51,703 --> 00:22:55,146 jāatkāpjas par vienu un jāsavieno šis mezgls ar šo mezglu, lai mēs 475 00:22:55,146 --> 00:22:58,590 varētu izdzēst vidū esošo. 476 00:22:58,590 --> 00:23:00,355 Taču atsevišķi saistītie saraksti nedod mums iespēju atgriezties 477 00:23:00,355 --> 00:23:02,120 atpakaļ. 478 00:23:02,120 --> 00:23:05,116 Tāpēc mums ir vai nu jāsaglabā divas norādesdivi rādītāji un 479 00:23:05,116 --> 00:23:08,113 jāpārvieto tāstie kā nobīdes vienu aiz otrasotra, vai arī jānokļūst 480 00:23:08,113 --> 00:23:11,110 punktā un pēc tam jānosūta cits rādītājs. 481 00:23:11,110 --> 00:23:13,150 Un, kā redzat, tas var kļūt nedaudz netīrsmazliet sajukt. 482 00:23:13,150 --> 00:23:15,480 Par laimi, mums ir cits veids, kā to atrisināt, runājot par divkārši 483 00:23:15,480 --> 00:23:17,810 saistītiem sarakstiem. 484 00:23:17,810 --> 00:23:20,720 Es esmu Dags Loids, šis ir CS50.