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

صفحه 1:


صفحه 2:


صفحه 3:
جايكاه درس در رشته كامبيود " ضرورت این درس: © ضرورت نیاز به زبانهای سطح بالا صرورت نیاز به زب 2 ۱ " ضرورت ترجمه برنامه های. نوشته شده با زبان سطح بالا به برنامه به زبان ماشین *" تنوع زبانهای برنامه نویسی سطح بالا * دروس پیش نیاز: ۴ نوع درس: اجباری © تعدادکل ساعات تدریس: ۳۰ © تعداد جلسات تدریس:۱۰ 

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

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

صفحه 6:
WY ۱-۱ سیکل زندگی نرم افزار- تحلیل تحلیل: ۴ در این مرحله مساله را به بخشهای قابل کنترل تقسیم می کنند. ۴ در تحلیل یک سیستم دو شیوه وجود دارد : ‎-١‏ شيوه از بالا به يايين ‏۲- شیوه از پایین به بالا } ‎ ‎ ‎ 

صفحه 7:
-\ ۱ سیکل زندگی نرم افزار- طراحی طراحي این مرحله ادامه کاری است که در مرحله تحلیل انجام می شود. طراح سیستم را از دو نقطه نظر بررسی می کند: از نظرداده های مقصود(ع۳۳اه 0) مورد نیاز برنامه از نظر اعمللی که بر روی ‎UT‏ اتجام می شود. لين ديدكاه به مشخصات امه یی های طراحی الگوریتم نیاز دارد. 

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

صفحه 9:
۱-۱ نمودار سیکل زندگی نرم افزار 

صفحه 10:
WY ‏تعریف الگوریتم‎ ۲-۱ الگوریتم مجموعه ای از دستورالعمل ها است که اگر دنبال شوند. موجب انجام کار خاصی می گردد گروه کامپیوتر ساختمان‌داده ها به نباری 7 صفحه: 10 

صفحه 11:
۲-۱ شرایط الگوریتم ‎of‏ ورودی: یک الگوریتم می تواند هیچ یا چندین کمیت ورودی داشته باشد که از محیط خارج تامین می شود. ‎EE‏ خروجی: الگوریتم بایستی حداقل یک کمیت به عنوان خروجی داشته باشد. ‏لا قطعیت: هر دستورالعمل باید واضح و بدون ابهام باشد. ‏لا محدودیت: اگر دستوذالعمل های یک الگوریتم را دنبال کنیم .برای تمام حالات . الگوریتم بايد يس از طى مراحل محدودی خاتمه یابد. ‏لا كارليى: هر دستورالعمل بايد به گونه ای باشد که با استفاده از قلم و کاغذ بتوان كن را با دست نیز اجرا نمود. ‎ ‎ ‎ ‎ 

صفحه 12:
UY ‏مثالی از الگوریتم: الگوریتم مرتب سازی‎ ۲-۱ Por (FO 5 iS sit +){ @renview tet [i] to bet [od] ced suppose that the swulest fateyer is ot lt [erin]; Aeterctscrace tet [+ ] cre bt [srt]; ساختم‌انداده هابه زباری 6 صفحه: 12 

صفحه 13:
۲-۱ الگوریتم باز گشتی تابع چیزی است که توسط تابع دیگر فراخوانده می شود ! توابع می توانند خودشان را صدا بزنند (باز گشت مستقیم يا مى توانند توابعى كه تابع فراخواننده را صدا میزنند(باز گشتی غيرمستقيم) را احضار نمايند. گروه کامپیوتر ساختمانداده ها به نبارل 8 صفحه: 13 

صفحه 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: return binsearch ( list . searchnum . middle +1. right ) ; case 0: return middle ; case 1: return binsearch ( list . searchnum . left . middle -1 ( : t return -1; إن |( صفحه: 14 

صفحه 15:
۳-۱ آرایه . ساختار و نوع داده ( آوایه [ مجموعه ای از عناصر از يك نوع داده مى باشد ( ساختار [ مجموعه ای از عناصر است که لزومی ندارد داده های آن یکسان باشد ( نوع داد( مجموعه ای از انواع داده مقصد(طام) و عملکردهایی است که بر روی این نوع داده ها عمل می کنند 15 ۰ گروه کامپیوتر 

صفحه 16:
WY ‏نوع داده ای مجرد‎ ۲-۱ © نوع داده مجرد يا انتزاعی (900/7)) که شامل مشخصات داده ها و اعمالى كه بر روى آنها انجام مى شود. *جهت جداسازی پیاده سازی و نمایش داده ها از یکدیگر. (aici Joe cere |} ‏گروه کامپیوتر‎ | 

صفحه 17:
نوع داده مجرد 94 ۱- ایجاد کننده/ سازنده ۲- تبدیل کنندگان ۳- مشاهده کنندگان / گزارش کنندگان گروه کامپیوتر ساختمان‌داده ها به نباری ] صفحه: 17 

صفحه 18:
۴-۱ تحلیل نحوه اجرای یک برنامه معیارهای محک زدن یک برنامه "۳ ن قسمت مربوط © آيا برنامه اهداف اصلى كارى را كه مى خواهيم انجام مى دهد؟ به تخمين های إنا 9 ‎Sas‏ حافظه و زمان © آيا برنامه درست كار مى كند' ‎nets‏ و © آيا برنامه مستند سازى شده است تا نحوه استفاده و طرز كار با آن مشخص شود؟ © آيا برنامه براى ايجاد واحدهاى منطقى . به طور موثر از توابع استفاده مى کند؟ © آيا كد كذارى خوانا است؟ ‎shel‏ برنامه می نامیم. ‏© آيا برنامه از حافظه اصلى و كمكى به طور موثرى استفاده مى كند؟ اميم. ‏آیا زمان اجرای برنامه برای هدف شما قابل قبول است؟ ‎ ‎ ‎ ‎ ‎ 

صفحه 19:
WY ‏میزان حافظه يا پیچیدگی فضای یک برنامه‎ ۴-۱ میزان حافظه یا پیچیدگی فضای یک برنامه مقدارحافظه مورد نیازبرای اجرای کامل یک برنامه است. میزان یا پیچیدگی زمان یک برنامه مقدار زمان کامپیوتر است که برای اجرای کامل برنامه لازم است. گروه کامپیوتر .. [ ساختم‌ازداده هابه نبا صفحه: 19 

صفحه 20:
۴-۱ میزان حافظه فضای مورد نیاز یک برنامه شامل موارد زیر است : یازمندیهای ‎Gre‏ این مطلب به فضای مورد نیازی که به تعداد و اندازه ورودی و خروجی بستگی ندارد. اشاره دارد. نیازمندیهای فضای متغیر این مورد شامل فضای مورد نیاز متغیرهای ساخت یافته ای است که اندازه آن بستگی به نمونه | از مساله ای که حل می شود دارد. | گروه کامپیوتر ساختمانداده هابه نبا إل منت 

صفحه 21:
WY ‏میزان حافظه(ادامه)‎ ۴-۱ نیازمندیهای فضای متغیر RP) =e SD نیازمندیهای فضای نیازمندیهای فضای بات ۳ گروه کامپیوتر ساختمانداده ها به نبارل 8 صفحه: 21 

صفحه 22:
۴-۱ زمان (100 بنامه دزمان ‎re);‏ برنامه عبارتست ازمجموع زمان ‎gia‏ و ۱ زمان اجرای برنامه. كريد کامپایل مشابه اجزای فضای ابت است زیرابه خصیصه های نمونه بستگی ندارد. (0)ر1 را به صورت زیر تعریف می شود T,(@) =¢,ADQun) + c,SURn) + GLDAn) + ‏عیه‎ 147 گروه کامپیوتر ساختمانداده ها به نبارل 8 صفحه: 22 

صفحه 23:
XI : ‏مرحله برنامه‎ ۴-۱ یک مرحله برنامه , قسمت با معنی برنامه است ( از لحاظ معنایی یا نحوی) که زمان اجرای آن مستقل از خصیصه های نمونه باشد | FEE Joe cere |} ‏گروه کامپیوتر‎ | 

صفحه 24:
۴-۱علامت گذاری مجانبی(6, 0.6) ‎Asymptotic)‏ ________ انگیزه برای تعیین تعداد مراحل. قابلیت مقایسه پیچیدگی دو برنامه که یک تلبع را اجرا می کنند و پیش بینی رشد و افزلیش زمان اجرا با تغییر صفات نمونه می باشد. ‎(a)=O(q(a)) [Big “ok” [‏ لس خولنده می‌شود ( ۴و ب ‎“PoP ae big ob oP‏ اگر و فقط اگر به ازای مقادیر ثابتی از ‎ly Plo) ODE‏ تمامی مقادیز > کمتر یا مساوی (9) ‎(a2 oD) at‏ ‏گروه کامپیوتر ساختمانداده ها به نبارل 8 صفحه: 24 ‎ ‎ ‎ ‎ ‎ 

صفحه 25:
۴-۱علامت گذاری مجانبی(6, 0.6) ‎WY‏ ‏م9۳0۵ فلس 0)1(8 :۰ نمان‌محاسبه ثابتی‌را نشانمی‌دهد 8 (0)۳ :۰ یک تابع خطی نامیده می شود 9 (07 تابع درجه دو نامیده می شود قضيه : 2 +62 ...+ 3 < (1)31 د. پنابراین ۰ (0)57 - )1 خواهد بود گروه کامپیوتر ساختمان‌داده ها به نباری ] صفحه: 25 

صفحه 26:
۴-۱ علامت گذاری مجانبی(6/ 0.6) 7 »۵ هکم تعریف امگا ‏ ۵0( می دادم شد ( کی( 1 و فقط اگر به ازای مقادیر ثلبت مثبت 7 و ()۰۳)0(2 ۷0 باشد(برای تمام مقادیر ‏ به شرطى كه 02000 باشد) ese 3 f() =a," +...+ aN+ & ‏اگر‎ a, > 0 ‏بود‎ daly: FU) =O7”) gal ple _ گروه کامپیوتر ساختمانداده ها به زبارن آ[ صفحه: 26 

صفحه 27:
۴-۱ علامت گذاری مجانبی(0؛ 0.62) ‎(Asymptotic).‏ _________— تعريف ‎sof) = O(g(n) : [Theta]ls‏ باشد (خوانده مي شود ‎FC)‏ 5 («ه)و اگر و فقط اگر به ازاي مقادیر ابت ,6 و ,6 و .بط ‎o9>9 C,g(n)<= f(n) <= c,g(n)‏ داشته باشد (براي تمام ‎M>=N, polis‏ نشلنه گذاری تتا از دو نشلنه گذاری ذکر شده ‏ طه ‎big‏ “9 امگا دقیق تر می باشد . ((9))0 < (20 می باشد اگر و فقط اگر (900 هم به عنوان کرلنه بالا و هم به عنوان کرلنه پایین در (260 باشد. گروه کامپیوتر ساختمانداده ها به نباری 7 صفحه: 27 

صفحه 28:
۴-۱ علامت گذاری مجانبی(6/ 0.6) 7 ‎iw (Asymptotic)‏ سم a,,>0 9 Aad =a, 7" +...+ ant a ‏اكر‎ ‏بنابراين (0)27©- (7)/خواهد بود‎ گروه کامپیوتر ساختمان‌داده ها به نباری ] صفحه: 28 

صفحه 29:
۴-۱ مثال(پیچیدگی جمع ماتریس ها) ۳ ‎Asymptotic Statement‏ ‎complexity‏ Void add (int a []JMAX- SIZE...) } @(rows) sint Ij @(rows.cols) For(i=0;i<rows ; i++) @(rows.cols) G+For[j=0 ; j<cols ; j اختمانداده هابه ‎Qty‏ صفحه: 29 

صفحه 30:
۵-۱روش های اندازه گیری زمان رویدادها در 7 دو روش متفاوت وجود دارد : :ف روش و مدل اول از ساعت (سسها) برای زمان بندی رویدادها استفاده می کند. این تابع . زمان تلف شده از آغاز برنامه به وسیله پردازنده را می دهد. برای زمان بندی یک رویداد دوبار از ساعت استفاده می شود. یک مرتبه در ابتدای رویداد و یک مرتبه در انتهای آن. ف روش یا مدل دوم از استفاده می کند. لین تلبع . زمان را بر حسب ثانیه به عنوان نوع پیش ساخته 4ج برمی گرداند. بر خلاف عه . اساه فقط یک پارامتر دارد که به وسیله آن موقعیتی را که زمان باید نگهداری شود . مشخص می کند. 

صفحه 31:
۵-۱ تولید داده های آزمایشی پرای ایجاد بدترین حالت اجرا 7 ایجاد داده های آزمایشی که منجر به بدترین حللت اجرا می شود . همیشه ساده نیست. 9 در بعضی از موارد لازم است که از یک برنامه کامپیوتری برای ایجاد بدتریت حالت استفاده می شود. 9 برای هر مجموعه مقادیر از صفات نمونه مورد نظر . یک داده آزمایشی تصادفی با عددی به اندازه کافی بزرگ ایجاد می کنیم زمان اجرای هر کدام از اين داده های آزمایشی به دست می آید گروه کامپیوتر ساختمان‌داده ها به یبای ] صفحه: 31 

صفحه 32:
فصل دوم ۰ آرایه ها در این فصل دانشجو با کاربرد موارد زیر آشنا خواهد شد: ‎all ©‏ ۳ ساختار نا 5 ۴ ماتریس اسپارس 8 رشته ساختمانداده هابه زباری 6 صفحه: 32 

صفحه 33:
فصل دوم ‎alt:‏ ها 9 ساختارها > آرایه مجموعه ای از زوج ها . شامل اندیس و مقدار است (<صلس . »طكح:>) . به ازاى هر انديس یک مقدار مربوط به آن اندیس وجود دارد که به زبان ریاضی آنرا تناظر یا انگاشت نامیده می شود. در رابطه با آرایه به دو عمل اساسی نیاز است : 

صفحه 34:
۱-۲ آرایه ها < تابع (ا [)2) :یک آرایه جدید تهی با طول مناسب را تولید می کند. تمتم مقادیر در ابتدا تعریف نشده اند. ‎Ke: Retrieve abi‏ آرايه ويى انديس رابه عنوان ورودى دريافت مى كند و يك مقدار مربوط به انديس را اكر انديس معتبر باشد برمیگرداند و گرنه یک خطا را بازمی گرداند. ‏تلبع و : برای وارد کردن زوج جدیدی شامل < اندیس, مقدار > به كار مى رود و آرايه اوليه افزايش يافته با زوج جديد.<مقدارءانديس > را بازمى كرداند. ‏گروه کامپیوتر ساختمان‌داده ها به یبال ] صفحه: 34 ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 35:
WY ‏آرایه ها‎ ۱-۲ آرایه در زبان © به صورت مثال در زیر آمده است : ‎int list [5]‏ C= در زبان 2) تمام آرایه ها از اندیس ۰ شروع می شوند. ساختمانداده ها به زباری ‏ صفحه: 35 

صفحه 36:
ساختارها 8 آرایه ها مجموع داده های از یک نوع می باشند. در 0 روش دیگری برای دسته بندی گروهی از داده وجود دارد . اين روش اجازه می دهد تا داده ها از انواع متفاوتی باشند. اين امکان را ‎ virwt‏ گویند كه مختصر جاص اح است. قا يى ساختار مجموعه اى از اقلام داده ها مى باشد كه هر قلم داده به وسيله نوع و نام آن مشخص كرديده است. | گروه کامپیوتر ساختمانداده هابه نبا إل عتما 

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

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

صفحه 39:
WY ۳ ‏ساختارهای خود ارجاعی‎ یک ساختار خودارجاعی ساختاری است که در آن یک جز پا بیشتر ۰ اشاره گری به خود آن می باشد. ساختارهای خود ارجاعی معمولا به روالهای مدیریت حافظه پویا احتیاج دارند (عص عصاهجم) تا به راحتى حافظه را گرفته و آزاد کنند. 

صفحه 40:
WY ساده ترین و متداول ترین نوع ساختمان داده ها . لیست های مرتب شده یا خطی هستند. ليست ها شامل اقلام داده په صول(بع617ر... 66171 ,وتعط) باشند. مثال : a * روزهای هفته ( شنبه ... جمعه ) ۳۹ Joe cere |} ‏گروه کامپیوتر‎ | 

صفحه 41:
اعمال صورت كرفته بر روى ليست ها 5 ‎lay &‏ كردن طول یک ليست ‏© خواندن اقلام داده يى ليست از جب به راست يا بر عكس ‏۶ بازیابی !امین عنصر از یک لیست (۰2<۰ > 4 ‏# تعویض یک قلم اطلاعاتی در !امین موقعیت یک لیست (۰< ۰ 5 4 ‏#۶ درج یک قلم داده جدید در !امین موقعیت یک ليست (20 ه > 4. ‏( اقلام داده ای که قبلابه صورت .... ۰+0 ! شماره گذاری شده لند به صورت) ه..... 6+ )+ در مى آيند) ‎Gio &‏ يك قلم اطلاعاتى از ‎١‏ امين موقعيت يك ليست ‎<2١(‏ > > 4 . اقلام داده , ).ءءء به اقلام داده با شماره ...1+0 تبدیل می شود. ‏كروه كامبيوتر اساعتبازد انف هيه زبار©) اك ‎ ‎ ‎ ‎ ‎ 

صفحه 42:
متداول ترین پیاده سازی . نمایش یک لیست مرتب شده به صورت یک آرلیه می باشد به نحوی که عنصر لیست 161۲ با اندیکس ! آرایه متناظر باشد. این مطلب یک نگاشت ترتیبی نامیده می شود. | FE Joe cere |} ‏گروه کامپیوتر‎ | 

صفحه 43:
WY ‏ماتریسسپلیس‎ ADT به طور کلی در ریاضیات . یک ماتریس شامل ۰۶ سطر و » ستون بوده و می تواند مانند شکل زير نمایش داده شود. &€ 9 -6۶ | 0 ربهر ‎QO 08 ©-‏ | 0 هر ‎٩ | 09 68- 0‏ ,سر © © 8 | 9 هر ‎rw F \ FO CP‏ ‏ميو هده ‎ ‎ 

صفحه 44:
1077 ماتریسسپایس در علوم کامپیوتر متداول ترین نمایش برای ماتریس آرایه دوبعدی است که به صورت [,0/000(_)00[000:00 نمایش داده می شود. هر عنصر ماتریس به صورت 0 نمایش داده می شود. ماتریسی که عناصر صفر ن زیاد بوده ماتریس اسپارس نامیده می شود. حدلقل اعمال ممکن شامل ایجاد. جمع ۰ ضرب و نرانهاده مانریس می باشد. | گروه کامپیوتر ساختمانداده هابه نبا إل | 

صفحه 45:
WY ‏ماتريسراسيايوس‎ 077 مى توان هر آرايه رابا استفاده از سه كلنه ذخيره نمود اين بدان معنا مى باشد كه مى توان يك آرايه از سه كانه ها را براى نمايش يك ماتريس اسيارس بيشنهاد كرد. ‎J‏ گروه کامپیوتر ‎J Os ob stor. J‏ مستا ‎ ‎ 

صفحه 46:
ترانهاده یک ماتریس برای پیدا نمودن ترانهاده یک ماتریس بلید جای سطرها و ستون ها را عوض کرد بدین مفهوم که هر عنصر |[ در ماتریس اولیه به عنص راط در ماتريس ترانهاده تبديل مى شود. ” الكوريتم زير براى بيدا كردن ترانهاده يك ماتريس ‎٠‏ الكوريتم مناسبى است : واد خ ‎Por dl ebwed‏ + حصله ‎phae ebwed <1. j‏ حصامس . | > مومحاد | گروه کامپیوتر ال ساختمانداده هب ‎JO‏ | 

صفحه 47:
ترانهاده یک ماتریس الگوریتم بیان شده نشان می دهد که ‎plod tab‏ عناصر در ستون ۰ را بيدا و آنها را در سطر ۰ ذخیره کرد همچنین تمام عناصر ستون ‎١‏ را بيدا و در سطر ۱ قرار داد و همین فر آیند را ادامه داد. از آنجا که ماتریس اولیه سطری بوده لذا ستون های داخل هر سطر از ماتریس ترانهاده نیز به صورت صعودی مرتب می شود. گروه کامپیوتر ساختمانداده ها به زبارن ‎Bh‏ صفحه: 47 

صفحه 48:
تحلیل ترانهاده ۳ تعیین زمان اجرای لین الگوریتم از آنجا که حلقه های تودرتوی ۳۲ عامل تعیین کننده می باشد . آسان است. حلقه ۳ خارجی اص.[0]0 مرتبه تکرار می شود که اص,[010 حاوی تعداد ستون های ماتریس اولیه است. علاوه بر لین . یک یک تکرار حلقه داخلی ۳۳ به زملنی برابر باصالسد[0/0 نیاز دارد که در اینجا , صالد[0/ تعداد عناصر در ماتریس اولیه است. بنابراین زمان کلی برای حلقه های تودرتوی 0 برابر با حاصل ضرب ستون ها در عناصر (5-طك./ح-) مى باشد. بنابراین زمان اجرا به صورت ۰ (حفسحاه ادم) خواهد بود. گروه کامپیوتر ساختمانداده ها به نبارل 8 صفحه: 48 

صفحه 49:
WY ‏ضرب ماتریس‎ با توجه به ماتریس های مشخص و معلوم 9 وظ) . فرض کنید که © یک ماتریس 7*7 و 0 یک ماتریس 77 باشد آنگاه ماتریس حاصل ضرب 00 دارای ابعاد 2 است و عنصر <ز> آن به صورت زیر تعریف مى شود : برای ۰< 0 > [ و ۰ < ۲ > [ اقلا نکته : حاصل ضرب دو ماتریس اسپارس ممکن است یک ماتریس اسپارس نباشد. 

صفحه 50:
روال1101101116 در روال الك ماتريس هاى 09 و©) را ضرب كرده و با توجه به توضیحات حاصل ضرب را در 0) قرار می دهیم. 0 ۵«) به عنولن‌ماتریس‌هایلسپایس‌به ترتیبدر آرلیه های 4 ۰۳ ) ذخیره می‌شوند ا گروه کامپیوتر }| ‎Joe cere‏ م 

صفحه 51:
نمایش آرایه های چند بعدی روش سطری دو راه متداول برای نمایش آرایه های چند بعدی وجود دارد : روش ستونی در روش سطری آرلیه های چند بعدی را به وسیله سطرهای آن ذخیره می کنیم. ‎er‏ آرلیه دو بعدی 0۳067[]110۳6نلن می دهد که دارای سط )11212 )1 ‎TOW, FOY,...TOW po.‏ به نحوى كه هر سطر ‎bb ee HABE alts‏ | گروه کامپیوتر }| ‎Joe cere‏ م 

صفحه 52:
نمایش آرایه های چند بعدی اگره آدرس ۸00 باشد. بنابراین آدرس ۱۰ +6 , [۸]۱[]0 0 خواهد بود. 8 برای نمایش یک ‎|Adppetluppeltuppegis, a. all‏ به عنوان ‎WAP BiaLT‏ با ابعاد در ‎UPPEESIDP Bs‏ ل كروه كامبيوتر _ألساختمانداده ماب نبا إل صفحه 32 ] 

صفحه 53:
نوع داده مجرد رشته ای(۸۳ ‎(STRING‏ از دیدگاه ۸4/27 یک رشته به ‎Bot yuo‏ ريف می گردد به نحوی که کارازلگرهای اخذ شده از مجموعه کاراکترهایزبان برنامه نویسی می باشد. اگر 0 باشد.5 یک رشته تهی می باشد. گروه کامپیوتر ساختمانداده ها به نبارل 8 صفحه: 53 

صفحه 54:
نوع داده مجرد رشته ای(۸ ‎(STRING‏ عملکردهای مناسب و مفیدی وجود دارد که می توان برای رشته ها تعریف کرد مانند : ایجاد یک رشته تهی جدید اندن یا نوشتن یک رشته ضمیمه کردن دو رشته به یکدیگر سس کپی کردن یک رشته مقایسه رشته ها درج كردن يك زير رشته به داخل رشته برداشتن یک زیر رشته از یک رشته مشخص مختص = = = ل ل ل ل 1 بيدا كردن يك الكو( حهح) يا عبارت در يك رشته 

صفحه 55:
نوع داده مجرد رشته ای(۸7 6117016) نحوه ذخیره سازی در حافظه : ‎char s[{] = {"dog’{ ;‏ ‎ s[2]‏ [5]1 [5]0 ‎q 2 d‏ لا ‎ ‎ ‎ ‎ ‎ ‏نمایش رشته در زبان 6 ‎J‏ گروه کامپیوتر ‎J Os ob stor. J‏ 5م ‎ ‎ ‎ ‎ 

صفحه 56:
مثال ۰ درج رشته ۳ می خواهیم رشته ا را در موقعیت رشته < جای دهیم : 2 ۱۱۱۸۰۱ ۰۱۱6۱ ° ‎-llo| t|u‏ : ۱ 5 02 |— 7ج ‎After‏ ‏۳۱۳۹ غلا مب موی ‎after‏ ۲ ‎str¢at| a ۳3[‏ اب مج ۷۱ ۱ ۶ 0۱ ۰1161111010۱8۱ گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 56 

صفحه 57:
(Pattern Matching), 3.U5 فرض كنيد که دو رشته داریم ۰ 2۷۱ ولج به نحوی ۳ یک الگو يا «طاه۲ بوده و باید در 2۳ پیدا شود. ساده ترین ‎Gly oly‏ تعیین اينکه آیا ۵ در رشته وجود دارد یا خیر . استفاده از تابع کتابخانه ای 2۲24 می باشد. با وجود اينکه 290 برای تطلبق عبارت مناسب به نظر می رسد . دو دلیل عمده برای نوشتن تابع تطابق الگو وجود دارد : ‎ali‏ فصو ‎ly‏ ) 0069). جدید بوده و ممکن است که در کامپایلر موجود نباشد. ‏چندین روش برای پیاده سازی تابع تطابق الگو وجود دارد. ‏گروه کامپیوتر ساختمانداده ها به نباری 7 صفحه: 57 ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 58:
c- غیر موثرترین روش . تست متوللی هر کاراکتر رشته تا زمان پیدا شدن الگو و یا رسیدن به انتهای رشته . می باشد. اگر ۲ در ود نباشد. این روش دارای زمان محاسباتی ۳(۰») خواهد بود که در آن " طول او طول 9۲۱ می باشد. | گروه کامپیوتر }| ‎Joe cere‏ منتها 

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

صفحه 60:
WY ‏فصل سوم : پشته و صف‎ پشته و صف . حالات خاصی از نوع داده عمومی یعنی لیست های مرتب شده , می باشند. پشته یک لیست مرتب شده ای است که جایگذاری و حذف از یک سمت آن که 9 (بالا) نامیده می شود , صورت می گيرد. "در يشته اى مانند,ق....,ر2 5 عنصاو بايبنى و عنصر بالاياقٌ مى باشد. | گروه کامپیوتر ال ساختمانداده هب نیال | تع 

صفحه 61:
*#*محدودیت کار با پشته ما را ملزم می کند که اگر عناصر »,2 رابه ترتیب به پشته اضافه کنیم . 2 اولین عنصری خواهد بود که که از پشته حذف می گردد. **از آنجا که آخرین عنصر وارده به پشته , اولین عنصر حذف شده از آن می باشد . پشته را به عنوان یک لیست ۲/۳0 (آخرین ورودی . آخرین خروجی ) می شناسیم. گروه کامپیوتر ساختمانداده ها به نبارل ۴ صفحه: 1 

صفحه 62:
‎ #‏ | 6۵8 | سا ‎0 0 ۳ top |D ‏بع‎ C |top |C c 3 8 ۱۴۰۵ 8 8 B B top A A A A A A ‏حذف و جایگذاری عناصر در یک پشته ‏| گروه کامپیوتر ال ساختمانداده هب ‎JO‏ ‎ ‎ ‎ ‎ ‎ 

صفحه 63:
5 ‏ساختار نوع داده مجرد پشته‎ 5 ructure ack is, fue 5: ‏نت‎ ordered list with zero or more elements. Silas tack Stack item — element .max Stack, size positive Sta reateS(max si Sti ick size)::= Creat an em stac se maxi eeu IsFull 1 ck.max_stack size Dumb er of elements‘in stat! return TRU. e 59 jume size is max_stack_size ax_stack_size) IsFu eh full else Insert ite! ag Fop of stack and return Boolean jean cea 5 ‏ی‎ 1 n turn max_s stack_size) El nant an re Em, erect return else rer ve and return the item on the top of the stack گروه کامپیوتر ساختمانداده ها به نباری 

صفحه 64:
پیاده سازی پشته راحت ترین روش پیاده سازی لین 902 . استفاده از یک آرایه ‎cue! Stack[MAX_STACK_SIZE] pli 4s 530 Ss‏ ‎aSla> (MAX STACK SIZE] s‏ تعداد عناصر آرلیه مى باشد. اولین یا پایین ترین عنصر پشته در[5]316]0 ذخیره . دومی در [6]1» و !امین عنصر در ‎Stack[i-1]‏ ذخیره می گردد.همراه با آرلیه . یک متغیر به نام 7 وجود دارد که به عنصر بالایی پشته اشاره می کند. در ابتدا به 9۳ مقدار ۱- داده می شود که نشان دهنده یک پشته خللی است. با این نمایش . می توانیم عملکردهای ساختار را به صورت زیر پیاده سازی کنیم : گروه کامپیوتر ساختمانداده ها به نبارل 8 صفحه: 64 

صفحه 65:
پیاده سازي پشته ۳ Stack CreatS(max_stack_size)::= #define MAX_STACK SIZE 100 /* maximume stack size*/ 3 3 typedef struct { int key; /* other fields*/ }yelement; Element stack [MAX_STACK_SIZE]; int top = -1; Boolean IsEmpty(Stack)::=top<0; BRR SAA CK siZehwlliStack)ie= top >= 

صفحه 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 ) { ‎the top element from the‏ را ‎if (* top == -1)‏ ‎tack t > /* ret eS a _empty (); /* returns an ‎return stack [( * top)--]; ‎} ‏| گروه کامپیوتر }| ‎Joe cere‏ صع ۳3 ‎ ‎ ‎ 

صفحه 68:
WY صف 22و صف یک لیست مرتب شده است که تمامی جایگذاری آن از یک سمت و تمام حذف های آن از سمت دیگر انجام می شود. درصف 2.۰.۰2۱ 2 شاصر اقتدا (۳۵) و دوه عنصر انتها (#) مى باشد و :1د كنار قرار داد ‎a<72-)‏ | گروه کامپیوتر }| ‎Joe cere‏ صعب | 

صفحه 69:
WY is ‏صف‎ محدودیت صف این است که ما ‎BOOM‏ را به ترتیب اضافه مى کنیم در حالی که 9 اولین عنصری است که حذف می شود. ‎rea‏ زم وهم ها مومهم ها ‎C c D‏ | ۲و6 ‎Bic ce‏ » م ۳63۳8 ‎front front front front‏ ‎A front| A A A B‏ ‏درج و حذف عناصر از یک صف ‏_ گروه کامپیوتر ساختمانداده ها به یبای ] صفحه: 69 ‎ ‎ ‎ ‎ ‎ ‎ 

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

صفحه 71:
WY ۱ ‏جايگذاري در صف‎ Noid addq ( int * rear « element item ) { /* add an item to the queue */ nt if (* rear ==MAX_QUEUE SIZE - queue_full(); retyrn; } queue[++* rear] = item; گروه کامپیوتر ساختمان‌داده ها به نباری ] صفحه: 71 

صفحه 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]; } | گروه کامپیوتر ال ساختمانداده هب ‎(acs JO‏ 

صفحه 73:
WY (MAZING) p> 9 ‏مساله مسیر پر پیچ‎ " بهترین راه نمایش مسیر فوق یک آرلیه دو بعدی است که صفرهای آن نشان دهنده پیچ و خم های مسیر می باشد. " يى مسير ير بيج و خم («2م) با ابعاد #۳ به یک آرایه (۵+)(۳+۲)_نیاز دارد. ورودی در موقعیت [۱[]1] و خروجی در موقعیت [][0]] می باشد. | گروه کامپیوتر ال ساختمانداده هب نیال | منت 

صفحه 74:
WY اندازه ‎pane Leal Ole} (are) pF 9 Sey seme‏ را تعیین می کند . از آنجا که هر موقعیت درون مسیر بیش از یک بار مشاهده نمی شود . بدترین حللت پیچیدگی الگوریتم به صورت + ‎est (Wp)‏ باشد به نحوى كه © و م۲ تعداد سطرها و ستون های مسیر است. | EE Joe cere |} ‏گروه کامپیوتر‎ | 

صفحه 75:
WY ‏ارزشیاپی عبارات‎ در هر زبان برنامه سازی برای ارزیاپی صحیح عبارات . به هر عملگر اولویتی نسبت می دهیم. حال در هر جفت پرانتز ؛ اول عملگرهایی که دارای اولویت بالاتر هستند ‏ ارزشیابی می شوند . | گروه کامپیوتر }| ‎Joe cere‏ تست 

صفحه 76:
/ اولویت عملگرها 7 1 شکل مقابل نشان دهنده اولویت ‎ae‏ ‏عملگرها در زبان ۲ می باشد. ‎wi‏ | گروه کامپیوتر }| ‎Joe cere‏ سحتتت| 

صفحه 77:
WY infix ‏روش‎ روش استاندارد نوشتن عبارات به عنوان ۳ معرفی و شناخته می شود چرا که در این روش عملگرهای دودویی را در بین دو عملوند قرار می دهیم. | گروه کامپیوتر ال ساختمانداده هب نیال | م 

صفحه 78:
نشانه گذاری ‎postfix‏ WY دراین روش هر عملگر بعد از عملوند های مربوطه ظاهر می شود Infix Fever a*b+5, Var(Ver) a*b/c cx(e-a)sx(a/(b-c+d))) a/b-c+d*e-a*c گروه کامپیوتر Postfix +۴۲ vab*5 Brey) ab*c swabc-d+/ea-*c ~xab/c-de*+ac 

صفحه 79:
خصوصیات. > 005 عبارات برای ارزیلبی از چپ به راست پویش می شوند. عملوندها تا مشاهده یک عملگر, داخل پشته قرار می گیرند. سپس تعداد لازم از عملوندها را از پشته خارج و پس از انجام عملکرد مربوطه . نتیجه را دوباره به داخل پشته منتقل می کنیم . لین کار را ادامه پیدا می کند تا به انتهای عبارت برسیم. | گروه کامپیوتر ال ساختمانداده هب ‎EE JO‏ | 

صفحه 80:
UY postfix 4, infix ‏الگوریتم تبدیل‎ می توان الگوریتمی برای تبدیل یک عبارت »۳ به و۳ به صورت زیر بیان نمود : ۱- پرانتزگذاری کامل عبارات ۲- انتقال همه عملگرهای دودویی به نحوی که با پرانتز بسته مربوطه سنمت رانت آن تعویض شوند ۳- حذف تمام پرانتزها | FEZ Joe cere |} ‏گروه کامپیوتر‎ | 

صفحه 81:
تبدیل عبارت ۲*ط0۴۳ به نشانه گذاری ۳۳۶۸ Token eos Top Output a a ab ab abc abe WY 

صفحه 82:
مثال تبدیل ٩*(۲)*ه‏ به نشانه گذاری ‎posPix‏ Token elo ‏سواه‎ C1 Stack 1 11 Top Output WY 

صفحه 83:
postfix ‏تحلیل‎ فرض كنيد تعداد نشلنه ها در عبارت باشد , برای خارج ساختن نشانه ها و انتقال آنها به خروجی نیاز به (0)0 می باشد. بنابراین بيجيدكى تابع »*#ومم به صورت (0)0 خواهد بود. | گروه کامپیوتر }| ‎Joe cere‏ مم 

صفحه 84:
فصل جهارم: ليست ها = آشنايى با اشاره كر ها 7 ليست ها و لییست حلقوی ۴ روابط هم ارزی 7 لیست پیوندی دوگانه 

صفحه 85:
فصل چهارم : لیستها ۱ ویژگی های نمایش ساختمان داده ها با استفاده از آرایه و نگاشت ترتیبی: خاصیت لین نحوه نملیش آن بود که عناصر پشت سرهم داده مقصود با فواصل ثابت ومعینی ذخیزه می شدند. بتابراین:: # گرا ‎LOG sigs yo Go pate gual‏ باشد. (1+1) امین عنصر. در نمایش حلقوی در موقعیت+(2 ‎Aes ( 9060606086‏ گرفت . # اكر بالاترین عنصر پشته در مکان ‎kdl‏ يايين ترين عنصر در مکان خواهد بود. ‎‘OP‏ LOGop- گروه کامپیوتر ساختمان‌داده ها به نباری ] صفحه: 85 

صفحه 86:
مشکلات نمایش ترتیبی ۱- حذف و درج عناصر در آرایه ها بسیار وقت گیر است وقتی‌دارلی‌چندین!_یستعرتبشده با طول‌هایم تفاوت 6 هستیم باذخیره کردن‌هر لیستهر آرلیه لعبا حداکثر اندازه , حافظه هدر می رود ۳- با نگهداری لیستها در یک آرایه . انتقال حجم زیادی از داده ها لازم است. | گروه کامپیوتر ال ساختمانداده هب نیال | م 

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

صفحه 88:
UY ‏اشاره گرها‎ مهمترین عملگرهای استفاده شده با نوع اشاره گر عبارتند از : © © عملگر آدرس © * عملكر غير رجوعى (وواصمحم ىواصلا عم مشسطم) te pit te" pt آنگاه !یک متفیر صحیح و ام یک اشاره گر به یک متغیر صحیح است. نه حامر ۷ آدرس ؛ را بركشت و به ان مقدار ام را نسبت مى دهد. 

صفحه 89:
خطر استفاده از اشاره گرها در هنگام برنامه نویسی به زبان 2) بهتر است که تمام اشاره گرهایی را که عملابه جایی اشاره نمی کنند را برابر مابل060) قرار دهیم. این عمل از تلاش برای دستیابی به قسمتی از حافظه که خارج از دامنه برنامه شما بوده و یا شامل اشاره گری به یک داده مقصود قابل دسترسی نیست . جلوگیری می کند. | گروه کامپیوتر ال ساختمانداده هب نیال | عتما 

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

صفحه 91:
استفاده از حافظه پویا( استفاده از 850) 3 هر زمان که نیاز به حافظه جدیدی باشد . می توان تابعی به نام -ط را فراخوانی و مقدار فضای لازم را درخواست کرد. اگر حافظه لازم وجود داشته باشد . اشاره گری به ابتدای ناحیه حافظه مورد نیاز بر گردانده می شود. زملنی که دیگر نیازی به آن حافظه نباشد . می توان ن رابا فراخوانی تابعی به ‎Pree pl‏ آزاد نمود. | گروه کامپیوتر ال ساختمانداده هب ‎FE JO‏ 

صفحه 92:
لیست های تک پیوندی ليست های پیوندی معمولا به وسیله گره هایی متوللی با اتصالاتی که به صورت فلش هایی نشان داده شده اند ارایه می گردند. از نام اشاره كر به اولين عنصر ليست به عنوان نام كل ليست استفاده مى شود. بنابراین لیست شکل زیر 28 نامیده می شود. | گروه کامپیوتر }| ‎Joe cere‏ م 

صفحه 93:
ليست هاى بيوندى روش معمول برای ۱ لیست پیوندی vat, ‘NULL هرد sat cat WY (۱) گره ها واقعا در مکانهای پشت سر هم حافظه قرار نمی گیرند (۲) موقعیت گره ها در اجراهای مختلف می تواند تغییر کند FEZ Joe cere |} ‏گروه کامپیوتر‎ | 

صفحه 94:
مثال مراحل درج کلمه ۳ بین لت و 9 به صورت زیر است : ۱- گره ای را که اخیرا استفاده نشده در نظر گرفته , فزض کنید که آدرس آن للحم باشد. ۲- فیلد داده این گره را برابر با 0 قرار دهيد ۲- فیلد اتصال ۸۹ را طوری تنظيم كنيد که به ادرسی که در فیلد اتصال گره حاوی ‏ می باشد. اشاره کند ۴- فیلد اتصالء گره حاوی ۱" را طوری تنظیم کنید که به ۵ اشاره کند. و گروه کامپیوتر WY 

صفحه 95:
(Cat 51s, mat ‏مثال(درج گره‎ نحوه تغییر لیست بعد از اضافه كردن 4 در شکل زیر نشان داده شده است : 

صفحه 96:
حذف ]102 از لیست برای انجام لین کار فقط لازم است که عنصر قبل از 4 یعنی ل را پیدا و فیلد اتصال آنرا طوری تنظیم کنیم که به گره ای اشاره کند که در حال حاضر اتصال كره 4 به ان اشاره دارد( شکل زیر ) f= NULL | گروه کامپیوتر ال ساختمانداده هب ‎FEZ JO‏ 

صفحه 97:
WY ‏امکانات لازم برای ایجاد لیست پیوندی‎ 9 مکانیزمی برای تعریف ساختار گره ها یعنی فیلدهایی که در گره وجود دارد 9 روشی برای ایجاد گره هایی که مورد نیاز می باشد 9 روشی برای آزاد کردن گره هایی که دیگر مورد نیاز نمی باشد | FE Joe cere |} ‏گروه کامپیوتر‎ | 

صفحه 98:
جاب يك ليست ۳ Void print_list (list_pointer ptr) print f (" The list contains: " ); for (; ptr; ptr = ptr -> link) print f (" %4d ۳ ۰ 0۲۲ - >data); print f ("\n" ); گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 98 

صفحه 99:
top 1 elemen_link front | elemen link انداده ها به زباری 

صفحه 100:
WY delete ‏تابع 200 و‎ تولبع له و صعط عناصری را به پشته اضافه و از آن حذف می كنند. كد کردن هر یک از این تولبع . کار ساده ای می باشد. در هر دو تلبع آدرس ۲ط رابه گونه ای تغییر می دهیم که به عنصر بالایی پشته اشاره کند. تابع له یک گره جدید به نام مسا ایجاد نموده . ‎tee‏ ‏را در فیلد داده و م9 را در فیلد اتصال قرار می دهد سپس متغير 7ط براى اشاره كردن به 677 تغيير مى كند گروه کامپیوتر ساختمانداده ها به نباری ‏ صفحه: 100 

صفحه 101:
تابع 06186 تلبع صعاط . عنصر را برگشت و 9۳۲ را عوض می کند تا به آدرسی که در فیلد اتصال ن قرار دارد , اشاره کند سپس گره حذف شده به حافظه سیستم بر گشت داده می شود. | گروه کامپیوتر ‎ob ttre‏ نبا سنج 202 | 

صفحه 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); } ۳ it it TE ‏امبیزترم 0 اف‎ 

صفحه 103:
حذف از یک پشته پيوندي 5 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 ; گروه کامپیوتر ساختمانداده ها به نباری ‏ صفحه: 103 

صفحه 104:
اضافه کردن گره اي به انتهاي یک صف پيوندي Void addq (queue pointer * front ٠ ueue_pointer *rear «efement item) 7 add an element tothe rear of the queue queue pointer femp = (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; كروه كامبيوتر | ساختمانداده هابه زبارل || صفحه. 104 

صفحه 105:
حذف از ابنداي یک صف پيوندي element deleteq (queue_pointer * front ) 1 delete an element from the queue */— queue pointer temp = * front ; element item ; if (IS EMPTY (* front )) { ۱ fprint? ( stderr «" The queue is 0 لك item = temp - >item * front = temp - > link ; كروه كامبيوتر | ساختؤ90 06 نونجم 105 

صفحه 106:
نمایش چند جمله ای ها به صورت لیست های تک پیوند: 3 در اينجا مى توان هر جمله رابه صورت يى كره نمايش داد. در اين ارتباط هر گره دارای سه فیلد برای نمایش ضریب . توان و اشاره گری به گره بعدی می باشد. a=3x4+2% +1 گروه کامپیوتر ] ساختمانداده ها به نباری ] صفحه: 106 

صفحه 107:
جمع چند جمله ای ۳ برای جمع دو چند جمله ای . ابتدا فرض می کنیم که هت و ۲ اشاره گری به ابتدای چند جمله ای ها می باشند. 8 اگر توان دو چند جمله ای با هم برایر باشد . ضرایب با هم جمع می شهند و گره جدیدی تشکیل می شود . همچنین اشاره گرها را به گره های بعدی در هو طحرکت می دهیم. 8 اگر توان چند جمله ای ه کمتر از توان متناظر در چند جمله ای ع باشد. آنگاه یک جمله شبیه به لین جمله ایجاد و آنرابه نتیجه . یعنی ‎od‏ اضافه می کنیم و اشاره گر رابه جمله بعدی در ۲ منتقل می کنیم. همين عمل را اكر ‎o> expo >b- > expo‏ باشد بر روی * انجام می دهیم . گروه کامپیوتر ساختمانداده ها به نبارل ] صفحه: 107 

صفحه 108:
WY ‏تحلیل جمع چند جمله ای ها‎ برای محاسبه زمان لازم اجرای جمع چند جمله ای . اولین نکته تعیین عملیاتی است که بر زمان اجرایی اثر می گذارد. @ جمع ضرایب برای این الگوریتم باید سه معیار در نظر گرفته شود ‎ :‏ © مقایسه توان ها ایجاد گره جدید برای 1 ” الگوریتم جمع چند جمله ای با فاکتور ثابت بهینه است. | گروه کامپیوتر ‎ob tuto‏ نبا سنج 208[ 

صفحه 109:
WY ‏رابطه هم ارزی‎ ‎abl,‏ = )59 هر مجموعه 69 رابطه هم ارزی گفته می شود اگر دارای خواص انعکاسی . تقارن و تعدی روی 2۵) باشد. ‎ie ‏" تساوی" (-). یک رابطه هم ارزی است زیرا : ‏(0) « < «لست ‏(6) 27 « تسصریح می‌کند که « 2 7 می‌ب‌اشد (9) 2 «و < 2 بر نتیجه می‌دهد که < < «لست ‏گروه کامپیوتر ] ساختمان‌داده ها به نباری ] صفحه: 109 ‎ ‎ ‎ ‎ 

صفحه 110:
الگوریتم تعیین کلاس های هم ارزی الگوریتم تعیین کلاس های هم ارزی , دو مرحله است : در مرحله اول . زوج های هم ارزی <4 (> . را خوانده و ذخیره می کند. در مرحله دوم از ‎٠‏ شروع کرده و تمام زوج های که به شکل < ۰ .> می باشد ( به نحوی که ۰ و در یک کلاس هم ارزی می باشند ) را پیدا می کند. 

صفحه 111:
WY ‏الگوریتم هم ارزی‎ بر اساس خاصیت تعدی همه مقادیر به شکل < ۰ ز > با ا در یک كلاس قرار مى كيرند. | كروه كامبيوتر [لساختمائداده هابه وبا إل صفح | 

صفحه 112:
نمایش ماتریس های اسپارس به وسیله لیست پیوندی ۳ در نمایش داده ها , هر سطر و ستون ماتریس اسپارس با یک لیست پیوندی حلقوی با گره لص ارایه می شود. هر گره دارای یک فیلد برچسب () خواهد بود که وجه تمایز بين گره های ل۲ و گره هایی که عناصر مخالف صفر را ذخیره می کنند . می باشد. 8 هر گره لصا دارای سه فیلد دیگر نیز می باشد : اوه تن بط 8 هر گره وارده دارای پنج فیلد دیگرمی باشد : ‎row‏ امد : موی ‎udu aright‏ گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 112 

صفحه 113:
WY ‏نمایش ماتریس های اسپارس به وسیله لیست پیوندی‎ 8 از فیلد سبط برای اشاره به عنصر مخالف صفر بعدی در همان ستون @ از فیلد ۲۲۸۷ برای اشاره به عنصر مخللف صفر بعدی در همان سطر استفاده می شود. هر كره لا در سه ليست قرار مى كيرد : #" ليست سطرها # لیست ستون ها 8 لیست گره های ‎head‏ گروه کامپیوتر ‏ ساختمانداده هابه نباری ] صفحه: 113 

صفحه 114:
UY ‏نمایش ماتریس های اسپارس به وسیله لیست پیوندی‎ اگر بخواهيم یک ماتریس اسپارس عامه_ممه.عصص_سم با عسط_مسه عنصر مخللف صفر را نمایش دهیم . تعداد گره ها »هم الوص طا_جصسم + ( طاود_جصسم: عبو_مسم ) خواهد بود. ] ete Jt biol. ‏گروه کامپیوتر‎ | 

صفحه 115:
لیست های پیوندی دوگانه لیست های تک پیوندی تنها بعضی از مشکلات را حل می کند چرا که فقط به راحتی می توانیم در جهت پیوندها حر کت کنیم. فرض کنید که به یک گره مشخص مانند ۳#. اشاره کنیم و بخواهیم گره قبل از 2۷ را پیدا کنیم . تنها راه یافتن گره ماقبل 28 پیمایش از ابتدای لیست می باشد. گروه کامپیوتر ‏ ساختمانداده هابه زباری ] صفحه: 115 

صفحه 116:
WY ‏لیست های پیوندی دوگانه‎ یک گره در یک لیست پیوندی دوگانه حداقل دارای سه فیلد می باشد : فیلد ول فیلد 0 (اشاره گر به چپ ) ۵ فیلد ۷۷۰( اشاره گر به راست ) گروه کامپیوتر ‏ )| ساختمانداده هابه نباری آ صفحه. 116 

صفحه 117:
UY Is ‏ليست هاى بيوندى دوگانه‎ 2. یک لیست پیوندی دوگانه به دو صورت است ۰ ۲ * حلقوی لصا ‎llink item‏ _- . عير حلقوی Head Node 0 | آ cS لیست پیوندی دوگانه حلقوی با گره اج درج و حذف از یک لیست پیوندی دوگانه بسیار ساده می باشد. 

صفحه 118:
درج دریک لیست پيوندي دوگانه حلقوي وه ‎Void dinsert ( node_pointer node‏ ‎node_pointer newnode )‏ { /* insert newnode to the right of node */ newnode-> Ilink = node ; newnode-> Ilink = node-> r link ; node -> r link -> | link = newnode; node -> r link = newnode ; گروه کامپیوتر ساختمان‌داده ها به زباره) || صفحه: 118 

صفحه 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 -> | link - > r link = deleted - < ۶ deleted -> r link - > 1 link = deleted - >I link; ساختمان‌داده ها به نباری 

صفحه 120:
ایی با درخت "" درخت های دودویی © پیمایش درختان 

صفحه 121:
WY ws yo: ‏فصل پنجم‎ ee ساختار درختی یعنی مجموعه داده های سازماندهی شده ای که عناصر اطلاعاتی شان به وسیله انشعاباتی با هم رابطه داشته باشند. گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 121 

صفحه 122:
مفهوم درخت درخت مجموعه محدودی از یک یا چند گره به صورت زیر می باشد : ۲ دارای گره خاصی به نام ريشه باشد. ‎Bl‏ بقیه گره هابه 0 2 ۰" مجموعه مجزا «- للم شده که هر یک از لين مجموعه ها خود يى درخت هستند. ‎Ep‏ درجائان ريشه ناميده مى شوند. ‎| 222 ote J Oty bso 7۳7 ‏ا‎ ‎ ‎ ‎ ‎ 

صفحه 123:
6 وللا 0.0 0)لست ۰0.600 0) همزادند گروه کامپیوتر . | ساختمانداده ها به نباری ‎amino‏ 123 

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

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

صفحه 126:
یک راه نمايش درخت . استفاده از لیست است . شکل ۵-۱ را می توان به صورت زیر نشان داد : (A(B(E(K .L).F).C(G).D(H(M).1J))) گروه کامپیوتر ] ساختمان‌داده هابه نباری ‏ صفحه: 126 

صفحه 127:
نمایش لیست ممکن برای درختان WY شکل زیر یک ساختار ممکن برای نمایش لیست را نشان می دهد : data link 1 link 2 ساختمانداده ها بسه ‎Qu‏ Link n 

صفحه 128:
UY ‏نمایش دودویی یک درخت‎ برای نمایش درختان دودویی . دقیقا نیاز به دو اتصال یا اشاره گر به ازای هر گره است. Data right sibling left child [228 te J ‏گروه کامپیوتر اس اندادد هاب نبا‎ J 

صفحه 129:
۲-۵ درخت های دودویی ۳ => یک درخت دودویی یا تهی است یا حاوی مجموعه ای محدود از گره ها شامل یک ریشه و دو زير درخت دودویی است. این درخت ها زیر درخت های چپ و راست نامیده می شوند. ** مشخصه اصلی یک درخت دودهیی بدین شکل است که هر گره آن حداکثر دو انشعاب دارد یعنی گره هایی که درجه ای بیشتر از دو نداشته باشند. * برای درخت های دودویی زیر درخت سمت چپ و راست با یکدیگر متمایز است. 

صفحه 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 Bina&y_tree. functions : for all bt« btl«bt2 BinTree «item element BinTree Create() Boolean |sEmpty (bt) BinTree MakeBT(bt1 « item « bt 2) [poeBipdiee LAID cos | 

صفحه 131:
UY ‏تفاوت درخت عادی با درخت دودویی‎ ۲-۵ © در هیچ درخت عادی صفر گره وجود ندارد . اما درخت دودویی تهی وجود دارد. در یک درخت دودویی ترتیب فرزندان دارای اهمیت بوده در حالی که در درخت عادی به این صورت نیست. | 132 ‏گروه کامپیوتر اس اندادد ماب نبا ]رصن‎ J 

صفحه 132:
۲-۵ خواص درختان دودویی * حداکثر تعداد گره ها در سطح !ام یک درخت دودویی است :4 ۰12 " حداکثر تعداد گره ها در یک درخت دودویی به عمق ۰ است . 4 2 1 

صفحه 133:
۲-۵ خواص درختان دودویی برای هر درخت دودويى غير تهى مانند 7 . اگر 0تعداد گره های پایانی و تعدولگره های درجه ۲ باشد . آنگاه خواهیم داشت : =n, +1 

صفحه 134:
WY ‏خواص درختان دودویی‎ ۲-۵ یک درخت دودویی پر به عمق ۰ یک درخت دودویی است که دارای گره باشد 0 2 . 8 یک درخت دودویی با ه گره و عمق ۲ کامل است . اگر و تنها اگر گره هایش مطابق با گره های شماره گذاری شده در یک درخت دودویی پر به عمق ۲ باشد. | كروه كامبيوتر ‎bso‏ نبا إل صفحه 234 | 

صفحه 135:
WY ‏نمایش درخت دودویی‎ ۲-۵ نمایش آرایه نمایش درخت دودویی به دو صورت است : نمايش ليست 

صفحه 136:
WY ‏نمایش آرایه‎ ۲-۵ شیوه شماره گذاری ارایه شده در شکل زیر . اولین نمایش یک درخت دودویی در حافظه را مطرح و پيشنهاد می کند . از آنجایی که گره ها از ۱ تا » شماره گذاری شده لند . یک آرلیه یک بعدی می تواند برای ذخیره سازی گره ها استفاده شود . گروه کامپیوتر ] ساختمانداده ها به نباری 8 صفحه: 136 

صفحه 137:
WY ‏نمایش آرایه‎ 2-5 الما ام ‎Pl‏ ‏عا كا ع 6 ‎el‏ ‎rl‏ ‏ام ‏6 نمایش آرایه اي درخت دودويي. 

صفحه 138:
۲-۵ نمایش ‎abt‏ ‏اكثر يى درخت دودويى كامل با ع كره ( يعنى ‎=llog a1‏ ترتیب بالا تعریف شده باشد . آنگاه براى هر كره با انديس / و 2 1 7 20 , داریم (۱) اگر #0 . آنگاه پدر !در [60/] است . اگر ۰۱ ۱20 ريشه است و پدری نخواهد داشت. (۲) اگرهک9 . آنگاه فرزند چپ !در 6 است. اگر 0<۰ . آنگاه ۱ فرزند چپ ندارد. (۳) اگر 6۱۲5۰ . آنگاه فرزند راست ! در ۱۷۲۵ است. اگر 6۳۲<۰. آنگاه ! فرزند راست ندارد ساختمانداده ها به نباری ۴ صفحه. 138 گروه کامپیوتر 

صفحه 139:
UY ‏نمایش آرایه‎ ۲-۵ 2۴-1 7 در بدترین حالت . یک درخت مورب به عمق .به محل و موقعیت نیاز دارد که از اين مقدار, فقط ۲ محل اشغال می شود. گروه کامپیوتر ساختمان‌داده ها به نباری ‏ صفحه: 139 

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

صفحه 141:
١ ‏نمايش ليست بيوندى‎ ١-0 با اين روش هر كره سه فيلد خواهد داشت ‎٠‏ ‎left_child .data . right_child‏ که در زبان 6 به شرح زیر تعریف می شوند : typedef struct node *tree_pointer ; typedef struct node { int data ; tree_pointer left_child . right_child ; 1 گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 141 

صفحه 142:
‎١-0‏ نمايش ليست بيوندى ‎right_child | aata | left_child ‏بخ‎ ‎PL cht ‏لاس مزر‎ ‏نمایش یک گره درخت دودویی ‎ ‎ ‎ ‎ ‎ 

صفحه 143:
۲-۵ پیمایش درخت دودویی به هنگام پیملیش یک درخت دودویی .با هر گره و زیردرختلنش به طرز مشابهی رفتار کنیم. اگر ‎CL‏ ۰۷ 8 جه ترتیب حرکت به چپ . ملاقات کردن یک گره ( برای مثال . چاپ فیلد داده آن گره) و حرکت به راست باشد. آنگاه شش تر کیب ممکن برای پیملیش یک درخت خواهیم داشت : RLV .RVL.VRL.VLR .LRV .LVR گروه کامپیوتر ساختمازداده ها به زباره) || صفحه: 143 

صفحه 144:
۲-۵ پیمایش درخت دودویی مر اگر تنها حالتی را انتخاب کنیم که ابتدا به سمت جب و بعد به ‎Cal Cros‏ ۱ خواهیم داشت. لین سه حللت رابا توجه به موقعیت ۷ نسبت به ا ‎aR >»‏ ترتیب ۰۱۳۵۲06۲ 0۵5۵۲06۲ : ۳۲۵۵۲۵۲ می نامیم. كروه كامبيوتر ساختمازدادم ها به زباره) || صفحه: 144 

صفحه 145:
۲-۵ پیمایش درخت دودویی در بیش 207107۲ یک گره موقعی ملاقات و جاب مى شود که زیردرختان چپ و راست آن قبلا ملاقات شده باشند. © در بيمايضش ‎SG. preorder‏ گره قبل از پیمایش زیردرختان چپ و راست . ملاقات می گردد. گروه کامپیوتر ‏ ساختمانداده هابه نباری ] صفحه: 145 

صفحه 146:
WY ‏پیمایش درخت دودویی‎ ۲-۵ درخت زیر حاوی یک عبارت ریاضی است ‎A/B*C*D*+E‏ مک درخت دودویی برای یک عبارت محاسباتی [246 se Qs ‏گروه کامپیوتر اس اندادد ماب‎ J 

صفحه 147:
۲-۵ پیمایش 1۳001۳06۲ 5 هنگامی که این پیمایش انتخاب می شود , حر کت به سمت پایین به طرف چپ انجام می شود و اين عمل تا آخرین گره صورت می گیرد سپس می توان گره را بازیلبی کرد و بعد به سمت راست رفته و به همین ترتیب کار را ادامه پیدا می کند. این متناظر با شکل 10۴32 یک عبارت است. گروه کامپیوتر ‏ ساختمازداده هابه نباری | صفحه: 147 

صفحه 148:
WY ۰ ‏پیمایش 120۲016۲آیک درخت دودويي‎ 3-5 Vide inorder (tree_pointer ptr) /* inorder tree traversal */ if (ptr) { inorder ( ptr -> left_child ); printf (“ %d” .ptr -> data ); inorder (ptr -> right_child); گروه کامپیوتر ساختمازداده ها به زباره) || صفحه: 148 

صفحه 149:
۲-۵ پیمایش 1۳۳۲۵0۲06۲ 5 تلبع 0۲۵0۵۲۵6۲] حاوی دستورات لازم برای شکل دوم پیمایش است. بر اساس این پیمایش . گره را ابتدا بازیابی و ملاقات نموده و سپس انشعابات چپ را دنبال و تمام گره ها را بازیابی می کنیم. اين فرآیند ادامه پیدا می کند تابه یک گره تهی برسیم. در لین نقطه . به نزدیکترین جدی که دارای یک فرزند راست باشد مراجعه و با اين گره شروع خواهیم نمود. گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 149 

صفحه 150:
۲-۵ پیمایش 1۳۳۲۵0۲06۲ با پیمایش ۲۵۵۲۵6۲ گره های درخت زیر خروجی به شك زیر خواهند داشت : + * * ۸۵ 8 DE اين به شکل یک عبارت ۲6۵32 است. گروه کامپیوتر ‏ ساختمانداده هابه نباری ] صفحه: 150 

صفحه 151:
۲-۵ پیمایش ۳۲60۲06۲ یک درخت دودویی 7 Vide preorder (tree_pointer ptr ) /* preorder tree traversal */ { if (ptr) { printf (“ %d” .ptr -> data ); preorder ( ptr -> left_child ); preorder (ptr -> right_child); گروه کامپیوتر ساختمانداده ها به نباری ‏ صفحه: 151 

صفحه 152:
۲-۵ پیمایش 1۳0510۲06۲ لین پیمایش دو فرزند یک گره را قبل از بازیلبی آن گره ملاقات و چاپ می کند. این مساله بدین منهوم است که فرزندان یک گره قبل از خود آن گره بازیایی می گردد. [152 ote J ‏نبا‎ be tuto ‏گروه کامپیوتر‎ | 

صفحه 153:
۲-۵ پیمایش 1۳0510۲06۲ خروجی حاصل از پیملیش 050۲06۲ شکل زیر به صورت زیر است : ==) AB/C*D*E + این خروجی مانند یک عبارت 051۴2 است. گروه کامپیوتر ساختمان‌داده ها به نباری 7 صفحه: 153 

صفحه 154:
۳-۵ پیمایش 1100۳0167 غیرباز گشتی Void iter_pointer (tree_pointer node ) int top = -1; /* initialize stack */ ‏رعو أممجقة رمم‎ stack ۴0۲ )۶:( » >left chilafor G node ; node = - stack */ add ( &top « node ); /* add to stacknode = delete (&top); /*delete from stack*/ if (! Node) break ; /* empty printf (“ %d”: node-> data ) ; node = node -> right_child; 2) گروه کامپیوتر ساختمان‌داده ها به نباری ‎٩‏ صفحه: 2 

صفحه 155:
۳-۵ پیمایش 11001016۲ غیرباز گشتی ۳ حليل 1110151612 : فرض كنيد تعداد كره هاى درخت »" باشد . اگر عمل 66۲_1۳0۲۳06۲ را در نظر بگیریم . مشاهده می شود که هر گره درخت فقط یک بار در پشته قرار گرفته و يا از آن خارج می شود. بنابراین اگر تعداد گره های درخت » باشد . پیچیدگی زمان تلبع برابر با (0)13 مى باشد. حافظه مورد نیاز برابر با عمق درخت است که مساوی با (0۵)۳0 می باشد. گروه کامپیوتر ساختمانداده ها به نباری ‏ صفحه: 155 

صفحه 156:
۲-۵ پیمایش ترتیب سطحی 5 پیملیش ‎inorder .preorder .postorder (sla‏ 4 به صورت بازگشت پذیری نوشته یابه صورت غیرباز گشتی . همگی نیازمند پشته می باشند. اين پیمایش . ترتیب سطحی . ابتدا ريشه را بازیلبی . سپس فرزند جب ريشه وبه دنبال آن فرزند راست ریشه بازیلبی می گردد. اين شیوه با بازیلبی از گره منتهی الیه سمت جب به سمت راست هر سطح جدید تکرار می گردد. این پیمایش از صف استفاده می کند. گروه کامپیوتر ساختمازداده ها به زباره) || صفحه: 156 

صفحه 157:
W ‏پیمایش ترتیب سطحی‎ ۳-۵ پیمایش ترتیب سطحی درخت زیر به صورت زیر است : om + ‏عم‎ D/C AB گروه کامپیوتر ] ساختمانداده ها به نباری ] صفحه: 157 

صفحه 158:
WY ‏اعمال مفید بر روی درختان دودوبی‎ ۴-۵ Satisfiability Ju. -y | كروه كامبيوتر [لساختمانداده هابه وبا إل صفحه 228[ 

صفحه 159:
۵-۵ درختان نخی دودویی ۳ تعداد اتصالات تهی در یک درخت دودویی بیشتر از تعداد اشاره گرهای غیرتهی است. در یک درخت دودویی تعداد 0 + > اتصال از کل اتصالات آن یعنی ۰ ۰ تهی است. یک راه برای به کارگیری این اتصالات توسط پرلین و تورنتن پيشنهاد شد. راه حل لین بود که از اتصالات تهی برای ارتباط با دیگر گره های یک درخت استفاده شود که در اين صورت درخت را درت نب مى نامند. | كروه كامبيوتر | كه اندادد هاب ‎ete J Oy‏ 239 | 

صفحه 160:
۵-۵ درختان نخی دودویی ۳ صالات نخ قو بر استفاده می شو \( اگر ۱6۲۲_110 ‎ptr->‏ تهی باشد . آن را طوری تغییر می دهیم که به گره ای که در پیمایش 180۲06۲ قبل از 0۳ قرار دارد . اشاره کند. ۲ اگر ۲۱9۳۲۱0 <-۲۲ تهی باشد . آن را طوری تغییر می دهیم که به گره ای که در پیملیش 10۳06۲ بعد از 0۷۳ قرار دارد . اشاره کند. گروه کامپیوتر ساختمانداده ها به نباری ‏ صفحه: 160 

صفحه 161:
۵-۵ درختان نخی دودویی \ هنگامی که درختی را در حافظه نملیش می دهیم . بایستی بتوانیم بين اتصالات نخی و واقعی تفاوتی قایل شویم. این کار را با افزودن دو فیلد اضافی به هر گره انجام می دهیم که آنها را ‎pul right_thread .left_thread‏ گروه کامپیوتر ساختمان‌داده ها به نباری 7 صفحه: 161 

صفحه 162:
WY ۵-۵ درختان نخی دودویی 

صفحه 163:
۵-۵ پیمایش 11201۳06۲ یک درخت نخی -دودویی برای هر گره مانند 0۳ . در یک درخت دودویی . چنانچه ۴۴ 2 ۲۱۲۵۵0 _۲۱0۳۲<-0]۲ باشد . طبق تعریف ‎Ptr cay oF‏ در پیمایش ‎inorder . ptr-‏ > ۳۱< می باشد . در غیر لین صورت گره بعدی ۴ با پایین رفتن روی مسیر فرزندان جب 6617 از طرف فرزند سمت راست 0۲ تا وقتی که به گره ای با وضعیت ‎paw left_thread = TRUE‏ « تعیین می شود . گروه کامپیوتر ساختمانداده ها به نبارل ‏ صفحه: 163 

صفحه 164:
۵-۵ پیمایش 11201۳06۲ یک درخت نخی -دودویی ‎INSUCC al‏ بدون استفاده از پشته , گره بعدی در پیمایش ‎inorder‏ را در یک درخت نخی دودویی پیدا می کند. ‏براى بيمايش 10۲016۲ می توانیم با فراخوانی مکرر ۲ تمام گره ها را بازیابی کنیم . ‏گروه کامپیوتر ساختمانداده ها به نبارل 8 صفحه: 164 ‎ ‎ ‎ ‎ ‎ 

صفحه 165:
۵-۵ پیمایش 11201۳06۲ یک درخت نخی i inatice ge HPSSSSURSMES, tree) insu { Gfindadba bnenig' eeasapsor of tree in threaded_pointer temp ; temp = tree -> right_child ; if (! Tree -> right_thread) while (! temp -> left_thread) > = ‎left_child ; temp femp‏ ‎return temp ;‏ بيدا نمودن كره بعد . يى كره خاص در پیمایش 180۳86۲ } گروه کامپیوتر ساختمانداده ها به نبارل ‏ صفحه: 165 

صفحه 166:
۵-۵ پیمایش 110010161 یک درخت نخی ‎Ze‏ ‏-دودویی Void tinorder (threaded_pointer tree) { 1 1 fe ie verse the threaded binary tree threaded_pointer temp = tree ; for(;;) 1 temp = insucc (temp) ; if (temp = tree ) break ; printf (“ % 3c” «temp -> data ) ; گروه کامپیوتر ساختمانداده ها به نبارل 8 صفحه: 166 

صفحه 167:
6-6 درج یک گره به داخل درخت نخی دودویی فرض كنيد داراى كرهى به نام ‎parent‏ هستيم كه داراى زیردرخت راست تهی می باشد . آنگاه ملیل هستیم ۵ را به عنوان فرزند راست ‎Parent‏ درج کنیم . برای انجام این کار بايد : ‎FLASH ,1_. |, parent->right_thread(1)‏ قرار دهيد ‎child-> right_thread , child-> left_thread (ry)‏ را ‎TRUE 1‏ 1,3 دهید . ‎4S su pak 5 y5b |, Child-> left_child (¥)‏ به3۲610] اشاره کند. ‎parent->right_child ,|, 1, child-> right_child (F) ‏قرار دهید.‎ ‎ar ight_child(5) rent: ‏رود‎ hild ‎a, ‎ ‎ ‎ ‎ ‎ 

صفحه 168:
UY 7 ‏درج یک گره به داخل درخت نخی دودویی‎ 6-6 در شکل زیر 0,5 ‎D‏ را به عنوان فرزند راست كره 8 جايكذارى می کنیم : ‘child گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 168 

صفحه 169:
۶-۵ نوع داده مجرد ( (۵21هرم ۳ ‎MN tree‏ درختی‌لستکه مقدار کلید هر گره آن‌کمتر از مقادیر کلیدهایف رزندالنشنباشد 2520 6۶۱5(26 ی کدرختدودهییک امل‌لستکه ی ۲036 6 نیز می‌ب‌اشد ‎niin tree‏ درختی‌لسنکه مقدار کلید هر گره آن‌بیشتر از مقادیر کلیدهایف رزندالنشنباشد 12810 1111 یکدیخندودیییکامللستکه در ولقع یک 6۵ ۲۲ می‌ب‌اشد _ گروه کامپیوتر ساختمان‌داده ها به نباری ‏ صفحه: 169 

صفحه 170:
min heap , max heap 3! Jt 5-4 گروه کامپیوتر |( ساختمازدادمها به زباره) || صفحه: 170 

صفحه 171:
WY 1630 ‏اعمال اساسی پر روی‎ ۶-۵ ایجاد یک هرم(0620) تهی 8 جایگذاری عنصر جدید به هرم (0680) 8 حذف بزر گترین عنصر از هرم (0630) | 272 rte Jt blot 7۳7 ‏ا‎ 

صفحه 172:
۶-۵ صف اولویت غالبا هرم ها برای پیاده سازی صف اولویت ها استفاده می شوند. در صف اولویت ها عنصری که دارای بالاترین ( یا پایین ترین ) اولویت هست , حذف ‎ge‏ شود. * آرایه ساده ترین نمایش برای یک صف اولویت می باشد. گروه کامپیوتر »ال ساختمانداده هابه نباری آأ صفحه. 172 

صفحه 173:
۶-۵ نمایش های صف اولویت ‎Insertion _| Representation‏ ‎Unordered array‏ 90 ‎eq) Unordered‏ ‎linked list‏ ‎TS | storea MOG‏ ‎om) Stored linked‏ list Max heap 5S WY Deletion eM 96۰ ea) 80 

صفحه 174:
ب - محل اولیه گره جدید اضافه کردن گره جدید در هر موقعیت دیگری ,تعریف 0630 را نقض می کند زیرا نتیجه یک درخت دودویی کامل نخواهد بود. 

صفحه 175:
۳ 1/1232 1۳630 ‏درج عنصر به یک‎ ۶-۵ vei insert_max_heap ( element item ۴۲ 00-06 > Anto a max heap of int i; if (HEAP_FULL(*n) { full .\n”) ; .fprint f (stderr «“ The heap is exit (1); } i= ++ (*n); heap whitey 11 i != 1) && (item.key > heap [i] = heap[i/2] ; i/=2; 7 گروه کامپیوتر ساختمانداده ها به نبالل 8 صفحه: 175( 

صفحه 176:
WY insert_max_heap @l Jos $-d از آنجا که ‎lls Abb Qo pais bl Gul 2559 Sheu‏ ارتفاع ‏ می )92| لدین معنی می باشد كه حلقهة ‎while‏ ‏به ميزان تکرار شود.ناَو)پیچید گی تابع درج برابر مى باشد. ‎n)‏ 0009 اساختمازداده ها به زباره) || صفحه؛ 176 گروه کامپیوتر 

صفحه 177:
۶-۵ حذف عنصری از ۲۲6۵0 ۷127[ هنگامی که عنصری از 1۱630 ۲۲۱8 حذف می شود . آن را از ريشه درخت 0630 می گیریم. گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 177 

صفحه 178:
UY delete_max_heap at Jos ۶-۵ ۴ پیچید گی حذف برابر(2 مع چا 'آ زمان حذف یک عنصر دلخواه از درخت با " عنصر . برابر (0)) می باشد. گروه کامپیوتر |( ساختمانداده هابه نباری ‎trio‏ 178 

صفحه 179:
۷-۵ درختان جستجوى دودويى د یک درخت جستجوی یک درخت دودویی است که ممکن است تهی باشد. اگر درخت تهی نباشد خصوصیات زیر را بر آورده می کند : & هر عنصر دارای یک کلید است و دو عنصر نباید دارای کلید یکسان باشند . در واقع کلیدها منحصر به فردند. © کلیدهای واقع در زیردرخت غیرتهی چپ باید کمتر از مقدار کلید واقع در ريشه زیردرخت راست باشد. & کلیدهای واقع در زیردرخت غیرتهی راست بلید بزرگتر از مقدار کلید واقع در ريشه زیردرخت چپ باشد. #زیردرختان چپ و راست نیز خود درختان جستجوی دودویی میباشند. گروه کامپیوتر ساختمان‌داده ها به نباری ‏ صفحه: 179 

صفحه 180:
۷-۵ درختان جستجوی دودویی ساختمانداده هابه نبا ‎rio‏ 180 

صفحه 181:
۷-۵ جستجوی یک درخت دودویی ۳ فرض کنید خواسته باشیم دنبال عنصری با کلید 66۷ بگردیم. ابتدا از ريشه (۳۵۵۸) شروع می کنیم . اگر ريشه تهی باشد , درخت جستجو فاقد هر عنصری بوده و جستجو ناموفق خواهد بود. در غير این صورت 6۷>آرا با با مقدار کلید ريشه مقایسه کرده : ‎lf‏ اگر 16۷ کمتر از مقدار کلید ريشه باشد . هیچ عنصری در زیردرخت راست وجود ندارد که دارای کلیدی برابر 66۷ باشد . بنابراین زیردرخت چپ ريشه را جستجو می کنیم. ‏اگر 6۷ بزرگتر از مقدار کلید ريشه باشد . زیردرخت راست را جستجو می کنیم. ‏گروه کامپیوتر ساختمانداده ها به نبارل ‏ صفحه: 181 ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 182:
search ‏تحلیل‎ ۷-۵ اگر 0 ارتفاع یا عمق یک درخت جستجوی دودویی باشد . عمل جستجو را در مدت (0)11 انجام مى شود. گروه کامپیوتر .| ساختماندادد هابه زباری ] صفحه: 182 

صفحه 183:
۷-۵ درج عنصری به داخل درخت جستجوی دودویی ‏ برای درج عنصر جدیدی به نام 66۷ . ابتدا بايد مشخص نمود که آیا کلید با عناصر موجود متفاوت است یا خیر. برای انجام این کار بايد درخت را جستجو کرد. اگرجستجو ناموفق باشد . عنصر را در محلی که جستجو خاتمه پیدا نموده است . درج می کنیم. گروه کامپیوتر ساختمان‌داده ها به نباری ‏ صفحه: 183 

صفحه 184:
كروه كامبيوتر ساختمازداده ها به زباره) || صفحه: 184 

صفحه 185:
UY ۱ 10606171 8006 ‏تحلیل‎ ۷-۵ زمان لازم برای جستجوی ۲۱01۲۷ در یک درخت برابر (0)10 می باشد به نحوی که 9 برابر با عمق یا ارتفاع درخت است. بقیه الگوریتم نیاز به زمان (0)1 دارد. بنابراین زمان کل مورد نیاز 11256111006 برابر با (12) © مى باشد. كروه كامبيوتر ساختمازداده ها به زباره) || صفحه: 185 

صفحه 186:
UY 129292 ‏حذف عنصری از درخت جستجوی‎ ۷-۵ برای حذف ۳۵ از درخت زیر باید فیلد فرزند چپ وللد این گروه ‎NULL ,1, ۳‏ قرار داده و گره را آزاد نمود : گروه کامپیوتر ] ساختمانداده ها به نباری ‏ صفحه: 186 

صفحه 187:
UY 129292 ‏حذف عنصری از درخت جستجوی‎ ۷-۵ زملنی که یک گره برگ با دو فرزند حذف می شوند . گره را با بزرگترین عنصر در زیر درخت چپ و یا کوچکترین عنصر در زیردرخت راست آن گره جایگزین و تعویض کرد. عمل حذف در زمان (0)19 انجام مى كيرد ؛ به نحوى كه ‎1١‏ ‏عمق درخت مى باشد | گروه کامپیوتر ‎bso.‏ نبا سنج 257 | 

صفحه 188:
۷-۵ درختان جستجوی متعادل درختان جستجو با بیشترین عمق (1 [#106لر)ختان جستجوی متعادل نامیده می شوند. درختان جستجوی متعادلی وجود دارند که عمل جستجو , درج و حذف را در زمان ()0۵ ممکن می سازند از جمله درختان ‎red_black .2-3 .AVL‏ گروه کامپیوتر ساختمان‌داده ها به نباری 7 صفحه: 188 

صفحه 189:
۸-۵ درختان انتخابی فرض کنید دارای >] مجموعه و رشته مرتب شده ای از عناصر هستیم که باید در یک رشته واحد ادغام شوند. هر دنباله یا ترتیب شامل تعدادی رکورد به ترتیب غیرنزیلی و فیلد مشخصی به نام 166 می باشد. ۶ یک دنباله مرتب اجرا ‎(FUN)‏ نامیده می شود. < فرض کنید که 1 تعداد رکوردها در اجرا باشد. عمل ادغام می تواند با تکرار ر کورد با کوچکترین کلید انجام شود. 

صفحه 190:
۸-۵ درختان انتخابی . كوجكترين كليد بايد ازبين »| امكان موجود بيدا شود و مى تواند ركوردى قبل از 42 ‎ASL (K-FUNS) Lol K‏ #ا بهترین روش برای ادغام ‎K‏ اجرا (۲۷۸5-) . نیازمند 1-1 مقایسه برای تعیین و انتقال ر کورد بعدی به خروجی می باشد. # به ازای 16<2. می توانیم با استفاده از ایده درخت انتخابی ؛ تعداد مقایسه های لازم جهت تعیین کوچکترین عنصر را کاهش دهیم. 

صفحه 191:
۸-۵ درختان انتخابی یک درخت انتخابی . یک درخت دودویی است که هر گره آن کوچکتر از دو فرزند خود می باشد بنابراین . گره ريشه نشان دهنده کوچکترین گره در درخت می باشد. | 292 ete J ‏نبا‎ ob str ‏گروه کامپیوتر‎ | 

صفحه 192:
WY ۸-۵ درختان انتخابی 122 2 ‏اه ]| اه‎ |1| fap ja my yo 5 o 0 5 5 1 8 1 3 3 2 5 1 7 0 6 8 3 5 0 6 # fed] fod he pm Pod bed for] ‏توملا‎ 

صفحه 193:
WY ۸-۵ درختان انتخابی زمان تجدید ساختار درخت پرابر ‏ )شد ‎k)‏ و020 زمان لازم براى أدخام تمام ۲ رکورد برابر می باشد. )& و0209 زمان كل لازم جيت ادخام »ل اجرا (11413) برابر می باشد. ساختمانداددها به زبان || صفحه: 193 

صفحه 194:
7 ‏چنگل ها‎ ٩-۵ جنگل مجموعه 0 < 9 درخت مجزا می باشد. اگر ريشه درخت را حذف کنیم , آنگاه دارای یک جنگل خواهیم بود. ساختمانداده هابه يباه اصفحه: 194 

صفحه 195:
WY ‏تبدیل جنگل به یک درخت دودویی‎ ٩-۵ برای تبدیل این جنگل به یک درخت دودویی واحد ابتدا نمایش دودویی هر یک از درختان جنگل را به دست می آوریم سپس تمام درختان دودویی را از طریق فیلد همزاد گره ريشه به یکدیگر متصل می کنیم. گروه کامپیوتر ] ساختمان‌داده ها به نباری ] صفحه: 195 

صفحه 196:
4-0 تبدیل جنگل به یک درخت دودویی foe bo اله درخت دودویی گروه کامپیوتر ] ساختمانداده ها به نباری ] صفحه: 196 

صفحه 197:
WY ۱ ‏تبدیل جنگل به یک درخت دودویی‎ ٩-۵ اگر جنگلی از درختان باشد (تگاه چم‌خت دودویی متناظر با اين جنكل يعنى ‏ 8: (۱) اگر ۵0 باشد . تهی خواهد بوط(7) BD Fos Tm) ‏دارای ریشه اي پرایر باتزیشه می باشد , داراعرپژیردرخت چپی‎ )۲( برابر با می باشد . به نحوول:آکه,یٌذرختان ريشه می باشند و در نهایت دارای زیردرخت راست می باشد. 

صفحه 198:
كروه كامبيوتر ساختمازداده ها به زباره) || صفحه: 198 

صفحه 199:
WY ۱ ‏پیمایش جنگل‎ ٩-۵ ‎by ye reorde 8‏ به ۲ معادل با بازیابی گره های ‎F‏ در درخت 0۲60۲۵6۲ می باشد: ‏* اگر ۴ تهی باشد , برگردید. * ریشه درخت اول ۴ را بازیابی کنید. ‏* زیردرخت . درخت اول رابه صورت ۲۵0۲۵6۲ پیمایش کنید. ‏* سایر درختان ۴ را به صورت ۲6۵0۲۵/6۲] پیمایش کنید. ‏گروه کامپیوتر ] ساختمانداده ها به نباری ‏ صفحه: 199 ‎ ‎ ‎ ‎ 

صفحه 200:
WY ۱ ‏پیمایش جنگل‎ ٩-۵ ‎n‏ مربوط به ۲ معادل گره های ۴ در درخت 6۳ است که به صورت زير تعریف می شود : ‎ ‏* اكر ۴ تهی باشد , برگردید. ريشه درخت . درخت اول را به صورت 10۳66۲ پیمایش ‏ريشه درخت اول را بازیابی کنید. ساير درختان را به صورت 1190۲016۳ پیمایش کنید. ‏گروه کامپیوتر ‏ ساختمانداده هابه زباری ] صفحه: 200 ‎ ‎ ‎ ‎ 

صفحه 201:
۳ ‏پیمایش جنگل‎ ٩-۵ هیچ گونه معادل طبیعی برای برای پیملیش 00510۲06۲ درخت دودویی متناظر یک جنگل وجود ندارد . پیمایش ۳0510۲06۲ یک جنگل ۳ را به صورت زیر بیان ی کنیم : ۱ اگر ‏ تهی باشد . برگردید. ۲ زیردرخت . اولین درخت ۴ را به صورت ۳۵50۲06۲ پیمایش کنید. ۲ ساير درختان باقی مانده‌ را به صورت ۳050۲06۲ پیمایش کنید. ۴) ريشه اولین درخت ۴ را بازیابی کنید گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 201 

صفحه 202:
۱۰-۵ نمایش مجموعه ده عضو از ۰ تا ‎٩‏ که به سه مجموعه مجزا از هم تفکیک شده باشند . می توانند بدین صورت باشند : S, ={2,35,},S, ={L4,9},S, ={0,6,7,8} Se oe گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 202 

صفحه 203:
WY ‏نمایش مجموعه‎ ۱۰-۵ در هر مجموعه بر خلاف معمول که اشاره گرها به از وللد به فرزندان در نظر گرفته می شدند. در اینجا اشاره گرها از فرزندان به وللد تنظیم می شوند و یا در حقیقت گره ها با رابطه پدری اتصال يافته اند. ] 203 woke J Qs owt ‏گروه کامپیوتر اس‎ J 

صفحه 204:
۱۰-۵ اعمال روی مجموعه ها حداقل اعمالی که بر روی مجموعه انجام می شود . به شرح زیر است ۱) اجتماع مجموعه مجزا (۸۲30۳) : اک ۹۶ دو مجموعه مجزا باشند . انگاه اجتماع آنها به صورت زیر تعریف می شود : | همه اعضا به صورت ۱ که ۷ يا عضوباشلایا عضو )4 ‎SUS = SF‏ ۲ (۲۱۵)1( پیداکردن آ) : مجموعه ای که آ عضو آن است را بيدا كنيد كروه كامبيوتر ساختمازدادم ها به زباره) || صفحه: 204 

صفحه 205:
۱۰-۵ اعمال روی مجموعه ها ۲ pe SUS, گروه کامپیوتر ساختمانداده هابه نباری 8 صفحه: 205 

صفحه 206:
۱۰-۵ قانون 6101011100 ۷۷ بر ای. ) ۱/۸10 جز مه قانون ۷۷619۳1۳09 برای( [. )۲۱۱0۵۲( :اگر تعدا گره ها در درخت 1 کمتر از تعداد گره ها در درخت ژ باشد . ژ را والد ‎cB‏ ‏در غير اين صورت 5 را والد أ[ قرار می دهیم. كروه كامبيوتر ساختمازداده ها به زباره) || صفحه: 206 

صفحه 207:
۱۰-۵ پیاده سازی قانون 610۳01170 ۷۷ برای پیاده سازی قانون ۷۷6101011۳0 باید بدانیم که در هر درخت چند گره وجود دارد. لين کار را بدین ترتیب انجام می دهیم که در ريشه هر درخت یک فیلد 60۷۸10۴ قرار می دهیم. اگر آ یک گره ريشه باشد . آنگاه 50 ‎COUNTLE]‏ تعداد گره های آن درخت خواهد بود. ‎COUNT‏ به صورت یک عدد منفی در فیلد ‎Parent‏ ‏گذاشته می شود. زملنی که ‎ped 2 oly LWeighting ogi‏ « عمل اجتماع به اين صورت را ۷1۳۱10102 می نامیم. گروه کامپیوتر ساختمانداده ها به نبارل ] صفحه: 207 

صفحه 208:
WY a 5 ‏مجموعه ها د‎ ۱۰-۵ اصل موضوعی ۰ فرض کنید ۲ یک درخت با 8۱ گره باشد که توسط 2 ایجاد شده باشد . در این صورت هیچ گرهی در ۲". سطحی بیشتر از 1+ یولع داشت. اگر در یک درخت ‏ عضو وجود داشته باشد . بیشترین زمان برای یافتن یک عضو به صورت ‎Sloe,‏ اگر ترکیبی از 11-1 عمل 4111013 و 110 عمل 811061 داشته باشیم . در بدترین حللت ممکن . زمان به ‎N+ MOG, D) gro‏ درمى آيد. تعریف ( قانون تخریب ) ۰ اگر ٌ گرهی روی مسیر از آ تا ريشه خود باشد . آنگاه ‏ را فرزند ريشه قرار دهید. گروه کامپیوتر ساختمانداده ها به نباری 7 صفحه: 208 

صفحه 209:
۱۱-۵ شمارش درختان دودویی تعداد درختان دودویی مجرا : تعداد درختان دودویی با ۷۱ گره . تعداد جایگشت های از ۱ تا 0 با استفاده از یک پشته و بالاخره تعداد راههای ضرب 1 ‎11١+‏ ماتریس . باهم مساوی اند. گروه کامپیوتر ] ساختمان‌داده ها به نباری ] صفحه: 209 

صفحه 210:
WY ‏تعداد درختان دودوبی مجزا‎ ۱۱-۵ برای به دست آوردن تعداد درختان مجزا با 9۱ گره از تابع زیر استفاده می کنیم : ‎bx‏ - وده ‏تابع فوق تولید کننده تعداد درختان دودویی است. ‏که‌بژابر است با : ا ‎2 +1 ‎ana ae ee ‏گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 210 ‎ ‎ ‎ ‎ ‎ 

صفحه 211:
فصل ششم: گراف ها "۳ .(حع ۲ ‎Slat‏ ) © آشنایی با گراف 8 را ماتریس مجاورتی ۴ جستجوی گراف * شبکه ها 

صفحه 212:
فصل ششم ۰ گراف ها هر گراف 3) شامل دو مجموعه ۷ و است ۷ مجموعه محدود و غیرتهی‌از یتوسلست : مجموعه لیمحدود و لحتمللاتسهی‌از لسبه ها می‌ب‌اشد (۷)6۵ و (6)63 : مجموعه یئوسو لبه هایگ رلفق) را نملیشمی دهند برای نمايش گراف هم می توانیم بنویسیم (۴, )66 گروه کامپیوتر ] ساختمانداده هابه نبارل ‏ صفحه: 212 

صفحه 213:
۱-۶ گراف ها در یک گ اف . جهت دار هر لبه با زوج مرتب ‎SMM?‏ داده می شود. انتها و ۲۵ دای لبه ۲۲ ند. بتابراین و < ۲۵,۲۲ >اوت ر < ۲۵ ,۲ > دهند. | 223 te J Oy ‏گروه کامپیوتر لسن اندادد هاب‎ J 

صفحه 214:
۱-۶ گراف ها #برای گراف بدون جهت , لبه هابه صورت خطوط یا منحنی نمایش داده می شوند. برای گراف های جهت دار لبه هابه صورت فلش هليى كه از انتها به ابتدا رسم شده است . ارایه می گردند. Pan | جهت دار بدون جهت | گروه کامپیوتر ‎btu.‏ نبا سنج 214 | 

صفحه 215:
۱-۶ محدودیت های گراف ها محدودیت های زیر بر روی گراف ها اعمال می شود : # یک گراف فاقد لبه ای از یک راس ماننداً .به خودش می باشد. اين مطلب بدین معنی است که لبه (:۲ غیرآمعتبر می باشد. یک گراف فاقد رویداد چند گانه از یک لبه می باشد. گروه کامپیوتر ساختمان‌داده ها به نباری ‏ صفحه: 215 

صفحه 216:
۱-۶ گراف ها برای یک گراف بدون جهت با 9 داس. ء حداكثر تعداد لبه ها . تعداد متمایز و غیرمرتب زوج هاو((۲/,۲) < آ مى باشد. ايت تعداد برابر است با : n(n-1)/2 اگر گراف جهت داری با 10 گره وجود داشته باشد. بیشترین تعداد لبه های آن برابر است با : ‎n(n-1)‏ گروه کامپیوتر ‏ ساختمانداده هابه نباری ] صفحه: 216 

صفحه 217:
۱-۶ گراف ها اگر(یک) لبه در گراف بدون جهت باشد , می گوییم رئوس ودو زاس مجاو و لبه یک لبه متلاقی(رلآی1) و است. ‎uw‏ يى زير ركراف 6 كرافى است مالقد به نحوق له (۲۷۲۵ و ‎Gas El‏ | 227 te J Ot ‏لس اختماندابد ماب‎ 7۳7 

صفحه 218:
۱-۶ گراف ها *** طول یک مسیر تعداد لبه های موجود در آن است. * مسیر ساده . مسیری است که همه رئوس آن احتمالا به جز اولی و آخری مجزا باشند. ** حلقه یا سیکل ,یک مسیرساده است که اولین و آخرین راس آن یکی باشد. برای مثال ۰0۱۰۲۰۰ یک حلقه دراگست. جک گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 218 

صفحه 219:
۱-۶ گراف ها در گراف بدون جهت مانند 63 , دو راس ۲۵ وا را ::-, می گویند. اگر مسیری در 6۵ از ۲۵ به ۲1 وجود داشته باشد. یک گراف بدون جهت را ۰:۰, می نامیم اگر برای هر زوج راس۲,قار (3)) ۷ .مسیری از ابه زر 63 وجود داشته باشد. يك مرانه انسال يابه طور ساده تر یک مولفه . در گراف بدون جهت . بزرگترین زیر گراف متصل آن است. | كروه كامبيوتر [لساختمانداده هايه وبا إل ‎se‏ 219[ 

صفحه 220:
۱-۶ گراف ها یک گراف جهت دار کاملا متصل نامیده می شود . اگر پرای هر زوج از رئوس /آدی(3)) ۷ ۰ مسیری جهت دار از به" و مچنین از به ,۲ وجو داشته باشد. جك رلقة سارت . بزرگترین زیر گرافی است که کاملا متصل ‎oo‏ 2 ال ‎6 ‏گروه کامپیوتر ‏ ساختمانداده هابه نباری ] صفحه: 220 ‎ ‎ ‎ ‎ 

صفحه 221:
۱-۶ گراف ها هب درحه راس تعداد لبه های متلاقی با آن راس است . اكر در كراف 6 با 18 راسر©. درجه راس 1 و 6 تعداد لبه ها باشد . به آسانى مى توان ديد كه تعداد لبه ها برابر است با : 

صفحه 222:
۱-۶ نمایش گراف نمایش گراف ها به سه صورت است : ماتریس مجاورتی ت های مجاورتی لیست های چند گانه 

صفحه 223:
۱-۶ ماتریس مجاورتی ۳ فرض کنید (] ۰ ۷)<) یک گراف با 9 راس باشد . 1 < ورتم راف ‎ic ii STi coon ctl es‏ ‎lad) mat‏ باشد. اككر لبه (براءئح رگراک جهت دار ( 59 ‎E(G)‏ ‏باشد . آنگاه 0 ‎[j]=‏ [801[_۱۸۵۲]1 خواهد بود. اور جهت متقازن است زیر G(@)),> 55 ‏اگر و تنهااگر لب‎ Lay sale OY) ad باشد گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 223 

صفحه 224:
۶-۱ ماتریس مجاورتی (مثال ) ۱ لا ماتريس مجاورتى م [ل>» ]| 

صفحه 225:
WY ‏ماتریس مجاورتی‎ ۱-۶ برای گراف بدون جهت . درجه هر راس مانند آً مجموع عناصر سطری آن است : 1 ور ‎adj_matit‏ ,> مدر براى يى گراف جهت دار . مجموع سطری . درجه خارجه و مجموع ستونی ء درجه وارده خواهد بود. گروه کامپیوتر ‏ ساختمانداده هابه نباری ] صفحه: 225 

صفحه 226:
۶-۱ لیست های مجاورتی با لین نمایش ۰ 9 سطر ماتریس مجاورتی در 1۱ لیست پیوندی قرار مى كيرد. براى هرراس از گراف 62 . یک لیست وجود دارد. هر گره حداقل دو فیلد دارد : راس و اتصال در هر لیست مشخصی مانند آ. گره های لیست حاوی رئوس مجاور از راس 5 می باشند. در یک كراف بدون جهت با 19 راس و 6 لبه . 9 گره 06۵۵0 و 6 كره ليست دارد. هر كره ليست دو فيلد لازم دارد. گروه کامپیوتر |[ ساختمازدادمهايه زباره) || صفحه؛ 226 

صفحه 227:
۶-۱ لیست های مجاورتی(مثال) ۳ _ گروه کامپیوتر ‎SS‏ كك ‎ ‎noe vertex link a]. ‏رس ‎ ‎ ‎6 6-۰ ‎ ‏ساختمانداده ها به زباری ] صفحه: 227 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 228:
WY ‏لیست های مجاورتی‎ ۶-۱ 7" درجه هر راس در یک گراف بدون جهت را می توان به سادگی با شمارش تعداد گره های آن در لیست مجاورتی تعیین کرد. اگر تعداد رئوس گراف 63 برابر با 90 باشد . تعداد کل لبه هاء در زمان © + 1 ) © ( تعيين مى شود. [228 ote J oat | ‏گروه کامپیوتر‎ | 

صفحه 229:
WY ‏ساختار گره برای لیست های مجاورتی‎ ۶-۱ نمایش دوم :هر گره دارای چهار فیلد بوده و نشان دهنده یک لبه است. row link for tail | column link for head | head | tail گروه کامپیوتر ‏ ساختمانداده هابه نباری ] صفحه: 229 

صفحه 230:
۱-۶ لیست های مجاورتی چند گانه (v,,¥)) " ‏در نمايش ایست مجاورتی ,هر لبه در یک گراف بدون جهت مانند‎ 7 : ‏با دو وارده نمایش داده می شود‎ ‘i لا در ليست براى ‎yj‏ لا در لیست برای 

صفحه 231:
۱-۶ لبه های وزنی در ماتریس مجاورتی . کمیت ۱ که نشان دهنده وجود یک لبه است را با وزن یک لبه تعویض می کنیم. در لیست های مجاورتی و لیست های مجاورتی چند گانه . فیلد ۷۷61010 به ساختار گره اضافه می شود. marked vertexl vertex2 path1 ساختار یک گره برای لیست های مجاورتی چند گانه path2 گرافی که لبه هایش دارای وزن باشد . شبکه نامیده می شود. _ گروه کامپیوتر ساختم‌انداده ها به نباری 6 صفحه: 231 

صفحه 232:
۲-۶ اعمال ابتدایی گراف 5 با توجه به گراف بدون جهت (۰ 6)۷ و راس ۷ از (۷)63 می خواهیم رئوسی از © را كه از لا قابل دسترسی هستند. به دست آوریم( یعنی همه رئوس متصل به ۷ . برای اين کار دو روش وجود دارد : ‎i ~ *‏ : روش عمقی تا حدودی شبیه پیمایش ‎preorder‏ یک درخت است. ‏6 جسته نی :این روش تا حدودی پیمایش ترتیب سطحی را ‏در پیمایش های عمقی و ردیفی . فرض می کنیم که برای نمایش گراف ‎ ‏كروه كامبيوتر ساختمازدادم ها به زباره) || صفحه: 232 ‎ ‎ ‎ ‎ 

صفحه 233:
۲-۶ جستجوی عمقی ۳ در آغاز راس ۷ را ملاقات می کنیم. بعد راسی مانند ۷۷ را که قبلا ملاقات نشده و مجاور به ۷ است را انتخاب کرده و روش جستجوی عمقی را با ۷۷ دنبال می کنیم. موقعیت جاری راس ۷ در لیست مجاورتی با قرار دادن آن در یک پشته صورت می گيرد. در نهایت . جستجو به راسی مانند لا خواهد رسید که فاقد هر گونه راس غیرملاقات شده در لیست مجاورتی باشد. در این مرحله راسی از پشته انتخاب و و حذف شده و فرآیند فوق به همین صورت ادامه پیدا می کند. بر اساس این روش ۰ رئوس ملاقات شده. خارج شده و رئوس ملاقات نشده . داخل پشته قرار می گیرند. جستجو زمانی پایان می پذیرد که پشته تهی باشد. گروه کامپیوتر ساختمانداده ها به زباری [ صفحه: 233 

صفحه 234:
۲-۶ جستجوی عمقی ۳ جستجوی عمقی شبیه پیمایش ط7 یک درخت مى باشد . زیرا ‎Void dfs (int V)‏ { ‎fiat ve stex ۰ apf a graph‏ و ‎nods, pointer w;‏ ‎visited[V] = TRUE ;‏ ‎print f (“ %5d“.V);‏ ‎link for (w = graph[V] ; w; w = w->‏ ‎if (! Visited [w->vertex] )‏ ‎dfs (w-> vertex ); ‎ ‏گروه کامپیوتر ساختمانداده ها به نبارل ] صفحه: 234 ‎ ‎ ‎ ‎ ‎ 

صفحه 235:
2-6 جستجوي عمقي(منال) گراف 6 a 8 0 0 ی م نمايش ليست هاي مجاورتي ¢ Teneo گروه کامپیوتر ساختمانداده ها به نبارل ] صفحه: 235 

صفحه 236:
۲۷-۶ جستجوی عمقی(مثال) توضیح شکل قبل 4 اگر روش جستجوی عمقي راز را و غاز نم : رئوس گراف ق) به تر تیب “ ملاقات می شوند. گروه کامپیوتر ساختمانداده ها به نباری ‏ صفحه: 236 

صفحه 237:
۲-۶ تحلیل 065 اگر 63 توسط ماتریس مجاورتی نمایش داده شود . زمان لازم برای تعیین همه رتوس مجاور به (0)0. ۷ است. از آنجا که حداکثر 1۱ راس مشاهده می شود , ‎wd LAB) OLe5 JS‏ گروه کامپیوتر ] ساختمانداده ها به نباری ] صفحه: 237 

صفحه 238:
۲-۶ جستجوی ردیفی پیمایش را با راس ۷ شروع نموده . پس از ملاقات راس مزیور . آنرا علامت گذاری می کنیم. اول هر یک از رئوس مجاور به راس ۷ را در لیست مجاورتی ملاقات می کنیم. زمانی که همه رئوس مجاور با راس ۷ را ملاقات کردیم . تمام رئیس ملاقات نشده که مجاور با اولین راس مجاور با ۷ در لیست مجاورتی است را ملاقات می کنیم. برای انجام این کار مادامیکه هر راس ملاقات می شود . آنرا در یک صف قرار می دهیم. هنگامی که لیست مجاورتی تمام شد . راسی را از صف حذف و با تست هر يك از رئوس در ليست مجاورتی این فرآیند را ادامه می دهیم. رئوس ملاقات نشده . ملاقات و سپس در صف قرار می گیرند. رئوس ملاقات شده نادیده گرفته می شوند. جستجو هنگامی که صف تهی گردد . خاتمه می یابد. گروه کامپیوتر ساختمانداده ها به نبارل ] صفحه: 238 

صفحه 239:
۲-۶ جستجوی ردیفی تابع 0۴5 حاوی دستورات لازم جهت پیاده سازی جستجوی ردیفی است. ساختمانداده ها به نبا || صفحه: 239 

صفحه 240:
۲-۶ درخت های پوشا چنانچه گراف 6۵ متصل باشد . پیمایش های جستجوی عمقی یا جستجوی ردیفی . تمام رثوس گراف 68 را ملاقات می کنند. در اين حللت با اعمال هر يك از پیملیش ها لبه های گراف 6 به دو تقسيم مى شوند : 7 ( برلیلبه های‌دیخت) : مجموعه لبه هاوبه کار یفته یا پیموده شده در جستجو می‌ب‌اشد 3 (برلیل به های‌غیر دیخت : مجموعه لبه هایب‌اقی‌مانده می باشد گروه کامپیوتر ساختمانداده ها به نباری ] صفحه: 240 

صفحه 241:
WY ‏درخت های پوشا‎ ۲-۶ لبه های ۰۲ یک درخت که شامل تمام رئوس گراف 6 مى باشد را تشکیل می دهند . تعریف درخت پوشا : درختی که تعدادی از لبه ها و تمام رئوس ‎GS‏ ‏را در بر دارد . درخت پوشا نامیده می شود : ۵ 5 5 سه درخت آن گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 241 

صفحه 242:
۲-۶ درخت های پوشا [- درخت پوشایی که از فراخوانی 61۴5 به دست می آید را درخت پوشای عمقی می نامند. - جنانجه از روش ۵۴5 استفاده شود . درخت پوشای حاصل را درخت پوشای ردیفی می org درخت پوشای ‎bPe‏ درخت پوشای 8 گروه کامپیوتر ‏ ساختمانداده هابه نباری ]| صفحه: 242 

صفحه 243:
۲-۶ درخت های پوشا ‎NS‏ مقصود از زیر گراف حداقل : یعنی زیرگرافی که تعداد لبه هایش کمترین باشد. <هر گراف متصل با 1 راس . بایستی حداقل 9-1 لبه داشته باشد و همه گراف ها متصل با 0-1 لبه . درخت هستند. درخت پوشا دارای 9-1 لبه می باشد. < ایجاد زیر گراف های حداقل . کاربردهای متعددی در طراحی شبکه های ارتباطی دارد. مثال :اگر رتوس گراف ق) نماینده شهرها و لبه ها معرف جاده هاى ارتباطى بين شهرها بلشد . آنگاه حداقل تعداد خطوط مورد نیاز برای اتصال 1۱ شهر به یکدیگر ۵-1 خواهد بود. گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 243 

صفحه 244:
۲-۶ اجزای دو اتصالی و نقاط اتصال ‎ob‏ ۳ :یک راس مانند ۷ از گراف 63 می باشد به نحوی که حذف راس ۷ همراه با تمام لبه های متلاقی با ۰۷ گرافی بهانام ایجادمی کند که حداقل دارای دو جز متصل است. ‏كراف ده اتسار یک گراف متصل است اگر فاقد نقاط اتصالی باشد . ‏گروه کامپیوتر ساختمان‌داده ها به نباری ‏ صفحه: 244 ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 245:
۲-۶ اجزای دو اتصالی و نقاط اتصال رای در سا یک گراف بدون جهت متصل مانند 3) یک زیر گراف دو اتصالی حداکثری به نام ۲ می باشد. منظور از اين حداكثر اين است که 3) فاقد زیردرختلنی است که هم دو اتصالی و هم دارای خاصیت ۳ استفاده از درخت پوشای عمقی گراف 68 . می توان اجزای دو اتصالی ایک گراف بدون جهت متصل را به دست آورد. یک لبه غیردرختی مانند( ایک لبه غیربر گشتی است (6096 ‎back‏ ‏اگر و تنها اگر لا جد ۷ و با ۷ جد لا باشد گروه کامپیوتر ساختمانداده ها به نباری ] صفحه: 245 

صفحه 246:
۲-۶ اجزای دو اتصالی و نقاط اتصال ريشه یک درخت پوشای عمقی یک نقطه اتصال است . اگر و تنها اگر دارای حداقل دو فرزند باشد. هر راس مانند لأ یک نقطه اتصال است . اگر و تنها اگر دارای یک فرزند مانند ۷۷ باشد به نحوی که قادر باشیم با استفاده از یک مسیر که شامل تنها ۰۷۷ نسل ها و یک لبه بر گشتی . به جد لا برسیم. گروه کامپیوتر |( ساختمانداده هابه نباری ] صفحه: 246 

صفحه 247:
۲-۶ اجزای دو اتصالی و نقاط اتصال برای هر راس در (۰10۷۷)۷ 6 پایین ترین عدد عمقی است که مى توانیم از لا با استفاده از یک مسیر نسل ها به دنبال حداکثر یک لبه برگشتی . به آن برسیم. ‎Low (u) = min { dfn (u) .min {low(w) | w‏ ‎is a child of u}.min { dfn (w) | (u.w‏ ‎is a back edge } }‏ ) که لا یک نقطه اتصال است . اگر و تنها اگر لا ريشه یک درخت پوشا بوده و دارای دو فرزند يا بیشتر باشد و يا لا ريشه نباشد و دارای یک فرزند مانند ۷۷ است به نحوی که (۷) ‎low (w) = = dfn‏ است. گروه کامپیوتر ساختمانداده ها به نبارل ] صفحه: 247 

صفحه 248:
UY ‏اجزای دو اتصالی و نقاط اتصال‎ ۲-۶ + 1 ۷ ۶ ۵ 0 5 Vertex A + 3 ۶ 95 0 1: 0 + | ‏هه‎ A + ۷ 5 5 0 + | tow ۲۵۵۲ 2 3 ‏مقدیر ۳8 و 0۷۷]برای درخت پوشای با‎ گروه کامپیوتر ‏ ساختمانداده هابه نباری ] صفحه: 248 

صفحه 249:
۴-۶ درختان پوشای با حداقل هزینه 5 هزينه يى درخعت برشای یک گراف جهت دار دارای وزن ۰ مجموع هزینه های( وزن های) لبه ها در درخت پوشا می باشد. خت يوشاى حدافل هرن درخت پوشایی است که دارای کمترین برای به دست آوردن درخت پوشای حداقل هزینه یک گراف جهت دارمتصل می توان از سه الگوریتم متفاوت استفاده نمود : ‎<i ۴‏ الگوریتم راشال . الگور یتم م . الگور یتم سولیر ‏هر سه روش از یک طراحی الگوریتمی به نام خط مشی ‎greedy‏ ‏استفاده می کنند. ‏گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 249 ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 250:
۲-۶ درختان پوشای با حداقل هزینه برای درخت های پوشا از ملاک کمترین هزینه استفاده می شود. روش ما باید دارای شرایط زیر باشد : ۱) بايد فقط از لبه های داخل گراف استفاده کنیم. ۲ باید دقیقا از 4ب لبه استفاده کنیم. ۳ نباید از لبه هایی که ایجاد یک حلقه می کنند . استفاده کنیم. 

صفحه 251:
۲-۶ الگور يتم راشال ۱ در لین روش . درخت پوشای با کمترین هزینه ۲ . لبه به لبه ساخته می شود. لبه های مورد استفاده در ۲ .به ترتیب صعودی وزن ها می باشد. یک لبه در ] خواهد بود. اگر با لبه های قبل که در ۲ بوده اند , تشکیل یک حلقه ندهد جون © متصل است و دارای 0 ‎ <‏ راس است . دقيقا 1 - 9 لبه برای ۲ انتخاب می شود. | گروه کامپیوتر لساختسانداده ماب نیام | صفحه 232 | 

صفحه 252:
۳-۶ الگوریتم راشال (منال) وس 0ه 

صفحه 253:
۲-۶ الگوریتم راشال گروه کامپیوتر ‏ |رساختمانداددهايه زيار |[ صفحه. 253 

صفحه 254:
۲-۶ الگوریتم پریم ‎iS‏ الگوریتم پریم مانند الگوریتم راشال . در هر زمان یک لبه از درخت پوشای حداقل هزینه را می سازد. هر چند در هر مرحله الگوریتم . مجموعه لبه ها انتخاب شده یک درخت را تشکیل می دهند . در مقابل . مجموعه لبه های انتخاب شده در الگوریتم راشال در هر مرحله یک جنگل را تشکیل می دهند. الگوریتم پریم با یک درخت مانند ۲ که تنها شامل یک راس است ۰ شروع می کند. این می تولند هر یک از رئوس در گراف اصلی باشد. سپس یک لبه با کمترین هزینه مانند ‎go aa. (U,V),‏ شود به نحوی که نیز (0:۷) لا [رخت می باشد. اين عمل را تا زمانی که ۲ شامل 1 - ‎٩‏ لبه باشد . ادامه می دهیم. گروه کامپیوتر ساختمانداده ها به نبارل ] صفحه: 254 

صفحه 255:
۳-۶ الگوریتم پریم (منال ) 

صفحه 256:
۳-۶ الگوریتم سولین بر خلاف الگوریتم پریم و راشال , الگوریتم سولین چندین لبه را برای اضافه نمودن در هر مرحله انتخاب می کند. در ابتدا یک مرحله , لبه های انتخاب شده . همراه با تمام 10 راس گراف , تشکیل یک درخت پوشا را می دهند. در خلال یک مرحله یک لبه برای هر درخت در جنگل انتخاب می کنیم. اين لبه دارای حداقل هزینه بوده یعنی دقیقا دارای یک راس در درخت می باشد. از آنجا که دو درخت در جنگل می توانند یک لبه یکسان انتخاب کنند . لذا می توانیم کپی تکراری از لبه ها را حذف کنیم. در ابتدای مرحله اول ؛ مجموعه لبه های انتخاب شده خللی می باشد. این الگوریتم هنگامی به پایان می رسد که فقط یک درخت در انتهای یک مرحله باقی و یا هیچ لبه ای برای انتخاب باقى نمانده باشد. گروه کامپیوتر ساختمانداده ها به نبارل ] صفحه: 256 

صفحه 257:
3 4 a 3 1 3 8 i 

صفحه 258:
۴-۶ یک مبدا و چند مقصد در اين مساله كراف جهت دار ( 8. لا) = را در نظر می كيرهم. تابع وزنى (©) للا 0< را برای لبه های 3) و راس مبدا فرض ميکنيم. مساله . تعیین کوتاهترین مسیر از به بقيه رئوس در 3) است. فرض می کنیم تمام وزن ها مثبت باشند. rok eats 9 6 33 ‏6ه ۷ ان‎ 1 ‏۱و‎ 1 ۷ ۷ 9 6 6 3: eo یک گراف و کوتاهترین مسیر از ما [298 soe ‏گروه کامپیوتر اس اندادد ماب نبا إل‎ J 

صفحه 259:
۴-۶ کوتاهترین مسیر بین هر جفت از رئوس ‎ .‏ مساله کوتاهترین مسیر بين هر زوج از رئوس به مفهوم یافتن کوتاهترین مسیر بين همه رئوس _. ملباشد (به طوری که [ ‎CDF‏ از آنجا که 65 دارای ۲۱ راس و 5۱0۵۳۲۵5۴۵۵۴ دارای (م0 می باشد, لذا كل زمان صرف شد( ”0017 خواهد بود. گراف 3) توسط ماتریس مجاورتی هزینه خودبا 0 < [][051]1) ارایه می شود ‎j)‏ < آ) و در صورتی که لبه ‎ (‏ * 1) < [. 1 > در © نباشد. [][6051]1 حاوی عدد بزرگی خواهد بود که اين عدد باید همان محدودیت های مطرح شده در خصوص مساله یک مبدا ( 50۱۲66۵ 510916 ) را دارا باشد. گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 259 

صفحه 260:
۴-۶ کوتاهترین مسیر بین هر جفت از رئوس ‎٠‏ [ ]رنه کوتاهترین مسیر از ۱به ز تعریف می کنیم که اين مسیر هیچ راس میلنی که اندیس کوچکتر یا مساوی از (ک ط ‎dh‏ > داشته باشیم . عبور نمی کند. ‎capa SAG LAL]‏ مسير از أبه [در 63 است. نکته اصلی در همه الگوریتم هایی که روی زوج ها عمل می کنند . ‏لین می باشد که همه آنهابا روع کرده و ماتریس های متوالی ‎wt‏ .., ۸ رااینگاد مى کند. 1 ‎ ‏گروه کامپیوتر ساختمانداده هابه نباری 8 صفحه: 260 ‎ ‎ ‎ ‎ ‎ 

صفحه 261:
۴-۶ کوتاهترین مسیر بین هر جفت از رئوس . ۱۳ اكر قبلا ' “مرا توليد كرده باشيم . مى توانيم با عمل روی هر زوج از رئوس و زبا توجه به یکی از دو قاعده زیر به دست آوریم : ) کوتاهترین مسیر از ابه ز از هیچ راسی با اندیس بزرگتر از | عبور نمی کند و حتی از راسی با اندیس نیز نمی گذرد و بنابرلین هزینه ان است. at ۲ جنير هن مسیری از ‎wl‏ ا مى گذرد بنابرلین چنین مسیری شامل مسیری از ابه > و به دنبال آن مسیری از به ا می باشد. هیچ کدام از اين مسیرها با اندیس بزرگتر از ۲-4 عبور نخواهد کرد . بنابراین هزینه آن ها و می باشد. ATA) ۹ گروه کامپیوتر ساختمانداده ها به نبارل ] صفحه: 261 

صفحه 262:
۴-۶ کوتاهترین مسیر بین هر جفت از رئوس ۸۶<0,([ز]۱]0 4 + ۸۲۱۲/0 رزر]ز] "هنت [ز]]2۳ ‎Vues:‏ ‎ALL =coshil/l‏ . فرمول ۲ تابع 6و۱ ه]۸۳۱]1 را محاسبه می کند. زمان کل ۵1160515 ب(ابولمت. | گروه کامپیوتر لس اختماندابد هاب» ‎ote J Ot‏ 252 | 

صفحه 263:
UY ‏مثال)‎ ( of ‏گراف چهت دار 6 و ماتریس هزینه‎ ۴-۶ ۶ 7 hee ‏مح‎ fr: 5 r 9 yo. ¢ ۱ ماتریس لمجارتى هزينه لها براي كرا © گراف جهت دار 6 ساختمازدادمها به نباری | صفحه؛ 263 

صفحه 264:
| گروه کامپیوتر لس اختماندابد هاب» نبا سنج 254 | 

صفحه 265:
۴-۶ بسته بودن تعدی در یک گراف جهت دار با لبه های بدون وزن مانند 63 . آیا برای هر دو راس مانند 1 ولّء مسیری از آ به أ[ وجود دارد يا خير؟ دو حالت می تواند مورد توجه قرار بگیرد : ۱)وقتی که همه مسیرها طول مثبت داشته باشند که بسته بودن تعدی یک گراف نامیده می شود. ۲ زمانی که طول مسیرها غیرمنفی باشد که بسته بودن تعدى انعکاسی یک گراف نامیده می شود. 

صفحه 266:
۴-۶ ماتریس بسته پودن تعدی و ماتربس بسته بودن تعدی انعکاسی تعريف ؛ ماتريس بسته بودن تعدى ‎٠‏ + كراف جهت دار مانند ©, ماتریسی است که اگر مسیری او عبز ][ل4بزگتر از صفر وجود داشته ‎ope ALI EQ, «ash‏ خواهد بود. تعريف ؛ ماتريس بسته بودن تعدى انعكاسى . ليك كراف جهت دار مانند 08 : ماتريسى است كه اكر مسير ط جز ‎GIS‏ ساوى با صفر از ‎١‏ به ز وجود داشته ‎Val =O su‏ 2 غير اين صورت خواهد بود. تنها تفاوت و ‎polis ot‏ روی قطر اصلی است. بنابراین 1= [][ مه باشد گروه کامپیوتر ساختمانداده ها به نباری ] صفحه: 266 

صفحه 267:
WY AOV 45.3 0-5 ‎GLE AOV (activity on vertex) ac5: wae‏ جهت داری مانندق) است که رئوس آن نمایانگر فعالیت ها یا عملکردها است و لبه های آن نمایانگر ارتباطات بین عملکردها می باشد. این گراف . شبکه فعالیت های روی رئوس یا شبکه /۸100۷ نامیده می شود. ‏گروه کامپیوتر ‏ساختمانداده ها به نباری ] صفحه. 267 ‎ ‎ ‎ ‎ ‎ 

صفحه 268:
۵-۶ شبکه ۸0۷ ۱ تعریف ۰ راس آ در یک شبکه ۸60۷ مربوط به گراف 6 . یک راس تقدمی برای راس ژ خواهد بود. اگر و تنها اگر مسیر جهت دارى از راس 5 به ل[ وجود داشته باشد. اكر و تنها اكر <[: ‎١‏ > لبه اى در 6 باشد . يك راس تقدمى بلافصل برای ‎cul J‏ اگر آ یک راس تقدمی برای ژ باشد . آنگاه ژ راس تاخیری برای آ مى باشد. اگر آ یک راس تقدمی بلافصل برای [ باشد . آنگاه ‏ راس تاخیری بلافصل برای آ می باشد. گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 268 

صفحه 269:
۵-۶ شبکه ۸۵۷ (منال) گروه کامپیوتر ] ساختمانداده ها به نباری ] صفحه: 269 

صفحه 270:
S AOV ‏شبکه‎ ۵-۶ تعریف :یک رابطه . تعدی است اگر وتنها اگر برای تمام سه گانه های ۷[ . ایا ۰ . >! . را نتيجه می دهد.ز 320 [.آ ‎ik‏ >=( یک رایطه . روی مجموعه 5 غیر انعکاسی است . اگربرای تمامی مقادیر در آ . ], 5 نادرست (85) باشد. رابطه ای که هم تعدی و هم ‎pat‏ انعکاسی باشد . یک رابطه ترتیبی نامیده می شود. اگر رابطه تقدمی غیرانعکاسی نباشد . آنگاه فعالیتی وجود دارد که راس تقدمی آن خودش است. گروه کامپیوتر ساختمانداده ها به نباری ‏ صفحه: 270 

صفحه 271:
۵-۶ شبکه ۸0۷ اف جهت داری که هیچ حلقه ای نداشته باشد . گراف ۵6۷6116 جهت دار یا جهت داری که هیچ ای ب جهت 09 نامیده می شود. تعریف ؛ ترتیب موضعی یک ترتیب خطی از رئوس گراف است به نحوی که به ازای هر دو راس او ؛ اگر آ یک راس تقدمی برای ژ در شبکه باشد . آنگاه آً در اين ترتيب خطی بیش از [قرار می گیرد. 

صفحه 272:
۵-۶ فعالیت بر روی لبه (6(۷) شبکه یک شبکه فعالیت که ارتباط نزدیکی با شبکه ‎۸٩0‏ داشته باشد , فعالیت روی لبه يا شبكه 8016 ناميده مى شود. اعمالى كه روى يروزه صورت كيرد با لبه هاى جهت دار نمايش داده مى شوند. رئوس شبکه نمایانگر وقایع است. یک واقعه فقط زملنی اتفاق می افتد که همه فعالیت های وارده به آن قبلا کامل شده باشد. 

صفحه 273:
۵-۶ فعالیت بر روی لبه (۸6(۷) شبکه 3 شبکه های فعالیت از نوع ۸60۴ در ارزیلبی اجرایی چندین نوع از پروژه ها به طور موثری مورد استفاده قرار می گيرند. اين ارزیابی شامل تعیین چندین نکته در مورد پروژه ها به شرح زیر است : (۱) کمترین زمان ممکن برای تکمیل پروژه (۲) تعیین اينکه کدام فعالیتها بایستی زودتر انجام شوند تا زمان تکمیل پروژه کاهش یابد. گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 273 

صفحه 274:
WY ‏شبکه‎ (AOV) au ‏فعالیت بر روی‎ ۵-۶ چندین تکنیک و روش بسیار مهم برای ارزیابی مدل های شبکه پروژه توسعه يافته اند از جمله : 1 ۶8۲( ارزیلبی‌اجراییو تکنیکب ازبینی) 2 ۳۱۷( روش‌مسیر بحرلنی) 3 ۱8۵۴5 تخصیصرمنبع و ‎sai ile‏ رود چند گلنه) ] 27 ete ‏گروه کامپیوتر اس اناده هيه وباك إل‎ J 

صفحه 275:
۵-۶ فعالیت بر روی لبه (6(۷/) شبکه از آنجا که فعالیتهای یک شبکه 06) می توانند به طور موازی انجام شوند . کمترین زمان لازم برای کامل شدن پروئه . اندازه طولانی ترین مسیر از راس اغازی به راس پایانی است. مسیری با طولانی ترین طول . یک مسیر بحرانی است. گروه کامپیوتر |( ساختمانداده هابه نباری ]| صفحه: 275 

صفحه 276:
۵-۶ فعالیت بر روی لبه (6(۷/) شبکه زودترین زملنی که واقعه (۲ می تولند اتفاق بیفتد , طولانی ترین مسیر از راس آغازی۲۵ به راس ۲ است. زودترین زملنی که یک واقعه می تولند اتفاق بیفتد . زودترین زمان شروع همه وقلیع موجود که از لین راس خارج شده لند را تعیین می کند. لین زمان رابه صورت () 68۲۱۷ برای فعالیت۹ نشان می دهیم. گروه کامپیوتر ساختمانداده ها به نبارل ] صفحه: 276 

صفحه 277:
۵-۶ فعالیت بر روی ‎(AOV) au‏ شبکه ۵ برای هر فعالیت مانند :4 می توان دیرترین زمان را نیز تعریف کرد. که در واقع دیرترین زملنی است که یک فعالیت می تواند انجام شود به شرط اينکه زمان پروژه را افزایش ندهد. همه فعالیتهلیی که به صورت (۱8۲6)1 < (۱) 66۲۱۷ هستند . فعالیت های بحرانی نامیده می شوند. ‎Law‏ ()6۵۲۱۷ و (12]6)1 . اندازه يا میزان بحرانی بودن یک فعالیت را نشان می دهند 

صفحه 278:
۵-۶ محاسبه زودترین زمان به منظور به دست آوردن زودترین و دیرترین زمان برای تمام فعالیتهای یک شبکه . مناسب است که برای تمام وقایع در شبکه . ابتدا زودترین زمان رویداد واقعه یعنی [[]*68۲1165 و سپس ‎Gas po‏ زمان رویداد واقعه یا [[]25]651] محاسبه نمود. سپس اگر فعالیّت به وسیله لبه < ۰۱ ۷ > ارایه شود , می توانیم ‎late(i), early(i)‏ را از فرمول زیر محاسبه کنیم : ‎earl) =earlie$kl‏ late(i) = latest [I] - duration of activity, ‏در دو‎ lastest[j] » earliest[j] ou; : ‏گردد‎ كروه كامبيوتر | ساختمانداده هابه زبار || صفحه. 278 

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

صفحه 280:
فصل هفتم ۰ مرتب سازی * فرض کنید مجموعه ای از اطلاعات مربوط به اشیا داریم . اكر اين مجموعه به راحتی در حافظه قلبل دسترسی قرار گیرند . آنرا لیست می نامند. * در صورتی که برای ذخیره کردن مجموعه به حافظه خارجی نیاز باشد آنرا فایل می نامند. * اطلاعات یک شی از مجموعه فوق را رکورد می نامند. * هر جز از رکورد را فیلد می نامیم. ‎J‏ گروه کامپیوتر لسن ]ت۱۳ ‎ ‎ ‎ ‎ ‎ 

صفحه 281:
۱-۷ اصطلاحات # زملنی که يى ليست از رکوردها را جستجو می کنیم . هدف پیدا نمودن ر کوردهایی است که دارای فیلدی با مشخصات مورد نیاز باشند. اين فیلد را اصطلاحا کلید می نامند. "ذ كارايى روش و خط مشى جستجي بستكى به آرايش و نحوه قرار كرفتن ركوردها در ليست دارد. | 252 te ‏إل‎ tsb tuto nics ‏ا‎ 

صفحه 282:
۱-۷ جستجوی ترتیبی ۳ فرض كنيد كه ليست ويك كليد جستجو به نام 563۳۷ داشته باشیم . هدف بازیابی رکوردی است که کلید آن منطبق بر 7 باشد. اگر این لیست دارای 1۱ رکورد باشد . با ۷ اتب مقدار کلید رکورد [ دسترسی پیدا می کنیم. لیست را با جستجوی مقادیر کلیدهای ۰۰.۰ ‎list[n-L]. key‏ ۷ مورد بررسی قرار می دهیم تابه رکورد مورد نظر برسيم يا تمام ليست را جستجو کنیم. گروه کامپیوتر ساختمانداده ها به نبارل ] صفحه: 282 

صفحه 283:
۱-۷ تحلیل تابع 560650637010 eqsearch تحلیل تابع 560565۲617 : قبل از شروع جستجو . 0 را در موقعیت ۱5]]۳01.166۷ قرار می دهیم. این موقعیت در واقع انتهای لیست را نشان می دهد. با جلوگیری از تست پایان لیست ۰ یعنی شرایطی که 1- 9 < آ باشد. می توانیم براحتی ساختار حلقه را ساده کنیم. اگر عمل جستجو موفقیت آمیز نباشد. ۷9 < آ. مقدار -۱ را برمی گردانيم . بنابراین در یک جستجوی ناموفق نیاز به 1 + 9 عمل مقایسه کلید داریم که زمان آن(0)۳ خواهد بود. گروه کامپیوتر ساختمانداده ها به نبارل ] صفحه: 283 

صفحه 284:
۱-۷ تحلیل تابع 560650637010 میانگین تعداد عمل مقایسه در یک جستجوی موفقیت آمیز برابر است با : 

صفحه 285:
۱-۷ جستجوی دودویی در جستجوی دودویی بایستی لیست بر اساس فیلد کلید مرتب شود , یعنی : .list{O].key s list{1].key =... = list[n-1].key گروه کامپیوتر ] ساختمانداده ها به نباری ] صفحه: 285 

صفحه 286:
۱-۷ جستجوی دودویی 5 این جستجو با مقایسه 568۲6۳۷0 و ۱5]۳00016[۰16۷ . به ازای )۳۸۱۵۵16 12 شروع می شود. هنكام مقایسه سه حالت ممکن است روی دهد 1( ۱5]۳۲00۱6[.6۷ 568۲۷۳ ۰ در لین حاللت یکوردهایی بین [۱5]]۳10016] و [1-]۱15 کنار گنلشته شده و جستجو بارکوردهای[۱151]0 تا [15]۳010016-1] دنبللمی‌شود. 2( ۱15]۳۱۱00۱6[.6۷ 563۲6۳۷۲۸ : در لین‌حا لنجستجو با موفقیتبه پایان‌می یسد ۷ ۲ < 568۲1۱۳۷۲۱ : در لین حللت . ر کوردهای بین ‎p List[O]‏ [5]۳010016 کنار گذاشته شده و جستجو با رکوردهای [15]۳010016+1] تا 9 ge dls list[n-1] a گروه کامپیوتر ساختمانداده ها به نباری 

صفحه 287:
WY ۱-۷ درخت تصمیم گیری برای جستجوی 19292 

صفحه 288:
dist Verification) 2... yl) \-Y نوعا مقایسه لیستها جهت تعیین تست یکی بودن یا تعیین اختلاف آنها نوعی بررسی لیست به حساب می آید. مستئله وارسی لیست یک نمینه از جستجوی مکرر یک ليست است که هر کلید آن به عنوان کلید جستجو در ليست دیگری به کار می رود. گروه کامپیوتر ساختمانداده ها به نبارل ] صفحه: 288 

صفحه 289:
۱-۷ وارسی لیست(۷۵۳۵6۵1۵0۵ اعق) ‏ تلبع 1 ۷6۵۲1۴۷ : دو لیست را در نظر می گیرد که به صورت تصادفی مرتب شده لند . به سادگی می توان ثلبت نمود که زمان مجلنبی لین تلبع در بدترین حللت برابر با ‎O(MN)‏ ‏می باشد. تلبع ۷6۲۴۷2 : از همان ورودی تابع ۷6۲۴۷1 استفاده می کند با لین تفاوت که لیستها قبل از وارسی . مرتب می شوند. در بدترین حالت ۰ زمان لازم (۳) 0050۲6 ( صغم + (0) 150۲ + خواهد بود . )11561( ‏زمان لازم جهت مرتب کردن 83 ركورد از ليست اول‎ : ۲50۲۴ (n) (۲) 50۲6 : زمانلانم برلیمرتبک ردن19] ی کورد از لیستوم (1512) می‌باشد 

صفحه 290:
WY ‏مرتب سازی‎ ۲-۷ دو نوع از کاربردهای مهم مرتب سازی عبارتند از : + کمک در امر جستجو ۴ تطابق عناصر و وارده ها در يك ليست گروه کامپیوتر ] ساختمان‌داده ها به نباری ] صفحه: 290 

صفحه 291:
Insertion Sort,,> 2 ‏مرتب سازی‎ ۲-۷ در اين نوع مرتب سازی . در هر لحظه فقط یک رکورد در داخل ليست قابا. مسبت است نابراین رکورد؟ را در بين ركوردهاى مرتب شد,۱ :۶1۹۰۰۰۰/۲ *رار م, دهیم که رشته حاصل با اندازه 1 نیز موتب شده باشد ۰ وبگاک...> ی > از گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 291 

صفحه 292:
۳-۷ تحلیل تابع 50۲ ‎insertion‏ زمان محاسباتی جهت درج یک رک.رد به داخل لیست مرتب شده . () 0 خواهد بود. 4 9 زمان كل در بدترين حالت برابر است با ‎٠‏ a(S!) =0ur) 1-0 | گروه کامپیوتر ‎ob tuto.‏ نبا سنج 292 ] 

صفحه 293:
WY ‏مرتب سازی درجی(مثال)‎ ۳-۷ رشته (۱و۲و۳و۴و۵ ) را با 5 < 9 در نظر گرفته , بعد از عمل درج . داریم : ۱ © ۰ ۵ 6 61 

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

صفحه 295:
۴-۷ مرتب سازی سریع ۳ تفاوت مرتب سازى سريع با درجى در اين است كه در اين نوع مرتب سازی کلید مفصل رک در سمت راست با توجه به كل فايل قرار مى كيرد. بنابراين اككر كليد در نكل (5)1 قرار بكيرد : پس به ازای ‎JP Sy ‘ Aydyrry‏ می باشد. از ‎Et‏ رو ‎GSS NAD‏ « فایل اصلی به دو زیر فایل که شامل رکوردهای و می باشته ‎past‏ مى ‎Rostra‏ ‏آنجایی که رشته مرتب شده از تمام رکوردها در زیر فایل اول ممکن است در سمت چپ (5)1 و تمام رکوردها در زیر فایل دوم در سمت راست (5)1 قرار گیرند . لذا اين دو فایل می توانند به طور مستقل مرتب گردند. گروه کامپیوتر ساختمانداده ها به نبارل ] صفحه: 295 

صفحه 296:
WY ‏مرتب سازی سریع‎ ۲-۷ میانگین زمان محاسبه برای مرتب سازی سریع 2۳ رمع آبالک. قضه س فرض کنید(2)زمآن لازم برای مرتب سازی یک فایل با 13 ركورد باشد. بنابراین به بزای مقدار ثابت > داریم : گروه کامپیوتر ساختمان‌داده ها به نبارل || صفحه: 296 

صفحه 297:
۴-۷ مرتب سازی سریع ‎eal‏ سازی سریع جهت پیاده سازی عمل بازگشت پذیری به فضای پشته نیاز دارد. ‏حداکثر عمق باز گشت پذیری 8 109 خواهد بود و به فضای پشته (۲ ۵)109 نیاز خواهد بود. ‏| گروه کامپیوتر ‎ts btn‏ سنج 297 | ‎ ‎ ‎ ‎ 

صفحه 298:
۵-۷ زمان مرتب سازی بهینه ۳ O(nlog, n) . log,(4)+1 Q(alog, 1) گروه کامپیوتر ساختمان‌داده ها به نباری 8 صفحه: 298 

صفحه 299:
WY ‏درخت تصمیم گیری(منال)‎ ۵-۷ (wae گروه کامپیوتر ] ساختمان‌داده ها به نباری ] صفحه: 299 

صفحه 300:
۶-۷ مرتب سازی ادغام الگوریتم (0)1 : مراحل در (62)1 فضای ادغام هنگامی که تعداد رکوردها یعنی 0 مجذور کامل بوده و تعداد رکوردهای هر فایل مورد ادغام نیز مضربی از باشلد , در نظر گرفته می شود. گروه کامپیوتر ] ساختمانداده ها به نباری ] صفحه: 300 

صفحه 301:
۶-۷مراحل انگوریتم ‎OD)‏ مره ۱ زکور یز رگترین کلیدها را مشغتض کنید ین امر با ردییی و فایل نورد اتغام از سمت راست به چپ صورت می گیرد. مرحله ۲ : رکوردهای فلیل دوم که از مرحله اول شناسایی شده لند را با آن دسته از رکوردهایی که در سمت چپ ر کوردهلیی که از فایل اول, شناسایی شدند . تعویض کنید. لین امر موجب می شود که رکورد با بیشترین کلید . تشکیل یک بلاک مجاور را بدهد. مرحله ۲ : بلاک با بیتت‌ین رکورد رابابلاک های منتهی الیه سمت چپ تعویض کنید( مگر اینکه آن بلاک قبلا بلاک منتهی الیه سمت چپ باشد ) . بلاک منتهی الیه سمت راست را مرتب کنید. 

صفحه 302:
۶-۷مراحل الگوریتم (02)1 (ادامه) مرحله ۴ + تمام بلاک هابه جز بلاک با بزرگترین رکوردها رابه ترتیب غیر نزولی آخرین کلید در بلاک مرتب کنید. / مرحله ۵ : هر تعداد غیر مرحله ادغامى كه براى ادغام بلاك ( غير از بلاگ هلیی پا بزرگترین کلید) نیاز باشد را اجرا کنید. مرحله ۶ : بلاک با بزرگترین کلید را مرتب کنید. 

صفحه 303:
۶-۷ مرتب سازی ادغام تکراری( غیر باز گشتی ) گروه کامپیوتر |[ ساختمانداده هابه نبا أ صفحه: 303 

صفحه 304:
۶-۷ مرتب سازی ادغام باز گشتی 5 برای نسخه باز گشتی , ساختار رکورد خود را طوری تغییر می دهیم تا یک فیلد اتصال (101) را نیز دربر گیرد. الگوریتم ادغام در بدترین حالت و حالت میانگین به زمان محاسباتی برابر با (1۱ 109 0)۳ نیاز دارد. لين الگوریتم همچنین متناسب با تعداد رکوردهلیی که در فلیل باید هرتب.می شدند: نیازمند فضای اضأفی است. 

صفحه 305:
۷-۷ مرتب سازی 6۵0 3 روش مرتب سازی 1630] نیازمند تنها یک مقدار حافظه اضافی است و در همین حال . بدترین حللت و زمان متوسط آن برابر با ‎n)‏ ۱09 0)۳ خواهد بود.با وجود اينکه مرتب سازی 1630 کمی کندتر از مرتب سازی ادغام با استفاده از (00)10 فضای اضافی است ولی از مرتب سازی ادغام با استفاده از (0)1 فضای اضافی سریعتر می باشد. گروه کامپیوتر ساختمانداده ها به نباری ‏ صفحه: 305 

صفحه 306:
۷-۷ مرتب سازی 1620 5 برای مرتب سازی یک لیست ۰ ۲0-1 گذر بر روی لیست اعمال می شود. در هر كذر . اولين ركورد در 1198210 با آخرين رکورد تعویض می كردد . از آنجا كه اولين ركورد هميشه شامل بزركترين كليد است. اين رکورد با بزرگترین کلید را در محل 9 ام قرار می دهیم. در گذر دوم رکورد با دومین کلید بزرگ را در موقعیت ۷-1 قرار می دهیم و در نهلیت در آ امین گذر . رکوردبا آ امین کلید بزرگ را در موقعیت - 1۱ 1+ آ قرار می دهیم. گروه کامپیوتر ساختمان‌داده ها به نبارل ‏ صفحه: 306 

صفحه 307:
۸-۷ مرتب سازی مینا 5 در اینجا توجه خود را روی مرتب سازی ر کوردهایی معطوف می کتیم که دارای چندین کلید هستند. لین کلیدها دارای برچسب زا .به نحوی که نشان؟اهنده با اهمیت ترین کلید و مش کننده کم اهمیت ترین کلید است. ۷ (بااريشتريزيقم) روش های مختلف مرتب سازی : & ۱5۵( کم ارزش ترین رقم ) ساختمانداده ها به نباری ] صفحه. 307 گروه کامپیوتر 

صفحه 308:
۸-۷ مرتب سازی ‎Lie‏ لا در مرتب سازی مبنا با استفاده از مبنا ‏ کلید مرتب سازی را تجزیه می کنیم. لآ زمان محاسباتی کل برابراست با : ‎O(MAX_DIGIT (RADIX_SIZE + n )‏ لا انتخاب مبنا در زمان مرتب سازی مبنا موثر است . گروه کامپیوتر ساختمانداده ها به نبارل ] صفحه: 308 

صفحه 309:
‎٩-۷‏ مرتب سازی لیست و جدول ‏این مرتب سازی . لیست را به طور فیزیکی مرتب نکرده بلکه فیلدهای اتصال را برای نشان دادن ترتیب عناصر اصلاح می کند. ‏گروه کامپیوتر ساختمانداده ها به زباری 6 صفحه: 309 ‎ ‎ ‎ ‎ 

صفحه 310:
۱۰-۷ خلاصه مرتب سازی داخلی ‎is‏ # مرتب سازی درجی زملنی که لیست به صورت جزیی مرتب شده باشد , خوب کار می کند. # مرتب سازی ادغام بهترین روش برای بدترین حالات است. # مرتب سازی سریع بهترین میانگین را دارد. # عملکرد مرتب سازی مبنا بستگی به کلید و انتخاب مبنا دارد. #به ازای 20 > 9 مرتب سازی درجی (۱۳56۲۲109_50۲) سریعترین است. #برای مقادیر ‎٩‏ بین ۲۰ تا ۴۵ مرتب سازی سریع (01011650۲6) بهترین و سریع ترین می باشد. #برای مقادیر بزرگتر از 9 . مرب سازی ادغام(6_50۲ ۲06۲9 ) سریع ترین می باشد گروه کامپیوتر .ال ساختمانداده هابه نباری ‏ صفحه, 310 

صفحه 311:
WY ‏خلاصه مرتب سازی داخلی‎ ۱۰-۷ # مرتب سازی داخلی در هر زمان می تولند سه پلاک (چمیعا به طول ‎Yd.‏ ‏رکورد ) را در قالی رانش به ترتیب تا مرتب نماید. در این مورد می توان از مرتب سازی سریع یا مس استقاده کرد. | گروه کامپیوتر [لساختمانداده طايه نبا ‎[Bitte J‏ 

صفحه 312:
۱۱-۷ مرتب سازی خارجی (روش های مرتب سازی فایل های بزر در زمان خواندن يا نوشتن از / به دیسک زمان های زیرمهم است : ‎)١‏ زمان جستجو(1۳06] 5661 ) ‎(latency time) ,>6 ou; ۲‏ (Transmission time) Jusi ou; ۳ 

صفحه 313:
۱۱-۷ مرتب سازی خارجی ۱ معمولا روش مرتب سازی بر روی دستگاه های حافظه جانبی . مرتب سازی ادغام است. روش اساسا شامل دو مرحله يا مجزا است ‎)١‏ در ابتداء سگمنت های فلیل ورودی با استفاده از یک روش مرتب سازی داخلی مناسب . مرتب می شود. سگمنت های مرتب شده اصطلاحا رانش (۲۸۸۲۱) نامیده می شوند. ‏۲ در فاز دوم . رانش های تولید شده در فاز اول بر اساس الگوی درخت ادغام . ادغام شده و لین فرآیند تا هنگامی که تنها يك رانش باقى بماند ؛ ادامه بيدا مى كند. ‏گروه کامپیوتر ساختمازداده ها به زباره) || صفحه: 313 ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 314:
۱۱-۷ مرتب سازی خارجی برای تعیین زمان مورد نیاز مرتب سازی خارجی باید موارد زیر را در نظر گرفت محداکثر زمان جست: چعداکثر زمان جستجو عخداکثر زمان تاخیر مان لازم برای خواندن یا نوشتن یک بلاک ۲۵۰ رکوردی ‎(t, + t+ £,,) tig‏ ‎1S,‏ ۱ وومان لازم برای مرتب سازی داخلی ۷۵۰ رکورد - زمان لازم برای ادغام " رکورد از میانگیر ورودی به میانگیر خروجی | ‏گروه کامپیوتر اس اندادد ماب نبا ]رصن‎ J 

صفحه 315:
/ ۱۱-۷ ادغام 1 طرفه ۲ ‎Hog? 17‏ ادغام >1 طرفه بر روی ۲۷۱ رانش حداکثر نیازمند ‏گذر بر روی داده ها می باشد. ‎aie al ‏با افزایش درجه ادغام . در میزان ورودی و خروجی صرفه جویی می شود‎ ‏گروه کامپیوتر ‏ ساختمانداده هابه نباری ] صفحه: 315 ‎ ‎ ‎ ‎ 

صفحه 316:
۱۱-۷ بکارگیری میانگیر برای عملیات موازی "" اگر ‏ رلنش به وسیله یک ادغام > طرفه با هم ادغام شوند . واضح است که به حداقل > میانگیر ورودی و یک میانگیر خروجی جهت انجام عملیات ادغام نیاز داریم. اگر ورودی . خروجی و ادغام داخلی به طور موازی وهمزمان انجام شود . کافی نیست. گروه کامپیوتر ‏ |( ساختمانداده هابه نبا || صفحه: 316 

صفحه 317:
11-17 مراحل الكوريتم مربوط به مياذكير ‎١‏ مرحله ۱ :اولین بلاک هر یک از رلئش را وارد کرده و 16 صف بيوندى كه هر كدام داراى يى بلاک داده مى باشد را برقرار ميكنيم بلاکورودیباقی‌مانده را بسه دلخلکپشته پیوندی‌قرار دادم و بلاک‌های‌ورودیرا آزاد کنید همچنین!ا۵ را برلبر صفر قرار دهید مرحله ۲ : فرض کنید [25816۷]1] آخرین کلید وارد شده از رلنش آ باشد . فرض کنید که ۷ رانشی باشد که ۱2506۷ حداقل باشد. اگر 00 + ‎gay SY ST wl # lastkey[nextrun]‏ از رلنش ۵۱6۲۸۸ را مقداردهی اولیه کنید. 

صفحه 318:
۱۱-۷ مراحل الگوریتم مربوط به میانگیر ‎x‏ مرحله۲ : تلبع 106۲96 /۷۷۵1>ارا برای ادغام رکوردهلیی از > صف ورودی و قرار دادن آنها در داخل میانگیر خروجی لا0 مورد استفاده قرار دهید. ادغام تا زملنی ادامه می یلبد که يا میانگیر خروجی پر شود و یا رکورد 00+ داخل لا0 ادغام شود. اگر در طی لین ادغام « یکی از میانگیرهای ورودی . قبل از اینکه میانگیر خروجی پر شود و یا اينکه 00+ داخل 001 ادغام گردد. خللی شود. ۷۷31۲6۲96 بر روی همان صف به میانگیر بعدی منتقل و میانگیر خللی رابه پشته میانگیرهای خللی برگشت می دهد. هر چند . اگر میانگیر ورودی در همان زمان که میانگیر خروجی پر شده یا 00+ داخل 914 ادغام كردد . خللی شود . آنگاه میانگیر خللی در صف باقی مانده و 16۷/3۷۲06۲96 به میانگیر بعدی بر روی صف منتقل نمی شود . مگر اینکه ادغام خاتمه یابد. 

صفحه 319:
۱۱-۷ مراحل الگوریتم مربوط به میانگیر ۱ مرحله ۴ : تا کامل شدن عملیات ورودی/ خروجی صبر کنید. مرحله ۵ : اگر یک میانگیرورودی خوانده شد . آثرا برای رلتش مناسب به صف اضافه می کنیم. رانش بعدی را با استفاده از 1262۲۷1 تعیین کنید به نحوی که ‎Jfila> lastkey[nextrun]‏ كردد. مرحله ۶ ۰اگر 0 + ‎SY olST . ub # lastkey[nextrun]‏ بعدى از رانش ۲ را خوانده و میانگیر ورودی را آزاد کنید. اده ها به زباری گروه کامپیوتر 

صفحه 320:
۱۱-۷ مراحل الگوریتم مربوط به میانگیر مرحله ۷ : شروع به نوشتن محتویات میانگیر خروجی 018 نمایید. 01 را برابر با ۱- 00 قرار دهید( 1 - ناه = ‎(ou‏ مرحله ۸ :اگر رکورد با کلید 0 + داخل میانگیر خروجی ادغام نشده باشد . به مرحله ۳ مراجعه كنيد در غير لين صورت تا تکمیل عملیات نوشتن صبر نموده و سپس الگوریتم را اخائيه مهنا