به‌نام خدا
دانشگاه اصفهان
ساختمان داده – دکتر رمضانی
پاییز ۰۲-۰۳
اهداف:
- پیاده‌سازی ساختمان داده لینک‌لیست دوطرفه
- مقایسه و تحلیل پیچیدگی زمانی پیاده‌سازی لینک‌لیست پیاده‌سازی شده توسط خودتان و لینک‌لیست پیاده‌سازی شده در زبان‌های برنامه‌نویسی
در ابتدا لینک‌لیست دوطرفه خود را پیاده‌سازی کنید.
لینک‌لیست شما باید قابلیت‌های زیر را داشته باشد:
- size(): Returns the number of elements in the list
- size
- isEmpty(): Returns True if the list is empty
- isEmpty
- first(): Returns the first element.
- first
- last(): Returns the last element.
- last
- addFirst(e): Adds a new elemenet to the front of the list.
- addFirst e
- addLast(e): Adds a new element to the end of the list.
- addLast e
- removeFirst(): Removes and returns the first element of the list.
- removeFirst
- removeLast(): Removes and returns the last element of the list.
- removeLast
- sort(): Sort elements
- sort
- add(i, e): Adds a new element to the i-th position of the list.
- add i e
- remove(i): Removes and returns the i-th element of the list.
- remove i
- get(i): Returns the i-th element of the list.
- get i
توجه کنید که توابع شما باید از طریق دستوراتی که زیر هر تابع نوشته شده قابل دسترسی باشند.
برای فهم بیشتر فایل example_input, example_output را بررسی کنید.
درباره لینک‌لیست دو طرفه در زبان برنامه‌نویسی Java (معادل LinkedList) و زبان برنامه‌نویسی Cpp (معادل list) مطالعه کنید و آن‌ها را مورد بررسی قرار دهید.
تحلیل خود را در یک فایل pdf در کنار کدهای خود در همین ریپازیتوری آپلود کنید. تحلیل شما باید شامل موارد زیر باشد:
- به دست آوردن پیچیدگی زمانی (اردر) توابع هر دو نسخه و مقایسه با یکدیگر.
- به دست آوردن زمان اجرا و حافظه مصرفی هر یک از توابع در هر دو نسخه به ازای یک مثال مشخص و مقایسه با یکدیگر.
برای تحلیل فرآیند‌ها از فایل‌های تستی که در ریپازیتوری قرار داده شده استفاده کنید.
توجه کنید که درباره هر یک از موارد تحلیل‌شده باید توضیح کوتاهی داشته باشید.
می‌توانید از منابع زیر برای مطالعه ساختمان‌داده‌های زبان‌های برنامه‌نویسی استفاده کنید.