國寶馬蘭所有權利。 歡迎回到CS50。 這是第8週開始。 記得這個問題集5結束 帶著一點點的挑戰。 因此，假如你恢復你所有的 教學研究員和加利福尼亞州的照片 在card.raw文件，你有資格 現在發現所有的那些人， 一個幸運的獲勝者將步行回家與 這些東西，飛躍運動 你可以使用最後的設備 項目，例如。 ，每一年，這會導致 有點creepiness。 所以我想我會做什麼是購 與您指出 來回走了過 後期工作人員名單。 舉例來說，就在昨天晚上，報價 引文結束，從一名工作人員 成員，“我只是一個學生敲 我的門，跟我拍一張照片。 潛行者，我告訴你。“開始了 相當的描述，然後我們感動 就到了，一個小時左右後，“我有一個 後部分學生在等著我 他有我們的名字和照片 幾張紙。“所有權利。 所以組織，但不 這一切令人毛骨悚然。 那麼，“我是出城的這個週末， 當我回來的時候，有一個在 我的 臥室裡。“[笑] 國寶的馬蘭：下報價從工作人員 成員，“一個學生來我家 薩默維爾今早凌晨4點“。 工作人員，“我得到了我的酒店在聖 舊金山和一名學生被等待 我在大堂有三個數碼單反相機“。 相機類型。 “我什至不對員工這學期， 但學生闖進我家 早晨和記錄了整個事情 與谷歌的玻璃。“最後， “至少12人翹首 等待著我，當我離開了我 豪華轎車，然後我 醒了。“所有權利。 因此，在拍攝的照片中，你可能 回想一下，這傢伙在這裡，你是誰 可能知道米洛香蕉，誰住 勞倫·卡瓦略，我們的頭 教學研究員。 米洛，米洛，來這裡的孩子。 米洛。 米洛。 你要知道，他的穿著谷歌的玻璃，所以 我們會告訴你這一切之後。 因此，這是米洛，如果你想 後來與他拍一張照片。 如果你想看看 在那裡的觀眾。 確定。 這是很好的素材。 嗯，香蕉米洛。 哦，不做到這一點。 [笑] 確定。 所以一個單詞，然後是什麼樣的未來， 因為當我們開始轉型， 具體而言，這個星期在從C 命令行環境PHP和 JavaScript和SQL，HTML和CSS 一個基於網絡的環境中，我們將 你的所有裝備 更多知識 潛在的最終項目。 為此，當然是有 傳統舉行研討會 上切線主題的 當然。 非常相關的編程和 應用開發等等，但 不一定探索 當然自己的教學大綱。 所以，如果你可能有興趣在一個 今年的研討會， 註冊cs50.net/seminar。 有舊研討會 在cs50.net/seminars。 和今年迄今名冊 驚人的Web應用程序使用Ruby on 導軌，這是一種替代 語言PHP。 計算語言學。 到iOS，這是 平台，用於iPhone和 iPad的發展。 JavaScript的Web應用程序的，我們將討論 ，但在本次研討會中，你會去 的更多細節。 蹦蹦運動，所以我們實際上也有 我們的朋友從大躍進運動， 公司本身，加入我們的行列。 明天，其實，為客戶提供 一個動手的研討會，如果 你的興趣。 meteor.js，另一種技術 而不是在瀏覽器中使用JavaScript， 但在服務器上。 Node.js的，這是非常 在該靜脈。 圓滑的Andr​​oid設計。 Android的一個非常受歡迎的替代 的iOS和Windows Phone 和其他移動平台。 和Web安全主動防禦。 因此，事實上，如果你想 搞這個，讓我 注意到這一點。 我們非常高興地說， 我們的朋友在大躍進 運動，這是一個啟動 - 這個裝置實際上只是來到 出幾個月前 - 慷慨捐贈30個此類設備 類盡可能多的學生，如果 你想藉硬件 朝學期結束，並用它來 實際的最終項目。 他們支持的語言數量。 他們沒有，他們沒有PHP的，所以 實現一個或多個這些研討會 可能證明的興趣。 和所有的人將被拍攝下來的 倘若你是不是能夠 親自出席。 通過時間表公佈 電子郵件作為我們鞏固客房。 最後，如果你去 projects.cs.50.net，這是一個網站 我們維持每年我們邀請 人們從社會，教師， 部門，人員，並且都 在CS50至外側的 提出項目設想。 學生群體感興趣的東西。 部門關心的事情。 因此，不要打開，如果你在掙扎 與你的不確定性 自己想解決的。 所以我們推出了一個可以說是最後一次 比我們更複雜的數據結構 在過去的幾週裡看到。 我們一直在使用數組漂亮 高興地作為一個有用的，如果 簡單化的數據結構。 然後，我們介紹了這些， 當然鍊錶。 到底是什麼東西的動機之一 引入這個數據結構？ 是嗎？ 那是什麼？ 觀眾：動態大小。 大衛馬蘭：動態尺寸。 因此，而數組中，你必須 知道它的大小時提前 你分配。 鍊錶，你不這樣做 要知道。 你可以只是malloc的，或更普遍的， 增撥 節點，可以這麼說，任何時候，你 要插入更多的數據。 節點沒有預定的意義。 這只是一個普通術語，描述 我們某種容器 使用我們的數據結構存儲 一些感興趣的項目，在這個 情況是整數。 但是總是有一個權衡。 因此，我們得到的數據的大小動態 結構，但我們付出什麼樣的價格？ 鍊錶的缺點是什麼？ 是嗎？ 觀眾：需要更多的內存。 國寶馬蘭：它需要更多的 內存，究竟怎麼了？ 觀眾：[聽不清]。 DAVID馬蘭：沒錯。 所以，現在我們已經指針 額外的內存，我們以前 並不需要，因為優勢 一個數組，當然是 一切連片， 背靠背， 為您提供了隨機訪問。 因為只需使用方括號 符號，或更技術上的指針 算術，很簡單，此外， 你可以訪問任何 在固定時間內的元素。 而事實上，這是一種暗示 另一個價格，我們正在與支付 鍊錶。 會發生什麼情況的運行時間 像搜索，如果我想 找到一些價值和內部 鍊錶？ 成為我的運行時間是什麼？ 大O的n。 如果它的排序？ 如果數據結構的排序？ 我可以做的更好的比大 n為O的搜索？ 沒有，因為在最壞的情況下，它可能會 很好地進行排序，但數量 你要找的可能是很大的。 它可能是第100號， 可能發生的事情是所有 在結束的方式。 因為你只能訪問一個鏈接 在本實施的喜愛 其第一個節點的方式，你 依然是那樣的運氣了。 你必須遍歷整個事情 從第一次到最後，為了找到 像100那麼大價值。 或確定，如果它是 甚至沒有。 因此，我們不能做什麼算法在數據 結構看起來像這樣嗎？ 我們不能這樣做，因為二進制搜索 二進制搜索需要，我們有 隨機訪問。 我們只能從位置到飛躍 的位置，而無需遵循 這些麵包屑的形式 所有這些指針。 現在，我們怎麼實現呢？ 那麼，如果我們到屏幕上，在這裡，如果 我們可以很快地重新實現此數據 結構 - 我的筆跡不是所有的 在這裡，偉大的，但我們會盡力。 所以typedef結構，什麼我 要調用這個東西在這裡？ 節點。 因此，我將讓我們開始。 而現在，需要將裡面的 該單獨的數據結構 鍊錶？ 多少個字段？ 所以兩個。 一個是很容易的。 所以INT N。 我們可以稱之為ñ我們想要的東西， 但它應該是一個int，如果我們 實現鍊錶為整數。 現在什麼第二 現場有嗎？ 結構節點。 所以，如果我做節點，然後我 可以調用這個也是我想做的事情， 但僅僅是明確的，我會打電話 未來，因為我們一直在做的事情。 然後我會關閉我的花括號。 而現在，作為最後一次， 我把節點。 但是，如果我聲明，這是作為一個 節點，我為什麼懶得如此 詳細在這裡宣布結構 節點下，而不是 只是節點*？ 是嗎？ 觀眾：[聽不清]。 DAVID馬蘭：沒錯。 沒錯。 由於C真的需要你從字面上 只看到的定義節點 一路下來這裡，你可以不 是指它在這裡。 因此，我們有這種先發製人 聲明在這裡，這是無可否認 更詳細。 節點結構，這意味著 我們現在可以訪問它 內部的數據結構。 順便說一句，因為這是 現在成為一個更主觀一點， 明星可以在技術上走在這裡， 它可以去這裡，它可以 甚至在中間。 我們已經通過，在風格指南 當然，把公約 星旁邊的數據 型，在這種情況下， 將結構節點。 但實現大量課本 在線參考，事實上，你可能會 看到它的另一側。 但是，僅僅實現這兩個實際上會 工作，你應該僅僅是 一致的。 好的。 所以這是我們的宣言 結構節點。 但後​​來我們開始做更多 複雜的事情。 例如，我們決定引進 如哈希表的東西。 因此，這裡是一個哈希表大小為n， 索引從0到n的左上方 減去1的左下角。 這可能是一個散列 表中的任何東西。 但我們討論了什麼事情 使用一個哈希表怎麼樣？ 存儲是什麼？ 名稱。 我們可以做名字，如 我們做了最後一次。 真的，你可以存儲任何東西。 我們將再次看到這 PHP和JavaScript中。 哈希表是一個很好的瑞士排序 瑞士軍刀，允許你存儲 幾乎任何你想要的內側 它的關聯值的鍵。 鍵與值。 現在，在這個簡單的情況下，我們的 只是數字鍵。 我們正在實施一個哈希 表中為一個數組。 等鍵是0， 1，2，等等。 因此，我們作為人類，最後決定 本週，你知道嗎，如果我們 去商店名稱，讓我們只是 隨意，但相當合理的， 假設Alice，一個名字， 只是索引為0。 鮑勃，一個B的名字，將被索引 為1，等等。 因此，我們不得不投入之間的映射， 是字符串，和散列 的位置，這是數字的。 因此，該過程通常被稱為 哈希函數，你可以真正 在代碼中實現它。 如果我想實現的哈希函數 這不正是我們 剛剛描述的從去年的時候，我可能會 聲明一個函數，它作為 例如輸入 - ，讓我們做到這一點在此 屏幕在這裡。 如果我想實現一個哈希 的功能，我可能會說， 這樣的事情。 這將返回一個int。 這將被稱為哈希，它是 要接受的參數是一個 字符串，或者我們可以更恰當， 說的char *，我們會打電話給它s。 然後這一切功能， 最終，返回一個int。 現在，它是如何可能 不那麼清晰。 我要實現這個沒有任何 現在形成的錯誤檢查。 我只是一味地說，返回 無論是在s支架0，減， 比方說，資本用分號。 完全打破。 它並不完美，因為 一，什麼如果s是空？ 不好的事情將要發生。 二，如果在此的第一個字母 名字是不是一個大寫字母？ 這不會變成 出。 這可能是一個小寫字母 不是一個字母。 所以完全改進的餘地， 但是這是基本的想法。 我們上週口頭 只是一個過程的映射愛麗絲 0和Bob 1可以表示 當然更公式為C 在這裡發揮作用。 再次調用哈希，將一個字符串作為 輸入，然後莫名其妙地做一些事情 與該輸入信號以產生一個輸出。 不像我們的黑箱描述 長期以來，我們已經完成了。 我不知道如何，這可能是 引擎蓋下工作。 對於問題集6，面臨的挑戰之一 是你來決定什麼 您的哈希函數是什麼？ 這是怎麼回事，裡面那個黑 框，據推測，它會是一個 比這更有趣一點， 肯定更容易出錯 這個特殊的檢查比 實現。 但可能會出現問題，對不對？ 如果我們有一個數據結構，例如 一，什麼是一個問題 你可以運行到隨著時間的推移，當您插入 越來越多的名字進入 哈希表？ 你得到的碰撞，對不對？ 如果你有愛麗絲和亞倫， 兩個人的名字發生 開始與A？ 這引出了一個問題，在那裡你 把第二個這樣的名字？ 那麼，你可能天真地把它 鮑勃屬於的地方，但隨後鮑勃是 擰種，如果您嘗試 插入他的名字旁邊， 有沒有他的空間。 所以，你不妨把鮑勃·查理在哪裡， 你能想像這個非常迅速 下放成有點亂。 線性的東西到底是哪裡你 只需要搜索整個事情 尋找Alice或Bob 或亞倫查理。 因此，而不是我們提出的，而不是只 線性開放空間探測的 橫臥在那裡，我們的名字 提出一個票友的方法。 哈希表仍與實現 的索引數組，但數據不同的 現在，這些指數分別為指針。 指點一下嗎？ 鍊錶的指針。 因為召回鍊錶是 真的只是一個指針，指向一個節點， 節點具有一個下一個域，該節點 有一個下一個域，等等。 所以，你現在覺得這個數組 作為一個哈希表的左手側 導致一個鍊錶。 如果你得到一個優勢是 Alice和亞倫之間的碰撞， 你是做什麼的 第二個這樣的人嗎？ 你只重視他或她的 端，甚至開始 該鍊錶。 而實際上，讓我們只是麵條通過 第二。 哪裡最有意義？ 如果我插入愛麗絲和她結束 第一的位置，然後我嘗試 插入亞倫的名字，而且也 顯然是一個碰撞，我應該把 他開始時 鍊錶？ 這是在那個第一的位置， 或在結束了嗎？ 觀眾：[聽不清]。 DAVID馬蘭：OK。 我聽說開始。 為什麼在開始？ 觀眾：[聽不清]。 DAVID馬蘭：OK。 它是按字母順序排列的，所以這是很好的。 這是一個很好的屬性。 它會來救我的潛在的一段時間。 它不會讓我做二進制搜索，但我 可能至少能夠打出來 一個循環，如果我知道，好了，我的方式 過去亞倫將在此 鍊錶排序。 我沒有浪費我的時間尋找 所有的方式結束。 所以這是合理的。 你為什麼要插入 在碰撞的名字 列表開始？ 那是什麼？ 觀眾：[聽不清]。 國寶馬蘭：這可能需要很長一段時間 得到的列表末尾。 而事實上，長。 越多的名字你插入 開始，不再 鏈要得到的。 的時間越長，掛鉤 列表會得到什麼。 所以，你真的只是 浪費你的時間。 也許你更好的維護 恆定的插入時間，大O 1， 始終把碰撞名 該鍊錶的開頭， 而不是盡可能多擔心 關於排序。 什麼是最好的答案嗎？ 目前還不清楚。 一種取決於什麼 分佈模式是什麼 你的名字插入。 這不一定 一個明顯的答案。 但在這裡，再次 設計的機會。 因此，我們再看著這件事情， 真正的另一大機遇 為對集6。 與實現，如果你還沒有的話， 的Zamyla潛入這兩個哈希 表和嘗試，更詳細。 和視頻演練的是 嵌入在對一套規範。 這是特里 - T-R-I-E。什麼是有趣的 這是運行時間 尋找一個名字，像麥克斯韋 最後一次，是大O是什麼？ 那是什麼？ 觀眾：數字字母。 國寶馬蘭：字母數。 我聽說了兩件事情。 字母和恆定的時間數。 所以，讓我們與第一。 的字母數。 那麼，這樣的數據結構，召回， 像一棵樹，一個家庭樹，每個 的節點組成的數組。 這些數組指針 其他這樣的節點，或其他這樣的 樹中的數組。 因此，如果我們想要再確定 麥克斯韋是否是在這裡，我可能去 第一陣列，在最頂部的 樹中，所謂的根，頂部 特里，然後按照米指針， 然後是一個指針，那麼x， W，E，L，L。 然後當我看到一些特殊的符號， 在這裡表示為三角形。 在代碼中，你會看到我們建議您 為bool實施，只是說是 或沒有，一個字在這裡停止。 那麼，一旦我們去參加M-à-X-W-E-L-L， 感覺就像七，也許 八，如果我們走過去吧，八 步驟找麥克斯韋。 還是讓我們叫它K.但記得最後 的時候，我認為，如果有 切實的最大長度上 字，像40一些奇怪的字符， 最大長度意味著 一個恆定值。 所以真的，是的，這是技術上的大O 8或7，或真大O K.，但 如果有一個有限的上限是什麼 K表，這是一個常數。 所以它的大O 1 在一天結束時。 不是在現實世界中。 當你真正開始看 時鐘程序的運行。 這絕對是有點 比真正的恆定速度較慢 時間與步驟。 這將是七八步， 但仍然好得多 比大O n表示這樣的算法 的大小取決於什麼 的數據結構。 請注意，這裡的上攻，我們可以插入 百萬名到這個 數據結構，但很多步 它是要帶我們去找到 麥克斯韋在這種情況下？ 沒有。 他不受影響。 到今天為止，我不認為我們已經看到了 的一個例子的數據結構或 完全的算法 不受外部 這樣的行為。 但是，這不能是驚人的。 這不能是唯一的解決方案 對於p-集 而事實並非如此。 這不一定是數據 結構應該吸引到， 因為像哈希表，權衡。 你付出的代價是什麼？ 內存。 我的意思是，這是一個窮凶極惡 的內存量。 你不能完全看到它，因為這裡 這幅畫的作者 顯然截斷所有陣列 和我們沒有看到很多A的 B的和C和Q和Y 和Z的這些數組中。 但是，他們在那裡。 每個節點是一個整體的陣列 約26或更多的字節，每個字節 這代表一個字母。 在我們的案例中，這樣我們就可以支持27 單引號的問題集。 因此，這個數據結構是真的， 非常密集和廣泛。 這本身最終可能會放緩 下來的東西，或者至少是成本你 更多的空間。 但同樣，我們可以得出 這裡的比較。 回憶了一段時間後，我們取得了很大成就 更令人興奮的運行時間排序 當我們使用歸併排序，但價格 我們實現N個記錄n為合併支付 排序要求，我們花 什麼資源？ 更多的空間。 我們需要一個輔助陣列 複製人，就像 我們在這裡做的，在舞台上。 如此反复，沒有明顯的贏家， 只是主觀設計 作出的決定。 好的。 因此，這個怎麼樣？ 任何人都承認，D-霍爾？ 確定。 所以，我們三個做。 奧美大廈。 因此，這是奧美的餐飲。 我敢打賭，所有食堂 這樣的托盤堆。 這實際上是代表 的東西，我們已經 顯然已經看到。 我們把它稱為名副其實的堆棧。 棧，您 計算機的內存，數據去 當功能被調用。 例如，什麼樣的東西去 相對於在堆棧上 我們已經討論過的內存佈局 在過去的幾週？ 那是什麼？ 觀眾：函數調用。 DAVID馬蘭：對不起。 觀眾：函數調用。 DAVID馬蘭：通話功能，但 具體而言，每個裡面有什麼 這些幀？ 什麼樣的東西呢？ 嗯。 因此，局部變量。 任何時候，我們需要一些本地存儲， 像一個說法，或INT I，或int 溫度，或任何地方 變量，我們已經 將在堆棧上。 我們稱之為堆棧，因為 該分層想法。 的比賽只是一種現實， 其概念。 但事實證明，一摞還可以 被看作是一個數據結構，一個 替代一個數組，另一種 鍊錶。 概念上的東西更有趣 仍然可以 那些採用 的東西，但它是一個不同類型的 數據結構的支持，真的， 只有兩個操作。 但是，您可以添加票友 功能不止這些。 但這些都是基礎知識 - push和pop。 用棧的想法是，如果我 這裡有，帶或不帶安南伯格 知道，一個托盤從隔壁 數字9就可以了。 所以只是一個int。 我要推到數據 結構，目前是空的。 考慮這個堆棧的底部。 我會推到9號 堆疊，而現在它就在那裡。 但有趣的關於堆棧 是，如果我現在要推 其他一些值，比如17，我推 入堆棧，我要做的事情 直觀的東西，我只是 說得不對，我們人類 會傾向於把它之上。 但是，什麼是有趣 ，我怎麼在9？ 你知道，我不是沒有做一些努力。 那麼，什麼是有趣的 堆棧，設計， 這是一個後進先出的數據結構。 傻的方式描述 後進先出。 所以最後一個數字 在這個時候的時間是17。 所以，如果我想流行的東西 棧，它只能是17。 所以這是一個強制性的順序 這裡的操作，其中的最後一個項目 在成為第一個出。 因此，首字母縮寫詞，後進先出法。 那麼，為什麼會這樣有用嗎？ 是的語境中，你 我想這樣的一個數據結構？ 那麼，它肯定是有用的 內的一台計算機。 所以操作系統顯然使用此 一種數據結構棧。 我們還會看到同樣的想法 當它涉及到網頁。 因此，本週和下週超越， 而當你開始實現Web 稱為HTML頁面的語言，你可以 實際使用的數據結構，如 這是為了確定的頁面 是正確的格式。 因為我們會看到所有的網頁遵循 一種層次，壓痕 在一天結束時，將是 引擎蓋下的樹結構。 所以，更多的只是一點點。 但現在，讓我們提出一個 此刻，我們怎麼可能去 相當於一個堆棧是什麼？ 最後，我提議，我們實施 像這樣的代碼堆棧。 因此，堆棧裡面它都將有 兩件事情，一個數組，稱為托盤 只是要符合演示。 和該陣列中的每個項目 將是一個int類型的。 和能力大概是什麼？ 因為我沒有寫 這裡完整定義。 這可能是最大的 數組的大小。 而且它可能急劇宣布 上面的文件頂部的定義，一些 所隱含類型的常量 單純的資本。 所以某處容量定義 作為可能的最大尺寸。 同時，內部的數據結構 被稱為一個堆棧將有 只是一個整數 只是作為大小。 所以，如果我現在代表這 形象，讓我們假設，這 全黑方塊代表我的籌碼。 在它的內部有兩個變量。 所以我要畫 第一個作為大小。 第二個我要去 以畫為一個數組。 但只是為了讓事情變得有序， 通常我會畫一個像數組 這一點，但它是一種很好的 如果我們匹配的現實，或 相匹配的心智模式。 所以，讓我來代替數組繪製 垂直，這僅僅是再次， 藝術家的演繹。 並不真正的問題是什麼呢 引擎蓋下。 我們會說，在默認情況下， 容量將是三個。 因此，這將是位置0，這 將位置1，本 將位置2。 如果我賄賂應力球， 有人想拿出並運行 登上這裡只是一瞬間嗎？ OK，首先看到你的手。 上來吧。 好的。 所以我相信這是史蒂芬。 上來吧。 好的。 但是，假定現在我們後退到初始 世界的狀態，我 剛剛宣布堆棧，它是 將是三能力。 但規模尚未確定。 托盤尚未確定。 因此，一對夫婦的問題先。 讓我給你話筒，這樣你就可以 更積極參加。 那麼，什麼是大小裡面在這一刻 如果所有我做過的時間 宣布棧 一行代碼？ 史蒂芬：不多。 國寶MALAN：OK，不多。 大家知不知道裡面有什麼大小， 我們不知道裡面有什麼 這個數組在這裡？ 史蒂芬：隨機碼，對不對？ 只是 - 國寶馬蘭：是的，我要 調用它的代碼，但隨機 - 史蒂芬：事情。 國寶馬蘭：就像是隨機的事情 史蒂芬：位。 國寶MALAN：位，對不對？ 因此，垃圾值，對不對？ 因此，0和1的排列。 以前的慣例遺跡 此內存。 我們真的不知道什麼值 ，所以我們通常吸引他們 問號。 所以，首先我們推測 想在這裡做 - 讓我給這個領域裡面 有一個名字 - 托盤。 我們應該怎麼想必初始化 如果我們想大小 開始使用該協議棧？ 史蒂芬：紙盒子3。 國寶馬蘭：那麼，“確定”。 很明顯，容量聲明 其他地方為三個。 而這正是我用過 分配數組。 大小要參閱多少 盤目前在棧上。 史蒂芬：零。 DAVID馬蘭，因此，它應該是零。 因此，繼續前進，並與任何手指， 大小繪製一個零。 好的。 所以，現在，這裡面有什麼 在這裡，我們不知道。 這些真的只是垃圾值。 因此，我們可以得出問號，但 讓我們保持板面乾淨 因為它並不重要 那裡有什麼。 我們不需要初始化數組 什麼，因為如果我們知道， 堆棧的大小是零，好，我們 不應被看什麼 反正在這個數組 這個時間點。 所以，現在想我推 數9入堆棧。 我們應該如何更新數據結構 這個黑盒子裡面？ 什麼樣的價值觀需要改變嗎？ 史蒂芬： - 大小？ DAVID馬蘭：OK。 大小應該變成什麼樣？ 史蒂芬：大小將是一個。 DAVID馬蘭：OK。 因此，大小應成為一體。 所以你可以在一對夫婦的方式做到這一點。 讓我給你，現在你的 手指是一個橡皮擦。 好的。 那麼現在你的手指一刷。 好的。 現在有什麼改變， 很明顯，在數據結構中？ 史蒂芬：我們打算從 底部9。 國寶馬蘭：9。 好，好。 所以還是什麼都無所謂的 一個或兩個位置，因為他們是 垃圾值，但我們不應該打擾 因為大小是尋找 告訴我們，只有第一個元素 實際上是合法的。 所以現在我推17到列表中。 這個畫面會發生什麼事？ 史蒂芬：那麼大小是要去兩個。 DAVID馬蘭：OK。 你橡皮擦 - 哎呀。 你是一個橡皮擦。 史蒂芬：橡皮擦。 DAVID馬蘭：你刷。 史蒂芬：刷機。 DAVID馬蘭：OK。 還有什麼？ 史蒂芬：那麼，我們 - 國寶馬蘭：我們推17。 史蒂芬：我們堅持17之上，所以 - 國寶馬蘭：OK，好。 史蒂芬 - 砸下來。 國寶馬蘭所有權利。 它變得容易。 我不會幫你這個時候。 推22。 史蒂芬：完成。 成為一個橡皮擦。 我成為一刷。 然後我把22。 國寶馬蘭：22。 優秀的。 所以有更多的時間。 我現在要推 入堆棧26。 史蒂芬：哦。 噢，天哪。 你真的讓我猝不及防。 國寶馬蘭：你也沒 看到這一切嗎？ 史蒂芬：我沒有看到這一切。 我們可以重新初始容量？ DAVID馬蘭：這是一個很好的問題。 所以我們自己畫 這裡的一個角落裡。 史蒂芬真的是沒有利好出盡 因為我們這個數組分配 靜態的，可以這麼說，裡面 的數據結構。 我們已經基本上硬編碼 它是大小為3。 因此，我們不能真的重新分配。 我們可以，如果我們回去，我們 重新定義托盤是一個指針， 然後，我們使用malloc手的內存。 因為如果我們得到了內存 通過malloc堆， 然後釋放它。 但在此之前，我們可以釋放它 重新分配一個更大的內存塊， 更新指針，等等。 但現在，這是真的 最好的，我們能做到。 push和pop大概是 有一些錯誤的信號。 因此，舉例來說，我們實施 推可以返回一個布爾值 以前返回真實的，真實的，真實的。 但第四次，這將有 返回false，例如。 好的。 非常出色。 恭喜。 你賺你的壓力，今天的球。 [掌聲] 史蒂芬：謝謝。 DAVID馬蘭：謝謝你。 OK，所以這似乎是沒有太大的 向前邁進了一步，對不對？ 我們描述的數據結構。 這是令人信服的，對不對？ 操作系統喜歡它。 顯然，網絡可以利用這個 和其他應用程序依舊。 但是我們是一個愚蠢的限制 備份排序本週二的限制 我們有固定大小的數組。 所以，確實有一對夫婦 方法我們可以解決這個問題。 我們可以動態分配的數組， 不是由硬編碼我 在這裡完成的，而是重新申報 這一點，只是很清楚， 這樣的事情。 詮釋*托盤，而不是決定 尚未容量。 但是，當我宣布堆棧別處 在我的代碼，然後，我可以調用malloc， 得到一個塊的地址 內存和I可以分配 該地址托盤。 然後，因為它只是一大塊 的記憶，我可以繼續使用方 括號表示法在通常的方式。 這還是因為同樣的原因，有此排序 陣列和功能上等同於 的內存塊來 從malloc。 我們可以把一個像其他 使用指針運算或 方括號。 所以這是一種方法。 但是，是怎麼回事，我們可能會實現這個 相同的數據結構，有可能？ 對嗎？ 我覺得像我們剛剛解決了這個 一個星期前的問題。 這是解決這個問題的 史蒂芬跑進？ 所以，鍊錶，對吧。 問題是，如果我們畫 自己分配到一個角落裡 提前內存太少，我們 然後以某種方式處理，很好， 為什麼不乾脆避免這種情況 共發出？ 為什麼不乾脆宣布托盤是一個 指針指向一個節點，因此一個鍊錶， 然後簡單地分配新的節點 每次史蒂芬需要，以適應 成的數據結構的數目。 所以畫面將不得不改變。 它不會是清潔和 簡單，只是三個整數的數組。 現在，它的將是一個指針，指向 結構，該結構是要 有一個int和一個next指針。 這將導致通過該指針 另一個這樣的結構 另一個這樣的結構。 所以圖片實際上會 得到一個有些混亂。 我們早就箭頭搭售 一切融合在一起。 但是，這是罰款，正確的，因為 我們已經看到了如何做到這一點。 一旦你得到舒適 實施類似一個鏈接 列表，你就必須做，如果你 選擇實現一個哈希表 單獨鏈接的p組6，你可以 使用它作為一個構建塊，或 成分，或在Scratch說話， 程序的東西，你說，你 創建了自己的一塊拼圖 然後，你可以重複使用。 所以權衡，但潛在的解決方案 我們實際上已經看到過。 所以很多時候，你看到每 一年或兩年，當蘋果發布 一些新的東西，所有的瘋狂的人 外面排隊的蘋果 商店買他們的邊際 在硬件升級。 我這樣說，這是確定的，因為 我的那些人之一。 那麼什麼樣的數據結構 可能代表這個現實嗎？ 好吧，我們姑且稱之為一個隊列，一條線。 因此，英國會調用它通常是 反正排隊，所以這是一個好聽的名字。 而且，這兩個操作，一個隊列 應支持，我們會叫排隊 操作和出隊操作， 這兩種相近的 push和pop的精神。 這只是形式的不同 慣例，我們調用這些。 但排隊的東西意味著添加 或插入的數據結構。 出列意味著將其刪除。 但是，而堆棧是一個後進先出的數據 結構，隊列是先入 先出的數據結構。 如果你是行的第一人， 你將是第一人獲得 脫節和購買新設備。 試想一下，這些人會如何心煩 如果蘋果，而不是用一個堆棧， 比如，實行採摘 組成你的新玩具。 所以隊列有意義，當然， 我們能想到的各種 應用程序，想必，隊列， 尤其是當你要公平。 那麼，我們怎麼可能實現這些 作為一個數據結構？ 好吧，我建議，我們可能 需要做的是這種方式。 所以我打算到現在已經有數字。 因此，我們將保持它的簡單，而不是 不一定談托盤。 只是數字，人們得到。 容量是怎麼回事，再次修復 人的總數，可以在 這條線，三個或 任何其他值。 不過，我建議，我需要跟踪 的大小不僅 隊列中，有多少東西都在裡面了。 因此，大小是電流大小，容量 是的最大尺寸。 又一次的，命名 按照慣例。 為什麼我需要一個額外的int裡面 隊列來跟踪誰在 前面的行嗎？ 為什麼我需要做的，在這種情況呢？ 好了，這是怎麼圖片 要改變呢？ 我也許可以重用 這張圖片。 讓我繼續前進，抹去了這裡。 我們會給這個稍微 不同的名字在這裡。 讓我們擺脫了17，讓我們擺脫 9，讓我們擺脫了3。 讓的添加另一件事。 我提議由我需要跟踪 列表的前面，這僅僅是 將是一個int。 我們要保持它的簡單。 現在沒有鍊錶。 我們得承認，我們要 顛簸起來反對這個限制。 但什麼我想看看 發生這個時間呢？ 因此，假設我繼續前進，第一 人來了線， 它是9號。 我們確實有壓力球。 我可以說，偷兩三人？ 一，二，三？ 上來吧。 從正面看，由於 我們會讓這個快。 現在你們每個人將要 線蘋果的風扇男孩。 你會不會接受蘋果的硬件 這雖然結束。 好的。 所以，你是9號，你 17號，22號。 這些都是任意數字，如 學生ID或諸如此類的東西。 在短短的時刻，讓我們開始 開始添加的東西。 我要跑董事會這次在這裡。 因此，在這種情況下，我已經初始化 前面是 - 其實，我真的不關心什麼 前面，因為大小為零。 因此，這可能也只是 是一個問號。 這些都是問號。 所以，現在我們將開始看到一些 排隊的人在店裡。 9號，所以如果你是第一個 凌晨5點，提前去排隊， 或前一天晚上。 確定。 所以，現在9號是在這裡。 因此，圖9是列表的前面。 所以我要繼續前進，並更新 這個電流的大小的數據 結構不能為0了， 但為1。 我打算把9日 列表的前面。 讓我繼續前進，切換屏幕 所以我們可以看到過去我們在這裡。 現在，我想要什麼 放在前面？ 我要跟踪 現在前面的隊列 是在位置0。 因為接下來會發生什麼呢？ 好吧，我想現在排隊 17。 因此第一跳有線。 再次，那種門 店會到這裡來。 所以，現在我已經增加了17。 即使這些傢伙堵 在屏幕上，這是確定的， 因為我們可以看到它在這裡。 抱歉。 觀眾：我們可以移動 - 國寶馬蘭：沒有，這是確定的。 在那裡，這是巨大的。 因此，圖17是內部的隊列。 我需要更新哪些 現在雖然領域呢？ OK，絕對大小。 關於前呢？ OK，沒。 前不應該改變，因為 不同的堆棧，我們 要維護公平。 因此，如果9排在第一，我們希望9 成為第一個出列 進店。 事實上，讓我們看到。 之前，我們插入22，讓我們 繼續前進，出隊9。 你叫什麼名字呢？ 觀眾：傑克。 國寶馬蘭：傑克是怎麼回事 現在被出列。 所以你走進商店。 並假裝商店 在那邊。 所以，現在需要什麼 - 二叔DIT-dit的！ 什麼需要現在發生？ 設計決定。 所以不是一個壞的本能，但 - 你叫什麼名字呢？ 觀眾：大衛。 大衛DAVID馬蘭。 所以，大衛做了什麼？ 他試圖修復數據排序 從他的位置的結構和移動 進入Jake的前位置。 這很好，如果我們願意 接受，作為一個 實施細節。 但首先，讓我們來更新數據 結構之前，我們做到這一點。 因為我不喜歡的想法 人在這條線轉移。 這沒什麼大不了的，如果大衛它 一步到位，但再次，想回 當我們已經有8名志願者在 階段，我們所做的一樣插入 排序，我們不得不開始 感動身邊的每一個人。 這引起了昂貴的，對不對？ 這讓我畏縮關於大O 大O N，n的平方了。 這不是感覺像 一個理想的結果。 因此，讓我們剛剛更新。 因此，該隊列的大小 不再是2。 現在只需1。 但是我現在可以更新的東西 我沒有更新之前， 列表的前面。 我可以這樣說，是位置1？ 所以，現在我們這裡的垃圾值， 垃圾價值在這裡，大衛在 這個垃圾中間。 但是，該數據結構 仍是完好的。 事實上，我不甚至需要 改變Jake的前數 9，因為誰在乎。 我有足夠的信息，現在在 大小，我知道有一個人在 此隊列。 我知道那個人 在位置1，而不是0。 我不計數。 所以1。 因此，數據結構還OK。 那麼，接下來會發生什麼呢？ 讓我們排隊 - 你叫什麼名字？ 觀眾：Callen先生。 國寶馬蘭：Callen先生。 讓我們排隊Callen先生， 圖22是在隊列中。 所以，現在這裡有什麼改變嗎？ 前不會 改變，很明顯。 尺寸要改變再次2。 和22結束在這裡，圖9是仍然存在， 但它實際上是一個 現在垃圾值。 這只是傑克過去的殘餘。 所以，現在發生什麼，如果 我隊列中取出大衛？ 最後一個操作，出隊的大衛。 我們可能會改變，但我提議，讓我們 做盡可能小的工作。 現在我的數據結構去 備份的大小從2到1。 但是，隊列前面的 現在變成2。 我不需要改變這些數字 只是還沒有，因為他們是 只是垃圾值。 但現在發生了什麼？ 假設我自己排隊，26？ 我覺得我屬於這裡。 所以，我正在排隊。 所以我屬於這裡。 而且，即使你做的不是很 欣賞這視覺在舞台上， 因為我們有足夠的空間，我應該 不會站在這裡，為什麼呢？ 觀眾：你出界。 國寶馬蘭：右。 我是出界。 我已經超越索引的 此陣列的界限。 我真的應該於一體的 三個可能的位置。 現在，在最自然的去嗎？ 我建議，我們的槓桿 每週一招。 mod運算符，百分比。 因為我在技術上站在 位置3，但我做的3模能力， SO 3，百分號，3 - 容量3。 那是什麼？ 什麼是餘 3除以3？ 0。 所以，把我傑克是， 這實際上是不錯的。 所以，現在的實施 這個東西要 是有點頭疼。 這真的只是一條線 頭痛，代碼。 但至少現在有垃圾 這裡的價值，但有兩個 這裡正當整數。 我要求，現在我們已經做了 這正是我們需要做的，只要 我們改變了傑克的 的值是26。 我們現在有足夠的信息仍然 保持完整 這樣的數據結構。 我們依然是那樣的運氣，當我們 要插入四個或更多的總 元素，但我至少可以做出漂亮 有效地利用這個常數 時間，其實。 我不必擔心轉移 大家作為大衛的傾向是。 堆棧上的任何問題， 此隊列？ 觀眾：是的原因 你需要的大小，以便你知道 在那裡有一個人？ DAVID馬蘭：沒錯。 我需要知道數組的大小 因為我需要確切地知道如何 許多這些值都是合法的， 所以，我可以找到放在哪裡 旁邊的人。 沒錯。 大小是 - 其實，我們並沒有更新。 我自己在26加入。 大小，而不是1，而是2。 所以，現在這的確有助於我找到 列表頭，這是不為0，不 1，但為2。 列表的前面 確實是22號。 因為他排在第一，所以他應該 被允許進入商店我面前， 儘管在視覺上，我站在 靠近商店。 沒事吧？ 這些傢伙的掌聲鼓勵 我們會讓他們離開那裡。 [掌聲] 國寶馬蘭：我可以讓 你守托盤。 我們可以看到發生什麼，如果 你想要的，但也許不會。 好的。 所以，現在沒有什麼離開我們？ 好吧，讓我建議，有一個 其他一些數據結構，我們可以 開始加入到我們的工具包，將 實際上是非常非常相關，因為 我們潛入網絡的東西。 這再次有某種聯繫 樹的形式 一種叫DOM，文件 對象模型。 但是，我們會看到更多的 用不了多久。 讓我提出的確定性 現在你可能知道什麼叫樹 更多的家庭樹，在那裡你 在有一些祖先 樹根。 重男輕女或女家長 樹的最頂端。 沒有他們的配偶，在這種情況下。 但是，現在我們有什麼，我們會打電話給 孩子，這是掛的節點 關閉左子或右的孩子， 這裡所描述的箭頭。 換句話說，在樹的數據結構 電腦，一棵樹零 或多個節點。 如果它有至少一個節點， 這就是所謂的根。 這是視覺上的東西 我們在上面畫。 該節點，像任何其他節點， 具有零個，一個或兩個，或三個， 然而，許多孩子 數據結構支持。 在這種情況下，根存儲 值，有兩個孩子，2和3， 所以我們一般稱之為左 兒童和3的右孩子。 然後當我們得到下降到5，6， 7，6可能被稱為中間的孩子。 如果你有四個孩子， 它變得撲朔迷離。 因此，我們停止使用那種 口頭上的快捷方式。 但它確實只是一個家族樹。 和這裡的葉子的節點 自己有沒有孩子。 他們掛在樹的底部。 那麼，我們怎麼可能實現的樹 具有最大限度僅有的兩個孩子嗎？ 我們會打電話給它一個二叉樹。 畢再次意思是兩個，在該 的情況下，像二進制。 因此，它可以具有零個，一個 兩個孩子最大限度。 我會建議我們實行節點 該結構與一個整數n， 然後兩個三分球，一個叫 離開後，一個叫權。 但這些都是剛剛好 任意約定。 ，什麼是現在不錯的，特別是如果你 樣的掙扎概念 遞歸，或認為這是不 一個真正的解決方案，任何東西， 特別是如果你能 耗盡內存。 現在，我們正在談論數據 結構和算法，使 我們遍歷和操作， 事實證明，遞歸回來 一個更引人注目 如果沒有美麗的方式。 所以我的建議是實施 搜索功能。 鑑於兩個輸入 - 所以認為這是一個黑盒子。 鑑於兩個輸入，正和一個int 一棵樹的指針，一個指向一個 節點，還是真的一棵樹的根，我 聲稱，該函數可以返回 真的還是假的，值n 是這種樹內。 這個黑盒子裡面有什麼？ 那麼，四分支。 起初只是檢查。 如果樹是空的，只是返回false。 如果沒有節點，有沒有N， 有沒有多少，只是返回false。 如果你正在尋找的價值，N，雖然 ，不到樹箭頭N， 只是要清楚，這是什麼意思時， 我寫的樹，然後箭頭 符號，N？ 沒錯。 這意味著取消引用 指針稱為樹。 去那裡，然後拿到裡面的 節點並獲取其字段名為N。 然後比較實際n表示 通過搜索反對。 因此，如果n是小於n的值 在樹節點本身，好了， 這是什麼意思？ 這乍一看沒什麼意思。 對嗎？ 就像當你有一個數組 值，你可能喜歡的應用二進制 作為一種形式的分搜索 而治之。 但假設沒有什麼我們需要做 二進制搜索在所有的工作 在電話簿和 前面的例子嗎？ 如何進行排序。 因此，讓我們細化的定義樹 這裡不只是一棵樹，它可以 有任意數量的兒童。 不只是一個二叉樹，它可以 最大限度有0，1，或2。 但是，作為一個二叉搜索樹，或BST， 這僅僅是一個奇特的方式說一個 二叉樹每個節點的 左子節點，如果存在，是 小於該節點。 而每一個節點的右子， 如果存在，是更大的 比該節點本身。 所以，換句話說，如果你是畫 樹出來，所有的數字都 這樣精心平衡，這樣，如果 你有55根，33可以去 在它的左邊，因為它是小於55。 77可以去其正確的，因為 它是大於55。 但是現在注意到，相同的定義， 這是一個遞歸定義口頭， 已申請33。 33的左子必須比它少， 和33的右子，44歲，必須 大於它。 所以這是一個二叉搜索樹， 我建議，使用一點點 遞歸，我們現在能夠找到N。 因此，如果n是小於值n的 當前節點，我要去 進取，撐船，所以說話，只是 返回任何回答是的 為n 樹的左子。 再次注意，這個函數只是 預計節點明星， 到一個節點的指針。 所以，我一定可以做樹 左箭頭，這將導致 去到另一個節點。 但是，該節點是什麼？ 那麼，根據這個聲明， 剩下的只是一個指針，所以，僅僅 意味著我通過搜索功能 不同的指針，即 就是代表 我的左子樹。 因此，在這種情況下，指針33，如果 同時，如果是我們的樣本輸入 n是大於上面的n值 當前樹中的節點，那麼我 要繼續前進，平底船在其他 方向，只是說，我不 知道此值n是樹中， 但我知道，如果它是，它是我的 右分支，可以這麼說。 因此，讓我叫遞歸搜索， 再通過一個n，但在傳遞 我的右孩子指針。 換句話說，如果我目前在55 ，我知道我在尋找99 99 大於55，所以就像我撕毀 電話簿星期前，我們 去正確的，同樣是我們 要去這裡。 我不知道，如果它是在我的右 孩子，它不是，77是有，但 我知道這是在那個方向。 因此，我呼籲搜索在我的右孩子， 77，讓搜索身影從 如果99本任意 例如實際上是存在的。 否則，什麼是最終的情況？ 如果樹是空是一個案例。 如果n小於當前節點的 值是另一種情況。 如果n為大於當前 節點的值是第三種情況。 第四和最後的情況是什麼？ 我認為我們的情況下，對不對？ 它必須是n在 當前節點我。 所以，如果我在尋找55在這一點上 在故事中，那支 樹將返回true。 那麼，什麼有趣的是，我們 實際上，不像週過去，我們種 有兩個基例。 ，他們不必 所有在頂部。 頂部是一個基本情況，因為如果 樹是空的，有沒有什麼關係。 只是返回一個硬編碼 值false。 底部分支排序 默認情況下，如果我們檢查 空，我們已經檢查了，如果它應該是 離開了，但是它不應該是，我們已經 檢查，如果它應該是正確的，但它 不應該的，清楚地，它必須是 右邊我們在哪裡。 這是一個基本情況。 因此，有兩個遞歸例 夾在中間。 但我可以寫 這在任何順序。 我只是認為這樣的感覺自然 首先檢查可能的錯誤， 然後檢查左，右檢查，然後 假設你是在節點 你實際上是在尋找。 那麼，為什麼會這樣有用嗎？ 因此，原來 - 讓我跳一個傳情 在這裡，在網上。 我們將開始使用不是一個 在第一編程語言，但 標記語言。 一種標記語言，是一個 類似的精神編程 語言，但它不會給你的 能夠表達自己的邏輯。 它只是給你的能力， 表達自己的結構。 你想放的東西在哪裡 在頁面上，網頁？ 你想讓它是什麼顏色的？ 你想讓它什麼字體大小？ 什麼話你實際上 想在網頁上嗎？ 所以這是一種標記語言。 但然後我們會很迅速推出 JavaScript中，這是一個完全成熟的 編程語言。 在語法上非常相似的外觀 C，但還會有一些 不錯，功能更強大，更 用戶友好的功能。 和挫折 在本學期，我們會點 即將實施的拼寫少得多 使用其他語言的代碼行 比C本身允許的，但對於原因 我們很快就會明白。 這將是第一個這樣的網頁。 這將是完全給人留下深刻印象， 我們的第一個。 簡單地說，你好世界。 但是，如果你從來沒有見過它 之前，這是HTML， 超文本標記語言。 如果你去某些菜單選項 任何瀏覽器，在任何網頁上 在互聯網上，你可以看到的HTML 一些人寫信給 創建該網頁。 它可能看起來並不 短暫或整齊。 但它會按照這些模式 開放式支架和斜線 字母和潛在的數字。 我想我給你傳情 你就可以做什麼 後服用CS50。 讓我去到cs.harvard.edu /搶劫， 我們自己的羅布·鮑登的主頁。 他給我們看。 所以你很快就能夠做到這一點。 此外，你聽到什麼 今天上午 - 你今早 - [倉鼠跳舞音樂] - 你將能作出這種。 等待著我們在週三。 然後我們會看到你。 [倉鼠跳舞音樂] 國寶馬蘭：在未來CS50 -