Data Structures with C++

📝 پروژه ساختمان داده‌ها

• دانشگاه: آزاد واحد قدس
• دانشکده: اندیشه
• درس: ساختمان داده
• استاد: دکتر آرتین زمردیان
• دانشجویان:
  • مهندس محمد حیدری
  • مهندس امیر رضا رشتبری
  • مهندس سروش بهمنی
  • مهندس نیما ماهر خامنه

📢 مقدمه

این پروژه شامل پیاده‌سازی درس‌های مختلف ساختمان داده‌ها در زبان C++ است. هدف پروژه آموزش و تمرین مفاهیم پایه مانند پشته، صف، لیست پیوندی، عبارات پسوندی و پیشوندی، بازگشت، و کاربردهای آنها می‌باشد. همچنین، پروژه به گونه‌ای طراحی شده که بتوانید با استفاده از فایل‌های Compile و Test عملیات کامپایل و اجرای برنامه‌ها را به صورت خودکار انجام دهید.

---

☰ فهرست دروس

Lesson	Chapter Readme	C++ File
	— Chapter 1 —
Factorial	Readme	Code
Matrix Addition	Readme	Code
Bubble Sort	Readme	Code
Linear Search	Readme	Code
Max Element	Readme	Code
Fibonacci Sequence	Readme	Code
Tower of Hanoi	Readme	Code
	— Chapter 2 —
Array Simple	Readme	Code
Array Addresses	Readme	Code
Address Formula	Readme	Code
Linear Search	Readme	Code
Binary Search	Readme	Code
Matrix Addresses	Readme	Code
Sparse Matrix	Readme	Code
	— Chapter 3 —
Stack Array	Readme	Code
Stack Under Flow	Readme	Code
Postfix Expression	Readme	Code
Infix to Postfix	Readme	Code
Recursive Subroutines	Readme	Code
	— Chapter 4 —
Queue (FIFO / LIFO)	Readme	Code
Queue Operations	Readme	Code
Queue Display	Readme	Code
Linked List	Readme	Code
Loops	Readme	Code
List Traversal	Readme	Code

---

🧱 ساختار کلی هر درس

هر درس در پروژه با یک فایل C++ مستقل نوشته شده و به جای گرفتن ورودی تعاملی (cin)، ورودی‌ها از آرگیومنت‌های خط فرمان (argv) دریافت می‌شوند.

برای مثال:

./01_factorial 5

در این حالت:

• argv[0] = مسیر برنامه (./01_factorial)
• argv[1] = 5 (عدد مورد نظر برای محاسبه فاکتوریل)

---

💢 آرگیومنت‌ها در برنامه‌ها

• اعداد ساده: مثل فاکتوریل یا فیبوناچی، تنها یک مقدار نیاز دارند.

• آرایه‌ها و لیست‌ها: عناصر آرایه یا لیست پیوندی به صورت دنباله‌ای از آرگیومنت‌ها پاس می‌شوند.

  • argv[1] = طول آرایه (5)
  • argv[2..6] = عناصر آرایه (10, 20, 15, 30, 25)

• صف و عملیات‌ها: در مثال Queue، ممکن است یک سری دستورات مثل dequeue و pop به عنوان آرگیومنت پاس شوند:

  مثال:

  ./04_queue 10 20 30 dequeue 40

---

🀠 هندل کردن آرایه‌ها و لیست‌ها

• در برنامه C++، معمولاً مراحل زیر انجام می‌شود:

1. خواندن طول لیست/آرایه از argv[1]

2. ایجاد آرایه/لیست با طول مشخص

3. پر کردن عناصر از باقی آرگیومنت‌ها (argv[2..n])

   for (int i = 0; i < n; i++)
       arr[i] = std::atoi(argv[2 + i]);

4. عملیات موردنظر (مرتب‌سازی، پیمایش، نمایش، …)

5. چاپ خروجی نهایی روی stdout (یک خط یا چند خط بسته به درس)

---

✅ مزیت این روش

• بدون نیاز به ورودی تعاملی → مناسب تست خودکار با Python
• هر خروجی قابل assert مستقیم است
• مدیریت آرایه‌ها و لیست‌ها کاملاً سلسله‌مراتبی و ساده است: طول + عناصر

---

🚀 مراحل پیاده سازی

مراحل 3 به بعد برای تست اختیاری میباشد.

1. ابتدا کمپایلر مربوط به سیستم عامل خود را نصب کنید: Download

2. داخل CMD از نصب آن اطمینان حاصل کنید

   دستور:

   g++ --version

   نتیجه:

   g++.exe (tdm64-1) 10.3.0
   

3. افزونه C++ را در vsCode نصب میکنیم.

   • در این مرحله میتوانیم کد هارا از مسیر source کامپایل و اجرا کنیم

4. برای کامپایل کردن و تست دست جمعی python را نصب میکنیم.

5. با استفاده از pip کتابخانه های مورد نیاز را نصب کنید:

   دستور:

   pip install -r requirements.txt

6. با اجرا کردن فایل compile.py تمامی فایل ها کمپایل شده و در پوشه build قرار میگیرند.

   دستور:

   python ./compile.py

7. حال با استفاده از دستور pytest میتوانید هر فصل را تست کنید:

   python -m pytest -v

   نتیجه:

   test/test_chapter_1.py::test_factorial PASSED
   test/test_chapter_1.py::test_matrix_add PASSED
   test/test_chapter_1.py::test_bubble_sort PASSED
   test/test_chapter_1.py::test_linear_search PASSED
   test/test_chapter_1.py::test_max_element PASSED
   ...
   

---

⚒️ توضیح درباره فایل Compile

• این فایل مسئول کامپایل کردن تمام فایل‌های درس‌ها است.
• از g++ برای تولید فایل‌های اجرایی (.exe) استفاده می‌کند.
• فایل خروجی در مسیر build/ ذخیره می‌شود.
• در صورت بروز خطا هنگام کامپایل، فایل جزئیات خطا را چاپ می‌کند.

---

🧪 توضیح درباره فایل Test

• فایل Test مسئول اجرای خودکار برنامه‌ها با ورودی‌های مشخص و بررسی خروجی است.

• از کتابخانه pytest برای دریافت نتایج تست ها به صورت یکجا استفاده شده است.

  1. برنامه اجرا می‌شود
  2. خروجی با نتیجه‌ی مورد انتظار مقایسه می‌شود

• در صورت موفقیت تست، پیام PASSED و در غیر این صورت پیام خطا نمایش داده می‌شود.

نمونه یکی از تست ها:

def test_postfix_expression():
    assert ch_3_postfix_expression.run('1', '1', '+') == '2'

• در مثال بالا اسکریپت عبارت پسوندی اجرا شده و مقادیر +11 به ماشین میدهد و در انتها جواب ماشین با عدد 2 مقایسه شده و در صورت مقایرت خطا چاپ میشود

---

☰ فهرست فایل های تست

Chapter	Test Files
Chapter 1	Test File
Chapter 2	Test File
Chapter 3	Test File
Chapter 4	Test File

---

📸 تصویر تست های انجام شده از تمامی دروس

---

✅ نکات مهم

• قبل از اجرای هر درس، مطمئن شوید که مسیر build/ وجود دارد.
• از Python 3 برای اجرای LessonScript استفاده کنید.
• در Windows، هنگام استفاده از * در Postfix، یا آن را quoted وارد کنید یا از جایگزین مثل 'x' استفاده کنید.