目录
( *^▽^* )作者有话说
(〃'▽'〃)代码
(๑*◡*๑)实验报告
实验题目：集合的表示与实现
一、概述
1.应用需求：
2.设计目标：
3.设计方案：
4.实验方案：
二、问题分析
1.实际应用需求
2.设计目标
3.数据分析
4.主要 *** 作
5.性能影响
三、设计和开发
1. ADT设计
2.存储方案
3.关键算法
4.实现总结
四、实验研究
1. 实验目的
2. 实验数据
3. 实验方案及实验结果
（1）实验方案
（2）实验结果
五、总结与优化
1. 方案的不足
2. 优化方案及实现思路
六、心得和体会
( *^▽^* )作者有话说
这是本人大二数据结构程序设计综合实验的实验报告和代码，当时是期中转专业过来的，这门课程已经上了一半，所以本人刚接触这门课的时候一窍不通，平时做实验也是copy。
天有不测风云，疫情封校，后来甚至封了宿舍，停课让我有大量的时间去好好学习一下。
这篇实验报告和实验代码，都是自己呕心沥血（没那么夸张哈哈哈哈哈）写的。
现在看来，可能很多地方有不足，但是最后这份实验课程的成绩还可以，所以还是想给大家分享一下，希望对也在接触综合实验的朋友们有所帮助。
千万不要照抄实验报告！！自己动手去敲一下代码，或者做一下修改，会更有收获。
愿我们都有很好的未来！
要是有帮助的话就关注点赞一下吧，或者有什么想说的也可以评论留言，我一定都会回复的。
以后也会多多分享自己写的实验报告。
#include
#include
#include
#include
#include
clock_t start, stop;//函数开始时的时钟打点，结束时的时钟打点
double duration;//函数运行的时间，以秒为单位
#define true 1
#define error -1
typedef int ElemType;
typedef int Status;
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LNode,*LinkList;
Status InitList(LinkList &L);//构造一个空的单链表L//
Status ListInsert(LinkList &L);//利用随机数输入集合元素//
Status ListInsertTow(LinkList &L,int n);//利用单链表的插入输入集合元素//
Status GetElem(LinkList L,int i,ElemType &e);//集合元素的查找//
Status ListDetete(LinkList &L,int i);//集合元素的删除//
Status ListOutput(LinkList&L);//利用单链表的取值输出集合的元素//
Status ClearList(LinkList&L);//重置单链表为空表//
void UnionList(LinkList L1,LinkList L2 ,LinkList &L );//求并集//
void InsersectionList(LinkList L1,LinkList L2,LinkList &L);//求交集//
void DiffenceList(LinkList &L1,LinkList L2);//求差集//
void menu()
{
printf("*********************集合运算 *** 作指南(￣▽￣)／*********************\n");
printf("\t\t1.随机数生成集合A元素ヽ(￣▽￣)\n");
printf("\t\t2.随机数生成集合B元素(*￣︶￣)\n");
printf("\t\t3.输入集合A元素ヽ(￣▽￣)\n");
printf("\t\t4.输入集合B元素(*￣︶￣)\n");
printf("\t\t5.输出集合A元素ヽ(ー_ー)ノ\n");
printf("\t\t6.输出集合B元素o(￣▽￣)ｄ \n");
printf("\t\t7.求集合AB的并集(ノ￣▽￣)\n");
printf("\t\t8.求集合AB的交集(～￣▽￣)～ \n");
printf("\t\t9.求集合AB的差集︿(￣︶￣)︿\n");
printf("\t\t0.展示完毕退出系统(^_-)☆\n");
printf("********************************************************************\n");
}
Status InitList(LinkList &L)//构造一个空的单链表L//
{
LinkList p;
p=(LinkList)malloc(sizeof(LNode));
if(!p)
{return error; }
else
{
L=p;
L->next=NULL;
return true;
}
}
Status ListInsert(LinkList &L) //利用随机数输入集合元素//
{
int i=1;
int a,n1,b,min,max;
LinkList p=L;
printf("请输入生成随机数的个数\n",n1);
scanf("%d",&n1);
printf("请输入生成随机数的范围min~max\n",min,max);
scanf("%d%d",&min,&max);
srand((unsigned int)time(0));//修改种子
for (size_t i = 0; idata =b;
p->next =L->next;
L->next =p;
}
}
Status ListInsertTow(LinkList &L,int n) //利用单链表的插入输入集合元素//
{
LinkList p=L;
int i=1;
while(i<=n)
{
printf("输入第%d个数据\n",i);
p=(LinkList)malloc(sizeof(LNode));
if(p!=NULL)
{
scanf("%d",&(p->data));
p->next =L->next;
L->next =p;
}
else
{return error;}
i++;
}
return true;
}
Status GetElem(LinkList L,int i,ElemType &e)//集合元素的查找//
{
LinkList p;int j;
p=L->next ;j=1;
while(p&&j<1)
{
p=p->next;
++j;
}
if(!p||jdata;
return true;
}
Status ListDetete(LinkList &L,int i)//集合元素的删除//
{
LinkList p,q;
int j;
p=L;j=0;
while((p->next)&&(jnext ; ++j;
}
if(!(p->next )||(j>i-1))
return error;
q=p->next ;
p->next =q->next ;
free(q);
return true;
}
Status ListOutput(LinkList&L)//利用单链表的取值输出集合的元素//
{ int i=0;
LinkList p=L;
p=L->next;
while(p!=NULL)
{
++i;
printf("输出第%d个数据 ",i);
printf("%d\n",p->data);
p=p->next;
}
if(i==0)
{
printf("空集(笨蛋！先输入再输出~)\n");
}
}
Status ClearList(LinkList &L)//重置单链表为空表//
{
LinkList p,q;
p=q=L->next;
if(!p)
{
return true;
}
else
{
q=p->next;
free(p);
}
L->next=NULL;
return error;
}
//求并集，即两个单链表合并去掉重复的元素//
void UnionList(LinkList L1,LinkList L2 ,LinkList &L ) //浪费了一点空间，也可以像p53数据结构书上算法设计第2题一样，不过就得要求两个链表是顺序表//
{
LinkList p,q,s;
if(L->next !=NULL)//如果L不是空表//
{
ClearList(L);//重置L为空表//
}
p=L1->next ;//p指针指向第一个集合单链表L1的第一个元素//
while(p!=NULL)
{
q=L->next ;
while(q!=NULL&&(q->data!=p->data))
{
q=q->next;
}
if(q==NULL)
{
s=(LinkList)malloc(sizeof(LNode));//赋予新结点空间//
s->data=p->data;//头插法//
s->next=L->next;
L->next =s;
}
p=p->next ;
}
p=L2->next ;//p指针指向第二个集合单链表L2的第一个元素,其步骤同上//
while(p!=NULL)
{
q=L->next ;
while(q!=NULL&&(q->data !=p->data ))
{
q=q->next ;
}
if(q==NULL)
{
s=(LinkList)malloc(sizeof(LNode));
s->data =p->data ;
s->next =L->next ;
L->next =s;
}
p=p->next ;
}
}
//求交集，即保留两个单链表中元素相同的部分//
void InsersectionList(LinkList L1,LinkList L2,LinkList &L)//同并集一样的道理，多用了一些空间，但是简单好理解//
{
LinkList p,q,s,h;
if(L->next !=NULL)//如果L不是空表//
{
ClearList(L);//重置L为空表//
}
p=L1->next ;
while(p)//A不是空集//
{
q=L2->next ;
while(q)//B不是空集//
{
if(p->data ==q->data ) break;//找到相同元素就跳出循环//
if(p->data !=q->data ) q=q->next ;
}
if(q)//找到了AB中有相同的元素//
{
s=L->next ;
while(s)
{
if(s->data ==p->data ) break;//表示L中已经存了相同元素，跳出循环//
if(s->data !=p->data ) s=s->next ;//没找到就下一个元素对比//
}
if(!s)//L中一个元素没存或者s指针已经遍历完了却没有找到相同的元素//
{
h=(LinkList)malloc(sizeof(LNode));//建立新结点把它存下来//
h->data =p->data ;
h->next =L->next;
L->next =h;
}
}
p=p->next ;
}
}
//求差集，就是求A集合中除去与B集合相同元素剩下的部分//
void DiffenceList(LinkList L1,LinkList L2,LinkList L)
{
LinkList p,q,s,h;
if(L->next !=NULL)//如果L不是空表//
{
ClearList(L);//重置L为空表//
}
p=L1->next ;
while(p)//A不是空集//
{
q=L2->next ;
while(q)//B不是空集//
{
if(p->data ==q->data ) break;//找到相同元素就跳出循环//
if(p->data !=q->data ) q=q->next ;
}
if(!q)//找到A中有而B中没有的元素//
{
s=L->next ;
while(s)
{
if(s->data ==p->data ) break;//表示L中已经存了相同元素，跳出循环//
if(s->data !=p->data ) s=s->next ;//没找到就下一个元素对比//
}
if(!s)//L中一个元素没存或者s指针已经遍历完了却没有找到相同的元素//
{
h=(LinkList)malloc(sizeof(LNode));//建立新结点把它存下来//
h->data =p->data ;
h->next =L->next;
L->next =h;
}
}
p=p->next ;
}
}
int main()
{
LinkList L,L1,L2;
int c;//选择菜单的意思 //
int n;//要插入的元素的个数//
InitList(L);
InitList(L1);
InitList(L2);
while(1)
{
menu();
printf("输入选择的功能序号");
scanf("%d",&c) ;
switch(c)
{
case 1:
ListInsert(L1);
getchar();getchar();system("cls");//回车清屏//
break;
case 2:
ListInsert(L2);
getchar();getchar();system("cls");//回车清屏//
break;
case 3:
printf("输入集合A的总个数：\n");
scanf("%d",&n);
ListInsertTow(L1,n);
getchar();getchar();system("cls");//回车清屏//
break;
case 4:
printf("输入集合A的总个数：\n");
scanf("%d",&n);
ListInsertTow(L2,n);
getchar();getchar();system("cls");//回车清屏//
break;
case 5:
printf("输出集合A的元素:\n");
ListOutput(L1);
getchar();getchar();system("cls");//回车清屏//
break;
case 6:
printf("输出集合B的元素:\n");
ListOutput(L2);
getchar();getchar();system("cls");//回车清屏//
break;
case 7:
printf("集合A和B的并集:\n");
start = clock();
UnionList(L1,L2,L );
stop = clock();
duration = ((double)(stop - start)) / CLK_TCK;
printf("并集算法性能%lf\n", duration);
ListOutput(L);
getchar();getchar();system("cls");//回车清屏//
break;
case 8:
printf("集合A和B的交集:\n");
stop = clock();
InsersectionList(L1,L2,L);
stop = clock();
duration = ((double)(stop - start)) / CLK_TCK;
printf("交集算法性能%lf\n", duration);
ListOutput(L);
getchar();getchar();system("cls");//回车清屏//
break;
case 9:
printf("集合A和B的差集:\n");
stop = clock();
DiffenceList(L1,L2,L);
stop = clock();
duration = ((double)(stop - start)) / CLK_TCK;
printf("差集算法性能%lf\n", duration);
ListOutput(L);
ListOutput(L);
getchar();getchar();system("cls");//回车清屏//
case 0:
printf("欢迎光临，下次再来！\n");
getchar();getchar();system("cls");//回车清屏//
exit(0);
default:
printf("笨蛋！！！请输入0~9！\n");
getchar();getchar();system("cls");//回车清屏//
}
}
}
①通过代码编写生成随机数求集合元素规模较大的运算，例如在汽车电商领域，要实现一辆车型在不同省份关于不同价格行情的分析。
②通过键盘输入的方式求方程的解集、几数之间的公倍数等集合元素规模较小的运算。
实验结果能够顺利实验集合的交集、并集、差集等运算。
利用单链表的头插法，链表对于删除添加 *** 作更加灵活方便。
首先定义链表结点的结构体包含指针域和数据域。 其次构造一个空的单链表L。 接着利用单链表的插入输入集合元素，利用单链表的取值输出集合的元素。 然后需要在编写一个重置单链表为空表的 *** 作。
①求并集：删去A和B集合中重复的元素。
L1表存储集合A中元素，L2表存储集合B中元素。
先判断L是否为空表，不为空则做清空 *** 作。
指针p指向L1->next，指针q指向L->next，在L表中遍历，看其是否有相同的元素，有则进行下一步，没有则添加进L表中。
对L2表进行相同 *** 作。
②求交集：求A和B集合中相同的元素。
L1表存储集合A中元素，L2表存储集合B中元素。
先判断L是否为空表，不为空则做清空 *** 作。
p=L1->next，q=L2->next找到相同元素就跳出循环，将新结点赋值并添加到L表中，找不到则进行下步 *** 作q=q->next。
③求差集：求A集合中除去与B集合相同元素剩下的部分。
L1表存储集合A中元素，L2表存储集合B中元素。
先判断L是否为空表，不为空则做清空 *** 作。 p=L1->next，q=L2->next，找到相同元素就跳出循环，没找到则进行q=q->next;再将s=L->next，
集合的运算在汽车电商领域的应用。
许多买卖车的APP需要给用户提供不同车型在不同省份的不同价格供用户选择。
如果要实现一辆车型在不同省份有不同的价格行情，就需要有一个车价管理的后台管理界面。
每辆车对应的详情界面管理各省价格行情，增加该车在某个省份的行情，或者更新某个省份的行情，或者该车暂时去除某个省份的行情等功能，需要服务器端保证正确地数据存储。
例如，A为客户端传送的数据对象，B为从数据库中获取的对象。
A中有的元素，而B中没有的元素就是要插入数据库中的数据，即A与B的差集。
A和B共有的元素就是要更新的数据，即A与B的交集。
B中有的元素，A中没有的就是要删除的数据，即B与A的差集。
集合A为客户端传送的数据对象，用键盘输入来实现。
集合B为从数据库中获取的对象，用生成的随机数来实现，可以控制随机数的数量和大小范围尽可能真实的模拟车价行情数据库。
集合元素的插入、集合元素的删除、两集合求并集、两集合求交集、两集合求差集等等。
实验主要使用的是单链表的头插法，问题规模是n,其中关于单链表元素的插入和删除，其时间性能是O(n)。
ADT List{
数据对象：D={ai|ai∈Elemset,i=1,2,3,…,n,n≧0}
数据关系：R={1,ai >|ai-1,ai∈D,i=1,2,3,…,n,n≧0}
基本 *** 作：
Status InitList(LinkList &L);//构造一个空的单链表L//
Status ListInsert(LinkList &L);//利用随机数输入集合元素//
Status ListInsertTow(LinkList &L,int n);//利用单链表的插入输入集合元素//
Status GetElem(LinkList L,int i,ElemType &e);//集合元素的查找//
Status ListDetete(LinkList &L,int i);//集合元素的删除//
Status ListOutput(LinkList&L);//利用单链表的取值输出集合的元素//
Status ClearList(LinkList&L);//重置单链表为空表//
void UnionList(LinkList L1,LinkList L2 ,LinkList &L );//求并集//
void InsersectionList(LinkList L1,LinkList L2,LinkList &L);//求交集//
void DiffenceList(LinkList &L1,LinkList L2);//求差集//
2.存储方案 由于实验中涉及大量元素的插入，所以本实验是用链式存储结构。
（1）顺序存储
特点：存储空间的地址连续，数据元素依次存放。
优点：存储密度大，可以随机访问，查询、修改元素的时间复杂度是O(1)。
缺点：表示关系能力弱，维护关系困难，插入和删除数据的时间复杂度是O(n)。
（2）链式存储
特点： 占用空间任意，元素任意存放；在存放元素的同时，还存放与其有关系的元素的地址。
优点：空间任意，显式地存储关系。
表示关系的能力强。
插入、删除元素的时间复杂度是O(1)，便于动态管理内存。
缺点：空间开销大，占用空间较多，存储密度小。
必须通过指针来访问元素，查找、修改元素的时间复杂度是O(n)。
①
算法的时间复杂度为O（n）,n指输入生成随机数的个数。
Status ListInsert(LinkList &L) //利用随机数输入集合元素//
{
int i=1;
int a,n1,b,min,max;
LinkList p=L;
printf("请输入生成随机数的个数\n",n1);
scanf("%d",&n1);
printf("请输入生成随机数的范围min~max\n",min,max);
scanf("%d%d",&min,&max);
srand((unsigned int)time(0));//修改种子//
for (size_t i = 0; i { a = rand(); int b = a % (max- min+1) + min;//设置范围// printf("%d ", b); p=(LinkList)malloc(sizeof(LNode)); p->data =b;//将随机数的值赋值给新结点// p->next =L->next;//单链表的头插法插入结点// L->next =p; } } ② 算法的时间复杂度是O（m+n）,m指集合A中的元素，n指集合B中的元素。 //求并集，即两个单链表合并去掉重复的元素// void UnionList(LinkList L1,LinkList L2 ,LinkList &L ) //浪费了一点空间，也可以像p53数据结构书上算法设计第2题一样，不过就得要求两个链表是顺序表// { LinkList p,q,s; if(L->next !=NULL)//如果L不是空表// { ClearList(L);//重置L为空表// } p=L1->next ;//p指针指向第一个集合单链表L1的第一个元素// while(p!=NULL) { q=L->next ; while(q!=NULL&&(q->data!=p->data)) { q=q->next; } if(q==NULL) { s=(LinkList)malloc(sizeof(LNode));//赋予新结点空间// s->data=p->data;//头插法// s->next=L->next; L->next =s; } p=p->next ; } p=L2->next ;//p指针指向第二个集合单链表L2的第一个元素,其步骤同上// while(p!=NULL) { q=L->next ; while(q!=NULL&&(q->data !=p->data )) { q=q->next ; } if(q==NULL) { s=(LinkList)malloc(sizeof(LNode)); s->data =p->data ; s->next =L->next ; L->next =s; } p=p->next ; } } ③ 算法的时间复杂度是O（m+n）,m指集合A中的元素，n指集合B中的元素。 //求交集，即保留两个单链表中元素相同的部分// void InsersectionList(LinkList L1,LinkList L2,LinkList &L)//同并集一样的道理，多用了一些空间，但是简单好理解// { LinkList p,q,s,h; if(L->next !=NULL)//如果L不是空表// { ClearList(L);//重置L为空表// } p=L1->next ; while(p)//A不是空集// { q=L2->next ; while(q)//B不是空集// { if(p->data ==q->data ) break;//找到相同元素就跳出循环// if(p->data !=q->data ) q=q->next ; } if(q)//找到了AB中有相同的元素// { s=L->next ; while(s) { if(s->data ==p->data ) break;//表示L中已经存了相同元素，跳出循环// if(s->data !=p->data ) s=s->next ;//没找到就下一个元素对比// } if(!s)//L中一个元素没存或者s指针已经遍历完了却没有找到相同的元素// { h=(LinkList)malloc(sizeof(LNode));//建立新结点把它存下来// h->data =p->data ; h->next =L->next; L->next =h; } } p=p->next ; } } ④ 算法的时间复杂度是O（m+n）,m指集合A中的元素，n指集合B中的元素。 //求差集，就是求A集合中除去与B集合相同元素剩下的部分// void DiffenceList(LinkList L1,LinkList L2,LinkList L) { LinkList p,q,s,h; if(L->next !=NULL)//如果L不是空表// { ClearList(L);//重置L为空表// } p=L1->next ; while(p)//A不是空集// { q=L2->next ; while(q)//B不是空集// { if(p->data ==q->data ) break;//找到相同元素就跳出循环// if(p->data !=q->data ) q=q->next ; } if(!q)//找到A中有而B中没有的元素// { s=L->next ; while(s) { if(s->data ==p->data ) break;//表示L中已经存了相同元素，跳出循环// if(s->data !=p->data ) s=s->next ;//没找到就下一个元素对比// } if(!s)//L中一个元素没存或者s指针已经遍历完了却没有找到相同的元素// { h=(LinkList)malloc(sizeof(LNode));//建立新结点把它存下来// h->data =p->data ; h->next =L->next; L->next =h; } } p=p->next ; } } ⑤集合元素的查找 Status GetElem(LinkList L,int i,ElemType &e) { LinkList p;int j; p=L->next ;j=1; while(p&&j<1) { p=p->next; ++j; } if(!p||j e=p->data; return true; } ⑥集合元素的删除 Status ListDetete(LinkList &L,int i) { LinkList p,q; int j; p=L;j=0; while((p->next)&&(j { p=p->next ; ++j; } if(!(p->next )||(j>i-1)) return error; q=p->next ; p->next =q->next ; free(q); return true; } 实验主要是靠链表完成的，首先重要的是对于链表的结点定义，接下来是关于链表一些基本 *** 作的定义，例如构造空链表、链表的插入、链表元素的读取、链表的清空等。 集合运算求并集并不难，开拓三个空间的链表，一个存放集合A元素，一个存放集合B元素，然后一个存放删去AB集合中重复元素剩下的所有元素。 主要就是浪费了空间。 难点在于交集和差集的运算。 交集运算。 起先想法是分两种情况，当集合A和集合B都不为空时，p,q指针指向存储集合A集合B的链表L1、L2，当p、q指针的数据域不相同是，p指着就往下遍历。 相等时，用新结点保存下来并插入到第三个链表中。 其重点是每次在L2中找到相同的元素，就新建结点赋值插入L中，并且p指针就不再往后走，继续从头开始。 当集合A和集合B有一个为空时，要有一个是空集求交集就是空集。 但是运行时结果不对。 光标闪动不出结果，进行调试。 是想法的错误，q指针只会指向链表的第一个元素，当p指针遍历完之后，q指针指向的元素数据如果没有和p指针指的数据向相同，也不会往下遍历用第二个对比。 换种思路，先判断L是否为空表，不为空则做清空 *** 作。 p=L1->next，q=L2->next找到相同元素就跳出循环，将新结点赋值并添加到L表中，找不到则进行下步 *** 作q=q->next。 再将s->data与p->data进行比较，相等表示L中已经存了相同元素，跳出循环；不相等表示没找到就下一个元素对比。 L中一个元素没存或者s指针已经遍历完了却没有找到相同的元素，就建立新结点h把它存下来。 经过测试集合的交集运算成功运行。 差集运算。 最初的想法是只使用两个链表。 L1表存储集合A中元素，L2表存储集合B中元素。 利用单链表L1的存储空间，把和L2中相同的元素删除即可。 分三种情况，第一种，当A和B集合都存在元素时，p=L1->next，q=L2->next。 若p、q指针数据域不相同则进行下步 *** 作q=q->next。 若p、q指针数据域相同，则s=p->next ;p->next =s->next;free(s); p=p->next ;q=L2->next; L1中每删除一个元素，q都要从头遍历一遍。 第二种，当A是空集而B不是空集时，其差集是空集。 第三种，当A不是空集而B是空集时，其差集是A。 运行时结果不对。 光标闪动不出结果，进行调试。 和交集运算是一样的错误，q指针只会指向链表的第一个元素，当p指针遍历完之后，q指针指向的元素数据如果没有和p指针指的数据向相同，也不会往下遍历用第二个对比。 导致光标闪动，无法进行下一步 *** 作。 原本是想节省空间的。 设备允许，空间充足，所以后期修改，我增加了一个链表L存储A和B的差集。 先判断L是否为空表，不为空则做清空 *** 作。 p=L1->next，q=L2->next，找到相同元素就跳出循环，没找到则进行q=q->next;再将s=L->next。 将s->data 和p->data做判断。 若相等就break，结束当前循环。 若不相等就进行s=s->next。 当 L中一个元素没存或者s指针已经遍历完了却没有找到相同的元素，则建立新结点h把它存下来。 分析大规模集合表示和运算所面临的挑战，实现集合元素查找、插入、删除以及集合的交、并、差等运算，并设计恰当的实验验证单链表实现集合运算的时空性能。 （1）代码编写过程中先选用小规模范围内的随机数检验代码是否正确。 多次经检验结果正确。 以下只列出一组。 （2）进过多次检验后，运用实例。 以大众迈腾为例不同省份的价格在186900~309900之间，集合B为从数据库中获取的对象，可以用生成随机数模拟数据库。 随机数在186900~309900之间，个数为全中国省份34。 集合A为客户端传送的数据对象,即最新年份不同省份大众迈腾的价格。 可以用键盘输入的方式来模拟。 ①随机数生成集合A元素 ②输出集合B元素 ③输入集合A元素 ④输出集合A元素 ⑤两集合求并集，在该实例下并无实际意义 ⑥两集合求交集.A和B共有的元素就是要更新的数据，即求交集。 ⑦两集合求差集A中有的元素，而B中没有的元素就是要插入数据库中的数据，即A与B的差集。 首先定义链表结点的结构体包含指针域和数据域。 其次构造一个空的单链表L。 接着设计了两种插入元素的方式。 其一是利用单链表的头插法输入集合元素，其二是利用随机数输入集合元素，利用单链表的取值输出集合的元素。 然后需要在编写一个重置单链表为空表的 *** 作。 利用这几个函数就可以求并集、交集、补集。 实验中还有对集合元素的删除，查找。 一个算法测试需要从正确性、可用性、可读性、健壮性四个方面来判断。 正确性：一个好的算法必需能够正确的执行要求的功能和性能要求。 进过算法测试，实验代码能够正确运行执行起来。 可用性：一个好的算法能够很方便的使用。 要求算法的输入和输出都良好的接口，一个算法只完成一个特定的功能 经过测试算法，实验算法具有良好的界面，实验中还定义了一个menu（）菜单函数，利用switch（）函数，使集合元素的插入、删除、查找、求并集、求交集、求差集等 *** 作整齐排列。 在主函数main（）中，使用system（“cls”）清屏 *** 作使得 *** 作界面简洁方便。 可读性：一个好的算法应该具有很好的可读性。 这样有利于理解、测试。 经过测试算法，实验中代码的逻辑是清晰、简单的。 函数名及变量名是具有实际意义，均是采用英语实际含义命名。 每一部分具有适当的注释，对算法函数的功能、输入、输出、参数使用、重要变量、主要功能段等进行说明。 健壮性：一个好的算法能够处理各种异常和特殊情况。 经过算法测试，本实验在这一方面完成度不够，算法的时空复杂度很大，算法结果很简单，逻辑不是十分严谨。 实验基本实现了集合运算的插入、查找、删除、并集、差集、补集。 但是还有很大提升空间。 首先是对集合元素的优化，实验中没有对集合元素进行规划 *** 作，由于集合元素是较为简单的int整型，所以可以先对集合元素进行排序。 在进行并集、交集、差集的 *** 作时空复杂度会减少。 应用到实际问题，在本实验中集合元素只能是整型int和单一元素，来表示汽车的价格。 其实可以定义一个汽车的结构体，其中包括汽车种类，省份和车价行情。 其中汽车种类、省份都可以用整型代码指代，不一定用char类型。 对元素进行排序可以采用希尔排序。 希尔排序的平均时间复杂度是众多排序中最小的。 先将整个待排序的元素序列分割成几组，从而减少参与直接插入排序的数据量，对每组分别进行直接插入排序，然后增加每组的数据量，重新分组。 这样当经过几次分组排序后，整个序列中的元素基本有序，再对全体元素进行一次直接插入排序。 输入集合元素后，L即为待排序表，使排序后的数据从小到大排列。 希尔排序关键算法入下。 void ShellInsert(SqList L,int dk){ for(int i=dk+1;i<=L.Length;i++){ if(L.elem[i-dk]>L.elem[i]){ L.elem[0]=L.elem[i-dk]; L.elem[i-dk]=L.elem[i]; L.elem[i]=L.elem[0]; i=dk+1;}}} 对元素进行排序后求并集。 合并后的新 如果两个表中的元素相等，只取L1表中的元素，删除L2表中的元素，这样确保合并后表中无重复的元素。 当一个表到达表尾结点，为空时，将非空表的剩余元素直接链接在L表的最后。 相较本实验而言，p、q不用反复遍历，一起向链表最后走。 相较原实验，极大的减少了空间。 对元素进行排序后求交集。 只有同时出现在两集合中的元素才出现在结果表中，合并后的新表使用头指针L指向。 p和q分别是指向链表L1和L2的指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表L1和L2均为到达表尾结点时，如果两个表中相等的元素时，取L1表中的元素，删除L2表中的元素。 如果其中一个表中的元素较小时，删除此表中较小的元素，此表的指针后移。 当链表L1和L2有一个到达表尾结点，为空时，依次删除另一个非空表中的所有元素。 相较原实验，极大的减少了空间。 对元素进行排序后求差集。 p和q分别是链表L1和L2的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表L1和L2均为到达表尾结点时，如果L1表中的元素小于L2表中的元素，pre指针设置为L1表的指针p，删除L2表中的元素。 如果其中一个表中的元素较小时，删除此表中较小的元素，此表的p或q指针后移。 当链表L1和L2有一个为空时，依次删除另一个非空表中的所有元素。 相较原实验，极大的减少了空间。 首次写较长的一个完整性的代码，虽然一开始觉得写代码的过程很艰难，但每一个完整的长代码都是由部分组成的，将代码分成多个定义函数和主函数，每一次写完一个函数都会很满足，最后完成整个代码会很有成就感。 实验结果总的来说是好的，成功完成了集合的交并差集运算，其中生成随机数函数，菜单函数和清屏的 *** 作都使得算法的可用性增加。 但是在联系实际，解决实际问题仍可以有很大提升，增加算法的健壮性。 集合在计算机中的应用甚广，我们仍需要不断探索，不断应用，利用科技的力量解决实际问题。 欢迎分享，转载请注明来源：内存溢出
在集合A中删除集合A和集合B中共有的元素，即删除链表中的相应结点，所以要保存待删除结点的前驱，使用指针pre指向前驱结点。
微信扫一扫
支付宝扫一扫
评论列表（0条）