CS/자료구조 (12) 썸네일형 리스트형 [인프런|Binary Search Tree(1)] 영리한 프로그래밍을 위한 알고리즘 강좌 Binary Search Tree Dynamic Set 데이터들이 고정되어 있지 않고 추가, 삭제, 수정 등으로 계속해서 바뀌는 집합을 Dynamic set이라 한다. Dynamic set, Dictionary(hash 타입 데이터 구조), Search Structure 등으로 불린다. Search Structure 새로운 데이터의 추가와 삭제가 가능 쉽게 생각했을 때 배열, 연결 리스트를 사용 가능 데이터를 정렬해서 저장 혹은 정렬하지 않고 저장 - 배열 정렬 안 된 경우 데이터의 검색, 추가, 삭제 - Search 최악의 경우 O(n) - Insert 마지막에 추가 하기에 O(1) 만약 공간이 모자라서 malloc 해야 하는 경우 새 배열에 기존 값을 다 복사해야 하므로 O(n) - Delete 인덱.. [인프런|13강] C로 배우는 자료구조 | 연결 리스트 (2) 연결리스트 (2) int main() { Node *head = (Node *)malloc(sizeof(Node)); head->data = "Tuesday"; head->next = NULL; Node *q = (Node *)malloc(sizeof(Node)); q->data = "Thrusday"; q->next = NULL; head->next = q; q = (Node *)malloc(sizeof(Node)); q->data = "Monday"; q->next = head; head = q; Node *p = head; while(p!=NULL) { printf("%s\n", p->data); p = p->next; // 다음 노드의 주소를 p에 담는다. 맨 마지막 노드까지 출력되기 위해! } .. [인프런|12강] C로 배우는 자료구조 | 연결 리스트 (1) 연결 리스트 (1) 개념과 기본연산 - 리스트 기본적인 연산: 삽입(insert), 삭제(delete), 검색(search) 등 리스트를 구현하는 대표적인 두 가지 방법: 배열, 연결 리스트 - 배열 장점 랜덤 액세스가 가능하다. 어떤 위치이든 인덱스를 통해 접근 쉽다. 시작 주소 + 가고자 하는 곳의 위치(ex 4번째 칸이면 4) * 1칸의 크기(데이터 타입의 기본 바이트 ) 단점 크기가 고정 -reallocation이 필요하다. 리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야 한다. - 연결 리스트 다른 데이터의 이동 없이 중간에 삽입이나 삭제가 가능하며, 길이의 제한이 없다. 하지만 랜덤 액세스가 불가능하다. 연결 리스트는 물리적으로 연속된 공간 데이터를 저장하지 않는다 노드는.. [인프런|11강] C로 배우는 자료구조 | 전화번호부 v5.0 (2) 전화번호부 v5.0 (2) 구조체에 대한 포인터, 동적 메모리 할당 전화번호부 v5.0 (1)(구조체에 대한 포인터) 이어서 동적메모리 할당을 적용한 전화번호 프로그램을 만든다. 위 그림처럼 Person ** directory 포인터 배열에 동적메모리 할당을 한다. #define INIT_CAPACITY 100 typedef struct person { // person은 생략가능 char *name; // 배열로 쓰기 위해 *로 선언 char *number; char *mail; char *group; } Person; Person **dicrectory; int capacity; int n; void init() { directory = (Person **)malloc(INIT_CAPCITY *siz.. [인프런|10강] C로 배우는 자료구조 | 전화번호부 v5.0 (1) 전화번호부 v5.0 (1) 구조체에 대한 포인터, 동적 메모리 할당 v4.0에서 구조체를 배열로 사용하였다. 배열 각 칸에 name, number 등 등 여러 변수가 저장된다. 함수를 호출할 때 넘겨주는 매개변수를 실질매개변수라고한다. 호출되는 함수에서 넘겨받는(복사되는) 매개변수를 형식매개변수라고 한다. 위 '함수 호출 과정에서 매개변수의 복사' 그림에서 void status()에서 print_person(directory[i])를 부를 때 directory[i]가 실질매개변수가 되며 void print_person(Person p) p가 형식매개변수가 여기서 실질매개변수가 형식매개변수로 복사가 되어서 사용된다. 그러므로 구조체 배열로 선언하여 넘겨주고 받게되면 매번 함수를 호출할때마다 구조체의 항목(.. [인프런|9강] C로 배우는 자료구조 | 전화번호부 v4.0 전화번호부 v4.0 더 많은 항목, 구조체 추가 이름을 제외한 일부 항목이 누락되어도 작동되도록 한다. 추가, 검색의 경우 공백 입력이 많이 되었더라도 실제로는 공백 1개로 인식되게한다. 구조체 - 항상 같이 붙어다녀야 하는 데이터를 별개의 변수들에 분산해서 저장하는 것은 바람직하지 않다. - 어떤 한 사람의 이름, 전화번호, 이메일 주소 등이 그런 예이다. - C언어에서는 이런 경우 구조체(structure)를 사용한다. #include #include #include #define CAPACITY 100 #define BUFFER_LENGTH 100 typedef struct person { // person은 생략가능 char *name; // 배열로 쓰기 위해 *로 선언 char *number; .. [인프런|6,7,8강] C로 배우는 자료구조 | 전화번호부 v3.0 전화번호부 v3.0 전화번호부 v2.0(5강)에 더해 배열 재할당, 라인 단위 입력과 문자열 tokenizing 기능을 추가한다 #include #include #include #define INIT_CAPACITY 3 // 배열 재할당을 테스트하기 위해 작은 값으로 설정 #define BUFFER_SIZE 50 char ** names; char ** numbers; // char * 타입 배열이므로 char **이다. int capacity = INIT_CAPACITY; // size of arrays int n = 0; // 전화번호부 사람 수 char delim[] = " "; int main() { init_directory(); process_command(); return 0; } init_.. [인프런|5강] C로 배우는 자료구조 | 전화번호부 v2.0 전화번호부 v2.0 전화번호부 v1.0(4강)에 더해 파일로 저장 및 로드, 알파벳 순 정렬 기능을 추가한다 자료구조는 v1.0과 동일하며 load, save 함수가 추가된다. #include .. #define CAPACITY 100 #define BUFFER_SIZE 100 char * names[CAPACITY]; char * numbers[CAPACITY]; int n = 0; void load(); void add(); void find(); void status(); void remove(); void save(); int main() { char buffer[BUFFER_SIZE]; while (1){ printf("$ "); scanf("%s", buffer); if (strcmp(comm.. [인프런|4강] C로 배우는 자료구조 | 전화번호부 v1.0 전화번호부 v1.0 위와 같이 동작되도록 전화번호부 프로그램을 만든다. add, find, status, delete 등의 동작 구현 코딩 이전에 어떤 자료구조로 저장할지 프로그램의 자료구조를 먼저 생각해야한다. - 어떤 데이터를 다루고 유지해야 하는지 생각 전화번호부 v1.0의 경우 1. 내부적으로 저장해야하는 데이터는 여러사람의 이름, 전화번호 char * 타입의 names[], numbers[]를 선언 전화번호의 경우 '-' 기호를 사용하며 0으로 시작하는 경우 정수형일때 0이 빠지므로 문제가 된다. 그래서 char 타입을 사용한다. #include .. #define CAPACITY 100 #define BUFFER_SIZE 100 char * names[CAPACITY]; char * numbe.. [인프런|3강] C로 배우는 자료구조 | 문자열 연습문제 문자열 연습문제 위와 같은 결과를 만드는게 목표 #define BUFFER_SIZE 20 int main(void) { char buffer[BUFFER_SIZE]; while(1) { printf("$ "); //scanf(buffer); scanf는 공백 문자 기준으로 끊기 때문에 공백을 포함한 문장에 쓸 수 없음 //gets(buffer); gets는buffer에 담을 수 있는 길이 상관없이 담는 문제가 있다. //fgets(buffer, BUFFER_SIZE, stdin); BUFFER_SIZE만큼 읽는다. 단, \n, buffer size 초과시 원하는 대로 반영이 제대 로 안됨 // buffer[strlen(buffer)-1] = '\0'; fgets를 쓸때 buffer[strlen(buffe.. 이전 1 2 다음
