利用线性表的顺序结构求集合的并、交、差、补（C语言实现）

2024-09-01 07:58
文章标签 语言 实现 结构 顺序 集合 线性表

本文主要是介绍利用线性表的顺序结构求集合的并、交、差、补（C语言实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

昨天用数据结构中的线性表的顺序结构实现了关于集合的并、交、差、补的集合运算，做个记录，希望也能帮助到其他人。

一、算法分析


　　（1）用数组A，B，C，E表示集合。假定A={1,3，4，5，6，7，9，10},
　　B={2，,3，4，7，8，10}, E={1,2，3，4，5，6，7，8，9，10},
　　输入数组A，B，E（全集），输入数据时要求检查数据是否重复（集合中的数据要求不重复），要求集合A，B是集合E的子集。
　　
　　（2）两个集合的并运算：把数组A中各个元素先保存在数组C中。将数组B中的元素逐一与数组A中的元素进行比较，把不相同的元素添加到数组C中，数组C便是集合A和集合B的并。
　　 C语言算法（线性表顺序结构实现）：

/**求集合的并集的函数**/
void Union_Sq(SqList La,SqList Lb,SqList &Lc){
int i;
ElemType elem;
Lc.length=0;
for(i = 0; i < La.length; i++)
Lc.elem[Lc.length++]=La.elem[i];
for(i = 1; i <= Lb.length; i++){
elem = Lb.elem[i-1];
if(!LocateElem_Sq(La,elem,Equal))
ListInsert_Sq(Lc,Lc.length+1,elem);}
}


（3）两个集合的交运算：把数组A中元素逐一与数组B中的元素进行比较，将相同的元素放在数组C中，数组C便是集合A和集合B的交。
　　C语言算法（线性表顺序结构实现）：

/**求集合的交集的函数**/
void Mix_Sq(SqList La,SqList Lb,SqList &Lc){
int i;
ElemType elem;
Lc.length = 0;
for(i = 1; i <= La.length; i++){
elem = La.elem[i-1];
if(LocateElem_Sq(Lb,elem,Equal))
ListInsert_Sq(Lc,Lc.length+1,elem);}
}


（4）两个集合的差运算：将数组A中的元素逐一与数组B中的元素进行比较，把数组A与数组B不同的元素保存在数组C中，数组C便是集合A和集合B的差A-B。
　　C语言算法（线性表顺序结构实现）：

/**求集合的差集函数**/
void Differ_Sq(SqList La,SqList Lb,SqList &Lc){
int i;
ElemType elem;
Lc.length = 0;
for(i = 1; i <= La.length; i++){
elem = La.elem[i-1];
if(!LocateElem_Sq(Lb,elem,Equal))
ListInsert_Sq(Lc,Lc.length+1,elem);}
}


（5）集合的补运算：将数组E中的元素逐一与数组A中的元素进行比较，把不相同的元素保存到数组C中，数组C便是集合A关于集合E的补集。
　　求补集是一种特殊的集合差运算。
　　 C语言算法（线性表顺序结构实现）：

/**求集合的补集函数**/
void Comple_Sq(SqList La,SqList Lb,SqList &Lc,SqList &Ld){
int i;
ElemType elem;
Ld.length = 0;
Union_Sq(La,Lb,Lc);
for(i = 1; i <= Lc.length; i++){
elem = Lc.elem[i-1];
if(!LocateElem_Sq(La,elem,Equal))
ListInsert_Sq(Ld,Ld.length+1,elem);
}
}


二、执行效果图如下：






三、源程序如下：

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define LIST_INIT_SIZE 100 //初始表空间大小
#define LISTINCREMENT 10 //表长增量
typedef int Status; /**Status是函数类型，其值是函数结果状态代码，如OK等**/
typedef char ElemType; /*ElemType类型根据实际情况而定，这里假设为char*/
/**顺序表的定义**/
typedef struct{
ElemType *elem; /**储存空间基地址**/
int length; /**当前长度**/
int listsize; /**当前分配的储存容量（以sizeof(Elemtype)为单位）**/
}SqList;SqList La,Lb,Lc,Ld; /**定义全局变量**//**构造一个空的线性表L**/
Status InitList_Sq(SqList &L){
L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if(!L.elem) exit(OVERFLOW); /**储存分配失败**/
L.length = 0; /**空表长度为0**/
L.listsize = LIST_INIT_SIZE; /**初始储存容量**/
return OK;
} /**该函数的时间复杂度为O(n)**//**在顺序表的逻辑为i的位置插入新元素e的函数**/
Status ListInsert_Sq(SqList &L,int i,ElemType e){
ElemType *newbase,*p,*q;
//i的合法值为(1 <= i <= L.length_Sq(L) + 1)
//异常处理
if(i < 1 || i > L.length + 1) return ERROR;
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;
}/**创建一个线性表，即输入数据,根据集合定义：集合中的元素不能相等创建**/
void CreateList_Sq(SqList &L){
ElemType ch;
int inlist = FALSE,j;
while((ch) != '\n'){
scanf("%c",&ch);
for(j = 0; j < L.length; j++)
if(ch == L.elem[j]){
inlist = TRUE;
break;
}
else
inlist = FALSE;
if(!inlist && ch != '\n') ListInsert_Sq(L,L.length+1,ch);
}
}
/**判断两元素是否相等,若相等则返回TRUE;否则返回FALSE**/
Status Equal(ElemType a,ElemType b){
if(a == b) return TRUE;
else return FALSE;
}/**在顺序线性表L中查找第1个与e满足compare()的元素位序，若找到，则返回其在L中的位序，否则返回0**/
int LocateElem_Sq(SqList L,ElemType e,Status(* compare)(ElemType,ElemType)){
ElemType *p;
int i;
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;
} //该函数的时间复杂度为O(n)/*销毁线性表的函数*/
Status Clear_Sq(SqList &L){
ElemType elem;
free(L.elem);
L.elem = NULL;
return OK;
}/**打印顺序表函数**/
void Print_Sq(SqList L){
int i;
for(i = 0; i < L.length; i++)
printf("%2c",L.elem[i]);
if(L.length == 0) printf("该集合为空集"); 
printf("\n\t\t\t#\t此集合中的个数 n = %d\n\n",L.length);
}/**求集合的并集的函数**/
void Union_Sq(SqList La,SqList Lb,SqList &Lc){
int i;
ElemType elem;
Lc.length=0;
for(i = 0; i < La.length; i++)
Lc.elem[Lc.length++]=La.elem[i];
for(i = 1; i <= Lb.length; i++){
elem = Lb.elem[i-1];
if(!LocateElem_Sq(La,elem,Equal))
ListInsert_Sq(Lc,Lc.length+1,elem);}
}/**求集合的交集的函数**/
void Mix_Sq(SqList La,SqList Lb,SqList &Lc){
int i;
ElemType elem;
Lc.length = 0;
for(i = 1; i <= La.length; i++){
elem = La.elem[i-1];
if(LocateElem_Sq(Lb,elem,Equal))
ListInsert_Sq(Lc,Lc.length+1,elem);}
}/**求集合的差集函数**/
void Differ_Sq(SqList La,SqList Lb,SqList &Lc){
int i;
ElemType elem;
Lc.length = 0;
for(i = 1; i <= La.length; i++){
elem = La.elem[i-1];
if(!LocateElem_Sq(Lb,elem,Equal))
ListInsert_Sq(Lc,Lc.length+1,elem);}
}/**求集合的补集函数**/
void Comple_Sq(SqList La,SqList Lb,SqList &Lc,SqList &Ld){
int i;
ElemType elem;
Ld.length = 0;
Union_Sq(La,Lb,Lc);
for(i = 1; i <= Lc.length; i++){
elem = Lc.elem[i-1];
if(!LocateElem_Sq(La,elem,Equal))
ListInsert_Sq(Ld,Ld.length+1,elem);
}
}void Index_Sq(){
char s;
int l;
l = 1;InitList_Sq(La);
printf("\t\t\t|****** 请输入你的第一个集合：******|\n");
printf("\t\t\t");
CreateList_Sq(La);
printf("\t\t\t#\t集合A为");
Print_Sq(La); //实现表LA的操作
printf("\t\n\n");InitList_Sq(Lb);
printf("\t\t\t|****** 请输入你的第二个集合：******|\n");
printf("\t\t\t");
CreateList_Sq(Lb);
printf("\t\t\t#\t集合B为");
Print_Sq(Lb); //实现表LB的操作
printf("\t\n\n");InitList_Sq(Lc); //初始化表LC的操作
InitList_Sq(Ld); //初始化表Ld的操作
while(l){
printf("\t\t|******* 您可以选择a、b、c或者d执行以下操作 ******|\n\n");
printf("\t\t|************* a、进行集合的并运算 ***************|\n");
printf("\t\t|************* b、进行集合的交运算 ***************|\n");
printf("\t\t|************* c、进行集合的差运算 ***************|\n");
printf("\t\t|************* d、进行集合的补运算 ***************|\n");
printf("\t\t|************* e、重新建立两个集合 ***************|\n");
printf("\t\t\t");
scanf("%c",&s);
switch(s){
case 'a' :  Union_Sq(La,Lb,Lc);
printf("\t\t\t#\t集合A与集合B的并集为:");
Print_Sq(Lc); //实现表LA与表LB并集的操作
printf("\n");
break;
case 'b' : Mix_Sq(La,Lb,Lc);
printf("\t\t\t#\t集合A与集合B的交集为:");
Print_Sq(Lc); //实现表LA与表LB交集的操作
printf("\n");
break;
case 'c' : Differ_Sq(La,Lb,Lc);
printf("\t\t\t#\t集合A与集合B的差集为:");
Print_Sq(Lc); //实现表LA与表LB差集的操作
printf("\n");
break;
case 'd' : Comple_Sq(La,Lb,Lc,Ld);
printf("\t\t\t#\t集合A的补集为:");
Print_Sq(Ld); //实现表LA的补集操作
printf("\n");
break;
case 'e' : Clear_Sq(La);
Clear_Sq(Lb);
Clear_Sq(Lc);
Clear_Sq(Ld);getchar();
Index_Sq();break;
default  : printf("\t\t\t#\tenter data error!\n");
printf("\n");
}
printf("\t\t|**** 您是否还想继续计算。是请输入1，否请输入0 ****|\n");
printf("\t\t\t");
scanf("%d",&l);
getchar();
}//while语句判断是否继续
printf("\n\t\t|**************** 欢迎使用，谢谢！*****************|\n");
getchar();
}
int main(){
printf("\t\t|************* 欢迎使用集合操作运算器 ************|\n");
Index_Sq();return 0;
}

这篇关于利用线性表的顺序结构求集合的并、交、差、补（C语言实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1126376。

相关文章

SpringBoot集成Milvus实现数据增删改查功能

SpringBoot集成Milvus实现数据增删改查功能

《SpringBoot集成Milvus实现数据增删改查功能》milvus支持的语言比较多,支持python,Java,Go,node等开发语言,本文主要介绍如何使用Java语言,采用springboo... 目录1、Milvus基本概念2、添加maven依赖3、配置yml文件4、创建MilvusClient
阅读更多...
JS+HTML实现在线图片水印添加工具

JS+HTML实现在线图片水印添加工具

《JS+HTML实现在线图片水印添加工具》在社交媒体和内容创作日益频繁的今天,如何保护原创内容、展示品牌身份成了一个不得不面对的问题,本文将实现一个完全基于HTML+CSS构建的现代化图片水印在线工具... 目录概述功能亮点使用方法技术解析延伸思考运行效果项目源码下载总结概述在社交媒体和内容创作日益频繁的
阅读更多...
openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
OpenCV图像形态学的实现

OpenCV图像形态学的实现

《OpenCV图像形态学的实现》本文主要介绍了OpenCV图像形态学的实现,包括腐蚀、膨胀、开运算、闭运算、梯度运算、顶帽运算和黑帽运算,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起... 目录一、图像形态学简介二、腐蚀（Erosion）1. 原理2. OpenCV 实现三、膨胀China编程（
阅读更多...
通过Spring层面进行事务回滚的实现

通过Spring层面进行事务回滚的实现

《通过Spring层面进行事务回滚的实现》本文主要介绍了通过Spring层面进行事务回滚的实现,包括声明式事务和编程式事务,具有一定的参考价值,感兴趣的可以了解一下... 目录声明式事务回滚：1. 基础注解配置2. 指定回滚异常类型3. ​不回滚特殊场景编程式事务回滚：1. ​使用 TransactionT
阅读更多...
Android实现打开本地pdf文件的两种方式

Android实现打开本地pdf文件的两种方式

《Android实现打开本地pdf文件的两种方式》在现代应用中,PDF格式因其跨平台、稳定性好、展示内容一致等特点,在Android平台上,如何高效地打开本地PDF文件,不仅关系到用户体验,也直接影响... 目录一、项目概述二、相关知识2.1 PDF文件基本概述2.2 android 文件访问与存储权限2.
阅读更多...
使用Python实现全能手机虚拟键盘的示例代码

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景：会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作？今天我要分享的Pyth... 目录一、项目概述：不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求
阅读更多...
Spring Shell 命令行实现交互式Shell应用开发

Spring Shell 命令行实现交互式Shell应用开发

《SpringShell命令行实现交互式Shell应用开发》本文主要介绍了SpringShell命令行实现交互式Shell应用开发,能够帮助开发者快速构建功能丰富的命令行应用程序,具有一定的参考价... 目录引言一、Spring Shell概述二、创建命令类三、命令参数处理四、命令分组与帮助系统五、自定义S
阅读更多...
SpringBatch数据写入实现

SpringBatch数据写入实现

《SpringBatch数据写入实现》SpringBatch通过ItemWriter接口及其丰富的实现,提供了强大的数据写入能力,本文主要介绍了SpringBatch数据写入实现,具有一定的参考价值,... 目录python引言一、ItemWriter核心概念二、数据库写入实现三、文件写入实现四、多目标写入
阅读更多...
Android Studio 配置国内镜像源的实现步骤

Android Studio 配置国内镜像源的实现步骤

《AndroidStudio配置国内镜像源的实现步骤》本文主要介绍了AndroidStudio配置国内镜像源的实现步骤,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、修改 hosts，解决 SDK 下载失败的问题二、修改 gradle 地址，解决 gradle
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2