[CS50 코칭스터디] 6주차_자료구조

 

[6주차 개념]

✔️ malloc과 포인터 복습 - 포인터, malloc

 

✔️ 배열의 크기 조정하기 - malloc, realloc

새로운 공간에 큰 크기의 메모리를 다시 할당하는 방법 2가지 :  malloc, realloc

 

✔️ 연결 리스트: 도입

배열 : 각 인덱스의 값이 메모리상에서 연이어 저장

연결 리스트 : 각 값이 메모리상의 여러 군데 나뉘어져 있다고 하더라도 바로 다음 값의 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수 있음. 각 인덱스의 메모리 주소에서 자신의 값과 함께 바로 다음 값의 주소(포인터)를 저장

 

✔️ 연결 리스트: 코딩

 

✔️ 연결 리스트: 시연 - 연결 리스트, 배열

장점 : 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 됨

단점 : 임의 접근이 불가능

 

✔️ 연결 리스트: 트리 - 트리, 루트

트리 : 연결 리스트를 기반으로 한 새로운 데이터 구조

루트 : 가장 높은 층에서 트리가 시작되는 노드

루트 노드는 다음 아래 층의 노드(=자식 노드)들을 가리키고 있음

 

✔️ 해시 테이블 -  해시 테이블, 해시 함수

해시 테이블 : 연결 리스트의 배열

해시 함수 : 각 값들은 해시 함수를 통해서 어떤 바구니에 담기는 지가 결정

 

✔️ 트라이

트라이 : 기본적으로 ‘트리’ 형태의 자료 구조, 각 노드가 ‘배열’로 이루어져있음

트라이에서 값을 검색하는데 걸리는 시간은 ‘문자열의 길이’에 의해 한정

 

✔️ 스택, 큐, 딕셔너리

스택 : ‘선입 선출’ 또는 ‘FIFO’ / 배열이나 연결 리스트

큐 : ‘후입 선출’ 또는 ‘LIFO’ / 배열이나 연결 리스트

딕셔너리 : ‘키’와 ‘값’ /  ‘해시 테이블’

 

 

[6주차 팀별미션]

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

typedef struct stack{
    int top;
    int capacity;
    int* array;
} Stack;

Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int *)malloc(stack->capacity*sizeof(int));
    return stack;
}

int isFull(Stack* stack) {
    return stack->top == stack->capacity-1;
}

int isEmpty(Stack* stack) {
    return stack->top == -1;
}

void push(Stack* stack, int item) {
    if (isFull(stack))
        return;
    stack->array[++stack->top] = item;
    printf("%d pushed to stack\n", item);
}

int pop(Stack* stack) { // 스택에서 데이터를 제거
    if (isEmpty(stack)) 
        return -9999;
    return stack->array[stack->top--];
}

int peek(Stack* stack) { // 스택에서 top이 가리키는 데이터를 읽음
    if (isEmpty(stack)) 
        return -9999;
    int data = stack->array[stack->top];
    return data;
}

int main() {
    Stack* stack = createStack(100);

    push(stack, 10);
    push(stack, 20);
    push(stack, 30);
    push(stack, 40);

    printf("%d pop from stack\n", pop(stack));
    printf("%d pop from stack\n", pop(stack));

    push(stack, 50);
    printf("%d pop from stack\n", pop(stack));
    printf("%d pop from stack\n", pop(stack));
    printf("%d pop from stack\n", pop(stack));
    printf("%d pop from stack\n", pop(stack));
    return 0;
}