mooh

• 배열(array) 리스트(list)의 차이점
• 배열은 인덱스를 가진 데이터의 집합이고, 리스트는 인덱스 없이 순차적으로 저장된 데이터의 집합이다.
• 배열은 메모리에 연속적으로 저장되고 리스트는 메모리에 분산 되어 저장된다. 

6.1 배열(array)로 구현된 리스트

- 배열을 이용하여 리스트를 구현하면 순차적인 메모리 공간이 할당됨(리스트의 순차적 표현)

#include<stdio.h>
#include<stdlib.h>
#define MAX_LIST_SIZE 100


typedef int element;
typedef struct {
	element array[MAX_LIST_SIZE]; // 배열의 정의
	int size; // 현재 리스트에 저장된 항목들의 개수
} ArrayListType;

// 오류 처리 함수
void init(ArrayListType* L)
{
	L->size = 0;
}

// 리스트가 비어 있으면 1을 반환
// 그렇지 않으면 0을 반환
int is_empty(ArrayListType* L)
{
	return L->size == 0;
}

// 리스트가 가득 차 있으면 1을 반환
// 그렇지 않으면 1을 반환
int is_full(ArrayListType* L)
{
	return L->size == MAX_LIST_SIZE;
}
element get_entry(ArrayListType* L, int pos)
{
	if (pos < 0 || pos >= L->size)
		printf("위치 오류");
	return L->array[pos];
}

// 리스트 출력
void print_list(ArrayListType* L)
{
	int i;
	for (i = 0; i < L->size; i++)
		printf("%d->", L->array[i]);
	printf("\n");
}

void insert_last(ArrayListType* L, element item)
{
	if (L->size >= MAX_LIST_SIZE)
	{
		printf("리스트 오버플로우");
	}
	L->array[L->size++] = item;
}

void insert(ArrayListType* L, int pos, element item)
{
	if (!is_full(L) && (pos >= 0) && (pos <= L->size)) {
		for (int i = (L->size - 1); i >= pos; i--)
			L->array[i + 1] = L->array[i];
		L->array[pos] = item;
		L->size++;
	}
}

element delect(ArrayListType* L, int pos)
{
	element item;

	if (pos < 0 || pos >= L->size)
		printf("위치 오류");
	item = L->array[pos];
	for (int i = pos; i < (L->size - 1); i++)
		L->array[i] = L->array[i + 1];
	L->size--;
	return item;
}

int main(void)
{
	// ArrayListType를 정적으로 생성하고 ArrayListType를 가리키는 포인터를 함수의 매개변수로 전달
	ArrayListType list;

	init(&list);
	insert(&list, 0, 10); print_list(&list); // 0번째 위치에 10 추가
	insert(&list, 0, 20); print_list(&list); // 0번째 위치에 20 추가
	insert(&list, 0, 30); print_list(&list); // 0번째 위치에 30 추가
	insert_last(&list, 40); print_list(&list); // 맨끝에 40 추가
	delect(&list, 0); print_list(&list); // 0번째 항목 삭제
	return 0;
}

6.2 연결 리스트(Linked List)

- 동적으로 크기가 변할 수 있고 삭제나 삽입 시에 데이터를 이동할 필요가 없는 연결된 표현

- 이 연결된 표현은 포인터를 사용하여 데이터들을 연결함

• 연결 리스트의 구조

- 연결리스트는 노드(node)들의 집합, 다른 노드로 가기 위해서는 현재 노드가 가지고 있는 포인터를 이용

- 연결 리스트에서는 연결 리스트의 첫번째 노드를 알아야 만이 전체의 노드에 접근할수 있음

- 따라서 연결 리스트마다 첫번째 노드를 가리키고 있는 변수가 필요한데 이것을 헤드포인터(head pointer)라고 한다

6.3 단순 연결 리스트(Single Linked List)

- 노드 들이 하나의 링크 필드를 가지며 이 링크 필드를 이용하여 모든 노드들이 연결. 마지막 노드의 링크 필드값 NULL

• 노드의 정의

- 노드는 자기 참조 구조체(자기 자신을 참조하는 포인터를 포함하는 구조체)를 이용하여 정의됨

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

typedef int element;

typedef struct ListNode { // 노드 타입을 구조체로 정의
	element data;
	struct ListNode* link;
} ListNode;

// 공백 리스트 생성
// 구조체 변수 선언
ListNode* head = NULL;

• 노드의 생성

노드의 크기만큼 동적메모리를 할당 받음, 이 동적 메모리가 하나의 노드가됨. 동적메모리의 주소를 헤드 포인터인 head에 저장

head = (ListNode*)malloc(sizeof(ListNode));

• 노드의 연결

// 두번째 노드 생성
ListNode* p;
p = (ListNode*)malloc(sizeof(ListNode));
p->data = 20;
p->link = NULL;

// 첫번째 노드의 링크가 두번째 노드를 가리킴
head->link = p;

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

typedef int element;
typedef struct ListNode { // 노드 타입을 구조체로 정의
	element data;
	struct ListNode* link;
} ListNode;

// 오류 처리 함수
void error(char* message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}

ListNode* insert_first(ListNode* head, int value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = head; // 헤드 포인터의 값을 복사
	head = p; // 헤드 포인터 변경
	return head;
}

// 노드 pre 뒤에 새로운 노드 삽입
ListNode* insert(ListNode* head, ListNode* pre, element value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = pre->link;
	pre->link = p;
	return head;
}

ListNode* delete_first(ListNode* head)
{
	ListNode* removed;
	if (head == NULL) return NULL;
	removed = head;
	head = removed->link;
	free(removed);
	return head;
}

// pre가 가리키는 노드의 다음 노드를 삭제
ListNode* delete(ListNode* head, ListNode* pre)
{
	ListNode* removed;
	removed = pre->link;
	pre->link = removed->link;
	free(removed);
	return head;
}

void print_list(ListNode* head)
{
	for (ListNode* p = head; p != NULL; p = p->link)
		printf("%d->", p->data);
	printf("NULL \n");
}

int main(void)
{
	ListNode* head = NULL;

	for (int i = 0; i < 5; i++)
	{
		head = insert_first(head, i); // insert_first()가 반환된 헤드 포인터를 head에 대입
		print_list(head);
	}

	for (int i = 0; i < 5; i++)
	{
		head = delete_first(head);
		print_list(head);
	}
	return 0;
}

5.1 queue

- FIFO

5.2 선형큐(linear queue)

- 구현이 간단하나 선형큐의 경우 앞으로 이동이 필요함(안그러면 배열의 앞부분이 비어있어도 사용못함)

#include<stdio.h>
#include<stdlib.h>
#define MAX_QUEUE_SIZE 5

typedef int element;
typedef struct {
	int front;
	int rear;
	element data[MAX_QUEUE_SIZE];
} QueueType;

// 오류 함수
void error(char* message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}

void init_queue(QueueType* q)
{
	q->rear = -1;
	q->front = -1;
}

void queue_print(QueueType* q)
{
	for (int i = 0; i < MAX_QUEUE_SIZE; i++)
	{
		if (i <= q->front || i > q->rear)
			printf(" | ");
		else
			printf("%d | ", q->data[i]);
	}
	printf("\n");
}

int is_full(QueueType* q)
{
	if (q->rear == MAX_QUEUE_SIZE - 1)
		return 1;
	else
		return 0;
}

int is_empty(QueueType* q)
{
	if (q->front == q->rear)
		return 1;
	else
		return 0;
}

void enqueue(QueueType* q, int item)
{
	if (is_full(q))
	{
		printf("queue is full");
		return;
	}
	q->data[++(q->rear)] = item;
}

int dequeue(QueueType* q)
{
	if (is_empty(q))
	{
		printf("queue is empty");
		return -1;
	}
	int item = q->data[++(q->front)];
	return item;
}

int main(void)
{
	int item = 0;
	QueueType q;

	init_queue(&q);

	enqueue(&q, 10); queue_print(&q);
	enqueue(&q, 20); queue_print(&q);
	enqueue(&q, 30); queue_print(&q);
	enqueue(&q, 40); queue_print(&q);

	item = dequeue(&q); queue_print(&q);
	item = dequeue(&q); queue_print(&q);
	item = dequeue(&q); queue_print(&q);
	return 0;
}

5.3 원형큐

- front와 rear의 값이 배열의 끝에 도달하면 다음에 증가되는 값은 0이 되도록 설계

- 한칸은 늘 공백을유지(포화상태와 공백상태 구별을 위해)

init_queue(), is_empty(), is_full(), enqueue(), dequeue()

#include<stdio.h>
#include<stdlib.h>
#define MAX_QUEUE_SIZE 5

typedef int element;
typedef struct {
	int front;
	int rear;
	element data[MAX_QUEUE_SIZE];
} QueueType;

// 오류 함수
void error(char* message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}

// queue 초기화
void init_queue(QueueType* q)
{
	q->rear = q->front = 0;
}

// 공백상태 검출함수
int is_empty(QueueType* q)
{
	return (q->front == q->rear);
}

// 포화상태 검출함수
int is_full(QueueType* q)
{
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

// 원형큐 출력 함수
void queue_print(QueueType* q)
{
	printf("QUEUE(front=%d rear =%d) = ", q->front, q->rear);
	if (!is_empty(q)) {
		int i = q->front;
		do {
			i = (i + 1) % (MAX_QUEUE_SIZE);
			printf("%d | ", q->data[i]);
			if (i == q->rear)
				break;
		} while (i != q->front);
	}
	printf("\n");
}

// 삽입 함수
void enqueue(QueueType* q, int item)
{
	if (is_full(q))
		printf("queue is full");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

// 삭제 함수
int dequeue(QueueType* q)
{
	if (is_empty(q))
		printf("queue is empty");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}

int main(void)
{
	QueueType queue;
	int element;

	init_queue(&queue);

	enqueue(&queue, 1);
	enqueue(&queue, 2);
	enqueue(&queue, 3);
	enqueue(&queue, 3);
	queue_print(&queue);

	dequeue(&queue);
	dequeue(&queue);
	dequeue(&queue);
	queue_print(&queue);
	return 0;
}

5.4  큐의 응용(버퍼)

- 서로 다른 속도로 실행되는 두 프로세스 간의 상호작용을 조화시키는 버퍼역할에 사용

5.5 덱(deque)

- double-ended queue : 큐의 front와 rear에서 모두 삽입과 삭제가 가능한 큐

init_deque(), is_empty(), is_full(), add_rear(), delect_front(), delect_rear() 

4.1 Stack

- LIFO

- 복귀할 주소를 기억하는데 사용됨

- push : 스택의 맨 위에 item을 추가

- pop : 스택의 맨 위의 원소를 제거해서 반환

4.2 스택의 구현

- 정수배열 스택

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

#define MAX_STACK_SIZE 100 // 스택의 최대 크기
typedef int element; // 데이터의 자료형
element stack[MAX_STACK_SIZE]; // 1차원 배열
int top = -1;

// 공백상태 검출함수
int is_empty()
{
	return (top == -1);
}

// 포화상태 검출함수
int is_full()
{
	return (top == MAX_STACK_SIZE - 1);
}

// 삽입(push)함수
void push(element item)
{
	if (is_full())
	{
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else
		stack[++top] = item;
}

// 삭제(pop)함수
element pop()
{
	if (is_empty())
	{
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else
		return stack[top--];
}

// 피크(peek)함수
element peek()
{
	if (is_empty())
	{
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else
		return stack[top];
}

- top과 stack배열을 하나의 구조체로 결합시키고 이 구조체의 포인터를 함수로 전달

StackType이라는 새로운 구조체 타입을 만들고 여기에 stack 배열과 top을 넣음

#include<stdio.h>
#include<stdlib.h>
#define MAX_STACK_SIZE 100

// 스택이 구조체로 정의됨
typedef int element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
} StackType;

// 스택 초기화 함수
void init_stack(StackType* s)
{
	s->top = -1;
}

// 공백상태 검출함수<모든 연산은 구조체의 포인터를 받는다>
int is_empty(StackType *s)
{
	return (s->top == -1);
}

// 포화상태 검출함수
int is_full(StackType* s)
{
	return (s->top == MAX_STACK_SIZE - 1);
}

// 삽입(push)함수
void push(StackType *s, element item)
{
	if (is_full(s))
	{
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else
		s->data[++(s->top)] = item;
}

// 삭제(pop)함수
element pop(StackType* s)
{
	if (is_empty(s))
	{
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else
		return s->data[s->top--];
}

// 피크(peek)함수
element peek(StackType* s)
{
	if (is_empty(s))
	{
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else
		return s->data[s->top];
}

int main(void)
{
	StackType s; // 스택을 정적으로 생성

	init_stack(&s);
	push(&s, 1);
	push(&s, 2);
	push(&s, 3); // 함수를 호출할 때 스택의 주소를 전달
	printf("%d\n", pop(&s));
	printf("%d\n", pop(&s));
	printf("%d\n", pop(&s));
	return 0;
}

4.3 동적 배열 스택

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

// 스택이 구조체로 정의됨
typedef int element;
typedef struct {
	element *data; // data는 포인터로 정의됨
	int capacity; // 현재 크기
	int top;
} StackType;

// 스택 생성 함수
void init_stack(StackType* s)
{
	s->top = -1;
	s->capacity = 1;
	s->data = (element*)malloc(s->capacity * sizeof(element));
}

// 공백상태 검출함수<모든 연산은 구조체의 포인터를 받는다>
int is_empty(StackType* s)
{
	return (s->top == -1);
}

// 포화상태 검출함수
int is_full(StackType* s)
{
	return (s->top == s->capacity - 1);
}

// 삽입(push)함수
void push(StackType* s, element item)
{
	if (is_full(s))
	{
		s->capacity *= 2;
		s->data =
			(element *)realloc(s->data, s->capacity * sizeof(element));
	}
	s->data[++(s->top)] = item;
}

// 삭제(pop)함수
element pop(StackType* s)
{
	if (is_empty(s))
	{
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else
		return s->data[s->top--];
}

int main(void)
{
	StackType s; // 스택을 정적으로 생성

	init_stack(&s);
	push(&s, 1);
	push(&s, 2);
	push(&s, 3); // 함수를 호출할 때 스택의 주소를 전달
	printf("%d\n", pop(&s));
	printf("%d\n", pop(&s));
	printf("%d\n", pop(&s));
	free(s.data);
	return 0;
}

3.1 배열

배열 : 동일한 타입의 데이터를 한 번에 여러 개 만들 때 사용됨, 연속적인 메모리 공간이 할당되고 인덱스 번호를 사용하여 쉽게 접근이 가능

int list[i]
int list[3][4] // 3개행 5개열

3.2 구조체

타입이 다른 데이터를 묶는 방법

struct 구조체이름 {
	항목1;
	항목2;
	...
};

typedef struct studentTag{
    char name[10] // 문자 배열로 된 이름
    int age;
    double gpa;
} student;

int main(void){
    student a = { "kim", 20, 4.3 };
    student b = { "park", 21, 4.1 };
    return 0;
}

3.3 포인터

포인터 : 다른 변수의 주소를 가지고 있는 변수

#include<stdio.h>
int main(void) {
    int a = 100; // 정수형 변수
    int* p;
    p = &a; // 변수의 주소를 포인터에 저장
    printf("%d\n", a); // a에 저장된 값 (100)
    printf("%d\n", &a); // a의 주소 (4061816)
    printf("%d\n", p); // 포인터 p가 가르키는 주소 (4061816)
    printf("%d\n", *p); // 포인터 p가 가르키는 주소에 저장된 값 (100)
    return 0;
}

3.4 동적 메모리 할당

- 동적 메모리 할당(dynamic memory allocation) : 필요한 만큼의 메모리를 os로부터 할당받아 사용하고 사용이 끝나면 메모리 반납

- heap : 동적 메모리가 할당되는 공간

2.1 순환

어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법

복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 매개변수(parameter)와 지역변수를 스택으로 할당받음

#include<stdio.h>

void hanoi_tower(int n, char from, char tmp, char to)
{
	if (n == 1)
	{
		printf("원판 1을 %c 에서 %c 으로 옮긴다.\n", from, to);
	}
	else
	{
		hanoi_tower(n - 1, from, to, tmp);
		printf("원판 %d를 %c 에서 %c 으로 옮긴다.\n", n, from, to);
		hanoi_tower(n - 1, from, to, tmp);
	}
}

int main(void)
{
	hanoi_tower(4, 'A','B','C');
	
	return 0;
}

프로그램 = 자료구조 + 알고리즘

1. 자료구조

프로그램에서 자료들을 정리하여 보관하는 여러가지 구조

2. 알고리즘

컴퓨터로 문제를 풀기 위한 단계적인 절차

- 입력 : 0개 이상의 입력이 존재

- 출력 : 1개 이상의 출력이 존재

- 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야함

- 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야함

- 유효성 : 각 명령어들은 종이와 연필, 또는 컴포터로 실행 가능한 연산이어야함

- 기술방법 : 한글,영어등 자연어, 흐름도(flowchart), 의사코드(pseudo-code), 프로그래밍 언어

1.2 추상 자료형(Abstract Data Type, ADT)

- 자료형(data type) : 데이터의 종류(정수, 실수, 문자, 배열, 구조체)

- ADT : 실제적인 구현으로부터 분리되어 정의된 자료형

1.3 알고리즘의 성능 분석

- 빅오 표기법 : 기본연산의 횟수가 다항식으로 표현되었을 경우 다항식의 최고차항만 남기고 나머진 버림