[Powered by Google Translate] [Həftə 6, davamı]
[David J. Malan] [Harvard Universiteti]
[Bu CS50 edir.] [CS50.TV]
Bu CS50 və bu həftə 6 sonu.
Belə CS50x ki, edX təşəbbüsü cəlb Harvard ilk kursları biri
həqiqətən bu ötən Bazar ertəsi oldu.
İnternet haqqında nə digər bir fikir almaq istəyirsinizsə
İndi birlikdə aşağıdakı, siz x.cs50.net giderim bilər.
Yəni, edx.org müvafiq yerə yönlendirir
bu və MİT və Berkeley digər kursları indi yaşadıqları idi.
Siz bir haqq-hesab üçün qeydiyyatdan lazımdır, siz maddi əsasən eyni olduğunu görəcəksiniz
Əgər biz hər şeyi hazır olaraq, təxirə bir neçə həftə olsa da, bu dövr idi. etdiyiniz kimi
Amma nə CS50x tələbələr indi görəcəksiniz olduqca bu kimi interfeys.
Bu, misal üçün, problem set 0 üçün gözden geçirmek aparıcı Zamyla edir.
Edx.org giriş sonra, CS50x tələbə şeyi növ görür
Bir kurs görmək gözləmək olardı: Bazar ertəsi üçün mühazirə,
Çərşənbə, müxtəlif şort, problem dəstləri, bu walkthroughs, PDF üçün mühazirə.
Bundan əlavə, burada bax, maşın tərcümə
, İspan, İtalyan, Yapon, Çin İngilis dili protokolları və
əlbəttə təkmil olacaq ki, digər dilləri və bütün dəstə
biz API deyilən bir şey istifadə program onları roll kimi
Google və ya proqram proqramlaşdırma interface,
ki, bu digər dillərdə İngilis çevirmək imkan verir.
Lakin bəzi yüz-plus könüllü gözəl ruh sayəsində,
xahiş məşğul olmaq təklif edən İnternet təsadüfi insanlar
Bu layihə, biz tədricən bu tərcümə keyfiyyətinin yaxşılaşdırılması olacaq
insanlar bizim kompüter etdiyiniz səhvləri düzəltmək malik.
>> Biz bir neçə tələbə biz ilkin gözləniləndən daha Bazar ertəsi göstərilir ki, həyata Belə ki çevrilir.
Əslində, indi CS50x evdə birlikdə aşağıdakı 100,000 nəfər var.
Belə ki, kompüter bu kurs edilməsi bu ilk sinif bütün hissəsidir həyata
ümumiyyətlə, təhsil, daha geniş, əlverişli.
Və reallıq, bu kütləvi online kurslar bəzi, indi
onlar bütün biz burada işlər görünür kimi, bu çox yüksək nömrələri ilə başlanır.
Amma məqsədi, nəticə etibarilə, CS50x üçün mümkün finiş xəttinə kimi bir çox insanlar üçün həqiqətən.
Dizayn, CS50x bu ötən Bazar ertəsi təklif edir
başqa yerdə məktəb öhdəlikləri insanlar kim ki, 15 aprel 2013 vasitəsilə bütün yolu,
iş, ailə, digər münaqişələr və kimi, bir az daha çox rahatlıq var
Bu kurs daxil dalış olan, bu, o demək kifayətdir
olduqca ambitiously edilir adi dövr ərzində yalnız üç ay ərzində yalnız.
Lakin bu tələbələr, eyni məzmunlu görüntülerken, eyni problem dəstləri həll olunacaq
Eyni şort və kimi çıxışı olan.
Beləliklə, biz bu birlikdə bütün həqiqətən bilirik.
Və CS50x sonunda məqsədlərindən biri kimi bir çox insanlar üçün deyil
finiş xəttinə və onlara kompüter elminin bu newfound anlayış vermək
və proqramlaşdırma, həm də onlara bu paylaşılan təcrübəsi var.
Kampus 50 müəyyən xüsusiyyətlərindən biri, biz ümid edirik ki,
, bəzən daha yaxşı və ya pis, kommunal təcrübə bu cür olmuşdur
amma bu insanlar üçün sol və sağ açmaq üçün olan
və ofis saat və Hackathon və ədalətli.
Bu, online xalqları ilə adam da bunu bir az çətindir
lakin CS50x, ilk CS50 Expo ilə aprel ayında yekunlaşacaq
ədalətli bizim fikir bir online uyğunlaşma olacaq
, 2 dəqiqəlik video - Ü tələbələr bu minlərlə bütün 1 təqdim etməyə dəvət olunacaq
onlara öz yekun layihə və ya video bir screencast salam waving ya
və onların layihə söhbət və demoing,
çox öz sələfləri kimi, ədalətli kampus burada işlər
semestr sonuna, ümid qlobal sərgi var ki
bu CS50x tələbələr yekun layihələrin çox kimi olan kampus burada bu Dekabr gözləyir.
Gələcək ay ki, daha çox.
>> 100,000 tələbələri ilə olsa da, bir neçə CA'lar ehtiyac gəlir.
Uşaqlar burada cığır parlaq və CS50 alaraq nəzərə alaraq
bir neçə həftə edX üzrə insanlar bu material azad əvvəl,
Biz bu təşəbbüsü mümkün kimi öz tələbələrin çox cəlb etmək istərdim həyata,
dövr habelə bu qış zamanı və bu gələn bahar də.
Beləliklə, siz CS50x cəlb almaq istəyirsinizsə,
xüsusilə CS50x müzakirə CS50 müzakirə və edX versiyası üzrə qoşulma
bir çox kampus üzrə istifadə edilmiş, online bulletin board,
ki, URL rəhbəri edin, bizi kim bildirin
biz eyni bir tələbə və heyəti komanda və fakültə yaratmaq sevindim, çünki
kampus olan sadəcə yanaşı oynayan və kömək edir.
Və onlara tanış olan bir sual gördükdə,
Siz, Internet bəzi ölkədə orada haradasa bir səhv hesabat, tələbə eşitmək
və siz də həmin məsələ ki, üzük bir zəng çünki
bir müddət əvvəl sizin d zalında, inşallah sonra sizə zəng və öz təcrübə mübadiləsi edə bilərsiniz.
Beləliklə, siz istəyirsinizsə iştirak edin.
>> Harvard Kompüter elm kursları, bir ənənə bir az var
Siz qürurla wear bilər ki, bəzi geyim, bəzi geyim, olan, onların arasında CS50,
semestr sonunda, siz CS50 başa olduqca qürurla dedi
və CS50 və kimi etdi və biz həmişə tələbələri cəlb etmək üçün cəhd edin
Bu prosesin mümkün qədər, biz dəvət vasitəsi ilə,
dövr bu dəfə ətrafında, tələbələr dizayn təqdim
istifadə etmək istədiyiniz seçimi Photoshop istifadə edərək, və ya hər hansı bir alət
siz T-shirt və sweatshirts üçün dizayn təqdim etmək, dizayner danışırsınızsa
və itlər üçün çətir və az bandanas biz indi və s.
Və hər şey sonra deyil - qalibləri hər il sonra nümayiş olunur
store.cs50.net da kurs saytında.
Hər şey orada dəyəri satılır, amma saytında yalnız özü uzanır edir
və insanlar kimi rəng və dizayn seçmək üçün imkan verir.
Mən yalnız ötən il dizayn bəzi bölüşmək istədiyiniz fikir
bir illik ənənə olan, burada bu bir başqa veb olmuşdur.
"Mən Faultn Seg alıram Hər gün", keçən il təqdim biri
olan məzunlar üçün hələ də mövcuddur.
Bu bir idi "CS50, 1989 yaranma tarixi."
Bizim Bowdens biri Rob, keçən il çox populyar idi.
"Komanda Bowden" anadan olub, bu dizayn üst satıcılar arasında təqdim edilmişdir.
Burada bu idi. Bir çox insanlar satış logs görə "Bowden Fever" idi.
Ki, indi İnternet var, sizin dizayn ola bilər bilirik.
Növbəti problem bu barədə daha ətraflı gəlmək edir.
>> Daha bir aracı: İndi inşallah bir ifşa idi və etdik
gdb bəzi praktiki təcrübə,
ki, əlbəttə, ayıklama və siz manipulyasiya imkan verir
kifayət qədər aşağı səviyyədə proqram, nə cür şeylər edir?
Gdb nə imkan vermir?
Evet? Mənə bir şey verin. [Tələbə cavab anlaşılmaz]
Yaxşı. Funksiyası daxil Addım, belə ki, yalnız run yazın yoxdur
və standart çıxış şeyi çap bütövlükdə vasitəsilə proqram zərbə var.
Əksinə, ya növbəti yazaraq, xətti ilə xətt vasitəsilə addım bilər
xətti və ya yazdığı bir qayda olaraq, bir funksiyası daxil dalış addım xətti ilə line getmək.
Gdb siz nə imkan vermir? Evet? [Tələbə cavab anlaşılmaz]
Dəyişənlərin yazdırın. Siz proqram daxilində bir az introspection etmək istəyirəm əgər
bütün yer üzərində printf hesabatları yazılı müraciət etmədən,
yalnız bir dəyişən çap və ya bir dəyişən bilərsiniz.
Siz gdb kimi ayıklama ilə başqa nə edə bilər?
[Tələbə cavab anlaşılmaz]
Exactly. Siz breakpoints bilərsiniz, siz fasilə icra deyə bilərsiniz
əsas funksiyası və ya foo funksiyası.
Siz line 123 at break icrası demək olar.
Və breakpoints həqiqətən güclü texnika var
Çünki harada problem ümumi mənada əgər
Yəqin ki, siz proqramın tam vasitəsilə gücləndirməklə vaxt sərf yoxdur olunur.
Siz mahiyyətcə orada jump və sonra yazmağa başlaya bilərsiniz -
addım və ya növbəti və ya analoji ilə vasitəsilə gücləndirməklə.
Amma gdb kimi bir şey tutmaq, bu insan, sizə kömək edir ki,
Sizin problemləri tapmaq ve hataları tapa bilərsiniz.
Bu mütləq sizin üçün çox tapmaq deyil.
>> Belə ki, biz qısa bir command line vasitədir ki, digər gün style50 təqdim
bir az daha cleanly siz artıq kodu stylize çalışır, insan, görülən bilər var.
Amma ki, bu da həqiqətən yalnız estetik bir şeydir.
Istifadə etmək üçün bir az daha gizli ki Valgrind adlı digər alət var həyata Amma çevrilir.
Onun çıxışı ilk baxışda ermənilər tərəfindən xüsusi amansızlıqla sirli edir.
Amma xüsusilə indi müddəti hissəsi olduğunu, gözəl faydalı
harada malloc və dinamik yaddaş ayrılması istifadə başlayan edirik.
Things tez həqiqətən, həqiqətən, yanlış getmək bilər.
Çünki sizin yaddaş azad unutmaq, və ya bəzi NULL pointer dereference əgər,
və ya bir zibil göstərici dereference, adətən nəticələri olan simptom nədir?
Günah Seg. Və kilobayttan ya megabayt bəzi sayının bu əsas fayl almaq
o düşdü ki, sizin proqramın yaddaş dövlət təmsil
ancaq proqram nəhayət, seqmentləşdirmə günah çatışmazlıqlar seg
bir şey pis demək olar ki, həmişə bağlı baş deməkdir
Əgər haradasa ki bir yaddaş bağlı səhv.
Belə Valgrind bu kimi şeylər tapmaq kömək edir.
Siz proqram tərtib etdik sonra, gdb kimi, çalışan bir aracıdır
lakin birbaşa proqram run deyil, siz Valgrind run
və siz gdb ilə kimi, bu proqram keçir.
İndi, istifadə, ən yaxşı cür çıxış əldə etmək
, belə ki, orada ekran üstün siz Valgrind-v bir az uzun görürsünüz olunur.
Bir Linux kompüter proqramları istifadə etdiyiniz zaman "v" demək olar ki, hamı verbose deməkdir.
Belə ki, siz default güc artıq data tüpürmək deməkdir.
"- = Tam sızması kontrol." Bu, bütün mümkün yaddaş sızıntıları üçün çek deyib
mən qəbul edə bilər ki, səhvlər. Bu, çox, Linux proqramları ilə ortaq bir paradiqma edir.
Bir command line arqument varsa Ümumiyyətlə, ki, bir "keçid" var
ki, proqram davranışı dəyişmək üçün nəzərdə, bu bir hərf var oldu
bu-v, lakin işə ki, əgər, yalnız proqramçı dizayn,
, command line arqumenti ilə sözləri tam bir söz və ya seriyası başlayır edilir -.
Bu yalnız insan konvensiyalar, lakin getdikcə onları görəcəksiniz.
Və sonra, nəhayət, "a.out" bu misal proqram üçün ixtiyari adı.
Burada bəzi nümayəndəsi çıxış edir.
>> Ki, demək bilər nə baxmaq əvvəl, mənə burada bir kod parçası üzərində gedək.
Və tezliklə mənə yol bu həyata hərəkət imkan
və in burada bu qısa nümunəsi olan memory.c, nəzər salaq.
Belə ki, bu proqram mənə funksiyaları və suallar zoom imkan verir.
Biz bir funksiyası çağırır əsas funksiyası, f var
və sonra nə f biraz texniki ingilis, nə davam edir?
F nə davam edir?
Necə haqqında I line 20 ilə başlar və ulduzun yeri etməz,
amma yalnız son məruzə ilə burada ardıcıl olacaq.
Bizim üçün line 20 nə var? Sol tərəfində. Biz daha da qırmaq lazımdır.
Int * x ki: nə edir?
Okay. Bu göstərici elan və indi nin daha texniki olsun var.
Bir göstərici bəyan çox konkret nə deməkdir? Başqası?
Evet? [Tələbə cavab anlaşılmaz] Çox uzaq.
Beləliklə, siz bərabər Qeydiyyat sağ tərəfinə oxu edirik.
Yalnız int * x üzrə yalnız sol-nin diqqət edək.
Bu göstərici "bəyan", ancaq indi edək ki, definition dərin dalış.
Ki, konkret, texniki nə deməkdir? Evet?
[Tələbə cavab anlaşılmaz]
Okay. Bu yaddaş bir ünvan saxlamaq hazırlanması oldu.
Yaxşı. Və gələcək bu bir addım olsun bu 32 bit ki, dəyişən, x, elan edir.
Mən çünki 32 bit olduğunu bilirik -
Bu halda bir göstərici deyil, çünki bu, bir int var, çünki deyil.
Bir int ilə eyni, ki, təsadüf
ancaq ulduz var ki, bu göstərici var deməkdir
və cihaz, bir çox kompüter kimi deyil, bütün göstəricilərinə 32 bit var.
Son Macs, son PC kimi daha müasir avadanlıq, siz, 64-bit göstəricilərinə ola bilər
ancaq cihaz, bu şeylər 32 bit var.
Beləliklə, biz ki standartlaşdırmaq lazımdır. Daha konkret, hekayə aşağıdakı kimi gedir:
Biz bir pointer "bəyan" nə deməkdir?
Biz yaddaş ünvan saxlamaq üçün hazırlamaq.
Ki, nə deməkdir?
Biz 32 bit qədər edir ki, dəyişən adlandırılan x yaratmaq
ki, tezliklə tam üçün ünvan saxlamaq olacaq.
Və yəqin ki, biz əldə edə bilərsiniz kimi haqqında kimi dəqiq deyil.
Bu dünya sadələşdirmək və yalnız x adlı göstərici bəyan demək irəliləyir gözəl var.
Bir göstərici elan, lakin həyata və nə həqiqətən neler anlamaq
hətta yalnız bir neçə simvol.
>> İndi, bu bir daha ifadə edir, hətta, demək olar ki, bir az daha asandır.
Beləliklə, bu artıq qeyd edir ki, nə edir: "malloc (10 * sizeof (int));" Evet?
[Tələbə cavab anlaşılmaz]
Yaxşı. Mən orada onu edəcəyik. Bu on integers üçün yaddaş yığın ayrılması oldu.
İndi in qədər dərin dalış olsun on integers üçün yaddaş yığın ayrılması oldu.
Malloc nə qayıdır?
Daha konkret ki yığın ünvanı, və ya ki, yığın ilk byte və ünvanı.
Mən necə deyiləm, proqramçı bilmək yerləşir yaddaş bitir ki, yığın?
Mən bunu bitişik ki, bilirik. Malloc, definition edərək, yaddaş bitişik yığın verəcək.
Bu No boşluqların. Siz ki, yığın hər byte etmək imkanı
geri geri geri, lakin yaddaş bu yığın sonunda olduğu necə bilirik?
Siz malloc istifadə zaman? [Tələbə cavab anlaşılmaz] Yaxşı.
Siz deyil. Siz yadda var.
Mən dəyəri 10 istifadə yadda var və mən hətta burada etmişik görünmür.
Amma onus mənə tamamilə. Biz strings üçün az güvenen olmaq etdiyiniz Strlen,
çünki \ 0 malik olan bu Konvensiya yalnız
və ya simli sonunda bu xüsusi nul xarakteri, NUL.
Bu yaddaş yalnız ixtiyari chunks keçirilən deyil.
Bu qədər var. Line 20 Beləliklə, sonra yaddaş yığın ayırır
ki, on integers saxlaya bilərsiniz, və bu ilk byte üçün ünvan saxlayan
dəyişən adlı x yaddaş ki, yığın edir.
Bir göstərici olan dolayı. Line 21 Beləliklə, təəssüf ki, bir səhv idi.
Lakin ilk, o nə edir? Bu, yer 10, dizine 0 mağaza deyən oldu
x dəyəri 0 adlı yaddaş yığın edir.
>> Belə şeylər bir neçə gedir bilərsiniz.
X bir göstərici olsa da, bir neçə həftə əvvəl geri
siz hələ də array-stil kvadrat mötərizə notation istifadə edə bilərsiniz.
Əslində çox sirli görünüşlü göstərici hesab üçün qısa tərəfdən notation çünki.
biz bu kimi bir şey olardı: ünvan x götür, artıq 10 ləkələr hərəkət
o yerdə saxlanılır nə ünvan üçün orada gedin.
Amma səmimi, bu oxumaq və rahat almaq üçün yalnız dəhşətli deyil.
Belə ki, dünya adətən bu qədər çox insan dostu oxumaq yalnız çünki kvadrat mötərizə istifadə edir.
Amma nə həqiqətən başlıq altında gedən var;
x bir ünvan deyil, bir sıra, hər se edir.
Belə ki, bu x-ci yeri 10 0 saxlanılması edilir.
Nə üçün bu pis? Evet?
[Tələbə cavab anlaşılmaz] Exactly.
Biz yalnız on ints ayrılmış, lakin C proqramlaşdırma zaman 0-dan saymaq
belə ki, 0 1 2 3 4 5 6 7 8 9 deyil, 10 girmə imkanı vardır.
Buna görə ya proqram seg günah edir və ya deyil.
Amma biz həqiqətən bilmirəm, bu bir nondeterministic davranış sortudur.
Bu, həqiqətən biz xoşbəxt almaq asılıdır.
Mən ki, əlavə byte istifadə əgər əməliyyat sistemi ağla deyil çıxır ki, varsa,
o mənə verilmir baxmayaraq, mənim proqram qəza bilər.
Bu, xammal var o arabası var, lakin bu simptom görmək bilər
və ya yalnız bir dəfə isə onu görə bilərsiniz.
Lakin reallıq səhv var, əslində, olmasıdır.
Siz doğru istəyirəm ki, bir proqram yazdıq, əgər o, həqiqətən problem var
insanların hər dəfə bir müddət çöküyor ki, istifadə etdiyiniz proqram satılan etdik ki,
çünki, əlbəttə, bu yaxşı deyil. Əslində, bir Android telefon və ya iPhone varsa
və siz, bu gün apps download Əgər yaşadığınız halda app yalnız çıxın
o yox qəflətən ki, demək olar ki, həmişə bir yaddaş bağlı problem var
proqramçı bir pointer qıfıllar və dereferenced vasitəsi
o yoxdur, və iOS və ya Android nəticəsində yalnız tamamilə proqram öldürmək ki,
çox risk müəyyən davranış və ya təhlükəsizlik kompromis bir növ çox.
>> Bu bir başqa bu proqram başqa bir səhv var.
Bu proqram nə qədər berbat var?
Mən təbliğ sonra nə tətbiq deyil etdik. Evet?
[Tələbə cavab anlaşılmaz] Yaxşı.
Mən yaddaş azad deyil. Belə ki, indi thumb qayda
siz malloc zəng zaman siz həyata zaman, o yaddaş istifadə edərək, pulsuz zəng olmalıdır olmalıdır.
İndi mən bu yaddaş azad istəyirsiniz?
Yəqin ki, bu ilk düzgün idi fərz, mən burada bunu etmək istəyirəm.
Mən, məsələn, burada aşağı edə bilmirdik. Niyə?
Məhz həyata çərçivəsində. Belə ki, göstəricilər haqqında söhbət edirik, baxmayaraq
bu həftə 2 və ya x yalnız elan edildiyi qıvrım aşırma daxilində daxilində olduğu 3 məsələdir.
Belə ki, siz mütləq orada azad edə bilməz. Bu pulsuz Mənim yalnız şans təxminən line 21 sonra.
Bu kifayət qədər sadə proqram, siz cür fikrinizi bükülmüş bir dəfə olduqca asan idi
səhvləri olduğu nə ətrafında proqram etdiklərini edir.
Və ilk onu görmədi belə, ümid edirəm ki, indi bir az aydın deyil
bu səhvlər olduqca asanlıqla həll və asanlıqla qəbul edir.
Amma bir proqram 12-dən çox xətləri uzun zaman, o, 100 xətləri uzun, 50 xətləri uzun
məntiqi vasitəsilə düşüncə, xətti ilə kodu xətti ilə gəzinti,
daim, hata tapmaq, mümkün deyil, bunu xüsusilə əyləncə deyil
və bunu da çətindir, və Valgrind kimi bir alət var edirdi.
Mənə irəli getmək və bunu edək: mənim terminal pəncərə açmaq qoy,
və yaddaş gözəl görünür, çünki mənə yalnız yaddaş run deyil bildirin.
Mən xoşbəxt alıram. Serialın sonunda əlavə byte gedən
çox problematik görünür deyil.
Lakin mə deməkdir ki, ağlı başında olma çeki, etmək, yenə mənə bildirin
Bu həqiqətən doğru olub olmadığını.
>> Belə valgrind-v nə edək - = tam sızması kontrol
və bu halda proqramın adını yaddaş deyil, a.out edir.
Mənə irəli getmək və bunu bildirin. Daxil Hit.
Allah Əziz. Bu çıxış, bu mən əvvəllər üçün alluded edir.
Lakin, burada ağılsızlıq bütün vasitəsilə oxumaq öyrənmək əgər,
Bu ən maraqlı deyil ki, yalnız diaqnostik çıxış edir.
Sizin göz həqiqətən axtarır istəyir səhv və ya etibarsız hər hansı qeyd edir.
Problemlər göstərir ki, söz.
Və həqiqətən, aşağı burada yanlış gedir nə edək.
Mən bir növ bir xülasə vardır "exit-da istifadə:. 1 blok 40 bayt"
Mən hələ həqiqətən bir blok nə əmin deyiləm, lakin 40 bayt
ki, gələn yerdə mən anlamaq bilər kimi həqiqətən hiss edir.
40 bytes. Niyə çıxış istifadə 40 bytes var?
Və daha konkret desək, biz burada aşağı diyirləyin əgər,
mən niyə mütləq 40 bytes itirmişdir? Evet?
[Tələbə cavab anlaşılmaz] mükəmməldir. Bəli, dəqiq.
Var, on integers idi və o hər 4 və ya 32 bit ölçüsü
siz təklif kimi, mən pulsuz adlı yoxdur, çünki mən dəqiq 40 bytes kaybettim.
Yəni, bir səhv var, indi daha az aşağı baxaq və bu yanında görmək
"Etibarsız ölçüsü 4 yazın." İndi bu nə deməkdir?
Bu ünvan, yəqin, nə baza notation ifadə edir?
Bu hexadecimal və hər hansı bir zaman siz 0x ilə başlayan bir sıra bax
ki, biz geri suallar, hesab edirəm ki, pset 0 bölməsində yol idi ki, hexadecimal deməkdir
olan ikili üçün hex üçün decimal konvertasiya və s, bir son hazırlıq həyata etmək yalnız idi.
Hexadecimal, yalnız insan konvensiyası ilə, adətən göstəricilərinə təmsil etmək üçün istifadə olunur
və ya ümumiyyətlə, ünvanlanır. Bu, yalnız bir konvensiya var
oxumaq üçün bir az daha asandır, çünki decimal kimi bir şey bir az daha yığcam var
ən insanlar istifadə üçün və ikili əhəmiyyətsizdir.
Belə ki, indi bu nə deməkdir? Yalnış yazmaq var kimi Bəli, görünür,
memory.c xətti 21 ölçülü 4.
Belə in line 21 geri bildirin, və həqiqətən, burada yalnış yazmaq deyil.
Belə Valgrind, tamamilə mənim əl keçirilməsi və nə fix mənə demək niyyətində deyil
lakin mən yalnış yazmaq edirəm ki, aşkar edilir.
Mən olmamalıdır 4 bayt toxunan deyiləm, və yəqin ki, çünki
Siz qeyd kimi, mən əvəzinə [9] və [10] edirəm maksimum
ya [0] və ya arasında bir şey.
Valgrind ilə, indi bir proqram yazıyoruz hər zaman həyata
göstəricilərinə istifadə edir və yaddaş istifadə edir və malloc xüsusilə ki,
mütləq bu uzun çalışan vərdiş halına almaq
lakin çox asanlıqla Valgrind əmri kopyalanamaz və yapışdırılır
orada bəzi səhvlər var görmek üçün.
Və, siz çıxış görmək hər zaman böyük olacaq
ancaq vizual bütün çıxış vasitəsilə analiz və görmək görmek səhvlər qeyd
ya xəbərdarlıq və ya etibarsız və ya itirdi.
Siz kimi səs haradasa qıfıllar hər hansı bir söz.
Sizin Toolbar yeni bir alət var ki, bilirik.
>> İndi Bazar ertəsi, biz insanlar bütün dəstə idi bura qədər gəlib
və əlaqəli siyahı anlayışı əks etdirir.
Və biz hansı problemin həlli kimi bağlı siyahı təqdim?
Evet? [Tələbə cavab anlaşılmaz] Yaxşı.
Diziler yaddaş onlara əlavə ola bilməz.
Siz ölçüsü 10 bir sıra ki, siz bütün ayrılması edin.
Siz əvvəlcə malloc adlı əgər Siz realloc kimi bir funksiyası zəng edə bilərsiniz
kosmik bunun sonuna olduqda və bu sıra inkişaf üçün cəhd edə bilərsiniz
Başqa heç bir istifadə edir və orada deyil, bu, yalnız başqa bir yerdə bir daha yığın tapmaq olacaq.
Lakin o, yeni array o bayt bütün surəti olacaq.
Bu, çox düzgün həll kimi səslənir.
Niyə bu çirkin deyil?
Mən bu işləri demək, insanlar bu problemi həll etmişik.
Niyə biz bağlı siyahıları ilə bazar ertəsi onu həll etmək lazım idi? Evet?
[Tələbə cavab anlaşılmaz] Bu uzun müddət bilər.
Əslində, malloc ya realloc və ya başqa biri olan calloc, zəng etdiyiniz istənilən vaxt,
hər zaman, proqram, əməliyyat sistemi üçün gedir,
proqramı yavaşlatmaq edirlər.
Siz loops şeyi bu cür edirik, əgər, həqiqətən, hər şeyi yavaşladaraq edirik.
Siz, "salam dünya" tipli proqramların sadə, bu qeyd etmək fikrində deyilik
lakin çox böyük proqramların, yaddaş üçün təkrar əməliyyat sistemi tələb
və ya təkrar geri verilməsi yaxşı bir şey olmayacaq çalışır.
Plus, yalnız intellektual növ - bu zaman tam tullantılar var.
Yeni array daxil hər şey çıxarmaq daha çox yaddaş ayrılması Niyə, risk,
Siz, həqiqətən, ehtiyac kimi yalnız çox yaddaş ayırmağa imkan verir ki, bir alternativ varsa?
Belə ki, burada müsbət və minuses var.
Bu müsbət biri indi dinamizm var.
Yaddaş chunks sərbəst olduğu əhəmiyyətli deyil,
Mən yalnız göstəricilər vasitəsilə yaratmaq bu çörək qırıntıları sıralayabilirsiniz
birlikdə mənim bütün bağlı siyahı simli üçün.
Amma ən azı bir qiymət ödəyirlər.
>> Mən bağlı siyahıları əldə imtina etmək lazımdır?
Evet? [Tələbə cavab anlaşılmaz] Yaxşı.
Daha çox yaddaş lazımdır. İndi, bu göstəricilər üçün yer lazımdır
və bu super sadə bağlı siyahı halında
yalnız 4 bayt olan integers saxlamaq üçün çalışır ki, deyirdik saxlamaq
yaxşı bir göstərici 4 bayt, belə ki, indi sözün iki dəfə etdik
yaddaş məbləği yalnız bu siyahıda saxlamaq lazımdır.
Ancaq yenə də, bu kompüter sabit tradeoff edir
zaman və məkan və inkişafı, səy və digər resurslar arasında.
Bir bağlı siyahısını istifadə edərək, bir İşin mənfi tərəfi odur nədir? Evet?
[Tələbə cavab anlaşılmaz]
Yaxşı. Daxil olmaq kimi asan deyil. Biz leverage artıq ola bilər
kimi həftə 0 prinsipləri bölmək və qalib.
Və daha çox xüsusi, ikili axtarış. Çünki baxmayaraq biz insanlar
Bu siyahıda ortasında olduğu təxminən bilərsiniz,
kompüter yalnız bu bağlı siyahı ilk deyilən ünvan başlayır bilir.
Və 0x123 və ya kimi bir şey var.
Və proqram yalnız yol ortasında element tapa bilərsiniz
əslində bütün siyahısını axtarış edir.
Və hətta sonra, bu sözün bütün siyahısını axtarış çünki
hətta bir dəfə siz göstəricilər aşağıdakı orta element çatmaq
siz, proqram, potensial, bu siyahı necə uzun heç bir fikrim yoxdur
siz sonunda edib, siz necə program bilmirəm qədər
Bir bağlı siyahı sonunda olduğunu?
Xüsusi NULL pointer, belə ki, yenə bir konvensiya var.
Bu göstərici istifadə daha çox, biz mütləq bəzi zibil dəyəri istəmirəm
haradasa mərhələ off işarə edərək, biz, bu tərəfdən olacaq NULL aşağı istəyirəm,
o başa yerləşir biz bilirik ki, biz bu data tərkibində bu dayanacaq var ki.
>> Biz bu manipulyasiya etmək istəyirsinizsə?
Biz bu vizual çox idi, və insanlar ilə
lakin nə biz durub etmək istəyirsinizsə?
Belə ki, orijinal siyahı 9, 17, 20, 22, 29, 34 idi.
Biz sonra sayı 55, bunun üçün bir node üçün malloc yer istədiyini əgər
və sonra biz bazar ertəsi günü etdiyiniz kimi siyahısına 55 əlavə etmək istəyirsiniz?
Biz bu etməliyəm? Yaxşı, Anita gəldi və o, mahiyyətcə siyahısı getdi.
O, növbəti, növbəti, növbəti, növbəti, növbəti sonra ilk element başladı.
Nəhayət sol bütün yol aşağı edib
və oh həyata, bu NULL edir. Belə ki, nə göstərici manipulyasiya edilməsi lazım?
Sonunda olan şəxs, sayı 34, sol əl qaldırdı lazım
55 qeyd etmək, 55 yeni NULL terminator olmaq pointing down onların sol qol lazımdır. Done.
Pretty asan bir sıralaması siyahısına 55 əlavə etmək üçün.
Və necə ola bilər?
>> Mənə irəli getmək və burada kodu Məsələn açmaq edək.
Mən gedit açmaq və mənə ilk iki faylları açmaq qoy edəcəyik.
Bir list1.h və bu kod yığın ki, mənə yalnız Xatırladaq
biz bir node təmsil etmək üçün istifadə edir.
A node siyahısında növbəti şey yalnız xal növbəti adlı n adlı int və bir pointer də var.
Bu. H fayl indi. Niyə?
Var, bu Konvensiyanın və biz bu böyük məbləği özümüz istifadə deyil
printf və digər funksiyaları yazırdı ancaq adam
stdio.h adlı fayl yazmaqla dünya üçün hədiyyə kimi bu funksiyaları bütün verdi.
Və sonra string.h var, sonra map.h var və bütün bu h fayllar var
siz görüldü və ya digər insanlar tərəfindən yazılı müddətində istifadə edə bilər ki.
Adətən o edir. H faylları typedefs kimi yalnız şeylər
və ya xüsusi növləri və ya sabitləri bəyan bəyan.
Siz mövzu faylları funksiyaları 'applications qoymaq deyil.
Siz əvəzinə, yalnız onların prototipləri qoydu.
Siz onlar ehtiyac nə dünya ilə bölüşmək istəyirəm şeyi qoymaq
onların kodu tərtib etmək üçün. Belə ki, yalnız bu vərdiş halına almaq üçün,
biz eyni şey etmək qərarına gəlib. Çox list1.h var deyil
lakin biz dünyada insanların maraq ola bilər ki, bir şey gətirdik
olan bağlı siyahı həyata keçirilməsi istifadə etmək istəyirik.
İndi list1.c, mən bu bütün şey ilə getmək deyil
o bir az uzun, çünki, bu proqram, lakin ən sətirinə tez real run bildirin.
Mənə List1 tərtib mənə sonra List1 run bildirin, və nə görürsünüz yerləşir edək
biz burada süni bir sadə kiçik proqram var
mənə siyahısına nömrələrin əlavə və aradan qaldırılması üçün imkan olacaq.
Mənə irəli getmək və menyu et 3 3 yazın edək.
Mən rəqəm daxil etmək istəyirəm - Gəlin 9 olan ilk sayı, nə
və indi mən siyahısı indi 9-a bildirib alıram.
Mənə davam və başqa durub edək, mən menyu et 3 təşkil edib.
Nə sayı mən əlavə etmək istəyirsiniz? 17.
Daxil edin. Mən yalnız bir daha edəcəyik.
Mənə sayı 22 daxil edək.
Beləliklə, biz bir an əvvəl slayd şəklində olduğunu bağlıdır siyahısı əvvəlinə var.
Bu durub əslində necə baş verir?
Həqiqətən, 22 siyahının sonunda indi.
Hekayə Beləliklə, biz bazar ertəsi mərhələdə bildirib və yalnız indi recapped
həqiqətən kodu baş edilməlidir.
Bir nəzər salaq. Bu fayl aşağıya fırladın edək.
Biz, funksiyaları, bəzi üzərində parıltı olacaq
amma biz enmək ki, daxil funksiyası lazımdır.
>> Biz bu bağlı siyahı yeni node daxil haqqında getmək necə edək.
Siyahısı Harada elan? Yaxşı, qoy ki, üst bütün yolu gedin
və mənim bağlı siyahı mahiyyətcə ilkin NULL olan bir göstərici kimi elan fark.
Mən ümumiyyətlə biz qarşı təbliğ etdiyiniz burada qlobal dəyişən kullanıyorum
onu qorumaq üçün kodu bir az messy edir, çünki
bu tənbəl, adətən sort, ancaq tənbəl deyil və bu yanlış deyil və bu, pis deyil
həyat üçün proqram yeganə məqsədi bir bağlı siyahı simülasyonu üçün olsun.
Hansı edirik məhz budur.
Hər funksiyası üçün keçməli sonra əsas bu elan və buna daha çox
biz bu proqram yazdıq, biz yerinə oh reallaşdırmaq isə yalnız qlobal edək
Bu proqram bütün məqsəd bir və yalnız bir bağlı siyahı nümayiş edir.
Belə ki, tamam hiss edir. Burada mənim prototipləri və biz, bu bütün vasitəsilə getməyəcək
amma sil funksiyası, bir tapmaq funksiyası, bir insert funksiyası və traverse funksiyası yazdı.
Amma indi daxil funksiyası geri enmək bildirin
və bu burada necə işlədiyini görmək.
Daxil line deyil - burada biz gedin.
Daxil edin. Biz xahiş olacaq, çünki Belə ki, hər hansı arqumentlər etmir
onlar əlavə etmək istədiyiniz nömrəni üçün bu funksiya istifadəçi içərisində.
Lakin ilk, biz onlara bir yer vermək üçün hazırlamaq.
Bu digər Məsələn surəti və yapışdırıb növ edir.
Bu halda, biz int ayrılması edilmişdir; bu dəfə biz bir node ayrılması edirik.
Mən, həqiqətən, bir node nə qədər bytes xatırlamıram, lakin gözəl var.
Sizeof mənim üçün ki, anlamaq olar.
Və niyə line 120 NULL kontrol edirəm?
Line 119 yanlış getmək bilər? Evet?
[Tələbə cavab anlaşılmaz]
Yaxşı. Sadəcə mən çox yaddaş tələb etdiyiniz halda ola bilər
və ya bir şey nın səhv və əməliyyat sistemi, mənə vermək üçün kifayət qədər bytes yoxdur
belə ki, NULL qaytarılması ilə qədər siqnalları, və mən kontrol olmayan
və yalnız kor-koranə ünvanı geri istifadə davam, bu, NULL ola bilər.
Bəzi unknown dəyər ola bilər; bir yaxşı şey istisna olmaqla, mən -
həqiqətən unknown dəyəri olmayacaq. Bu NULL ola bilər, mən istəmirəm belə
bu sui-istifadə və dereferencing risk.
Ki, baş verərsə, mən yalnız qayıtmaq və mən hər hansı bir yaddaş geri ala bilmədim kimi biz iddia lazımdır.
>> Əks halda, mən istifadəçi mənə əlavə etmək üçün bir sıra demək, mən bizim köhnə dostumuz GetInt zəng
və sonra bu biz bazar ertəsi təqdim yeni sintaksis idi.
"Newptr-> n 'siz malloc tərəfindən verilmiş ünvanı almaq deməkdir
olan, yeni bir node obyekt ilk byte təmsil
və sonra n adlı sahəsində gedin.
Bir az trivia sual: Bu kodu nə daha sirli line bərabərdir?
Necə başqa mən bu yazılı ola bilər? Bir zərbə almaq istəyirsiniz?
[Tələbə cavab anlaşılmaz]
Yaxşı. Edin. N istifadə edərək, lakin bu kimi olduqca kimi sadə deyil.
Mən ilk nə etmək lazımdır? [Tələbə cavab anlaşılmaz]
Yaxşı. I * newptr.n etmək lazımdır.
Belə ki, bu göstərici yeni açıq-aydın bir ünvan var deyib. Niyə?
Bu malloc geri Çünki. Deyərək * newptr "getmək"
siz olduğumuzda, sonra, sonra daha çox tanış. n istifadə edə bilərsiniz
lakin bu, yalnız biz insanlar edir, xüsusilə də əgər, bir az çirkin görünür
oxları ilə göstəricilərinə bütün vaxt çəkmək; dünyanın bu arrow notation haqqında standart var,
hansı tam eyni şey yoxdur.
Sol şey bir göstərici olduqda> notation - Beləliklə, siz yalnız istifadə edin.
Bir faktiki struct varsa Əks halda, bu. N istifadə edin.
Və sonra bu: Niyə newptr-> gələn başlamaq yoxdur null?
Biz mərhələnin sonunda bir sallanan sol off istəmirəm.
Biz düz aşağı işarə istəyirik, bu siyahının sonu deməkdir
potensial bu node da ola bilər, belə ki, biz daha yaxşı NULL əmin olun.
Və, ümumiyyətlə, sizin dəyişənlərin və ya data üzvləri və structs başlatılıyor
bir şey yalnız yaxşı təcrübədir.
Yalnız zibil var və ümumiyyətlə mövcud davam imkan sorun siz alır
Daha sonra haqqında bir şey unutmaq əgər.
>> Burada bir neçə hallarda var. Bu, bir daha, daxil funksiyası
dəyişən ilk adlanan əgər mən kontrol ilk şey deyil,
qlobal dəyişən NULL ki, heç bir bağlı siyahı var deməkdir.
Biz hər hansı bir ədəd daxil deyil, belə ki, bu cari nömrəsi daxil mənasız deyil
siyahısına, çünki yalnız siyahının əvvəlində məxsusdur.
Anita yalnız iddiasında, yalnız burada duran zaman bu idi
biz bir node ayrılmış qədər başqa heç bir mərhələsində burada idi
sonra o, ilk dəfə əlini qaldırmaq bilər
hər kəs bazar ertəsi onun sonra səhnəyə çıxmaq əgər.
İndi burada, bu demək üçün bir az çek əgər n yeni node dəyəri
, cari ilk node-ci ildə n dəyəri <olunur
ki, başlayıb ki, bir bağlı siyahı var deməkdir.
Var siyahıda ən azı bir node, lakin bu yeni oğlan
ki, biz ətrafında şeyi hərəkət etmək lazımdır əvvəl məxsusdur.
Siyahısında yalnız başlamışdır başqa sözlə, deyək
bu ki, yalnız sayı 17, - əslində, biz daha aydın bunu edə bilərsiniz.
Biz ilk çağırıb burada bir pointer ilə hekayə başlamaq varsa,
və ilkin, bu, NULL, və biz sayı 9 daxil
sayı 9 aydın siyahı əvvəlində məxsusdur.
Belə ki, biz yalnız ünvanı və ya sayı 9 malloced və burada qoymaq nin iddia edək.
Ilk ismarıcları 9 varsa, biz müzakirə ilk ssenari yalnız burada edək nöqtə bu adam deməkdir
bu kimi NULL tərk; indi biz 9 saylı var.
Biz daxil etmək istədiyiniz növbəti sayı 17-dir.
17 buraya aiddir, belə ki, biz bu yolu bir məntiqi step var olacaq.
Biz, biz sayı 8 daxil istədiyini iddia edək ki, əvvəl Belə ki, əvəzinə edək.
>> Belə ki, yalnız rahatlığı xatirinə, mən burada çəkmək üçün gedirəm.
Amma unutmayın, malloc ən yerdə qoya bilər.
Amma rəsm xatirinə, mən burada qoymaq lazımdır.
Mən yalnız sayı 8 üçün node ayrılmış etdik iddia, bu default NULL edir.
İndi nə var? Bir cüt.
Biz bu kimi bir pointer yenilənir Biz Bazar ertəsi, mərhələsində bu səhv etdi
sonra bu idi, sonra biz iddia - biz səhnədə hər kəs yetim.
Siz can't Çünki - burada əməliyyatları üçün vacibdir,
İndi, çünki biz yalnız kosmosda üzən növ ki, bu node 9 kaybettim.
Belə ki, bu barədə bazar ertəsi doğru yanaşma deyil.
Biz ilk başqa bir şey var.
Dünyanın dövlət bu kimi görünür. Əvvəlcə, 8 ayrılıb.
Nə 8 daxil daha yaxşı yol ola bilər?
Əvəzində ilk bu göstərici yenilənməsi, yalnız əvəzinə burada bu bir yeniləmə.
Beləliklə, biz bu NULL xarakter çevirmək olacaq ki kodu bir line lazımdır
node 9 işarə ki, faktiki göstərici daxil,
və sonra təhlükəsiz burada bu oğlan da qeyd etmək ilk dəyişə bilərsiniz.
İndi iki elementlərinin siyahısı, bir bağlı siyahı var.
Bu, həqiqətən, burada kimi nə görünür?
Biz kodu baxsaq, mən məhz o etdik ki, görürsünüz.
Mən newptr bildirib etdik və bu hekayə, newptr bu oğlan da işarə edilmişdir.
>> Mənə bir şey daha cəlb edək və bu üçün bir az daha otağı tərk olmalıdır.
Belə ki, kiçik kiçik rəsm bağışla.
Bu adam newptr adlanır.
Yəni olaraq, bir neçə xətləri əvvəllər elan dəyişən deyil - yalnız 25 yuxarıda.
Və 8 işarə edir. Mən newptr-> gələn demək zaman, struct getmək deməkdir ki,
newptr tərəfindən də qeyd edilir ki, belə ki, burada biz orada getmək.
Sonra arrow növbəti sahəsində əldə deyib, sonra = nə dəyəri qoymaq deyib?
Nə dəyər ilk idi? Ilk idi dəyəri
Birinci bu bu node da qeyd olunmalıdır deməkdir ki, bu düyün də işarə edilmişdir.
Başqa sözlə, nə, mənim yazı ilə bir gülünc mess olsa görünür
yalnız ətrafında bu oxlar hərəkət sadə bir fikir var
bu bir liner ilə kodu tərcümə.
Növbəti sahəsində ilk nə saxlamaq və sonra ilk əslində nə yeniləmə.
Bu bəzi vasitəsilə irəli və sürətli irəli gedək,
və indi bu quyruq durub yalnız baxmaq.
Mən bir node növbəti sahəsində NULL olduğunu tapmaq nöqtəyə almaq düşünək.
Və hekayə, bir detal bu nöqtədə mən artıq Parıldadıcı edirəm ki,
Mən line 142, sələfi göstərici burada başqa göstərici qədər təqdim etdik ki.
Əsasən, hekayə bu nöqtədə bir siyahısını uzun olur,
I növ iki barmaqları ilə gəzmək lazımdır, mən də uzaq getmək əgər, çünki
bir-uzunluğu siyahısına xatırlayıram, siz geri getmək bilməz.
Belə predptr bu fikir mənim sol barmaq və newptr - deyil newptr.
Burada bir başqa göstərici digər barmaq və mən siyahısı gəzinti yalnız cür edirəm.
Ki, mövcud görə. Amma yalnız burada sadə hallarda biri hesab edək.
Ki, pointer növbəti sahəsində NULL varsa, məntiqi dolayısı nə var?
Bu siyahı traversing və Əgər bir NULL pointer edib?
Siz siyahısı sonunda istəyirik, və s kodu bu bir əlavə element əlavə etmək
intuitiv növ, onların növbəti pointer NULL ki node almaq olacaq
Bu hazırda NULL, və yeni node ünvan üçün, baxmayaraq ki, o, dəyişir.
Belə ki, yalnız biz kiminsə sol artırılması ilə səhnəyə çəkdi kodu ok rəsm edirik.
>> Mən indi mənim əlləri dalğa lazımdır ki, işin
Düşünürəm ki, biz ətraf mühit bu cür bunu zaman itirilmiş almaq asandır düşünmək yalnız, çünki,
siyahısı nin ortasında durub kontrol edilir.
Siz anlamaq istəyirsinizsə, ancaq daxilən, nə etmək lazımdır
Bəzi sayı orta məxsusdur yerləşir siz gəzmək var
birdən çox barmaq ilə bir çox göstərici,
bu yoxlama ilə məxsus olduğu anlamaq element edir <cari,
> Cari və sonra ki, yer tapmaq
sonra siz çox diqqətlə ətrafında göstəricilərinə hərəkət yerləşir shell oyun bu sort var.
Və cavab, siz öz evdə vasitəsilə səbəb istəyirsinizsə,
aşağı yalnız kodu bu iki xətti sonunda, lakin həmin xətlərin üçün super vacibdir.
Əgər kimsə əl açılan və qaldırmaq əgər başqası, səhv üçün, çünki
yenidən, siz siyahısı orphaning ola bilər.
Daha konseptual yekunlaşdırmaq üçün, quyruq da daxil nisbətən sadə deyil.
Baş da durub, həmçinin nisbətən sadə
lakin bir əlavə göstərici bu dəfə güncellemeniz lazımdır
burada siyahısına sayı 5 sıxmaq,
və sonra ortada durub daha səy cəlb,
çox diqqətlə onun düzgün yer sayı 20 əlavə etmək üçün,
olan 17 və 22 arasında.
Siz, 22 yeni node 20 nöqtəsi kimi bir şey etmək lazımdır
sonra hansı node in göstərici ötən yenilənir lazımdır?
Bu həqiqətən daxil, 17 var.
Belə ki, təkrar edirəm ki, xüsusi həyata keçirilməsi üçün faktiki kodu uzatmaq lazımdır.
>> İlk baxışdan, bu bir az böyük, amma bu, həqiqətən, yalnız sonsuz loop var
ki, loop loop, loop, loop, siz NULL pointer hit kimi qırılma oldu
bu noktada zəruri daxil edə bilərsiniz.
Bu, sonra nümayəndəsi bağlı siyahı durub kodu.
Ki, bir çox növ idi və biz bir problem həll etdiyiniz kimi hiss
lakin biz bütün başqa bir təqdim etdik. Açığı, biz bütün bu vaxt sərf etdik
böyük O və Ω və daha tez problemləri həll etmək üçün çalışır, vaxt çalışan,
və burada biz geri, bu hiss böyük bir addım atırıq.
Və hələ, məqsəd veri olsa,
biz bazar ertəsi dedi ki, müqəddəs grail kimi hiss, həqiqətən olacaq
dərhal hər şeyi saxlamaq üçün.
>> Əslində, biz bir an qoymaq kənara bağlı siyahı etdi güman
və biz əvəzinə masa anlayışı təqdim etdi.
Və bir sıra kimi bir an üçün yalnız bir masa hesab edək.
Bu array və bu halda burada 26 elementlər, 25 0 var
və adları storage bəzi yığın lazım Güman:
Alice və Bob və Charlie və kimi.
Və bu adlar saxlamaq üçün bəzi data struktur lazımdır.
Yaxşı, bir bağlı siyahısı kimi bir şey istifadə edə bilər
və s Bob sonra Bob və Charlie əvvəl Alice daxil siyahısına gəzmək bilər.
Və əslində, bir kənara kimi belə kodu görmək istəyirsinizsə,
list2.h, biz məhz bunu bilirik.
Biz bu kod vasitəsilə getmək deyil, lakin bu ilk nümunəsi bir variantdır
ki, qondarma tələbə əvvəl gördüm başqa bir struct, təqdim
və sonra nə faktiki bağlı siyahısında saxlayan bir tələbə strukturu bir göstəricisidir
çox sadə bir az tam, n.
Kod faktiki strings əhatə orada belə həyata
lakin əl-qolu həqiqətən indi səmərəliliyi problemini həll etmək üçün, əgər
biz Alice adlı bir obyekt verilir əgər bu gözəl ola bilməz,
biz data strukturunda sağ yeri onu qoymaq istəyirəm
yalnız Alice qoymaq həqiqətən gözəl olardı kimi hiss,
adı birinci yeri, A ilə başlayır.
Və onun adı ikinci yeri, B ilə başlayır Bob.
Bir sıra ilə, və ya, bir masa ki, bir hash table zəng başlamaq edək
biz məhz bunu edə bilərsiniz. Biz Alice kimi bir ad verilir varsa,
Alice kimi simli, siz A-l-i-c-e yerləşir qoymaq bilərəm?
Biz hueristic lazımdır. Biz Alice kimi daxil etmək funksiyası ehtiyac
və cavab qaytarmaq, "bu yerdə Alice qoyun."
Bu funksiya, bu qara qutusu, bir hash funksiyası adlanır gedir.
>> A hash funksiyası, "Alice" kimi giriş edir ki, bir şey
və qaytarır, adətən, bəzi data strukturunda rəqəmli yeri Alice məxsusdur yerləşir.
Bu halda, bizim hash funksiyası nisbətən sadə olmalıdır.
Bizim hash funksiyası hansı karakter mən qayğı lazımdır "Alice" verilir, əgər demək lazımdır?
İlk. Mən [0] baxmaq, sonra [0] karakter A, əgər sayı 0 qayıtmaq deyirlər.
O B varsa, 1 qayıtmaq. Onun C varsa, s 2 qayıtmaq, və.
Bütün 0 indeksi, və s mənə Alice və sonra Bob və sonra Charlie daxil imkan və olardı
Bu data strukturu. Amma bir problem var.
Nə Anita yenidən çıxınca? Əgər
Biz Anita harada qoymaq bilərəm? Onun adı da, A hərfi ilə başlayır
biz bu məsələnin bir daha böyük mess etdik kimi və hiss edir.
İndi data strukturu dərhal durub, daimi vaxt durub var
olduqca pis halda daha xətti,
ancaq bu halda Anita ilə nə edə bilər?
Iki variant, həqiqətən, hansılardır? Evet?
[Tələbə cavab anlaşılmaz] Okay, biz başqa ölçüsü ola bilər.
Bu yaxşı. Belə ki, biz bazar ertəsi şifahi danışdıq kimi 3D şeylər inşa edə bilərsiniz.
Biz burada bir giriş əlavə, lakin, bu sadə saxlamaq üçün çalışıram Güman bilər.
Burada bütün məqsəd dərhal daimi zaman giriş əldə etmək
ki, çox mürəkkəblik əlavə edir.
Bu data strukturu Anita daxil çalışırken digər variantları hansılardır? Evet?
[Tələbə cavab anlaşılmaz] Yaxşı. Belə ki, aşağı hər kəs hərəkət edə
o, həqiqətən olmaq istəyir daha sonra Charlie Bob və Alice, aşağı nudges və kimi biz Anita qoydu.
>> Əlbəttə ki, indi bu bir yan təsiri var.
Bu data structure insanların bir dəfə daxil etmək istəmirəm, çünki yəqin ki, faydalı
lakin biz onlar sonradan əgər yoxlamaq istəyirəm, çünki
biz data strukturunda adları bütün çap istəyirsinizsə.
Biz nəhayət Bu data ilə bir şey olacaq.
Belə ki, indi biz o ehtimal yerdə artıq olan Alice, artıq berbat növü var.
Nə Bob, nə Charlie edir.
Belə ki, bəlkə bu yaxşı bir fikir deyil.
Lakin, həqiqətən, bu bir variantdır. Biz hər kəs aşağı keçmək bilər
və ya heck, Anita oyun gec gəldi, niyə biz yalnız Anita qoymaq deyil
deyil, burada deyil, burada deyil, burada isə yalnız siyahıda bir az aşağı öz qoymaq bildirin.
Amma sonra bu problem daha qalmaq başlayır.
Siz onun ilk adı əsasında dərhal Alice tapa bilər.
Və dərhal Bob və Charlie. Amma sonra, Anita axtarmaq
və hmm bax Alice yolu var.
Yaxşı, məni Alice aşağıda yoxlamaq edək. Bob Anita deyil.
Charlie Anita deyil. Oh, Anita var.
Və məntiq ki, qatar bütün yolu davam etsəniz,
Bu yeni data strukturu tapmaq və ya Anita daxil ən pis halda çalışan zaman nə var?
Bu doğru, O (n) var?
Ən pis halda, çünki, Alice, Bob, Charlie var. . .
bütün "Y" adına kimsə yol aşağı, belə ki, yalnız bir ləkə var buraxdı.
Şükür ki, biz "Z" adlı heç bir, biz çox alt Anita qoydu.
>> Biz həqiqətən problem həll deyil.
Belə ki, bəlkə biz bu üçüncü ölçüsü təqdim etmək lazımdır.
Biz bu üçüncü ölçüsü təqdim yoxsa Və bu, həyata çevirir
biz mükəmməl bunu edə bilər, lakin müqəddəs grail almaq olacaq
daimi zaman durub və dinamik insertions ki,
biz ölçüsü 26 ağır kodu dizisi yoxdur.
Biz istədiyiniz kimi bir çox adları kimi əlavə edə bilərsiniz, amma Gəlin burada 5 dəqiqə fasilə etmək
və sonra düzgün edin.
Bütün hüquqlar. Mən olduqca süni orada hekayə qurmaq
Alice, sonra Bob və sonra Charlie və sonra Anita, seçerek
onun adı aydın Alice ilə toqquşmaq gedirdi.
Amma ilə bazar ertəsi günü sona çatdı sual yalnız necə ehtimal
Bu cür toqquşma almaq olardı ki? Başqa sözlə,
biz bu cədvəlli strukturunda istifadə başlamaq əgər, bu, həqiqətən, yalnız bir sıra deyil
26 locations bu halda,
bizim giriş yerinə bərabər paylanır əgər nə?
Bu süni Alice və Bob və Charlie və David deyil və s əlifba,
bu eyni Z. vasitəsilə A yayılan oldu
>> Bəlkə biz yalnız uğurlu almaq lazımdır və biz iki A və ya iki B etmək fikrində deyilik
kimsə işarə çox yüksək ehtimalı ilə, həm
biz ümumiləşdirilmiş bu problem deyil, əgər 0 25
lakin, demək, 0 364 və ya 65, tipik bir il gün tez-tez sayı,
və sual, "bu otaq bizim iki eyni ad var ehtimalı nədir?"
Başqa sözlə, ehtimal bizə iki A ilə başlayan bir adı var ki, nə var?
Sual növ, eyni, lakin bu ünvan kosmik
Bu axtarış yer, ad günləri halda böyükdür
biz əlifba hərflərin çox il bir çox gün daha var.
Bir toqquşma ehtimalı nədir?
Yaxşı, biz riyaziyyat qarşı çıxış yolu figuring bu hesab edə bilər.
Heç bir toqquşma ehtimalı nədir?
Yaxşı, burada bu ifadə nə ehtimalı olduğunu deyir
onlar unikal ad var ki, bu otaqda yalnız bir adam var, əgər?
Bu 100% var. Çünki otaqda yalnız bir nəfər var, əgər
onun ad günü ilin həyata 365 gün hər hansı ola bilər.
Belə ki, 365/365 variantları mənə 1 dəyər verir.
Belə ki, hazırda sözügedən ehtimal yalnız 1-dir.
Ancaq otaq ikinci şəxs olduqda,
onların ad günü fərqli ehtimalı var?
Yalnız 364 mümkün gün məhəl sıçrayış il var
onların ad günü üçün digər şəxslər ilə toqquşmaq deyil.
Belə ki, 364/365. Üçüncü şəxs gəlir, bu, s 363/365, və.
Belə ki, biz, kiçik və kiçik əldə olunur, bu fraksiyaları birlikdə vurulması saxlamaq
anlamaq üçün bizə bütün unikal ad günü olduğunu ehtimal nədir?
Amma sonra biz, əlbəttə, yalnız cavab almaq və onun ətrafında flip bilər
və 1 minus bütün, biz nəhayət almaq lazımdır ifadə etmək
Sizin math kitab geri xatırlayıram, o, bu kimi bir az bir şey görünür
olan çox daha asan qrafik şərh olunur.
Burada bu qrafik, x oxunda ad günü sayı var
və ya ad günü olan insanlar və y ox üzrə sayı matç ehtimal edir.
Və nə dedi, siz varsa, belə deyək ki,
22, 23 kimi bir şey seçə imkan verir.
Otaq, 22 və ya 23 nəfər, varsa
o çox az adam iki eyni ad üçün gedir ehtimalı
combinatorially, həqiqətən, super yüksək.
50% bahis ki, praktiki olaraq yalnız 22 nəfər, seminar, bir sinif,
Insanların 2 eyni ad üçün gedir.
Çünki eyni ad ola bilər ki, bir çox yolları var.
Hətta pis, siz chart və sağ tərəfdən baxsaq,
zaman siz onu 58 tələbələri ilə bir sinif var
ad olan 2 nəfər ehtimalı super, super yüksək, təxminən 100%-dir.
İndi ki, real həyatı haqqında bir əyləncə fakt növ var.
>> Ancaq təsiri, indi data strukturları və saxlanılması məlumat
yalnız məlumatların bir gözəl, təmiz, bərabər yayılması var fərz o deməkdir ki,
və şeyi bir dəstə uyğun bir böyük kifayət qədər array var
Siz unikal yerlərdə insanların almaq olacaq demək deyil.
Siz toqquşma var olacaq. , Bu deyilən kimi, hashing bu anlayışı Belə
"Alice" kimi daxil alaraq və bir şəkildə masaj
və sonra 0 və ya 1 və ya 2 kimi bir cavab geri almaq.
Ki, funksiya bəzi çıxış geri almaq toqquşması bu ehtimalı ilə mürəkkəbləşdirilir olunur.
Belə ki, necə biz bu toqquşma idarə edə bilərsiniz?
Yaxşı, bir halda da, biz təklif edilib ki, ideya bilər.
Biz yalnız bir az daha sadəcə, bəlkə hər kəs aşağı keçmək, və ya
deyil, başqa hərəkət hər kəs çox isə yalnız mövcud spot altına Anita hərəkət edək.
Alice 0 Yəni əgər, Bob 1 deyil, Charlie, 2 deyil
biz yalnız yeri 3 Anita qoymaq lazımdır.
Bu probing xətti deyilən data strukturlarında bir texnikadır.
Yalnız bu xətt gəzinti edirik, siz probing növ istəyirik Xətti çünki
məlumat tərkibində mövcud ləkələr üçün.
Əlbəttə, bu, O (n) daxil devolves.
Məlumat struktur həqiqətən tam varsa, bu 25 nəfər artıq var
və sonra Anita çıxınca, o yeri Z olacaq nə başa və gözəl edir.
O, hələ də uyğun, biz sonra onun tapa bilərsiniz.
>> Amma bu şeyi sürətləndirmək məqsədi zidd idi.
Yerine bu üçüncü ölçüsü təqdim nə olur?
Bu texnika ümumiyyətlə ayrı-ayrı chaining adlanan və ya zəncirlər olan edilir.
Və bir hash table, indi bu cədvəlli strukturunda nə
Sizin masa yalnız göstəricilər bir sıra edir.
Amma nə bu göstəricilər qeyd tahmin nədir?
A bağlı siyahısı. Biz bu dünyanın, həm də ən yaxşı almaq nə olur?
Biz ilkin göstəriciləri üçün seriallarda istifadə
məlumat strukturu biz dərhal, [1], [30] və ya s [0] bilərsiniz
lakin biz bəzi rahatlıq var və biz Anita və Alice və Adəm uyğun olar ki,
və digər bir adı,
biz əvəzinə digər ox özbaşına inkişaf edək.
Və biz nəhayət, Bazar ertəsi kimi, bağlı siyahı ilə ifadə qabiliyyəti var.
Biz qanunsuz məlumat strukturu inkişaf edə bilər.
Alternativ olaraq, biz yalnız böyük 2-ölçülü array edə bilər
lakin əgər bir dəhşətli vəziyyət olacaq 2 ölçülü array satırları bir
onun adı A. ilə başlamaq olur əlavə şəxs üçün kifayət qədər böyük deyil
Allah biz böyük 2-ölçülü struktur təkrar bölüşdürə var
A adına bir çox insanlar var yalnız
Z bir şey adına belə bir neçə nəfər var xüsusilə.
Bu yalnız bir çox seyrək data quruluş olacaq.
Belə ki, hər hansı bir vasitə ilə mükəmməl deyil, lakin indi biz ən azı imkanı var
Alice ya Anita aid olduğu dərhal tapmaq,
ən azı şaquli ox baxımından,
və biz yalnız bu bağlı siyahısında Anita ya Alice qoymaq yerləşir qərar var.
Biz şeyi çeşidlənməsi haqqında qayğı yoxdur, nə qədər tez biz bu kimi bir strukturu Alice daxil edə bilər?
Bu daimi zamanı. [0] daxil Biz indeksi, və heç bir var, əgər
Alice ki bağlı siyahı əvvəlində gedir.
Lakin böyük bir məşğul deyil. Anita sonra çıxınca əgər Çünki
addımlar bir sıra sonra, Anita Ü aid deyil?
Yaxşı, [0]. Oop. Alice ki bağlı siyahı artıq.
>> Amma biz bu adlar çeşidlənməsi haqqında qayğı yoxsa,
biz yalnız Alice üzərində, insert Anita hərəkət edə bilər, lakin hətta daimi dəfə.
Alice və Adəm və bütün bu digər bir adları var belə
həqiqətən fiziki onlara dəyişkən deyil. Niyə?
Biz yalnız bilən bağlı siyahısı ilə burada Çünki bu qovşaqlarının hər halda var idi?
Siz bütün çörək qırıntıları hərəkət edir.
Ətrafında okları hərəkət, siz fiziki ətrafında hər hansı bir məlumat hərəkət yoxdur.
Beləliklə, biz dərhal, bu halda, Anita əlavə edə bilərsiniz. Sabit vaxt.
Beləliklə, biz daimi zaman axtarış və Anita kimi kimsə daim zaman durub var.
Amma dünya oversimplifying cür.
Biz sonra Alice tapmaq istəyirsinizsə?
Neçə addımlar ki, iştirak edir?
[Tələbə cavab anlaşılmaz]
Exactly. Də bağlı siyahısında Alice əvvəl insanların sayı.
Bizim data strukturu, yenidən, bu şaquli çıxışı var, çünki Belə ki, kifayət qədər mükəmməl deyil
və sonra asma bu bağlı siyahıları var - əslində isə bu bir sıra çəkmək deyil bildirin.
Bu bağlı siyahıları bu kimi bir az bir şey görünür ki, bu off asma etdi.
Ancaq problem varsa, Alice və Adəm və bütün bu digər bir adları
orada daha çox başa,
kimsə addımlar dəstə alaraq ola bilər tapmaq,
, siz bağlı siyahı axır var bcause
bir xətti əməliyyatdır.
Belə ki, həqiqətən, sonra durub zaman nəticədə n siyahısına elementlərinin sayı yerləşir O (n) edir.
Bölünür, in özbaşına bu m bağlı siyahıları sayı yerləşir m, zəng edək
biz bu şaquli ox var ki.
Başqa sözlə, biz həqiqətən adları bərabər yayılması güman əgər,
tamamilə qeyri-real. Daha bir məktub açıq-aydın daha var.
>> Amma biz an vahid paylanması üçün güman əgər,
və biz ümumi insanlar, və m ümumi zəncir n
Bu zəncir hər bizə mövcud, sonra uzunluğu
ədalətli sadəcə ümumi, n zəncirlər sayı bölünür olacaq.
Belə n / m. Biz bütün riyazi ağıllı ola bilər Lakin burada.
Bu sabit sayı var, çünki m, daimi deyil.
Siz əvvəlində sizin array bəyan olacaq
və biz boyutlandırma şaquli ox deyilik. Anlayışı ilə, müəyyən edilir ki,.
Bu dəyişən ki, danışmaq, yalnız üfüqi ox var.
Belə ki, texniki, bu daimi deyil. Belə ki, indi durub dəfə
olduqca çox O (n) edir.
Belə ki, bütün daha yaxşı hiss etmir.
Amma həqiqət burada nə var? Yaxşı, bütün bu vaxt, həftə,
deyirdik olduğunuz O (n ²). O (n), 2 x n ², - n, 2 bölünür. . . ech.
Bu, sadəcə n ² var. Amma indi dövr bu hissəsində,
biz daha real dünya haqqında danışmağa başlaya bilərsiniz.
Və n / m yalnız tək n artıq tamamilə daha sürətli edir.
Bir min adları var, və çox buketler onları parçalamaq edin
siz bu zəncirlər hər yalnız on adları var ki,
tamamilə on şeyi axtarış min şey daha sürətli olacaq.
Və qarşıdakı problem dəstdən birini siz etiraz edir
məhz bu barədə düşünmək belə olsa, evet,
asimptotik və riyazi, hələ də yalnız xətti deyil,
şeyi tapmaq üçün çalışırıq zaman ümumi gücünü zaptetti.
Əslində, bu çox daha sürətli olacaq
çünki bu bölən edir.
Və yenə bu ticarət-off olmalıdır olacaq
və nəzəriyyəsi və reallıq arasındakı bu münaqişə,
və kulplar bir dövr bu nöqtədə dönüş başlayacaq
biz növ semster sonuna hazırlamaq kimi reallıq bir daha çox,
biz web proqramlaşdırma dünya tanıtmaq kimi
istifadəçilər üçün gedir çünki yerləşir həqiqətən, performans saymaq gedir
yoxsul dizayn qərarları hiss təşəkkür başlayın.
>> Bir bağlı həyata haqqında Belə ki, necə getmək yoxdur - bir hash table 31 elementləri ilə?
Və əvvəlki Məsələn ad günləri haqqında əsassız idi.
Kimsə 1 Yanvar və ya Fevral 1 ad varsa, bu bucket onları qoymaq lazımdır.
Yanvar 2, 2 fevral, 2 mart varsa, bu bucket onları qoymaq lazımdır.
31 səbəb olmuşdur. Necə bir hash table bəyan edirsiniz?
Bu olduqca sadə ola bilər, node * masa üçün mənim ixtiyari adı, [31] edir.
Bu qovşaqlarının mənə 31 göstəricilərinə verir
və mənə bağlı siyahıları 31 göstəricilərinə üçün imkan verir ki,
o zəncirlər ilkin NULL, hətta əgər.
Mən saxlamaq istəyirsinizsə, mən "Bob", "Charlie" "Alice" qoymaq üçün nə istəyirsiniz?
Bəli, biz bir quruluş olan şeyi kesmek lazımdır
biz Alice, Bob qeyd etmək Charlie qeyd etmək və s. lazımdır, çünki
Biz yalnız tək adları ola bilməz, belə ki, mən burada node adlı yeni struktur yarada bilər.
>> Faktiki node nədir? Bu yeni bağlı siyahısında node nədir?
Söz adlı ilk şey, bu şəxsin adı üçün.
BOY, ehtimalla, bir insan adı maksimum uzunluğu aiddir
ki, nə olursa olsun, 20, crazy künc hallarda 30, 40 simvol
və +1 nə üçün vacibdir? Bu, sadəcə əlavə NULL xarakteri, \ 0 var.
Belə ki, bu düyün, içərisində özünü "bir şey" wrapping edir
lakin sonrakı adlı göstərici bəyan
biz Charlie Bob üçün zəncir Alice bilər və s edir.
NULL ola bilər amma mütləq olmalıdır deyil.
Bu hash masalar hər hansı suallar? Evet?
[Tələbə anlaşılmaz, sualı] Bir sıra - yaxşı sual.
Niyə bir sıra daha çox yalnız char * Bu char söz?
Bu qədər əsassız Məsələn, mən müraciət etmək istəmir
orijinal adları hər malloc üçün.
Mən string üçün yaddaş maksimum məbləği bəyan istədi
Mən Alice \ 0 və malloc və pulsuz və kimi ilə məşğul olan strukturu surəti bilər ki.
I yer istifadə daha şüurlu olmaq istəyirdi, lakin mən bunu bilər. Sual Yaxşı.
Belə ki, bu uzaq ümumiləşdirmək üçün cəhd edək
və ümumiyyətlə data strukturları bu gün qalan diqqət
və eyni əsaslar istifadə həll edə bilər ki, digər problemləri
hətta data strukturları baxmayaraq öz özəllikləri fərqlənə bilər.
>> Belə ki, kompüter çıxır, ağaclar çox rast gəlinir.
Və siz, bir ailə ağac kimi bir ağac növ hesab edə bilər
bəzi kökləri, bəzi matriarch ya patriarx var olduğu
nənə və ya baba və ya əvvəllər geri,
hansı altında ana və dad və ya müxtəlif bacı və ya bu kimi var.
Belə ki, bir ağac strukturu qovşaqlarının var və övladı var
hər node üçün adətən 0 və ya daha çox uşaq.
Və jarqon bəzi burada bu şəkil bax
edir kənarları haqqında kiçik uşaq və ya grandkids hər hansı
kim onlardan qaynaqlanan heç bir oxlar var
o deyilən yarpaq, və daxili hər kəs var
daxili node edir; siz bu xətt bir şey zəng edə bilərsiniz.
Amma bu quruluşu olduqca ümumi. Bu bir az ixtiyari var.
Biz sağ üç övladı var, sol bir uşaq var
altındakı iki övladı qaldı.
Belə ki, biz hər şeyi standartlaşdırmaq başlamaq əgər müxtəlif ölçülü ağaclar var, ancaq
və bir əvvəlki qısa olan binar axtarış Patrick video bu xatırlayıram bilər
online, ikili axtarış bir sıra ilə həyata keçiriləcək yoxdur
bir yazı taxtası üzrə kağız və ya ədəd.
Bir daha mürəkkəb data strukturunda nömrələri saxlamaq istədiyini düşünək.
Bu kimi bir ağac yarada bilər.
Siz C elan node ola bilər ki, node daxilində bu ən azı iki elementləri ola bilər.
Bir siz saxlamaq istədiyiniz nömrə və digər - yaxşı, biz bir daha lazımdır.
Digər onun uşaqlar var.
Belə ki, burada başqa data strukturu var. Bu dəfə bir node n bir sıra saxlanılması kimi müəyyən edilir
və sonra iki göstəricilərinə; sol uşaq və sağ uşaq.
Onlar özbaşına deyilik. Bu ağac haqqında maraqlı var?
>> Biz Patrick onun video onu müəyyən necə bu müəyyən və ya sonra necə model nədir?
O, burada bəzi çeşidlənməsi olduğunu cür Aşkar var
lakin sadə qayda var? Evet?
[Tələbə cavab anlaşılmaz]
Mükəmməldir. Bu nəzər, siz, sol kiçik nömrələri bax
böyük sol nömrələri, lakin hər node üçün doğru.
Hər node üçün, artıq onun sol uşaq az və çox hüququ uşaq daha.
Mən sayı 44, demək, bu data structure axtarmaq istəyirsinizsə, Bu artıq o deməkdir ki,
Mən, çünki indi bu daha mürəkkəb data strukturları bütün kimi, kök başlamaq üçün
biz yalnız başlanğıcdır, bir şey bir göstərici yoxdur.
Və bu halda, əvvəlində kök edir. O, sol son deyil
Bu struktur kökü var. Mən burada 55 var bax, mən 44 arıyorum.
Hansı istiqamətdə mən getmək istəyirəm?
Aydındır ki, doğru çox böyük olacaq, çünki Bəli, mən, sol getmək istəyirəm.
Belə ki, burada qeyd, siz konseptual yarısında ağac Doğrama növ istəyirik
Siz sağ enən heç etdiyiniz çünki.
Belə ki, indi mən 55-dən 33-gedin. Bu bir sıra çox kiçik.
Mən 44 arıyorum, indi mən 44 bu ağac olsa, mən sağa aşkar edə bilərsiniz bilirik.
Belə ki, yenə, mən budama yarısında ağac edirəm.
Bu telefon kitab konseptual olduqca çox eyni deyil.
Bu, biz yazı taxtası üzrə sənədləri ilə nə eyni deyil
amma bu bizə həqiqətən imkan verir ki, bir daha mürəkkəb strukturu var
Bu, bölmək və alqoritmi dizayn fəth
və əslində, belə bir struktur traversing - whoops.
Bu kimi bir quruluş traversing, yalnız olduğu "bu yolla getmək və ya yol getmək"
bölməsində bu həyata keçirərkən ilk fikrinizi əyilmiş bütün kod deməkdir
və ya, recursion ya iteration istifadə edərək, ikili axtarışı üçün, evdə vasitəsilə gəzinti
bu boyun bir ağrı var. Orta element tap, sonra yuvarlaqlaşdırma yuxarı və ya aşağı edin.
>> İndi yenidən recursion istifadə edə bilərsiniz, çünki bir gözəllik, bu var
lakin daha çox pakizə. Həqiqətən, siz sayı 55 istəyirik və 44 tapmaq istəyirsinizsə,
Bu halda sola getmək, sonra nə etməliyəm? Siz eyni alqoritmi axır.
Siz node dəyəri yoxlamaq, sonra sol və ya sağ getmək.
Sonra sol və ya sağ gedin node dəyəri yoxlayın.
Bu mükəmməl recursion uyğun.
Belə ki, hətta keçmişdə biz recursion cəlb bəzi ədalətli ixtiyari nümunələri etdik
ki, data stuctures ilə recursive olmalıdır etməyib
xüsusən ağaclar, bir problem alaraq bu fikri mükəmməl bir proqram var
bu daralır və sonra eyni tipli, lakin kiçik, proqram həlli.
>> Belə ki, təqdim edə bilər ki, başqa data strukturu var.
Bu sirli baxmaq ilk baxışda nəzərdə, lakin bu, bir gözəl edir.
Belə ki, bu, söz axtarış miras olan trie, trie adlı data strukturu
yenidən cəhd-val elan, lakin dünyada bunlar çağırır nə deyil. Çalışır. T-r-i-e.
Bəzi növ ağac strukturu, lakin trie ildə qovşaqlarının hər
nə görünür? Bu qısaldılmış növü var, çünki bu bir az yanlışdır.
Lakin bu trie hər node həqiqətən bir sıra kimi görünür.
Və baxmayaraq bu diaqram müəllifidir, o, göstərilən deyil
Bu halda, bu trie kimin məqsədi həyat sözlər saxlamaq üçün bir data strukturu
A-l-i-c-e və ya B-o-b kimi.
Və yol olan s Bu data mağazalar Alice və Bob və Charlie və Anita və
ki, bir trie Alisa saxlamaq vasitəsi bir sıra istifadə edir
biz bir sıra kimi görünür olan kök node-da başlayacaq
və stenoqrafiya notation yazılı oldu.
Ilə heç bir adı var idi, çünki müəllif abcdefg çıxarılmışdır.
Onlar yalnız M və P və T göstərdi, lakin bu halda,
nin burada olan bəzi adların səfərdə Alice və Bob və Charlie hərəkət edək.
Maxwell bu sxemdə əslində.
Belə ki, necə müəllifi mağaza etdi M-a-x-w-e-l-l?
O, kök node başladı və getdi [M], belə ki, təxminən 13-sıra 13 yer.
Sonra oradan bir göstərici yoxdur.
Başqa array gedən bir göstərici.
Oradan müəllifi, sol üst orada təsvir kimi, yer A ki massivinə dizine
və o, və ya o, başqa bir sıra ki, pointer sonra
və yeri X. da pointer getdi
Sonra s növbəti array yeri W, E, L, L, və,
və nəhayət, in əslində bu şəkil qoymaq edək.
Kodu kimi bir node baxmaq nə?
Bir trie bir node daha qovşaqlarının üçün göstəricilər bir sıra var.
Amma ən azı bu həyata, boolean dəyər bir növ var var.
Mən bunu is_word zəng etmək üçün baş verir. Niyə?
Siz Maxwell daxil olduğunuz zaman daxil deyilik Çünki
Bu data strukturu şey.
Siz X. yazılı deyilik M. yazılı deyilik
Siz yapýyorsun bütün göstəricilər aşağıdakı edir.
Sonra M, A təmsil göstəricisidir təmsil edən göstərici
sonra X, W, E, L, L, təmsil göstəricisidir
lakin nə sonunda nə etmək lazımdır kontrol getmək növ, mən bu yeri çatıb.
Məlumat strukturunda burada bitir bir söz var idi.
>> Belə ki, nə bir trie həqiqətən dolu və müəllif təmsil seçdi olunur
az üçbucaq bu terminuses.
Əsl Bu yalnız faktı bu üçbucağı burada o deməkdir ki, bu boolean dəyər
Siz ağac geri getmək əgər deməkdir
ki Maxwell bu deyil adlı bir söz deməkdir.
Məsələn Amma söz foo,
, ağac deyil mən üst qədər burada kök node-da başlayacaq əgər, çünki
Heç bir f pointer, heç o pointer, heç o göstərici var. Foo bu lüğət bir ad deyil.
Amma əksinə, turing, t-u-r-i-n-g. Yenə t və ya u və ya r ya i və ya n və ya g saxlaya bilmədi.
Amma aşağı burada bu node doğru yol dəyəri Bu data tərkibində mağaza idi - ağac ilə
doğru üçün is_word bu boolean dəyər yaradılması.
Belə bir trie, bu çox maraqlı meta strukturunun növ
həqiqətən lüğət bu cür sözləri özləri saxlanılması deyilik yerləşir.
Aydın olmaq üçün, yalnız bəli ya heç saxlanılması edirik, burada bitir bir söz var.
>> İndi dolayısı nə var?
Siz yaddaşında saxlamaq üçün çalışdığınız bir lüğətdə 150,000 sözlər varsa
bir bağlı siyahısı kimi bir şey istifadə edərək,
Siz bağlı siyahısında 150,000 qovşaqlarının üçün gedir.
Və əlifba sırası ilə bu sözlər bir tapmaq O (n) vaxt bilər.
Xətti vaxt. Amma trie burada halda,
bir söz tapmaq çalışan zaman nə var?
Burada gözəllik çıxır ki, siz artıq bu lüğətdə 149.999 sözlər, olsa belə
Bu data strukturu ilə həyata
ki, daxil, Alice kimi, Alice bir daha şəxs tapmaq və ya əlavə etmək üçün nə qədər vaxt lazımdır?
Yaxşı, bu arxada xarakter üçün bəlkə 6 addımlar yalnız 5 var.
Çünki tərkibində digər adları presense
Alice daxil yolu ilə almaq deyil.
Bundan başqa, Alice tapmaq bu lüğətdə 150,000 sözlər var dəfə
, bütün Alice tapmaq yolla almaq deyil
Alice çünki. . . . . burada, çünki mən bir boolean dəyər tapdı.
Və heç boolean doğru, sonra Alice olduqda sözlər Bu data struktur deyil.
Başqa sözlə, bu yeni daxil şeyi şeyi tapmaq və daxil olan çalışan zaman
trie data strukturu O - bu n deyil.
150,000 nəfər presense Alice heç bir təsiri var, çünki görünür.
Nin bu k İngilis söz maksimum uzunluğu olduğu k, zəng Belə bildirin
hansı adətən artıq 20-bir simvol çoxdur.
Belə ki, k sabit deyil. Müqəddəs grail Beləliklə, biz artıq aşkar görünür
edər bir trie, daimi vaxt ki silme üçün lookups üçün edir.
Çünki artıq strukturunda şeyi sayı
hətta fiziki yoxdur. Yenə yalnız off yoxlanılır və sort edirik, bəli və ya xeyr,
gələcək çalışan zaman heç bir təsiri yoxdur.
>> Amma tutmaq olmalıdır var, əks halda biz çox vaxt sərf olmazdı
Bütün bu digər strukturlar üzrə yalnız nəhayət gözəl olan gizli bir almaq.
Yaxşı qiymət biz burada bu böyüklük nail ödəyir? Space.
Bu şey kütləvi deyil. Və səbəbi müəllifi
burada təqdim etməmiş, qeyd seriallarda kimi baxmaq ki, bu şeyi ki,
O ağac istirahət trie qalan, cəlb etməyib
onlar yalnız hekayə müvafiq deyilik, çünki.
Lakin bu qovşaqlarının bütün geniş super və ağac hər node tutur
26 və ya faktiki olaraq, bu halda mən apostrof üçün yer daxil olmaqla, çünki 27 simvol ola bilər
belə ki, biz apostrophized sözləri ola bilər.
Bu halda, bu geniş Diziler var. Onlar picutured deyilik Belə ki, baxmayaraq ki,
Bu RAM kütləvi məbləği alır.
Hansı müasir hardware especilly, gözəl ola bilər
ancaq tradeoff var. Biz daha çox yer xərcləyərək az vaxt almaq.
Belə ki, bu bütün gedir?
Yaxşı, nə edək - burada bax edək.
Burada bu oğlan bir jump etmək edək.
>> Iman və ya, C indi bir neçə dəfə olub kimi çox fun,
daha müasir şeyə keçid zaman olduğu dövr çatma nöqtəsində edirik.
Yüksək səviyyədə şeylər. Və hətta həftə növbəti neçə olsa
biz hələ göstəricilərinə və yaddaş idarə dünyada özümüzü batırmaq davam edəcəyik
biz sonra qurmaq bilər ki, rahat almaq üçün,
sonunda oyun Bu dil, istehzayana deyil, təqdim etmək, son nəticədə edir.
Biz HTML söhbət 10 dəqiqə kimi xərcləmək lazımdır.
HTML bütün biçimlendirme dili, və nə bir biçimlendirme dili
"Bu qalın edin 'deyə açıq Mötərizədə və qapalı Mötərizədə bu sıra
"Bu mərkəzli etmək 'Bu italik etmək'. '
Bu bütün intellektual maraqlı deyil, lakin faydalı super deyil.
Və əlbəttə, bu gün hər yerdə var.
Amma nə HTML dünya haqqında güclü və web proqramlaşdırma ümumiyyətlə,
dinamik şeylər qurur; PHP və ya Python və ya Ruby və ya Java və ya C # kimi dillərdə kodu yazmaq.
Həqiqətən, hər hansı seçdiyiniz dil və dinamik HTML yaradan.
Dinamik CSS deyilən bir şey yaradan.
Cascading stillər, estetik də edir.
Və baxmayaraq, bu gün mən tanış Google.com kimi bəzi veb getmək əgər
və mən, bəlkə əvvəl görülən etdiyiniz geliştirici, görünüşü mənbə, keçirmək üçün getmək
lakin mənbə keçirmək üçün gedir, bu məhsulları yəqin ki, olduqca sirli görünür.
Amma bu Google.com həyata keçirir əsas kodu.
Ön sonuna. Və həqiqətən bütün bu qabarıq estetik stuff deyil.
Burada CSS edir. Mən aşağı scrolling saxlamaq, biz bir renk kodlu məhsulları almaq lazımdır.
Bu HTML edir. Google kodu mess kimi görünür, amma əslində fərqli bir pəncərə açmaq əgər
biz bu bəzi struktur bilərsiniz.
Mən bu açmaq varsa, burada qeyd, bir az daha oxunaqlı deyil.
Biz əvvəl bu tag görmək olacaq, [söz] bir tag edir
HTML, baş, bədən, div, script, mətn sahəsi, span, mərkəzi, div.
Bu da, ilk baxışdan sirli görünüşlü və sort edir
lakin bu mess bütün müəyyən nümunələri və repeatable nümunələri aşağıdakı
bir dəfə biz əsasları aşağı almaq, belə ki, bu kimi kod yazmaq edə bilərsiniz
və sonra JavaScript adlı başqa bir dil istifadə edərək, bu kimi kodu manipulyasiya.
Və JavaScript browser daxilində çalışan bir dil
Google xəritələri istifadə edir ki, əlbəttə alver alət Harvard kursları, istifadə ki, bu gün
siz dinamizm bütün dəstə vermək, Facebook, ani statusu yenilikləri göstərmək verir
Twitter anında tweets göstərmək üçün istifadə edir.
Bütün bu özümüzü daxil batırmaq başlayacaq
Amma almaq üçün biz Internet haqqında bir az bir şey anlamaq lazımdır.
Burada Bu klip yalnız uzun bir dəqiqə və indi bu əslində kəsb edək,
İnternet gəlmək haqqında nə üçün bir iltifat kimi çalışır. Mən sizə "Net və Warriors". Vermək
>> [♫ Slow xor musiqi ♫]
[Kişi dastançı] O bir mesaj gəldi.
Protokol bütün öz ilə.
[♫ Faster elektron musiqi ♫]
O, yönlendirici uncaring, sərin firewall dünya gəldi
və ölüm çox pis təhlükələr.
O, sürətli. O, güclü deyil. O, TCP / IP, və o ünvan var.
Net və Warriors.
[Malan] Sonrakı həftə sonra. İnternet. Web proqramlaşdırma. Bu CS50 edir.
[CS50.TV]