Linked Lists

DCOM · #1 26-Mar-2005, 02:42

It seems every program that I write always ends up with segmentation faults, no matter how hard I try to prevent them. Since looking at your own code at 2:00AM is nothing like having someone else look at your code, I decided to post it up here. The description for the assignment is here http://www.cs.ucf.edu/courses/cop3502/spr2005/section2/assign3.doc

Sample input files are here http://www.cs.ucf.edu/courses/cop3502/spr2005/section2/assign.html

If anything isn't apparent in the code, don't hesitate to ask.

CPP / C++ / C Code:

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

struct linked_list{
        char last[31];
        char first[31];
        int date;
        int seat;
        struct linked_list *next;
};

typedef struct linked_list booking;

booking *head = NULL;

int allotseat(char last[], char first[], int day, int seats[][9]);

void insertnode(char last[], char first[], int day, int seatinfo);

int cancel(char last[], char first[], int day, int seats[][9]);

int confirm(char last[], char first[], int day);

void display(int day);

void seatdisplay(int day, int seats[][9]);

int main(){

        head = malloc(sizeof(booking));

        FILE *input;
        char filename[31], eat[6], firstname[31], lastname[31];
        int i, j, command, dotm, result;
        int seating[32][9];
        for(i = 1; i < 32; i++){
                for(j = 1; j < 9; j++){
                        seating [i][j] = j;
                }
        }

        printf("Welcome to ZOOM airlines.  Please enter the name of the passenger information file: ");
        scanf("%s", filename);

        input = fopen(filename, "r");

        do{
                fscanf(input, "%d", &command);
                result = 0;
                switch(command){
                        case 1:
                                fscanf(input, "%s %d %s %s", eat, &dotm, lastname, firstname);
                                result = allotseat(lastname, firstname, dotm, seating);
                                if(!result) printf("Sorry, all seats booked for flight ZM101 for date %d\n", dotm);
                                break;
                        case 2:
                                fscanf(input, "%s %d %s %s", eat, &dotm, lastname, firstname);
                                result = cancel(lastname, firstname, dotm, seating);
                                if(result) printf("No booking for %s %s was listed for %d.\n", lastname, firstname,
                                dotm);
                                break;
                        case 3:
                                fscanf(input, "%s %d %s %s", eat, &dotm, lastname, firstname);
                                result = confirm(lastname, firstname, dotm);
                                if(result) printf("Yes, booking confirmed for %s %s.\n", lastname, firstname);
                                else printf("No booking found for %s %s.\n", lastname, firstname);
                                break;
                        case 4:
                                fscanf(input, "%s %d", eat, &dotm);
                                display(dotm);
                                break;
                        case 5:
                                fscanf(input, "%s %d", eat, &dotm);
                                seatdisplay(dotm, seating);
                                break;
                };

        }while(command != 6);

        printf("Good bye!\n");

        fclose(input);


        return 0;

}

int allotseat(char last[], char first[], int day, int seats[][9]){
        int i, test = 0;

        for(i = 1; i < 9; i++){
                if(seats[day][i] != 0){
                        seats[day][i] = 0;
                        test = i;
                        break;
                }
        }

        if(test != 0) insertnode(last, first, day, test);

        return test;
}

void insertnode(char last[], char first[], int day, int seatinfo){
        booking *current = head;
        booking *new = malloc(sizeof(booking));

        int i, test = 1;

        printf("%s %s booked on ZM101 May %d seat %d\n", last, first, day, seatinfo);

       do{

                if(current -> next == NULL){

                        current -> next = new;
                        strcpy(last, new -> last);
                        strcpy(first, new -> first);
                        new -> date = day;
                        new -> seat = seatinfo;
                        new -> next = NULL;
                        test = 0;
                }

                else if(strcmp(last, current -> next -> last) < 0){

                        new -> next = current -> next;
                        current -> next = new;
                        strcpy(last, new -> last);
                        strcpy(first, new -> first);
                        new -> date = day;
                        new -> seat = seatinfo;
                        test = 0;
                }

                else if(strcmp(last, current -> next -> last) == 0){

                        if(strcmp(first, current -> next -> first) < 0){

                                new -> next = current -> next;
                                current -> next = new;
                                strcpy(last, new -> last);
                                strcpy(first, new -> first);
                                new -> date = day;
                                new -> seat = seatinfo;
                                test = 0;
                        }
                }

                current = current -> next;
        }while(test);

}

int cancel(char last[], char first[], int day, int seats[][9]){
        booking *current = head, *temp;
        int test = 1, seatinfo, result = 0;

        do{
                if(strcmp(last, current -> next -> last) == 0){

                        if(strcmp(first, current -> next -> first) == 0){

                                if(day == current -> next -> date){

                                        seatinfo = current -> next -> seat;

                                        if(current -> next -> next == NULL){
                                                free(current -> next);
                                                test = 0;
                                        }

                                        else{
                                                temp = current -> next;
                                                current -> next = current -> next -> next;
                                                free(temp);
                                                test = 0;
                                        }
                                }
                        }
                }

                else if(current -> next == NULL){
                        test = 0;
                        result = 1;
                }

                current = current -> next;
        }while(test);

        seats[day][seatinfo] = seatinfo;

        if(!result) printf("Booking cancelled for %s %s for flight ZM101 May %d.\n", last, first, day);

        return result;
}

int confirm(char last[], char first[], int day){
        booking *current = head;
        int test = 1, result;

        do{
                if(strcmp(last, current -> next -> last) == 0){

                        if(strcmp(first, current -> next -> first) == 0){

                                if(day == current -> next -> date){

                                        result = 1;
                                        test = 0;
                                }
                        }
                }

                else if(current -> next == NULL){

                        result = 0;
                        test = 0;
                }
        }while(test);

        return result;
}

void display(int day){
        booking *current = head;
        int test = 1;

        printf("Passenger list for ZM101 May %d.\n", day);

        do{

                if(current -> next -> date == day){

                        printf("%s %s %d\n", current -> next -> last, current -> next -> first, current -> next ->
                        seat);
                }

                else if(current -> next == NULL) test = 0;

                current = current -> next;
        }while(test);

}

void seatdisplay(int day, int seats[][9]){
        int i;

        printf("Seats ZM101 May %d [ ", day);

        for(i = 1; i < 9; i++){

                printf("%d ", seats[day][i]);

        }

        printf("\n");
}

davekw7x · #2 26-Mar-2005, 08:17

Quote:

Originally Posted by DCOM

It seems every program that I write always ends up with segmentation faults, no matter how hard I try to prevent them. Since looking at your own code at 2:00AM is nothing like having someone else look at your code, I decided to post it up here.

I think that expecting other people to look at your 250+ lines of code and spot your problems isn't entirely realistic (but it could happen).

I think that debugging your own code is more instructive, and is usually faster than posting a request for help and waiting for a helpful response.

So, after looking at your own code until you are really, truly sick of it, here's a plan for debugging:

Put printf() statements at various places in the code so that you can see what's really happening. This also gives you a chance to see if there are any places that you could improve your error checking (to prevent those dreadful segment faults).

Here's a few hints to get started. First, make sure that files are successfully opened:

CPP / C++ / C Code:

  printf("Please enter the name of the passenger information file: ");
  scanf("%s", filename);
  printf("You entered %s\n", filename);

  if ((input = fopen(filename, "r")) == NULL) {
    printf("Can't open input file %s\n", filename);
    return 0;
  }
  else {
    printf("Opened input file %s\n", filename);
  }

After scanf statements, make sure that the program is working on what you think it should be:

CPP / C++ / C Code:

    fscanf(input, "%d", &command);
    printf("DEBUG1: command = %d\n", command);

Now, just these two steps pointed out the following to me as I ran it with assign3_file1.txt:

The first two lines of the file went through OK with the following output

Quote:

Welcome to ZOOM airlines.
Please enter the name of the passenger information file: assign3_file1.txt
You entered assign3_file1.txt
Opened input file assign3_file1.txt
DEBUG1: command = 1
Budd Turner booked on ZM101 May 4 seat 1
DEBUG1: command = 1
Jain Ankur booked on ZM101 May 8 seat 1
DEBUG1: command = 3

Now the program hung up (ctrl-c got me out of it).

So, I don't know if command = 1 is working OK or not, but I do see that command = 3 is giving me grief.

So put in a few more debug statements. Let's concentrate on command 3 for now:

First of all you didn't check the struct allocated at the beginning of the program. It's highly unlikely that malloc() will fail to give you the storage, but you should always check. Note that most segfaults are caused by a program attempting to access memory not allocated to it. This may be dynamic memory, where the pointer got corrupted by a program bug, or may be statically allocated memory where the program attempted to access memory outside of an array's bounds.

In this case I will actually print out the value of the pointer returned by malloc(). (Your global variable "head" is set to this value; I will check it later in the program to make sure it's ok.)

So your malloc() at the beginning of main() looks something like this:

CPP / C++ / C Code:

   if ((head = malloc(sizeof(booking))) == NULL) {
    printf("malloc can't allocate %d bytes. Program is terminated\n", 
        sizeof(booking));
    return 0;
  }
  else {
    printf("head = %p, sizeof(head) = %d\n", head, sizeof(head));
  }

Now, we want to see what's the story with command=3, so in your switch statement in main(), put in something like this:

CPP / C++ / C Code:

      case 3:
        printf("DEBUG2: case 3\n");
        fscanf(input, "%s %d %s %s", eat, &dotm, lastname, firstname);
        printf("DEBUG3: eat = %s , dotm = %d, lastname = %s, firstname = %s\n",
            eat, dotm, lastname, firstname);
        printf("Calling confirm %s, %s, %d\n", lastname, firstname, dotm);
        result = confirm(lastname, firstname, dotm);
        printf("from confirm(), result = %d\n", result);

Then, in confirm(), put in something like this;

CPP / C++ / C Code:

  printf("In confirm: last = %s, first = %s, day = %d\n", last, first, day);
  printf("head = %p, current = %p\n", 
          head, current);
  printf("current->next = %p, current->last = %p\n", 
          current->next, current->last);
  do {
    printf("current->next = %p, current->last = %p\n", 
            current->next, current->last);

I got an infinite loop scrolling very fast. When I hit ctrl-c, I saw a screen full of this:

Quote:

current->next = 0xa052b10, current->last = 0xa051cd

So, I put in a getchar() just after the printf in the do{

then, after hitting Enter a few times the following is on the screen:

Quote:

DEBUG1: command = 1
Budd Turner booked on ZM101 May 4 seat 1
DEBUG1: command = 1
Jain Ankur booked on ZM101 May 8 seat 1
DEBUG1: command = 3
DEBUG2: case 3
DEBUG3: eat = L.A. , dotm = 4, lastname = Campbell, firstname = James
Calling confirm Campbell, James, 4
In confirm: last = Campbell, first = James, day = 4
head = 0xa051cd0, current = 0xa051cd0
current->next = 0xa052b10, current->last = 0xa051cd0
current->next = 0xa052b10, current->last = 0xa051cd0
current->next = 0xa052b10, current->last = 0xa051cd0

current->next = 0xa052b10, current->last = 0xa051cd0

current->next = 0xa052b10, current->last = 0xa051cd0

current->next = 0xa052b10, current->last = 0xa051cd0

current->next = 0xa052b10, current->last = 0xa051cd0

Now, that should be telling us something. You take it from here. Maybe command=1 wasn't doing its job; you can put debug statements to see how it is working (show pointers returned from malloc() if you need to see how the links are actually linking). Maybe command=1 is OK but something is wrong with command=3. Maybe both, maybe something else, maybe...

Summary: segfaults are usually caused by accessing memory that doesn't belong to the program. (Also sometimes by recursive function calls that get out of control, but that doesn't apply here.)

Put debug printf statements at various places in your program to see how far it gets, and what it's working with at the time.

getchar() sometimes is needed to prevent the program from running away (Sometimes a program has tried to print out your debug statements and the segfault occurs before the output buffer has actually sent text to the screen, so you won't see all of the debug statements.)

In any case, if the program is actually accessing illegal storage, say, due to uninitialized variables, the exact symptoms may be different with different compilers and different systems, so one gives an infinite loop, another simply hangs up, so you have to hit ctrl-c, another gives a seg fault, etc. The approach to debugging is the same:

printf() is your friend.

Regards,

Dave

We can face our problem.
We can arrange such facts as we have with order and method.

---Hercule Poirot
Murder on the Orient Express

DCOM · #3 26-Mar-2005, 12:28

I actually did give it a cursory lookover last night to see if something jumped out at me, but nothing did. I fully planned to debug it today, I just posted it to see if I could get a second opinion. Thanks for the pointers though.

DCOM · #4 26-Mar-2005, 23:08

Actually, I do have a specific question now. After throwing in some debugging printf statements, I've narrowed down a problem with the insertnode function. When it finds the correct position to insert the node, it is supposed to copy the name information to the node using the strcpy function(the only way I currently know how to do this). However, it seems that for some reason, this function won't work for a pointer to a structure.

The specific lines are

CPP / C++ / C Code:

strcpy(last, new -> last);
strcpy(first, new -> first);

Anyone have any idea why these two lines aren't valid? I don't get a compile time error, so the function is receiving the correct data types. It just seems that at run time, something is screwy.

nkhambal · #5 27-Mar-2005, 00:00

argument to strcpy() are as follows

CPP / C++ / C Code:

 char *strcpy(char *dest, const char *src);

it copies "src" string to the "dest" string. Looking at your code you need to have following

CPP / C++ / C Code:

strcpy(new->last, last);
strcpy(new->first, first);

thanks,

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Airport Log program using 3D linked List : problem reading from file	batrsau	C Programming Language	11	29-Feb-2008 07:44
[Include] Doubly-linked List	dsmith	C Programming Language	6	14-Apr-2006 13:12
help on linked lists any1?????	nick4	C Programming Language	1	17-May-2004 09:32
linked lists, newbie needs help	moltarim	C Programming Language	4	06-May-2004 11:32
Linked lists	vortz83	C++ Forum	3	20-Mar-2004 06:56