[Powered by Google Translate] در برنامه نویسی، ما اغلب نیاز به نشان دادن لیستی از ارزش ها، مانند نام دانش آموزان در بخش یا نمرات خود را در آخرین مسابقه. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

عبور است خیلی بد نیست، اما آنچه در مورد قرار دادن؟ بیایید می گویند ما می خواهیم برای قرار دادن یک عدد صحیح به سمت 4 در یک لیست صحیح است. که بین گره های 3 و 4. باز هم، ما باید به گذشتن از این لیست فقط به رسیدن به عنصر 3، یکی از ما پس از قرار دادن. بنابراین، یک اشاره گر خزنده ما دوباره این لیست را به گذشتن از، اگر اشاره گر سر ما تهی است، و اگر این طور نیست، نقطه اشاره گر خزنده ما در گره سر. بنابراین، ما در عنصر 1 هستید. ما باید برای رفتن به جلو 2 بیشتر عناصر قبل از ما می توانید وارد، بنابراین ما می توانیم یک حلقه for استفاده کنید اعضای هیات من = 1؛ <3، من + + و در هر تکرار از حلقه، پیشبرد اشاره گر خزنده ما رو به جلو با 1 گره با چک کردن اگر میدان گره فعلی تهی است، و اگر این طور نیست، حرکت خزنده اشاره گر به گره بعدی تنظیم آن را به اشاره گر گره برابر است. بنابراین، از آنجا که حلقه برای ما می گوید: برای انجام این کار دو بار، ما رسیده گره 3، و یک بار اشاره گر خزنده ما رسیده است گره پس از که ما می خواهیم برای وارد کردن عدد صحیح جدید ما، چگونه ما در واقع قرار دادن؟ 

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

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

بنابراین، به این ساده، اجازه دهید بگویم که ما 4 گره A، B، C، و D نامیده می شود، با فلش به نمایندگی از زنجیره ای از اشاره گرها که اتصال گره ها. بنابراین، ما باید به درج گره جدید ما در بین گره های C و D. این مهم به آن را در جهت درست انجام دهد، و من به شما نشان می دهد که چرا. 

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

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

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

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

نام من ... است Steinkamp جکسون، این CS50 است.