实验报告规范(20xx)20(3600字)

发表于:2021.9.6来自:www.fanwen118.com字数:3600 手机看范文

《数据结构与算法分析》实验报 姓名 李妍___ 学号 20121183067 年 月日

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. 测试结果

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

实验报告规范20xx20

5. 附件

见20121183067_李妍.cpp



更多类似范文
┣ 实验报告1 2200字
┣ 实验四实验报告 400字
┣ 实验报告一(附图)
┣ 实验报告-实验三 3400字
┣ 更多实验报告
┗ 搜索类似范文

更多相关推荐:
实验报告2800字

并行处理及体系结构实验报告ParallelComputingandarchitectureExperimentReport班级学号姓名指导教师信息学院20xx年11月实验一MPI安装与程序编译运行和调试1实验目...

实验报告1

实验报告1,内容附图。

实验报告标准答案11800字

课程名称实验报告1成绩评定实验项目名称指导教师实验项目编号实验项目类型实验地点学生姓名学号学院系专业实验时间年月日午月日午一实验目的1熟悉VB编程环境能够建立编译和运行VB程序2掌握窗体标签文本框命令按钮图形框...

专栏推荐
大家在关注

地图地图CC