揚聲器1：對，所以我們又回來了。 歡迎CS50。 是星期七月底。 所以記得，最後一次，我們開始 稍微複雜的看 的數據結構。 由於到現在為止，我們真的 在我們的處置是這樣的，一個數組。 但在此之前我們不會丟棄數組 所有有趣的，這的確 實際上，是一些什麼 加上這個簡單的數據 結構，從而有多遠？ 什麼是它擅長的？ 到目前為止，我們已經看到？ 你得到了什麼？ 什麼也沒有。 學生：[聽不清]。 揚聲器1：那是什麼？ 學生：[聽不清]。 揚聲器1：固定尺寸。 OK，那麼，為什麼是固定大小的好，雖然？ 學生：[聽不清]。 揚聲器1：確定的，所以它的效率 這個意義上，你可以分配一個 固定大小的空間，希望 恰恰是盡可能多 空間，只要你想。 所以這可能是一個絕對加分。 一個數組的另一側什麼？ 是嗎？ 學生：[聽不清]。 揚聲器1：所有的 - 對不起？ 學生：[聽不清]。 揚聲器1：在內存中的所有箱子 或給對方。 這是有幫助的 - 為什麼？ 這是相當正確的。 但如何才能利用這一真理嗎？ 學生：[聽不清]。 揚聲器1：沒錯，我們可以跟踪 一切都只是知道 一個地址，即地址 該內存塊的第一個字節。 或字符串的情況下， 地址的第一個 在該字符串中的字符。 並從那裡，我們可以找到 結束的字符串。 我們可以找到的第二個元素， 第三個元素，依此類推。 等花俏的手法描述， 特點是陣列給我們 隨機訪問。 只需使用方括號 符號和數字，你可以跳 一個特定的數組中的元素 在固定時間內，大O 之一，可以這麼說。 但也有一些缺點。 數組不是很容易做嗎？ 什麼不擅長什麼？ 學生：[聽不清]。 揚聲器1：那是什麼？ 學生：[聽不清]。 揚聲器1：在規模擴大。 所以的缺點數組是 正好相反的是什麼 一面是。 所以，一個缺點是 ，這是一個固定大小的。 所以你不能真正成長。 您可以重新分配更大的大塊 內存中，然後將舊的元素 到新的數組。 然後釋放舊的陣列， 例如，通過用malloc或類似的 函數調用realloc的， 重新分配內存。 REALLOC，順便說一句，試圖給你 內存陣列旁邊 你已經有了。 但它也可能移動的東西 周圍完全。 但總之，這是昂貴的，對不對？ 因為如果你有一大塊的內存 這個長度，但是你真的想要一個 這種規模，你要保留 你有原創要素， 大致的線性時間複製過程 需要發生 新的舊的陣列。 和現實要求的經營 系統一而再，再而 再大的內存塊，就可以開始 花費你一些時間。 因此，它既是祝福和詛咒 偽裝，但事實上，這些陣列 固定大小。 但是，如果我們引入，而不是東西 這樣，我們稱為聯 列表中，我們得到了一些積極和 幾個缺點在這裡。 所以一個鍊錶是一個簡單的數據 結構由C結構 情況下，當一個struct，召回，只是 用容器的一個或多個特定 類型的變量。 在這種情況下，什麼數據類型 似乎是裡面的結構， 我們最後一次稱為一個節點？ 這些矩形中的每一個是一個節點。 並且每個小矩形 裡面它是一種數據類型。 什麼樣的類型，我們說 他們在星期一？ 是嗎？ 學生：[聽不清]。 揚聲器1：變量和指針，或 更具體地說，一個int，對n， 和指針底部。 兩個那些碰巧是32位，在 至少在電腦上像這樣CS50 電器，所以他們 得出同樣的大小。 那麼，什麼是使用指針 但顯然？ 為什麼現在這個箭頭數組時 這麼漂亮，乾淨和簡單的？ 指針是什麼做的 我們在這些節點中的每個節點？ 學生：[聽不清]。 揚聲器1：沒錯。 它告訴你在哪裡 下一個是。 所以我使用的比喻 使用一個線程來排序 線程這些節點連接在一起。 這正是我們正在做的 指針，因為每個這些 內存塊可能會或可能不會 連續回背靠背 內側RAM因為每次 調用malloc說，給我足夠的 字節一個新的節點，它可能 在這裡，或者它可能是在這裡。 這可能是在這裡。 這可能是在這裡。 你只是不知道。 但是，使用指針的地址 這些節點，你可以拼接 一起在視覺上看起來的方式 即使這些東西都像一個列表 傳遍你的一個或 你的兩個或4 GB的RAM 自己的電腦裡面。 所以下行，那麼， 鍊錶是什麼？ 什麼是我們的價格 顯然支付？ 學生：[聽不清]。 揚聲器1：更多的空間，對不對？ 在這種情況下，我們已經增加了一倍 空間，因為我們已經走了 從32位的每個節點，每個 INT，所以現在64位的，因為我們有 保持周圍的指針。 你得到更多的效率，如果你的結構 是大於這個簡單的事情。 如果你確實有一個學生裡面 這是一對夫婦的字符串 名稱和房子，也許是一個ID號， 也許其他一些領域完全。 所以，如果你有一個足夠大的結構， 那麼也許成本的指針 沒有什麼大不了的。 這是一個位在一個角落的情況下 我們存儲這樣一個簡單的原始 內的鏈接的列表。 但問題是相同的。 你肯定花更多 內存，但你得到 的靈活性。 因為現在如果我想添加一個元素 在此列表的開頭， 我必須分配一個新的節點。 我有只更新那些 不知何故只是移動箭頭 周圍一些指針。 如果我要插入到的東西 中間的列表，我不必 拋開眾人推像我們一樣 週過去與我們的志願者 表示一個數組。 我可以只分配一個新的節點， 然後就點中的箭頭 不同的方向，因為它不 必須保持以實際的 內存一個真正像我畫的線 這裡的屏幕上。 最後，如果你想插入 在列表末尾的東西，這是 更容易。 這是任意符號， 但34的指針，以此來猜測。 其指針的價值是什麼 可能拉有點像一個老 有學校天線？ 學生：[聽不清]。 揚聲器1：這可能是空的。 事實上，這是一個作者的 表示空。 它是空的，因為你絕對 需要知道在哪裡結束的聯 名單，免得你保持以下 後，並按照這些箭頭 一些垃圾值。 因此，空表示沒有任何 更多的節點號為34的右側， 在這種情況下。 因此，我們提出，我們可以實現 這個節點的代碼。 我們已經看到這種 之前的語法。 用typedef定義一個新類型 我們，為我們提供了這樣的代名詞 對於char *字符串。 在這種情況下，它給我們 速記符號，使結構節點 而是可以被寫成 節點，它是乾淨了很多。 這是少了很多冗長。 節點內顯然是一個int 稱為n和結構節點* 這意味著正是我們想要的 箭頭的意思是，到另一個指針 完全相同的數據類型的節點。 我建議，我們可以實現一個 搜索這樣的功能，這在 乍一看似乎 有點複雜。 但是，讓我們來看看它在上下文中。 讓我去到這裡的家電。 讓我打開一個名為 列表零點H。 只包含的定義，我們 只是剛才也看到了這些數據 類型稱為一個節點。 因此，我們已經把到一個點h文件。 而順便說一句，儘管這 程序，你將要看到的是 不是所有的，複雜的，它的的確確 當編寫一個程序來公約 數據類型一樣，把東西拉 有時，在裡面你的常量 頭文件不一定 你的C文件，當然，當你的 方案變得越來越大，從而使 你知道到哪裡尋找既為 在某些情況下，文檔或 基本這個樣子， 某種類型的定義。 如果我現在打開列表零點 C，注意的幾件事情。 它包括了幾個頭文件，最 我們之前見過。 它包括其自己的頭文件。 順便說一句，這就是為什麼雙 報價。在這裡，相對於角度 括號就行了， 我已經強調了那裡？ 學生：[聽不清]。 揚聲器1：是啊，所以它是一個本地文件。 所以，如果你自己在這裡的本地文件 第15行，例如，您可以使用 雙引號，而不是 的尖括號。 現在，這是一種有趣的。 注意，我已經宣布為全球 這個程序的第18行的變量 被稱為第一想法是這是 將是一個指針指向第一個 在我的鍊錶節點，並且我 初始化為null，因為我 沒有分配任何實際 節點只是還沒有。 因此，這代表1973年，我們 剛才也看到了圖片作為 該指針遠 左手側。 所以現在，該指針 不會有一個箭頭。 相反，它僅僅是空的。 但它代表的會是怎樣的 第一個實際的地址 在此列表中的節點。 所以，我已經實現了它是一個全球 因為，你會看到，這一切 計劃並落實在生活中是 一個鍊錶為我。 現在我已經得到了一些原型。 我決定實現的功能，如 缺失，插入，搜索和 穿越 - 最後只是徒步穿越 列表，打印出它的元素。 而現在，這裡是我的主程序。 並且我們不會花太多時間 這些，因為這是那種，希望 現在的舊帽子。 我要做到以下幾點： 而用戶合作。 所以，我要打印 出此菜單。 我格式化它作為 乾淨，盡我所能。 如果用戶在一個類型，即表示 他們要刪除的東西。 如果用戶有兩種類型，即表示 他們要插入的東西。 等等。 我要提示 然後命令。 然後我要使用調用getInt。 所以這是一個非常簡單的menuing 界面，您只需要輸入 一些映射到一個 這些命令。 現在我有一個漂亮乾淨的開關 語句要切換 無論用戶輸入。 而且，如果他們輸入了一個，我會 調用delete和突破。 鍵入兩個我 調用插入和突破。 現在請注意，我已經把每 這些在同一行上。 這是一種風格上的決定。 通常情況下，我們已經看到的東西 像這樣。 但我剛剛決定，坦率地說，我的程序 看上去更具可讀性，因為 它只有四個案件 像這樣只列出。 完全合法使用樣式。 我要做到這一點，只要 用戶沒有輸入零，這是我 決定將意味著他們想戒菸。 所以，現在發現我什麼 要在這裡做。 我要去顯然釋放的清單。 但在短短的時刻。 首先，讓我們來運行這個程序。 因此，讓我一個更大的終端 窗口，點斜線列表0。 我要繼續前進並插入 50這樣的數字，現在打字兩 你會看到列表中現在是50。 我的文字只是滾動了一下。 所以，現在看到列表中包含 數字50。 讓我們做另一個採取兩個插入。 讓我們像一個輸入的數量。 列表現在，接著為50。 所以這僅僅是一個文字表述 列表。 我們插入一個像 數字42，這是有希望的 要結束了，因為在中間 特別是各種程序 它插入他們的元素。 因此，我們有它。 超級簡單的程序，可以 絕對使用一個數組，但我 碰巧使用一個鍊錶 就這樣我就可以動態地 增長和收縮。 因此，讓我們來看看搜索，如果我 運行命令三，我想搜索 ，也就是說，43號。 顯然並沒有什麼發現， 因為我回來沒有反應。 因此，讓我們再次做到這一點。 搜索。 50，或者更確切地說，搜索的搜索 42，有一個很好的 有點微妙的含義。 而且我發現有生命的意義。 42，如果你不知道 參考谷歌。 好的。 那麼是什麼為我做這個程序？ 它只是讓我插入從而 到目前為止，搜索元素。 讓我們快進，那麼， 我們瞟了一眼那個函數 週一傳情。 所以，我要求這個功能，搜索 第一列表中的一個元素 一，提示用戶，然後調用 調用getInt得到一個實際的int 要搜索。 然後注意到這一點。 我要創建一個臨時變量 在第188行稱為指針 - PTR - 可以把它叫做什麼。 這是一個節點的指針 因為我說有節點*。 我初始化它等於 首先，讓我實際上是我的 手指，可以這麼說，就非常 列表中的第一個元素。 所以，如果我的右手是PTR我 指向同一件事，第一 是否對準。 現在，我們回到代碼中， 接下來會發生什麼 - 迭代時，這是一個共同的範式 像結構 鍊錶。 我要做到以下幾點，同時 指針不等於空，因此， 我的手指指著一些空 值，如果指針箭頭n等於N。 我們首先會注意到，n是什麼 用戶輸入每GetInts這裡打電話。 和指針箭頭N意味著什麼呢？ 好吧，如果我們再回到這裡的圖片， 如果我有一個手指指著 九，即第一個節點 箭頭基本上意味著去那 節點，並搶在位置n的值， 在這種情況下，數據字段稱為N。 順便說一句 - 我們看到一對夫婦 星期前，當有人問 - 這個語法是新的，但它不 給我們的權力，我們 沒有已經有了。 這句話是什麼相當於使用 點符號和明星夫婦 星期前，當我們剝開 這一層有點過早？ 學生：[聽不清]。 揚聲器1：沒錯，這是明星， 那麼它是星點N， 括號在這裡，它看起來， 坦率地說，我想了很多 更神秘的閱讀。 但星級指針，一如既往 手段去那裡。 而一旦你在那裡，什麼樣的數據 現場你要訪問嗎？ 那麼你用點符號訪問 一個結構的數據字段，我 特別希望N。 坦率地說，我認為這 只是很難閱讀。 這是很難記得在哪裡 做括號走， 明星和一切。 因此，世界上採取了一些句法 糖，可以這麼說。 只是一個性感的說法， 這是等價的，並且 或許更直觀。 如果指針確實是一個指針， 箭頭符號手段去那裡找 在這種情況下，該領域稱為N。 所以，如果我找到它，發現我做什麼。 我只是打印出來，我發現我％， 堵在這個int值。 我叫睡一秒鐘只是一種 暫停在屏幕上的東西 給用戶一個第二吸收 剛剛發生了什麼。 然後我就打破。 否則，我該怎麼辦？ 我更新指針等於 指針旁邊的箭頭。 所以，僅僅是明確的，這意味著去 在那裡，我的老學校的符號。 因此，這只是意味著去任何 你指出，這在很 第一種情況是，我指著 結構九。 所以，我去那裡。 然後點符號表示， 在未來獲得價值。 但該值，即使它的繪製 作為窄，僅僅是一個數字。 這是一個數字地址。 所以這一行代碼，無論 這樣寫，更神秘 的方式，還是這個樣子，稍微 直觀的方式，只是意味著移動我的手 從第一個節點到下一個， 然後下一個，然後 下一個，等等。 因此，我們不會糾纏於其他 插入和刪除的實現 和遍歷，前兩個 這是相當複雜的。 而且，我認為這是很容易得到 做口頭丟失。 但我們可以在這裡做什麼 嘗試，以確定如何 最好做視覺。 因為我會提出，如果我們 要插入元素 現有的名單，其中 有五個要素 - 9，17，22，26，33 - 如果我要實現這 代碼，我需要考慮如何去 這樣做。 我建議採取小步 據此，在這種情況下，我的意思是什麼 可能出現的情況，我們 可能遇到的一般？ 當執行插入一個鏈接 名單，這恰好是一個 具體例的大小為5。 好吧，如果你要插入一個數字， 喜歡說的頭號 保持排序順序，其中 顯然做一個需要數 走在這個具體的例子嗎？ 開始時一樣。 但有趣的是 如果你要插入到這個 列表中，需要什麼特殊的指針 顯然要更新？ 第一。 所以，我認為，這是第一種情況 我們可能要考慮， 方案涉及於 在列表的開頭。 讓我們為這事也許容易，甚至 更簡單的情況下，相對來說。 假設我要插入 35號排序。 這顯然屬於那邊。 那麼，什麼指針，顯然是要 在這種情況下必須進行更新？ 34的指針變得不空 但該結構的地址 含有數字35。 因此，案例二。 所以，我已經是量化排序 在這裡我必須做多少工作。 最後，明顯的中間的情況下是 的確，如果我在中間，要 插入像說23，雲 在23和26之間，但 現在事情變得有點更 因為涉及什麼 指針需要改變嗎？ 因此，22顯然需要改變 因為他不能點到26了。 他需要，以指向新節點 我將不得不通過調用分配 malloc或一些等價。 但是，我也需要新的節點，23 在這種情況下，有它的指針 指向誰？ 26。 而且也將是一個 這裡的操作順序。 因為如果我這樣做愚蠢的是，我和 實例的開始處開始 列表中，我的目標是要插入23。 檢查，它屬於 在這裡，近九？ 號 它屬於這裡，未來17？ 號 是否屬於這裡旁邊22？ 是。 現在，如果我在這裡很愚蠢的，而不是 通過思考，我可能 分配我的新節點上為23。 我可能會更新指針 節點稱為22，指著 在新的節點。 然後我有什麼更新 新節點的指針？ 學生：[聽不清]。 揚聲器1：沒錯。 指著26。 但是，該死，如果我沒有已經更新 22的指針指向這個傢伙， 現在我有孤兒，其餘 列表，可以這麼說。 所以，這裡的操作順序 會是重要的。 要做到這一點，我能偷， 說，六個月志願者。 讓我們來看看，如果我們不能做到這一點 視覺上，而不是代碼明智。 我們有一些可愛的壓力 今天為你的球。 OK，約一，兩個，在 回 - 到底有沒有。 三，四，雙方你 傢伙到底。 及五，六。 當然。 五和六。 好吧，我們還會回來 你們下一次。 好吧，我們就到了。 所有的權利，因為你先在這裡 你想成為一個笨拙 在谷歌的玻璃在這裡？ 好，那麼，OK，玻璃， 錄製視頻。 OK，你去好。 所有的權利，所以如果你們可以過來 在這裡，我已經提前做好準備 一些數字。 好吧，我們在這裡。 而你為什麼不走一點 進一步的方式。 ，讓我們看看，你叫什麼名字， 谷歌玻璃？ 學生：本。 揚聲器1：本？ OK，奔，你將是第一，從字面上。 因此，我們會向您發送 結束階段。 所有的權利，和你的名字嗎？ 學生：賈森。 揚聲器1：傑森，OK你 9號。 所以，如果你想遵循本辦法。 學生：吉爾。 揚聲器1：吉爾，你要去 17，如果我這樣做 智能，我將不得不 在其另一端開始。 你走那條路。 22。 你是誰？ 學生：瑪麗。 揚聲器1：瑪麗，你會是22。 你的名字是什麼？ 學生：克里斯。 揚聲器1：克里斯，你會是26。 然後最後。 學生：戴安娜。 揚聲器1：戴安娜，你會是34。 所以你在這裡。 好吧，如此完美排序 已經訂購。 ，讓我們繼續前進，為此 這樣我們就可以真的 - 奔你只是尋找一​​種 到無處存在。 OK，讓我們繼續前進，並描繪這個 使用武器，就像我，究竟 這是怎麼回事。 因此，繼續前進，給自己一個 步行或兩個自己之間。 繼續前進，用一隻手點 你應該指向誰 在此基礎上。 如果你只是指向空 直下到地板上。 OK，這樣很好。 所以現在我們有一個鍊錶，讓我 建議，我會發揮的作用 PTR，所以我不會打擾 攜帶這種左右。 然後 - 有人愚蠢的慣例 - 你可以調用任何你想要的 - 前身指針，潑尼松指針 - 它只是我們給的綽號 我們的示例代碼，我的左手。 另一方面，要保持 誰是誰在跟踪 下面的場景。 因此，假設，第一，我要拔掉 ，插入第一個例子，說 20，到列表中。 所以我需要有人來 體現我們20號。 所以我需要有人對malloc 從觀眾。 上來吧。 你叫什麼名字？ 學生：布萊恩。 揚聲器1：布萊恩，所有的權利，所以你 須含20的節點。 好吧，我們在這裡。 很顯然， 不屬於布賴恩？ 因此，在中間 - 實際上， 等待一分鐘。 我們這樣做是為了 我們正在做這個了很多困難 比它需要的是在第一次。 OK，我們要免費布賴恩 和realloc的布賴恩五個。 好了，現在我們要插入 布賴恩五個。 這樣一來就在這裡 本只是一瞬間。 你大概可以告訴 這個故事是怎麼回事。 但是，讓我們仔細想想 操作順序。 和它的正是這種視覺 要排隊 與示例代碼。 所以，我在這裡已經PTR最初指向 不奔，本身的，但在任何 重視他包含在這種情況下 - 再次你叫什麼名字？ 學生：賈森。 揚聲器1：傑森，所以我和Ben 指著傑森在這一刻。 所以現在我必須確定， 布賴恩屬於哪裡？ 所以唯一的事情，我有機會到 現在是他的n個數據項。 所以我要來檢查， 布賴恩小於賈森？ 答案是真實​​的。 那麼現在需要什麼發生， 以正確的順序？ 我需要更新多少指針 總在這個故事呢？ 在哪裡，我的手仍指向 傑森，和你的手 - 如果你想 把你的手，有點像，我 不知道，是一個問號。 好，好。 好吧，讓你擁有 幾個候選人。 奔或I或布賴恩或傑森 或其他人，這 指針需要改變嗎？ 總共有多少人？ OK，所以兩個。 我的指針並不真的無所謂了 因為我只是暫時的。 因此，它是這兩個傢伙，據推測， Ben和布賴恩。 所以我建議大家更新 奔，因為他是第一。 這個列表的第一個元素 現在將是布萊恩。 因此，本布賴恩點。 OK，現在該怎麼辦呢？ 誰被指出在誰？ 學生：[聽不清]。 揚聲器1：確定Brian擁有 以指向賈森。 但我已經失去了該指針的軌道？ 我知道Jason是嗎？ 學生：[聽不清]。 揚聲器1：我做的，因為我 暫時指針。 而據推測，我並沒有改變 指向新的節點。 所以，我們可以簡單地布賴恩點 我指著誰。 我們就大功告成了。 所以，在插入 開始的名單。 有兩個關鍵步驟。 一，我們必須更新奔，然後 我們也有更新布賴恩。 然後我沒有打擾 其餘的疲憊 名單，因為我們已經找到了自己的 位置，因為他屬於 左側的第一個元素。 所有的權利，所以非常簡單。 事實上，感覺就像我們幾乎 這太複雜了。 現在讓我們為這事結束 列表，看到 開始的複雜性。 因此，如果現在，我的alloc從觀眾。 任何人想打55？ 好吧，我先看到你的手。 上來吧。 嗯。 你叫什麼名字？ 學生：[聽不清]。 揚聲器1 Habata。 OK，就到了。 你會是55號。 所以，你，當然，屬於 上面的列表末尾。 因此，讓我們重播模擬與我 是PTR只是一瞬間。 所以，我首先要指向 無論奔指向。 我們都指向現在在布賴恩。 因此，圖55是不小於5。 所以，我要更新自己的 Brian的下一個指針，指向誰 現在當然賈森。 圖55是不小於9，所以 我要更新PTR。 我要更新PTR。 我要更新的PTR 我更新的PTR。 我要去 - 嗯，有什麼 你的名字嗎？ 學生：戴安娜。 揚聲器1：戴安娜是指指點點，當然， 在null與她的左手。 那麼，這實際上Habata 屬於清楚嗎？ 到左邊，在這裡。 所以，我怎麼知道在這裡把她 我想我搞砸了。 因為PTR藝術 時間在這一刻？ NULL。 因此，即使，在視覺上，我們就可以 明顯看到所有這些 這裡的人在舞台上。 我以前沒有記錄 在列表中的人。 我沒有手指指出， 在這種情況下，節點號為34。 因此，讓我們真正開始過。 所以，現在我居然需要 一個第二局部變量。 這是什麼，你會看到在 實際樣品的C代碼，在那裡，因為我去， 當我更新我的右手指向 傑森，從而留下布賴恩的背後，我 最好開始用我的左手 更新我在哪裡，讓我去 通過這個名單 - 比我預期的更笨拙 現在這裡視覺 - 我會去的 列表末尾。 這手仍是空的，這是非常 沒用的，其他的比來表示 我很清楚在列表末尾， 但現在至少我有這個 前身指向這裡，所以 現在是什麼手和指針需要什麼 要更新？ 你想誰的手 先來重新配置？ 學生：[聽不清]。 揚聲器1：OK，所以戴安娜的。 在哪裡你想點 戴安娜的左指針？ 在55中，據推測，從而使 我們已經有插入。 55指針應該在哪裡去了？ 向下，佔空。 而我的手，在這一點上，不 不要緊，因為他們只是 臨時變量。 所以，現在我們就大功告成了。 所以額外的複雜性 - 它並不難實現， 但我們需要一個輔助變量 確定之前，我將我的權利 另一方面，我更新我的左值 手潑尼松指針，所以 我有一個尾隨指針 跟踪我在哪裡。 順便說一句，如果你以為這 通過，這種感覺就像是一個 必須保持有點煩 跟踪這個左手。 將另一種解決方案 這個問題已被？ 如果你得到了重新設計數據 我們正在談論的結構 通過吧？ 如果這只是一種感覺有點 惱人的一樣，兩個指針 通過列表，誰還能 有，在一個理想的世界中，保持 我們所需要的信息？ 是嗎？ 學生：[聽不清]。 揚聲器1：沒錯。 所以實際上是一個有趣的 胚芽的想法。 而前一個指針，這個想法 指向前一個元素。 如果我只是體現 列表本身的內部？ 這將是難以想像 沒有所有的紙張 掉落到地板上。 但是，假如這些人同時使用 他們手中沒有先前 指針，和一個下一個指針，從而 執行什麼，我們會打電話給一個雙 鍊錶。 這將允許我排序退， 更容易無我有， 程序員，不得不保持 手動跟踪 - 真正的手動 - 以前我一直 在列表中。 因此，我們將無法做到這一點。 我們將保持它的簡單，因為這是 要來的價格，兩倍 多的空間的指針， 如果你想要第二個。 但是，這確實是一個共同的 數據結構被稱為一個 雙向鍊錶。 讓我們在這裡做最後的例子把 這些傢伙，他們的苦難。 所以malloc的20。 來吧從那裡的過道。 好吧，你叫什麼名字？ 學生：[聽不清]。 揚聲器1：對不起？ 學生：[聽不清]。 SPEAKER 1：Demeron的？ 確定上來吧。 您應為20。 你顯然要 屬於17和22之間。 因此，讓我吸取我的教訓。 我要開始指針 指著布賴恩。 我要我的左手 只更新布萊恩，我謹 傑森，檢查少做了20比9？ 號 20小於17？ 號 20小於22？ 是。 那麼，什麼指針或手需要改變 他們指著呢？ 因此，我們可以做的17指向20。 所以這就是罰款。 我們要指出在哪裡 你的指針現在？ 在22。 我們知道22，再次感謝 我臨時指針。 因此，我們有“確定”。 所以在這臨時存儲 我一直保留著的軌道，每個人都。 現在，你可以直觀地去到哪裡 屬於你，現在我們需要1，2，3， 4，5，6，7，8，9個壓力球， 和掌聲雷動 這些傢伙，如果我們能。 幹得漂亮。 [掌聲] 揚聲器1：所有權利。 您可能保持件 紙作為紀念。 好，那麼相信我，這是一個很大 更容易穿行 人類比它的實際代碼。 但你會發現在短短的時刻 現在，是相同的 - 哦，謝謝你。 謝謝 - 是，你會發現相同的數據 結構，鍊錶，實際上可以 可以使用作為構建塊更 複雜的數據結構。 實現過這裡的主題是 我們絕對介紹 進入實施的複雜性 在此算法中。 插入，如果我們通過它去， 刪除和搜索，是一個小的 比它更複雜 是一個數組。 但是，我們獲得了一些活力。 我們得到一個自適應的數據結構。 但同樣，我們付出的代價有一些 額外的複雜性，無論是在 執行它。 我們放棄了隨機訪問。 而且說實話，有沒有一些不錯的 乾淨的玻片，我可以給你， 這裡說的是為什麼一個鍊錶 優於數組。 離開它。 由於主題現在再次發生，甚至 更何況在未來幾週內， 不一定 一個正確的答案。 這就是為什麼我們有獨立的軸 問題集的設計。 這將是非常敏感的上下文 您是否要使用此數據 結構或那一個，會 取決於什麼對你很重要條款 的資源和複雜性。 但是，讓我提出，理想的數據 結構，聖杯，將 東西是恆定的時間， 不論多少東西 在它裡面，它不會是驚人的，如果一個 返回的數據結構答案 常量時間。 是。 這個詞是在巨大的字典。 “或”否“，這個詞是沒有的。 或任何這樣的問題。 那麼讓我們來看看，如果我們不能至少 走，一步步走向。 讓我提出了一個新的數據結構， 可用於不同的事情， 在這種情況下，所謂的哈希表。 所以我們實際上一眼 在一個數組中，在這種情況下， 有些武斷，我畫這 作為數組排序的哈希表 兩維數組 - 或者更確切地說，它這裡描繪為兩 維數組 - 但是這僅僅是 大小為26的數組，例如，如果我們 調用數組桌，桌上托架 零是在頂部的矩形。 表托架25是矩形 在底部。 我這是怎麼可能畫出一個數據 我想存儲結構中， 人的名字。 因此，舉例來說，我不會畫 整個事情上的開銷，如果我 該數組，我現在要 調用一個哈希表，這又是 零的位置。 這裡是位置 一個，等等。 我要求，我想用這個數據 結構，為了討論的方便， 存儲人的名字，Alice和Bob 查理和其他類似的名稱。 所以，現在覺得這個作為起點 ，也就是說，一個字典 有很多的話。 他們正好是名 在我們的例子。 這是太有密切關係，也許， 實施一個拼寫檢查，因為我們 可能問題設置6。 所以，如果我們有一個總規模26陣列 因此，這是第25的位置 在底部，我要求愛麗絲 字典中的第一個字 名，我想插入RAM， 到該數據結構中，其中 愛麗絲的直覺告訴你， 在這個數組名稱應該去？ 我們有26個選項。 如果我們想要把她嗎？ 我們希望她在支架為零，對不對？ 為愛麗絲，我們稱之為零。 和B，和C將有兩個。 因此，我們打算寫 愛麗絲的名字在這裡。 如果我們再插入鮑勃，他 名稱會去這裡。 查理會去這裡。 如此反复向下 這樣的數據結構。 這是一個美妙的數據結構。 為什麼呢？ 那麼什麼是運行時間 插入成這樣的一個人的名字 數據結構的權利嗎？ 鑑於實施該表， 誠然，作為一個數組。 那麼它的恆定時間。 這是一個順序。 為什麼呢？ 那麼你如何確定 愛麗絲屬於？ 你看看她的名字的信嗎？ 第一。 在那裡，你可以得到，如果它是一個字符串， 只是看著串 支架零。 因此，第0個字符的字符串。 這是很容易的。 我們已在加密 分配星期前。 然後，一旦你知道Alice的 字母是大寫的A，我們可以減去 關閉65或資本A本身， 這給了我們為零。 因此，我們現在知道，愛麗絲屬於 在零的位置。 和給定的一個指針，指向這個數據 某種結構，多久？ 它帶我找到位置 陣列中的零？ 只需一個步驟，這是恆定的時間 由於隨機接入中，我們 建議的是一個數組的一個特徵。 因此，在短期，搞清楚什麼索引 Alice的名字，這是在 這種情況下，是A，或讓剛剛解決 為零，其中B是C是 二，計算出 是恆定的時間。 我只是來看看她的第一個字母， 搞清楚其中零為 數組也是恆定的時間。 因此從技術上講這是 像現在兩個步驟。 但是，這仍然不變。 所以，我們稱之為一大O，所以我們 愛麗絲插入到這個表中 常量時間。 不過，當然，我 天真在這裡，對不對？ 如果在課堂上有亞倫？ 還是艾麗西亞？ 或任何其他的名字開始 A.我們要去哪裡放 那人，對不對？ 我的意思是，現在只有三個 老百姓餐桌上，所以也許我們 應該把亞倫的位置 零壹兩三個。 好吧，我可以在這裡把A。 然而，如果我們嘗試將大衛 這個名單，大衛去哪裡？ 現在，我們的系統開始打破 向下，向右？ 因為現在，大衛在這裡結束了 如果阿龍其實是在這裡。 所以現在有一個整體思路 乾淨的數據結構，讓我們 恆定的時間插入不再 恆定的時間，因為我有 檢查，哦，該死的，有人已經 在愛麗絲的位置。 讓我探究這些數據的其餘部分 結構，尋找一個位置把 有人喜歡亞倫的名字。 等也開始 線性時間。 此外，如果你現在想找到 亞倫在此數據結構，你 檢查和亞倫的名字是不是在這裡。 理想情況下，你只說亞倫 而不是在數據結構中。 但是，如果你開始做空間 亞倫那裡應該有一個D 或E，你最壞的情況下，有檢查 整個數據結構，在 這種情況下，移交到的東西 表的大小成線性關係。 所以所有的權利，我會解決這個問題。 這裡的問題是，我不得不 26此數組中元素。 讓我改變它。 哎呀。 讓我改變它，因此而幸福 大小26個，發現底部 指數將改變為n減1。 如果26顯然是太小了人類的 的名字，因為有成千上萬的 世界的名字，讓我們使 在100或1000或10000。 讓我們只分配更多的空間。 嗯，這並不一定減少 的概率，我們不會有兩個 人們起的名字， 所以，你要嘗試將 名位置零。 他們還在碰撞， 意味著我們仍然需要一個解決方案，把 愛麗絲亞倫和艾麗西亞和其他 名開始與A別處。 但多少的問題是什麼？ 什麼的概率 有碰撞在一個數據 這樣的結構？ 好吧，讓我 - 我們會回來的 這裡這個問題。 看我們如何可能 先解決它。 讓我拉起這個建議。 我們剛剛描述的是一種算法， 一個啟發式稱為線性 探測，即如果你試圖插入 這裡的東西在此數據 結構，該結構被稱為一個哈希表， 而且也沒有的房間裡，你 真正探測的數據結構 檢查，這是可用的？ 這是這是可用？ 這是？ 而當它終於插入 名字，你原本打算 在該位置的其他地方。 但是，在最壞的情況下，唯一的現貨 可能是最底層的數據 結構，數組的盡頭。 因此，線性探測，在最壞的情況下， 下放成線性算法 亞倫，如果他恰好是最後插入 這個數據結構中，他可能會 碰撞，該第一位置，但 然後結束壞運氣的最末尾。 因此，這是不是一個常數 一次聖杯的我們。 這種方法插入元素 一種數據結構，稱為散列 表不似乎是恆定的時間 至少不會在一般的情況下。 它可以下放成線性的東西。 那麼，如果我們解決衝突 有所不同呢？ 因此，這裡是一個更複雜 仍然接近 稱為哈希表。 哈希，順便說一句， 我的意思是指數 我前面提到的。 哈希的東西可以 想到作為一個動詞。 所以，如果你哈希愛麗絲一個名字， 哈希函數，可以這麼說， 應該返回一個數字。 在這種情況下是零，如果她是屬於 位置為零，如果她屬於 的位置，等等。 所以，我的哈希函數迄今一直 超級簡單，只看著 在別人的名字的第一個字母。 但是哈希函數需要 輸入某些數據塊， 一個整數，字符串，等等。 它吐出一個典型的數字。 而且這個數字是該數據 在數據結構中的元素屬於 這裡稱為哈希表。 所以只是憑直覺，這是一個 略有不同的上下文中。 這實際上是指一個例子 涉及的生日， 可能有多達 31月份中的天。 但是，什麼人決定 在發生碰撞時？ 上下文，而不是現在的碰撞 名，生日，而是碰撞 如果兩個人有相同的生日 10月2日，例如。 學生：[聽不清]。 揚聲器1：是啊，所以我們在這裡有 利用鍊錶。 因此，它看起來有點不同 把它比我們更早。 但是，我們似乎有一個數組 在左手側。 這是一個索引，因為沒有 特別的原因。 但它仍然是一個數組。 這是一個數組的指針。 每一元素，每個 這些圓圈或斜線 - 斜線 代表空 - 這些 指針顯然指向 什麼數據結構？ 鍊錶。 所以，現在我們有能力 硬到我們的程序代碼 表的大小。 在這種情況下，我們知道從未有 在一個月內超過31天。 所以硬編碼值，如31 在這種情況下合理。 在名稱的上下文中，硬編碼 26是不講理的人 名字才開始，例如， 涉及A到Z的字母 我們可以塞進他們都到數據 只要結構，當我們得到一個 碰撞，我們不把這裡的名字， 我們反而認為，這些細胞 不是字符串本身，而是作為 的指針，例如，愛麗絲。 然後愛麗絲可以有另一個指針 另一個名字開始 A.和鮑勃實際上是在這裡。 如果有另一個名字開始 B，他結束了在這裡。 等各元素與該 表二，如果我們設計一個 更巧妙一點 - 來吧 - 如果我們設計了這個多一點 巧妙的，現在變成了一個自適應數據 結構，那裡是沒有硬性限制 你可以插入多少元素 到它，因為如果你這樣做有 碰撞，這很好。 只要繼續下去，並將它附加到 我們所看到的有點前 被稱為一個鍊錶。 那麼讓我們來的暫停只是一瞬間。 碰撞的概率是什麼 擺在首位？ 對的，也許我過思考，也許 我在工程的這個問題， 因為你知道是什麼嗎？ 是的，我可以拿出任意 關閉我的頭頂部的例子喜歡 Allison和亞倫，但在現實中， 給定的均勻分佈 投入，是一些隨機插入 到一個數據結構，什麼是真正的 碰撞的概率？ 好吧原來，它實際上是 超高。 讓我概括 問題是這個。 因此，在一個房間裡的n CS50學生，什麼是 的概率，至少 兩名學生在房間裡 有相同的生日嗎？ 因此，有什麼。幾個洪德 - 200，300人在這裡和幾個 今天在家百餘人。 所以，如果你要問自己什麼 兩個人的概率 在這個房間裡有相同的生日， 我們可以弄清楚了這一點。 其實我要求有兩個 同一天生日的人。 舉例來說，有沒有人 今天生日嗎？ 昨天？ 明天？ 所有的權利，所以感覺像我要去 不得不做這363左右 次真正弄清楚 如果我們這樣做，有碰撞。 或者，我們可以做到這一點數學 而不是繁瑣 這樣做。 並提出以下建議。 所以，我建議，我們可以模擬 兩個人的概率 同一天生日的概率為1 減去的概率沒有一個具有 同一天生日。 所以就弄這個，這只是 花哨的編寫方式， 在房間裡的第一人，他或她 可以有任何其中一個可能的 生日的一年，假設365天 與人道歉 2月29日的生日。 因此，在這個房間裡的第一人免費 有任意數量的生日 365的可能性，所以， 我們要做的，365除以365， 這是其中之一。 旁邊的人在房間裡，如果我們的目標 是為了避免碰撞時，也只能 有他或她的生日就如何 許多不同的可能的天？ 364。 所以這個表達式中的第二項是 基本上這樣做對我們的數學 通過減去一個可能的日子。 然後第二天，第二天， 第二天下來的總數 在房間裡的人。 如果我們再考慮，又是什麼 的概率不是人人有 獨特的生日，但1減去再次 ，我們得到了什麼是一個表達式 可以很稀奇 這個樣子。 但它更有趣 看視覺。 這是一個圖表上的x軸 多少人在房間裡， 生日數。 在y軸上的概率是 碰撞時，兩個人 具有相同的生日。 而從這個曲線是外賣 只要你喜歡40 同學們，你們是在90％的概率 ，combinatorically兩個 人或以上有 同一天生日。 一旦你得到58人喜歡它的 幾乎100％的機​​會兩個 房間裡的人將不得不 同一天生日，即使有 365或366個可能的桶， 只有58人在房間裡。 只是統計學，你很可能會 得到的碰撞，在短 激勵這個討論。 即使我們得到看中這裡， 開始這些連鎖，我們還是 將有碰撞。 所以引出了一個問題，什麼是 成本做插入和刪除 進入這樣一個數據結構？ 那麼讓我提出 - 並讓我回到屏幕上對 在這裡 - 如果我們有n個元素 列表，所以如果我們試圖插入 n個元素，我們有 總共有多少桶？ 比方說，共31桶 在的情況下的生日。 什麼是最大長度為一個 這些鏈可能？ 如果再有31個可能 在一個給定月份的生日。 我們只是聚集大家 - 實際上這是一個愚蠢的例子。 讓做26代替。 因此，如果實際擁有人名列 從A到Z，從而使 我們26的可能性。 我們使用一個數據結構，如 我們剛才看到的，據此，我們有 一個數組的指針，其中每個 指向一個鍊錶地方的 第一份清單是每個人都 愛麗絲的名字。 第二個名單是每週與 命名開始， 為B，依此類推。 什麼可能各有長短 這些列表，如果我們假設一個乾淨的 從A到Z的名稱分配 在整個數據結構？ 有n個人的數據結構中 除以26，如果他們很好 攤開在整個 的數據結構。 因此，每個這些的長度 鏈為n除以26。 但在大O表示法，那是什麼？ 什麼是真的？ 所以這真的只是N，對不對？ 因為我們說，在過去， 唉你除以26。 是的，在現實中，它是速度更快。 但是，從理論上講，它不能從根本上 所有的更快。 因此，我們不似乎是所有的東西 接近本聖杯。 事實上，這僅僅是線性時間。 哎呀，在這一點上，為什麼我們不 只使用一個巨大的鍊錶？ 為什麼我們不只是用一個巨大的 數組來存儲的名稱 每個人都在房間裡嗎？ 嗯，還有東西 引人注目的一個哈希表？ 還有一些引人注目的 關於數據結構的 看起來像這樣嗎？ 此。 學生：[聽不清]。 揚聲器1：右鍵，並再次，如果它只是 一個線性時間算法，並有 線性時間的數據結構，我為什麼不 只是在一個大的存儲每個人的名字 陣列，或在一個大的鍊錶？ 停止CS這麼更難 比它需要的嗎？ 什麼是引人注目的，甚至 雖然我劃出來？ 學生：[聽不清]。 揚聲器1：插入都沒有？ 昂貴了。 因此，插入可能仍然 時間是恆定的，即使你的數據 結構看起來是這樣的，琳瑯滿目的 指針，其中每個指向 潛在的鍊錶。 你怎麼能實現恆 時間插入的名字？ 把它貼在了前面，對不對？ 如果我們犧牲一個設計目標 所說，我們希望保持 每個人的名字，例如，排序， 舞台上所有的數字排序， 假設我們有一個 未分類的鍊錶。 我們只需花費一個或兩個步驟， 像Ben和布萊恩的情況下 早些時候，插入一個元素 在列表的開頭。 因此，如果我們不關心排序的所有 開頭的名字或全部 以B開頭的名字，我們仍然可以 實現恆定的時間插入。 現在回頭Alice或Bob或任何名稱 更普遍的仍是什麼？ 大O的n除以26，在 理想情況下，每個人的均勻 分佈，其中有盡可能多的 有Z的，這可能是 不現實的。 但是，這仍然是線性的。 但在這裡，我們再回過頭來點 漸近符號 理論上確實如此。 但在現實世界中，如果我要求 我的程序可以做一些26倍 速度比你的，其程序 你要喜歡使用？ 你的還是我， 快26倍？ 實際上，人是26 倍的速度，即使在理論上 我們的算法運行在相同的 漸近運行時間。 讓我提出一個不同的 完全的解決方案。 如果這不吹你的頭腦， 我們的數據結構。 因此，這是特里 - 樣的一個愚蠢的名字。 它來自檢索，字 拼寫特里，T-R-I-E，因為 當然檢索聽起來像特里。 但是，這是歷史 的特里字。 因此，一個特里確實是某種樹， 它也是一上場就那個字。 即使你可以不太看到它 這個可視化，特里是一個 樹結構，就像一個家庭樹 在頂部和意見的一個祖先 孫子和重孫 離開底部。 但特里在每個節點是一個數組。 ，它是在一個數組 - 讓 過於簡單化了一會兒 - 這是一個 陣列，在這種情況下，大小為26，其中 每個節點是數組的大小為 26的方法，其中在第零個元素 數組代表A，最後 在每個這樣的元素 數組代表Z。 所以，我建議，那麼，這個數據 結構，稱為一個特里，可 也用於存儲字。 我們剛才也看到了，我們如何能夠存儲 的話，在這種情況下，名稱，這樣我們 前面所看到的，我們如何能夠存儲數字， 但如果我們專注於名或字符串 這裡，發現什麼有趣的。 我要求麥克斯韋的名字是 內的這樣的數據結構。 你在哪裡看到麥克斯韋？ 學生：[聽不清]。 揚聲器1：在左邊。 那麼，有什麼有趣的與此數據 而不是存儲結構 串M-à-X-W-E-L-L反斜杠零，所有的 連續，就是你，而不是做 以下。 如果這是一個類似的數據結構的線索， 的每個節點又是一個數組， ，你想，你先存儲麥克斯韋 指數和根的節點，所以 說話，最上面的節點， 右，所以在位置M， 大致可分為中間。 然後從那裡，你遵循 一個子節點的指針，可以這麼說。 所以家譜感， 你跟著它向下。 導致你到另一個節點 左邊有，這是 只是另一個數組。 然後，如果你想存儲麥克斯韋， 你找到指針，表示 A，這是此人在這裡。 然後你去到​​下一個節點。 和通知 - 這就是為什麼圖片的 有點自欺欺人 - 這個節點看起來超級微小的。 但是，這樣做的權利是Y和Z。 這只是筆者已截斷 圖片，讓你實際上 看到的東西。 否則這幅畫 將是巨大的寬。 所以，現在你的索引位置X，然後 W，然後E，那麼L，L，然後有什麼 這種好奇心？ 那麼，如果我們正在使用這種新 採取有關如何存儲中的字符串 數據結構，你仍然需要 基本上在數據核對 結構詞語到此為止。 換句話說，這些節點中的每個節點 不知何故要記住，我們 後面其實所有這些指針 並留下一點點 麵包屑的底部，在這裡對本 結構示意M-à-X-W-E-L-L 確實這個數據結構中。 因此，我們可能會做如下。 我們只是在圖片中的每一個節點 鋸有一個大小為27的數組。 它現在27，因為在p設置6個， 實際上，我們就會給你一個撇號， 所以我們可以有名稱，如奧賴利 和其他帶撇號。 但同樣的想法。 在這些元素 陣列指向一個struct 節點，所以只是一個節點。 因此，這很容易讓人想起 我們的鍊錶。 然後我有一個布爾值，我將 致電字，這是只是要 如此，如果一個詞結束 樹中的節點。 它有效地代表小 三角形，我們剛才也看到了。 因此，如果有一個字在該節點處結束 樹，那田字是真實的， 在概念上被檢查過，或 我們繪製這個三角形，是有 這裡是一個字。 所以這是一個特里。 現在的問題是，什麼 是它的運行時間？ 它是大O的n？ 是別的原因呢？ 好吧，如果你有n個名字，在此數據 結構，麥克斯韋只是其中之一 他們，什麼是運行時間 插入或找到馬克斯韋爾？ 什麼是運行時間 插入麥克斯韋？ 如果有n其他名稱 已經在表中？ 是嗎？ 學生：[聽不清]。 揚聲器1：是的，它的長度 的名字，對不對？ 所以M-A-X-W-E-L-L，所以這樣的感覺 算法是大O七。 現在，當然，該名稱 將長短不一。 也許這是一個簡短的名稱。 也許這是一個較長的名稱。 但這裡的關鍵是， 這是一個常數。 也許這不是真的不變， 不過神來，如果實事求是，在 字典裡，可能有一些限制 中的字母的數目 在某個特定國家的人的名字。 因此，我們可以假設， 值是一個常數。 我不知道它是什麼。 這也可能是大於 我們認為它是。 因為總有一些角落 一個瘋狂的長名稱的情況。 因此，讓我們叫它K表，但它仍然是一個 常數，大概，因為每一個 命名在世界上，至少在 特定的國家，該長度或 短，所以它是恆定的。 但是，當我們已經說了一句大 O的一個恆定值，那是什麼 真的等同嗎？ 這真的是同一件事 說恆定的時間。 現在，我們是一種欺騙，對吧？ 我們利用一些理論 這裡要說的是，訂單的k 真的只是為了一個， 和它的持續時間。 但它確實是。 因為這裡的關鍵洞察力是 如果我們有n個名字已經在這 數據結構，我們插入麥克斯韋 是需要我們的時間量 在所有受影響的插入麥克斯韋 有多少人 在數據結構中？ 似乎不。 如果我有一個10億多元素 特里，然後插入麥克斯韋， 他在所有受影響？ 號 而這不同於任何一天的數據 結構到目前為止，我們已經看到，其中 你的算法的運行時間是 完全獨立的多少 東西已經是或不是 在該數據結構中。 因此，與這提供了你現在是一個 機會對p六集，這將 再次涉及實施自己的 拼寫檢查器，讀入150,000 也就是說，如何最好地儲存， 不一定是顯而易見的。 雖然我渴望找到 聖杯，我不 聲稱，特里。 事實上，一個哈希表，很可能 被證明是更有效的。 但那些只是 - 這只是一個設計決策 你將不得不作出。 但在收盤讓我們50歲左右 秒採取偷看是什麼樣的 下週提前超出了我們的過渡 從這個命令行 世界上，如果C程序網絡的事情 基於語言，如PHP， JavaScript和互聯網本身， 協議，如HTTP，你 理所當然的多年 現在，類型最 一天，也許，或可見一斑。 我們將開始剝開 層是什麼是互聯網。 什麼是代碼， 今天的基礎工具。 所以，50秒這個傳情。 我給你的淨勇士。 [視頻回放] 他帶來一個消息。 有了自己的協議。 他來到世界殘忍防火牆， 漠不關心的路由器和危險遠 比死亡更糟糕。 他的速度快。 他很強壯。 他的TCPIP。 他有你的地址。 勇士淨。 [END視頻播放] 揚聲器1：這是如何在互聯網上 應下週工作。