数据结构课程设计报告-大学论文.doc

数据结构课程设计学院名称： 计算机工程学院 专 业： 信息管理与信息系统 班 级： 姓 名： 2015 年 1 月 7 日 目录一、数据结构课程设计报告要求.1 二、第一类题目.22.1 问题陈述.2 2.2程序代码.2 2.3运行结果.4 2.4设计体会与总结.4 三、第二类题目.4 3.1问题陈述.4 3.2需求分析.5 3.3概要设计.5 3.4详细设计.6 3.5程序代码.7 3.6运行结果与测试.18 3.7设计体会与总结.19四、第三类题目.20 4.1问题陈述.20 4.2需求分析.20 4.3概要设计.20 4.4详细设计.21 4.5程序代码.40 4.6运行结果与测试.58 4.7设计体会与总结.65五、课设总结.65六、参考文献.66数据结构课程设计报告要求 一、第一类题目（宋体，四号，加粗） 1问题陈述（宋体，小四，单倍行距） 2程序代码 3运行结果 4设计体会与总结 二、第二类题目（宋体，四号，加粗） 1问题陈述（宋体，小四，单倍行距） 2需求分析 3概要设计 4详细设计 5程序代码 6运行结果与测试 7设计体会与总结 三、第三类题目（宋体，四号，加粗） 1问题陈述（宋体，小四，单倍行距） 2需求分析 3概要设计 4详细设计 5程序代码 6运行结果与测试 7设计体会与总结 四、要求 1标题为字体黑体，小三，居中 2小标题为宋体，四号，加粗 3正文要求为宋体，小四，单倍行距 4每个段落缩进2个汉字（4个空格） 5每个人报告书不得雷同，尤其第二类与第三类题目，发现雷同者一律按 不及格论处。 6相关内容可以参考数据结构课程设计指导书，但不得抄袭相关内容。0 一、第一类题目（宋体，四号，加粗）1 问题陈述（宋体，小四，单倍行距） 串的模式匹配： 字符串模式匹配算法是入侵检测系统中的一种重要算法。通过对算法 KMP分析,该算法通过每次匹配失败时特殊位置上字符的启发来获得字符串向后移动的可能距离,这个距离由定义的一个统一函数求出,取其中的最大值作为字符串向后移动的实际距离。实验结果表明,该算法能减少模式匹配中字符的比较次数和尝试次数,提高模式匹配的效率。 2 程序代码#include"stdio.h" #include"string.h" typedef char DataType; void GetNext(DataType *t,int *next,int tlength)/求模式串t的next函数值并存入数组next int i=1,j=0; /定义整型变量i,j next1=0; /初始化存放部分匹配数组的next的第一项为-1 while(i<tlength) /当i小于字符串的长度时，执行循环 if(j=0|ti=tj) /如果j刚开始循环或者i和j表示的字符相同时 +i;+j; /i和j都自增，即增加到next中i位置的后一位，而j的增加也表示与i表示的字符相符的个数加1 if(ti!=tj) /如果此时模式串中的i和j位置的字符不等nexti=j; /将j的值赋给next数组，便于直接比较目标串s与t在nextj处的值 else /如果模式串中的i和j位置的字符仍然相等nexti=nextj; /将j的next中的值赋给i所在位置的值，这样能够保证后面比较目标串和字串时，直接比较t在nextj处的值，而不需要比较t在j处的值 else /如果i和j对应的字符不相同j=nextj; /继续后续比较 int IndexKmp(DataType *s,DataType *t,int pos,int tlength,int slength,int *next)/利用模式串t的next函数求t在主串s中第pos个字符之后的位置 int i=pos,j=1; /定义整型变量i,j while(i<=slength&&j<=tlength) /当i和j都未到达字符串末端时 if(j=0|si=tj) /如果j刚开始比较或者模式串和目标串对应的字符相等时 +i;+j; /i和j均往后移动，比较后续字符 elsej=nextj; /否则，保持i不变，将j右滑动到下一个部分匹配位置 if(j>tlength) /如果j的大小都大于t（模式串）的长度，说明能够找到匹配的位置 return i-tlength; /返回此时i的值减去t（模式串）的长度得到t在对应的s前方还有几个字符，即为它们的匹配位置 else return 0; /否则，即为找不到匹配，返回0 int main(int argc,char *argv) int locate,tlength,slength; /定义整型变量表示它们的匹配和两个字符串的长度int next256; /定义存放它们部分匹配数值的数组DataType s256,t256; /定义字符数组s，tprintf("请输入第一个串(母串):");slength=strlen(gets(s+1); /目标串长度printf("请输入第二个串(母串):");tlength=strlen(gets(t+1); /模式串长度GetNext(t,next,tlength); /求部分匹配数组nextlocate=IndexKmp(s,t,0,tlength,slength,next); /求出它们的具体匹配位置printf("匹配位置:%dn",locate);return 0; 3 运行结果 （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之间的一个正整数表示。接下来的几行输入格式为I C1 C2或者 C或者C C1C2或者S，其中C1和C2是两台计算机的序号，I表示在C1和C2间输入一条连线，C表示检查C1和C2间是否可以传输文件，S表示该组测试结束。当N为0时，表示全部测试结束，不要对该数据做任何处理。输出要求：对每一组C开头的测试，检查C1和C2间是否可以传输文件，若可以，则在一行中输出“yes”，否则输出“no”。当读到S时，检查整个网络。若网络中任意两机器间都可以传输文件，则在一行中输出“The network is connected.”，否则输出“There are k components.”,其中k是网络中连通集的个数。两组测试数据之间请输出一空行分隔。3. 概要设计 设计框架main findInithebin(1)初始化树类型的并查集 void init(int n)(2)查找元素所在集合每棵树表示一个集合，树的根作为集合的“代表元”。对于Find操作，实际上沿着父指针向上找到根即可。 find(int e)/路径压缩寻找祖先时我们一般采用递归查找，但是当元素很多亦或是整棵树变为一条链时，每次Find (x)都是O(n)的复杂度，为减小这个复杂度用路径压缩，即当我们经过"递推"找到祖先节点后，"回溯"的时候顺便将它的子孙节点都直接指向祖先，这样以后再次Find(x)时复杂度就变成O(1)了。find（int e）(3)合并分离的两个树对于hebin操作，分别找到A,B的代表元sizeA ,sizeB，如果sizeA = sizeB，不进行任何操作。否则令parentB = A，或parentA =B，即可把两棵树合并 hebin(int A, int B) （4）main（）主函数4详细设计 原理：在查找祖先时，找到后对路径上的所有节点，修改其父亲，使它直接连接根结点。正确性证明：设x所在集合的根结点为p，在Father(x)的路径上的某节点为y，当找到p=Father(x)后，因为途经y节点并且，所以必调用了Father(y)来找p,所以Father(y)必然为p。当使fay=p后，Father(y)仍然是p，所以不会改变y点的基本属性，这种做法是可行的。 (1)初始化并查集 A.数组 void init(int n) for (int i = 1; i <= n; +i) parenti = i; sizei = 1; B.结构体 void MAKE_SET(UFStree t,int N) int i; /定义整型变量for(i=1;i<=N;i+) /当个数小于输入的N时循环ti.data=i; /数据为该人的编号ti.rank=0; /秩初始化为0ti.parent=i; /双亲初始化指向自己 结构体定义 typedef struct node int data; /节点对应人的编号 int rank; /节点对应秩 int parent; /定义双亲节点 UFStree; (2) find（int e） A.数组 每棵树表示一个集合，树的根作为集合的“代表元”。对于Find操作， 实际上沿着父指针向上找到根即可。find(int e)/路径压缩 if (e = parente) return e; parente = find(parente); return parente; /这里用递归实现，每次查询的时间复杂度是树的深度，约为O(1)。B.结构体 int FIND_SET(UFStree t,int x) /在x所在的子树中查找集合编号 if (x!=tx.parent) /双亲不是自己 return(FIND_SET(t,tx.parent); /递归在双亲中找x else /双亲是自己，即为只有本身一个元素return x; /返回x (3)hebin(int A ,int B)A.数组对于hebin操作，分别找到A,B的代表元sizeA ,sizeB，如果sizeA = sizeB，不进行任何操作。否则令parentB = A，或parentA =B，即可把两棵树合并。hebin(int A, int B) if(sizeA >= sizeB) sizeA += sizeB; parentB = A; else sizeB += sizeA; parentA = B; B.结构体 void UNION(UFStree t,int x,int y) /合并x和y所在的子树 x=FIND_SET(t,x); /在x所在的子树中查找集合编号 y=FIND_SET(t,y); /在y所在的子树中查找集合编号 if(tx.rank>ty.rank) /y节点的秩小于x节点的秩 ty.parent=x; /将y连接到x节点上，x作为y的双亲节点 else /y节点的秩大于等于x节点的秩 tx.parent=y; /将x连接到y节点上，y作为x的双亲节点 if(tx.rank=ty.rank) /x和y节点的秩相同ty.rank+; /y节点的秩增加1 （4）main主函数 A.数组 int main() int n, count; /定义整型变量 int u, v, r1, r2; /定义两台电脑为u,v，他们的编号为r1,r2 char oper; /定义字符型变量 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"); else if (oper = 'C') /当输入为C时，判断两个计算机之间能否传输文件，即是否连通 printf("请输入两台计算机的序号："); scanf("%d %d", &u, &v);/从键盘上输入两个计算机的编号 r1 = find(u); /在u所在的子树中查找集合编号 r2 = find(v); /在v所在的子树中查找集合编号 if (r1 != r2) /如果集合编号不相同 printf("non"); /则表示两个计算机之间不能传输文件 printf("请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：n"); else /如果集合编号相同 printf("yesn"); /则表示两个计算机之间能够传输文件 printf("请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：n"); else if (oper = 'S') /当输入为S时，表示本组测试结束 count = 0; /初始化count为0 for (int i = 1; i <= n; +i) if (i = parenti) /如果在e的值等于双亲数组中e位置的值，表示集合中只有e一个元素 count+; /则统计计算机数的count自增 if (count = 1) /如果count为1，则表示所有计算机在同一个集合，计算机之间连通 printf("The network is connectednn"); /表示网络的计算机之间可以互相传输文件 printf("n请输入网络中计算机的总台数："); else /如果count的值不为1，则输出网络中有几个分离集合树 printf("There are %d componentsnn", count); /输出并查集中的分离集合树的数目 printf("n请输入网络中计算机的总台数："); break; return 0; B.结构体 void main() int n, count; /定义整型变量n，count int u, v, r1, r2; /定义两台电脑为u,v，他们的编号为r1,r2 char oper; /定义字符型变量 UFStree tMAX+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"); else if (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("non"); /则表示两个计算机之间不能传输文件 printf("请输入C（检查是否可以传输文件）、I（输入一 条连线）、S（该组测试结束）字符：n"); else /如果集合编号相同 printf("yesn"); /则表示两个计算机之间能够传输文件 printf("请输入C（检查是否可以传输文件）、I（输入一 条连线）、S（该组测试结束）字符：n"); else if (oper = 'S') /当输入为S时，表示本组测试结束 count = 0; /初始化count为0 for (int i = 1; i <= n; +i) if (i = ti.parent) /如果双亲节点指向自己，则表示根节点 count+; /则统计计算机数的count自增 if (count = 1) /如果count为1，则表示所有计算机拥有同一个根，计算机之间连通 printf("The network is connectednn"); /表示网络的计算机之间可以互相传输文件 pri