ساختمان داده ها به زبان C

ساختمان داده ها به زبان C

اسلاید 1: ساختمان داده ها به زبان Cتهيه کننده: سيده فاطمه نورانيگروه: کامپيوتردانشگاه پيام نورData Structure in C

اسلاید 2: شناسنامه منبععنوان منبع: ساختمان داده ها به زبان Cمترجم: امير عليخانزادهانتشارات: باغانيمنبع اصلي:Fundamental of data Structure in CHorowitz Ellis

اسلاید 3: جايگاه درس در رشته کامپيوترضرورت اين درس:ضرورت نياز به زبانهاي سطح بالاضرورت ترجمه برنامه هاي نوشته شده با زبان سطح بالا به برنامه به زبان ماشينتنوع زبانهاي برنامه نويسي سطح بالادروس پيش نياز:نوع درس: اجباريتعدادکل ساعات تدريس: 30تعداد جلسات تدريس:10

اسلاید 4: فصل اول : مفاهيم اساسيآشنايي با سيکل زندگي نرم افزارآشنايي با الگوريتماهداف

اسلاید 5: 1-1 سيکل زندگي نرم افزار-نیازمندی هانیازمندیهاتمام پروژه هاي بزرگ برنامه نويسي با مجموعه اي از مشخصات و خصوصياتي که اهداف پروژه را مشخص مي کند، شروع مي شود. اين نيازمنديها اطلاعاتي را به برنامه نويسان مي دهند(ورودي) و نيز نتايجي را که بايد ايجاد گردد(خروجي) تعيين مي کنند.

اسلاید 6: 1-1 سيکل زندگي نرم افزار- تحلیلتحليل: در اين مرحله مساله را به بخشهاي قابل کنترل تقسيم مي کنند.در تحليل يک سيستم دو شيوه وجود دارد : 1- شيوه از بالا به پايين 2- شيوه از پايين به بالا

اسلاید 7: 1-1 سيکل زندگي نرم افزار- طراحیطراحي اين مرحله ادامه کاري است که در مرحله تحليل انجام مي شود.طراح سيستم را از دو نقطه نظر بررسي مي کند:از نظرداده هاي مقصود(data objects) مورد نياز برنامهاز نظر اعمالي که بر روي آنها انجام مي شود. اين ديدگاه به مشخصات الگوريتم ها و فرضيات خط مشي ها ي طراحي الگوريتم نياز دارد.ايجاد نوع داده مجرد

اسلاید 8: 1-1 سيکل زندگي نرم افزار- ... پالايش(اصلاح) و کدنويسي: در اين مرحله، نمايشي براي داده هاي مقصد خود انتخاب مي شود و براي هر عملي که بر روي آنها انجام مي شود، الگوريتم نوشته مي شود. بازبيني: در اين مرحله درستي برنامه ها اثبات مي شود و برنامه ها با انواع داده هاي ورودي مختلف تست و خطاهاي برنامه رفع مي شود.جنبه هاي مهم بازبيني: اثبات درستیتستاشکال زدايي

اسلاید 9: 1-1 نمودار سيکل زندگي نرم افزارنيازمنديهاتحليلطراحيپالايش و کدنويسيبازبيني

اسلاید 10: 2-1 تعريف الگوريتمالگوريتم مجموعه اي از دستورالعمل ها است که اگر دنبال شوند، موجب انجام کار خاصي مي گردد

اسلاید 11: ورودي: يک الگوريتم مي تواند هيچ يا چندين کميت ورودي داشته باشدکه از محيط خارج تامين مي شود. خروجي: الگوريتم بايستي حداقل يک کميت به عنوان خروجي داشته باشد. قطعيت: هر دستورالعمل بايد واضح و بدون ابهام باشد. محدوديت: اگر دستوذالعمل هاي يک الگوريتم را دنبال کنيم ،براي تمام حالات ، الگوريتم بايد پس از طي مراحل محدودي خاتمه يابد. کارايي: هر دستورالعمل بايد به گونه اي باشد که با استفاده از قلم و کاغذ بتوان آن را با دست نيز اجرا نمود.2-1 شرايط الگوريتم

اسلاید 12: 2-1 مثالی از الگوريتم: الگوریتم مرتب سازيfor(i=0 ; i<n ;i++){Examine list [ i ] to list [n-1] and suppose that the smallest integer is at list [min];Interchange list [ i ] and list [min];

اسلاید 13: 2-1 الگوريتم بازگشتيتابع چيزي است که توسط تابع ديگر فراخوانده مي شود . توابع مي توانند خودشان را صدا بزنند (بازگشت مستقيم ) يا مي توانند توابعي که تابع فراخواننده را صدا ميزنند(بازگشتي غيرمستقيم) را احضار نمايند.

اسلاید 14: 2-1 مثال الگوريتم جستجوي دودوييint binsearch ( int list [ ] ، int searchnum ، int left ، int right ){/* search list [0] <= list [1] <= … <=list [ n-1 ] for searchnum Return its position if found . Otherwise return -1 */int middle ;if (left <= right ) {middle = ( left + right ) / 2 ;switch ( COMPARE ( list [ middle ] ، searchnum )) {case -1 : returnbinsearch ( list ، searchnum ، middle +1 ، right ) ;case 0 : return middle ;case 1 : returnbinsearch ( list ، searchnum ، left ، middle -1 ) ;}}return -1 ;}

اسلاید 15: 3-1 آرايه ، ساختار و نوع دادهمجموعه اي از عناصر از يک نوع داده مي باشدمجموعه اي از عناصر است که لزومي ندارد داده هاي آن يکسان باشدمجموعه اي از انواع داده مقصد(object) و عملکردهايي است که بر روي اين نوع داده ها عمل مي کنندآرايهساختارنوع داده

اسلاید 16: 3-1 نوع داده اي مجرد نوع داده مجرد یا انتزاعی (ADT) که شامل مشخصات داده ها و اعمالی که بر روی آنها انجام می شود.جهت جداسازی پياده سازی و نمایش داده ها از یکدیگر.

اسلاید 17: 3-1 نوع داده مجردتوابع يک نوع داده به گروه هاي زير تقسيم مي شوند:1- ايجادکننده/ سازنده2- تبديل کنندگان3- مشاهده کنندگان / گزارش کنندگان

اسلاید 18: 4-1 تحليل نحوه اجراي يک برنامهمعيارهاي محک زدن يک برنامه آيا برنامه اهداف اصلي کاري را که مي خواهيم، انجام مي دهد؟ آيا برنامه درست کار مي کند؟ آيا برنامه مستند سازي شده است تا نحوه استفاده و طرز کار با آن مشخص شود؟ آيا برنامه براي ايجاد واحدهاي منطقي ، به طور موثر از توابع استفاده مي کند؟ آيا کد گذاري خوانا است؟ آيا برنامه از حافظه اصلي و کمکي به طور موثري استفاده مي کند؟ آيا زمان اجراي برنامه براي هدف شما قابل قبول است؟اين قسمت مربوط به تخمين هاي حافظه و زمان مورد نياز بوده و مستقل از ماشين است . اين قسمت را تحليل نحوه اجراي برنامه مي ناميم.

اسلاید 19: 4-1 ميزان حافظه يا پيچيدگي فضاي يک برنامهميزان حافظه يا پيچيدگي فضاي يک برنامه مقدارحافظه مورد نيازبراي اجراي کامل يک برنامه است.ميزان يا پيچيدگي زمان يک برنامه مقدار زمان کامپيوتر است که براي اجراي کامل برنامه لازم است.

اسلاید 20: 4-1 ميزان حافظهفضاي مورد نياز يک برنامه شامل موارد زير است :اين مطلب به فضاي مورد نيازي که به تعداد و اندازه ورودي و خروجي بستگي ندارد، اشاره دارد.اين مورد شامل فضاي مورد نياز متغيرهاي ساخت يافته اي است که اندازه آن بستگي به نمونه I از مساله اي که حل مي شود، دارد.نيازمنديهاي فضاي ثابتنيازمنديهاي فضاي متغير

اسلاید 21: 4-1 ميزان حافظه(ادامه)نيازمنديهاي فضاي کلنيازمنديهاي فضاي ثابت نيازمنديهاي فضاي متغير

اسلاید 22: 4-1 زمان T(P) برنامهزمان T(P) برنامه عبارتست ازمجموع زمان کامپايل و زمان اجراي برنامه.زمان کامپايل مشابه اجزاي فضاي ثابت است زيرابه خصيصه هاي نمونه بستگي ندارد. را به صورت زير تعريف مي شود:

اسلاید 23: 4-1 مرحله برنامهيک مرحله برنامه ، قسمت با معني برنامه است ( از لحاظ معنايي يا نحوي) که زمان اجراي آن مستقل از خصيصه هاي نمونه باشد

اسلاید 24: 4-1علامت گذاري مجانبي(O، Ω ،Θ)(Asymptotic)انگيزه براي تعيين تعداد مراحل، قابليت مقايسه پيچيدگي دو برنامه که يک تابع را اجرا مي کنند و پيش بيني رشد و افزايش زمان اجرا با تغيير صفات نمونه مي باشد. f(n)=O(g(n)) [Big “oh” ] است ( خوانده مي شود (“f of n is big oh of g of n “ اگر و فقط اگر به ازاي مقادير ثابتي از f(n)،n0،c براي تمامي مقاديز n کمتر يا مساوي g(n) باشد (n ≥ n0)

اسلاید 25: 4-1علامت گذاري مجانبي(O، Ω ،Θ)(Asymptotic)O(1) : زمان محاسبه ثابتي را نشان مي دهد O(n) : يک تابع خطي ناميده مي شود : تابع درجه دو ناميده مي شوداگر باشد، بنابراين خواهد بود قضيه :

اسلاید 26: 4-1 علامت گذاري مجانبي(O، Ω ،Θ)(Asymptotic)تعريف:]امگا [: f(n)=Ω(g(n)) مي باشد(خوانده مي شود f(n) امگاي g(n) اگر و فقط اگر به ازاي مقادير ثابت مثبت c و n0 ، f(n)≥cg(n) باشد(براي تمام مقادير n به شرطي که n≥n0 باشد)اگر باشد، و بنابراين خواهد بود قضيه :

اسلاید 27: 4-1 علامت گذاري مجانبي(O، Ω ،Θ)(Asymptotic)تعريف تتا[Theta] : f(n) = θ(g(n)مي باشد (خوانده مي شود f(n) تتاي (g(n) اگر و فقط اگر به ازاي مقادير ثابت c1 و c2 و n0، c1g(n)<= f(n) <= c2g(n) وجود داشته باشد (براي تمام مقاديرn>=n0)نشانه گذاري تتا از دو نشانه گذاري ذکر شده “ big oh “ و امگا دقيق تر مي باشد . f(n) = Θ(g(n)) مي باشد اگر و فقط اگر g(n) هم به عنوان کرانه بالا و هم به عنوان کرانه پايين در f(n) باشد.

اسلاید 28: 4-1 علامت گذاري مجانبي(O، Ω ،Θ)(Asymptotic)اگر باشد، و بنابراين خواهد بود قضيه :

اسلاید 29: 4-1 مثال(پيچيدگي جمع ماتريس ها)

اسلاید 30: 5-1روش هاي اندازه گيري زمان رويدادها در Cدو روش متفاوت وجود دارد :روش و مدل اول از ساعت (clock) براي زمان بندي رويدادها استفاده مي کند. اين تابع ، زمان تلف شده از آغاز برنامه به وسيله پردازنده را مي دهد. براي زمان بندي يک رويداد دوبار از ساعت استفاده مي شود. يک مرتبه در ابتداي رويداد و يک مرتبه در انتهاي آن.روش يا مدل دوم ازtime استفاده مي کند. اين تابع ، زمان را بر حسب ثانيه به عنوان نوع پيش ساخته time-t برمي گرداند. بر خلاف clock ، time فقط يک پارامتر دارد که به وسيله آن موقعيتي را که زمان بايد نگهداري شود ، مشخص مي کند.

اسلاید 31: 5-1 توليد داده هاي آزمايشي براي ايجاد بدترين حالت اجراايجاد داده هاي آزمايشي که منجر به بدترين حالت اجرا مي شود ، هميشه ساده نيست.در بعضي از موارد لازم است که از يک برنامه کامپيوتري براي ايجاد بدتريت حالت استفاده مي شود.براي هر مجموعه مقادير از صفات نمونه مورد نظر ، يک داده آزمايشي تصادفي با عددي به اندازه کافي بزرگ ايجاد مي کنيم زمان اجراي هر کدام از اين داده هاي آزمايشي به دست مي آيد

اسلاید 32: فصل دوم : آرايه هاآرايهساختارليستماتريس اسپارسرشتهاهدافدر این فصل دانشجو با کاربرد موارد زیر آشنا خواهد شد:

اسلاید 33: فصل دوم : آرايه ها و ساختارهاآرايه مجموعه اي از زوج ها ، شامل انديس و مقدار است (<index ، value>) . به ازاي هر انديس يک مقدار مربوط به آن انديس وجود دارد که به زبان رياضي آنرا تناظر يا انگاشت ناميده مي شود.آرايهدر رابطه با آرايه به دو عمل اساسي نياز است : بازيابي ذخيره سازي مقادير

اسلاید 34: 1-2 آرايه هاتابعCreat(J،list) : يک آرايه جديد تهي با طول مناسب را توليد مي کند. تمتم مقادير در ابتدا تعريف نشده اند.تابع Retrieve : يک آرايه و يک انديس را به عنوان ورودي دريافت مي کند و يک مقدار مربوط به انديس را اگر انديس معتبر باشد برميگرداند و گرنه يک خطا را بازمي گرداند.تابع store : براي وارد کردن زوج جديدي شامل < انديس، مقدار> به کار مي رود و آرايه اوليه افزايش يافته با زوج جديد،<مقدار،انديس> را بازمي گرداند.

اسلاید 35: 1-2 آرايه هاآرايه در زبان C به صورت مثال در زير آمده است :int list [5]در زبان C تمام آرايه ها از انديس 0 شروع مي شوند.نکته

اسلاید 36: ساختارها آرايه ها مجموع داده هاي از يک نوع مي باشند. در C روش ديگري براي دسته بندي گروهي از داده وجود دارد . اين روش اجازه مي دهد تا داده ها از انواع متفاوتي باشند. اين امکان را struct مي گويند که مختصر structure است. يک ساختار مجموعه اي از اقلام داده ها مي باشد که هر قلم داده به وسيله نوع و نام آن مشخص گرديده است.ساختار

اسلاید 37: ساختارهامثال:Struct{char name[10];int age;float salary;}personمتغيري به نام person ايجاد مي کند که داراي سه فيلد متفاوت است : نام شخص به صورت يک آرايه کاراکتري است . يک مقدار صحيح که نشان دهنده سن همان شخص است. يک مقدار float که حقوق شخص را معين مي کند.

اسلاید 38: يونيون هااعلان يونيون مشابه تعريف و اعلان يک ساختار است با اين تفاوت که فيلدهاي يک يونيون بايد در حافظه با هم مشترک باشند يعني فقط يک فيلد يونيون در هر زمان فعال مي گردد.يونيون

اسلاید 39: ساختارهاي خود ارجاعي يک ساختار خودارجاعي ساختاري است که در آن يک جز يا بيشتر ، اشاره گري به خود آن مي باشد.ساختارهاي خود ارجاعي معمولا به روالهاي مديريت حافظه پويا احتياج دارند (malloc free) تا به راحتي حافظه را گرفته و آزاد کنند.

اسلاید 40: ليستساده ترين و متداول ترين نوع ساختمان داده ها ، ليست هاي مرتب شده يا خطي هستند. ليستمثال : روزهاي هفته ( شنبه ... جمعه )ليست ها شامل اقلام داده به صورت مي باشند.

اسلاید 41: اعمال صورت گرفته بر روي ليست ها پيدا کردن طول يک ليست خواندن اقلام داده يک ليست از چپ به راست يا بر عکس بازيابي i امين عنصر از يک ليست (0≤ i < n) تعويض يک قلم اطلاعاتي در i امين موقعيت يک ليست (0≤ i ≤ n) درج يک قلم داده جديد در i امين موقعيت يک ليست (0≤ i < n). ( اقلام داده اي که قبلا به صورت i ، i+1 ،…،n-1 شماره گذاري شده اند به صورت i+1،i+2،…،n در مي آيند) حذف يک قلم اطلاعاتي از i امين موقعيت يک ليست (0≤ i < n) . اقلام داده i+1،…،n-1 به اقلام داده با شماره I،i+1،…،n-2 تبديل مي شود.

اسلاید 42: نگاشت ترتيبيمتداول ترين پياده سازي ، نمايش يک ليست مرتب شده به صورت يک آرايه مي باشد به نحوي که عنصر ليست با انديکس i آرايه متناظر باشد. اين مطلب يک نگاشت ترتيبي ناميده مي شود.نگاشت ترتيبي

اسلاید 43: ADT ماتريس اسپارسبه طور کلي در رياضيات ، يک ماتريس شامل m سطر و n ستون بوده و مي تواند مانند شکل زير نمايش داده شود.27-346822-10964-111289482747row 0row 1row 2row 3row 4col1col2col3

اسلاید 44: ADT ماتريس اسپارسدر علوم کامپيوتر متداول ترين نمايش براي ماتريس آرايه دوبعدي است که به صورت a[MAX_ROW][MAX_COLS] نمايش داده مي شود. هر عنصر ماتريس به صورت a[i][j] نمايش داده مي شود. ماتريسي که عناصر صفر آن زياد بوده ماتريس اسپارس ناميده مي شود.ماتريس اسپارسحداقل اعمال ممکن شامل ايجاد، جمع ، ضرب و ترانهاده ماتريس مي باشد.

اسلاید 45: مي توان هر آرايه را با استفاده از سه گانه ذخيره نمود اين بدان معنا مي باشد که مي توان يک آرايه از سه گانه ها را براي نمايش يک ماتريس اسپارس پيشنهاد کرد.ADT ماتريس اسپارس

اسلاید 46: ترانهاده يک ماتريسبراي پيدا نمودن ترانهاده يک ماتريس بايد جاي سطرها و ستون ها را عوض کرد بدين مفهوم که هر عنصر a[i][j] در ماتريس اوليه به عنصرb[j][i] در ماتريس ترانهاده تبديل مي شود. الگوريتم زير براي پيدا کردن ترانهاده يک ماتريس ، الگوريتم مناسبي است :for all element is column jplace element < i ، j ،value> inelement < j ، i ،value>

اسلاید 47: ترانهاده يک ماتريسالگوريتم بيان شده نشان مي دهد که بايد تمام عناصر در ستون 0 را پيدا و آنها را در سطر 0 ذخيره کرد همچنين تمام عناصر ستون 1 را پيدا و در سطر 1 قرار داد و همين فرآيند را ادامه داد. از آنجا که ماتريس اوليه سطري بوده لذا ستون هاي داخل هر سطر از ماتريس ترانهاده نيز به صورت صعودي مرتب مي شود.

اسلاید 48: تحليل ترانهادهتعيين زمان اجراي اين الگوريتم از آنجا که حلقه هاي تودرتوي for عامل تعيين کننده مي باشد ، آسان است.حلقه for خارجي a[0].col مرتبه تکرار مي شود که a[0].col حاوي تعداد ستون هاي ماتريس اوليه است. علاوه بر اين ، يک يک تکرار حلقه داخلي for به زماني برابر باa[0].value نياز دارد که در اينجا ، a[0].value تعداد عناصر در ماتريس اوليه است. بنابراين زمان کلي براي حلقه هاي تودرتوي for برابر با حاصل ضرب ستون ها در عناصر(columns.elements) مي باشد. بنابراين زمان اجرا به صورت 0(columns.elements) خواهد بود.

اسلاید 49: ضرب ماتريسبا توجه به ماتريس هاي مشخص و معلوم A وB ، فرض کنيد که A يک ماتريس m×n و B يک ماتريس m×p باشد آنگاه ماتريس حاصل ضرب D داراي ابعاد m×p است و عنصر <i،j> آن به صورت زير تعريف مي شود :براي 0 ≤ j < p و 0 ≤ i < m نکته : حاصل ضرب دو ماتريس اسپارس ممکن است يک ماتريس اسپارس نباشد.

اسلاید 50: روالmmult در روال mmult ماتريس هاي A وB را ضرب کرده و با توجه بهتوضيحات حاصل ضرب را در D قرار مي دهيم.A ، B ، D به عنوان ماتريس هاي اسپارس به ترتيب در آرايه هايA ، b ،d ذخيره مي شوند.زمان اين الگوريتم برابر با O(rows_a . Cols_a . cols_b)است

اسلاید 51: نمايش آرايه هاي چند بعديدو راه متداول براي نمايش آرايه هاي چند بعدي وجود دارد :روش سطريروش ستونيدر روش سطري آرايه هاي چند بعدي را به وسيله سطرهاي آن ذخيره مي کنيم. روش سطريمثالآرايه دو بعدي نشان مي دهد که داراي سطر استبه نحوي که هر سطر شامل عنصر مي باشد.

اسلاید 52: نمايش آرايه هاي چند بعدياگرα آدرس A[0][0] باشد، بنابراين آدرس A[i][0] ، α+ i. Upper خواهد بود.مثال براي نمايش يک آرايه سه بعدي ، آن را به عنوان آرايه دو بعدي با ابعاد در نظر مي گيريم.

اسلاید 53: نوع داده مجرد رشته اي(STRING ADT) از ديدگاه ADT يک رشته به صورت تعريف مي گردد به نحوي که کاراکترهاي اخذ شده از مجموعه کاراکترهايزبان برنامه نويسي مي باشد. اگر n=0 باشد،S يک رشته تهي مي باشد.در زبان C ، رشته ها به صورت آرايه هاي کاراکتري که به کاراکترتهي، 0،ختم مي شوند ،آرايه مي گردد.

اسلاید 54: نوع داده مجرد رشته اي(STRING ADT) عملکردهاي مناسب و مفيدي وجود دارد که مي توان براي رشته ها تعريفکرد مانند : ايجاد يک رشته تهي جديدخواندن يا نوشتن يک رشته ضميمه کردن دو رشته به يکديگر (concatenation) کپي کردن يک رشتهمقايسه رشته هادرج کردن يک زير رشته به داخل رشتهبرداشتن يک زير رشته از يک رشته مشخصپيدا کردن يک الگو(pattern) يا عبارت در يک رشتهمختص ADT جديد

اسلاید 55: نوع داده مجرد رشته اي(STRING ADT) نحوه ذخيره سازي در حافظه :char s[] = {dog”{ ;s[0]s[1] s[2] s[3]نمايش رشته در زبان C

اسلاید 56: مثال : درج رشتهمي خواهيم رشته t را در موقعيت رشته s جاي دهيم :0elibomotua0otua0a0sttempinitially(a) After strncpy(temp،s،i)(b) After strcat(temp،t)temptemptemp

اسلاید 57: تطابق الگو(Pattern Matching)فرض کنيد که دو رشته داريم ، string وpat، به نحوي pat يک الگو يا pattern بوده و بايد در string پيدا شود. ساده ترين راه براي تعيين اينکه آيا pat در رشته وجود دارد يا خير ، استفاده از تابع کتابخانه اي strstr مي باشد.با وجود اينکه strstr براي تطابق عبارت مناسب به نظر مي رسد ، دو دليل عمده براي نوشتن تابع تطابق الگو وجود دارد : تابع strstr براي ANSI C. جديد بوده و ممکن است که در کامپايلر موجود نباشد. چندين روش براي پياده سازي تابع تطابق الگو وجود دارد.

اسلاید 58: تطابق الگوغير موثرترين روش ، تست متوالي هر کاراکتر رشته تا زمان پيدا شدن الگو و يا رسيدن به انتهاي رشته ، مي باشد. اگر pat در string نباشد، اين روش داراي زمان محاسباتي 0(n،m) خواهد بود که در آن n طول patوm طول string مي باشد. نکته

اسلاید 59: فصل سوم : صف وپشتهآشنايي با پشتهآشنايي با صفارزشيابي عباراتاهداف

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

اسلاید 61: پشتهمحدوديت کار با پشته ما را ملزم مي کند که اگر عناصر A،B،C،D،E را به ترتيب به پشته اضافه کنيم ، E اولين عنصري خواهد بود که که از پشته حذف مي گردد.از آنجا که آخرين عنصر وارده به پشته ، اولين عنصر حذف شده از آن مي باشد ، پشته را به عنوان يک ليست LIFO (آخرين ورودي ، آخرين خروجي ) مي شناسيم.

اسلاید 62: پشتهCBA← top← top← topDCBAEDCBADCBA← top← top←topحذف و جايگذاري عناصر در يک پشته

اسلاید 63: ساختار نوع داده مجرد پشتهstructure srack isobjects: a fine ordered list with zero or more elements.functions:for all stack Stack ، item element ، max_stack_size positive integreStack CreateS(max_stack_size)::=creat an empty stack whose maximume size is max_stack_sizeBoolean IsFull(stack،max_stack_size)::=if(number of elements in stack == max_stack_size)return TRUEelse return FALSEStack Add(stack،item)::=if (IsFull (stack)stack_fullelse insert item into top of stack and returnBoolean IsEmpty (stack)::=if(stack ==Creat S( max_stack_size)return TRUEelse return FALSEElement Delete (stack)::=if (IsEmpty (stack)returnelse remove and return the item on the top of the stack

اسلاید 64: پياده سازي پشتهراحت ترين روش پياده سازي اين ADT ، استفاده از يک آرايه يک بعدي به نام stack[MAX_STACK_SIZE] است که [MAX_STACK_SIZE] حداکثر تعداد عناصر آرايه مي باشد. اولين يا پايين ترين عنصر پشته درstack[0] ذخيره ، دومي در stack[1] و i امين عنصر در stack[i-1] ذخيره مي گردد.همراه با آرايه ، يک متغير به نام top وجود دارد که به عنصر بالايي پشته اشاره مي کند. در ابتدا به top مقدار 1- داده مي شود که نشان دهنده يک پشته خالي است. با اين نمايش ، مي توانيم عملکردهاي ساختار را به صورت زير پياده سازي کنيم :

اسلاید 65: پياده سازي پشته Stack CreatS(max_stack_size)::=#define MAX_STACK_SIZE 100 /* maximume stack size*/typedef struct {int key;/* other fields*/}element;Element stack [MAX_STACK_SIZE];int top = -1;Boolean IsEmpty(Stack)::=top<0;Boolean IsFull(Stack)::= top >= MAX_STACK_SIZE-1;

اسلاید 66: جايگذاري به يک پشتهVoid add (int *top ، element item){/* add an item to the global stack */if (* top > = MAX_STACK_SIZE-1) {stack_full();return;}stack [++*top] = item;}

اسلاید 67: حذف از يک پشتهelement delete (int * top ){/* return the top element from the stack */ if (* top == -1)return stack _empty (); /* returns an error key */return stack [( * top)--];}

اسلاید 68: صفصف يک ليست مرتب شده است که تمامي جايگذاري آن از يک سمت و تمام حذف هاي ان از سمت ديگر انجام مي شود.صفدرصف ، عنصر ابتدا (front) وعنصر انتها (rear) مي باشد ودر کنار قرار دارد (0≤ i < n-1)

اسلاید 69: صفمحدوديت صف اين است که ما A،B،C،D را به ترتيب اضافه مي کنيم در حالي که A اولين عنصري است که حذف مي شود.ABACBA← rearDCBADCB← front← rear← front← rear← front← rear← front← rear← frontدرج و حذف عناصر از يک صف

اسلاید 70: صفاز آنجا که اولين وارد شده به يک صف ، اولين عنصري است که خارج مي شود ، صف را به عنوان ليست هاي FIFO ( اولين ورودي، اولين خروجي ) در نظر مي گيرند.

اسلاید 71: جايگذاري در صفVoid addq ( int * rear ، element item ){/* add an item to the queue */if (* rear ==MAX_QUEUE _SIZE -1) {queue_full();retyrn;}queue[++* rear] = item;}

اسلاید 72: حذف عنصري از يک صفelement deleteq (int *front ، int rear ){/* remove element at the front of the queue */if (* front == rear )return queue_empty (); /* return an error key */return queue [==* front];}

اسلاید 73: مساله مسير پر پيچ و خم (MAZING) بهترين راه نمايش مسير فوق يک آرايه دو بعدي است که صفرهاي آن نشان دهنده پيچ و خم هاي مسير مي باشد. يک مسير پر پيچ و خم (maze) با ابعاد m×p به يک آرايه (m+2)×(p+2) نياز دارد. ورودي در موقعيت [1][1] و خروجي در موقعيت [m][p] مي باشد.

اسلاید 74: تحليل مسيراندازه مسير پرپيچ و خم (maze) زمان اجراي مسير را تعيين مي کند . از آنجا که هر موقعيت درون مسير بيش از يک بار مشاهده نمي شود ، بدترين حالت پيچيدگي الگوريتم به صورت 0(mp) مي باشد به نحوي که m و p تعداد سطرها و ستون هاي مسير است.

اسلاید 75: ارزشيابي عباراتدر هر زبان برنامه سازي براي ارزيابي صحيح عبارات ، به هر عملگر اولويتي نسبت مي دهيم. حال در هر جفت پرانتز ، اول عملگرهايي که داراي اولويت بالاتر هستند ، ارزشيابي مي شوند .

اسلاید 76: اولويت عملگرهاشکل مقابل نشان دهنده اولويت عملگرها در زبان c مي باشد.

اسلاید 77: روش infixروش استاندارد نوشتن عبارات به عنوان infix معرفي و شناخته مي شود چرا که در اين روش عملگرهاي دودويي را در بين دو عملوند قرار مي دهيم.

اسلاید 78: نشانه گذاري postfixدراين روش هر عملگر بعد از عملوند هاي مربوطه ظاهر مي شودمثال

اسلاید 79: خصوصيات postfixعبارات براي ارزيابي از چپ به راست پويش مي شوند. عملوندها تا مشاهده يک عملگر، داخل پشته قرار مي گيرند، سپس تعداد لازم از عملوندها را از پشته خارج و پس از انجام عملکرد مربوطه ، نتيجه را دوباره به داخل پشته منتقل مي کنيم . اين کار را ادامه پيدا مي کند تا به انتهاي عبارت برسيم.

اسلاید 80: الگوريتم تبديل infix به postfixمي توان الگوريتمي براي تبديل يک عبارت infix به postfix به صورت زير بيان نمود :1- پرانتزگذاري کامل عبارات2- انتقال همه عملگرهاي دودويي به نحوي که با پرانتز بسته مربوطه سمت راست آن تعويض شوند3- حذف تمام پرانتزها

اسلاید 81: مثالتبديل عبارت a+b*c به نشانه گذاري postfix

اسلاید 82: مثالتبديل a*(b+c)*d به نشانه گذاري postfix

اسلاید 83: تحليل postfixفرض کنيد n تعداد نشانه ها در عبارت باشد ، براي خارج ساختن نشانه ها و انتقال آنها به خروجي نياز به Θ(n) مي باشد. بنابراين پيچيدگي تابع postfix به صورت Θ(n) خواهد بود.

اسلاید 84: فصل چهارم: ليست هاآشنايي با اشاره گر هاليست ها و ليست حلقويروابط هم ارزيليست پيوندي دوگانهاهداف

اسلاید 85: ويژگي هاي نمايش ساختمان داده ها با استفاده از آرايه و نگاشت ترتيبي: فصل چهارم : ليستهاخاصيت اين نحوه نمايش آن بود که عناصر پشت سرهم داده مقصود با فواصل ثابت و معيني ذخيره مي شدند. بنابراين : اگرi امين عنصر صف در موقعيت باشد، (i+1) امين عنصر، در نمايش حلقوي در موقعيت+c)%MAX_QUEUE_SIZE ( قرار خواهد گرفت . اگر بالاترين عنصر پشته در مکان باشد، پايين ترين عنصر در مکان خواهد بود.

اسلاید 86: 2- وقتي داراي چندين ليست مرتب شده با طول هاي متفاوت هستيم. باذخيره کردن هر ليست در آرايه اي با حداکثر اندازه ، حافظه هدر مي رود3- با نگهداري ليستها در يک آرايه ، انتقال حجم زيادي از داده ها لازم است.مشکلات نمايش ترتيبي1- حذف و درج عناصر در آرايه ها بسيار وقت گير است

اسلاید 87: نمايش پيونديراه حل مناسب براي حل مشکل شيفت داده ها در نگاشت ترتيبي ، استفاده از نمايش پيوندي مي باشد. بر خلاف نمايش ترتيبي که عناصر در فواصل ثابتي از هم قرار مي گرفتند، در ليست پيوندي عناصر مي توانند در هر جاي حافظه قرار گيرند.براي دستيابي صحيح به عناصر يک ليست ، بايستي به همراه هر عنصر، آدرس يا موقعيت عنصر بعدي نيز ذخيره شود. بنابراين براي هر عنصر ، اشاره گري به عنصر بعدي در ليست وجود دارد.

اسلاید 88: اشاره گرهامهمترين عملگرهاي استفاده شده با نوع اشاره گر عبارتند از : & عملگر آدرس * عملگر غيررجوعي(indirection or dereferencing) int i ، * pi ; آنگاه i يک متغير صحيح و pi يک اشاره گر به يک متغير صحيح است.pi = &i ;&i آدرس i را برگشت و به ان مقدار pi را نسبت مي دهد.مثال

اسلاید 89: خطر استفاده از اشاره گرهادر هنگام برنامه نويسي به زبان C بهتر است که تمام اشاره گرهايي را که عملا به جايي اشاره نمي کنند را برابر NULL قرار دهيم. اين عمل از تلاش براي دستيابي به قسمتي از حافظه که خارج از دامنه برنامه شما بوده و يا شامل اشاره گري به يک داده مقصود قابل دسترسي نيست ، جلوگيري مي کند.

اسلاید 90: استفاده از حافظه پويا( استفاده ازheap)در يک برنامه ممکن است خواسته باشيم فضاي لازم براي ذخيره کردن اطلاعات را در نظر بگيريم. هنگام برنامه نويسي ممکن است ندانيم چه ميزان فضا لازم داشته يا نخواسته باشيم فضاي بسيار زيادي که احتمال دارد استفاده نشود را تخصيص دهيم، براي حل اين مشکل ، زبانC در زمان اجرا از مکانيزمي به نام heap براي تخصيص حافظه استفاده مي کند.

اسلاید 91: هر زمان که نياز به حافظه جديدي باشد ، مي توان تابعي به نام malloc را فراخواني و مقدار فضاي لازم را درخواست کرد. اگر حافظه لازم وجود داشته باشد ، اشاره گري به ابتداي ناحيه حافظه مورد نياز برگردانده مي شود. زماني که ديگر نيازي به آن حافظه نباشد ، مي توان آن را با فراخواني تابعي به نام free ، آزاد نمود.استفاده از حافظه پويا( استفاده ازheap)

اسلاید 92: ليست هاي تک پيونديليست هاي پيوندي معمولا به وسيله گره هايي متوالي با اتصالاتي که به صورت فلش هايي نشان داده شده اند ارايه مي گردند. از نام اشاره گر به اولين عنصر ليست به عنوان نام کل ليست استفاده مي شود. بنابراين ليست شکل زير ptr ناميده مي شود.

اسلاید 93: ليست هاي پيونديbat.cat.sat.vat NULLptr گره ها واقعا در مکانهاي پشت سر هم حافظه قرار نمي گيرند(2) موقعيت گره ها در اجراهاي مختلف مي تواند تغيير کندنکاتروش معمول براي نمايش يک ليست پيوندي

اسلاید 94: مثالمراحل درج کلمه mat بين cat و sat به صورت زير است : 1- گره اي را که اخيرا استفاده نشده در نظر گرفته ، فزض کنيد که آدرس آن paddr باشد.2- فيلد داده اين گره را برابر با mat قرار دهيد3- فيلد اتصال paddr را طوري تنظيم کنيد که به ادرسي که در فيلد اتصال گره حاوي cat مي باشد، اشاره کند4- فيلد اتصال گره حاوي cat را طوري تنظيم کنيد که به paddr اشاره کند.

اسلاید 95: مثال(درج گره mat بعد از cat)نحوه تغيير ليست بعد از اضافه کردن mat در شکل زير نشان داده شده است :bat.cat.sat.vat NULLptrmat.

اسلاید 96: حذف mat از ليستبراي انجام اين کار فقط لازم است که عنصر قبل از mat يعني cat را پيدا و فيلد اتصال آنرا طوري تنظيم کنيم که به گره اي اشاره کند که در حال حاضر اتصال گره mat به ان اشاره دارد( شکل زير )bat.cat.sat.vat NULLptrmat.

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

اسلاید 98: چاپ يک ليستVoid print_ list (list_pointer ptr){print f ( The list contains: );for ( ; ptr ; ptr = ptr -> link)print f ( %4d ، ptr ->data);print f ( n );}

اسلاید 99: صف و پشته پيونديtop.NULL.…linkelementfront.NULL.…linkelementrearپشته پيونديصف پيوندي

اسلاید 100: تابع add و deleteتوابع add و delete عناصري را به پشته اضافه و از آن حذف مي کنند. کد کردن هر يک از اين توابع ، کار ساده اي مي باشد. در هر دو تابع آدرس top را به گونه اي تغيير مي دهيم که به عنصر بالايي پشته اشاره کند.تابع add يک گره جديد به نام temp ايجاد نموده ، item را در فيلد داده و top را در فيلد اتصال قرار مي دهد سپس متغير top براي اشاره کردن به temp تغيير مي کند تابعadd

اسلاید 101: تابع deleteتابع delete ، عنصر را برگشت و top را عوض مي کند تا به آدرسي که در فيلد اتصال آن قرار دارد ، اشاره کند سپس گره حذف شده به حافظه سيستم برگشت داده مي شود.تابع delete

اسلاید 102: تابع اضافه کردن به يک پشته پيونديVoid add (stack_pointer * top ، element item){/* add an element to the top of the stack */stack _pointer temp = (stack_pointer ) malloc (sizeof (stack));if (IS_FULL(temp )) { fprint f (stderr ، The memory is full n); exit(1);}temp - > item = item ;temp - > link = * top ;* top = temp ;}

اسلاید 103: حذف از يک پشته پيونديelement delete (stack_pointer * top ){/* delete an element from the stack */stack_pointer temp = * top ;element item ;if (IS_EMPTY (temp)) {fprintf ( stderr ، The stack is empty n);exit(1);}item = temp - >item ;* top = temp - > link ;Free (temp) ;return item ;}

اسلاید 104: اضافه کردن گره اي به انتهاي يک صف پيونديVoid addq (queue_pointer * front ، queue_pointer *rear ، element item){/* add an element to the rear of the queue */queue _pointer temp =(queue_pointer ) malloc (sizeof (queue ));if (IS_full (temp)) {fprint f (stderr ، The memory is full n);exit(1);}temp - > item = item ;temp - > link = NULL ;if (* front ) (* rear ) - > link = temp ;else * front = temp ;* rear = temp ;}

اسلاید 105: حذف از ابتداي يک صف پيونديelement deleteq (queue_pointer * front ){/* delete an element from the queue */queue_pointer temp = * front ;element item ;if (IS_EMPTY (* front )) {fprintf ( stderr ، The queue is empty n);exit(1);}item = temp - >item ;* front = temp - > link ;free (temp) ;return item ;}

اسلاید 106: نمايش چند جمله اي ها به صورت ليست هاي تک پيونديدر اينجا مي توان هر جمله را به صورت يک گره نمايش داد. در اين ارتباط هر گره داراي سه فيلد براي نمايش ضريب ، توان و اشاره گري به گره بعدي مي باشد.مثال314.28.10NULLa

اسلاید 107: جمع چند جمله ايبراي جمع دو چند جمله اي ، ابتدا فرض مي کنيم که a و b اشاره گري به ابتداي چند جمله اي ها مي باشند. اگر توان دو چند جمله اي با هم برابر باشد ، ضرايب با هم جمع مي شوند و گره جديدي تشکيل مي شود ، همچنين اشاره گرها را به گره هاي بعدي در a و b حرکت مي دهيم. اگر توان چند جمله اي a کمتر از توان متناظر در چند جمله اي b باشد، آنگاه يک جمله شبيه به اين جمله ايجاد و آنرا به نتيجه ، يعني d ، اضافه مي کنيم و اشاره گر را به جمله بعدي در b منتقل مي کنيم. همين عمل را اگر a-> expon >b- > expon باشد بر روي a انجام مي دهيم .

اسلاید 108: تحليل جمع چند جمله اي هابراي محاسبه زمان لازم اجراي جمع چند جمله اي ، اولين نکته تعيين عملياتي است که بر زمان اجرايي اثر مي گذارد.براي اين الگوريتم بايد سه معيار در نظر گرفته شود : جمع ضرايب مقايسه توان ها ايجاد گره جديد براي d الگوريتم جمع چند جمله اي با فاکتور ثابت بهينه است.

اسلاید 109: رابطه هم ارزيرابطه ≡ روي هر مجموعه S ، رابطه هم ارزي گفته مي شود اگر داراي خواص انعکاسي ، تقارن و تعدي روي S باشد.مثال تساوي (=) ، يک رابطه هم ارزي است زيرا :x = x (1) است .x = y (2) تصريح مي کند که y = x مي باشد x = u (3) و y = z نتيجه مي دهد که x = z است .

اسلاید 110: الگوريتم تعيين کلاس هاي هم ارزيالگوريتم تعيين کلاس هاي هم ارزي ، دو مرحله است :در مرحله اول ، زوج هاي هم ارزي <i ،j> ، را خوانده و ذخيره مي کند.در مرحله دوم از 0 شروع کرده و تمام زوج هاي که به شکل < 0 ، J > مي باشد ( به نحوي که 0 و j در يک کلاس هم ارزي مي باشند ) را پيدا مي کند.

اسلاید 111: الگوريتم هم ارزيبر اساس خاصيت تعدي همه مقادير به شکل < j ، k > با k در يک کلاس قرار مي گيرند.فضاي لازم براي اين الگوريتم 0(m + n ) است

اسلاید 112: نمايش ماتريس هاي اسپارس به وسيله ليست پيونديدر نمايش داده ها ، هر سطر و ستون ماتريس اسپارس با يک ليست پيوندي حلقوي با گره head ارايه مي شود.هر گره داراي يک فيلد برچسب (tag) خواهد بود که وجه تمايز بين گره هاي head و گره هايي که عناصر مخالف صفر را ذخيره مي کنند ، مي باشد. هر گره head داراي سه فيلد ديگر نيز مي باشد :down ، right، next هر گره وارده داراي پنج فيلد ديگرمي باشد : value ، right ، down ، col، row

اسلاید 113: نمايش ماتريس هاي اسپارس به وسيله ليست پيوندي از فيلد down براي اشاره به عنصر مخالف صفر بعدي در همان ستون از فيلد right براي اشاره به عنصر مخالف صفر بعدي در همان سطر استفاده مي شود.هر گره head در سه ليست قرار مي گيرد : ليست سطرها ليست ستون ها ليست گره هاي head

اسلاید 114: اگر بخواهيم يک ماتريس اسپارس num_rows.num_cols با num_terms عنصر مخالف صفر را نمايش دهيم ، تعداد گره ها max { num_rows ،num_cols } + num_terms+1 خواهد بود.نمايش ماتريس هاي اسپارس به وسيله ليست پيوندي

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

اسلاید 116: ليست هاي پيوندي دوگانهيک گره در يک ليست پيوندي دوگانه حداقل داراي سه فيلد مي باشد : فيلد data فيلد llink (اشاره گر به چپ ) فيلد rlink ( اشاره گر به راست )

اسلاید 117: ليست هاي پيوندي دوگانهيک ليست پيوندي دوگانه به دو صورت است : حلقوي غير حلقويHead Nodel link item r link ليست پيوندي دوگانه حلقوي با گره headدرج و حذف از يک ليست پيوندي دوگانه بسيار ساده مي باشد.

اسلاید 118: درج دريک ليست پيوندي دوگانه حلقويVoid dinsert ( node_pointer node ، node_pointer newnode ){/* insert newnode to the right of node */newnode-> llink = node ;newnode-> llink = node-> r link ;node -> r link -> l link = newnode;node -> r link = newnode ;}

اسلاید 119: حذف از يک ليست پيوندي دوگانه حلقويVoid delete ( node_pointer node ، node_pointer deleted ){/* delete from the doubly linked list */ if (node = = deleted ) print f ( Deletion of head node not permitted . n )else {deleted -> l link - > r link = deleted - > r link ;deleted -> r link - > l link = deleted - > l link ;free ( deleted) ; }}

اسلاید 120: فصل پنجم : درختآشنايي با درختدرخت هاي دودوييپيمايش درختانهرمجنگلاهداف

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

اسلاید 122: مفهوم درختدرخت مجموعه محدودي از يک يا چند گره به صورت زير مي باشد : داراي گره خاصي به نام ريشه باشد. بقيه گره ها به n ≥ 0 مجموعه مجزا تقسيم شده که هر يک از اين مجموعه ها خود يک درخت هستند. زير درختان ريشه ناميده مي شوند.

اسلاید 123: مثالي از يک درختA والد B ، C، D است . B ، C، D همزادند.ACGDBEHIJMFريشه درختLKهمزاددرجه A = 3شکل1-5

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

اسلاید 125: اصطلاحات درخت هاگره هاي همزاد :فرزندان يک گره ، گره هاي همزاد يا هم نيا ناميده مي شوند.اجداد گره : اجداد يک گره ، گره هايي هستند که در مسير طي شده از ريشه تا آن گره وجود دارند.سطح گره : سطح يک گره بدين صورت تعريف مي شود که ريشه در سطح يک قرار مي گيرد. براي تمامي گره هاي بعدي ، سطح گره برابر است با سطح والد به اضافه يک .ارتفاع درخت : ارتفاع يا عمق يک درخت به بيشترين سطح گره هاي آن درخت گفته مي شود.

اسلاید 126: نمايش ليستيک راه نمايش درخت ، استفاده از ليست است .شکل 1-5 را مي توان به صورت زير نشان داد : (A(B(E(K ،L)،F)،C(G)،D(H(M)،I،J)))

اسلاید 127: نمايش ليست ممکن براي درختانشکل زير يک ساختار ممکن براي نمايش ليست را نشان مي دهد :

اسلاید 128: نمايش دودويي يک درختبراي نمايش درختان دودويي ، دقيقا نياز به دو اتصال يا اشاره گر به ازاي هر گره است.

اسلاید 129: 2-5 درخت هاي دودويي مشخصه اصلي يک درخت دودويي بدين شکل است که هر گره آن حداکثر دو انشعاب دارد يعني گره هايي که درجه اي بيشتر از دو نداشته باشند. براي درخت هاي دودويي زير درخت سمت چپ و راست با يکديگر متمايز است.يک درخت دودويي يا تهي است يا حاوي مجموعه اي محدود از گره ها شامل يک ريشه و دو زير درخت دودويي است. اين درخت ها زير درخت هاي چپ و راست ناميده مي شوند.تعريف :

اسلاید 130: 2-5 ساختار درخت دودوييstructure Binary_tree (abbreviated BinTree ) is objects : a finite set of nodes either empty or consisting of a root node ، left Binary_tree ، and right Binary_tree. functions :for all bt ، bt1 ، bt2 BinTree ، item elementBinTree Create()Boolean IsEmpty (bt)BinTree MakeBT(bt1 ، item ، bt 2)BinTree Lchild(bt)element Data(bt)BinTree Rchild(bt)

اسلاید 131: 2-5 تفاوت درخت عادي با درخت دودوييدر هيچ درخت عادي صفر گره وجود ندارد ، اما درخت دودويي تهي وجود دارد.در يک درخت دودويي ترتيب فرزندان داراي اهميت بوده در حالي که در درخت عادي به اين صورت نيست.

اسلاید 132: 2-5 خواص درختان دودويي حداکثر تعداد گره ها در سطح i ام يک درخت دودويي است ، i ≥ 1 . حداکثر تعداد گره ها در يک درخت دودويي به عمق k ، است ، k ≥ 1حداکثر تعداد گره ها

اسلاید 133: 2-5 خواص درختان دودوييبراي هر درخت دودويي غير تهي مانند T ، اگر تعداد گره هاي پاياني و تعداد گره هاي درجه 2 باشد ، آنگاه خواهيم داشت :رابطه بين تعداد گره هاي برگ و گره هاي درجه 2

اسلاید 134: 2-5 خواص درختان دودويييک درخت دودويي پر به عمق k ، يک درخت دودويي است که داراي گره باشد k ≥ 0 .يک درخت دودويي با n گره و عمق k کامل است ، اگر و تنها اگر گره هايش مطابق با گره هاي شماره گذاري شده در يک درخت دودويي پر به عمق k باشد.

اسلاید 135: 2-5 نمايش درخت دودويينمايش درخت دودويي به دو صورت است :نمايش آرايهنمايش ليست

اسلاید 136: 2-5 نمايش آرايهشيوه شماره گذاري ارايه شده در شکل زير ، اولين نمايش يک درخت دودويي در حافظه را مطرح و پيشنهاد مي کند . از آنجايي که گره ها از 1 تا n شماره گذاري شده اند ، يک آرايه يک بعدي مي تواند براي ذخيره سازي گره ها استفاده شود .

اسلاید 137: 2-5 نمايش آرايهACBDFGEIHAB-C---D-...E[1][2][3][4][5][6][7][8][9]...[16]نمايش آرايه اي درخت دودويي

اسلاید 138: 2-5 نمايش آرايه اگر يک درخت دودويي کامل با n گره ( يعني عمق ) به ترتيب بالا تعريف شده باشد ، آنگاه براي هر گره با انديس i و ≤ n i 1≤ ، داريم : اگر i≠1 ، آنگاه پدر i در [i/2] است . اگر i=1 ، i ريشه است و پدري نخواهد داشت.(2) اگر2i≤n ، آنگاه فرزند چپ i در 2i است. اگر 2i>n ، آنگاه i فرزند چپ ندارد.(3) اگر 2i+1≤n ، آنگاه فرزند راست i در 2i+1 است. اگر 2i+1>n ، آنگاه i فرزند راست ندارد

اسلاید 139: 2-5 نمايش آرايهدر بدترين حالت ، يک درخت مورب به عمق k ، بهمحل و موقعيت نياز دارد که از اين مقدار، فقط k محل اشغال مي شود.

اسلاید 140: 2- 5 نمايش ليست پيوندي ماداميکه نمايش ترتيبي (آرايه اي) براي درختان دودويي کامل مناسب به نظر مي رسد ، ما براي بسياري از درختان ديگر باعث اتلاف حافظه مي شود به علاوه ، اين روش از نارسايي هاي موجود در نمايش ترتيبي نيز برخوردار است. درج يا حذف گره هاي يک درخت ، مستلزم جابه جايي گره هاست که خود باعث تغيير شماره سطح گره ها مي شود. اين مسايل مي تواند با به کارگيري نمايش پيوندي به آساني حل شود.

اسلاید 141: 2-5 نمايش ليست پيونديبا اين روش هر گره سه فيلد خواهد داشت :left_child ، data ، right_child که در زبان C به شرح زير تعريف مي شوند :typedef struct node *tree_pointer ;typedef struct node {int data ;tree_pointer left_child ، right_child ;};

اسلاید 142: 2-5 نمايش ليست پيونديleft_childdataright_childنمايش يک گره درخت دودويي

اسلاید 143: 3-5 پيمايش درخت دودوييبه هنگام پيمايش يک درخت دودويي ، با هر گره و زيردرختانش به طرز مشابهي رفتار کنيم. اگر R ، V ، L به ترتيب حرکت به چپ ، ملاقات کردن يک گره ( براي مثال ، چاپ فيلد داده آن گره) و حرکت به راست باشد، آنگاه شش ترکيب ممکن براي پيمايش يک درخت خواهيم داشت : RLV ، RVL ، VRL ، VLR ، LRV ، LVR

اسلاید 144: 3-5 پيمايش درخت دودويياگر تنها حالتي را انتخاب کنيم که ابتدا به سمت چپ و بعد به سمت راست برود ، تنها سه ترکيب VLR ، LRV ، LVR خواهيم داشت. اين سه حالت را با توجه به موقعيت V نسبت به L و R به ترتيب preordcr ، postorder ، inorder مي ناميم.مثال

اسلاید 145: 3-5 پيمايش درخت دودويي در پيمايش postorder ، يک گره موقعي ملاقات و چاپ مي شود که زيردرختان چپ و راست آن قبلا ملاقات شده باشند. در پيمايش preorder ، يک گره قبل از پيمايش زيردرختان چپ و راست ، ملاقات مي گردد.

اسلاید 146: 3-5 پيمايش درخت دودوييدرخت زير حاوي يک عبارت رياضي است : A/B*C*D*+E+E**DC/AB12345679108111417191816151312درخت دودويي براي يک عبارت محاسباتي

اسلاید 147: 3-5 پيمايش Inorderهنگامي که اين پيمايش انتخاب مي شود ، حرکت به سمت پايين به طرف چپ انجام مي شود و اين عمل تا آخرين گره صورت مي گيرد سپس مي توان گره را بازيابي کرد و بعد به سمت راست رفته و به همين ترتيب کار را ادامه پيدا مي کند.اين متناظر با شکل infix يک عبارت است.

اسلاید 148: Vide inorder (tree_pointer ptr )/* inorder tree traversal */{if (ptr) {inorder ( ptr -> left_child );printf (“ % d” ، ptr -> data );inorder (ptr -> right_child);}}3-5 پيمايش Inorderيک درخت دودويي

اسلاید 149: 3-5 پيمايش Preorderتابع preorder حاوي دستورات لازم براي شکل دوم پيمايش است.بر اساس اين پيمايش ، گره را ابتدا بازيابي و ملاقات نموده و سپس انشعابات چپ را دنبال و تمام گره ها را بازيابي مي کنيم. اين فرآيند ادامه پيدا مي کند تا به يک گره تهي برسيم. در اين نقطه ، به نزديکترين جدي که داراي يک فرزند راست باشد مراجعه و با اين گره شروع خواهيم نمود.

اسلاید 150: 3-5 پيمايش Preorder+E**DC/AB12345679108111417191816151312با پيمايش preorder گره هاي درخت زير خروجي به شکل زير خواهند داشت :خروجي+ * * / A B C D Eاين به شکل يک عبارت prefix است.

اسلاید 151: 3-5 پيمايش Preorder يک درخت دودوييVide preorder (tree_pointer ptr )/* preorder tree traversal */{if (ptr) {printf (“ % d” ، ptr -> data );preorder ( ptr -> left_child );preorder (ptr -> right_child);}}

اسلاید 152: 3-5 پيمايش postorderاين پيمايش دو فرزند يک گره را قبل از بازيابي آن گره ملاقات و چاپ مي کند. اين مساله بدين مفهوم است که فرزندان يک گره قبل از خود آن گره بازيابي مي گردد.

اسلاید 153: 3-5 پيمايش postorderخروجي حاصل از پيمايش postorder شکل زير به صورت زير است :+E**DC/AB12345679108111417191816151312خروجيA B/ C* D* E +اين خروجي مانند يک عبارت postfix است.

اسلاید 154: 3-5 پيمايش inorder غيربازگشتيVoid iter_pointer (tree_pointer node ){int top = -1 ; /* initialize stack */tree_pointer stack [MAX_STACK_SIZE] ;for ( ; ; ) {for (; node ; node = ->left_child)add ( &top ، node ); /* add to stack */node = delete (&top); /*delete from stack */if (! Node) break ; /* empty stack*/printf (“ % d”، node-> data ) ;node = node -> right_child;}}

اسلاید 155: 3-5 پيمايش inorder غيربازگشتيتحليل inorder2 : فرض کنيد تعداد گره هاي درخت n باشد ، اگر عمل iter_inorder را در نظر بگيريم ، مشاهده مي شود که هر گره درخت فقط يک بار در پشته قرار گرفته و يا از آن خارج مي شود. بنابراين اگر تعداد گره هاي درخت n باشد ، پيچيدگي زمان تابع برابر با O(n) مي باشد. حافظه مورد نياز برابر با عمق درخت است که مساوي با O(n) مي باشد.

اسلاید 156: 3-5 پيمايش ترتيب سطحيپيمايش هاي inorder ، preorder ، postorder چه به صورت بازگشت پذيري نوشته يا به صورت غيربازگشتي ، همگي نيازمند پشته مي باشند.اين پيمايش ، ترتيب سطحي ، ابتدا ريشه را بازيابي ، سپس فرزند چپ ريشه و به دنبال آن فرزند راست ريشه بازيابي مي گردد. اين شيوه با بازيابي از گره منتهي اليه سمت چپ به سمت راست هر سطح جديد تکرار مي گردد. اين پيمايش از صف استفاده مي کند.

اسلاید 157: 3-5 پيمايش ترتيب سطحيپيمايش ترتيب سطحي درخت زير به صورت زير است : +E**DC/AB12345679108111417191816151312+ *E *D / C A B

اسلاید 158: 4-5 اعمال مفيد بر روي درختان دودويي1- کپي کردن درختان دودويي2- تعيين برابري و تساوي دو درخت3- مساله Satisfiability

اسلاید 159: 5-5 درختان نخي دودوييتعداد اتصالات تهي در يک درخت دودويي بيشتر از تعداد اشاره گرهاي غيرتهي است.در يک درخت دودويي تعداد n + 1 اتصال از کل اتصالات آن يعني ، 2n تهي است. يک راه براي به کارگيري اين اتصالات توسط پرلين و تورنتن پيشنهاد شد. راه حل اين بود که از اتصالات تهي براي ارتباط با ديگر گره هاي يک درخت استفاده شود که در اين صورت درخت را درخت نخي مي نامند.

اسلاید 160: 5-5 درختان نخي دودوييبراي ايجاد اتصالات نخي از قوانين زير استفاده مي شود : اگر ptr-> left_child تهي باشد ، آن را طوري تغيير مي دهيم که به گره اي که در پيمايش inorder قبل از ptr قرار دارد ، اشاره کند. اگر ptr-> right_child تهي باشد ، آن را طوري تغيير مي دهيم که به گره اي که در پيمايش inorder بعد از ptr قرار دارد ، اشاره کند.

اسلاید 161: 5-5 درختان نخي دودوييهنگامي که درختي را در حافظه نمايش مي دهيم ، بايستي بتوانيم بين اتصالات نخي و واقعي تفاوتي قايل شويم. اين کار را با افزودن دو فيلد اضافي به هر گره انجام مي دهيم که آنها را right_thread ، left_thread مي ناميم.

اسلاید 162: 5-5 درختان نخي دودوييACBDFGEIHدرخت نخي متناظرACBDFGEIHاتصالات نخي

اسلاید 163: 5-5 پيمايش inorder يک درخت نخي دودوييبراي هر گره مانند ptr ، در يک درخت دودويي ، چنانچه ptr->right_thread = TRUE باشد ، طبق تعريف گره بعدي ptr در پيمايش inorder ، ptr->right_child مي باشد . در غير اين صورت گره بعدي ptr، با پايين رفتن روي مسير فرزندان چپ ptr از طرف فرزند سمت راست ptr تا وقتي که به گره اي با وضعيت left_thread = TRUE برسيم ، تعيين مي شود .

اسلاید 164: تابع insucc بدون استفاده از پشته ، گره بعدي در پيمايش inorder را در يک درخت نخي دودويي پيدا مي کند.براي پيمايش inorder مي توانيم با فراخواني مکرر insucc تمام گره ها را بازيابي کنيم .5-5 پيمايش inorder يک درخت نخي دودويي

اسلاید 165: 5-5 پيمايش inorder يک درخت نخي دودوييthreaded_pointer insucc (threaded_pointer tree){/* find the inorder sucassor of tree in a threaded binary tree */threaded_pointer temp ;temp = tree -> right_child ;if (! Tree -> right_thread)while (! temp -> left_thread)temp = temp -> left_child ;return temp ;}تابع insucc :پيدا نمودن گره بعد ، يک گره خاص در پيمايش inorder

اسلاید 166: 5-5 پيمايش inorder يک درخت نخي دودوييVoid tinorder (threaded_pointer tree){/* traverse the threaded binary tree inorder */threaded_pointer temp = tree ;for ( ; ; ) {temp = insucc (temp) ;if (temp = tree ) break ;printf (“ % 3c” ، temp -> data ) ;}}

اسلاید 167: 5-5 درج يک گره به داخل درخت نخي دودوييفرض کنيد داراي گرهي به نام parent هستيم که داراي زيردرخت راست تهي مي باشد ، آنگاه مايل هستيم child را به عنوان فرزند راست parent درج کنيم . براي انجام اين کار بايد :parent->right_thread را برابر FLASH قرار دهيد. child-> left_thread و child-> right_thread را برابر TRUE قرار دهيد . child-> left_child را طوري تنظيم کنيد که بهparen اشاره کند. child-> right_child را برابر parent->right_child قرار دهيد.parent->right_child را طوري تنظيم کنيد که به childاشاره کند.

اسلاید 168: 5-5 درج يک گره به داخل درخت نخي دودوييمثالدر شکل زير گره D را به عنوان فرزند راست گره B جايگذاري مي کنيم :ABCrootparentDchildABCrootDparentchild

اسلاید 169: 6-5 نوع داده مجرد ( (ADTهرمmax tree درختي است که مقدار کليد هر گره آن کمتر از مقادير کليدهاي فرزندانش نباشد.max heap يک درخت دودويي کامل است که يک max tree نيز مي باشد.min tree درختي است که مقدار کليد هر گره آن بيشتر از مقادير کليدهاي فرزندانش نباشد.min heap يک درخت دودويي کامل است که در واقع يک min tree مي باشد.

اسلاید 170: 6-5 مثال از max heap و min heap14712108[1][2][4] [5][3]6[6]247108[1][2][4] [5][3]6[6]9365[1][2][4][3]10832050[1][2][4][3]مثال از max heapمثال از min heap

اسلاید 171: 6-5 اعمال اساسي بر روي heapايجاد يک هرم(heap) تهيجايگذاري عنصر جديد به هرم (heap) حذف بزرگترين عنصر از هرم (heap)

اسلاید 172: 6-5 صف اولويتغالبا هرم ها براي پياده سازي صف اولويت ها استفاده مي شوند. در صف اولويت ها عنصري که داراي بالاترين ( يا پايين ترين ) اولويت هست ، حذف مي شود. آرايه ساده ترين نمايش براي يک صف اولويت مي باشد.

اسلاید 173: 6-5 نمايش هاي صف اولويتDeletionInsertionRepresentationΘ(n)Θ(1)Unordered arrayΘ(nΘ(1)Unordered linked listΘ(1)O(n)Stored arrayΘ(1)O(n)Stored linked listMax heap

اسلاید 174: 6-5 درج عناصر به داخل يک Max Heap2021514[1][2][4][3]10[5]الف - درخت heap قبل از درجب - محل اوليه گره جديددرج عنصر جديداضافه کردن گره جديد در هر موقعيت ديگري ،تعريف heap را نقض مي کند زيرا نتيجه يک درخت دودويي کامل نخواهد بود.2021514[1][2][4][3]10[5]

اسلاید 175: Void insert_max_heap ( element item ، int *n ){/* insert item into a max heap of current size *n * /int i ;if (HEAP_FULL(*n) {fprint f (stderr ، “ The heap is full . n”) ;exit (1) ;}i = ++ ( *n ) ; while (( i ! = 1 ) && (item.key > heap [i/2] . Key )) {heap [i] = heap[i/2] ;i / = 2 ; }heap [i] = item ;}6-5 درج عنصر به يک Max heap

اسلاید 176: 6-5 تحليل تابع insert_max_heapاز آنجا که heap يک درخت کامل با n عنصر مي باشد ، داراي ارتفاع مي باشد. اين بدين معني مي باشد که حلقه while به ميزانتکرار شود. بنابراين پيچيدگي تابع درج برابرمي باشد.

اسلاید 177: 6-5 حذف عنصري از Max Heap2021514[1][2][4][3]10[5]هنگامي که عنصري از max heap حذف مي شود ، آن را از ريشه درخت heap مي گيريم.21514[1][2][4][3][5]20 removedحذف يک عنصر از max heap

اسلاید 178: 6-5 تحليل تابع delete_max_heapپيچيدگي حذف برابرمي باشد.زمان حذف يک عنصر دلخواه از درخت heap با n عنصر ، برابر O(n) مي باشد.

اسلاید 179: 7-5 درختان جستجوي دودويييک درخت جستجوي يک درخت دودويي است که ممکن است تهي باشد. اگر درخت تهي نباشد خصوصيات زير را برآورده مي کند : هر عنصر داراي يک کليد است و دو عنصر نبايد داراي کليد يکسان باشند ، در واقع کليدها منحصر به فردند. کليدهاي واقع در زيردرخت غيرتهي چپ بايد کمتر از مقدار کليد واقع در ريشه زيردرخت راست باشد. کليدهاي واقع در زيردرخت غيرتهي راست بايد بزرگتر از مقدار کليد واقع در ريشه زيردرخت چپ باشد.زيردرختان چپ و راست نيز خود درختان جستجوي دودويي ميباشند.

اسلاید 180: 7-5 درختان جستجوي دودويي304052مثال

اسلاید 181: 7-5 جستجوي يک درخت دودوييفرض کنيد خواسته باشيم دنبال عنصري با کليد key بگرديم. ابتدا از ريشه (root) شروع مي کنيم ، اگر ريشه تهي باشد ، درخت جستجو فاقد هر عنصري بوده و جستجو ناموفق خواهد بود. در غير اين صورت keyرا با با مقدار کليد ريشه مقايسه کرده : اگر key کمتر از مقدار کليد ريشه باشد ، هيچ عنصري در زيردرخت راست وجود ندارد که داراي کليدي برابر key باشد ، بنابراين زيردرخت چپ ريشه را جستجو مي کنيم. اگر key بزرگتر از مقدار کليد ريشه باشد ، زيردرخت راست را جستجو مي کنيم.

اسلاید 182: 7-5 تحليل searchاگر h ارتفاع يا عمق يک درخت جستجوي دودويي باشد ، عمل جستجو را در مدت O(h) انجام مي شود.

اسلاید 183: 7-5 درج عنصري به داخل درخت جستجوي دودوييبراي درج عنصر جديدي به نام key ، ابتدا بايد مشخص نمود که آيا کليد با عناصر موجود متفاوت است يا خير. براي انجام اين کار بايد درخت را جستجو کرد، اگرجستجو ناموفق باشد ، عنصر را در محلي که جستجو خاتمه پيدا نموده است ، درج مي کنيم.

اسلاید 184: 7-5 درج عنصري به داخل درخت جتجوي دودويي304052304052803040523580جايگذاري 80جايگذاري 35مثال

اسلاید 185: 7-5 تحليل insert_nodeزمان لازم براي جستجوي num در يک درخت برابر O(h) مي باشد به نحوي که h برابر با عمق يا ارتفاع درخت است. بقيه الگوريتم نياز به زمان Θ(1) دارد. بنابراين زمان کل مورد نياز insert_node برابر با Θ(h) مي باشد.

اسلاید 186: 7-5 حذف عنصري از درخت جستجوي دودوييبراي حذف 35 از درخت زير بايد فيلد فرزند چپ والد اين گروه را برابر NULL قرار داده و گره را آزاد نمود :3040523580

اسلاید 187: زماني که يک گره برگ با دو فرزند حذف مي شوند ، گره را با بزرگترين عنصر در زير درخت چپ و يا کوچکترين عنصر در زيردرخت راست آن گره جايگزين و تعويض کرد.عمل حذف در زمان O(h) انجام مي گيرد ، به نحوي که h عمق درخت مي باشد.7-5 حذف عنصري از درخت جستجوي دودويي

اسلاید 188: 7-5 درختان جستجوي متعادلدرختان جستجو با بيشترين عمق، درختان جستجوي متعادل ناميده مي شوند.درختان جستجوي متعادلي وجود دارند که عمل جستجو ، درج و حذف را در زمان O(h) ممکن مي سازند از جمله درختان red_black ، 2-3 ، AVL

اسلاید 189: 8-5 درختان انتخابيفرض کنيد داراي k مجموعه و رشته مرتب شده اي از عناصر هستيم که بايد در يک رشته واحد ادغام شوند. هر دنباله يا ترتيب شامل تعدادي رکورد به ترتيب غيرنزولي و فيلد مشخصي به نام key مي باشد. يک دنباله مرتب اجرا (run) ناميده مي شود. فرض کنيد که n، تعداد رکوردها در k اجرا باشد، عمل ادغام مي تواند با تکرار رکورد با کوچکترين کليد انجام شود.

اسلاید 190: 8-5 درختان انتخابي کوچکترين کليد بايد ازبين k امکان موجود پيدا شود و مي تواند رکوردي قبل از هر k اجرا (k-runs) باشد. بهترين روش براي ادغام k اجرا (k-runs) ، نيازمند k-1 مقايسه براي تعيين و انتقال رکورد بعدي به خروجي مي باشد. به ازاي k>2 ، مي توانيم با استفاده از ايده درخت انتخابي ، تعداد مقايسه هاي لازم جهت تعيين کوچکترين عنصر را کاهش دهيم.

اسلاید 191: 8-5 درختان انتخابييک درخت انتخابي ، يک درخت دودويي است که هر گره آن کوچکتر از دو فرزند خود مي باشد بنابراين ، گره ريشه نشان دهنده کوچکترين گره در درخت مي باشد.

اسلاید 192: 68698176910620981790[1][2][4][3][5][12][11][10][9][8][6][14][13][15][7]8-5 درختان انتخابيمثال203820301525155011161001101820run1run 2run 3run 4run 5run 8run 7run 6

اسلاید 193: زمان تجديد ساختار درخت برابر مي باشد.زمان لازم براي ادغام تمام n رکورد برابر مي باشد.زمان کل لازم جهت ادغام k اجرا (run) برابر مي باشد.8-5 درختان انتخابي

اسلاید 194: 9-5 جنگل هاجنگل مجموعه n ≥ 0 درخت مجزا مي باشد.اگر ريشه درخت را حذف کنيم ، آنگاه داراي يک جنگل خواهيم بود.

اسلاید 195: 9-5 تبديل جنگل به يک درخت دودوييبراي تبديل اين جنگل به يک درخت دودويي واحد :ابتدا نمايش دودويي هر يک از درختان جنگل را به دست مي آوريمسپس تمام درختان دودويي را از طريق فيلد همزاد گره ريشه به يکديگر متصل مي کنيم.

اسلاید 196: 9-5 تبديل جنگل به يک درخت دودوييADBCEFGIHAEBFGIHCDتبديل به درخت دودويي

اسلاید 197: اگرجنگلي از درختان باشد ، آنگاه درخت دودويي متناظر با اين جنگل يعني B:اگر n=0 باشد ، تهي خواهد بود. داراي ريشه اي برابر با ريشه مي باشد ، داراي زيردرخت چپي برابر با مي باشد ، به نحوي که زيردرختان ريشه مي باشند و در نهايت داراي زيردرخت راستمي باشد. 9-5 تبديل جنگل به يک درخت دودويي

اسلاید 198: 9-5 پيمايش جنگلپيمايش هاي postorder ، inorder ، preorder متناظر درخت دودويي T يک جنگل F داراي يک تناظر طبيعي با پيمايش هاي F مي باشند.

اسلاید 199: پيمايش preorder مربوط به T معادل با بازيابي گره هاي F در درخت preorder مي باشد:اگر F تهي باشد ، برگرديد. ريشه درخت اول F را بازيابي کنيد. زيردرخت ، درخت اول را به صورت preorder پيمايش کنيد. ساير درختان F را به صورت preorder پيمايش کنيد.9-5 پيمايش جنگل

اسلاید 200: 9-5 پيمايش جنگلپيمايش inorder مربوط به T معادل گره هاي F در درخت inorder است که به صورت زير تعريف مي شود : اگر F تهي باشد ، برگرديد. ريشه درخت ، درخت اول را به صورت inorder پيمايش کنيد. ريشه درخت اول را بازيابي کنيد. ساير درختان را به صورت inorder پيمايش کنيد.

اسلاید 201: 9-5 پيمايش جنگلهيچ گونه معادل طبيعي براي براي پيمايش postorder درخت دودويي متناظر يک جنگل وجود ندارد . پيمايش postorder يک جنگل F را به صورت زير بيان ي کنيم :1) اگر F تهي باشد ، برگرديد.2) زيردرخت ، اولين درخت F را به صورت postorder پيمايش کنيد.3) ساير درختان باقي ماندهF را به صورت postorder پيمايش کنيد. 4) ريشه اولين درختF را بازيابي کنيد

اسلاید 202: 10-5 نمايش مجموعهده عضو از 0 تا 9 که به سه مجموعه مجزا از هم تفکيک شده باشند ، مي توانند بدين صورت باشند :0867491253مثال

اسلاید 203: 10-5 نمايش مجموعهدر هر مجموعه بر خلاف معمول که اشاره گرها به از والد به فرزندان در نظر گرفته مي شدند، در اينجا اشاره گرها از فرزندان به والد تنظيم مي شوند و يا در حقيقت گره ها با رابطه پدري اتصال يافته اند.

اسلاید 204: 10-5 اعمال روي مجموعه هاحداقل اعمالي که بر روي مجموعه انجام مي شود ، به شرح زير است :اجتماع مجموعه مجزا (union) : اگر دو مجموعه مجزا باشند ، انگاه اجتماع آنها به صورت زير تعريف مي شود :{ همه اعضا به صورت x که x يا عضوباشد يا عضو }2) find(i)( پيداکردن i ) : مجموعه اي که i عضو آن است را پيدا کنيد

اسلاید 205: 10-5 اعمال روي مجموعه هامثال0867491

اسلاید 206: 10-5 قانون Weighting برايUnion(i ، j ) قانون Weighting برايUnion(i ، j ) : اگر تعدا گره ها در درخت i کمتر از تعداد گره ها در درخت j باشد ، j را والد i ، در غير اين صورت i را والد j قرار مي دهيم.تعريف

اسلاید 207: 10-5 پياده سازي قانون Weighting براي پياده سازي قانون Weighting بايد بدانيم که در هر درخت چند گره وجود دارد. اين کار را بدين ترتيب انجام مي دهيم که در ريشه هر درخت يک فيلد count قرار مي دهيم. اگر i يک گره ريشه باشد ، آنگاه در count[i] تعداد گره هاي آن درخت خواهد بود. Count به صورت يک عدد منفي در فيلد parent گذاشته مي شود. زماني که قانون Weightingرا بيان مي کنيم ، عمل اجتماع به اين صورت را union2 مي ناميم.

اسلاید 208: 10-5 مجموعه هااصل موضوعي : فرض کنيد T يک درخت با n گره باشد که توسط union2 ايجاد شده باشد ، در اين صورت هيچ گرهي در T ، سطحي بيشتر از نخواهد داشت. اگر در يک درخت n عضو وجو.د داشته باشد ، بيشترين زمان براي يافتن يک عضو به صورت خواهد بود.اگر ترکيبي از n-1 عمل union و m عملfind داشته باشيم ، در بدترين حالت ممکن ، زمان به صورت درمي آيد. تعريف ( قانون تخريب ) : اگر j گرهي روي مسير از i تا ريشه خود باشد ، آنگاه j را فرزند ريشه قرار دهيد.

اسلاید 209: 11-5 شمارش درختان دودوييتعداد درختان دودويي مجزا :تعداد درختان دودويي با n گره ، تعداد جايگشت هاي از 1 تا n با استفاده از يک پشته و بالاخره تعداد راههاي ضرب n+1 ماتريس ، باهم مساوي اند.

اسلاید 210: 11-5 تعداد درختان دودويي مجزابراي به دست آوردن تعداد درختان مجزا با n گره از تابع زير استفاده مي کنيم :تابع فوق توليدکننده تعداد درختان دودويي است.کهبرابر است با : در نتيجه داريم :

اسلاید 211: فصل ششم: گراف هاآشنايي با گرافماتريس مجاورتيجستجوي گرافشبکه هااهداف

اسلاید 212: فصل ششم : گراف هاهر گراف G شامل دو مجموعه V وE است :V : مجموعه محدود و غيرتهي از رئوس استE : مجموعه اي محدود و احتمالا تهي از لبه ها مي باشد.V(G) و E(G) : مجموعه رئوس و لبه هاي گراف G را نمايش مي دهند.براي نمايش گراف هم مي توانيم بنويسيم G=(V ، E)

اسلاید 213: 1-6 گراف هادر يک گراف بدون جهت، زوج رئوس ، زوج مرتب نيستند ، بنابراين زوج هايبا هم يکسانند. در يک گراف جهت دار هر لبه با زوج مرتبنمايش داده مي شود. انتها و ابتداي لبه هستند. بنابراين ودو لبه متفاوت را نمايش مي دهند.

اسلاید 214: براي گراف بدون جهت ، لبه ها به صورت خطوط يا منحني نمايش داده مي شوند. براي گراف هاي جهت دار لبه ها به صورت فلش هايي که از انتها به ابتدا رسم شده است ، ارايه مي گردند.1-6 گراف ها0213021F643012بدون جهتجهت دارمثال

اسلاید 215: 1-6 محدوديت هاي گراف هامحدوديت هاي زير بر روي گراف ها اعمال مي شود : يک گراف فاقد لبه اي از يک راس مانندi ، به خودش مي باشد. اين مطلب بدين معني است که لبهغير معتبر مي باشد. يک گراف فاقد رويداد چندگانه از يک لبه مي باشد.گراف کامل : گراف کامل گرافي است که داراي حداکثر تعداد لبه باشد.

اسلاید 216: 1-6 گراف هابراي يک گراف بدون جهت با n راس ، حداکثر تعداد لبه ها ، تعداد متمايز و غيرمرتب زوج هاي، i ≠ j مي باشد. ايت تعداد برابر است با : n(n-1 ) / 2اگرگراف جهت داري با n گره وجود داشته باشد، بيشترين تعداد لبه هاي آن برابر است با :n(n-1)

اسلاید 217: 1-6 گراف هااگر يک لبه در گراف بدون جهت باشد ، مي گوييم رئوس ودو راس مجاور و لبهيک لبه متلاقي روي و است . يک زير گراف G، گرافي است مانند به نحوي که و باشد.

اسلاید 218: طول يک مسير تعداد لبه هاي موجود در آن است. مسير ساده ، مسيري است که همه رئوس آن احتمالا به جز اولي و آخري مجزا باشند. حلقه يا سيکل ، يک مسيرساده است که اولين و آخرين راس آن يکي باشد. 02131-6 گراف هابراي مثال 0،1،2،0 يک حلقه در است.

اسلاید 219: 1-6 گراف هادر گراف بدون جهت مانند G ، دو راس و را متصل مي گويند، اگر مسيري در G از به وجود داشته باشد. يک گراف بدون جهت را متصل مي ناميم اگر براي هر زوج راس در V(G) ،مسيري از به در G وجود داشته باشد. يک مولفه اتصال يا به طور ساده تر يک مولفه ، در گراف بدون جهت ، بزرگترين زيرگراف متصل آن است.

اسلاید 220: يک گراف جهت دار کاملا متصل ناميده مي شود ، اگر براي هر زوج از رئوس در V(G) ، مسيري جهت دار از به و همچنين از به وجود داشته باشد.1-6 گراف هايک مولفه کاملا متصل ، بزرگترين زيرگرافي است که کاملا متصل باشد.012مولفه کاملا متصل012مثال

اسلاید 221: 1-6 گراف ها درجه يک راس تعداد لبه هاي متلاقي با آن راس است .اگر در گراف G با n راس ، درجه راس i و e تعداد لبه ها باشد ، به آساني مي توان ديد که تعداد لبه ها برابر است با :

اسلاید 222: 1-6 نمايش گرافنمايش گراف ها به سه صورت است :ماتريس مجاورتي ليست هاي مجاورتيليست هاي چندگانه

اسلاید 223: 1-6 ماتريس مجاورتيفرض کنيد G=(V ، E) يک گراف با n راس باشد ، n ≥ 1، ماتريس مجاورتي گراف G يک آرايه دوبعدي n × n به نام adj_mat مي باشد. اگر لبه(براي گراف جهت دار) در E(G) باشد ، آنگاه adj_mat[i] [j]= 0 خواهد بود. ماتريس مجاورتي براي يک گراف بدون جهت متقارن است زيرا لبه در E(G) خواهد بود ، اگر و تنها اگر لبه نيز در E(G) باشد

اسلاید 224: 6-1 ماتريس مجاورتي (مثال )0213ماتريس مجاورتي01230 1 2 30 1 1 11 0 1 11 1 0 11 1 1 0

اسلاید 225: 1-6 ماتريس مجاورتيبراي گراف بدون جهت ، درجه هر راس مانند i مجموع عناصر سطري آن است :براي يک گراف جهت دار ، مجموع سطري ، درجه خارجه و مجموع ستوني ، درجه وارده خواهد بود.

اسلاید 226: 6-1 ليست هاي مجاورتي با اين نمايش ، n سطر ماتريس مجاورتي در n ليست پيوندي قرار مي گيرد. براي هرراس از گراف G ، يک ليست وجود دارد.هر گره حداقل دو فيلد دارد : راس و اتصالدر هر ليست مشخصي مانند i ، گره هاي ليست حاوي رئوس مجاور از راس i مي باشند.در يک گراف بدون جهت با n راس و e لبه ، n گره head و 2e گره ليست دارد. هر گره ليست دو فيلد لازم دارد.

اسلاید 227: 6-1 ليست هاي مجاورتي(مثال) 0213....1.0.0.0.2.2.1.1.3NULL3NULL3NULL2NULL0123head nodesvertexlink

اسلاید 228: درجه هر راس در يک گراف بدون جهت را مي توان به سادگي با شمارش تعداد گره هاي آن در ليست مجاورتي تعيين کرد.اگر تعداد رئوس گراف G برابر با n باشد ، تعداد کل لبه ها، در زمان O( n + e ) تعيين مي شود.6-1 ليست هاي مجاورتي

اسلاید 229: 6-1 ساختار گره براي ليست هاي مجاورتينمايش دوم : هر گره داراي چهار فيلد بوده و نشان دهنده يک لبه است.

اسلاید 230: 1-6 ليست هاي مجاورتي چندگانه در نمايش ليست مجاورتي ، هر لبه در يک گراف بدون جهت مانند با دو وارده نمايش داده مي شود : در ليست براي در ليست براي

اسلاید 231: 1-6 لبه هاي وزني در ماتريس مجاورتي ، کميت 1 که نشان دهنده وجود يک لبه است را با وزن يک لبه تعويض مي کنيم. در ليست هاي مجاورتي و ليست هاي مجاورتي چندگانه ، فيلد weight به ساختار گره اضافه مي شود.ساختار يک گره براي ليست هاي مجاورتي چندگانهگرافي که لبه هايش داراي وزن باشد ، شبکه ناميده مي شود.

اسلاید 232: 2-6 اعمال ابتدايي گرافبا توجه به گراف بدون جهت G(V ، E) و راس v از V(G) مي خواهيم رئوسي از G را که از v قابل دسترسي هستند، به دست آوريم( يعني همه رئوس متصل به v) . براي اين کار دو روش وجود دارد : جستجوي عمقي : روش عمقي تا حدودي شبيه پيمايش preorder يک درخت است. جستجوي رديفي : اين روش تا حدودي پيمايش ترتيب سطحي را مجسم مي کند.در پيمايش هاي عمقي و رديفي ، فرض مي کنيم که براي نمايش گراف ها از ليست مجاورتي پيوندي استفاده شده است.

اسلاید 233: 2-6 جستجوي عمقيدر آغاز راس v را ملاقات مي کنيم. بعد راسي مانند w را که قبلا ملاقات نشده و مجاور به v است را انتخاب کرده و روش جستجوي عمقي را با w دنبال مي کنيم. موقعيت جاري راس v در ليست مجاورتي با قرار دادن آن در يک پشته صورت مي گيرد. در نهايت ، جستجو به راسي مانند u خواهد رسيد که فاقد هر گونه راس غيرملاقات شده در ليست مجاورتي باشد. در اين مرحله راسي از پشته انتخاب و و حذف شده و فرآيند فوق به همين صورت ادامه پيدا مي کند. بر اساس اين روش ، رئوس ملاقات شده، خارج شده و رئوس ملاقات نشده ، داخل پشته قرار مي گيرند. جستجو زماني پايان مي پذيرد که پشته تهي باشد.

اسلاید 234: 2-6 جستجوي عمقيجستجوي عمقي شبيه پيمايش preorder يک درخت مي باشد . زيراVoid dfs (int V){/* depth first search of a graph beginning with vertex V . */node_pointer w ;visited[V] = TRUE ;print f ( “ %5d “ ، V ) ;for (w = graph[V] ; w ; w = w-> link )if ( ! Visited [w->vertex] )dfs (w-> vertex ) ;}

اسلاید 235: ....1.0.0.1.2NULL3.5.7NULL4NULL6NULL....1.2.2.3.7NULL7NULL7NULL4.6NULL5.01234567گراف Gنمايش ليست هاي مجاورتي2-6 جستجوي عمقي(مثال)

اسلاید 236: اگر روش جستجوي عمقي را از راس آغاز کنيم ، رئوس گراف G به ترتيب ملاقات مي شوند.2-6 جستجوي عمقي(مثال)توضيح شکل قبل

اسلاید 237: 2-6 تحليل dfsاگر G توسط ماتريس مجاورتي نمايش داده شود ، زمان لازم براي تعيين همه رئوس مجاور به v ، O(n) است. از آنجا که حداکثر n راس مشاهده مي شود ، کل زمان خواهد شد.

اسلاید 238: 2-6 جستجوي رديفي پيمايش را با راس v شروع نموده ، پس از ملاقات راس مزبور ، آنرا علامت گذاري مي کنيم. اول هر يک از رئوس مجاور به راس v را در ليست مجاورتي ملاقات مي کنيم. زماني که همه رئوس مجاور با راس v را ملاقات کرديم ، تمام رئوس ملاقات نشده که مجاور با اولين راس مجاور با v در ليست مجاورتي است را ملاقات مي کنيم. براي انجام اين کار ماداميکه هر راس ملاقات مي شود ، آنرا در يک صف قرار مي دهيم. هنگامي که ليست مجاورتي تمام شد ، راسي را از صف حذف و با تست هر يک از رئوس در ليست مجاورتي اين فرآيند را ادامه مي دهيم. رئوس ملاقات نشده ، ملاقات و سپس در صف قرار مي گيرند. رئوس ملاقات شده ناديده گرفته مي شوند. جستجو هنگامي که صف تهي گردد ، خاتمه مي يابد.

اسلاید 239: 2-6 جستجوي رديفي تابع bfs حاوي دستورات لازم جهت پياده سازي جستجوي رديفي است.

اسلاید 240: 2-6 درخت هاي پوشاچنانچه گراف G متصل باشد ، پيمايش هاي جستجوي عمقي يا جستجوي رديفي ، تمام رئوس گراف G را ملاقات مي کنند.در اين حالت با اعمال هر يک از پيمايش ها لبه هاي گراف G به دو قسمت تقسيم مي شوند :T ( براي لبه هاي درخت ) : مجموعه لبه هاي به کار رفته يا پيموده شده در جستجو مي باشد.N (براي لبه هاي غير درخت ) : مجموعه لبه هاي باقي مانده مي باشد.

اسلاید 241: 2-6 درخت هاي پوشالبه هاي T ، يک درخت که شامل تمام رئوس گراف G مي باشد را تشکيل مي دهند .تعريف درخت پوشا : درختي که تعدادي از لبه ها و تمام رئوس G را در بر دارد ، درخت پوشا ناميده مي شود :گرافسه درخت پوشاي آن

اسلاید 242: درخت پوشايي که از فراخواني dfs به دست مي آيد را درخت پوشاي عمقي مي نامند. چنانچه از روش bfs استفاده شود ، درخت پوشاي حاصل را درخت پوشاي رديفي مي نامند.2-6 درخت هاي پوشادرخت پوشاي dfsدرخت پوشاي bfs

اسلاید 243: مقصود از زير گراف حداقل ، يعني زيرگرافي که تعداد لبه هايش کمترين باشد.هر گراف متصل با n راس ، بايستي حداقل n-1 لبه داشته باشد و همه گراف ها متصل با n-1 لبه ، درخت هستند. درخت پوشا داراي n-1 لبه مي باشد. ايجاد زيرگراف هاي حداقل ، کاربردهاي متعددي در طراحي شبکه هاي ارتباطي دارد.مثال : اگر رئوس گراف G نماينده شهرها و لبه ها معرف جاده هاي ارتباطي بين شهرها بلشد ، آنگاه حداقل تعداد خطوط مورد نياز براي اتصال n شهر به يکديگر n-1 خواهد بود.2-6 درخت هاي پوشا

اسلاید 244: 2-6 اجزاي دو اتصالي و نقاط اتصالنقطه اتصال : يک راس مانند v از گراف G مي باشد به نحوي که حذف راس v همراه با تمام لبه هاي متلاقي با v ، گرافي به نام ايجادمي کند که حداقل داراي دو جز متصل است.گراف دو اتصالي يک گراف متصل است اگر فاقد نقاط اتصالي باشد .0951326487گراف دو اتصاليگراف متصل

اسلاید 245: 2-6 اجزاي دو اتصالي و نقاط اتصالاجزاي دو اتصالي يک گراف بدون جهت متصل مانند G يک زير گراف دو اتصالي حداکثري به نام H مي باشد. منظور از اين حداکثر اين است که G فاقد زيردرختاني است که هم دو اتصالي و هم داراي خاصيت H باشند.با استفاده از درخت پوشاي عمقي گراف G ، مي توان اجزاي دو اتصالي يک گراف بدون جهت متصل را به دست آورد.يک لبه غيردرختي مانند يک لبه غيربرگشتي است (back edge ) ، اگر و تنها اگر u جد v و يا v جد u باشد.

اسلاید 246: 2-6 اجزاي دو اتصالي و نقاط اتصالريشه يک درخت پوشاي عمقي يک نقطه اتصال است ، اگر و تنها اگر داراي حداقل دو فرزند باشد.هر راس مانند U يک نقطه اتصال است ، اگر و تنها اگر داراي يک فرزند مانند W باشد به نحوي که قادر باشيم با استفاده از يک مسير که شامل تنها W ، نسل ها و يک لبه برگشتي ، به جد u برسيم.

اسلاید 247: براي هر راس در G ، low(u) پايين ترين عدد عمقي است که مي توانيم از U با استفاده از يک مسير نسل ها به دنبال حداکثر يک لبه برگشتي ، به آن برسيم.Low (u) = min { dfn (u) ، min {low(w) │ w is a child of u } ، min { dfn (w) │ ( u ، w ) is a back edge } }که u يک نقطه اتصال است ، اگر و تنها اگر u ريشه يک درخت پوشا بوده و داراي دو فرزند يا بيشتر باشد و يا u ريشه نباشد و داراي يک فرزند مانند w است به نحوي که low (w) ≥ = dfn (u) است.2-6 اجزاي دو اتصالي و نقاط اتصال

اسلاید 248: 2-6 اجزاي دو اتصالي و نقاط اتصال42310856790123456789مقدير dfn و low براي درخت پوشاي با root = 3

اسلاید 249: 3-6 درختان پوشاي با حداقل هزينههزينه يک درخت پوشاي يک گراف جهت دار داراي وزن ، مجموع هزينه هاي( وزن هاي) لبه ها در درخت پوشا مي باشد.درخت پوشاي حداقل هزينه ، درخت پوشايي است که داراي کمترين هزينه باشد.براي به دست آوردن درخت پوشاي حداقل هزينه يک گراف جهت دارمتصل مي توان از سه الگوريتم متفاوت استفاده نمود :الگوريتم راشال ، الگوريتم پريم ، الگوريتم سولينهر سه روش از يک طراحي الگوريتمي به نام خط مشي greedy استفاده مي کنند.

اسلاید 250: 3-6 درختان پوشاي با حداقل هزينهبراي درخت هاي پوشا از ملاک کمترين هزينه استفاده مي شود. روش ما بايد داراي شرايط زير باشد :بايد فقط از لبه هاي داخل گراف استفاده کنيم. بايد دقيقا از n-1 لبه استفاده کنيم. نبايد از لبه هايي که ايجاد يک حلقه مي کنند ، استفاده کنيم.

اسلاید 251: 3-6 الگوريتم راشالدر اين روش ، درخت پوشاي با کمترين هزينه T ، لبه به لبه ساخته مي شود. لبه هاي مورد استفاده در T ، به ترتيب صعودي وزن ها مي باشد. يک لبه در T خواهد بود، اگر با لبه هاي قبل که در T بوده اند ، تشکيل يک حلقه ندهد چون G متصل است و داراي n > 0 راس است ، دقيقا n – 1 لبه براي T انتخاب مي شود.

اسلاید 252: 3-6 الگوريتم راشال (مثال)01526430152643100152643101201526431012140152643102524221812162814015264310121416015264310121416222501526431012141622

اسلاید 253: 3-6 الگوريتم راشالفرض کنيد G يک گراف متصل بدون جهت باشد ، الگوريتم راشال يک درخت پوشاي حداقل را ايجاد مي کند.قضيه

اسلاید 254: 3-6 الگوريتم پريمالگوريتم پريم مانند الگوريتم راشال ، در هر زمان يک لبه از درخت پوشاي حداقل هزينه را مي سازد. هر چند در هر مرحله الگوريتم ، مجموعه لبه ها انتخاب شده يک درخت را تشکيل مي دهند . در مقابل ، مجموعه لبه هاي انتخاب شده در الگوريتم راشال در هر مرحله يک جنگل را تشکيل مي دهند. الگوريتم پريم با يک درخت مانند T ، که تنها شامل يک راس است ، شروع مي کند. اين مي تواند هر يک از رئوس در گراف اصلي باشد. سپس يک لبه با کمترين هزينه مانند به T اضافه مي شود به نحوي که نيز خود يک درخت مي باشد. اين عمل را تا زماني که T شامل n – 1 لبه باشد ، ادامه مي دهيم.

اسلاید 255: 3-6 الگوريتم پريم (مثال )0152643102524221812162814250152643102501526431022250152643101222015264310250152643101214162225015264310121622

اسلاید 256: 3-6 الگوريتم سولينبر خلاف الگوريتم پريم و راشال ، الگوريتم سولين چندين لبه را براي اضافه نمودن در هر مرحله انتخاب مي کند. در ابتدا يک مرحله ، لبه هاي انتخاب شده ، همراه با تمام n راس گراف ، تشکيل يک درخت پوشا را مي دهند. در خلال يک مرحله يک لبه براي هر درخت در جنگل انتخاب مي کنيم. اين لبه داراي حداقل هزينه بوده يعني دقيقا داراي يک راس در درخت مي باشد. از آنجا که دو درخت در جنگل مي توانند يک لبه يکسان انتخاب کنند ، لذا مي توانيم کپي تکراري از لبه ها را حذف کنيم. در ابتداي مرحله اول ، مجموعه لبه هاي انتخاب شده خالي مي باشد. اين الگوريتم هنگامي به پايان مي رسد که فقط يک درخت در انتهاي يک مرحله باقي و يا هيچ لبه اي براي انتخاب باقي نمانده باشد.

اسلاید 257: 3-6 الگوريتم سولين (مثال )01526431025242218121628140152643101214222501526431012141622

اسلاید 258: 4-6 يک مبدا و چند مقصددر اين مساله گراف جهت دار G = (V ، E ) را در نظر مي گيريم. تابع وزني w(e) >0 را براي لبه هاي G و راس مبدا فرض مي کنيم. مساله ، تعيين کوتاهترين مسير از به بقيه رئوس در G است. فرض مي کنيم تمام وزن ها مثبت باشند.4520101515320353050101) 2)3)4)10254545pathlengthيک گراف و کوتاهترين مسير از

اسلاید 259: 4-6 کوتاهترين مسير بين هر جفت از رئوسمساله کوتاهترين مسير بين هر زوج از رئوس به مفهوم يافتن کوتاهترين مسير بين همه رئوس مي باشد ( به طوري که i ≠ j ) از آنجا که G داراي n راس و shortestpath داراي زمان مي باشد، لذا کل زمان صرف شده خواهد بود.گراف G توسط ماتريس مجاورتي هزينه خود با cost[i][j] = 0 ارايه مي شود (i = j) و در صورتي که لبه ( i ≠ j ) < i ، j > در G نباشد، cost[i][j] حاوي عدد بزرگي خواهد بود که اين عدد بايد همان محدوديت هاي مطرح شده در خصوص مساله يک مبدا ( single source ) را دارا باشد.

اسلاید 260: هزينه کوتاهترين مسير از i به j در G است.را هزينه کوتاهترين مسير از i به j تعريف مي کنيم که اين مسير هيچ راس مياني که انديس کوچکتر يا مساوي از (index ≤ k) k داشته باشيم ، عبور نمي کند. 4-6 کوتاهترين مسير بين هر جفت از رئوسنکته اصلي در همه الگوريتم هايي که روي زوج ها عمل مي کنند ، اين مي باشد که همه آنها با شروع کرده و ماتريس هاي متوالي را ايجاد مي کند.

اسلاید 261: اگر قبلارا توليد کرده باشيم ، مي توانيم را با عمل روي هر زوج از رئوس i و j با توجه به يکي از دو قاعده زير به دست آوريم :کوتاهترين مسير از i به j از هيچ راسي با انديس بزرگتر از k عبور نمي کند و حتي از راسي با انديس k نيز نمي گذرد و بنابراين هزينه آن است. چنين کوتاهترين مسيري از راس k مي گذرد بنابراين چنين مسيري شامل مسيري از i به k و به دنبال آن مسيري از k به i مي باشد. هيچ کدام از اين مسيرها با انديس بزرگتر از k-1 عبور نخواهد کرد ، بنابراين هزينه آن ها و مي باشد. 4-6 کوتاهترين مسير بين هر جفت از رئوس

اسلاید 262: 4-6 کوتاهترين مسير بين هر جفت از رئوس: فرمول 1: فرمول 2تابع allcosts را محاسبه مي کند.زمان کل allcosts برابراست.

اسلاید 263: 4-6 گراف جهت دارG و ماتريس هزينه آن ( مثال)ماتريس مجاورتي هزينه ها براي گراف G642113گراف جهت دار G

اسلاید 264: 4-6 ماتريس هاي توليد شده توسط allcosts (مثال) 0 1 20 4 116 0 23 ∞ 00120 1 20 4 116 0 23 7 00120 1 20 4 66 0 23 7 00120 1 20 4 65 0 23 7 0012(1)(2)(3)(4)

اسلاید 265: 4-6 بسته بودن تعديدر يک گراف جهت دار با لبه هاي بدون وزن مانند G ، آيا براي هر دو راس مانند i وj ، مسيري از i به j وجود دارد يا خير؟ دو حالت مي تواند مورد توجه قرار بگيرد :وقتي که همه مسيرها طول مثبت داشته باشند که بسته بودن تعدي يک گراف ناميده مي شود. زماني که طول مسيرها غيرمنفي باشد که بسته بودن تعدي انعکاسي يک گراف ناميده مي شود.

اسلاید 266: 4-6 ماتريس بسته بودن تعدي و ماتريس بسته بودن تعدي انعکاسيتعريف : ماتريس بسته بودن تعدي ، ، يک گراف جهت دار مانند G ، ماتريسي است که اگر مسيري از i به j با طول بزرگتر از صفر وجود داشته باشد ، بوده و در غير اين صورت خواهد بود.تعريف : ماتريس بسته بودن تعدي انعکاسي ، ، يک گراف جهت دار مانند G ، ماتريسي است که اگر مسيري بزرگتر يا مساوي با صفر از i به j وجود داشته باشد، بوده و در غير اين صورت خواهد بود. تنها تفاوت و در عناصر روي قطر اصلي است. بنابراين مي باشد

اسلاید 267: 5-6 شبکه AOVتعريف : شبکه AOV (activity on vertex) گراف جهت داري مانندG است که رئوس آن نمايانگر فعاليت ها يا عملکردها است و لبه هاي آن نمايانگر ارتباطات بين عملکردها مي باشد، اين گراف ، شبکه فعاليت هاي روي رئوس يا شبکه AOV ناميده مي شود.

اسلاید 268: تعريف : راس i در يک شبکه AOV مربوط به گراف G ، يک راس تقدمي براي راس j خواهد بود، اگر و تنها اگر مسير جهت داري از راس i به j وجود داشته باشد. اگر و تنها اگر <i ، j > لبه اي در G باشد ، i يک راس تقدمي بلافصل براي j است. اگر i يک راس تقدمي براي j باشد ، آنگاه j راس تاخيري براي i مي باشد. اگر i يک راس تقدمي بلافصل براي j باشد ، آنگاه j راس تاخيري بلافصل براي i مي باشد.5-6 شبکه AOV

اسلاید 269: 5-6 شبکه AOV (مثال)c8c7c3c11c15c5c4c6c14c1c2c9c10c13c12

اسلاید 270: 5-6 شبکه AOVتعريف : يک رابطه . تعدي است اگر وتنها اگر براي تمام سه گانه هاي i . j ‚i ، j ، kوj . k ، i . Kرا نتيجه مي دهد(i.j and j.k => i.k)يک رايطه . روي مجموعه S غير انعکاسي است ، اگربراي تمامي مقادير i در S ، i . i نادرست (flash) باشد. رابطه اي که هم تعدي و هم غير انعکاسي باشد ، يک رابطه ترتيبي ناميده مي شود.اگر رابطه تقدمي غيرانعکاسي نباشد ، آنگاه فعاليتي وجود دارد که راس تقدمي آن خودش است.

اسلاید 271: گراف جهت داري که هيچ حلقه اي نداشته باشد ، گراف acyclic جهت دار يا dag ناميده مي شود.تعريف : ترتيب موضعي يک ترتيب خطي از رئوس گراف است به نحوي که به ازاي هر دو راس i و j ، اگر i يک راس تقدمي براي j در شبکه باشد ، آنگاه i در اين ترتيب خطي بيش از j قرار مي گيرد.5-6 شبکه AOV

اسلاید 272: 5-6 فعاليت بر روي لبه (AOV) شبکهيک شبکه فعاليت که ارتباط نزديکي با شبکه AOV داشته باشد ، فعاليت روي لبه يا شبکه AOE ناميده مي شود.اعمالي که روي پروژه صورت گيرد با لبه هاي جهت دار نمايش داده مي شوند.رئوس شبکه نمايانگر وقايع است.يک واقعه فقط زماني اتفاق مي افتد که همه فعاليت هاي وارده به آن قبلا کامل شده باشد.

اسلاید 273: 5-6 فعاليت بر روي لبه (AOV) شبکهشبکه هاي فعاليت از نوع AOE در ارزيابي اجرايي چندين نوع از پروژه ها به طور موثري مورد استفاده قرار مي گيرند. اين ارزيابي شامل تعيين چندين نکته در مورد پروژه ها به شرح زير است : کمترين زمان ممکن براي تکميل پروژه تعيين اينکه کدام فعاليتها بايستي زودتر انجام شوند تا زمان تکميل پروژه کاهش يابد.

اسلاید 274: چندين تکنيک و روش بسيار مهم براي ارزيابي مدل هاي شبکه پروژه توسعه يافته اند از جمله :PERT ( ارزيابي اجرايي و تکنيک بازبيني)CPM ( روش مسير بحراني )RAMPS ( تخصيص منبع و زمان بندي پروژه چندگانه ) 5-6 فعاليت بر روي لبه (AOV) شبکه

اسلاید 275: از آنجا که فعاليتهاي يک شبکه AOE مي توانند به طور موازي انجام شوند ، کمترين زمان لازم براي کامل شدن پروژه ، اندازه طولاني ترين مسير از راس اغازي به راس پاياني است.مسيري با طولاني ترين طول ، يک مسير بحراني است.5-6 فعاليت بر روي لبه (AOV) شبکه

اسلاید 276: 5-6 فعاليت بر روي لبه (AOV) شبکهزودترين زماني که واقعه مي تواند اتفاق بيفتد ، طولاني ترين مسير از راس آغازي به راس است. زودترين زماني که يک واقعه مي تواند اتفاق بيفتد ، زودترين زمان شروع همه وقايع موجود که از اين راس خارج شده اند را تعيين مي کند. اين زمان را به صورت early(i) براي فعاليت نشان مي دهيم.

اسلاید 277: 5-6 فعاليت بر روي لبه (AOV) شبکهبراي هر فعاليت مانند مي توان ديرترين زمان را نيز تعريف کرد. که در واقع ديرترين زماني است که يک فعاليت مي تواند انجام شود به شرط اينکه زمان پروژه را افزايش ندهد.همه فعاليتهايي که به صورت early(i) = late(i) هستند ، فعاليت هاي بحراني ناميده مي شوند.تفاضل early(i) و late(i) ، اندازه يا ميزان بحراني بودن يک فعاليت را نشان مي دهند.

اسلاید 278: 5-6 محاسبه زودترين زمانبه منظور به دست آوردن زودترين و ديرترين زمان براي تمام فعاليتهاي يک شبکه ، مناسب است که براي تمام وقايع در شبکه ، ابتدا زودترين زمان رويداد واقعه يعني earliest[j] و سپس ديرترين زمان رويداد واقعه يا lastest[j] محاسبه نمود. سپس اگر فعاليت به وسيله لبه < k ، l > ارايه شود ، مي توانيم early(i) وlate(i) را از فرمول زير محاسبه کنيم : late(i) = latest [l] – duration of activity زمان earliest[j] و lastest[j] در دو مرحله محاسبه مي گردد : مرحله پيشرو و مرحله پسرو

اسلاید 279: فصل هفتم: مرتب سازيجستجو جستجوي دودوييمرتب سازي درجيمرتب سازي سريعمرتب سازي ادغاممرتب سازي ليست.....اهداف

اسلاید 280: فصل هفتم : مرتب سازيفرض کنيد مجموعه اي از اطلاعات مربوط به اشيا داريم . اگر اين مجموعه به راحتي در حافظه قابل دسترسي قرار گيرند ، آنرا ليست مي نامند.در صورتي که براي ذخيره کردن مجموعه به حافظه خارجي نياز باشد آنرا فايل مي نامند.اطلاعات يک شي از مجموعه فوق را رکورد مي نامند.هر جز از رکورد را فيلد مي ناميم.

اسلاید 281: 1-7 اصطلاحاتزماني که يک ليست از رکوردها را جستجو مي کنيم ، هدف پيدا نمودن رکوردهايي است که داراي فيلدي با مشخصات مورد نياز باشند. اين فيلد را اصطلاحا کليد مي نامند. کارايي روش و خط مشي جستجو بستگي به آرايش و نحوه قرار گرفتن رکوردها در ليست دارد.

اسلاید 282: 1-7 جستجوي ترتيبيفرض کنيد که ليست و يک کليد جستجو به نام Searchnum داشته باشيم . هدف بازيابي رکوردي است که کليد آن منطبق بر searchnum باشد. اگر اين ليست داراي n رکورد باشد ، با list[i].key به مقدار کليد رکورد i دسترسي پيدا مي کنيم، ليست را با جستجوي مقادير کليدهايlist[n-1].key ، … ، list[0].key مورد بررسي قرار مي دهيم تا به رکورد مورد نظر برسيم يا تمام ليست را جستجو کنيم.

اسلاید 283: 1-7 تحليل تابع seqsearch تابع seqsearch نحوه جستجوي ترتيبي را نشان مي دهد.تحليل تابع seqsearch : قبل از شروع جستجو ، seqsearch را در موقعيت list[n].key قرار مي دهيم. اين موقعيت در واقع انتهاي ليست را نشان مي دهد. با جلوگيري از تست پايان ليست ، يعني شرايطي که i > n -1 باشد، مي توانيم براحتي ساختار حلقه را ساده کنيم. اگر عمل جستجو موفقيت آميز نباشد، i = n ، مقدار -1 را برمي گردانيم . بنابراين در يک جستجوي ناموفق نياز به n + 1 عمل مقايسه کليد داريم که زمان آنO(n) خواهد بود.

اسلاید 284: ميانگين تعداد عمل مقايسه در يک جستجوي موفقيت آميز برابر است با :1-7 تحليل تابع seqsearch

اسلاید 285: 1-7 جستجوي دودوييدر جستجوي دودويي بايستي ليست بر اساس فيلد کليد مرتب شود ، يعني :.list[0].key ≤ list[1].key ≤ … ≤ list[n-1].key

اسلاید 286: اين جستجو با مقايسه searchnum و list[middle].key ، به ازاي middle=(n-1)/2 شروع مي شود.هنگام مقايسه سه حالت ممکن است روي دهد :searchnum< list[middle].key : در اين حالت رکوردهايي بين list[middle] و list[n-1] کنار گذاشته شده و جستجو با رکوردهاي List[0] تا List[middle-1] دنبال مي شود.Searchnum= list[middle].key : در اين حالت جستجو با موفقيت به پايان مي رسد. searchnum> list[middle].key : در اين حالت ، رکوردهاي بين List[0] و list[middle] کنار گذاشته شده و جستجو با رکوردهاي list[middle+1] تا list[n-1] دنبال مي شود.1-7 جستجوي دودويي

اسلاید 287: 1-7 درخت تصميم گيري براي جستجوي دودويي46581744890261530569582[5][2][0][8][3][4][1][6][9][7][11][10]

اسلاید 288: 1-7 وارسي ليست(list Verification) نوعا مقايسه ليستها جهت تعيين تست يکي بودن يا تعيين اختلاف آنها نوعي بررسي ليست به حساب مي آيد.مسئله وارسي ليست يک نمونه از جستجوي مکرر يک ليست است که هر کليد آن به عنوان کليد جستجو در ليست ديگري به کار مي رود.

اسلاید 289: تابع verify1 : دو ليست را در نظر مي گيرد که به صورت تصادفي مرتب شده اند . به سادگي مي توان ثابت نمود که زمان مجانبي اين تابع در بدترين حالت برابر با O(mn) مي باشد.تابع verify2 : از همان ورودي تابع verify1 استفاده مي کند با اين تفاوت که ليستها قبل از وارسي ، مرتب مي شوند. در بدترين حالت ، زمان لازم O(tsort (n) + tsort (m) + m+n ) خواهد بود . tsort (n) : زمان لازم جهت مرتب کردن n رکورد از ليست اول (list1) tsort (m) : زمان لازم براي مرتب کردن m رکورد از ليست دوم (list2) مي باشد.1-7 وارسي ليست(list Verification)

اسلاید 290: 2-7 مرتب سازيدو نوع از کاربردهاي مهم مرتب سازي عبارتند از :کمک در امر جستجوتطابق عناصر و وارده ها در يک ليست

اسلاید 291: 3-7 مرتب سازي درجيInsertion Sort در اين نوع مرتب سازي ، در هر لحظه فقط يک رکورد در داخل ليست قابل رويت است بنابراين رکورد را در بين رکوردهاي مرتب شده طوري قرار مي دهيم که رشته حاصل با اندازه i نيز مرتب شده باشد.

اسلاید 292: 3-7 تحليل تابع insertion sort زمان محاسباتي جهت درج يک رک.رد به داخل ليست مرتب شده ، O(i) خواهد بود.زمان کل در بدترين حالت برابر است با :

اسلاید 293: 3-7 مرتب سازي درجي(مثال)رشته (1و2و3و4و5 ) را با n = 5 در نظر گرفته ، بعد از عمل درج ، داريم :زمان محاسباتي مرتب سازي درجي O(( k + 1 ) n ) مي باشد.

اسلاید 294: مرتب سازي درجي دودويي :براي انجام اين عمل بايستي به جاي جستجوي ترتيبي از جستجوي دودويي استفاده نماييم.در اين حالت ، تعداد انتقال رکورد بدون تغيير باقي خواهد ماند.مرتب سازي درجي ليست : عناصر يک ليست را مي توان به جاي قرار دادن در آرايه در يک ليست پيوندي پويا قرار داد. در اين حالت ، تعداد انتقال رکورد صفر مي شود زيرا فقط فيلد اشاره گر تغيير مي کند.3-7 انواع مرتب سازي درجي

اسلاید 295: 4-7 مرتب سازي سريعتفاوت مرتب سازي سريع با درجي در اين است که در اين نوع مرتب سازي کليد مفصلدر سمت راست با توجه به کل فايل قرار مي گيرد. بنابراين اگر کليد در محل s(i) قرار بگيرد ، پس به ازايبوده و به ازاي، مي باشد. از اين رو بعد از جايگذاري ، فايل اصلي به دو زير فايل که شامل رکوردهاي و مي باشند ، تقسيم مي شوند. از آنجايي که رشته مرتب شده از تمام رکوردها در زير فايل اول ممکن است در سمت چپ s(i) و تمام رکوردها در زير فايل دوم در سمت راست s(i) قرار گيرند ، لذا اين دو فايل مي توانند به طور مستقل مرتب گردند.

اسلاید 296: 4-7 مرتب سازي سريعميانگين زمان محاسبه براي مرتب سازي سريع مي باشد.فرض کنيد زمان لازم براي مرتب سازي يک فايل با n رکورد باشد. بنابراين به بزاي مقدار ثابت k داريم :قضيه

اسلاید 297: 4-7 مرتب سازي سريعمرتب سازي سريع جهت پياده سازي عمل بازگشت پذيري به فضاي پشته نياز دارد.حداکثر عمق بازگشت پذيري log n خواهد بود و به فضاي پشته O(log n) نياز خواهد بود.

اسلاید 298: 5-7 زمان مرتب سازي بهينهبهترين زمان ممکن براي مرتب سازي مي باشدحداقل عمق يک درخت تصميم گيري براي مرتب سازي n عنصر مجزا و قابل تفکيک برابر با مي باشد.هر الگوريتمي که عمل مرتب سازي را تنها با مقايسه انجام مي دهد ، در بدترين حالت بايستي زماني برابر داشته باشد.

اسلاید 299: 5-7 درخت تصميم گيري(مثال)stopstopstopstopstopstopINoІІVVIІІІVIYesYesYesYesYesNoNoNoNo[0،1،2][0،1،2][0،1،2][1،0،2][1،0،2][1،0،2][0،2،1][0،2،1][2،0،1][1،2،0][2،1،0]

اسلاید 300: 6-7 مرتب سازي ادغامالگوريتم O(1) :مراحل در O(1) فضاي ادغام هنگامي که تعداد رکوردها يعني n مجذور کامل بوده و تعداد رکوردهاي هر فايل مورد ادغام نيز مضربي از باشد ، در نظر گرفته مي شود.

اسلاید 301: 6-7مراحل الگوريتم O(1)مرحله 1 :رکورد با بزرگترين کليدها را مشخص کنيد. اين امر با رديابي دو فايل مورد ادغام از سمت راست به چپ صورت مي گيرد. مرحله 2 : رکوردهاي فايل دوم که از مرحله اول شناسايي شده اند را با آن دسته از رکوردهايي که در سمت چپ رکوردهايي که از فايل اول شناسايي شدند ، تعويض کنيد. اين امر موجب مي شود که رکورد با بيشترين کليد ، تشکيل يک بلاک مجاور را بدهد.مرحله 3 : بلاک با بيشترين رکورد را با بلاک هاي منتهي اليه سمت چپ تعويض کنيد( مگر اينکه آن بلاک قبلا بلاک منتهي اليه سمت چپ باشد ) . بلاک منتهي اليه سمت راست را مرتب کنيد.

اسلاید 302: 6-7مراحل الگوريتم O(1) (ادامه)مرحله 4 : تمام بلاک ها به جز بلاک با بزرگترين رکوردها را به ترتيب غير نزولي آخرين کليد در بلاک مرتب کنيد.مرحله 5 : هر تعداد غير مرحله ادغامي که براي ادغام بلاک ( غير از بلاک هايي با بزرگترين کليد ) نياز باشد را اجرا کنيد.مرحله 6 : بلاک با بزرگترين کليد را مرتب کنيد.

اسلاید 303: 6-7 مرتب سازي ادغام تکراري( غير بازگشتي )در نسخه تکراري فرض خواهد شد که رشته ورودي شامل n ليست مرتب شده به طول يک است. ليست ها را دو به دو ( جفتي ) ادغام مي کنيم تا تعداد n/2 ليست با اندازه 2به دست آوريم. سپس n/2 ليست حاصل را مجددا دو به دو ادغام مي کنيم و اين عمل را ادامه مي دهيم تا يک ليست باقي بماند.

اسلاید 304: براي نسخه بازگشتي ، ساختار رکورد خود را طوري تغيير مي دهيم تا يک فيلد اتصال (Link) را نيز دربرگيرد.6-7 مرتب سازي ادغام بازگشتيالگوريتم ادغام در بدترين حالت و حالت ميانگين به زمان محاسباتي برابر با O(n log n) نياز دارد.اين الگوريتم همچنين متناسب با تعداد رکوردهايي که در فايل بايد مرتب مي شدند ، نيازمند فضاي اضافي است.

اسلاید 305: 7-7 مرتب سازي heapروش مرتب سازي heap نيازمند تنها يک مقدار حافظه اضافي است و در همين حال ، بدترين حالت و زمان متوسط آن برابر با O(n log n) خواهد بود. با وجود اينکه مرتب سازي heap کمي کندتر از مرتب سازي ادغام با استفاده از O(n) فضاي اضافي است ولي از مرتب سازي ادغام با استفاده از O(1) فضاي اضافي سريعتر مي باشد.

اسلاید 306: 7-7 مرتب سازي heapبراي مرتب سازي يک ليست ، n-1 گذر بر روي ليست اعمال مي شود. در هر گذر ، اولين رکورد در heap با آخرين رکورد تعويض مي گردد . از آنجا که اولين رکورد هميشه شامل بزرگترين کليد است، اين رکورد با بزرگترين کليد را در محل n ام قرار مي دهيم. در گذر دوم رکورد با دومين کليد بزرگ را در موقعيت n-1 قرار مي دهيم و در نهايت در i امين گذر ، رکورد با i امين کليد بزرگ را در موقعيت n - i + 1 قرار مي دهيم.کل زمان محاسباتي O(n log n) خواهد شد.

اسلاید 307: 8-7 مرتب سازي مبنادر اينجا توجه خود را روي مرتب سازي رکوردهايي معطوف مي کنيم که داراي چندين کليد هستند. اين کليدها داراي برچسب مي باشد. به نحوي که نشان دهنده با اهميت ترين کليد و مشخص کننده کم اهميت ترين کليد است.روش هاي مختلف مرتب سازي :MSD ( با ارزش ترين رقم ) LSD ( کم ارزش ترين رقم )

اسلاید 308: در مرتب سازي مبنا با استفاده از مبنا r کليد مرتب سازي را تجزيه مي کنيم. زمان محاسباتي کل برابراست با : O(MAX_DIGIT (RADIX_SIZE + n ) انتخاب مبنا در زمان مرتب سازي مبنا موثر است .8-7 مرتب سازي مبنا

اسلاید 309: 9-7 مرتب سازي ليست و جدولاين مرتب سازي ، ليست را به طور فيزيکي مرتب نکرده بلکه فيلدهاي اتصال را براي نشان دادن ترتيب عناصر اصلاح مي کند.

اسلاید 310: 10-7 خلاصه مرتب سازي داخليمرتب سازي درجي زماني که ليست به صورت جزيي مرتب شده باشد ، خوب کار مي کند.مرتب سازي ادغام بهترين روش براي بدترين حالات است.مرتب سازي سريع بهترين ميانگين را دارد.عملکرد مرتب سازي مبنا بستگي به کليد و انتخاب مبنا دارد.به ازاي n ≤ 20 مرتب سازي درجي (insertion_sort) سريعترين است.براي مقادير n بين 20 تا 45 مرتب سازي سريع (quicksort) بهترين و سريع ترين مي باشد.براي مقادير بزرگتر از n ، مرتب سازي ادغام(merge_sort ) سريع ترين مي باشد

اسلاید 311: مرتب سازي داخلي در هر زمان مي تواند سه بلاک (جميعا به طول 750 رکورد ) را در قالي رانش به ترتيب تا مرتب نمايد.در اين مورد مي توان از مرتب سازي سريع يا heap استقاده کرد. 10-7 خلاصه مرتب سازي داخلي

اسلاید 312: در زمان خواندن يا نوشتن از / به ديسک زمان هاي زيرمهم است :زمان جستجو(Seek time ) زمان تاخير (latency time ) زمان انتقال (Transmission time ) 11-7 مرتب سازي خارجي (روش هاي مرتب سازي فايل هاي بزرگ )

اسلاید 313: 11-7 مرتب سازي خارجيمعمولا روش مرتب سازي بر روي دستگاه هاي حافظه جانبي ، مرتب سازي ادغام است.اين روش اساسا شامل دو مرحله يا فاز مجزا است : در ابتدا ، سگمنت هاي فايل ورودي با استفاده از يک روش مرتب سازي داخلي مناسب ، مرتب مي شود. سگمنت هاي مرتب شده اصطلاحا رانش (run) ناميده مي شوند. در فاز دوم ، رانش هاي توليد شده در فاز اول بر اساس الگوي درخت ادغام ، ادغام شده و اين فرآيند تا هنگامي که تنها يک رانش باقي بماند ، ادامه پيدا مي کند.

اسلاید 314: براي تعيين زمان مورد نياز مرتب سازي خارجي بايد موارد زير را در نظر گرفت : = حداکثر زمان جستجو= حداکثر زمان تاخير= زمان لازم براي خواندن يا نوشتن يک بلاک 250 رکوردي= مجموع = زمان لازم براي مرتب سازي داخلي 750 رکورد= زمان لازم براي ادغام n رکورد از ميانگير ورودي به ميانگير خروجي11-7 مرتب سازي خارجي

اسلاید 315: 11-7 ادغام k طرفه به طور کلي ادغام k طرفه بر روي m رانش حداکثر نيازمند گذر بر روي داده ها مي باشد. با افزايش درجه ادغام ، در ميزان ورودي و خروجي صرفه جويي مي شود

اسلاید 316: 11-7 بکارگيري ميانگير براي عمليات موازي اگر k رانش به وسيله يک ادغام k طرفه با هم ادغام شوند ، واضح است که به حداقل k ميانگير ورودي و يک ميانگير خروجي جهت انجام عمليات ادغام نياز داريم. اگر ورودي ، خروجي و ادغام داخلي به طور موازي وهمزمان انجام شود ، کافي نيست.

اسلاید 317: مرحله 1 : اولين بلاک هر يک از k رانش را وارد کرده و k صف پيوندي که هر کدام داراي يک بلاک داده مي باشد را برقرار ميکنيم.k بلاک ورودي باقي مانده را به داخل يک پشته پيوندي قرار داده و بلاک هاي ورودي را آزاد کنيد. همچنين ou را برابر صفر قرار دهيد.مرحله2 : فرض کنيد lastkey[i] آخرين کليد وارد شده از رانش i باشد ، فرض کنيد که nextrun رانشي باشد که lastkey حداقل باشد. اگر ∞ + lastkey[nextrun] ≠ باشد، آنگاه بلاک بعدي از رانش nextrun را مقداردهي اوليه کنيد.11-7 مراحل الگوريتم مربوط به ميانگير

اسلاید 318: مرحله3 : تابع kwaymergeرا براي ادغام رکوردهايي از k صف ورودي و قرار دادن آنها در داخل ميانگير خروجي ou مورد استفاده قرار دهيد. ادغام تا زماني ادامه مي يابد که يا ميانگير خروجي پر شود و يا رکورد ∞+ داخل ou ادغام شود. اگر در طي اين ادغام ، يکي از ميانگيرهاي ورودي ، قبل از اينکه ميانگير خروجي پر شود و يا اينکه ∞+ داخل ou ادغام گردد، خالي شود، kwaymerge بر روي همان صف به ميانگير بعدي منتقل و ميانگير خالي را به پشته ميانگيرهاي خالي برگشت مي دهد. هر چند ، اگر ميانگير ورودي در همان زمان که ميانگير خروجي پر شده يا ∞+ داخل ou ادغام گردد ، خالي شود ، آنگاه ميانگير خالي در صف باقي مانده و kwaymerge به ميانگير بعدي بر روي صف منتقل نمي شود ، مگر اينکه ادغام خاتمه يابد.11-7 مراحل الگوريتم مربوط به ميانگير

اسلاید 319: مرحله4 : تا کامل شدن عمليات ورودي/ خروجي صبر کنيد.مرحله5 : اگر يک ميانگيرورودي خوانده شد ، آنرا براي رانش مناسب به صف اضافه مي کنيم. رانش بعدي را با استفاده از nextrun تعيين کنيد به نحوي که lastkey[nextrun] حداقل گردد.مرحله6 : اگر ∞ + lastkey[nextrun] ≠ باشد ، آنگاه بلاک بعدي از رانش nextrun را خوانده و ميانگير ورودي را آزاد کنيد.11-7 مراحل الگوريتم مربوط به ميانگير

اسلاید 320: مرحله7 : شروع به نوشتن محتويات ميانگير خروجي ou نماييد. ou را برابر با 1- ou قرار دهيد( ou = ou – 1 ) مرحله 8 : اگر رکورد با کليد ∞ + داخل ميانگير خروجي ادغام نشده باشد ، به مرحله 3 مراجعه کنيد در غير اين صورت تا تکميل عمليات نوشتن صبر نموده و سپس الگوريتم را خاتمه دهيد.11-7 مراحل الگوريتم مربوط به ميانگير