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

مولفین

مهندس جعفر تنها

مهندس سید ناصر آیت

لینک دانلود

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

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

داده

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

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

پردازش داده

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

---

نوع داده

داده ها نمایشی از اطلاعات در حافظه می باشند. نحوه نمایش یک داده خاص در حافظه توسط نوع داده (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. کپی : تهیه یک نسخه از ساختمان داده

سیستم عامل OS/2

OS/2 یک سیستم عامل است که توسط مایکروسافت و IBM ساخته شد و بعد به تنهایی توسط IBM توسعه یافت.نامش کوتاه شده ی Operating System/2 (سیستم عامل/2)است،زیرا به عنوان سیستم عامل ترجیح داده شده برای سیستم های شخصی/2 (Personal System/2 (PS/2))، خطِ نسل دوم کامپیوترهای شخصی معرفی شده بود.OS/2 دیگر توسط IBM فروخته نمیشود و پشتیبانی از آن از 31 دسامبر 2006 پایان یافت.

قرار بود OS/2 جانشین حفاظت شده ای برای MS-DOS و ویندوز مایکروسافت باشد.قابل توجه است که تماس های سیستم(system calls) پایه بعد از تماسهای MS-DOS مدل سازی شدند؛ حتی نامهایشان با "DOS"شروع میشد و ممکن بود برنامه های کاربردی حالت خانواده (family mode) ساخته شوند:برنامه های کاربردی حالت متنی که می توانند روی هر دو سیستم کار کنند.به همین خاطر ،OS/2 در بسیاری زمینه ها به ویندوز شبیه است،همچنین شباهت هایی هم به Unix و Xenix دارد. توسعه ی OS/2 وقتی شروع شد که IBM و مایکروسافت در آگوست 1985 قرارداد توسعه ی مشترکی را امضا کردند.هرچند، دو سال طول کشید تا محصول اول تحویل داده شود.

OS/2 1.0 در آوریل 1987 منتشر شد و در دسامبر به عنوان یک سیستم عامل فقط متنی ارائه شد.به هر حال،آن یک رابط برنامه ی کاربردی (API) توانگر را برای کنترل نمایش تصویر (video display(VIO)) و به کار بردن کیبورد و رویدادهای ماوس به صورت یک بایوس حفاظت شده نشان می داد.همچنین،تصویر و کیبورد رابط برنامه ی کاربردی (API) برای برنامه های حالت خانواده (family mode) در حال اجرا در MS-DOS قابل استفاده بودند.یک جابجا کننده ی وظیفه به نام "انتخاب کننده ی برنامه" از راه ترکیب کلیدهای ترکیبی Crt+Esc قابل دسترس بود و به کاربر اجازه میداد از میان جلسه های حالت های متنی چند وظیفه ای یکی را انتخاب کند(و یا گروه های تصویری که میتوانستند چند برنامه را اجرا کنند).

ارتباطات و تمدیدات پایگاه داده گرا در سال 1988 به عنوان ویراست تمدید شده ی OS/2 1.0 تحویل داده شدند:SNA,X.25/APPC/LU 6.2,LAN manager,Query manager,SQL. مدیر معرفی(Presentation Manager) ،رابط گرافیکی کاربرانی که قول داده شده بود، ،با OS/2 1.1 در نوامبر 1988 معرفی شد.با فونتهای متناسب ،این یک پیشرو برای ظاهر ویندوز بعدی 3.0 بود. ویراست تمدید شده ی 1.1 پشتیبانی پایگاه داده توزیع شده را معرفی کرد.

نسخه ی 1.2 سیستم‌های فایل قابل نصب به ویژه سیستم فایل HPFS را معرفی کرد.HPFS پیشرفتهایی را برای سیستم‌های فایل FAT ،شامل نام های طولانی و شکلی از جریان داده متناوب نه نام ویژگی های توسعه یافته فراهم می‌کرد.همچنین،ویژگی های توسعه یافته به سیستم فایل FAT هم افزوده میشدند. ویراست توسعه یافته ی 1.2 پشتیبانی TCP/IPو Ethernet را معرفی کرد. OS/2 و کتاب های مربوط به ویندوز سالهای پایانی دهه ی 1980 ، وجود هر دوی سیستم‌ها و OS/2 ی ارتقا داده شده را به عنوان سیستمی برای آینده تصدیق کردند.

 سازگاری DOS

به خاطر محدودیت های پردازنده ی Intel 80286 ، OS/2 1.x میتوانست در لحظه تنها یک برنامه ی DOS را اجرا کند و این کار را به گونه ای می‌کرد که به برنامه های DOS اجازه میداد کنترل کاملی روی کامپیوتر داشته باشند.مشکلی در حالت DOS میتوانست کل کامپیوتر را از کار بیاندازد.در مقابل ،OS/2 2.0 میتوانست از حالت مجازی 8086 پردازنده ی 80386 اینتل برای ساخت یک ماشین مجازی بسیار امن تر برای اجرای برنامه های DOS بهره ببرد.این یک دسته ی پهناور از گزینه های پیکر بندی برای بهینه ساختن کارایی و تواناییهای داده شده به هر برنامه ی DOS را شامل می شد. مانند بسیاری از محیط های 32 بیتی، OS/2 نمی توانست برنامه های حالت حفاظت شده ی DOS را با استفاده از رابط VCPI قدیمی تر اجرا کند ، برخلاف حالت استاندارد ویندوز 3.0 و 3.1 ؛ این فقط برنامه های نوشته شده بر اساس DPMI را پشتیبانی می‌کرد.

بر خلاف ویندوز NT ،OS/2 همیشه به برنامه های DOS امکان پوشش گذاری وقفه های واقعی سخت افزار را می داد، بنابراین هر برنامه ی DOS اینگونه می توانست ماشین را از کار بیاندازد.OS/2 هم چنین می توانست از یک سگ نگهبان سخت افزار بر روی ماشین های انتخاب شده (بر خلاف IBM) برای شکستن یک بن بست استفاده کند.سپس نسخه ی 3.0 پردازنده های توسعه یافته ی 486 اینتل - پرچم مجازی وقفه- را برای حل این مشکل به کار برد.

 سازگاری ویندوز 3.x

توانایی ویندوز 3.0 (و پس از ویندوز 3.1) با وفق دادن اجزای کد حالت کاربر ویندوز برای اجرا درون ماشین DOS مجازی به دست آمده بود.در اصل،یک نسخه ی تقریباً کامل کد ویندوز با خود OS/2 شامل شده بود.ویندوز 3.0 در OS/2 2.0 ، و ویندوز 3.1 در OS/2 2.1؛ هرچند سپس IBM نسخه ای از OS/2 را توسعه داد که می توانست از هر نسخه ای از ویندوز که کاربر پیشتر نصب کرده بود استفاده کند،در همان فرایند آن را سر هم کند و قیمت یک ویندوز اضافی را پس انداز کند.این می توانست هم با استفاده از درایو های تصویری خودش تمام صفحه اجرا شود و هم به صورت یک پارچه،جایی که برنامه های ویندوز مستقیما روی دسکتاپ OS/2 نمایان می‌شوند.

این فرآیند شامل ویندوز ، دسترسی پهناور منصفانه به سخت افزار را میداد، به ویژه تصویر ،و نتیجه این بود که جابجایی بین یک جلسه ی WinOS/2 و پوسته ی محل کار میتوانست گهگاه پی آمد هایی را موجب شود. به خاطر اینکه OS/2 فقط اجزای سیستم حالت کاربر ویندوز را اجرا می کرد،با درایوهای دستگاه های ویندوز(VxDs) سازگار نبود و نرم افزار های کاربردی به آنها نیاز داشتند. چندین برنامه ی کاربردی ویندوز در یک تک فرایند ویندوز اجرا می شدند،درست مانند ویندوز های بومی.برای دستیابی به یک جداسازی درست بین برنام های ویندوز 3.x ،OS/2 به چندین کپی موازی از ویندوز نیاز داشت.این روش به منابع سیستمی قابل توجهی،به ویژه حافظه نیاز داشت.مایکروسافت از یک روش ساده تر در ویندوز NT استفاده می کرد، ترجمه ی تماس های سیستم ویندوز 16 به ویندوز 32 به معنی لایه ی سازگاری ویندوز روی ویندوز(Windows-on-Windows).این روی OS/2 ممکن نبود زیرا رابط برنامه ی کاربردی(API) آن به کلی متفاوت بود.ممکن بود از DDE بین OS/2 و برنامه های کاربردی ویندوز استفاده شود، و OLE فقط بین برنامه های کاربردی ویندوز.

 ویژگی های محلی

OS/2 2.0 یک API ی 32 بیتی برای برنامه های محلی فراهم می‌کرد، گرچه سیستم عامل خودش ترکیبی از کد های 16 بیتی و 32 بیتی بود. این همچنین یک محیط رابط گرافیکی کاربر(GUI) تازه به نام پوسته ی محل کار(Workplace Shell) را شامل می شد.این یک رابط گرافیکی کاربر تمام شی گرا بود که از حرکت مهم از سوی رابط گرافیکی کاربر گذشته بود تا صرفاً فراهم کننده ی یک محیط برای برنامه های ویندوز(مانند مدیر برنامه ها) ،پوسته ی محل کار محیطی را فراهم می کرد که کاربر می توانست برنامه ها،فایل ها و دستگها ها را با دستکاری اشیا ی روی صفحه مدیریت کند. یک عامل مهم در در گسترش دادن و پذیرش OS/2 و نسخه های بعد OS/2 ی گروهی ، یک گروه مدافع منشا بود که در سال 1992 شکل گرفت.

 

 فناوری

سیستم گرافیک لایه ای به نام مدیر نمایش دارد که پنجره ها، فونت ها و آیکن ها را مدیریت می کند.این به وابستگی به یک نسخه ی غیر شبکه از X11 یا GDI ویندوز شبیه است.از همه مهم تر،پوسته ی محل کار (WPS) در OS/2 2.0 معرفی شد.WPS یک پوسته ی شئ گراست که به کاربر اجازه می دهد وظایف حساب کردن سنتی مانند دسترسی به فایل ها،پرینتر ها ،اجرا کردن برنامه های ارثی و وظایف پیشرفته ی شئ گرا را با استفاده از درون ساخت و اشیای کاربردی دسته ی سوم که پوسته را در یک سبک مجتمع که روی هیچ سیستم عامل اصلی دیگری در دسترس نیست را انجام دهد.WPS از استاندارد های دسترسی مشترک کاربر IBM پیروی می کند.

فروشندگان سخت افزار برای پشتیبانی درایور های دستگاه برای سیستم عامل های متناوب شامل OS/2 و لینوکس بی میل بودند و این کاربران را با انتخاب های فروشندگان محدودی رها می‌کرد.برای برجسته کردن این نسخه برای کارتهای ویدئویی ،IBM نسخه ی کاهش یافته ای از درایور های گرافیک Scitech را ارائه کرد که به کاربران اجازه می داد از میان تعداد زیادی کارت پشتیبانی شده یکی را به وسیله ی طراحی درایور وابسته به Scitech انتخاب کنند.

WPS اشیایی از جمله دیسکها، فولدرها، فایل ها،اشیای برنامه و پرینتر ها را با استفاده از مدل شئ سیستم(SOM) نمایش می دهد که به کد اجازه می دهد با برنامه های کاربردی که ممکن است در زبان های برنامه نویسی دیگری نوشته شده باشند ،به اشتراک گذاشته شود.یک نسخه ی توزیع شده به نام DSOM به اشیای کامپیوتر های مختلف اجازه می داد با هم ارتباط برقرار کنند.DSOM بر CORBA پایه گذاری شده است.SOM شبیه و یک رقیب مستقیم برای مدل شئ اجزای مایکروسافت است.SOM و DSOM دیگر توسعه نیافتند.

OS/2 همچنین یک پیشرفت اساسی در توسعه ی برنامه های کاربردی با فناوری اسناد مرکب به نام سندباز(OpenDoc) را شامل می شود که Apple آن را توسعه داد.OpenDoc جذابیت را به عنوان یک فناوری ثابت کرد ولی به شکل وسیع مورد استفاده قرار نگرفت ویا توسط کاربران و توسعه دهندگان پذیرفته نشد. OpenDoc هم دیگر توسعه نیافت.

توانایی های چند رسانه ای OS/2 به وسیله ی دستورات رابط کنترل رسانه(Media Control Interface commands) قابل دسترسی هستند.واپسین بروز رسانی (دسته بندی شده توسط نسخه ی IBM پلاگین های Netscape Navigator) پشتیبانی فایل های MPEG را افزود.پشتیبانی فرمت های جدید مانند PNG،JPG پیشرفت کننده،DivX،OGG وMP3 از قسمت های سوم می آید.گاهی این با سیستم چند رسانه ای یکی می شود ولی در ارائه های دیگر این به عنوان یک برنامه ی کاربردی جداگانه است. پشته ی TCP/IP بر پشته ی کد باز BSD پایه گذاری شده است.