[Powered by Google Translate] [6週，續]
[戴維·J·馬蘭] [哈佛大學]
這是CS50。[CS50.TV]
這是CS50，這是第6週結束。
所以CS50x，哈佛大學的第一EDX主動參與課程
確實在過去的這個星期一推出。
如果你想別人在互聯網上窺見一斑
現在跟隨著，您可以前往x.cs50.net的。
這將您重定向到適當的位置上edx.org，
這是和其他來自麻省理工學院和伯克利的課程，現在住。
你必須註冊一個帳戶，你會發現，該材料是大致相同的
你這學期，雖然幾個星期延遲，為我們做好一切準備。
但現在學生在CS50x將看到的是一個接口，像這個一樣。
這一點，例如，Zamyla問題集0領先的演練。
在登錄到edx.org，一個CS50x學生看到了各種各樣的事情
你希望看到的一門課程：在週一的演講，
週三，各種短褲，習題的演練，PDF文件的講座。
此外，你在這裡看到，機器翻譯
中文，日語，西班牙語，意大利語，英語成績單，
和一大堆其他的語言，肯定會是不完美的
我們推出了所謂的API以編程方式使用，
或應用程序編程接口，從谷歌
，使我們能夠轉換成其他語言英語。
但由於精彩的一百多名志願者精神，
隨機的人在互聯網上獲悉的參與
在這個項目中，我們將逐步得到改善這些翻譯的質量
的人，我們的計算機已經糾正錯誤。
>> 事實證明了，我們有一些更多的學生顯示週一最高上比我們最初的預期。
事實上，現在CS50x的有100,000人在家裡。
因此，知道你是所有的一部分，這使本課程在計算機科學的就職類的
更為廣泛的教育，更廣泛地訪問。
而現在的現實是，這些大量的網上課程，
他們一開始都是非常高的數字，我們似乎已經在這裡完成。
但這個目標，最終，CS50x是真正的終點線可能獲得盡可能多的人。
在設計上，CS50x將要提供從過去的這個星期一
所有2013年4月15日通過的方式，讓學校的人誰也承擔其他地方，
工作，家庭，其他衝突一樣，有了更多的靈活性
潛入這門課程，其中，可以肯定地說，
相當雄心勃勃地做，如果僅在短短3個月期間，通常學期的課程。
但是，這些學生將被處​​理同樣的問題集，觀看相同的內容，
具有相同的短褲和訪問。
因此，認識到我們都是真的，在此一併。
的CS50x的最終目標之一是不只是為了讓盡可能多的人
終點線，給他們新發現的計算機科學的理解
和編程，但也讓他們有這樣的經驗共享。
50在校園的定義特徵之一，我們希望，
這種共同體驗，是好還是壞，有時，
但具有這些人打開到左邊和右邊，
和辦公時間的黑客馬拉松和公平。
這一點做起來難，在網上與人的人，
但CS50x有史以來第一次CS50世博會，將於4月結束
這將是我們的想法的網游改編的公平
這些成千上萬的學生都將被邀請提交1 - 2分鐘的視頻，
無論是他們最後的項目或視頻截屏揮手打招呼
談論他們的項目和演示，
很像你的前任在這裡做在校園內的公平，
所以，到學期結束，是希望能夠有一個全球性的展覽
的的CS50x學生的最終項目，就像等待著你這個月在這裡的校園生活。
所以，在未來幾個月內。
>> 10萬名學生，不過，隨著而來的，是需要一些更多的CA。
既然你們正在開闢的線索，並採取CS50
數週提前EDX的人對這種物質的釋放，
實現我們很樂意涉及許多我們自己的學生盡可能的這一舉措，
在學期期間以及今年冬天和今年春天。
所以，如果你想參與CS50x的，
特別參加上的EDX CS50x討論，版本的CS50討論的，
你們中許多人已經在校園內使用，網上公告板，
請做頭，URL，讓我們知道你是誰，
因為我們很樂意建立一個團隊的學生和工作人員和教師的一致好評
在校園簡單地打順和幫助。
當他們看到一個問題，這是他們熟悉的，
你聽到學生報告一些錯誤的地方，在一些國家，在互聯網上，
而且鈴響了，因為你也有同樣的問題
希望在D廳前一段時間，那麼你可以附和和分享自己的經驗。
所以，請不要參加，如果你想。
>> 計算機科學課程在哈佛有一個傳統的位，
CS50其中，有一些服裝，有些衣服，你可以自豪地穿
在學期結束，頗為自豪地說，你完成CS50
並把CS50之類的，我們一直在努力讓學生參與
在這個過程中盡可能多，因此我們邀請，
在這段時間的學期，學生提交設計
使用Photoshop或任何工具，選擇你想使用
如果你是一個設計師，提交設計T-卹和運動衫
和太陽傘和小頭巾的狗，我們現在等。
一切是那麼的 - 獎每年展出
過程的網站store.cs50.net。
一切都按成本有銷售，但該網站只運行
並允許人們選擇自己喜歡的顏色和設計。
所以，我想我們只是分享一些去年的設計
在網站上，除了這一個在這裡，它是每年的傳統。
“每一天我在賽格Faultn的”是去年的意見書，
這仍然是校友。
我們在這其中，“CS50，成立於1989年。”
Bowdens，羅布，是去年非常流行。
“鮑登隊”誕生了，這個設計提交，當中最暢銷的。
由於這一個在這裡。很多人有“鮑登發燒”的銷售日誌。
實現，這可能是你的設計，在互聯網上。
在這個問題上的下一個問題的更多細節設置來。
>> 工具：你已經有一些風險，並希望現在
與GDB的一些實踐經驗，
這是，當然，一個調試器，讓您操作
你的程序在一個相當低的水平，做什麼樣的事情呢？
GDB讓你做什麼呢？
是嗎？給我的東西。 [學生回答，不知所云]
好。步入功能，讓你不只是要鍵入run
並有計劃通過其整體的打擊，打印出來的東西輸出到標準輸出。
相反，你可以通過線的步驟，方法是鍵入下一個
走行線或步驟潛入功能，通常是你寫的。
什麼GDB讓你這樣做嗎？是嗎？ [學生回答，不知所云]
打印變量。所以，如果你想你的程序裡面做了一點反省
而不必訴諸printf語句寫入所有的地方，
你可以只打印一個變量或顯示一個變量。
像GDB調試器，你還能做什麼呢？
[學生回答，不知所云]
沒錯。您可以設置斷點，你可以說破的執行
在主要功能或函數foo。
你可以說123線中斷執行。
斷點是一個真正強大的技術
因為如果你有一個一般意義上的你的問題所在
可能的是，你不浪費時間的程序全部通過加強。
基本上，您可以在那裡跳，然後開始打字 -
步進通過它與步驟或下一個或等。
但類似GDB勾的是，它可以幫助你的人，
找到你的問題，並找出你的錯誤。
它並不一定能找到他們這麼大的給你。
>> 因此，我們推出了一天style50，這是一個簡短的命令行工具
嘗試的樣式代碼比你多一點點乾淨的人，可能會做的事。
但是，也真的是只是一個審美的東西。
但事實證明，有這樣的工具，稱為Valgrind的是多了幾分神秘的使用。
乍看之下，它的輸出是十惡不赦神秘的。
但它的奇妙有用的，特別是現在，我們在這個詞的一部分，
在你開始使用malloc和動態內存分配。
事情都可能很快真的，真的錯了。
因為如果你忘記釋放你的記憶，你解引用NULL指針，
或者你解引用一些垃圾的指針，什麼是典型的症狀，結果呢？
賽格故障。這個核心，你會得到一定數目的字節或兆字節的文件
表示該程序的內存狀態時墜毀，
但你的程序，最終段故障，分割故障，
這意味著什麼糟糕的事情發生幾乎總是與
記憶體相關的錯誤，你的某個地方制定。
因此，Valgrind的幫助你找到這樣的事情。
這是一個工具，你運行，如GDB，你編譯你的程序後，
但不是直接運行你的程序，你運行Valgrind的
傳遞給你的程序，只是像你這樣的GDB。
現在，使用，以獲得最佳的輸出類型，
是有點長，所以在屏幕的頂部在那裡你會看到Valgrind的-V。
“-V”幾乎普遍意味著冗長的，當你在Linux計算機上使用程序。
因此，這意味著你可能會比默認情況下，吐出更多的數據。
“ - 洩漏檢查十足。”這只是說檢查所有可能的內存洩漏，
錯誤，我可能會。這一點，也與Linux程序，是一種常見的範例。
一般來說，如果你有一個命令行參數，這是一個“開關”，
這應該改變程序的行為，它是一個單一的字母，
它的-V，但如果這就是切換，只需通過設計的程序員，
是一個完整的字或者一組字，啟動命令行參數 - 。
這些都只是人的慣例，但你會看到他們越來越多地。
然後，最後，“a.out格式”是在這個特定的例子中的程序的任意名稱。
這裡的一些有代表性的輸出。
>> 在我們看這可能意味著什麼，讓我過去在這裡的代碼片段。
讓我感動了這一點的方式，即將推出，
讓我們來看看在memory.c，這是這短短的例子。
因此，在這個程序中，讓我放大的功能和問題。
我們有一個main函數中調用一個函數，F，
然後什麼f進行，稍有技術的英語嗎？
什麼f繼續做嗎？
怎麼樣，我會與第20行開始，恆星的位置並不重要，
，但我會是一致的最後一次演講。
什麼是第20行為我們做什麼？在左手側。我們將打破它進一步下降。
詮釋：什麼是幹什麼的？
好吧。它聲明一個指針，現在讓我們更技術。
是什麼意思，很具體，聲明一個指針呢？別人嗎？
是嗎？ [學生回答，難以理解太遠。
所以，你正在閱讀的右手邊等號。
讓我們把注意力集中在左側，剛剛於int * X。
“聲明”的指針，但現在我們來看看在更深的這一定義。
這是什麼具體的，技術上是什麼意思？是嗎？
[學生回答，不知所云]
好吧。準備保存內存中的地址。
好。讓我們進一步採取這一步，它聲明了一個變量x，這是32位。
我知道這是32位，因為 - ？
這不是因為它是一個int，因為它是一個指針，在這種情況下。
巧合的是，它是一個和同一個int，
但事實上，有明星，有指這是一個指針
在家電，與許多計算機中，但不是所有的，指針是32位。
在更現代化的硬件，如最新的Mac電腦，最新的電腦，你可能有64位指針，
但在家電，這些東西都是32位的。
因此，我們將標準化這一點。更具體的是，故事的結局如下：
我們的“聲明”指針，這是什麼意思呢？
我們準備存放的內存地址。
這是什麼意思呢？
我們創建了一個變量x 32位
不久將存儲的地址的整數。
這是大概準確的，我們可以得到的。
這是向前邁進簡化了世界，只說聲明一個指向名為x。
聲明一個指針，但認識和理解到底發生了
甚至在短短的幾個字符。
>> 現在，這幾乎是一點點變得更容易，即使它是一個較長的表達式。
那麼，是什麼做的，現在的突出“的malloc（10 *表示sizeof（int））;”是嗎？
[學生回答，不知所云]
好。我要了。它分配的內存塊的十個整數。
現在讓我們略深潛水，它是一大塊的十個整數的內存分配。
什麼是malloc的返回呢？
這個塊的地址，或更具體而言，該塊的第一個字節的地址。
我又如何，程序員，知道在哪裡，內存塊的結束？
我知道，這是連續的。定義的malloc，給你一個連續的內存塊。
無間隙。您可以訪問該塊中的每個字節，
背靠背回來了，但我怎麼知道是這個內存塊的結束嗎？
當你使用malloc嗎？ [學生回答，不知所云]好。
你不知道。你要記住。
我一定要記住，我用的值是10，我什至不似乎都做了，在這裡。
但責任完全在我身上。 STRLEN，我們已經變得稍微依賴於字符串，
不僅是因為本公約的\ 0
這種特殊的空字符，NUL，在字符串的結尾。
這並不持有的只是任意的內存塊。
這是給你的。因此，第20行，然後，分配的內存塊
可以存儲10的整數，並且其存儲的第一個字節的地址
該塊內存中的變量x。
埃爾戈，這是一個指針。所以，不幸的是，第21行是一個錯誤。
但首先，它是什麼做的？說店在位置10，0索引，
名為x的值為0的內存塊。
>> 因此，注意兩件事情是怎麼回事。
即使x是一個指針，記得幾個星期前
你仍然可以使用陣列式方括號。
因為這實際上是簡單的記法更神秘的前瞻性指針的算術運算。
在這裡我們會做這樣的事情：地址x，移動10個點，
然後去那裡的地址存儲在該位置。
但坦率地說，這僅僅是殘酷的，並得到舒適的。
因此，世界上通常使用方括號只是因為它是更人性化的閱讀。
但是，這到底發生了什麼引擎蓋下的;
x是一個地址，而不是一個數組，每本身。
因此，這是存儲0 10英寸x位置。
這是為什麼不好？是嗎？
[學生回答，不知所云]沒錯。
我們只分配了10整數，但我們從0數C語言編程時，
所以你必須為0 1 2 3 4 5 6 7 8 9，但不為10的訪問。
因此，無論是程序要賽格故障或事實並非如此。
但是，我們真的不知道，這是一個不確定的行為。
這真的取決於我們是否得到幸運。
如果原來的操作系統，如果我不介意使用額外的字節，
即使它不給我，我的程序可能不會崩潰。
它的原料，它的馬車，但你可能看不到症狀，
您可能會看到它在一段時間內只有一次。
但現實的情況是，錯誤，其實是有。
它的確是有問題的，如果你寫了一個程序，你想要是正確的，
你賣的程序的人都在用，每一次在一段時間內崩潰
因為，當然，這是不好的。事實上，如果你有一個Android手機或iPhone
你下載的應用程序，這些天，如果你曾經有過一個應用程序退出，
突然消失，幾乎總是一些與內存相關的問題的結果，
程序員搞砸了，並取消引用指針
他或她不應該有，和iOS或Android的結果是完全中止程序
而不是風險不確定的行為或某種安全漏洞。
>> 這個計劃除了這一個，還有另外一個錯誤。
還有什麼我搞砸了這個項目？
我還沒有練什麼我傳福音。是嗎？
[學生回答，不知所云]好。
我還沒有釋放的內存。因此，經驗法則
必須隨時調用malloc，你必須調用完成後，使用該內存。
現在，當我將要釋放內存呢？
也許，我會假設這第一行是正確的，要做到這一點。
例如，因為我不能做到這一點在這裡。為什麼呢？
剛出來的範圍。因此，即使我們談論的指針，
這是一個星期2或3個問題，其中x是僅在範圍內的大括號，它被宣布。
所以，你絕對不能釋放它。我唯一​​的機會，以釋放後，大約是21行。
這是一個相當簡單的程序，它是相當容易，一旦你種你的心包裹
周圍有什麼程序在做，其中的錯誤。
而且，即使你沒有看到它在第一，希望它現在有點明顯
這些錯誤很容易地解決，很容易實現。
但是，當一個程序長超過12行，50行，100行，
步行通過您的代碼行，想通過它在邏輯上，
是可能的，但不是特別有趣的事情，不斷地尋找錯誤，
，它也是很難做到的，這就是為什麼這樣的工具Valgrind的存在。
讓我繼續這樣做：讓我打開我的終端窗口，
讓我不只是運行內存，因為內存似乎是罰款。
我得到幸運。去，額外的字節陣列的結尾
似乎不成為問題太多。
但是，讓我儘管如此，做一個理智的檢查，這只是意味著要檢查
這是否實際上是正確的。
>> 因此，讓我們做的valgrind-V - 洩漏檢查=完全​​，
然後在這種情況下的程序的名稱是存儲器，而不是a.out的。
所以，讓我繼續這樣做。按下回車鍵。
親愛的上帝。這是它的輸出，這就是我前面提到的。
但是，如果你學習閱讀的廢話，
這是診斷輸出，是不是很有趣。
你的眼睛真正要尋找的是沒有提到的錯誤或無效的。
建議問題的詞。
事實上，讓我們看看會發生什麼錯在這裡。
我有某種形式的一個總結，“在使用中在出口處：1塊40個字節。”
我真的不知道塊還沒有，但40字節
其實感覺我可以找出其中，來自。
40個字節。為什麼是40個字節在出口中使用嗎？
更具體地，如果我們向下滾動這裡，
為什麼我肯定失去了40個字節？是嗎？
[學生回答，不知所云]完美。是的，沒錯。
有10的整數，和每個人是4位或32位的大小，
所以我已經失去了精確的40個字節，因為，你的建議，我並沒有所謂的自由。
這是一個錯誤，現在就讓我們來看看遠一點，看到旁邊，
“無效的寫大小為4。”現在這是什麼？
這裡地址是什麼基準符號，顯然是嗎？
這是十六進制的，任何時候你看到一個數字，以0x開頭，
這意味著我們回來的路上，我想，問題的pset 0的部分，十六進制，
這是剛剛做的熱身運動，十進制轉換為十六進制，二進制等等。
十六進制，只是人的慣例，通常用來表示指針
或者，更普遍的是，地址。這只是一個慣例，
因為這是一個有點更容易閱讀，這是一個小更緊湊，比什麼是小數，
二進制文件是無用的為大多數人類使用。
所以，現在這是什麼意思呢？嗯，它看起來像有一個無效的寫
大小為4的第21行上的memory.c。
所以，讓我們回到第21行，而事實上，這裡是無效的寫。
因此，Valgrind是不會完全握住我的手，告訴我的解決辦法是什麼，
但它是檢測，我做了一個無效的寫。
我接觸的4個字節，我不應該，顯然這是因為，
正如你指出的，我做的[10]而不是[9]最大限度地
或[0]或介於兩者之間。
使用Valgrind，實現任何時間，你現在寫一個程序
使用指針和使用內存，和malloc更具體地說，
肯定的習慣運行此長
但很容易複製和粘貼命令的Valgrind的
看在那裡，如果有一些錯誤。
這將是壓倒性的，每次你看到的輸出，
只是解析視覺上所有的輸出，看看你看到提到的錯誤
或警告無效或丟失。
任何的話聽起來像你搞砸了某個地方。
所以，意識到這是一個新的工具，在您的工具箱。
>> 現在，在週一，我們有一大堆的人來這裡
並代表一個鏈接的列表的概念。
我們介紹了鍊錶作為一個解決什麼問題？
是嗎？ [學生回答，不知所云]好。
數組不能有內存添加到他們。
如果你分配一個大小為10的數組，這就是你所得到的。
你可以調用一個函數，如果你像realloc的最初叫的malloc，
，並且可以試種陣列朝向它的結束，如果有足夠的空間
沒有其他人使用，而且，如果有，它會找到你一個更大的塊其他地方。
然後將所有的這些字節複製到新的數組。
這聽起來像一個非常正確的解決方案。
這是為什麼缺乏吸引力？
我的意思是，人類已經解決了這個問題。
為什麼我們需要週一鍊錶來解決它？是嗎？
[學生回答，不知所云]這可能需要很長的時間。
事實上，在任何時候，當你調用malloc或realloc或calloc，這又是另外一個，
任何時候，你的程序，所談的操作系統，
你會減慢程序速度下降。
如果你正在做這類的東西在循環中，你真的放緩下來的東西。
你不會注意到這一點的最簡單的“Hello World”類型的程序，
但在更大的計劃，要求操作系統一而再，再而內存
或給它一次又一次的往往不是一件好事。
另外，它只是形式的智力 - 這是一個完全是浪費時間。
為什麼越來越多的內存分配，風險將所有內容複製到新的數組，
如果你有一個選擇，讓你真正需要的，你只有盡可能多的內存分配？
所以在這裡的長處和短處。
現在的長處之一是，我們有活力。
無所謂的內存塊，是免費的，
我只是有點創建這些麵包屑通過指針
我的整個鍊錶串在一起。
但我支付至少一價。
>> 我不得不放棄在獲得鍊錶是什麼？
是嗎？ [學生回答，不知所云]好。
你需要更多的內存。現在我需要為這些指針的空間，
的情況下，這個超級簡單的鍊錶
只要存儲4個字節的整數，這是我們一直在說
，指針為4個字節，所以現在我已經一倍
我只需要存儲此列表的內存量。
但是，這是一個不斷權衡計算機科學
在時間和空間和發展，精力和其他資源。
使用鍊錶的另一個缺點什麼？是嗎？
[學生回答，不知所云]
好。不容易獲得。我們不能再利用
0週的原則，如分而治之。
更具體地，二進制搜索。因為即使我們人類
大致可以看到這個列表的中間，
計算機只知道這個鍊錶開始的地址，稱為第一。
這是為0x123或類似的東西。
而唯一的方式，程序可以找到中間的元素
實際上是搜索整個列表。
即使如此，它的字面搜索整個列表，因為
甚至當你達到的中間元素的指針，
你的計劃，這份名單是不知道多久，潛在的，
直到你擊中結束的時候，你怎麼知道編程的
你在一個鍊錶的結束？
有一個特殊的NULL指針，如此反复，一個慣例。
而不是使用這個指針，我們絕對不希望它是一些垃圾的價值
指向階段的地方，我們希望它是手，NULL，
因此，我們有這個總站在這種數據結構，所以我們知道它在哪裡結束。
>> 如果我們要操作的呢？
我們做了最重要的，這在視覺，與人類，
但如果我們想要做的插入，該怎麼辦呢？
因此，原來的名單是9，17，20，22，29，34。
如果我們想的malloc空間為55號，它的節點，
然後我們要插入55到列表中，就像我們上週一？
如何才能做到這一點呢？那麼，梅艷芳走過來，她基本上走的列表。
她的第一個元素，然後開始下，下，下，下，下一個。
終於擊中了左側的一路下滑
並實現了哦，這是NULL。那麼，什麼指針操作需要做的嗎？
誰的人就結束了，34號，需要提高他的左手
在55點，55需要他們的指點下成為新的NULL終止的左手臂。完成。
很容易插入55到排序的列表。
如何看？
>> 讓我去進取，不斷開拓這裡的一些代碼示例。
我會打開gedit的，讓我第一次打開兩個文件。
一個是list1.h，我只想提醒的是，這是代碼塊
我們用來代表一個節點。
節點具有一個int n和一個指針，只是點稱為下一個在列表中的下一件事。
這是現在的。h文件。為什麼呢？
有這樣的約定，和我們沒有優勢，這是一個巨大的量自己，
但人誰寫printf和其他功能
給作為禮物送給世界所有這些功能編寫一個名為stdio.h中。
然後string.h中，然後有map.h，並有所有這些h文件
期內別人寫的，你可能已經看到或使用。
一般來說，在那些h文件是唯一的東西，如類型定義。
或自定義類型或聲明的常量的聲明。
你不把在頭文件中的函數的實現。
你說，而不是，只是他們的原型。
你把你想分享的東西與他們所需要的世界
為了編譯自己的代碼。因此，只要進入這個習慣，
我們決定做同樣的事情。沒有太多的list1.h
但我們已經把人在世界上可能有興趣的東西，
要使用我們的鏈接列表實現。
現在，在list1.c，我不會去通過這整個事情
因為這是一個有點長，這個程序，但讓我們迅速在提示符下運行。
讓我編list1的，讓我運行list1的，你會看到什麼
我們模擬了一個簡單的小程序，在這裡
這是怎麼回事，讓我來添加和刪除號碼的列表。
所以，讓我去進取型和3型的菜單選項3。
我想插入數字 - 讓我們做的第一個數字，這是9，
現在我告訴我說，的列表現在9。
讓我繼續前進，做的是另一套插入，所以我打選項3。
我要插入什麼號碼？ 17。
輸入。我會做更多的只是一個。
讓我插入22號。
因此，我們已經有了一個初步的鏈接列表，我們剛才在幻燈片的形式。
這是怎麼插入實際發生的事情嗎？
事實上，圖22是現在在列表的末尾。
這樣的故事告訴我們在舞台上週一，剛才扼
必須實際發生的代碼。
讓我們一起來看看。讓我在這個文件中，向下滾動。
我們會掩飾一些的功能，
但我們會去，說，插入功能。
>> 讓我們看一下如何去到這個鍊錶中插入一個新的節點。
名單在哪裡申報？好吧，讓我們滾動的方式在最頂端，
注意到，我基本上宣布鍊錶作為一個單一的指針，這是最初NULL。
所以我用一個全局變量，在一般情況下我們所鼓吹反對
因為它使你的代碼有點亂來維持，
這是一種懶惰的，通常，但它不是懶​​惰，這是沒有錯的，它不壞
如果你的程序的唯一目的是模擬一個鏈接列表。
而這正是我們正在做的。
因此，而不是宣布在主，然後將它傳遞給每一個功能
我們已經寫了這個程序，而不是實現哦，讓我們使全球
因為這項計劃的整個目的是展示一個且只有一個鍊錶。
所以，感覺還可以。下面是我的原型，我們不會通過所有這些，
但我寫的刪除功能，查找功能，插入功能，和移動功能。
但現在，讓我們往回走的插入功能
如何在這裡工作。
插入上線 - 在這裡，我們走了。
插入。因此，它不帶任何參數，因為我們要問
他們要插入的數目這個功能的用戶內部。
但首先，我們準備給他們一些空間。
這是複製並粘貼到其他的例子。
在這種情況下，我們被分配一個int，這一次我們分配一個節點。
我真的不記得有多少個字節的節點，但是這很好。
SIZEOF能明白這一點對我來說。
我為什麼要檢查是否為NULL在第120行嗎？
什麼可能會出錯，在第119行嗎？是嗎？
[學生回答，不知所云]
好。只要可能的情況下，我問了太多的內存
什麼錯誤的，操作系統沒有足夠的字節給我，
所以它的信號盡可能多的返回NULL，如果我不檢查
我只是一味地繼續使用返回的地址，也可能是NULL。
這可能是一些未知的值不是一件好事，除非I -
其實不會是一個未知的值。這可能是NULL，所以我不希望
濫用它，，風險提領。
如果出現這種情況，我只是返回，我們會假裝就像我沒有得到任何內存在所有。
>> 否則，我告訴用戶給我一些插入，我呼籲我們的老朋友調用getInt，
然後，這是新的語法，我們（星期一）推出。
“newptr-> N”是指你的地址是由malloc
這代表一個新的節點對象的第一個字節，
然後去到外地，稱為n。
一點點小問題：這是相當於什麼更神秘的代碼行嗎？
我還能這樣寫呢？要採取刺？
[學生回答，不知所云]
好。使用N，但它不是一件簡單的事情，因為這。
我首先需要做什麼？ [學生回答，不知所云]
好。我需要做newptr.n。
因此，這是說，顯然是一個新的指針地址。為什麼呢？
因為它是malloc返回的。 * newptr說：“去那裡”，
然後，一旦你有，那麼你可以使用比較熟悉，N，
但這只是看起來有點難看，特別是如果我們人類要
畫箭頭的指針，所有的時間，世界上有該箭頭符號標準化，
這不完全一樣的事情。
所以，你只能使用 - >符號的東西，左邊是一個指針。
否則，如果它是一個真正的結構，使用，N。
那麼這：為什麼我初始化newptr的 - >下一個到NULL？
我們不希望一個懸空的左手的結束階段。
我們要垂直向下，這意味著列表末尾
可能是在這個節點，所以我們最好確保它是NULL。
而且，在一般情況下，初始化的變量或數據成員和結構
的東西是很好的做法。
只要讓垃圾的存在和繼續存在一般，讓你有麻煩
如果你忘了以後做一些事情。
>> 這裡有一個少數情況下。這又是插入功能，
我檢查的第一件事是，如果該變量被稱為第一，
這個全局變量是NULL，這意味著有沒有鍊錶。
我們沒有插入任何數字，所以它是微不足道的插入此數
到列表中，因為它只是屬於在開始該列表。
因此，這是當Anita只是站著一個人在這兒，假裝
舞台上沒有其他人在這裡，直到我們分配了一個節點，
然後她可以提高她的手，第一次，
如果每個人都來了之後，她在舞台上週一。
現在在這裡，我不得不說這是一個小的檢查，如果新節點的n值
<n的值，在當前的第一個節點，
這意味著有一個鍊錶的開始。
在列表中至少有一個節點，但這個新來的傢伙
屬於在它之前，所以我們需要左右移動的東西。
換句話說，如果該列表已經開始，只是讓我們說，
僅僅是17號，這就是 - 實際上，我們可以做到這一點更清楚。
如果我們開始我們的故事指針在這裡被稱為第一，
它最初是NULL，我們插入了9號，
數字9明顯屬於在開始該列表。
因此，讓我們假裝我們只是malloced的地址或9號，並把它放在這裡。
默認情況下，如果第一個是9，第一種情況下，我們討論的只是意味著我們的角度這傢伙在這裡，
離開這個NULL;現在我們的9號。
我們要插入的下一個數字是17。
17屬於這裡，所以我們將不得不做一些邏輯步通過。
因此，讓我們相反，在我們這樣做，讓我們假設，我們想插入數字8。
>> 所以，只是為方便起見，我在這裡要繪製。
但請記住，malloc的可以把它的大多數地方。
但是，對於圖形的緣故，我準備把它放在這裡。
因此，我假裝剛剛分配的節點8號，默認情況下，這是NULL。
現在有什麼發生？一對夫婦的事情。
（星期一）在舞台上犯這樣的錯誤，我們更新了指針這樣的，
這樣做，然後我們要求 - 我們孤立在舞台上的其他人。
因為你不能做到 - 在這裡操作的順序是很重要的，
因為現在我們已經失去了，只是漂浮在太空中的這個節點9。
因此，這是不正確的方法（星期一）。
我們首先必須做其它的事情。
世界的狀態看起來是這樣的。最初，8個已分配。
什麼的插入8將是一個更好的辦法嗎？
而不是先更新這個指針，只需更新，而不是這一個在這裡。
因此，我們需要把這個NULL字符的代碼行的
成實際的指針，該指針指向節點9，
然後我們就可以安全地改變首先指出這傢伙在這裡。
現在，我們有一個列表，鍊錶，兩個元素。
這是什麼實際上看起來像這裡嗎？
如果我們的代碼，請注意，我已經做了。
我已經說過了newptr，在這個故事中，newptr指著這傢伙。
>> 因此，讓我畫一件事，我應該留下多一點空間。
所以請原諒小的小客廳。
這傢伙叫newptr。
這是變量，我們宣布的幾行，行 - 剛剛25歲以上。
和它的指向到8。所以當我說newptr - >下，這意味著到結構
被指出在的newptr，所以我們在這裡，去那裡。
箭頭說獲得下一個字段，那麼“=”是說把什麼樣的價值？
這是在什麼樣的價值是在第一的價值？
首先是指向這個節點上，這樣就意味著現在應該在這個節點。
換句話說，看起來雖然是一個荒謬的亂用我的筆跡，
什麼是一個簡單的想法，只是將這些箭頭圍
轉化為代碼，僅這一項襯墊。
存儲在第一位的下一個字段，然後更新第一個實際上是什麼樣的。
讓我們繼續前進，快進一些這方面的，
並期待只在這條尾巴插入。
假如我得到的地步，我發現，一些節點的下一個字段是NULL。
而故事中的一個細節，在這一點上，我掩飾
是，我已經介紹了另一種指針在142行，前身指針。
從本質上講，在這一點上的故事，列表後，獲得長期，
我種需要用兩個手指走，因為如果我走的太遠，
記得在一個單一的長列表，你可以不走回頭路。
因此，這個想法predptr是我的左的手指，newptr的 - 而不是newptr。
另一個指針，這裡是我的手指，我只是種走的列表。
這就是為什麼存在。但是，讓我們只考慮一個簡單的情況下在這裡。
如果該指針的下一個字段是空的，什麼是合乎邏輯的含義嗎？
如果你遍歷這個列表，你打一個NULL指針嗎？
你在列表末尾，這樣的代碼，然後追加一個額外的元素
是一種直觀的將採取該節點的指針為NULL，
因此，這是目前NULL，並改變它，但是，要在新的節點的地址。
所以我們僅僅是畫在代碼中的箭頭，，我們提請在舞台上提高一個人的左手。
>> 而且，我會揮揮手，在目前的情況下，
只是因為我認為這是很容易迷失在這樣的環境中，當我們這樣做，
在列表的中間插入檢查。
但是，僅僅憑直覺，需要做些什麼，如果你想弄清楚
其中一些號碼是屬於中間的是你必須走
使用一個以上的手指，多個指針，
揣摩出它所屬的檢查是元素<當前，
>目前，一旦你找到那個地方，
然後，你做這樣的騙局，你周圍移動指針非常仔細。
的答案，如果你想在自己的家裡，原因通過
歸結只是這兩行代碼，但這些生產線的順序是超級重要的。
因為，如果你把別人的手和提高別人的錯誤的順序，
再次，你可能最終成為孤兒的名單。
總結的尾部插入多個概念，是相對簡單的。
在頭插入也比較簡單，
但這個時候，你需要更新一個額外的指針
擠5號到列表中，
然後在中間插入涉及更加努力，
在正確的位置，非常小心地將20號，
這是在17和22之間。
所以，你需要做這樣的事情有新的節點20點到22點，
然後，哪一個節點的指針，因此需要更新最後？
17，要真正將其插入。
所以，再一次，我要推遲，特別是實施的實際代碼。
>> 乍一看，這是一個有點勢不可擋，但它實際上只是一個無限循環
的循環，循環，循環，循環，而打破，只要你打的NULL指針，
在這一點，你可以做必要的插入。
那麼，這是代表鍊錶插入代碼。
這是種了很多，而且感覺就像我們已經解決了一個問題，
但我們已經推出了另一個。坦率地說，我們已經花了所有時間
大O的Ω和運行時間，試圖解決問題更迅速，
在這裡，我們採取的大倒退，感覺。
然而，如果目標是存儲數據，
那感覺就像聖杯，為我們週一表示，是否真的會
即時存儲的東西。
>> 事實上，假設我們確實放下了一會兒鍊錶
我們，而不是推出一個表的概念。
我們只是覺得一個表作為數組的時刻。
這個數組，這種情況下，這裡有26個元素，從0到25，
假設你需要的存儲塊的名稱：
Alice和Bob和Charlie之類的。
你需要一些數據結構來存儲這些名字。
好了，你可以使用的東西像一個鍊錶
，你可以走之前，Bob和Charlie後，鮑勃列表中插入愛麗絲等等。
而且，事實上，如果你想看到這樣的代碼，順便說一句，
我知道，在list2.h，我們做的正是。
我們不會去通過這個代碼，但是這是第一個例子中的一個變種
引入了一個其他的struct我們以前見過的所謂的學生，
再有什麼實際存儲在鍊錶中是一個指針，指向一個學生結構
而不是一個簡單的小整數n。
所以實現的代碼，涉及到實際的字符串，
但如果目標在手，現在確實是要解決效率問題，
不會是很好，如果我們給一個叫愛麗絲的對象，
我們希望把她一個數據結構的正確位置，
感覺它會是非常好的，只是把愛麗絲，
名稱開頭為A，在第一個位置。
和Bob，他的名字開始的B，在第二個位置。
有了一個數組，或讓我們從一張桌子，一個哈希表，
我們可以這樣做。如果我們有一個“愛麗絲夢遊仙境”的名稱，如，
一個字符串，如愛麗絲，你在哪裡放的-l-I-C-E？
我們需要一個hueristic。我們需要一個函數來採取一些“愛麗絲夢遊仙境”的輸入，比如
並返回一個答案，“把愛麗絲在這個位置。”
而這個函數，這個黑盒子，將被稱為散列函數。
>> 散列函數是一些需要輸入，如“愛麗絲”，
，然後返回給你，通常情況下，其中，在一些數據結構中的數字的位置艾麗斯屬於。
在這種情況下，我們的散列函數應該是相對簡單的。
我們的散列函數應該說，如果你是“愛麗絲”，我應該關心哪些字符？
第一個。因此，我期待在[0]，然後我說，如果[0]字符是A，返回0。
如果是B，則返回1。如果它的C，返回2，等等。
共0指數，這將讓我插入Alice和Bob，這樣查理等等
到這樣的數據結構中。但是，有一個問題。
如果梅艷芳嗎？
我們把安妮塔？她的名字也以字母A開頭，
感覺就像我們對這個問題做了一個更大的爛攤子。
現在，我們有直接的插入，插入固定的時間，到一個數據結構
最壞情況下的，而不是線性的，
但與梅艷芳在這種情況下，我們可以做嗎？
這兩個選項是什麼，真的嗎？是嗎？
[學生回答，不知所云]好吧，所以我們可以有另一個維度。
這是很好的。因此，我們可以建立在三維像我們談論口頭上週一。
在這裡我們可以添加另一個訪問，但沒有，我想保持這個簡單的假設。
這裡的目標是立即有固定時間的訪問，
因此，公司增加太多的複雜性。
其他選項時，試圖將這個數據結構梅艷芳是什麼？是嗎？
[學生回答，不知所云]好。因此，我們可以把其他人都下來，
像查理Bob和Alice引起了下來，然後，我們把梅艷芳，她真的想成為。
>> 當然，現在，這有一個副作用。
可能是有用的，不是因為我們要插入的人一旦這個數據結構
但是，因為我們要檢查，如果他們晚
如果我們想打印出所有的數據結構中的名稱。
我們要做的事情，最終與此數據。
所以，現在我們已經搞砸了，誰的愛麗絲不再，她應該是。
也不是鮑勃，也不是查理。
因此，也許這不是一個好主意。
但事實上，這是一種選擇。我們可能會改變每個人都下來，
心裡很不舒服，梅艷芳來晚了的遊戲，為什麼我們不能只是把梅艷芳
不在這裡，不在這裡，而不是在這裡，我們只是把她一點點在列表中上下。
但是，這個問題再次開始下放。
你也許能夠找到愛麗絲瞬間，她的名字。
和Bob瞬間，查理。但是，然後你看梅艷芳，
你看，嗯，愛麗絲的方式。
好了，讓我查一下下面的愛麗絲。鮑勃是不是梅艷芳。
查理是不是梅艷芳。哦，還有梅艷芳。
如果你繼續搭乘火車，邏輯的方式，
什麼是最壞情況下的運行時間發現或插入到這個新的數據結構梅艷芳？
這是O（n）的，對不對？
因為在最壞的情況下，有愛麗絲，鮑勃，查理。 。 。
一路下跌命名為“Y”的人，所以只有一個點離開。
值得慶幸的是，我們有沒有一個叫“Z”，所以我們把梅艷芳在最底層。
>> 我們還沒有真正解決這個問題。
所以，也許我們需要引入第三維。
而事實證明，如果我們不引進這第三個維度，
我們不能這樣做完美，但聖杯得到
固定時間的插入和動態插入，所以
我們沒有進行硬編碼的大小為26的數組。
我們可以將許多名字，因為我們希望，但讓我們在這裡休息5分鐘
然後做正確。
好的。我的故事，漂亮的人為有
通過選擇愛麗絲，然後Bob，然後查理，然後梅艷芳，
他的名字顯然是要碰撞與愛麗絲。
但我們週一結束的問題是它是如何可能的是
你會得到這些種類的衝突？換言之，
如果我們開始使用此表格的結構，這是真的只是一個數組，
在這種情況下，26個地點，
如果我們的輸入，而不是均勻分佈的，怎麼辦？
這不是人為Alice和Bob和Charlie和David等按字母順序，
它均勻地分佈在從A到Z
>> 也許我們會得到幸運的，我們不會有兩個A或B的
具有非常高的概率，但有人指出，
如果我們廣義這個問題，而不是0到25
但是，例如，從0到364或65，往往是一個典型的一年中的天數，
並提出這樣的問題，“什麼是概率在這個房間裡，我們兩個人有相同的生日嗎？”
它的另一種方式，什麼是概率，我們兩個人有一個名字開頭的嗎？
樣的問題是相同的，但這個地址空間，
本次搜索空間的生日是大的情況下，
因為我們有這麼多天，今年比字母在字母表。
的衝突概率是什麼？
好了，我們可以把這個搞清楚數學相反的方向。
沒有碰撞的概率是什麼？
好了，在這裡說，這表達的概率
如果只有一個人在這個房間裡，他們有一個獨特的生日？
這是100％。因為如果只有一個人在房間裡，
他或她的生日可以是任何365天的一年。
因此，三百六十五分之三百六十五選項給了我一個值為1。
所以，此刻的概率問題是只有1。
但是，如果有一個人在房間裡，
什麼是他們的生日的概率是不同的？
只有364天，忽略閏年，
他們的生日沒有碰撞與其他人。
因此，364/365。如果第三人來，它是363/365，並依此類推。
因此，我們將這些分數相乘，這是越來越小，
弄清楚，我們所有的人都有獨特的生日的概率是多少？
但我們可以，當然，只是這個答案和翻轉
和1負所有這一切，我們最終會得到一個表達
如果你還記得你的數學書的背面，它看起來有點像這樣，
這是更容易理解的圖形。
這裡這個圖形的x軸方向上的數量的生日，
或人與生日，和在y軸上的數量是一個匹配的概率。
這是什麼說的是，如果你有，比方說，甚至，
讓我們選擇像22，23。
如果有22或23人在房間裡，
的概率是那些極少數的兩個人有相同的生日
實際上是超級高，組合性。
50％的機率只有22人，研討會，幾乎一類，
2的那些人有相同的生日。
因為有這麼多的方法，讓你可以有相同的生日。
更糟的是，如果你右手邊的圖表，
的時候，你有一個類，它有58名學生，
2人的生日的概率是超級，超級高，幾乎100％。
現在，這是一種現實生活中的一個有趣的事實。
>> 但所帶來的影響，現在，數據結構和存儲信息
也就是說，假設你有一個漂亮，乾淨，均勻分佈的數據
你有一個足夠大的數組，以適應一堆東西
並不意味著你會得到人們的獨特的地方。
你要去有衝突。所以這個散列的概念，因為它是所謂的，
輸入像“愛麗絲”和按摩以某種方式
然後取回如0或1或2的答案。
從該函數獲取一些輸出正困擾著這個碰撞的概率。
那麼，我們如何處理這些衝突？
那麼，在一種情況下，我們可以採取的想法，建議。
我們就可以轉移倒眾人，或也許，多了幾分簡單，
而不是移動所有的人，讓我們只是梅艷芳的底部備有現貨。
因此，如果Alice是0，鮑勃是1，查理是2，
我們只是把梅艷芳在位置3。
這是一個數據結構稱為線性探測技術。
線性的，因為你走這條線，和你有幾分試探
可用的點的數據結構中。
當然，這種不滿轉化為O（n）。
如果數據結構確實充分，已經有25人，
，然後袁詠儀走來，她結束了在什麼位置Z，這很好。
她仍然適用，我們能找到她。
>> 但是，這是相反的目標，加快東西。
那麼，如果我們不是介紹了這第三個維度？
這種技術通常被稱為單獨的鏈接，或鏈。
是怎樣的一個哈希表，這個表結構，
你的表是一個指針數組。
但是，這些指針指向的是你猜怎麼著？
鍊錶。那麼，如果我們把這些世界最好的嗎？
我們使用數組的初始指標
到的數據結構，這樣我們就可以即刻前往[0] [1]，[30]等等，
但是，我們有一定的靈活性，我們可以適合梅艷芳，愛麗絲和亞當
和任何其他的名稱，
我們，而不是讓其他軸增長到任意。
截至週一，我們終於有鏈接列表，表達能力。
我們可以任意增長數據結構。
另外，我們可以只讓一個巨大的二維數組，
一個2維陣列中的行，但是這將是一個可怕的情況，如果一個
不夠大，更多的人，他的名字恰好開始A.
上帝保佑，我們必須重新分配一個巨大的二維結構
正因為有這麼多的人命名為A，
特別是當有所以幾個人命名為Z東西。
這將是一個非常稀疏的數據結構。
因此，它不是完美的，任何手段，但至少現在我們有能力
Alice或梅艷芳屬於立即找到，
至少在縱軸條款，
然後我們只需要決定把梅艷芳或翹在這個鍊錶。
如果我們不關心排序的事情，如何迅速，我們將愛麗絲成這樣的結構嗎？
這是恆定的時間。我們的指數為[0]，如果沒有一個人的存在，
艾麗斯在該鏈接的列表的開始。
但是，這不是一個大問題。因為如果梅艷芳然後是沿
一些步數後，梅艷芳屬於嗎？
那麼，[0]。面向對象編程。愛麗絲已經在該鏈接的列表。
>> 但是，如果我們不關心這些名稱進行排序，
我們就可以將愛麗絲過來，插入梅艷芳，但即使是恆定的時間。
即使有愛麗絲和亞當和所有這些其他的地名，
它不是真正的轉移他們的身體。為什麼呢？
因為我們剛剛在這裡做的與鍊錶，誰知道，這些節點呢？
所有你必須做的是移動的麵包屑。
將周圍的箭頭，你沒有實際移動周圍的任何數據。
因此，我們可以將梅艷芳，在這種情況下，瞬間。固定的時間。
因此，我們有固定時間的查找，插入固定時間的像梅艷芳的人。
但一種過於簡單化的世界。
如果我們以後要找到愛麗絲嗎？
多少個步驟是，將要採取的嗎？
[學生回答，不知所云]
沒錯。愛麗絲還沒鍊錶中的人數。
所以它不是很完美，因為我們的數據結構，再有這樣的垂直通道
然後它有這些鍊錶掛 - 實際上，讓我們畫一個數組。
這些鏈接列表，掛它看起來有點像這樣。
但問題是，如果愛麗絲和亞當和所有這些其他的地名
結束了越來越多的那邊，
發現有人可以結束了一堆的步驟，
bcause你必須遍歷鍊錶，
這是一個線性操作。
所以，真的，那麼，最終的插入時間是O（n），其中n是列表中的元素的數量。
除以，讓我們隨意m，其中m是多少鍊錶
，我們已經在此垂直軸。
換句話說，如果我們真正假設均勻分佈的名稱，
完全不現實的。顯然有比別人更多一些字母。
>> 但是，如果我們假定為均勻分佈的那一刻起，
我們有N總的人，和m總鏈
提供給我們，然後每個這些鏈的長度
相當簡單的將是的總量中，n鏈的數目除以。
所以N / M。但在這裡，我們可以將所有數學聰明。
m是一個常數，因為有​​一個固定數量的這些。
你會開始申報您的陣列，
我們不調整的垂直軸。根據定義，即固定不變的。
這是唯一的橫軸，可以這麼說，這改變。
因此從技術上講，這是一個常數。所以，現在，在插入時間
幾乎是O（n）的。
這樣就不會覺得所有的東西更好。
但是，什麼是真相嗎？那麼，這一切的時間，幾個星期，
我們一直在說為O（n²）。 O（N），2×N“， - N，再除以2。 。 。 ECH。
這是僅僅局限於N²。但現在，這部分的學期，
我們可以開始再次談論真實的世界。
N / M是絕對的速度比僅僅局限於N孤獨。
如果你有一萬餘名，你將它們分解為多個桶
所以，你有這些鏈中只有10名，
絕對搜索的十件事將是快千餘件事情。
因此，即將到來的習題會向你挑戰
即使認為正是，是啊，
漸近和數學，這還只是線性的，
它吸收一般時試圖找東西。
在現實中，它要快於
因為這個除數。
因此，有再一次將是這種權衡
理論和現實之間的衝突，
和一個旋鈕將在本學期開始轉向在這一點上
是更現實的一個，因為我們準備semster的結束，
為大家介紹一下世界的網絡編程，
真的，性能要算，因為你的用戶要
開始感受和欣賞糟糕的設計決策。
>> 那麼，你如何去實施一個鏈接 - 哈希表的31個元素呢​​？
前面的例子中任意生日。
如果有一個人生日1月1日或2月1日，我們將把它們放在這個桶。
如果這是1月2日，2月2日，3月2日，我們將把它們放在這個桶。
這就是為什麼它是31。如何聲明一個哈希表？
它可以是非常簡單的，的節點*表是我的任意名稱，[31]。
這給了我31節點的指針，
，讓我有31個指針鍊錶
即使這些鏈是最初為NULL。
把我想要什麼，如果我想存儲“愛麗絲”，“鮑勃”，“查理”嗎？
好了，我們需要用這些東西在一個結構
因為我們需要愛麗絲來指向給Bob，指向查理，等等。
我們不能只單獨的名字，這樣我就可以創建一個新的結構，稱為節點在這裡。
>> 什麼是實際的節點？在這個新的鍊錶節點是什麼？
第一件事情，叫字，是人的名字。
據推測，LENGTH，涉及一個人的名字的最大長度，
不管它是什麼，20，30，40個字符瘋狂的角落的情況下，
+1是為了什麼？這僅僅是額外的NULL字符，\ 0。
因此，這個節點是包裝內的“東西”本身，
但同時也宣告了一個指針稱為未來
這樣我們就可以鏈Alice給Bob查理等等。
可以為NULL，但不一定必須。
這些哈希表的任何問題嗎？是嗎？
[學生提問，不知所云]數組 - 很好的問題。
字符數組中的字，而不是僅僅的char *這是為什麼？
在這個有點亂的例子，我不想訴諸
對malloc為原來的名稱。
我想聲明的字符串的最大內存量
這樣我就可以複製到結構愛麗絲\ 0，而不必處理malloc和free之類的。
但我能做到這一點，如果我想成為更加自覺地空間使用。這個問題問得好。
因此，讓我們嘗試概括距離
和聚焦今天的其餘部分上的數據結構，更一般
和其他問題，我們能夠解決使用相同的基本面
即使自己的數據結構可能有所不同，在他們的資料。
>> 因此，原來在計算機科學中，樹是非常常見的。
你能想到的樹排序，就像一個家庭樹，
那裡的一些根，有的女家長或族長，
爺爺奶奶或或更早回來，
下面是和爸爸媽媽或各種兄弟姐妹等。
因此，一個樹結構的節點和它的孩子，
通常每個節點的0個或更多的孩子。
還有一些的專用術語，你在這張照片上看到的
任何小的孩子或孫子的邊緣
誰沒有從他們身上發出的箭頭，
這些是所​​謂的葉子，並在裡面的任何人
是一個內部節點，沿著這些線路，你可以把它叫做什麼。
但是，這種結構是很常見的。這其中的任意一點。
我們有一個孩子在左邊，我們有三個孩子的權利，
兩個孩子的左下角。
因此，我們可以有不同大小的樹木，但如果我們開始規範的東西，
您可能還記得二進制從帕特里克的視頻上搜索從以前的短
在線，二進制搜索不具有要實現的一個數組
或紙片在黑板上。
假設你想在一個更複雜的數據結構來存儲您的數字。
你可以創建一個這樣的樹。
你可以有一個在C中聲明的節點，該節點可以有它的內部的至少兩種元素。
一個是你要存儲的號碼，另一個是 - 好了，我們需要一個更。
另一種是它的孩子。
因此，這裡的另一種數據結構。這時候，一個節點被定義為存儲號碼Ň
然後兩個指針;左孩子和右孩子。
他們不是任意的。這棵樹有什麼有趣的嗎？
>> 在已經奠定了這一點，或如何帕特里克奠定了它在他的影片有什麼模式？
這是一種明顯的，有一些排序怎麼回事，
但什麼是簡單的規則嗎？是嗎？
[學生回答，不知所云]
完美的。如果你看一眼這，你會看到在左側的小數字，
大號碼的左側，但為每個節點，這是真的。
對於每個節點，其左子小於，大於它的右子樹。
這意味著什麼，現在是，如果我要搜索這個數據結構，也就是說，44號，
我必須從根開始，因為所有的這些更複雜的數據結構現在，
我們只有一件事，有一個指針開始。
在這種情況下，一開始是根。這不是左端，
它的這種結構的根目錄中。所以我在這裡看到的是55歲，和我期待的44。
我想往哪個方向去？
嗯，我想往左走，因為很明顯，在右邊將是太大了。
所以，注意在這裡，你樣的概念上砍了一半的樹
因為你永遠也不會下降的右手邊。
所以，現在我從55到33。這是過於小了一些。
我在尋找44，但現在我知道，如果44是在這棵樹，我可以去顯然是正確的。
所以，再一次，我修剪樹的一半。
這幾乎是相同的概念上的電話簿。
這是相同的，我們所做的在黑板上的文件，
但它是一個更複雜的結構，使我們能夠真正做到
這種分而治之的算法設計，
而事實上，穿越這樣的結構 - 哎呦。
遍歷這樣的結構，它只是“走這條路還是走那條路。”
意味著所有的代碼，彎曲你的心靈第一次執行時第
在家裡或步行通過，為二進制搜索，使用遞歸或迭代，
這是一個痛苦的脖子上。中間的元素，然後做你的四捨五入向上或向下。
>> 有一個美麗了，因為我們現在可以再次使用遞歸，
但更乾淨。事實上，如果你在55號和您想要尋找44，
在這種情況下，你向左走，然後你會怎麼做？您可以運行相同的算法。
檢查節點的值，然後你去左邊或右邊。
然後檢查節點的值，向左走還是向右。
這是非常適合遞歸。
因此，即使在過去，我們已經做了一些非常隨意的，涉及遞歸的例子
沒有需要的是遞歸的，數據鋼結構，
特別是樹木，這是一個完美的應用這個想法的一個問題，
縮小，然後解決相同類型的，但較小的，程序。
>> 所以，我們可以引進另一種數據結構。
這一個是在第一眼就看神秘的，但是這一次是驚人的。
因此，這是一個數據結構稱為特里，特里，這是繼承的詞檢索，
沒有明顯的重試時間間隔，但是這就是世人所謂的這些東西。嘗試。 T-R-I-E。
它是一個某種形式的樹結構，但在一個Trie樹的每個節點
似乎是什麼？這是一個有點誤導，因為它是一種簡稱。
但它看起來像這trie樹中的每個節點實際上是一個數組。
即使此圖的作者並沒有表現出它，
在這種情況下，這個線索是一種數據結構，其目的在生活中是存儲詞語
A-L-I-C-E或B-O-B等。
的方式，此數據存儲Alice和Bob和Charlie和梅艷芳等等
是使用一個數組來存儲，愛麗絲在特里，
它看起來像一個數組的根節點開始，
它被寫在速記符號。
筆者省略，ABCDEFG，因為有沒有名字。
他們僅表現為M和P和T，但在這種情況下，
讓搬走Alice和Bob和Charlie一些名字在這裡。
麥克斯韋實際上是在此圖中。
那麼，如何做的作者店M-X-W-E-L-L？
他或她的根節點開始，並到[M]，因此，大約13時，13日在數組中的位置。
然後從那裡，有一個指針。
導致另一個數組的指針。
從那裡到該數組的索引位置A，作為描繪在左上角，
那麼他或她跟著到另一個數組，指針，
去的指針位置X.
然後，在下一數組位置W，E，L，L，等等，
最後，讓我們真正嘗試把圖片。
節點看起來像在代碼中做了什麼？
trie樹中的一個節點包含多個節點的指針數組。
但也有，至少在這個實現了某種形式的布爾值。
我碰巧把它稱為is_word。為什麼呢？
因為當你插入麥克斯韋，你不插入
任何東西到這個數據結構。
你不寫M.你不寫X.
你做的是以下指針。
表示M，接著是表示A的指針，該指針的指針，該指針
然後指針，表示X，則W，E，L，L，
但結束時你需要做的是去，檢查排序，我達到了這個位置。
有在數據結構中的一個詞，在這裡結束。
>> 那麼什麼是特里真的是充滿了筆者選擇了代表
這些小三角總站。
這只是意味著這樣一個事實，這個三角形在這裡，這個布爾值true;
也就是說，如果你往後走的樹，
這意味著名為Maxwell是在這一個字。
但這個詞foo的，例如，
是不是在樹中，因為如果我開始在這裡的根節點在頂部，
有沒有F指針，無O指針，無O指針。 foo不是在這本字典的名稱。
但相反的是，圖靈，T-U-R-I-N-G。同樣，我沒有存儲t或u r或i或N或G。
但我沒有商店這個數據結構中的值的正確的方法，在這裡在此節點 - 樹
這個布爾值is_word設置為true。
因此，trie樹是種很有趣的元結構，
你不是真正的存儲的話自己這種字典。
要清楚，你只是存儲“是”或“否”，有一個詞在這裡結束。
>> 現在有什麼含義？
如果你有15萬字，在字典中，你想存儲在內存中
使用類似的鏈接列表，
你將有15節點的鍊錶。
發現這些詞的字母順序排列，可能需要O（n）的時間。
線性時間。但是，在這裡的情況下的線索，
什麼是運行時間找到一個詞？
原來，這裡的美景，即使你已經在這本字典有149,999個字，
如使用該數據結構實現，
找到或插入多一個人進認為，像愛麗絲，愛麗絲需要多少時間？
嗯，這是只有5個，也許6個步驟的尾隨字符。
由於結構中的其他名稱presense
沒有得到中的插入愛麗絲的方式。
此外，尋找愛麗絲曾經在這本字典有15萬字
在用自己的方式尋找愛麗絲在沒有得到，
因為Alice。 。 。 。 。在這裡，因為我發現一個布爾值。
如果沒有布爾值true，則Alice是不是這個數據結構中的話。
換言之，找東西和插入到這個新的東西的運行時間
數據結構的特里是O - 它不是N。
因為presense 15萬人沒有“愛麗絲夢遊仙境”的影響，它似乎。
因此，讓我們把它k，其中k是一個英語單詞的最大長度
這是通常不超過20的東西字符。
因此，k是常數。所以我們現在似乎已經找到了聖杯
是的特里，不變的插入，查找，刪除。
由於已經在結構的數目的事情，
這是甚至沒有親臨現場。同樣，他們只是排序的檢查，“是”或“否”，
沒有影響其未來的運行時間。
>> 但還有了一個catch，否則我們不會浪費這麼多時間
在所有這些其他的數據結構，最終得到的秘密是驚人的。
所以，我們要付出什麼樣的價格在這裡實現這一​​偉大嗎？空間。
這件事是巨大的。的原因，筆者
並不會出現在這裡，請注意，所有的這些東西，看起來像陣列，
他沒有畫出其餘的樹，其餘的特里，
因為他們只是不相關的故事。
但是，所有的這些節點是超級寬，樹中的每個節點佔用
26實際上，可能是27個字符，因為在這種情況下，我包括空間中的所有格符號
這樣我們就可以有apostrophized的話。
在這種情況下，這些都是寬陣列。因此，即使他們沒有picutured，
這佔用了大量的內存。
這可能是罰款，especilly在現代的硬件，
但是這是一個折衷。我們得到了更短的時間內，花更多的空間。
那麼，這是怎麼回事？
好吧，讓我們做的 - 讓我們在這裡看到的。
讓我們做一個跳轉到這個傢伙在這裡。
>> 不管你相信與否，盡可能多的樂趣為C已經有一段時間了，
我們到達點在本學期的時間過渡到更現代的東西。
在更高層次上的事情。即使在接下來的幾個星期
我們仍然會繼續埋頭在世界上的指針和內存管理
得到安慰，使我們可以再建，
比賽結束，最終還是引進，具有諷刺意味的是，這不是語言。
我們會花10分鐘，談論HTML一樣。
所有的HTML是一種標記語言，一種標記語言是什麼
這些系列開放式支架和封閉括號，說'這個大膽的“
“這斜體”，“使這個中心的。”
這是不是所有的智力有趣的，但它是超級有用的。
它肯定是無所不在的這些天。
但是，什麼是功能強大的HTML世界，更普遍的Web編程，
建立動態的東西的語言，如PHP或Python或Ruby或Java或C＃編寫代碼。
真的，無論你選擇的語言，並動態地生成HTML。
被稱為CSS動態生成的東西。
級聯樣式表，這也是對美學。
因此，即使今天，如果我去一些喜歡熟悉的Google.com網站，
我去查看，開發人員，查看源代碼，也許你以前做過，
但要查看源代碼，這東西可能看起來很神秘的。
但是，這是基本的代碼，實現Google.com。
在前端。而實際上這是蓬鬆的美學的東西。
這是CSS在這裡。如果我繼續向下滾動，我們會得到一些顏色編碼的東西。
這是HTML。谷歌的代碼看起來像一個爛攤子，但如果我真的打開不同的窗口，
在此，我們可以看到一些結構。
如果我打開這件事，請注意，這是一個有點更具可讀性。
我們不久會看到這個標籤，[字]是一個標籤，
HTML，頭部，身體，DIV，腳本，文本區，跨度為中心的分區。
這也有幾分神秘的前瞻性乍看之下，
但這個爛攤子遵循一定的模式和重複的模式，
因此，一旦我們得到的基本知識，你就可以寫這樣的代碼
然後操作使用另一種語言，稱為JavaScript代碼。
JavaScript是一種語言，運行在瀏覽器
今天，我們用哈佛的課程，該課程的購物工具，谷歌地圖使用
給你一大堆的活力，Facebook讓你顯示的即時狀態更新，
Twitter的使​​用它來顯示你的鳴叫瞬間。
所有這一切，我們將開始埋頭進來。
但到了那裡，我們需要了解一些關於互聯網。
這個夾子在這裡只是一分鐘之久，現在讓我們假設這是，其實，
如何在互聯網什麼來捉弄人。我給你“勇士的淨。”
>> [♫合唱音樂的慢♫]
男解說員，他帶著一個消息。
隨著自己的協議。
[♫更快的電子音樂♫]
他來到一個世界的酷防火牆的，漠不關心的路由器，
遠遠比死還要痛苦和危險。
他速度非常快。他的強者。他是TCP / IP，和他有你的地址。
勇士的淨。
[馬蘭]下週。互聯網。 Web編程。這是CS50。
[CS50.TV]