数据结构 / 2019级数据结构

//王世康 2班 2019012299 2班 12/1

1、2、

3、

#include<stdio.h>
#include<stdlib.h>
typedef struct adjnode{
       int vexindex;
	   struct adjnode*next;
}adjnode;
typedef struct vexnode{
      int data;
	  int indegree;
	  adjnode*firstAdjNode;
}vexnode;
typedef struct algragh{
      vexnode array[50];
	  int vexnum,edgenum;
}algrath;

void function(algragh &gragh ){
    adjnode*q=NULL;
	for(int i=0;i<gragh.vexnum;i++){
		gragh.array[i].indegree=0;
	}
	for(int i=0;i<gragh.vexnum;i++){
		if(gragh.array[i].firstAdjNode==NULL){
		      continue;
		}else{
			q=gragh.array[i].firstAdjNode;
			while(q){
				gragh.array[i].indegree
				q=q->next;
			}
		}
	}		
}

/**

姓名：宫梦南

学号：2015015391

班级：2015级5班

日期：2020年12月1日

**/

第2题：

从顶点2出发得到的：

（1） DFS序列：2-1-4-3-5-6

（2） BFS序列：2-1-3-5-4-6

第3题

（1）首先创建图的邻接表存储结构结构体
#include <stdio.h>
#include <stdlib.h>
#define Max_Vertex_Num 100
typedef struct ArcNode{
    int adjvex; //此题用不到
    struct ArcNode *nextarc;//下一个节点
    int weight;//权重-此题用不到
}ArcNode;
/*表头节点*/
typedef struct VNode{
    int vertex;//表头数组的数据
    ArcNode *firstarc;//表头数组的表头节点域
}VNode; 
 
typedef VNode Adjlist[Max_Vertex_Num];//VNode构成的表头节点数组
 
/*整个邻接表*/
typedef struct{
    Adjlist adjlist;//每个定点后面的链表，记录关联点
    int vexnum,arcnum;//顶点数和边数
}ALGraph;
（2）主函数的结构如下，先输入图的类型（gType）
int main()
{
    ALGraph G;
    int gType;//定义类型 0是无向图，1是有向图
    scanf("%d",&gType);
    CreateALGraph(&G,gType);
    
    if(gType!=0)
        CountInDegree(&G);//计算入度
    }
    return 0;
}
（3）有了主函数的大致结构，然后根据输入的图的类型分类创建图
int LocateVex(ALGraph *G,int u){
    int i;
    for(i = 0; i<G->vexnum;++i)
    {
        if(G->adjlist[i].vertex == u)
        {
            return i;
        }
    }
    return -1;
}
/*创建图*/
void CreateALGraph(ALGraph *G,int gType)
{
    ArcNode *p;
    int i,j,k;
    int v1,v2;
 
    scanf("%d,%d",&G->vexnum,&G->arcnum); //输入顶点数和边数
 
    if(gType==0)
    {
        for(k=0;k<G->vexnum;k++)
        {
            G->adjlist[k].vertex = k;
            G->adjlist[k].firstarc = NULL;
        }
        k = 0;
        while(k<G->arcnum){
            scanf("%d,%d",&v1,&v2);
            k++;
            i = LocateVex(G,v1);
            j = LocateVex(G,v2);
            /*给第i的表头添加数据是j的节点*/
            p=(ArcNode*)malloc(sizeof(ArcNode));
            p->adjvex = j;
            p->nextarc = G->adjlist[i].firstarc;
            G->adjlist[i].firstarc = p;
            /*给第j的表头添加数据是i的节点*/
            p=(ArcNode*)malloc(sizeof(ArcNode));
            p->adjvex = i;
            p->nextarc = G->adjlist[j].firstarc;
            G->adjlist[j].firstarc = p;
        }
    }else{
         for(k=0;k<G->vexnum;k++)
        {
            G->adjlist[k].vertex = k;
            G->adjlist[k].firstarc = NULL;
        }
        k = 0;
        while(k<G->arcnum){
            scanf("%d,%d",&v1,&v2);
            k++;
            i = LocateVex(G,v1);
            j = LocateVex(G,v2);
            /*给第i的表头添加数据是j的节点——有向图，不需要给j添加i数据的节点了*/
            p=(ArcNode*)malloc(sizeof(ArcNode));
            p->adjvex = j;
            p->nextarc = G->adjlist[i].firstarc;
            G->adjlist[i].firstarc = p;
        }
    }
}
（4）求入度的代码如下
/*计算入度*/
void CountInDegree(ALGraph *G)
{
    ArcNode *p;
    int i;
    int j;
    //数组存放每个顶点的入度数量，赋初始值都为0
    int arr[G->vexnum];
    for(i=0;i<G->vexnum;i++)
    {
        arr[i]=0;
    }
    for(i = 0;i<G->vexnum;i++)
    {
        p = G->adjlist[i].firstarc;
        while(p!=NULL)
        {
            //根据有向图的结构
            //表头节点后面连接的表体的数据p->adjvex，出现一次就是作为入度一次
            //比如0后面有1，2，那么顶点1和2肯定都作为后驱一次，就有一个入度
            arr[p->adjvex]++;
            //指针移动到下一个表体
            p=p->nextarc;
        }
 
    }
    
    
    /*输出*/
    for(i=0;i<G->vexnum;i++){
        if(i!=G->vexnum-1)
            printf("%d ",arr[i]);
        else
            printf("%d",arr[i]);
    }
 
    printf("\n");
}