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

صفحه 1:
نوع داده هاي انتزاعي ‎@bstract Daa Types‏ ساختّمان داده ها و الگوریتم‌ها 

صفحه 2:
ياد آوري: هر برنامه كامپيوتري روي چند "داده" کار مي کند و به اين منظور از چند الگوریتم استفاده مي كند. © داده هاي مورد استفاده» انواع مختلفي دارند: ‎.,int, boolean, String = -‏ - نوع داده بیانگر مقادیر ممکن برلي داده است: ‎{true, false} , 4 =‏ ‎e‏ با تعيين نوع داده برخي از زبانها مي توانند خطاهاي استفاده از آنها در ‎Wigs GE ray‏ ‎Dupe chevhiy -‏ - برخي از اعمال تنها روي انواع خاصي از داده ها قابل استفاده هستند ‏تعیین نوع داده» نحوه نمایش داخلي آن را نیز تعیین مي کند: میزان و تحوه مدیریت حافظه مورد استفده نوع ,95 54 ¢ ‎Oi Boolean‏ است 

صفحه 3:
# نوع داده بیانگر مشخصات زیر است: - مجموعه مقادیر ممکن - نحوه نمایش» که براي همه مقادیر ممکن یکسان است - مجموعه عملیات روي این داده ها که به شکل واحد روي همه مقادیر ممكن اعمال مي شود 

صفحه 4:
داده انتزاعي عم ‎@bstruct Duta‏ & ) یعنیتوصیف: - داده ها - عملیات روي داده ها ‎٩‏ مثال : مجموعه اعداد طبيعي ‎D‏ ‏- داده ها : اعداد طبيعيم, 20,6 ... - عملیات: © عضویت یک عدد در یک مجموعه ‎aici‏ ‏#زير مجموعه : ‎=f] 0 =A. OOO}‏ ‎٩‏ اعمال مختلف روي زیر مجموعه ها - اشتراک» اجتماع » تفاضل متقارن» ‎Corder‏ ‏© در “00041 نحوه نمايش داخلي داده بوسيله كامييوترء مطرح نمي شود 

صفحه 5:
نوع داده هاي اولیه در جاوا 9 جاوا 6 نوع داده اولیه دارد: ‎boolean -‏ ‎char, byte, short, int, long -‏ ‎float, double -‏ © هر نوع داده اوليه: - مجموعه مقاديري دارد - نحوه نمايشي دارد - مجموعه عملياتي دارد ‎٩‏ برنامه نویس نمي تواند این مشخصات را تغبیر دهد 

صفحه 6:
نوع داده هاي اوليه در سا ۱87/۰2 oa ‏اا‎ ©) cdot caste boolean true, alse (CN anid &&, ||, ! ‎Oe rr‏ 0 كلمت ‎da ah aad‏ ‎re ‎Le aco er‏ ل ليك كنا 122ل حاص ۳ عاطابول ‎DSN EEN ad‏ ‏مه اس اد ‎ 

صفحه 7:
مثال 0: اعداد گویا © یک عدد گویاء به شکل ماه تعریف مي شود که در آن تاره اعدادي صحیح هستند و «| صفر نیست. ‎٩‏ عملیات : چهار عمل اصليء توان» ريشه و... ‎٩‏ محدودیت: جذر اعداد گوياي منفي تعریف نشده است. ‎٩‏ توصیف کامل عملیات نیازمند تعریف دقيق همه اعمال روي داده هاست مثل عمل ضرب براي دو عدد گوياي 6/۵ , 0/۲0 چنین تعریف مي شود: ‎bE)‏ * 4 ۱ (*60) ع 8/9۵ * ۰0/۲۵ 

صفحه 8:
© توصیف رسمي: توصیف دقیق و بدون ابهام - نوع داده ها - عملیات : ورودي و خروجي عملیات. الگوریتم ‎٩‏ شبه کد ول مرحم - روشي بیان رسمي 00۳) با زباني شبیه يكي زبانهاي برنامه نويسي © ابهام زبان طبيعي را ندارد © نسبت به فلوچارت انعطاف بيشتري دارد @ پیاده سازي آن راحت تر و سریعتر است © در این درس از شبه کد 690268 استفاده مي کنیم. 

صفحه 9:
© كلاس در جاوا يك “نوع داده است” - مجموعه مقادير ممكنء اشيائي(1-ج01) از جنس كلاس هستند - نمایش داخلي کلاس با استفاده از يك بحسم به بلوك حافظه كلاس انجام مي كيرد #در 0++ از ‎Porter‏ استفاده مي کنیم - ساختار بلوك حافظه با ويژگيهاي کلاس تعیین مي شود - اعمال روي اشيا با متدها (علت()) معرفي مي شوند 

صفحه 10:
بیان 9007) با شبه كد مرول سمل نام فی را نشان‌مي‌دهد. لین .هر 6000/۴ را به شکل زیر نمایش مي دهیم : نام بايد مسميياشد. و0 | Weve POT ‏هايموجود در‎ 2212 Data 0 Chis <odborne>{ Ae 0 وموم عملياتمختلفووي دادم ها ‎<pperctica (I>‏ را نشانميدهند از // براي مشخص كردن توضيحات ا استفاده مي كنيم. وم ‎BOD‏ بايد به لندازم كافيخولنا و مه مه ‎aly apie‏ <0 مهل> ‎<dota o>‏ 

صفحه 11:
© هر قلم داده مورد استفاده در 96) باید تعریف و دلیل استفاده از آن ذکر شود. © محدودیت هر فلم داده باید تعیین شود ‎٩‏ مثال: اگر داده »اج براي مشخص کردن طول یک مستطیل در نظر گرفته شده باشد» به شكل زیر تعریف مي شود: ‎fot leas 5 // beogh oP the revtocnde, leak >= O 

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

صفحه 13:
حوس وحمت ‎lBeverd‏ كدوك 0) ركدووا»// I Postooetion <returippe> <ppercive-onve>(<pl>...<pa>) { wee | detailed inoplespectativa } 

صفحه 14:
وسوحاركب لمدصفم جتوصدات جندجو صوص ‎0000/1١‏ كذ "|| ‎a ocd b ore‏ كاعكانب ا جاله صا مجحاميب و بو || ‎WH ictewers ood b ts wozerv‏ { مس 0 تال ‎ced retires‏ وی امججقو سب ولج ‎Thou:‏ ‎I pre: qed rl, rO, woo reavod anvbers;‏ ‎rO‏ * و وس || ) (۲ ام ,۷ اجه ام تسس ما ‎rat r.a* PO. jrb=rb*rOb;‏ ‎retrar‏ ‏1 ‏شوه || وی واه | : ول ‎wnt be werzerv:‏ اي سم موم و : 0 

صفحه 15:
بمب ‎Chess‏ © ‎D‏ > سا : ما و = ‎Dewberype Dewbers (0... Lew] ;‏ - ‎Opersiicas:‏ © ‎Once Cow‏ - : ماه = ‎Bssica: Prray[k]‏ = ‎Kis on ier‏ و ور ما مب سیر و :بط < واه ‎Retive:‏ - سب مط )) و را اه مه یی و ? او ‎ober‏ و۱ - 50 

صفحه 16:
© براي بياده سازي “6004 بايد: 0. يك نمايش داده انتخاب كنيد © اين نوع نمايش بايد قادر به نمايش تمامي مقادير ممكن باشد ۶ باید ورن (خصوصي) باشد . الگوريتمي براي هر کدام از عملیات انتخاب كنيد © اين الگوریتم باید با نحوه نمایش انتخاب شده سازگار باشد * تمامي عملياتي که بعنوان عملیات کمكي استفاده مي شوند؛ ‎Ca private ub‏ 58 

صفحه 17:
# يك نوع داده» مقادیر» نحوه نمایش و عملیات روي آنها را توصیف مي كند © نوع داده انتزاعي “90041) مقادير و عمليات روي آنها را توصیف مي كند و كاري به نحوه نمايش ندارد @ توصيف رسمي يك “90041 با شبه كد يك زبان برنامه نويسي صورت مي كيرد 

صفحه 18:
© 6004 لعداد مختلط را بنويسيد: - هر عدد مختلط به شكل ول + ب نشان داده مي شود که در آن ما, ه دو عدد - عمل جمع اعداد مختلط چنین تعريف مي شوند: ‎(WO +bC) = (eX tu) +1 (LK +bO );‏ + )۳4 +۰( - عمل ضرب چنین تعریف مي شود: (لماعه ‎(ol + Hl) * (GO +O) = (Kho - LILO) +1 (ILO+‏ © بفرستيد - انك ©)ايميل كروه رياضي : ‎[de-wak-assigDO]‏ ‏- )یبیل گروه کامپیوتر : ‎[ever DO]‏ 

نوع داده هاي انتزاعي ‏Abstract Data Types ساختمان داده ها و الگوريتم‌ها Data ‏ ياد آوري :هر برنامه کامپيوتري روي چند “داده” کار مي کند و به اين منظور از چند الگوريتم استفاده مي کند. ‏ داده هاي مورد استفاده ،انواع مختلفي دارند: – – … ,int, boolean, String نوع داده بيانگر مقادير ممكن برا8ي داده است: ‏ ‏ با تعيين نوع داده برخي از زبانها مي توانند خطاهاي استفاده از آنها در برنامه را كشف كنند: – – ‏ {}true, false{ ,}... ,2 ,1 ,0 ,1- ,2- ,... ‏Type checking برخي از اعمال تنها روي انواع خاصي از داده ها قابل استفاده هستند تعيين نوع داده ،نحوه نمايش داخلي آن را نيز تعيين مي كند: – ميزان و نحوه مديريت حافظه مورد استفاده نوع Stringبا نوع Booleanمتفاوت است نوع داده Data Types نوع داده بيانگر مشخصات زير است: – – – مجموعه مقادير ممكن نحوه نمايش ،كه براي همه مقادير ممكن يكسان است مجموعه عمليات روي اين داده ها كه به شكل واحد روي همه مقادير ممكن اعمال مي شود نوع داده انتزاعي Abstract Data Type ADT ي88عنيت888وصيف: – – داده ها عمليات روي داده ها مثال :مجموعه اعداد طبيعي N – – داده ها :اعداد طبيعي…,n=1,2,3 عمليات: عضويت يک عدد در يک مجموعه n is-in N زير مجموعه A={n| n =1..1200} : اعمال مختلف روي زير مجموعه ها – اشتراک ،اجتماع ،تفاضل متقارنCardinality1 ، در ADTنحوه نمايش داخلي داده بوسيله كامپيوتر ،مطرح نمي شود نوع داده هاي اوليه در جاوا جاوا 8نوع داده اوليه دارد: – – – ‏boolean ‏char, byte, short, int, long ‏float, double هر نوع داده اوليه: – – – مجموعه مقاديري دارد نحوه نمايشي دارد مجموعه عملياتي دارد برنامه نويس نمي تواند اين مشخصات را تغيير دهد نوع داده هاي اوليه در جاوا Type Va lues Rep re sent a t io n Op era t io ns boolean t rue, fa l se Sing le byt e &&, ||, ! Two ’s co mpl ement +, -, *, /, o t h e rs Flo a t i n g p o int Two ’s co mpl ement numbers o f wit h exp o nent a nd va rying si zes ma nt i ssa a nd p recisi ons +, -, *, /, o t h e rs ch ar, byt e, Int eg e rs o f sh ort , i nt , va rying si zes l ong fl o at , d o ubl e مثال :1اعداد گويا يک عدد گويا ،به شکل a/bتعريف مي شود که در آن a,b اعدادي صحيح هستند و bصفر نيست. عمليات :چهار عمل اصلي ،توان ،ريشه و... محدوديت :جذر اعداد گوياي منفي تعريف نشده است. توصيف کامل عمليات نيازمند تعريف دقيق همه اعمال روي داده هاست مثل عمل ضرب براي دو عدد گوياي a1/b1 , a2/b2 چنين تعريف مي شود: )a1/b1 * a2/b2 = (a1*a2) / (b1 * b2 توصيف رسمي ADT توصيف رسمي :توصيف دقيق و بدون ابهام – – نوع داده ها عمليات :ورودي و خروجي عمليات ،الگوريتم شبه کد pseudo code – روشي بيان رسمي ADTبا زباني شبيه يکي زبانهاي برنامه نويسي ابهام زبان طبيعي را ندارد نسبت به فلوچارت انعطاف بيشتري دارد پياده سازي آن راحت تر و سريعتر است در اين درس از شبه کد JAVAاستفاده مي کنيم. كالس هاي جاوا كالس در جاوا يك “نوع داده است” – – مجموعه مقادير ممكن ،اشيائي( )Objectاز جنس كالس هستند نمايش داخلي كالس با استفاده از يك referenceبه بلوك حافظه كالس انجام مي گيرد در ++Cاز Pointerاستفاده مي كنيم – – ساختار بلوك حافظه با ويژگيهاي كالس تعيين مي شود اعمال روي اشيا با متدها ( ‌)Methodsمعرفي مي شوند بيان ADTبا شبه کد Java ‏ ‏ ‏ ‏ ‏ Adt-nameن88ام adt 8را ن88شانميدهد .ا8ين ن88ام 8ب888ايد مسميب888اشد. Data 1..nداده 8هايموجود در ADT را ن88شانميدهند Operation 1..nعملياتمختلفروي داده 8ها را ن88شانميدهند از //براي مشخص کردن توضيحات استفاده مي کنيم. ADTب888ايد ب888ه 8ا8ندازه 8ک888افيخ8وا8نا و ص88ريح ب888اشد. هر ADTرا به شکل زير نمايش مي دهيم : // Comment .. …// {>Class <adt-name ><operation 1 …. ><operation n //Data section ><data 1 …. ><data n } توصيف داده ها هر قلم داده مورد استفاده در ADTبايد تعريف و دليل استفاده از آن ذکر شود. محدوديت هر قلم داده بايد تعيين شود مثال :اگر داده lengthبراي مشخص کردن طول يک مستطيل در نظر گرفته شده باشد ،به شکل زير تعريف مي شود: ‏int length ; // length of the rectangle, length >= 0 توصيف عمليات هر عمل نامي دارد .اين نام بايد مسمي باشد. هر عمل تعدادي ورودي و خروجي دارد .قبل از نام هر عمل توضيحاتي شامل بخش هاي زير قرار مي گيرد: – – – – توصيف کلي و صوري عمل نوع و تعداد ورودي هاي عمل و توصيف هر کدام از آنها شرايط ورودي شرايط خروجي ADT يک عمل در8توصيف //General comments //Inputs, Outputs // Pre-condition // Post-condtion <return-type> <operation-name>(<p1>…<pn>) { …. // detailed implementation } ويا888عداد گ8 ا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 } آرايه:2 مثال  Class Array{ – –  Int length ; // length > 0 Member-type Members [1... Length] ; Operations: – – Create Array Assign: Array[k] = element ; K is an integer  element is an object of element-type  – Retrive: element = Array[k]; K is an integer  element is an object of element-type  –  } //Any other method ? پياده سازي ADT ‏ براي پياده سازي ADTبايد: .1 يك نمايش داده انتخاب كنيد ‏ ‏ اين نوع نمايش بايد قادر به نمايش تمامي مقادير ممكن باشد بايد ( privateخصوصي) باشد .2الگور8يتمي براي هر كدام از عمليات انتخاب كنيد ‏ ‏ اين الگوريتم بايد با نحوه نمايش انتخاب شده سازگار باشد تمامي عملياتي كه بعنوان عمليات كمكي استفاده مي شوند، بايد ‌privateتعريف شوند خالصه يك نوع داده ،مقادير ،نحوه نمايش و عمليات روي آنها را توصيف مي كند نوع داده انتزاعي ADTمقادير و عمليات روي آنها را توصيف مي كند و كاري به نحوه نمايش ندارد توصيف رسمي يك ADTبا شبه كد يك زبان برنامه نويسي صورت مي گيرد تمرين 2 ADT ا8عداد مختلط را ب888نويسيد: – – هر عدد مختلط به شکل 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[ :