데이터 구조 7 ( Functions, Reference parameter, Linked List )

• -Overloading 

   → 같은 형식을 여러 모양으로 나타낸 함수 

        ex) 덧셈 > 정수 덧셈, 스트링 덧셈 << 넘겨주는 parameter가 다름! 

        → 이름과 기능 같고, parameter만 다르게 함수를 2개 만든다! 속이 뻥

 

overloading 예시 - add함수

 

  → Handling하는 과정.

     - 먼저 Signature에 대한 exact matching 을 시도한다.  (다른 방법은 그냥 없다고 생각)

   ( signature = name , parameter순서 , type )  

 

 

  → Default function arguments

    : 선언할 때, parameter 쪽에 초기값을 설정하고, Call하면서 넘겨줄 때, 별 말 없으면(생략하면) 초기값을 따라감

         [ 생략은 뒤에서부터 !! ]

Default function arguments 예시

→  Friend function 

     : Non-member function 이 private member data를 access할 수 있도록 허용

   Class의 public function 선언 앞에 ‘friend’ 표시하면, access가능. 

+   해당 클래스의 member function이 아니어도 access 가능하다는 뜻.  ( = 클래스 밖에서 만든 함수여도 ㅇㅋ )

 

예)

다른 친구 무리들(내 private member data ) 한테 '얘 내 친구 A임 애 ㄱㅊ음' 이라고 하면, A는 같은 무리가( = 같은 class )

아니어도 내 친구들한테 접근 가능

 

Friend function 예시 ) 무게

 

 

• Reference Parameter

      1.  sub(x) →   void sub (int y)

      2.  포인터 :                        sub(&x) →   void sub (int *y)    > 주소로 콜하고 포인터로 받음

      3.  Reference Parameter : sub(x) →   void sub (int &y)     > 변수로 콜하고 주소로 받음

      

2번 결과 = 3번 결과 

→ 포인터의 주소에 가서 작업하는 기능을 사용하는 것

Reference Parameter 예시

 

• Linked List

     - Array list 표현

     장점 : 특정 원소 접근이 용이함 ( = Indexing 가능)

     단점 : 고정된 크기임 ( =낭비 혹은 부족) / 연속된 공간이 필요 / 중간의 추가,삭제가 비효율적(밀어내기가 안 되고 빈 칸 그대로 남음) 

 

Array list의 단점을 개선 = Linked list 

 

    - Linked List

   장점 : 크기, 메모리를 효율적으로 사용할 수 있다.

   단점 : 다 Linked 가 되어있어서 Indexing이 불편하다.  << a[80] 이게 안 됨

 

   ADT 

   - DATA : Link 로 연결된 원소 + 첫 원소의 위치를 가리키는 (Head) , 끝 원소를 가리키는 (Tail)

   - Operations : 

1. Head위치에 원소 하나 추가

2. Tail위치에 원소 하나 추가

3. Head위치에 원소 하나 삭제

4. 현재 Node 수 확인

5. Empty 인지 확인

 

[ 구현 ]

 

노드를 먼저 만들고, 어디를 가리킬지 정할 Head랑 Tail 클래스를 미리 만들어야한다.

 

- 노드

 

class node {

   public:

      string name;

      double score;

      node *link;   //다음으로 어디를 가리킬지

      void set_data(string s, double n);  //

};

    void node::set_data(string s, double n) {  노드 안에 넣을 데이터

      name = s;

      score = n;

}

 

-Head와 Tail

 

class my_list {

      node *head, *tail;

public:

      my_list();

      void add_to_head(node t);

      void add_to_tail(node t);

      node delete_from_head();

      int num_nodes();

      bool list_empty();

};

my_list:: my_list() {

      head = NULL; //  초기값 == 아직 만들어진 노드가 없으면 아무것도 안 가리킨다.

      tail = NULL;

}

 

 

1. Add_to_head()

 

알고리즘: 

1. 노드 하나를 만든다. (노드 a라고 하자)

2. 노드 a 안에 데이터를 넣는다.

3. Link를 조정

 3.1 노드a 가 가리키는 곳 = head가 가리키는 곳의 주소

 3.2 head가 가리키는 곳= a로 한다.

 (3.3 tail==Null이면 tail==a)

 

구현

 

 

 

2. Add_to_tail()

 

알고리즘:

1. 노드 하나를 만든다. (노드 a라고 하자)

2. 노드 a 안에 데이터를 넣는다.

3. Link를 조정

 3.1 노드a 가 가리키는 곳 = NULL //제일 마지막이니까

 

If tail!==NULL       //Empty가 아니라면

  3.2 tail이 가리키는 것 (tail주소에 있는 것) 이 가리키는 것 = a [ 원래 마지막이었던 원소가 새로 생긴 노드를 가리키게 한다 ]   

  else //이전 상태가 //Empty면  

  3.3 head =p;

tail=p;

 

 

 

 

 

https://www.youtube.com/watch?v=GnvLJ3qB6lE&list=PLj7x16SB_2GkaAf4y22Vo8uXr8jJ4wbjG

이 사람 거 들어보기

 

 

출처 : 한동대학교 김호준교수님 - 데이터구조 PPT