ساختمان های داده در c (آرایه)

آرايه ساده ترين ساختمان داده اي است كه در زبان c وجود دارد. ساده ترين شكل آن، آرايه يك بعدي است كه بردارنيز ناميده مي شود. آرايه يك بعدي، مجموعه مرتب و محدودي از عناصر همگن است. منظور از "محدود" اين است كه تعداد عناصر آرايه مشخص است.

آرايه به عنوان يك adt

adt آرايه

مجموعه عناصر:

دنباله اي با طول ثابت(مجموعه مرتب) از عناصر كه همگي از يك نوع اند.

عمليات اصلي:

دستيابي مستقيم به هر عنصر آرايه، به طوري كه مقادير را مي توان از اين عنصر بازيابي يا در آن ذخيره كرد.

آرايه هاي يك بعدي

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

vپياده سازي آرايه يك بعدي

آرايه هاي يك بعدي را به آساني مي توان پياده سازي كرد. دستور زير را در نظر بگيريد:

int a[10];

اين دستور 10محل متوالي حافظه را تخصيص مي دهد كه درهر محل مي توان يك مقدار صحيح را ذخيره كرد. آدرس اولين محل، آدرس پايهنام دارد و با base(a) مشخص مي شود. اگر فرض كنيد هر مقدار صحيح چهار بايت از فضاي حافظه را اشغال مي كند، آنگاه اولين عنصر آرايه با شروع از آدرس base(a) در چهار بايت از حافظه ذخيره مي شود.

عنصر a[1] با شروع از آدرس 4+ base(a) در چهار بايت ذخيره مي شود به طور كلي، اگر طول هر عنصر آرايه a را size درنظر بگيريم، محل عنصر iﭐم به صورت زير محاسبه مي شود:

base(a) + i * size

مثال 1_1

فرض كنيد آرايه x به صورت int x[10] تعريف شود و base(x) برابر با 1000 باشد. اگر مقادير صحيح چهار بايت از فضاي حافظه را اشغال كنند، آدرس x[3] چيست؟

اهداف آموزشي

1. آشنايي با ذخيره عناصر آرايه

2. يافتن محل ذخيره عنصر آرايه (آدرس عنصر آرايه).

= base(x) + 3 *Sizeof(int) آدرس x[3]

= 1000 + 3*4
=1012

كاربردهاي آرايه هاي يك بعدي

يكي از كاربردهاي آرايه در الگوريتم هاي مرتب سازي و جست و جو است كه مثال هايي را در ادامه خواهيد ديد.

كاربرد آرايه در مرتب سازي

يكي از اعمالي كه به وفور در كامپيوتر انجام مي گيرد، عمل مرتب سازي است. الگوريتم هاي متعددي براي مرتب سازي وجود دارند كه در اين جا، الگوريتم مرتب سازي انتخابي را در نظر مي گيريم.

مثال 2_1

الگوريتم و برنامه اي كه عناصر آرايه اي به طول n را با الگوريتم انتخابي به طور صعودي مرتب مي كند.

الگوريتم مرتب سازي انتخابي

دريافتي:مقدار صحيح 1 =< n و آرايهx

برگشتي: آرايه x كه به طور صعودي مرتب شده است.

1. براي i = 0 تا n - 2 مراحل زير را انجام بده:

/* در گذر iﭐم، ابتدا كوچك ترين عنصر x[i] تا x[n-1] را پيدا كن*/

2.min = i

3. براي j = i + 1 تا n – 1 اعمال زير را انجام بده:

4. اگر x[j] < x[min] آنگاه

5.min = j

/* اكنون كوچك ترين عنصر را با iﭐمين عنصر ليست جابه جا كن.

6.item = x[i];

7.x[i] = x[min];

8.x[min] = item;

جست و جو در آرايه

جست و جو مي تواند به صورت ترتيبي يا دودويي انجام شود. جست و جوي دودويي در آرايه مرتب صورت مي گيرد.

مثال 4_1

الگوريتم و برنامه اي كه مقداري را در آرايه اي به طول n به طور خطي(ترتيبي) جست و جو مي كند. سپس زمان اجراي الگوريتم و پيچيدگي الگوريتم تعيين مي شود.

الگوريتم جست و جوي ترتيبي

دريافتي: مقدار صحيح n، آرايه x به طول n ، و item كه بايد جست و جو شود.

برگشتي: اگر item وجود داشته باشد،مقدار 1 وگرنه مقدار صفر برگردانده مي شود.

1.o را در found قرار بده

2.o را در loc قرار بده

3.تا زماني كه n > locو found = 0 مراحل زير را انجام بده:

4.اگر item == x[loc] آن گاه

5. 1 را در found قرار بده

6.وگرنه loc را يك واحد اضافه كن.

7. Found را برگردان.

محاسبه زمان جست و جوي خطي

در اين تابع، تعداد مقايسه ها به مقدار item و عدد ورودي n بستگي دارد.

در بدترين حالت داريم:

T(n) = n

مثال 5_1

الگوريتم و برنامه اي كه جست و جوي دودويي را در آرايه اي انجام مي دهد.

حل: ابتدا الگوريتم و سپس برنامه جست و جوي دودويي و در ادامه، زمان اجراي الگوريتم را خواهيد ديد.

الگوريتم جست وجوي دودويي

دريافتي: عدد صحيح n، آرايه n عنصري مرتب صعودي aو item كه بايد جست وجو شود.

برگشتي: اگر item پيدا شود، found = 1 و موقعيت آن در locقرار مي گيرد، و گرنه صفر در found قرار مي گيرد.

1.0found

2.0first

3.n - 1 را در Last قرار بده

4.تا زماني كه first < Last و found = 0 اعمال زير را انجام بده:

5.loc

6.اگر item < a[loc] آنگاه

7.loc - 1Last /* جست وجو در بخش اول */

8.وگرنه، اگر item > a[loc] آنگاه

9.loc + 1first /* جست وجو در بخش دوم */

10. وگرنه 1 found

محاسبه زمان جست و جوي دودويي

در جست و جوي دودويي، تعداد مقايسه ها برخسب item و تعداد عناصر آرايه (n) متفاوت است. اگر مقدار item برابر با a[mid] باشد، آنگاه فقط يك مقايسه انجام مي شود. اگر itemبرابر با

عنصر اول+(عنصر وسط-1)/2

باشد، 2بار مقايسه صورت مي گيرد. به همين ترتيب، در بدترين حالت، يعني زماني كه itemدر آرايه نباشد، تعداد مقايسه ها

مرحله، تعداد عناصر مورد جست وجو نصف مي شود.

آرايه هاي دو بعدي

نوع=;[ name[dim1][dim2