پیش‌گفتار مؤلف
در مورد داده‌ساختارها و طراحی الگوریتم‌ها کتاب‌های زیادی به‌زبان فارسی نوشته یا ترجمه شده است. اما اغلب این کتاب‌ها یا بیش‌تر به بیان مفاهیم داده‌ساختارها می‌پردازند یا تأکید خود را به طراحی الگوریتم‌ها معطوف می‌کنند. یکی از هدف‌های این کتاب، تلفیق این دو موضوع با هم در قالب یک کتاب پایه است. در این کتاب ضمن آن‌که می‌خواهیم شما را با اکثر مطالب داده‌ساختارهای کامپیوتر، در سطح پایه و پیشرفته آشنا کنیم، در همه‌ی مراحل نگاهی الگوریتمی به موضوعات مورد بحث داریم.
کار تهیه‌ی محتوای این کتاب را از سال 1374 و با تهیه‌ی جزوه‌هایی از مطالبی که در آن‌زمان تدریس می‌کردم آغاز نمودم. این مطالب را به تدریج با تدریس درس‌هایی در دانشکده‌ی مهندسی کامپیوتر دانشگاه صنعتی شریف، چون «روشهای حل مسئله»، «ساختمان داده‌ها»، «ساختمان داده‌ها و الگوریتم‌ها»، «طراحی و تحلیل الگوریتم‌ها»، «مبانی علم کامپیوتر 1 و 2» تکمیل، و از آنها دو جزوه‌ی درسی تهیه کردم.
حدود 10 سال پیش تصمیم گرفتم این جزوه‌ها را که بی‌غلط هم نبودند، به دو کتاب تبدیل کنم، اما هرگز فکر نمی‌کردم که تهیه‌ی اولین کتاب از این مجموعه بیش از 10 سال به‌طول انجامد. طی دو سال اخیر ساعت‌های بسیار زیادی بر روی این کتاب کار کرده‌ام و به‌مرور، این کتاب به‌عنوان یک محصول مهم از زندگی علمی‌ام درآمد و تکمیل آن به‌صورت یک کتاب درسی کامل و منسجم، شامل تمرین‌ها و پروژه‌های مناسب یکی از هدف‌هایم شد.
نقش المپیاد کامپیوتر در تکمیل محتوای این کتاب انکار‌ناپذیر است. 18 سال خدمت در المپیاد کامیپوتر ایران و سروکار داشتن با دانش‌آموزان و دانشجویان خوش‌فکر و تیزهوشی که درگیر این المپیاد بودند، به من نکات بسیاری آموخته است. برخی از ایده‌های نو در این کتاب و تعدادی از تمرین‌ها (اکثر تمرین‌های فصل 2) و پروژه‌ها، حاصل این تعامل است.
در این کتاب، برخی از تمرین‌ها که مشکل‌ترند با علامت ستاره(*) و آن‌هایی که بسیار مشکل هستند با علامت دوستاره (**) مشخص شده‌اند. من سال‌هاست که این کتاب را تقریباً به‌طور کامل، در درسی به‌همین‌نام تدریس می‌کنم. این اولین درسی است که دانشجویان رشته ی مهندسی کامپیوتر، پس از گذراندن دروس «مبانی کامپیوتر» و «ساختمان‌های گسسته» می‌گیرند و به‌طور جدی با این مفاهیم آشنا می‌شوند. این کتاب برای همه‌ی دانشجویان رشته‌های مهندسی و علوم کامپیوتر و همچنین، دانش‌آموزانی که خود را برای ورود به دوره‌های المپیاد کامپیوتر آماده می‌کنند، مناسب خواهد بود.
به‌زودی اسلایدهایی را که برای آن تهیه کرده‌ام در وبگاهی که به‌منظور پشتیبانی از کتاب توسط انتشارات فاطمی طراحی و راه‌اندازی خواهد شد در اختیار علاقه‌مندان قرار خواهم داد. از خوانندگان محترم تقاضا می‌کنم اشکال‌های احتمالی کتاب را از طریق همین وبگاه با من در میان بگذارند.
دربارۀ کتاب
این کتاب با نگاهی الگوریتمی مطالب مربوط به داده ساختاری کامپیوتری را، هم در سطح پایه و هم پیشرفته، ارائه می کند. از این رو، از همان ابتدا به مبانی طراحی الگوریتم ها می پردازد و ترکیب مناسبی از داده ساختارها و الگوریتم هاست. این کتاب که بخشی از آن سال ها به عنوان جزوۀ درسی در دانشگاه صنعتی شریف تدریس شده است، می تواند به عنوان کتاب اصلی در اولین درسی که دانشجویان رشته های مهندسی و علوم کامپیوتر در این زمینه می گیرند، و در برنامۀ مصوب به نام ساختمان داده و الگوریتم ها یا ساختمان داده ها آمده است، استفاده شود. این کتاب حاوی 128 شبه کد، 165 شکل، بیش از 330 تمرین و 15 پروژۀ برنامه نویسی است و حاصل سال ها تجربۀ تدریس مؤلف است. استفاده از این کتاب علاوه بر دانشجویان، برای دانش آموزانی که خود را برای ورود به دوره های المپیاد کامپیوتر آماده می کنند مفید خواهد بود.
دربارۀ مؤلف
دکتر محمد قدسی در سال 1331 در شهر ملایر متولد شد. دیپلم خود را از دبیرستان علوی در تهران گرفت و لیسانس خود را در سال 1354 در رشتۀ مهندسی برق از دانشگاه صنعتی شریف اخذ نمود. سپس برای ادامۀ تحصیل به دانشگاه کالیفرنیا، برکلی در آمریکا رفت و در سال 1356 فوق لیسانس خود را در رشتۀ مهندسی برق و علم کامپیوتر گرفت. در همان سال به ایران بازگشت و عضو هیأت علمی دانشگاه صنعتی شریف و مربی دانشکدۀ ریاضی و علوم کامپیوتر آن دانشگاه شد. در سال 1363 جهت ادامۀ تحصیل مجدداً به آمریکا رفت و در سال 1368 دکترای خود را در علم کامپیوتر از دانشگاه ایالتی پنسیلوانیا گرفت. از آن سال تاکنون عضو هیأت علمی دانشکدۀ مهندسی کامپیوتر دانشگاه صنعتی شریف است و از سال 1384، استاد تمام این رشته است. علاوه بر سمت‌های علمی و اجرایی فراوان، او از سال 1371 رئیس کمیتۀ ملی المپیاد کامپیوتر در کشور است، و از سال 1378 مسابقۀ برنامه‌نویسی دانش‌جویی ای‌سی‌ام را در ایران آغاز کرد و سرپرست مسابقۀ منطقه‌ای ای‌سی‌ام در تهران است.
فهرست مطالب:
پیش گفتار مؤلف
۱ معرفی
۱-۱ یک مثال: برنامه‌ریزی چراغ‌های راهنما
۱-۱-۱ یک راه‌حل حریصانه برای مسئله
۱-۱-۲ داده‌های مسئله
۱-۲ گونه‌های مختلف داده
۱-۲-۱ داده‌گونه‌ی انتزاعی
۱-۲-۲ داده‌ها در زبان‌های شیءگرا
۱-۳ زبان برنامه‌نویسی استفاده شده در این کتاب
تمرین‌های فصل ۱
پروژه‌های برنامه‌نویسی فصل ۱
۲ مبانی استقرا و شمارش
۲-۱ استقرای ریاضی
۲-۱-۱ استقرای ضعیف
۲-۱-۲ استقرای قوی
۲-۱-۳ مثال‌هایی از استقرا
۲-۱-۴ خطاهای معمول در اثبات با استقرا
تمرین‌های بخش ۲-۱
۲-۲ مبانی روشهای شمارش
۲-۲-۱ ترتیب و ترکیب
۲-۲-۲ ترتیب دوری و حلقوی
۲-۲-۳ تناظر یک‌به‌یک
۲-۲-۴ مسئله‌های توپ و ظرف
۲-۲-۵ شمول و عدم شمول
۲-۲-۶ اصل لانه‌کبوتری
تمرین‌های بخش ۲-۲
۳ روشهای تحلیل الگوریتم‌ها
۳-۱ زمان اجرای برنامه‌ها
۳-۱-۱ مثال: مرتب‌سازی درجی
۳-۱-۲ مثال: مرتب‌سازی درجی دودویی
تمرین‌های بخش ۳-۱
۳-۲ پیچیدگی الگوریتم‌ها
تمرین‌های بخش ۳-۲
۳-۳ تابع‌های رشد
تمرین‌های بخش ۳-۳
۳-۴ روشهای تحلیل الگوریتم‌ها
۳-۴-۱ تحلیل الگوریتم‌های ترتیبی
تمرین‌های زیربخش ۳-۴-۱
۳-۴-۲ تحلیل الگوریتم‌های بازگشتی
تمرین‌های زبرخش ۳-۴-۲
۳-۵ روشهای حل رابطه‌های بازگشتی
۳-۵-۱ حدس و استقرا
۳-۵-۲ تکرار با جای‌گذاری
۳-۵-۳ درخت بازگشت
۳-۵-۴ قضیه‌ی اصلی
۳-۵-۵ حل مستقیم یک رابطه‌ی بازگشتی
تمرین‌های بخش ۳-۵
۶-۳ رابطه‌های بازگشتی همگن
تمرین‌های بخش ۳-۶
۳-۷ تحلیل سرشکنی
۳-۷-۱ روشهای تحلیل سرشکنی
۳-۷-۲ روش تابع پتانسیل
تمرین‌های بخش ۳-۷
تمرین‌های فصل ۳
۴ داده ساختارهای ساده
۴-۱ دسته‌بندی داده ساختارها
۴-۲ لیست‌ها
۴-۲-۱ پیاده‌سازی لیست‌های پیوندی
۴-۲-۲ اعمال اصلی بر روی لیست خطی
۴-۲-۳ عملیات دیگر بر روی لیست‌ها
۴-۲-۴ پیاده‌سازی لیست‌ها با اشاره‌گرهای اندیسی
تمرین‌های زیربخش ۴-۲-۴
۴-۲-۵ پشته‌ها
تمرین‌های زیربخش ۵-۲-۴
۴-۲-۶ صف
۴-۳ کاربردهای از لیست‌ها
۴-۳-۱ مرتب‌سازی ادغامی
۴-۳-۲ لیست‌های کلی
۴-۳-۳ تبدیل الگوریتم‌های بازگشتی به غیربازگشتی
تمرین‌های بخش ۴-۳
۴-۴ درخت‌ها
۴-۴-۱ تعریف‌های اولیه در درخت‌ها
۴-۴-۲ پیمایش درخت‌ها
۴-۴-۳ درخت دودویی معادل
۴-۴-۴ اعمال مختلف بر روی درخت
۴-۴-۵ پیاده‌سازی درخت‌ها
۴-۴-۶ درخت دودویی
۴-۴-۷ درخت‌های عبارت
۴-۴-۸ تبدیل نگارش‌های مختلف عبارت به هم
۴-۴-۹ تِرای، درختی برای ذخیره‌ی رشته‌ها
تمرین‌های بخش ۴-۴
۴-۵ درخت دودویی جست‌وجو
۴-۵-۱ اعمال مختلف بر روی درخت دودویی جست‌وجو
۴-۵-۲ میانگین ارتفاع درخت دودویی جست‌وجو
تمرین‌های بخش ۴-۵
۴-۶ صف اولویت
۴-۶-۱ تعریف و ویژگی‌های هرم بیشینه
۴-۶-۲ پیاده‌سازی هرم بیشینه و انجام اعمال مختلف
تمرین‌های بخش ۴-۶
تمرین‌های فصل ۴
پروژه‌های برنامه‌نویسی فصل ۴
۵ درهم‌سازی
۵-۱ جدول آدرس‌دهی مستقیم
تمرین‌های بخش ۵-۱
۵-۲ جدول‌های درهم‌سازی
۵-۳ روش زنجیره‌ای برای حل برخورد
تمرین‌های بخش ۵-۳
۵-۴ توابع درهم‌سازی
۵-۴-۱ روش تقسیم
۵-۴-۲ روش ضرب
۵-۵ درهم‌سازی سراسری
تمرین‌های بخش ۵-۵
۵-۶ آدرس‌دهی باز
۵-۶-۱ وارسی خطی
۵-۶-۲ وارسی درجه‌ی ۲
۵-۶-۳ درهم‌سازی دوگانه
۵-۶-۴ تحلیل آدرس‌دهی باز
تمرین‌های بخش ۵-۶
۵-۷ درهم سازی کامل
تمرین بخش ۵-۷
۵-۸ درهم‌سازی پویا
۵-۸-۱ فقط درج
۵-۸-۲ درج و حذف باهم
تمرین‌های بخش ۵-۸
تمرین‌های فصل۵
۶ مرتب‌سازی و مرتبه‌ی آماری
۶-۱ دسته‌بندی و کران پایین
تمرین‌های بخش ۶-۱
۶-۲ مرتب‌سازی خطی
۶-۲-۱ مرتب‌سازی شمارشی
۶-۲-۲ مرتب‌سازی مبنایی
۶-۲-۳ مرتب‌سازی سطلی
تمرین‌های بخش ۶-۲
۶-۳ مرتب‌سازی مقایسه‌ای
۶-۳-۱ مرتب‌سازی سریع
۶-۳-۲ مرتب‌سازی سریع تصادفی
تمرین‌های زیربخش ۶-۳-۲
۶-۳-۳ مرتب‌سازی هرمی
تمرین‌های زیربخش ۶-۳-۳
۶-۴ الگوریتم فورد ـ جانسون
تمرین‌های بخش ۶-۴
۶-۵ میانه‌ها و مرتبه‌های آماری
۶-۵-۱ کمینه و بیشینه
۶-۵-۲ یافتن هم‌زمان بیشینه و کمینه
۶-۵-۳ انتخاب در زمان میانگین خطی
تمرین‌های زیربخش ۶-۵-۳
۶-۵-۴ انتخاب خطی در بدترین حالت
تمرین‌های بخش ۶-۵
۶-۶ مرتب‌سازی خارجی
۶-۶-۱ مرتب‌سازی ادغامی خارجی
۶-۶-۲ مرتب‌سازی خارجی چندفازه
تمرین‌های بخش ۶-۶
تمرین‌های فصل ۶
پروژه‌های برنامه‌نویسی فصل ۶
۷ داده ساختارهای پیشرفته
۷-۱ مجموعه‌های مجزا
۷-۱-۱ داده‌ساختار مبتنی بر لیست
۷-۱-۲ داده‌ساختار مبتنی بر درخت
۷-۱-۳ پیاده‌سازی با «فشرده‌سازی مسیر»
تمرین‌های بخش ۷-۱
۷-۲ درخت دودویی جست‌وجوی بهینه
۷-۲-۱ راه‌حل بازگشتی
۷-۲-۲ راه‌حل پویا
تمرین‌های بخش ۷-۲
۷-۳ درخت‌های دودویی جست‌وجو با ارتفاع لگاریتمی
۷-۳-۱ درخت قرمز – سیاه
تمرین‌های زیربخش ۷-۳-۱
۷-۳-۲ گسترش درخت قرمز ـ سیاه: درخت مرتبه‌ی آماری
تمرین‌های زیربخش ۷-۳-۲
۷-۳-۳ گسترش درخت قرمز ـ سیاه: درخت بازه
تمرین‌های زیربخش ۷-۳-۳
۷-۳-۴ درخت اِی.وی.اِل
۷-۴ درخت ۳-۲
۷-۵ درخت «بی»
تمرین‌های فصل۷
پروژه‌های برنامه‌نویسی فصل ۷
پیوست‌ها
۱ نمونه‌ای از برنامه‌ی جاوا
۲ نمادها و تابع‌های مهم
۳ واژه‌نامه‌ی فارسی به انگلیسی
۴ واژه‌نامه‌ی انگلیسی به فارسی
کتاب‌نامه
فهرست الفبایی