[Powered by Google Translate] [Seksyen 6: Kurang Selesa] [Nate Hardison] [Universiti Harvard] [Ini adalah CS50.] [CS50.TV] Semua hak. Selamat datang kepada seksyen 6. Minggu ini, kita akan bercakap mengenai struktur data dalam seksyen, terutamanya kerana masalah ini minggu ini ditetapkan pada spellr melakukan sekumpulan keseluruhan data penerokaan struktur yang berbeza. Terdapat sekumpulan cara yang berbeza anda boleh pergi dengan set masalah, dan data struktur yang lebih anda tahu mengenai, perkara-perkara yang lebih sejuk yang boleh anda lakukan. 

Jadi mari kita mulakan. Pertama kita akan bercakap tentang susunan, timbunan dan beratur struktur data yang kita akan bercakap tentang. Susunan dan beratur adalah benar-benar berguna apabila kita mula bercakap tentang graf, yang kita tidak akan melakukan begitu banyak hak sekarang. Tetapi mereka benar-benar baik untuk memahami salah satu struktur data asas besar CS. Penerangan dalam spesifikasi set masalah, jika anda tarik, ceramah tentang susunan sebagai serupa dengan timbunan dulang makan bahawa anda mempunyai di kafeteria di dewan makan di mana apabila kakitangan makan datang dan meletakkan dulang makan selepas mereka telah dibersihkan mereka, mereka timbunan mereka salah satu di atas yang lain. Dan kemudian apabila anak-anak datang dalam untuk mendapatkan makanan, mereka tarik dulang, pertama satu atas, maka satu di bawah, maka satu di bawah yang. Jadi, pada hakikatnya, dulang pertama bahawa kakitangan makan meletakkan adalah yang terakhir yang mendapat diambil kira. Yang terakhir bahawa kakitangan makan diletakkan di atas adalah yang pertama yang mendapat diambil kira untuk makan malam. Dalam spec set masalah, yang anda boleh memuat turun jika anda tidak sudah, kita bercakap mengenai model stuktur timbunan data dengan menggunakan jenis ini struct. 

Jadi apa yang kita miliki di sini, ini adalah serupa dengan apa yang telah dibentangkan dalam kuliah, kecuali dalam kuliah kita mempersembahkan dengan ints berbanding char * s. Ini akan menjadi timbunan bahawa kedai apa? Daniel? Apa yang kita menyimpan dalam timbunan ini? [Daniel] Rentetan? >> Kami akan menyimpan rentetan dalam timbunan ini, sebenarnya. Semua yang anda perlu untuk mewujudkan timbunan adalah array kapasiti tertentu, yang dalam kes ini, kapasiti akan berada dalam semua topi kerana ia adalah pemalar. Dan kemudian di samping array, semua kita perlu untuk mengesan saiz semasa array. Satu perkara yang perlu diambil perhatian di sini bahawa jenis sejuk adalah bahawa kita sedang mewujudkan struktur data disusun pada bahagian atas struktur data yang lain, array. Terdapat banyak cara yang berbeza untuk melaksanakan susunan. Kami tidak akan melakukan ia agak lagi, tetapi diharapkan selepas melakukan masalah berkaitan senarai, anda akan melihat bagaimana anda boleh melaksanakan timbunan di atas senarai berkaitan serta. Tetapi untuk sekarang, kita akan berpegang kepada tatasusunan. Jadi sekali lagi, semua yang kita perlukan adalah array dan kita hanya perlu untuk mengesan saiz array. [Sam] Maaf, mengapa ia bahawa anda berkata timbunan di atas tali? Bagi saya, ia seolah-olah seperti rentetan berada dalam timbunan. [Hardison] Yeah. Kami mewujudkan, kami mengambil pelbagai struktur data kami - itulah persoalan yang besar. Jadi persoalannya ialah mengapa, bagi orang-orang yang menonton talian ini, mengapa kita mengatakan bahawa timbunan di atas tali, kerana di sini ia kelihatan seperti tali berada di dalam timbunan? Yang benar-benar kes itu. Apa yang saya merujuk kepada adalah bahawa kita telah mendapat struktur data array. Kami telah mendapat pelbagai char * s, pelbagai rentetan, dan kita akan menambah bahawa dalam usaha untuk mewujudkan struktur data disusun. 

Jadi timbunan adalah sedikit lebih kompleks daripada array. Kita boleh menggunakan array untuk membina timbunan. Jadi itulah di mana kita katakan bahawa timbunan dibina di atas pelbagai. Begitu juga, seperti saya katakan sebelum ini, kita boleh membina timbunan di atas senarai berkaitan. Sebaliknya menggunakan array untuk memegang elemen kita, kita boleh menggunakan senarai berpaut untuk memegang elemen kami dan membina timbunan sekitar itu. Mari kita berjalan melalui beberapa contoh, melihat beberapa kod, untuk melihat apa yang sebenarnya berlaku di sini. Di sebelah kiri, saya telah dibuang ke bawah apa yang struct timbunan akan kelihatan seperti dalam ingatan jika kapasiti telah # ditakrifkan untuk menjadi empat. Kami telah mendapat pelbagai empat unsur * char kami. Kami telah mendapat tali [0], rentetan [1], rentetan [2], rentetan [3], dan kemudian bahawa ruang terakhir bagi integer saiz kami. Adakah ini masuk akal? Okay. Ini adalah apa yang berlaku jika apa yang saya lakukan di sebelah kanan, yang akan menjadi kod saya, adalah untuk hanya mengisytiharkan struct, struct disusun dipanggil s. Ini adalah apa yang kita dapat. Ia meletakkan jejak ini dalam ingatan. Soalan pertama di sini ialah apakah kandungan struct timbunan ini? Sekarang mereka apa-apa, tetapi mereka tidak benar-benar apa-apa. Mereka ini jenis sampah. Kami tidak mempunyai idea apa yang di dalamnya. Apabila kita mengaku s timbunan, kita hanya membuang yang turun di atas ingatan. Ia adalah jenis seperti mengisytiharkan int i dan tidak Memulakan ia. Anda tidak tahu apa yang di sana. Anda boleh membaca apa yang di sana, tetapi ia tidak mungkin super helpful. Satu perkara yang anda mahu untuk sentiasa ingat untuk lakukan adalah memulakan apa sahaja yang perlu dimulakan. Dalam kes ini, kita akan memulakan saiz menjadi sifar, kerana itu akan berubah menjadi sangat penting bagi kita. Kita boleh pergi ke hadapan dan memulakan semua petunjuk, semua s * char, untuk menjadi beberapa nilai yang difahami, mungkin batal. Tetapi ia tidak benar-benar perlu bahawa kita berbuat demikian. 

Kini, dua operasi utama pada susunan? Sesiapa yang ingat dari kuliah apa yang anda lakukan dengan susunan? Ya? [Stella] Menolak dan muncul? >> Tepat sekali. Menolak dan pop dua operasi utama pada susunan. Dan apakah menolak lakukan? >> Ia meletakkan sesuatu ke atas tindanan, dan kemudian pop mengambil ia dimatikan. [Hardison] Tepat sekali. Jadi menolak menolak sesuatu di atas tindanan. Ia adalah seperti kakitangan makan meletakkan dulang makan ke atas kaunter. Dan muncul mengambil dulang makan luar tindanan. Mari kita berjalan melalui beberapa contoh apa yang berlaku apabila kita menolak perkara-perkara ke dalam tindanan. Jika kita untuk menolak rentetan 'hello' ke dalam tindanan kami, ini adalah apa gambarajah kami akan kelihatan seperti sekarang. Lihat apa yang berlaku? Kami menolak ke dalam elemen pertama pelbagai rentetan kami dan kita upped kiraan saiz kami menjadi 1. Jadi, jika kita melihat perbezaan antara kedua-dua slaid, di sini adalah 0, di sini sebelum menolak. Berikut adalah selepas menolak. Sebelum menolak, selepas menolak. Dan sekarang kita mempunyai satu elemen dalam timbunan kita. Ia adalah rentetan "hello", dan itulah ia. Segala-galanya dalam array, dalam pelbagai rentetan kami, masih sampah. Kami telah tidak dimulakan. Katakan kita menolak tali lain ke dalam tindanan kami. Kami akan menolak "dunia" pada masa ini. Jadi anda boleh melihat "dunia" di sini pergi di atas "hello", dan kiraan saiz pergi sehingga 2. Sekarang kita boleh menolak "CS50", dan yang akan pergi di atas sekali lagi. Jika kita kembali, anda boleh melihat bagaimana kita hendak menolak perkara-perkara di atas timbunan. Dan sekarang kita mendapatkan pop. Apabila kita muncul sesuatu yang luar tindanan, apa yang berlaku? Sesiapa melihat perbezaan? Ia cukup halus. [Pelajar] Saiz. >> Yeah, saiz berubah. 

Apa lagi yang anda akan dijangka untuk menukar? [Pelajar] tali, terlalu. >> Hak. Rentetan terlalu. Ia ternyata bahawa apabila anda melakukannya dengan cara ini, kerana kita tidak meniru unsur-unsur ke dalam timbunan kami, kita sebenarnya tidak perlu berbuat apa-apa, kita hanya boleh menggunakan saiz untuk menjejaki beberapa perkara dalam pelbagai kami supaya apabila kita muncul semula, sekali lagi kita hanya penyusutan saiz kami ke 1. Tidak ada keperluan untuk benar-benar pergi dan overwrite apa-apa. Jenis funky. Ia ternyata bahawa kita biasanya hanya meninggalkan perkara sahaja kerana ia adalah kerja yang kurang bagi kita untuk melakukan. Jika kita tidak perlu kembali dan menimpa sesuatu, maka mengapa melakukannya? Jadi apabila kita muncul dua kali off tindanan, semua yang tidak adalah susutan saiz beberapa kali. Dan sekali lagi, ini hanya kerana kita tidak menyalin perkara ke dalam tindanan kami. Ya? Teruskan. [Pelajar, difahami] >> Dan kemudian apa yang berlaku apabila anda menolak sesuatu lagi? Apabila anda menolak sesuatu lagi, di mana ia pergi? Di manakah ia pergi, Basil? >> Ke rentetan [1]? >> Hak. Mengapa tidak pergi ke rentetan [3]? [Basil] Kerana ia terlupa bahawa ada apa-apa dalam rentetan [1] dan [2]? [Hardison] Tepat sekali. Timbunan kami, pada asasnya, "terlupa" bahawa ia telah berpegang kepada apa-apa dalam rentetan [1] atau rentetan [2], jadi apabila kita menolak "woot", ia hanya meletakkan itu ke dalam elemen pada tali [1]. Adakah terdapat apa-apa soalan tentang bagaimana kerja-kerja ini, di peringkat asas? [Sam] Jadi ini tidak dinamik dalam apa jua cara, dari segi jumlah atau dari segi saiz tindanan? [Hardison] Tepat sekali. Ini adalah - titik adalah bahawa ini tidak adalah timbunan yang dinamik growning. Ini adalah timbunan yang boleh memegang, paling, empat char * s, empat perkara-perkara yang paling. Jika kita cuba dan menolak satu perkara yang kelima, apa yang anda fikir patut berlaku? [Pelajar, difahami] [Hardison] Tepat sekali. Terdapat beberapa perkara yang boleh berlaku. Ia mungkin seg bersalah, bergantung kepada apa yang kita - bagaimana sebenarnya kita telah melaksanakan back-end. Ia boleh overwrite. Ia boleh mempunyai bahawa buffer overflow bahawa kita bercakap tentang di dalam kelas. Apa yang akan menjadi perkara yang paling jelas yang mungkin ditindih jika kita cuba untuk menolak satu perkara tambahan pada timbunan kami? Jadi anda menyebut suatu buffer overflow. Apa yang mungkin menjadi perkara yang akan mendapat ditulis atau menghentak-hentak pada jika kita melimpah tidak sengaja dengan cuba untuk menolak satu perkara tambahan? [Daniel, difahami] Kemungkinan >>. Tetapi pada mulanya, apa yang mungkin berlaku? Bagaimana jika kita cuba untuk menolak satu perkara yang keempat? Ia mungkin menimpa saiz, sekurang-kurangnya dengan gambarajah memori ini bahawa kita telah mendapat. 

Dalam spesifikasi set masalah, yang adalah apa yang kita akan melaksanakan hari ini, apa yang kita mahu lakukan hanya kembali palsu. Kaedah menolak kami akan memulangkan nilai boolean, dan bahawa nilai boolean akan menjadi kenyataan jika menolak berjaya dan palsu jika kita tidak boleh menolak apa-apa yang lebih kerana timbunan penuh. Mari berjalan melalui sedikit kod yang sekarang. Berikut adalah fungsi usaha kita. Fungsi push kami untuk timbunan akan mengambil tali untuk meletakkan pada timbunan. Ia akan kembali benar jika rentetan telah berjaya ditolak selainnya timbunan dan palsu. Apa-apa cadangan mengenai apa yang mungkin menjadi perkara yang baik pertama yang perlu dilakukan di sini? [Sam] Jika saiz sama kapasiti kemudian kembali palsu? [Hardison] Bingo. Kerja bagus. Jika saiz kapasiti, kami akan kembali palsu. Kita tidak boleh meletakkan apa-apa yang lebih dalam timbunan kami. Jika tidak, kita mahu meletakkan sesuatu di atas timbunan. Apakah "atas tindanan," pada mulanya? [Daniel] Saiz 0? >> Saiz 0. Apakah atas timbunan selepas ada satu perkara dalam tindanan? Missy, adakah anda tahu? [Missy] Satu. Saiz >> adalah salah, sebenarnya. Anda menyimpan menambah saiz, dan setiap masa anda meletakkan dalam elemen baru pada saiz indeks dalam array. Kita boleh melakukannya dengan jenis yang satu-liner, jika yang masuk akal. Jadi kita telah mendapat pelbagai rentetan kita, kita pergi untuk mengakses pada indeks saiz, dan kami hanya akan menyimpan * char kami di sana. Perhatikan bagaimana tidak ada menyalin rentetan berlaku di sini, tiada peruntukan memori yang dinamik? Dan kemudian Missy dibesarkan apa yang kita perlu lakukan, kerana kita telah disimpan tali di tempat yang sesuai dalam pelbagai, dan dia berkata bahawa kita terpaksa untuk menokokkan saiz oleh salah supaya kita sudah bersedia untuk menolak seterusnya. Jadi kita boleh berbuat demikian dengan s.size + +. Pada ketika ini, kita telah ditolak ke dalam pelbagai kami. Apakah perkara terakhir yang perlu kita lakukan? [Pelajar] Return benar. >> Kembali benar. Jadi ia adalah agak mudah, kod yang agak mudah. Tidak terlalu banyak. Sebaik sahaja anda telah dibalut kepala anda sekitar bagaimana timbunan berfungsi, ini adalah agak mudah untuk melaksanakan. 

Sekarang, bahagian seterusnya ini adalah pop tali kira timbunan. Saya akan memberi anda semua sedikit masa untuk bekerja pada sedikit ini sedikit. Ia hampir asasnya belakang apa yang kita telah dilakukan di sini di tolak. Apa yang saya telah lakukan sebenarnya - oops. Saya telah boot perkakas di sini, dan di dalam perkakas, Saya telah ditarik ke atas masalah menetapkan 5 spesifikasi. Jika kita zoom di sini, kita boleh melihat saya di cdn.cs50.net/2012/fall/psets/pset5.pdf. Pernahkah anda semua turun kod ini yang terletak di sini, section6.zip? Semua hak. Jika anda tidak pernah dilakukan itu, berbuat demikian sekarang, benar-benar cepat. Saya akan melakukannya dalam tetingkap terminal saya. Saya sebenarnya melakukannya di sini. Yeah. Ya, Sam? >> Saya mempunyai soalan tentang kenapa anda mengatakan 's kurungan s.string saiz = str? Apakah str? Apakah yang ditakrifkan tempat sebelum ini, atau - oh, str * char? [Hardison] Ya, betul-betul. Itu adalah hujah. >> Oh, okay. Maaf. [Hardison] Kami menyatakan rentetan untuk menolak masuk Persoalan lain yang mungkin datang bahawa kita tidak benar-benar bercakap tentang di sini adalah kita ambil untuk diberikan bahawa kita mempunyai pembolehubah ini dipanggil s itu adalah dalam skop dan boleh diakses kepada kami. Kami mengambil untuk diberikan bahawa ini struct timbunan. Jadi melihat kembali pada kod ini menolak, anda boleh melihat bahawa kita sedang melakukan barangan dengan rentetan ini yang mendapat diluluskan pada tetapi kemudian tiba-tiba, kita mengakses s.size, seperti, mana s datang dari? Dalam kod yang kita akan melihat dalam arkib seksyen dan kemudian set barangan yang anda akan lakukan dalam masalah anda, kita telah membuat timbunan kami struct pembolehubah global supaya kita boleh mempunyai akses kepada maklumat itu dalam semua fungsi yang berbeza kita tanpa perlu manual lulus di sekeliling dan lulus dengan rujukan, melakukan semua yang jenis barangan. Kami hanya menipu sedikit, jika anda akan, untuk membuat perkara yang lebih bagus. Dan itulah sesuatu yang kita lakukan di sini kerana ia adalah untuk bersenang-senang, ia adalah lebih mudah. Selalunya, anda akan melihat orang melakukan ini jika mereka mempunyai satu struktur data yang besar yang sedang dikendalikan di dalam program mereka. 

Mari kita kembali kepada perkakas. Adakah semua orang berjaya mendapatkan section6.zip? Semua orang unzip ia menggunakan section6.zip unzip? Jika anda pergi ke direktori seksyen 6 - aah, seluruh tempat - dan anda menyenaraikan apa yang di sini, anda melihat bahawa anda telah mendapat tiga berbeza. c fail. Anda telah mendapat giliran, SLL, yang merupakan senarai berseorangan berkaitan, dan timbunan. Jika anda membuka stack.c, anda boleh melihat bahawa kita telah mendapat ini struct ditakrifkan untuk kita, struct tepat bahawa kita hanya bercakap tentang di slaid. Kami telah mendapat pembolehubah global kami untuk timbunan, kita telah mendapat fungsi usaha kita, dan kemudian kita telah mendapat fungsi pop kami. Saya akan meletakkan kod untuk menolak kembali pada slaid di sini, tetapi apa yang saya ingin anda semua untuk melakukan, dengan sedaya upaya anda, pergi dan melaksanakan fungsi pop. Sebaik sahaja anda telah dilaksanakan, anda boleh menyusun ini dengan membuat timbunan, dan kemudian menjalankan executable timbunan yang terhasil, dan yang akan menjalankan semua kod ujian ini turun di sini yang di utama. Utama dan menjaga sebenarnya membuat menolak dan pop panggilan dan memastikan bahawa segala-galanya akan melalui semua betul. Ia juga initializes saiz timbunan di sini jadi anda tidak perlu risau tentang Memulakan bahawa. Anda boleh menganggap bahawa ia telah dimulakan dengan betul oleh masa yang anda mengakses dalam fungsi pop. Adakah yang masuk akal? Jadi di sini kita pergi. Terdapat kod menolak. Saya akan memberikan anda lelaki 5 atau 10 minit. Dan jika anda mempunyai sebarang soalan dalam interim semasa anda pengekodan, sila bertanya kepada mereka dengan kuat. Jadi, jika anda sampai ke titik melekat, hanya meminta. Biar saya tahu, membiarkan orang lain tahu. Bekerja dengan jiran anda juga. [Daniel] Kami hanya melaksanakan pop sekarang? >> Hanya pop. Walaupun anda boleh menyalin pelaksanaan menolak jika anda ingin supaya ujian akan berfungsi. Kerana ia adalah sukar untuk menguji perkara-perkara yang mendapat ke - atau, ia adalah sukar untuk menguji pop perkara daripada timbunan jika tidak ada apa-apa dalam timbunan untuk memulakan dengan. 

Apakah pop sepatutnya kembali? Elemen dari atas timbunan. Ia sepatutnya untuk mendapatkan elemen luar atas timbunan dan kemudian penyusutan saiz tindanan, dan kini anda telah hilang elemen di atas. Dan kemudian anda kembali elemen di atas. [Pelajar, difahami] [Hardison] Jadi apa yang berlaku jika anda berbuat demikian? [Pelajar, difahami] Apa yang akhirnya berlaku adalah anda mungkin mengakses sama ada elemen yang belum dimulakan lagi, jadi pengiraan mana elemen terakhir adalah dimatikan. Jadi di sini, jika anda perasan, di tolak, kita mengakses rentetan pada elemen s.size kerana ia adalah satu indeks baru. Ia adalah atas baru timbunan. Manakala dalam bentuk pop, s.size akan menjadi ruang seterusnya, ruang yang di atas semua elemen dalam timbunan anda. Jadi elemen paling atas tidak di s.size, tetapi sebaliknya, ia adalah di bawahnya. 

Perkara lain yang perlu dilakukan apabila anda - dalam bentuk pop, anda perlu untuk penyusutan saiz. Jika anda ingat kembali kepada gambarajah kecil kami di sini, benar-benar, satu-satunya yang kita lihat berlaku apabila kita dipanggil pop adalah bahawa saiz ini menurun, pertama kepada 2, kemudian kepada 1. Kemudian apabila kita menolak elemen baru pada, ia akan pergi pada tempat yang betul. [Basil] Jika s.size ialah 2, maka tidak akan ia pergi kepada 2 elemen, dan kemudian anda akan mahu pop elemen yang luar? Jadi, jika kita pergi ke - >> Jadi mari kita melihat ini lagi. Jika ini adalah timbunan kami pada ketika ini dan kita panggil pop, di mana indeks adalah elemen yang paling atas? [Basil] Pada 2, tetapi ia akan pop 3. >> Hak. Supaya di mana saiz kami adalah 3, tetapi kita mahu pop elemen pada 2 indeks. Ia adalah yang jenis tipikal off oleh salah satu yang anda perlu dengan pengindeksan sifar tatasusunan. Jadi anda tidak mahu untuk pop elemen ketiga, tetapi elemen ketiga tidak adalah pada indeks 3. Dan sebab kita tidak perlu berbuat demikian 1 tolak apabila kita menolak kerana sekarang, anda dapati bahawa elemen yang paling atas, jika kita menolak sesuatu yang lain ke dalam tindanan pada ketika ini, kita mahu menolak ia pada indeks 3. Dan ia hanya kebetulan bahawa saiz dan indeks beratur apabila anda menolak. 

Siapa yang mendapat timbunan pelaksanaan bekerja? Anda telah mendapat timbunan kerja satu. Adakah anda mempunyai pop bekerja lagi? [Daniel] Ya. Saya fikir begitu. Program >> berjalan dan tidak seg Sesar, ia mencetak? Adakah ia mencetak "kejayaan" apabila anda menjalankan? Yeah. Buat timbunan, jalankan ia, jika ia mencetak keluar "kejayaan" dan tidak pergi ledakan, maka semua baik. Semua hak. Mari kita pergi ke perkakas benar-benar cepat, dan kami akan berjalan melalui ini. Jika kita melihat apa yang berlaku di sini dengan pop, Daniel, apakah perkara pertama yang anda lakukan? [Daniel] Jika s.size adalah lebih besar daripada 0. [Hardison] Okay. Dan kenapa anda berbuat demikian? [Daniel] Untuk memastikan bahawa ada sesuatu di dalam tindanan. [Hardison] Hak. Anda mahu untuk menguji untuk memastikan bahawa s.size adalah lebih besar daripada 0; sebaliknya, apa yang anda mahu telah berlaku? [Daniel] Return batal? >> Kembali null, tepat. Jadi jika s.size adalah lebih besar daripada 0. Maka apa yang kita akan lakukan? Apa yang kami lakukan jika timbunan tidak kosong? [Stella] Anda penyusutan saiz? >> Anda penyusutan saiz, okay. Jadi bagaimana anda berbuat demikian? >> S.size -. [Hardison] Great. Dan kemudian apa yang kamu lakukan? [Stella] Dan kemudian saya berkata pulangan s.string [s.size]. [Hardison] Great. Jika tidak, anda kembali null. Ya, Sam? [Sam] Mengapa ia tidak perlu menjadi s.size + 1? [Hardison] Plus 1? >> Yeah. >> Got ia. [Sam] Saya fikir kerana anda mengambil 1 daripada, maka anda akan kembali tidak satu yang mereka meminta. [Hardison] Dan ini adalah hanya apa yang kita telah bercakap mengenai dengan isu ini keseluruhannya 0 indeks. Jadi jika kita zoom kembali di sini. Jika kita melihat lelaki ini di sini, anda boleh melihat bahawa apabila kita pop, kita muncul unsur pada indeks 2. 

Jadi kita mengurangkan saiz kami terlebih dahulu, maka saiz kami sepadan dengan indeks kami. Jika kita tidak penyusutan saiz pertama, maka kita perlu lakukan saiz -1 dan kemudian susutan. Besar. Semua yang baik? Sebarang pertanyaan mengenai perkara ini? Terdapat beberapa cara yang berbeza untuk menulis ini juga. Malah, kita boleh melakukan sesuatu yang - kita boleh melakukan satu-liner. Kita boleh melakukan pulangan satu line. Jadi, kita sebenarnya boleh SUSUTAN sebelum kita kembali dengan berbuat demikian. Jadi meletakkan - sebelum s.size. Itu menjadikan garis benar-benar padat. Jika perbezaan antara - saiz s dan s.size - adalah bahawa ini Postfix - mereka memanggilnya Postfix kerana datang selepas s.size - bermakna bahawa s.size dinilai bagi maksud mencari indeks kerana ia ketika apabila garis ini dilaksanakan, dan kemudian ini - berlaku selepas baris mendapat dilaksanakan. Selepas elemen di s.size index diakses. Dan itu bukan apa yang kita mahu, kerana kita mahu susutan berlaku dahulu. Yang Othewise, kita akan mengakses array, berkesan, di luar batas. Kami akan mengakses elemen di atas satu bahawa kita benar-benar mahu untuk mengakses. Ya, Sam? >> Adakah ia lebih cepat atau menggunakan RAM yang kurang untuk membuat dalam satu baris atau tidak? [Hardison] Secara jujur, ia benar-benar bergantung. [Sam, difahami] >> Ya, ia bergantung. Anda boleh melakukan helah pengkompil untuk mendapatkan pengkompil untuk menyedari bahawa, biasanya, saya bayangkan. 

Jadi kita telah sebutkan sedikit tentang barangan ini pengoptimuman pengkompil yang boleh anda lakukan dalam menyusun, dan itulah jenis perkara yang pengkompil mungkin dapat memikirkan, seperti oh, hey, mungkin saya boleh lakukan ini semua dalam satu operasi, berbanding memuatkan pembolehubah saiz dari RAM, decrementing, menyimpan ia kembali keluar, dan kemudian memuatkan kembali semula untuk memproses seluruh operasi ini. Tetapi biasanya, tidak, ini tidak adalah jenis perkara yang akan membuat program anda dengan ketara lebih cepat. Sebarang pertanyaan lanjut mengenai susunan? 

Jadi menolak dan pop. Jika kalian mahu mencuba edisi hacker, apa yang kita lakukan dalam edisi penggodam sebenarnya pergi dan membuat timbunan ini berkembang dinamik. Cabaran terutamanya terdapat di sini dalam fungsi tolak, untuk memikirkan bagaimana untuk membuat pelbagai yang tumbuh sebagai anda menyimpan menolak lebih banyak unsur-unsur ke timbunan. Ia sebenarnya tidak terlalu banyak kod tambahan. Hanya panggilan - anda perlu ingat untuk mendapatkan panggilan ke malloc di sana dengan betul, dan kemudian memikirkan apabila anda pergi untuk memanggil realloc. Itulah cabaran yang menyeronokkan jika anda berminat. 

Tetapi buat masa ini, mari kita beralih, dan mari kita bercakap tentang beratur. Tatal melalui sini. Beratur adalah adik-beradik rapat timbunan. Jadi dalam tindanan, perkara-perkara yang telah dimasukkan ke dalam lepas adalah perkara pertama yang kemudian diubah. Kami telah mendapat ini terakhir dalam, mula-mula keluar, atau LIFO, pesanan. Manakala dalam barisan, seperti yang anda harapkan daripada apabila anda berdiri di barisan, orang pertama untuk mendapatkan dalam talian, perkara pertama untuk masuk ke dalam barisan, adalah perkara pertama yang mendapat diambil dari barisan. Beratur juga sering digunakan apabila kita berurusan dengan graf, seperti yang kita bercakap tentang secara ringkas dengan susunan, dan barisan juga berguna untuk sekumpulan perkara-perkara lain. Salah satu perkara yang datang sehingga sering cuba untuk mengekalkan, sebagai contoh, senarai disusun unsur. Dan anda boleh melakukan ini dengan pelbagai. Anda boleh mengekalkan senarai yang disusun perkara dalam pelbagai, tetapi di mana yang mendapat sukar maka anda sentiasa perlu mencari tempat yang sesuai untuk memasukkan perkara yang akan datang. Jadi jika anda mempunyai pelbagai nombor, 1 hingga 10, dan kemudian anda mahu untuk mengembangkan bahawa kepada semua nombor 1 melalui 100, dan anda mendapat nombor-nombor dalam susunan rawak dan cuba untuk memastikan segala-galanya disusun seperti anda pergi melalui, anda akhirnya perlu melakukan banyak berubah. Dengan jenis tertentu beratur dan jenis tertentu struktur data asas, anda sebenarnya boleh menyimpan ia agak mudah. Anda tidak perlu untuk menambah sesuatu dan kemudian rombakan keseluruhan perkara setiap kali. Nor adakah anda mempunyai untuk melakukan banyak peralihan unsur-unsur dalaman sekitar. Apabila kita melihat barisan, anda melihat bahawa - juga di queue.c kod seksyen - struct bahawa kita telah diberikan anda adalah benar-benar serupa dengan struct bahawa kita memberikan anda untuk timbunan. 

Terdapat satu pengecualian ini, dan bahawa satu pengecualian adalah bahawa kita ini integer tambahan dipanggil kepala, dan ketua di sini adalah untuk mengesan kepala barisan, atau elemen pertama dalam barisan. Dengan timbunan, kita dapat menjejaki elemen yang kita kira-kira untuk mendapatkan, atau atas tindanan, dengan hanya menggunakan saiz, sedangkan dengan barisan, kita perlu untuk berurusan dengan hujung yang bertentangan. Kami cuba untuk jelujur perkara di akhir, tetapi kemudian kembali perkara-perkara dari hadapan. Jadi dengan berkesan, dengan kepala, kita mempunyai indeks permulaan barisan, dan saiz memberikan kita indeks akhir barisan supaya kita boleh mengambil perkara-perkara dari kepala dan menambah perkara yang ke ekor. Manakala dengan timbunan, kita hanya pernah berurusan dengan bahagian atas tindanan. Kami tidak pernah mempunyai untuk mengakses bawah timbunan. Kami hanya menambah perkara ke atas dan mengambil sesuatu di luar bahagian atas jadi kita tidak perlu bahawa bidang tambahan di dalam struct kami. Adakah yang biasanya masuk akal? Semua hak. Ya, Charlotte? [Charlotte, difahami] [Hardison] Itulah persoalan yang besar, dan yang merupakan salah satu yang datang dalam syarahan. Mungkin berjalan melalui beberapa contoh akan menggambarkan mengapa kita tidak mahu menggunakan rentetan [0] sebagai ketua barisan. 

Jadi bayangkan bahawa kita mempunyai barisan kita, kita akan memanggilnya beratur. Pada mulanya, apabila kita baru sahaja instantiated, apabila kita baru sahaja diisytiharkan, kita telah tidak dimulakan apa-apa. Ia adalah semua sampah. Jadi, sudah tentu kita mahu pastikan bahawa kita memulakan kedua-dua saiz dan bidang kepala menjadi 0, sesuatu yang munasabah. Kita juga boleh pergi ke hadapan dan menyeimbangkan unsur-unsur dalam barisan kita. Dan untuk membuat ini patut gambarajah, notis bahawa kini giliran kami hanya boleh memegang tiga elemen; manakala timbunan kami boleh memegang empat, barisan kami hanya boleh memegang tiga. Dan itu hanya untuk membuat patut gambarajah. Perkara pertama yang berlaku di sini ialah kita enqueue string "hi". Dan seperti yang kita lakukan dengan timbunan, tiada apa yang sangat berbeza di sini, kita buang tali di tali [0] dan kenaikan saiz kami dengan 1. Kami enqueue "bye", ia mendapat diletakkan di atas. Jadi ini kelihatan seperti timbunan untuk sebahagian besar. Kami bermula di sini, elemen baru, elemen baru, saiz terus naik. Apa yang berlaku pada ketika ini apabila kita hendak dequeue sesuatu? Apabila kita ingin dequeue, yang merupakan elemen yang kita mahu dequeue? [Basil] Rentetan [0]. >> Zero. Tepat betul, Basil. Kami mahu menghilangkan rentetan pertama, yang satu ini, "hi". Jadi apa perkara lain yang berubah? Notis apabila kita muncul sesuatu yang luar tindanan, kita hanya mengubah saiz, tetapi di sini, kita telah mendapat beberapa perkara bahawa perubahan. Bukan sahaja melakukan perubahan saiz, tetapi perubahan kepala. Ini akan kembali ke titik awal Charlotte: mengapa kita perlu kepala ini serta? Adakah masuk akal sekarang, Charlotte? Jenis >>. [Hardison] Jenis? Jadi apa yang berlaku apabila kita dequeued? Apa yang kepala lakukan yang kini menarik? [Charlotte] Oh, kerana ia berubah - okay. Saya lihat. Kerana ketua - mana kepala menunjuk kepada perubahan dari segi lokasi. Ia tidak lagi sentiasa satu indeks sifar. >> Yeah, tepat. Apa yang berlaku ialah jika dequeueing elemen yang tinggi telah dilakukan dan kita tidak mempunyai bidang ini kepala kerana kita selalu memanggil rentetan ini pada 0 indeks kepala barisan kita, maka kita akan perlu untuk beralih seluruh barisan ke bawah. Kami akan perlu untuk beralih "bye" dari rentetan [1] kepada rentetan [0]. Dan rentetan [2] turun ke rentetan [1]. Dan kita akan mempunyai untuk melakukan ini untuk senarai keseluruhan unsur, pelbagai keseluruhan unsur. Dan apabila kita melakukan ini dengan pelbagai, yang mendapat benar-benar mahal. Jadi di sini, ia bukan masalah besar. Kami hanya mempunyai tiga elemen dalam pelbagai kami. Tetapi jika kita mempunyai giliran seribu elemen atau satu juta elemen, dan kemudian tiba-tiba, kami mula membuat sekumpulan dequeue panggilan semua dalam gelung, perkara-perkara yang benar-benar akan melambatkan kerana ia perubahan segala-galanya di bawah sentiasa. Anda tahu, beralih sebanyak 1, peralihan anjakan sebanyak 1, oleh 1, anjakan sebanyak 1. Sebaliknya, kita menggunakan kepala ini, kita panggil ia "penunjuk" walaupun ia tidak benar-benar penunjuk dalam erti kata yang ketat, ia bukan sejenis penunjuk. Ia bukan satu * int atau * char atau apa-apa seperti itu. Tetapi ia menunjuk atau menunjukkan kepala barisan kita. Yeah? 

[Pelajar] Bagaimanakah dequeue tahu hanya minggat apa yang ada di kepala? [Hardison] Bagaimanakah dequeue tahu bagaimana untuk minggat apa yang di kepala? >> Hak, yeah. >> Apakah ia melihat hanya apa jua bidang kepala ditetapkan. Jadi dalam kes ini pertama, jika kita lihat di sini, kepala kita adalah 0, Isi 0. >> Hak. [Hardison] Jadi ia hanya berkata okay, baik, unsur pada indeks 0, string "hi", adalah elemen di kepala barisan kita. Jadi kita akan untuk dequeue lelaki itu. Dan yang akan menjadi elemen yang akan dikembalikan kepada pemanggil. Ya, Saad? >> Jadi kepala pada dasarnya menetapkan - ke mana anda hendak pergi kepada indeks ia? Itulah permulaan ia? >> Yeah. >> Okay. [Hardison] Itulah menjadi permulaan baru untuk pelbagai kami. Jadi apabila anda dequeue sesuatu, semua yang anda perlu lakukan adalah mengakses elemen di index q.head, dan yang akan menjadi elemen yang anda mahu dequeue. Anda juga perlu penyusutan saiz. Kita akan melihat dalam sedikit di mana perkara mendapatkan sedikit rumit dengan ini. Kami dequeue, dan kini, jika kita enqueue lagi, di mana kita enqueue? Di manakah elemen seterusnya pergi dalam barisan kami? Katakanlah kita mahu enqueue rentetan "CS". Ke indeks mana ia akan pergi? [Pelajar] Rentetan [2]. >> Dua. Mengapa 2 dan tidak 0? [Basil] Kerana kini kepala adalah 1, maka itulah seperti permulaan senarai? [Hardison] Hak. Dan apa yang menandakan akhir senarai? Apa yang kita menggunakan untuk menandakan akhir barisan kita? Kepala adalah ketua barisan kita, permulaan barisan kita. Apakah akhir barisan kita? [Pelajar] Saiz. >> Saiz, tepat. Jadi elemen baru kami pergi pada saiz, dan elemen-elemen yang kita mengambil off terkeluar di kepala. Apabila kita enqueue elemen seterusnya, kami meletakkan ia di saiz. [Pelajar] Sebelum anda meletakkan bahawa walaupun saiz adalah 1, betul-betul? [Hardison] Hak. Jadi tidak cukup pada saiz. Saiz +, tidak +1, tetapi kepala +. Kerana kita beralih segala-galanya dengan jumlah kepala. Jadi di sini, kini kita telah mendapat giliran saiz 1 yang bermula pada indeks 1. Ekor adalah indeks 2. Ya? 

[Pelajar] Apa yang berlaku apabila anda dequeue rentetan [0], dan slot tali 'dalam ingatan hanya mendapat dikosongkan, pada dasarnya, atau hanya dilupakan? [Hardison] Yeah. Dalam pengertian ini, kami hanya melupakan mereka. Jika kita telah menyimpan salinan mereka untuk - banyak struktur data selalunya akan menyimpan salinan mereka sendiri unsur-unsur supaya orang yang menguruskan struktur data tidak perlu bimbang kira-kira di mana semua orang penunjuk akan. Struktur data memegang kepada segala-galanya, memegang kepada semua salinan, untuk memastikan bahawa segala-galanya berterusan sewajarnya. Walau bagaimanapun, dalam kes ini, struktur data adil, kesederhanaan, tidak membuat salinan apa-apa yang kita sedang menyimpan di dalamnya. [Pelajar] Jadi ini pelbagai berterusan? >> Ya. Jika kita melihat kembali apa definisi adalah struktur ini, ia adalah. Ia hanya pelbagai standard seperti anda telah melihat, pelbagai char * s. Adakah itu? >> Ya, saya hanya tertanya-tanya jika anda akhirnya akan kehabisan memori, sehingga ke tahap tertentu, jika anda mempunyai semua tempat kosong dalam pelbagai anda? [Hardison] Ya, itu adalah satu titik yang baik. 

Jika kita melihat apa yang berlaku sekarang pada ketika ini, kita telah dipenuhi barisan kami, ia kelihatan seperti. Tetapi kita tidak benar-benar dipenuhi barisan kita kerana kita mempunyai barisan yang saiz 2, tetapi ia bermula pada indeks 1, kerana itulah di mana penunjuk kepala kita. Seperti anda berkata, bahawa elemen pada rentetan [0], pada indeks 0, tidak benar-benar ada. Ia bukan dalam barisan kita lagi. Kami hanya tidak mengganggu untuk masuk dan overwrite ia apabila kita dequeued. Jadi, walaupun ia kelihatan seperti kita telah kehabisan memori, kita benar-benar tidak mempunyai. Itu spot adalah disediakan untuk kita gunakan. Tingkah laku yang sesuai, jika kita mencuba dan pertama dequeue sesuatu suka "bye", yang akan pop bye off. Sekarang giliran kami bermula pada indeks 2 dan adalah daripada 1 saiz. Dan sekarang jika kita cuba dan enqueue sesuatu lagi, katakan 50, 50 perlu pergi di tempat ini pada indeks 0 kerana ia masih boleh didapati untuk kita. Ya, Saad? [Saad] Adakah yang berlaku secara automatik? [Hardison] Ia tidak berlaku agak secara automatik. Anda perlu lakukan matematik untuk membuat ia bekerja, tetapi pada dasarnya apa yang kami lakukan adalah kita telah hanya dibalut di sekeliling. [Saad] Dan ia mengapa jika ini mempunyai lubang di tengah-tengah itu? [Hardison] Ia adalah jika kita boleh membuat matematik bersenam betul. 

Dan ternyata bahawa sebenarnya tidak begitu sukar untuk dilakukan dengan operator arena. Jadi seperti yang kita lakukan dengan Caesar dan barangan kripto, menggunakan arena, kita boleh mendapatkan perkara untuk membalut di sekitar dan terus pergi sekitar dan di sekeliling dan sekitar dengan barisan kita, memastikan bahawa penunjuk kepala bergerak. Notis saiz yang sentiasa menghormati bilangan unsur sebenarnya dalam barisan. Dan ia hanya penunjuk kepala yang menyimpan berbasikal melalui. Jika kita melihat apa yang berlaku di sini, jika kita kembali ke permulaan, dan anda hanya menonton apa yang berlaku kepada kepala apabila kita enqueue sesuatu, tiada apa yang berlaku kepada ketua. Apabila kita enqueued sesuatu yang lain, tiada apa yang berlaku kepada ketua. Secepat kita dequeued sesuatu, kepala naik demi satu. Kami enqueued sesuatu, tiada apa yang berlaku kepada ketua. Apabila kita dequeue sesuatu, tiba-tiba kepala mendapat incremented. Apabila kita enqueue sesuatu, tiada apa yang berlaku kepada ketua. 

Apa yang akan berlaku pada ketika ini jika kita dequeue sesuatu lagi? Mana-mana pemikiran? Apa yang akan berlaku kepada kepala? Apa yang sepatutnya berlaku kepada kepala jika kita untuk dequeue sesuatu yang lain? Kepala sekarang adalah pada 2 indeks, yang bermaksud bahawa kepala barisan adalah rentetan [2]. [Pelajar] Yang mengembalikan 0? >> Ia harus kembali kepada 0. Ia harus membalut kembali sekitar, betul-betul. Setakat ini, setiap kali kita dipanggil dequeue, kami telah menambah satu ke kepala, menambah satu ke kepala, menambah satu ke kepala, menambah satu ke kepala. Secepat bahawa penunjuk kepala mendapat indeks terakhir dalam pelbagai kami, maka kita perlu untuk membalut kembali sekitar ke permulaan, kembali kepada 0. [Charlotte] Apa yang menentukan kapasiti beratur dalam timbunan? [Hardison] Dalam kes ini, kita baru sahaja telah menggunakan malar # ditakrifkan. >> Okay. [Hardison] Dalam fail sebenar c, anda boleh pergi di dalam dan kotoran sedikit dan menjadikan ia sebagai besar atau sesedikit yang anda mahu. [Charlotte] Jadi apabila anda membuat barisan, bagaimana anda membuat komputer tahu berapa besar anda mahu timbunan untuk menjadi? [Hardison] Itulah persoalan yang besar. Terdapat beberapa cara. Salah satu adalah untuk hanya menentukan ia di depan dan mengatakan ini akan menjadi barisan yang mempunyai 4 elemen atau 50 elemen atau 10,000. Cara yang lain adalah untuk melakukan apa yang orang edisi penggodam melakukan dan mewujudkan fungsi untuk mempunyai baris gilir anda berkembang dinamik kerana lebih banyak perkara ditambah masuk 

[Charlotte] Jadi untuk pergi dengan pilihan pertama, Bagaimana sintaks anda menggunakan untuk memberitahu program apa saiz barisan? [Hardison] Ah. Jadi mari kita keluar dari ini. Saya masih dalam stack.c sini, jadi saya hanya akan untuk menatal ke atas di sini. Bolehkah anda melihat hak ini di sini? Ini adalah # menentukan kapasiti 10. Dan ini adalah hampir sintaks tepat sama bahawa kita perlu untuk beratur. Kecuali dalam barisan, kita telah mendapat bahawa bidang struct tambahan di sini. [Charlotte] Oh, saya fikir keupayaan bermakna kapasiti untuk tali. [Hardison] Ah. >> Bahawa ia adalah panjang maksimum perkataan. >> Got ia. Yeah. Kapasiti di sini - bahawa adalah titik yang besar. Dan ini adalah sesuatu yang sukar kerana apa yang kita telah diisytiharkan di sini adalah pelbagai char * s. Pelbagai petunjuk. Ini adalah pelbagai aksara. Ini mungkin apa yang anda lihat apabila anda telah mengisytiharkan penampan anda untuk fail I / O, apabila anda telah mewujudkan rentetan manual pada timbunan. Walau bagaimanapun, apa yang kita telah mendapat di sini adalah pelbagai char * s. Jadi ia adalah pelbagai petunjuk. Sebenarnya, jika kita zum keluar dan kita melihat apa yang berlaku di sini dalam persembahan, anda lihat bahawa elemen sebenar, data watak tidak disimpan dalam array sendiri. Apa yang disimpan dalam pelbagai kami di sini adalah petunjuk untuk data watak. Okay. Jadi kita telah melihat bagaimana saiz barisan hanya suka dengan timbunan, saiz sentiasa menghormati bilangan unsur dalam barisan. Selepas membuat 2 enqueues, saiz ialah 2. Selepas membuat dequeue saiz kini 1. Selepas membuat enqueue lain saiz kembali sehingga 2. Jadi saiz pasti menghormati bilangan unsur dalam barisan, dan kemudian kepala hanya menyimpan berbasikal. Ia pergi dari 0-1-2, 0-1-2, 0-1-2. Dan setiap kali kita panggil dequeue, penunjuk kepala mendapat incremented ke indeks seterusnya. Dan jika kepala adalah kira-kira untuk pergi ke, ia gelung kembali sekitar kepada 0. Maka dengan itu, kita boleh menulis fungsi dequeue. Dan kami akan meninggalkan fungsi enqueue untuk anda semua untuk melaksanakan dan bukannya. 

Apabila kita dequeue elemen keluar barisan kita, apakah perkara pertama yang Daniel lakukan apabila kita mula menulis fungsi pop untuk susunan? Biar saya mendengar dari seseorang yang telah tidak bercakap lagi. Mari kita lihat, Saad, adakah anda ingat apa yang Daniel lakukan sebagai perkara yang pertama apabila dia menulis pop? [Saad] Terdapat, ia adalah - >> Beliau diuji untuk sesuatu. [Saad] Jika saiz adalah lebih besar daripada 0. >> Tepat sekali. Dan apa yang adalah bahawa ujian untuk? [Saad] Itu adalah ujian untuk melihat jika terdapat apa-apa yang di dalam array. [Hardison] Yeah. Tepat sekali. Jadi anda tidak boleh pop apa-apa daripada timbunan jika ia adalah kosong. Begitu juga, anda tidak boleh dequeue apa-apa daripada barisan jika ia kosong. Apakah perkara pertama yang kita harus lakukan dalam fungsi dequeue kami di sini, adakah anda fikir? [Saad] Jika saiz adalah lebih besar daripada 0? >> Yeah. Dalam kes ini, saya sebenarnya hanya diuji untuk melihat jika ia adalah 0. Jika ia adalah 0, kita boleh kembali null. Tetapi logik yang sama yang tepat. Dan mari kita terus dengan ini. Jika saiz tidak adalah 0, di mana adalah elemen yang kita mahu dequeue? [Saad] Di kepala? >> Tepat sekali. Kami hanya boleh tarik keluar elemen pertama dalam barisan kita dengan mengakses unsur di kepala. Tiada apa-apa gila. Selepas itu, apa yang patut kita buat? Apa yang telah berlaku? Apakah perkara lain yang kita bercakap tentang di dequeue? Dua perkara perlu berlaku, kerana barisan kita telah berubah. [Daniel] Kurangkan saiz. >> Kami mempunyai untuk mengurangkan saiz, dan meningkatkan kepala? Tepat sekali. Untuk meningkatkan kepala, kita tidak boleh hanya membuta tuli meningkatkan kepala, ingat. Kita tidak boleh hanya melakukan queue.head + +. Kita juga perlu termasuk arena ini oleh kapasiti. Dan mengapa kita MOD oleh kapasiti, Stella? [Stella] Kerana ia mempunyai untuk membalut sekitar. >> Tepat sekali. Kami arena oleh kapasiti kerana ia mempunyai untuk membalut kembali sekitar kepada 0. Jadi sekarang, pada ketika ini, kita boleh melakukan apa yang Daniel berkata. Kita boleh penyusutan saiz. Dan kemudian kita hanya boleh mengembalikan elemen yang berada di atas barisan. Ia kelihatan jenis monggol pada mulanya. Anda mungkin mempunyai soalan. Maaf? 

[Sam] Mengapa pertama di atas barisan? Di manakah yang pergi? [Hardison] Ia datang dari baris keempat dari bawah. Selepas kita menguji untuk memastikan bahawa barisan kita tidak kosong, kita tarik keluar * char pertama, kita tarik keluar elemen yang duduk di indeks kepala array kami, pelbagai rentetan >> kami, dan panggilan yang pertama? [Hardison] Dan kita memanggilnya pertama. Yeah. Hanya untuk susulan pada itu, mengapa anda fikir kita terpaksa untuk berbuat demikian? [Sam] Setiap pertama hanya kembali q.strings [q.head]? >> Yeah. >> Kerana kita lakukan ini berubah q.head itu dengan fungsi arena, dan tidak ada cara untuk melakukannya dalam talian kembali juga. [Hardison] Tepat sekali. Anda tempat di. Sam benar-benar tempat di. Sebab kita terpaksa tarik keluar elemen pertama dalam barisan kita dan menyimpannya ke dalam sebuah pembolehubah adalah kerana baris ini di mana kita telah hanya q.head, ada pengendali arena di sana bukan sesuatu yang boleh kita lakukan dan ia telah mengambil kesan ke atas kepala tanpa - dalam satu baris. Jadi kita sebenarnya mempunyai untuk menarik keluar elemen pertama, kemudian laraskan kepala, melaraskan saiz, dan kemudian kembali elemen yang kita ditarik keluar. Dan ini adalah sesuatu yang kita akan lihat datang kemudian dengan dikaitkan senarai, seperti yang kita bermain-main dengan mereka. Selalunya apabila anda membebaskan atau melupuskan senarai yang dipautkan anda perlu ingat elemen seterusnya, penunjuk seterusnya senarai berkaitan sebelum melupuskan semasa. Kerana jika tidak, anda buang maklumat apa yang ditinggalkan dalam senarai. Sekarang, jika anda pergi ke perkakas anda, anda membuka queue.c-x daripada ini. Jadi jika saya membuka queue.c, izinkan saya zum di sini, anda akan melihat bahawa anda mempunyai fail yang sama-cari. -Cari fail yang serupa dengan apa yang kita telah awal dengan stack.c. Kami telah mendapat struct kami untuk beratur ditakrifkan hanya seperti yang kita lihat pada slaid. 

Kami mempunyai fungsi enqueue kami yang adalah untuk anda lakukan. Dan kita mempunyai fungsi dequeue sini. Fungsi dequeue dalam fail tidak disediakan, tetapi saya akan meletakkan ia kembali pada PowerPoint supaya anda boleh menaip dalam, jika anda ingin. Jadi untuk 5 minit akan datang atau lebih, anda semua bekerja pada enqueue yang hampir hanya bertentangan dequeue. Anda tidak perlu untuk menyesuaikan kepala apabila anda enqueueing, tetapi apa yang anda perlu untuk menyesuaikan diri? Saiz. Jadi, apabila anda enqueue, kepala kekal tidak disentuh, saiz mendapat berubah. Tetapi ia mengambil sedikit - anda akan mempunyai untuk bermain-main dengan arena yang untuk mengetahui dengan tepat apa indeks elemen baru perlu dimasukkan di. Jadi, saya akan memberikan anda semua sedikit, letakkan dequeue kembali pada slaid, dan kerana anda semua mempunyai soalan, menjerit mereka keluar supaya kita dapat semua bercakap tentang mereka sebagai satu kumpulan. Juga, dengan saiz anda Don 't - apabila anda menyesuaikan saiz, anda boleh sentiasa hanya - adakah anda mempunyai MOD saiz pernah? [Daniel] No >> Anda tidak perlu untuk MOD saiz, betul. Kerana saiz akan sentiasa, jika you're - menganggap anda menguruskan perkara sewajarnya, saiz akan sentiasa menjadi antara 0 dan 3. Di manakah anda perlu MOD apabila anda melakukan enqueue? [Pelajar] Hanya untuk kepala. >> Hanya untuk kepala, sebenarnya. Dan mengapa anda perlu MOD pada semua dalam enqueue? Bilakah adalah satu keadaan di mana anda akan perlu arena? [Pelajar] Jika anda mempunyai barangan di kawasan, seperti pada ruangan 1 dan 2, dan kemudian anda perlu menambah sesuatu pada 0. [Hardison] Yeah, tepat. Jadi jika penunjuk kepala anda adalah pada akhir sangat, atau jika saiz anda ditambah kepala anda adalah lebih besar, atau sebaliknya, akan membalut di sekitar barisan. 

Jadi dalam keadaan ini bahawa kita telah mendapat di sini pada slaid sekarang, jika saya mahu untuk enqueue sesuatu sekarang, kita mahu untuk enqueue sesuatu pada indeks 0. Jadi, jika anda melihat di mana 50 pergi, dan saya panggil enqueue 50, ia pergi bawah sana di bawah. Ia pergi di titik 0 indeks. Ia menggantikan 'hi' yang sudah dequeued. [Daniel] Jangan anda mengambil penjagaan yang pada dequeue sudah? Mengapa ia melakukan apa-apa dengan kepala di enqueue? [Hardison] Oh, jadi anda tidak mengubah kepala, maaf. Tetapi anda perlu menggunakan pengendali arena apabila anda mengakses elemen yang anda mahu untuk enqueue apabila anda mengakses Elemen seterusnya dalam baris gilir anda. [Basil] saya tidak berbuat demikian, dan saya mendapat "kejayaan" di sana. [Daniel] Oh, saya faham apa yang anda katakan. [Hardison] Jadi anda didn't - anda hanya lakukan di q.size? [Basil] Yeah. Saya hanya berubah pihak, saya tidak berbuat apa-apa dengan kepala. [Hardison] Anda tidak benar-benar mempunyai untuk menetapkan semula kepala untuk menjadi apa-apa, tetapi apabila anda indeks ke pelbagai rentetan, anda sebenarnya perlu pergi ke hadapan dan mengira di mana elemen seterusnya, kerana withe timbunan, Elemen seterusnya dalam timbunan anda sentiasa pada indeks sepadan dengan saiz. Jika kita melihat kembali pada fungsi menolak timbunan kami, kita sentiasa boleh memetik dalam elemen baru kami betul-betul pada saiz indeks. Manakala dengan barisan, kita tidak boleh berbuat demikian kerana jika kita berada di situasi ini, jika kita enqueued 50 rentetan baru kami akan pergi tepat pada rentetan [1] yang kita tidak mahu lakukan. Kami mahu mempunyai rentetan baru pergi pada indeks 0. 

Sesiapa Adakah - ya? [Pelajar] Saya mempunyai satu soalan tetapi ia tidak benar-benar berkaitan. Apa maknanya apabila seseorang hanya memerlukan sesuatu seperti penunjuk Pred? Apakah nama yang singkat? Saya tahu ia adalah sekadar nama. [Hardison] penunjuk Pred? Mari kita lihat. Dalam konteks apa? [Pelajar] Ia adalah untuk memasukkan. Saya boleh meminta anda kemudian jika anda mahu kerana ia tidak benar-benar berkaitan, tetapi saya hanya - [Hardison] Dari memasukkan kod Daud dari kuliah? Kita boleh tarik bahawa bangun dan bercakap tentang itu. Kami akan bercakap tentang yang seterusnya, sebaik sahaja kami sampai ke senarai berkaitan. 

Jadi mari kita benar-benar cepat melihat apa fungsi enqueue kelihatan seperti. Apakah perkara pertama yang orang cuba untuk melakukan selaras enqueue anda? Ke dalam barisan ini? Serupa dengan apa yang anda lakukan untuk menolak timbunan. Apa yang anda lakukan, Stella? [Stella, difahami] [Hardison] Tepat sekali. Jika (q.size KEUPAYAAN ==) - Saya perlu meletakkan pendakap saya di tempat yang betul - kembali palsu. Zum ke dalam sedikit. Okay. Sekarang apa perkara yang akan datang yang kita terpaksa lakukan? Sama seperti dengan timbunan, dan dimasukkan di tempat yang betul. Dan jadi apa adalah tempat yang tepat untuk memasukkan bahawa? Dengan timbunan ia adalah saiz indeks, dengan ini ia tidak cukup bahawa. [Daniel] Saya mempunyai q.head atau - >> q.strings? >> Yeah. q.strings [q.head + q.size arena KEUPAYAAN]? [Hardison] Kita mungkin mahu untuk meletakkan kurungan sekitar ini supaya kita mendapat keutamaan yang sesuai dan sebagainya yang cleart kepada semua orang. Dan menetapkan yang sama? >> Str? >> Kepada str. Besar. Dan kini apa yang perkara terakhir yang perlu kita lakukan? Sama seperti kita lakukan dalam tindanan. >> Kenaikan saiz? >> Kenaikan saiz. Ledakan. Dan kemudian, sejak kod starter baru sahaja pulang palsu secara lalai, kita ingin menukar ini kepada true jika semua berjalan melalui dan semua berjalan lancar. Semua hak. Itulah banyak maklumat untuk seksyen. Kita tidak berada agak lebih. Kita mahu bercakap benar-benar cepat mengenai senarai berseorangan berkaitan. Saya akan meletakkan ini supaya kita boleh kembali kemudian. Tetapi mari kita kembali kepada persembahan kami untuk hanya beberapa slaid. Jadi enqueue adalah TODO, sekarang kita telah melakukannya. 

Sekarang mari kita lihat pada senarai secara tunggal berkaitan. Kita bercakap mengenai lebih sedikit dalam kuliah. Berapa ramai daripada anda semua melihat demo di mana kita mempunyai orang canggung menunjuk kepada setiap nombor lain dan pegangan? >> Saya di bahawa. >> Apa yang anda semua berfikir? Lakukan itu, diharapkan demystify ini sedikit? Dengan senarai, ia ternyata bahawa kita berurusan dengan jenis ini yang kita akan memanggil nod. Manakala dengan beratur dan timbunan kita terpaksa structs bahawa kita akan memanggil beratur dalam timbunan, kita terpaksa ini barisan baru dalam jenis timbunan, di sini senarai benar-benar hanya terdiri sekumpulan nod. Dengan cara yang sama bahawa rentetan adalah hanya sekumpulan aksara semua berbaris bersebelahan antara satu sama lain. Satu senarai yang dikaitkan hanya nod dan nod yang lain dan satu lagi nod dan nod yang lain. Dan bukannya memecahkan semua nod bersama-sama dan menyimpan mereka contiguously semua betul-betul bersebelahan antara satu sama lain dalam ingatan, ini penunjuk seterusnya membolehkan kita untuk menyimpan nod di mana-mana, secara rawak. Dan kemudian jenis wayar mereka semua bersama-sama untuk menunjukkan dari satu kepada yang seterusnya. 

Dan apakah kelebihan besar bahawa ini mempunyai lebih array? Atas segala-galanya menyimpan contiguously hanya terperangkap bersebelahan antara satu sama lain? Anda ingat? Yeah? >> Peruntukan memori Dinamik? >> Memori peruntukan Dinamik dalam apa rasa? [Pelajar] Dalam bahawa anda boleh menyimpan menjadikan ia lebih besar dan anda tidak perlu untuk menggerakkan pelbagai keseluruhan anda? [Hardison] Tepat sekali. Jadi dengan array, apabila anda mahu untuk meletakkan elemen baru ke tengah-tengah itu, anda perlu beralih segala-galanya untuk membuat ruang. Dan seperti yang kita bercakap tentang dengan barisan, itulah sebabnya kita memastikan bahawa penunjuk kepala, supaya kita tidak sentiasa berubah perkara-perkara. Kerana yang mendapat mahal jika anda telah mendapat pelbagai besar dan anda sentiasa melakukan ini sisipan rawak. Manakala dengan senarai, semua yang anda perlu lakukan adalah membuang ia pada nod baru, menyesuaikan petunjuk, dan anda selesai. Apa yang menghisap tentang perkara ini? Selain daripada fakta bahawa ia tidak mudah untuk bekerja dengan sebagai array? Yeah? [Daniel] Well, saya rasa ia adalah lebih sukar untuk mengakses elemen tertentu dalam senarai dikaitkan? [Hardison] Anda tidak boleh hanya melompat kepada elemen sewenang-wenangnya di tengah-tengah senarai dikaitkan anda. Bagaimana anda perlu lakukan ia sebaliknya? >> Anda perlu melangkah melalui perkara keseluruhan. [Hardison] Yeah. Anda perlu pergi melalui satu pada satu-satu masa, pada satu masa. Ia adalah besar - ia sakit. Apa yang lain - ada lagi kejatuhan ini. [Basil] Anda tidak boleh pergi ke hadapan dan ke belakang? Anda perlu pergi ke satu arah? [Hardison] Yeah. Jadi bagaimana kita menyelesaikan itu, kadang-kadang? [Basil] duanya adalah terpakai dikaitkan senarai? >> Tepat sekali. Terdapat senarai duanya adalah terpakai dikaitkan. Terdapat juga - maaf? 

[Sam] Adakah itu sama seperti menggunakan perkara Pred bahawa - Saya hanya teringat, tidak bahawa apa perkara Pred adalah untuk? Adakah tidak bahawa di antara duanya adalah terpakai dan berseorangan? [Hardison] Mari kita melihat apa sebenarnya yang dia lakukan. Jadi di sini kita pergi. Berikut adalah senarai kod. Di sini kita mempunyai predptr, di sini. Adakah ini apa yang anda bercakap tentang? Jadi ini adalah - dia membebaskan senarai dan dia cuba untuk menyimpan penunjuk untuk ia. Ini bukan duanya adalah terpakai, secara tunggal dikaitkan senarai. Kita boleh bercakap lebih lanjut tentang perkara ini kemudian kerana ini sedang bercakap tentang membebaskan senarai dan saya ingin menunjukkan beberapa barangan lain terlebih dahulu. tetapi ia hanya - ia mengingat nilai ptr [Pelajar] Oh, ia penunjuk sebelumnya? >> Yeah. Supaya kita boleh kenaikan ptr sendiri sebelum kita kemudian bebas apa predptr. Kerana kita tidak boleh bebas ptr dan kemudian memanggil ptr = ptr seterusnya, kan? Itu akan menjadi buruk. Jadi mari kita lihat, kembali kepada lelaki ini. 

Perkara lain yang buruk tentang senarai adalah bahawa manakala dengan pelbagai kita hanya mempunyai semua unsur-unsur sendiri disusun bersebelahan antara satu sama lain, di sini kita juga telah diperkenalkan penunjuk ini. Jadi ada sebahagian tambahan ingatan bahawa kita perlu menggunakan untuk setiap elemen yang kita sedang menyimpan dalam senarai kami. Kita mendapat fleksibiliti, tetapi ia datang pada kos. Ia datang dengan kos masa ini, dan ia datang dengan kos memori ini juga. Masa dalam erti kata bahawa kita kini mempunyai untuk pergi melalui setiap elemen dalam array untuk mencari satu pada indeks 10, atau yang sepatutnya index 10 dalam array. 

Hanya benar-benar cepat, apabila kita gambarajah keluar senarai ini, biasanya kita berpegang kepada kepala senarai atau penunjuk pertama senarai dan ambil perhatian bahawa ini adalah satu penunjuk yang benar. Ia hanya 4 bait. Ia bukan satu nod sebenar itu sendiri. Jadi anda lihat bahawa ia tidak mempunyai nilai int di dalamnya, tiada penunjuk seterusnya di dalamnya. Ia adalah benar-benar hanya penunjuk. Ia akan menunjukkan kepada sesuatu yang merupakan struct nod sebenar. [Sam] Satu penunjuk yang dipanggil nod? >> Ini adalah - tidak. Ini adalah penunjuk kepada sesuatu nod jenis. Ia adalah penunjuk kepada struct nod. >> Oh, okay. Rajah pada kod kiri, di sebelah kanan. Kita boleh menetapkan ia untuk batal, yang merupakan cara yang baik untuk memulakan. Apabila anda gambarajah ia, sama ada anda menulis ia sebagai batal atau anda meletakkan garisan melalui ia seperti itu. 

Salah satu cara paling mudah untuk bekerja dengan senarai, dan kami meminta anda Prepend kedua-dua dan melampirkan untuk melihat perbezaan antara kedua-dua, tetapi prepending memang mudah. Apabila anda Prepend, ini adalah di mana anda - apabila anda Prepend (7), anda pergi dan mewujudkan struct nod dan anda menetapkan pertama untuk menunjukkan kepadanya, kerana kini, kerana kita prepended, ia akan berada di awal senarai. Jika kita Prepend (3), yang mencipta nod lain, tetapi sekarang 3 datang sebelum 7. Jadi, kita pada dasarnya menolak perkara-perkara ke senarai kami. Kini, anda boleh melihat bahawa Prepend, kadang-kadang orang panggil ia menolak, kerana anda menolak elemen baru ke senarai anda. Ia juga mudah untuk memadam di hadapan senarai. Jadi orang sering akan memanggil pop yang. Dan dengan cara itu, anda boleh mencontohi susunan menggunakan senarai yang dipautkan. Oop. Maaf, sekarang kita sedang masuk ke dalam lampiran. Jadi di sini kita prepended (7), sekarang kita Prepend (3). Jika kita prepended sesuatu yang lain ke senarai ini, jika kita prepended (4), maka kita akan mempunyai 4 dan kemudian 3 dan kemudian 7. Jadi maka kita boleh pop dan keluarkan 4, remove 3, keluarkan 7. Selalunya cara yang lebih intuitif untuk berfikir tentang perkara ini adalah dengan lampiran. Jadi saya telah diagrammed apa yang ia akan kelihatan seperti dengan melampirkan di sini. Di sini, dilampirkan (7) tidak melihat apa-apa yang berbeza kerana ada hanya satu elemen dalam senarai. Dan appending (3) meletakkan ia pada akhir. Mungkin anda boleh lihat sekarang helah dengan lampiran ialah kerana kita hanya tahu di mana permulaan senarai, untuk menambah kepada senarai anda perlu berjalan sepanjang jalan melalui senarai untuk sampai ke akhir, berhenti, kemudian membina nod anda dan segala-galanya mengempaskan turun. Wayar semua barangan atas. Jadi dengan Prepend, kita hanya mengoyakkan melalui ini benar-benar cepat, apabila anda Prepend ke senarai, ia agak mudah. 

Anda membuat nod baru anda, melibatkan beberapa peruntukan memori dinamik. Jadi di sini kita membuat struct nod menggunakan malloc. Jadi malloc kita menggunakan kerana yang akan mengetepikan ingatan bagi kita untuk masa lain kerana kita tidak mahu perkara ini - kami mahu memori ini berterusan untuk jangka masa yang panjang. Dan kita mendapat penunjuk kepada ruang dalam ingatan bahawa kita hanya diperuntukkan. Kami menggunakan saiz nod, kita tidak meringkaskannya bidang. Kami tidak manual menjana bilangan bait, sebaliknya kita gunakan sizeof supaya kita tahu kita sedang mendapatkan nombor yang sesuai bait. Kami pastikan untuk menguji bahawa panggilan malloc kami berjaya. Ini adalah sesuatu yang anda mahu lakukan secara umum. Pada mesin moden, kehabisan memori bukanlah sesuatu yang mudah melainkan jika anda memperuntukkan satu tan barangan dan membuat senarai besar, tetapi jika anda sedang membina barangan untuk, katakan, seperti iPhone atau Android, anda tidak mempunyai sumber memori yang terhad, terutamanya jika anda sedang melakukan sesuatu yang kuat. Jadi ia adalah baik untuk masuk ke dalam amalan. 

Perhatikan bahawa saya telah menggunakan fungsi yang berbeza beberapa di sini bahawa anda telah melihat bahawa adalah jenis baru. Jadi fprintf seperti printf kecuali hujah pertama adalah aliran yang anda mahu untuk mencetak. Dalam kes ini, kita ingin mencetak rentetan kesilapan standard yang berbeza dari outstream standard. Secara lalai ia muncul di tempat yang sama. Ia juga mencetak keluar ke terminal, tetapi anda boleh - menggunakan mereka arahan anda belajar tentang, redirection teknik anda belajar kira-kira dalam video Tommy untuk menetapkan masalah 4, anda boleh mengarahkan kepada kawasan-kawasan yang berlainan; kemudian keluar, di sini, keluar program anda. Ia adalah asasnya seperti pulang dari utama, kecuali kita menggunakan keluar kerana di sini pulangan tidak akan berbuat apa-apa. Kita tidak berada di utama, jadi kembali tidak keluar dari program seperti kita mahu. Jadi kita gunakan fungsi keluar dan memberikan kod ralat. Kemudian di sini kita menetapkan bidang nilai nod baru, bidang i untuk menjadi sama dengan i, dan kemudian kita wayar sehingga ia. Kami menetapkan penunjuk nod seterusnya baru ke titik pertama, dan kemudian pertama kini akan menunjukkan kepada nod baru. Ini baris pertama kod, kita sebenarnya membina nod baru. Bukan yang terakhir dua baris fungsi ini tetapi yang pertama. Anda sebenarnya boleh tarik keluar ke fungsi, ke dalam fungsi pembantu. Itu sering apa yang saya lakukan adalah, saya tarik ia keluar ke fungsi, Saya memanggilnya sesuatu seperti membina nod, dan yang menyimpan fungsi Prepend agak kecil, ia adalah hanya 3 baris kemudian. Saya membuat panggilan kepada fungsi nod membina saya, dan kemudian saya dawai segala-galanya sehingga. 

Perkara terakhir yang saya ingin menunjukkan kepada anda, dan saya akan membiarkan anda melakukan lampiran dan semua yang anda sendiri, adalah bagaimana untuk melelar senarai. Terdapat sekumpulan cara yang berbeza untuk melelar atas senarai. Dalam kes ini, kita akan mendapati panjang senarai. Jadi kita mulakan dengan = 0 panjang. Ini adalah amat serupa untuk menulis strlen untuk rentetan. Ini adalah apa yang saya mahu menunjukkan kepada anda, ini untuk gelung di sini. Ia kelihatan agak funky; ia tidak biasa int i = 0, i <apa sahaja, i + +. Sebaliknya, ia yang Memulakan n pembolehubah kita untuk menjadi permulaan senarai. Dan kemudian manakala pembolehubah iterator kita tidak adalah batal, kita terus pergi. Ini adalah kerana, mengikut konvensyen, akhir senarai kami akan menjadi batal. Dan kemudian ke kenaikan, bukannya melakukan + +, bersamaan senarai bersambung + + n = n-> seterusnya. 

Saya akan membiarkan anda mengisi jurang di sini kerana kita berada di luar masa. Tetapi menyimpan ini dalam minda sebagai anda bekerja pada psets spellr anda. Berkaitan senarai, jika anda sedang melaksanakan jadual hash, pasti akan datang dalam sangat berguna. Dan mempunyai ungkapan ini untuk menggelung atas perkara akan menjadikan kehidupan lebih mudah, mudah-mudahan. Sebarang soalan, cepat? [Sam] Adakah anda menghantar SLL siap dan sc? [Hardison] Yeah. Saya akan menghantar keluar slaid siap dan SLL siap timbunan dan queue.cs. [CS50.TV]