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

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

 

1. 스택과 큐의 비교

 

2. 연결 리스트로 구현한 자료구조

2-1. 스택

• 연결 리스트의 맨 앞이 노드를 삽입/삭제하기에 편하다→ 맨 앞을 스택의 top으로 한다.

typedef int Item;
typedef struct stack_type *Stack;

struct node{
	Item data;
	struct node *next;
}
struct stack_type{
	struct node *top;
}

//스택의 생성
Stack create(){
	Stack s = malloc(sizeof(struct stack_type));
	s->top = NULL;
	return s;
}

//삽입
void push(Stack s, Item i){
	struct node *new_node = malloc(sizeof(struct node));
	new_node->data = i;
	new_node->next = s->top;
	s->top = new_node;
}

//삭제 
Item pop(Stack s){
	struct node *old_top;
	Item i;

	//스택이 비지 않았을 때: s->top != NULL
	old_top = s->top;
	i = old_top->data;
	s->top = old_top->next;
	free(old_top);
	return i;
}

2-2. 큐

• 연결 리스트의 첫 번째 노드에서는 삽입과 삭제가 둘 다 가능하나, 마지막 노드의 삭제는 어렵다.
  ⇒ 첫 번째 노드를 삭제하는 역할의 rear, 마지막 노드를 삽입하는 역할의 front
• 큐는 배열보다 연결 리스트로 구현하는 것이 간편하다.

typedef int Item;
typedef struct stack_type *Stack;

struct node{
	Item data;
	struct node *next;
};
struct queue_type{
	struct node *front;
	struct node *rear;
	int size;
}

//큐의 생성
Queue create(){
	Queue q = malloc(sizeof(struct queue_type));
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
	return q;
}

//삽입
void enqueue(Queue q, Item i){
	struct node *new_node = malloc(sizeof(struct node));
	new_node->data = i;
	new_node->next = NULL;

	if(q->front == NULL){
		q->front = new_node;
		q->rear = new_node;
	}
	else{
		q->rear->next = new_node;
		q->rear = new_node;
	}
	q->size++;
}

//삭제
Item dequeue(Queue q){
	struct node *old_front;
	Item i;

	//큐가 비지 않았을 때: q->size != 0
	old_front = q->front;
	i = old_front->data;
	q->front = old->front->next;
	
	//큐에 노드가 하나 있을 때
	if(q->front == NULL)
		q->rear = NULL;
	free(old_front);
	q->size--;
	return i;
}

 

3. 배열로 구현한 자료구조

3-1. 스택

• 데이터를 저장할 *contents, top을 가리키는 변수 top, 배열의 크기를 저장하는 size 가 하나의 구조체
• 스택을 동적 할당하고, 내부의 데이터인 contents도 할당받아야 함

typedef int Item;
typedef struct stack_type *Stack;

struct stack_type{
	Item *contents;
	int top;
	int size;
}

//스택의 생성
Stack create(){
	Stack s = malloc(sizeof(struct stack_type));
	s->contents = (Item *)malloc(배열의 크기 * sizeof(Item));
	s->top = -1;
	s->size = 배열의 크기;
	return s;
}

//삽입
void push(Stack s, Item i){
	if(s->top +1 == s->size)
		reallocateStack(s);
	s->top++;
	s->contents[s->top] = i;
}

//배열 재할당
void reallocate(Stack s){
	Item *tmp = (Item *)malloc(2 * s->size * sizeof(Item));
	for(int i=0; i<s->size; i++){
		tmp[i] = s->contents[i];
	free(s->contents);
	s->contents = tmp;
	s->size *= 2;
}

//삭제
Item pop(Stack s){
	//스택이 비지 않았을 때: s->top != -1
	s->top--;
	return s->contents[s->top+1];
}

3-2. 큐

• 배열로 구현한 큐는 front부터 rear까지 빈공간이 없어야 한다.
• 배열로 구현한 큐는
  • 인덱스의 범위와
  • 배열의 모든 칸을 사용하고 있어야 추가 reallocate를 받을 수 있기 때문에

       ⇒ 환형배열을 사용해야 한다 ~ reallocate도 스택과 다르게 해줘야 함

• 스택을 동적 할당하고, 내부의 데이터인 contents도 할당받아야 함

typedef int Item;
typedef struct queue_type *Queue;

struct queue_type{
	Item *contents;
	int front, rear, size, capacity;
}

//큐의 생성
Queue create(){
	Queue q = malloc(sizeof(struct queue_type));
	q->contents = (Item *)malloc(배열의 크기 * sizeof(Item));
	q->front = 0;
	q->rear = -1;
	q->size = 0;
	q->capacity = 배열의 크기;
	return q;
}

//삽입
void enqueue(Queue q, Item i){
	if(q->size == q->capacity)
		reallocate();
	q->rear = (q->rear +1) % q->capacity;
	q->contents[q->rear] = i;
	q->size++;
}

//재할당
void reallocate(Queue q){
	Item *tmp = (Item *)malloc(2 * q->capacity * sizeof(Item));
	int j = q->front;
	for(int i=0; i<q->size; i++){
		tmp[i] = q->contents[j];
		j = (j+1) % q->capacity;
	}
	free(q->contents);

	q->front = 0;
	q->rear = q->size-1;
	q->contents = tmp;
	q->capacity *= 2;
}

//삭제
Item dequeue(Queue q){
	//큐가 비지 않았을 때: q->size != 0
	Item result = q->contents[q->front];
	q->front = (q->front + 1) % q->capacity;
	q->size--;
	return result;
}

 

4. DFS와 BFS의 미로 찾기

4-1. 스택

while(1)
{
    maze[cur.x][cur.y] = VISITED;       //현재 위치를 방문했다고 표시
    if(cur.x == n-1 && cur.y == n-1){   
        printf("Found the path.\\\\n");
        break;
    }
    
    bool forwarded = false;    //되돌아 나가야하는지를 알려줌
	    for(int dir = 0 ; dir<4; dir++){    
	        if(movable(cur, dir)==1){       
            push(s, cur);               //**이동할 수 있다면 현재 위치를 스택에 push
            cur = move_to(cur, dir);    
            forwarded = true;           
            break;
        }
    }
    if(!forwarded){    //**이동에 성공하지 못했다면 ~ 되돌아가야함
        maze[cur.x][cur.y] = BACKTRACKED;    //현재 위치를 되돌아간 위치라 표시
			...
        cur = pop(s);    //**스택에서 pop한 위치가 새로운 현재 위치(cur)
    }
}

4-2. 큐

enqueue(q, cur);    //출발점을 큐에 넣고 시작
maze[0][0] = -1;

while(!is_empty(q)){
    Position cur = dequeue(q);    //**
    for(int dir = 0; dir<4; dir++){
        if(movable(cur, dir)){
            Position p = move_to(cur, dir);

            //**이동한 칸의 값 = 현재 위치 값 -1
            maze[p.x][p.y] = maze[cur.x][cur.y] -1;

            if(p.x == n-1 && p.y == n-1){
                printf("Found the path.\\\\n");
                //found = true;
                break;
            }
            
            enqueue(q, p);    //**이동한 위치가 출구가 아니라면 큐에 삽입
        }
    }
}

 

 

 

 

 

---

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