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

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

  1. آشنایی با لیست پیوندی
  2. آشنایی با توابع
  3. آشنایی با if
  4. آشنایی با while
  5. آشنایی با شی گرایی
  6. آشنایی با constructor
  7. آشنایی با palindrome

واروخوانه

قلب مستوی یا جناس قلب، همچنین شناخته شده با نام واروخوانه که معادل فارسی است برای پالیندروم (Palindrome) به واژه، جمله، عدد یا هر چیز دیگری گفته می‌شود که خواندن آن از چپ به راست یا از راست به چپ کاملاً یکسان باشد. به‌عنوان مثال عدد ۱۵۳۴۳۵۱ یک عدد واروخوانه است، یا واژه «Malayalam» که نام یکی از زبانهای محلی جنوب غربی هندوستان است ویا واژه «داد» از این قاعده پیروی می‌کنند(ویکیپدیا).

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

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

پیش نیاز

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

همچنین برای بررسی واروخوانه لیست پیوندی ما از پشته (Stack) کمک گرفته‌ایم. در آموزش‌های گذشته نیز کد پشته توضیح داده شده است. سورس کد پشته در سی پلاس پلاس به صورت زیر می‌باشد:

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

برای پیاده سازی واروخوانه یک لیست پیوندی، ما از پشته کمک می‌گیریم. بدین صورت که یک بار تا انتها لیست پیوندی را پیموده و dataهای هر Node را درون پشته می‌ریزیم. حال با داشتن معکوس لیست پیوندی (منظور معکوس dataها است) دوباره از ابتدا لیست پیوندی را پیموده اما این بار data خود را با dataهای پشته مقایسه می‌کنیم در صورتی که با هم برابر باشد (طبق شرط واروخوانه) ما تا انتها لیست را بررسی می‌کنیم. در پایان اگر لیست پیوندی ما شرایط واروخوانه را داشت true برمی‌گردانیم در غیر این صورت false برگردانده می‌شود. کد این الگوریتم به صورت زیر است(متد زیر در کلاس LinkedList قرار میدهیم):

تست برنامه

برای تست کدهای بالا، کد main زیر را بزنید:

در کد بالا لیستی از اعداد 1و2و3و2و1 ایجاد کردیم. سپس به بررسی واروخوانه بودن آن پرداختیم. خروجی کد بالا به صورت زیر است:

    پسورد: www.codegate.ir

    دیدگاهتان را بنویسید

    نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *