链表操作.cpp

这是一个在C环境下编写的链表操作

//链表的插入及链表的交、并、差运算。
//其它参见"文档RTF"中的内容。
#include<iostream>
#include<string>
using namespace std;

  
  struct NODE
 {  
	 int  data;
	 NODE  *next;
 };
  
class LinkList 
{
     private:	
        int   count ;
		NODE  *head;
	 public:
		 LinkList();
		 ~LinkList(){};
		 void  Insert(int);
		 void Initersection(LinkList &);
         void Union(LinkList &);
	     void Difference(LinkList &); 
		 void  print( );
		 bool emptyList();
		 void destroy(LinkList &);		 	
}La,Lb,Lc;
           
LinkList::LinkList()         //create linked list
{  
	  head=new NODE;
	  head->next=NULL;
	  count=0;
	  
}
  
void LinkList::Insert(int x)      //插入一个
{  
	NODE *p,*q; 
    q=new NODE; 
	q->data=x; q->next=NULL;
    p=head;
	if(p->next==NULL)
	{
		q->next=p->next;
		p->next=q;
	}
	else
	{
		while(p->next&&x>p->next->data)
			p=p->next;
		q->next=p->next;
		p->next=q;   
		count++;
	}
}

void  LinkList::print()
{
	 NODE *p;
	 int dataOut;
     p=head->next ;
	 if(p==NULL)
		 cout<<"Empty!"<<endl;
	 else
		while(p)
		{
			dataOut=p->data;
			cout<< dataOut<<"  ";
			p=p->next;
		}
    cout<<endl;
} 

void LinkList::Initersection(LinkList &Lc)
{
	 NODE *pa,*pb,*pc,*q;
	 pa=La.head->next; 
	 pb=Lb.head->next;
	 pc=Lc.head;
	 while(pa && pb)
	 {
		 if(pa->data==pb->data)
		 {
			 q = new NODE;
			 q->data = pa->data;
			 q->next = NULL;
			 pc->next = q;
			 pc = q;
			 pa=pa->next;
			 pb=pb->next;
			 Lc.count++;
		 }
		 else
			if(pa->data < pb->data)
			{
				pa = pa->next;
			}
			else
				pb = pb->next;
	 }
}


void LinkList::Union(LinkList &Lc)
{
	 NODE *pa,*pb,*pd,*q;
	 pa=La.head->next; 
	 pb=Lb.head->next;
	 pd=Lc.head;
	 while(pa && pb)
	 {
		 if(pa->data < pb->data)
		 {			 
			 q = new NODE; 
			 q->data = pa->data;
			 q->next = NULL;
			 pa = pa->next;
			 Lc.count++;
		 }
		 else
			 if(pa->data == pb->data)
			 {			 
				q = new NODE;
				q->data = pa->data;
				q->next = NULL;
				pa = pa->next;
				pb = pb->next;
				Lc.count++;
			}
			else {
				q=new NODE;
			    q->data = pb->data;
			    q->next = NULL;
			    pb = pb->next;
				Lc.count++;
			} 
		pd->next = q;
		pd = q;
	 }
	 while(pa)
	 {
		q = new NODE;
		q->data = pa->data;
		q->next = NULL;
		pd->next = q;
		pd = q;
		pa = pa->next;
		Lc.count++;
	 }
	 while(pb)
	 {
		q = new NODE;
		q->data = pb->data;
		q->next = NULL;
		pd->next = q;
		pd = q;
		pb = pb->next;
		Lc.count++; 
	 }
 } 
 void LinkList::Difference(LinkList &Lc)
{
	 NODE *pa,*pb,*pe,*q;
	 pa=La.head->next; 
	 pb=Lb.head->next;
	 pe=Lc.head;
	 if(pa==NULL)
		 return;
	 while(pa && pb)
	 {
		 if(pa->data < pb->data){			 
			 q = new NODE; 
			 q->data = pa->data;
			 q->next = NULL;
			 pe->next = q;
			 pe = q;
			 pa = pa->next;
			 Lc.count++;
		 }
		 else
			 if(pa->data == pb->data)
			 {
                pa = pa->next;
                pb = pb->next;
			 }
			 else 
				pb = pb->next;
	 }
	 while(pa)
	 {
		q = new NODE;
		q->data = pa->data;
		q->next = NULL;
		pe->next = q;
		pe = q;
		pa = pa->next;
		Lc.count++;
	 }
	 
 } 
bool LinkList::emptyList()
{
	return (count==0);
}
void LinkList::destroy(LinkList &L)
{
	NODE *p,*q;
	p=L.head;
	while(p->next)
	{
		q=p->next;
		p->next=q->next;
		delete q;
		L.count--;
	}
}
void menue()
{
	cout<<"输入1，就插入元素"<<endl;
	cout<<"输入2，就求两个链表的交集"<<endl;
	cout<<"输入3，就求两个链表的并集"<<endl;
	cout<<"输入4，就求两个链表的差集"<<endl;
	cout<<"输入0，程序退出"<<endl;
}
void main()
{      
	int N,choice,x; 
	menue();
	cout<<"please  choose operation(操作项）："<<endl;
    while(cin>>N)
	{    
		if(N<0||N>4)
		{
			cout<<"Error!"<<endl;
			cout<<"please input N(N>=0&&N<=4)："<<endl;	
		}
		switch(N)
		{
		case 1: 
			cout<<"输入1，则插到A表中,否则插到B表中"<<endl;
			cin>>choice;
			cout<<"输入要插入的数"<<endl;
			cin>>x;
			if(choice==1)
				La.Insert(x);
			else
				Lb.Insert(x);
			cout<<"please  choose operation(操作项）："<<endl;
			break;
		case 2:   
			La.Initersection(Lc);
			cout<<"La is:"; La.print();
			cout<<"Lb is:"; Lb.print();
			cout<<"Initersection is:"; Lc.print();
			Lc.destroy(Lc);
			cout<<"please  choose operation(操作项）："<<endl;
			break;
		case 3:   
			La.Union(Lc);
			cout<<"La is:"; La.print();
			cout<<"Lb is:"; Lb.print();
			cout<<"Union is:"; Lc.print();
			Lc.destroy(Lc);
			cout<<"please  choose operation(操作项）："<<endl;
			break;
		case 4:   
			La.Difference(Lc);
			cout<<"La is:"; La.print();
			cout<<"Lb is:"; Lb.print();
			cout<<"Difference is:"; Lc.print(); 
			Lc.destroy(Lc);
			cout<<"please  choose operation(操作项）："<<endl;
			break;
		case 0: 
			La.destroy(La);
			Lb.destroy(Lb);
			exit(0);
		}
	}            
}