پاورپوینت آرایه ها و ساختارها

بخشی از پاورپوینت

اسلاید 1 :

فصل دوم : آرايه ها و ساختارها
اهداف
در اين فصل دانشجو با کاربرد موارد زير آشنا خواهد شد:

آرايه
ليست
چند جمله اي
ماتريس خلوت
رشته

اسلاید 2 :

آرايه مجموعه اي از زوج ها ، شامل انديس و مقدار است (,) . به ازاي هر انديس يک مقدار مربوط به آن انديس وجود دارد که به زبان رياضي آنرا تناظر يا انگاشت مينامند.

در رابطه با آرايه به دو عمل اساسي نياز است :

اسلاید 3 :

آرايه نوعي ساختمان داده است كه عناصر آن هم نوع بوده و هر يك از عناصر با يك انديس و بصورت مستقيم قابل دستيابي ميباشد.
آرايه ميتواند يك بعدي و يا چند بعدي باشد
آرايه هاي دو بعدي را با نام ماتريس ميشناسيم

اسلاید 5 :

1-2 آرايه ها
آرايه در زبان C به صورت مثال در زير آمده است :
int list [5]
در زبان C تمام آرايه ها از انديس 0 شروع مي شوند.
آرايه اي با n عنصر با انديسهاي 0 تا n-1 ميتوان به درايههاي آن دسترسي پيدا كرد
نکته

اسلاید 6 :

ليست
ساده ترين و متداول ترين نوع ساختمان داده ها ، ليست هاي مرتب شده يا خطي هستند.
ليست
مثال :
روزهاي هفته ( شنبه . جمعه )

اسلاید 7 :

پيدا کردن طول يک ليست
خواندن اقلام داده يک ليست از چپ به راست يا بر عکس
بازيابي i امين عنصر از يک ليست (0≤ i < n)
تعويض يک قلم اطلاعاتي در i امين موقعيت يک ليست (0≤ i ≤ n)
درج يک قلم داده جديد در i امين موقعيت يک ليست (0≤ i < n).
( اقلام داده اي که قبلا به صورت i ، i+1 ،…،n-1 شماره گذاري شده اند به صورت i+1،i+2،…،n در مي آيند)
حذف يک قلم اطلاعاتي از i امين موقعيت يک ليست (0≤ i < n) . اقلام داده i+1،…،n-1 به اقلام داده با شماره I،i+1،…،n-2 تبديل مي شود.
اعمال صورت گرفته بر روي ليست ها

اسلاید 8 :

نگاشت ترتيبي
متداول ترين پياده سازي ، نمايش يک ليست مرتب شده به صورت يک آرايه مي باشد به نحوي که عنصر iام ليست با انديس i آرايه متناظر باشد. اين مطلب يک نگاشت ترتيبي ناميده مي شود.
نگاشت ترتيبي

اسلاید 9 :

ليست پيوندي
راه حل ديگر براي پياده سازي ليست، ذخيره در يك ليست پيوندي ميباشد كه هر گره از ليست حاوي دو عنصر انديس و مقدار ميباشد.
ليست پيوندي

اسلاید 10 :

ما نيازمند ساخت يك نوع داده اي تجريدي براي نمايش و پردازش چندجملهاي نمادين هستيم.
منظور از نمادين ليستي از ضرايب و توانهاست كه با هم چند جمله اي را تشكيل ميدهند.
نوع داده اي چند جملهاي (Polynomial)

اسلاید 11 :

چند جملهاي ها (ادامه.)
بزرگترين توان x در چند جمله اي را درجه چند جمله اي ميگويند.
PA درجه چند جمله اي A(x)

اسلاید 12 :

پياده سازي چند جمله ايها
استفاده از آرايه
در اين روش انديس آرايه معرف توان x و مقدار ذخيره شده معرف ضريب ميباشد.
مثال:

اسلاید 13 :

بطور كلي اگر به صورت كلاس بنويسيم كلاس چند جمله اي به شكل زير خواهد بود.
كلاس مربوط به چند جملهاي

پياده سازي 1
پياده سازي 2

اسلاید 14 :

در اين چندجملهاي ها ضرايب صفر زياد هستند مثلاً x1000 + 1 داراي 999 صفر است.
براي ذخيره چند جملهاي هاي خلوت از ساختار زير استفاده ميكنيم
عناصر بر اساس قواي صعودي و يا نزولي مرتب ميشوند
چند جمله اي هاي تنك (خلوت)

اسلاید 15 :

كلاس مربوط به چند جملهايهاي خلوت

اسلاید 16 :

جمع دو چند جمله اي خلوت

اسلاید 18 :

برنامه اي بنويسيد كه دو چند جمله اي خلوت را در هم ضرب نمايد.
براي پياده سازي تابع ضرب در صورت نياز توابع ديگري كه كار شما را ساده تر سازد را نيز ميتوانيد تعريف نماييد
تمرين 1
(زمان تحويل جلسه آينده)

اسلاید 19 :

ADT ماتريس
به طور کلي در رياضيات ، يک ماتريس شامل m سطر و n ستون بوده و مي تواند مانند شکل زير نمايش داده شود.

اسلاید 20 :

ADT ماتريس اسپارس (ماتريس خلوت)
در علوم کامپيوتر متداول ترين نمايش براي ماتريس آرايه دوبعدي است که به صورت a[MAX_ROW][MAX_COLS] نمايش داده مي شود. هر عنصر ماتريس به صورت a[i][j] نمايش داده مي شود. ماتريسي که عناصر صفر آن زياد باشد ماتريس اسپارس ناميده مي شود.
ماتريس اسپارس
حداقل اعمال ممکن شامل ايجاد، جمع ، ضرب و ترانهاده ماتريس ميباشد.