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

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

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

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

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

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

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

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

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

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

ایستا

اولیه: داده صحیح و داده اعشاری

غیر اولیه: آرایه-رکورد-رشته-داده کاراکتری.

نیمه ایستا

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

پویا

خطی: لیست پیوندی

غیرخطی: درخت و گراف

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ﺗﻌداد ﮔﺎم ﺣﻟﻗﻪ ﻫﺎي 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 نشان داده می شود (پشته همیشه از بالا به پایین پر می شود)

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

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

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

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

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

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

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

آرایه 2 بعدی:                     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];          10*4=40 byte

int A[-1…3 , 2…5]        حافظه =20*4=80 byte

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

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

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

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

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

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

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

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

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

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

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

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

رشته ها

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

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

یکی از کاربرد های پشته ذخیره آدرس بازگشت و ساخت متغیر های محلی در صدا زدن توابع است. به عمل ریختن اطلاعات در داخل پشته (push) و به برداشتن اطلاعات (Pop) گفته می شود. ساده ترین راه نمایش پشته استفاده از آرایه 1 بعدی به طول 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 به انتها می رسد نمی توان در صف چیزی را ذخیره کرد برای حل این مشکل از صف حلقوی استفاده می کنیم.

صف حلقوی:

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

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

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

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

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

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

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

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

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

ﻟﻳﺳت ﺣﻟﻗوي ﻣﺷﺎﺑﻪ ﻟﻳﺳت ﻳﻚ طرﻓﻪ اﺳت ﺑﺎ اﻳن ﺗﻓﺎوت ﻛﻪ اﺷﺎره ﮔر آﺧرﻳن ﮔره ﺑﻪ ﺟﺎي اﻳﻧﻜﻪ 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 ﻧﻳز زﻳر درﺧﺗﺎن رﻳﺷﻪ ﻧﺎﻣﻳده ﻣﻲ ﺷوﻧد.

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

ﺗﻌﺎرﻳف

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

درخت دودویی

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

در این فصل برخی از درختان از جمله درخت 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 بوده که ارتفاع متوازن دارد  و اولین ساختار داده‌ای از این نوع می‌باشد که اختراع شد. در یک درخت ای‌وی‌ال اختلاف ارتفاع دو زیر شاخه هر گره حداکثر برابر یک است؛ بنابراین به این درخت، درخت با ارتفاع متوازن نیز گفته می‌شود.

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

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

برسی سه عدد نسبت به هم دیگر 3! نسبت به  6! دارد

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

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

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

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

فرض کنید یک لیست با 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 از لبه استفاده کنیم
• نباید از لبه هایی که ایجاد حلقه می کنند استفاده کنیم.

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

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

تعیین درخت پوشای مینیمم با الگوریتم کروسکال در سی شارپ

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

همین الان کلیک کنید

تعیین درخت پوشای مینیمم با الگوریتم پریم در سی شارپ #C

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

همین الان کلیک کنید

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

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

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

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

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

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