[音樂播放] [視頻回放] - 他在說謊。 - 關於什麼？ - 我不知道。 - 所以我們怎麼知道？ - 即在9:15，雷 Santoya是在自動取款機。 - 是啊。 所以，問題是，什麼樣 是他在9:16做什麼？ -Shooting的9毫米的東西。 也許他看到了狙擊手。 - 或者是和他一起工作。 -Wait。 回到之一。 - 什麼，你看到了什麼？ -Bring臉上了整個屏幕。 -His眼鏡。 - 存在的一種反映。 - 它是在努埃維塔斯棒球隊。 這是他們的標誌。 - 和他交談 誰穿著那件夾克衫。 [結束播放] DAVID馬蘭：好的。 這是CS50，這是一個有點多 的[聽不清]與你 有問題的涉足設4。 今天我們先來了解一下多一點 深入這些東西叫做三分球， 這即使它 一個非常神秘的話題， 事實證明，這是怎麼回事 是通過何種途徑，我們 可以開始構建和組裝 更複雜的方案。 但是我們做到了上週三 一些粘土動畫的第一種方式。 所以這一點，召回，是 賓基，我們用他 要看一看一個程序， 真的沒有做什麼有趣的事， 但它確實揭示了一些問題。 因此，為了從今天開始，我們為什麼不走 快速通過幾個步驟， 嘗試提煉到人的方面 什麼是怎麼回事 為什麼這是不好的，然後繼續前進 而真正開始構建的東西 這種技術？ 因此，這些是第一 該程序中的兩行 在通俗地說，是什麼 在這兩條線在做什麼？ 有人誰是相當舒適 用什麼屏幕上的聲明？ 什麼是這兩條線在做什麼？ 這還不是所有的 從一周不同， 但有一些新的特殊符號。 是嗎？ 回到那裡。 聽眾：聲明指針？ DAVID馬蘭：再說一遍嗎？ 聽眾：聲明指針？ DAVID馬蘭：聲明指針和 讓我們來完善它多一點點。 聽眾：[聽不清] 地址X，那麼y。 DAVID馬蘭：然後解決。 那麼具體是什麼，我們正在做 是我們宣布的兩個變量。 這些變量，雖然，將會 是int類型的明星，哪 更具體地指 他們將要存儲 一個int的地址， 分別使用x和y。 現在還有什麼價值？ 有沒有在這些任何實際地址 兩個變量在這個時間點？ 第 這只是所謂的垃圾值。 如果你不實際分配 變量，無論是在RAM中 以前是要填補零 和那些這兩個變量。 但是，我們還不知道 它們是什麼，這就是 將是關鍵，為什麼賓基 上週失去了他的頭。 因此，這是粘土動畫 這個化身 因此你只有兩個變量， 小環形件粘土， 可以存儲的變量，但作為 該包裹起來箭頭提示， 他們不是真正指向 到任何地方本身已知。 於是，我們有這條線，這 是新的，上週的malloc內存 分配，這僅僅是一個奇特的方式 告訴操作系統，Linux的的 或Mac OS或Windows， 嘿，給我一些記憶， 而你要告訴 操作系統 就是要求它的內存時。 它不會去關心什麼 你會用它做什麼， 但你需要告訴工作 什麼系統由malloc的方式。 是嗎？ 聽眾：多少錢？ DAVID馬蘭：多少錢？ 多少字節，所以，這再次 一個人為的例子，只是說， 給我一個int的大小。 一個int現在，大小 是四字節或32位。 因此，這只是一種方式 他說，嘿，操作系統， 給我4個字節的內存 我可以用在我手上， 具體有哪些呢 malloc的收益相對於 以四個字節塊？ 聽眾：地址？ DAVID馬蘭：地址。 四個字節塊的地址。 沒錯。 所以這就是所儲存的最終 在x和這就是為什麼我們真的不 關心的是，數 地址是，無論是OX1或OX2 或者一些神秘的十六進制地址。 我們只關心形象化 那該變量x是現在 指向的內存塊。 這樣的箭頭表示的指針，或 更具體地說，存儲器地址。 但是再次，我們並不關心通常 什麼樣的實際地址。 現在，這條線說： 什麼通俗地說？ 星x被42分號。 這是什麼意思？ 你想去？ 不要劃傷你的脖子。 聽眾：x的地址是在42。 DAVID馬蘭：x的地址是42位。 不完全是。 如此接近，但並不完全，因為有 多數民眾贊成這個前綴X中的明星。 因此，我們需要調整一點點。 是嗎？ 聽眾：值了 指針x被指向的是42。 DAVID馬蘭：OK。 的值，該指針x是 指著，讓我們說，應是42， 或者換一種方式，星 x說，去到任何地址 在X，無論是1牛津 街或33牛津街 或OX1或ox33，無論 該數字地址， 明星x是x的間接引用。 所以去該地址並 然後把數字42出現。 因此，這將是一個 的話說，相當於途徑。 所以這一切都很好，然後 我們將代表圖像 如下所示，我們已經添加 42到四個是塊 字節上的右手邊，但 這條線是那裡的東西去了歪 和賓基的頭部彈出 關於這一點， 因為不好的事情發生時， 取消引用垃圾值 或取消引用無效 指針和我說無效 因為在這一點上，在 故事，什麼是Y的內部？ 什麼是Y的基礎價值 在過去的幾個步驟？ 是嗎？ 那是什麼？ 聽眾：一個地址。 DAVID馬蘭：地址。 它應是一個地址 但我初始化呢？ 所以我還沒有。 那麼，什麼是已知的在那裡？ 這只是一些垃圾的價值。 它可以是從零到任何地址 2十億，如果你的RAM 2演出， 或零4個十億，如果你已經 有4 GB的RAM。 這是一些垃圾的價值， 但問題是 操作系統， 如果沒有給你 該內存塊專 你試圖去， 它通常會導致什麼 我們已經看到了一個分段錯誤。 所以，事實上，任何你們誰 在掙扎於辦公時間問題 或者問題，更 通常，試圖找出 段錯誤， 這通常意味著 你觸摸的段 內存，你不應該。 你觸摸內存 操作系統有不 讓你觸摸，無論是 通過去太遠陣列 或者從現在開始，無論是 那是因為你接觸 內存僅僅是一些垃圾的價值。 這樣算下來星X這裡是 那種不確定的行為。 你不應該這樣做，因為賠率 是，該方案只是將崩潰， 因為你說， 去這個地址 你不知道在哪裡 該地址實際上是。 因此操作系統很可能 將你的程序崩潰 因此，事實上，這是 那裡發生的事情來賓基。 所以，最後，賓基固定 此問題與此。 這樣程序本身是有缺陷的。 但是，如果你之類的銳意進取 並執行此行，而不是， Ÿ度等於x只是意味著什麼 地址是一個X，也把它的年。 因此形象化，我們已經 有兩個箭頭表示這 從x和從y中指點 同一個地方。 因此語義，x等於 為y，因為這兩項的 都存儲相同 地址，ERGO指著42， 而現在，當你說明星 Y，轉到地址Y， 這有一個有趣的副作用。 因此，在y中的地址是 同樣的事情在X中的地址。 所以，如果你說去地址 在Y和值更改為13， 還有誰受影響？ X的，點D，可以這麼說， 應該受到影響。 事實上，尼克怎麼畫了這幅畫 在粘土動畫正是這一點。 即使我們按照指針 Y，我們結束了在同一個地方， 所以，如果我們要打印 出X或Y的指針對象， 那麼我們將看到13的值。 現在，我說指針對象是 與視頻一致。 程序員，我 知識，從來沒有真正 說一句話指針對象， 這是尖 在，但對於一致性 與視頻，實現 這一切，這是 意味著在這種情況下。 因此，對粘土動畫有任何疑問 或指針或malloc的，只是還沒有？ 沒有？ 好的。 因此，沒有進一步的 廢話不多說，讓我們一起來看看 在其中，這實際上已經 已經使用了一段時間。 因此，我們有這個CS50庫 這得到了所有這些功能。 我們使用調用getInt很多，GetString的， 也許更早GetLongLong 在我的PSET一左右，但 什麼實際已經持續？ 好吧，讓我們快速瀏覽一下 罩在一個程序下方那 激勵我們為什麼給你CS50 圖書館，實際上截至上週， 我們開始採取這些 訓練車輪關閉。 因此，這是現在排序 一個死後是什麼 已經持續 在CS50庫中， 即使我們現在將開始移動 遠離它對於大多數程序。 因此，這是一個名為scanf函數0的程序。 它的超級短。 它只是這些行，但它 引入了一個函數調用scanf函數 那我們究竟要看到 片刻CS50庫裡面， 儘管在一個稍微不同的形式。 所以這個方案行16 正在申報一個變量x。 所以給我四個字節為一個int。 它在告訴用戶， 號碼請，然後 這是一個有趣的行 上週實際聯繫在一起 而這一點。 scanf函數，然後發現它需要一個 格式字符串，就像printf的， ％我是指一個int，然後它需要一個 這看起來有點第二個參數 時髦。 它的符號x和召回， 我們只有這一次看到上週。 這是什麼符號的x代表？ C語言是什麼符號呢？ 是嗎？ 聽眾：地址。 DAVID馬蘭：的地址。 因此，它是相反的 星運營商， 而明星接線員說，去 這個地址，符號運算符 說，計算出 這個變量的地址， 所以這是關鍵，因為 scanf函數的人生目標 是掃描用戶的 從鍵盤輸入， 根據不管他或她 類型，然後讀取該用戶的輸入 成可變的，但我們 在過去兩個星期看到 這是交換功能，我們 試圖輕鬆實現 剛剛打破。 回想一下，與交換功能， 如果我們只是宣布A和B為整數， 我們也成功地交換 互換中的兩個變量 只是想用牛奶和OJ， 但只要換回來了， 結果是什麼就 x和y，原始值？ 什麼也沒有。 是啊。 什麼都沒有發生的時候，因為 掉期只改變它的本地副本， 這就是說，所有 這個時候，每當我們已經 被傳入的參數 到功能，我們 剛好路過的那些參數的拷貝。 你可以用那些 無論你想和他們在一起， 但他們將不得不無 上的原始值影響。 因此，這是有問題的，如果你 想擁有像scanf函數的函數 在生活中，其目的是要掃描 用戶的從鍵盤輸入 然後填補空白，所以 說話，就是給如x變量 一個值，因為如果我是 只是傳遞X到scanf函數， 如果你考慮最後的邏輯 本週，scanf函數可以為所欲為 與x的拷貝，但它不能 永久x更改，除非我們放棄 scanf的藏寶圖，可以這麼說， 因此，其中的X標記的位置， 我們通過x的地址，以便 scanf函數可以去那裡其實是一個改變 x的值。 所以，事實上，所有的 這個程序會 如果我做的scanf 0，在我的源代碼 5米目錄，使scanf函數0， 點斜線scanf函數，數 請50，感謝50。 因此，它不是那麼有趣， 但什麼是確實發生的事情 是，只要我打電話 的scanf這裡，x的值 被永久改變。 現在，這似乎不錯， 好，而且，事實上，它 看起來我們並不真正需要的 在CS50庫在所有了。 例如，讓我們運行 這一次在這裡。 讓我重新打開第二個。 讓我們嘗試了一些，請與 而不是說50像以前一樣， 我們只能說沒有。 OK，這是一個有點怪異。 確定。 而只是一些廢話這裡。 因此，它似乎並沒有 處理錯誤的情況。 因此，我們需要最小的開始 加入一些錯誤檢查 以確保用戶具有 鍵入的實際數目的像50， 因為很明顯打字的話 不被檢測為有問題的， 但它可能應該是。 讓我們來看看這個版本現在是 我試圖重新實現的GetString。 如果scanf函數有這一切 功能內置， 為什麼我們已經涉足這些 培訓車輪狀的GetString？ 好了，下面也許是我自己 簡單的GetString版本 因此一個星期前，我可能會說， 給我一個字符串，並將其命名為緩衝區。 今天，我要開始只是 話說焦明星，其中，召回， 它只是代名詞。 它看起來可怕，但它 同樣的事情。 所以給我一個變量叫做緩衝 那將存放的字符串， 告訴用戶字符串請 然後，就像以前一樣， 讓我們嘗試借用這一課的scanf ％S這個時候再通過緩衝區。 現在，一個快速的完整性檢查。 為什麼我不能說 符號緩衝這段時間？ 從前面的例子推斷。 聽眾：字符明星是一個指針。 DAVID馬蘭：沒錯， 因為這個時候，炭 星已經是一個指針，一個地址， 由明星在那裡的定義。 並且如果scanf的期望一個地址， 它足以只是為了打發在緩衝區中。 我不需要說了連字符緩衝區。 對於好奇的，你可以 做這樣的事情。 它將有不同的意義。 這會給你一個指針 一個指針，它實際上是 一個有效的東西在C中，但對於 現在，讓我們保持簡單 和保持故事的連貫。 我只是要傳遞 緩衝，這就是正確的。 這個問題雖然是這樣的。 讓我繼續前進，運行這個 編譯後的程序。 讓scanf函數1。 該死的，我的編譯器 抓住我的錯誤。 給我一秒鐘。 鏘。 比方說，scanf函數，1.C。 確定。 在那裡，我們走了。 我需要它。 CS50 ID有不同 配置設置 保護您免受自己。 我需要禁用那些 手動運行鐺這個時候。 所以字符串請。 我要繼續前進，並鍵入 在我最喜歡的Hello World。 OK，空。 這不是我所輸入的。 因此，它指示 什麼是錯的。 讓我繼續前進，鍵入 在很長的字符串。 感謝您的空，我不知道 如果我將能夠讓它崩潰。 讓我們試著一點點副本 粘貼，看看這會有所幫助。 剛貼了很多本。 這絕對是一個更大的 字符串比平常。 讓我們真的把它寫。 第 該死。 找不到命令。 所以這是不相關的。 那是因為我粘貼 一些不好的字， 但事實證明這是行不通的。 讓我們試試這個曾經多，因為 它更多的樂趣，如果我們真的崩潰了。 讓我們輸入這個，現在，我 要複製一個很長的字符串 現在就讓如果我們看看 可能會崩潰這件事。 請注意，我省略了空間和 新的生產線和分號 和所有時髦的人物。 輸入。 而現在的網絡只是正在緩慢。 我按住Command-V鍵太長，清晰。 該死！ 找不到命令。 確定。 那麼，問題是 儘管如此以下。 那麼什麼是真正會 與此聲明 的第16行字符星緩衝？ 所以，我是什麼讓 當我宣布一個指針？ 所有我得到是一個四字節的值 所謂的緩衝區，但什麼是它的內部 此刻？ 這只是一些垃圾的價值。 因為任何時候你聲明一個變量 在C，它只是一些垃圾的價值， 我們已經開始 絆倒這個現實。 現在，當我告訴scanf函數， 去這個地址 並把在不管用戶類型。 如果在用戶鍵入你好 世界上，還有，我在哪裡放呢？ 緩衝區是一個垃圾的價值。 所以這有點像一個箭頭 該指針誰知道在哪裡。 也許它指向 這裡在我的記憶中。 因此，當用戶 類型的hello world， 該計劃試圖把 字符串的hello world反斜線0 該內存塊。 但是高概率，但 顯然不是100％的概率， 計算機將要然後崩潰 程序，因為這不是 內存我應該被允許觸摸。 因此，在短期，這一計劃是 有缺陷的正是這個原因。 我根本沒有做什麼的？ 有哪些步驟我省略了，就像 我們省略了與賓基的第一個例子？ 是嗎？ 聽眾：內存分配？ DAVID馬蘭：內存分配。 我還沒有實際分配 任何內存該字符串。 所以我們可以在幾個方式解決這個問題。 第一，我們可以保持簡單 而事實上，現在你 將開始看到一個模糊 之間有什麼行 數組是什麼，一個字符串是什麼 炭明星，字符什麼數組 是。 下面是第二個例子 涉及字符串和通知 所有我已經在網上做了 16是不是說， 該緩衝區將是一個char 明星，一個指向一個內存塊， 我會很主動地給 我自己一個緩衝的16個字符， 而事實上，如果你熟悉 與術語緩衝， 大概從影片的世界裡， 其中，一個視頻緩衝，緩衝， 緩衝。 那麼，什麼是連接這裡？ YouTube的嘛，裡面 和視頻播放器內 通常是一個數組 這是大於16。 它可能是大小為一的陣列 兆字節，也許10兆， 進入該數組做您的瀏覽器 下載一個一大堆字節， 一大堆的兆字節 視頻和視頻播放器， YouTube的還是誰的，開始 從陣列讀取的字節數， 任何時候你看到的 字緩衝，緩衝， 這意味著該播放器具有 得到該數組的末尾。 該網絡是如此緩慢，它並沒有 回填數組有更多的字節 所以你出位 以顯示給​​用戶。 因此，緩衝區是一個恰當的詞在這裡是 它只是一個數組，一個內存塊。 這將解決這個問題 因為事實證明 你可以把數組，就好像 他們的地址，即使緩衝區 僅僅是一個符號，它是一個 字符序列，緩衝液， 這對我來說是非常有用的，程序員， 你可以通過周圍的名字 就好像它是一個 指針，就好像它 是一個組塊的地址 內存為16個字符。 所以這是說，我可以通過 scanf函數正是那個詞 所以現在，如果我做這個節目， 讓scanf函數2，點斜線scanf函數2， 和類型的hello world， 回車，即時間 - 嗯，什麼事？ 字符串請。 我做了什麼錯？ 世界您好，緩衝區。 世界，你好。 嗯，我知道它在做什麼。 確定。 因此，它的讀了 直到第一空間。 因此，讓我們騙了就一下 說我只是想輸入的東西 真的長的很像，這是一個長句子 這是一個，兩個，三個，四個，五個， 六，七，八，九， 10，11，12，13，14，15，16。 確定。 這的確是一個長句子。 所以，這句話是 長度超過16個字符 所以當我按下回車鍵， 什麼會發生？ 那麼，在的這種情況下， 故事，我宣布緩衝區 實際上是一個數組 有16個字符蓄勢待發。 這樣一，二，三，四，五，六， 七，八，九，十，十一，十二，十三，十四， 15，16。 所以16個字符，而現在，當我 讀這樣的事情是一個長期的 一句話，是什麼將要發生的 那我要讀這是一個漫長 S-E-N-T-E-N-C-E，句子。 因此，這是故意 一件壞事，我 不斷書寫超越 我的數組的邊界， 超出了我緩衝器的邊界。 我能得到幸運和程序 將繼續運行，並沒有在意， 但一般來說，這 確實會崩潰我的程序， 它是在一個錯誤我 代碼的那一刻，我一步 超越界限 該數組的，因為我 不知道這是否是 必然要崩潰 或者，如果我只是要得到幸運。 因此，這是有問題的，因為在 這種情況下，它似乎工作 讓我們鋌而走險這裡，即使 在IDE似乎容忍了不少 of-- 在那裡，我們走了。 最後。 所以我能看到這唯一的一個。 所以，我只是有很多好玩的打字 出了很長的實際短語 它肯定超過 16個字節，因為我 輸入在這個瘋狂的長期多線 短語，然後看到發生了什麼。 該程序試圖在打印 然後得到一個分段錯誤 和段錯誤是當 這樣的事情發生 和操作系統說 不，不能觸摸的記憶。 我們會殺了 該方案完全。 因此，這似乎是有問題的。 我已經提高了該計劃的實施 至少有一些記憶， 但是這似乎局限 該函數的GetString，這是讓 一些有限的長度為16的字符串。 所以，如果你想支持更長 句子超過16個字符， 你該怎麼辦？ 那麼，你可以增加 此緩衝器32的大小 或者說似乎有點短。 為什麼我們不只是做 它1000，但推回。 什麼是直覺的反應 只是通過避免這種問題 我的緩衝更大，像1000字符？ 通過實施GetString的這種方式。 什麼是好還是壞嗎？ 是嗎？ 聽眾：如果你綁定了很多 的空間，你不使用它， 那麼你就不能重新分配空間。 DAVID馬蘭：沒錯。 這是浪費的，只要你不 實際上需要那些字節的900 可是你要求 1000共無論如何， 你只是佔用更多的內存 比你需要到用戶的計算機上， 畢竟，一些 你已經遇到 在生活中，當你 運行很多程序 和他們吃了大量的內存， 這實際上可能會影響性能 和用戶的經驗 上的計算機中。 所以這是一種懶的解決方案， 可以肯定，相反， 這不僅造成浪費，什麼問題 仍然存在，即使我讓我的緩衝區 1000？ 是嗎？ 聽眾：字符串的長度為1001。 DAVID馬蘭：沒錯。 如果字符串的長度為1001， 你有相同的問題， 和我的觀點，我會 就在這時，使其2000年， 但你不知道 推進它應該多大， 然而，我必須編譯我的程序 之前，讓人們使用和下載 它。 因此，這也正是那種 東東的CS50庫嘗試 幫助我們，我們將只一瞥 一些底層實現的 這裡，但這是CS50點C.這 是一直在CS50 IDE文件 所有這幾個星期你一直在使用。 這是預編譯的。而你 一直在使用它自動 由具有的性質 衝大號CS50標誌鏗鏘， 但如果我向下滾動，通過所有的 這些功能，這裡是GetString的， 而只給你一個 什麼樣的味道是怎麼回事， 讓我們快速瀏覽一下 的相對複雜性。 這不是一個超長 功能，但我們沒有 必須考慮所有的硬盤約 如何去得到的字符串。 因此，這裡是我的緩衝區和我 顯然初始化為null。 當然，這是在 同樣的事情為char明星， 但我決定 實施CS50庫 如果我們要 是完全動態的， 我事先不知道有多大的根本 字符串用戶會希望得到的。 所以我要開始 只有一個空字符串 我要去建立盡可能多 記憶，因為我需要適合用戶字符串 如果我沒有 夠了，我要去問 操作系統為更多的內存。 我打算把他們的串 成的存儲器的更大的塊 我要去釋放或釋放 內存不夠大塊 我們正要 反复地做到這一點。 因此，快速瀏覽， 這裡只是一個變量 與我要去跟踪 的我的緩衝器的容量。 我多少字節可以裝？ 這裡有一個變量n與 而我要繼續 跟踪有多少字節實際上是 緩衝器或用戶已鍵入。 如果你還沒有見過這個，你 可以指定就像一個int變量 是無符號的，它顧名思義， 意味著它的非負的，為什麼會 我曾經想打擾指定 即一個int不只是一個int， 但它是一個unsigned int？ 這是一個非負的int。 什麼是[聽不清]是什麼意思？ 聽眾：它描述了一個量 內存，可以[聽不清]。 DAVID馬蘭：是的。 所以，如果我說的符號，這其實是 給你一個額外的內存一位 它似乎有點傻，但如果你 擁有更多的內存一位，那 意味著你有兩倍多 你可以代表值， 因為它可以是一個0或1。 因此，在默認情況下，一個int可以大致 負2十億一路 達正2十億。 這些都是大的範圍，但 它是一種浪費還是 如果你只關心 尺寸，這只是直覺 應該是非負或 正或0，那麼， 你為什麼要浪費2十億 為負數的可能值 如果你從來沒有打算使用它們？ 所以說無符號的，現在我的INT可以 介於0和約4十億。 因此，這裡只是一個int下原因 我們不會進入剛才的 為什麼它是一個int，而不是 一個char，但這裡是 發生了什麼事情的要點 上，並且一些你 可能使用，例如，在 即使在PSET 4龜etc功能 或之後，我們會看到它 又在問題設置五， 龜etc是不錯的，因為作為名稱 那種，有點arcanely表明， 這是一個函數， 獲取一個字符等等， 有什麼本質上的區別 什麼，我們正在做的GetString的 是我們沒有使用 scanf的以相同的方式。 我們沿著一步一步的只是爬行 以上的任何用戶已鍵入中， 因為我們總是可以分配一個 字符，所以我們總能安全地 看一個字符的時間，和 神奇的開始發生在這裡。 我要向下滾動到 此功能的中間 只是簡單介紹一下這個功能。 就像有一個 malloc函數，有 一個realloc函數，其中的realloc 讓你重新分配一塊內存 並使它更大或更小。 所以長話短說，並與 一波我的手今天， 知道什麼樣的GetString 正在做的是它的排序 的神奇成長或 緩衝收縮作為用戶 類型在他或她的字符串。 因此，如果用戶鍵入一個 短字符串，該代碼 僅分配足夠 存儲器以適應串。 如果用戶保持打字 我一次又一次做到了 又一次，好吧，如果 緩衝區的最初這個大 和程序實現，對 等一下，我的空間， 這將增加一倍 緩衝區的大小 然後加倍緩衝區的大小 而且確實增加一倍代碼， 如果我們看一下在這裡，它是 只是這個聰明的一班輪。 你可能沒見過這種語法 之前，但如果你說明星等於， 這是同樣的事情， 說產能的2倍。 因此，它只是不斷翻番 所述緩衝器的容量 然後告訴realloc的給 本身更多的內存。 現在，順便說一句，有 在這裡等功能 我們不會考慮任何細節 比其他的調用getInt顯示， 我們使用的GetString的調用getInt。 我們檢查，這不是 空，其中，召回， 是特殊的值， 意味著出事了。 我們是內存不足。 更好地檢查了。 而我們返回的警戒值。 但我會推遲到的意見，以 為什麼然後我們用這個表弟scanf函數的 所謂sscanf的和原來 該sscanf的，或字符串scanf函數， 讓你看看就行了 用戶鍵入，讓你 本質上分析它，就是我 這裡做的是我要告訴sscanf的， 分析任何用戶具有 鍵入並確保％我， 有在它的整數，並且我們不會 進入今天究竟為什麼有還 一％C在這裡，但簡而言之允許 我們檢測是否用戶已鍵入 在一些號碼後偽造的。 因此原因，調用getInt和GetString 告訴你重試，重試，重試 是因為所有的 我們編寫的代碼， 它種在看用戶的輸入 在確保它完全數字 或者它是一個真正的浮動 點值等， 這取決於什麼樣的價值 您正在使用的功能。 呼。 確定。 這是一個拗口 但問題在這裡 我們有原因 這些培訓車輪 是因為在最低水平， 還有就是這麼多的事情 可以去錯了，我們想 搶先處理 這些東西肯定是在 最早的幾個星期之類的， 但現在PSET四個PSET五 以後你會發現它更對 你還要你更強大 對解決這些類型的問題 你自己。 上的GetString或調用getInt有問題嗎？ 是嗎？ 聽眾：你為什麼會增加一倍 所述緩衝器的容量 而不是僅僅增加 它的具體數額？ DAVID馬蘭：好問題。 為什麼我們的身份倍增 緩衝器的相 只是增加它 一些常數值？ 這是一個設計決策。 我們剛剛決定，因為它往往 有點貴的時間，聰明的問 操作系統 內存，我們沒有 要最終進入 這種情況對於大串 我們被要求 連連操作系統 一次又一次的 快速連續的內存。 因此，我們剛剛決定，多少有些 任意但我們希望合理， 如此，你知道嗎，讓我們 試圖獲得超越自我 而只是一味增加了一倍它使 我們最小化的倍量 我們必須調用malloc或 realloc的，但總的判斷 在沒有知道的調用 什麼樣的用戶可能需要輸入內容。 這兩種方式可能是值得商榷的。 可以說不錯。 因此，讓我們來看看一對夫婦 的內存等副作用， 事情可能出錯 和工具，你可以 用它來捕獲這些類型的錯誤。 原來大家，即使 check50沒有告訴你一樣多， 一直在寫越野車 因為一個星期代碼， 即使所有check50測試 過去了，即使你和你的TF 超級信心 你的代碼按預期工作。 您的代碼已被馬車或 有缺陷的，所有的你， 在使用CS50庫 被洩漏內存。 你一直在問的操作系統 對於存儲器在大多數的節目 你寫的，但你 從來沒有真正賦予它回來。 你所謂的GetString 和調用getInt和GetFloat， 但GetString的，你 從來沒有所謂unGetString或給 返回的字符串或類似的，但我們已經看到 是的GetString確實分配內存 由malloc或方式這 功能realloc的，這僅僅是 在精神上非常相似， 然而，我們已經 詢問操作系統以 存儲器和存儲器連連 但從來沒有給它回來。 現在，順便說一句，事實證明， 當程序退出，所有內存 自動釋放。 所以它沒有一個巨大的交易。 它不會打破 IDE或放慢改革的步伐， 但是當程序執行 一般內存洩漏 而他們正在運行很長一段時間。 如果你見過那些愚蠢的小 在Mac OS或沙漏沙灘球 在Windows上它是一種 減緩或思考或思維 或者只是真正開始 慢如蝸牛， 它很可能可以 內存洩漏的結果。 誰寫的程序員 您正在使用的軟件 要求對內存的操作系統 每隔幾分鐘，每隔一小時。 但是，如果你正在運行的 軟件，即使是 最小化您的電腦 幾個小時或幾天， 你可能會問了越來越多 內存和從來沒有真正使用它 所以你的代碼可能是，或 程序可能洩漏內存， 如果你開始洩漏內存， 還有其他程序內存少， 而且其效果是 慢都記錄下來。 現在，這是迄今為止的一個 最殘暴的方案 你將有機會 在CS50運行，只要 作為其輸出甚至比更深奧 鏗鏘的或做的或任何命令 我們之前已經運行線方案，但 值得慶幸的是，鑲嵌在其輸出 一些超有用的技巧， 將是有益的無論是PSET 4 不然肯定P設定五位。 所以Valgrind是一個工具， 可用於看 程序中的內存洩漏。 這是相對簡單的運行。 你跑Valgrind的，然後，連 雖然這是一個有點冗長， 短跑衝刺洩漏檢查 等於滿，然後點 斜線和你的程序的名稱。 因此，Valgrind的會後運行程序 並在程序的最後 運行它退出前， 為您提供了另一個提示， 它會分析你的 雖然它已經正在運行的程序 並告訴你你洩露 任何內存和更好的是， 你觸碰內存 不屬於你？ 它無法趕上一切，但它的 在最醒目的東西很不錯。 因此，這裡是有經營我的一個例子 這個節目，有跑Valgrind的， 在調用程序 記憶，我要去 以突出的線條 最終我們感興趣的。 因此，有更多的分心 我已經從幻燈片中刪除。 但是，讓我們只看看這是什麼 程序能夠告訴我們的。 它能夠告訴我們的東西 像大小為4無效寫。 換句話說，如果你觸碰到內存， 特別是4字節的內存 你不應該有， 的valgrind可以告訴你。 無效的寫大小為4。 你感動了四個字節 你不應該有。 你在哪兒做的？ 這是美。 記憶點C線21就是你 搞砸了，這就是為什麼它是有幫助的。 就像GDB，它可以幫助 點你在實際的錯誤。 現在，這一個多一點 冗長的，如果不是混亂。 在1塊40個字節肯定 在負的戰績1 1的丟失。 這是什麼意思？ 嗯，這只是意味著你問 40個字節，你從來沒有給它回來。 你叫的malloc，或者您叫 GetString的和操作系統 給你40​​個字節，但你永遠不 釋放或者釋放內存， 而公平地說，我們從來沒有展示 你如何回饋內存。 原來有一個超 所謂的自由簡單的功能。 有一個參數的東西 你想免費或給予回复， 但40個字節，顯然， 這個方案 已經失去了線 內存20 C點。 因此，讓我們看到這個計劃。 這是超級沒用。 它不僅展現 此特定錯誤。 因此，讓我們一起來看看。 下面是主要的和主要的，通知，電話 一個函數調用f和再返回。 所以不是那麼有趣。 什麼是f執行？ 請注意，我並沒有原型麻煩。 我想保持代碼 盡可能小。 所以我把F時上部主 這很好，當然， 對於這樣的短期課程。 因此，F不返回任何東西和做 不能帶什麼，但它確實做到這一點。 它聲明，很像 在賓基例如， 一個名為x的指針是怎麼回事 存儲一個int的地址。 所以這是左手側。 在英語中，什麼是 右手邊做什麼？ 有人嗎？ 這是什麼做的我們呢？ 是嗎？ 聽眾：[聽不清] 倍int的大小 它是10倍，[聽不清] DAVID馬蘭：好，讓我來總結。 因此，分配足夠的空間為10整數 或10，什麼是一個int的大小， 它的四個字節，所以10次4 40，使右手邊，我已經 高亮顯示的是給我40個字節， 存儲第一字節的地址 成X個。 而現在最後，而這裡的地方 這個程序有錯誤，什麼是 錯線21基於該邏輯是什麼？ 有什麼不對線21？ 是嗎？ 聽眾：你不能 索引X [聽不清]。 DAVID馬蘭：是的。 我不該指數成X個這樣的。 所以語法，沒關係。 什麼是好的是，就像你 可以把一個數組名 就好像它是一個指針，同樣 你可以把一個指針，彷彿它是 一個數組，這樣我就可以在語法 例如x支架的東西，X架我， 但10是有問題的。 為什麼呢？ 聽眾：因為它不是內。 DAVID馬蘭：這不是 裡面的內存塊。 什麼是最大的價值，我應該 可以把這些方括號？ 9，0到9。 因為零索引。 因此，從0到9就可以了。 支架10是不好的， 但是，每一次回憶，雖然 我似乎盡量讓CS50的IDE 墜毀通過鍵入假值， 它並不總是合作， 而事實上，你經常 幸運只是因為 操作系統不 請注意，您可以輕微 通過一些內存塊， 因為你住在技術上 您的段，但更多介紹 在一個操作系統類， 所以像這樣 可以很容易被忽視。 你的程序永遠不會崩潰 持續但也許曾經在一段時間。 因此，讓我們嘗試的valgrind 這一點，和這裡的 在這裡，我們會變得不知所措 通過瞬間的輸出。 因此，請Valgrind的內存洩漏檢查 等於全點斜線內存。 這裡就是為什麼我保證 這將壓倒。 以下是Valgrind的，下面是 一個程序員，有些年份ago- 決定這將是一個好主意 為輸出的樣子。 因此，讓我們理解這一點。 因此，所有對左手的方式 側面沒有很好的理由 是程序的進程ID 我們只需運行，唯一標識符 對於該方案，我們只是跑。 我們刪除了從 滑動，但也有 在這裡一些有用的信息。 讓我們向上滾動到頂部。 這裡就是我們的開始。 因此，它不是所有的東西輸出。 下面是無效的寫 對21行大小4。 那麼，什麼是第21行？ 第21行正是 這一點，這是有道理的 我是在有效 寫4個字節，因為我 試圖把這個整數， 它可以是任何東西， 這恰好是 零，但是我想 把它在一個位置 這不屬於我。 此外，到這裡，40在一個字節 塊肯定是失去了在創紀錄的1。 這是因為當我調用malloc 在這裡，我從來沒有真正釋放內存。 那麼，如何才能解決這個問題？ 讓我繼續前進，是一個小更安全 並做9那兒，讓我在這裡免費的X。 這是新的功能，為今天。 如果我現在重新運行使內存點斜線， 讓我們在其上運行的valgrind再次， 最大限度地發揮我的窗口，然後按Enter。 現在，這是很好的。 他們埋葬好消息 在這一切的輸出。 所有堆塊是免費的。 我們會回來的東西堆 是，但無洩漏是可能的。 因此，這只是另一種 工具的工具箱 使用它可以開始 現在發現這樣的錯誤。 但是讓我們看看有什麼 更可以去錯在這裡。 現在讓我們來轉變 其實解決問題。 順便說一句，如果這將緩解一 混亂或緊張一點， 這是現在好笑。 是啊。 這是相當不錯的。 因為指針 地址和地址 一般都是按照慣例 寫的十六進制。 哈，哈，這個現在好笑。 總之，讓我們現在 其實解決的一個問題。 這一直是超級， 超低水平迄今為止， 而我們實際上可以做有益 事情與這些低級別的細節。 因此，我們介紹了幾個星期 前的陣列的概念。 數組是不錯的，因為 很難清理我們的代碼 因為如果我們想寫 程序有多個學生 或多個名稱和房屋及 宿舍，學院和所有這一切， 我們可以存儲的一切更 乾淨的陣列的內部。 但提出一個缺點 陣列的迄今。 即使你沒有自己遭受它 在一個程序，只是本能地， 什麼是壞事 有關陣列，也許？ 我聽到一些​​雜音。 聽眾：這很難 改變大小。 DAVID馬蘭：這很難 改變大小。 你不能改變大小 陣列的，實際上，本身 在C.你可以分配另一個數組， 從舊的移動一切 到新的，現在 有一些額外的空間， 但它不喜歡 如Java或Python語言 或任何數目的其他的 與語言的一些你 可能是熟悉的，你 可以只保留添加的東西 令人作嘔到數組的結尾。 當你有一個數組 大小6，這是它的大小， 和這麼多喜歡這個主意更早 具有一定大小的緩衝區， 你必須猜測出大門 你想要什麼尺寸它是什麼？ 如果你猜過大， 你就是在浪費空間。 如果你猜過小， 不能存儲的數據，至少 沒有更多的工作。 所以今天，多虧了指針，我們可以 開始拼接起來自己的自定義 數據結構，以及在 其實，這裡的東西 看起來有點多 神秘的第一眼， 但是這就是我們會打電話給一個鏈接 列表，它的名字樣的總結 它。 它的號碼的列表，或者在 這種情況下，數字的列表， 但它可能是任何一個列表，但 它連接在一起的箭頭的方式， 而只是採取一種猜測 有什麼方法 我們要能 縫合在一起， 有點像爆米花用線， 一個鍊錶矩形嗎？ 它的數字？ 什麼是底層語言功能？ 聽眾：一個指針。 DAVID馬蘭：一個指針。 所以，每一個箭在這裡代表 指針或只是一個地址。 因此，換句話說，如果我想 來存儲數字列表， 我不能只保存它，如果我想 增長和收縮的能力 我的數據結構中的陣列。 因此，我需要有一點 更複雜， 但是請注意，這 圖片一種暗示 如果你拿到的小線程 一切都連接在一起， 也許並不難，以騰出空間 其中的兩個矩形之間 兩個這些節點，因為我們將開始 美其名曰，放入一個新的節點， 然後用一些新的線程，只 溝三個節點一起， 第一個，最後一個，並且所述一個 您剛剛插入中間。 事實上鍊錶， 一個數組不同的，是動態的。 它可以成長，它可以 收縮而你不知道 有知道或關心提前如何 你要多少數據被存儲， 但事實證明，我們是一個小 小心如何實現這一點。 因此，首先讓我們來看看我們如何實現 其中一個小矩形。 這很容易實現一個int。 你剛才說INT n和再 你得到的4個字節為一個int， 但我怎麼得到一個int，正調用它， 再一個指針，讓我們稱之為下一個。 我們可以把這些 什麼東西我們要 但我需要一個自定義的數據結構。 是嗎？ 聽眾：＆符號[聽不清]。 DAVID馬蘭：所以符號，我們將用它來 獲得一個節點的地址可能。 但是，我們需要另一個 C的順序功能 給我創造的能力 這個自定義的矩形，這種風俗 變量，如果你願意，在內存中。 聽眾：一個結構。 DAVID馬蘭：一個結構。 從上週還記得，我們​​推出 結構，這種相對簡單的關鍵詞 這讓我們做這樣的事情。 Ç沒有配備數據 結構被稱為學生。 它配備了int和float和char和 這樣，但它不來學生， 但我們可以創建一個學生數據類型， 學生結構，這種語法 在這裡。 你會一次又一次地看到這一點。 所以不要擔心 記憶中的關鍵字， 但關鍵字，重要的是 只是一個事實，即我們所說的結構 然後我們把它稱為學生和內 學生的是一個名字和一個房子 或者宿舍等。 所以現在的今天，讓我們提出這一點。 我加了幾句話，但是如果我想 實現這個矩形的 既得到了一個int和 指針，你知道嗎，我 要聲明一個叫做節點結構。 我也是，在它的內部，會說 一個節點，這個矩形，有一個int 我們將稱之為n和 它具有一個下一個指針。 這是一個有點冗長， 但如果你仔細想想， 那些出現在畫面中的箭頭 剛才是什麼數據類型？ 每個這些箭頭的指向 數據結構是什麼類型？ 這不是指著剛本身一個int。 它指向 整個矩形的事情 那長方形的東西， 我們說，被稱為一個節點。 所以，我們種得 遞歸定義該這樣 一個節點，我們會說， 將包含一個名為-n的INT 並呼籲下及指針 數據結構的類型向其中 該指針指向顯然是 將是結構節點。 因此，這是煩人詳細 而剛需迂腐， 我們之所以不能 只是這麼一說，坦率地說 看起來很多更具可讀性， 是因為回想一下，C了解 東西從上到下，從左到右。 這不是直到我們得到了分號 該關鍵字的節點確實存在。 因此，如果我們希望有這樣的 數據的內部循環參考 結構，我們不得不這樣做，在哪裡 我們說結構節點在頂部，這 給我們描述了這樣一個更長的路 的事情，然後在裡面我們說結構節點， 然後在最後一行 我們說，沒事，C，順便說一下， 只需撥打這個整個該死 事情的一個節點，並停止 共使用關鍵字結構。 因此，這只是有點句法 伎倆，最終讓我們創造 一些看起來完全一樣。 因此，如果我們現在假設我們可以 用C實現這個東西， 我們如何做實際上 開始遍歷這個？ 唉，其實，我們所要做的就是 遍歷從左至右，只是 一種插入節點或刪除節點 或搜索東西的地方，我們希望， 但要做到這一點，讓我們繼續前進，使 事情變得更真實，因為這 已經超低水平迄今。 會有人從字面上想成為第一個？ 確定。 上來吧。 你叫什麼名字？ 大衛：大衛。 DAVID馬蘭：大衛。 認識你很高興。 我也是。 好的。 我們需要一個9號。 還不如先，也許是。 OK，號碼9。 一個數字17，請。 讓我回去遠了一點。 22號，請和 怎麼樣靠後 如果我能看到任何的手 與所有的光或沒有。 有人正在被自願在那裡。 難道你要來了？ 你的前臂用力往上走。 OK，17。 22。 26下來。 誰都想 forcefully--上來吧。 一個實際的志願者。 所以很快，如果 你們可以安排 自己只是喜歡 屏幕上的節點。 謝謝。 你會是26。 好吧，快速推出。 所以，我是大衛，你也是？ 大衛：大衛。 DAVID馬蘭：你是誰？ 傑克：傑克。 蘇：蘇。 亞歷克斯：亞歷克斯。 拉斐爾：拉斐爾。 泰勒：泰勒。 DAVID馬蘭：泰勒。 優秀的。 所以，這些都是我們的志願者 今天和前進 和轉移一點的方式， 而只是繼續前進，保持 牽著你的號碼，你的或你的 第一個跡象，用你的左手， 繼續前進，只是實施 這些箭頭，只是 讓你的左手是名副其實 指著無論你應該點 在，給自己一些空間，以便 我們可以直觀地看到你的手臂居然 指點，你可以只點 那種在地面罰款。 所以在這裡我們有一個鍊錶， 兩個，三個，四個，五個節點最初 並請注意，我們有這個特殊的 指針一開始誰的 關鍵，因為我們必須跟踪 全長列表莫名其妙。 這些傢伙，即使他們離開 以對，背靠背在內存中， 他們實際上可以在任何地方 在計算機的存儲器中。 因此，這些人可能是 在舞台上的任何地方靜置 這很好，只要他們 實際上指著對方， 但為了方便， 乾淨簡潔，我們將 只是吸引他們從左到右像 這一點，但可能有大量的空白 在這些節點之間。 現在，如果我想實際插入一些 新的價值，讓我們繼續前進，做到這一點。 我們有機會現 選擇另一個節點。 說讓我們與mallocing 55開始。 會有人介意的malloc？ 好了，上來吧。 你叫什麼名字？ 彩虹：彩虹。 DAVID馬蘭：彩虹？ 好的。 malloc的彩虹。 上來吧。 所以，現在我們要問自己， 算法，我們可以把55。 所以，我們都知道， 顯然，她很可能 所屬如果我們嘗試 保持這個排序 如果你們能帶一個 退一步所以我們不脫落 舞台上，那將是巨大的。 所以實際上，彩虹， 從這裡開始了我， 因為我們的電腦現在可以 只看到一個變量的時間。 因此，如果這是第一個節點。 請注意，他不是一個節點， 他只是一個指針， 這就是為什麼他的畫是 指針只大小，不 其中的一個完整的矩形。 因此，我們要檢查每個 迭代比9 55少？ 第 比17 55少了呢？ 第 比22少？ 比26少？ 比34少？ 所以現在，很明顯 彩虹所屬的結尾。 所以要明確，什麼 是你的名字，泰勒？ 泰勒：泰勒。 DAVID馬蘭：所以之中泰勒 左手和彩虹的手在這裡， 誰的手需要在什麼指向 為了將55進這個名單？ 什麼是我們需要做什麼？ 是嗎？ 聽眾：泰勒的手 需要指向左邊。 DAVID馬蘭：沒錯。 所以插入一個節點 成列表的末尾 很簡單，因為泰勒剛 必須指向，而不是在地面 或者我們叫它空， null是那種沒有 指針或特 零指針，你 要指向用你的左手 手彩虹，然後彩虹， 其中，如果你的左 一方面可能是點？ 向下。 這並不好，如果她的手是排序 在這裡或排序的任何指點過的 哪種方式。 這將被視為 垃圾值， 但如果她指向 一些已知的價值，我們將 稱之為零或零，這是確定 因為我們在這一個術語 我們知道名單現在就完成了。 那麼，什麼是另一種 比較簡單的情況下？ 難道我們的malloc 5？ 上來吧。 你叫什麼名字？ 蒂芬妮：蒂芙尼。 DAVID馬蘭：對不起？ 蒂芬妮：蒂芙尼。 DAVID馬蘭：蒂芙尼。 好的。 蒂芙尼一直malloced 用值5。 上來吧。 這一次是比較容易過，但 讓我們考慮為了操作了。 這是很容易 與泰勒在末端。 號碼5是當然小於9， 所以，我們有大衛，我們有蒂芙尼， 什麼是你的名字嗎？ 傑克：傑克。 DAVID馬蘭：傑克。 蒂芙尼，傑克和大衛。 誰的手，應該首先更新？ 你想在這裡做？ 有一對夫婦可能的方式，但 另外還有一個或多個錯誤的方法。 聽眾：先從最左邊。 DAVID馬蘭：先從最左邊。 誰是最左邊的位置呢？ 聽眾：第一。 DAVID馬蘭：OK。 因此，開始與第一，你在哪裡 要更新大衛的手中呢？ 聽眾：邁向5。 DAVID馬蘭：OK。 於是，大衛點五 或蒂芙尼在這裡，現在呢？ 聽眾：蒂芙尼指向9？ DAVID馬蘭：完美的，除了賓基的 正中下懷頭掉了下來，對不對？ 因為這有什麼錯 這幅畫從字面上？ 聽眾：沒有指向。 DAVID馬蘭：沒有什麼是 指著傑克了。 我們已經從字面上孤立9 17，我們已經從字面上 洩漏的這一切的記憶，因為 首先更新大衛的手，這是 精細因為它是正確的 現在在蒂凡尼指出， 但如果沒有人有 深謀遠慮地指向傑克， 那麼，我們已經失去了 全部的列表。 因此，讓我們撤消。 所以這是一件好事， 絆倒，但現在，讓我們糾正。 我們應該怎麼做第一呢？ 是嗎？ 聽眾：蒂芙尼應指向在9？ DAVID馬蘭：我不能 得到這個機會給你。 誰應該指向的9？ 聽眾：蒂芙尼。 DAVID馬蘭：好的。 因此蒂芙尼應在9第一點。 因此，蒂芙尼應 在一個相同的值 大衛，這似乎 多餘的了片刻， 但是這很好，因為現在，第二 步驟中，我們可以更新大衛的手 為指向凡尼，然後如果 只是一種清潔我們的東西了 好像這是一種春天般的， 現在這是一個正確的插入。 所以，優秀的。 所以，現在我們快到了。 讓我們插入一個決賽 值就像值20。 如果我們能malloc的最後一個志願？ 上來吧。 所以這一塊是一個有點棘手。 但實際上，該代碼我們 寫作，儘管口頭上， 就像有一群 如果現在的條件下，對不對？ 我們有一個條件 若屬於檢查 在最後，也許是開始。 我們需要某種形式循環到 發現在中間的地方。 因此，讓我們做到這一點與你叫什麼名字？ 艾瑞克：埃里克。 DAVID馬蘭：埃里克？ 埃里克。 認識你很高興。 因此，我們有20個。 超過五少？ 第 超過九少？ 第 比17少？ 第 確定。 他屬於這裡 你的名字又是什麼？ 蘇：蘇。 DAVID馬蘭：蘇。 亞歷克斯：亞歷克斯。 DAVID馬蘭：蘇，亞歷克斯和？ 艾瑞克：埃里克。 DAVID馬蘭：埃里克。 誰的手先獲取更新？ 聽眾：埃里克。 確定。 因此，Eric的應指向哪裡？ 在22。 好。 現在，下一步是什麼？ 然後蘇可指向埃里克 而現在，如果你們只是 使一些空間，這是罰款 在視覺上，現在我們所做的插入。 現在讓我們考慮一個問題，但 非常感謝你對我們的志願者。 非常出色地完成。 您可以保留這些，如果你喜歡。 我們有一個可愛的臨別禮物，如果 你每次想藉此壓力球。 讓我傳遞下來。 那麼，什麼是這個外賣？ 這似乎是驚人的 只要我們現在有 引入了一個替代的 陣列事實並非如此局限 到一些固定尺寸的陣列。 他們可以動態地增長。 但是，就像我們已經看到在週 過去，我們從來沒有得到任何東西是免費的， 喜歡肯定有一個權衡在這裡。 因此，與一個鏈接的上漲空間 列表，是這種活力？ 這種能力成長，坦率地說， 我們可以做刪除 並根據需要，我們有可能縮小。 是我們付出什麼樣的代價？ 兩倍的空間，首先。 如果你看一下圖片，不再 我是存儲整數列表。 我存儲的列表 整數加指針。 所以我加倍的空間量。 現在，也許這不是這樣的 什麼大不了的4個字節，8個字節， 但它當然可以加 彌補大型數據集。 什麼是另一個缺點？ 是嗎？ 聽眾：我們要 遍歷它們一個接酮。 DAVID馬蘭：是的。 我們必須遍歷它們一個接一個。 你知道嗎，我們放棄了這個超級 括號的方便的功能， 符號，更恰當 稱為隨機存取， 在這裡我們可以自己跳 到單個元素 但現在，如果我仍然有 我的志願者在這裡， 如果我想找到 22號，我不能只 跳轉到支架上一些東西。 我要看看在列表中，多 像我們的搜索例子線， 找到數22。 因此，我們似乎已經付出了代價那裡。 但是，我們還是能夠 解決其他問題。 其實，我來介紹一下 只是一對夫婦的視覺效果。 所以，如果你已經下降到 馬瑟飯堂最近， 你還記得自己 棧這樣的托盤， 我們從借來的這些 課前安嫩伯格。 所以這個棧托盤，不過， 代表實際 一個計算機科學的數據結構。 有一個數據結構 在計算機科學 被稱為棧非常漂亮 適合於正是這種視覺。 因此，如果每一個托盤的是不是一個 托盤但像一些，我想 存儲的數字，我 可以放一到這裡， 我可以把另一個倒在這裡， 並不斷堆積號碼 對彼此，什麼是頂部 這個可能有幫助 是什麼含義 這種數據結構？ 哪個號碼，我可以拉出來 第一個最方便？ 最近期看跌的存在。 所以，這就是我們所說的 計算機科學後進先出的數據結構。 後進先出。 我們將不久為什麼看 現在可能是有用的，但對於， 只是考慮物業。 而且它是一種愚蠢的，如果你想 有關如何食堂做的。 他們每次清潔托盤 把最新鮮的人之上， 你可以有一個以前乾淨 但最終很髒亂，塵土飛揚 托盤在最底層 如果你從來沒有真正 得到的，該底部 堆棧，因為你 不斷把新的， 乾淨的人在它的上面。 同樣的事情可能會發生 在一家超市了。 如果你有一個陳列櫃 牛奶每次CVS 或者誰得到更多的牛奶， 你剛才推的牛奶 你已經擁有的背部和 你把新的鋒線， 你將有一些非常討厭 牛奶在數據結構的末尾， 因為它總是在底部或 等效它總是在後面。 但還有另一種方式來思考 排隊的數據和例如，此。 如果你是其中的一個人誰喜歡 排隊的蘋果專賣店外 當一個新的產品來 出來，你可能 不使用堆棧數據 結構，因為你 會疏遠其他人誰是 排隊購買一些新的玩具。 相反，你可能使用 什麼樣的數據結構的 或者是什麼樣的制度 在現實世界？ 希望這是一條線，或更多 正確或更多的英國狀，一個隊列。 而事實證明隊列也是 數據結構，計算機科學， 但一個隊列具有一個非常 不同的屬性。 這不是後進先出法。 後進先出。 上帝保佑。 這是不是FIFO。 先入先出。 這是一件好事 為公平起見 當然，當你排隊 早上起來的超級早。 如果你第一次那裡，你 想要得到第一個為好。 所以，所有的這些數據， 結構，隊列，棧 和其他人一束束，原來你 可以認為這是只是一個數組。 這是一個數組，也許 一個固定大小為4，但它會 是種不錯的，如果我們可以只堆 托盤幾乎可以無限高的，如果我們 有那麼多的托盤或數字。 因此，也許我們要 使用鍊錶這裡， 但權衡將是 可能我們需要更多的內存， 需要多一點的時間，但我們 不限制疊層的高度， 就像奧美的陳列櫃 可能限制堆棧的大小， 等等這些都是設計決策或 可供我們選擇大勢所趨。 因此，這些數據 結構，我們已經開始 看到新的上限可能 什麼以前是超級快 當我們將離開 今天關在哪裡 我們希望能得到 上週三，我們將 開始看數據 結構讓我們搜索 通過日誌結束時間的數據了。 並且我們看到了，記得，在零一周 和一個用二進制搜索或除法 和征服。 這是回來了，更好的是， 聖杯這個星期三 將要拿出 運行真正的數據結構 或者理論上 恆定時間，由此 不要緊多少 千萬甚至上億的東西 我們已經在該數據結構中，它會 需要我們持續的時間，也許一步 兩個步驟或10個步驟， 但步驟常數 通過該數據結構進行搜索。 這的確將是制勝法寶 但更多的是在週三。 見雅則。 [音樂播放]