ساختمان داده

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

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

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

 

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

 

در قسمت دوم ، به بررسی صف (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 f

alse; // If we reach here, we didn’t find the extension

}

}

به نگاهی دقیق تر به این برنامه، متوجه می شوید که در بدترین حالت، یعنی زمانیکه فایل مورد نظر در آرایه وجود نداشته باشد و یا وجود داشته باشد اما در آخرین خانه آرایه جای داشته باشد، باید تمامی عناصر آرایه را یکبار مورد بررسی و جستجو قرار دهیم. برای آنالیز مسائل، بطور مثال برای آنالیز مرتب سازی عناصر آرایه (Sort)، به شکل زیر باید فکر کنیم : ” فرص می کنم آرایه ای با n عنصر دارم، اگر عنصر دیگری به این آرایه اضافه کنم n+1 عنصر خواهم داشت، در این حالت زمان اجرای برنامه من چقدر خواهد شد؟ ” . توجه نمایید که کلمه “زمان اجرا ” یا Running Time عملا به معنا محاسبه دقیق زمان اجرا برنامه نیست، بلکه محاسبه تعداد مراحل و زمان اجرای این مراحل برای یک عمل خواسته شده است. برای مثال در مورد آرایه، تعداد مراحل به تعداد دفعات دسترسی به عناصر آرایه است. برای جستجو درون یک آرایه، در صورتیکه n+1 عنصر در آرایه داشته باشیم، باید n+1 بار مقدار مورد نظر خود را با عناصر آرایه مقایسه نماییم. از اینرو می گوئیم مدت زمان جستجو درون یک آرایه بطور خطی با تعداد عناصر موجود در آرایه رابطه مستقیم دارد.

این روش آنالیز که در اینجا مطرح گردید، به روش آنالیز آسیمپوتیک (Asymptotic A

nalyze) معروف است. روش علامتگذاری که در این روش آنالیز مورد استفاده قرار می گیرد، به روش نشانه گذاری O (Big-Oh Notation) معروف است. برای نشان دادن کارآیی جستجو در آرایه غیر مرتب با استفاده از این روش نشانه گذاری، بشکل زیر عمل می شود O(n) که نشان دهنده رابطه زمان با تعداد اعضا است. بدین ترتیب با استفاده از O(n) برای نشان دادن کارآیی یک ساختمان داده، این مفهوم بدست می آید که رابطه ای خطی و مستقیم بین افزایش تعداد اعضای از n به n+1 و زمان انجام عملیات وجود دارد. بدین ترتیب علامت O ن

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

برای محاسبه زمان اجرای یک قطعه کد با استفاده از O-Notation یا همان Asymptotic Analyze می توان از چند مرحله ساده زیر استفاده نمود :

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

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

۲- خطهایی از برنامه که در الگوریتم شما تاثیر دارند و می خواهید کارآیی

را برای آنها محاسبه کنید را پیدا کرده و در کنار آنها عدد ۱ قرار دهید.

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

۴- بزگترین عدد نوشته شده را پیدا کنید. این عدد زمان اجراست.

حال برای روشتن تر شدن موضوع همین مراحل را برای کد نوشته شده در بالا اجرا میکنیم. در کد نوشته شده در بالا، مراحل مورد نظر برای ما، تعداد دفعات دسترسی به عناصر آرایه است. با توجه به کد و با توجه به مرحله ۲، تنها در یک خط کد، دسترسی به عناصر آرایه وجود دارد، پس عدد ۱ را در کنار این خط قرار می دهیم. با توجه به مرحله ۳، این خط در یک حلقه تکرار قرار دارد و این حلقه n با تکرار می شود که n تعداد عناصر آرایه است. طبق مرحله ۳، عدد ۱ را پاک کرده و بجای آن 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-Man

aged Heap به اندازه تعداد allocationSize از arrayType میشود. (برای مثال اگر فضای مورد نیاز برای ذخیره سازی متغیری از نوع int برابر ۲ بایت باشد، برای آرایه ای که allocationSize آن ۵ است، به ۱۰ بایت حافظه نیاز است.) اگر 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 را پس از اجرای این چند کد به نمایش در می آورد :

 

باید به این نکته نیز توجه نمایید که ۱۰ عنصر موجود در آرایه Files، مرجع هایی به نمونه هایی از FileInfo هستند.

در .Net تمامی عناصر آرایه امکان نوشته شدن و نوشتن بر آرایه را دارند. نحوه دسترسی به عناصر آرایه به فرم زیر است :

// Read an array element

bool b = booleanArray[7];

// Write to an array element

booleanArray[0] = false;

 

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

نکته قابل توجه دیگر آنست که، در کدهای مدیریت شده، زمان دسترسی به عناصر آرایه اندکی با آنچه گفته شد متفاوت است. برای مثال در .Net ، با هر درخواست برای دسترسی به عنصر یک آرایه، CLR اندیس مورد نظر را نیز چک میکند تا این اندیس درون آرایه قرار داشته باشد. درصورتیکه اندیس موزد نظر خارج از آرایه باشد، استثنای IndexOutOfRangeException ایجاد میشود. (برای مثال اگر آرایه ای با ۱۰ عنصر داشته باشیم و اندیس دسترسی به عنصر آرایه را ۱۵ در نظر بگیریم، این استثناء رخ خواهد داد، چراکه اندیس مورد نظر خارج از مرزهای (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 به یک آریه ده عنصری اشاره میکند. عناصر ۳ تا ۹ این آرایه جدید مقدار پیش فرض 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 استفاده می کند، از اینرو برنامه نویسان میتوانند از آن برای کار با انواع مختلف داده ای، بهره گیرند.