计算机应用 | 古代文学 | 市场营销 | 生命科学 | 交通物流 | 财务管理 | 历史学 | 毕业 | 哲学 | 政治 | 财税 | 经济 | 金融 | 审计 | 法学 | 护理学 | 国际经济与贸易
计算机软件 | 新闻传播 | 电子商务 | 土木工程 | 临床医学 | 旅游管理 | 建筑学 | 文学 | 化学 | 数学 | 物理 | 地理 | 理工 | 生命 | 文化 | 企业管理 | 电子信息工程
计算机网络 | 语言文学 | 信息安全 | 工程力学 | 工商管理 | 经济管理 | 计算机 | 机电 | 材料 | 医学 | 药学 | 会计 | 硕士 | 法律 | MBA
现当代文学 | 英美文学 | 通讯工程 | 网络工程 | 行政管理 | 公共管理 | 自动化 | 艺术 | 音乐 | 舞蹈 | 美术 | 本科 | 教育 | 英语 |

图的遍历-自动化毕业论文网

2013-06-12 01:03
导读:自动化论文毕业论文,图的遍历-自动化毕业论文网论文模板,格式要求,科教论文网免费提供指导材料:   1.需求分析  【实验目的】  很多涉及图上

 

1.需求分析 
【实验目的】
 很多涉及图上操作的算法都是以图的遍历操作为基础的,通过这个实验的算法设计,可以巩固所学的有关图的基本知识。
【基本要求】
   以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列。 
2.算法设计
1)为了实现上述程序功能,需要定义单链表的抽象数据类型:
定义边结点   ArcNode
数据成员      int adjvex;
              struct ArcNode *nextarc;
定义顶点信息   VNode 
数据成员      VertexType data;
               ArcNode *firstarc;
定义无向图    typedef struct                    
数据成员     AdjList vertices;
              int vexnum,arcnum;
定义链表      typedef struct LNode
数据成员     ElemType data;
              struct LNode *next;
定义头结点    typedef struct QNode   
数据成员     QElemType data;
              struct QNode *next;
定义队列      typedef struct   
数据成员     QueuePtr front;
              QueuePtr rear; (科教作文网 zw.nseac.com整理)
2)本程序用到的主要函数:
InitQueue(LinkQueue &Q)    //初始化队
EnQueue(LinkQueue &Q,QElemType e)   //入队
DeQueue(LinkQueue &Q,QElemType &e)   //出队
LocateVex(ALGraph G,char v)      //确定v在G中的位置
CreateDG(ALGraph &G)     //创建无向连通图的邻接表结构
FirstAdjvex(ALGraph G,int v)  //返回G中顶点v的第一个邻接点
NextAdjVex(ALGraph G,int v,int w)   //返回G中顶点v相对于w的下一个邻接点
BFSTraverse(ALGraph G)   //进行深度优先遍历
DFS(ALGraph G,int v,int *visited)
DFSTraverse(ALGraph G)   //进行广度优先遍历3.调试分析
 刚开始输入的是abcdef可是遍历出来的是123456的数字,后来将入前的出输改写成G.vertices[w].data形式就可以了。
4.经验收获和体会
   每次都要写这个,我都不知写什么好了呵呵,嗯总体来说还是那句话程序要自已编出来的才叫好。无论编得怎么样总会学到东西的,编写的同时也可以复习以前的知识这样很好。
5.测试数据及结果
 
 
 
6.附录
#include"iostream.h"
#include"stdlib.h"
typedef char VertexType;
typedef int QElemType;
typedef int ElemType;
typedef int Status;
#define MAX 20
#define ok 1
bool visit[MAX];
typedef struct ArcNode //定义边结点
{
 int adjvex;
    struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode  //定义顶点信息
{
 VertexType data;
    ArcNode *firstarc;
}VNode,AdjList[MAX];
typedef struct    //定义无向图                    

(转载自http://www.NSEAC.com中国科教评价网)


{
 AdjList vertices;
    int vexnum,arcnum;
}ALGraph;
typedef struct LNode //定义链表
{
 ElemType data;
    struct LNode *next;
}LNode,*LinkList;
typedef struct QNode    //定义头结点
{
   QElemType data;
   struct QNode *next;
}QNode,*QueuePtr;
typedef struct    //定义队列
{
 QueuePtr front;
    QueuePtr rear;
}LinkQueue;
Status InitQueue(LinkQueue &Q)    //初始化队
{
 Q.front=new QNode;
    if(!Q.front)exit(-1);
    Q.front->next=NULL;
    Q.rear=Q.front;
 return ok;
}
Status EnQueue(LinkQueue &Q,QElemType e)   //入队
{
    QueuePtr p;
 p=new QNode;
    if(!p)exit(-1);
    p->data=e;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
 return ok;
}
Status DeQueue(LinkQueue &Q,QElemType &e)   //出队
{
 if(Q.front==Q.rear)return false;
 QueuePtr p;
 p=Q.front->next;
    Q.front->next=p->next;
    e=p->data;
    if(Q.rear==p)Q.rear=Q.front;
 delete p;
    return ok;
}
int LocateVex(ALGraph G,char v)      //确定v在G中的位置
{
 for(int i=0;i<G.vexnum;i++)
  if(G.vertices[i].data==v)
   return i;
 if(i==G.vexnum)
  {
   cout<<"你的输入有错请重新输入"<<endl;
   return -1; 您可以访问中国科教评价网(www.NsEac.com)查看更多相关的文章。
  }
 return 0;
}
void  CreateDG(ALGraph &G)     //创建无向连通图的邻接表结构
{
 cout<<"请输入图的结点数:"<<endl;
 cin>>G.vexnum;
 cout<<"请输入图的边数:"<<endl;
 cin>>G.arcnum;
 for(int i=0;i<G.vexnum;i++)     //构造表头向量
 {
  cout<<"请输入第"<<i+1<<"个结点的信息"<<endl;
  cin>>G.vertices[i].data;
  G.vertices[i].firstarc=NULL;   //初始化头结点  
 }
 char v1,v2;
 for(int k=0;k<G.arcnum;k++)   //输入各边并构造邻接表
 {
  cout<<"请输入第"<<k+1<<"条边所对应的的两个结点"<<endl;
e:
  cin>>v1>>v2;
  int s=LocateVex(G,v1);   //确定v1在G中的位置
  int t=LocateVex(G,v2);   //确定v2在G中的位置
  if(s<0||t<0)
   goto e;
  ArcNode *p=new ArcNode;
        p->adjvex=t; 
  ArcNode *q=G.vertices[s].firstarc;    //采用头插法插入链表
  G.vertices[s].firstarc=p;
  p->nextarc=q;  //因为是无向图,每条边对应两个结点
  s=LocateVex(G,v2);
  t=LocateVex(G,v1);
  p=new ArcNode;
  p->adjvex=t;
  q=G.vertices[s].firstarc;
  G.vertices[s].firstarc=p;
  p->nextarc=q;
 }
}
void BFSTraverse(ALGraph G)   //进行广度优先遍历
{
  int v,w,u;
    int visited[MAX];

中国大学排名


    LinkQueue Q;
    for(v=0;v<G.vexnum;++v)
  visited[v]=0;
    InitQueue(Q);
    for(v=0;v<G.vexnum;++v)
 if(visited[v]==0)
 { 
   visited[v]=1;
   cout<<G.vertices[v].data<<" ";
   EnQueue(Q,v);
   while(!(Q.rear==Q.front))
   {
    DeQueue(Q,u); 
    for(w=G.vertices[u].data;
    G.vertices[u].firstarc!=NULL;
    w=G.vertices[u].firstarc->adjvex,
     G.vertices[u].firstarc=G.vertices[u].firstarc->nextarc)
     if(visited[w]==0)
     {
      visited[w]=1;
      cout<<G.vertices[w].data<<" ";
      EnQueue(Q,w);  
     }
   }
     }
}
void DFS(ALGraph G,int v,int *visited)

 int w;
 visited[v]=1;
 cout<<G.vertices[v].data<<" ";
 for(w=G.vertices[v].data;
 G.vertices[v].firstarc!=NULL;
 w=G.vertices[v].firstarc->adjvex,
  G.vertices[v].firstarc=G.vertices[v].firstarc->nextarc)
    if(visited[w]==0)
   DFS(G,w,visited);
}
void DFSTraverse(ALGraph G)   //进行深度优先遍历
{
    int v;
      int visited[MAX];
      for(v=0;v<G.vexnum;++v)
  visited[v]=0;
    for(v=0;v<G.vexnum;++v)
  if(visited[v]==0) (科教作文网http://zw.ΝsΕac.cOM编辑)
  DFS(G,v,visited);
}

int main()//主函数
{
  ALGraph G;
    CreateDG(G);
  cout<<"深度优先遍历序列:";
  DFSTraverse(G);
  cout<<endl;
  cout<<"广度优先遍历序列:";
    BFSTraverse(G);
  cout<<endl;
    return 0;

    上一篇:自制快速干手器-自动化毕业论文网 下一篇:没有了