반응형 척척학사/자료구조11 자료구조 트리 트리의 정의 트리는 나무를 거꾸로 매달아 놓은 것의 모양을 띄는 데이터를 구조화한 것으로 검색의 편리함, 논리적 계층, 계급적 특성을 갖고 있다. 이는 데이터를 사용하는 목적에 따라 추상화한다. 트리의 구성 노드 : 트리의 항목/트리에 저장되는 데이터의 묶음 부모노드와 자식노드 : 상하 계층구조가 있고 직접적으로 연결된 노드들로서 상위계층의 부모노드와 하위계층에 자식노드를 의미한다. 루트노드 : 트리의 최상위 노드(부모 노드가 없는) 서브트리 : 부모노드를 삭제하면 생기는 트리 잎노드 : 트리 맨 끝에 있으면서 자신의 서브트리를 갖지 않는 노드.(자식 노드가 없다) 진입/진출차수 루트노드 : 진입차수 = 0 루트노드를 제외한 모든 노드의 진입 차수 : 1 잎노드 : 진출 차수 = 0 내부 노드와 형제 내.. 2023. 10. 17. 연결 리스트의 응용 단순 연결 리스트는 하나의 링크 부분이 존재한다. 각각의 노드는 후행 노드만을 가리키는 구조이다. 따라서 특정 노드의 선행노드에 대한 접근은 해드 노드부터 재검색해야 한다. 이러한 단점 보완을 위해 선행 노드를 가리키는 링크부분과 후행노드를 가리키는 링크 부분을 갖는 이중 연결리스트가 제안되었다. 단순연 결리 시스트가 사용되지 않는 마지막 노드 링크 부분을 활용하면서도 프로그램 성능에 도움이 되도록 하기 위해서 원형 연결리스트가 제안되었다. 단순 연결 리스트의 마지막 노드의 링크가 처음 노드를 가리키게 하여 원형 연결 리스트를 만든다. 원형 연결 리스트는 한 방향으로 모든 노드가 원형으로 계속 연결되어 있기에 한 노드에서부터 다른 어떤 노드로도 접근할 수 있는 이점이 있다. 연결 리스트의 변형 단순 연결.. 2023. 10. 6. 자료구조 연결 리스트 리스트의 개념 리스트는 '물품이나 명칭 따위들을 일정한 순서로 적어 놓은 것'이라고 정의됩니다. 중요한 것은 일정한 순서를 이해해야 하는데 앞서 배열에서는 인덱스로 표현되는 순서가 배열원소의 메모리공간에서 물리적인 위치를 순서적으로 결정하는 특징을 공부했었다. 리스트에서의 순서는 어떤 정의에 의해 결정된 논리적인 순서라고 이해할 수 있다. 배열은 메모리 공간에서 물리적 순서를 의미했고, 리스트의 순서는 그런 것과 상관없이 사람들의 머릿속에 인식되는 논리적인 순서 또는 의미적 순서를 의미한다. 리스트 : 원소들 간의 순서가 지켜지며 유지되는 자료구조 리스트의 원소들 간의 순서 데이터가 저장되는 물리적 순서와 상관없이 인식되는 논리적인 순서/의미적 인순서 숫자 2,6,8,9를 예로 들어보자. 배열에서는 4라.. 2023. 9. 18. 큐 . 자료구조 큐의 개념 큐는 일상생활에서 많이 예를 들 수 있습니다. 택시를 타기 위해 서있는 줄, 급식소에서 급식판을 들고 순서를 기다리는등이 좋은 예입니다. 거기에 컴퓨터 시스템에서도 많이 사용됩니다. 큐는 가장 처음에 제출되어 작업 대기줄에 들어간 작업이 가장 처음에 처리되는 스케줄을 표현하는 자료구조인데요. 앞서 공부했던 스택에 비교하면 공정한 편이라고 할 수 있죠. 말이 나온 김에 스택은 한쪽이 막힌 관처럼 생각해서 입구와 출구가 동일했다면, 큐는 양쪽이 뚫린 관이고 양쪽모두에서 삽입연산과 삭제연산이 이루어질 수 있습니다. 하지만 양쪽모두에서 일어나면 혼란스러울 수 있어 제한을 두어 한쪽에서는 삽입만이 다른 한쪽에선 삭제만이 이루어지게 했습니다. 큐는 스택과 달리 먼저 삽입된 원소가 먼저 삭제되어 선입 선출.. 2023. 9. 7. 이전 1 2 3 다음 반응형
