CODEWITHSUNDEEP
crecursion
Dmcdodge1
Dmcdodge1

Reputation: 3

Recursive Reverse Link Lists

I can't figure out why my code breaks. Every thing works, except when I try to reverse the linked list. It "stops working." (This function; void reverseList(struct produceItem** inHead)) Any ideas? I've been stuck on this for some time now. I think the issue might be that it doesn't read a NULL some where, but I cannot figure it out.

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

Upvotes: 0

Views: 150

Answers (1)

Heinrich du Toit
Heinrich du Toit

Reputation: 458

in this recursive function:

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

This function will run recursively through the list.

Ok lets look at your code:

  1. 2 local variables (does nothing really)
  2. code to exit if input is null (mostly for safety)
  3. You set your local variables to the current and next node.
  4. code to exit if this is the last node in the list.
  5. You call your function recursively.

Note that at this stage actually nothing has happened. This means that your processing (the lines at the end of your function) will happen in reverse order of the list. From back to front. This seems correct for what you want to do.

Next line:

first->next->next = first;

This seems correct as it would set the next of the "following" node to point to this one. As in change the direction of the next pointer within the list.

Now you have this line:

first->next = NULL;

Remember that we said your "processing" of the nodes will happen in the reverse order. So effectively one by one you will set all your next pointers to NULL. Which I think will completely disconnect your queue completely?

The last line I understand is simply to enable you to find the new head pointer for your queue and that seems fine.

btw doing this kind of algorithm with recursion is a bad idea normally. As you can easily cause stack overflow problems if your list is getting long. Also if for some reason your list has a problem and it is circular then it is difficult to detect that and not cause problems. Also generally in terms of performance this type of recursive algorithm will be slower than just a proper loop implementation.

Pseudo code to "reverse" list:

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

Upvotes: 1

Related Questions