https://virgool.io/feed/@I_Am_Yoda علاقه‌مند fa 2026-06-16 13:36:15 https://files.virgool.io/upload/users/433693/avatar/umLq5g.jpeg?height=120&width=120 https://virgool.io/@I_Am_Yoda https://virgool.io/@I_Am_Yoda/tree-abstract-base-class-hatwtcrrf05t در قسمت قبلی این مقاله راجع به مقدمات ساختار داده غیرخطی و یک نوع آن یعنی درخت‌ها صحبت کردیم و تا حدودی با آن آشنایی پیدا کردیم. همانطور که گفته شد قصد داریم از صفر یک پیاده سازی از یکی از انواع معروف درخت‌ها یعنی Binary Trees انجام بدهیم. در این قسمت می‌خواهیم یک کلاس را Implement کنیم که بتوان از آن به عنوان کلاس پایه تمام انواع درخت‌ها از جمله درخت مورد مطالعه ما استفاده کرد. در قسمت قبلی از این کلاس به عنوان General Tree یاد کردیم. ما برای سادگی از abstract base class پایتون استفاده نمی‌کنیم و صرفا یک ارور NotImplementedError را rasie می‌کنیم. هر نود را به صورت یک Position در نظر می‌گیریم که در واقع یک عضو از base class ما است و خود یک کلاس است. متد سازنده کلاس Position دو آرگومانِ container و node را به عنوان ورودی گرفته و همچین متدهای __eq__ و __ne__ را هم implement می‌کند. دلیل استفاده از container به عنوان یک اتریبیوت این است که کاربر نتواند نودی که متعلق به این درخت نیست را به آن الحاق کند و باعث بروز مشکلات بعدی شود(در ادامه واضح تر میبینیم). متدهایی که میخواهیم پیاده سازی کنیم در کلاس پایه، به صورت زیر هستند:root()is_root(p)is_leaf(p)parent(p)children(p)pisitions()num_children(p)__iter__()__len__()is_empty()متد root نود روت را برمیگرداند. متد در صورتی که پوزیشنی که به عنوان آرگومان می‌گیرد نود روت باشد True و در غیر این صورت False را برگشت می‌دهد. بقیه متدها هم در واقع نام گذاری متد مشخص کننده کاری است که انجام می‌دهد و فکر نمی‌کنم نیاز به توضیح اضافه باشد. مثلا متد num_children یک پوزیشن p را به عنوان آرگومان گرفته و تعداد نود‌های فرزند آن را بر‌میگرداند. همچنین متد positions تمام پوزیشن‌های درخت را بر‌میگرداند.کلاس Position صرفا متد زیر را ساپورت می‌کند.element()و البته داندر‌های __eq__ و __ne__ را هم برای راحتی استفاده پیاده سازی میکنیم.(مورد استفاده اینها را بعدا هنگام validate کردن پوزیشن‌ها خواهیم دید)کلاس Tree متدهای پیمایش درخت و همچین height و depth را هم پیاده سازی می‌کند اما در اینجا از پیاده‌سازی آن‌ها صرف نظر کرده تا هنگامی که به مباحث مربوط به الگوریتم‌های پیمایش درخت رسیدیم در آن‌جا آن‌ها را پیاده می‌کنیم.● پیاده سازی General Tree Abstract Data Type در قالب کلاس Treeتا این مرحله کلاس ما به صورت بالا خواهد بود. این کد بخشی از ساختار داده درخت پیاده شده در پکیج luna است که کد آن را روی گیت‌هاب می‌توانید مشاهده کنید و خوشحال می‌شوم اگر دوس داشتید ستاره بدهید. البته این پکیج هنوز در مرحله توسعه قرار دارد.خب تا این لحظه ما توانستیم یک absrtact base class برای تمام انواع ساختار داده درخت در پایتون پیاده کنیم. در مرحله بعد ما سعی می‌کنیم درخت مورد مطالعه خود یعنی Binary Tree را پیاده کنیم. ادامه مقاله را در قسمت بعد خواهیم خواند. Yoda Yoda Tue, 18 Oct 2022 14:43:49 +0330 https://virgool.io/@I_Am_Yoda/tree-data-structure-in-python-hu2lymaeiqbm ● آنچه که در این مقاله به آن می‌پردازیم:تفاوت linear data structurs و nonlinear data structuresمعرفی درخت به عنوان یک nonlinear datastructureمعرفی تعاریف و اصطلاحات مربوط به درخت‌هاانواع درخت‌پیاده سازی یک درخت در زبان پایتونمعرفی و پیاده سازی الگوریتم‌های پیمایش درختمعرفی نمونه مسائلی که با کمک درخت‌ها حل می‌شوندبا توجه به مطالب بالا و اینکه میخواهیم تا حدود خوبی به هر یک بپردازیم و با توجه به اینکه می‌خواهیم یک درخت را به همراه الگوریتم‌های پیمایش آن به صورت کامل و از صفر پیاده کنیم، پیش بینی میشود که حجم این مقاله نسبتا زیاد باشد و در چند بخش مجزا ارائه شوند که این مقاله بخش اول آن می‌باشد.● تفاوت linear datastrucure و nonlinear data structureساختار داره خطی یا linear:در این نوع ساختار داده، عناصر به صورت خطی چیده می‌شوند و روابط بین عناصر به صورت after و before تعریف می‌شود. تمام عناطر در یک لول از نظر ساختاری قرار دارند و به همین دلیل میتوان کل ساختار را به یکباره پیمایش کرد. از آنجایی که مموری کامپیوتر‌ها ذاتا به صورت linear چیده شده است، پیاده سازی این نوع ساختار داده راحت است. مثال‌هایی از ساختار داده‌های خطی آرایه ها، صف‌ها، استک و ... است.ساختار داده غیرخطی یا nonlinear:در این نوع ساختار داده عناصر به صورت سلسه مراتیی چیده می‌شوند و روابط بین عناصر به صورت child و parent تعریف می‌شود. در این نوع ساختار داده، لزوما یک سطح وجود ندارد بنابراین نمی‌توان کل ساختار را در یک مرحله پیمایش کرد. با توجه به خطی بودن مموری کامپیوتر، پیاده سازی این نول ساختار داده نیازمند تلاش بیشتری نسبت به ساختار داده‌های خطی است. مثال‌هایی از ساختار داده‌های غیرخطی، درخت ها و گراف‌ها هستند.● معرفی درخت به عنوان یک ساختار داده غیرخطی:درخت یک ساختار داده غیرخطی است که در آن عناصر به صورت سلسله مراتبی و با روابط parent-child چیده شده‌اند. هر درخت یک عنصر به عنوان ریشه یا root دارد. معمولا ریشه درخت در پایین آن قرار دارد ولی در علوم کامپیوتر هنگام نمایش درخت ریشه آن را در بالا رسم می‌کنند. برای نمایش درخت عناصر درخت را به صورت دایره و یا شکل‌های دیگر رسم می‌کنند و مقدار عنصر را درون شکل می‌نویسند. با توجه به اینکه در ساختار داده درخت مفهوم سطح (Level) وجود دارد، هر عنصر در سطح مناسب خود قرار می‌گیرد و روابط والد-فرزند ی را با خطوطی که عناصر را به هم وصل می‌کنند مشخص می‌کنیم. برای نمونه تصویر زیر نمونه‌ای از نمایش یک درخت است.● معرفی تعاریف و اصطلاحات مربوط به درخت‌هانود یا node: به هر عنصر در درخت یک نود یا گره گفته می‌شود. برای مثال هریک از دایره‌های شکل بالا یک نود هستند.فرزند یا child: در نمایش درخت‌ها اگر نود a در یک سطح بالاتر از نود b قرار گرفته باشد و با یک خط به b وصل باشد، نود b را فرزند یا child نود a می‌نامیم. مثلا در تصویر بالا نود B فرزند نود A است.والد یا parent: در تعریف child، نود a والد یا parent نود b است. مثلا در تصویر بالا نود A والد نود B است.شاخه(branch) یا edge: به هرجف نود به شکل (u, v) که در آن u نود والد v باشد یا برعکس، یک edge یا branch گفته می‌شود.نود ancestor: نود v را ancestor نود u می‌نامیم اگر u=v یا نود v خود ancestor نود والد u باشد.(لطفا این تعریف را با دقت بیشتری بخوانید!)نود descendant: نود u نود descendant نود v است اگر و تنها اگر نود v نود ancestor نود u باشد.عمق یا depth: عمق نود p برابر است با تعداد ancestor های نود p به جز خود آن(اگر تعریفی که در بالاتر گفته شد را با دقت خوانده باشید متوجه شدید که هر نود ancestor خودش است). در یک تعریف ساده‌تر، عمق نود p برابر تعداد نودهایی است که از نود p تا خود ریشه قرار گرفته اند.(خود ریشه محاسبه میشود ولی خود p نه). عمق نود root صفر است.ارتفاع یا height: ارتفاع نود p برابر با ارتفاع بزرگترین زیردرخت آن است. یعنی تعداد decendant های آن. ارتفاع خود درخت برابر با ارتفاع نود root است.خواهر/برادر یا siblings: نود v خواهر/برادر نود u است اگر و تنها اگر parent نود u و v برابر باشد. یعنی هر دو فرزند یک والد باشند.● انواع درخت‌ها:درخت‌ها انواع متفاوتی دارند مانند binary tree ها، heap، avl trees، search trees، و ... که ما در این سری مقاله‌ها صرفا General Tree ها و یک نمونه از انواع گفته شده یعنی Binary Tree را بررسی و پیاده سازی می‌کنیم. منظور از General Tree در واقع یک پیاده سازی از درخت است که به عنوان کلاس پایه تمام درخت‌ها می‌تواند استفاده شود و در واقع متدها و ویژگی‌هایی که همه درخت‌ها دارند.حال که با تعاریف بالا آشنا شدیم، در بخش بعدی یک General Tree Abstract Data Type که در واقع یک کلاس پایه برای تمام انواع درخت‌هااز جمله درختی که ما بعدا پیاده سازی می‌کنیم(binary tree) است، پیاده سازی می‌کنیم. سپس به کمک آن درخت باینری را پیاده سازی میکنیم. دقت کنید که قصد نداریم از هیچ کتابخانه‌ای استفاده کنیم و می‌خواهیم از صفر خودمان یک ساختار داده درخت ایجاد کنیم. برای جلوگیری از طولانی شدن مقاله، ادامه آن را در قسمت بعدی می‌خوانیم. Yoda Yoda Mon, 17 Oct 2022 19:53:12 +0330 https://virgool.io/@I_Am_Yoda/%D9%85%D8%AA%D8%AF-clockwisespiral-%D8%B3%D8%A7%D8%AE%D8%AA%D8%A7%D8%B1-%D8%AD%D9%84%D8%B2%D9%88%D9%86%DB%8C-%D8%AF%D8%B1-%D8%AC%D9%87%D8%AA-%D8%B3%D8%A7%D8%B9%D8%AA%DA%AF%D8%B1%D8%AF-%D8%AF%D8%B1-%D8%B2%D8%A8%D8%A7%D9%86-c-%D9%88-c-imas6aewjotd تا قبل از سال ۱۹۹۴، زندگی برای برنامه‌نویس‌های C و ++C خیلی سخت می‌گذشت. اونها رو در حالی تصور کنین که زیر فشارِ درک و خوندن چیزی مثل :char (*fp)(int, float *);بودند. مثلا از خودشون میپرسیدن که خب حالا fp چیه ؟!!! اینجا بود که هزار تیرزهرآگین در قلبشون فرو میرفت. آخ بیچاره برنامه نویس‌های C و ++C ... (یک دقیقه سکوت)زندگی همینجور داشت بر برنامه‌نویس‌های C و ++C سخت می‌گذشت تا این که سال ۱۹۹۴ اومد. خب این عدد چه معنی خاصی داره؟ مثلا بیاین ۹ رو با ۱ جمع کنیم میشه ۱۰ بعد با اون یکی ۹ جمع کنیم میشه ۱۹ که با ۴ جمع بشه میشه ... امم مثل این که به چیزی نرسیدیم. خب این عدد برا ما هیچ معنی خاصی نداره. ولی برای برنامه‌نویس‌های C و ++C این یک عدد مقدسه. چرا که David Anderson در این سال بود که متد Clockwise/Spiral رو معرفی کرد و بالاخره بعد از سال‌ها چهره درهم برنامه‌نویس های C و ++C رو به چیزی شبیه ? تغییر داد. بالاخره این زندگی ارزش این همه سختی رو نداره ... بیاین ببینیم آقای اندرسون، این ناجی افسانه ای که بود و چه کرد ... خب بیاین از یه چیز ساده شروع کنیم. اول این مثال رو در نظر بگیرین :int *ptr;خب اینجا ما اگه از خودمون بپرسیم که ptr چیه خیلی ساده میگیم که : "ptr یک اشاره گر به نوع int است"خب تا اینجا ساده است. بیاین یکم سخت ترش کنیم. مثال پایین کمی سخت تره:chat *str[5];اینجا اگه از خودمون بپرسیم str چیه جوابی که میدیم اینه : "str یک آرایه با سایز ۵ است که اشاره می‌کند به نوع char" خب اینم آسون بود. حالا اینو شما بگین که همون مثالی هستش که اول گفتیم. پرسش اینه که fp چیه ؟char *(*fp)(int, float *);خب ... قبل این که ادامه متن رو بخونین سعی کنین خودتون اینو به فارسی توضیح بدین مثل کاری که با دو مثال قبلی کردیم.اگه برنامه نویس نسبتا حرفه‌ای C یا ++C بودین و تونستین مثال بالا رو هم جواب بدین، پس اینو هم لطفا به همون صورت توضیح بدین. اینجا پرسش اینه که f چیه ؟string(const* f(int, void (*const p)(int)))(char[]);خب اعتراف کنین که گفتن پاسخ سوال f چیه سخته. و گیج کننده است. ولی با متد "ساختار حلزونی در جهت عقربه‌های ساعت" ( یکم اسمش عجیبه ولی به زودی میفهمین دلیل نام گذاریش چیه) این کار دیگه سخت نیست.اول بیاین چندتا قرارداد با هم ببندیم :۱ - هر جا که با [x] یا [] روبه‌رو شدیم اونو به عبارت فارسی : "آرایه‌ای با سایز x ... آرایه‌ای با سایز تعریف نشده" تبدیل می‌کنیم۲ - هرجا که با ) یعنی پرانتز باز روبه‌رو شدیم که حتما داخلش آرگومان های تابع هست مثل مثلا (int b, int a ) ما اونو به این عبارت تبدیل می‌کنیم : "تابعی که به آن b از نوع int و a از نوع int پاس داده می‌شود، و بر می‌گرداند ..."۳ - اگه با * روبه‌رو شدیم اونو به عبارت : "اشاره گری به ..." تبدیل می‌کنیم.۴ - اگر با ( یعنی پرانتز بسته روبه‌رو بشیم باید کارمون رو با عناصر داخل پرانتز ادامه دهیم. نگران نباشین اگه اینا رو متوجه نمیشین در ادامه متوجه میشیم.۵ - کارمون رو تا وقتی ادامه میدیم که با همه عنصر‌ها رو به رو شده باشیم.۵ - اگر با ; رو به رو بشیم در حالی که هنوز عنصر دیگه‌ای بوده که باهاش مواجهه نشدیم پس هنوز کارمون تموم نشده و در همون جهت عقربه‌های ساعت ادامه میدیم.خب کاری که میکنیم اینه. با مثال دوم شروع می‌کنیم. char *str[5];از خودمون میپرسیم مثلا str چیه؟ جواب اینه : str یک ... خب تا اینجا رو داشته باشین.از str شروع کنین یه ساختار حلزون مانند در جهت عقربه های ساعت بکشین. مثل پایین :ساختار حلزونی در جهت ساعت‌گردخب میبینیم که اول با ] رو به رو شدیم. پس یک آرایه است. جوابمون رو اینجور اصلا میکنیم(طبق قرار دادهامون) :"امم str یک آرایه با سایز ۵ است که ..."خب اگه مارپیچ رو دوباره نگاه کنین میبینیم که با * مواجه شدیم. پس جوابمون رو اینجوری اصلاح میکنیم :"امم str یک آرایه با سایز ۵ است که اشاره می‌کند به ..."حالا میبینیم که با ; مواجهه شدیم ولی هنوز عنصری هست که باهاش مواجه نشدیم( char ) پس طبق قرار دادی که بالاتر با هم داشتیم هنوز کارو باید ادامه داد. خب میبینیم که با char مواجه شدیم. جوابمون رو به صورت زیر اصلاح میکنیم. "امم str یک آرایه با سایز ۵ است که اشاره می‌کند به نوع char"خب میبینیم که با همه عناصر از جمله ; هم مواجهه شدیم پس کارمون تمومه و سوال و جواب نهاییش اینه : بهم بگو str تو عبارت بالا چیه ؟ - امم str یک آرایه با سایز ۵ است که اشاره می‌کند به نوع charآفرین هوراااا ...خب حالا فرض کنین با این رو به رو هستیم : char *(*fp)(int, float *); یک مثال سخت تراز خودمون میپرسیم که مثلا fp چیه؟ خب حواب ما فعلا اینه :"امم fp یک ..."مارپیچ رو نگاه کنین. از fp شروع کردیم در جهت عقربه‌های ساعت پیش میریم. به ( یعنی پرانتز بسته رسیدیم. پس باید طبق قرارداد بالا کار رو تو داخل پراتتز ادامه بدیم. پس اول میبینین که با * رو به رو شدیم. جواب ما تا اینجا به این صورت تغییر میکنه :"امم fp یک اشاره‌گر به(اشاره میکند به) ..."حالا تمام عناصر داخل پرانتز رو باهاش مواجه شدیم. حالا در جهت عقربه های ساعت باز مارپیچ رو ادامه میدیم و مواجه میشیم با ) طبق قرارداد بالا باید جملمون اینجور کنیم :"امم fp یک اشاره‌گر به تابعی است که یک int و یک اشاره‌گر به float به آن پاس داده میشود، و برمیگرداند ..."حالا مواجه میشیم با *. جملمون اینجوری میشه :"امم fp یک اشاره‌گر به تابعی است که یک int و یک اشاره‌گر به float به آن پاس داده میشود، و برمیگرداند یک اشاره‌گر به ..."در ادامه با ; رو به رو میشیم ولی چون هنوز با همه عناصر رو به رو نشدیم طبق قرار داد بالا باید ادامه بدیم. رو به رو میشیم با char. جملمون اینجور میشه :"امم fp یک اشاره‌گر به تابعی است که یک int و یک اشاره‌گر به float به آن پاس داده میشود، و برمیگرداند یک اشاره‌گر به نوع chat"با همه عناصر مواجه شدیم و کار تمومه ... Yoda Yoda Fri, 24 Dec 2021 11:35:18 +0330