数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学使用C++迭代法从二维矩阵构造链表
假设我们有一个矩阵，我们需要使用迭代法将其转换为二维链表。该链表将具有右指针和下指针。
因此，如果输入如下：
| 10 | 20 | 30 |
| 40 | 50 | 60 |
| 70 | 80 | 90 |
那么输出将是
为了解决这个问题，我们将遵循以下步骤：
real_head := NULL
定义一个大小为m的数组head_arr。
对于初始化 i := 0，当 i < m，更新（i增加1），执行：
head_arr[i] := NULL
对于初始化 j := 0，当 j < n，更新（j增加1），执行：
p := 一个值为mat[i, j]的新树节点
如果real_head为null，则：
real_head := p
如果head_arr[i]为null，则：
head_arr[i] := p
否则
right_ptr的right := p
right_ptr := p
对于初始化 i := 0，当 i < m - 1，更新（i增加1），执行：
p := head_arr[i]，q = head_arr[i + 1]
当(p和q都不为null)时，执行：
p的down := q
p := p的right
q := q的right
返回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
更新于：2020年8月27日
161 次浏览
广告