数据结构课程设计集合运算.doc

集合的运算1 需求分析1.1 设计任务集合的元素限定含有两个数据域的结构体，一个数据域为整数，另一个数据域为小写字母字符a.z；演示程序以用户和计算机的对话方式执行；其中运用了编程软件microsoft visual c+ 6.0创建链表来表示集合，用链表的查找、删除、插入等知识点来实现集合的并、交、差和布尔和四种运算。1.2 功能要求集合输入的形式为一个以回车符为结束标志的字符串，元素中字符顺序为先整数后字母，否则程序提示重新输入,若出现重复元素或非法字符，不符合集合的定义,程序提示重新输入。本段程序旨在对输入的元素进行并集,交集,差集和布尔和运算。 2 概要设计2.1链表表的抽象数据类型定义1为实现上述程序功能，并要求以有序链表表示集合。所以，抽象数据类型就是单链表adt orderedlinklist数据对象：d=( ai, bi)|aiinteger，bicharset, i=1,2,.,n, n 0数据关系：rl=| ( ai-1, bi-1), ( ai, bi)d, ( ai-1, bi-1)e)return 1;elseif(enode2.c)return 1;elseif(ode2.c)return -1;elsereturn 0;3.3元素个数输入的合法性检查这个函数完全是为了程序的健壮性准备的，当用户错误输入时，程序提示用户输入正确的整数，直到输入正确后才可以进行下一步操作。如果用户输入的有多余的字符，存在输入输入缓冲却，将会被函数中调用的fflush(stdin) 6函数处理掉，消除了缓冲区残留信息对下一步操作的影响。函数如下：status input1(int n)while(1)if(scanf(%d,&n)=1)fflush(stdin);/清除输入缓冲区break;elsecout请正确输入整数：endl;fflush(stdin);/退出循环就输入正确了return n;/返回正确输入的整数3.4 集合元素输入的合法性检查即归为结点数据输入的正确性检查。当输入不正确时，程序提示用户具体的输入操作，直到用户输入正确后，才可以把输入的值赋值给结点的两个数据成员，否则提示用户重新输入该元素。具体函数如下：status input(linklist &s)int a,x;char c;/scanf()函数的返回值5进行条件判断if(scanf(%d,&a)=1 & scanf(%c,&c)=1)/控制字符为小写字母if(c=97)s-inte=a;s-c=c;fflush(stdin);/清除缓冲区的一个输入流x=1;elsecout输入失败,第二部分是小写字母endl;fflush(stdin);x=-1;elsecout集合元素是先一个整数后一个小写字母！nex=null。如用重复，则需要重新输入。直到元素的个数等于用户第一步输入的元素个数时函数调用结束。函数如下：status createlinklist(linklist &l,int n)cout输入集合元素时，整数与字母之间没有任何符号，endl并且多余的字符将被程序处理掉，元素之间用回车键next=null;for(int i=0;inext)& datacompare(*p-next,*s)!=0)/调用元素大小比较函数p=p-next;if(p-next)/检查到重复元素cout元素有重复next=s;p=p-next;p-next=null;x=ok;elsei-;/为下一次循环显示元素的id号x=-1;return x;3.6求集合的并集2求集合的并集，根据课题要求，转化为合并两个链表的的问题。先把链表a的元素拷贝到链表c中，然后对链表b从头开始检索，依次和链表c中的每一个元素进行比较，如果该元素不存在于链表c中，就将该元素用尾插法插入链表c。直到链表b为空，就完成了两个集合的并集运算。函数如下：status unionset(linklist &a,linklist &b,linklist &c)linklist pa=a-next,pb=b-next,s,r;/pb指向b的第一个结点，s为要插入的结点，r为扫描指针c=(linklist)malloc(sizeof(lnode);r=c;while(pa!=null)/复制链表a的结点到链表c中s=(linklist)malloc(sizeof(lnode);s-inte=pa-inte;s-c=pa-c;r-next=s;r=s;pa=pa-next;while(pb!=null)/依次检索链表bpa=a-next;while(pa!=null & datacompare(*pa,*pb)/检查元素是否重复pa=pa-next;if(pa=null)/说明该元素不存在于a中/尾插法插入该结点s=(linklist)malloc(sizeof(lnode);s-inte=pb-inte;s-c=pb-c;r-next=s;r=s;pb=pb-next;r-next=null;return ok;3.7 求a、b集合的交集3转化为求两个链表中相同元素的算法。先创建空链表c，外层循环对链表a首元结点开始检索，内层循环是将外层循环的结点的数据域与链表b中的非表头结点的数据域依次进行比较，当外循环的节点数据与内循环结点数据相等时，就得到交集的一个元素，用尾插法插入链表c中，当两层循环都结束时，就完成了集合的交集运算。函数如下：status interset(linklist &a,linklist &b,linklist &d)linklist pa=a-next,pb,s,r;/pb指向b的第一个结点，s为要插入的结点，r为扫描指针d=(linklist)malloc(sizeof(lnode);r=d;while(pa!=null)/外层循环，对a中元素检索pb=b-next;while(pb!=null& datacompare(*pb,*pa)内层循环，找相等元素pb=pb-next;if(pb!=null)/此元素在a中s=(linklist)malloc(sizeof(lnode);s-c=pa-c;s-inte=pa-inte;r-next=s;r=s;pa=pa-next;r-next=null;return ok;3.8求差集2转化为求两表中，存在于前一个表中而不存在于后一个表中的元素的组成，即为差集。具体思路是先创建空链表c，外层循环从首元结点检索a表中的元素，内层循环就是将a中的该元素从首元结点开始与表b中的元素依次作比较，如不等，则为差集的一个元素，用尾插法插入链表c中。当这两层循环结束时，集合a、b的差集运算就结束了，便得到了差集c。函数如下：status diffence(linklist &a,linklist &b,linklist &e)linklist pa=a-next,pb,s,r;/pb指向b的第一个结点，s为要插入的结点，r为扫描指针e=(linklist)malloc(sizeof(lnode);r=e;while(pa!=null)/外层循环，从首元结点开始检索表apb=b-next;while(pb!=null& datacompare(*pb,*pa)/相应元素作比较pb=pb-next;if(pb=null)/此元素在a中/尾插法插入找到的结点s=(linklist)malloc(sizeof(lnode);s-inte=pa-inte;s-c=pa-c;r-next=s;r=s;pa=pa-next;/外层循环的指针后移r-next=null;return ok;3.9 求布尔和。依据数学上的定义，布尔和即为两集合的对称差，其实质是（a-b）u（b-a），再次转化为（aub）-（a b ）。所以只需要对并集和交集调用求差集函数即可。4 调试分析4.1 调试过程中遇到的问题死循环问题1. 在输入合法性检查中，输入整数时，如果不合法，带有其他字符，产生死循环。这种问题产生于循环体的条件是永真式，而循环体内没有用break语句或者其他跳出语句；2. 同样是在输入时造成的死循环，在while(1)中，用了break语句，但是仍然出现的死循环。比如用scanf(“%d”,n)=1来判断是否输入一个整数时，在输入的不是合理整数的情况下，就死循环。其原因是输入的字符存为整数不成功，它将留在输入缓冲区，进入下一次存储，也不成功，就形成死循环。查阅资料可以找到一个清除输入缓冲区的库函数fflush(stdin)，这个函数很有效，在每次有可能在输入缓冲区残留信息的地方调用一次该函数就可以了（部分程序如下）：while(1)if(scanf(%d,&n)=1)fflush(stdin);break;elsecout请正确输入整数：endl;fflush(stdin);但是据网友细说，此函数在linux下不管用，由于本人及周边人没有用linux，所以未得试验。另一种解决方案，就是自己定义一个字符数组，把多余的字符接收掉，这样就不会影响下一次输入。3. 对于链表，条件判定后，指针未后移引起的死循环。这种主要是判断条件永真，而漏写指针后移的语句，检查程序可以解决。参数传递问题1. 如果参数是一个数组，那么形参处就写明数组类型和数组名即可，应为数组名本来就是指向该数组首地址的一个指针。2. 如果传递的是二维数组，如二维字符数组，其前面的一维就是数组如 char a5，那么a1指的是一个字符数组。3. cannot convert parameter 1 from struct lnode * to struct lnode；这种问题是参数类型不一致引起的，如果类型是明显的基本类型时一般不会出现这类错误，但是如果是自己定义的类型时，很容忽视类型而引起这类错误。字符串数组长度问题。我曾花了很多时间在网上搜索关于求字符串长度的问题，试验过不少网友提供的方法，大部分人提供的是使用库函数strlen(数组名)，但经我试验，这种方法是错误的，如：char *a=111,222,3, ,fjdkal;执行printf(“%d”,strlen(a);将得到3。这不是字符串数组的长度，其得到的是字符串数组中第一个字符串的字符个数，后来继续搜索才找到了正确答案：sizeof(数组名)/sizeof(数组元素类型)。这个真是正确答案，我试验过多次，下面是一个样例:void main() char *a=111,222,3, ,fjdkal; cout sizeof(a)/sizeof(char*) endl; cout a0 endl;运行结果如下：指针问题1. 如果指针指向的结点没有数据，而执行输出语句时却用了该指针指向的结点，则会输出一个很小的负数，一看就明白不是想要的结果。2. 指针未初始化，当程序执行过程遇到指针未初始化语句时，将无法继续执行而不正常退出，典型错误就是把一个空指针赋值给一个空指针。4.2 算法的时间复杂度和空间复杂度分析如果不改变指针本身的值时，就不要用指向指针的指针。算法复杂度（n，m为元素个数）创建链表时，正确输入的情况下，检查元素是否重复为o(n2)；求并集、交集，差集和布尔和时，时间复杂度为o(m*n);由于是用链表来作运算的，空间上都比较合理。4.3经验与体会遇到问题时，可以自己改动程序，然后编译和运行，这样可以找到错误的原因；网络是较好的资源，但是部分东西还需要我们自己验证。程序出现问题时，可以自己在程序中加入标记，观察程序执行过程，找出错误。这次课程设计让我的这方面的只是得到了扩充，程序设计思路更为清楚，同时也强化了基础，学到了不少新的知识。5 用户使用说明1 编译后，点击运行，出现如图5-1所示的运行界面；图5-12 在图5-1的情况下，用户输入两个集合中第一集合的元素的个数，输入的数必须为正整数或者0。如果用户输入的不是整数，系统会提示用户正确输入整数，直到用户输入正确后方能进入下一步（如图5-2）；如图5-23 用户输入正确后得到如图5-3所示界面，提示用户输入第一个集合的元素，元素必须含有两个部分-整数和字符，之间没有任何其他符号，对于用户输入的多余的字母，程序将自动处理掉，元素之间用回车键，并提示用户输入第一个元素；图5-34 用户输入一个元素，如果是按要求先整数后小写字母，系统就提示输入下一个元素（如图5-4所示），否则提示用户输入正确的元素（如图5-5所示），如过程中有重复的元素，系统会提示用户重新输入（如图5-6所示），直到正确输入用户在前面输入的元素个数，系统提示用户输入第二个集合的元素（如图5-7），其要求和规则同第一个集合完全一样；图5-4图5-5图5-6图5-75 当用户正确完成两个集合的元素的输入后，系统将直接输出两个集合的并集、交集、差集和布尔和，其顺序依次为集合、集合、并集、用直接插入法排序后的并集、交集、用直接选择法排序后的交集、差集、用冒泡法排序后的差集、布尔和、用希尔排序后的布尔和（如图5-8所示），之后主程序调用destroylinklist() 销毁所有链表，程序到此结束。 图5-86 测试数据与测试结果请输入集合a的元素个数：7依次输入：98f 56d23b78h21z98q2b请输入集合b的元素个数：8依次输入：56d21z78h98f36j8w1l0x得到结果：（为了尽可能显示界面，输入元素提示处没有换行）参考文献1 严蔚敏，吴伟民. 数据结构(c语言版). 北京：清华大学出版社，1997.042 数据结构习题与解析b级 第3版 清华大学出版社 李春葆 喻丹丹 编著3 数据结构教程（第2版）清华大学出版社 李春葆 等 编著4 data structures & program drsign in c,second edition 数据结构与程序设计c语言（第二版） 清华大学出版社5 c语言程序设计 复旦大学出版社 主编 孟爱国6 /view/1390039.htm7 /t/20051018/15/4334095.html附录 源程序#include#include#include#define null 0 #define ok 1#define error 0typedef int status;typedef struct lnode/定义结构体，数据域两种类型int inte;char c;struct lnode *next;lnode,*linklist;/比较元素大小status datacompare(lnode node1,lnode node2)/元素大小的比较：结点作参数，先比整数域，再比字母域/用点运算取结构体的成员变量if(e)return 1;elseif(enode2.c)return 1;elseif(ode2.c)return -1;elsereturn 0;/输入的合法性（检查输入元素个数与input的区分）status input1(int n)while(1)if(scanf(%d,&n)=1)fflush(stdin);break;elsecout请正确输入整数：endl;fflush(stdin);return n;/输入合法性检查status input(linklist &s)int a,x;char c;/scanf()函数的返回值进行条件判断if(scanf(%d,&a)=1 & scanf(%c,&c)=1)/控制字符为小写字母if(c=97)s-inte=a;s-c=c;fflush(stdin);/清除缓冲区的一个输入流x=1;elsecout输入失败,第二部分是小写字母endl;fflush(stdin);x=-1;elsecout集合元素是先一个整数后一个小写字母！endl;fflush(stdin);x=-1;return x;/创建链表status createlinklist(linklist &l,int n)cout输入集合元素时，整数与字母之间没有任何符号，endl并且多余的字符将被程序处理掉，元素之间用回车键next=null;for(int i=0;inext)& datacompare(*p-next,*s)!=0)p=p-next;if(p-next)cout元素有重复next=s;p=p-next;p-next=null;x=ok;elsei-;x=-1;return x;/求集合并集status unionset(linklist &a,linklist &b,linklist &c)linklist pa=a-next,pb=b-next,s,r;/pb指向b的第一个结点，s为要插入的结点，r为扫描指针c=(linklist)malloc(sizeof(lnode);r=c;while(pa!=null)s=(linklist)malloc(sizeof(lnode);s-inte=pa-inte;s-c=pa-c;r-next=s;r=s;pa=pa-next;while(pb!=null)pa=a-next;while(pa!=null & datacompare(*pa,*pb)pa=pa-next;if(pa=null)s=(linklist)malloc(sizeof(lnode);s-inte=pb-inte;s-c=pb-c;r-next=s;r=s;pb=pb-next;r-next=null;return ok;/求交集status interset(linklist &a,linklist &b,linklist &d)linklist pa=a-next,pb,s,r;/pb指向b的第一个结点，s为要插入的结点，r为扫描指针d=(linklist)malloc(sizeof(lnode);r=d;while(pa!=null)pb=b-next;while(pb!=null& datacompare(*pb,*pa)pb=pb-next;if(pb!=null)/此元素在a中s=(linklist)malloc(sizeof(lnode);s-c=pa-c;s-inte=pa-inte;r-next=s;r=s;pa=pa-next;r-next=null;return ok;/求集合差集status diffence(linklist &a,linklist &b,linklist &e)linklist pa=a-next,pb,s,r;/pb指向b的第一个结点，s为要插入的结点，r为扫描指针e=(linklist)malloc(sizeof(lnode);r=e;while(pa!=null)pb=b-next;while(pb!=null& datacompare(*pb,*pa)pb=pb-next;if(pb=null)/此元素在a中s=(linklist)malloc(sizeof(lnode);s-inte=pa-inte;s-c=pa-c;r-next=s;r=s;pa=pa-next;r-next=null;return ok;/直接插入排序status insertsort(linklist l)linklist p,r,s;p=l-next;/p扫描无序表段，r为扫描有序表段，s指向要插入的结点while(p-next)r=l;while(r-next!=p-next & datacompare(*p-next,*r-next)0)r=r-next;if(r-next=p-next)p=p-next;elseif(r=l)/如果是在表头后插入，则需要移动表头指针s=p-next; p-next=p-next-next;s-next=r-next;l-next=s;else /不是在表头插入s=p-next;p-next=p-next-next;s-next=r-next;r-next=s;return ok;/直接选择排序status selectsort(linklist l)linklist r,s,p;/r为扫描指针，s为选中的最小结点，p指向有序段的尾指针int tempinte;char tempc;p=l;while(p-next)r=p;s=p-next;while(r-next)if(datacompare(*s,*(r-next)0)s=r-next;r=r-next;elser=r-next;if(s)/交换结点的数据即可tempinte=s-inte;tempc=s-c;s-inte=p-next-inte;s-c=p-next-c;p-next-inte=tempinte;p-next-c=tempc;p=p-next;return ok;/冒泡排序（大的往下沉）status bubblesort(linklist l)int tempinte;char tempc;linklist p,r;/p为扫描指针，r指向有序段得头指针r=null;for(r=null;r!=l-next;p=l-next)for(p=l-next;p-next!=null&p-next!=r;)if(datacompare(*p,*(p-next)0)tempinte=p-inte;tempc=p-c;p-inte=p-next-inte;p-c=p-next-c;p-next-inte=tempinte;p-next-c=tempc;else;p=p-next;r=p;return ok;/希尔排序status shellsort(linklist l)int i=0,flag=0;linklist p,r,s;int count=0,d;/count为结点总数，d为步长p=l;while(p)/计算链表结点个数count+;p=p-next;for(d=count/2;d0;d=d/2)r=s=l;for(i=0;inext;for(i=0;inext;while(r)p=l;flag=0;while(flag=0)if(datacompare(*(p-next),*r)0)s-next=r-next;r-next=p-next;p-next=r;r=s-next;break;for(i=0;inext;if(p=r)|(p=null)flag=1;/标记扫描结束break;/防止指针越界if(flag=1)&(r!=null)r=r-next;s=s-next;return ok;/输出链表status dislinklist(linklist &l)linklist p;p=l;while(p-next)coutnext-intenext-cnext;coutnext)/非表头结点的销毁q=p-next;p-next=p-next-next;free(q);if(p-next=null)/判定到表头结点时，也将其销毁free(l) ;return ok;status main()/主函数int na=0,nb=0;/na和nb分别为集合a和b的元素个数linklist a,b,c,d,e,f;/c,d,e,f分别为并集、交集、差集和布尔和cout请输入集合a的元素个数：endl;na=input1(na);createlinklist(a,na);cout请输入集合b的元素个数：nb;createlinklist(b,nb);coutendla集合为：endl;dislinklist(a);coutendlb集合为：endl;dislinklist(b);unionset(a,b,c);/并集coutendl并集为：endl;dislinklist(c);insertsort(c);/直接插入法排序并集cout用直接插入法排序并集后为：endl;dislinklist(c);interset(a,b,d);/交集coutendl交集为：endl;dislinklist(d);selectsort(d);/直接选择法排序交集cout用直接选择法排序交集后为：endl;dislinklist(d);diffence(a,b,e);/差集coutendl差集为：endl;dislinklist(e);bubblesort(e);/冒泡法排序差集cout用冒泡排序法排序差集后为：endl;dislinklist(e);diffence(c,d,f);/布尔和coutendl布尔和为：endl;dislinklist(f);shellsort(f);/希尔排序布尔和cout用希尔排序法排序布尔和后为：endl;dislinklist(f);destroylinklist(a);/依次销毁链表destroylinklist(b);destroylinklist(c);destroylinklist(d);destroylinklist(e);destroylinklist(f);coutendl;return ok;附录：外文翻译in wang zuoliangs translation practices, he translated many poems, especially the poems written by robert burns. his translation of burns “a red, red rose” brought him fame as a verse translator. at the same time, he published about ten papers on the translation of poems. some argue that poems cannot be translated. frost stresses that poetry might get lost in translation. according to wang, verse translation is possible and necessary, for “the poet-translator brings over some exciting work from another culture and in doing so is also writing his own best work, thereby adding something to his culture. in this transmission and exchange, a richer, more colorful world emerges. ”(wang, 1991:112). then how can we translate poems? according to wangs understanding, the translation of poems is related to three aspects: a poems meaning, poetic art and language. （1）a poems meaning “socio-cultural differences are formidable enough, but the matter is made much more complex when one realizes that meaning does not consist in the meaning of words only, but also in syntactical structures, speech rhythms, levels of style.” (wang, 1991:93).（2）poetic art according to wang, “blys point about the marvelous translation being made possible in the united states only after whitman, pound and williams carlos williams composed poetry in speech rhythms shows what may be gained when there is