DAVIDマラン：すべての権利。 CS50におかえりなさい。 これは8週の始まりです。 そして問題は終わった5を設定することを思い出す 挑戦の少しと。 だから、あなたのすべてを回収したと仮定して 教育フェローとCAの写真 card.rawファイルには、対象となります 今、それらの人々のすべてを見つけることにし、 1の幸運な勝者は1と一緒に家に歩いていく これらのものの、うるう運動 あなたが最終的に使用できるデバイス インスタンスのためのプロジェクト、。 これは、毎年、につながる creepinessのビット。 そして私は私がやるだろうと思っていたことは共有です あなたと一緒に持っているノートの一部 上の前後に行っ 後半のスタッフ一覧。 例えば、ただ昨晩、引用 スタッフの一人からの引用終わり、 メンバーは、 "私はちょうど学生ノックしていた 私のドアに私と一緒に写真を撮るために。 ストーカーは、私はあなたを教えてください。 "オフ開始 我々は移動した後、かなり説明的 へと、時間かそこら後、 "私が持っていた セクションの後に私を待っている学生 そして、彼は私たちの名前と写真のすべてを持っていた 紙の一部シートに。 "すべての権利。 だから組織化ではなく、 まだすべてが不気味。 その後、 "私はこの週末は、町外であった と私が帰ってきたときに、いずれかであった 私の 寝室。 "[笑い] DAVIDマラン：スタッフから次の引用 メンバーが、 "学生で私の家に来た 4でサマービルは今朝AM。 "次 スタッフは、 "私はサンに私のホテルに着いた サンフランシスコと学生が待っていた 3デジタル一眼レフカメラとのロビーで私を。 " カメラのタイプ。 "私は、スタッフのこの学期でさえないんだけど しかし、学生が私の家にこれを破った 全部を記録した朝と 。グーグルグラスを持つ "そして最後に、 "少なくとも12人は熱心だった 私は外に着いたとき、私のため待って リムジン、そして私 目が覚めた。 "すべての権利。 だから、写真の中で、あなたは可能性がある リコールは、ここでこの仲間、あなたです 住んでミロバナナ、として知っているかもしれません ローレンカルバリョ、私たちの頭の フェローを教える。 ミロ、ミロは、ここで少年に来る。 ミロ。 ミロ。 そう、彼はGoogleのガラスを身に着けている、あなたの心 私たちはあなたにこのすべてをした後に紹介しま​​す。 あなたがしたい場合ので、これはミロです その後彼と一緒に写真を撮る。 あなたが出て見えるしたい場合 そこに観客で。 OK。 それは良い映像だ。 まあ、ミロバナナ。 ああ、それをしない。 [笑い] OK。 先にあるもので、その後の単語だから、 我々は移行を始めるとなぜなら、 今週具体的には、Cから PHPのコマンドライン環境と JavaScriptとSQLとHTMLとCSSの Webベースの環境では、我々はできるでしょう すべてであなたを装備 ためのより多くの知識 潜在的な最終的なプロジェクト。 そのために、コースは持って その開催セミナーの伝統 接線のトピックにある コー​​スに。 非常にプログラミングとの関連 アプリの開発などが、 必ずしもで探検しない もちろん独自のシラバス。 1つに興味があるかもしれませんので、もし 今年のセミナーの以上、 cs50.net/seminarで登録。 年上のセミナーがあります cs50.net/seminarsで。 そして今年のこれまでの名簿上の ルビーとア​​メージングのWebアプリにある 代替手段ですレール、 PHPの言語。 計算言語学。 であるiOSの、入門 iPhoneとのために使われているプラ​​ットフォーム iPadの開発。 JavaScriptはウェブアプリのために、我々は説明します それが、このセミナーでは、あなたが行くよ 詳細へ。 モーションリープので、実際にいくつかを持っているよ リープモーションからの我々の友人の、 会社自体は、私たちに参加。 提供するために、明日、実際には、 ハンズオンセミナー、もし あなたに関心の。 Meteor.js、ための代替技術 、ブラウザでJavaScriptを使用していない しかし、サーバー上の。 非常によく似ていますNode.jsの、 その静脈だけでなく。 なめらかなAndroidのデザイン。 Androidは非常に人気の代替であること iOSとWindowsの携帯電話へ やその他のモバイルプラットフォーム。 およびWebセキュリティアクティブディフェンス。 だから実際には、あなたがご希望の場合 これに従事する、私を聞かせて これをメモしておきます。 我々は、と言うことは非常に満足している リープで私たちの友人 スタートアップで動き、 - このデバイスは、実際には来 数ヶ月前から - 優雅に30このようなデバイスを寄贈しました など、多くの学生のためのクラス、場合に あなたは、ハードウェアを借りたいのですが 学期の終わりに向かってとのためにそれを使用 実際の最終的なプロジェクト。 彼らは、多くの言語をサポートしています。 それらのどれもないようにC、それらのどれもPHP、 実現するこれらのセミナーの一つ以上の 関心の証明するかもしれない。 それらのすべてはで撮影されます あなたができないことをイベント 本人が出席する。 スケジュールは経由して発表される 私たちは部屋を固めるようにメールしてください。 そして最後に、あなたがに行けば projects.cs.50.net、これはウェブサイトです 我々は招待する毎年維持 コミュニティからの人々、教職員、 部門、スタッフ、両方 CS50への外で プロジェクトのアイデアを提案する。 学生グループに興味のあるもの。 部門に興味のあるもの。 あなたが苦労している場合、そうそこに回すか 何かの不確実性 自分で取り組むことを望む。 我々は間違いなく導入されたので、最後の時間 より複雑なデータ構造我々が思いより 過去数週間で見られる。 我々は、かなりの配列を使用していたい もし喜んとして有用 単純なデータ構造。 次に我々は、これらを導入している もちろんリストをリンクされています。 と動機の一つだったもの このデータ構造を導入？ うん？ 何それ？ 聴衆：ダイナミックサイズ。 DAVIDマラン：ダイナミックサイズ。 配列のに対しだから、あなたがする必要があります 場合は、事前にその大きさを知る あなたはそれを割り当てる。 リンクされたリストで、あなたはしないでください ことを知っている必要があります。 あなたは、より一般的に単にmalloc関数、または、することができます 追加を割り当てる ノード、いわば、あなたはいつでも より多くのデータを挿入したい。 そして、ノードは所定の意味を持ちません。 それはちょうど記述総称です 私たちがしていることをコンテナのいくつかの種類 保存するには、弊社のデータ構造での使用 この中で興味のあるいくつかの項目、その ケースは整数であることが起こる。 しかし、トレードオフが常にある。 そこで、データの動的なサイズを取得する 構造が、我々はどのような価格を支払うのですか？ リンクリストの欠点は何ですか？ うん？ 観客は：多くのメモリが必要です。 DAVIDマラン：それはより多くを必要とする メモリ、どのように正確？ 読者：[聞こえない]。 DAVIDマラン：その通り。 だから今我々は、ポインタを取っている 私たちは以前にその増設メモリ 利点ので、必要はありませんでした アレイもちろん、すなわち すべてが連続し、帰ってきた 背面にバックアップするには、どの あなたにランダムアクセスを提供します。 なぜなら単に角括弧を使用することにより 表記法、あるいはそれ以上の技術的にポインタ 算術、非常に単純に加え、 何かにアクセスすることができます 一定時間内の要素。 実際に、それはを示唆のようなものだ 我々が払っていることを別の価格 リンクリスト。 何の実行時間に起こる 検索のようなもの、私がしたい場合 いくつかの値と内部を見つける リンクリストの？ 私の実行時間はどうなるのでしょうか？ nはビッグオー。 それに替えられている場合は？ データ構造がソートいたら？ 私はビッグよりも良い行うことができます 検索するためのnのO？ いや、最悪の場合、それは可能性があるため 非常によく並べ、その数れる あなたが探していることは、大きな可能性があります。 これは、どの番号100、かもしれない すべてのことが起こるかもしれません 末尾の方法。 そして、あなたは唯一のリンクにアクセスすることができますので、 することにより、この実装ではリスト その最初のノードのように、あなたはしている まだ運のようなもののうち、。 あなたは、全体を横断する必要があります 最初から見つけるために最後まで 100のようにその大きな価値。 それともそれはかどうかを判断するために なくてもそこに。 だから私たちは、データのどのアルゴリズムで行うことはできません このように見える構造は？ ので、私たちは、バイナリ検索を行うことができません 我々が持っていたことが必要とバイナリサーチ ランダムアクセス。 私たちはただの場所から飛躍でした フォローしなくても場所 フォームでこれらのパン粉 すべてのこれらのポインタ。 さて、どのように我々はこれを実装したのですか？ まあ、我々はここで画面に行けば、もし 我々はすぐに、このデータを再実装することができます 構造 - 私の筆跡は、すべてのことではありません ここで素晴らしい、しかし我々は試してみます。 だからます。typedef struct、と私がした この事をここに呼び出すしたいですか？ ノード。 だから私は、私たちが始められるでしょう。 そして今、内部のように必要なもの その単独でのデータ構造 リンクリスト？ どのように多くの分野？ 2だから。 一つは、非常に簡単です。 nにint型。 そして、私たちは、私たちが望むnの何を呼び出すことができます 我々は、ならそれがint型でなければなりません int型のためのリンクリストを実装する。 そして今、第二に何をするか フィールドがあることがありますか？ 構造ノード*。 だから私は、構造体ノード*、そして私をすれば また、私はやりたい、これを呼び出すことができ、 しかし、ちょうど私が電話するよ明確にする 私たちが行ってきたとして、それを次の。 そして私は私の中括弧を閉じます。 そして今、最後の時間のように、 私はここで、ノードを置く。 しかし、私はこれを宣言しているかのようである ノード、なぜ私はそうされてわざわざでし ここで構造体を宣言するに冗長 ノードは、*次に、反対した 次のノードだけ*に？ うん？ 読者：[聞こえない]。 DAVIDマラン：その通り。 まさに。 Cは本当にあなたを文字通りかかるためと 唯一のノードの定義を見て ここでダウン方法、することはできません ここでそれまで参照してください。 だから我々は先制のこの種を持っている 確かにここで宣言され、 より冗長。 構造体ノードは、その手段 我々は今それをアクセスすることができます データ構造の内部。 そして、これがあるので、脇など 、今ではもう少し主観的になってき 星は技術的にここに行くことができ、 それはここに行くことができ、それができ でも、真ん中に行く。 我々のスタイルガイドでは、採択されまし​​た もちろん、パッティングの大会 右隣のデータにつ そのこの場合はタイプ、、 構造のノードになります。 しかし、教科書の多くで実現し、 オンラインリファレンス、あなたは確かかもしれない 反対側にそれを参照してください。 しかし、単に双方が実際にすることを実現する 仕事とは、単純であるべき 一貫性のある。 わかりました。 だから私たちの宣言だった 構造ノードの。 しかし、その後、我々はより多くを始め 洗練されたもの。 例えば、我々が導入を決定 ハッシュテーブルのようなもの。 だからここにサイズnのハッシュテーブルがあり、 nの左上に0からインデックス マイナス底面の1を残しました。 これは、ハッシュ可能性があり 何のためのテーブル。 しかし、我々は物事の種類を話したのか のハッシュテーブルを使用してはどうでしょうか？ 何を保存する？ 名称。 我々のような名前を行うことができ 我々は最後の時間でした。 そして実際に、あなたは何を保存することができます。 そして、我々は再びこれを見るだろう PHPとJavaScriptである。 ハッシュテーブルは、スイスの素敵なものです あなたが保存することができアーミーナイフ ほとんどあなたの中の好きな 値を持つキーを関連付けることによって、それ。 値を持つキー。 今、このような単純なケースでは、我々の キーは数字だけです。 私たちは、ハッシュを実装している 配列としてテーブル。 そしてキーは0であり、 1,2、等が挙げられる。 そして我々は、人間として、最後の決め あなたは私たちがしている場合はどうでしょう、知っている週 ストア名に行く、みましょうだけ 任意ですが、かなり合理的に、 仮定アリス、名前、 ただ0に索引付けされます。 とボブ、B名前は、索引付けされます 1に、等が挙げられる。 だから我々は、入力間のマッピングを持っていた これは文字列で、ハッシュ 数字である場所。 だから方法は、一般として知られている ハッシュ関数、あなたは本当にすることができます コー​​ドでそれを実装する。 私は、ハッシュ関数を実装したい場合 まさに我々ないこと ただ私は、前回からかもしれない説明 として、取る関数を宣言する 例えば入力 - とみましょうこの上でこれを行う こっち画面。 私はハッシュを実装したい場合 この関数は、私が言うかもしれない このような何か。 これは、int型を返すことが起こっている。 これは、ハッシュと呼ばれるようになるだろう、そしてそれはだ 引数として受け入れるつもり 文字列、または私達は、今ではより適切なことができます と、char *を言う、我々はそれの電話するよ。 そして、このすべての機能が、関係しています 最終的には、int型を返すことです。 さて、どのようにそれがないことかもしれない それほど明確ではない。 私はせずにこれを実装するつもりです 今エラーチェックの形。 私はただやみくもに戻る、と言うつもりです Sブラケット0、マイナスであるものは何でも 首都セミコロン、のは言わせて。 完全に壊れた。 それは完璧ではないので、 1、sがnullの場合は何？ 悪いことが起こるとしている。 二、これが何の最初の文字であれば 名前は、大文字ではないでしょうか？ 有効にするつもりはないことを 外にうまくどちら。 それは小文字かもしれない またはまったく手紙。 ここに改善のためのだから全く部屋、 しかし、これは基本的な考え方です。 我々として口頭先週記述したもの にアリスをマッピングするだけのプロセス 1から0へとボブを表すことができる。 確かにも​​っとformulaically Cなど ここで機能します。 として文字列を受け取り、ハッシュ再び呼び出さ 入力してから、何とか何かを 出力を生成するために、その入力である。 はなく、私たちのブラックボックスの説明とは異なり、 我々は長い間やっていること。 私はこれがあるかもしれないのか分からない ボンネットの下に取り組んでいます。 問題セット6、課題のいずれかの 何を決定するためのものです あなたのハッシュ関数は次のようになります？ その黒の内側になるだろう何が ボックス、およびおそらく、それができるでしょう これより少し面白い、と エラーが間違いやすい この特定よりチェック 実装。 しかし、問題は右、発生する可能性があります？ 我々は、このようなデータ構造を持っている場合 問題の一つ何1、 あなたは挿入のように時間をかけてに実行することができます に、より多くの名前 ハッシュテーブル？ あなたは正しい、衝突を得る？ あなたはアリスとアロンを、何を持っている場合 名前が起こった2人 で開始するには？ それはどこに、質問を頼む 第二のような名前を入れて？ さて、あなたは単純にそれを置くかもしれない ボブが属する場所が、その後ボブです あなたがしようとする一種のねじ込み 次の彼の名前を挿入し、 彼の余地はありません。 だから、チャーリーはボブを置くかもしれない そして、あなたは非常に迅速にこれを想像することができます 混乱のビットに委譲。 最後の直線何か、あなた ただ全体を検索する必要が アリスやボブを探して またはアーロンまたはチャーリー。 だからではなく、我々だけで提案し、代わりに 直線的にオープンスペースのためのプロービング そして我々は、そこに名前をplopping 手の込んだ手法を提案した。 とまだ実装ハッシュテーブル インデックスの配列が、データ型の これらの指標は現在のポインタだった。 何へのポインタ？ リンクされたリストへのポインタ。 リンクリストであることがあるためリコール 本当にただノードへのポインタ、および ノードは、次のフィールドを有し、そのノード 次のフィールドを有し、などが挙げられる。 だから、今のこの配列を考えることができます ハッシュテーブルとしての左側 リンクリストにつながる。 あなたが得る場合の利点は、 アリスとアーロンの衝突、 あなたは、で何を行うのですか 第二のような人ですか？ あなただけに彼を添付したり、彼女の 終わり、あるいは始まり リンクされたリストの。 そして実際に、スルーだけ麺みましょう そのただ秒間。 どこが最も理にかなって？ 私はアリスを挿入して、彼女は見上げ終了した場合 最初の場所は、その後、私がしよう アーロンの名前を挿入し、そこ 明らかに衝突、私は置くべき 彼を初めに リンクリストの？ その最初の場所でそれだ、 または末尾に？ 読者：[聞こえない]。 DAVIDマラン：OK。 私が始めて聞いた。 なぜ初めに？ 読者：[聞こえない]。 DAVIDマラン：OK。 それは素晴らしいですので、アルファベット順です。 それは良い財産だ。 それは潜在的に私にいくつかの時間を節約できます。 それは私がバイナリ検索をさせますが、私はありません 少なくとも、抜け出すことができるかもしれない 私が気付いた場合、ループの、まあ、私は方法だ 過去あったアーロンはこれになるでしょう リンクされたリストを並べ替え。 私が探して私の時間を無駄にする必要はありません 最後にすべての方法。 だから合理的だ。 なぜ他には、挿入したいかもしれません で衝突名前 リストの先頭に？ 何それ？ 読者：[聞こえない]。 DAVIDマラン：それは長い時間がかかることがあり リストの最後に到達する。 そして実際に、どんどん長く。 あなたがそれを挿入して複数の名前 、長いことで始まる チェーンが取得する予定です。 リンクされているより長いこと リストが取得する予定です。 だからあなたは本当にしている あなたの時間を無駄に。 たぶん、あなたは維持する方がいいでしょう 定数挿入時間、1のビッグO、 常にで衝突名前を置くことによって、 リンクリストの先頭に、 と同じくらい気にしない ソートについて。 最良の答えは何ですか？ それは不明だ。 それは一種のは何に依存 ディストリビューションは、パターンとは何か、です。 あなたが挿入されている名前の。 それは必ずしもありません 明白な答え。 しかし、ここには、再び、です デザインの機会。 だから我々は、その後、この事を見ている 本当に他の大きな機会です Pセット6。 そして、あなたが既に持っていなければ、実現する これらの両方にZamylaダイブ、ハッシュ テーブルとより詳細にしよう。 とビデオチュートリアルです Pセット仕様に包埋した。 これはトライだった - T-R-I-E。とについての興味深いものだっ これは、実行中の時間だった マクスウェルのように、名前を検索する 最後の時間は、何のビッグOでしたか？ 何それ？ 読者：文字数。 DAVIDマラン：文字の数。 私は二つのことを聞いた。 手紙や時定数の数。 それでは、最初に手放す。 文字数。 さて、このデータ構造は、リコールは、ある 木、家系、それぞれが好き そのノードが配列で構成されています。 そして、それらの配列はへのポインタである 他のこのようなノード、または他の ツリー内の配列。 我々はその後、決定したいのであれば マクスウェルがここにあるかどうか、私が行くかもしれない の最上部にある最初の配列に 木、いわゆる根の上部 その後トライ、およびmポインタをたどる、 次に、ポインタ、xは、 W、E、L、L。 そして私は、いくつかの特殊記号が表示されたとき 三角形としてここに表記。 コー​​ドでは、私たちはあなたのことを提案わかります ただはい言って、ブールとして実装 あるいはまったく、言葉はここに停止します。 まあ、かつて我々は、M-A-X-W-E-L-Lに行ってきた、 多分、7のように感じている 8我々はそれ過去1、8に行く場合 マクスウェルを見つけるための手順。 またはみましょうそれK.呼び出すしかし最後のリコール 時間は、私ががあればと主張 で現実的に最大長 40いくつかの奇数の文字、のような言葉、 最大の長さを意味します 定数値。 だから本当に、はい、それは技術的には大きなOだ しかし、8または7、またはKの本当に大きなOの 何上の有限キャップがあれば Kは可能性があり、それは一定です。 そしてそれはで1のビッグOです 一日の終わり。 ではない現実の世界である。 あなたが実際に見て起動しないとき プログラムの実行など、あなたの時計。 それは絶対に少しになるだろう 真に定数よりも遅く 一歩との時間。 それは、7または8つのステップになるだろう それでも、それは、はるかに多くの方が良いでしょう そのn個のビッグOのようなアルゴリズムより に何があるかのサイズに依存 データ構造。 ここで逆さまに気付く我々は挿入することができますです これに万人以上の名前 データ構造が、どのように多くの手順 それを見つけるために私たちを取るために起こっている その場合のマクスウェル？ なし。 彼が影響を受けないです。 そして今日まで、私たちは見てきたとは思わない データ構造の一例又は 完全にあったアルゴリズム 外部の影響を受けない そのような行動。 しかし、これは驚くべきことはできません。 これが唯一の解決策になることができません P-setの とそうではありません。 これは、データとは限りません あなたに引き寄せられるべき構造、 トレードオフは、ハッシュテーブルのようなので。 ここで支払う価格は何ですか？ メモリ。 私が意味する、これはひどいです メモリの量。 そして、あなたは非常にここでそれを見ることができないので、 この絵の作者 明らかに、配列のすべてを切り捨て 私たちはのをたくさん見ていない BのとCとQのとYの とZのこれらの配列である。 しかし、彼らはそこにいる。 これらの各ノードは、全体の配列です いくつかの26バイト以上、それぞれの これは、文字を表します。 我々がサポートできるように、我々の場合は27、 問題セットでアポストロフィ。 、本当にこのデータ構造は、そう 本当に緻密で広い。 そして、それだけでは減速終わるかもしれない 物事ダウン、または少なくともあなたの原価計算 より多くのスペース。 しかし、再び、私たちは描くことができます ここで比較。 しばらく前を思い出して、我々は多くを達成 選別でよりエキサイティングな実行時間 私たちは、マージソートが、価格を使用するとき 我々は、マージのためにn個を達成nをログするために支払わ ソートは、我々が過ごすことが必要 もっと何リソース？ より多くのスペース。 私たちは、続発する配列を必要としてい 同じように、人にコピー 私たちは、ステージ上でここにしました。 だからもう一度、明確な勝者、 しかしちょうど主観的設計 決定がなされる。 わかりました。 だから、どのようにこれはどうでしょうか？ 誰もがそのD-ホールを認識？ OK。 だから私たちの3人はやる。 マザーハウス。 だから、これはマザーのダイニングです。 私はすべてのダイニングホールが持っている賭ける このようなトレーのスタック。 そして、これは実際に代表である 私たちが何かしたの 明らかにすでに見。 我々は文字通りスタックそれを呼んだ。 あなたの観点とスタック、 コンピュータのメモリは、データがどこに行くかです。 関数が呼び出されている。 例えば、物事の何種類が行く に関して、スタック上 我々は説明したメモリレイアウト 過去数週間で？ 何それ？ 読者：関数の呼び出し。 DAVIDマラン：ごめんなさい。 読者：関数の呼び出し。 DAVIDマラン：関数の呼び出しが、 具体的には、それぞれの内部には何ですか これらのフレーム？ 物事の何種類？ うん。 ローカル変数だから。 いつでも我々は、いくつかのローカルストレージを必要としてい 引数のような、またはint型I、またはint型 一時、または任意のローカル 変数は、我々はしてきている スタックにそれを置く。 そして、我々はそれを呼び出すためのスタック そのレイヤーのアイデアの。 現実と一致するだけの種類まで、 そのコンセプト。 しかし、それはスタックにもできることが判明した データ構造として見られ、 配列の代わりに、代替 リンクされたリストに追加します。 概念的にはもっと面白い まだできること それらのいずれかを使用して実装 物事は、それは別の種類だ データ構造は、実際には、支援 2つだけの操作。 しかし、あなたは手の込んだ上で追加することができます これら以外の機能。 しかし、これらは基本です - pushとpop。 とスタックとの考えは、私であればということです アネンバーグの有無にかかわらず、ここにある 、隣からトレイを知る その上に9番を持つ。 だからint型。 そして、私はデータの上にこれをプッシュする 現在は空である構造。 これをスタックの底を考えてみましょう。 私は上にこの9番を押します 積み重ね、今ではすぐそこです。 しかし、スタックに関する興味深い 私は今プッシュする場合ということです 他の値、17のように、と私はプッシュ このスタックには、私はするつもりです 唯一の直感的なものは、私はちょうど行くよ 右のそれをどこに置くかを私たち人間 上部に、それを置くように傾斜される。 しかし、今は面白いものだ 、どのように私は9で入手できますか？ あなたが知っている、私はいくつかの努力なしにしないでください。 それでは、約興​​味深い スタックは、その仕様です それは、LIFOのデータ構造です。 記述の愚かな方法 後入れ先出し。 だから、最後の番号で この時点で17だった。 だから私は何かをオフにポップアップ表示したい場合 スタックは、わずか17とすることができる。 だから必須の順序があり ここでの操作は、最後の項目 には、最初のうち一つでなければならない。 したがって頭字語、LIFO。 では、なぜこれが役に立つかもしれません？ あなたが思いの彼らのコンテキストは このようなデータ構造をしたいですか？ まあ、それは確かに役立っている コンピュータの内部。 だから、オペレーティングシステムは明らかにこれを使用 スタックのデータ構造の一種。 また、同じ考えを見ることができます Webページに来るとき。 だから、今週と来週以降、 あなたがウェブを実装を開始として HTMLと呼ばれる言語のページ、次のことができます 実際にデータ構造を使うように このページかどうかを判断する 正しくフォーマットされています。 我々は、表示されますので、すべてのWebページがフォロー 階層の並べ替え、インデント それは、一日の終わりには、となる ボンネットの下にツリー構造。 少しだけでその上で非常に多くの。 しかし、今のところ、のはのために提案してみましょう どのように我々は取り掛かることができた瞬間、 スタックは何ですか？表す 我々が実装している私が提案してみましょう このようなコードを使用してスタック。 だからスタックは、それの内側を持っているために起こっている 二つのことは、配列と呼ばれるトレイ、 ただデモと一致しています。 そして、その配列内の各項目 int型になるだろう。 そして容量はおそらく何ですか？ 私は書かれていませんでしたので、 ここに完全な定義。 それはおそらく最高だ 配列のサイズ。 そしてそれはおそらくシャープとして宣言された いくつかのファイルの先頭に定義 によって暗示として一定の種類 単なる大文字。 だからどこかで容量が定義されています 可能な最大サイズとして。 一方、内部のデータ構造の スタックとして知られているそこに意志 ただ知ら整数でなければ 単にサイズなど。 私は今、これを表現するためにあったのであれば 画像で、のは、そのこのことを仮定してみよう 全体のブラックボックスは私のスタックを表します。 その中は、2つの変数である。 だから私は描くつもりです サイズとして最初のもの。 そして、私は行くよ一秒 配列として描画する。 しかし、単に、物事が整然と維持する 通常、私のような配列を引く これが、それは一種の素敵なの 我々は現実と一致している場合、または メンタルモデルと一致している。 だから私は、代わりに配列を描画してみましょう 垂直に、それはただ、再び、 芸術家の演出。 本当に何がそれは問題ではありません ボンネットの下にある。 そして我々は、デフォルトでは、ことを言うよ 容量は、次の3つになるだろう。 だから、これは位置0、これになります 場所1、これになります 位置2になります。 私はストレスボールで買収した場合、だろう 誰かが出てくると実行したい ちょっとここでボード？ OK、最初にあなたの手を見た。 までさあ。 わかりました。 だから、私はそれがスティーブンであると考えています。 までさあ。 わかりました。 しかし、今我々は初期に巻き戻したとし 世界の状態はどこ 単にスタックを宣言し、それがだた 容量は3であることになるだろう。 しかし、サイズがまだ決定されていない。 トレイは、まだ決定されていない。 最初の質問のカップルだから。 することができますので、私はあなたにマイクを与えてみましょう これでより積極的に参加する。 だからサイズの内部は、この瞬間に何ですか 時間内にすべての私が行っている場合です。 とスタックを宣言 1行のコード？ STEVEN：あまりない。 DAVIDマラン：OK、あまりない。 我々は、内部の大きさの何を知っていますか 我々は内部の何を知っています この配列のここに？ STEVEN：ちょうどランダムコード、右？ ただ - DAVIDマラン：ええ、私はするつもりです そのコードを呼び出すが、ランダム - STEVEN：物事。 DAVIDマラン：ランダムのようなもの STEVEN：ビット。 DAVIDマラン：ビット、右？ だからゴミ値、右？ だから、0と1の順列。 以前の用法の残骸 このメモリの。 私たちは本当に何の値かわからない ですので、我々は一般的に、それらを描く 疑問符として。 我々はおそらくいるので最初のもの ここでやりたいつもり - と私は内部でこのフィールドを与えてみましょう トレー - そこに名前の。 我々は、おそらく何を初期化する必要があります サイズは私たちがしたい場合に このスタックを使用して起動する？ STEVEN：トレイはサブ3です。 DAVIDマラン：だから、OK。 明確にするために、容量が宣言されています 他の場所で3として。 そして、それは私が使用したものだ 配列を割り当てます。 サイズを参照するために起こっているどのように多くの トレイは、スタック上に現在ある。 STEVEN：ゼロ。 DAVIDマラン：だから、それはゼロでなければなりません。 だから先に行くと、任意の指で、 サイズがゼロを描きます。 わかりました。 だから今、この内何 ここで、我々は知らない。 これらは実際には単なるゴミ値です。 だから我々は、疑問符を描くこともできますが、 今のボードを清潔に保つましょう それは問題ではありませんので、 そこに何が。 私たちは、配列を初期化する必要はありません 何に、我々はそれを知っていれば理由 スタックのサイズがゼロで、まあ、我々 には何を見てはいけません とにかく、この配列 この時点での時間である。 だから今、私がプッシュすると仮定 スタックに9番。 どのように我々は、データ構造を更新する必要があります このブラックボックスの内側？ 値は変更する必要がありますか？ STEVEN：内 - サイズは？ DAVIDマラン：OK。 サイズは何になるでしょうか？ STEVEN：サイズは1になります。 DAVIDマラン：OK。 だからサイズは1になるはず。 だから、いくつかの方法でこれを行うことができます。 あなたの今、私はあなたを与えることを許可しなさい 指が消しゴムです。 わかりました。 それから、今あなたの指がブラシです。 わかりました。 そして今、他に何が、変更する必要があり 明らかに、データ構造内？ STEVEN：我々からのつもり 9〜ボトムアップ。 DAVIDマラン：9。 OK、グッド。 だから、まだATのかは重要ではありません 場所、1つまたは2つの彼らはだから ゴミ値が、我々は気にしないはず サイズがあるのでそこを見て を告げて、その最初の要素のみ 実際には正当なものである。 だから今私は、リストの上に17を押してください。 何がこの写真はどうなりますか？ STEVEN：だからサイズが2に行く予定です​​。 DAVIDマラン：OK。 あなたは消しゴムだ - おっと。 あなたは消しゴムです。 STEVEN：消しゴム。 DAVIDマラン：あなたがブラシです。 STEVEN：ブラシ。 DAVIDマラン：OK。 そして、ほかに何か？ その後、そして、私たち - ：STEVEN DAVIDマラン：我々は17を押した。 STEVEN：私達は、一番上に17を貼る - DAVIDマラン：OK、良い。 STEVEN： - それをドロップダウン。 DAVIDマラン：すべての権利。 それは簡単になってきている。 私はあなたにこの時間を支援するつもりはない。 22を押してください。 STEVEN：完了。 消しゴムになって。 私はブラシになっています。 そして私は22を入れています。 DAVIDマラン：22。 優秀。 したがって、1つより多くの時間。 私は今プッシュするつもりだ スタック26へ。 STEVEN：ああ。 おやっああ。 あなたは本当に油断私を捉えました。 DAVIDマラン：あなたがしませんでした これが来て見？ STEVEN：私はこれが来て見ていない。 我々は、再初期容量だろうか？ DAVIDマラン：良い質問です。 だから我々は一種の自分自身を描いてきた ここのコーナーである。 本当にスティーブンのための良い外にはありません 我々はこの配列を割り当てられたので 静的なので、内側に、話すこと データ構造である。 そして、私たちは本質的にハードコーディングされてきた それはサイズが3であることが。 だから、私たちは本当にそれを再割り当てすることはできません。 我々は、我々は、に戻って行きましたができれば トレイはそのポインタに再定義 我々はその後に手メモリにmallocを使用しています。 なぜなら我々はからメモリを得た場合 malloc関数経由ヒープ、我々 それを解放することができます。 しかし、それを解放する前に、我々は可能性 、メモリの大きなチャンクを再割り当て ポインタを更新する、などが挙げられる。 しかし、今のところ、これは本当にある 我々ができる最善。 pushとpopはおそらく行っている いくつかのエラーを通知する必要があります。 だから例えば、我々の実装 プッシュしたブールを返すことができ 以前に真の、本当の、真の戻った。 しかし四時間、それが持っているために起こっている 例えば、falseが返されます。 わかりました。 非常によくやった。 おめでとうございます。 あなたが今日のあなたのストレスボールを獲得した。 [拍手] STEVEN：ありがとうございます。 DAVIDマラン：ありがとうございます。 [OK]を、ので、これはあまりないと思われる 一歩前進の、右？ 我々は、このデータ構造を説明した。 それは右、説得されている？ それのようなオペレーティングシステム。 明らかにウェブは、これを利用することができ まだ他のアプリケーション。 しかし、私たちがしていることを愚かな制限 背中週一種の2つの限界に どこに私たちは、サイズの配列を修正しました。 そこらのカップルは確かに存在する の方法は、我々はこの問題を解決することができます。 我々は動的配列を割り当てることができ 私がきたようで難しい、それをコーディングしない ここで行われますが、代わりに再宣言 これは、同じように、明確にすること このような何か。 int型*トレイは、決めていない まだ容量に。 しかし、私は他の場所でスタックを宣言するとき 私のコードでは、私はその後、malloc関数を呼び出すことができ の塊のアドレスを取得 メモリ、Iは割り当てることができます トレイにそのアドレス。 そして、それだけの塊だから メモリ、Iは、正方形継続して使用することができ 通常の方法でブラケット表記。 再び、この種の存在だから 配列の機能的に同等と 来るのメモリチャンク malloc関数から戻って。 我々は、他のようなものを扱うことができます ポインタ演算を使用するか、 角括弧表記。 だから一つのアプローチです。 しかし、どのように他の我々は、これを実装するかもしれません 同じデータ構造、潜在的に？ 右？ 私たちはただ、これを解決したように私は感じる 一週間前のような問題。 この問題を解決するには、何だったの スティーブンに走っていること？ だからリンクリスト、右側。 問題は、我々は塗装していることである場合 割り当てることで、自分自身のコーナーへ 私たちはその事前あまりに少ないメモリで その後は、まあ、何とか対処しなければならない 理由だけでは避けられない 完全に出す？ 理由だけであることがトレイを宣言しない ノード、エルゴリンクリストへのポインタ その後、単純に新しいノードを割り当てる スティーブンがフィットするのに必要なたび データ構造に番号。 だから絵は変更する必要があります。 それはきれいにしてようであることを行っていない 3 intの配列だけのような単純な。 今では体へのポインタになるだろう 構造体、及びその構造体はに起こっている intおよび次のポインタを持っている。 それは、そのポインタを介してつながるために起こっている 別のこのような構造体への 別のそのような構造体。 だから絵は実際だろ ビットメシエを得る。 そして、我々の矢印は抱き合わせていると思います 一緒にすべてのもの。 しかし、それはので、右、大丈夫です 我々はこれを行う方法を見てきました。 そして、一度は快適得る リンクされたようなものを実装する あなたがあれば行う必要があるでしょうリスト、 でハッシュテーブルを実装することを選択 P-6のセット用に別のチェーン、次のことができます ビルディングブロックとして、またはそれを使用する 成分、またはスクラッチで話す、 手順、あなたは、あなたを置くことを何か あなた自身のパズルのピースを作成しました あなたはその後再利用できる。 だからトレードオフですが、潜在的な解決策 我々は実際に前に見たこと。 だからかなり頻繁に、このごとを参照してください Appleはリリース1年か2年 何か新しいこと、およびすべての狂った人 アップルの外線まで 彼らの限界を買うために保存 ハードウェア上でアップグレードします。 ので、私は、それはOKですが、これを言う 私はそれらの人々の一人です。 だから、どのようなデータ構造の この現実を表すのでしょうか？ まあ、のはそれをキュー、ラインと呼ぶことにしましょう​​。 だから英国は、それが一般的に呼ぶだろう キューがとにかくので、それはいい名前だ。 そして、そのキュー二つの操作 我々はエンキューを呼ぶことにしますサポートしなければならない 操作とデキュー操作、 に類似している pushとpopする精神。 それだけで別のものだ 大会、私たちがこれらを呼んでいる。 しかし、何かをキューに追加することを意味します またはデータ構造に挿入する。 デキューするには、それを削除することを意味します。 しかし、スタックはLIFOのデータだったのに対し、 構造は、キューは、最初にある データ構造先入れ先出し。 あなたは、行の最初の人であれば、 あなたを取得する最初の人になります ラインの外にして、新しいデバイスを購入する。 これらの人々がどのように動揺だろう想像してみて Appleは代わりにスタックを使用した場合、用 ピッキングを実装するインスタンス、 あなたの新しいおもちゃのアップ。 だからキューは確かに、意味をなさない、と 我々はあらゆる種類のものと考えることができ キューのアプリケーション、おそらく、、 あなたは公平にしたい場合は特に。 それでは、どのように我々は、これらを実装するかもしれません データ構造として？ まあ、私は、我々は可能性があることを提案 このようにそれを行う必要があります。 だから私は今、数字を持っているつもりです。 だから我々は、それが簡単でな​​いでおこう 必ずしもトレイの観点で話す。 の人々が得ているだけの数字。 容量は再び、に起こっている、修正 にすることができ、人々の総数は このライン、3として、または 他のどのような値。 しかし、私は追跡する必要があることを提案する の大きさだけでなく、 キューは、その中にどのように多くのものです。 だからサイズが現在のサイズ、容量は 最大サイズです。 もう一度、命名 慣例により。 なぜ私は内側に追加のint型が必要なのでしょうか 中の人を追跡するためのキューの ラインの前？ なぜ私は、この場合にこれを行う必要がありますか？ さて、どのようにこの絵です 変更するつもり？ 私はおそらく最も再利用することができます この写真の。 私が先に行くと、ここで何を消去しましょう​​。 我々はこれを少しをしてあげる ここでは別の名前まで。 17を取り除くましょう、みましょう取り除く 9に、3を取り除くみましょう。 そしてもうひとつ追加してみましょう。 私はを追跡する必要があることを提案 ただ、リストの前、 同様にint型になるだろう。 そして、我々はそれをシンプルに保つつもりです。 今のところリンクリストはありません。 我々は我々が行っていることを認めるよ この制限に上げる。 しかし、私は見て何をしたいですか 今回が起こる？ だから私は先に行くと、最初の仮定 人が並んで登場し、 それは9番だ。 私たちは、ストレスボールを持っている。 私は、言う、2〜3人を盗むことはできますか？ 一つ、二つ、三つ？ までさあ。 正面から右、なぜなら 我々はこの1つは迅速作ってあげる。 あなたのそれぞれは今であることを行っている アップルのライン内のファンの少年。 あなたは、Appleのハードウェアを受信されることはありません これでもの終わりに。 わかりました。 だから、あなたは、9番だね 番号17、番号22。 これらは以下のように、任意の数字 学生IDやその他もろもろ。 そして、ちょうどその瞬間に、始めましょう 物事の追加を開始します。 そして、私はここに、この時間をボードを実行することになるでしょう。 したがって、この場合には、私が初期化しました なるようにフロント - 私は実際には本当に気にしないのか サイズがゼロであるため、正面である。 だから、これは同様にだけかもしれない 疑問符である。 これらはすべてクエスチョンマークです。 だから今我々は、実際にいくつかを見ることから始めましょう 人々は店で並んで。 9番であれば、あなたは最初のものだ そこに午前5時、先に行くと並んで、 または前の夜。 OK。 だから今9はここにある。 そう9は、リストの先頭にある。 だから私は先に行くと更新するつもりです この電流データのサイズ もう0にしないように構造、 しかし、1とする。 私はで9を置くつもりです リストの先頭。 私が先に行くと、画面を切り替えてみましょう ので、ここで私たちの過去を見ることができます。 そして今、私は何をしたいですか 前面に置くか？ 私が追跡するつもりだ 今キューの先頭 位置0にあります。 次に何が起ころうとしているので？ まあ、私はエンキュー今仮定 17同様に。 だから、そこに並んでホップ。 そして再び、ドアのようなものに 店はここになるだろう。 だから今、私は17を追加しました。 そして、これらの人はブロックしているにもかかわらず OKの画面、、 我々はここでそれを見ることができるので。 申し訳ありません。 聴衆：我々は、移動することができます - DAVIDマラン：いいえ、大丈夫です。 それはそこまで巨大だ。 だから17は現在、キューの中にある。 私はどのを更新する必要があります しかし今のフィールド？ OK、確かにサイズ。 そして、どのようにフロントはどうでしょうか？ いや、OK。 フロントには、変更すべきではありませんので、 スタックとは異なり、我々 公平性を維持したい。 9が最初に来たのであれば、我々は9が欲しい 行の最初にすること とストアに。 実際には、その見てみましょう。 我々は22を挿入する前に、してみましょう 先に行くとデキュー9。 あなたの名前は何です再び？ 読者：ジェイク。 DAVIDマラン：ジェイクが起こっている 今デキューする。 だから、店に歩いてもらう。 とふり、そのストア あそこです。 だから今必要なもの - DIT-DIT-DIT！ 何が今起こる必要ですか？ デザイン決定。 だから悪くない本能が、 - あなたの名前は何ですか再び？ 読者：デビッド。 DAVIDマラン：デビッド。 ダビデは何をしたのですか？ 彼は固定のデータをソートしようとしていた 彼の場所から構造および移動 ジェイクの元の場所に。 そして、我々は喜んでいる場合、それは大丈夫です としてそれを受け入れるように 実装の詳細。 しかし、最初のデータを更新してみましょう 我々はそれを行う前に、構造。 私はすべてのアイデアを好きではないだから 人々がこの行にシフト。 ダビデはそれをしない場合、それは大したことない 一歩ですが、再び、に戻ると思います 我々は上の8人のボランティアを持っていたとき ステージと我々は挿入のようやった 我々はスタートしなければならなかったソート、 周りの人を動かす。 それは右、高価だ？ ビッグOについて私はうんざりなること n個のnの大きなOが再び乗。 それはのように感じていない 理想的な結果。 だから、これを更新してみましょう。 だからキューのサイズ もはや2ではありません。 これは、今では単に1だ。 しかし、私は今、何かを更新することができます 私は前に更新されませんでした、 リストの先頭。 私はちょうどその場所1である、と言うことができる？ だから今我々は、ここにゴミ値を持つ ゴミここで値、でデイビッド このゴミの真ん中。 しかし、データ構造 まだそのままである。 実際に、私もする必要はありません ジェイクの元数を変更 9、気遣うので。 私は今で十分な情報を持っている 私はそこの一人で知っているサイズ このキュー。 そして私は知っているその人 場所1、ではない0にあります。 私は数えていないよ。 1だから、同様に。 だから、データ構造はまだOKです。 さて、次に何が起こるか？ レッツエンキュー - お名前は何ですか？ 読者：キャレン。 DAVIDマラン：キャレン。 キャレンをエンキューましょう、と 22はキューになりました。 だから今、ここで変更しているか？ フロントに行くされていません 明らかに、変更します。 サイズは再び2と変更する予定です。 22はここで終わる、9は、依然として存在している それが効果的だ 今ゴミ値。 それはちょうどジェイクの過去の名残だ。 だから今何が起こるか 私はデイヴィッドをデキュー？ One最後の操作、デキューデビッド。 我々はシフトする可能性がありますが、私はレッツを提案 できるだけ少ない作業として行う。 今私のデータ構造が行く 2から1へのサイズのバック。 しかし、キューの先頭 今、2になります。 私は、これらの番号を変更する必要はありません ただまだ、彼らはだから ただゴミ値。 しかし、今は何が起こる？ 私は自分自身、26をエンキューと仮定？ 私はこっちに属するような気がします。 だから私は、キューに入れられているんだ。 だから私は種類のここに属しています。 そして、あなたは全くないにもかかわらず、 ステージ上で視覚的にこれを感謝し、 我々は部屋がたくさんあるので、私がすべき ここに立っていることではない、なぜですか？ 読者：あなたが範囲外です。 DAVIDマラン：右。 私は範囲外です。 私は越えてインデックスを作成しました この配列の境界。 私は実際のいずれかでなければなりません 3つの可能な場所。 さて、どこへ行くのが最も自然なのですか？ 私は我々が活用提案 週に1つのトリック。 Mod演算子、パーセンテージ。 私は技術的に立っているので、 場所3、しかし、私は、3 MOD容量を行う その3、パーセント記号、3 - 容量の3。 何それ？ 残りは時何 あなたは3点で3を分割？ 0。 だから私を置くことジェイクは、であった これは実際には良いです。 だから今は実装 このことのために起こっている 頭痛のビットである。 それは本当に1行だけだ 頭痛のコードの。 しかし、少なくとも今ではゴミはあり ここで値が、そこの2 ここで正当な整数。 そして、私は今、私たちが行っていると主張 まさに我々がいる限り何をすべきか 私たちは何のジェイクを変更 値が26であることだった。 私たちは、今はまだ十分な情報を持っている 整合性を維持するために このデータ構造である。 時々我々はまだ運のようなものの外出 合計四つ以上を挿入する 要素が、私は、少なくともかなり作ることができます この定数の効率的な使用 実際の時間、。 私がシフトを心配する必要はありません みんな、Davidの傾きがあったように。 スタック上のご質問、 またはこのキュー？ 読者：理由です あなたが知っているので、あなたのサイズを必要とする 人を持っているどこに？ DAVIDマラン：その通り。 Iは、配列の大きさを知る必要がある 私は正確にどのように知っている必要がありますので、 これらの値の多くは合法的であり、 どこに置くかと私は見つけることができる 次の人。 まさに。 サイズは - 実際に、我々はまだ、これを更新しませんでした。 私は26で自分自身を追加しました。 サイズが、現在ではない1であるが、2。 だから今、これは確かに私が見つけることができます リストの先頭には、これは0ではない、ではない 1ですが、2である。 リストの先頭 22番は確かです。 彼は最初に来たので、彼は必要があるため 私の前にストアに許可され、 もかかわらず、視覚的に私が立っている 店に近い。 大丈夫？ これらの人のために拍手 そして我々は彼らをそこから出てもらおう。 [拍手] DAVIDマラン：私はさせことができる あなたは、トレイを保つ。 我々は何が起こるか見ることができました あなたはしたいが、そうでないかもしれない。 わかりました。 だから今はそれが私たちに何を残すのでしょうか？ まあ、私があることを提案してみましょう 私たちができるいくつかの他のデータ構造 意志たちのツールキットへの追加を開始 として実際には非常に、非常に関連性がある 我々は、Webのものに飛び込む。 どの再び、接続のいくつかの種類を持っている の形で木に DOMと呼ばれるものは、文書 オブジェクトモデル。 しかし、我々はより多くを見ることができます そのずっと前に。 私は我々というdefinitionally提案してみましょう 今、あなたは知っているかもしれないものとして、木を呼び出す 家系、あなたのより多くの でいくつかの祖先を持っている 木の根。 で家父長または女家長 ツリーの最上部。 配偶者なしで、このような場合である。 しかし、我々は今我々が呼ぶよ何を持っている ハングノードである子どもたち、 左の子、または右の子オフ、 矢印は、ここに示されている。 換言すれば、ツリーデータ構造で コンピュータで、ツリーはゼロを持って 以上のノード。 それは少なくとも1つのノードがある場合は、 それは、ルートと呼ばれています。 これは、視覚的にいる事だ 私たちは、一番上に描画します。 そのノードは、他のノードのように、することができます 、0,1、または2つ、または3つを有する またはしかし多くの子どもたち データ構造をサポートしています。 この場合、ルートは、記憶 1の値は、2人の子供、2および3を有する 従って我々は一般的に2左を呼び出す 子供と3右の子。 そして、我々は5、6に取り掛かるとき、および 7、6は真ん中の子と呼ばれるかもしれない。 あなたには、四人の子供を持っている場合、 それは混乱を取得します。 だから私たちはそのようなものを使用して停止 ショートカットの口頭。 しかし、それは本当に家系だ。 そしてここで葉はそのノードである 自身が子を持たない。 彼らは、ツリーの最下部をオフにハングアップ。 では、どのようにその木を実装するかもしれません 最大限にただ二人の子供を持っている？ 我々はそれをバイナリツリーと呼ぶことにします。 同性には再びこのでは、2つの意味 バイナリとのような場合、。 そしてそれは、ゼロ、1つを持つことができます または最大限に二人の子供。 私たちは、ノードを実装することを提案します int型のnは、その構造のために、 し、2つのポインタと呼ばれる1つの 左、人は右と呼ばれる。 しかし、それらは単にいいです 任意の規則。 そして、あなたは、今では場合は特に素敵な何だ の種類はと概念的に苦戦 再帰、またはそうでないと思った 何を本当に解決策、 特にあなたができれば メモリが不足する。 今、我々はデータの話をしていることを 許す構造とアルゴリズム それらを横断し、操作するために私達に、 再帰に戻ってくることが判明 はるかに説得力のある 美しい方法ではない場合。 だから私は提案し、これは実装です 検索機能の。 2つの入力を与え - そのブラックボックスと考える。 二つの入力、N、int、および与えられた 木へのポインタへのポインタ ノード、または実際にツリーのルート、I この関数が返すことができるという主張 trueまたはfalse、そのnの値 このツリーの内部です。 このブラックボックスの中には何ですか？ さて、4枝。 最初だけチェックします。 木がnullの場合は、ただfalseを返す。 どのノードがない場合、nは、ありません ない番号がありません、ただfalseを返す。 しかしもし、nは、あなたが探している値 例えば、ツリー矢印n個未満であり、かつ ただ明確にするためには、ときに何を意味するのでしょう 私は、ツリーと矢印を書く 表記法、N？ まさに。 これは、間接参照を意味する ツリーと呼ばれるポインタ。 そこに移動し、その中に入る ノードとそのフィールドがnと呼ばれ得る。 そしてあった実際のNを比較 それに対する検索に渡され。 nはn値未満であれば ツリーノード自体は、まあ、 それは何を意味するのでしょうか？ それは一目見ただけで何の意味もありません。 右？ あなたの配列を持っているときと同じように 値は、バイナリを適用するかもしれません 分割の形などの検索 と征服。 しかし、どのような仮定すると、我々は確認する必要がありました すべてで動作するバイナリ検索用 電話帳でと 前述の例？ どのようにソートする。 それでは、木の定義を洗練させて ここですることができるだけでツリー、すべきではない 子供任意の数を有する。 だけではなく、バイナリツリー、そのことができます 0,1、または最大2を有する。 しかし、二分探索木として、またはBST、 これは、ただ言う空想の方法です バイナリツリーようにすべてのノードの 左の子は、存在する場合、ある ノード未満。 そして、すべてのノードの右の子、 存在する場合は、大きい ノード自体より。 だから、他の言葉で、あなたが描画した場合 ツリー外に、数字のすべてがある このように慎重にバランスのとれたようであれば あなたが行くことができ、ルートとして33〜55を持って その左には55未満だから。 77は、その右に行くことができます それは、55よりも大きいです。 しかし、今、同じ定義を気付く それは、口頭で再帰的な定義だ 33を申請しています。 33の左の子は、それ未満でなければなりません と33の右の子、44は、でなければなりません それよりも大きい。 だから、これは二分探索木であり、 私の少しを使用して、提案する 再帰は、我々は今、n個を見つけることができます。 nは、の値がnよりも小さいのであれば 現在のノードが、私は行くつもりです 先とパント、いわば、とだけ 答えはである何を返す nに探し 木の左の子。 再び注目し、この機能だけ ノード星、期待してい ノードへのポインタ。 だからきっと私はちょうどツリーを行うことができます つながる矢印左、 私を別のノードに。 しかし、そのノードは何ですか？ さて、この宣言によると、 左がその結果だけでは、単にポインタである 私は検索機能に渡していることを意味し 別のポインタ、すなわち 表す1つの 私の左の子のツリー。 したがって、この場合には、ポインタがあれば、33〜 これがあれば、一方で我々のサンプルの入力です nは値よりnにおける大きい ツリー内の現在のノードが、その後私はよ 他に先に行くとパントに行く 方向とだけ言って、私はしないでください この値は、nはツリー内にあるかどうかを知り、 私はそれがあれば、それは私のダウンであることを知っている 右側のブランチは、いわば。 だから、私は検索再帰的に呼び出してみましょう 再びNを渡しますが、渡して 私の右の子へのポインタ。 言い換えれば、私は現在いたら55時 と私は99を探しています、私が知っている99 私は引き裂いたので、ちょうど同じように、55より大きい 電話帳週間前に、私たち 同様に私たちは、まっすぐ飛んでいった 右ここに行くつもり。 それは私の右側にいた場合、私は知らない 子供は、それはないが、77はありますが、 私はそれがその方向に知っている。 だから、私は右の子の検索を呼び出し、 77、検索から把握させ そこにあれば、この任意で99 例は実際にある。 そうでなければ、最後のケースは何ですか？ 木がnullの場合は一例です。 nは、現在のノードの未満である場合 値は、別のケースである。 nは電流よりも大きい場合 ノードの値は、第三のケースです。 4番目と最後のケースは何ですか？ 私は、我々は右、例出ていると思う？ nがであること、それでなければならない 私は上だと現在のノード。 私はこの時点で55を探しているのであれば の物語の中で、そのブランチ ツリーには、trueを返します。 それでは、ここで興味深いのは、我々ということです 実際、過去数週間、我々種類は違って のは、2つのベースケースを持っている。 そして、彼らはする必要はありません 上部にあるすべてのこと。 上部には、ベースケースであるため場合 木がnullの場合、何の関係もありません。 ただ、ハードコードを返す 値false。 ボトム支店の一種である 我々がチェックした場合、それによってデフォルト、 、我々はそれがあるべき場合はnullをチェックした 左が、それはすべきではない、我々はしました それは右であるべき場合にチェックされますが、それ すべきではない、明らかにそれがなければならない 右のどこに私たちはいます。 それは、ベースケースです。 ので、2つの再帰的な場合があり 途中でそこに挟まれた。 しかし、私は書かれている可能性が 任意の順序でこれ。 私はそれが一種の自然な感じと思った 最初のエラーの可能性をチェックする、 その後、その後、右確認、左確認 ノードにいることを前提としてい あなたが実際に探している。 では、なぜこれが役に立つかもしれません？ だから、判明 - と私はティーザーにジャンプしてみましょう ここではウェブにそのだ。 我々はしない使用を開始するつもりだ プログラミング最初は言語が、 マークアップ言語。 の一つであるマークアップ言語 プログラミングと基本的に変わるところは 言葉、それはあなたに与えるものではありません 論理的に自分を表現する能力。 それだけであなたの能力を与える 構造的に自分を表現。 どこに何を入れたいか ページ上の、ウェブページ？ あなたはそれを作るために何色をしたいですか？ どのようなフォントサイズは​​、それを作りたいのですか？ 何の言葉は実際にあなたを行う Webページにしたいですか？ だからマークアップ言語です。 しかし、その後、我々は非常に迅速に紹介しま​​す 本格的なされるJavaScript、 プログラミング言語。 構文的に外観が非常に似て Cに、それはいくつかを持っているよ 素敵な、より強力な、より多くの ユーザーフレンドリーな機能。 そして、これで不満の一つ 学期のポイントは、我々がよということです すぐにはるかに少ないでスペルチェックを実装 他の言語を使用したコードの行 C自体は可能ですが、理由のより 我々はすぐに理解できるでしょう。 これは最初のそのようなWebページになります。 それは、完全にがっかりされます 私たちが作る最初のもの。 これは単に世界こんにちは、と言うだろう。 しかし、あなたはそれを見たことがない場合 前に、これはHTMLです、 ハイパーテキストマークアップ言語。 あなたは、ある特定のメニューオプションに行く場合 上の任意のWebページ上のほとんどすべてのブラウザ、 インターネットは、あなたは、HTMLを見ることができます 一部の人々はに書き込んだ そのWebページを作成します。 そして、それはおそらくとして見ていません 短いまたはこれと同じくらいきちんとした。 しかし、それは、これらのパターンに従います 開いた括弧とスラッシュと 文字と潜在的数字。 私はあなたにティーザーを与えるだろうと思って あなたが行うことができるでしょう何の CS50を取った後。 私はcs.harvard.edu /ロブに行こう、 私たち自身のロブボーデンのホームページ。 彼は私たちのためにこれを作りました。 だから、すぐにそれを行うことができるでしょう。 そしてまた、あなたは何を聞いた 今朝 - あなたは今朝聞いた - [ハムスターダンスミュージック] - you'llは、これを作ることができる。 それは水曜日に私たちを待っています。 私たちは、あなたが表示されます。 [ハムスターダンスミュージック] DAVIDマラン：次のCS50で -