数据结构关键路径及十字链表基本操作课程设计报告.doc

数据构造课程设计报告小组成员：王瑞琦 13052007姜薇 13052021*倩 13052027小组课题： 1-1有向图十字链表的操作2-5 关键路径 . z.-有向图十字链表的操作功能概述将有向图以是十字链表的形式存储，并借助十字链表对有向图进展查找有向图中指定结点的度〔出度和入度〕、插入有向边和删除有向边等操作模块简介创立有向图十字链表：void creat_crosslink(ALGraph *&G,char ve*[],int n,etype edge[],int e)查找结点在十字链表中的位置：int LocateVe*(ALGraph *G,Verte* u) 插入指定边：bool InsertArc(ALGraph *G,etype a)删除指定边：bool DeletetArc(ALGraph *G,etype a)查找有向图中指定结点的度〔出度和入度〕：int Count(ALGraph *G,Verte* u)数据类型/*边的数据类型*/typedef struct{ char vi,vj; int info; }etype;/*弧结点数据类型*/typedef struct Arode{ int tailve*,headve*;/* 该弧的尾和头顶点的位置 */ struct Arode *hlink,*tlink;/* 分别为弧头一样和弧尾一样的弧的链域 */ InfoType info;/*假设为网络则为权值*/}Arode;/*表头结点数据类型*/typedef struct Ve*Node{ Verte* data; Arode *firstin,*firstout; /* 指向该顶点的第一条入弧和出弧 */}Ve*Node;typedef Ve*Node AdjList[MA*V];/*十字链表数据类型*/typedef struct{ AdjList adjlist; int n,e;/*图中顶点数n和边数e*/}ALGraph;概要设计CreateDG(建表)〔1〕获取有向图的顶点数、弧数并存入；〔2〕依次获取各顶点的值，存入数组，构建十字链表头结点向量组；〔3〕依次获取弧信息，存入，确认弧结点在十字链表中的位置并对弧赋值；〔4〕十字链表创立成功；LocateVe*(查找)传参：有向图，顶点利用指针依次扫描表头数组，当找到该顶点时，返回该顶点在十字链表表头数组的位置〔序号〕，未找到该顶点时，返回-1。

Count(求度)传参：有向图，顶点调用LocateVe*()，找到顶点的位置，利用tlink指针依次扫描以该顶点为弧尾的边，统计该顶点的出度，利用hlink指针依次扫描以该顶点为弧头的边，统计该顶点的入度，则该顶点的度为入度加出度InsertArc(插入边)传参：有向图，边调用LocateVe*()，找到顶点的位置，建立新的存储空间，对新存储空间赋值，通过修改tlink和hlink，将新结点放入十字链表bool DeletetArc(ALGraph *G,etype a)传参：有向图，边调用LocateVe*()，找到顶点的位置，通过修改指针，将指定的边结点从十字链表中删除，同时释放存储空间详细设计〔源代码〕/*建立十字链表*/void creat_crosslink(ALGraph *&G,char ve*[],int n,etype edge[],int e){ Arode *p; G=(ALGraph *)malloc(sizeof(ALGraph)); G->n=n;G->e=e; int k,i,j; for (i=0;iadjlist[i].firstin=NULL; G->adjlist[i].firstout=NULL; G->adjlist[i].data=ve*[i]; } for(k=0;kadjlist[i].data !=edge[k].vi) i++; j=0; while(G->adjlist[j].data !=edge[k].vj) j++; p=(Arode *)malloc(sizeof(Arode)); p->headve*=i+1;//始边顶点(数组元素第一个序号为0) p->tailve*=j+1;//终边顶点 p->info=edge[k].info;//权值 p->hlink=G->adjlist[i].firstout;//建立弧头链表 p->tlink=G->adjlist[j].firstin;//建立弧尾链表 G->adjlist[i].firstout=G->adjlist[j].firstin=p;//头插 }}/*查找指定顶点的位置〔序号〕*/int LocateVe*(ALGraph *G,Verte* u){ int i; for(i=0;i<(*G).n;i++)//循环查找结点 if((*G).adjlist[i].data==u) return i;//如果找到该结点就返回其在十字链表中的序号 return -1;//如果没有找到该结点，返回-1}/*求指定顶点的度*/int Count(ALGraph *G,Verte* u){ int i=0,j=0,k; Arode *p,*q; k=LocateVe*(G,u);//k是顶点v的序号 if(k<0)//k不是图G的顶点 return -1; p=(*G).adjlist[k].firstin;//找出弧 q=(*G).adjlist[k].firstout;//找入弧 while(p!=NULL && p->tlink!=NULL)//依次扫描以该顶点为尾结点的弧 { p=p->tlink; i++; } while(q!=NULL && q->hlink==NULL)//依次扫描以该顶点为头结点的弧 { q=q->hlink; j++; } return i+j;}/*插入新边*/bool InsertArc(ALGraph *G,etype a){ int i,j; Arode *p; i=LocateVe*(G,a.vi);//弧尾序号 j=LocateVe*(G,a.vj);//弧头序号 if(i<0||j<0) return false; p=(Arode *)malloc(sizeof(etype));//生成新结点 p->tailve*=i;//给新结点赋值 p->headve*=j; p->info=a.info; p->hlink=(*G).adjlist[j].firstin;//插在入弧和出弧的链头 p->hlink=(*G).adjlist[i].firstout; (*G).adjlist[j].firstin=(*G).adjlist[i].firstout=p; (*G).e++;//弧数+1 return true;}/*删除指定边*/bool DeletetArc(ALGraph *G,etype a){ int i,j; Arode *p1,*p2; i=LocateVe*(G,a.vi);//弧尾序号 j=LocateVe*(G,a.vj);//弧头序号 if(i<0||j<0||i==j) return false; p2=(*G).adjlist[i].firstout;//将弧结点从出弧表中删去if(p2&&p2->headve*==j)//第一个结点为待删除结点 (*G).adjlist[i].firstout=p2->tlink; else { while(p2&&p2->headve*!=j) { p1=p2; p2=p2->tlink; } if(p2)//没到表尾 p1->tlink=p2->tlink; } p2=(*G).adjlist[j].firstin;//将弧结点从入弧链表中删去 if(p2&&p2->tailve*==i) (*G).adjlist[j].firstin=p2->hlink; else { while(p2&&p2->tailve*!=i) { p1=p2; p2=p2->hlink; } if(p2)//没到表尾 p1->hlink=p2->hlink; } if(p2->info)//释放弧结点 free(p2); (*G).e--;//弧数-1 return true;}调试分析及问题解决1、typedef struct OLGArc，定义弧结点构造体，包含：两个整数类型的数据：tailve*、headve，q，分别为该弧的尾顶点、头顶点和该弧的权值；两个指针：*hlink、*tlink，分别为与该弧拥有一样头顶点的链域和与该弧拥有一样尾顶点的链域；2、typedef struct OLGVNode，定义顶点结点构造体，包含：一个字符类型的数据：data，为顶点的名字；两个指针：*firstin,*firstout，分别指向该顶点的第一条入弧和出弧；3、typedef struct ALGraph，定义十字链表构造体，包含：一个OLGVNode类型的数组，用于存放表头向量；两个整数类型的数据：ve*num、arum，分别为有向图的当前顶点数和弧数；4、Status CreateDG(ALGraph *G)，创立十字链表的函数，实现创立空的十字链表，在十字链表中放入有向图的顶点、弧、权值等功能；5、void DestroyGraph(ALGraph *G)，销毁十字链表的函数，实现销毁用十字链表存储的有向图的功能；6、Verte*Type* GetVe*(ALGraph G,int v)，查找序号为v的顶点并返回该顶点的名字〔即该顶点的值〕；7、建表时为了统一代码，由另一人更改了建表的操作，导致建表时从1开场计数而不是0，后面的查找和删除功能有误；更改后正常。

8、在插入指定边时，插入边将原有的边覆盖；在查找指定结点的度时，获得的结果不正确，特别是在插入一条新边后的数据与原数据的差不为1解决方法：通过调试查找，找到了错误来源：1、在创立十字链表时，数据的下标是从1开场存储的，而在"查找指定结点的度〞、"插入边〞、"删除边〞等函数中均默认十字链表的存储下标是从0开场；2、在创立十字链表时，出现弧头和弧尾的定义与函数中的定义相反〔如以下图说明〕于是进展如下修改：1、将创立十字链表函数中的下标改为从0开场存储；2、将"查找指定结点的度〞、"插入边〞、"删除边〞等函数出现的弧头相关信息改为弧尾的，将弧尾相关信息改为弧头的再次经过调试，证明程序正确关键路径功能概述输入有向图，求其关键路径及最短时间模块简介创立有向图邻接表；creatlin。