毕设论文-数据结构课程设计报告Word文件下载.docx
《毕设论文-数据结构课程设计报告Word文件下载.docx》由会员分享，可在线阅读，更多相关《毕设论文-数据结构课程设计报告Word文件下载.docx（70页珍藏版）》请在冰点文库上搜索。
二、第二类题目（宋体，四号，加粗）
2.需求分析
3.概要设计
4.详细设计
5.程序代码
6.运行结果与测试
7.设计体会与总结
三、第三类题目（宋体，四号，加粗）
四、要求
1.标题为字体黑体，小三，居中
2.小标题为宋体，四号，加粗
3.正文要求为宋体，小四，单倍行距
4.每个段落缩进2个汉字（4个空格）
5.每个人报告书不得雷同，尤其第二类与第三类题目，发现雷同者一律
按
不及格论处。
6.相关内容可以参考《数据结构课程设计》指导书，但不得抄袭相关内
容。
20
串的模式匹配：
字符串模式匹配算法是入侵检测系统中的一种重要算法。
通过对算法
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表示的字符相符的个数加1if（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,int
tlength,intslength,int*next）//利用模式串t的next函数求t在主串
s中第pos个字符之后的位置
量i,j
inti=pos,j=1;
//定义整型变
=slength&
&
j<
=tlength） //当i和j都
未到达字符串末端时
if（j==0||s[i]==t[j]） //如果j刚开
始比较或者模式串和目标串对应的字符相等时
//i和j均往
后移动，比较后续字符
else
//否则，保持
i不变，将j右滑动到下一个部分匹配位置
if（j>
tlength） //如果j的
大小都大于t（模式串）的长度，说明能够找到匹配的位置
returni-tlength;
//返回此时
i的值减去t（模式串）的长度得到t在对应的s前方还有几个字符，即为它们的匹配位置
return0;
//否则，即
为找不到匹配，返回0
intmain（intargc,char*argv[]）
intlocate,tlength,slength;
//定义整型变量表示它们的匹配和两个字符串的长度
intnext[256];
//定义存放
它们部分匹配数值的数组
DataTypes[256],t[256];
//定义字符数组s，t
printf（"
请输入第一个串（母串）:
"
）;
slength=strlen（gets（s+1））;
//目标串长
度
请输入第二个串（母串）:
tlength=strlen（gets（t+1））;
//模式串长
GetNext（t,next,tlength）;
//求部分匹
配数组next
locate=IndexKmp（s,t,0,tlength,slength,next）;
//求出它们
的具体匹配位置
匹配位置:
%d\n"
locate）;
return0;
（1）能够找到匹配
（2）不能找到匹配位置时间复杂度O（m+n）
串匹配算法虽然发展了几十年，然而非常实用的算法是近年才出现。
串匹配问题的研究存在理论研究和实际应用的脱节。
那些专门从事算法研究的学者关心的只是理论上看起来很美妙的算法——具有很好的时间复杂度。
而本程序运用的是KMP算法，即保证其中一个字符串时另一个字符串的子串，利用next数组保存部分匹配的信息。
实际上，模式串中的部分匹配信息就是真子串。
通过观察串的模式匹配的算法，大致了解他的一般步骤，令s为目标串，t为模式串，设i指针和j指针，若s的i指针和t的j指针指向的字符相同，则指针加1，接着比较后面的字符是否相同，若不相同，则保持i不变，将j指针右移，比较是否相同，知道比较完整个字符串为止。
而且知道KMP算法的时间复杂度为O（n+m），所以这种算法不仅时间复杂度低，而且便于理解。
另外，我们在掌握串的匹配模式时，还应该关注串的一些基本运算，理解串的基本概念和特征的基础，了解串的内部表示和处理方法。
字符串时一种特殊的线性表。
特殊之处在于表中的每一个元素都是，在串的基本操作中，有联接，求串长、求子串、比较串的大小、串的插入、删除、子串的定位和置换。
给定一个计算机网络以及机器间的双向连线列表，每一条连线允许两端的计算机进行直接的文件传输，其他计算机间若存在一条连通路径，也可以进行间接的文件传输。
请写出程序判断：
任意指定两台计算机，它们之间是否可以进行文件传输？
输入要求：
输入若干测试数据组成。
对于每一组测试，第1行包含一个整数N（≤10000），即网络中计算机的总台数，因而每台计算机可用1到N之间的一个正整数表示。
接下来的几行输入格式为IC1C2或者C或者C
C1C2或者S，其中C1和C2是两台计算机的序号，I表示在C1和C2间输入一条连线，C表示检查C1和C2间是否可以传输文件，S表示该组测试结束。
当N为0时，表示全部测试结束，不要对该数据做任何处理。
输出要求：
对每一组C开头的测试，检查C1和C2间是否可以传输文件，若可以，则在一行中输出“yes”，否则输出“no”。
当读到S时，检查整个网络。
若网络中任意两机器间都可以传输文件，则在一行中输出“Thenetworkisconnected.”，否则输出“Therearek
components.”,其中k是网络中连通集的个数。
两组测试数据之间请输出一空行分隔。
设计框架
main
Init
find
hebin
（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（）主函数
原理：
在查找祖先时，找到后对路径上的所有节点，修改其父亲，使它直接连接根结点。
正确性证明：
设x所在集合的根结点为p，在Father（x）的路径上的某节点为y，当找到p=Father（x）后，因为途经y节点并且y¹
p，所以必调用了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;
//秩初始化为0t[i].parent=i;
//双亲初始化指向自己
结构体定义
typedefstructnode
intdata;
//节点对应人的编号
intrank;
//节点对应秩intparent;
//定义双亲节点
}UFStree;
（2）find（inte）
对于Find操作，
实际上沿着父指针向上找到根即可。
if（e==parent[e]）returne;
parent[e]=find（parent[e]）;
returnparent[e];
}//这里用递归实现，每次查询的时间复杂度是树的深度，约为O
（1）。
intFIND_SET（UFStreet[],intx） //在x所在的子树中查找集合编
号
if（x!
=t[x].parent） //双亲不是自己return（FIND_SET（t,t[x].parent））;
//递归在双亲中找x
else //双亲是自己，即为只有本身一个元素returnx;
//返回x
（3）hebin（intA,intB）
否则令parent[B]=A，或parent[A]=B，即可把两棵树合并。
if（size[A]>
=size[B]）
size[A]+=size[B];
parent[B]=A;
size[B]+=size[A];
parent[A]=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;
//定义字符型变量
请输入网络中计算机的总台数：
while（scanf（"
%d"
&
n）!
=EOF） //当输入的n不为-1，执行循
环
if（n==0）break;
//当n为0时，全部测试结束
if（n<
1||n>
MAX） //网络中计算机的总台数N（≤10000），不在范围内即为越界
数据越界，请重新输入!
continue;
//结束本次循环，重新输入
init（n）;
//初始化并查集
请输入C（检查是否可以传输文件）、I（输入一条连线）、
S（该组测试结束）字符：
\n"
%s"
oper）!
=EOF） //从键盘上输入字符，当不为-1时，执行循环
if（oper!
='
S'
oper!
C'
I'
）//如果不为S,C,I中的一
个，则命令错误
命令错误，请重新输入!
if（oper=='
） //输入为I，表示在两台计算
机之间输入一条连线
请输入两台计算机的序号：
scanf（"
%d%d"
u,&
v）;
//从键盘上输入两个计算机的编
hebin（u,v）;
//合并包含A，B元素的集合
请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：
elseif（oper=='
） //当输入为C时，判断两个计算机之间能否传输文件，即是否连通
能传输文件
printf（"
//从键盘上输入两个计算机的编号r1=find（u）;
//在u所在的子树中查找集合编号r2=find（v）;
//在v所在的子树中查找集合编号if（r1!
=r2） //如果集合编号不相同
no\n"
//则表示两个计算机之间不
请输入C（检查是否可以传输文件）、I（输入
一条连线）、S（该组测试结束）字符：
能够传输文件
else //如果集合编号相同
yes\n"
//则表示两个计算机之间
） //当输入为S时，表示本组测试结
束
count=0;
//初始化count为0for（inti=1;
if（i==parent[i]） //如果在e的值等于双亲
数组中e位置的值，表示集合中只有e一个元素
count++;
//则统计计算机数的
count自增
if（count==1） //如果count为1，则表
示所有计算机在同一个集合，计算机之间连通
Thenetworkisconnected\n\n"
//表示
网络的计算机之间可以互相传输文件
\n请输入网络中计算机的总台数：
else //如果count的值不为1，则输出网络中有几个分离集合树
Thereare%dcomponents\n\n"
count）;
//输出并查集中的分离集合树的数目
break;
voidmain（）
//定义整型变量n，count
//定义字符型变量
UFStreet[MAX+1];
//定义树类型的并查集
=EOF） //当输入的n不为-1，执行循环
MAX） //网络中计算机的总台数N（≤10000），不在范围内即为越界
MAKE_SET（t,n）;
请输入C（检查是否可以传输文件）、I（输入一条连线）、S（该组测试结束）字符：
=EOF）//从键盘上输入字符，当不为
-1时，执行循环
一条连线
） //输入为I，表示在两台计算机之间输入
请输入两台计算机C1,C2的序号：
//从键盘上输入两个计算机的编号UNION（t,u,v）;
//合并两个计算机集合
请输入C（检查是否可以传输文件）、I（输入一条连
线）、S（该组测试结束）字符：
r1=FIND_SET（t,u）;
//在x所在的子树中查找集合编号r2=FIND_SET（t,v）;
//在y所在的子树中查找集合编号if（r1!
//则表示两个计算机之间不能传输文件
—条连线）、S（该组测试结束）字符：
else //如果集合编号相同
//则表示两个计算机之间能够传输文
件
） //当输入为S时，表示本组测试结束
//初始化count为0
则表示根节点
if（i==t[i].parent） //如果双亲节点指向自己，
//则统计计算机数的count自增
示所有计算机拥有同一个根，计算机之间连通
\n\n请输入网络中计算机的总台数：
else //如果count的值不为
1，则输出网络中有几个分离集合树
//
输出并查集中的分离集合树的数目
（1）数组
#include<
stdio.h>
#defineMAX10001 //定义MAX常量intparent[MAX];
//定义双亲数组
intsize[MAX];
//定义树的高度数组
//初始化
v
升级会员 