سلام
توی کتاب داده ساختار های دکتر قدسی، الگوریتم زیر برای حذف عنصر کمینه آورده شده:
[attachment=12695]
و روند کار رو توی این شکل هم نشون داده:
[attachment=12696]
توی توضیحات گفته شده عنصر کمینه t هست که در آخرین مرحله بهش میرسیم، برای حذف کافی است که دستور [tex]r\rightarrow right®[/tex]
انجام شود در صورتی که من فکر میکنم این جلمه اشتباهه و باید مینوشت [tex]r\rightarrow right( left®) )[/tex] و اینطور که اینجا گفته شده اون گره t حذف نمیشه!
به نظرم توی اون الگوریتم هم باید بین خط ۵ و ۶ دستور:
[tex]left( parent®)\leftarrow right®[/tex]
باید اضافه بشه تا درست کار کنه!
نظر شما چیه؟
الگوریتم درسته کاملاً.
توی الگوریتم فرض شده که فراخوانی تابع با مرجع انجام میشه (Call by reference)، بنابراین درون تابع، متغیر اشاره‌گر r (که داره به محل گره جاری اشاره میکنه) در واقع خود متغیر اشاره‌گر چپ پدر گره‌ی جاری هستش که از فراخوانی قبلی به اینجا رسیده! بنابراین اضافه کردن left(parent)->right غلط نیست، ولی کاملاً بیهوده است! (چی در اومد! :دی).
در مورد (r->right(left هم منظورتونو راستش نفهمیدم، چون اگه r ما left داشته باشه که اصلاً وارد این قسمت کد نمیشه چون شرط ورودش null بودن left هستش.
ان r که در شبه کد نوشته با r ای که در شکل می بینی فرق داره . در حقیقت r شبه کد ، t شکل است که قراره حذفش کنیم.در نتیجه این t شکل یا r شبه کد ، همون عنصر کمینه است و فرزند چپی هم نداره که بخوای ان طوری بگی .
(۱۳ شهریور ۱۳۹۲ ۱۰:۴۰ ب.ظ)azk84 نوشته شده توسط: الگوریتم درسته کاملاً.احتمالا ایراد من مربوط به همون توضیح اولی شما درباره call by reference هست! راستش جملات سطر دوم و سوم تون کمی گیج کنندس!
توی الگوریتم فرض شده که فراخوانی تابع با مرجع انجام میشه (Call by reference)، بنابراین درون تابع، متغیر اشاره‌گر r (که داره به محل گره جاری اشاره میکنه) در واقع خود متغیر اشاره‌گر چپ پدر گره‌ی جاری هستش که از فراخوانی قبلی به اینجا رسیده! بنابراین اضافه کردن left(parent)->right غلط نیست، ولی کاملاً بیهوده است! (چی در اومد! :دی).
در مورد (r->right(left هم منظورتونو راستش نفهمیدم، چون اگه r ما left داشته باشه که اصلاً وارد این قسمت کد نمیشه چون شرط ورودش null بودن left هستش.
گفتید r داره به محل گره ی جاری اشاره میکنه؟ من فرض میکنم منظورتون از گره ی جاری همونی گره ی بالایی توی تصویر هست، در این صورت طبق این تصویر t فرزند چپ نداره ولی r هر دو رو داره!
من عرض کردم در این لحظه برای حذف گره ی t باید:
۱- lchild گره ای که r بهش اشاره میکنه رو برابر rchild گره ی t کنیم (این کار عملا گره ی t رو از درخت حذف میکنه)
۲- گره ی t رو Free کنیم!
نقل قول: مطمئن هستید؟ این کد بلافاصله بعد از اون شکل اومده و جدا از م نیستند که باهم فرق کنند، جایی هم اشاره ای به اینکه اینها با هم متفاوت باشند نکرده و به نظرم این خیلی بعیده!
بله مشخص است ؛ من خودم کتاب رو دارم می بینم .
همون‌طور که Aseman7 هم اشاره کرد، شکل کمی گمراه‌کننده‌است و سعی کن با تصور خودت بدون شکل ببینی چی میشه ;-)
منظورم از خط‌های ۲ و ۳ اینه:
r یک متغیر اشاره‌گر هستش که درونش آدرس گره‌ی جاری (گره‌ای که کمینه هستش و فرزند چپ نداره و می‌خوایم حذف شه) قرار داره.
این r در واقع همون ورودی تابع هستش. این ورودی تابع هم از فراخوانی بازگشتی همین تابع در مرحله‌ی قبل اومده که قطعاً پارامتری که اونجا به عنوان ورودی فراخوانی بازگشتی داده شده، [tex]left[r][/tex] بوده. بنابراین، چون فراخوانی با ارجاع هستش، پس r ما توی تابع، خود [tex]left[parent[r]][/tex] خواهد بود!
فکر کنم بازم بد گفتم، ولی امیدوارم بتونین دیکد کنین حرفمو
همون طور که در کتاب هم معلومه این شکل (در ص ۲۲۴ ) مربوط به توضیحات ص قبل است(ص ۲۲۳ ) و اصلا" هم گمراه کننده نیست.
(۱۳ شهریور ۱۳۹۲ ۱۱:۵۱ ب.ظ)Aseman7 نوشته شده توسط: همون طور که در کتاب هم معلومه این شکل (در ص ۲۲۴ ) مربوط به توضیحات ص قبل است(ص ۲۲۳ ) و اصلا" هم گمراه کننده نیست.
آها خوب من نگاه به کتاب نکردم، ببخشید :دی
(۱۳ شهریور ۱۳۹۲ ۱۱:۲۹ ب.ظ)azk84 نوشته شده توسط: همون‌طور که Aseman7 هم اشاره کرد، شکل کمی گمراه‌کننده‌است و سعی کن با تصور خودت بدون شکل ببینی چی میشه ;-)
منظورم از خط‌های ۲ و ۳ اینه:
r یک متغیر اشاره‌گر هستش که درونش آدرس گره‌ی جاری (گره‌ای که کمینه هستش و فرزند چپ نداره و می‌خوایم حذف شه) قرار داره.
این r در واقع همون ورودی تابع هستش. این ورودی تابع هم از فراخوانی بازگشتی همین تابع در مرحله‌ی قبل اومده که قطعاً پارامتری که اونجا به عنوان ورودی فراخوانی بازگشتی داده شده، [tex]left[r][/tex] بوده. بنابراین، چون فراخوانی با ارجاع هستش، پس r ما توی تابع، خود [tex]left[parent[r]][/tex] خواهد بود!
فکر کنم بازم بد گفتم، ولی امیدوارم بتونین دیکد کنین حرفمو
دستتون درد نکنه فهمیدم
یعنی چندین و چند بار همون توضیحات اول شما رو خوندم و متوجه شدم بالاخره. ممنون.
(۱۴ شهریور ۱۳۹۲ ۰۷:۵۷ ب.ظ)هاتف نوشته شده توسط:(13 شهریور ۱۳۹۲ ۱۱:۲۹ ب.ظ)azk84 نوشته شده توسط: همون‌طور که Aseman7 هم اشاره کرد، شکل کمی گمراه‌کننده‌است و سعی کن با تصور خودت بدون شکل ببینی چی میشه ;-)
منظورم از خط‌های ۲ و ۳ اینه:
r یک متغیر اشاره‌گر هستش که درونش آدرس گره‌ی جاری (گره‌ای که کمینه هستش و فرزند چپ نداره و می‌خوایم حذف شه) قرار داره.
این r در واقع همون ورودی تابع هستش. این ورودی تابع هم از فراخوانی بازگشتی همین تابع در مرحله‌ی قبل اومده که قطعاً پارامتری که اونجا به عنوان ورودی فراخوانی بازگشتی داده شده، [tex]left[r][/tex] بوده. بنابراین، چون فراخوانی با ارجاع هستش، پس r ما توی تابع، خود [tex]left[parent[r]][/tex] خواهد بود!
فکر کنم بازم بد گفتم، ولی امیدوارم بتونین دیکد کنین حرفمو
دستتون درد نکنه فهمیدم
یعنی چندین و چند بار همون توضیحات اول شما رو خوندم و متوجه شدم بالاخره. ممنون.
خوشحالم که توضیحاتم به دردتون خورد :-). خواهش میکنم ;-)