线性表应用三（集合（线性表实训））线性表应用三：集合（线性表

使用线性表实现集合的表示及操作。具体需要补全三个函数：计算集合并集的 unionSet 函数、计算集合交集的 intersection 函数和向集合中添加元素的 addElement 函数。
相关知识集合是数学中一个基本概念，它是集合论的研究对象。朴素集合论中，集合的定义就是“一堆东西”，集合里的“东西”，称为元素。下面介绍几个集合的知识点：

集合中的元素是无序的，对于任意的集合S1和S2，S1=S2当且仅当对于任意的对象a，都有若a∈S1，则a∈S2；若a∈S2，则a∈S1；
集合中的元素互不相同，空集合是没有任何元素的集合；
集合的并集定义为：A∪B={x|x∈A或x∈B}。例如，A={1，3，5}，B={1，2，5}，则A∪B={1，2，3，5}；
集合的交集定义为：A∩B={x|x∈A且x∈B}。例如，A={1，3，5}，B={1，2，5}，则A∩B={1，5}。

接下来首先声明结构类型：

// 定义结点结构 struct node { int data; // 数据域 node * next; // 指针域,指向下一个结点 }; typedef node * intSet; // 定义类型别名，intSet即相当于node*

【线性表应用三（集合（线性表实训））】其中：上述结构类型的声明中定义intSet是为了使程序的可读性更好一些。因为本关是用线性表实现集合，而访问一个线性表其实只需要一个链表头指针就可以了，intSet实际上就是node*类型，所以后面可以这样声明集合a：
intSet a=NULL; // 声明集合a，并初始化为空集合（空线性表）
三个需要用户补全的函数的函数原型分别为：

计算集合并集：函数unionSet计算并返回集合a和b的并集。参数a和b是两个集合，返回值为a和b的并集。
intSet unionSet(intSet a, intSet b);
计算集合交集：函数intersection计算并返回集合a和b的交集。参数a和b是两个集合，返回值为a和b的交集。
intSet intersection(intSet a, intSet b);
将元素加入到集合中：函数addElement将元素num加入到集合is中，如果is中已经存在num了，则不需要加入，不存在则加入。参数is是一个集合，num是要加入到is中的元素。
void addElement(intSet &is, int num);

//linearList.cpp #include "linearList.h" //函数delList：删除链表，释放空间 //参数：h-链表头指针 void delList(node *h) { node *p=h; //指针p指向头结点，第一个要删除的结点 while(p) //这个结点是存在的 { h = h->next; //头指针h指向下一个结点（下一个结点的地址存在当前结点的指针域中，即h->next中 delete p; //删除p指向的结点 p = h; //p指向当前的头结点，即下一个要删除的结点 } } //函数printList：输出链表，每个数据之间用一个空格隔开 //参数：h-链表头指针 void printList(node *h) { cout<<"List:"; while(h) {//h为真，即h指向的结点存在，则输出该结点的数据 cout<<" "next; //将该结点的指针域赋值给h，h就指向了下一个结点 } cout<next=NULL; //链表尾指针置为NULL return t; //返回第一个结点的地址（即链表头指针） } //非空链表的情况 node *p=h; //让p指向最后一个结点 while(p->next) p=p->next; p->next = t; //让最后一个结点的指针域指向结点t t->next=NULL; //链表尾指针置为NULL return h; //返回第一个结点的地址（即链表头指针） } //函数insertHead：链表头部插入 //参数：h-链表头指针，t-指向要插入的结点 //返回值：插入结点后链表的首结点地址 node * insertHead(node *h, node *t) { t->next=h; return t; } //函数insertSort：链表排序插入 //参数：h-链表头指针，t-指向要插入的结点 //返回值：插入结点后链表的首结点地址 node * insertSort(node *h, node *t) { node *p=NULL,*q=h; //定位第一个插入点：链首 while(q && q->datadata) //查找插入点 {//两个指针并行后移 p=q; q=q->next; } if(p==NULL) //插入链首 { t->next = h; return t; } if(q==NULL) //插入链尾 { p->next = t; t->next = NULL; return h; } //插入p、q之间 t->next=q; p->next=t; return h; } //函数search：在链表中查找包含数据num的结点 //参数：h-链表头指针，num-要查找的数据 //返回值：找到了返回该结点的地址，否则返回NULL node * search(node * h, int num) { while(h) {//h为真，即h指向的结点存在 if(h->data=https://www.it610.com/article/=num) return h; h=h->next; //将该结点的指针域赋值给h，h就指向了下一个结点 } return NULL; //没找到包含num的结点 } //函数delAt：删除链表中序号为i的结点，如果i是非法序号则不做操作 //参数：h-链表头指针，i-要删除结点的序号 //返回值：删除结束后链表首结点地址 node * delAt(node * h, int i) { if(i<0) //序号非法，不删除 return h; node *p=NULL, *q = h; // 定位删除结点，试图让q指向要删除结点，p指向其前面的结点 for(int k=0; knext==NULL) //后面没有结点了，序号非法 return h; p=q; q=q->next; } if(p) //p指向的结点存在，不是删除首结点 { //删除q指向的结点，让p指向结点的指针域指向q的后续结点 p->next = q->next; //释放空间 delete q; return h; } else //删除首结点 { h = q->next; //下一个结点成了首结点 //释放空间 delete q; return h; } } //函数delHas：删除链表中data为n的结点，如果有多个这样的结点，只删除第一个 //参数：h-链表头指针，n-结点包含的数据 //返回值：删除结束后链表首结点地址 node * delHas(node * h, int n) { node *p=NULL, *q=h; //p为要删除结点的前结点，q指向要删除结点 while(q) {//h为真，即h指向的结点存在 if(q->data=https://www.it610.com/article/=n) break; //找到了 if(q->next==NULL)//后面没有结点了，没有结点满足条件 return h; //不删除，直接返回 //继续往后找，两个指针一起后移 p=q; q=q->next; } //删除q指向的结点 if(p==NULL)//删除头结点 { h=q->next; //下一个结点变成头结点 delete q; //删除结点 return h; } //不是头结点 p->next=q->next; //把q指向结点的指针域（q后面结点的地址）赋值给p指向结点的指针域 return h; } //函数listLength：计算并返回链表的长度 //参数：h-链表头指针 //返回值：链表长度 int listLength(node * h) { int n=0; while(h) { n++; h=h->next; } return n; } //函数listSort：链表排序（为了输出结果唯一） //参数：h-链表头指针 //返回值：排序后的链表 node * listSort(node *h) { node *p=NULL, *t=h; while(t) { h=h->next; t->next=NULL; p=insertSort(p,t); t=h; } return p; }

//linearList.h #include using namespace std; //定义结点结构 struct node { int data; //数据域 node * next; //指针域,指向下一个结点 }; //函数listSort：链表排序（为了输出结果唯一） //参数：h-链表头指针 //返回值：排序后的链表 node * listSort(node *h); //函数listLength：计算并返回链表的长度 //参数：h-链表头指针 //返回值：链表长度 int listLength(node * h); //函数delHas：删除链表中data为n的结点，如果有多个这样的结点，只删除第一个 //参数：h-链表头指针，n-结点包含的数据 //返回值：删除结束后链表首结点地址 node * delHas(node * h, int n); //函数delAt：删除链表中序号为i的结点，如果i是非法序号则不做操作 //参数：h-链表头指针，i-要删除结点的序号 //返回值：删除结束后链表首结点地址 node * delAt(node * h, int i); //函数search：在链表中查找包含数据num的结点 //参数：h-链表头指针，num-要查找的数据 //返回值：找到了返回该结点的地址，否则返回NULL node * search(node * h, int num); //函数insertSort：链表排序插入 //参数：h-链表头指针，t-指向要插入的结点 //返回值：插入结点后链表的首结点地址 node * insertSort(node *h, node *t); //函数insertHead：链表头部插入 //参数：h-链表头指针，t-指向要插入的结点 //返回值：插入结点后链表的首结点地址 node * insertHead(node *h, node *t); //函数printList：输出链表，每个数据之间用一个空格隔开 //参数：h-链表头指针 void printList(node *h); //函数insertTail：链表尾部插入 //参数：h-链表头指针，t-指向要插入的结点 //返回值：插入结点后链表的首结点地址 node *insertTail(node *h, node *t); //函数delList：删除链表，释放空间 //参数：h-链表头指针 void delList(node *h);

//mset.cpp #include "mset.h" // 函数unionSet：求集合a和b的并集 // 参数：a-集合，b-集合 // 返回值：集合（集合a和b的并集） intSet unionSet(intSet a, intSet b) { // 准备空集合 intSet c=NULL; // 把a中每一个元素加入c中 node *p=a; while(p) { addElement(c,p->data); p=p->next; } // 把b中每一个元素加入c中 p=b; while(p) { addElement(c,p->data); p=p->next; } return c; } // 函数intersection：求集合a和b的交集 // 参数：a-集合，b-集合 // 返回值：集合（集合a和b的交集） intSet intersection(intSet a, intSet b) { // 准备空集合 intSet c=NULL; // 查看a中每一个元素 node *p=a; while(p) { if(search(b,p->data)) {// 也在b中，则选入集合c addElement(c,p->data); } p=p->next; } return c; } // 函数addElement：在集合is中增加元素num // 参数：is-集合，num-要增加的元素 // 返回值：无 void addElement(intSet &is, int num) { // 首先确认num是否在is中 node *p=search(is,num); if(p!=NULL) return; // 准备结点 p=new node; p->data = https://www.it610.com/article/num; p->next = NULL; is = insertHead(is,p); }

//mset.h #include "linearList.h" typedef node * intSet; // 定义类型别名，intSet即相当于node* // 函数unionSet：求集合a和b的并集 // 参数：a-集合，b-集合 // 返回值：集合（集合a和b的并集） intSet unionSet(intSet a, intSet b); // 函数intersection：求集合a和b的交集 // 参数：a-集合，b-集合 // 返回值：集合（集合a和b的交集） intSet intersection(intSet a, intSet b); // 函数addElement：在集合is中增加元素num // 参数：is-集合，num-要增加的元素 // 返回值：无 void addElement(intSet &is, int num);

//test.cpp #include "mset.h" int main() { //声明4个空集合 intSet a=NULL,b=NULL,c=NULL,d=NULL; int n,num,i; //输入集合a cin>>n; for(i=0; i>num; addElement(a,num); } //输入集合b cin>>n; for(i=0; i>num; addElement(b,num); } //计算集合交集 c=intersection(a,b); //计算并集 d=unionSet(a,b); //调整集合c、d中元素的顺序 c = listSort(c); d = listSort(d); //输出结果 printList(c); printList(d); //删除结点，释放空间 delList(a); delList(b); delList(c); delList(d); return 0; }