单链表 C 中返回根节点的链表

Question

我正在编写一个程序来删除大于 x 的节点。我想删除后return链表的根节点。我将新的根节点保存在变量“root”中。但不幸的是，当我在 main 函数中获取 root 时，该值似乎为 0。谁能帮我找出问题所在？**

// structure of a node
struct Node {
    int data;
    Node* next;
};

// function to get a new node
Node* getNode(int data)
{
  
    Node* newNode = (Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// function to delete all the nodes from the list
// that are greater than the specified value x
Node *deleteGreaterNodes(Node* head_ref, int x)
{
    Node *temp = head_ref, *prev;
    static Node *root;

    // If head node itself holds the value greater than 'x'
    if (temp != NULL && temp->data > x) {
        head_ref = temp->next; // Changed head
        free(temp); // free old head
        temp = head_ref; // Change temp
    }
    root = temp;
    // Delete occurrences other than head
    while (temp != NULL) {

        // Search for the node to be deleted,
        // keep track of the previous node as we
        // need to change 'prev->next'
        while (temp != NULL && temp->data <= x) {
            prev = temp;
            temp = temp->next;
        }

        // If required value node was not present
        // in linked list
        if (temp == NULL)
            return 0;

        // Unlink the node from linked list
        prev->next = temp->next;

        free (temp); // Free memory

        // Update Temp for next iteration of
        // outer loop
        temp = prev->next;
    }
    return head_ref;
}

// function to a print a linked list
void printList(Node* head)
{
    while (head) {
       
        printf("%d ",head->data);
        head = head->next;
    }
}

// Driver program to test above
int main()
{
    static Node *root;
    // Create list: 7->3->4->8->5->1
    Node* head = getNode(7);
    head->next = getNode(3);
    head->next->next = getNode(4);
    head->next->next->next = getNode(8);
    head->next->next->next->next = getNode(5);
    head->next->next->next->next->next = getNode(1);

    int x = 3;

   
     printf("Original List: "); 
    printList(head);

   root = deleteGreaterNodes(head, x);
     
     printf("\nModified List: "); 
    printList(root);

    return 0;
}

Answer 1

首先，不要在一个翻译单元中混用两种语言 C 和 C++。

写一个 C 或 C++ 程序。

例如 C 中的这个声明

// structure of a node
struct Node {
    int data;
    Node* next;
};

不正确，你必须写

// structure of a node
struct Node {
    int data;
    struct Node* next;
};

声明静态变量意义不大root

static Node *root;

然后又一个变量head.

// Create list: 7->3->4->8->5->1
Node* head = getNode(7);

您的函数 deleteGreaterNodes 太复杂了，与任何复杂函数一样，它在此代码段中包含一个错误

    // If required value node was not present
    // in linked list
    if (temp == NULL)
        return 0;

因为它returns一个空指针而不是返回指针head_ref。

这是您根据C语言调整后的更新程序，其中包含修改后的函数deleteGreaterNodes。

#include <stdio.h>
#include <stdlib.h>

// structure of a node
struct Node {
    int data;
    struct Node* next;
};

// function to get a new node
struct Node* getNode(int data)
{
  
    struct Node* newNode = ( struct Node * )malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// function to delete all the nodes from the list
// that are greater than the specified value x

struct Node *deleteGreaterNodes( struct Node* head_ref, int x )
{
    while ( head_ref && x < head_ref->data )
    {
        struct Node *tmp = head_ref;
        head_ref = head_ref->next;
        free( tmp );
    }
    
    if ( head_ref )
    {
        for ( struct Node *current = head_ref; current->next != NULL; )
        {
            if ( x < current->next->data )
            {
                struct Node *tmp = current->next;
                current->next = current->next->next;
                free( tmp );
            }
            else
            {
                current = current->next;
            }
        }
    }
    
    return head_ref;
}

// function to a print a linked list
void printList(struct Node* head)
{
    while (head) {
       
        printf("%d ",head->data);
        head = head->next;
    }
}

// Driver program to test above
int main()
{
    struct Node* head = getNode(7);
    head->next = getNode(3);
    head->next->next = getNode(4);
    head->next->next->next = getNode(8);
    head->next->next->next->next = getNode(5);
    head->next->next->next->next->next = getNode(1);

    int x = 3;

    printf( "Original List: " );
    // printf("Original List: "); 
    printList(head);

   head = deleteGreaterNodes(head, x);

    
     printf("\nModified List: "); 
    printList( head );

    return 0;
}

程序输出为

Original List: 7 3 4 8 5 1 
Modified List: 3 1

Answer 2

实现 deleteGreaterNodes 的一种简单方法是使用额外的间接级别来访问 Node * 链接。

// function to delete all the nodes from the list
// that are greater than the specified value x
Node *deleteGreaterNodes(Node* head_ref, int x)
{
    Node **link = &head_ref; // Point to the pointer to the first node.
    Node *cur;

    while ((cur = *link) != NULL) {
        if (cur->data > x) {
            // The current node needs to be deleted from the list.
            // Change the link pointing to the current node to point to the next node.
            *link = cur->next;
            // Delete the current node.
            free(cur);
        } else {
            // The current node is to be kept on the list.
            // Get a pointer to the link to the next node.
            link = &cur->next;
        }
    }
    return head_ref;
}

单链表 C 中返回根节点的链表

Linked list returning root node in singly-linked list C

c

struct

linked-list

nodes

singly-linked-list