数据结构之图C源代码
玩转算法与数据结构之图
—HIT2000鲁天伟
图在数据结构中比前面的链表和二叉树要复杂一些，复杂在无固定的造型。比如让大家画一个链表，画一个二叉树，大家应该画的差不多一个样子。但是图就不行，让大家画个图可能就千差万别了，我们数据结构里面常用的图是由顶点和边构成的图。有长度的边叫加权边。由加权边构成的图叫带权图。研究的无向图基本上都是连通图（图中任意两个顶点之间都连通，即任两点间都有一条通路连接）。所研究的有向图，也是在无向图的基础上，在每条边上加上指示方向的箭头，并能够从图（有向图按无向图使用算法）中从任一个顶点开始进行先深搜索（DFS）算法或是先广搜索（BFS）算法遍历找到所有顶点。关于图中度的概念，简单来说，无向图顶点的度是指该顶点连接几条边，连几条边，就是几度，无向图中所有顶点的总度数是边数的两倍。有向图顶点的度分入度和出度，入度是指向该顶点的边总和，出度是以该点为起点指向其他顶点的边总和。无向图的应用主要是在连通图中寻找任意顶点到其它顶点间的最短路径，用最小代价连通各个顶点的最小生成树。有向图的应用主要在工程方面，使用AOV（顶点表示活动）网和AOE（边表示活动）网。AOV网用来表示活动的先后顺序，可用拓扑排序来找出活动的先后顺序。AOE网用来找出关键路径（从起始点到终止点最长的一条路径）。AOV和AOE网都是无环有向图。
图表 1 无向图
图表 2 有向图
如上图1表示无向图，这个无向图的边没有标明长度，只有邻接关系。可以用邻接矩阵来表示，即用一个二维的数组存放顶点间的关系（表示两顶点是否有线连接）。邻接矩阵既可以存无向图的顶点关系也可以存有向图的顶点关系。边没有长度时，在二维数组邻接两点对应的坐标位置填1表示有邻接，不邻接的两点确定的坐标位置填0表示不邻接。如果边有长度设定，可以在坐标位写入加权边的长度值。
图表 3 邻接矩阵
如上左图是图1的邻接矩阵。右图是图2的邻接矩阵。
那么对于有向图，我们还可以用邻接表来存储。即可以用一个一维的地址数组来存放各顶点指向其它顶点构成的链表的头结点地址。
struct list{ /*定义链表结点结构体*/
int data; /*顶点的序号*/
struct list * next; /*指向下一个结点的指针*/
};
typedef struct list listNode;
typedef listNode * link;
link graph[6]; /*有向图的邻接表统计顶点出度*/
link reversegraph[6]; /*有向图的逆邻接表统计顶点入度*/
图表 4 邻接表
如上图4是邻接表，比如0指向的顶点是1和4，那么就把1和4形成链表，把头结
点的地址存入指针数组的0号位置。由此可以方便的找出0指向的顶点，同时也可以统计出0的出度是2。同理，我们可以再作一个逆邻接表，统计出指向顶点的边数，用来统计顶点的入度。
图表 5 逆邻接表
如上图5就是逆邻接表，以4为例，有0,1,2,3四个顶点指向4,所以4的出度是4。图中的8位数字是结点地址。那么我们尝试着把邻接表和逆邻接表合二为一，于是有了下面的这种十字链表。
struct EdgeList{ /*十字链表边结点结构体*/
int source; /*起点值*/
int destination; /*终点值*/
struct EdgeList * sourcenext; /*起点索引链表指针*/
struct EdgeList * destinationnext; /*终点索引链表指针*/
};
typedef struct EdgeList EdgeListNode; /*结点类型别名*/
typedef EdgeListNode * Edgelink; /*结点指针别名*/
Edgelink graphorth[Max][2]; /*4.正交邻接表二维地址数组，例：graphorth[i][0]是以i为起点的边的链表首地址，graphorth[i][1]是以i为终点的边的链表首地址*/
图表 6 十字链表
如上图是十字链表的黑线连接部分是邻接表，蓝线连接的部分是逆邻接表。两个表共用边结点，边结点只需建立一次，将结点根据边的起始点加入到对应的邻接表，根据终止点加入到对应的逆邻接表。
那么对于无向图，也有这样的应用，可建立邻接多重表。因为无向图无关方向，只关注顶点有几条边相连接。比如1 –2 这条边，既是1相关的边，也是2相关的边，2—4 这条边既是2相关的边，也是4相关的边。那么1—2 和2—4 都是2相关的边，可以建个链表，把2相关的边都连起来，同时1—2 也是1相关的边，所以把这个结点同时加入到1相关的边链表。按此思路，也可以使用十字链表的边结点结构体来完成。
图表7 邻接多重表
如上图7邻接多重表，把一个无向图的顶点和边的关系描述的很清楚。如果与顶点相关的边链表的头结点为空，则把第一条与顶点相关的边的结点地址写入到一维地址数组顶点对应的位置中。后面如果有新增的边结点，起始点和终止点中包含有顶点。则查看当前与顶点相关的链表尾结点中边的起始点source和终止点destination哪个是顶点。如果source是顶点，则在sourcenext中写入新增边结点的地址，如果是destination是顶点，则在destinationnext中写入新增边结点的地址。
还有一种方法，用一维邻接数组，把顶点和边都加入到一维数组中。比如数组位置0代表顶点0,数组0位置存的6代表，从数组6位置开始存的是0的邻接点，位置1存的8代表，从数组8位置开始存的是1的邻接点。也就是顶点0的邻接点是1和2，也就是边[0 1]和[0 2]。顶点1的邻接点是2和3，也就是边[1 2]和[1 3]以此类推。
图表8 邻接数组。
下面来介绍先深搜索遍历算法（深度优先搜索算法）：比如从图的一个顶点v1开始访问，v1结点访问过了，打访问过的标记（访问过的结点要打访问过的标记，最简单的办法是用一维数组）。然后访问v1的邻接点，比如是v2，如果没访问过则访问，然后访问v2的邻接点。如果v2已经访问过了，则访问v1的下一个邻接点。如此使用递归方法，可以很好的实现，当然也可以使用栈的方法来实现。如下图是从顶点1开始的先深搜索顶点访问顺序图。
图表9 先深搜索顶点访问顺序图
先深搜索算法（递归实现，栈实现两种方法）可执行代码如下：
/*====================begin===========================*/ #include
#include
struct list{/*定义链表结点结构体*/
int data;/*指向的结点序号*/
struct list * next;/*指向下一个结点的指针*/
};
typedef struct list listNode;
typedef listNode * link;
/*===建立邻接表===========*/
void create_EdgeList(link * Gr,int source,int destination){ link p;
link newNode=(link)malloc(sizeof(listNode));
newNode->data=destination;
newNode->next=NULL;
if(Gr[source]==NULL){
Gr[source]=newNode;
}
else{
p=Gr[source];
while(p->next!=NULL){
p=p->next;
}
p->next=newNode;
}
}
/*===打印邻接表==========*/
void print_EdgeList(link * Gr,int len){
int i;
link p;
for(i=0;i p=Gr[i]; printf("%d [%d]: ",i,p); while(p!=NULL){ printf("%d [%d] ",p->data,p->next); p=p->next; } printf("\n"); } printf("\n"); } /*===深度优先======*/ int edgesearch[10][2]={1,2,1,3,2,4,2,5,3,6,3,7,4,8,5,8,6,8,7,8};/*深度优先,广度优先算法使用*/ link deepgraph[9];/*邻接表*/ int vmark[9];/*顶点访问标记数组*/ int counter=0;/*访问顶点计数*/ /*===深度优先搜索递归实现======*/ int deepSearch(link * Gr,int index){ link p=NULL; int q; printf("%d ",index); vmark[index]=1; counter++; if(counter==8) return counter; else{ p=Gr[index]; while(p!=NULL){ if(vmark[p->data]==0){ q=deepSearch(Gr,p->data); if(q==8) return counter ; } p=p->next; } return counter; } } /*===深度优先搜索栈操作=======*/ /*===入栈======*/ void push(int* stack,int data,int* topaddr){ * topaddr=* topaddr +1; stack[* topaddr]=data; } /*===出栈======*/ void pop(int* stack,int* dataaddr,int* topaddr){ * dataaddr=stack[*topaddr]; * topaddr=* topaddr -1; } /*===深度优先搜索栈实现======*/ int deepSearchStack(link *Gr,int index){ link p=NULL; int q=0; int num; int counter=0; int stack[9]; int top=-1; printf("%d ",index); push(stack,index,&top); vmark[index]=1; counter++; while(top>-1){ p=Gr[stack[top]]; while(p!=NULL){ q=0; if(vmark[p->data]==0){ push(stack,p->data,&top); printf("%d ",p->data); vmark[p->data]=1; q=1; counter++; break; } else p=p->next; } if(q==0){ pop(stack,&num,&top); } } return counter; } void main(){ int source; int destination; int result; int i; do{ source=edgesearch[i][0]; destination=edgesearch[i][1]; create_EdgeList(deepgraph,source,destination);/*把正向的边加入邻接表*/ create_EdgeList(deepgraph,destination,source);/*把反向的边也加入邻接表，这是无向图的邻接表建法*/ i++; }while(i<10); printf("Adjacency List:\n"); print_EdgeList(deepgraph,9); printf("\nDi Gui Deep Search:\n"); result=deepSearch(deepgraph,1); printf("\nresult=%d\n\n",result); for(i=0;i<9;i++){ vmark[i]=0; } printf("\nStack Deep Search:\n"); result=deepSearchStack(deepgraph,1); printf("\nresult=%d\n\n",result); getch(); } /*=====================end============================*/ 附执行结果供参考： 先广搜索算法（广度优先搜索算法）： 同先深搜索一样，比如从图的一个顶点v1开始访问，v1结点访问过了，打访问过的标记（访问过的结点要打访问过的标记，最简单的办法是用一维数组）。以顶点1为起始点为例，访问过的顶点打访问过标记。用队列来实现先广搜索算法。将1放入到队列中，查看队列，如果不空，弹出1个数据，弹出数据为1，那么访问1的邻接表，按顺序把未访问过的顶点加入到队列中，并标记已访问。访问过的顶点略过。查看队列，如果不空，弹出队列中第一个数据。访问弹出数据的邻接表，把邻接表中没有访问过的顶点加入队列，查看队列，如果不空，再弹出1个数据。如此循环直到队列为空。下图是从顶点1开始的先广搜索顶点访问顺序图。 图表10 先广搜索顶点顺序图 先广搜索算法（队列实现两种方法）可执行代码如下： /*====================begin===========================*/ #include #include struct list{/*定义链表结点结构体*/ int data;/*指向的结点序号*/ struct list * next;/*指向下一个结点的指针*/ }; typedef struct list listNode; typedef listNode * link; /*===建立邻接表===========*/ void create_EdgeList(link * Gr,int source,int destination){ link p; link newNode=(link)malloc(sizeof(listNode)); newNode->data=destination; newNode->next=NULL; if(Gr[source]==NULL){ Gr[source]=newNode; } else{ p=Gr[source]; while(p->next!=NULL){ p=p->next; } p->next=newNode; } } /*===打印邻接表==========*/ void print_EdgeList(link * Gr,int len){ int i; link p; for(i=0;i p=Gr[i]; printf("%d [%d]: ",i,p); while(p!=NULL){ printf("%d [%d] ",p->data,p->next); p=p->next; } printf("\n"); } printf("\n"); } /*===广度优先======*/ int edgesearch[10][2]={1,2,1,3,2,4,2,5,3,6,3,7,4,8,5,8,6,8,7,8};/*深度优先,广度优先算法使用*/ link deepgraph[9];/*邻接表*/ int vmark[9];/*顶点访问标记数组*/ int counter=0;/*访问顶点计数*/ /*===先广搜索队列操作======*/ /*===入队======*/ void inqueue(int* queue,int* endaddr,int data){ *endaddr=*endaddr+1; queue[*endaddr]=data; } /*===出队======*/ void outqueue(int* queue,int* frontaddr,int* temp){ * frontaddr =* frontaddr+1; * temp = queue[* frontaddr]; } /*===广度优先搜索队列实现======*/ int broadSearch(link *Gr,int index){ link p=NULL; int queue[9]; int front=-1; int end=-1; int temp; int counter=0; vmark[index]=1; inqueue(queue,&end,index); counter++; while(front!=end){ outqueue(queue,&front,&index); printf("%d ",index); p=Gr[index]; while(p!=NULL){ if(vmark[p->data]==0){ vmark[p->data]=1; inqueue(queue,&end,p->data); counter++; } p=p->next; } } return counter; } void main(){ int source; int destination; int result; int i; do{ source=edgesearch[i][0]; destination=edgesearch[i][1]; create_EdgeList(deepgraph,source,destination);/*把正向的边加入邻接表*/ create_EdgeList(deepgraph,destination,source);/*把反向的边也加入邻接表，这是无向图的邻接表建法*/ i++; }while(i<10); printf("Adjacency List:\n"); print_EdgeList(deepgraph,9); for(i=0;i<9;i++){ vmark[i]=0; } printf("\nQueue Broad Search:\n"); result=broadSearch(deepgraph,1); printf("\nresult=%d\n\n",result); getch(); } /*=====================end============================*/ 附执行结果供参考： 最小生成树：一个有n 个结点的连通图，用最少的边（n-1条边）保持图的连通性，并且所选出的各边的长度总和最小。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。 Kruskal算法，将所有的加权边按大小排序，先取长度最小边，并标记该边的起始顶点和终止顶点已访问过。然后从边链表重新选下一条最小的边，但是这条边的起始点和终止点不能都是已标记过的，至少有一个顶点没有标记过。对选出的边中未标记的顶点进行标记已访问过。如此反复直至找出n-1条边。 Prim算法，将所有的加权边按大小排序，先取一个顶点，并标记已访问过。然后选取包含该顶点的长度最小边，并标记新选出的边中未标记的点。然后再选一条最小的边，但是这条边的起始点和终止点必须有一个顶点是没有标记过的，一个顶点是标记过的。对选出的边中未标记的顶点进行标记已访问过。如此反复直至找出n-1条边。 图表11 最小生成树 如上图，选出的边是图中红线。按kruskal算法，选边的顺序是[4 5]，[3 4] ，[1 4 ]，[1 2]。按prim算法，比如从顶点1开始，选边的顺序是[1 4]，[4,5]，[3,4]，[1,2]。 最小生成树kruskal和prim算法可执行代码如下： /*====================begin===========================*/ #include #include int mingraph[10][3]={1,2,7,1,3,6,1,4,5,1,5,12,2,3,14,2,4,8,2,5,8,3,4,3,3, 5,9,4,5,2}; int Mmark[9]; struct mintree{ int marked; int source; int destination; int weight; struct mintree * next; }; typedef struct mintree mtree; typedef mtree * mlink; mlink createMtree(mlink head,int source,int destination,int weight){/*边排序*/ mlink p; mlink q; mlink newNode=(mlink)malloc(sizeof(mtree)); newNode->marked=0; newNode->source=source; newNode->destination=destination; newNode->weight=weight; newNode->next=NULL; if(head==NULL) head=newNode; else{ if(weight newNode->next=head; head=newNode; } else{ p=head; q=head->next; while(q!=NULL){ if(weight newNode->next=q; p->next=newNode; break; else{ p=q; q=q->next; } } if(q==NULL) p->next=newNode; } } return head; } /*kruskal算法*/ void kruskal(mlink head,int Edge){ int edge=0; mlink p=NULL; p=head; while(p!=NULL& edge if(Mmark[p->source]==0|| Mmark[p->destination]==0){ Mmark[p->source]=1; Mmark[p->destination]=1; printf("[%d %d]",p->source,p->destination); edge++; } p=p->next; } } /*prim算法*/ void prim(mlink head,int Edge,int index){ int edge=0; mlink p=NULL; int min; mlink q; Mmark[index]=1; while(edge p=head; min=999; while(p!=NULL){ if((Mmark[p->source]^ Mmark[p->destination])==1) if(p->weight min=p->weight; q=p; } p=p->next; Mmark[q->source]=1; Mmark[q->destination]=1; printf("[%d %d] ",q->source,q->destination); edge++; } } void main(){ int i=0; int source; int destination; int weight; mlink head=NULL; do{ source=mingraph[i][0]; destination=mingraph[i][1]; weight=mingraph[i][2]; head=createMtree(head,source,destination,weight); i++; }while(i<10); printf("\nKruskal Minimum Spanning Tree:\n "); kruskal(head,4); printf("\n"); for(i=0;i<9;i++){ Mmark[i]=0; } printf("\nPrim Minimum Spanning Tree:\n "); prim(head,4,1); printf("\n"); getch(); } /*=====================end============================*/ 执行结果如下： 最短路径： 图表12 最短路径 如上图是起点设定为0，查找0到各顶点的最短路径，选出的边是图中红线。可以用Dijkstra （迪杰斯特拉）算法和Floyd（弗洛伊德）算法。 Dijkstra算法是：采用邻接矩阵Graph[6][6]，没有联系的两个顶点形成的边设为999这个值。先对开始的顶点v1标记已访问，然后再选一个点v2，[v1 v2]是v1到其它所有顶点中最短的这条边。标记v2已访问过，计算v1通过v2到其它顶点v3（指v2到v3有边且边长不等于999且v3没有标记过的情况）的距离，如果比直接从v1到v3的距离短，则用v1到v2的距离与v2到v3的距离之和来替代v1到v3的距离，写入到邻接矩阵，标记v3为v2的前置顶点。计算替换完所有可以计算的v3类顶点。同上面对v2的操作，再选一个新的顶点v4（未标记过的），在未标记过的顶点中，[v1 v4]是边长最短的。标记v4然后计算v1通过v4到其它未标记顶点v5的新距离。如果新距离比从v1直接到达更短，则替换v1到对应顶点v5的距离，标记v4为v5的前置顶点。循环执行直到所有顶点都被标记过。 Floyd 算法是：Graph[i][i]=0;(i=0;i<6;i++)，对从顶点i到顶点j的距离，我们取顶点u(0= 最短路径Dijkstra算法和Floyd算法可执行代码如下： /*====================begin===========================*/ #include #include #define Max 6 int graphshortpath[Max][Max];/*图的邻接距阵，用来存放边长*/ int edgeshortpath[9][3]={0,1,6,0,2,3,2,1,2,1,3,5,2,3,3,2,4,4,3,4,2,3,5,3, 4,5,5};/*6个顶点9条边的图的初始数组*/ int Smark[6];/*结点标记数组，1表示已选，0表示未选*/ int prenode[Max];/*前置结点数组*/ void createShortpath(int(* Gr)[Max],int source,int destination,int weight){/*建无向图*/ Gr[source][destination]=weight; Gr[destination][source]=weight; } void push(int* stack,int data,int* topaddr){ * topaddr=* topaddr +1; stack[* topaddr]=data; } void pop(int* stack,int* dataaddr,int* topaddr){ * dataaddr=stack[*topaddr]; * topaddr=* topaddr -1; } void shortpathDijkstra(int(* Gr)[Max],int index){ int p,q; int counter=0; int min; int i; int stack[6];/*用来输出连串的前置结点*/ int top=-1; int temp; Smark[index]=1; min=999; for(i=0;i prenode[i]=index;/*前置结点数组初始化为指定的开始结点*/ if(Gr[index][i]!=999&& Gr[index][i] min=Gr[index][i]; p=i; } } printf("%d->%d ",index,p); Smark[p]=1; counter++; while(counter<5){ for(i=0; i if( Gr[p][i]!=999&& Smark[i]==0){ temp=Gr[index][p]+Gr[p][i];/*计算index结点通过新增前置结点能到达的未标记结点的距离*/ if(temp Gr[index][i]=temp;/*距离替换*/ prenode[i]=p;/*前置结点替换*/ printf("%d->%d ",p,i); } } } min=999; for(i=0;i if(Smark[i]==0){ if(Gr[index][i] min=Gr[index][i]; q=i;/*找出index结点到达所有未标记结点距离最短的点*/ } } } Smark[q]=1; counter++; p=q; } printf("\n"); for(i=0;i if(i!=index){ printf("[%d->%d %d] ",index,i,Gr[index][i]); } } printf("\n"); for(i=0;i if(i!=index){ push(stack,i,&top); p=prenode[i]; while(p!=index){ push(stack,p,&top); p=prenode[p]; } printf("%d-> ",index); while(top!=-1){ pop(stack,&p,&top); printf("%d-> ",p); } printf(" [%d->%d length=%d]\n",index,i,Gr[index][i]); } } } void shortpathFloyd(int(* Gr)[Max],int index){ int i,j,u; int stack[6];/*栈用来输出连串的前置结点*/ int top=-1; int p; for(i=0;i prenode[i]=index;/*前置结点数组初始化为指定的开始结点*/ } for(i=0;i Gr[i][i]=0; } for(u=0;u for(i=0;i for(j=0;j if(Gr[i][u]+Gr[u][j] Gr[i][j]=Gr[i][u]+Gr[u][j]; if(i==index){ prenode[j]=u; printf("%d->%d ",u,j); } } } } } printf("\n"); for(i=0;i if(i!=index){ printf("[%d->%d %d] ",index,i,Gr[index][i]); } } printf("\n"); for(i=0;i if(i!=index){ push(stack,i,&top); p=prenode[i]; while(p!=index){ push(stack,p,&top); p=prenode[p]; } printf("%d-> ",index); while(top!=-1){ pop(stack,&p,&top); printf("%d-> ",p); } printf(" [%d->%d length=%d]\n",index,i,Gr[index][i]); } } } void main(){ int i; int j; int source; int destination; int weight; int index; for(i=0;i for(j=0;j graphshortpath[i][j]=999; } } i=0; do{ source=edgeshortpath[i][0]; destination=edgeshortpath[i][1]; weight=edgeshortpath[i][2]; createShortpath(graphshortpath,source,destination,weight); i++; }while(i<9); for(i=0;i for(j=0;j printf("%3d ",graphshortpath[i][j]); } printf("\n"); } index=0; printf("\nDijkstra Shortest Path:\n"); shortpathDijkstra(graphshortpath,index); for(i=0;i for(j=0;j graphshortpath[i][j]=999; } } i=0; do{ source=edgeshortpath[i][0]; destination=edgeshortpath[i][1]; weight=edgeshortpath[i][2]; createShortpath(graphshortpath,source,destination,weight); i++; 数学与计算机学院 课程设计说明书 课程名称: 数据结构与算法课程设计 课程代码: 6014389 题目: 图的遍历和生成树求解实现 年级/专业/班: 学生姓名: 学号: 开始时间: 2012 年 12 月 09 日 完成时间: 2012 年 12 月 26 日 课程设计成绩： 指导教师签名：年月日 目录 摘要 (3) 引言 (4) 1 需求分析 (5) 1.1任务与分析 (5) 1.2测试数据 (5) 2 概要设计 (5) 2.1 ADT描述 (5) 2.2程序模块结构 (7) 软件结构设计： (7) 2.3各功能模块 (7) 3 详细设计 (8) 3.1结构体定义 (19) 3.2 初始化 (22) 3.3 插入操作（四号黑体） (22) 4 调试分析 (22) 5 用户使用说明 (23) 6 测试结果 (24) 结论 (26) 摘要 《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。 因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。 关键词：计算机；图；算法。 数据结构家谱管理 系统 宁波大红鹰学院 信息工程学院 课 程 设 计 报 告 项目名 家谱查询系统 称： 白钰琦 项目组 长： 徐程凯、徐海域、项鸿伟 项目成 员： 10计科1班 班级名 称： 计算机科学与技术 专业名 称： 完成时间: 12月1日 信息工程学院制 目录 一、案例描述 ............................................................ 错误!未定义书签。 1、总体描述 ....................................................... 错误!未定义书签。 2、模块描述 ....................................................... 错误!未定义书签。 二、设计思路 ............................................................ 错误!未定义书签。 三、程序设计 ............................................................ 错误!未定义书签。 1、数据结构描述................................................ 错误!未定义书签。 2、主函数及其流程图........................................ 错误!未定义书签。 3、源程序 ........................................................... 错误!未定义书签。 四、调试与分析 ........................................................ 错误!未定义书签。 1、主菜单 ........................................................... 错误!未定义书签。 2、显示家谱信息................................................ 错误!未定义书签。 3、显示家谱中第n代人所有信息 .................... 错误!未定义书签。 4、按姓名查找某人并相应输出 ........................ 错误!未定义书签。 5、按出生日期查找家谱成员信息 .................... 错误!未定义书签。 6、为家谱中成员添加孩子信息 ........................ 错误!未定义书签。 7、为家谱中成员添加妻子信息 ........................ 错误!未定义书签。 8、删除家谱中成员及其后代信息 .................... 错误!未定义书签。 9、修改家谱中成员信息.................................... 错误!未定义书签。 10、确定家谱中两个成员关系 .......................... 错误!未定义书签。 11、按出生年月排序家谱 .................................. 错误!未定义书签。 五、设计总结 ............................................................ 错误!未定义书签。 1、完成情况 ....................................................... 错误!未定义书签。 2、心得体会 ....................................................... 错误!未定义书签。 数据结构实验报告 实验：图的遍历 一、实验目的： 1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表 2、掌握图的构造方法 3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法 4、掌握图的深度优先遍历和广度优先原理 二、实验内容： 1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。 2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图 3、深度优先遍历第一步中构造的图G，输出得到的节点序列 4、广度优先遍历第一部中构造的图G，输出得到的节点序列 三、实验要求： 1、无向图中的相关信息要从终端以正确的方式输入； 2、具体的输入和输出格式不限； 3、算法要具有较好的健壮性，对错误操作要做适当处理； 4、程序算法作简短的文字注释。 四、程序实现及结果： 1、邻接矩阵： #include 一、定义与术语 图：无序数据结构 基本构成：1.边集（Edge ）：a. 有向图，有向边 数据结构实验---图的储存与遍历 学号： 姓名： 实验日期： 2016.1.7 实验名称： 图的存贮与遍历 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 V0 V1 V2 V3 V4 三、附录： 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;i 家谱管理系统 姓名：田鑫磊 学号：1514020421 (1)功能部分： 本程序共实现了6个功能分别为： 1.读出家谱并显示 2.确定指定成员在家族中的辈份 3.输出指定辈的所有成员 4.在家谱中添加新成员，并追加到文件中 5.输出指定家庭的所有成员 6. 退出本系统 (2)各功能的算法思想： 1.读出家谱并显示 存储结构用栈，按照先显示双亲，然后显示其所有孩子的顺序显示所有的家庭成员。 2.确定指定成员在家族中的辈份 用求成员所在的二叉树中的层数（按层遍历二叉树）来确定，这里采用的是递归算法3.输出指定辈的所有成员 此处定义了一个新的结构体类型（增加存储节点所在的层数），定义如下： struct { BTNode *q; int loc; //存结点所在的层数 }qu[10]; 并用一个队列来比较显示同辈分的所有成员。 4.在家谱中添加新成员，并追加到文件中 首先，输入一个新成员的名字； 然后，输入其双亲； 之后，再添加到整个存储二叉链表中。 然后，再将新的存储结构写回到文件中。 二叉链表的结点类型为：typedef struct node { ElemType data[10]; //存放成员的名字 struct node *child; //其孩子指针 struct node *brother; //其兄弟指针 }BTNode; 5.输出指定家庭的所有成员 首先，设一个栈，并设一个标记位，先置1； 然后，找到输入的要待显示的成员，将标记位置0； 再次，显示其孩子和兄弟，依次下去直到显示完其所有的亲戚。 6.退出本系统 通过一个输入字符q来控制，每完成一个功能，系统提示是否要继续操作： 第8章 图 8-1 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n 个顶点的无向完全图中，边的条数为n(n-1)/2。 【解答】 【证明】 在有n 个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有 n-1条边与其他n-1个顶点相连，总计n 个顶点有n(n-1)条边。但在无向图中，顶点i 到顶点j 与顶点j 到顶点i 是同一条边，所以总共有n(n-1)/2条边。 8-2 右边的有向图是强连通的吗？请列出所有的简单路径。 【解答】 点，它不是强连通的有向图。各个顶点自成强连通分量。 所谓简单路径是指该路径上没有重复的顶点。 从顶点A 出发，到其他的各个顶点的简单路径有A →B ，A →D →B ，A →B →C ，A →D →B →C ，A →D ，A →B →E ，A →D →E ，A →D →B →E ，A →B →C →F →E ，A →D →B →C →F →E ，A →B →C →F ，A 1个顶点的 无向完全图 2个顶点的 无向完全图 3个顶点的 无向完全图 4个顶点的 无向完全图 5个顶点的 无向完全图 A D ????????? ?????? ?????=01 00000001001010000 010*********Edge →D →B →C →F 。 从顶点B 出发，到其他各个顶点的简单路径有B →C ，B →C →F ，B →E ，B →C →F →E 。 从顶点C 出发，到其他各个顶点的简单路径有C →F ，C →F →E 。 从顶点D 出发，到其他各个顶点的简单路径有D →B ，D →B →C ，D →B →C →F ，D →E ，D →B →E ，D →B →C →F →E 。 从顶点E 出发，到其他各个顶点的简单路径无。 从顶点F 出发，到其他各个顶点的简单路径有F →E 。 8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。 【解答】 (1) 邻接矩阵 A D #include"stdlib.h" #include"stdio.h" #include"malloc.h" #define INFINITY 32767 #define MAX_VERTEX_NUM 20 typedef enum{FALSE,TRUE}visited_hc; typedef enum{DG,DN,UDG,UDN}graphkind_hc; typedef struct arccell_hc {int adj; int*info; }arccell_hc,adjmatrix_hc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct {char vexs[MAX_VERTEX_NUM]; adjmatrix_hc arcs; int vexnum,arcnum; graphkind_hc kind; }mgraph_hc; typedef struct arcnode_hc {int adjvex; struct arcnode_hc *nextarc; int*info; }arcnode_hc; typedef struct vnode_hc {char data; arcnode_hc *firstarc; }vnode_hc,adjlist_hc[MAX_VERTEX_NUM]; typedef struct {adjlist_hc vertices; int vexnum,arcnum; graphkind_hc kind; }algraph_hc; int locatevex_hc(mgraph_hc*g,char v) {int i,k=0; for(i=0;i ##大学 数据结构课程设计报告题目：图的遍历和生成树求解 院（系）：计算机工程学院 学生: 班级：学号: 起迄日期: 2011.6.20 指导教师: 2010—2011年度第 2 学期 一、需求分析 1.问题描述： 图的遍历和生成树求解实现 图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。 生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生成树。 2.基本功能 1) 先任意创建一个图； 2) 图的DFS,BFS的递归和非递归算法的实现 3) 最小生成树（两个算法）的实现，求连通分量的实现 4) 要求用邻接矩阵、邻接表等多种结构存储实现 3.输入输出 输入数据类型为整型和字符型，输出为整型和字符 二、概要设计 1.设计思路： a.图的邻接矩阵存储：根据所建无向图的结点数n,建立n*n的矩阵，其中元素全是无穷大（int_max），再将边的信息存到数组中。其中无权图的边用1表示，无边用0表示；有全图的边为权值表示，无边用∞表示。 b.图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。 c.图的广度优先遍历：假设从图中的某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的，则另选未被访问的重复以上步骤，是一个非递归过程。 d.图的深度优先遍历：假设从图中某顶点v出发，依依次访问v的邻接顶点，然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，这是个递归的过程。 e.图的连通分量：这是对一个非强连通图的遍历，从多个结点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分量的顶点集。本程序利用的图的深度优先遍历算法。 2.数据结构设计： ADT Queue{ 数据对象：D={a i | a i ∈ElemSet,i=1,2,3……，n,n≥0} 数据关系：R1={| a i-1 ,a i ∈D,i=1,2,3,……，n} 基本操作： InitQueue(&Q) 操作结果：构造一个空队列Q。 QueueEmpty(Q) 初始条件：Q为非空队列。 操作结果：若Q为空队列，则返回真，否则为假。 EnQueue(&Q,e) 初始条件：Q为非空队列。 操作结果：插入元素e为Q的新的队尾元素。 DeQueue(&Q,e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。}ADT Queue //////////////////////////////////////////////////////////// /////////////////// //题目：家谱资料管理 //要求：家谱用于记录某家族历代家族成员的情况与关系。现编制一个家谱资料管理软件， //实现对一个家族所有的资料进行收集整理。支持对家谱的增加，删除，更新，统计等。 //////////////////////////////////////////////////////////// /////////////////// #include int Num; //记录这个人拥有几个儿女 char Name[20]; //记录这个人的姓名 char Kind; //标示节点的种类有女G男B struct TreeNode * NextNode[20]; //记录这个人的儿女struct TreeNode * Parent; //记录这个节点的父节点 }TreeNode; void CreatTree(TreeNode *Tree); void OutPutAll(TreeNode *Tree); TreeNode * SearchTree(TreeNode *Tree,char name[],int length); void MainMenue(TreeNode *Tree); void SubMenue1(TreeNode * Tree); void SubMenue2(TreeNode *Tree); void Change(TreeNode * Tree); void AddNew(TreeNode * Tree); 第七章图：习题 习题 一、选择题 1．设完全无向图的顶点个数为n，则该图有( )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3．有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7．对于具有e条边的无向图，它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先 二、填空题 1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。 8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。 实验四图的存储、遍历与应用姓名：班级： 学号：日期：一、实验目的： 二、实验内容： 三、基本思想，原理和算法描述: 四、源程序： （1）邻接矩阵的存储： #include #include 家谱管理系统——C语言（数据结构） 目的和要求：树形结构是一种非常重要的非线性结构，它用于描述数据元素之间的层次关系，人类家谱是树形结构的典型体现，通过此项训练让学生掌握树形结构的知识；使学生重点掌握树与二叉树的转换，二叉树的存储和遍历，和二叉树相关的一些运算；要求完成家谱信息的录入和保存，任意成员的查找及某一成员祖先、子孙、兄弟、堂兄弟的查找。 排答疑和辅导。 完整代码： #include 实验六图的应用及其实现 （相关知识点：拓扑排序、关键路径、最小生成树和最短路径） 一、实验目的 1．进一步功固图常用的存储结构。 2．熟练掌握在图的邻接表实现图的基本操作。 3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。 二、实验内容 一>.基础题目：(本类题目属于验证性的，要求学生独立完成) [题目一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。 测试数据：教材图7.28 [题目二]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 测试数据：教材图7.29 二>.简单应用题目：（ACM/ICPC训练题，本类题目属于设计性的，要求学生三人为一个团队，分工协作完成)） 【题目三】高速公路 描述 某国共有n个城市（n不超过200），有些城市之间直接有一条高速公路相连，高速公路都是双向的，总共有m条。每条高速公路都有自己的载重限制，即载重最大值。通过车辆的载重不能超过公路的载重限制。如今我们想了解的是，从某一起点城市出发，到达目标城市，车辆最多能带多重的货物。 输入 输入的第一行为两个整数n和m。以下有m行，每行三个整数描述一条公路，分别是首尾相连的城市以及载重限制。然后是一个整数k，即问题个数。接下来k行描述k个问题，每行两个整数表示起点城市和目标城市。问题数不超过一百。 输出 输出包括k行，每行对应一个问题，输出从起点到目标的最大载重量。如果两城市间无路径则输出-1。 样例输入 3 3 1 2 100 2 3 100 1 3 50 2 1 3 2 3 样例输出 100 100 【题目四】最短的旅程 描述 在Byteland有n个城市（编号从1到n），它们之间通过双向的道路相连。Byteland 的国王并不大方，所以，那里只有n -1条道路，但是，它们的连接方式使得从任意城市都可以走到其他的任何城市。 一天，starhder到了编号为k的城市。他计划从城市k开始，游遍城市m1，m2，m3……，mj（不一定要按这个顺序旅游）。每个城市mi都是不同的，并且，也与k不同。Starhder ——就像每一个旅行家一样，携带的钱总是有限的，所以，他要以最短的路程旅行完所有的城市（从城市k开始）。于是，他请你帮助计算一下，旅游完上述的城市最短需要多少路程。 输入 实践四：图及图的应用 1.实验目的要求 理解图的基本概念，两种主要的存储结构。掌握在邻接链表存储结构下的图的深度优先递归遍历、广度优先遍历。通过选做题"最短路径问题"认识图及其算法具有广泛的应用意义。 实验要求：正确调试程序。写出实验报告。 2.实验主要内容 2.1 在邻接矩阵存储结构下的图的深度优先递归遍历、广度优先遍历。 2.1.1 要完成图的两种遍历算法，首先需要进行图的数据初始化。为把时间主要花在遍历算法的实现上，图的初始化采用结构体声明时初始化的方法。示例代码如下： #include "stdio.h" typedef int Arcell; typedef int AdjMatrix[5][5]; typedef struct { char vexs[5]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; void main(){ MGraph g={ {'a','b','c','d','e'}, {{0,1,0,1,0}, {1,0,0,0,1}, {1,0,0,1,0}, {0,1,0,0,1}, {1,0,0,0,0}} ,5,9}; } 2.1.2 深度优先遍历算法7.5中FirstAdjVex方法和NextAdjVex方法需要自己实现。 2.2 拓扑排序，求图的拓扑序列 2.3 "最短路径问题"，以校园导游图为实际背景进行设计。（选做） 程序代码如下： #include #include 实习报告 题目：图遍历的演示 编译环 境： Microsoft Visual Studio 2010 功能实现： 以邻接表为存储结构，演示在连通无向图上访冋全部节点的操作； 实现连通无向图的深度优先遍历和广度优先遍历； 建立深度优先生成树和广度优先生成树，按凹入表或树形打印生成树。 1.以邻接表为存储结构，演示在连通无向图上访问全部节点的操作。 该无向图为 一个交通网络，共25个节点，30条边，遍历时需要以用户指定的节点为起点， 建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。 2.程序的测试数据：graph.txt 文件所表示的无向交通图。 //边表结点 //邻接点域，即邻接点在顶点表中的下标 //顶点表结点 //数据域 struct TNode // 树结点 { stri ng data; struct TNode *fristchild, * nextchild; }; 2.邻接表类设计： class GraphTraverse { public: 需求分析 二、概要设计 1.主要数据结构设计: struct ArcNode { int vex In dex; ArcNode* n ext; }; struct VertexNode { stri ng vertex; ArcNode* firstArc; }; 三、详细设计 1. 主要操作函数的实现： (1) 建立深度优先生成树函数： TNode* GraphTraverse::DFSForest(i nt v) { int i,j; TNode *p,*q,*DT; j=v; for(i=O;i 数据结构大作业说明文档 一、题目的选择 这次数据结构的大作业，我的选题是家谱管理系统的设计与实现。由于平时疏于编程——针对我得个人实际——我把主要的目标定位在完成家谱管理系统得基本要求。（基本要求大纲中有，就不浪费版面了） 二、设计的思路 接到这个题目，我的总体设计思路是先为程序搭建好一个结构框架，再跟据时间的宽裕程度和其它的要求逐步增强程序的性能。 关于IO的设计： 考虑到题目要求家谱信息以树形的形式一次读入内存，而个人的各种资料现在虽然条目不多，但随着程序的升级，以后可能变得越来越大。我把树形结构和个人信息记录的文档分为两个文件保存在外存中，一个文件串行化地记录家谱树的结构信息，保存少量个人信息作为识别标志；另一个文件保存完整的个人信息，所有的个人信息以线性记录的方式记录在其中。当程序运行要读入家谱结构时，只读入保存少量记录的文件并建立起树形结构。索引时，以树形中的少量信息为依据在另一个文件中找到全部的各人信息资料。 这样的好处主要有两点： 1. 由于树形结构是串行化记录于外存，一个节点记录多次，信息大量冗余，如果树形节点中保留全部信息，必将造成大量的空间浪费；只保存作为索引的少量信息在树形结构中，节约了空间。 2. 由于结构的精简，在家谱初始化时读入内存需要的时间相应减少，节约了装载时间。 这样做存在的问题： 每次执行修改，添加，删除，查询时都要直接访问外存来取得或写入数据。内外存访问上的巨大时间差的存在，使得进行这些操作相对来说并不显得很高效。 关于树形的结构： 在树形结构的选择上，根据实际中多子女的现象选择一般树，考虑到家谱中成员可能存在的不定成员数问题，抛弃了以数组为基础的一般树方案，决定用链表来实现。 树形结构的外存保存。为了提高效率，树形结构在程序初始化时由外存文件一次读入内存，此后不管插入还是修改，删除都不再对外存的树结构保存文件进行操作，只在内存中处理，程序退出时对外存树结构文件进行一次更新。也就是说，不管在程序运行中中对家谱结构进行多少种，多少次的操作，外存的树结构文件始终只会被程序访问两次。数据结构课程设计图的遍历和生成树求解
数据结构家谱管理系统范本
数据结构实验报告-图的遍历
数据结构--图重点
数据结构实验---图的储存与遍历
数据结构家谱课程设计报告
数据结构-图习题
数据结构图的遍历
数据结构课程设计之图的遍历和生成树求解
数据结构家谱管理系统
数据结构图习题
数据结构 图的存储、遍历与应用 源代码
数据结构无向图
家谱管理系统(含源代码)
数据结构--图的应用及其实现
数据结构 图的遍历(初始化图)
数据结构_图遍历的演示
数据结构家谱管理系统报告书