وکتور و نگاشت
آرایه اندازه‌ی ثابت دارد. وکتور فهرستی است که بزرگ و کوچک می‌شود و نگاشت هر کلید را به مقداری وصل می‌کند. بیشتر داده‌های یک برنامه در یکی از این دو جا می‌گیرد، و کتابخانه‌ی مجموعه ها هم مجموعه، پشته و صف را برای کارهایی که به آن‌ها بیشتر می‌خورد آماده کرده است.
وکتور
وکتور را با وکتور {} برگردان وکتور<گونه> بسازید. بیفزا عضوی به ته فهرست اضافه می‌کند، بگیر و بنشان عضوی را با شماره‌اش می‌خوانند یا عوض می‌کنند، دربیاور آخرین عضو را برمی‌دارد و برمی‌گرداند و طول تعداد را می‌دهد. هر عضوها را به ترتیب می‌پیماید.
تابع ریشه:
ناپایا عددها := وکتور {} برگردان وکتور<صحیح>
دیرکن عددها.آزادکن()
عددها.بیفزا(۱۰)
عددها.بیفزا(۲۰)
عددها.بیفزا(۳۰)
عددها.بنشان(۱، ۲۵)
سرچاپ عددها.طول()، عددها.بگیر(۱)
آخری := عددها.دربیاور()
سرچاپ آخری، عددها.طول()
هر ع در عددها:
سرچاپ ع
پایان
پایانوکتور و نگاشت حافظه می‌گیرند. درست در خط بعد از ساختنشان دیرکن نام.آزادکن() بنویسید تا حافظه در پایان تابع آزاد شود، از هر راهی که تابع تمام شود.
درج و حذف
کار با وکتور فقط به ته فهرست محدود نیست. درج(ش، م) مقدار را در جای ش می‌گذارد و بقیه را یک خانه جلو می‌برد، و حذف در(ش) عضوی را بیرون می‌کشد و برمی‌گرداند. اول() و آخر() دو سر فهرست را می‌خوانند، پاک‌سازی() وکتور را خالی می‌کند و خالی است() می‌گوید چیزی مانده یا نه. کروشه هم مثل آرایه کار می‌کند: ف[ش] می‌خواند و ف[ش] = م می‌نویسد.
تابع ریشه:
ناپایا فهرست پخش := وکتور {} برگردان وکتور<رشته>
دیرکن فهرست پخش.آزادکن()
فهرست پخش.بیفزا("مرغ سحر")
فهرست پخش.بیفزا("سلطان قلب‌ها")
فهرست پخش.بیفزا("گل گلدون")
فهرست پخش.درج(۰، "پیش‌درآمد")
سرچاپ فهرست پخش
برداشته := فهرست پخش.حذف در(۲)
سرچاپ "برداشته شد:"، برداشته
سرچاپ "اولی:"، فهرست پخش.اول()، "آخری:"، فهرست پخش.آخر()
فهرست پخش[۱] += " (اجرای زنده)"
سرچاپ فهرست پخش[۱]، فهرست پخش.طول()
فهرست پخش.پاک‌سازی()
سرچاپ فهرست پخش.خالی است()
پایانشمارهها از ۰ شروع می‌شوند و به طول() - ۱ ختم می‌شوند. خواندن بیرون از این بازه بی‌صدا رد نمی‌شود و برنامه با پیام Vector.Get: index out of bounds می‌ایستد. درج یا حذف در ابتدای فهرست همه‌ی عضوهای بعدی را جابه‌جا می‌کند؛ پس در وکتورهای خیلی بلند، تا جای ممکن با ته فهرست کار کنید.
درج روی وکتور یعنی گذاشتن در یک جای مشخص، و روی نگاشت یعنی گذاشتن یک جفت کلید و مقدار. نام یکی است، ولی معنایش به گونه‌ی متغیر بستگی دارد.
وکتوری از ساختارها
عضوهای وکتور از هر گونه‌ای می‌توانند باشند و بیشتر برنامه‌های واقعی فهرستی از رکوردها نگه می‌دارند: کارها، سفارش‌ها، بازیکن‌ها. هر ش، ک در کارها شماره و خود عضو را با هم می‌دهد.
ساختار کار:
همگانی عنوان: رشته = ""
همگانی دقیقه: صحیح = ۰
همگانی انجام‌شده: منطقی = نادرست
پایان
تابع ریشه:
ناپایا کارها := وکتور {} برگردان وکتور<کار>
دیرکن کارها.آزادکن()
کارها.بیفزا(کار { عنوان = "جلسه‌ی صبح"، دقیقه = ۱۵ })
کارها.بیفزا(کار { عنوان = "نوشتن گزارش"، دقیقه = ۹۰ })
کارها.بیفزا(کار { عنوان = "بازبینی کد"، دقیقه = ۴۰ })
اولی := کارها.ارجاع(۰)
اولی.انجام‌شده = درست
ناپایا مانده := ۰
هر ش، ک در کارها:
نشان := ک.انجام‌شده ? "x" : " "
سرچاپ ش + ۱، "[" + نشان + "]"، ک.عنوان
اگر وارونه ک.انجام‌شده:
مانده += ک.دقیقه
پایان
پایان
سرچاپ "دقیقه‌های مانده:"، مانده
پایانمتغیر حلقه، یعنی ک، رونوشتی از عضو است. اگر درون حلقه ک.انجام‌شده را عوض کنید، فقط رونوشت عوض می‌شود و وکتور دست نمی‌خورد. برای تغییر خود عضو، با ارجاع(ش) اشاره‌گری به آن بگیرید و از راه همان بنویسید؛ مثال بالا با کار اول همین کار را می‌کند. راه دیگر این است که عضو را بخوانید، تغییرش دهید و با بنشان(ش، م) سر جایش برگردانید.
خود ساختارها موضوع درس بعد است.
مرتب‌سازی
کتابخانه‌ی مرتب سازی وکتور را درجا مرتب می‌کند. مرتب سازی.مرتب عددها و رشته‌ها را صعودی می‌چیند و مرتب سازی.مرتب نزولی نزولی. برای ساختارها یا هر ترتیب دلخواه دیگر، مرتب سازی.مرتب سازی با تابعی می‌گیرد که فقط به یک پرسش پاسخ می‌دهد: آیا الف باید پیش از ب بیاید؟
واردسازی مرتب سازی
ساختار بازیکن:
همگانی نام: رشته = ""
همگانی امتیاز: صحیح = ۰
پایان
تابع ریشه:
ناپایا زمان‌ها := وکتور {} برگردان وکتور<صحیح>
دیرکن زمان‌ها.آزادکن()
زمان‌ها.بیفزا(۴۲)
زمان‌ها.بیفزا(۷)
زمان‌ها.بیفزا(۱۹)
مرتب سازی.مرتب(زمان‌ها)
سرچاپ زمان‌ها
مرتب سازی.مرتب نزولی(زمان‌ها)
سرچاپ زمان‌ها
ناپایا جدول := وکتور {} برگردان وکتور<بازیکن>
دیرکن جدول.آزادکن()
جدول.بیفزا(بازیکن { نام = "سارا"، امتیاز = ۳۱ })
جدول.بیفزا(بازیکن { نام = "امید"، امتیاز = ۴۸ })
جدول.بیفزا(بازیکن { نام = "لیلا"، امتیاز = ۲۷ })
مرتب سازی.مرتب سازی با(جدول، (الف: بازیکن، ب: بازیکن): برگشت الف.امتیاز > ب.امتیاز پایان)
هر ش، ب در جدول:
سرچاپ ش + ۱، ب.نام، ب.امتیاز
پایان
پایانمقایسه در این‌جا الف.امتیاز > ب.امتیاز است، پس امتیاز بالاتر جلوتر می‌آید. مرتب سازی با قول نمی‌دهد عضوهای برابر ترتیب قبلی‌شان را نگه دارند. اگر این مهم است، مثلاً فهرستی که بر پایه‌ی نام مرتب شده و حالا بر پایه‌ی امتیاز مرتب می‌شود، از مرتب سازی ترتیب‌نگه‌دار با استفاده کنید که همان ورودی‌ها را می‌گیرد. این کتابخانه مرتب شده (رونوشتی مرتب)، جستجوی دودویی، کمینه و بیشینه هم دارد؛ راهنمای مرتب سازی را ببینید.
رشته‌ها بر پایه‌ی کد یونیکد حرف‌ها مرتب می‌شوند. برای بیشتر واژه‌های فارسی این همان ترتیب الفبایی است، ولی کد حرف‌های پ، چ، ژ، ک و گ از کد «و» و «ه» بزرگ‌تر است؛ برای همین «پسته» به‌جای این‌که درست بعد از «بادام» بیاید، بعد از «هلو» و «وزن» می‌آید.
نگاشت
نگاشت کلیدها را به مقدارها وصل می‌کند: درج جفتی را می‌گذارد (و اگر کلید از پیش باشد، مقدارش را عوض می‌کند)، بگیر مقدار یک کلید را می‌دهد، دارد بودن کلید را می‌سنجد، حذف آن را برمی‌دارد و اندازه تعداد جفت‌ها را می‌دهد. با هر کلید، مقدار در نگاشت همه را می‌پیمایید.
تابع ریشه:
ناپایا پایتخت := نگاشت {} برگردان نگاشت<رشته، رشته>
دیرکن پایتخت.آزادکن()
پایتخت.درج("ایران"، "تهران")
پایتخت.درج("ژاپن"، "توکیو")
سرچاپ پایتخت.بگیر("ایران")
سرچاپ پایتخت.دارد("فرانسه")، پایتخت.اندازه()
پایتخت.حذف("ژاپن")
هر کشور، شهر در پایتخت:
سرچاپ کشور, "->", شهر
پایان
پایانبگیر برای کلیدی که نیست خطا نمی‌دهد و مقدار صفرِ گونه را برمی‌گرداند، مثلاً ۰ یا رشته‌ی خالی. اگر ۰ می‌تواند مقدار واقعی هم باشد، اول با دارد بسنجید، یا با دریافت با پیش فرض(کلید، جایگزین) تعیین کنید برای کلید ناموجود چه برگردد.
شمارش با نگاشت
شمردن این‌که هر چیز چند بار آمده، همان کاری است که نگاشت برایش ساخته شده. این‌جا هر واژه‌ی جمله یک کلید است و تعداد تکرارش مقدار آن. دریافت با پیش فرض(واژه، ۰) + ۱ هم بار اولی را که واژه دیده می‌شود پوشش می‌دهد و هم دفعه‌های بعد را.
واردسازی مرتب سازی
واردسازی رشته
تابع ریشه:
متن := "سیب انار به سیب انار سیب توت به سیب"
واژه‌ها := رشته.تفکیک کردن(متن، " ")
دیرکن واژه‌ها.آزادکن()
ناپایا شمار := نگاشت {} برگردان نگاشت<رشته، صحیح>
دیرکن شمار.آزادکن()
هر واژه در واژه‌ها:
شمار.درج(واژه، شمار.دریافت با پیش فرض(واژه، ۰) + ۱)
پایان
سرچاپ واژه‌ها.طول()، "واژه و"، شمار.اندازه()، "واژه‌ی متفاوت"
ناپایا کلیدها := وکتور {} برگردان وکتور<رشته>
دیرکن کلیدها.آزادکن()
هر واژه، _ در شمار:
کلیدها.بیفزا(واژه)
پایان
مرتب سازی.مرتب(کلیدها)
هر واژه در کلیدها:
سرچاپ واژه، شمار.بگیر(واژه)
پایان
پایاننگاشت ترتیب افزوده شدن کلیدها را به یاد نمی‌آورد و هنگام پیمایش، آن‌ها را به ترتیبی می‌دهد که ربطی به داده‌ی شما ندارد. اگر خروجی باید ترتیب مشخصی داشته باشد، کلیدها را در یک وکتور بریزید، مرتبش کنید و مثل همین مثال، مقدار هر کلید را جداگانه بخوانید.
مجموعه، پشته و صف
کتابخانه‌ی مجموعه ها (واردسازی مجموعه ها) چند ظرف دیگر هم دارد که هر کدام برای کار مشخص‌تری است:
| گونه | کاربرد | روش‌های اصلی |
|---|---|---|
مجموعه<ت> | به خاطر سپردن مقدارهای دیده‌شده، بدون تکرار | افزودن، دارد، حذف، اندازه، خالی است |
پشته<ت> | آخرین ورودی، اولین خروجی: تاریخچه‌ی واگرد، پرانتزهای تودرتو | افزودن، برداشتن، مشاهده، اندازه، خالی است |
صف<ت> | اولین ورودی، اولین خروجی: کارها و درخواست‌ها به ترتیب رسیدن | وارد کردن، خارج کردن، مشاهده، اندازه، خالی است |
صف دوسر<ت> | افزودن و برداشتن از هر دو سر | افزودن به ابتدا، افزودن به انتها، برداشتن از ابتدا، برداشتن از انتها |
صف اولویت دار<ت> | همیشه برداشتن کوچک‌ترین عضو | افزودن، برداشتن، مشاهده |
پشته راه طبیعی بررسی درست بودن پرانتزهاست: هر پرانتز باز روی پشته می‌رود و هر پرانتز بسته باید با پرانتزِ بالای پشته جور باشد.
واردسازی مجموعه ها
واردسازی رشته
تابع متوازن(کد: رشته): منطقی:
ناپایا بازها := مجموعه ها.پشته {} برگردان مجموعه ها.پشته<رشته>
دیرکن بازها.آزادسازی()
نویسه‌ها := رشته.نویسه ها(کد)
دیرکن نویسه‌ها.آزادکن()
هر ن در نویسه‌ها:
اگر ن == "(" یا ن == "[":
بازها.افزودن(ن)
وگرنه ن == ")" یا ن == "]":
اگر بازها.خالی است():
برگشت نادرست
پایان
بالا := بازها.برداشتن()
اگر (ن == ")" و بالا != "(") یا (ن == "]" و بالا != "["):
برگشت نادرست
پایان
پایان
پایان
برگشت بازها.خالی است()
پایان
تابع ریشه:
سرچاپ متوازن("جمع(الف[۱]، ب[۲])")
سرچاپ متوازن("ت(ع]")
سرچاپ متوازن("((ع)")
پایانصف به ترتیب رسیدن رسیدگی می‌کند. در این مثال یک مجموعه کنار صف نشسته تا مشتری‌ای که از پیش منتظر است دوباره به صف اضافه نشود:
واردسازی مجموعه ها
تابع ریشه:
ناپایا صف انتظار := مجموعه ها.صف {} برگردان مجموعه ها.صف<رشته>
دیرکن صف انتظار.آزادسازی()
ناپایا منتظرها := مجموعه ها.مجموعه {} برگردان مجموعه ها.مجموعه<رشته>
دیرکن منتظرها.آزادسازی()
هر مشتری در ["سارا"، "امید"، "سارا"، "لیلا"، "امید"]:
اگر منتظرها.دارد(مشتری):
سرچاپ مشتری، "از پیش در صف است"
گذر
پایان
منتظرها.افزودن(مشتری)
صف انتظار.وارد کردن(مشتری)
پایان
سرچاپ صف انتظار.اندازه()، "نفر در صف، نفر بعدی:"، صف انتظار.مشاهده()
تا وارونه صف انتظار.خالی است():
مشتری := صف انتظار.خارج کردن()
منتظرها.حذف(مشتری)
سرچاپ "رسیدگی به"، مشتری
پایان
سرچاپ منتظرها.خالی است()
پایاناین ظرف‌ها هم مثل وکتور حافظه می‌گیرند و باید با آزادسازی() آزاد شوند. فهرست کامل روش‌هایشان در راهنمای مجموعه ها آمده است.
اشتراک و رونوشت
نسبت دادن یک وکتور به متغیری دیگر عضوهایش را رونویسی نمی‌کند. همان := قیمت‌ها نام دومی برای همان حافظه می‌سازد، پس تغییری که از راه یک نام بدهید از راه نام دیگر هم دیده می‌شود. اگر نسخه‌ای مستقل لازم دارید، مثلاً عکسی از وضعیت فعلی برای مقایسه‌ی بعدی، رونوشت() را صدا بزنید. رونوشت حافظه‌ی خودش را دارد و آزادکن() جداگانه می‌خواهد.
تابع افزودن هزینه(قیمت‌ها &: وکتور<صحیح>، هزینه: صحیح):
قیمت‌ها.بیفزا(هزینه)
پایان
تابع ریشه:
ناپایا قیمت‌ها := وکتور {} برگردان وکتور<صحیح>
دیرکن قیمت‌ها.آزادکن()
قیمت‌ها.بیفزا(۱۰۰)
قیمت‌ها.بیفزا(۲۵۰)
همان := قیمت‌ها
نسخه := قیمت‌ها.رونوشت()
دیرکن نسخه.آزادکن()
قیمت‌ها.بنشان(۰، ۹۰)
سرچاپ همان.بگیر(۰)، نسخه.بگیر(۰)
افزودن هزینه(قیمت‌ها، ۵)
سرچاپ قیمت‌ها
سرچاپ نسخه
پایاندربارهی ورودی تابع‌ها هم همین‌طور است. تابعی که وکتور را فقط می‌خواند می‌تواند آن را با مقدار بگیرد، ولی تابعی که به وکتورِ صدازننده چیزی اضافه می‌کند باید آن را با &: بگیرد، مثل افزودن هزینه. عضوهایی که روی ورودیِ با مقدار افزوده شوند هرگز به صدازننده نمی‌رسند. نگاشت هم همین رفتار را دارد و رونوشت() هم دارد.
هر حافظه را دقیقاً یک بار آزاد کنید. در مثال بالا همان و قیمت‌ها یک حافظه‌اند، پس فقط قیمت‌ها آزاد می‌شود؛ نسخه حافظه‌ی جداست و جدا آزاد می‌شود.
چند قاعده‌ی کاربردی
- وقتی اندازه ثابت است آرایه، وقتی بزرگ می‌شود وکتور، و وقتی با کلید دنبال چیزی می‌گردید نگاشت.
- بعد از ساختن هر وکتور، نگاشت یا ظرف دیگر، در خط بعد
دیرکن ... .آزادکن()بنویسید؛ حتی برای ظرف‌هایی که تابعی مثلرشته.تفکیک کردنبرمیگرداند. - متغیر حلقه‌ی
هررونوشت است. عضوها را باارجاع(ش)،بنشان(ش، م)یاف[ش] = معوض کنید. - به ترتیب نگاشت تکیه نکنید. هر جا ترتیب مهم است، کلیدها را مرتب کنید.
ب := الفوکتور را به اشتراک می‌گذارد والف.رونوشت()وکتور تازه‌ای می‌سازد. تابعی که به وکتور صدازننده عضو اضافه می‌کند آن را با&:می‌گیرد.