[자료구조] 6. 연결리스트의 응용

연결 리스트의 변형 연결 리스트 종류 단일 연결 리스트 이중 연결 리스트 단일/이중 원형 연결 리스트 단일 연결 리스트 헤드부터 순차적으로 검색 이중 연결 리스트 특정 노드의 선행 노드에 접근하기 용이하도록 개선 원형 연결 리스트 꼬리 노드의 링크가 항상 Null 인 것을 개선하여 처음으로 돌아갈 수 있도록 개선 (검색성능 향상) 이중 원형 연결 리스트 이중 연결 리스트와 원형 연결 리스트의 장점을 합친 것으로, 연결리스트 내에서 선행 노드와 후행 노드의 접근이 자유로우며 첫 노드와 마지막 노드를 연결해두어 순환구조로 인덱싱을 한층 더 자유롭게 만든 자료구조 이다.

• format_list_bulleted 노트/자료구조
• · 2022. 1. 27.
• textsms

[자료구조] 5. 연결 리스트

5장. 연결 리스트 EX) C언어 프로그램 실행 중 구조체 메모리 할당 int a, *p_a; float b, *p_b; p_a = (int*)malloc(sizeof(int)); p_b = (float*)malloc(sizeof(float)); *p_a = 10; 1. 리스트의 개념 ❗ **논리적인 순서에 의해 결정된 원소들의 나열 → 물리적인 순서와 무관하게 논리적인 순서만 유지** 2. 배열을 이용한 리스트 구현 배열을 이용하여 리스트를 구현한 자료형 배열로 구성한 리스트 중간 인덱스에 자료가 삽입되는 경우 배열을 이용하여 리스트를 구현하면, 논리적인 순서와 함께 물리적인 순서 또한 일정하게 유지 된다. 이로 인해 중간에 데이터를 삽입이나 삭제하는 경우가 생긴다면 뒤의 인덱스 자료형들의 물리적 공간..

• format_list_bulleted 노트/자료구조
• · 2022. 1. 6.
• textsms

[자료구조] 4. 큐

4강. 큐 1. 큐의 개념 ⭐ **가장 먼저 대기 줄에 들어간 작업이 가장 처음에 처리되는 작업 (First-In-First-Out) 한 쪽에서 삭제, 다른 한 쪽에서 삽입 연산이 발생한다.** queue 의 자료 입출력 2. 큐의 추상 자료형 Queue Create_q(maxQueueSize) 큐의 크기가 maxStackSize인 빈 큐를 생성하고 반환한다. Boolean IsFull_q(queue, maxQueueSize) 큐에 저장되어있 자료의 갯수를 파악하여 저장공간이 남아 있는지 확인한다. Queue Add_q(queue, item) 큐에 저장공간이 있다면 rear 영역에 item을 삽입한다. Boolean IsEmpty_q(queue) 큐의 front 포인터와 rear 포인터가 같은 주소를 가..

• format_list_bulleted 노트/자료구조
• · 2022. 1. 6.
• textsms

[자료구조] 3. 스택

3강. 스택 1. 스택의 개념 💡 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형 가장 나중에 들어온 자료가 가장 먼저 나가는 형태(LIFO, 후입선출) TOP : 스택에서 가장 최근에 삽입 된 자료의 메모리 주소를 지칭 push : 스택에 자료 하나를 삽입하는 함수. 스택의 저장공간이 충분한지 확인해야 한다. pop : 스택의 최상단 자료형을 반환(제거) 하는 함수. 스택에 데이터가 존재하는지 확인해야 한다. 2. 스택의 추상 자료형 Stack CreateS(maxStackSize) 스택의 크기가 maxStackSize인 빈 스택을 생성하고 반환한다. Boolean IsFull(stack, maxStackSize) 스택이 가득 찼는지 여부를 확인하여 반환한다. Stack Push(s..

• format_list_bulleted 노트/자료구조
• · 2022. 1. 6.
• textsms

[자료구조] 2. 배열

1. 배열의 정의 💡 배열 : 일정한 차례와 간격에 따라 벌여 놓은 자료형 1.1 배열의 정의 인덱스와 원소값(index, value) 의 쌍으로 구성된 집합으로 정의된 각 인덱스는 그 인덱스와 관련된 값을 가진다. 1.2 배열의 특성 원소들이 모두 같은 자료형, 즉 동질의 값과 기억 공간의 크기가 같다. 배열의 각 원소의 물리적인 위치(메모리 주소)의 순서가 배열의 인덱스 순서(논리적 순서) 와 일치한다. 배열의 인덱스 값을 이용해서 배열의 원소값에 직접 접근(direct access) 한다. → 배열의 인덱스 번호는 사람(개발자)가 이해할 수 있도록 정의한 (추상화) 값이다. 배열에서 인덱스 번호를 알고 있을 때 원소를 찾아내는 방법의 시간복잡도를 O(1)로 두는 이유에 대해 궁금했었는데, 이는 배열..

• format_list_bulleted 노트/자료구조
• · 2021. 12. 20.
• textsms

[자료구조] 1. 자료구조란 무엇인가

1. 자료와 정보의 관계자료(Data)현실 세계에서 관찰이나 측정을 통해 수집된 값(Value) 이나 사실(Fact). 정보(Information) 적절한 의사결정(decision)을 할 수 있도록 하는 지식(knowledge) 으로서, 자료의 유효한 해설(interpretation)이나 자료 상호관의 관계(relationship) 을 표현하는 내용 자료 ⇒ 처리(컴퓨터) ⇒ 정보 I = P(D) 2. 추상화의 개념추상화공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것 3. 자료구조의 개념자료구조(Data Structure) 란?자료 사이의 논리적 관계를 컴퓨터나 프로그램에 적용하기 위해 실시하는 자료의 추상화 알고리즘컴퓨터가 어떤 수행을 실시하기 위해 필요한 명령의 집합 복잡한 데이터와 ..

• format_list_bulleted 노트/자료구조
• · 2021. 12. 20.
• textsms