小组成员：小组课题： 数据结构课程设计报告
王瑞琦 13052007
姜薇 13052011
刘倩 13052027
1-1有向图十字链表的操作
2-5 关键路径
有向图十字链表的操作
功能概述
将有向图以是十字链表的形式存储，并借助十字链表对有向图进行查找有向图中指定结点的度（出度和入度）、插入有向边和删除有向边等操作。
模块简介
创建有向图十字链表：void creat_crosslink(ALGraph *&G,char vex[],int n,etype edge[],int e)
查找结点在十字链表中的位置：int LocateVex(ALGraph *G,Vertex u) 插入指定边：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 ArcNode
{ int tailvex,headvex;/* 该弧的尾和头顶点的位置 */
struct ArcNode *hlink,*tlink;/* 分别为弧头相同和弧尾相同的弧的链域 */ InfoType info;/*若为网络则为权值*/
}ArcNode;
/*表头结点数据类型*/
typedef struct VexNode { Vertex data;
ArcNode *firstin,*firstout; /* 指向该顶点的第一条入弧和出弧 */ }VexNode;
typedef VexNode AdjList[MAXV];
/*十字链表数据类型*/
typedef struct { AdjList adjlist;
int n,e;/*图中顶点数n和边数e*/ }ALGraph;
概要设计
CreateDG(建表)
（1）获取有向图的顶点数、弧数并存入；
（2）依次获取各顶点的值，存入数组，构建十字链表头结点向量组； （3）依次获取弧信息，存入，确认弧结点在十字链表中的位置并对弧赋值； （4）十字链表创建成功；
LocateVex(查找) 传参：有向图，顶点
利用指针依次扫描表头数组，当找到该顶点时，返回该顶点在十字链表表头数组的位置（序号），未找到该顶点时，返回-1。
Count(求度) 传参：有向图，顶点
调用LocateVex()，找到顶点的位置，利用tlink指针依次扫描以该顶点为弧尾的边，统计该顶点的出度，利用hlink指针依次扫描以该顶点为弧头的边，统计该顶点的入度，那么该顶点的度为入度加出度。
InsertArc(插入边) 传参：有向图，边
调用LocateVex()，找到顶点的位置，建立新的存储空间，对新存储空间赋值，通过修改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; for (i=0;i } while(G->adjlist[i].data !=edge[k].vi) i++; j=0; while(G->adjlist[j].data !=edge[k].vj) j++; p=(ArcNode *)malloc(sizeof(ArcNode)); p->headvex=i+1;//始边顶点(数组元素第一个序号为0) p->tailvex=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 LocateVex(ALGraph *G,Vertex 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,Vertex u) { int i=0,j=0,k; ArcNode *p,*q; k=LocateVex(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; ArcNode *p; i=LocateVex(G,a.vi);//弧尾序号 j=LocateVex(G,a.vj);//弧头序号 if(i<0||j<0) return false; p=(ArcNode *)malloc(sizeof(etype));//生成新结点 p->tailvex=i;//给新结点赋值 p->headvex=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; ArcNode *p1,*p2; i=LocateVex(G,a.vi);//弧尾序号 j=LocateVex(G,a.vj);//弧头序号 if(i<0||j<0||i==j) return false; p2=(*G).adjlist[i].firstout;//将弧结点从出弧表中删去 if(p2&&p2->headvex==j)//第一个结点为待删除结点 (*G).adjlist[i].firstout=p2->tlink; else { while(p2&&p2->headvex!=j) { p1=p2; p2=p2->tlink; } if(p2)//没到表尾 p1->tlink=p2->tlink; } p2=(*G).adjlist[j].firstin;//将弧结点从入弧链表中删去 if(p2&&p2->tailvex==i) } (*G).adjlist[j].firstin=p2->hlink; else { while(p2&&p2->tailvex!=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，定义弧结点结构体，包含：两个整数类型的数据：tailvex、headve，q，分别为该弧的尾顶点、头顶点和该弧的权值；两个指针：*hlink、*tlink，分别为与该弧拥有相同头顶点的链域和与该弧拥有相同尾顶点的链域； 2、typedef struct OLGVNode，定义顶点结点结构体，包含：一个字符类型的数据：data，为顶点的名字；两个指针：*firstin,*firstout，分别指向该顶点的第一条入弧和出弧； 3、typedef struct ALGraph，定义十字链表结构体，包含：一个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、将“查找指定结点的度”、“插入边”、“删除边”等函数出现的弧头相关信息改为弧尾的，将弧尾相关信息改为弧头的。 再次经过调试，证明程序正确。 关键路径 功能概述 输入有向图，求其关键路径及最短时间。 模块简介 创建有向图邻接表；creatlink(ALGraph *&G,char vex[],int n,etype edge[],int e) 输入有向图邻接表；Inputgraph(ALGraph *&G) 获取事件发生最早时间；int get_ve(ALGraph *G,int i,VNode q) 获取时间发生最迟时间；int get_vl(ALGraph *G,int i,VNode q) 对有向图进行拓扑排序；TopSort(ALGraph *&G) 求关键活动及最短时间。get_keyroad(ALGraph *G) 数据类型 /*边的数据类型*/ typedef struct { char vi,vj; int info; }etype; /*边结点数据类型*/ typedef struct ANode { int adjvex; /*邻接点存储序号*/ int lt;/*活动最迟发生时间*/ int flag;/*标记是否为关键活动*/ InfoType info; /*若是网络存储权值*/ struct ANode *nextarc; /*指向下一个边结点*/ }ArcNode; /*表头结点数据类型*/ typedef struct { Vertex data; /*存储顶点元素*/ int count;/*顶点入度*/ int ve,vl;/*事件最早及最迟发生时间*/ ArcNode *firstarc; /*指向依附于该顶点的第一边*/ }VNode; typedef VNode AdjList[MAXV]; /*邻接表数据类型*/ typedef struct { AdjList adjlist; int n,e;/*图中顶点数n和边数e*/ }ALGraph; 概要设计 Creatlink（建表）此函数用于调试后面的功能 传参：空表，顶点，顶点个数，边数，有向边信息 邻接表为链式存储，传参使用的数组则为顺序存储。 步骤为：1.将顶点信息(char vex[])放入表头结点(G->adjlist[i].data)；2.将有向边信息(etype edge[])填入表中作为边结点。 为了方便调试采用尾插法，后期可能会改成头插。 Inputgraph(输入图)此函数为正式建表 传参：空的有向图 步骤为：先输入顶点数和边数，确定邻接表大小后再进行边信息的录入。输入顶点信息，建立邻接表头->输入边信息，将边信息填入表中作为边结点。 为了便于调试采用尾插法。 TopSort（拓扑排序） 传参：有向图（以邻接表方式存储） 步骤为：利用栈存储入度为零的顶点，逐一输出，再删去其作为始点出发的边得出下一个入度为零的点，输出，重复上述步骤，即得拓扑排序序列。 一边进行拓扑排序的同时一边调用get_ve(图,头结点序号,头结点)函数获得每个事件发生的最早时间，同时将序列存入一个栈St1以便后面获得拓扑排序逆序列。 由于St1属于本函数中的局部变量，因此get_vl函数放在本函数里，对St1进行出栈操作，获取拓扑排序逆序列并求算事件最迟发生时间。 get_keyroad（关键路径及最短时间） 传参：有向图（以邻接表方式存储） 遍历有向图，利用公式 活动最迟发生时间=终点事件最迟发生时间-活动持续时间 活动最早发生时间=起点事件最早发生时间 求出关键活动，以此获得关键路径及最短时间。 详细设计（源代码） /*建立邻接表*/ void creatlink(ALGraph *&G,char vex[],int n,etype edge[],int e) { ArcNode *p,*t; t=(ArcNode *)malloc(sizeof(ArcNode)); t->nextarc=NULL; G=(ALGraph *)malloc(sizeof(ALGraph)); G->n=n;G->e=e; } int k,i,j; for (i=0;i for(k=0;k p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=j;//终边顶点 p->info=edge[k].info;//权值 p->flag=0;//默认为非关键活动 if(G->adjlist[i].firstarc==NULL)//尾插 { G->adjlist[i].firstarc=p; p->nextarc=NULL; t=p; } else { t->nextarc=p; p->nextarc=NULL; t=p; } } /*输入邻接表*/ void Inputgraph(ALGraph *&G) { char e[2]; int l,i,j,k=0;//l:边长 ArcNode *p,*t; t=(ArcNode *)malloc(sizeof(ArcNode)); t->nextarc=NULL; G=(ALGraph *)malloc(sizeof(ALGraph)); printf(\先输入顶点数和边数 } scanf(\ for (i=0;i while(k { printf(\ scanf(\ scanf(\ i=0; while(G->adjlist[i].data !=e[0]) i++; j=0; while(G->adjlist[j].data !=e[1]) j++; p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=j;//终边顶点 p->info=l;//权值 p->flag=0;//默认为非关键活动 if(G->adjlist[i].firstarc==NULL)//尾插 { G->adjlist[i].firstarc=p; p->nextarc=NULL; t=p; } else { t->nextarc=p; p->nextarc=NULL; t=p; } k++; } /*获取事件发生最早时间*/ int get_ve(ALGraph *G,int i,VNode q) { int j=0; ArcNode *p; if(i==0) return 0; else { while(j if(p==NULL) { j++; continue; } while(p->nextarc!=NULL && p->adjvex!=i) p=p->nextarc; if(p->adjvex==i&& p->info+G->adjlist[j].ve>=G->adjlist[i].ve) { G->adjlist[i].ve=p->info+G->adjlist[j].ve; j++; } else j++; } return G->adjlist[i].ve; } } /*获取事件发生最迟时间*/ int get_vl(ALGraph *G,int i,VNode q) { ArcNode *p; p=G->adjlist[i].firstarc; if(i==0) return 0; G->adjlist[i].vl=G->adjlist[p->adjvex].vl-p->info;//出度为0的顶点只有一个且已出栈，此处无需判断p！=NULL while(p->nextarc!=NULL) { p=p->nextarc; if(G->adjlist[i].vl>=G->adjlist[p->adjvex].vl-p->info) G->adjlist[i].vl=G->adjlist[p->adjvex].vl-p->info; } } return G->adjlist[i].vl; /*拓扑排序*/ void TopSort(ALGraph *G) { int i,j; int St[MAXV],top=-1; ArcNode *p; for(i=0;i } p=p->nextarc; } } for(i=0;i /*进行拓扑排序并将结果逐个输出*/ while(top>-1)//栈不为空时进行循环 { i=St[top];top--; printf(\ p=G->adjlist[i].firstarc; while(p!=NULL) { j=p->adjvex; G->adjlist[j].count--; if(G->adjlist[j].count==0) { top++; St[top]=j; } p=p->nextarc; } } /*关键路径及最短时间*/ void get_keyroad(ALGraph *G) { int i=0, stime=0; ArcNode *p; printf(\ while(i { p->lt=G->adjlist[p->adjvex].vl-p->info; if(p->lt-G->adjlist[i].ve==0) { p->flag=1;//该活动为关键活动 printf(\ stime=stime+p->info;//最短时间 } p=p->nextarc; } i++; } printf(\ } 调试分析 建表时间复杂度与O(n)同阶，拓扑排序时间复杂度与O(n)同阶，关键路径时间复杂度与O(n)同阶。由于为了调试方便，没有实现图形输入这个函数。 所 用 测 试 数 据 如 下 ： etype edge[]={{'a','b',6}, {'a','c',4}, {'a','d',5},{'b','e',1},{'c','e',1},{'d','f',3},{'e','g',9},{'e','h',5},{'f','h',2},{'g','m',2},{'h','m',4}}; 问题解决 1. 建表时由于采用尾插，需要始终保留一个指针指向最后一个结点，且该指针的下一个出度边位置应设为空，但起初编程时没有考虑到这点，导致出现程序占用不合法内存的错误出现，后修改。 2. 建表初期使用scanf进行输入，调试时总出错，因为scanf将回车键默认为输入的结束，如果用“%c”的方法去输入顶点信息，会导致只输出一半顶点的情况发生，因此在%c后添加空格，才可将全部信息录入邻接表。 3. 调试时出现一个问题，由于scanf是输入边信息，但经过调试跟踪发现输入的信息与跟踪的信息不符，可能因为输入之后计算机将其转为ASCII码上对应的数值因而出现此状况。 4. 起初对于关键路径不了解，认为是最迟发生时间-最短发生时间=0的事件（顶点）构成的，后来得知是求宽裕时间为0的活动（即边），通过边找顶点。所以开始认为是调试数据不好，修改调试数据为书上所给。 课程设计总结 姜薇： 首先对主要负责的“有向图的十字链表存储及相关操作”，进行总结，有向图因为每个顶点均有可能有入弧和出弧，有时还要处理权值，以十字链表的方式进行存储恰好能够满足能同时处理一个顶点的入弧、出弧和权值，扫描、操作时通过移动指针实现，操作便捷，但需要注意的是条件的设置。而另一个涉及工程问题的作业，重点则在于求解过程中的算法。 课程设计可以说完成的很不顺利，两个程序都是关于有向图和链表的。从我个人的角度看，链表（无论是十字链表还是邻接表）都是相对于其他结构较有难度的，而图的操作往往是牵一发而动全身，所以将二者结合起来的两个程序更是难度更甚了。由于老师上课提及过此题的解法，故而认为题目并不很难，于是轻视了此题，但看别人讲解，如同看书上例题一样，看的再多也不过是如纸上谈兵。“纸上得来终觉浅，绝知此事要躬行”，工科是实践性极强的，凡是从书上得来的知识，均要一一实践过才能当做自己的收入囊中。 从期末考试前完成开题报告起，经过了期末考试周、考试结束后留校的那几天、漫长的回家旅途、回家后的同学聚会，才开始想起我们的课程设计。由于长时间的放松，精神状态已经很松懈了，以至于平时很轻易想清楚的问题想了很久才能找到答案，于是“有向图的十字链表存储及相关操作”一个程序就已经费时颇久。其实，这不过是人人都有的拖延和惰性在作怪，只是我再一次的被它们击败了。与其说课程设计是一种提升或测试，倒不如说是给我的一个提醒，事事的成功与否都必须建立在是否尽心尽力上。人的主观能动性并不是万能的，也就是 说每个人的能力都是有限的，我们事事尽心都尚且不能做到事事顺心，更何况不尽心尽力呢？不计前嫌，只要求自己日后不再重复昨日之失，勤与付思想于实践。 刘倩： 通过这次的数据结构的课程设计，让我对编程语言以及VC6.0的软件都有了一定的熟悉。首先，我们组所选的课题是“有向图十字链表的操作和关键路径”两个题目。两道题都与数据结构课程中“图”的内容有关，在查阅了图，以及十字链表的相关知识后我们才开始对程序的初步规划，要如何以十字链表的形式来存储图，并可以进行“插入边，删除边”等操作；存储图形，并进行最短时间和关键路径的计算。经过这一系列的查找和预先构想，不但对于这部分知识加强了巩固，更从中发现了许多以前没有掌握的东西。让我对这一部分的知识有了更深一步的认识。 在编写程序的过程中，由于我个人的原因，遇到了不少的麻烦。比如图和十字链表要怎样建立联系等等问题。还有一些程序语句的使用错误，逻辑错误。这些所有的问题，都是在组内其他成员的帮助下解决的。并且这次的课程设计是以小组的形式完成的，在这过程中，我们一起讨论，一起研究思路，一起解决问题，互帮互助，配合默契，也培养出了我们的团队精神。这也是在这次课程设计中，除了知识方面收获最大的东西了。 本次课程设计花费了一个多月的时间，在这段时间里，无论是专业方面的，还是学习技巧方面的，我都学到了很多东西。也让我进一步明白了“数据结构”的重要性。“数据结构”教授的很多东西，都是可以串联在一起，用到一个程序中去的，使得运行更加方便，也使程序更简洁易懂。所以，“数据结构”是非常重要的一门课程，要熟练掌握其中每一部分的知识，学会把所有知识贯穿到一起， 灵活使用。 王瑞琦： 此次课程设计我负责的部分主要是2-5关键活动的代码。做这题之前我对于关键路径的认识仅限于老师的ppt，而且理解有误。我以为关键路径是简单的最长路径，之后才了解到关键路径是要依靠每个活动的富余时间找出关键活动才能得到，因此在之前的开题报告表中我并没有列出关于活动最早发生时间和最迟发生时间的函数。这是我先学到的内容，但也是我认为最难的一步。我以为自己在课上学的都会了，后来发现我根本不知道什么是关键路径，所以最初设计程序结构时我发现根据我设计的那些函数无法求解关键路径。所以我在做这道题时有很长时间花在了关键路径如何求解的学习上。 在帮助同学调试的过程中我发现同学和我有一样的常犯错误，判断条件里忽略了指针域为空的情况，因为链表操作数据间关系依赖指针实现，所以指针域为空时再利用它去进行判断就会出错，而且不是error类型的报错，是非法占用了空间的错误，运行时才会弹出。这点我想以后我会有更深刻的认识，写判断条件时也会注意很多。 最后修改关键路径程序的输入图形函数时我重新复习了C语言里字符和字符串的使用，我试过用puts函数代替scanf，发现根本运行不了，查书才知道puts函数是输出函数，相当于printf，gets函数可以用于输入，但必须是定义一个确定长度的字符串。这些函数的使用我在调试程序时有了更深刻的学习。 通过此次学习，我对数据结构这门课有了一个新的认识。在学习这门课时我知道我们这门课都是围绕着绪论里说的数据的存储方式和逻辑关系进行的，先是线性存储，链式存储，之后是书，图，学的都是数据结构。这次的课程设计我有 种强烈的感觉，数据结构是程序的工具，算法+数据结构=程序，这是我深有体会的一点。比如栈和队列的使用，在我知道需要知道拓扑排序逆序列时第一个想到的是栈，这时我就很强烈地认为数据结构就是一门工具，为我们写程序提供各类数据存储方式。 我认为随着我学的专业课增加，写得代码量再多些，我就会对数据结构这门课有更多的认识和感悟。 [此文档可自行编辑修改，如有侵权请告知删除，感谢您的支持，我们会努力把内容做得更好]
数据结构关键路径及十字链表基本操作课程设计报告
