[디에스 과제] 데이터 구조론 - 프로그래밍 레포트 Programming Report -

소개글

[디에스 과제] 데이터 구조론 - 프로그래밍 레포트 Programming Report -에 대한 보고서 자료입니다.

목차

1. 프로그램 실행방법
2. 실행창이미지
3. 검토 및 소감

본문내용

CES], int distance[], int n, short int found[])
{/*distance[i] : 정점 v에서 i로의 최단 경로, 최단 경로가 발견되면 found[i] = 1*/
int i, u, w;
node_pointer ptr, temp, next;
for(i = 0; i < n; i++) {
found[i] = FALSE;
distance[i] = cost[v][i];
}
found[v] = TRUE;
distance[v] = 0;
for(i = 0; i < n-2; i++) {
u = choose(distance, n ,found);
found[u] = TRUE;
if(!pred[u] && !(distance[u] == 1000)) {/*발견되지 않은 정점*/
temp = (node_pointer)malloc(sizeof(node));
temp->vertex = v;
temp->link = NULL;
pred[u] = temp;
}
for(w = 0; w < n; w++)
if(!found[w]) {
if(distance[u] + cost[u][w] < distance[w]) {
distance[w] = distance[u] + cost[u][w];
/*기존의 최단 경로에서 다시 최단경로로 업데이트 되었을때 */
if(pred[w]){
free_memory(&pred[w]);/*기존의 경로 삭제*/
}/*새로 발견된 경로들을 정점에 입력*/
for(ptr = pred[u]; ptr; ptr = ptr->link) {
temp = (node_pointer)malloc(sizeof(node));
temp->vertex = ptr->vertex;
temp->link = NULL;
if(!pred[w])
pred[w] = next = temp;
else {
next->link = temp;
next = next->link;
}
}
/*마지막 정점 입력*/
temp =(node_pointer)malloc(sizeof(struct node));
temp->vertex = u;
temp->link = NULL;
next->link = temp;}
}
}
}
2. 실행창이미지
각 점의 경로가 나오고 그 경로의 길이를 출력한다
3. 검토 및 소감
ShortestPath 함수를 통해 배열 pred를 통해 시작 노드에서 각 노드로의 최단 경로를 구해서 시작 정점에서 각 정점으로의 경로를 출력하는 것을 구현해보았다. 지금까지 최단경로가 발견된 정점들의 집합인 s에 없는 정점 w 에 대하여 distance[w] 는 오직 S 안의 정점들만을 통과하여 w 에 도달하는 최단 경로의 거리를 가지게 하여 이러한 최단 경로의 길이의 결정하여 각 노드로의 경로가 출력된다. 이것은 예전의 미로경로를 찾는 프로그램과 상당히 유사하다는 것을 알 수 있었다. 다만 pred 배열에 대한 개념이 이해되지 않았고 이를 구현하는 데에 상당히 힘들었다. 그리고 이러한 프로그램을 응용해서 세계 나라의 경로와 운항정보에 큰 도움을 줄 수 있지 않을가 생각해보았다.

키워드

data structure,   프로그램 실행방법,   소스,   프로그램,   데이터 구조론,   데이터,   구조론,   distance,   node,   경로,   pred