JH 개발 블로그

※ 인프런 강의 "C로 배우는 자료구조 및 여러가지 예제실습(권오흠 교수님)"를 보고 개인적인 복습을 위해 정리한 내용입니다. add_song 함수를 구현하기 위해서는 다음과 같은 자료구조의 이해가 필요하다. 한 명의 가수를 구현하는 "구조체 Artist" 가 있다. 그 안에 이 가수의 노래 세 곡이 있다면 노래들을 양방향 리스트로 만들어준다. 이때 직접 Song 을 만드는 대신에 SNode 를 만든다. (= 각각의 SNode 가 Song을 거느린다.) 가수의 구조체 안 head와 tail 에 곡 첫번째와 마지막을 저장해준다. (양방향 리스트이므로) 가수 구조체는 artist_directory 배열의 이니셜에 따라 분류해서 단방향 연결리스트로 만들어준다. next 는 가수끼리 단방향 연결리스트로 연결해주..

※ 인프런 강의 "C로 배우는 자료구조 및 여러가지 예제실습(권오흠 교수님)"를 보고 개인적인 복습을 위해 정리한 내용입니다. main.cpp 에서 read_line 함수를 호출하면 string_tools.cpp 에서 read_line 함수를 정의한 것을 불러오게 됨 이들을 연결시켜주기 위한 메커니즘은.. string_tools.h에 read_line 함수의 프로토타입을 써주어야 하고 main.cpp에 #include "string_tools.h" 헤더파일 포함시켜야 함 그리고 string_tools.cpp 에 자신이 해당하는 헤더파일 include "string_tools.h" 해서 포함시켜주면 연결 완성 #pragma once #include int read_line(FILE *fp, char str..

단방향 연결 리스트(single linked list)의 한계: 어떤 노드의 앞에 새로운 노드를 삽입하기 어렵다 삭제의 경우에 항상 삭제할 노드의 앞 노드가 필요하다 단방향의 순회만이 가능하다 이중 연결 리스트 각각의 노드가 다음(next) 노드와 이전(previous) 노드의 주소를 가지는 연결 리스트 양방향의 순회(traverse)가 가능하다 Node struct node { char *data; /* 각 노드에 하나의 문자열이 저장된다고 가정함 */ struct node *next; struct node *prev; }; typedef struct node Node; Node *head; Node *tail; int size = 0; 앞서 단방향 연결리스트(Single linked list)에서 ①..

※ 인프런 강의 "C로 배우는 자료구조 및 여러가지 예제실습(권오흠 교수님)"를 보고 개인적인 복습을 위해 정리한 내용입니다. 내림차순으로 정렬된 항에서 새로운 항을 삽입해야 하므로 두 포인터 p, q 를 이용한다. 공식처럼 외워야 할 것은 정렬된 항에서 삽입할 때에는 두 포인터를 이용하는 것이 좋다는 것이다. 그리고 이때 q는 항상 p의 한발 뒤를 따라가야 한다. addafter 가 간단하기 때문이다. Term p = first; Term q = null; while (p != null && p.expo > e) { q = p; // q는 항상 p의 한발 뒤를 따라감 p = p.next; } add_after(q); p는 연결리스트의 노드들을 순회하면서 특정한 노드를 찾는 데 쓰고 q는 p의 뒤를 쫓아..

※ 인프런 강의 "C로 배우는 자료구조 및 여러가지 예제실습(권오흠 교수님)"를 보고 개인적인 복습을 위해 정리한 내용입니다. void add ( int index, ...) 연결리스트의 index 번째 위치에 새로운 노드를 만들어서 삽입한다. int add(int index, char *item) { if (index < 0) return 0; if (index == 0) { /* 맨 앞에 삽입하는 경우 */ add_first(item); return 1; } Node *prev = get_node(index - 1); /* 그 이외의 경우 */ if (prev != NULL) { add_after(prev, item); return 1; } return 0; } 삽입에 실패하면 0을, 성공하면 1을 ..

연결리스트 순회 (traverse) 연결리스트의 노드들을 처음부터 순서대로 방문하는 것을 순회(traverse) 한다고 말한다. 아래 함수는 입력된 문자열 word와 동일한 단어를 저장한 노드를 찾아서 그 노드의 주소를 반환한다. 그것을 위해서 연결리스트를 순회한다. Node *find(char *word) { /* 검색할 단어를 받는다. */ Node *p = head; /* p가 첫번째 head 노드를 가리키도록 함 */ while (p != NULL) { if (strcmp(p->data, word)==0) /* word : 내가 찾는 단어 */ return p; p = p->next; } return NULL; } 검색할 단어를 먼저 받는다. 그리고 p가 head 노드를 가리키도록 한다. p가 N..

1. 첫번째 노드의 삭제 head 가 현재 head 노드의 다음 노드를 가리키게 만든다. head = head -> next; Node * remove_first () { /* 주소 리턴 */ if (head == NULL) { return NULL; } else { Node *tmp = head; /* head 노드의 주소를 임시로 보관할 포인터 */ head = head->next; return tmp; /* head 노드의 주소 리턴 */ } } if 문에서 head 가 NULL 이라는 것은 연결리스트의 노드가 하나도 없음을 의미한다. 이 경우 return NULL 로 처리한다. else문에서 head의 주소를 임시적으로 tmp 가 가지고 있게 한다. head = head -> next 에 의해 첫..

1. 연결리스트의 맨 앞에 새로운 노드 삽입하기 다음과 같은 알고리즘을 기억하면 좋다. 1) 새로운 노드를 만들고 추가할 데이터를 저장한다. 2) 새로운 노드의 next 필드가 현재의 head 노드를 가리키도록 한다. 3) 새로운 노드를 새로운 head 노드로 한다. 다음과 같이 코드를 작성할 수 있다. Node *tmp = (Node *)malloc(sizeof(Node)); // 새로운 노드 생성 tmp->data = “Ann”; // (1) 추가할 데이터 저장 tmp->next = head; // (2) 새로운 노드의 next 는 기존의 head를 가리키게 한다 head = temp // (3) head 는 temp 로 한다 이와 관련 함수 작성 1) head = 전역변수 void add_first..

List (리스트) 는 순서가 의미가 있다. (1, 2, 3) != (3, 2, 1) Set (집합) 은 순서가 무의미하다. {1, 2, 3} == {3, 2, 1} 리스트를 구현하는 대표적인 두 가지 방법은 배열, 연결리스트 이다. 배열은 앞서 전화번호부를 만들때 배웠으며, 단점은 배열은 크기가 고정되어 있다는 것이다. 따라서 reallocation(재할당) 이 필요했었다. 또한 리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야 하는 단점이 있었다. vs 그러나 연결리스트는 다른 데이터의 이동 없이 중간에 삽입하거나 삭제가 가능하며, 길이 제한이 없다. 하지만 랜덤 엑세스가 불가능하다는 단점이 있다. 배열과 연결리스트의 메모리를 살펴보자. 배열은 데이터들이 연속된 공간에 저장되는 것..

typedef struct person { char *name; char *number; char *email; char *group; } Person; Person directory[CAPACITY]; /* 구조체 배열 */ int n = 0; /* number of people in phone directory */ void status() { int i; for (i = 0; i < n; i++) print_person(directory[i]); printf("Total %d persons.\n", n); } void print_person(Person p) /* 매개변수 주목 */ { printf("%s:\n", p.name); printf(" Phone: %s\n", p.number); prin..