《数据结构与算法分析》实验报

姓名     李妍___       学号   20121183067

__ 2014  __年  ___5_月__  19   __日

1.    上机题目：

实现下图的邻接矩阵存储、输出图的深度优先搜索、图的广度优先搜索的序列算法。

2. 需求分析

明确说明程序的开发环境和功能要求。针对主要功能，给出如下说明：

（1）  输入参数的格式和合法取值范围

输入的格式为int 整形数据，其合法取值范围为：-21474836～2147483647

（2）  输出的格式 ：%3d

（3）  测试数据:(1,2,12),(1,3,9),(3,1,-3),(3,5,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7),

3. 详细设计

(1)确定存储结构，并给出所用数据类型的数据结构定义

typedef int VertexData;

typedef struct Node

{

    int data;

    struct Node *next;

}LinkQueueNode;

typedef struct

{

    LinkQueueNode *front;

    LinkQueueNode *rear;

}LinkQuenue;

typedef struct

{

   VertexData vertex[MAX_VERTEX_NUM];//顶点向量

   int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵

   int vexnum,arcnum;//图的顶点数和弧数

}AdjMatrix;

(2)给出所用数据类型中每个操作的伪码算法

1. int LocateVertex(AdjMatrix *G,VertexData v)//求顶点位置函数

{

    int j=Error,k;

    for(k=0;k<G->vexnum;k++)

       if(G->vertex[k]==v)

       {

           j=k;

           break;

       }

       return(j);

} 

2.int CreateUDG(AdjMatrix &G)//创建无向图

{

    int i,j,k;

    VertexData v1,v2;

    printf("请输入图的顶点数:");

    scanf("%d",&G.vexnum);

    printf("请输入图的弧数:");

    scanf("%d",&G.arcnum);

    for(i=0;i<G.vexnum;i++)

       for(j=0;j<G.vexnum;j++)

           G.arc[i][j]=0;

    printf("请输入图的顶点:");

    for(i=0;i<G.vexnum;i++)

       scanf("%d",&G.vertex[i]);

    printf("请输入一条弧的两个顶点\n");

    for(k=0;k<G.arcnum;k++)

    {

       scanf("%d,%d",&v1,&v2);

       i=LocateVertex(&G,v1);

       j=LocateVertex(&G,v2);

       G.arc[i][j]=1;

       G.arc[j][i]=1;

    }

    return(ok);

}

3.void Display(AdjMatrix &G)

{

    int i,j;

    printf("该无向图的邻接矩阵如下图所示\n");

    for(i=0;i<G.vexnum;++i)

    {

       for(j=0;j<G.vexnum;++j)

           printf("%d ",G.arc[i][j]);

       printf("\n");         

    }                

}

4.void DepthFirstSearch(AdjMatrix G,int a)  //深度优先搜索

{  

    int j;

    printf(" %d ",a);

    visited[a-1]=True;

    for(j=1;j<=G.vexnum;j++)

       if(visited[j-1]!=True&&G.arc[a-1][j-1]==1)

           DepthFirstSearch(G,j);

}

5.int InitQueue(LinkQuenue *Q)//链队列的初始化

{

    Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));

    if(Q->front!=NULL)

    {

       Q->rear=Q->front;

       Q->front->next=NULL;

       return(True);

    }

    else return(Error);

}

6.int EnterQueue(LinkQuenue *Q,int v0)//入队

{

    LinkQueueNode *p;

    p=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));

    if(p!=NULL)

    {

       p->data=v0;

       p->next=NULL;

       Q->rear->next=p;

       Q->rear=p;

       return(True);

    }

    else return(Error);

}

7.int DeleteQueue(LinkQuenue *Q,int *x)//出队

{

    LinkQueueNode *p;

    if(Q->front==Q->rear)

       return(Error);

    p=Q->front->next;

    Q->front->next=p->next;

    if(Q->rear==p)

       Q->rear=Q->front;

    *x=p->data;

    free(p);

    return(True);

}

8.int Empty(LinkQuenue Q)//判断队列是否为空

{

    if(Q.front==Q.rear)

       return(True);

    else return(0);

}

9.int FirstAdjVertex(AdjMatrix G,int k)//找第一个邻接点

{

    int i;

    for(i=0;i<G.vexnum;i++) 

       if(G.arc[k][i]==1&&visited[i]!=1)    

            {

             return(i); 

           }

         return(Error) ;

}

10.int NextAdjVertex(AdjMatrix G,int v,int v1)//找其他邻接点

{

    int i;

    for(i=v1+1;i<G.vexnum;i++)

       {

           if(G.arc[v][i]==1&&visited[i]!=1)

              break;

       }

    if(i!=G.vexnum)

       return(i);

        return(Error);

}

11.void BreadthFirstSearch(AdjMatrix G,int b) //广度优先搜索

{

    LinkQuenue Q;

    int w,i;

    for(i=0;i<MAX_VERTEX_NUM;i++)

        visited[i]=0;

    printf(" %d ",b);

    visited[b-1]=1;

    InitQueue(&Q);

    EnterQueue(&Q,b);

    while(!Empty(Q))

    {

       DeleteQueue(&Q,&b);

       w=FirstAdjVertex(G,b-1);

       while(w!=Error)

       {

           printf(" %d ",w+1);

           visited[w]=1;

           EnterQueue(&Q,w+1);

           w=NextAdjVertex(G,b-1,w);

       }

    }

}

4调试分析

（1）  程序的调试中主要还是对基本概念，基本操作，不太熟悉了解，各种小问题程出不穷，

（2）  经验和体会

4. 测试结果

采用测试数据，列出实际的输入、输出结果。

5.  附件

见20121183067_李妍.cpp