جزوه ساختمان داده ها

یک فیلم آموزشی ساختمان داده ها پسورد :arsanjan.blogfa.com              دانلود

سوالات ترم اول 93-92            دانلود

سوالات ترم دوم  ۸۹-۸۸      دانلود

سوالات ترم اول ۹۰-۸۹       دانلود

نمونه سوالات ساختمان داده ها دانشگاه پیام نور    دانلود2    دانلود۱

اغلب می خواهيم کليه گره های درخت را بررسی کنيم. چند روش برای پيمايش وجود دارد که در آنها گره ها می توانند پردازش يا ملاقات شوند. هر روش وقتی روی يک درخت دودويی اجرا می شود ويژگی های مفيدی را در اختيار می گذارد. سه روش معمول پيمايش درخت های دودويی روش های preorder، postorder و inorder است که در آنها هر گره و فرزندانش به طور بازگشتی ملاقات می شوند. هر سه پيمايش از ريشه درخت شروع می شوند. تفاوت آنها در ترتيب ملاقات گره و فرزندانش است. در روش preorder ابتدا گره ملاقات شود سپس فرزندانش. در روش postorder ابتدا فرزندان سپس خود گره ملاقات می شود. در روش inorder گره مابين فرزندان چپ و راست خود ملاقات می شود.

• يک max meap يك درخت دودوئي كامل است كه بزرگ هم باشد. در max heap بزرگترين مقدار هميشه در ريشه قرار می گيرد.
• يک min meap يك درخت دودوئي كامل است كه كوچك هم باشد. در min heap کوچکترين مقدار در ريشه قرار می گيرد.

يك درخت بزرگ (max tree) درختی است كه مقادير كليد هر گره بزرگتر از مقادير فرزندانش باشد. يعنی اگر B فرزند A است آنگاه key(A) key(B) است.

يك درخت كوچك (min tree) درختی است كه مقادير كليد هر گره كوچكتر از مقادير فرزندانش باشد. يعنی اگر B فرزند A است آنگاه key(A) key(B) است.

مثال. در شکل زير درخت (b) يک max heap است. درخت (a) يک درخت بزرگ است ولی max heap نيست چون يک درخت دودويی کامل نيست.

مثال. در شکل زير درخت (b) يک min heap است. درخت (a) يک درخت کوچک است ولی min heap نيست چون يک درخت دودويی کامل نيست.

وقتي عمليات جستجو، حذف و اضافه مدنظر باشد درخت جستجوی دودوئی از تمام ساختارهای ديگر مناسب‌تر است. يک درخت جستجوی دودويی (binary search tree) يا BST نوع خاصی از درخت دودويی است که اگر تهی نباشد خواص زير را دارا است:

• هر گره يك مقدار منحصر بفرد دارد.
• کليه مقادير فرزندان زيردرخت چپ هر گره از مقدار خود گره کوچکتر هستند.
• کليه مقادير فرزندان زيردرخت راست هر گره از مقدار خود گره بزرگتر هستند.

احتمالا پرکاربردترين ترين نوع درختی، درخت دودويی (binary tree) است. درخت های دودويی يک پياده سازی خاص از يک درخت m-ary است که در آن m=2 است يا به عبارت ساده تر هر گره حداکثر دو فرزند دارد که فرزند چپ و فرزند راست (يا زيردرخت چپ و زير درخت راست) ناميده می شوند. ترتيت قرار گرفتن گره ها در درخت دودويی کاملا اختياری نيست. درحقيقت نحوه درج گره های جديد در درخت دودويی ساختار و کاربرد آنرا تعيين می کند.

مثال. درخت های زير همگی دودويی هستند.

اصطلاحات

ساختمان داده درخت برای نمايش داده‌های سلسله ‌مراتبی به ‌كار می ‌رود و چون شبيه درخت رسم می شود ساختار درختی نامگذاری شده است. البته ساختار درختی در مقايسه با درخت واقعی معمولا به صورت وارونه رسم می شود، يعنی ريشه درخت در بالا و برگ های آن در پائين قرار می گيرند. به طور كلي يک درخت مجموعه ای از گره هاست که از طريق پيوندهايی با هم در رابطه هستند. هر گره دارای داده مرتبط و مجموعه ای از گره های ديگر است. در نظريه گراف يک درخت يک گراف متصل بدون دور است.

در ليست يک طرفه فقط می توانيم در يک جهت پيمايش کنيم. گاهی پيمايش روی ليست از هردوطرف مورد نياز است. بنابراين در هر گره به دو فيلد اشاره گر نياز است؛ برای اشاره به گره بعدی و گره قبلی که اغلب اشاره گرهای Left و Right ناميده می شوند. ليستی که شامل اين نوع گره باشد را ليست پيوندی دوطرفه (doubly-linked list) می نامند. شکل زير ساختار گره را نشان می دهد.

اگر ليست به صورت افقی ترسيم شود اشاره گرهای Right برای پيمايش ليست از چپ به راست (از ابتدا به انتها) استفاده می شوند. توسط اشاره گرهای Left می توان در صورت نياز به گره قبلی برگشت. بنابراين امکان پيمايش ليست در هردو جهت وجود دارد.

typedef int ItemType;
typedef struct Node
{
ItemType Info;
Node * Right, * Left;
};
typedef Node * NodePtr;

همين طور که در شکل ديده می شود اشاره گر Left اولين گره و اشاره گر Right آخرين گره ليست NULL هستند که نشان دهنده ابتدای هر جهت می باشند.

يک ليست پيوندی يک طرفه (Singly-linked list) دنباله ای از عناصر داده ای به نام گره(node) است که ترتيب خطی آنها توسط اشاره گرها تعيين می گردد. عناصر ليست تنها می توانند به ترتيب از ابتدای ليست تا انتها مورد دسترسی قرار بگيرند. هر گره آدرس گره بعدی را شامل می شود که به اين صورت امکان پيمايش از يک گره به گره بعدی فراهم می شود. برای رسم ليست پيوندی گره ها به صورت مستطيل هائی پشت سرهم رسم می شوند که توسط فلش هائی بهم متصل شده اند.

مقدار ثابت NULL برای علامتگذاری انتهای ليست در اشاره گر آخرين گره ذخيره می شود. ليست توسط يک اشاره گر Head که آدرس اولين گره ليست را در خود ذخيره می کند قابل دسترس است. بقيه عناصر توسط جستجوی خطی بدست می آيند.

صف لیست مرتبی است كه عناصر در انتهای آن (Rear) اضافه و از ابتدای آن(Front) حذف می شوند. به عبارت ديگر طول صف از انتهای آن افزایش و از ابتدای آن كاهش می یابد.  اولين عنصری که وارد صف می شود اولين عنصری است که از صف خارج می شود. بنابراين عناصر به همان ترتيبی که به صف اضافه می شوند از آن حذف می شوند. به همين دليل به صف لیست FIFO (first in, first out) نیز گفته می‌شود.

این برنامه وظیفه  اضافه کردن به صف و حذف از صف را بر عهده دارد که به زبان ‍‍++C مي باشد براي ديدن برنامه روي ادامه مطلب كليك كنيد.

2. برنامه ای بنويسيد كه اطلاعات مربوط به يك جدول 5×10 را دريافت كرده تعيين كند كه آيا هيچ دو سطری برابر هستند يا خير.

3. برنامه ای برای جمع دو ماتريس خلوت بنويسيد. ماتريس های به روش point access method ذخيره شده اند.

4. برنامه ای بنويسيد که بيشترين و کمترين مقدار را در يک آرايه دوبعدی پيدا کند.

5. برنامه ای که دو آرايه مرتب را با هم ادغام کرده در آرايه ديگری ذخيره کند.

به طور خلاصه مجموعه ای از دستوالعمل ها برای حل يک مسئله را الگوريتم می گويند. کلمه الگوريتم از نام رياضیدان قرن نهم ابوجعفرمحمد ابن موسی الخوارزمی گرفته شده است.
تعريف دقيق تر الگوريتـم به صورت زير است:

يک الگوريتم مجموعه ای متناهی از دستورات برای حل يک مسئله خاص توسط انسان يا ماشين است، که ترتيب انجام عمليات در آن مشخص شده و عمليات در زمان معينی خاتمه پيدا می کند. هر دستورالعمل در الگوريتم بايد مختصر، دقيق، و صريح باشد.

يک الگوريتم پنج خاصيت زير را بايد دارا باشد:

1. متناهی بودن. يک الگوريتم بايد هميشه بعد از تعدادی گام به پايان برسد.
2. صراحت. فعلی که در هر قدم الگوريتم انجام می گيرد بايد مختصر، صريح و غير مبهم باشد.
3. ورودی. مقاديری هستند که ابتدا، قبل از شروع، به الگوريتم داده می شوند.
4. خروجی. مقاديری هستند توسط الگوريـم توليد می شود و رابطه مشخصی با ورودی ها دارند.
5. کارائی. دستورات الگوريتم درحد کفايت بايد ساده و دقيق باشند تا يک انسان مانند يک روبات بتواند آنها را با استفاده از قلم و کاغذ بدون احتياج به فکر کردن در زمان معينی انجام بدهد.

الگوريتم ها قرن ها برای حل مسائلی که بشر با آنها روبرو بوده استفاده می شده اند. تقريبا کليه برنامه های کامپيوتر، بجز برنامه های کاربردی هوش مصنوعی، دربرگيرنده الگوريتم هستند. مشهورترين الگوريتم در تاريخ، الگوريتم اقليدسی، مربوط به زمان يونان باستان است که برای محاسبه بزرگترين مقسوم عليه مشترک دو عدد صحيح به کار می رفته است و هنوز در دنيای رياضی کاربرد دارد.

’’’ تجزیه و تحلیل یک الگوریتم ’’’ ، عبارتست از تعیین مقدار منابع مورد نیاز (مانند زمان و ظرفیت ذخیره سازی) برای اجرای آن . بیشتر الگوریتم ها طوری طراحی شده اند که با ورودی هائی با طولهای دلخواه کار کنند. معمولاً‌میزان ’’’ کارایی’’’ یا ’’’ پیچیدگی ’’’ یک الگوریتم بصورت تابعی بیان می شود که طول ورودی را به تعداد مراحل (’’’ پیچیدگی زمانی’’’) یا محل های ذخیره سازی (’’’ پیچیدگی فضائی یا حافظه’’’) مورد نیاز برای اجرای الگوریتم ارتباط می دهد.
تجزیه و تحلیل الگوریتم بخشی مهم از تئوری پیچیدگی محاسباتی گسترده است که تقریبهای نظری را برای منابع مورد نیاز هر الگوریتم که مسئله ای محاسباتی را حل می کند، فراهم می نماید. این تقریب ها موجب دستیابی به اطلاعات معقول برای تحقیق در مورد الگوریتم های کارا می شود.
در تجزیه و تحلیل نظری الگوریتم ها، معمول این است که پیچیدگی آنها را بصورت ’’’ تقریبی’’’ asymptotic تخمین بزنیم. بعنوان مثال برای تخمین زدن تابع پیچیدگی ورودهایی که واقعا طولانی هستند، از نمادهای O بزرگ ، امگا و تتا استفاده می گردد. مثلاً جستجوی دودوئیدر (log(n» O ، یا به اصطلاح « در زمان لگاریتمی »، مراحلی را طی می کند که متناسب با یک لگاریتم است. معمولا ً‌بدین دلیل از تخمین های تقریبی استفاده می شود، چون اجراهای متفاوت یک الگوریتم یکسان ممکن است از نظر میزان کارایی با هم متفاوت باشند. اما کارایی دو اجرای «معقول» یک الگوریتم خاص توسط یک فاکتور ثابت چند برابر کننده که «ثابت پنهان» نامیده می شود، به یکدیگر مرتبط می شوند.
اندازه گیری دقیق (نه تقریبی) کارایی اجرایی الگوریتم را می توان محاسبه کرد، ولی این کار معمولاً‌ نیازمند برخورد با موارد خاص در موقع اجرای الگوریتم است، که مدل محاسباتی خوانده می شود.
یک مدل محاسباتی را می توان بصورت یک کامپیوتر انتزاعی ، همانندماشین تورنیگ تعریف کرد، و یا با فرض این موضوع که اعمال خاصی در واحد زمان انجام می پذیرند، آنرا تعریف نمود. بعنوان مثال ، اگر مجموعه ای مرتب که جستجوی دودوئی را در مورد آن بکار می گیریم دارای n عنصر باشد، و بتوانیم تضمین کنیم که در هر واحد زمان فقط یکبار می توان عمل جستجوی دودویی را انجام داد، آنگاه حداکثر به واحد زمان احتیاج داریم تا پاسخ را بیابیم.
اندازه گیری های دقیق میزان کارایی اجرایی الگوریتمها، برای کسانی که حقیقتاً‌ الگوریتم ها را اجرا کرده و مورد استفاده قرار می دهند، مفید هستند ، زیرا این اندازه گیری ها دقیق تر است و بنابراین آنان را قادر می سازد آگاهی یابند که چقدر زمان لازم است تا یک سری عملیات به اجرا در آید . برای برخی مردم ( مثلاً برنامه نویسان) ، ثابت پنهان می تواند به معنای شکست یا موفقیت باشد.
تخمین میزان کارایی زمان اجرا بستگی به این دارد که ما هر مرحله را چگونه تعریف کنیم. برای اینکه این تجزیه و تحلیل معنی داشته باشد، باید تضمین کرد که زمان مورد نیاز برای اجرای یک مرحله توسط یک مقدار ثابت محدود شده است یعنی حد بالایی برای آن تعریف شده باشد. باید در اینجا دقت کرد؛ بعنوان مثال در برخی تجزیه و تحلیل ها ، جمع کردن دو عدد را یک مرحله به حساب می آورند. ممکن است در برخی شرایط این فرض مورد قبول نباشد. مثلاً ، اگر اعدادی که در یک محاسبه مورد استفاده قرار می گیرند، بدون ترتیب خاص و بطور اختیاری بزرگ باشند، دیگر نمی توان فرض کرد که عمل جمع به مدت زمانی ثابت احتیاج دارد (مقدار زمان مورد نیاز برای جمع دو عدد دو رقمی و دو عدد 1000 رقمی را به کمک کاغذ و قلم مقایسه نمایید)

1. - تعریف ساختارهای خطی (Linear Structure) و غیر خطی (Non - Linear Structure)
2. 2- رشته ها (String)، نحوه نمایش رشته ها

   1-2- عملیات روی رشته ها (تعیین رشته، مجاورسازی، جستجوی یک زیر رشته در داخل یک رشته دیگر، انتخاب زیر رشته ای از رشته دیگر، مقایسه رشته ها، حذف زیر رشته ای از داخل رشته، زیر رشته ای در داخل رشته دیگر، جایگزین کردن قسمتی از یک رشته با زیر رشته دیگر، تهیه کپی از روی یک رشته)
3. 3- رکوردها
   - نحوه توصیف رکوردها
   - انجام عملیات روی رکوردها
   Sort، Search، حذف و اضافه
4. 4- آرایه ها
   - نحوه نمایش آرایه های یک، دو ... n بعدی در حافظه کامپیوتر
   - نحوه محاسبه آدرس عنصری در آرایه های یک، دو ... n بعدی
   - انجام عملیات Search، Sort، حذف و درج در آرایه ها
   - محاسن، معایب و محدودیت های آرایه ها و کاربرد آنها
   - ماتریس
   - ماتریس خلوت، ماتریس پایین مثلثی، ماتریس بالا مثلثی و کار با آنها
5. 5- پشته یا Stack
   1-5- تعریف داده ها و حافظه هایی از نوع Stack
   2-5- نحوه شبیه سازی Stack با استفاده از آرایه ها
   3-5- انجام عملیات درج (Insert)، یا Push و حذف (Delete) یا Pop و نوشتن الگوریتم آنها
   4-5- Stack و بیان الگوریتم آنها، برنامه سازی الگوریتم های مزبور در یک زبان برنامه سازی
   5-5- کاربردها:
          1-5-5- در فراخوان توابع
          2-5-5- در توابع بازگشتی (مانند تابع فاکتوریل، تعریف و محاسبه چند جمله ایهای بصورت بازگشتی، معکوس کردن(Reverse) رشته ها، محاسبه بزرگترین مقسوم علیه دو عدد، تابع هانوی (Hano's Function))
   - کاربرد Stack و تبدیل عبارات Infix به Suffix، نمایش عبارات ریاضی به صورت های Prefix، Infix، Suffix، الگوریتم های این تبدیلات
6. 6- صف Queue
   - تعریف صف
   - شبیه سازی صف با استفاده از آرایه ها
   - الگوریتم های درج عنصری در صف و حذف عنصری از صف
   - کاربردهای صف
   - صف دایره ای (Circular Queue)
   - الگوریتم های درج و حذف در صف دایره ای
   - لیست پیوندی: امکان تعریف، نحوه نمایش، حذف و درج گره در ابتدا و انتها
   - لیست پیوندی دو طرفه: امکان تعریف، نحوه نمایش، حذف و درج گره
   - امکان تعریف لیست پیوندی حلقوی و نحوه درج حذف
   - ایجاد لیست پیوندی با سر لیست
7. 7- درخت
   1-7- تعریف درخت در حالت کلی، روشهای مختلف نمایش درخت در حافظه
   2-7- درخت دودویی
   3-7- ویژگیهای درخت دودویی و روشهای مختلف نمایش آن در حافظه
   4-7- پیمایش های مختلف درخت دودویی
   5-7- تعاریف درختهای MaxTree، MinTree، Max Heap، Min Heap، ...
8. 8- عملیات متداول درخت دودویی
   1-8- ایجاد درخت
   2-8- جستجوی نود (node) خاص
   3-8- حذف و درج درخت
   4-8- الگوریتم های مربوط و استفاده از Stack در اینگونه موارد
   5-8- تمرین برنامه سازی الگوریتم های بالا
9. 9- کاربرد درخت دودویی
   1-9- جستجوی درخت دودویی (Binary Tree Search)
   2-9- مرتب کردن به روش درخت دودویی (Binary Tree Sort)
   3-9- تبدیل عبارات Infix به Suffix به کمک درخت دودویی
   - گراف، نکات و برخی تعاریف

یکی از دروسی که در ترم ۳ کاردانی کامپیوتر ارایه می شود درس ساختمان داده ها می باشد این درس دارای مباحث شیرین و جالب است که  از این پس سعی می کنم در این قسمت راجع به این درس مطلب بنویسم تا دانشجویان خود را برای ترم بعد آماده نمایند .

جزوه ساختمان داده ها                                 دانلود

یک فیلم آموزشی ساختمان داده ها پسورد :arsanjan.blogfa.com              دانلود

جزوه ساختمان داده ها به زبان c                           دانلود