[Powered by Google Translate] [第6週、続く] [デビッド·J·マラン] [ハーバード大学] [これはCS50です。] [CS50.TV] これはCS50であり、これは第6週の終わりです。 だからCS50x、EDXイニシアチブに関与ハーバード初のコースのひとつ 確かに、この過去の月曜日にデビューしました。 あなたは、インターネット上で何他人を垣間見ることがしたい場合 今と一緒にフォローしている、あなたはx.cs50.netに向かうことができる。 edx.org上の適切な場所にリダイレクトされますつまり、 どの本とMITとバークレーから他のコースが今住んでいるところだった。 あなたのアカウントにサインアップする必要があります、あなたは、材料はほぼ同じであることがわかります 私達はいろいろと準備をするようには、数週間遅れとはいえ、この学期を持っていたとして。 しかし、何CS50xの学生が今見ますと、非常にこのようなインターフェイスです。 これは、例えば、問題セット0のチュートリアルをリードZamylaです。 edx.orgへのログイン時に、CS50x学生は物事の種類を見ている 、月曜日の講義を：あなたは、コースに見られるような、 水曜日、さまざまなショートパンツ、問題セット、チュートリアル、PDFの講義。 加えて、ここで見たように、機械翻訳 、イタリア語、スペイン語、日本語、中国語に英語の成績証明書の 確かに不完全になり、他の言語との全体の束 我々は、プログラムのAPIと呼ばれるものを使用してそれらをロールアウトするように、 Googleから、またはアプリケーション·プログラミング·インターフェース、 それは、私たちは、これらの他の言語に英語に変換することができます。 しかし、いくつかの百プラスボランティアの素晴らしい精神のおかげで、 親切に巻き込まれることを申し出ているインターネット上のランダムな人々 このプロジェクトでは、我々は徐々にそれらの翻訳の品質を向上させることでしょう 人間は私たちのコンピュータが作っていることの間違いを修正させることによって。 

だから、我々はいくつかのより多くを持っていた20人の生徒は、我々が当初予想よりも月曜日に表示に変わります。 実際には、今CS50xは自宅で一緒に以下の10万人を持っています。 ですから、コンピュータサイエンスのこのコースを作るこの期生のすべての部分です実現 教育より一般的には、もっと広く言えば、アクセスできます。 そして現実には、これらの大規模なオンラインコースのいくつかと、今ある それらはすべて我々がここで行っているように見えるように、これらの非常に高い数字で始まる。 しかし、目標は、最終的に、CS50xためできるだけフィニッシュラインをできるだけ多くの人々を得るために本当にです。 設計により、CS50xこの過去月曜日から提供されようとしている 人々は他の場所で学校のコミットメントを持っているように、2013年4月15日を介してすべての道、 仕事、家族、他の競合など、もう少し柔軟性を持っている このコースに飛び込むことになる、これは、、それが言えば十分 通常の学期中、わずか3ヶ月に渡っている場合にのみ、非常に意欲的に行われます。 しかし、これらの生徒は、同じコンテンツを視聴し、同じ問題セットに取り組むことになる 同じショートパンツなどへのアクセスを有する。 だから我々はこの一緒にすべて実際にあることを認識しています。 とCS50xの終わりの目標の一つは、同じように多くの人々を得ることではありません フィニッシュラインにし、それらにコンピュータサイエンスのこの新たな理解を与える とプログラミングだけでなく、彼らは、この共有経験を持っている持っている。 キャンパス内の50の特​​徴の1つは、我々は願っています、 、時々、良くも悪くも、共同の経験のこの種であった しかし、これらの人々に左右にターンすること、 とオフィスアワーとhackathonかつ公正。 それは、オンラインの人々と個人的にそれを行うには少し難しくなっている しかしCS50xは、初CS50エキスポ4月に締結する 公正の私たちのアイデアのオンライン適応される 学生のこれらの数千はすべて1を提出するよう要請される場所 -  2分間のビデオに、 それらの彼らの最終的なプロジェクトやビデオのスクリーンキャストは、hello振っどちら とそのプロジェクトについて話して、それをデモ、 ずっとあなたの前任者のようには、公正でキャンパスでここに行っている 学期の終わりまでに、希望はグローバルな展示会を持つようになるように キャンパスでここにこの12月あなたを待ってずっとそのようなCS50x学生の最終的なプロジェクトの。 これから数ヶ月で、その上で非常に多くの。 

10万人で、しかし、いくつかのより多くのCAの必要性を付属しています。 君たちはここで新機軸を開くとCS50を取っていることを考えると EDX上の人々にこの材料のリリースに先立って数週間、 我々はこの構想に、できるだけ私たち自身の学生の多くが関与するのが大好きだ実現する、 学期と同様に、今年の冬と今年春に両方。 ですからCS50xに巻き込まれたい場合は、 特にCS50x議論し、CS50論議のEDXバージョン、上に参加 あなたがたの多くは、キャンパス内で使用されている、オンラインの掲示板、 そのURLへの頭をしてください、私たちはあなたが誰であるかを知らせる 私たちは、学生やスタッフのチームと教員を構築してみたいので キャンパス内に単にに沿って演奏し、手伝っている人。 そして、彼らはそれらになじみの質問を見たとき、 あなたは、インターネット上のいくつかの国でそこにどこかにいくつかのバグを報告する学生を聞く あなたも、同じ問題を持っていたので、ベルを鳴らしている あなたのD-ホールでいくつかの時間前に、うまくいけば、あなたは相づちを打つと自分の経験を共有することができます。 ですから、もし、ご希望分かち合うようにしてください。 

ハーバード大学でコンピュータサイエンスのコースは、伝統のビットを持っている いくつかの服装を持っていることのそれらの間のCS50、あなたが自信を持って着ることができるいくつかの服、 学期の終わりに、あなたはCS50を終了したことを非常に誇らしげに言って とCS50などを取って、我々は常に学生を関与しよう この過程で、可能な限り、それによって私たちが招待 学期のこの時期には、学生がデザインを提出する 選択肢のPhotoshopを使って、あるいはどのようなツールでも使用したいのですが あなたは、Tシャツやスウェットシャツのデザインを提出し、デザイナーなら と犬のための傘と小さなバンダナは、我々は今持っているなどが挙げられる。 そして、すべてはその後です - 受賞者は毎年、その後展示されています store.cs50.netでコースのウェブサイトで。 すべてはそこにコストで販売しますが、ウェブサイトでは、単にそれ自身が実行され そして人々は、彼らが好きな色やデザインを選ぶことができます。 だから私たちはちょうど昨年の設計のいくつかを共有したいと思った それは毎年の伝統であるここでは、この1以外のウェブサイトにあった。 "私はFaultnをワンセグてる毎日は"昨年提出の一つであった、 これは、卒業生のためにそこにまだ使用可能です。 我々は、このいずれかを持っていた、 "CS50は、1989年に設立。" 当社Bowdensの一つ、ロブは、昨年とても人気があった。 "チーム·ボーデンは"生まれた、このデザインは、トップ売り手の間、提出された。 として、この1つはここにあった。多くの人々が販売ログによると、 "ボーデンフィーバー"を持っていた。 それは今までインターネット上で、そこにあなたのデザインかもしれないことを認識しています。 次の問題でこれについての詳細は、来るように設定します。 

もう1つのツール：あなたが今うまくいけば、いくつかのエクスポージャーを有していたとき GDBでいくつかの実地体験、 これは、もちろん、デバッガであり、あなたが操作することができます かなり低いレベルでのプログラムは、どのような種類のものをやって？ GDBは、あなたが何をできるのですか？ うん？私に何かを与える。 [学生の答えは、不明朗] グッド。関数にステップインするので、あなただけの実行を入力する必要はありません と標準出力に物事をプリントアウトし、その全体を通して、プログラムの一撃を持っています。 むしろ、次のいずれかの横に入力し、それを介して行ずつステップ実行することができます あなたが書いた典型的には、関数に飛び込むラインや工程によって行ずつ移動する1。 GDBは、あなたが行う他に何ができるのですか？うん？ [学生の答えは、不明朗] 変数を印刷します。あなたのプログラムの中に少しのイントロスペクションを行いたいのであれば あらゆる場所にprintf文を書くことに頼ることなく、 あなただけの変数を印刷したり、変数を表示することができます。 あなたは、GDBのようなデバッガで他に何ができる？ [学生の答えは、不明朗] その通りです。あなたは、ブレークポイントを設定でき、ブレーク実行を言うことができます main関数またはfoo関数で。 あなたは、123行目でブレーク実行を言うことができます。 とブレークポイントは本当に強力な技術である なぜならあなたはどこにあなたの問題の一般的な意味を持っている場合 おそらく、あなたは、プログラムの全体をステップ実行時間を無駄にする必要はありませんされています。 あなたは本質的にそこにジャンプしてから入力を開始することができます -  stepやnextなどでそれをステップ。 しかし、GDBのようなものでキャッチは、それは、人間に役立つことです あなたの問題を見つけ、あなたのバグを見つける。 それは必ずしもあなたのために多くのそれらを見つけることができません。 

だから我々は短いコマンドラインツールです先日style50を導入 よりきれいにあなたよりもあなたのコードを少しはめるしようとしている、人間が行っている可能性があります。 しかし、それは、あまりにも、本当にただ美的なものです。 使用するのはもう少し難解ですValgrindのと呼ばれるこの他のツールがあるのOUTしかし、それは変わります。 その出力は一見atrociously謎めいています。 しかし、それは特に今、私たちは、用語の一部にいることを、素晴らしく便利です どこでmallocと動的なメモリ割り当てを使用し始めている。 物事が迅速に、本当に、本当に間違って行くことができます。 なぜならあなたのメモリを解放するのを忘れたり、あなたには、いくつかのNULLポインタを間接参照する場合、 または、いくつかのゴミポインタを間接参照する、一般的にその結果の症状は何ですか？ seg ​​faultを。そして、あなたは、キロバイトまたはメガバイトのいくつかの数のこのコアファイルを取得する それがクラッシュしたとき、それは、あなたのプログラムのメモリの状態を表す しかし、あなたのプログラムが最終的にセグメント障害、セグメンテーションフォルト、 これは何か悪いことがほとんど常に関連起こっ意味 あなたがどこかで作ったメモリ関連のミス。 だから、Valgrindはあなたがこのようなものを見つけることができます。 あなたのプログラムをコンパイルした後には、GDBのように、あなたが実行するツールです しかし、直接ではなく、プログラムを実行する際には、Valgrindは実行 とあなたはGDBとまったく同じように、あなたのプログラムに渡す。 さて、使い方は、最高出力の種類を取得する 画面の上になる権利がある、少し長いですあなたはValgrindの-vを参照してくださいよ。 あなたがLinuxコンピュータ上でプログラムを使用しているときは、 "-v"ほぼ普遍的に冗長なことを意味します。 だから、あなたは、デフォルトではかもしれないより多くのデータを吐き出すことを意味します。 " -  =完全に漏れを確認してください。"これは単に、すべての可能なメモリリークのチェックを言っている 私が作ったかもしれないというミス。これも、Linuxのプログラムと共通パラダイムです。 一般的に、 "スイッチ"のコマンドライン引数を使用している場合、 そのプログラムの動作を変更することになって、それがただ一つの手紙だのは、 それが切り替わっている場合、それは、単にプログラマの設計によっては、-vですが、 単語の完全な単語または一連のですが、コマンドラインの引数で始まる - 。 これらは、ちょうど人間の慣習ですが、あなたはますますそれらが表示されます。 そして、最後に、 "a.outは"この特定の例では、プログラムの任意の名前です。 そして、ここでは、いくつかの代表的な出力です。 

我々はそれが意味するかもしれないものを見て前に、私はこっちのコードスニペットに渡って行こう。 そして、すぐに来て、私は道のこれを移動することができ とのヒアこの短い例ですmemory.cの、見てみましょう。 したがって、このプログラムでは、私は関数や質問にズームインしてみましょう。 我々は、F関数を呼び出すmain関数を持っている その後何fは少し技術的な英語で、何に進みますか？ fは何を進めるのですか？ どうです、私は20行目から始めましょう、と星の位置は重要ではありません、 だけど、最後の講義と一緒にここに一貫しているでしょう。 20行目では、私たちのために何をするのか？左手側にあります。我々は、さらに壊してやる。 int型* X：それは何をするのでしょうか？ オーケー。これは、ポインタを宣言し、今のはもっと技術的なことしてみましょう。 それはポインタを宣言するために、非常に具体的には、どういう意味ですか？他の誰か？ うん？ [学生の答え、理解不能]遠すぎる。 だからあなたは、等号の右側に読んでいる。 ただのint * xに、ちょうど左のは、注目しましょう​​。 これは、ポインタを "宣言"が、今、その定義に深くでレッツダイビングん。 それは具体的には、技術的にはどういう意味ですか？うん？ [学生の答えは、不明朗] オーケー。これは、メモリ内のアドレスを保存するために準備を進めている。 グッド。とのこの一歩進めてみましょう、それは、32ビットの変数xを宣言している。 そして、私はそれがために32ビットであることを知っている - ？ それがこの場合のポインタだからそれは、int型だからそうではありません。 それはint型を持つものと同じだという偶然、 しかし、星があるという事実は、これはポインタであるそこに意味 とアプライアンスでは、多くのコンピュータと同様に、すべてではありませんが、ポインタは32ビットです。 最新のMacは、最新のPCと同様に、より現代的なハードウェア上では、64ビット·ポインタを持っているかもしれませんが、 が、アプライアンスでは、これらのものは32ビットです。 だから我々はそれを標準化します。具体的には、物語は次のようになる： 私たちは、ポインタを "宣言"、それはどういう意味ですか？ 我々は、メモリアドレスを格納するための準備をします。 どういう意味ですか？ 我々は、32ビットを占有しますと呼ばれる変数xを作成 それはすぐに整数のアドレスを格納します。 そして、それはおそらく我々が得ることができると同じくらい正確なのです。 それは、世界を単純化し、ちょうどxというポインタを宣言したとする前進大丈夫です。 ポインタを宣言しますが、実際に何が起こっているのを認識し、理解する だけでも、それらのいくつかの文字インチ 

さて、この1つは、それが長い式は言っても、ほとんど少し簡単です。 だから、これは現在ハイライトされていること、何をやっている "のmalloc（10 * sizeof（int））を、"ええ？ [学生の答えは、不明朗] グッド。そして、私はそこにそれを取るよ。これは、10個の整数のためのメモリチャンクを割り当てている。 そして今、少し深くでダイビングしましょう​​、それは10個の整数のために大量のメモリーを割り当てている。 malloc関数その後復帰とは何ですか？ そのチャンクのアドレス、または、より具体的には、そのチャンクの最初のバイトのアドレス。 どのようにしてどこにメモリの端の、そのチャンク私は、プログラマが、知っているのですか？ 私はそれが連続したことを知っている。 malloc関数は、定義により、あなたのメモリの連続した​​チャンクを与えるだろう。 それにギャップはありません。あなたは、そのチャンク内の全てのデータへのアクセス権を持っている 背中合わせに戻ることではなく、このメモリチャンクの終わりがどこにあるか、どのように私は知っていますか？ あなたは、mallocを使用するときは？ [学生の答え、理解不能]グッド。 あなたはしないでください。あなたが覚えておく必要があります。 私は値10を使用したことを覚えておく必要があり、私もそれここでやったとは思えません。 しかし、責任は私に完全にある。我々が文字列のためにわずかに依存するようになってきたstrlenは、 なぜなら\ 0を持つこの大会の作品だけ 文字列の末尾にNULかこの特別NUL文字、、。 これはメモリのちょうど任意のチャンクに保持していません。 それはあなた次第です。だから、20行目は、その後、メモリのチャンクを割り当て それは10個の整数を格納することができ、そしてそれは最初のバイトのアドレスを格納 と呼ばれる変数xのメモリのチャンクの。 ポインタであるエルゴ、。だから、21行目は、残念なことに、間違いだった。 しかし、最初に、それは何をやっている？それは、場所10、インデックス0の店を言っている メモリのチャンクの値を0 xという。 

だから物事のカップルが起こっているがわかります。 xがポインタであっても、数週間前からリコール あなたはまだ配列形式の角括弧記法を使用することができます。 それは実際にはもっと不可解に見えるポインタ演算に対する簡略表記だから。 我々はこのような何かをする場所：アドレスxを取り、上に10箇所を移動 その後、その場所に格納されたアドレスに進みます。 しかし、率直に言って、これは読んで慣れるためだけに凶悪です。 だから世界は、典型的には、読むことをそんなに、より人間にやさしいという理由だけ角括弧を使用しています。 しかし、それは本当にフードの下で何が起こっているかです; xはアドレスではなく、配列自体です。 だから、これは、xの位置10に0を格納しています。 なぜこれが悪いのか？うん？ [学生の答え、理解不能]その通りです。 、我々は唯一の10個のint値を割り当てられますが、C言語でプログラミングするとき、我々は0から数える ので、0 1 2 3 4 5 6 7 8 9ではなく、10へのアクセスを持っています。 だから、どちらかのプログラムがセグメントフォルトに起こっているか、そうではありません。 しかし、我々は本当に知りませんが、これは非決定的な振る舞いのようなものです。 それは本当に我々が幸運を得るかどうかに依存します。 それは私がその余分なバイトを使用する場合は、オペレーティングシステムには気にしないことが判明した場合、 それは私にそれを与えていないにもかかわらず、私のプログラムがクラッシュしない場合があります。 、それはバグだらけだ、生ですが、あなたはその症状が表示されない場合があり またはあなたはしばらくの間に一度だけそれを見るかもしれません。 しかし、現実にはバグがあり、実際にはあるということです。 あなたが正しいことをするプログラムを書いたことがあるのなら、それは、本当に問題だ あなたは人々がすべてのがたまにクラッシュすることが、使用しているプログラムを販売してきた なぜなら、もちろん、これは良くありません。実際には、あなたのAndroid携帯電話やiPhoneを持っている場合 そして、あなたは、これらの日のアプリをダウンロードあなたが今まで持っていた場合にアプリが終了するだけ ほとんどの場合、いくつかのメモリ関連の問題の結果だとそれが消える突然、 プログラマは、ポインタを台無しにし、それによって間接参照 彼または彼女は持つべきではない、とiOSやAndroidの結果は、単に完全にプログラムを強制終了することを むしろリスク未定義の動作またはセキュリティ侵害のいくつかの種類より。 

これ以外にも、このプログラムのもう一つのバグがあります。 私はこのプログラムに他に何を台無しにしている？ 私が説教したものを実践していませんでした。うん？ [学生の答え、理解不能]グッド。 私はメモリを解放していない。だから今は経験則 あなたは、malloc（）を呼び出すいつにする必要があり、そのメモリを使用して設定が終了したら、自由に呼び出す必要があります。 さて、ときに私はこのメモリを解放したいのでしょうか？ おそらく、この最初の行は正しかったと仮定して、私はここでそれをやってみたいと思います。 ので、私は、例えば、ここでそれを行うことができませんでした。なぜですか？ ただスコープ外。だから我々は、ポインタの話をしているにもかかわらず、 これは、xは、それが宣言された中括弧内のスコープである週2または3の問題である。 だから、あなたは間違いなくそこにそれを解放することはできません。それを解放するために私の唯一のチャンスは、大体21行目の後である。 これはかなり単純なプログラムである、あなたは一種のあなたの心を包んでしまえば、かなり簡単だった 間違いがあった場合にどのような周りのプログラムは、やっている。 そして、あなたが最初にそれを見なかったとしても、うまくいけば、今は少しは明らかだ これらの間違いはかなり簡単に解決すると簡単に作られている。 しかし、プログラムが12以上の行の長さである場合には、100行の長い、長い50行だ 論理的にそれを考えて、線であなたのコード行を歩いて、 、常にバグを探して、可能性はなく、やることは特に楽しいです そしてそれを行うことも困難だし、Valgrindのようなツールが存在する理由です。 私が先に行くとこれをやってみましょう：私は私の端末ウィンドウを開いてみましょう、 とメモリは大丈夫だと思われるので、私はただ、メモリを実行しないようにしましょう​​。 私は幸運取得しています。配列の最後に追加のバイトに行く あまりにも問題があるようには思えない。 しかし、単に確認を行うことを意味健全性チェックを行い、それにもかかわらず、私を聞かせて これは実際に正しいかどうか。 

だからvalgrindの-vを実行してみましょう - リークチェック=フル、 し、この場合のプログラムの名前は、メモリではなく、a.outです。 だから私は先に行くとこれを行うことができます。 ENTERキーを押してください。 親愛なる神。これは、その出力され、これは私が以前に言及したものです。 しかし、あなたはここにナンセンスのすべてを読むことを学ぶ場合には、 これのほとんどが面白くないというだけの診断が出力されます。 何があなたの目が本当に探して欲しいとすると、エラーまたは無効のいずれかの言及である。 問題を示唆する言葉。 そして実際、ダウンここで間違って何が起こっているのか見てみましょう。 私はいくつかの並べ替えの概要、持っている "出口で使用されている：1ブロック内の40バイトを" 私はまだ実際にブロックが何であるかわからないんだけど、40バイト それはから来てどこに私が把握できるように、実際に感じている。 40バイト。なぜ出口で使用されている40バイトは何ですか？ より具体的には、我々がここで下にスクロールした場合、 なぜ私は間違いなく40バイトを失っているか？うん？ [学生の答え、理解不能]パーフェクト。ええ、その通りです。 、そこに10個の整数があって、それらの各々は、2,4、または32ビットの大きさである あなたが提案したように、私は自由に呼び出していない、ので、ので、私は正確に40バイトを失ってしまった。 それは、一つのバグだし、今のさらに少し下に見て、この隣に見てみましょう "無効なサイズ4の書いている。"さて、これは何ですか？ このアドレスは、明らかに、何ベースの記法を表すのでしょうか？ これは、16進数であり、あなたが0xで始まる番号を参照してくださいいつでも それは、我々は戻っての質問は、私が思うに、PSET 0のセクションのやり方をやっている、16進数を意味します これは、バイナリ、16進小数に変換するなど、ウォームアップエクササイズを行うだけであった。 進、ちょうど人間の慣例により、通常のポインタを表すために使用され または、より一般的には、対処しています。それは、単に慣習的なやり方です それは読んで少し楽だから、それは、小数のようなものよりも少しコンパクトだ ほとんどの人間が使用するために、バイナリは無意味です。 だから今、これはどういう意味ですか？無効な書き込みがあるようにまあ、それは見える memory.cのの21行目の大きさ4。 それでは、21行目に戻りましょう、そして実際に、ここでその無効な書き込みです。 だから、Valgrindは完全に私の手を握ると修正が何であるかを教えするつもりはないが、 それは私が無効な書き込みをやっていることを検出しています。 私はすべきではないことを4バイトに触れている、と明らかにそれは、からだ あなたが指摘したように、私の代わりに、[9] [10]をやって最大限に または[0]または間に何か。 Valgrindので、あなたが今、プログラムを書いている任意の時間を実現 ポインタを使用し、メモリを使用し、mallocをより具体的には、その 間違いなくこの長いを実行する習慣を身につける しかし、非常に簡単にValgrindののコマンドをコピー＆ペースト そこにいくつかのエラーがあるかどうかを確認する。 そしてそれは、あなたが出力を見るたびに圧倒されることでしょう しかし、ただ視覚的にすべての出力を解析し、エラーの言及を参照してくださいかどうかを確認 または警告または無効であるか、または失われた。 あなたのような音がどこかでしくじったことをどんな言葉。 だからあなたのツールキットで、新しいツールだということを悟る。 

今すぐ月曜日に、私たちはここに来る人々の全体の束を持っていた と連結リストの概念を表しています。 そして、我々はどのような問題の解決策としてリンクリストを導入しました？ うん？ [学生の答え、理解不能]グッド。 配列はメモリがそれらに追加することはできません。 あなたはすべてのあなたが得るのサイズ10の配列を割り当てる場合。 あなたが最初にmallocを呼び出した場合は、reallocのような関数を呼び出すことができ、 それはそれの終わりに向かってスペースがある場合は、配列を成長しようとすることができます 誰も使っていないし、そこではない場合、それだけでどこかにあなたに大きな塊を見つけること。 しかし、それは新しい配列にそれらのバイトのすべてをコピーします。 これは非常に正しい解決策のように聞こえる。 なぜこのような魅力的ではない？ 私はそれが動作するわけで、人間はこの問題を解決している。 なぜ我々は、リンクリスト、月曜日にそれを解決しなければならなかったのか？うん？ [学生の答えは、不明朗な]それは長い時間がかかることがあります。 まだ別の1つですあなたは、mallocやrealloc又はcalloc関数を呼び出して、実際には、いつでも、 いつでもあなたは、プログラムは、オペレーティング·システムと接続している あなたは、プログラムが遅くなってしまう。 あなたがループ内で物事のこれらの種類をやっていると、あなたは本当に物事を遅くしている。 あなたは、 "hello world"のタイプのプログラムの最も簡単のためにこれを気付くするつもりはない しかし、はるかに大規模なプログラムでは、メモリのために何度も何度も、オペレーティング·システムを求めて または何度も何度もそれを還元することは良いことしない傾向にある。 プラス、それは単に知的なものだ - それは時間の無駄だ。 新しい配列にすべてをコピーして、より多くのメモリを割り当てることがなぜ、リスク、 あなたが実際に必要なだけのように多くのメモリを割り当てることができ、代替がある場合は？ だからここでプラスとマイナスがあります。 長所の一つは、今我々が活力を持っているということです。 メモリのチャンクが自由であることである場合は関係ありません、 私はただのポインタを介してこれらのパン粉を作るの並べ替えることができます 一緒に私の全体のリンクリストを文字列に変換します。 しかし、私は、少なくとも一つの料金を払っています。 

私は、リンクされたリストを得ることにあきらめなければならないのですか？ うん？ [学生の答え、理解不能]グッド。 あなたがより多くのメモリを必要としています。今私は、これらのポインタのためのスペースが必要 そして、この超単純なリンクリストの場合には わずか4バイトの整数を格納しようとしていることを、私たちは言い続ける よく、ポインタは4バイトなので、今私は文字通り倍増しました 私はちょうどこのリストを保存するために必要なメモリの量。 しかし、再び、これはコンピュータサイエンスの一定のトレードオフです 時間と空間と開発の間、労力、およびその他のリソース。 リンクリストを使用して別の欠点は何ですか？うん？ [学生の答えは、不明朗] グッド。アクセスするのは容易ではない。我々は、もはや活用でき 分割統治のような週は0原則。 より具体的には、二分探索。そのためにもかかわらず、私たち人間 このリストの真ん中がどこにあるか大体見ることができ、 コンピュータは、このリンクリストは、最初に呼び出されたアドレスで開始したことを知っています。 そして、それが0x123またはそのような何かです。 とプログラムの唯一の方法は、中央の要素を見つけることができます 実際に全体のリストを検索することです。 そしてその時でさえ、それは文字通り全体のリストを検索する必要があるため、 でも、一度は、ポインタを辿ることによって、中間要素に到達 あなたは、プログラムは、潜在的には、このリストがどれくらい長いか見当がつかない あなたはそれの端を押すと、あなたはどのようにプログラムで知ってまで、 あなたがリンクリストの末尾だということ？ 特別なNULLポインタので、再度、規則があります。 このポインタを使用するのではなく、我々は間違いなく、それがいくつかのゴミ値になりたくない どこかでステージを降り、ポインティング、我々はそれがNULLハンドダウンになりたい、 それが終わるところ我々が知っているように、我々は、このデータ構造では、この末端を持つように。 

我々はこれを操作したい場合はどうなりますか？ 我々は、この視覚のほとんどを行なったし、人間と しかし、私たちが挿入を行いたい場合はどうなりますか？ だから、元のリストは9、17、20、22、29、34であった。 我々はその後、数55、それのためのノードのためにmalloc関数空間にしたかった場合はどうすればよい その後私たちは月曜日に行ったのと同様にリストに55を挿入したいですか？ どのように我々はこれを行うのですか？まあ、アニタが来て、彼女は基本的にリストを歩いた。 彼女は次、次、次、次、次の後、最初の要素から開始しました。 最後に左側のすべての方法ダウンを打つ とまあ、これがNULLだと気づいた。ポインター操作が行われるために必要なだから何？ 端にあった者が、番号34は、彼の左手を上げに必要な 55を指すように、55は新しいNULL終端であることが下を向いて自分の左腕を必要としていた。完了しました。 ソートされたリストに55を挿入することは非常に簡単。 そしてこれはどのように見えるかもしれません？ 

私が先に行くと、ここでいくつかのコード例を開いてみましょう。 私はgeditを開くと、私は最初の2つのファイルを開いてもらおう。 一つはlist1.hであり、私はちょうどこのコードの塊であったことを思い出させる 我々はノードを表すために使用すること。 ノードは、リスト内の次の事を指すのみその次のいわゆるNと呼ばれるintとポインタの両方を持っています。 つまり、hファイルに今ある。なぜですか？ 、そこにこの大会だし、我々は、この膨大な量の自分自身を利用していない printf関数と他の関数を書いたが、人 stdio.hという名前のファイルを作成することによって、世界への贈り物として、これらの機能のすべてを与えた。 その後string.hであり、その後map.hはあり、これらのすべてのhファイルはあり あなたが他の人によって書かれた期間中に見られるか、または使用された可能性がある。 通常、これらのインチhファイルのtypedefのような唯一のものです またはカスタム型や定数の宣言の宣言。 あなたは、ヘッダファイルで関数の実装を入れてはいけません。 あなたは、代わりに、ちょうど彼らのプロトタイプを置く。 あなたは、彼らが必要なものを世界と共有したいものを置く 自分のコードをコンパイルするために。だから、この習慣を身につけるために、 私たちは同じことを行うことを決めた。 、list1.hではあまりなさそうだ しかし、我々は世界の人々に興味を持ってもらえるかもしれない何かを入れてきた 誰が私たちのリンクリストの実装を使用したい。 さて、list1.cで、私はこの全部を通ることはありません それは少し長いですので、このプログラムが、のプロンプトですぐにそれが本当の実行してみましょう。 私はその後、list1に実行してみましょう、私は、list1にコンパイルしてみましょう、と何が表示されますです 我々はここでシミュレートされたシンプルで小さなプログラムをしました それは私がリストに番号を追加したり削除したりできるようになるだろう。 だから私は先に行くと、メニューオプション3に3を入力してみましょう。 私は番号を挿入したい - レッツ9であった最初の数字は、何 そして今、私は、リストは現在9ですと聞いています。 私が先に行くと、別の挿入をやってみましょう、そう私は、メニュー·オプション3を打った。 何番私が挿入したいのですか？ 17。 入力します。そして私はちょうど1つのより多くをするつもりだ。 私は22番を挿入してみましょう。 だから我々は、我々は少し前にスライド形式で持っていたリンクリストの始まりを持っています。 この挿入は、実際にはどのように起きているのか？ 確かに、22はリストの最後になりました。 物語のように、我々は月曜日にステージ上で言って、ちょうど今recapped 実際にコードで何が起こっている必要があります。 のは、見てみましょう。私は、このファイル内で下にスクロールしてみましょう。 我々は、いくつかの機能をごまかすよ しかし、我々は、下に行くと言う、insert関数があります。 

我々は、このリンクリストに新しいノードを挿入取り掛かる方法を見てみましょう。 リストはどこで宣言されている？まあ、みましょう、一番上にあるすべての道を上にスクロール と私のリンクリストは、基本的に初期値がNULLである単一のポインタとして宣言されていることに気づく。 だから私は、一般的に我々は説教に対してきたここにグローバル変数を使用しています それは維持するためにあなたのコードが少し厄介になるので、 それは怠惰な、通常のようなものだが、それは怠惰ではない、それは間違っていないですし、それは悪くはない 生活の中であなたのプログラムの唯一の目的は、1つのリンクリストをシミュレートすることである場合。 それは我々がやっているかを正確になります。 だからではなく、メインでこれを宣言し、すべての関数に渡すために持っているよりも 我々はこのプログラムに書いた、私たちの代わりに、ああ、ちょうどそれをグローバルに実現してみましょう このプログラムの全体の目的は、1つだけリンクされたリストを実証することであるので。 だから、それは大丈夫な感じ。ここに私のプロトタイプがあり、我々は、これらのすべてを通ることはありません しかし、私は削除機能、検索機能、インサート機能、traverse関数を書いた。 しかし、今度は、insert関数に戻ってダウン手放す 、この1つはここに様子を見てください。 インサートは、ライン上にある - ここに私達は行く。 挿入します。私達が頼むつもりのでだから、任意の引数を取りません 彼らは挿入したい数字には、この関数の内部ユーザー。 しかし、最初に、我々は彼らにいくつかのスペースを与えるために準備をします。 これは、他の例からのコピー＆ペーストのようなものです。 その場合、我々はintを割り当てていたが、この時間は、我々はノードを割り当てています。 私は実際にノードがどのように多くのバイトを覚えていないが、それは大丈夫です。 sizeofは私のためにそれを把握することができます。 そして、なぜ私は、ライン120でNULLをチェックするのですか？ 119行目で間違って行くことができるか？うん？ [学生の答えは、不明朗] グッド。ちょうど私はあまりにも多くのメモリを要求してきたそうであるかもしれません か何かの間違った、オペレーティング·システムは、私を得るために十分なバイトがありません ので、それはNULLを返すことによって、できるだけ多くの信号を送り、私はそれをチェックしない場合 と私はただやみくもにアドレスが返さ使用に進み、それはNULLである可能性があります。 これは、いくつかの未知の値にすることができ、そうでない限り、私は良いこと -  実際に未知の値ではありません。それはNULLかもしれないので、私はしたくない それを乱用し、それを間接参照するリスクへ。 その場合、私はちょうど戻って、私はまったく記憶を取り戻すなかったように私たちはふりをします。 

そうでなければ、私は、ユーザーが私に挿入するための番号を教えて教えて、私は、私たちの古い友人getIntを呼び出す そして、これは私たちが月曜日に導入された新しい構文であった。 'NEWPTR-> n'はあなたがmallocで与えられたアドレスを取ることを意味します これは、新しいノードオブジェクトの最初のバイトを表します その後、Nという名前のフィールドに移動します。 少しトリビアの質問：これは、コードのどのより不可解なラインと同等ですか？ 他にどのように私はこれを書いたのだろうか？刺しを取るしたいですか？ [学生の答えは、不明朗] グッド。 。nを使用しますが、それはこのように非常に簡単ではない。 私が最初に何をする必要がありますか？ [学生の答えは、不明朗] グッド。私は* newptr.nを行う必要があります。 だから、これは新しいポインタが明らかにアドレスだと言っています。なぜですか？ ので、それはmallocによって戻されました。 "そこに行く"と言って*のNEWPTR あなたがそこにいるに一度、その後、あなたは、より身近にnを使用することができます しかし、これは単に私たち人間がしようとしている場合は特に、少し醜い 矢印付きポインタのすべての時間を描く、世界は、この矢印記法を標準化している、 これは、正確に同じことをします。 左のものはポインタであるときに>表記 - だからあなただけを使用します。 それは実際の構造体の場合、そうでない場合は、、。nを使用します。 そして、この：なぜ私はNULLにNEWPTR->次の初期化するのですか？ 私たちは、ステージの最後のダングリング左手オフをしたくない。 我々は、このリストの終わりを意味する、それがまっすぐ下を向いて欲しい 潜在的には、このノードにさらされる可能性がありますので、私たちはより良い、それがNULLであることを確認してください。 そして、一般的には、あなたの変数またはデータメンバと構造体を初期化する 何かにちょうど良い習慣です。 ただゴミが存在し、一般的に存在し続けるさせるとおかしくなるあなたを取得 あなたは、後で何かを忘れてしまった場合。 

ここでは、いくつかの例です。これは、再び、insert関数であり、 変数が最初に呼び出された場合、私がチェックまず最初に、ある そのグローバル変数がNULLである場合、それがリンクされたリストがないことを意味します。 我々は、任意の数字を挿入していないので、それはこの現在の番号を挿入するのは簡単なことです リストには、それだけでリストの先頭に属しているため。 だから、これはアニタはちょうどふりをして、一人でここに立っていたときだった 我々はノードを割り当てまで、誰も、ここでステージに上がってませんでした それから彼女は、初めて彼女の手を上げることができる 他の皆は月曜日に彼女の後ステージに上がって来ていた場合。 今ここに、これは私が言わなければならない小さなチェックである場合、nの新しいノードの値 、現在の最初のノードのnの値を<されている それが始まったのリンクリストがあることを意味します。 そこにリスト内の少なくとも1つのノードには、ですが、この新しい男 その前に属しているので、私たちは周りのものを移動する必要があります。 リストが単にで始まっている場合に他の言葉で、としましょう​​、 だ単に番号17は、 - 実際に、我々はより明確にこれを行うことができます。 我々は、最初に呼び出さここポインタ、との話を開始した場合 と最初は、それはNULLだし、我々は9番を挿入 9番は明らかにリストの先頭に属します。 だから我々は単にアドレスや番号9をmallocされ、ここでそれを置くふりをしてみましょう。 第一は、デフォルトでは9である場合は、我々が議論して最初のシナリオはただ、ここにしてみましょうポイントこの男を意味する NULLとしてこれを残して、今、私たちは9番を持っています。 我々は挿入する次の番号は17です。 17はこっちに属しているので、私たちはこれを通じて、いくつかの論理的なステップを行う必要があるとしている。 我々は、のは、我々は8番を挿入したいと考えてみましょうそれを行う前に、代わりにしてみましょう。 

だから、便宜上、私はここで描くつもりです。 しかし、覚えて、malloc関数はほとんどどこにでも置くことができます。 しかし、描画のために、私はそれをここに置くことにしましょう​​。 だから、僕は8番のノードを割り当てたふり、これはデフォルトではNULLです。 何が今起こっていますか？物事のカップル。 我々は、我々がこのようなポインタを更新した月​​曜日、ステージ上でこのミスを犯した 次にこれをしなかったし、我々は主張して - 私たちはステージ上で皆を孤立。 あなたはマストアイテムなので - ここで操作の順序は、重要である 今ので、我々は宇宙空間に浮いているの一種であるこのノード9を失ってしまった。 だから、これは月曜日に正しいアプローチではありませんでした。 私たちは最初に何かをしなければならない。 世界の状態は次のようになります。当初、8が割り当てられました。 何が8を挿入するのは良い方法でしょうか？ 代わりに、最初にこのポインタを更新するのでは、だけではなく、ここで、このいずれかをアップデートしてください。 だから我々は、このNULL文字を回すために起こっているコード行を必要とする ノード9で指している実際のポインタに、 それから私達は無事にここにこの男を指すように、最初の変更ができます。 今、私たちは2つの要素を持つリスト、リンクリストを持っています。 そして、これは実際にここに、どんな風に見えますか？ 我々はコードを見れば、私はまさにそれをやったことがわかります。 私はNEWPTR言ってきたが、この物語の中で、NEWPTRはこの男を指さした。 

だから私は、もう一つのことを描いてみましょう、と私はこれのために少しより多くの部屋を残しているはずです。 だから小さな図面をお許しください。 この男はNEWPTRと呼ばれています。 ちょうど25の上方に - それは我々が並んで、数行前に宣言された変数です。 そして、それは8を指している。だから私は、構造体に行く意味NEWPTR->次の、と言うとき NEWPTRによって指されているということなので、ここで我々は、そこに行くされています。 その後、矢印次のフィールドを得ると言っているし、次に=があり、何が値入れて言ってるの？ 最初にあったもの値;第一にあった値はありますか？ 最初は、これは今では、このノードを指し示すべきであることを意味するように、このノードを指していた。 言い換えれば、何が、私の筆跡とはいえとんでもない混乱に見える ちょうど周りにこれらの矢印を移動するシンプルなアイデアは何ですか ちょうどこの1ライナー付きコードへの変換を行います。 次のフィールドの最初にあるものを格納して、その第一が実際に何であるか更新します。 、のはこの一部を進んで、早送りに行こう そして今のところ、このテール挿入だけを見る。 私はいくつかのノードの次のフィールドがNULLであることを見つけるポイントになると仮定します。 そして物語は、詳細にこの時点で私は終わっていることに光沢 私はライン142、先行ポインタここで別のポインタを紹介してきたということです。 本質的には、物語の中で、この時点で、一度リストが長くなり、 私は一種の2本の指を使って歩く必要がある私は、あまりにも遠くに行く場合があるため、 単一長リストで覚えて、あなたは後方に行くことはできません。 だからpredptrのこの考え方は、私の左指で、NEWPTR  -  NEWPTRません。 ここに別のポインタは、私の他の指である、と私はちょうどリストを歩くようなものだ。 それが存在する理由です。しかし、ここだけ簡単なケースのいずれかを検討してみましょう。 そのポインタの次のフィールドがNULLの場合、論理的な含意は何ですか？ このリストをトラバースしている場合は、NULLポインタを打つ？ あなたは、リストの最後にしている、などのコードは、この一つの追加要素を追加する 直感的な一種のは、その次のポインタがNULLである場合、そのノードを予定されている ので、これは現在NULLで、新しいノードのアドレスになるように、しかし、それを変更してください。 だから我々は、ちょうど我々が誰かの左手を上げることにより、ステージ上に描いたコード内の矢印を描画している。 

そして、私は今のところで私の手を振るだろうという場合、 私はそれが我々がこの種類の環境でそれを行うときに迷子になるのは簡単だと思うからといって、 リストの途中に挿入するためにチェックしています。 しかし、単に直感的に、あなたが把握したい場合にどうする必要があるもの いくつかの番号が真ん中に属する場所あなたがそれを歩かなければならないということです 複数の指を持つ、複数のポインタ、 検査によってそれが属する場所を見つけ出すには、要素<現在の一つです >現在の1、そして一度は、その場所を見つける その後、あなたは非常に慎重にポインタを動かしどこシェルゲームのこの種のことを行う必要があります。 そしてその答えは、あなたが自分で自宅でこれを通じて理由をご希望の場合は、 ただ、次の2行のコードに帰着するが、それらの行の順序は超重要です。 あなたが誰かの手をドロップすると、間違った順序で誰か他の人を上げる場合があるため、 もう一度、あなたはリストを孤立化してしまう可能性があります もっと概念的に要約すると、末尾に挿入は比較的簡単です。 先頭に挿入も比較的簡単である、 しかし、あなたは追加のポインタにこの時間を更新する必要があります ここにリストに番号5を圧迫する、 その後途中で挿入がより一層の努力を伴う、 非常に慎重に、その正しい場所に番号20を挿入する これは、17と22の間です。 ですから、22に新しいノード20ポイントを持っているように何かをする必要があり、 その後、ノードのポインタは最後に更新される必要がある？ それは実際にそれを挿入するには、17です。 だからもう一度、私はその特定の実装の実際のコードを延期します。 

一見すると、それは少し圧倒的だが、それは本当に無限ループだ それは、ループループ、ループ、ループ、あなたはNULLポインタを打つとすぐに壊している その時点で、あなたは必要な挿入を行うことができます。 これは、その後、代表的な連結リストの挿入コードです。 、それは多くのようなものだった、と我々は一つの問題を解決したような気が しかし、我々は全体の他の1を導入しました。率直に言って、我々はこのすべての時間を費やしてきた ビッグOとΩ上、より迅速に問題を解決しようと、実行時間、 そしてここで我々は後方に大きな一歩を取っている、それは感じている。 そして、まだ、ゴール、データを格納する場合、 我々は月曜日に言ったようにそれは、聖杯のように感じて、本当になる 瞬時に物事を格納する。 

実際には、我々はしばらくの間はさておきリンクリストを作りましたと仮定 そして我々はその代わりに、テーブルの概念を導入しました。 そして、ちょうど配列として一瞬テーブル考えるてみましょう。 この配列は、この場合には、ここでいくつかの26要素、25 0〜を持っています そしてあなたが名前のストレージの塊を必要としていると仮定します。 アリスとボブとチャーリーなど。 そして、あなたはそれらの名前を格納するためにいくつかのデータ構造を必要としています。 さて、あなたはリンクリストのようなものを使用することができます そしてあなたは、などの後にボブボブとチャーリーの前にアリスを挿入するリストを歩くと、可能性があります。 そして、実際には、あなたはさておきとして、そのようなコードを見たい場合は、 list2.hでは、我々はまさにそれをやることを知っている。 我々は、このコードを通ることはありませんが、これは最初のサンプルの変形 それは、我々が呼ばれる学生の前に見てきたもう一つの構造を紹介します その後どのように処理し、実際にリンクされたリストに格納すると、学生の構造体へのポインタである むしろより単純で小さな整数n。 だから、実際の文字列を含むそこにコードがあり実現 しかし手元にある目標は、本当に今効率の問題を解決するためであれば、 我々はアリスと呼ばれるオブジェクトを与えている場合、それはいいのではないでしょう、 我々は、データ構造内の正しい場所に彼女を入れたい それだけでアリスを置くために本当にいいだろうと思うようにそれは感じている、 名前は最初の場所で、始まります。 名前は第二の位置では、Bから始まり、ボブ、。 配列を使用して、または、それをテーブルに、その時点でハッシュテーブルを呼び出してみましょう 我々は正確にそれを行うことができます。私たちは、アリスのような名前を与えられた場合、 アリスのような文字列は、-L-I-C-Eを入れますか？ 我々はhueristicを必要としています。私たちは、アリスのようないくつかの入力を取得する関数が必要 と答えを返し、 "アリスはこの場所に置いてください。" そして、この関数は、このブラックボックスは、ハッシュ関数と呼ばれようとしています。 

ハッシュ関数は、 "アリス"のように、入力を受け取り、何か 一般的にあなたへと戻り、アリスが属するいくつかのデータ構造内の数値場所。 このケースでは、我々のハッシュ関数は比較的簡単であるべきです。 私達のハッシュ関数を使用すると、文字私は気にしなければならない "アリス"を、与えられている場合、と言うべきでしょうか？ 最初の1つ。だから私は、[0]を見て、それから私は[0]の文字がある場合は、数字の0を返すと言う。 それはBさんの場合は、1を返します。それはCの場合は、等2を返す、と。 すべて0のインデックス、と私はアリスとボブその後を挿入できるようになるとその後チャーリーなど このデータ構造に変換します。しかし、問題はそこだ。 アニタが再び一緒に来る場合はどうなりますか？ 我々は、アニタはどこに置けばいいの？彼女の名前は、あまりにも、文字で始まる 我々はこの問題のさらに大きな混乱を作ったように、それは感じている。 現在のデータ構造体に即時の挿入、一定時間の挿入を、持っている むしろワーストケースより線形、 しかし、我々は、このケースではアニタで何ができる？ 実際には、2つのオプションは何ですか？うん？ [学生の答え、理解不能]わかりましたので、私たちは別の次元を持つことができます。 それは良いことだ。だから我々は、我々は月曜日に口頭での話のように3Dで物事を構築することができます。 我々はここで別のアクセスを追加しますが、全く、私は、これは単純にしようとしていると仮定することができなかった。 ここで全体の目標は、当面一定時間のアクセスを持つことである そう、それはあまりにも多くの複雑さを追加しているところ。 このデータ構造にアニタを挿入しようとし、他のオプションは何ですか？うん？ [学生の答え、理解不能]グッド。だから我々は、ダウンしてみんなを動かすことができる 彼女が本当になりたい場所その後チャーリーボブとアリス、ダウングリグリと同じように、我々はアニタを置く。 

もちろん、今、これの副作用があります。 このデータ構造は、我々はかつて人々を挿入する必要がないので、おそらく便利です しかし、我々は彼らが後でそこにいるかどうかを確認したいので、 我々はデータ構造のすべての名前をプリントアウトしたい場合。 我々は最終的に、このデータを使って何かをやろうとしている。 だから今我々は一種の彼女がすることになっている場所はもはやませんアリス、上にねじ込まれました。 またボブです、また、チャーリーです。 だから多分これは、このような良いアイデアではありません。 しかし、確かに、これは1つのオプションです。我々は、誰もシフトダウンができる または一体、アニタがゲームに遅れて来て、なぜ我々はちょうどアニタを入れてはいけません ここではなく、ここではなく、ここではなく、リストだけで少し低い彼女を入れてみましょう。 しかし、その後、この問題が再び委譲を開始します。 あなたは彼女の最初の名前に基づいて、瞬時にアリスを見つけることができるかもしれない。 と瞬時にボブとチャーリー。しかし、あなたは、アニタ探す そしてあなたはうーん、見、アリスが邪魔になります。 まあ、私はアリスの下をチェックしましょう​​。ボブはアニタではありません。 チャーリーはアニタではありません。ああ、アニタがあります。 そして、あなたは論理のその列車のすべての方法を継続する場合、 この新しいデータ構造の中に見つけたり、アニタを挿入するの最悪実行時間は何ですか？ それは右、O（n）のですか？ 最悪のケースであるため、アリス、ボブ、チャーリーはそこだ。 。 。 ダウンして、 "Y"という名前の人にすべての方法なので、残された唯一つのスポットがあります。 ありがたいことに、私たちは "Z"と呼ばれる人がいませんので、一番下にアニタを置く。 

私たちは本当にその問題を解決していない。 だから多分、我々はこの三次元を導入する必要もありません。 我々はこの三次元を導入しない場合、それは、結局 我々は完全にこれを行うことはできませんが、聖杯は、取得しようとしている 一定時間の挿入と動的挿入するよう 我々は、サイズ26のハードコード配列する必要はありません。 私たちが望むように我々は多くの名前のように挿入することはできますが、みましょうここで我々の5分の休憩を取る し、適切にそれを行う。 かしこまりました。私はそこにかなり人為的に物語を設定 アリスとボブその後、その後チャーリーその後アニタを選択して 名前は明らかにアリスと衝突するつもりだった。 しかし、我々は月曜日に終了した質問は、それがどれだけ可能性が高いです あなたは、これらの種類の衝突を得るだろう？言い換えれば、 我々は、この表の構造を使用して起動した場合、それは、実際には単なる配列です。 26ヶ所のこのケースでは、 私たちの入力が代わりに一様に分布している場合はどうでしょうか？ それは、人工的にアリスとボブとチャーリーとDavidはないなどアルファベット順に それは一様にZまでにわたって配布されている 

多分、我々はちょうど幸運を得るだろうし、我々は2つ​​のまたは2つのBのを持っているつもりはない 非常に高い確率で、誰かが指摘したように、 0から25までを行い、我々にこの問題を一般化していない場合 しかし、言う、364または65を介して0、多くの場合、典型的な年の日数、 との質問をし、 "この部屋に私達二人が同じ誕生日を持っている確率は何ですか？" それを別の言い方をすれば、確率は私たち二人で始まる名前を持っていることは何ですか？ 質問のソートは、同じですが、このアドレス空間 このサーチスペース、誕生日の場合には大きく、 我々は、アルファベットの文字よりも年間で非常に多くのより多くの日を持っているからです。 衝突の確率は何ですか？ さて、私たちは数学の反対の方法を考え出すことによってこれを考えることができます。 無衝突の確率は何ですか？ さて、ここで、この式は、何が確率だと言う 彼らはユニークな誕生日を持っているこの部屋に一人だけは、あったら？ それは100％だ。そのため部屋の中で一人だけがある場合、 彼または彼女の誕生日は一年のうち365日のいずれかになります。 365/365だからオプションは私に1の値を与えます。 だから、現時点では問題になっている確率はちょうど1である。 しかし、部屋の中で二人目があったら、 自分の誕生日が異なる確率は何ですか？ のみ364可能日は、うるう年は無視し、そこ 自分の誕生日のために他の人と衝突しないように。 だから、365分の364。第三者が入ってくるなら、それは365分の363だ、など。 だから我々は、ますます小さくなっている、これらの画分を掛け合わ保つ 把握するために私たちのすべてがユニークな誕生日を持っている確率は何ですか？ しかし、その後、私たちは、もちろん、ただその答えを取得し、それを周りに反転することができます すべてのことを行うとマイナス1、我々は最終的には買ってあげる表現 あなたは数学の本の背中を覚えていれば、それは、このような小さなものになります それははるかに簡単にグラフィカルに解釈されます。 そしてここでこのグラフィックは、x軸上に誕生日の数を持っています や誕生日を持つ、とy軸上の人々の数が一致する確率です。 そして、何これは言っていることは、あなたが持っている場合であっても、としましょう​​ということです 22のような何か、23を選択してみましょう。 部屋の中で22または23の人があるとすれば、 これらの非常に少数の人々の2つが同じ誕生日を持っているとしている確率 コンビナトリアルに、実際に超高い。 わずか22人のクラスで、その50％の確率、セミナー、事実上、 それらの人々の2は同じ誕生日を持っているとしている。 ために、同じ誕生日を持つことができるので、多くの方法があります。 さらに悪いことに、あなたはチャートの右側を見れば、 あなたがそれで58の生徒とクラスを持っている時間によって、 2人が誕生日を有する確率は、スーパー、超高、ほぼ100％です。 さて、それは現実の生活に関する面白い事実のようなものだ。 

データ構造と情報を格納するための今でも影響、 ちょうどあなたがデータの素敵な、きれいで、均一な分布を持っていると仮定することを意味 そしてあなたは、物事の束に合わせて十分な大きさの配列を持っている あなたはユニークな場所で人々を取得するつもりだという意味ではありません。 あなたは、衝突を持っているつもりです。 、それが呼ばれるように、ハッシュのこの概念は、そう "アリス"のような入力を取って、それを何らかの方法でマッサージ その後0または1または2のような答えを取り戻す。 その機能からいくつかの出力を取り戻すが、衝突のこの確率に悩まされています。 それでは、どのように我々はそれらの衝突を扱うことができますか？ まあ、1ケースに、我々は、提案されたアイデアを取ることができます。 私たちはただ、もう少し単純に、多分誰もシフトダウンしたり、することができます のではなく、みんなを移動させ、ちょうど利用できるスポットの底にアニタを動かしてみましょう。 アリスが0になっているので、もし、ボブが1である、チャーリーは、2である 私達はちょうど場所3でアニタを置くことにしましょう​​。 そして、これはプロービング線形と呼ばれるデータ構造内のテクニックです。 あなただけのこのラインを歩いていると、あなたはソートのプロービングしているので、線形 データ構造で使用可能なスポットに。 もちろん、これはO（n）に委譲。 データ構造が本当にいっぱいある場合、それは25人が、すでにある その後アニタが登場し、彼女が位置Zがどうなるかで終わる、それは大丈夫です。 彼女はまだフィットし、我々は後に彼女を見つけることができます。 

しかし、これは物事をスピードアップすることを目的に反していた。 我々はその代わりに、この第三の次元を導入しましたので、どうでしょう？ その技術は、一般的にはセパレートチェーンと呼ばれる、またはチェーンを抱えている。 とハッシュテーブルは、この表の構造は何です、 あなたのテーブルはちょうどポインターの配列です。 しかし、どのようなこれらのポインタが指すことは推測は何ですか？ リンクリスト。我々はこれらの世界の両方の長所を取るので、どうでしょう？ 我々は最初のインデックス用配列を使用 データ構造の中に私たちは瞬時に、[1]、[30]またはなど[0]に行くことができます しかし私たちは、ある程度の柔軟性を持っていると我々はアニタとアリスとアダムを収めることができていること と他の名前、 我々はその代わりに他の軸を任意に増やせてみましょう。 そして、我々は最終的に、月曜日の時点では、リンクされたリストでその表現力を持っています。 我々は、任意のデータ構造を成長することができます。 代わりに、私達はちょうど、巨大な2次元配列を作ることができる しかし、それは2次元配列の行のいずれかの場合にひどい状況になるだろう 名前がAで始まるたまたま追加の人のために十分な大きさではない 禁じる神我々は巨大な2次元構造を再割り当てする必要があります 名前のように多くの人々が、そこにという理由だけ Zの何という名前のように少数の人々がある場合は特に。 それだけで非常に希薄なデータ構造になるだろう。 だからそれは決して完璧ではないが、今、私たちは、少なくとも能力を持っている アリスやアニタが属するところ瞬時に検索するには、 少なくとも縦軸の観点から、 それから私達はちょうどこのリンクリストにアニタまたはアリスをどこに置くかを決めなければなりません。 我々は物事を分類する気にしないのであれば、どのように迅速に私たちは、このような構造にアリスを挿入することができる？ それは一定の時間です。 WE [0]に、そして誰の存在であれば、へのインデックス アリスは、そのリンクリストの先頭になります。 しかし、それは大きな問題ではありません。アニタは、その後に沿って来る場合があるため 手順のいくつかの番号以降、アニタはどこに属しますか？ さて、[0]。 OOP。アリスは、そのリンクされたリストに既にある。 

しかし、我々はこれらの名前を並べ替える気にしない場合、 私達はちょうどアリス以上、挿入アニタを移動できますが、でもそれは時定数である。 アリスとアダムとのすべてのこれらの他の名前は、そこだとしても それは実際に物理的にそれらをずらしていない。なぜですか？ 私達はちょうど知っているリンクリストと一緒にここにいたので、これらのノードはとにかくアールたか？ あなたがしなければならないのは、パン粉を移動することです。 周りに矢印を移動し、あなたは物理的に周囲に任意のデータを移動する必要はありません。 だから我々は即座に、その場合には、アニタを挿入することができます。時定数。 だから我々は一定時間のルックアップ、およびアニタのような誰かの定数時間挿入しています。 しかし、世界し過ぎのようなもの。 我々は後でアリスを見つけたい場合はどうなりますか？ 我々は後でアリスを見つけたい場合はどうなりますか？ どのように多くの手順を実行することは取るつもりですか？ [学生の答えは、不明朗] その通りです。リンクリストの国のアリスの前に人々の数。 我々のデータ構造は、再び、この縦のアクセスを持っているので、だからそれは、非常に完璧ではあり​​ません そして、それがぶら下がってこれらのリンクされたリストを持っています - 実際には、うまくいくよう配列を描画しないようにしましょう​​。 それは、これらのリンクされたリストは、このような少し何かしているように思えてそれをオフにぶら下がっています。 しかし、問題はあるかアリスとアダムと、これらのすべての他の名前 、あそこにますます終わる 誰かがステップの束を取ってしまう可能性を見つける、 は、リンクリストを横断しなければならないbcause これは、線形動作です。 だから本当に、その後、挿入時間は、最終的には、nはリスト内の要素の数はO（n）です。 で割って、任意に、mはリンクリストの数がm、呼び出してみましょう 我々は、この縦軸に持っている。 言い換えれば、我々は本当に名前の一様分布を仮定した場合、 全く非現実的。他の人よりも、いくつかの文字の多くは明らかにありま​​す。 

しかし、我々は一瞬一様分布と仮定した場合、 そして我々は全人口をN、およびメートル総チェーンた これらの鎖の各々の長さは、次に私達に利用できる かなり単純合計は、n鎖の数で割ったものになるだろう。 ので、n / mである。我々はすべて数学的に巧妙なことができますどこでも、ここだ。 これらの固定数があるので、mは定数である。 あなたは、冒頭で配列を宣言するつもりだ そして我々は、サイズ変更縦軸をしていない。定義によって、それが固定されたままになります。 それは変化だという、いわば、横軸のみです。 したがって、厳密には、これは一定である。だから今は、挿入時間 かなりO（n）である。 だからそれはすべてそのはるかに良い感じがしない。 しかし、真実はここに何ですか？まあ、すべてのこの時間、週間、 私たちは言ってきたはO（n²）である。 O（n）で、2×nの²、 -  nは、2で割った値です。 。 。 ECH。 それはちょうどn個の²のだ。しかし、今、学期のこの部分では、 我々は再び現実の世界の話を始めることができます。 とn / mはちょうどn個だけの場合よりも絶対的に速くなります。 あなたは千の名前を持っていて、複数のバケットにそれらを分割する場合 あなたは、これらの鎖の各々の唯一の10名を持つように 絶対に10の事を検索すると、千の事よりも高速であることを行っている。 それで、今度の問題セットの一つがあなたに挑戦しようとしている まさにそのことについて考えることにもかかわらず、ええ、 漸近的に、数学的に、これはまだほんの線形であり、 物事を見つけようとするときには、一般的に吸う。 現実には、それよりも速くなるだろう このため、除数の。 それで、もう一度、このトレードオフがあるように起こっている 理論と現実の間に、この紛争、 とノブの1学期には、この時点で回転を開始します 我々は一種のsemsterの終わりのための準備として、現実1の詳細です 我々は、Webプログラミングの世界を紹介として 本当に、性能、ユーザーがしようとしているので、カウントしようとしている場所 貧弱な設計上の決定を感じ、感謝を開始します。 

だからあなたは、リンクを実装するにはどうすればいい -  31の要素を持つハッシュテーブル？ 前の例では、誕生日について任意であった。 誰かが1月1日または2月1日の誕生日を持っている場合、我々はこのバケツに入れます。 それは1月2日、2月2日、3月2日の場合、我々はこのバケツに入れます。 それは31だったのはそういうわけです。どのようにハッシュテーブルを宣言するのですか？ それは非常に単純なことができ、ノード*テーブルは、[31]それは私の任意の名前です。 これは、ノードにくれ31ポインタを与える そしてそれは私がリンクリストに31のポインタを持つことができます これらのチェインは、最初はNULLである場合でも同様です。 私は、 "アリス"、 "ボブ"、 "チャーリー"を格納する場合は、私は入れて何をしたいのですか？ さて、私たちは構造体にそれらの事をラップする必要があります 私たちは、アリスは、ボブを指すようにチャーリーを指すように、など。必要があるため、 我々は、ちょうど名前だけを持つことができないので、ここでノードと呼ばれる新しい構造を作成することができます。 

実際のノードとは何ですか？この新しいリンクリスト内のノードとは何ですか？ ワードと呼ばれる最初のものは、人の名前です。 LENGTHは、おそらく、人間の名前の最大の長さに関係する 、20が何であれ、30、クレイジーコーナーケースが40文字、 と1は何のためですか？それだけで余分なNULL文字を、\ 0です。 だから、このノードは、自身の内部に "何か"をラップしている それはまた次に呼び出さポインタを宣言しています ので、我々はチャーリーにボブにチェーンアリス缶などという。 NULLを指定することもできますが、必ずしも必要はありません。 これらのハッシュテーブル上で何か質問はありますか？うん？ [質問をする学生、不明朗]配列 - 良い質問。 なぜ、この配列のchar単語だけではなく、char *型は何ですか？ この幾分恣意例では、私は頼らざるをしたくなかった オリジナル名ごとに、mallocへ。 私は、文字列のためのメモリの最大量を宣言したかった ので、私は構造アリス\ 0にコピーして、mallocやfreeなどに対処する必要がなかったこと。 しかし、私は宇宙利用をより意識になりたい場合は、それを行うことができます。良い質問です。 だからこれから一般化してみましょう そしてより一般的にはデータ構造に、今日の残りの部分を集中 と我々は同じファンダメンタルズを使用して解くことができる他の問題 データ構造自体は彼らの細目で異なるかもしれませんが。 

だから、コンピュータサイエンスで判明し、木は非常に一般的です。 そして、あなたは、家系図のようなツリーの一種と考えることができます いくつかの根、またはいくつかの女家長家長は、そこここで、 おばあちゃんやおじいちゃんまたはそれ以前のバック、 その下にママとパパ、または様々な兄弟などです。 だから、ツリー構造は、ノードを持っており、それが子供を持っている 各ノードに対して、通常、0個以上の子。 ここでこの画像に表示されている専門用語の一部と あるエッジに小さな子供や孫のいずれか 誰が、それらから発せなく矢を持っていない それらは、いわゆる葉であり、内側に誰も 内側のノードであり、あなたはそれをそれらの線に沿って何かを呼び出すことができます。 しかし、この構造はかなり一般的です。この1つは少し任意です。 我々は、我々は右側に三人の子供を持って、左の上の1つの子を持つ 底部の2つの子供が残っています。 そこで、我々は、異なるサイズの木を持つことができますが、我々は物事を標準化するために起動した場合 と、以前短いから二分探索でパトリックビデオからリブログ思い出すかもしれない オンラインで、バイナリ検索によって、アレイに実装する必要はありません 黒板上の紙または片。 あなたがより洗練されたデータ構造にあなたの番号を格納したいと仮定します。 あなたはこのようなツリーを作成することができます。 あなたがC言語で宣言されたノードを持つことができ、そのノードは、その中に少なくとも2つの要素を持つことができます。 一つは、あなたが保存したい番号であり、他方が - まあ、我々は1つの多くを必要とする。 他のは、その子である。 だからここでは、別のデータ構造です。この時間は、ノードが数nを記憶するものとして定義されています してから、2つのポインタが、左の子と右の子。 そして、彼らは任意じゃない。この木について興味深い何ですか？ 

我々はこれを広げてきたか、パトリックは彼のビデオでそれをどのようにレイアウトする方法のパターンとは何ですか？ いくつかの並べ替えがここそこで起こっていることは明らかのようなものだ、 しかし、単純なルールは何ですか？うん？ [学生の答えは、不明朗] パーフェクト。この一瞥場合は、左側の小さな数字を参照してください 大きな左の数字が、すべてのノードのために本当のことです。 各ノードに対して、それよりも、その左の子より少なく、それよりも大きく、その右の子。 私はこのデータ構造を検索したい場合はどうすればよいこれが今意味する、と言う、44番ですが、 私は今、なぜならこれらのより複雑なデータ構造のすべてと同様に、ルートから起動する必要があります 我々はまだ始まったばかり、一つのことへのポインタを持っている。 この場合には、初めはrootです。それは、左端ではありません それは、この構造のルートです。だから私はここには55の見て、私は44を探しています。 どの方向に私は行きたいですか？ まあ、私は明らかに、右に大きくなりすぎようとしているので、左に行きたい。 だからここに気付くには、概念的には半分に木をチョッピングの一種だ あなたは、右手側に下って行くことはありませんしているので。 だから今は55から33に行く。それは、数では小さすぎます。 私は44を探していますが、今は44がこのツリーにある場合は、私は右に明らかに行くことができます知っている。 だからもう一度、私は半分にツリー剪定だ。 これは、電話帳に概念的にほとんど同じです。 それは、私たちが黒板に紙でやったことと同じだ それは私たちが実際に行うことができ、より洗練された構造だ これは、分割して、アルゴリズムの設計によって征服 そして実際に、このような構造を横断 - おっと。 それは、 "この道を行くか、その道を行く"だけだ、このような構造を、横断 セクションでそれを実装するときに、最初にあなたの心を曲げすべてのコードを意味します または、再帰または反復を使用して、二分探索のために、自宅でそれを歩く それは、首の痛みです。真ん中の要素を検索し、次に上下にあなたの丸めを行う。 

我々が今再び再帰を使用することができますので、美しさはこれにあります、 しかし、はるかにきれい。確かに、あなたは数55にいて、あなたが44を検索する場合は、 この場合、左に行く、あなたは何をしますか？あなたは正確に同じアルゴリズムを実行します。 次に、あなたが左または右に移動し、ノードの値を確認します。 次に、左または右に行くと、ノードの値を確認します。 これは完全に再帰に適しています。 過去に我々は、再帰を含むいくつかのかなり恣意的な例をやったので、あっても それは、データstucturesと、再帰的にする必要はありませんでした 特に木々、それは、問題を取るのこのアイデアの完璧なアプリケーションです それを縮小してから、同じタイプのが、より小さい、プログラムを解決。 

だから我々は導入することができ、別のデータ構造があります。 この1は不可解に見えるように一目見ただけで設計されていますが、この1つは驚くべきことださ。 だから、これは、単語の検索から継承されトライ、トライ、と呼ばれるデータ構造である これは、再試行-valを宣告されていませんが、それは世界がこれらの事を呼んでいるものだ。しようとします。 T-R-I-E。 それはある種のツリー構造ですが、トライの各ノード どのように見える？略称のようなものだので、これは少し誤解を招くおそれがあります。 しかし、それはこのトライの各ノードが実際には配列であるように見えます。 そして、この図の作者は、それを示していないにもかかわらず、 この場合には、このトライは、その目的は生活の中で単語を格納するデータ構造です。 -L-I-C-EまたはB-O-Bのような。 などと、このデータを格納し、アリスとボブとチャーリーとアニタ方法と それは、トライでアリスを格納することにより、配列を使用しています 我々は、配列のように見えるルートノードから開始 そしてそれは簡単な表記法で書かれている。 それとは名前がなかったので著者はabcdefgで省略。 彼らは唯一のMとPとTを示したが、このケースでは、 の現在のいくつかの名前に離れて、アリスとボブとチャーリーから移動することができます。 マクスウェルは、この図に実際にある。 それでは、どの著者ストアのM-X-W-E-L-Lがした？ 彼または彼女はルートノードから開始され、ので、大体[M] 13は、アレイ内の13番目の場所に行きました。 そこから、ポインタがあります。 別の配列に至るポインタ。 そこから著者は、左上にそこに描かれているように、場所に、その配列のインデックスを作成 それから彼または彼女は、別の配列にそのポインタを追っ と場所Xの部分にポインタに行ってきました その後、次の配列位置W、E、L、Lなど、内 そして最後に、実際にはこれに絵を入れてみてみましょう。 コー​​ド内のノードのような外観とは何でしょうか？ トライのノードは、複数のノードへのポインタの配列が含まれています。 しかし、また、少なくとも、この実装では、ブール値のいくつかの種類があるはずだ。 私はそれis_word呼び出すために起こる。なぜですか？ あなたはマクスウェルを挿入しているときは、挿入していないので このデータ構造には何も。 あなたがXを書いていないしているMを書いていないしている あなたのやっていることは、次のポインタです。 その後、M、表すポインタを表すポインタ その後、その後、X、W、E、L、Lを表すポインタ しかし、何を終わりに行う必要があることは確認して行くの一種ですが、私はこの場所に到達した。 データ構造の中にここで終了という言葉がありました。 

それでは、トライは本当にで満たされ、著者は表現することを選んださ 小さな三角形でこれらterminuses。 本当のこれはただの事実は、この三角形はここにあることを意味し、このブール値 あなたは木で後方に行けば、意味 それはマクスウェルはこれであるという言葉です。 例えばだが、単語fooは、 私は一番上にここにルートノードで起動した場合ので、ツリーに含まれていない 何fのポインタ、ノーoのポインタ、ないoのポインタがありません。 Fooはこのディクショナリの名前ではありません。 しかし、対照的に、チューリング、T-U-R-I-N-G。繰り返しますが、私はtまたはuまたはrまたはiまたはn gのいずれかを格納していなかった。 しかし、私はダウンしてここにこのノードの真の方法の値は、このデータ構造に格納した - ツリーに trueにis_wordのこのブール値を設定することによって。 だからトライは、この非常に興味深いメタ構造の一種である どこにあなたは本当に辞書のこの種の単語自体を格納していない。 明確にするために、あなただけのyesまたはnoを保管していません、ここで終了という言葉があります。 

今すぐ含意は何ですか？ あなたはメモリに保存しようとしている辞書で15万の単語を持っている場合 リンクリストのようなものを使用して、 あなたのリンクリストで15万ノードを持っているとしている。 アルファベット順にそれらの単語のいずれかを見つけることは、O（n）の時間がかかることがあります。 線形時間。しかしトライの今回のケースで、 単語を見つけることの実行時間は何ですか？ それは、ここの美しさはすでにこの辞書で149999の言葉を持っていてもということであると判明 このデータ構造を使用して実装として、 それはアリス、アリスのように、中にもう一人を見つけるか、または挿入することがどのくらいの時間がかかりますか？ まあ、それは末尾の文字のための唯一の5は、多分6つのステップです。 構造体の他の名前の存在する理由 アリスを挿入する方法で取得していません。 また、アリスを見つけ、この辞書に15万の単語があります一度 すべてでアリスを見つけるあなたの方法で取得していません アリスがあるためです。 。 。 。 。ここで、ので、私はブール値を発見した。 全くブール値trueがない場合と、アリスは言葉のこのデータ構造ではありません。 換言すれば、この新しい物事を物事を見つけると挿入の実行時間 トライのデータ構造は、Oである - それは、nではありません。 15万人の存在する国のアリスには効果がありませんので、それは思われる。 だから、kは英語の単語の最大長であるk、呼び出してみましょう これは、典型的には20代の文字に過ぎません。 だから、kは定数である。聖杯ので、我々は今、発見したように見える トライのことは、挿入のため、検索のために、削除のた​​めの時定数である。 すでに構造のものの数があるため、 どちらも物理的に存在しません。繰り返しますが、彼らはちょうどオフにチェックの並べ替えています、yesまたはno、 今後の実行時間に影響を与えません。 

しかし、漁獲量があるはずだ、そうでなければ我々は、そんなに時間を無駄にしなかっただろう すべてのこれらの他のデータ構造についに驚くべき秘密の1を取得します。 だから我々はここでこの偉業を達成するためにどのような価格払っている？スペース。 このことは巨大だ。と理由その著者 ここにそれを提示しなかったが、気付くの配列と同じように見えるこれらの事のすべてが、 彼は、トライの残りの部分をツリーの残りの部分を描画しませんでした 彼らはただストーリーには関係ありませんだから。 しかし、これらのすべてのノードは、超広角であり、ツリー内のすべてのノードが占有 26または実際に、このケースでは、私はアポストロフィのためのスペースを含めていたため27文字かもしれません 私たちはapostrophized言葉を持つことができること。 この場合、これらは広い配列です。それらはpicuturedならないようにもかかわらず、 これは、RAMを大量に占有します。 それは、現代のハードウェアでespecilly、細かいかもしれない それはトレードオフです。我々はより多くのスペースを費やすことによって少ない時間を取得します。 だから、これはすべてどこに行くのですか？ まあ、してみましょう - のがここを見てみましょう。 ここにこの男へのジャンプを行いましょう。 

信じられないかもしれませんが、Cはいくつかの時間が今のあったように同じくらい楽しい、 我々はそれがより現代的なものに移行する時が来学期にポイントに到達している。 より高いレベルで物事。とにもかかわらず、数週間のために 我々はまだポインタやメ​​モリ管理の世界に身を浸すし続けるだろう 我々はその後に構築するために使用できるような快適さを得るために、 終盤は、この言語、皮肉ではなく、最終的に導入することです。 我々は、HTMLの話を10分のように、過ごします。 すべてのHTMLマークアップ言語ですが、どのようなマークアップ言語である 'これは太字に'と言うオープン括弧と閉括弧のこれらのシリーズです この中心を作る 'このイタリック作る'。 ' それはすべてその知的に面白くありませんが、それは便利なスーパーです。 そしてそれは確かに、これらの日遍在だ。 しかし、何を、HTMLの世界についての強力だし、Webプログラミング、より一般的には、 動的なものを構築しています。PHPやPythonやRubyやJavaやC＃のような言語でコードを書く。 本当に、何でも選択した言語であり、動的にHTMLを生成。 動的にCSSと呼ばれるものを生成します。 カスケーディング·スタイル·シート、美学でもあります。 そしてそうにもかかわらず、今日、私は、おなじみのGoogle.comのようないくつかのウェブサイトに行けば と私は、多分あなたが前に行ってきた開発者は、ソースの表示を、表示するために行く しかし、ソースを表示しようと、このようなものはおそらくかなり不可解に見える。 しかし、これはGoogle.comを実装し、基になるコードです。 フロントエンドで。そして、実際にこのすべてがふわふわ美学のものです。 これはここにCSSをアップです。私は下にスクロールしておくならば、我々はいくつかの色分けされたものを買ってあげる。 これはHTMLです。 Googleのコードは混乱のように見えるが、私は実際に別のウィンドウを開く場合 我々はこれにいくつかの構造を見ることができます。 私がこれを開くと、ここで気づく、それはもう少し読みやすい。 我々は、ずっと前にこのタグを見ていくつもりですが、[ワード]タグで、 HTML、頭、体、div要素、スクリプト、テキスト領域、スパン、中心は、div。 そして、これはまた、一見不可解に見えるの一種である しかしこの混乱のすべては、特定のパターン、および再現性のパターンに従います かつて我々は基本を降りるように、このようなコードを書くことができるでしょう として、JavaScriptと呼ばれる別の言語を使用して、このようなコードを操作します。 とJavaScriptは、ブラウザの内部で実行される言語である 我々はGoogleマップで使用されているコースのショッピングツールでは、ハーバード大学のコースで使用することを本日 あなたのダイナミズムの全体の束を与えるために、Facebookは、インスタントステータスの更新を表示することができます Twitterは瞬時にあなたのつぶやきを表示するためにそれを使用しています。 これはすべて我々は自分自身をインチ没頭し始めます しかし、そこに着くために、我々はインターネットについて少し何かを理解する必要があります。 ここでこのクリップは長いわずか数分だけですが、今のところ、これは、実際には、あると仮定しましょう どのようにインターネットが来るについてです何のためのティーザーとして働いています。私は "ネットの戦士たち"をあなたに与える 

[♫スローコーラス音楽♫] 【男性ナレーター]彼はメッセージが付属しています。 プロトコルはすべて彼自身である。 [♫速い電子音楽♫] 彼は、ルータを思いやり、クールファイアウォールの世界に来た 死よりもはるかに悪いと危険。 彼は高速です。彼は強いです。彼は、TCP / IPのだ、と彼はあなたの住所を持っている。 ネットの戦士たち。 [マラン]来週、その後。インターネット。 Webプログラミング。これはCS50です。 [CS50.TV]