《数据结构关键路径及十字链表基本操作课程设计报告》由会员分享，可在线阅读，更多相关《数据结构关键路径及十字链表基本操作课程设计报告（19页珍藏版）》请在金锄头文库上搜索。
1、-数据构造课程设计报告小组成员：王瑞琦 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 In
2、sertArc(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 Arodeint tailve*,headve*;/* 该弧的尾和头顶点的位置 */ struct Arode *hlink,*tlink;/* 分别为弧头一样和弧尾一样的弧的链域 */ InfoTyp
3、e info;/*假设为网络则为权值*/Arode;/*表头结点数据类型*/typedef struct Ve*NodeVerte* data; Arode *firstin,*firstout; /* 指向该顶点的第一条入弧和出弧 */Ve*Node;typedef Ve*Node AdjListMA*V;/*十字链表数据类型*/typedef struct AdjList adjlist; int n,e;/*图中顶点数n和边数e*/ALGraph;概要设计CreateDG(建表)1获取有向图的顶点数、弧数并存入；2依次获取各顶点的值，存入数组，构建十字链表头结点向量组；3依次获取弧信息，
4、存入，确认弧结点在十字链表中的位置并对弧赋值；4十字链表创立成功；LocateVe*(查找)传参：有向图，顶点利用指针依次扫描表头数组，当找到该顶点时，返回该顶点在十字链表表头数组的位置序号，未找到该顶点时，返回-1。Count(求度)传参：有向图，顶点调用LocateVe*()，找到顶点的位置，利用tlink指针依次扫描以该顶点为弧尾的边，统计该顶点的出度，利用hlink指针依次扫描以该顶点为弧头的边，统计该顶点的入度，则该顶点的度为入度加出度。InsertArc(插入边)传参：有向图，边调用LocateVe*()，找到顶点的位置，建立新的存储空间，对新存储空间赋值，通过修改tlink和hl
5、ink，将新结点放入十字链表。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;iadjlisti.firstin=NULL;G-adjli
6、sti.firstout=NULL;G-adjlisti.data=ve*i;for(k=0;kadjlisti.data !=edgek.vi) i+;j=0;while(G-adjlistj.data !=edgek.vj)j+; p=(Arode *)malloc(sizeof(Arode);p-headve*=i+1;/始边顶点(数组元素第一个序号为0)p-tailve*=j+1;/终边顶点p-info=edgek.info;/权值p-hlink=G-adjlisti.firstout;/建立弧头链表p-tlink=G-adjlistj.firstin;/建立弧尾链表G-adjlist
7、i.firstout=G-adjlistj.firstin=p;/头插/*查找指定顶点的位置序号*/int LocateVe*(ALGraph *G,Verte* u)int i;for(i=0;i(*G).n;i+)/循环查找结点if(*G).adjlisti.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(ktlink!=NU
8、LL)/依次扫描以该顶点为尾结点的弧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(i0|jtailve*=i;/给新结点赋值p-headve*=j;p-info=a.info;p-hlink=(*G).adjlistj.firstin;/插在入弧和出弧的链头p
9、-hlink=(*G).adjlisti.firstout;(*G).adjlistj.firstin=(*G).adjlisti.firstout=p;(*G).e+;/弧数+1return true;/*删除指定边*/bool DeletetArc(ALGraph *G,etype a)int i,j;Arode *p1,*p2;i=LocateVe*(G,a.vi);/弧尾序号j=LocateVe*(G,a.vj);/弧头序号if(i0|jheadve*=j)/第一个结点为待删除结点(*G).adjlisti.firstout=p2-tlink;elsewhile(p2&p2-headv
10、e*!=j)p1=p2;p2=p2-tlink;if(p2)/没到表尾p1-tlink=p2-tlink;p2=(*G).adjlistj.firstin;/将弧结点从入弧链表中删去if(p2&p2-tailve*=i)(*G).adjlistj.firstin=p2-hlink;elsewhile(p2&p2-tailve*!=i)p1=p2;p2=p2-hlink;if(p2)/没到表尾p1-hlink=p2-hlink;if(p2-info)/释放弧结点free(p2);(*G).e-;/弧数-1return true;调试分析及问题解决1、typedef struct OLGArc，定
11、义弧结点构造体，包含：两个整数类型的数据：tailve*、headve，q，分别为该弧的尾顶点、头顶点和该弧的权值；两个指针：*hlink、*tlink，分别为与该弧拥有一样头顶点的链域和与该弧拥有一样尾顶点的链域；2、typedef struct OLGVNode，定义顶点结点构造体，包含：一个字符类型的数据：data，为顶点的名字；两个指针：*firstin,*firstout，分别指向该顶点的第一条入弧和出弧；3、typedef struct ALGraph，定义十字链表构造体，包含：一个OLGVNode类型的数组，用于存放表头向量；两个整数类型的数据：ve*num、arum，分别为有向
12、图的当前顶点数和弧数；4、Status CreateDG(ALGraph *G)，创立十字链表的函数，实现创立空的十字链表，在十字链表中放入有向图的顶点、弧、权值等功能；5、void DestroyGraph(ALGraph *G)，销毁十字链表的函数，实现销毁用十字链表存储的有向图的功能；6、Verte*Type* GetVe*(ALGraph G,int v)，查找序号为v的顶点并返回该顶点的名字即该顶点的值；7、建表时为了统一代码，由另一人更改了建表的操作，导致建表时从1开场计数而不是0，后面的查找和删除功能有误；更改后正常。8、在插入指定边时，插入边将原有的边覆盖；在查找指定结点的度时
13、，获得的结果不正确，特别是在插入一条新边后的数据与原数据的差不为1。解决方法：通过调试查找，找到了错误来源：1、在创立十字链表时，数据的下标是从1开场存储的，而在查找指定结点的度、插入边、删除边等函数中均默认十字链表的存储下标是从0开场；2、在创立十字链表时，出现弧头和弧尾的定义与函数中的定义相反如以下图说明。于是进展如下修改：1、将创立十字链表函数中的下标改为从0开场存储；2、将查找指定结点的度、插入边、删除边等函数出现的弧头相关信息改为弧尾的，将弧尾相关信息改为弧头的。再次经过调试，证明程序正确。关键路径功能概述输入有向图，求其关键路径及最短时间。模块简介创立有向图邻接表；creatlin
