ساختمان دادهها (به انگلیسی: Data Structure
صفحه 1 از 1
ساختمان دادهها (به انگلیسی: Data Structure
ساختمان دادهها (به انگلیسی: Data Structure) از جملهٔ بنیادیترین مباحث مورد نیاز جهت یادگیری و درك بسیارى از مفاهیم عمده در علوم رایانه است.
مدل منطقی یا ریاضی ساماندهی به دادهها به یک شکل خاص، ساختمان داده نام دارد. هر برنامه رایانهای از الگوریتم و ساختمان دادهها تشکیل شدهاست. [۱]
Data structures.png
موارد زیر از جمله مهمترین ساختمان دادهها هستند:
* آرایه (Array)
* صف (Queue)
* پشته (Stack)
* لیست پیوندی (Linked list)
* گراف (Graph)
* درخت (Tree)
در علوم کامپیوتر، یک آرایه پویا، آرایه قابل رشد، آرایه با قابلیت تغییر اندازه، جدول پویا، یا لیست پیوندی داده ساختاری آرایهای است که میتواند تغییر اندازه دهد و اجازه دهد عناصر اضافه و حذف شوند. امروزه امکان انجام این عمل در بسیاری از کتابخانههای استاندارد مسیر اصلی زبانهای برنامه نویسی تعبیه شدهاست. در یک آرایه پویا ابتدای کار حافظه اختصاص داده نمیشود؛ به طوری که اندازه اش غیر قابل تغییر باشد.
فهرست مندرجات
[نهفتن]
* ۱ آرایههای پویای کراندار و ظرفیت آنها
* ۲ تصاعد هندسی و هزینه واگذار شده
* ۳ کارایی
* ۴ متغیر ها
* ۵ زبانهای پشتیبانی کننده
* ۶ منابع
* ۷ پانویسها
ساده ترین آرایه پویا با اختصاص دادن آرایهای به طول ثابت ساخته میشود که بعد آن را به دو قسمت تقسیم میکنند: قسمت اول عناصر آرایه پویا را ذخیره میکند و قسمت دوم ذخیره شده، یا بدون استفاده میماند. سپس میتوان با استفاده از فضای رزرو شده در زمانی ثابت عناصر را به انتهای آرایه پویا اضافه کرد یا آنها را حذف کرد، تا زمانی که این فضا به طور کامل استفاده شود. تعداد عناصری که توسط محتویات آرایه پویا استفاده میشود اندازه منطقی یا اندازه آن است، در حالیکه اندازه آرایه زیرین ظرفیت آرایه پویا نام دارد، که حداکثر اندازه منطقی ممکن است. در برنامههایی که اندازه منطقی کراندار است، این ساختار داده کفایت میکند. تغییر دادن اندازه آرایه زیرین عملی هزینه بر است، گاهی ناچار میشویم تمام محتویات آرایه را کپی کنیم.
برای جلوگیری از تحمیل هزینههای اضافی حاصل از تغییر اندازه دادنهای مکرر، آرایههای پویا به مقدار زیادی تغییر اندازه میدهند، مثلا به دو برابر اندازه اولیه تغییر اندازه میدهند، و فضای رزرو شده را برای بسط بعدی استفاده میکنند. عمل اضافه کردن یک عنصر باید مانند زیر انجام شود:
function insertEnd(dynarray a, element e)
if (a.size = a.capacity)
// (اندازه را به دو برابر مقدار اوليه تغيير مي دهيم):
a.capacity ← a.capacity * 2
// (کپي کردن محتويات در محل حافظه جديد)
a[a.size] ← e
a.size ← a.size + 1
در فرآیند درج n عنصر، ظرفیتها تشکیل تصاعد هندسی میدهند. بسط دادن آرایه با هر نسبت ثابتی تضمین میکند وارد کردن عصر در کل از (O(n زمان میبرد، یعنی وارد کردن هر عنصر زمان سرشکن شده ثابتی میبرد. مقدار این تناسب منجر به لزوم سبک سنگین کردن این فصله زمانی میشود: زمان متوسط هر بار وارد کردن تقریبا (a/(a-۱ است، در حالی که تعداد خانههای تلف شده از بالا به a−۱)n) کراندار است. انتخاب a بستگی به برنامه دارد، ولی معمولا a=۲ میگیرند. بعلاوه در بسیاری از آرایههای پویا اگر مقدار استفاده شده از حدی کمتر شود، مانند ۳۰٪ ظرفیت، آن را آزاد میکنند. آرایههای پویا مثال رایجی در تدریس تحلیل سرشکن شده [۱] هستند.
کارایی آرایه پویا شبیه آرایهاست، بعلاوه عمل حذف و افزودن عناصر به انتها:
* گرفتن یا قرار دادن مقدار در محلی خاص (زمان ثابت)
* به ترتیب روی عناصر حرکت کردن (زمان خطی)
* وارد کردن یا پاک کردن عنصر در وسط آرایه (زمان خطی)
* وارد کردن یا پاک کردن عنصر در آخر آرایه (زمان ثابت سرشکن )
بسیاری از مزیتهای آرایهها در آرایههای پویا نیز وجود دارد، از جمله محل مناسب مرجع و استفاده از حافظه نهان، تراکم (کم استفاده کردن از حافظه)، و دسترسی تصادفی. معمولاً آرایههای پویا در کل فقط یک حافظه اضافی کوچکی برای اطلاعات اندازه و ظرفیت دارند. این ویژگی موجب میشود آرایههای پویا ابزار مناسبی برای ساختن داده ساختار متناسب با حافظه نهان شوند. آرایههای پویا در مقایسه با لینک لیست، قابلیت شاخص گذاری [۲] سریع تری دارند (زمان ثابت در برابر زمان خطی) و معمولا به دلیل اصلاح محل مرجع عناصر سریعتر میتوان بر روی عناصر واقع در خانههای آرایه حرکت کرد؛ اگرچه، آرایههای پویا برای وارد کردن در محلی دلخواه یا پاک کردن از جایگاهی اختیاری زمانی خطی نیاز دارند، چون همه عناصر بعدی باید یک عنصر جا به جا شوند، در حالیکه لینک لیست میتواند این عمل را در زمانی ثابت انجام دهد. بوسیله میانگیر وقفه[۳] و متغیرهای بردار صف شده این اشکال را برطرف کردهاند که در مورد آن در قسمت متغیرها بحث شدهاست. همچنین، ممکن است یافتن فضایی پیوسته در ناحیه یک حافظه بسیار قطعه بندی شده هزینه بر یا غیرممکن باشد، در حالیکه لینک لیستها نیازی ندارند همه داده ساختار به طورپیوسته در حافظه ذخیره شود
میانگیرهای وقفه شبیه آرایههای پویا هستند ولی اجازه میدهند عملگرهای کارای درج و حذف نزدیک محل اختیاری مشابه جمع شوند. برخی از پیاده سازیهای صف دو سر از آرایههای صف دو سر استفاده میکنند، که اجازه درج/جابجایی در هر دو سر، به جای یک طرف میدهد. Goodrich الگوریتمی از آرایههای پویا به نام Tiered Vectors ارائه کرد که کارایی آن برای درج و حذف از وسط آرایه با حفظ ترتیب n۱/۲ O(است. درخت آرایهای درهم [۴] یک الگوریتم آرایهٔ پویا است که توسط Sitarski در سال ۱۹۹۶ ساخته شدهاست. درخت آرایهای درهم حافظهای از مرتبه n۱/۲ هدر میدهد، که n تعداد عناصر آرایهاست. وقتی دنبالهای از اشیا به انتهای درخت آرایهای درهم میافزاییم، کارکرد سرشکن الگوریتم O(۱) است. در سال ۱۹۹۹ Brodnik et al. در مقالهای یک داده ساختار آرایه پویای صفی [۵] توصیف کرد، که در هر نقطهای از زمان تنها n۱/۲ فضا برای n عنصر هدر میداد، و آنها کران پایینی را ثابت کردند که نشان میداد در هر آرایه پویایی اگر عملگرها میخواهند زمان ثابت سرشکنی بگیرند حداقل به این مقدار فضا نیاز هست. بعلاوه، برای مواردی که رشد کردن و جمع شدن میانگیرنه تنها درحالت سرشکن بلکه در بدترین حالت ثابت باشد، متغیری ارائه کردند. در سال ۲۰۰۲ Bagwell الگوریتم Vlist را ارائه کرد، که میتواند برای پیاده سازی آرایه پویا اقتباس شود.
مدل منطقی یا ریاضی ساماندهی به دادهها به یک شکل خاص، ساختمان داده نام دارد. هر برنامه رایانهای از الگوریتم و ساختمان دادهها تشکیل شدهاست. [۱]
Data structures.png
موارد زیر از جمله مهمترین ساختمان دادهها هستند:
* آرایه (Array)
* صف (Queue)
* پشته (Stack)
* لیست پیوندی (Linked list)
* گراف (Graph)
* درخت (Tree)
در علوم کامپیوتر، یک آرایه پویا، آرایه قابل رشد، آرایه با قابلیت تغییر اندازه، جدول پویا، یا لیست پیوندی داده ساختاری آرایهای است که میتواند تغییر اندازه دهد و اجازه دهد عناصر اضافه و حذف شوند. امروزه امکان انجام این عمل در بسیاری از کتابخانههای استاندارد مسیر اصلی زبانهای برنامه نویسی تعبیه شدهاست. در یک آرایه پویا ابتدای کار حافظه اختصاص داده نمیشود؛ به طوری که اندازه اش غیر قابل تغییر باشد.
فهرست مندرجات
[نهفتن]
* ۱ آرایههای پویای کراندار و ظرفیت آنها
* ۲ تصاعد هندسی و هزینه واگذار شده
* ۳ کارایی
* ۴ متغیر ها
* ۵ زبانهای پشتیبانی کننده
* ۶ منابع
* ۷ پانویسها
ساده ترین آرایه پویا با اختصاص دادن آرایهای به طول ثابت ساخته میشود که بعد آن را به دو قسمت تقسیم میکنند: قسمت اول عناصر آرایه پویا را ذخیره میکند و قسمت دوم ذخیره شده، یا بدون استفاده میماند. سپس میتوان با استفاده از فضای رزرو شده در زمانی ثابت عناصر را به انتهای آرایه پویا اضافه کرد یا آنها را حذف کرد، تا زمانی که این فضا به طور کامل استفاده شود. تعداد عناصری که توسط محتویات آرایه پویا استفاده میشود اندازه منطقی یا اندازه آن است، در حالیکه اندازه آرایه زیرین ظرفیت آرایه پویا نام دارد، که حداکثر اندازه منطقی ممکن است. در برنامههایی که اندازه منطقی کراندار است، این ساختار داده کفایت میکند. تغییر دادن اندازه آرایه زیرین عملی هزینه بر است، گاهی ناچار میشویم تمام محتویات آرایه را کپی کنیم.
برای جلوگیری از تحمیل هزینههای اضافی حاصل از تغییر اندازه دادنهای مکرر، آرایههای پویا به مقدار زیادی تغییر اندازه میدهند، مثلا به دو برابر اندازه اولیه تغییر اندازه میدهند، و فضای رزرو شده را برای بسط بعدی استفاده میکنند. عمل اضافه کردن یک عنصر باید مانند زیر انجام شود:
function insertEnd(dynarray a, element e)
if (a.size = a.capacity)
// (اندازه را به دو برابر مقدار اوليه تغيير مي دهيم):
a.capacity ← a.capacity * 2
// (کپي کردن محتويات در محل حافظه جديد)
a[a.size] ← e
a.size ← a.size + 1
در فرآیند درج n عنصر، ظرفیتها تشکیل تصاعد هندسی میدهند. بسط دادن آرایه با هر نسبت ثابتی تضمین میکند وارد کردن عصر در کل از (O(n زمان میبرد، یعنی وارد کردن هر عنصر زمان سرشکن شده ثابتی میبرد. مقدار این تناسب منجر به لزوم سبک سنگین کردن این فصله زمانی میشود: زمان متوسط هر بار وارد کردن تقریبا (a/(a-۱ است، در حالی که تعداد خانههای تلف شده از بالا به a−۱)n) کراندار است. انتخاب a بستگی به برنامه دارد، ولی معمولا a=۲ میگیرند. بعلاوه در بسیاری از آرایههای پویا اگر مقدار استفاده شده از حدی کمتر شود، مانند ۳۰٪ ظرفیت، آن را آزاد میکنند. آرایههای پویا مثال رایجی در تدریس تحلیل سرشکن شده [۱] هستند.
کارایی آرایه پویا شبیه آرایهاست، بعلاوه عمل حذف و افزودن عناصر به انتها:
* گرفتن یا قرار دادن مقدار در محلی خاص (زمان ثابت)
* به ترتیب روی عناصر حرکت کردن (زمان خطی)
* وارد کردن یا پاک کردن عنصر در وسط آرایه (زمان خطی)
* وارد کردن یا پاک کردن عنصر در آخر آرایه (زمان ثابت سرشکن )
بسیاری از مزیتهای آرایهها در آرایههای پویا نیز وجود دارد، از جمله محل مناسب مرجع و استفاده از حافظه نهان، تراکم (کم استفاده کردن از حافظه)، و دسترسی تصادفی. معمولاً آرایههای پویا در کل فقط یک حافظه اضافی کوچکی برای اطلاعات اندازه و ظرفیت دارند. این ویژگی موجب میشود آرایههای پویا ابزار مناسبی برای ساختن داده ساختار متناسب با حافظه نهان شوند. آرایههای پویا در مقایسه با لینک لیست، قابلیت شاخص گذاری [۲] سریع تری دارند (زمان ثابت در برابر زمان خطی) و معمولا به دلیل اصلاح محل مرجع عناصر سریعتر میتوان بر روی عناصر واقع در خانههای آرایه حرکت کرد؛ اگرچه، آرایههای پویا برای وارد کردن در محلی دلخواه یا پاک کردن از جایگاهی اختیاری زمانی خطی نیاز دارند، چون همه عناصر بعدی باید یک عنصر جا به جا شوند، در حالیکه لینک لیست میتواند این عمل را در زمانی ثابت انجام دهد. بوسیله میانگیر وقفه[۳] و متغیرهای بردار صف شده این اشکال را برطرف کردهاند که در مورد آن در قسمت متغیرها بحث شدهاست. همچنین، ممکن است یافتن فضایی پیوسته در ناحیه یک حافظه بسیار قطعه بندی شده هزینه بر یا غیرممکن باشد، در حالیکه لینک لیستها نیازی ندارند همه داده ساختار به طورپیوسته در حافظه ذخیره شود
میانگیرهای وقفه شبیه آرایههای پویا هستند ولی اجازه میدهند عملگرهای کارای درج و حذف نزدیک محل اختیاری مشابه جمع شوند. برخی از پیاده سازیهای صف دو سر از آرایههای صف دو سر استفاده میکنند، که اجازه درج/جابجایی در هر دو سر، به جای یک طرف میدهد. Goodrich الگوریتمی از آرایههای پویا به نام Tiered Vectors ارائه کرد که کارایی آن برای درج و حذف از وسط آرایه با حفظ ترتیب n۱/۲ O(است. درخت آرایهای درهم [۴] یک الگوریتم آرایهٔ پویا است که توسط Sitarski در سال ۱۹۹۶ ساخته شدهاست. درخت آرایهای درهم حافظهای از مرتبه n۱/۲ هدر میدهد، که n تعداد عناصر آرایهاست. وقتی دنبالهای از اشیا به انتهای درخت آرایهای درهم میافزاییم، کارکرد سرشکن الگوریتم O(۱) است. در سال ۱۹۹۹ Brodnik et al. در مقالهای یک داده ساختار آرایه پویای صفی [۵] توصیف کرد، که در هر نقطهای از زمان تنها n۱/۲ فضا برای n عنصر هدر میداد، و آنها کران پایینی را ثابت کردند که نشان میداد در هر آرایه پویایی اگر عملگرها میخواهند زمان ثابت سرشکنی بگیرند حداقل به این مقدار فضا نیاز هست. بعلاوه، برای مواردی که رشد کردن و جمع شدن میانگیرنه تنها درحالت سرشکن بلکه در بدترین حالت ثابت باشد، متغیری ارائه کردند. در سال ۲۰۰۲ Bagwell الگوریتم Vlist را ارائه کرد، که میتواند برای پیاده سازی آرایه پویا اقتباس شود.
pooriamirani- کاربر متوسط
- تعداد پستها : 119
تاريخ التسجيل : 2009-10-24
العمر : 38
آدرس پستي : pooriamirani1291@yahoo.com
صفحه 1 از 1
صلاحيات هذا المنتدى:
شما نمي توانيد در اين بخش به موضوعها پاسخ دهيد