مقدمه
مطالعه و بررسی ساختمان داده ها جزء اصلی و اجباری برنامه ی هر دانشجوی علم کامپیوتر است . کامپیوتر علم پرفسونی است که فسون آن در ساختمان داده ها متجلی است . ساختمان داده ها یکی از زیباترین مباحث و نیرومندترین ابزار در حل مسائل کامپیوتری است . در این گزارش بیشتر به تئوری پرداخته و عاری از لفاظی و توصیفهای ناضرور است .
اصول ساختمان داده ها سیمور لیپ شوتز
دپارتمان کامپیوتر دانشگاه تِهپل
سیمپور لیپ شوتز / مهندس حسین ابراهیم زاده ی قلزم
هوروتیز – تننباوم
و ساختمان داده ها / مهندس حمیدرضا تجسمی
فصل اول
- زیر برنامه های بازگشتی
- دو شیوه تحلیل و برنامه نویسی
- الگوریتم
- ساختمان داده ها
- زیر برنامه های بازگشتی در پاسکال
- زیر برنامه های باز گشتی در زبان نویسی c
« زیر برنامه های بازگشتی »
فصل اول
شیوه تحلیل و برنامه نویسی :
به طور کلی در تحلیل یک سیستم دو شیوه وجود دارد : 1- شیوه از پایین به بالا (Down Top )که روشی غیر ساختیاخته و قدیمی است و بیشتر بر نکات صحیح که نویسی تاکید دارد .
2- شیوه از بالا به پایین (Top Down) که در ابتدا برنامه به بخش ها و بلوکهای مشخص تقسیم شده و سپس هر قسمت و بلوک نوشته می شود . نام دیگر این روش برنامه نویسی اولیه ای یا مالاژولار است .
الگوریتم
تعریف : الگوریتم مجموعه محدودی از دستور العمل هاست که اگر دنبال شوند موجب انجام کار خاصی می گردد هر الگوریتم ویژگیهای زیر را داراست :
1- ورودی : یک الگوریتم می تواند هیچ یا چندین کمیت ورودی داشته باشد .
2- خروجی : الگوریتم باید حداقل یک کمیت به عنوان خروجی ایجاد کند .
3- قطعیت : هر دستور العمل باید بدون ابهام و کاملا" واضح باشد .
4- محدودیت : الگوریتم باید پس از طی مراحل محدودی خاتمه یابد .
5- کارایی : هر دستورالعمل باید به گونه ای باشد که با استفاده از قلم و کاغذ بتوان آن را با دست نیز اجراء کرد به عبارت دیگر هر دستور العمل باید انجام پذیر باشد .
ساختمان داده ها (Data Structures)
ساختارهایی که جهت دریافت داده های خام به شکل مناسب توسط کامپیوتر و پیاده سازی و اجرای الگوریتم های مختلف روی آنها مورد استفاده قرار می گیرند ساختمان داده نامیده می شوند . یک نمونه از تقسیم بندی ساختمان داده های مختلف به شکل زیر است :
ساختار ساختمان داده های ایستا در طول حیاتشان تغییر نمی کند ولی در مدل پویا تغییرات نامحدود و مجاز است .
زیر برنامه های باز گفتنی ( Recur Sion ) در پاسکال :
در پاسکال دو نوع برنامه داریم یکی تابع و دیگری پروسی جر
بعضی از مسائل طبیعت بازگشتی دارند مثلاً اگر به ما بگویند ! 5 برابر چند است با توجه به فرمول
! ( 1- n ) ٭ n = ! n می توانیم بگوییم که اگر !4 را بدانیم کافی است آن را در 5 ضرب کنیم پس مسأله !5 تبدیل به مسأله !4 می شود و الی آخر .
زیر برنامه های باز گفتنی دارای دو ویژگی اصلی هستند :
1- زیر برنامه ، خودش ، خودش را صدا می زند ( اغلب با آرگومان کمتر )
2- یک شرط جهت اتمام فراخوانی ها وجود دارد .
در پاسکال هم توابع و هم پروسی جر را می توان به صورت بازگشتنی نوشت .
مثال : برنامه ای بنویسید که عددی را خوانده و به کمک تابع بازگشتنی و غیر بازگشتنی !8 را محاسبه کرده و در قسمت اصلی آن را چاپ کند .
Var x : Integer ;
Funcfion Fact1 ( n : Integer ) : Integer ; تابع غیر بازگشتنی
Var I و f : integer ;
Begin
F : = 1 ;
For i = 1 to n do
F: F* i ;
Factt = F ;
End ;
Funcfion Fact( n : Integer ) : Integer ; تابع بازگشتی
Begin
Ip n <=1 then fact : =1
Else fact : = n* fact (n-1)
End;
Begin
Readln ( x ) ;
Writeln ( fact ( x ) ) ; Writeln ( fact ( x ) ) ;
End.
هر بار که تابع خود را فراخوانی می کند ، تمام متغیرهای محلی و پارامتر های آن دوباره فضای را از پشته می گیرند .و مقادیر جدید پارامترها در این فضا ذخیره می شوند و تابع با این مقادیر جدید اجرا می شوند برای فراخوانی های مکرر تابع ، هیچ فضایی برای ذخیره سازی مجدد که تابع اشغال نمی شود . برای سادگی فرض می کنیم عملیاتی که قرار است هم اکنون اجرا شوند ولی به علت فراخوانی مجدد تابع ، نمی توان آنها را اجرا کرد در داخل حافظه پشته (Stack ) ذخیره می گردند تا بعدا" اجرا می شوند حافظه Stackبصورت LIFO می باشد (Last In First Out) یعنی آخرین اطلاعات وارد شده ابتدا به خارج می شود .
- معمولا" مسائلی را با تکنیک Recursive حل می کنیم که حالت n ام آن به کمک حالت n-1 ام آن قابل بدست آوردن باشد بسیاری از مسائلی که الگوریتم حل آنها به ظاهر پیچیده است را به کمک تکنیک بازگشتی به راحتی می توان حل کرد .
- فریت روش Recursiveبه روش معمولی ، سادگی برنامه نویسی آن است و عیب آن مصرف زیاد حافظه ( بخاطر مصرف حافظه استک و فراخوانی های مکرر ) و نیز زمان زیادی است که برای فراخوانی ها صرف می شود .
- اگر زیر برنامه ای مرتبا" خودش را صدا بزند و شرطی برای اتمام فراخوانی ها وجود نداشته باشد پس از مدتی پیام خطای Stack Over flow در زمان اجرا صادر شده و اجرای برنامه توقف می شود .
مثال : در زیر فاکتوریل را به کمک پروسی جر بازگشتی بازنویسی می کنیم .
Procedure Fact (n : Integer ; Nar F : Infeger ) ;
Begin
If n=0 then exit
Else
F : = f * n ;
End ;
Var F: integer ;
Begin
F : =1 ;
Fact (4 , f ) ;
Write In ( f ) ;
End .
خروجی برنامه ی روبرو عدد 24 یعنی 4! می باشد هنگامی که پردازه fact بار اول با پارامتر ورودی n=4 صدا زده می شود چون شرط if نادرست است دستور جلوی else که فراخوانی مجرد fact است اجرا می گردد در اینحال دستور f : = f * 4 ; که اجرا نشده است در استک ذخیره می شود و به همین ترتیب داریم :
F : = f * 1
F : = f * 2 ;
F : = f * 3 ;
F : = f * 4 ;
هنگامی که بار آخر پردازه fact با پارامتر n=5 صدا زده می شود شرط if درست شده دستور exit اجرا می گردد در این حال پردازه تمام شده ولی دستورات موجود در پشته می بایست از بالا به پایین ( با قصد اولیه f=1 ) اجرا گردند . پس داریم :
F : = 1 * 1 =1
F : = 1 * 2 = 2
F : = 2 * 3 = 6
F : = 6 * 4 = 24
مثال : با توجه به فرمول زیر تابعی بازگشتی بنویسید که a * b را محاسبه کرده و برگرداند .
a if b = 1
a * b =
a + a * ( b -1 ) if b > 1
جواب :
Function Multiply ( a , b : integer ) : integer ;
Begin
if b = 1 Multiply : 1
else Multiply : = a + Multiply ( a , b -1 ) ;
End ;
زیر برنامه های بازگشتی در زبان C
در زبان C برخلاف پاسکال فقط یک نوع برنامه با نام تابع وجود دارد مفهوم و اصول توابع بازگشتی در C دقیقا" معادل پاسکال است و فقط قدرت Syntax آنها با یکدیگر تفاوت دارد مثلا" هنگامی که تابع پاسکال می خواهد مقداری را برگرداند ، آن مقدار در اسم تابع ریخته می شود ولی زبان Cمقداری بازگشتی جلوی دستور return نوشته می شود .
تابع بازگشتی در زبان C به صورت زیر است :
int fact ( int n )
if ( n < = 1 )
return 1 ;
else
return ( n * fact ( n -1 ) ) ;
ترسیم استک تابع فوق دقیقا" مثل تابع معادل پاسکال آن است به همین ترتیب تابعی که بصورت بازگشتی a * b را محاسبه کند بصورت زیر است :
int Multiply ( int a , int b )
if ( b ==1 ) return a ;
return ( a + multiply ( a , b -1 )) ;
- یکی از ویژگی های اصلی زیر برنامه های بازگشتی آن بود که « زیر برنامه ، خودش ، خودش را صدا بزند» . این ویژگی در مورد تابع پاسکال بدین معناست که در خطی اسم تابع هم در سمت چپ و هم در سمت راست عبارت دیده شود ( اغلب با آرگومان کمتر ) در مورد توابع C بدین معناست که جلوی دستور return نام تابع ( اغلب با آرگومان کمتر ) بیاید . این خاصیت در مورد پروسی جر پاسکال به این صورت است که نام پروسی جر درون بر نه پروسی جر ( اغلب با آرگومان کمتر ) دیده ی شود .