تحقیق درباره ساختمان داده ها

دسته بندي: تحقیق و پروژه رایگان,پروژه و تحقیق رایگان,دانش آموزی,تحقیق دانشجویی,

تحقیق درباره ساختمان داده ها

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

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

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

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

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

معيارسنجش كارا آيي يك الگوريتم 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