I am confused....

This is a discussion on I am confused.... within the C++ Programming forums, part of the General Programming Boards category; I wrote a VERY cheaply written version of a text editor. Believe me...it was CHEAP! Anyway, the way I did ...

  1. #1
    Refugee face_master's Avatar
    Join Date
    Aug 2001
    Posts
    2,052

    I am confused....

    I wrote a VERY cheaply written version of a text editor. Believe me...it was CHEAP! Anyway, the way I did it was save the text that the user had inputted (btw, it was in DOS) and saved it into a char array. Ofcourse the program had bugs...but this guy (unregistered) told me that this was not correct to write it like that. He said that it was better to "store each line as a node in a linked list". What i'd like to know is what this means and how to go about doing it.

    Thankyou
    -Chris

  2. #2
    Registered User
    Join Date
    Aug 2001
    Posts
    223

    linked list

    a linked list is an ADT(abstract data type). The list composed of nodes where each node contains two items data and a pointer to the next node to the next node. The linked list can grow dynamically as the nodes are created on the fly (unlike an array).
    A list typically has a head (top of list), a tail (bottom of the list), to find an item in the list you must walk through the list beginning on one end (most lists allow two way navigation and some only alllow one way) Let's stick with one way for now.
    Three actions may be performed with this list typically -- delete a node, insert a node, and search for a node.

    In your case your nodes could be made up of the string of chars -- holding only one line per node and a pointer to the next node. Well enough theory.
    Here is how you can create a list in C++, although you do not need to because they already exist in the template library. Also MFC has some awesome lists objects where all you have to do is create the string add it to the list.

    // ** create the node struct
    struct myNode{
    public:

    char myLineBuffer[100];
    myNode *pNext; //pointer to a node

    };

    // ** Declare the basic nodes
    myNode* pHead;
    myNode* pTail;

    //** Declare the insertion method and define it
    void AddTail(myNode* pHead, char* myString)
    {

    myNode* pPrevious = NULL;

    if(pHead == NULL)
    return;

    while(1)
    {
    pPrevious = pHead; //hold pointer to the previous node
    pHead = pHead->pNext; //traverse the pointer to the next node
    if(pHead == NULL)
    break; //break out of endless loop
    }
    pPrevious->pNext = new myNode; //create new node
    pPrevious->pNext->pNext = NULL; //new node's next NULL
    strcpy(pPrevious->pNext->myLineBuffer, myString); //copy string
    }


    //perform a search on the list
    myNode* FindExact(myNode* pHead, char* myString)
    {

    if(pHead == NULL)
    return NULL; //empty list

    while(1)
    {
    if(strcmp(pHead->myLineBuffer, myString) == 0)
    {
    return pHead; //return pointer to found string
    }

    pHead = pHead->next; //advance to next node
    if(pHead == NULL)
    break; //reached the end of the list with no success
    }

    return pHead;
    }

    //returns true if deleted false otherwise
    //call like this Delete(&pHead, pNodeToDel)
    //where bothn are declared as myNode* types
    //** allows deletion of head from within delete
    //assignment of null
    BOOL Delete(myNode** pHead, myNode* pNodeToDel)
    {

    myNode* temp = *pHead;

    if(pNodeToDel == NULL || pHead == NULL)
    return false;

    //special case head is the node to delete
    if(temp == pNodeToDel)
    {
    del *pHead;
    *pHead = NULL; //head is now null
    }

    while(1)
    {
    pPrevious = temp;
    *temp = *(pTemp->pNext);
    if(pTemp == NULL)
    break;
    //if node to delete is found
    if(pTemp == pNodeToDel)
    {
    if(pNodeToDel->pNext == NULL)
    { //no nodes follow
    del pNodeToDel;
    Previous->pNext = NULL;
    }
    else{
    //hold reference to next node after the one to del
    pTemp = pNodeToDel->pNext;
    del pNodeToDel; // delete node
    pPrevious->pNext = temp; //relink the chain
    }
    return true;
    }
    }
    return false;
    }
    void main(void)
    {

    char* myChar = {"Mickey Mouse"};
    char* myChar2 = {"Donald duck"};
    char* myChar3 = {"Goofy too!!"};


    //inserting at the head is a special case
    pHead = new myNode;
    pHead->pNext = null;
    strcpy(pHead->myLineBuffer, myChar);

    AddTail(pHead, myChar2);
    AddTail(pHead, myChar3);

    //find a given node based on value
    myNode* pRemove = FindExact(pHead, myChar2);

    //delete a node that node
    Delete(&pHead, pRemove);
    }


    //whoowi!!! anyway this is just a rough pseudo code
    //not a running program
    //a linked list can be implemented in a class which
    //already exist you just have to know how to use the
    //interface


    Anyway this is the main idea. You can add as many data members as you want
    and in addition to pNext you can have a pPrevious to allow navigating both ways. The idea behing the list is that you are using pointers to reference other nodes.
    pThisPointer = pThatPointer; is called traversing
    because they are passing addresses

    that is why when you pass pHead to some function
    the original pHead pass to the function continues pointing
    at the location prior to entering the function
    the function has mere created a copy of the pointer but is
    not the pointer.
    Confusing????!!! I would think so it took me two classes to begin to understand linked lists

    someFunction(pHead )
    {
    pHead = pHead->pNext;
    }
    zMan

  3. #3
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Here is an example using templates



    Code:
    #include <iostream>
    using std::cout;
    using std::endl;
    
    #include <list>
    using std::list;
    
    // main returns int!
    int main(void)
    {
        list<char*> L;
        
        L.insert(L.begin(), "Hello World!");
        L.insert(L.begin(), "Good bye!");
        L.insert(++L.begin(), "Inbetween");
    
        // traverse list
        typedef list<char*>::const_iterator LI;
        
        for (LI i = L.begin(); i != L.end(); ++i) 
            cout << *i << endl;
    
        return 0;
    }


    You will have to read a little infomation on how the stl works. Once

    you know how to use a list creating a list shouldn't be too hard.

  4. #4
    Registered User
    Join Date
    Sep 2001
    Posts
    2

    Cool a .h for (linux) linked lists (first thing I ever wrote in c++)

    Hey there. I'm totally new to c++, so I decided to get some excercize by putting this linked list thing to the test. I created a nodelist class and a node struct with functions to browse through the list. No search functions as yet, but they shouldn't be hard to implement.

    I used this .h to create a _very_ basic 'text editor' which uses cin.getlines to create nodes in a 'buffer' nodelist. After entering lines it would use the firstnode() function of the 'buffer' object to move to the root node, followed by a while loop checking for buffer.eol, using buffer.nextnode() to traverse the list (and write the node values to a file using buffer.getvalue()).

    This code might be useful to any other beginner c++ coders, including the creator of this thread (if I do say so myself ). Personally I'd like to know if I handled the pointers correctly and if I implemented the strcpy() properly. I don't want to make this a 'please check my code' kind of post, but it would be very helpful to me if someone could have a look and point out any issues...

    Anyway, here's the code:

    ---linklist.h---

    Code:
    #include <string.h>
    
    struct node {
     char text[100];
     node *nNode;
     node *pNode; 
    };
    
    class nodelist {
     public:
      bool bol;
      bool eol;
      nodelist(char *value) {
       root = new node;
       current = new node;
       root->pNode = NULL;
       root->nNode = NULL;
       strcpy(root->text, value);
       last = root;
       current = root;
      };
      ~nodelist() {
       current = root;
       dellist();
      };
    
      void dellist() {
       if (current->nNode!=NULL) {
        current = current->nNode;
        dellist();
       }
       root = current;
       delete current;
       current = root->pNode;
      }
    
      void addnode(char *value){
       current = last;
       node *a;
       a = new node;
       strcpy(a->text,value);
       current->nNode=a;
       a->pNode=current;
       current = a;
       last = a;
       a->nNode = NULL;
      }
    
      void insertnode(char *value){
       node *a;
       a = new node;
       strcpy(a->text,value);
       a->nNode=current;
       a->pNode=current->pNode;
       current->pNode->nNode = a;
       current->pNode = a;
       current = a;
       last = a;
      }
    
      void deletenode(){
       current->pNode->nNode=current->nNode;
       current->nNode->pNode=current->pNode;
       delete current;
       current = root;
      }
    
      void nextnode() {
       check();
       if (!eol) current=current->nNode;
      }
    
      void prevnode() {
       check();
       if (!bol) current=current->pNode;
      }
    
      void firstnode() {
       current=root;
       check();
      }
    
      void lastnode() {
       current=last;
       check();
      }
    
      char * getvalue() {
       return current->text;
      }
    
     protected:
      node *root;
      node *current;
      node *last;
    
      void check() {
       if (current->pNode == NULL) bol = true;
        else bol = false;
       if (current->nNode == NULL) eol = true;
        else eol = false;
      }
    };
    Thanks in advance,

    TheMouth

  5. #5
    zen
    zen is offline
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    I've not had a thorough look but you've created an extra node in your constructor that has current initially pointing to it but shortly after you point current back to your root loosing a pointer to what current was pointing to creating a small memory leak.

  6. #6
    Registered User
    Join Date
    Sep 2001
    Posts
    2

    tnx

    You're right, the line with current = new node; should be left out.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Confused with array size
    By desmond5 in forum C Programming
    Replies: 4
    Last Post: 12-04-2007, 04:14 PM
  2. New to C++ and confused by boolean and ifs and else
    By jconner in forum C++ Programming
    Replies: 10
    Last Post: 08-02-2006, 03:29 AM
  3. So Now Im getting confused?!?!?
    By zergdeath1 in forum C++ Programming
    Replies: 11
    Last Post: 03-06-2004, 04:41 PM
  4. confused.. in selecting my line of deapth
    By jawwadalam in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 05-04-2003, 01:21 PM
  5. Extern Question, really confused
    By SourceCode in forum C Programming
    Replies: 10
    Last Post: 03-26-2003, 10:11 PM

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