행렬이 하나 있다고 가정하면 반복 접근 방식을 사용하여 이를 2차원 연결 목록으로 변환해야 합니다. 목록에는 오른쪽 및 아래쪽 포인터가 있습니다.
따라서 입력이 다음과 같으면
| 10 | 20 | 30 |
| 40 | 50 | 60 |
| 70 | 80 | 90 |
그러면 출력은
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
real_head :=NULL
-
크기가 m인 배열 head_arr을 정의합니다.
-
initialize i :=0의 경우 i
-
head_arr[i] :=NULL
-
j 초기화의 경우:=0, j
-
p :=값이 mat[i, j]
인 새 트리 노드 -
real_head가 null이면 -
-
real_head :=피
-
-
head_arr[i]가 null이면 -
-
head_arr[i] :=p
-
-
그렇지 않으면
-
right_ptr의 오른쪽 :=p
-
-
right_ptr :=p
-
-
-
initialize i :=0의 경우 i
-
p :=head_arr[i], q =head_arr[i + 1]
-
동안(p와 q 둘 다 null이 아님) −
-
아래로 p :=q
-
p :=p의 오른쪽
-
q :=q의 오른쪽
-
-
-
real_head 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int data;
TreeNode *right, *down;
TreeNode(int d){
data = d;
right = down = NULL;
}
};
void show_2d_list(TreeNode* head) {
TreeNode *right_ptr, *down_ptr = head;
while (down_ptr) {
right_ptr = down_ptr;
while (right_ptr) {
cout << right_ptr->data << " ";
right_ptr = right_ptr->right;
}
cout << endl;
down_ptr = down_ptr->down;
}
}
TreeNode* make_2d_list(int mat[][3], int m, int n) {
TreeNode* real_head = NULL;
TreeNode* head_arr[m];
TreeNode *right_ptr, *p;
for (int i = 0; i < m; i++) {
head_arr[i] = NULL;
for (int j = 0; j < n; j++) {
p = new TreeNode(mat[i][j]);
if (!real_head)
real_head = p;
if (!head_arr[i])
head_arr[i] = p;
else
right_ptr->right = p;
right_ptr = p;
}
}
for (int i = 0; i < m - 1; i++) {
TreeNode *p = head_arr[i], *q = head_arr[i + 1];
while (p && q) {
p->down = q;
p = p->right;
q = q->right;
}
}
return real_head;
}
int main() {
int m = 3, n = 3;
int mat[][3] = {
{ 10, 20, 30 },
{ 40, 50, 60 },
{ 70, 80, 90 } };
TreeNode* head = make_2d_list(mat, m, n);
show_2d_list(head);
} 입력
{ { 10, 20, 30 },
{ 40, 50, 60 },
{ 70, 80, 90 } } 출력
10 20 30 40 50 60 70 80 90