0

my first time here and a beginner, so bear with me.

I got an assignment dealing with a doubly linked list and we were given two print functions that prints the linked list forward and in reverse. We are not allowed to alter those functions in anyways.

I am unable to pass the linked list through while(1) passing to it. I made a test function where it iterates the list with while(pointer != NULL) and that works fine.

Any suggestions?

This is my main function.

FILE *fp;

struct node{
    int data;
    struct node* prev;
    struct node* next;
};
typedef struct node* listPointer;
listPointer headNode = NULL;
listPointer tailNode = NULL;


void delete(listPointer *head, listPointer removalNode);
//int traverseList(listPointer head, int data);
listPointer insertBefore(listPointer *head, listPointer nextNode, listPointer insertionNode);
listPointer findPosition(listPointer *head, int data);
listPointer findNode(listPointer *head, int data);
listPointer insertAtHead(listPointer *head, listPointer insertionNode);
listPointer insertAtBack(listPointer *head, listPointer insertionNode);
listPointer createNode(int data);
void print_forward(listPointer list);
void print_reverse(listPointer list);

void sortedInsert(listPointer *head,listPointer *tail,int data)
{

    listPointer p = malloc(sizeof(listPointer));
    listPointer temp = malloc(sizeof(listPointer));

    p->data = data;
    p->next = NULL;

    if ((*head) == NULL)
    {
        (*head) = p;
        (*tail) = p;
        (*head)->prev = NULL;
        return;
    }

    if ((p->data) < ((*head)->data))
    {
        p->prev = NULL;
        (*head)->prev = p;
        p->next = (*head);
        (*head) = p;
        return;
    }

    if ((p->data) > ((*tail)->data))
    {
        p->prev = (*tail);
        (*tail)->next = p;
        (*tail) = p;
        return;
    }

    temp = (*head)->next;
    while ((temp->data) < (p->data))
        temp = temp->next;


    (temp->prev)->next = p;
    p->prev = temp->prev;
    temp->prev = p;
    p->next = temp;
}

///test print function
void printlist(listPointer head) // this is a test function
{
  listPointer temp = head;
  while(temp != NULL) // works, but seg fault when is set to while(1) like line 282
  {
    printf("%d - ", temp->data);
    temp = temp->next;
  }
  printf("\n");
}

test print function reverse
void printlist2(listPointer head)
{
  listPointer temp = head;
  while( temp != NULL)
  {
    printf("%d - ", temp->data);
    temp = temp->prev;
  }
  printf("\n");
}


void main(int argc, char** argv)
{
    if(argc != 2)
    {
        fprintf(stderr, "usage: ./mp1 input_filename\n");
        exit(1);
    }

    FILE *fp = fopen(argv[1], "r");

    if(fp == NULL)
    {
        fprintf(stderr, "The input file does not exist.\n");
        exit(1);
    }
    char *op;

    listPointer temp;
    listPointer newnode;
    int data=0;
    int flag=0;
    char c;
    int num;
    ///////////////////////////////////////////////////////// TESTING

    data = 10;
    op = "INSERT";
    sortedInsert(&headNode,&tailNode,data);
    sortedInsert(&headNode,&tailNode,6);
    sortedInsert(&headNode,&tailNode,7);
    printlist(headNode);
    printf("\nhead %d\n",headNode->data);
    printf("tail %d\n",tailNode->data);
    printlist2(tailNode);

    print_forward(headNode); // seg fault
    ///////////////////////////////////////////////////////// TESTING


    /*while(!feof(fp)){
        fscanf(fp,"%s",op);
        fscanf(fp,"%d",&data);
        //printf("%s ",op);
        //printf("%d ",data);
        if(strcmp(op,"INSERT")==0){flag=1;}
        else if(strcmp(op,"DELETE")==0){flag=2;}
        else if(strcmp(op,"ASCEND")==0) {flag=3;}
        else if(strcmp(op,"DESCEND")==0) {flag=4;}
        switch(flag)
        {
            case 1:
                newnode = createNode(data);
                if(headNode == NULL) insertAtHead(&headNode,newnode);
                else{
                    temp = findPosition(&headNode,data);
                    insertBefore(&headNode,temp,newnode);
                }
                break;
            case 2:
                temp = findNode(&headNode,data);
                delete(&headNode,temp);
                break;
            case 3:
                print_forward(headNode);
                break;
            case 4:
                print_reverse(headNode);
                break;
            default: break;
        }
    }*/
    fclose(fp);
}

And this are the given print functions.

void print_forward(listPointer list) {
    listPointer curr;
    FILE *outfile;
    outfile = fopen("mp1_result.txt", "a");
    if(list) {
        curr = list;
        while(1) {
            fprintf(outfile, "%d ", curr->data);
            printf("%d ", curr->data);
            curr = curr->next;
            if(curr == list) break;
        }
    }
    fprintf(outfile, "\n");
    printf("\n");
    fclose(outfile);
}

void print_reverse(listPointer list) {
    listPointer curr;
    FILE *outfile;
    outfile = fopen("mp1_result.txt", "a");
    if(list) {
        curr = list->prev;
        while(curr != list) {
            fprintf(outfile, "%d ", curr->data);
            printf("%d ", curr->data);
            curr = curr->prev;
        }
        fprintf(outfile, "%d ", curr->data);
        printf("%d ", curr->data);
    }
    fprintf(outfile, "\n");
    printf("\n");
    fclose(outfile);

Any suggestions welcomed and appreciated!

8
  • First thing to do: check if fopen fails. There is no excuse for not doing so. Commented May 19, 2020 at 6:03
  • I thought I did so with if(fp == NULL) { fprintf(stderr, "The input file does not exist.\n"); exit(1); } Is this wrong? Thanks for the input! Commented May 19, 2020 at 6:22
  • No, this is correct, but there are more fopens in your code. Commented May 19, 2020 at 6:23
  • Where is the segmentation fault occurring? What is the actual error message you get when you run your program? Commented May 19, 2020 at 6:24
  • This is what I get cse20172184@cspro:~/datastructures/mp1$ ./mp1 input.txt 6 - 7 - 10 - head 6 tail 10 10 - 7 - 6 - Segmentation fault (core dumped) Commented May 19, 2020 at 6:26

2 Answers 2

1

The given function works assuming a circular doubly linked list , look at the checks if(curr==list) - it's checking for the first entry, not NULL. As your linked list is not circular, it fails when pointing to NULL.

Sign up to request clarification or add additional context in comments.

1 Comment

Yeah, that makes total sense when u mention it. I'll make sure to spot these things in the future. Thanks!
1

The main thing that is causing you to get a segfault here is that the print_forward function expects a circular linked list, where the head and tail are also linked together. Otherwise that while(1) loop will segfault when it hits the end of the list (as you're seeing).

It is generally a good idea to build up an application piece-by-piece, checking each bit as you go, rather than the whole thing at once then trying to figure out what's wrong with the whole thing afterwards, especially when you're new. That said, I can see a number of things wrong with your code:

  • listPointer p = malloc(sizeof(listPointer)); - this only does what it says: allocates space for a pointer to a list (element), it doesn't make space for an actual list element.
  • When you check if the new item is greater than the tail, you should use >=. Otherwise, if the new element is equal to the tail, it will fail this check, then run through the loop searching for a location, and eventually segfault when it falls off the end of the list.
  • You don't actually need to test if the new item is less than the head - just check if it is greater (or equal) to the tail, and if not then iterate through all items in the list to find which is greater than the new item (starting with the head).

2 Comments

With your advice I was able to finally make it work. Been struggling with this one for a few days. Will definitely rethink how I write a program next time. I found it easier to imagine the data structure in my head by drawing it out on pen and paper. Thanks once again!
Writing it down with pen and paper is an excellent approach that doesn't just apply to beginners - I still like to do that for a lot of my work. Glad you got it going

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.