آموزش ++c, زبان c++

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

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

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

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

واروخوانه

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

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

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

پیش نیاز

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

#include "LinkedList.h"
#include "Stack.h"
#include <iostream>
using namespace std;
node *LinkedList::create_node(int value) {
	struct node *temp;
	temp = new (struct node);
	if (temp == NULL) {
		cout << "Memory not allocated " << endl;
		return 0;
	} else {
		temp->data = value;
		temp->next = NULL;
		return temp;
	}
}
void LinkedList::insert(int value) {
	struct node *temp, *s;
	temp = create_node(value);
	if (start == NULL) {
		start = temp;
		return;
	}
	s = start;
	while (s->next != NULL) {
		s = s->next;
	}
	temp->next = NULL;
	s->next = temp;
}
void LinkedList::deleteFirst() {
	if (start == NULL) {
		cout << "The List is Empty" << endl;
		return;
	}
	node *temp = start;
	start = start->next;
	delete temp;
}
void LinkedList::display() {
	struct node *temp;
	if (start == NULL) {
		cout << "The List is Empty" << endl;
		return;
	}
	temp = start;
	cout << "Elements of list are: " << endl;
	while (temp != NULL) {
		cout << temp->data << "->";
		temp = temp->next;
	}
	cout << "NULL" << endl;
}

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

#include "Stack.h"
#include <iostream>
using namespace std;
bool Stack::push(int x) {
	if (top >= (MAX - 1)) {
		cout << "Stack Overflow";
		return false;
	} else {
		a[++top] = x;
		return true;
	}
}
int Stack::pop() {
	if (top < 0) {
		cout << "Stack Underflow";
		return 0;
	} else {
		int x = a[top--];
		return x;
	}
}
int Stack::peek() {
	if (top < 0) {
		cout << "Stack Underflow";
		return 0;
	} else {
		return a[top];
	}
}
bool Stack::isEmpty() {
	return (top < 0);
}

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

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

bool LinkedList::isPalindrome(node* head) {
	node* next = head;
	Stack s;
	while (next != NULL) {
		s.push(next->data);
		next = next->next;
	}
	while (head != NULL) {
		int i = s.peek();
		if (head->data != i) {
			return false;
		}
		s.pop();
		head = head->next;
	}
	return true;
}

تست برنامه

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

int main() {
	LinkedList l;
	l.insert(1);
	l.insert(2);
	l.insert(3);
	l.insert(2);
	l.insert(1);
	l.display();
	bool result = l.isPalindrome(l.start);
	cout << "Check if List is Palindrome:" << endl;
	if(result){
		cout << "List is Palindrome" << endl;
	}else{
		cout << "List is not Palindrome" << endl;
	}
	return 0;
}

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

Elements of list are: 
1->2->3->2->1->NULL
Check if List is Palindrome:
List is Palindrome

پسورد: www.codegate.ir

نوشته های مشابه

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

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