پاورپوینت کامل ساختمان داده ها به زبان C 330 اسلاید در PowerPoint

توجه : این فایل به صورت فایل power point (پاور پوینت) ارائه میگردد

 پاورپوینت کامل ساختمان داده ها به زبان C 330 اسلاید در PowerPoint دارای ۳۳۰ اسلاید می باشد و دارای تنظیمات کامل در PowerPoint می باشد و آماده ارائه یا چاپ است

شما با استفاده ازاین پاورپوینت میتوانید یک ارائه بسیارعالی و با شکوهی داشته باشید و همه حاضرین با اشتیاق به مطالب شما گوش خواهند داد.

لطفا نگران مطالب داخل پاورپوینت نباشید، مطالب داخل اسلاید ها بسیار ساده و قابل درک برای شما می باشد، ما عالی بودن این فایل رو تضمین می کنیم.

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل می باشد و در فایل اصلی پاورپوینت کامل ساختمان داده ها به زبان C 330 اسلاید در PowerPoint،به هیچ وجه بهم ریختگی وجود ندارد

---

بخشی از مطالب داخلی اسلاید ها

پاورپوینت کامل ساختمان داده ها به زبان C 330 اسلاید در PowerPoint

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

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

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

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

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

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

اسلاید ۱۰: ۲-۱ تعریف الگوریتمالگوریتم مجموعه ای از دستورالعمل ها است که اگر دنبال شوند، موجب انجام کار خاصی می گردد

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

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

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

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

اسلاید ۱۵: ۳-۱ آرایه ، ساختار و نوع دادهمجموعه ای از عناصر از یک نوع داده می باشدمجموعه ای از عناصر است که لزومی ندارد داده های آن یکسان باشدمجموعه ای از انواع داده مقصد(object) و عملکردهایی است که بر روی این نوع داده ها عمل می کنندآرایهساختارنوع داده

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

اسلاید ۱۷: ۳-۱ نوع داده مجردتوابع یک نوع داده به گروه های زیر تقسیم می شوند:۱- ایجادکننده/ سازنده۲- تبدیل کنندگان۳- مشاهده کنندگان / گزارش کنندگان

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

اسلاید ۱۹: ۴-۱ میزان حافظه یا پیچیدگی فضای یک برنامهمیزان حافظه یا پیچیدگی فضای یک برنامه مقدارحافظه مورد نیازبرای اجرای کامل یک برنامه است.میزان یا پیچیدگی زمان یک برنامه مقدار زمان کامپیوتر است که برای اجرای کامل برنامه لازم است.

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

اسلاید ۲۱: ۴-۱ میزان حافظه(ادامه)نیازمندیهای فضای کلنیازمندیهای فضای ثابت نیازمندیهای فضای متغیر

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

اسلاید ۲۳: ۴-۱ مرحله برنامهیک مرحله برنامه ، قسمت با معنی برنامه است ( از لحاظ معنایی یا نحوی) که زمان اجرای آن مستقل از خصیصه های نمونه باشد

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

اسلاید ۲۵: ۴-۱علامت گذاری مجانبی(O، ،)(Asymptotic)O(1) : زمان محاسبه ثابتی را نشان می دهد O(n) : یک تابع خطی نامیده می شود : تابع درجه دو نامیده می شوداگر باشد، بنابراین خواهد بود قضیه :

اسلاید ۲۶: ۴-۱ علامت گذاری مجانبی(O، ،)(Asymptotic)تعریف:]امگا [: f(n)=(g(n)) می باشد(خوانده می شود f(n) امگای g(n) اگر و فقط اگر به ازای مقادیر ثابت مثبت c و n0 ، f(n)cg(n) باشد(برای تمام مقادیر n به شرطی که nn0 باشد)اگر باشد، و بنابراین خواهد بود قضیه :

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

اسلاید ۲۸: ۴-۱ علامت گذاری مجانبی(O، ،)(Asymptotic)اگر باشد، و بنابراین خواهد بود قضیه :

اسلاید ۲۹: ۴-۱ مثال(پیچیدگی جمع ماتریس ها)

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

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

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

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

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

اسلاید ۳۵: ۱-۲ آرایه هاآرایه در زبان C به صورت مثال در زیر آمده است :int list [5]در زبان C تمام آرایه ها از اندیس ۰ شروع می شوند.نکته

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

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

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

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

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

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

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

اسلاید ۴۳: ADT ماتریس اسپارسبه طور کلی در ریاضیات ، یک ماتریس شامل m سطر و n ستون بوده و می تواند مانند شکل زیر نمایش داده شود.۲۷-۳۴۶۸۲۲-۱۲۸۹۴۸۲۷۴۷row 0row 1row 2row 3row 4col1col2col3

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

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

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

اسلاید ۴۷: ترانهاده یک ماتریسالگوریتم بیان شده نشان می دهد که باید تمام عناصر در ستون ۰ را پیدا و آنها را در سطر ۰ ذخیره کرد همچنین تمام عناصر ستون ۱ را پیدا و در سطر ۱ قرار داد و همین فرآیند را ادامه داد. از آنجا که ماتریس اولیه سطری بوده لذا ستون های داخل هر سطر از ماتریس ترانهاده نیز به صورت صعودی مرتب می شود.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

اسلاید ۶۶: جایگذاری به یک پشته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;}

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

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

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

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

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

اسلاید ۷۲: حذف عنصری از یک صف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];}

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

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

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

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

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

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

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

اسلاید ۸۰: الگوریتم تبدیل infix به postfixمی توان الگوریتمی برای تبدیل یک عبارت infix به postfix به صورت زیر بیان نمود :۱- پرانتزگذاری کامل عبارات۲- انتقال همه عملگرهای دودویی به نحوی که با پرانتز بسته مربوطه سمت راست آن تعویض شوند۳- حذف تمام پرانتزها

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

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

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

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

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

اسلاید ۸۶: ۲- وقتی دارای چندین لیست مرتب شده با طول های متفاوت هستیم. باذخیره کردن هر لیست در آرایه ای با حداکثر اندازه ، حافظه هدر می رود۳- با نگهداری لیستها در یک آرایه ، انتقال حجم زیادی از داده ها لازم است.مشکلات نمایش ترتیبی۱- حذف و درج عناصر در آرایه ها بسیار وقت گیر است

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

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

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

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

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

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

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

اسلاید ۹۴: مثالمراحل درج کلمه mat بین cat و sat به صورت زیر است : ۱- گره ای را که اخیرا استفاده نشده در نظر گرفته ، فزض کنید که آدرس آن paddr باشد.۲- فیلد داده این گره را برابر با mat قرار دهید۳- فیلد اتصال paddr را طوری تنظیم کنید که به ادرسی که در فیلد اتصال گره حاوی cat می باشد، اشاره کند۴- فیلد اتصال گره حاوی cat را طوری تنظیم کنید که به paddr اشاره کند.

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

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

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

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

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

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

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

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

اسلاید ۱۰۳: حذف از یک پشته پیوندی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 ;}

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

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

اسلاید ۱۰۶: نمایش چند جمله ای ها به صورت لیست های تک پیوندیدر اینجا می توان هر جمله را به صورت یک گره نمایش داد. در این ارتباط هر گره دارای سه فیلد برای نمایش ضریب ، توان و اشاره گری به گره بعدی می باشد.مثال۳۱۴.۲۸.۱۰NULLa

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

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

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

اسلاید ۱۱۰: الگوریتم تعیین کلاس های هم ارزیالگوریتم تعیین کلاس های هم ارزی ، دو مرحله است :در مرحله اول ، زوج های هم ارزی <i ،j> ، را خوانده و ذخیره می کند.در مرحله دوم از ۰ شروع کرده و تمام زوج های که به شکل < 0 ،