毕业论文设计-数据结构课程设计报告

数据结构课程设计学院名称：计算机工程学院专业：信息管理与信息系统班级：姓名：2015年1月7日目录TOC\o"1-3"\h\u1861一、数据结构课程设计报告要求111730二、第一类题目2136602.1问题陈述22.2．程序代码22.3．运行结果42.4．设计体会与总结417053三、第二类题目43.1．问题陈述43.2．需求分析53.3．概要设计53.4．详细设计63.5．程序代码73.6．运行结果与测试183.7．设计体会与总结19317四、第三类题目204.1．问题陈述204.2．需求分析204.3．概要设计204.4．详细设计214.5．程序代码404.6．运行结果与测试584.7．设计体会与总结65322五、课设总结6523723六、参考文献66一、第一类题目（宋体，四号，加粗）问题陈述（宋体，小四，单倍行距）串的模式匹配：字符串模式匹配算法是入侵检测系统中的一种重要算法。通过对算法KMP分析,该算法通过每次匹配失败时特殊位置上字符的启发来获得字符串向后移动的可能距离,这个距离由定义的一个统一函数求出,取其中的最大值作为字符串向后移动的实际距离。实验结果表明,该算法能减少模式匹配中字符的比较次数和尝试次数,提高模式匹配的效率。程序代码#include"stdio.h"#include"string.h"typedefcharDataType;voidGetNext(DataType*t,int*next,inttlength)//求模式串t的next函数值并存入数组next{ inti=1,j=0;//定义整型变量i,j next[1]=0;//初始化存放部分匹配数组的next的第一项为-1 while(i<tlength)//当i小于字符串的长度时，执行循环 { if(j==0||t[i]==t[j])//如果j刚开始循环或者i和j表示的字符相同时 { ++i;++j;//i和j都自增，即增加到next中i位置的后一位，而j的增加也表示与i表示的字符相符的个数加1 if(t[i]!=t[j])//如果此时模式串中的i和j位置的字符不等 next[i]=j;//将j的值赋给next数组，便于直接比较目标串s与t在next[j]处的值 else//如果模式串中的i和j位置的字符仍然相等 next[i]=next[j];//将j的next中的值赋给i所在位置的值，这样能够保证后面比较目标串和字串时，直接比较t在next[j]处的值，而不需要比较t在j处的值 } else//如果i和j对应的字符不相同 j=next[j];//继续后续比较 }}intIndexKmp(DataType*s,DataType*t,intpos,inttlength,intslength,int*next)//利用模式串t的next函数求t在主串s中第pos个字符之后的位置{ inti=pos,j=1;//定义整型变量i,j while(i<=slength&&j<=tlength)//当i和j都未到达字符串末端时 { if(j==0||s[i]==t[j])//如果j刚开始比较或者模式串和目标串对应的字符相等时 { ++i;++j;//i和j均往后移动，比较后续字符 } else j=next[j];//否则，保持i不变，将j右滑动到下一个部分匹配位置 } if(j>tlength)//如果j的大小都大于t（模式串）的长度，说明能够找到匹配的位置 returni-tlength;//返回此时i的值减去t（模式串）的长度得到t在对应的s前方还有几个字符，即为它们的匹配位置 else return0;//否则，即为找不到匹配，返回0}intmain(intargc,char*argv[]){ intlocate,tlength,slength;//定义整型变量表示它们的匹配和两个字符串的长度 intnext[256];//定义存放它们部分匹配数值的数组 DataTypes[256],t[256];//定义字符数组s，t printf("请输入第一个串(母串):"); slength=strlen(gets(s+1));//目标串长度 printf("请输入第二个串(母串):"); tlength=strlen(gets(t+1));//模式串长度 GetNext(t,next,tlength);//求部分匹配数组next locate=IndexKmp(s,t,0,tlength,slength,next);//求出它们的具体匹配位置 printf("匹配位置:%d\n",locate); return0;}运行结果（1）能够找到匹配（2）不能找到匹配位置时间复杂度O（m+n)4．设计体会与总结串匹配算法虽然发展了几十年，然而非常实用的算法是近年才出现。串匹配问题的研究存在理论研究和实际应用的脱节。那些专门从事算法研究的学者关心的只是理论上看起来很美妙的算法——具有很好的时间复杂度。而本程序运用的是KMP算法，即保证其中一个字符串时另一个字符串的子串，利用next数组保存部分匹配的信息。实际上，模式串中的部分匹配信息就是真子串。通过观察串的模式匹配的算法，大致了解他的一般步骤，令s为目标串，t为模式串，设i指针和j指针，若s的i指针和t的j指针指向的字符相同，则指针加1，接着比较后面的字符是否相同，若不相同，则保持i不变，将j指针右移，比较是否相同，知道比较完整个字符串为止。而且知道KMP算法的时间复杂度为O（n+m)，所以这种算法不仅时间复杂度低，而且便于理解。另外，我们在掌握串的匹配模式时，还应该关注串的一些基本运算，理解串的基本概念和特征的基础，了解串的内部表示和处理方法。字符串时一种特殊的线性表。特殊之处在于表中的每一个元素都是，在串的基本操作中，有联接，求串长、求子串、比较串的大小、串的插入、删除、子串的定位和置换。二、第二类题目（宋体，四号，加粗）1．问题陈述（宋体，小四，单倍行距）给定一个计算机网络以及机器间的双向连线列表，每一条连线允许两端的计算机进行直接的文件传输，其他计算机间若存在一条连通路径，也可以进行间接的文件传输。请写出程序判断：任意指定两台计算机，它们之间是否可以进行文件传输？2．需求分析输入要求：输入若干测试数据组成。对于每一组测试，第1行包含一个整数N（≤10000），即网络中计算机的总台数，因而每台计算机可用1到N之间的一个正整数表示。接下来的几行输入格式为IC1C2或者C或者CC1C2或者S，其中C1和C2是两台计算机的序号，I表示在C1和C2间输入一条连线，C表示检查C1和C2间是否可以传输文件，S表示该组测试结束。当N为0时，表示全部测试结束，不要对该数据做任何处理。输出要求：对每一组C开头的测试，检查C1和C2间是否可以传输文件，若可以，则在一行中输出“yes”，否则输出“no”。当读到S时，检查整个网络。若网络中任意两机器间都可以传输文件，则在一行中输出“Thenetworkisconnected.”，否则输出“Therearekcomponents.”,其中k是网络中连通集的个数。两组测试数据之间请输出一空行分隔。概要设计设计框架mainmainfindInitfindInithebin(1)初始化树类型的并查集voidinit(intn)(2)查找元素所在集合每棵树表示一个集合，树的根作为集合的“代表元”。对于Find操作，实际上沿着父指针向上找到根即可。find(inte)//路径压缩寻找祖先时我们一般采用递归查找，但是当元素很多亦或是整棵树变为一条链时，每次Find(x)都是O(n)的复杂度，为减小这个复杂度用路径压缩，即当我们经过"递推"找到祖先节点后，"回溯"的时候顺便将它的子孙节点都直接指向祖先，这样以后再次Find(x)时复杂度就变成O(1)了。find（inte）(3)合并分离的两个树对于hebin操作，分别找到A,B的代表元size[A],size[B]，如果size[A]=size[B]，不进行任何操作。否则令parent[B]=A，或parent[A]=B，即可把两棵树合并hebin(intA,intB)（4）main（）主函数4．详细设计原理：在查找祖先时，找到后对路径上的所有节点，修改其父亲，使它直接连接根结点。正确性证明：设x所在集合的根结点为p，在Father(x)的路径上的某节点为y，当找到p=Father(x)后，因为途经y节点并且，所以必调用了Father(y)来找p,所以Father(y)必然为p。当使fa[y]=p后，Father(y)仍然是p，所以不会改变y点的基本属性，这种做法是可行的。(1)初始化并查集A.数组voidinit(intn){for(inti=1;i<=n;++i){parent[i]=i;size[i]=1;}}B.结构体voidMAKE_SET(UFStreet[],intN){ inti;//定义整型变量 for(i=1;i<=N;i++)//当个数小于输入的N时循环 { t[i].data=i;//数据为该人的编号 t[i].rank=0;//秩初始化为0 t[i].parent=i;//双亲初始化指向自己 }}结构体定义typedefstructnode { intdata;//节点对应人的编号 intrank;//节点对应秩 intparent;//定义双亲节点 }UFStree;(2)find（inte）A.数组每棵树表示一个集合，树的根作为集合的“代表元”。对于Find操作，实际上沿着父指针向上找到根即可。find(inte)//路径压缩{if(e==parent[e])returne;parent[e]=find(parent[e]);returnparent[e];}//这里用递归实现，每次查询的时间复杂度是树的深度，约为O(1)。B.结构体intFIND_SET(UFStreet[],intx)//在x所在的子树中查找集合编号{if(x!=t[x].parent)//双亲不是自己return(FIND_SET(t,t[x].parent));//递归在双亲中找xelse//双亲是自己，即为只有本身一个元素 returnx;//返回x}(3)hebin(intA,intB)A.数组对于hebin操作，分别找到A,B的代表元size[A],size[B]，如果size[A]=size[B]，不进行任何操作。否则令parent[B]=A，或parent[A]=B，即可把两棵树合并。hebin(intA,intB){if(size[A]>=size[B]){size[A]+=size[B];parent[B]=A;}else{size[B]+=size[A];parent[A]=B;}}B.结构体voidUNION(UFStreet[],intx,inty)//合并x和y所在的子树 { x=FIND_SET(t,x);//在x所在的子树中查找集合编号 y=FIND_SET(t,y);//在y所在的子树中查找集合编号 if(t[x].rank>t[y].rank)//y节点的秩小于x节点的秩 t[y].parent=x;//将y连接到x节点上，x作为y的双亲节点 else//y节点的秩大于等于x节点的秩 { t[x].parent=y;//将x连接到y节点上，y作为x的双亲节点 if(t[x].rank==t[y].rank)//x和y节点的秩相同 t[y].rank++;//y节点的秩增加1 } }（4）main主函数A.数组intmain(){intn,count;//定义整型变量intu,v,r1,r2;//定义两台电脑为u,v，他们的编号为r1,r2charoper;//定义字符型变量printf("请输入网络中计算机的总台数：");while(scanf("%d",&n)!=EOF)//当输入的n不为-1，执行循环{if(n==0)break;//当n为0时，全部测试结束 if(n<1||n>MAX)//网络中计算机的总台数N（≤10000），不在范围内即为越界 { printf("数据越界，请重新输入!"); continue;//结束本次循环，重新输入 }init(n);//初始化并查集printf("请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：\n");while(scanf("%s",&oper)!=EOF)//从键盘上输入字符，当不为-1时，执行循环 {if(oper!='S'&&oper!='C'&&oper!='I')//如果不为S,C,I中的一个，则命令错误 { printf("命令错误，请重新输入!"); continue;//结束本次循环，重新输入 }if(oper=='I')//输入为I，表示在两台计算机之间输入一条连线{printf("请输入两台计算机的序号：");scanf("%d%d",&u,&v);//从键盘上输入两个计算机的编号hebin(u,v);//合并包含A，B元素的集合printf("请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：\n");}elseif(oper=='C')//当输入为C时，判断两个计算机之间能否传输文件，即是否连通{printf("请输入两台计算机的序号：");scanf("%d%d",&u,&v);//从键盘上输入两个计算机的编号r1=find(u);//在u所在的子树中查找集合编号r2=find(v);//在v所在的子树中查找集合编号if(r1!=r2)//如果集合编号不相同 {printf("no\n");//则表示两个计算机之间不能传输文件printf("请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：\n"); }else//如果集合编号相同 {printf("yes\n");//则表示两个计算机之间能够传输文件printf("请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：\n"); }}elseif(oper=='S')//当输入为S时，表示本组测试结束{count=0;//初始化count为0for(inti=1;i<=n;++i){if(i==parent[i])//如果在e的值等于双亲数组中e位置的值，表示集合中只有e一个元素count++;//则统计计算机数的count自增}if(count==1)//如果count为1，则表示所有计算机在同一个集合，计算机之间连通 {printf("Thenetworkisconnected\n\n");//表示网络的计算机之间可以互相传输文件printf("\n请输入网络中计算机的总台数："); }else//如果count的值不为1，则输出网络中有几个分离集合树 {printf("Thereare%dcomponents\n\n",count);//输出并查集中的分离集合树的数目printf("\n请输入网络中计算机的总台数："); }break;}}}return0;}B.结构体voidmain(){intn,count;//定义整型变量n，countintu,v,r1,r2;//定义两台电脑为u,v，他们的编号为r1,r2charoper;//定义字符型变量 UFStreet[MAX+1];//定义树类型的并查集printf("请输入网络中计算机的总台数：");while(scanf("%d",&n)!=EOF)//当输入的n不为-1，执行循环{if(n==0)break;//当n为0时，全部测试结束 if(n<1||n>MAX)//网络中计算机的总台数N（≤10000），不在范围内即为越界 { printf("数据越界，请重新输入!"); continue;//结束本次循环，重新输入 } MAKE_SET(t,n);//初始化并查集printf("请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：\n");while(scanf("%s",&oper)!=EOF)//从键盘上输入字符，当不为-1时，执行循环{ if(oper!='S'&&oper!='C'&&oper!='I')//如果不为S,C,I中的一个，则命令错误 { printf("命令错误，请重新输入!"); continue;//结束本次循环，重新输入 }if(oper=='I')//输入为I，表示在两台计算机之间输入一条连线{printf("请输入两台计算机C1,C2的序号：");scanf("%d%d",&u,&v);//从键盘上输入两个计算机的编号UNION(t,u,v);//合并两个计算机集合printf("请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：\n");} elseif(oper=='C')//当输入为C时，判断两个计算机之间能否传输文件，即是否连通{printf("请输入两台计算机C1,C2的序号：");scanf("%d%d",&u,&v);//从键盘上输入两个计算机的编号r1=FIND_SET(t,u);//在x所在的子树中查找集合编号r2=FIND_SET(t,v);//在y所在的子树中查找集合编号if(r1!=r2)//如果集合编号不相同 {printf("no\n");//则表示两个计算机之间不能传输文件printf("请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：\n"); }else//如果集合编号相同 {printf("yes\n");//则表示两个计算机之间能够传输文件printf("请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：\n"); }}elseif(oper=='S')//当输入为S时，表示本组测试结束{count=0;//初始化count为0for(inti=1;i<=n;++i){if(i==t[i].parent)//如果双亲节点指向自己，则表示根节点count++;//则统计计算机数的count自增}if(count==1)//如果count为1，则表示所有计算机拥有同一个根，计算机之间连通 {printf("Thenetworkisconnected\n\n");//表示网络的计算机之间可以互相传输文件printf("\n\n请输入网络中计算机的总台数："); }else//如果count的值不为1，则输出网络中有几个分离集合树 {printf("Thereare%dcomponents\n\n",count);//输出并查集中的分离集合树的数目printf("\n\n请输入网络中计算机的总台数："); }break;}}}}5．程序代码(1)数组#include<stdio.h>#defineMAX10001//定义MAX常量intparent[MAX];//定义双亲数组intsize[MAX];//定义树的高度数组//初始化voidinit(intn){for(inti=1;i<=n;++i)//当i小于输入的计算机台数，执行循环{parent[i]=i;//将i的值赋给双亲数组，初始化size[i]=1;//将树的高度初始化为1}}voidhebin(intA,intB)//元素少的集合合并到元素多的集合中,降低树的高度{if(size[A]>=size[B])//如果保存A的数组的大小大于等于保存B的数组{size[A]+=size[B];//将保存A的数组大小扩大到A和B的数组之和parent[B]=A;//将A添加到B的双亲数组中，即将A作为B的双亲}else//如果保存A的数组的小于等于保存B的数组{size[B]+=size[A];//将保存B的数组大小扩大到A和B的数组之和parent[A]=B;//将B添加到A的双亲数组中，即将B作为A的双亲}}//在集合中找元素intfind(inte)//路径压缩{if(e==parent[e])//如果在e的值等于双亲数组中e位置的值，表示集合中只有e一个元素returne;//则返回元素e，也是e集合parent[e]=find(parent[e]);//如果，e的值与双亲中e的值不等，表明还有其他元素，递归在双亲数组中找ereturnparent[e];//返回包含元素e的集合}intmain(){intn,count;//定义整型变量intu,v,r1,r2;//定义两台电脑为u,v，他们的编号为r1,r2charoper;//定义字符型变量printf("请输入网络中计算机的总台数：");while(scanf("%d",&n)!=EOF)//当输入的n不为-1，执行循环{if(n==0)break;//当n为0时，全部测试结束 if(n<1||n>MAX)//网络中计算机的总台数N（≤10000），不在范围内即为越界 { printf("数据越界，请重新输入!"); continue;//结束本次循环，重新输入 }init(n);//初始化并查集printf("请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：\n");while(scanf("%s",&oper)!=EOF)//从键盘上输入字符，当不为-1时，执行循环 {if(oper!='S'&&oper!='C'&&oper!='I')//如果不为S,C,I中的一个，则命令错误 { printf("命令错误，请重新输入!"); continue;//结束本次循环，重新输入 }if(oper=='I')//输入为I，表示在两台计算机之间输入一条连线{printf("请输入两台计算机的序号：");scanf("%d%d",&u,&v);//从键盘上输入两个计算机的编号hebin(u,v);//合并包含A，B元素的集合printf("请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：\n");}elseif(oper=='C')//当输入为C时，判断两个计算机之间能否传输文件，即是否连通{printf("请输入两台计算机的序号：");scanf("%d%d",&u,&v);//从键盘上输入两个计算机的编号r1=find(u);//在u所在的子树中查找集合编号r2=find(v);//在v所在的子树中查找集合编号if(r1!=r2)//如果集合编号不相同 {printf("no\n");//则表示两个计算机之间不能传输文件printf("请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：\n"); }else//如果集合编号相同 {printf("yes\n");//则表示两个计算机之间能够传输文件printf("请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：\n"); }}elseif(oper=='S')//当输入为S时，表示本组测试结束{count=0;//初始化count为0for(inti=1;i<=n;++i){if(i==parent[i])//如果在e的值等于双亲数组中e位置的值，表示集合中只有e一个元素count++;//则统计计算机数的count自增}if(count==1)//如果count为1，则表示所有计算机在同一个集合，计算机之间连通 {printf("Thenetworkisconnected\n\n");//表示网络的计算机之间可以互相传输文件printf("\n请输入网络中计算机的总台数："); }else//如果count的值不为1，则输出网络中有几个分离集合树 {printf("Thereare%dcomponents\n\n",count);//输出并查集中的分离集合树的数目printf("\n请输入网络中计算机的总台数："); }break;}}}return0;}(2)结构体#include<stdio.h>#defineMAX10000typedefstructnode { intdata;//节点对应人的编号 intrank;//节点对应秩 intparent;//定义双亲节点 }UFStree;//定义并查集的节点类型为树//初始化并查集树voidMAKE_SET(UFStreet[],intN){ inti;//定义整型变量 for(i=1;i<=N;i++)//当个数小于输入的N时循环 { t[i].data=i;//数据为该人的编号 t[i].rank=0;//秩初始化为0 t[i].parent=i;//双亲初始化指向自己 } } //查找一个元素所属的集合，路径压缩intFIND_SET(UFStreet[],intx)//在x所在的子树中查找集合编号{if(x!=t[x].parent)//双亲不是自己return(FIND_SET(t,t[x].parent));//递归在双亲中找xelse//双亲是自己，即为只有本身一个元素 returnx;//返回x}//元素少的集合合并到元素多的集合中,降低树的高度voidUNION(UFStreet[],intx,inty)//合并x和y所在的子树 { x=FIND_SET(t,x);//在x所在的子树中查找集合编号 y=FIND_SET(t,y);//在y所在的子树中查找集合编号 if(t[x].rank>t[y].rank)//y节点的秩小于x节点的秩 t[y].parent=x;//将y连接到x节点上，x作为y的双亲节点 else//y节点的秩大于等于x节点的秩 { t[x].parent=y;//将x连接到y节点上，y作为x的双亲节点 if(t[x].rank==t[y].rank)//x和y节点的秩相同 t[y].rank++;//y节点的秩增加1 } }voidmain(){intn,count;//定义整型变量n，countintu,v,r1,r2;//定义两台电脑为u,v，他们的编号为r1,r2charoper;//定义字符型变量 UFStreet[MAX+1];//定义树类型的并查集printf("请输入网络中计算机的总台数：");while(scanf("%d",&n)!=EOF)//当输入的n不为-1，执行循环{if(n==0)break;//当n为0时，全部测试结束 if(n<1||n>MAX)//网络中计算机的总台数N（≤10000），不在范围内即为越界 { printf("数据越界，请重新输入!"); continue;//结束本次循环，重新输入 } MAKE_SET(t,n);//初始化并查集printf("请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：\n");while(scanf("%s",&oper)!=EOF)//从键盘上输入字符，当不为-1时，执行循环{ if(oper!='S'&&oper!='C'&&oper!='I')//如果不为S,C,I中的一个，则命令错误 { printf("命令错误，请重新输入!"); continue;//结束本次循环，重新输入 }if(oper=='I')//输入为I，表示在两台计算机之间输入一条连线{printf("请输入两台计算机C1,C2的序号：");scanf("%d%d",&u,&v);//从键盘上输入两个计算机的编号UNION(t,u,v);//合并两个计算机集合printf("请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：\n");} elseif(oper=='C')//当输入为C时，判断两个计算机之间能否传输文件，即是否连通{printf("请输入两台计算机C1,C2的序号：");scanf("%d%d",&u,&v);//从键盘上输入两个计算机的编号r1=FIND_SET(t,u);//在u所在的子树中查找集合编号r2=FIND_SET(t,v);//在v所在的子树中查找集合编号if(r1!=r2)//如果集合编号不相同 {printf("no\n");//则表示两个计算机之间不能传输文件printf("请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：\n"); }else//如果集合编号相同 {printf("yes\n");//则表示两个计算机之间能够传输文件printf("请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：\n"); }}elseif(oper=='S')//当输入为S时，表示本组测试结束{count=0;//初始化count为0for(inti=1;i<=n;++i){if(i==t[i].parent)//如果双亲节点指向自己，则表示根节点count++;//则统计计算机数的count自增}if(count==1)//如果count为1，则表示所有计算机拥有同一个根，计算机之间连通 {printf("Thenetworkisconnected\n\n");//表示网络的计算机之间可以互相传输文件printf("\n\n请输入网络中计算机的总台数："); }else//如果count的值不为1，则输出网络中有几个分离集合树 {printf("Thereare%dcomponents\n\n",count);//输出并查集中的分离集合树的数目printf("\n\n请输入网络中计算机的总台数："); }break;}}}}运行结果与测试（1）输入的台数超过10000和输入的字符不是C,S,I中的一个的错误查找和合并的时间复杂度是O（）(2)向两台计算机之间插入一条连线时，能够保证两个计算机之间能够传输文件,同时，发现，输入S，表示本组数据测试结束时，在并查集中有两个分离集合树，因为1,2序号的两台计算机已经连接，之间可以相互传输文件，但网络中总共3个计算机，而另一个计算机还没有声明，所以，不管他是什么，都单独作为一个集合，因此，得到并查集中有两个分离的树第一行，先输入网络中计算机的总台数，然后检查1,2电脑是否可以传输文件，结果是不可以，然后，在1和2中输入一条连接，从而连接两个电脑，再输入C判断两个电脑之间可以传输文件。再输入S表示这组测试结束，发现这个网络中拥有两个部分。第二次，同样，还是3台电脑，先在1,3输入一条连线，然后，在2,3之间输入一条连线，保证他们之间都能传输文件，最后输入S得到三台电脑相互之间都能传输文件，即网络互通。7．设计体会与总结并查集，顾名思义，就是合并A，B所在的集合，反复查找元素所在集合。两棵分离集合树A，B，通过比较他们树的深度，将深度较小的作为子树，合并得到的分离集合树是一棵比较平衡的树，对应的查找与合并的时间复杂度也就稳定在O（log2n）。通过对并查集的编写，了解了并查集的初始化，利用递归查找一个元素所属的集合，合并两个元素所属的集合，也明白并查集的算法是由树实现的。因为并查集本身不具有结构，要借助一定的数据结构。并查集反应的是一种亲戚关系，本程序先判断1和2电脑无联系，再通过在电脑之间输入一条连线，即输入I，建立他们的关系，然后输入S，判断他们有几个构成部分。并且，本例中，先是1,2建立关系，后来在3,1之间输入一条连线，另外，在2,3之间也输入一条连线，导致存放并查集树的数组的的每个元素，即1,2,3的双亲都指向自己，所以，整个网络都联通，也表示他们之间都有关系。最后，只要控制输入为S就表示这组测试已经结束，就能够判断这个网络的关系，最后，只要保证输入的总台数为0，从而保证输入结束，整个程序结束。三、第三类题目（宋体，四号，加粗）1．问题陈述（宋体，小四，单倍行距）针对某一种行业的库房的产品进销存情况进行管理。(1)采用一定的存储结构对库房的货品及其数量进行分类管理；(2)可以进行产品类的添加、产品的添加、产品数量的添加；(3)能够查询库房每种产品的总量、进货日期、销出数量、销售时间等；2．需求分析进入系统后，管理员就可以对产品的进货，销售，存货等方面的信息有个详细的了解。并且可以对产品的类，产品，产品的数量,产品销售信息进行管理，可以添加新的产品信息。同时对库房每种产品的总量、进货日期、销出数量、销售时间等也可以有详细的了解。运用链表进行存储，同时用到指针变量，运用循环存储，对存储产品的信息要用到日期结构体和产品结构体，对存储要用到文件指针以及文件法的使用。要找到链表的指针变量，对指针变量进行修改，然后再进行产品的出入。定义一个查询函数，对产品类的指针变量进行循环查询，再对产品的指针变量进行循环查询，找到产品时，在调用显示产品信息函数，显示查询到的产品的各项信息。3.概要设计为了能够提高内存的利用及各功能的实现，程序主要使用了：线性表的链式存储，分配存储空间，空间可扩展性强，方便频繁的录入、插入、查找、删除和排序等而不占用多余的内存。（主要应用）文件文本的读取与写入，为了方便用户更加快速的执行管理操作。结构体的定义，定义了产品结构体和日期结构体。登录用户时的字符串读取及验证（1）录入产品函数LinkListgoods_input()//运用链式存储产品信息写入文件的函数voidfile_write(Node*p)文件中的信息读出的函数LinkListfile_read()（2）查找产品函数voidgoods_find()（3）修改信息函数voidgoods_change()（4）插入产品函数voidgoods_insert()（5）删除产品函数voidgoods_delete()（6）产品信息排序函数voidgoods_rank()（7)产品信息统计函数voidvoidgoods_tongji()（8）注册、登陆及密码保护函数voidapply()intload()voidkey（）（9）主函数voidmain()设计框架主菜单主菜单统计产品信息产品信息排序删除产品信息插入产品信息修改产品信息查找产品信息录入产品品信息统计产品信息产品信息排序删除产品信息插入产品信息修改产品信息查找产品信息录入产品品信息程序流程图开始开始修改产品信息查找产品信息录入产品品信息删除产品信息插入产品信息根据a的值选择相应的函数操作输入0~7修改产品信息查找产品信息录入产品品信息删除产品信息插入产品信息根据a的值选择相应的函数操作输入0~7选0选0退出退出产品信息排序统计产品信息产品信息排序统计产品信息结束结束4．详细设计（1）录入产品函数LinkListgoods_input()//运用链式存储数据录入是该软件必备的基本功能当链表为空时，对产品信息变量“产品号”判断并进行录入，系统调用录入函数，在用户输入产品信息后添加到链表里，在添加过程中按提示自动插入到相应位置。添加成功后，返回主菜单并提示用户保存到自建的文本中，并可以根据各个模块要求进行读取修改。LinkListgoods_input(){LinkListL;Node*p1,*p2;inti=1;voidfile_write(Node*p);intflag=1;L=p2=(Node*)malloc(sizeof(Node));//为头节点分配存储空间while(flag){ p1=(Node*)malloc(sizeof(Node));printf("请输入第%d种产品的信息(产品号为0时,结束产品输入):\n\n",i++); flushall(); printf("产品号:"); scanf("%ld",&p1->num); if(p1->num!=0) { flushall();//i/o库函数清除缓冲 printf("名称:"); scanf("%s",&p1->name); flushall(); printf("类别:"); scanf("%s",&p1->kind); flushall(); printf("生产日期(年★月★日用空格隔开):"); scanf("%d%d%d",&p1->pro_date.year,&p1->pro_date.month,&p1->pro_date.day); flushall(); printf("保质期:"); scanf("%d",&p1->save_day); flushall(); printf("产品总量:"); scanf("%d",&p1->zongliang);flushall(); printf("产品销量:"); scanf("%d",&p1->xiaoliang); flushall(); printf("进价:");scanf("%f",&p1->jinjia); flushall(); printf("售价:"); scanf("%f",&p1->shoujia); flushall();printf("销售日期(年☆月☆日用空格隔开):"); scanf("%d%d%d",&p1->sale_date.year,&p1->sale_date.month,&p1->sale_date.day); p2->next=p1; p2=p1; } else { flag=0; break; }}p2->next=NULL;file_write(L);free(p1);return(L);}产品信息写入文件的函数voidfile_write(Node*p)利用fprintf将信息输入到文件中，从而进行保存。文件是创建在E盘，以文本文档形式呈现的文件。voidfile_write(Node*p){FILE*fp; intc; printf("是否保存?(保存按1;不保存按0):");scanf("%d",&c); if(c==1) {flushall(); fp=fopen("E:\\产品.txt","w");//文件写入if(fp==NULL) { printf("\nthisfilecannotbeopen!"); exit(1); }p=p->next; while(p!=NULL) { fprintf(fp,"%ld%s%s%d%d%d%d%d%d%f%f%d%d%d\n",p->num,p->name,p->kind,p->pro_date.year,p->pro_date.month,p->pro_date.day,p->save_day,p->zongliang,p->xiaoliang,p->jinjia,p->shoujia,p->sale_date.year,p->sale_date.month,p->sale_date.day); p=p->next; } fclose(fp); printf("文件保存成功!"); }}文件中的信息读出的函数LinkListfile_read()利用fscanf进行对文件中信息的读写，文件是创建在E盘，以文本文档形式呈现的文件。LinkListfile_read(){ FILE*fp; LinkListL;Node*p1,*p2; inti,k=0,t=-2; flushall(); printf("请输入此时产品的总数:"); scanf("%d",&i);fp=fopen("E:\\产品.txt","r");//文件读出L=p2=(Node*)malloc(sizeof(Node));//为头节点分配存储空间while(t!=EOF&&k<i) { p1=(Node*)malloc(sizeof(Node)); t=fscanf(fp,"%ld%s%s%d%d%d%d%d%d%f%f%d%d%d",&p1->num,p1->name,p1->kind,&p1->pro_date.year,&p1->pro_date.month,&p1->pro_date.day,&p1->save_day,&p1->zongliang,&p1->xiaoliang,&p1->jinjia,&p1->shoujia,&p1->sale_date.year,&p1->sale_date.month,&p1->sale_date.day); p2->next=p1; p2=p1; k++; } p2->next=NULL; fclose(fp); returnL;}（2）查找产品函数voidgoods_find()查找产品是信息管理的基本功能，当数据很多时怎么快速找到产品对管理员来说很重要，系统调用查找函数模块，显示查找菜单。根据提示输入需要查找的“产品号”进行查找，查找成功，用户会看到查找产品的详细信息，如没有该产品，则查找失败，查找函数设计：voidgoods_find(){ longsnum; intflag=0,t; Node*p0,*p1; p1=p0=file_read(); while(1) { flag=0; printf("请输入你要查找的产品信息的产品号:"); scanf("%ld",&snum); while(p0->next!=NULL) { p0=p0->next; if(p0->num==snum) { flag=1; break; } } if(flag==1) {printf("☆★该产品的信息如下:\n\n"); printf("产品号名称类别生产日期保质期总量销量进价售价销售日期\n"); printf("%3d%8s%5s%6d-%02d-%02d%5d%5d%6d%8.2f%8.2f%6d-%02d-%02d\n",p0->num,p0->name,p0->kind,p0->pro_date.year,p0->pro_date.month,p0->pro_date.day,p0->save_day,p0->zongliang,p0->xiaoliang,p0->jinjia,p0->shoujia,p0->sale_date.year,p0->sale_date.month,p0->sale_date.day); } else printf("☆★此产品号不存在,查找失败!★☆\n");p0=p1; printf("结束查找按0,继续查找按1:"); scanf("%d",&t); if(t==0) break; }}（3）修改信息函数voidgoods_change()主函数能够调用修改函数，先打开E盘中的产品文本，输入要修改的产品号，如果能够与文件中的产品号匹配，则用switch又抛出几个选项，分别修改文件中产品的各项信息。最后，再将修改后的结果存放在产品文本文档中。voidgoods_change(){Node*p1,*p0,*p2;intc,flag=0,t; longsnum; p2=p0=file_read(); while(1){ flag=0; p1=p0->next; if(p1==NULL)flag=0; printf("请输入你要修改的产品信息的产品号:"); scanf("%ld",&snum); while(p1!=NULL) { if(p1->num==snum) { flag=1; break; } p1=p1->next; } if(flag==1) { printf("☆1:产品号;\n"); printf("☆2:产品名称;\n"); printf("☆3:产品类别;\n");printf("☆4:产品生产日期;\n");printf("☆5:产品保质期;\n"); printf("☆6:产品总量\n");printf("☆7:产品销量\n"); printf("☆8:产品进价\n"); printf("☆9:产品售价\n"); printf("☆10:产品销售日期\n"); printf("☆★请选择修改的内容(1~9):"); scanf("%d",&c); while(1) { if(c==1||c==2||c==3||c==4||c==5||c==6||c==7||c==8||c==9||c==10)break; else { printf("\n输入有误,请重新输入!\n清选择(1~9):");scanf("%d",&c); if(c==1||c==2||c==3||c==4||c==5||c==6||c==7||c==8||c==9||c==10)break; } } switch(c) { case1: { printf("\n输入修改后的产品号:"); scanf("%ld",&p1->num);break; } case2: { printf("输入修改后的产品名:"); scanf("%s",&p1->name);break; } case3: { printf("输入修改后的产品类别:"); scanf("%s",&p1->kind);break; } case4: { printf("输入修改后的产品生产日期(年★月★日之间用空格隔开):"); scanf("%d%d%d",&p1->pro_date.year,&p1->pro_date.month,&p1->pro_date.day);break; } case5: { printf("输入修改后的产品保质期:"); scanf("%d",&p1->save_day);break; } case6: { printf("输入修改后的产品总量:"); scanf("%d",&p1->zongliang);break; }case7: { printf("输入修改后的产品销量:"); scanf("%d",&p1->xiaoliang);break; } case8: { printf("输入修改后的产品进价:"); scanf("%f",&p1->