问题描述 :
输入A、B、C、D四个集合（集合中无重复元素，且元素值都大于0），分别存储在不带头结点的链表中。
本程序先将四个集合执行以下操作：
1.对A、B、C、D分别进行升序排序；（该功能已实现，见函数sort）。
2.做A=A+B操作：先执行两个有序链表A和B的合并，并仍然保持有序，结果存储在A中，然后删除重复元素；（该功能已实现，见函数merge和purge）。
3.做A=A-C操作：将C中出现的元素从A中删除；（该功能已实现，见函数subtract）。
4.对D中出现的元素，逐一到A中查询：
a.如果在A中存在，则从A中删除
b.如果在A中不存在，则将元素添加到A中，并保持链表A有序。
请编写函数fun的函数体实现本功能。
输出集合A中的元素。（该功能已实现，见函数displayLink）。需要编写的函数的原型如下：
struct student* fun(struct student* L1, struct student* L2)
形参：
L1：传入的第一个集合，程序中将传入A集合的链表头指针
L2：传入的第二个集合，程序中将传入D集合的链表头指针
返回值：返回第一个集合的链表的头指针。
输入说明 :
首先输入一行，包含一个整数N，表示共测试N组数据。
后面接着输入4*N行，每行为一个集合的元素。
每组数据的第1行为集合A的元素，第2行为集合B的元素，第3行为集合C的元素，第4行为集合D的元素。
每个集合的元素值都为大于0的整数，输入时，-1表示结束。
输出说明 :
输出的信息以head开头，以tail结尾，以“–>”分隔。如果是空链表，则直接输出“head–>tail”。具体见输出范例
输入范例： 2 3 5 8 10 15 9 -1 2 5 8 11 14 -1 2 5 10 -1 3 1 9 -1 3 5 8 10 15 9 -1 2 5 8 11 14 -1 2 5 10 -1 2 3 8 -1
输出范例： head–>1–>8–>11–>14–>15–>tail head–>2–>9–>11–>14–>15–>tail
#include <stdio.h> #include <stdlib.h> struct student { int num; struct student *next; }; struct student *createByTail() { struct student *head; struct student *p1,*p2; int n; n=0; p1=p2=(struct student*)malloc(sizeof(struct student)); scanf("%d",&p1->num); head=NULL; //首先置链表为空链表 while(p1->num!=-1) //num为-1，意味着用户输入结束 { n=n+1; if(n==1) //创建第一个结点 head=p1; else p2->next=p1; p2=p1; //p2始终指向最后一个结点（即尾指针） p1=(struct student*)malloc(sizeof(struct student)); //p1指向新结点 scanf("%d",&p1->num); } p2->next=NULL; //切记：最后一个结点的next赋值为NULL return head; } //输出链表中的信息（num） void displayLink(struct student *head) { struct student *p; p=head; printf("head-->"); while(p!= NULL) { printf("%d-->",p->num); p=p->next; } printf("tail\n"); } struct student *insertNodeInOrder(struct student *head,struct student *stu) { struct student *p0,*p1,*p2; p1=head; p0=stu; if(head== NULL) //目前还是空链表 { p0->next=head; head=p0; } else { while((p0->num>p1->num)&&(p1->next!= NULL)) {//查找插入位置，p2指向p1的前驱 p2=p1; p1=p1->next; } //while循环的结束条件有两个，下面需要判断是由哪个条件退出循环 if(p0->num<=p1->num) {//由while循环条件的第一个条件退出循环，因此可插在p1结点之前 if(head==p1) head=p0; else p2->next=p0; p0->next=p1; } else {//由while循环条件的第二个条件退出循环，因此p0->num最大，要插在最后 p1->next=p0; p0->next= NULL; } } return head; } struct student *sort(struct student *head) { struct student *p,*s; p=head; head= NULL; while(p) { s=p; p=p->next; head=insertNodeInOrder(head, s); } return head; } struct student * merge(struct student *LA, struct student *LB) { struct student *p,*s; p=LB; while(p) { s=p; p=p->next; LA=insertNodeInOrder(LA, s); } return LA; } struct student* subtract(struct student* LA, struct student* LB) { struct student *q, * p=LB; struct student *pre=NULL;//pre指向q的前驱，所以最开始赋为NULL while(p!=NULL) //对LB链表遍历 { q=LA; while (q!=NULL && q->num!=p->num) { pre=q; q=q->next; //在LA中查找是否有元素与p->num相同 } if (q!=NULL) //找到了相同的元素，则删除q所指向结点 { if (q==LA) //如果删除第一个结点 { LA = LA -> next; free(q); } else { pre->next=q->next; free(q); } } p=p->next; } return LA; } void purge(struct student * head) { struct student *p,*q; if(head== NULL || head->next == NULL) return; p=head; while(p->next!= NULL) { if(p->num == p->next->num) { q=p->next; p->next=q->next; free(q); } else { p=p->next; } } } struct student* fun(struct student* L1, struct student* L2) { int flag; struct student *pa,*pb,*t,*q; pb=L2; while(pb!=NULL) { flag=0; pa=L1; while(pa!=NULL){ if((pa->num) == (pb->num)){ flag=1; break; } pa=pa->next; } t=pa; if(flag==0){ //插入新结点 student *node=new student; node->num=pb->num; L1=insertNodeInOrder(L1, node); } else{ //删除 if(t==L1){ L1=t->next; } else{ q=L1; while(q->next!=t){ q=q->next; } q->next=t->next; } delete t; } pb=pb->next; } return L1; } int main() { struct student *headA, *headB, *headC, *headD; int i,n; while(scanf("%d", &n)!= EOF) { i=0; while(i<n) { headA=createByTail();//创建链表A headB=createByTail();//创建链表B headC=createByTail();//创建链表C headD=createByTail();//创建链表D headA = sort(headA);//链表A排序 headB = sort(headB);//链表B排序 headC = sort(headC);//链表C排序 headD = sort(headD);//链表D排序 headA = merge(headA, headB);//将链表B合并到链表A中 purge(headA);//删除链表A中重复元素 headA = subtract(headA, headC);//从链表A中减去链表C中元素 headA=fun(headA, headD);//对链表A和链表D调用fun函数 displayLink(headA);//输出链表A中的元素 i++; } } return 0; }*注意： 1、新建结点：student node=new student; 2、找该结点的前置结点语句：while(q->next!=t) q=q->next;
