تماس درباره   صفحه اصلی
  ساختمان داده > آرايه  
 
 

آرايه


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

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


تعريف آرايه

آرايه (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 مشخص مي شوند. آرايه هاي چند بعدي در حافظه به صورت دنباله اي از خانه هاي پشت سر هم ذخيره مي شوند.


محاسبه فضا و آدرس

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

در زبان Pascal اندازه آرايه به صورت زير محاسبه می شود:

A[L1..U1, L2..U2, ….Ln..Un]

محاسبه اندازه آرايه

در زبان C اندازه آرايه به صورت زير محاسبه می شود:

A[M1][M2]…. [Mn]

محاسبه اندازه آرايه

نوع های داده در زبان های برنامه نويسی C و Pascal


مثال(Pascal). آرايه زير 24 عنصر کاراکتری دارد.

A: Array [1..2,1..3,1..2,1..2] of Char;
(2-1+1)(3-1+1)(2-1+1)(2-1+1) = 24.

مثال(C). ميزان فضاي اشغال شده توسط آرايه num به صورت زير محاسبه می شود:

int num [10][5] ;
10×5×2 = 100


نمايش آرايه ها

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

• روش سطری (row-major order)
• روش ستونی (column-major order)


روش سطری

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

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

آرايه a[2][3] را درنظر بگيريد که از آدرس α حافظه شروع شده است.

روش سطري

آدرس اولين عنصر سطر اول برابر با α + 0×sizeof(t) = α. چون در هر سطر 3 عنصر وجود دارد بنابراين آدرس عنصر اول سطر دوم برابربا α + 3×sizeof(t) می شود.

می توان يک فرمول کلی برای آرايه n بعدی بدست آورد. اگر آرايه A[δ1] [δ2] […] [δn] از آدرس α حافظه شروع شده باشد. آدرس خانه A[i1][i2]…. [in] اين آرايه به صورت زير محاسبه می شود‌(W تعداد بايت‌هاي نوع آرايه است):

α + W [ (i1)δ2δ 3… δn + (i2)δ3…δn + … + (in) ]

اگر آرايه توسط زبان Pascal به صورت A[L1..U1, L2..U2, …,Ln..Un] تعريف شده باشد فرمول به شکل زير در می آيد:

α + W [ (i1-L1)δ2δ 3… δn + (i2-L2 )δ3…δn + … + (in-Ln) ]
δi=Ui-Liکه


مثال 1. آدرس خانه های آرايه يک بعدی به طريق زير محاسبه می شود.

آدرس A[i] = α + W(i-L)

مثال 2. آرايه دو بعدی A را در نظر بگيريد. اگر آرايه از آدرس 100 ذخيره شده باشد، آدرس خانه A[12][4] به طريق زير محاسبه می شود.

A : Array [10..15][3..5] of integer;
δ1=15-10+1=6 , δ2=5-3+1=3

آدرس A[i1,i2] = α + W [ (i1-L1)δ2+(i2-L2)]
آدرس A[12,4] = 100 + 2 [ (12-10)3+(4-3 )]
     =114

مثال 3. اگر آرايه سه بعدی num از آدرس 2000 به بعد ذخيره شده باشد، آدرس خانه A[3][2][1] به طريق زير محاسبه می شود:

float A[4][5][3] ;
δ1=4 ,δ2=5, δ3=3

آدرس A[i1][i2][i3] = α + W [ (i1)δ2δ3+(i2)δ3+(i3)]
آدرس A[3][2][1] = 2000 + 4 [ (3)5×3+(2)3+(1)]
     =2208


روش ستونی

در روش ستونی عناصر يک ستون پشت سر هم در حافظه قرار می گيرند در نتيجه انديس های سمت چپ سريع تر حرکت می کنند.

آدرس خانه A[i1][i2]… [in] در اين روش توسط فرمول زير محاسبه می شود:

α + W [ (i1) + δ1(i2)+ δ1δ2(i3) + … + δ1δ2δ 3…δn-1(in)]

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

α + W [ (i1-L1) + δ1(i2-L2)+ δ1δ2(i3-L3) + … + δ1δ2δ 3…δn-1(in-Ln)]
δi=Ui-Li


مثال. درمثال 2 اگر آرايه به صورت ستونی ذخيره شده باشد:

A[i1,i2] = α + W[ (i1-L1) + δ1(i2-L2)]
آدرس A[12,4] = 100 + 2 [ (12-10) +6(4-3)]
     =116

مثال. درمثال 3 اگر آرايه به صورت ستونی ذخيره شده باشد:

آدرس A[i1][i2][i3] = α + W[(i1)+ δ1 (i2) + δ1δ2 (i3)]
آدرس A[3][2][1] = 2000 + 4 [ (3) +4(2)+4×5(1)]
     =2124


آرایه های پويا

آرايه پويا (dynamic array) آرايه است اندازه اش در زمان اجرا با عمل درج يا حذف عناصردر آن تغيير می کند.

در زبان برنامه نويسی Visual Basic توسط دستور REDIM و در زبان C با تعريف حافظه پويا می توان آرايه پويا ايجاد کرد. در بعضی زبان ها مانند Perl کليه آرايه ها به صورت پويا هستند.


برنامه مقداردهی عناصر آرايه يک بعدی پويا در زبان C

برنامه مقداردهی عناصر آرايه دو بعدی پويا در زبان C


الگوريتم های درج و حذف

درج عنصری در آرايه

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

درج در آرايه

در کل n-k+1 عنصر بايد جابجا شوند. اگر عنصر جديد در محل آخرين عنصر درج شود تنها عنصر آخر آرايه جابجا می شود. بدترين حالت زمانی اتفاق می افتد که بخواهيم عنصر جديد را درمكان اول آرايه درج کنيم در اين حالت تعداد جابجائي‌ها برابر است با n می شود.
به طور متوسط نياز به(n+1)/2 جابجائي است.
با هربار عمل درج يک واحد به n تعداد عناصر آرايه اضافه می شود. n تعداد عناصری که در آرايه درج شده اند را نشان می دهد و ربطی به طول آرايه ندارد.

الگوريتم زير عنصر item را در مکان k ام آرايه A با n عنصر درج می کند.

for (i:= n down to k )
   A[j+1] := A[j]
end for
A[k] := item
n := n +1
end

پيچيدگي الگوريتم فوق O(n) است.


حذف عنصری از آرايه

وقتی عنصری از آرايه حذف می شود عناصر بعدی بايد به سمت بالا منتقل شوند تا محل عنصر حذف شده پر شود. برای حذف عنصری که در مکان k ام قرار دارد، کليه عناصر از k+1 به بعد بايد به سمت بالا شيفت داده شوند.

حذف عنصري از ارايه

در کل n-k عنصر بايد جابجا شوند. کمترين جابجائی وقتی است که عنصر آخر حذف شود که هيچ عنصری جابجا نمی شود. در بدترين حالت تعداد جابجائي‌ها برابر با n-1 است وقتی که اولين عنصر آرايه حذف می شود.
به طور متوسط نياز به (n-1)/2 جابجائي است.
با هربار عمل درج يک واحد به n تعداد عناصر آرايه اضافه می شود. n تعداد عناصری که در آرايه درج شده اند را نشان می دهد و ربطی به طول آرايه ندارد.

الگوريتم زير عنصرk ام آرايه A را حذف و در item ذخيره می کند.

item := A[k]
for (j := k to n – 1)
   A[j] := A[j + 1]
end for
n := n –1
end

پيچيدگي الگوريتم فوق O(n) است.


زيربرنامه درج عنصری در آرايه به زبان C
زيربرنامه حذف عنصری از آرايه به زبان C
برنامه درج و حذف عنصری در آرايه به زبان ++C


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


تمرينات آرايه

سوالات چندگزينه ای درباره آرايه


 


 


صفحه اصلی| PDF| درباره| تماس