Circular linked list to print last N lines of file

This is a discussion on Circular linked list to print last N lines of file within the C Programming forums, part of the General Programming Boards category; Hey all, its my first post here and I'm looking forward to learning c with some of the other newbs ...

  1. #1
    Registered User
    Join Date
    Oct 2008
    Posts
    18

    Circular linked list to print last N lines of file

    Hey all, its my first post here and I'm looking forward to learning c with some of the other newbs like me.
    My professor assigned a program that must read in lines from a file and print the last n number of lines in the most efficient way, so reading thru the file once to obtain a line count is out of the question, i must use a circular linked list. I have this code so far which seems like its just a few lines away from success.
    Please help, thank you.
    Input file
    Code:
    aaa
    bbb
    ccc
    ddd
    eee
    fff
    ggg
    hhh
    My code
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    struct node{
      char string[80];
      int value;
      struct node *next;
    };
    int main()
    {
      void insert(struct node **, struct node **, int);
      struct node *head, *tail, *temphead;
      int num=0; int i = 0;
      FILE *finp;
      char *infile = "inp.dat";
    
      finp = fopen(infile, "r");
    
      head = tail = temphead = NULL;
      printf("Enter list size\n");
      scanf("%d", &num);
    
      while(i<=num)
        {
          insert(&head, &tail, i);
          i++;
        }
      temphead = head;
    
      while(head->next   != head)
        {
          if((fgets(head->string, 81, finp))!=NULL)
            {
              head = head->next;
              printf("how many");
            }
          else
            break;
    
    
            }
      head = temphead;
      i=0;
      while(head != tail)
        {
          i++;
          printf("%s", head->string);
          head  = head->next;
        }
    
    }
    
    void insert(struct node **h, struct node **t, int val)
    {
      struct node *temp;
      temp = (struct node*)malloc(sizeof(struct node));
      temp->value = val; temp->next = *h;
      if(*h == NULL)
        {
          *h = *t = temp;
        }
      else
        {
          (*t)->next = temp; *t = (*t)->next;
        }
    }
    my output
    Code:
    fff
    ggg
    hhh
    ddd
    it shoud be putting the ddd in front and bumping the rest down.

    Thanks!

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    It's always a good idea, when one's wishes contradict the reality of a program, to sit down with a piece of paper and trace through the execution of the program to see what's happening. It's even more important, when you do this, to trace the code as it actually is, rather than what you want it to be. If we do that here, this is what we get:
    1. We open the file.
    2. The person types 4 in response to the prompt.
    3. We put 5 nodes in our circular linked list (labeled 0, 1, 2, 3, and 4).
    4. We put line a into node 0.
    5. We put line b into node 1.
    6. We put line c into node 2.
    7. We put line d into node 3.
    8. We put line e into node 4.
    9. We put line f into node 0.
    10. We put line g into node 1.
    11. We put line h into node 2.
    12. We reset the head back to node 0.
    13. We print the first four nodes in the list (starting at 0) -- these are lines f, g, h, and d from above.
    14. We neglect to print the last one.

    The highlighted parts are those which seem incorrect, in the grand scheme of things.

  3. #3
    Registered User
    Join Date
    Oct 2008
    Posts
    18

    Got it, but seg fault when i implement to my main function

    The code worked 100% independently but when i implemented it into my main function it has a seg fault. I have this prog split up into multiple files so i was wondering if its ok to have a seperate file function that has its own function in that file. Does the insert() need to be declared in my main?

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Insert isn't declared in your main now (in what you posted). I'm not sure what you're asking.

  5. #5
    Registered User
    Join Date
    Oct 2008
    Posts
    18

    scratch that

    That one piece i showed you was just a part of a 5 piece program, but i just did it independently first to get it working.


    scratch that last post, just forgot to put error checking for negative integers and it was freaking out my linked list.
    Thanks for all the help tabstop, I appreciate it.

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    I would warn you that if the goal is to use a linked list, great, but if the goal is to do it "in the most efficient means possible" -- not necessarily with a linked list -- then doing it with a linked list would be very far from your goal.

    I think you should be able to do this in less than twenty lines.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #7
    Registered User
    Join Date
    Oct 2008
    Posts
    18

    I agree

    My prof said we need to use a circular linked list unless we can do it without reading through the file twice or saving unnecessary lines of a file to a string.
    I originally did it by running through the file and counting the lines then just printed the last n but I was told "ABSOLUTELY NOT" by him.

  8. #8
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by FortinsM3 View Post
    My prof said we need to use a circular linked list unless we can do it without reading through the file twice or saving unnecessary lines of a file to a string.
    I originally did it by running through the file and counting the lines then just printed the last n but I was told "ABSOLUTELY NOT" by him.
    If you read through the file and always kept the last two lines, when you reached the EOF you would have the last three lines, and nothing superfluous in memory. You would have to do this in any case -- but it would be simpler using 3 char* string buffers than a linked list. Like I said, less than twenty lines.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Using a linked list globally and File I/O
    By Leftos in forum C Programming
    Replies: 46
    Last Post: 01-07-2008, 10:21 AM
  2. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 12:21 PM
  3. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  4. Line Counting
    By 00Sven in forum C Programming
    Replies: 26
    Last Post: 04-02-2006, 08:59 PM
  5. Replies: 3
    Last Post: 03-04-2005, 01:46 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21