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

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

اسلاید 1: نوع داده هاي انتزاعي Abstract Data Typesساختمان داده ها و الگوريتم‌ها

اسلاید 2: Dataياد آوري: هر برنامه کامپيوتري روي چند “داده” کار مي کند و به اين منظور از چند الگوريتم استفاده مي کند.داده هاي مورد استفاده، انواع مختلفي دارند: int, boolean, String, …نوع داده بيانگر مقادير ممكن براي داده است: {..., -2, -1, 0, 1, 2, ...}, {true, false}با تعيين نوع داده برخي از زبانها مي توانند خطاهاي استفاده از آنها در برنامه را كشف كنند:Type checkingبرخي از اعمال تنها روي انواع خاصي از داده ها قابل استفاده هستندتعيين نوع داده، نحوه نمايش داخلي آن را نيز تعيين مي كند:ميزان و نحوه مديريت حافظه مورد استفاده نوع String با نوع Boolean متفاوت است

اسلاید 3: نوع داده Data Typesنوع داده بيانگر مشخصات زير است:مجموعه مقادير ممكننحوه نمايش، كه براي همه مقادير ممكن يكسان استمجموعه عمليات روي اين داده ها كه به شكل واحد روي همه مقادير ممكن اعمال مي شود

اسلاید 4: نوع داده انتزاعي Abstract Data TypeADT يعني توصيف :داده ها عمليات روي داده هامثال : مجموعه اعداد طبيعي Nداده ها : اعداد طبيعيn=1,2,3,… عمليات: عضويت يک عدد در يک مجموعه n is-in N زير مجموعه : A={n| n =1..1200} اعمال مختلف روي زير مجموعه هااشتراک، اجتماع ، تفاضل متقارن، Cardinality1در ADT نحوه نمايش داخلي داده بوسيله كامپيوتر، مطرح نمي شود

اسلاید 5: نوع داده هاي اوليه در جاواجاوا 8 نوع داده اوليه دارد:booleanchar, byte, short, int, longfloat, doubleهر نوع داده اوليه:مجموعه مقاديري داردنحوه نمايشي داردمجموعه عملياتي داردبرنامه نويس نمي تواند اين مشخصات را تغيير دهد

اسلاید 6: نوع داده هاي اوليه در جاوا

اسلاید 7: مثال 1: اعداد گويايک عدد گويا، به شکل a/b تعريف مي شود که در آن a,b اعدادي صحيح هستند و b صفر نيست.عمليات : چهار عمل اصلي، توان، ريشه و...محدوديت: جذر اعداد گوياي منفي تعريف نشده است. توصيف کامل عمليات نيازمند تعريف دقيق همه اعمال روي داده هاست مثل عمل ضرب براي دو عدد گوياي a1/b1 , a2/b2 چنين تعريف مي شود: a1/b1 * a2/b2 = (a1*a2) / (b1 * b2)

اسلاید 8: توصيف رسمي ADTتوصيف رسمي: توصيف دقيق و بدون ابهامنوع داده هاعمليات : ورودي و خروجي عمليات، الگوريتمشبه کد pseudo codeروشي بيان رسمي ADT با زباني شبيه يکي زبانهاي برنامه نويسيابهام زبان طبيعي را نداردنسبت به فلوچارت انعطاف بيشتري داردپياده سازي آن راحت تر و سريعتر استدر اين درس از شبه کد JAVA استفاده مي کنيم.

اسلاید 9: كلاس هاي جاواكلاس در جاوا يك “نوع داده است”مجموعه مقادير ممكن، اشيائي(Object) از جنس كلاس هستند نمايش داخلي كلاس با استفاده از يك reference به بلوك حافظه كلاس انجام مي گيرددر C++ از Pointer استفاده مي كنيمساختار بلوك حافظه با ويژگيهاي كلاس تعيين مي شوداعمال روي اشيا با متدها (Methods)‌ معرفي مي شوند

اسلاید 10: بيان ADT با شبه کد Javaهر ADT را به شکل زير نمايش مي دهيم :// Comment ..//…Class <adt-name>{<operation 1>….<operation n>//Data section <data 1> ….<data n>}Adt-name نام adt را نشان مي دهد. اين نام بايد مسمي باشد.Data 1..n داده هاي موجود در ADT را نشان مي دهندOperation 1..n عمليات مختلف روي داده ها را نشان مي دهنداز // براي مشخص کردن توضيحات استفاده مي کنيم. ADT بايد به اندازه کافي خوانا و صريح باشد.

اسلاید 11: توصيف داده هاهر قلم داده مورد استفاده در ADT بايد تعريف و دليل استفاده از آن ذکر شود.محدوديت هر قلم داده بايد تعيين شودمثال: اگر داده length براي مشخص کردن طول يک مستطيل در نظر گرفته شده باشد، به شکل زير تعريف مي شود: int length ; // length of the rectangle, length >= 0

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

اسلاید 13: توصيف يک عمل در ADT//General comments//Inputs, Outputs// Pre-condition // Post-condtion <return-type> <operation-name>(<p1>…<pn>) {…. // detailed implementation}

اسلاید 14: ADT اعداد گويا//This ADT represents classic rational numbers// any rational number is a/b in which a and b are// integers and b is non-zero . Class rational { //mult: multiplies two rational numbers and returns result // pre: given r1 , r2, two rational numbers;// post: returns r1 * r2 rational mult(rational r1, rational r2) {rational r ; r.a = r1.a * r2.a ; r.b = r1.b * r2.b ; return r ; }//data section int a ; // a is numerator int b ; //b is denominator , b must be non-zero}

اسلاید 15: مثال 2:آرايهClass Array{Int length ; // length > 0 Member-type Members [1... Length] ;Operations:Create Array Assign: Array[k] = element ;K is an integerelement is an object of element-typeRetrive: element = Array[k];K is an integerelement is an object of element-type//Any other method ?}

اسلاید 16: پياده سازي ADTبراي پياده سازي ADT بايد:يك نمايش داده انتخاب كنيداين نوع نمايش بايد قادر به نمايش تمامي مقادير ممكن باشدبايد private (خصوصي) باشدالگوريتمي براي هر كدام از عمليات انتخاب كنيداين الگوريتم بايد با نحوه نمايش انتخاب شده سازگار باشدتمامي عملياتي كه بعنوان عمليات كمكي استفاده مي شوند، بايد private‌تعريف شوند

اسلاید 17: خلاصهيك نوع داده، مقادير، نحوه نمايش و عمليات روي آنها را توصيف مي كندنوع داده انتزاعي ADT مقادير و عمليات روي آنها را توصيف مي كند و كاري به نحوه نمايش ندارد توصيف رسمي يك ADT با شبه كد يك زبان برنامه نويسي صورت مي گيرد

اسلاید 18: تمرين 2ADT اعداد مختلط را بنويسيد:هر عدد مختلط به شکل a + ib نشان داده مي شود که در آن a ,b دو عدد حقيقي هستند. عمل جمع اعداد مختلط چنين تعريف مي شوند:) a1 + ib1( + (a2 + ib2) = (a1 +a2) + i (b1 + b2 ) ;عمل ضرب چنين تعريف مي شود:(a1 + ib1) * (a2 + ib2) = (a1a2 - b1b2) + i (a1b2+ a2b1)بفرستيد Subjectايميل گروه رياضي : [ds-math-assign02] Subjectايميل گروه كامپيوتر : [ds-cs-assign02]