دیوید مالان: بسیار خوب. خوش آمدید به CS50. این شروع هفته 8 است. به یاد بیاورید که مجموعه ای مشکل 5 به پایان رسید با کمی از چالش است. بنابراین با این فرض که همه شما خود را بهبود بورسیه آموزش و عکس CA در فایل card.raw، شما واجد شرایط هستند در حال حاضر همه از این افراد، پیدا کردن و یک برنده خوش شانس به خانه با یک پیاده روی از این چیزها، حرکت جهش دستگاهی است که شما می توانید برای استفاده نهایی پروژه ها، به عنوان مثال. 

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

سپس، "من به خارج از شهر این آخر هفته بود، و وقتی که من از آنجا به عقب، یکی در بود من اتاق خواب. "[خنده] دیوید مالان: نقل قول بعدی از کارکنان عضو، "یک دانش آموز در خانه من آمد Somerville در 4 صبح امروز. "بعدی کارکنان، "من به هتل من در سان فرانسیسکو و یک دانش آموز انتظار من در لابی با سه DSLR ها است. " نوع دوربین. "من حتی در کارکنان این ترم، اما یک دانش آموز به خانه من نفوذ صبح و ثبت همه چیز با Google شیشه ای. "و پس از آن در آخر، "حداقل 12 نفر مشتاقانه بودند انتظار برای من وقتی که من بیرون از من ماشین لیموزین، و پس از آن من بیدار شد. "همه حق. بنابراین در میان عکس ها، شما ممکن است به یاد بیاورید، این شخص در اینجا، که شما ممکن است به عنوان میلو موز، که زندگی می کند می دانم با لورن کاروالهو، سر ما آموزش همکار. میلو، میلو، به اینجا می آیند پسر. میلو میلو ذهن شما، او با پوشیدن شیشه ای گوگل، به طوری که ما به شما همه از این پس از نشان می دهد. بنابراین این میلو است اگر شما می خواهم به گرفتن یک عکس با او پس از آن. اگر شما می خواهم به نگاه کردن در مخاطب وجود دارد. OK را بزنید. این فیلم خوب است. خوب، موز میلو. آه، آیا انجام این کار نیست. 

[خنده حضار] 

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

بنابراین اگر شما ممکن است علاقه مند در یک یا بیشتر از سمینارها امسال، ثبت نام در cs50.net/seminar. سمینارها مسن تر وجود دارد در cs50.net/seminars. و در فهرستی تا کنون برای این سال نرم افزار وب سایت شگفت انگیز با روبی در آهن، که جایگزین زبان به پی اچ پی. زبانشناسی محاسباتی است. مقدمه ای بر IOS، است که پلت فرم است که برای آی فون استفاده می شود و توسعه اپل. جاوا اسکریپت را برای برنامه های وب، خواهیم پوشش ، اما در این سمینار، شما بروید به جزئیات بیشتر. 

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

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

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

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

مخاطبان: اندازه دینامیک. 

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

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

مخاطبان: نیاز به حافظه بیشتر است. 

دیوید مالان: این نیاز به بیش حافظه، دقیقا چگونه؟ 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

دیوید مالان OK. من شنیده ام آغاز شده است. چرا در ابتدا؟ 

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

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

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

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

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

بنابراین ما پس از آن در این چیزی که نگاه کرد، که واقعا دیگر این فرصت بزرگ برای P-مجموعه 6. و ببینی، اگر شما در حال حاضر نه، غواصی Zamyla به هر دو از این، هش جداول و تلاش می کند، در جزئیات بیشتر است. و خرید فیلم جاسازی شده در P-مجموعه تنظیمات. این درخت بود - T-R-I-E. و چه جالب بود این که زمان در حال اجرا بود جستجو برای یک نام، مانند ماکسول زمان گذشته، بزرگ O از چه بود؟ چه خبر؟ 

مخاطب: تعداد حروف است. 

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

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

خوب، زمانی که ما به M-A-X-W-E-L-L رفته، احساس می کند مانند هفت، شاید هشت اگر ما به گذشته، هشت گام برای پیدا ماکسول. یا اجازه دهید آن K. می نامند اما به یاد آخرین زمان، من استدلال می کنند که اگر وجود دارد واقع بینانه حداکثر طول بر کلمه، مانند شخصیت های 40 و برخی از عجیب و غریب، حداکثر طول پیداست یک مقدار ثابت. پس در واقع، بله، آن را از لحاظ فنی بزرگ O از 8 یا 7 یا O واقعا بزرگ K. اما اگر یک کلاه محدود در چه وجود دارد K می تواند، آن را ثابت. و پس از آن O بزرگ، از مجموع 1 در پایان روز. 

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

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

و آن نیست. این است که لزوما داده ها ساختار شما باید به جذب، زیرا مانند جداول هش، معاوضه. قیمت شما در اینجا پرداخت چه خبر؟ حافظه است. منظورم این است که، این است که بی رحم مقدار از حافظه است. و شما می توانید کاملا آن را در اینجا ببینید زیرا نویسنده این تصویر بدیهی است تمام آرایه های کوتاه، و ما شاهد تعداد زیادی از و B و C و Q و Y و Z در این آرایه ها. اما آنها وجود دارد. 

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

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

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

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

مخاطبان: فراخوانی توابع. 

دیوید مالان: متاسفم. 

مخاطبان: فراخوانی توابع. 

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

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

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

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

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

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

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

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

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

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

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

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

پس چه داخل از اندازه است در این لحظه در زمان اگر من انجام داده اند این است پشته با اعلام یک خط از کد؟ 

استیون: نه خیلی زیاد. 

دیوید مالان: خوب، نه خیلی زیاد. آیا ما می دانیم چه در داخل به اندازه، آیا ما می دانیم که آنچه در داخل این آرایه در اینجا؟ 

استیون: کد تصادفی، درست است؟ فقط - 

دیوید مالان: آره، من رفتن به آنرا کد، اما تصادفی - 

استیون: اوضاع. 

دیوید مالان: چیزهایی مثل تصادفی 

استیون: بیت. 

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

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

استیون: سینی زیر 3 است. 

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

استیون: صفر. 

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

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

استیون: در - اندازه؟ 

دیوید مالان OK. حجم باید تبدیل به چه؟ 

استیون: حجم خواهد بود. 

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

استیون: ما قصد داریم از پایین به بالا تا 9. 

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

استیون: پس اندازه برای رفتن به دو. 

دیوید مالان OK. تو پاک کن - متأسفم. تو پاک کن. 

استیون: پاک کن. 

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

استیون: قلم مو. 

دیوید مالان OK. و چه چیز دیگری؟ 

استیون: و پس از آن ما - 

دیوید مالان: ما تحت فشار قرار دادند 17. 

استیون: ما چوب 17 در بالا، به طوری - 

دیوید مالان: خوب، خوب است. 

استیون: - رها کردن آن را. 

دیوید مالان: بسیار خوب. این آسان است. من قصد ندارم به شما کمک کند این زمان. فشار 22. 

استیون: انجام شد. تبدیل شدن به یک پاک کن. من تبدیل شدن به یک قلم مو. و سپس من قرار دادن 22. 

دیوید مالان 22. بسیار عالی است. بنابراین یک بار دیگر. من در حال حاضر رفتن به فشار بر روی پشته 26. 

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

دیوید مالان: شما نمی دیدن این آینده؟ 

استیون: من نمی بینم این آینده است. آیا ما دوباره ظرفیت اولیه؟ 

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

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

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

[تشویق حضار] 

استیون: با تشکر از شما. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

هر یک از شما در حال حاضر به رفتن به یک پسر فن در خط در اپل. شما نمایش داده نمی شود سخت افزار اپل در پایان این هر چند. بسیار خوب. بنابراین عدد 9 شما، شما شماره 17، شماره 22. این اعداد دلخواه هستند، مانند دانشجوی شناسه یا فلان چیز. و در یک لحظه، بیایید شروع برای شروع به اضافه کردن چیزهایی. و من به هیئت مدیره در اینجا این زمان را اجرا کنید. 

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

بنابراین اگر شماره 9، یکی از اولین وجود دارد در 5 صبح، پیش بروید و خط، و یا شب قبل از. OK را بزنید. بنابراین در حال حاضر 9 است در اینجا. بنابراین 9 در جلو از لیست است. بنابراین من قصد دارم به جلو بروید و به روز رسانی اندازه این اطلاعات در حال حاضر ساختار نمی شود (0) دیگر، اما به 1. من قصد دارم برای قرار دادن 9 در جلو از لیست. بگذار بروم جلو و ضامن صفحه نمایش بنابراین ما می توانیم گذشته ما اینجا را ببینید. 

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

مخاطبان: ما می تواند حرکت کند - 

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

در واقع، بیایید ببینید که. قبل از اینکه ما 22 وارد کنید، اجازه دهید پیش بروید و dequeue 9. نام شما چیست؟ دوباره؟ 

مخاطبان: جیک. 

دیوید مالان: جیک در حال رفتن است به هم اکنون dequeued. بنابراین شما می توانید به فروشگاه راه رفتن. و وانمود کنید که فروشگاه بیش از وجود دارد. بنابراین در حال حاضر چه نیاز - DIT-DIT-DIT! چه نیاز دارد اتفاق می افتد در حال حاضر؟ تصمیم گیری طراحی. بنابراین نه یک غریزه بد است، اما - نام شما چیست دوباره؟ 

مخاطبان: دیوید. 

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

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

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

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

خب، چه اتفاقی می افتد؟ نوبت قراردادن بیایید - نام شما چیست؟ 

مخاطبان: Callen. 

دیوید مالان: Callen. اجازه دهید نوبت قراردادن Callen، و 22 در حال حاضر در صف. بنابراین در حال حاضر چه چیزی برای تغییر در اینجا؟ جبهه رفتن به تغییر، بدیهی است. حجم در حال رفتن به تغییر به 2 دوباره. و 22 به پایان می رسد تا در اینجا، 9 است که هنوز هم در حال حاضر، اما آن را به طور موثر ارزش شرکت زباله. این فقط یک باقی مانده از گذشته جیک. 

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

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

مخاطبان: شما از مرزهای هستید. 

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

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

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

هر گونه سؤال در پشته، یا این صف؟ 

مخاطبان: آیا به همین دلیل شما نیاز به اندازه بنابراین شما می دانید که در آن به یک شخص؟ 

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

همه درست است؟ دور از کف زدن برای این بچه ها و ما به آنها اجازه دهید وجود دارد. 

[تشویق حضار] 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

من فکر کردم من می خواهم به شما یک تیزر از چیزی است که شما قادر به انجام پس از در نظر گرفتن CS50. اجازه دهید من به cs.harvard.edu / راب بروید، پیام خصوصی به خودمان راب Bowden. او این کار را برای ما ساخته شده است. بنابراین شما به زودی قادر خواهید بود به انجام این کار باشد. و همچنین، چیزی که شما شنیده این صبح - آنچه شما شنیده ام این صبح - 

[همستر DANCE MUSIC] 

- گرفتند دیگر قادر به انجام این کار است. انتظار ما در روز چهارشنبه. ما بعد از آن شما را ببینید. 

[همستر DANCE MUSIC] دیوید مالان: در CS50 بعدی -