ساختمان داده در سی شارپ

ساختمان داده ها در C#:<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

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

قسمت اول : مقدمه ای بر ساختمان داده

مطالب مورد بحث در این قسمت بشرح زیر می باشند :

- مقدمه

- آنالیز کارآیی یک ساختمان داده

- ساختمان داده خطی، همگون و بسیار متداول : آرایه (Array)

- ایجاد ساختمان داده های کارآ، قابل استفاده مجدد و Type-Safe

- لیست (List) : ساختمان داده ای همگون

- نتیجه و جمه بندی

مقدمه

در طول این مطلب، با چندین ساختمان داده موجود در .Net Framework Base Class و همچنین ساختمان داده هایی که توسط کاربر ایجاد می شوند، آشنا خواهید شد. اگر با مفهوم ساختمان داده آشنایی ندارید به تعریف زیر توجه نمایید :

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

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

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

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

در قسمت دوم ، به بررسی صف (Queue) و پشته (Stack) خواهیم پرداخت. همانند لیست ها، صف و پشته نیز مجموعه ای از داده ها هستند و این دو ساختمان داده در .Net Framework Base Class Library وجود دارند. بر خلاف لیست، که اعضای آن به هر ترتیبی قابل دسترسی هستند، دسترسی به اعضای صف و پشته تنها از طریق ترتیبی خاص قابل دسترسی است. سپس به بررسی چند برنامه و طریقه پیاده سازی صف و پشته خواهیم پرداخت و پس از آن Hashtable ها را مورد بررسی قرار می دهیم. Hashtable ها امکان دسترسی به عناصر را بصورت مستقیم فراهم می نمایند (همانند آرایه یا ArrayList ها) ولی اندیس مورد استفاده در آن کلیدهایی رشته ای هستند. (String Keys)

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

اگرچه استفاده از درخت جستجوی دودویی باعث کاهش زمان جستجو می شود، اما دارای نواقص و کاستی هایی نیز می باشد. در قسمت چهارم، به بررسی SkipList ها می پردازیم که ترکیبی از درختهای دودویی و لیست های پیوندی (Linked List) است.

در قسمت پنجم، به بررسی ساختمان داده هایی پرداخته می شوند که می توانند نشان دهنده گراف (Graph) باشند. یک گراف مجموعه ای از گره ها (Nodes) است که هر یک از آنها با لبه هایی (Edge) به گره های دیگر متصل شده اند. برای مثال، نقشه شهرها را میتوان با یک گراف پیاده سازی کرد که در آن شهرها همان گره ها و راه ها و اتوبانهای بین شهرها نشان دهنده Egde ها می باشند. بسیاری از مسایل دنیای واقعی با استفاده از مفهوم گرافها بطور انتزاعی قابل پیاده سازی هستند.

نهایتاً در قسمت ششم، به بررسی ساختمان داده هایی می پردازیم که نشان دهنده Sets و Disjoined Sets هستند. Set ، مجموعه ای است از داده ها که بدون هیچ گونه ترتیبی در کنار یکدیگر قرار گرفته اند. Disjoined Set ، مجموعه ای از Set هاست که هیچ عنصر مشترکی با یکدیگر ندارند. این دو مفهوم در پیاده سازی برنامه های امروزه کارآیی زیادی دارند و در قسمت ششم به بررسی و نحوه استفاده از آنها خواهیم پرداخت.

آنالیز کارآیی ساختمان های داده

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

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

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

public bool DoesExtensionExist(string [] filenames , string extension)

{

int i = 0;

for (i = 0; i < fileNames.Length; i++)

if (String.Compare(Path.GetExtension(fileNames[i]), extension, true) == 0)

return true;

return false; // If we reach here, we didn't find the extension

}

به نگاهی دقیق تر به این برنامه، متوجه می شوید که در بدترین حالت، یعنی زمانیکه فایل مورد نظر در آرایه وجود نداشته باشد و یا وجود داشته باشد اما در آخرین خانه آرایه جای داشته باشد، باید تمامی عناصر آرایه را یکبار مورد بررسی و جستجو قرار دهیم. برای آنالیز مسائل، بطور مثال برای آنالیز مرتب سازی عناصر آرایه (Sort)، به شکل زیر باید فکر کنیم : " فرص می کنم آرایه ای با n عنصر دارم، اگر عنصر دیگری به این آرایه اضافه کنم n+1<span l

ساختمان داده در سی شارپ

مطالب مشابه :

ساختمان داده در سی شارپ

ساختمان داده ها

اینم جزوه ساختمان داده ها

ساختمان داده ها صف اولویت دار

ساختمان داده‌ها

برنامه آموزش درس ساختمان داده ها (صلواتی) - رشته کامپیوتر - نرم افزار آموزش ساختمان داده