Thread: need help w/ linked lists

  1. #1
    Registered User
    Join Date
    Aug 2002
    Posts
    24

    Question need help w/ linked lists

    I am a high school student doing a summer project in AI.
    I am not experienced enough with linked lists and I need your help to put some values into linked list.

    I would like to make 4 linked lists (superarrays). Can I use this one function below for all 4 linked lists?
    What is the headRef variable for? Does it contain the name of the linked list?

    Please help me build a linked list that would seek 2nd, 3rd, 4th, and 42nd field in the following line and append each new value within that field to this field's linked list. Fields are groups of values that are between commas.
    // I decided to use linked lists rather than arrays because in the array you have to know the length of the array, but I do not know how many values each field has.
    Also, I am working in the linux environment and use g++ compiler (both C and C++)... but I doubt that this compiler is any different from the Turbo C++ compiler
    --------------------------------------------------------------------------------------------------------
    For example:
    the lines are:
    0,tcp,http,SF,241,259,0,0,1,0,0,etc...,0,normal.
    0,tcp,smtp,SF,432,543,0,0,1,0,0,etc...,0,normal.
    0,udp,ftp,SF,511,777,0,1,1,0,0,etc...,0,normal.
    (the actual dataset is much longer and consists of 43 fields)
    The program should put the values of second field (tcp,udp,etc...) into the linked list #2 (because the source file is huge and I dont know how many values each field has), and values of field 3 (http, smtp, ftp, etc...) into a separate linked list #3. Provided that the code for extracting these fields is known and each field is stored in char buff[50] (I am not asking you to create a whole program), can you please help me put nonnumerical fields into linked list that after going through all source file would assign different values within the same field different numbers. If for example, for field 3 http was the first value added to liked list #3, it would be assigned 1, smtp would be assigned 2, and ftp would be assigned 3, and so on depending on the order these values were extracted from the source file.
    Below is the function that would append new fields to the linked list. And below that, there is a complete code of the program that extracts nonnumerical fields from the source file.

    ==================================================
    ======================
    Function for appending new values to the linked lists.
    --------------------------------------------------------------------------------------------------------------
    Code:
    struct node* AppendNode(struct node** headRef, char var[50]) {
        struct node* current = *headRef;
        struct node* newNode;
        newNode = malloc(sizeof(struct node));
        newNode->data = var;
        newNode->next = NULL;
    // special case for length 0
        if (current == NULL) {
            *headRef = newNode;
        }
        else {
    // Locate the last node
            while (current->next != NULL) {
                current = current->next;
            }
            current->next = newNode;
        }
    }
    ==================================================
    ============
    The actual code of field seeking program
    -------------------------------------------------------
    Code:
    #include <string.h>
    #include<iostream.h>
    #include<fstream.h> 
    #include<ctype.h>
    int main() 
    { 
        const long BUFF_SIZE = 1000000;
        int a, b, c;
        ifstream infile;
        ofstream outfile;
        char buff[BUFF_SIZE];
        char outbuff[BUFF_SIZE];
        char output[50][50]; // using an array of char arrays.
    // open the files
        infile.open("data.txt");
        outfile.open("output.txt");
    // make sure the files are open
        if(!infile.is_open()){
            cerr << "error opening input file";
            return 1;
        }
        if(!outfile.is_open()){
            cerr << "error opening output file";
            return 1;
        }
    // loop until the end of the input file
        for(a=0; !infile.eof(){
    // read in one line
            infile.get(buff, BUFF_SIZE, '.');
            infile.ignore(1);
    // loop through each char in the current line
            for(b=c=0; buff[b]; ++b){
    // eat whitespace
                while(buff[b] == ' ')
                    ++b;
    // ignore numbers and commas in the input
    // copy everything else to the output buffer.
                if(!isdigit(buff[b]) && buff[b] != ','){
                    outbuff[c++] = buff[b];
                }
    // when we come to a comma or the end of the input buffer
    // AND there is something in the output buffer,
    // move contents of output buffer to the next array in the output 2D array.
    // print the output to the screen and the output file
                if((buff[b] == ',' !buff[b+1]) && strlen(outbuff) > 0){
                    outbuff[c] = '\0'; 
                    strcpy(output[a], outbuff);
                    cout << output[a] << endl;
                    outfile << output[a] << endl;
    // increment the end output array counter
                    ++a;
    // start the output buffer counter again
                    c = 0;
    // reset the output buffer
                    outbuff[0] = '\0';
                }
            }
        }
    // close the files
        infile.close();
        outfile.close();
    // pause so you can see the output on the screen
        cout << " **** All done! ****\n";
        cin.get();
        return 0;
    }
    --------------------------------------------------------------------------------

    -----------------------------------------
    Thanks alot! =),



    __________________
    Dmitry Kashlev
    Dmitry Kashlev

  2. #2
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Well I could give you code that would do exactly what you want. But I think you may not be doing this the way that you should. You should use vectors instead of linked lists. That way you would be using arrays!

  3. #3
    Registered User
    Join Date
    Aug 2002
    Posts
    24

    Wink

    Is it possible to use vectors if you don't know the actual number of values in each field?

    I would be happy if you could give me your code.
    Thanks for helping me out.

    ~Dmitry
    Dmitry Kashlev

  4. #4
    Registered User
    Join Date
    Jan 2002
    Posts
    552
    if you know the maximum number of values you data will consist of, you can create an array with the maximum size and keep an integer that tells you the amount of meaningful data you have in the array

    If you must use linked lists.... check on the FAQ board, search this board or search the web. Youll find a plethora of info on them

  5. #5
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,138
    Originally posted by MKashlev
    Is it possible to use vectors if you don't know the actual number of values in each field?

    I would be happy if you could give me your code.
    Thanks for helping me out.

    ~Dmitry
    Yep, that is the basic idea behind vectors. You can resize them using the resize method.

    vector <int> bunch;//could be of any data type by changing int to whatever
    bunch.resize(5);//resizes the vector to hold 5 items

  6. #6
    Registered User
    Join Date
    Jan 2002
    Posts
    552
    if your going to be doing alot of resizing you definitely would be better off sticking with linked lists since the buffer is dumped and recreated each time the resize method is called

  7. #7
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    Originally posted by *ClownPimp*
    if your going to be doing alot of resizing you definitely would be better off sticking with linked lists since the buffer is dumped and recreated each time the resize method is called
    yes and no. If I'm not mistaken, allocation of a large buffer is not necessarily slower than allocation of a small amount. So you might gain in the memcpy step not being there but not in the allocation. Linked lists and trees can be slow because of lots of allocations.

    Best way....

    allocate a vector to a reasonable size. When you need more, allocate a good sized chunk so that you don't have to keep allocating on every entry.

  8. #8
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    vector doesn't allocate small chunks anyway. It doubles it's size if it needs more room.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  9. #9
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    Originally posted by SilentStrike
    vector doesn't allocate small chunks anyway. It doubles it's size if it needs more room.
    Is that right? I always was afraid of push_back() because I thought it had to realloc every time. that's pretty cool.

  10. #10
    Seeking motivation... endo's Avatar
    Join Date
    May 2002
    Posts
    537
    Originally posted by SilentStrike
    vector doesn't allocate small chunks anyway. It doubles it's size if it needs more room.
    Thats why they have a resize function. That way you can control it a bit better than just doubling the space everytime.
    Couldn't think of anything interesting, cool or funny - sorry.

  11. #11
    Registered User
    Join Date
    Aug 2002
    Posts
    24

    Arrow

    Linked List is not required, but suggested. If there is another way, i would be happy to hear it from you...
    Dmitry Kashlev

  12. #12
    linked lists are very useful in situations with changing number of stuff. Like if you do a particle engine. It is also useful in stuff like animation and AI.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Singly Linked Lists: Clarification Needed
    By jedispy in forum C++ Programming
    Replies: 4
    Last Post: 12-14-2006, 05:30 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 11:32 PM
  4. Linked Lists Integer addition ? HELP Please??
    By green_eel in forum C Programming
    Replies: 3
    Last Post: 03-12-2003, 04:36 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM