پایان نامه gl/l (485)

ععناصر که چند

موجوديت Entity : شيء است که داراي خصيصهها با خواص معين باشد و ممکن است مقاديري به آن نسبت داده شود موجوديت کارمند داراي خصيصههاي :
اسم ، سن ، جنسيت، SSN (شمارة تامين اجتماعي)

مقادير علي 24 مرد 14235

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A(1) , A(2) , …. , A(n) و يا نماد کروشهاي A[1] , A[2] , … A[n]

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

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

STUDENT [2] = Ali m.

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

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

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

دوانديس داريم: مثال: فروشگاه زنجيرهاي که از 28 فروشگاه که هر کدام 4 بخش دارند تشکيل شده (فروش/ هفتگي) دانشگاه آزاد که هر کدام از واحدها چند رشته دارند (تعداد دانشجو)
4 3 2 1 Derb.
store

28702 1
2
.
.
.
28

Pointer مشتري

a
b
a
d
c
b
a
.
. A
B
C
D
.
.
.
.
. 1
2
3
4
5
.
.
.

Pointer مشتري

3
2
1
1
2
1
3
1
1 A
B
C
D
1
2
3
0
1
1
0

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

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

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

3,6
1,2,4
. . . . a
b
c

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

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

3
2
1 a
b
c

Link مشتري

5 A 1
2
3
.
.
.

4
6

7
8 B
C
D
E
.
.

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

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

درختها:

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

کارمند

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

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

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

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

پیمایش: دسترسی به اطلاعات یک رکورد آن هم دقیقاً یکبار پیمایش می گویند.
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” || '('|| ‘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 : آسان هر رکورد معين (طول نبايد بيشتر از طول ثابت رکورد باشد)

معايب : 1- اگر فضاهاي خالي زياد باشد خواندن تمام رکورد هدر رفتن زمان

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 (‘ ( ’)=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

کارايي زمان time efficincy
برآورده کردن هر دو معياربا هم امکانپذيرنيست. لذا، برنامه نويسي بايد بين نيازمنديهاي فضا وزمان توازن ايجاد کند.
باتوجه به آنکه حافظههاي با حجم بالا در دسترس است در حال حاضر زمان از اهميت بيشتري برخوردار است.

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

(پيچيدگي زماني) 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 ام از فرمول زير محاسبه ميشود.

(بايت) size = 4 ، عنصر اول : base(a) + 4

حد پائين = 1 = base (a) + (i+1)*size آدرس a[i]

حد پائين = L = base (a) + (i-L) * size آدرس a[i]

مثال : base (a) , int A[15] برابر با 512 و مقادير صحيح 4 بايت از حافظه را اشکال کننده آدرس A[7] = ?

کاربردهاي آرايه يک بعدي:

1- مرتبسازي2- جستجوي 1.2- معمولي (خطي)

2.2- دودويي

1- مرتب سازي آرايهاي خطي با n عنصر از طريق الگوريتم انتخابي:

ورودي : مقدار صحيح n وآرايه x

خروجي: ارايه x مرتب شده صعودي

الگوريتم: 1- براي i=0 تا n-2 مراحل زير را انجام بده: براي تکتک مکانهاي آرايه اين کار تکرار ميشود.

2- min = i

3- براي j=i+1 تا n-1 اعمال زير را انجام بده:

4- اگر x[j]

5- min = j

6- ; tem = x [i ] ;

7- x[i] = x [min] ;

8- x [min] = item ;

پيادهسازي الگوريتم بالا به زبان C++ و پاسکال:
Pascal:
Program data ;
Uses crt ;
Const n=5 ;
Type
at = array [ 0 … 4] of integer ;
var
x: at ;
procedure select (var x:at ; integer) ;
var i , j , item , min : integer ; C++ :
# include ‘io stream.h’
# include ‘conio.h’
template
void select (T x [] , const int n)
{
int min , item ;
for (int i=0 ; i{
min = i ;

Begin
for i:= 0 to n-2 do
begin
min := i ;
for j:=i+1 to n-1 do
if [j] item := x [i] :
x[i] := x [min] ;
x[min] := item ;
end ; {for}
end ; {procedure}
{*******}
begin
clrscr ;
write (‘Enter’ , n , ‘numbers:’) ;
for i:= 0 to n-1 do
read (x[i]) ;
select (x , n);
write (‘sorted data is:’);
for i := 0 to n-1 do
write (x[i] : 3) ;
readln ;
end.

تعداد تكرار براي حلقه داخلي:
For (int j = I +1 ; If (x[i] Min=j ;
Item = x[i];
x[i]=x[min] ;
x[min]=item;
}
}

int main ()
{
const int = 5 ;
int x [n];
clrscr ();
cout for (int i := 0 ; icin >> x[i] ;
select (x,n) ;
cout cout getch () ;
return 0 ;
}
T(n) = (n-1) + (n+2) + … +1
=

همانطور که مشاهده ميشود T(n) برحسب ازn از مرتبه دوم است و آن را به صورت O(n2) نمايش ميدهند.

2- جستجو :

2,1: جستجو آرايه معمولي: پيدا کردن مقداري درآرايه . ورودي : n، آرايه x به طول n و item مورد نظر

خروجي: در صورت پيدا کردن 1، درغير اينصورت 0

1- 0 را در found قرار بده.

2- 0 را در loc قرار بده.

3- تا زمانيکه foundzo Loc

4- اگر item = = x[loc] آنگاه

5- 1 را در found قرار بده.

6- و اگر نه Loc را يک واحد اضافه کن

7- found را برگردان

پياده سازي الگوريتم به زبان C++ و پاسکال:
Pascal :
Program data ;
uses crt;
const n=5 ;
Type
at = array [0 , 4] of integer;
Var i , item : integer ;
x: at ;
found : boolean ;
Procedure Isearch (var x:at ; n:integer item:integer ; var
Var loc : integer ;
begin
found:= false ;
for loc := 0 to n-1 do
If x[loc]=item then
Begin
found::= true ;
break ;
end ;
end ; {procedure}
{********}
begin
clrscr;
write (‘Enter’ , n , ‘number:’) ;
for i:= 0 to n-1 do
read (x[i]) ;
write (‘Enter item to search:’) ;
readln (item ) ;
Isearch (x , n , item , found) ;
if (found) then
write (‘item exist’)
else
write (‘Item not exist’) ;
readln ;
پيچيدگي O (n)
end. C++;
# include “ iostream.h”
# include “conio.h”
template
int Isearch (T x[] , coust int n , T item)
{
int loc , found = 0 ;
for (Loc = 0 ; loc , Loc ++ )
If (x[loc]= = item)
Found = 1 ;
return found ;
}
int main ()
{
const int n=5 ;
int item , x[n] ;
clrscr () ;
cout for (int i=0 ; i cin >> x [i] ;
cout cin >> item;
If (Isearch (x , n , item))
cout else
cout getch () ;
return 0 ;
}

2-2- جستجو در آرايه دودويي: اين نوع جستجو فقط درآرايه مرتب صورت ميگيرد.

ورودي : n و آرايه صعودي x و item مورد نظر

خروجي: 1 و در صورت وجود ، 0 عدم وجود.

الگوريتم:

0 found

0 first

n-1 را در Last قرار بده.

تا زمانيکه first

(first + last) loc

اگر item

loc-1 last / *جستجو در بخش اول */

و اگر نه ، اگر item > a [loc] آنگاه

Loc+1 first /* جستجو در بخش دوم */

و اگر نه 1 found
پيادهسازي الگوريتم به C++ وپاسکال:
Pascal ;
Program data ;
Uses crt ;
Const n=5 ;
Type
At=array [0 … 4] of integer ;
Var I , item: integer ;
X: at ;
Found : Boolean ;
Procedure bsearch (var x:at ; n: integer ; item : integer) ;
Var found : Boolean
Var loc , first , last : integer ;
begin
Found := false;
First := 0 ;
Last := n-1 ;
While (first begin
Loc := (first + last) div 2 ;
If item Last := loc -1
else if item>x[loc] then
First := loc +1 ;
Else
Found := true ;
end;
end ; {procedure}
{********}
begin
clrscr;
write (‘Enter’ , n , ‘numbers:’);
for i:= 0 to n-1 do
read (x[i]);
write (‘Enter item to search:’);
readln (item) ;
b search (x, n , item , found) ;
if (found) then
write (‘item exist')
else
write (‘item not exist:’) ;
readln ;
end . C++
# include ‘iostreach’
# include “conio.h”
else
Found = 1 ;
}
return found;
}
int main ()
{
const int n=5 ;
Int item, x[n]
clrscr () ;
cout for (int i:= 0 icin >> x[i] ;
cout cin >> item ;
if (bsearch (x , n , item)) ;
cout Else
cout getch ;
return ;
}

مقايسه جستجوي ترتيبي ودودويي براي تعداد : n=1024

ترتيبي دودويي

در بدترين حالت: 1024log21024=10

آرايههاي دو بعدي:

اعلان در پاسکال

روش اول:

Var

;نوع Name array [DIM1,DIM2] of

روش دوم:

Type

;نوع Array type = array [DIM1,DIM2] of

var

name : array type ;

يک ساختمان داده منطقي است که در برنامهنويسي مسائل بکار ميرود. به خصوص براي توصيف اشياي فيزيکي دو بعدي، مثل نقشه صفحه شطرنج مثل نمره 30 دانشجو که 5 بار امتحان دادند.

Var

Grade : array [1 .. 30 , 1 … 5] of signal ;

پيادهسازي آرايههاي دو بعدي:

آرايه دو بعدي از نظر منطقي بصورت دو بعدي و از نظر فيزيکي بصورت خطي (در محلهاي متوالي حافظه) ذخيره ميشود. آرايههاي دو بعدي ميتوانند بصورت سطري يا ستوني ذخيره شوند. در روش سطري، ابتدا عناصر سطر اول، سپس عناصر سطر دوم و غيره ذخيره ميشوند. در روش ستوني، ابتدا عناصر ستون اول، سپس عناصر ستون دوم و غيره ذخيره ميشوند. در پاسکال آرايهها بصورت سطري ذخيره ميشوند:

Var

a: array [1.. 3 , 1 .. 5] of integer ;

پيدا کردن مکان يک عنصر آرايه:

آدرس پايه: base(a) عنصر مورد نظر : a[i , j ]

طول هر عنصر : size آرايه n×m

اين بدا معني است که براي پيدا کردن اين عنصر بايد از (i-1) سطر بگذريم:

base (a) + (i-1) * n * size = آدرس اولين عنصر سطر i

فاصله اولين عنصر سطر i و ستون i = (j-1) * size

بنابراين آدرس عنصر base(a) + (i-1) *n* size + (j-1) * size : a[i,j]

مثال: ارايه m=3 و n=5 طول هر مقدار صحيح = 4 بايت:

آدرس ?=a[2,4] base(a)+((2-1)*5(4-1))*4=base(a)=32= آدرس a[2,4]

حال اگر حد پائين هر بعد آرايه نامشخص باشد فرمول آدرس يک عنصر آرايه بصورت زير درميآيد:

Base(a)+(i-f1)*(u2-f2+1)*size + (j-f2)*size = آدرس a[i,j]

کاربرد آرايههاي دو بعدي:

نام ديگر اين آرايهها ماتريس است و براي حل مسائل بسيار مورد استفاده قرار ميگيرند.

جمع و تفريق ماتريسها:

جمع و تفريق دو عملي هستند که به سادگي بر روي ماتريسها انجام ميشوند. درجمع و تفريق تعداد سطرها و ستونهاي ماتريس بايد برابر باشند.

در اينجا دو ماتريس 3×3 را با هم جمع و تفريق ميکنيم.

Program data;

uses crt ;

const n = 3 ;

type

at=array[0..2 , 0..2] of integer ;

var

i,j : integer

a,b,sub,add: at

procedure sub add (a:at , b:at , var sub: at , var add:at) ;

const n=3 ;

var i,j : integer ;

begin

for i:=0 to n-1 do

for j:= 0 to n-1 do

begin

sub[i,j] := a[i,j] – b [i,j] ;

add[i,j]:= a[i,j]+b[i,j] ;

end;

end; {produre}

{*******}

begin

clrscr;

for i:=0 to n-1 do

for j:=0 to n-1 do

begin

write (‘Enter a[‘ , i ,’,’ , j , ‘]:’) ;

read (a[i,j]) ;

end;

for i:=0 to n-1 do

for j:= 0 to n-1 do

begin

write(‘Enter b[‘ , i , ‘ , ’ , j , ‘]:’) ;

read (b[i,j]) ;

end ;

sub Add (a,b,sub,add) ;

writeln (‘sub[n,n] is :’) ;

for i=: 0 to n-1 do

begin

for j: = 0 to n-1 do

write (sub [i,j]: 5) ;

writeln ;

end ;

writeln (‘add[n,n] is :’) ;

for i:= 0 to n-1 do

begin

for i:=0 to n-1 do

write (add [i,j]:5) ;

writeln ;

end ;

readln ;

end .

ضريب دو ماتريس:

ضرب دو ماتريس در صورتي انجامپذير است که تعداد ستونهاي ماتريس اول برابر با تعداد سطرهاي ماتريس دوم باشد.

Program data ;

uses crt ;

type

at1:= array[0..1 , 0..2] of integer ;

at2:= array [0..2 , 0..3] of integer ;

at3 := array[0..1 , 0..3] of integer ;

var

i,j : integer ;

m1: at1 ;

m2: at2 ;

m3: at3 ;

procedure multiply (m1;at1;m2:at2 ; var m3:at3) ;

var i,j,k: integer ;

begin

for i:= 0 to 1 do

for j:= 0 to 3 do

for k:=0 to 2 do

m3[i,j] := m3 [i,j] + m1 [i,k] * m2 [k,j] ;

end ; {procedure}

{*******}

begin

clrscr ;

{read m1 }

for i:= 0 to 1 do

for j:= 0 to 2 do

begin

write (‘Enter m1[‘,i,’,’ , j , ‘]:’) ;

read (m1 [i,j]) ;

end;

{read m2}

for i:= 0 to 2 do

for j:=0 to 3 do

begin

write (‘Enter m2 [‘ , i , ‘,’ , j , ‘]:’) ;

read (m2 [i,j]) ;

end ;

multiply (m1 , m2 , m3) ;

writeln (‘m3[n,n] is:’) ;

for i:= 0 to 1 do

begin

for i:= 0 to 3 do

write (m3[i,j]:5) ;

writeln ;

end ;

readln ;

end.

ترانهاده ماتريس: برنامهاي بنويسيد که يك ماتريس را از ورودي خوانده به رويهاي ارسال کند و رويه ترانهاده آن را محاسبه کند.

program data ;

uses , crt ;

type

at1 = array[0..2 , 0..3] of integer ;

at2 = array [0..3 , 0.. 2] of integer ;

var

i,j: integer ;

m:at1 ;

t : at2 ;

procedure transpose (m:at1 ; var t:at2) ;

var i,j: integer ;

begin

for := 0 to 3 do

for j:= 0 to 2 do

t[i,j]:= m[i,j] ;

end ; {procedure}

ماتريس اسپارس: ماتريسي که تعداد زيادي از عناصر آن صفر باشد ماتريس اسپارس ناميده ميشود.

کارهايي که در مورد ماتريس انجام ميگيرند بر روي عناصر غير صفر انجام ميشود بنابراين:

لازم نيست عناصر صفر ماتريس در حافظه ذخيره شوند. لذا نمايش معمولي ماتريس در مورد اين نوع ماتريسها مناسب نيست.

براي نمايش آنها از ماتريس استفاده ميشود که داراي سه ستون است. ستون اول حاوي شماره سطر مقدار غير صفر، ستون دوم حاوي شماره ستون مقدار غير صفر و ستون سوم حاوي خود مقدار غير صفر است اگر تعداد عناصر غير صفر ماتريس اصلي n باشد آنگاه نمايش ماتريس اسپارس داراي n+1 سطر است.

مشخصات کلي
3 1 3

3 1 0

6 0 1

2 3 2

ب: نمايش ماتريسي اسپارس الف- ماتريس اسپارس

بايت 60 =4 × 5 × 3= حافظه A

بايت 48 = 4×3×4 = حافظه AS

تمرين: نمايش زير را براي ماتريس اسپارس در نظر بگيريد وسپس ماتريس اسپارس اوليه را بدست آوريد و فضاي حافظه آنها را مقايسه کنيد:
2 5

4

6 2 0

8 0 3

حل :

تمرين منزل 1- ترانهاده ماتريس اسپارس

2- جمع دو ماتريس اسپارس

ماتريسهاي پائين مثلثي و بالا مثلثي:

ماتريس پائيني مثلثي x ماتريس مربعي است که تمام عناصر بالاي قطر اصلي آن صفر هستند يعني m يک آرايه دو بعدي است که به ازاي i>j عناصر m[i,j] صفر هستند.

مثال: ماتريس بالا مثلثي A :

الف- ميزان حافظه مصرفي ؟

ب- عناصر غير صفر را در يک ارايه يك بعدي ذخيره کرده و ميزان حافظه مصرفي را مشخص کنيد.

بايت 64=4×4×4 = مقدار حافظه A
5 4 1 3 2 2 2 1 4 3

B

آرايههاي چند بعدي:

در پاسکال آرايه سه بعدي:

var

b:array[0..2 , 0..1 , 0..3] of integer ;

آرايه يک بعدي با يک "خط"، دو بعدي با يک "صفحه" و سه بعدي با "کتاب" قابل قياس است.

براي ذخيره يک ماتريس 1 بعدي:

همانطور که مشاهده ميشود انديس خارجي با سرعت بيشتري تغيير ميکند مانند: کليومتر شماره اتومبيل که رقم سمت راست با سرعت بيشتر تغيير ميکند:

مشکلات آرايهها:

1- آرايه در پاسکال به عنوان نوع تلقي ميشود.

type at = array [1 ..4] of integer ;

at 1= array [1..4] of integer ;

var

x:at ;

y:at1 ;

با اين که ساختار اين دو ارايه دقيقاً يکسان است، ولي همنوع تلي نميشوند، در صورتيکه از دستور x:=y استفاده کنيم پيغام خطاي Type mismatch صادر ميشود.

2- ظرفيت آرايه در طول اجراي برنامه تغيير نميکند بايد در هنگام اعلان به اندازه کافي بزرگ باشد، که ممکن است منجر به اتلاف حافظه شود.

3- درج کردن مقداري در بين مقاديرديگر درآرايه، مستلزم جابجايي عناصر است.

4- حذف مقداري از آرايه نيز مستلزم جابجايي عناصر است.

پشته:

ساختمان داده اي است که در کامپيوتر کاربرد زيادي دارد.

عمل حذف ودرج عنصر در يک طرف انجام ميشود. LIFO (خروج به ترتيب عکس ورود)

مثالها: چيدن کتابها روي هم، که زمان برداشتن آخرين کتاب برداشته ميشود.

چيدن سکهها روي هم

بشقابهاي روي هم در رستورانها

سمتي که عناصر قابل دسترسي هستند بالاي پشته نام دارد.

عمليات اصلي روي پشتهها:

Creator : ايجاد کننده پشته

Empty : خالي بودن پشته را تست ميکند.

Push : افزودن عنصر به بالاي پشته

Pop : حذف عنصر از بالاي پشته

Top : بازيابي عنصر بالاي پشته

Push(s,item)

Pop(s)

Top(s)

x:= pop(s);

push(s,x) ;

* پاريز (under flow) : تلاش براي دستيابي به عنصري از بالاي پشته خالي.

پشته را به دو شکل ميتوان پيادهسازي کرد:

1- خطي – استفاده از آرايه

2- پيوندي – استفاده از ليست پيوندي

از آرايه استفاه ميگردد ولي بايد دقت کرد تفاوت اساسي با يکديگر دارند: تعداد عناصر آرايه ثابت است ودر هنگام تعريف مشخص ميشود و قابل تغيير نيست درحاليکه در پشته، طول آن با درج وحذف عنصر تغيير ميکند.

براي رفع اين مشکل و اينکه بتوان پشته را نمايش داد، گنجايش حداکثر تعداد عناصر پشته را براي آرايه در نظر ميگيرند يک طرف آرايه انتهاي شيشه وطرف ديگر بالاي پشته است:

پيادهسازي پشته با آرايه:

از متغيري به نام mytop براي نگهداري بالاي پشته استفاده ميشود.

تعريف پشته:

چون پشته از يک متغير و يک آرايه تشکيل ميشودسپس يک رکورد تعريف ميکنيم:

Const size = 100 ;

type

stack := record

MyTop : integer ;

item : array [0..size-1] ;

end ;

var

s:stack ;

عناصر پشته در s.items ذخيره ميشوند.

متغير myTop نشان دهنده موقعيت عنصر بالاي پشته در آراية items است.

پيادهسازي عمل ايجاد پشته:

Const size = 100 ;

Type

Stack=record ;

myTop : integer ;

item : array [0..size1] of integer ;

end ;

var

s:stack;

تست خالي بودن با s.myTop=-1 امکانپذير است ولي به دو دليل زير تابع empty راتعريف ميکنيم:

1- بالا بردن خوانايي برنامه

2- به کارگيري پشته، مستقل از نحوه پيادهسازي (ايجاد استاندارد)

پيادهسازي عمل تست خالي بودن پشته:

Function empty (s:stack) : Boolean ;

Begin

If

S:myTop=-1 then

Empty := true

Else

Empty:=false

End; {function}

پيادهسازي عمل حذف از پشته:

عمل pop سه وظيفه انجام ميدهد: 1- اگر پشته خالي باشد، پيام اخطار چاپ کرده و اجراي برنامه را خاتمه ميدهد.

2- عنصر بالاي پشته را حذف ميکند.

3- عنصر بالاي پشته را به برنامه فراخوان برميگرداند.

Procedure pop (var s:stack ; var x:integer) ;

Begin

if empty (s) then

write (‘stack is empty.’)

else

begin