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

جلسه اول – فصل اول: مفاهیم و مقدمات

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

تعریف خصوصیات الگوریتم

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

تفاوت برنامه و الگوریتم: یک برنامه تمامی خصوصیات یک الگوریتم را به جز شرط پایان پذیر بودن  شامل می‌شود. به عنوان مثال سیستم عامل برنامه‌ای است که هیچ گاه پایان نمی‌پذیرد و همواره در حال اجراست تا برنامه بعدی وارد چرخه پردازش شود.

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

انواع ساختمان داده

1. ایستا
2. نیمه ایستا
3. پویا

ایستا

• اولیه: داده صحیح و داده اعشاری
• غیر اولیه: آرایه، رکورد، رشته، داده کاراکتری

نیمه ایستا

• پشته: پشته یا Stack به ساختمان داده‌ای گفته‌ می‌شود که مجموعه‌ای از المان‌ها را بر اساس اصل LIFO (اولویت خروج با عناصر تازه وارد) در خود نگه داری می‌کند و از دو عمل Push برای افزودن آیتم و Pop برای حذف آیتم پشتیبانی می‌کند.

پویا

• خطی: لیست پیوندی
• غیرخطی: درخت و گراف

داده های ایستا: ساختارهایی هستند که  از فضای محدود و از پیش تعریف شده استفاده می‌کنند و چنین فضایی در طول اجرای  یک برنامه ثابت است.

داده های پویا: ساختارهایی هستند که امکان تغییرات نامحدود و متناسب با داده‌ها رو فراهم می‌کنند و این کار معمولا توسط اشاره گرها صورت می‌گیرد.

اشاره‌گرها و آرایه‌ها از جمله مهم‌ترین ساختارهای داده‌ای ایستا هستند. پشته و صف هم جزء ساختمان‌های داده‌ای نیمه ایستا هستند.

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

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

جلسه دوم – فصل اول: پیچیدگی زمانی الگوریتم‌ها

مقدمه‌ای بر تحلیل پیچیدگی زمانی و مرتبه اجرایی الگوریتم‌ها: در ارزیابی یک برنامه یا الگوریتم دو عامل اصلی وجود دارد که باید مورد توجه قرار گیرد یکی حافظه و دیگری زمان الگوریتم است یعنی الگوریتم بهتر است که فضای مصرفی و زمان کم‌تری را درخواست کند.

در تحلیل زمان اجرای یک الگوریتم تمام دستورات را شمارش نمی‌کنیم زیرا تعداد دستورات به نوع زبان برنامه نویسی بستگی دارد. برای محاسبه زمان اجرای یک الگوریتم فقط به عملیات اصلی نیاز داریم که مستقل از کامپیوتر و زبان برنامه نویسی هستند در عین حال هیچ قاعده مشخصی برای انتخاب عملیات اصلی وجود ندارد و انتخاب عمل اصلی به صورت تجربی انجام می‌شود. برای بررسی زمان اجرای یک الگوریتم به تابعی به نام (t(n که تابع زمان الگوریتم می‌شود در نظر می‌گیریم که در آن n اندازه ورودی مسئله است که ممکن است شامل چندین داده ورودی باشد.

مثال: اگر ورودی یک گراف باشد علاوه بر تعداد راس‌ها (n) یال‌ها نیز (m) یکی از مشخصه‌های ورودی است بنابراین زمان اجرای الگوریتم با (T(n,m  شمارش می‌شود. در محاسبه زمان (T(n یک الگوریتم محاسبه تعداد تکرارعملیات و توابع بازگشتی اهمیت بیشتری دارد.

شمارش گام‌ها یا مراحل یک برنامه

گام‌های یک برنامه با استفاده از مراحل کلی و قواعد کلی زیر قابل محاسبه خواهد بود.

• تعاریف زیر برنامه‌ها و توابع دارای گام صفر هستند.
• هر بلاک شامل باز و بسته کردن { } دارای صفر گام است.
• تعاریف متغیر در صورتی که مقدار اولیه برای آن‌ها درنظر گرفته نشود ۰ و اگر گرفته در نظر گرفته شود ۱ خواهد بود.
• درهر دستور اجرایی به ازای هربار اجرا دارای یک گام است.

عبارت شرطی if: عبارت شرطی یک گام دارد اما با توجه به درست و غلط بودن شرط چون جملات مختلفی ممکن است اجرا شود کل دستور شرطی و به درست و غلط بودن شرط بستگی خواهد داشت

دستور حلقه for: مهم‌ترین قسمت در شمارش گام‌های یک برنامه حلقه for است که ترتریب  زیر گام آن را محاسبه می‌کنیم.

• ابتدا تعداد تکرار حلقه را محاسبه می‌کنیم.
• حلقه for به تعداد تکرار + یک گام اختیار می‌کند.
• جملات تکرار شونده داخل حلقه for به تعداد تکرار گام اختیار می‌کند.

حلقه تودرتو: برای محاسبه گام حلقه‌های تودرتو به صورت زیر عمل می‌کنیم.

• از بیرون‌ترین حلقه شروع می‌کنیم.
• تعداد تکرار هر حلقه را برای تمام حلقه‌ها و دستورات تکرار شونده پایین در نظر گرفته و تعداد تکرار +۱ را برای خود حلقه در نظر می‌گیریم.
• قسمت ۲ را برای تمامی حلقه‌ها انجام می‌دهیم.

ﺗﻌداد ﮔﺎم ﺣﻟﻗﻪ‌ﻫﺎی while مانند ﻣﺣﺎﺳﺑﻪ می‌ﺷود ﻳﻌنی ﮔﺎم حلقه ﻳک واﺣد از ﺗﻌداد ﺗﻜرار حلقه بیشتر است.

بررسی کارایی اﻟﮕورﻳﺗم:

• bigO
• bigƟ
•  Ω

نقاط رشد تابع

1. لگاریتم N با هر پایه‌ای رشدشان باهم برابر است به شرطی که پایه پایشان ثابت باشد.

Loga n = Loga na,b>1

2. n به توان هر عدد ثابت رشدش از log n به هر توان ثابتی بیشتر است.
3. log n با هر توانی از log logn با هر توانی بیش تر است به شرطی که توانش ثابت باشد.

توابع نمایی رشدشان از توابع چند جمله‌ای بیشتر است

توابع و زیر برنامه‌های بازگشتی: به هر تابع یا برنامه‌ای که بتواند داخل بدنه‌اش خودش را دوباره فرا خوانی کند یا صدا بزند تابع یا زیر برنامه بازگشتی می‌گویند.

1. بدون بازگشتی(عادی)
2. بازگشتی

توابع بازگشتی دو ویژگی دارند:

1. تابع خودش خودش را صدا می زند البته اغلب با آرگومان‌های کوپکتر.
2. یک شرط جهت اتمام فراخوانی‌ها وجود دارد.

نکته:

مراحل بازگشت در استک یا پشته نگه داری می‌شود با پرشدن استک هنگام خطای stack over flow نشان داده می‌شود (پشته همیشه از بالا به پایین پر می‌شود)

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

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

جلسه سوم – فصل دوم: آرایه ها

تعریف آرایه: مجموعه‌ای از داده‌های پشت سر هم که همگی از یک نوع بوده و از آدرس مشخص شروع می‌شوند.

عناصر یک آرایه با اندیس شان قابل دستیابی هستند آرایه می‌تواند یک بعدی دو بعدی یا چند بعدی باشد.

آرایه یک بعدی:  آرایه یک بعدی برای دخیره سازی مجموعه‌ای از عناصر هم نوع به کار می‌رود.

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

آرایه  ۱بعدی:                     int A[10]                                        A[L1…..u1]

آرایه ۲ بعدی:                     int A[10][20]                                 A[L1…..u1 , L2…..u2]

آرایه n بعدی:                                                                        A[L1..u1] , [L2..u2 , Ln…un]

نکته: کوچکترین اندیس آرایه حد پایین آرایه یا Lower یا (L) بزرگترین مقدار  اندیس آرایه را کران بالای آرایه می‌گویند و با Upper یا  (U) نشان می‌دهند.

تعداد عناصر یک آرایه: تعداد عناصر یک آرایه برابر است (u-L) می‌باشد.

A=[L1……u1]            تعداد خانه             u1-L1+1

A=[L1……u1 , L2……u2]             تعداد خانه     (u1-L1+1)*(u2-L2+1)

محاسبه فضای آرایه: برای محاسبه فضای آرایه کافی است تعداد عناصر آرایه را در فضای نوع عناصر آن ضرب کنیم.

عناصر نوع آرایه * تعداد عناصر آرایه=فضای آرایه

مثال؟

int A[10];          ۱۰*۴=۴۰ byte

int A[-1…۳ , ۲…۵]        حافظه =۲۰*۴=۸۰ byte

محاسبه آدرس خانه(i) : اگر هر عنصر از آرایه با نام A به اندازه سایز N بایت فضا اشغال کند محل عنصر (i) به صورت زیر محاسبه می‌شود.

آدرس اولین محل

Loc(i)=base(a)+i*size

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

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

جلسه چهارم – ماتریس ها و پشته

ماتریس: به هر آرایه دو بعدی m*n یک ماتریس یا جدول با m سطر و n ستون گفته می‌شود که تعداد m*n خانه در آن وجود دارد.

تعریف ماتریس پایین مثلثی و بالا مثلثی: اگر عناصر زیر قطر اصلی ۰ باشند ماتریس بالا مثلثی است و اگر عناصر بالای قطر اصلی ۰ باشند ماتریس پایین مثلثی است.

شرایط ضرب دو ماتریس: برای اینکه ضرب دو ماتریس A,B امکان پذیر باشد باید ستون ماتریس A با سطر ماتریس B یکسان باشد.

خواص ضرب ماتریس‌ها:

1. ضرب ماتریس خاصیت جابه جایی ندارد.
2. ضرب ماتریس ها خاصیت شرکت پذیری دارند.

ترا نهاده یک ماتریس: اگر جای سطر و ستون یک ماتریس را عوض کنیم ماتریس ترانهاده می‌شود.

ماتریس اسپارس(ماتریس خلوت): به هر ماتریس m*n که تعداد خانه‌های ۰ یا بدون ارزش آن بیشتر از تعداد خانه‌های مخالف ۰  باشد ماتریس اسپارس می‌گویند.

رشته‌ها

رشته‌ها در واقع آرایه‌ای از کاراکترها می باشند. در زبان پاسکال طول رشته در خانه ۰ ذخیره می‌شود و در زبان C در انتهای رشته کاراکتر (\۰) ذخیره می‌گردد.

پشته: پشته لیست مرتبی است که عملیات اضافه و حذف کردن  از یک طرف آن انجام می‌شود. پشته به صورت (Lifo) عمل می‌کند یعنی آخرین عنصر وارد شده  اولین عنصری است که خارج می‌شود. به پشته (Lifo) نیز گفته می‌شود.

یکی از کاربردهای پشته ذخیره آدرس بازگشت و ساخت متغیرهای محلی در صدا زدن توابع است. به عمل ریختن اطلاعات در داخل پشته (push) و به برداشتن اطلاعات (Pop) گفته می‌شود. ساده‌ترین راه نمایش پشته استفاده از آرایه ۱ بعدی به طول n می‌باشد. خانه‌های آرایه stack از عدد یک تا n شماره گذاری شده و در کنار آرایه متغیری به نام Top وجود دارد که عنصر بالایی به آن اشاره می‌کند.

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

جلسه پنجم- کاربرد پشته و عبارت های محاسباتی

کاربرد پشته:

1. استفاده از توابع بازگشتی
2. ارزیابی عبارت های محاسباتی یعنی(prefix , postfix , infix)
3. الگوریتم مسیر حرکت maze
4. پیمایش عمیقی گراف ها و درخت ها
5. استفاده در روش های مرتب سازی (Quick sort , marge sort)

ارزشیابی عبارت های محاسباتی:

هر عبارت محاسباتی با توجه به اولویت عملگرهایش قابل ارزیابی و محاسبه است.

1. () پارانتز
2. – منفی یا + مثبت                 اولویت از چپ به راست
3. توان اولویت از چپ به راست
4. * ضرب / تقسیم اولویت از چپ به راست
5. + جمع – منها اولویت از چپ به راست

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

1. ابتدا اولویت‌های هر عبارت محاسباتی را بر حسب اولویت‌های عملگرهایش محاسبه می‌کنیم.
2. ریشه درخت کم اولویت ترین از نظر اولویت است.
3. ریشه زیر درختان چپ و راست به ترتیب کم اولویت ترین عملگر از نظر اولویت در چپ و راست ریشه است.
4. برگ‌های درخت عملوندها هستند

عبارت های محاسباتی

1. prefix عبارت پیشوندی روش لهستانی -+abc , +ab
2. infix عبارت میانوندی a+b             (a+b)-c
3. postfix عبارت پسوندی ab+ ab+c-

عبارت infix :

در این روش عملگر وسط قرار گرفته و عملوندها چپ و راست قرار می‌گیرند. اولویت عملگرها مطرح می‌باشد و با توجه به جدول اولویت عملگرها مشخص می‌گردد.

عبارت prefix :

در این روش هر عملگر قبل از عملوندهایش قرار می‌گیرد اولویت عملگرها مطرح نیست و از پارانتز استفاده نمی‌شود.

عبارت postfix :

در این روش هر عملگر بعد از عملوندهایش قرار می‌گیرد. اولویت مطرح نیست و از پارانتز هم استفاده نمی‌شود.

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

جلسه ششم – صف و انواع آن

صف لیست خطی مرتبی از عناصر است که در آن عمل درج از یک طرف و عمل حذف از طرف دیگر انجام می‌شود.به ساختار صف fifo نیز گفته می‌شود. در صف از دو متغیر اشاره گر به نام front که به عنصر قبل از عنصر ابتدایی اشاره می‌کند و دیگری به نام rear که همیشه به اخرین عنصر اشاره می‌کند. کاربرد مهم صف در زمان بندی  برنامه‌ها در سیستم عامل است.نمایش  صف با دو ساختار لیست پیوندی و آرایه‌ای می‌باشد. ساده‌ترین راه نمایش صف استفاده از آرایه‌ی یک بعدی به طول n  است.

نکته:مشکل اصلی صف معمولی آن است که یک بار قابل استفاده است و هنگامی که rear به انتها می‌رسد نمی‌توان در صف چیزی را ذخیره کرد برای حل این مشکل از صف حلقوی استفاده می‌کنیم.

صف حلقوی:

آرایه انتخابی ۰ تا۱ Q[0 , …. , n-1] را می‌توان به صورت صف حلقوی در نظر گرفت به طوری که در این صف زمانی که rear برابر n-1 می‌شود عنصر بعدی در خانه شماره ۰ قرار می‌گیرد.

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

جلسه هفتم- لیست پیوندی

 ﻏﺎﻟﺑﺎً ﺑرای ذﺧﻳره داده‌ﻫﺎ ﻫم ﻣﻲ‌ﺗوان از آراﻳﻪ اﺳﺗﻓﺎده ﻛرد و ﻫم از ﻟﻳﺳت ﭘﻳوﻧدی ﻋﻧﺎﺻر آراﻳﻪ اﻟزاﻣﺎً در ﺣﺎﻓظﻪ ﭘﺷت ﺳر ﻫم ﻗرار ﮔرﻓﺗﻧد وﻟﻲ ﻋﻧﺎﺻر ﻟﻳﺳت ﭘﻳوﻧدی از ﻧوع ﭘوﻳﺎ ﺑوده و ﻋﻧﺎﺻر آن اﻟزاﻣﺎ در ﻛﻧﺎر ﻳﻚ دﻳﮕر ﻧﻣﻲ‌ﺑﺎﺷﻧد ﺑﻪ ﻫﻣﻳن دﻟﻳل اﻋﻣﺎل درج و ﺣذف در ﻟﻳﺳت ﭘﻳوﻧدی ﺳﺎده‌ﺗر و ﺧﻳﻟﻲ ﺳرﻳﻊ‌ﺗر از آراﻳﻪ اﻧﺟﺎم ﻣﻲ‌ﮔﻳرد. ﻟﻳﺳت ﭘﻳوﻧدی از ﻣﺟﻣوﻋﻪ‌ای از ﻋﻧﺎﺻر ﺗﺷﻜﻳل ﺷده اﺳت ﻫر ﻋﻧﺻر ﻳﺎ ﮔره ﻳﺎ ﻧود در ﻟﻳﺳت ﭘﻳوﻧدی ﺣداﻗل از دو ﻓﻳﻟد داده (data) و اﺷﺎره‌ﮔری ﺑﻪ ﮔره ﺑﻌدی (link) ﺗﺷﻜﻳل ﻳﺎﻓﺗﻪ است.

لیست‌های پیوندی را به ۳ دسته تقسیم می‌کنند.

1. لیست‌ها یک طرفه هستند یا دو طرفه.
2. لیست‌ها یا خطی هستند یا حلقوی.
3. لیست‌ها یا بدون گره سر هستند یا گره سر دارند.

ﻟﻳﺳت ﭘﻳوﻧدی ﻳﻚ ﻃرﻓﻪ ﺧﻃﻲ:

در ﻟﻳﺳت ﭘﻳوﻧدی ﻳﻚ طرﻓﻪ ﺧطﻲ در ﻫر ﮔره ﻓﻗط آدرس ﮔره ﺑﻌدی ذﺧﻳره ﻣﻲ‌ﺷود و اﺷﺎره ﮔره آﺧرﻳن ﮔره ﻧﻳز ﺑراﺑر ۰\ هست.

ﻟﻳﺳت ﺣﻟﻗوی ﻳﻚ ﻃرفه:

ﻟﻳﺳت ﺣﻟﻗوی ﻣﺷﺎﺑﻪ ﻟﻳﺳت ﻳﻚ طرﻓﻪ اﺳت ﺑﺎ اﻳن ﺗﻓﺎوت ﻛﻪ اﺷﺎره ﮔر آﺧرﻳن ﮔره ﺑﻪ ﺟﺎی اﻳﻧﻜﻪ null ﺑﺎﺷد ﺑﻪ ﺳر ﻟﻳﺳت اﺷﺎره ﻣﻲ‌ﻛﻧد (head) در ﻟﻳﺳت ﺧطﻲ ﻫﻣواره ﺑﺎﻳد آدرس ﺳر ﻟﻳﺳت را داﺷﺗﻪ ﺑﺎﺷﻳم وﻟﻲ در ﻟﻳﺳت ﺣﻟﻗوی ﺑﺎ داﺷﺗن ﻫر ﮔوﻧﻪ دﻟﺧواه ﻣﻲ‌ﺗوان ﺑﻪ ﺗﻣﺎﻣﻲ ﮔره‌ﻫﺎ دﺳﺗرﺳﻲ داﺷت.

لیست پیوندی دو  طرفه (TWL  (Two Way List:

در لیست دو طرفه یا(TWL)  در هر گونه دو اشاره گر وجود دارد که یکی به گره بعدی و دیگری به گره قبلی در لیست اشاره می‌کند. به کمک اشاره گرهای سمت راست (R.link) و سمت چپ (L.link)  می‌توان در هر دو طرف لیست حرکت کرد بنابراین با داشتن یک گره کلیه گره‌ها قابل دسترسی‌اند.

لیست عمومی

لیستی که هر گونه آن بتواند خود یک زیر لیست باشد لیست عمومی نامیده می‌شود.به عبارتی دیگر لیست عمومی (L) از تعداد محدودی عنصر A1,A2,…An  تشکیل شده به گونه‌ای که هر (AI)یک عضو ساده و یا یک لیست می‌باشد.

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

جلسه هشتم- درخت یا tree

 درﺧت ﻳﺎ ﺳﺎﺧﺗﻣﺎن داده ﻏﻳر ﺣﻗﻳﻗﻲ اﺳت و ﻣﺟﻣوﻋﻪ‌ای ﻣﺣدودی از ﻳﻚ ﻳﺎ ﭼﻧد ﮔره ﺑﻪ ﺻورت زﻳر اﺳت.

1. دارای ﮔره ﺧواﺻﻲ ﺑﻪ ﻧﺎم رﻳﺷﻪ اﺳت.
2. بقیه ﮔره‌ﻫﺎ ﺑﻪ n>=0 ﻣﺟﻣوﻋﻪ ﻣﺟزا ﻳﻌﻧﻲ t1….,tn ﺗﻗﺳﻳم ﺷده اﺳت ﻛﻪ ﻫر ﻛدام از اﻳن ﻣﺟﻣوﻋﻪ‌ﻫﺎ ﺧود ﻳﻚ درﺧت ﻫﺳﺗﻧد وt1….,tn ﻧﻳز زﻳر درﺧﺗﺎن رﻳﺷﻪ ﻧﺎﻣﻳده ﻣﻲ‌ﺷوﻧد.

ﻧﻜﺗﻪ: در درﺧت ﺣﻟﻗﻪ وﺟود ﻧدارد.

ﺗﻌﺎرﻳف

درﺟﻪ ﻳﻚ ﮔره: ﺗﻌداد زﻳر درﺧت‌ﻫﺎی ﻳﻚ ﮔره درﺟﻪ آن ﻧﺎم دارد.

ﺑرگ: ﮔره ﻫﺎﻳﻲ ﻛﻪ درﺟﻪ ۰ دارﻧد ﺑرگ ﻳﺎ ﮔره‌ﻫﺎﻳﻲ ﭘﺎﻳﺎﻧﻲ ﻧﺎﻣﻳده ﻣﻲ‌ﺷود.

درﺟﻪ ﻳﻚ درﺧت: ﺣداﻛﺛر درﺟﻪ ﮔره‌ﻫﺎی آن درﺧت ﻣﻲ‌ﺑﺎﺷد.

ﮔره ﻫﺎی ﻫم ذات: ﻓرزﻧدان ﻳﻚ ﮔره ﻫم ذات ﻧﺎﻣﻳده ﻣﻲ‌ﺷود.

ﺳﻃﺢ ﻳﻚ ﮔره: رﻳﺷﻪ در ﺳطﺢ ۱ ﻗرار دارد و ﺳﺎﻳز ﮔره‌ﻫﺎ ﺑر اﺳﺎس ﺗﻌداد ﻣﻜﺎﻧﻲ ﻛﻪ از رﻳﺷﻪ ﻓﺎﺻﻟﻪ دارﻧد ﺷﻣﺎره ﺳطﺢ ﻧﺎﻣﻳده ﻣﻲ‌ﺷود. ﮔره‌ﻫﺎﻳﻲ ﺑﺎ ﻓﺎﺻﻟﻪ n ﻣﻜﺎن از رﻳﺷﻪ در ﺳطﺢ 1n+ ﻗرار دارﻧد. اﮔر ﮔره‌ای در ﺳطﺢ k ﺑﺎﺷد ﻓرزﻧدان آن در ﺳطﺢ 1k+ ﻗرار دارﻧد.

ارتفاع یا عمق یک درخت: ﺑﻪ بیش ترین ﺳطﺢ ﮔره‌ﻫﺎی آن درﺧت ﮔﻓﺗﻪ ﻣﻲ‌ﺷود.

تعریف یال و مسیر: هر خط یا اتصال  از یک گره به گره دیگر یا هر انشعاب از گره به گره دیگر را یال می‌گوییم و دنباله‌ای از یال‌های متوالی یک مسیر نامیده می‌شود.

شاخه: مسیری که به یک برگ ختم می‌شود یک شاخه نام دارد.

درخت مرتب: درختی است که ترتیب زیر درخت‌ها در آن مهم باشد.

درخت مشابه: درخت‌های t1,t2 مشابه هستند اگر دارای ساختمان داده یکسان باشند یا به بیان دیگر شکل مساوی داشته باشند. درخت‌ها را کپی می‌گویند اگر مشابه بوده و محتوای گره‌های متناضر آن نیز یکی باشد.

درخت k تایی: درختی که فرزندان هر گره در آن حداکثر k باشد.

درخت متوازن: درختی است که اختلاف سطح گره‌های آن حداکثر یک باشد و اگر اختلاف سطح برگ ها ۰ باشد آنگاه درخت کاملا متوازن است.

نمایش درخت: برای نمایش درخت می توان از فرم پرانتزی استفاده کرد.در این فرم ابتدا اطلاعات ریشه و سپس داخل پرانتز ها اطلاعات فرزندان آن گره به ترتیب از چپ به راست نوشته می‌شود.

A(B(E(K),F),C(G(L,M)H,T),D(J))

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

درخت دودویی

یک درخت دودویی یک ساختمان داده درخت است که در آن هر گره حداکثر دو گره فرزند دارد که فرزندان راست و چپ نامیده می شوند.در درخت دودویی،درجه هر گره حداکثر می تواند دو باشد. درخت های دودویی برای پیاده سازی درخت جست و جوی دودویی و انبوه دودویی و برای جست و جوی کارآمد و مرتب سازی استفاده می‌شود.درخت دودویی یک حالت خاص از یک درخت Kتایی است که در آن K برابر ۲ است.در درخت دودویی ترتیب زیر درخت ها مهم است

انواع درخت دودویی

درخت پر: درختی است که به جز گره‌های سطح آخر دقیقا دو فرزند داشته باشد.

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

درخت مورب: در درخت مورب چپ هر گره فرزند چپ والد خود می‌باشد و در درخت مورب راست هر گره فرزند راست  والد خود می‌باشد.

نمایش درخت دودویی

س از ﺷﻣﺎره ﮔذاری ﮔره ﻫﺎی درﺧت دودوﻳﻲ ﻣﻲ ﺗوان درﺧت را در آراﻳﻪ ذخیره ﻛرد ﺑﻪ طوری ﻛﻪ محتوای ﻫر ﮔره در ﺧﺎﻧﻪ ای از آراﻳﻪ ﺑﺎ ﻫﻣﺎن ﺷﻣﺎره ذﺧﻳره ﺷود.

اﺳﺗﻓﺎده از ﻓرم آراﻳﻪ ﺑرای درختان ﻛﺎﻣل ﻣﻧﺎﺳب اﺳت ﭼون ﻫﻳﭻ ﺧﺎﻧﻪ ای از حافظه ﻫدر ﻧﻣﻲ رود وﻟﻲ ﺑرای درﺧت ﻫﺎی ﻣورب ﻛﺎﻣﻼ ﻧﺎﻣﻧﺎﺳب اﺳت ﭼون ﻓﺿﺎی زﻳﺎدی ﺑﻪ ﻫدر ﻣﻲ رود اﻳراد ﻧﻣﺎﻳش درﺧت ﺑﺎ آراﻳﻪ اﻳن اﺳت ﻛﻪ ﺣذف ﻳﺎ درج ﮔره ﻫﺎ و ﻣﺳﺗﻟزم ﺟﺎﺑﻪ ﺟﺎﻳﻲ ﮔره ﻫﺎﺳت ﻛﻪ ﺧود ﺑﺎﻋث ﺷﻣﺎره ﺳطر ﮔره ﻫﺎ ﻣﻲ ﺷود و ﻣﺷﻜل ﻓوق ﺑﺎ اﺳﺗﻓﺎده از ﻧﻣﺎﻳش ﭘﻳوﻧدی ﻗﺎﺑل ﺣل اﺳت.

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

جلسه نهم –  پیمایش درخت دودویی

 در پیمایش درخت می خواهیم هر گره درخت فقط یک بار ویزیت شود به هنگام پیمایش یک درخت با هر گره و زیر درختانش به طرز مشابهی رفتار کنیم. اگر L به ترتیب حرکت به چپ،V ملاقات کردن یک گره و R حرکت کردن به راست باشد. آنگاه ۶ ترکیب به دست خواهد آمد که سه ترکیب آن برای مهم است.

• LVR یا پیمایش میانوندی inorder
• VLR یا پیمایش پیشوندی preorder
• LRV یا پیمایش پسوندی postorder

ترسیم درخت به کمک پیمایش آن ها

• اگر پیمایش های میانوندی و پسوندی درخت دودویی را داشته باشیم می توانیم آن درخت را به صورت یکتا رسم کنیم.
• اگر پیمایش های میانوندی و پیشوندی درخت دودویی را داشته باشیم می توانیم آن درخت را به صورت یکتا رسم کنیم.
• اگر پیمایش های پیشوندی یا پسوندی یک درخت دودویی را داشته باشیم ممکن است نتوانیم آن درخت را به صورت یکتا رسم کنیم.

پیمایش ترتیبی سطحی

پیمایش های inorder , preorder , postorder در واقع پیمایش های عمقی هستند که برای آنها از پشته استفاده می‌شود.درپیمایش سطحی از یک صف استفاده می‌شود و در این روش ابتدا ریشه سپس فرزند چپ ریشه و به دنبال آن فرزند راست  ریشه بازیابی می گردد.این شیوه  با بازیابی از گره‌های منتها علیه سمت چپ به راست هر صف جدید تکرار می‌شود.

درخت عمومی (Genral tree)

درخت عمومی یا درخت کلی یک درخت Kتایی است که در آن فقط یک گره به نام ریشه با درجه ورودی ۰ وجود دارد و سایر گروه ها دارای یک مکان ورودی هستند از این به بعد فرض می کنیم یک درخت عمومی مرتب است یعنی بچه های هر گره یک ترتیب مشخص دارند هر چند که با این خاصیت همواره برای تعریف درخت عمومی کافی نیست.

معمولا به دلیل اتلاف زیادی فضای حافطه بهتر است درخت های عمومی را با استفاده از الگوریتم به یک درخت دودویی تبدیل کرد.

تبدیل درخت عمومی به یک درخت دودیی

• در هر سطح گره‌های کنار هم که فرزند یک پدر هستند را به یک دیگر وصل می‌کنیم.
• ارتباط کلیه گره ها به جز اتصال سمت چپ ترین فرزند را قطع می‌کنیم.
• گره‌های متصل به هم در هر سطح افقی را ۴۵ درجه در جهت حرکت عقربه‌های ساعت می‌چرخانیم.

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

جلسه دهم- درختان ویژه

در این فصل برخی از درختان از جمله درخت AVL , BCD , Heap , Huffman , انتخابی و درخت تقسیم  را مورد بررسی قرار خواهیم داد.یکی دیگر از درخت‌های پر استفاده B tree در مباحث مربوط به فایل‌ها به کار برده می‌شود.

تعریف max tree : درختی است که مقدار هر کلید گره آن بزرگنر یا مساوی کلیدهای فرزندهایش باشد.

تعریف min tree : درختی است که مقدار هر کلید گره آن کوچکتر یا مساوی کلیدهای فرزندهایش باشد.

تعریف max heap : درخت کامل دودویی است که max tree  نیز باشد.

تعریف min heap : درخت کامل دودیی است که min tree  نیز باشد.

توجه کنید که کامل بود شرط لازم برای heap بودن درخت است ریشه درخت min heap حاوی کوچک ترین کلید و درخت و ریشه درخت max heap حاوی بزرگترین کلید درخت است.

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

جست و جوی عنصر در BST :

برای پیدا کردن گرهی با یک کلید خاص مانند  x در درخت ابتدا باید از ریشه درخت شروع کنیم اگر ریشه تهی باشد،درخت فاقد هر عنصری بوده و جست و جو ناموفق خواهد بود.در غیر این صورت x را با مقدار گره ریشه مقایسه می کنیم اگر برابر بودند جست و جو موفق است و گره ریشه همان گره مورد نظر است در غیر این صورت دو حالت پیش خواهد آمد:

•  x از گره ریشه کوچکتر است در این حالت هیچ عنصری در زیر درخت سمت راست وجود ندارد که مقدار کلید آن برابر با x باشد بنابراین جست و جو باید در زیر درخت سمت چپ ادامه یابد
• x بزرگتر از ریشه است در این حالت هیچ عنصری در زیر درخت  سمت چپ وجود ندارد که مقدار کلید آن برابر با x  باشد بنابراین جست و جو باید در زیر درخت سمت راست ادامه یابد.
• سپس بسته به حالت یک و دو  زیر درخت سمت چپ یا زیر درخت سمت راست را به روش بازگشتی و با استفاده از الگوریتم بالا جست و جو می کنیم.عمل جست و جو در درخت جست و جوی دودویی  از مرتبه O(h) است که در آن  h ارتفاع درخت است چرا که حداکثر باید به میزان عمق درخت به طرف پایین حرکت کنیم.

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

جلسه یازدهم- ادامه درختان ویژه

 درخت با ارتفاع متوازن

درختی که در آن اختلاف در زیر درخت چپ و راست هر گره حداکثر یک باشد درخت با ارتفاع متوازن نامیده می‌شود.

درخت AVL 

یک نوع درخت جستجوی دودویی خود متوازن‌کننده‌است هر درخت AVL یک درخت BST بوده که ارتفاع متوازن دارد  و اولین ساختار داده‌ای از این نوع می‌باشد که اختراع شد. در یک درخت ای‌وی‌ال اختلاف ارتفاع دو زیر شاخه هر گره حداکثر برابر یک است؛ بنابراین به این درخت، درخت با ارتفاع متوازن نیز گفته می‌شود.

درخت تصمیم گیری:

۳ عدد k1 , k2 , k3   را در نظر بگیرید.منظور از درخت تصمیم تمام حالاتی است که این ۳ عدد می توانند نسبت به هم دیگر داشته باشند.

برسی سه عدد نسبت به هم دیگر ۳! نسبت به  ۶! دارد

که برابر حالت های توقف می‌باشد به طور کلی بررسی n عضو دارای n! حالت است که یکی از این حالات همان حالت مرتب شده عناصر ارتفاع درخت تصمیم برای حالت مرتب عناصر O log n  بودن که این بهترین حالت نیز می‌باشد.

درخت دودویی گسترش یافته توی مسیر(Extended Binary Tree)

درخت دودویی گسترش یافته یک درخت دودیی است که در آن هر گره ۰ یا ۲ بچه دارد.گره‌هایی که ۰ بچه دارند گره‌های خارجی و گره‌هایی که ۲ بچه دارند گره‌های داخلی نامیده می شوند.

الگوریتم هافمن:

فرض کنید یک لیست با n وزن داده شده است در میان تمام EBTهای دارای این گره  خارجی و n وزن داده شده تعیین کنید یک درخت با حداقل طول مسیر وزن در اینجت مهم است.در الگوریتم هافمن برای ایجاد درخت  با حداقل طول مسیر وزن در مرحله دو درختی را  که ریشه minimum دارند را انتخاب می کنیم  و وزن آنها را باهم جمع می کنیم و وزن کمتر گره ها در سمت چپ قرار می گیرند بدین ترتیب هم از لحاظ حافظه و زمان جست و جو بهینه سازی و کاهش در اشغال فضا خواهیم داشت.

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

جلسه دوازدهم- گراف

هر گراف (g) شامل دو مجموعه V , E است. V مجموعه ای محدود از رئوس و E مجموعه ای محدود از لبه هاست. (E(g و (V(g مجموعه رئوس و لبه های گراف را نشان می دهد هر گراف به صورت G(V,E) نمایش داده می‌شود.در گراف دو وضعیت وجود دارد، وضعیت جهت دار و غیر جهت دار که در وضعیت غیر جهت دار رئوس زوج مرتب نیستند بنابراین زوج های (v1 , v0) , (v0,v1) یکسانند اما در گراف جهت دار این دو زوج دو لبه متفاوت را نمایش می دهد.گراف حداقل یک راس دارد و نم یتواند کاملا تهی باشد.

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

گراف چندگانه: گرافی را که دارای لبه های چندگانه هست را گراف چندگانه می گویند.

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

گراف ساده: گرافی است که فاقد خود حلقه و لبه های چندگانه است.

گراف کامل: گرافی که دارای حداکثر لبه باشد یعنی بین هر گره زوج،لبه ی مستقیمی وجود داشته باشد.

درخت پوشا یا (Spanning Tree):

درختی که تعدادی از لبه ها یا همان)یال ها( که تمام حروف(G)را در بر دارد که درخت پوشا نامیده می‌شود.

درخت پوشا Minimum

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

• فقط از لبه های داخل گراف استفاده کنیم
• باید دقیقا از n-1 از لبه استفاده کنیم
• نباید از لبه هایی که ایجاد حلقه می کنند استفاده کنیم.

الگوریتم راشال کروسکال

در این روش درخت پوشا با کمترین هزینه (+) لبه به لبه ساخته می‌شود لبه‌های مورد استفاده در (+) به ترتیب سعودی وزن‌ها می‌باشد.یک لبه در (+) اگر با لبه های قبل که در (+) بودند تشکیل حلقه ندهد.

الگوریتم پریم (prim)

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

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

جلسه سیزدهم – مرتب سازی

•  الگوریتم‌های متعددی برای مرتب سازی n عنصر وجود دارد که برخی از آن‌ها عبارتند از:
• مرتب سازی انتخابی (selection sort)
• مرتب سازی حبابی (bubble sort)
• مرتب سازی درجی (insertion sort)
• مرتب سازی جا به جایی (exchange sort)
• مرتب سازی سریع (quick sort)
• مرتب سازی هرمی (heap sort)
• مرتب سازی ادغامی یا ترکیبی (merge sort)
• مرتب سازی درختی (tree sort)
• مرتب سازی مبنا (radius sort)
• مرتب سازی پوسته (shell sort)

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