۰۹ مهر ۱۳۹۹

ساختمان داده ها

دانشکده / گروه دانشکده ریاضیات و علوم کامپیوتر/ گروه مهندسی برق، کامپیوتر و فناوری اطلاعات
رشته تحصیلی کارشناسی مهندسی کامپیوتر/ مهندسی فناوری اطلاعات
عنوان و کد درس ساختمان داده ها           
تعداد واحد و نوع 3 واحد اصلی
پیش نیاز درس ریاضیات گسسته و برنامه سازی پیشرفته
ترم تحصیلی نیمسال اول سال تحصیلی 95-96

 

نام استاد: :سمن شیشه چی
شماره اتاق: طبقه اول، دانشکده شهید مجید شهریاری، دفتر آموزشهای آزاد
شماره تماس: 0283-3894801 ,  0283-3894800
آدرس ایمیل:
saman.shishechi@gmail.com

دریافت نسخه الکترونیکی طرح درس

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

 

اهداف یادگیری درس:

:LO1 تجزیه و تحلیل ساختمان داده آرایه و پیاده سازی ساختار آن

:LO2 تجزیه و تحلیل ساختمان داده پشته و پیاده سازی ساختار آن

:LO3 تجزیه و تحلیل ساختمان داده انواع صف و پیاده سازی ساختار آنها و همچنین تشخیص تفاوت موجود بین آنها

:LO4 تجزیه و تحلیل ساختمان داده انواع لیست پیوندی و و پیاده سازی ساختار آنها و همچنین تشخیص تفاوت موجود بین آنها

:LO5 تجریه و تحلیل ساختار درخت و گراف و پیاده سازی آنها

LO6:تعیین و اندازه گیری پیچیدگی زمانی الگوریتم ها و مقایسه الگوریتمهای مرتب سازی

 

ماتریس همپوشانی اهداف یادگیری و حیطه یادگیری(LO->H3)

اهداف یادگیری درس

درکی ، شناختی

(Cognitive)

طراحانه و خلاقانه

(Psychomotor)

مدیریتی و عاطفی

(Affective)

LO1 2    
LO2 3 2 2
LO3 2    
LO4 3 3 2
LO5 2 1 1
LO6 2 1 1

نکته:  1=کم   2= متوسط   3= زیاد

 

روش تدریس و یادگیری

 تدریس با استفاده ازاسلایدهای درس و کتاب

حل تمرین ومثال

ارایه پروژه

استفاده از پایگاه مدیریت یادگیری  Schoology

 

برنامه  زمانی هفتگی کلاس:

یکشنبه 15:30 - 17:30 کلاس 311
يکشنبه 13:30 - 15:30(هفته زوج) کلاس 311

یکشنبه 08:00 - 10:00 کلاس 316
يکشنبه 10:00 - 12:00(هفته فرد) کلاس 316

برنامه هفتگی:

هفته موضوع جلسه تعداد ساعات تدریس

1

1

2

2

3

3

3

3

3

3

4

4

4

4

5

5

5

5

5

5

مقدمه و شناختی از انواع ساختمان داده ها

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

کاربرد آرایه یک بعدی

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

تعریف و پیاده سازی ساختمان داده پشته

اولویت عملگرها

پیاده سازی تبدیل infix به   postfix  و prefix با اولویت عملگرها

پیاده سازی تبدیل infix به postfix با پشته

 پیاده سازی ارزیابی عبارت postfix

پیاده سازی تبدیل infix به prefix با پشته

 پیاده سازی ارزیابی عبارت prefix

پیاده سازی تبدیل postfix به infix با پشته

پیاده سازی تبدیل prefixبه infix با پشته

پیاده سازی تبدیل prefixبه postfix  با پشته  و بالعکس

تعریف و پیاده سازی ساختمان داده صف

درج در صف

حذف از صف

تعریف و پیاده سازی صف حلقوی

درج در صف حلقوی

حذف از صف حلقوی

2

 

 

2

2

 

4

6

6

6

6

7

7

7

7

8

8

8

8

8

8

8

9

9

9

9

9

10

10

10

10

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

پیاده سازی لیست پیوندی یک طرفه

ایجاد گره در لیست پیوندی یک طرفه

پیمایش در لیست پیوندی یک طرفه

 درج در ابتدای لیست پیوندی یک طرفه

درج در انتهای لیست پیوندی یک طرفه

درج در وسط لیست پیوندی یک طرفه

درج بعد از گره ای با آدرس معلوم

درج بعد از گره ای با شماره معلوم

حذف از ابتدای لیست پیوندی یک طرفه

حذف از انتهای لیست پیوندی یک طرفه

حذف از وسط لیست پیوندی یک طرفه

پیاده سازی لیست پیوندی حلقوی

درج در انتهای لیست پیوندی حلقوی

درج در وسط لیست پیوندی حلقوی

حذف از انتهای لیست پیوندی حلقوی

پیاده سازی لیست پیوندی دو طرفه

درج گره در لیست پیوندی دو طرفه

حذف گره از پیوندی دو طرفه

پیاده سازی چند جمله ای با لیست پیوندی

پیاده سازی ساختار صف و پشته با لیست پیوندی

تعریف ساختمان داده درخت

تعاریف اصطلاحات درخت

انواع درخت دودویی

پیاده سازی درخت دودویی با ارایه

4

2

4

2

 

 

 

 

4

 

 

2

11

11

11

12

12

12

13

13

13

13

14

14

14

14

15

15

16

پیاده سازی درخت دودویی با لیست پیوندی

پیاده سازی درج گره در درخت دودویی

پیاده سازی inorder،  preorder ، postorder

تعریف و پیاده سازی درخت جستجوی دودویی

پیاده سازی درج گره

پیاده سازی حذف گره

تعریف و پیاده سازی درخت کپه

پیاده سازی درج گره

پیاده سازی حذف از ریشه

 تعریف گراف

روش ماتریس مجاورتی

روش لیست همجواری

روش پیمایش اول سطح

روش پیمایش اول عمق

الگوریتم کراسکال

الگوریتم پریم

پیچیدگی الگوریتها و مرتب سازی

4

 

 

4

 

 

2

 

 

4

 

 

 

2

4

سیستم ارزشیابی:

هفته برگزاری

وزن المان ارزشیابی (%)

متد ارزشیابی

هفته# 4

4%

کوئیز1(تا آخر پشته)

کل هفته ها

4%

تمربن کلاسی )

هفته# 9

10%

امتحان میان ترم(تا سر لیست پیوندی دوطرفه)

هفته# 11

4%

(لیست پیوندی)2کوئیز

هفته# 16 تحویل و ارائه

18%

پروژه

هفته# 17- 19

60%

امتحان پایان ترم(تمام سرفصل ها)

ماتریس همپوشانی ارزشیابی و اهداف یادگیری:

متد ارزشیابی LO1 LO2 LO3 LO4 LO5 LO6
آزمونک 1 * *        
تمرین کلاسی * * * * * *
آزمونک 2       *    
امتحان میان ترم * * * *    
پروزه گروهی * * * * * *
امتحان پایان ترم * * * * * *

مراجع اصلی:

ساختمان داده به زبان c++

نویسنده: الیسهورویتز/ سارتجساهنی

ترجمه: امیر علیخانزاده

ناشر: خراسان(نشر/مشهد)

ساختمان داده به زبان c++

نویسنده: الیسهورویتز/ سارتجساهنی

ترجمه: حسین ابراهیم زاده قلزم

ناشر: سیمای دانش

Fundamental of data structure in c++

Author: horowitz, sahni and mehta

منابع فرعی

ساختمان داده ها (درس و کنکور)

نویسنده:مهندس حمید رضا مقسمی

ناشر: گسترش علوم پایه

قوانین در صورت تاخیر تکالیف تحویلی و شرایط اعطاء وقت اضافه:

  1. تمرین ها باید دارای منظم و خوانا بهمراه  تاریخ قید شده باشد.
  2. دانشجویان می بایست تکالیف و گزارش ها را در زمان مقرر بصورت فایل نرم softcopy  در پایگاه Schoology درس بفرستد و گزارش پرنیت شده hardcopy را مستقیما" به استاد درس تحویل دهد.هرگونه دیرکرد در تحویل تمرین و یا پروژه مشمول خسارت خواهد شد و به ازای هر روز دیرکرد 10% از نمره احتسابی شما برای آن المان ارزشیابی کسر خواهد شد.

قوانین برخورد با سرقت ادبی :

1-  درصورت مشاهده هر یک از مصادیق تقلب در آیتم های ارزشیابی، نمره شما صفر منظور گردیده و از شرکت شما در امتحان پایان ترم ممانعت خواهد شد.

2-  سرقت علمی باعث مخدوش شدن چهره علمی و نابودی حیثیت دانشگاه  می شود و خسارتی بی جبران را برای جامعه علمی کشور در پی خواهد داشت. لذا مرکز آموزش عالی فنی و مهندسی بوئین زهرا با هر گونه مصادیق سرقت علمی  ( در سایت دانشگاه اعلام شده است)  به شدت برخورد خواهد کرد. در صورت کشف چنین جرایمی نمره دانشجو در هر مرحله از تحصیل  به صفر تغییر یافته و پرونده آموزشی دانشجو معلق و جهت اتخاذ تصمیماتی شدیدتر به کمیته انضباطی دانشگاه ارجاع می گردد.