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

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

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

#include#include#include#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#include#include#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)); //申请结点空间ck->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指向Aint 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;}PrintLinkList(B);}int main(){LinkList A;A = (LNode *) malloc(sizeof(LNode)); //初始化单链表AA->next = NULL;LinkList B;B = (LNode *) malloc(sizeof(LNode)); //初始化单链表BB->next = NULL;LinkList C;C = (LNode *) malloc(sizeof(LNode)); //初始化单链表CC->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;}}