/*文件名:exam10_8.cpp*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef char DataType;    	/*用typedef語句定義DataType為char類型*/
typedef struct node 		/*用typedef語句定義ListNode為node結(jié)構(gòu)體類型*/
{
	DataType data;     		/*數(shù)據(jù)域*/
   	struct node *next;  	/*指針域*/
} ListNode;
ListNode *createlist() 			/*該函數(shù)最后返回單鏈表的頭結(jié)點(diǎn)的指針*/
{   
	char ch;
	ListNode *head=(ListNode *)malloc(sizeof(ListNode));/*創(chuàng)建頭結(jié)點(diǎn)*/
	ListNode *s,*r=head;       	/*r始終指向單鏈表的最后結(jié)點(diǎn)*/
	printf("輸入結(jié)點(diǎn)值:");
   	ch=getchar();              	/*讀第1個(gè)字符*/
	while (ch!='\n') 
	{
		s=(ListNode *)malloc(sizeof(ListNode));  /*創(chuàng)建一個(gè)新結(jié)點(diǎn)*/
		s->data=ch;            	/*將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中*/
       	r->next=s;r=s;         	/*在*r之后插入*s,并將s賦給r*/
		ch=getchar();          	/*讀入下一字符*/
	}
	r->next=NULL;
   	return head;               	/*返回頭結(jié)點(diǎn)的指針*/
}
ListNode *getnode(ListNode *head,int i)
{
	int j=0;
	ListNode *p;
   	p=head;	                     	/*從頭開始掃描*/
	while (p->next!=NULL && j<i)   	/*順next指針方向移動(dòng)指針變量p*/
	{
		p=p->next;
		j++;
	}
	if (p!=NULL)					/*若p不為空,表示查找成功*/
		return p;                   /*找到了第i個(gè)結(jié)點(diǎn)*/
   	else
     	return NULL;                /*當(dāng)i<0或i>n時(shí),找不到第i個(gè)結(jié)點(diǎn)*/
}
void displist(ListNode *head)  
{
	ListNode *p=head->next;			/*p指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)*/
	if (p==NULL)
		printf("空表\n");
	else 
	{
		while (p!=NULL) 			/*沿next順序掃描每個(gè)結(jié)點(diǎn),并輸出其data域*/
		{
			printf("%c ",p->data);
			p=p->next;
		}
		printf("\n");
	}
} 
void insertnode(ListNode *head,DataType x,int i)
{
	ListNode *p,*s;
	s=(ListNode *)malloc(sizeof(ListNode));  /*創(chuàng)建新插的結(jié)點(diǎn)*/
	s->data=x;
	if (i==1)       					/* *s作為1號(hào)數(shù)據(jù)結(jié)點(diǎn) */
	{
		s->next=head->next;
		head->next=s;
	}
	else 
	{
		p=getnode(head,i-1);  			/*查找指向第i-1個(gè)結(jié)點(diǎn)的指針*/
		if (p==NULL)         			/*i<1或i>n+1時(shí)插入位置i有錯(cuò)*/
		{
			printf("i取值有錯(cuò)\n");
			exit(0);
		}
		s->next=p->next;     			/*將*s插入在*p之后*/
		p->next=s;						/*將*p的指針域指向*s結(jié)點(diǎn)*/
	}
} 
void deletenode(ListNode *head,int i)
{
	ListNode *p,*r;
	p=getnode(head,i-1);           	/*找第i-1個(gè)結(jié)點(diǎn)*/
	if (p==NULL || p->next==NULL)  	/*i<1或i>n時(shí)刪除位置有錯(cuò)*/
	{
		printf("i取值有錯(cuò)\n");
		exit(0);
	}
	r=p->next;                     	/*令r指向被刪結(jié)點(diǎn)*/
	p->next=r->next;               	/*將*r從鏈上摘下*/
	free(r);   						/*釋放結(jié)點(diǎn)*r,將所占用的空間歸還給存儲(chǔ)池*/
} 
void freelist(ListNode *head)
{
	ListNode *p=head,*q=p->next;
	while (q!=NULL) 
	{
		free(p);
		p=q;q=q->next;
	}
	free(q);
}
ListNode *subs(ListNode *heada,ListNode *headb)
{
	ListNode *p,*q,*r,*s;
	p=heada->next;          			/*p指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)*/
	r=heada;r->next=NULL;   		/*r指向生成的單鏈表的最后一個(gè)結(jié)點(diǎn)*/
	while (p!=NULL)        			/*掃描A*/
	{
		q=headb;
		while (q!=NULL && q->data!=p->data)  
			q=q->next; 
		if (q!=NULL)        			/*若p結(jié)點(diǎn)在B中,則要?jiǎng)h除之*/
		{
			s=p->next;
			free(p);p=s;
		}
		else               			/*若p結(jié)點(diǎn)不在B中,則鏈接到新單鏈表中*/
		{
			r->next=p;s=p->next;
			r=p;r->next=NULL;
			p=s;
		}
	}
	return heada;
}
main()
{
	ListNode *ha,*hb,*hc;
	ha=createlist();        		/*調(diào)用單鏈表基本運(yùn)算函數(shù)創(chuàng)建A集合*/
	hb=createlist();        		/*調(diào)用單鏈表基本運(yùn)算函數(shù)創(chuàng)建B集合*/
	printf("A集合:");displist(ha);	/*調(diào)用單鏈表基本運(yùn)算函數(shù)輸出單鏈表ha*/
	printf("B集合:");displist(hb); 	/*調(diào)用單鏈表基本運(yùn)算函數(shù)輸出單鏈表hb*/
	hc=subs(ha,hb);
	printf("A-B:");displist(hc);	/*調(diào)用單鏈表基本運(yùn)算函數(shù)輸出單鏈表hc*/
}