Thread: How to use Linked List?

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

    Question How to use Linked List?

    I am a high school student doing a summer project in AI. I am not experienced in Linked Lists, and I need your help to put some values into the 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! =),
    Last edited by MKashlev; 08-04-2002 at 05:22 PM.
    Dmitry Kashlev

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Like this?

    Code:
    struct htmlData
    (type) 2nd, 3rd, 4th, 42nd;
    
    
    int Split(struct node* _node, char *buff)
     {
      char *start, *stop;
    
      hData = new htmlData;
      
      while(buff)  
      while(!done)
      //retrieve a line...
      //find first element...find last element...copy *start->*stop->2nd;
      //if necessary, 2nd = (atof(char2nd)), etc...
      //repeat till 42nd...
      //if none found, don't append, delete chunk...otherwise append... 
      //...return # of lines split...or total elements...etc...
     }
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

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

    Question how would you do that?

    How would you do that? I am pretty inexperienced in linked list, so can you please write a code? Your algorithm seems fine to me.

    Thx,

    ~Dmitry
    Dmitry Kashlev

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

    Question a note:

    also, i need to come up with sequence for each field separately (2nd field- 1,2,3,...; 3rd field - 1,2,3,...; and so on).

    thx
    Dmitry Kashlev

  5. #5
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784

    Re: How to use Linked List?

    Originally posted by MKashlev

    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;
        }
    }

    Code:
    void AppendNode(struct node** headp, char var[50]) {
        struct node *currentp, *previousp, *newp;
        currentp = previousp = newp = NULL;
        newp = malloc(sizeof(struct node) );
    //Perform deep copy
        strcpy( newp->data,var );
        newp->next = NULL;
    // special case for length 0
        if (*headp == NULL) {
            **headp = *newp;
        }
        else {
    // Locate the last node
      currentp = headp;
            while (current->next != NULL) {
      previousp = currentp;
                current = current->next;
            }
            previousp->next = newp;
        }
    }
    I forget, it's been ages, but the code for adding a node goes something like this. There are sure to be a few errors. I did not test the code, but this is the basic idea for appending a node to a linked list. You don't need to return the list because your using a pointer to a pointer. Someone else can fix the errors.
    Last edited by Troll_King; 08-06-2002 at 07:13 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM