使用顺序表、单链表求集合运算

******、设有两个顺序表A和B，编写一个算法将属于A，但是不属于B的数据元素放大到另一个顺序表C中

（1）、算法设计
遍历顺序表A，将A中每一个元素依次与顺序表B比较，如果相等直接跳过开始比较下一个元素，如果没有相等的直接放在顺序表C中！
（2）、算法实现

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#define MAXSIZE 20
#define endl '\n' 
using namespace std; 
typedef struct{
	int *data; 
	int length; 
}SqList;

//操作函数 
void SubStrction(SqList &A,SqList &B,SqList &C){
	int i = 0 , j = 0 , k = 0;
	for(i = 0; i < A.length; i++){                    //依次遍历顺序表A   
		for (j = 0; j < B.length; j++){               //依次遍历顺序表B 
			if (A.data[i] == B.data[j])
			    break;                                //如果在B中找到与A.data[i]相同的元素，直接跳出当前循环，执行该层循环外的代码 
		}
		if ( j == B.length )                          //如果j == B.length说明直到将顺序表B遍历完都没有找到A.data[i]相同的元素，即可将A.data[i]加入顺序表C中 
	        C.data[k++] = A.data[i];           
	}
	C.length = k;                                     //修改顺序表C的长度  
}

//输入函数 
void Input(SqList &A,SqList &B){
	cout<<"\n请输入顺序表A(结束请输入-1)：";
	int i = 0; 
	int a;
	cin>>a; 
	while(a != -1){ 
		A.data[i] = a;     
		i++;
		cin>>a; 
	}
	A.length = i;
	cout<<"\n请输入顺序表B(结束请输入-1)：";
	int j = 0;
	int b; 
	cin>>b; 
	while(b != -1){
		B.data[j] = b; 
		j++;
		cin>>b; 
	}
	B.length = j;
} 
int main(){
	SqList A;
	A.data = (int *) malloc(sizeof(int)*MAXSIZE);          //给顺序表A分配内存空间
	A.length = 0;
	SqList B;
	B.data = (int *) malloc(sizeof(int)*MAXSIZE);          //给顺序表B分配存储空间
	B.length = 0;
	SqList C;
	C.data = (int *) malloc(sizeof(int)*MAXSIZE);          //给顺序表C分配存储空间 
	C.length = 0;
	Input(A,B);                                            //输入顺序表 
	SubStrction(A,B,C); 
	cout<<"\n输出包含在顺序表A中但是不在顺序表B中的元素集合如下：";                                 
    for(int i = 0;i < C.length; i++){                      //输出顺序表C               
    	cout<<" "<<C.data[i]<<" "; 
	} 
}

******、已知两个单链表A和B分别表示两个集合，其元素递增排列，设计一个算法求A和B的交集，要求C同样以元素值递增的单链表存储！

（1）、算法设计
先遍历链表A，找到第一个结点，然后取结点的数值域依次与链表A中的每一个结点中的数值域进行比价，如果相同使用后插法创建单链表的方法将交集元素插入到链表C中！直到将链表A中所有结点中的数值域均与链表B中的依次比较，即可完成操作！
（2）、算法实现

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#define MAXSIZE 20
#define endl '\n' 
using namespace std; 
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList; 

//打印创建的单链表 
void PrintLinkList(LinkList L){
	LNode *p;
	p = L->next;
	cout<<"\n后插法创建的单链表如下：";
	while(p){
		cout<<p->data<<" ";
		p = p->next;
	}
} 

//操作函数
void InterSection(LinkList &A,LinkList &B,LinkList &C){
	LNode *p = A->next;
	LNode *q;
	LNode *c = C;
	int ElemA; 
	while(p != NULL){
		ElemA = p->data;
		q = B->next;                                           //每次遍历完内层循环，一定要将指针q回溯到链表B的首元节点 
		while(q != NULL){
			if ( ElemA == q->data){                            //如果AB有交集 
			    LNode *k = (LNode *)malloc(sizeof(LNode));     //申请结点空间c
				k->data = ElemA;             
				k->next = NULL;
				c->next = k;
				c = k;  
			}
			q = q->next; 
		}
		p = p->next;
	}
} 

//输入函数
void InputElement(LinkList &A,LinkList &B){
	cout<<"\n输入单链表A(结束请输入 -1)：";
	LNode *LA = A;                                            //LA指向A
	int a;
	cin>>a;
	while(a != -1){
		LNode *p;
		p = (LNode *)malloc(sizeof(LNode));                   //申请结点的存储空间 
		p->data = a;
		p->next = NULL;
		LA->next = p;                                         //将新节点*p插入到尾节点*LA之后，使得p有了地址 
		LA = p;                                               //使LA重新指向新的尾结点*p 
		cin>>a; 
	}
	PrintLinkList(A);
	cout<<"\n\n输入单链表B(结束请输入 -1)：";
	LNode *LB = B;
	int b;
	cin>>b;
	while(b != -1){
		LNode *p;
		p = (LNode *)malloc(sizeof(LNode));                   //申请结点存储空间 
		p->data = b;
		p->next = NULL; 
	    LB->next = p;
		LB = p; 
		cin>>b;
		break;                  
	}
	PrintLinkList(B);
}


int main(){
	LinkList A;
	A = (LNode *) malloc(sizeof(LNode));                      //初始化单链表A
	A->next = NULL;
	LinkList B;
	B = (LNode *) malloc(sizeof(LNode));                      //初始化单链表B
	B->next = NULL;
	LinkList C;
	C = (LNode *) malloc(sizeof(LNode));                      //初始化单链表C
	C->next = NULL; 
	InputElement(A,B);                                        //输入单链表
	InterSection(A,B,C);                                      //操作函数
	cout<<"\n\n输出单链表A和B的交集如下：";
    LNode *p;
	p = C->next;
	while(p){
		cout<<p->data<<" ";
		p = p->next;
	}
}