minitree.cpp

数据结构课程设计

#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
#define infinate 10000
typedef struct graph /* 图的结构*/
{int **matrix;     /*结点关系矩阵*/
char *vertex;      /*字符结点*/
int arcs,vernum;  /*边的条数，结点个数*/
}graph;
typedef struct   /* 关系矩阵*/
{char adjvex;
int lowcost;
}close;

 int locate(graph g,char ch) /* 确定结点序号*/
 { int find;
    int i;
 for(i=0;i<g.vernum;i++)
       if(ch==g.vertex[i])
    {find=i; break;}
    if(i==g.vernum)
 return(-1);
 return(i);
 }

   int minimum(close *closedge,int n) /*查找最小边*/
   {int i;
   static int a=0;
   int k=-1;
     for(i=0;i<n;i++)
  {while((i<n-1)&&closedge[i].lowcost==0)/*寻找有效边*/
   i++;
  if(i==n-1&&closedge[i].lowcost==0) break;
    if(k==-1) k=i;
    else if(closedge[i].lowcost<closedge[k].lowcost)
        k=i;
   }
  return(k);
   }

void graph_input(graph &g)  /*图的输入*/
{int i,j,n,m;
  printf("输入结点个数:");
  scanf("%d",&m);
  g.vernum=m;
  g.vertex=(char*)malloc(m*sizeof(char));
   g.matrix=(int**)malloc(m*sizeof(int));
  for(i=0;i<m;i++)
  g.matrix[i]=(int*)malloc(m*sizeof(int));
  for(i=0;i<m;i++)
   for(j=0;j<m;j++)
    if(i==j)
      g.matrix[i][j]=0;
           else g.matrix[i][j]=infinate;/*距离无穷大*/
   printf("连续输入结点字符回车结束:");
   fflush(stdin);
    for(i=0;i<m;i++)
      scanf("%c",&g.vertex[i]);
   printf("输入边的条数:");
   scanf("%d",&n);
   g.arcs=n;
   printf("输入边和距离，边的两个字符连续输，如边为ab,距离为5则输入(ab 5):\n");
       for(i=0;i<n;i++)
       {  int  v1,v2;
          char vt1,vt2;
    int w;
     fflush(stdin);      /*清空输入流缓存*/
        scanf("%c%c%d",&vt1,&vt2,&w);
        v1=locate(g,vt1);v2=locate(g,vt2);
        g.matrix[v1][v2]=g.matrix[v2][v1]=w;
    }
  for(i=0;i<m;i++)
   for(j=0;j<m;j++)
    printf(j==m-1?"%d\n":"%d ",g.matrix[i][j]);

}

     void minitree(graph &g)
  {int i,j,k;
  char ch;
  close *closedge;
  closedge=(close*)malloc(g.vernum*sizeof(close));/*申请与已有结点有关边的关系组，此数组用于存放剩余结点到与入选节点的最短距离，在选择中不断赋值*/
  printf("输入开始的结点:");
  fflush(stdin);
  scanf("%c",&ch);
  k=locate(g,ch);
   for(i=0;i<g.vernum;i++)
   if(i!=k) {closedge[i].adjvex=ch;closedge[i].lowcost=g.matrix[k][i];}/*赋初值*/
      closedge[k].lowcost=0;
   for(i=1;i<g.vernum;i++)
   { k=minimum(closedge,g.vernum);/*寻找与已有结点有关的边的权最小边*/
   if(k==-1) break;
      printf("%c%c  %d\n",closedge[k].adjvex,g.vertex[k],closedge[k].lowcost);
   closedge[k].lowcost=0;
      for(j=0;j<g.vernum;j++)
    if(closedge[j].lowcost!=0)
    { if(g.matrix[k][j]<closedge[j].lowcost)/*调整其他接点到已有接点的最小距离*/
    {closedge[j].adjvex=g.vertex[k]; closedge[j].lowcost=g.matrix[k][j];}
    }
   }
  }



void main()
{graph g;
graph_input(g);
minitree(g);

}