问一道数据结构 求无向图和邻接表的习题麻烦老师讲解.
编辑： admin 2017-23-02
-
4
类似问题
类似问题1：数据结构：无向图适合邻接矩阵,有向图适合邻接表这句话对吗,并给出理由[数学科目]
这句话不对,邻接表和邻接矩阵,即可以存储无向图也可以存储有向图,稠密图适合用邻接矩阵,稀疏图适合用邻接表存储
类似问题2：数据结构题.假定无向图G有6个结点和9条边,.(1) 画出G的邻接距阵和邻接表(2) 根据邻接表从顶点3假定无向图G有6个结点和9条边,并依次输入这9条边为（0,1）（0,2）（0,4）（0,5）（1,2）（2,3）（2
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<malloc.h>
#define maxsize 64
#define TRUE 1
#define FALSE 0
#define n 6
#define e 9
typedef char datatype ;
typedef char vextype;
typedef int adjtype;
typedef struct
{
vextype vexs[maxsize];
adjtype arcs[maxsize][maxsize];
}graph;
typedef struct
{
datatype data[maxsize];
int front,rear;
}sequeue;
typedef struct node
{
int adjvex;
struct node *next;
}edgenode;
typedef struct
{
vextype vertex;
edgenode *link;
}vexnode;
vexnode gl[maxsize];
graph *ga;
sequeue *Q;
graph *CREATGRAPH()
{
int i,j,k;
char ch;
system("cls");
scanf("%c",&ch);
printf("\n请输入顶点信息(邻接矩阵): ");
for(i=1;i<=n;i++)
scanf("%c",&ga->vexs[i]);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
ga->arcs[i][j]=0;
printf("\n输入节点信息与权值：\n");
for(k=0;k<e;k++)
{
scanf("%d%d",&i,&j);//读入一条变得两端顶点序号i,j及边上的权值
ga->arcs[i][j]=1;
ga->arcs[j][i]=1;
}
return ga;
}
void PRINT()
{
int i,j;
system("cls");
printf("\n对应的邻接矩阵是：\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%5d",ga->arcs[i][j]);
printf("\n");
}
}
void CREATADJLIST()
{
int i,j,k;
edgenode *s;
char ch;
system("cls");
printf("请输入顶点信息: ");
scanf("%c",&ch);
for(i=1;i<=n;i++)
{
gl[i].vertex=getchar();
gl[i].link=NULL;
}
printf("输入边表节点信息：\n");
for(k=1;k<=e;k++)
{
scanf("%d %d",&i,&j);
s=(edgenode *)malloc(sizeof(edgenode));
s->adjvex=j;
s->next=gl[i].link;
gl[i].link=s;
s=(edgenode *)malloc(sizeof(edgenode));
s->adjvex=i;
s->next=gl[j].link;
gl[j].link=s;
}
}
void PRINTL()
{
int i;
edgenode *s;
system("cls");
printf("\n对应的邻接表是：\n");
for(i=1;i<=n;i++)
{
s=gl[i].link;
printf("%3c",gl[i].vertex);
while(s!=NULL)
{
printf("%5d",s->adjvex);
s=s->next;
}
printf("\n");
}
}
sequeue *SETNULL(sequeue *P)
{
P->front=maxsize-1;
P->rear=maxsize-1;
return P;
}
int EMPTY(sequeue *Q)
{
if(Q->rear==Q->front)
return TRUE;
else
return FALSE;
}
sequeue *ENQUEUE(sequeue *Q,int k)
{
if(Q->front==(Q->rear+1)%maxsize)
{
printf("队列已满!\n");
return NULL;
}
else
{
Q->rear=(Q->rear+1)%maxsize;
Q->data[Q->rear]=k;
}
return Q;
}
int DEQUEUE(sequeue *Q)
{
if(EMPTY(Q))
{
printf("队列为空,无法出队!\n");
return FALSE;
}
else
{
Q->front=(Q->front+1)%maxsize;
return Q->data[Q->front];
}
return 1;
}
void BFS(int k)
{
int i,j;
int visited[maxsize]={0};
printf("\n广度优先遍历后得到的序列是: ");
Q=SETNULL(Q);
printf("%3c",ga->vexs[k]);
visited[k]=TRUE;
Q=ENQUEUE(Q,k);
while(!EMPTY(Q))
{
i=DEQUEUE(Q);
for(j=1;j<=n;j++)
if((ga->arcs[i][j]==1)&&(!visited[j]))
{
printf("%3c",ga->vexs[j]);
visited[j]=TRUE;
Q=ENQUEUE(Q,j);
}
}
printf("\n\n深度优先遍历后得到的序列是: ");
}
void BFSL(int k)
{
int i;
int visited[maxsize]={0};
edgenode *p;
Q=SETNULL(Q);
printf("\n广度优先遍历后得到的序列是: ");
printf("%3c",gl[k].vertex);
visited[k]=TRUE;
Q=ENQUEUE(Q,k);
while(!EMPTY(Q))
{
i=DEQUEUE(Q);
p=gl[i].link;
while(p!=NULL)
{
if(!visited[p->adjvex])
{
printf("%3c",gl[p->adjvex].vertex);
visited[p->adjvex]=TRUE;
Q=ENQUEUE(Q,p->adjvex);
}
p=p->next;
}
}
printf("\n\n深度优先遍历后得到的序列是: ");
}
void DFS(int i)
{
int j;
static int visited[maxsize]={0};
printf("%3c",ga->vexs[i]);
visited[i]=TRUE;
for(j=1;j<=n;j++)
if((ga->arcs[i][j]==1)&&(!visited[j]))
DFS (j);
}
void DFSL(int k)
{
int j;
edgenode *p;
static int visited[maxsize]={0};
printf("%3c",gl[k].vertex);
visited[k]=TRUE;
p=gl[k].link;
while(p)
{
j=p->adjvex;
if(!visited[j])
DFSL(j);
p=p->next;
}
}
void main()
{
int i,k;
int ch;
Q=malloc(sizeof(graph));
ga=malloc(sizeof(graph));
while(1)
{
printf("\n\n\n");
printf("输入你的选择: ");
scanf("%d",&ch);
switch(ch)
{
case 1: CREATADJLIST();
PRINTL();
printf("想从第几号结点开始: ");
scanf("%d",&k);
BFSL(k);
DFSL(k);break;
case 2: ga=CREATGRAPH();
PRINT();
printf("想从第几号结点开始: ");
scanf("%d",&i);
BFS(i);
DFS(i);break;
case 3:exit (0);
}
}
}
PS:下标从1开始的,输入矩阵的对应元素时要按你的顺序输入 输入表的顺序是要逆序输入 否则两者答案不匹配 因为表的选择要有大小要求的 你可以试一下.
类似问题3：数据结构关于图的一道题[数学科目]
题在哪呢?
你是要找题...?
类似问题4：数据结构与算法实验题 条形图轮廓问题★实验任务在x 轴上水平放置着n 个条形图.条形图的轮廓是消去这n 个条形图的隐藏线后得到的图形,如图所示.每个条形图由3 元组（Li,Hi,Ri）表示.其中,[数学科目]
#include
#include
#include
#define LBound (-3000)
#define UBound 3000
#define Cod2Idx(x) ((x)-LBound)
#define Size Cod2Idx(UBound+1)
int main() {
int hs[Size],n;
int i,l,r,h,i0,i1;
memset(hs,0,sizeof(*hs) * Size);
scanf("%d",&n);
for (i0=UBound,i1=LBound; n>0; n--) {
scanf("%d %d %d",&l,&h,&r);
if (l < i0) i0 = l;
if (r > i1) i1 = r;
for (i=l; i
类似问题5：【数据结构】 填空第14题 求图求解析
树的形状如下：
A
/ \
B C
\ / \
D E F
/ \
G H
所以中序遍历为：BGDAEHCF