مسیرها
/
Tcl
Tcl
/
تمرین‌ها
/
لیست پیوندی
لیست پیوندی

لیست پیوندی

متوسط

مقدمه

شما روی پروژه‌ای کار می‌کنید که هدفش توسعه‌ی یک سامانه‌ی زمان‌بندی قطار برای شبکه‌ی راه‌آهنی پرتردد است.

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

دستورالعمل‌ها

تیم شما تصمیم گرفته است برای نمایش هر مسیر قطار در برنامه‌ی زمانی، از یک «لیست پیوندی دوطرفه» استفاده کند. هر ایستگاه در مسیر قطار با یک گره در لیست پیوندی نمایش داده می‌شود.

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

می‌توان مسیرها را گسترش داد و به ابتدا یا انتهای یک مسیر ایستگاه افزود. همچنین می‌توان با حذف ایستگاه‌ها از ابتدا یا انتهای یک مسیر، آن را کوتاه کرد.

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

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

Note

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

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

نکات پیاده‌سازی

شما یک پیاده‌سازی از لیست پیوندی دوطرفه خواهید نوشت.

یک Node پیاده‌سازی کنید که یک مقدار و اشاره‌گرهایی به گره‌های بعدی و قبلی را نگه می‌دارد.

سپس یک LinkedList پیاده‌سازی کنید که ارجاع‌هایی به اولین و آخرین گره نگه می‌دارد و رابطی شبیه به آرایه برای افزودن و برداشتن عنصرها ارائه می‌دهد:

  • push (درج مقدار در انتها)؛
  • pop (حذف مقدار از انتها)؛
  • shift (حذف مقدار از ابتدا)؛
  • unshift (درج مقدار در ابتدا)؛
  • delete (حذف اولین گره‌ی منطبق)

برای اینکه پیاده‌سازی شما ساده بماند، تست‌ها شرایط خطا را پوشش نمی‌دهند. به‌طور خاص: pop یا shift هرگز روی یک لیست خالی فراخوانی نمی‌شوند.


منبع

موضوعی کلاسیک در علوم کامپیوتر
ویرایش از طریق GitHub این لینک در پنجره یا زبانه‌ی جدیدی باز می‌شود
Tcl Exercism

آماده‌اید لیست پیوندی را شروع کنید؟

در Exercism ثبت‌نام کنید تا Tcl را همراه با 135 تمرین و مربی‌گری انسانی واقعی یاد بگیرید و در آن استاد شوید، همه‌ی این‌ها رایگان.