/*=============== Program Description =============*/
/* Name of Program: 數(shù)據(jù)結(jié)構(gòu)試驗(yàn)一.cpp*/
/* Purpose of Program: 建立和刪除單鏈表 */
#include<iostream.h>
struct node
/*定義數(shù)據(jù)結(jié)構(gòu)*/
{
 	int data; //數(shù)據(jù)
	node *next;//指向下一結(jié)點(diǎn)的指針
};


node *Creat()
/*創(chuàng)建無序鏈表函數(shù),參數(shù)為空,返回值為鏈表首結(jié)點(diǎn)。*/
{
	node *p1,*p2,*head;
 	int a ;
 	head=NULL;
 	cout<<"產(chǎn)生一條無序鏈表，請(qǐng)輸入數(shù)據(jù)，以-1結(jié)束：";
	cin>>a;
	while(a!=-1)//循環(huán)輸入數(shù)據(jù)，建立鏈表
	{
		p1=new node;
  		p1->data=a;
		if(head==NULL)//首結(jié)點(diǎn)的建立
		{
			head=p1;
			p2=p1 ;
		}
		else//中間結(jié)點(diǎn)的建立
		{
			p2->next=p1;
			p2=p1;
		}
		cin>>a;
	}
	if(head!=NULL)//尾結(jié)點(diǎn)的處理
		p2->next=NULL;
	return(head);
}


void print(node *head)
/*輸出鏈表上各結(jié)點(diǎn)的數(shù)據(jù)域函數(shù)。參數(shù)為自定義數(shù)據(jù)結(jié)構(gòu)的鏈表首結(jié)點(diǎn)，返回值為空。*/
{
	node *p;
	p=head;
	cout<<endl;
	while(p!=NULL)
	{
 		cout<<(p->data)<<'\t';
 		p=p->next;
 	}
 	cout<<endl;
}


node *Delete_one_node(node *head,int num)
/*刪除結(jié)點(diǎn)（此函數(shù)增加了刪除重復(fù)結(jié)點(diǎn)的功能，
不僅對(duì)于A、B這種不會(huì)出現(xiàn)重復(fù)數(shù)字的集合有用，
對(duì)單鏈表中存在相同data值的情況可以全部刪除）*/
{
	if(head==NULL)//鏈表為空的情況
	{
		return(head);
	}
	node *p1,*p2;
	int i=0;
	p2=head;
	while(p2!=NULL&&i<=1)//被刪結(jié)點(diǎn)后的一個(gè)結(jié)點(diǎn)不為空就進(jìn)行查找
	{	
		node *p;
		if(head->data==num)//首結(jié)點(diǎn)符合要求的情況
		{
			p=head;
			p2=head=head->next;
			delete p;
		}
 		else
		{
 			p1=head;
 			p2=head->next;
		}
 		while(p2&&p2->data!=num&&p2->next!=NULL)//當(dāng)前結(jié)點(diǎn)不符合要求則往后移
		{
			p1=p2;
			p2=p2->next;
		}
		if(p2&&p2->data==num&&p2!=head)//結(jié)點(diǎn)不為首結(jié)點(diǎn)且符合要求
		{
			p=p2;
			p2=p2->next;
			p1->next=p2;
			delete p;
		}
		if(p2!=NULL&&p2->next==NULL)//當(dāng)前結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)
			i++;
	}
	return(head);
}


node *AB(node *A ,node *B )//A減B
{
	node *pb=B;
	while(pb!=NULL)
 	{
 		A=Delete_one_node(A,pb->data);
 		pb=pb->next;
 	}
	return(A);
}


void Del_chain(node *head)        
/*釋放鏈表函數(shù)。循環(huán)刪除鏈表首結(jié)點(diǎn)，函數(shù)參數(shù)為待刪除鏈表首結(jié)點(diǎn)，返回值為空。*/
{
	node *p1;
	while(head)
	{
		p1=head;
		head=head->next;
		delete p1;
	}
}


void main()
{
	node *A,*B;
	A=Creat();
	B=Creat();
	A=AB(A,B);
	cout<<"打印A－B";
	print(A);
	Del_chain(A);           //釋放a鏈表和b鏈表
	Del_chain(B);
	cout<<endl;
}