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
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
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.
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---
Thanks in advance,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; } };
TheMouth
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.
You're right, the line with current = new node; should be left out.
