تعریف ساختمان داده

عبارت است از ساختارهای دادهای که درحافظهء اصلی کامپیوتر در نظرمی گیریم تا بتوانیم الگوریتمهای برنامه نویسی را بر روی انها به شکل مناسب پیاده سازی نماییم.

آرایه:

مجموعه ای از داده ها هستند که نوعشان یکسان است به عنوان مثال:اگر 10 عدد صحیح را بخواهیم در حافظه اصلی قرار دهیم بجای انکه 10 متغیر (int) تعریف بکنیم یک آرایه (int) تعریف می کنیم که 10 خانه داشته باشد .

　

　

Int b [3][4] = آرایه 2 بعدی : مثال

(ساختمان ب 3 تا طبقه دارد و دارای 4 تا خانه است.)

آرایه های 2 بعدی را ماتریس نیز می گویند .

در آرایه های 2 بعد به بالا برای اینکه بتوانیم عناصر را به صورت صحیح از خانه هایی که ذخیره شده اند بازیابی نماییم بایستی مشخص گردد که اگر ذخیرهء عناصر به شکل سطری است بازیابی آنها نیز به شکل سطری باشد و اگر ستونی است بازیابی انها به صورت ستونی باشد.

　

　

　

روش سطری پیمایش و ذخیرهء آرایه ها :

: ( پیمایش سطری )b11 , b12 , b13 , b14 , b21 , b22 , b23 , b24 , b31 , b32 , b33 , b34

در پیمایش سطری آرایه ها اندیسهای خانه های آرایه از سمت راست تغییر می کنند بطوریکه اندیس سمت چپ به صورت ثابت باقی می ماند و یک واحد یک واحد به اندیس سمت راست اضافه می شود تا زمانیکه به ماکسیمم مقدار خود برسد که در این لحظه یک واحد به اندیس سمت چپ اضافه می شود و دوباره اندیس سمت راست شروع به افزایش می یابد واین کار تا زمانی ادامه پیدا می کند که هر 2 اندیس به ماکسیمم مقدار خود برسد.

مثال : ماتریس 3 بعدی زیر را به صورت سطری پیمایش کنید:

Int a [3][4][3]

پیمایش سطری : (a) : a111 , a112 , a113 , a121 , a122 , a123 , a131 , a132 , a133 , a141 , a142 , a143 , a211 , a212 , a213 , a221 , a222 , a223 , a231 , a232 , a233 , a241 , a242 , a243 , a311 , a312 , a313 , a321 , a322 , a323 , a331 , a332 , a333 , a341 , a342 , a343

　

　

روش ستونی پیمایش ذخیره ها :

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

پيمايش ستونی

b11 , b21, b31 , b12 , b22 , b32 , b13 , b23 , b33 , b14 , b24 , b34

پیمایش ستونی : (a) : a111 , a211 , a311 , a121 , a221 , a321 , a131 , a231 , a331 , a141 , a241 , a341 , a112 , a212 , a312 , a122 , a222 , a322 , a132 , a232 , a332 , a142 , a242 , a342 , a113 , a213 , a313 , a123 , a223 , a323 , a133 , a233 , a333 , a143 , a243 , a343

ماتریس اسپارس (خلوت - پراکنده) :

ماتریسی است که اکثریت عناصر ان مقدار ثابت و غیر قابل محاسبه ( معمولا صفر) می باشد و تنها تعداد کمی از خانه های ان داده ها به درد بخور می باشند بنابراین فضای بسیار زیادی از حافظه اصلی را برای ذخیره کردن این تعداد کم داده ها تلف می کنیم .

مثال :

0 0 0 2 0

0 0 3 0 1

0 0 0 0 0

0 18 0 0 0

به عنوان مثال در ماتریس فوق برای ذخیره کردن چهار عنصر غیر صفر یک ماتریس ( 5 * 4 ) و 20 خانه از حافظه را تلف کرده ایم روشی که برای ذخیرهء بهینهء این نوع ماتریسها استفاده می شود بدین صورت است که یک ماتریس در نظر می گیریم که همیشه 3 ستون خواهد داشت و به تعداد عناصر غیر صفر سطر خواهد داشت که در هر سطر در ستون اول شمارهء سطر مربوط به عنصر غیر صفر ودر ستون دوم شمارء مربوط به ستون عنصر غیر صفر ودر ستون سوم مقدار عنصر غیر صفر را ذخیره خواهیم کرد

که کاهش قابل توجهی در میزان حافظه مصرفی خواهیم داشت.

i j value

1 2 2

2 1 1

2 3 3

4 4 18

مثال : 2 ماتریس اسپارس زیر را با هم دیگر جمع بزنید:

　

5 2 1 1 3 2 5 2 1

9 3 3 5 3 3 3 4 3

11 1 4 = 6 2 4 + 11 1 4

9 2 4 11 1 5 3 2 4

1 3 2 5 5 5

11 1 5

5 5 5

　

نکته کلیدی :

1 1 1 1 1 1 4 3 2

8 3 2 4 3 2 12 3 3

12 3 3 = 1 2 4 + 5 4 3

5 4 3 7 5 5 1 2 4

0 2 4 6 5 5

13 5 5

　

نکته :

A 3 4

: پیمایش سطری for i: =1 to 3 do

for j: =1 to 4 do

write (a i,j ) ;

　

پیمایش ستونی : for j: =1 to 4 do

for i: =1 to 3 do

write (a i,j ) ;

　

مثال : با استفاده ازfor های تو در تو یک ماتریس 3 بعدی

( 2* 3 * 4 ) به 2 روش سطری و ستونی پیمایش کنید:

　

: پیمایش سطری for i: =1 to 4 do

for j: =1 to 3 do

for k: =1 to 2 do

write ( a i,j,k ) ;

　

　

پیمایش ستونی : for k: =1 to 2 do

for j: =1 to 3 do

for i: =1 to 4 do

write ( a i,j,k ) ;

　

　

مثال : با استفاده از for های تو در توبرنامه ای بنویسید که 2 ماتریس (2 * 3 * 4) رابا یکدیگر جمع کرده ودر ماتریس سوم قرار دهد:

: پیمایش سطریfor i: =1 to 4 do

for j: =1 to 3 do

for k: =1 to 2 do

c i,j,k = b i,j,k + a i,j,k

write ( c i,j,k ) ;