#include<iostream.h>
#include<stdio.h>
#include<conio.h>

bool CheckInteger(int &i);//檢驗輸入內容是否為整數

class Node
{
	int element;
	Node *link;
	friend class List;
};

class List
{
public:
	List(int MaxLength);//構造函數
	~List(void);//析構函數
	void DeleteAll(void);//刪除所有節(jié)點
	bool CreateAsendingSort(void);//創(chuàng)建升序鏈表
	void Insert(int x);//插入節(jié)點
	int GetLong(void);//獲取鏈表長度
	void Reverse(int i,int n);//逆序函數
	void Output(ostream &out)const;//輸出函數
private:
	Node *first;
	int n;
};

List::List(int MaxLength)//構造默認鏈表:2 4 6 8 10 12 14 16 18 20
{
	first = NULL;
	n = 0;
	int j = n = MaxLength;
	
	for(;j > 0;j--)
	{
		Node *q = new Node;
		q->element = 2 * j;
		q->link = first;
		first = q;
	}
}

List::~List(void)
{
	DeleteAll();
}

void List::DeleteAll(void)
{
	Node *p;
	while(first)
	{
		p = first->link;
		delete first;
		n--;
		first = p;
	}
}

bool List::CreateAsendingSort(void)
{
	DeleteAll();
	while(1)
	{
		int x;
		if(first != NULL)
		{
			cout<<"Now the list is: ";
			Output(cout);
			cout<<"Plaese input a new element."<<endl;
			cout<<"If uneffective element,end input."<<endl;
		}
		else
		{
			cout<<"Plaese input the element."<<endl;
			cout<<"If uneffective element,end input."<<endl;
		}
		if(CheckInteger(x) == false)
			if(first == NULL)
				return false;
			else
				break;
		Insert(x);
		cout<<endl;
	}
	return true;
}

void List::Insert(int x)
{
	n++;
	if(first == NULL || first->element > x)
	{
		Node *temp = new Node;
		temp->element = x;
		temp->link = first;
		first = temp;
		return;
	}
	else if(first->element == x)
	{
		n--;
		cout<<"There is same element!"<<endl;
		cout<<"Please input this element again."<<endl;
		return;
	}

	Node *f = first;
	while(f->element <= x)
	{
		Node *p = f->link;
		if(p == NULL || p->element > x)
		{
			Node *temp = new Node;
			temp->element = x;
			temp->link = p;
			f->link = temp;
			return;
		}
		else if(p->element == x)
		{
			n--;
			cout<<"Same element exist!"<<endl;
			cout<<"Please input again."<<endl;
			return;
		}
		f = f->link;
	}
}

int List::GetLong(void)
{
	return n;
}

void List::Output(ostream &out)const
{
	Node *p = first;
	while(p)
	{
		out<<p->element<<" ";
		p = p->link;
	}
	out<<endl;
}

//函數功能：將從第i位開始的n個數進行逆序轉換
//函數入口參數
//    i：起始位置數
//    n：進行逆序操作的個數
//函數返回值：無
void List::Reverse(int i,int n)
{
	int j;
	Node *t,*p,*q,*r,*f;
	
	t = p = q = r = f = first;
	
	
	for(j = 1;j < i-1;j++)//逆序從第一位開始，t為頭節(jié)點
		t = t->link;//否則，t為進行逆序轉換的前一個節(jié)點
	if(i != 1)
	{
		r = t->link;
		p = r->link;
		q = r->link;
		f = r;//f,r為需進行逆序轉換的第一個節(jié)點
	}
	else
	{
		p = p->link;
		q = q->link;
	}
	if(n > 1)//若逆序個數n為"0"或"1",則無需進行轉換
	{
		j = 2;//計數器j判斷實際操作數有無超過逆序轉換個數n
		while(j <= n && p)//p,q為需進行逆序轉換的第二個節(jié)點
		{
			p = p->link;
			q->link = r;
			f->link = p;
			r = q;
			q = p;
			j++;
		}
		if(i == 1)//鏈表斷點
			first = r;
		else
		{
			t->link = r;
		}
	}
}

//函數功能: 檢驗輸入內容是否為整數，“空格鍵”為非法輸入
//函數入口參數
//    i: 若判斷結果為整數,其為整數的存儲變量
//函數返回值
//    是整數: 返回true
//    否則: 返回false
bool CheckInteger(int &i)
{
	i = 0;
	int flag1 = 0,flag2 = 0;//判斷標識符
	char c;
	fflush(stdin);//清空緩存區(qū)，stdin為標準輸入，與stdout相對
	c = getchar();
	
	if(c == '\n')
	{
		cout<<"Not a integer."<<endl<<endl;
		return false;
	}
	if(c == '-')
	{
		flag1 = 1;
		c = getchar();
		if(c == ' ' || c == '\n')
			return false;
	}
	while(c != '\n')//對輸入的字符從前到后逐位檢驗合法性
	{
		if(c < '0' || c > '9')//非法數據
		{
			i = 0;//還原i的默認值
			flag2 = 1;//更改標識符
			break;
		}
		else
		{
			char ch;
			int a;
			for(ch = '0',a = 0;c != ch;ch++,a++);//確定該位a的數值
			i = 10 * i + a;//對i加權
			if((flag1 == 1 && i < -1) || (flag1 == 0 && i < 0))//(int)2147483648為64位計算機儲存空間極限
			{
				cout<<"Integer out of bounds"<<endl<<endl; 
				return false;
			}
			c = getchar();
		}
	}
	if(flag1 == 1)
	{
		i *= (-1);
		return true;
	}
	if(flag2 == 1)
	{
		cout<<"Not a integer."<<endl<<endl;
		return false;
	}
	return true;
}


int main()
{
	int q = 1;
	int z = 0;
	int i = 0,n = 0;
	int max;
	max = 10;
	List L(max);

	cout<<"After input,please press \"Enter\" to next step"<<endl;
	while(q)//為測試數據，反復循環(huán)
	{
		char c;
		
		if(z)
			cout<<"0   Use the lastest list."<<endl;
		cout<<"1   Create a ten nodes list by computer."<<endl;
		cout<<"2   Create a sort asending list by yourself."<<endl;
		cout<<"3   Quit."<<endl;
		c = getche();
		cout<<endl<<endl;
		switch(c)
		{
		case '0':
			L.Reverse(i,n);
			break;
		case '1':
			z = 1;
			break;
		case '2':
			if(L.CreateAsendingSort() == false)
				continue;
			z = 1;
			break;
		case '3':
			q = 0;
			continue;
		default:
			cout<<"Incorrect input! "<<"Plaese input again."<<endl<<endl;
			continue;
		}

		max = L.GetLong();
		if(max == 0)
		{
			cout<<"The list is empty."<<endl<<endl;
			z = 0;
			continue;
		}
		
		cout<<"Now,the list is:"<<endl;
		L.Output(cout);
		
		if(max == 1)
		{
			cout<<"There is only one element."<<endl<<endl;
			i = 1;
			n = 1;
			continue;
		}

		cout<<"Reverse from which place? (1 - "<<max<<")"<<endl;
		if(CheckInteger(i) == false)//調用函數輸入,并檢驗其數據合法性
			continue;
		
		if(i < 1 || i > max)
		{
			if(i < 1)
				cout<<"Too low!"<<endl<<endl;
			else
				cout<<"Too high!"<<endl<<endl;
			continue;
		}
		int m = max + 1 - i;
		if(m == 1)
		{
			cout<<"The element is the last one."<<endl<<endl;
			continue;
		}
		
		cout<<"Reverse how many? (0 - "<<m<<")"<<endl;
		if(CheckInteger(n) == false)//調用函數輸入,并檢驗其數據合法性
			continue;
		
		if(n < 0 || n > m)
		{
			if(n < 0)
				cout<<"Too low."<<endl<<endl;
			else
				cout<<"Too high"<<endl<<endl;
			continue;
		}
		
		L.Reverse(i,n);
		cout<<"After reverse,the list is:"<<endl;
		L.Output(cout);

		cout<<endl;
	}
	return 0;
}