《2013年中国矿业大学徐海学院计算机系《软件认知实践》报告》由会员分享，可在线阅读，更多相关《2013年中国矿业大学徐海学院计算机系《软件认知实践》报告（26页珍藏版）》请在金锄头文库上搜索。
1、中国矿业大学徐海学院计算机系软件认知实践报告姓 名： 学 号： 专 业： 设计题目： 指导教师： 2013年12月30日目 录第1章 题目概述2第1.1节 题目要求2第1.2节 主要难点3第2章 系统流程图4第3章 数据结构和算法5第4章 核心代码分析6第5章 复杂度分析25参考文献25第1章 题目概述第1.1节 题目要求(1)自选存储结构,输入含n个顶点（用字符表示顶点）和e条边的图G；(2)求每个顶点的度,输出结果；(3)指定任意顶点x为初始顶点,对图G作DFS遍历,输出DFS顶点序列(提示:使用一个栈实现DFS)；(4)指定任意顶点x为初始顶点,对图G作BFS遍历,输出BFS顶点序列(提
2、示:使用一个队列实现BFS)；(5)输入顶点x,查找图G:若存在含x的顶点,则删除该结点及与之相关连的边,并作DFS遍历(执行操作3)；否则输出信 息“无x”；(6)判断图G是否是连通图，输出信息“YES”/“NO”；(7)如果选用的存储结构是邻接矩阵,则用邻接矩阵的信息生成图G的邻接表,即复制图G,然再执行操作(2)；反之亦然。第1.2节 主要难点(1)自选存储结构创建一个图：通过用户从键盘敲入的两个数值分别确定图的顶点数和边数，选择邻接矩阵存储结构将图的结点信息存储在一个顺序表中，图的边信息存储在一个二维数组中。(2)求每个顶点的度：1.邻接矩阵存储结构下求每个顶点的度：利用图的邻接矩阵，
3、每个顶点所在行和所在列的边的权值如果存在则该顶点的度+1，依次算出每个顶点的度，并且记录在一个数组中输出。2.邻接表存储结构下求每个顶点的度：定义一个邻接边指针循环指向顶点的邻接边单链表头结点，当结点不空时，该顶点的出度+1,邻接边弧头结点的入度+1，依次求出每个顶点的出度和入度之和就为该顶点的度。(3)图的深度优先遍历：采取邻接矩阵结构，指定任意顶点x为初始顶点1.访问结点v并标记结点v已访问；2.查找结点v的第一个邻接结点w；3.若结点v的邻接结点w存在，则继续执行，否则算法结束；4.若结点w尚未被访问，则递归访问结点w；5.查找结点v的w邻接结点的下一个邻接结点w,转到步骤3。(4)图的
4、广度优先遍历：采取邻接矩阵结构，指定任意顶点x为初始顶点，利用顺序循环队列以保持访问过的结点的顺序1.首先访问初始结点v并标记结点v为已访问；2.结点v入队列；3.当队列非空时则继续执行，否则算法结束；4.出队列取得队头结点u；5.查找u的第一个邻接结点w；6.若u的邻接结点w不存在则转到步骤3，否则循环执行下列步骤：6.1若结点w尚未被访问，则访问结点w并标记结点w为已访问；6.2结点w入队列；6.3查找结点u的w邻接结点的下一个邻接结点w，转到步骤6 。(5)判断有向图的强连通性：采取邻接表结构，在图中寻找一个包含所有顶点且首尾相连的环，若这样的环存在，则该图为强连通图，否则不为强连通图。
5、(6)用邻接矩阵的信息生成邻接表：定义一个邻接表的边信息结构体，将邻接矩阵的边信息转换成邻接表的边信息存储到邻接边的单链表中。第二章 系统流程图main（）PrintCreatGraphMVerticesDepthFirstSearchCreatLGraphMDeleteBroadFirstSearchChaZhaoLianTongLVerticesInsertVertexInsertEdgeLInsertVertexLAdjInitiateDeleteVertenDeleteEdgeLInsertEdgeInitiate第3章 数据结构和算法(1)有向图顶点的数据类型DataType 定义如
6、下： typedef int DataType ；(2)邻接矩阵存储结构下图的结构体定义如下：typedef structSeqList Vertices； int edgeMaxVerticesMaxVertices；int numOfEdges； AdjMGraph； (3)邻接矩阵存储结构下图的边信息结构体定义如下：typedef structint row； int col； int weight； RowColWeight； (4)邻接表存储结构下图的结构体定义如下：typedef struct Node int dest； struct Node *next； Edge； type
7、def structDataType data； int sorce； Edge *adj； AdjLHeight； typedef structAdjLHeight aMaxVertices； int numOfVerts； int numOfEdges； AdjLGraph； (5)邻接表存储结构下图的边信息结构体定义如下：typedef structint row； int col； RowCol； (6)顺序循环队列的结构体定义如下：typedef struct DataType queueMaxQueueSize；int rear；int front；int count；SeqCQu
8、eue；(7)顺序表的结构体定义如下：typedef structDataType listMaxSize；int size；SeqList；第四章 核心代码分析源程序存放在八个文件夹中，文件SeqList.h是顺序表的结构体定义和操作函数，文件SeqCQueue.h是顺序循环队列的结构体定义和操作函数，文件AdjMGraph.h是邻接矩阵存储结构下图的结构体定义和操作函数，文件AdjMGraphCreate.h是邻接矩阵存储结构下图的创建函数，文件AdjLGraph.h是邻接表存储结构下图的结构体定义和操作函数，文件AdjLGraphCreate.h是邻接表存储结构下图的创建函数，文件Adj
9、MGraphTraverse.h是邻接矩阵存储结构下图的深度优先遍历和广度优先遍历操作函数，文件图的基本操作与实现.c是主函数。(1)/* 文件SeqList.h */typedef structDataType listMaxSize;int size;SeqList;void ListInitiate(SeqList *L)L-size=0;int ListLength(SeqList L)return L.size;int ListInsert(SeqList *L,int i,DataType x)int j;if(L-size=MaxSize)printf(数组已满无法插入！n);r
10、eturn 0;else if(iL-size)printf(参数不合法！n);return 0;elsefor(j=L-size;ji;i-)L-listj=L-listj-1;L-listi=x;L-size+;return 1;int ListDelete(SeqList *L,int i,DataType *x)int j;if(L-size=0)printf(顺序表已空无数据元素可删！n);return 0;else if(iL-size-1)printf(参数i不合法！n);return 0;else*x=L-listi;for(j=i+1;jsize-1;j+)L-listj-1
11、=L-listj;L-size-;return 1;int ListGet(SeqList L,int i,DataType *x)if(iL.size-1)printf(参数i不合法！n);return 0;else*x=L.listi;return 1;(2)/* 文件SeqCQueue.h */typedef struct DataType queueMaxQueueSize;int rear;int front;int count;SeqCQueue;void QueueInitiate(SeqCQueue *Q)Q-rear=0;Q-front =0;Q-count =0;int Q
12、ueueNotEmpty(SeqCQueue Q)if(Q.count !=0) return 1;else return 0;int QueueAppend(SeqCQueue *Q,DataType x)if(Q-count0&Q-rear=Q-front)printf(队列已满无法插入!);return 0;else Q-queue Q-rear=x;Q-rear =(Q-rear +1)%MaxQueueSize;Q-count +;return 1;int QueueDelete(SeqCQueue *Q,DataType *d)if(Q-count =0)printf(队列已空无数
13、据出队列!n);return 0;else*d=Q-queueQ-front; Q-front=(Q-front+1)%MaxQueueSize;Q-count -;return 1;int QueueGet(SeqCQueue Q,DataType*d)if(Q.count =0)printf(队列已空无数据出队列!n);return 0;else*d=Q.queue Q.front ;return 1;(3)/* 文件AdjMGraph.h*/#includeSeqList.htypedef structSeqList Vertices; /存放结点的顺序表int edgeMaxVerticesMaxVe
