linkedlist in c language

Discussion in 'General Linux' started by duaa shloul, Oct 24, 2013.

  1. duaa shloul

    duaa shloul New Member

    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    1
    i have to write a c code to read a billions of integer from textfile .. each integer is of 10 digit .. then i have to build a linkedlist to store these integer ...


    ... now my question is : If i have to search for a number in the linked list, how much time it takes to traverse the linkedlist ???

    i have already tried this code :


    #include <stdio.h>

    #include <malloc.h>

    #include <stdlib.h>




    void main()

    {

    struct node

    {

    int num;

    struct node *ptr;

    };

    typedef struct node NODE;



    NODE *head, *first, *temp = 0;

    int count = 0;

    int choice = 1;

    first = 0;




    FILE *f = fopen("file.txt", "w");
    if (f == NULL)
    {
    printf("Error opening file!\n");
    exit(1);
    }


    int i = 0;






    for (i = 0; i < 100000; i++)
    {





    fprintf(f, " %d ", i);

    }
    fclose(f);



    FILE *file = fopen ("file.txt", "r");



    fscanf (file, "%d", &head-> num);
    while (!feof (file))
    { head = (NODE *)malloc(sizeof(NODE));

    printf ("%d ", i);
    fscanf (file, "%d", &head-> num);

    if (first != 0)

    {

    temp->ptr = head;

    temp = head;

    }
    else

    {

    first = temp = head;

    }

    fflush(stdin);

    }






    fclose (file);



    temp->ptr = 0;
  2. ryanvade

    ryanvade Administrator Staff Member Staff Writer

    Messages:
    1,341
    Likes Received:
    447
    Trophy Points:
    83
  3. Joe_M

    Joe_M New Member

    Messages:
    1
    Likes Received:
    1
    Trophy Points:
    1
    There are a couple of things that I think need improvement. When you insert a number don't just stick on the end put it in order. It will make your life much better in the long run. The next thing you do is a binary search for the integer. Don't assume you have 10000 integers. Very wasteful. Keep track of how many integers you have. Or you can delve into the "sizeof" operator. Because you have been inserting the integers in order you can do a binary search. You split the list in half. The head of the lower half of the list will either be greater or less them what you are looking for. If it's greater just dump the top half of the list and split the lower half. If it's less then dump the lower half. At this point I think I have pointed you in the right direction. Now lookup in your book about binary searches. Remember when you are inserting an integer use the same code you use to find an integer. Code reuse!!! You can also do this recursively but I will leave that as an exercise for you. Joe_M
    ryanvade likes this.
  4. ryanvade

    ryanvade Administrator Staff Member Staff Writer

    Messages:
    1,341
    Likes Received:
    447
    Trophy Points:
    83
    Selection sort to put the numbers in order. :)

Share This Page