[MUSIC پخش] DAVID J. مالان: خوب. این CS50 است. این هفته پنج ادامه داد، و ما برخی از خبر خوب و یک خبر بد. پس خبر خوب این است که CS50 راه اندازی این جمعه. اگر شما می خواهم برای پیوستن به ما، سر به URL معمول است. اخبار حتی بهتر، بدون سخنرانی این آینده دوشنبه از 13TH. کمی کمتر بهتر از اخبار، مسابقه صفر چهارشنبه آینده است. جزئیات بیشتر را می توان که در این URL را در اینجا. و در طی چند روز آینده ما در جاهای خالی پر با توجه به اتاق که ما محفوظ خواهد. اخبار بهتر است که وجود دارد خواهید یک بررسی البته گسترده جلسه این آینده دوشنبه شب. اقامت به البته در تنظیم وب سایت برای مکان و جزئیات. بخش ها، حتی اگر آن است که یک تعطیلات، نیز به خوبی تامین کند. بهترین اخبار، سخنرانی روز جمعه. بنابراین این ما سنت است ، به عنوان در هر برنامه درسی. Just-- آن را به شگفت انگیز است. شما چیزهایی مانند دیدن ساختمان داده زمان ثابت و جداول هش و درختان و تلاش می کند. و ما در مورد مشکلات تولد صحبت کنید. دسته کامل از مسائل در انتظار روز جمعه. OK. به هر حال. پس به یاد آورید که ما شده است تمرکز بر این تصویر از چه در داخل از حافظه کامپیوتر را می دهد. بنابراین حافظه یا RAM که در آن برنامه است وجود داشته باشد در حالی که شما آنها را در حال اجرا. اگر شما دوبار کلیک کنید آیکون برای اجرای برخی از برنامه و یا دوبار کلیک کنید آیکون برای باز کردن بعضی از فایل، آن را از سخت شما بارگذاری رانندگی و یا درایو حالت جامد به RAM، حافظه دسترسی تصادفی، که در آن آن زندگی می کند تا زمانی که قدرت خاموش می رود، درب لپ تاپ بسته می شود، و یا شما را ترک برنامه است. 

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

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

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

رسید توابع. 

DAVID J. مالان: برای توابع؟ در چه حس برای توابع؟ 

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

DAVID J. مالان: دقیقا. هنگامی که شما یک تابع فراخوانی، آن استدلال را بر روی پشته کپی می شود. بنابراین هر X یا Y است و یا یا در B که شما عبور را به یک تابع به طور موقت قرار داده و در پشته به اصطلاح، درست مثل یکی از آننبرگ سینی های غذاخوری، و همه چیز مانند متغیرهای محلی. اگر تابع مواد غذایی خود را و یا مبادله خود را تابع باید متغیرهای محلی، مثل درجه حرارت، آن دو در نهایت بر روی پشته. در حال حاضر، ما نمی خواهد بیش از حد صحبت کردن در مورد آنها را، اما این متغیر های محیط زیست در پایین دیدیم در حالی که پیش زمانی که من در صفحه کلید یک روز futzing شد آغاز شده و من دسترسی به همه چیز مانند argv را 100 یا argv را 1000، فقط elements-- I را فراموش کرده ام numbers-- اما شد قرار نیست به من دسترسی. ما شروع به دیدن برخی از کاراکتر های بد بو بر روی صفحه نمایش. کسانی که به اصطلاح بود متغیر های محیط زیست مانند تنظیمات جهانی برای من برنامه یا کامپیوتر من، نه غیر مرتبط با اخیر مشکلات را که مورد بحث ما، Shellshock، که شده است فاکتورها باعث ایجاد پلاک کاملا چند کامپیوتر. 

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

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

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

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

رسید از پشته. 

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

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

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

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

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

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

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

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

اما در حال حاضر سعی کنید به سرعت رو به جلو. چه در مورد این است که اتفاق می افتد اگر تصویب ما در نوار رشته که بیش از ج؟ و ما در حال چک کردن اگر آن را در واقع بیش از 12. کدام بخش از این تصویر در حال رفتن به توسط کلمه در ادامه متن 0، ​​1، 2، 3 رونویسی، نقطه نقطه نقطه، 11، و پس از آن بد، 12، 13 تا 19؟ آنچه در اینجا اتفاق می افتد، اگر شما از سفارش استنباط که ج براکت 0 است در بالا و ج براکت 11 است مرتب سازی بر اساس پایین در سمت راست؟ آره؟ 

رسید: خوب، این رفتن به بازنویسی نوار کاراکتر *. 

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

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

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

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

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

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

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

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

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

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

و Valgrind، یکی از ابزار معرفی شده در Pset 4، همه چیز در مورد کمک به شما در حال حاضر اشکالات مانند آن را پیدا کنید. اما از خود گذشتگی برای Pset 4 شما لازم نیست برای استفاده از کتابخانه CS50 یا getstring. بنابراین هر گونه اشکالات مربوط به حافظه در نهایت رفتن به خود شما. 

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

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

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

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

DAVID J. مالان: متاسفم؟ 

رسید آن را در پایان. 

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

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

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

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

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

پس چه می شود اگر، به جای فقط ذخیره سازی اعداد، مانند 9، 17، 22، 26، 34، اگر ما ذخیره نمی شوند تنها تعداد اما یک اشاره گر در کنار هر عدد مانند؟ به طوری که بسیار شبیه به شما یک موضوع سوزن از طریق یک دسته کامل از پارچه، همه چیز به نحوی تساوی با هم، به طور مشابه می تواند ما با اشاره گر، به عنوان تجسم های فلش در اینجا، نوع با هم بافتن این مستطیل فردی به طور موثر با استفاده از اشاره گر در کنار هر تعداد که اشاره به برخی از عدد بعدی، که اشاره به، به نوبه خود، برخی از عدد بعدی؟ بنابراین به عبارت دیگر، آنچه که اگر ما در واقع می خواستم برای پیاده سازی چیزی شبیه به این؟ خوب متاسفانه، این مستطیل ها، حداقل یکی از با 9، 17، 22، و به این ترتیب، این دیگر مربع زیبا با اعداد یک. پایین، مستطیل زیر 9، به عنوان مثال، نشان دهنده چیزی است که باید یک اشاره گر، 32 بیت. در حال حاضر، من هنوز از هر نوع داده آگاه نیست در C است که به شما نه تنها یک int اما یک اشاره گر در دسترس نباشد. 

پس چه راه حل اگر ما می خواهیم به اختراع جواب خود ما در این؟ آره؟ 

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

DAVID J. مالان: آن چیست؟ 

رسید ساختار جدید. 

DAVID J. مالان: آره، پس چرا ما یک ساختار جدید ایجاد کنید، و یا در C، یک ساختار؟ ما ساختار دیده می شود قبل از، اگر به طور خلاصه، که در آن ما با یک ساختار دانش آموز سر و کار داشتن مثل این که یک نام و یک خانه داشت. در Pset 3 برک آوت شما با استفاده از یک کل دسته از GRect structs-- و GOvals که استنفورد به ایجاد اطلاعات خوشه با هم. بنابراین اگر ما این ایده را مشابه از کلمات کلیدی "typedef" و "ساختار" و پس از آن برخی چیزهای خاص به دانش آموزان، و تکامل این به شرح زیر است: typedef ساختار node-- و گره است فقط یک علم کامپیوتر بسیار عمومی مدت چیزی در یک ساختار داده ها، یک ظرف در یک ساختار داده ها. یک گره I ادعا است که به تعداد اعضای هیات، کاملا سر راست، و پس از آن کمی cryptically بیشتر، این خط دوم، گره ساختار * بعدی. اما از نظر فنی کمتر، آنچه که خط دوم است کد داخل آکولاد؟ آره؟ 

رسید [نامفهوم] DAVID J. مالان: اشاره گر به گره دیگر. بنابراین مسلما، نحو (Syntax) کمی مرموز. اما اگر شما آن را به عنوان خوانده شده به معنای واقعی کلمه، بعد به نام یک متغیر است. نوع داده آن چیست؟ این یک کمی طولانی این زمان، اما از نوع گره ساختار است *. هر زمان دیده ایم چیزی ستاره، که به معنی آن است که یک اشاره گر به نوع داده است. بنابراین بعد ظاهرا اشاره گر به گره ساختار. 

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

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

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

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

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

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

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

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

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

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

رسید ما نیاز به یک اشاره گر به گره. DAVID J. مالان: یک اشاره گر به گره. به طور خاص، که گره را خود غرایز است برای حفظ یک اشاره گر به؟ 

رسید اولین گره. 

DAVID J. مالان: آره، احتمالا فقط در صفحه اول و متوجه، اولین گره یک شکل متفاوت است. این تنها نیمی از اندازه از ساختار است، زیرا این در واقع تنها یک اشاره گر. بنابراین آنچه شما در واقع می تواند انجام دهد، اعلام یک لیست پیوندی به گره نوع است *. و اجازه دهید فقط آن را برای اولین بار تماس بگیرید و مقدار دهی اولیه آن را به تهی. بنابراین تهی، دوباره، به زودی را به تصویر اینجا. نه تنها null به عنوان مثل یک خاص استفاده می شود مقدار بازگشتی برای چیزهایی مانند getstring و malloc، پوچ است نیز صفر اشاره گر، به دلیل نبود یک اشاره گر، اگر شما خواهد شد. این فقط به معنای چیزی است که هنوز در اینجا. در حال حاضر برای اولین بار، من می تونستیم نام این هر چیزی. من می توانم آن را "فهرست" نامیده می شود و یا هر تعداد از چیزهای دیگر. اما من آن را خواستار "اولین" به طوری که خطوط آن را با این عکس. بنابراین درست مثل یک رشته را می توان ارائه با آدرس اولین بایت آن، بنابراین می توانید یک لیست پیوندی. و ما به داده های دیگر را ببینید ساختار به نمایندگی تنها با یک اشاره گر، 32 بیتی فلش، با اشاره در اولین گره در ساختار. 

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

تا زمانی که ما در حال نخ کشیدن برگهای توتون تمام این گره با هم، تنها یاد آوردن جایی که یکی از اولین است، تا زمانی ما به عنوان یک نماد ویژه در قرار داده آخرین گره در لیست، و ما تهی استفاده کنید، زیرا که آنچه که ما را در دسترس ما، این لیست کامل می باشد. و حتی اگر فقط من به شما یک اشاره گر را به عنصر اول، شما، برنامه نویس، مطمئنا می تواند بقیه از آن دسترسی داشته باشید. اما اجازه دهید اجازه دهید ذهن شما سرگردان کمی، اگر آنها در حال حاضر نمی کاملا wandered-- چه رفتن به زمان در حال اجرا از پیدا کردن هر چیزی در این لیست؟ لعنت آن، آن را O بزرگ از n است، است که بد نیست، در انصاف. اما این خطی است. ما شده اند تا با توجه به آنچه از ویژگی های آرایه های حرکت بیشتر به سمت این تصویر از به صورت پویا با هم بافته شده و یا گره های مرتبط است؟ ما تا دسترسی تصادفی داده ام. یک آرایه خوب است زیرا است همه چیز ریاضی بازگشت به عقب به عقب به عقب. هر چند این تصویر به نظر می رسد بسیار، و حتی هر چند آن را مانند این به نظر می رسد گره سادگی فاصله از هم جدا، در واقعیت آنها در هر نقطه می تواند باشد. OX1، Ox50، Ox123، Ox99، این گره در هر نقطه می تواند باشد. از آنجا که malloc تخصیص حافظه می کند از پشته، اما در هر نقطه از پشته. شما لزوما نمی دانند که این رفتن به پشت به پشت به پشت. و به این ترتیب این تصویر در واقع در نمی شود کاملا این بسیار. 

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

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

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

اگر من شما را در این پیدا کردن، من هستم رفتن به خواهید برای انجام کاری مانند اعلام کند که ما در بر داشت نفر. و ما را ترک که به عنوان یک ارسال نظر یا کد شبه. دیگری، و در اینجا بخش جالب، چه من می خواهم به انجام اگر گره فعلی است شامل n که من اهمیت ندارد؟ چگونه این کارها را رسیدن به من؟ اگر انگشت من در لحظه PTR است، و آن را اشاره در هر برای اولین بار است اشاره در، چگونه انگشت من حرکت من به گره بعدی در کد؟ خوب، چه خرده نان ما است به دنبال در این مورد؟ رسید [نامفهوم]. DAVID J. مالان: آره، تا بعد. بنابراین اگر من به بازگشت به من کد اینجا، در واقع، من رفتن به جلو بروید و می گویند اشاره گر، که فقط یک variable-- موقت آن است یک نام عجیب و غریب، PTR، اما درست مثل temp-- من قصد دارم به راه اشاره گر به هر اشاره گر is-- برابر و دوباره، این است که برای رفتن به یک حشره دار کمی برای یک نقطه moment-- بعدی. به عبارت دیگر، من قصد دارم به من انگشت که اشاره به این گره در اینجا و من قصد دارم برای گفتن، شما می دانید چه، نگاهی به زمینه بعدی و حرکت انگشت خود را به هر چه آن را اشاره در. و این است که به تکرار، تکرار، تکرار کنید. اما وقتی انگشت من می کند جلوگیری از انجام هر چیزی در همه؟ به محض این که چه خط از ضربات کد در؟ رسید [نامفهوم] DAVID J. مالان: اگر در حالی که نقطه اشاره گر برابر تهی نیست. در برخی از نقطه انگشت من رفتن به اشاره است در تهی و من قصد دارم به درک که در پایان به این لیست است. در حال حاضر، این است که کمی دروغ های سفید برای سادگی. به نظر می رسد که حتی اگر ما فقط یاد گرفته این نماد نقطه برای سازه، اشاره گر است یک ساختار نیست. PTR چیزی است؟ فقط به nitpicky است. این یک اشاره گر به یک گره است. این یک گره به خودی خود نیست. اگر من تا به حال هیچ ستاره در اینجا، اشاره گر absolutely-- آن یک گره است. این مثل یک هفته تعریف یک متغیر، حتی اگر کلمه "گره" جدید است. 

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

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

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

بنابراین اجازه دهید این کار را انجام. اگر شما که به طنز من اینجا، من را یک دسته از توپ های استرس. من یک دسته از اعداد به ارمغان آورد. و می تواند ما فقط چند داوطلب برای نشان دادن 9، 17، 20، 22، 29، و 34؟ بنابراین اساسا همه که امروز در اینجا. این یکی، دو، سه بود، چهار، پنج، شش نفر. و از من خواسته شده به go-- مشاهده کنید، هیچ یکی در پشت دست خود را بالا می برد. OK، یک، دو، سه، چهار، five-- اجازه دهید من بار balance-- شش. OK، شما شش در آمده است. ما افراد دیگر نیاز دارند. ما توپ های استرس اضافی به ارمغان آورد. و اگر شما می توانید، برای فقط یک لحظه، خط خود فقط مثل این عکس بنویسید. 

خوب. بیایید ببینید، چه نام شما چیه؟ 

رسید اندرو. 

DAVID J. مالان: اندرو، شما شماره 9 می باشد. از ملاقات شما خوشبختم. در اینجا شما بروید. رسید جن. DAVID J. مالان: جن. دیوید. شماره 17. بله؟ 

رسید من جولیا هستم. 

DAVID J. مالان: جولیا، دیوید. شماره 20. رسید مسیحی. DAVID J. مالان: مسیحی، دیوید. شماره 22. و؟ 

رسید JP. DAVID J. مالان: JP. شماره 29. پس پیش بروید و in-- اوه اوه. اوه اوه. آماده به کار. 20. آیا کسی که یک مارکر؟ رسید من Sharpie کردم. DAVID J. مالان: شما Sharpie کردم؟ OK. و یا کسی که یک تکه کاغذ؟ صرفه جویی در سخنرانی. بیا. رسید ما آن را کردم. DAVID J. مالان: ما آن را کردم؟ خوب، از شما سپاسگزارم. در اینجا ما بروید. این از شما بود؟ شما فقط روز را نجات داد. بنابراین 29. خوب. من اشتباه 29، اما OK. برو جلو. خوب، من به شما می دهد قلم خود را به عقب لحظه ای. بنابراین ما باید این دوستان در اینجا. بیایید یک دیگر داشته باشد. گیب، آیا شما می خواهید بازی عنصر اول که اینجا هستید؟ ما شما نیاز به نقطه در این دوستان خوب است. بنابراین 9، 17، 20، 22، مرتب کردن بر اساس از 29، و پس از آن 34. آیا ما به کسی از دست می دهند؟ من یک 34. از کجا did-- OK، که می خواهد به 34؟ OK، در آمد تا، 34. خوب، این خواهد بود به خوبی به ارزش اوج. نام شما چیست؟ 

رسید پیتر. 

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

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

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

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

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

بنابراین این آغاز داستان ما بود. و در حال حاضر این فقط ساده، حتی اگر از دستور جدید است. از نظر مفهومی این فقط جستجوی خطی است. آیا 55 برابر با 9؟ یا نه، اجازه دهید کمتر از 9 می گویند. از آنجا که من در تلاش برای کشف کردن که در آن برای قرار دادن 55. کمتر از 9، کمتر از 17، کمتر از 20، کمتر از 22، کمتر از 29، کمتر از 34، نه. بنابراین در حال حاضر ما در مورد هستید یکی از حداقل سه. 

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

بنابراین در حال حاضر اگر بعد سناریو می آید همراه، و ما می خواهیم برای وارد کردن در شروع و یا سر به این لیست؟ و چه نام شما، شماره 55 است؟ 

رسید جک. 

DAVID J. مالان: جک؟ OK، ملاقات با شما خوشبختم. روی خوش آمدید. بنابراین در حال حاضر ما در حال رفتن به وارد کردن، می گویند، تعداد 5. در اینجا مورد دوم است سه ما با قبل از آمد. بنابراین اگر 5 متعلق در آغاز، بیایید ببینید که چگونه پیدا کنیم که از. I مقداردهی اولیه PTR من اشاره گر به تعداد 9 دوباره. و من متوجه شدم، آه، 5 است کمتر از 9. پس این تصویر را برای ما حل کنند. چه کسانی به دست، در گیب و یا دیوید or-- چه نام تعداد 9 چیست؟ 

رسید جن. 

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

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

رسید کریستین. 

DAVID J. مالان: کریستین. روی خوش آمدید. همه حق است، بنابراین اجازه دهید در حال حاضر در نظر یک سناریوی کمی بیشتر آزار دهنده، به موجب آن من می خواهم برای وارد کردن چیزی شبیه به 26 را به این. 20؟ چه؟ این are-- چیز خوبی که داریم این قلم. همه حق است، 20. اگر کسی می تواند قطعه دیگری از دریافت مقاله آماده، فقط در case-- همه حق. اوه، جالب است. خب این یک مثال است از یک اشکال سخنرانی. OK چه خوب دوباره نام خود را؟ رسید جولیا. DAVID J. مالان: جولیا، می تواند به شما پاپ و وانمود کنید که هرگز آنجا نبودی؟ OK، این هرگز اتفاق افتاده است. با تشکر از شما. بنابراین فرض کنید ما می خواهیم وارد جولیا به این لیست در ارتباط است. او تعداد 20 است. و البته او رفتن به تعلق در begin-- را در هر چیزی اشاره نشده است. پس دست خود را نوع می تواند پایین صفر و یا برخی از ارزش زباله. اجازه دهید داستان سریع بگویید. من اشاره در شماره 5 این زمان. سپس من تیک بزنید 9. سپس من تیک بزنید 17. سپس من تیک بزنید 22. و من می دانم، آه، جولیا باید قبل از 22 است. پس چه اتفاقی باید بیفتد؟ چه کسانی به دست نیاز به تغییر؟ در جولیا، معدن، or-- چه نام خود را دوباره چیست؟ 

رسید مسیحی. 

DAVID J. مالان: مسیحی یا؟ 

رسید اندی. 

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

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

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

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

رسید جک. 

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

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

بنابراین، هنگامی که سر از لیست است حذف، که دست نیاز به تغییر در حال حاضر؟ نام و نام خانوادگی خود را دوباره چه خبر؟ 

رسید کریستین. 

DAVID J. مالان: I افتضاح هستم در نام، ظاهرا. بنابراین کریستین و گیب، که دست نیاز به تغییر زمانی که ما سعی می کنیم به حذف کریستین، شماره 5، از تصویر؟ OK، بنابراین اجازه دهید کار را انجام گیب. گیب رفتن به نقطه، احتمالا، در شماره 9. اما بعد چه باید اتفاق می افتد؟ رسید کریستین باید تهی است [نامفهوم]. DAVID J. مالان: OK، ما باید احتمالا make-- من شنیده ام "تهی" جایی. رسید نول و آزاد خود را. DAVID J. مالان: تهی چه؟ رسید نول و آزاد خود را. DAVID J. مالان: صفر و آزاد خود را. بنابراین این بسیار آسان است. و این عالی است که شما هم اکنون به نوعی هستیم ایستاده وجود دارد، نه متعلق. از آنجا که شما بوده ام جدا از لیست. شما به طور موثر بوده است یتیم را از لیست. و به این ترتیب ما بهتر بود تماس رایگان در حال حاضر در کریستین را که حافظه را به عقب. در غیر این صورت هر زمان که ما حذف یک گره از لیست ما ممکن است به این ترتیب فهرست کوتاه تر، اما در واقع کاهش نیست اندازه در حافظه است. و به این ترتیب اگر ما به حفظ اضافه و اضافه کردن، اضافه کردن چیزهایی به لیست، کامپیوتر من ممکن است آهسته تر و کندتر و آهسته تر، چرا که من در حال اجرا هستم از حافظه، حتی اگر من در واقع نه با استفاده از بایت کریستین را حافظه دیگر. 

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

[تشویق حضار] 

DAVID J. مالان: خوب. بنابراین زن و شوهر از تحلیلی سوالات و سپس، اگر من می تواند. ما این نماد دیده می شود قبل از، O بزرگ و امگا، مرزهای بالایی و مرزهای پایین تر در زمان برخی از الگوریتم در حال اجرا. بنابراین اجازه دهید فقط در نظر یک زن و شوهر از سوالات. 

یک، و ما آن را گفت: قبل، چه در حال حرکت است زمان جستجو برای لیست در نظر O بزرگ؟ چه یک حد بالا در حال اجرا زمان جستجو یک لیست پیوندی که توسط داوطلبان ما اجرا که اینجا هستید؟ این O بزرگ از n، خطی است. از آنجا که در بدترین حالت، این عنصر، مانند 55، ما ممکن است به دنبال ممکن است که در آن جک تمام راه در پایان بود. و متاسفانه، بر خلاف یک آرایه ما نمی توانیم دریافت فانتزی این زمان. حتی اگر همه انسانها ما بودند طبقه بندی شده اند از عناصر کوچک، 5، تمام راه را تا به این عنصر بزرگتر، 55، که معمولا چیز خوبی است. اما این به چه فرض دیگر به ما اجازه انجام دهید؟ رسید [نامفهوم] DAVID J. مالان: بگو دوباره؟ رسید دسترسی تصادفی. DAVID J. مالان: دسترسی تصادفی. و به نوبه خود این بدان معناست که ما می توانیم بدون دیگر استفاده از صفر ضعیف، شهود، و گویایی از با استفاده از باینری جستجو و تقسیم و تسخیر. از آنجا که حتی اگر ما انسان به وضوح می تواند ببینید که اندی و یا مسیحی بودند تقریبا در وسط این فهرست، ما تنها می دانیم که به عنوان یک کامپیوتر های دستکاری لیست از همان ابتدا. بنابراین ما تا که دسترسی تصادفی داده ام. 

O پس بزرگ از n در حال حاضر بالا است محدود در زمان جستجو است. چه در مورد امگا از جستجوی ما؟ چه پایین تر حد در جستجو است برای برخی از تعداد در این لیست؟ رسید [نامفهوم] DAVID J. مالان: بگو دوباره؟ رسید یکی. DAVID J. مالان: یک. زمان ثابت است. در بهترین حالت، کریستین است در واقع در ابتدای فهرست. و ما به دنبال شماره 5، پس ما او را در بر داشت. بنابراین هیچ معامله بزرگ است. اما او کردم به در می شود شروع از لیست در این مورد. چه در مورد چیزی شبیه حذف شود؟ چه می شود اگر شما می خواهید یک عنصر را حذف کنید؟ چه حد بالا و حد پایین تر در حذف چیزی را از یک مرتبط لیست؟ رسید [نامفهوم] DAVID J. مالان: بگو دوباره؟ رسید نفر. DAVID J. مالان: نفر است در واقع حد بالای. از آنجا که در بدترین حالت ما سعی می کنیم برای حذف جک، که ما فقط. او تمام راه را در پایان است. ما طول می کشد برای همیشه لطفا برای، و یا نفر گام برای رسیدن به او پیدا کنید. به طوری که یک حد بالا. که خطی است، مطمئن شوید. و بهترین حالت زمان در حال اجرا، و یا از مرزهای پایین تر در بهترین حالت خواهد بود زمان ثابت است. از آنجا که شاید ما سعی می کنیم را حذف کنید کریستین، و ما فقط خوش شانس او در آغاز راه است. حالا یک دقیقه صبر کنید. گیب نیز در آغاز بود، و ما نیز تا به حال به روز رسانی گیب. به طوری که فقط یک قدم نیست. پس از آن در واقع ثابت زمان، در بهترین حالت، برای حذف کوچکترین عنصر؟ این است، اگر چه آن ممکن است دو، سه، و یا حتی 100 خط کد، اگر آن را به همان تعداد از این خطوط، در برخی از حلقه، و مستقل از اندازه از لیست، کاملا. حذف عنصر در ابتدای فهرست، حتی اگر ما را برای مقابله با گیب، هنوز زمان ثابت است. 

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

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

ما همچنین در حال گذراندن فضا. به چه معنا است مرتبط لیست گران تر از نظر فضا از یک آرایه؟ فضای اضافی از کجا می آید؟ آره؟ 

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

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

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