پاورپوینت ساختمان داده ها در C++

بخشی از پاورپوینت

اسلاید 1 :

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

اسلاید 3 :

فصل اول : مفاهيم اساسي
آشنايي با سيکل زندگي نرم افزار
آشنايي با الگوريتم
اهداف

اسلاید 4 :

1-1 سيکل زندگي نرم افزار
مراحل مختلفي كه در چرخه نرم افزار هستند:
نيازمنديها
تجزيه و تحليل
طراحي
تعريف الگوريتم و برنامه سازي آن
تست برنامه

اسلاید 5 :

1-1 سيکل زندگي نرم افزار-نيازمندي ها
نيازمنديها
تمام پروژه هاي بزرگ برنامه نويسي با مجموعه اي از مشخصات و خصوصياتي که اهداف پروژه را مشخص مي کند، شروع مي شود.
اين نيازمنديها اطلاعاتي را به برنامه نويسان مي دهند(ورودي) و نيز نتايجي را که بايد ايجاد گردد(خروجي) تعيين مي کنند.

اسلاید 6 :

1-1 سيکل زندگي نرم افزار- تحليل
تحليل:
در اين مرحله مساله را به بخشهاي قابل کنترل تقسيم مي کنند.
در تحليل يک سيستم دو شيوه وجود دارد :
1- شيوه از بالا به پايين:با هدف طراحي و توليد طرحي سطح بالا شروع ميشود كه در آن برنامه به بخشهاي قابل مديريت تقسيم ميشود.
2- شيوه از پايين به بالا: روش قديمي و غيرساختيافته است كه تاكيد آن بر مطالعه نكات حساس برنامه نويسي استوار است

اسلاید 7 :

1-1 سيکل زندگي نرم افزار- طراحي
طراحي
اين مرحله ادامه کاري است که در مرحله تحليل انجام مي شود.
طراح سيستم را از دو نقطه نظر بررسي مي کند:
از نظرداده هاي مقصود(data objects) مورد نياز برنامه

از نظر اعمالي که بر روي آنها انجام مي شود. اين ديدگاه به مشخصات الگوريتم ها و فرضيات خط مشي ها ي طراحي الگوريتم نياز دارد.
ايجاد نوع داده مجرد

اسلاید 8 :

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

اسلاید 9 :

1-1 نمودار سيکل زندگي نرم افزار
نيازمنديها
تحليل
طراحي
الگوريتم و کدنويسي
بازبيني

اسلاید 10 :

2-1 تعريف الگوريتم
الگوريتم مجموعه اي از دستورالعمل ها است که
اگر دنبال شوند، موجب انجام عمل خاصي مي گردد

اسلاید 11 :

ورودي: يک الگوريتم مي تواند هيچ يا چندين کميت ورودي داشته باشدکه از محيط خارج تامين مي شود.
خروجي: الگوريتم بايستي حداقل يک کميت به عنوان خروجي داشته باشد.
قطعيت: هر دستورالعمل بايد واضح و بدون ابهام باشد.
محدوديت: اگر دستورالعمل هاي يک الگوريتم را دنبال کنيم ،براي تمام حالات ، الگوريتم بايد پس از طي مراحل محدودي خاتمه يابد.
کارايي: هر دستورالعمل بايد به گونه اي باشد که با استفاده از قلم و کاغذ بتوان آن را با دست نيز اجرا نمود.
2-1 شرايط الگوريتم

اسلاید 12 :

2-1 مثالي از الگوريتم: الگوريتم مرتب سازي
for(i=0 ; i{
Examine list [ i ] to list [n-1] and suppose that the smallest integer is at list [min];
Interchange list [ i ] and list [min];
{

اسلاید 13 :

2-1 الگوريتم بازگشتي
تابع مجموعه ای از دستورات است که تحت یک نام در برنامه تعریف شده است.
توابع میتوانند یکدیگر را فراخوانی نمایند.
توابع مي توانند خودشان را صدا بزنند (بازگشت مستقيم )
همچنین توابع مي توانند توابعي که تابع فراخواننده را صدا ميزنند، احضار نمايند (بازگشتي غيرمستقيم) .

اسلاید 14 :

2-1 مثال الگوريتم جستجوي دودويي تكراري
الگوريتم جستجوي دودويي را بنويسيد.
int binsearch ( int list [ ] ، int x ، int n )
{
/* search sorted array list[0]… list [n-1] for x */
for(int left=0,right=n-1 ; left<=right ; )
{
int middle = ( left + right ) / 2 ;
switch ( COMPARE (x , list [ middle ]))
{
case ‘>’ : left = middle+1; break;
case ‘<’ : right = middle-1; break;
case ‘=’ : return middle; break;
}
}
return -1 ;
}

اسلاید 15 :

2-1 مثال الگوريتم جستجوي دودويي بازگشتي
int binsearch ( int list [ ] ، int x، int left ، int right )
{
/* search list [0] <= list [1] <= … <=list [ n-1 ] for x Return its position if found . Otherwise return -1 */
if (left <= right )
{
int middle = ( left + right ) / 2 ;
switch ( COMPARE (x , list [ middle ]))
{
case ‘>’ :
return binsearch ( list ، x ، middle +1 ، right ) ;
case ‘=‘ :
return middle ;
case ‘<‘ :
return binsearch ( list ، x ، left ، middle -1 ) ;
}
}
return -1 ;
}

اسلاید 16 :

2-1 الگوريتم بازگشتي
مجموعه اي از دستورات مختلف كه عملي منطقي را انجام ميدهند ميتوانند در كنار هم قرارگرفته و تابع را تشكيل دهند
نام تابع و پارامترهاي آن بعنوان دستوري جديد درنظر گرفته ميشوند
با تعيين مشخصات ورودي-خروجي يك تابع ميتوانيم به تابع دسترسي پيدا كنيم از اينرو لازم نيست بدانيم كه تابع چگونه كارش را انجام ميدهد
با داشتن چنين تصويري از تابع، ابتدا تابع احضار ميشود آنگاه اجرا شده و كنترل اجرا به مكان مربوطه در تابع احضار كننده باز ميگردد.
توابع ميتوانند قبل از اتمام كارشان خودشان را احضار كنند (توانمندي لازم براي الگوريتم هاي بازگشتي)

اسلاید 17 :

مثال الگوريتم هاي بازگشتي
بيان معمولي
بيان بازگشتي

اسلاید 18 :

مثال: برنامه مولد جايگشت را بصورت بازگشتي بنويسيد
void perm(char *a,const int k, const int n)
{
/* Generate all the permutations of a[k],…,a[ n-1 ] */
if (k == n-1 )
{
for(int i=0 ; i< n ; i++)
cout<cout<return;
}
for(int i=k; i < n ; i++)
{
//interchange a[k] , a[i]
Interchange(a,k,i);
perm(a,k+1,n);
//interchange a[k] , a[i] again to return the original configuration
Interchange(a,k,i);
}
}

اسلاید 19 :

3-1 آرايه ، ساختار و نوع داده
مجموعه اي از عناصر از يک نوع داده مي باشد

مجموعه اي از عناصر است که لزومي ندارد داده هاي آن يکسان باشد

مجموعه اي از انواع داده (object) و عملکردهايي است که بر روي اين نوع داده ها عمل مي کنند
آرايه
ساختار
نوع داده

اسلاید 20 :

3-1 نوع داده اي مجرد
نوع داده مجرد يا انتزاعي (ADT) که شامل مشخصات داده ها و اعمالي که بر روي آنها انجام مي شود.
جهت جداسازي پياده سازي و نمايش داده ها از يکديگر از ADT استفاده ميشود