آموزش ساختمان داده قسمت سوم

1395/1/23 سعید ضیادید 3696

به نام خدا

سلام عرض می کنم خدمت همه ی شما دوستان عزیز

در خدمت شما هستم با جلسه ی سوم  آموزش  ساختمان داده ها از سری آموزش های برنامه نویسی

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

اصلا نوع داده ی انتزاعی یعنی چی؟ ببینید دوستان ، یک نوع داده ی انتزاعی (Abstract Data Type) نوعی مدل ریاضی برای ساختار های داده ای هست که عملکرد مشابهی دارند یا برای یک یا چند زبان برنامه نویسی مشترک به کار میرن . بنابراین از الان هر وقت در این آموزش ADT رو دیدید ، منظور ما " نوع داده ی انتزاعی " هست . خود کلمه ی "انتزاع" هم دارای معانی مختلفی هست که در علوم کامپیوتر بیشتر به معنی مخفی سازی و کاهش مفاهیم برای افزایش تمرکز روی برخی مفاهیم خاص هست .

پس حالا بیایم ADT مربوط به یک آرایه رو در حالت معمول بررسی کنیم . ما در بررسی ADT مربوط به ارایه ها معمولا با اعمالی که روی آرایه انجام میشه کارداریم . اکثر زبان های برنامه نویسی 3 عملگر استاندارد رو برای آرایه ها تعریف کردن که عبارت هستن از :

1- ایجاد یک آرایه  ی جدید

2- بازیابی یک مقدار

3- ذخیره سازی یک مقدار

 

 

نوع داده ی انتزاعی "آرایه"

در تصویر بالا ، نوع داده ی انتزاعی یک آرایه ی عمومی رو ملاحظه می کنید . همون طور هم که گفتم ما در این سری آموزشی بیشتر روی مفاهیم تمرکز میکنیم ولی اگه بخوایم در برخی موارد از زبان برنامه نویسی استفاده کنیم ، اون زبان برنامه نویسی ،++C (و کمی هم JAVA) خواهد بود .

نوع داده ی انتزاعی رو به شکل یک کلاس معرفی کردیم . اجازه بدید یک توضیح کوچک درباره ی کلاس در زبان ++C بدم :

" کلاس" یکی از مکانیزم های زبان ++C هست که شامل 4 جزء خواهد بود :

1-نام کلاس

2-عضو های داده

3-توابع عضو

4-سطوح دسترسی برنامه (خصوصی-عمومی –محافظت شده)

انشاالله با این مبحث (Class) در سری آموزش های زبان برنامه نویسی ++C که در این کانال هم توسط آقای دادخواه تدریس میشه ، به طور کامل آشنا خواهید شد .

اما برگردیم به همون ADT . در قسمت Public یک "سازنده " تعریف کردیم که میاد و یک آرایه  ی جدید با طول و نوع مناسب ایجاد میکنه . توابع Retrieve و Store هم همون اعمال بازیابی و ذخیره سازی رو انجام میدن . البته این نکته رو باید بگم که تصویر بالا فقط نوع داده ی انتزاعی آرایه رو با مفاهیم زبان C++ بیان میکنه و نه خود آرایه رو . خود آرایه در C++ بسیار راحت و با جزییات بیشتر تعریف میشه . ما در اینجا فقط نوع داده ی انتزاعی آرایه رو با تمرکز بر اعمالی که روی آرایه انجام میشه به طور کلی بررسی کردیم . کاری که انشاءالله برای برخی از ساختار های داده ای دیگر هم انجام خواهیم داد .

همونطور که متوجه شدید ما میتونیم از آرایه ها برای پیاده سازی برخی از انواع داده ها به شکل مطلوب استفاده کنیم . مثلا ذخیره سازی یا تعریف روز های هفته (شنبه ، یکشنبه ،....، جمعه) یا سال های حضور تیم ملی فوتبال ایران در جام های جهانی (1978،1998،2006،2014)

اما الان میخوایم یک ADT برای نمایش و انجام اعمال روی چندجمله ای ها رو بیان کنیم . شکل زیر دو چند جمله ای رو همراه با اعمال جمع و ضرب اونها رو نشون میده :

تصویر زیر هم نوع داده ی انتزاعی چند چمله ای رو نشون میده :

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

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

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

نوع اول : این نوع نمایش ، چند جمله ای رو به شکل زیر تعریف می کنیم :

Private:

int degree ;

float coef [Maxdegree +1];

با این نوع نمایش ساده ، الگوریتم های فوق العاده راحتی برای اعمال جمع و تفریق و ..... در چندجمله ای ها به دست میاد .

نوع دوم : در این نوع نمایش یک تغییر کوچیک میدیم نسبت به نوع قبلی و یک سازنده هم اضافه میکنیم :

Private :

     int degree;

     float  *coef;

Polynomial (int d){

 degree=d;

 coef = new float[degree+1];

}

 

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

پس بهتره در این نوع نمایش ( نمایش سوم) دنبال مکانیزمی باشیم که ضرایب غیر صفر رو ذخیره کنیم . شکل کلی این نوع مایش به صورت زیر هست :

Class Polynominal ;

class term  {

friend Polynominal ;

private :

       float coef ;

       int exp ;

  };

private :

static term termArray [MaxTerms];

static int free;

int Start , Finish;

تصویر زیر ، مثالی مناسب برای این نوع نمایش است . در این نوع نمایش از عناصر start , finish استفاده شده است و A,B دو شی از نوع چند جمله ای هستن .

اما آیا میتونیم بگیم که نمایش نوع سوم از همه بهتره ؟

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

اگر m تعداد جملات غیر صفر موجود در چندجمله ای A و n تعداد جملات غیر صفر موجود در چند جمله ای B باشن ، اون وقت پیچیدگی زمانی الگوریتم  جمع دو چند جمله ای تقریبا از مرتبه ی O(m+n) خواهد بود .

خب در این جلسه با ساختار داده ای آرایه آشنا شدیم . در جلسه ی بعد کاربرد آرایه رو در نمایش و ذخیره سازی ماتریس ها بیان میکنیم و یکسری نکات بیشتر و کاربردی تر درباره ی آرایه ها میگیم و در آخر جلسه ی بعد هم درباره ی نوع داده ی انتزاعی" رشته " صحبت خواهیم کرد .

تا جلسه ی بعدی خدا نگهدار .

کلمات کلیدی