ساختمان داده ها و کلکسیون ها در سی شارپ C sharp

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

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

کلاس های خود ارجاع

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

 

Class Node

{

Private int data

Private Node next

…

}

در این دستورات ، کلاسی به نام Node ایجاد شد دارای دو فیلد اختصاصی است . فیلدdata از نوع int و فیلد next از نوع Node است . یعنی فیلد Node می تواند به شی ای از کلاس Node اشاره کند . به عبارت دیگر ، دو فیلد Node مرجعی به شی از نوع کلاس Node خواهد شد .

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

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

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

Node node1=new Node();

 

پشته ها

پشته ، ساختمان داده ای است که عناصر فقط به بالای آن اضافه و از بالای آن حذف می شوند . این ساختمان داده راLIFO  یا خروج به ترتیب عکس ورود می نمامند . داده ای که آخر وارد پشته شد ، اول از پشته حذف می شود . عمل قراردادن عنصر در پشته را push و عمل حذف عنصر از پشته را pop می نامند .

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

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

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

صف ها

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

درخت ها در سی شارپ C#

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

درخت های دودویی نیز  انواع مختلفی دارند .یکی از معروف ترین آنها ، درخت جست و جوی دودویی یا BST است . درخت جست و جوی دودویی که فاقد گره تکراری است ، دارای این ویژگی است که مقادیر موجود در زیر درخت چپ کوچک تر از مقدار ریشه ، و مقادیر موجود در زیر درخت راست ، بزرگ تر از مقدار ریشه اند .سه عمل در مورد درخت های جست و جوی دودویی مورد توجه است ، شامل ساخت درخت (درج گره در درخت) ، پیامش درخت و حذف گره ها از درخت است . حذف گره ها از درخت ، مسئله ساده ای نیست ، آن را به درس ساختمان داده ها موکول می کنیم پیمایش درخت به معنای ملاقات کردن تمام گره های درخت است که به سه روش انجام می شود :

Inorder : در این روش ، ابتدا گره سمت چپ ، سپس گره ریشه و سپس گره سمت راست ملاقات می شود.

Preorder : در این روش ، ابتدا گره ریشه ، سپس گره چپ و سپس گره سمت راست ملاقات می شود .

Postorder : در این روش ، ابتدا گره سمت چپ ، سپس گره سمت راست و در آخر گره ریشه ملاقات می شود .