آرايه ساده ترين ساختمان داده اي است كه در زبان c وجود دارد. ساده ترين شكل آن، آرايه يك بعدي است كه بردارنيز ناميده مي شود. آرايه يك بعدي، مجموعه مرتب و محدودي از عناصر همگن است. منظور از "محدود" اين است كه تعداد عناصر آرايه مشخص است.
کاربر فعال
آرايه ساده ترين ساختمان داده اي است كه در زبان c وجود دارد. ساده ترين شكل آن، آرايه يك بعدي است كه بردارنيز ناميده مي شود. آرايه يك بعدي، مجموعه مرتب و محدودي از عناصر همگن است. منظور از "محدود" اين است كه تعداد عناصر آرايه مشخص است.
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
کاربر فعال
آرايه به عنوان يك adt
adt آرايه
مجموعه عناصر:
دنباله اي با طول ثابت(مجموعه مرتب) از عناصر كه همگي از يك نوع اند.
عمليات اصلي:
دستيابي مستقيم به هر عنصر آرايه، به طوري كه مقادير را مي توان از اين عنصر بازيابي يا در آن ذخيره كرد.
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
کاربر فعال
آرايه هاي يك بعدي
آرايه يك بعدي كه نام ديگر آن بردار است، براي ذخيره مجموعه اي از عناصر همنوع به كار مي رود. عناصر آرايه يك بعدي در محل هاي متوالي حافظه ذخيره مي شوند. طول آرايه يك بعدي در هنگام اعلان بايد تعيين شود و در طول اجراي برنامه قابل تغيير نيست.
vپياده سازي آرايه يك بعدي
آرايه هاي يك بعدي را به آساني مي توان پياده سازي كرد. دستور زير را در نظر بگيريد:
int a[10];
اين دستور 10محل متوالي حافظه را تخصيص مي دهد كه درهر محل مي توان يك مقدار صحيح را ذخيره كرد. آدرس اولين محل، آدرس پايهنام دارد و با base(a) مشخص مي شود. اگر فرض كنيد هر مقدار صحيح چهار بايت از فضاي حافظه را اشغال مي كند، آنگاه اولين عنصر آرايه با شروع از آدرس base(a) در چهار بايت از حافظه ذخيره مي شود.
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
کاربر فعال
عنصر 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
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
کاربر فعال
كاربردهاي آرايه هاي يك بعدي
يكي از كاربردهاي آرايه در الگوريتم هاي مرتب سازي و جست و جو است كه مثال هايي را در ادامه خواهيد ديد.
كاربرد آرايه در مرتب سازي
يكي از اعمالي كه به وفور در كامپيوتر انجام مي گيرد، عمل مرتب سازي است. الگوريتم هاي متعددي براي مرتب سازي وجود دارند كه در اين جا، الگوريتم مرتب سازي انتخابي را در نظر مي گيريم.
مثال 2_1
الگوريتم و برنامه اي كه عناصر آرايه اي به طول n را با الگوريتم انتخابي به طور صعودي مرتب مي كند.
الگوريتم مرتب سازي انتخابيدريافتي:مقدار صحيح 1 =< n و آرايهxبرگشتي: آرايه x كه به طور صعودي مرتب شده است.1. براي i = 0 تا n - 2 مراحل زير را انجام بده:/* در گذر iﭐم، ابتدا كوچك ترين عنصر x[i] تا x[n-1] را پيدا كن*/2.min = i3. براي 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;
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
کاربر فعال
جست و جو در آرايه
جست و جو مي تواند به صورت ترتيبي يا دودويي انجام شود. جست و جوي دودويي در آرايه مرتب صورت مي گيرد.
مثال 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 را برگردان.
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
کاربر فعال
محاسبه زمان جست و جوي خطي
در اين تابع، تعداد مقايسه ها به مقدار item و عدد ورودي n بستگي دارد.
در بدترين حالت داريم:
T(n) = n
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
کاربر فعال
مثال 5_1
الگوريتم و برنامه اي كه جست و جوي دودويي را در آرايه اي انجام مي دهد.
حل: ابتدا الگوريتم و سپس برنامه جست و جوي دودويي و در ادامه، زمان اجراي الگوريتم را خواهيد ديد.
الگوريتم جست وجوي دودوييدريافتي: عدد صحيح n، آرايه n عنصري مرتب صعودي aو item كه بايد جست وجو شود.برگشتي: اگر item پيدا شود، found = 1 و موقعيت آن در locقرار مي گيرد، و گرنه صفر در found قرار مي گيرد.1.0found2.0first3.n - 1 را در Last قرار بده4.تا زماني كه first < Last و found = 0 اعمال زير را انجام بده:5.loc6.اگر item < a[loc] آنگاه7.loc - 1Last /* جست وجو در بخش اول */8.وگرنه، اگر item > a[loc] آنگاه9.loc + 1first /* جست وجو در بخش دوم */10. وگرنه 1 found
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
کاربر فعال
محاسبه زمان جست و جوي دودويي
در جست و جوي دودويي، تعداد مقايسه ها برخسب item و تعداد عناصر آرايه (n) متفاوت است. اگر مقدار item برابر با a[mid] باشد، آنگاه فقط يك مقايسه انجام مي شود. اگر itemبرابر با
عنصر اول+(عنصر وسط-1)/2
باشد، 2بار مقايسه صورت مي گيرد. به همين ترتيب، در بدترين حالت، يعني زماني كه itemدر آرايه نباشد، تعداد مقايسه ها
مرحله، تعداد عناصر مورد جست وجو نصف مي شود.
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
کاربر فعال
آرايه هاي دو بعدي
نوع=;[ name[dim1][dim2
[دل خوش از آنیم که حج میرویم؟ ..]غافل از آنیم که کج میرویم
[SIGPIC][/SIGPIC]
پاسخ با نقل قول
علاقه مندی ها (بوک مارک ها)