Admin
6th July 2009, 06:35 PM
ساختمان داده ها در C# (با رویکردی بر C# 2.0 )
این مطلب، آغاز یک سری شش قسمتی از مطالب مهم و کلیدی درباره ساختمان داده و کاربر آن در توسعه و طراحی نرم افزار است. در قسمت اول، مختصری درباره ساختمان داده ها، تعریف ساختمان داده، آنالیز کارآیی یک ساختمان داده و بررسی اهمیت این آنالیز صحبت خواهیم نمود. در این بخش همچنین درباره دو ساختمان داده بسیار مهم و رایج در .Net Framework یعنی آرایه ها و لیست ها صحبت خواهیم کرد.
توجه : مطالب موجود در این 6 قسمت، منطبق بر ساختار .Net Framework 2.0 و C# 2.0 تنظیم شده اند.
پیشنیاز این مطالب، آشنایی با زبان برنامه سازی C# است
قسمت اول : مقدمه ای بر ساختمان داده
مطالب مورد بحث در این قسمت بشرح زیر می باشند :
- مقدمه
- آنالیز کارآیی یک ساختمان داده
- ساختمان داده خطی، همگون و بسیار متداول : آرایه (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 Doe***tensionExist(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 عنصر خواهم داشت، در این حالت زمان اجرای برنامه من چقدر خواهد شد؟ " . توجه نمایید که کلمه "زمان اجرا " یا Running Time عملا به معنا محاسبه دقیق زمان اجرا برنامه نیست، بلکه محاسبه تعداد مراحل و زمان اجرای این مراحل برای یک عمل خواسته شده است. برای مثال در مورد آرایه، تعداد مراحل به تعداد دفعات دسترسی به عناصر آرایه است. برای جستجو درون یک آرایه، در صورتیکه n+1 عنصر در آرایه داشته باشیم، باید n+1 بار مقدار مورد نظر خود را با عناصر آرایه مقایسه نماییم. از اینرو می گوئیم مدت زمان جستجو درون یک آرایه بطور خطی با تعداد عناصر موجود در آرایه رابطه مستقیم دارد.
این روش آنالیز که در اینجا مطرح گردید، به روش آنالیز آسیمپوتیک (Asymptotic Analyze) معروف است. روش علامتگذاری که در این روش آنالیز مورد استفاده قرار می گیرد، به روش نشانه گذاری O (Big-Oh Notation) معروف است. برای نشان دادن کارآیی جستجو در آرایه غیر مرتب با استفاده از این روش نشانه گذاری، بشکل زیر عمل می شود O(n) که نشان دهنده رابطه زمان با تعداد اعضا است. بدین ترتیب با استفاده از O(n) برای نشان دادن کارآیی یک ساختمان داده، این مفهوم بدست می آید که رابطه ای خطی و مستقیم بین افزایش تعداد اعضای از n به n+1 و زمان انجام عملیات وجود دارد. بدین ترتیب علامت O نشان دهنده روش نشانه گذاری و روش آنالیز کارآیی است و n نشان دهنده چگونگی افزایش مراحل پردازش عمل بسته به تعداد عناصری است که می خواهند مورد پردازش قرار گیرند.
برای محاسبه زمان اجرای یک قطعه کد با استفاده از O-Notation یا همان Asymptotic Analyze می توان از چند مرحله ساده زیر استفاده نمود :
1- بدست آوردن مراحلی که زمان اجرای یک الگوریتم را شکل می دهند. همانطور که قبلاً ذکر شد، این مراحل برای یک آرایه، خواندن و نوشتن یا همان دسترسی به عناصر آرایه است و این مراحل برای ساختمان های داده ای دیگر متفاوت خواهد بود. باید توجه داشته باشید که برای آنالیز کارآیی یک ساختمان داده، تنها به مراحلی که توسط خود ساختمان داده ی مورد نظر انجام می شود توجه می گردد و عملیات ساده ای که توسط کامپیوتر انجام می شوند را در این محاسبه به حساب نمی آوریم. برای مثال در کد بالا، برای محاسبه کارآیی تنها به تعداد دفعات لازم برای دسترسی به عناصر آرایه توجه کرده و به زمان های لازم جهت ایجاد متغیرها و با زمان محاسبه تساوی دو رشته اهمیت نداده ایم.
2- خطهایی از برنامه که در الگوریتم شما تاثیر دارند و می خواهید کارآیی را برای آنها محاسبه کنید را پیدا کرده و در کنار آنها عدد 1 قرار دهید.
3- اگر این خطوط که آنها را با عدد 1 مشخص کرده اید خود یک حلقه تکرار هستند، بجای عدد 1 در کنار آنها عدد معادل بیشترین تعداد تکرار حلقه را قرار دهید. اگر در جایی حلقه تو در تو دارید، باید از ضرب بیشترین تعداد دفعات تکرار حلقه ها استفاده کنید.
4- بزگترین عدد نوشته شده را پیدا کنید. این عدد زمان اجراست.
حال برای روشتن تر شدن موضوع همین مراحل را برای کد نوشته شده در بالا اجرا میکنیم. در کد نوشته شده در بالا، مراحل مورد نظر برای ما، تعداد دفعات دسترسی به عناصر آرایه است. با توجه به کد و با توجه به مرحله 2، تنها در یک خط کد، دسترسی به عناصر آرایه وجود دارد، پس عدد 1 را در کنار این خط قرار می دهیم. با توجه به مرحله 3، این خط در یک حلقه تکرار قرار دارد و این حلقه n با تکرار می شود که n تعداد عناصر آرایه است. طبق مرحله 3، عدد 1 را پاک کرده و بجای آن n در کنار این خط قرار می دهیم. N بزرگترین مقدار نوشته شده است از اینرو زمان اجرا O(n) است.
O(n) یکی از صدها زمان اجرای موجود در آنالیز Asymptotic است. برخی دیگر از زمانهای اجرا عبارتند از O(log2 n), O(n log2 n), O(n2), O(2n) و .... بدون اینکه وارد جزئیات پیچیدگیهای ریاضیاتی Notation_O شویم، بیان میداریم که هرچه مقدار داخل پرانتز در این آنالیز کوچکتر باشد، عملیات بر روی ساختمان داده کارآمدتر است. برای مثال ساختمان داده ای که زمان اجرای آن O(log n) است به مراتب کارآمدتر از ساختمان داده ایست که زمان اجرای آن O(n) است. چراکه log n < n
نکته : برای یادآوری باید بگویم که loga b = y روش دیگری برای نمایش ay = b است. از اینرو log2 n رشد کندتری نسبت به n دارد، چراکه اگر n=8 فرض کنیم، log2 n = 3 می شود در حالیکه n=8 است. در قسمت سوم از این سری مطالب، با درخت های جستجوی دودویی آشنا می شویم که زمان اجرایی آنها O(log2 n) است.
زمان اجرای Asymptotic و الگوریتمهای دنیای واقعی
زمان اجرای Asymptotic روشی برای محاسبه کارآیی الگوریتم در زمانی است که تعداد عناصر مورد نظر آن به سمت بینهایت میل می کند. هنگامیکه گفته می شود زمان اجرایی یک الگوریتم از الگوریتم دیگر بیشتر است، از لحاظ ریاضی بدین معناست که مراحل اجرایی و زمان اجرایی این مراحل در الگوریتم زمان بر بیشتر از الگوریتمی است که زمان اجرایی کمتری دارد. اما باید توجه کرد که در مواردی، الگوریتم هایی با مراحل اجرایی کم ، با اینکه دارای زمان اجرایی بالایی هستند، از الگوریتمهایی که زمان اجرایی پائین تری دارند، سریعتر اجرا می شودند. همانطور که گفته شد این امر معمولا در مواردی صادق است که الگوریتمی که زمان اجرایی آن بالاست، دارای مراحل بسیار کمی باشد.
بعنوان مثال، الگوریتمهای بسیار زیاد و متفاوتی برای مرتب سازی آرایه ها وجود دارد و هر یک از آنها دارای زمان اجرایی متفاوتی هستند. یکی از ساده ترین و بدیهی ترین الگوریتمهای مرتب سازی (Sort) الگوریتم مرتب سازی حبابی یا Bubble Sort است. زمان اجرایی این الگوریتم O(n2) است که این مقدار خاطر وجود دو حلقه تودرتو در این الگوریتم بوجود آمده است. در مقابل الگوریتم دیگری به نام Merge Sort وجود دارد که زمان اجرایی آن O(n log2 n) است. زمان اجرایی Merge Sort به مراتب کمتر از زمان اجرایی Bubble Sort است. اما برای آرایه هایی با تعداد عناصر کم، زمان اجرایی Bubble Sort کمتر از زمان اجرای Merge Sort است ! از آنجائیکه Merge Sort از یک ساختار بازگشتی استفاده میکند و نیز نیم آرایه Sort شده را در انتها با یکدیگر ادغام می نماید، در مورد آرایه های کوچک کارآیی چندانی ندارد و چون Bubble Sort تنها از جابجا کردن عناصر مجاور آرایه استفاده می کند، از اینرو برای آرایه ها کوچک الگوریتمی مناسب تر است. (لطفاً در صورتیکه در مورد الگوریتمهای Sort سوال و یا مشکلی دارید حتما به من ایمیل بزنید) نهایتاً، مراحل کاری Merge Sort از Bubble Sort کمتر است اما از آنجائیکه وزن این مراحل بالاست (هر مرحله احتیاج به زمان پردازشی بالایی دارد) از اینرو برای آرایه هایی عظیم مفید است. حال آنکه برای آرایه هایی با حجم کم الگوریتم Bubble Sort مناسب تر است. پس علاوه بر توجه به زمان اجرایی یک الگوریتم، توجه به موارد استفاده و حجم داده مورد نظر نیز موثر است.
آرایه : ساختمان داده ای خطی، همگون، با امکان دسترسی مستقیم
آرایه ها یکی از ساده ترین و پر استفاده ترین ساختمانهای داده هستند که در تمامی زبانهای برنامه سازی دارای ویژگیهای مشترکی هستند :
· محتویات آرایه در یک فضای حافظه پیوسته ذخیره می شود
· تمامی عناصر یک آرایه باید از یک نوع یا از یک نوع مشتق شده باشند. از اینرو به آرایه ، ساختمان داده ای همگون گفته میشود.
· دسترسی به عناصر آرایه بصورت مستقیم و از طریق اندیس است.
عملیات متدوالی که بر روی آرایه ها انجام میشود نیز بشرخ زیر است :
· تخصیص
· دسترسی
در زبان C# هنگامیکی آرایه ای ایجاد میشود، مقدار پیش فرض تهی (Null) برای آن در نظر گرفته میشود. برای مثال خط زیر آرایه تهی BoolArray را ایجاد میکند :
bool[] BoolArray;
قبل از اینکه بتوانیم از آرایه ها استفاده کنیم، می بایست نمونه ای از آن را ایجاد نماییم تا بتوانیم عناصر مورد نظر را در آن ذخیره کنیم :
arrayName = new arrayType[allocationSize];
این خط از کد، باعث تخصیص فضای پیوسته ای از حافظه در CLR-Managed Heap به اندازه تعداد allocationSize از arrayType میشود. (برای مثال اگر فضای مورد نیاز برای ذخیره سازی متغیری از نوع int برابر 2 بایت باشد، برای آرایه ای که allocationSize آن 5 است، به 10 بایت حافظه نیاز است.) اگر arrayType از انواع مقداری (Value Type) باشد، آنگاه مقادیری از نوع arrayType و به تعداد allocationSize ایجاد میشود. (این مقادیر ایجاد شده unboxed هستند.) در صورتیکه arrayType از انواع مرجعی (Reference Type) باشند، آنگاه مرجع هایی از نوع arrayType و به تعداد allocationSize ایجاد میگردند. (در صورتیکه تفاوت بین انواع مرجعی و مقداری و فرق بین پشته و heap را نمیدانید، به درک انواع رایج در .Net مراجعه نمایید.)
برای درک چگونگی نگهداری عناصر آرایه توسط .Net Framework ، به مثال زیر توجه نمایید :
bool [] booleanArray;
FileInfo [] files;
booleanArray = new bool[10];
files = new FileInfo[10];
در اینجا، آرایه booleanArray از نوع System.Boolean است در حالیکه آرایه files از نوع مرجعی System.IO.FileInfo میباشد. شکل زیر وضعیت CLR-Managed Heap را پس از اجرای این چند کد به نمایش در می آورد :
لینك تصویر (http://csharp-persian.netfirms.com/images/Data_Structure/datastructures-fig01big.JPG)
باید به این نکته نیز توجه نمایید که 10 عنصر موجود در آرایه Files، مرجع هایی به نمونه هایی از FileInfo هستند.
لینك تصویر (http://csharp-persian.netfirms.com/images/Data_Structure/datastructures-fig02big.JPG)
در .Net تمامی عناصر آرایه امکان نوشته شدن و نوشتن بر آرایه را دارند. نحوه دسترسی به عناصر آرایه به فرم زیر است :
// Read an array element
bool b = booleanArray[7];
// Write to an array element
booleanArray[0] = false;
زمان اجرایی دسترسی به یک آرایه را بصورت O(1) نشان می دهیم، زیرا زمانی ثابت است. این به معنی آنست که، هر چقدر هم که عناصر آرایه زیاد باشند، زمان دسترسی به یک عنصر یکسان و ثابت است. علت ثابت بودن این زمان آنست که، عناصر آرایه بصورت متوالی در خانه های حافظه قرار می گیرند و به هنگام دسترسی به یک عنصر تنها کافی است تا نقطه شروع آرایه، طول عناصر آرایه و اندیس عنصر مورد نظر را داشته باشیم. در این حالت دسترسی به هر یک از عناصر آرایه زمانی واحد و ثابت را نیاز دارد.
نکته قابل توجه دیگر آنست که، در کدهای مدیریت شده، زمان دسترسی به عناصر آرایه اندکی با آنچه گفته شد متفاوت است. برای مثال در .Net ، با هر درخواست برای دسترسی به عنصر یک آرایه، CLR اندیس مورد نظر را نیز چک میکند تا این اندیس درون آرایه قرار داشته باشد. درصورتیکه اندیس موزد نظر خارج از آرایه باشد، استثنای IndexOutOfRangeException ایجاد میشود. (برای مثال اگر آرایه ای با 10 عنصر داشته باشیم و اندیس دسترسی به عنصر آرایه را 15 در نظر بگیریم، این استثناء رخ خواهد داد، چراکه اندیس مورد نظر خارج از مرزهای (Bound) آرایه است.) این کنترل باعث می شود تا به هنگام استفاده از آرایه ها مطمئن باشیم که به اشتباه وارد قسمت دیگری از حافظه نشده ایم. (برای مثال در برخی از نسخه های کامپایلر C این کنترل صورت نمی گیرد و شما می توانید به عنصر یازدهم یک آرایه ده عنصری دسترسی پیدا کنید !!! در این حالت اتفاقی که رخ می دهد آنست که، کامپایلر به اشتباه محتویات خانه ای از حافظه را به شما نشان میدهد که اصلا جزو آرایه مورد نظر نیست. این امر باعث بروز اشکالات فراوانی برای برنامه نویس به هنگام تست برنامه میشود. چراکه محتویات خانه ای از حافظه که به اشنباه اندیس دهی شده است، ممکن است تاثیرات نامطلوب و غیر قابل پیش بینی بر روی نتیجه برنامه داشته باشد و بررسی و کنترل منبع این خطا بسیار دشوار است.) توجه نمایید که انجام این کنترل باعث تغییر زمان اجرایی دسترسی به عناصر آرایه (O(1)) نمیشود چراکه با افزایش تعدا عناصر آرایه این زمان تغییر نمیکند.
نکته : انجام چنین کنترلی بر روی اندیس دسترسی به عناصر آرایه، باعث افزایش کارآیی در برنامه هایی میشود که بطور عظیمی با آرایه ها و دسترسی به عناصر آنها سروکار دارند. در کدهای مدیریت نشده (Unmanaged Code) امکان غیر فعال کردن این کنترل بر روی اندیس آرایه وجود دارد. برای مطالعه بیشتر در این زمینه میتوانید به فصل چهاردهم از کتاب "Applied Microsoft .Net Framework Programming" نوشته Jeffrey Richter مراجعه نمایید.
بهنگام کار با آرایه ها ممکن است نیاز به افزایش تعداد عناصر آرایه داشته باشیم. برای انجام چنین کاری لازم است تا نمونه جدیدی از آرایه مورد نظر را با طول جدید ایجاد کرده و عناصر آرایه فعلی را در آرایه جدید کپی نمایید. نمونه ای از کد مورد نظر برای اجرای چنین عملی در زیر آمده است :
// Create an integer array with three elements
int [] fib = new int[3];
fib[0] = 1;
fib[1] = 1;
fib[2] = 2;
// Redimension message to a 10 element array
int [] temp = new int[10];
// Copy the fib array to temp
fib.CopyTo(temp, 0);
// Assign temp to fib
fib = temp;
پس از اجرای آخرین خط در کد بالا، آریه fib به یک آریه ده عنصری اشاره میکند. عناصر 3 تا 9 این آرایه جدید مقدار پیش فرض Int32 یعنی صفر را دارا خواهند بود.
آرایه ها یکی از بهترین ساختمان های داده برای نگهداری مجموعه ای از داده های همگون است که باید بطور مستقیم مورد دسترسی قرار گیرند. جستجو درون یک آرایه نا مرتب، زمان اجرای خطی دارد. توجه نمایید، در صورتیکه آرایه ای مرتب شده را مورد جستجو قرار دهیم، زمان اجرای جستجو به O(log n) تغییر پیدا خواهد کرد که زمانی نزدیک به زمان اجرایی درخت جستجوی دودویی است. توجه نمایید که در .Net ، کلاس Array دارای متد BinarySearch() است که با استفاده از آن میتوان به جستجوی باینری درون آرایه مرتب شده پرداخت.
نکته : همانطور که میدانید .Net Framework از آرایه های چند بعدی نیز پستیبانی مینماید. از آنجائیکه زمان اجرای جستجو درون آرایه تک بعدی برابر با O(n) است، زمان اجرای جستجو در یک آرایه k بعدی برابر با O(nk) خواهد بود. توجه کنید که در اینجا n تعداد عناصر آرایه در هر بعد است و منظور از n تعداد کل عناصر موجود در آرایه نیست.
ساخت ساختمان داده ای مطمئن، کارآ و قابل استفاده مجدد
هنگامیکه میخواهیم ساختمان داده ای را برای مسئله ای خاص ایجاد نمائیم، ویژگیهای داخلی ساختمان داده در اغلب موارد، امکان شخصی سازی برای منطبق شدن با مسئله ما را فراهم مینماید. برای مثال فرض کنید میخواهید برنامه ای برای محاسبه حقوق کارکنان خود ایجاد نمایید. در این برنامه یکی از ساختمان داده های مورد نیاز میتواند آرایه Employee باشد. در عین حال شما نمی خواهید برای ورود هر کارمند جدید به شرکت، طول آرایه را تغییر دهید. از اینرو می توانید ساختمان داده ای شخصی تولید کنید که بصورت داخلی از یک آرایه استفاده می کند و کارآیی آن را افزایش میدهد. برای مثال میتوان به تواناییهای آرایه، قابلیت افزایش حجم و جتسجو را اضافه کرد.
ایجاد چنین ساختمان داده ای آنچنان می تواند مفید باشد که ممکن بخواهید از آن در برنامه های دیگر خود نیز استفاده نمایید. اما این ساختمان داده برای استفاده در برنامه های دیگر مفید نیست چراکه تنها عناصری از نوع Employee را میپذیرد. یک روش برای انعطاف پذیر کردن ساختمان داده مورد نظر آنست که بجای استفاده از آرایه ای از نوع Employee، آرایه ای از نوع Object را درون ساختمان داده خود استفاده کنیم. چون تمام انواع در .Net Framework از نوع Object مشتق میشوند، از اینرو آرایه ما میتواند هر نوع خاصی را بپذیرد. با این روش میتوانیم از ساختمان داده ایجاد شده در برنامه های دیگر نیز استفاده کنیم.
در .Net Framework چنین ساختمان داده ای بطور از پیش تعریف شده وجود دارد : کلاس System.Collections.ArrayList . ArrayList درون خود از آرایه ای از نوع Object استفاده کرده و امکان تغییر سایز خودکار را با افزایش تعداد عناصر مورد نیاز، فراهم مینماید. به دلیل اینکه ArrayList از آرایه ای از نوع Object استفاده می کند، از اینرو برنامه نویسان میتوانند از آن برای کار با انواع مختلف داده ای، بهره گیرند.
ایجاد انعطاف پذیری بیشتر، هزینه هایی دارد و در مورد ArrayList این هزینه مربوط به کارآیی است. از آنجائیکه ArrayList از نوع Object استفاده میکند، بهنگام خواندن مقادیر از ArrayList میبایست بطور صریح عمل casting را با توجه به نوع داده ذخیره شده انجام داد. (Casting عملی است که در آن نوع داده مورد استفاده را مشخص میکنیم. برای مثال x = (int) y; در اینجا معیین کرده ایم که متغییر y با نوع int به متغیر x تخصیص داده شود.) همانطور که به یاد دارید، گفتیم که آرایه هایی از نوع مقداری (همانند System.Int32 ، System.Double و System.Boolean) بصورت پیوسته در Managed Heap در فرم Unboxed خود ذخیره میشوند. اما آرایه مورد استفاده در ArrayList، از نوع Object است. از اینرو هنگامیکه ArrayList مورد نظر از انواع مقداری استفاده نماید، هر عنصر ArrayList مرجعی به نوع مقداری در فرم Boxed خود خواهد بود. این مطلب در شکل زیر به نمایش گذاشته شده است.
لینك تصویر (http://csharp-persian.netfirms.com/images/Data_Structure/datastructures-fig03big.JPG)
Boxing و Unboxing ، هنگامیکه از ArrayList هایی با انواع مقداری استفاده می کنید و حجم دسترسی به عناصر ArrayList بالاست، میتوان بشکل محسوسی در کارآیی برنامه تاثیر گذارد. همانطور که در شکل فوق نیز مشاهده میکنید، برای انواع مرجعی، فرمت شکل گیری حافظه در آرایه و ArrayList یکسان است.
استفاده از ArrayList ها، همچنین میتواند باعث بروز خطاهایی شود که تا زمان اجرای برنامه قابل لمس نخواهند بود. از آنجائیکه آرایه داخلی ArrayList از نوع Object است، قرار دادن نوع ناخواسته در ArrayList از سوی برنامه قابل قبول بوده و این مسئله باعث ایجاد خطا در برنامه میشود. همچنین این مسئله میتواند باعث پنهان شدن خطا تا زمان اجرا، تست و حتی، در بدترین شرایط، زمان تحویل نهایی برنامه شود.
Generic ها به کمک می آیند !
مسئله نوع و کارآیی در ArrayList ها، با استفاده از Generic ها در .Net Framework 2.0 بهبود یافته است. Generic این امکان را به طراح نرم افزار میدهد تا بهنگام ایجاد ساختمان داده انواع خاصی را برای استفاده در آن انتخاب نماید. برای روشن شدن بهتر موضوع مثالی را بررسی میکنیم. در این مثال کلاسی ایجاد میشود که در آن آرایه ای که به نوع خاصی محدود شده است، مورد استفاده قرار گرفته است.
public class TypeSafeList<T>
{
T[] innerArray = new T[0];
int currentSize = 0;
int capacity = 0;
public void Add(T item)
{
// see if array needs to be resized
if (currentSize == capacity)
{
// resize array
capacity = capacity == 0 ? 4 : capacity * 2; // double capacity
T[] copy = new T[capacity]; // create newly sized array
Array.Copy(innerArray, copy, currentSize); // copy over the array
innerArray = copy; // assign innerArray to the new, larger array
}
innerArray[currentSize] = item;
currentSize++;
}
public T this[int index]
{
get
{
if (index < 0 || index >= currentSize)
throw new IndexOutOfRangeException();
return innerArray[index];
}
set
{
if (index < 0 || index >= currentSize)
throw new IndexOutOfRangeException();
innerArray[index] = value;
}
}
public override string ToString()
{
string output = string.Empty;
for (int i = 0; i < currentSize - 1; i++)
output += innerArray[i] + ", ";
return output + innerArray[currentSize - 1];
}
}
در نخستین خط این کد و درون کلاس TypeSafeList، شناسه ای جهت تعیین نوع T تعریف شده است. این کد معیین میکند که استفاده کننده از آن میبایست یک نوع خاص را برای کار با آن در نظر بگیرد. در این کد، این نوع قابل انتخاب توسط برنامه نویس، با عنوان T تعریف شده که میتوان به جای T از هر نام متغییر دیگری نیز استفاده کرد. از این متغییر در متدها و ویژگیهای کلاس نیز استفاده شده است. برای مثال، آرایه داخلی از نوع T تعریف شده و متد Add متغییری از نوع T را بعنوان ورودی میپذیرد.
برای تعریف متغییری از این کلاس، برنامه نویس میبایست نوع T را معین نماید :
TypeSafeList<type> variableName;
در قطعه کد زیر نیز، نمونه ای از کلاس TypeSafeList که نوع int را میپذیرد نشان داده شده است :
TypeSafeList<int> fib = new TypeSafeList<int>();
fib.Add(1);
fib.Add(1);
for (int i = 2; i < 25; i++)
fib.Add(fib[i - 2] + fib[i - 1]);
Console.WriteLine(fib.ToString());
از مهمترین مزایای Generics به شرح زیر است :
Type-Safe : با استفاده از کلاس SafeTypeList، برنامه نویس اطمینان حاصل میکند که از انواع ناخواسته به طور اشتباه استفاده نخواهد کرد.
کارآیی : کنترل نوع مورد استفاده در زمان اجرا را حذف کرده و هزینه مربوط به Boxing و Unboxing را کاهش میدهد.
قابلیت استفاده مجدد : قابلیت استفاده مجدد در برنامه های مختلف را بالا میبرد.
بسیاری از ساختمان داده هایی که در این سری مطالب مورد بررسی قرار خواهند گرفت از Generics ها استفاده میکنند و بهنگام ساخت یک ساختمان داده، مانند درخت دودویی که در قسمت سوم مورد بررسی قرار خواهد گرفت، از Generics استفاده خواهیم کرد.
لیست : آرایه ای همگون با قابلیت تغییر سایز ابعاد
یک آرایه، همانطور که قبلا نیز مشاهده کردیم، ساختمان داده ای با قابلیت نگهداری تعداد معینی عنصر هم نوع است که بطور مرتب در کنار یکدیگر قرار گرفته اند. هر چند استفاده از آرایه بسیار ساده است، اما در مواردی همچون زمانیکه تعداد عناصر آرایه برای ما مشخص نیست و یا نیاز به تغییر سایز آرابه وجود داشته باشد، میـواند مشکل ساز باشد. یک روش برای پرهیز از تغییر سایز آرایه بطور دستی، ایجاد ساختمان داده ای مشابه به آرایه است که علاوه بر امکان خواندن و نوشتن اعضاء، قابلیت افزایش سایر را نیز در موارد مورد نیاز فراهم نماید. راهکار .Net Framework برای این ساختمان داده، لیست است که در Sysyem.Collections.Generics قرار دارد.
لیست، کلاسی است که درون خود از یک آرایه بهره می برد و علاوه بر قابلیت خواندن و نوشتن اعضاء این آرایه داخلی، قابلیت تغییر سایز خودکار آرایه را نیز فراهم می نماید. لیست نیز همانند آرایه، ساختمان داده ای همگون است، بدین معنا که تنها قابلیت ذخیره سازی عناصر هم نوع (از یک نوع داده ای) را دارا می باشد. لیست، از Generics بهره میبرد تا با استفاده از آنها، برنامه نویس امکان تعیین نوع داده مورد نظر را در هنگام استفاده، دارا باشد. در هنگام ایجاد نمونه ای جدید از کلاس لیست، میبایست نوع داده مورد استفاده در آن تعیین گردد :
// int ساخت لیستی از نوع داده ای
List<int> myFavoriteIntegers = new List<int>();
// ساخت لیستی از نوع داده ای رشته
List<string> friendsNames = new List<string>();
توجه کنید که نوع داده مورد استفاده در لیست بهنگام ایجاد نمونه ای جدید از کلاس لیست مشخص می گردد. بهنگام ایجاد نمونه جدید از لیست نیازی به تعیین سایز لیست نیست، هر چند میتوان سایز پیش فرضی برای لیست در نظر گرفت. برای افزودن عنصری به لیست، تنها کافیست تا از متد Add() آن استفاده کنید. همانند آرایه، دسترسی به عناصر لیست نیز از طریق اندیس صورت می گیرد. در مثال زیر لیستی از int ایجاد شده است. سپس با با استفاده از متد Add() عناصری به آن افزوده شده و سپس با استفاده از اندیس به این عناصر دسترسی پیدا شده است .
// ساخت لیست
List<int> powersOf2 = new List<int>();
// افزودن 6 عنصر به لیست
powersOf2.Add(1);
powersOf2.Add(2);
powersOf2.Add(4);
powersOf2.Add(8);
powersOf2.Add(16);
powersOf2.Add(32);
// تغییر دومین عنصر لیست به مقدار 10
powersOf2[1] = 10;
// انجام یک عملیات ریاضی با استفاده از عناصر لیست
int sum = powersOf2[2] + powersOf2[3];
لیست، در حقیقت پیدا سازی خاص از یک آرایه است که پیچیدگی های پیاده سازی را پنهان کرده است. با استفاده از لیست، نیازی به تعیین سایز آرایه در ابتدا ایجاد آن نداریم. همچنین به هنگام افزودن عنصری به آن، نیازی به تغییر سایز آرایه داخلی آن نیست. علاوه بر مطالب گفته شده، لیست متدهایی جهت انجام عملیات مورد استفاده بر روی آرایه ها می باشد. برای مثال، در یک آرایه، برای پیدا کردن یک عنصر درون اعضای آرایه می بایست از حلقه for استفاده نمایید. در لیست با استفاده از متد Contains() می توان به وجود عنصری خاص در لیست پی برد. همچنین با استفاده از متد IndexOf() می توان به محل ذخیره سازی عنصری خاص در لیست پی برد. کلاس لیست همچنین دارای متد BinarySearch() است که با استفاده از آن می توان به جستجوی باینری درون لیست مرتب شده پرداخت. با استفاده از متدهای دیگری نظیر Find() ، FindAll() ، Sort() و ConvertAll() نیز می توان با استفاده از delegate ها، به اجرای عملیاتی پرداخت که اجرای آنها بر روی آرایه ها نیاز به نوشتن چندین خط کد دارد.
منبع: http://www.700dolar.blogfa.com (http://www.700dolar.blogfa.com/)
این مطلب، آغاز یک سری شش قسمتی از مطالب مهم و کلیدی درباره ساختمان داده و کاربر آن در توسعه و طراحی نرم افزار است. در قسمت اول، مختصری درباره ساختمان داده ها، تعریف ساختمان داده، آنالیز کارآیی یک ساختمان داده و بررسی اهمیت این آنالیز صحبت خواهیم نمود. در این بخش همچنین درباره دو ساختمان داده بسیار مهم و رایج در .Net Framework یعنی آرایه ها و لیست ها صحبت خواهیم کرد.
توجه : مطالب موجود در این 6 قسمت، منطبق بر ساختار .Net Framework 2.0 و C# 2.0 تنظیم شده اند.
پیشنیاز این مطالب، آشنایی با زبان برنامه سازی C# است
قسمت اول : مقدمه ای بر ساختمان داده
مطالب مورد بحث در این قسمت بشرح زیر می باشند :
- مقدمه
- آنالیز کارآیی یک ساختمان داده
- ساختمان داده خطی، همگون و بسیار متداول : آرایه (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 Doe***tensionExist(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 عنصر خواهم داشت، در این حالت زمان اجرای برنامه من چقدر خواهد شد؟ " . توجه نمایید که کلمه "زمان اجرا " یا Running Time عملا به معنا محاسبه دقیق زمان اجرا برنامه نیست، بلکه محاسبه تعداد مراحل و زمان اجرای این مراحل برای یک عمل خواسته شده است. برای مثال در مورد آرایه، تعداد مراحل به تعداد دفعات دسترسی به عناصر آرایه است. برای جستجو درون یک آرایه، در صورتیکه n+1 عنصر در آرایه داشته باشیم، باید n+1 بار مقدار مورد نظر خود را با عناصر آرایه مقایسه نماییم. از اینرو می گوئیم مدت زمان جستجو درون یک آرایه بطور خطی با تعداد عناصر موجود در آرایه رابطه مستقیم دارد.
این روش آنالیز که در اینجا مطرح گردید، به روش آنالیز آسیمپوتیک (Asymptotic Analyze) معروف است. روش علامتگذاری که در این روش آنالیز مورد استفاده قرار می گیرد، به روش نشانه گذاری O (Big-Oh Notation) معروف است. برای نشان دادن کارآیی جستجو در آرایه غیر مرتب با استفاده از این روش نشانه گذاری، بشکل زیر عمل می شود O(n) که نشان دهنده رابطه زمان با تعداد اعضا است. بدین ترتیب با استفاده از O(n) برای نشان دادن کارآیی یک ساختمان داده، این مفهوم بدست می آید که رابطه ای خطی و مستقیم بین افزایش تعداد اعضای از n به n+1 و زمان انجام عملیات وجود دارد. بدین ترتیب علامت O نشان دهنده روش نشانه گذاری و روش آنالیز کارآیی است و n نشان دهنده چگونگی افزایش مراحل پردازش عمل بسته به تعداد عناصری است که می خواهند مورد پردازش قرار گیرند.
برای محاسبه زمان اجرای یک قطعه کد با استفاده از O-Notation یا همان Asymptotic Analyze می توان از چند مرحله ساده زیر استفاده نمود :
1- بدست آوردن مراحلی که زمان اجرای یک الگوریتم را شکل می دهند. همانطور که قبلاً ذکر شد، این مراحل برای یک آرایه، خواندن و نوشتن یا همان دسترسی به عناصر آرایه است و این مراحل برای ساختمان های داده ای دیگر متفاوت خواهد بود. باید توجه داشته باشید که برای آنالیز کارآیی یک ساختمان داده، تنها به مراحلی که توسط خود ساختمان داده ی مورد نظر انجام می شود توجه می گردد و عملیات ساده ای که توسط کامپیوتر انجام می شوند را در این محاسبه به حساب نمی آوریم. برای مثال در کد بالا، برای محاسبه کارآیی تنها به تعداد دفعات لازم برای دسترسی به عناصر آرایه توجه کرده و به زمان های لازم جهت ایجاد متغیرها و با زمان محاسبه تساوی دو رشته اهمیت نداده ایم.
2- خطهایی از برنامه که در الگوریتم شما تاثیر دارند و می خواهید کارآیی را برای آنها محاسبه کنید را پیدا کرده و در کنار آنها عدد 1 قرار دهید.
3- اگر این خطوط که آنها را با عدد 1 مشخص کرده اید خود یک حلقه تکرار هستند، بجای عدد 1 در کنار آنها عدد معادل بیشترین تعداد تکرار حلقه را قرار دهید. اگر در جایی حلقه تو در تو دارید، باید از ضرب بیشترین تعداد دفعات تکرار حلقه ها استفاده کنید.
4- بزگترین عدد نوشته شده را پیدا کنید. این عدد زمان اجراست.
حال برای روشتن تر شدن موضوع همین مراحل را برای کد نوشته شده در بالا اجرا میکنیم. در کد نوشته شده در بالا، مراحل مورد نظر برای ما، تعداد دفعات دسترسی به عناصر آرایه است. با توجه به کد و با توجه به مرحله 2، تنها در یک خط کد، دسترسی به عناصر آرایه وجود دارد، پس عدد 1 را در کنار این خط قرار می دهیم. با توجه به مرحله 3، این خط در یک حلقه تکرار قرار دارد و این حلقه n با تکرار می شود که n تعداد عناصر آرایه است. طبق مرحله 3، عدد 1 را پاک کرده و بجای آن n در کنار این خط قرار می دهیم. N بزرگترین مقدار نوشته شده است از اینرو زمان اجرا O(n) است.
O(n) یکی از صدها زمان اجرای موجود در آنالیز Asymptotic است. برخی دیگر از زمانهای اجرا عبارتند از O(log2 n), O(n log2 n), O(n2), O(2n) و .... بدون اینکه وارد جزئیات پیچیدگیهای ریاضیاتی Notation_O شویم، بیان میداریم که هرچه مقدار داخل پرانتز در این آنالیز کوچکتر باشد، عملیات بر روی ساختمان داده کارآمدتر است. برای مثال ساختمان داده ای که زمان اجرای آن O(log n) است به مراتب کارآمدتر از ساختمان داده ایست که زمان اجرای آن O(n) است. چراکه log n < n
نکته : برای یادآوری باید بگویم که loga b = y روش دیگری برای نمایش ay = b است. از اینرو log2 n رشد کندتری نسبت به n دارد، چراکه اگر n=8 فرض کنیم، log2 n = 3 می شود در حالیکه n=8 است. در قسمت سوم از این سری مطالب، با درخت های جستجوی دودویی آشنا می شویم که زمان اجرایی آنها O(log2 n) است.
زمان اجرای Asymptotic و الگوریتمهای دنیای واقعی
زمان اجرای Asymptotic روشی برای محاسبه کارآیی الگوریتم در زمانی است که تعداد عناصر مورد نظر آن به سمت بینهایت میل می کند. هنگامیکه گفته می شود زمان اجرایی یک الگوریتم از الگوریتم دیگر بیشتر است، از لحاظ ریاضی بدین معناست که مراحل اجرایی و زمان اجرایی این مراحل در الگوریتم زمان بر بیشتر از الگوریتمی است که زمان اجرایی کمتری دارد. اما باید توجه کرد که در مواردی، الگوریتم هایی با مراحل اجرایی کم ، با اینکه دارای زمان اجرایی بالایی هستند، از الگوریتمهایی که زمان اجرایی پائین تری دارند، سریعتر اجرا می شودند. همانطور که گفته شد این امر معمولا در مواردی صادق است که الگوریتمی که زمان اجرایی آن بالاست، دارای مراحل بسیار کمی باشد.
بعنوان مثال، الگوریتمهای بسیار زیاد و متفاوتی برای مرتب سازی آرایه ها وجود دارد و هر یک از آنها دارای زمان اجرایی متفاوتی هستند. یکی از ساده ترین و بدیهی ترین الگوریتمهای مرتب سازی (Sort) الگوریتم مرتب سازی حبابی یا Bubble Sort است. زمان اجرایی این الگوریتم O(n2) است که این مقدار خاطر وجود دو حلقه تودرتو در این الگوریتم بوجود آمده است. در مقابل الگوریتم دیگری به نام Merge Sort وجود دارد که زمان اجرایی آن O(n log2 n) است. زمان اجرایی Merge Sort به مراتب کمتر از زمان اجرایی Bubble Sort است. اما برای آرایه هایی با تعداد عناصر کم، زمان اجرایی Bubble Sort کمتر از زمان اجرای Merge Sort است ! از آنجائیکه Merge Sort از یک ساختار بازگشتی استفاده میکند و نیز نیم آرایه Sort شده را در انتها با یکدیگر ادغام می نماید، در مورد آرایه های کوچک کارآیی چندانی ندارد و چون Bubble Sort تنها از جابجا کردن عناصر مجاور آرایه استفاده می کند، از اینرو برای آرایه ها کوچک الگوریتمی مناسب تر است. (لطفاً در صورتیکه در مورد الگوریتمهای Sort سوال و یا مشکلی دارید حتما به من ایمیل بزنید) نهایتاً، مراحل کاری Merge Sort از Bubble Sort کمتر است اما از آنجائیکه وزن این مراحل بالاست (هر مرحله احتیاج به زمان پردازشی بالایی دارد) از اینرو برای آرایه هایی عظیم مفید است. حال آنکه برای آرایه هایی با حجم کم الگوریتم Bubble Sort مناسب تر است. پس علاوه بر توجه به زمان اجرایی یک الگوریتم، توجه به موارد استفاده و حجم داده مورد نظر نیز موثر است.
آرایه : ساختمان داده ای خطی، همگون، با امکان دسترسی مستقیم
آرایه ها یکی از ساده ترین و پر استفاده ترین ساختمانهای داده هستند که در تمامی زبانهای برنامه سازی دارای ویژگیهای مشترکی هستند :
· محتویات آرایه در یک فضای حافظه پیوسته ذخیره می شود
· تمامی عناصر یک آرایه باید از یک نوع یا از یک نوع مشتق شده باشند. از اینرو به آرایه ، ساختمان داده ای همگون گفته میشود.
· دسترسی به عناصر آرایه بصورت مستقیم و از طریق اندیس است.
عملیات متدوالی که بر روی آرایه ها انجام میشود نیز بشرخ زیر است :
· تخصیص
· دسترسی
در زبان C# هنگامیکی آرایه ای ایجاد میشود، مقدار پیش فرض تهی (Null) برای آن در نظر گرفته میشود. برای مثال خط زیر آرایه تهی BoolArray را ایجاد میکند :
bool[] BoolArray;
قبل از اینکه بتوانیم از آرایه ها استفاده کنیم، می بایست نمونه ای از آن را ایجاد نماییم تا بتوانیم عناصر مورد نظر را در آن ذخیره کنیم :
arrayName = new arrayType[allocationSize];
این خط از کد، باعث تخصیص فضای پیوسته ای از حافظه در CLR-Managed Heap به اندازه تعداد allocationSize از arrayType میشود. (برای مثال اگر فضای مورد نیاز برای ذخیره سازی متغیری از نوع int برابر 2 بایت باشد، برای آرایه ای که allocationSize آن 5 است، به 10 بایت حافظه نیاز است.) اگر arrayType از انواع مقداری (Value Type) باشد، آنگاه مقادیری از نوع arrayType و به تعداد allocationSize ایجاد میشود. (این مقادیر ایجاد شده unboxed هستند.) در صورتیکه arrayType از انواع مرجعی (Reference Type) باشند، آنگاه مرجع هایی از نوع arrayType و به تعداد allocationSize ایجاد میگردند. (در صورتیکه تفاوت بین انواع مرجعی و مقداری و فرق بین پشته و heap را نمیدانید، به درک انواع رایج در .Net مراجعه نمایید.)
برای درک چگونگی نگهداری عناصر آرایه توسط .Net Framework ، به مثال زیر توجه نمایید :
bool [] booleanArray;
FileInfo [] files;
booleanArray = new bool[10];
files = new FileInfo[10];
در اینجا، آرایه booleanArray از نوع System.Boolean است در حالیکه آرایه files از نوع مرجعی System.IO.FileInfo میباشد. شکل زیر وضعیت CLR-Managed Heap را پس از اجرای این چند کد به نمایش در می آورد :
لینك تصویر (http://csharp-persian.netfirms.com/images/Data_Structure/datastructures-fig01big.JPG)
باید به این نکته نیز توجه نمایید که 10 عنصر موجود در آرایه Files، مرجع هایی به نمونه هایی از FileInfo هستند.
لینك تصویر (http://csharp-persian.netfirms.com/images/Data_Structure/datastructures-fig02big.JPG)
در .Net تمامی عناصر آرایه امکان نوشته شدن و نوشتن بر آرایه را دارند. نحوه دسترسی به عناصر آرایه به فرم زیر است :
// Read an array element
bool b = booleanArray[7];
// Write to an array element
booleanArray[0] = false;
زمان اجرایی دسترسی به یک آرایه را بصورت O(1) نشان می دهیم، زیرا زمانی ثابت است. این به معنی آنست که، هر چقدر هم که عناصر آرایه زیاد باشند، زمان دسترسی به یک عنصر یکسان و ثابت است. علت ثابت بودن این زمان آنست که، عناصر آرایه بصورت متوالی در خانه های حافظه قرار می گیرند و به هنگام دسترسی به یک عنصر تنها کافی است تا نقطه شروع آرایه، طول عناصر آرایه و اندیس عنصر مورد نظر را داشته باشیم. در این حالت دسترسی به هر یک از عناصر آرایه زمانی واحد و ثابت را نیاز دارد.
نکته قابل توجه دیگر آنست که، در کدهای مدیریت شده، زمان دسترسی به عناصر آرایه اندکی با آنچه گفته شد متفاوت است. برای مثال در .Net ، با هر درخواست برای دسترسی به عنصر یک آرایه، CLR اندیس مورد نظر را نیز چک میکند تا این اندیس درون آرایه قرار داشته باشد. درصورتیکه اندیس موزد نظر خارج از آرایه باشد، استثنای IndexOutOfRangeException ایجاد میشود. (برای مثال اگر آرایه ای با 10 عنصر داشته باشیم و اندیس دسترسی به عنصر آرایه را 15 در نظر بگیریم، این استثناء رخ خواهد داد، چراکه اندیس مورد نظر خارج از مرزهای (Bound) آرایه است.) این کنترل باعث می شود تا به هنگام استفاده از آرایه ها مطمئن باشیم که به اشتباه وارد قسمت دیگری از حافظه نشده ایم. (برای مثال در برخی از نسخه های کامپایلر C این کنترل صورت نمی گیرد و شما می توانید به عنصر یازدهم یک آرایه ده عنصری دسترسی پیدا کنید !!! در این حالت اتفاقی که رخ می دهد آنست که، کامپایلر به اشتباه محتویات خانه ای از حافظه را به شما نشان میدهد که اصلا جزو آرایه مورد نظر نیست. این امر باعث بروز اشکالات فراوانی برای برنامه نویس به هنگام تست برنامه میشود. چراکه محتویات خانه ای از حافظه که به اشنباه اندیس دهی شده است، ممکن است تاثیرات نامطلوب و غیر قابل پیش بینی بر روی نتیجه برنامه داشته باشد و بررسی و کنترل منبع این خطا بسیار دشوار است.) توجه نمایید که انجام این کنترل باعث تغییر زمان اجرایی دسترسی به عناصر آرایه (O(1)) نمیشود چراکه با افزایش تعدا عناصر آرایه این زمان تغییر نمیکند.
نکته : انجام چنین کنترلی بر روی اندیس دسترسی به عناصر آرایه، باعث افزایش کارآیی در برنامه هایی میشود که بطور عظیمی با آرایه ها و دسترسی به عناصر آنها سروکار دارند. در کدهای مدیریت نشده (Unmanaged Code) امکان غیر فعال کردن این کنترل بر روی اندیس آرایه وجود دارد. برای مطالعه بیشتر در این زمینه میتوانید به فصل چهاردهم از کتاب "Applied Microsoft .Net Framework Programming" نوشته Jeffrey Richter مراجعه نمایید.
بهنگام کار با آرایه ها ممکن است نیاز به افزایش تعداد عناصر آرایه داشته باشیم. برای انجام چنین کاری لازم است تا نمونه جدیدی از آرایه مورد نظر را با طول جدید ایجاد کرده و عناصر آرایه فعلی را در آرایه جدید کپی نمایید. نمونه ای از کد مورد نظر برای اجرای چنین عملی در زیر آمده است :
// Create an integer array with three elements
int [] fib = new int[3];
fib[0] = 1;
fib[1] = 1;
fib[2] = 2;
// Redimension message to a 10 element array
int [] temp = new int[10];
// Copy the fib array to temp
fib.CopyTo(temp, 0);
// Assign temp to fib
fib = temp;
پس از اجرای آخرین خط در کد بالا، آریه fib به یک آریه ده عنصری اشاره میکند. عناصر 3 تا 9 این آرایه جدید مقدار پیش فرض Int32 یعنی صفر را دارا خواهند بود.
آرایه ها یکی از بهترین ساختمان های داده برای نگهداری مجموعه ای از داده های همگون است که باید بطور مستقیم مورد دسترسی قرار گیرند. جستجو درون یک آرایه نا مرتب، زمان اجرای خطی دارد. توجه نمایید، در صورتیکه آرایه ای مرتب شده را مورد جستجو قرار دهیم، زمان اجرای جستجو به O(log n) تغییر پیدا خواهد کرد که زمانی نزدیک به زمان اجرایی درخت جستجوی دودویی است. توجه نمایید که در .Net ، کلاس Array دارای متد BinarySearch() است که با استفاده از آن میتوان به جستجوی باینری درون آرایه مرتب شده پرداخت.
نکته : همانطور که میدانید .Net Framework از آرایه های چند بعدی نیز پستیبانی مینماید. از آنجائیکه زمان اجرای جستجو درون آرایه تک بعدی برابر با O(n) است، زمان اجرای جستجو در یک آرایه k بعدی برابر با O(nk) خواهد بود. توجه کنید که در اینجا n تعداد عناصر آرایه در هر بعد است و منظور از n تعداد کل عناصر موجود در آرایه نیست.
ساخت ساختمان داده ای مطمئن، کارآ و قابل استفاده مجدد
هنگامیکه میخواهیم ساختمان داده ای را برای مسئله ای خاص ایجاد نمائیم، ویژگیهای داخلی ساختمان داده در اغلب موارد، امکان شخصی سازی برای منطبق شدن با مسئله ما را فراهم مینماید. برای مثال فرض کنید میخواهید برنامه ای برای محاسبه حقوق کارکنان خود ایجاد نمایید. در این برنامه یکی از ساختمان داده های مورد نیاز میتواند آرایه Employee باشد. در عین حال شما نمی خواهید برای ورود هر کارمند جدید به شرکت، طول آرایه را تغییر دهید. از اینرو می توانید ساختمان داده ای شخصی تولید کنید که بصورت داخلی از یک آرایه استفاده می کند و کارآیی آن را افزایش میدهد. برای مثال میتوان به تواناییهای آرایه، قابلیت افزایش حجم و جتسجو را اضافه کرد.
ایجاد چنین ساختمان داده ای آنچنان می تواند مفید باشد که ممکن بخواهید از آن در برنامه های دیگر خود نیز استفاده نمایید. اما این ساختمان داده برای استفاده در برنامه های دیگر مفید نیست چراکه تنها عناصری از نوع Employee را میپذیرد. یک روش برای انعطاف پذیر کردن ساختمان داده مورد نظر آنست که بجای استفاده از آرایه ای از نوع Employee، آرایه ای از نوع Object را درون ساختمان داده خود استفاده کنیم. چون تمام انواع در .Net Framework از نوع Object مشتق میشوند، از اینرو آرایه ما میتواند هر نوع خاصی را بپذیرد. با این روش میتوانیم از ساختمان داده ایجاد شده در برنامه های دیگر نیز استفاده کنیم.
در .Net Framework چنین ساختمان داده ای بطور از پیش تعریف شده وجود دارد : کلاس System.Collections.ArrayList . ArrayList درون خود از آرایه ای از نوع Object استفاده کرده و امکان تغییر سایز خودکار را با افزایش تعداد عناصر مورد نیاز، فراهم مینماید. به دلیل اینکه ArrayList از آرایه ای از نوع Object استفاده می کند، از اینرو برنامه نویسان میتوانند از آن برای کار با انواع مختلف داده ای، بهره گیرند.
ایجاد انعطاف پذیری بیشتر، هزینه هایی دارد و در مورد ArrayList این هزینه مربوط به کارآیی است. از آنجائیکه ArrayList از نوع Object استفاده میکند، بهنگام خواندن مقادیر از ArrayList میبایست بطور صریح عمل casting را با توجه به نوع داده ذخیره شده انجام داد. (Casting عملی است که در آن نوع داده مورد استفاده را مشخص میکنیم. برای مثال x = (int) y; در اینجا معیین کرده ایم که متغییر y با نوع int به متغیر x تخصیص داده شود.) همانطور که به یاد دارید، گفتیم که آرایه هایی از نوع مقداری (همانند System.Int32 ، System.Double و System.Boolean) بصورت پیوسته در Managed Heap در فرم Unboxed خود ذخیره میشوند. اما آرایه مورد استفاده در ArrayList، از نوع Object است. از اینرو هنگامیکه ArrayList مورد نظر از انواع مقداری استفاده نماید، هر عنصر ArrayList مرجعی به نوع مقداری در فرم Boxed خود خواهد بود. این مطلب در شکل زیر به نمایش گذاشته شده است.
لینك تصویر (http://csharp-persian.netfirms.com/images/Data_Structure/datastructures-fig03big.JPG)
Boxing و Unboxing ، هنگامیکه از ArrayList هایی با انواع مقداری استفاده می کنید و حجم دسترسی به عناصر ArrayList بالاست، میتوان بشکل محسوسی در کارآیی برنامه تاثیر گذارد. همانطور که در شکل فوق نیز مشاهده میکنید، برای انواع مرجعی، فرمت شکل گیری حافظه در آرایه و ArrayList یکسان است.
استفاده از ArrayList ها، همچنین میتواند باعث بروز خطاهایی شود که تا زمان اجرای برنامه قابل لمس نخواهند بود. از آنجائیکه آرایه داخلی ArrayList از نوع Object است، قرار دادن نوع ناخواسته در ArrayList از سوی برنامه قابل قبول بوده و این مسئله باعث ایجاد خطا در برنامه میشود. همچنین این مسئله میتواند باعث پنهان شدن خطا تا زمان اجرا، تست و حتی، در بدترین شرایط، زمان تحویل نهایی برنامه شود.
Generic ها به کمک می آیند !
مسئله نوع و کارآیی در ArrayList ها، با استفاده از Generic ها در .Net Framework 2.0 بهبود یافته است. Generic این امکان را به طراح نرم افزار میدهد تا بهنگام ایجاد ساختمان داده انواع خاصی را برای استفاده در آن انتخاب نماید. برای روشن شدن بهتر موضوع مثالی را بررسی میکنیم. در این مثال کلاسی ایجاد میشود که در آن آرایه ای که به نوع خاصی محدود شده است، مورد استفاده قرار گرفته است.
public class TypeSafeList<T>
{
T[] innerArray = new T[0];
int currentSize = 0;
int capacity = 0;
public void Add(T item)
{
// see if array needs to be resized
if (currentSize == capacity)
{
// resize array
capacity = capacity == 0 ? 4 : capacity * 2; // double capacity
T[] copy = new T[capacity]; // create newly sized array
Array.Copy(innerArray, copy, currentSize); // copy over the array
innerArray = copy; // assign innerArray to the new, larger array
}
innerArray[currentSize] = item;
currentSize++;
}
public T this[int index]
{
get
{
if (index < 0 || index >= currentSize)
throw new IndexOutOfRangeException();
return innerArray[index];
}
set
{
if (index < 0 || index >= currentSize)
throw new IndexOutOfRangeException();
innerArray[index] = value;
}
}
public override string ToString()
{
string output = string.Empty;
for (int i = 0; i < currentSize - 1; i++)
output += innerArray[i] + ", ";
return output + innerArray[currentSize - 1];
}
}
در نخستین خط این کد و درون کلاس TypeSafeList، شناسه ای جهت تعیین نوع T تعریف شده است. این کد معیین میکند که استفاده کننده از آن میبایست یک نوع خاص را برای کار با آن در نظر بگیرد. در این کد، این نوع قابل انتخاب توسط برنامه نویس، با عنوان T تعریف شده که میتوان به جای T از هر نام متغییر دیگری نیز استفاده کرد. از این متغییر در متدها و ویژگیهای کلاس نیز استفاده شده است. برای مثال، آرایه داخلی از نوع T تعریف شده و متد Add متغییری از نوع T را بعنوان ورودی میپذیرد.
برای تعریف متغییری از این کلاس، برنامه نویس میبایست نوع T را معین نماید :
TypeSafeList<type> variableName;
در قطعه کد زیر نیز، نمونه ای از کلاس TypeSafeList که نوع int را میپذیرد نشان داده شده است :
TypeSafeList<int> fib = new TypeSafeList<int>();
fib.Add(1);
fib.Add(1);
for (int i = 2; i < 25; i++)
fib.Add(fib[i - 2] + fib[i - 1]);
Console.WriteLine(fib.ToString());
از مهمترین مزایای Generics به شرح زیر است :
Type-Safe : با استفاده از کلاس SafeTypeList، برنامه نویس اطمینان حاصل میکند که از انواع ناخواسته به طور اشتباه استفاده نخواهد کرد.
کارآیی : کنترل نوع مورد استفاده در زمان اجرا را حذف کرده و هزینه مربوط به Boxing و Unboxing را کاهش میدهد.
قابلیت استفاده مجدد : قابلیت استفاده مجدد در برنامه های مختلف را بالا میبرد.
بسیاری از ساختمان داده هایی که در این سری مطالب مورد بررسی قرار خواهند گرفت از Generics ها استفاده میکنند و بهنگام ساخت یک ساختمان داده، مانند درخت دودویی که در قسمت سوم مورد بررسی قرار خواهد گرفت، از Generics استفاده خواهیم کرد.
لیست : آرایه ای همگون با قابلیت تغییر سایز ابعاد
یک آرایه، همانطور که قبلا نیز مشاهده کردیم، ساختمان داده ای با قابلیت نگهداری تعداد معینی عنصر هم نوع است که بطور مرتب در کنار یکدیگر قرار گرفته اند. هر چند استفاده از آرایه بسیار ساده است، اما در مواردی همچون زمانیکه تعداد عناصر آرایه برای ما مشخص نیست و یا نیاز به تغییر سایز آرابه وجود داشته باشد، میـواند مشکل ساز باشد. یک روش برای پرهیز از تغییر سایز آرایه بطور دستی، ایجاد ساختمان داده ای مشابه به آرایه است که علاوه بر امکان خواندن و نوشتن اعضاء، قابلیت افزایش سایر را نیز در موارد مورد نیاز فراهم نماید. راهکار .Net Framework برای این ساختمان داده، لیست است که در Sysyem.Collections.Generics قرار دارد.
لیست، کلاسی است که درون خود از یک آرایه بهره می برد و علاوه بر قابلیت خواندن و نوشتن اعضاء این آرایه داخلی، قابلیت تغییر سایز خودکار آرایه را نیز فراهم می نماید. لیست نیز همانند آرایه، ساختمان داده ای همگون است، بدین معنا که تنها قابلیت ذخیره سازی عناصر هم نوع (از یک نوع داده ای) را دارا می باشد. لیست، از Generics بهره میبرد تا با استفاده از آنها، برنامه نویس امکان تعیین نوع داده مورد نظر را در هنگام استفاده، دارا باشد. در هنگام ایجاد نمونه ای جدید از کلاس لیست، میبایست نوع داده مورد استفاده در آن تعیین گردد :
// int ساخت لیستی از نوع داده ای
List<int> myFavoriteIntegers = new List<int>();
// ساخت لیستی از نوع داده ای رشته
List<string> friendsNames = new List<string>();
توجه کنید که نوع داده مورد استفاده در لیست بهنگام ایجاد نمونه ای جدید از کلاس لیست مشخص می گردد. بهنگام ایجاد نمونه جدید از لیست نیازی به تعیین سایز لیست نیست، هر چند میتوان سایز پیش فرضی برای لیست در نظر گرفت. برای افزودن عنصری به لیست، تنها کافیست تا از متد Add() آن استفاده کنید. همانند آرایه، دسترسی به عناصر لیست نیز از طریق اندیس صورت می گیرد. در مثال زیر لیستی از int ایجاد شده است. سپس با با استفاده از متد Add() عناصری به آن افزوده شده و سپس با استفاده از اندیس به این عناصر دسترسی پیدا شده است .
// ساخت لیست
List<int> powersOf2 = new List<int>();
// افزودن 6 عنصر به لیست
powersOf2.Add(1);
powersOf2.Add(2);
powersOf2.Add(4);
powersOf2.Add(8);
powersOf2.Add(16);
powersOf2.Add(32);
// تغییر دومین عنصر لیست به مقدار 10
powersOf2[1] = 10;
// انجام یک عملیات ریاضی با استفاده از عناصر لیست
int sum = powersOf2[2] + powersOf2[3];
لیست، در حقیقت پیدا سازی خاص از یک آرایه است که پیچیدگی های پیاده سازی را پنهان کرده است. با استفاده از لیست، نیازی به تعیین سایز آرایه در ابتدا ایجاد آن نداریم. همچنین به هنگام افزودن عنصری به آن، نیازی به تغییر سایز آرایه داخلی آن نیست. علاوه بر مطالب گفته شده، لیست متدهایی جهت انجام عملیات مورد استفاده بر روی آرایه ها می باشد. برای مثال، در یک آرایه، برای پیدا کردن یک عنصر درون اعضای آرایه می بایست از حلقه for استفاده نمایید. در لیست با استفاده از متد Contains() می توان به وجود عنصری خاص در لیست پی برد. همچنین با استفاده از متد IndexOf() می توان به محل ذخیره سازی عنصری خاص در لیست پی برد. کلاس لیست همچنین دارای متد BinarySearch() است که با استفاده از آن می توان به جستجوی باینری درون لیست مرتب شده پرداخت. با استفاده از متدهای دیگری نظیر Find() ، FindAll() ، Sort() و ConvertAll() نیز می توان با استفاده از delegate ها، به اجرای عملیاتی پرداخت که اجرای آنها بر روی آرایه ها نیاز به نوشتن چندین خط کد دارد.
منبع: http://www.700dolar.blogfa.com (http://www.700dolar.blogfa.com/)