بایگانی برچسب‌ها : اشاره گر

لیست پیوندی Linked List

لیست پیوندی یا Linked List چیست؟

لیست پیوندی (Linked List) مجموعه‌ای از عناصر داده‌ای است که در آن هر عنصر به عنصر بعدی خود اشاره می‌کند. این عناصر که در کنار یکدیگر تشکیل یک دنباله می‌دهند گره (Node) نامیده می‌شوند و در ساده‌ترین فرم (لیست یک طرفه)، هرکدام شامل یک فیلد داده و یک فیلد اشاره‌گر (ارجاع یا لینک) به گره بعدی خود می‌باشند. این اشاره‌گر با عناوینی چون Next Pointer یا Next Link نیز شناخته می‌شود.

از این ساختمان داده برای پیاده‌سازی لیست، پشته، صف، آرایه انجمنی و … استفاده می‌شود. معمولا برای دسترسی به یک لیست پیوندی از اشاره‌گری به اولین گره لیست استفاده می‌شود که به آن head (یا front) گفته می‌شود. در لیست‌های پیوندی ساده، معمولا اشاره‌گر گره آخر برابر با null (تهی) خواهد بود. در برخی موارد برای تسهیل افزودن گره به انتهای لیست، اشاره‌گری به نام tail درنظر گرفته می‌شود که به آخرین گره لیست اشاره می‌کند.

لیست پیوندی یک طرفه singly linked list
نمونه‌ای از یک لیست پیوندی یک طرفه با سه گره (نود) – در این لیست پیوندی هر گره دارای دو فیلد (یک فیلد برای نگه‌داری داده و دیگری اشاره‌گر به گره بعدی) می‌باشد.

اعمال رایج لیست‌های پیوندی

اعمال رایجی که روی لیست‌های پیوندی انجام می‌شود عبارتست از: حذف نود از ابتدا و انتهای لیست، حذف نود پس از یک نود مشخص، پیمایش لیست (به منظور خواندن یا انجام عملی دیگر با استفاده از داده گره‌ها)، افزودن نود به ابتدا و انتهای لیست، افزودن نود پس از یک نود مشخص و یافتن نود با داده‌ای معین.

برای نمونه فرض کنید می‌خواهیم در لیست پیوندی یک طرفه شکل زیر، گره جدیدی با داده B پس از گره اول درج کنیم.

لیست پیوندی
در این لیست پیوندی می‌خواهیم گره جدیدی را پس از گره اول درج کنیم.

در صورتی که خصوصیات گره اول را داشته باشیم این کار به آسانی تنها با دو عمل انجام می‌شود. به این ترتیب که ابتدا اشاره‌گر گره جدید به گره بعدی گره A اشاره می‌کند و سپس اشاره‌گر گره A به گره جدید اشاره می‌کند.

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

شبه کد زیر نحوه انجام این کار را به زبان ساده بیان می‌کند. nodeA گرهی است که می‌خواهیم nodeB را پس از آن درج کنیم و next متغیر اشاره‌گر گره است:

function insertAfter(Node nodeA, Node nodeB)
     nodeB.next := nodeA.next
     nodeA.next := nodeB

انواع لیست‌های پیوندی

برای افزایش کارایی لیست‌های پیوندی یک طرفه (Singly Linked List)، گونه‌های مختلفی بر اساس همین ساختار شکل گرفته‌اند که از رایج‌ترین آن‌ها می‌توان به لیست پیوندی دو طرفه (Doubly Linked List) و لیست پیوندی دایره‌ای یا حلقوی (Circular Linked List) اشاره نمود.

در لیست پیوندی دو طرفه، هر نود علاوه بر یک اشاره‌گر به نود بعدی (Next) دارای یک اشاره‌گر به نود قبلی (Prev) نیز می‌باشد. به این ترتیب امکان پیمایش لیست در هر دو سمت فراهم می‌شود. در لیست‌های حلقوی، گره آخر به جای آنکه دارای ارجاع null باشد به گره ابتدایی (یا head) اشاره می‌کند. نوع دیگری که از ترکیب این دو مدل به دست می‌آید لیست پیوندی دوطرفه حلقوی نامیده می‌شود.

لیست پیوندی دو طرفه doubly linked list
نمونه‌ای از یک لیست پیوندی دو طرفه با سه گره – در این شکل هر گره دارای سه فیلد (یک فیلد برای نگه‌داری داده، یک فیلد برای اشاره‌گر به گره بعدی و یک فیلد برای اشاره‌گر به گره قبلی) می‌باشد.

مزایا و معایب لیست‌های پیوندی

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

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

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

پیوندهای پیشنهادی تک دیک

لینک واژه در ویکیپدیا

تاچ پد Touchpad

تاچ پد یا Touchpad چیست؟

تاچ پد (Touchpad) نوعی ابزار اشاره‌گر است که مجهز به یک حسگر (یا سطح) لمسی می‌باشد. حرکت و مکان انگشتان کاربر روی این سطح به مکانی نسبی تبدیل می‌شود که به نحوی مشابه با یک ماوس برای تعامل با دستگاه مورد استفاده قرار می‌گیرد. ترک پد (یا Trackpad) نیز نام دیگری است که گهگاه به عنوان جایگزینی برای Touchpad به کار می‌رود.

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

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

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

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

کاربرد تاچ پد در لپ تاپ‌ها تقریبا از دهه نود میلادی رواج یافت. البته امروزه استفاده از این دستگاه‌های اشاره‌گر به عنوان یک ابزار جانبی در رایانه‌های رومیزی نیز با رواج کمتری قابل مشاهده است. امکان چرخش، بزرگ‌نمایی (Zoom in) و کوچک‌نمایی (Zoom out) تصاویر از دیگر قابلیت‌هایی است که به مدد درایور برخی از ترک پدها و همچنین نرم افزار مورد استفاده می‌تواند کاربردی کاملا مفید و ویژه برای کاربر داشته باشد.

تاچ پد Touchpad
نمونه‌ای از یک تاچ پد در بخش پایینی صفحه کلید یک لپ تاپ

پیوندهای پیشنهادی تک دیک

لینک واژه در ویکیپدیا