سوال در مورد آرایه ها در ساختمان داده ها

v.b.f1 · May 6, 2011

با سلام خدمت دوستان

یه توضیحی در مورد ساختمان داده ها می خوام

درمورد آرایه ها
تعداد عناصر
فرمولش اینه

کد:

u1-L1+1

میزان حفظه مورد نیاز آرایه

کد:

u1+L1+1*n

و آدرس عنصر ارایه یک بعدی

کد:

i-L1*n+*

hoceyn · May 6, 2011

خیلی سادست. مثلا می خوای بگی چنتا عدد بین 10 و 15 هست؟ می نویسی

15-10

حالا اگه خود خونه ی 15 هم حساب شه با یک جمعش می کنی.

15-10+1

دقیقا آرایه ام اینطوره. آخری منهای اولی به علاوه 1

U-L+1

بقیه خوانا نیست. لطفا ویرایشش کن. مثلا این یعنی چی؟!

i-L1*n+*

the_king · May 6, 2011

v.b.f1 گفت:
با سلام خدمت دوستان

یه توضیحی در مورد ساختمان داده ها می خوام

درمورد آرایه ها
تعداد عناصر
فرمولش اینه

کد:

u1-L1+1

میزان حفظه مورد نیاز آرایه

کد:

u1+L1+1*n

و آدرس عنصر ارایه یک بعدی

کد:

i-L1*n+*

خانه های آرایه توسط اندیس مشخص می شوند که یک عدد صحیح است، مثلا خانه شماره 5 یعنی خانه ای که
اندیس اش 5 است. هر آرایه ای یک اندیس شروع و یک اندیس پایان دارد که شماره های معتبر اندیس بین ایندو
خواهند بود.
L1 اندیس شروع آرایه است و L اختصاری Low یعنی پایین است .در بعضی زبان ها اندیس شروع همیشه 0 است
ولی در زبان های دیگر می تواند هر عدد مثبتی باشد. مثلا اگر L1 برابر 4 باشد، اولین اندیس آرایه 4 است.

U1 اندیس پایان آرایه است و U اختصاری Up یعنی بالا است. مقدار U1 همیشه مساوی با بزرگتر از L1 است.

اگر اندیس شروع یک آرایه (L1) برابر 1 و اندیس پایان آرایه (U1) برابر با 5 باشد، اندیس های معتبر آرایه مقادیر
1 و 2 و 3 و 4 و 5 خواهند بود. تعداد خانه های آرایه برابر است با 5 خانه که از فرمول زیر مشخص می شود :

کد:

U1 - L1 + 1 = 5 - 1 + 1 = 5

در آرایه های ساده، طول داده هر خانه بر حسب بایت ثابت و مشخص است. مثلا برای هر خانه از آرایه فرضا 4 بایت
در نظر گرفته می شود. اگر ما تعداد خانه های آرایه و طول داده هر خانه بر حسب بایت را بدانیم طبیعتا
می توانیم با ضرب کردن ایندو عدد در هم میزان حافظه لازم برای ایجاد کردن کل آرایه را بدست بیاوریم.
مثلا اگر تعداد خانه های آرایه 5 خانه و هر خانه 4 بایت باشد، جمعا برای این آرایه به 20 بایت فضا احتیاج داریم.
اگر طول داده یک خانه از حافظه را با N مشخص کنیم، یعنی در مثال N را 4 در نظر بگیریم، با استفاده از فرمول
قبلی میزان حافظه کل آرایه برابر است با :

کد:

(U1 - L1 + 1) * N = (5 - 1 + 1) * 4 = 5 * 4 = 20

اگر آدرس شروع آرایه در حافظه را 0 فرض کنیم، داده ای که در اولین خانه آرایه نوشته می شود در آدرس 0
ذخیره خواهد شد. چون هر خانه از آرایه N بایت طول دارد، داده های خانه دوم آرایه N بایت بعد از داده های
خانه اول ذخیره خواهد شد، یعنی در آدرس N و به همین ترتیب داده های خانه سوم در آدرس N + N و ...
طبق این روال اگر بخواهیم بدانیم که داده های خانه ای با اندیس i در چه آدرسی از حافظه نوشته می شود،
فرمول اش چنین خواهد بود :

کد:

(i - L1) * N

مثلا اگر طول داده هر خانه (N) برابر 4 و اندیس شروع آرایه (L1) برابر 1 باشد، داده های خانه اندیس 1
در آدرس 0 نوشته خواهند شد :

کد:

(i - L1) * N = (1 - 1) * 4 = 0 * 4 = 0

و داده های خانه اندیس 2 در آدرس 4 نوشته خواهند شد :

کد:

(i - L1) * N = (2 - 1) * 4 = 1 * 4 = 4

البته ما فرض کرده ایم که آدرس شروع آرایه در حافظه 0 است، یعنی ما آدرس شروع آرایه را نسبت به خود آرایه
محاسبه می کنیم، یعنی نسبی است. اگر آدرس شروع ارایه در حافظه 0 نیست باید نتیجه فرمول قبلی
را با آدرس شروع آرایه در حافظه جمع کنیم تا آدرس نسبی به مطلق تبدیل شود.

v.b.f1 · May 6, 2011

دوستان ممنون از توضیحتون فقط چندتا سوال دیگه دارم

درمورد تعداد عناصر دو بعدی هم میشه توضیحی بدین

(u1-L1+1)(u2-L2+1)*n

و طریقه تبدیل آرایه دوبعدی به یک بعدی رو بگین

(i-L1)*(u2-L2+1)+(j-L2)
البته به روش سطری و ستونیش میخوام بازم شرمنده سوالاتم زیاده

the_king · May 6, 2011

v.b.f1 گفت:
دوستان ممنون از توضیحتون فقط چندتا سوال دیگه دارم

درمورد تعداد عناصر دو بعدی هم میشه توضیحی بدین

(u1-L1+1)(u2-L2+1)*n

و طریقه تبدیل آرایه دوبعدی به یک بعدی رو بگین

(i-L1)*(u2-L2+1)+(j-L2)
البته به روش سطری و ستونیش میخوام بازم شرمنده سوالاتم زیاده

آرایه دو بعدی عبارت است یک تعداد آرایه یک بعدی که پشت سر هم قرار گرفته. اگر یک آرایه دو بعدی 5 سطر
و 7 ستون داشته باشه (یک آرایه 5 در 7) این آرایه دو بعدی در واقع 5 تا آرایه یک بعدی 7 خانه ای است.

در آرایه یک بعدی برای محاسبه کردن تعداد خانه های آرایه از فرمول U1 - L1 + 1 استفاده می کردیم، در آرایه دو بعدی
این فقط طول یک بعد از آرایه است، طول بعد دیگر آرایه از فرمول U2 - L2 + 1 بدست می آید. بدیهی است که
تعداد کل خانه های یک آرایه از ضرب کردن طول این دو بعد بدست بیاید، فرضا تعداد کل خانه های یک آرایه 5 در 7
یا 7 در 5 برابر است با 5 * 7 یا به عبارتی 35 خانه. فرمول اش هم عبارت است از :

کد:

(U1 - L1 + 1) * (U2 - L2 + 1)

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

کد:

(U1 - L1 + 1) * (U2 - L2 + 1) * N

در آرایه دو بعدی که برای هر خانه دو اندیس وجود دارد، عموما اندیس اول را سطر (با حرف i ) و اندیس دوم را
ستون (با حرف j ) در نظر می گیرند و از شیوه سطری برای ذخیره کردن آرایه در حافظه استفاده می کنند.

در شیوه سطری ابتدا تمامی محتویات یک سطر بطور کامل در آرایه نوشته می شود و سپس سراغ سطر
بعدی می روند. مثلا یک آرایه دو بعدی a را فرض کنید که 3 در 3 است و اندیس های هر دو بعد اعداد 1 الی 3
هستند :

کد:

[COLOR="Blue"]a[1,1] a[1,2] a[1,3][/COLOR]
a[2,1] a[2,2] a[2,3]
[COLOR="DarkGreen"]a[3,1] a[3,2] a[3,3][/COLOR]

خانه های این آرایه در حافظه به شیوه سطری از چپ به راست چنین نوشته می شود :

کد:

[COLOR="Blue"]a[1,1] a[1,2] a[1,3][/COLOR] a[2,1] a[2,2] a[2,3] [COLOR="DarkGreen"]a[3,1] a[3,2] a[3,3][/COLOR]

فرمول زیر مشخص می کند که اگر از شیوه سطری استفاده کنیم، در آرایه یک بعدی (یا خود حافظه، چون
حافظه کامپیوتر خودش یک آرایه یک بعدی است) خانه [ a[ i , j در چه اندیسی نوشته می شود، اندیس شروع
را در آرایه یک بعدی 0 فرض می کنیم :

کد:

(i - L1) * (U2 - L2 + 1) + ( j - L2)

برای درک کردن نحوه بدست آمدن این فرمول به یاد داشته باشید که U2 - L2 + 1 طول بعد دوم آرایه است، یعنی
تعداد ستون های آرایه.

در شیوه ستونی ابتدا تمامی محتویات یک ستون بطور کامل در آرایه نوشته می شود و سپس سراغ ستون
بعدی می روند. مثلا همان آرایه دو بعدی a به شیوه ستونی در حافظه با این ترتیب ذخیره می شود :

کد:

[COLOR="Blue"]a[1,1][/COLOR] a[2,1] [COLOR="DarkGreen"]a[3,1][/COLOR] [COLOR="Blue"]a[1,2][/COLOR] a[2,2] [COLOR="DarkGreen"]a[3,2][/COLOR] [COLOR="Blue"]a[1,3][/COLOR] a[2,3] [COLOR="DarkGreen"]a[3,3][/COLOR]

تفاوت میان فرمول روش ستونی با سطری در عوض شدن جای i و j و جای L1 و L2 و جای U1 و U2 است :

کد:

(j - L2) * (U1 - L1 + 1) + ( i - L1)

ice_boy68 · Dec 31, 2012

آرایه دو بعدی

با سلام.من سوالم در شکل زیر هست.تو این حالت چون base رو از اول آرایه دوبعدی شروع نکرده من به مشکل برخوردم و نیاز به راهنمایی دارم.

the_king · Dec 31, 2012

ice_boy68 گفت:
با سلام.من سوالم در شکل زیر هست.تو این حالت چون base رو از اول آرایه دوبعدی شروع نکرده من به مشکل برخوردم و نیاز به راهنمایی دارم.

این ماتریس بالا مثلثی 6 در 6 ئه، اندیس هایی که مشخص نشده اند و جایشان خالی است صفر اند :

کد:

A[1][1]	A[1][2]	A[1][3]	A[1][4]	A[1][5]	A[1][6]
	A[2][2]	A[2][3]	A[2][4]	A[2][5]	A[2][6]
		A[3][3]	A[3][4]	A[3][5]	A[3][6]
			A[4][4]	A[4][5]	A[4][6]
				A[5][5]	A[5][6]
					A[6][6]

و در آرایه یک بعدی به روش سطری (از بالا به پایین و از چپ به راست) اینطوری نوشته می شود :

کد:

A[1][1], A[1][2], A[1][3], A[1][4], A[1][5], A[1][6], A[2][2], A[2][3], A[2][4], A[2][5], A[2][6], A[3][3], A[3][4], A[3][5], ..., A[6][6]

اگر بخواهیم بدانیم در ماتریس n در n مقدار [A[j در چندمین خانه از آرایه یک بعدی نوشته شده، از فرمول زیر استفاده می شود،
توجه داشته باشید که تمامی اندیس ها از 1 شروع می شود :

کد:

[SIZE=4](i - 1) * (n - (i / 2)) + j[/SIZE]

ما می دانیم که آدرس خانه [A[4][5 کجا است، اول ببینیم [A[4][5 چندمین خانه آرایه یک بعدی است :

کد:

A[4][5] i = 4, j = 5, n = 6 (i - 1) * (n - (i / 2)) + j = (4 - 1) * (6 - (4 / 2)) + 5 = 3 * (6 - 2) + 5 = 17

پس [A[4][5 در آرایه خانه 17 ام است.

حالا ببینیم [A[2][3 چندمین خانه آرایه یک بعدی است :

کد:

A[2][3] i = 2, j = 3, n = 6 (i - 1) * (n - (i / 2)) + j = (2 - 1) * (6 - (2 / 2)) + 3 = 1 * (6 - 1) + 3 = 8

پس [A[2][3 در آرایه خانه 8 ام است.
حالا می توانیم بفهمیم که خانه [A[2][3 چند خانه عقب تر از خانه [A[4][5 است :

کد:

17 - 8 = 9

و آدرس اش چند بایت عقب تر است، در فرض سوال هر خانه دو بایتی است :

کد:

9 * 2 = 18

پس آدرس خانه [A[2][3 از آدرس خانه [A[4][5 دقیقا 18 بایت عقب تر است :

کد:

1000 - 18 = 982

و گزینه دوم پاسخ صحیح است.

ice_boy68 · Jan 1, 2013

سپاس از شما استاد گرامی بابت توضیحات کاملی که ارائه فرمودین :rose:

من طبق گفته های شما عمل کردم و تازه فهمیدم اوضاع از چه قراره...
البته من ماتریس رو کشیدم و به جواب رسیدم(طبق عکس پیوست شده،فاصله ی دو خونه ی مشخص شده 9 تاست که هرکدم 2 بایت فضا اشغال میکنه که میشه 18 تا کمتر از 1000)
ولی برای ماتریس های چند بعدی و تعداد بالا،روشی که من رفتم،روش خوبی نیست.
باز هم ممنون.