-
Notifications
You must be signed in to change notification settings - Fork 0
/
TrabalhoFinalCompleto.c
318 lines (267 loc) · 9.83 KB
/
TrabalhoFinalCompleto.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
typedef struct{
float x;
float y;
} Ponto;
float calcularDistancia(Ponto *PtrPlano, float **PtrDistancias,int qtdCidade){
int i,j;
float distancia;
//percorrer as linhas da matriz distancia
for(i=0;i<qtdCidade;i++){
//percorrer as colunas da matriz distância
for(j=0;j<qtdCidade;j++){
//se linha e coluna forem iguais, quer dizer que calculará a distância para ela mesma
if(i==j){
distancia = 0;
}
else{
//verificar que o valor da coluna da matriz distancia equivale a linha da cidade que estamos calculando
//a distância, ou seja, o valor de x2 e y2 e o valor da linha da matriz distancia equivale a cidade que estamos verificando a
//distância, ou seja, a x1 e y1
distancia = sqrt(pow(PtrPlano[j].x - PtrPlano[i].x,2) + pow(PtrPlano[j].y-PtrPlano[i].y,2));
}
PtrDistancias[i][j] = distancia;
}
}
}
int calcularRota(int qtdCidade,float **PtrDistancias,int cidadeAtual, int *cidadesVisitadas, float *distancias, FILE *rota){
static int pos=0;
static int quebrarlinha = 1;
//utilizando uma maneira de calcular a menor distância sem um número pré-definido para evitar futuros problemas
int i,prxCidade;
float menorDistancia;
//pegar o primeiro valor diferente da cidade de onde está
// e que a cidade ainda não tenha sido visitada para usar como a menor distância inicial
for(i=0;i<qtdCidade;i++){
if(cidadeAtual != i && cidadesVisitadas[i]!=1) {
menorDistancia = PtrDistancias[cidadeAtual][i];
prxCidade = i;
break;
}
}
//escolhendo a cidade com a menor distância ainda não visitada
for(i;i<qtdCidade;i++){
//condicional caso a distancia pega anteriormente seja a menor do vetor
if(cidadeAtual != i && PtrDistancias[cidadeAtual][i]<menorDistancia && cidadesVisitadas[i]!=1){
menorDistancia = PtrDistancias[cidadeAtual][i];
prxCidade = i;
}
}
//adcionando ao vetor a distância gasta de uma cidade a outra
distancias[pos] = menorDistancia;
pos++;
//organizando o vetor das cidades já visitadas
cidadesVisitadas[prxCidade] = 1;
//mostrando na tela a ordem das cidades a serem percorridas
printf("%d --> ", prxCidade+1);
if(quebrarlinha%10==0){
fprintf(rota,"%d -> \n", prxCidade+1);
} else fprintf(rota,"%d -> ", prxCidade+1);
quebrarlinha++;
return prxCidade;
};
float calcularDistanciaTotal(float *distancias,int qtdCidade){
if(qtdCidade<0) return 0;
return distancias[qtdCidade] + calcularDistanciaTotal(distancias, qtdCidade-1);
}
// função atoi não estava atendendo o requisitado então foi criada uma função para que o problema fosse resolvido
int myAtoi(char s[]){
int i=0,pos=0,constante=1;
int *nums = NULL;
// verificar quando o array está com um caracter que é reconhecido como número na tabela ASCII
for(i;i<strlen(s);i++){
if(s[i]>47 && s[i]<58){
break;
}
}
for(i;i<strlen(s);i++){
// verificar se na posição anterior existe o sinal de negativo
if(s[i-1]=='-'){
constante=-1;
}
// quando chega em um espaço quer dizer que aquele número acabou
if(s[i]==' ') break;
// guardar os números separados dentro de um vetor
if(s[i]>47 && s[i]<58){
nums = realloc(nums, sizeof(int));
nums[pos] = 0;
int num = s[i] - '0';
nums[pos] = num;
pos++;
}
}
int tam = pos-1;
int valor=0;
int auxTam = tam+1;
// realizar a soma desses números com as casas decimais que as representam
for(i=0;i<auxTam;i++){
valor += pow(10,tam)*nums[i];
tam -= 1;
}
return valor*constante;
}
int main(){
// variáveis que serão utilizadas durante o código
int *PtrCidades = NULL, cidadeAtual, cidadePartida, concluido = 0;
float **PtrDistancias = NULL;
int i,j,qtdCidade,id;
char NomeArquivo[100];
char NomeArqRota[100] = "Rota - ";
// verificar de qual arquivo será lido os pontos
printf("Nome do arquivo a ser lido: ");
scanf("%s", NomeArquivo);
fflush(stdin);
// abrir arquivos de pontos
FILE *arq = NULL;
arq = fopen(NomeArquivo, "r");
if(arq==NULL) {
printf("Arquivo de pontos não encontrado\n");
return -2;
};
// encontrar qual a cidade que o arquivo representa
int contador = 0, verificador = 1;
char NomeCidade[100];
char cidade[100];
// variáveis descartáveis para armazenar na linha que é padronizada e evitar ficar comparando através de caracteres
char nomeDescart1[100],nomeDescart2[100], nomeDescart3[100], nomeDescart4[100], nomeDescart5[100];
while(fgets(NomeCidade, 100, arq)!=NULL){
contador++;
// verificar na linha 2 do arquivo
if(contador==1){
fscanf(arq,"%s %s %s %s %s %s", &nomeDescart1,&nomeDescart2,&nomeDescart3,&nomeDescart4,&nomeDescart5,&cidade);
break;
}
}
// Salvar arquivo de rota junto com o nome da cidade para diferenciar dos demais arquivos lidos e poder salvar todos eles separadamente
int pos = 7;
for(i=0;i<strlen(cidade);i++){
NomeArqRota[pos] = cidade[i];
pos++;
}
// adcionando a extensão txt no nome do arquivo
char txt[4] = ".txt";
for(i=0;i<4;i++){
NomeArqRota[pos] = txt[i];
pos++;
}
// arquivo aonde será armazenada a rota
FILE *rota = NULL;
rota = fopen(NomeArqRota, "w");
if(rota==NULL) {
printf("Arquivo de rota não encontrado\n");
return -2;
};
printf("Cidade: %s\n", cidade);
fprintf(rota, "Cidade %s\n", cidade);
fclose(arq);
// enocntrar qual a dimensão do arquivo
contador=0;
verificador = 1;
char dimensao[100];
arq = fopen(NomeArquivo,"r");
while (fgets(dimensao, 100,arq)!=NULL){
contador++;
for(i=0;i<strlen(dimensao);i++){
// arquivo segue padrão que não se repete esta sequência para qualquer outro dado presente nele
// então aquela string que se inicia com D e logo após vem o I é a linha de dimensão
if(dimensao[0]=='D' && dimensao[1]=='I'){
qtdCidade=myAtoi(dimensao);
verificador = 0;
break;
}
}
// parar leitura assim que encontrado tamanho do arquivo
if(verificador==0) break;
}
fclose(arq);
printf("Quantidade de cidades: %d\n", qtdCidade);
// deixando propício a quantidade de cidades que irá receber
PtrCidades = malloc(sizeof(int) * qtdCidade);
if(PtrCidades == NULL) return -1;
//iniciando os vetores com 0 para evitar possíveis lixos de memória
for(i=0;i<qtdCidade;i++){
PtrCidades[i] = 0;
}
PtrDistancias = (float**)malloc(sizeof(int*)*qtdCidade);
for(i=0;i<qtdCidade;i++){
PtrDistancias[i] = (float*)malloc(sizeof(int)*qtdCidade);
}
if(PtrDistancias == NULL) {
printf("Distancias não adcionadas\n");
return -1;
};
for(i=0;i<qtdCidade;i++){
for(j=0;j<qtdCidade;j++){
PtrDistancias[i][j] = 0;
}
}
//Finalizando de preencher as matrizes e vetores com o valor 0
//armazenando os pontos do plano
Ponto *PtrLocPlano;
PtrLocPlano = malloc(sizeof(Ponto));
// verficar os pontos
int contador2=0;
i = 0;
arq = fopen(NomeArquivo, "r");
if(arq==NULL) {
printf("Arquivo não encontrado\n");
return -2;
};
// Utilizando uma lógica para que se considere a leitura duas linhas após a linha de dimensão ser lida
// como os arquivos seguem um certo padrão essas linhas de pontos sempre estarão duas linhas a mais que a de
// dimensão.
while(!feof(arq)){
// ler até aonde se inicia os pontos
contador2++;
fgets(dimensao, 100, arq);
if(contador2>contador+1){
// quando encontrado a linha de inicio ler e armazenar os pontos
PtrLocPlano = realloc(PtrLocPlano, (i+1)*sizeof(Ponto));
fscanf(arq,"%d %f %f",&id, &PtrLocPlano[i].x, &PtrLocPlano[i].y);
fflush(stdin);
i++;
}
}
fclose(arq);
// vetor para ser armazenado as distancias percorridas e somada ao final
float *distancias;
distancias = malloc(sizeof(float) * qtdCidade);
//transformando os pontos do plano em distâncias entre um ponto e outro
calcularDistancia(PtrLocPlano,PtrDistancias,qtdCidade);
// Colocando como cidade de partida a cidade 1, supondo que seja dela que comece a jornada de entregas
cidadeAtual = 0;
cidadePartida = 0;
//adcionando no vetor de cidades visitadas a cidade de partida
PtrCidades[cidadeAtual] = 1;
printf("%d -> ", cidadeAtual+1);
fprintf(rota,"%d -> ", cidadeAtual+1);
while(concluido !=1){
//verificando se já se foi passado por todas as cidades
for(i=0;i<qtdCidade;i++){
if(PtrCidades[i]==0) break;
}
//se já tiver sido passada por todas as cidades voltará para cidade de partida
if(i==qtdCidade) {
concluido =1;
break;
}
//calcular a rota pela função
cidadeAtual = calcularRota(qtdCidade,PtrDistancias,cidadeAtual,PtrCidades, distancias, rota);
}
//Retornando a cidade de partida
printf("%d\n", cidadePartida + 1);
fprintf(rota, "%d\n", cidadePartida+1);
// adcionando a distancia da ultima cidade para a cidade de partida
distancias[qtdCidade] = PtrDistancias[cidadeAtual][cidadePartida];
// chamar a soma da distancia a partir da função para calcular a distancia total gasta
float distanciafunc;
distanciafunc = calcularDistanciaTotal(distancias, qtdCidade);
// printando saida da distancia e confirmando ao usuário que o arquivo foi criado
printf("Distancia Total Percorrida: %.2fkm\n", distanciafunc);
printf("Arquivo com a rota a ser percorrida foi criado com sucesso!!!");
fprintf(rota,"Distancia Total Percorrida: %.2fkm", distanciafunc);
return 0;
}