تحقیق مقاله ساختمان داده

داده‌ها: مجموعه‌هایی از مقادیر یک عنصر داده‌ ای به معنی واحد‌ منحصر به فرد از مقادیر است.

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

موجودیت Entity : شیء است که دارای خصیصه‌ها با خواص معین باشد و ممکن است مقادیری به آن نسبت داده شود موجودیت کارمند دارای خصیصه‌های :

(جدول در فایل اصلی موجود است)

  هر خصیصه از یک موجودیت دارای یک دامنه از مقادیر است.

به داده‌های دارای معنی یا داده‌های پردازش شده اطلاعات می‌گویند.

به داده‌هایی که دارای خصیصه‌های با مقادیر معین باشد اطلاعات می‌گویند.

سلسله مراتب داده‌ها:

فیلد:  یک واحد ابتدایی منحصر بفرد از اطلاعات است. (نمایانگر یک خصیصه ازموجودیت)

رکورد:  مجموعه‌ای از مقادیر فیلدهای یک موجودیت معین.

فایل:  مجموعه‌ای از رکوردهای موجودیت در یک مجموعه از موجودیتهای معین.

Px: به فیلدی که بطور منحصر بفرد رکورد داخل فایل را مشخص می‌کند فیلد اولیه یا اصلی می‌گوییم.

مثال: 1- نگاه‌ معاملات اتومبیل:   شماره سریالpk Accessories Price gear Type  (لوازم همراه)

2- سازمان: Dues Owed Tel.No Address (دیون بدهکار)

رکوردها با طولهای متغیر  مثل

رکوردهای دانشجویی

(تعداد درسهای متفاوت)

تمام رکوردها دارای فیلدهای برابر

و یکسان مقدار حافظه ی هر فیلد مساوی

پپیک فایل می‌تواند دارای یک رکورد با طول ثابت یا با طول متغیر باشد.

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

این سازماندهی باید بتواند رابطه‌های واقعی بین داده‌ها را منعکس‌ کرده و ساده باشد تا بتوان به راحتی داده‌ها را پردازش کرد.

آرایه‌ ها:  آرایه یک بعدی، ساده‌ترین نوع ساختمان داده است.

یک لیست متناهی با n عنصر داده‌ای مشابه که به  عناصر آن به ترتیب به کمک مجموعه‌ای از n عدد متوالی که معمولا از n , ….. , 2 , 1 می‌باشد، دسترسی پیدا می‌کنیم.

اگر نام آرایه A باشد، عناصر آن را a1 , a2 , a3 , …. an یا با نماد پرانتزی

(جدول در فایل اصلی موجود است)

زمانیکه از نماد پرانتزی و یا کروشه‌ای استفاده می‌شود نام آرایه به حروف بزرگ نوشته می‌شود.

مثال: آرایه خطی  STUDENT

STUDENT [2] = Ali m.

آرایه خطی= ارایه یک بعدی

دسترسی فقط از طریق یک اندیس

آرایه دو بعدی یا در اصطلاح ریاضی ماتریس (در تجارت جدول):

دواندیس داریم: مثال: فروشگاه زنجیره‌ای که از 28 فروشگاه که هر کدام  4 بخش دارند تشکیل شده (فروش/ هفتگی) دانشگاه آزاد که هر کدام از واحدها چند رشته دارند (تعداد دانشجو)

لیستهای پیوندی:  یک شرکت خدماتی، مشخصات مشتریهای خود را در یک فایل نگهداری می‌کند که فروشنده مرتبط با ان مشتری را نیز مشخص می‌کند.

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

یک مزیت دیگر پیدا کردن نام مشتریان یک فروشنده است که به سادگی انجام می‌گیرد به جای search در کل فایل پیکانها دنبال می‌شوند.

عیب اینکار:  هر فروشنده ممکن است چند اشاره‌گر داشته باشد وبا اضافه ویا حذف شدن مشتریها، مجموعه اشاره‌گرها تغییرکند.

راه حل:  هر فروشنده یک اشاره گر دارد که به مشتری اول اشاره می‌کند که اشاره گر آن نیز به نوبه خود به مشتری دوم و .... Link مشتری آخر به 0

Pointer (اشاره گر): یک عنصر از یک لیست بر یک عنصر از لیست دیگر اشاره می کند.

Link (پیوند): یک عنصر از لیست به یک عنصر دیگری از همان لیست اشاره می کند.

درختها:

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

Pointer (اشاره گر): یک عنصر از یک لیست بر یک عنصر از لیست دیگر اشاره می کند.

Link (پیوند): یک عنصر از لیست به یک عنصر دیگری از همان لیست اشاره می کند.

درختها:

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

پشته (Stack): به آن سیستم LIFO یا آخرین ورودی اولین خروجی است یک لیست خطی که اضافه و کم کردن عناصر فقط از یک سر لیست امکان پذیر است. مثال: یک پشته از بشقابها

صف (Queue) : یک سیستم FIFO است. اولین ورودی اولین خروجی است. لیست خطی که اضافه کردن عناصر تنها از انتهای لیست (Rear)  و برداشتن عناصر از ابتدا (front) صورت می گیرد. مثل : ایستگاه اتوبوس

گراف (Graph): گاهی اوقات داده ها یک رابطه بین حقیقت عناصر طبیعت را نشان می دهد و بصورت سلسله مراتبی نیستند. مثل : ارتباط  بین شهرها.

عملیات بر روی ساختمان داده ها: چهار عمل اصلی شامل:

1-

2-  جستجو: عمل یافتن مکان یک رکورد با یک مقدار کلیدی معین یا رکوردهایی که روی یک یا چند شرط صدق می‌کنند.

3- اضافه کردن: افزودن رکورد جدید به ساختمان داده.

4- حذف کردن: حذف یک رکورد جدید از ساختمان داده.

گاهی از بیش از یک عمل برای یک هدف استفاده می‌شود. مثل:

1- یک رکورد با کلید معلوم حذف می‌شود.2- مرتب کردن      3- ادغام کردن

الگوریتم:  پیچیدگی الگوریتم، توازن بین زمان اجرا و حافظه

یک الگوریتم یک لیست خوش تعریف از مراحلی است که برای حل یک مساله معین در نظر گرفته شده است  زمان و حافظه دو معیار  اصلی در کارآیی یک الگوریتم هستند.

رشته‌ها:

ابتدا کامپیوترها برای پردازش داده‌های عددی استفاده می‌شود ولی امروزه بیشتر برای پردازش داده‌های غیر عددی موسوم به داده‌های کاراکتری مورد استفاده قرار می‌گیرد.

در دروس کامپیوتری معمولاً به دنباله‌ای از کاراکترها به جای اصلاح «کلمه» رشته می‌گویند (String)

String آرایه‌ای از کاراکتر‌هاست

کاراکترهای الفبایی:                                                                

ABCDE…

کاراکترهای رقمی :                                                   ....0 1 2 3      

کاراکتر های مخصوص :                                     + - / * ( ) , . $ = ‘

رشته تهی : طول رشته صفر است.

یک رشته، دنباله متناهی از صفر تا چند کاراکتر است طول رشته ثابت نیست وبا داده‌هایی که در آن ذخیره شده است مشخص می‌شود.

تعداد کاراکترهای یک رشته ، طول رشته نامیده می‌شود.

رشته‌ای که هیچ کاراکتری ندارد، رشته تهی یا رشته پوچ نام دارد. نمایش رشته‌ها دربین علامت نقل قول است.

“The End” , ‘  ‘ ,  ‘      ‘

اگر در پاسکال از دستور Name := “ ” , استفاده می‌کنیم. رشته Name را به تهی تبدیل می‌کند.

دو رشته S1 و S2 را با هم ترکیب می‌کنیم و رشته S2 حاصل می‌شود به اینکار پیوند یا اتصال S1 و S2 می‌گویند.

S1||S2

“The” || 'o'|| ‘End’ = ‘The End’  اما  ‘The’ || ‘End’=’The End’

طول رشته حاصل برابر با طول رشته‌های ترکیب شده است.

رشته Y یک زیر رشته از S نامیده می‌شود.

S=X||Y||Z

مثال: ‘The’ یک زیر رشته ابتدایی ‘The End’ است.

طول یک زیر رشته نمی‌تواند از طول رشته بیشتر باشد.

توجه: برای نمایش یک کاراکتر یک بایت فضا مورد نیاز است. کامپیوتری که به یک بایت از حافظه دسترسی پیدا کند، یک ماشین با قابلیت آدرس دهی بایتی می‌گویند.

در پاسکال می‌توان با استفاده از زیر برنامه Val رشته را به عدد تبدیل کرد:

در پاسکال می‌توان با استفاده از زیر برنامه Sbr عدد را به رشته تبدیل کرد:

Val (st , number , error):

Sbr (number ; format , numstring)

ذخیره رشته‌ها:

1- ساختارهایی که طول ثابت دارند - طول رکوردها برابر (تعداد کاراکترهایکسان)

               مزایا: 1- دسترسی آسان به اطلاعات

2- update : آسان هر رکورد معین (طول نباید بیشتر از طول ثابت رکورد باشد)

2- بعضی از رکوردها نیاز به حافظه بیشتر از مقدار ثابت   دارند.

      3- تصحیح یک یا چند کاراکتر            تغییر تمام رکوردها.

2- حافظه با طول متغیر که ماکزیمم طول ثابت دارند: به دو روش صورت می گیرد 1- در پایان رشته علامت $$ 2- طول رشته را به عنوان فیلد اضافه در یک آرایه نگه‌داشت.

3- ذخیره رشته‌ها بصورت پیوندی : این روش استفاده زیاد دارد.

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

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

مثال: رشته ‘The End’

هر گره یک کاراکتر:

هر گره سه کاراکتر:

عملیات بر روی رشته‌ها:

     زیر رشته: مستلزم داشتن اطلاعات زیر است: 1- نام رشته یا خود رشته. 

2- مکان اولین کاراکتر زیر رشته در رشته داده شده .

 3- طول زیر رشته یا مکان آخرین کاراکتر زیر رشته.

SOBSTRING (String  , initial , length)

1در پاسکال :   S=’I am Learning Pascal’; S1=copy (S , 15 , 6) ; S1=’Pascal’

شاخص گذاری (تطبیق الگو): مکان یابی رشته P که برای نخستین‌بار‌، در رشته T ظاهر شده است.

INDEX (text , pattern)

 اتصال دو رشته: S111S2

طول رشته: تعداد کاراکترهای داخل یک رشته، برای تعیین طول می‌نویسیم.

مثال:                 Length (String)

       length (‘ o ’)=1

      2-  در پاسکال :          S:=Concat (S1,S2)

پردازش کلمه یا رشته:

 1- جانشین سازی: یک رشته را جانشین رشته دیگر می‌کنیم. (text , pattern , pattern2)REPLACE

2- اضافه کردن : یک رشته در وسط متن اضافه می‌شود. INSERT (text , position , string)

3- حذف کردن:  یک رشته از متن حذف می‌شود. DELETE (text , position , length)

توجه: شمارش از صفر

اجرای تابع  Replace(P2 به جای P1)

الگوریتم‌های تطبیق الگو:  مسأ‌له‌ای است که تعیین  می‌کند یک الگوی رشته‌ای داده شده p در متن رشته‌ای T وجود دارد یا خیر

(p کوچکتر از T)

الگوریتم

2- مقایسه wn با -3

در پاسکال برای جستجوی یک رشته S1 در رشته S2 بصورت زیر عمل می‌شود:

حذف و درج زیر رشته‌ در پاسکال:

تکلیف: 1- برنامه‌ای بنویسید که 100 رشته از ورودی دریافت و در یک آرایه به طول 100 از نوع String بریزد و به سوالات زیر جواب دهد:

1- تعداد کل کلمات  2- تعداد کل حروف      3- تعداد کل حروف صدا‌دار

2- برنامه‌ای بنویسید که یک اسم را از ورودی دریافت و آنرا برعکس چاپ کند.

3- برنامه‌ای بنویسید که تعدادی نام را از ورودی دریافت ودر یک فایل بریزد سپس فایل تشکیل شده را باز کرده و از روی این فایل دو فایل دیگر تشکیل دهید که در یکی از آنها اسامی که بین a تا u قرار گرفته‌اند ریخته و در فایل دوم کلیه اسامی که از v تا z هستند را بریزد.

برنامه‌نویس به C++ :

کامپیوتر وسیله‌ای است که داده‌ها و الگوریتم‌ها را گرفته‌، الگوریتم‌ها را بر روی داده‌ها اجرا می‌کند. کارایی برنامه وقتی تضمین می‌شود که داده ‌ها را خوب سازماندهی کرده الگوریتم خوبی برای پردازش و تجزیه و تحلیل انها انتخاب کنیم.

ساختمان داده‌ها: مدل منطقی یا ریاضی سازماندهی داده‌ها به یک شکل خاص، ساختمان داده نام دارد. (شیوه قرار گرفتن داده‌ها در حافظه کامپیوتر یا دیسک، ساختمان داده‌ها نامیده می‌شود)

برنامه = الگوریتم‌ها  + ساختمان داده‌

حل مسأله به وسیله کامپیوتر:  نیازمند استفاده از نرم‌افزار و سخت‌افزار است. توسعه نرم‌افزار شامل مراحل زیر است:

- تحلیل‌ مساله و مشخصات

- طراحی

- کد نویسی

- تست و اجرا و اشکال زدایی

- نگهداری

الگوریتم:  مجموعه‌ای از دستور ‌العمل‌ها که توسط کامپیوتر اجرا می‌شود. که باید دارای خصوصیات زیر باشد.

1- باید بدون ابهام، معین و قطعی باشد (هر مرحله روشن و واضح)

2- ساده باشد و توسط کامپیوتر قابل اجرا باشد.

3- خاتمه پذیر باشد.

الگوریتم‌ها شبیه برنامه‌ها هستند وتفاوت آنها در این  است که از Pseudecode (شبه کد) برای نوشتن دستورات استفاده می‌کنند که ترکیبی از زبان طبیعی ونمادها، عبارات و سایر ویژگی‌ها است. نمادها:

1- از نمادهای + ، -  و * برای عملیات محاسباتی

2- اسامی نمادین برای بخشی از پردازش‌ها

3- علامت‌های خاص مثل  برای نمایش توضیحات

4- واژه های کلیدی برنامه ها، مانند write, print, display, read

5-تورفتگی برای خوانایی برنامه‌ها

کارایی الگوریتم:  بر اساس دو معیار اندازه‌گیری می‌شود: - بهره‌وری از فضا Space utilization

-

برآورده کردن هر دو معیاربا هم امکان‌پذیرنیست. لذا، برنامه نویسی باید بین نیازمندی‌های فضا وزمان توازن ایجاد کند.

باتوجه به آنکه حافظه‌های با حجم بالا در دسترس است در حال حاضر زمان از اهمیت بیشتری برخوردار است.

محاسبه زمان اجرای الگوریتم :  تحت تاثیر عوامل زیر است:

(پیچیدگی زمانی)   1- ورودی  (تعداد) مثل مرتب‌سازی که به عناصر لیست بستگی دارد.    T(n)

2- نوع دستور‌العمل

3- کیفیت کد منبع: کیفیت که منبع بستگی به سه قاعده زیر دارد:

الف- برنامه‌ها و زیر برنامه‌های ساخت یافته : -استفاده از روش‌ پیمانه‌ای (modular) برای مسائل پیچیده

- استفاده از ساختارهای کنترلی

- استفاده از متغیرهای محلی در زیربرنامه‌ها

- تبادل اطلاعات با  زیر‌برنامه‌ها از طریق پارامتر

- حفاظت از پارامتر‌هایی که نباید تغییر کند.

- مقادیر عددی ثابت را به صورت ثوابت عددی تعریف کنید.

- کد را ساده و واضح بنویسید.

ب- مستند سازی برای تمام کدها: - برنامه باید دارای توضیحات در ابتدای ان باشد.

-  هر زیربرنامه مستند سازی شود.

- توضیح در کد برنامه

- از شناسه‌های بامعنی استفاده شود.

ج- زیبایی کد: - استفاده از حروف کوچک و بزرگ در جای مناسب.

- } و { در خطوط جداگانه

- تنظیم فرورفتگی‌ها

- فاصله بین عملوند با عملگر برای خوانایی بیشتر

- خروجی‌ها همراه با پیام باشند.

ADT (Abstract Data Type): وقتی در برنامه‌ای به نوعی داده نیاز باشد که در آن زبان وجود ندارد، برنامه‌نویسی باید نوع مورد نظرش را ایجاد کند. بنابراین، باید چگونگی ذخیره داده‌ها و عملیاتش را که بر روی آن داده‌ها عمل می‌کنند، مشخص کند.

آرایه در C++ و پاسکال:

آرایه یک بعدی = بردار    آرایه را می‌توان به عنوان نوعی ADT مطرح کرد.

مجموعه عناصر:

دنباله‌ای با طول ثابت (مجموعه مرتب) از عناصر که همگی از یک نوع‌اند.

عملیات  اصلی:

دستیابی مستقیم به هر عنصر آرایه به طوری که مقادیر را می‌توان از این عنصر بازیابی یا درآن ذخیره کرد.

معنای دستیابی مستقیم یا تصادفی به آرایه به معنای آن است که می‌توان با مشخص کردن محل آن  عنصر در آرایه به عنصر دستیابی پیدا کرد و دستیابی به  عنصر 5 و دستیابی به عنصر 35 به یک میزان زمان نیاز دارد.

روش اول:     

var

Name: array Type

روش دوم:

کامپایلر بلوکی از محل های متوالی حافظه را برای نگهداری آرایه با نام name به تعداد capity بلوک برای این آرایه انتخاب می‌کند.

پیاده‌سازی آرایه یک بعدی:

int  a[10];   به معنای تخصیص 10 خانه متوالی از حافظه است که در هر خانه یک عدد صحیح ذخیره می‌شود. اگر هر مقدار صحیح چهار بایت حافظه نیاز داشته باشد. و عنصر اول در base(a) قرار گیرد. محل عنصر i ام از فرمول زیر محاسبه می‌شود.