递归反向 Link 列表

Question

我不明白为什么我的代码会出错。一切正常，除非我试图反转链表。它 "stops working."（这个函数；void reverseList(struct produceItem** inHead)）有什么想法吗？我已经坚持了一段时间了。我认为问题可能是它在某些地方没有读到 NULL，但我无法弄清楚。

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

struct produceItem{
    char produce[20];
    char type[20];
    char soldBy[20];
    float price;
    int quantityInStock;
    struct produceItem *next;
};

struct produceItem* append(struct produceItem *inHead, char *nextProduce, char *nextType, char *nextSoldBy, char *nextPrice, char *nextQuantityInStock){

    struct produceItem *temp;
    temp =(struct produceItem *)malloc(sizeof(struct produceItem));
    strcpy(temp->produce, nextProduce);
    strcpy(temp->type, nextType);
    strcpy(temp->soldBy, nextSoldBy);
    temp->price = atof(nextPrice);
    temp->quantityInStock = atoi(nextQuantityInStock);

    if(inHead == NULL){
        inHead = temp;
        temp->next = NULL;
    }

    else{
        temp->next = inHead;
        inHead = temp;
        }
    return inHead;
}

struct produceItem* readData(struct produceItem *inHead){
    const char comma[2] = ",";
    char *produceTemp;
    char *typeTemp;
    char *soldByTemp;
    char *priceTemp;
    char *quantityInStockTemp;

    char dataLine[100];
    char fileName[] = "AssignmentTwoInput.txt";
    FILE *inputFile;

    printf("\nFile %s has been read.\n\n", fileName);
    inputFile = fopen(fileName, "r");

    if( inputFile == NULL){
        printf("%sList Does not exist\n", fileName);
        return;
        }

    while((fgets(dataLine, 100, inputFile)) != NULL){
        produceTemp = strtok(dataLine, comma);
        typeTemp = strtok(NULL, comma);
        soldByTemp = strtok(NULL, comma);
        priceTemp = strtok(NULL, comma);
        quantityInStockTemp = strtok(NULL, comma);
        inHead = append(inHead, produceTemp,typeTemp,soldByTemp,priceTemp,quantityInStockTemp);
    }
    fclose(inputFile);
    return inHead;
}



void display(struct produceItem *inHead){

    int i = 1;
    if(inHead == NULL){
        printf("List does not exist.\n");
        return;
    }
    printf("=========================================================================\n");
    printf("Item #    Produce        Type          Sold By          Price     In Stock\n");
    printf("==========================================================================\n");

    for(i=1; i<27; i++){
    //while(inHead != NULL){
        printf("\n%5d", i);
        printf("     %-12s ", inHead->produce);
        printf("%-16s ", inHead->type);
        printf("%-16s ", inHead->soldBy);
        printf("%3.2f ", inHead->price);
        printf("%8d", inHead->quantityInStock);
        inHead = inHead->next;
        //i++;
    }
    printf("\n\n");
}

exportData(struct produceItem *n){
    char fileName[] = "AssignmentTwoOutput.txt";
    FILE *exportFile;
    int i =1;

        if(n == NULL){
            printf("List does not exist.\n");
            return;
        }

    exportFile = fopen(fileName, "w");
    //printf("hi");
    fprintf(exportFile,"================================================================\n");
    //printf("hi");
    fprintf(exportFile,"Item# Produce        Type           Sold By    Price    In Stock\n");
    fprintf(exportFile,"================================================================\n");

        for(i=1; i<27; i++){
        //while(n->next != NULL){
            //printf("hi");
            fprintf(exportFile,"\n%3d", i);
            fprintf(exportFile,"   %-12s ", n->produce);
            fprintf(exportFile,"%-15s ", n->type);
            fprintf(exportFile,"%-15s ", n->soldBy);
            fprintf(exportFile,"%3.2f ", n->price);
            fprintf(exportFile,"%8d", n->quantityInStock);
            n = n->next;
        }
    printf("\nYour data has been written to AssignmentTwoOutput.txt, thank you.\n\n");
    fclose(exportFile);
}

//void recursiveReverse(struct node** head_ref)
//{
    //struct node* first;
   // struct node* rest;

    /* empty list */
   // if (*head_ref == NULL)
       //return;

    /* suppose first = {1, 2, 3}, rest = {2, 3} */
    //first = *head_ref;
    //rest  = first->next;

    /* List has only one node */
    //if (rest == NULL)
       //return;

    /* reverse the rest list and put the first element at the end */
    //recursiveReverse(&rest);
    //first->next->next  = first;

    /* tricky step -- see the diagram */
    //first->next  = NULL;

    /* fix the head pointer */
    //*head_ref = rest;
//}

void reverseList(struct produceItem** inHead){

    //printf("1");
    struct produceItem* first;
    struct produceItem* follow;
    //printf("2");

    if (*inHead==NULL){
       // printf("3");
        printf("List does not exist.\n");
        return;}

    first = *inHead;
    //printf("4");
    follow = first->next;

    if(follow==NULL)
        //printf("5");
        return;

    reverseList(&follow);
    first->next->next = first;
    first->next = NULL;
    *inHead = follow;
}

int main (void){
    int choice;
    struct produceItem *head;

    while(1){
        printf("List of Operations\n");
        printf("===============\n");
        printf("1. Stock Produce Department\n");
        printf("2. Display Produce Inventory\n");
        printf("3. Reverse Order of Produce Inventory\n");
        printf("4. Export Produce Inventory\n");
        printf("5. Exit\n");

    printf("Enter you choice: ");
    scanf("%d", &choice);

    if(choice <= 0 || choice > 5){
        printf("Enter a valid response please: \n");
        exit(0);
    }

    switch(choice){
                case 1:
                    //reading from  thefile
                    head = readData(head);
                    break;
                case 2:
                    //displays the list
                    display(head);
                    break;

                case 3:
                    //reverse the list
                    reverseList(&head);
                    break;

                case 4:
                    exportData(head);
                    break;

                case 5:
                    //Exits the operation
                    printf("Exiting, Thank you.");
                    exit(0);
                    break;
            }
    }
}

Answer 1

在这个递归函数中：

void reverseList(struct produceItem** inHead){

    //printf("1");
    struct produceItem* first;
    struct produceItem* follow;
    //printf("2");

    if (*inHead==NULL){
       // printf("3");
        printf("List does not exist.\n");
        return;}

    first = *inHead;
    //printf("4");
    follow = first->next;

    if(follow==NULL)
        //printf("5");
        return;

    reverseList(&follow);
    first->next->next = first;
    first->next = NULL;
    *inHead = follow;
}

此函数将运行递归遍历列表。

好的，让我们看看您的代码：

2 个局部变量（实际上什么都不做）
输入为空时退出的代码（主要是为了安全）
您将局部变量设置为当前节点和下一个节点。
如果这是列表中的最后一个节点，则退出的代码。
你递归地调用你的函数。

请注意，在这个阶段实际上什么都没有发生。这意味着您的处理（函数末尾的行）将按照列表的相反顺序进行。从后到前。这似乎对你想做的是正确的。

下一行：

first->next->next = first;

这似乎是正确的，因为它会将 "following" 节点的下一个设置为指向这个节点。就像改变列表中下一个指针的方向一样。

现在你有这一行：

first->next = NULL;

请记住，我们说过您的 "processing" 节点将以相反的顺序发生。如此有效地一个接一个，您会将所有 next 指针设置为 NULL。我认为哪个会完全断开您的队列？

我理解的最后一行只是让您能够为您的队列找到新的头指针，这看起来不错。

顺便说一句，用递归做这种算法通常不是一个好主意。如果列表变长，很容易导致堆栈溢出问题。此外，如果由于某种原因您的列表有问题并且它是循环的，那么很难检测到并且不会引起问题。通常在性能方面，这种类型的递归算法将比适当的循环实现慢。

"reverse" 列表的伪代码：

reverseList(** head)
{
 current = head
 prev = null
 next = null
 int i = 0;
 while (current)
 {
   next = current->next;

   current->next = prev;  

   prev = current;
   current = next;


   i++;
   if (i > MAX) reportError();
 }
 head = prev;
}

递归反向 Link 列表

Recursive Reverse Link Lists

c

recursion