دانشگاه شهید بهشتی
دانشکده مهندسی برق و کامپیوتر
ترم دوم ۹۰-۸۹

برنامه‌سازی پیشرفته

گروه درسی بر روی گوگل
تارنامه ارسال تمرینات
استاد : دکتر آزاده منصوری
برنامه‌سازی پیشرفته - دانشگاه شهید بهشتی - ترم دوم سال تحصیلی ۹۰-۸۹ | پروژک نوروزی
آخرین به روز رسانی : ۲۶ اسفند ۸۹

پروژک نوروزی


سال نو مبارک

بچه که بودیم پیک شادی در عیدها می دادند، قسمت‌های جالبش را نگاه می‌کردیم و بقیه‌اش را با عذاب تمام می‌کردیم. اما الان چون بسیار علاقمند به علم و تکنولوژی شیرین کامپیوتر هستیم، وقتی پروژه نوروزی می‌دهند کلی خوشحال می‌شویم و حتی ممکن است وقتی دوتا پروژه می‌دهند و می‌گویند یکی را انتخاب کنید، هر دو را انجام دهیم!

پروژه اول :‌ اطلاعات دانشجویان

مقدمه

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

struct CourseNode; //forward declaration [cuz used in StudentNode but declared after that]

struct StudentNode
{
	StudentNode *next;

	char name[30];
	int id; //شماره دانشجویی
	enum {Male=0,Female} gender; //جنسیت
	
	CourseNode *courseList; //لیست پیوندی دروس
};

struct CourseNode 
{
	CourseNode* next;

	char title[30]; // عنوان
	char teacher[30]; //نام مدرس
	int units; //تعداد واحد
	int score; //نمره
};
در این پروژه باید دو لیست پیوندی از StudentNode به نامهای computerList و electronicList داشته باشیم که دانشجویان مربوطه را نگهداری نماید. عملیات زیر توسط برنامه باید قابل انجام باشد :

عملیات

افزودن دانشجو دانشجویان باید طوری افزوده شوند که لیست‌ها همواره بر اساس شماره دانشجویی مرتب باشند (یعنی در جای مناسب لیست درج شوند). به مثال توجه کنید :

AddStudent
computer AbbasNaderi 89213151 m

AddStudent
electronic SaraHasani 89203010 f

AddStudent
computer HamidPoorjam 88203050 m

PrintAll
--computer--
88203050 HamidPoorjam m
89213151 AbbasNaderi m
--electronic--
89203010 SaraHasani f

حذف دانشجو برای حذف دانشجو، با دریافت شماره دانشجویی وی، باید از لیست حذف گردد :

RemoveStudent
89213151

RemoveStudent
89102030
- Not Found

افزودن درس به دانشجو با ورود اطلاعات درس و شماره دانشجویی دانشجو، درس به لیست دروس وی اضافه گردد.

AddCourse
89213151 AdvancedProgramming Mansouri 3 19.2

AddCourse
89213151 ComputerBasics Ahmadifar 4 16

AddCourse
89102030 AnotherCourse Teacher 1 20
- Student Not Found

حذف یک درس از لیست دروس دانشجو با وارد کردن شماره دانشجویی و نام درس، درس از لیست دروس وی حذف شود :

RemoveCourse
89213151 AdvancedProgramming

RemoveCourse
89102030 AdvancedProgramming
- Student Not Found

RemoveCourse
89213151 AnotherCourse
- Course Not Found

تغییر نمره با دریافت شماره دانشجویی و نام درس و نمره جدید، نمره را تغییر دهد :

UpdateScore
89213151 AdvancedProgramming 20

UpdateScore
89102030 AdvancedProgramming
- Student Not Found

UpdateScore
89213151 AnotherCourse
- Course Not Found

چاپ لیست و چاپ نزولی لیست دانشجویان بر اساس شماره دانشجویی به صورت صعودی یا نزولی نمایش داده شود :

PrintAll
--computer--
88203050 HamidPoorjam m
89213151 AbbasNaderi m
--electronic--
89203010 SaraHasani f

PrintReverse
--computer--
89213151 AbbasNaderi m
88203050 HamidPoorjam m
--electronic--
89203010 SaraHasani

چاپ لیست دروس یک دانشجو با دریافت شماره دانشجویی، لیست دروس و نمرات یک دانشجو را نمایش دهد :

ListCourse
89213151
- AbbasNaderi m Computer:
-- AdvancedProgramming (Mansouri) 19.2 (3 units)
-- ComputerBasics (Ahmadifar) 16 (4 units)

چاپ معدل یک دانشجو با دریافت شماره دانشجویی، معدل را خروجی دهد :

Average
89213151
- AbbasNaderi m Computer : 17.37 = ( 19.2 x 3 + 16 x 4 ) / 7 

چاپ آمار رشته‌ها تعداد دانشجویان و درصد دانشجویان دختر و پسر هر رشته را خروجی دهد :

Stats
- Computer 2 students, 100.0% male, 0.0% female
- Electronic 1 students, 0.0% male, 100.0% female

چاپ لیست اساتید رشته‌ها با حذف اساتید تکراری (دانشجویان ممکن است اساتید تکراری داشته باشند) لیست اساتید هر رشته را نمایش دهد :

Teachers
- Computer:
-- Mansouri
-- Ahmadifar
- Electronic:

بازگرداندن سیستم به حال اول با پاک کردن تمام دانشجویان و دروس آنها از لیست‌ها، سیستم را به حال اول باز گرداند :

PrintAll
--computer--
88203050 HamidPoorjam m
89213151 AbbasNaderi m
--electronic--
89203010 SaraHasani f

ListCourse
89213151
- AbbasNaderi m Computer:
-- AdvancedProgramming (Mansouri) 19.2 (3 units)
-- ComputerBasics (Ahmadifar) 16 (4 units)

Reset
- All data erased.

PrintAll
--computer--
--electronic--

ListCourse
89213151
- Not Found

پیاده‌سازی

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

رفع مشکل

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

تحویل

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


پروژه دوم : آرایه جدید

مقدمه

در بسیاری از برنامه‌ها احتیاج به آرایه‌ای داریم که محدودیت‌های آرایه پایه سی را نداشته باشد، یعنی :

  • اندازه آن ثابت نباشد
  • بتوان در میانه آن چیزی درج کرد
  • بتوان از میانه آن چیزی حذف کرد
  • کار کردن با آن ساده باشد
اکنون که مقداری از شی‌ء گرایی می‌دانیم، می‌خواهیم برای خودمان همچین آرایه‌ای بسازیم! تقریبا تمام زبان‌های سطح بالا ساختارهایی برای استفاده از اینچنین آرایه‌هایی دارند، و چندتا هم دارند. پس از انجام این پروژه متوجه خواهیم شد که چرا چندتا دارند و این چند ساختار چه تفاوت‌هایی با هم دارند.

قالب

از آنجایی که می‌خواهیم چند نوع آرایه بدون محدودیت پیاده کنیم، ولی نمی‌خواهیم در هنگام استفاده از آنها به تفاوت‌ها فکر کنیم (در واقع می‌خواهیم با همه آنها مثل یک آرایه ساده رفتار کنیم بدون در نظر گرفتن پیچیدگی‌های داخلی) ترجیح می‌دهیم که نام توابع و متدها برای دسترسی در همه آنها یکسان باشد. لذا قالب زیر را استفاده خواهیم کرد :

typedef int myType;

class NewArray {
	private:

	public:
	int append(myType data);
	void remove(int index);
	void insert(myType data, int index);
	int count();
	myType& item(int index);
};

خط اول، یعنی typedef را به این دلیل استفاده کردیم که با تغییر آن بتوانیم نوع کلاس آرایه خود را تغییر دهیم. فعلا نوع را int در نظر گرفته‌ایم ولی قصد نداریم طوری برنامه بنویسیم که آرایه جدید ما تنها برای نوع int قابل استفاده باشد.

در بخش public کلاس تنها همین متدها باید وجود داشته باشند، بنابراین کاربرانی که قصد استفاده از آرایه‌های جدید را دارند به سادگی می‌دانند چه توابعی وجود دارد. در بخش private می‌توان هر چیزی که لازم است اضافه نمود.

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

تابع remove یک اندیس دریافت کرده و آن خانه را از آرایه ما حذف خواهد کرد. توجه داشته باشید که در صورت امکان این عملیات حذف باید حافظه اختصاص یافته به عنصر را آزاد کند.

تابع insert برای درج یک عنصر در میانه آرایه است. این تابع عنصر و محل درج آنرا دریافت می‌کند و آنرا درج می‌نماید.

تابع count تعداد عناصر موجود در آرایه جدید را باز می‌گرداند. دقت داشته باشید که تعداد عناصر از اندیس آخرین عنصر یکی بیشتر است، زیرا اگر آرایه‌ای یک عنصر داشته باشد، اندیس تنها عنصر آن صفر است.

در نهایت تابع item باید یک اندیس دریافت کرده، عنصر مربوطه را باز گرداند. اینکه نوع بازگشتی این تابع reference است برای آنست که توسط آن بتواند مقادیر را تغییر نیز داد، به مثال زیر توجه فرمایید :

NewArray a;
a.append(5);
int b = a.item(0) * 2;
a.item(0) = b + 1; //this line requires item() to return a reference instead of value

دقت داشته باشید که در تمامی توابع، در صورتی که اندیس ورودی کاربر از دامنه اندیس‌های معتبر خارج بود ( منفی بود یا از count() بزرگتر بود) برنامه باید خطای زمان اجرا تولید کند. برای اینکه برنامه شما خطای زمان اجرا تولید کند می‌توانید از تابع زیر بهره بگیرید :

void doError()
{
	int b=0;
	int a=10/b;
}

پیاده‌سازی

اکنون شما باید دو کلاس DynamicArray و LinkedArray را بر اساس توضیحات بالا بنویسید. DynamicArray می‌بایست برای نگهداری داده‌های خود از الگوی معرفی شده در تمرین ششم (آخر) سری دوم بهره بگیرد. LinkedArray نیز می‌بایست برای نگهداری داده‌های خود، از یک لیست پیوندی بهره بگیرد. دقت داشته باشید که توابعی که در بالا معرفی شد در هر دوی این کلاسها باید عینا یکسان باشد (از نظر نوع نه بدنه). در نهایت پس از اینکه کلاس‌ها را نوشتید و تکمیل نمودید، می‌توانید از برنامه تستی که در انتها قرار داده شده جهت تست صحت عملکرد آنها بهره بگیرید.

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

نکته : کل کد مربوط به این دو کلاس حدود ۳۰۰ خط خواهد شد (که بسیار کم است) ولی پیچیدگی زیادی دارد و چون دسترسی مستقیم به حافظه است، خطاهای زمان اجرای زیادی پیش خواهد آمد. لذا حتما از روزهای اولیه زمانتان شروع به انجام کنید تا اگر جایی گیر کردید بتوانید با کمک گرفتن مشکل را رفع کنید و یا وقت کافی صرف رفع آن بنمایید.

برنامه تست

برنامه تست را از این قسمت دریافت کنید. توضیحات ابتدایی در داخل فایل آن نوشته شده است. ترجیحا ابتدا کلاس‌ها را برای خودتان بنویسید، تست کنید و از صحت اولیه مطمئن شوید، سپس بر روی این فایل تست نمایید. توصیه اکید می‌شود کلاس‌ها را در دو فایل DynamicArray.h و LinkedArray.h جداگانه بنویسید (که تست از این دو فایل استفاده می‌کند) typedef تعریف نوع را در برنامه قرار دهید نه در فایلهای تعریف کلاس. کد را تا حد ممکن تمیز بنویسید زیرا در تمرینات بعدی نیز از همین کلاس‌ها استفاده خواهیم کرد.

دریافت فایل برنامه تست

رفع مشکل

جهت رفع مشکلات برنامه خود می‌توانید از برنامه قدرتمند Valgrind استفاده نمایید. این برنامه تمام مشکلات کار با حافظه موجود در برنامه شما را تشخیص می دهد و دقیق با شماره خط اعلام می‌کند. البته تنها دوستانی که از لینوکس و مک استفاده می‌کنند امکان بهره‌جویی از آن را دارند. دوستان مایکروسافتی می توانند از بقیه دوستان مایکروسافتی کمک بگیرند!

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

تحویل

در نهایت باید زمان‌های مشخص شده در برنامه تست به همراه دو فایل DynamicArray.h و LinkedArray.h را برای ما همانگونه که در پایین توضیح داده شده ارسال کنید.


نکات

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

نحوه ارسال

کلیه اطلاعات را با قالب مشخص (که در سری قبل معین شد) برای ای‌میل sbuap89b@gmail.com ارسال نمایید. به جای شماره تمرین از کلیدواژه Projak استفاده کنید. آخرین فرصت ارسال جمعه ۱۲ فروردین خواهد بود.

بازگشت