>> [موسیقی]
>> داگ لوید: خوب، پس در این نقطه در این دوره،
ما بسیاری از اصول اولیه C. تحت پوشش ما می دانیم که بسیاری در مورد متغیرها، آرایه ها،
اشاره گرها، که چیزهای خوب است.
کسانی که همه نوع ساخته شده است به عنوان اصول را مشاهده کنید،
اما ما می توانیم بیش از این انجام، درست است؟
ما می توانیم چیزهایی ترکیب با هم در راه جالب است.
>> و بنابراین اجازه انجام آن، اجازه دهید شروع به شعبه از آنچه C به ما می دهد،
و شروع به ایجاد اطلاعات خود ما ساختار با استفاده از این ساختمان
بلوک های با هم برای انجام کاری واقعا با ارزش، مفید است.
یکی از راه های انجام این کار ما می توانیم است به مجموعه صحبت کنید.
بنابراین تا کنون ما یک نوع از داده ها داشته ام ساختار برای نمایش مجموعه
از ارزش ها، ارزش های مشابه را دوست دارم.
این امر می تواند یک آرایه.
ما مجموعه ای از اعداد صحیح، و یا مجموعه ای از شخصیت و غیره.
>> سازه نیز از داده های مرتب کردن بر اساس ساختار برای جمع آوری اطلاعات،
اما آن را برای جمع آوری مانند ارزش است.
این حالت معمولا مخلوط انواع داده های مختلف با هم داخل یک جعبه.
اما این به خودی خود نمی با استفاده از زنجیره ای با هم
و یا اتصال با هم مشابه اقلام، مانند یک آرایه.
آرایه های بزرگ هستند عنصر نگاه کردن، اما به یاد
که آن را بسیار دشوار برای وارد کردن به یک آرایه،
مگر اینکه ما در حال قرار دادن در پایان بسیار از آن آرایه.
>> بهترین مثال من برای که مرتب سازی درجی است.
اگر شما به خاطر ویدئو ما در مرتب سازی بر درج،
بود که بسیاری از وجود دارد هزینههای داشتن
انتخاب کنید تا به عناصر، و تغییر آنها از راه به جا چیزی
به وسط آرایه خود را.
آرایه نیز از دیگر رنج می برند مشکل، که عدم انعطاف است.
هنگامی که ما اعلام می کنیم یک آرایه، ما یک شات در آن است.
ما را وادار به گفتن نیست، من می خواهم این بسیاری از عناصر.
ممکن است 100، ممکن است شود 1،000، آن را ممکن است
X که در آن X یک عدد است که کاربر باشد ما در یک اعلان یا در دستور داد
خط.
>> اما ما فقط یک شات در آن، ما نمی تواند به پس از آن می گویند آه، در واقع من
مورد نیاز 101، و یا من نیاز به اضافه 20 X.
خیلی دیر شده، ما در حال حاضر اعلام کرده ام آرایه، و اگر ما می خواهیم به 101 یا X
به علاوه 20، ما باید به اعلام یک آرایه کاملا متفاوت است،
کپی کردن تمام عناصر آرایه بیش از، و پس از آن ما به اندازه کافی.
و اگر ما دوباره اشتباه هستند، چه اگر ما در واقع نیاز به 102، و یا X به علاوه 40،
ما باید به انجام این کار دوباره.
به طوری که آنها بسیار انعطاف ناپذیر هستند برای تغییر اندازه داده های ما،
اما اگر ما با هم برخی از ترکیب از اصول اولیه است که ما در حال حاضر
در مورد اشاره گر ها و سازه ها به دست، به طور خاص با استفاده از حافظه پویا
تخصیص با malloc، ما می توانید این قطعه را با هم
برای ایجاد یک داده جدید structure-- تنهایی لیست ما ممکن است می گویند مرتبط
که اجازه می دهد تا ما را به رشد و کوچک مجموعه ای از ارزش ها
و ما هر فضای هدر رفته را ندارد.
>> پس دوباره، پاسخ این ایده، این مفهوم، یک لیست پیوندی.
به ویژه، در این فیلم ما صحبت کردن در مورد لیست تنهایی مرتبط،
و پس از آن یکی دیگر از فیلم ما صحبت لیست مورد مضاعف مرتبط است، که
فقط یک تنوع در تم در اینجا است.
اما یک لیست تنهایی مرتبط از گره تشکیل شده است،
گره فقط به عنوان یک term-- انتزاعی این تنها چیزی است که من آنرا است
که یک نوع از این ساختار، اساسا، من؟
فقط رفتن به آن را یک node-- و این گره دو عضو، و یا دو حوزه.
از آن است که داده ها، معمولا عدد صحیح، یک شناور شخصیت،
و یا می تواند برخی از نوع داده دیگر که شما با دف ​​نوع تعریف شده است.
و آن را یک اشاره گر به گره دیگر از همان نوع.
>> بنابراین ما باید دو چیز داخل این گره، داده ها و یک اشاره گر
به گره دیگر است.
و اگر شما شروع به تجسم این، شما می توانید در مورد آن فکر می کنم
مثل یک زنجیره ای از گره های که به یکدیگر متصل هستند.
ما گره اول، آن شامل داده ها، و یک اشاره گر
به گره دوم، که شامل داده ها، و یک اشاره گر به گره سوم.
و به طوری که به همین دلیل ما آن را به یک پاسخ لیست پیوندی، آنها با هم مرتبط است.
>> چه می کند این ویژه ساختار گره نگاه می کنید؟
خوب، اگر شما از ویدیو های ما در یاد تعریف نوع سفارشی، با نوع دف،
ما می توانیم یک تعریف و structure-- نوع تعریف یک ساختار شبیه به این.
tyepdef sllist ساختار، و پس از آن من با استفاده از ارزش کلمه در اینجا خودسرانه
برای نشان دادن هر نوع داده واقعا.
شما می توانید در یک عدد صحیح و یا شناور عبور، شما می توانید هر آنچه که شما می خواهید.
این فقط به محدود نمی اعداد صحیح، و یا هر چیزی شبیه به آن.
بنابراین ارزش است فقط یک خودسرانه نوع داده، و سپس یک اشاره گر
به گره دیگر از همان نوع.
>> در حال حاضر، یک گرفتن کمی وجود دارد در اینجا با تعریف یک ساختار
هنگامی که آن را به یک ساختار خویشتن است.
من به طور موقت نام برای ساختار است.
در پایان روز من به وضوح می خواهید به آن پاسخ
گره SLL که در نهایت جدید نام بخشی از تعریف نوع من،
اما من می تواند گره SLL استفاده نمی در وسط این.
دلیل بودن من نه ایجاد یک نوع به نام گره SLL
تا زمانی که من این مرحله نهایی رسید در اینجا.
تا آن زمان، من به راه دیگری برای اشاره به این نوع داده ها.
>> و این یک خود است نوع داده ارجاعی.
این؛ این یک نوع داده یک ساختار که شامل یک داده ها،
و یک اشاره گر به یکی دیگر از ساختار همان نوع است.
بنابراین من باید قادر به مراجعه به این نوع داده حداقل به طور موقت،
بنابراین به آن موقت از ساختار sllist نام
من اجازه می دهد تا پس از آن می گویند من می خواهم یک اشاره گر به یکی دیگر از sllist ساختار،
یک ستاره sllist ساختار، و پس از آن پس از تعریف کامل شده است،
من هم اکنون می توانید این نوع گره SLL پاسخ.
>> به همین دلیل شما می بینید وجود دارد نام موقت در اینجا،
اما یک نام دائمی است.
گاهی اوقات شما ممکن است ببینید تعاریف ساختار،
به عنوان مثال، که نمی خویشتن، که
یک نام تعیین اینجا وجود ندارد.
این فقط می گویند ساختار از typedef، باز کردن آکولاد و سپس آن را تعریف کنیم.
اما اگر شما ساختار خود است ارجاع، به عنوان این یکی است،
شما نیاز به مشخص کردن یک نام نوع موقت است.
اما در نهایت، در حال حاضر که ما انجام داده ایم این
ما فقط می توانید برای اشاره این گره، این واحد،
به عنوان گره SLL برای اهداف از بقیه از این فیلم.
>> همه حق است، بنابراین ما می دانیم که چگونه به ایجاد یک لیست گره مرتبط است.
ما می دانیم که چگونه به تعریف یک گره لیست پیوندی.
حال اگر قصد داریم به شروع با استفاده از آنها برای جمع آوری اطلاعات،
یک زن و شوهر از انجام عملیات وجود دارد و ما نیاز به درک و کار با.
ما نیاز به دانستن چگونه برای ایجاد یک لیست پیوندی از هوا نازک.
اگر هیچ لیست وجود دارد در حال حاضر، ما می خواهیم برای شروع یک.
بنابراین ما باید قادر برای ایجاد یک لیست پیوندی،
ما نیاز به جستجو احتمالا از طریق لیست لینک
برای پیدا کردن یک عنصر ما دنبال آن هستید.
ما باید قادر به قرار دادن چیزهای جدید را به لیست،
ما می خواهیم لیست ما قادر به رشد می کنند.
و همین ترتیب، ما می خواهم که قادر را حذف کنید همه چیز از لیست ما،
ما می خواهیم لیست ما قادر به کوچک شدن.
و در پایان ما برنامه، به ویژه
اگر شما به خاطر است که ما تخصیص حافظه به صورت پویا
برای ساخت این لیست طور معمول، ما می خواهیم برای آزاد کردن همه که حافظه
هنگامی که ما در حال کار با آن انجام می شود.
و بنابراین ما باید قادر به حذف کل لیست پیوندی در از بین بردن یک شکست است.
بنابراین اجازه دهید از طریق رفتن برخی از این عملیات
و چگونه ممکن است آنها را تجسم، صحبت کردن در کد شبه به طور خاص.
بنابراین ما می خواهیم برای ایجاد یک لیست پیوندی، تا شاید ما
می خواهیم به تعریف یک تابع با این نمونه است.
SLL ستاره گره، ایجاد، و من عبور در یک آرگومان، برخی از داده های دلخواه
تایپ دوباره، از برخی از انواع داده های دلخواه.
اما من returning-- این تابع باید بازگشت به من یک اشاره گر، به تنهایی
گره لیست پیوندی.
باز هم، ما در حال تلاش برای ایجاد یک لیست پیوندی از هوا نازک،
بنابراین من نیاز به یک اشاره گر به این فهرست که من انجام می شود.
>> پس چه مراحل اینجا هستید؟
خب، اولین چیزی که من برای انجام شده است به صورت پویا
اختصاص فضا برای یک گره جدید.
باز هم، ما در حال ایجاد آن را از نازک هوا، بنابراین ما به فضای از malloc برای آن نیاز دارید.
و البته، بلافاصله پس از malloc ما،
ما همیشه بررسی کنید تا مطمئن شوید که ما اشاره گر ما می کنید تماس تهی.
چرا که اگر ما را امتحان کنید و احترام یک اشاره گر NULL،
ما در حال رفتن به رنج می برند segfault و ما این را نمی خواهیم.
>> پس ما می خواهیم برای پر کردن در این زمینه، ما می خواهیم به مقداردهی اولیه درست ارزش
و مقداردهی اولیه رشته بعدی.
و سپس ما to-- در نهایت به عنوان می خواهم نمونه indicates-- عملکرد ما می خواهیم
برای بازگشت به یک اشاره گر به یک گره SLL.
پس چه این مثل بصری نگاه می کنید؟
خب، اول ما قصد داریم به صورت پویا اختصاص فضا برای یک گره SLL جدید،
بنابراین ما malloc-- که نمایش تصویری
از گره ما فقط ایجاد شده است.
و ما را بررسی کنید تا مطمئن شوید که آن را در این مورد null-- نیست،
تصویر نمی خواهد که نشان داده شده است تا اگر آن را تهی بود،
ما را از حافظه اجرا، بنابراین ما خوب به آن بروید وجود دارد.
بنابراین در حال حاضر ما در حال به مرحله C، مقداردهی اولیه مقدار فیلد گره.
خب، بر اساس این تابع پاسخ من با استفاده از در اینجا،
به نظر می رسد مانند من می خواهم به تصویب در 6، بنابراین من 6 در زمینه ارزش.
در حال حاضر، مقداردهی اولیه رشته بعدی.
خب، چه هستم من برای انجام وجود دارد، هیچ چیز وجود دارد بعدی، راست،
این تنها چیزی است که در این لیست است.
پس چه چیزی که بعد از در لیست نیست.
>> آن را باید به هر چیزی نقطه نیست، راست.
هیچ چیز وجود دارد دیگری وجود دارد، پس چه شده است مفهوم ما که می دانیم این nothing--
اشاره گر به هیچ چیز؟
باید آن را شاید ما می خواهیم برای قرار دادن یک اشاره گر تهی وجود دارد،
و من تهی نشان اشاره گر به عنوان فقط یک جعبه قرمز،
ما نمی توانیم به هر بیشتر.
همانطور که خواهیم کمی بعد در دید، ما در نهایت زنجیره
از فلش اتصال این گره با هم،
اما زمانی که شما ضربه جعبه قرمز که تهی،
ما نمی توانیم به هر بیشتر، که پایان این فهرست است.
>> و در نهایت، ما فقط می خواهم بازگشت به یک اشاره گر به این گره.
بنابراین ما آن جدید پاسخ، و جدید باز خواهد گشت
پس از آن می توان در استفاده هر تابع آن ایجاد شده است.
بنابراین ما بروید، ما به تنهایی ایجاد کرده اید مرتبط گره لیست از هوا نازک،
و در حال حاضر ما یک لیست ما می توانیم با کار.
>> در حال حاضر، اجازه دهید ما می گویند در حال حاضر یک زنجیره ای بزرگ،
و ما می خواهیم برای پیدا کردن چیزی در آن است.
و ما می خواهیم یک تابع که رفتن برای بازگشت به درست یا غلط، بسته
در مورد اینکه آیا یک مقدار در این لیست وجود دارد.
یک نمونه تابع، یا بیانیه برای آن تابع،
ممکن است شبیه this-- بولی پیدا کنید، و پس ما می خواهیم به تصویب در دو آرگومان.
>> اول، یک اشاره گر به است اولین عنصر از لیست پیوندی.
این است که در واقع چیزی است که شما همیشه خواهید برای پیگیری از،
و در واقع ممکن است چیزی که شما حتی در یک متغیر جهانی قرار داده است.
هنگامی که یک لیست ایجاد می کنید، شما همیشه، همیشه
می خواهید برای پیگیری از بسیار اولین عنصر از لیست.
به این ترتیب شما می توانید به تمام دیگر مراجعه کنید عناصر تنها با زیر زنجیره ای،
بدون نیاز به نگه داشتن اشاره گر دست نخورده به هر عنصر.
شما فقط نیاز به پیگیری از اولین یک اگر همه آنها با هم زنجیر.
>> و پس از آن دومین چیزی ما در حال عبور دوباره
است خودسرانه some-- هر نوع اطلاعاتی که ما
به دنبال وجود دارد در داخل امیدوارم یکی از گره ها در لیست.
پس چه مراحل است؟
خب، اولین چیزی که ما انجام است یک اشاره گر عرضی
اشاره به سر لیست.
خب، چرا ما انجام این کار، ما در حال حاضر یک اشاره گر در سر لیست ها،
چرا ما فقط حرکت که در اطراف؟
خب، مثل من فقط گفت: این واقعا برای ما مهم
برای همیشه آهنگ از حفظ عنصر بسیار برای اولین بار در این فهرست است.
و پس از آن در واقع بهتر برای ایجاد یک کپی از آن،
و استفاده از آن به حرکت در اطراف بنابراین ما هرگز به طور تصادفی حرکت به دور، و یا ما همیشه
یک اشاره گر در برخی از نقطه است که در سمت راست عنصر اول لیست.
بنابراین بهتر است برای ایجاد یک دوم که استفاده می کنیم به حرکت.
>> سپس ما فقط اینکه آیا مقایسه زمینه ارزش که در آن گره
چیزی است که ما به دنبال آن هستید، و اگر آن را نیست، ما فقط به گره بعدی حرکت می کند.
و ما را انجام می دهند که بیش از، و بیش از، و بیش از،
تا زمانی که ما هم پیدا این عنصر، یا ما ضربه
null-- ما به پایان رسیده ام از لیست و آن وجود ندارد.
این باید امیدوارم حلقه زنگ به شما به عنوان تنها جستجوی خطی،
ما فقط آن را تکرار در ساختار لیست تنهایی مرتبط
به جای استفاده از یک آرایه به انجام آن.
>> بنابراین در اینجا یک مثال از یک لیست تنهایی مرتبط.
این یکی شامل پنج گره، و ما باید
یک اشاره گر به سر از لیست، که لیست نامیده می شود.
اولین چیزی که ما می خواهیم انجام دهیم این است دوباره، ایجاد می کند که اشاره گر پیمایش.
بنابراین ما در حال حاضر دو اشاره گر آن نقطه به همان چیزی است.
>> در حال حاضر، در اینجا متوجه همچنین، من نیست دارند به malloc هر فضا برای TRAV.
من نگفتم TRAV برابر از malloc چیزی، که گره حال حاضر وجود دارد،
که فضا در حافظه وجود دارد.
به طوری که تمام من در واقع انجام است ایجاد اشاره گر دیگری به آن.
من نمی mallocing اضافی فضا، فقط در حال حاضر دو اشاره گر
اشاره به همین است.
>> بنابراین 2 چه من به دنبال؟
خب، نه، بنابراین به جای من رفتن به حرکت به بعدی.
بنابراین اساسا من می گفت، TRAV برابر TRAV بعدی.
3 چه من به دنبال، نه.
بنابراین من همچنان به از طریق، تا در نهایت
به 6 است که در آنچه من به دنبال برای در فراخوانی تابع بر اساس
من از بالا به وجود دارد، و بنابراین من انجام می شود.
>> حالا اگر عنصر من به دنبال آن در لیست نیست،
آیا هنوز هم برای رفتن به کار می کند؟
خوب، توجه داشته باشید که فهرست در اینجا این است ماهرانه مختلف،
و این یک چیز دیگر است که با لیست های پیوندی مهم است،
شما لازم نیست که برای حفظ آنها را در هر منظور خاص است.
شما هم می توانید اگر شما می خواهید، اما شما ممکن است در حال حاضر متوجه
که ما در حال پیگیری از نگه داشتن نیست چه عنصر شماره ما را در.
>> و آن نوع از یک تجارت است که ما با لیست پیوندی آیات آرایه را داشته باشد،
است آن را ما لازم نیست دسترسی تصادفی نیست.
ما نه تنها می توان گفت، من می خواهم برای رفتن به عنصر 0،
و یا عنصر از آرایه 6 من، که من می توانم در یک آرایه انجام دهید.
من نمی توانم بگویم من می خواهم برای رفتن به عنصر 0، و یا عنصر 6،
و یا عنصر 25 از لیست پیوندی من، هیچ شاخص مرتبط با آنها وجود دارد.
و پس از آن واقعا مهم نیست اگر ما لیست ما به منظور حفظ کند.
اگر شما به شما می خواهید قطعا می توانید، اما وجود دارد
هیچ دلیلی وجود ندارد که آنها نیاز به تواند در هر جهت حفظ شده است.
پس دوباره، بیایید امتحان کنید و پیدا کردن 6 در این لیست است.
خب، ما در شروع آغاز، ما را پیدا کند 6،
و پس از آن ما همچنان به پیدا کردن نیست 6، تا زمانی که ما در نهایت به اینجا دریافت کنید.
بنابراین در حال حاضر TRAV نقطه به گره حاوی 8، و شش است در وجود ندارد.
>> بنابراین گام بعدی خواهد بود برای رفتن به اشاره گر،
می گویند TRAV برابر TRAV بعدی.
خب، TRAV بعدی، نشان داده شده جعبه قرمز وجود دارد، تهی است.
بنابراین در هیچ جای دیگری وجود دارد به رفتن، و بنابراین در این مرحله
می توان نتیجه گرفت که ما رسیدهاید در پایان از لیست پیوندی،
و 6 است در وجود ندارد.
و این امر می تواند بازگشت نادرست در این مورد.
>> OK، ما چگونه قرار دادن جدید گره به لیست پیوندی؟
بنابراین ما قادر به ایجاد شده یک لیست پیوندی از هیچ جا،
اما ما احتمالا می خواهید ایجاد یک زنجیره ای و نه
ایجاد یک دسته از لیست مجزا می باشد.
ما می خواهیم به یک لیست که دارای یک دسته از گره ها در آن،
نه یک دسته از لیست با یک گره.
بنابراین ما فقط نمی تواند با استفاده از درست عملکرد ما قبلا تعریف شده است، در حال حاضر ما
می خواهید برای وارد به یک لیست که در حال حاضر وجود دارد.
>> پس در این صورت، ما قصد داریم به تصویب در دو آرگومان،
اشاره گر به سر که لیست که ما می خواهیم برای اضافه کردن به مرتبط است.
باز هم، به همین دلیل آن را بسیار مهم است که ما همیشه
پیگیری آن، به دلیل آن را تنها راه ما واقعا
مجبور به مراجعه به کل لیست است فقط با یک اشاره گر به اولین عنصر.
بنابراین ما می خواهیم به تصویب در یک اشاره گر به آن عنصر اول،
و هر چه ارزش ما خواهید برای اضافه کردن به لیست.
و در نهایت این تابع رفتن به بازگشت یک اشاره گر
به رئیس جدید یک لیست پیوندی.
>> مراحل در اینجا چیست؟
خب، درست مانند با ایجاد، ما نیاز به صورت پویا تخصیص
فضا برای یک گره جدید، و بررسی کنید تا مطمئن ما را در اجرا از حافظه نیست، دوباره،
چرا که ما با استفاده از malloc.
پس از آن ما می خواهیم به جمعیت و قرار دادن گره،
بنابراین قرار دادن شماره، هر آنچه که وال است، به گره.
ما می خواهیم به قرار دادن گره در آغاز لیست پیوندی.
>> یک دلیل وجود دارد که من می خواهید برای انجام این کار، و آن
ممکن است ارزش گرفتن یک دوم به مکث ویدیو اینجا،
و فکر می کنم در مورد اینکه چرا من می خواهم قرار دادن در آغاز از یک مرتبط
لیست.
باز هم، من که قبلا ذکر شد که آن را واقعا نمی
مهم نیست اگر ما آن را در هر حفظ سفارش، شاید که یک سرنخ است.
و شما را دیدم اگر ما چه اتفاقی می افتد می خواستم to-- و یا از یک ثانیه
پیش زمانی که ما قرار بود از طریق جستجو شما
می تواند آنچه را ببینید ممکن است اگر ما در تلاش بودند
برای وارد کردن در پایان این فهرست است.
از آنجا که ما یک ندارد اشاره گر به انتهای لیست.
>> بنابراین به این دلیل است که من می خواهم برای وارد کردن در آغاز،
است چرا که من آن را بلافاصله انجام می.
من یک اشاره گر در آغاز، و ما این را در یک بصری در یک ثانیه را ببینید.
اما اگر من می خواهم برای قرار دادن در پایان، من برای شروع در آغاز،
گذشتن از تمام راه را به پایان، و سپس آن را رویه در.
به طوری که بدان معنی است که قرار دادن در انتهای لیست
تبدیل شدن به یک دوست O از N عملیات، رفتن به عقب
به بحث ما پیچیدگی محاسباتی.
آن را می خواهم تبدیل شدن به یک درجه از عملیات N، که در آن به عنوان لیست بزرگتر و بزرگتر،
و بزرگتر، آن را تر و سخت تر به رویه چیزی
در در پایان.
اما همیشه واقعا آسان برای رویه چیزی در در آغاز،
شما همیشه در ابتدای راه هستیم.
>> و ما یک بصری از این دوباره ببینید.
و سپس یک بار ما در حال انجام، یک بار ما در گره جدید قرار داده ام،
ما می خواهیم به بازگشت به اشاره گر ما رئیس جدید یک لیست پیوندی، که
از آنجایی که ما در حال قرار دادن در آغاز، در واقع می خواهد
یک اشاره گر به گره ما فقط ایجاد شده است.
بیایید این تجسم، چون فکر می کنم به شما کمک کند.
>> بنابراین در اینجا لیست ما است، آن را از شامل چهار عامل، گره شامل 15،
که اشاره به یک گره حاوی 9، که
اشاره به یک گره شامل 13، که اشاره به یک گره حاوی
10، که دارای تهی اشاره گر به عنوان اشاره گر خود را
به طوری که در پایان این فهرست است.
بنابراین ما می خواهیم به قرار دادن یک گره جدید با ارزش 12
در آغاز این لیست، چه کار کنیم؟
خب، اول ما از malloc فضا برای گره، و سپس ما در 12 وجود دارد قرار داده است.
>> بنابراین در حال حاضر ما به آن رسیده ام نقطه تصمیم گیری، درست است؟
ما یک زن و شوهر از اشاره گر که ما می توانیم
حرکت می کند، که یکی باید اول ما حرکت می کند؟
باید ما را به نقطه 12 رئیس جدید از list--
و یا ببخشید، باید ما را 12 اشاره به سر قدیمی از لیست؟
یا باید ما می گویند که لیست در حال حاضر در 12 آغاز می شود.
یک تمایز وجود دارد وجود دارد، و ما نگاه
در چه با هر دو را در یک ثانیه اتفاق می افتد.
>> اما این منجر به موضوع بزرگ برای نوار کناری،
که این است که یکی از مهم ترین چیز با لیست های پیوندی
شده است به ترتیب اشاره گر در جهت درست.
اگر شما حرکت می کند همه چیز از سفارش، شما می توانید تا پایان به طور تصادفی
یتیم بقیه از لیست.
و در اینجا یک مثال از آن است.
بنابراین اجازه دهید با این ایده به of-- خب، ما فقط 12 ایجاد کرده اید.
ما می دانیم که 12 است برای رفتن به رئیس جدید لیست،
و چرا ما نه تنها حرکت لیست اشاره گر به اشاره می کنند.
>> خوب، پس این خوب است.
بنابراین در حال حاضر که در آن می کند 12 نقطه بعدی؟
منظور من، بصری ما می توانید ببینید که آن را به 15 نقطه،
به عنوان انسان آن را واقعا به ما آشکار است.
چگونه کامپیوتر دانید؟
ما هیچ چیز را ندارد با اشاره به 15 دیگر، درست است؟
>> ما هر گونه توانایی برای اشاره به 15 از دست داده ام.
ما می توانیم بگوییم تیر جدید برابر بعدی چیزی، هیچ چیز وجود دارد.
در واقع، ما را یتیم بقیه لیست
با انجام این کار، ما به طور تصادفی شکسته زنجیره ای.
و ما قطعا نمی خواهید به انجام این کار.
>> بنابراین اجازه دهید بروید و سعی کنید دوباره.
شاید چیزی که حق انجام است به مجموعه ای اشاره گر 12
به سر های قدیمی از لیست اول، پس از آن ما می توانید لیستی بیش از حرکت می کند.
و در واقع، این است که جهت درست است که ما
باید به دنبال زمانی که ما کار با لیست تنهایی مرتبط.
ما همیشه می خواهیم برای اتصال عنصر جدید به لیست،
قبل از اینکه ما این نوع از گام مهم تغییر
که در آن سر از لیست پیوندی است.
باز هم، که چنین چیزی اساسی است، ما نمی خواهیم از دست دادن آهنگ از آن است.
>> بنابراین ما می خواهیم مطمئن شوید که همه چیز با هم زنجیر،
قبل از ما حرکت که اشاره گر.
و به این ترتیب این امر می تواند در جهت درست، است که برای اتصال 12 به لیست،
پس از آن می گویند که شروع می شود یک لیست 12.
اگر ما گفت: لیست شروع می شود در 12 و سپس سعی در اتصال 12 به لیست،
ما در حال حاضر دیده می شود چه اتفاقی می افتد.
ما به اشتباه از دست دادن لیست.
>> خوب، پس یک چیز بیشتر به بحث در مورد.
اگر ما می خواهیم به خلاص شدن از شر کل لیست پیوندی در یک بار؟
باز هم، ما mallocing تمام این فضا، و بنابراین ما
نیاز به آن را آزاد زمانی که ما انجام می شود.
بنابراین در حال حاضر ما می خواهیم به حذف کل لیست پیوندی.
خب، چه چیزی ما می خواهیم کاری انجام دهید؟
>> اگر ما اشاره گر تهی رسیدهاید، ما می خواهید برای جلوگیری، در غیر این صورت، فقط حذف
بقیه لیست و سپس به من آزاد.
حذف و از بقیه از لیست، و سپس آزاد گره فعلی.
چه که صدا مانند، چه تکنیک ما صحبت کردیم
در مورد قبلا که صدا مانند؟
حذف هر کس دیگری، پس از آن دوباره و من را حذف کنید.
>> که بازگشت، ما ساخته ایم مشکل کمی کوچکتر،
ما در حال گفت حذف همه دیگری، و سپس شما می توانید به من را حذف کنید.
و بیشتر پایین جاده، آن گره می گویند، حذف هر کس دیگری.
اما در نهایت ما را به دریافت نقطه که در آن لیست تهی است،
و مورد پایگاه ما است.
>> بنابراین اجازه دهید نگاهی به این و چگونه این ممکن است کار کند.
بنابراین در اینجا لیست ما است، آن را همان لیست ما فقط در مورد صحبت می کردند،
و مراحل وجود دارد.
در بسیاری از متن وجود دارد، ولی امیدوارم تجسم کمک خواهد کرد.
>> بنابراین ما have-- و من هم کشیده تا ما قاب پشته تصویر
از ویدیو های ما در پشته پاسخ، و امیدوارم همه از این
با هم به شما چه خبر است نشان می دهد.
بنابراین در اینجا کد شبه ما است.
اگر ما رسیدن به یک مقدار null اشاره گر، توقف، در غیر این صورت،
حذف و از بقیه از لیست، پس از آن آزاد گره فعلی.
بنابراین در حال حاضر، list-- اشاره گر است که ما
عبور در از بین بردن نقاط به 12.
12 یک اشاره گر تهی نیست، بنابراین ما در حال رفتن بقیه لیست را حذف کنید.
>> آنچه که حذف بقیه از ما دارد؟
خب، به این معنی ساخت یک پاسخ برای از بین بردن، گفت:
که 15 آغاز شده است بقیه از لیست ما می خواهیم به از بین ببرد.
و به این ترتیب پاسخ برای از بین بردن 12 نوع از در انتظار نگه داشته.
آن را منجمد وجود دارد، انتظار برای پاسخ برای از بین بردن 15، به پایان کار خود را.
>> خب، 15 یک اشاره گر تهی نیست، و پس از آن را می گویند، همه حق است،
خب، حذف و از بقیه از لیست.
بقیه فهرست شروع در 9، و بنابراین ما فقط
صبر کنید تا همه شما را حذف کنید که مواد، پس از عقب می آیند و حذف کنید.
خوب 9 را می گویند، خوب، من یک اشاره گر تهی نیست،
بنابراین از اینجا حذف و از بقیه این فهرست است.
و بنابراین سعی کنید و از بین بردن 13.
13 می گوید، من اشاره گر تهی نیست، همان چیزی که، از آن عبور جفتک انداختن.
10 اشاره گر تهی، 10 یک اشاره گر NULL،
اما 10 است نه یک null را در حال حاضر اشاره گر،
و پس از آن عبور می کند جفتک انداختن بیش از حد.
>> و در حال حاضر نقاط لیست وجود دارد، آن را واقعا اشاره به some--
اگر فضای بیشتری در تصویر بود، آن را به برخی از فضای تصادفی اشاره
که ما نمی دانیم که آنچه در آن است.
این اشاره گر تهی است هر چند، لیست به معنای واقعی کلمه در حال حاضر مجموعه آن ارزش های پوچ.
این اشاره که در داخل جعبه قرمز است.
ما یک اشاره گر تهی رسیده است، بنابراین ما می توانیم را متوقف کند، و ما در حال انجام است.
>> و به طوری که فریم بنفش است now-- در بالای stack-- که قاب فعال،
اما آن را انجام داده است.
اگر ما یک اشاره گر تهی رسیدهاید، متوقف شود.
ما هیچ چیز را نمی کنند، ما می توانید یک اشاره گر null آزاد نیست،
ما هیچ از malloc نیست فضا، و بنابراین ما در حال انجام است.
به طوری که عملکرد قاب از بین می رود، و ما
resume-- ما انتخاب کنید تا جایی که ما را ترک با بالاترین یک بعدی، که
این قاب به رنگ آبی تیره در اینجا است.
بنابراین ما انتخاب کنید تا جایی که ما را ترک کردن.
ما بقیه حذف لیست در حال حاضر، به طوری که در حال حاضر ما
رفتن به رایگان گره فعلی است.
بنابراین در حال حاضر ما می توانیم این گره آزاد، و در حال حاضر ما در پایان از عملکرد رسیدهاید.
و به طوری که قاب تابع از بین می رود، و ما انتخاب کنید تا در یک نور آبی.
>> پس از آن says-- من در حال حاضر done-- حذف بقیه لیست، بنابراین
آزاد گره فعلی.
و در حال حاضر قاب زرد است تماس در بالای پشته.
و بنابراین به عنوان شما می بینید، ما در حال حاضر از بین بردن لیست از راست به چپ.
>> چه اتفاقی می افتاد، هر چند، اگر ما همه چیز را به راه اشتباه انجام داده بود؟
درست مثل زمانی که ما سعی برای اضافه کردن یک عنصر است.
اگر ما را خراب کرد زنجیره ای، اگر ما اتصال اشاره گر نیست
در جهت درست، اگر ما فقط آزاد عنصر اول،
اگر ما فقط آزاد کرد سر از لیست، در حال حاضر ما
هیچ راهی برای اشاره به بقیه از لیست.
و بنابراین ما باید همه چیز یتیم،
ما را به حال چه به نام نشت حافظه.
اگر شما از فیلم ما به یاد در تخصیص حافظه پویا،
که چیز بسیار خوبی است.
>> همانطور که گفتم، وجود دارد چندین عملیات
که ما نیاز به استفاده از به کار با لیست پیوندی به طور موثر.
و شما ممکن است متوجه من حذف یکی، حذف یک عنصر از یک مرتبط
لیست.
دلیل من که است آن را در واقع نوعی از
روی حیله و تزویر در مورد چگونگی حذف فکر می کنم یک عنصر از یک تنهایی
لیست پیوندی.
ما باید قادر به جست و خیز بیش از چیزی در لیست، که
معنی است که ما به ما point-- گرفتن می خواهید این node-- را حذف کنید
اما به منظور آن را به طوری که ما انجام هر گونه اطلاعات از دست دادن نیست،
ما نیاز به اتصال این گره در اینجا، در اینجا.
>> بنابراین من احتمالا اشتباه از دیدگاه بصری.
بنابراین ما در آغاز هستید ما لیست، ما در حال اقدام از طریق،
ما می خواهیم این گره را حذف کنید.
اگر ما فقط آن را حذف کنید، ما در زنجیره شکسته ام.
این گره در اینجا اشاره به هر چیز دیگری،
آن شامل زنجیره ای از اینجا در خارج.
>> بنابراین آنچه که ما نیاز به انجام در واقع بعد از ما به این نقطه،
است که ما نیاز به قدم به عقب یک، و اتصال این گره را به این گره،
بنابراین ما پس از آن می توانید حذف کنید یکی در وسط.
اما فهرست تنهایی مرتبط نیست به ما ارائه یک راه برای رفتن به عقب.
بنابراین ما نیاز به هم نگه دو اشاره گر، و حرکت آنها
مرتب کردن بر اساس گام، یکی در پشت دیگر ما به عنوان، و یا رسیدن به یک نقطه
و سپس از طریق ارسال اشاره گر است.
و به عنوان شما می توانید، آن را ببینید می توانید کثیف کمی دریافت کنید.
خوشبختانه ما یکی دیگر از راه برای حل و فصل آن،
هنگامی که ما در مورد لیست مضاعف مرتبط صحبت کنید.
>> من داگ لوید هستم، این CS50.