数据结构课程设计报告书

1课程设计正文1.问题分析和任务定义1.1问题分析图的有关知识在很多领域有着广泛的应用，如电路分析、寻找最短路径、鉴定化合物等。在很多情况下是要在寻找两个顶点之间的最短路径。本课程设计是判断无向图中任意两个顶点之间是否存在一条长度为k的简单路径。1.2任务定义(1)采用邻接表作为存储结构(2)编写程序判断无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径。(3)测试用例自己设计2.开发平台WindowsXP，C++语言，VC++6.03.数据类型和系统定义3.1概要设计3.1.1抽象数据类型图的定义ADTGraphlnk{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={(v,w)|v,wV,(v,w)表示v和w之间存在路径}基本操作：NumberOfVertices()初始条件：图已存在。操作结果：返回图中的顶点数。NumberOfEdges()初始条件：图已存在。操作结果：返回图中的边数。getValue(inti)初始条件：图已存在。操作结果：返回图中第i(从0开始)号位置上的顶点。2getFirstNeighbor(intv)初始条件：图已存在，v是图中某个顶点。操作结果：返回v的第一个邻接顶点。getNextNeighbor(intv,intw)初始条件：图已存在，v和w是图中的两个顶点。操作结果：返回v的第一个邻接顶点w的下一个邻接顶点。getVertexPos(constTvertex)初始条件:图已存在，vertex与图中顶点具有相同的特征。操作结果：如图中存在顶点vertex，返回该顶点在图中的位置；否则返回-1。insertVertex(constT&vertex)初始条件：图已存在，vertex和图中顶点有相同的特征。操作结果：如果vertex不在图中，则插入；否则不插入。removeVertex(intv)初始条件：图已存在，v是图中某个顶点。操作结果：删除顶点v及与其关联的边。insertEdge(intv1,intv2)初始条件：图已存在，v和w是图中的两个顶点。操作结果：在图中插入边(v1,v2)。removeEdge(intv1,intv2)初始条件：图已存在，(v1,v2)是图中一条边。操作结果：删除图中的边(v1,v2)FineRoute(Tc1,Tc2,intk)初始条件：图已存在，c1，c2是图中两个顶点。操作结果：寻找c1,c2之间长度为k的简单路径，若找到，则返回1，并给出路径；否则，返回-1，并输出相关信息。friendistream&operator(istream&in,GraphlnkT&G);输入friendostream&operator(ostream&out,GraphlnkT&G);输出}ADTGraphlnk3.1.2主程序intmain(){输入顶点数和边数；输入顶点信息；输入边信息；输出图的顶点数，边数，顶点，边；寻找两顶点之间长度为k的简单路径；删除图中一个顶点；输出图的顶点数，边数，顶点，边；寻找两顶点之间长度为k的简单路径；往图中插入一条边；3输出图的顶点数，边数，顶点，边；寻找两顶点之间的路径；}3.2详细设计3.2.1存储结构本设计采用邻接表作为图中数据的存储结构，程序中使用指针定义一个顶点表*NodeTable，同时它也是每一条边链表的头结点，其data域中存放的是各顶点在图中的位置，其adj域中则存放的是指向第一条边结点的指针。边链表结点中dest域中存放的是与此顶点相关联的边的另一顶点位置，link域中存放的是与此顶点相关联的下一条边的指针。例如：3.2.2类的说明程序中需要的全程量constintDefaultSize=10;顶点类型templateclassT//模板structVertex//顶点的定义{Tdata;//顶点的名字EdgeT*adj;//边链表的投指针};边类型templateclassTstructEdge//边结点的定义{intdest;//边的另一顶点位置EdgeT*link;//下一条边链指针Edge(){}//构造函数Edge(intnum):dest(num),link(NULL){}//构造函数};4无向图类型templateclassTclassGraphlnk//图的类定义{public:Graphlnk(intsz=DefaultVertices);//构造函数~Graphlnk();//析构函数TgetValue(inti){return(i=0&&iNumVertices)?NodeTable[i].data:NULL;}//取位置为i的顶点中的值intNumberOfVertices(){returnNumVertices;}//返回图中的顶点数intNumberOfEdges(){returnNumEdges;}//返回图中的边数intgetFirstNeighbor(intv);//取顶点v的第一个邻接顶点intgetNextNeighbor(intv,intw);//取顶点v的第一个邻接顶点的下一个邻接顶点intgetVertexPos(constTvertex);//给出顶点v在图中的位置intFind(intv1,intv2,intk,intvisited[],intpath[],intd);//寻找路径boolinsertVertex(constT&vertex);//在图中插入一个顶点vertexboolremoveVertex(intv);//在图中删除一个顶点vboolinsertEdge(intv1,intv2);//在图中插入一条边(v1,v2)boolremoveEdge(intv1,intv2);//在图中删除一条边(v1,v2)voidFindRoute(Tc1,Tc2,intk);//在图中寻找顶点v1,v2之间长度为k的简单路径protected:intmaxVertices;//图中的最大顶点数intNumVertices;//图中的顶点数intNumEdges;//图中的边数private:VertexT*NodeTable;//顶点表friendistream&operator(istream&in,GraphlnkT&G);5//输入friendostream&operator(ostream&out,GraphlnkT&G);//输出};3.2.3主要函数的伪代码算法insertVertex(constT&vertex)//在图的顶点表中插入一个新顶点vertex。若插入成功，//函数返回true，否则返回false{if(表满)不能插入，返回false；for(inti=0;iNumVertices;i++)在图中寻找该顶点，如果已经存在，不能插入，返回false；图中无此顶点，将其插在顶点表的最后；图中顶点数加1;返回true;}removeVertex(intv)//在图中删除一个指定点v,v是顶点号。若删除成功，//函数返回true，否则返回false。{if(表空或顶点号超出范围)无法删除，返回falseEdgeT*p,*s,*t;intk;while(NodeTable[v].adj!=NULL){顶点v的邻接顶点k；找对称存放的边结点；删除对称存放的边结点；清除顶点v的边链表结点；与顶点v相关联的边数减1；}图中顶点个数减1；用图中最后一个顶点来填补被删顶点}insertEdge(intv1,intv2)//在图中插入一条边(v1,v2)，若此边存在或参数不合理，//函数返回false，否则函数返回true{if(顶点v1,v2都在图中){EdgeT*q,*p=NodeTable[v1].adj;6//v1对应的边链表头指针寻找邻接顶点v2；找到此边，不插入；否则创建新结点；链入v1边链表；链入v2边链表；}顶点v1或v2不在图中，无法插入边，返回false;}removeEdge(intv1,intv2){if(顶点v1,v2都在图中){EdgeT*p=NodeTable[v1].adj,*q=NULL,*s=p;在v1对应边链表中找被删边；找到被删边结点；{如果该结点是边链表首节点p指向p下一个节点；如果不是首结点，重新链接；删除结点p;}如果没有找到被删边结点，返回false；p=NodeTable[v2].adj;//v2对应边链表中删除找到被删边结点；{如果该结点是边链表首节点p指向p下一个节点；如果不是首结点，重新链接；删除结点p;}返回true;}结点v1或v2不在图中，返回false；}Find(intv1,intv2,intk,intvisited[],intpath[],intd)//寻找顶点v1和v2之间长度为k的简单路径{intnode,i;EdgeT*p;从顶点v1出发，并将visited[v1]标记为1，表示此顶点已经被问过；7走过的路径的条数d(从0开始)加1；记录下走过第d条路径时，经过的顶点；如果从顶点v1出发，走过k条路径到达顶点v2，函数返回1p=NodeTable[v1].adj;//顶点v1对应边链表的头指针while(p!=NULL){寻找此边的另一顶点；If(另一顶点没有被访问过)调用FindRoute函数递归寻找；与v1相关联的下一条边结点；}顶点回溯；边回溯；未找到，返回0；}getFirstNeighbor(intv)//给出顶点位置为v的第一个邻接顶点的位置，如果找不到，//则函数返回-1{if(顶点v存在){EdgeT*p=NodeTable[v].adj;//对应边链表第一个边结点如果第一个邻接顶点存在，返回其在图中的的位置；}顶点v或第一个邻接顶点不存在，返回-1；}getNextNeighbor(intv,intw)//给出顶点位置为v的邻接顶点w的下一个邻接顶点的位置，//如果没有下一个邻接顶点，则函数返回-1{if(顶点v存在1){EdgeT*p=NodeTable[v].adj,*q=NULL;//对应边链表第一个边结点寻找邻接顶点w;寻找顶点w对应边链表的第一个边结点；不为空返回顶点在图中的位置；}顶点v或下一个邻接顶点不存在，返回-1；}8istream&operator(istream&in,GraphlnkT&G)//输入{inti,j,k,n,m;Te1,e2;输入顶点数n和边数m；如果mn*(n-1)/2,给出出错信息，并要求用户重新输入；for(i=0;in;i++){输入顶点；if(此顶点已在图中)给出出错信息，并要求用户重新输入；将顶点插入图中；}while(im){输入边；if(顶点不在图中或者此边已在图中)给出出错信息，并要求用户重新输入；将边插入图中；}returnin;}ostream&operator(ostream&out,GraphlnkT&G)//输出{输出图中顶点数；输出图中边数；输出图中所有的顶点；输出图中所有的边；returnout;}3.2.4测试用例设计输入顶点数和边数：610输入顶点：ABCDEF输入边：ABACADAEAFBCBDEFDECE4.调试报告4.1遇到的问题及解决方案9(1)开始时，将getVertexPos()函数定义为Graphlnk类的私有函数，当Graphlnk类的对象G调用它时，编译出现如下错误：errorC2248:'getVertexPos':cannotaccessprivatememberdeclaredinclass'Graphlnkchar'。将getVertexPos()的访问权限改为公有后，不再出现此错误。这是因为类中定义的私有成员函数只能在类中使用，即使是该类的对象也不能访问该类的私有成员，包括数据成员和成员函数。(2)由于无向图采用邻接表作为其存储结构时，由于(Vi,Vj)与(Vj,Vi)是同一条边，在邻接表