جلسه دهم ۲۳ فروردین ۱۳۸۷

از ویکی یزدلاگ، دانشنامهٔ آزاد.

سال نو مبارک

دهمین جلسه یزدلاگ ساعت ۱۷ روز جمعه، ۲۳ فروردین ۱۳۸۷ آغاز شد.

در این جلسه کارهای زیر انجام گرفت:

۱- معرفی qmake به عنوان قسمتی از ابزارهای Qt جهت ساختن خودکار MakeFile و همچنین ساخت برنامه Hello World عملی به کمک C++، Qt و KDevelop

۲- معرفی دو الگوریتم جهت ذخیره سازی یک ساختار درختی درون بانکهای اطلاعاتی رابطه ای (RDBMS)، روشهای بازگشتی (بسیار ساده و کند!) و الگوریتم زیبا Modified Preorder Tree Traversal

معرفی qmake به عنوان قسمتی از ابزارهای Qt جهت ساختن خودکار MakeFile و همچنین ساخت برنامه Hello World عملی به کمک C++، Qt و KDevelop

در ادامه بحث جلسه قبل در مورد چارچوب برنامه‌نویسی Qt، آقای مومنی نحوه‌ی ساخت یک پروژه با استفاده از Qt4 را بررسی کردند.

و در ادامه روش ایجاد و کامپایل یک برنامه ++C را در این محیط توضیح دادند.

برای ساخت ظاهر یا GUI یک برنامه‌ی ++C با استفاده از کتابخانه‌ی Qt4 چند راه وجود دارد:

شما می‌توانید، GUIی برنامه را دستی با کد بسازید، یا برای ساخت آن از ابزار Qt4-Designer استفاده کنید!

ما از Qt4-Designer استفاده می‌کنیم:

ابتدا یک فرم در محیط این برنامه می‌سازید، این برنامه اصطلاحا ویژوال است، و ساخت فرم با آن آسان است!

تصویر زیر فرم برنامه‌ی ما را در این برنامه نشان می‌دهد: (خروجی این کار یک فایل با پسوند ui است!)

حالا برای استفاده از فرم ایجاد شده: ابتدا یک کلاس با مشخصات زیر ایجاد می‌کنیم:

کلاس ما باید از دو کلاس ارث ببرد. (خاصیت ارث‌بری چندگانه‌ی ++C) یکی کلاسی که فرم ما از آن نوع است، که عموما QWidget یا QDialog یا QMainWindow است، بسته به نوعی که هنگام ایجاد فرم تعیین کرده‌ایم. و کلاس دیگر، کلاسی است که uic از فایل ui ما می‌سازد! کلاس مورد نظر (اینجا) Ui::MainDia نام دارد، (که MainDia نامی‌است که ما برای فرم انتخاب کرده‌ایم!)

نکته: uic یا UI Compiler ابزاری کمکی از جانب Qt است که کار تبدیل فایل ui به کد ++C را انجام می‌دهد! نام فایل هدری که این ابزار می‌سازد بصورت ui_{name of ui file}.h است! که با توجه به اینکه ما اسم فایل ui را main.ui گذاردیم، اینجا ui_main.h است!

نکته: Q_OBJECT ماکرو ایست که باید در هدر فایل کلاسهایی که از Qt Designer برای طراحی فرم استفاده کرده‌اند، گذارده شود!

تصویر زیر کد فایل هدر کلاس ما را نشان می‌دهد: (نام فایل اینجا mainform.h است!)

عمل دیگری که هنگام استفاده از Qt Designer باید انجام دهیم فراخوانی تابع setupUi(this) در سازنده‌ی کلاس است!

هر کد ++C ی باید یک تابع main داشته باشد که شروع اجرای برنامه از آن است! کد main ما اینجا اینگونه است:

Qt از یک ساختار SIGNAL – SLOT برای ایجاد ارتباط بین اتفاقاتی مثل کلیک شدن یک دکمه و اجرا شدن یک تابع استفاده می‌کند! همانطور که بالاتر ملاحظه می‌کنید، تابع d در کلاس ما به عنوان slot تعریف شده است!

حالا تنها با یک دستور به کامپایلر اطلاع می‌دهیم که می‌خواهیم سیگنال کلیک شدن دکمه‌ی p باعث اجرا شدن تابع d گردد! برای اینکار از تابع connect استفاده می‌کنیم، همانطور که در کد زیر که مربوط به سورس کلاس ما می‌گردد ملاحظه می‌کنید اینکار را در سازنده‌ی کلاس انجام داده‌ایم!

حالا کد ما آماده‌ی کامپایل است!

Qt ابزار کمکی دیگری به‌نام qmake دارد که در کار ساخت Makefile به ما کمک می‌کند! برای کامپایل کردن کد Qt خود، ابتدا به پوشه‌ی حاوی آن رفته سپس دستور qmake -project را اجرا کنید، تا qmake برای شما یک فایل با پسوند pro که حاوی اطلاعات پروژه‌ی شما است بسازد، (اینکار را دستی نیز می‌توانید انجام دهید!) بعد از ایجاد فایل مربوطه دستور qmake را اجرا کنید، تا Makefile برای کد شما ایجاد گردد! حالا مثل دیگر برنامه‌های لینوکسی با اجرا کردن دستور make پروژه‌ی شما کامپایل و آماده‌ی اجرا می‌گردد!

برای سادگی کار می‌توانید از ابزارهای برنامه‌نویسی مثل KDevelop استفاده کنید!

برای کسب اطلاعات بیشتر از مستندات Qt که هم نسخه‌ی online و هم نسخه‌ی off line دارد استفاده کنید!

معرفی دو الگوریتم جهت ذخیره سازی یک ساختار درختی درون بانکهای اطلاعاتی رابطه ای (RDBMS)، روشهای بازگشتی (بسیار ساده و کند!) و الگوریتم زیبا Modified Preorder Tree Traversal

آقای هومند در مورد پیاده‌سازی ساختار درختی در یک پایگاه داده رابطه‌ای (RDBMS) صحبت کردند.

مقدمه همونطور که می دونید پایگاه های داده رابطه ای (Relational Database Management Systems) برای براندازی روشهای ذخیره سازی قدیمی بوجود اومدند. در روش قدیمی داده ها بصورت درختی ذخیره می شدند، یعنی دقیقا مثل ساختار یک شجره نامه خانوادگی. در صورتی که در اکثر مواقع ما نیازی به یک درخت نداریم، مثلا برای ثبت مشتریان و سفارشهای اونها، خوب فقط این درخت کذایی تا ۲ مرحله (level) میره پایین، یکی خود مشتری و یکی اینکه چه چیزی را سفارش داده. بنابر این همونطور که اگر به مبانی بانک های اطلاعاتی رابطه ای آشنایی داشته باشید می دونید، دیگه نیازی نیست که از یک درخت استفاده کنیم، بلکه با دو تا جدول می شه به راحتی این قضیه را پیاده کرد، کما اینکه اینکار مزایای زیادی هم داره، میشه روابط مختلفی تعریف کرد و نتایج جالبی بدست آورد.

صورت مساله فرض کنید همچین درختی داشته باشیم:

چیکار می کنید حالا اگر خواسته باشید که یک ساختار واقعا درختی که معلوم نیست تا چه عمقی پیش میره را داخل یک بانک اطلاعاتی رابطه ای ذخیره کنید؟! یعنی با یک RDBMS کاری بکنید که واسش ساخته نشده! فرض کنید می خواید یک فایل سیستم بنویسید که تا بی نهایت می تونه شاخه هاش بره پایین، یا یک لیست سوال و جواب بنویسید که با انتخاب هر سوال، مجموعه سوالات دیگه ای واسه انتخاب وجود داشته باشه! اگر در سطح پایین داشته باشید کد کنید، می تونید یک ساختار درختی مثلا با اشاره گرها در C بنویسید و کارتون راه میافته، ولی اگه خواسته باشید از یک بانک اطلاعاتی رابطه ای مثل MySQL، PostgreSQL و امثالهم استفاده کنید، اونوقت چی؟!

راه حلها راه حل اول ساخت جدولی با دو فیلد است، فیلد اول نام عنصر (مثلا Fruit) را مشخص می کند و فیلد دوم پدر آن فیلد را (در مثال با Food). برای عنصر اول که پدری ندارد (در اینجا Food)، مقدار NULL را بجای پدرش وارد می کنیم. حالا تنها لازم است که با یک تابع بازگشتی (Recursive) و مشخص کردن Node ای که می خواهیم تمام بچه های آن را داشته باشیم، بچه های Node مشخص شده را خوانده و به ازاء هر فرزند، فرزندان آن Node را خوانده و به ازاء فرزندان آن Node، باز هم فرزندان آنرا خوانده و .... یک تابع بازگشتی!

جدولی که هر Node را با مشخص سازی پدرش ذخیره می کند. در واقع فیلد دوم رابطه ای یک به چند بر روی خودش دارد:

کد PHP ای که این جدول را خوانده و فرزندان را به ترتیب سطح چاپ می کند:

ويژگی این روش سادگی الگوریتم استفاده شده است. منتها به دلیل بازگشتی بودن، تعداد query بسیار زیادی به سمت server می رود که عملا استفاده از این روش را در یک پروژه واقعی زیر سوال می برد.

در الگوریتم دیگری که می خواهم معرفی کنم، شما ابتدا تمام node های درخت را از بالا به پایین و از چپ ترین node به سمت راست ترین node شماره گذاری می کنید، به قسمی که برای هر node دو شماره در سمت راست و چپ آن نوشته می شود. به این صورت:

حال که گراف خود را شماره گذاری کردید، آنرا در جدول بانک اطلاعاتی خود ذخیره می کنید، هر node به همراه شماره های موجود در راست و چپ آن ذخیره می شود:

همانطور که در عکس می بینید، اگر بخواهیم بچه های هر node را در بیاوریم، تنها کافیست که query بنویسیم که رکوردهایی که عدد سمت چپشان بین عدد سمت چپ و راست node مورد نظر ما باشد را برگرداند. فرض کنید بخواهیم تمام بچه های Fruit را استخراج کنیم، کافیست بنویسیم:

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC

دقت کنید که ORDER BY lft ASC نقشی حیاتی را در اینجا بازی می کند! چرا که فرزندان را به ترتیب بر می گرداند، تنها کاری که باقی مانده این است که رکوردهای دریافت شده را به ترتیب مرحله توگذاری کرده و چاپ کنیم. در واقع مشخص کنیم که کدام node فرزند کدام node دیگر است. کد PHP زیر به زیبایی این کار را انجام می دهد:

همانطور که دیدید تنها با ۲ query توانستیم کل درخت را بسازیم! ویژگی این روش سرعت بسیار بالای آن است. به راحتی نیز می توان تعداد فرزندان هر node را مشخص کرد، تنها کافیست از فرمول زیر استفاده کنید:

descendants = (right – left - 1) / 2

همچنین برای اضافه سازی یک node به عنوان فرزند به کل مجموعه، تنها کافیست از آنجایی که می خواهید node مربوطه را اضافه کنید، تمامی node های دیگر را که در سمت راست قرار دارند به صورتی update کنید که اعداد سمت راست و چپ آنها ۲ تا اضافه گردند، بدین صورت جا برای node جدید شما باز می شود! در صورت تمایل برای دیدن توضیحات کامل و کد PHP نمونه جهت پیاده سازی این ساختار با MySQL، به این آدرس مراجعه کنید.

---

دوستان حاضر در جلسه

آقایان بیژن هومند،مهرداد مومنی،محمدرضا حسن‌رضاییان،علی وکیلی و فرهاد باقری، عبدالرضا طالبیان

خانمها عظیمه بهشتی‌زاده،شیوا شاه میرزایی و گلناز نیلیه.