c-修复反向链接

Question

嘿，由于某种原因，我的链表以相反的顺序打印，例如，如果我的输入是2->4->6我的输出是6->4->2

list* add_int_list(list* a,int b)
{
list *temp;
temp = (list*)malloc(sizeof(list*));
temp->next = NULL;
if (a->next == NULL)//insert to the first node
{
temp->data = b;
temp->next = a;
a = temp;
}
else 
{
temp->data = b;
temp->next = a;
a = temp;//I think the problem is here, couldnt find how to fix 
}

Answer 1

对于此语句中的启动器

temp = (list*)malloc(sizeof(list*));
^^^^^

分配了大小等于指针的大小而不是节点的大小的存储器。你必须写任意一个

temp = (list*)malloc(sizeof(list));

或

temp = (list*)malloc(sizeof( *temp));

此if语句

if (a->next == NULL)

可以调用未定义的行为，因为最初列表可以为空。因此指针a可以等于NULL。也就是说，使用了一个空指针来访问内存。

在if-else语句的if和else部分之后的这两个代码块之间没有区别

if (a->next == NULL)//insert to the first node
{
temp->data = b;
temp->next = a;
a = temp;
}
else 
{
temp->data = b;
temp->next = a;
a = temp;//
}

这是两个代码片段都尝试在列表的开头插入一个新节点。

这是一种通用的方法，在一个单独链接的单边列表的开头插入一个新节点。将一个节点附加到这样的列表的末尾是低效的，因为必须遍历整个列表。

如果要将节点附加到单链列表的末尾，请将其设置为双面。

这是一个示范节目。

#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node *next;
} Node;
typedef struct List
{
Node *head;
Node *tail;
} List;
int push_front( List *list, int data )
{
Node *new_node = malloc( sizeof( Node ) );
int success = new_node != NULL;
if ( success )
{
new_node->data = data;
new_node->next = list->head;
list->head = new_node;
if ( list->tail == NULL ) list->tail = list->head;
}
return success;
}
int push_back( List *list, int data )
{
Node *new_node = malloc( sizeof( Node ) );
int success = new_node != NULL;
if ( success )
{
new_node->data = data;
new_node->next = NULL;
if ( list->tail == NULL )
{
list->head = list->tail = new_node;
}
else
{
list->tail = list->tail->next = new_node;
}
}   
return success;
}
void output( const List *list )
{
for ( const Node *current = list->head; current != NULL; current = current->next )
{
printf( "%d -> ", current->data );
}
puts( "null" );
}
int main(void) 
{
List list = { .head = NULL, .tail = NULL };
const int N = 10;
for ( int i = 0; i < N; i++ )
{
if ( i % 2 != 0 )
{
push_front( &list, i );
}
else
{
push_back( &list, i );
}
output( &list );
}
return 0;
}

其输出为

0 -> null
1 -> 0 -> null
1 -> 0 -> 2 -> null
3 -> 1 -> 0 -> 2 -> null
3 -> 1 -> 0 -> 2 -> 4 -> null
5 -> 3 -> 1 -> 0 -> 2 -> 4 -> null
5 -> 3 -> 1 -> 0 -> 2 -> 4 -> 6 -> null
7 -> 5 -> 3 -> 1 -> 0 -> 2 -> 4 -> 6 -> null
7 -> 5 -> 3 -> 1 -> 0 -> 2 -> 4 -> 6 -> 8 -> null
9 -> 7 -> 5 -> 3 -> 1 -> 0 -> 2 -> 4 -> 6 -> 8 -> null

在该演示程序中，使用函数push_back将偶数插入列表的末尾，使用函数push_front将奇数插入列表的开头。

如果你的C编译器不支持指定的初始化程序，那么这个声明

List list = { .head = NULL, .tail = NULL };

可以通过以下方式更改

List list = { NULL, NULL };

Answer 2

问题是，在这两种情况下，代码都将节点追加到列表的前面。如果要始终追加到列表的末尾，则需要遍历列表直到末尾，然后在那里添加temp。

我即兴写了这个代码，所以把它当作伪代码：

// Assuming this function returns the front (head) of the list.
list* append_element_to_list(list* a, int b)
{
list *newNode;
newNode = (list*)malloc(sizeof(list*));
newNode->data = b;
// Handle the case where `a` is NULL. This means
// no list was passed in, so the newly created node
// will be returned to start the list.
if (a == NULL)
{
return newNode;
}
// If we get this far, it means `a` contains at least
// one node. So walk the list until the end.
list *currentNode = a;
while (currentNode->next != NULL)
{
currentNode = currentNode->next;
}
// Once you reach the end of the list, set
// `newNode` as the last node.
currentNode->next = newNode;
// The front of the list hasn't changed, so return that.
return a;
}

Answer 3

您的代码中有一些错误，我正在对您的代码进行更正，只是更改所需内容。首先，我想关注主要问题，在插入任何列表的最后一个之前，您应该迭代完整的列表。

i = a; // to iterate
while(i->next != NULL)
{
i = i->next;
}
// Now i is last node of list a
i->next = temp;

现在是下面的代码，我只是在TurboC上检查它，我正在使用你的函数，插入三个值，然后打印列表。请查看所有行评论：

#include <stdio.h>
#include <malloc.h>
typedef struct node{
int data;
struct node *next;
}list;
list* add_int_list(list* a,int b)
{
list *temp;
list *i;
temp = (list*)malloc(sizeof(list*));
temp->next = NULL;
temp->data = b;
if (a == NULL)//insert to the first node
{
//temp->data = b; -  done above
//temp->next = a; no reason for this line
a = temp;
}
else
{
// temp->data = b; - done above
//temp->next = a; wrong logic
// a = temp;//I think the problem is here, couldnt find how to fix : Yes it is also wrong
//Here it required to iterate complete list and go to end
i = a; // to iterate
while(i->next != NULL)
{
i = i->next;
}
// Now i is last node of list a
i->next = temp;
}
return a;
}
void printList(list *root)
{
list *i;
if(root == NULL)
{
printf("List is empty");
}
else
{
i = root;
while(i != NULL){
printf("%d,",i->data);
i = i->next;
}
}
}
int main()
{
list *root = NULL;
clrscr();
root =  add_int_list(root, 3);
root =  add_int_list(root, 4);
root =  add_int_list(root, 5);
printList(root);
return 0;
}