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

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

باز هم، pset6 غلط املائی است، pset این هفته. و آن را نیز شما را تشویق می کند، و من شما را تشویق به استفاده از برخی دیگر منابع به طور خاص برای این pset. به طور خاص، سه من ذکر شده است تا بر روی صفحه نمایش - GDB، که ما با آن آشنا بوده است و شده است با استفاده از یک در حالی که در حال حاضر، است رفتن به بسیار مفید این هفته. بنابراین من قرار داده است که تا اینجا. اما هر زمان که شما در حال کار با C، شما همیشه باید با استفاده از توان از gdb به برنامه های خود را اشکال زدایی. این هفته نیز valgrind. آیا کسی می داند چه valgrind می کند؟ 

رسید آن را برای نشت حافظه چک می کند؟ 

JASON HIRSCHHORN: Valgrind چک برای نشت حافظه است. بنابراین اگر شما چیزی malloc در خود برنامه، شما برای حافظه درخواست. در پایان برنامه های خود را، شما باید به ارسال رایگان بر روی همه چیز را که شما malloced به حافظه است. اگر شما در پایان ارسال نمی رایگان و برنامه شما می آید به نتیجه گیری، همه چیز به طور خودکار آزاد شود. و برای برنامه های کوچک، آن را که بزرگ یک معامله. اما اگر شما در حال نوشتن در حال اجرا دیگر برنامه ای است که به این ترک نیست، لزوما، در چند دقیقه و یا یک چند ثانیه، سپس حافظه نشت می تواند تبدیل به یک معامله بزرگ. 

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

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

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

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

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

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

یک مدعو: برو به گره و ارزیابی ارزش N برای آن. 

JASON HIRSCHHORN: که دقیقا درست است. نقطه به معنی دسترسی به بخش N از این گره جدید. این خط بعد چه؟ مایکل. 

یک مدعو: این گره دیگر ایجاد که به گره نقطه. 

JASON HIRSCHHORN: بنابراین آن را نمی کند ایجاد یک گره جدید است. آن را ایجاد چه؟ 

رسید یک اشاره گر. 

JASON HIRSCHHORN: یک اشاره گر به گره، عنوان های این گره * نشان داد در اینجا. پس از آن ایجاد یک اشاره گر به گره. و که گره آن اشاره به، مایکل؟ 

یک مدعو: گره جدید؟ 

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

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

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

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

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

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

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

رسید: با اشاره گر به گره بعدی. 

JASON HIRSCHHORN: و چرا ما را به یکی بعدی بروید؟ 

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

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

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

یک مدعو: شش بزرگتر از پنج است. 

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

یک مدعو: دو. 

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

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

JASON HIRSCHORN: دقیقا. بنابراین ما هشت. ما در رسیدن به انتهای لیست به دلیل این است با اشاره به تهی. و در حال حاضر، به جای داشتن آن را به نقطه تهی ما باید آن را به گره جدید ما اشاره می کنند. و ما اشاره گر در مجموعه گره جدید ما تهی. آیا هر کسی هر گونه سوال در مورد قرار دادن؟ چه می شود اگر من مهم نیست که در مورد نگه داشتن لیست طبقه بندی شده اند؟ 

یک مدعو: استیک آن را در شروع یا پایان. 

JASON HIRSCHORN: استیک آن را در آغاز یا پایان. کدام یک باید کرد؟ بابی؟ چرا پایان؟ 

یک مدعو: از آنجا که آغاز در حال حاضر پر شده است. 

JASON HIRSCHORN: OK. آغاز شده است در حال حاضر پر شده است. چه کسی می خواهد به استدلال می کنند در مقابل بابی. مارکوس. 

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

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

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

یک مدعو: غلط؟ 

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

یک مدعو: این ارزش برای اولین بار از پیدا کردن که بیشتر از یک شما به دنبال و و سپس بازگشت نادرست است. 

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

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

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

رسید بنابراین اگر شما قصد حذف آن، شما را فقط به رایگان استفاده کنید زیرا احتمالا آن malloced شد؟ 

JASON HIRSCHORN: اگر می خواهید آزاد چیزی که دقیقا سمت راست و شما آن malloced. می گویند ما می خواستیم به بازگشت این مقدار است. ما ممکن است بازگشت شش و سپس آزاد این گره و تماس رایگان بر روی آن. یا ما احتمالا می خواهم رایگان برای اولین بار تماس بگیرید و سپس بازگشت شش. 

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

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

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

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

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

اجازه دهید با نوشتن شروع شبه در هیئت مدیره. چه کسی می تواند به من خط اول را شبه برای این برنامه؟ برای این تابع، به جای - insert_node. آلدن؟ 

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

JASON HIRSCHORN: OK. بنابراین شما ایجاد یک اشاره گر جدید به این فهرست، نه به گره. 

یک مدعو: راست. آره. 

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

یک مدعو: اوه، ببخشید. ما نیاز به malloc فضا برای گره. 

JASON HIRSCHORN: بسیار عالی. اجازه دهید - OK. نمی توان آن را بالا برسد. OK. ما قصد داریم به پایین، و پس از آن ما با استفاده از دو ستون. من نمی توانم که - OK. ایجاد یک گره جدید. شما می توانید اشاره گر دیگری به لیست ایجاد کنید یا شما فقط می توانید لیست استفاده از آن را به عنوان وجود دارد. شما واقعا نیاز به انجام این کار. 

بنابراین ما ایجاد یک گره جدید است. بزرگ. این چیزی است که ما انجام می دهیم اول است. گام بعدی چیست؟ 

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

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

یک مدعو: رایگان است. 

JASON HIRSCHORN: آره. احتمالا آن را آزاد کند. OK. چه ما پس از ما انجام می دهیم ایجاد یک گره جدید؟ آنی؟ 

رسید ما را از تعداد در گره؟ 

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

یک مدعو: ما از طریق لیست بروید. 

JASON HIRSCHORN: برو از طریق این فهرست است. OK. و چه چیزی برای ما در هر گره تیک بزنید. کورت، چه چیزی را چک ما برای هر گره؟ 

رسید مشاهده کنید که آیا مقدار N از که گره بیشتر از مقدار N است گره ما. 

JASON HIRSCHORN: OK. من قصد دارم برای انجام این کار - بله، OK. پس از آن n - من قصد دارم برای گفتن اگر ارزش بیشتر است از این گره، پس چه کنیم؟ 

یک مدعو: خب، پس ما وارد درست قبل از آن. 

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

یک مدعو: سپس شما را ادامه دهم مگر اینکه آن را یکی از آخرین است. 

JASON HIRSCHORN: من دوست دارم که. بنابراین به گره بعدی بروید. مگر در مواردی که در آن یکی از آخرین است - ما احتمالا در حال بررسی است که در شرایط یک وضعیت. اما آره، گره بعدی. و این بیش از حد کم، بنابراین ما در اینجا حرکت می کند. اما اگر - همه می بینند این؟ اگر ما برابر آنچه که ما انجام می دهید؟ اگر ارزش ما در حال تلاش برای وارد کردن به ارزش این گره برابر است با؟ آره؟ 

یک مدعو: [نامفهوم]. 

JASON HIRSCHORN: آره. با توجه به این - مارکوس درست است. ما می تواند شاید انجام می شود چیزی متفاوت است. اما با توجه به اینکه ما آن را ایجاد کرده اید، اینجا ما باید آزاد و سپس بازگشت. آه پسر. است که بهتر است؟ چگونه است که؟ OK. رایگان و پس از آن چه کار می کنیم بازگشت، [نامفهوم]؟ OK. آیا ما هر چیزی گم شده؟ تا جایی که ما نگه داشتن در حال پیگیری از گره قبل؟ 

یک مدعو: من فکر می کنم آن را به بعد از یک گره جدید ایجاد کنید. 

JASON HIRSCHORN: OK. بنابراین در آغاز خواهیم احتمالا - بله، ما می توانیم یک اشاره گر به جدید ایجاد کنید گره، مانند یک اشاره گر به گره قبلی و یک اشاره گر گره فعلی. بنابراین اجازه دهید که در اینجا وارد کنید. ایجاد کنونی و پیشین اشاره گر به گره. اما زمانی که ما تنظیم آن اشاره گر؟ کجا کار می کنیم که در کد؟ جف؟ 

یک مدعو: - شرایط ارزش؟ 

JASON HIRSCHORN: کدام یکی به طور خاص؟ 

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

JASON HIRSCHHORN: بنابراین اگر ارزش های ما است بیشتر از مقدار از این گره است. 

یک مدعو: آره، پس از آن شما می خواهم می خواهم به بیشتر پایین خط، درست است؟ 

JASON HIRSCHHORN: راست. بنابراین ما آن را در اینجا وارد نیست. اگر مقدار کمتر از این گره است، پس از آن ما به گره بعدی بروید - و یا پس از آن ما قرار دادن قبل از. 

یک مدعو: صبر کن، که این گره و ارزش است؟ 

JASON HIRSCHHORN: سوال خوب. ارزش در این تعریف تابع چیزی است که ما داده می شود. بنابراین ارزش تعداد ما داده شده می باشد. بنابراین اگر ارزش کمتر از این است گره، ما هم برای وارد کردن نیاز دارید. اگر مقدار را بیشتر از این گره است، ما به گره بعدی بروید. و به سوال اصلی، هر چند، که در آن - 

یک مدعو: اگر ارزش بیشتر است از این گره است. 

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

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

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

یک مدعو: شما ساختار *. 

JASON HIRSCHHORN: پس ما که تا اینجا. اوه، ببخشید. شما ساختار می گفتند *. 

رسید و پس از آن [؟ نوع؟] گره یا گره ج. 

JASON HIRSCHHORN: OK. من قصد دارم به آن را new_node بنابراین ما می توانیم سازگار باقی بماند. 

رسید و شما می خواهید به مجموعه ای است که به سر، گره اول است. 

JASON HIRSCHHORN: OK. بنابراین در حال حاضر این اشاره به - پس این تا به یک گره جدید ایجاد نشده است. این فقط به اشاره اولین گره در لیست. چگونه می توانم ایجاد کنم یک گره جدید؟ اگر من نیاز به فضای برای ایجاد یک گره جدید. Malloc. و چقدر بزرگ؟ 

یک مدعو: اندازه ساختار. 

JASON HIRSCHHORN: اندازه ساختار. و چیزی که ساختار نامیده می شود؟ 

یک مدعو: گره؟ 

JASON HIRSCHHORN: گره. بنابراین malloc (sizeof (گره))؛ ما فرصت می دهد. و این خط است - یک چیز در این خط نادرست است. آیا یک اشاره گر به ساختار new_node؟ که یک نام عمومی است. آنچه در آن است - گره، دقیقا. این یک گره * است. و ما چه بلافاصله پس از انجام ما چیزی، آسان malloc؟ اولین چیزی که ما انجام می دهیم چیست؟ چه می شود اگر آن کار نمی کند؟ 

یک مدعو: اوه، چک کردن آن اشاره به گره؟ 

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

یک مدعو: شما باید برای انجام یک گره *. شما می خواهم که به یک را ندارد برای new_node اما برای گره های ما در حال حاضر. 

JASON HIRSCHHORN: OK. بنابراین گره فعلی ما در حال. من که curr تماس بگیرید. بسیار خوب. ما تصمیم گرفتیم ما می خواهیم برای حفظ دو دلیل ما نیاز به دانستن چه قبل از آن. چه آنها که به مقداردهی اولیه؟ 

رسید ارزش آنها در لیست ما است. 

JASON HIRSCHHORN: پس چه شده است اولین چیزی که در لیست ما؟ و یا چگونه ما می دانیم که در آن آغاز از لیست ما است؟ 

یک مدعو: آیا نمی گذشت به تابع؟ 

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

یک مدعو: فهرست. 

JASON HIRSCHHORN: فهرست. این دقیقا همان سمت راست. در حال حاضر از آن است که آدرس آغاز از لیست ما است. و آنچه در مورد قبلی؟ 

یک مدعو: فهرست منهای یک؟ 

JASON HIRSCHHORN: وجود دارد هیچ چیز قبل از آن. پس چه می تواند ما انجام می دهیم به معنی هیچ چیز؟ 

رسید نول. 

JASON HIRSCHHORN: آره. به نظر می رسد ایده خوبی است. کامل. متشکرم. برو از طریق این فهرست است. کنستانتین، چه مدت می خواهیم به این لیست برود؟ 

رسید تا رسیدن تهی. 

JASON HIRSCHHORN: OK. بنابراین اگر، در حالی که، برای حلقه. چه کار می کنیم؟ 

رسید شاید برای حلقه؟ 

JASON HIRSCHHORN: اجازه دهید کار را برای حلقه. OK. 

رسید و ما برای گفتن - تا زمانی که اشاره گر فعلی است به تهی برابر نیست. 

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

رسید در حالی که. 

JASON HIRSCHHORN: آره. این را حس می کند بیشتر بر اساس خارج از آنچه شما گفت. اگر ما فقط می خواهم برای رفتن به ما آن را فقط می دانم که چیزی، آن را به حس به انجام یک حلقه در حالی که. در حالی که در حال حاضر نشانی از تهی برابر نیست، اگر مقدار کمتر از این گره است. Akshar، من این خط را. 

یک مدعو: اگر در حال حاضر-> نفر نفر کمتر از مقدار است. و یا معکوس است. سوییچ که با براکت. 

JASON HIRSCHHORN: متاسفم. 

یک مدعو: تغییر براکت. 

JASON HIRSCHHORN: بنابراین اگر آن را بیشتر از مقدار است. از آنجا که گیج کننده است با اظهار نظر فوق، من قصد دارم برای انجام این کار. اما بله. اگر ارزش های ما کمتر از این است گره، چه کنیم؟ آه. من آن را در اینجا ببینید. قرار دادن قبل از. OK. ما چگونه انجام این کار؟ 

یک مدعو: آیا هنوز هم من؟ 

JASON HIRSCHHORN: آره. 

یک مدعو: شما - new_node-> بعدی. 

JASON HIRSCHHORN: پس چه که رفتن را برابر؟ 

یک مدعو: این رفتن به فعلی برابر است. 

JASON HIRSCHHORN: دقیقا. و به این ترتیب دیگر - چه چیز دیگری ما نیاز به به روز رسانی؟ 

رسید چک کنید اگر گذشته برابر تهی. 

JASON HIRSCHHORN: اگر قبلی - بنابراین اگر قبل برابر تهی. 

یک مدعو: این بدان معناست که آن را برای تبدیل شدن به سر. 

JASON HIRSCHHORN: این یعنی آن را تبدیل به سر. پس ما چه کاری انجام دهید؟ 

یک مدعو: ما سر برابر new_node. 

JASON HIRSCHHORN: سر برابر new_node. و چرا سر در اینجا، لیست نیست؟ 

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

JASON HIRSCHHORN: شیرین. OK. و - 

یک مدعو: سپس شما دیگری قبل،-> بعدی برابر new_node. و سپس شما را به راست. 

JASON HIRSCHHORN: کجا ما پایان new_node است؟ 

رسید من - من در آغاز مجموعه ای که. 

JASON HIRSCHHORN: پس چه خط؟ 

یک مدعو: پس از دستور if چک کردن اگر آن شناخته شده است. 

JASON HIRSCHHORN: در اینجا؟ 

یک مدعو: من می خواهم انجام new_node-> نفر برابر است با ارزش. 

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

یک مدعو: اگر ارزش بیشتر است از curr-> N - 

JASON HIRSCHHORN: چگونه ما به گره بعدی بروید؟ 

یک مدعو: Curr-> نفر است به new_node برابر است. 

JASON HIRSCHHORN: بنابراین نفر است چه بخشی از ساختار؟ عدد صحیح. و new_node یک اشاره گر به گره است. پس چه بخشی از curr باید به روز رسانی ما؟ اگر نه نفر، پس از آن چه در بخش های دیگر؟ نوح، چه در بخش های دیگر است. 

یک مدعو: اوه، بعدی. 

JASON HIRSCHHORN: بعدی، دقیقا. دقیقا. بعد یک حق است. و چه چیز دیگری نیاز داریم برای به روز رسانی، نوح؟ 

یک مدعو: اشاره گر. 

JASON HIRSCHHORN: پس ما در حال حاضر به روز شد. 

یک مدعو: قبل> بعد. 

JASON HIRSCHHORN: آره. OK، ما مکث. چه کسی می تواند ما را در اینجا کمک کند؟ مانو، چه باید کرد؟ 

رسید شما باید به مجموعه آن را به curr-> بعدی برابر است. اما انجام این کار قبل از خط قبلی. 

JASON HIRSCHHORN: OK. هر چیز دیگری؟ Akshar. 

یک مدعو: من فکر نمی کنم شما به معنای تغییر curr-> بعدی. من فکر می کنم که شما به منظور انجام برابر curr curr-> بعدی برای رفتن به گره بعدی. 

JASON HIRSCHHORN: خیلی متاسفم، که در آن؟ در خط؟ این خط؟ 

یک مدعو: آره. را curr برابر curr-> بعدی. 

JASON HIRSCHHORN: پس این درست چون در حال حاضر است اشاره گر به گره. و ما می خواهیم آن را به نقطه به بعد گره از آنچه که در حال حاضر گرفتن به اشاره کرد. Curr خود را تا بعد. اما اگر ما برای به روز رسانی curr.next ما می شود به روز رسانی توجه داشته باشید واقعی خود را، که در آن این اشاره گر اشاره شد. چه در مورد این خط، هر چند. AVI؟ 

یک مدعو: قبل> بعد برابر curr. 

JASON HIRSCHHORN: پس دوباره، اگر قبلی است اشاره گر به گره قبلی-> بعدی است اشاره گر واقعی در گره. بنابراین این امر می تواند به روز رسانی اشاره گر در یک گره به curr. ما نمی خواهیم برای به روز رسانی یک اشاره گر در یک گره. ما می خواهیم برای به روز رسانی های قبلی است. بنابراین ما چگونه انجام این کار؟ 

رسید که فقط قبل، است. 

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

یک مدعو: اگر ارزش است به curr-> N برابر است. 

JASON HIRSCHHORN: متاسفم. اوه خدای. چه؟ ارزش == curr-> نفر. چه کنیم؟ 

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

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

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

JASON HIRSCHHORN: من نمی دانم. آیا شما من می خواهم به؟ 

یک مدعو: ذهن هرگز. شماره 

JASON HIRSCHHORN: Akshar؟ 

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

JASON HIRSCHHORN: پس از کجا آیا شما می خواهید آن را برای رفتن؟ 

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

JASON HIRSCHHORN: OK. پس چه که ما در اینجا انجام دهید؟ 

یک مدعو: شما بازگشت کاذب نیز وجود دارد. 

JASON HIRSCHHORN: اوه، ما این کار را در هر دو مکان؟ 

یک مدعو: آره. 

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

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

یک مدعو: آیا شما اشاره نمی کند - آیا شما نمی بینید می گویند که رئیس آن بود در آغاز به NULL مقدار دهی اولیه. اما من فکر کردم شما فرمودید که OK بود. 

JASON HIRSCHHORN: بریم - اجازه دهید نگاه در GDB، و پس از آن ما به عقب برگردد. اما به نظر می رسد که شما در حال حاضر برخی از ایده های در مورد آنچه اتفاق افتاده است. بنابراین ما می خواهیم به قرار دادن چیزی. OK. ما وارد شده است. لطفا یک int را وارد کنید. ما سه را وارد کنید. و بعد من در این خط هستم. چگونه می توانم به I شروع اشکال زدائی درج عملکرد شناخته شده ای؟ اوه خدای. این مقدار زیادی است. است که ناجور می کنه زیادی؟ 

یک مدعو: آه، آن درگذشت. 

JASON HIRSCHHORN: من فقط آن را بیرون آورد. OK. 

رسید شاید آن را انتهای دیگر سیم. 

JASON HIRSCHHORN: وای. بنابراین خط پایین - چه گفتی؟ 

یک مدعو: من گفت: طنز از فنی مشکلات در این کلاس. 

JASON HIRSCHHORN: من می دانم. اگر فقط من کنترل بر آن بخش بود. [نامفهوم] به نظر می رسد بزرگ است. چرا شما بچه ها نمی شروع به فکر کردن در مورد آنچه که ما می تواند به اشتباه انجام داده اند، و ما در 90 ثانیه خواهد بود. 

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

رسید چه؟ 

JASON HIRSCHHORN: چه فرمان GDB من با استفاده به داخل این تابع برود؟ 

یک مدعو: مرحله؟ 

JASON HIRSCHHORN: قدم از طریق S. که من طول می کشد در داخل. OK. New_node mallocing برخی از فضا. این همه به نظر می رسد مانند رفتن آن است. اجازه دهید new_node را بررسی کند. این آدرس حافظه است. بیایید بررسی - است که همه درست است. بنابراین همه چیز در اینجا به نظر می رسد خوبی کار میکند. 

یک مدعو: تفاوت چیست بین P و صفحه نمایش؟ 

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

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

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

حضار: نه 

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

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

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

JASON HIRSCHHORN: OK. خواهد شد که حل مشکل ما، هر چند؟ 

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

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

یک مدعو: اگر شما در حال حاضر کردم گره malloced، شما فقط می گفت: new_node-> آینده برابر تهی به دلیل آن را در پایان می شود. یا new_node-> آینده برابر تهی. 

JASON HIRSCHHORN: OK. متأسفم. New_node-> آینده برابر با تهی از آنجا که ما در پایان است. که آن را قرار داده به سایت چگونه ما آن را در لیست قرار داده است؟ راست. که فقط تنظیم آن به برابر است. بدون که ما چگونه در واقع آن را در لیست؟ چه خبر با اشاره به انتهای فهرست؟ 

رسید سر. 

JASON HIRSCHHORN: ببخشید؟ 

رسید سر اشاره به انتهای لیست. 

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

رسید: من به شما فکر می کنم انجام فعلی-> بعدی. 

JASON HIRSCHHORN: OK. curr-> بعدی. بنابراین دوباره، تنها به این دلیل که ما را می در اینجا این است، آنچه که در حال حاضر برابر می کند؟ 

یک مدعو: برابر تهی. 

JASON HIRSCHHORN: و چیزی اتفاق می افتد اگر ما تهی-> بعدی؟ چه ما برای به دست آوردن؟ ما یک خطای تقسیم بندی را دریافت کنید. 

یک مدعو: آیا curr برابر تهی. 

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

یک مدعو: قبلی-> بعدی؟ 

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

رسید این خبر را به بازگشت نادرست در این مورد؟ 

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

یک مدعو: آیا قبلی هنوز هم برابر تهی در بالای لیست؟ 

JASON HIRSCHHORN: هنوز هم پس قبلی برابر صفر را در همان ابتدا. پس چگونه می توان بیش از آن را دریافت کنید؟ آره؟ 

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

JASON HIRSCHHORN: OK. بنابراین اجازه دهید به اینجا بروید. آیا چک. اگر - 

رسید بنابراین اگر سر برابر برابر تهی. 

JASON HIRSCHHORN: اگر سر برابر برابر تهی - که شما به ما بگویید که اگر آن را به یک لیست خالی است. 

رسید و پس از آن شما سر انجام معادل جدید. 

JASON HIRSCHHORN: سر برابر new_node؟ و چه چیز دیگری باید انجام دهیم؟ 

رسید و پس از آن شما به راست. 

JASON HIRSCHHORN: نه کاملا. ما در حال از دست رفته یک گام. 

یک مدعو: New_node بعدی به نقطه تهی. 

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

حضار: بله. 

JASON HIRSCHHORN: آره. و چه نیازی به تغییر این به؟ درست است. آیا این خوب صدا به هر کس تا کنون؟ هر کسی هر گونه - AVI، آیا شما چیزی برای اضافه کردن؟ 

حضار: نه 

JASON HIRSCHHORN: OK. بنابراین ما یک زن و شوهر از تغییرات ساخته شده است. ما این چک قبل از ما ساخته شده در یک لیست خالی رفت. بنابراین ما مراقبت از یک لیست خالی گرفته شده. و در اینجا ما مراقبت از قرار دادن در زمان چیزی در انتهای لیست. بنابراین آن را مانند این گرفتن حلقه در حالی که به نظر می رسد مراقبت از چیزها در میان، جایی در لیست اگر وجود دارد همه چیز در این لیست می باشد. 

OK. اجازه دهید ما دوباره این برنامه را اجرا کنید. موفق نشده. 

رسید شما انجام آن را ندارد. 

JASON HIRSCHHORN: اوه، من آن را ندارد. نقطه خوب، مایکل. اجازه دهید اضافه کردن یک آرایش مرتبط است. خط 87 یک خطا وجود دارد. خط 87. آلدن، این خط شما به من داد بود. چی شده؟ 

یک مدعو: این موضوع باید تهی. 

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

یک مدعو: هفت. 

JASON HIRSCHHORN: هفت؟ 

حضار: بله. 

JASON HIRSCHHORN: ما یک گسل SEG. بنابراین ما کردم، اما ما به وضوح نمی تواند دو دریافت کنید. این 05:07 می باشد. بنابراین ما می تواند این اشکال زدایی برای سه دقیقه. اما من قصد دارم به ما در اینجا ترک و حرکت بر روی هش جدول. اما باز هم، پاسخ برای این کد من آن را برای شما در یک بیت ایمیل. ما بسیار نزدیک به آن. من به شدت شما را تشویق به کشف کردن چه خبر است در اینجا و تعمیر آن. بنابراین من به شما این کد به ایمیل چاه + راه حل - احتمالا راه حل بعد. اول این کد. 

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

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

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

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

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

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

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

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

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

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

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

رسید آن را می توانید پیدا کنید شاخص در زمان ثابت؟ 

JASON HIRSCHHORN: که چیزی است که به این معنی نیست. اما این یک حدس خوب است. هر کس دیگری یک حدس به این به چه معناست؟ این یک تابع هش خوب قطعی است؟ آنی؟ 

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

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

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

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

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

یک مدعو: صفر. 

JASON HIRSCHHORN: چرا صفر؟ 

رسید آنجا که سه پیمانه سه صفر است؟ 

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

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

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

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

بنابراین من در کدو قرار داده است. این صفر را برمی گرداند. و من قرار داده کدو تنبل در اینجا. سپس من در قرار داده است - چه چیز دیگری هالووین با مضمون است؟ 

یک مدعو: آب نبات. 

JASON HIRSCHHORN: آب نبات! این یکی از بزرگ است. من در آب نبات و آب نبات را همچنین به من صفر است. چه کار کنم؟ هر گونه ایده ها؟ از آنجا که شما همه نوع دانم چه زنجیری جداگانه است. بنابراین هر ایده چه کاری انجام دهید؟ آره. 

یک مدعو: قرار دادن رشته در واقع در جدول هش. 

JASON HIRSCHHORN: بنابراین ما در حال رفتن به قرعه کشی ایده خوبی است اینجا. OK. 

یک مدعو: آیا پشته دارید [نامفهوم] اشاره گر که به آغاز یک لیست. و پس از آن کدو تنبل است مقدار اول در آن لیست پیوندی و آب نبات است ارزش دوم در این لیست در ارتباط است. 

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

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

رسید اشاره گرها به - 

JASON HIRSCHHORN: از آنجا که شما گفت: یک لیست پیوندی، پس - 

یک مدعو: اشاره گر به گره؟ 

JASON HIRSCHHORN: اشاره گر به گره. اگر چیزهایی که در ما مرتبط است لیست گره ها و سپس آنها باید اشاره گر گره باشد. و چه چیزی آنها برابر در ابتدا؟ 

رسید نول. 

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

یک مدعو: من قصد دارم به یک حدس. بنابراین، هنگامی که شما آب نبات دریافت کنید. 

JASON HIRSCHHORN: آره. خب، ما کدو تنبل شدم. اجازه دهید اول ما را دریافت کنید. ما کدو تنبل شدم. 

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

JASON HIRSCHHORN: چگونه ما انجام می دهیم آن را در لیست پیوندی؟ 

یک مدعو: اوه، نحو واقعی؟ 

JASON HIRSCHHORN: کافی است به پیاده - می گویند بیشتر. چه کنیم؟ 

یک مدعو: شما فقط قرار دادن آن را به عنوان گره اول. 

JASON HIRSCHHORN: OK. بنابراین ما باید گره ما، کدو تنبل. و در حال حاضر چگونه می توانم آن را درج کنم؟ 

یک مدعو: شما اختصاص دهید آن را به اشاره گر. 

JASON HIRSCHHORN: کدام اشاره گر؟ 

یک مدعو: اشاره گر در صفر. 

JASON HIRSCHHORN: پس از کجا به این نقطه؟ 

رسید به NULL در حال حاضر. 

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

رسید به کدو. 

JASON HIRSCHHORN: به کدو تنبل. دقیقا. پس این اشاره به کدو تنبل. و آیا این اشاره گر در نقطه کدو تنبل؟ به 

رسید نول. 

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

رسید این در مورد اینکه آیا یا وابسته نیست که ما در تلاش هستیم تا آن را مرتب. 

JASON HIRSCHHORN: که دقیقا درست است. این بستگی دارد که آیا یا نه ما در حال تلاش برای آن را مرتب. اجازه دهید فرض کنیم نیست رفتن به آن را مرتب. 

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

JASON HIRSCHHORN: OK. در نگه دارید. اجازه دهید به من آب نبات ایجاد حق در اینجا. پس این اشاره گر - 

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

JASON HIRSCHHORN: که می خواهم؟ و می گویند که ما دیگر وقت چیزی که به نقشه را به صفر؟ 

یک مدعو: خوب، شما فقط همین کار را؟ 

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

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

یک مدعو: چرا شما قرار داده کدو تنبل و آب نبات را به همان بخشی از جدول هش؟ 

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

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

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

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

JASON HIRSCHHORN: برای خطی برنامه نویسی، هیچ لیست مرتبط است. نقطه بعدی در جدول هش. 

تماشاچیان: OK. بنابراین جدول هش خواهد بود مقدار دهی اولیه به اندازه - مانند تعداد رشته ها که شما با قرار دادن بودند؟ 

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

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

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

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

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

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