فرادرسمعرفی مبانی ساختار داده و آرایه های داده ای — به زبان ساده
در این بخش از آموزش ساختار داده قصد داریم به معرفی مبانی ساختار داده و همچنین مفهوم آرایه در ساختار داده بپردازیم. ابتدا اصطلاحت مقدماتی مرتبط با ساختار داده معرفی می‌شوند.
تعریف داده
در هنگام تعریف داده، یک داده خاص که خصوصیات زیر را دارد تعریف می‌شود:
- اتمیک بودن: تعریف باید یک مفهوم منفرد را معرفی کند.
- قابلیت ردگیری: تعریف باید بتواند به برخی عناصر داده‌ای نگاشت شود.
- صحت: تعریف باید بی‌ابهام باشد.
- واضح و مختصر: تعریف باید قابل درک باشد.
شیء داده‌ای
شیء داده‌ای نماینده شیئی است که یک داده دارد.
نوع داده
نوع داده روشی برای تعیین انواع مختلف داده‌ها مانند عدد صحیح (Integer)، رشته (String) و موارد دیگر است. این نوع داده‌ای مقداری که باید با نوع داده متناظر مورد استفاده قرار گیرد و نوع عملیاتی که می‌تواند بر روی نوع متناظر داده اجرا شود را تعیین می‌کند. دو نوع داده وجود دارند:
- نوع داده داخلی
- نوع داده انشقاقی
نوع داده داخلی
نوع داده‌هایی که یک زبان به طور درونی از آن‌ها پشتیبانی می‌کند به نام انواع داده داخلی نامیده می‌شوند. برای نمونه اغلب زبان‌ها انواع داده داخلی زیر را در خود دارند:
- اعداد صحیح
- مقادیر بولی (درست، نادرست)
- مقادیر با ممیز شناور (اعداد اعشاری)
- کاراکترها و رشته‌ها
نوع داده انشقاقی
انواع داده‌هایی که مستقل از پیاده‌سازی هستند یعنی می‌توان آن‌ها را به روش‌های مختلف پیاده‌سازی نمود به نام انواع داده انشقاقی نامیده می‌شوند. این انواع داده معمولاً به وسیله ترکیب انواع اولیه یا داخلی و عملیات‌های مرتبط با آن‌ها به دست می‌آیند. برای نمونه
- لیست
- آرایه
- پشته
- صف
عملیات‌های ابتدایی
داده‌ها در ساختار داده به وسیله عملیات‌های معینی پردازش می‌شوند. ساختار داده خاصی که انتخاب می‌شود تا حدود زیادی به فراوانی عملیات‌هایی که باید روی ساختار داده اجرا شوند بستگی دارند.
- پیمایش (Traversing)
- جستجو (Searching)
- درج (Insertation)
- حذف (Deletion)
- مرتب‌سازی (Merging)
- ادغام (Merging)
در بخش دوم این نوشته به بررسی ساختارهای داده آرایه‌ای خواهیم پرداخت. آرایه یک ظرف است که تعداد ثابتی از آیتم‌ها را نگه‌داری می‌کند و این آیتم‌ها باید از نوع یکسانی باشند. اغلب ساختارهای داده‌ای از آرایه‌ها برای پیاده‌سازی الگوریتم‌هایشان استفاده می‌کنند. در ادامه برخی اصطلاح‌های مهم برای درک مفهوم ارائه شده است:
- عنصر (Element): هر آیتم که در یک آرایه ذخیره شود به نام عنصر خوانده می‌شود.
- اندیس (Index): هر عنصر در آرایه، یک اندیس عددی دارد که برای شناسایی آن عنصر مورد استفاده قرار می‌گیرد.
بازنمایی آرایه
آرایه‌ها را می‌توان به روش‌های مختلفی در زبان‌های گوناگون اعلان کرد.
برای نمونه اعلان آرایه در زبان C را بررسی می‌کنیم.
همانند تصویر فوق می‌بینیم که نقاط مهمی در آرایه هستند که در ادامه آن‌ها را توضیح داده‌ایم:
- اندیس آرایه از صفر آغاز می‌شود
- طول آرایه 10 است یعنی می‌تواند 10 عنصر در خود جای دهد.
- هر عنصر می‌تواند از طریق اندیس خود مورد دسترسی قرار گیرد. برای مثال، می‌توانیم یک عنصر را در اندیس 6 با مقدار 9 به دست آوریم.
عملیات‌های ابتدایی
در فهرست زیر عملیات‌های ابتدایی که می‌توان روی یک آرایه اجرا کرد را می‌بینیم:
- Traverse: این عملیات همه عناصر آرایه را یک به یک پرینت می‌کند.
- Insertation: یک عنصر به آرایه مفروض اضافه می‌کند.
- Deletion: یک عنصر را از اندیس مفروض پاک می‌کند
- Search: بک عنصر را با استفاده از اندیس مفروض یا بر حسب مقدار جستجو می‌کند.
- Update: یک عنصر را در اندیس مفروض به‌روزرسانی می‌کند.
در زبان C وقتی یک آرایه با اندازه مشخص مقداردهی اولیه شود، در این صورت مقادیر پیش‌فرض زیر به عناصر آن به ترتیب زیر انتساب می‌یابند.
عملیات درج
عملیات درج برای وارد کردن یک یا چند عنصر داده‌ای در یک آرایه استفاده می‌شود. بر اساس نیاز یک عنصر جدید می‌تواند در آغاز، پایان یا هر اندیس دلخواه آرایه درج شود.
در این بخش یک پیاده‌سازی عملی از عملیات درج را مشاهده خواهیم کرد که در آن داده‌هایی در بخش انتهای آرایه اضافه می‌شوند. فرض کنید LA یک آرایه نامرتب خطی با N عنصر باشد و K یک عدد صحیح باشد که K<=N. در ادامه الگوریتمی ارائه شده است که در آن ITEM در موقعیت k-ام آرایه LA درج می‌شود:
1. Start 2. Set J = N 3. Set N = N+1 4. Repeat steps 5 and 6 while J >= K 5. Set LA[J+1] = LA[J] 6. Set J = J-1 7. Set LA[K] = ITEM 8. Stop
مثال
در ادامه پیاده‌سازی الگوریتم فوق را می‌بینید:
#include
main() {
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) { printf("LA[%d] = %d \n", i, LA[i]); } n = n + 1; while( j >= k) {
LA[j+1] = LA[j];
j = j - 1;
}
LA[k] = item;
printf("The array elements after insertion :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
وقتی کد فوق را کامپایل و اجرا کنیم، خروجی زیر به دست می‌آید:
خروجی
The original array elements are : LA[0] = 1 LA[1] = 3 LA[2] = 5 LA[3] = 7 LA[4] = 8 The array elements after insertion : LA[0] = 1 LA[1] = 3 LA[2] = 5 LA[3] = 10 LA[4] = 7 LA[5] = 8
عملیات حذف
منظور از حذف، پاک کردن یک عنصر موجود از آرایه و سازماندهی مجدد همه عناصر آرایه است.
الگوریتم
فرض کنید LA یک آرایه با N عنصر و K یک عدد صحیح مثبت است که K<=N. در ادامه الگوریتمی برای حذف یک عنصر از آرایه LA ارائه شده است که در موقعیت K-ام آن قرار دارد.
1. Start 2. Set J = K 3. Repeat steps 4 and 5 while J < N 4. Set LA[J] = LA[J + 1] 5. Set J = J+1 6. Set N = N-1 7. Stop
مثال
پیاده‌سازی الگوریتم فوق به صورت زیر است:
#include
void main() {
int LA[] = {1,3,5,7,8};
int k = 3, n = 5;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
j = k;
while( j < n) {
LA[j-1] = LA[j];
j = j + 1;
}
n = n -1;
printf("The array elements after deletion :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
زمانی که فایل فوق را کامپایل کرده و برنامه را اجرا کنیم، نتیجه زیر به دست می‌آید:
خروجی
The original array elements are: LA[0] = 1 LA[1] = 3 LA[2] = 5 LA[3] = 7 LA[4] = 8 The array elements after deletion: LA[0] = 1 LA[1] = 3 LA[2] = 7 LA[3] = 8
عملیات جستجو
شما می‌توانید عملیات جستجو برای یک عنصر آرایه را بر اساس مقدار یا اندیس آن اجرا کنید.
الگوریتم
تصور کنید LA یک آرایه خطی با N عنصر و K یک عدد صحیح مثبت باشد که K<=N. در ادامه با استفاده از جستجوی ترتیبی، الگوریتمی برای یافتن عنصری که دارای مقدار ITEM است اجرا می‌کنیم.
1. Start 2. Set J = 0 3. Repeat steps 4 and 5 while J < N 4. IF LA[J] is equal ITEM THEN GOTO STEP 6 5. Set J = J +1 6. PRINT J, ITEM 7. Stop
مثال
در ادامه پیاده‌سازی الگوریتم فوق را اجرا می‌کنیم.
#include
void main() {
int LA[] = {1,3,5,7,8};
int item = 5, n = 5;
int i = 0, j = 0;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
while( j < n){
if( LA[j] == item ) {
break;
}
j = j + 1;
}
printf("Found element %d at position %d\n", item, j+1);
}
وقتی برنامه فوق را کامپایل و اجرا کنیم، نتیجه زیر به دست می‌آید:
خروجی
The original array elements are: LA[0] = 1 LA[1] = 3 LA[2] = 5 LA[3] = 7 LA[4] = 8 Found element 5 at position 3
عملیات به‌روزرسانی
منظور از عملیات به‌روزرسانی، تغییر عناصر موجود در یک آرایه در اندیس مفروض است.
الگوریتم
فرض کنید LA یک آرایه با N عنصر و K عدد صحیح مثبتی باشد که K<=N. در ادامه الگوریتم به‌روزرسانی عنصر موجود در موقعیت k-ام LA ارائه شده است.
1. Start 2. Set LA[K-1] = ITEM 3. Stop
مثال
در ادامه پیاده‌سازی الگوریتم فوق ارائه شده است:
#include
void main() {
int LA[] = {1,3,5,7,8};
int k = 3, n = 5, item = 10;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
LA[k-1] = item;
printf("The array elements after updation :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
وقتی برنامه فوق را کامپایل و اجرا کنیم، نتیجه زیر به دست می‌آید:
خروجی
The original array elements are: LA[0] = 1 LA[1] = 3 LA[2] = 5 LA[3] = 7 LA[4] = 8 The array elements after updation: LA[0] = 1 LA[1] = 3 LA[2] = 10 LA[3] = 7 LA[4] = 8
اگر این نوشته مورد توجه شما قرار گرفته است، پیشنهاد می‌کنیم موارد زیر را نیز ملاحظه نمایید:
- آموزش آرایه در ساختمان داده
- آموزش آرایه ها در زبان برنامه نویسی C
- پایگاه داده و سیستم های مدیریت اطلاعات
- آموزش معرفی و تعریف آرایه ها در تکمیلی پایتون
- آموزش آرایه ها در زبان برنامه نویسی Microsoft Small Basic
- آموزش آرایه در ساختمان داده ها (مرور – تست کنکور ارشد)
- دروس مهندسی کامپیوتر
==
