تاریخ بروزرسانی : 1400/09/20
نام بسته درسی : ساختمان داده ها
———————–
فهرست:
فصل اول – مفاهیم
ساختار برنامه در C++
دامنه (scope) در C++
دستورات و عملگرهای C++
تعریف داده در C++
تخصیص حافظه پویا در C++
مشخصات الگوریتم
نکات مهم
فصل دوم – آرایه ها
نوع داده مجرد و کلاس C++
آرایه به عنوان یک نوع داده انتزاعی
نوع داده انتزاعی چند جملهای
ماتریسهای پراکنده (اِسپارس)
نمایش آرایهها
نوع داده انتزاعی رشته
فصل سوم – پشته ها و صف ها
الگوها در C++
نوع داده انتزاعی پشته
نوع داده انتزاعی صف
مسأله مسیر مارپیچ (MAZING)
ارزیابی عبارتها
پشته و صف چندتایی
فصل چهارم – لیست های پیوندی
لیستهای تک پیوندی
نمایش لیستها در C++
لیستهای حلقوی
پشتهها و صفهای پیوندی
چند جملهایها
کلاسهای همارزی
ماتریسهای پراکنده
لیستهای پیوندی دوگانه
فصل پنجم – درختان
مقدمه
درختان دودویی
پیمایش درخت دودویی و تکرارکنندههای درختان
درختان نخی دودویی
هرمها (HEAPS)]
درختان جستجوی دودویی
درختان انتخاب
جنگلها
شمارش درختان دودویی
فصل ششم – گراف ها
نوع دادۀ انتزاعی گراف
عملکردهای مقدماتی گرافها
فصل هفتم – مرتب سازی
مرتبسازی درجی (INSERTION SORT)
با چه سرعتی میتوانیم عمل مرتبسازی را انجام دهیم؟
مرتبسازی ادغام
مرتبسازی براساس چند کلید (مبنا)
مرتبسازی خارجی
فصل هشتم – درهم سازی
نوع داده انتزاعی جدول نمادی
درهم سازی ایستا
منابع و مآخذ
بخش هایی از بسته درسی ساختمان داده ها
تعریف: نوع داده مجرد یا انتزاعی (ADT) نوعی داده است که مشخصات اشیاء و مشخصات اعمالی که برروی آنها انجام میشوند از نمایش اشیاء و پیادهسازی آن اعمال کاملاً متمایز میباشد.
در سراسر این بسته، بر تفاوت بین مشخصات و پیادهسازی تأکید خاصی شده است. برای انجام این موضوع، کار خود را با تعریف ADT شیء مورد مطالعه شروع میکنیم. بدین ترتیب خوانند میتواند بدون درگیر شدن با پیچیدگی نمایش یا پیادهسازی واقعی عملکردها به عناصر اصلی اشیاء دست یابد. هنگامی که ADT کاملاً تشریح شد، مبحث نمایش و پیادهسازی را مطرح میکنیم. این مباحث در مطالعه ساختمان دادهها از اهمیت ویژهای برخوردار است. برای رسیدن به چنین هدفی، نشانهگذاری را برای بیان یک ADT معرفی میکنیم. این نشانهگذاری کاملاً از قواعد زبان C++ مستقل است. بعداً مشاهده خواهید نمود که چگونه قواعد کلاس C++ را برای بیان ADT بکار میبریم.
مثال: 1-1: [نوع داده انتزاعی اعداد طبیعی]: بعنوان اولین مثال ADT، لازم است زمان بیشتری را صرف توضیح این نشانهگذاری کنیم. ADT شماره 1-1 شامل تعریف ADT اعداد طبیعی است. تعریف با نام نوع داده انتزاعی شروع میشود. این تعریف از دو بخش مهم و اصلی تشکیل شده است: اشیاء و توابع. در این مثال، اشیاء اعداد صحیح هستند که هیچ اشاره صریحی به نمایش آنها نخواهیم داشت. تعاریف توابع تا حدی پیچیدهتر هستند. در ابتدا تعاریف از دو نماد x و y برای نمایش دو عضو مجموعه اعداد طبیعی استفاده میکنند. TRUE و FALSE عناصر مجموعه مقادیر بولی هستند. علاوه بر این، تعریف از توابعی که بر روی مجموعه اعداد صحیح مانند جمع، تفریق، تساوی و کمتر از، تعریف شده است استفاده میکند. این مسئله بیانگر این واقعیت است که برای تعریف یک نوع داده، ممکن است نیازمند استفاده از عملکردهای نوع داده دیگر نیز باشیم.
برای هر تابع، نوع نتیجه و تعریف آن را در سمت راست نام تابع میآوریم. نماد ترکیبی “::=” باید ”به صورت … تعریف میشود” خوانده شود.
اولین تابع، Zero، فاقد هرگونه آرگومانی است و عدد طبیعی صفر را باز میگرداند. تابع Successor (x) در دنباله اعداد طبیعی عدد طبیعی بعد از x را برمیگرداند. توجه کنید که اگر در این دنباله عدد بعدی وجود نداشته باشد، یعنی اگر مقدار x برابر با MAXINT باشد، Successor را طوری تعریف میکنیم که MAXINT را بازگرداند. بعضی از برنامهنویسان ترجیح میدهند در چنین حالتی، Successor یک پیام خطا بازگرداند که البته این توصیه هم کاملاً مجاز و منطقی میباشد. در اینجا توابع دیگر Add و Subtract هستند. آنها هم ممکن است یک پیغام خطا بازگردانند، هرچند در اینجا ترجیح میدهیم عنصری از مجموعه NaturalNumber را برگردانیم.□
اکنون مشاهده میکنیم که قوانین انتزاع (تجرد) و مخفیسازی دادهها چگونه در ساختن برنامههایی با طراحی مناسب به طور مؤثر به ما کمک میکنند.
1) سادهسازی فرآیند طراحی و تولید نرمافزار: در حقیقت مزیت مهم انتزاع دادهها این است که تجزیه کار پیچیده تولید یک سیستم نرمافزاری به تعدادی زیر وظیفه سادهتر را آسان میکند. مسئله زیر را در نظر بگیرید: مسئلهای به یک برنامهنویس یا به یک تیم از برنامهنویسان واگذار شده است. فرض کنید با مرور از بالا به پایین این مسئله تصمیم بر این شده است که سه نوع داده A، Bو C به همراه تعدادی دستور اضافی (که ما آنها را در اینجا چسب مینامیم) استفاده شود. این دستورهای اضافی برای سهولت ارتباط بین این سه نوع، در نظر گرفته شدهاند. همچنین فرض کنید خصوصیات هر نوع داده در ابتدا مشخص شده است، به عبارت دیگر، اعمالی که نوع داده باید پشتیبانی کند کاملاً مشخص شده است.
ADT Natural Number is
Objects: An ordered sybrange of the integers starting at zero and ending at the maximum integer (MAXINT) on the computer.
Functions:
For all x, y Natural Number; TRUE, FALSE Boolean
And where +,-,<,==<and= are the usual integer operations
Zero (): Natural Number ::= 0
IsZero (x): Boolean ::= if (x==0) IsZero= true
Else IsZero = false
Add (x, y): Natural Namber ::= if (x+ y<= MAXINT) Add= x+ y
Else Add=MAXINT
Equal (x, y): Boolean ::= if (x== y) Equal= TRUE
Else Equal= FALSE
Successor (x): Natural Number ::= if (x== MAXINT) Successor= x
Else Successor = x+ 1
Subtract (x, y): Natural Number ::= if (x< y) Sybtract=0
Else Subtract= x- y
End Natural Number
ADT شماره1-1 : نوع داده انتزاعی Natural Number
الف) سناریوی 1- تیمی متشکل از چهار برنامهنویس: زیر وظیفهها را میتوان به صورت زیر بین اعضاء تیمی متشکل از چهار برنامهنویس تقسیم کرد. هر یک از سه نوع داده به یک برنامهنویس واگذار میشود. کار هر برنامهنویس پیادهسازی نوع داده خودش بر طبق مشخصاتی است که قبلاً در مورد آن توافق شده است. چهارمین برنامهنویس، چسب (glue) را با این فرض که نوع دادهها واقعاً بر طبق مشخصات پیادهسازی شدهاند، پیادهسازی میکند. هیچ یک از برنامهنویسها نیاز نیست بداند سایر برنامهنویسان چگونه بخش مربوط به خود را پیادهسازی میکنند. بنابراین، هر برنامهنویس میتواند حواس خود را منحصراً به کد بخش خود معطوف کند بدون هیچگونه نگرانی راجع به این که دیگران چه میکنند و چگونه ممکن است به آنچه او انجام میدهد اثر بگذارند.
ب) سناریوی 2- یک برنامهنویس: در اینجا، انتزاع دادهها به برنامهنویس کمک میکند تا مواردی که در هر زمان نیاز به نگهداری آنها در حافظه خود دارد را کاهش دهد. در این مثال، برنامهنویس هر نوع داده را یکی یکی با توجه به مشخصات آنها پیادهسازی میکند. بنابراین وقتی که برنامهنویس نوع داده A را پیادهسازی میکند هیچگونه نگرانی راجع به نوعهای داده B و C و چسب ندارد. بعد از اینکه هر کدام از انواع داده به تنهایی پیادهسازی شدند، برنامهنویس میتواند توجه خود را به چسب معطوف کند. در اینجا وی دیگر کاری به اینکه چگونه آن سه نوع داده را پیادهسازی کرده، ندارد بلکه باید به چگونگی استفاده عملکردها برروی آنها دقت کند تا به اهداف خواسته شده برسد.
2) آزمایش و رفع اشکال: شکستن یک برنامه (وظیفه) پیچیده به تعدادی زیر برنامه (زیروظیفه) سادهتر، امتحان و رفع اشکال برنامه را نیز سادهتر میسازد. در مثال بالا، هر نوع داده میتواند به طور جداگانه امتحان و رفع اشکال شود. بعد از اینکه هر نوع داده آزمایش و رفع اشکال شد، تمام برنامه را میتوان آزمایش کرد. اگر خطایی در این مرحله پیدا شود احتمال اینکه این خطا از ساختار دادههای A، B و C بسیار کم است، زیرا همه آنها قبلاً آزمایش شدهاند. بنابراین خطا به احتمال زیاد مربوط به چسب است اکنون این حالت را با حالتی مقایسه کنید که میخواستیم این اشکالات را در برنامهای که در آن انتزاع دادهها استفاده نشده بود پیدا کنیم. به سادگی دیده میشود که به کار گرفتن انتزاع دادهها در توسعه نرمافزارها، کارآیی آزمایش و رفع خطا را بسیار افزایش میدهد.
3) قابلیت استفاده مجدد: تجرد و مخفیسازی دادهها باعث ایجاد ساختمان دادههایی میشود که به صورت نهادهای مجزا از یک سیستم پیادهسازی میشود. این امر کار استخراج کدهای یک ساختمان داده و عملکردهای آن از یک سیستم نرمافزاری و استفاده آن در یک سیستم دیگر را نسبت به حالتی که این ساختمانها به صورت پیچیده همراه با سیستم اصلی پیادهسازی شده باشند، را سادهتر میسازد. بعداً روشهای دیگر C++ برای افزایش قابلیت استفاده مجدد را توضیح خواهیم داد.
ساختار برنامه در C++
مانند C، یک برنامه C++ معمولاً در بیشتر از چندین فایل بسط پیدا میکند. دو نوع فایلی که درC++ استفاده میشوند: فایلهای سرآمد (Header files) و فایلهای برنامه (Source files) هستند. فایلهای سرآمد پسوند h. دارند و برای ذخیره کردن تعاریف (اعلانها) بکار برده میشوند. فایلهای برنامه برای ذخیرهسازی دستورات و کد برنامه C++ استفاده میشوند. پسوندی که برای فایلهای برنامه بکار برده میشود بستگی به نوع کامپایلر دارد. ما از پسوند C. برای فایلهای برنامه استفاده میکنیم. فایلهای سرآمد با استفاده از دستور پیشپردازنده #include در فایل مطلوب گنجانده میشوند.
قبل از این که یک برنامه C++ بتواند اجرا شود، فایلهای برنامه آن باید هر کدام به صورت جداگانه کامپایل شوند، به یکدیگر متصل (link) و سپس بارگیری (load) شوند. چون یک برنامه C++ معمولاً دارای تعداد زیادی فایل برنامه و فایل سرآمد است، این امکان وجود دارد که یک فایل سرآمد چندین بار در برنامه گنجانده شود که باعث خطای کامپایل میشود. برای این که مطمئن شویم که یک فایل سرآمد دوبار گنجانده نمیشود، مندرجات آن را در بین دستورات پیشپردازنده زیر قرار میدهیم.
#ifndef FILENAME_ H
# define FILENAME_H
//مندرجات یک فایل سرآمد در اینجا قرار میگیرد
.
.
.
#endif
نتیجه دیگر استفاده از چندین فایل برنامه این است که فرآیند تایپ دستورات کامپایل هر بار که برنامه را تغییر میدهیم و دوباره کامپایل میکنیم نسبتاً خستهکننده میشود. برای اجتناب از این کار خستهکننده، پیشنهاد میکنیم از امکان make در UNIX یا معادل آن برای نگهداری (ادامه) یک برنامه C++ استفاده کنیم. Make علاوه بر کاهش زحمت نوشتن دستورات کامپایل، فایلهایی که تغییرات اعمال شده تأثیری بر آنها نگذاشته را دوباره کامپایل نمیکند و در نتیجه زمان کمتری صرف میشود.
دامنه (scope) در C++
سؤال دیگری که در نتیجه استفاده از چندین فایل در یک برنامه ساده به وجود میآید در مورد قابلیت رویت یک متغیر است که در یک فایل تعریف شده و در فایلهای دیگر نیز از آن استفاده میشود. برای این منظور نگاه کوتاهی به دامنه برنامه در C++ میاندازیم. متن یک برنامه C++ میتواند در یکی از چهار دامنه زیر باشد:
دامنه فایل: تعاریف و اعلانهایی که جزو تعاریف یک تابع یا یک کلاس نباشند به دامنه فایل تعلق دارند.
دامنه تابع: برچسبها در هر جای تابعی که در آن تعریف شدهاند میتوانند مورد استفاده قرار گیرند. فقط برچسبها هستند که دامنه تابعی دارند. از آنجایی که برچسبها فقط برای مقصد عبارت goto مورد استفاده قرار میگیرند؛ و از آنجایی که از عبارت goto به دلیل اینکه برنامه را را غیر ساخت یافته میکند استفاده نمیکنیم، با این نوع دامنه برنامه، کاری نخواهیم داشت.
دامنه محلی: نامی که در یک بلاک تعریف میشود متعلق به دامنه محلی است که شامل آن بلاک میباشد. این نام همچنین میتواند توسط زیربلاکهای موجود در بلاکی به کار گرفته شود که در آن تعریف شده است.
دامنه کلاس: تعاریف (اعلانهای) واقع در تعیف یک کلاس به دامنه کلاس تعلق دارند. هر کلاس نشاندهنده یک دامنه کلاس مجزا است. کلاسها را با ذکر جزئیات بیشتر در فصل دوم بررسی خواهیم کرد.
هر متغیر دارای یک زمینه یا دامنه است. یک متغیر به وسیله دامنه و نامش به صورت منحصر به فردی شناخته میشود، و فقط در دامنه خود برای برنامه قابل رویست است. به عنوان مثال متغیری که در یک بلاک تعریف شده است فقط در همان بلاک قابل دسترسی است. در حالیکه، متغیری که در دامنه فایل تعریف شده باشد (متغیر سراسری) در همه جای برنامه قابل دسترسی است. بعضی سوالاتی که ممکن است در این مورد پیش آیند عبارتند از:
اگر نام یک متغیر محلی در یک بلاک همنام با یک متغیر سراسر باشد و بخواهیم از متغیر سراسری در آن بلاک استفاده کنیم، چه باید کرد:
راه حل: از عملکرد دامنه :: برای دستیابی به متغیر سراسری استفاده کنید.
یک متغیر سراسری در file 1.C تعریف شده است اما در file 2.C مورد استفاده قرار گرفته است.
چگونه این متغیر سراسری را در file 2.C اعلان کنیم؟ اگر متغیر سراسری را به همان صورت تعریف نکنیم پیغام «تعریف نشده است!» را میدهد.
راه حل: از کلمه کلیدی extern برای اعلان متغیر در file 2.C استفاده کنید.
فرض کنید در هر دو فایل file1.C و file 2.C برنامه، یک متغیر سراسری با نام یکسان تعریف شده است؛ حال آن که این دو متغیر سراسری به عنوان دو نهاد متفاوت در نظر گرفته شدهاند. چگونه برنامه را بدون تغییر نام متغیر سراسری در یکی از فایلها میتوانیم کامپایل کنیم؟
راه حل: از کلمه static برای تعریف متغیر در هر دو فایل استفاده کنید.
برای جزئیات بیشتر، به یکی از متون مقدماتی C++ که در بخش منابع در انتهای این فصل نام برده شدهاند، مراجعه کنید.
دستورات و عملگرهای C++
دستورات C++ همان قواعد و معانی دستورات C را دارند. دستورات C++ را بعداً در همین فصل در بخش “تحلیل کارایی و ارزیابی برنامه” مختصراً مرور میکنیم.
عملگرهای C++ نیز به جز دو استثنای new و delete عیناً همان عملگرهای C هستند. New و delete را به هنگام توضیح مدیریت حافظه پویا در C++ مختصراً بررسی خواهیم کرد. تفاوت دیگر این است که C++ از عملگرهای انتقال به چپ (>>) و انتقال به راست (>>) برای ورودی و خروجی استفاده میکند. این عملگرها را نیز مختصراً موقع بررسی ورودی/ خروجی در C++ مرور میکنیم. یک تفاومت مهم C و C++ این است که در C++ اضافه بار عملگر (operator overloading) مجاز است؛ بدین معنی که یک عملگر میتواند بسته به نوع عملوندهای بکار برده شده دارای چندین عملکرد متفاوت باشد. از این گذشته این عملکردها میتوانند توسط برنامهنویس تعریف شوند.
تعریف داده در C++
یک تعریف (اعلان) داده، انتساب یک نوع داده به یک نام است. حال انواع راههای تعریف داده در C++ را بررسی میکنیم. تمامی این روشهای تعریف داده بجز نوع مرجع در C نیز موجودند.
مقادیر ثابت: شامل الفاضی مانند ‘a’5 یا 4.3 هستند.
متغیرها: نمونههایی از انواع داده هستند که مقدارشان در حین اجرای برنامه قابل تغییر است.
متغیرهای ثابت: متغیرهایی هستند که در حین اجرای برنامه نمیتوان به آنها مقداری نسبت داد. بنابراین، باید مقداردهی اولیه شوند؛ به این معنی که محتوای آنها وقتی که تعریف میشوند باید یک مقدار مشخص بگیرد. نوع ثابت با اضافه کردن کلمه کلیدی const به ابتدای دستور اعلان، تعریف میشود (به عنوان مثال، const int MAX= 500;).
انواع شمارشی: یک روش دیگر برای تعریف سریهایی از اعداد ثابت صحیح است. همچنین بدین وسیله میتوان انواع داده جدیدی با دادن یک نام به نوع شمارشی ایجاد کرد:
Enum Boolean {FALSE , TRUE};
FALSEو TRUE ثابتهای صحیح از نوع منطقی (Boolean) هستند. مقادیر آنها به طور پیشفرض به ترتیب برابر 0 و1 است.
اشارهگرها: آدرس اشیاء را در خود نگهداری میکنند، به عنوان مثال
در اینجا np به عنوان اشارهگری به عدد صحیح تعریف شده و سپس آدرس متغیر صحیح i در آن قرار میگیرد. بنابراین، اکنون np اشارهگری است به عدد صحیحی که در متغیر i ذخیره شده است (در اینجا عدد 25).
نوشتههای تازه
آخرین دیدگاه ها