구조체의 개념, 포인터, 이중포인터

<이진트리(Binary Tree)>
- 연결리스트에 의한 방법
  - 배열에 의한 트리의 표현은 상당히 제한적인 기능을 갖는다
  - 특히 트리 구조는 데이터 양의 가변적인 경우에 주로 많이 사용하므로 데이터의 양을 미리 예측하기 힘들다
  - 트리가 포화이진 또는 완전 이진의 구조가 아니라 중간에 노드가 비어있는 경우가 발생할 때 메모리의 낭비가 일어난다
  - 따라사 실제의 응용분야에서는 포인터를 사용한 연결리스트 방법이 주로 사용되며, 연결리스트 역시 메모리 기반이 아닌 파일기반으로 구현된다
  - 이진트리는 하나의 데이터 필드에 두 개의 자식노드를 연결하는 연결필드가 필요하다 : 이중 연결리스트



<구조체란?>
- 구조체는 사용자가 혼합하기에 따라서 무한대에 가까운 조합(정수형, 실수형, 문자형 등)을 갖는다
  즉, 사용자가 구조체를 직접 만들어야한다
  ex) struct ST {      //사용자가 struct구조체를 만들어라, 구조체의 이름은 ST
      int SID;           //정수형(int는 프로그래밍 언어 자료형)
      char name[10];  //문자형(char는 프로그래밍 언어 자료형)
      float GPA;        //실수형(float는 프로그래밍 언어 자료형)
  }; 
  -> 정수형(SID : 120) | 문자형(char : KIM) | 실수형(float : 3.75) => 레코드
      구조체는 하나의 레코드로 표현이 가능하며 다양한 타입의 데이터를 묶어서 쓸 수 있다
      ex) struct ST K;  //struct ST(사용자가 많은 자료형), 구조체 ST이름의 구조체형 변수 K
           K.SID          //K=구조체형 변수,  (.)=구성원소의 SID

- 구조체는 다양한 방법으로 사용할 수 있는데, 
  ex) struct ST K;         //사용자가 만든 구조체형(struct ST) 변수 K
       1. struct ST M[3]; //사용자가 만든 구조체형 크기(공간)가 3개인 배열M -> 구조체형 원소가 3개 들어간다
            printf("%s", M[1].name)
                        - 구조체로 만들어진 배열은 정수형, 문자형, 실수형원소 모두 들어갈 수 있다

       2. int X[3] //정수형 변수로 만들어진 배열 3개짜리 -> 정수형 원소가 3개 들어간다
                       - 배열은 동일한 타입만 들어갈 수 있다
                       - 연속된 공간에 데이터가 할당되어 있어야한다
                       - 배열의 크기가 미리 지정되어야 한다(공간이 남을수도 모자를 수도 있다)



<포인터(동적 기억공간 - 우리가 원하는만큼 메모리를 할당)의 개념>
- 주소를 의미하는 것
- return은 1개의 값 1번만 리턴할 수 있다. A와 B라는 함수에서 각각 함수 내부에서 일어나는 일들은 접근할 수 없다
  포인터를 사용하면 다른함수에서 선언한 값을 접근할 수 있다
- A라는 함수에서 선언한 변수의 값을 B라는 함수에서 접근 할 수 없지만, A함수의 변수의 주소값을 알면 변수 값에 접근할 수 있다
- ex1) int x;
       int *xp; - 주소저장(xp = &x;)
       x = 20;
       printf("%d", *xp) -> *100 : 100번지의 값을 출력 즉, 20
--------------------------------
       x   20(값)
       xp 100(주소)

     

<이중 포인터의 개념>
- ex1) int x, y;
        int *xp;
        x=20, y=30;
        xp = &x;
--------------------------------
      x 20<100> 이고 xp 100<300>
      y 30<200> 이고 yp 200<  > 일 때, < >는 주소를 의미한다고 가정
      P1(  &xp, &y  ) //포인터 변수의 주소값 즉, int **pp(pp는 **의 이름이라고 가정)
      P1(int **pp, int *yp)일 때, 
      pp->300, yp->200
      즉, *pp = yp; <=> *300=200 <=>300번지 안에 200을 넣어라 
      싱글 포인터는 변수의 내용을 변화시키지만
      이중 포인터는 포인터가 가리키고 있는 성분을 변화한다



<이중 연결 리스트와 유사한 방식의 노드 구조>
struct bin_node{
  char data;
  struct bin_node *I_child;
  struct bin_node *r_child;
};
-> I_child  |  data  | r_child;



<리스트(List)>
- 리스트란 하나 이상의 데이터가 순서대로 나열한 형태
  - 공간적 순서
  - 데이터의 값에 의한 순서

- 리스트는 선형리스트, 연결리스트로 크게 분류
  - 리스트의 구현
    - 배열
    - 포인터
struct bin_node{
  char data;
  struct bin_node *I_child;
  struct bin_node *r_child;
};

- x = (struct bin_node*) malloc(sizeof(struct node));
    -> 구조체의 크기만큼(sizeof(struct node) 메모리에 할당(malloc)되고,
        그 공간을 구조체(struct) 노드형의 구조(bin_node)로 만들어서 그곳에 주소값(*)을 리턴
        *malloc : 동적할당


- struct bin_node * root : root는 구조체형 포인터변수를 말하며, 노드를 가리킬 수 있는 메모리 공간(포인터 공간)
                                 root노드의 주소값을 알고있다면 트리의 주소값과 값을 알 수 있다