c - 在c中递归地从链表中删除元素时的无限链接循环

Question

我正在为做练习题的测试而学习，似乎无法让我的链表与递归地从链表中删除元素的函数一起正常工作。下面是我的完整代码，如果您看到我可以改进其他方法的任何方法，请告诉我。谢谢! :)

    /*
Q1: 
Try implementing the functions shown in class on your own: 
    check:  node creation 
    check:  insertion at the end of a linked list,
    check:  insertion at the head of a linked list, 
    check:  a list printing function.
Q2: 
    check: Write a recursive printList() function.
Q3:
    check: Write a recursive tailInsert() function.
Q4:
    check: Write a function that inserts nodes at the beginning of the linked list.
Q5:
    check: Write a recursive function that prints a linked list in reverse order. 
           The function signature is: void printReverse(node *head);
Q6:
    - Write an iterative destroyList() function that frees all the nodes in a linked list.
Q7:
    - Now implement destroyList() recursively.
Q8:
    - Write a function that deletes the nth element from a linked list. 
      If the linked list doesn't even have n nodes, don't delete any of them. 
      The function signature is: node *deleteNth(node *head, int n). 
     - Try implementing the function iteratively and recursively. 
     - (In terms of how to interpret n, you can start counting your nodes from zero or one; your choice.)
Q9:
    - Write a function that deletes every other element in a linked list. 
    - (Try writing it both ways: one where it starts deleting at the head of the list, 
    - and one where it starts deleting at the element just after the head of the list.)
    - Can you write this both iteratively and recursively?
Q10:
    - Write a function that deletes all even integers from a linked list.
Q11:
    - Write a function that takes a sorted linked list and an element to be inserted into that linked list,
      and inserts the element in sorted order. 
      The function signature is: node *insertSorted(node *head, int n);
Q12:
    - One of the problems with the first insertNode() function from today is that it 
      requires us to call it using head = insertNode(head, i). 
      That's a bit dangerous, because we could forget the "head =" part very easily. 
      Re-write the function so that it takes a pointer to head, 
      thereby allowing it to directly modify the contents of head without any need for a return value. 
      The function signature is: void insertNode(node **head, int data). 
      The function will be called using insertNode(&head, i).
*/

//come back to
#include <stdio.h>
#include <stdlib.h>


// Basic linked list node struct; contains 'data' and 'next' pointer.
// What happens if we type "node *next" instead of "struct node *next"?
typedef struct node
{
    // data field
    int data;

    // the next node in the list
    struct node *next;
} node;

// Allocate a new node. Initialize its fields. Return the pointer.
// We call this from our insertion functions.
node *createNode(int data)
{
    node *ptr = NULL;
    ptr = malloc(sizeof(node));
    if(ptr == NULL)
    {
        printf("space could not be allocated\n");
        return NULL;
    }
    ptr->data = data;
    ptr->next = NULL;
    return ptr;
}

// Insert into the end of the linked list. Return the head of the linked list.
// (What is the order (Big-Oh) of this function?)
node *insertNode(node *head, int data)
{    
    node *temp;
    if (head == NULL)
        return createNode(data);

    for(temp = head; temp->next != NULL; temp = temp->next)
        ;
    temp->next = createNode(data);

    return head;
}

node *insertNodeFront(node *head, int data)
{
    node *temp;
    if(head == NULL)
        return createNode(data);

    temp = createNode(data);
    temp->next = head;

    return temp;
}   

// Simple function to print the contents of a linked list.
void printList(node *head)
{
    if (head == NULL)
    {
        printf("Empty List\n");
        return;
    }

    for(; head != NULL; head = head->next)
        printf("%d ", head->data);

    printf("\n");
}

void printListRecursiveHelper(node *head)
{
    if (head == NULL)
        return;

    printf("%d%c", head->data, (head->next == NULL) ? '\n' : ' ');
    printListRecursiveHelper(head->next);
}

void printListRecursive(node *head)
{
    if (head == NULL)
    {
        printf("empty list\n");
        return;
    }
    printListRecursiveHelper(head);
}
// Q3: - Write a recursive tailInsert() function.

node *tailInsert(node *head, int data)
{
    if(head->next == NULL)
    {
        node *temp;
        temp = createNode(data);
        temp->next = NULL;
        head->next = temp;
        return temp;
    }
    return tailInsert(head->next, data);
}   
//Q5: Write a recursive function that prints a linked list in reverse order. 
void printReverse(node *head)
{
    if (head == NULL)
        return;

    printReverse(head->next);

    printf("%d ", head->data);
}

// Q6: - Write an iterative destroyList() function that frees all the nodes in a linked list.
// Got code from internet, memorize it
/* Function to delete the entire linked list */
void destroyList (struct node** head)
{
   struct node* current = *head;
   struct node* next;

   while (current != NULL) 
   {
       next = current->next;
       free(current);
       current = next;
   }


   *head = NULL;
}

//Q7:  - Now implement destroyList() recursively.
// Look up online, need to examine why it deson't work
node *destroyListRecursive(node *head)
{
    if ( head == NULL)
        return NULL;

    destroyListRecursive(head->next);

    free(head);
}

int main(void)
{
    int i, r;

    // The head of our linked list. If we don't initialize it to NULL, our
    // insertNode() function might segfault.
    node *head = NULL;

    srand(time(NULL));

    // Populate the linked list with random integers. We are inserting into the
    // head of the list each time.
    for (i = 0; i < 10; i++)
    {
        printf("Inserting %d...\n", r = rand() % 20 + 1);
        head = insertNode(head, r);
    }
    head = insertNodeFront(head, 1);

    tailInsert(head, 5);

    // Print the linked list.
    printList(head);
    printf("\n");
    printReverse(head);
    printf("\n\n");

    // Print the linked list using our recursive function.
    printListRecursive(head);

    //destroyList(&head);
    head = destroyListRecursive(head);

    printList(head);

    system("PAUSE");
    return 0;
}

Answer 1

这是基于我的 [和其他人] 的热门评论，但这是有效的 [很抱歉发布整个程序，只是 main 中的一行更改和函数的重写]:

/*
Q1:
Try implementing the functions shown in class on your own:
    check:  node creation
    check:  insertion at the end of a linked list,
    check:  insertion at the head of a linked list,
    check:  a list printing function.
Q2:
    check: Write a recursive printList() function.
Q3:
    check: Write a recursive tailInsert() function.
Q4:
    check: Write a function that inserts nodes at the beginning of the linked list.
Q5:
    check: Write a recursive function that prints a linked list in reverse order.
           The function signature is: void printReverse(node *head);
Q6:
    - Write an iterative destroyList() function that frees all the nodes in a linked list.
Q7:
    - Now implement destroyList() recursively.
Q8:
    - Write a function that deletes the nth element from a linked list.
      If the linked list doesn't even have n nodes, don't delete any of them.
      The function signature is: node *deleteNth(node *head, int n).
     - Try implementing the function iteratively and recursively.
     - (In terms of how to interpret n, you can start counting your nodes from zero or one; your choice.)
Q9:
    - Write a function that deletes every other element in a linked list.
    - (Try writing it both ways: one where it starts deleting at the head of the list,
    - and one where it starts deleting at the element just after the head of the list.)
    - Can you write this both iteratively and recursively?
Q10:
    - Write a function that deletes all even integers from a linked list.
Q11:
    - Write a function that takes a sorted linked list and an element to be inserted into that linked list,
      and inserts the element in sorted order.
      The function signature is: node *insertSorted(node *head, int n);
Q12:
    - One of the problems with the first insertNode() function from today is that it
      requires us to call it using head = insertNode(head, i).
      That's a bit dangerous, because we could forget the "head =" part very easily.
      Re-write the function so that it takes a pointer to head,
      thereby allowing it to directly modify the contents of head without any need for a return value.
      The function signature is: void insertNode(node **head, int data).
      The function will be called using insertNode(&head, i).
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

    // Basic linked list node struct; contains 'data' and 'next' pointer.
    // What happens if we type "node *next" instead of "struct node *next"?
typedef struct node {
    // data field
    int data;

    // the next node in the list
    struct node *next;
} node;

    // Allocate a new node. Initialize its fields. Return the pointer.
    // We call this from our insertion functions.
node *
createNode(int data)
{
    node *ptr = NULL;

    ptr = malloc(sizeof(node));
    if (ptr == NULL) {
        printf("space could not be allocated\n");
        return NULL;
    }
    ptr->data = data;
    ptr->next = NULL;
    return ptr;
}

    // Insert into the end of the linked list. Return the head of the linked list.
    // (What is the order (Big-Oh) of this function?)
node *
insertNode(node * head, int data)
{
    node *temp;

    if (head == NULL)
        return createNode(data);

    for (temp = head; temp->next != NULL; temp = temp->next);
    temp->next = createNode(data);

    return head;
}

node *
insertNodeFront(node * head, int data)
{
    node *temp;

    if (head == NULL)
        return createNode(data);

    temp = createNode(data);
    temp->next = head;

    return temp;
}

    // Simple function to print the contents of a linked list.
void
printList(node * head)
{
    if (head == NULL) {
        printf("Empty List\n");
        return;
    }

    for (; head != NULL; head = head->next)
        printf("%d ", head->data);

    printf("\n");
}

void
printListRecursiveHelper(node * head)
{
    if (head == NULL)
        return;

    printf("%d%c", head->data, (head->next == NULL) ? '\n' : ' ');
    printListRecursiveHelper(head->next);
}

void
printListRecursive(node * head)
{
    if (head == NULL) {
        printf("empty list\n");
        return;
    }
    printListRecursiveHelper(head);
}

    // Q3: - Write a recursive tailInsert() function.

node *
tailInsert(node * head, int data)
{
    if (head->next == NULL) {
        node *temp;

        temp = createNode(data);
        temp->next = NULL;
        head->next = temp;
        return temp;
    }
    return tailInsert(head->next, data);
}

    // Q5: Write a recursive function that prints a linked list in reverse order.
void
printReverse(node * head)
{
    if (head == NULL)
        return;

    printReverse(head->next);

    printf("%d ", head->data);
}

    // Q6: - Write an iterative destroyList() function that frees all the nodes in a linked list.
    // Got code from internet, memorize it
    /* Function to delete the entire linked list */
void
destroyList(struct node **head)
{
    struct node *current = *head;
    struct node *next;

    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }

    *head = NULL;
}

    // Q7: - Now implement destroyList() recursively.
    // Look up online, need to examine why it deson't work
node *
destroyListRecursive(node * head)
{

    if (head != NULL) {
        destroyListRecursive(head->next);
        free(head);
    }

    return NULL;
}

int
main(void)
{
    int i,
     r;

    // The head of our linked list. If we don't initialize it to NULL, our
    // insertNode() function might segfault.
    node *head = NULL;

    srand(time(NULL));

    // Populate the linked list with random integers. We are inserting into the
    // head of the list each time.
    for (i = 0; i < 10; i++) {
        printf("Inserting %d...\n", r = rand() % 20 + 1);
        head = insertNode(head, r);
    }
    head = insertNodeFront(head, 1);

    tailInsert(head, 5);

    // Print the linked list.
    printList(head);
    printf("\n");
    printReverse(head);
    printf("\n\n");

    // Print the linked list using our recursive function.
    printListRecursive(head);

    // destroyList(&head);
    head = destroyListRecursive(head);

    printList(head);

    system("PAUSE");
    return 0;
}