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

《程序设计艺术与方法》课程实验报告一实验名称STL的熟悉与使用姓名系院专业计算机与信息学院班级计算机科学与技术12—2班学号2012211643实验日期指导教师徐本柱成绩一、实验目的和要求1．（1）掌握C++中STL的容器类使用。（2）掌握C++中STL的算法类的使用。二、实验预习内容Vector,list可当作列表使用的数据结构，它们都是动态增长的。1.vector表示一段连续的内存区域每个元素被顺序储存在这段内存中。对vector的随即访问效率很高。但是在任意位置而不是在vector末尾插入元素则效率很低，因为它需要把待插入元素的右边的每个元素都拷贝一遍。类似的删除任一个而不是vector的最后一个元素效率低。2list表示非连续的内存区域并通过一对指向首尾元素的指针双向进行遍历在list的任意位置插入和删除元素的效率都很高，指针必须被赋值但不需要用拷贝元素来实现移动，另一方面它对随机访问的支持并不好访问一个元素需要遍历中间的元素，另外每个元素还有俩不能给个指针的额外空间开销。3泛型算法让编写一般化并可重复使用的算法，其效率与指针对某特定数据类型而设计的算法相同。泛型即是指具有在多种数据类型上皆可操作的含义，与模板有些相似。STL巨大而且可以扩充，它包含很多计算机基本算法和数据结构，而且将算法与数据结构完全分离，其中算法是泛型的，不与任何特定数据结构或对象类型系在一起。三、实验项目摘要1.练习vector和list的使用。定义一个空的vector，元素类型为int，生成10个随机数插入到vector中，用迭代器遍历vector并输出其中的元素值。在vector头部插入一个随机数，用迭代器遍历vector并输出其中的元素值。用泛型算法find查找某个随机数，如果找到便输出，否则将此数插入vector尾部。用泛型算法sort将vector排序，用迭代器遍历vector并输出其中的元素值。删除vector尾部的元素，用迭代器遍历vector并输出其中的元素值。将vector清空。定义一个list，并重复上述实验，并注意观察结果2练习泛型算法的使用。定义一个vector，元素类型为int，插入10个随机数，使用sort按升序排序，输出每个元素的值，再按降叙排序，输出每个元素的值。练习用find查找元素。用min和max找出容器中的最小元素个最大元素，并输出。四、实验结果与分析（源程序及相关说明）1.练习vector和list的使用：#includeiostream#includevector#includeiomanip#includectime#includealgorithmusingnamespacestd;vectorintmyV;boolsortup(intv1,intv2){returnv1v2;}intmain(intargc,char*argv[]){srand(time(NULL));//随机产生十个数for(inti=0;i10;i++)myV.push_back(rand());sort(myV.begin(),myV.end(),sortup);//用sort排序升序vectorint::iteratorit1;for(it1=myV.begin();it1!=myV.end();it1++){cout(*it1)setw(6);//打印数组}coutendl;intmin=myV[0];for(it1=myV.begin()+1;it1!=myV.end();it1++)if((*it1)min)min=(*it1);cout最小元素为minendl;intmax=myV[0];for(it1=myV.begin();it1!=myV.end();it1++)if((*it1)max)max=(*it1);cout最大元素为maxendl;coutendl;intvalue=rand();it1=find(myV.begin(),myV.end(),value);if((*it1)==value)cout找到了这个随机数endl;elsecout没有找到这个随机数endl;myV.insert(myV.end(),value);//数组中没有随机数,插入尾部cout插入尾部的随机数为valueendl;for(it1=myV.begin();it1!=myV.end();it1++){cout(*it1)setw(6);}cout\nendl;//随机在vector头部插入一个随机数intt=rand();//定义t;将一个随机数赋给t，插入到数组·头部myV.insert(myV.begin(),t);cout插入头部的随机数为tendl;for(it1=myV.begin();it1!=myV.end();it1++){cout(*it1)setw(6);}coutendl;//删除尾部元素myV.pop_back();for(it1=myV.begin();it1!=myV.end();it1++){cout(*it1)setw(6);}coutendl;myV.clear();//清空数组if(myV.empty()){coutIt'sempty!endl;}system(PAUSE);//pressanykeytocontinue...return0;}运行截图：2练习泛型算法的使用：#includelist#includeiostream//#incluedalgorithmusingnamespacestd;typedeflistintlin;intvalue[]={1,6,7,8,9};//定义一个数组value并赋值voidprint(lin&l){inti;lin::iteratorlit;//定义一个迭代器for(lit=l.begin();lit!=l.end();lit++)cout(*lit);//依次打印list中的元素coutendl;}boolsortsp(intv1,intv2)//定义一个升序排序算法{returnv1v2;}intmain(){linlin2;lin2.push_front(3);//单独逐个插入几个数lin2.push_front(4);lin2.insert(lin2.begin(),value,value+5);coutlin2内的元素为：;print(lin2);lin2.sort();//对链表l1进行从小到大排序cout排序后的lin2:;print(lin2);lin2.push_front(10);//在list头部插入10cout在list头部插入10之后的结果：;print(lin2);lin2.remove(6);cout删除一个数后的lin1:;print(lin2);system(PAUSE);//pressanykeytocontineu...return0;}//List不允许对随机数进行操作运行截图：二实验名称搜索算法的实验姓名黄星辰系院专业计算机与信息学院班级计算机科学与技术12—2班学号2012211643实验日期指导教师徐本柱成绩一、实验目的和要求1．掌握宽度优先搜索算法。2．掌握深度优先搜索算法。二、实验预习内容1宽度优先搜索算法：又称广度优搜索。是最简单的图的算法的原形。其属于一种盲搜寻法，目的是系统地展开并检查图中的所有节点，以寻找结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。2深度优先搜索算法：它的目的是要达到被搜索结构的叶结点。在一个HTML文件中，当一个超链被选择后，被连接的HTML文件将执行深度优先搜索，即在搜索其余的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。三、实验项目摘要1.将书上的走迷宫代码上机运行并检验结果，并注意体会搜索的思想。2.八皇后问题：在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋方法。上机运行并检验结果。思考：将此题推广到N皇后的情况，检验在N比较大的情况下，比方说N=16的时候，你的程序能否快速的求出结果，如果不能，思考有什么方法能够优化算法。3骑士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，输出一条符合上述要求的路径。4倒水问题：给定2个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出L升的水，如果可以，输出步骤，如果不可以，请输出NoSolution。四、实验结果与分析（源程序及相关说明）2，八皇后问题：#includestdio.h/*声明常量N存储行和列*/#defineN8#defineNUM8/*声明全局变量，h[N][N]控制盘格，H[N][N]控制输出，n[N]存储每一步的*纵坐标，count用于计数。*/inth[N][N],n[N],H[N][N];intcount=0;/*声明函数voidtryit(int,int)尝试符合条件的方法*/voidtryit(int,int);/*声明函数voidoutputArray(int[][N])输出数组*/voidoutputArray(int[][N]);main(){intx=0,y=0,i,j;/*初始化为零*/for(i=0;i=N-1;i++){for(j=0;j=N-1;j++)h[i][j]=0;}tryit(x,y);printf(//其他的布局略\n);printf(共有%d种布局.\n,92);return(0);}/*定义函数voidtryit(int,int)尝试符合条件的方法*/voidtryit(intx,inty){inti,j;if(count=NUM){/*重复时跳出递归*/if((H[0][0]==1&&H[1][4]==1&&H[2][7]==1&&H[3][5]==1&&H[4][2]==1&&H[5][6]==1&&H[6][1]==1&&H[7][3]==1)&&count!=1){}else{if(x=0&&x=N-1&&y=0&&y=N-1&&h[x][y]==0){/*对与皇后在同一行、列、斜线上的点作出处理*/for(j=0;j=7;j++){if(h[x][j]==0)h[x][j]=x+1;if(h[j][y]==0)h[j][y]=x+1;if(x+j=0&&x+j=N-1&&y+j=0&&y+j=N-1&&h[x+j][y+j]==0)h[x+j][y+j]=x+1;if(x+j=0&&x+j=N-1&&y-j=0&&y-j=N-1&&h[x+j][y-j]==0)h[x+j][y-j]=x+1;if(x-j=0&&x-j=N-1&&y+j=0&&y+j=N-1&&h[x-j][y+j]==0)h[x-j][y+j]=x+1;if(x-j=0&&x-j=N-1&&y-j=0&&y-j=N-1&&h[x-j][y-j]==0)h[x-j][y-j]=x+1;}/*对皇后处的点作出标志*/h[x][y]=-x-1;/*完成一种走法作出处理*/if(x==7){/*转换成输出的格式*/for(i=0;i=N-1;i++){for(j=0;j=N-1;j++){if(h[i][j]0)H[i][j]=1;elseH[i][j]=0;}}count=count+1;/*输出前几种情况*/if(count=NUM){printf(------布局%d------\n,count);outputArray(H);}/*对下一种走法，清楚前一次的影响*/for(i=0;i=N-1;i++)