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

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

 

تفاوت الگوریتم و برنامه در این است که الگوریتم حتما باید پایان پذیر باشد اما برنامه لزوما پایان پذیر نیست .

سیستم عامل یک برنامه است زیرا هیچگاه پایان نمی پذیرد و در یک سیکل انتظار نیست تا برنامه بعدر وارد شود و آن را پردازش کند .

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

به عبارت دیگر پیچیدیگی زمانی و فضایی کمتری دارد.

سرعت اجرا را مرتبه اجرائی هم می گویند .

معیار سنجش کارا آیی یک الگوریتم order یا رتبه الگوریتم است که پیچیدیگی های زمانی و فضایی را نشان می دهد.

 

رتبه برحسب سایز مساله (n) محاسبه می شود .

اگر در حلقه ،متغیر حلقه در عمل ضرب و یا تقسیم شرکت کند ،مرتبه اجرایی لگاریتمی است و عددی که ضرب و یا تقسیم می شود مبنای الگوریتم است .

اگر متغیر حلقه در عمل جمع و یا تفریق شرکت کند ، تعددا تکرار دستور داخل حلقه برابر عددجمع و یا تفریق /n می باشد .

 

اگر تابع بازگشتی باشد تعداد فراخوانی تابع مبنای توان خواهد بود . نحوه کار روی پارامتر های تابع ،توان آن عدد خواهد بود.

 

گاهی اوقات عبارت f(n)=o(g(n)) را به صورت f(n) € o(g(n)) نیز نمایش می دهند.

آرایه

نوعی ساختمان داده است و برای پیاده سازی ساختار های مختلف داده ای بکار می رود . و به صورت A[L..U] که کران U بالا و L کران پایین می باشد . اگر آدرس شروع این آرایه در حافظه آدرس α باشد و هر خانه N بایت حافظه اشعال کند .

 

انگاه آدرس خانه a[i] و تعداد عناصر آرایه از فرمول زیر بدست می آید: : A[I]=α+(I-L)*N آدرس خانه و U-L+1= تعداد عناصر آرایه a که به همین ترتیب می توانیم برای پیمایش سطری و ستونی از آرایه با فرمول مشخص استفاده کنیم

اما در مورد جمع دو ماتریس ها باید گفت که اگر از دوحلقه تودرتو استفاده می شود بنابر این پیچیدیگی زمانی در جمع ماتریس ها برابر (o(mn است .

اگر ماتریس ها مربع باشند o(n^2) زمان اجرای آنها خواهد بود .

 

در ضرب دو ماتریس ، از سه حلقه تودر تو استفاده می شود لذا o(n^3) مناسب ترین مرتبه زمانی برای ماتریس های مربع می باشند . در زمان حذف آرایه n عنصری مقدار متوسط جابجایی[n-1/2] می باشد.

 

به صورت سر انگشتی ،هنگام ضرب چند ماتریس در همدیگر ابتدا آنهایی را در هم ضرب می کنیم که بعد وسطی آنها بزرگتر و بهد های کناری آنها کوچکتر باشد.

 جستجو در آرایه ها به دو صورت انجام می شود :

 1- جستجوی خطی *

 2- جستجوی دودویی *

در جستجوی خطی ،پیچیدگی زمانی برابر تعداد مقایسه ها یعنی o(n) می باشد .

برای یافتن متوسط باید بدترین حالت مقایسه و بهترین حالت مقایسه را در نظر گرفت.بدترین حالت زمانی است که باید کل آرایه را مورد جستچو قرار دهد با n مقایسه .

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

محدودیتهای جستجوی دودویی عبارتند از :

1- آرایه حتما باید مرتب شده باشد .

 

 2- به عنصر وسط هر آرایه باید دسترسی مستقیم وجود داشته باشد

.

حاصلضرب دو ماتریس بالا مثلثی یک ماتریس بالا مثلثی است.

حاصلضرب دو ماتریس پایین مثلثی یک ماتریس پایین مثلثی خواهد شد.

حاصلضرب یک ماتریس پایین مثلثی در یک ماتریس پایین مثلثی یک ماتریس پایین مثلثی خواهد شد.

حاصلضرب یک ماتریس بالا مثلثی در یک ماتریس بالا مثلثی یک ماتریس بالا مثلثی خواهد بود.

ماتریس های sparse به شکل یک ماتریس (n*3) در حافظه ذخیره می شوند.

در اولین سطر در ماتریس اسپارک که شامل ستون های row، col، value است تعداد سطر ها و تعداد ستون ماتریس خلوت و در value تعداد مقادیر غیر صفر قرار می گیرد .

لزوما حاصلضرب دو ماتریس اسپارک یک ماتریس اسپارک نیست .

ادغام دو لیست در بدترین حالت نیاز به n+m-1 مقایسه دارد

ادغام دو لیست در بهترین حالت نیاز به min (m,n) مقایسه دارد .

در مجموعه ،تعداد تکراری وجود ندارد در حالیکه در لیست داده تکراری وجود دارد

داده ها در لیست می توانند مرتب یا نامرتب باشد .

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

 

صف

 

لیستی است که تمامی عملیات درج از یک طرف و تمامی عملیانت حذف از طرف مخالف آن صورت می گیرد .

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

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

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

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

1) عنصری که دارای الویت بیشتر است قبل از تمام عناصری که الویت کمتر دارد پردازش می شود .

2) دو عنصری که دارای الویت یکسان هستند با توجه به تر تیبی که به صف اضافه شده اند پردازش می شوند.

 

 صف الویت بر دو نوع است :

1– صف الویتی نزولی :

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

2- صف الویت صعودی :

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

عمل حذف از صف الویت صعودی عناصر صف را به ترتیب صعودی بازیاری می کند و عمل حذف از صف الویت نزولی عناصر صف را به ترتیب نزولی بازیاری می یکند.

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

1. لیست یکطرفه .
2. استفاده از چند صف نامرتب – مرتب .

3.درخت heap

 

 موارد استفاده از صف :

 پاسخ دهی به درخواستهای دسته ای

(batch) . 2

پاسخ دهی به در خواستهای چاپ .

3.پیمایش سطحی گراف

 

پشته

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

 موارد استفاده از پشته عبارتند :

1. پیمایش عمقی گراف
2. . فراخوانی زیر برنامه ها .
3. در توابع بازگشتی .

4.تبدیل عبارت پسوندی و پیشوندی .

5. پیمایش درختها (چون دارای ساختار بازگشتی هسنتد ) .
6. 6. QUICK SORT .

. HEAP SORT . 7

MAZE.8