程序设计艺术与方法课程实验报告

1、程序设计艺术与方法课程实验报告实验名称STL的熟悉与使用姓名系院专业信息工程系班级物联网一班学号实验日期指导教师成绩一、实验目的和要求1.(1)掌握C+中STL的容器类使用。(2)掌握C+中STL的算法类的使用。二、实验预习内容Vector,list可当作列表使用的数据结构，它们都是动态增长的。表示一段连续的内存区域每个元素被顺序储存在这段内存中。对vector的随即访问效率很高。但是在任意位置而不是在vector末尾插入元素则效率很低，因为它需要把待插入元素的右边的每个元素都拷贝一遍。类似的删除任一个而不是vector的最后-个元素效率低。2list表示非连续的内存区域并通过一对指向首尾元素

2、的指针双向进行遍历在list的任意位置插入和删除元素的效率都很高，指针必须被赋值但不需要用拷贝元素来实现移动，另一方面它对随机访问的支持并不好访问一个元素需要遍历中间的元素，另外每个元素还有俩不能给个指针的额外空间开销。3泛型算法让编写一般化并可重复使用的算法，其效率与指针对某特定数据类型而设计的算法相同。泛型即是指具有在多种数据类型上皆可操作的含义，与模板有些相似。STL巨大而且可以扩充，它包含很多计算机基本算法和数据结构，而且将算法与数据结构完全分离，其中算法是泛型的，不与任何特定数据结构或对象类型系在一起。三、实验项目摘要1.练习vector和list的使用。定义一个空的vector,元

3、素类型为int,生成10个随机数插入到vector中，用迭代器遍历vector并输出其中的元素值。在vector头部插入一个随机数，用迭代器遍历vector并输出其中的元素值。用泛型算法find查找某个随机数，如果找到便输出，否则将此数插入vector尾部。用泛型算法sort将vector排序，用迭彳器遍历vector并输出其中的元素值。删除vector尾部的元素，用迭代器遍历vector并输出其中的元素值。将vector清空。定义一个list,并重复上述实验，并注意观察结果2练习泛型算法的使用。te义一个vector,兀素类型为int,插入10个随机数，使用sort按升殍排序，输出每个元素的

4、值，再按降叙排序，输出每个元素的值。练习用find查找元素。用min和max找出容器中的最小元素个最大元素，并输出。四、实验结果与分析（源程序及相关说明）1.练习vector和list的使用：#include#include#include#include#includeusingnamespacestd;vectormyV;boolsortup(intv1,intv2)returnv1v2;intmain(intargc,char*argv口)srand(time(NULL);return0;运行截图：2练习泛型算法的使用：#include#include.return0;运行截图：实验名称

5、搜索算法的实验系院专业信息工程物联网一级班实验日期指导教师一、实验目的和要求1掌握宽度优先搜索算法。2掌握深度优先搜索算法。二、实验预习内容1 宽度优先搜索算法：又称广度优搜索。是最简单的图的算法的原形。其属于一种盲搜寻法，目的是系统地展开并检查图中的所有节点，以寻找结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。2 深度优先搜索算法：它的目的是要达到被搜索结构的叶结点。在一个HTML文件中，当一个超链被选择后，被连接的HTML文件将执行深度优先搜索，即在搜索其余的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有

6、其他超链可选择时，说明搜索已经结束。三、实验项目摘要1 .将书上的走迷宫代码上机运行并检验结果，并注意体会搜索的思想。2 .八皇后问题：在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋方法。上机运行并检验结果。思考：将此题推广到N皇后的情况，检验在N比较大的情况下，比方说N=16的时候，你的程序能否快速的求出结果，如果不能，思考有什么方法能够优化算法。3骑士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，输出一条符合上述要求的路径。4 倒水问题：给定2个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出L升的水，如果可以，输出

7、步骤，如果不可以，请输出NoSolution。四、实验结果与分析(源程序及相关说明)2，八皇后问题：#include/*声明常量N存储行和列*/# defineN8# defineNUM8/*声明全局变量，hNN控制盘格，HNN控制输出，nN存储每一步的# 纵坐标，count用于计数。*/inthNN,nN,HNN;intcount=0;/*声明函数voidtryit(int,int)尝试符合条件的方法*/voidtryit(int,int);/*声明函数voidoutputArray(intN)输出数组*/voidoutputArray(intN);main()intx=0,y=0,i,j;

8、/*初始化为零*/for(i=0;i=N-1;i+)for(j=0;j=N-1;j+)hij=0;tryit(x,y);printf(n,92);return(0);/*定义函数voidtryit(int,int)尝试符合条件的方法*/voidtryit(intx,inty)inti,j;if(count=0&x=0&y=N-1&hxy=0)/*对与皇后在同一行、列、斜线上的点作出处理*/for(j=0;j=0&x+j=0&y+j=0&x+j=0&y-j=0&x-j=0&y+j=0&x-j=0&y-j=N-1&hx-jy-j=0)hx-jy-j=x+1;)/*对皇后处的点作出标志*/hxy=-

9、x-1;/*完成一种走法作出处理*/if(x=7)(/*转换成输出的格式*/for(i=0;i=N-1;i+)(for(j=0;j=N-1;j+)(if(hij0)Hij=1;elseHij=0;)count=count+1;/*输出前几种情况*/if(count=NUM)(printf(布局dn,count);outputArray(H);)/*对下一种走法，清楚前一次的影响*/for(i=0;i=N-1;i+)(for(j=0;j7)(/*清楚前一次影响*/for(i=0;i=N-1;i+)(for(j=0;j=0)tryit(x-1,nx-1+1);elsetryit(0,0);/*尝试

10、下一格*/elsetryit(x,y+1);/*定义函数voidoutputArray(intN)输出数组*/voidoutputArray(inthN)inti,j;for(i=0;i=N-1;i+)for(j=0;j=N-1;j+)printf(%d,hij);printf(n);运行截图：4.倒水问题：#includeintmain()intca,cb,cc,x,y;while(scanf(%d%d%d,&ca,&cb,&cc)!=EOF)if(cb=cc)printf(fillBn);elseif(ca=cc)printf(fillAn);printf(pourABn);elsex=y

11、=0;if(caca-x)考：用跨立方法，跨立的含义是：如果一条线段的一个端点在一条直线的一边，另一个端点在这条直线的另一端，我们就说这条线段跨立在这条直线上。线段相交满足且只需满足如下两个条件就可以了：1两条线段相互跨立；2条线段的一个端点在另一条线段上。如果两线段相交，则两线段必然相互跨立对方。若p1p2跨立p3P4,则矢量(pl-p3)和(p2-pl)位于矢量(p4p3)的两侧，即(pl-p3)X(p4-p3)*(p2-p3)义(p4-p3)0。当(pl-p3)X(p4-p3)=0时，说明(pl-p3)和(p4-p3)共线，但是因为已经通过快速排斥试验，所以pl一定在线段p3P4上；同理

12、，(p4-p3)X(p2-p3)=0说明p2一定在p3P4上。所以判断p1p2跨立Q1Q2的依据是：(pl-p3)X(p4-p3)*(p4-p3)X(p2-p3)=0。同理判断Q1Q2跨立P1P2的依据是：(p3-pl)X(p2-pl)*(p2-pl)X(p4-pl)=0O代码中函数boolsegment_intersect(用于判断pl、p2构成的线段和p3、p4构成的线段是否相交。可以看出共五种情况两经段是相交而，友之就输出“ThetwoareNotintersected!4.房间最短路问题：#include#include#includeinncludeusingnamespacestd;typedefpairPOINT;econd|pointi.second=&pointi.firstp0=pointi;k=i;()+k)；(),P0)；vectorconvex_hull;do(point0);startPoint=point0;()；sort(),(),sortByPolorAngle);if(point0=convex_hull0)break;(convex_hull()-1);while(1);for(intj