数据结构课程设计.docx
《数据结构课程设计.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计.docx（11页珍藏版）》请在冰点文库上搜索。
数据结构课程设计
实验报告
课程名称数据结构课程设计
实验项目名称数据结构课程设计报告
班级与班级代码
实验室名称（或课室）实验楼803
专业计算机科学与技术
任课教师
学号：
姓名：
实验日期：
2015年12月28日
广东财经大学教务处制
姓名实验报告成绩
评语：
指导教师（签名）
年月日
说明：
指导教师评分后，实验报告交院（系）办公室保存。
一．实验目的和要求
通过对于数据结构课程设计相关实验的操作进行总结，从中得到的收获，对于相关实验的看法或者深入的研究，加深对于相关算法的理解，提高个人的算法设计分析能力。
课程设计1-Josephus问题
课程设计2-八皇后问题
课程设计3-二叉树树中的最小公共最先
课程设计4-动态规划入门
课程设计5-有向图的强连通分量
课程设计6-串的模式匹配
课程设计7-动态规划Floyd最短路径算法
二．Josephus问题
解决这一问题，可以采用数学方法和采用循环链表的方法。
数学方法：
1）当有人出局之后，可以用给原来的编号赋新值。
因此，当到第二轮时，1和2分别变成n+1和n+2，3已经出局，4和5分别变为n+3和n+4，6已经出局，以此类推；3k+1和3k+2分别变成n+2k+1和n+2k+2。
2）在上述编号方式下，第k个出局的人的号码一定是3k，所以最后一个出局的人的最终号码为3n。
3）如果编号N>;n，则编号为N的人此前一定有另一个编号。
我们如何求编号N对应的前一个编号呢？
因为N=n+2k+1或N=n+2k+2，因此k=（N-n-1）/2。
前面的编号分别为3k+1和3k+2，即有3k+（N-n-2k）=k+N-n,这就求得了编号N对应的前一个编号。
N=3*n;
whileN>;ndoN=（N-n-1）/2+N-n;
returnN;
循环链表：
由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表；由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，应该选用效率较高的链表结构；为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。
所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头节点的循环链表来描述。
for（i=2;i<=n;++i）
{
p=（node*）malloc（sizeof（node））;
p->id=i;
q->next=p;
q=p;
}
q->next=head;
三．八皇后问题
解决这一问题可以使用回溯法和递归法。
每一行可以而且必须放一个皇后，所以n皇后问题的解可以用一个n元向量X=（x1,x2,.....xn）表示，其中，1≤ i≤ n且1≤ xi≤ n，即第n个皇后放在第i行第xi列上。
由于两个皇后不能放在同一列上，所以，解向量X必须满足的约束条件为:
xi≠ xj;若两个皇后的摆放位置分别是（i,xi）和（j,xj），在棋盘上斜率为-1的斜线上，满足条件i-j=xi-xj;在棋盘上斜率为1的斜线上，满足条件i+j=xi+xj;
综合两种情况，由于两个皇后不能位于同一斜线上，所以，
解向量X必须满足的约束条件为:
|i-xi|≠ |j-xj|
i=0;
while（i<=7&&i>=0）{
for（j=position[i]+1;j<=7;j++）{
//测试位置（i,j）是否合适
if（positionIJOk（queens,i,j））{
queens[i][j]=1;//放置皇后
position[i]=j;//记下皇后在当前行的位置
i=i+1;
j=20;//强制跳出循环
}
}
if（j==8）{//在本行没找到合适位置
position[i]=-1;//回溯前将position[i]复原
i=i-1;//退回上一行,回溯
if（i>=0）queens[i][position[i]]=0;//i<0为结束条件
利用递归方法很容易解决。
没放置一个皇后，就将其能够攻击的区域进行标记，然后放置下一个皇后，一次类推……；此外，如果有解最终肯定是每一行有且只有一位皇后，所以放置的时候按照逐行放置的顺序进行。
（1）运行时有些函数的头文件未定义，导致无法进行编译。
（2）在统计方法的个数时，未将累加的那个整型变量进行初始化，导致无法显示。
（3）如果将92种情形全部打印，则前面的几十种情况将无法显示出，要想看到前面的状态，必须添加一个控制语句，使其能一个一个的输出。
四．二叉树树中的最小公共最先
如果给定pRoot是NULL，即空树，则返回的公共节点自然就是NULL；
如果给定pRoot与两个节点中任何一个相同，说明，pRoot在就是所要找的两个节点之一，则直接返回pRoot，表明在当前链路中找到至少一个节点；
如果给定pRoot不是两个节点中任何一个，则说明，需要在pRoot的左右子树中重新查找，此时有三种情况：
两个节点都在左子树上；两个节点都在右子树上；一个在左子树，一个在右子树上；具体来说，就是：
1）如果左子树查找出的公共节点是NULL，则表明从左子树根节点开始到左子树的所有叶子节点等所有节点中，没有找到两个节点中的任何一个，这就说明，这两个节点不在左子树上，不在左子树，则必定在右子树上；
2）如果右子树查找的公共节点是NULL，说明在右子树中无法找到任何一个节点，则两个节点必定在左子树上；
3）如果左右子树查找的公共节点都不是NULL，说明左右子树中各包含一个节点，则当前节点pRoot就是最低公共节点，返回就可以
StackS;
voidPreOrder（BTNode*b,BTNode*p）
{
if（b!
=NULL）{
Push（S,b）;//或Push（b->Element）
if（b==p）复制栈S中的内容，结束程序
PreOrder（b->Left）;
PreOrder（b->Right）;
Pop（S,b）;//或Pop（b->Element）
}
}
有时输入两个节点程序无法运行
解决方法：
注意两个节点一个和另一个不能是父子关系。
五．动态规划入门
可以将背包问题的求解过程看作是进行一系列的决策过程，即决定哪些物品应该放入背包，哪些物品不放入背包。
如果一个问题的最优解包含了物品n，即xn=1，那么其余x1，x2，...，x（n-1）一定构成子问题1，2，...，n-1在容量W-wn时的最优解。
如果这个最优解不包含物品n，即xn=0，那么其余x1，x2，...，x（n-1）一定构成子问题1，2，...，n-1在容量W时的最优解。
（2）递归定义最优解的值
根据上述分析的最优解的结构递归地定义问题最优解。
设c[i,w]表示背包容量为w时，i个物品导致的最优解的总价值，得到下式。
显然要求c[n,w]。
六．有向图的强连通分量
深度优先遍历是求有向图的强连通分量的一个有效方法，具体求解步骤如下：
⑴在有向图中，从某个顶点出发进行深度优先遍历，并按其所有邻接点的访问都完成（即出栈）的顺序将顶点排列起来。
⑵在该有向图中，从最后完成访问的顶点出发，沿着以该顶点为头的弧作逆向的深度优先遍历，若此次遍历不能访问到有向图中所有顶点，则从余下的顶点中最后完成访问的那个顶点出发，继续作逆向的深度优先遍历，依次类推，直至有向图中所有顶点都被访问到为止。
⑶每一次逆向深度优先遍历所访问到的顶点集便是该有向图的一个强连通分量的顶点集，若仅作一次逆向深度优先遍历就能访问到图的所有顶点，则该有向图是强连通图。
aslongasadjacencylistsareused*/
voidDFS（VertexV）/*thisisonlyatemplate*/
{visited[V]=true;/*markthisvertextoavoidcycles*/
for（eachWadjacenttoV）
if（!
visited[W]）
DFS（W）;
}/*T=O（|E|+|V|
voidDFS（VertexV）/*thisisonlyatemplate*/
{
visited[V]=true;/*markthisvertextoavoidcycles*/
for（eachWadjacenttoV）
if（!
visited[W]）
DFS（W）;
post[V]=postCounter;//递归返回时对节点V进行编号
postCounter++;
}/*T=O（|E|+|V|）aslongasadjacencylistsareused*/
七．串的模式匹配
解法一：
暴力法模式匹配算法
暴力算法就是文本串每次移动向右移动一个字符，与模式串比较，如果每个字符都相等，则表示在文本串中找到与模式串匹配的子集。
intIndex（StringS,StringP,intpos）{
inti=pos;
intj=1;
while（i<=S[0]&&j<=P[0]）{
if（S[i]==P[j]）{i++;j++;}
else{
i=i-j+2;
j=1;
}
}
if（j>P[0]）
returni-P[0];
else
return0;
解法二：
KMP
KMP算法，是在朴素的模式匹配算法的基础上，实现了匹配不成功时，不对主串指针进行回溯，使模式匹配的时间复杂度降低为：
O（n+m）。
将主串S中某个位置i起始的子串和模式串T相比较。
即从 j=0 起比较S[i+j] 与 T[j]，若相等，则在主串 S 中存在以 i 为起始位置匹配成功的可能性，继续往后比较（j逐步增1），直至与T串中最后一个字符相等为止，否则改从S串的下一个字符起重新开始进行下一轮的"匹配"，即将串T向后滑动一位，即 i 增1，而 j 退回至0，重新开始新一轮的匹配。
intIndex_KMP（StringS,StringP,intpos）{
inti=pos;
intj=1;
while（i<=S[0]&&j<=P[0]）{
if（j==0||S[i]==P[j]）{i++;j++;}
else{
j=next[j];
}
}
if（j>P[0]）
returni-P[0];
else
return0;
}
有时输入两个节点程序无法运行
解决方法：
注意两个节点一个和另一个不能是父子关系。
八．动态规划Floyd最短路径算法
求解最短路径有两种方法：
Dijkstra算法和Floyd算法
Dijkstra算法
算法思想：
设G=（V,E）是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径,就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。
在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。
此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
voidDijkstra（intv0）
{
boolS[MAXNUM];//判断是否已存入该点到S集合中
intn=MAXNUM;
for（inti=1;i<=n;++i）
{
dist[i]=A[v0][i];
S[i]=false;//初始都未用过该点
if（dist[i]==MAXINT）
prev[i]=-1;
else
prev[i]=v0;
}
dist[v0]=0;
S[v0]=true;
Floyd算法
算法思想原理：
从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。
所以，我们假设Dis（i,j）为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis（i,k）+Dis（k,j）voidAllPairs（TwoDimArrayA,TwoDimArrayD,intN）
{inti,j,k;
for（i=0;ifor（j=0;jD[i][j]=A[i][j];
for（k=0;kfor（i=0;ifor（j=0;jif（D[i][k]+D[k][j]/*Updateshortestpath*/
D[i][j]=D[i][k]+D[k][j];
}
（1）使用path矩阵构造路径，由修改后的算法可以得出，矩阵的位置坐标是首尾，具体数为中间路径。
（2）Floyd算法对于图中负权边和负权环的反应：
可能陷入死循环。
（3）比较Dijkstra算法和Floyd算法：
Dijkstra一个一个添加，需要不断更新，无法处理负权边和负权环，Floyd算法把已经连接的路径都标出来,再通过不等式比较来更改路径，可以处理负权边和负权环。
九．感想和总结
数据结构课程设计是实践很强的一门课程，对于计算机专业意义重大，光是“听”和“读”是绝对不够的，必须加强实践。
在写算法的过程中，可能会出现很多问题，而不断修改的过程便是学习的过程。
在这个过程中，只要全身心的投入了，便会发现很多乐趣。
在以后的学习中，还要加强对于相关算法的研究和分析，提高自己的编程水平和处理问题的能力，需要贯穿整个学习过程。
升级会员 