کتاب ساختمان داده ها و الگوریتم ها در جاوا - اشرفی پیامن

کتاب ساختمان داده ها و الگوریتم ها در جاوا تألیف مهندس نصرت علی اشرفی پیامن توسط انتشارات دانشگاه تربیت معلّم به چاپ رسیده است.

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

این اثر مطالب آموزشی را طی یازده فصل در اختیار خوانندگان قرار می دهد که عبارتند از:

1- الگوریتم های بازگشتی 2- محاسبه پیچیدگی الگوریتم ها 3- آرایه 4- صف 5- پشته 6- الگوریتم های مرتب سازی 7- لیست های پیوندی 8- درخت 9- کاربرد های درخت 10- گراف 11- درهم سازی

 

فهرست

الگوریتم های بازگشتی 1.1. حل نمونه هایی از مسائل بازگشتی مسائل محاسبه ی پیچیدگی الگوریتم ها 2.1. پیچیدگی زمانی 1.2.2: تعریف نمادO 2.2.2. تعریف نمادΩ 3.2.2. تعریف نمادѲ 2.3. معادلات بازگشتی 1.2.3. حل معادلات بازگشتی خطی همگن 2.3.2. حل معادلات بازگشتی خطی ناهمگن 3.3.2. فرمول کلی برای به دست آوردن جواب معادلات بازگشتی خطی 4.3.2. حل بعضی از معادلات بازگشتی غیر خطی مسائل: آرایه 1.3: نحوه ذخیره سازی آرایه ها 1.1.3: آرایه دوبعدی 2.3: کاربرد آرایه ها 1.2.3: ماتریس خلوت 2.2.3: اعداد بزرگ 3.2.3: چند جمله ای ها مساول صف 1.4. تعریف 2.4. صف های اولویت 3.4. پیاده سازی صف Queue1.3.4. کلاس Fullqueue exception2.3.4کلاس Empty queue exception  3.3.4 کلاس مسائل پشته 5.1 تعریف 2.5 کاربردهای پشته 1.2.5 توضیح اگوریتم تبدیل میانوندی به پسوندی 2.2.5 تبدیل عبارت میانوندی به پیشوندی 3.5 پیاده سازی پشته Stack  1.3.5 کلاس Empty stack exceptio  2.3.5کلاس Fullstack exception  3.3.5کلاس مسائل الگوریتم ها ی مرتب سازی 1.6 شرح کامل الگوریتم ها 1.1.6 الگوریتم مرتب سازی حبابی 1.1.1.6 تحلیل پیچیدگی الگوریتم 2.1.1.6 بهینه کردن الگوریتم 1.6 3.1.1.6 تحلیل پیچیدگی الگوریتم 2.1.6 الگوریتم مرتب سازی انتخابی 1.2.1.6 تحلیل پیچیدگی الگوریتم مرتب سازی انتخابی 3.1.6 الگوریتم مرتب سازی درجی 1.3.1.6 تحلیل پیچیدگی 4.1.6 الگوریتم مرتب سازی ادغام 1.4.1.6 تحلیل پیچیدگی الگوریتم 5.1.6 الگوریتم مرتب سازی سریع Place  1.5.1.6 تحلیل الگوریتم 2.5.1.6 تحلیل پیچیدگی الگوریتم مرتب سازی سریع مسائل لیست های پیوندی 1.7 لیست یک پیوندی 1.1.7 تحلیل لیست یک پیوندی 2.1.7 لیست دو پیوندی 3.7 لیست پیوندهای حلقوی 1.3.7 لیست دوپیوندی حلقوی مسائل درخت 1.8 تعاریف 1.1.8 تعریف دیگر درخت دودویی 2.1.8 سطح درخت دودویی 3.1.8 عمیق یک گره از درخت 4.1.8 عمق یا ارتفاع درخت H 5.1.8 حداکثر گره های یک درخت دودویی با ارتفاع گرهN 6.1.8 مینیمم ارتفاع یک درخت دودویی با ارتفاع 7.1.8 ارتفاع یک درخت دودویی برحسب ارتفاع زیر درخت های  چپ و راست آن 8.1.8 رابطه بین تعداد برگ های درخت دودویی و تعداد برگ های زیردرخت های چپ و راست آن 9.1.8 شماره گذاری گره های یک درخت دودویی 10.1.8 درخت دودویی تقریبا کامل 11.1.8 درخت دودویی محض

12. 1.8 پیمایش درخت دودویی

1.2.8 پیمایش میان ترتیب 2.2.8 پیمایش پیش ترتیب 3.2.8 پیمایش پس ترتیب 4.2.8 پیمایش سطحی 1.2.8 تبدیل فرم های مختلف عبارات ریاضی به یکدیگر با استفاده از درخت دودویی مسائل کاربردهای درخت 1.9 درخت جستجویی دودویی Binsearchtree 1.1.1.9 کلاس 1.1.1.9 توضیح کلاس Avl  2.9درخت Avl  1.2.9 تعریف درخت 3.9 دوران 1.3.9 دوران چپ حول یک گره 2.3.9 دوران راست حول یک گره 3.3.9 دوران چپ حول فرزند چپ گره و سپس دوران راست حول خود گره 4.3.9 دوران راست حول فرزند راست گره و سپس دوران چپ حول خود گره 4.9 کد هافمن 5.9 الگوریتم مرتب سازی هیپ 1.1.5.9 درخت هیپ ماکسیمم 2.1.5.9 تحلیل الگوریتم مرتب سازی هیپ 3.5.9 هزینه ساخت درخت هیپ ماکسیمم مسائل گراف 1.10 تعریف گراف 1.1.1.10 سیکل 2.1.1.10 گراف همبند 2.1.10 گراف جهت دار 2.10 نمایش گراف 1.2.10 نمایش ماتریس مجاورتی 2.2.10 لیست های مجاورتی مسائل درهم سازی 1.11 جدول درهم سازی 1.1.11 روش وسط مربع 2.1.11 روش تقسیم 3.1.11 روش تا زدن 4.1.11 روش مبنا 2.11 روش های حل تصادم 1.2.11 ذخیره در اولین مکان خالی بعد از آن 2.2.11 روش زنجیره ای کردن مسائل

برشی از متن کتاب

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

• نویسنده: مهندس نصرت علی اشرفی پیامن
• انتشارات: دانشگاه تربیت معلم