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

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

بنابراین دستور کار امروز همه چیز در مورد ساختمان داده. بعضی از این فقط رفتن به فقط برای دریافت شما با این آشنا. ممکن است شما تا به حال اجرا آنها در این کلاس. برخی از آنها به شما خواهد شد، مانند برای pset کتاب املاء خود را. 

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

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

بنابراین با توجه به، ما آغاز شده است. و همچنین، آزمونها yes--. من فکر می کنم بیشتر از شما که در هستند بخش من آزمونها خود را، اما هر کسی می آید و یا در برخی از دلایل شما نمی کنند، آنها حق در اینجا در مقابل هستید. 

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

پس چرا ما را انتخاب کنید ممکن است لیست پیوندی بیش از یک آرایه؟ چه آنها را متمایز می کند؟ بله؟ 

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

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

SPEAKER 1: درست است. بنابراین با arrays-- 

رسید [نامفهوم]. 

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

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

و در این مورد، برخی از گره که یک عدد صحیح در خود نگه دارد. و پس از آن چه بخش دوم در اینجا؟ هر کسی؟ 

رسید [نامفهوم]. 

SPEAKER 1: آره. این یک اشاره گر به گره بعدی است. پس این در واقع باید اینجا باشد. این یک اشاره گر از نوع است گره به چیزی که بعد از. و این چیزی است که آنها شامل گره های ما. سرد. 

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

همه حق است، به آنها توجه کنیم. آن را دنبال کنید. آیا این شامل تعداد 9؟ شماره دنبال یک بعدی. 

بنابراین ما باید به واقع تکرار از طریق لیست پیوندی ما. ما نمی توانیم فقط به طور مستقیم به که در آن 9 است. و اگر شما بچه ها در واقع می خواهند به برخی از شبه کد نام وجود داشته است. ما برخی از تابع جستجو در اینجا که طول می کشد in-- چه در می برد؟ شما چه فکر میکنید؟ یکی بسیار آسان است. این چیست؟ رسید [نامفهوم]. SPEAKER 1: تعداد ما به دنبال. درست است؟ و آنچه را که از این به مطابقت دارد؟ این یک اشاره گر به چیست؟ 

رسید گره. 

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

و در حالی که آن را NULL نیست، در حالی که ما هنوز هم چیزهایی در لیست ما، چک کنید اگر که گره تعداد ما به دنبال. بازگشت درست است. در غیر این صورت، آن را بروز رسانی، درست است؟ 

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

بنابراین با درج، شما سه راه مختلف. شما می توانید prepend، شما می توانید اضافه و شما می توانید وارد به همه فن حریف. در این مورد، ما رفتن به انجام prepend. آیا کسی می داند که چگونه کسانی که سه مورد ممکن است متفاوت باشد؟ 

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

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

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

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

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

اما مجدد شما اشاره گر را در جهت درست در حال رفتن به بسیار، بسیار برای این pset مهم است. در غیر این صورت، شما در حال رفتن به یک رشته هش جدول و یا سعی کنید که فقط رفتن به تنها بخشی از کلمات که شما می خواهید و سپس mmhmm you're--؟ رسید چه موقت بود چیزی که ذخیره سازی شما صحبت کردن در مورد؟ SPEAKER 1: ذخیره سازی موقت. بنابراین اساسا دیگر راه شما می توانید این کار را انجام ذخیره شده است سر از چیزی مثل متغیر موقت ذخیره آن. انتساب آن را به 1 و پس از آن به روز رسانی 1 به نقطه به هر سر استفاده می شود به نقطه را به. به این ترتیب واضح است زیبا تر به خاطر شما یک مقدار به طور موقت لازم نیست، اما فقط ارائه راه دیگری برای آن انجام دهد. و ما در واقع انجام برخی از کد برای این. بنابراین برای لیست پیوندی، ما در واقع برخی از کد داشته باشد. بنابراین در اینجا وارد است، این است prepending. پس این را وارد در سر. 

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

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

رسید آیا ما به مقداردهی اولیه بعدی جدید به NULL اول، و یا می تواند ما فقط آن را مقداردهی اولیه به سر؟ 

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

OK، بنابراین در حال حاضر لیست مضاعف مرتبط است. چه فکر می کنم ما؟ چه با مختلف لیست مضاعف مرتبط است؟ 

بنابراین در لیست های پیوندی ما، ما می توانیم تنها در یک جهت حرکت می کند، درست است؟ ما فقط در کنار داشته باشد. ما فقط می توانیم به جلو بروید. 

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

گره بنابراین مضاعف مرتبط، بسیار مشابه، درست است؟ تنها تفاوت این است در حال حاضر ما یک بعدی و قبلی. این تنها تفاوت است. 

بنابراین اگر ما به prepend یا append-- ما هیچ کد برای این نیست تا here-- اما اگر شما را امتحان کنید و درج آن، نکته مهم این است که شما نیاز به ایجاد مطمئن شوید که شما تعیین هر دو قبل و خود شما اشاره گر بعدی به درستی. بنابراین در این مورد، شما را نه تنها بعد مقداردهی اولیه، شما مقداردهی اولیه قبلی. اگر ما در سر لیست، ما نه تنها سر برابر جدید، اما باید قبل جدید ما اشاره به سر، درست است؟ 

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

OK، بنابراین جداول هش. این است که احتمالا بیشتر کمی مفید برای pset شما در اینجا دلیل این که شما در حال رفتن به اجرای یکی از این، یا امتحان کنید. من واقعا جداول هش می خواهم. آنها بسیار سرد است. 

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

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

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

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

آیا لازم نیست به خود شما. برخی از آنهایی که واقعا سرد وجود دارد از وجود دارد که همه انواع ریاضی دیوانه. و اگر می خواهید مطمئن شما غلط گیر املا فوق العاده سریع، من قطعا به یکی از آن نگاه کنید. 

بلکه وجود دارد آنهایی که ساده مانند محاسبه از مجموع کلمات، مانند هر حرف دارای یک عدد است. محاسبه مجموع. که تعیین سطل. آنها همچنین آنهایی که آسان درست مثل همه در اینجا، همه از B را در اینجا. هر یکی از آن. 

در واقع، آن را فقط به شما می گوید که اندیس عنصر شما باید وارد. فقط تصمیم گیری bucket-- این همه یک تابع هش است. بنابراین در اینجا ما یک مثال است که فقط اولین حرف رشته که من فقط در مورد صحبت شد. 

بنابراین شما باید برخی از هش که فقط حرف اول رشته خود را منهای A، که به شما برخی را عدد بین 0 و 25. و آنچه که می خواهید انجام دهید این است مطمئن شوید که این نشان دهنده اندازه هش خود را table-- چگونه بسیاری از سطل وجود دارد. با بسیاری از این توابع هش، آنها رفتن به برگرداندن داده که ممکن است بسیار بالاتر از تعداد سطل شود که شما در واقع در جدول هش خود، بنابراین شما نیاز به ایجاد مطمئن و وزارت دفاع توسط کسانی که. در غیر این صورت، آن را می گویند، آه، آن را باید در سطل 5000 است اما شما فقط 30 دارند سطل در جدول هش شما. و البته، همه ما می دانیم که رفتن به منجر به برخی از اشتباهات دیوانه. بنابراین مطمئن شوید که به وزارت دفاع توسط اندازه جدول هش شما. سرد. بنابراین برخورد. آیا همه خوب تا کنون؟ Mmhmm؟ 

رسید: چرا آن را چنین ارزش های عظیم بازگشت؟ 

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

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

بنابراین سوال این است، چه ما در این مورد انجام دهید؟ چه کنیم؟ ما در حال حاضر چیزی وجود دارد؟ آیا ما فقط آن را دور بریزید؟ 

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

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

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

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

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

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

رسید بنابراین جدول هش تا به اندازه از پیش تعیین شده، مانند یک [نامفهوم] سطل؟ 

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

پس هر کس OK وجود دارد؟ همه راست. آه. چه اتفاقی افتاده؟ واقعا در حال حاضر. حدس می زنم کسی به من کشتن. 

OK ما در حال رفتن به رفتن به تلاش می کند، که یک کمی دیوانه هستند. من جداول هش می خواهم. من فکر می کنم آنها واقعا سرد است. تلاش ها سرد است، بیش از حد. 

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

رسید که برای یک درخت بازیابی. 

SPEAKER 1: آره. این یک درخت بازیابی است. بسیار جذاب است. بنابراین یک چیز متوجه هستند که ما به دنبال شخصیت های منحصر به فرد در اینجا، درست است؟ 

بنابراین قبل از تابع هش را با ما، ما در کلمات به عنوان یک کل نگاه می شد، و در حال حاضر ما به دنبال تر در حرف، درست است؟ بنابراین ما باید ماکسول اینجا و مندل. بنابراین اساسا try-- راه به فکر می کنم در مورد این که هر سطح در اینجا است مجموعه ای از حروف است. بنابراین این گره ریشه خود را در اینجا، درست است؟ این همه حرف از ای بی سی برای شروع هر کلمه. 

و آنچه که می خواهید انجام دهید این است بگو، OK، ما باید برخی از کلمه M. ما قصد داریم برای ماکسول نگاه کنید، به طوری که ما به M. M و نقطه رفتن به یک کل دیگر یک آرایه که در آن هر کلمه، تا زمانی که وجود دارد یک کلمه است که است عنوان نامه دوم، تا زمانی که یک کلمه ای که وجود دارد است B به عنوان نامه دوم، آن را به یک اشاره گر دارند رفتن به برخی از آرایه بعدی. 

احتمالا وجود ندارد کلمه ای که MP چیزی، بنابراین در موقعیت P در این آرایه، آن را فقط NULL باشد. این امر می گویند، OK، هیچ کلمه ای وجود دارد است که M به دنبال P، OK؟ بنابراین اگر ما در مورد آن، هر فکر یکی از این چیزها کوچکتر است که در واقع یکی از این آرایه های بزرگ از طریق Z. پس چه ممکن است یکی از چیزهایی که این نوع از اشکال امتحان کنید؟ 

رسید مقدار زیادی از حافظه. 

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

اما آنها بسیار سریع می باشد. بنابراین سرعت باور نکردنی اما واقعا فضای ناکارآمد. نوع باید به شکل که یکی از شما می خواهید. این واقعا سرد برای pset خود را، اما آنها را تا مقدار زیادی از حافظه، بنابراین شما معامله خاموش است. آره؟ 

رسید آیا امکان آن وجود داشته باشد برای راه اندازی یک امتحان کنید و پس از آن هنگامی که شما همه داده ها در آن است که شما need-- من نمی دانم اگر آن را حس کند. من خلاص شدن از همه بود شخصیت های NULL، اما بعد از آن شما نمی قادر خواهد بود تا شاخص them-- 

SPEAKER 1: شما هنوز به آنها نیاز دارید. 

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

خوب، پس این همان چیزی است. در حالی که در یک لیست پیوندی، اصلی ما نوع of-- چه کلمه من می خواهم به - مانند ساختمان بلوک گره بود. در را امتحان کنید، ما نیز یک گره داشته باشد، اما آن را متفاوت تعریف شده است. 

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

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

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

بنابراین ما در حال رفتن را از طریق رفتن پیدا کردن "بت" در این را امتحان کنید. بنابراین در بالا شروع شود، درست است؟ و ما می دانیم که ب مربوط به شاخص دوم، عنصر دوم در این آرایه، به خاطر A و B. بنابراین حدود یک ثانیه. 

و آن را می گوید، OK، سرد، به دنبال که به آرایه بعدی، چرا که اگر ما به یاد داشته باشید، آن است که هر یک از این نمی در واقع حاوی عنصر. هر یک از این آرایه ها شامل یک اشاره گر، درست است؟ این یک تمایز مهم را دارد. 

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

پس ما در این مورد ب، که شاخص دوم ما است. اگر ما تا به حال، می گویند، C و یا D یا هر حرف دیگر، ما نیاز به نقشه که قدمت آن به شاخص از آرایه ما است که که مربوط به. بنابراین ما می خواهیم را rchar و ما فقط تفریق کردن به آن نقشه را به 0 تا 25. همه خوب چگونه ما نقشه شخصیت ما؟ OK. 

بنابراین ما به یک دوم و ما به می بینیم که، بله، آن است که به NULL نیست. ما می توانیم در این آرایه بعدی حرکت می کند. بنابراین ما در این آرایه بعدی اینجا بروید. 

و ما می گوییم، خوب، در حال حاضر ما نیاز به مراجعه در صورت است که در اینجا. آیا پوچ و یا آن را ندارد در واقع رو به جلو حرکت می کند؟ بنابراین در واقع حرکت می کند به جلو در این آرایه. و ما می گویند، OK، T آخرین نامه ما است. بنابراین ما به T در صفحه اول بروید. و بعد ما حرکت رو به جلو چرا که یکی دیگر وجود دارد. و این یکی می گوید اساسا که، بله، آن را می گوید که یک کلمه وجود دارد here-- که اگر این را دنبال راه رسیدی در یک کلمه، که ما می دانیم "خفاش" است. بله؟ 

رسید آیا این استاندارد است که این به عنوان شاخص 0 و پس از آن نوعی در 1 و یا در پایان دارند؟ 

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

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

بنابراین یک راه برای انجام that-- اوه، ببخشید، این یکی. بنابراین در این مورد، "باغ وحش" است یک کلمه است، اما آن را در تلاش های ما است. اما در این یکی، می گویند که ما آن را می خواهم معرفی کلمه "حمام"، چه اتفاقی می افتد این است که ما به دنبال through-- B، A، T. ما در این مجموعه، و ما به جستجو برای ساعت رفتن. 

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

و ما می گویند، OK، Z. Z در این وجود دارد، و آن را انجام می دهد. بنابراین شما در حال حرکت به آرایه بعدی خود، OK؟ و سپس در یک بعدی، ما می گوییم، خوب، نمی ای وجود دارد؟ آن را ندارد. این دوباره. 

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

رسید پس می کند که این معنی است که "کارشناسی" یک کلمه نیز می باشد؟ 

SPEAKER 1: شماره بنابراین در این مورد، "کارشناسی" ما را دریافت در اینجا، ما می گویند این است که آن یک کلمه، و آن را هنوز هم هیچ است. OK؟ Mmhmm؟ 

رسید بنابراین هنگامی که شما آن را کلمه و به شما می گویند بله، سپس آن را شامل رفتن به متر؟ 

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

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

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

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

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

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

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

رسید صبر کنید، بنابراین شما باید 26 حروف در هر یک؟ 

SPEAKER 1: Mmhmm. بله، شما باید 26. شما باید برخی از نشانگر کلمه و پس از آن است شما باید اشاره گر 26 در هر یک. و آنها point-- 

رسید و هر 26، آنها هر کدام 26؟ 

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

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

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

هر چیزی در here-- پایین در بسیار، بسیار bottom-- برگ در نظر گرفته شده. پس از آن همراه با چیزی که تمامی درخت، درست است؟ برگ در لبه های درخت خود را می باشد. 

و سپس ما نیز یک زن و شوهر از نظر در مورد گره در رابطه با بحث به هر یک از دیگر. بنابراین ما باید پدر و مادر، کودکان، و خواهر و برادر. بنابراین در این مورد، 3 است پدر و مادر از 5، 6، و 7. بنابراین پدر و مادر است هر چه باشد یک مرحله بالاتر از هر آنچه که شما هستید با اشاره به، به طوری که فقط مثل یک شجره نامه. خوشبختانه، این همه کمی است کمی درک تر از تلاش می کند. 

خواهر و برادر هستند هر که پدر و مادر همان، درست است؟ آنها در همان سطح در اینجا. و پس از آن، به عنوان من بود گفت: کودکان تنها هر یک قدم زیر است گره مورد نظر، OK؟ سرد. بنابراین یک درخت دودویی. هر کسی می تواند خطر حدس بر روی یکی از ویژگی های درخت دودویی؟ 

رسید حداکثر دو برگ. 

SPEAKER 1: درست است. بنابراین حداکثر دو برگ. بنابراین در این یکی قبل از ما این بود که تا به حال سه، اما در یک درخت دودویی، شما باید حداکثر دو کودکان در هر پدر و مادر، درست است؟ یکی دیگر وجود دارد ویژگی جالب است. آیا کسی می داند که؟ درخت دودویی. 

بنابراین یک درخت دودویی خواهد همه چیز در the-- این یکی نمی sorted-- اما در یک درخت دودویی طبقه بندی شده اند، همه چیز را در سمت راست بیشتر از پدر و مادر است، و همه چیز را در سمت چپ کمتر از پدر و مادر است. و است که یک مسابقه سوال قبل، خیلی خوب می دانند. پس راه این تعریف می کنیم، دوباره، ما گره دیگر. این به نظر می رسد بسیار شبیه به چه چیزی؟ مضاعف 

رسید لینک لیست 

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

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

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

OK، پشته. و نیز، آن را مانند به نظر می رسد ما ممکن است یک کمی از زمان داشته باشد. اگر ما، من خوشحال میرم بیش از هر یک از این دوباره. خوب، پس پشته. آیا کسی به یاد داشته باشید آنچه که stacks-- هر ویژگی های یک پشته؟ 

OK، بنابراین بسیاری از ما، من فکر می کنم، غذا خوردن در ناهار خوری halls-- تا آنجا که ممکن است ما را به دوست ندارند. اما بدیهی است، شما می توانید از یک پشته فکر می کنم به معنای واقعی کلمه فقط به عنوان یک پشته از سینی و یا یک پشته از همه چیز. و آنچه که مهم است برای تحقق بخشیدن به این است که آن را something-- مشخصه که ما آنرا by-- LIFO می باشد. آیا کسی می داند که چه چیزی برای ایستد؟ Mmhmm؟ 

رسید در آخرین، اولین بار. 

SPEAKER 1: راست، در آخرین، اولین بار. بنابراین اگر ما می دانیم، اگر ما انباشته چیز تا، ساده ترین چیزی که برای گرفتن off-- و شاید تنها چیزی که ما می توانیم با شتاب خاموش اگر پشته ما enough-- بزرگ است که عنصر بالا است. بنابراین هر آنچه در قرار داده شد last-- که ما در اینجا مشاهده می کنید، هر رانده شد در اکثر recently-- است رفتن به اولین چیزی که ما پاپ کردن، OK؟ 

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

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

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

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

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

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

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

رسید [نامفهوم]. SPEAKER 1: بررسی برای اندازه؟ اندازه. بنابراین ما می خواهیم به بررسی کنید اندازه ما بزرگتر از 0 است، OK؟ و اگر چنین باشد، پس از آن ما می خواهیم به کاهش اندازه خود را با 0 و بازگشت است. چرا؟ 

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

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

رسید من فقط به طور کلی حدس می زنم، چرا این ساختار داده ها مفید باشد؟ 

SPEAKER 1: این متن شما بستگی دارد. بنابراین برای برخی از نظریه، اگر شما در حال کار with-- OK، به من اجازه دیدن یک یک مفید وجود دارد که به بیش از خارج مفید است از CS. با پشته، هر زمان که شما نیاز دارید برای پیگیری چیزی است که است اخیرا اضافه شده است زمانی که شما در حال رفتن به می خواهید به استفاده از یک پشته. 

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

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

بنابراین یک صف. اساسا یک صف است مانند یک خط است. شما بچه ها من استفاده مطمئن از این روزمره هستم، فقط در غذاخوری ما می خواهم. بنابراین ما باید به در و سینی ما، من اطمینان حاصل کنید که در صف انتظار به کش رفتن و یا مواد غذایی خود را. 

بنابراین تفاوت در اینجا این است که این FIFO است. بنابراین اگر LIFO گذشته در بود، برای اولین بار از، FIFO است برای اولین بار در، اولین بار. پس این است که هر آنچه شما قرار داده در اول شما مهم است. بنابراین اگر شما در انتظار بودند در line-- می تواند به شما تصور کنید اگر شما به رفت رم آی فون جدید و آن را به یک پشته بود که در آن آخرین فرد خط اول آن را کردم، مردم یکدیگر را می کشند. 

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

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

رسید یکی از اولین. 

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

این نوع مانند من گفتن شما بچه ها، اگر شما برای باز کردن یک فایل، شما باید برای null به. با هر یک از این دسته و صف، شما باید برای دیدن اگر فضا وجود دارد زیرا ما برخورد با یک آرایه اندازه ثابت، به ما می بینیم here-- 0، 1 تمام تا 5. بنابراین آنچه که ما در این مورد انجام چک است برای دیدن اگر ما هنوز هم فضای دارند. آیا اندازه ما کمتر از ظرفیت؟ 

اگر چنین است، ما نیاز به ذخیره سازی آن در دم و ما به اندازه ما را به روز. پس چه ممکن است دم در این مورد خواهد بود؟ این صراحت نوشته شده است. چگونه آن را ذخیره کنیم؟ دم چه خواهد بود؟ 

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

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

رسید که آیا معنی است که ما می توانست یک آرایه اعلام کرد که پنج عنصر بلند بود و پس از آن ما در حال اضافه کردن بر روی آن؟ 

SPEAKER 1: شماره بنابراین در این مورد، این است که یک پشته است. این امر می تواند به اعلام به عنوان آرایه ای از اندازه 6. و در این مورد، ما فقط باید یک فضای سمت چپ. 

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

OK، بنابراین thing-- آه، این گچ وحشتناک است. یک چیز را به در نظر گرفتن مورد است. ما فقط انجام پنج. OK، بنابراین ما در حال رفتن به می گویند سر است که در اینجا. این 0، 1، 2، 3، 4 می باشد. 

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

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

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

پس این در واقع شما یک راه برای انجام آن به شما بدهد. از آنجا که در این مورد، چه؟ سر ما این است که در 1، اندازه ما 4 است. اگر ما وزارت دفاع که توسط 5، ما 0، که جایی است که ما باید ورودی آن است. 

بنابراین پس از آن در مورد آینده، اگر ما برای انجام این کار، ما می گوییم، خوب، اجازه دهید چیزی dequeue. ما این dequeue. ما را از این عنصر، درست است؟ 

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

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

بنابراین این فرمول این است که چگونه شما محاسبه دم خود را. آیا که حس می کند؟ OK. OK، dequeue، و پس از آن شما بچه ها باید 10 دقیقه به من هر گونه سوال روشن بپرسید شما می خواهید، زیرا من می دانم که این دیوانه. 

همه حق است، به طوری که در همان way-- من نمی دانم اگر شما بچه ها متوجه شده، اما CS همه چیز در مورد الگوهای است. همه چیز خیلی همان، فقط با ترفند کوچک. بنابراین همان چیزی که در اینجا. ما نیاز به چک کنید اگر ما در واقع چیزی در صف ما، درست است؟ می گویند، خوب، است اندازه ما بیشتر از 0؟ سرد. 

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

بسیار ملموس تر وجود دارد کد study.cs50.net، و من به شدت توصیه رفتن از طریق آن، اگر شما هم، حتی اگر آن را فقط یک شبه کد است. و اگر شما بچه ها می خواهید به صحبت از طریق که با من یک در یک، لطفا اجازه دهید من می دانم. من خوشحال می شود. ساختمان داده، اگر شما را CS 124، نظر شما می دانیم که ساختارهای داده ای بسیار دریافت سرگرم کننده است و این فقط آغاز است. 

بنابراین من می دانم که آن را سخت. این OK. ما مبارزه است. من هنوز هم دارم. پس نگران نباشید بیش از حد در مورد آن. 

اما این است که اساسا شما تصادف البته در ساختمان داده. من می دانم که آن را بسیار. آیا چیزی هست که ما می خواهم به بیش از دوباره؟ هر چیزی که ما می خواهیم به صحبت از طریق؟ بله؟ 

رسید برای که به عنوان مثال، تا دم جدید در 0 بیش از که؟ SPEAKER 1: بله. رسید OK. پس رفتن را از طریق، شما می خواهم 1 به علاوه 4 or-- دارند 

SPEAKER 1: پس شما، گفتند زمانی که ما می خواهم به انجام این کار دوباره؟ رسید: آره. بنابراین اگر شما out-- بدانند شد که در آن شما محاسبه دم از در که؟ 

SPEAKER 1: پس دم بود in-- من این را تغییر داد. بنابراین در این مثال در اینجا، این بود آرایه ما به دنبال در، OK؟ بنابراین ما باید همه چیز در 1، 2، 3، و 4. بنابراین ما باید سر ما را به 1 در برابر است این نقطه، و ما را به اندازه 4 برابر است با در این نقطه، درست است؟ 

همه شما توافق می کنید که مورد؟ بنابراین ما سر به علاوه اندازه، که به ما می دهد 5، و سپس ما از 5 وزارت دفاع. ما دریافت 0، که به ما می گوید که 0 است که در آن دم ما، که در آن ما فضا است. 

رسید کلاه چیست؟ 

SPEAKER 1: ظرفیت. متأسفم. به طوری که اندازه آرایه شما می باشد. بله؟ 

رسید [نامفهوم] قبل ما به عنصر؟ 

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

رسید OK، چرا که در این نقطه، سر در 0، و پس از آن شما می خواهید به بازگشت صفحه اول 0 و سپس سر 1؟ 

SPEAKER 1: درست است. من فکر می کنم دیگر وجود دارد نوع فرمول شبیه به این. من آن را در بالا به عنوان سر من نیست من نمی خواهم به شما یک اشتباه را. اما من فکر می کنم آن را کاملا به معتبر بگو، OK، ذخیره این element-- هر عنصر سر را is-- واحد کم میکنیم شما اندازه، بیش از حرکت سر خود، و بازگشت هر چه که عنصر است. که کاملا معتبر است. OK. احساس می کنم مثل این است که مانند most-- شما نیست رفتن به قدم زدن به بیرون از اینجا مانند، بله، من می دانم که تلاش می کند. من آن را تمام کردم. که OK. من قول می دهم. اما ساختمان داده چیزی است که آن طول می کشد زمان زیادی را به مورد استفاده برای. احتمالا یکی از سخت ترین همه چیز، من فکر می کنم، در این دوره. 

پس از آن قطعا طول می کشد تکرار و به دنبال at-- من واقعا نمی دانم لیست های پیوندی تا زمانی که من بیش از حد با آنها انجام داد، در راه همان است که من نمی واقعا درک اشاره گر تا زمانی که من تا به حال به آن آموزش برای دو سال و انجام psets خود من با آن. طول می کشد تا مقدار زیادی از تکرار و زمان. و در نهایت، آن نوع از کلیک خواهد شد. 

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

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

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

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

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

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

SPEAKER 1: بله، درست است. بنابراین به معنای واقعی کلمه برای تابع هش خود، مانند گوگل "تابع هش" و برای برخی از آنهایی که سرد است. شما انتظار نمی رود که برای ساخت توابع هش خود را. مردم صرف خود پایان نامه در این چیزها. 

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

رسید: آیا سعی می کنید و یا کارآمد اما فقط سخت تر به، like-- 

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

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

پس از آن کاملا طبیعی است. این که شما نمی انجام بدتر در pset شما. این فقط ما را سخت تر بر شما در حال حاضر. پس هر کس آن را احساس. من فقط تمام psets خود را درجه بندی. من می دانم که هر کس احساس می کند. 

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

من می دانم که در هفته گذشته تمام بررسی بود، بنابراین ما ممکن است در طول برخی از بررسی قلم از سخنرانی. هر گونه سؤال دیگر من می توانم پاسخ خواهد داد؟ OK، همه حق. خوب، شما بچه ها زود بیرون 15 دقیقه. 

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