آموزش ساختمان داده ها برای امتحان وکنکور

[mehdijj]

به درخواست یکی از دوستان عزیز این مطالب آموزشی رو گذاشتم انشاالله با نمره عالی این درس مهم رو پاس کنی

***ویرایش شده مهم
این مطالبی که ایجا گذاشتم از یه سایت گرفتم که خب اومده ساختمان داداه رو توضیح داده با تمومه جزئیات همه چی هم داره اینجا شلوغ میشه اگه همه مطالب رو بذارم

**http://www.hpkclasses.ir/Courses/DataSt ... s0000.html**

مفاهيم مقدماتي
جهت دستيابي و پردازش سريع تر به داده ها معمولا آنها را طبق يک مدل رياضي يا منطقي سازماندهي مي کنند.

داده
نوع داده
نوع داده انتزاعي
ساختمان داده
عمليات روي ساختمان داده


داده
داده يک نمايش باينری از يک موجوديت منطقی قابل ذخيره سازی در حافظه کامپيوتر است.

داده ها درواقع مقاديری هستند که بعنوان ورودی به يک الگوريتم داده می شود تا پردازشی روی آنها انجام شود.

پردازش داده
هر نوع عملياتي، نظير محاسبات، مقايسه، جستجو، حذف يا تغيير داده كه توسط برنامه روي داده ها انجام مي پذيرد پردازش داده محسوب می شود.


نوع داده
داده ها نمايشی از اطلاعات در حافظه می باشند. نحوه نمايش يك داده خاص در حافظه توسط نوع داده (Data Type) آن مشخص مي شود. نوع داده مجموعه اي از مقادير و مجموعه اي از عملياتي که روي اين مقادير اجرا مي شود را تعيين می کند.

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

پياده سازی می تواند سخت افزاری يا نرم افزاری باشد:

• در پياده سازی سخت افزاری مدارات لازم برای اجرای عمليات طراحی می شود.
• در پياده سازی نرم افزاری برنامه ای برای تفسير رشته های بيتی و انجام عمليات موردنياز با استفاده از دستورات سخت افزاری نوشته می شود.


وقتی نوع داده پياده سازی شد برنامه نويس می تواند از آنها برای حل مسائل استفاده کند.

انواع داده ای که به صورت سخت افزاری طراحی می شوند انواع داده ابتدايي (Primitive Data Type) ناميده می شوند. هر كامپيوتري داراي مجموعه اي از انواع داده ابتدايي است.

يك زبان برنامه نويسی سطح بالا امكانات خوبي را برای تعريف نوع متغير در اختيار برنامه نويس قرار مي دهد. تعريف نوع داده متغير مشخص مي کند محتويات حافظه چگونه بايد تفسير شود و كامپايلر را قادر مي سازد كه عملكرد متناسب با متغيررا تشخيص دهد.

هر زبان برنامه نويسی مجموعه ای از انواع داده را تعريف می کند.


نوع داده انتزاعي
جدا از جنبه های سخت افزاری، اگر مفهوم نوع داده بر اساس آنچه برنامه نويس می خواهد به صورت نرم افزاری پياده سازی شود نوع داده انتزاعی (Abstract Data Type) ناميده می شود.

اگر مفهوم نوع داده از توانائيهای سخت افزار جدا شود، تعداد نامحدودی از انواع نوع داده را می توان درنظر گرفت.


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

انواع ساختمان داده
1. ساختمان داده خطي : يك ساختمان داده را خطي مي گويند هرگاه عناصر آن تشكيل يك دنباله را دهند، به بيان ديگر يك ليست خطي باشند.
براي نمايش ليست خطي دو روش اساسي وجود دارد:
• رابطه خطي بين عناصربه وسيله خانه هاي متوالي حافظه نمايش داده مي شود(آرايه).
• رابطه خطي بين عناصر به وسيله اشاره گرها نمايش داده مي شود(ليست پيوندی).
2. ساختمان داده غير خطي مانند درخت ها و گراف ها


عمليات روي ساختمان داده
داده هايي كه در ساختمان داده ها ظاهر مي شوند به وسيله عمليات مشخصي پردازش مي شوند. در واقع ساختمان داده خاصي كه برنامه نويس براي يك مسئله انتخاب مي كند بستگي زيادي به ميزان عمليات خاصي دارد كه در آن مسئله انجام مي شود. برخي از اين عمليات كه زياد مورد استفاده قرار مي گيرند عبارتند از :

1. پيمايش : دقيقا يک بار دسترسي به کليه داده های ساختمان داده
2. جستجو : يافتن يك داده يا مجموعه ای از داده ها با شرايط خاصي درون ساختمان داده
3. اضافه : افزودن يك داده جديد به ساختمان داده.
4. حذف : حذف يك داده از ساختمان داده.
5. مرتب سازي : قرار دادن داده ها در كنار هم با يك نظم معين.
6. ادغام : تركيب داده هاي دو ساختمان داده مرتب و بدست آوردن يک ساختمان داده مرتب ديگر
7. اتصال : پيوند دو ساختمان داده به يكديگر
8. كپي : تهيه يك نسخه از ساختمان داده

[mehdijj]

الگوريتم

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

تعريف
نحوه بيان الگوريتم
ارزيابی کارائی الگوريتم ها
پيچيدگی حافظه
پيچيدگي زماني



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

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

يک الگوريتم پنج خاصيت زير را بايد دارا باشد:

1. متناهی بودن. يک الگوريتم بايد هميشه بعد از تعدادی گام به پايان برسد.
2. صراحت. فعلی که در هر قدم الگوريتم انجام می گيرد بايد مختصر، صريح و غير مبهم باشد.
3. ورودی. مقاديری هستند که ابتدا، قبل از شروع، به الگوريتم داده می شوند.
4. خروجی. مقاديری هستند توسط الگوريـم توليد می شود و رابطه مشخصی با ورودی ها دارند.
5. کارائی. دستورات الگوريتم درحد کفايت بايد ساده و دقيق باشند تا يک انسان مانند يک روبات بتواند آنها را با استفاده از قلم و کاغذ بدون احتياج به فکر کردن در زمان معينی انجام بدهد.


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

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


نحوه بيان الگوريتم
الگوريتم های می توانند با نمادهای مختلفی بيان شوند:

• زبان طبيعی. استفاده از عبارات زبان طبيعی برای بيان الگوريتمی ممکن است باعث طولانی و مبهم شدن آن بشود و برای الگوريـتم های پيچيده و فنی بندرت استفاده می شود.
• زبان های برنامه نويسی. در ابتدا بيان الگوريتم با زبان های برنامه نويسی موجود طرفدار داشت.
• Pseudo Code و فلوچارت. راه های ساختيافته ای برای نمايش الگوريتم، که درحين استقلال از زبان برنامه نويسی خاصی، از ابهام پرهيز می کنند.


امروزه الگوريتم ها معمولا با استفاده از Pseudo Code در يک زبان برنامه نويسی که معمولا پياده سازی نشده بيان می شوند. در طی اين درس از کدهای ساختگی که در ادامه شرح داده می شوند برای بيان الگوريتم ها استفاده می شود.

variable := value

اختصاص مقداری به يک متغير را نشان می دهد.

if (condition) then
statements1
else
statements2
end if


برای بيان تصميم گيری، اگر شرط برقرار باشد عبارت 1 انجام می گيرد و اگر برقرار نباشد عبارت 2

while (condition)
statement
end while


برای نمايش حلقه تکرار، اگر شرط برقرار باشد دستورات تکرار می شوند.

repeat until (condition)
statement
end loop


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

for (counter:=value1 to value2 )
statement
end for


برای نمايش تکرار عبارتی به تعداد معينی، شمارنده از مقدار1 شروع شده در هربار تکرار يک واحد به آن اضافه می شود تا به مقدار2 برسد. برای شمارش معکوس به جای to از down to قرار می گيرد.

انتهای الگوريتم توسط کلمه end مشخص می شود.


مثال. الگوريتم زير به متغير x مقادير 1 تا 10 بجز عدد 5 را اختصاص می دهد.

x:=0
while (x < 10)
if x = 4 then
x := x + 2
else
x := x + 1
end if
end while
end


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

آناليز کارائی يک تخمين اوليه است با دو معيار پيچيدگی فضائی (space complexity) و پيچيدگی زمانی (time complexity) سنجيده می شود که رفتار الگوريتم را در زمان اجرا با مجموعه ای از ورودی های منتخب توصيف می کنند.

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


پيچيدگی حافظه
پيچيدگی حاظه ای ميزان فضائی از حافظه است که برنامه برای اجرای کامل به آن نياز دارد. فضای مورد نياز در هربرنامه مجموع قسمت های زير است:

• بخش ثابت فضا که معمولا شامل فضای دستورالعمل، فضای متغيرهای با اندازه ثابت و فضای لازم برای ذخيره ورودی و خروجی های برنامه است.
• بخش متغير فضا شامل فضای پشته و فضای موردنياز برای مقادير متغيرهائی که اندازه آنها بستگی به مسئله و مشخصات ورودی دارد.


در تحليل فضای لازم روی تخمين بخش متغير تاکيد نداريم زيرا برای هرمسئله ابتدا بايد مشخصات موردی را تعيين کنيم که کار دشواری است.


پيچيدگی زمانی
زمان اجرا مقدار زمانی از کامپيوتر است که برنامه برای اجرای کامل مصرف می کند. برای محاسبه پيچيدگی زمان الگوريتم ابتدا تعداد قدم های الگوريتم به صورت تابعی از اندازه مسئله مشخص می شود، برای انجام اين کار تعداد تکرارعمليات اصلی الگوريتم محاسبه می شود و به صورت تابع f(n) (که n تعداد ورودی هاست) بيان می شود. سپس تابع g(n)، که مرتبه بزرگی تابع f(n) را وقتی اندازه ورودی به اندازه کافی بزرگ است نشان می دهد، بدست می آيد. در نهايت پيچيدگی الگوريتم برای نشان دادن رفتار الگوريتم با ورودی های مختلف با استفاده از نمادها O ، Θ و Ω بيان می شود.

تعريف Big-O (حدبالا)

تابع f(n) را نظر بگيريد که برای کليه n≥0 است، می گوئيمf(n) = O(g(n)) اگر ثابت های مثبت n0 و c وجود داشته باشند به طوريکه از يک n0 به بعد هميشه f(n)≤ cg(n) برقرار باشد.

اين نماد حدبالائی برای تابع f(n) می دهد و وقتی بکار می رود که رفتار الگوريتم بدترين حالت و بيشترين زمان اجرا را برای مقادير معين ورودی دارد

تعريف Big-Ω (حدپائين)

تابع f(n) را نظر بگيريد که برای کليه n≥0 است ، می گوئيم f(n) = Ω (g(n)) اگر ثابت های مثبت n0 و c وجود داشته باشند به طوريکه از يک n0 به بعد هميشه f(n)≥ cg(n) برقرار باشد.

اين نماد حد پائينی برای تابع f(n) می دهد و وقتی بکار می رود که رفتار الگوريتم بهترين حالت و کمترين زمان اجرا را برای مقادير معين ورودی دارد

تعريف Big-Θ (حدمتوسط)

تابع f(n) را نظر بگيريد که برای کليه n≥0 است، می گوئيم f(n) = Θ(g(n)) اگر ثابت های مثبت n0، c1 و c2 وجود داشته باشند به طوريکه از يک n0 به بعد هميشه c1g(n) ≤f(n) ≤ c2g(n) برقرار باشد.

اين نماد حدمتوسطی برای تابع f(n) می دهد و زمان اجرای الگوريتم را به صورت ميانگينی از تعداد عمليات انجام شده با کليه نمونه ورودی های مسئله نشان می دهد.



مثال. الگوريتم مرتب سازی حبابی را درنظر بگيريد.

for (i:=1 to n-1)
for (j:=1 to n-1)
if aj>aj+1 then exchange(aj,aj+1)


با درنظر گرفتن عمل مقايسه بعنوان عملگر اصلی، دستور If در الگوريتم فوق (n-1)2 بار تکرار می شود. بنابراين f(n)= (n-1)2=n2-2n+1 و طبق قضيه g(n)=n2 است. بنابراين پيچيدگی الگوريتم فوق برابر با O(n2) می باشد.


نکته. اگر زمان الگوريتم وابسته به ورودی نباشد با نماد O(1) نشان داده می شود.

نکته. بايد به اندازه کافی الگوريتم را درک کرده باشيم تا بهترين و بدترين رفتار را توليد و محاسبه کنيم. چون برآورد رفتار آماری ورودی ها امری دشوار است، در اکثر موارد به بدترين حالت قناعت می کنيم.

نکته. اگر الگوريتم شامل بخش های مختلفی باشد که هر قسمت پيچيدگی متفاوتی دارد، مرتبه بزرگی هر قسمت را پيدا کرده و بزرگترين مرتبه را بعنوان پيچيدگی کل الگوريتم درنظرمی گيريم.


غالبا پيچيدگی g(n) يکی از توابع زير است: n (پيچيدگی خطی)، log n (لگاريتمی)، na (چندجمله ای) و an که a≥2 (نمائی).

در زير مربته اجرائی چند تابع به ترتيب صعودی نوشته شده است.

O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O( n3) < O(2n) < O(n!)

[mehdijj]

آرايه

يکي از پرکاربردترين ساختمان های داده آرايه است که اغلب برای پياده سازی داده های انتزاعی خطی بکار می رود

تعريف آرايه
آرايه هاي يک بعدی
آرايه هاي دو بعدی
محاسبه فضا و آدرس
آرایه های پويا
الگوريتم های درج و حذف


تعريف آرايه
آرايه (array) ليست متناهی از عناصر داده‌ای هم نوع است

محل يک عنصر درون آرايه توسط انديس (Index) معين می شود. عنصر ai در مكان i ام آرايه قرار مي گيرد به اين ترتيب مي توان به صورت تصادفي مقدار آرايه را بازيابي كرد. البته با روش ترتيبي هم مي توان به مقادير عناصر ليست دسترسي پيدا كرد.

به عناصر آرايه ممکن است به كمك مجموعه اي از انديس ها مراجعه شود.

فرم كلي تعريف آرايه در زبان برنامه نويسی Pascal به صورت زير است:

ArrayName : ARRAY [IndexType1, IndexType2,…, IndexTypen] OF Type;

IndexType مجموعه انديس را تعيين می کند و می تواند از هر نوع اسکالری باشد. اگر دستور کامپايلر {$R+} فعال نباشد کنترلی روی انديس های غير مجاز نيست. اگر فعال باشد در صورت استفاده از انديس غيرمجاز پيغام خطای Range Check Error صادر می شود.

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

Type ArrayName[Size1] [Size2] …[Sizen];

Size تعداد عناصر يک بعد آرايه را تعيين می کند. در زبان C کليه انديس ها عددی هستند و از صفر شروع می شوند (0-based indexing)و کنترلی روی محدوده انديس ها وجود ندارد.

دراکثر زبان ها به آرايه به صورت ايستا حافظه اختصاص می دهند و اندازه آرايه در طول اجرای برنامه ثابت است. مگر اينکه حافظه پويا صريحا توسط برنامه نويس استفاده شود.


آرايه هاي يک بعدی
آرايه يک بعدی مجموعه متناهي از زوج ها به صورت ‹ انديس،مقدار› است. بدين معنی که، به ازاي يك انديس يک مقدار مربوط به آن وجود دارد.

براي تعريف آرايه يك بعدي يک مجموعه انديس تعريف می شود.


مثال(C). آرايه num با 20 عنصر صحيح تعريف شده است. عناصر آرايه در خانه های num[0], num[1], num[2],…, num[19] ذخيره مي شوند.

int num [20] ;

مثال(C). آرايه کاراکتری num با 4 عنصر تعريف و مقداردهی شده است.

Char num[4]={'d','a','t','a'};
يا
Char num[4]={"data"}; (اگه مشکل داشتید واسه خوندن توی نت پد کپی کنید درست میشه)

آرايه هاي دو بعدی
يك آرايه دو بعدی مجموعه اي با m×n عنصر داده اي است كه هر عنصر آن با يك جفت انديس مشخص مي شود.

آرايه دو بعدي را مي توان به جدولي تشبيه كرد كه داراي m سطر و n ستون است. هر سطر شامل عناصري است كه انديس هاي اول آنها برابر است و هر ستون شامل عناصري هستند كه انديس هاي دوم آنها برابر هستند.

آرايه هاي دوبعدي به عنوان ماتريس به كار مي روند.

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

مثال(Pascal). آرايه Table از نوع اعداد حقيقي با 5 سطر و 4 ستون تعريف شده است.

Table : Array[1..5,3..6] of Real;
يا
Table : Array[1..5] of Array [3..6] of Real;

مثال(C). آرايه A از نوع اعداد صحيح با 3 سطر و 4 ستون

int A[3][4];

مثال(C). آرايه دوبعدی num را می توان به دو صورت مقداردهی اوليه کرد.

int num [4][3]={‍‌{15,6,13},{9,17,2},{4,5,4},{10,11,12}} ;
يا
int num [4][3]={15,9,13,9,17,2,4,5,4,10,11,12};

آرايه هاي چندبعدي
آرايه nبعدی مجموعه اي از m1×m2×…×mn عنصر داده اي است كه هر عنصر توسط n‌ انديس نظير i1,i2,…,in مشخص مي شوند. آرايه هاي چند بعدي در حافظه به صورت دنباله اي از خانه هاي پشت سر هم ذخيره مي شوند.

[obalitjoon]

ادامه