[자료구조 - C언어] 자료구조 [1강-10강] 복습 및 정리

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

자료구조 1강

• 메모리
  • 모든 변수는 주소를 가진다.
• 포인터
  • 포인터는 메모리 주소를 값으로 가지는 변수이다.

  type-name * variable-name;

  • variable-name은 선언된 포인터 변수의 이름
  • *는 포인터 변수임을 표시하는 기호
  • type-name은 * variable-name이 저장하는 메모리 주소에 저장된 값의 데이터 타입
• & 연산자: 엠퍼센트
  • 연산자 &(엠퍼센트)는 변수로부터 그 변수의 주소를 추출하는 연산자

  int a = 100;
  int *ptr = &a;
  //ptr = 변수 a의 주소 값

  • ptr은 주소값을 저장 → *ptr은 ptr(주소값) 가리키는 값
  • ptr은 a의 주소 값을 저장 → *ptr은 a의 주소 값이 가리키는 값 100
• 포인터와 배열

    int a[10];
    //정수형 배열, 배열의 이름은 a, 배열 a의 크기는 10

  • 배열의 이름 a는 배열의 시작 주소 a[0]를 저장하는 포인터 변수
    • *a와 a[0]은 동일한 의미
    • *(a+1)와 a[1]은 동일한 의미 - 메모리 주소는 연산 가능하다.

• 동적 메모리 할당
  • malloc 함수를 사용해서 직접적으로 메모리를 요청해서 할당받아 데이터를 저장해 두는 것
    • malloc 함수를 호출 → 동적 메모리 할당을 요청 → 요구하는 크기의 메모리를 할당 → malloc 함수가 메모리의 시작주소를 반환
    • 일반적으로는 변수를 선언하고 그 변수에 데이터를 저장

    int *p;
    p = (int*)malloc(sizeof(int) * 10);
    
    p[0] = 12;
    *(p+1) = 16;
    

  • malloc 함수는 메모리 어딘가에 연속된 40byte의 메모리 공간을 확보한 다음 그 메모리 공간의 시작주소(첫 번째 byte)의 주소를 리턴
  • malloc으로 할당 받은 메모리는 보통의 배열처럼 사용한다.
• 배열 키우기(reallocation)
  • 할당 받은 배열의 크기 그 자체를 그냥 키우는 것은 가능하지 않다.

      int * array = (int *)malloc(4*sizeof(int));
      array[0] = 1; array[1] = 2; *(array+2) = 3;
      //array[4] = 4; 공간부족
    
      int *tmp = (int *)malloc(8*sizeof(int));
      for (int i=0; i<4; i++)
          tmp[i] = array[i];
    
      //free(array);
      array = tmp;

    • 메모리의 다른 곳에 더 큰 배열을 할당 받은 다음(tmp)
    • 원래 배열의 데이터(array)를 새로 할당 받은 더 큰 배열(tmp)로 옮기고 새로 할당 받은 공간(array = tmp)을 사용
  • array = tmp: array에 tmp를 저장하면 array가 새로 할당받은 메모리 공간의(tmp) 주소를 갖는다.
• 가비지(garbage)
  • 어떤 프로그램이 메모리를 할당 받았지만, 할당 받은 메모리의 주소를 아무도 가지고 있지 않게 되면 그 메모리 공간을 가비지라고 부른다.
  • free() 함수를 이용해 사용하지 않는 메모리 공간을 반환시켜야 한다.

 

자료구조 2강

• 문자열: char 타입의 배열이 각 칸마다 문자 하나씩 저장되는 것
  • 배열의 맨 마지막에는 null character(’\0’)가 저장되어 있어야 문자열의 끝을 표시할 수 있다.
  • 문자열 생성의 차이
    • str[]은 배열 안의 값은 바꿀 수 있지만(= str[1] = “k”), str이 전혀 다른 배열을 가리키도록 할 수 없다.
    • *str은 배열 안의 값은 바꿀 수 없지만, str이 전혀 다른 새로운 문자열을 가리킬 수 있다(= str = tmp;)
• 문자열을 저장할 때
  • scanf(”%s”, buffer)
    • 배열의 이름이 실제 그 주소를 저장하기 때문에 &연산이 필요 없다.
• 포인터 변수들 간의 치환문

    char * words[100];
  
    while(){
        words[n] = buffer;
    }
    //입력 aaaa, bbbb, cccc
    //출력 cccc, cccc, cccc
  
    while(){
        words[n] = strdup(buffer);
    }
    //입력 aaaa, bbbb, cccc
    //출력 aaaa, bbbb, cccc

  • 포인터 변수는 어떤 문자 배열의 주소를 저장할 포인터 변수이지 칸 자체가 문자 배열인 것은 아니다
    • 하나의 문자열을 받아 복제본을 만들어 복제본의 주소를 리턴할 수 있는 strdup를 사용해야 한다.

 

자료구조 3강

• 문자 입력시
  • scanf는 공백 단위로 단어 하나씩만 입력받기 때문에 문장을 읽기에 적절하지 않다.
  • gets는 줄바꿈 문자가 나올 때 까지 통째로 읽기 때문에 사이즈를 초과해서 입력을 받을 수 있어서 문제가 발생할 수 있다.
  • fgets는 배열의 크기를 매개변수로 받기 때문에 어떤 경우에도 그 사이즈를 초과할 수 없기 때문에 사용하기 적절하다.

  fgets(buffer, BUFFER_SIZE, stdin);
  //fgets(문자열, 첫 번째 매개변수에 대한 크기, 표준 입력 파일 포인터(= 키보드))

 

자료구조 4강

• c언어에서 메모리 관리
  • 전역변수(global variable)
    • 함수의 외부에 선언된 변수들, 프로그램이 시작될 때 할당되며 종료될 때 까지 유지
    • 메모리 영역 중 data section에 위치
  • 지역변수(local variable)
    • 함수 냉부에 선언된 변수들, 자신이 속한 함수가 호출될 때 메모리가 할당되며 함수가 return 될 때 소멸 → strdup

      void add(){
          char buf1[BUFFER_SIZE], buf2[BUFFER_SIZE];    //지역변수 buf1, buf2
          scanf("%s", buf1);
          scanf("%s", buf2);
    
          names[n] = strdup(buf1);                      //strdup와 strcpy
          numbers[n] = strdup(buf2);
      }

    • 내부 함수가 종료된 후에도 소멸하지 않고 프로그램이 실행되는 중에 계속해서 전역적으로 유지되어야 하는 데이터들은 지역변수의 주소값이 아닌, strdup함수가 malloc으로 heap에 메모리를 할당 받아서 값을 복사한 새로운 문자열의 주소를 저장해야 한다.
    • 메모리 영역 중 stack에 위치
  • 동적 메모리 할당(dynamic memory allocation)
    • 아무 때나 malloc 등의 함수를 호출하여 필요한 크기의 메모리를 할당할 수 있다.
      • 명시적으로 free() 함수를 호출하여 반환하지 않는 한 계속 유지
    • 메모리 영역 중 heap에 위치
      • 내부 함수가 return, 종료되더라도 그 메모리를 계속해서 사용할 수 있다.

 

자료구조 5강

• 파일로 저장하고 로드하기

    FILE *fp = fopen(fileName, "r");
  
    fscanf(fp, "%s", buf) != EOF;
  
    fclose(fp);

  • fopen함수는 file pointer 라는 값을 리턴
    • w: 파일에 쓸 때, 파일이 미리 존재하지 않아도 된다.
    • r: 파일을 읽을 때, 파일이 미래 존재해야 한다.
  • fsacnf 함수는 파일의 끝에 도달하면 EOF 값 리턴
    • EOF = End Of File
    • fscanf(fp, “%s”, buf): 입력받은 fp를 읽어 buf에 저장
  • fclose(fp): 사용이 끝난 파일은 반드시 받아야 한다.
    • fp는 fopen에서 리턴받은 파일 포인터

• 데이터를 추가할 때
  • 정렬된 상태를 유지하는 삽입정렬을 사용(= 한 칸씩 뒤로 이동해서 삽입)

 

자료구조 6강

• 이중 포인터 타입 변수

    char * names[100];
    char ** names;

  • char * names[100];
    • 캐릭터 포인터 타입의 배열의 이름이 names
      • 배열의 이름은 배열의 시작주소를 가리키는 포인터 변수
        • 캐릭터 포인터 타입 + 배열의 이름(= 포인터 변수)
          = char * 타입의 배열의 이름
          • = char * * names: 이중 포인터 타입 변수

• tokenizing
  • 구분 문자(delimiter)를 이용하여 하나의 긴 문자열을 작은 문자열들로 자르는 일
  • strtok을 이용한 문자열 자르기

      #include <stdio.h>
      #include <string.h>
    
      int main(void){
          char str[] = "now # is the time # to start preparing ### for the exam#";
          char delim[] = "#";
          char *token;
    
          //첫 번째 호출
          token = strtok(str, delim);
          while(token != NULL){    //문자열이 끝나서 더 이상 토큰이 존재하지 않으면 null 리턴
              printf("next token is: %s:%d\\n", token, strlen(token));
              //이어진 호출들
              token = strtok(NULL, delim);
          }
          return 0;
      }

    • token = strtok(문자열의 주소, 구분 문자로 사용할 문자 배열)
      • 리턴 값은 문자열을 구분자 기준으로 tokenizing 했을 때 첫 번째 toekn의 시작 주소를 리턴
        • str = "now # is the time # to start preparing ### for the exam#";
        • token = strtok(str, delim); ~ ‘now’의 n의 주소
      • 첫 번째 호출에서는 tokenizing 하고자 하는 문자열의 주소를 주어야 하지만, 그다음부터는 NULL 입력

      token = strtok(NULL, delim)

    • strtok는 첫 번째 시작 주소를 찾아 리턴해주는 것에 그치지 않고 첫 번째 토큰이 끝나는 위치에 null character를 삽입한다.
      • strtok은 원본 문자열을 변화시킨다.(= ‘\n’을 삽입한다.)
      • char * str = “ “; 변경할 수 없는 상수(string literal), strtok 사용 불가
      • char str[] = “”; 변경할 수 있는 변수, strtok사용 가능

 

자료구조 7강

• 구조체(struct): 항상 같이 붙어 다녀야 하는 데이터들을 하나의 그룹으로 묶어주는 역할

    typedef struct person{
        char * name;
        char * number;
        char * email;
        char * group;
    } Person;
  
    Person directory[100];

  • struct person을 정의하고 typedef를 사용해서 Person으로 renaming
    • typedef 선언을 사용하여 C에서 이미 정의된 형식이나 사용자가 선언한 형식에 대한 보다 짧거나 의미 있는 이름을 생성할 수 있다.
  • char * name은 문자열이라는 의미
  • struct person은 한 사람을 표현하기 위한 구조체로 여러 사람을 표현하기 위해서는 배열을 사용

    Person directory[CAPACITY];
  
    //struct 간에도 치환할 수 있다.
    directory[i+1] = directory[i];
  
    directory[i+1].name = strdup(name);
    directory[i+1].number = strdup(number);
    directory[i+1].email = strdup(email);
    directory[i+1].group = strdup(group);

 

자료구조 8강

• 구조체에 대한 포인터
  • C언어에서 구조체의 배열은 일반적인 방법이 아니다
    • 전달, 리턴등 구조체 내부의 모든 멤버들이 복사되기 때문에 구조체의 크기가 커지면 복사되는 데이터양이 많기 때문에 프로그램의 성능에 영향을 끼칠 수 있다.
    • 구조체의 배열로 표현하게 되면 구조체의 복사를 피할 수 없다.
  • 구조체의 배열 대신 구조체 포인터의 배열

    Person * directory[CAPACITY];

    
    • 포인터 변수를 매개변수로 사용해도 call-by-value로 값을 전달하는 것은 동일
      • call-by-value: 값에 의한 매개 변수 전달 방식
      • 하지만, 구조체의 모든 맴버들이 복사되는 것이 아니라, 주소값만 복사되기 때문에
        • 복사되는 값이 주소 1개로 매우 적어진다.
    • directory = tmp;
      • 와 같은 표현은 객체 자체가 복사되는 것이 아니라 객체의 주소가 복사되는 것
      • directory가 새로운 배열(tmp)를 가리키도록 하는 것
• 새로운 연산자 ->
  • (*p).name과 p->name은 동일한 표현이다.

 

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.