>> 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で -