طراحی سایت و برنامه نویسی

آموزش طراحی سایت و برنامه نویسی

طراحی سایت و برنامه نویسی

آموزش طراحی سایت و برنامه نویسی

آموزش ساخت یک اپلیکیشن آیفون (بخش یازدهم) — به زبان ساده

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

آموزش ساخت یک اپلیکیشن آیفون (بخش دهم) — به زبان ساده

ارتفاع پیش‌فرض سلول

زمانی که لی‌آوت NewsTableViewCell را ایجاد کردیم، قیدی برای حاشیه‌های فوقانی و تحتانی آن در نظر گرفتیم. بدین ترتیب سلول می‌تواند ارتفاعی را که برای نمایش محتوایش نیاز دارد (یعنی اندازه ثابت ذاتی) بداند. اگر متن یا تصویر بزرگ‌تر از این شوند، سلول می‌داند که باید ارتفاع بیشتری پیدا کند.

یک نمای جدولی به صورت پیش‌فرض و به طور خودکار ارتفاع سلول‌هایش را برابر با محتوایش تنظیم می‌کند. هر دو سلول را در صحنه News انتخاب کنید. یک روش برای انجام این کار کلیک کردن روی یک سلول و نگه‌داشتن کلید Shift و کلیک روی سلول دیگر است. Size Inspector (آیکون خط کش) را انتخاب کنید.

تنظیم خودکار اندازه

در کنار برچسب Row Height در بخش Size Inspector کادر انتخاب Custom را غیر فعال کنید.

تنظیم خودکار اندازه

بدین ترتیب فیلد Row Height به صورت Default درمی‌آید. بنابراین ارتفاع سلول‌ها در این بوم تا مقدار 44 پوینت کاسته می‌شود و دیگر نمی‌توانید محتوا را ببینید. اکنون اپلیکیشن را اجرا کنید.

تنظیم خودکار اندازه

در زمان اجرا، نمای جدولی به صورت دینامیک ارتفاع سلول‌ها را طوری تنظیم می‌کند که با محتوا مطابقت یابند. اما در زمان طراحی سلول‌ها تنها 44 پوینت ارتفاع دارند و پیش‌نمایش کاملی ایجاد نمی‌شود.

این وضعیت بغرنجی است. اگر از یک ارتفاع سفارشی استفاده کنیم، سلول‌ها در زمان طراحی ارتفاع مفیدی دارند، اما در زمان اجرا تنظیم نمی‌شوند. اگر از ارتفاع پیش‌فرض استفاده کنیم، محتوای سلول در زمان طراحی فشرده می‌شود، اما در زمان اجرا به صورت دینامیک تنظیم می‌شود. خوشبختانه می‌توانیم ارتفاع سلول‌ها را در «سازنده اینترفیس» (Interface Builder) یعنی در زمان طراحی به هر مقداری که مناسب به نظر می‌رسد تغییر دهیم و کنترلر نما را به صورت دینامیک برای ارتفاع هر سلول تنظیم کنیم تا با محتوا در زمان اجرا مطابقت پیدا کند.

ارتفاع سلول کنترلر نما

چنان که پیش‌تر گفتیم، هر نما یک کنترلر نما دارد که شامل کدی است که آن را اجرا می‌کند. کنترلر نما، چنان که از نامش برمی‌آید، به کنترل همه نماهای درون صحنه در زمان اجرا می‌پردازد و این مسئله شامل ارتفاع سلول نیز می‌شود. ما درون کنترلر برای تنظیم دینامیک ارتفاع سلول‌ها به کد نیاز داریم. خوشبختانه این کد در فریمورک BFWControl از قبل برای ما نوشته شده است.

قبل از هر چیز باید سلول‌ها را در سازنده اینترفیس به حالت ارتفاع پیش‌نمایش مفید بازگردانیم. به xcode بروید و با انتخاب دو سلول در بخش Size Inspector مقدار 220 را برای Row Height وارد کنید.

ما می‌توانیم ارتفاع ردیف را طوری وارد کنیم که پیش‌نمایش معقولی از سلول‌ها در استوری‌بورد به دست بدهد. همچنین می‌توانیم ارتفاع آن‌ها را با کشیدن دستگیره تحتانی سلول چنان که قبلاً انجام دادیم تنظیم کنیم.

تنظیم خودکار اندازه

در ادامه به کنترلر نما اعلام می‌کنیم که ارتفاع هر سلول را در زمان اجرا طوری تنظیم کند که با ارتفاع ذاتی محتوایش مطابقت داشته باشد. به این منظور کافی است نمای کنترلر نما را به صورت AdjustingTableViewController تغییر داده و خصوصیت intrinsicHeightCells را فعال کنیم.

کنترلر نمای جدولی را با کلیک کردن روی آیکون زردرنگ در نوار عنوان انتخاب کنید. در ادامه در سمت پنل سمت راست Identity Inspector را انتخاب کنید.

تنظیم خودکار اندازه

در Identity Inspector در فیلد Class عبارت Adj را وارد کرده و گزینه AdjustingTableViewController را از منوی بازشدنی انتخاب کنید. Return یا Tab را بزنید. در این مرحله Xcode به صورت خودکار عبارت Module را به مقدار BFWControls تنظیم می‌کند چون جایی است که کلاس در آن قرار دارد.

تنظیم خودکار اندازه

به پنل Attributes Inspector بروید. در این زمان با یک بخش جدید مواجه می‌شوید که عنوان آن Adjusting Table View Controller است. روی منوی بازشدنی کنار Intrinsic Height Cells کلیک کرده و آن را از Default به On تغییر دهید.

تنظیم خودکار اندازه

اپلیکیشن را اجرا کنید.

تنظیم خودکار اندازه

چنان که مشاهده می‌کنید، کنترلر نما به صورت خودکار ارتفاع هر سلول را بر مبنای محتوای آن تنظیم کرده است. این همان نتیجه‌ای است که در زمان تنظیم Row Height هر سلول به صورت Default به دست می‌آید. با این حال اکنون ما مقدار Row Height را روی 220 تنظیم کرده‌ایم و در زمان اجرا آن را به ارتفاع ذاتی هر سلول override کرده‌ایم.

تعداد خطوط در برچسب

متن درون هر سلول در حال حاضر تنها یک خط اشغال می‌کند. بدیهی است که متن تفصیلی در هر سلول به فضای بیشتری برای جای گرفتن نیاز دارد و این مسئله به وسیله (…) مورد اشاره قرار گرفته است. در این بخش برچسب‌های متنی را تغییر می‌دهیم تا در بیش از یک خط قرار گیرند.

چنان که می‌دانید، هر سلول در صحنه News وهله‌ای از کلاس NewsTableViewCell است. برچسب‌های متنی درون آن کلاس و لی‌آوت، تحت کنترل NewsTableViewCell.xib هستند. هر برچسب یک مشخصه numberOfLines دارد که در بخش Attributes Inspector به صورت Lines ظاهر می‌شود. مقدار پیش‌فرض 1 است، اما می‌توانیم آن‌ها را به 2، 3 یا هر مقداری که خطوط ما برای آن برچسب نیاز دارند تغییر دهیم. برای این که تعداد خطوط بیشینه متن نامحدود باشند می‌توانید مقدار 0 وارد کنید.

فایل NewsTableViewCell.xib را در Project Navigator انتخاب کنید. یک‌بار روی برچسب [Detail Text] (برچسب انتهایی) کلیک کنید و Attributes Inspector را انتخاب نمایید. در فیلد Lines مقدار 1 را به 0 تغییر دهید و دکمه Return را بزنید.

تنظیم خودکار اندازه

به Main.storyboard بازگردید. اینک باید ببینید که برچسب‌ها خطوط متنی بیشتری را نمایش می‌دهند. اگر چنین نیست، در منوی Editor گزینه Refresh All Views را انتخاب کنید.

تنظیم خودکار اندازه

از آنجا که سلول‌ها در سازنده اینترفیس (زمان طراحی) ارتفاع ثابتی دارند، Xcode ارتفاع نمایان نمای تصویر را کاهش داده تا فضای بیشتری برای متن باز شود.

اگر دوست دارید می‌توانید ارتفاع سلول‌ها را در سازنده اینترفیس تغییر دهید، چون ارتفاع زمان اجرا اکنون به طور مستقل و از سوی کنترلر نما تعیین می‌شود. اینک اپلیکیشن را اجرا کنید.

توجه کنید که روی شبیه‌ساز iPhone XR، تعداد خطوط مورد نیاز برای هر برچسب متن تفصیلی متفاوت است و کنترلر نما به صورت دینامیک اندازه سلول‌ها را مستقل از هم تعیین می‌کند.

استایل متن

تا به اینجا برچسب‌های متنی ما همگی از استایل فونت پیش‌فرض بهره می‌گیرند. در ادامه مقداری تمایز بین برچسب‌ها ایجاد می‌کنیم.

به Xocde بازگردید. فایل NewsTableViewCell.xib را انتخاب کنید. برچسب [Text] را انتخاب کرده و به Attributes Inspector بروید.

تنظیم خودکار اندازه

در Attributes Inspector روی آیکون T در فیلد Font کلیک کنید. در فیلد Font که باز می‌شود گزینه Headline را از بخش Text Styles انتخاب کنید.

تنظیم خودکار اندازه

تعداد Lines را روی 2 قرار دهید. بدین ترتیب عنوان می‌تواند بسته به نیاز یک یا دو خط اشغال کند.

تنظیم خودکار اندازه

برچسب [Tertiary Text] را انتخاب کرده و گزینه استایل متنی Caption 1 را انتخاب کنید.

تنظیم خودکار اندازه

همزمان با انتخاب برچسب [Tertiary Text] در بخش Attributes Inspector منوی بازشدنی Color را به Light Gray Color تغییر دهید.

تنظیم خودکار اندازه

اپلیکیشن را اجرا کنید.

تنظیم خودکار اندازه

چنان که ملاحظه می‌کنید، هر وهله از NewsTableViewCell استایل متنی جدیدی دارد. ارتفاع برچسب‌ها، نماهای پشته‌ای و سلول‌ها هر کدام محتوای با اندازه اندکی متفاوت دارند.

کامیت کردن تغییرات

همانند بخش‌های قبلی کارهای زیر را برای کامیت کردن تغییرات پروژه انجام می‌دهیم:

گزینه Commit Changes را از منوی Source Control انتخاب کنید.
توضیحی مانند زیر وارد کنید:
```
ews: auto adjusting cell heights; text styles
```
روی دکمه Commit کلیک کنید.

جمع‌بندی

اکنون سلول‌های News ما استایل‌های متنی دارند، اندازه فونتشان متفاوت است و به صورت خودکار ارتفاع سلول را تنظیم می‌کنند. در بخش بعدی این سری مقالات آموزشی از همه آنچه تاکنون آموخته‌ایم بهره می‌گیریم تا سلول‌های با تنظیم خودکار برای صحنه Products بسازیم.

منبع: فرادرس

مشاوره دوشنبه 24 تیر 1398 ساعت 20:30

0 نظر

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

در این مقاله، شیوه ایجاد یک اپلیکیشن کوچک و کارآمد را بررسی می‌کنیم که تاریخچه هزینه‌های مالی شما را نگهداری می‌کند. این اپلیکیشن مدیریت هزینه های مالی امکان گردآوری همه رسیدها را در یک پوشه «دراپ‌باکس» (Dropbox) فراهم می‌سازد و سپس می‌توانید با کلیک روی یک دکمه آن‌ها را به صورت ماهانه تنظیم کنید.

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

در این راهنما موارد زیر بررسی شده‌اند:

ایجاد یک حساب دراپ‌باکس و راه‌اندازی محیط توسعه پروژه
ایجاد UI با استفاده از جاوا اسکریپت خالص که شامل مراحل واکشی داده‌ها، رندر کردن عناصر، مدیریت مقدماتی «حالت» (State) و ناوبری ساده است.
برخی متدهای API دراپ‌باکس برای دریافت و جابجایی فایل‌ها نیز مورد استفاده قرار می‌گیرند.

راه‌اندازی دراپ‌باکس

برای ساختن اپلیکیشنی بر مبنای دراپ‌باکس، ابتدا باید یک حساب دراپ‌باکس (+) داشته باشید. پس از این که در این وب سایت ثبت نام کردید، به بخش توسعه‌دهندگان (+) بروید. در این بخش در منوی سمت چپ داشبورد گزینه My apps را انتخاب کرده و روی Create app کلیک کنید.

تنظیمات زیر را انتخاب کرده و نام یکتایی برای اپلیکیشن خود انتخاب کنید.

اپلیکیشن مدیریت مالی

در داشبورد، به بخش OAuth 2 زیر Generated access token بروید و روی دکمه Generate کلیک کنید تا یک accessToken برای API به دست آورید. این توکن دسترسی را برای استفاده آتی ذخیره کنید.

اپلیکیشن مدیریت مالی

اکنون می‌توانیم اپلیکیشن دسکتاپ دراپ‌باکس (+) را نصب کنیم. با استفاده از اطلاعات احراز هویت جدید که به دست آوردید وارد اپلیکیشن شوید تا بتوانید پوشه‌ای را که همان نام اپلیکیشن اخیراً ایجادشده را دارد مشاهده می‌کنید. ما در این مقاله از نام ExpenseOrganizer استفاده کرده‌ایم.

اپلیکیشن مدیریت مالی

برخی رسیدها و فاکتورهای خود را در این پوشه قرار دهید تا بتوانید از طریق API به آن‌ها دسترسی داشته باشید و در زمان اتمام پروژه آن‌ها را در پوشه‌های مشخصی دسته‌بندی‌شده‌ای به صورت زیر داشته باشید:

اپلیکیشن مدیریت مالی

راه‌اندازی کدبیس

اکنون باید کدبیس خود را راه‌اندازی کنیم. ما از ساده‌ترین ساختار ممکن استفاده می‌کنیم که یک فایل index.html با لینک‌های به فایل جاوا اسکریپت و یک استایل‌شیت است. همچنین باید یک نام برای اپلیکیشن خود در تگ <title> قرار دهیم.

اپلیکیشن مدیریت مالی

نکته: کد نهایی این راهنما را می‌توانید در این صفحه (+) مشاهده کنید و می‌توانید در صورت علاقه آن را کلون کنید. با این حال باید کلید API دراپ‌باکس خود را به پروژه اضافه کنید تا کار کند.

نصب و افزودن دراپ‌باکس

اکنون باید کتابخانه دراپ‌باکس را در پروژه خود نصب کنیم. به طور معمول به این منظور باید کاری مانند زیر انجام دهیم:

npm install dropox
# or
yarn add dropbox

با این حال در کد Scrimba که در بخش قبل معرفی کردیم، ما صرفاً کتابخانه دراپ‌باکس را به صورت یک وابستگی در نوار کناری چپ اضافه کرده‌ایم چون روش افزودن پکیج‌های npm در Scrimba چنین است.

گام بعدی ایمپورت کردن دراپ‌باکس و ایجاد یک وهله از کلاس Dropbox است. ما آن را dbx می‌نامیم و توکن خود را به آن ارسال می‌کنیم و کتابخانه منتخبمان را که در این مورد fetch است واکشی می‌کنیم. اگر ترجیح می‌دهید از axios با هر کتابخانه واکشی دیگر استفاده کنید، می‌توانید از آن استفاده کنید و هیچ مشکلی وجود ندارد.

1
2
3
4
5
6
import { Dropbox } from 'dropbox';
const accessToken = '<your-token-from-dashboard>';
const dbx = new Dropbox({
  accessToken,
  fetch
});

دریافت و نمایش هزینه‌ها

در این بخش مراحلی که برای دریافت و نمایش هزینه‌ها مورد نیاز است را مورد بررسی قرار می‌دهیم.

واکشی کردن داده‌ها

برای نمایش داده‌ها در اپلیکیشن باید ابتدا آن‌ها را واکشی کنیم. بدین منظور رسیدهایی که در پوشه دراپ‌باکس خود داریم را دریافت می‌کنیم.

به این منظور می‌توانیم از متد ()filesListFolder استفاده کنیم. این متد نام یک پوشه را می‌گیرد و یک Promise بازگشت می‌دهد که وقتی resolve شود، محتوای پوشه را در اختیار ما قرار می‌دهد. البته این متد یک فوت کوزه‌گری دارد، زیرا برای تعیین یک مسیر ریشه (پوشه مبنایی که در آن هستیم) باید یک رشته خالی به صورت ‘ ‘ بنویسیم و نوشتن آن به صورت ‘/’ صحیح نیست.

1
2
3
dbx.filesListFolder({
  path: ''
}).then(res => console.log(res))

زمانی که این متد را برای بازیابی فایل‌ها از حساب دراپ‌باکس فراخوانی کنیم، باید چیزی مانند تصویر زیر ببینیم:

اپلیکیشن مدیریت مالی — برای مشاهده در اندازه بزرگتر روی تصویر کلیک کنید.

بنابراین ما یک آرایه entries داریم که آرایه‌ای از شیءها است. هر شیء در آرایه entries، فایل ما (و در ادامه برخی از آن‌ها می‌توانند پوشه‌هایی باشند که داده‌هایمان را در آن‌ها سازماندهی می‌کنیم) به همراه تگ‌های tag ،name ،id و مشخصه‌های زیاد دیگر ارائه شده است. اینک تابعی می‌نویسیم که هر فایل را نمایش می‌دهد. tag مشخصه‌ای است که نوع مدخل بازیابی شده را مشخص می‌کند که یک file یا یک folder است.

زمانی که همه فایل‌ها را واکشی کردیم، آن‌ها را در اپلیکیشن خود ذخیره می‌کنیم. ما می‌توانیم شیئی به نام state برای انجام این کار بسازیم. همچنین می‌توانیم آرایه‌ای داشته باشیم که files را نگهداری کند و یک رشته نیز بسازیم که رد rootPath ما را ذخیره کند.

1
2
3
4
const state = {
  files: [],
  rootPath: ''
}

رندر کردن داده‌ها

یکی از روش‌های رندر کردن داده‌ها این است که یک لیست نامرتب <ul> به کد HTML خود اضافه کنیم، آن را با جاوا اسکریپت انتخاب کرده و با فایل‌های واکشی شده از دراپ‌باکس مقداردهی کنیم. در این مرحله یک placeholder به صورت Loading… به فایل index.html خود اضافه می‌کنیم که به محض نمایش فایل‌های واکشی شده بازنویسی خواهد شد.

1
2
3
<main>
  <ul class="dbx-list js-file-list">Loading...</ul>
</main>

اینک می‌توانیم fileListElem را بسازیم که لیست نامرتب را انتخاب می‌کند.

1
const fileListElem = document.querySelector('.js-file-list')

ما می‌توانیم همه فایل‌های مرتب‌سازی شده به صورت الفبایی را به fileListElem.innerHTML اضافه کنیم تا مطمئن شویم که پوشه‌ها را ابتدا قرار داده‌ایم. سپس هر پوشه و فایل را با استفاده از (”)join به یک <id> نگاشت (map) می‌کنیم تا از رندر کردن آرایه به جای رشته جلوگیری کنیم.

اما در این مرحله هیچ چیز روی صفحه نمایش نمی‌یابد. دلیل این مسئله آن است که باید داده‌ها را واکشی کرده و سپس فایل‌ها را با ()renderFiles رندر کنیم. در ادامه یک تابع کمکی ()init به این منظور می‌سازیم.

1
2
3
4
5
6
7
8
9
10
11
const init = async () => {
  // fetch files
  const res = await dbx.filesListFolder({
    path: state.rootPath,
    limit: 100
  })
  // update state, but first, keep the existing files, 
  // and then add newly received files 
  state.files = [...state.files, ...res.entries]
  renderFiles()
}

می‌توان حالت را استخراج و به‌روزرسانی کرده و ()renderFiles را در یک متد جداگانه درج کرد.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const init = async () => {
  const res = await dbx.filesListFolder({
    path: state.rootPath,
    limit: 100
  })
  updateFiles(res.entries)
}
const updateFiles = files => {
  state.files = [...state.files, ...files]
  renderFiles()
}
// Let's also add a reset() function. 
// It's always nice to be able to start from scratch.
const reset = () => {
  state.files = []
  init()
}

اکنون ()init را به انتهای فایل index.js اضافه می‌کنیم تا کل فرایند راه‌اندازی شده و فایل‌ها نمایش پیدا کنند. بدین ترتیب لیست فایل‌های ما نمایش می‌یابد گرچه کمی خلوت به نظر می‌رسد.

می‌توان آن را بهبود بخشید و برای این لیست آیتم‌ها یک آیکون پوشه و فایل پیش‌فرض قرار داد.

برای این که همه چیز زیباتر به نظر برسد، یک فایل به نام icon.js می‌سازیم و آیکون‌های base64 SVG را آنجا اضافه می‌کنیم. دلیل استفاده از این نوع آیکون آن است که کاربرد آن‌ها در این راهنما راحت‌تر است و دیگر نیازی به رفتن به جای دیگر و دانلود کردن آن‌ها وجود ندارد.

1
2
export const fileIcon = 'data:image/svg+xml;base64,PHN2ZyB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciIHdpZHRoPSIyNCIgaGVpZ2h0PSIyNCIgdmlld0JveD0iMCAwIDI0IDI0IiBmaWxsPSJub25lIiBzdHJva2U9IiNmZmYiIHN0cm9rZS13aWR0aD0iMiIgc3Ryb2tlLWxpbmVjYXA9InJvdW5kIiBzdHJva2UtbGluZWpvaW49InJvdW5kIiBjbGFzcz0iZmVhdGhlciBmZWF0aGVyLWZpbGUiPjxwYXRoIGQ9Ik0xMyAySDZhMiAyIDAgMCAwLTIgMnYxNmEyIDIgMCAwIDAgMiAyaDEyYTIgMiAwIDAgMCAyLTJWOXoiPjwvcGF0aD48cG9seWxpbmUgcG9pbnRzPSIxMyAyIDEzIDkgMjAgOSI+PC9wb2x5bGluZT48L3N2Zz4='
export const folderIcon = 'data:image/svg+xml;base64,PHN2ZyB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciIHdpZHRoPSIyNCIgaGVpZ2h0PSIyNCIgdmlld0JveD0iMCAwIDI0IDI0IiBmaWxsPSJub25lIiBzdHJva2U9IiNmZmYiIHN0cm9rZS13aWR0aD0iMiIgc3Ryb2tlLWxpbmVjYXA9InJvdW5kIiBzdHJva2UtbGluZWpvaW49InJvdW5kIiBjbGFzcz0iZmVhdGhlciBmZWF0aGVyLWZvbGRlciI+PHBhdGggZD0iTTIyIDE5YTIgMiAwIDAgMS0yIDJINGEyIDIgMCAwIDEtMi0yVjVhMiAyIDAgMCAxIDItMmg1bDIgM2g5YTIgMiAwIDAgMSAyIDJ6Ij48L3BhdGg+PC9zdmc+'

اینک می‌توانیم آیکون‌ها را در فایل index.js ایمپورت کنیم:

1
import { fileIcon, folderIcon } from './icons.js'

در این مرحله map. را در renderFiles خود به‌روزرسانی می‌کنیم تا آیکون‌های جدید را شامل شود.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const renderFiles = () => {
  fileListElem.innerHTML = state.files.sort((a, b) => {
    // ... this part stays the same
  }).map(file => {
    const type = file['.tag']
    let thumbnail
    if (type === 'file') {
      thumbnail = fileIcon
    } else {
      thumbnail = folderIcon
    }
    return `
    <li class="dbx-list-item ${type}">
    <img class="dbx-thumb" src="${thumbnail}">
    ${file.name}
    </li>
    `
  }).join('')
}

اکنون فایل ما زیباتر به نظر می‌رسد.

سازماندهی فایل‌ها و پوشه‌ها

قابلیت اصلی اپلیکیشن ما در این است که با یک کلیک همه فایل‌ها درون پوشه جابجا می‌شوند و بر حسب سال و سپس درون هر پوشه بر حسب ماه سازماندهی می‌شوند. قبل از هر چیز باید یک دکمه در فایل index.js بسازیم.

1
<button type="button" class="dbx-btn js-organize-btn">Organize</button>

در وهله دوم مقداری کد جاوا اسکریپت به آن اضافه می‌کنیم.

1
2
3
4
5
6
// select the button
const organizeBtn = document.querySelector('.js-organize-btn')
// add an event listener to it
organizeBtn.addEventListener('click', e => {
  console.log(e)
})

ما در انتهای این راهنما مجدداً به سراغ این دکمه می‌آییم تا تابعی که فایل‌ها را جابجا می‌کند را تکمیل کنیم. برای جابجایی فایل‌ها می‌توانیم از ()filesMoveBatchV2 استفاده کنیم. این متد فایل‌ها را به صورت دسته‌ای از یک پوشه به پوشه دیگر جابجا می‌کند. در این مورد ما می‌خواهیم فایل‌ها را از پوشه root به پوشه‌های با نام مجزا جابجا کنیم.

این متد زمانی که به صورت بخشی از تابع async استفاده شود، بهترین پیاده‌سازی خود را خواهد داشت.

1
2
3
const moveFiles = async () => {
  let response = await dbx.filesMoveBatchV2()
}

این متد entries را می‌پذیرد که آرایه‌ای از شیءها است و شامل مشخصه‌های from_path و to_path است.

1
2
3
4
5
6
7
8
// temporarily, pseudocode values for paths
const entries = [{
  from_path: 'origin_folder',
  to_path: 'destination_folder'
}]
const moveFiles = async () => {
  let response = await dbx.filesMoveBatchV2({ entries })
}

()filesMoveBatchV2 اگر فراخوانی بی‌درنگ موفق باشد و در واقع فایل‌های معدودی برای پردازش ارائه شده باشند، مقدار success بازگشت می‌دهد.

با این حال در مورد حجم جابجایی بالا، شیئی به همراه یک مشخصه به نام async_job_id بازگشت می‌دهد و معنی آن این است که فراخوانی شما اجرا شده است و باید آن را در مرحله بعدی یعنی زمانی که تکمیل شده و دیگر در حالت in_progress نیست، با فراخوانی filesMoveBatchCheckV2 بررسی کنیم.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// still, pseudocode values for paths
const entries = {
  from_path: 'origin_folder',
  to_path: 'destination_folder'
}
const moveFiles = async () => {
  let response = await dbx.filesMoveBatchV2({ entries })
  const { async_job_id } = response
  if (async_job_id) {
    do {
      response = await dbx.filesMoveBatchCheckV2({ async_job_id })
      console.log(res)
    } while (response['.tag'] === 'in_progress')
  }
}

اینک مسیرهای صحیح را برای شیء entries پیاده‌سازی می‌کنیم و آن را به ()moveFiles اضافه می‌کنیم.

برای تکمیل این قابلیت باید ()moveFiles را به دکمه Organise وصل کنیم. همچنین خوب است که متن دکمه را طوری به‌روزرسانی کنیم که نشان دهد پردازش جابجایی فایل‌ها آغاز شده و در زمان اتمام کار به حالت عادی بازگردانیم.

1
2
3
4
5
6
7
8
9
organizeBtn.addEventListener('click', async e => {
  const originalMsg = e.target.innerHTML
  e.target.disabled = true
  e.target.innerHTML = 'Working...'
  await moveFiles()
  e.target.disabled = false
  e.target.innerHTML = originalMsg
  reset()
})

اکنون وقتی روی دکمه کلیک کنیم، می‌بینیم که تغییریافته و پیام in_progress در لاگ console دیده می‌شود. این صرفاً برای ما است تا ببینیم که دراپ‌باکس فایل‌ها را جابجا می‌کند.

زمانی که کار پایان یافت، پوشه سالانه به دست می‌آید.

چنان که می‌بینید همه رسیدهای مثال ما مربوط به یک سال هستند. برای این که بتوانید به داخل پوشه آنگاه کنید باید بتوانید روی آن‌ها کلیک کنید و به این منظور باید قابلیت ناوبری را تکمیل کرده باشیم. در ادامه به پیاده‌سازی بخش ناوبری اپلیکیشن خود می‌پردازیم.

ناوبری در اپلیکیشن

ناوبری در دراپ‌باکس عملاً شبیه به ناوبری در پوشه‌های فایل اکسپلورر در ویندوز یا نرم‌افزار Finder روی سیستم‌های مک است. تنها چیزی که لازم داریم این است که پوشه‌ای که در آن قرار داریم را عوض کنیم. در ادامه ابتدا این فرایند را به صورت دستی بررسی می‌کنیم و سپس کد آن را نیز می‌نویسیم تا پردازش به صورت خودکار اجرا شود.

اگر rootPath را در state تغییر دهیم و صفحه را بارگذاری مجدد کنیم:

1
2
3
4
const state = {
  files: [],
  rootPath: '/2019'
}

همه فایل‌های آوریل 2019 را به دست می‌آوریم:

یک بار دیگر state را به صورت دستی به‌روزرسانی می‌کنیم تا به پوشه آوریل یعنی ماه شماره 4 برویم و صفحه را به‌روزرسانی می‌کنیم:

1
2
3
4
const state = {
  files: [],
  rootPath: '/2019/4'
}

بدین ترتیب همه رسیدها را مشاهده می‌کنید:

برای این که این فرایند کمی ساده‌تر شود، باید یک فیلد input اضافه کنیم، به طوری که بتوانیم نام پوشه‌ای که می‌خواهیم به آن برویم را وارد کنیم و نیاز نباشد که هر بار از hard-code استفاده کنیم. بدین ترتیب فیلد input را درون یک عنصر <form> قرار می‌دهیم که در ادامه مشاهده می‌کنید.

همچنین در ادامه صفحه خود را با طراحی یک هدر زیبا در index.html زیباتر می‌سازیم.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
<header>
  <h1>Expense Organizer</h1>
  <form class="root-path-wrap js-root-path__form">
    <h2><label for="root-path"> Folder Path</label></h2>
    <input
      type="text"
      name="root-path"
      id="root-path"
      class="js-root-path__input"
      value="/"
    />
    <button aria-label="Load path" class="dbx-btn" type="submit">
    &rarr;
    </button>
  </form>
</header>

اینک صفحه اپلیکیشن ما به صورت زیر در آمده است:

چنان که مشاهده می‌کنید، یک دکمه نیز برای تأیید مسیری که می‌خواهیم برویم تعبیه کرده‌ایم. درون فایل index.js تلاش می‌کنیم state را به همان چیزی که بود بازگردانیم.

1
2
3
4
const state = {
  files: [],
  rootPath: ''
}

همچنین کمی کد جاوا اسکریپت اضافه می‌کنیم تا rootPath را با مقادیری از فیلد input به‌روزرسانی کنیم:

1
2
3
4
5
6
7
8
9
10
const rootPathForm = document.querySelector('.js-root-path__form')
const rootPathInput = document.querySelector('.js-root-path__input')
rootPathForm.addEventListener('submit', e => {
  e.preventDefault();
  state.rootPath = rootPathInput.value === '/' 
    ? '' 
    :  rootPathInput.value.toLowerCase()
  
  reset()
})

بدین ترتیب کار ما به پایان رسیده و ناوبری اپلیکیشن عملیاتی شده است.

سخن پایانی

بدین ترتیب ما موفق شدیم با پیگیری مراحل معرفی شده در این راهنما اپلیکیشنی بسازیم که به رسیدهای مالی ما سر و سامان می‌بخشد. این موفقیت بزرگی محسوب می‌شود. اگر همچنان حس می‌کنید که موفق نشده‌اید همه مفاهیم مطرح‌شده در این راهنما را به خوبی متوجه نشده‌اید پیشنهاد می‌کنیم به صفحه کد منبع این اپلیکیشن (+) نیز سری بزنید تا توضیحات را با تفصیل بیشتری مشاهده کنید.

منبع: فرادرس

مشاوره دوشنبه 24 تیر 1398 ساعت 20:29

0 نظر

پیاده سازی درخت دودویی در جاوا — راهنمای جامع

در این مقاله به بررسی روش پیاده‌سازی درخت دودویی در جاوا می‌پردازیم. ما در این راهنما از یک درخت دودویی مرتب استفاده می‌کنیم که شامل مقادیر عدد صحیح (int) است.

درخت دودویی در جاوا

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

در زیر بازنمایی مختصری از این نوع درخت دودویی را می‌بینید:

درخت دودویی در جاوا

ما برای پیاده‌سازی این درخت از یک کلاس کمکی Node استفاده می‌کنیم که مقادیر int را ذخیره می‌کند و ارجاعی به هر فرزند نگه می‌دارد:

1
2
3
4
5
6
7
8
9
10
11
class Node {
    int value;
    Node left;
    Node right;
 
    Node(int value) {
        this.value = value;
        right = null;
        left = null;
    }
}

در ادامه گره آغازین درخت را که «ریشه» (Root) نامیده می‌شود اضافه می‌کنیم:

1
2
3
4
5
6
public class BinaryTree {
 
    Node root;
 
    // ...
}

عملیات رایج

در این بخش برخی از رایج‌ترین عملیات که می‌توان روی یک درخت دودویی اجرا کرد را بررسی می‌کنیم.

درج عنصر

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

اگر مقدار گره جدید کمتر از گره کنونی باشد، به فرزند سمت چپ می‌رویم.
اگر مقدار گره جدید بزرگ‌تر از گره جاری باشد، به فرزند سمت راست می‌رویم.
زمانی که گره کنونی null باشد، به گره رسیده‌ایم و می‌توانیم گره جدید را در این موقعیت درج کنیم.

ابتدا یک متد بازگشتی برای انجام این عملیات درج ایجاد می‌کنیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private Node addRecursive(Node current, int value) {
    if (current == null) {
        return new Node(value);
    }
 
    if (value < current.value) {
        current.left = addRecursive(current.left, value);
    } else if (value > current.value) {
        current.right = addRecursive(current.right, value);
    } else {
        // value already exists
        return current;
    }
 
    return current;
}

سپس متد عمومی را ایجاد می‌کنیم که فرایند بازگشتی را از گره ریشه آغاز می‌کند:

1
2
3
public void add(int value) {
    root = addRecursive(root, value);
}

اکنون بررسی می‌کنیم که چگونه می‌توانیم از این متد برای ایجاد درخت در مثال خود استفاده کنیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
private BinaryTree createBinaryTree() {
    BinaryTree bt = new BinaryTree();
 
    bt.add(6);
    bt.add(4);
    bt.add(8);
    bt.add(3);
    bt.add(5);
    bt.add(7);
    bt.add(9);
 
    return bt;
}

یافتن یک عنصر

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

1
2
3
4
5
6
7
8
9
10
11
private boolean containsNodeRecursive(Node current, int value) {
    if (current == null) {
        return false;
    } 
    if (value == current.value) {
        return true;
    } 
    return value < current.value
      ? containsNodeRecursive(current.left, value)
      : containsNodeRecursive(current.right, value);
}

در این متد با مقایسه مقدار مورد نظر با مقادیر گره جاری به جستجوی آن می‌پردازیم و سپس بسته به نتیجه مقایسه، ادامه کار را در فرزندان سمت چپ یا راست ادامه می‌دهیم.

سپس متد عمومی را ایجاد می‌کنیم که از گره ریشه آغاز می‌شود.

1
2
3
public boolean containsNode(int value) {
    return containsNodeRecursive(root, value);
}

اکنون می‌توانیم یک تست ساده بنویسیم که تأیید کند آیا درخت واقعاً شامل عنصر درج شده است یا نه.

1
2
3
4
5
6
7
8
9
@Test
public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements() {
    BinaryTree bt = createBinaryTree();
 
    assertTrue(bt.containsNode(6));
    assertTrue(bt.containsNode(4));
  
    assertFalse(bt.containsNode(1));
}

همه گره‌های اضافه شده باید در درخت موجود باشند.

حذف یک عنصر

عملیات رایج دیگری که روی درخت‌های دودویی استفاده می‌شود، حذف یک گره از درخت است. ابتدا باید گرهی را که می‌خواهیم حذف کنیم به روشی که قبلاً معرفی کردیم بیابیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private Node deleteRecursive(Node current, int value) {
    if (current == null) {
        return null;
    }
 
    if (value == current.value) {
        // Node to delete found
        // ... code to delete the node will go here
    } 
    if (value < current.value) {
        current.left = deleteRecursive(current.left, value);
        return current;
    }
    current.right = deleteRecursive(current.right, value);
    return current;
}

زمانی که گره مورد نظر را یافتیم، 3 حالت متفاوت وجود دارد:

این گره هیچ فرزندی ندارد: این ساده‌ترین حالت است و کافی است که گره را در والدینش با مقدار null عوض کنیم.
گره مورد نظر دقیقاً یک فرزند دارد: در این حالت در گره والد، این گره را با آن فرزند عوض می‌کنیم.
گره مورد نظر دو فرزند دارد: این پیچیده‌ترین حالت است، چون نیازمند سازماندهی مجدد درخت است.

در ادامه شیوه پیاده‌سازی حالت نخست را می‌بینید که در آن گره مورد نظر یک برگ است:

1
2
3
if (current.left == null && current.right == null) {
    return null;
}

اکنون به بررسی حالتی می‌پردازیم که گره یک فرزند دارد:

1
2
3
4
5
6
7
if (current.right == null) {
    return current.left;
}
 
if (current.left == null) {
    return current.right;
}

در کد فوق یک فرزند غیر تهی بازگشت می‌دهیم تا بتواند به گره والد انتساب یابد.

در نهایت باید حالتی را مدیریت کنیم که گره دو فرزند دارد. در این حالت ابتدا باید گرهی را که جایگزین گره حذف شده خواهد شد بیابیم. به این منظور از کوچک‌ترین گرهی که در زیردرخت سمت راست گره مورد نظر قرار دارد استفاده می‌کنیم:

1
2
3
private int findSmallestValue(Node root) {
    return root.left == null ? root.value : findSmallestValue(root.left);
}

سپس کمترین مقدار را به گرهی که باید حذف شود انتساب می‌دهیم و سپس آن را از زیردرخت راست حذف می‌کنیم.

1
2
3
4
int smallestValue = findSmallestValue(current.right);
current.value = smallestValue;
current.right = deleteRecursive(current.right, smallestValue);
return current;

در نهایت متد عمومی را ایجاد می‌کنیم که فرایند حذف را از ریشه آغاز می‌کند:

1
2
3
public void delete(int value) {
    root = deleteRecursive(root, value);
}

اکنون بررسی می‌کنیم که آیا عملیات حذف مطابق انتظار پیش می‌رود یا نه.

1
2
3
4
5
6
7
8
@Test
public void givenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements() {
    BinaryTree bt = createBinaryTree();
 
    assertTrue(bt.containsNode(9));
    bt.delete(9);
    assertFalse(bt.containsNode(9));
}

پیمایش یک درخت

در این بخش روش‌های مختلف پیمایش یک درخت را بررسی می‌کنیم و جستجوهای «عمق-اول» و «سطح-اول» را بررسی می‌کنیم. ما از همان درختی که قبلاً استفاده کردیم بهره می‌گیریم و ترتیب پیمایش را در هر حالت نمایش می‌دهیم.

جستجوی عمق-اول

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

1
2
3
4
5
6
7
public void traverseInOrder(Node node) {
    if (node != null) {
        traverseInOrder(node.left);
        System.out.print(" " + node.value);
        traverseInOrder(node.right);
    }
}

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

3 4 5 6 7 8 9

در پیمایش پیش‌ترتیبی ابتدا گره ریشه مورد بازدید قرار می‌گیرد، سپس زیردرخت چپ و در نهایت زیردرخت راست بازدید می‌شود:

1
2
3
4
5
6
7
public void traversePreOrder(Node node) {
    if (node != null) {
        System.out.print(" " + node.value);
        traversePreOrder(node.left);
        traversePreOrder(node.right);
    }
}

خروجی پیمایش پیش‌ترتیبی در کنسول به صورت زیر خواهد بود:

6 4 3 5 8 7 9

در روش پیمایش پس‌ترتیبی، ابتدا زیردرخت چپ مورد بازدید قرار می‌گیرد و سپس زیردرخت راست و در نهایت گره ریشه بازدید می‌شود:

1
2
3
4
5
6
7
public void traversePostOrder(Node node) {
    if (node != null) {
        traversePostOrder(node.left);
        traversePostOrder(node.right);
        System.out.print(" " + node.value);
    }
}

خروجی پیمایش پس‌ترتیبی گره‌ها به صورت زیر است:

3 5 4 7 9 8 6

جستجوی سطح-اول

این نوع جستجو نیز یکی دیگر از روش‌های رایج پیمایش درخت است و در آن ابتدا همه گره‌های یک سطح مورد بازدید قرار می‌گیرند و سپس به سطح بعدی مراجعه می‌شود. این نوع از پیمایش به نام پیمایش ترتیب سطح نیز نامید می‌شود و در آن همه سطوح درخت با آغاز از ریشه و از چپ به راست مورد بازدید قرار می‌گیرد.

برای پیاده‌سازی این نوع جستجو از «صف» (Queue) استفاده می‌کنیم تا گره‌ها را در هر سطح به ترتیب حفظ کنیم. به این منظور هر گره را از لیست استخراج و مقدار آن را پرینت می‌کنیم، سپس فرزندانش را به صف اضافه می‌کنیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void traverseLevelOrder() {
    if (root == null) {
        return;
    }
 
    Queue<Node> nodes = new LinkedList<>();
    nodes.add(root);
 
    while (!nodes.isEmpty()) {
 
        Node node = nodes.remove();
 
        System.out.print(" " + node.value);
 
        if (node.left != null) {
            nodes.add(node.left);
        }
 
        if (node.right!= null) {
            nodes.add(node.right);
        }
    }
}

در این حالت، ترتیب گره‌ها به صورت زیر خواهد بود:

6 4 8 3 5 7 9

سخن پایانی

در این مقاله با شیوه پیاده‌سازی درخت دودویی در جاوا و رایج‌ترین عملیات مربوط به آن آشنا شدیم. مانند همیشه همه کدهای معرفی شده در این مقاله را می‌توانید در این آدرس گیت‌هاب (+) مشاهده کنید.

منبع: فرادرس

مشاوره دوشنبه 24 تیر 1398 ساعت 20:28

0 نظر

ساختمان های داده در جاوا اسکریپت — به زبان ساده

امروزه شاهد هستیم که منطق تجاری وب‌اپلیکیشن‌ها به مرور از بک‌اند به سمت فرانت‌اند در حال جابجایی است و از این رو خبرگی در زمینه «مهندسی فرانت‌اند» از هر زمان دیگری اهمیت بیشتری یافته است. مهندسان فرانت‌اند امروزه به کتابخانه‌های view از قبیل React وابسته هستند تا بهره‌وری را بالا ببرند. کتابخانه‌های view به نوبه خود به کتابخانه‌های «حالت» (State) مانند Redux وابسته هستند تا داده‌ها را مدیریت کنند. در مجموع ری‌اکت و ریداکس در پارادایم برنامه‌نویسی واکنشی مشارکت دارند که در آن UI در واکنش به تغییرهای داده اقدام به به‌روزرسانی ری‌اکت می‌کند. در این مطلب به بررسی ساختمان های داده در جاوا اسکریپت خواهیم پرداخت.

در عصر حاضر بک‌اند به طور فزاینده‌ای صرفاً به عنوان یک سرور API عمل کرده و نقاط انتهایی لازم برای بازیابی و به‌روزرسانی داده‌ها را عرضه می‌کند. در واقع، بک‌اند صرفاً پایگاه داده را به فرانت‌اند فوروارد می‌کند و انتظار دارد که مهندسان فرانت‌اند همه منطق کنترلر را مدیریت کنند. محبوبیت رو به تزاید میکروسرویس‌ها و GraphQL گواهی بر این روند رو به رشد است.

در حال حاضر انتظار می‌رود که مهندسان فرانت‌اند علاوه برداشتن درکی زیبایی‌شناسانه از HTML و CSS، بر جاوا اسکریپت نیز مسلط باشند. از آنجا که ذخیره داده‌ها در سمت کلاینت به عنوان نسخه‌هایی تکراری از پایگاه داده روی سرور تلقی می‌شود، کسب دانش دقیق از ساختمان‌های داده رایج به امری ضروری تبدیل شده است. درواقع، سطح خبرگی یک مهندس را می‌توان از توانایی وی برای تمییز زمان و چرایی استفاده از یک ساختمان داده، استنباط کرد.

برنامه نویسان بد از کد نگران هستند، اما برنامه نویسان خوب در مورد ساختمان داده و روابط آن دغدغه دارند.

– لینوس تروالدز، خالق لینوکس و گیت

در سطوح بالا اساساً سه نوع ساختمان داده وجود دارد: «پشته» (Stack)، «صف» (Queue) و ساختارهای شبیه آرایه که تنها تفاوتشان در شیوه درج و حذف آیتم‌ها است. لیست‌های پیوندی، درخت و گراف ساختمان‌هایی با گره هستند که به گره‌های دیگر ارجاع می‌دهند. جداول هَش برای ذخیره و مکان‌یابی داده‌ها به تابع‌های هش وابسته هستند.

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

در این مقاله برای توضیح علت و روشن ساختن زمان استفاده از هر کدام از این ساختمان‌های داده از ترتیب این وابستگی‌ها تبعیت خواهیم کرد.

پشته

بدیهی است که مهم‌ترین پشته در جاوا اسکریپت «پشته فراخوانی» (call stack) است که هر زمان یک تابع را اجرا می‌کنیم آن را به دامنه تابع ارسال می‌کنیم. از نظر برنامه‌نویسی پشته فراخوانی صرفاً یک آرایه با دو عملیات اصلی یعنی push و pop است. عملیات push عناصری را به ابتدای آرایه اضافه می‌کند در حالی که عملیات pop عناصر را از همان مکان حذف می‌کند. به بیان دیگر پشته از پروتکل «ورودی اول، خروجی اول» به اختصار FIFO تبعیت می‌کند.

در ادامه مثالی از یک پشته را در کد جاوا اسکریپت می‌بینید. دقت کنید که می‌توانیم ترتیب پشته را معکوس کنیم و انتهای پشته به ابتدا بیاید و ابتدا به انتها برود. در چنین حالتی می‌توانیم از متدهای unshift و shift به ترتیب به جای عملیات push و pop استفاده کنیم.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Stack {
    constructor(...items) {
        this.reverse = false;
        this.stack = [...items];
    }
 
    push(...items) {
        return this.reverse
            ? this.stack.unshift(...items)
            : this.stack.push(...items);
    }
 
    pop() {
        return this.reverse ? this.stack.shift() : this.stack.pop();
    }
}
 
mocha.setup("bdd");
const { assert } = chai;
 
describe("Stacks", () => {
    it("Should push items to top of stack", () => {
        const stack = new Stack(4, 5);
        assert.equal(stack.push(1, 2, 3), 5);
        assert.deepEqual(stack.stack, [4, 5, 1, 2, 3]);
    });
 
    it("Should push items to bottom of stack", () => {
        const stack = new Stack(4, 5);
        stack.reverse = true;
        assert.equal(stack.push(1, 2, 3), 5);
        assert.deepEqual(stack.stack, [1, 2, 3, 4, 5]);
    });
 
    it("Should pop item from top of stack", () => {
        const stack = new Stack(1, 2, 3);
        assert.equal(stack.pop(), 3);
    });
 
    it("Should pop item from bottom of stack", () => {
        const stack = new Stack(1, 2, 3);
        stack.reverse = true;
        assert.equal(stack.pop(), 1);
    });
});
 
mocha.run();

زمانی که تعداد آیتم‌ها افزایش پیدا می‌کند، push/pop به طور فزاینده‌ای کارایی بیشتری نسبت به unshift/shift پیدا می‌کنند، زیرا در حالت دوم هر آیتم باید مجدداً اندیس‌گذاری شود، اما در حالت اول چنین الزامی وجود ندارد.

صف

جاوا اسکریپت یک زبان برنامه‌نویسی «رویداد-محور» (event-driven) است که امکان پشتیبانی از عملیات غیر مسدودساز را فراهم می‌سازد. مرورگر به صورت داخلی تنها یک نخ دارد که کل کد جاوا اسکریپت را روی آن اجرا می‌کند و از «صف رویداد» (event queue) برای صف‌بندی شنونده‌ها و از «حلقه رویداد» (event loop) برای گوش دادن به رویدادهای ثبت شده استفاده می‌کند. برای پشتیبانی از ناهمگامی در یک محیط تک نخی (برای صرفه‌جویی در منابع پردازنده و بهبود تجربه وب) تابع‌های شنونده از صف خارج می‌شوند و تنها زمانی اجرا می‌شوند که پشته فراخوانی خالی شود. Promise-ها به این معماری رویداد-محور وابسته هستند که امکان اجرای کد ناهمگام به «سبک همگام» را فراهم می‌سازد و دیگر عملیات را مسدود نمی‌کند.

از نظر برنامه‌نویسی، صف‌ها صرفاً آرایه‌ای هستند که دو عملیات عمده یعنی unshift و pop دارند. unshift آیتم‌ها را در انتهای آرایه صف‌بندی می‌کند در حالی که pop آن‌ها را از ابتدای آرایه از صف خارج می‌کند. به بیان دیگر صف‌ها از پروتکل «ورودی اول، خروجی اول» یا FIFO تبعیت می‌کنند. اگر جهت عوض شود می‌توانیم unshift و pop را به ترتیب با push و shift عوض کنیم.

مثالی از کدنویسی صف در عمل به صورت زیر است:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Queue {
    constructor(...items) {
        this.reverse = false;
        this.queue = [...items];
    }
 
    enqueue(...items) {
        return this.reverse
            ? this.queue.push(...items)
            : this.queue.unshift(...items);
    }
 
    dequeue() {
        return this.reverse ? this.queue.shift() : this.queue.pop();
    }
}
 
mocha.setup("bdd");
const { assert } = chai;
 
describe("Queues", () => {
    it("Should enqueue items to the left", () => {
        const queue = new Queue(4, 5);
        assert.equal(queue.enqueue(1, 2, 3), 5);
        assert.deepEqual(queue.queue, [1, 2, 3, 4, 5]);
    });
 
    it("Should enqueue items to the right", () => {
        const queue = new Queue(4, 5);
        queue.reverse = true;
        assert.equal(queue.enqueue(1, 2, 3), 5);
        assert.deepEqual(queue.queue, [4, 5, 1, 2, 3]);
    });
 
    it("Should dequeue item from the right", () => {
        const queue = new Queue(1, 2, 3);
        assert.equal(queue.dequeue(), 3);
    });
 
    it("Should dequeue item from the left", () => {
        const queue = new Queue(1, 2, 3);
        queue.reverse = true;
        assert.equal(queue.dequeue(), 1);
    });
});
 
mocha.run();

لیست‌های پیوندی

لیست‌های پیوندی نیز همانند آرایه‌ها به ذخیره‌سازی عناصر داده با ترتیب متوالی می‌پردازند. اما لیست‌های پیوندی به جای این که داده‌ها را اندیس‌گذاری کنند، از اشاره‌گر برای اشاره به عناصر دیگر بهره می‌گیرند. نخستین گره به نام head خوانده می‌شود در حالی که گره آخر tail نام دارد. در یک لیست پیوندی یک‌طرفه، هر گره تنها یک اشاره‌گر به گره بعدی دارد. در این وضعیت head جایی است که مسیر حرکت ما تا انتهای لیست از آنجا آغاز می‌شود. در لیست پیوندی دوطرفه، یک اشاره‌گر به گره قبلی نیز نگهداری می‌شود. از این رو می‌توانیم از tail نیز آغاز کنیم و در جهت معکوس به سمت head حرکت کنیم.

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

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

لیست‌های پیوندی در هر دو سمت کلاینت و سرور مفید هستند. در سمت کلاینت کتابخانه‌های مدیریت «حالت» (State) مانند ریداکس منطق میان‌افزاری خود را به روشی مانند لیست پیوندی سازمان‌دهی می‌کنند. زمانی که اکشن ارسال می‌شود این کتابخانه آن را از یک میان‌افزار به دیگری pipe می‌کند و همین طور تا آخر می‌رود تا این که پیش از رسیدن به «کاهنده‌ها» (Reducers) همه میان‌افزارها را بازدید کرده باشد. در سمت سرور فریمورک‌های وب مانند Express نیز منطق میان‌افزاری خود را به روش مشابهی سازماندهی می‌کنند. زمانی که یک درخواست دریافت می‌شود، از یک میان‌افزار به دیگری pipe می‌شود تا این که یک پاسخ صادر شود.

نمونه‌ای از لیست پیوندی دوطرفه را در مثال زیر ملاحظه می‌کنید:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
class Node {
    constructor(value, next, prev) {
        this.value = value;
        this.next = next;
        this.prev = prev;
    }
}
 
class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
    }
 
    addToHead(value) {
        const node = new Node(value, null, this.head);
        if (this.head) this.head.next = node;
        else this.tail = node;
        this.head = node;
    }
 
    addToTail(value) {
        const node = new Node(value, this.tail, null);
        if (this.tail) this.tail.prev = node;
        else this.head = node;
        this.tail = node;
    }
 
    removeHead() {
        if (!this.head) return null;
        const value = this.head.value;
        this.head = this.head.prev;
        if (this.head) this.head.next = null;
        else this.tail = null;
        return value;
    }
 
    removeTail() {
        if (!this.tail) return null;
        const value = this.tail.value;
        this.tail = this.tail.next;
        if (this.tail) this.tail.prev = null;
        else this.head = null;
        return value;
    }
 
    search(value) {
        let current = this.head;
        while (current) {
            if (current.value === value) return value;
            current = current.prev;
        }
        return null;
    }
 
    indexOf(value) {
        const indexes = [];
        let current = this.tail;
        let index = 0;
        while (current) {
            if (current.value === value) indexes.push(index);
            current = current.next;
            index++;
        }
        return indexes;
    }
}
 
mocha.setup("bdd");
const { assert } = chai;
 
describe("Linked List", () => {
    it("Should add to head", () => {
        const list = new LinkedList();
        list.addToHead(1);
        list.addToHead(2);
        list.addToHead(3);
        assert.equal(list.tail.prev, null);
        assert.equal(list.tail.value, 1);
        assert.equal(list.tail.next.value, 2);
        assert.equal(list.head.prev.value, 2);
        assert.equal(list.head.value, 3);
        assert.equal(list.head.next, null);
        assert.equal(list.head.prev.prev.value, 1);
        assert.equal(list.tail.next.next.value, 3);
    });
 
    it("Should add to tail", () => {
        const list = new LinkedList();
        list.addToTail(1);
        list.addToTail(2);
        list.addToTail(3);
        assert.equal(list.tail.prev, null);
        assert.equal(list.tail.value, 3);
        assert.equal(list.tail.next.value, 2);
        assert.equal(list.head.prev.value, 2);
        assert.equal(list.head.value, 1);
        assert.equal(list.head.next, null);
        assert.equal(list.head.prev.prev.value, 3);
        assert.equal(list.tail.next.next.value, 1);
    });
 
    it("Should remove head", () => {
        const list = new LinkedList();
        list.addToHead(1);
        list.addToHead(2);
        list.addToHead(3);
        assert.equal(list.removeHead(), 3);
        assert.equal(list.head.value, 2);
        assert.equal(list.tail.value, 1);
        assert.equal(list.tail.next.value, 2);
        assert.equal(list.head.prev.value, 1);
        assert.equal(list.head.next, null);
        assert.equal(list.removeHead(), 2);
        assert.equal(list.head.value, 1);
        assert.equal(list.tail.value, 1);
        assert.equal(list.tail.next, null);
        assert.equal(list.head.prev, null);
        assert.equal(list.head.next, null);
        assert.equal(list.removeHead(), 1);
        assert.equal(list.head, null);
        assert.equal(list.tail, null);
    });
 
    it("Should remove tail", () => {
        const list = new LinkedList();
        list.addToTail(1);
        list.addToTail(2);
        list.addToTail(3);
        assert.equal(list.removeTail(), 3);
        assert.equal(list.head.value, 1);
        assert.equal(list.tail.value, 2);
        assert.equal(list.tail.next.value, 1);
        assert.equal(list.head.prev.value, 2);
        assert.equal(list.tail.prev, null);
        assert.equal(list.removeTail(), 2);
        assert.equal(list.head.value, 1);
        assert.equal(list.tail.value, 1);
        assert.equal(list.tail.next, null);
        assert.equal(list.head.prev, null);
        assert.equal(list.tail.prev, null);
        assert.equal(list.removeTail(), 1);
        assert.equal(list.head, null);
        assert.equal(list.tail, null);
    });
 
    it("Should search for value", () => {
        const list = new LinkedList();
        list.addToHead(1);
        list.addToHead(2);
        list.addToHead(3);
        assert.equal(list.search(1), 1);
        assert.equal(list.search(2), 2);
        assert.equal(list.search(3), 3);
        assert.equal(list.search(4), null);
    });
 
    it("Should search for indexes of value", () => {
        const list = new LinkedList();
        list.addToTail(1);
        list.addToTail(2);
        list.addToTail(3);
        list.addToTail(3);
        list.addToTail(1);
        assert.deepEqual(list.indexOf(1), [0, 4]);
        assert.deepEqual(list.indexOf(2), [3]);
        assert.deepEqual(list.indexOf(3), [1, 2]);
        assert.deepEqual(list.indexOf(4), []);
    });
});
 
mocha.run();

درخت

«درخت» (Tree) شبیه به لیست پیوندی است به جز این که هر آیتم در آن به گره‌های فرزند زیادی ارجاع می‌دهد و ساختاری سلسله مراتبی دارد. به بیان دیگر هر گره نمی‌تواند بیش از یک والد داشته باشد. «مدل شیء سند» (Document Object Model) یا به اختصار DOM چنین ساختاری است که ریشه آن گره html است که به گره‌های body و head تقسیم می‌شود و سپس به همه تگ‌های آشنای خانواده html انشعاب می‌یابد. وراثت پروتوتایپی و ترکیب‌بندی با استفاده از کامپوننت‌های ری‌اکت نیز در پس زمینه، ساختارهای درخت را بازتولید می‌کنند. البته DOM مجازی ری‌اکت به عنوان یک بازنمایی درون حافظه‌ای از DOM نیز ساختاری درختی دارد.

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

پیمایش درخت به دو شیوه افقی و عمودی اجرا می‌شود. «پیمایش عمق-اول» (Depth-First Traversal) یا به اختصار DFT در جهت عمودی صوت می‌گیرد و یک الگوریتم بازگشتی مناسب‌تر از نوع تکراری است. گره‌ها می‌توانند به روش‌های پیش‌ترتیبی، میان‌ترتیبی یا پس‌ترتیبی پیمایش شوند. اگر لازم باشد ریشه‌ها را پیش از بازرسی برگ‌ها بررسی کنیم، باید روش پیش‌ترتیبی را انتخاب کنیم. اما اگر نیاز باشد که برگ‌ها قبل از ریشه بررسی شوند، باید از روش پس‌ترتیبی استفاده کنیم. روش میان‌ترتیبی نیز چنان که از نامش مشخص است امکان پیمایش گره‌ها به روش متوالی را فراهم می‌سازد. این مشخصه موجب شده است که درخت جستجوی دودویی برای مرتب‌سازی بهینه باشد.

در روش «پیمایش سطح-اول» (Breadth-First Traversal) که به اختصار BFT نامیده می‌شود، از جهت‌گیری افقی استفاده می‌شود و رویکرد تکرار مناسب‌تر از رویکرد بازگشتی است. این پیمایش نیازمند استفاده از صف برای ردگیری همه گره‌های فرزند در هر تکرار است. با این حال، حافظه مورد نیاز برای چنین صفی ممکن است سنگین باشد. اگر شکل درخت بیشتر عریض است تا عمیق، BFT گزینه بهتری نسبت به DFT محسوب می‌شود. ضمناً مسیری که BFT بین هر دو گره طی می‌کند، کوتاه‌ترین مسیر ممکن است. نمونه‌ای از کد درخت جستجوی دودویی را در ادامه ملاحظه می‌کنید:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
class Tree {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
 
    insert(value) {
        if (value <= this.value) {
            if (!this.left) this.left = new Tree(value);
            else this.left.insert(value);
        } else {
            if (!this.right) this.right = new Tree(value);
            else this.right.insert(value);
        }
    }
 
    contains(value) {
        if (value === this.value) return true;
        if (value < this.value) {
            if (!this.left) return false;
            else return this.left.contains(value);
        } else {
            if (!this.right) return false;
            else return this.right.contains(value);
        }
    }
 
    depthFirstTraverse(order, callback) {
        order === "pre" && callback(this.value);
        this.left && this.left.depthFirstTraverse(order, callback);
        order === "in" && callback(this.value);
        this.right && this.right.depthFirstTraverse(order, callback);
        order === "post" && callback(this.value);
    }
 
    breadthFirstTraverse(callback) {
        const queue = [this];
        while (queue.length) {
            const root = queue.shift();
            callback(root.value);
            root.left && queue.push(root.left);
            root.right && queue.push(root.right);
        }
    }
 
    getMinValue() {
        if (this.left) return this.left.getMinValue();
        return this.value;
    }
 
    getMaxValue() {
        if (this.right) return this.right.getMaxValue();
        return this.value;
    }
}
 
mocha.setup("bdd");
const { assert } = chai;
 
const tree = new Tree(5);
for (const value of [3, 6, 1, 7, 8, 4, 10, 2, 9]) tree.insert(value);
 
/*
  5
 3 6
1 4 7
 2   8
          10
         9  
*/
 
describe("Binary Search Tree", () => {
    it("Should implement insert", () => {
        assert.equal(tree.value, 5);
        assert.equal(tree.left.value, 3);
        assert.equal(tree.right.value, 6);
        assert.equal(tree.left.left.value, 1);
        assert.equal(tree.right.right.value, 7);
        assert.equal(tree.right.right.right.value, 8);
        assert.equal(tree.left.right.value, 4);
        assert.equal(tree.right.right.right.right.value, 10);
        assert.equal(tree.left.left.right.value, 2);
        assert.equal(tree.right.right.right.right.left.value, 9);
    });
 
    it("Should implement contains", () => {
        assert.equal(tree.contains(2), true);
        assert.equal(tree.contains(9), true);
        assert.equal(tree.contains(0), false);
        assert.equal(tree.contains(11), false);
    });
 
    it("Should implement depthFirstTraverse", () => {
        const _pre = [];
        const _in = [];
        const _post = [];
        tree.depthFirstTraverse("pre", value => _pre.push(value));
        tree.depthFirstTraverse("in", value => _in.push(value));
        tree.depthFirstTraverse("post", value => _post.push(value));
        assert.deepEqual(_pre, [5, 3, 1, 2, 4, 6, 7, 8, 10, 9]);
        assert.deepEqual(_in, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
        assert.deepEqual(_post, [2, 1, 4, 3, 9, 10, 8, 7, 6, 5]);
    });
 
    it("Should implement breadthDepthTraverse", () => {
        const result = [];
        tree.breadthFirstTraverse(value => result.push(value));
        assert.deepEqual(result, [5, 3, 6, 1, 4, 7, 2, 8, 10, 9]);
    });
 
    it("Should implement getMinValue", () => {
        assert.equal(tree.getMinValue(), 1);
    });
 
    it("Should implement getMaxValue", () => {
        assert.equal(tree.getMaxValue(), 10);
    });
});
 
mocha.run();

گراف

اگر در یک درخت امکان این باشد که هر گره بیش از یک والد داشته باشد، آن را گراف می‌نامیم. یالی که گره‌ها را در گراف به هم وصل می‌کند، می‌تواند جهت‌دار یا غیر جهت‌دار، وزن‌دار یا بی‌وزن باشد. یال‌های دو جهته و وزن‌دار، شبیه بُردار هستند.

وراثت‌های چندگانه به شکل Mixin و اشیای داده که روابط چند به چند دارند ساختمان‌های داده گراف را ایجاد می‌کنند. یک شبکه اجتماعی و خود اینترنت نیز گراف محسوب می‌شوند. پیچیده‌ترین گراف برحسب ماهیت، مغز انسان است که الگوریتم‌های شبکه عصبی تلاش می‌کنند با شبیه‌سازی آن به ماشین‌ها نوعی فراهوشمندی بدهند.

نمونه‌ای از کد گراف به صورت زیر است:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const fibonacci = element => {
	return element < 3 ? 1 : fibonacci(element - 1) + fibonacci(element - 2);
};
 
mocha.setup("bdd");
const { assert } = chai;
 
describe("Graphs", () => {
	it("todo", () => {
		assert.equal(fibonacci(6), 8);
		assert.equal(fibonacci(10), 55);
	});
});
 
mocha.run();

جداول هش

جداول هش ساختمان‌های شبه دیکشنری هستند که از جفت کلید/مقدار استفاده می‌کنند. مکان حافظه برای هر جفت بر اساس تابع هش تعیین می‌شود که یک کلید می‌پذیرد و آدرسی که جفت باید درج و بازیابی شود را بازمی‌گرداند. در صورتی که دو یا چند کلید به آدرس یکسانی تبدیل شوند، تصادم رخ می‌دهد. برای افزایش پایداری باید getter و setter، این رویدادها را پیش‌بینی کنند و اطمینان حاصل کنند که همه داده‌ها می‌توانند بازیابی شوند و هیچ داده‌ای بازنویسی نمی‌شوند. به طور معمول linked lists ساده‌ترین راه‌حل هستند. داشتن جداول بسیار بزرگ نیز در این زمینه کمک زیادی خواهد کرد.

اگر بدانیم که آدرس‌های ما توالی‌های عدد صحیح هستند، می‌توانیم صرفاً از Arrays برای ذخیره‌سازی جفت‌های کلید-مقدار استفاده کنیم. برای نگاشت‌های آدرس پیچیده‌تر می‌توانیم از Maps یا Objects استفاده کنیم. جداول هش به طور میانگین زمان ثابتی برای درج و جستجو دارند. به دلیل تصادم و تغییر اندازه، این هزینه ناچیز می‌تواند به صورت زمان خطی رشد کند. با این حال در عمل می‌توانیم تصور کنیم که تابع‌های هش به قدر کافی هوشمند هستند که تصادم و تغییر اندازه نادر و ارزان است. اگر کلیدها نماینده آدرس‌ها باشند و زمانی که به هیچ هش کردن نیاز نباشد، می‌توان از یک object literal استفاده کرد. البته همواره تعادلی بین مزیت‌ها و معایب وجود دارند. تناظر ساده بین کلید و مقدار و ارتباط ساده بین کلیدها و آدرس‌ها، روابط بین داده‌ها را قربانی می‌کند. از این رو جداول هش برای مرتب‌سازی داده‌ها اصلاً بهینه نیستند.

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

در هر دو سمت کلاینت و سرور کتابخانه‌های محبوب زیادی وجود دارند که از memorization برای بیشینه‌سازی عملکرد بهره می‌گیرند. با حفظ سوابق ورودی‌ها و خروجی‌ها در جدول هش، تابع‌ها برای ورودی‌های یکسان صرفاً یک بار اجرا می‌شوند. کتابخانه محبوب Reselect از این راهبرد کَش کردن برای بهینه‌سازی تابع‌ها در اپلیکیشن‌هایی که از ریداکس استفاده می‌کنند بهره می‌گیرد. در واقع موتور جاوا اسکریپت در پس زمینه از جداول هش به نام heap برای ذخیره‌سازی همه variables و primitives که ایجاد کردیم بهره می‌گیرد. این موارد از طریق اشاره‌گرها به پشته فراخوانی مورد دسترسی قرار می‌گیرند.

خود اینترنت برای عملکرد صحیحش بر مبنای الگوریتم‌های هش کردن بنا شده است. ساختار اینترنت به طوری است که هر رایانه‌ای می‌تواند با رایانه دیگر از طریق شبکه‌ای از دستگاه‌های به هم متصل ارتباط برقرار کند. هر زمان که یک دستگاه وارد اینترنت می‌شود خود به یک روتر تبدیل می‌شود که جریان داده‌ها می‌توانند از آن بگذرند. اما این یک شمشیر دو لبه است. معماری نامتمرکز به این معنی است که هر دستگاهی در شبکه می‌تواند بسته‌های داده را مورد شنود قرار دهد و آن‌ها را که رله می‌کند دستکاری نماید. تابع‌های هش مانند MD5 و SHA256 نقشی حیاتی در جلوگیری از چنین حمله‌های «مرد میانی» (Man-in-the-Middle) دارند. تجارت الکترونیک در بستر HTTPS تنها به این جهت امن است که این تابع‌های هش مورد استفاده قرار می‌گیرند.

فناوری بلاک‌چین که از اینترنت الهام گرفته به دنبال این است که ساختار وب را در سطح پروتکل، متن‌باز کند. بلاک‌چین با بهره‌گیری از تابع‌های هش برای ایجاد «اثرانگشت‌های تغییرناپذیر» (immutable fingerprints) برای هر بلوک داده کاری کرده است که اساساً کل پایگاه داده امکان حضور آزادانه روی وب برای همه افرادی که قصد مشارکت دارند پیدا کند. بلاک‌چین از نظر ساختاری صرفاً لیست‌های پیوندی یک‌طرفه‌ای از درخت‌های دودوییِ هش‌های رمزنگاری‌شده است.

هش کردن چنان جنبه رمزنگاری‌شده‌ای دارد که با استفاده از آن می‌توان یک پایگاه داده از تراکنش‌های مالی را طوری ایجاد و به‌روزرسانی کرد که هر کس به آن دسترسی آزاد داشته باشد. نتیجه ضمنی خارق‌العاده این وضعیت قدرت شگفت‌انگیز خلق پول بوده است. کاری که روزگاری صرفاً تحت سلطه دولت‌ها و بانک‌های مرکزی بود؛ اما امروزه هر کس می‌تواند پول خاص خود را خلق کند. این همان بینش کلیدی بود که بنیان‌گذار «اتریوم» (Ethereum) و مبدع ناشناس بیت‌کوین درک کرده‌اند.

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

در کد زیر می‌توانید نمونه‌ای از جدول هش را ملاحظه کنید:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}
 
class Table {
    constructor(size) {
        this.cells = new Array(size);
    }
 
    hash(key) {
        let total = 0;
        for (let i = 0; i < key.length; i++) total += key.charCodeAt(i);
        return total % this.cells.length;
    }
 
    insert(key, value) {
        const hash = this.hash(key);
        if (!this.cells[hash]) {
            this.cells[hash] = new Node(key, value);
        } else if (this.cells[hash].key === key) {
            this.cells[hash].value = value;
        } else {
            let node = this.cells[hash];
            while (node.next) {
                if (node.next.key === key) {
                    node.next.value = value;
                    return;
                }
                node = node.next;
            }
            node.next = new Node(key, value);
        }
    }
 
    get(key) {
        const hash = this.hash(key);
        if (!this.cells[hash]) return null;
        else {
            let node = this.cells[hash];
            while (node) {
                if (node.key === key) return node.value;
                node = node.next;
            }
            return null;
        }
    }
 
    getAll() {
        const table = [];
        for (let i = 0; i < this.cells.length; i++) {
            const cell = [];
            let node = this.cells[i];
            while (node) {
                cell.push(node.value);
                node = node.next;
            }
            table.push(cell);
        }
        return table;
    }
}
 
mocha.setup("bdd");
const { assert } = chai;
 
const table = new Table(5);
table.insert("baa", 1);
table.insert("aba", 2);
table.insert("aba", 3);
table.insert("aac", 4);
table.insert("aac", 5);
 
describe("Hash Table", () => {
    it("Should implement hash", () => {
        assert.equal(table.hash("abc"), 4);
    });
 
    it("Should implement insert", () => {
        assert.equal(table.cells[table.hash("baa")].value, 1);
        assert.equal(table.cells[table.hash("aba")].next.value, 3);
        assert.equal(table.cells[table.hash("aac")].value, 5);
    });
 
    it("Should implement get", () => {
        assert.equal(table.get("baa"), 1);
        assert.equal(table.get("aba"), 3);
        assert.equal(table.get("aac"), 5);
        assert.equal(table.get("abc"), null);
    });
 
    it("Should implement getAll", () => {
        assert.deepEqual(table.getAll(), [[], [], [1, 3], [5], []]);
    });
});
 
mocha.run();

سخن پایانی

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

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

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

منبع: فرادرس

مشاوره یکشنبه 23 تیر 1398 ساعت 12:53

0 نظر

تابع های ++C — به زبان ساده

در این مقاله هر آن چه باید در مورد تابع های ++C بدانید را آموزش می‌دهیم. از جمله این که چه نوع تابع‌هایی در زبان برنامه‌نویسی ++C وجود دارند و مثال‌هایی از شیوه استفاده از آن‌ها ارائه می‌کنیم. در برنامه‌نویسی منظور از تابع گزاره‌ای است که کدها را برای اجرای وظیفه خاصی گروه‌بندی می‌کند. برای مطالعه بخش قبلی این مجموعه مقالات آموزشی می‌توانید به لینک زیر رجوع کنید:

گزاره goto در ++C — به زبان ساده

بسته به این که تابع از قبل تعریف شده باشد یا از سوی برنامه‌نویس ایجاد شود دو نوع تابع وجود دارد:

تابع کتابخانه
تابع تعریف شده از سوی کاربر

تابع کتابخانه

تابع‌های کتابخانه تابع‌های داخلی زبان برنامه‌نویسی ++C هستند. برنامه‌نویس می‌تواند با فراخوانی مستقیم تابع از این تابع‌های کتابخانه استفاده کند و نیازی نیست که آن‌ها را خودش بنویسد.

مثال 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <cmath>
 
using namespace std;
 
int main()
{
    double number, squareRoot;
    cout << "Enter a number: ";
    cin >> number;
 
    // sqrt() is a library function to calculate square root
    squareRoot = sqrt(number);
    cout << "Square root of " << number << " = " << squareRoot;
    return 0;
}

خروجی

Enter a number: 26
Square root of 26 = 5.09902

در مثال فوق، تابع کتابخانه ()sqrt برای محاسبه ریشه مربع یک عدد استفاده می‌شود. به کد <include <cmath# در برنامه فوق توجه کنید. در این کد cmath یک فایل «هدر» (Header) است. تعریف تابع ()sqrt یعنی بدنه تابع در فایل هدر cmath قرار دارد. زمانی که فایل cmath را با استفاده از دستور <include <cmath# در برنامه خود بگنجانید، می‌توانید از همه تابع‌های تعریف شده در آن استفاده کنید.

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

++C به برنامه‌نویس امکان می‌دهد که تابع خاص خود را تعریف کند. تابع تعریف شده از سوی کاربر به گروه‌بندی کد می‌پردازد تا وظیفه خاصی را اجرا کند و این گروه کد یک نام (شناسه) دارد. زمانی که تابع از هر بخش از برنامه فراخوانی شود، کدهای تعریف شده در بدنه تابع را اجرا می‌کند.

طرز کار تابع‌های تعریف شده از سوی کاربر

تابع های ++C

به تصویر فوق توجه کنید. زمانی که یک برنامه شروع به اجرا می‌کند، سیستم تابع ()main را فراخوانی می‌کند، یعنی سیستم شروع به اجرای کد از تابع ()main می‌کند. زمانی که کنترل برنامه به ()function_name درون ()main برسد، به ()void function_name انتقال می‌یابد و همه کدهای درون آن را اجرا می‌کند. سپس کنترل برنامه مجدداً به تابع main بازمی‌گردد و چنان که در تصویر فوق مشخص است، کد پس از فراخوانی ()function_name اجرا می‌شود.

مثال 2

برنامه ++C زیر، دو عدد صحیح را با هم جمع می‌کند. یک تابع به نام ()add ایجاد می‌کنیم تا اعداد صحیح را با هم جمع کند و مجموع را در تابع ()main نمایش دهد.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;
 
// Function prototype (declaration)
int add(int, int);
 
int main()
{
    int num1, num2, sum;
    cout<<"Enters two numbers to add: ";
    cin >> num1 >> num2;
 
    // Function call
    sum = add(num1, num2);
    cout << "Sum = " << sum;
    return 0;
}
 
// Function definition
int add(int a, int b)
{
    int add;
    add = a + b;
 
    // Return statement
    return add;
}

خروجی

Enters two integers: 8
-4
Sum = 4

اعلان پروتوتایپ تابع

اگر یک تابع تعریف شده از سوی کاربر پس از تابع ()main تعریف شود، کامپایلر خطایی نمایش خواهد داد. دلیل این امر آن است که کامپایلر از وجود تابع تعریف شده از سوی کاربر، نوع آرگومان‌های ارسالی به تابع و نوع بازگشتی آن ناآگاه است.

پروتوتایپ تابع در ++C یک اعلان از تابع بدون بدنه است که اطلاعاتی را در مورد تابع تعریف شده از سوی کاربر در اختیار کامپایلر قرار می‌دهد. پروتوتایپ تابع در مثال فوق به صورت زیر است:

int add(int، int);

چنان که ملاحظه می‌کنید، در پروتوتایپ تابع هیچ بدنه‌ای ندارد. ضمناً تنها نوع بازگشتی آرگومان‌ها ذکر شده و خبری از خود آرگومان‌ها نیست. پروتوتایپ تابع را می‌توان به شکل زیر نیز اعلان کرد، اما لزومی به نوشتن آرگومان‌ها وجود ندارد:

int add(int a، int b);

نکته: در صورتی که تابع تعریف شده کاربر پیش از تابع ()main قرار داشته باشد، اعلان پروتوتایپ ضروری است.

فراخوانی تابع

برای اجرای کد بدنه تابع، تابع تعریف شده از سوی کاربر باید احضار یا فراخوانی شود. در برنامه فوق دستور زیر:

1
 add(num1, num2);

درون ()main تابع تعریف شده کاربر را فراخوانی می‌کند. بدین ترتیب تابع یک عدد صحیح بازگشت می‌دهد که در متغیر add ذخیره می‌شود.

تعریف تابع

خود تابع به صورت تعریف تابع مورد ارجاع قرار می‌گیرد. تعریف تابع در برنامه فوق به صورت زیر است:

1
2
3
4
5
6
7
// Function definition
int add(int a,int b)
{
    int add;
    add = a + b;
    return add;
}

زمانی که تابعی فراخوانی می‌شود، کنترل به گزاره اول بدنه تابع انتقال می‌یابد. سپس گزاره‌های دیگر در بدنه تابع به ترتیب اجرا می‌شوند. هنگامی که همه کدهای درون تعریف تابع اجرا شدند، کنترل برنامه به برنامه فراخوانی کننده بازگشت می‌یابد.

ارسال آرگومان به تابع

پارامتر آرگومان در برنامه‌نویسی، اشاره به داده‌هایی دارد که در زمان فراخوانی تابع به آن ارسال می‌شوند. در مثال فوق، دو متغیر num1 وnum2 در طی فراخوانی تابع به آن ارسال می‌شوند. این آرگومان‌ها به نام آرگومان‌های واقعی شناخته می‌شوند. مقدار num1 و num2 به ترتیب با متغیرهای a و b مقداردهی می‌شوند. این آرگومان‌های a و b به نام آرگومان‌های صوری شناخته می‌شوند.

این وضعیت در شکل زیر نمایش یافته است:

تابع های ++C

نکاتی در مورد ارسال آرگومان‌ها

تعداد آرگومان‌های واقعی و آرگومان‌های صوری باید یکسان باشند. تنها استثنا در زمان Overload کردن تابع است.
نوع آرگومان واقعی اول باید با نوع آرگومان صوری اول مطابقت داشته باشد. به طور مشابه، نوع آرگومان واقعی دوم باید با نوع آرگومان صوری دوم مطابقت پیدا کند و همین طور تا آخر.
می‌توان تابعی را بدون ارسال آرگومان نیز فراخوانی کرد. تعداد آرگومان‌های ارسالی به یک تابع به شیوه‌ای که برنامه‌نویس برای حل مسئله مربوطه انتخاب کرده است وابستگی دارد.
در برنامه فوق، هر دو آرگومان از نوع int هستند، اما لزومی نیست که هر دو آرگومان از نوع واحدی باشند.

گزاره بازگشت

هر تابعی می‌تواند با استفاده از گزاره Return یک مقدار منفرد به برنامه فراخوانی کننده بازگشت دهد. در برنامه فوق، مقدار add از تابع تعریف شده از سوی کاربر با استفاده از گزاره زیر به برنامه فراخوانی کننده بازگشت می‌یابد:

return add;

تصویر زیر طرز کار گزاره return را نشان می‌دهد:

تابع های ++C

در برنامه فوق، مقدار add درون تابع تعریف شده کاربر به تابع فراخوانی کننده بازگشت می‌یابد. سپس این مقدار در متغیر sum ذخیره می‌شود. توجه داشته باشید که متغیر بازگشت یافته یعنی add از نوع int و متغیر sum نیز از نوع int است. ضمناً توجه کنید که نوع بازگشتی یک تابع در اعلان تابع تعریف می‌شود:

int add(int a، int b)

عبارت int در دستور اعلان فوق به این معنی است که این تابع باید مقداری با نوع int بازگشت دهد. اگر هیچ مقداری به تابع فراخوانی کننده بازگشت نیابد، در این صورت باید از void استفاده کنید. بدین ترتیب به پایان این بخش از سری مقالات آموزش ++C می‌رسیم.

برای مطالعه قسمت بعدی این مجموعه مطلب آموزشی می‌توانید روی لینک زیر کلیک کنید:

منبع: فرادرس

مشاوره یکشنبه 23 تیر 1398 ساعت 12:52

0 نظر

332
1
...
57
58
صفحه 59
60
61
...
67

طراحی سایت و برنامه نویسی

ابر برجسب

جدیدترین یادداشت‌ها

بایگانی

جستجو

آموزش ساخت یک اپلیکیشن آیفون (بخش یازدهم) — به زبان ساده

ارتفاع پیش‌فرض سلول

ارتفاع سلول کنترلر نما

تعداد خطوط در برچسب

استایل متن

کامیت کردن تغییرات

جمع‌بندی

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

راه‌اندازی دراپ‌باکس

راه‌اندازی کدبیس

نصب و افزودن دراپ‌باکس

دریافت و نمایش هزینه‌ها

واکشی کردن داده‌ها

رندر کردن داده‌ها

سازماندهی فایل‌ها و پوشه‌ها

ناوبری در اپلیکیشن

سخن پایانی

پیاده سازی درخت دودویی در جاوا — راهنمای جامع

درخت دودویی در جاوا

عملیات رایج

درج عنصر

یافتن یک عنصر

حذف یک عنصر

پیمایش یک درخت

جستجوی عمق-اول

جستجوی سطح-اول

سخن پایانی

ساختمان های داده در جاوا اسکریپت — به زبان ساده

پشته

صف

لیست‌های پیوندی

درخت

گراف

جداول هش

سخن پایانی

تابع های ++C — به زبان ساده

تابع کتابخانه

مثال 1

خروجی

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

طرز کار تابع‌های تعریف شده از سوی کاربر

مثال 2

خروجی

اعلان پروتوتایپ تابع

فراخوانی تابع

تعریف تابع

ارسال آرگومان به تابع

نکاتی در مورد ارسال آرگومان‌ها

گزاره بازگشت