2-2-12- درس: ساختمان داده‌ها
1401/09/21 15:05فصل قبل
سرفصل: مقدمه
مطلب درسي: تعريف ساختمان داده‌ها
به ساختارهايي که جهت دريافت داده‌ها به شکل مناسب توسط کامپيوتر براي پياده‌سازي و اجراي الگوريتم‌هاي مختلف مورد استفاده قرار مي‌گيرند، «ساختمان داده‌ها» گفته مي‌شود.[1]
انسان را نيز مي‌توان همچون رايانه‌اي دانست که سازنده آن (خداوند متعال) برايش برنامه‌اي تهيه کرده است. اين برنامه در ادبيات مذهبي «دين» ناميده مي‌شود. همان گونه که يک برنامه رايانه‌اي متشکل از يک بخش ساختاري موسوم به «ساختمان داده‌ها»، و يک بخش عملياتي موسوم به «الگوريتم» است، دين الهي نيز به طور مشابهي شامل يک بخش ساختاري موسوم به «اصول اعتقادي دين» و يک بخش عملياتي موسوم به «اخلاق و احکام دين» است.
در ميان شريعت‌هاي مختلف الهي، شريعت حضرت محمد a نيز داراي يک ساختار اعتقادي است که مذاهب مختلف اعم از شيعه با تمامي شعب آن[2] و سني با تمام شعب آن[3] در اين ساختار جا گرفته و احکام حقوقي و فقهي مترتب بر مسلمان بر همگي صادق است. زيرا به هر سه بخش ساختاري (اصول اعتقادي دين) يعني توحيد، نبوت و معاد ايمان دارند. اما پيروان ساير شريعت‌ها همچون يهوديان، مسيحيان، زرتشتيان و . . . چون به طور کامل در اين ساختار قرار نمي‌گيرند (يعني به بخشي از نبوت اعتقاد ندارند)، مشمول چنين احکامي نيستند.
البته همانگونه که در مباحث ساختمان داده‌ها تنها صحبت از ساختار ذخيره‌سازي و ارتباطي اطلاعات کافي نيست و بايستي به فرآيندها و عمليات پايه‌اي تعريف شده بر روي ساختارهاي مذکور نيز توجه شود، در دين الهي نيز مناسک و ساختارهاي ظاهري و پوسته‌اي وجود دارد که تنها با فرآيندها و عمليات باطني در وجود مومن، معناي واقعي خود را يافته و حقيقتاً در زندگي شخصي و اجتماعي فرد تاثير گذار خواهد بود.
سرفصل: صف (Queue)
مطلب درسي: آشنايي با ساختار صف
هر ساختاري از داده‌هاي پشت سر هم ذخيره شده، که در آن عمل درج از يک طرف (انتها) و عمل حذف از طرف ديگر (ابتدا) انجام مي‌شود، را «صف» گويند. در اين ساختار اولين ورودي از همه زودتر خارج مي‌شود. اين سياست اساس کار صف‌ها را تشکيل مي‌دهد و به مفهوم آن است که اولين داده ذخيره شده در صف، نخستين داده‌اي است که بازيابي مي‌شود. اصطلاح FIFO سرواژه عبارت First In First Out است که براي بيان همين حقيقت به کار مي‌رود.[4]
اين قاعده که آنکه زودتر آمده بايد زودتر از صف خارج شود مسئله اي است که عقل نيز در ادراکات خويش آن را تأييد کرده، و شرع نيز بر آن مهر تأييد مي نهد. از طرفي مفهوم صف نيز در نظام‌هاي اجتماعي فراوان کاربرد دارد. از صف اتوبوس، نانوايي، بخش پاسخگويي يک اداره بگيريد تا صف انتظار وام در يک بانک. و از آنجا که مفهوم مهم «حق‌الناس» صرفاً به دارايي‌هاي مادي مردم و غصب آنها تعلق نمي‌گيرد، همين بي‌نوبتي‌هاي متأسفانه رايج در صف‌ها و نوبت‌هاي مختلف در نظام‌هاي اجتماعي را نيز شامل مي‌شود. بنابراين قطعا اين رفتارها نوعي «حق‌الناس» بوده و انسان مؤمن بايستي از افتادن در وادي آنها احتراز نمايد.
سرفصل: مقدمه
مطلب درسي: ADT: «انواع داده‌اي انتزاعي»
ADT يا «انواع داده‌اي انتزاعي» را در کتاب‌هاي ساختمان داده‌ها به قلعه تشبيه مي‌کنند. قلعه‌اي که در عين آنکه با دنياي پيرامون خود تعامل دارد، اما اجازه دخالت در ساختار و فرآيندهاي داخلي خود را نمي‌دهد! با اين روش، کيفيت روشهاي توليد نرم‌افزار ارتقاء يافته و بروز مشکلات مختلف در هنگام پياده‌سازي کاهش مي‌يابد.[5]
به همين صورت مي‌توان در مورد مفهوم و فوايد استقلال يک جامعه نيز نظر داد. ما بايد در عين آنکه با ساير جوامع تعامل تحت کنترلي داريم، استقلال خود را نيز حفظ کرده و اجازه دخالت در امور داخلي خود را به ديگر کشورها ندهيم. از جمله در مقوله اقتصاد مي‌توانيم اين شيوه را به «اقتصاد مقاومتي» که يک اقتصاد درون‌زا و برون‌گرا است مرتبط بدانيم.
سرفصل: درخت‌ها
مطلب درسي: خواص درختهاي دودويي
«درختهاي دودوئي» يا Binary Trees نوعي از ساختمان‌هاي داده‌اي هستند که در علوم کامپيوتر بسيار پرکاربردند.[6] اين ساختارهاي داده‌اي خواص جالبي دارند که بعضي از آنها عبارتند از:
اگر ارتفاع درخت را h ، تعداد کل گره‌هاي آن را n ، تعداد بازوهاي تکميل نشده درخت را e ، تعداد گره‌هاي داراي دو فرزند را i و تعداد گره‌هاي برگ آن را b بناميم، آنگاه قواعد ذيل را داريم:
و و
در اينجا به چند نکته ساده در مورد شبکه‌هاي شرکتهاي هرمي (همچون گلدکوئست و صدالبته نه محدود به همين يک شرکت!) توجه کنيد. يک درخت دودويي دلخواه، منظم يا نامنظم، رسم کنيد. رئوس اين درخت بر سه نوع‌اند: رئوسي که راست و چپ آنها تکميل شده است، رئوسي که يک طرف آنها تکميل شده است و رئوسي که هيچ رأسي زيرشان نيست. تعداد اين سه دسته را بشماريد و مشاهده کنيد که تعداد رئوس گروه سوم دقيقاً يکي بيشتر از تعداد رئوس گروه اول است. اين قانون هميشه و در هر حالتي که شما فرض کنيد صادق است. به زبان گلدکوئستي، هميشه و در هر شرايطي تعداد کساني که موفق به پيدا کردن هيچ مشتري‌اي نشده‌اند يکي بيشتر از تعداد کساني است که به تعادل يک‌ويک رسيده‌اند!
اکنون به تعداد بازوهايي که هنوز تکميل نشده‌اند توجه کنيد؛ به ازاي هر رأس از گروه دوم، يک بازو و به ازاي هر رأس گروه سوم دو بازوي تکميل‌نشده وجود دارد. مشاهده کنيد که تعداد کل بازوهاي تکميل‌نشده دقيقاً يکي بيشتر از تعداد کل رئوس درخت است. اين قانون نيز هميشه صادق است. به زبان گلدکوئستي، يکي بيشتر از کل تعدادي که الان عضو شبکه هستند، عضو جديد بايد اضافه شود تا همه افراد کنوني دست کم به تعادل يک‌ويک برسند!
در هر درخت دودويي تعداد رئوسي که تعادلشان دست‌کم يک است کم‌تر از نصف، تعداد رئوسي که تعادلشان دست‌کم سه است کم‌تر از يک چهارم، تعداد رئوسي که تعادلشان دست‌کم شش است کم‌تر از يک هفتم، و تعداد رئوسي که تعادلشان دست‌کم نه است کم‌تر از يک دهم کل رئوس است. با رسم چند درخت مختلف درستي اين موضوع را بررسي کنيد. توجه کنيد که در شبکه‌هاي شرکت گلدکوئست براي دريافت پنجاه دلار، دويست و پنجاه دلار، پانصد دلار، و هفتصد و پنجاه دلار پورسانت، بايد به ترتيب به تعادل يک، سه، شش، و نه رسيد.
آيا سزاست که يک دانشجو که مباحث ساختمان داده‌ها را مطالعه کرده است به آساني به دام فعالان شبکه‌هاي هرمي بيفتد؟!
[1]. ساختمان داده ها درC ، ص 52.
[2]. اثني عشري، زيدي، علوي، اسماعيليه و . . .
[3]. شافعي، حنفي، حنبلي، مالکي و . . .
[4]. ساختمان داده ها به زبان++C، صص 125-126.
[5]. ساختمان داده ها در C ،ص 26.
[6]. ساختمان داده ها در C ، ص 235.