[자료구조] Arrays

Abstract Data Type (ADT) : 추상 자료형

: A data type that is organized in such a way that the specification of the objects and the specification of the operations on the objects is seperated from the representation of the objects and the implementation of the operations.

→ 무엇을 할 수 있는지 (연산, 행동 등)를 약속하고, 어떻게 저장, 구현하는지는 정하지 않음

• 장점
  • 구현 교체 자유 (representation independence) : array ↔ linked list 교체 가능
  • 정보 은닉 & 모듈성
• Ex) You can implement a graph using many different ways
• Primitive and composite types can also be reagarded as part of ADT
  • Array can be viewed as ADT : ‘원소’ 라는 인터페이스만 사용하는 ADT로 바라볼 수 있음

Performance of Programs

Program Performance

• suppose that program A, B take the same input, output
• run on same environment (HW, SW)

Time complexity

how is the running time of a program related to the input size?

Space complexity

how is the memory space of program related to the input size?

Big-O notation → upper bound of the performance

: asymptotic represenation of time(or space) complexity

→ coefficients and lower degree terms removed

• definition

For a given function f(n), O(f(n)) is the set of complexity functions g(n), for which there exists some positive real constant c and some nonnegative integer N such that g(n) ≤ c * f(n) for all n≥N

Arrays

Arrays as an ADT

A set of pairs <index, value> where for each value of index there is a value from the set item index
→ finite set of one or more dimensions

Functions of Array

: A∈ Array, i∈ index, x∈ Items, j:size∈ integer

Array Create (j, list)

return an array of j dimensions where list is a j-tuple whose i-th element is the size of the i-th dimensions. Items are undefined.

Item Retrieve (A, i)

if (i∈ index) return the item associated with index value i in array A else return error.

→ i 위치에 해당하는 값을 반환한다.

Array Store (A, i, x)

if (i∈ index) return an array that is identical to array A except the new pair <i, x> has inserted else return error.

→ i 위치의 값을 x로 update한 배열 A를 반환한다.

Arrays in C

int list2[4];
int *list1;

list2는 정수 값을 가리키는 포인터로 기능하고, list1도 마찬가지이다.

이때, list1과 list2의 차이점은 list2는 정수 4개의 memory space가 할당되어 있지만, list1은 memory가 동적 할당 (dynamically allocated) 되어야 한다.

• list2 : a pointer to list2[0](list2+i) is equal to &list2[i]
• *(list2+i) is equal to list2[i]
• list2+i : a pointer to list2[i]

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

float sum(float[], int);    
float input[MAX_SIZE], answer;
int i;

int main() {
    for(i=0; i<MAX_SIZE; i++)
        input[i] = i;
    printf("address of input: %p\n", input);
    answer = sum(input, MAX_SIZE);
    printf("The sum is: %f\n", answer);
    return 0;
}

// Get the sum of the values of input, and print the address of the input
float sum(float *list, int n) {
    int i;
    float tempsum = 0;
    for(i=0; i<n; i++)
        tempsum += list[i];
    printf("address of list: %p\n", list);
    return tempsum;
}

#include <stdio.h>
#include <stdlib.h>

void print1(int*, int);

void main() {
    int one[] = {0, 1, 2, 3, 4};    
    print1(one, 5);
}

void print1(int *ptr, int rows) {
    /* print out a one-dimensional array using a pointer */
    int i;
    printf("address contents\n");
    for(i=0; i<rows; i++)
        printf("%8p %5d\n", ptr+i, *(ptr+i));
    printf("\n");
}

print1 is function that prints the address of i-th element, and the value found at this address.

Dynamically Allocated Arrays (배열의 동적 할당)

#define MAX_SIZE 100

void main() {
  int i, n data[MAX_SIZE];
  printf("How many integers do you want to generate?");
  scanf("%d", &n);
  for(i=0; i<n; i++) {
    data[i] = rand();
    printf("%d\n", data[i]);
    }
}

: If the number of intergers is smaller than 100, we are wasting memory

: If the number of integers is larger than 100, program will stop or behave unexpectedly.

@warning
Good solution to this program is to define memory allocation to run time

void main() {
  int i, n, *data;
  printf("How many integers do you want to generate?");
  scanf("%d",&n);
  data = malloc(n * sizeof(int));
  for(i=0; i<n; i++) {
    data[i] = rand();
    printf("%d\n", data[i]);
  }
  free(data);
}

• void* malloc (size_t size)
  : allocates block of size bites of memory, returning a pointer to the beginning of the block
• free()
• realloc()

if you need to change the size of array after allocation, use realloc()

void main() {
  int i, n, *data;
  printf("How many integers do you want to generate?");
  scanf("%d", &n);
  data = malloc(n * sizeof(int));
  for(i=0; i<n; i++) {
    data[i] = rand(); 
  }
  printf("How many integers do you want to generate additonally?");
  scanf("%d", &m);
  data = realloc(data, (n+m) * sizeof(int));
  for(i=0; i<n+m; i++) {
    data[i] = rand(); 
  }
  for(i=0; i<n+m; i++) {
    printf("%3d : %8d\n", i+1, data[i]);
  }
  free(data);
}

#include <stdio.h>
#include <stdlib.h>

int** make2dArray(int, int);  // 2차원 배열의 각 행을 따로 동적할당하려면 이중 포인터가 필요

void main() {
    int i, j;
    int **matrix;

    matrix = make2dArray(5, 5);

    for(i = 0; i < 5; i++) {
        for(j = 0; j < 5; j++) {
            matrix[i][j] = i*5 + j + 1;
            printf("%p: %2d ", &matrix[i][j], matrix[i][j]);
        }
        printf("\n");
    }

    /* free memory */
    for(i = 0; i < 5; i++) 
        free(matrix[i]);
    free(matrix);
}

int** make2dArray(int rows, int cols) {

    int **x, i;

    /* allocate memory for row pointers */
    x = malloc(rows*sizeof(*x));
    printf("%lu\n", sizeof(*x));
    printf("%lu\n", sizeof(**x));
    printf("x allocated at address %p\n", x);

    /* allocate memory for each row */
    for(i = 0; i < rows; i++)  {
        x[i] = malloc(cols*sizeof(**x));
        printf("x[%2d] allocated at address %p\n", i, x[i]);
    }

    return x;
}    

• void* calloc(size_t num, size_t size): initializes all its bits to zero
  : allocates a block of memory for an array of num elements, each of them size bytes long.