[Powered by Google Translate] [Minggu 6]
[David J. Malan] [Harvard University]
[Ini adalah CS50.] [CS50.TV]
>> Ini adalah CS50, dan ini adalah awal dari Minggu 6,
sehingga beberapa alat baru yang sekarang tersedia bagi Anda untuk mengambil keuntungan dari,
yang pertama disebut CS50 Style.
Kemungkinannya adalah jika Anda seperti saya atau salah satu rekan-rekan mengajar,
Anda mungkin pernah melihat sebuah program yang gaya terlihat sedikit sesuatu seperti ini.
Mungkin Anda mulai memotong beberapa sudut larut malam, atau Anda akan berurusan dengan itu nanti,
dan kemudian TF atau CA datang lebih selama jam kerja.
Maka sulit bagi kita untuk membaca.
Nah, kode ini adalah sintaksis benar, dan itu akan mengkompilasi, dan itu benar-benar akan berjalan.
Tapi itu jelas bukan 5 untuk gaya.
>> Tapi sekarang, jika kita pergi ke direktori ini di sini-
dan perhatikan bahwa saya memiliki-conditions2.c
dan saya menjalankan perintah baru, style50, pada conditions2.c file, Enter,
melihat bahwa itu memberitahu saya bahwa telah bergaya.
Gedit menyadari bahwa file tersebut telah diubah pada disk,
dan jika saya klik ulang, semua masalah Anda sekarang otomatis.
[Tepuk tangan]
Itulah salah satu hal yang kita lakukan akhir pekan ini.
Sadarilah bahwa itu tidak sempurna karena ada beberapa kode
bahwa itu hanya tidak akan mampu untuk menyesuaikan dgn mode sempurna,
tapi menyadari hal ini sekarang menjadi alat yang dapat mengambil keuntungan dari
jika hanya untuk merapikan beberapa kurung kurawal lebih errantly ditempatkan dan sejenisnya.
>> Tapi yang lebih menarik sekarang adalah CS50 Periksa.
Dengan CS50 Cek, Anda benar-benar dapat melakukan tes kebenaran yang sama
pada kode Anda sendiri bahwa rekan-rekan mengajar mampu.
Ini adalah sebuah utilitas baris perintah yang datang sekarang dalam alat
segera setelah Anda melakukan update50 sesuai
pset 4 spesifikasi, dan Anda menggunakannya pada dasarnya seperti ini.
Anda menjalankan perintah check50.
Kemudian Anda lulus dalam argumen baris perintah, atau lebih umum dikenal sebagai switch atau bendera.
Umumnya, hal-hal yang memiliki tanda hubung disebut switch
untuk program baris perintah, sehingga-c menentukan
cek yang ingin Anda jalankan.
>> Tes yang ingin Anda jalankan diidentifikasi secara unik dengan string ini,
2012/pset4/resize.
Dengan kata lain, itu hanya sebuah string sewenang-wenang tapi unik
yang kita gunakan untuk secara unik mengidentifikasi tes ketepatan 4 pset itu.
Dan kemudian Anda menentukan daftar dipisahkan dengan spasi dari file yang ingin Anda upload
untuk CS50 Periksa analisis.
Misalnya, jika saya pergi ke solusi saya di sini untuk resize.c-
biarkan aku membuka jendela terminal besar-
dan saya pergi ke depan dan menjalankan katakanlah check50-c 2012/pset4/resize,
dan kemudian saya pergi ke depan dan menentukan nama-nama file,
resize.c, dan kemudian tekan Enter, maka kompres,
itu upload, mengecek, dan saya hanya gagal sejumlah tes.
Yang merah di sebelah kiri atas mengatakan bahwa resize.c dan bmp ada.
Itu tes. Itulah pertanyaan kita.
Dan itu tidak bahagia karena jawabannya adalah palsu.
Teks putih di bawah itu mengatakan diharapkan bmp.h ada, dan itu hanya salahku.
Aku lupa untuk meng-upload, jadi saya perlu untuk meng-upload kedua file,
resize.c dan bmp.h.
Tapi sekarang perhatikan semua tes lainnya dalam kuning karena mereka tidak menjalankan,
dan sehingga wajah tersenyum adalah vertikal karena dia tidak merasa bahagia ataupun sedih,
tapi kita harus memperbaiki masalah itu dalam warna merah sebelum mereka cek lainnya akan berjalan.
>> Biarkan saya memperbaiki hal ini.
Biarkan saya zoom out dan memutarkan ini, kali ini dengan bmp.h juga
pada baris perintah, Enter, dan sekarang jika semuanya berjalan dengan baik,
itu akan memeriksa dan kemudian kembali hasil dari-tahan napas Anda-
semua hijau, yang berarti saya lakukan dengan sangat baik pada pset 4 sejauh ini.
Anda dapat melihat dan menyimpulkan dari teks deskriptif di sini
persis apa yang kita diuji.
Kami diuji terlebih dahulu melakukan file yang ada?
Kami kemudian diuji apakah kompilasi resize.c?
Kemudian kita diuji apakah itu tidak mengubah ukuran 1x1-pixel BMP jika n, faktor resize, adalah 1.
Sekarang, jika Anda tidak tahu apa n adalah, Anda sekali Anda akan menyelam ke pset 4,
tapi itu hanya merupakan kewarasan periksa untuk memastikan bahwa Anda tidak mengubah ukuran
gambar sama sekali jika faktor resize 1.
Jika, sebaliknya, itu mengubah ukuran piksel 1x1 ke 1x1 pixel BMP untuk 2x2 dengan benar
jika n adalah 2, maka sama, saya membentuk sesuai.
>> Singkatnya, hal ini dimaksudkan untuk, satu, mengambil melintasi jari
dari persamaan tepat sebelum Anda mengirimkan pset Anda.
Anda akan tahu persis apa TF Anda akan segera tahu
ketika Anda pergi tentang mengirimkan beberapa set masalah,
dan juga motivasi pedagogis benar-benar menempatkan
kesempatan di depan Anda sehingga ketika Anda tahu a priori
bahwa ada bug dalam kode Anda dan tes yang tidak lulus,
Anda dapat dimasukkan ke dalam waktu yang lebih efektif di depan untuk memecahkan masalah-masalah
bukannya kehilangan poin, mendapatkan umpan balik dari TF Anda,
dan kemudian pergi, "Ahh," seperti saya harus berpikir bahwa keluar.
Sekarang setidaknya ada alat untuk membantu Anda menemukan bahwa.
Ini tidak akan menunjukkan di mana bug tersebut, tetapi akan memberitahu Anda
apa gejala itu.
>> Sekarang menyadari tes tidak selalu lengkap.
Hanya karena Anda mendapatkan layar penuh hijau wajah smiley
tidak berarti kode Anda sempurna, tetapi tidak berarti
yang telah lulus tes tertentu yang ditentukan oleh spec.
Kadang-kadang kita tidak akan merilis cek.
Misalnya, cerita detektif, salah satu aspek pset 4,
adalah agak mengecewakan jika kita memberikan
jawaban untuk apa itu, dan ada sejumlah cara untuk mengungkapkan
siapa orang itu dalam kebisingan merah.
Spec akan selalu menentukan di masa depan untuk pset 5 seterusnya
apa yang ada untuk memeriksa Anda.
Anda akan melihat ada URL putih di bagian bawah.
Untuk saat ini, ini hanya output diagnostik.
Jika Anda mengunjungi URL tersebut, Anda akan mendapatkan sejumlah besar gila, pesan samar
bahwa Anda dipersilakan untuk melihat melalui, tapi itu sebagian besar untuk staf
sehingga kita dapat mendiagnosa dan debug bug di check50 sendiri.
>> Tanpa basa-basi, mari kita beralih ke tempat kami tinggalkan.
CS50 perpustakaan kami mengambil begitu saja selama beberapa minggu,
tapi kemudian minggu lalu, kami mulai mengupas kembali salah satu lapisan itu.
Kami mulai menyisihkan string dalam mendukung apa bukan?
[Siswa] Char.
Char *, yang telah menjadi char * sepanjang waktu ini,
tapi sekarang kita tidak harus berpura-pura bahwa itu adalah tipe data string yang sebenarnya.
Sebaliknya, itu menjadi sinonim macam untuk char *,
dan string adalah rangkaian karakter,
jadi mengapa tidak masuk akal untuk mewakili string sebagai char * s?
Apa char * mewakili dalam konteks ini konsep string?
Ya >> [Mahasiswa]. Karakter pertama.
Baik, karakter pertama, tetapi tidak cukup karakter pertama.
Ini-[Siswa] Alamat.
Baik, alamat dari karakter pertama.
Semua yang diperlukan untuk mewakili string dalam memori komputer
hanya alamat unik dari byte yang pertama.
Anda bahkan tidak harus tahu berapa lama itu
karena bagaimana Anda bisa mencari tahu secara dinamis?
[Mahasiswa] panjang String.
Anda dapat memanggil panjang string, baik, tapi bagaimana cara kerja panjang string?
Apa yang dilakukannya? Ya.
[Mahasiswa] Terus sampai Anda mendapatkan karakter null.
Ya, tepatnya, itu hanya iterates dengan untuk loop, sementara loop,
apapun dari * sampai akhir, dan akhirnya diwakili
oleh \ 0, karakter yang disebut nul, nul,
tidak harus bingung dengan nol, yang merupakan pointer,
yang akan muncul dalam percakapan lagi hari ini.
>> Kami dikupas kembali lapisan GetInt, dan kemudian kita mengambil melihat GetString,
dan mengingat bahwa kedua fungsi tersebut, atau benar-benar,
GetString, adalah menggunakan fungsi tertentu
untuk benar-benar mengurai, yaitu, membaca atau menganalisis, masukan pengguna.
Dan apa itu fungsi baru?
Scanf atau sscanf. Ini benar-benar datang dalam beberapa rasa yang berbeda.
Ada scanf, ada sscanf, ada fscanf.
Untuk saat ini, meskipun, mari kita fokus pada yang paling mudah digambarkan,
dan biarkan aku pergi ke depan dan terbuka di alat
file seperti ini, scanf1.c.
Ini adalah program super sederhana,
tapi yang melakukan sesuatu yang kita belum pernah melakukan
tanpa bantuan dari perpustakaan CS50.
Ini mendapat int dari pengguna. Bagaimana cara kerjanya?
Nah, di baris 16 sana,
perhatikan bahwa kita mendeklarasikan x disebut int, dan pada titik ini dalam cerita,
berapakah nilai dari x?
[Respon siswa tidak terdengar]
[David M.] Benar, siapa tahu, beberapa nilai sampah yang berpotensi, sehingga di 17, kami hanya memberitahu pengguna
memberi saya nomor, silahkan, dan langkah 18 adalah di mana ia mulai menarik.
Scanf tampaknya meminjam ide dari printf karena menggunakan kode-kode format yang dalam tanda kutip.
D% tentu saja angka desimal.
Tapi mengapa aku lewat di & x bukan hanya x?
Yang pertama adalah benar. Ya.
[Respon siswa tidak terdengar]
Tepat, jika tujuan dari program ini, seperti GetInt fungsi itu sendiri,
adalah untuk mendapatkan int dari pengguna saya bisa lulus fungsi
semua variabel saya inginkan, tetapi jika aku tidak melewati mereka dengan referensi
atau berdasarkan alamat atau pointer, semua sinonim untuk keperluan hari ini,
maka fungsi yang tidak memiliki kemampuan untuk mengubah isi dari variabel itu.
Hal ini akan lulus dalam salinan seperti versi kereta swap
bahwa kita telah berbicara tentang beberapa kali sekarang.
>> Tapi sebaliknya, dengan melakukan & x, aku benar-benar lewat di apa?
[Mahasiswa] Alamat. >> Alamat dari x.
Ini seperti menggambar peta untuk fungsi yang disebut scanf dan katakan di sini,
ini adalah petunjuk untuk sepotong memori di komputer
bahwa Anda dapat pergi menyimpan bilangan bulat beberapa masuk
Agar sscanf sekarang melakukan itu
apa operator, apa bagian dari sintaks itu akan harus menggunakan
meskipun kita tidak bisa melihatnya karena orang lain menulis fungsi ini?
Dengan kata lain - apa itu?
[Siswa] X dibaca.
Ada akan menjadi beberapa bacaan, tetapi hanya berkaitan dengan x di sini.
Jika scanf sedang melewati alamat dari x,
sintaksis, apa operator pasti akan ada di suatu tempat
dalam pelaksanaan scanf itu sehingga scanf
benar-benar dapat menulis nomor 2 ke alamat tersebut?
Ya, jadi file *.
Ingat bahwa * adalah dereference operator kami, yang pada dasarnya berarti pergi ke sana.
>> Setelah Anda telah menyerahkan alamat, seperti yang terjadi di sini,
scanf mungkin-jika kita benar-benar melihat sekeliling sumbernya kode-
melakukan * x atau setara untuk benar-benar pergi ke alamat tersebut dan menempatkan beberapa nilai di sana.
Sekarang, seperti untuk bagaimana scanf mendapat masukan dari keyboard,
kita akan melambaikan tangan kami keluar untuk hari ini.
Hanya berasumsi bahwa sistem operasi memungkinkan untuk berbicara sscanf
ke keyboard pengguna, tetapi pada titik ini sekarang di baris 19,
ketika kita hanya mencetak x, tampaknya menjadi kasus
bahwa scanf telah menempatkan int di x.
Itulah bagaimana scanf bekerja, dan ingat minggu lalu
itulah bagaimana GetString dan GetInt dan keluarga lainnya dari fungsi
akhirnya bekerja, meskipun dengan sedikit varian seperti sscanf,
yang berarti memindai string bukan keyboard.
Tapi mari kita lihat pada varians sedikit ini.
Pada scanf2, saya benar-benar kacau.
Apa yang salah-dan saya akan menyembunyikan komentar yang menjelaskan sebanyak-
apa yang salah dengan program ini, versi 2?
Jadilah seperti teknis mungkin kali ini.
Ini terlihat cukup baik.
Ini baik indentasi, tapi-
Oke, mari kita bagaimana memangkas itu ke pertanyaan pendek?
Baris 16. Apa baris 16 dilakukan dalam bahasa Inggris yang tepat namun teknis?
Mendapatkan sedikit canggung. Ya, Michael.
[Mahasiswa] Ini menunjuk ke huruf pertama dari string.
>> Oke, dekat. Biarkan saya tweak yang sedikit.
Menunjuk ke huruf pertama dari string, Anda menyatakan buffer disebut variabel
yang akan menunjuk ke alamat pertama dari string,
atau lebih tepatnya, yang akan mengarahkan lebih spesifik ke char.
Perhatikan itu tidak benar-benar menunjuk di mana saja karena tidak ada operator penugasan.
Tidak ada tanda sama, sehingga semua yang kita lakukan adalah mengalokasikan buffer disebut variabel.
Hal ini terjadi menjadi 32 bit karena pointer,
dan isi buffer mungkin akhirnya
akan berisi alamat char, tapi untuk saat ini, apa penyangga mengandung?
Hanya beberapa palsu, siapa tahu, beberapa nilai sampah,
karena kita tidak secara eksplisit diinisialisasi itu, jadi kita tidak boleh berasumsi apa-apa.
Oke, jadi sekarang baris 17 adalah baris-apa 17 lakukan?
Mungkin itu akan menghangatkan ini.
Ini mencetak string, kan?
Mencetak String silahkan.
>> Baris 18 adalah jenis akrab sekarang kita hanya melihat varians ini
tapi dengan kode format yang berbeda, sehingga sejalan 18,
kita mengatakan scanf sini adalah alamat dari sepotong memori.
Saya ingin Anda untuk cincin dalam sebuah string, seperti yang tersirat oleh% s,
tapi masalahnya adalah bahwa kita tidak melakukan beberapa hal di sini.
Apa salah satu masalah?
[Mahasiswa] Ini mencoba untuk dereference pointer null.
Baik, nol atau hanya jika diketahui pointer.
Kau menyerahkan scanf alamat, tapi Anda hanya mengatakan beberapa saat yang lalu
bahwa alamat itu adalah beberapa nilai sampah karena kita tidak benar-benar menetapkan apa-apa,
dan begitu kau mengatakan scanf efektif pergi menempatkan string di sini,
tapi kita tidak tahu di mana di sini namun,
jadi kita belum benar-benar mengalokasikan memori untuk buffer.
Selain itu, apa yang Anda juga bahkan tidak memberitahu scanf?
Misalkan ini adalah sepotong memori, dan itu bukan nilai sampah,
tapi kau masih belum mengatakan scanf sesuatu yang penting.
[Mahasiswa] Dimana sebenarnya, ampersand.
Ampersand, sehingga dalam kasus ini, tidak apa-apa.
Karena buffer sudah dinyatakan sebagai pointer
dengan potongan * sintaksis, kita tidak perlu menggunakan ampersand
karena itu sudah alamat, tapi saya pikir saya dengar di sini.
[Mahasiswa] Seberapa besar itu?
Baik, kita tidak mengatakan scanf seberapa besar penyangga ini,
yang berarti bahkan jika buffer adalah pointer,
kami katakan scanf, menempatkan string di sini,
tapi di sini bisa menjadi 2 byte, bisa 10 byte, bisa jadi satu megabyte.
Scanf memiliki tidak tahu, dan karena ini adalah sepotong memori
mungkin, itu bukan string belum.
Ini hanya string sekali Anda menulis karakter dan \ 0 dengan sepotong memori.
Sekarang hanya beberapa potongan memori.
Scanf tidak akan tahu kapan harus berhenti menulis ke alamat tersebut.
>> Jika Anda ingat beberapa contoh di masa lalu di mana saya secara acak mengetik pada keyboard
mencoba untuk buffer overflow, dan kami berbicara pada hari Jumat tentang hal itu.
Jika musuh entah bagaimana menyuntikkan ke dalam program Anda sebuah kata yang jauh lebih besar
atau kalimat atau frase maka Anda mengharapkan Anda dapat dikuasai
sepotong memori, yang dapat memiliki konsekuensi yang buruk,
seperti mengambil alih seluruh program itu sendiri.
Kita harus memperbaiki ini, entah bagaimana.
Biarkan saya zoom out dan masuk ke versi 3 dari program ini.
Itu sedikit lebih baik.
Dalam versi ini, melihat perbedaan.
Sejalan 16, aku lagi menyatakan buffer disebut variabel,
tapi apa sekarang?
Ini sebuah array dari 16 karakter.
Ini bagus karena ini berarti saya sekarang dapat memberitahu scanf
di sini adalah potongan yang sebenarnya memori.
Anda hampir bisa memikirkan array sebagai pointer sekarang,
meskipun mereka tidak benar-benar setara.
Mereka akan berperilaku berbeda dalam konteks yang berbeda.
Tapi pasti terjadi bahwa buffer referensi
16 bersebelahan chars karena itulah array adalah
dan telah berlangsung selama beberapa minggu sekarang.
>> Di sini, saya mengatakan scanf inilah sepotong memori.
Kali ini, itu sebenarnya sepotong memori,
tapi mengapa program ini masih dimanfaatkan?
Apa yang salah masih?
Aku sudah mengatakan memberi saya 16 byte tapi-
[Siswa] Bagaimana jika mereka ketik di lebih dari 16?
Tepat, bagaimana jika pengguna jenis dalam 17 karakter atau karakter 1.700?
Bahkan, mari kita lihat apakah kita tidak bisa tersandung kesalahan ini sekarang.
Lebih baik tetapi tidak sempurna.
Biarkan aku pergi ke depan dan menjalankan make scanf3 untuk mengkompilasi program ini.
Biarkan saya menjalankan scanf3, silahkan String: halo, dan kami tampaknya baik-baik saja.
Biarkan saya mencoba yang sedikit lebih panjang, hello there.
Oke, mari kita lakukan halo ada bagaimana kabarmu hari ini, Enter.
Mendapatkan jenis beruntung di sini, katakanlah halo ada kabar.
Sialan.
Oke, jadi kita beruntung. Mari kita lihat apakah kita tidak bisa memperbaiki ini.
Tidak, itu tidak akan membiarkan saya salin.
Mari kita coba ini lagi.
Baiklah, stand by.
Kita akan melihat berapa lama aku bisa berpura-pura untuk fokus sementara masih melakukan hal ini.
Sialan. Itu agak tepat, sebenarnya.
Di sana kami pergi.
Titik yang dibuat.
>> Hal ini, memalukan meskipun juga, itu juga merupakan salah satu sumber kebingungan besar
ketika menulis program yang memiliki bug karena mereka menampakkan diri
hanya sekali-sekali kadang-kadang.
Kenyataannya adalah bahwa bahkan jika kode Anda benar-benar rusak,
itu hanya mungkin benar-benar rusak sesekali
karena kadang-kadang, pada dasarnya apa yang terjadi adalah mengalokasikan sistem operasi
memori yang lebih sedikit dari yang Anda benar-benar perlu untuk alasan apapun,
sehingga tidak ada orang lain yang menggunakan memori tepat setelah potongan Anda dari 16 karakter,
jadi jika Anda pergi ke 17, 18, 19, apa pun, itu bukan masalah besar.
Sekarang, komputer, bahkan jika tidak crash pada saat itu,
akhirnya bisa menggunakan nomor byte 17 atau 18 atau 19 untuk sesuatu yang lain,
di mana titik data Anda bahwa Anda diletakkan di sana, meskipun terlalu panjang,
akan mendapatkan ditimpa berpotensi oleh beberapa fungsi lainnya.
Ini belum tentu akan tetap utuh,
tapi tidak akan selalu menyebabkan kesalahan seg.
Tapi dalam kasus ini, saya akhirnya disediakan karakter yang cukup
bahwa saya pada dasarnya melebihi segmen memori saya, dan bam,
sistem operasi mengatakan, "Maaf, itu bukan karena kesalahan, segmentasi yang baik."
>> Dan mari kita lihat sekarang jika apa yang tersisa di sini di saya direktori-
melihat bahwa saya memiliki file ini di sini, inti.
Perhatikan bahwa ini lagi disebut core dump.
Ini pada dasarnya adalah sebuah file yang berisi isi dari memori program Anda
pada titik di mana ia jatuh,
dan hanya untuk mencoba contoh kecil di sini biarkan aku pergi di sini
dan menjalankan gdb pada scanf3 dan kemudian menentukan argumen ketiga yang disebut inti,
dan perhatikan di sini bahwa jika saya daftar kode,
kita akan dapat seperti biasa dengan gdb untuk mulai berjalan melalui program ini,
dan saya dapat menjalankannya dan segera setelah aku memukul-seperti dengan perintah langkah dalam gdb-
segera setelah aku memukul garis berpotensi kereta setelah mengetik dalam serangkaian besar,
Aku akan dapat benar-benar mengidentifikasi sini.
Lebih lanjut tentang ini, meskipun, di bagian dalam hal core dumps
dan sejenisnya sehingga Anda dapat benar-benar melihat-dalam core dump
dan melihat apa program baris gagal Anda.
Setiap pertanyaan kemudian pada pointer dan alamat?
Karena hari ini, kita akan mulai mengambil begitu saja bahwa hal-hal ini ada
dan kita tahu persis apa yang mereka.
Ya.
>> [Mahasiswa] Kenapa Anda tidak harus meletakkan ampersand sebelah bagian-
Pertanyaan bagus.
Kenapa saya tidak harus meletakkan ampersand sebelah array karakter seperti yang saya lakukan sebelumnya
dengan sebagian besar contoh kita?
Jawaban singkatnya adalah array yang sedikit istimewa.
Anda hampir dapat berpikir buffer sebagai benar-benar menjadi alamat,
dan kebetulan menjadi kasus bahwa notasi persegi braket
adalah kenyamanan sehingga kita bisa masuk ke braket 0, 1 braket,
braket 2, tanpa harus menggunakan notasi *.
Itu sedikit kebohongan putih karena array dan pointer
adalah, pada kenyataannya, sedikit berbeda, tetapi mereka bisa sering tapi tidak selalu digunakan secara bergantian.
Singkatnya, ketika sebuah fungsi mengharapkan pointer ke sepotong memori,
Anda dapat lulus alamat yang dikembalikan oleh malloc,
dan kita akan melihat malloc lagi sebelum panjang, atau Anda bisa lulus nama array.
Anda tidak perlu melakukan ampersand dengan array karena mereka sudah
dasarnya seperti alamat.
Itulah satu-satunya pengecualian.
Tanda kurung siku membuat mereka istimewa.
>> Bisakah Anda menempatkan sebuah ampersand sebelah buffer?
Tidak dalam kasus ini.
Itu tidak akan bekerja karena, sekali lagi, ini kasus sudut
di mana array tidak cukup sebenarnya alamat.
Tapi kita mungkin akan kembali ke sebelum panjang dengan contoh-contoh lainnya.
Mari kita coba untuk memecahkan masalah di sini.
Kami memiliki struktur data yang kita telah menggunakan untuk beberapa waktu yang dikenal sebagai array.
Kasus di titik, itulah yang kita baru saja.
Tapi array memiliki beberapa keuntungan dan kerugian.
Array adalah mengapa bagus?
Apa satu hal yang Anda sukai-sejauh yang Anda suka array-array tentang?
Apa nyaman tentang mereka? Apa yang menarik?
Mengapa kita memperkenalkan mereka di tempat pertama?
Ya.
[Mahasiswa] Mereka dapat menyimpan banyak data, dan Anda tidak harus menggunakan seluruh hal.
Anda dapat menggunakan bagian.
Baik, dengan array Anda dapat menyimpan banyak data,
dan Anda tidak perlu harus menggunakan semua itu, sehingga Anda dapat overallocate,
yang mungkin nyaman jika Anda tidak tahu sebelumnya berapa banyak dari sesuatu untuk diharapkan.
>> GetString adalah contoh yang sempurna.
GetString, ditulis oleh kami, tidak tahu berapa banyak karakter yang diharapkan,
sehingga fakta bahwa kita dapat mengalokasikan potongan memori yang berdekatan yang baik.
Array juga memecahkan masalah kami melihat beberapa minggu lalu sekarang
di mana kode Anda mulai berpindah ke sesuatu yang sangat buruk dirancang.
Ingat bahwa saya membuat sebuah struktur mahasiswa bernama David,
dan kemudian itu benar-benar alternatif, meskipun,
untuk memiliki nama yang disebut variabel dan variabel lain yang disebut, saya pikir, rumah,
dan variabel lain yang disebut ID karena dalam cerita itu saya kemudian ingin memperkenalkan sesuatu yang lain
seperti Rob ke dalam program, jadi aku memutuskan tunggu dulu,
Saya perlu untuk mengubah nama variabel.
Mari kita sebut tambang name1, ID1, House1.
Mari kita sebut Rob name2, house2, ID2.
Tapi kemudian tunggu sebentar, bagaimana dengan Tommy?
Kemudian kita memiliki tiga variabel yang lebih.
Kami memperkenalkan orang lain, empat set variabel.
Dunia mulai mendapatkan berantakan sangat cepat,
jadi kami memperkenalkan structs, dan apa yang menarik tentang struct?
Apa struct C membiarkan Anda lakukan?
Ini benar-benar aneh hari ini.
Apa >> [respon siswa tidak terdengar]?
Ya, khusus, typedef memungkinkan Anda untuk membuat tipe data baru,
dan struct, kata kunci struct, memungkinkan Anda untuk merangkum
konseptual terkait potongan data bersama-sama
dan kemudian memanggil mereka seperti mahasiswa.
>> Itu bagus karena sekarang kita dapat model
semacam lebih banyak konseptual konsisten gagasan mahasiswa dalam sebuah variabel
daripada sewenang-wenang memiliki satu untuk string, satu untuk ID, dan sebagainya.
Array yang bagus karena mereka memungkinkan kita untuk mulai membersihkan kode kita.
Tapi apa sisi negatifnya sekarang dari array?
Apa yang dapat Anda lakukan tidak? Ya.
[Mahasiswa] Anda harus tahu seberapa besar itu.
Anda harus tahu seberapa besar itu, sehingga jenis rasa sakit.
Bagi Anda dengan pengalaman pemrograman sebelumnya tahu bahwa dalam banyak bahasa,
seperti Java, Anda dapat meminta sepotong memori, khususnya array,
seberapa besar kau, dengan panjang, properti, sehingga untuk berbicara, dan itu benar-benar nyaman.
Di C, Anda bahkan tidak bisa menyebut strlen pada array generik
karena strlen, sebagai kata menyiratkan, hanya untuk string,
dan Anda dapat mengetahui panjang string karena ini konvensi manusia
dari memiliki \ 0, tapi array, lebih umum, hanya sepotong memori.
Jika itu array ints, ada tidak akan ada beberapa karakter khusus
di akhir menunggu untuk Anda.
Anda harus ingat panjang array.
Kelemahan lain dari array dibesarkan pusat di GetString sendiri.
Apa lagi Kelemahan dari array?
Pak, hanya kau dan aku hari ini.
[Respon siswa terdengar] >> Ini apa?
Ini menyatakan pada stack.
Oke, menyatakan pada stack. Kenapa tidak Anda seperti itu?
[Mahasiswa] Karena itu akan digunakan kembali.
Ini akan digunakan kembali.
Oke, jika Anda menggunakan array untuk mengalokasikan memori,
Anda tidak bisa, misalnya, kembali karena pada stack.
Oke, itu suatu kerugian.
Dan bagaimana yang lain dengan array?
Setelah Anda mengalokasikan itu, kau jenis kacau jika Anda membutuhkan lebih banyak ruang
dari array yang memiliki.
>> Kemudian kami diperkenalkan, ingat, malloc, yang memberi kami kemampuan untuk secara dinamis mengalokasikan memori.
Tapi bagaimana kalau kita mencoba dunia yang berbeda sama sekali?
Bagaimana jika kita ingin memecahkan beberapa masalah tersebut
jadi kita bukannya saya-pena telah tertidur di sini-
bagaimana jika kita bukan ingin dasarnya menciptakan dunia yang tidak lagi seperti ini?
Ini adalah sebuah array, dan, tentu saja, ini semacam memburuk setelah kita memukul akhir array,
dan sekarang saya tidak lagi memiliki ruang untuk yang lain integer atau karakter lain.
Bagaimana jika kita semacam preemptively mengatakan baik, kenapa tidak kita bersantai
ini persyaratan bahwa semua potongan memori akan berdekatan kembali ke belakang,
dan kenapa tidak, ketika saya membutuhkan sebuah int atau char,
hanya memberi saya ruang untuk salah satu dari mereka?
Dan ketika aku butuh yang lain, memberi saya ruang lain,
dan ketika aku butuh yang lain, memberi saya ruang lain.
Keuntungan yang sekarang adalah bahwa jika orang lain
mengambil memori di sini, bukan masalah besar.
Aku akan mengambil sepotong tambahan memori di sini dan kemudian satu ini.
>> Sekarang, hasil tangkapan hanya di sini adalah bahwa ini hampir terasa seperti saya
sejumlah variabel yang berbeda.
Ini terasa seperti lima variabel yang berbeda berpotensi.
Tapi bagaimana kalau kita mencuri ide dari string
dimana kita entah bagaimana menghubungkan hal-hal ini bersama-sama secara konseptual, dan bagaimana jika saya melakukan ini?
Ini adalah panahku sangat buruk ditarik.
Tapi misalkan bahwa masing-masing potongan memori
menunjuk ke yang lain, dan orang ini, yang tidak memiliki saudara di sebelah kanannya,
tidak memiliki panah tersebut.
Ini sebenarnya apa yang disebut linked list.
Ini adalah struktur data baru yang memungkinkan kita untuk mengalokasikan sepotong memori,
kemudian lain, lalu yang lain, lalu yang lain, setiap saat kita inginkan
selama program, dan kita ingat bahwa mereka semua entah bagaimana terkait
oleh harfiah chaining mereka bersama-sama, dan kami melakukan itu pictorially sini dengan panah.
Tapi dalam kode, apa yang akan menjadi mekanisme melalui mana Anda entah bagaimana bisa terhubung,
hampir seperti Scratch, salah satu potongan ke potongan lain?
Kita bisa menggunakan pointer, kan?
Karena benar-benar panah yang pergi dari alun-alun kiri atas,
orang ini di sini untuk yang satu ini, bisa berisi dalam alun-alun ini
bukan hanya beberapa ints, bukan hanya beberapa char, tapi bagaimana jika saya benar-benar dialokasikan
sedikit ruang ekstra sehingga sekarang,
masing-masing potongan memori saya, meskipun ini akan saya biaya,
sekarang terlihat sedikit lebih persegi panjang di mana salah satu potongan memori
digunakan untuk nomor, seperti nomor 1,
dan kemudian jika orang ini menyimpan nomor 2,
ini potongan lain dari memori digunakan untuk panah,
atau lebih konkret, pointer.
Dan kira saya menyimpan nomor 3 di sini sementara aku menggunakan ini untuk menunjuk pada orang itu,
dan sekarang orang ini, mari kita kira saya hanya ingin tiga potongan seperti memori.
Aku akan menarik garis melalui itu, menunjukkan nol.
Tidak ada karakter tambahan.
>> Memang, ini adalah bagaimana kita bisa pergi tentang pelaksanaan
sesuatu yang disebut linked list.
Sebuah linked list adalah struktur data baru, dan itu adalah batu loncatan menuju
jauh lebih menarik struktur data yang mulai memecahkan masalah
sepanjang garis Facebook-jenis masalah dan Google-jenis masalah
di mana Anda memiliki set data yang besar, dan tidak lagi memotong itu
untuk menyimpan segala contiguously dan menggunakan sesuatu seperti pencarian linear
atau bahkan sesuatu seperti pencarian biner.
Anda ingin waktu berjalan lebih baik.
Bahkan, salah satu Grails Kudus kita akan berbicara tentang akhir pekan ini atau berikutnya
adalah algoritma yang berjalan waktu konstan.
Dengan kata lain, selalu mengambil jumlah waktu yang sama tidak peduli
seberapa besar input, dan itu memang akan menarik,
bahkan lebih daripada sesuatu yang logaritmik.
Apa ini di layar di sini?
Setiap persegi panjang adalah apa yang saya hanya menggambar dengan tangan.
Tapi hal sepanjang jalan di sebelah kiri adalah variabel khusus.
Ini akan menjadi pointer tunggal karena satu gotcha
dengan linked list, sebagai hal-hal yang disebut,
adalah bahwa Anda harus menggantung ke salah satu ujung linked list.
>> Sama seperti dengan string, Anda harus tahu alamat char pertama.
Sama kesepakatan untuk daftar terkait.
Anda harus tahu alamat dari potongan pertama dari memori
karena dari sana, Anda dapat mencapai setiap orang lainnya.
Downside.
Berapa harga yang kita bayar untuk fleksibilitas memiliki dinamis
struktur data yang cukup besar bahwa jika kita pernah membutuhkan lebih banyak memori, baik,
hanya mengalokasikan satu potongan lagi dan menarik pointer dari
lama ke ekor baru dari daftar?
Ya.
[Mahasiswa] Dibutuhkan ruang sekitar dua kali lebih banyak.
Dibutuhkan ruang dua kali lebih banyak, sehingga pasti sisi negatifnya, dan kita telah melihat ini
tradeoff sebelumnya antara waktu dan ruang dan fleksibilitas
di mana sekarang, kita tidak perlu 32 bit untuk masing-masing nomor.
Kami benar-benar membutuhkan 64, 32 untuk nomor 32 dan untuk pointer.
Tapi, hei, aku punya 2 gigabyte RAM.
Menambahkan lain 32 bit di sini dan di sini tidak tampak bahwa masalah besar.
Tapi untuk set data yang besar, pasti menambahkan hingga benar-benar dua kali lebih banyak.
Apa downside lain sekarang, atau apa fitur yang kita menyerah,
jika kita mewakili daftar hal-hal dengan linked list dan bukan array?
[Mahasiswa] Anda tidak dapat melintasi itu mundur.
Anda tidak dapat melintasi ke belakang, sehingga Anda jenis kacau jika Anda berjalan
dari kiri ke kanan menggunakan untuk loop atau loop sementara
dan kemudian Anda menyadari, "Oh, aku ingin kembali ke awal daftar."
Anda tidak bisa karena pointer hanya pergi dari kiri ke kanan sebagai panah menunjukkan.
>> Sekarang, Anda bisa mengingat awal daftar dengan variabel lain,
tapi itu kompleksitas yang perlu diingat.
Array, tidak peduli seberapa jauh Anda pergi, Anda selalu dapat melakukan dikurangi, dikurangi, dikurangi, dikurangi
dan kembali dari mana kamu datang.
Apa Kelemahan lain di sini? Ya.
[Pertanyaan siswa tidak terdengar]
Anda bisa, sehingga Anda sudah benar-benar hanya mengusulkan struktur data yang disebut daftar ganda terkait,
dan memang, Anda akan menambahkan pointer lain untuk masing-masing persegi panjang
yang pergi arah lain, terbalik dari yang
kini Anda dapat melintasi bolak-balik,
downside yang sekarang Anda menggunakan tiga kali sebagai memori sebanyak yang kita digunakan untuk
dan juga menambah kompleksitas dalam hal kode Anda harus menulis untuk bisa melakukannya dengan benar.
Tapi ini semua mungkin pengorbanan yang sangat wajar, jika pembalikan yang lebih penting.
Ya.
[Mahasiswa] Anda juga tidak dapat memiliki sebuah linked list 2D.
Baik, Anda tidak bisa benar-benar memiliki linked list 2D.
Anda bisa. Ini tidak semudah array.
Seperti array, Anda melakukan braket terbuka, tertutup braket, braket terbuka, tertutup braket,
dan Anda mendapatkan beberapa struktur 2-dimensi.
Anda bisa menerapkan daftar 2-dimensi terkait
jika Anda melakukan add-seperti yang Anda diusulkan-pointer ketiga untuk masing-masing hal,
dan jika Anda berpikir tentang daftar yang lain datang pada Anda bergaya 3D
dari layar untuk kita semua, yang hanya satu rantai dari beberapa macam.
Kita bisa melakukannya, tapi itu tidak sesederhana mengetik braket terbuka, braket persegi. Ya.
[Pertanyaan siswa tidak terdengar]
Baik, jadi ini adalah kicker nyata.
>> Algoritma ini bahwa kita telah pined lebih, seperti oh, pencarian biner,
Anda dapat mencari berbagai angka di papan
atau buku telepon jauh lebih cepat jika Anda menggunakan membagi dan menaklukkan
dan algoritma pencarian biner, tapi pencarian biner diperlukan dua asumsi.
Satu, bahwa data diurutkan.
Sekarang, kita mungkin bisa menjaga ini diurutkan,
jadi mungkin itu bukan masalah, tapi pencarian biner juga diasumsikan
bahwa Anda memiliki akses acak ke daftar nomor,
dan array memungkinkan Anda untuk memiliki akses acak, dan dengan akses random,
Maksudku jika Anda diberikan sebuah array, berapa lama waktu yang dibutuhkan Anda
untuk sampai ke braket 0?
Satu operasi, Anda hanya menggunakan [0] dan Anda berada di sana.
Berapa banyak langkah yang dibutuhkan untuk sampai ke lokasi 10?
Salah satu langkah, Anda hanya pergi ke [10] dan Anda berada di sana.
Sebaliknya, bagaimana Anda bisa sampai ke bilangan bulat 10 dalam linked list?
Anda harus mulai dari awal karena Anda hanya mengingat
awal dari sebuah linked list, seperti string sedang diingat
dengan alamat char pertama, dan menemukan bahwa int 10
atau bahwa karakter ke-10 dalam sebuah string, Anda harus mencari hal sialan seluruh.
>> Sekali lagi, kita tidak memecahkan semua masalah kita.
Kami memperkenalkan yang baru, tapi itu benar-benar tergantung pada apa yang Anda mencoba untuk merancang untuk.
Dalam hal pelaksanaan ini, kita dapat meminjam ide dari mahasiswa bahwa struktur.
Sintaksnya sangat mirip, kecuali sekarang, ide ini sedikit lebih abstrak
dari rumah dan nama dan ID.
Tapi saya mengusulkan agar kita bisa memiliki struktur data dalam C
yang disebut node, sebagai kata terakhir pada slide menunjukkan,
dalam sebuah node, dan node adalah hanya sebuah wadah generik dalam ilmu komputer.
Ini biasanya digambarkan sebagai lingkaran atau persegi atau persegi panjang seperti yang kita lakukan.
Dan dalam hal ini struktur data, kita memiliki int, n,
jadi itu nomor saya ingin menyimpan.
Tapi apa ini baris kedua, struct simpul * selanjutnya?
Mengapa hal ini benar, atau apa peran apakah ini bermain hal,
meskipun agak samar pada pandangan pertama?
Ya.
[Respon siswa tidak terdengar]
Tepat, sehingga semacam * dari rampasan bahwa itu adalah pointer dari beberapa macam.
Nama pointer ini sewenang-wenang berikutnya,
tapi kita bisa menyebutnya apa pun yang kita inginkan, tapi apa titik pointer ke?
[Mahasiswa] simpul lain >> Tepat,. Ini menunjuk ke node lain tersebut.
>> Sekarang, ini adalah semacam rasa ingin tahu C.
Ingat bahwa C dibaca oleh compiler atas ke bawah, kiri ke kanan,
yang berarti jika-ini sedikit berbeda dari apa yang kita lakukan dengan siswa.
Ketika kita mendefinisikan mahasiswa, kita benar-benar tidak menaruh kata di sana.
Itu hanya kata typedef.
Kemudian kami memiliki id, nama string int, string rumah,
dan kemudian mahasiswa di bawah struct.
Deklarasi ini sedikit berbeda karena,
lagi, compiler C sedikit bodoh.
Ini hanya akan membaca atas ke bawah,
jadi jika mencapai garis 2 di sini
di mana selanjutnya dinyatakan dan melihat, oh, di sini adalah variabel yang disebut selanjutnya.
Ini adalah pointer ke node struct.
Compiler akan menyadari apa yang node struct?
Aku belum pernah mendengar hal ini sebelumnya,
karena node kata tidak mungkin jika tidak muncul
sampai bagian bawah, sehingga ada redundansi ini.
Anda harus mengatakan simpul struct di sini, yang kemudian dapat mempersingkat nanti
berkat typedef di sini, tapi ini karena
kita referensi struktur itu sendiri dalam struktur.
Itulah satu gotcha di sana.
>> Beberapa masalah yang menarik akan muncul.
Kami punya daftar nomor. Bagaimana kita masukkan ke dalamnya?
Bagaimana kita mencarinya? Bagaimana kita menghapus dari itu?
Apalagi sekarang bahwa kita harus mengelola semua pointer.
Kau pikir pointer adalah semacam pikiran-lipatan
ketika Anda memiliki salah satu dari mereka hanya mencoba untuk membaca sebuah int untuk itu.
Sekarang kita harus memanipulasi senilai seluruh daftar itu.
Kenapa tidak kita mengambil 5 menit istirahat kami di sini, dan kemudian kami akan membawa
beberapa orang di atas panggung untuk melakukan hal itu.
>> C adalah jauh lebih menyenangkan ketika itu bertindak keluar.
Yang secara harfiah ingin menjadi yang pertama?
Oke, ayo naik. Anda pertama kali.
Siapa yang ingin menjadi 9? Oke, 9.
Bagaimana 9? 17?
Sebuah kelompok kecil di sini. 22 dan 26 dalam barisan depan.
Dan lalu bagaimana tentang seseorang di sana yang menunjuk.
Anda 34. Oke, 34, datang ke atas.
Pertama ada di sana. Oke, semua empat dari kalian.
Dan siapa yang kita katakan untuk 9?
Siapa 9 kita?
Yang benar-benar ingin menjadi 9? Baiklah, ayolah, menjadi 9.
Di sini kita pergi.
34, kita akan bertemu Anda di sana.
Bagian pertama adalah membuat dirimu terlihat seperti itu.
26, 22, 17, baik.
Jika Anda dapat berdiri ke samping, karena kita akan malloc Anda dalam sekejap.
>> Bagus, bagus.
Oke, baik, jadi mari kita mengajukan beberapa pertanyaan di sini.
Dan sebenarnya, siapa namamu? >> Anita.
Anita, oke, datang ke sini.
Anita akan membantu kita semacam memecahkan salah satu pertanyaan yang cukup sederhana di pertama,
yang adalah bagaimana Anda mengetahui apakah atau tidak nilai dalam daftar?
Sekarang, perhatikan bahwa pertama, diwakili di sini oleh Lucas,
adalah sedikit berbeda, sehingga karyanya kertas yang sengaja samping
karena itu tidak cukup sebagai tinggi dan tidak mengambil banyak bit,
meskipun secara teknis ia memiliki ukuran kertas yang sama hanya diputar.
Tapi dia sedikit berbeda dalam bahwa dia hanya 32 bit untuk pointer,
dan semua orang-orang ini adalah 64 bit, setengah dari yang adalah nomor, setengah dari yang adalah pointer.
Tapi pointer tidak digambarkan, jadi jika kalian bisa agak canggung
menggunakan tangan kiri Anda untuk menunjuk pada orang di sebelah Anda.
Dan kau nomor 34. Siapa nama Anda?
Ari.
Ari, jadi sebenarnya, memegang kertas di tangan kanan Anda, dan tangan kiri berjalan lurus ke bawah.
Anda mewakili nol di sebelah kiri.
>> Sekarang gambar manusia sangat konsisten.
Ini sebenarnya bagaimana pointer bekerja.
Dan jika Anda bisa mengernyitkan sedikit cara ini jadi saya tidak dengan cara Anda.
Anita sini, menemukan saya nomor 22,
tetapi mengasumsikan kendala tidak manusia memegang potongan kertas,
tapi ini adalah daftar, dan Anda hanya memiliki Lucas untuk memulai dengan
karena ia secara harfiah pointer pertama.
Misalkan Anda sendiri adalah pointer, dan sehingga Anda juga memiliki kemampuan untuk menunjuk sesuatu.
Kenapa tidak Anda mulai dengan menunjuk pada apa Lucas menunjuk?
Baik, dan biarkan aku memberlakukan hal ini di sini.
Hanya demi diskusi, biarkan aku menarik sebuah halaman kosong di sini.
Bagaimana Anda mengeja nama Anda? >> Anita.
Oke, Anita.
Katakanlah simpul * anita = lucas.
Yah, kita tidak harus memanggil Anda lucas. Kita harus menghubungi Anda terlebih dahulu.
Mengapa ini sebenarnya sesuai dengan kenyataan di sini?
Satu, pertama sudah ada.
Pertama telah dialokasikan mungkin di suatu tempat di sini.
Node * pertama, dan itu sudah dialokasikan daftar entah bagaimana.
Saya tidak tahu bagaimana itu bisa terjadi. Itu terjadi sebelum kelas dimulai.
Ini linked list manusia telah diciptakan.
Dan sekarang pada titik ini dalam kisah-ini semua terjadi Facebook rupanya nanti-
pada titik ini dalam cerita, Anita telah diinisialisasi menjadi sama dengan pertama,
yang tidak berarti bahwa Anita poin di Lucas.
Sebaliknya, ia menunjuk pada apa yang ia menunjuk pada
karena alamat yang sama itu dalam 32 Lucas bit -, 1 2, 3 -
sekarang juga dalam 32 Anita bit -, 1 2, 3.
>> Sekarang menemukan 22. Bagaimana Anda pergi tentang melakukan ini?
Apa itu Point? >> Apa pun.
Gunanya untuk apa, jadi lanjutkan dan bertindak keluar sebagai yang terbaik Anda dapat di sini.
Bagus, bagus, dan sekarang Anda sedang menunjuk-siapa namamu dengan 22?
Ramon. >> Ramon, sehingga Ramon adalah mengangkat 22.
Anda sekarang telah melakukan cek.
Apakah Ramon == 22, dan jika demikian, misalnya, kita bisa kembali benar.
Mari saya-sementara orang-orang ini berdiri di sini agak canggung-
biarkan aku melakukan sesuatu dengan cepat seperti bool menemukan.
Aku akan pergi ke depan dan mengatakan (node ​​* Daftar, int n).
Aku akan segera kembali dengan kalian. Aku hanya harus menulis beberapa kode.
Dan sekarang aku akan pergi ke depan dan melakukan hal ini, simpul * anita list =.
Dan aku akan pergi ke depan dan mengatakan sementara (anita = NULL!).
>> Metafora di sini semakin sedikit membentang, tapi sementara (anita = NULL!), Apa yang ingin saya lakukan?
Aku butuh cara referensi
integer yang Anita menunjuk.
Di masa lalu, ketika kami memiliki struktur, yang simpul adalah,
kami menggunakan notasi titik, dan kita akan mengatakan sesuatu seperti
anita.n, tapi masalah di sini adalah bahwa Anita bukanlah struct per se.
Apa dia?
Dia pointer, sehingga benar-benar, jika kita ingin menggunakan dot notasi-
dan ini akan terlihat sengaja sedikit samar-
kita harus melakukan sesuatu seperti pergi ke tangan kiri apapun Anita menunjuk pada
dan kemudian mendapatkan lapangan disebut n.
Anita pointer, tapi apa * anita?
Apa yang Anda temukan ketika Anda pergi ke apa Anita yang menunjuk?
Sebuah struct, node, dan node, recall, memiliki medan disebut n
karena telah, ingat, ini 2 bidang, selanjutnya dan n,
bahwa kita melihat beberapa saat yang lalu di sini.
>> Untuk benar-benar meniru ini dalam kode,
kita bisa melakukan ini dan mengatakan jika ((* anita). n == n), n yang saya cari.
Perhatikan bahwa fungsi disahkan pada nomor saya peduli.
Lalu aku bisa pergi ke depan dan melakukan sesuatu seperti return true.
Lain, jika itu tidak terjadi, apa yang ingin saya lakukan?
Bagaimana cara menerjemahkan untuk kode apa Anita melakukannya secara intuitif dengan berjalan melalui daftar?
Apa yang harus saya lakukan di sini untuk mensimulasikan Anita mengambil langkah yang ke kiri, langkah yang ke kiri?
[Respon siswa terdengar] >> Apa itu?
[Respon siswa tidak terdengar]
Baik, bukan ide yang buruk, namun di masa lalu, ketika kita sudah melakukan ini, kami telah melakukan anita + +
karena itu akan menambahkan angka 1 sampai Anita,
yang biasanya akan menunjuk pada orang berikutnya, seperti Ramon,
atau orang di sampingnya, atau di sampingnya orang di telepon.
Tapi itu tidak cukup baik di sini karena apa hal ini terlihat seperti dalam memori?
Bukan itu. Kita harus menonaktifkan itu.
Ini terlihat seperti ini dalam memori, dan meskipun saya sudah ditarik 1 dan 2 dan 3 dekat satu sama lain,
jika kita benar-benar mensimulasikan ini-bisa kalian, sementara masih menunjuk pada orang yang sama,
dapat beberapa dari Anda mengambil langkah mundur acak, beberapa dari Anda langkah acak maju?
>> Kekacauan ini masih merupakan linked list,
tapi orang-orang bisa di mana saja dalam memori,
jadi anita + + tidak akan bekerja mengapa?
Apa yang ada di lokasi anita + +?
Siapa tahu.
Ini beberapa nilai lain yang kebetulan akan sela
di antara semua node secara kebetulan karena kita tidak menggunakan array.
Kami dialokasikan masing-masing node individual.
Oke, jika kalian dapat membersihkan diri kembali.
Biarkan saya mengusulkan bahwa bukan anita + +, kita bukannya melakukan anita mendapat-
baik, kenapa tidak kita pergi ke apapun Anita yang menunjuk dan kemudian melakukan. selanjutnya?
Dengan kata lain, kita pergi ke Ramon, siapa yang memegang nomor 22,
dan kemudian selanjutnya adalah. seakan Anita akan menyalin pointer tangan kirinya.
Tapi dia tidak akan pergi lebih jauh dari Ramon karena kita menemukan 22.
Tapi itu akan menjadi ide. Sekarang, ini adalah berantakan dewa-mengerikan.
Jujur, tak seorang pun akan mengingat sintaks ini, dan jadi untungnya,
itu sebenarnya disengaja-oh sedikit, Anda tidak benar-benar melihat apa yang saya tulis.
Hal ini akan lebih menarik jika Anda bisa. Voila!
>> Di belakang layar, saya memecahkan masalah dengan cara ini.
Anita, untuk mengambil langkah ke kiri,
pertama, kami pergi ke alamat yang Anita menunjuk
dan di mana dia akan menemukan tidak hanya n, yang kita hanya memeriksa demi perbandingan itu,
tetapi Anda juga akan menemukan berikutnya - dalam hal ini,
Tangan kiri Ramon menunjuk ke node berikutnya dalam daftar.
Tapi ini adalah kekacauan dewa-mengerikan yang saya disebut sebelumnya,
tapi ternyata C memungkinkan kita menyederhanakan ini.
Alih-alih menulis (* anita), kita malah bisa hanya menulis anita-> n,
dan itu hal yang sama persis secara fungsional, tapi itu jauh lebih intuitif,
dan itu jauh lebih konsisten dengan gambar yang kita telah menggambar
selama ini menggunakan panah.
>> Terakhir, apa yang perlu kita lakukan di akhir program ini?
Ada satu baris kode yang tersisa.
Kembali apa?
Salah, karena jika kita melewati keseluruhan sementara loop
dan Anita adalah, pada kenyataannya, nol, itu berarti dia pergi semua jalan ke akhir daftar
di mana dia menunjuk-siapa namamu lagi?
Ari >> Ari. Ini tangan kiri, yang adalah null.
Anita sekarang nol, dan aku sadar kau hanya berdiri di sini canggung dalam limbo
karena aku pergi pada monolog di sini,
namun kami akan melibatkan Anda lagi hanya dalam beberapa saat.
Anita nol pada titik dalam cerita, sehingga loop sementara berakhir,
dan kami harus kembali palsu karena jika dia mendapat semua jalan ke pointer nol Ari
maka tidak ada nomor yang dia mencari dalam daftar.
Kita dapat membersihkan ini juga, tapi ini adalah implementasi yang cukup baik maka
dari fungsi traversal, menemukan fungsi untuk linked list.
Ini masih pencarian linear, tapi tidak sesederhana + + pointer
atau + + variabel i karena sekarang kita tidak bisa menebak
di mana masing-masing node dalam memori.
Kami harus benar-benar mengikuti jejak remah roti atau, lebih khusus,
pointer, untuk mendapatkan dari satu node ke yang lain.
>> Sekarang mari kita coba satu sama lain. Anita, apakah Anda ingin kembali ke sini?
Mengapa kita tidak pergi ke depan dan mengalokasikan satu orang lainnya dari para penonton?
Malloc-siapa namamu? >> Rebecca.
Rebecca. Rebecca telah malloced dari penonton,
dan dia sekarang menyimpan nomor 55.
Dan tujuan yang ada sekarang adalah untuk Anita untuk menyisipkan
Rebecca ke linked list di sini di tempat yang sesuai.
Ayo ke sini sebentar.
Saya telah melakukan sesuatu seperti ini.
Saya telah melakukan * simpul. Dan siapa namamu lagi?
Rebecca. >> Rebecca, oke.
Rebecca mendapat malloc (sizeof (node)).
Sama seperti kita telah dialokasikan hal-hal seperti siswa dan yang lainnya di masa lalu,
kita perlu ukuran dari node, jadi sekarang Rebecca
menunjuk pada apa?
Rebecca memiliki dua bidang di dalam dirinya, salah satunya adalah 55.
Mari kita lakukan apa, rebecca-> = 55.
Tapi kemudian rebecca-> berikutnya harus-seperti sekarang, tangannya adalah jenis yang tahu?
Ini menunjuk pada beberapa nilai sampah, jadi mengapa tidak untuk mengukur baik
setidaknya kita melakukan ini sehingga tangan kiri sekarang di sisinya.
Sekarang Anita, mengambilnya dari sini.
Anda memiliki Rebecca yang telah dialokasikan.
Pergi ke depan dan menemukan di mana kita harus meletakkan Rebecca.
Baik, sangat baik.
Oke, baik, dan sekarang kami membutuhkan anda untuk memberikan sedikit arahan,
sehingga Anda telah mencapai Ari.
Tangan kirinya adalah null, tapi Rebecca jelas milik ke kanan,
jadi bagaimana kita harus mengubah ini linked list
dalam rangka untuk memasukkan Rebecca ke tempat yang tepat?
Jika Anda benar-benar bisa menggerakkan tangan kiri masyarakat sekitar yang diperlukan,
kami akan memperbaiki masalah itu.
Oke, baik, dan sementara itu, tangan kiri Rebecca sekarang di sisinya.
>> Itu terlalu mudah.
Mari kita coba mengalokasikan-kita hampir selesai, 20.
Oke, ayo naik.
20 telah dialokasikan, jadi biarkan aku pergi ke depan dan berkata lagi di sini
baru saja kita lakukan saad simpul *.
Kami memiliki malloc (sizeof (node)).
Kami kemudian melakukan sintaks yang tepat sama seperti yang kita lakukan sebelumnya selama 20,
dan saya akan melakukan NULL berikutnya =, dan sekarang terserah kepada Anita
untuk memasukkan Anda ke dalam linked list, jika Anda bisa memainkan peran yang sama persis.
Jalankan.
Oke, baik.
Sekarang pikirkan baik-baik sebelum Anda mulai bergerak tangan kiri sekitar.
Anda sejauh mendapat peran paling canggung saat ini.
Yang tangan harus dipindahkan terlebih dahulu?
Oke, tunggu, aku mendengar beberapa tidak ada itu.
Jika beberapa orang sopan ingin membantu mengatasi situasi yang canggung di sini.
Tangan kiri yang harus diperbarui pertama mungkin? Ya.
[Mahasiswa] itu Saad.
Oke, itu Saad, mengapa, meskipun?
[Respon siswa tidak terdengar]
Baik, karena jika kita bergerak-siapa namamu? >> Marshall.
Marshall, jika kita menggerakkan tangannya terlebih dahulu turun ke nol,
sekarang kita telah benar-benar yatim empat orang di daftar ini
karena ia adalah satu-satunya menunjuk Ramon dan semua orang ke kiri,
sehingga memperbarui pointer yang pertama adalah buruk.
Mari kita batalkan itu.
Baik, dan sekarang pergi ke depan dan menggerakkan tangan kiri tepat menunjuk Ramon.
Ini terasa berlebihan sedikit.
Sekarang ada dua orang menunjuk Ramon, tapi itu baik-baik saja
karena sekarang bagaimana lagi kita memperbarui daftar?
Apa sisi lain harus bergerak?
Sangat baik, kami sekarang memiliki kehilangan memori apapun?
Tidak, begitu baik, mari kita lihat apakah kita tidak dapat mematahkan ini sekali lagi.
>> Mallocing terakhir kalinya, nomor 5.
Semua jalan di belakang, datang pada turun.
Ini sangat menarik.
[Tepuk tangan]
Siapa nama Anda? >> Ron.
Ron, oke, Anda malloced sebagai nomor 5.
Kami baru saja dieksekusi kode yang hampir identik dengan ini
hanya dengan nama yang berbeda.
Sangat baik.
Sekarang, Anita, keberuntungan memasukkan nomor 5 ke dalam daftar sekarang.
Baik, dan?
Sangat baik, jadi ini benar-benar ketiga dari tiga total kasus.
Kami pertama kali punya seseorang di akhir, Rebecca.
Kami kemudian memiliki seseorang di tengah.
Sekarang kita memiliki seseorang di awal, dan dalam contoh ini,
sekarang kita harus memperbarui Lucas untuk pertama kalinya
karena elemen pertama dalam daftar sekarang harus menunjuk pada node baru,
yang, pada gilirannya, menunjuk pada jumlah node 9.
>> Ini adalah demonstrasi yang sangat canggung, aku yakin,
sehingga tepuk tangan meriah untuk orang-orang jika Anda bisa.
Nicely done.
Itu saja. Anda dapat menyimpan potongan kertas Anda sebagai memori kecil.
Ternyata bahwa melakukan hal ini dalam kode
tidak sesederhana hanya bergerak tangan di sekitar
dan menunjuk pointer pada hal yang berbeda.
Tapi menyadari bahwa ketika tiba saatnya untuk melaksanakan sesuatu seperti
linked list atau varian dari itu jika Anda benar-benar fokus pada
ini dasar fundamental, gigitan-ukuran masalah yang saya harus mencari tahu,
apakah ini tangan atau tangan ini, menyadari bahwa apa yang dinyatakan sebuah program yang cukup kompleks
dapat, pada kenyataannya, dikurangi menjadi blok bangunan yang cukup sederhana seperti ini.
>> Mari kita mengambil hal-hal ke arah yang lebih canggih masih.
Kami sekarang memiliki gagasan linked list.
Kami juga memiliki-berkat usulan kembali ke sana-daftar ganda terkait,
yang terlihat hampir sama, tapi sekarang kita memiliki dua pointer dalam struct
bukan satu, dan kita mungkin bisa menyebut mereka pointer sebelumnya dan berikutnya
atau kiri atau kanan, tetapi kita, pada kenyataannya, membutuhkan dua dari mereka.
Kode akan menjadi sedikit lebih terlibat.
Anita akan harus melakukan pekerjaan lebih lanjut di sini di atas panggung.
Tapi kita pasti bisa menerapkan semacam struktur.
Dalam hal waktu berjalan, meskipun, apa yang akan menjadi waktu berjalan
Anita untuk menemukan a n nomor dalam linked list sekarang?
O masih besar n, jadi tidak lebih baik daripada pencarian linear.
Kita tidak bisa melakukan pencarian biner, meskipun, lagi.
Mengapa bahwa kasus tersebut? Anda tidak bisa melompat-lompat.
Meskipun kita jelas melihat semua manusia di atas panggung,
Anita dan bisa eyeballed itu dan berkata, "Inilah tengah daftar,"
dia tidak akan tahu bahwa jika dia adalah program komputer
karena satu-satunya dia harus kait pada pada awal skenario
adalah Lucas, yang merupakan pointer pertama.
Dia tentu akan harus mengikuti link tersebut,
menghitung cara sampai dia menemukan kira-kira tengah,
dan bahkan kemudian, dia tidak akan tahu kapan dia mencapai tengah
kecuali dia pergi sepanjang jalan sampai akhir untuk mengetahui berapa banyak ada,
maka backtracks, dan itu juga akan sulit kecuali jika Anda memiliki
daftar ganda terkait dari beberapa macam.
>> Memecahkan beberapa masalah saat ini, tapi memperkenalkan orang lain.
Bagaimana struktur data yang berbeda sama sekali?
Ini adalah foto dari nampan di Mather House,
dan dalam kasus ini, kami memiliki struktur data kami juga jenis sudah bicarakan.
Kami berbicara tentang tumpukan dalam konteks memori,
dan itu semacam sengaja bernama karena tumpukan dalam hal memori
secara efektif struktur data yang memiliki lebih banyak barang dan lebih berlapis-lapis di atasnya.
Tetapi hal menarik tentang stack, seperti yang terjadi dalam kenyataan,
adalah bahwa itu adalah jenis khusus dari struktur data.
Ini adalah struktur data dimana elemen pertama dalam
adalah elemen terakhir keluar.
Jika Anda adalah baki pertama untuk diletakkan ke dalam stack,
Anda akan menjadi sayangnya baki terakhir yang diambil dari tumpukan,
dan itu tidak selalu hal yang baik.
Sebaliknya, Anda dapat berpikir tentang hal sebaliknya,
yang terakhir dalam adalah keluar pertama.
>> Sekarang, apakah ada skenario datang ke pikiran di mana memiliki setumpuk
struktur data di mana Anda memiliki properti yang
yang terakhir, keluar pertama, sebenarnya menarik?
Apakah itu hal yang baik? Apakah itu hal yang buruk?
Ini jelas merupakan suatu hal yang buruk jika nampan tidak semua identik
dan mereka semua warna yang berbeda khusus atau entah apa lagi,
dan warna yang Anda inginkan adalah semua jalan di bagian bawah.
Tentu saja, Anda tidak bisa mendapatkan bahwa tanpa usaha yang besar.
Anda harus mulai dari atas dan bekerja dengan cara Anda ke bawah.
Demikian pula, bagaimana jika Anda adalah salah satu dari anak-anak ini fan
yang menunggu sepanjang malam berusaha untuk mendapatkan iPhone dan berbaris
di tempat seperti ini?
Bukankah lebih baik jika Apple store
adalah struktur data stack?
Yay? Nay?
Ini hanya baik untuk orang-orang yang muncul di menit terakhir
dan kemudian mendapatkan dipetik dari antrian.
Dan pada kenyataannya, fakta bahwa aku begitu ingin mengatakan antrian
sebenarnya konsisten dengan apa yang kita sebut semacam ini struktur data,
satu kenyataan dimana urutan tidak peduli,
dan Anda ingin yang pertama untuk menjadi yang pertama keluar
jika hanya demi keadilan manusia.
Kita umumnya akan menyebut bahwa struktur data antrian.
>> Ternyata selain daftar terhubung, kita dapat mulai menggunakan ide-ide dasar yang sama
dan mulai menciptakan jenis baru dan berbeda dari solusi untuk masalah.
Misalnya, dalam kasus tumpukan, kita bisa mewakili stack
menggunakan struktur data seperti ini, saya akan mengusulkan.
Dalam hal ini, saya telah menyatakan struct, dan saya sudah mengatakan dalam struktur ini
adalah array angka dan kemudian ukuran yang disebut variabel,
dan saya akan menelepon hal ini stack.
Sekarang, mengapa hal ini benar-benar bekerja?
Dalam kasus stack, aku bisa menggambar efektif ini pada layar sebagai array.
Berikut ini adalah tumpukan saya. Mereka adalah nomor saya.
Dan kita akan menarik mereka karena hal ini, ini, ini, ini, ini.
Dan kemudian saya memiliki beberapa anggota data lain di sini,
yang disebut ukuran, jadi ini adalah ukuran, dan ini adalah angka,
dan kolektif, iPad penuh di sini merupakan salah satu struktur tumpukan.
Sekarang, secara default, ukuran yang mungkin harus diinisialisasi ke 0,
dan apa yang ada di dalamnya dari array nomor awalnya
ketika saya pertama kali mengalokasikan array?
Sampah. Siapa yang tahu? Dan itu tidak benar-benar peduli.
Tidak masalah jika ini adalah 1, 2, 3, 4, 5, benar-benar acak
oleh nasib buruk yang tersimpan dalam struktur saya karena selama saya tahu bahwa ukuran tumpukan
adalah 0, maka saya tahu pemrograman, tidak melihat salah satu elemen dalam array.
Tidak peduli apa yang ada.
Jangan melihat mereka, seperti yang akan implikasi dari ukuran 0.
>> Tapi rasa sekarang aku pergi ke depan dan memasukkan sesuatu ke dalam stack.
Saya ingin memasukkan nomor 5, jadi saya memasukkan nomor 5 di sini,
dan kemudian apa yang harus saya meletakkan di sini?
Sekarang aku benar-benar akan meletakkan 1 untuk ukuran,
dan sekarang tumpukan adalah ukuran 1.
Bagaimana jika saya pergi ke depan dan masukkan nomor, katakanlah, 7 berikutnya?
Hal ini kemudian akan diperbarui untuk 2, dan kemudian kita akan melakukan 9,
dan kemudian ini akan diperbarui untuk 3.
Tapi fitur menarik sekarang dari tumpukan ini adalah bahwa
Aku harus menghapus elemen yang jika saya ingin pop
sesuatu dari tumpukan, sehingga untuk berbicara?
9 akan menjadi hal pertama untuk pergi.
Bagaimana seharusnya gambar berubah jika saya ingin pop elemen dari tumpukan,
banyak seperti nampan di Mather?
Ya >> [Siswa] Ukuran Set ke 2..
Tepat, semua saya lakukan adalah mengatur ukuran 2, dan apa yang harus saya lakukan dengan array?
Saya tidak perlu melakukan apa-apa.
Aku bisa, hanya untuk menjadi anal, menempatkan 0 ada atau -1 atau sesuatu untuk menandakan
bahwa ini bukan nilai yang legit, tapi itu tidak masalah karena
Saya dapat merekam luar dari array itu sendiri berapa lama
sehingga saya tahu hanya melihat dua elemen pertama dalam array ini.
Sekarang, jika saya pergi dan menambahkan nomor 8 ke array ini, bagaimana mengubah gambar selanjutnya?
Ini menjadi 8, dan ini menjadi 3.
Aku memotong beberapa sudut di sini.
Sekarang kita memiliki 5, 7, 8, dan kami sudah kembali ke ukuran 3.
Ini sangat sederhana untuk menerapkan,
tetapi ketika kita akan menyesali keputusan ini desain?
Ketika melakukan hal-hal mulai pergi sangat, sangat salah? Ya.
[Respon siswa tidak terdengar]
Bila Anda ingin kembali dan mendapatkan elemen pertama Anda meletakkan masuk
>> Ternyata di sini meskipun stack adalah array di bawah tenda,
struktur data ini kita sudah mulai berbicara tentang juga umumnya dikenal sebagai
abstrak struktur data dimana bagaimana mereka diimplementasikan
benar-benar selain titik.
Sebuah struktur data seperti tumpukan yang seharusnya untuk menambahkan dukungan
operasi seperti push, yang mendorong baki ke dalam stack,
dan pop, yang menghilangkan elemen dari tumpukan, dan hanya itu.
Jika Anda adalah untuk men-download kode orang lain yang sudah dilaksanakan
Hal ini disebut stack, orang itu akan ditulis
hanya dua fungsi untuk Anda, mendorong dan pop, yang satu-satunya tujuan dalam hidup
akan melakukan hal itu.
Anda atau dia yang melaksanakan program yang
akan menjadi sepenuhnya satu untuk memutuskan bagaimana menerapkan
semantik mendorong dan muncul di bawah tenda
atau fungsi mendorong dan muncul.
Dan aku telah membuat keputusan yang agak rabun sini
dengan menerapkan tumpukan saya dengan struktur data sederhana mengapa?
Ketika hal ini istirahat struktur data?
Pada titik manakah saya harus kembali kesalahan ketika pengguna memanggil mendorong, misalnya?
[Siswa] Jika tidak ada lebih banyak ruang.
Tepat, jika ada ruang lagi, jika saya sudah melebihi kapasitas,
yang semua topi karena menunjukkan bahwa itu semacam konstanta global.
Nah, maka aku hanya akan harus mengatakan, "Maaf, saya tidak dapat mendorong nilai lain
ke stack, "banyak seperti di Mather.
>> Pada titik tertentu, mereka akan memukul bagian atas lemari kecil itu.
Tidak ada lebih banyak ruang atau kapasitas dalam stack, di mana titik ada beberapa jenis kesalahan.
Mereka harus meletakkan elemen di tempat lain, nampan tempat lain,
atau tidak sama sekali.
Sekarang, dengan antrian, kita bisa menerapkannya sedikit berbeda.
Antrian adalah sedikit berbeda dalam bahwa di bawah tenda, dapat dilaksanakan
sebagai sebuah array, tapi mengapa, dalam kasus ini, saya mengusulkan
juga memiliki unsur kepala mewakili kepala daftar,
depan daftar, orang pertama dalam antrean di toko Apple, selain ukurannya?
Mengapa saya perlu sepotong tambahan data di sini?
Pikirkan kembali apa angka adalah
jika saya sudah ditarik sebagai berikut.
Misalkan sekarang ini adalah antrian bukannya stack,
perbedaan menjadi-seperti antrian toko-Apple adil.
Orang pertama dalam antrean di awal daftar, nomor 5 dalam hal ini,
dia atau dia akan membiarkan ke toko pertama.
Mari kita lakukan itu.
Misalkan bahwa ini adalah keadaan antrian saya saat ini dalam waktu, dan sekarang toko Apple
membuka dan orang pertama, nomor 5, dipimpin ke toko.
Bagaimana cara mengubah gambar sekarang bahwa saya telah de-antri orang pertama
di garis depan?
Apa itu >> [Mahasiswa]? Mengubah antrian.
Mengubah kepala, sehingga 5 menghilang.
Pada kenyataannya, itu seolah-olah-cara terbaik untuk melakukan hal ini?
Pada kenyataannya, itu seolah-olah orang ini menghilang.
Apa yang akan dilakukan di nomor 7 toko yang sebenarnya?
Mereka akan mengambil langkah besar ke depan.
>> Tapi apa yang telah kita datang untuk menghargai ketika datang ke array
dan bergerak hal-hal di sekitar?
Itu semacam membuang-buang waktu Anda, kan?
Kenapa kau harus begitu anal untuk memiliki orang pertama
pada awal baris pada fisik awal sepotong memori?
Itu sama sekali tidak perlu. Kenapa?
Apa yang bisa saya hanya ingat bukan >> [respon siswa tidak terdengar]?
Tepat, saya hanya bisa mengingat dengan kepala anggota data tambahan
bahwa sekarang kepala daftar tidak lagi 0, yang itu beberapa saat yang lalu.
Sekarang sebenarnya nomor 1. Dengan cara ini, saya mendapatkan optimasi sedikit.
Hanya karena aku sudah de-antri seseorang dari garis pada awal baris di toko Apple
tidak berarti setiap orang harus bergeser, dimana recall adalah operasi linear.
Saya malah bisa menghabiskan waktu konstan hanya
dan mencapai kemudian respon lebih cepat.
Tapi harga saya membayar adalah apa untuk mendapatkan bahwa kinerja tambahan
dan tidak harus menggeser semua orang?
Ya >> [respon siswa tidak terdengar].
Dapat menambahkan lebih banyak orang, baik, masalah yang ortogonal
dengan fakta bahwa kita tidak bergeser orang di sekitar.
Ini masih array, jadi apakah atau tidak kita menggeser orang atau tidak-
oh, saya melihat apa yang Anda maksud, oke.
Sebenarnya, saya setuju dengan apa yang Anda katakan dalam sehingga hampir seolah-olah
kita sekarang tidak akan pernah menggunakan awal dari array ini lagi
karena jika saya menghapus 5, maka saya menghapus 7.
Tapi aku hanya menempatkan orang-orang ke kanan.
>> Rasanya seperti aku menyia-nyiakan ruang, dan akhirnya antrian saya hancur menjadi apa-apa,
jadi kami hanya bisa memiliki sampul orang,
dan kita bisa memikirkan array ini benar-benar sebagai semacam struktur melingkar,
tapi kita menggunakan apa yang operator di C untuk melakukan itu semacam sampul?
[Respon siswa terdengar] >> Operator modulo.
Ini akan menjadi sedikit mengganggu untuk memikirkan bagaimana Anda melakukannya sampul tersebut,
tapi kita bisa melakukannya, dan kita bisa mulai menempatkan orang pada apa yang digunakan untuk menjadi garis depan,
tapi kita hanya ingat dengan variabel kepala yang kepala sebenarnya garis sebenarnya.
Bagaimana jika, sebaliknya, tujuan kami pada akhirnya, meskipun,
adalah untuk mencari nomor, seperti yang kita lakukan di sini di atas panggung dengan Anita,
tapi kami benar-benar ingin yang terbaik dari semua dunia?
Kami ingin kecanggihan lebih dari array yang memungkinkan
karena kami ingin kemampuan untuk secara dinamis menumbuhkan struktur data.
Tapi kita tidak mau harus resor untuk sesuatu yang kita menunjukkan
dalam kuliah pertama adalah bukan merupakan algoritma optimal,
bahwa pencarian linear.
Ternyata bahwa Anda bisa, pada kenyataannya, mencapai
atau setidaknya dekat dengan waktu yang konstan, dimana seseorang seperti Anita,
jika dia mengkonfigurasi struktur data untuk tidak menjadi linked list,
tidak menjadi stack, tidak menjadi antrian, bisa, pada kenyataannya,
datang dengan struktur data yang memungkinkan dia untuk melihat hal-hal,
bahkan kata-kata, bukan hanya angka, dalam apa yang kita akan menelepon waktu yang konstan.
>> Dan pada kenyataannya, melihat ke depan, salah satu psets di kelas ini hampir selalu
pelaksanaan pemeriksa ejaan, dimana
kami memberikan lagi beberapa kata dalam bahasa Inggris 150.000 dan tujuannya adalah untuk
memuat mereka ke dalam memori dan cepat bisa menjawab pertanyaan-pertanyaan dalam bentuk
adalah kata ini dieja dengan benar?
Dan itu benar-benar akan mengisap jika Anda harus iterate melalui semua 150.000 kata untuk menjawab itu.
Tapi, pada kenyataannya, kita akan melihat bahwa kita dapat melakukannya dalam waktu yang sangat, sangat cepat.
Dan itu akan melibatkan sesuatu yang menerapkan disebut tabel hash,
dan meskipun pada pandangan pertama hal ini disebut tabel hash akan
mari kita mencapai waktu respon yang cepat Super,
ternyata memang ada masalah.
Ketika tiba saatnya untuk melaksanakan hal ini disebut-lagi, aku melakukannya lagi.
Saya satu-satunya di sini.
Ketika tiba saatnya untuk melaksanakan hal ini disebut tabel hash,
kita akan harus membuat keputusan.
Seberapa besar hal ini harus benar-benar menjadi?
Dan ketika kita mulai memasukkan ke nomor ini tabel hash,
bagaimana kita akan menyimpannya dalam sedemikian rupa
bahwa kita bisa mendapatkan mereka kembali secepat yang kita punya mereka di?
Tapi kita akan lihat sebelum panjang yang pertanyaan ini
ketika ulang tahun semua orang adalah di kelas akan cukup erat.
Ternyata bahwa di ruangan ini, kita punya beberapa ratus orang,
sehingga kemungkinan bahwa dua dari kita memiliki ulang tahun yang sama mungkin cukup tinggi.
Bagaimana jika hanya ada 40 dari kami di ruangan ini?
Apa kemungkinan dua orang memiliki ulang tahun yang sama?
[Siswa] Lebih dari 50%.
Ya, lebih dari 50%. Bahkan, aku bahkan membawa grafik.
Ternyata-dan ini benar-benar hanya menyelinap pratinjau-
jika hanya ada 58 dari kita di ruangan ini, kemungkinan 2 dari kami
memiliki ulang tahun yang sama adalah sangat tinggi, hampir 100%,
dan itu akan menyebabkan sejumlah besar terluka bagi kita pada hari Rabu.
>> Dengan mengatakan bahwa, mari kita menunda sini. Kami akan melihat Anda pada hari Rabu.
[Tepuk tangan]
[CS50.TV]