3 判断单链表的对称性

3 判断单链表的对称性

作者: 冯向阳时间限制: 1S章节: 课程设计

问题描述 :

设带头结点的单链表的头指针为head，结点结构由data和next两个域构成，其中data域为字符型。在使用单链表ADT的基础上，设计一算法判断该链表的前n个字符是否中心对称。例如 x, xyx,  xyyx都是中心对称。

参考函数原型：

//判断单链表的前n个结点是否中心对称 

template<class ElemType>

bool Judge_Symmetry( LinkList<ElemType> &L, int num );

输入说明 :

第一行：顺序表A的数据元素的数据类型标记（0：int，1：double，2：char，3：string）

第二行：待判断对称性的链表长度n

第三行：单链表A的数据元素（数据元素之间以空格分隔）

注意：单链表A中的元素个数可能小于n，也可能大于n。如果元素个数小于n，则判断整个单链表是否对称。

输出说明 :

如第一行输入值为0、1、2、3之外的值，直接输出“err”

否则：

第一行：单链表A的遍历结果（数据元素之间以"->"分隔）

空行

第三行：true（对称）

             false（不对称）

输入范例 :

2
10
A B C D E E D C B A X Y

-----------------

A->B->C->D->E->E->D->C->B->A->X->Y

true

--------------------------------

#include<iostream>
#include<stack>
using namespace std;
int length = 0;
 
 
 
template<class T>
struct student
{
	T data;
	student<T>* next = NULL;
};
 
template<class T>
void creat(student<T>& begin, int& n)
{
	student<T>* r = &begin;
	T temp;
	while(cin>>temp)
	{
		student<T>* p;
		p = new student<T>;
		 p->data=temp;
		r->next = p;
		r = p;
		length++;
	}
}
 
template<class T>
void display(student<T>& head, int number)
{
	student<T>* p = head.next;
	while (p != NULL)
	{
		cout << p->data;
		if (p->next != NULL)
		{
			cout << "->";
		}
		p = p->next;
	}
	cout << endl;
}
 
template<class T>
void check(student<T>& head, int number)
{
	if (number == 1)
	{
		cout << "true";
		return;
	}
 
 
	stack<T> m;
	if (number % 2 == 0)
	{
		student<T>* p = head.next;
		for (int i = 0; i < number / 2; i++)
		{
			m.push(p->data);
			p = p->next;
		}
		while (!m.empty())
		{
			if (p->data == m.top())
			{
				p = p->next;
				m.pop();
			}
			else
			{
				cout << "false" << endl;
				return;
			}
		}
		cout << "true" << endl;
	}
	else if (number % 2 != 0)
	{
		student<T>* p = head.next;
		for (int i = 0; i < number / 2; i++)
		{
			m.push(p->data);
			p = p->next;
		}
		p = p->next;
		while (!m.empty())
		{
			if (p->data == m.top())
			{
				p = p->next;
				m.pop();
			}
			else
			{
				cout << "false" << endl;
				return;
			}
 
			cout << "true" << endl;
		}
	}
}
 
 
int main()
{
	int n;
	int m;
	cin >> n;	
	cin >> m;
	
	if (n == 0)
	{
		student<int> a;
		student<int> head;
		creat(head, m);
		display(head, m);
		cout << endl;
 
 
 
		if(length>=m)
		check(head, m);
		else
		{
			check(head, length);
		}
 
		
	}
	else if (n == 1)
	{
		student<double> a;
		student<double> head;
		creat(head, m);
		display(head, m);
		cout << endl;
 
 
 
		if (length >= m)
			check(head, m);
		else
		{
			check(head, length);
		}
	}
	else if (n == 2)
	{
		student<char> a;
		student<char> head;
		creat(head, m);
		display(head, m);
		cout << endl;
 
 
		if (length >= m)
			check(head, m);
		else
		{
			check(head, length);
		}
	}
	else if (n == 3)
	{
		student<string> a;
		student<string> head;
		creat(head, m);
		display(head, m);
 
		cout << endl;
 
		if (length >= m)
			check(head, m);
		else
		{
			check(head, length);
		}
	}
	else
	{
		cout << "err" << endl;
	}
	
 
 
 
 
 
}