ساختمان داده و الگوريتم به زبان JavaScript

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

فصل 1. نماد O بزرگ (Big-O) 1
اصول اولیه و مبانی نماد Big-O 1
مثال‌های رایج 2
قوانین نماد Big-O 3
قانون ضریب: ثوابت را حذف کنید 4
قانون جمع: O ها را با هم جمع کنید 5
قانون ضرب: O ها را در هم ضرب کنید. 6
قانون چند جمله‌ای: O توان k 6
خلاصه 7
تمرین 7
فصل 2. نکته‌های مهم زبان جاوااسکریپت 9
حوزه‌ی دید 9
تعریف متغیر به صورت سراسری: حوزه‌ی دید سراسری 9
متغیرهای var: حوزه‌ی دید تابعی 9
متغیرهای let: حوزه‌ی دید بلاکی 12
مقایسه‌ی برابری 12
انواع متغیر 12
بررسی درستی (truthy) و نادرستی (falsey) 13
عملگر === و == 14
مقایسه‌ی اشیا 14
خلاصه 16
فصل 3. اعداد در جاوااسکریپت 17
سیستم عددی 17
شی Number 19
نقسیم صحیح و رُند کردن 19
Number.EPSILON 19
ماگزیمم 20
می‌نیمم 20
بینهایت یا infinity 21
خلاصه‌ی بزرگی و کوچکی مقادیر ثابت جاوااسکریپت 21
الگوریتم‌های عددی 21
آزمایش اول بودن 21
به دست آوردن فاکتورهای اول یک عدد 23
تولید اعداد تصادفی 23
تمرین 24
خلاصه 27
فصل 4. رشته‌ها در جاوااسکریپت 29
کلاس پایه‌ای String در جاوااسکریپت 29
مقایسه‌ی رشته 29
جستجو در رشته 30
خُرد کردن رشته 31
جایگزین کردن رشته 31
عبارت‌های با قاعده 32
مبانی عبارت با قاعده 32
چند عبارت با قاعده‌ی رایج و مفید 33
Query String 34
انکُد کردن رشته‌ها 35
انکُدینگ Base64 35
کوتاه کردن رشته 35
رمزنگاری 37
الگوریتم رمزنگاری RSA 39
خلاصه 43
فصل 5. آرایه‌ها 45
معرفی 45
درج 45
حذف 45
دستیابی 46
تکرار یا Iteration 46
دستور for ( ; ; ) 46
دستور while 47
دستور for ( in ) 47
دستور for ( of ) 48
متد forEach() 48
توابع کمکی 49
.slice(beginIndex, endIndex) 49
تابع splice(startIndex, removeCount, element1, element2, …) 49
concat() 51
خصوصیت length 51
عملگر Spread 52
تعریف تابعی با تعداد پارامتر متغیر 52
پاس دادن تعداد آرگومان متغیر به تابع 52
تمرین 53
متدهای تابعی کار با آرایه 59
map() 59
filter() 59
reduce() 59
آرایه‌های چند بُعدی 60
تمرین 62
خلاصه 71
فصل 6. اشیاء 73
خصوصیت‌های اشیاء 73
وراثت پروتوتایپی 73
سازنده و متغیرها 74
خلاصه 75
تمرین 75
فصل 7. مدیریت حافظه در جاوااسکریپت 77
نشتی حافظه 77
ارجاع به اشیا 77
نشتی DOM 78
شی سراسری window 79
محدود کردن ارجاع به اشیا 79
عملگر delete 80
خلاصه 80
تمرین 80
فصل 8. الگوریتم‌های بازگشتی 85
معرفی بازگشت 85
قوانین بازگشت 85
حالت پایه 86
روش تقسیم و غلبه 86
مثال کلاسیک: سری فیبوناجی 86
حل مساله به روش تکرار 87
حل مساله به روش بازگشتی 87
حل مساله به روش tail recursion 88
مثلث پاسکال 89
محاسبه‌ی پیچیدگی زمانی Big-O برای توابع بازگشتی 90
روابط تکرار دوباره (Recurrence relations) 90
تئوری مستر 91
حافظه‌ی پشته‌ی فراخوانی بازگشتی 92
خلاصه 93
تمرین 94
فصل 9. مجموعه‌ها 99
معرفی مجموعه‌ها 99
عملیات کار با مجموعه 99
درج (Insertion) 100
حذف (Deletion) 100
شامل بودن (Contains) 100
دیگر توابع مفید کار با مجموعه 100
اشتراک 101
چک کردن مجموعه‌ی پدر بودن 101
اجتماع 101
افتراق 102
خلاصه 102
تمرین 103
فصل 10. جستجو و مرتب‌سازی 105
جستجو 105
جستجوی خطی 105
جستجوی دودویی 106
مرتب‌سازی 108
مرتب‌سازی حبابی 108
مرتب‌سازی انتخابی 110
مرتب‌سازی درجی 111
مرتب‌سازی سریع 113
انتخاب سریع 115
مرتب‌سازی ادغامی 116
مرتب‌سازی شمارشی 118
تابع درون ساخت مرتب‌سازی آرایه‌ها در جاوااسکریپت 119
خلاصه 120
تمرین 121
فصل 11. جدول هَش 127
معرفی جدول هَش 127
تکنیک‌های هَش کردن 128
استفاده از اعداد اول 128
کاوش 130
کاوش خطی 130
کاوش درجه دو 130
هَش کردن دوباره/دو بار هَش کردن 131
پیاده‌سازی جدول هَش 131
استفاده از تکنیک کاوش خطی 132
استفاده از تکنیک کاوش درجه دو 133
استفاده از تکنیک دو بار هَش کردن و کاوش خطی 134
خلاصه 135
فصل 12. پشته و صف 137
پشته 137
عمل Peek یا نگاه کردن 138
درج 138
حذف 139
دستیابی 139
جستجو 140
صف 140
عمل Peek یا نگاه کردن 142
درج 142
دستیابی 143
جستجو 143
خلاصه 144
تمرین 144
فصل 13. لیست پیوندی 149
لیست پیوندی یک طرفه 149
درج 150
حذف 150
حذف سر لیست 152
جستجو 152
لیست پیوندی دو طرفه 153
درج در سر لیست 154
درج در ته لیست 154
حذف گره سر لیست 155
حذف گره ته لیست 155
جستجو 156
خلاصه 157
تمرین 158
فصل 14. حافظه‌ی کَش 161
درک مفهوم کَش 161
ساختار کلی کَش 162
تکنیک کمترین دفعات استفاده یا LFU 162
پیاده‌سازی کَش LFU 163
پیاده‌سازی متد set() و get() 164
تکنیک کمترین دسترسی اخیر یا LRU 167
خلاصه 170
فصل 15. درخت 171
ساختار کلی درخت 171
درخت دودویی 172
پیمایش درخت 172
پیمایش Pre-Order 172
پیمایش In_order 174
پیمایش Post-Order 176
پیمایش Level-Order 177
خلاصه‌ی روش‌های پیمایش درخت 178
درخت جستجوی دودویی 179
درج 179
حذف 181
جستجو 182
درخت AVL 183
دوران تکی 184
دوران به چپ 184
دوران مضاعف 186
دوران به راست، سپس به چپ 186
دوران به چپ، سپس به راست 187
متوازن کردن درخت 188
درج 189
حذف 190
سر هم کردن همه‌ی اجزا 191
خلاصه 192
تمرین 193
فصل 16. هیپ 201
هیپ چیست؟ 201
Max-Heap 202
Min-Heap 202
ساختار اندیس آرایه‌ی هیپ 203
نفوذ: بالا و پایین رفتن حبابی 204
پیاده‌سازی عملیات percolation 206
مثالی از Max-Heap 207
درج و حذف 209
پیاده‌سازی Max-Heap 210
الگوریتم مرتب‌سازی هیپ (heap sort) 212
مرتب‌سازی صعودی با min-heap 212
مرتب‌سازی نزولی با max-heap 214
خلاصه 216
تمرین 216
فصل 17. گراف 221
مبانی گراف 221
گراف غیرجهت‌دار 224
افزودن یال و گره 225
حذف گره‌ها و یال‌ها 226
گراف جهت‌دار 228
پیمایش گراف 231
جستجوی اول سطح (Breadth-First Search) 231
جستجوی اول عمق (Depth-First Search) 235
گراف وزن‌دار و کوتاهترین مسیر 239
گراف وزن‌دار 239
الگوریتم دیجکسترا: پیدا کردن کوتاهترین مسیر 240
مرتب‌سازی توپولوژیکی 244
خلاصه 246
فصل 18. مباحث پیشرفته‌ی کار با رشته‌ها 249
درخت پیشوند (Prefix Tree یا Trie) 249
الگوریتم جستجوی رشته‌ی بویر-مور 252
الگوریتم جستجوی رشته‌ی ناث-موریس-پرت 256
جستجوی رابین-کارپ 259
اثر انگشت رابین 260
برنامه‌های دنیای واقعی 263
خلاصه 263
فصل 19. برنامه‌نویسی پویا 265
انگیزه‌ی برنامه‌نویسی پویا 265
قوانین برنامه‌نویسی پویا 267
همپوشانی زیر مساله‌ها 267
زیر ساختار بهینه یا مطلوب 267
مثال: راه‌های پوشش دادن مراحل 267
مثال‌های کلاسیکی از برنامه‌نویسی پویا 269
مساله‌ی کوله پشتی 269
زیر ساختار بهینه 269
راه حل ناپخته 269
رهیافت DP 270
بزرگترین زیر دنباله‌ی مشترک 271
روش ناپخته 271
رهیافت DP 273
تغییر سکه 273
زیر ساختار بهینه 274
رهیافت ناپخته 274
همپوشانی زیر مساله‌ها 274
رهیافت DP 275
فاصله‌ی ویرایش (لونشتاین) 276
زیر ساختار بهینه 276
رهیافت ناپخته 277
رهیافت DP 278
خلاصه 279
فصل 20. عملیات بیتی 281
عملگرهای بیتی 281
عملگر AND یا & 281
عملگر OR یا | 282
یای انحصاری، عملگر XOR یا ^ 282
عملگر NOT یا ~ 283
عملگر Shift به چپ یا << 283
عملگر Shift به راست یا >> 284
عملگر Shift به راست با وارد کردن بیت 0 یا >>> 285
پیاده‌سازی عملگرهای محاسباتی به صورت بیتی 285
جمع 285
تفریق 286
ضرب 287
تقسیم 288
خلاصه 290

تصحیحات

مخاطبین

نیازمندی ها