stack & heap [بایگانی] - برنامه نویس

MRHagh

شنبه 20 بهمن 1386, 18:36 عصر

دوست عزیز ، خیلی بهتر بود که سوالت رو در بخش ساختمان داده مطرح میکردی ...
Heap یک درخت کامل باینری ( درخت دودوئی که تا سطح nام پر باشد و در سطح n+1 از چپ به راست پر باشد ) است و نوع خاصی از درختان باینری محسوب میشود .
عموما Heap ها بر دو نوع هستند : Max Heap و Min Heap .
Max Heap: درخت باینری کاملی است که مقدار هر ریشه از فرزندانش بیشتر است .
Min HEap : درست بر عکس Max Heap ، درخت باینری کاملی است که مقدار هر ریشه از فرزندانش کوچکتر است .
در پیاده سازی Heap ها از آرایه ستفاده میشود . برای آدرس دهی هر عنصر i از آرایه Heap از دستورات زیر پیروی میشود :
1- اگر i مخالف 1 باشد ، آنگاه پدر i در [i/2] است .
2- اگر 2i کوچکتر یا مساوی n باشد ، آنگاه فرزند چپ i در 2i است و اگر 2i بزرگتر از n باشد ، یعنی i فرزند چپ ندارد .
3- اگر 2i+1 کوچکتر یا مساوی n باشد ، آنگاه فرزند راست i در 2i+1 است و اگر 2i+1 بزرگتر از n باشد ، i فرزند راست ندارد .

در موارد بالا nبرابر تعداد عناصر Heap است .
Stack هم نوعی ساختمان داده هست که عموما با آرایه یا Linked List پیاده سازی میشه . درج و حذف در آرایه یا Linked List ، پشته یا همون Stack ، از قاعده ای به نام LIFO ، تبعیت میکند ( LIFO = Last In Frist Out) یعنی ، مقادیر به ترتیب و پشت سر هم وارد ساختار Stackمیشوند ولی هنگام حذف یا برداشتن چیزی از این ساختار ، به ترتیب اول ، آخرین عناصری که وارد شده اند ، خارج میشوند !
به هر حال اینها بحث های گسترده ای هستند که نیاز به مطالعه دارند . پیشنهاد میکنم ، کتاب ساختمان داده های Horowitz رو مطاله کنید . البته این کتاب مباحث رو با زبان C توضیح میده که برای یادگیری ریشه ای خیلی مناسب . با این حال من هم کتابهایی برای ساختمان داده در Visual Basic دیدم که میتونید از آنها هم اسفاده کنید ... موفق باشید !