본문 바로가기

분류 전체보기407

6: 자료구조-6(해시 테이블) 해시 테이블: “연결 리스트의 배열” 해시 테이블에서는 단어나 이름 같은 입력값이 들어온다면 그 단어에 포함된 문자를 보고 어디에 그 이름을 넣을지 결정하는 방식이 흔하게 사용됨 - 이름이 해시 테이블에 저장되며, 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며, 해시 함수는 ‘이름의 가장 첫 글자’인 경우, 각 포인터는 그 알파벳을 시작으로 하는 이름들을 저장하는 연결 리스트를 가리키게 됨 - 해시 테이블 -> 세로: 배열 / 가로: 연결 리스트 - 충돌: 어떤 값을 넣으려고 하는데 이미 무언가 들어가 있는 경우. / 최대한 충돌을 피해야 함! 인덱싱을 하는데 사용하는 배열 -> 해시 함수 Albus를 해시함수에 넣으면 0이 반환되어서 0번째 배열 즉 A에 해당하게 됨 Harry를 해시함.. 2021. 12. 11.
6: 자료구조-5(연결 리스트: 트리) 트리 : 연결 리스트를 기반으로 한 새로운 데이터 구조 - 연결 리스트에서의 요소들의 연결은 1차원적으로 구성되어 있고, 트리에서의 노드들의 연결은 2차원적으로 구성되어 있음 - 각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가지게 됨 - 가장 높은 층에서 트리가 시작되는 노드 ‘루트’ - 루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 ‘자식 노드’라고 함 - 트리의 노드들은 최대 두 개의 자식 노드를 가짐. 이진법의 이진을 따와서 최대 2라는 것을 표현 - 왼쪽 자식 노드는 자신의 값보다 작고, 오른쪽 자식 노드는 자신의 값보다 큼 이런 트리 구조는 이진 검색을 수행하는 데 유리함 - 트리를 탐색하려면 트리의 가장 위에 있는 루트라는 노드만 알려주면 트리의 모든 곳으로 갈.. 2021. 12. 11.
6: 자료구조-4(연결 리스트: 코딩과 시연) 연결리스트의 코드를 나눠서 보기 1. 연결 리스트의 기본 단위가 되는 node 구조체를 정의 typedef struct node { //node 안에서 정수형 값이 저장되는 변수를 number로 지정 int number; //다음 node의 주소를 가리키는 포인터를 *next로 지정 struct node *next; } node; 2. list라는 변수 생성하고 그곳에 node의 주소(포인터)가 들어감 int main(void) { // List of size 0 -> 연결리스트를 아무것도 없는 상태로 초기화(NULL) // 연결 리스트의 첫 번째 node 가리킴 // list라는 빈박스를 NULL로 표현(아무것도 들어가 있지 않아서) node *list = NULL; } 3. 새로운 node를 위한 메.. 2021. 12. 11.
6: 자료구조-3(연결 리스트: 도입) 자료 구조: C, C++, 자바, 파이썬에 있는 프로그래밍 구조 자료 구조는 컴퓨터 메모리에 정보를 각기 다른 방법으로 저장할 수 있도록 해 줌 데이터 구조는 우리가 컴퓨터 메모리를 더 효율적으로 관리하기 위해 서로 정의하는 구조체 일종의 메모리 레이아웃, 또는 지도라고 생각할 수 있음 1) 구조체(struct) - C에서 자신만의 구조를 만들 수 있는 키워드(예, person 구조체에 이름과 번호) 2) . 구조체의 속성 값에 접근할 때 사용(속성 값을 가져올 때 사용) 3) * 메모리 덩어리로 접근할 수 있는 역참조 연산자 배열 장점: 쉽게 인덱싱할 수 있음 단점: 고정된 값 배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있음 연결 리스트 : 각 값이 메모리 상의 여러 군데에 나뉘어 있어도.. 2021. 12. 11.
6: 자료구조-2(배열의 크기 조정하기) 리스트에 1, 2, 3을 할당하는 코드 작성 include int main(void) { int list[3]; list[0] = 1; list[1] = 2; list[2] = 3; for (int i = 0; i 2021. 12. 11.
6: 자료구조-1(malloc과 포인터 복습) int main(void) { int *x; int *y; x = malloc(sizeof(int)); *x = 42; *y = 13; } - main 함수 안에 첫 두 줄에서는 포인터 x와 y를 선언 - x에 malloc 함수를 이용해서 int 자료형 크기(4바이트)에 해당하는 메모리를 할당 - *은 역참조 연산자로 그 주소로 가라는 의미! - 다음에는 x와 y 포인터가 가리키는 지점에 42와 13을 저장함, 여기서 y는 포인터로만 선언되었을 뿐이지, 어디를 가리킬지에 대해서는 아직 정의가 되지 않았기 때문에 *y = 13은 문제가 됨 - 초기화되지 않은 y는 프로그램에서 임의로 가리키고 있는 곳에 13이라는 값을 저장하는 것이 오류를 발생시킴 -> y = x;라는 코드를 더해주면 y는 x가 가리키는 .. 2021. 12. 11.

티스토리툴바