C++中使用Struct的链表

Question

我没有得到create_node((函数中的else部分
正如你在其他部分看到的，内存块被分配给r，coeff和幂被分配但他们什么时候把r节点分配到链表的最后一个。。他们什么时候遍历到链表的末尾
我的意思是它是如何被分配到链表的最后一个的。

#include <bits/stdc++.h>
using namespace std;
struct Node {
int coeff;
int pow;
struct Node* next;
};
// Function to create new node
void create_node(int x, int y, struct Node** temp)
{
struct Node *r, *z;
z = *temp;
if (z == NULL) {
r = (struct Node*)malloc(sizeof(struct Node));
r->coeff = x;
r->pow = y;
*temp = r;
r->next = (struct Node*)malloc(sizeof(struct Node));
r = r->next;
r->next = NULL;
}
else {
r->coeff = x;
r->pow = y;
r->next = (struct Node*)malloc(sizeof(struct Node));
r = r->next;
r->next = NULL;
}
}
// Display Linked list
void show(struct Node* node)
{
while (node->next != NULL) {
printf("%dx^%d", node->coeff, node->pow);
node = node->next;
if (node->coeff >= 0) {
if (node->next != NULL)
printf("+");
}
}
}
// Driver code
int main()
{
struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL;
// Create first list of 5x^2 + 4x^1 + 2x^0
create_node(5, 2, &poly1);
create_node(4, 1, &poly1);
create_node(2, 0, &poly1);
// Create second list of -5x^1 - 5x^0
create_node(-5, 2, &poly2);
create_node(-5, 0, &poly2);
printf("1st Number: ");
show(poly1);
printf("n2nd Number: ");
show(poly2);
return 0;
}

是不是只有我一个人认为create_node((函数应该比上面的代码更像这样

void create_node(int x, int y, struct Node** temp)
{
struct Node *r, *z;
z = *temp;
if (z == NULL) {
r = (struct Node*)malloc(sizeof(struct Node));
r->coeff = x;
r->pow = y;
r->next=NULL;
*temp = r;
}
else {
r = (struct Node*)malloc(sizeof(struct Node));
r->coeff = x;
r->pow = y;
r->next=NULL;
while(z->next!=NULL)
{
z=z->next;
}
z->next=r;
}
}

我真的很想知道它是如何产生正确的输出的，即使没有将newnode分配到链接列表的最后一个

Answer 1

如果要编写C++程序，请使用运算符new来分配内存，而不是调用C函数malloc。

如果要将一个节点附加到列表的尾部，则最好使用双边单链列表。

第一个函数CCD_ 3没有意义，这是因为将除了数据成员next之外的未初始化的数据成员附加到伪节点上。

r->next = (struct Node*)malloc(sizeof(struct Node));
r = r->next;
r->next = NULL;

函数show可以调用未定义的行为，因为它不检查传递的指针是否等于nullptr。

// Display Linked list
void show(struct Node* node)
{
while (node->next != NULL) {
//...

作为C++函数的函数可以通过以下方式声明和定义，而不需要使用重复的代码。

void create_node( Node **head, int x, int y )
{
Node *new_node = new Node { x, y, nullptr };
while ( *head ) head = &( *head )->next;
*head = new_node;
}
std::ostream & show( const Node *head, std::ostream &os = std::cout )
{
for ( ; head != nullptr; head = head->next )
{
os << head->coeff << '^' << head->pow;
if ( head->next != nullptr ) os << " + ";
}
return os;
}

Answer 2

我没有得到create_node((函数中的else部分。。尽你所能请参阅其他部分，内存块被分配给r和coeff权力被分配了。。。但是他们什么时候把r节点分配给的最后一个链接列表。。他们什么时候遍历到链表的末尾它是如何被分配到链表的最后的的。

不是。当您传递一个nullNode*时，z将为null，并且您的else代码正在取消引用甚至尚未初始化的r。

// Function to create new node
void create_node(int x, int y, struct Node** temp)
{
struct Node *r, *z;
z = *temp;
if (z == NULL) {
r = (struct Node*)malloc(sizeof(struct Node));
r->coeff = x;
r->pow = y;
*temp = r;
r->next = (struct Node*)malloc(sizeof(struct Node));
r = r->next;
r->next = NULL;
}
else {
r->coeff = x;
r->pow = y;
r->next = (struct Node*)malloc(sizeof(struct Node));
r = r->next;
r->next = NULL;
}
}

我是唯一一个认为create_node((函数应该比上面的代码更像这个？

这似乎解决了上面的代码问题。在这里，您要创建一个Node并将其分配给r，然后将其附加在z的末尾(输入Node*(。不过请注意，您正在两个代码块中复制用于创建r的代码。你至少可以从if-else中去掉那部分。

void create_node(int x, int y, struct Node** temp)
{
struct Node *r, *z;
z = *temp;
if (z == NULL) {
r = (struct Node*)malloc(sizeof(struct Node));
r->coeff = x;
r->pow = y;
r->next=NULL;
*temp = r;
}
else {
r = (struct Node*)malloc(sizeof(struct Node));
r->coeff = x;
r->pow = y;
r->next=NULL;
while(z->next!=NULL)
{
z=z->next;
}
z->next=r;
}
}