[Powered by Google Translate] [第6條] [舒適]
羅布·鮑登] [哈佛大學]
這是CS50。[CS50.TV]
>> 我們可以前往我們的部分問題。
我的空間，然後再發送URL。
開始部分的問題說
顯然，我並不完全unsick是一個很簡單的問題
究竟什麼是Valgrind的？
Valgrind的是什麼辦？
任何人想要說什麼Valgrind的嗎？
[學生]：檢查內存洩漏。
是啊，Valgrind是一個一般的內存檢查。
，最終，它會告訴你，如果你有任何內存洩漏，
這主要是我們正在使用它，因為如果你想
問題集，或如果你想
大板，你需要有任何沒有內存洩漏，
如果你有內存洩漏，你不能找到，
也請記住，每當你打開一個文件時，
，如果你不關閉它，這是一個內存洩漏。
>> 很多人都在尋找一些節點，他們不釋放
真的，他們沒有關閉字典中的第一步。
它也告訴你，如果你有任何無效的讀取或寫入，
這意味著，如果你嘗試設置一個值
這超出堆的結束，它不會發生段故障
但Valgrind的捕獲它，你不應該寫在那裡，
，所以你絕對不應該有任何的那些要么。
你如何使用Valgrind的嗎？
>> 這是一個普遍的問題
種運行它，並期待在輸出端。
輸出壓倒了很多次。
也很有趣，如果你有一些非常錯誤的事情的錯誤
發生在一個循環中，那麼它最終會說，“太多的錯誤。
我要現在停止計數。“
它基本上是你要解析的文本輸出。
最後，它會告訴你，你有任何內存洩漏，
有多少塊，它可以是有用的，因為
如果是1塊未釋放，那麼它通常更容易找到
超過1000塊未釋放。
千的塊未釋放可能意味著你不釋放
您的鍊錶是否恰當一些。
這是Valgrind的。
>> 現在，我們有我們的部分問題，
您不需要下載。
您可以點擊我的名字和他們的空間。
現在點擊我。
第1次修訂將堆棧，這是我們正在做的第一個。
修訂2將隊列中，第三次修訂版將是單向鍊錶。
開始我們的堆棧。
因為它說，在這裡，一個堆棧是一個最基本的，
計算機科學的基本數據結構。
很典型的例子是
在食堂的托盤堆。
它基本上是只要你被介紹到堆棧，
有人會說，“哦，就像一個堆棧的托盤。”
您堆疊紙盤。
然後，當你去拉一個托盤，
第一盤，但最近拉的是放在堆棧中的最後一個。
該協議棧也喜歡在這裡說
我們有內存段稱為堆疊。
為什麼它被稱為堆棧？
>> 因為像一個堆棧的數據結構，
它壓入和彈出堆棧幀在堆棧上，
堆棧幀像一個特定的呼叫的功能。
就像一個堆棧，你將永遠有返回
從一個函數調用之前，你可以下降到較低的堆棧幀。
您可以沒有main調用foo調用酒吧和酒吧返回到主直接。
它總是遵循了正確的堆棧入棧和出棧。
就像我說的，這兩個操作，push和pop。
這些都是普及條款。
你應該知道，在棧不管是什麼方面的push和pop。
我們會看到隊列是一種不同的。
它並沒有真正有一個通用的術語，但是普遍的堆棧push和pop。
只是在棧上推。
流行是從堆棧中。
我們在這裡看到的，我們有我們的typedef結構棧，
所以，我們的char *字符串。
不要害怕任何**。
這將是一個字符串數組
或字符數組的指針，其中
指向字符的指針往往是字符串。
它沒有為字符串，但在這裡，他們將是字符串。
>> 我們有一個字符串數組。
我們有一個大小，表示目前有多少元素在棧上，
然後我們有能力，這是可以在棧上有多少個元素。
容量應開始大於1，
但規模要開始為0。
現在，基本上有三種不同的方式，你能想到的堆棧。
嗯，有可能更多，但兩種主要方式
你可以實現使用一個數組，也可以實現使用鍊錶。
鍊錶是一種微不足道的棧。
這是很容易使一個堆棧使用鍊錶，
所以在這裡，我們要製作堆棧使用數組，
，然後使用數組，有兩種方式，你可以考慮一下。
在此之前，當我說我們有能力為堆棧，
因此，我們可以容納一個元素在堆棧中。
>> 它可能發生的一種方式是，一旦你打10個元素，那麼你就大功告成了。
你可能知道，有一個上限的10件事情在世界上
你永遠也不會在棧上有10個以上的東西，
在這種情況下，你可以有你的堆棧的大小的上限。
或者你可以有你的堆棧是無界的，
但如果你正在做一個陣列，這意味著每一次你打10個元素，
那麼你會增長到20個元素，當你打20個元素，
你將有增長數組的30個元素或40個元素。
你會需要增加的能力，這是我們要在這裡做什麼。
每一次我們達到我們的堆棧的最大大小，
當我們把別的事情上，我們將需要增加的能力。
在這裡，我們推聲明為布爾推（字符*海峽）。
的char * str是字符串，我們推入堆棧，
和bool只是說我們是否成功或失敗。
>> 我們怎能不呢？
什麼是唯一的情況下，你能想到的
在這裡，我們需要返回false？
是啊。
[學生]：如果它是完整的，我們使用的是有界的實現。
是啊，所以我們定義，他說：
如果是完整的，和我們使用的是有界的實現。
然後，我們肯定會返回false。
只要我們打的10件事情在數組中，我們可以不適合11，所以我們返回false。
如果它是無界的，該怎麼辦？是啊。
如果出於某種原因，你不能擴展磁盤陣列。
是啊，所以內存是一種有限的資源，
最終，如果我們繼續推動入堆棧的事情一遍又一遍，
我們要嘗試分配一個更大的數組，以適應
產能較大，我們正在使用的malloc或任何會返回false。
好了，malloc將返回null。
>> 請記住，你曾經每一次調用malloc，你應該檢查，看它是否
返回null，否則這是一個正確的扣除。
因為我們希望有一個無限的堆棧，
唯一的情況下，我們將要返回false，如果我們試圖
增加的容量和malloc或任何返回false。
這時彈出不帶任何參數，
並且它返回字符串，該字符串是在堆棧的頂部。
無論是最近被壓入堆棧彈出返回，
它也把它從棧中刪除。
發現，它返回null，如果在棧上有什麼。
它始終是可能的堆棧是空的。
在Java中，如果你使用，或其他語言，
試圖從一個空棧中彈出，可能會導致異常或什麼的。
>> 但在C，空是種了很多的情況下，我們如何處理這些問題。
返回null是我們要如何表示的堆棧是空的。
我們提供的代碼，將測試協議棧的功能，
實現push和pop。
這會不會是大量的代碼。
我會實際上，在我們這樣做之前，提示，提示
如果你還沒有看到它時，malloc是不是唯一的功能
為您的堆分配內存。
有一個家庭的alloc函數。
首先是malloc的，你已經習慣了。
然後釋放calloc，做同樣的事情的malloc，
但它會為零，一切為你。
如果你曾經想將一切設置為null後mallocing的東西
你應該只是用來釋放calloc，而不是寫在首位
一個循環零出整個內存塊。
>> 如malloc和realloc是有很多的特殊情況下，
但基本上什麼realloc的是
它需要一個已經分配的指針，該指針。
realloc是你想要的功能，關注這裡。
它需要一個已經從malloc返回的指針。
比方說，你從malloc要求10個字節​​的指針。
後來你意識到你需要20個字節，
所以你調用realloc的，20個字節的指針，
和realloc會自動複製過來的一切都是為了你。
如果你只是叫的malloc再次，像我有塊10個字節​​。
現在我需要一個20字節的塊，
因此，如果我malloc的20個字節，那麼我必須手動複製10個字節​​的第一件事
進入第二件事情，然後自由的第一件事。
realloc的會為你處理。
>> 請注意，簽名會是void *，
這是只返回一個指針，指向的內存塊，
void *的指針。
作為一個通用的指針，你可以認為是void *。
一般情況下，你永遠不處理用void *，
但malloc（）並返回一個void *，然後它只是用來像
這實際上是將是一個char *。
，以前的void * malloc返回的
現在要通過向realloc，然後大小
是你要分配的字節數，因此新的能力。
我給你一兩分鐘，這樣做在我們的空間。
開始第1次修訂。
我會停下來後，希望能有足夠的時間執行推入，
然後，我給你做流行音樂的另一種突破。
但它確實是沒有那麼多的代碼在所有。
大多數的代碼可能擴大的東西，擴充產能。
好了，沒有壓力，完全做到，
但只要你覺得你是在正確的道路，這是很好的。
>> 沒有人有任何的代碼，他們與我拉起來感覺很舒服嗎？
是的，我會的，但沒有人有任何的代碼，我可以拉起來嗎？
好了，你可以啟動，保存它，不管它是什麼？
我總是忘了這一步。
好吧，看在推，
你要解釋你的代碼嗎？
[學生]：首先，我增加的大小。
我想，也許我應該有，反正，我增加的大小，
我看看它的容量不足。
如果是容量不足，我添加到數組中，我們已經有了。
而且，如果不是的話，我的能力乘以2，
我和重新分配的字符串數組的東西，現在更大的容量大小。
然後如果失敗了，我告訴用戶並返回false，
如果它的罰款，然後我把字符串在新的位置。
>> [羅布B.還要注意，我們這裡用一個漂亮的位運算符
乘以2。
請記住，左移總是要乘以2。
除以2，只要你記住，它意味著右移
除以2除以2的整數。
它可能會截斷在這裡或那裡。
但左移1總是要被乘以2，
除非你的整數溢出邊界，那麼就不會是。
A面註釋。
我喜歡做，這是不會改變的編碼任何方式，
但我喜歡做這樣的事情。
它實際上是要使其稍長。
這也許是不完美的情況下顯示，
但我喜歡分割成塊，
好吧，如果這一點，如果發生了，那麼我要做的事情，
，然後函數完成的。
我不需要，然後一路向下滾動我的眼睛的功能
看看會發生什麼後，其他。
如果這如果發生的話，我就回來。
它也有額外的好處，一切都超出了這個漂亮的
現在左移一次。
我不再需要，如果你曾經冗長得可笑的近線，
然後這4個字節可以提供幫助，也更左的東西，
少不堪重負，你覺得如果想好了，我一定要記住
我目前在一個while循環內的其他內的循環。
任何地方，你可以馬上做到這一點回報，我倒是很喜歡。
這是完全可選的，並且預期不會以任何方式。
>> [學生]：應該有一個大小 - 在故障條件？
故障條件在這裡，我們向realloc失敗，所以，是的。
請注意，在故障條件下，據推測，
除非我們免費的東西，我們總是要失敗
無論多少次，我們試推的東西。
如果我們繼續推動我們不斷遞增，規模，
即使我們不把任何東西壓入堆棧。
通常，我們不會增加的大小，直到
之後，我們已經成功地把它放在堆棧中。
我們將做到這一點，說，無論是在這裡和這裡。
然後，不要說s.size≤能力，它的容量小於，
只是因為我們搬到這裡的一切。
>> 請記住，唯一的地方，我們可能會返回false
在這裡，這裡的realloc返回null，
如果你碰巧要記住標準錯誤，
也許你會認為這是一個情況下，你要打印一個標準的錯誤，
fprintf STDERR，而不是直接打印到標準輸出。
再次，這是不是一種期望，但如果它是一個錯誤，
輸入輸出，那麼你可能希望將它打印到標準錯誤，而不是標準輸出。
>> 任何人還有什麼要注意的嗎？是。
[學生]：你去[聽不清]？
[羅布B.]是的，或實際binariness，只是它是什麼呢？
[學生]：所以你將它乘以2？
[羅布B.]是啊，基本上是這樣。
在二進制的土地，我們總是有一組數字。
移此由1左側基本上將它插入這裡在右側。
返回到這一點，只是記住，一切以二進制
是2的冪，所以這表示2到0，
這2到1，這2到2。
右側插入一個0到現在，我們只是改變一切。
曾經被認為是2 0現在是2到1，2 2。
我們插入右側，
一定是0，
這是有道理的。
如果你曾經一個數字乘以2，這不是要結束了奇數，
所以2〜0的地方應為0，
這是什麼我一半警告說，如果你之前是發生轉移
以外的一個整數中的比特數，
那麼這個1是要最終會關閉。
這是唯一的擔心，如果你碰巧要處理的非常大的能力。
但在這一點，那麼你正在處理的數組數十億美元的東西，
可能不適合到內存中了。
>> 現在，我們可以得到流行，這是更容易。
你可以不喜歡，如果你碰巧彈出一大堆，
現在你的一半容量。
你可以realloc的縮小的內存量，
但你不必擔心，所以只有realloc的情況下，將是
日益增長的記憶，永遠不會萎縮的內存，
這是會彈出超級簡單的。
現在要像棧，隊列，
但順序是相反的，你拿東西出來。
隊列中的典型例子是一條線，
所以我想，如果你是英語，我會說
一個典型的例子是一個隊列的隊列。
因此，像一條線，如果你是行的第一人，
您期望成為第一個出列的人。
如果你是行的最後一個人，你會是最後一個人服務。
我們稱之為FIFO模式，而堆棧是後進先出法的模式。
這些話是非常普遍的。
>> 就像棧和，不像數組，隊列通常不允許在中間的元素。
在這裡，我們有一個堆棧，push和pop。
在這裡，我們碰巧召他們入隊和出隊。
我也聽到他們叫shift和unshift。
我已經聽到有人說push和pop也適用於隊列。
我聽說插入，刪除，
所以push和pop，如果你正在談論有關棧，入棧和出棧。
如果你說的隊列，你可以選擇你要使用的話
插入和刪除，是應該叫什麼沒有達成共識。
但在這裡，我們有入隊和出隊。
現在，該結構看起來幾乎相同的堆棧結構。
但是，我們必須跟踪頭。
我想在這裡說的，但為什麼我們需要的頭嗎？
的原型基本上是相同的push和pop。
你可以把它看成push和pop。
唯一的區別是彈出的返回，而不是最後的，它的第一個返回。
2，1，3，4，或東西。
這裡的開始。
我們的隊列已經完全滿了，所以有四個元素在裡面。
結束我們的隊列當前為2，
現在我們去插入別的東西。
>> 當我們要插入其他的東西，我們所做的堆棧版本
是我們擴大了我們的內存塊。
這個是什麼問題呢？
[學生]：你提出的2。
我說的隊列結束前，
這沒有任何意義，我們開始為1，
然後，我們要出列1，然後出隊，出隊4
然後出列，然後出列，這一個。
我們現在不能使用realloc，
最起碼，你有，使用realloc以不同的方式。
但你可能不應該只是使用realloc。
你將必須手動複製你的記憶。
>> 有兩個函數複製內存。
有存儲器複製和memmove。
我目前正在讀，看看哪一個你將要使用的手冊頁。
好了，存儲器複製，不同的是
存儲器複製和memmove，而正確處理的情況下
您在何處複製到一個區域發生重疊的區域
你複製。
存儲器複製不處理。 Memmove。
你能想到的問題，
比方說，我要複製這個傢伙，
這四個這傢伙過來。
最後，該數組應該像
後的副本是2，1，2，1，3，4，然後在最後的一些東西。
但是，這是依賴於複製的順序，
因為如果我們不考慮該地區的事實，我們複製到
我們複製重疊，
然後，我們可能不喜歡開始，在這裡，我們想要去的地方複製2，
然後將指針向前發展。
>> 現在，我們要在這裡和這裡，現在我們要複製
這傢伙在這個傢伙的指針向前移動。
我們將最終得到的是2，1，2，1，2，1
而不是在適當的2，1，2，1，3，4，因為
2，推翻了原來的3，4。
Memmove處理是正確的。
在這種情況下，基本上只是使用memmove
因為它處理是正確的。
它一般不執行任何惡化。
我們的想法是開始，而不是從一開始就複製這種方式
就像我們剛剛在這裡做的，從去年底開始和複製，
在這種情況下，你可以永遠不會有問題。
有沒有性能上的丟失。
請務必使用memmove。再也不用擔心存儲器複製。
這就是你要去的地方有單獨memmove
包裹的部分，您的隊列。
不用擔心，如果沒有完全做到。
這是更加困難比棧，推，和流行。
>> 任何人有任何的代碼，我們可以使用？
即使完全不完整？
[學生]：是的，這是完全不完整的，雖然。
完全不完全是罰款，只要我們能為您節省修訂？
我忘了，每一次。
好了，忽略了會發生什麼，當我們需要調整的東西。
完全忽略調整大小。
解釋一下這段代碼。
我首先檢查如果尺寸小於首先複印
，然後在那之後，我將我頭+大小，
我要確保它環繞的數組的容量，
我在該位置插入新的字符串。
然後我增加的大小，並返回true。
>> 羅布B.]這是肯定的情況下，你會希望使用的模之一。
任何一種情況下，你已經環繞著，如果你認為周圍包裹，
馬上想到的應該是MOD。
作為一個快速優化/較短的一行代碼，
您發現該行緊隨
只是大小+ +，所以你合併入這行，大小+ +。
在這裡，我們的情況下，
我們沒有足夠的內存，
所以我們提高我們的能力，2。
我想你可以在這裡有同樣的問題，但現在我們可以忽略它，
其中，如果你沒有提高你的能力，
然後，你會想，以減少你的能力，2。
另一個短值得注意的是，就像你可以做+ =，
你也可以做<< =。
前平等，幾乎什麼都可以去，+ =，| =，＆=，<< =。
新的char *是我們的新的內存塊。
哦，在這裡。
>> 人怎麼看我們的新的內存塊的類型嗎？
[學生]：應該是char **。
回想我們的結構在這裡，
字符串是什麼，我們重新分配。
我們正在一個全新的動態存儲在隊列中的元素。
我們要分配給你的字符串就是我們mallocing的，現在，
等新的將是一個char **。
這將是一個字符串數組。
那麼，是什麼的情況下，我們要返回false？
[學生]：我們應該做的char *？
羅布B.]是的，良好的通話。
[學生]：那是什麼？
[羅布B.我們想要做的char *的大小，因為我們不再是
這實際上是一個很大的問題，因為大小（字符）將是1。
SIZEOF的char * 4，
所以很多時候，你正在處理int類型，
你會得到它，因為尺寸大小的int * int和
在32位的系統將是同樣的事情。
但在這裡，大小（字符）和sizeof（CHAR *）現在將是同樣的事情。
>> 在我們返回false是什麼情況？
[學生]是空的。
是的，如果新為空，則返回FALSE，
我要在這裡摔倒
[學生] [聽不清]
羅布B.]是啊，這是好的。
你既可以做2次，容量或容量移1，然後將其設置或任何。
我們會做到這一點，因為我們有它。
容量>> = 1。
你永遠不會有擔心失去的地方
因為你左移1，所以1的地方必然是一個0，
所以右移1，你仍然會好起來的。
[學生]：你需要做的是在返回之前？
羅布B.是的，這使得完全沒有意義。
>> 現在假設我們要最終結束返回true。
方式我們要做這些memmoves的，
我們必須要小心我們如何做。
沒有任何人有任何建議，我們如何做？
下面是我們的開始。
不可避免的是，我們要再次從頭開始
和從那裡複製的東西，1，3，4，2。
你是怎麼做到的呢？
首先，我必須看的手冊頁memmove。
memmove，而參數的順序是非常重要的。
我們希望我們的目標首先，源第二，規模第三。
有很多扭轉源和目標的功能。
目標，源往往有些是一致的。
移動，它返回的是什麼？
它返回一個指針到目的地，不管是什麼原因，你可能想。
我能想像讀它，但我們要進入我們的目的地。
>> 什麼是我們的目標又如何呢？
[學生]。
羅布B.是的，和我們複製的呢？
我們要複印的第一件事情是這樣的1，3，4。
這是-1，3，4。
這地址是什麼？
這1的地址是什麼？
[學生] [聽不清]
[羅布B.]頭+的第一個元素的地址。
我們怎樣才能在數組的第一個元素？
[學生]：隊列中。
羅布B.]是的，q.strings。
請記住，在這裡，我們的頭是1。
織補它。我只是覺得這是奇蹟般地
在這裡，我們的頭是1。我要改變我的顏色。
這裡是字符串。
這一點，我們可以把它寫在這裡我們做了
用頭+ q.strings。
很多人也寫它與q.strings的頭。
這是不是真的任何效率不高。
你可能會認為它為您提領，然後得到的地址，
但編譯器將它翻譯成我們以前的事，反正，q.strings +頭。
無論哪種方式，你要考慮它。
>> 我們要複製多少字節？
[學生]：能力 - 頭。
能力 - 頭。
然後你就可以一直寫的一個例子
搞清楚，如果這是正確的。
[學生]：它需要除以2，然後。
是啊，所以我想我們可以使用大小。
我們仍然有大小，
使用大小，我們有大小等於4。
我們的規模是4。我們的頭是1。
我們要複製這3個元素。
這就是合理性檢查，尺寸 - 是正確的3頭。
回來這裡，就像我們之前說的，
如果我們使用的能力，那麼我們就必須除以2
因為我們已經長大了我們的能力，所以不是，我們會使用大小。
副本的那部分。
現在，我們需要複製的其他部分，剩下的部分開始。
>> 這是怎麼回事memmove到什麼位置？
[學生]：加上大小 - 頭。
是的，所以我們已經複製的大小 - 頭字節，
，所以在這裡我們要複製剩餘的字節是新的
然後大小負好，我們的字節數已經複製英寸
然後我們複製的呢？
[學生]：Q.strings [0]。
羅布B.]是的，q.strings。
我們可以做和的q.strings [0]。
這是比這明顯不太常見。
如果它只是為0，然後你會傾向於看q.strings。
這就是我們正在複製。
多少個字節我們還剩下複製？>> [學生]：10。
右。
[學生]：我們要乘5 - 10倍的大小的字節或什麼的？
是啊，所以這是究竟是什麼，我們複製嗎？
[學生] [聽不清]
我們在複製的東西的類型是什麼呢？
[學生] [聽不清]
是啊，這樣的char *，我們複製，我們不知道那些來自。
好了，他們指著，像琴弦，我們最終將其推到隊列中
或到隊列中進行排隊。
如果這些都來自我們不知道。
我們只需要跟踪的char *自己。
我們不希望複製的大小 - 頭字節。
我們要複製的大小 - 頭的char *，
所以，我們要乘這個大小（char *）的。
在這裡，頭*大小（CHAR *）。
>> [學生]：怎麼樣[聽不見的？
這項權利在這裡嗎？
[學生]，下面的大小 - 頭。
羅布B.這項權利在這裡嗎？
指針的算術運算。
指針運算是如何去上班
它會自動將的類型，我們正在處理的大小。
就像在這裡，新+（大小 - 頭）
是完全等同於和新的大小 - 頭]
直到我們預計正常工作，
因為如果我們要處理的一個int數組，然後我們不要索引的INT-
如果它的大小為5，和你想的第4個元素，然後我們索引
int數組[4]。
你不 - [4] *大小的int。
來處理它，這種情況下自動
簡直是等同的，所以括號的語法
只是要轉換為只要你編譯。
這件事情你需要小心
當你加入的大小 - 頭
你是不是一個字節。
您要添加一個char *，它可以是一個字節或什麼的。
>> 其他問題嗎？
好了，出隊會更容易。
我給你一分鐘的時間來實現。
哦，我想這也是同樣的情況
排隊的情況下，如果我們入隊空，
也許我們要處理它，也許我們不這樣做。
我們不會再在這裡，但我們的堆棧情況下相同。
如果我們加入隊列為空，我們可能要忽略它。
任何人有一些代碼，我可以拉起來嗎？
[學生]：我只是出隊。
第2版​​是沒事。
你想說明什麼？
[學生]：首先，你要確定有什麼東西在隊列中
而且其大小是由1。
你需要做的，然後返回頭
然後將頭1。
好了，所以我們必須考慮的一個角落的情況。是啊。
[學生]：如果你的頭是在最後一個元素，
然後，你不想頭指向陣列外。
>> 是啊，所以只要頭打我們的陣列，
我們出列的時候，我們的頭被改裝為0。
不幸的是，我們不能做到這一點的一個步驟。
我想我可能會解決它是
這是怎麼回事，我們正在返回，是一個char *
無論你的變量名要。
然後，我們希望我們的能力，國防部頭
然後返回漚。
很多人在這裡，他們可能會做
這種情況下，您看人家做頭
大於產能，做頭 - 能力。
而這僅僅是解決mod是什麼。
頭模能力是乾淨多了
一個周圍環繞的比大於容量頭 - 能力，如果頭。
>> 有問題嗎？
好了，我們剩下的最後一件事是我們的鍊錶。
你可能會使用一些鍊錶行為，如果你沒有
在哈希表，鍊錶，如果你做了一個哈希表。
我強烈建議做一個哈希表。
您可能已經做了特里，
但嘗試都比較困難。
從理論上講，他們是漸近更好。
但就在大板，
並嘗試從來沒有做的更好，，他們佔用更多的內存。
一切有關嘗試最終被更多的工作差。
這是大衛·馬蘭的解決方案始終是
是他的帖子他的特里的解決方案，讓我們來看看他目前是。
他是幹什麼的“，DAVID J？
他是第18，所以這不是差得要命，
，這將是一個最好的嘗試，你能想到的
或一個最好的嘗試的線索。
這難道不是他原來的解決方案嗎？
我覺得，像特里解決方案更傾向於在此範圍內的內存使用。
>> 你下到最高層，和RAM的使用是在個位數。
向下朝下方，然後你開始看到試圖
你在哪裡得到絕對使用大量的RAM，
嘗試都比較困難。
不完全是值得的，但教育經驗，如果你沒有一個。
最後一點是我們的鏈接列表，
，這三個東西，棧，隊列，鍊錶，
你做的任何未來的事情在計算機科學
假設你熟悉這些東西。
他們只不過是一切的根本。
>> 鏈接列表，在這裡我們有一個單鍊錶，將是我們實現。
什麼是單鍊錶，雙向鍊錶的意思，而不是？是。
[學生]：只點到下一個指針，而不是指針，
像一個前它和它的一前一後。
是啊，所以在圖片格式上，我只是做嗎？
我有兩件事。我有圖片，圖片。
在圖片格式上，我們的單鍊錶，
不可避免地，我們有我們的列表的頭指針種，
然後在我們的名單，我們只是有三分球，
也許這點為空。
這將是一個單向鍊錶的典型示意圖。
一個雙向鍊錶，你可以倒著走。
如果我給你列表中的任何一個節點，那麼你就一定能獲得
列表中的任何其他節點，如果它是一個雙向鍊錶。
但是，如果我讓你在列表中的第三個節點，這是一個單向鍊錶，
沒有辦法，你對你將要得到的第一個和第二個節點。
有利弊，一個明顯的例子
是你採取了更多的大小，和你有這些東西現在都指向跟踪。
但是，我們只關心單鍊錶的。
>> 有幾件事情，我們將不得不實行。
你的typedef結構節點，INT I：結構節點下;節點。
該typedef應燒入你的心。
測驗1應該是這樣的一個typedef一個鍊錶節點，
你應該能夠立即潦草下來
甚至沒有考慮它。
我猜一對夫婦的問題，為什麼我們需要結構的嗎？
我們為什麼不能說的節點*？
[學生] [聽不清]
是啊。
定義了一個節點的唯一的事情
是typedef本身。
但是這一點，當我們種的解析通過這個結構節點定義，
我們還沒有完成我們的typedef，因為typedef還沒有完成，
節點不存在。
但結構節點呢，這個節點在這裡，
這也可以被稱為什麼都重要。
這可以被稱為n。
它可以被稱為鍊錶的節點。
它可以被稱為什麼。
但是，這需要調用同樣的事情，這個結構節點結構節點。
你也可以在這裡，
等還回答了第二點的問題
這就是為什麼有很多的時候，你看到的結構和類型定義的結構體，
你會看到匿名結構的話，你會看到typedef結構，
實施結構，字典，或其他。
>> 為什麼我們在這裡需要說的節點？
為什麼不能是一個匿名的結構？
這幾乎是同樣的回答。
[學生]：您需要在struct來引用它。
是啊，在結構，你需要參考的結構本身。
如果你不給結構體的名稱，如果它是一個匿名的結構，你可以不引用它。
最後，但並非最不重要的，這些都應該是有些簡單的，
他們應該幫助你實現，如果你寫下來
你做錯了什麼，如果這些事情是沒有意義的。
最後但並非最不重要的一點是，為什麼會發生這種結構節點*？
為什麼它不能只是結構的節點嗎？
[學生]：到下一個結構體的指針。
這是不可避免的，我們想要的東西。
為什麼它永遠不會是結構節點下？
為什麼有是結構節點下的嗎？是啊。
[學生]：這是一個無限循環。
是啊。
[學生]：這將是中的一個。
是啊，就認為我們將如何做大小或東西。
一個結構的大小基本上是+或 - 在這裡或那裡一些模式。
它基本上是要的事情，在結構尺寸的總和。
不改變任何東西，在這裡，大小是一件容易的事。
結構節點的大小將是大小的i +尺寸的未來。
的i的大小將是4。下次的大小將是4。
結構節點的大小將是8。
如果我們不*，思維的sizeof
然後大小（ⅰ）將是4。
結構節點的大小未來將是結構節點下的大小為I +大小
+我+尺寸的結構節點下的大小。
這將是一個無限遞歸的節點。
這就是為什麼這是怎麼會事必須的。
>> 再次，一定記住，
或至少​​理解不夠，你可以可以
通過它看起來應該像什麼原因。
我們將要實現的事情。
如果列表長度
你可以欺騙，並保持周圍
全球的長度或東西，但我們不打算這樣做。
我們要算列表的長度。
我們已經包含，所以這基本上是一樣的搜索，
所以我們有一個鍊錶的整數，如果這個整數鍊錶中。
前面加上要插入在列表的開頭。
附加將要插入的結束。
Insert_sorted要插入排序列表中的位置。
Insert_sorted種假設你從來沒有使用前置或附加在惡劣的方式。
>> 當你實施Insert_sorted insert_sorted -
比方說，我們有我們的鍊錶。
這是它目前看起來，2，4，5。
我想插入3個，所以只要已排序的列表本身，
可以很容易地發現其中3屬於。
我從2開始。
好了，3是大於2的，所以我想繼續下去。
哦，是太大了，所以我知道要在2至4，
我有固定的指針和所有的東西。
但是，如果我們沒有嚴格使用insert_sorted，
喜歡讓我們只想說，我在前面加上6，
我的鏈接列表將成為這個。
現在，它沒有任何意義，所以的insert_sorted，你可以假設
是對列表進行排序，即使操作
這可能會導致不進行排序，就是這樣。
找到一個有用的插件，所以這些都是主要的事情，你將不得不實行。
>> 現在，花一分鐘的長度和包含，
這些應該是比較快的。
接近關門時間，所以任何人有任何長度或包含？
他們將是幾乎相同的。
[學生]：長度。
讓我們來看看，修訂工作。
好吧。
你想說明什麼？
[學生]：我只是創建一個的指針節點，並把它初始化為第一，這是我們的全局變量，
然後我檢查，看它是否為null，所以我沒有得到段故障，並返回0，如果是這樣的話。
否則，我遍歷，跟踪的內的整數
多少次，我已經訪問列表中的下一個元素
和在相同的增量操作也訪問該實際元素，
然後我不斷地檢查，看它是否為NULL，
，如果它是空的，那麼它中止，只是返回我訪問過的元素。
>> [羅布B.]有沒有人有任何意見什麼？
這看起來精細的正確性明智的。
[學生]：我不認為你需要的節點== NULL。
是啊，所以如果節點== null返回0。
但如果節點== NULL，那麼這個，哦，有一個正確的問題。
這只是你回到我的，但它現在不在範圍之內。
你只需要我，所以我= 0。
但是，如果節點是空的，那麼我仍然為0，
我們將返回0，所以這種情況是相同的。
另一種常見的是要保持的聲明
節點內的for循環。
你可能會說，哦，不。
讓我們保持它，因為這。
我可能會放INT I = 0在這裡，
然後節點節點第一次在這裡。
這可能是如何擺脫現在的這種。
這可能是我會怎麼寫。
你也可以看它是這樣的。
在這裡循環結構，這
應該是幾乎一樣自然地為int i = 0
i是小於數組的長度一+ +。
如果這就是你如何遍歷一個數組，你這是怎麼遍歷一個鍊錶。
>> 在某些時候，這應該是第二自然。
考慮到這一點，這將是幾乎同樣的事情。
你將要遍歷一個鍊錶。
如果節點的價值是什麼，我不知道。
節點i。
如果該節點的值=返回true，這就是它。
請注意，只有這樣，我們永遠返回false
的是，如果我們遍歷整個鍊錶，永不返回true，
所以，這是什麼做的。
作為一個方面說明，我們可能不會得到要前插或追加。
>> 快速最後一個音符。
如果你看到了static關鍵字，所以讓我們說靜態詮釋計數= 0，
然後我們做數+ +中，你可以基本上認為它作為一個全局變量，
即使我只是說，這不是我們要如何落實長度。
我這樣做是在這裡，再算上+ +。
任何方式，我們就可以進入到我們的鏈接列表，我們正在增加我們的計算節點。
這點是static關鍵字意味著什麼。
如果我剛做了詮釋計數= 0，這將是一個普通的老全局變量。
靜態詮釋計數裝置是什麼，它是一個全局變量，這個文件。
這是不可能的其他一些文件，
想到的pset 5，如果你已經開始。
你有都speller.c，和你有dictionary.c，
和，如果你只是全球申報的事情，那麼在speller.c
可以訪問在dictionary.c，反之亦然。
全局變量。c文件的任何訪問，
但靜態變量只能在文件本身，
所以裡面的法術檢查或內部dictionary.c的，
這是我的數組的大小如何，我會宣布我的變量
我在字典中的單詞數的大小。
因為我不希望聲明一個全局變量，任何人都可以訪問，
我真的只關心我自己的目的。
>> 好的事情也整個名稱衝突的東西。
如果有其他文件試圖使用一個全局變量數，事情會變得非常，非常錯誤的，
所以這很好地保持安全起見，只有你可以訪問它，
並沒有其他人就可以了，如果有人聲明了一個全局變量數，
然後，它不會干擾您的靜態變量數。
這是靜態的。它是一個文件的全局變量。
>> 問題什麼呢？
所有的設置。再見。
[CS50.TV]