[요약] 자료 구조 - 2 [순차(행렬), 선형(1, 2, 3차원 배열), 연결(단순, 원형, 이중, 다항식) 자료 구조]

※ 주의 ※
이 블로그는 어디까지나 CS관련 지식을 정리하는 것이 목적입니다. 제가 이해한 내용이 잘못 된 것 같다면 댓글로 남겨주세요. 여러분의 관심이 저의 지식 함양에 도움이 됩니다.

>> 순차 자료 구조와 선형 자료 구조 리스트 

• 순차 자료구조는 논리적 순서와 물리적 순서가 항상 일치하는 메모리 연속 저장 방식이다.
• 포인터는 주소를 가리키는 변수로, C 프로그래밍에서 순차 자료구조를 구현하는 기법은 배열이다.
• 선형 리스트는 원소들을 순서대로 나열한 리스트로, 순서 리스트라고도 한다.
• 이러한 리스트는 자료들 간에 순서를 유지하며 데이터를 처리한다.

>> 선형 리스트 저장, 삽입, 삭제 

• 선형 리스트에서 원소는 논리적 순서대로 메모리에 연속 저장된다.
• 원소를 삽입할 때, 삽입된 위치 이후의 원소들은 한 자리씩 뒤로 이동하여 물리적 순서와 논리적 순서를 일치시킨다.
• 원소를 삭제할 때는, 삭제된 자리 이후의 원소들이 한 자리씩 앞으로 이동하여 순서를 맞춘다.
• 이 과정에서 빈 자리가 생기거나 원소의 위치가 변경된다.

>> 1차원 배열 

• 1차원 배열을 사용하면 선형 리스트를 간단하게 구현할 수 있다.
• 배열은 메모리에 연속적으로 저장된 원소들로 구성되며, 각 원소는 인덱스를 통해 순서를 표현한다.
• 인덱스는 배열의 원소 순서를 나타내며, 1차원 배열은 하나의 인덱스를 사용하여 원소를 구별한다.
• 이러한 방식으로, 간단한 선형 리스트를 효율적으로 표현하고 관리할 수 있다.

>> 2차원 배열 

• 2차원 배열을 사용하여 선형 리스트를 구현할 때, 데이터의 순서 기준이 두 가지인 경우 행과 열 인덱스를 가진 배열을 활용한다.
• 2차원 배열은 논리적으로 행과 열 구조로 표현되지만, 실제 메모리에는 1차원 구조로 저장된다.
• 행의 개수가 ni, 열의 개수가 nj인 2차원 배열 A[ni][nj]의 시작 주소가 α이고, 원소의 길이가 ℓ이라면, A[i][j]의 물리적 위치는 다음과 같이 계산된다:
  • 행 우선 순서는 α + (i × nj + j) × ℓ, 열 우선 순서는 α + (j × ni + i) × ℓ이다.

>> 3차원 배열 

• 3차원 배열을 이용하여 선형 리스트를 구현할 때, 데이터의 순서 기준이 면, 행, 열로 구분되는 경우에는 면, 행, 열 인덱스를 가진 배열을 사용한다.
• 3차원 배열은 논리적으로 면, 행, 열의 구조로 표현되지만, 메모리에는 1차원 구조로 저장된다.
• 면의 개수가 ni, 행의 개수가 nj, 열의 개수가 nk인 3차원 배열 A[ni][nj][nk]에서 시작 주소가 α이고 원소의 길이가 ℓ이라면, A[i][j][k]의 물리적 위치는 면 우선 순서로는 α + {(i × nj × nk) + (j × nk) + k} × ℓ, 열 우선 순서로는 α + {(k × nj × ni) + (j × ni) + i} × ℓ로 계산된다.

>> 행렬 순차 자료 구조 

• 희소 행렬은 대부분의 원소가 0인 행렬로, 메모리 효율성을 높이기 위해 0이 아닌 원소만 저장하는 방법을 사용한다.
• 행렬은 행과 열로 구성되며, m × n 행렬은 m개의 행과 n개의 열을 가진다.
• 정방 행렬은 행과 열의 수가 같은 행렬이고, 전치 행렬은 행과 열을 바꾼 행렬이다.
• 희소 행렬을 2차원 배열로 표현할 때는 0이 아닌 원소를 <행번호, 열번호, 원소> 쌍으로 저장하고, 이 쌍들을 2차원 배열의 행으로 저장하며, 원래 행렬의 정보는 순서쌍 형태로 0번 행에 저장한다.

>> 순차 자료 구조와 연결 자료 구조 

• 순차 자료 구조
  • 순차 자료구조의 문제점은 삽입이나 삭제 연산 후에 원소들을 이동시켜 연속적인 물리 주소를 유지해야 하는 추가 작업과 시간 소요가 발생한다.
  • 이로 인해 원소 개수가 많고 삽입·삭제 연산이 빈번할 경우 성능 저하가 발생한다.
  • 또한, 배열을 사용하기 때문에 메모리 할당이 연속적으로 이루어져야 하며, 메모리 사용의 비효율성 문제가 있다.
• 연결 자료 구조
  • 반면, 연결 자료구조는 논리적인 순서와 물리적인 순서가 불일치하며, 각 원소가 다음 원소의 주소를 저장하여 순서를 연결한다.
  • 이로 인해 순서 맞추기 위한 오버헤드가 없으며, 여러 개의 작은 공간을 연결하여 유연한 크기 조절과 효율적인 메모리 사용이 가능하다.

>> 선형 VS 연결 리스트 

• 선형 리스트
  • 구성: 배열을 사용하여 원소들을 연속적으로 저장한다.
  • 특징: 원소의 삽입이나 삭제 시에 원소들을 이동시켜야 하며, 메모리 할당이 연속적이다.
  • 장점: 인덱스를 통해 빠르게 원소에 접근할 수 있다.
  • 단점: 삽입과 삭제 연산에서 성능 저하가 발생할 수 있으며, 메모리 할당이 비효율적일 수 있다.
• 연결 리스트
  • 구성: 노드(Node)로 구성되며, 각 노드는 <원소, 주소> 단위로 이루어져 있다. 데이터 필드(Data Field)는 원소 값을 저장하고, 링크 필드(Link Field)는 다음 노드의 주소를 저장한다.
  • 특징: 링크 필드는 포인터 변수로 주소값을 저장하며, 포인터, 링크 또는 참조(Reference)라고도 한다. 노드는 동적으로 메모리에서 할당되며, 노드 간의 연결로 데이터를 저장한다.
  • 장점: 삽입과 삭제 연산이 용이하고, 메모리 할당이 비연속적이다.
  • 단점: 원소 접근 속도가 느릴 수 있으며, 링크 필드로 인해 추가 메모리가 필요하다.

>> 단순 연결 리스트 

• 단순 연결 리스트는 노드가 하나의 링크 필드를 통해 다음 노드와 연결되는 구조를 가진다.
• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성된 구조체로 구현된다.
• 연결 리스트는 자주 변경되는 상황에서 배열 리스트보다 비용 측면에서 더 효율적이다.

>> 단순 연결 리스트 삽입 

1. 삽입할 노드를 준비한다: 새로운 노드를 생성한다.
2. 새 노드의 데이터 필드값을 저장한다: 새 노드의 데이터 필드에 삽입할 데이터를 저장한다.
3. 새 노드의 링크 필드값을 지정한다: 새 노드의 링크 필드를 현재 노드의 다음 노드를 가리키도록 설정한다. 즉, 새 노드가 삽입될 위치의 이전 노드가 새 노드를 가리키도록 한다.
4. 리스트의 앞 노드에 새 노드를 연결한다: 삽입할 위치의 이전 노드의 링크 필드를 새 노드를 가리키도록 업데이트한다.

>> 단순 연결 리스트 삭제 

1. 삭제할 노드의 앞 노드(선행자)를 찾는다: 삭제할 노드의 위치를 찾기 위해 리스트를 순회하여 삭제할 노드의 바로 앞에 위치한 노드를 찾는다.
2. 앞 노드에 삭제할 노드의 링크 필드값 저장한다: 앞 노드의 링크 필드를 삭제할 노드의 다음 노드를 가리키도록 업데이트한다. 즉, 앞 노드가 삭제할 노드의 후속 노드를 가리키도록 한다.
3. 삭제한 노드의 앞 노드와 삭제한 노드의 다음 노드를 연결한다: 삭제할 노드를 리스트에서 제거하고, 앞 노드와 삭제할 노드의 다음 노드가 연결되도록 한다. 삭제할 노드는 메모리에서 해제한다.

>> 단순 연결 리스트 노드 탐색 

1. 리스트의 시작 주소를 포인터 temp에 저장한다: 포인터 temp를 리스트의 시작 주소로 초기화한다.
2. temp가 NULL이 아닐 때까지 탐색을 반복한다: temp가 NULL이 아닐 동안 (즉, 리스트의 끝에 도달할 때까지) 반복한다.
3. 현재 노드의 데이터 필드 값과 탐색 값 x를 비교한다: temp가 가리키는 노드의 데이터 필드 값이 탐색 값 x와 같으면, 탐색 성공으로 현재 노드를 반환한다.
4. temp가 가리키는 노드의 데이터 필드 값이 탐색 값 x와 같지 않으면: temp를 현재 노드의 링크 필드를 따라 다음 노드로 이동한다.
5. temp가 NULL인 경우: 탐색 값 x가 리스트에 없다는 의미로 탐색 실패를 나타내며, NULL을 반환한다.

>> 원형 연결 리스트 

• 원형 구조: 단순 연결 리스트의 마지막 노드가 리스트의 첫 번째 노드를 가리키도록 하여, 리스트가 원형으로 연결된다. 이로 인해 리스트를 끝없이 순회할 수 있다.
• 링크 필드: 단순 연결 리스트와 마찬가지로 각 노드는 데이터 필드와 링크 필드로 구성된다. 그러나 원형 연결 리스트에서는 마지막 노드의 링크 필드에 첫 번째 노드의 주소가 저장된다.
• 순회: 링크를 따라 계속 순회하면 리스트의 처음으로 돌아오므로, 이전 노드에 접근할 수 있다. 리스트를 무한히 순회할 수 있는 구조를 가지며, 리스트의 시작과 끝이 명확히 구분되지 않는다.

>> 원형 연결 리스트 삽입 

• 기본 동작: 단순 연결 리스트에서의 삽입 연산과 유사하지만, 마지막 노드의 링크 필드가 첫 번째 노드를 가리키도록 연결한다.

>> 원형 연결 리스트 삭제 

• 포인터 사용: pre와 old 포인터를 사용한다.
• 삭제 과정:
  • pre 포인터는 삭제할 노드 old의 바로 앞 노드를 가리킨다.
  • pre의 링크 필드를 old의 다음 노드를 가리키도록 업데이트한다.
  • old 노드는 리스트에서 제거된다.

>> 이중 연결 리스트 

• 양방향 순회: 노드가 양쪽 방향으로 순회할 수 있도록 연결되어 있다. 이중 연결 리스트에서는 각 노드가 두 개의 링크 필드를 통해 양방향으로 연결된다.
• 왼쪽 링크 필드 (llink): 노드의 왼쪽 노드와 연결하는 포인터를 저장한다. 이를 통해 현재 노드의 이전 노드에 접근할 수 있다.
• 오른쪽 링크 필드 (rlink): 노드의 오른쪽 노드와 연결하는 포인터를 저장한다. 이를 통해 현재 노드의 다음 노드에 접근할 수 있다.

>> 이중 연결 리스트 삽입 

1. 삽입할 노드 준비: 새로운 노드를 생성하고 데이터 필드에 값을 저장한다.
2. 왼쪽 노드와의 연결:
   • 왼쪽 노드의 오른쪽 링크 필드를 새 노드의 주소로 업데이트한다.
   • 새 노드의 왼쪽 링크 필드에 왼쪽 노드의 주소를 저장한다.
3. 오른쪽 노드와의 연결:
   • 오른쪽 노드의 왼쪽 링크 필드를 새 노드의 주소로 업데이트한다.
   • 새 노드의 오른쪽 링크 필드에 오른쪽 노드의 주소를 저장한다.

>> 이중 연결 리스트 삭제 

1. 삭제할 노드의 주변 노드 찾기: 삭제할 노드의 오른쪽 및 왼쪽 노드를 찾는다.
2. 연결 업데이트:
   • 오른쪽 노드의 왼쪽 링크 필드를 삭제할 노드의 왼쪽 노드 주소로 업데이트한다.
   • 왼쪽 노드의 오른쪽 링크 필드를 삭제할 노드의 오른쪽 노드 주소로 업데이트한다.
3. 노드 제거: 삭제할 노드는 리스트에서 제거된다.

•  

>> 다항식 연결 자료 구조 

• 항의 표현: 다항식의 각 항은 연결 리스트의 노드로 표현된다. 즉, 다항식의 각 항이 하나의 노드로 관리된다.
• 데이터 필드:
  • 계수 (coef): 각 항의 계수를 저장하는 필드.
  • 지수 (expo): 각 항의 지수를 저장하는 필드.
• 링크 필드: 다음 항을 연결하는 포인터로 구성되어 있다. 이를 통해 각 항이 리스트에서 다음 항과 연결된다.

>> 다항식 연결 자료 구조 삽입 

1. 새 노드 생성:
   • 새로운 항을 나타내는 노드를 생성한다.
   • 생성된 노드의 coef 필드에 계수를 저장하고, expo 필드에 지수를 저장한다.
2. 위치 결정:
   • 삽입할 위치를 결정한다. 일반적으로 다항식의 항들은 지수에 따라 내림차순으로 정렬되므로, 적절한 위치를 찾기 위해 리스트를 순회하여 삽입할 위치를 결정한다.
3. 링크 업데이트:
   • 리스트가 비어 있는 경우: 새 노드가 리스트의 첫 번째 노드가 된다. 이 경우, 리스트의 헤드 포인터를 새 노드를 가리키도록 설정한다.
   • 리스트가 비어 있지 않은 경우:
     • 삽입할 위치의 이전 노드와 다음 노드를 찾아야 한다.
     • 새로운 노드의 link 필드를 삽입할 위치의 노드를 가리키도록 설정한다.
     • 이전 노드의 link 필드를 새 노드를 가리키도록 업데이트한다.
4. 마지막 노드에 삽입할 경우:
   • 리스트의 마지막 노드를 찾고, 그 노드의 link 필드를 새 노드를 가리키도록 업데이트한다.
   • 새 노드의 link 필드는 NULL로 설정하여 리스트의 끝을 나타낸다.

>> 다항식 연결 자료 덧셈 

1. 포인터 초기화:
   • 포인터 p: 다항식 A(x)A(x)A(x)의 현재 항을 가리킨다.
   • 포인터 q: 다항식 B(x)B(x)B(x)의 현재 항을 가리킨다.
   • 포인터 r: 결과 다항식 C(x)C(x)C(x)의 현재 항을 가리킨다.
2. 항 비교 및 덧셈:
   • 두 다항식의 현재 항을 비교하여 지수가 같은 경우, 계수를 더하여 결과 항에 저장한다.
   • 지수가 다른 경우, 지수가 더 큰 항을 결과 다항식에 복사하고, 지수가 같은 항이 나올 때까지 계속 비교한다.
3. 항 이동:
   • 포인터 p 또는 **포인터 q**를 다음 항으로 이동시킨다.
   • 항 비교 후, 지수가 같은 항이 더 이상 없을 때까지 계속 진행한다.
4. 결과 다항식 생성:
   • 다항식 A(x)A(x)A(x)와 B(x)B(x)B(x)의 모든 항을 처리한 후, 포인터 r이 결과 다항식의 끝을 가리킬 때까지 진행한다.
   • 만약 하나의 다항식이 더 남아있다면, 그 항들을 결과 다항식에 추가한다.