list.cpp

设有一个数列

#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);//删除所有节点
	bool CreateAsendingSort(void);//创建升序链表
	void Insert(int x);//插入节点
	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为头节点
		t = t->link;//否则，t为进行逆序转换的前一个节点
	if(i != 1)
	{
		r = t->link;
		p = r->link;
		q = r->link;
		f = r;//f,r为需进行逆序转换的第一个节点
	}
	else
	{
		p = p->link;
		q = q->link;
	}
	if(n > 1)//若逆序个数n为"0"或"1",则无需进行转换
	{
		j = 2;//计数器j判断实际操作数有无超过逆序转换个数n
		while(j <= n && p)//p,q为需进行逆序转换的第二个节点
		{
			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);//清空缓存区，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)//为测试数据，反复循环
	{
		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;
}