Why Data Structures???...QUESTIONS INSIDE

[Fasola]

I HAVE SPECIFIC QUESTIONS!!!

1. Why do you need Self-Referential Classes? Please provide a "real" life example of when it would be used.

class Node {
public:
	Node(int);
	void setData(int);
	int getData() const; 
	void setNextPtr( const Node *);
	const Node *getNextPtr() const;
private:
	int data;
	Node *nextPtr;
};

2. ^^^What is a Node, is it just a random name for this Class?

3. what does the (const Node *) mean in:

void setNextPtr(const Node *);

4. why is nextPtr the, "Link?"

I understand Dynamic Memory Allocation, somewhat, but

5. Can somebody break down these two lines of code form me?:

Node *newPtr = new Node(10);

delete newPtr;

DEFINITION

A Linked List is a linear collection of self-referential class objects, called nodes, connected by pointer links.

6. What is that definition REALLY saying (plain english)?

According to my text book, "...if Nodes contain base-class pointers or base-class references to base-class and derived-class objects related by inheritance, we can have a linked list of such nodes and use Virtual Function calls to process these objects polymorphically...."

7. Can you please explain or provide an example of what is really being said here ^^^?

I think I understand how Stacks and Queues work, so I'll leave those alone until I think otherwise, but

8. How does a Tree work and what is it's purpose?

:?:

[marinme]

1. Why do you need Self-Referential Classes? Please provide a "real" life example of when it would be used.

Well... self-referential class - a class that refers to itself. This is shown in the Node * nextPtr data member. the main reason you would use this is to actually link to the next Node in the linked list/tree/other data structure. A "real" life example you would use this in? Other than use in data structures I can't link of a use for it.

2. ^^^What is a Node, is it just a random name for this Class?

A Node an object which stores your data/other objects.. works kind of like a cable connection. Think of them as local areas, like neighborhoods.

3. what does the (const Node *) mean in:

void setNextPtr(const Node *);

Well, what does the const qualifier do? Makes data unchangeable? you should be able to figure out the rest by the name of the function.

4. why is nextPtr the, "Link?"

it points to the next Node object.

5. what does can somebody break down these two lines of code form me?:

Node *newPtr = new Node(10);

delete newPtr;

The first line creates another node that you can add to the list. The second deletes that node from memory.

DEFINITION

A Linked List is a linear collection of self-referential class objects, called nodes, connected by pointer links.

6. What is that definition REALLY saying (plain english)?

Let's look at this logically... pull out key phrases..
linear collection - collection in a linear(a line) order
I defined self-referential class objects above.
pointer links - this is where the Node * nextPtr comes into play, as I said above, points to the next node.

According to my text book, "...if Nodes contain base-class pointers or base-class references to base-class and derived-class objects related by inheritance, we can have a linked list of such nodes and use Virtual Function calls to process these objects polymorphically...."

7. Can you please explain or provide an example of what is really being said here ^^^?

This is kind of a difficult subject to explain... do you know anything about inheritance/polymorphism? your answer lies in research of the previously listed topics.

8. How does a Tree work and what is it's purpose?

:?:

what kind of tree do you mean? there are different tree data structures..

And if this post didn't help, here are some links regarding linked lists for you to do some further research:

http://www.inversereality.org/tutorials/c++/linkedlists.html
http://www.fredosaurus.com/notes-cpp/index.html go to structs near the bottom.

That should be enough to get ya started

[Narue]

>1. Why do you need Self-Referential Classes?
It's the easiest way to implement non-contiguous data structures. You don't need them, but they make life easier.

>2. ^^^What is a Node, is it just a random name for this Class?
Node

>3. what does the (const Node *) mean in
It's a pointer to a Node that shouldn't be modified.

>4. why is nextPtr the, "Link?"
That's basic data structure terminology. A "link" leads from one node to another.

>Node *newPtr = new Node(10);
It creates a Node, calls the constructor with the value 10, and assigns the address of it to newPtr.

>delete newPtr;
It releases the memory pointed to by newPtr. This only works predictably for memory returned by new.

>6. What is that definition REALLY saying (plain english)?
That's an awful explanation of a linked list. Sadly, it's not that simple when first introducing people to the concept. This provides more suitable information.

>7. Can you please explain or provide an example of what is really being said here ^^^?
Basically, you can have a linked list of polymorphic types.

>8. How does a Tree work and what is it's purpose?
Go here and read up on the tutorials that talk about binary trees. When someone talks about a tree, they usually mean a binary search tree.

[Fasola]

First of all Thank you both Marinme and Narue...that's real helpful

Na, That link you gave me to wikipedia was exactly what I needed. I've been going from one definition to another for the last hour and a half. I have a few interesting questions, but have run out of (session) time in this public library computer, will be back ;)

[Fasola]

Lets see if i've learnt anything and if I am getting this:

Okay so a Linked List is just a list of Nodes

Nodes are basicly just Structs/Classes

the Members of these Nodes contain data (such as Values of Objects) and Pointers to the previous or next Node on a Linked List

a Linked List's primary use is to access data (i.e. Nodes or Members of Nodes) that are not contiguously (i.e. adjacent) to eachother. So, it's safe to say a Linked List is primarily used to increase effiecency (i.e. speed up) the process of accessing data at runtime. It's kind of like an "Index" in general or in a database.

NOTE: I am not sure how to utilize this in real world programming!

damn, another session time has ended, I'll be back :(

[Fasola]

I was reading up on Trees, can I get an example of a Binary Tree (top down) and a B-Tree (ground up)?

More importantly, what the two types of Trees are good for, in real word programming?

[Narue]

>can I get an example of a Binary Tree (top down)
The link I gave you covers these in detail.

>and a B-Tree (ground up)?
These are complicated enough that example code will be hard to find, but you shouldn't have any trouble finding B-tree info on google. I won't give you code or concepts because the search will be good for you.

>what the two types of Trees are good for, in real word programming?
Binary trees (usually of the binary search tree variation) have a wide range of uses. A good simple example is a large phonebook, where the records must be sorted, but still quickly accessible. B-trees are primarily used as external storage structures for databases.

[Fasola]

>can I get an example of a Binary Tree (top down)
The link I gave you covers these in detail.

>and a B-Tree (ground up)?
These are complicated enough that example code will be hard to find, but you shouldn't have any trouble finding B-tree info on google. I won't give you code or concepts because the search will be good for you.

>what the two types of Trees are good for, in real word programming?
Binary trees (usually of the binary search tree variation) have a wide range of uses. A good simple example is a large phonebook, where the records must be sorted, but still quickly accessible. B-trees are primarily used as external storage structures for databases.

gotcha!

was i right about this (below):

http://www.daniweb.com/techtalkforums/showpost.php?p=110622&postcount=5

[Narue]

>was i right about this (below):
More or less. Linked lists can be more efficient than arrays, but the inverse can also be true. It depends on what you need. You use an array when you need fast random access, you know roughly how many items ther will be, and items will only be added to the end of the array. This is because arrays can access any item with an index very quickly. With linked lists, you would be forced to follow links until you found the right item. However, insertion into an array is potentially expensive because you need to shift every item that goes after the new item to make room. Resizing an array (if possible) is tedious and error prone, so it's best avoided when possible.

You use a linked list when you don't know how many items there will be, you may insert an item anywhere in the list, and random access is not a primary goal. Because linked lists are non-contiguous, insertion is a trivial matter of simply resetting a few links, so the operation is very efficient no matter where you insert. Linked lists are inherently dynamic, so you don't have to bend over backward to get them to resize themselves.

>I am not sure how to utilize this in real world programming!
File processing. You need to read all of the lines in a file and then sort them. You could use an array, but then you would have to guess at how many lines are in the file, or try to implement a resizable array. Using a linked list is easier and cleaner. Now you have more comfortable options. For example, you can use an unsorted linked list, count the number of lines, then create an array of pointers and sort that, or you could maintain a sorted linked list from the start.

[kc0arf]

Hello,

Excellent discussion so far. Wondering if you would expand it a bit more, and discuss sorting a linked list. Perhaps also go into double-linked lists (when I write them, I write these too, so I can easily go backwards). You guys are on such a good role..

Christian

[tonakai]

a linked list can be sort by two way, while inserting a data, or sorting it after inserting data....
first while inserting data, you will start from the beginning and try to find a place for your data and insert it, so your linked list will always be sorted.
other way is you simply insert your data at the end on list, then you can sort it whenever you want...
either of them has some advantages and disadvantages... so you need to choose one of them according to your need.

[Fasola]

>I am not sure how to utilize this in real world programming!
File processing. You need to read all of the lines in a file and then sort them. You could use an array, but then you would have to guess at how many lines are in the file, or try to implement a resizable array. Using a linked list is easier and cleaner. Now you have more comfortable options. For example, you can use an unsorted linked list, count the number of lines, then create an array of pointers and sort that, or you could maintain a sorted linked list from the start.

I'm with you on this one Na, I'm all over this linked list stuff now. (finished reading up on inheritance too, now looking up virtual functions and polymorphism).

Question 1, I fail to make a clear and distinct comparison between linked list and arrarys. Isn't an linked list more powerful than an array because nodes are classes/structs that can hold member functions and not just member data?

Question 2, There's a whole chapter on file processing i'll have to read next to get up to speed, but are you telling me that linked lists are used for file processing only?

Damn I want to know what you mean in that last sentence!!!

[Narue]

>Isn't an linked list more powerful than an array
Which data structure is more powerful depends solely on how you intend to use it. That's why there are so many data structures. You can simulate any data structure with an array, but the benefits of those data structures are diminished when you do so. Different problems, different solutions, and all that jazz. :)

>because nodes are classes/structs that can hold member functions and not just member data?
You can have an array of structs/classes, so that's hardly a reason to favor linked lists.

>but are you telling me that linked lists are used for file process only?
No, I was giving you an example where arrays start to fail and linked lists start to look good. The linked list is a fundamental data structure that's used all across the board, not just in file processing. The limits of where you can use them are determined by your imagination alone.

[Fasola]

a linked list can be sort by two way, while inserting a data, or sorting it after inserting data....
first while inserting data, you will start from the beginning and try to find a place for your data and insert it, so your linked list will always be sorted.
other way is you simply insert your data at the end on list, then you can sort it whenever you want...
either of them has some advantages and disadvantages... so you need to choose one of them according to your need.

what's the big deal with having to sort a linked list? or better yet sort them according to what (i.e. date, time, numerically, priority, etc.)?

[Narue]

>what's the big deal with having to sort a linked list?
?

>sort them according to what (i.e. date, time, numerically, priority, etc.)?
That's up to the application. If you have a linked list of employee records then you can sort by first name, last name, date of hire, salary bracket, (etc...) or even all of them in any order.

[Fasola]

>Isn't an linked list more powerful than an array
Which data structure is more powerful depends solely on how you intend to use it. That's why there are so many data structures. You can simulate any data structure with an array, but the benefits of those data structures are diminished when you do so. Different problems, different solutions, and all that jazz. :)

>because nodes are classes/structs that can hold member functions and not just member data?
You can have an array of structs/classes, so that's hardly a reason to favor linked lists.

>but are you telling me that linked lists are used for file process only?
No, I was giving you an example where arrays start to fail and linked lists start to look good. The linked list is a fundamental data structure that's used all across the board, not just in file processing. The limits of where you can use them are determined by your imagination alone.

Ahhhh man, seems like arrarys can do a lot more than I thought, i'm only use to seeing them hold numbers or character as elements, never seen an array with a struct in it, what would that look like?

[tonakai]

>sort them according to what (i.e. date, time, numerically, priority, etc.)?
That's up to the application. If you have a linked list of employee records then you can sort by first name, last name, date of hire, salary bracket, (etc...) or even all of them in any order.

yep, thats what i was going to say.
you are fast! :D

[Narue]

string array[50]; // 50 string objects

struct rec {
  char name[11];
  int age;
};

rec records[50]; // 50 rec objects

Everything is fairly consistent, even if it doesn't seem that way at first. You access an element of one of those arrays by taking the index and then using the member access operator:

strcpy ( records[5].name, array[5].substr ( 0, 10 ).c_str() );
cout<< records[5].name <<endl;

[Fasola]

>what's the big deal with having to sort a linked list?
?

>sort them according to what (i.e. date, time, numerically, priority, etc.)?
That's up to the application. If you have a linked list of employee records then you can sort by first name, last name, date of hire, salary bracket, (etc...) or even all of them in any order.

Okay, so a linked is just a form of "indexing"?

>File processing. You need to read all of the lines in a file and then sort them. You could use an array, but then you would have to guess at how many lines are in the file, or try to implement a resizable array. Using a linked list is easier and cleaner. Now you have more comfortable options.

I am so lost by that Na. How would you make an array work with a file or even a linked list for that matter?

[Fasola]

you are fast! :D

yes she is...hahaha

amazing, i love it :)

[Narue]

>Okay, so a linked is just a form of "indexing"?
A linked list is just a way to structure data so that certain operations are more efficient than others. Insertion into an array is inefficient while indexing is fast, switching to a linked list reverses those roles. The more you work with data, the more you'll realize that the same data can be represented any number of ways. Some of them good, some of them bad. That's why we have so many data structures. And all a data structure does is hold data.

>How would you make an array work with a file or even a linked list for that matter?
when processing a file, you read a record and then do something with it. When working with an array, that something would be to add the record to the array. When working with a linked list, that something would be to add the record to the linked list.

[Fasola]

>Okay, so a linked is just a form of "indexing"?
A linked list is just a way to structure data so that certain operations are more efficient than others. Insertion into an array is inefficient while indexing is fast, switching to a linked list reverses those roles. The more you work with data, the more you'll realize that the same data can be represented any number of ways. Some of them good, some of them bad. That's why we have so many data structures. And all a data structure does is hold data.

>How would you make an array work with a file or even a linked list for that matter?
when processing a file, you read a record and then do something with it. When working with an array, that something would be to add the record to the array. When working with a linked list, that something would be to add the record to the linked list.

GOT IT, I GOT IT, I GOT IT! Just found an example in my book it shows you how to use ofstream to open a file, like this:

ofstream outClientFile("clients.dat", ios::out);

and the it goes on

THANX Na', you just added value to what i've been learning, now i know how to work with files ;)

YES!

[Narue]

>ofstream outClientFile("clients.dat", ios::out);
ofstream opens files using the ios::out mode by default, so you could do this:

ofstream outClientFile("clients.dat");

And the effect would be the same.

[Fasola]

>ofstream outClientFile("clients.dat", ios::out);
ofstream opens files using the ios::out mode by default, so you could do this:

ofstream outClientFile("clients.dat");

And the effect would be the same.

To get the same effect do you have to have the <iostream.h> header or <fstream.h>?

Also, did ios::out in parenthesis work as an argument?

[Fasola]

^^^^

lol @ :o...how did you? Ahhhhh forget it!

:)

[Narue]

>To get the same effect do you have to have the <iostream.h> header or <fstream.h>?
ofstream is declared in <fstream> (or <fstream.h> if you use a pre-standard compiler).

>Also, did ios::out in parenthesis work as an argument?
Yes. The constructor for basic_ofstream takes two arguments: a path and an open mode. The open mode for basic_ofstream is defaulted to ios_base::out, which is equivalent to ios::out.

[Fasola]

my book mentions basic_istringstream < char >, basic_ostringstream < char >, basic_string < char > and basic_string

There is no mention of basic_ofstream, what does it mean?

[Narue]

All of your streams are actually typedef's. istream is a typedef for basic_istream<char, type_traits<char> >, ostream is a typedef for basic_ostream<char, type_traits<char> >, ifstream is a typedef for basic_ifstream<char, type_traits<char> >, ofstream is a typedef for basic_ofstream<char, type_traits<char> >, and so on.

The idea is that streams don't care what type of character they use, so you can define a character type and set up the char_traits for it, maybe make your own stream buffer, then plug it in to the existing framework. Boom! You've saved yourself several hundred lines of reinventing the wheel.

Unless your book doubles as a reference, or happens to be exceptionally detailed, it won't say a thing about the template classes hidden by those typedef's.

[Fasola]

All of your streams are actually typedef's. istream is a typedef for basic_istream<char, type_traits<char> >, ostream is a typedef for basic_ostream<char, type_traits<char> >, ifstream is a typedef for basic_ifstream<char, type_traits<char> >, ofstream is a typedef for basic_ofstream<char, type_traits<char> >, and so on.

The idea is that streams don't care what type of character they use, so you can define a character type and set up the char_traits for it, maybe make your own stream buffer, then plug it in to the existing framework. Boom! You've saved yourself several hundred lines of reinventing the wheel.

Unless your book doubles as a reference, or happens to be exceptionally detailed, it won't say a thing about the template classes hidden by those typedef's.

Na, I don't know how you know all this stuff, but I hope to be there one day, seriously

I was reading JoBe's thread on classes and i got lost lost lost, i just don't know enough to follow along *frustrated*, but so i'll know before hand what's predefined in libraries, where can I get access to the find out what's inside these "standard libraries", is there a site I can go to?

[Narue]

>Na, I don't know how you know all this stuff
Well, I'm in a somewhat unique position. I've actually implemented the standard libraries, whereas most people are only on the client end.

>where can I get access to the find out what's inside these "standard libraries"
The best reference you can get is the ISO C++ standard. It's available as a book from Wiley (ISO/IEC 14882:1998), or with the latest technical corrigendum from www.ansi.org. The most recent document is ISO/IEC 14882:2003. Of course, if you can't handle that (and most people can't), www.dinkumware.com has a good reference for the standard library.