ساختار داده و الگوریتم‌ ها — راهنمای مقدماتی

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

• رابط (Interface) - هر ساختار داده‌ای یک رابط دارد. رابط مجموعه عملیات‌هایی که از این ساختار داده پشتیبانی می‌کنند را شامل می‌شود. یک رابط تنها فهرستی از عملیات‌های مورد پشتیبانی، نوع پارامترهایی که می‌پذیرند و نوع بازگشتی این عملیات‌ها را ارائه می‌دهد.
• پیاده‌سازی (Implementation) - منظور از پیاده‌سازی ارائه بازنمایی داخلی از ساختار داده است. پیاده‌سازی تعریفی از الگوریتم‌های مورد استفاده در عملیات‌های ساختار داده ارائه می‌دهد.

خصوصیات ساختار داده

• درستی (correctness) – پیاده‌سازی ساختار داده باید رابط آن را به طور درستی اجرایی کند.
• پیچیدگی زمانی (Time Complexity) – زمان اجرای عملیات‌های ساختار داده باید تا حد امکان کوتاه باشد.
• پیچیدگی فضایی (Space Complexity) – میزان استفاده از حافظه در عملیات‌های ساختار داده باید تا حد امکان کم باشد.

فیلم آموزش ساختمان داده ها در فرادرس

کلیک کنید

نیاز به ساختار داده

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

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

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

موارد زمان اجرایی

سه حالت هستند که در آن‌ها معمولاً زمان اجرای عملیات‌های ساختار داده به روشی نسبی با هم مقایسه می‌شود:

• بدترین حالت – این سناریویی است که در آن عملیات‌های ساختار داده خاصی بیشترین زمان ممکن را به خود اختصاص می‌دهند. اگر بدترین حالت زمانی برای یک عملیات به صورت (f(n باشد، که (f(n نشان دهنده تابع n است، در این صورت این عملیات هیچ گاه زمانی بیش از (f(n طول نمی‌کشد.
• حالت میانی – در این سناریو زمان اجرایی متوسطی برای یک عملیات ساختار داده توصیف می‌شود. اگر یک عملیاتی زمان اجرایی (f(n طول بکشد، در این صورت اجرای m عملیات در مجموع به زمانی برابر با (mf(n نیاز خواهند داشت.
• بهترین حالت – در این سناریو کمترین زمان اجرایی برای یک عملیات محاسبه می‌شود. اگر یک عملیات در مدت زمان (f(n اجرا شود، در این صورت عملیات واقعی در طی مدت زمانی تصادفی به پایان می‌رسد که مقدار بیشینه آن (f(n است.

اصطلاحات مقدماتی ساختار داده

فیلم آموزش ساختمان داده ها – مرور و تست کنکور ارشد در فرادرس

کلیک کنید

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

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

راه‌اندازی محیط محلی

در این بخش یک محیط برای برنامه‌نویسی به زبان C آماده‌سازی می‌کنیم و به این منظور به دو ابزار نیاز داریم: (الف) یک ویرایشگر متنی و (ب) کامپایلر C.

ویرایشگر متنی

از این ویرایشگر برای نوشتن برنامه استفاده می‌شوند. نمونه‌هایی از چند ویرایشگر که می‌توانید مورد استفاده قرار دهید برنامه Notepad ویندوز، دستور Edit در سیستم عامل مک، Brief، Epsilon، EMACS و vim یا vi هستند. اما در هر صورت یکی از بهترین ویرایشگرهای متنی برای هر پلتفرمی برنامه ++Notepad محسوب می‌شود. نام و نسخه هر ویرایشگر متنی برای سیستم‌های مختلف ممکن است متفاوت باشد. برای مثال در سیستم ویندوز می‌توان از نت پد استفاده کرد. از vim یا vi نیز می‌توان در ویندوز یا لینوکس و یونیکس بهره گرفت.

در هر صورت فایل‌هایی که با استفاده از ویرایشگر متن ایجاد می‌کنید، به نام فایل‌های منبع یا سورس نامیده می‌شوند و شامل کد منبع برنامه است. فایل‌های منبع زبان C به طور معمول دارای پسوند «C.» است. پیش از آغاز برنامه‌نویسی مطمئن شوید که یک ویرایشگر متنی در اختیار دارید و تجربه کافی در زمینه نوشتن یک برنامه کامپیوتری دارید، سپس فایل را ذخیره کرده و آن را کامپایل کنید. در نهایت می‌توانید این فایل را اجرا کنید.

کامپایلر C

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

از کامپایلر زبان برنامه‌نویسی C برای کامپایل کردن فایل‌های سورس C به صورت برنامه نهایی استفاده می‌شود. ما فرض می‌کنیم که دانشی مقدماتی در مورد کامپایلر یک زبان برنامه‌نویسی دارید. یکی از متداول‌ترین کامپایلرهایی که به طور رایگان برای زبان C وجود دارد، کامپایلر GNU++ C/C نام دارد. البته می‌توانید در صورتی که از سیستم‌های عامل مربوط به HP یا Solaris استفاده می‌کنید از کامپایلرهای آن‌ها نیز استفاده کنید. در بخش بعدی شیوه نصب کامپایلر GNU++ C/C بر روی سیستم‌های عامل مختلف توضیح داده شده است. ما به این دلیل به هر دو زبان C و ++C اشاره می‌کنیم، چون برای کامپایل هر دو زبان C و C++ استفاده می‌شود.

نصب روی یونیکس/لینوکس

اگر از سیستم لینوکس یا یونیکس استفاده می‌کنید، در این صورت می‌توانید با تایپ دستور زیر در خط فرمان بررسی کنید که آیا GCC بر روی سیستم شما نصب شده است یا نه:

$ gcc -v

اگر کامپایلر GCC بر روی رایانه شما نصب شده باشد، در این صورت در خروجی دستور فوق پیامی به صورت زیر نمایش می‌یابد:

Using built-in specs.
Target: i386-redhat-linux
Configured with:../configure --prefix = /usr .......
Thread model: posix
gcc version 4.1.2 20080704 (Red Hat 4.1.2-46)

اگر GCC نصب نشده باشد، در این صورت باید خودتان آن را نصب کنید. بدین منظور می‌توانید از راهنمای تفصیلی در این آدرس استفاده کنید. این راهنما بر مبنای لینوکس به نگارش در آمده است و نمونه‌هایی که در ادامه خواهند آمد بر روی توزیع CentOS از سیستم عامل لینوکس متمرکز شده‌اند.

نصب روی ویندوز

برای نصب GCC روی ویندوز باید ابتدا MinGW را نصب کنید. برای نصب MinGW به صفحه اصلی وب‌سایت آن مراجعه کنید و به لینکی که به صفحه دانلود MinGW اشاره دارد بروید. در این صفحه، آخرین نسخه از برنامه نصب MinGW را دانلود کنید. عنوان این فایل معمولاً به صورت MinGW-<version>.exe است. هنگام نصب MinGW دست کم باید موارد زیر روی سیستم نصب شوند: cc-core, gcc-g++، binutils و MinGW runtime. البته می‌توانید موارد دیگری را نیز برای نصب انتخاب کنید. شما باید زیرشاخه bin در محل نصب MinGW را به متغیر محیطی PATH سیستم عامل اضافه کنید، تا بتوانید این ابزارها را در محیط خط فرمان صرفاً با استفاده از نام‌هایشان فراخوانی کنید. زمانی که مراحل نصب پایان یافت، می‌توانید ابزارهای gcc، g++، ar، ranlib، dlltool و چند ابزار دیگر را از خط فرمان ویندوز اجرا کنید.

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

• آموزش ساختمان داده ها
• مجموعه آموزش‌های علوم کامپیوتر
• مجموعه آموزش‌های دروس مهندسی کامپیوتر
• پایگاه داده و سیستم های مدیریت اطلاعات
• مجموعه آموزش‌های برنامه نویسی
• آموزش ساختمان داده در پایتون

==