#2
书生牛犊2016-06-17 17:06
ps:我去年刚在慕课上学的算法,小白一个,别被版主的名头吓到了
1.我复制了代码,但没能搞清你的思路架构。调试都做不到(主要是一看到这么长的代码就头疼,没有过看别人代码的经历),所以希望你能把题目、以及题目的测试案例也贴出来,看着方便些。 2. 请选择进行的操作: 你看下我这个测试流程有没错。我这图是等长的边,应该结果是1-2 1-3 1-4,你的程序不知道为什么跑出三个1-1来,我想第一你就没做筛选,你没有机制去判断这个要去的地方是不是已经去过了(或者你看下这里有没有问题)1.构建图 2.遍历 3.构建最小生成树 3 请先构建无向网 构建无向网,请输入顶点的数目和边的数目: 4 6 请依次输入对应的顶点的值: 1 2 3 4 请输入第1条边的第一个顶点的值:1 请输入第1条边的第二个顶点的值:2 请输入权值 9 请输入第2条边的第一个顶点的值:2 请输入第2条边的第二个顶点的值:3 请输入权值 9 请输入第3条边的第一个顶点的值:3 请输入第3条边的第二个顶点的值:4 请输入权值 9 请输入第4条边的第一个顶点的值:1 请输入第4条边的第二个顶点的值:3 请输入权值 9 请输入第5条边的第一个顶点的值:2 请输入第5条边的第二个顶点的值:4 请输入权值 9 请输入第6条边的第一个顶点的值:4 请输入第6条边的第二个顶点的值:1 请输入权值 9 请输入最小生成树的起点 1 (1-1)(1-1)(1-1) -------------------------------- Process exited after 93.49 seconds with return value 0 请按任意键继续. . . 3.我看你那个最小生成树的函数好短,我自己曾经写过一个Prim的练习作业,里面的Prim就要长得多。 程序代码: #include <stdio.h> #include <stdlib.h> #define FULL 101 typedef struct LNode *Vertex; struct LNode { int b,lenth; Vertex Next; }; Vertex CreatV(int); void FreeV(Vertex,int); int Prim(Vertex,int); Vertex InsertV(Vertex,int,int); int main() { int N,M; scanf("%d%d",&N,&M); Vertex V=CreatV(N+1); for(int i=0; i<M; i++) { int from,to,lenth; scanf("%d%d%d",&from,&to,&lenth); InsertV(&V[to],from,lenth); InsertV(&V[from],to,lenth); } int lenth=Prim(V,N+1); printf("%d",lenth); return 0; } int Prim(Vertex V,int n) { printf("*"); int lenth=0; int min=0; for(int i=1; i<n; i++) { if(V[i].Next) if(V[i].Next->lenth<V[min].Next->lenth)min=i; } int*a=(int*)malloc(sizeof(int)*n-1),right=1; a[0]=min; lenth+=V[min].Next->lenth; a[right++]=V[min].Next->b; FreeV(V,a[0]); while(right<n-1) { min=-1; for(int i=0; i<right; i++) { if(V[a[i]].Next){ if(min!=-1){ if(V[a[i]].Next->lenth<V[a[min]].Next->lenth)min=i; }else min=i; } } if(min==-1)return 0; int i; for(i=0; i<right; i++) if(a[i]==V[a[min]].Next->b)break; if(i==right) { printf("%d",V[a[min]].Next->b) ; a[right++]=V[a[min]].Next->b; lenth+=V[a[min]].Next->lenth; } FreeV(V,a[min]); } printf("%d ",a[0]); return lenth; } void FreeV(Vertex V,int X) { Vertex temp=V[X].Next; V[X].Next=temp->Next; X=temp->b; free(temp); temp=V[X].Next; V[X].Next=temp->Next; free(temp); } Vertex CreatV(int num) { Vertex V=(Vertex)malloc(sizeof(struct LNode)*num); for(int i=0; i<num; i++) { V[i].Next=NULL; V[i].b=0; V[i].lenth=0; } V[0].Next=(Vertex)malloc(sizeof(struct LNode)); V[0].Next->b=0; V[0].Next->lenth=FULL; V[0].Next->Next=NULL; return V; } Vertex InsertV(Vertex V,int b,int lenth) { Vertex head=V; while(V->Next) { if(V->Next->lenth>lenth)break; if(V->Next->lenth==lenth&&V->Next->b>b)break; V=V->Next; } Vertex New=(Vertex)malloc(sizeof(struct LNode)); New->lenth=lenth; New->b=b; New->Next=V->Next; V->Next=New; return head; } |
真的很郁闷,自己纠错了两天还是不行
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INT_MAX 1000
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
#define ERROR false
#define OK true
typedef struct ArcCell {
int adj;
char *info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
int vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum, arcnum;
int kind;
}MGraph;
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
int *info;
}ArcNode;
typedef struct VNode{
int data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
//邻接矩阵 (udn)
int LocateVex(MGraph G, int u)
{
int i;
for (i=0; i<G.vexnum; ++i){
if (G.vexs[i]==u)
return i;
}
return -1;
}
int CreateDG(MGraph &G) {
int i,j,k;
int v1,v2;
printf("构建有向图,请输入顶点的数目和边的数目:\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("请依次输入对应的顶点值:\n");
for( i = 0; i < G.vexnum; ++i ) {
scanf("%d",&G.vexs[i]);
}
for( i = 0; i < G.vexnum; ++i ) {
for( j = 0; j <G.vexnum; ++j ) {
G.arcs[i][j].adj = 0;
G.arcs[i][j].info = NULL;
}
}
for( k = 0; k < G.arcnum; ++k ) {
printf("请输入第%d条边的第一个顶点的值:",k+1);
scanf("%d",&v1);
printf("请输入第%d条边的第二个顶点的值:",k+1);
scanf("%d",&v2);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j].adj=1;
}
}
int CreateDN(MGraph &G) {
int i,j,k,w;
int v1,v2;
printf("构建有向网,请输入顶点的数目和边的数目:\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("请依次输入对应的顶点的值:\n");
for( i = 0; i < G.vexnum; ++i ) {
scanf("%d",&G.vexs[i]);
}
for( i = 0; i < G.vexnum; ++i ) {
for( j = 0; j <G.vexnum; ++j ) {
G.arcs[i][j].adj = INFINITY;
G.arcs[i][j].info = NULL;
}
}
for( k = 0; k < G.arcnum; ++k ) {
printf("请输入第%d条边的第一个顶点的值:",k+1);
scanf("%d",&v1);
printf("请输入第%d条边的第二个顶点的值:",k+1);
scanf("%d",&v2);
printf("请输入权值\n");
scanf("%d",&w);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j].adj=w;
}
}
int CreateUDG(MGraph &G) {
int i,j,k;
int v1,v2;
printf("构建无向图,请输入顶点的数目和边的数目:\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("请依次输入对应的顶点的值:\n");
for( i = 0; i < G.vexnum; ++i ) {
scanf("%d",&G.vexs[i]);
}
for( i = 0; i < G.vexnum; ++i ) {
for( j = 0; j <G.vexnum; ++j ) {
G.arcs[i][j].adj = 0;
G.arcs[i][j].info = NULL;
}
}
for( k = 0; k < G.arcnum; ++k ) {
printf("请输入第%d条边的第一个顶点的值:",k+1);
scanf("%d",&v1);
printf("请输入第%d条边的第二个顶点的值:",k+1);
scanf("%d",&v2);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j].adj=1;
}
}
int CreateUDN(MGraph &G) {
int i,j,k,w;
int v1,v2;
printf("构建无向网,请输入顶点的数目和边的数目:\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("请依次输入对应的顶点的值:\n");
for( i = 0; i < G.vexnum; ++i ) {
scanf("%d",&G.vexs[i]);
}
for( i = 0; i < G.vexnum; ++i ) {
for( j = 0; j <G.vexnum; ++j ) {
G.arcs[i][j].adj = INFINITY;
G.arcs[i][j].info = NULL;
}
}
for( k = 0; k < G.arcnum; ++k ) {
printf("请输入第%d条边的第一个顶点的值:",k+1);
scanf("%d",&v1);
printf("请输入第%d条边的第二个顶点的值:",k+1);
scanf("%d",&v2);
printf("请输入权值\n");
scanf("%d",&w);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j].adj=w;
}
}
//邻接表
int CreateUDG2(ALGraph &G){
int i,s,d;
ArcNode *p,*q;
printf("请输入顶点数,边数:\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("请输入顶点值(字符)\n");
for(i=0;i<G.vexnum;i++){
getchar();
scanf("%c",&G.vertices[i].data);
G.vertices[i].firstarc=NULL;
}
printf("请输入顶点序号:\n");
for(i=0;i<G.arcnum;i++){
scanf("%d%d",&s,&d);
p=(ArcNode*)malloc(sizeof(ArcNode));
q=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=d;
q->adjvex=s;
p->nextarc=G.vertices[s].firstarc;
G.vertices[s].firstarc=p;
q->nextarc=G.vertices[d].firstarc;
G.vertices[d].firstarc=q;
}
}
int CreateDG2(ALGraph &G){
int i,s,d;
ArcNode *p;
printf("请输入顶点数,边数:\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("请输入顶点值(字符)\n");
for(i=0;i<G.vexnum;i++){
getchar();
scanf("%c",&G.vertices[i].data);
G.vertices[i].firstarc=NULL;
}
printf("请输入顶点序号:\n");
for(i=0;i<G.arcnum;i++){
scanf("%d%d",&s,&d);
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=d;
p->nextarc=G.vertices[s].firstarc;
G.vertices[s].firstarc=p;
}
}
int CreateDN2(ALGraph &G){
int i,s,d,IncInfo;
ArcNode *p;
printf("请输入顶点数,边数:\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("请输入顶点值(字符)");
for(i=0;i<G.vexnum;i++){
getchar();
scanf("%c",&G.vertices[i].data);
G.vertices[i].firstarc=NULL;
}
printf("请输入顶点序号:\n");
for(i=0;i<G.arcnum;i++){
scanf("%d%d",&s,&d);
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=d;
p->nextarc=G.vertices[s].firstarc;
G.vertices[s].firstarc=p;
printf("此边是否含有其他信息?(0.是 1. 否)");
scanf("%d",&IncInfo);
if(IncInfo){
printf("请输入相关信息\n");
scanf("%s",p->info);
}
}
}
int CreateUDN2(ALGraph &G){
int i,s,d,IncInfo;
ArcNode *p,*q;
printf("请输入顶点数,边数:\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("请输入顶点值(字符)\n");
for(i=0;i<G.vexnum;i++){
getchar();
scanf("%c",&G.vertices[i].data);
G.vertices[i].firstarc=NULL;
}
printf("请输入顶点序号:\n");
for(i=0;i<G.arcnum;i++){
scanf("%d%d",&s,&d);
p=(ArcNode*)malloc(sizeof(ArcNode));
q=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=d;
q->adjvex=s;
p->nextarc=G.vertices[s].firstarc;
G.vertices[s].firstarc=p;
q->nextarc=G.vertices[d].firstarc;
G.vertices[d].firstarc=q;
printf("此边是否含有其他信息?(0.是 1. 否)");
scanf("%d",&IncInfo);
if(IncInfo){
printf("请输入相关信息\n");
scanf("%s",p->info);
}
}
}
int CreateGraph2(ALGraph &G) {
printf("请输入你要创建的图的类型:\n1、有向图;2、有向网;3、无向图;4、无向网\n");
scanf("%d",&G.kind);
switch(G.kind) {
case 1: CreateDG2(G);break;
case 2: CreateDN2(G);break;
case 3: CreateUDG2(G);break;
case 4: CreateUDN2(G);break;
default:return ERROR;
}
}
int CreateGraph(MGraph &G) {
printf("请输入你要创建的图的类型:\n1、有向图;2、有向网;3、无向图;4、无向网\n");
scanf("%d",&G.kind);
switch(G.kind) {
case 1: CreateDG(G);break;
case 2: CreateDN(G);break;
case 3: CreateUDG(G);break;
case 4: CreateUDN(G);break;
default:return ERROR;
}
}
int(*VisitFunc)(int v,ALGraph G);
bool visited[MAX_VERTEX_NUM];
//DFS
int DFS(ALGraph G,int v){
ArcNode *p;
visited[v]=true;
(*VisitFunc)(v,G);
for(p=G.vertices[v].firstarc;p;p=p->nextarc){
if(!visited[p->adjvex])
DFS(G,p->adjvex);
}
}
//DFSraverse
int DFSTraverse(ALGraph G,int(*Visit)(int v,ALGraph G)){
int v;
VisitFunc=Visit;
for(v=0;v<G.vexnum;++v)
visited[v]=false;
for(v=0;v<G.vexnum;++v){
if(!visited[v])
DFS(G,v);
}
}
//v函数
int Printelem(int v,ALGraph G){
printf("%c ",G.vertices[v].data);
}
//prim算法
typedef struct{
char adjvex;
int lowcost;
}CLOSEDGE,closedge[MAX_VERTEX_NUM];
int minimum(closedge SZ,MGraph G)
{
int i=0,j,k,min;
while(SZ[i].lowcost!=0)
i++;
min=SZ[i].lowcost;
k=i;
for(j=i+1;j<G.vexnum;j++)
if(SZ[j].lowcost>0)
if(min>SZ[j].lowcost)
{
min=SZ[j].lowcost;
k=j;
}
return k;
}
int MiniSpanTree_PRIM(MGraph G,int u){
int k,j,i;
closedge T;
k=LocateVex(G,u);
for(j=0;j<G.vexnum;++j){
if(j!=k)
{T[j].adjvex=u;
T[j].lowcost=G.arcs[k][j].adj;
}
}
T[k].lowcost=0;
for(i=1;i<G.vexnum;++i){
k=minimum(T,G);
printf("(%d-%d)",T[k].adjvex,G.vexs[k]);
T[k].lowcost=0;
for(j=0;j<G.vexnum;++j){
if(G.arcs[k][j].adj<T[j].lowcost)
{
T[j].adjvex=G.vexs[k];
T[j].lowcost=G.arcs[k][j].adj;
}
}
}
}
int main(){
int t,i;
do{
printf("请选择进行的操作:\n1.构建图 2.遍历 3.构建最小生成树\n");
scanf("%d",&i);
switch(i){
case 1:printf("请选择存储结构:1.邻接矩阵 2.邻接表\n");
scanf("%d",&t);
if(t==1){
MGraph G;
CreateGraph(G);
}
else {
ALGraph G;
CreateGraph2(G);
}
printf("\n");
break;
case 2:printf("请先构建图\n");
ALGraph K;
CreateGraph2(K);
DFSTraverse(K,Printelem);
printf("\n");
break;
case 3:printf("请先构建无向网\n");
MGraph M;
char o;
CreateUDN(M);
printf("请输入最小生成树的起点\n");
scanf("%d",&o);
printf("\n");
MiniSpanTree_PRIM(M,o);
printf("\n");
break;
}
}while(i);
}