ساختمان داده - جلسه اول

مفاهیم مقدماتی

داده

داده یک نمایش باینری از یک موجودیت منطقی قابل ذخیره سازی در حافظه کامپیوتر است.

داده ها درواقع مقادیری هستند که بعنوان ورودی به یک الگوریتم داده می شود تا پردازشی روی آنها انجام شود.

پردازش داده

هر نوع عملیاتی، نظیر محاسبات، مقایسه، جستجو، حذف یا تغییر داده که توسط برنامه روی داده ها انجام می پذیرد پردازش داده محسوب می شود.


نوع داده

داده ها نمایشی از اطلاعات در حافظه می باشند. نحوه نمایش یک داده خاص در حافظه توسط نوع داده (Data Type) آن مشخص می شود. نوع داده مجموعه ای از مقادیر و مجموعه ای از عملیاتی که روی این مقادیر اجرا می شود را تعیین می کند.

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

پیاده سازی می تواند سخت افزاری یا نرم افزاری باشد:

• در پیاده سازی سخت افزاری مدارات لازم برای اجرای عملیات طراحی می شود.
• در پیاده سازی نرم افزاری برنامه ای برای تفسیر رشته های بیتی و انجام عملیات موردنیاز با استفاده از دستورات سخت افزاری نوشته می شود.

وقتی نوع داده پیاده سازی شد برنامه نویس می تواند از آنها برای حل مسائل استفاده کند.

انواع داده ای که به صورت سخت افزاری طراحی می شوند انواع داده ابتدایی (Primitive Data Type) نامیده می شوند. هر کامپیوتری دارای مجموعه ای از انواع داده ابتدایی است.

یک زبان برنامه نویسی سطح بالا امکانات خوبی را برای تعریف نوع متغیر در اختیار برنامه نویس قرار می دهد. تعریف نوع داده متغیر مشخص می کند محتویات حافظه چگونه باید تفسیر شود و کامپایلر را قادر می سازد که عملکرد متناسب با متغیررا تشخیص دهد.

هر زبان برنامه نویسی مجموعه ای از انواع داده را تعریف می کند.

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

Data Type
Pascal
C
Character 8 Bit char char
Signed Integer 8 Bit shortint short int
Signed Integer 16 Bit integer int
Signed Integer 32 Bit longint long
Unsigned Integer 8 Bit byte unsigned short int
Signed Integer 16 Bit word unsigned int
Single Precision 32 Bit single float
Double Precision 64 Bit double double
Extended Precision 80 Bit extended long double

نوع داده انتزاعی

جدا از جنبه های سخت افزاری، اگر مفهوم نوع داده بر اساس آنچه برنامه نویس می خواهد به صورت نرم افزاری پیاده سازی شود نوع داده انتزاعی (Abstract Data Type) نامیده می شود.

اگر مفهوم نوع داده از توانائیهای سخت افزار جدا شود، تعداد نامحدودی از انواع نوع داده را می توان درنظر گرفت.


ساختمان داده

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

انواع ساختمان داده

1. ساختمان داده خطی : یک ساختمان داده را خطی می گویند هرگاه عناصر آن تشکیل یک دنباله را دهند، به بیان دیگر یک لیست خطی باشند.
برای نمایش لیست خطی دو روش اساسی وجود دارد:
     • رابطه خطی بین عناصربه وسیله خانه های متوالی حافظه نمایش داده می شود(آرایه).
     • رابطه خطی بین عناصر به وسیله اشاره گرها نمایش داده می شود(لیست پیوندی).
2. ساختمان داده غیر خطی مانند درخت ها و گراف ها


عملیات روی ساختمان داده

داده هایی که در ساختمان داده ها ظاهر می شوند به وسیله عملیات مشخصی پردازش می شوند. در واقع ساختمان داده خاصی که برنامه نویس برای یک مسئله انتخاب می کند بستگی زیادی به میزان عملیات خاصی دارد که در آن مسئله انجام می شود. برخی از این عملیات که زیاد مورد استفاده قرار می گیرند عبارتند از :

1. پیمایش : دقیقا یک بار دسترسی به کلیه داده های ساختمان داده
2. جستجو : یافتن یک داده یا مجموعه ای از داده ها با شرایط خاصی درون ساختمان داده
3. اضافه : افزودن یک داده جدید به ساختمان داده.
4. حذف : حذف یک داده از ساختمان داده.
5. مرتب سازی : قرار دادن داده ها در کنار هم با یک نظم معین.
6. ادغام : ترکیب داده های دو ساختمان داده مرتب و بدست آوردن یک ساختمان داده مرتب دیگر
7. اتصال : پیوند دو ساختمان داده به یکدیگر
8. کپی : تهیه یک نسخه از ساختمان داده