有两个集合用两个线性表LA和LB表示即线性表中的数据元素即为集合中的成员。现要求一个新的集合A=A∪B。

第一篇：有两个集合用两个线性表LA和LB表示即线性表中的数据元素即为集合中的成员。现要求一个新的集合A=A∪B。

例2-1 假设有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A＝A∪B。////////////////////////////////////////////////////////// 上述问题可演绎为：

要求对线性表作如下操作：

扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。

////////////////////////////////////////////////////////// 操作步骤：

1．从线性表LB中依次察看每个数据元素;GetElem(LB,i)→e 2．依值在线性表LA中进行查访;LocateElem(LA,e,equal())3．若不存在，则插入之。ListInsert(LA,n+1,e)////////////////////////////////////////////////////////// void union(List &La,List Lb){ La_len=ListLength(La);//求线性表的长度 Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){ GetElem(Lb,i,e);//取Lb中第i个数据元素赋给e if(!LocateElem(La,e,equal()))ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则插入之 } }//union ////////////////////////////////////////////////////////// #ifndef DSH #define DSH

#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE-1 #define OVERFLOW-2 //Status是函数的类型，其值是函数结果状态代码 typedef int Status;typedef int ElemType;

#endif ////////////////////////////////////////////////////////// #ifndef LISTH #define LISTH

#include “ds.h”

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct{ ElemType *elem;//存储空间基址

int length;//当前长度

int listsize;//当前分配的存储容量(以sizeof(ElemType)为单位)}List;

//俗称顺序表

#endif

Status InitList(List &);void CreateList(List &, int[],int);int ListLength(List);void GetElem(List, int, ElemType &);int LocateElem(List, ElemType, Status(*compare)(ElemType,ElemType));Status ListInsert(List &, int, ElemType);void PrintList(List);//////////////////////////////////////////////////////////////// #include #include #include “List.h” Status InitList(List &L){ //构造一个空的线性表L。

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;} //InitList

void CreateList(List &L, int a[],int n){

//顺序输入n个数据元素，建立顺序表

int i;for(i=0;i

L.elem[i]=a[i];//输入元素值

L.length=n;} //CreateList

int ListLength(List L){ return L.length;}

void GetElem(List L, int i, ElemType &e){ e=L.elem[i-1];}

int LocateElem(List L, ElemType e, Status(*compare)(ElemType,ElemType)){ int i;int *p;i=1;//i的初值为第1元素的位序

p=L.elem;

//p的初值为第1元素的存储位置

while(i<=L.length &&!(*compare)(*p++,e))

++i;if(i<=L.length)

return i;else

return 0;}

Status ListInsert(List &L,int i,ElemType e){ //在顺序线性表L的第i个位置之前插入新的元素e,i的合法值为1≤i≤ListLength(L)+1 ElemType *newbase,*q,*p;if(i<1 || i>L.length+1)

return ERROR;//i值不合法

if(L.length>=L.listsize)

{

//当前存储空间已满，增加分配

newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase)exit(OVERFLOW);//存储分配失败

L.elem=newbase;

//新基址

L.listsize+=LISTINCREMENT;//增加存储容量

}

q=&(L.elem[i-1]);

//q为插入位置

for(p=&(L.elem[L.length-1]);p>=q;--p)

*(p+1)=*p;//插入位置及之后的元素右移

*q=e;

//插入e ++L.length;//表长增1 return OK;} // ListInsert

void PrintList(List L){

// 输出顺序表L int i;printf(“n”);for(i=1;i<=L.length;++i)

printf(“%d ”,L.elem[i-1]);

// 输入元素值

printf(“n”);} ////////////////////////////////////////// #include #include #include “List.h” int a[]={3,5,8,11};int b[]={2,6,8,9,11,15,20};Status equal(ElemType,ElemType);void Union(List &,List);Status equal(ElemType x,ElemType y){ return x==y;}

void Union(List &La,List Lb){ // 将所有在线性表Lb中但不在La中的数据元素插入到La中

int i;int e;int La_len,Lb_len;

La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){

GetElem(Lb,i,e);

if(!LocateElem(La,e,equal))

ListInsert(La,++La_len,e);} }//Union

int main(){ List La,Lb;InitList(La);InitList(Lb);

CreateList(La,a,4);CreateList(Lb,b,7);printf(“集合A：”);PrintList(La);printf(“集合B：”);PrintList(Lb);

Union(La,Lb);printf(“集合A U B：”);PrintList(La);printf(“A与B的并集对吗？”);getchar();return 0;} /////////////////////////////////////////////////