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

[مهدی]

ساختمان های داده ای،اجزای سازنده ی الگوریتم های رایانه ای هستند.طراحی یک الگوریتم همانند طراحی یک ساختمان است.اتاق های یک ساختمان باید به گونه ای در کنار هم قرار گیرند که برای کاربرد مورد نظر بیشترین کارایی را داشته باشند.برای این کار دانستن عملکرد،بهره وری،شکل و زیبایی،به تنهایی کافی نیست،بلکه به دانش کامل روش های ساختمان سازی نیازمندیم.ممکن است کارایی دلخواه ما قرار دادن اتاق در هوا،بین زمین و آسمان باشد،اما چنین کاری شدنی نیست یا ممکن است برخی ایده های شدنی،بسیار گران تمام شوند.به همین ترتیب طراحی یک الگوریتم باید بر مبنای درگ.کاملی از روش های ساختمان داده و هزینه ی هر یک از این روش ها باشد.[nb]برگرفته شده از کتاب طراحی الگوریتم ها[/nb]

در این تاپیک،یه روند آموزشی و پرسش و پاسخ در پیش می‌گیریم.

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


عناصر

از «عنصر» در تمام کتاب(در اینجا،تاپیک ) به عنوان نامی کلی برای هر نوع نامشخص داده استفاده می‌کنیم.یک عنصر،ممکن است عددی صحیح،مجموعه ای از اعداد صحیح،پرونده ای متنی یا ساختمان داده ی دیگری باشد. این واژه را هنگامی که مبحث مورد نظر،مستقل از نوع داده باشد،به کار می‌بریم.
برای نمونه،الگوریتم های مرتب سازی را در نظر بگیرید. اگر گام هایی که الگوریتم برمی‌دارد،تنها مقایسه‌ی عناصر یا جا به جا کردن آنها باشد؛ آنگاه میتوان از آن الگوریتم،هم برای مرتب سازی اعداد صحیح و هم برای مرتب سازی نام ها(یعنی رشته های کاراکتری) استفاده کرد.پیاده سازی این دو الگوریتم (یعنی برنامه ی آنها) احتمالا قدری متفاوت از یکدیگر است،اما هر دو از ایده های یکسانی بهره می‌برند.
از آنجایی که ما بر ایده های طراحی الگوریتم(و نه پیاده سازی آنها) تمرکز می‌کنیم،پس چشم پوشی از نوع عنصر عاقلانه است.

تنها سه پیش فرض برای عناصر در نظر می‌گیرم:
1-میتوان عناصر را با هم مقایسه کرد
2-همه ی عناصر به مجموعه هایی به ترتیب کلی تعلق دارد و از هر دو عنصر نابرابر،یکی «کوچکتر» از دیگری است.تا هنگامی که با مجموعه های ترتیب ناپذیر(مانند اعداد مختلط) سرو کار نداریم،به تعریف دقیق رابطه ی «کوچکتری»نخواهیم پرداخت.
3-از یک عنصر میتوان نسخه برداری کرد(یعنی کپی گرفت)



آرایه ها

آرایه را میتوان سطری از عناصر هم نوع در نظر گرفت.اندازه یک آرایه،تعداد عناصر آن است.
اندازه آرایه باید ثابت باشد.از آنجا که اندازه ی آرایه ثابت است و عناصرش نیز هم نوع هستند،پس مقدار حافظه ی لازم برای ذخیره ی آن از پیش آشکار است.برای مثال اکر عناصر آرایه نام هایی 8 کاراکتری باشند و هر کاراکتر نیازمند یک بایت حافظه بوده، طول آرایه هم 100 باشد؛برای ذخیره آن به 800 بایت حافظه نیاز داریم. عناصر آرایه همواره پشت سر هم ذخیره می‌شوند.اگر اولین بایت یک آرایه در محل x از حافظه ذخیره شود،آنگاه محل ذخیره ی Kاُمین بایت آرایه خانه ی x+k-1 از حافظه خواهد بود.
پس به آسانی میتوان محل هر عنصر آرایه در حافظه را محاسبه مرد.در مثال پیش،اکر محل شروع آرایه 10000باشد،پنجاه و پنجمین نام از بایت چهارصد و سی و سوم آغاز می‌شود،
یعنی محل 10432از حافظه.(در این مثال،فرض بر این اساس که محل های حافظه را بایت به بایت می‌شماریم،اما اگر شمارش به صورت دیگری هم انجام شود،به آسانی میتوان محاسبات را تغییر داد و محل مورد نظر را به درستی پیدا کرد.)

 

[مهدی]

پاسخ : مقدمه و سوالاتی پیرامون داده ساختار ها

رکورد ها

رکورد نیز شبیه آرایه است،با این تفاوت که عناصر آن را هم نوع در نظر نمیگیریم.پس یک رکورد مجموعه ای از چند عنصر گوناگون است که به شیوه ی مشخصی کنار یکدیگر قرار گرفته اند.اندازه ی حافظه ی مورد نیاز برای ذخیره ی یک رکورد
(همانند آرایه)روشن است.
میتوان به هر یک از عناصر رکورد در زمانی ثابت دسترسی پیدا کرد.این کار با نگهداری رکورد به صورت یک آرایه انجام می شود ،به گونه ای که هر عنصر این آرایه از محل ویژه ی خود آغاز گردد.نگه داری یک رکورد به صورت آرایه،برای دسترسی به عناصر
آن در زمانی ثابت ضروری است. دسترسی، با مراجعه به محل عنصر در آرایه گفته شده انجام میشود .کامپایلر،خود،برنامه ای را که برای مدیریت آرایه لازم است،ایجاد خواهد کرد.مثلا ممکن است رکوردی شامل دو عدد صحیح، 3 آرایه 20 تایی از اعدادصحیح، 4 عدد صحیح دیگر و 2 نام 12 کاراکتری باشد.(توجه کنید که هر دو نوع ارایه ی مختلفِ موجود در این رکورد ،خود عنصر هایی از رکورد هستند.) این رکورد در شکل 4-1 تعریف شده است.
در آرایه ی ذخیره کننده این رکورد ،مکان شروع این عنصرها با توجه به ترتیب نسبی آن ها و محل شروع آرایه در حافظه،
قابل محاسبه است.بنابراین اگر اعداد صحیح 4 بایت جا بگیرند،Int6 که نهمین عنصر رکورد است،از بایت 261(یعنی1+3*4+3*20*4+2*4)آغاز میشود.
از آن جایی که اندازه ی همه ی عنصرهای رکورد مشخص است،پس میتوان محل هر عنصر را در زمانی ثابت حساب کرد.مانند آرایه،فضای ذخیره سازی رکورد نیز همواره ترتیبی است و باز مانند آرایه ها نمیتوان پس از تعریف عنصری را به رکورد افزود.1

record example1]
begin
       Int1 : integer;        
       Int2 : integer;      
       Ar1 : array [1..20] of integer;
       Ar2 : array [1..20] of integer;
       Ar3 : array [1..20] if integer;
       Int3 : integer;
       Int4 : integer;    
       Int5 : integer;     
       Int6 : integer;    
       Name1 : array [1..12] of character;      
       Name2 : array [1..20] of character;      
end

[nb]شکل 4-1[/nb]