SPEAKER 1: خوب، پس این است CS50 این پایان هفته پنج است. به یاد بیاورید که آخرین باری که ما به دنبال آغاز شده در داده خیال باف ساختار است که شروع به حل مشکلات، آغاز شده است که به معرفی مشکلات جدید است، اما کلید این مرتب کردن بر اساس نخ بود که ما شروع به انجام از گره به گره. بنابراین این البته یک لیست تنهایی مرتبط. و تنهایی مرتبط، منظور من فقط یک وجود دارد موضوع بین هر یک از این گره ها. معلوم است شما می توانید خیال باف انجام چیزهایی مانند لیست مضاعف مرتبط به موجب آن شما یک فلش که در هر دو جهت، که می توانید با راندمان خاص کمک کند. اما این حل مشکل؟ مشکل این را حل کند؟ چرا ما در روز دوشنبه مراقبت کرد؟ چرا، در تئوری، آیا ما در روز دوشنبه مراقبت؟ این چیکار می کنه؟ 

مخاطبان: ما به صورت پویا می توانید آن را تغییر اندازه دهید. 

SPEAKER 1: خوب، پس ما می توانیم به صورت پویا تغییر اندازه آن. خب هر دو از شما انجام می شود. بنابراین شما به صورت پویا می توانید این تغییر اندازه ساختار داده ها، در حالی که یک آرایه، به یاد بیاورید، شما باید بدانید که پیشینی چه مقدار فضای شما می خواهید و اگر شما نیاز به یک کمی بیشتر فضا، شما نوع از شانس هستید. شما باید برای ایجاد یک آرایه کاملا جدید است. شما باید به حرکت تمام خود را داده ها از یکی به دیگری، در نهایت آزاد آرایه های قدیمی اگر شما می توانید، و سپس ادامه دهید. که فقط احساس می کند بسیار پر هزینه و بسیار ناکارآمد، و در واقع می توان آن را. اما این تمام خوب نیست. ما پرداخت قیمت، چه بود از قیمت های واضح تر ما پرداخت با استفاده از یک لیست پیوندی؟ 

مخاطبان: ما مجبور به استفاده از فضای دو برای هر یک. SPEAKER 1: آره، بنابراین ما نیاز حداقل دو بار به عنوان فضای زیادی است. در واقع، من متوجه شدم این تصویر حتی یک کمی گمراه کننده است، چرا که در IDE CS50 در بسیاری از مدرن کامپیوتر، یک اشاره گر و یا یک آدرس در واقع چهار بایت است. این بسیار اغلب این روز هشت بایت، که معنی پایین ترین مستطیل وجود دارد در واقع از نوع دو برابر بزرگ به عنوان آنچه که من کشیده ام، که بدان معنی است شما با استفاده از سه برابر فضای آنجا که ما در غیر این صورت ممکن است. در حال حاضر در همان زمان، ما هنوز صحبت بایت، درست است؟ ما لزوما در حال صحبت کردن نیست مگابایت یا گیگابایت، مگر اینکه این داده ها سازه ها مطلع بزرگ است. 

و بنابراین، امروز ما شروع به در نظر چگونه ممکن است ما داده اکتشاف موثر تر اگر در واقع داده بزرگتر می شود. اما اجازه دهید سعی کنید به متعارف و استاندارد عملیات اول که شما می توانید در این کار را انجام انواع ساختمان داده. بنابراین چیزی شبیه به یک مرتبط لیست کلی از عملیات مانند حذف، قرار دادن، و جستجو کنید. و چه چیزی که من در؟ این تنها بدان معنی است که معمولا، اگر مردم با استفاده از لیست پیوندی، آنها یا شخص دیگری را اجرا کرده است توابع مانند حذف، درج، و جستجو، بنابراین شما می توانید در واقع انجام کاری با ساختار داده ها مفید است. بنابراین اجازه دهید نگاهی سریع در ما چگونه ممکن است پیاده سازی برخی از کد برای یک لیست پیوندی شرح زیر است. 

بنابراین این فقط برخی از کد C است، حتی یک برنامه کامل که من واقعا به سرعت شلاق تا. به صورت آنلاین در توزیع نمی کد، دلیل آن در واقع اجرا نمی شود. اما توجه کنید من فقط با یک نظر، گفت: نقطه نقطه نقطه، چیزی وجود دارد وجود دارد، نقطه نقطه نقطه، چیزی وجود دارد. و اجازه دهید فقط نگاه چه بخش آبدار هستند. بنابراین در خط سه، به یاد آورید که این در حال حاضر ما پیشنهاد اعلام یک گره آخرین زمان، یکی از کسانی که اشیاء مستطیل شکل است. از آن است که یک int است که ما N پاسخ، اما ما می تواند آن را هر چیزی پاسخ، و پس از آن یک ستاره ساختار گره به نام آینده. و فقط به روشن، که دوم خط، در خط شش، این است که؟ چه چیزی است که برای ما انجام می دهند؟ از آنجا که آن را قطعا به نظر می رسد بیشتر مرموز از متغیرهای معمول ما. 

مخاطبان: این باعث می شود آن را بیش از یک حرکت. 

SPEAKER 1: این باعث می شود آن را بیش از یک حرکت. و به عبارت دقیق تر، آن را به آدرس فروشگاه از گره که به معنای معنایی در کنار آن، درست است؟ پس از آن به رفتن نیست لزوما هر چیزی حرکت می کند. این فقط رفتن به ذخیره یک مقدار است که رفتن به آدرس برخی از گره های دیگر، و به همین دلیل ما ساختار گفت ستاره گره، ستاره دلالت یک اشاره گر و یا یک آدرس. OK، بنابراین در حال حاضر اگر شما فرض کنیم که ما این N در دسترس ما، و اجازه دهید فرض کنیم که شخص دیگری است درج یک دسته کامل از اعداد صحیح به یک لیست پیوندی. و لیست پیوندی است توسط برخی از نقطه به نقطه اشاره یک متغیر به نام لیست که در اینجا به عنوان یک پارامتر، چگونه در مورد خط بروم 14 اجرای جستجو؟ به عبارت دیگر، اگر من هستم اجرای تابع هدف در زندگی که این است که به یک int و پس از آن آغاز یک لیست پیوندی، که یک اشاره گر به لیست پیوندی است. مانند اول، که من فکر می کنم دیوید داوطلب ما در روز دوشنبه بود، او با اشاره به شد طیف مرتبط لیست، آن را به عنوان هر چند ما در حال عبور دیوید در عنوان آرگومان ما در اینجا. چگونه ما در مورد تراورس این لیست است؟ خب، معلوم است که حتی اگر اشاره گر نسبتا جدید در حال حاضر به ما، ما می توانیم این کار را انجام نسبتا صریح. 

من قصد دارم به جلو بروید و تعریف یک متغیر موقت که توسط کنوانسیون فقط رفتن به نام اشاره گر، یا PTR، اما شما می توانید آن را هر چیزی که می خواهید تماس بگیرید. و من قصد دارم به مقداردهی اولیه آن را به شروع از لیست. بنابراین شما می توانید نوع از این فکر می کنم به عنوان من معلم روز دیگر، نوع اشاره در کسی در میان انسان ما را به عنوان داوطلب. بنابراین من یک متغیر موقت که هستم فقط در همین اشاره که ما به نام اتفاقی داوطلب داود اشاره شده است. حالا در حالی که اشاره گر است تهی نیست، به دلیل فراخوان که تهی برخی از ارزش نگهبان خاصی است demarcates پایان از لیست، بنابراین در حالی که من در اشاره نمی زمین مانند گذشته داوطلب ما بود، اجازه دهید به جلو و زیر را انجام. اگر اشاره گر و در حال حاضر من از نوع می خواهید برای انجام آنچه ما با دانش آموز بود structure-- اگر اشاره گر نقطه بعدی equals-- نه، اگر اشاره گر نقطه N برابر با برابر با متغیر ازت، استدلال شده است که در گذشت، پس از آن من می خواهم به جلو بروید و می گویند بازگشت واقعی است. من پیدا کرده اند N تعداد داخل یکی از گره از لیست پیوندی است. اما نقطه دیگر با این نسخهها کار در این زمینه، چون اشاره گر، PTR، است در واقع یک اشاره گر، آدرس، ما در واقع می توانید زیبا استفاده از نهایت یک قطعه از نحو این نوع از می سازد حس بصری و در واقع استفاده از فلش در اینجا، که به معنی رفتن از که آدرس به عدد صحیح وجود دارد در. پس از آن در بسیار شبیه روح به عملگر نقطه، اما به دلیل اشاره گر یک اشاره گر نیست و نه یک ساختار واقعی خود، ما فقط استفاده از فلش. 

بنابراین اگر گره فعلی است که من، متغیر موقت، من اشاره در نه N، چه من می خواهم کاری انجام دهید؟ خب، با داوطلبان انسانی من که ما در اینجا به حال و روز دیگر، اگر برای اولین بار است که انسان من یکی نیست می خواهید، و شاید انسان دوم است یکی من می خواهم، و سوم، من نیاز به نگه داشتن از لحاظ جسمی در حال حرکت. مانند چگونه از طریق یک لیست مرحله من؟ هنگامی که ما یک آرایه به حال شما، درست مثل من به علاوه به علاوه انجام داد. اما در این مورد، آن را به کافی انجام اشاره گر، می شود، اشاره گر، بعدی. به عبارت دیگر، در این زمینه بعد مثل این است که همه از دست چپ که داوطلبان انسانی ما در روز دوشنبه با استفاده از به نقطه در برخی از گره های دیگر بود. این همسایه ها بعدی خود بودند. 

بنابراین اگر من می خواهم به قدم از طریق این لیست، من فقط می توانید انجام به علاوه به علاوه دیگر، من به جای می گویند من، اشاره گر است، رفتن برابر هر زمینه است، رشته بعدی است، درست است، زیر همه کسانی که دست چپ که ما در مرحله اشاره حال به برخی از ارزش های پس از آن. و اگر من از طریق دریافت که طیف تکرار، و در نهایت، من ضربه های پوچ داشتن نیست یافت N عین حال، من فقط بازگشت نادرست است. پس دوباره، که ما در اینجا انجام می دهند، به عنوان در هر تصویر یک لحظه پیش، توسط اشاره به شروع ابتدای فهرست احتمالا. و پس از آن را بررسی کنم، ارزش است من به دنبال به نه برابر است؟ اگر چنین است، من به راست و من انجام می شود. اگر نه، من دست من به روز رسانی، اشاره گر AKA، به نقطه در محل فلش در کنار، و پس از آن محل فلش آینده، و بعدی. من به سادگی راه رفتن را از طریق این آرایه است. 

پس دوباره، چه کسی اهمیت میدهد؟ مانند آنچه این یک عنصر برای است؟ خب، به یاد آورید که ما معرفی مفهوم پشته، که یک داده نوع مقاله تا آنجا که آن را یک چیز C، آن چیزی که CS50 نیست، این یک ایده انتزاعی، این ایده های انباشته همه چیز در بالای یکدیگر که می تواند در اجرا مجموعه ای از روش های مختلف. و یکی از راه های ما پیشنهاد می شد یک آرایه، یا با یک لیست پیوندی. و معلوم است که canonically، یک پشته از حداقل دو عملیات. و کلمات وزوز هستند فشار، به فشار چیزی را بر روی پشته، مانند یک سینی جدید در سالن غذاخوری، و یا پاپ، که به معنی به حذف بالاترین سینی را از پشته در ناهار خوری سالن، و پس از آن شاید برخی از عملیات دیگر نیز هست. پس چگونه ممکن است ساختار تعریف می کنیم که ما در حال حاضر خواستار یک پشته؟ 

خب، ما باید تمام نیاز نحو در اختیار ما در C. من می گویم، من یک تعریف نوع را یک ساختار داخل یک پشته، من قصد دارم به یک آرایه است، از یک تمام دسته از اعداد و پس از اندازه. بنابراین به عبارت دیگر، اگر من می خواهم برای اجرای این کد در، به من اجازه رفتن و فقط نوع رسم این می گوید. پس این است که گفت، من را ساختار که کردم یک آرایه، و من نمی دانم که چه ظرفیت است ظاهرا برخی از ثابت که من تعریف جاهای دیگر، و این خوب است. اما فرض این تنها یکی، دو، سه، چهار، پنج. بنابراین ظرفیت 5 است. این عنصر در داخل من ساختار خواهد شد اعداد نامیده می شود. و پس از آن من نیاز به یک متغیر دیگر ظاهرا اندازه که در ابتدا به نام من قصد دارم به تصریح است به صفر مقداردهی اولیه. اگر هیچ چیز در آن وجود دارد پشته، اندازه صفر است، و آن را ارزش زباله در اعداد است. من هیچ ایده چه چیزی در آن وجود دارد فقط رتبهدهی نشده است. 

بنابراین اگر من می خواهم به فشار چیزی را بر روی پشته، گمان می کنم فشار تابع، و من می گویم فشار 50، مانند شماره 50، که در آن شما پیشنهاد من آن را در قرعه کشی این آرایه؟ پنج پاسخ های متفاوت وجود دارد. کجا می خواهید به فشار شماره 50؟ اگر هدف در اینجا، دوباره، با تابع فشار، تصویب در بحث 50، که در آن آن را قرار دهم؟ پنج possible-- 20٪ احتمال از حدس زدن صحیح می باشد. بله؟ 

رسید سمت راست. 

SPEAKER 1: سمت راست. در حال حاضر 25٪ احتمال وجود دارد از حدس زدن صحیح می باشد. به طوری که در واقع خوب است. بر اساس قرارداد، من با یک آرایه می گویند، ما به طور کلی را در سمت چپ شروع اما ما می توانیم قطعا شروع در سمت راست. بنابراین اسپویلر در اینجا خواهد بود من احتمالا رفتن به آن را رسم در سمت چپ، فقط در یک آرایه طبیعی که در آن دوست من شروع به رفتن چپ به راست. اما اگر شما می توانید تلنگر حساب، خوب است. آن را فقط معمولی نیست. خوب، من نیاز به ایجاد یک تغییر بیشتر است. در حال حاضر که من چیزی تحت فشار قرار دادند بر روی پشته، چه بعدی؟ 

همه حق است، من به افزایش اندازه. بنابراین اجازه دهید من جلو و فقط به به روز رسانی این است که صفر بود. و به جای آن در حال حاضر، من قصد دارم به در ارزش یک قرار داده است. و در حال حاضر گمان می کنم یکی دیگر از فشار تعداد روی پشته، مانند 51. خوب، من به یک تغییر، که تا به اندازه دو. و پس از آن گمان می کنم فشار یک تعداد روی پشته مانند 61، در حال حاضر من نیاز به بروز رسانی به اندازه یک زمان، و ارزش 3 به عنوان اندازه. و در حال حاضر گمان می کنم پاسخ پاپ. در حال حاضر موسیقی پاپ، توسط کنوانسیون، یک استدلال می کند را ندارد. با یک پشته، کل نقطه استعاره سینی این است که شما اختیار ندارد به رفتن که سینی، همه شما می توانید انجام دهید پاپ بالاترین یکی از پشته، فقط به خاطر. این چیزی است که این ساختار داده است. 

بنابراین با این منطق اگر من می گویند پاپ، چه می آید؟ بنابراین 61. بنابراین آنچه که واقعا از کامپیوتر می باشد قصد دارم در حافظه؟ کد من چه کاری انجام دهید؟ آنچه را که شما پیشنهاد ما بر روی صفحه نمایش را تغییر دهید؟ چه باید تغییر دهید؟ متاسف؟ بنابراین ما از 61 خلاص شوید. بنابراین من قطعا می تواند انجام دهد. و من می توانید از 61 خلاص شوید. و پس از آن چه دیگر تغییر اتفاقی باید بیفتد؟ حجم احتمالا برای رفتن به دو. و به این ترتیب که خوب است. اما یک دقیقه صبر کنید، اندازه یک لحظه پیش سه بود. بیایید فقط بررسی سلامت عقل سریع است. چگونه ما می دانیم که ما را می خواستم به 61 خلاص شوید؟ از آنجا که ما در حال ظاهر. و بنابراین من این اندازه املاک دوم داشته باشد. 

یک دقیقه صبر کنید، من فکر بازگشت به هفته دو زمانی که ما شروع به صحبت در مورد آرایه ها، که در آن این مکان صفر بود، این مکان یکی بود، این محل بود دو، این مکان سه، چهار است، آن را مانند به نظر می رسد رابطه بین اندازه و عنصر که من می خواهم به حذف از آرایه به نظر می رسد فقط چه؟ حجم منهای یک. و به این ترتیب این که چگونه به عنوان انسان ما می دانیم که 61 اولین بار می آید. چگونه کامپیوتر رفتن به می دانم؟ هنگامی که کد خود را، که در آن شما احتمالا می خواهم به انجام یک منهای اندازه، پس از سه منهای یک دو، و آن این است معنی است که ما می خواهیم از 61 خلاص شوید. و سپس ما در واقع می توانید به روز رسانی اندازه به طوری که اندازه کن از سه به دو می رود. و فقط به موشکاف، من قصد دارم به پیشنهاد که من انجام می شود، درست است؟ شما به طور مستقیم پیشنهاد درست من باید از 61 خلاص شوید. اما من ندارد نوع مرتب کردن بر اساس از شر آنها خلاص 61؟ من به طور موثر را فراموش کرده ام که در واقع وجود دارد. و فکر می کنم به PSET4، اگر شما را خوانده ام مقاله در مورد پزشکی قانونی، پی دی اف که ما تا به حال شما بچه ها به عنوان خوانده شده، و یا شما این هفته برای PSET4 به عنوان خوانده شده. به یاد بیاورید که این در واقع به وابسته کل ایده کامپیوتر پزشکی قانونی. چه یک کامپیوتر به طور کلی می کند فقط فراموش آن چیزی است، اما در رفتن نیست و مانند سعی کنید آن را خراش و یا زیر پا بگذارند کسانی که بیت با صفر و آنهایی که و یا برخی از الگوی تصادفی دیگر مگر اینکه شما خودتان این کار را به عمد. بنابراین شهود خود را بود خوب، اجازه دهید از 61 خلاص شوید. اما در واقعیت، ما لازم نیست به زحمت. ما فقط نیاز به فراموش کرد که آن وجود دارد با تغییر اندازه ما است. 

در حال حاضر یک مشکل با این پشته وجود دارد. اگر من هل دادن همه چیز بر روی پشته، چه بدیهی است که اتفاق می افتد تنها در یک زمان چند لحظه؟ ما قصد داریم به اجرا از فضا. و چه کار کنیم؟ ما نوع پیچ. این پیاده سازی اجازه نمی ما تغییر اندازه آرایه، به دلیل استفاده از این نحو، اگر شما فکر می کنم به دو هفته، هنگامی که شما اعلام کرده ام به اندازه یک آرایه، ما را دیده اند که در آن مکانیزم شما می توانید اندازه آرایه را تغییر دهید. و در واقع C که ویژگی را ندارد. اگر شما می گویم من پنج را Nths، آنها را شماره های تماس، که همه شما در حال رفتن به آن را دریافت کند. بنابراین ما در حال حاضر از دوشنبه، دارند توانایی بیان یک راه حل هر چند، ما فقط نیاز به نیشگون گرفتن و کشیدن تعریف پشته ما به برخی از آرایه سخت رمزی نیست، اما فقط برای ذخیره یک آدرس. 

حالا چرا این است؟ در حال حاضر ما فقط باید راحت با این واقعیت است که زمانی که برنامه من اجرا می شود، من احتمالا رفتن به باید بپرسید انسان، چگونه بسیاری از اعداد را می خواهید برای ذخیره؟ بنابراین ورودی بالاخره باید از جایی آمده است. اما هنگامی که من می دانم که شماره، سپس من فقط می توانید استفاده از آنچه تابع را به من یک تکه از حافظه؟ من می توانم از malloc استفاده کنید. و من می توانم هر تعداد از گویند من می خواهم بایت برای این Nths. و تمام من برای ذخیره اعداد در متغیر در اینجا در داخل این ساختار باید چه؟ آنچه در واقع به می رود اعداد در این سناریو؟ آره، یک اشاره گر به اولین بایت از آن تکه از حافظه، و یا به طور خاص، آدرس از اولین کسانی که بایت است. مهم نیست که اگر آن را یکی بایت یا یک میلیارد بایت من فقط باید در مورد مراقبت از اول. از آنجا که آنچه تضمین malloc و من تضمین سیستم عامل، این است که تکه از حافظه من دریافت کنید، آن را برای رفتن به هم پیوسته. وجود دارد که نمی تواند شکاف. بنابراین اگر من برای 50 خواسته ام بایت یا 1،000 بایت، همه آنها در حال رفتن به برگشت به پشت به پشت. و تا زمانی که من به یاد داشته باشید که چگونه بزرگ، چگونه بسیار برای همه من نیاز به دانستن خواسته اولین آدرس است. 

بنابراین در حال حاضر ما باید توانایی در کد. البته، آن را به ما را زمان بیشتری را برای ارسال این، ما در حال حاضر می تواند که حافظه تخصیص مجدد توسط فقط ذخیره سازی آدرس های مختلف وجود دارد اگر ما می خواهیم یک بزرگتر و یا حتی یک تکه کوچک تر از حافظه است. بنابراین در اینجا به یک خاموش تجارت است. در حال حاضر ما پویایی است. ما هنوز contiguousness من ادعا. از آنجا که از malloc خواهد به ما بدهد یک قطعه پیوسته از حافظه است. اما این است که برای رفتن به یک درد در گردن برای ما، برنامه نویس، به واقع کد است. این کار فقط بیشتر است. ما نیاز به کد شبیه به آنچه که من بود banging از فقط یک لحظه پیش. بسیار شدنی، اما می افزاید پیچیدگی. و پس از آن زمان توسعه، برنامه نویس زمان هنوز یکی دیگر از منابع که ما ممکن است نیاز به صرف برخی از زمان برای دریافت ویژگی های جدید است. و پس از آن البته یک صف وجود دارد. ما نمی خواهد به این رفتن در جزئیات بسیار. اما آن را در روح بسیار مشابه است. من می توانم یک صف پیاده سازی، و عملیات مربوط به آن، در نوبت قراردادن و یا dequeue، مانند اضافه یا حذف، این فقط یک راه خیال باف از گفتن آن است، در نوبت قراردادن و یا dequeue، به شرح زیر. من فقط می توانم خودم را یک ساختار که دوباره است آرایه یک عدد است، که دوباره تا به اندازه، اما چرا من در حال حاضر نیاز برای پیگیری از جلوی صف؟ من نیاز به دانستن جلوی پشته من. خب، اگر من دوباره برای queue-- بیا فقط سخت کد آن را به عنوان داشتن مانند پنج اعداد صحیح در اینجا به طور بالقوه. بنابراین این صفر، یک، دو، سه، چهار است. این است برای رفتن به اعداد به نام دوباره. و این خواهد شد به نام اندازه. 

چرا آن را کافی نیست به اندازه فقط؟ خوب، اجازه دهید آن اعداد همان فشار در. بنابراین من pushed-- من را enqueued، و یا تحت فشار قرار دادند. در حال حاضر من نوبت 50، و پس از آن 51، و پس از آن 61 و نقطه نقطه نقطه. به طوری که در نوبت قراردادن. من را enqueued 50، پس از آن 51، پس از آن 61. و به نظر می رسد یکسان به پشته تا کنون، به جز من نیاز به یک تغییر دهید. من نیاز به به روز رسانی این اندازه، بنابراین من به از صفر به یک به دو تا سه در حال حاضر. چگونه dequeue من؟ چه با dequeue اتفاقی می افتد؟ چه کسی باید اول آمده به این لیست اگر آن را به خط در فروشگاه اپل؟ بنابراین 50. بنابراین نوع سختتر این بار آن را. در حالی که آخرین بار آن را فوق العاده بود آسان به فقط یک منهای اندازه، من به پایان آرایه من به طور موثر که در آن اعداد هستند، آن را حذف 61. اما من نمی خواهم به حذف 61. من می خواهم به 50، که وجود دارد در 5:00 AM شد به خط کردن برای آیفون و یا فلان چیز جدید است. و به همین ترتیب برای خلاص شدن از شر 50، من می توانید این نه فقط انجام، درست است؟ من می توانید عبور از 50. اما ما فقط ما گفت: لازم نیست که می شود تا مقعد به عنوان به خراش و یا مخفی کردن داده ها. ما فقط می توانید فراموش که در آن است. 

اما اگر اندازه را تغییر دهم در حال حاضر به دو، این اطلاعات کافی است بدانید که چه چیزی در جریان است در صف من؟ نه واقعا. مانند اندازه من دو است، اما کجا صف شروع، به خصوص اگر من هنوز هم تعداد کسانی که همان در حافظه است. 50، 51، 61. بنابراین من نیاز به یاد داشته باشید اکنون که در آن جلوی است. و بنابراین به عنوان من پیشنهاد تا وجود دارد، ما باید فقط به نام جلو n ام، که اولیه مقدار باید چه بوده است؟ صفر، فقط آغاز این فهرست است. اما در حال حاضر علاوه بر طرح ساده اندازه، ما فقط افزایش جلو. حالا در اینجا مشکل دیگری است. پس یک بار من را ادامه دهم. فرض کنید این تعداد است مانند 121، 124، و پس از آن، لعنتی، من از فضای هستم. اما یک دقیقه صبر کنید، من نیستم. بنابراین در این مرحله در داستان، فرض کنید که به اندازه یک، دو است، سه، چهار، بنابراین فرض کنید که اندازه چهار است، جلو یکی است، بنابراین 51 است در جلو. من می خواهم برای قرار دادن شماره دیگری اینجا هست، اما، لعنتی، من از فضا است. اما من واقعا، درست است؟ که در آن می تواند برخی از قرار ارزش اضافی، مانند 171؟ آره، من فقط می تواند نوع برو به بیش وجود دارد، درست است؟ و سپس عبور از 50، و یا فقط آن را با 171 بازنویسی. و اگر شما تعجب که چرا تعداد ما اینقدر تصادفی، این ها برای کامپیوتر گرفته دروس علوم در دانشگاه هاروارد پس از CS50. اما این یک بهینه سازی خوب بود، چون در حال حاضر من فضا هدر رفتن نیست. من هنوز هم به یاد داشته باشید چقدر بزرگ این چیزی که کل است. پنج کل است. برای این که من نمی خواهم شروع جای نوشتن 51. بنابراین در حال حاضر من هنوز هم از فضا هستم، بنابراین مشکل مانند قبل است. اما شما می توانید ببینید که چگونه با شرکت در کد خود را، شما احتمالا برای نوشتن یک کمی بیشتر پیچیدگی را که اتفاق می افتد. و در واقع، آنچه اپراتور در C احتمالا اجازه می دهد تا شما جادویی این دوری را انجام دهد؟ آره عملگر باقی مانده، علامت درصد. پس چه نوع سرد در مورد یک صف، حتی اگر ما را حفظ آرایه رسم این خطوط مستقیم مانند، اگر شما نوع مورد این عنوان کرنش فکر می کنم به عنوان یک دایره، پس از آن فقط به طور مستقیم آن نوع آثار روانی من فکر می کنم کمی پاک تر. باز هم باید به پیاده سازی که مدل ذهنی در کد. به طوری که نه سخت است، در نهایت، به پیاده سازی، اما ما هنوز از دست دادن size-- نه، توانایی تغییر اندازه، مگر اینکه ما این کار را. 

ما باید از شر از آرایه خلاص شدن از شر، ما جایگزین کردن آن با یک اشاره گر تک، و سپس در جایی در کد من من تماس بگیرید آنچه تابع در واقع به ایجاد آرایه از اعداد به نام؟ از malloc، و یا برخی مشابه عملکرد، دقیقا. هر گونه سوال و یا بر روی پشته صف. آره؟ سوال خوبی بود. چه پیمانه استفاده می کنید در اینجا. بنابراین به طور کلی، هنگامی که با استفاده از وزارت دفاع، شما می توانید آن را انجام دهید با اندازه ساختار داده ها کل. بنابراین چیزی شبیه به پنج یا ظرفیت، اگر آن را ثابت، احتمالا نقش دارند. اما فقط انجام پیمانه پنج احتمالا کافی نیست، چرا که ما نیاز به دانستن ما انجام می دهیم پوشش در اطراف اینجا یا اینجا یا اینجا. بنابراین شما احتمالا همچنین در حال رفتن به خواهید برای شامل اندازه چیزی، یا متغیر مقابل است. بنابراین آن را فقط این نسبتا بیان ساده ریاضی، اما به پیمانه می شود عنصر کلیدی. 

فیلم به قدری کوتاه اگر شما خواهد شد. یک انیمیشن است که برخی مردمی در یکی دیگر از دانشگاه کنار هم قرار دادن ایم که اقتباس برای این بحث. این شامل جک یادگیری حقایق در مورد صف و آمار. 

فیلم: روزی روزگاری، بود یک پسر به نام جک است. که آن را به دوستان آمد، جک یک استعداد ندارد. بنابراین جک رفت و به صحبت کردن با پسر محبوب ترین او می دانست. او به لو رفت و پرسید، چه باید بکنم؟ لو دیدم که دوست خود را واقعا نگران و دلواپس بود. خب، او شروع، فقط نگاه کنید که چگونه شما در حال لباس پوشیدن. آیا شما هر گونه لباس نیست با نگاه های مختلف؟ بله، گفت: جک. من مطمئن هستم که انجام می دهند. بیا به خانه من و من آنها را به شما نشان دهد. به طوری که آنها را به جک رفت. و جک لو نشان داد جعبه که در آن او نگه داشته، همه پیراهن او، و شلوار خود را، و جوراب خود را. لو گفت، من می بینم شما تمام لباس های خود را در یک شمع. چرا شما پوشیدن برخی از یک بار در چندی دیگران؟ 

جک گفت: خوب، وقتی من حذف لباس و جوراب، من آنها را بشویید و آنها را دور در جعبه. سپس می آید بعدی صبح، و من هاپ. من به جعبه بروید و لباس هایم بالا. لو به سرعت متوجه شدم مشکل با جک. او نگه داشته، لباس، سی دی، و کتاب در پشته. زمانی که او برای ما چیزی برای خواندن و یا به لباس، او می خواهم این کتاب بالا و یا لباس زیر را انتخاب کنید. سپس هنگامی که او انجام شد، او آن را به سمت راست برگشت. برگشت آن خواهند رفت، در بالای پشته. من می دانم که راه حل، گفت با صدای بلند پیروزی. شما نیاز به یادگیری به شروع به استفاده از یک صف. لو لباس جک را گرفت و آنها را در گنجه آویزان. و هنگامی که او را خالی کرده بود جعبه، او فقط آن را پرتاب کرد. 

سپس به او گفت، در حال حاضر جک، در پایان روز، لباس های خود را در سمت چپ قرار هنگامی که شما آنها را دور. و سپس فردا صبح هنگامی که شما دیدن آفتاب، لباس های خود را در سمت راست، از انتهای خط. آیا شما نمی بینید؟ گفت لو. از آن خواهد شد تا خوب. شما همه چیز را یک بار لباس قبل از اینکه شما پوشیدن چیزی دو بار. و با همه چیز در صف در گنجه و قفسه خود، جک شروع به احساس کاملا مطمئن از خود. همه به لطف و لو صف فوق العاده اش. SPEAKER 1: همه حق است، آن را شایان ستایش. پس چه شده است واقعا در زیر هود در حال حاضر؟ که ما اشاره گر، که ما از malloc، که ما توانایی ایجاد تکه های حافظه برای خودمان به صورت پویا. بنابراین این یک تصویر است ما فقط روز دیگر دیدم. ما واقعا ساکن نیست بر روی آن، اما این تصویر در جریان بوده است زیر هود برای هفته ها در حال حاضر. و این نشان دهنده، فقط یک مستطیل است که ما کشیده ام، حافظه کامپیوتر شما. و شاید کامپیوتر شما و یا CS50 ID، دارای یک گیگابایت حافظه یا RAM و یا دو گیگابایت یا چهار. این واقعا مهم نیست. سیستم عامل شما ویندوز یا Mac OS یا لینوکس، اساسا اجازه می دهد تا برنامه های خود را به فکر می کنم که به آن دسترسی دارد به طور کامل از حافظه کامپیوتر شما، حتی اگر شما ممکن است در حال اجرا برنامه های متعدد در یک بار. پس در حقیقت، که واقعا کار می کنند. اما این نوع از یک توهم به تمام برنامه های خود را داده است. بنابراین اگر شما تا به حال دو گیگابایت رم، این این است که چگونه کامپیوتر ممکن است آن فکر می کنم. 

در حال حاضر اتفاقی، یکی از این همه چیز، یکی از این بخش از حافظه، است یک پشته نامیده می شود. و در واقع هر زمان تا کنون در نوشتن کد که شما به نام یک تابع، برای مثال اصلی. به یاد بیاورید که هر زمان من حافظه کامپیوتر کشیده شده است، من همیشه مرتب کردن بر اساس قرعه کشی نیمی از یک مستطیل در اینجا و زحمت صحبت کردن در مورد چه چیزی بالا. چرا که وقتی اصلی نامیده می شود، من ادعا که شما این بریدن از حافظه که در اینجا پایین می رود. و اگر یک تابع اصلی به نام مانند مبادله، به خوبی مبادله اینجا می رود. و معلوم است که که در آن پایان دادن به. در چیزی به نام پشته در داخل حافظه کامپیوتر شما. در حال حاضر در پایان روز، این فقط آدرس. آن را مانند بایت صفر است، یکی بایت، بایت 2 میلیارد. اما اگر شما در مورد آن فکر این شی مستطیل شکل، همه ما در حال انجام هر زمان ما با یک تابع است لایه بندی یک تکه جدید از حافظه است. ما در حال دادن که تابع یک تکه حافظه خود را برای کار با. 

و به یاد که این مهم است. از آنجا که اگر لازم ما چیزی شبیه به مبادله و دو متغیر های محلی مانند A و B و ما این مقادیر را تغییر دهید از یک و دو به دو و یک، فراخوان که زمانی که مبادله می گرداند، آن را به عنوان هر چند این قطعه حافظه فقط رفته. در واقع، آن را هنوز هم forensically به وجود دارد. و چیزی که هنوز هم در واقع وجود دارد. اما مفهومی، آن را به عنوان هر چند آن را به طور کامل از بین رفته اند. و به این ترتیب هیچ اصلی از کار مطمئن شوید که که در آن تابع swap انجام شد، مگر اینکه آن را در واقع در آن به تصویب رسید استدلال شده توسط اشاره گر و یا توسط مرجع. در حال حاضر، راه حل اساسی به این مسئله را با مبادله در حال عبور از چیزهایی که در آدرس های. اما معلوم است، بیش از حد، چه شده است در جریان بالا که بخشی از مستطیل تمام این مدت است در عین حال حافظه بیشتر وجود دارد وجود دارد. و هنگامی که شما به صورت پویا تخصیص حافظه، آیا آن را در داخل از getstring، که ما شده ایم انجام را برای شما در CS50 کتابخانه، و یا اگر شما بچه ها از malloc تماس بگیرید و بپرسید سیستم عامل برای یک تکه از حافظه، آن را از پشته آمده است. آن را از جای دیگری می آید در حافظه کامپیوتر شما که پشته نامیده می شود. و این هر متفاوت است. این RAM همان است. این حافظه همان است. آن را فقط به RAM است که تا به جای پایین در اینجا وجود دارد. 

و به این ترتیب به چه معنا است؟ خوب، اگر کامپیوتر شما دارای مقدار محدودی از حافظه و پشته در حال رشد است، به طوری که به صحبت می کنند، و پشته، با توجه این فلش، در حال رشد است به پایین. به عبارت دیگر، هر زمان شما malloc تماس بگیرید، شما در حال داده یک تکه حافظه از بالا، پس از آن شاید کمی پایین تر، پس از آن کمی پایین تر، هر زمانی که شما malloc تماس بگیرید، پشته، آن را استفاده، از نوع در حال رشد، در حال رشد نزدیک و نزدیکتر به چه؟ پشته. بنابراین آیا این مانند یک ایده خوب به نظر می رسد؟ منظور من، که در آن واقعا روشن نیست چه چیز دیگری شما می توانید اگر فقط شما انجام یک مقدار محدود از حافظه است. اما این قطعا بد است. این دو فلش در می سقوط دوره برای یکدیگر است. 

و معلوم است که مرد بد است، مردمی که به خصوص با برنامه نویسی خوب، و تلاش برای هک کامپیوتر، می توانید این واقعیت بهره برداری. در واقع، اجازه دهید در نظر یک قطعه کوچک است. بنابراین این مثال شما می توانید به عنوان خوانده شده در مورد با جزئیات بیشتر در ویکیپدیا. ما شما را در نقطه مقاله اگر کنجکاو. اما به طور کلی از یک حمله وجود دارد شناخته شده به عنوان سرریز بافر که برای تا زمانی که انسان وجود داشته توانایی دستکاری داشته اند حافظه کامپیوتر، به ویژه در C. این یک برنامه بسیار خودسرانه است، اما اجازه دهید آن از پایین به بالا به عنوان خوانده شده. اصلی را به ستاره کاراکتر تعداد آنها و argv. پس از آن یک برنامه ای است که طول می کشد آرگومان های خط فرمان. و همه اصلی می کند ظاهرا پاسخ است یک تابع، آن را F برای سادگی. و آن را در چه می گذرد؟ ی argv یک. بنابراین آن را به F عبور هر کلمه این است که کاربر تایپ در اعلان پس از نام برنامه را در همه. بنابراین بسیار شبیه سزار و یا ویژنر که شما ممکن است به خاطر انجام می دهند با ی argv. 

پس چه F است؟ F طول می کشد در یک رشته به عنوان آرگومان های انحصاری خود AKA یک ستاره کاراکتر، همان چیزی، به عنوان یک رشته است. و آن را به نام دلخواه نوار در این مثال. و پس از آن کاراکتر C 12، فقط در عبارت، چه کاراکتر C براکت 12 انجام برای ما؟ چه کاری انجام میدهد؟ تخصیص حافظه، به طور خاص 12 بایت برای 12 کاراکتر می باشد. دقیقا. و پس از آن در آخرین خط، هم بزنید و کپی، شما احتمالا دیده ایم. این یک نسخه رشته است تابع هدف در زندگی که است برای کپی کردن آرگومان دوم آن به اولین آرگومان آن، اما تنها تا یک تعداد معینی از بایت است. بنابراین استدلال سوم می گوید: چگونه بسیاری از بایت باید به شما کپی کنید؟ طول نوار، هر کاربر تایپ در. و محتویات نوار، این رشته، می کپی در حافظه در اشاره در C. 

بنابراین به نظر می رسد این نوع احمقانه، و آن است. این یک مثال ساختگی است، اما آن را نماینده از یک کلاس از بردارهای حمله، راه حمله به یک برنامه است. همه خوب و خوب اگر کاربر انواع در یک کلمه که 11 کاراکتر یا کمتر، به علاوه بک اسلش صفر. اگر کاربر در بیش از 11 یا 12 یا 20 یا 50 کاراکتر؟ این برنامه را به انجام چه خبر؟ گسل بالقوه SEG. قرار است که کورکورانه همه چیز را در نوار بالا کپی طول آن است، که به معنای واقعی کلمه همه چیز را در نوار، به آدرس اشاره کرد C. اما C تنها پیشگیرانه به عنوان 12 بایت داده شده است. اما هیچ چک اضافی وجود دارد. وجود ندارد در صورتی که شرایط. هیچ چک کردن خطا در اینجا وجود دارد. 

و بنابراین، آنچه این برنامه این است برای انجام شده است فقط کورکورانه کپی یک چیز دیگر است. و بنابراین اگر ما این رسم به عنوان یک تصویر، در اینجا فقط یک تکه از فضای حافظه. بنابراین اطلاع در پایین، ما در نوار متغیر محلی است. به طوری که اشاره گر که رفتن به store-- نه که استدلال محلی که رفتن به ذخیره نوار رشته است. و پس از آن فقط متوجه بالاتر از آن در یک پشته، زیرا هر بار که شما درخواست برای حافظه در پشته، از آن می رود کمی در بالای آن pictorially، توجه کنید که ما 12 بایت کردم وجود دارد. یکی از بالا سمت چپ C براکت صفر و است یکی از پایین سمت راست C براکت 11 است. که چقدر کامپیوتر رفتن به آن را پخش کردن. بنابراین فقط به طور مستقیم، اگر نوار دارای بیش بیش از 12 کاراکتر در کل، از جمله بک اسلش صفر، که در آن است که 12 یا براکت C 12 برای رفتن؟ و یا به جای که در آن در 12th است شخصیت یا شخصیت 13TH، شخصیت صدم رفتن برای پایان دادن به در تصویر؟ در بالا یا زیر؟ 

راست، چرا که حتی اگر پشته خود رشد می کند به سمت بالا، هنگامی که شما مسائل را در قرار داده ام آن، آن را به دلایل طراحی، قرار می دهد حافظه از بالا به پایین. بنابراین اگر شما بیش از 12 بایت کردم، شما در حال رفتن به شروع به بازنویسی نوار. در حال حاضر که یک اشکال است، اما آن واقعا یک معامله بزرگ است. اما این یک معامله بزرگ است، به دلیل وجود دارد چیزهای بیشتری که در حافظه است. بنابراین در اینجا ما چگونه ممکن است قرار سلام، روشن می شود. اگر من در سلام در اعلان تایپ. H-E-L-L-O بک اسلش صفر، به پایان می رسد تا در کسانی که 12 بایت، و ما فوق العاده امن است. همه خوب است. اما اگر تایپ کنید من چیزی دیگر، به طور بالقوه آن رفتن به خزش به نوار فضا. اما بدتر از آن، آن را تبدیل از این همه زمان، حتی اگر ما هرگز در مورد صحبت کردیم آن، پشته برای چیزهای دیگر استفاده می شود. آن را فقط متغیرهای محلی است. 

C یک زبان سطح بسیار پایین است. و آن نوع مخفیانه با استفاده از پشته هم به یاد داشته باشید زمانی که یک تابع نامیده می شود، چه آدرس تابع قبلی، پس از آن به که تابع می تواند پرش. بنابراین، هنگامی که تماس های اصلی مبادله، در میان چیزهایی که روی پشته قرار می نه فقط معاوضه متغیرهای محلی، و یا استدلال خود، همچنین مخفیانه تحت فشار قرار دادند بر روی پشته به عنوان نمایندگی توسط تکه های قرمز در اینجا، آدرس اصلی فیزیکی است در حافظه کامپیوتر شما، به طوری که وقتی مبادله انجام شده است، کامپیوتر می داند که من نیاز به رفتن برگشت به بخش اصلی و پایان اجرای تابع اصلی. بنابراین این خطرناک است، چون اگر نوع کاربر در خوبی بیش از سلام، به طوری که ورودی کاربر clobbers و یا رونویسی که بخش قرمز، اگر منطقی کامپیوتر فقط رفتن به کورکورانه فرض که بایت است که قطعه قرمز رنگ هستند آدرس که به آن باید بازگشت، چه می شود اگر دشمن است و یا به اندازه کافی هوشمند اندازه کافی خوش شانس برای قرار دادن یک دنباله ای از بایت وجود دارد که به نظر می رسد مانند آدرس، اما آدرس از کد است که او می خواهد کامپیوتر برای اجرای به جای اصلی. 

به عبارت دیگر، اگر چه کاربران در حال تایپ کردن در اعلان، تنها چیزی نیست مانند بی ضرر سلام، اما در واقع کد که معادل تمام فایل های این کاربر را حذف کنید؟ و یا رمز عبور خود را ایمیل به من؟ ورود به سیستم یا شروع خود کلید، درست است؟ یک راه وجود دارد، اجازه دهید امروز تصریح، که آنها می توانند در نوع نه فقط سلام جهان و یا نام خود، آنها می توانند در اصل تصویب در کد، صفر و آنهایی که، که کامپیوتر اشتباهات برای هر دو کد و یک آدرس. بنابراین تا حدودی انتزاعی البته، اگر نوع کاربر در کافی کد خصمانه ما در اینجا به عنوان که باید تعمیم الف حمله و یا دشمنان است. چیزهای بد. ما در مورد اهمیت نمی اعداد یا صفر و یا آنهایی که امروز، به طوری که شما را تا پایان نوشتن که بخش قرمز، توجه کنید که دنباله ای از بایت است. O 835 C صفر هشت صفر است. و در حال حاضر به عنوان مقاله ویکیپدیا در اینجا پیشنهاد کرده است، اگر شما در حال حاضر در واقع شروع برچسب بایت در کامپیوتر شما حافظه، چه مقاله ویکیپدیا ارائه طرح این است که، اگر آدرس از بایتی بالا سمت چپ 80 C 0 3508 است. 

به عبارت دیگر، اگر آن مرد بد است به اندازه کافی هوشمند با کد خود را به واقع یک عدد را در اینجا که مربوط به آدرس از کد او تزریق به کامپیوتر، شما می توانید کامپیوتر فریب به انجام کاری. از بین بردن فایل، ایمیل همه چیز، خرناس ترافیک خود را، به معنای واقعی کلمه هر چیزی می تواند باشد به کامپیوتر تزریق می شود. و به این ترتیب یک سرریز بافر حمله در هسته خود فقط یک احمق، احمق مهم از یک آرایه است که لازم نیست مرزهای خود را بررسی می شود. و این چیزی است که فوق العاده خطرناک و به طور همزمان فوق العاده قدرتمند در C این است که ما در واقع دارای دسترسی به هر نقطه در حافظه است. این به ما است، برنامه نویسان، که نوشتن کد اصلی برای بررسی طول رفو از هر آرایه های که ما در حال دستکاری. بنابراین به روشن باشد، چه ثابت است؟ اگر ما به این رول کد، من باید نه فقط تغییر طول نوار، چه دیگری باید چک شود؟ چه چیز دیگری باید انجام به جلوگیری از این حمله به طور کامل؟ من نمی خواهم به فقط کورکورانه می گویند که شما باید به عنوان بسیاری بایت کپی به عنوان طول نوار است. من می خواهم بگویم، کپی به عنوان بایت های بسیاری به عنوان در نوار هستند تا اختصاص داده حافظه، و یا 12 حداکثر. بنابراین من نیاز به نوعی از شرایط اگر می کند که بررسی طول نوار، اما اگر آن را بیش از 12، ما کد فقط سخت 12 به عنوان حداکثر فاصله ممکن. در غیر این صورت بافر به اصطلاح حمله سرریز می تواند رخ دهد. در پایین آن اسلاید، اگر شما کنجکاو هستید به ادامه مطلب مقاله واقعی اصلی است اگر شما می خواهم به نگاهی. 

اما در حال حاضر، در میان قیمت پرداخت در اینجا ناکارآمدی بود. به طوری که یک سریع بود کم نگاه در چه سطح مشکلات هم اکنون می توانید بوجود می آیند که ما دسترسی به حافظه کامپیوتر را داشته باشد. اما مشکل دیگری که ما در حال حاضر در روز دوشنبه تصادفا فقط ناکارآمدی بود از یک لیست پیوندی. ما به زمان خطی. ما دیگر باید یک آرایه به هم پیوسته. ما با دسترسی تصادفی نیست. ما می توانیم علامت کروشه مربع استفاده کنید. ما به معنای واقعی کلمه مجبور به استفاده از یک حلقه در حالی که مانند یکی از من نوشت یک لحظه پیش. اما در روز دوشنبه، ما ادعا کرد که ما می توانیم خزش آن را به حوزه بهره وری دستیابی به چیزی که لگاریتمی شاید، و یا بهترین و در عین حال، شاید حتی چیزی که اصطلاح زمان ثابت است. پس چگونه می توان این کار را با استفاده از این جدید ابزار، به این آدرس، این اشاره گر، و چیزهایی از خود ما نخ؟ خب، فرض کنید که در اینجا، این یک دسته از اعداد است که ما می خواهیم برای ذخیره در ساختار داده ها و جستجو موثر است. ما کاملا می توانید به هفته عقب دو، این پرتاب به یک آرایه، و جستجو آنها را با استفاده جستجوی دودویی. تفرقه بینداز و حکومت کن. و در واقع شما نوشت جستجوی دودویی در PSET3، که در آن شما اجرا برنامه پیدا کردن. اما شما می دانید چه. این نوع از بیشتر وجود دارد راه هوشمندانه از انجام این کار. آن را کمی بیشتر پیچیده و شاید ما اجازه می دهد که چرا باینری جستجو بسیار سریع تر است. اول، اجازه دهید به معرفی مفهوم از یک درخت. که حتی اگر در درختان واقعیت نوع رشد شبیه به این، در جهان از کامپیوتر علم آنها از نوع رشد رو به پایین مانند یک درخت خانواده، که در آن شما پدربزرگ و مادربزرگ خود یا پدربزرگ و مادربزرگ بزرگ و یا فلان چیز در بالا، ایلخانی و مادر خانواده، یکی فقط به اصطلاح ریشه، گره، زیر که کودکان خود هستند، زیر که کودکان خود را، و یا فرزندان آن به طور کلی. و هر کسی حلق آویز کردن پایین خانواده درخت، علاوه بر این که جوان در خانواده، همچنین می توانید فقط عام شود به نام برگ از درخت. 

بنابراین این فقط یک دسته است از کلمات و تعاریف برای چیزی به نام یک درخت در کامپیوتر علم، بسیار شبیه به یک شجره نامه. اما برداشت رویایی وجود دارد درختان، که یکی از آنها است یک درخت جستجوی دودویی نامیده می شود. و شما می توانید نوع کسی را دست انداختن جدا چه این چیزی که. خوب، آن را دودویی به چه معنا؟ کجا باینری از اینجا می آیند؟ متاسف؟ آن را آنقدر هم یا نه. این بیشتر که هر یک از گره ها ندارد بیش از دو فرزند، به عنوان ما اینجا را ببینید. به طور کلی، tree-- و پدر و مادر و پدربزرگ و مادربزرگ خود را می توانید به عنوان بسیاری از بچه ها و یا نوه به عنوان آنها در واقع می خواهم، و بنابراین به عنوان مثال ما سه کودکان را که گره دست راست، اما در یک درخت دودویی، یک گره است صفر، یک، یا دو بچه حداکثر. و ملک خوب است، چرا که اگر آن را توسط دو پوش، ما قصد داریم قادر به گرفتن یک پایگاه ورود به سیستم کمی دو عمل در جریان است در اینجا در نهایت! بنابراین ما باید چیزی لگاریتمی است. اما بیشتر که در یک لحظه. درخت جستجوی بدان معنی است که اعداد مرتب به طوری که کودک چپ مقدار بیشتر از ریشه است. و فرزند راست آن است بزرگتر از ریشه. به عبارت دیگر، اگر شما هر یک از گره ها، حلقه ها در این تصویر، و به نظر می رسد در سمت چپ آن کودک و فرزند راست آن، برای اولین بار باید کمتر از باشد، دوم باید بیشتر از باشد. بنابراین سلامت عقل را بررسی کنید 55. این کودک باقی مانده 33 است. این کمتر از. 55، فرزند راست آن 77 است. آن را بیشتر از. و این یک تعریف بازگشتی است. ما می تواند هر یک از آن را بررسی کنید گره ها و همان الگوی نگه دارید. 

پس چه خوب است در یک درخت جستجوی دودویی است، که، ما می توانیم آن را پیاده سازی با یک ساختار، فقط این را دوست. و حتی اگر ما در حال پرتاب بسیاری از ساختارهای خود را، آنها تا حدودی هستید بصری اکنون امیدوارم. نحو است که هنوز هم محرمانه برای مطمئن، اما محتویات یک گره در این context-- و ما را حفظ با استفاده از گره کلمه، آیا آن یک مستطیل است بر روی صفحه نمایش و یا یک دایره، این فقط برخی از ظرف های عمومی است، در این مورد یک درخت، مثل یک ما دیدیم، ما نیاز به یک عدد صحیح در هر یک از گره و پس از آن من نیاز به دو اشاره گر اشاره به فرزند چپ و فرزند راست، به ترتیب. به طوری که ما چگونه ممکن است پیاده سازی است که در یک ساختار. و چگونه ممکن است آن را در کد پیاده سازی؟ خوب، اجازه دهید یک سریع در این مثال کوچک است. آن را کاربردی نیست، اما من کپی و جا به جا که ساختار. و اگر تابع من برای یک فایل باینری درخت جستجوی نامیده می شود جستجو، و این طول می کشد دو استدلال، عدد n و یک اشاره گر به یک گره، به طوری که یک اشاره گر به درخت و یا یک اشاره گر به ریشه یک درخت، چگونه می توانم در مورد جستجو برای N برود؟ خب، اول، چون من خرید و فروش با اشاره گر، من قصد دارم به انجام یک بررسی سلامت عقل. اگر برابر درخت برابر تهی، N است در این درخت یا نه در این درخت؟ این نمی تواند، درست است؟ اگر من در گذشته های پوچ هستم، هیچ چیز وجود دارد وجود دارد. من نیز ممکن است فقط کورکورانه می گویند بازگشت نادرست است. اگر شما به من چیزی بدهد، من قطعا می تواند پیدا کردن هر N. شماره پس چه چیز دیگری ممکن است من در حال حاضر بررسی؟ من قصد دارم به خوبی دیگری اگر N است کمتر از آنچه در گره درخت که من تحویل داده شده است که ارزش N. به عبارت دیگر، اگر تعداد من به دنبال، N، کمتر از گره است که من به دنبال در. و گره من به دنبال در است که به نام درخت، و به یاد از مثال قبلی به ارزش در یک اشاره گر، من با استفاده از فلش نماد. بنابراین اگر N کمتر از درخت جهت دار است N، من می خواهم به مفهومی به سمت چپ. چگونه می توانم بیان جستجوی سمت چپ؟ برای روشن باشد، در صورتی که این تصویر در سوال، و من تصویب شده است که بالاترین فلش است که با اشاره به پایین. که اشاره گر درخت من است. من اشاره در ریشه درخت. و من به دنبال می گویند، برای تعداد 44، خودسرانه. 44 یا کمتر از بیشتر از 55 بدیهی است؟ پس از آن کمتر از. و بنابراین این اگر شرایط اعمال می شود. بنابراین مفهومی، چه چیزی می خواهید من جستجو در کنار اگر من به دنبال 44؟ آره؟ 

دقیقا، من می خواهم جستجو در فرزند چپ و یا زیر درخت سمت چپ این تصویر است. و در واقع، به من اجازه دهید از طریق تصویر پایین در اینجا برای فقط یک لحظه، از من می توانم این خراش نیست. اگر من در اینجا شروع در 55، و من می دانم که ارزش 44 من به دنبال این است که در سمت چپ، آن نوع مانند پاره شدن دفترچه تلفن در نیم یا پاره شدن درخت در نیم. من دیگر در مورد مراقبت این نیمه تمام از درخت است. و در عین حال، جالب، از نظر ساختار، این چیزی بیش از اینجا که شروع می شود با 33، که خود را یک درخت جستجوی دودویی است. گفتم کلمه بازگشتی قبل به دلیل در واقع این یک ساختار داده است که توسط تعریف بازگشتی است. شما ممکن است یک درخت که این دارند بزرگ است، اما هر یک از فرزندان خود نشان دهنده یک درخت فقط یک کمی کوچکتر است. به جای آن که پدر بزرگ یا مادر بزرگ، در حال حاضر آن را فقط به مامان or-- من نمی توانم مادر نمی گویند یا پدر، خواهد بود که عجیب و غریب. به جای دو فرزند وجود دارد می خواهم برادر و خواهر و برادر است. نسل جدیدی از شجره نامه. اما ساختار، آن همان ایده است. و معلوم است من یک تابع دارند که با من می توانم یک جستجوی دودویی جستجو درخت. آن را به نام جستجو. من برای N در درخت فلش سمت چپ جستجو دیگری اگر N بزرگتر از ارزش است که من در حال حاضر در هستم. 55 در داستان یک لحظه پیش. من یک تابع به نام جستجو است که من فقط می توانید تصویب N و به صورت بازگشتی جستجو زیر درخت و فقط بازگشت هر چه که پاسخ. دیگری من مقداری در مورد پایه نهایی کردم اینجا. 

مورد نهایی چیست؟ درخت هم تهی. ارزش من هم به دنبال است کمتر از آن و یا بیشتر از و یا برابر با آن. و من می توانم بگویم برابر برابر است، اما منطقی آن معادل فقط گفت دیگری در اینجا. بنابراین درست چیزی است که چگونه پیدا کنم. بنابراین امیدوارم این است حتی به عنوان مثال قانع کننده تر از تابع سیگما احمقانه ما چند سخنرانی و عقب، که در آن بود به همان اندازه آسان به استفاده از یک حلقه به تعداد بالا تمام اعداد از یک به N. در اینجا با یک ساختار داده که خود را به صورت بازگشتی است تعریف شده و به صورت بازگشتی کشیده شده است، در حال حاضر ما از این توانایی برای بیان خود در کد است که خود را بازگشتی است. بنابراین این همان کد دقیق در اینجا است. 

پس چه مشکلات دیگر می تواند ما را حل کند؟ بنابراین یک گام سریع به دور از درختان برای فقط یک لحظه. در اینجا است، می گویند، پرچم آلمان است. و به وضوح وجود دارد الگوی این پرچم. و بسیاری از وجود دارد پرچم ها در جهان است که عنوان ساده به عنوان این در رنگ ها و الگوهای خود را. اما فرض کنید که این به عنوان یک ذخیره شده .GIF، یا JPEG، یا بیت مپ، و یا یک پینگ، هر فرمت فایل گرافیکی که با آن شما آشنا هستید، که برخی از آنها ما بازی با در PSET4. این به نظر می رسد ارزشمند به ذخیره نمی پیکسل سیاه و سفید، سیاه و سفید پیکسل، پیکسل سیاه و سفید، نقطه، نقطه، نقطه، یک دسته کامل از پیکسل سیاه و سفید برای scanline اول، و یا ردیف، و سپس یک دسته کامل از همان، سپس یک دسته کامل از همان، و سپس یک تمام دسته از پیکسل های قرمز، پیکسل های قرمز، پیکسل های قرمز، پس از آن یک کل دسته از پیکسل زرد، زرد، درست است؟ 

چنین ناکارآمدی در اینجا وجود دارد. چگونه می خواهید به طور مستقیم فشرده سازی پرچم آلمان اگر اجرای آن به عنوان یک فایل؟ مانند چه اطلاعاتی را می ما نمی زحمت ذخیره سازی بر روی دیسک به منظور کاهش اندازه پرونده ما را از مثل یک مگابایت به یک کیلوبایت، چیزی کوچکتر؟ در آن نهفته است افزونگی در اینجا روشن می شود؟ چه چیزی می تواند شما انجام دهد؟ آره؟ دقیقا. چرا به جای به یاد داشته باشید رنگ هر پیکسل رفو درست مثل شما در حال انجام در PSET4 با فرمت فایل بیت مپ، چرا شما فقط نشان دهنده ستون سمت چپ از پیکسل ها، به عنوان مثال یک دسته از پیکسل سیاه و سفید، یک دسته قرمز، و یک دسته از زرد، و پس از آن فقط به نحوی رمز ایده تکرار این 100 بار و یا تکرار این 1،000 بار؟ که در آن 100 یا 1،000 است فقط یک عدد صحیح است، بنابراین شما می توانید دور با فقط یک عدد تک به جای صدها یا هزاران نفر پیکسل های اضافی. و در واقع، این که چگونه ما می تواند پرچم آلمان فشرده سازی. و در حال حاضر حدود پرچم فرانسه چه؟ و کمی نوعی از ورزش ذهنی، که پرچم می توان بیشتر بر روی دیسک فشرده؟ پرچم آلمان یا فرانسه پرچم، اگر ما این رویکرد؟ پرچم آلمان، به دلیل وجود دارد افزونگی افقی است. و با طراحی، بسیاری از فایل های گرافیکی فرمت در واقع به عنوان خطوط اسکن کار به صورت افقی. آنها می توانند کار به صورت عمودی، فقط انسانیت سال پیش تصمیم گرفت که ما به طور کلی از همه چیز ردیف فکر می کنم ردیف به جای ستون به ستون. پس در واقع اگر شما به در فایل نگاه کنید اندازه یک پرچم آلمان و فرانسه پرچم، تا زمانی که قطعنامه است در همین حال، هم عرض و ارتفاع، این یکی در اینجا رفتن به بزرگتر، چرا که شما باید به خودتان سه بار تکرار کنید. شما باید برای مشخص آبی، تکرار خود را، سفید، خودتان را تکرار، قرمز، تکرار خودتان. شما نمی توانید فقط همه به راه به سمت راست. و از سوی دیگر، به روشن فشرده سازی در همه جا، اگر این چهار فریم از یک video-- شما ممکن است به یاد آورید که یک فیلم یا ویدئو است به طور کلی مانند 29 یا 30 فریم در ثانیه. آن را مانند یک کتاب تلنگر کوچک که در آن شما فقط ببینید تصویر، تصویر، تصویر، تصویر، تصویر فقط فوق العاده سریع پس از آن به نظر می رسد بازیگران بر روی صفحه نمایش در حال حرکت. در اینجا یک زنبور عسل سرهم بندی کردن در است بالای یک دسته از گل. و هر چند ممکن است آن را از سخت است برای دیدن در نگاه اول، تنها چیزی که در حال حرکت در این فیلم زنبور عسل است. 

چه گنگ در مورد ذخیره سازی است ویدئو غیر فشرده. این نوع از زباله برای ذخیره ویدیو به عنوان چهار عکس تقریبا یکسان است که متفاوت فقط تا آنجا که در آن زنبور عسل است. شما می توانید دور انداختن ترین از آن اطلاعات و تنها به یاد داشته باشید، برای مثال، قاب اول و آخر قاب، فریم های کلیدی اگر شما تا به حال شنیده کلمه، و فقط در فروشگاه وسط که در آن زنبور عسل است. و شما لازم نیست که ذخیره تمام از صورتی، و آبی، و ارزش سبز است. پس این است که تنها می گویند که فشرده سازی است در همه جا. این روش اغلب با استفاده از این ما و یا برای این روز داده شود. 

اما چگونه می توانم متن شما فشرده سازی؟ نظر شما در مورد فشرده سازی متن بروید؟ خوب، هر یک از شخصیت در ASCII یک بایت، یا هشت بیت است. و این نوع از گنگ، درست است؟ از آنجا که شما احتمالا نوع A و E و I و O و تو خیلی بیشتر از مثل W و یا Q و یا Z، بسته به زبان است که در آن شما در حال نوشتن قطعا. و چرا ما با استفاده از هشت بیت برای هر حرف، از جمله دست کم نامه محبوب، درست است؟ چرا بیت کمتر برای استفاده از حروف فوق العاده محبوب، مانند E، چیزهایی که شما حدس می زنم برای اولین بار در چرخ از فورچون، و استفاده از بیت های بیشتری برای حروف کمتر محبوب؟ واسه چی؟ از آنجا که ما فقط رفتن به استفاده از آنها کمتر. 

خب، معلوم است که وجود دارد تلاش برای انجام این کار بوده است. و اگر شما از درجه یاد مدرسه یا دبیرستان، کد مورس. کد مورس است نقطه و خط تیره است که می تواند منتقل شده در طول یک سیم به عنوان برای تلفن های موبایل و یا سیگنال از نوعی. اما کد مورس است فوق العاده تمیز. این نوع از سیستم دوتایی در که شما باید نقطه و یا خط تیره. اما اگر می بینید، برای مثال، دو نقطه. و یا اگر شما فکر می کنم به اپراتور که مانند بوق، بوق، بوق می رود، بوق، هدف قرار دادن یک ماشه کوچک که یک سیگنال، اگر شما، دریافت کننده، دو دریافت نقطه، شما چه پیامی دریافت کرده اند؟ کاملا خودسرانه. 

من؟ من؟ و یا چه about-- یا من؟ شاید این فقط دو حق E بود؟ پس این مشکل وجود دارد از decodability با مورس کد، به موجب آن، مگر اینکه شخص ارسال پیام شما در واقع مکث بنابراین شما می توانید از مرتب سازی بر اساس دیدن و یا شنیدن شکاف بین حروف، کافی نیست فقط به ارسال یک جریان از صفر و آنهایی که، و یا نقطه و خط تیره، چرا که ابهام وجود دارد. E یک نقطه است، بنابراین اگر شما دو نقطه دیدن و یا شنیدن دو نقطه، شاید آن را دو E یا شاید آن را یک I. است بنابراین ما نیاز به یک سیستم است که یک کمی باهوش تر از آن. بنابراین مردی به نام سال هافمن پیش تا دقیقا با این آمد. بنابراین ما فقط رفتن به یک نگاه سریع چگونه درختان وابسته به این است. فرض کنید که این چند است پیام احمقانه شما می خواهید برای ارسال، متشکل از فقط A، B، C است D'بازدید کنندگان و E، اما بسیاری از افزونگی در اینجا وجود دارد. آن را به معنای انگلیسی. آن رمزگذاری شده است. این فقط یک پیام احمقانه است با تعداد زیادی از تکرار. بنابراین اگر شما در واقع به حساب همه الف، ب، ج، D'S، و E است، در اینجا فرکانس. 20 درصد از نامه ها الف، 45٪ از حروف می E، و سه فرکانس دیگر است. ما شمارش تا به صورت دستی و فقط به ریاضی. 

پس از آن معلوم است که هافمن، چند وقت پیش، متوجه شدم که، شما می دانید چه، اگر شروع به ساختمان من یک درخت، و یا جنگل از درختان، اگر شما خواهد شد، به شرح زیر، من می توانم زیر را انجام دهید. من از رفتن به یک گره به هر از نامه ها که من در مورد مراقبت و من قصد دارم برای ذخیره در داخل آن گره فرکانس به عنوان یک نقطه شناور ارزش، یا شما می توانید آن را به یک N استفاده کنید، بیش از حد، اما ما فقط در اینجا استفاده از یک شناور. و الگوریتم است که او پیشنهاد این است که شما این جنگل از تک گره درختان، درختان فوق العاده کوتاه، و شما شروع به اتصال آنها را با گروه های جدید، پدر و مادر جدید، اگر شما خواهد شد. و شما این کار را با انتخاب دو کوچکترین فرکانس در یک زمان. بنابراین من 10٪ و 10٪ و جو در زمان. من یک گره جدید است. و من پاسخ به گره جدید 20٪. 

که دو گره با هم ترکیب کنیم؟ این کمی مبهم است. بنابراین برخی از موارد گوشه ای به وجود نظر است، اما به نگه داشتن چیزهای زیبا، من قصد دارم به را انتخاب کنید 20٪ - من در حال حاضر کودکان را نادیده گرفت. من قصد دارم به را انتخاب کنید 20٪ و 15٪ و دو لبه جدید قرعه کشی. و در حال حاضر که دو گره من منطقی ترکیب؟ چشم پوشی از همه کودکان، همه نوه، فقط در ریشه نگاه اکنون. که دو گره با هم کراوات من؟ نقطه دو و 0.35. بنابراین اجازه دهید من در قرعه کشی دو لبه است. و پس از آن من تنها یک سمت چپ است. بنابراین در اینجا یک درخت. و آن را به عمد کشیده شده است به نگاه نوع زیبا، اما توجه کنید که لبه دارند همچنین صفر و یک برچسب شده است. پس همه از سمت چپ لبه صفر هستند خودسرانه، اما به طور مداوم. تمام لبه های راست آنهایی هستند. 

و بنابراین، آنچه هافمن پیشنهاد شده است، اگر شما می خواهید برای نشان دادن یک B، به جای نشان دهنده تعداد 66 عنوان اسکی است که هشت بیت کل، شما می دانید چه، فروشگاه فقط الگوی صفر، صفر، صفر، صفر، چرا که مسیر را از درخت من، درخت آقای هافمن، به برگ از ریشه. اگر شما می خواهید برای ذخیره یک E، در مقابل، نمی ارسال هشت بیت است که نشان دهنده E. در عوض، ارسال چه الگوی بیت؟ یکی. و چه خوب در مورد این است که E نامه محبوب ترین است، و شما با استفاده از کوتاه ترین کد برای آن است. بعدی محبوب ترین نامه به نظر می رسد مانند آن A. بود و چگونه بسیاری از بیت او با استفاده از پیشنهاد که؟ صفر، یک. 

و چون آن را اجرا عنوان این درخت، در حال حاضر اجازه دهید من وجود دارد تصریح هیچ ابهامی در مورس کد، چرا که همه از نامه شما در مورد مراقبت در پایان این گوشه می باشد. به طوری که فقط یک استفاده از یک درخت. این is-- و من موج دست من در این که چگونه شما ممکن است این به عنوان یک ساختار C پیاده سازی. ما فقط نیاز به ترکیب یک نماد، مانند یک کاراکتر، و فرکانس در چپ و راست. اما اجازه دهید در دو نگاه نمونه نهایی است که شما گرفتن کاملا آشنا با پس مسابقه صفر در مجموعه ای مشکل پنج. 

بنابراین ساختار داده ها وجود دارد شناخته شده به عنوان یک جدول هش. و یک جدول هش نوع خنک در آن است که سطل. و فرض چهار سطل وجود دارد در اینجا، فقط چهار فضاهای خالی. در اینجا یک دسته کارت، و در اینجا است باشگاه، بیل زدن، باشگاه، الماس، باشگاه، الماس، باشگاه، الماس، clubs-- این است که به صورت تصادفی. قلب، hearts-- بنابراین من bucketizing همه از ورودی است. و یک جدول هش نیازهای به در ورودی خود را نگاه کنید، و سپس آن را در یک خاص قرار مشخصات، بر اساس آنچه می بینید. این الگوریتم است. و من با استفاده از فوق العاده الگوریتم های بصری ساده است. سخت ترین قسمت بود که به خاطر سپردن آنچه در تصاویر بود. و پس از آن چهار مجموع چیزها وجود دارد. 

در حال حاضر پشته، در حال رشد بودند که یک چیز طراحی عمدی در اینجا است. اما چه چیز دیگری ممکن است انجام دهم؟ پس در واقع در اینجا ما یک دسته از کتاب آزمون مدرسه قدیمی. فرض کنید که یک دسته از نام دانش آموزان در اینجا. در اینجا یک جدول هش بزرگتر است. به جای چهار سطل، من، اجازه دهید بگویم 26. و ما نمی به قرض 26 همه چیز از خارج [؟ آننبرگ؟]، به طوری که در اینجا پنج است که نشان دهنده A تا Z. و اگر من یک دانش آموز که نام با یک شروع می شود را مشاهده کنید، من قصد دارم به او و یا مسابقه او قرار داده است. اگر کسی با C شروع می شود، بیش از وجود دارد، A-- در واقع، نمی خواهم به انجام این کار. B می رود بیش از اینجا. بنابراین من A و B و C و در حال حاضر اینجا دانش آموز دیگری است. اما اگر این جدول هش اجرا با یک آرایه، من از پیچ نوع در این نقطه، درست است؟ من از نوع نیاز به قرار دادن این جایی. 

بنابراین یکی از راه حل من می توانم این است، همه درست است، یک مشغول است، B مشغول است، C مشغول است. من قصد دارم به او را در D. بنابراین در اول، من با دسترسی تصادفی فوری به هر یک از سطل برای دانش آموزان است. اما در حال حاضر این نوع از محول به چیزی خطی، چرا که اگر من می خواهم به جستجو برای کسی نام و نام خانوادگی که شروع می شود با، من اینجا چک کنید. اما اگر این است که A نمی دانش آموز من به دنبال، من نوعی باید شروع به چک سطل، زیرا آنچه من مرتب کردن بر اساس خطی بود بررسی ساختار داده ها. یک راه احمقانه گفتن فقط نگاه برای اولین باز در دسترس است، قرار داده و به عنوان یک طرح B، پس به صحبت می کنند، و یا طرح D در این مورد، ارزش در آن مکان به جای. این فقط به طوری که اگر شما 26 مکان و دانش آموزان رو با نام Q و یا Z، یا چیزی شبیه به که، حداقل شما با استفاده از فضا. 

اما ما در حال حاضر دیده تر راه حل های هوشمندانه در اینجا، درست است؟ چه کار می کنید به جای اگر شما یک برخورد؟ اگر دو نفر نام A، آنچه را که یک هوشمندانه تر و یا شده راه حل بصری از قرار دادن یک که در آن D قرار است به؟ چرا من فقط خارج [؟ آننبرگ؟]، مانند از malloc، گره دیگر، آن را در اینجا، و سپس قرار دادن که یک دانش آموز است. به طوری که من اساسا نوعی از یک آرایه، و یا شاید به زیبایی بیشتر به عنوان ما شروع به دیدن یک لیست پیوندی. 

و به این ترتیب یک جدول هش یک ساختار است که می تواند فقط شبیه به این، اما هوشمندانه تر، شما چیزی به نام زنجیره جداگانه، به موجب آن یک جدول هش کاملا به سادگی یک آرایه است، هر یک از که عناصر یک عدد نیست، به خودی خود یک لیست پیوندی است. به طوری که شما دسترسی فوق العاده سریع تصمیم گیری که در آن به هش ارزش خود را به. بسیار شبیه با مثال کارت، من تصمیم فوق العاده سریع ساخته شده است. قلب در اینجا می رود، الماس در اینجا می رود. در اینجا همان، A در اینجا می رود، D در اینجا می رود، B در اینجا می رود. بنابراین فوق العاده سریع نگاه یو پی اس، و اگر شما اتفاق می افتد به اجرا را به یک مورد برخورد که در آن شما را کردم، دو مردم با همین نام، و سپس شما فقط شروع به ارتباط آنها با هم. و شاید شما آنها را طبقه بندی شده اند حفظ بر اساس حروف الفبا، شاید شما نمی کنند. اما حداقل در حال حاضر ما پویایی است. بنابراین در یک طرف ما فوق العاده سریع زمان ثابت، و نوع زمان خطی درگیر اگر این لیست های پیوندی شروع به گرفتن یک کمی طولانی است. 

بنابراین این نوع از احمقانه، سال شوخی نخبه پیش. در CS50 هک مراسم، هنگامی که دانش آموزان بررسی در، برخی TF یا CA هر سال فکر می کند آن را خنده دار قرار داده تا نشانه شبیه به این، که در آن فقط معنی است که اگر نام خود را شروع می شود با A، رفتن در این راه. اگر نام شما شروع می شود با B، به this-- OK، این خنده دار است شاید بعدا در ترم. اما یکی دیگر از وجود دارد راه های انجام این، TOO. بازگشت به که. 

بنابراین این ساختار وجود دارد. و این است که ما آخرین ساختار برای امروز، که چیزی به نام یک درخت پیشوندی است. T-R-I-E، که برای برخی از دلیل کوتاه است برای بازیابی، اما آن را به نام درخت. بنابراین یک درخت پیشوندی دیگر جالب است ملغمه ای از بسیاری از این ایده ها. این یک درخت، که ما قبل از دیده ام. این یک درخت جستجوی دودویی نیست. این یک درخت با هر تعداد از کودکان، اما هر یک از کودکان در یک درخت پیشوندی یک آرایه است. آرایه ای از اندازه، می گویند، 26 و یا شاید 27 اگر شما می خواهید برای پشتیبانی از نام hyphenated و یا آپوستروف در نام مردم است. 

و بنابراین این یک ساختار داده است. و اگر شما از بالا نگاه به پایین، مانند اگر شما در گره بالا وجود دارد، M نگاه کنید، با اشاره به سمت چپ چیز وجود دارد، که سپس A، X، W، E، L، L. این است فقط یک ساختار داده که خودسرانه ذخیره سازی نام افراد. و ماکسول است تنها با زیر ذخیره می شود یک مسیر از آرایه به آرایه به آرایه. اما آنچه شگفت انگیز در مورد یک درخت پیشوندی است که، در حالی یک لیست پیوندی و حتی یک آرایه، بهترین ما تا کنون بدست است زمان خطی یا زمان لگاریتمی به دنبال کسی که. در این ساختار داده ها از یک درخت پیشوندی، اگر ساختار داده ها من یک نام در آن و من به دنبال ماکسول، من رفتن به او را پیدا کنید خیلی سریع. من فقط برای M-A-X-W-E-L-L است. اگر این ساختار داده، در مقابل، اگر n یک میلیون نفر است، اگر یک وجود دارد میلیون نام در این ساختار داده ها، ماکسول است که هنوز هم برای رفتن به کشف تنها پس از M-A-X-W-E-L-L مراحل. و مراحل David-- D-A-V-I-D. به عبارت دیگر، با ساخت یک ساختار داده که کردم همه از این آرایه، همه از آن خود حمایت از دسترسی تصادفی، من می توانم شروع به دنبال کردن مردم نام استفاده از مقدار زمان که متناسب با تعداد نیست از چیزهایی که در ساختار داده ها، مانند یک میلیون نام موجود است. مقدار زمان آن را به من طول می کشد تا M-A-X-W-E-L-L در این ساختار داده است متناسب نیست به اندازه ساختار داده ها، اما به طول نام. و در واقع نام ما به دنبال تا هرگز به دیوانه طولانی باشد. شاید کسی دارای یک شخصیت 10 نام، نام شخصیت 20. این قطعا محدود، درست است؟ یک انسان بر روی زمین وجود دارد که دارای طولانی ترین نام ممکن است، اما که نام یک ثابت است طول ارزش، درست است؟ این کار در هر حس تغییر نمی کند. بنابراین در این روش، ما به دست آورد یک ساختار داده که زمان ثابت نگاه کردن است. آن را می کند تعدادی از مراحل بسته به طول ورودی، اما نه تعداد نام در ساختار داده ها. بنابراین اگر ما تعدادی از نام های دو برابر سال آینده از یک میلیارد به دو میلیارد، یافته ماکسول می گذرد را به به همان تعداد دقیق هفت مرحله به او پیدا کنید. و بنابراین ما به نظر می رسد به دست آورد جام مقدس ما از زمان حال اجرا است. 

بنابراین چند اطلاعیه ها سریع. مسابقه صفر در حال آمدن است. بیشتر در مورد که در وب سایت درس در طی چند روز آینده. روز دوشنبه lecture-- آن یک روز تعطیل است در اینجا در دانشگاه هاروارد در روز دوشنبه. آن را در نیوهیون نیست، بنابراین ما در حال گرفتن کلاس به پناهگاه جدید برای سخنرانی در روز دوشنبه. همه چیز فیلم برداری خواهد و جریان به طور معمول زندگی می کنند، اما اجازه دهید امروز به پایان با یک کلیپ 30 ثانیه به نام "افکار عمیق" توسط Daven فرنهام که سال گذشته روز شنبه الهام گرفته شده بود "افکار عمیق" شب زنده توسط جک دستی، که در حال حاضر باید حس. 

فیلم: در حال حاضر، "عمیق افکار "توسط Daven فرنهام. جدول هش. 

SPEAKER 1: همه حق است، که آن را در حال حاضر. ما شما را هفته آینده را ببینید. 

داگ: برای دیدن آن در عمل است. بنابراین اجازه دهید نگاهی به که در حال حاضر. بنابراین در اینجا، ما یک آرایه نامرتب. 

ایان: داگ، می تواند شما را به جلو و راه اندازی مجدد این فقط برای یک لحظه لطفا همه حق است، دوربین دارن، بنابراین عمل هر زمان که شما آماده، داگ هستید، خوب است؟ داگ: همه حق است، بنابراین آنچه که ما در اینجا یک آرایه نامرتب است. و من تمام عناصر رنگی ام قرمز به نشان می دهد که در آن است، در واقع، نامرتب. پس به یاد آورید که اولین چیزی که ما انجام می دهیم این است که ما در نیمه سمت چپ آرایه مرتب کردن. سپس ما حق مرتب سازی بر اساس نیمی از آرایه. و بله، دا، بله، دا، بله، DA، ما آنها را با هم ادغام خواهند شد. و ما باید یک آرایه به طور کامل طبقه بندی شده اند. بنابراین این که چگونه ادغام مرتب سازی بر کار می کند. 

ایان: هی، هی، هی، برش، برش، برش، برش. داگ، شما نمی توانید فقط از ya-DA، بله، DA، بله، DA، راه خود را از طریق مرتب سازی بر ادغام. 

داگ: من فقط. این خوبه. ما خوب به آن بروید. اجازه دهید فقط نورد نگه دارید. پس به هر حال، 

ایان: شما باید به توضیح این به طور کامل بیشتر از آن. که فقط کافی نیست. داگ: ایان، ما نمی نیاز به رفتن به یک است. این خوبه. پس به هر حال، اگر ما با merge-- ادامه یان، ما در وسط فیلمبرداری است. 

ایان: من می دانم. و ما نمی توانیم فقط از ya-DA، بله، DA، بله، DA، از طریق تمام مراحل. شما باید برای توضیح دهد که چگونه دو طرف از هم ادغام شدند. 

داگ: اما ما در حال حاضر چگونه دو sides-- توضیح داد 

ایان: شما فقط نشان داده ایم آنها یک آرایه ادغام. داگ: آنها می دانند که این فرآیند است. آنها خوب است. ما بیش از ده بار رفته است. 

ایان: شما فقط حق بر آن قلم. ما در حال رفتن به یک، شما می تواند به شما بله، دا، بله، دا بیش از آن. همه حق است، به یکی. 

داگ: من برای رفتن به عقب از طریق تمام اسلاید؟ خدای من. آن را مانند ششمین بار، ایان است. این خوبه. 

ایان: بسیار خوب. آماده ای؟ عالی. عمل.