트리(tree) 트리는 계층적인 구조를 나타내는 비선형 자료구조입니다. 트리는 부모-자식 관계의 노드들로 이루어지며 트리를 응용한 분야로는 계층적 조직을 표현하거나 컴퓨터 파일들의 디렉토리 구조 조직, 인공지능에서의 결정 트리 등이 있습니다. 트리의 용어 노드(node) : 트리의 구성 요소입니다. 루트(root) : 부모가 없는 최상위 노드입니다. 서브 트리(subtree) : 하나의 노드와 그 노드들의 자손들의 이루어진 트리입니다. 단말노드(terminal node) : 자식이 없는 노드입니다. 비단말노드 : 적어도 하나의 자식을 가지는 노드입니다. 자식, 부모, 형제, 조상, 자손 노드: 용어 그대로의 의미입니다. 레벨(level) : 트리의 각층의 번호입니다. 높이(height) : 트리의 최대 ..

연결리스트로 구현한 스택 스택을 구현하는 데 있어서 연결리스트를 활용할 수 있습니다. 연결리스트로 스택을 구성하면 배열로 구성된 스택에 비해 크기의 제한이 없다는 장점이 있지만 반대로 메모리를 동적으로 할당하므로 할당과 해제에 따른 시간이 소모된다는 단점이 있습니다. 삽입 연산 연결리스트로 구현된 스택에 노드를 삽입하는 연산의 경우 다음 두 순서의 변경 사항이 필요합니다. 1. temp(삽입할 노드)의 link를 top으로 할당. 2. top을 temp로 할당. 이때 순서가 변경되어서는 안됩니다. 만약 top을 temp로 할당하는 과정을 먼저 수행하면 temp의 link가 가리킬 위치를 알 수 없게됩니다. 삭제 연산 연결리스트로 구현된 스택에 노드를 삭제하는 연산의 경우 다음 두 순서의 변경 사항이 필요..

파일시스템과 파일 입출력 : fopen(), fclose(), fgetc(), fputc() 연습문제 01-01. 명령줄 인수로 받은 텍스트 파일내의 문자의 수와 줄의 수를 출력하는 프로그램 ch12wc.c를 작성한다. 실행결과 01-02. 파일1에 파일2의 내용을 추가하는 프로그램 ch12append.c를 작성하라. 실행결과 01-03. 입력 파일의 홀수 줄 만을 출력 파일에 저장하는 프로그램 ch12cp.c를 작성하라. 실행결과 01-04. ch12cp의 입력파일과 출력파일을 diff로 비교해 보고 설명한다. 2d1 : origin.txt의 line2를 삭제하면 copied.txt의 line1과 같다. 4d2 : origin.txt의 line4를 삭제하면 copied.txt의 line2와 같다. 6d..

이중 연결리스트 이중 연결리스트는 각 노드가 선행 노드와 후속 노드에 대한 링크를 가지는 리스트입니다. 아래 그림처럼 노드의 왼쪽 링크(left link)와 오른쪽 링크(right link)가 각각 다른 노드의 오른쪽 링크와 왼쪽 링크를 연결짓고 있으며 특별하게 헤드도 노드로 이루어져 있습니다. 헤드노드 헤드노드는 데이터를 가지지 않고 오로지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드입니다. 따라서 헤드 포인터와의 구별이 필요하며 리스트가 공백상태라면 헤드 노드만 존재하는 상태입니다. 이때 헤드노드의 left link는 right link를 가리키며 right link는 left link를 가리키는 상태입니다. 삽입 연산 new_node를 before의 앞쪽에 삽입하는 연산입니다. (1)은 ..

gcc compile 연습문제 01-01. 다음 순서에 따라 수행하고 설명한다. test.c 파일을 컴파일하여 test0 실행 파일을 만든다. test.c 파일을 최적화 컴파일하여 test1 실행 파일을 만든다. (옵션 -O1 사용) test.c 파일을 최적화 컴파일하여 test2 실행 파일을 만든다. (옵션 -O2 사용) test.c 파일을 최적화 컴파일하여 test3 실행 파일을 만든다. (옵션 -O3 사용) diff 명령어를 사용하여 test0, test1, test2, test3가 같은지 다른지 확인한다. 01-02. 위 실행파일들의 수행 시간을 time 명령어로 측정 및 비교한다. 최적화 컴파일을 하지 않은 test0에서는 가장 느린 속도를 보였고 최적화 컴파일 -O1옵션으로 컴파일하니 속도가 ..

원형 연결리스트 원형 연결리스트에서 head 포인터는 마지막 노드를 가리키게 됩니다. 이러한 방식의 원형 리스트는 head는 마지막 노드를, head의 link는 첫 노드를 가리키므로 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 편리해집니다. 앞부분 삽입 연산 노드를 리스트의 첫 부분에 삽입하는 연산의 경우 두 가지의 변경 사항이 필요합니다. 1. node의 link를 head의 link로 할당 2. head의 link를 node로 할당 [중요] 이때 순서가 변경되어서는 안됩니다. 만약 2를 먼저 실행, 즉 head의 link를 먼저 변경해버리면 node의 link를 지정해 줄 주소를 알 수 없게됩니다. // 앞 삽입 ListNode* insert_first(ListNode* head, elemen..