[자작 예제] 유향선분 구조체를 저장하는 리스트

https://cascade.tistory.com/70

[열혈자료구조] 3강. 연결 리스트(Linked List) 1 - (2)

 
앞서 열혈자료구조 교재에서 배열로 정의한 리스트를 구현하고, Point 라는 구조체(2차원 좌표평면 상의 점)를 정의하여 리스트 안에 이 구조체를 저장할 수 있도록 하는 코드를 공부하였다. 본 포스팅에서는, 두 개의 Point (시작점, 끝점)을 변수로 가지는 유향선분(Directed Line Segment) 구조체를 정의하고, 이를 저장하는 리스트를 만들어 볼 것이다.
 
이 작업을 하는 데 헤더 파일과 함수 구현까지 다 해놓고 컴파일하다 문제가 생겨서 모든 게 싹 날아가버렸다. VS Code 사용할 때 꼭 ctrl+s를 생활화하자..... (연습 한번 더 했다고 좋게좋게 생각하는 중)
 

• 2차원 좌표평면에서의 점에 대한 구현인 point.h, point.c 
• 리스트에 대한 구현인 ArrayList.h, ArrayList.c

위 두 가지는 교재에서 이미 구현되어 있고 열혈자료구조 홈페이지(https://blog.naver.com/oedu/223011150597) 에서 다운받을 수 있다. 내가 직접 구현한 것은 아래 두 가지+메인함수이다.

dls.h

0.00MB

dls.c

0.00MB

dls_main.c

0.00MB

 

---

유향선분(Directed Line Segment, DLS)이란?

 

방향을 가진 선분

 
선분은 서로 다른 두 점으로 정의된다. 유향선분은 방향을 가지는 선분으로, 두 개의 점을 시작과 끝으로 구분해 주기만 하면 된다. 시작점의 위치를 고려하지 않는 벡터와는 조금 다른 개념이지만, 유향선분을 벡터로 생각하여 내적을 정의할 수 있다. 본 구현에서는 아래 6개의 유향선분을 리스트에 저장할 것이다.
 

헤더 파일(.h)

유향선분에는 어떤 연산이 필요할까? 이 자료형을 구조체로 정의하기 전에 어떤 성질이 필요한지 구상해 보았다.

정의: 두 개의 Point(시작 점, 끝 점)를 받아, 서로 다른 점이라면 유향성분을 정의한다. Point의 주소 값을 받아 와서 비교 연산 후 DLS 구조를 새로운 메모리에 저장한다.
출력: DLS의 주소를 받아 와 어떤 점으로 구성되어 있는지 출력한다.
길이 계산: DLS의 주소를 받아 와 길이를 float으로 도출한다.
내적: 두 개의 DLS의 주소를 받아 와 내적한 결과를 int로 도출한다.

 
이를 헤더 파일에 아래와 같이 작성하였다.

#ifndef __DLS_H__
#define __DLS_H__
#include "Point.h"

typedef struct _directed_line_segment
{
	Point * start_pt;
	Point * end_pt;
} DLS;


void Set_DLS_Pos(DLS * ppos, Point * pos1, Point * pos2);
void Show_DLS_Pos(DLS * ppos);
float DLS_Length(DLS * ppos);
int DLS_inner_product(DLS * pp1, DLS * pp2);

#endif

 

함수의 구현

DLS의 정의: Set_DLS_Pos

 
Point.c에서 정의된 비교 연산 PointComp를 통해 들어온 두 점이 다르다는 것을 확인하고, 포인터 변수인 pos1과 pos2를 start_pt, end_pt에 저장한다.

void Set_DLS_Pos(DLS * ppos, Point * pos1, Point * pos2)
{
    if (PointComp(pos1, pos2)==0){
        printf("cannot define DLS with same points");
        return;
    }
    ppos->start_pt = pos1;
    ppos->end_pt = pos2;
    
}

 

DLS의 출력: Show_DLS_Pos

 
DLS의 출력은 시작점과 끝점을 아래 형식으로 출력하는 것으로 하였다.

void Show_DLS_Pos(DLS * ppos)
{
    printf("--------DLS data--------\nstarting point : ");
    ShowPointPos(ppos->start_pt);
    printf("ending point : ");
    ShowPointPos(ppos->end_pt);
    printf("------------------------\n");
}

 

DLS의 길이 계산: DLS_Length

 
start_pt와 end_pt에서 x, y좌표를 받아 와 각각의 정수로 저장하고, math.h에서 가져온 연산으로 피타고라스 정리를 적용하여 거리를 float로 리턴하는 함수를 만들었다.

float DLS_Length(DLS * ppos){
    int x1 = (ppos->start_pt->xpos);
    int y1 = (ppos->start_pt->ypos);
    int x2 = (ppos->end_pt->xpos);
    int y2 = (ppos->end_pt->ypos);

    return sqrt(pow(x1-x2, 2)+pow(y1-y2, 2));
}

 

두 DLS 사이의 내적: DLS_inner_product

 
두 DLS의 주소를 받아 와, start_pt를 원점으로 평행이동시켜 end_pt를 elementwise하게 곱하면 내적이므로 아래와 같이 정의하였다.

int DLS_inner_product(DLS * pp1, DLS * pp2){
    int delta_x1 = (pp1->end_pt->xpos)-(pp1->start_pt->xpos);
    int delta_y1 = (pp1->end_pt->ypos)-(pp1->start_pt->ypos);
    int delta_x2 = (pp2->end_pt->xpos)-(pp2->start_pt->xpos);
    int delta_y2 = (pp2->end_pt->ypos)-(pp2->start_pt->ypos);

    return delta_x1*delta_x2 + delta_y1*delta_y2;
}

 

메인 함수

앞서 살펴보았던 6개의 유향선분을 저장하는 리스트를 만들기 위해, 세 점 (0,0), (1,4), (4,1)을 좌표로 하는 Point 구조체를 정의하고 3P2 번의 조합을 하여 LInsert로 리스트에 넣어 주었다. 이때 리스트에는 DLS의 주소값이 저장(Call by Reference)된다. 또한 이 DLS들을 LFirst로 시작하여 LNext로 하나씩 옮겨 가며 출력하고 길이를 계산할 수 있다.
 

 
리스트에서 제거되는 조건은 빨간 선(y=x)과 수직인 것이다. 이를 구현하기 위해 위에서 정의한 내적 함수인 DLS_inner_product를 사용했다. (0,0)~(1,1)을 연결하는 DLS를 새로 정의하고, 이와 내적하여 0이 나오는 것을 LRemove로 제거하였다.
 

#include <stdio.h>
#include <stdlib.h>
#include "ArrayList.h"
#include "Point.h"
#include "dls.h"

int main(){

    List list;
    DLS * ppos;
    ListInit(&list);
    
    //define Point 1
    Point * ppoint1;
    ppoint1 = (Point *) malloc (sizeof(Point));
    SetPointPos(ppoint1, 0, 0);
    
    //define Point 2
    Point * ppoint2;
    ppoint2 = (Point *) malloc (sizeof(Point));
    SetPointPos(ppoint2, 4, 1);
    
    //define Point 3
    Point * ppoint3;
    ppoint3 = (Point *) malloc (sizeof(Point));
    SetPointPos(ppoint3, 1, 4);

    //define Point 4 and comparing DLS
    Point * ppoint4;
    ppoint4 = (Point *) malloc (sizeof(Point));
    SetPointPos(ppoint4, 1, 1);
    DLS * ppos_comp;
    ppos_comp = (DLS *) malloc(sizeof(DLS));
    Set_DLS_Pos(ppos_comp, ppoint1, ppoint4);

    //각 점을 연결하는 유향선분 6개 정의
    ppos = (DLS *) malloc (sizeof(DLS));
    Set_DLS_Pos(ppos, ppoint1, ppoint2);
    LInsert(&list, ppos);
    ppos = (DLS *) malloc (sizeof(DLS));
    Set_DLS_Pos(ppos, ppoint2, ppoint3);
    LInsert(&list, ppos);
    ppos = (DLS *) malloc (sizeof(DLS));
    Set_DLS_Pos(ppos, ppoint3, ppoint1);
    LInsert(&list, ppos);
    ppos = (DLS *) malloc (sizeof(DLS));
    Set_DLS_Pos(ppos, ppoint2, ppoint1);
    LInsert(&list, ppos);
    ppos = (DLS *) malloc (sizeof(DLS));
    Set_DLS_Pos(ppos, ppoint1, ppoint3);
    LInsert(&list, ppos);
    ppos = (DLS *) malloc (sizeof(DLS));
    Set_DLS_Pos(ppos, ppoint3, ppoint2);
    LInsert(&list, ppos);

    // 저장된 데이터 출력
    printf("data in List : \n");
    
    if(LFirst(&list, &ppos)){
        Show_DLS_Pos(ppos);
        printf("length : %.2f\n", DLS_Length(ppos));

        while(LNext(&list, &ppos)){
            Show_DLS_Pos(ppos);
            printf("length : %.2f\n\n", DLS_Length(ppos));
        }
    }

    // comparing DLS와 직교하는 유향선분은 모두 삭제
    if(LFirst(&list, &ppos)){
        if(DLS_inner_product(ppos_comp, ppos)==0){
            ppos = LRemove(&list);
            free(ppos);
        }
        while(LNext(&list, &ppos)){
            if(DLS_inner_product(ppos_comp, ppos)==0){
                ppos = LRemove(&list);
                free(ppos);
            }
        }
    }

    //삭제 후 남은 데이터 출력
    printf("data in List AFTER DELETION : \n");
    
    if(LFirst(&list, &ppos)){
        Show_DLS_Pos(ppos);
        printf("\n");
        while(LNext(&list, &ppos)){
            Show_DLS_Pos(ppos);
            printf("\n");
        }
    }
    printf("\n");

    free(ppoint1);
    free(ppoint2);
    free(ppoint3);
    free(ppoint4);
    return 0;

}

 

실행 결과

이 구현을 실행 파일로 옮기기 위해서는 cmd에 아래 명령어를 쳐야 한다. 즉 ArrayList, Point 파일까지 한꺼번에 컴파일해 주어야 한다.

 gcc -o my_program .\ArrayList.c .\ArrayList.h .\dls.c .\dls.h .\dls_main.c .\Point.c .\Point.h

 
먼저, 리스트에 있는 6가지 DLS의 목록을 출력하고, 각각의 길이를 소수점 2자리까지 출력한 결과이다.

 
다음으로, 내적을 이용하여 y=x와 직교하는 DLS를 제거한 뒤, 나머지를 다시 출력하였다.

 
(4,1)과 (1,4)를 연결한 두 개의 DLS를 제외하고 나머지 4개가 살아남았음을 확인할 수 있다.