实验 4 图的基本操作
- 格式：doc
- 大小：89.00 KB
- 文档页数：12
实验 4 图的基本操作
计算11-2 18 陶盛科
程序 1
#include
#include
struct stu
{
char name[3];
struct stu * next;
};
struct stt
{
struct stu * head;
int shu;
int jz[10][10];
};
struct stt * jltu()
{
int i=0,j=0;
struct stt * p;
p=(struct stt *)malloc(sizeof(struct stt));
p->head=NULL;
p->shu=0;
for(;i<10;i++)
for(j=0;j<10;j++)
p->jz[i][j]=0;
return p;
}
void txtu(struct stt * p)
{
void scjd(struct stt * p);
int i,j,k=0;
struct stu * p1,* p2;
printf("输入节点数（<10）:\n");
scanf("%d",&i);
getchar();
p->shu=i;
p->head=p1=(struct stu *)malloc(sizeof(struct stu));
printf("输入第%d个结点名字:\n",p->shu-i); gets(p1->name);
while(--i)
{p2=(struct stu *)malloc(sizeof(struct stu));
p1->next=p2;
printf("输入第%d个结点名字:\n",p->shu-i);
gets(p2->name);
p1=p2;}
p2->next=NULL;
printf("填充领结矩阵:（1:有，0:没有）\n");
p1=p->head;
p2=p1->next;
for(i=0;p1;i++)
{
for(j=i+1;p2;j++,p2=p2->next)
{printf("结点%s和结点%s有无关联？\n",p1->name,p2->name);
scanf("%d",&k);
if(k)
{p->jz[i][j]=1;
p->jz[j][i]=1;}
}
p1=p1->next;
if(p1)
p2=p1->next;
}
scjd(p);
}
void scjd(struct stt * p)
{
int i=0,j=0;
struct stu * p1;
p1=p->head;
while(p1)
{printf("姓名:%s\n",p1->name);
p1=p1->next;}
printf("临接矩阵为:\n");
for(;i<10;i++)
{for(j=0;j<10;j++)
printf(" %d ",p->jz[i][j]);
printf("\n");}
}
void bianli(struct stt * p)
{
void gdbl(struct stt * p,int j,int b[10]);
void sdbl(struct stt * p,struct stu * p1,int b[10]); int i,j,b[10]={1,1,1,1,1,1,1,1,1,1};
struct stu * p1;
i=p->shu;
while(i--)
b[i]=0;
printf("从第几个结点开始遍历？\n");
scanf("%d",&i);
p1=p->head;
j=i-1;
while(--i)
p1=p1->next;
printf(" 深度遍历:\n");
sdbl(p,p1,b);
i=p->shu;
while(i--)
b[i]=0;
printf("\n");
printf(" 广度遍历:\n");
gdbl(p,j,b);
}
void gdbl(struct stt * p,int i,int b[10])
{
int j=0,m,k=0,a[10]={11,11,11,11,11,11,11,11,11,11};
struct stu * p1;
a[j++]=i;b[i]=1;
while(!pd(b))
{i=a[k];m=0;
while(m<10)
{if(p->jz[i][m]&&!b[m]) {a[j++]=m;b[m]=1;}
m++;}
k++;}
k=0;
while(a[k]!=11)
{j=a[k++];
p1=p->head;
while(j--)
p1=p1->next;
printf("----%s---",p1->name);
}
}
int pd(int b[10])
{
int i=0;
while(i<10) {if(!b[i]) break;
i++;}
if(i==10&&b[9])
return 1;
return 0;
}
void sdbl(struct stt * p,struct stu * p1,int b[10])
{
int pd(int b[10]);
int i=0,j=0;
struct stu * p2=p->head;
printf("----%s---",p1->name);
while(p2!=p1)
{p2=p2->next;
j++;}
b[j]=1;
while(ishu)
{if(pd(b)) break;
if(p->jz[j][i]&&!b[i])
{p2=p->head;
while(i--)
p2=p2->next;
sdbl(p,p2,b);}
i++;}
}
int main()
{
struct stt * p;
p=jltu();
txtu(p);
bianli(p);
printf("\n");
return 0;
}
程序 2
#include
#include
struct st
{
int wz; int chang;
struct st * next;
};
struct stu
{
char name[3];
struct st * s;
};
struct stt
{
struct stu dian[10];
int dd,hs;
char kd[4];
};
struct stt * jlt()
{
struct stt * p;
p=(struct stt *)malloc(sizeof(struct stt));
p->dd=0;
p->hs=0;
return p;
}
struct st * tchh(struct stt * p,int i)
{
int j,k=0,m;
struct st * pp,* p1,* p2;
printf("顶点%d的出度为几？\n",i);
scanf("%d",&j);
if(!j)
return NULL;
while(kdd)
{if(i==k) k++;
printf("顶点%d和顶点%d有无关联？（0:没有）",i,k);
scanf("%d",&m);
if(m) break;
k++;}
pp=p1=(struct st *)malloc(sizeof(struct st));
if(!p1) printf("建立空间失败!\n");
printf("输入该弧长:\n");
scanf("%d",&p1->chang);
pp->wz=k;
pp->next=NULL;
j--;
k++;
