递归反向链接列表

Question

我找不出为什么我的代码中断。除了当我尝试颠倒链表时，每件事都有效。它“停止工作”。 （这个函数; 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; 
} 

该功能将通过列表递归地运行。

好吧，让我们看看你的代码：

1. 2局部变量（并没有什么）
2. 代码退出，如果输入为空（多为安全）
3. 你设置你的局部变量的当前和下一个节点。
4. 如果这是列表中的最后一个节点，则退出代码。
5. 递归地调用你的函数。

请注意，在这个阶段实际上没有发生任何事情。 这意味着您的处理（函数结束处的行）将以与列表相反的顺序发生。从后面到前面。 这对你想要做的事似乎是正确的。

下一行：

first->next->next = first; 

这似乎是正确的，因为它会设置旁边的“下面的”节点指向这一个。如同改变列表中下一个指针的方向一样。

现在你有这样一行：

first->next = NULL; 

请记住，我们说你的节点的“处理”，将按照相反的顺序发生。如此有效的一个接一个，你将所有你的下一个指针设置为NULL。我认为这将完全断开你的队列？

我理解的最后一行仅仅是为了让您能够为您的队列找到新的头指针并且看起来很好。

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

伪代码为 “反转” 的文章：

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; 
}