[موسیقی] 

ANDI PENG: به هفته 6 از بخش خوش آمدید. ما از استاندارد ما منحرف شده زمان بخش از سه شنبه بعد از ظهر به این یکشنبه صبح دوست داشتنی. با تشکر از شما برای هر کس که من پیوست امروز، اما به طور جدی، دور از تشویق. 

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

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

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

خوب، پس امتحان 0. متوسط ​​58٪ بود. آن بسیار کم بود، و بنابراین شما بچه ها همه خیلی، خیلی خوب بود بر اساس با آن. 

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

من می دانم که آن را ترسناک به فکر می کنم که من مثل یک٪ 40 در این مسابقه است. من قصد دارم به شکست این کلاس است. من به شما قول، شما نه رفتن به شکست کلاس. شما کاملا خوب است. 

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

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

رسید که در آن ساعت اداری است؟ 

ANDI PENG: ساعات اداری tonight-- آه، سوال خوب است. من فکر می کنم امشب ساعات اداری در ای آبی سیر یا در ویکیانبار است. اگر شما بررسی آنلاین CS50 و شما را به ساعات اداری بروید، باید یک برنامه وجود داشته باشد که شما که در آن همه از آنها می گوید. 

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

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

خوب، پس پشته. چه کسی سوال در مورد جک دوست و لباس خود را در مسابقه؟ هیچکس؟ باشه خوبه. 

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

اساسا، یک فکر پشته به عنوان هر پشته از اشیاء که در آن شما قرار دادن همه چیز بر روی بالا، و سپس شما آنها را از بالا به پاپ. بنابراین LIFO مخفف ما دوست است به use-- گذشته در، برای اولین بار بیرون. و به این ترتیب آخرین به بالای پشته یکی از اولین که بیرون می آید است. و به این ترتیب دو دوره ما دوست داریم به معاشرت که با فشار و پاپ هستند نامیده می شود. هنگامی که شما فشار را بر روی چیزی پشته، و شما آن را به پاپ به بالا. 

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

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

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

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

بنابراین برای مثال، این دوست داشتنی سوال در مسابقه بود. اساسا چگونه ما فشار بر روی بالای پشته. خیلی ساده است. اگر شما در آن نگاه کنید، ما از طریق این راه رفتن. اگر [نامفهوم] size-- به یاد داشته باشید، هر زمان که شما می خواهید برای دسترسی به هر پارامتر در داخل یک ساختار، شما به نام از struct.parameter. 

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

شما می خواهید برای دسترسی به داخل پشته خود را، به طوری که s.strings، و شما در حال رفتن برای قرار دادن که شماره جدید که شما می خواهید برای وارد کردن به وجود دارد. بیایید می گویند ما می خواهید قرار دادن INT N را بر روی پشته، ما می تواند s.strings انجام دهید، براکت، s.size برابر با n. از آنجا که اندازه جایی است که ما در حال حاضر در پشته می باشد اگر ما قصد داریم به فشار آن را در، ما فقط دسترسی هر کجا به اندازه است، پری در حال حاضر از پشته، و ما فشار INT N بر روی آن. و پس از آن ما می خواهیم مطمئن شوید که ما نیز در حال افزایش اندازه N، بنابراین ما می توانیم پیگیری ایم یک چیز اضافی به پشته اضافه شده است. در حال حاضر ما به یک اندازه بیشتر است. آیا این حس را در اینجا به همه، چگونه منطقی کار می کند؟ این نوع از سریع بود. رسید می تواند شما را بیش از s.stringss.strings [s.size] دوباره؟ ANDI PENG: مطمئنا، پس چه s.size در حال حاضر به ما بدهید؟ رسید این اندازه فعلی است. ANDI PENG: دقیقا، به طوری که شاخص در حال حاضر که اندازه ما در، و بنابراین ما خواهید برای قرار دادن عدد صحیح جدید که ما می خواهیم برای وارد کردن به s.size. فرقی میکنه؟ از آنجا که s.strings، همه که است که نام آرایه است. همه آن است که دسترسی به آرایه در ساختار ما، و بنابراین اگر ما می خواهیم مشخصات N به آن شاخص، ما فقط می توانید به آن دسترسی داشته با استفاده از براکت s.size. خنک. 

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

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

مخاطبان: این اسلاید و این که کل آن تا امروز حرکت؟ ANDI PENG: همیشه، بله. من قصد دارم به تلاش برای قرار دادن این مثل یک ساعت پس از. من دیوید را ایمیل، دیوید سعی خواهد کرد به قرار داده و آن را مانند یک ساعت بعد از این. 

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

بنابراین آنچه که ما دوست به این است dequeueing و enqueueing. اگر ما می خواهیم به اضافه کردن چیزی به صف ما، ما نوبت. اگر ما می خواهیم به dequeue، و یا چیزی دور، ما dequeue. 

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

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

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

مخاطبان: [نامفهوم] ANDI PENG: دقیقا، شما می خواهید برای اضافه آن را بسته به شما آن را نوشته شده است. در هر صورت این خالی است یا که خالی است. بنابراین شما می خواهید به آن اضافه کنید، احتمالا در اینجا به دلیل اگر به اندازه is-- اگر این همه کامل، شما می خواهید به آن اضافه کنید در اینجا، درست است؟ 

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

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

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

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

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

حالا ما می خواهیم به اضافه کردن چیزی به این صف، اما به عنوان شما می توانید ببینید بچه ها، آن را بسیار ساده به عنوان نه تنها اضافه هر آنچه پس از اندازه چرا که پس از ما از اجرا مرزهای آرایه واقعی ما. که در آن ما می خواهیم به واقعا اضافه است در اینجا. که زیبایی یک صف است این است که به ما، بصری آن به نظر می رسد مثل خط می رود مثل این، اما زمانی که در یک ساختار داده های ذخیره شده، آنها آن را به عنوان یک چرخه را مانند. این نوع از به دور به جلو به همان شیوه که یک خط همچنین می توانید بسته بندی در اطراف بسته به هر کجا که می می خواهم به ابتدای خط است. و بنابراین اگر ما را پایین نگاه کنید، اجازه دهید می گویند که ما می خواست برای ایجاد یک تابع به نام نوبت قراردادن. ما می خواستیم به اضافه INT N به که q. اگر q.size q-- ما تماس بگیرید که داده های ما structure-- اگر queue.size ما ندارد به ظرفیت و یا اگر برابر آن را کمتر از ظرفیت، q.strings آرایه در س ما است. ما در حال رفتن به راه که به q.heads برابر، که مناسب است در اینجا، به علاوه q.size مدول با ظرفیت، که بسته بندی با ما تماس در اطراف اینجا. 

بنابراین در این مثال، شاخص سر 1 است، درست است؟ شاخص اندازه 0، 1، 2، 3، 4 است. بنابراین ما می توانیم 1 به علاوه 4 مدول انجام ظرفیت ما است که 5. چه که به ما بدهید؟ شاخص این است که از این می آید؟ 

مخاطبان: 0. 

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

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

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

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

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

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

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

مخاطبان: از آنجا که همه آنها در ارتباط است، اما شما کاملا نمی دانند که در آن [نامفهوم]. 

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

و به این ترتیب به عنوان یک نتیجه، تنها راه برای جستجو از طریق یک لیست پیوندی جستجوی خطی است. از آنجا که من دقیقا نمی دانم که در آن ارزش 12th در لیست پیوندی است، من را به گذشتن از تمامیت که لیست پیوندی یک توسط یکی از سر به گره اول، به گره دوم، به گره سوم، تمام راه را تا زمانی که من در نهایت به جایی که آن گره من به دنبال است. و بنابراین در این معنا، جستجو در یک لیست پیوندی است که همیشه N. این N همیشه. این همیشه در زمان خطی. 

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

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

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

مخاطبان: [نامفهوم] 

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

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

در غیر این صورت، شما می خواهید به مجموعه اشاره گر خود را به گره بعدی. این چیزی است که این خط در اینجا انجام شده است. اشاره گر برابر اشاره گر. همه ببینید که چگونه است که کار می کند؟ 

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

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

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

مخاطبان: این پویا، پس از آن راحت to-- 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ANDI PENG: دقیقا، دقیقا همان روند به جز شما باید برای قرار که دقیقا شما می خواهید که اشاره گر به به، بنابراین اگر من می خواهم برای وارد کردن به وسط مرتبط list-- OK، اجازه دهید بگویم که لیست پیوندی ما است. اگر ما می خواهیم به آن را درج در اینجا، ما قصد داریم برای ایجاد یک گره جدید است. ما قصد داریم به malloc. ما قصد داریم برای ایجاد یک گره جدید است. ما قصد داریم به او واگذار اشاره گر از این گره است. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

و بنابراین در اینجا، اگر ما می خواستیم برای ذخیره کلمات انگلیسی، ما به طور بالقوه می تواند فقط، من نمی مطمئن شوید، به نوبه خود تمام حروف اول به نوعی یک عدد است. و بنابراین، برای مثال، اگر من می خواستم A به مترادف با apple-- و یا با شاخص 0 و B، مترادف با 1، ما می توانیم 26 مدخل داشته که فقط می تواند ذخیره همه حروف از الفبای که ما شروع با. و پس از آن ما می توانیم سیب در شاخص 0. ما می توانیم موز در شاخص از 1، طالبی در شاخص 2، و به همین ترتیب، و غیره. و به این ترتیب اگر من می خواستم به جستجو هش من جدول و دسترسی سیب، من می دانم که اپل شروع می شود با یک A، و من می دانم که دقیقا که باید آن را و هش جدول در اندیس 0 به دلیل از تابع قبلا اختصاص داده است. 

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

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

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

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

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

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

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

بنابراین تابع هش این معادله است که شما در حال اجرا نوع ورودی خود را از طریق هر شاخص به شما می خواهید به آن اختصاص به سمت. و به همین ترتیب، در این مثال، همه ما می خواست برای انجام شد را حرف اول، تبدیل آن به یک شاخص، پس ما می توانید ذخیره که در تابع هش ما است. همه ما در این جا انجام است که ما تبدیل حرف اول. بنابراین keykey [0] فقط حرف اول از هر رشته ما با داشتن، ما در حال عبور در. ما در حال تبدیل که به بالا، و ما در حال کم کردن توسط حروف بزرگ A، به طوری که تمام است که انجام به ما تعداد که در آن ما می توانیم ارزش های ما بر روی هش. 

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

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

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

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

اگر من می خواستم به insert-- چه یک میوه است که با، من نمی دانم شروع می شود، B، به غیر از انواع توت ها، موز. 

مخاطبان: توت سیاه. 

ANDI PENG: شاه توت، شاه توت. کجا شاه توت اینجا بروم؟ خب، ما در واقع طبقه بندی شده اند این در عین حال، اما به لحاظ نظری اگر ما می خواستیم به این به ترتیب حروف الفبا، که در آن باید BLACKBERRY رفت؟ 

مخاطبان: [نامفهوم] 

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

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

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

ANDI PENG: پس هش خود را تابع هش خود را جدول می تواند به عنوان بزرگ به عنوان شما می خواهید آن را به. بنابراین در این معنا، من فکر کردم آن بسیار آسان است، بسیار ساده برای من به بر اساس فقط به نوع در حرف از کلمه است. و بنابراین تنها 26 گزینه وجود دارد. تنها می توانم از 26 گزینه 0 تا 25 زیرا آنها تنها می توانید شروع از A تا Z. اما اگر شما می خواهید برای اضافه کردن، شاید، پیچیدگی بیشتر یا سریع تر زمان اجرا و به خود جدول هش، شما کاملا می توانید تمام انواع چیزهای است. شما می توانید خود را معادله است که به شما می دهد توزیع بیشتر در خود کلمات، سپس هنگامی که شما را جستجو کنید، آن را به سریع تر. 

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

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

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

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

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

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

جدول هش به نظر می رسد مانند یک میز. درخت درست مثل یک درخت به نظر می رسد. همه آن است که یک جداگانه روش سازماندهی گره با توجه به آنچه نیاز خود هستند. 

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

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

بنابراین در اینجا، اگر من قصد دارم به جستجو برای ارزش 66، من می توانم در 55 شروع می شود. آن را 66 بیشتر از 55؟ بله از آن است، به طوری که من می دانم من دردعضلات جستجو من ñ اشاره گر راست این درخت. من به 77 است. OK، 66 کمتر از 77 یا بیشتر از؟ این کمتر از، بنابراین شما می دانید، آه، است که به گره است. 

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

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

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

رسید شما می خواهید به نگاه راست و نگاه چپ و ببینید [نامفهوم] تعداد بیشتر است. 

ANDI PENG: بله، دقیقا. بنابراین شما در حال رفتن به ریشه خود نگاه کنید. بسیاری از روش شما می توانید پاسخ وجود دارد آن، خود را از مردم گره پدر و مادر می گویند. من دوست دارم بگویم ریشه به دلیل که مانند ریشه درخت است. شما در حال رفتن به در نگاه کنید گره ریشه خود را، و شما رفتن به 66 بیشتر یا کمتر از 55. و اگر آن را بیش از، خوب، آن است بیشتر از، که در آن ما می خواهیم به نگاه می کنید؟ ما کجا باید به جستجو در حال حاضر، درست است؟ ما می خواهیم به جستجو در نیمه راست این درخت. 

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

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

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

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

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

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

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

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

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

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

و here-- آه، بعدی نامه را در [نامفهوم] A. است بنابراین ما در آن آرایه است. ما پیدا کردن مقدار هشتم، و سپس ما نگاه کنید تا ببینید، آه، با سلام، این است که یک کلمه، B-A یک کلمه است؟ آن است که یک کلمه نیست. ما باید به دنبال حفظ. 

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

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

باشه خوبه. بنابراین B-A-T، و پس از آن شما در حال رفتن به جستجو. دفعه بعد که شما در حال رفتن برای دیدن، آه، هی، این درست است، بنابراین من می دانم این باید یک کلمه باشد. 

همان چیزی که برای باغ وحش. بنابراین در اینجا چیزی نیست در حال حاضر، اگر ما می خواستم به جستجو برای باغ وحش، در حال حاضر، در حال حاضر باغ وحش است نه کلمه در فرهنگ لغت ما زیرا، به عنوان شما بچه ها می توانید، را ببینید وهله اول که ما یک بولی بازگشت درست است در پایان زوم. ما Z-O-O-M. 

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

مخاطبان: [نامفهوم] 

ANDI PENG: دقیقا، ما خواهید مطمئن شوید که این در اینجا، که مقدار بولی است چک کردن که این درست است. Z-O-O، پس از آن ما قصد داریم به بررسی کنید که، بنابراین ما می دانیم دقیقا، هی، باغ وحش یک کلمه است. من قصد دارم که به کامپیوتر است که آن یک کلمه خیلی که زمانی که چک کامپیوتر، می داند که باغ وحش یک کلمه است. 

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

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

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

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

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

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

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

و به این ترتیب pset4، از 5-- آه، که اشتباه است. Pset5 غلط املائی است. همانطور که قبلا گفتم، شما در حال رفتن به یک بار دوباره، دانلود کد منبع از ما. رفتن وجود دارد به سه اصلی چیزهایی که شما دانلود می شود. شما واژهنامهها دانلود، KERS، و متون. 

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

و به این ترتیب سه بلوک از برنامه هایی که ما به شما می دهد می dictionary.c نامیده می شود، dictionary.h و speller.c. و به این ترتیب تمام dictionary.c کند است آنچه شما خواسته به پیاده سازی. این بار کلمات. آن را طلسم چک آنها، و آن اطمینان حاصل می کند که همه چیز به درستی وارد می شود. 

diction.h فقط یک فایل کتابخانه است که اعلام تمام کسانی که توابع. و speller.c، ما قصد داریم به شما بدهد. شما لازم نیست برای تغییر هر یک از آن. همه speller.c کند است را که، بارهای آن، چک سرعت آن، آزمون معیار مانند که چگونه از به سرعت شما قادر به انجام کارهای است. 

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

و بخش عمده ای از این چالش را برای شما بچه ها واقعا تغییر dictionary.c. ما قصد داریم به شما بدهد 140،000 کلمات در یک فرهنگ لغت. ما قصد داریم به شما یک متن را فایل است که این واژه ها، و ما می خواهیم شما را به قادر به سازماندهی آنها را به یک جدول هش یا یک درخت پیشوندی زیرا زمانی که ما از شما می خواهیم به طلسم check-- تصور کنید اگر شما طلسم هستید چک کردن مانند ادیسه هومر. این مثل این، آزمون بزرگ بزرگ است. 

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

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

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

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

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

همه ما در تلاش بودند برای پیاده سازی سریعترین کد که ممکن است. ما می خواهیم شما بچه ها به سعی کنید به چالش ما و پیاده سازی سریع تر از همه ما می توان. و به این ترتیب این است که واقعا اولین بار است که ما درخواست شما بچه ها برای انجام یک pset که شما واقعا می تواند در هر روش انجام شما می خواهی. 

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

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

مخاطبان: آیا ما می توانیم فقط استناد با استفاده از [نامفهوم]؟ 

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

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

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

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

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

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