[KNK] CH19 - advanced uses of pointers

CH19 advanced uses of pointers

Dynamic Storage Allocation

Memory Allocation Functions

• malloc: Allocates a block of memory but doesn’t initialize it(most used)
• calloc: Allocates a block of memory and clears it
• realloc: Resizes a previously allocated block of memory

Null Pointers

• pointer to nothing
• If the functions above return null pointer, you have to take appropriate action.
• null pointer의 논리값은 false, non-null pointer의 논리값은 true
• NULL매크로가 정의된 헤더파일 리스트
  • locale.h
  • stddef.h
  • stdio.h
  • stdlib.h
  • string.h
  • time.h
  • wchar.h(c99)

Dynamically Allocated Strings

Using malloc to Allocate Memory for a String

void *malloc(size_t size); // prototype
p = malloc(n+1); // example

동적 할당을 하고 나면 free를 이용해서 memory를 정리해야 한다.

Dynamically Allocated Arrays

Using malloc to Allocate Storage for an Array

a = malloc(n * sizeof(int) )

The calloc Function

void *calloc(size_t nmemb, size_t size); // prototype
a = calloc(n , sizeof(int)); // example 1
struct point { int x, y; } *p; // example 2
p=calloc(1, sizeof(struct point));

The realloc Function

void *realloc(void *ptr, size_t size); // prototype

ptr에 들어가는 포인터는 반드시 malloc, calloc, realloc으로 만들어진 것이어야 함

1. memory block이 확장되면 확장된 부분은 초기화가 되어있지 않음.
2. memory block이 요구대로 확장이 안된 경우 null pointer를 반환
3. first argument로 null pointer를 넣을 경우 malloc이랑 같음
4. second argument로 0을 넣으면 메모리를 free 시킴

   (주의) memory block을 확장시킬 때 바이트가 사용중이면 다른 곳에 memory block이 생성 됨. realloc을 사용 후에는 byte를 update

Deallocating Storage

memory leak이 생기지 않도록 항상 메모리를 해제해야 한다.

The free Function

void free(void*ptr); // prototype 
/* example */
p = malloc(...);
q = malloc(...);
free(p);
p=q;

other object(such as a variable or array element) cause undefined behavior

The “Dangling Pointer” 문제

free 함수로 지운 memory block을 access하면 undefined behavior를 할 수 있다.

Linked Lists

• array에 비해 유연하다. 다시 말해, 삽입과 삭제가 용이하다.
• 랜덤 엑세스 할 수 없다. 만드시 헤드 노드를 통해서 접근해야 한다.

Declaring a Node Type

struct node
{
  int value;
  struct node *next;
};
// structure tag is necessary if

Creating a Node

1. Allocate memory for the node.
2. Store data in the node.
3. Insert the node into the list.

   struct node *new_node;
   new_node = malloc(sizeof(struct node));
   (*new_node).value = 10;
   

   (주의) sizeof 연산자 안에 new_node를 넣으면 안된다.

The ‘->’ Operator

// continuing example above
(*new_node).value = 10;
new_node->value = 10; // 위 코드와 동일하다.
scanf("%d",&new_node->value);

Inserting a Node at the Beginning of a Linked List

struct node *first;
struct node *new_node;
first = NULL;
new_node = malloc(sizeof(struct node));
new_node->value = 10;
new_node->next = first;
first = new_node;
new_node = malloc(sizeof(struct node));
new_node->value = 20;
new_node->next = first;
first = new_node;

struct node *add_to_list(struct node *list, int n)
{
  struct node *new_node;

  new_node = malloc(sizeof(struct node));
  if (new_node == NULL)
  {
    printf("Error: malloc failed in add_to_list\n");
    exit(EXIT_FALURE);
  }
  new_node->value = n;
  new_node->next=list;
  return new_node;
}
/* 위 함수를 이용한 주어진 정수로 linked list 만들기 */
struct node *read_numbers(void)
{
  struct node *first=NULL;
  int n;

  printf("Enter a series of intergers (0 to terminate): ");
  for(;;)
  {
    scanf("%d",&n);
    if(n==0)
      return first;
    first = add_to_list(first, n);
  }
}

Searching a Linked List

// for (p = first; p != NULL; p=p->next)를 이용
struct node *search_list(struct node *list, int n)
{
  struct node *p;

  for(p=list; p!=NULL; p=p->next)
    if(p->value ==n)
      return p;
  return NULL;
}

Deleting a Node from a Linked List

1. Locate the node to be deleted
2. Alter the previous node so that it “bypasses” the deleted node.
3. Call ‘free’ to reclaim the space occupied by the deleted node.

struct node *delete_from_list(struct node *list, int n)
{
  struct node *cur, *prev;

  for(cur = list, prev = NULL;
  cur != NULL && cur->value != n;
  prev = cur, cur = cur-> next)
  ;
  if(cur ==NULL)
     return list;
  if(prev == NULL)
    list = list->next;
  else
    prev->next = cur->next;
  free(cur);
  return list;
}

Ordered Lists

삽입은 어려워지나 검색이 빨라진다.

Pointers to Pointers

argument of ‘add_to_list’ function does not modify parameter itself. (you have to use the function first = add_to_list(first, 10))

void add_to_list(struct node **list, int n)
{
  struct node *new_code;

  new_code =malloc(sizeof(struct node));
  if(new_code==NULL)
  {
    printf("Error: malloc failed in add_to list\n");
    exit(EXIT_FAILFURE);
  }
  new_node->=n;
  new_node->next=*list;
}
add_to_list(&first,10);

Pointers to Functions

double integrate(double (*f)(double), double a, double b);
double integrate(double f(double), double a, doubleb); // 위와 동일
// f(): function call
// f: pointer to function

Declaration of function pointer variables

// FuncPtr라는 변수가 생김(이 변수는 2개의 int형 parameter를 받고 int형을 return)
int (*FuncPtr)(int,int);

// FuncPtr이라는 type이 생김 (FuncPtr f1, f2;같이 선언 가능)
typedof int (*FuncPtr)(int,int);

쓰는 이유

1. Functions can be used as a argument
2. Functions can be assigned to the variable

Restricted Pointers(c99)

it is for advanced user

Flexible Array Members

struct vstring
{
  int len;
  char chars[ 1 (dummy value) ];
};
struct vstring *str = malloc(sizeof(struct vstring) + n-1 );
str->len = n;

또는

struct vstring
{
  int len;
  char chars[];
};
struct vstring *str = malloc(sizeof(struct vstring) + n);
str->len = n;