پروژه دانشجویی: AVL Trees

---

شرح پروژه

این پروژه شامل پیاده‌سازی یک کلاس به نام Wordlist است که وظیفه آن شمارش تعداد دفعات تکرار هر واژه در یک فایل متنی است. برای این منظور، ساختار داده‌ای اصلی که استفاده می‌شود، یک درخت جستجوی متوازن از نوع AVL Tree است. در این پروژه استفاده از ساختارهای دیگری مانند آرایه‌ها یا وکتورها مجاز نیست. کلاس Wordlist باید مستقیماً به عنوان یک درخت AVL طراحی و پیاده‌سازی شود.

وظایف و اهداف:

 1. ایجاد درخت متوازن برای ذخیره واژگان:

هر گره در درخت شامل یک واژه، تعداد دفعات تکرار آن، اشاره‌گر به گره‌های فرزند (چپ و راست)، اشاره‌گر به گره والد، و ارتفاع گره است.

 2. شمارش تعداد کل کلمات و تعداد کلمات منحصر به فرد:

 • تعداد کل کلمات: مجموع تمام کلمات (با تکرار) در فایل.

 • تعداد کلمات متفاوت: تعداد گره‌های موجود در درخت.

 3. شناسایی و مدیریت کلمات خاص:

 • واژه‌ای که بیشترین تکرار را دارد.

 • تعداد کلماتی که فقط یک بار در فایل ظاهر شده‌اند (Singletons).

 4. امکانات اضافه:

 • چاپ آمار کلی در مورد واژه‌ها.

 • چاپ واژه‌ها به ترتیب الفبایی به همراه تعداد تکرار هر واژه.

 • عملیات ورود، حذف، و جستجو بر روی واژه‌ها.

ویژگی‌های اصلی پروژه:

 • AVL Tree:

 • این درخت با حفظ ویژگی توازن، امکان جستجو، درج، و حذف را در زمان بهینه فراهم می‌کند.

 • برای پیاده‌سازی عملیات درج و حذف، از چرخش‌های (Rotations) چپ و راست استفاده می‌شود.

 • ساختار گره‌ها:

هر گره (Node) شامل موارد زیر است:

 • word: یک رشته که واژه موردنظر را ذخیره می‌کند.

 • count: تعداد دفعات تکرار واژه.

 • left: اشاره‌گر به گره فرزند سمت چپ.

 • right: اشاره‌گر به گره فرزند سمت راست.

 • parent: اشاره‌گر به گره والد.

 • height: ارتفاع گره در درخت.

عملکردهای اصلی:

 1. سازنده‌ها (Constructors):

 • سازنده پیش‌فرض: ایجاد یک درخت خالی.

 • سازنده فایل: خواندن یک فایل متنی و افزودن کلمات آن به درخت.

 • سازنده کپی: ایجاد یک نسخه کپی از یک شی Wordlist دیگر.

 2. دستورالعمل‌های عمومی:

 • Insert: افزودن یک واژه جدید یا افزایش تعداد تکرار آن در صورت وجود.

 • Remove: حذف یک واژه از درخت.

 • Contains: بررسی وجود یک واژه در درخت.

 • GetCount: دریافت تعداد دفعات تکرار یک واژه خاص.

 3. گزارش‌دهی:

 • PrintStatistics: نمایش تعداد کل واژه‌ها، تعداد واژه‌های متفاوت، پرتکرارترین واژه، و تعداد تک‌واژه‌ها.

 • PrintWords: نمایش تمام واژه‌ها به ترتیب الفبایی به همراه تعداد تکرار آن‌ها.

نکات مهم:

 • رعایت توازن درخت با به‌کارگیری چرخش‌های مناسب در عملیات درج و حذف الزامی است.

 • مدیریت حافظه پویا (Dynamic Memory) باید به گونه‌ای انجام شود که پس از پایان برنامه، هیچ حافظه‌ای نشت نکند.

 • پیاده‌سازی باید به گونه‌ای باشد که امکان تست و ارزیابی آسان فراهم شود.

هدف کلی:

ایجاد یک ابزار ساده و سریع برای پردازش فایل‌های متنی و استخراج اطلاعات آماری مرتبط با واژه‌ها، با استفاده از الگوریتم‌های بهینه درخت‌های جستجوی متوازن.

1. پروژه باید شامل دو فایل اصلی باشد:

 • Wordlist.h: شامل تعریف کلاس‌های Wordlist و AVLTreeNode و تمام متغیرها و توابع آن‌ها.

 • Wordlist.cpp: شامل پیاده‌سازی تمام توابع تعریف‌شده در فایل .h.

 تمام فایل‌های پروژه را در یک پوشه قرار دهید و سپس این پوشه را به صورت .zip فشرده‌سازی کنید.

شرح کامل پروژه به صورت عکس و فایل همراه با فایل های مورد نیاز پروژه ضمیمه شده است.

این پروژه شامل 15 فایل مهم است، لطفا قبل از ارسال پیشنهاد حتما نسبت به بررسی این فایل اقدام فرمایید.

مهارت ها و تخصص های مورد نیاز

---

---