ساختمان داده‌ها و الگوریتم‌ها

هدف
درس ساختمان داده‌ها، ادبيات برنامه‌نويسي و هنر ايجاد نرم‌افزار است. هدف اين درس ارايه ساختار کلاسيک ساختمان‌هاي مختلف داده‌ها، آشنايي با اصول استفاده از آنها به صورتی مستقل از زبانهاي برنامه‌نويسي و در نهايت آشنايي مقدماتي با نحوه طراحي الگوريتم براي حل يک مسأله به ويژه نحوه انتخاب ساختمان داده مناسب براي آن مسأله است.

پيش‌نياز
هر چند درس ساختمان داده‌ها به صورتی مستقل از زبانهاي برنامه‌نويسي ارائه مي‌شود، اما آشنايي مقدماتي با يک زبان برنامه‌نويسي شيءگرا (مانند C++ يا JAVA) براي دانشجويان الزامي است.

سرفصل مطالب درس
• مقدمه‌اي بر الگوريتمها، اصول رياضي تحليل الگوريتم، پيچيدگي‌هاي زمان-فضاي الگوريتمها
• آرايه‌ها: عمليات اساسي آرايه‌ها، الگوريتمهاي جستجو، چندجمله‌اي‌ها، رشته‌ها، آرايه‌هاي چندبعدي و ماتريسها، ماتريسهاي خلوت، رکوردها، ADT آرايه.
• پشته‌ها و روابط بازگشتي: ساختار و عمليات اساسي پشته، ارزيابي عبارات محاسباتي و نمادگذاري لهستاني، نقش پشته‌ها در الگوريتمهاي بازگشتي، بازسازي روابط بازگشتي با پشته‌ها، ADT پشته.
• صف: عمليات اساسي صفها، صفهاي حلقوي، دوصفها، صفهاي اولويتي، ADT صف.
• ليستهاي پيوندي: عمليات اساسي ليستهاي پيوندي، ليستهاي پيوندي با سرگره، ليستهاي دوطرفه، ليستهاي حلقوي، ليستهاي ناهمگون، الگوريتمهاي بازگشتي تحليل ليستها، مديريت حافظه پويا، ADT ليستهاي پيوندي، پیاده‌سازی پشته‌ها و صفها با لیستها پیوندی.
• درختها: معرفي ساختار درختها، نمايش درختها به کمک ليستهاي پيوندي، درختهاي دودويي، نمايش درختهاي دودويي به کمک آرايه‌ها و ليستهاي پيوندي، الگوريتمهاي پيمايش درختهاي دودويي، تحليل درختهاي دودويي، ADT درختهاي دودويي، درختهاي دودويي نخ‌کشي‌شده، کومه‌ها و الگوريتمهاي مرتبط، درختهاي جستجوي دودويي، عمليات اساسي درختهاي جستجوي دودويي، درختهاي عمومي، درختهاي موزون عمقي، درختهاي تصميم‌گيري، درختهاي کومه‌اي، درخت بيشينه-کمينه کومه‌اي، درختهاي کومه‌اي دوجمله‌اي، درختهاي کومه‌اي فيبوناتچي، جنگل.
• گرافها: نظريه گرافها، ماتريسهاي مجاورت، عمليات اساسي گرافها، پيمايش گرافها، درختهاي پوشا، مسأله کوتاهترين مسير.
• ساختارهاي جستجو: درختهاي جستجوي بهينه، درختهاي AVL، درختهاي 2-3، درختهاي 2-3-4، درختهاي قرمز-سياه.
• مرتب‌سازي: مفاهيم مرتب‌سازي، بررسي الگوريتمهاي مختلف مرتب‌سازي (حبابي، درجي، گزينشي، ادغام، مبنايي، کومه‌اي، پوسته‌اي) و مقايسه پيچيدگي آنها.
• درهم‌سازي: مفاهيم درهم‌سازي، الگوريتمهاي درهم‌سازي، درهم‌سازي ايستا، درهم‌سازي پويا.

مراجع

• Goodrich M., Tamassia R., Mount D., “Data Structures and Algorithms in C++”, John Wiley & Sons Inc., ISBN: 0-471-20208-8.
• Goodrich M., Tamassia R., “Data Structures and Algorithms in Java”, John Wiley & Sons, Inc., 4th Editio (pdf available).
• Kruse Robert L. , Ryba Alexander J., “Data Structures and Program Design in C++”, Prentice Hall, 2000 (pdf available)
• Seymour Lipschutz,”Schaum’s Outline of Theory and Problems of Data Structure”, McGraw Hill, 1986.
• Horowitz E., Sahni S., Mehta D., “Fundamentals of Data Structures in C++”, W. H. Freeman & Co, 1999 (pdf available)
• Dale N., Joyce D., Weems C., “Object-oriented Data Structures Using Java”, Jones and Bartlett Publishers, 2006.
• Dale N., “C++ plus Data Structures”, Jones and Bartlett Publishers, 3d Edition.
• Cormen T., Leiserson C., Stein C., Rivest R.,”Introduction to Algorithms”, MIT Press, 2001 (pdf available).
• Wirth, N., “Algorithms + Data Structures = Programs”, Prentice- Hall.