20081222试验1.cpp

单链表删除 集合a和集合b

/*=============== Program Description =============*/
/* Name of Program: 数据结构试验一.cpp*/
/* Purpose of Program: 建立和删除单链表 */
#include<iostream.h>
struct node
/*定义数据结构*/
{
 	int data; //数据
	node *next;//指向下一结点的指针
};


node *Creat()
/*创建无序链表函数,参数为空,返回值为链表首结点。*/
{
	node *p1,*p2,*head;
 	int a ;
 	head=NULL;
 	cout<<"产生一条无序链表，请输入数据，以-1结束：";
	cin>>a;
	while(a!=-1)//循环输入数据，建立链表
	{
		p1=new node;
  		p1->data=a;
		if(head==NULL)//首结点的建立
		{
			head=p1;
			p2=p1 ;
		}
		else//中间结点的建立
		{
			p2->next=p1;
			p2=p1;
		}
		cin>>a;
	}
	if(head!=NULL)//尾结点的处理
		p2->next=NULL;
	return(head);
}


void print(node *head)
/*输出链表上各结点的数据域函数。参数为自定义数据结构的链表首结点，返回值为空。*/
{
	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)
/*删除结点（此函数增加了删除重复结点的功能，
不仅对于A、B这种不会出现重复数字的集合有用，
对单链表中存在相同data值的情况可以全部删除）*/
{
	if(head==NULL)//链表为空的情况
	{
		return(head);
	}
	node *p1,*p2;
	int i=0;
	p2=head;
	while(p2!=NULL&&i<=1)//被删结点后的一个结点不为空就进行查找
	{	
		node *p;
		if(head->data==num)//首结点符合要求的情况
		{
			p=head;
			p2=head=head->next;
			delete p;
		}
 		else
		{
 			p1=head;
 			p2=head->next;
		}
 		while(p2&&p2->data!=num&&p2->next!=NULL)//当前结点不符合要求则往后移
		{
			p1=p2;
			p2=p2->next;
		}
		if(p2&&p2->data==num&&p2!=head)//结点不为首结点且符合要求
		{
			p=p2;
			p2=p2->next;
			p1->next=p2;
			delete p;
		}
		if(p2!=NULL&&p2->next==NULL)//当前结点为最后一个结点
			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)        
/*释放链表函数。循环删除链表首结点，函数参数为待删除链表首结点，返回值为空。*/
{
	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;
}