Prim.c - Revizia istoricului

Rhobincu la 10 mai 2014 08:21

2014-05-10T08:21:16Z

Rhobincu la 10 mai 2014 08:20

2014-05-10T08:20:48Z

Rhobincu: Pagină nouă: #include #include #include #define IN_FILE "matrix.in" #define MAX_INT 0x7FFFFFFF typedef struct { int node_count; ...

2014-05-10T08:18:46Z

Pagină nouă: <syntaxhighlight lang="c"> #include <stdio.h> #include <stdlib.h> #include <string.h> #define IN_FILE "matrix.in" #define MAX_INT 0x7FFFFFFF typedef struct { int node_count; ...

Pagină nouă

<syntaxhighlight lang="c">
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define IN_FILE "matrix.in"

#define MAX_INT 0x7FFFFFFF

typedef struct {
int node_count;
unsigned char ** matrix;
} graph;

void dump_matrix(graph * my_graph){
int i, j;
for(i=0; i<my_graph->node_count; i++){
for(j=0; j<my_graph->node_count; j++){
printf("%d ", my_graph->matrix[i][j]);
}
printf("\n");
}
}

graph* read_matrix(){

FILE* input_file = fopen(IN_FILE, "r");
if(input_file == NULL){
printf("Error opening input file!\n");
exit(0);
}

graph * new_graph = (graph*)malloc(sizeof(graph));

fscanf(input_file, "%d", &new_graph->node_count);
printf("Node count is %d\n", new_graph->node_count);

new_graph->matrix = (unsigned char **)malloc(sizeof(unsigned char *) * new_graph->node_count);
int i, j;
for(i=0; i<new_graph->node_count; i++){
new_graph->matrix[i] = (unsigned char *)malloc(sizeof(unsigned char) * new_graph->node_count);
}

for(i=0; i<new_graph->node_count; i++){
for(j=0; j<new_graph->node_count; j++){
fscanf(input_file, "%d", &(new_graph->matrix[i][j]));
}
}

return new_graph;
}

graph * prim(graph * my_graph){
graph * mst = (graph*)malloc(sizeof(graph));
mst->node_count = my_graph->node_count;

mst->matrix = (unsigned char **)malloc(sizeof(unsigned char *) * mst->node_count);
int i, j;
for(i=0; i<mst->node_count; i++){
mst->matrix[i] = (unsigned char *)malloc(sizeof(unsigned char) * mst->node_count);
memset(mst->matrix[i], 0, sizeof(unsigned char) * mst->node_count);
}

int *visited_nodes = (int*)malloc(mst->node_count * sizeof(int));
memset(visited_nodes, 0, mst->node_count * sizeof(int));
visited_nodes[0] = 1;
int visited_node_count = 1;
while(visited_node_count < mst->node_count){
int i, j;
int source_visited_node = 0;
int next_visited_node = 0;
int shortest_edge = MAX_INT;
for(i=0; i<my_graph->node_count - 1; i++){
for(j=i+1; j<my_graph->node_count; j++){
if(my_graph->matrix[i][j] < shortest_edge){
if(visited_nodes[i] == 1 && visited_nodes[j] == 0){
next_visited_node = j;
source_visited_node = i;
shortest_edge = my_graph->matrix[i][j];
}
if(visited_nodes[j] == 1 && visited_nodes[i] == 0){
next_visited_node = i;
source_visited_node = j;
shortest_edge = my_graph->matrix[i][j];
}
}
}
}

mst->matrix[next_visited_node][source_visited_node] = shortest_edge;
mst->matrix[source_visited_node][next_visited_node] = shortest_edge;
visited_nodes[next_visited_node] = 1;
visited_node_count++;
}

return mst;
}

int main(){
graph * my_graph;

my_graph = read_matrix();

graph * mst_my_graph = prim(my_graph);

dump_matrix(mst_my_graph);

return 0;
}
</syntaxhighlight>

@@ Linia 1: / Linia 1: @@
 #include <stdio.h>
 #include <stdlib.h>
@@ Linia 106: / Linia 107: @@
      return 0;
+}

@@ Linia 1: / Linia 1: @@
 #include <stdio.h>
 #include <stdlib.h>
@@ Linia 9: / Linia 8: @@
 typedef struct {
      int node_count;
-     unsigned char ** matrix;
+     int ** matrix;
 } graph;
@@ Linia 35: / Linia 34: @@
      printf("Node count is %d\n", new_graph->node_count);
-     new_graph->matrix = (unsigned char **)malloc(sizeof(unsigned char *) * new_graph->node_count);
+     new_graph->matrix = (int **)malloc(sizeof(int *) * new_graph->node_count);
      int i, j;
      for(i=0; i<new_graph->node_count; i++){
-         new_graph->matrix[i] = (unsigned char *)malloc(sizeof(unsigned char) * new_graph->node_count);
+         new_graph->matrix[i] = (int *)malloc(sizeof(int) * new_graph->node_count);
+     }
@@ Linia 54: / Linia 53: @@
      mst->node_count = my_graph->node_count;
-     mst->matrix = (unsigned char **)malloc(sizeof(unsigned char *) * mst->node_count);
+     mst->matrix = (int **)malloc(sizeof(int *) * mst->node_count);
      int i, j;
      for(i=0; i<mst->node_count; i++){
-         mst->matrix[i] = (unsigned char *)malloc(sizeof(unsigned char) * mst->node_count);
+         mst->matrix[i] = (unsigned char *)malloc(sizeof(int) * mst->node_count);
-         memset(mst->matrix[i], 0, sizeof(unsigned char) * mst->node_count);
+         memset(mst->matrix[i], 0, sizeof(int) * mst->node_count);
+     }
@@ Linia 107: / Linia 106: @@
      return 0;
+}