算法实验报告

华北电力大学实验报告||实验名称算法设计与分析综合实验课程名称算法设计与分析||专业班级软件12学生姓名：学号：成绩：指导教师：胡朝举实验日期：2014.12实验一分治策略—归并排序一、实验要求（1）编写一个模板函数：templatetypenameT，MergeSort(T*a,intn);以及相应的一系列函数，采用分治策略，对任意具有:booloperator(constT&x,constT&y);比较运算符的类型进行排序。（2）与STL库中的函数std::sort(..)进行运行时间上的比较，给出比较结果,如：动态生成100万个随机生成的附点数序列的排序列问题,给出所用的时间比较。二、实验代码#includestdio.h#includestdlib.h#includestring.h#includelimits.h#defineMAX50typedefstruct{intarr[MAX+1];intlength;}SortArr;SortArr*CreateSortArr(){inti=0;charbuf[4*MAX]=;char*ptr=NULL;SortArr*sortArr=(SortArr*)malloc(sizeof(SortArr));memset(sortArr,0,sizeof(SortArr));printf(请输入待排序数据，以逗号分隔，以分号结束\ninput:);scanf(%s,buf);ptr=buf;sortArr-arr[i]=0;i=1;while(*ptr!=';'){sortArr-arr[i]=atoi(ptr);i++;ptr=strstr(ptr,,);if(!ptr){break;}ptr++;}sortArr-length=(i-1);returnsortArr;}intmerge(intarr[],intp,intq,intr){inti=0;intj=0;intk=0;intn1=0;intn2=0;int*leftArr=NULL;int*rightArr=NULL;n1=q-p+1;n2=r-q;leftArr=(int*)malloc((n1+2)*sizeof(int));rightArr=(int*)malloc((n2+2)*sizeof(int));for(i=1;i=n1;i++){leftArr[i]=arr[p+i-1];}for(j=0;j=n2;j++){rightArr[j]=arr[q+j];}i=1;j=1;leftArr[n1+1]=INT_MAX;rightArr[n2+1]=INT_MAX;for(k=p;k=r;k++){if(leftArr[i]=rightArr[j]){arr[k]=leftArr[i];i++;}else{arr[k]=rightArr[j];j++;}}free(leftArr);free(rightArr);return0;}intmergeSort(intarr[],intp,intr){intq=0;if(pr){q=(p+r)/2;mergeSort(arr,p,q);mergeSort(arr,(q+1),r);merge(arr,p,q,r);}return0;}intMergingSortRecursion(SortArr*sortArr){mergeSort(sortArr,1,sortArr-length);return0;}intPrintArray(SortArrsortArr){inti=0;for(i=1;i=sortArr.length;i++){printf(%d,,sortArr.arr[i]);}printf(\b;\n);return0;}intmain(){SortArr*sortArr=NULL;sortArr=CreateSortArr();printf(\nBeforeSort：\t);PrintArray(*sortArr);MergingSortRecursion(sortArr);printf(SortedArray：\t);PrintArray(*sortArr);free(sortArr);return0;}实验二贪心算法—Huffman树及Huffman编码一、实验要求一个记录字符及出现频率的文件如下所示：Huffman.haf，7，a,45，b,13，c,12，d,16，e,89，f,34，g,20试编写一个读取此种格式文件类CHuffman,内部机制采用优先队列，用于建立Huffman树及进行Huffman编码输出，其用法可以如下所示：CHuffmanhm(huffman.dat);hm.CreateTree();hm.OutputTree();hm.OutputCode();//二进制形式的字符串对于输出树的形式可自行决定(如图形界面或字符界面)。二、实验代码#includeiostream#includestdlib.husingnamespacestd;constintMaxValue=10000;//初始设定的权值最大值constintMaxBit=4;//初始设定的最大编码位数constintMaxN=10;//初始设定的最大结点个数structHaffNode//哈夫曼树的结点结构{intweight;//权值intflag;//标记intparent;//双亲结点下标intleftChild;//左孩子下标intrightChild;//右孩子下标};structCode//存放哈夫曼编码的数据元素结构{intbit[MaxBit];//数组intstart;//编码的起始下标intweight;//字符的权值};//weight[]:由小到大排序voidHaffman(intweight[],intn,HaffNodehaffTree[])//建立叶结点个数为n权值为weight的哈夫曼树haffTree{intj,m1,m2,x1,x2;//哈夫曼树haffTree初始化。n个叶结点的哈夫曼树共有2n-1个结点for(inti=0;i2*n-1;i++){if(in)haffTree[i].weight=weight[i];elsehaffTree[i].weight=0;//注意这里没打else那{}，故无论是n个叶子节点还是n-1个非叶子节点都会进行下面4步的初始化haffTree[i].parent=0;haffTree[i].flag=0;haffTree[i].leftChild=-1;haffTree[i].rightChild=-1;}//构造哈夫曼树haffTree的n-1个非叶结点for(inti=0;in-1;i++){m1=m2=MaxValue;//Maxvalue=10000;(就是一个相当大的数)x1=x2=0;//x1、x2是用来保存最小的两个值在数组对应的下标for(j=i;jn+i;j++)//循环找出所有权重中，最小的二个值--morgan{if(haffTree[j].weightm1&&haffTree[j].flag==0){m2=m1;x2=x1;m1=haffTree[j].weight;x1=j;}elseif(haffTree[j].weightm2&&haffTree[j].flag==0){m2=haffTree[j].weight;x2=j;}}couti=im1m2endl;//将找出的两棵权值最小的子树合并为一棵子树haffTree[x1].parent=n+i;haffTree[x2].parent=n+i;haffTree[x1].flag=1;haffTree[x2].flag=1;haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;haffTree[n+i].leftChild=x1;haffTree[n+i].rightChild=x2;}}voidHaffmanCode(HaffNodehaffTree[],intn,CodehaffCode[])//由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode{Code*cd=newCode;intchild,parent;//求n个叶结点的哈夫曼编码for(inti=0;in;i++){//cd-start=n-1;//不等长编码的最后一位为n-1,cd-start=0;//,----修改从0开始计数--morgancd-weight=haffTree[i].weight;//取得编码对应权值的字符child=i;parent=haffTree[child].parent;//由叶结点向上直到根结点while(parent!=0){if(haffTree[parent].leftChild==child)cd-bit[cd-start]=0;//左孩子结点编码0elsecd-bit[cd-start]=1;//右孩子结点编码1//cd-start--;cd-start++;//改成编码自增--morganchild=parent;parent=haffTree[child].parent;}//保存叶结点的编码和不等长编码的起始位//for(intj=cd-start+1;jn;j++)for(intj=cd-start-1;j=0;j--)//重新修改编码，从根节点开始计数--morganhaffCode[i].bit[cd-start-j-1]=cd-bit[j];haffCode[i].start=cd-start;haffCode[i].weight=cd-weight;//保存编码对应的权值}}intmain(){inti,j,n=4,m=0;intweight[]={2,4,5,7};//intweight[]={7,5,4,2};HaffNode*myHaffTree=newHaffNode[2*n-1];Code*myHaffCode=newCode[n];if(nMaxN){cout定义的n越界，修改MaxN!endl;exit(0);}Haffman(weight,n,myHaffTree);HaffmanCode(myHaffTree,n,myHaffCode);//输出每个叶结点的哈夫曼编码for(i=0;in;i++){coutWeight=myHaffCode[i].weightCode=;//for(j=myHaffCode[i].start+1;jn;j++)for(j=0;jmyHaffCode[i].start;j++)coutmyHaffCode[i].bit[j];m=m+myHaffCode[i].weight*myHaffCode[i].start;cout长度：myHaffCode[i].startendl;}couthuffman'sWPLis:;coutm;coutendl;return0;}实验三用回溯方法求解n后问题一、实验要求问题：对任意给定的n求解n后问题。具体要求：1．封装n后问题为类，编写以下两种算法进行求解：（1）递归回溯方法；（2）迭代回溯方法。(选)2．对任意给定的n，要求输出其解向量（所有解），并输出其解数；3．构造n后问题的解数表格（由程序自动生成）:n后数解数第一个解42(2,4,1,3)5……6……………参考类的封装如下：classCQueen{public:CQueen();//缺省构造函数CQueen(intn);~CQueen();voidIniQueen(intn);voidToPrintAll();//求出所有的解并输出voidToPrint(int