링크드 리스트를 만들어서 사전을 만드는 것을 진행할 것 - 사전.
2차원 링크드 리스트.
처음에 관측한 단어가 id가 0이다. 관측되지 않은 단어에 한해서 id를 하나씩 올려가면서 할당을 하게 된다.
17장 동적메모리와 연결리스트
동적 할당 메모리의 개념
- 프로그래밍 메모리를 할당 받는 방법
- 정적(static)
- 동적(dynamic)
- 정적 메모리 할당
- 프로그램이 시작되기 전에 미리 정해진 크기의 메모리를 할당받는 것
- 메모리의 크기는 프로그램이 시작하기 전에 결정
- 동적 메모리
- 실행 도중에 동적으로 메모리를 할당 받는 것
- 사용이 끝나면 시스템에 메모리를 반납
- malloc() 계열의 라이브러리 함수를 사용
- malloc()과 free()
- 바이트 단위로 메모리 할당
- size는 바이트의 수
- malloc()함수는 메모리 블럭의 첫 번쨰 바이트에 대한 주소를 반환
- 요청한 메모리 공간을 할당할 수 없는 경우 NULL 값을 반환
- free()는 동적으으로 할당되었던 메모리 블록을 시스템에 반납
- ptr은 malloc()을 이용하여 동적 할당된 메모리를 가리키는 포인터
- 예제
calloc()과 realloc()
- calloc()은 malloc()과 다르게 0으로 초기화된 메모리 할당
- realloc()함수는 할당하였던 메모리 블록의 크기를 변경
연결 리스트
- 배열(array)
- 장점 : 구현이 간단하고 빠르다
- 단점 : 크기가 고정된다. 중간에서 삽입, 삭제가 어렵다
- 연결 리스트 (linked list)
- 각각의 원소가 포인터를 사용하여 다음 원소의 위치를 가리킨다. (자기 참조 구조체 할 때 배움)
연결리스트의 장단점
- 중간에 데이터를 삽입, 삭제하는 경우
- 데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들어서 쉽게 추가
- 구현이 어렵고 오류가 나기 쉽다.
연결 리스트의 구조
-
노드(node) = 데이터 필드(data field) + 링크 필드(link field)
-
헤드 포인터(head pointer) : 첫 번째 노드를 가리키는 포인터
(링크 필드와 데이터 필드의 제약이 없다.뭘 넣어도 상관 없다)
자기 참조 구조체
구성 멤버중에 같은 타입의 구조체를 가리키는 포인터가 존재하는 구조체
간단한 연결 리스트 생성
과제 할 때,
디버거를 써야한다. 디버깅 하는게 쉽지 않을 거야. 링크드 리스트를 쓰게 되면. 디버깅 하는게 쉽지 않을 거야.
디버깅 - 몇 번쨰 라인에서 브레이크 포인트를 걸어줄 수 있어. 12번에서 설정하면 멈춤. 그리고 12번째 메모리상태를 들고 온다. 디버거는 한줄 한줄 실행시키면서 메모리가 어떻게 바뀌는지 실행을 시켜준다. 죽는 라인이 어딘지 알 수 있다. gdb 사용법 디버거 활용할 수 있다.gdb 없으면 굉장히 힘들어진다.
참고자료