算法分析与设计-实验指导

实验一、归并排序及各种排序算法性能一.上机实验的问题和要求二．程序设计的基本思想，原理和算法描述 三、源程序及注选择排voidfun(int*a,intn){inttemp,min;inti,j;for(i=0;i<n-1;{min=for(j=i+1;j<n;{if(a[j]<min //min}temp=a[min];a[min]=a[i];a[i]=temp;}}voidfun(int*a,int{intfor(i=1;i<n;{val=a[i]; //a[i]依次j=i-1;while((val<a[j])&&(j>={a[j+1]=a[j]; }a[j+1]=}}快速排//voidquicksort(int*a,inti,int{if(i<{intp=partion(a,i,j); }} 把a[l]放在正确的位置intpartion(int*a,intl,intr){inti=l;intj=r+1;inttemp;intv=a[l];{ //v //vif(j==if(i>=temp //a[i]=a[j];a[j]=temp;}temp //a[l]a[j]=a[l];a[l]=temp;return //j}堆排序 法的思voidheapfy(int*a,intn){inttemp;inth=n-1;while(h //h0{if(a[ha[(h- {}}}

temp=a[h];a[h]=a[(h-1)/2];a[(h-1)/2]=temp;h=(h-1)/2;//a[0]...a[n-1]为堆voidshiftdown(int*a,intn){inth=0;intwhile(2*h+2<{if((a[h]>a[2*h+1])&&(a[h]>a[2*h+2])) elseif(a[2*h+1 {temp=a[h];a[h]=a[2*h+1];a[2*h+1]=h=} {temp=a[h];a[h]=a[2*h+2];a[2*h+2]=temp;h=2*h+2;}}}//voidheapsort(int*a,int{intintfor(i=1;i<n;i++) for(i=n-1;i>1;i--{temp=a[0]; a[0]=a[i];a[i] }}(4)归并排//输入：a[l]<=...<=a[p](有序) 且a[p+1]<=a[p+2]<=a[r](有序)voidmerge(int*a,intl,intr,intp) //l<=p<=r{intb[N]; inti=l;intj=p+1;intk=i;intt;while((i<=p)&&(j<={if(a[i]<={b[k]=a[i];}{}}

b[k]=a[j];{for(t=i;t<=p;{}}{

b[k]=a[t];for(t=j;t<=r;{b[k]=a[t];}}for(i=l;i<=r;i++)a[i]=b[i];}voidmergesort(int*a,intl,intr){if(l {intp=(l+r)/2; mergesort(a,p+1,r);//排右边部分 }}一 实验内二、算法思想分治算法思想：把规模为n的问题分成k快速排序算法思想：假定把对n个对象的排序看作是对1nn个整数的排序。快速排序算法的基本思想是从中取一适合的关键字k，以k为标准把需要排序的n个对象分成两部分，一部分比k另一部分比k大，即：(小于k部分)k（k）三 实验过intPartition(intL[],intlow,inthigh j=high;L[0]=L[low];while(i<j)while(j>i&&L[j].key>=pivotkey)j //i,j描L[i]=L[j while(i<j&&L[i].key<=pivotkey) //ji描L[j]=L[i }L[i]= } QuickSort(intL[],intlow,inthigh if(low<high){pivotloc=partition(L,low,high}}

QuickSort(L,low,pivotloc-1) QuickSort(L,pivotloc+1,high) intintcout<<"请输入待排序数字的个数：";intdata[20];for(inti=1;i<=n;i++) for(inti=1;i<n;i++)cout<<data[i]<<",";return(0);}四 实验结 n-11O(nn)。实验三：0-1niwipi，M。ixi（1<=i<=n,0<=xi<=1pi*xiproblemw[i]来排序。voidsort(floattempArray[],flaotw[],int{ inti=0,j= intindex=5for(i=0;i<n; floatswapMemory=floattemp=index=i; for(j=i+1;j<n; if(temp<{temp=index=}}swapMemory=w[index]=w[i]= 31p[3]{25,24,15};w[3]{18,15,10}。得到的结果如下：pleaseinputthetotalcountofobject:3Pleaseinputarrayofp2524Nowpleaseinputarrayofw1815sortResult[i]is afterarithmeticdata: x[3]{1.4,1.6,1.5M200，1，0.5。然而事实上是不是就这样呢？当程序进入此函数经过必要的变量初始化后，进入了循环，也就是程序的第7行。第一轮循环中，temp=tempArray[0]=1.4,index=i=015内层循环的主要任务是从第i+1个元后找到一个最大的效益并保存此时的下标。24w[i]进行排序。w[i]{1.6,1.6,1.5}，w[i]排序后就既改变了w[i]w[i]的原来值！ voidsort(floattempArray[],intsortResult[],int inti=0,j= intindex=0,k=5 for(i=0;i<n;i++)//对数组赋初值 sortResult[i]= for(i=0;i<n;{floatswapMemory=floattemp=index=i;for(j=i;j<n;{if((temp<tempArray[j])&&(sortResult[j]== temp= index= if(sortResult[index]== sortResult[index]= for(i=0;i<n; if(sortResult[i]== sortResult[i]= 43修改后最大的一个改变是没有继续沿用直接对w[i]排序，而是用w[i]的一个数组sortResult[i]。sortResult[i]w[i]的大小顺序！这样#include#defineMAXSIZE100//假设物体总数#defineM20 voidGREEDY(floatw[],floatx[],intsortResult[],int{floatcu=M;inti=0;inttemp=0;for(i0;in;i++{x[i]=}for(i=0;i<n;{tempsortResult[i];//得到取物体的顺序if(w[temp]>cu){}x[temp]1;/cuw[temp];}if(in)//{x[temp]=cu/}}voidsort(floattempArray[],intsortResult[],int{inti=0,j=intindex=0,k=for(i=0;i<n;i++)//对数组赋初值{sortResult[i]=}for(i=0;i<n;{floattemp=tempArray[i];index=i;for(j=0;j<n;j++){if((temp<tempArray[j])&&(sortResult[j]=={temp=tempArray[j];index=j;}}if(sortResult[index]=={sortResult[index]=}}sortResult[i]标记for(i=0;i<n;i++){if(sortResult[i]=={sortResult[i]=}}}voidgetData(floatp[],floatw[],int{inti=printf("pleaseinputthetotalcountofobject:");scanf("%d",n);printf("Pleaseinputarrayofp:\n");for(i=0;i<(*n);i++){scanf("%f",}printf("Nowpleaseinputarrayofw:\n");for(i=0;i<(*n);i++){scanf("%f",}}voidoutput(floatx[],int{intprintf("\n\nafterarithmeticdata:advisemethod\n");for(i=0;i<n;i++){printf("x[%d]\t",}for(i=0;i<n;{printf("%2.3f\t",}}void{floatp[MAXSIZE],w[MAXSIZE],inti=0,n=intsortResult[MAXSIZE];getData(p,w,&n);for(i=0;i<n;{x[i]=p[i]/}sort(x,sortResult,n);GREEDY(w,x,sortResult,n);output(x,n);}Dijkstra1掌握最短路径的算法原理掌握最短路径的算法实现3实验要遵守使用规范Dijkstra实验步Dijkstra参考伪//用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]D[v]//若P[v][w]TRUE，则w是从v0到v//final[v]TRUE当且仅当v∈S，即已经求得从v0到vfor(v=0；v<G.vexnum；++v){final[v]=FALSE；D[v]=G.arcs[v0][v]；for(w=0w<G.vexnum++wP[v][wFALSE；//设空路径if(D[v]<INFINITY){P[v][v0]=TRUE；P[v][v]=TRUE；}D[v0]0final[v0TRUE//初始化，v0顶点属于S//开始主循环，每次求得v0到某个v顶点的最短路径，并加v到sfor(i=1i<G.vexnum；++i其余G.vexnum-1个顶点minINFINITY//当前所知离v0顶点的最近距离if(D[w]<min){v=w；min=D[w]；}//w顶点离v0顶点更近final[v]=TRUE；//v0顶点最近的v加入S集for(w=0；w<G.vexnum；++w)//更新当前最短路径及距离if(!final[w]&&(min+G.arcs[v][w]<D[w])){//修改D[w]和P[w]实验六 C语言程序实现。3①prim②数据表示③算法实现细节primC#includetypedefstructpp{int}intg[100][100],u[100],v[100],vexnum;edgep[100];//用于记录最小生成树的各条边voidinput()//读入图的邻接矩阵{intFILEfor(i=1;i<=vexnum;i++){for{printf("%d}}}{inti,j,k,m,n,ma,s=0;for(i=1;i<=vexnum-1;i++)/vexnum-1{i

for/*v[k]!=0kV；g[u[j][k]>0{}}for(i=1;i<=vexnum-printf("\n%d%d%d",p[i].p,p[i].q,g[p[i].p][p[i].q]);}实验六 采用卡尔(kruskal)算法构造网络的最小生树C语言程序实现。3①卡你算法的主要步②数据表示③算法实现细节kruskalC#includetypedefstructpp/{intp,q,r;12}intg[100][100],sort[100],vexnum;//定义图的邻接矩阵，集合，顶点数edgep[100],temp;voidinput{intFILEfor(i=1;i<=vexnum;i++){for{printf("%d}}}{inti,j,k,for(i=1;i<=vexnum;i++)//初始时，每一顶点属于一个集合for(i=1;i<=vexnum-1;i++)/pfor(j=i+1;j<=vexnum;j++)if(g[i][j]>0){}for(i=1;i<l;i++)/{for(j=i+1;j<=l;j++)if(m>p[j].r){}}{{

printf("\n%d%d%d",p[i].p,p[i].q,p[i].r);//选择这条边if(sort[j]==l)sort[j]=sort[p[i].p];}}实验七回溯算法-一、实验目的与下面都是“-”14个“+”14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。 +给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。voidTriangle::Backtrack(int{if((count>half)||(t*(t-1)/2-count>half))return;if(t>n)sum++;for(inti=0;i<2;i++){for(intj=2;j<=t;j++)}for(intj=2;j<=t;j++)}}实验N皇一、上机实验的问题和要求1实现N二．程序设计的基本思想，原理和算法描述(1)NN(1)N皇后#defineN15#defineCswap(a,b){inttemp=a;a=b;b=intdig[2*N- intsec_dig[2*N- introw[N]; intcount;//8皇后的个数int//void{intfor(i=0;i<N;{for(j=0;j<N;{if(row[j]=={printf("Q}{printf("#}}}}//i0voidqueen(int{if(i>={ok=1;}if(ok=={}for(intk=i;k<N;{if(dig[row[i]-i+N-1]==0&&sec_dig[i+row[i]]==0){dig[row[i]-i+N-1sec_dig[i+row[i1;dig[row[i]-i+N-1sec_dig[i+row[i0;}}}void{ intt1=for(inti=0;i<N;{row[i]=} intt2= }实验装一、上机实验的问题和要求1二．程序设计的基本思想，原理和算法描述(1)c1c2船//必要条件:sum{wi}c1+c2#defineN4intx[N]; //x[i]=1表示w[i]装载在c1intw[N]; int //c1int //c2intc1;intint //c1void{for(inti=0;i<N;{if(x[i]!={}}}//i个物品,voidload(int{if(i>={ok=1;}if(ok=={}//w[i]c1x[i]=w1+=w[i];if(w1<=w1-=w[i];//w[i]c2x[i]=w2+=w[i];if(w2<=w2-=w[i];}void{c1=c2=for(inti=0;i<N;{w[i]=}}一、上机实验的问题和要求1二．程序设计的基本思想，原理和算法描述 Arrm[20] 代表图的第i条边 代表第j 代表第k 图的各个顶点的相邻的数组的中间变 最大团的顶点个 顶点转换的中间 顶点转换的中 typedef{intmaxlen;//对应各个顶点最大团的顶点个数intar[6][10];//最大团方案intnum;//voidTurn(Arrm[20],inta1[20][20],inta2[20][20],inti,int{intj,k(1),tem,len(1),m1,m2;intflag=1; {{for(j=1;j<=vertex-{}{}} {}}voidOutput(Arrm[20],inta1[20][20],inta2[20][20],intmax,int{int{cout<<len++<<")";for(k=0;k<=vertex-cout<<m[i].ar[j][k]<<"";}}void{intintvertex,edge;//顶点和边数Arrm[20];intinta[20][20]={0};//初始化过程cout<<"cout<<i<<"";cout<<"\n{}{}{}{cout<<array[i][j]<<"";}for(i=1;i<=vertex;i++)/{}{cout<<a[i][j]<<"";}for(i=1;i<=vertex;i++)/{}}实验十一验题目：二实三实验内容：解单源最短路径问题的优先队列式分支限界法用一极小堆来活结点Gs和空优先队列开始。ijij的所相应的路径验代usingnamespacestd;constintsize=constintinf=5000; constintn=6; //图顶点个数加1intprev[n]; intdist[]= intc[n][n] constintn=5; intprev[n]; intdist[]={0,0,5000,5000,5000}; class{publicint int classCirQueue{intfront,rear;MinHeapNodedata[size];front=rear=voidqueryIn(MinHeapNodeif((rear+1)%size!=rear=(rear+1)%size;//队尾指针在循环意义下加1data[rear]=e; }MinHeapNodequeryOut(){if(rear!=front){front=(front+1)%size; 1returndata[front];}}//队头元素，但不出队MinHeapNodegetQuery(){if(rear!=front){return}boolempty(){returnfront==boolfull(){return(rear+1)%size==}};//CirQueueclassGraph{*voidshortestPath(int{CirQueue;//定义源为初始扩展结点MinHeapNodee;e.i=v;e.length=dist[v]=.queryIn(e);for(intj={{}MinHeapNodem=.getQuery();if((c[m.i][j]<inf)&&(m.length+c[m.i][j]<dist[j])){ijdist[j]=m.length+c[m.i][j];prev[j]=m.i;MinHeapNodemi;mi.i= =dist[j]; }.queryIn(mi);}}//forif({}.queryOut();}//whileintmain(){Graphg;cout<<""<<dist[n-1]<<endl;cout<<"中间路径为：";for(inti=3;i<n;i++){cout<<prev[i]<<"";}return0;}验心得实验十二：分支限界法解装载问一、上机实验的问题和要求1二．程序设计的基本思想，原理和算法描述(1)三、源程序及注(1)装载问/*structQueue{intweight;structQueue*nextstructQueue*parent;bool int structQueue*nextint*bestxintbestw0Queue*Q;Queue*bestE; Queue*lq=NULL;Queue*fq=NULLintAdd(intw,Queue*E,bool{Queue*qq=(Queue*)malloc(sizeof(Queue));if(q==NULL){printf("没有足够的空间分配\n")return1;}q->next=NULL;q->weight=w;q->parent=E;q->LChild=l;if(Q->next==NULL){Q->next=qfqlqQ->next}{lq->next=q;lq=q;}return0}int{return1;return0}int{Queue*tmp=NULL;tmp=fq;//w=fq->weight;E=fq;Q->nextfq->next/*一定不能丢了链表头*/fq=fq->next;//free(tmp);return0;}voidEnQueue(intwt,int&bestw,inti,intnQueue*EQueue*&bestE,boolch)//该函数负责加入活结点wtQif(i==n){if(wt==bestE=E;bestx[n]=ch;}}Add(wtEch);}intMaxLoading(intw[],intc,int1interrinti=1;//当前扩展结点的层intEw0;intr=0;//剩余集装箱重量Queue*E=0;//当前扩展结点 for(intj=2;j<=n;j++)r+=bestw0;Q=(Queue*)malloc(sizeof(Queue));Q->next=NULL;Q->weight=-1errAdd(-1NULL0){return0}while{intwt=Ew+w[i]if(wt<=c){bestw=wt;//x[i]=EnQueue(Ew+w[i],bestw,i,n,E,bestE,}EnQueue(Ew,bestw,i,nEbestE0x[i]0Delete(E);//取下一个扩展结点if(E!=NULL&&E->weight==-if(IsEmpty())Add(-1NULL0)Delete(E);i++;r-=w[i]}Ew=E->weight}for(j=n-1;j>0;j--){bestx[j]=bestE->LChild;bestE=bestE->parent;}return0}int{intn=0;intc=0;inti=0;int*w;FILE*in,*outin=fopen("input.txt","r")out=fopen("output.txt","w");printf("没有输入输出文件\n")return1;}fscanf(in,"%d",&n)fscanf(in,"%d",&c)w=(int*)malloc(sizeof(int)*(n+1));bestx=(int*)malloc(sizeof(int)*(n+1));for(i=1;i<=n;i++)fscanf(in,"%d",&w[i]);MaxLoading(w,c,n);for(i=1;i<=n;i++)fprintf(stdout,"%d\t",bestx[i]);fprintf(stdout,"\n");return0;}实验十三遍一、上机实验的问题和要求二．程序设计的基本思想，原理和算法描述三、源程序及注图的深度优先(递归)基于链表typedefstruct intstructnodeNodeint voiddfs(intcurrent) { //该visit[current]=1; //设置标志为1，说明已经Node*ptr=head[current].next;while(ptr!={if(visit[ptr->val]==0)ptr=ptr-}}图的深度优先(递归)基于邻接矩阵#defineNint //0表示还没有被，1表示已经voiddfs(inta[N][N],intbegin){//begin点visit[begin]=1; for(inti=0;i<N;{if(a[begin][i]!=0&&visit[i]=={}}}图的深度优先(非递归)基于链#defineN5typedefstructnode{intstructnodeNodeint Node*stack[20];intvoiddfs(intcurrent) {visit[current]= Node*p=head[current].next;if(p!=NULL){{if(visit[p->val {stack[++top]=p; visit[p->val]=1; p&head[p }{pp- if(p== {pstack[top }}}while(top!= //top==0是完}}图的深度优先(非递归)基于邻接矩阵#defineNint //0表示还没有被，1表示已经/*------*/voiddfs(inta[N][N]){inti,j,k;intint for(i=0;i<N;i++){top=1; if(visit[i]==0){visit[i]=1; //k，j指示当前的地ki;//k行j0;//j列{if(a[k][j]!=0&&visit[j]==0&&j<{stack[top][0k;stack[top][1]=j;visit[j]=1; k=j;j=}elseif(j<{}{

k=j=}//endof}while(top!=}}//end}//end图的广度优先搜索(非递归基于#defineN5typedefstructnode{intstructnodeNodeintqueue[30]; intfront=0;intrear=int //标志数////(1)从图中某个顶点vi出发，//(2)vi的所有相邻接且未被的所有顶点//(3)vi1，vi2vimvij(1≦j≦m)vi，转(1);voidbfs(){inti,w;Node*p;for(i0iN {if(visit[i]=={printf("%d",i+1);visit[i]=1;queue[++rear]= while(front!={w=queue[++front];p=head[w].next;while(p!=NULL){if(visit[p->val]=={w=p->val;printf("%d",w+1);visit[w]=1;queue[++rear]=p-}p=p-}}//end}//end}//end}//end图的广度优先搜索(非递归基于#defineNintvisit[N];//0表示还没有被，1表示已经 voidbfs(int{intfront=0;//前指针用于出队列intrear1;//后指针用于进队列intqueue[20];//标识一个行intfor(i=0;i<N;{if(visit[i]=={visit[i]=1; //kk=i;{for(j=0;j<N;j++){if(a[k][j]!=0&&visit[j]=={queue[rearj;visit[j]=1; }}k= //}while(rear!=}//end}//end}//end实验十一子一、上机实验的问题和要求二．程序设计的基本思想，原理和算法描述1：2：O(n*log三、源程序及注转换法#defineN11intint//排序//a[1]a[10]排序voidsortArray(int*a){intfor(i=2;i<N;{intvalue=a[i];j=i-1;while(j>0&&a[j]>{a[j+1]=a[j];j--;}a[j+1]=}}voidfun(int*a){intint//for(i=1;i<N;i++)b[i]=a[i];//ab//c[i][jaib的前jfor(i=1;i<N;i++){for(j=1;j<N;{if(a[i]=={c[i][j]=c[i-1][j-1]+1;d[i][j]=1;}elseif(c[i-1][j]>c[i][j-{}{}}}}

c[i][j]=c[i-1][j];d[i][j]=2;c[i][j]=c[i][j-1];d[i][j]=3;voiddisplay(inti,intj,int*a){if(i==0||j==0)if(d[i][j]=={ }elseif(d[i][j]=={}{}}

void{intfor(inti=1;i<N;{a[i]=rand()%100; }}直接法#defineN11//数组 //b[i]=max{b[k}+1;intfun(int*a){intb[1]= intindex=1; intc[N]={0}; //记录怎样获得最长单调递增子列intmax=0; for(i=2;i<N;i++){//b[k]的最大值intlen=0;for(k=1;k<i;{if(b[k]len&&a[k]a[i{len= c[i]=}}b[i]=len+if(b[i]>max){max=b[i];index=i;}}//初始化Cintt=N-1;c[tindex;intm=0; intj=0; while(index>1){