为可变大小的链表动态创建节点

Question

对于一项任务，我的任务是根据文件输入创建一个多维链表。每个节点都包含一个带有文件的行、列(作为字符(和字符数据的seat对象。例如，如果文件是

ABC
DEF
GHI

然后链接列表将是(其中-和|表示连接的指针(

A-B-C
| | |
D-E-F
| | |
G-H-I

我目前正在尝试根据文件中的元素数量，首先创建所有节点。我已经创建了head节点，但我不确定如何分配剩余的可变数量的节点。到目前为止，我有2个for循环遍历文件的每个字符，以收集行、列和字符，如下所示：

scanner.open(fileName);
if(scanner)
{
for(int i = 0; i < cols; i++)
{
for(int j = 0; j < rows; j++)
{
if(i == 0 && j == 0)
{
Node<Seat> *headNode = new Node<Seat>(Seat(j, letter, c));
headNode->up = NULL;
headNode->left = NULL;
setFirst(headNode);
continue;
}
scanner >> c;
letter = ('A' + i);
Node<Seat> *curNode = new Node<Seat>(Seat(j, letter, c));
std::cout << "Row, seat, ticket: " << curNode->getPayload().getRow() << curNode->getPayload().getSeat() << curNode->getPayload().getTicketType() << std::endl;
}
}
}
}

现在我正在创建一个新的节点，并将其打印出来以验证它是否工作(确实如此(，但我不确定如何为文件中的每个字符创建一个单独的新节点。(如果我能简单地创建它们，我想我就能弄清楚如何连接它们。(

Answer 1

我要做的是保留两组指针：

• a"；最后一行"；以及"；这一行"；用于跟踪行开头的指针
• a"；最后一列节点"最后一行节点"；以及"；这个节点"；用于跟踪兄弟姐妹的指针

然后重复这些步骤：

1. 从文件中读取名称
2. 创建节点
3. 勾搭兄弟姐妹
4. 更新指针；最后"指向"；这个">

这是一个示例：

#include <fstream>
#include <sstream>
#include <iostream>
#include <string>
struct Node {
std::string name;
Node *up, *down, *left, *right;
Node(std::string name) : name(name), up(NULL), down(NULL), left(NULL), right(NULL) {}
};
void dump(Node *this_node) {
std::cout
<< " name="  << this_node->name
<< " up="    << (this_node->up?this_node->up->name:" ")
<< " down="  << (this_node->down?this_node->down->name:" ")
<< " left="  << (this_node->left?this_node->left->name:" ")
<< " right=" << (this_node->right?this_node->right->name:" ")
<< std::endl;
}
Node *print(Node *head) {
Node *this_row = head;
while (this_row) {
Node *this_node = this_row;
while (this_node) {
dump(this_node);
this_node = this_node->right;
}
this_row = this_row->down;
}
return head;
}
Node *read() {
Node *head = NULL;
std::fstream file("input.txt");
if (file) {
std::string line;
Node *last_row = NULL;
Node *this_row = NULL;
while (std::getline(file,line)) {
std::string name;
std::stringstream ss(line);
Node *last_row_node = NULL;
Node *last_col_node = last_row;
Node *this_node = NULL;
while (ss >> name) {
this_node = new Node(name);
// if we haven't set these yet then do it now
if (!head) head = this_node;
if (!this_row) this_row = this_node;
// if there was a last column then use it
if (last_col_node) {
last_col_node->down = this_node;
this_node->up = last_col_node;
}
// if there was a last row then use it
if (last_row_node) {
last_row_node->right = this_node;
this_node->left = last_row_node; 
}
// move right one column
last_row_node = this_node;
if (last_col_node)
last_col_node = last_col_node->right;
}
// move down one row
last_row = this_row;
this_row = NULL;
}
}
return head;
}
int main() {
Node *head = read();
print(head);
}

在线试用：https://onlinegdb.com/HyW7SrY8v

这是它创建的网格：

name=A up=  down=D left=  right=B
name=B up=  down=E left=A right=C
name=C up=  down=F left=B right= 
name=D up=A down=G left=  right=E
name=E up=B down=H left=D right=F
name=F up=C down=I left=E right= 
name=G up=D down=  left=  right=H
name=H up=E down=  left=G right=I
name=I up=F down=  left=H right= 

Answer 2

IMHO，每个节点中需要四个链接。想象一下棋盘。

struct Node
{
Node * up;
Node * down;
Node * left;
Node * right;
};

对于up字段，最上面一行将具有nullptr值。其他边也是如此。

添加节点需要调整适当的链接。