プログラマ専用SNS ミクプラ

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<malloc.h>
#include<string.h>
#include<limits.h>
#define VERTEX_NUM 100000
struct AVL_Node *AVL_Tree;
struct Vertex{
char name[100];
int d; //出発点からの距離
int is_visited;
struct Edgelist *edge_head;
struct Vertex *shortest_path;
};
struct Edgelist {
int length; //辺の長さ
struct Vertex *to;
struct Edgelist *next;
};


int Max(int lh, int rh){
int Max;
Max = lh;
if(lh <= rh)Max = rh;
return Max;
}

void initialize_vertex(struct Vertex *v, char *name){
strcpy(v->name,name);
v->d=INT_MAX/2; //int型の最大値
v->edge_head=NULL;
v->shortest_path=NULL;
v->is_visited=0;
}
void connect_dir(struct Vertex *from, struct Vertex *to, int length){
struct Edgelist *new_edge;
new_edge=(struct Edgelist *)malloc(sizeof(struct Edgelist));
new_edge->to = to;
new_edge->next= from->edge_head;
from->edge_head=new_edge;
new_edge->length=length;
}
struct AVL_Node{
struct Vertex *v; // 頂点をおぼえる
struct AVL_Node *left;
struct AVL_Node *right;
int h;
};
struct AVL_Node* new_AVL_Node(struct Vertex *v){
struct AVL_Node *n;
n=(struct AVL_Node*)malloc(sizeof(struct AVL_Node));
n->v=v;
n->h=0; n->left=NULL; n->right=NULL;
return n;
}
struct AVL_Node *new_AVL_Node(struct Vertex *v);
struct AVL_Node *insert_v(struct AVL_Node *p, struct Vertex *v);
struct AVL_Node *insert_n(struct AVL_Node *p, struct AVL_Node*x);
struct AVL_Node *rotate(struct AVL_Node *p);
int compare_vertex(struct Vertex *a, struct Vertex *b);
void set_height(struct AVL_Node *p);
struct AVL_Node *find_min(struct AVL_Node *T_root);
struct AVL_Node *remove_min(struct AVL_Node *T_root);
struct AVL_Node *delete_v(struct AVL_Node *T_root, struct Vertex *v);
int compare_vertex(struct Vertex *a, struct Vertex *b){
if(a->d< b->d){
return -1;
} else if( a->d > b->d){
return 1;
} else {
return strcmp(a->name,b->name);
}
}

void set_height(struct AVL_Node *p){
if(p==NULL){
return ;
} else if(p->left==NULL && p->right==NULL){
p->h=0;
} else if(p->left==NULL && p->right!=NULL){
p->h=p->right->h+1;
} else if(p->left!=NULL && p->right==NULL){
p->h=p->left->h+1;
} else {
p->h=Max(p->left->h,p->right->h)+1;
}
}
//*関数maxは自分で作る*//
struct AVL_Node *
insert_n(struct AVL_Node *p, struct AVL_Node *x){
if(x==NULL){ return p; }
if(compare_vertex(x->v,p->v)<0){
if(p->left==NULL){ p->left=x; }
else { p->left = insert_n(p->left, x); }
} else if(compare_vertex(x->v,p->v)>0){
if(p->right==NULL){ p->right=x; }
else { p->right = insert_n(p->right,x); }
} else{
return p;
}
set_height(p);
return rotate(p); /* 回転による根の入替に対応*/
}

struct AVL_Node* insert_v(struct AVL_Node *p, struct Vertex *v){
struct AVL_Node *n= new_AVL_Node(v);
if(p!=NULL){ return insert_n(p,n); }
else { return n; }
}

struct AVL_Node* rotate(struct AVL_Node *p){
int lh=-1, rh=-1, llh=-1,lrh=-1, rlh=-1,rrh=-1;
if(p->left!=NULL){
lh=p->left->h;
if(p->left->left!=NULL){ llh=p->left->left->h;}
if(p->left->right!=NULL){lrh=p->left->right->h;}
}
if(p->right!=NULL){
rh=p->right->h;
if(p->right->left!=NULL){ rlh=p->right->left->h;}
if(p->right->right!=NULL){ rrh=p->right->right->h;}
}
if(lh-rh<=1 && rh-lh<=1){ return p; }
if(lh < rh){ /* 右の子が高い*/
struct AVL_Node *A=p, *B=p->right;
struct AVL_Node *Y=B->left;
if(rlh<rrh){ /*右の右の孫が高い：１重回転*/
B->left=A; A->right=Y;
set_height(A); set_height(B);
return B;
} else {/*右の左の孫が高い：２重回転 */
struct AVL_Node *C=Y, *Y1=C->left, *Y2=C->right;
C->left=A; C->right=B; A->right=Y1; B->left=Y2;
set_height(A); set_height(B); set_height(C);
return C;
}
}else { /*左の子が高い*/
struct AVL_Node *A=p, *B=p->left;
struct AVL_Node *Y=B->right;
if(llh > lrh){/* 左の左の孫が高い：１重回転*/
B->right=A; A->left=Y;
set_height(A); set_height(B);
return B;
} else {/*左の右の孫が高い：２重回転*/
struct AVL_Node *C=Y, *Y1=C->left, *Y2=C->right;
C->left=B; C->right=A; B->right= Y1; A->left=Y2;
set_height(A); set_height(B); set_height(C);
return C;
}
}
}


struct AVL_Node *find_min(struct AVL_Node *p){
struct AVL_Node *q;
if(p==NULL){
return NULL;
}
for(q=p;q->left!=NULL;q=q->left){
; /* なにもしない*/
}
/* qに左の子が存在しないのでqは最小値 */
return q;
}

struct AVL_Node *remove_min(struct AVL_Node *p){
if(p==NULL){
return NULL;
} else if(p->left==NULL) {
return p->right;
} else if(p->left->left==NULL){
/*左の左の孫が無いならば、pは最小値の親*/
p->left=p->left->right;
set_height(p);
return rotate(p);
} else {
p->left=remove_min(p->left);
set_height(p);
return rotate(p);
}
}

struct AVL_Node *delete_v(struct AVL_Node *p, struct Vertex *v){
struct AVL_Node *min_node;
if(p==NULL || v==NULL){
return NULL;
}
if(compare_vertex(v,p->v)<0){
p->left=delete_v(p->left,v);
set_height(p);
return rotate(p);
} else if(compare_vertex(v,p->v)>0){
p->right=delete_v(p->right,v);
set_height(p);
return rotate(p);
}

if(p->right==NULL){
struct AVL_Node *left= p->left;
free(p);
return rotate(left);
} else {
min_node=find_min(p->right);
p->right=remove_min(p->right);
min_node->left=p->left;
min_node->right=p->right;
free(p);
set_height(min_node);
return rotate(min_node);

}}

void read_file(char *filepath,struct Vertex vertex[]){
FILE *fp;
fp=fopen(filepath,"rt");
if(fp==NULL){
printf("ファイルオープン失敗\n%s\n",filepath); return;
}
while(!feof(fp)){
char buf[1000]; int from, to, length;
fgets(buf,1000,fp);
if(buf[0]!='a') continue;
sscanf(buf,"%c %d %d %d",&buf[0], &from, &to, &length);
connect_dir(&vertex[from],&vertex[to],length);
}
fclose(fp);
}

struct Vertex* extract_nearest_AVL();
void add_all_vertices_to_AVL_Tree(struct Vertex *s);
void Dijkstra_fast(struct Vertex *s);


void add_all_vertices_to_AVL_Tree(struct Vertex *s){
struct Edgelist *e;
s->is_visited=1;
AVL_Tree=insert_v(AVL_Tree,s);
for(e=s->edge_head; e!=NULL; e=e->next){
if(e->to->is_visited==0){
add_all_vertices_to_AVL_Tree(e->to);
}
}
return;
}

struct Vertex* extract_nearest_AVL(){
struct AVL_Node *min_node;
struct Vertex *min_vertex;

min_node=find_min(AVL_Tree);
min_vertex=min_node->v;
AVL_Tree=delete_v(AVL_Tree,min_vertex); return min_vertex;
}

void Dijkstra_fast(struct Vertex *s){
struct Edgelist *e; struct Vertex *u;
s->d=0;
add_all_vertices_to_AVL_Tree(s);
while(AVL_Tree!=NULL){
u=extract_nearest_AVL();
for( e= u->edge_head; e!=NULL; e=e->next){
if(e->to->d > u->d + e->length){
AVL_Tree=delete_v(AVL_Tree,e->to);
e->to->d=u->d+e->length;
e->to->shortest_path=u;
AVL_Tree=insert_v(AVL_Tree,e->to);
}
}
}
}

int main(void ){
struct Vertex *p;
char filename[]="C:\\Users\\G\\Desktop\\USA-road-d.NY.gr.txt";
int i,j;
time_t start,end;
struct Vertex *vertex_array=
(struct Vertex *)malloc(sizeof(struct Vertex)*VERTEX_NUM);
printf("初期化中...");
for(i=0;i<VERTEX_NUM;i++){
char name[100];
sprintf(name,"V%d",i);
initialize_vertex(&vertex_array,name);
}
printf("初期化完了\n");
printf("地図読み込み中...");

read_file(filename,vertex_array);
printf("地図読み込み完了\n");

AVL_Tree=NULL;
start=clock();
Dijkstra_fast(&vertex_array[999]);
end=clock();
for(p=&vertex_array[9999];p!=NULL;p=p->shortest_path){
printf("%s<-- ", p->name);
}
printf("最短路の長さは%d\n", vertex_array[9999].d);
printf("%5.4f秒でした\n",(end-start)/(double)CLOCKS_PER_SEC);
getchar(); return 0;


}



Ｂｏｒｌａｎｄです

exeは動作を停止しましたと出て動きません

どうすれば動きますか

とりあえず、コードを提示するときはBBcodeを有効にした状態でcodeタグで囲み、
かつ適切なインデントをしていただけると、見やすくて助かります。

USA-road-d.NY.grを入力として用いて実行したところ、
41行目のでアクセス違反が出たので、
おそらく木の回転にバグがあるのではないかと思います。
fromの値がおかしいかもしれません。
VERTEX_NUMの値を10倍にしたらここでのアクセス違反は出なくなりました。

びあでゅｆ さんが書きました:どうすれば動きますか

デバッグをしましょう。

まずはVERTEX_NUMの値が入力の頂点数より少なかったため、確保したメモリ領域以外にアクセスしてしまったようです。
次の問題は、 add_all_vertices_to_AVL_Tree関数での再帰が深すぎることのようです。

gcc 4.8.1を用いてスタックサイズ100MBでコンパイルしたところ、次のアクセス違反が出ました。
115行目で、pがNULLになっていました。

rotate関数の変数宣言の直後(115行目)に という行を入れると、アクセス違反が怒らずに結果が出力されました。
結果が正しいかは検証していません。

実行結果(YUKI.N>はプロンプトを表す) ※スタックサイズを10MBに変更していますが、仕様です。1MBではアクセス違反が発生しました。