基于单链表实现集合的并交差运算实验报告

实验报告实验课程：数据结构实验项目：实验一集合的并交差运算专业：计算机科学与技术班级：姓名：学号：指导教师：目录一、问题定义及需求分析（1）实验目的（2）实验任务（3）需求分析二、概要设计：(1)抽象数据类型定义(2)主程序流程(3) 模块关系三、详细设计(1)数据类型及存储结构(2)模块设计四、调试分析(1)调试分析(2)算法时空分析(3)经验体会五、使用说明(1)程序使用说明六、测试结果(1)运行测试结果截图七、附录(1)源代码一、问题定义及需求分析（1）实验目的设计一个能演示集合的并、交、差运算程序。

（2）实验任务1)采用顺序表或链表等数据结构。

2)集合的元素限定为数字和小写英文字母。

（3）需求分析：输入形式为:外部输入字符串；输入值限定范围为:数字和小写英文字母；输出形式为：字符集；程序功能:计算两个集合的交、并、差以及重新输入集合功能；二、概要设计：(1)抽象数据类型定义：线性表(2)主程序流程：调用主菜单函数初始化两个线性表作为集合给两个集合输入数据输出集合数据元素信息另初始化两个线性表创建选择功能菜单界面通过不同选项调用不同功能函数在每个功能函数里面加结束选择功能，实现循环调用功能菜单计算完毕退出程序；（3）模块关系：主菜单差运算并运算交运算结束/返回结束三、详细设计抽象数据类型定义：typedef struct{ElemType *elem;int length;int listsize;}SqList;存储结构：顺序表；模块1-在顺序表的逻辑为i的位置插入新元素e的函数；算法如下：/**在顺序表的逻辑为i的位置插入新元素e的函数**/Status ListInsert_Sq(SqList &L,int i,ElemType e){ElemType *newbase,*p,*q;if(i < 1 || i > L.length + 1) return 0; //i的合法值为(1 <= i <= L.length_Sq(L) + 1)if(L.length >= L.listsize){ //当前储存空间已满，增加分配newbase = (ElemType *)realloc(L.elem,(L.listsize + LISTINCREMENT) * sizeof(ElemType));if(!newbase) exit(-1); //储存分配失败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; //表长加1return 1;}模块二在顺序线性表L中查找第1个与e满足compare()的元素位序，若找到，则返回其在L中的位序，否则返回0算法如下：/**在顺序线性表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; //从表L中的第一个元素开始与e比较，直到找到L中与e相等的元素时返回该元素的位置if(i <= L.length) return i; //若i的大小小于表长，则满足条件返回ielsereturn 0; //否则，i值不满足条件，返回0}模块三集合交运算算法如下：/**求集合的交集的函数**/void Mix_Sq(SqList La,SqList Lb,SqList &Lc){int i;ElemType elem;Lc.length = 0; //将表Lc的长度设为0for(i = 1; i <= La.length; i++){ //依次查看表La的所有元素elem = La.elem[i-1]; //将表La中i位置的元素赋值给elemif(LocateElem_Sq(Lb,elem,Equal)) //在表Lb中查找是否有与elem相等的元素ListInsert_Sq(Lc,Lc.length+1,elem); //将表La与Lb中共同的元素放在Lc中}}模块四集合并运算算法如下：/**求集合的并集的函数**/void Union_Sq(SqList La,SqList Lb,SqList &Lc){int i;ElemType elem;Lc.length=0; //将表Lc的长度初设为0for(i = 0; i < La.length; i++) //先将表La的元素全部复制到表Lc中Lc.elem[Lc.length++]=La.elem[i];for(i = 1; i <= Lb.length; i++){elem = Lb.elem[i-1]; //依次将表Lb的值赋给elemif(!LocateElem_Sq(La,elem,Equal)) //判断表La中是否有与elem相同的值ListInsert_Sq(Lc,Lc.length+1,elem); //若有的话将elem放入表Lc中}}模块五集合的差运算算法如下：/**求集合的差集函数**/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]; //把表La中第i个元素赋值给elem if(!LocateElem_Sq(Lb,elem,Equal)) //判断elem在表Lb中是否有相同的元素ListInsert_Sq(Lc,Lc.length+1,elem); //若有，则把elem放入表Lc中，否则，就不存放}for(i = 1; i <= Lb.length; i++){elem = Lb.elem[i-1]; //把表Lb中第i个元素赋值给elemif(!LocateElem_Sq(La,elem,Equal)) //判断elem在表La中是否有相同的元素ListInsert_Sq(Lc,Lc.length+1,elem); //若有，则把elem放入表Lc中，否则，就不存放}}四、调试分析问题分析及解决：首先，在编写程序时没有设置线性表的初始长度，导致集合元素输入错误；然后通过#define LIST_INIT_SIZE 100和#define LISTINCREMENT 10解决；时空分析：int LocateElem_Sq(SqList L,ElemType e,Status(* compare)(ElemType,ElemType))时间复杂度为O(n);Status ListInsert_Sq(SqList &L,int i,ElemType e) 时间复杂度为O(n);void Union_Sq(SqList La,SqList Lb,SqList &Lc) 时间复杂度为O(m*n);void Mix_Sq(SqList La,SqList Lb,SqList &Lc) 时间复杂度为O(m*n);void Differ_Sq(SqList La,SqList Lb,SqList &Lc) 时间复杂度为O(2*m*n);改进设想：当同时求两个以上的结合间的运算是需要先进性两个集合间的运算，然后在于另外的集合进行运算；若要同事进行多个集合的运算需要建立多个顺序表；经验体会：顺序表使用起来比较简单，但长度不可随意变化，适用于大量访问元素，而不适用于大量增添和删除元素；在内存中存储地址连续；五、使用说明第一步：点击运行按钮；第二步: 根据提示输入集合A(可以连续输入，只限输入小写字母和数字)；第三步：程序自动显示输入结果；第四步：输入集合B（同第二步）；第五步：跳出主菜单界面；第六步：根据选项输入对应运算项的数字序号；第七步：显示运算结果，并可继续进行选择运算还是退出；第八步：若继续运算则返回主菜单，否则退出；第九步：循环第六、七、八步，直至选择退出；六、测试结果输入界面：并运算结果：交运算结果：差运算结果：重新建立集合并运算：七、附录#include<stdio.h>#include<stdlib.h>#define LIST_INIT_SIZE 100//初始表空间大小#define LISTINCREMENT 10//表长增量typedef int Status; /**Status是函数类型**/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(-1); /**储存分配失败**/L.length = 0;L.listsize = LIST_INIT_SIZE;/**初始储存容量**/return 1;}/**在顺序表的逻辑为i的位置插入新元素e的函数**/Status ListInsert_Sq(SqList &L,int i,ElemType e){ElemType *newbase,*p,*q;if(i < 1 || i > L.length + 1)return 0;if(L.length >= L.listsize)//当前储存空间已满，增加分配{newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase) exit(-1);//储存分配失败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;return 1;}/**创建一个线性表，输入数据**/void CreateList_Sq(SqList &L){ElemType ch='\0';int inlist =0,j;while((ch) != '\n'){scanf("%c",&ch);//输入数据for(j = 0; j < L.length; j++)if(ch == L.elem[j])//判断表L中是否有与ch相等的元素{inlist = 1; //若有，则inlist置1break; //跳出本轮循环}elseinlist =0; //否则inlist为0if(!inlist && ch != '\n')//若inlist为0且ch不为”\n”ListInsert_Sq(L,L.length+1,ch);//则将ch存入表L中}}/*判断两元素是否相等,若相等则返回1;否则返回0*/Status Equal(ElemType a,ElemType b){if(a == b)return 1;//相等，返回1elsereturn 0;//否则，返回0}/*在顺序线性表L中查找第1个与e满足compare()的元素位序，若找到，则返回其在L中的位序，否则返回0*/int LocateElem_Sq(SqList L,ElemType e,Status(* compare)(ElemType,ElemType)) {ElemType *p;int i;i = 1;p = L.elem;//p的初值为第1个元素的储存位置while(i <= L.length && !(* compare)(*p++,e))//循环查找表L找出其中与e相等的元素的位置++i;if(i <= L.length)//若i小于表长return i;//则i满足条件，返回i的值elsereturn 0;//否则返回0}/*销毁线性表的函数*/Status Clear_Sq(SqList &L){ElemType elem;free(L.elem);L.elem = NULL;return 1;}/*打印顺序表函数*/void Print_Sq(SqList L){int i;for(i = 0; i < L.length; i++)printf("%2c",L.elem[i]);//通过for循环将表元素全部输出if(L.length == 0) printf("空集");//若表长为0，则输出空表printf("\n\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; //将表Lc的长度初设为0for(i = 0; i < La.length; i++) //先将表La的元素全部复制到表Lc中Lc.elem[Lc.length++]=La.elem[i];for(i = 1; i <= Lb.length; i++){elem = Lb.elem[i-1]; //依次将表Lb的值赋给elemif(!LocateElem_Sq(La,elem,Equal)) //判断表La中是否有与elem 相同的值ListInsert_Sq(Lc,Lc.length+1,elem); //若有的话将elem放入表Lc中}}/*求集合的交集的函数*/void Mix_Sq(SqList La,SqList Lb,SqList &Lc){int i;ElemType elem;Lc.length = 0; //将表Lc的长度设为0for(i = 1; i <= La.length; i++){ //依次查看表La的所有元素elem = La.elem[i-1]; //将表La中i位置的元素赋值给elemif(LocateElem_Sq(Lb,elem,Equal)) //在表La中查找是否有与elem相等的元素ListInsert_Sq(Lc,Lc.length+1,elem); //将表La与Lb中共同的元素放在Lc 中}}/*求集合的差集函数*/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]; //把表La中第i个元素赋值给elemif(!LocateElem_Sq(Lb,elem,Equal)) //判断elem在表Lb中是否有相同的元素ListInsert_Sq(Lc,Lc.length+1,elem);//若有，则把elem放入表Lc中，否则，就不存放}for(i = 1; i <= Lb.length; i++){elem = Lb.elem[i-1]; //把表Lb中第i个元素赋值给elemif(!LocateElem_Sq(La,elem,Equal)) //判断elem在表La中是否有相同的元素ListInsert_Sq(Lc,Lc.length+1,elem); //若有，则把elem放入表Lc中，否则，就不存放}}void Index_Sq(){//主菜单函数char s;int l=1;InitList_Sq(La);//初始化表Laprintf("\n\t\t 请输入集合A:");CreateList_Sq(La);//创建表Laprintf("\t\t\t集合A为");Print_Sq(La);printf("\n\n");InitList_Sq(Lb);//初始化表Lbprintf("\t\t 请输入集合B:");CreateList_Sq(Lb);//创建表Lbprintf("\t\t\t集合B为");Print_Sq(Lb);printf("\n\n");InitList_Sq(Lc);//初始化表LcInitList_Sq(Ld);//初始化表Ldwhile(l){printf("\t\t ******* 请输入您的操作选项1、2、3、4. ****** \n\n");printf("\t\t 1、进行集合的并运算\n");printf("\t\t 2、进行集合的交运算\n");printf("\t\t 3、进行集合的差运算\n");printf("\t\t 4、重新建立两个集合\n");printf("\t\t\t");scanf("%c",&s);switch(s){case '1' : system("cls");Union_Sq(La,Lb,Lc);//调用集合的并运算函数printf("\t\t\t集合A与集合B的并集为:");print_Sq(Lc);printf("\n");break;case '2' :system("cls");Mix_Sq(La,Lb,Lc);//调用集合的交集运算函数printf("\t\t\t集合A与集合B的交集为:");print_Sq(Lc);printf("\n");break;case '3' : system("cls");Differ_Sq(La,Lb,Lc);//调用集合的差集运算函数printf("\t\t\t集合A与集合B的差集为:");print_Sq(Lc);printf("\n");break;case '4' :system("cls");Clear_Sq(La);//销毁表LaClear_Sq(Lb);//销毁表LbClear_Sq(Lc);//销毁表LcClear_Sq(Ld);//销毁表Ldgetchar();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();system("cls");}printf("\n\t\t**************** 谢谢使用！*****************\n");}int main(){printf("\t\t************* 欢迎使用集合操作运算器************\n");Index_Sq();//调用主菜单函数return 0;}。

单链表的实验报告单链表的实验报告引言：单链表是一种常用的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

在本次实验中，我们将学习如何使用单链表来实现一些基本的操作，并通过实验验证其功能和效率。

一、实验目的本次实验的主要目的是掌握单链表的基本概念和操作方法，包括插入、删除、查找等操作，并通过实际操作来验证其正确性和效率。

二、实验过程1. 单链表的定义和初始化首先，我们需要定义一个单链表的结构，并初始化一个空链表。

链表的结构可以使用C语言中的结构体来表示，其中包含一个数据域和一个指向下一个节点的指针。

2. 插入操作在已有链表中插入一个新的节点，可以分为两种情况：在链表头部插入和在链表中间插入。

我们可以通过修改指针的指向来实现插入操作。

3. 删除操作删除链表中的一个节点，同样可以分为两种情况：删除头节点和删除中间节点。

删除操作需要注意指针的重新连接，以防止链表断裂。

4. 查找操作在链表中查找指定的元素，可以通过遍历链表的方式来实现。

从链表头开始，依次比较节点的数据域，直到找到目标元素或者遍历到链表尾部。

5. 其他操作在实际应用中，还可以对链表进行排序、逆序、合并等操作，这些操作都可以通过适当的算法来实现。

三、实验结果通过实际操作，我们验证了单链表的各种操作方法的正确性和效率。

在插入、删除和查找操作中，链表的时间复杂度为O(n)，其中n为链表的长度。

而在其他操作中，时间复杂度则根据具体算法的实现方式而定。

四、实验总结通过本次实验，我们深入了解了单链表的结构和操作方法，并通过实际操作来验证了其功能和效率。

单链表作为一种常用的数据结构，在实际应用中具有广泛的用途，例如链表可以用来实现栈、队列等其他数据结构，也可以用于解决一些实际问题，如链表的反转、环的检测等。

总之，掌握单链表的基本概念和操作方法对于学习和理解数据结构具有重要意义。

通过实验的方式，我们不仅能够加深对单链表的理解，还能够提高编程能力和解决实际问题的能力。

江西理工大学软件学院实验报告系（部）机电工程系课程数据结构专业班级11机械电子（2）班姓名杨锦其学号11212203指导教师刘廷苍实验题目：用单链表实现集合的操作一．实验目的用有序单链表实现集合的判等，交，并和差等基本运算。

二．实验内容（1）对集合中的元素用有序单链表进行存储；（2）实现交，并，差等基本运算时，不能另外申请存储空间；（3）充分利用单链表的有序性，要求算法有较好的时间性能。

三．设计与代码1. 理论知识集合是由互不相同的元素构成的一个整体，在集合中，元素之间可以没有任何关系，所以，集合也可以作为线性表处理。

用单链表实现集合的操作，需要注意集合中元素的唯一性，即在单链表中不存在值相同的结点。

本实验要求采用有序单链表，还要注意单链表的有序性。

2. 算法设计（1）判断集合相等算法：两个集合相等的条件是不仅长度相同，而且各个对应的元素也相等。

由于用有序单链表表示集合，所以只要同步扫描两个单链表，若从头至尾每个对应的元素都相等，则表明两个集合都相等。

template<class DataType>bool IsEqual(linklist<DataType> &list1,linklist<DataType> &list2){int i1=1,i2=1;//分别表示链表list1和list2的位置//当list1不为'\0'时循环if(list1.GetLength()!=list2.GetLength()){ return false; }else{while(list1.Get(i1)!='\0'){while(list2.Get(i2)!='\0'){if(list1.Get(i1)!=list2.Get(i2)){i2++;}else{break;}}//whileif(list2.Get(i2)!='\0'){ i1++;i2=1; }else{ return false;}}//whilereturn true;}//else}（2）求集合交集算法：根据集合的运算规则，集合A交B中包含所有既属于集合A又属于集合B的元素，因此需查找单链表A和B中的相同元素并保留在单链表A中。

基于单链表实现集合的并交差运算实验报告一 实验题目: 基于单链表实现集合的并交差运算二 实验要求:2.2:编写一个程序，实现顺序表的各种基本运算(1)初始化单链表h ；(2)依次采用尾插法插入a,b,c,d,e 元素;(3)输出单链表h(4)输出单链表h 的长度(5)判断单链表h 是否为空(6)输出单链表h 的第三个元素(7)输出元素在a 的位置(8)在第4个元素位置上插入f 元素(9)输出单链表h(10)删除L 的第3个元素(11)输出单链表(12)释放单链表2.2:编写一个程序，采用单链表表示集合(集合中不存在重复的元素),并将其按照递增的方式排序，构成有序单链表，并求这样的两个集合的并,交和差。

三 实验内容:3.1 线性表的抽象数据类型:ADT List{数据对象;D=}0,,...,2,1,ElemS et |{≥=∈n n i a a i i数据关系:R1=},...,2,,|,{11n i D a a a a i i i i =∈><--基本操作：InitList(&L)操作结果;构造一个空的线性表LDestroyList(&L)初始条件：线性表L已存在操作结果：销毁线性表LClearList(&L)初始条件：线性表L已存在操作结果：将L置为空表ListEmpty(L)初始条件：线性表已存在操作结果：若L为空表，则返回TRUE，否则返回FALSEListLength(L)初始条件：线性表已存在操作结果：返回L中数据元素的个数GetElem(L,i)初始条件:线性表已存在，1<=i<=ListLength(L)操作结果：用e返回L中第i个数据元素的值LocateElem(L,i,e)初始条件：线性表已存在，用循环遍历整个线性表，如果e与线性表中的元素相同；操作结果：用此时的i+1返回该元素在线性表的位序ListInsert(&L,i,e)初始条件：线性表存在，1<=i<=ListLength(L)+1;操作结果：在L中第i个位置之前插入新的数据元素,e,L的长度加1。

实验报告题目：集合的并、交和差运算班级：13信息管理姓名：刘学号：20130403012 完成日期：20,11一、需求分析1［问题描述］编制一个能演示执行集合的并、交和差运算的程序。

2［基本要求］（1）集合的元素限定为整数。

（2）用链式存储结构完成。

3．测试数据set1={ 1 2 3 4 5 },set2={ 3 4 5 6 7 }set1∪set2={ 1 2 3 4 5 6 7 };set1∩set2={ 3 4 5 }set1-set2={ 1 2 }二、编码实现1．存储类型typedef struct LNode{int data;struct LNode *next;}LNode,*LinkList;2．部分函数的伪码算法//构造一个集合void CreateList_L(LinkList &L){LinkList p;int n,i;printf("请输入元素个数：\n");scanf("%d",&n);L=(LinkList)malloc(sizeof(LNode));L->next=NULL;printf("请一次输入各个元素：\n");for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));scanf("%d",&p->data);p->next=L->next;L->next=p;}}//取出数据值int get_data(LinkList h){int t;t=h->data;return t;}//删除与t相同的节点LinkList del(LinkList L1,int t){LinkList p1,p2;p1=L1->next;while(t!=p1->data&&p1->next!=NULL){p2=p1,p1=p1->next;}if(t==p1->data){if(p1==L1->next)L1->next=p1->next;elsep2->next=p1->next;}return L1;}//打印集合void printf_L(LinkList &L){LinkList h;h=L->next;while(h){printf(" %d ",h->data);h=h->next;}}//集合排序void sort(LinkList &L){LinkList p=L->next,q,r;if(p){r=p->next;p->next=NULL;p=r;}while(p){r=p->next;q=L;while(q->next!=NULL&&q->next->data<p->data) q=q->next;p->next=q->next;q->next=p;p=r;}}//集合并集void combine(LinkList &L1,LinkList L2){LinkList p,h;p=L1;while(p->next){p=p->next;}p->next=L2->next;sort(L1);p=L1->next;while(p->next){if(p->data==p->next->data){h=p->next;p->next=h->next;free(h);}elsep=p->next;}}//集合的差void differ(LinkList L1,LinkList L2){int t;LinkList h;h=L2->next;while(h){t=get_data(h);L1=del(L1,t);h=h->next;}}//交集void intersectLink(LinkList L1,LinkList L2) {LinkList p,h;p=L1;while(p->next){p=p->next;}p->next=L2->next;sort(L1);p=L1;while(p->next->next){h=p->next->next;if(p->next->data!=h->data){p->next=h;h=h->next;}elsep=p->next;}p->next=NULL;}三、调试分析1，说实话，自己根本不会做，参考网上的资料都做不出来；2，自己做的程序，没有任何错误，但就是不能运行；3，对链表的认识不够深入，不知道如何构造链表，以及实现各种操作；四、测试结果set1={ 1 2 3 4 5 },set2={ 3 4 5 6 7 }set1∪set2={ 1 2 3 4 5 6 7 };set1∩set2={ 3 4 5 }set1-set2={ 1 2 }五．附录#include<stdlib.h>typedef struct LNode{int data;struct LNode *next;}LNode,*LinkList;//构建集合函数void CreateList_L(LinkList &L){LinkList p;int n,；i;printf("请输入元素个数：\n");scanf("%d",&n);L=(LinkList)malloc(sizeof(LNode));L->next=NULL;printf("请一次输入各个元素：\n");for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));scanf("%d",&p->data);p->next=L->next;L->next=p;}}//获取数据函数int get_data(LinkList h){int t;t=h->data;return t;}//删除函数LinkList del(LinkList L1,int t){LinkList p1,p2;p1=L1->next;while(t!=p1->data&&p1->next!=NULL){p2=p1,p1=p1->next;}if(t==p1->data){if(p1==L1->next)L1->next=p1->next;elsep2->next=p1->next;}return L1;}//打印函数void printf_L(LinkList &L){LinkList h;h=L->next;while(h){printf(" %d ",h->data);h=h->next;}}//排序void sort(LinkList &L){LinkList p=L->next,q,r;if(p){r=p->next;p->next=NULL;p=r;}while(p){r=p->next;q=L;while(q->next!=NULL&&q->next->data<p->data) q=q->next;p->next=q->next;q->next=p;p=r;}}//并集void combine(LinkList &L1,LinkList L2)LinkList p,h;p=L1;while(p->next){p=p->next;}p->next=L2->next;sort(L1);p=L1->next;while(p->next){if(p->data==p->next->data){h=p->next;p->next=h->next;free(h);}elsep=p->next;}}//求差void differ(LinkList L1,LinkList L2) {int t;LinkList h;h=L2->next;while(h){t=get_data(h);L1=del(L1,t);h=h->next;}}//交集void intersect(LinkList L1,LinkList L2) {LinkList p,h;p=L1;while(p->next){p=p->next;}p->next=L2->next;sort(L1);p=L1;while(p->next->next){h=p->next->next;if(p->next->data!=h->data){p->next=h;h=h->next;}elsep=p->next;}p->next=NULL;}//主函数int main(){LinkList L1,L2;int t;printf("求集合交集请按1\n求集合并集请按2\n请集合之差请按3\n");scanf("%d",&t);while(t!=0){switch(t){case 1:CreateList_L(L1);CreateList_L(L2);intersect(L1,L2);sort(L1);printf_L(L1);break;case 2:CreateList_L(L1);CreateList_L(L2);combine(L1,L2);sort(L1);printf_L(L1);break;case 3:CreateList_L(L1);CreateList_L(L2);differ(L1,L2);sort(L1);printf_L(L1);break;default :printf("error\n");}scanf("%d",&t);}return 0;}11。

单链表求集合的并、交和差运算单链表是一种常用的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

在计算机科学中，我们经常需要对集合进行操作，包括求并集、交集和差集。

在本文中，我们将介绍如何使用单链表来实现这些集合操作。

我们需要定义一个单链表的数据结构。

每个节点包含一个数据元素和一个指向下一个节点的指针。

我们可以使用类来实现这个数据结构，例如：```class Node:def __init__(self, data):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = None```接下来，我们需要实现集合的并、交和差运算。

首先是并运算，它将两个集合中的所有元素合并为一个新的集合。

我们可以使用两个指针分别遍历两个链表，将两个链表中的元素逐个比较，并将不重复的元素添加到结果链表中。

具体代码如下：```def union(l1, l2):result = LinkedList()p1 = l1.headp2 = l2.headwhile p1 is not None:result.append(p1.data)p1 = p1.nextwhile p2 is not None:if not result.contains(p2.data):result.append(p2.data)p2 = p2.nextreturn result```接下来是交运算，它将两个集合中共有的元素提取出来组成一个新的集合。

同样地，我们可以使用两个指针分别遍历两个链表，将相同的元素添加到结果链表中。

具体代码如下：```def intersection(l1, l2):result = LinkedList()p1 = l1.headwhile p1 is not None:if l2.contains(p1.data):result.append(p1.data)p1 = p1.nextreturn result```最后是差运算，它将第一个集合中不属于第二个集合的元素提取出来组成一个新的集合。

《数据结构》实验报告题目：集合的并、交、差专业：信息管理与信息系统班级：17信管3组别：一组长：胡源完成日期：2018年10月23 日评分依据及结果代码分工情况实验报告分工情况一、需求分析1．本演示程序中，集合的元素限定为小写字母和数字，集合的大小小于MAXSIZE=100(可以通过宏定义来动态改变大小)。

集合的输入形式为以一个“回车符”为结束标志的字符串，串中字符顺序不限。

程序能自动过滤出现的重复字符和非法字符，且经过过滤的集合中，数字始终在字母前面。

输出运算结果字符中不含重复字符或非法字符。

2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据（除去非法字符）和运算结果显示在其后。

3．程序的执行命令包括：1）构造集合1；2）构造集合2；3）求并集；4）求交集；5）求差集；6）程序结束。

“构造集合1”和“构造集合2”时，需要以字符串的形式链入集合元素。

4．测试数据（1）S et1=”abcdefg”，Set1=”123456”（未赋值时的原始集合）Set2∩Set2=”123456abcdefg”, Set2∩Set2=””,Set2-Set2=”abcdefg”（2）S et1=”1314524huyuan”，Set1=”748fuck”Set2∩Set2=”12345678acfhknuy”, Set2∩Set2=” 4u”,Set2-Set2=”1235ahny”（3）S et1=”1314524huyuan数据结构”，Set1=”958abcd考研”Set2∩Set2=”1234589abcdhnuy”, Set2∩Set2=” 5a”,Set2-Set2=”1234hnuy”二、概要设计用有序链表表示集合来使程序达到预期功能。

因此，需要一个抽象数据类型：有序集合。

1.有序集合的抽象数据类型定义为：ADT OrderedList{数据对象：D={a|a为数字（1-9）或字母（a-z）}数据关系：R={<a[i]-1,a[i]>|a[i-1],a[i]∈D，a[i-1]<a[i],i为自然数}}基本操作：InitList(&L)操作结果：构造空的有序链集合LocateElem(L, e, &p)。

用单链表实现集合的并，交，差运算1．需求分析求两个字符集合的交、并、差：（1）输入字符的范围：小写字母a,b,…，y,z（2）输出的形式：字符集合，按从a到z的顺序排列（3）程序所能达到的功能：分别求两个字符集合的交、并、差2．系统设计1．主程序的流程与调用关系：（1）调用CreateList_L(&L,n)函数建立单链表La和Lb；（2）调用SortList_L(&L)函数对La和Lb排序；（3）选择要进行的操作，若为1则调用Intersect_L(La,Lb,&Lc)函数求交；若为2则调用UnionList_L（&La,&Lb,&Lc）函数求并；若为3则调用Difference_L(La,&Lb)函数求差；（4）调用PrintList(L)函数输出结果3．调试分析（1）．调试过程中遇到的问题：在求并与交时去不掉重复出现的字母，如set1=”magazine” , set2 = “paper”，求出set1 ∪set2=” aa egimnprz”，出现了两个a。

原来想在求并/交的过程中把重复的字母去掉，但没有成功，所以另外编了一个函数Quchong(LinkList &Lc)专门对求完并/交的字符集合去重。

（2）算法的时间复杂度分析：求交：T(n)=O(mn);求并：T(n)=O(n);求差：T(n)=O(mn);（3）改进思想：求交的算法改进后时间复杂度可以为O(n)，在求交之前已经对两个字符集合排过序了，因此不必每次都从头到尾进行查找。

4．测试结果⑴set1=”magazine” , set2 = “paper”，求set1 ∩set2 ：⑵set1=”paper” , set2 = “magazine”，求set1 ∪set2 ：⑶set1=”magazine” , set2 = “paper”，求set1 - set2 ：（4）无效选择：5、用户手册1. 按屏幕提示输入字符串1的长度，回车后输入字符串1；2. 按屏幕提示输入字符串2的长度，回车后输入字符串2；3. 按屏幕提示选择操作，1、2、3是有效选择，否则提示“选择无效！”；4. 输出结果，按任意键退出6、附录源程序：#include<stdio.h>#include<stdlib.h>typedef struct LNode{char data;struct LNode *next;}LNode,*LinkList;void CreateList_L(LinkList &L,int n){int i;char m;LinkList p,rear;L=rear=(LinkList)malloc(sizeof(LNode)); L->next=NULL;scanf("%c",&m);for(i=1;i<=n;i++){p=(LinkList)malloc(sizeof(LNode)); scanf("%c",&p->data);p->next=NULL;rear->next=p;rear=p;}}void SortList_L(LinkList &L){ //排序int temp;LinkList p,q,small;for(p=L->next;p->next!=NULL;p=p->next) {small=p;for(q=p->next;q;q=q->next)if(q->data<small->data)small=q;if(small!=p){temp=p->data;p->data=small->data;small->data=temp;}}}void PrintList(LinkList L){ //输出LinkList p;p=L->next;do{printf("%c,",p->data);p=p->next;}while(p);printf("\n");}void Quchong(LinkList &Lc){ //去重LinkList pc,p,q;for(pc=Lc->next;pc;pc=pc->next)for(p=pc->next;p;p=p->next){if(pc->data==p->data){q=p;p=p->next;pc->next=p;free(q);}}}void Intersect_L(LinkList La,LinkList Lb,LinkList &Lc){ //求交LinkList pa,pb,pc,p;Lc=pc=(LinkList)malloc(sizeof(LNode));Lc->next=NULL;for(pb=Lb->next;pb;pb=pb->next){pa=La->next;do{if(pa->data==pb->data){p=(LinkList)malloc(sizeof(LNode));p->data=pa->data;p->next=NULL;pc->next=p;pc=p;}pa=pa->next;}while(pa);}Quchong(Lc);}void UnionList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ //求并LinkList pa,pb,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->data<pb->data){pc->next=pa;pc=pa;pa=pa->next;}else if(pa->data==pb->data){pc->next=pa;pc=pa;pa=pa->next;pb=pb->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;free(Lb);Quchong(Lc);}void Difference_L(LinkList La,LinkList &Lb){ //求差LinkList Lc,pa,pc,p,q;Intersect_L(La,Lb,Lc);Quchong(La);for(pa=La,p=La->next;p;pa=pa->next,p=p->next)for(pc=Lc->next;pc;pc=pc->next){if(p->data==pc->data){q=p;p=p->next;pa->next=p;free(q);}}free(Lc);}void main(){LinkList La,Lb,Lc;int n;printf("请输入字符串1的长度：");scanf("%d",&n);CreateList_L(La,n);SortList_L(La);printf("请输入字符串2的长度：");scanf("%d",&n);CreateList_L(Lb,n);SortList_L(Lb);printf("选择操作：1 求交2 求并3 求差\n");scanf("%d",&n);switch(n){case 1:Intersect_L(La,Lb,Lc);printf("\n字符串1与2的交："); PrintList(Lc);break;case 2:UnionList_L(La,Lb,Lc);printf("\n字符串1与2的并："); PrintList(Lc);break;case 3:Difference_L(La,Lb);printf("\n字符串1与2的差："); PrintList(La);break;default:printf("选择无效！");break;}}。

c语言数据结构单链表的交并差集运算实现(总7页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--数据结构上机实验课后练习报告姓名：冯天明学号：班级：通信1412015年9月28日星期一实验五：实现A 、B两个单链表表示的集合的交集、并集和差集实验代码：#include<>#include<>#define OK 0#define ERROR -1#define OVERFLOW -2typedef int ElemType;typedef struct LNode{ElemType data; //定义数据域LNode *next; //定义指针域}LNode,*LinkList;void InitList(LinkList *L) //创建链表头{*L = ( LinkList )malloc( sizeof(LNode) );if(!L) exit(OVERFLOW); //头结点内存申请失败(*L)->next = NULL;}void DerstorList(LinkList &L) //清空链表{LinkList p;while(L->next){p = L->next;L->next = p->next;free(p);}}void ClearList(LinkList *L,int n) //初始化链表{LinkList p ;int i;for(i = 0;i<n;i++){p = (LinkList )malloc(sizeof(LNode)); //生成新节点scanf("%d",&(p)->data);p->next = (*L)->next; //头插法( *L)->next = p;}}void InserList(LinkList *L,ElemType e) //头插法插入数据{LinkList p;p = (LinkList )malloc(sizeof( LNode ));p->data = e;p->next = (*L)->next; //头插法( *L)->next = p;}void DisplaList(LinkList L) //输出链表{LinkList head;head = L->next;if(head==NULL)printf("集合为空！\n");while(head) //遍历链表{printf("%4d",head->data); //输出节点信息head = head->next;}printf("\n");}int isPresent(LinkList L,ElemType data) //判断链表中是否已经存在data该元素{LinkList p = L->next;while(p) //遍历链表，查找是否存在data值{if( p->data == data )return 1;p = p->next;}return 0;}/*************求两个链表的交集**************/int Intersection(LinkList L1,LinkList L2,LinkList L3){LinkList p,q;p = L1->next;q = L2->next;while( p ){while( q ){//判断两链表的元素是否相当，并且存入的链表中不存在该元素即可存入if(p->data == q->data && !isPresent(L3,p->data)){InserList(&L3,p->data);}q = q->next;}q = L2->next; //复位p = p->next;}return OK;}/************求链表的并集************/void Union(LinkList L1,LinkList L2,LinkList L3){LinkList p,q;p = L1->next;q = L2->next;DerstorList(L3); //清空链表，重新存入数据while( p ){//如果p中的元素不在并集链L3中，防止L1中有重复元素if(!isPresent(L3,p->data))InserList(&L3,p->data); //插入元素p = p->next;}p = L1->next;while(q){if(!(isPresent(L3,q->data))) //q->data元素不存在并集表中，则插入{InserList(&L3,q->data); //把L2表中的元素插入}q = q->next;}}/************求链表的差集************/void Subtraction(LinkList L1,LinkList L2,LinkList L3){LinkList p,q;p = L1->next;q = L2->next;DerstorList(L3);while(p){if(!(isPresent(L2,p->data))) //如果L2中不存在data值，即为L1-L2差集InserList(&L3,p->data);p = p->next;}}void main(){LinkList L1,L2,L3;int number;InitList(&L1); //创建空链表InitList(&L2);InitList(&L3); //存储交并差集的链表printf("请输入链表L1的元素个数:");scanf("%d",&number);printf("输入链表L1的内容:\n");ClearList(&L1,number); //初始化链表L1printf("请输入链表L2的元素个数:");scanf("%d",&number);printf("输入链表L2的内容:\n");ClearList(&L2,number); //初始化链表L2printf("L1：");DisplaList(L1);printf("L2：");DisplaList(L2);printf("L1 ∩ L2为(交集):");Intersection(L1,L2,L3); //求链表L1与L2的交集DisplaList(L3);printf("L1 ∪ L2为(并集):");Union(L1,L2,L3); //求链表L1 L2的并集DisplaList(L3);printf("L1 - L2(补集):");Subtraction(L1,L2,L3); //求链表L1 L2 的差集（补集）DisplaList(L3);}。

软件技术基础实验一——单链表的各种基本运算的实现一、实验题目编写一个程序，实现单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能：（1）初始化单链表（2）依次采用尾插法插入a,b,c,d,e元素（3）输出单链表（4）在第四个元素位置上插入f元素（5）删除该单链表的第三个元素二、实验目的1、理解单链表的概念及结构特点；2、掌握单链表的基本操作：查找、插入、删除等运算在链接存储结构上的运算。

三、调试通过并正确执行给定功能要求的实验代码#include "stdafx.h"#include<malloc.h>#include<iostream.h>struct link{char data;link *next;};link *rcreat(link *head,char x) //尾插法建立单链表{link *s,*r;r=head;s=new link;s->data=x;r->next=s;r=s;r->next=NULL;return r;}link *get(link *head,int i) //查找第i个元素，返回其地址{int j;link *p;j=1;p=head->next ;while((j<i-1)&&(p!=NULL)){j++;p=p->next;}return p;}void insert(link *head,int num,char y) //元素y之后插入x {link *p,*s;s=new link;s->data=y;if(head->next==NULL){head->next=s;s->next=NULL;}p=get(head,num);if(p==NULL) cout<<"插入位置非法";else{s->next=p->next;p->next=s;}}void delet(link *head,char x) //将指定元素x删除{link * p, * q;q=head;p=head->next;while((p!=NULL)&&(p->data!=x)){q=p;p=p->next;}if(p==NULL) cout<<"要删除的元素不存在";else{q->next=p->next;delete(p);}}void print(link *head) //输出单链表{link *p;p=head->next;while(p->next!=NULL){cout<<p->data<<"->";p=p->next;}cout<<p->data<<endl;}void main(int argc, char* argv[]){link *head,*p,*q,*r;char x,y;int n,dele,i=1,j=1;head=new link;head->next=NULL;r=head;while(j<=5){cout<<"请输入要插入的元素：";cin>>x;r=rcreat(r,x);j=j+1;}print(head);cout<<"请输入要插入元素的位置：";cin>>n;cout<<"请输入要插入的元素：";cin>>y;insert(head,n,y);cout<<"输出插入后的单链表："<<endl;print(head);cout<<"请输入要删除元素的位置：";cin>>dele;q=head;p=head->next;while(i<dele){q=p;p=p->next;i=i+1;}q->next=p->next;delete (p);cout<<"删除后的链表如下："<<endl;print(head);}四、实验结果。