ساختمان داده ها و الگوریتم ها (JAVA Collections Framework)

ساختمان داده ها و الگوریتم ها (JAVA Collections Framework)

اسلاید 1: JAVA Collections Framework Set Interfaces & Implementationsساختمان داده ها و الگوريتم ها

اسلاید 2: CollectionCollection : دسته اي از اشياء هم نوع{ 1و و2و 2و3و4و4و5و5} ، روزهاي هفته عمليات روي Collectionمرتب سازيجستجوحذف و اضافه نمودن اعضاذخيره و بازيابي Storage/Retrieve

اسلاید 3: مزاياي استفاده از Collectionsکاهش برنامه نويسيافزايش کيفيت و سرعت برنامه هاارتباط آسانتر نرم افزارهاي مختلفکاهش زمان يادگيري توابع و متدهاي لازم کاهش زمان طراحي توابع و متدهاي جديدامکان استفاده مجدد از نرم افزارهاي مبتني بر Collections Framework

اسلاید 4: JAVA Collections FrameworkJAVA Collections Framework: مجموعه ابزارها، قراردادها و چارچوبهاي يکسان براي پياده سازي انواع مجموعه هاي پوياStack, queue, list, hash table, mapCollections FrameworkInterfacesAbstract Data Type Representation of CollectionsImplementationJAVA class definition of the ADT ‘sAlgorithmsHow to sort, search ..?

اسلاید 5: InterfaceInterface == ADTقراردادهايي براي نحوه دسترسي به مجموعه پويانحوه پياده سازي اين قرار دادها در Interface ذکر نمي شودمثال: Stack ADT ساختمان داده پشته را تعريف مي کند. داده هاي Stack : آرايه اي از اعضاعمليات روي Stack :حذف و اضافه نمودن اعضا، بررسي پر يا خالي بودن Stack و...JAVA Collections Framework چندين Interface‌براي پشتيباني ساختمان داده هاي معروف تعريف مي کند

اسلاید 6: Core Collection Interfaces‍Collection : مجموعه از اشيا هم نوع تمام عملياتي که روي دسته اي از اشيا به صورت عام قابل انجام است، در Collection تعريف مي شودانواع خاص تر مجموعه هاي پويا، از Collection ارث مي برندMap : تابع ( به مفهوم رياضي)‌را تعريف مي کندهر عضو دامنه به يک و فقط يک عضو برد اختصاص مي يابد.

اسلاید 7: Collection هاي خاصSet: يک مجموعه به مفهوم رياضي را تعريف مي کندعضو تکراري در اين Collection وجود نداردSortedSet: نوع خاصي از Set است که اعضاي به صورت مرتب قرار گرفته اند. الگوريتم هاي جستجو روي اين مجموعه ها، بسيار سريعتر از مجموعه هاي نا مرتب کار مي کنند.List : دسته اي از اشياء به صورت مرتب است. برخلاف Set در list مي توان عضوي تکراري داشت

اسلاید 8: queuequeue (صف)ساختار داده اي است که در آن تريب دسترسي به اعضا، با ترتيب ورود اعضا به queue معين مي شودهر عضوي که زودتر وارد queue زودتر در دسترس قرار مي گيرداين ساختار First in First Out ‌ است

اسلاید 9: Collection Interfacepublic interface Collection<E> extends Iterable<E> { // Basic operations int size(); boolean isEmpty(); boolean contains(Object element); boolean add(E element); //optional boolean remove(Object element); //optional Iterator<E> iterator(); // Bulk operations boolean containsAll(Collection<E> c); boolean addAll(Collection<E> c); //optional boolean removeAll(Collection<E> c); //optional boolean retainAll(Collection<E> c); //optional void clear(); //optional // Array operations Object[] toArray(); <T> T[] toArray(T[] a);}

اسلاید 10: Set Interfacepublic interface Set<E> extends Collection<E> { // Basic operations int size(); boolean isEmpty(); boolean contains(Object element); boolean add(E element); //optional boolean remove(Object element); //optional Iterator<E> iterator(); // Bulk operations boolean containsAll(Collection<?> c); boolean addAll(Collection<? extends E> c); //optional boolean removeAll(Collection<?> c); //optional boolean retainAll(Collection<?> c); //optional void clear(); //optional // Array Operations Object[] toArray(); <T> T[] toArray(T[] a);}

اسلاید 11: Set ImplementationHashSet : اعضاي يك مجموعه را در HashTable نگهداري و مديريت مي كند. ازنظر كارايي، HashSet بهترين پياده سازي است .اين روش ترتيب خاصي روي اعضا اعمال نمي كندTreeSet : اعضاي مجموعه را به صورت مرتب در يك Red-Black Tree نگهداري مي كندكندتر از HashSet عمل مي كند اما ترتيب اعضا را حفظ مي كندLinkedHashSet اعضاي مجموعه را در يك HashTable مجهز به Linked List نگهداري مي كند.تريب اعضا، بر اساس ترتيب اضافه شدن به مجموعه تعيين مي شود

اسلاید 12: مثال 1: مجموعه اي از رشته ها Set<String> s = new HashSet<String>(); for (String a : args) if (!s.add(a)) System.out.println(a);System.out.println(s.size() + distinct words: + s);

اسلاید 13: مثال 2 : تفاضل متقارنSet <String> s1= new HashSet<String>() ;Set <String> s2 = new HashSet<String>() ; Set <String> union = new HashSet<String>(s1);union.addAll(s2) ; Set <String> inter = new HashSet<String>(s1);Inter.retainAll(s2) ; Set <String>diff = new HashSet<String>(union);Diff.removeAll(inter);

اسلاید 14: تمرينبا استفاده از Set و يكي از پياده سازي هاي آن ، برنامه اي بنويسيد كه آرايه اي از رشته ها را دريافت كرده و عناصر غير تكراري آن را چاپ كندمهلت ارسال : تا پايان خرداد