精华内容
下载资源
问答
  • C语言数据结构课程设计,集合交并差,分部完成实验报告。
  • Problem A: 求集合交并补集 Time Limit: 1 SecMemory Limit: 4 MB Submit: 6817Solved: 1972 [Submit][Status][Web Board] Description 任意给定两个包含1-30000个元素的集合A,B(集合中元素类型为任意整型数...

    Problem A: 求集合的交并补集

    Time Limit: 1 SecMemory Limit: 4 MB
    Submit: 6817Solved: 1972
    [Submit][Status][Web Board]

    Description

    任意给定两个包含1-30000个元素的集合A,B(集合中元素类型为任意整型数,且严格递增排列),求A交B、A并B、A-B和B-A集合。

    Input

    输入第一行为测试数据组数。每组测试数据两行,分别为集合A、B。每行第一个数n(1<=n<=30000)为元素数量,后面有n个严格递增的绝对值小于2^31代表集合中包含的数。

    Output

    对每组测试数据输出5行,第1行为数据组数,后4行分别为按升序输出两个集合的A交B、A并B、A-B和B-A集合。格式见样例。

    Sample Input

    1
    2
    3
    1
    3 1 2 5
    4 2 3 5 8

    Sample Output

    1
    2
    3
    4
    5
    Case #1:
    2 5
    1 2 3 5 8
    1
    3 8

    HINT

    考察知识点:有序表合并,时间复杂度O(n),空间复杂度O(n)

    解题思路:1)分析 数据/元素 需要用什么结构储存 2)设计算法实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    #include <stdio.h>    
    #include <malloc.h>    
    #include <iostream>    
    #include <stdlib.h>    
    #define LIST_INIT_SIZE 100    
    #define LISTINCREMENT 10    
    #define OK 1    
    #define OVERFLOW -1    
    #define ERROR 0    
       
           
    typedef int Status;    
           
    typedef int ElemType;    
           
    typedef struct SqList{    
        ElemType * elem;   //数组首地址    
        int listSize;  //表容量;当前表的容量    
        int length;  //表长,代表当前数组中有效元素的个数    
    }SqList;    
           
    // 下面实现nitList操作,即初始化一个空的线性表    
    Status InitList_Sq(SqList &L)    
    {    
        L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));    
        //malloc的返回值类型是void *;    
        //使用时要及时进行强制类型转换    
        if(!L.elem)    
            exit(OVERFLOW);    
        L.listSize=LIST_INIT_SIZE;    
        L.length=0;    
        return OK;    
    }    
         
       
             
    Status CreateList(SqList &La,int na){     
        for(int i = 1;i<=na;++i){     
            ElemType e;     
    //      printf("请输入第%d个元素",i);     
            scanf("%d",&e);     
       if(La.length >= La.listSize)   {     
            La.elem=(ElemType *)realloc(La.elem,(La.listSize+LISTINCREMENT)*sizeof(ElemType));     
            La.listSize += LISTINCREMENT;     
        }     
            La.elem[i-1]=e;     
            La.length++;     
        }     
        return OK;     
    }       
     
           
    void MergeList_Sq(SqList La,SqList Lb,SqList &Ld,SqList &Le)    
    //Ld是交,Le是补  
        ElemType* pa = La.elem;    
        ElemType* pb = Lb.elem;    
     
        Ld.length = 0;    
        Ld.listSize = La.length + Lb.length;    
        Ld.elem = (ElemType*)malloc(Ld.listSize*sizeof(ElemType));    
        ElemType* pd = Ld.elem;    
        if(!Ld.elem)    
            exit(OVERFLOW);    
           
        Le.length = 0;    
        Le.listSize = La.length + Lb.length;    
        Le.elem = (ElemType*)malloc(Ld.listSize*sizeof(ElemType));    
        ElemType* pe = Le.elem;     
        if(!Le.elem)    
            exit(OVERFLOW);    
           
           
        ElemType* pa_last = La.elem + La.length -1;    
        ElemType* pb_last = Lb.elem + Lb.length -1;    
        while(pa <= pa_last && pb <= pb_last)    
        {    
            if(*pa <= *pb)    
            {    
                if(*pa == *pb)    
                {    
                    *pd++ = *pa;    
                    Ld.length++;    
                }    
                else
                {    
                    *pe++ = *pa;     
                    Le.length++;    
                }    
               // *pc++ = *pa++;    
                pa++;  
            }    
            else
            {    
                *pe++ = *pb;    
                Le.length++;    
              //  *pc++ = *pb++;    
                pb++;  
            }    
        }    
        while(pa <= pa_last)    
        {    
            *pe++ = *pa;    
            Le.length++;    
            //*pc++ = *pa++;    
            pa++;  
        }    
           
        while(pb <= pb_last){    
            *pe++ = *pb;    
            Le.length++;    
           // *pc++ = *pb++;   
            pb++;  
        }    
    }    
           
    void MergeList_Sq2(SqList La,SqList Lb,SqList &Lc)    
    {    
        int i,j;    
        Lc.length = 0;    
        Lc.listSize = La.length + Lb.length;    
        Lc.elem = (ElemType*)malloc(Lc.listSize*sizeof(ElemType));    
        int n = 0;    
        for(i = 0;i < La.length;i++){    
            j = 0;    
            while((j < Lb.length)&&(La.elem[i] != Lb.elem[j])){    
                j++;    
            }    
            if(j == Lb.length){    
                Lc.elem[n] = La.elem[i];    
                ++Lc.length; ++n;   
            }    
        }    
             
    }    
           
           
    void ListPrint_Sq(SqList L){     
        if(L.length==0) {     
            printf("\n");     
        }     
        else
        {     
            for(int i=0;i<L.length;++i){     
                if(i==0){     
                  printf("%d",L.elem[i]);     
                }     
                else{     
                  printf(" %d",L.elem[i]);     
                    }     
            }     
            printf("\n");     
        }     
    }     
       
           
    int main()    
    {    
        int num,i;    
        scanf("%d",&num);    
        for(i = 1;i <= num;i++)    
        {    
            SqList La,Lb,Ld,Le,Lf,Lg;    
            InitList_Sq(La);    
            InitList_Sq(Lb);    
       
            int na,nb;    
            scanf("%d",&na);   
            CreateList(La,na);  
            scanf("%d",&nb);    
            CreateList(Lb,nb);  
     
            MergeList_Sq(La,Lb,Ld,Le);  
            MergeList_Sq2(La,Ld,Lf);    
            MergeList_Sq2(Lb,Ld,Lg);    
            printf("Case #%d:\n",i);    
            //ListPrint_Sq(Lc);    
            ListPrint_Sq(Ld);    
            ListPrint_Sq(Le);    
            ListPrint_Sq(Lf);    
            ListPrint_Sq(Lg);    
           
        }    
           
        return 0;    
    }
    展开全文
  • 数据结构–c语言链表实现集合的()运算! **前言:** *进入了大二,有同学说学习数据结构像学习数学(但这里不仅仅高中数学运算那么简单!更多是逻辑和思维的训练吧!)。而本宝宝刚开始面对这门课程...

    数据结构–c语言链表实现集合的(并,交,补)运算!

    要求如图:
    这里在这里插入图片描述
    这些是功能界面,相当于一个菜单吧(声明:集合只适用于时数字)!

    #include<stdio.h>
    #include<stdlib.h>
    #define ERROR -1
    #define OK     1
    typedef int Status;   //要加分号
    typedef int ElemType;
    typedef struct LNode{
    	ElemType      data;
    	struct LNode  * next;
    }LNode, *LinkList;
    //创建空链表
    Status Init_LinkList(LinkList &L)
    {
    	LinkList p;
    	p=(LinkList)malloc(sizeof(LNode));
    	if(!p)
    		return ERROR;
    	L=p;
    	L->next=NULL;
    	return OK;
    }
    int x,y;
    void show()
    {
    	
    	printf("\t\t*********单链表(头插法)集合运算************\n");
    	printf("\n");
    	printf("\t\t\t1 集合A数据输入\n");
    	printf("\t\t\t2 集合B数据输入\n");
    	printf("\t\t\t3 集合A数据显示\n");
    	printf("\t\t\t4 集合B数据显示\n");
    	printf("\t\t\t5 集合A和集合B的并集\n");
    	printf("\t\t\t6 集合A和集合B的交集\n");
    	printf("\t\t\t7 集合A和集合B的差集\n");
    	printf("\t\t\t0 退出系统\n");
    	printf("\n");
    	printf("\t\t*********单链表(头插法)集合运算*************\n");
    	printf("\n");
    }
    // 输入
    Status input(LinkList &L,int n)   //不能写成input(LinkList L,int n),这样的值不会改变
    {
    	LinkList p;
    	int i;
    	for(i = 1;i <= n;i ++)
    	{
    		//printf("请输入集合的第%d个数:",i);
    		p=(LinkList)malloc(sizeof(LNode));
    		if(p!=NULL)
    		{
    			scanf("%d",&p->data);
    			p->next = L->next;   //头插法
    			L->next = p;
    		}
    		else
    			return ERROR;
    	}
    	printf("集合输入完成!\n");
    	return OK;
    }
    
    //输出
    
    void Output(LinkList L)
    {
    	LinkList p;  //定义一个指针p
    	//p=(LinkList)malloc(sizeof(LNode));
    	if(L->next==NULL)
    		printf("该链表是空链表!\n");
    	else
    	{
    		for(p=L->next;p!=NULL;p=p->next)
    			printf("%d ",p->data);
    		printf("\n");
    	}
    }
    
    
    //实现链表的清空
    Status ClearList_L(LinkList &L)
    {
    	LinkList p,q; //定义两个指针p,q
    	p=L->next;
    	if(!p)        //如果p指向的链表L是一个空表 就直接返回OK
    		return OK;
    	while(p)      //当p指向的链表L不是空表  则进行以下语句,赋给另外一个指针
    	{
    		q=p;
    		p=p->next;
    		free(q);   //释放链表结点的空间
    	}
    	L->next=NULL; //将L链表的next指针域 置为 NULL 空
    	return OK;
    }
    
    
    //并集  (先清空C,C中的数据会在后面的循环中不断插入!就是A与C找比较,C中没有A的就插入;B与C找比较,C中没有B的就插入(遍历完,即==NULL的时候插入))
    void and_set(LinkList La,LinkList Lb,LinkList &Lc)
    {
    	if(Lc->next!=NULL)  //如果Lc链表不为空则就要进行链表清空
    		ClearList_L(Lc); 
    	LinkList p,q,s;//p指针用来遍历A,B   q用来控制C的结点
    
    	//对链表A插入C中
    	p=La->next;   //指针p控制扫描La的每一个结点(元素)
    	while(p)
    	{
    		q=Lc->next;
    		while(q && (q->data!=p->data))//C中不为空,且数据不相等
    			q=q->next;
    		if(q==NULL)  //当q遍历完一次都没有找到的话,即q的最后为空时就可以将A中的一个元素插入C中
    		{
    			s=(LinkList)malloc(sizeof(LNode));  //s指针用来控制C中的数据
    			s->data=p->data;  //头插法
    			s->next=Lc->next;
    			Lc->next=s;
    		}
    		p=p->next;
    	}
    
    	//对链表B插入C中
    	p=Lb->next;   //指针p控制扫描Lb的每一个结点(元素)
    	while(p)
    	{
    		q=Lc->next;
    		while(q && (q->data!=p->data))C中不为空,且数据不相等
    			q=q->next;
    		if(q==NULL)  //当q遍历完一次都没有找到的话,即q的最后为空时就可以将A中的一个元素插入C中
    		{
    			s=(LinkList)malloc(sizeof(LNode));  //s指针用来控制C中的数据
    			s->data=p->data;  //头插法
    			s->next=Lc->next;
    			Lc->next=s;
    		}
    		p=p->next;
    	}
    
    	/*
    	//插A
    	while(p!=NULL)
    	{
    		q=Lc->next;  //指针q控制扫描链表Lc的每一个结点(元素)
    		while(q && (q->data != p->data))
    			q=q->next;
    		if(!q) //La中没找到与Lc链表中相同的结点时,就把La上结点在Lc上插入(把集合La的元素填入集合Lc)
    		{
    			s=(LinkList)malloc(sizeof(LNode));
    			s->data=p->data;
    			s->next=Lc->next;   //插入到头部
    			Lc->next=s;
    		}
    		p=p->next;  //指向下一个结点
    	}
    	p=Lb->next;
    	*/
    	//插B
    	/*while(p!=NULL)
    	{
    		q=Lc->next;
    		while(q && (q->data != p->data))  //如果找到Lb中的元素与Lc中的元素相同则就继续循环否则就结束循环
    			q=q->next;
    		if(!q) //满足没找到相同元素的情况
    		{
    			s=(LinkList)malloc(sizeof(LNode)); //创建一个新的结点
    			s->data=p->data;    //将Lb中的元素赋给s结点
    			s->next=Lc->next;  //然后插入到Lc表的头部
    			Lc->next=s;
    		}
    		p=p->next;
    	}*/
    }
    
    //交集   (先清空C链表,再A与B中找相同的break(不为空,记录),再与C中比较(与并集同理插入)插入C中即可)
    void intersection(LinkList La,LinkList Lb,LinkList &Lc)
    {
    	LinkList p,q,s,k; //p是遍历A,q是遍历B,s是遍历C,k是赋值指针
    	if(Lc->next)
    		ClearList_L(Lc);
    	//A
    	p=La->next;
    	while(p)  //A中不为空时
    	{
    		q=Lb->next;
    		while(q)
    		{
    			if(p->data==q->data)//找到了就可以break,也可以定义t进行计数操作,但是这样不好计算链表长度,当然也可以定义全局变量
    				break;
    			else
    				q=q->next;
    		}
    		if(q) //p不为空
    		{
    			s=Lc->next;
    			//寻找C中是否含有相同数据
    			while(s)
    			{
    				if(s->data==p->data)
    					break;
    				else
    					s=s->next;
    			}
    			if(s==NULL)
    			{
    				k=(LinkList)malloc(sizeof(LNode));
    				k->data=p->data;
    				k->next=Lc->next;
    				Lc->next=k;
    			}
    		}
    		p=p->next;
    	}
    
    
    	/*
    	p=La->next;
    	while(p)
    	{
    		q=Lb->next;
    		while(q)
    		{
    			if(q->data==p->data)  
    				break;
    			else
    				q=q->next;
    		}
    		if(q)
    		{
    			s=Lc->next;
    			//寻找C中是否含有相同数据
    			while(s!=NULL)
    			{
    				if(s->data==p->data)
    					break;
    				else 
    					s=s->next;
    			}
    			if(s==NULL)
    			{
    				k=(LinkList)malloc(sizeof(LNode));
    				k->data=p->data;
    				k->next=Lc->next;
    				Lc->next=k;
    			}
    		}
    		p=p->next;
    	}*/
    }
    
    //差集  (先清空C后,找A中与B中不同的,找到B最后,即==NULL的时候插入即可!)
    void difference_set(LinkList La,LinkList Lb,LinkList &Lc)
    {
    	LinkList p,q,s,k;
    	if(Lc->next)
    		ClearList_L(Lc);
    	p=La->next;
    	while(p!=NULL)
    	{
    		q=Lb->next;
    		while(q!=NULL)
    		{
    			if(q->data==p->data)
    				break;
    			else
    				q=q->next;
    		}
    		if(q==NULL)
    		{
    			s=Lc->next;
    			//寻找C中是否含有相同数据
    			while(s!=NULL)
    			{
    				if(s->data==p->data)
    					break;
    				else 
    					s=s->next;
    			}
    			if(s==NULL)
    			{
    				k=(LinkList)malloc(sizeof(LNode));
    				k->data=p->data;
    				k->next=Lc->next;
    				Lc->next=k;
    			}
    		}
    		p=p->next;
    	}
    }
    int main()
    {
    	//定义
    	int choice;
    	LinkList La,Lb,Lc;
    	//初始化
    	Init_LinkList(La);
    	Init_LinkList(Lb);
    	Init_LinkList(Lc);
    	//功能
    	while(1)
    	{
    		show();
    		printf("请输入要选择的功能:\n");
    		scanf("%d",&choice);
    		
    		switch(choice)
    		{
    			case 1:ClearList_L(La);printf("请输入集合A要插入的个数:\n");scanf("%d",&x);input(La,x);
    					printf("请按回车继续!\n");
    				    getchar();getchar();system("cls");break;
    			case 2:ClearList_L(Lb);printf("请输入集合B要插入的个数:\n");scanf("%d",&y);input(Lb,y);
    					printf("请按回车继续!\n");
    					getchar();getchar();system("cls");break;
    			case 3:printf("集合A为:\n");
    					Output(La);
    					printf("请按回车继续!\n");
    					getchar();getchar();system("cls");break;
    			case 4:printf("集合B为:\n");
    					Output(Lb);
    					printf("请按回车继续!\n");
    					getchar();getchar();system("cls");break;
    			case 5:printf("集合A与集合B的并集为:\n");
    					and_set(La,Lb,Lc);
    					Output(Lc);
    					printf("请按回车继续!\n");
    					getchar();getchar();system("cls");break;
    			case 6:printf("集合A与集合B的交集为:\n");
    					intersection(La,Lb,Lc);
    					Output(Lc);
    					printf("请按回车继续!\n");
    					getchar();getchar();system("cls");break;
    			case 7:printf("集合A与集合B的并集为:\n");
    					difference_set(La,Lb,Lc);
    					Output(Lc);
    					printf("请按回车继续!\n");
    					getchar();getchar();system("cls");break;
    			case 0:printf("成功退出系统!\n");exit(0);
    					getchar();getchar();system("cls");break;
    			default:printf("输入有误!\n"); exit(0);break;
    		}
    	}
    	return 0;
    }
    

    最后,相关步骤注意清空,代码中含有一些注释(大佬们若感觉很白痴请自动忽略),另外我所写得代码中的集合A,B的是完全依赖于高中的定义(即三个性质:确定性,互异性,无序性),若代码中存在错误,请评论留言,或者联系qq邮箱:865805295@qq.com,祝大家编程愉快!完!

    展开全文
  • 顺序表结构编程实现两集合交并补 #include <iostream> #include<stdio.h> #include <stdlib.h> using namespace std; #define OK 1 #define ERROR 0 #define LIST_INIT_SIZE 100 #define LIST...

    顺序表结构编程实现两集合交并补

    #include <iostream>
    #include<stdio.h>
    #include <stdlib.h>
    using namespace std;
    
    #define OK 1
    #define ERROR 0
    #define LIST_INIT_SIZE 100
    #define LISTINCREMENT 10
    #define OVERFLOW -2
    typedef struct
    {
        int *elem;             //定义一个指针表示存储空间基址
        int  length;               //当前表长(特指元素个数)
        int listsize;
    } SqList;
    
    //初始化
    int InitList_Sq(SqList &L)
    {
        L.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));//动态分配内存
        if(!L.elem)
            exit(OVERFLOW);
        L.length=0;
        L.listsize=LIST_INIT_SIZE;
        return OK;
    }
    
    //给顺序表赋值
    void fuzhi(SqList &L)
    {
        int n,m;
        cout<<"请输入集合的数据元素个数"<<endl;
        cin>>n;
        for(int i=0; i<n; i++)
        {
            cout<<"请输入第"<<i+1<<"的数据元素的值"<<endl;
            cin>>m;
            L.elem[i]=m;
            L.length++;
        }
        cout<<"赋值成功"<<endl;
    }
    
    void Get(SqList L)
    //输出当前列表
    {
        //cout<<"当前列表:"<<endl;
        for(int i=0; i<L.length; i++)
        {
            cout<<L.elem[i]<<" ";
        }
        cout<<endl;
    }
    
    int GetElem(SqList L,int i,int &e)
    //用e返回L中第i个元素的值
    {
        if(i<1||i>L.length)
            return ERROR;
        e=L.elem[i-1];
        return OK;
    }
    
    int equal_e(int a,int b)
    {
        if(a==b)
            return OK;
        else
            return ERROR;
    }
    
    int LocateElem(SqList L,int e,int (*compare)(int,int))
    //在表中查找第一个值与e满足compare()元素的位序
    {
        int i=1;
        int *p=L.elem;
        while(i<=L.length&&!(*compare)(*p++,e))
            ++i;
        if(i<=L.length)
            return i;
        else
            return 0;
    }
    
    //在顺序表指定位置插入元素
    int ListInsert_Sq(SqList &L,int i,int e)
    {
        if(i<1||i>L.length+1)
            return ERROR;
        if(L.length>=L.listsize)
        {
            int *newbase;
            newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));//扩充内存
            if(!newbase)
                exit(OVERFLOW);
            L.elem=newbase;
            L.listsize+=LISTINCREMENT;
        }
        int *p,*q;
        q=&(L.elem[i-1]);
        for(p=&(L.elem[L.length-1]); p>=q; p--)
            *(p+1)=*p;
        *q=e;
        ++L.length;
        return OK;
    }
    
    void union_set(SqList La,SqList Lb,SqList &Lc)
    //a与b的并集放入c中
    {
        int La_len=La.length;
        int Lb_len=Lb.length;
        int e;
        for(int i=1; i<=Lb_len; i++)
        {
            GetElem(Lb,i,e);
            if(!LocateElem(La,e,equal_e))
                ListInsert_Sq(La,++La_len,e);
        }
    
        for(int i=1; i<=La_len; i++)
        {
            GetElem(La,i,e);
            ListInsert_Sq(Lc,i,e);
        }
    }
    
    int mixture(SqList La,SqList Lb,SqList &Lc)
    //a与b的交集
    {
        int La_len=La.length;
        int Lb_len=Lb.length;
        int e;
        int index=0;
        //cout<<Lc.length<<endl;
        SqList p=La_len<=Lb_len?La:Lb;
        SqList q=La_len>Lb_len?La:Lb;
        for(int i=1; i<=p.length; i++)
        {
            GetElem(p,i,e);
            if(LocateElem(q,e,equal_e))
            {
                ListInsert_Sq(Lc,++index,e);
                //Get(Lc);
            }
        }
        if(Lc.length)
            return OK;
        else
            return ERROR;
    }
    
    int different(SqList La,SqList Lb,SqList &Lc)
    //求a-b差集
    {
        int La_len=La.length;
        int e;
        int index=0;
        for(int i=1; i<=La_len; i++)
        {
            GetElem(La,i,e);
            if(!LocateElem(Lb,e,equal_e))
                ListInsert_Sq(Lc,++index,e);
        }
        if(Lc.length)
            return OK;
        else
            return ERROR;
    }
    
    int main()
    {
    
        SqList La,Lb;
        InitList_Sq(La);
        InitList_Sq(Lb);
        cout<<"集合A:"<<endl;
        fuzhi(La);
        cout<<"集合A中元素: ";
        Get(La);
        cout<<endl;
        cout<<"集合B:"<<endl;
        fuzhi(Lb);
        cout<<"集合B中元素: ";
        Get(Lb);
        cout<<endl;
    
        cout<<"A并B:"<<endl;
        SqList Lc1;
        InitList_Sq(Lc1);
        union_set(La,Lb,Lc1);
        Get(Lc1);
        cout<<endl;
    
        cout<<"A交B:"<<endl;
        SqList Lc2;
        InitList_Sq(Lc2);
        if(mixture(La,Lb,Lc2))
        {
            Get(Lc2);
            cout<<endl;
        }
        else
        {
            cout<<"null"<<endl;
            cout<<endl;
        }
        
        cout<<"A-B:"<<endl;
        SqList Lc3;
        InitList_Sq(Lc3);
        if(different(La,Lb,Lc3))
            Get(Lc3);
        else
            cout<<"null"<<endl;
    
        return 0;
    }
    
    

    剖析:
    1.初始化

    //初始化
    int InitList_Sq(SqList &L)
    {
        L.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));//动态分配内存
        if(!L.elem)
            exit(OVERFLOW);
        L.length=0;
        L.listsize=LIST_INIT_SIZE;
        return OK;
    }
    
    • malloc()为动态存储分配函数,需要头文件<stdlib.h>.
    • 这里我们从堆中动态分配了400个字节的内存空间(按照int 是4个字节计算,即100个int的大小)。然后将首地址返回给L.elem,若函数执行失败则返回null。
    • exit(n)就是退出,传入的参数n是程序退出时的状态码,0表示正常退出,其他表示非正常退出

    2.往顺序表中插入元素

    //在顺序表指定位置插入元素
    int ListInsert_Sq(SqList &L,int i,int e)
    {
        if(i<1||i>L.length+1)
            return ERROR;
        if(L.length>=L.listsize)
        {
            int *newbase;
            newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));//扩充内存
            if(!newbase)
                exit(OVERFLOW);
            L.elem=newbase;
            L.listsize+=LISTINCREMENT;
        }
        int *p,*q;
        q=&(L.elem[i-1]);
        for(p=&(L.elem[L.length-1]); p>=q; p--)
            *(p+1)=*p;
        *q=e;
        ++L.length;
        return OK;
    }
    
    • realloc(a,b)函数用来扩大动态分配区域,即当第二个参数b大于第一个参数a指向的动态内存大小时将重新申请一个大小为b的内存空间。
    • 添加时为防止覆盖要先把后面的向后移再插入。

    3.构造一个按某种规则定位的函数

    int equal_e(int a,int b)
    {
        if(a==b)
            return OK;
        else
            return ERROR;
    }
    
    int LocateElem(SqList L,int e,int (*compare)(int,int))
    //在表中查找第一个值与e满足compare()元素的位序
    {
        int i=1;
        int *p=L.elem;
        while(i<=L.length&&!(*compare)(*p++,e))
            ++i;
        if(i<=L.length)
            return i;
        else
            return 0;
    }
    
    • compare那个是把一个函数作为变量传入函数locateElem()中,本题中compare指向equal_e()函数。
    • 本题中函数locateElem()的功能是找到顺序表L中第一个和e相同的元素位置。

    4.求两个集合的并集

    void union_set(SqList La,SqList Lb,SqList &Lc)
    //a与b的并集放入c中
    {
        int La_len=La.length;
        int Lb_len=Lb.length;
        int e;
        for(int i=1; i<=Lb_len; i++)
        {
            GetElem(Lb,i,e);
            if(!LocateElem(La,e,equal_e))
                ListInsert_Sq(La,++La_len,e);
        }
    
        for(int i=1; i<=La_len; i++)
        {
            GetElem(La,i,e);
            ListInsert_Sq(Lc,i,e);
        }
    }
    
    • 如果集合B中的元素在集合A中全找了一遍都没有相等的话,那LocateElem()函数中的i就会大于L.length。此时这里的if判断成真。我们把这个e添加到集合A的最后一位。

    5.两个集合求交集

    int mixture(SqList La,SqList Lb,SqList &Lc)
    //a与b的交集
    {
        int La_len=La.length;
        int Lb_len=Lb.length;
        int e;
        int index=0;
        //cout<<Lc.length<<endl;
        SqList p=La_len<=Lb_len?La:Lb;
        SqList q=La_len>Lb_len?La:Lb;
        for(int i=1; i<=p.length; i++)
        {
            GetElem(p,i,e);
            if(LocateElem(q,e,equal_e))
            {
                ListInsert_Sq(Lc,++index,e);
                //Get(Lc);
            }
        }
        if(Lc.length)
            return OK;
        else
            return ERROR;
    }
    
    
    • 因为两集合的交集一定小于等于两集合中最小的那个,所以我们从小集合中取元素跟大集合比较,这样更快一点。
    • 如果对比成功的位置小于L.length说明集合A中存在这个元素,此时if判断成真,我们将它放入新的顺序表中表示交集。

    6.两集合求差

    int different(SqList La,SqList Lb,SqList &Lc)
    //求A-B差集
    {
        int La_len=La.length;
        int e;
        int index=0;
        for(int i=1; i<=La_len; i++)
        {
            GetElem(La,i,e);
            if(!LocateElem(Lb,e,equal_e))
                ListInsert_Sq(Lc,++index,e);
        }
        if(Lc.length)
            return OK;
        else
            return ERROR;
    }
    
    
    • ABA - BBAB - A可不一样,所以这里只能从A中拿元素和B里的元素进行比较。
    • 差集和交集规则相反,if里面加一个!就好。
    展开全文
  • 集合交并补C语言版

    2010-12-14 23:00:06
    这是一个我们数据结构课程设计做的集合交并补,当时我们学的是c语言,很适合于大学生作为课程设计之用,当然也可以做为毕业设计的参考,真心希望对你的课程设计有所帮助!!!
  • 集合的定义以及集合交并补运算

    千次阅读 2018-12-29 12:16:04
    //集方法difference:返回一个新的集合,该集合是那些属于第一个集合但是不属于第二个集合的成员 function difference(set) { var tempSet=new Set(); for (var i=0;i;i++) { if (set.dataStore.indexOf...
    <!DOCTYPE html>
    <html lang="en">
    <head>
        <meta charset="UTF-8">
        <title>Title</title>
    </head>
    <body>
    <script>
        function Set()
        {
            this.dataStore=[];//初始化空数组保存Set元素
            this.add=add;//向集合中增加元素
            this.remove=remove;//删除集合中的元素
            this.union=union;//执行集合的并集操作,将两个集合合并成一个
            this.interSect=interSect;//求两个集合的交集
            this.subset=subset;//判断一个集合是否是另一个集合的子集
            this.difference=difference;//求两个集合的补集
            this.show=show;
        }
        //add方法
        function add(data)
        {
            if (this.dataStore.indexOf(data)<0)//首先判断要添加的元素是否存在于该集合
            {
              this.dataStore.push(data);//添加元素
              return true;//正确的在Set中添加元素,返回True
            }
            else
            {
                return false;//否则返回false
            }
        }
    
        //remove方法:首先检查要删除的元素在Set中是否存在,存在的话,使用splice()方法删除
        function remove(data)
        {
            if (this.dataStore.indexOf(data)>-1)
            {
                var position=this.dataStore.indexOf(data);//获取要删除元素的位置
                this.dataStore.splice(position,1);
                return true;
            }
            else
            {
                return false;
            }
        }
    
        //union方法:将第一个集合的元素加入临时集合,然后查看第二个集合中的元素是否属于第一个集合中的元素,如果属于,则跳过该成员;否则就将该成员加入临时集合
        function union(set)
        {
            var tempSet=new Set();//定义临时集合
            for(var i=0;i<this.dataStore.length;i++)
        {
                tempSet.add(this.dataStore[i]);
            }
            for (var i=0;i<set.dataStore.length;i++)
            {
                if (tempSet.dataStore.indexOf(set.dataStore[i])<0)//这里使用了contains方法
                {
                    tempSet.dataStore.push(set.dataStore[i]);
                }
            }
            return tempSet;
        }
    
        //补集方法intersect():第一个集合的成员也属于第二个集合
        function interSect(set)
        {
            var tempSet=new Set();
            for (var i=0;i<this.dataStore.length;i++)
            {
                if (set.dataStore.indexOf(this.dataStore[i])>-1)
                {
                    tempSet.add(this.dataStore[i]);
                }
            }
            return tempSet;
        }
    
    //子集方法subset():首先确定该集合的长度是否小于待比较集合。
        //如果该集合比待比较集合大,那么该集合肯定不是待比较集合的一个子集;
        //当该集合的长度小于待比较集合时,在判断该集合内的成员是否都属于待比较集合;
        //如果有任意一个成员不属于比较集合,则返回false,程序终止
        function subset(set)
        {
            if (this.dataStore.length>set.dataStore.length)
            {
                return false;
            }
            else
            {
                for (var i = 0; i < this.dataStore.length; i++)
                {
                    if (set.dataStore.indexOf(this.dataStore[i])<0)
                    {
                        return false;
                    }
                }
    
            }
            return true;
        }
    
    //补集方法difference:返回一个新的集合,该集合是那些属于第一个集合但是不属于第二个集合的成员
        function difference(set)
        {
            var tempSet=new Set();
            for (var i=0;i<this.dataStore.length;i++)
            {
                if (set.dataStore.indexOf(this.dataStore[i])<0)
                {
                    tempSet.add(this.dataStore[i]);
                }
            }
            return tempSet;
        }
        //显示Set元素的方法
        function show()
        {
            return this.dataStore;
        }
    
    
    
    
    
    
    
    
    
    //测试add方法
        var names=new Set();//实例化集合
        names.add("Huaicui Zheng");
        names.add("Mingsi Zhang");
        names.add("Qin Han");
        names.add("RUigang Zhao");
        names.add("Peiang Zuo");
        console.log(names.show());/*["Huaicui Zheng", "Mingsi Zhang", "Qin Han", "RUigang Zhao", "Peiang Zuo"]*/
        if (names.add("Qin Han"))
        {
            console.log("Qin Han is added successfully!");/*Qin Han has been added,please checked again!*/
        }
        else
        {
            console.log("Qin Han has been added,please checked again!");
        }
        if (names.add("Jie Yang"))
        {
            console.log("JIe Yang is added successfully!");/*Qin Han has been added,please checked again!*/
        }
        else
        {
            console.log("Qin Han has been added,please checked again!");/*JIe Yang is added successfully!*/
        }
    
    //测试remove方法
        var removedNames="Peiang Zuo";
        if (names.remove(removedNames))
        {
            console.log( removedNames+"is removed.");/*Peiang Zuois removed.*/
        }
        else
        {
            console.log(removedNames+"is not existed.");
        }
        console.log(names.show());/* ["Huaicui Zheng", "Mingsi Zhang", "Qin Han", "RUigang Zhao", "Jie Yang"]*/
        var removedNames="Mike";
        if (names.remove(removedNames))
        {
            console.log( removedNames+"is removed.");
        }
        else
        {
            console.log(removedNames+"is not existed.");/*Mikeis not existed.*/
        }
        console.log(names.show());/*["Huaicui Zheng", "Mingsi Zhang", "Qin Han", "RUigang Zhao", "Jie Yang"]*/
    //union方法
        var cis=new Set();//集合cis
        cis.add('Mike');
        cis.add('Clayton');
        cis.add('Jennifer');
        cis.add('Raymond');
    
        var dmp=new Set();//集合dmp
        dmp.add("Raymond");
        dmp.add("Cynthia");
        dmp.add("Jonathan");
    
        var newNrr=new Set();//取union之后的集合
        newNrr=cis.union(dmp);
        console.log(newNrr.show());/* ["Mike", "Clayton", "Jennifer", "Raymond", "Cynthia", "Jonathan"]*/
    
    
    //交集方法
        var ciss=new Set();
        ciss.add("Mike");
        ciss.add("Clayton");
        ciss.add("Jennifer");
        var dmpp=new Set();
        dmpp.add("Raymond");
        dmpp.add("Cynthia");
        dmpp.add("Jennifer");
    
        var newNrr1=new Set();//取union之后的集合
        newNrr1=ciss.interSect(dmpp);
        console.log(newNrr1.show());/*["Jennifer"]*/
    
     //子集方法subset
     var it1=new  Set();
     it1.add("Cynthia");
     it1.add("Clayton");
     it1.add("Danny");
     it1.add("Mike");
     it1.add("Terrill");
    
    
     var dmp1=new Set();
     dmp1.add("Cynthia");
     dmp1.add("Clayton");
     dmp1.add("Terrill");
    
     if (dmp1.subset(it1))
     {
         console.log("dmp1 is the subset of the it1");/*dmp1 is the subset of the it1*/
     }
     else
     {
         console.log("dmp is not the subset of the it1");
     }
    
    
    
    
     //补集方法
        var  cisss=new Set();
        var  itt=new Set();
        cisss.add("Clayton");
        cisss.add("Danny");
        cisss.add("Jennifer");
        cisss.add("Huaicui Zheng");
    
        itt.add("Clayton");
        itt.add("Danny");
        itt.add("Mike");
        itt.add("lily");
    
        var diff=new Set();
        diff=cisss.difference(itt);
        console.log("The difference is"+diff.show());/*Jennifer,Huaicui Zheng*/
    </script>
    </body>
    </html>```
    
    
    展开全文
  • 集合、差运算 【问题描述】 编制一个能演示执行集合和差运算的程序。 【任务要求】 集合元素用小写英文字母,执行各种操作应以对话方式执行。 算法要点:利用单链表表示集合;理解好三种运算的含义...
  • 本设计中用到的数据结构ADT定义如下: ADT List{ 数据对象:D={} 数据关系:={}
  • list集合交并补计算

    2020-05-28 22:06:06
    list是我们常用的数据结构,存放数据,如何对数据进行交并补的计算。 list的底层是动态数组,作为比较基础和常用的数据结构,在日常的工作中我们可能将不同的数据存放到了list中,根据业务要求,对两个集合的数据...
  • 编制一个能演示执行集合和差运算的程序。 【基本要求】 (1) 集合的元素限定为小写字母字符 [‘a’..’z’] 。 (2) 演示程序以用户和计算机的对话方式执行。 【测试数据】 (1)Set1="magazine",Set2=...
  • 编制一个能演示执行集合并交和差运算的程序 要求 集合的元素限定为小写字母字符[a.z] 演示程序以用户和计算机的对话方式执行 实现提示以链表表示集合 选作内容 集合的元素判定和子集判定运算 求集合集 ...
  • 集合交并补运算

    2018-06-29 10:28:02
    可以实现资源的交并差运算,有良好的人机交互界面,可以实现交并差运算内容
  • 至少应包括初始化,用尾插法建立集合,查找给定元素是否在集合内,将新元素插入集合中,删除集合中指定元素,求两个集合、差、输出等操作的实现。 要求设计一个主程序,首先定义3个用有序单链表实现的集合A...
  • Problem A: 求集合交并补集 任意给定两个包含1-30000个元素的集合A,B(集合中元素类型为任意整型数,且严格递增排列),求AB、AB、A-B和B-A集合
  • //利用顺序表实现集合的运算 #include<cstdio> #include<iostream> #include<stdbool.h> #define MAXSIZE 10//最大元素个数设置为10个 using namespace std; typedef struct { int *elem; int ...
  • 集合 运算

    千次阅读 2017-07-21 10:15:07
    //C=AB; for(int i=0;i;i++){ C.a[i]=A.a[i]; C.length++; } for(int i=0;i;i++){ int sign=0; for(int j=0;j;j++) if(C.a[j]==B.a[i]) sign=1; if(sign==0){ C.a[C.length]=B....
  • 昨天用数据结构中的线性表的顺序结构实现了关于集合、差、集合运算,做个记录,希望也能帮助到其他人。 一、算法分析  (1)用数组A,B,C,E表示集合。假定A={1,3,4,5,6,7,9,10},  B={2,,3,4...
  • 实验 二 集合和差运算 //在写代码的过程中,没有注意头结点~~~ 导致出现了很多野指针~~~ ,几乎重写. 。o 0 ~~~ // 经同学检查,发现有错误~~~ 红色部分代码已经修正 //集合和差运算 /*选作...
  • 集合运算:、差,判定一个元素是否属于某一集合差集:集合并、差某元素属于什么集合 查集中集合存储如何实现: (1)用树结构表示集合,树的每个节点代表一个集合元素。 (2)采用数组存储形式: ...
  • 数据结构:整数集合

    2020-03-31 12:10:22
    整数集合 整数集合的定义:由若干互不相同的正整数组成的集合,其中全集为0至MaxRange,MaxRange为构成该集合元素的最大值 整数集合的操作: ...T:集合中元素的数据类型,对于整数集合来说是无符号整型u...
  • 文章目录三种方式实现 Python 中的集合、补运算一 背景二 实践过程2.1 通过 Python 的推导式来实现2.2 通过 Python 对集合的内置方法来实现2.3 通过 Python 按位运算来实现三 总结 三种方式实现 Python 中...
  • 数据结构集合及运算

    千次阅读 2019-08-24 18:02:30
    集合运算:、差,判定一个元素是否属于某一集合 查集:集合并、查某元素属于什么集合 查集问题中集合存储如何实现? 可以用树结构表示集合,树的每个结点代表一个集合元素 采用数组存储形式 ...
  • 查集是一种树型的数据结构,用于处理一些不相交集合(disjoint sets)的合并及查询问题。   查集问题中集合存储如何实现?     ⋄\diamond⋄ 可以用树结构表示集合,树的每个结点代表一个集合元素。   ...
  • 使用双亲表示法表示一个集合
  • 实 验 报 告 实验课程数 据 结 构 实验项目实验一集合交差运算 专 业计算机科学与技术 班 级 姓 名 学 号 指导教师 目 录 问题定义及需求分析 1实验目的 2实验任务 3需求分析 二概要设计 (1)抽象数据类型定义 (2...
  • python中的set是指一系列无序元素的集合,其中的元素都是相异的,常见的操作包括集合的并集,交集和集等操作。 1、set的创建 格式 set_name = {value1, value2, ...} 创建空的集合 set_name = set() 注意:...
  • 数据结构课程设计 #include using namespace std; #include typedef struct LNode//结构体 { char data; struct LNode *next; }*linklist; void in_put(linklist head)//输入 { linklist p; char tmp=cin.get(); cin...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,582
精华内容 3,832
关键字:

数据结构集合交并补

数据结构 订阅