数据结构实验报告2

数据结构实验报告

实验1.汉诺塔的实现

一．需求分析

题目：假设有三个命名为X，Y，Z的塔座，在塔座X上插有n个直径大小各不相同、依小到大编号为1,2,……，n的圆盘。现按照要求将X轴上的n个圆盘移至塔座Z上，并仍按同样顺序叠排，圆盘移动时必须遵守以下规则：1，每次只能移动一个；2，圆盘

0

可以插在XYZ中的任一塔座上；3，任何时刻都不能将一个较大的圆盘压在较小的圆盘上。

需要输入的值：圆盘的个数。

输出：从X塔座上移至Z塔座上的顺序。

测试数据：3，输出结果预测：x?y,x?z,y?z,x?y,z?y,z?x,y?x,y?z,x?y,x?z,y?z（箭头符号表示圆盘移动的次序）移动结束。 二．概要设计：

本实验主要运用递归的思想，先把上面的n-1个拿到Y盘，把最下面的一个Z盘，然后剩下的n-1个也用这样的思路，用递归调用的算法实现圆盘的移动。 三．详细设计：

四．调试分析：

遇到的问题：移动时，步骤编号不变。解决方法：用static使其成为静态变量。 时间复杂度：o(n);

经验体会：递归可以把问题简单化，是个很好的方法。 五．使用说明：

输入盘子的数目即可。 六．测试结果：

1

七．源代码：

#include #include

void move(char a,int i,char b){ static int c=0; printf(\}//移动

void hanoi(int n,char x,char y,char z){ if(n==1) move(x,1,z); else{ hanoi(n-1,x,z,y); move(x,n,z); hanoi(n-1,y,x,z); } }//递归

int main(){ char x,y,z; int n; scanf(\ x='x'; y='y'; z='z'; hanoi(n,x,y,z);//调用 return 0; }

实验2.字符串匹配。

2

一．需求分析：

输入一母串，另输入一字符串，判断该字符串是不是母串的字串，若是字串，则返回母串中字串的起始位置，否则输出不是字串。 输入：两串字符； 输出：返回值或0。

测试数据：abcdefgijk efg 预测结果：4 二．概要设计：

用查找的方法，如果遇到第一个相同的字母，则字串母串同时往后移一个。 三．详细设计：

int substring(string s1,string s2)//s1是字串 { int a=0,b,j=1,i; for(b=0;b

四．调试分析：

遇到的问题：跳出循环时没有考虑到如果字串与母串相匹配则字串的字母也要向后移动一个。解决方法：字串同时后移一个如果前一个相匹配。 时间复杂度：o(n^2);

经验体会：设计算法时，即使是很简单的算法，也不能掉以轻心。 五．用户使用说明：

输入一字符串，换行，再输入一字符串，再换行，在换行，即可。 六．运算结果：

七．源代码：

#include #include using namespace std;

3

int substring(string s1,string s2)//s1是字串 { int a=0,b,j=1,i; for(b=0;b

int main(){ string s1,s2; getline(cin,s1);//输入母串 getline(cin,s2);//输入字串 cout<

实验3.停车场管理。

4

本文来源：https://www.bwwdw.com/article/x57d.html