[Powered by Google Translate] [第6條] [舒適] 羅布·鮑登] [哈佛大學] 這是CS50。[CS50.TV] 我們可以前往我們的部分問題。我的空間，然後再發送URL。開始部分的問題說顯然，我並不完全unsick是一個很簡單的問題究竟什麼是Valgrind的？ 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]