کد خبر: 4649

تاریخ بروزرسانی : 1400/09/20

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

منابع آزمون دکتری

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

———————–

فهرست:

فصل اول – مفاهیم                                                                                                                                   

ساختار برنامه در C++                                                                                                                                 

دامنه (scope) در C++                                                                                                                                    

دستورات و عملگرهای C++                                                                                                                           

تعریف داده در C++                                                                                                                                    

تخصیص حافظه پویا در C++                                                                                                                        

مشخصات الگوریتم                                                                                                                                      

نکات مهم                                                                                                                                              

فصل دوم – آرایه ها                                                                                                                                

نوع داده مجرد و کلاس C++                                                                                                                        

آرایه به عنوان یک نوع داده انتزاعی                                                                                                               

نوع داده انتزاعی چند جمله­ای                                                                                                                       

ماتریس­های پراکنده (اِسپارس)                                                                                                                     

نمایش آرایه­ها                                                                                                                                          

نوع داده انتزاعی رشته                                                                                                                               

فصل سوم – پشته ها و صف ها                                                                                                                   

الگوها در C++                                                                                                                                         

نوع داده انتزاعی پشته                                                                                                                               

نوع داده انتزاعی صف                                                                                                                                 

مسأله مسیر مارپیچ (MAZING)                                                                                                                 

ارزیابی عبارت­ها                                                                                                                                       

پشته و صف چندتایی                                                                                                                                

فصل چهارم – لیست های پیوندی                                                                                                                

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

نمایش لیست­ها در C++                                                                                                                             

لیست­های حلقوی                                                                                                                                    

پشته­ها و صف­های پیوندی                                                                                                                           

چند جمله­ای­ها                                                                                                                                         

کلاس­های هم­ارزی                                                                                                                                   

ماتریس­های پراکنده                                                                                                                                   

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

فصل پنجم – درختان                                                                                                                             

مقدمه                                                                                                                                                 

درختان دودویی                                                                                                                                      

پیمایش درخت دودویی و تکرارکننده­های درختان                                                                                           

درختان نخی دودویی                                                                                                                               

هرم­ها (HEAPS)]                                                                                                                                  

درختان جستجوی دودویی                                                                                                                        

درختان انتخاب                                                                                                                                     

جنگل­ها                                                                                                                                               

شمارش درختان دودویی                                                                                                                          

فصل ششم – گراف ها                                                                                                                            

نوع دادۀ انتزاعی گراف                                                                                                                               

عملکردهای مقدماتی گراف­ها                                                                                                                     

فصل هفتم – مرتب سازی                                                                                                                       

مرتب­سازی درجی (INSERTION SORT)                                                                                                   

با چه سرعتی می­توانیم عمل مرتب­سازی را انجام دهیم؟                                                                                    

مرتب­سازی ادغام                                                                                                                                    

مرتب­سازی براساس چند کلید (مبنا)                                                                                                              

مرتب­سازی خارجی                                                                                                                                 

فصل هشتم – درهم سازی                                                                                                                      

نوع داده انتزاعی جدول نمادی                                                                                                                     

درهم سازی ایستا                                                                                                                                   

منابع و مآخذ                                                                                                                                                          

 

 

بخش هایی از بسته درسی ساختمان داده ها

 

تعریف: نوع داده مجرد یا انتزاعی (ADT) نوعی داده است که مشخصات اشیاء و مشخصات اعمالی که برروی آنها انجام می­شوند از نمایش اشیاء و پیاده­سازی آن اعمال کاملاً متمایز می­باشد.

در سراسر این بسته، بر تفاوت بین مشخصات و پیاده­سازی تأکید خاصی شده است. برای انجام این موضوع، کار خود را با تعریف ADT شیء مورد مطالعه شروع می­کنیم. بدین ترتیب خوانند می­تواند بدون درگیر شدن با پیچیدگی نمایش یا پیاده­سازی واقعی عملکردها به عناصر اصلی اشیاء دست یابد. هنگامی که ADT کاملاً تشریح شد، مبحث نمایش و پیاده­سازی را مطرح می­­کنیم. این مباحث در مطالعه ساختمان داده­ها از اهمیت ویژه­ای برخوردار است. برای رسیدن به چنین هدفی، نشانه­گذاری را برای بیان یک ADT معرفی می­کنیم. این نشانه­گذاری کاملاً از قواعد زبان C++ مستقل است. بعداً مشاهده خواهید نمود که چگونه قواعد کلاس C++ را برای بیان ADT بکار می­بریم.

مثال: 1-1: [نوع داده انتزاعی اعداد طبیعی]: بعنوان اولین مثال ADT، لازم است زمان بیشتری را صرف توضیح این نشانه­گذاری کنیم. ADT شماره 1-1 شامل تعریف ADT اعداد طبیعی است. تعریف با نام نوع داده انتزاعی شروع می­شود. این تعریف از دو بخش مهم و اصلی تشکیل شده است: اشیاء و توابع. در این مثال، اشیاء اعداد صحیح هستند که هیچ اشاره صریحی به نمایش آنها نخواهیم داشت. تعاریف توابع تا حدی پیچیده­تر هستند. در ابتدا تعاریف از دو نماد x و y برای نمایش دو عضو مجموعه اعداد طبیعی استفاده می­کنند. TRUE و FALSE عناصر مجموعه مقادیر بولی هستند. علاوه بر این، تعریف از توابعی که بر روی مجموعه اعداد صحیح مانند جمع، تفریق، تساوی و کمتر از، تعریف شده است استفاده می­کند. این مسئله بیانگر این واقعیت است که برای تعریف یک نوع داده، ممکن است نیازمند استفاده از عملکردهای نوع داده دیگر نیز باشیم.

برای هر تابع، نوع نتیجه و تعریف آن را در سمت راست نام تابع می­آوریم. نماد ترکیبی “::=” باید ”به صورت … تعریف می­شود” خوانده شود.

اولین تابع، Zero، فاقد هرگونه آرگومانی است و عدد طبیعی صفر را باز می­گرداند. تابع Successor (x) در دنباله اعداد طبیعی عدد طبیعی بعد از x را برمی­گرداند. توجه کنید که اگر در این دنباله عدد بعدی وجود نداشته باشد، یعنی اگر مقدار x برابر با MAXINT باشد، Successor را طوری تعریف می­کنیم که MAXINT را بازگرداند. بعضی از برنامه­نویسان ترجیح می­دهند در چنین حالتی، Successor یک پیام خطا بازگرداند که البته این توصیه هم کاملاً مجاز و منطقی می­باشد. در اینجا توابع دیگر Add و Subtract هستند. آنها هم ممکن است یک پیغام خطا بازگردانند، هرچند در اینجا ترجیح می­دهیم عنصری از مجموعه NaturalNumber  را برگردانیم.□

اکنون مشاهده می­کنیم که قوانین انتزاع (تجرد) و مخفی­سازی داده­ها چگونه در ساختن برنامه­هایی با طراحی مناسب به طور مؤثر به ما کمک می­کنند.

1) ساده­سازی فرآیند طراحی و تولید نرم­افزار: در حقیقت مزیت مهم انتزاع داده­ها این است که تجزیه کار پیچیده تولید یک سیستم نرم­افزاری به تعدادی زیر وظیفه ساده­تر را آسان می­کند. مسئله زیر را در نظر بگیرید: مسئله­ای به یک برنامه­نویس یا به یک تیم از برنامه­نویسان واگذار شده است. فرض کنید با مرور از بالا به پایین این مسئله تصمیم بر این شده است که سه نوع داده A، Bو C به همراه تعدادی دستور اضافی (که ما آنها را در اینجا چسب می­نامیم) استفاده شود. این دستورهای اضافی برای سهولت ارتباط بین این سه نوع، در نظر گرفته شده­اند. همچنین فرض کنید خصوصیات هر نوع داده در ابتدا مشخص شده است، به عبارت دیگر، اعمالی که نوع داده باید پشتیبانی کند کاملاً مشخص شده است.

ADT Natural Number is

Objects: An ordered sybrange of the integers starting at zero and ending at the maximum integer (MAXINT) on the computer.

Functions:

For all x, y  Natural Number; TRUE, FALSE  Boolean

And where +,-,<,==<and= are the usual integer operations

Zero (): Natural Number                      ::= 0

IsZero (x): Boolean                                ::= if (x==0) IsZero= true

                                                                        Else IsZero = false

Add (x, y): Natural Namber                      ::= if (x+ y<= MAXINT) Add= x+ y

                                                                             Else Add=MAXINT

Equal (x, y): Boolean                                  ::= if (x== y) Equal= TRUE

                                                                            Else Equal= FALSE

Successor (x): Natural Number                ::= if (x== MAXINT) Successor= x

                                                                            Else Successor = x+ 1

Subtract (x, y): Natural Number              ::= if (x< y) Sybtract=0

                                                                             Else Subtract= x- y

End Natural Number

ADT شماره1-1 : نوع داده انتزاعی Natural Number

الف) سناریوی 1- تیمی متشکل از چهار برنامه­نویس: زیر وظیفه­ها را می­توان به صورت زیر بین اعضاء تیمی متشکل از چهار برنامه­نویس تقسیم کرد. هر یک از سه نوع داده به یک برنامه­نویس واگذار می­شود. کار هر برنامه­نویس پیاده­سازی نوع داده خودش بر طبق مشخصاتی است که قبلاً در مورد آن توافق شده است. چهارمین برنامه­نویس، چسب (glue) را با این فرض که نوع داده­ها واقعاً بر طبق مشخصات پیاده­سازی شده­اند، پیاده­سازی می­کند. هیچ یک از برنامه­نویس­ها نیاز نیست بداند سایر برنامه­نویسان چگونه بخش مربوط به خود را پیاده­سازی می­کنند. بنابراین، هر برنامه­نویس می­تواند حواس خود را منحصراً به کد بخش خود معطوف کند بدون هیچگونه نگرانی راجع به این که دیگران چه می­کنند و چگونه ممکن است به آنچه او انجام می­دهد اثر بگذارند.

ب) سناریوی 2- یک برنامه­نویس: در اینجا، انتزاع داده­ها به برنامه­نویس کمک می­کند تا مواردی که در هر زمان نیاز به نگهداری آنها در حافظه خود دارد را کاهش دهد. در این مثال، برنامه­نویس هر نوع داده را یکی یکی با توجه به مشخصات آنها پیاده­سازی می­کند. بنابراین وقتی که برنامه­نویس نوع داده A را پیاده­سازی می­کند هیچگونه نگرانی راجع به نوعهای داده B و C و چسب ندارد. بعد از اینکه هر کدام از انواع داده به تنهایی پیاده­سازی شدند، برنامه­نویس می­تواند توجه خود را به چسب معطوف کند. در اینجا وی دیگر کاری به اینکه چگونه آن سه نوع داده را پیاده­سازی کرده، ندارد بلکه باید به چگونگی استفاده عملکردها برروی آنها دقت کند تا به اهداف خواسته شده برسد.

2) آزمایش و رفع اشکال: شکستن یک برنامه (وظیفه) پیچیده به تعدادی زیر برنامه (زیروظیفه) ساده­تر، امتحان و رفع اشکال برنامه را نیز ساده­تر می­سازد. در مثال بالا، هر نوع داده می­تواند به طور جداگانه امتحان و رفع اشکال شود. بعد از اینکه هر نوع داده آزمایش و رفع اشکال شد، تمام برنامه را می­توان آزمایش کرد. اگر خطایی در این مرحله پیدا شود احتمال اینکه این خطا از ساختار داده­های A، B و C  بسیار کم است، زیرا همه آنها قبلاً آزمایش شده­اند. بنابراین خطا به احتمال زیاد مربوط به چسب است اکنون این حالت را با حالتی مقایسه کنید که می­خواستیم این اشکالات را در برنامه­ای که در آن انتزاع داده­ها استفاده نشده بود  پیدا کنیم. به سادگی دیده می­شود که به کار گرفتن انتزاع داده­ها در توسعه نرم­افزارها، کارآیی آزمایش و رفع خطا را بسیار افزایش می­دهد.

3) قابلیت استفاده مجدد: تجرد و مخفی­سازی داده­ها باعث ایجاد ساختمان داده­هایی می­شود که به صورت نهادهای مجزا از یک سیستم پیاده­سازی می­شود. این امر کار استخراج کدهای یک ساختمان داده و عملکردهای آن از یک سیستم نرم­افزاری و استفاده آن در یک سیستم دیگر را نسبت به حالتی که این ساختمان­ها به صورت پیچیده همراه با سیستم اصلی پیاده­سازی شده باشند، را ساده­تر می­سازد. بعداً روش­های دیگر C++ برای افزایش قابلیت استفاده مجدد را توضیح خواهیم داد.

ساختار برنامه در C++

مانند C، یک برنامه C++ معمولاً در بیشتر از چندین فایل بسط پیدا می­کند. دو نوع فایلی که درC++ استفاده می­شوند: فایل­های سرآمد (Header files) و فایل­های برنامه (Source files) هستند. فایل­های سرآمد پسوند h. دارند و برای ذخیره کردن تعاریف (اعلان­ها) بکار برده می­شوند. فایل­های برنامه برای ذخیره­سازی دستورات و کد برنامه C++ استفاده می­شوند. پسوندی که برای فایل­های برنامه بکار برده می­شود بستگی به نوع کامپایلر دارد. ما از پسوند C. برای فایل­های برنامه استفاده می­کنیم. فایل­های سرآمد با استفاده از دستور پیش­پردازنده #include در فایل مطلوب گنجانده می­شوند.

قبل از این که یک برنامه C++ بتواند اجرا شود، فایل­های برنامه آن باید هر کدام به صورت جداگانه کامپایل شوند، به یکدیگر متصل (link) و سپس بارگیری (load) شوند. چون یک برنامه C++ معمولاً دارای تعداد زیادی فایل برنامه و فایل سرآمد است، این امکان وجود دارد که یک فایل سرآمد چندین بار در برنامه گنجانده شود که باعث خطای کامپایل می­شود. برای این که مطمئن شویم که یک فایل سرآمد دوبار گنجانده نمی­شود، مندرجات آن را در بین دستورات پیش­پردازنده زیر قرار می­دهیم.

#ifndef        FILENAME_ H

# define      FILENAME_H

//مندرجات یک فایل سرآمد در اینجا قرار می­گیرد

.

.

.

#endif

نتیجه دیگر استفاده از چندین فایل برنامه این است که فرآیند تایپ دستورات کامپایل هر بار که برنامه را تغییر می­دهیم و دوباره کامپایل می­کنیم نسبتاً خسته­کننده می­شود. برای اجتناب از این کار خسته­کننده، پیشنهاد می­کنیم از امکان make در UNIX  یا معادل آن برای نگهداری (ادامه) یک برنامه C++ استفاده کنیم. Make علاوه بر کاهش زحمت نوشتن دستورات کامپایل، فایل­هایی که تغییرات اعمال شده تأثیری بر آنها نگذاشته را دوباره کامپایل نمی­کند و در نتیجه زمان کمتری صرف می­شود.

دامنه (scope) در C++

سؤال دیگری که در نتیجه استفاده از چندین فایل در یک برنامه ساده به وجود می­آید در مورد قابلیت رویت یک متغیر است که در یک فایل تعریف شده و در فایل­های دیگر نیز از آن استفاده می­شود. برای این منظور نگاه کوتاهی به دامنه برنامه در C++ می­اندازیم. متن یک برنامه C++ می­تواند در یکی از چهار دامنه زیر باشد:

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

دامنه تابع: برچسب­ها در هر جای تابعی که در آن تعریف شده­اند می­توانند مورد استفاده قرار گیرند. فقط برچسب­ها هستند که دامنه تابعی دارند. از آنجایی که برچسب­ها فقط برای مقصد عبارت goto مورد استفاده قرار می­گیرند؛ و از آنجایی که از عبارت goto به دلیل اینکه برنامه را را غیر ساخت یافته می­کند استفاده نمی­کنیم، با این نوع دامنه برنامه، کاری نخواهیم داشت.

دامنه محلی: نامی که در یک بلاک تعریف می­شود متعلق به دامنه محلی است که شامل آن بلاک می­باشد. این نام همچنین می­تواند توسط زیربلاک­های موجود در بلاکی به کار گرفته شود که در آن تعریف شده است.

دامنه کلاس: تعاریف (اعلان­های) واقع در تعیف یک کلاس به دامنه کلاس تعلق دارند. هر کلاس نشان­دهنده یک دامنه کلاس مجزا است. کلاس­ها را با ذکر جزئیات بیشتر در فصل دوم بررسی خواهیم کرد.

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

اگر نام یک متغیر محلی در یک بلاک همنام با یک متغیر سراسر باشد و بخواهیم از متغیر سراسری در آن بلاک استفاده کنیم، چه باید کرد:

راه حل:   از عملکرد دامنه :: برای دستیابی به متغیر سراسری استفاده کنید.

یک متغیر سراسری در file 1.C تعریف شده است اما در file 2.C مورد استفاده قرار گرفته است.

چگونه این متغیر سراسری را در file 2.C اعلان کنیم؟ اگر متغیر سراسری را به همان صورت تعریف نکنیم پیغام «تعریف نشده است!» را می­دهد.

راه حل:   از کلمه کلیدی extern برای اعلان متغیر در file 2.C استفاده کنید.

فرض کنید در هر دو فایل file1.C و file 2.C برنامه، یک متغیر سراسری با نام یکسان تعریف شده است؛ حال آن که این دو متغیر سراسری به عنوان دو نهاد متفاوت در نظر گرفته شده­اند. چگونه برنامه را بدون تغییر نام متغیر سراسری در یکی از فایل­ها می­توانیم کامپایل کنیم؟

راه حل:   از کلمه static برای تعریف متغیر در هر دو فایل استفاده کنید.

برای جزئیات بیشتر، به یکی از متون مقدماتی C++ که در بخش منابع در انتهای این فصل نام برده شده­اند، مراجعه کنید.

دستورات و عملگرهای C++

دستورات C++ همان قواعد و معانی دستورات C را دارند. دستورات C++ را بعداً در همین فصل در بخش “تحلیل کارایی و ارزیابی برنامه” مختصراً مرور می­کنیم.

عملگرهای C++ نیز به جز دو استثنای new و delete عیناً همان عملگرهای C هستند. New و delete را به هنگام توضیح مدیریت حافظه پویا در C++ مختصراً بررسی خواهیم کرد. تفاوت دیگر این است که C++ از عملگرهای انتقال به چپ (>>) و انتقال به راست (>>) برای ورودی و خروجی استفاده می­کند. این عملگرها را نیز مختصراً موقع بررسی ورودی/ خروجی در C++ مرور می­کنیم. یک تفاومت مهم C و C++ این است که در C++ اضافه بار عملگر (operator overloading) مجاز است؛ بدین معنی که یک عملگر می­تواند بسته به نوع عملوندهای بکار برده شده دارای چندین عملکرد متفاوت باشد. از این گذشته این عملکردها می­توانند توسط برنامه­نویس تعریف شوند.

تعریف داده در C++

یک تعریف (اعلان) داده، انتساب یک نوع داده به یک نام است. حال انواع راه­های تعریف داده در C++ را بررسی می­کنیم. تمامی این روش­های تعریف داده بجز نوع مرجع در C نیز موجودند.

مقادیر ثابت: شامل الفاضی مانند ‘a’5 یا 4.3 هستند.

متغیرها: نمونه­هایی از انواع داده هستند که مقدارشان در حین اجرای برنامه قابل تغییر است.

متغیرهای ثابت: متغیرهایی هستند که در حین اجرای برنامه نمی­توان به آنها مقداری نسبت داد. بنابراین، باید مقداردهی اولیه شوند؛ به این معنی که محتوای آنها وقتی که تعریف می­شوند باید یک مقدار مشخص بگیرد. نوع ثابت با اضافه کردن کلمه کلیدی const به ابتدای دستور اعلان، تعریف می­شود (به عنوان مثال، const int MAX= 500;).

انواع شمارشی: یک روش دیگر برای تعریف سری­هایی از اعداد ثابت صحیح است. همچنین بدین وسیله می­توان انواع داده جدیدی با دادن یک نام به نوع شمارشی ایجاد کرد:

Enum Boolean {FALSE , TRUE};

FALSEو TRUE  ثابت­های صحیح از نوع منطقی (Boolean) هستند. مقادیر آنها به طور پیش­فرض به ترتیب برابر 0 و1 است.

اشاره­گرها: آدرس اشیاء را در خود نگهداری می­کنند، به عنوان مثال

در اینجا np به عنوان اشاره­گری به عدد صحیح تعریف شده و سپس آدرس متغیر صحیح i در آن قرار می­گیرد. بنابراین، اکنون np اشاره­گری است به عدد صحیحی که در متغیر i ذخیره شده است (در اینجا عدد 25).

مشاوره برای آزمون دکتری

برای مشاوره اینجا بزنید

خدمات کنکور دکتری 
معرفی موسسات آموزشی آزمون دکتری
0 0 رای ها
امتیاز بدهید
guest
0 نظرات
بازخورد (Feedback) های اینلاین
مشاهده همه دیدگاه ها
0
افکار شما را دوست داریم، لطفا با ما در میان بگذارید.x