jiheyunsuan.cpp

算法与数据结构中

#include<string>
#include<iostream>
using namespace std;

template<class ELEM>class LinkedList;
template<class ELEM>
class Node//结点类
{
	friend class LinkedList<ELEM>;//声明链表类是它的友元
	private:
	    Node<ELEM> * link;
		ELEM data; 		
	public:			
		Node();	
};
template<class ELEM>//构造函数
Node<ELEM>::Node()
{}


template<class ELEM>//链表类
class LinkedList
{	 
	private:
		Node<ELEM> *first;
	public:
		LinkedList();//构造链表
		int Length();//求链表长度
		Node<ELEM> * GetNode();//得到指向链表首结点的指针
        Node<ELEM> * Next(Node<ELEM> * p);//指针p后移一位
		ELEM FindIndex(const int i);//返回第i个结点的数据域
		Node<ELEM> * Insert(ELEM value,int i);//向链表中插入一个结点，以value为数据域，使之成为第i个					
		bool Exist(ELEM e);//判断链表中是否存在数据域为e的结点
		void Show();//遍历链表，逐个显示结点数据域
		void Order();//对链表数据域按从小到大进行排序
};

template<class ELEM>
LinkedList<ELEM>::LinkedList()//构造空链表
{
	first=new Node<ELEM>;
	first->link=NULL;
}
template<class ELEM>
int LinkedList<ELEM>:: Length()//求链表长度
{
	Node<ELEM> *p=first->link;//遍历计数
	int i=1;
	while(p->link!=NULL)
	{			
		p=p->link;
		i++;
	};
    return i;

}
template<class ELEM>
Node<ELEM> * LinkedList<ELEM>::GetNode()//得到指向链表首结点的指针
{
	return first->link;
}
template<class ELEM>
Node<ELEM> * LinkedList<ELEM>::Next(Node<ELEM>* p)//指针p后移一位
{
	Node<ELEM> * q;
	q= p->link;
	return q;
}

template<class ELEM>
ELEM LinkedList<ELEM>::FindIndex(const int i)//返回第i个结点的数据域
{
	Node<ELEM> *p=first->link;
	int j=1;
	while(p!=NULL&&j<i)
	{
		p=p->link;
		j++;
	};
	if(p!=NULL)
		return p->data;
	else 
		return NULL;
}
template<class ELEM>
Node<ELEM> * LinkedList<ELEM>::Insert(ELEM value,int i)//向链表中插入一个结点，以value为数据域，使之成为第i个
{
	Node<ELEM> *q=new Node<ELEM>;
	q->data=value;
	if(i==1)
	{
		first->link=q;//若要插入首结点
		q->link=NULL;
	}
	else
	{
		Node<ELEM> * p=first->link;
	    int j=1;
	    while(p->link!=NULL&&j<i-1)//找到应插入位置的前一结点
		{  
			p=p->link;
		    j++;
		};    
        q->link=p->link;
	    p->link=q;
        return q;
	}
}
template<class ELEM>
bool LinkedList<ELEM>::Exist(ELEM e)//判断链表中是否存在数据域为e的结点
{
	if(first)
	{
		Node<ELEM> *p=first->link;
	    Node<ELEM> * q=first;
	    while(p&&p->data!=e)
		{
		   q=p;
		   p=p->link;
		}
	    if(p&&p->data==e)//若存在返回真
		    return true;
	    else
		    return false;
	}
	else
		return false;
}
template<class ELEM>
void LinkedList<ELEM>::Show()//遍历链表，逐个显示结点数据域
{
	Node<ELEM> *p=first->link;
	while(p!=NULL&&p->link!=NULL)
	{
		cout<<p->data;
		p=p->link;
	}
	if(p!=NULL)
	   cout<<p->data<<endl;

}

template<class ELEM>
void LinkedList<ELEM>::Order()//对链表数据域按从小到大进行排序
{
	Node<ELEM> *p=first->link;
    Node<ELEM> *q;
	while(p)
	{	
		q=p->link;
		while(q)
		{
			if((p->data)>(q->data))
			{
		 	   ELEM e=p->data;
			   p->data=q->data;
			   q->data=e;
			}
			if(q->link)
				q=q->link;
			else
				break;
		}
		if(p->link)
			p=p->link;
		else
			break;
	}
}

template<class ELEM>
LinkedList<ELEM>  Union(LinkedList<ELEM>& s1,LinkedList<ELEM>& s2)//求两个链表中元素的并集
{
	LinkedList<ELEM> t;//存放结果的集合
	Node<ELEM> * p1=s1.GetNode();//找到集合1首结点
	Node<ELEM> * p2=s2.GetNode();//找到集合2首结点
	int i=1,m=1,n=1;//i用来记录结果集应插入元素的位置，m用来记录集合1访问到元素的位置，n用来记录集合2访问到元素的位置
	ELEM c1;//记录1中访问的元素
	ELEM c2;//记录2中访问的元素
	while(p1&&p2)
	{
		c1=s1.FindIndex(m);//得到集合1中第m个结点的元素
	    c2=s2.FindIndex(n);//得到集合2中第n个结点的元素
        if(c1<=c2)
		{
			if(!t.Exist(c1))//若结果集中无该元素，则插入
			{
				t.Insert(c1,i);
			    i++;
			}					
			p1=s1.Next(p1);	//1中指针后移，访问下一元素		
			m++;	
		    if(c1==c2)//相等则不插入，集合2中指针后移，取下一元素
			{
				p2=s2.Next(p2);
				n++;			
			}
		}
		else
		{
			if(!t.Exist(c2))//若结果集中无c2,将元素c2插入结果集
			{
				t.Insert(c2,i);
			    i++;
			}		
			p2=s2.Next(p2);//指针后移，取下一元素
			n++;		
		}
	}		
	while(p1)//若集合1还有剩余元素
	{
		c1=s1.FindIndex(m);
		if(!t.Exist(c1))
		{
				t.Insert(c1,i);//将结果集中不存在的元素都插入
			    i++;
		}		
		p1=s1.Next(p1);//指针后移，插入下一元素
		m++;
	}
	while(p2)//若集合2还有剩余元素
	{
		c2=s2.FindIndex(n);
        if(!t.Exist(c2))
		{
			t.Insert(c2,i);//将结果集中不存在的元素都插入
			i++;
		}		
		p2=s2.Next(p2);//指针后移，插入下一元素
		n++;

	}
	t.Order();//对元素进行排序
	return t;
}

template<class ELEM>
LinkedList<ELEM> Intersaction(LinkedList<ELEM>& s1,LinkedList<ELEM>& s2)//求两个链表中元素的交集
{
	LinkedList<ELEM> t;//存放结果的集合
	Node<ELEM> * p1=s1.GetNode();//找到首结点
	int i=1,m=1;//i用来记录结果集应插入元素的位置，m用来记录集合1访问到元素的位置
	ELEM c1;//记录1中访问的元素
	while(p1)
	{
		c1=s1.FindIndex(m);//得到集合1中第m个结点的元素
        if((s2.Exist(c1))&&(!t.Exist(c1)))//该字符存在2中且结果集中无该元素
		{
			t.Insert(c1,i);//将元素插入结果集合中
			i++;	//标志加1			
			p1=s1.Next(p1);	//指针后移，访问下一个元素		
			m++;	//标志加1
		}
		else 
		{
			p1=s1.Next(p1);	//继续后移，取下一元素			
			m++;			
		}
	
	};
	t.Order();//对元素进行排序
	return t;
}


template<class ELEM>
LinkedList<ELEM>  Difference(LinkedList<ELEM>& s1,LinkedList<ELEM>& s2)//求两个集合的差集
{
	LinkedList<ELEM> t;//存放结果的集合
	Node<ELEM> * p1=s1.GetNode();//找到首结点
	int i=1,m=1;//i用来记录结果集应插入元素的位置，m用来记录集合1访问到元素的位置
	ELEM c1;//记录访问的元素
	while(p1)
	{
		c1=s1.FindIndex(m);//得到集合1中第m个结点的元素
        if((!s2.Exist(c1))&&(!t.Exist(c1)))//若2中无该元素且结果中无该元素
		{	
			t.Insert(c1,i);//将元素插入结果集合中
			i++;	//标志加1		
			p1=s1.Next(p1);	//指针后移，访问下一个元素	
			m++;//标志加1
		}
		else
		{
			p1=s1.Next(p1);	//继续后移，取下一元素		
			m++;
		}
	};
    t.Order();//对元素进行排序
	return t;
}

LinkedList<char> CreatSet(LinkedList<char>& t,string& s)//过滤去非法字符和重复字符，用字符串构造一个集合
{
	int i,j=1;
	for(i=0;i<s.length();i++)
	{
		if((s[i]>='a')&&(s[i]<='z')&&(!t.Exist(s[i])))//对字符逐个进行合法性验证，并保证不重复，构造集合
		{
			t.Insert(s[i],j);
			j++;
		}
	}
	t.Order();//对字符进行排序
    return t;
}


//主函数
void main()
{
	LinkedList<char> s1,s2,s;//构造存放两个集合字符的链表s1和s2,存放运算结果的集合s
	string  a,b;//存放输入的两个字符串
	cout<<"请输入第一个字符串"<<endl;
	cin>>a;//用户输入第一个字符串
	s1=CreatSet(s1,a);//用第一个字符串经过过滤程序构造不含非法字符和重复字符的集合1
	cout<<"经过程序滤去的不含重复字符和非法字符的集合为："<<endl;
	s1.Show();//显示过滤后的数据
	cout<<"请输入第二个字符串"<<endl;
    cin>>b;//用户输入第二个字符串
	s2=CreatSet(s2,b);//用第二个字符串经过过滤程序构造不含非法字符和重复字符的集合2
    cout<<"经过程序滤去的不含重复字符和非法字符的集合为："<<endl;
	s2.Show();//显示过滤后的数据
	s=Union(s1,s2);//求并集
    cout<<"两者的并集是："<<endl;
    s.Show();//显示并集运算结果
	s=Intersaction(s1,s2);//求交集
    cout<<"两者的交集是："<<endl;
    s.Show();//显示交集运算结果
	s=Difference(s1,s2);//求差集
    cout<<"两者的差集是："<<endl;
    s.Show();//显示差集运算结果
}