《数据结构关键路径及十字链表基本操作课程设计报告》由会员分享，可在线阅读，更多相关《数据结构关键路径及十字链表基本操作课程设计报告（17页珍藏版）》请在金锄头文库上搜索。
1、数据结构2015寒假课程设计报告数据结构课程设计报告 小组成员：王瑞琦 13052007姜薇 13052011刘倩 13052027小组课题： 1-1有向图十字链表的操作2-5 关键路径 17有向图十字链表的操作功能概述将有向图以是十字链表的形式存储，并借助十字链表对有向图进行查找有向图中指定结点的度（出度和入度）、插入有向边和删除有向边等操作。模块简介创建有向图十字链表：void creat_crosslink(ALGraph *&G,char vex,int n,etype edge,int e)查找结点在十字链表中的位置：int LocateVex(ALGraph *G,Vertex u
2、) 插入指定边：bool InsertArc(ALGraph *G,etype a)删除指定边：bool DeletetArc(ALGraph *G,etype a)查找有向图中指定结点的度（出度和入度）：int Count(ALGraph *G,Vertex u)数据类型/*边的数据类型*/typedef struct char vi,vj; int info; etype;/*弧结点数据类型*/typedef struct ArcNodeint tailvex,headvex;/* 该弧的尾和头顶点的位置 */ struct ArcNode *hlink,*tlink;/* 分别为弧头相同
3、和弧尾相同的弧的链域 */ InfoType info;/*若为网络则为权值*/ArcNode;/*表头结点数据类型*/typedef struct VexNodeVertex data; ArcNode *firstin,*firstout; /* 指向该顶点的第一条入弧和出弧 */VexNode;typedef VexNode AdjListMAXV;/*十字链表数据类型*/typedef struct AdjList adjlist; int n,e;/*图中顶点数n和边数e*/ALGraph;概要设计CreateDG(建表)（1）获取有向图的顶点数、弧数并存入；（2）依次获取各顶点的值
4、，存入数组，构建十字链表头结点向量组；（3）依次获取弧信息，存入，确认弧结点在十字链表中的位置并对弧赋值；（4）十字链表创建成功；LocateVex(查找)传参：有向图，顶点利用指针依次扫描表头数组，当找到该顶点时，返回该顶点在十字链表表头数组的位置（序号），未找到该顶点时，返回-1。Count(求度)传参：有向图，顶点调用LocateVex()，找到顶点的位置，利用tlink指针依次扫描以该顶点为弧尾的边，统计该顶点的出度，利用hlink指针依次扫描以该顶点为弧头的边，统计该顶点的入度，那么该顶点的度为入度加出度。InsertArc(插入边)传参：有向图，边调用LocateVex()，找到顶
5、点的位置，建立新的存储空间，对新存储空间赋值，通过修改tlink和hlink，将新结点放入十字链表。bool DeletetArc(ALGraph *G,etype a)传参：有向图，边调用LocateVex()，找到顶点的位置，通过修改指针，将指定的边结点从十字链表中删除，同时释放存储空间。详细设计（源代码）/*建立十字链表*/void creat_crosslink(ALGraph *&G,char vex,int n,etype edge,int e)ArcNode *p;G=(ALGraph *)malloc(sizeof(ALGraph);G-n=n;G-e=e;int k,i,j;
6、for (i=0;iadjlisti.firstin=NULL;G-adjlisti.firstout=NULL;G-adjlisti.data=vexi;for(k=0;kadjlisti.data !=edgek.vi) i+;j=0;while(G-adjlistj.data !=edgek.vj)j+; p=(ArcNode *)malloc(sizeof(ArcNode);p-headvex=i+1;/始边顶点(数组元素第一个序号为0)p-tailvex=j+1;/终边顶点p-info=edgek.info;/权值p-hlink=G-adjlisti.firstout;/建立弧头链表
7、p-tlink=G-adjlistj.firstin;/建立弧尾链表G-adjlisti.firstout=G-adjlistj.firstin=p;/头插/*查找指定顶点的位置（序号）*/int LocateVex(ALGraph *G,Vertex u)int i;for(i=0;i(*G).n;i+)/循环查找结点if(*G).adjlisti.data=u)return i;/如果找到该结点就返回其在十字链表中的序号return -1;/如果没有找到该结点，返回-1/*求指定顶点的度*/int Count(ALGraph *G,Vertex u)int i=0,j=0,k;ArcNod
8、e *p,*q;k=LocateVex(G,u);/k是顶点v的序号if(ktlink!=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;ArcNode *p;i=LocateVex(G,a.vi);/弧尾序号j=LocateVex(G,a.vj);/弧头序号if(i0|jtailvex=i;/给新结点赋值p-headvex=j;p-info=
9、a.info;p-hlink=(*G).adjlistj.firstin;/插在入弧和出弧的链头p-hlink=(*G).adjlisti.firstout;(*G).adjlistj.firstin=(*G).adjlisti.firstout=p;(*G).e+;/弧数+1return true;/*删除指定边*/bool DeletetArc(ALGraph *G,etype a)int i,j;ArcNode *p1,*p2;i=LocateVex(G,a.vi);/弧尾序号j=LocateVex(G,a.vj);/弧头序号if(i0|jheadvex=j)/第一个结点为待删除结点(*
10、G).adjlisti.firstout=p2-tlink;elsewhile(p2&p2-headvex!=j)p1=p2;p2=p2-tlink;if(p2)/没到表尾p1-tlink=p2-tlink;p2=(*G).adjlistj.firstin;/将弧结点从入弧链表中删去if(p2&p2-tailvex=i)(*G).adjlistj.firstin=p2-hlink;elsewhile(p2&p2-tailvex!=i)p1=p2;p2=p2-hlink;if(p2)/没到表尾p1-hlink=p2-hlink;if(p2-info)/释放弧结点free(p2);(*G).e-;
11、/弧数-1return true;调试分析及问题解决1、typedef struct OLGArc，定义弧结点结构体，包含：两个整数类型的数据：tailvex、headve，q，分别为该弧的尾顶点、头顶点和该弧的权值；两个指针：*hlink、*tlink，分别为与该弧拥有相同头顶点的链域和与该弧拥有相同尾顶点的链域；2、typedef struct OLGVNode，定义顶点结点结构体，包含：一个字符类型的数据：data，为顶点的名字；两个指针：*firstin,*firstout，分别指向该顶点的第一条入弧和出弧；3、typedef struct ALGraph，定义十字链表结构体，包含：一
12、个OLGVNode类型的数组，用于存放表头向量；两个整数类型的数据：vexnum、arcnum，分别为有向图的当前顶点数和弧数；4、Status CreateDG(ALGraph *G)，创建十字链表的函数，实现创建空的十字链表，在十字链表中放入有向图的顶点、弧、权值等功能；5、void DestroyGraph(ALGraph *G)，销毁十字链表的函数，实现销毁用十字链表存储的有向图的功能；6、VertexType* GetVex(ALGraph G,int v)，查找序号为v的顶点并返回该顶点的名字（即该顶点的值）；7、建表时为了统一代码，由另一人更改了建表的操作，导致建表时从1开始计数而不是0，后面的查找和删除功能有误；更改后正常。8、在插入指定边时，插入边将原有的边覆盖；在查找指定结点的度时，获得的结果不正确，特别是在插入一条新边后的数据与原数据的差不为1。解决办法：通过调试查找，找到了错误来源：1、在创建十字链表时，数据的下标是从1开始存储的，而在“查找指定结点的度”、“插入边”、“删除边”等函数中均默认十字链表的存储下标是从0开始；2、在创建十字链表时，出现弧头和弧尾的定义与函数中的定义相反（如下图说明）。于是进行如下修改：1、将创建十字链表函数中的下标改为从0开始存储；2、将“查找指定结点的度”、“插入边”、“删除边”等函数出现的弧头相关信息改为弧尾的，将弧尾相关
