C中的链表不能在开头添加节点

Question

我在向链表的开头添加元素时遇到问题。

#include <conio.h>
#include "list.h"
int main () {
nodePtr L;
L = createList();
L = makeNode(20);
display(L);
addFront(L,25);
display(L);
return 0;
}     

这是我的库，它只是打印NODE INSERTED，而不是真正插入在前面。

#include <stdlib.h>
#include <stdio.h>
#ifndef list_h
#define list_h

typedef int itemType;
typedef struct node *nodePtr;
struct node{
itemType item;
nodePtr next;
};
nodePtr createList();                                   //init list
nodePtr makeNode(itemType x);                           //allocate node 
void display(nodePtr L);                                //print output
void addFront(nodePtr L, itemType x);                   //add as first element
nodePtr createList() {      
nodePtr L;
L= (nodePtr) malloc(sizeof(struct node));
L->next= NULL;
return L;
}
nodePtr makeNode(itemType x) {
nodePtr temp = (nodePtr) malloc(sizeof(struct node));
temp->item=x;
temp->next=NULL;
return temp;
}
void display(nodePtr L) {
nodePtr temp;
temp = L;
while (temp!=NULL) {
printf("%d", temp->item);
temp = temp->next;
}
}
void addFront(nodePtr L, itemType x) {
nodePtr newNode = (nodePtr) malloc(sizeof(struct node));
if(newNode == NULL) {
printf("Unable to allocate memory.");
}
else {
newNode->item = x;
newNode->next = L;
L=newNode;
printf("NODE INSERTED");
}   
}
#endif

我真的不明白出了什么问题，我正试图遵循老师初始化typedef nodePtr和itemType的格式，但我实际上可以理解在前面添加元素的概念，而不必遵循老师的格式，我只需要了解她的格式是如何作为替代方案的。

Answer 1

此函数

nodePtr createList() {      
nodePtr L;
L= (nodePtr) malloc(sizeof(struct node));
L->next= NULL;
return L;
}

没有道理。它使数据成员item未初始化。

这两个调用

L = createList();
L = makeNode(20);

产生内存泄漏。

函数addFront通过值接受指向节点的指针。也就是说，该函数处理用作参数的原始指针的副本。因此，在函数中更改指针的副本

L=newNode;

不会影响原始指针的值。您需要通过指向指针的指针来通过引用传递指针。

void addFront(nodePtr *L, itemType x) {
nodePtr newNode = (nodePtr) malloc(sizeof(struct node));
if(newNode == NULL) {
printf("Unable to allocate memory.");
}
else {
newNode->item = x;
newNode->next = *L;
*L=newNode;
printf("NODE INSERTED");
}   
}

这个函数被称为

addFront( &L,25 );

请注意，函数不应输出任何消息。函数的调用方将根据函数返回的值决定是否输出消息。

因此，最好用以下的方式来定义它

int addFront( nodePtr *L, itemType x ) 
{
nodePtr newNode = malloc( sizeof( struct node ) );
int success = newNode != NULL;
if ( success )
{
newNode->item = x;
newNode->next = *L;
*L = newNode;
}
return success;   
}

定义函数的另一种方法是当函数返回指向头节点的指针的新值时，例如

nodePtr addFront( nodePtr L, itemType x ) 
{
nodePtr newNode = malloc( sizeof( struct node ) );
if ( newNode != NULL )
{
newNode->item = x;
newNode->next = L;
}
return newNode;   
}

但这种做法并不灵活。在将返回的指针分配给调用者中指向头节点的指针之前，您需要检查返回的指针是否不等于NULL，例如

nodePtr tmp = addFront( L,25 );
if ( tmp != NULL ) L = tmp;

Answer 2

我相信addFront的代码没有"错误"，但是您缺少返回值。按照现在编写代码的方式，您正在创建一个新的锚点元素，但没有返回它，这意味着您的锚点变量仍然指向现在的第二个元素。

任一：

• 返回(并分配(指向锚点的新指针
• 将指针传递到锚点变量并对其进行操作
• 创建一个新节点，将值(和下一个(复制到该新节点，并用新值覆盖当前节点的值/下一个。(锚位置保持不变(

这是一个带有返回值的函数。

nodePtr addFront(nodePtr L, itemType x) {
nodePtr newNode = (nodePtr) malloc(sizeof(struct node));
if(newNode == NULL) {
printf("Unable to allocate memory.");
}
else {
newNode->item = x;
newNode->next = L;
printf("NODE INSERTED");
}
return newNode;
}

自然地(谨慎地(称为：

anchor = addFront(anchor, 5);

如果内存分配失败，这将使整个链表无法访问，因为锚点现在指向NULL，因此可能需要一个临时变量。

或者：

void addFront(nodePtr *L, itemType x) {
nodePtr newNode = (nodePtr) malloc(sizeof(struct node));
if(newNode == NULL) {
printf("Unable to allocate memory.");
}
else {
newNode->item = x;
newNode->next = *L;
*L = newNode;
printf("NODE INSERTED");
}
}

只有在成功分配内存的情况下，此版本才会覆盖锚点。但是，如果传递的L为NULL，那么它显然会失败。