算法设计与分析实验报告格式

算法设计与分析实验报告一

实验名称           统计数字问题                   评分               

实验日期        年          日      指导教师  ­­­   刘长松                 

姓名    刘飞初         专业班级      计算机0901       学号     10               

                                                                                  

.实验要求

1、掌握算法的计算复杂性概念。

2、掌握算法渐近复杂性的数学表述。

3、掌握用C++语言描述算法的方法。

4.实现具体的编程与上机实验,验证算法的时间复杂性函数。

.实验内容

   统计数字问题

1、问题描述

一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排,每个页码都不含多余的前导数字0。例如,第6 页用数字6 表示,而不是06 或006 等。数字计数问题要求对给定书的总页码n,计算出书的全部页码中分别用到多少次数字0,1, 2,…,9。

2、编程任务

给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0,1,2,…,9。

.程序算法

   将页码数除以10,得到一个整数商和余数,商就代表页码数减余数外有多少个1—9作为个位数,余数代表有1—余数本身这么多个数作为剩余的个位数,此外,商还代表1—商本身这些数出现了10次,余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。

.程序代码

#include<iostream.h>

int s[10]; //记录0~9出现的次数

int a[10]; //a[i]记录n位数的规律

void sum(int n,int l,int m)

{

  if(m==1)

{

int zero=1;

  for(int i=0;i<=l;i++) //去除前缀0

{

  s[0]-=zero;

  zero*=10;

}

}

if(n<10) 

  {

  for(int i=0;i<=n;i++)

  {

  s[i]+=1;

  }

  return;

  }//位数为1位时,出现次数加1

//位数大于1时的出现次数

  for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1)

{

m=1;int i;

for(i=1;i<t;i++)

m=m*10;

a[t]=t*m;

}

int zero=1;

  for(int i=0;i<l;i++)

  {

  zero*= 10;

  } //求出输入数为10的n次方

  int yushu=n%zero; //求出最高位以后的数

  int zuigao=n/zero; //求出最高位zuigao

  for(i=0;i<zuigao;i++)

  {

  s[i]+=zero;

  } //求出0~zuigao-1位的数的出现次数

  for(i=0;i<10;i++)

  {

  s[i]+=zuigao*a[l];

  } //求出与余数位数相同的0~zuigao-1位中0~9出现的次数

  //如果余数是0,则程序可结束,不为0则补上所缺的0数,和最高位对应所缺的数

if(yushu==0) //补上所缺的0数,并且最高位加1

  {

  s[zuigao]++;

  s[0]+=l;

  }

  else

  {

  i=0;

  while((zero/=10)>yushu)

  {

  i++;

  }

  s[0]+=i*(yushu+1);//补回因作模操作丢失的0

  s[zuigao]+=(yushu+1);//补回最高位丢失的数目

  sum(yushu,l-i-1,m+1);//处理余位数

}

}

void main()

{

  int i,m,n,N,l;

cout<<"输入数字要查询的数字:";

cin>>N;

cout<<'\n';

n = N;

  for(i=0;n>=10;i++)

  {

  n/=10;

  } //求出N的位数n-1

  l=i;

  sum(N,l,1);

  for(i=0; i<10;i++)

  {

  cout<< "数字"<<i<<"出现了:"<<s[i]<<"次"<<'\n';

  }

}

.程序调试中的问题

调试过程中总是有这样那样的问题,通过一步步的修改,最终得以实现。

.实验结果

算法设计与分析实验报告二

实验名称            分治法实现归并排序算法            评分             

实验日期        年          日      指导教师  ­­­     刘长松                

姓名   刘飞初       专业班级   计算机0901          学号      10           

                                                                                  

.实验要求

1.了解用分治法求解的问题:当要求解一个输入规模为n,且n的取值相当大的问题时,

如果问题可以分成k个不同子集合,得到k个不同的可独立求解的子问题,其中1<k≤n,而且子问题与原问题性质相同,原问题的解可由这些子问题的解合并得出。那末,对于这类问题分治法是十分有效的。

2.掌握分治法的一般控制流程。

DanC(p,q)

  global n,A[1:n]; integer m,p,q;  // 1£p£q£n

  if Small(p,q) then return G(p,q);

  else m=Divide(p,q); // p£m<q

      return Combine(DanC(p,m),DanC(m+1,q));

  endif

end DanC

3.实现典型的分治算法的编程与上机实验,验证算法的时间复杂性函数。

.实验内容

1.编程实现归并排序算法,程序中加入比较次数的计数功能,输出排序结果和比较次数。

2.输入10组相同的数据,验证排序结果和完成排序的比较次数。

3.与复杂性函数所计算的比较次数比较。

4.用表格列出比较结果。

5.给出文字分析。

.程序算法

1. 归并排序算法

procedure MERGESORT(low,high)

 //A(low;high)是一个全程数组,它含

有high-low+1≥0个待排序的元素//

  integer low,high;

   if low<high;

    then mid←          ,  //求这个集合的分割点//

     call  MERGESORT(low,mid)  //将一个子集合排序//

     call  MERGESORT(mid+1,high)  //将另一个子集合排序      

     call  MERGE(low,mid,high)  //归并两个已排序的子集合//

   endif

 end MERGESORT

归并两个已排序的集合

    procedure MERGE(low,mid,high)

   //A(low:high)是一个全程数组//

    //辅助数组B(low;high)//

    integer  h,i,j,k;

    h←low;i←low;j←mid+1;

    while  h≤mid  and   j≤high  do  //当两个集合都没取尽时//

      if  A(h)≤A(j)  then  B(i) ←A(h);h←h+1

       else  B(i) ←A(j);j←j+1

      endif

      i←i+1

    repeat

    if h>mid then

       for k←j  to high   do  //处理剩余的元素//

         B(i) ←A(k);i←i+1

       repeat

     else for k←h  to mid   do

              B(i) ←A(k);i←i+1

            repeat

    endif

   将已归并的集合复制到A

end MERGE

2. 快速排序算法

QuickSort(p,q)

//将数组A[1:n]中的元素

  A[p], A[p+1], ¼ , A[q]按不降次序排列,

  并假定A[n+1]是一个确定的、且大于

  A[1:n]中所有的数。//

 int p,q; global n, A[1:n];

 if p<q then

    j=Partition(p, q+1); // 划分后j成为划分元素的位置

    QuickSort(p,j-1);

    QuickSort(j+1,q);

 endif

 end QuickSort

procedure PARTITION(m,p)

    //退出过程时,p带着划分元素所在的下标位置。//

    integer  m,p,i;global  A(m:p-1)

    v←A(m);i←m  //A(m)是划分元素//

    loop

     loop   i←i+1  until  A(i)≥v  repeat  //i由左向右移//

     loop  p←p-1  until  A(p)≤v  repeat  //p由右向左移//

     if  i<p

       then  call  INTERCHANGE(A(i),A(p))  //A(i)和A(p)换位//

       else exit

      endif

    repeat

    A(m) ←A(p);A(p) ←v  //划分元素在位置p//

   End  PARTITION

.程序代码

归并排序

#include<iostream.h>

#include<iomanip.h>

#include<stdlib.h>

#include<time.h>

#define M 11

typedef int KeyType;

typedef int ElemType;

struct rec{

   KeyType key;

   ElemType data;

};

typedef rec sqlist[M];

class guibing{

public:

   guibing(sqlist b)

   {

       for(int i=0;i<M;i++)

           r[i]=b[i];

   }

       void output(sqlist r,int n)

       {

           for(int i=0;i<n;i++)

               cout<<setw(4)<<r[i].key;

           cout<<endl;

       }

       void xuanze(sqlist b,int m,int n)

       {

           int i,j,k;

           for(i=m;i<n-1;i++)

           {

               k=i;

               for(j=i;j<n;j++)

                   if(b[k].key>b[j].key) k=j;

                   if(k!=i)

                   {

                       rec temp=b[k];

                       b[k]=b[i];

                       b[i]=temp;

                   }

           }

       }

       void merge(int l,int m,int h,sqlist r2)

       {

           xuanze(r,l,m);

           xuanze(r,m,h);

           output(r,M);

           int i,j,k;

           k=i=l;

           for(j=m;i<m&&j<h;k++)

           {

               if(r[i].key<=r[j].key)

               {

                   r2[k]=r[i];

                   i++;

               }

               else

               {

                   r2[k]=r[j];

                   j++;

               }

               output(r2,M);

           }

           while(j<h)

           {

               r2[k]=r[j];

               j++;

               k++;

           }

           while(i<=m)

           {

               r2[k]=r[i];

               i++;

               k++;

           }

           output(r2,M);

       }

private:

   sqlist r;

   };

   void main()

   {

       cout<<"guibingfa1运行结果:\n";

       sqlist a,b;

       int i,j=0,k=M/2,n=M;

       srand(time(0));

       for(i=0;i<M;i++)

       {

           a[i].key=rand()%80;b[i].key=0;

       }

       guibing gx(a);

       cout<<"排序前数组:\n";

       gx.output(a,M);

       cout<<"数组排序过程演示:\n";

       gx.merge(j,k,n,b);

       cout<<"排序后数组:\n";

       gx.output(b,M);

       cin.get();

   }

快速排序

#include<iostream.h>

#include<iomanip.h>

#include<stdlib.h>

#include<time.h>

#define MAXI 10

typedef int KeyType;

typedef int ElemType;

struct rec{

   KeyType key;

   ElemType data;

};

typedef rec sqlist[MAXI];

class kuaisu

{

public:

   kuaisu(sqlist a,int m):n(m)

   {

       for(int i=0;i<n;i++) b[i]=a[i];

   }

   void quicksort(int s,int t)

   {

       int i;

       if(s<t){

           i=part(s,t);

           quicksort(s,i-1);

           quicksort(i+1,t);

       }

       else return;

   }

   int part(int s,int t)

   {

       int i,j;

       rec p;

       i=s;j=t;p=b[s];

       while(i<j)

       {

           while(i<j&&b[j].key>=p.key)j--;

           b[i]=b[j];

           while(i<j&&b[i].key<=p.key)i++;

           b[j]=b[i];

       }

       b[i]=p;

       output();

       return i;

   }

   void output()

   {

       for(int i=0;i<n;i++)

           cout<<setw(4)<<b[i].key;

       cout<<endl;

   }

private:

   sqlist b;

   int n;

};

void main()

{

   cout<<"kuaisu1.cpp运行结果:\n";

   sqlist a1;

   int i,n=MAXI,low=0,high=9;

   srand(time(0));

   for(i=0;i<n;i++)

       a1[i].key=rand()%80;

   kuaisu px(a1,n);

   cout<<"数组排序过程演示:\n";

   px.quicksort(low,high);

   cout<<"排序后数组:\n";

   px.output();

   cin.get();

}

.程序调试中的问题

1.  归并排序

2.  快速排序

算法设计与分析实验报告三

实验名称     动态规划算法实现多段图的最短路径问题       评分            

实验日期        年          日      指导教师  ­­­     刘长松             

姓名   刘飞初       专业班级   计算机0901          学号      10        

                                                                                  

.实验要求

1. 理解最优子结构的问题。

有一类问题的活动过程可以分成若干个阶段,而且在任一阶段后的行为依赖于该阶段的状态,与该阶段之前的过程如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在50年代,贝尔曼(Richard Bellman)等人提出了解决这类问题的“最优化原理”,从而创建了最优化问题的一种新的算法设计方法-动态规划。

对于一个多阶段过程问题,是否可以分段实现最优决策,依赖于该问题是否有最优子结构性质,能否采用动态规划的方法,还要看该问题的子问题是否具有重叠性质。

最优子结构性质:原问题的最优解包含了其子问题的最优解。

子问题重叠性质:每次产生的子问题并不总是新问题,有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。

2.理解分段决策Bellman方程。

每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。

 

Us  初始值,uj第j段的最优值。

3.一般方法

1) 找出最优解的性质,并刻画其结构特征;

2) 递归地定义最优值(写出动态规划方程);

3) 以自底向上的方式计算出最优值;

4) 根据计算最优值时得到的信息,构造一个最优解。

步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形,步骤4可以省略,步骤3中记录的信息也较少;若需要求出问题的一个最优解,则必须执行步骤4,步骤3中记录的信息必须足够多以便构造最优解。

.实验内容

1.编程实现多段图的最短路径问题的动态规划算法。

2.图的数据结构采用邻接表。

3.要求用文件装入5个多段图数据,编写从文件到邻接表的函数。

4.验证算法的时间复杂性。

.程序算法

多段图算法

procedure FGRAPH(E,k,n,P)

 //输入是按段的顺序给结点编号的,有n个结点

    的k段图。E是边集,c(i,j)是边<i,j>的成本。

     P(1:k)是最小成本路径。//

    real COST(n),integerD(n一1),P(k),r,j,k,n

    COST(n)← 0

    for j←n-1to 1by-1do  //计算COST(j)//

   设r是一个这样的结点,(j,r)ÎE且使c(j,r)+COST(r)取最小值

   COST(j)←c(j,r)+COST(r)

      D(j)←r

     repeat  //向前对j-1进行决策//

      P(1)←1;P(k)←n;

       for j←2 to k-1 do //找路径上的第j个节点//

           P(j)←D ( P(j-1) )

       repeat

    end   FGRAPH

.程序代码

多段图问题

#include<stdio.h>

#include<conio.h>

#include<malloc.h>

#define MAX_VERTEX_NUM 50

typedef struct ArcNode

{

   int adjvex; //该弧所指向的顶点的位置

   int value;  //该结点与邻接结点间的代价

   struct ArcNode *nextarc; //指向下一条弧的指针

}ArcNode, *node;

typedef struct VNode

{

   int data; //顶点信息

    ArcNode *firstArc; //指向第一条依附该顶点的弧的指针

}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct Graph

{

   AdjList vertices;

   int vexnum,arcnum; //图的当前顶点数和弧数

}*ALGraph;

int build_adList(ALGraph G,int n,int a)

{ //建立邻接表

   int v, m, i, t, h;

   node p, q;

   if(n < 0) return printf("ERROR");

   G->vexnum = n; //图的顶点数

   if(a < 0) return printf("ERROR");

   G->arcnum = a; //图的弧数

   for(m = 0; m < n; m++)

   {

       G->vertices[m].data = m;

       G->vertices[m].firstArc = NULL;

   }

   for(m = 1; m <= a; m++)

   {

       i = 1;

       printf("输入第%d条弧:", m);

       scanf("%d,%d,%d",&t,&h,&v);

       p = (ArcNode*)malloc(sizeof(ArcNode));

       p->adjvex = h;

       p->value = v;

       p->nextarc = NULL;

       while(G->vertices[i].data != t) i++; //转到下一个结点

       if(!G->vertices[i].firstArc) //终点

           G->vertices[i].firstArc = p;

       else

       { //若当前结点有后继节点则后移

           for(q = G->vertices[i].firstArc; q->nextarc; q = q->nextarc);

           q->nextarc = p; //新开辟结点

       }

   }

   return v;

}

void print_Graph(ALGraph G)

{ //打印邻接表

   ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode));

   int i;

   for(i = 1; i < G->vexnum; i++)

   {

       p = G->vertices[i].firstArc;

       printf("[%d]",i);

       while(p)

       {

           printf("->%d,%d",p->adjvex,p->value);//第i个结点的邻接结点信息

           p = p->nextarc;

       }

       printf("\n");

   }

}

void fgraph(ALGraph G ,int k,int n)

{ //多段图ALGraph G,n为结点数,k为图的段数

  //输入是按段的顺序给结点编号

   int cost[100];

   int d[100];

   int path[100];

   int j, r, i, min, w, value;

   node p;

   cost[n] = 0;

   for(j = n - 1; j >= 1; j--) //向前处理结点

   {

       p = G->vertices[j].firstArc;

       min = p->value+cost[p->adjvex]; //初始化路径最小代价

       r = p->adjvex;

       value = p->value;

       while(p != NULL)

       { //r是一个的这样的结点,权值c(j,r)+cost[r]取最小值

           if((p->value + cost[p->adjvex]) < min) 

           {

               min = p->value + cost[p->adjvex]; //p->value=c(j,r)

               r = p->adjvex;

               value = p->value;

           }

           p = p->nextarc;

       }

       cost[j] = value + cost[r]; //当前节点的代价值

       d[j] = r; //决策阶段,各结点到终点最小代价路径上前方顶点的编号

   }

   path[1] = 1; path[k] = n;

   for(i = 2; i <= k - 1; i++) //找出最小代价路径上的结点

       path[i] = d[path[i - 1]];

   printf("最小成本为:%d\n",cost[1]);

   printf("最小成本路径为: ");

   for(w = 1; w <= k; w++)

       printf("%d->", path[w]);

}

void main()

{

   ALGraph g; 

    int n,a,k;

   g = (ALGraph)malloc(sizeof(ALGraph));

    printf("请输入多段图节点数目:");

    scanf("%d", &n);

   printf("请输入多段图边的数目:");

    scanf("%d", &a);

   printf("请输入多段图的段数:");

   scanf("%d", &k);

    printf("输入多段图的弧的信息(弧头,弧尾,权值)\n");

   build_adList(g, n, a);

    printf("多段图的邻接表为:\n");

   print_Graph(g);

    fgraph(g, k, n);

    getch();

}

五.实验结果

多段图问题

算法设计与分析实验报告四

实验名称          贪心算法实现背包问题                 评分            

实验日期        年          日      指导教师  ­­­     刘长松                

姓名   刘飞初       专业班级     计算机0901        学号   10             

                                                                                  

.实验要求

1. 优化问题

   有n个输入,而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组

成,而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。那些使目标函数取极值(极大或极小)的可行解,称为最优解。

2.贪心法求优化问题

算法思想:在贪心算法中采用逐步构造最优解的方法。在每个阶段,都作出一个看上去最优的决策(在一定的标准下)。决策一旦作出,就不可再更改。作出贪心决策的依据称为贪心准则(greedy criterion)。

3.一般方法

1)根据题意,选取一种量度标准。

2)按这种量度标准对这n个输入排序

3)依次选择输入量加入部分解中。如果当前这个输入量的加入,不满足约束条件,则不把此输入加到这部分解中。

procedure GREEDY(A,n) /*贪心法一般控制流程*/

    //A(1:n)包含n个输入//

    solutions←φ  //将解向量solution初始化为空/

    for i←1  to  n do

     x←SELECT(A)

     if  FEASIBLE(solution,x)

      then solutions←UNION(solution,x)

     endif

    repeat

    return(solution)

end GREEDY

4. 实现典型的贪心算法的编程与上机实验,验证算法的时间复杂性函数。

.实验内容

1. 编程实现背包问题贪心算法。通过具体算法理解如何通过局部最优实现全局最优,并验证算法的时间复杂性。

2.输入5个的图的邻接矩阵,程序加入统计prim算法访问图的节点数和边数的语句。

3.将统计数与复杂性函数所计算的比较次数比较,用表格列出比较结果,给出文字分析。

.程序算法

1.   背包问题的贪心算法

  procedure  KNAPSACK(P,W,M,X,n)

    //P(1:n)和W(1;n)分别含有按

      P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值

      和重量。M是背包的容量大小,而x(1:n)是解向量

    real P(1:n),W(1:n),X(1:n),M,cu;

    integer i,n;

X←0  //将解向量初始化为零

    cu←M  //cu是背包剩余容量

    for i←1 to n do

      if  W(i)>cu  then  exit  endif

      X(i) ←1

       cu←cu-W(i)

    repeat

    if  i≤n  then  X(i) ←cu/ W(i)

    endif

  end GREEDY-KNAPSACK

procedure  prim(G,)

status←“unseen”                     // T为空

 status[1]←“tree node”              // 将1放入T

for each edge(1,w) do

   status[w]←“fringe”               // 找到T的邻接点

   dad[w] ←1;                      //w通过1与T建立联系

     dist[w] ←weight(1,w)          //w到T的距离

  repeat

while status[t]≠ “tree node” do

  pick a fringe u with min dist[w]  // 选取到T最近的节点

  status[u]←“tree node”

  for each edge(u,w) do

   修改w和T的关系

  repeat

repeat

2.   Prim算法

PrimMST(G,T,r){
  //求图G的以r为根的MST,结果放在T=(U,TE)中
    InitCandidateSet(…);//初始化:设置初始的轻边候选集,并置T=({r},¢)
    for(k=0;k<n-1;k++){ //求T的n-1条树边
        (u,v)=SelectLiShtEdge(…);//选取轻边(u,v);
         T←T∪{(u,v)};//扩充T,即(u,v)涂红加入TE,蓝点v并人红点集U
        ModifyCandidateSet(…); //根据新红点v调整候选轻边集
      } 
   }

1.  背包问题贪心算法

#include <iostream.h>

struct goodinfo

{

 float p; //物品效益

 float w; //物品重量

 float X; //物品该放的数量

 int flag; //物品编号

};//物品信息结构体

void Insertionsort(goodinfo goods[],int n)

{

 int j,i;

 for(j=2;j<=n;j++)

 {

  goods[0]=goods[j];

     i=j-1;

  while (goods[0].p>goods[i].p)

  {

   goods[i+1]=goods[i];

   i--;

  }

  goods[i+1]=goods[0];

 }

}//按物品效益,重量比值做升序排列

void bag(goodinfo goods[],float M,int n)

{

 float cu;

 int i,j;

 for(i=1;i<=n;i++)

  goods[i].X=0;

 cu=M;  //背包剩余容量

 for(i=1;i<n;i++)

 {

  if(goods[i].w>cu)//当该物品重量大与剩余容量跳出

   break;

   goods[i].X=1;

   cu=cu-goods[i].w;//确定背包新的剩余容量

 }

 if(i<=n)

  goods[i].X=cu/goods[i].w;//该物品所要放的量

for(j=2;j<=n;j++)

 {

  goods[0]=goods[j];

     i=j-1;

  while (goods[0].flag<goods[i].flag)

  {

   goods[i+1]=goods[i];

   i--;

  }

  goods[i+1]=goods[0];

 }

cout<<"最优解为:"<<endl;

 for(i=1;i<=n;i++)

 {

  cout<<"第"<<i<<"件物品要放:";

  cout<<goods[i].X<<endl;

 }

}

void main()

{

 cout<<"|--------运用贪心法解背包问题---------|"<<endl;

 cout<<"|-------------------------------------|"<<endl;

 int j;

 int n;

 float M;

 goodinfo *goods;//定义一个指针

 while(j)

 {

 cout<<"请输入物品的总数量:";

 cin>>n;

 goods=new struct goodinfo [n+1];//

 cout<<"请输入背包的最大容量:";

 cin>>M;

 cout<<endl;

 int i;

 for(i=1;i<=n;i++)

  { goods[i].flag=i;

   cout<<"请输入第"<<i<<"件物品的重量:";

   cin>>goods[i].w;

   cout<<"请输入第"<<i<<"件物品的效益:";

   cin>>goods[i].p;

   goods[i].p=goods[i].p/goods[i].w;//得出物品的效益,重量比

   cout<<endl;

  }

 Insertionsort(goods,n);

 bag(goods,M,n);

 cout<<"press <1> to run agian"<<endl;

 cout<<"press <0> to exit"<<endl;

 cin>>j;

 }

}

2.  Prim算法

#include <stdio.h>

#include <stdlib.h>

#include <iostream.h>

#define INFINITY INT_MAX

#define MAX_VERTEX_NUM 20

typedef int VRType;

typedef int InfoType;

typedef char VerTexType;

typedef struct ArcCell

{

 VRType adj;

 InfoType *info;

}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct

{

 VerTexType vexs[MAX_VERTEX_NUM];

 AdjMatrix arcs;

 int vexnum, arcnum;

}MGraph;

typedef struct

{

 VerTexType adjvex;

 VRType lowcost;

}closedge[MAX_VERTEX_NUM];

void CreateGraph(MGraph &G);

void MiniSpanTree_PRIM(MGraph G, VerTexType u);

int LocateVex(MGraph G, VerTexType u);

int minimum(closedge close);

void main( void )

{

 int i, j;

 MGraph G;

 CreateGraph(G);

 for(i = 0; i < G.vexnum; i++)

 {

  for(j = 0; j < G.vexnum; j++)

  {

   cout<<G.arcs[i][j].adj;

   cout<<" ";

  }

  cout<<endl;

 }

 MiniSpanTree_PRIM(G, 'a');

}

void CreateGraph(MGraph &G)

{

 int weigh;

 int i, j = 0, k = 0;

 char hand, tide;

 cout<<"input the number for vexnum and arcnum:";

 cin>>G.vexnum>>G.arcnum;

 for(i = 0; i < G.vexnum; i++)

 {

  for(j = 0; j < G.vexnum; j++)

   G.arcs[i][j].adj = 88;

 }

 cout<<endl;

 cout<<"input"<<G.vexnum<<"char for vexs:";

 for(i=0; i < G.vexnum; i++)

  cin>>G.vexs[i];

 cout<<endl;

 cout<<"input"<<G.arcnum<<"arc(char,char,weigh):"<<endl;

 j = 0;

 k = 0;

 for(i=0; i < G.arcnum; i++)

 {

  cout<<i<<":";

  cin>>hand;

  cin>>tide;

  cin>>weigh;

  while (hand != G.vexs[j])

   j++;

  while (tide != G.vexs[k])

   k++;

  G.arcs[j][k].adj = weigh;

  G.arcs[k][j].adj = weigh;

  j = 0;

  k = 0;

  cout<<endl;

 }

}

void MiniSpanTree_PRIM(MGraph G,VerTexType u)

{

 int i, j, k = 0;

 closedge close;

 k = LocateVex ( G, u );

 for ( j = 0; j < G.vexnum; j++ )

 {

  if (j != k)

  {

   close[j].adjvex = G.vexs[k];

   close[j].lowcost = G.arcs[k][j].adj;

  }

 }

  close[j].lowcost = 88;

  close[j].adjvex = '\0';

  close[k].lowcost = 0;

  close[k].adjvex = u;

 for (i = 1; i < G.vexnum; i++)

 {

  k = minimum(close);

  cout<<close[k].adjvex;

  cout<<"---->";

  cout<<G.vexs[k]<<" ";

  cout<<close[k].lowcost<<endl;

  close[k].lowcost = 0;

  for (j=0; j<G.vexnum; j++)

  {

   if (G.arcs[k][j].adj < close[j].lowcost)

   {

    close[j].adjvex = G.vexs[k];

    close[j].lowcost = G.arcs[k][j].adj;

   }

  }

 }

}

int LocateVex(MGraph G, VerTexType u)

{

 int k = 0;

 while(G.vexs[k++] == u)

   return k-1;

 return 0;

}

int minimum(closedge close)

{

 int j1=0, client = 88, j2;

 while(close[j1].adjvex != '\0')

 {

  if (client > close[j1].lowcost && close[j1].lowcost != 0)

  {

   client = close[j1].lowcost;

   j2 = j1;

  }

  j1++;

 }

 return j2;

}

五.实验结果

1. 背包问题贪心算法

相关推荐