求助《数据结构》课程设计--图的建立及输出问题描述

沙发

中国台湾 [专家分：2140] 发布于 2006-06-25 00:59:00

你参考一下
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 10
#define ERROR 0
typedef char VertexType;
typedef int VPType;
typedef int Graphkind;
typedef int status;
typedef enum {FALSE, TRUE} boolean;
boolean visit[MAX_VERTEX_NUM];
typedef struct Arcell
{
VPType adj;
}Arcell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
VertexType vex[MAX_VERTEX_NUM];//顶点标志或者叫代号
int vexnum, arcnum;//点的个数和边的条数
AdjMatrix arcs;
Graphkind kind;//图的类型
}MGraph;

status  CreatGraph(MGraph *G)       //建立图
{
int i, j, select;

printf("1:建立有向图!\n");
printf("2:建立无向图!\n");
printf("3:请选者种类!\n");
scanf("%d",&select);
    if (select == 1)
{
  G->kind = 0;
}
else if (select == 2)
{
  G->kind = 1;
}
else
{
  return ERROR;
}

printf("\n请输入顶点的个数:");
scanf("%d",&G->vexnum);
    getchar();// 吃掉内存中的残留数据
printf("\n 请输入顶点的信息(代号)");
for ( i = 0; i < G->vexnum; i++)
{
  scanf("%c",&G->vex[i]);//注意一下

}

getchar();
printf("\n 请输入2个顶点之间的相互关系(0表示相邻 1表示不相邻):\n");
for ( i = 0 ; i < G->vexnum; i++)
  for ( j = 0; j < G->vexnum; j++)
  {
   scanf("%d",&G->arcs[i][j].adj);
  }

   printf("建立成功\n");
   return 0;
}

板凳

中国台湾 [专家分：2140] 发布于 2006-06-25 01:00:00

status qiudu(const MGraph *G)//求度操作
{
int sum1 , sum2 = 0;
    int i, j;

if (G->kind == 1)
{
  for ( i = 0; i < G->vexnum; i++)
  {
   sum1=0;
   for ( j = 0; j < G->vexnum; j++)
   {
    if ( G->arcs[i][j].adj == 1)
    {
     sum1++;
    }
   }
   printf("编号为%c的第%d的点的度为%d\n",G->vex[i], i+1, sum1);
  }
}
else
{
  for ( i = 0 ; i < G->vexnum; i++)
  {
    sum1=0, sum2=0;
   for ( j = 0 ; j < G->vexnum; j++)
   {
    if ( G->arcs[i][j].adj == 1)
    {
     sum1++;
                }
    if ( G->arcs[j][i].adj == 1)
    {
     sum2++;
    }
   }
   printf("编号为%d的第%d的点的出度为%d入度为%d\n",G->vex[i], i+1, sum1,sum2);

  }
}

return 0;
}

void DFS(MGraph G) //深搜索   这里出现问题
{
int i, j;
    void DFS1( MGraph G, int i);//函数声明

for (i = 0 ; i < G.vexnum; i++)
{
  visit[i] = FALSE;
}
for (j = 0; j <G.vexnum; j++)
{
  if (!visit[j])
   DFS1(G,j);//不要用&G 因为G已经是地址了
}

// return 0;
}

void DFS1(MGraph G, int i)
{
int j;

visit[i]=TRUE;
printf("%c",G.vex[i]);

for (j = 0; j < G.vexnum; j++)
{
  if ((i != j) && (G.arcs[i][j].adj == 1) && !visit[j])
  {
   DFS1(G,j);
  }
}

// return 0;
}

status BFS( const MGraph *G,int k)//广度搜索
{
   int s = 0, g = 0;
   int i, j;
   char a[MAX_VERTEX_NUM];

   for (i = 0; i < G->vexnum; i++)
   {
    visit[i] = FALSE;
   }

   printf("%c ",G->vex[k]);
   visit[k]=TRUE;

   for ( j = 0; j < G->vexnum; j++)
   {
    a[j] = -1;
   }
   a[s] = k;

   while(a[s]!=-1)
   {
    int j;

    i = a[g];
    g++;
       for ( j = 0; j < G->vexnum; j++)
    {
     if (G->arcs[i][j].adj == 1 && !visit[j])
     {
      printf("%c ",G->vex[j]);
      visit[j] = TRUE;
      s++;
      a[s] = j;
     }

    }
   if ( s == G->vexnum-1)
   {
   break;
   }
   }
   return 0;
}

int main(void)
{
    MGraph G;
    int flag, select;
int flag1 = 0;
int k;
while(1)
{
  do
  {
   printf("1:构建图\n");
   printf("2:求度\n");
   printf("3:深度搜索\n");
   printf("4:广度搜索\n");
   printf("5:退出\n");
   printf("6:请选择\n");
   scanf("%d",&select);
   if (select == 5)
   {
    flag = 0;
   }
         else
   {
    flag = 1;  //这里出错
   }
  }while(select < 1 || select > 6);

        if (flag == 0)
  {
   break;
  }
  switch(select)
  {
   case 1:
               flag1 = 1;
               CreatGraph(&G);
      break;
        case 2:
               if(flag1 == 1)
      {
                  qiudu(&G);
      }
      else
      {
      printf(" 请先建立图\n");
      }
      break;
        case 3:
      if(flag1 == 1)
      {
                   printf("进行深度搜索:\n");
       DFS(G);
          printf("进行深度搜索:\n");
       printf("\n");
      }
      else
      {
                    printf(" 请先建立图\n");
      }
      break;

        case 4:
      if(flag1 == 1)
      {
       printf("请哪个点开始搜索");
          scanf("%d",&k);
       getchar();
       printf("进行广度搜索\n");
       BFS(&G,k);
       printf("\n");
      }
               else
      {
                    printf(" 请先建立图\n");
      }
      break;

  default: continue;
  }
}

}

3 楼

47656748 [专家分：0] 发布于 2006-06-27 19:11:00

谢谢1\2楼的"中国台湾",你给出的这些,我运行了一下,成功运行,但好像没法输出图的邻接矩阵,还有吗?
谢谢!

4 楼

a204480 [专家分：90] 发布于 2006-07-04 00:53:00

我这个是有向图的建立与输出：

#define max 20
#include<malloc.h>
#include<iostream>
using namespace std;
typedef struct ArcNode//定义表结点
{int adjvex;//该弧所指向顶点的位置
struct ArcNode *nextarc;//指向下一条弧的指针
int info;//该弧的权值
}ArcNode;
typedef struct VNode//定义头结点
{int data;//顶点信息
ArcNode *firstarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[max];
typedef struct//定义ALGraph
{AdjList vertices;
int vexnum,arcnum;//图的当前顶点数和弧数
int kind;//图的种类标志
}ALGraph;

void CreateDG(ALGraph &G)//创建邻接表的图
{int k,i,j;
char tag;
cout<<"请输入图的顶点数目:"<<endl;//输入顶点数目
cin>>G.vexnum;
cout<<"请输入图的弧的数目:"<<endl;//输入弧的数目
cin>>G.arcnum;
cout<<"请确认是否输入弧的权值(y/n):"<<endl;
cin>>tag;
for(i=1;i<=G.vexnum;++i)
{G.vertices[i].data=i;//初始化顶点值
  G.vertices[i].firstarc=NULL;//初始化指针
}

cout<<"请输入弧的相关信息arc(V1-->V2)"<<endl;//构造弧
for(k=1;k<=G.arcnum;++k)
{cout<<endl<<"请输入弧头"<<"[1,"<<G.vexnum<<"]:";
  cin>>i;
  cout<<"请输入弧尾"<<"[1,"<<G.vexnum<<"]:";
  cin>>j;
  while(i<1||i>G.vexnum||j<1||j>G.vexnum)//如果弧头或弧尾不合法,重新输入
{cout<<endl<<"请再次输入弧头"<<"[1,"<<G.vexnum<<"]:";
  cin>>i;
  cout<<"请再次输入弧尾"<<"[1,"<<G.vexnum<<"]:";
  cin>>j;
}

  ArcNode *p;
  p=(ArcNode*)malloc(sizeof(ArcNode));//分配内存
  if(!p)
  {cout<<"Overflow!";//如果没有足够的空间,则退出
  }
  p->adjvex=j;//对弧结点的弧顶点数据域赋值
  p->nextarc=G.vertices[i].firstarc;//对弧结点下一条弧指针域赋值
  p->info=0;                // 对弧结点相关信息指针域赋值
  G.vertices[i].firstarc=p;    // 将弧结点插入到对应的单链表
  if(tag=='y')
  {cout<<"请输入弧的权值:";
   cin>>p->info;
  }
  }
}

void ShowMGraph(ALGraph G)
{int *a,i,k;
ArcNode *p;
a=(int*)malloc((G.vexnum*G.vexnum+1)*sizeof(int));
for(i=1;i<=G.vexnum*G.vexnum;i++)
a[i]=0;
for(i=1;i<=G.vexnum;i++)
  for(p=G.vertices[i].firstarc;p;p=p->nextarc)
  {k=p->adjvex;
   ++a[(i-1)*G.vexnum+k];
  }
for(i=1;i<=G.vexnum*G.vexnum;i++)
{cout<<a[i]<<" ";
  if(i%G.vexnum==0)
  cout<<endl;
}
}

int main()//主函数
{ALGraph G;
cout<<"=============================="<<endl;
cout<<"======1.创建邻接表图=========="<<endl;
cout<<"======2.输出邻接表图=========="<<endl;
cout<<"======3.退出=================="<<endl;
cout<<"=============================="<<endl;
cout<<"请选择操作:"<<endl;
int a;
l1:
{cin>>a;
}
system("cls");
while(a<=3)
{switch(a)
{case 1:
         cout<<"请正确创建邻接表图:"<<endl;
         CreateDG(G);
         cout<<"Create ALGraph success !"<<endl;
         cout<<"请选择操作:"<<endl;
         goto l1;
         break;
  case 2:
         cout<<"输出该邻接矩阵图如下:"<<endl;
         cout<<"=================="<<endl;
         ShowMGraph(G);
         cout<<"该图输出完毕!"<<endl;
         cout<<"=================="<<endl;
         cout<<"请选择操作:"<<endl;
         goto l1;
         break;

  case 3:
         return 0;
}
}
return 0;
}

5 楼

tgbtgb [专家分：490] 发布于 2006-08-20 10:09:00

#define max 100
#include "malloc.h"
typedef struct
{char dd[max];
int w[max][max];
int bs;
int dds;
}g;
g *creat2(void)
{g *mg;
int i,j,a,b,c,v1,v2,v3;
char aa,w1,w2;
mg=(g *)malloc(sizeof(g));
    printf("请输入顶点数和边数:\n");

scanf("%d%d",&mg->dds,&mg->bs);
printf("请输入各个顶点:(为一个字符)\n");
for(b=0;b<mg->dds;b++)
{printf("NO.%d\n",b+1);

   scanf("%c",&aa);
    scanf("%c",&mg->dd[b]);
    }
for(i=0;i<mg->dds;i++)
    for(j=0;j<mg->dds;j++)
        mg->w[i][j]=0;
    for(a=0;a<mg->bs;a++)
    {printf("请输入A-到-B的权值w(注:总共要输入3个.):\n");
    scanf("%c",&aa);
    scanf("%c",&w1);
    printf("\n到\n");
    scanf("%c",&aa);
    scanf("%c",&w2);
    printf("\n权值:\n");
    scanf("%c",&aa);
    scanf("%d",&v3);
    for(c=0;c<mg->dds;c++)
    {if(w1==mg->dd[c])
        v1=c+1;
    if(w2==mg->dd[c])
        v2=c+1;
    }
    mg->w[v1-1][v2-1]=v3;
    }
    return(mg);
}
void print2(g *mm)
{int i,j,v1,v2;
printf("数组表示为:\n");
printf("\n");

for(i=0;i<mm->dds;i++)
    {for(j=0;j<mm->dds;j++)
        printf("%4d",mm->w[i][j]);
    printf("\n");
    }
    printf("\n");
    printf("其它信息为:\n");
    printf("\t总共有顶点:      %d\n",mm->dds);
    printf("\t总共有边:      %d\n",mm->bs);
    printf("\t相通的顶点为:\n");
for(v1=0;v1<mm->dds;v1++)
    for(v2=0;v2<mm->dds;v2++)
if(mm->w[v1][v2]!=0)
    printf("\n\t%c---到---%c\n",mm->dd[v1],mm->dd[v2]);
        }

g *creat1(void)
{g *mg;
int i,j,a,b,c,v1,v2,v3;
char aa,w1,w2;
mg=(g *)malloc(sizeof(g));
    printf("请输入顶点数和边数:\n");

scanf("%d%d",&mg->dds,&mg->bs);
printf("请输入各个顶点:(为字符)\n");
for(b=0;b<mg->dds;b++)
{printf("NO.%d\n",b+1);

   scanf("%c",&aa);
    scanf("%c",&mg->dd[b]);
    }
for(i=0;i<mg->dds;i++)
    for(j=0;j<mg->dds;j++)
        mg->w[i][j]=0;
    for(a=0;a<mg->bs;a++)
    {printf("请输入A-连-B的权值w(注:总共要输入3个.):\n");
    scanf("%c",&aa);
    scanf("%c",&w1);
    printf("\n通\n");
    scanf("%c",&aa);
    scanf("%c",&w2);
    printf("\n权值:\n");
    scanf("%c",&aa);
    scanf("%d",&v3);
    for(c=0;c<mg->dds;c++)
    {if(w1==mg->dd[c])
        v1=c+1;
    if(w2==mg->dd[c])
        v2=c+1;
    }
    mg->w[v1-1][v2-1]=v3;
    mg->w[v2-1][v1-1]=v3;
    }
return(mg);
}
void print1(g *mm)
{int i,j,v1,v2;
printf("\n");
printf("\n");
printf("\n");
printf("数组表示为:\n");
printf("\n");

for(i=0;i<mm->dds;i++)
    {for(j=0;j<mm->dds;j++)
        printf("%4d",mm->w[i][j]);
    printf("\n");
    }
    printf("\n");
    printf("\t其它信息为:\n");
    printf("\t总共有顶点:      %d\n",mm->dds);
    printf("\t总共有边:      %d\n",mm->bs);
printf("\t相通的顶点为:\n");
for(v1=0;v1<mm->dds;v1++)
    for(v2=0;v2<mm->dds;v2++)
        if(mm->w[v1][v2]!=0&&v1>=v2)
            printf("\t%c---通---%c\n",mm->dd[v1],mm->dd[v2]);
        }
main()
{g *m,*n;
int fag,i;
do{
printf("\n");
printf("\t=====================\n");
printf("\t1----------建立有向图.\n");
printf("\t2----------输出有向图.\n");
printf("\t3----------建立无向图.\n");
printf("\t4----------输出无向图.\n");
printf("\t0----------退出.\n");
printf("\t=====================\n");
printf("\n");
printf("请选择:\n");
scanf("%d",&i);
switch(i)
{case 0:fag=0;break;
case 1:m=creat2();break;
case 2:print2(m);break;
case 3:n=creat1();break;
case 4:print1(n);break;
defult :printf("ERROR\n");
    }
}while(fag);

}

6 楼

gugen [专家分：0] 发布于 2006-08-28 01:40:00

谢谢,我也要一个

您尚未登录，请登录后再回复。点此登录或注册

主题：求助《数据结构》课程设计--图的建立及输出问题描述

回复列表（共6个回复）

我来回复

程序员工具箱 new

代码片段